mlsanityData to 14 Oct 2026

Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning

arXiv 1510.08906 ↗First posted 29 Oct 2015stat.ML cs.AI cs.LGcited by 106

Not on the map. Why?

Cited by 25 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Recently, there has been significant progress in understanding reinforcement learning in discounted infinite-horizon Markov decision processes (MDPs) by deriving tight sample complexity bounds. However, in many real-world applications, an interactive learning agent operates for a fixed or bounded period of time, for example tutoring students for exams or handling customer service requests. Such scenarios can often be better treated as episodic fixed-horizon MDPs, for which only looser bounds on the sample complexity exist. A natural notion of sample complexity in this setting is the number of episodes required to guarantee a certain performance with high probability (PAC guarantee). In this paper, we derive an upper PAC bound tilde O(frac|mathcal S|2 |mathcal A| H2ε2 lnfrac 1 δ) and a lower PAC bound tilde Omega(frac|mathcal S| |mathcal A| H2ε2 ln frac 1 δ + c) that match up to log-terms and an additional linear dependency on the number of states |mathcal S|. The lower bound is the first of its kind for this setting. Our upper bound leverages Bernstein's inequality to improve on previous bounds for episodic finite-horizon MDPs which have a time-horizon dependency of at least H3.

Key facts. Cited by 106 papers in the map (data through 14 Oct 2026). First posted on arXiv 29 Oct 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 36; 2022: 22; 2023: 16; 2024: 14; 2025: 10; 2026: 7.

106 papers.

Sort:

By area:

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  2. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  3. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  4. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 106
  5. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  6. 2021Reward is enough for convex MDPscited by 84
  7. 2019Provably Efficient Imitation Learning from Observation Alonecited by 78
  8. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  9. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  10. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  11. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  12. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
38 more
  1. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  2. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  3. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  4. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  5. 2021Heuristic-Guided Reinforcement Learningcited by 42
  6. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  7. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  8. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 35
  9. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  10. 2021Geometric Entropic Explorationcited by 32
  11. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  12. 2023On the Importance of Exploration for Generalization in Reinforcement Learningcited by 31
  13. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  14. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  15. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  16. 2021Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environmentscited by 26
  17. 2021Principled Exploration via Optimistic Bootstrapping and Backward Inductioncited by 26
  18. 2022Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Pathcited by 22
  19. 2021Dynamic Bottleneck for Robust Self-Supervised Explorationcited by 21
  20. 2023Towards Theoretical Understanding of Inverse Reinforcement Learningcited by 21
  21. 2023Replicable Reinforcement Learningcited by 21
  22. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  23. 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
  24. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  25. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 18
  26. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 18
  27. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 18
  28. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  29. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  30. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 17
  31. 2025Toward Efficient Exploration by Large Language Model Agentscited by 17
  32. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  33. 2021Provably Efficient Multi-Task Reinforcement Learning with Model Transfercited by 16
  34. 2021Task-Optimal Exploration in Linear Dynamical Systemscited by 15
  35. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 15
  36. 2021Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learningcited by 15
  37. 2022Latent Variable Representation for Reinforcement Learningcited by 15
  38. 2021No-Regret Reinforcement Learning with Heavy-Tailed Rewardscited by 14

50 most cited of 106 All 106 (JSON)