Bayesian sparse sampling for on-line reward optimization

By Tao Wang, Daniel J. Lizotte, Michael H. Bowling, Dale Schuurmans. 2005

126 citations recorded by the source corpus.

We present an efficient "sparse sampling" technique for approximating Bayes optimal decision making in reinforcement learning, addressing the well known exploration versus exploitation tradeoff. Our approach combines sparse sampling with Bayesian exploration to achieve improved decision making while controlling computational cost. The idea is to grow a sparse lookahead tree, intelligently, by exploiting information in a Bayesian posterior---rather than enumerate action branches (standard sparse sampling) or compensate myopically (value of perfect information). The outcome is a flexible, practical technique for improving action selection in simple reinforcement learning scenarios.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research

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 Computational Theory and Mathematics

In Management Science and Operations Research

Citations in the corpus

Deep Exploration via Bootstrapped DQN (2016, methodology): “Other approaches aim to approximate Bayes-optimal exploration though tree-based search (Wang et al., 2005; Guez et al., 2014).”
(More) Efficient Reinforcement Learning via Posterior Sampling (2013, methodology): “We show through simulation that PSRL significantly outperforms existing algorithms with similar regret bounds.”
A Bayesian Sampling Approach to Exploration in Reinforcement Learning (2009, background): “Myopic (Wang et al., 2005) approaches make decisions to reduce uncertainty, but they do not explicitly consider how this reduced uncertainty will impact future reward.”
Learning and Using Models (2012, methodology): “Wang et al (2005) make this method more computationally feasible by combining it with MCTS-like planning.”
Better Optimism By Bayes: Adaptive Planning with Rich Models (2014, methodology): “(Wang et al Ross and Pineau 2008; Asmuth and Littman 2011).”
Multi-task reinforcement learning: a hierarchical Bayesian approach (2007, methodology): “This is similar to Thompson sampling which has been employed with success in prior work (Thompson, 1933; Strens, 2000; Wang et al., 2005), but di.ers in that instead of sampling a single MDP and solving it, we draw a set of MDPs and select the one with highest probability.”
Bayesian Reinforcement Learning (2010, methodology): “…is Thompson sampling , which involves sampling just one MDP from the current belief, solve this MDP to optimality (e.g., by Dynamic Programming), and execute the optimal action at the current state (Thompson, 1933; Strens, 2000), a strategy that reportedly tends to over-explore (Wang et al, 2005).”
A Bayesian Approach for Learning and Planning in Partially Observable Markov Decision Processes (2011, methodology): “Because of this convenience, most authors assume that the prior over the transition function T follows the previous independence and Dirichlet assumptions (Duff, 2002; Dearden et al., 1999; Wang et al., 2005; Castro and Precup, 2007).”
An analytic solution to discrete Bayesian reinforcement learning (2006, background): “…(Dearden et al., 1998), linear combinations of hyperparameters (Duff, 2003) and sampling (Dearden et al., 1999; Strens, 2000; Wang et al., 2005) have been proposed, but they tend to be computationally intensive at run time, preventing online learning or to make drastic approximations…”
Convex Optimization: Algorithms and Complexity (2015, unknown): “This can be very time consuming, and thus, so far the approach has only been applied to small MDPs. HMDP: A linear program approach for the hyper-state MDP Castro and Precup [Castro and Precup, 2007] present a similar approach to [Wang et al., 2005].”
Optimistic Bayesian Sampling in Contextual-Bandit Problems (2012, background): “According to Wang et al. (2005), " in all but trivial circumstances, there is no hope of exactly following an optimal action selection strategy " .”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, unknown): “has been weakened by Wang et al. [2008] with an assumption focusing on this distribution upper tail only.”
Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints (2014, unknown): “A deterministic policy f : Q∗ → Σ is such that given ρ = q0 . . . qn, f(ρ) = σ only if σ is enabled at qn.”
Multi-task Reinforcement Learning in Partially Observable Stochastic Environments (2009, background): “Solving a POMDP is computationally expensive, which is particularly true when one takes into account the model uncertainty; in the latter case the POMDP state space grows fast, often making it inefficient to find even an approximate solution (Wang et al. 2005).”
Bayes-Adaptive Simulation-based Search with Value Function Approximation (2014, methodology): “1 Algorithm As in other forward-search planning algorithms for Bayesian model-based RL [22, 17, 1, 12], at each step t, which is associated with the current history ht (or belief) and state st, we plan online to find π̃(ht, st) by constructing an action-value function Q(h, s, a).”