Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning

Abstract

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}|H^2}{{\epsilon }^2}\ln \frac{1}{\delta })$ and a lower PAC bound $\tilde{\Omega }(\frac{|\mathcal{S}||\mathcal{A}|H^2}{{\epsilon }^2}\ln \frac{1}{\delta +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 $H^3$.

28 pages, appeared in Neural Information Processing Systems (NIPS) 2015, updated version with fixed typos and modified Lemma 1 and Lemma C.5

References in corpus (2)

• Empirical Bernstein Bounds and Sample Variance Penalization
• On the Sample Complexity of Reinforcement Learning with a Generative Model

Cited by in corpus (45)

• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Fast active learning for pure exploration in reinforcement learning
• Naive Exploration is Optimal for Online LQR
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Corruption-robust exploration in episodic reinforcement learning
• $Q$-learning with Logarithmic Regret
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems
• Policy Certificates: Towards Accountable Reinforcement Learning
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions
• Heuristic-Guided Reinforcement Learning
• Variational Bayesian Reinforcement Learning with Regret Bounds
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• Adaptive Reward-Free Exploration
• Robust Policy Gradient against Strong Data Corruption
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• Online learning in MDPs with linear function approximation and bandit feedback
• Adaptive Discretization for Model-Based Reinforcement Learning
• Long-Term Visitation Value for Deep Exploration in Sparse Reward Reinforcement Learning
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
• Preference-based Reinforcement Learning with Finite-Time Guarantees
• When Simple Exploration is Sample Efficient: Identifying Sufficient Conditions for Random Exploration to Yield PAC RL Algorithms
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
• Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Reward Tweaking: Maximizing the Total Reward While Planning for Short Horizons
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Dueling RL: Reinforcement Learning with Trajectory Preferences
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Posterior sampling for reinforcement learning: worst-case regret bounds
• Task-Optimal Exploration in Linear Dynamical Systems
• Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
• Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulation
• Provably Efficient Multi-Task Reinforcement Learning with Model Transfer
• A Short Survey on Probabilistic Reinforcement Learning
• Reward is enough for convex MDPs
• Surveillance Evasion Through Bayesian Reinforcement Learning