Near-Optimal Reinforcement Learning in Polynomial Time

By Michael Kearns, Satinder Singh. 2002

1,236 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Computer Networks and Communications

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

Learning Parameterized Skills (2012, methodology): “Two techniques have been especially influential among researchers studying efficient RL algorithms: R–Max [11], and E(3) [30].”
Surprising Negative Results for Generative Adversarial Tree Search (2018, background): “The exploration-exploitationtrade-off is extensively studied in RL literature (Kearns & Singh, 2002; Brafman & Tennenholtz, 2003; Asmuth et al., 2009).”
Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents (2017, background): “Most approaches for exploration focus on the tabular case and generally learn models of the environment (e.g., Brafman & Tennenholtz, 2002; Kearns & Singh, 2002; Strehl & Littman, 2008).”
Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models (2015, methodology): “Many of the pioneering algorithms in this area, such as R − Max [7] and E(3) [8], achieve efficient exploration that scales polynomially with the number of parameters in the agent’s state space (see also [9, 10]).”
Reinforcement Learning in Healthcare: A Survey (2019, methodology): “L methods applied in healthcare in the current literature [199], [196], [200]. While a number of modelbased RL algorithms have been proposed and investigated in the RL community (e.g., R-max [25], E3 [318]), most of these algorithms assume that the agent operates in small domains with a discrete sta”
Reinforcement learning in robotics: A survey (2013, background): “…(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 suitable substitute including the discount factor or “mixing time” (Kearns and Singh, 2002)).”
Doubly Robust Policy Evaluation and Optimization (2014, background): “This theorem is the ﬁrst of this sort for policy eval-uators, although the mechanics of its proof have appeared in model-based reinforcement-learning (e.g., Kearns and Singh, 1998).”
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].”
Adaptive Online Planning for Continual Lifelong Learning (2019, background): “[17] considers MDPs with various reward functions, using them to decide whether to explore or exploit, similar to our framework.”
MOReL : Model-Based Offline Reinforcement Learning (2020, background): “Such a hard partitioning was considered in early works like E(3) [55], R-MAX [56], and metric-E(3) [57], but was not used to encourage pessimism.”
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).”
The Uncertainty Bellman Equation and Exploration (2017, background): “Propagating the potential value of exploration over many timesteps, or deep exploration, is important for statistically efficient RL [13, 26].”
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…”
Bootstrapping with Models: Confidence Intervals for Off-Policy Evaluation (2016, neutral): “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].”
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”