Abstract
Bayesian reinforcement learning (RL) is aimed at making more efficient use of data samples, but typically uses significantly more computation. For discrete Markov Decision Processes, a typical approach to Bayesian RL is to sample a set of models from an underlying distribution, and compute value functions for each, e.g. using dynamic programming. This makes the computation cost per sampled model very high. Furthermore, the number of model samples to take at each step has mainly been chosen in an ad-hoc fashion. We propose a principled method for determining the number of models to sample, based on the parameters of the posterior distribution over models. Our sampling method is local, in that we may choose a different number of samples for each state-action pair. We establish bounds on the error in the value function between a random model sample and the mean model from the posterior distribution. We compare our algorithm against state-of-the-art methods and demonstrate that our method provides a better trade-off between performance and running time.
Introduction
Model-Based Bayesian Reinforcement Learning (RL) involves maintaining a probability distribution over possible models of the environment. While this approach allows for principled exploration, it is often computationally prohibitive. A common technique involves sampling multiple models from the posterior distribution and solving them to determine an optimal policy. However, the number of samples ($K$) and the frequency of resampling ($B$) have historically been chosen through ad-hoc "magic numbers."
This paper introduces SmarterSampler, an algorithm that replaces these heuristics with a principled statistical approach. By dynamically adjusting sampling parameters based on the variance of the posterior distribution, SmarterSampler achieves state-of-the-art performance with significantly lower computational overhead than previous methods like BOSS.
The SmarterSampler Algorithm
The core innovation of SmarterSampler lies in its "local" approach to sampling and its dynamic trigger for re-evaluation.
Local, Variance-Based Sampling
Instead of a global sample count, the algorithm determines the number of samples for each state-action pair $(s, a)$ based on the variance of its associated Dirichlet distribution. When the agent is uncertain about a transition, it increases the sample count to better capture potential outcomes. As it gains experience and the posterior variance decreases, the required number of samples drops, ensuring computational resources are spent where uncertainty is highest.
Dynamic Resampling
SmarterSampler monitors the "drift" of the mean model rather than resampling at fixed intervals. It calculates a score based on how many standard deviations the current posterior mean has moved from the mean used for the last set of samples. A costly re-computation is only triggered when the model has changed significantly, allowing the agent to be more tolerant of change early in learning and more precise as it converges.
Experimental Evaluation
The authors evaluated SmarterSampler on several classic RL benchmark domains, ranging from simple chains to complex grid-worlds.
The Chain Problem (Figure 2) tests an agent's ability to delay gratification for long-term rewards. In more complex spatial tasks, such as the 6x6 Maze and the Dearden Maze (Figure 1), the agent must navigate around traps and collect items to reach a goal.
Key Results
- Efficiency vs. Performance: SmarterSampler reached high reward levels much faster in terms of wall-clock time than the BOSS algorithm.
- Reduced Sampling: While fixed-rate samplers continue to sample linearly, SmarterSampler’s sampling rate plateaus as it becomes confident in the model, leading to massive time savings in later stages of learning.
- Robustness: The algorithm is less sensitive to initial hyperparameter choices, as the statistical bounds naturally correct the sampling behavior over time.
Conclusion
SmarterSampler addresses a major bottleneck in Bayesian RL by providing a principled way to manage computational resources. By linking sampling density to posterior variance, it enables more efficient exploration and faster convergence. Future work may extend these variance-based methods to continuous state spaces and environments with uncertain reward functions.
Summary updated