From Bandits to Experts: On the Value of Side-Observations

Abstract

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.

Presented at the NIPS 2011 conference

References in corpus (2)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Multi-Armed Bandits in Metric Spaces

Cited by in corpus (19)

• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
• Leveraging Side Observations in Stochastic Bandits
• Online Learning with Feedback Graphs: Beyond Bandits
• On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits
• 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
• Stochastic Online Learning with Probabilistic Graph Feedback
• Online learning with Erdős-Rényi side-observation graphs
• Reinforcement Learning with Feedback Graphs
• Regional Multi-Armed Bandits
• Online learning with graph-structured feedback against adaptive adversaries
• Best Arm Identification in Graphical Bilinear Bandits
• Strategic Arms with Side Communication Prevail Over Low-Regret MAB Algorithms
• Learning to Bid Without Knowing your Value
• Bandit based centralized matching in two-sided markets for peer to peer lending
• BLAG: Bandit On Large Action Set Graph