On the sample complexity of reinforcement learning.

By Sham M. Kakade. 2003

755 citations recorded by the source corpus.

Subfields: 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 Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

Reinforcement Learning in Healthcare: A Survey (2019, methodology): “RL methods are usually able to learn an accurate model quickly and then use this model to plan multi-step actions. Therefore, MRL methods normally have better sample efﬁciency than model-free methods [28]. c) Task-level: A higher task-level of efﬁcient approaches focuses on the development of method”
Reinforcement learning in robotics: A survey (2013, background): “…principle, reinforcement learning algorithms for MDPs with performance guarantees are known (Brafman and Tennenholtz, 2002; Kearns and Singh, 2002; Kakade, 2003) with polynomial scaling in the size of the state and action spaces, an additive error term, as well as in the horizon length (or a…”
Continual Learning of Control Primitives: Skill Discovery via Reset-Games (2020, background): “Second, complex and temporally extended behaviors can be exceedingly hard to learn with naïve exploration [25, 24].”
Trajectory-wise Control Variates for Variance Reduction in Policy Gradient Methods (2019, background): “The high variance of G is due to the exploration difficulty in RL: in the worst-case, the variance of G can grow exponentially in the problem’s horizon [29, 30], as it becomes harder for the policy to visit meaningful states and get useful update information.”
Learning When-to-Treat Policies (2019, background): “Then, a result from Kakade (2003, Chapter 5) and Murphy (2005) yields the following.”
The Uncertainty Bellman Equation and Exploration (2017, background): “These algorithms will eventually explore every reachable state and action infinitely often, but can take exponentially long to learn the optimal policy (Kakade, 2003).”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, background): “These provably eﬃcient algorithms (see, e.g., [16, 5, 15, 23, 26, 14, 8]) predominantly address the exploration-exploitation trade-oﬀ via optimism in the face of uncertainty (OFU): when at a state, the agent assigns to each action an optimistically biased while statistically plausible estimate of…”
Deep Exploration via Bootstrapped DQN (2016, background): “Unlike bandit problems, which balance actions which are immediately rewarding or immediately informative, RL settings require planning over several time steps [10].”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “We first provide argument (1), which reuses the construction by Krishnamurthy et al. (2016). Let each instance of M be a complete tree with branching factor |A| and depth H = ⌊1/(1 − γ)⌋.”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “lgorithm 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 theproblem[18,39,23,41,98,111,99]. However,thesestrategiesgenerallysufferfrom linear regret,since many PAC-MDP”
Reinforcement Learning from Imperfect Demonstrations (2018, background): “However, RL algorithms usually require a large amount of interactions with an environment to reach good performance (Kakade et al., 2003); initial performance may Proceedings of the 35 th International Conference on Machine Learning , Stockholm, Sweden, PMLR 80, 2018.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “The interested reader is addressed to [108, 157, 158].”
PAC Bounds for Discounted MDPs (2012, methodology): “Many previous algorithms have been shown to be PAC with varying bounds (Kakade, 2003; Strehl and Littman, 2005; Strehl et al., 2006, 2009; Szita and Szepesvári, 2010; Auer, 2011).”
(More) Efficient Reinforcement Learning via Posterior Sampling (2013, methodology): “We show through simulation that PSRL significantly outperforms existing algorithms with similar regret bounds.”
EPOpt: Learning Robust Neural Network Policies Using Model Ensembles (2016, methodology): “Model-free methods like Q-learning, actor-critic, and policy gradients are known to suffer from long learning times [6], which is compounded when combined with expressive function approximators like deep neural networks.”
On the Sample Complexity of Reinforcement Learning with a Generative Model (2012, methodology): “…problems, it has been shown that an action-value based variant of VI, model-based Q-value iteration (QVI), ﬁnds an ε -optimal estimate of the action-value function with high probability using only T = ˜ O ( N/ (cid:0) (1 − γ ) 4 ε 2 (cid:1) ) samples (Kearns & Singh, 1999; Kakade, 2004, chap.”
Reinforcement and Imitation Learning via Interactive No-Regret Learning (2014, methodology): “In the reinforcement learning setting, the bound provided is as strong as that provided by [4, 16] for an arbitrary policy class.”
Generalization and Exploration via Randomized Value Functions (2014, methodology): “As a specific algorithm of this kind, we propose randomized least-squares value iteration (RLSVI).”