Near-Optimal BRL using Optimistic Local Transitions

By Mauricio Araya-López, Olivier Buffet, Vincent Thomas. 2012

41 citations recorded by the source corpus.

Model-based Bayesian Reinforcement Learning (BRL) allows a sound formalization of the problem of acting optimally while facing an unknown environment, i.e., avoiding the exploration-exploitation dilemma. However, algorithms explicitly addressing BRL suffer from such a combinatorial explosion that a large body of work relies on heuristic algorithms. This paper introduces BOLT, a simple and (almost) deterministic heuristic algorithm for BRL which is optimistic about the transition function. We analyze BOLT's sample complexity, and show that under certain parameters, the algorithm is near-optimal in the Bayesian sense with high probability. Then, experimental results highlight the key differences of this method compared to previous work.

Subfields: Artificial Intelligence, Computer Networks and Communications

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

Citations in the corpus

Model-based reinforcement learning with parametrized physical models and optimism-driven exploration (2015, background): “In the case of linear dynamics or discrete systems, this optimistic exploration scheme has a number of desirable theoretical properties that make it a good choice [1], [3], [4], [7].”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, methodology): “In addition to the results already presented we also investigate the scaling of similar Bayesian learning algorithms BEB [17] and BOLT [1].”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “We also ran comparisons against BOLT [4], UCFH [14],”
Convex Optimization: Algorithms and Complexity (2015, unknown): “The main insight in BOLT is to put a similar exploration bonus on the transition probabilities [Araya-Lopez et al., 2012].”
An Optimistic Posterior Sampling Strategy for Bayesian Reinforcement Learning (2013, methodology): “We propose a strategy based on two main assumptions: (i) a posterior distribution can be maintained over the set of all possible transition models, and (ii) one can easily sample and solve MDPs drawn according to this posterior.”
Optimism-driven exploration for nonlinear systems (2015, methodology): “Our method extends the approaches presented in [4] and [6] to nonlinear dynamical systems.”
Bayesian Optimal Control of Smoothly Parameterized Systems (2015, methodology): “…e The reader interested in further algorithms for Bayesian reinforcement learning (including algorithms for inﬁnite state spaces) may consult the papers of Araya-L´opez et al. (2012), Vlassis et al. (2012) and Guez et al. (2013), which together give an excellent overview of the literature.”
Bounded Optimal Exploration in MDP (2016, methodology): “In the appendix of the extended version, we present the results for a problem with low-probability high-consequence transitions, in which PAC-RMDP(8) produced the best result. ter δ. BEB and BOLT are near-Bayes optimal algorithms whose parameters β and η are fully specified by their analyses, namely”
Unifying Count-Based Exploration and Intrinsic Motivation (2016, methodology): “Since an exploration bonus proportional to Nn(x, a) −1 leads to PAC-BAMDP algorithms (Kolter and Ng, 2009; Araya-López et al., 2012), we hypothesize that similar bounds can be derived for our pseudo-counts.”
Active Reinforcement Learning with Monte-Carlo Tree Search (2018, background): “Optimism in the face of uncertainty Optimism means adding bonuses to more uncertain rewards and taking optimal actions in the resulting optimistic MDP (Kolter and Ng, 2009; Araya et al., 2012; Auer et al., 2002).”
Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models (2015, methodology): “, as the size of state spaces increases, these methods quickly become intractable. A number of prior methods also examine various techniques for using models and prediction to incentivize exploration [12, 13, 14, 15]. However, such methods typically operate directly on the transition matrix of a dis”