PAC model-free reinforcement learning

By Alexander L. Strehl, Lihong Li, Eric Wiewiora, J. Langford, Michael L. Littman. 2006

527 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Statistical 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 Statistical Learning Theory

Citations in the corpus

Learning Parameterized Skills (2012, methodology): “We compare our model-free approach to other exploration techniques, most importantly Delayed Q-Learning (DQL) [68] and ∆V [15], and show that ours is both based on a well-defined optimization problem and empirically efficient.”
Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, methodology): “Delayed Q-learning uses O ( |S||A| ) space and O (ln |A| ) arithmetic operations per iteration Strehl et al. (2006).”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, methodology): “MORMAX (Szita & Szepesvári, 2010) and delayed Q-learning (Strehl et al., 2006), in particular, come with sample complexity bounds that are linear in S, and match lower bounds.”
Informing sequential clinical decision-making through reinforcement learning: an empirical study (2010, background): “In the reinforcement learning literature, Bayesian approaches have also been explored for similar reasons (Dearden et al. 1999 ;S trens2000 ;W ang et al.2005; Engel et al. 2005); other methods targeting efficient exploration have also been explored (Kakade et al. 2003; Strehl et al. 2006; Brunskil”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “An algorithm is said to be PAC-MDP if it is guaranteed to have close to optimal performance with high probability after a number of time-steps that is polynomial in the quantities that describe the problem [18, 39, 23, 41, 98, 111, 99].”
PAC Bounds for Discounted MDPs (2012, methodology): “Note that Strehl et al. (2009) proved their theorem for a specific class of policies while Theorem 15 holds for all policies.”
Generalization and Exploration via Randomized Value Functions (2014, background): “There is a sizable literature on RL algorithms that are provably efficient in tabula rasa contexts (Brafman & Tennenholtz, 2002; Kakade, 2003; Kearns & Koller, 1999; Lattimore et al., 2013; Ortner & Ryabko, 2012; Osband et al., 2013; Strehl et al., 2006).”
Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning (2015, methodology): “[1] improves the state-dependency of these bounds for their delayed Q-learning algorithm to Õ ( |S||A|H(5) 4 ln 1 δ ) .”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “…rich body of theoretical literature on learning Markov Decision Processes (MDPs) with small state spaces [Kearns and Singh, 2002, Brafman and Tennenholtz, 2003, Strehl et al., 2006], with an emphasis on sophisticated exploration techniques that ﬁnd near-optimal policies in a sample-eﬃcient manner.”
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).”
DORA The Explorer: Directed Outreaching Reinforcement Action-Selection (2018, methodology): “Efﬁcient exploration in model-free RL was also analyzed in PAC-MDP framework, most notably the Delayed Q Learning algorithm by Strehl et al. (2006).”
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, 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].”
Provably Efficient Exploration in Policy Optimization (2019, background): “Broadly speaking, our work is related to a vast body of work on value-based reinforcement learning in tabular (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) and linear settings (Yang & Wang, 2019b;a; Jin”
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).”
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction (2020, background): “In addition, [2, 14, 22, 37, 40, 45] studied modified Q-learning algorithms that might potentially improve sample complexities and accelerate convergence.”
Model-based reinforcement learning with nearly tight exploration complexity bounds (2010, methodology): “3 The only model-free method with known complexity bounds is for delayed Q-learning (Strehl et al., 2006), which requires at most O N KV 4 max 4 (1−γ) 4 exploratory actions.”