Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs

Abstract

We develop a new approach to obtaining high probability regret bounds for online learning with bandit feedback against an adaptive adversary. While existing approaches all require carefully constructing optimistic and biased loss estimators, our approach uses standard unbiased estimators and relies on a simple increasing learning rate schedule, together with the help of logarithmically homogeneous self-concordant barriers and a strengthened Freedman's inequality. Besides its simplicity, our approach enjoys several advantages. First, the obtained high-probability regret bounds are data-dependent and could be much smaller than the worst-case bounds, which resolves an open problem asked by Neu (2015). Second, resolving another open problem of Bartlett et al. (2008) and Abernethy and Rakhlin (2009), our approach leads to the first general and efficient algorithm with a high-probability regret bound for adversarial linear bandits, while previous methods are either inefficient or only applicable to specific action sets. Finally, our approach can also be applied to learning adversarial Markov Decision Processes and provides the first algorithm with a high-probability small-loss bound for this problem.

References in corpus (11)

• The on-line shortest path problem under partial monitoring
• Online Learning with Predictable Sequences
• More Adaptive Algorithms for Adversarial Bandits
• Online Convex Optimization in Adversarial Markov Decision Processes
• Learning in Games: Robustness of Fast Convergence
• Minimax Policies for Combinatorial Prediction Games
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• Efficient Online Portfolio with Logarithmic Regret
• Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits
• Online Learning via the Differential Privacy Lens
• An efficient high-probability algorithm for Linear Bandits

Cited by in corpus (10)

• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Robust Policy Gradient against Strong Data Corruption
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Minimax Regret for Stochastic Shortest Path
• Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• Corralling Stochastic Bandit Algorithms
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses