More Adaptive Algorithms for Adversarial Bandits

Abstract

We develop a novel and generic algorithm for the adversarial multi-armed bandit problem (or more generally the combinatorial semi-bandit problem). When instantiated differently, our algorithm achieves various new data-dependent regret bounds improving previous work. Examples include: 1) a regret bound depending on the variance of only the best arm; 2) a regret bound depending on the first-order path-length of only the best arm; 3) a regret bound depending on the sum of first-order path-lengths of all arms as well as an important negative term, which together lead to faster convergence rates for some normal form games with partial feedback; 4) a regret bound that simultaneously implies small regret when the best arm has small loss and logarithmic regret when there exists an arm whose expected loss is always smaller than those of others by a fixed gap (e.g. the classic i.i.d. setting). In some cases, such as the last two results, our algorithm is completely parameter-free. The main idea of our algorithm is to apply the optimism and adaptivity techniques to the well-known Online Mirror Descent framework with a special log-barrier regularizer. The challenges are to come up with appropriate optimistic predictions and correction terms in this framework. Some of our results also crucially rely on using a sophisticated increasing learning rate schedule.

Cited by in corpus (34)

• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Exploration by Optimisation in Partial Monitoring
• Corruption-robust exploration in episodic reinforcement learning
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Path Length Bounds for Gradient Descent and Flow
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
• Regret-optimal control in dynamic environments
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Mirror Descent and the Information Ratio
• Near-Optimal No-Regret Learning in General Games
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications
• Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits
• Hedging in games: Faster convergence of external and swap regrets
• Prediction with Corrupted Expert Advice
• Corralling Stochastic Bandit Algorithms
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Scale Free Adversarial Multi Armed Bandits
• On Optimal Robustness to Adversarial Corruption in Online Decision Problems
• A Closer Look at Small-loss Bounds for Bandits with Graph Feedback
• Adaptive and Efficient Algorithms for Tracking the Best Expert
• Banker Online Mirror Descent
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs
• Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs
• Combinatorial Bandits under Strategic Manipulations
• Nonstochastic Bandits and Experts with Arm-Dependent Delays
• Logarithmic Regret from Sublinear Hints
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition
• Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers
• Online estimation and control with optimal pathlength regret
• Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays