Efficient learning by implicit exploration in bandit problems with side observations

Abstract

We consider online learning problems under a partial observability model capturing situations where the information conveyed to the learner is between full information and bandit feedback. In the simplest variant, we assume that in addition to its own loss, the learner also gets to observe losses of some other actions. The revealed losses depend on the learner's action and a directed observation system chosen by the environment. For this setting, we propose the first algorithm that enjoys near-optimal regret guarantees without having to know the observation system before selecting its actions. Along similar lines, we also define a new partial information setting that models online combinatorial optimization problems where the feedback received by the learner is between semi-bandit and full feedback. As the predictions of our first algorithm cannot be always computed efficiently in this setting, we propose another algorithm with similar properties and with the benefit of always being computationally efficient, at the price of a slightly more complicated tuning mechanism. Both algorithms rely on a novel exploration strategy called implicit exploration, which is shown to be more efficient both computationally and information-theoretically than previously studied exploration strategies for the problem.

Published at Neural Information Processing Systems (NeurIPS) 2014

References in corpus (1)

• From Bandits to Experts: A Tale of Domination and Independence

Cited by in corpus (28)

• Causal Bandits: Learning Good Interventions via Causal Inference
• Delay and Cooperation in Nonstochastic Bandits
• Online Learning with Feedback Graphs: Beyond Bandits
• Secure Mobile Edge Computing in IoT via Collaborative Online Learning
• Online learning with noisy side observations
• Online Learning with Feedback Graphs Without the Graphs
• Fighting Bandits with a New Kind of Smoothness
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• Revealing graph bandits for maximizing local influence
• Optimal No-regret Learning in Repeated First-price Auctions
• First-order regret bounds for combinatorial semi-bandits
• Online Learning with Gaussian Payoffs and Side Observations
• Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall
• Online learning with Erdős-Rényi side-observation graphs
• Understanding Bandits with Graph Feedback
• Improper Reinforcement Learning with Gradient-based Policy Optimization
• Stochastic Online Learning with Probabilistic Graph Feedback
• Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits
• Bandits with Feedback Graphs and Switching Costs
• Bandit algorithms for real-time data capture on large social medias
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
• Regret Minimization in Stochastic Contextual Dueling Bandits
• Adversarial Dueling Bandits
• Path Planning Problems with Side Observations-When Colonels Play Hide-and-Seek
• Experts with Lower-Bounded Loss Feedback: A Unifying Framework
• Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
• Online Learning with Uncertain Feedback Graphs
• Dueling Bandits with Adversarial Sleeping