Online Learning with Feedback Graphs

21 concepts17 papers1 proposal

In sequential decision-making, we traditionally operate at two extremes of the information spectrum. In the classic multi-armed bandit setting, an agent only observes the reward of the specific action it chooses. In the full-information (or expert) setting, the agent observes the rewards of all possible actions, regardless of its choice.

Real-world applications rarely fit neatly into these extremes. Consider a recommendation system: if a platform suggests a specific sci-fi movie, a user's click or skip explicitly reveals their interest in that movie. However, it also provides side observations about highly related sci-fi movies. To capture this intermediate reality, a powerful framework has emerged: modeling side observations as a feedback graph.

The Feedback Graph Intuition

Formally, we represent the action space as a directed or undirected graph $G = (V, E)$, where each node represents an action (or "arm"). When an agent selects a node $i \in V$, it receives the reward for $i$, but it also observes the rewards of any neighboring nodes $j$ connected by an edge $(i, j)$.

As shown by Shie Mannor et al. in From Bandits to Experts: On the Value of Side-Observations, this graph structure acts as a mathematical bridge between bandits and full-information settings. If the graph contains only self-loops, the problem reduces to a standard multi-armed bandit. If the graph is fully connected, it becomes a full-information expert problem.

The core reason this framework works is sample efficiency. Instead of updating a single reward estimate per round, the agent propagates a single interaction across multiple neighboring actions, drastically reducing the exploration required to find optimal strategies.

How Graph Topology Dictates Learning Complexity

The fundamental difficulty of an online learning problem is typically governed by the number of actions $K$. However, in the presence of side observations, the structural topology of the feedback graph dictates how fast an agent can learn.

In their foundational work, Shie Mannor et al. demonstrated that the minimax regret—the measure of an algorithm's performance penalty relative to the optimal strategy—is tightly coupled to graph-theoretic properties like the independence number $\alpha(G)$. The independence number represents the largest set of vertices in a graph where no two nodes are connected. Intuitively, independent nodes represent actions that reveal zero information about one another. The larger this number, the more the agent is forced to explore actions individually, increasing regret.

To formalize this, Noga Alon et al. mapped out a complete classification of directed feedback graphs in Online Learning with Feedback Graphs: Beyond Bandits. They proved that graphs fall into three distinct structural regimes that determine problem difficulty:

  1. Strongly Observable Graphs: Every node can see its neighbors or itself. These yield "easy" problems with standard $\mathcal{O}(\sqrt{T})$ regret.
  2. Weakly Observable Graphs: Some nodes can only be observed by choosing other nodes. These yield "hard" problems with $\mathcal{O}(T^{2/3})$ regret.
  3. Unobservable Graphs: Certain nodes provide no information and cannot be observed by any action, making sublinear regret impossible.

Furthermore, Bingshan Hu et al. showed in Problem-dependent Regret Bounds for Online Learning with Feedback Graphs that problem-dependent regret scales with the clique covering number of the graph rather than the total number of actions. Because a clique is a fully connected subgraph, an agent can learn about every action within a clique by sampling its members, effectively collapsing a massive action space into a few highly informative clusters.

Algorithmic Paradigms for Side Observations

To exploit these structural properties, standard bandit algorithms must be modified to integrate neighborhood updates.

Graph-Aware Upper Confidence Bounds (UCB)

In stochastic environments, standard UCB algorithms maintain an uncertainty width for each action based on how many times it has been pulled. With graph feedback, algorithms like UCB-N and UCB-MaxN, introduced by Stéphane Caron et al. in Leveraging Side Observations in Stochastic Bandits, update the empirical reward estimates and shrink the confidence intervals of all neighboring nodes simultaneously. This significantly accelerates convergence, demonstrating up to 14x empirical speedups on real-world social network data where connections naturally dictate information flow.

Implicit Exploration (IX)

In adversarial environments, algorithms rely on importance-weighted estimators to maintain unbiased loss estimates. This requires dividing the observed loss by the probability of choosing that action. When side observations are present, an action can be observed through multiple paths, making these probabilities highly complex or entirely unknown if the graph structure is hidden.

To circumvent this, Tomás Kocák et al. developed the Implicit Exploration (IX) strategy in Efficient learning by implicit exploration in bandit problems with side observations. By adding a clever stabilization term directly to the loss estimators (e.g., in EXP3-IX), the authors proved that an agent can achieve near-optimal regret guarantees without needing to know the underlying observation network before making a decision.

Advanced Frontiers

The intuition of graph-structured feedback has expanded far beyond basic multi-armed bandits into complex, dynamic learning settings:

  • Post-Hoc Contextual Bandits: Traditional models assume the feedback graph is known before an action is selected. However, in applications like clinical trials, the structural relationship between treatments might only manifest after a choice is made. Mengxiao Zhang et al. addressed this in Practical Contextual Bandits with Feedback Graphs, designing computationally efficient algorithms capable of handling post-hoc feedback revelations.
  • Combinatorial and Path Planning Settings: When agents select subsets of actions simultaneously, the feedback graph scales in complexity. Yuxiao Wen extended this to adversarial combinatorial semi-bandits in Adversarial Combinatorial Semi-bandits with Graph Feedback, introducing an online mirror descent algorithm (OSMD-G) that leverages negative sampling correlations to achieve optimal minimax regret. Similarly, Dong Quan Vu et al. applied this to complex resource allocation scenarios like Colonel Blotto games in Colonel Blotto Games and Hide-and-Seek Games as Path Planning Problems with Side Observations.
  • Reinforcement Learning: Moving from stateless bandits to full Markov Decision Processes, Christoph Dann et al. formalized Reinforcement Learning with Feedback Graphs. In this setting, nodes represent state-action pairs, and edges represent transition-level side observations, allowing agents to update their internal world models for multiple transitions simultaneously.
  • Pure Exploration: In Best Arm Identification (BAI) tasks, the goal is to find the single best action as fast as possible without worrying about cumulative reward. In Pure Exploration with Feedback Graphs, Alessio Russo et al. provided the first comprehensive treatment of pure exploration under graph feedback, demonstrating how side observations can be systematically leveraged to minimize the sample complexity of identification tasks.

Key Foundational Work

Leveraging Side Observations in Stochastic Bandits (2012) — contributed 2 concept elements to this direction.
From Bandits to Experts: On the Value of Side-Observations (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_structured_feedback_fdf4d540,
  title = {graph-structured feedback},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-structured-feedback/rdr_fdf4d540e6874e459b2cbc191a60e15f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_structured_feedback_fdf4d540_v1,
  title = {graph-structured feedback},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-structured-feedback/rdr_fdf4d540e6874e459b2cbc191a60e15f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake