# Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited

arXiv: https://arxiv.org/abs/2010.03531 · HTML: https://mlsanity.com/paper/2010.03531/

## Key facts

- Cited by 106 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2020.

## Built on by (most cited first, 30 of 106)

- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [UFT: Unifying Supervised and Reinforcement Fine-Tuning](https://mlsanity.com/paper/2505.16984/) (2025)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Fast Rates for Maximum Entropy Exploration](https://mlsanity.com/paper/2303.08059/) (2023)
- [A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2209.15634/) (2022)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses](https://mlsanity.com/paper/2205.07704/) (2022)
- [Towards Theoretical Understanding of Inverse Reinforcement Learning](https://mlsanity.com/paper/2304.12966/) (2023)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection](https://mlsanity.com/paper/2110.14798/) (2021)
- [Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs](https://mlsanity.com/paper/2203.09251/) (2022)
- [Optimistic PAC Reinforcement Learning: the Instance-Dependent View](https://mlsanity.com/paper/2207.05852/) (2022)
- [Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds](https://mlsanity.com/paper/2210.14051/) (2022)
- [Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning](https://mlsanity.com/paper/2305.10282/) (2023)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)
- [Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalents](https://mlsanity.com/paper/2301.12601/) (2023)
- [Lower Bounds for Learning in Revealing POMDPs](https://mlsanity.com/paper/2302.01333/) (2023)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)

## Abstract (arXiv)

In this paper, we propose new problem-independent lower bounds on the sample complexity and regret in episodic MDPs, with a particular focus on the non-stationary case in which the transition kernel is allowed to change in each stage of the episode. Our main contribution is a novel lower bound of Omega((H3SA/ε2)log(1/δ)) on the sample complexity of an (varepsilon,δ)-PAC algorithm for best policy identification in a non-stationary MDP. This lower bound relies on a construction of "hard MDPs" which is different from the ones previously used in the literature. Using this same class of MDPs, we also provide a rigorous proof of the Omega(√H3SAT) regret bound for non-stationary MDPs. Finally, we discuss connections to PAC-MDP lower bounds.