Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning

By Christoph Dann, Emma Brunskill. 2015

266 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

In Scaling & Learning Theory

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Over the years, several works have addressed RL in terms of both the optimal sample complexity for finding the best policy (Azar et al., 2013; Dann and Brunskill, 2015; Dann et al., 2017; Domingues et al., 2020a; Lattimore and Hutter, 2012) and minimizing regret via balancing exploration and…”
Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, methodology): “…learning, many methods have been developed and some of them are proved to achieve near-optimal performance guarantees in certain senses; recent examples including (Ortner and Auer, 2007; Dann and Brunskill, 2015; Lattimore et al., 2013; Lattimore and Hutter, 2012; Chen and Wang, 2016).”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, methodology): “…over a conﬁdence set, PSRL samples a single statistically plausible MDP and selects a policy that maximizes value for that MDP. Algorithm 1 OFU RL The literature on eﬃcient reinforcement learning oﬀers statistical eﬃciency guarantees for a number of OFU-based algorithms [16, 5, 15, 23, 26, 14, 8].”
Deep Exploration via Bootstrapped DQN (2016, methodology): “Similarly, even for this tiny problem size, the recent analysis that proves a near optimal sample complexity in ﬁxed horizon problems [4] only guarantees that we will have fewer than 10 10 = 1 suboptimal episodes.”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “We also ran comparisons against BOLT [4], UCFH [14], and UCRL2 [21] but they did not perform much better than the dithering approaches and contributed to the clutter in the ﬁgure so we do not show them.”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “The result is similar in spirit to other lower bounds for PAC-learning MDPs [Dann and Brunskill, 2015, Krishnamurthy et al., 2016], but we are not aware of any lower bound that applies directly to the setting.”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, methodology): “Our algorithm is conceptually similar to other algorithms based on the optimism principle such as MBIE [5], UCFH [3], UCRL2 [6] or UCRL-γ [2] but there are several key differences:”
Deep Exploration via Randomized Value Functions (2017, background): “Subsequent papers proposed and analyzed alternative tabular algorithms that carry out deep exploration with varying degrees of efficacy (Brafman and Tennenholtz, 2002; Auer and Ortner, 2006; Strehl et al., 2006; Jaksch et al., 2010; Osband et al., 2013; Dann and Brunskill, 2015; Azar et al., 2017).”
On Oracle-Efficient PAC RL with Rich Observations (2018, neutral): “[8] Christoph Dann and Emma Brunskill.”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, background): “Jiang and Agarwal [2018] conjectured a linear dependence on the horizon, which is consistent with all existing upper bounds, which scale at least linearly with the planning horizon [Dann and Brunskill, 2015, Azar et al., 2017, Zanette and Brunskill, 2019] (see Section 3 for further discussion).”
On the Optimality of Sparse Model-Based Planning for Markov Decision Processes (2019, background): “There exists a large body of literature on MDPs and RL (see e.g. Kakade et al. (2003); Strehl et al. (2009); Kalathil et al. (2014); Dann and Brunskill (2015) and reference therein).”
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, background): “There is also a line of works studying the sample complexity of obtaining a value or policy that is at most ǫ -suboptimal (Kakade, 2003; Strehl et al., 2006, 2009; Szita and Szepesv´ari, 2010; Lattimore and Hutter, 2014; Azar et al., 2013; Dann and Brunskill, 2015; Sidford et al., 2018).”
Reinforcement Learning with Trajectory Feedback (2020, result): “This result can also be found in other works such as [Dann and Brunskill, 2015].”
A Tour of Reinforcement Learning: The View from Continuous Control (2018, methodology): “This is our oracle model and is called episodic reinforcement learning (See, for example Chapter 3 of Sutton and Barto [76], Chapter 2 of Puterman [58], or Dann and Brunskill [24]).”
PAC Reinforcement Learning With an Imperfect Model (2018, background): “In particular, it might be possible to remove one 1/ term by carefully distinguishing important states from the unimportant ones (Dann and Brunskill 2015).”