mlsanityData to 7 Oct 2026

Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited

arXiv 2010.03531 ↗First posted 7 Oct 2020cs.LG stat.MLcited by 104

Not on the map. Why?

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.

Key facts. Cited by 104 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 20; 2022: 18; 2023: 23; 2024: 15; 2025: 12; 2026: 16.

104 papers.

Sort:

By area:

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  2. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  3. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  4. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  5. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  6. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  7. 2025UFT: Unifying Supervised and Reinforcement Fine-Tuningcited by 58
  8. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  9. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  10. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  11. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  12. 2023Fast Rates for Maximum Entropy Explorationcited by 32
38 more
  1. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  2. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  3. 2022Hindsight Learning for MDPs with Exogenous Inputscited by 25
  4. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  5. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  6. 2023Towards Theoretical Understanding of Inverse Reinforcement Learningcited by 21
  7. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
  8. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  9. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  10. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  11. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  12. 2022Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Boundscited by 16
  13. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
  14. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  15. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  16. 2023Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalentscited by 14
  17. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  18. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  19. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  20. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  21. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13
  22. 2023Learning to Make Adherence-Aware Advicecited by 13
  23. 2021Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimallycited by 12
  24. 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
  25. 2022Max-Min Off-Policy Actor-Critic Method Focusing on Worst-Case Robustness to Model Misspecificationcited by 11
  26. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  27. 2023Probabilistic Inference in Reinforcement Learning Done Rightcited by 11
  28. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  29. 2021A Reduction-Based Framework for Conservative Bandits and Reinforcement Learningcited by 9
  30. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  31. 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
  32. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  33. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  34. 2024Reinforcement Learning with Lookahead Informationcited by 8
  35. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  36. 2023Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measurescited by 7
  37. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  38. 2024Can we hop in general? A discussion of benchmark selection and design using the Hopper environmentcited by 7

50 most cited of 104 All 104 (JSON)