Minimax Regret Bounds for Reinforcement Learning

2017/03/16 by Mohammad Gheshlaghi Azar, Azar, Mohammad Gheshlaghi, Ian Osband +3 · 35 citations
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Reinforcement Learning in Robotics #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.1703.05449

Abstract

We consider the problem of provably optimal exploration in reinforcement learning for finite horizon MDPs. We show that an optimistic modification to value iteration achieves a regret bound of O( √(HSAT) + H²S²A+H√(T)) where H is the time horizon, S the number of states, A the number of actions and T the number of time-steps. This result improves over the best previous known bound O(HS √(AT)) achieved by the UCRL2 algorithm of Jaksch et al., 2010. The key significance of our new results is that when T≥ H³S³A and SA≥ H, it leads to a regret of O(√(HSAT)) that matches the established lower bound of Ω(√(HSAT)) up to a logarithmic factor. Our analysis contains two key insights. We use careful application of concentration inequalities to the optimal value function as a whole, rather than to the transitions probabilities (to improve scaling in S), and we define Bernstein-based "exploration bonuses" that use the empirical variance of the estimated values at the next states (to improve scaling in H).

Cited by

• Online Robust Reinforcement Learning with General Function Approximation
• Spectral Representation-based Reinforcement Learning
• Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes
• Tail Distribution of Regret in Optimistic Reinforcement Learning
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Tensor-Efficient High-Dimensional Q-learning
• Noisy Networks for Exploration
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• RL for Latent MDPs: Regret Guarantees and a Lower Bound
• Model-Based Reinforcement Learning with a Generative Model is Minimax\n Optimal
• Preference-based Reinforcement Learning with Finite-Time Guarantees
• Active Reinforcement Learning with Monte-Carlo Tree Search
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Greedy Sampling Is Provably Efficient for RLHF
• Count Counts: Motivating Exploration in LLM Reasoning with Count-based Intrinsic Rewards
• No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes
• Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approach
• Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach
• Learning When Not to Learn: Risk-Sensitive Abstention in Bandits with Unbounded Rewards
• Q-Learning with Fine-Grained Gap-Dependent Regret
• Risk level dependent Minimax Quantile lower bounds for Interactive Statistical Decision Making
• Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning
• Polychromic Objectives for Reinforcement Learning
• Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
• Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints
• Online Learning for Optimizing AoI-Energy Tradeoff under Unknown Channel Statistics
• Towards Provable Emergence of In-Context Reinforcement Learning
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Outcome-based Exploration for LLM Reasoning
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• What Fundamental Structure in Reward Functions Enables Efficient Sparse-Reward Learning?
• Online Learning of Optimal Sequential Testing Policies
• ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning
• Learning to Control in Metric Space with Optimal Regret

Related

• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Exploration in Structured Reinforcement Learning
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
• Near-optimal Reinforcement Learning in Factored MDPs