PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Learning with Feedback Graphs: Beyond Bandits

Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, Tomer Koren

arXiv:1502.07617v1cs.LG

TL;DR

The paper asks how feedback-graph structure determines the inherent difficulty of online learning, especially when players may not observe their own losses. It characterizes fixed, known graphs through graph properties and obtains three minimax-regret regimes, while also connecting the results to partial monitoring and varying graphs.

  • Problem

    The paper studies how feedback-graph structure controls the inherent difficulty of online learning when some actions' losses, including the player's own, may be unobserved.

  • Method

    The paper characterizes fixed, known feedback graphs using observability classes, independence number, and weak domination number.

  • Results

    The minimax regret is eΘ(α^1/2 T^1/2) for strongly observable graphs, eΘ(δ^1/3 T^2/3) for weakly observable graphs, and Θ(T) for unobservable graphs.

  • Takeaways & Limitations

    The characterization shows that small changes in feedback structure can substantially change learnability, including a jump to order T^2/3 after removing one loop.

Abstract

from arXiv · show

We study a general class of online learning problems where the feedback is specified by a graph. This class includes online prediction with expert advice and the multi-armed bandit problem, but also several learning problems where the online player does not necessarily observe his own loss. We analyze how the structure of the feedback graph controls the inherent difficulty of the induced $T$-round learning problem. Specifically, we show that any feedback graph belongs to one of three classes: strongly observable graphs, weakly observable graphs, and unobservable graphs. We prove that the first class induces learning problems with $\widetildeΘ(α^{1/2} T^{1/2})$ minimax regret, where $α$ is the independence number of the underlying graph; the second class induces problems with $\widetildeΘ(δ^{1/3}T^{2/3})$ minimax regret, where $δ$ is the domination number of a certain portion of the graph; and the third class induces problems with linear minimax regret. Our results subsume much of the previous work on learning with feedback graphs and reveal new connections to partial monitoring games. We also show how the regret is affected if the graphs are allowed to vary with time.

1 Introduction

The paper frames online learning through feedback graphs, focusing on how missing self-observation changes the game's inherent difficulty. It gives a three-way characterization of minimax regret based on graph structure and connects the framework to established feedback models and partial monitoring.

  • Problem setting: Online learning pits a randomized player against an arbitrary environment, with regret comparing cumulative loss against the best fixed action in hindsight.The player learns when regret after T rounds is o(T).
  • Feedback models: Feedback graphs generalize full feedback and bandit feedback by specifying which action losses are observed after each chosen action.Full feedback reveals all action losses, whereas bandit feedback reveals only the chosen action's loss.
  • Non-self-aware feedback: Missing self-loops create settings where players remain accountable for losses they cannot observe, including apple tasting and loopless-clique feedback.In the loopless clique, the player observes every other action's loss but not the chosen action's own loss.
  • Main characterization: The paper's main result completely characterizes minimax regret by categorizing feedback graphs into strongly observable, weakly observable, and unobservable classes.This characterization targets the inherent difficulty of the induced learning problem rather than the performance of one specific algorithm.
  • Main characterization: Strongly observable graphs have eΘ(α^1/2 T^1/2) regret, while weakly observable graphs have eΘ(δ^1/3 T^2/3) regret and are harder to learn.Here α is the independence number, and δ is the weak domination number.
  • Implications: Removing a single self-loop can change a graph's regret rate from eΘ(TK) to eΘ(T^2/3), illustrating the sensitivity of learnability to feedback structure.The paper also relates its three regret classes to easy, hard, and unlearnable partial-monitoring games and extends the analysis to time-varying, initially unknown graphs.

2 Problem Setting and Main Results

The paper models online learning through directed feedback graphs and characterizes minimax regret by graph observability. Strongly observable, weakly observable, and unobservable graphs yield distinct regret regimes, with sharp changes possible after removing only a few edges.

  • Problem Setting: A feedback graph records which action losses become observable after each action is chosen, including whether the chosen action’s own loss is observed.The player observes losses in the selected action’s out-neighborhood; without a self-loop, the selected action’s loss may remain unknown.
  • Problem Setting: Observability classifies vertices by incoming edges: strongly observable vertices have either a self-loop or incoming edges from every other vertex.Graphs are strongly observable when all vertices satisfy this condition, weakly observable when all are observable but not strongly, and unobservable otherwise.
  • Main Results: The weak domination number δ is the minimum size of a set whose outgoing edges cover every weakly observable vertex.The independence number α is the size of the largest set of vertices with no edges between distinct members.
  • Main Results: Theorem 1 gives minimax regret eΘ(α^1/2 T^1/2) for strongly observable graphs, eΘ(δ^1/3 T^2/3) for weakly observable graphs, and Θ(T) for unobservable graphs.Here α is the independence number and δ is the weak domination number, for fixed known graphs with T ≥ |V|^3.
  • Main Results: Removing at most two edges from a strongly observable graph can change the regret order from T^1/2 to T^2/3 and switch dependence from α to δ.The loopy star illustrates this abrupt transition; removing a single self-loop yields a weakly observable graph with regret eΘ(T^2/3).

3 The Exp3.G Algorithm

Exp3.G achieves the upper bounds for strongly and weakly observable feedback graphs by combining importance-sampled loss estimates with exploration distributions tailored to graph structure. A refined second-order Hedge bound supports the analysis, including a tight logarithmic bound for the loopless clique.

  • Algorithm design: Exp3.G uses importance sampling to construct unbiased loss estimates with controlled variance.The observation probability P_t(i) determines whether the estimate for action i is formed from the observed loss.
  • Algorithm design: The exploration distribution lower-bounds observation probabilities for selected actions, controlling estimator variance.For strongly observable graphs it is uniform over all vertices; for weakly observable graphs it is supported on a smallest weakly dominating set.
  • Upper bounds: For weakly observable graphs, Exp3.G uses a smallest weakly dominating set and obtains the corresponding upper bound under the stated horizon condition.The exploration distribution is uniform over the dominating set, whose size is δ.
  • Loopless clique: The loopless clique has regret O(T^1/2 ln(KT)) for Exp3.G and matches the full-feedback rate Θ(T^1/2 ln K) up to constants.Thus hiding the player’s own loss in this graph does not change the regret rate up to constants.
  • Refined analysis: The refined second-order Hedge bound improves dependence on actions whose losses do not exceed 1/η through factors involving 1−q_t(i).In Exp3.G, the bound is applied to estimated losses and strongly observable vertices without self-loops are included in the corresponding sets S_t.

4 Lower Bounds

The lower-bound analysis matches the upper-bound rates for weakly observable and non-observable graphs. It uses graph constructions to embed hard bandit instances or conceal a vertex’s losses from the player.

  • Strongly observable graphs: The known strongly observable lower bound, together with the new results, completes the characterization of Theorem 1.The cited lower bound applies to strongly observable graphs in the relevant horizon regime.
  • Non-observable graphs: Θ(T) regret follows for non-observable graphs because a vertex with no incoming edges can have an unknown loss fixed at either 0 or 1.The player has no feedback that distinguishes these two possibilities.
  • Graph construction: The graph-theoretic core extracts an independent set whose vertices are dominated only sparsely by every vertex in the graph.This connects weak domination to the independent structure needed for the hard instance.
  • Weakly observable graphs: The weakly observable lower bound is obtained by finding many weakly observable, sparsely dominated independent actions and embedding a hard stochastic bandit instance among them.All other vertices receive maximal loss, forcing exploration through actions outside the hard set.
  • Weakly observable graphs: Ω(δ/ε^2) exploration regret combined with the exploitation gap is maximized at ε=(δ/T)^1/3, yielding the stated weakly observable lower bound.The construction requires many outside actions to be sampled repeatedly for accurate estimates.

5 Time-Varying Feedback Graphs

Allowing feedback graphs to vary over time preserves the strongly observable rate and the informed weakly observable analysis, but the uninformed weakly observable setting can be strictly harder.

  • Strongly observable: For time-varying strongly observable graphs, the upper bound adapts by replacing α with the sum of the per-round independence numbers α_t.The algorithm uses time-dependent graph neighborhoods.
  • Weakly observable, informed: In the informed weakly observable model, the exploration set changes each round to the smallest weakly dominating set D_t of the revealed graph.The corresponding complexity term is the sum of δ_t=|D_t|.
  • Weakly observable, uninformed: In the uninformed weakly observable model, the regret rate can strictly increase when graphs vary across rounds.The constant-graph rate depends on δ, whereas the uninformed time-varying upper bound uses exploration over all K actions.
  • Weakly observable, uninformed: The uninformed upper bound is eO(K^1/3 T^2/3), and a matching construction has δ(G_t)=α(G_t)=1 on every round.Each graph is formed by removing most incoming edges and one self-loop from a complete graph.

A.1 Proof of Lemma 4

The proof of Lemma 4 extends the standard exponential-weights analysis to a second-order bound that treats low-loss actions more favorably. This bound is later used with estimated losses in the Exp3.G analysis.

  • Lemma 4 proof: The proof reduces the general loss sequence to shifted losses and combines the resulting inequalities to establish the lemma.The shift preserves the Hedge execution while enabling the required lower-bound condition.
  • Lemma 4 proof: Lemma 10 assumes loss functions bounded below by −1/η and gives a second-order regret bound for the probability vectors q_t.The proof follows exponential weighting using inequalities for the exponential and logarithm.
  • Lemma 4 proof: Lemma 4 applies the bound when losses are nonnegative and a subset S_t has losses at most 1/η.This produces improved dependence on actions in S_t through factors involving 1−q_t(i).

A.2 Proof of Lemma 5

The proof discretizes node weights, expands each original node into a clique, and applies a graph lemma to derive the desired bound in terms of the independence number.

  • Discretization: The proof discretizes each weight w_i using M = ⌈2K/ε⌉ and integer representatives m_i.Because every w_i ≥ ε, each representative satisfies m_i ≥ M w_i ≥ 2K.
  • Graph construction: The construction replaces node i with a clique C_i of m_i vertices and preserves inter-node edges between the corresponding cliques.Every vertex of C_i connects to every vertex of C_j exactly when (i, j) is present in G.
  • Reduction: The transformed graph converts the target expression into a sum involving 1 + d_i, where d_i is the in-degree of a vertex in the expanded graph.This enables application of the cited graph lemma to the expanded graph G′.
  • Conclusion: Applying Lemma 13 of Alon et al. to G′ yields the desired inequality, completing the proof.The conclusion is stated after the graph expansion and lemma application.

B Proofs of Lower Bounds

The lower-bound proofs establish that non-observable graphs force linear regret by hiding one action’s loss from the player throughout the game.

  • Theorem 6: Theorem 6 states that every non-observable graph with at least two nodes admits losses causing expected regret at least 1.The theorem applies to any player algorithm and any such graph.
  • Construction: Non-observability provides a node with no incoming edges, so the proof randomizes its loss while leaving the player unable to observe it.The construction draws χ uniformly from {0, 1} and assigns losses accordingly.
  • Information limitation: The number of times the player chooses the hidden action is independent of χ because the player never observes that action’s loss.This independence is the key information limitation used in the regret calculation.
  • Lower-bound conclusion: Averaging over the randomized loss functions implies that some fixed loss sequence produces regret at least 1.The randomized construction therefore yields a deterministic sequence witnessing the lower bound.

B.2 Weakly observable Feedback Graphs

For weakly observable graphs, the lower-bound proof combines a combinatorial independent-set construction with randomized losses and information bounds to obtain the stated regret rate.

  • Main lower bound: Theorem 7 states that weakly observable graphs with weak domination number δ induce losses causing expected regret at least 1.The result applies to every randomized player algorithm and every horizon T.
  • Combinatorial lemma: A combinatorial lemma extracts an independent set U from the weakly observable portion, with size at least 1/50(k/ln n).Each vertex then dominates at most ln n vertices of U.
  • Combinatorial reduction: Applying the lemma with domination number δ yields an independent set U of m ≥ δ/(50 ln K) weakly observable vertices.The proof first assumes δ ≥ 100 ln K so that m ≥ 2.
  • Randomized losses: The construction labels U as good actions and V \ U as bad actions, with ε = m^1/3(32T ln K)^−1/3.Observing a good action requires selecting a bad action because U is independent and its vertices lack self-loops.
  • Information analysis: The proof controls information about the hidden optimal action using conditional distributions, total variation, and KL-divergence bounds tied to observations of bad actions.The observed variables generate the σ-algebra used to compare the relevant distributions.
  • Regret calculation: The resulting regret lower bound follows by balancing the cost of selecting bad actions against the information needed to identify the good action.The proof derives the bound through the relation between ε, T, and the number of informative selections.
  • Small-δ case: A separate construction handles δ < 100 ln K, using a graph with at least three vertices and two nearly optimal actions.The proof chooses ε = 1/2T^−1/3 and uses Bernoulli losses to complete the theorem for small δ.

B.3 Separation Between the Informed and Uninformed Models

The separation result shows that time-varying weakly observable graphs can make the uninformed model harder, even when every graph has independence and domination numbers equal to 1.

  • Separation result: Theorem 9 constructs weakly observable graphs with δ(G_t) = α(G_t) = 1 that force expected regret at least 1 in the uninformed model.The construction applies to any randomized player strategy over K ≥ 4 actions.
  • Lower-bound strategy: The proof targets a lower bound of Ω(K^1/3T^2/3) using randomized graphs and losses.It analyzes deterministic algorithms without loss of generality.
  • Graph construction: Each round removes all edges incoming to node 1 except the edge from a uniformly random node J_t.Thus the graph’s feedback structure changes randomly across rounds.
  • Uninformed feedback: Because the graph is unknown when the action is selected, the player cannot reliably choose the unique node that reveals node 1’s loss.The analysis bounds the probability of matching the revealing node and the resulting number of informative selections.
  • Regret consequence: The resulting information scarcity yields the claimed regret lower bound after the same style of analysis used for weakly observable graphs.The proof proceeds under a bound on the number of selections from V′ and then concludes the regret estimate.

C Tight Bounds for the Loopless Clique

The section restates a regret theorem for Algorithm 1 on the loopless clique feedback graph and proves it using strong observability and a uniform exploration distribution.

  • Theorem 3: Theorem 3 bounds Algorithm 1's expected regret for any sequence of loss functions on the loopless clique feedback graph.The theorem uses parameters η and γ, though the supplied statement is truncated before the complete bound.
  • Proof: Strong observability makes the exploration distribution u uniform over the vertex set V.
  • Proof: For every vertex i, the clique structure gives P_t(i)=1−p_t(i), and the algorithm's mixture ensures P_t(i)≥η.
  • Proof: The proof applies Lemma 4 to the estimated loss vectors with S_t=V and then takes expectations.
  • Proof: Combining the resulting inequalities with Eq. (5) completes the theorem proof.The final supplied proof text states that the theorem follows after the combination step.

D Connections to Partial Monitoring

The paper connects feedback-graph learning to partial monitoring by encoding graph feedback as loss and feedback matrices. This encoding preserves observability classes and transfers minimax-regret characterizations between the settings.

  • Partial monitoring setup: Partial monitoring uses a loss matrix L and feedback matrix H over finite action and environment-action sets.The environment fixes hidden matrix columns, while the player incurs loss after choosing an action.
  • Encoding feedback graphs: The reduction creates one partial-monitoring environment action for each binary loss assignment, yielding M=2^K columns and loss columns equal to {0,1}^K.
  • Encoding feedback graphs: The feedback matrix H encodes the graph through symbols that distinguish environment columns according to the feedback observed after each action.The encoding is specified through the condition associated with Eq. (12).
  • Reduction: The construction is a bona fide reduction: a partial-monitoring algorithm can be converted into an algorithm for graph feedback with binary losses.The converted algorithm precomputes the mapping from graph feedback to partial-monitoring symbols and feeds those symbols to the original algorithm.
  • Observability: The induced partial-monitoring instance represents feedback through canonical matrices S_i, whose rows correspond to distinct symbols observed for action i.
  • Scope: The reduction's lower-bound connection applies under a weaker environment model than standard adaptive partial monitoring, because the cited lower bounds remain valid there.
  • Regret connection: Partial-monitoring characterizations give minimax-regret orders T for locally observable games and T^2/3 for globally observable games.The paper combines these rates with the preserved observability classes of the graph encoding.
  • Observability: The encoding preserves observability: weakly observable graphs map to globally observable games, while strongly observable graphs map to locally observable games.The proof uses row-space representations of loss vectors and pairwise loss differences.
Loading 1502.07617v1…