Reinforcement Learning in Finite MDPs: PAC Analysis

By Alexander L. Strehl, Lihong Li, Michael L. Littman. 2009

339 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Control and Systems Engineering, 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 Control and Systems Engineering

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

Stochastic Primal-Dual Q-Learning (2018, positive): “Lastly, Theorem 1 suggests that the SPD Q-learning guarantees the convergence with a certain convergence rate even when the state-action distribution under a certain behavior policy is time-varying but sub-linearly converges to a stationary distribution as stated in Assumption 3.”
Bootstrapping with Models: Confidence Intervals for Off-Policy Evaluation (2016, positive): “Paduraru introduced tight model bias bounds for i.i.d. sampled transitions from general MDPs and i.i.d. trajectories from directed acyclic graph MDPs [12].”
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 ”
Agnostic System Identification for Model-Based Reinforcement Learning (2012, neutral): “This improves upon other state-of-the-art MBRL algorithms, such as R max , ˜ O ( ) (Strehl et al., 2009) and a recent modiﬁcation of R max , ˜ O ( Here, the dependency on | S | 2 | A | is due to the complexity of the class ( | S | 2 | A | parameters).”
On the Sample Complexity of Reinforcement Learning with a Generative Model (2012, methodology): “Therefore, we did not compare our results with the-state-of-the-art of PAC-MDP (Strehl et al., 2009; Szita & Szepesv´ari, 2010) and upper-conﬁdence bound based algorithms (Bartlett & Tewari, 2009; Jaksch et al., 2010), in which the choice of the exploration policy has an inﬂuence on the behavior of ”
Dynamic policy programming (2010, neutral): “, 2000), or upper-confidence bounds methods which address the exploration-exploitation dilemma (Jaksch et al., 2010; Szita and Szepesvári, 2010; Bartlett and Tewari, 2009; Strehl et al., 2009).”
Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning (2015, methodology): “EVI performs modiﬁed Bellman backups that are optimistic with respect to a given set of parameters.”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, methodology): “Note our PAC bound for UBEV is never worse than ˜ O ( S 2 AH 4 /ε 2 ) , which improves on the similar MBIE algorithm by a factor of H 2 (after adapting the discounted setting for which MBIE was analysed to our setting).”
Importance Sampling Policy Evaluation with an Estimated Behavior Policy (2018, background): “In these settings, an alternative to importance sampling policy evaluation is model-based policy evaluation [20, 16, 9].”
Environment-Independent Task Specifications via GLTL (2017, background): “The problems of learning and planning in such environments have been vigorously studied in the AI community for over 25 years (Watkins, 1989; Boutilier et al., 1999; Strehl et al., 2009).”
Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited (2020, methodology): “We note that unlike existing sample complexity lower bounds which also construct “bandit-like” hard instances (Strehl et al., 2009; Lattimore and Hutter, 2012; Dann and Brunskill, 2015), we do not refer to the bandit lower bound of Mannor and Tsitsiklis (2004), but instead use explicit change of dis”
State Abstractions for Lifelong Reinforcement Learning (2018, methodology): “In general, it us unknown whether state abstractions cooperate with PAC-MDP algorithms like Delayed-Q, an area we hope to clarify in future work.”
Lipschitz Continuity in Model-based Reinforcement Learning (2018, methodology): “The Simulation Lemma (Kearns & Singh, 2002; Strehl et al., 2009) is for discrete state MDPs and relates error in the one-step model to the value obtained by using it for planning.”
Sample Efficient Reinforcement Learning with Gaussian Processes (2014, methodology): “The proof is similar to the DQL analysis and shown in the Supplementary Material.”