R-MAX - A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning

By Ronen I. Brafman, Moshe Tennenholtz. 2001

1,390 citations recorded by the source corpus.

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

Citations in the corpus

Investigating Contingency Awareness Using Atari 2600 Games (2012, background): “Solving these harder games may require more elaborate reinforcement learning techniques, such as smarter exploration (Brafman and Tennenholtz 2003), temporally extended actions (Sutton, Precup, and Singh 1999) or MonteCarlo Tree Search (Kocsis and Szepesvári 2006).”
Concrete Problems in AI Safety (2016, background): “can’t get out of. Robot helicopters may run into the ground or damage property; industrial control systems could cause serious issues. Common exploration policies such as epsilongreedy [150] or R-max [31] explore by choosing an action at random or viewing unexplored actions optimistically, and thus ”
Taming the Noise in Reinforcement Learning via Soft Updates (2015, background): “While in the usual case the optimism is externally imposed as an initial condition [19], here it is spontaneously generated by the noise and selfcorrected through exploration.”
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).”
Deep Reinforcement Learning with Double Q-Learning (2015, background): “…should not be confused with optimism in the face of uncertainty (Sutton, 1990; Agrawal, 1995; Kaelbling et al., 1996; Auer et al., 2002; Brafman and Tennenholtz, 2003; Szita and L ˝ orincz, 2008; Strehl et al., 2009), where an exploration bonus is given to states or actions with…”
Unifying Count-Based Exploration and Intrinsic Motivation (2016, methodology): “ion of the close relationship between tabular value estimation using a decaying step-size (e.g. Even-Dar and Mansour, 2001; Azar et al., 2011) and count-based exploration in the tabular setting (e.g. Brafman and Tennenholtz, 2002; Strehl and Littman, 2008; Jaksch et al., 2010; Szita and Szepesv´ari,”
Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models (2015, methodology): “Many of the pioneering algorithms in this area, such as R − Max [8] and E 3 [9], achieve efﬁcient exploration that scales polynomially with the number of parameters in the agent’s state space (see also [10, 11]).”
Deep learning in neural networks: An overview (2014, background): “…Bertsekas, & Borkar, 2002; Baird, 1995; Baird & Moore, 1999; Barto, Sutton, & Anderson, 1983; Bertsekas, 2001; Bradtke, Barto, & Kaelbling, 1996; Brafman & Tennenholtz, 2002; Kaelbling, Littman, & Cassandra, 1995; Lagoudakis & Parr, 2003; Maei & Sutton, 2010; Mahadevan, 1996; Meuleau, Peshkin,…”
Learning First-Order Symbolic Representations for Planning from the Structure of the State Space (2019, neutral): “The same inputs are used in model-based reinforcement learning methods where the policy is derived from a flat model that is learned incrementally but which does not transfer to other problems [8].”
Deep Reinforcement Learning for Autonomous Driving: A Survey (2020, methodology): “In the case of model-based approaches ( e.g. Dyna-Q [32], R-max [33]), agents attempt to learn the transition function T and reward function R , which can be used when making action selections.”
Reinforcement Learning in Healthcare: A Survey (2019, methodology): “traditional RL community, proposing a wealth of exploration strategies including simple heuristics such as ε-greedy and Boltzmann exploration, Bayesian learning [22], [23], countbased methods with Probably Approximately Correct (PAC) guarantees [24], [25], as well as more expressive methods of intri”
Reinforcement learning in robotics: A survey (2013, background): “In principle, reinforcement learning algorithms for Markov Decision Processes with performance guarantees are known (Kakade, 2003; Kearns and Singh, 2002; Brafman and Tennenholtz, 2002) with polynomial scaling in the size of the state and action spaces, an additive error term, as well as in the hori”
Information seeking, curiosity and attention: computational and neural mechanisms (2013, neutral): “dynamics and using it to plan a solution (Brafman and Tennenholtz 2003), or it may directly optimize parameters of a solution in model-free approaches (Sutton, McAllester et al.”
Safe Policy Improvement with Baseline Bootstrapping (2017, methodology): “[5] Ronen I Brafman and Moshe Tennenholtz.”
The Uncertainty Bellman Equation and Exploration (2017, background): “For this reason, most provably-efficient approaches to reinforcement learning rely upon the optimism in the face of uncertainty (OFU) heuristic [14, 13, 7].”
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…”