Online Learning with Feedback Graphs: Beyond Bandits
Exp3.G classifies feedback graphs: strongly observable gives ~√(αT), weakly observable ~δ^(1/3)T^(2/3), and unobservable Θ(T).
Key Findings
Methodology
The paper represents K actions as vertices of a directed graph: playing i reveals losses on its out-neighborhood. It defines observable, strongly observable, and weakly observable vertices using in-neighborhoods, then introduces independence number α and weak domination number δ. Exp3.G combines exploration mixing, importance-weighted unbiased loss estimates, and exponential updates. A refined second-order Hedge bound controls estimator variance.
Key Results
- Theorem 1 gives a complete trichotomy for T≥K^3: strongly observable graphs have minimax regret ~Θ(α^(1/2)T^(1/2)); weakly observable graphs have ~Θ(δ^(1/3)T^(2/3)); graphs with an unobservable vertex have Θ(T) regret.
- For strongly observable graphs, Exp3.G uses U=V, γ=min{(1/(αT))^(1/2),1/2}, and η=2γ, yielding O(√(αT)ln(KT)). For weakly observable graphs, exploration over a minimum weakly dominating set yields O((δlnK)^(1/3)T^(2/3)).
- The loopless clique has α=1 and achieves 5√(TlnK), matching full information up to constants. In contrast, removing one self-loop from a loopy star changes the rate from ~Θ(√(KT)) to ~Θ(T^(2/3)).
Significance
This work unifies expert advice, bandits, apple tasting, revealing actions, and asymmetric monitoring under one graph model. It shows that learnability depends not merely on how much feedback is observed, but on how information is routed through directed edges. Missing self-loops can cause a sharp transition from square-root regret to T^(2/3) or even linear regret. The framework also connects graph feedback to the classical easy, hard, and unlearnable classes of partial monitoring.
Technical Contribution
Exp3.G extends Exp3-SET to directed graphs with missing self-loops. Its estimator is ˆℓ_t(i)=ℓ_t(i)1{i observed}/P_t(i), where P_t(i)=∑_{j∈Nin(i)}p_t(j), making it unbiased. A new second-order Hedge inequality with (1−q_t(i)) factors handles strongly observable vertices without self-loops. Independence number controls strong-graph variance, weak domination controls exploration cost, and matching lower bounds establish parameter-tight rates up to logarithms.
Novelty
The central novelty is a graph-theoretic, parameter-sensitive characterization of learning when the player may not observe its own loss. Earlier work largely focused on self-aware feedback. This paper identifies weak observability as a distinct intermediate regime, introduces weak domination number δ, and proves that deleting only a few edges can change the temporal regret exponent from 1/2 to 2/3.
Limitations
- The main theorem assumes a fixed, known graph and adversarial losses in [0,1]. It does not directly provide a complete adaptive solution when the feedback structure must itself be learned.
- Logarithmic factors are hidden in minimax notation, and the weakly observable upper bound requires T≥K^3ln(K)/δ^2. Small-horizon, stochastic, delayed, and continuous-action settings are not fully covered.
- There are no real-world datasets or large-scale empirical benchmarks; the claims are established through graph examples, algorithmic analysis, and minimax lower bounds.
Future Work
Important directions include unknown or time-varying graphs, stochastic and noisy feedback, delayed observations, contextual actions, and continuous decision spaces. Algorithms could estimate α and δ online, reduce logarithmic overhead, and exploit benign rather than adversarial loss sequences. A broader extension from feedback graphs to general feedback matrices may combine the structural clarity of this work with the expressiveness of partial monitoring.
AI Executive Summary
Online learning is often presented through two extremes: full information, where every action’s loss is visible, and bandit feedback, where only the chosen action is observed. Real systems are less tidy. A decision may reveal neighboring options, fail to reveal its own outcome, or produce no feedback at all. Alon, Cesa-Bianchi, Dekel, and Koren model these situations with directed feedback graphs and ask how topology determines worst-case learnability.
Their answer is a sharp trichotomy. A graph is strongly observable when every action has a self-loop or is observed by all other actions; its minimax regret is ~Θ(√(αT)). If every action is observable but some require special exploration, the graph is weakly observable and regret becomes ~Θ(δ^(1/3)T^(2/3)). If any action has no incoming edge, learning is impossible in the adversarial sense, with Θ(T) regret. Here α is the independence number and δ the weak domination number.
The proposed Exp3.G algorithm mixes exploitation with graph-aware exploration, constructs unbiased importance-weighted loss estimates, and updates exponential weights. It achieves O(√(αT)ln(KT)) in the strong regime and O((δlnK)^(1/3)T^(2/3)) in the weak regime. The loopless clique remains as easy as full information, with regret at most 5√(TlnK); yet removing a single self-loop from a loopy star can trigger a jump from ~√(KT) to T^(2/3). The lesson is consequential: the route by which feedback travels can matter more than the amount of feedback itself.
Deep Analysis
Background
Full-information expert advice is handled by Hedge with Θ(√(TlnK)) regret, while Exp3 handles bandits with roughly ~Θ(√(KT)). Mannor and Shamir’s feedback-graph model contains both as special cases. Earlier graph analyses emphasized self-aware settings with self-loops. Apple tasting, revealing actions, and the loopless clique expose a harder question: what happens when the player is accountable for a loss but cannot observe it?
Core Problem
Given a fixed directed graph G, the learner chooses one of K actions per round and observes losses only on the chosen action’s out-neighborhood. Regret compares cumulative loss with the best fixed action in hindsight. The difficulty is that observation probability depends on the learner’s own distribution, while some actions’ losses are never directly seen. Exploration must therefore control estimator variance without sacrificing too much reward.
Innovation
- ��A complete strong/weak/unobservable trichotomy.
- ��Independence number α for strongly observable graphs and weak domination number δ for weakly observable graphs.
- ��Matching temporal rates √T, T^(2/3), and T.
- ��Exp3.G for directed graphs and missing self-loops.
- ��A refined second-order Hedge inequality.
- ��A sharp loopless-clique result and examples showing that deleting one or two edges can change the regret exponent.
Methodology
- ��Model: edge (i,j) means that playing i reveals ℓ_t(j); P_t(i)=∑_{j∈Nin(i)}p_t(j).
- ��Exploration: p_t=(1−γ)q_t+γu; use uniform u over V for strong graphs and over a minimum weakly dominating set D for weak graphs.
- ��Estimation: ˆℓ_t(i)=ℓ_t(i)1{i observed}/P_t(i), so E[ˆℓ_t(i)]=ℓ_t(i).
- ��Update: q_{t+1}(i)∝q_t(i)exp(−ηˆℓ_t(i)).
- ��Analysis: apply the second-order Hedge lemma and bound graph-dependent variance terms. Strong graphs use α; weak graphs use δ/γ.
- ��Lower bounds: an unobservable vertex yields T/4 regret; weak graphs use an independent hard subset to obtain Ω((δ/ln^2K)^(1/3)T^(2/3)).
Experiments
This is a theoretical minimax study rather than a dataset benchmark. The evaluated structures are full feedback, ordinary bandits, the loopless clique, apple tasting, revealing action, a clique with a missing self-loop and incoming edge, and loopy stars. The metric is expected regret and its dependence on T, K, α, and δ. Strong-graph parameters use η=2γ; weak-graph parameters use η=γ^2/δ. For the loopless clique, η=√(lnK)/(2T) and γ=2η. No external dataset or conventional ablation study is reported.
Results
Upper and lower bounds match up to logarithmic factors. Strongly observable graphs achieve O(√(αT)ln(KT)); weakly observable graphs achieve O((δlnK)^(1/3)T^(2/3)); unobservable graphs have a T/4 lower bound. The loopless clique admits 5√(TlnK), essentially full-information performance. A loopy star has α=K−1 and strong-graph regret ~√(KT), but removing one self-loop makes it weakly observable and changes the temporal rate to T^(2/3).
Applications
The framework applies to advertising, portfolio or expert selection, network routing, active monitoring, and asymmetric medical decisions. An engineer can encode actions as vertices and observable outcomes as directed edges, compute α and δ, and select graph-aware exploration. Practical deployment requires bounded losses, a reasonably stable feedback relation, and either a known graph or an added structure-learning layer.
Limitations & Outlook
The theory assumes finite actions, losses bounded in [0,1], and a known fixed graph. Adversarial minimax rates may be conservative for stochastic business environments, while the weak regime’s horizon requirement and hidden logarithmic terms can matter in practice. Future work should address unknown dynamic graphs, delayed or noisy feedback, contextual and continuous decisions, and computationally efficient estimation of graph parameters.
Plain Language Accessible to non-experts
Imagine a school where each student is a possible teammate. Every day you must choose one teammate, and the teacher gives you that student’s performance score—or perhaps the scores of several other students instead. The arrows in the paper say who can reveal whose score. Your goal is to keep choosing the student who turns out to be best over the whole semester, even though the teacher can arrange the scores adversarially.
Exp3.G is like a clever coach. It usually chooses students who currently look promising, but sometimes deliberately asks a student who can reveal information about many others. If every student can report their own score, or nearly everyone can report for them, the coach learns quickly. If some students can be checked only through a few special “messengers,” the coach must spend more days gathering information, so mistakes grow faster.
The worst case is a student whose score nobody can reveal. No strategy can reliably tell whether that student is excellent or terrible, so mistakes can grow almost one day at a time. The paper’s main message is that the school’s information network matters more than the raw number of scores the teacher provides. A small change to one arrow can transform an easy learning problem into a much harder one.
ELI14 Explained like you're 14
Picture a game with K mystery boxes. Each turn you pick one box and lose the number written inside it. Afterward, you may see the number in your box, the numbers in other boxes, or nothing at all. The numbers can change every turn, and you want to end up almost as well as if you had known the best box from the beginning.
The paper draws arrows between boxes. An arrow means: “If I pick this box, I get to peek at that box’s number.” Exp3.G is a strategy that learns from the peeks. It sometimes picks the box that looks best, but it also picks boxes that reveal useful information. That is like exploring new game levels instead of replaying the same safe move forever!
There are three situations. In the easy one, every box’s number can be discovered somehow, so the amount of regret grows roughly like √T. In the middle case, some boxes can be checked only by special messenger boxes, so regret grows like T^(2/3). In the impossible case, one box has no arrows coming into it. You can never learn its number, and regret can grow linearly with T.
Here is the surprising part: hiding your own box’s number does not always make the game harder. In the loopless clique, you can see every other box and still perform almost like full information. But removing just one important arrow from another graph can make learning much worse. Tiny rule changes can create huge difficulty changes—just like a video game level becoming impossible after one bridge disappears!
Glossary
Feedback graph
A directed graph whose vertices are actions and whose edges specify which losses become visible after an action is played. It is a structural model of partial information.
It is the central object used to define observability and design Exp3.G.
Strong observability
Every vertex has a self-loop or incoming edges from all other vertices. Thus each action’s loss has a robust observation route.
It yields ~Θ(√(αT)) minimax regret.
Weak observability
Every vertex is observable, but some vertices lack both a self-loop and universal incoming coverage. Learning them requires targeted exploration.
It yields ~Θ(δ^(1/3)T^(2/3)) regret.
Independence number α
The largest set of vertices with no directed edges between distinct members. It measures how many actions are mutually uninformative.
It controls strong-observability rates and variance bounds.
Weak domination number δ
The smallest number of actions whose out-neighborhoods cover every weakly observable vertex. It measures the size of an information-gathering exploration set.
It determines the weak-observability rate.
Exp3.G
An exponential-weights algorithm for directed feedback graphs. It mixes exploitation with exploration and corrects observed losses by their observation probabilities.
It provides the main upper bounds in the paper.
Open Questions Unanswered questions from this research
- 1 How can a learner estimate graph structure, α, and δ while simultaneously learning under an unknown changing graph? The paper points toward dynamic extensions but does not give an equally complete classification.
- 2 Do the three rates persist under stochastic, noisy, delayed, or strategically corrupted feedback? New probabilistic and robust estimation tools are needed.
- 3 Can logarithmic factors, horizon requirements, and worst-case assumptions be reduced without losing graph-specific guarantees?
Applications
Immediate Applications
Advertising and recommendation
Treat ads as actions and post-display signals as directed observations. Exp3.G can balance trying new ads with exploiting high-performing ones, provided feedback links are logged and losses are normalized.
Network monitoring and routing
Represent routes or probes as vertices and connect a probe to the links whose states it reveals. Graph-aware exploration can identify reliable routes without measuring every component on every round.
Long-term Vision
Information-aware system design
Future platforms could deliberately add feedback edges or self-reporting channels for critical decisions, converting T^(2/3)-type learning into √T-type learning. Privacy, cost, and changing connectivity remain major obstacles.
Abstract
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.