Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning

By Christoph Dann, Tor Lattimore, Emma Brunskill. 2017

329 citations recorded by the source corpus.

Statistical performance bounds for reinforcement learning (RL) algorithms can be critical for high-stakes applications like healthcare. This paper introduces a new framework for theoretically measuring the performance of such algorithms called Uniform-PAC, which is a strengthening of the classical Probably Approximately Correct (PAC) framework. In contrast to the PAC framework, the uniform version may be used to derive high probability regret guarantees and so forms a bridge between the two setups that has been missing in the literature. We demonstrate the benefits of the new framework for finite-state episodic MDPs with a new algorithm that is Uniform-PAC and simultaneously achieves optimal regret and PAC guarantees except for a factor of the horizon.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research, Reinforcement Learning

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 Electrical and Electronic Engineering

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “…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 exploitation (Zhang and…”
Neural Approaches to Conversational AI (2018, neutral): “While exploration in finite-state RL is relatively well-understood (Strehl et al., 2009; Jaksch et al., 2010; Osband and Roy, 2017; Dann et al., 2017), exploration when parametric models like neural networks are used is an active research topic (Bellemare et al.”
Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, background): “Another line of work of model-based reinforcement learning is to learn a dynamic model in a hidden representation space, which is especially necessary for pixel state spaces (Kakade et al., 2018; Dann et al., 2017; Szita & Szepesvári, 2010; Kearns & Singh, 2002; Jaksch et al., 2010).”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “ebonusisatleast 1= p n (s;a ). Thisisnecessarytoachieve a Bayesian expected regret bound of O ( p T ), which these other works do not achieve, instead suffering from linear expected regret. Indeed in [24] it was shown that in order to achieve a sublinear expected regret bound every state must be vis”
A Study on Overfitting in Deep Reinforcement Learning (2018, background): “Algorithms and regret analysis for stochastic (Auer et al., 2002) and adversarial bandits (Auer, 2000; Bubeck & Cesa-Bianchi, 2012), for contextual bandits (Agarwal et al., 2014), contextual decision processes (Jiang et al., 2017) and RL (Jaksch et al., 2010; Azar et al., 2017), as well as Probably ”
Minimax Regret Bounds for Reinforcement Learning (2017, background): “Almost all reinforcement learning algorithms with polynomial bounds on sample complexity employ optimism to guide exploration (Kearns & Singh, 2002; Brafman & Tennenholtz, 2002; Strehl et al., 2006; Dann et al., 2017).”
On Oracle-Efficient PAC RL with Rich Observations (2018, background): “While such problems are central to empirical RL research [2], most theoretical results on strategic exploration focus on tabular MDPs with small state spaces [3–10].”
Recent advances in reinforcement learning in finance (2021, methodology): “17) since V (n)(s) = supa∈AQ(s, a) and (1)Sample complexity with respect to the number of episodes has also been adopted in the literature [60, 61].”
Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs (2018, unknown): “We ﬁnally mention that some studies consider regret minimization in MDPs in the episodic setting, where the length of each episode is ﬁxed and known; see, e.g., (Osband et al., 2013), (Gheshlaghi Azar et al., 2017), and (Dann et al., 2017).”
Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (2019, methodology): “Please see (Dann et al., 2017) for a detailed explanation of how to proceed with the algorithm design and analysis is this case(5).”
Near-Optimal Reinforcement Learning with Self-Play (2020, background): “Single-agent RL There is a rich literature on reinforcement learning in MDPs [see e.g. 12, 24, 1, 7, 32, 14].”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, background): “Under Assumption 3.1, a line of work has attempted to provide tight sample complexity bounds [Azar et al., 2017, Dann and Brunskill, 2015, Dann et al., 2017, 2019, Jin et al., 2018, Osband and Van Roy, 2017].”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “…on the tabular setting; see e.g., Strehl et al. (2006); Jaksch et al. (2010); Osband et al. (2014); Osband and Van Roy (2016); Azar et al. (2017); Dann et al. (2017); Agrawal and Jia (2017); Jin et al. (2018); Russo (2019); Rosenberg and Mansour (2019a,b); Jin and Luo (2019); Zanette and…”
Provably Efficient Exploration in Policy Optimization (2019, methodology): “…adopted by the existing work on value-based reinforcement learning (Jaksch et al., 2010; Osband et al., 2014; Osband & Van Roy, 2016; Azar et al., 2017; Dann et al., 2017; Strehl et al., 2006; Jin et al., 2018; 2019; Yang & Wang, 2019b;a), where the reward function is fixed across all the episodes.”
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (2020, background): “Learning adversarial MDPs with changing dynamics is computationally hard even under full-information feedback (Yadkori et al., 2013).”
Model-Based Reinforcement Learning with Value-Targeted Regression (2020, methodology): “…MDP with S states and A actions, there have been results on model-based methods (e.g., Jaksch et al. 2010; Osband et al. 2014; Azar et al. 2017; Dann et al. 2017; Agrawal & Jia 2017; Dann et al. 2018; Kakade et al. 2018), and on modelfree methods (e.g., Osband et al. 2017; Jin et al. 2018;…”
Reward-Free Exploration for Reinforcement Learning (2020, background): “Lemma C.1 (Lemma E.15 in Dann et al. [2017]) .”
Strategic Object Oriented Reinforcement Learning (2018, background): “y expensive. Indeed, while there is a considerable amount of theoretical work done on tabular modelbased reinforcement learning that suggests model-based approaches can be provably sample efﬁ- cient (Dann et al., 2017; Brafman & Tennenholtz, 2002; Strehl & Littman, 2008), there is much less ”