Data to 7 Oct 2026

Minimax Regret Bounds for Reinforcement Learning

arXiv 1703.05449 ↗First posted 16 Mar 2017stat.ML cs.AI cs.LGcited by 500

Not on the map. Why?

Cited by 35 in Offline RL and imitation learning from data, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

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 tildeO( √HSAT + H2S2A+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 tildeO(HS √AT) achieved by the UCRL2 algorithm of Jaksch et al., 2010. The key significance of our new results is that when T≥ H3S3A and SA≥ H, it leads to a regret of tildeO(√HSAT) that matches the established lower bound of Omega(√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).

Key facts. Cited by 500 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Mar 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 2; 2021: 111; 2022: 92; 2023: 109; 2024: 76; 2025: 51; 2026: 59.

500 papers.

Sort:

By area:

2020Is Pessimism Provably Efficient for Offline RL?cited by 362
2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learningcited by 125
2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
2021Recent Advances in Reinforcement Learning in Financecited by 102
2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
2023Is RLHF More Difficult than Standard RL?cited by 96
2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
2022RORL: Robust Offline Reinforcement Learning via Conservative Smoothingcited by 83

38 more

2021Reward is enough for convex MDPscited by 82
2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 82
2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
2025Outcome-based Exploration for LLM Reasoningcited by 79
2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
2021A Survey of Exploration Methods in Reinforcement Learningcited by 68
2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
2021Reinforcement Learning, Bit by Bitcited by 59
2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
2021Tactical Optimism and Pessimism for Deep Reinforcement Learningcited by 55
2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
2021Learning to Map for Active Semantic Goal Navigationcited by 47
2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
2021MobILE: Model-Based Imitation Learning From Observation Alonecited by 44
2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 42
2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
2021Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 42
2022PAC Reinforcement Learning for Predictive State Representationscited by 42
2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41

50 most cited of 500 All 500 (JSON)