In sequential decision-making, a learner repeatedly chooses an action and observes its outcome. Traditionally, this field is divided into two informational extremes:
- The Multi-Armed Bandit (MAB) Setting: The learner only observes the reward or loss of the chosen action. This partial-information constraint forces a strict trade-off between exploration and exploitation, typically resulting in a minimax regret that scales with the square root of the number of actions $K$, i.e., $\mathcal{O}(\sqrt{KT})$.
- The Expert Advice Setting: The learner observes the rewards or losses of all possible actions, regardless of which one was chosen. With this full-information feedback, the learner can evaluate counterfactuals, allowing the regret to scale much more gracefully as $\mathcal{O}(\sqrt{T \log K})$.
Real-world applications rarely sit at these extremes. For instance, in a social network recommendation system, showing an item to a user might reveal their preferences for that item, but it also provides side-observations about highly similar items or the preferences of connected friends.
To bridge this gap, Shie Mannor and Ohad Shamir introduced the framework of feedback graphs in From Bandits to Experts: On the Value of Side-Observations. By modeling side-information as a graph where nodes represent actions and directed edges represent visibility, graph-theoretic regret bounds precisely quantify how "a little bit of extra information" accelerates learning.
The Geometry of Information: From Cliques to Independence
To understand why graph-structured feedback reduces regret, we must look at how graph topology alters the effective dimensionality of the action space.
The Clique Cover Perspective
An intuitive way to quantify side-observations is to group mutually informative actions together. If a subset of actions forms a clique (a fully connected subgraph), choosing any single action within that clique reveals the losses of all other actions in the clique.
Early graph-feedback algorithms leveraged this insight. As shown by Stéphane Caron et al. in Leveraging Side Observations in Stochastic Bandits, the learning complexity can be bounded by the clique cover number $\chi(G)$—the minimum number of cliques needed to cover all nodes. By treating each clique as a collective information unit, the effective number of actions shrinks from $K$ to $\chi(G)$, yielding regret bounds proportional to $\sqrt{\chi(G)T}$. This framework was similarly extended to Thompson Sampling by Aristide C. Y. Tossou in Thompson Sampling for Stochastic Bandits with Graph Feedback, demonstrating that exploiting network cliques significantly outperforms standard bandit exploration.
The Independence Number Breakthrough
While the clique cover number provides a natural starting point, it can be overly pessimistic. A graph might require many cliques to cover its nodes, yet still possess high information density.
A foundational shift occurred when Noga Alon et al. proved in From Bandits to Experts: A Tale of Domination and Independence that the true fundamental limit of learning is governed by a tighter combinatorial property: the independence number $\alpha(G)$. The independence number is the size of the largest set of nodes where no two nodes are connected by an edge.
$$\alpha(G) \le \chi(G) \le K$$
Why does $\alpha(G)$ dictate the fundamental limit of exploration? Consider an independent set of actions. By definition, choosing one action in this set provides absolutely zero information about any other action in the set. Therefore, the independence number represents the minimum number of actions that must be explicitly explored to guarantee that no hidden, highly rewarding action is missed. The authors proved that for undirected graphs, the minimax regret scales tightly with $\sqrt{\alpha(G)T}$, completely bypassing the larger clique cover number.
Observability Regimes and Regret Phase Transitions
When feedback graphs are directed, the directionality of information flow introduces structural asymmetries. In Online Learning with Feedback Graphs: Beyond Bandits, Noga Alon et al. established that the topology of directed graphs forces a stark phase transition in the achievable minimax regret, categorizing learning problems into three distinct structural regimes:
[Information Structure] ──► Strongly Observable ──► Regret: O(√(α · T))
──► Weakly Observable ──► Regret: O(T^(2/3))
──► Unobservable ──► Regret: O(T)
1. Strongly Observable Graphs
A graph is strongly observable if every node either has a self-loop (choosing it reveals its own loss) or is observed by at least one neighbor. In this regime, the learner can always construct low-variance, unbiased estimators for the losses of all actions. The minimax regret remains in the standard square-root regime, scaling as $\widetilde{\mathcal{O}}(\sqrt{\alpha(G) T})$.
2. Weakly Observable Graphs
The problem becomes significantly harder when certain nodes lack self-loops but have incoming edges from other nodes. This means you can only learn about action $A$ by choosing a different action $B$. However, choosing action $B$ might incur massive loss, and action $B$ might not even reveal its own outcome.
In this weakly observable regime, standard square-root regret is mathematically impossible. The authors showed that the minimax regret undergoes a phase transition, slowing down to $\widetilde{\mathcal{O}}(T^{2/3})$. Here, the complexity is governed by the weak domination number $\gamma_w(G)$—the size of the smallest set of nodes that can collectively observe the entire graph. To minimize regret, algorithms must restrict their exploratory actions to this weakly dominating set, balancing the cost of pulling suboptimal "informant" nodes against the value of the global information they reveal.
3. Unobservable Graphs
If there is even a single node that lacks a self-loop and cannot be observed by any neighbor, the graph is unobservable. The learner can never gain information about this action without choosing it, yet choosing it reveals nothing. In this catastrophic regime, the minimax regret scales linearly ($\Omega(T)$), making sublinear learning impossible.
Algorithmic Adaptations to Graph Feedback
To exploit these graph-theoretic bounds, classic online learning algorithms must be modified to pool information across neighboring nodes.
Modifying Importance Sampling
In adversarial settings (like the EXP3 framework), importance sampling is used to maintain unbiased loss estimators. For standard bandits, the estimated loss $\hat{\ell}_i(t)$ for action $i$ is scaled inversely by its selection probability $p_i(t)$. With a feedback graph, because action $i$ can be observed whenever any neighbor $j$ in the neighborhood $N(i)$ is selected, the estimator is modified to scale by the total probability mass of its neighborhood:
$$\hat{\ell}_i(t) = \frac{\ell_i(t)}{\sum_{j \in N(i)} p_j(t)} \mathbb{I}\{X_t \in N(i)\}$$
This pooling reduces the variance of the estimators. By incorporating this graph-aware loss estimator into Follow-the-Regularized-Leader (FTRL) or mirror descent frameworks, Shinji Ito et al. developed "Best-of-Both-Worlds" algorithms in Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs that automatically adapt to achieve optimal $\sqrt{\alpha(G)T}$ regret in adversarial environments and poly-logarithmic regret in stochastic environments.
Information-Directed Exploration
In stochastic settings, algorithms can explicitly optimize the information-exploration trade-off. Fang Liu et al. demonstrated in Information Directed Sampling for Stochastic Bandits With Graph Feedback that Information Directed Sampling (IDS) is uniquely suited for graph feedback. Instead of choosing actions based solely on individual upper confidence bounds, IDS minimizes the ratio between the squared expected regret and the expected information gain about the optimal arm, explicitly prioritizing central nodes that illuminate large subgraphs.
Learning in the Dark: Uninformed Feedback Graphs
A major practical hurdle is that the underlying feedback graph is often unknown to the decision-maker before an action is selected.
Alon Cohen and Tamir Hazan exposed a fundamental "information gap" in Online Learning with Feedback Graphs Without the Graphs: if the environment is adversarial and the graph is hidden, side-observations become theoretically useless because the adversary can dynamically manipulate the unobserved information flow.
However, in stochastic environments, learning remains highly effective even without prior knowledge of the graph. Fang Liu et al. proved in Analysis of Thompson Sampling for Graphical Bandits Without the Graphs that standard Thompson Sampling is inherently robust; by simply updating its posterior distributions whenever side-observations appear, its cumulative regret naturally scales with the average independence number of the hidden graphs without needing to see the network topology in advance.
For complex contextual scenarios where actions depend on user features, Mengxiao Zhang et al. introduced the SquareCB.UG algorithm in Efficient Contextual Bandits with Uninformed Feedback Graphs. This approach couples online regression with a log-loss objective to implicitly learn the graph's connectivity pattern on the fly. As a result, the contextual bandit's learning complexity is successfully decoupled from the total number of actions, scaling instead with the underlying independence number of the hidden feedback structure.
Key Foundational Work
From Bandits to Experts: On the Value of Side-Observations (2011) — contributed 3 concept elements to this direction.