Source-linked AI summary
From Bandits to Experts: On the Value of Side-Observations
Shie Mannor, Ohad Shamir
TL;DR
The paper studies adversarial online learning when actions provide side observations about other actions, addressing the gap between full-information experts and bandit feedback. It formalizes these settings with time-varying graphs, develops practical algorithms, and derives graph-dependent upper and lower regret bounds. The results identify independence number and clique-partition structure as central quantities, while leaving gaps for directed and changing-graph settings.
Problem
Standard experts feedback reveals all rewards, whereas bandits reveal only the selected reward; the paper asks how to analyze intermediate graph-structured side observations.
Method
The paper models feedback with directed graphs and develops ExpBan for fixed graphs plus ELP for graphs that may change between rounds.
Results
Regret guarantees depend on graph independence and clique-partition numbers, with partially matching lower bounds and an information-theoretic lower bound for fixed graphs.
Takeaways & Limitations
Side observations yield a broad family of online-learning problems whose attainable regret is governed by non-trivial information-feedback structure.
Takeaways & Limitations
Upper and lower bounds essentially match only in particular settings, and the paper has no lower bound for changing graphs.
Abstract
from arXiv · showhide
We consider an adversarial online learning setting where a decision maker can choose an action in every stage of the game. In addition to observing the reward of the chosen action, the decision maker gets side observations on the reward he would have obtained had he chosen some of the other actions. The observation structure is encoded as a graph, where node i is linked to node j if sampling i provides information on the reward of j. This setting naturally interpolates between the well-known "experts" setting, where the decision maker can view all rewards, and the multi-armed bandits setting, where the decision maker can only view the reward of the chosen action. We develop practical algorithms with provable regret guarantees, which depend on non-trivial graph-theoretic properties of the information feedback structure. We also provide partially-matching lower bounds.
1 Introduction
The paper formalizes online learning with graph-structured side observations, interpolating between experts and bandits. It develops algorithms and bounds whose regret depends on graph properties, while addressing fixed and changing observation structures.
- Problem setting: The framework models partial feedback with directed graphs: sampling action i reveals sufficiently good information about selected other actions, potentially changing each round.Complete graphs recover experts, empty graphs recover bandits, and arbitrary intermediate graphs define the studied regime.
- Graph-dependent guarantees: The attainable regret depends on the graph’s independence number α(Gt) and clique-partition number χ̄(Gt).These measure, respectively, the largest edge-free node set and the smallest partition into cliques.
- Algorithms: ExpBan combines within-clique experts algorithms with a bandits algorithm over clique-level meta-actions, applying when the graph is fixed.Ignoring computational constraints, its guarantee uses χ̄(G) log(k)T; efficient computation may require a larger clique partition c.
- Algorithms: ELP handles graphs that change between rounds and provides guarantees for both undirected and directed observation structures.The paper presents ELP as more fundamentally novel and with superior guarantees, while directed-graph bounds depend on clique-partition quantities.
- Lower bounds and experiments: For fixed graphs, the paper gives an information-theoretic lower bound, and synthetic experiments indicate ELP’s advantage is not merely an artifact of analysis.The lower bound holds regardless of computational efficiency.
2 Problem Setting
The paper studies adversarial online learning with rewards in [0, 1], side-observations represented by time-varying directed graphs, and expected regret against the best action in hindsight.
- 2 Problem Setting: The learner chooses one of k actions per round and seeks to minimize regret against the best single action in hindsight.The setting assumes a finite horizon, expected regret bounds, and an oblivious adversary with rewards fixed in advance.
- 2 Problem Setting: ExpBan partitions the fixed graph into c cliques, runs an experts algorithm within each clique, and applies a bandits algorithm across the resulting meta-actions.The algorithm uses neighborhood sets as input and requires a fixed graph throughout the horizon.
- 2 Problem Setting: Choosing an action reveals its reward and may provide unbiased estimates of other actions’ rewards through side-observations.This extends standard bandit feedback by allowing information about additional actions.
- 2 Problem Setting: The feedback structure is modeled as a graph Gt, with an edge from i to j exactly when choosing i reveals information about j.The graph may be directed or undirected and can change between rounds.
3 The ExpBan Algorithm
ExpBan handles fixed observation graphs by combining experts and bandits algorithms over a clique partition. Its regret interpolates between experts and bandits regimes through the graph’s clique-partition number, while computation and a logarithmic factor limit the stated guarantee.
- 3 The ExpBan Algorithm: ExpBan partitions a fixed graph into cliques, learns within each clique using an experts algorithm, and treats the clique learners as meta-actions for EXP3.This combines an exponentially weighted forecaster with a standard multi-armed-bandits algorithm.
- 3 The ExpBan Algorithm: For the optimal clique partition, c equals the graph’s clique-partition number ¯χ(G).The clique-partition number ranges from 1 to k.
- 3 The ExpBan Algorithm: ¯χ(G)=1 yields the experts regime, where the algorithm attains O(log(k)T) regret because every action reveals estimates for all actions.A clique observation structure corresponds to the standard experts setting.
- 3 The ExpBan Algorithm: More sophisticated methods can remove the log(k) factor from the analysis, but the paper retains it for simplicity.The stated analysis uses the less tight logarithmic form.
- 3 The ExpBan Algorithm: ¯χ(G)=k yields the bandit regime, while general graphs interpolate between experts and bandits according to ¯χ(G).The empty graph corresponds to standard bandit feedback.
- 3 The ExpBan Algorithm: Finding a clique partition with c=O(k^(1−ϵ)) for any ϵ>0 is NP-hard for general graphs, limiting computationally efficient regret guarantees.The paper notes this is a worst-case disadvantage; good partitions may still be easy to compute for particular graph classes.
4 The ELP Algorithm
The ELP algorithm uses graph-aware exploration selected by linear programming and extends side-observation learning to time-varying graphs. Its guarantees depend on independence numbers for undirected graphs and clique-partition numbers for directed graphs, with computational workarounds for NP-hard quantities.
- 4 The ELP Algorithm: ELP combines exponentially weighted learning with a linear program that chooses graph-aware, rather than uniform, exploration probabilities.The exploration distribution reflects the graph structure at each round.
- 4.1 Undirected Graphs: For undirected graphs, ELP’s regret bound depends on the average independence number α(Gt) across rounds.The independence number is the size of the largest independent set in each graph.
- 4.1 Undirected Graphs: ELP can outperform ExpBan because α(Gt) lower-bounds the clique-partition number, and it also handles graphs that change between rounds.ExpBan applies only when the graph remains fixed and uses clique partitions.
- 4 The ELP Algorithm: Computing the optimal ELP parameter can require NP-hard graph quantities, but running ⌈log(k)⌉ copies as meta-actions preserves the regret up to logarithmic factors in k.One guessed value is within a factor of 2, and EXP3 selects among the copies.
- 4.2 Directed Graphs: For directed graphs, ELP’s guarantee uses the clique-partition number, yielding a weaker bound than the undirected guarantee based on α(Gt).The paper does not establish that this directed-graph bound is tight and conjectures that independence number is not the right measure there.
5 Lower Bound
The lower-bound analysis reduces independent vertices to a bandit-like hard instance. For constant undirected graphs, this lower bound matches ELP’s upper bound up to logarithmic factors, while directed graphs retain a gap between graph parameters.
- 5 Lower Bound: For a fixed graph, the lower bound is expressed in terms of its independence number α(G).The result assumes nonadjacent actions provide no side-observations.
- 5 Lower Bound: An adversary can make α(G) independent vertices behave like a standard multi-armed bandit with α(G) actions.The proof invokes the known Ω(√(nT)) bandit lower bound.
- 5 Lower Bound: For constant undirected graphs, the lower bound matches ELP’s regret upper bound up to logarithmic factors.For directed graphs, the comparison depends on the gap between clique-partition and independence numbers.
6 Examples
Graph structure can make side-observations either ineffective or highly valuable. The examples emphasize that independence and clique-partition numbers may yield sharply different regret guarantees.
- 6 Examples: A single super-action revealing every other reward is not helpful up to negligible factors because the graph’s independence number is k − 1.The lower bound therefore remains essentially as hard as the bandit setting.
- 6 Examples: With metric-based observations, α(G) corresponds essentially to the number of nonoverlapping radius-r spheres that can be packed.The clique-partition number instead corresponds to a covering quantity.
- 6 Examples: For constant-p random graphs, α(G) is O(log(k)) while the clique-partition number is at least Ω(k/log(k)).This separation produces substantially different regret bounds for ELP and ExpBan.
7 Empirical Performance Gap between ExpBan and ELP
Experiments on random graphs show that side-observations improve performance as graph density increases, while the empirical gap between ExpBan and ELP is largest at intermediate densities. The gap narrows again for nearly complete graphs.
- 7 Empirical Performance Gap between ExpBan and ELP: The experiment uses 300-node random Erdős–Rényi graphs, binary rewards, and one node with reward probability 3/4 instead of 1/2.Each action reveals the rewards of its graph neighbors, and results average 10 runs.
- 7 Empirical Performance Gap between ExpBan and ELP: For p = 0.05, the graph is sparse and all three algorithms perform roughly the same for the tested horizon.The advantage of side-observations is small in this regime.
- 7 Empirical Performance Gap between ExpBan and ELP: As p increases, the two side-observation algorithms outperform the standard multi-armed bandits algorithm.The experiments associate denser graphs with greater value from side-observations.
- 7 Empirical Performance Gap between ExpBan and ELP: At intermediate p values, ELP shows a noticeable performance advantage over ExpBan, matching the regime where their graph-based bounds differ most.The difference is attributed in the paper to the gap between clique-partition and independence numbers.
- 7 Empirical Performance Gap between ExpBan and ELP: For large p, the graph is nearly complete and ELP’s advantage over ExpBan becomes small.Most actions then provide information about most other actions.
8 Discussion
The paper studies online learning with side observations and shows that regret depends on graph structure, while identifying several gaps for future work.
- The study covers a broad regime interpolating between experts and bandits, with regret bounds depending non-trivially on feedback structure.
- Upper and lower bounds essentially match only in particular settings, including undirected graphs without additional side observations.
- Open questions include changing graphs, policy-based learning, high-probability bounds, and partially or approximately known observation structures.
- For complete and empty graphs, the relevant graph quantities both equal 1 and k, respectively; for constant p in (0, 1), they differ.
A.1 Proof of Thm. 1
The ExpBan proof combines an exponentially weighted forecaster within each clique with EXP3 across clique-level meta-actions, using unbiased reward estimates.
- Within each clique, the exponentially weighted forecaster samples actions by normalized weights and updates them using estimated rewards.The estimates are unbiased and bounded, enabling the analysis despite observing estimates rather than actual rewards.
- The forecaster’s expected regret against actions in a clique is bounded using an optimized parameter β.
- Each clique forecaster becomes a meta-action, and EXP3 is run over the resulting collection of clique-level meta-actions.
- Combining the within-clique and meta-action guarantees yields the total expected regret bound for ExpBan.
A.2 Proof of Thm. 2
The proof of Theorem 2 uses combinatorial lemmas to control graph-dependent estimation terms, then inserts those bounds into a potential-based analysis of ELP.
- The proof establishes three lemmas, including a key combinatorial inequality and a lemma giving an explicit choice of simplex weights.
- Lemma 3 bounds neighborhood-weight expressions using the graph’s independence number α(G).Its proof shifts weight between adjacent nodes until support lies on an independent set.
- Lemma 4 assigns equal weight to a largest independent set and shows every node’s closed neighborhood receives positive weight.
- The theorem proof applies a potential function, exponential inequalities, logarithms, telescoping, and expectation bounds to control regret.
- Using the minimizing choice of simplex weights together with Lemmas 3 and 4 completes the theorem’s graph-dependent upper bound.
A.3 Proof of Thm. 3
Theorem 3 derives lower bounds by reducing a side-observation algorithm on a graph to a standard bandit strategy over an independent set.
- For directed graphs, the analysis replaces the independence-number inequality with a weaker bound based on a smallest clique partition.
- The resulting bound is weaker than Theorem 2’s because the independence number is at most the clique-partition number.
- The lower-bound reduction assigns bandit actions to an independent set and uses the side-observation algorithm to construct a standard bandit strategy.
- Actions outside the independent set trigger pure-exploration steps, whose number is controlled through the algorithm’s regret.
- Applying the standard bandit lower bound yields a graph-dependent lower bound, with an improved threshold when maximum degree is bounded by d.