From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning

By R´emi Munos. 2014

297 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Mathematical Optimization

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 Management Science and Operations Research

In Reinforcement Learning

In Mathematical Optimization

Citations in the corpus

Benchmark and Survey of Automated Machine Learning Frameworks (2019, methodology): “Even though multi-armed bandit learning can also be applied to continuous optimization (Munos, 2014), in the context of AutoML it is only used in a finite setting in combination with other optimization techniques (Hoffman et al., 2014; Efimova et al., 2017; Gustafson, 2018; das Dôres et al., 2018).”
Survey on Automated Machine Learning (2019, methodology): “tion methods. The selection of a hyperpartition can be modeled as a multi-armed bandit problem (Robbins, 1952). Even though multi-armed bandit learning can also be applied to continuous optimization (Munos, 2014), in the context of AutoML it is only used in a nite setting in combination with other o”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “In this section, we focus on the results concerning Gaussian process based Bayesian optimization and defer detailed discussions of bandit algorithms to other dedicated surveys [29], [117].”
The Uncertainty Bellman Equation and Exploration (2017, background): “However this approach can be computationally intractable for even very small problems [9] while direct computational approximations can fail spectacularly badly [22].”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, background): “ion to this problem (Bellman & Kalaba,1959). However, this is computationally intractable for anything beyond the simplest of toy problems and direct approximations can fail spectacularly poorly (Munos, 2014). As such, researchers have proposed and analyzed a number of heuristic reinforcement le”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “m in the face of uncertainty, whereby the agent searches for a value function that is a highprobability upper bound on the true value function, then follows the greedy policy for that value function (Munos, 2014; Szita and Szepesv´ari, 2010; Strehl and Littman, 2005). This process may involve, for e”
Integrated Task and Motion Planning (2020, methodology): “Sampling for continuous parameter values can itself be similarly guided, using techniques for optimistic global optimization (128, 107).”
Introduction to Multi-Armed Bandits (2019, background): “on of “taxonomy bandits”, where the goal is to CHAPTER 4. LIPSCHITZ BANDITS 53 output a “predicted best arm” with small instantaneous regret (Munos, 2011; Valko et al., 2013; Grill et al., 2015), see Munos (2014) for a survey. The main result essentially recovers the regret bounds for the zooming al”
Tunneling Neural Perception and Logic Reasoning through Abductive Learning (2018, background): “Recent studies have shown that derivative-free optimization algorithms can solve a range of sophisticated optimization functions at a guaranteed level [32, 37, 47].”
Derivative-Free Optimization via Classification (2016, methodology): “…optimization algorithms are very weak in their theoretical foundations, only except the recent development of the optimistic optimization method (Munos 2011; 2014), Bayesian optimization methods (Bull 2011; de Freitas, Smola, and Zoghi 2012), and ∗This research was supported by the NSFC…”
Planning in Discrete and Continuous Markov Decision Processes by Probabilistic Programming (2015, background): “Several improvements and extensions for UCT have been proposed, including handling continuous actions [13] (see [16] for a review), and continuous states [1] with a simple Gaussian distance metric; however the knowledge of the probabilistic model is not directly exploited.”
Bayesian Multi-Scale Optimistic Optimization (2014, methodology): “Deterministic optimistic optimization (DOO) and simultaneous optimistic optimization (SOO) are tree-based space partitioning methods for black-box function optimization (Munos, 2011, 2014).”
Simple regret for infinitely many armed bandits (2015, background): “One class of examples is fixed design such as linear bandits (Dani et al., 2008) other settings consider bandits in known or unknown metric space (Kleinberg et al., 2008; Munos, 2014; Azar et al., 2014).”
Reinforcement learning for control: Performance, stability, and deep approximators (2018, methodology): “they are generally exponentially complex in the horizon up to which sequences are examined (Munos, 2014).”
Beyond the One Step Greedy Approach in Reinforcement Learning (2018, methodology): “More interestingly, one may compute these first optimal actions with specifically designed procedures such as A∗-like/optimistic tree exploration algorithm (Hren & Munos, 2008; Busoniu & Munos, 2012; Munos, 2014; Szörényi et al., 2014; Grill et al., 2016).”
Optimal Best Arm Identification with Fixed Confidence (2016, background): “…efﬁcient strategies in much more elaborate settings, for example including side information ( Abbasi-Yadkori et al., 2011; Agrawal and Goyal, 2013), inﬁnitely many arms (Srinivas et al., 2010; Bubeck et al., 2011), or for the search of optimal strategies in games (Munos, 2014), to name just a few.”