# Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning

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

## Key facts

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

## 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)
- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Provably Efficient Imitation Learning from Observation Alone](https://mlsanity.com/paper/1905.10948/) (2019)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Making Linear MDPs Practical via Contrastive Representation Learning](https://mlsanity.com/paper/2207.07150/) (2022)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Heuristic-Guided Reinforcement Learning](https://mlsanity.com/paper/2106.02757/) (2021)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost](https://mlsanity.com/paper/2101.00494/) (2021)
- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Geometric Entropic Exploration](https://mlsanity.com/paper/2101.02055/) (2021)
- [A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2209.15634/) (2022)
- [On the Importance of Exploration for Generalization in Reinforcement Learning](https://mlsanity.com/paper/2306.05483/) (2023)
- [Robust Policy Gradient against Strong Data Corruption](https://mlsanity.com/paper/2102.05800/) (2021)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments](https://mlsanity.com/paper/2102.08492/) (2021)
- [Principled Exploration via Optimistic Bootstrapping and Backward Induction](https://mlsanity.com/paper/2105.06022/) (2021)
- [Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Path](https://mlsanity.com/paper/2206.02678/) (2022)

## 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.