Online Learning with Feedback Graphs: Beyond Bandits

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 $\tilde{\Theta }({\alpha }^{1/2}{T}^{1/2})$ minimax regret, where $\alpha$ is the independence number of the underlying graph; the second class induces problems with $\tilde{\Theta }({\delta }^{1/3}{T}^{2/3})$ minimax regret, where $\delta$ 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.

References in corpus (2)

• Efficient learning by implicit exploration in bandit problems with side observations
• From Bandits to Experts: On the Value of Side-Observations

Cited by in corpus (16)

• Online Learning with Feedback Graphs Without the Graphs
• r-Extreme Signalling for Congestion Control
• Online Learning with Gaussian Payoffs and Side Observations
• Analysis of Thompson Sampling for Graphical Bandits Without the Graphs
• Bandits with Side Observations: Bounded vs. Logarithmic Regret
• Online learning with Erdős-Rényi side-observation graphs
• Stochastic Online Learning with Probabilistic Graph Feedback
• Minimax Optimal Online Stochastic Learning for Sequences of Convex Functions under Sub-Gradient Observation Failures
• Online learning with graph-structured feedback against adaptive adversaries
• Regret Minimization in Stochastic Contextual Dueling Bandits
• Semi-bandit Optimization in the Dispersed Setting
• Compliance-Aware Bandits
• Bayesian optimization for modular black-box systems with switching costs
• Thompson Sampling for Unimodal Bandits
• Best-of-Both-Worlds Algorithms for Partial Monitoring
• Online Learning with Randomized Feedback Graphs for Optimal PUE Attacks in Cognitive Radio Networks