A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes

By Michael Kearns, Yishay Mansour, Andrew Y. Ng. 1999

Subfields: Reinforcement Learning, Algorithms & Complexity

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 Algorithms & Complexity

Citations in the corpus

Surprising Negative Results for Generative Adversarial Tree Search (2018, methodology): “To mitigate the effect of the bias, one can deploy MCTS methods [25, 27] to enhance the quality of policies by rolling out on the simulated environment.”
Mapping Instructions and Visual Observations to Actions with Reinforcement Learning (2017, background): “plexity (Kearns et al., 1999; Krishnamurthy et al., 2016).”
Reverse Curriculum Generation for Reinforcement Learning (2017, background): “[24]) and is deemed to be a considerably weaker assumption than having access to the full transition model of the MDP.”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, neutral): “image, text, or audio signals. Alternatively, Monte Carlo Tree Search (MCTS) methods can handle arbitrarily large state spaces, but only at the cost of exponential dependence on the planning horizon [Kearns et al., 2002, Kocsis and Szepesvari, 2006]. Our work departs from these existing eorts by aim”
Equivalence notions and model minimization in Markov decision processes (2003, background): “Large state spaces have also been dealt with approximately by trajectory sampling in [26], and elsewhere.”
DESPOT: Online POMDP Planning with Regularization (2013, methodology): “The sparse sampling (SS) algorithm (Kearns et al., 2002) and the DESPOT algorithm both construct sparse approximations to a belief tree.”
Strategic Object Oriented Reinforcement Learning (2018, background): “Fortunato et al., 2017). However, these methods are unable to show substantial improvement in hard exploration, sparse reward environments. A closely related line of research, ﬁnite horizon planning (Kearns et al., 2002; Mannor et al., 2007; Kearns et al., 1994), has noted how planning horizon can a”
PAC Reinforcement Learning With an Imperfect Model (2018, methodology): “3To approximate the oracle in problems with large state spaces, we can use Sparse Sampling (Kearns, Mansour, and Ng 2002) or any Monte-Carlo tree search methods that do not depend on the state branching factor (Bjarnason, Fern, and Tadepalli 2009; Grill, Valko, and Munos 2016).”
Algorithmic Game Theory (2012, unknown): “For references on online algorithms and methods for solving sequential decision problems see [BEY98, HB06, Put94, KMN99].”
Knows what it knows: a framework for self-aware learning (2008, background): “Fortunately, recent advances in approximate local planning have made it possible for large-scale problems (Kearns et al. 2002; Kocsis and Szepesvári 2006).”
A unifying framework for computational reinforcement learning theory (2009, methodology): “So, the per-step computation complexity scales nicely from regression problems to sequential decision making in MDPs, in contrast to algorithms such as state-space discretization [Chow and Tsitsiklis 1989] that scales exponentially in the dimension of S and sparse sampling [Kearns et al. 2002] that ”
Reinforcement Learning as Classification: Leveraging Modern Classifiers (2003, methodology): “We expect this approach would benefit from more sophisticated approaches to managing the number of samples used (Kaelbling, 1993; Kearns et al., 1999).”
Online Planning for Large Markov Decision Processes with Hierarchical Decomposition (2015, methodology): “BACKGROUND In this section, we brieﬂy review the MDP model [Puterman”