Source-linked AI summary
A Bayesian Sampling Approach to Exploration in Reinforcement Learning
John Asmuth, Lihong Li, Michael L. Littman, Ali Nouri, David Wingate
TL;DR
Reinforcement learning needs exploration that reduces uncertainty without sacrificing reward, while existing approaches face tractability or limited planning trade-offs. BOSS maintains a Bayesian posterior, samples and merges models optimistically, and achieves near-optimal behavior with favorable comparisons and generalization through a non-parametric model. Its guarantees assume posterior sampling is feasible and the prior accurately describes the environment model space.
Problem
Reinforcement learning must balance exploration that reveals uncertain environment dynamics with exploitation of current knowledge to obtain high reward.
Method
BOSS maintains a posterior over models, samples multiple models when state–action counts reach a threshold, and merges them into an optimistic MDP for action selection.
Results
BOSS takes near-optimal actions on all but a small number of trials with high probability, compares favorably across tested scenarios, and can generalize experience between states using a non-parametric Bayesian model.
Takeaways & Limitations
BOSS provides a modular exploration approach that combines Bayesian model learning with optimistic decision making and can learn more quickly than non-generalizing comparison algorithms in clustered-state settings.
Takeaways & Limitations
The analysis assumes efficient posterior sampling and requires a prior that accurately describes the environment’s model space.
Abstract
from arXiv · showhide
We present a modular approach to reinforcement learning that uses a Bayesian representation of the uncertainty over models. The approach, BOSS (Best of Sampled Set), drives exploration by sampling multiple models from the posterior and selecting actions optimistically. It extends previous work by providing a rule for deciding when to resample and how to combine the models. We show that our algorithm achieves nearoptimal reward with high probability with a sample complexity that is low relative to the speed at which the posterior distribution converges during learning. We demonstrate that BOSS performs quite favorably compared to state-of-the-art reinforcement-learning approaches and illustrate its flexibility by pairing it with a non-parametric model that generalizes across states.
1 INTRODUCTION
Reinforcement learning must balance gathering information about uncertain environment dynamics with exploiting current knowledge for reward. BOSS addresses this dilemma with posterior-based optimistic exploration, aiming to retain stronger guarantees and broader scalability than alternative approaches.
- Exploration in reinforcement learning requires acquiring experience that reduces uncertainty about environment dynamics while pursuing high reward.
- Belief-lookahead methods make optimal decisions under uncertainty but are generally intractable and therefore require approximations that sacrifice optimality.
- Myopic methods reduce uncertainty without explicitly considering its effect on future reward; RMAX instead explores by treating insufficiently visited states optimistically.
- Undirected methods explore without regard to which model components remain uncertain, and their guarantees are generally weaker.
- BOSS maintains a posterior over models, samples multiple models, and acts optimistically with respect to the best sampled set.
2 BOSS: BEST OF SAMPLED SET
BOSS answers when to resample and how to combine posterior models by sampling after state–action counts reach a threshold and merging the samples into an optimistic MDP. This design keeps planning polynomial while supporting posterior-based exploration.
- Posterior-sampling approaches must decide when to sample, how many models to sample, and how to combine those models.
- BOSS samples K posterior models whenever a state–action pair reaches B transitions, then merges them into an optimistic MDP for decision making.
- BOSS labels a state–action pair known after it has been observed B times, analogously to RMAX.
- Merging creates an MDP with the original state space and an augmented action space of KA actions, each corresponding to an action in one sampled model.
- BOSS solves no more than SA merged MDPs and samples at most KSA models, requiring polynomial planning time when posterior sampling is efficient.
3 ANALYSIS
The analysis establishes high-probability near-optimality for BOSS by combining optimism, posterior concentration, and PAC-MDP reasoning. Its sample complexity depends on Bayesian concentration, which yields polynomial guarantees under suitable prior-convergence conditions and is polynomial for an uninformative Dirichlet prior.
- General guarantee: BOSS is analyzed as a non-stationary policy whose value is ϵ-close to optimal except for a polynomial number of steps, with high probability.The analysis targets V_A^t(s_t) being ϵ-close to optimal outside a polynomial number of steps when K and B are chosen appropriately.
- Optimism: K = Θ(1/δ1) sampled models contain an optimistic model with probability at least 1 −δ1.The proof separates cases according to the posterior probability P of sampling an optimistic model and bounds the probability that all K samples fail.
- Optimism: The merged MDP is optimistic throughout learning with probability at least 1 −δ.The argument applies union bounds across state–action pairs and model-sampling steps.
- Posterior concentration: With B set through Bayesian concentration complexity, sampled transition functions are ϵ-close to the true transitions on known pairs with probability at least 1 −δ −ρ.The bound uses diffusion parameter ρ and accounts for concentration across state–action pairs, sampled models, and sampling steps.
- Sample complexity: The bound depends on Bayesian concentration complexity f, whose analysis depends on the model space and prior; sufficiently fast prior convergence yields polynomial exploration complexity.The paper leaves a full analysis of f beyond scope, but relates it to prior characteristics and states that ε_n = O(n^-c) gives a polynomial bound.
- Sample complexity: For an uninformative Dirichlet prior, f is polynomial in the relevant quantities, yielding a performance guarantee similar to RMAX’s PAC-MDP result.This is a prior-specific consequence of the general concentration analysis.
4 EXPERIMENTS
Experiments evaluate BOSS on the Chain problem, including priors that either share or independently represent transition parameters. BOSS performs effectively across Semi and Full settings, where belief-lookahead becomes difficult in the larger parameter space.
- Prior structure: The Tied prior shares one slip probability across all state–action pairs, whereas the Full prior models each pair with an independent multinomial distribution.The Tied prior therefore encodes stronger structural knowledge about transition dynamics.
- Chain experiment: The Chain experiment compares cumulative reward over the first 1000 steps, averaged across 500 runs, against an optimal-policy score of 3677.BOSS uses B = 10 and K = 5, with discount factor γ = 0.95.
- Results by scenario: All algorithms perform very well in Tied, although RAM-RMAX is slower because it must estimate the shared slip probability accurately.The slower behavior can lead RAM-RMAX toward a suboptimal policy during estimation.
- Results by scenario: In Semi, BEETLE is more effective than exploit, while in Full BEETLE falls behind because the larger parameter space makes belief-lookahead difficult to complete.The scenarios therefore distinguish careful exploration from the computational burden of belief-space planning.
- Results by scenario: BOSS explores as effectively as BEETLE in Semi and remains effective in Full, while Bayesian DP achieves a cumulative reward of 3158 in Full.This shows favorable performance in both the more careful-exploration setting and the larger-parameter-space setting.
5 BAYESIAN MODELING OF STATE CLUSTERS
BOSS uses a non-parametric Bayesian clustering model to share transition information across states while learning the cluster structure. In Chain and Chain2, learned clustering improves performance relative to weaker or mismatched priors, with differences statistically significant.
- Model: BOSS models states in a cluster with shared multinomial transition parameters, placing Dirichlet priors over those parameters to couple observations.The model integrates out cluster-specific parameters and uses posterior predictive distributions for transition sampling.
- Model: The Chinese Restaurant Process prior allows BOSS to infer both the number of state clusters and their assignments.Gibbs sampling repeatedly updates state assignments, including the possibility of creating a new cluster.
- Prior comparison: In Chain, the Cluster prior identifies the single cluster quickly and is not significantly worse than the stronger Tied prior.The experiments used B = 10 and K = 5, with Cluster using a CRP concentration parameter α = 0.5.
- Prior comparison: In Chain2, Tied’s single-cluster assumption is violated, while Cluster outperforms Full by learning two independent clusters.The differences across priors and environments are statistically significant (2 × 3 ANOVA p < 0.001).
- Marble Maze: BOSS variants with learned cluster structure dominated RMAX in cumulative reward, with BOSS B = 10 K = 10 reaching near-optimal behavior nearly instantaneously.RMAX variants required 50 to 250 trials before behaving comparably; the clustering prior’s outcomes helped BOSS ignore longer paths after finding an effective one.
- Marble Maze: In the 6x6 Marble Maze, BOSS learned roughly 10 clusters and grouped frequently visited states according to action-relevant wall patterns.Frequently visited states under the optimal policy were grouped accurately, while less commonly visited states were clustered less systematically.
6 CONCLUSIONS
BOSS is presented as a modular Bayesian exploration approach that combines model learning with exploration and decision-making. The paper reports strong performance across tested scenarios, faster learning with non-parametric clustering, and flexibility for future Bayesian-model integrations.
- BOSS interfaces a Bayesian model learner with sampled-model exploration and decision-making components, enabling behavior that converges quickly to near optimality.
- Across tested scenarios, BOSS was as good as the best known exploration algorithm.
- BOSS learned more quickly with a non-parametric Bayesian clustering model than non-generalizing comparison algorithms.
- Future work considers priors that are only approximate indicators of the real environment distribution and hierarchical methods for learning more accurate priors.
- The paper proposes integrating newly developed Bayesian-model specification languages directly with BOSS to create a flexible learning toolkit.