Source-linked AI summary
(More) Efficient Reinforcement Learning via Posterior Sampling
Ian Osband, Daniel Russo, Benjamin Van Roy
TL;DR
Provably efficient reinforcement learning has largely relied on optimism to encourage exploration under uncertainty. This paper studies PSRL, which samples an MDP from a posterior each episode and follows its optimal policy, obtaining near-state-of-the-art regret guarantees and strong simulation performance.
Problem
Most provably efficient reinforcement learning algorithms use optimism, motivating the study of an alternative exploration approach.
Method
PSRL maintains a prior over MDPs, samples one posterior MDP at each episode, and follows its optimal policy for that episode.
Results
PSRL achieves ˜O(τS sqrt(AT)) expected regret, with guarantees among the first for a non-optimism-based algorithm, and outperforms UCRL2 across every simulated environment.
Takeaways & Limitations
PSRL is conceptually simple, computationally efficient, and naturally incorporates prior knowledge.
Takeaways & Limitations
The analysis assumes the state space, action space, and episode horizon are known and deterministic.
Abstract
from arXiv · showhide
Most provably-efficient learning algorithms introduce optimism about poorly-understood states and actions to encourage exploration. We study an alternative approach for efficient exploration, posterior sampling for reinforcement learning (PSRL). This algorithm proceeds in repeated episodes of known duration. At the start of each episode, PSRL updates a prior distribution over Markov decision processes and takes one sample from this posterior. PSRL then follows the policy that is optimal for this sample during the episode. The algorithm is conceptually simple, computationally efficient and allows an agent to encode prior knowledge in a natural way. We establish an $\tilde{O}(τS \sqrt{AT})$ bound on the expected regret, where $T$ is time, $τ$ is the episode length and $S$ and $A$ are the cardinalities of the state and action spaces. This bound is one of the first for an algorithm not based on optimism, and close to the state of the art for any reinforcement learning algorithm. We show through simulation that PSRL significantly outperforms existing algorithms with similar regret bounds.
1 Introduction
The paper frames reinforcement learning as exploration under uncertainty and studies posterior sampling as an alternative to optimism for efficient exploration.
- Reinforcement learning requires balancing exploration of poorly understood states and actions against improving future performance.
- Most provably efficient algorithms use optimism bonuses to make uncertain states and actions appear as valuable as statistically plausible.
- Posterior sampling represents environmental uncertainty with a prior and selects an episode policy by sampling an MDP from the posterior.
- Posterior sampling has a history in bandits, where it is also called Thompson sampling or probability matching.
- PSRL is motivated by computational efficiency, natural incorporation of prior environment structure, and separation of algorithmic components.
2 Problem formulation
The paper formulates episodic learning in a random finite-horizon MDP, with known state, action, and horizon spaces but uncertain rewards and transitions.
- The environment is a random finite-horizon MDP defined by state and action spaces, rewards, transitions, horizon τ, and an initial-state distribution.
- Reward distributions are supported on [0, 1], while transition probabilities specify next-state likelihoods and τ specifies the time horizon.
- The agent need not learn the state space, action space, or time horizon because S, A, and τ are assumed deterministic.
- A policy maps states and within-episode time positions to actions, and each MDP has an associated optimal policy.
- At each timestep, the agent selects an action, observes a scalar reward, and transitions to the next state.
- Regret is assessed relative to the optimal policy and can be random because the MDP, algorithmic sampling, transitions, and rewards may be random.
3 Posterior sampling for reinforcement learning
PSRL samples one MDP from the posterior at each episode, follows its optimal policy, and achieves regret guarantees comparable to leading optimism-based methods.
- Posterior sampling for reinforcement learning (PSRL): PSRL samples an MDP from the history-conditioned posterior at each episode and follows that MDP’s optimal policy throughout the episode.
- Posterior sampling for reinforcement learning (PSRL): The algorithm iterates posterior sampling, policy computation, action execution, and observation collection across finite episode steps.
- Posterior sampling for reinforcement learning (PSRL): PSRL avoids explicit confidence-bound construction and requires only one posterior sample, supporting simpler and cheaper computation than optimistic approaches.
- 3.1 Main results: ˜O(τS sqrt(AT)) expected regret provides one of the first guarantees for an algorithm not based on optimism.
- 3.1 Main results: The main result holds for any prior distribution on MDPs, while the performance measure is expected regret under that prior.
- 3.1 Main results: The guarantees are related to UCRL2 and REGAL, whose episodic adaptations also yield ˜O(τS sqrt(AT)) bounds.
4 True versus sampled MDP
Posterior sampling makes the true and sampled MDP identically distributed at each episode start, enabling regret to be related to quantities from the sampled model.
- At the start of each episode, the true MDP M* and sampled MDP M_k are identically distributed.This posterior-sampling property connects the unknown environment to the sampled environment.
- The posterior-sampling lemma preserves equality in expectation for functions measurable from the history before episode k.The tower property gives E[g(M*)] = E[g(M_k)].
- The regret-equivalence argument avoids direct dependence on the unobserved optimal policy by using posterior sampling.The resulting comparison tracks the policy actually selected by the agent.
- Regret in episode k can be compared with the difference between the policy’s expected values under the sampled and true MDPs.The sampled-model value is known to the agent, while the true-model performance is observed through interaction.
- As information accumulates, differences between a policy’s performance in the true and sampled MDPs are expected to diminish.This motivates formal regret bounds based on the sampled model’s estimation error.
5 Analysis
The analysis rewrites regret using Bellman errors on visited states, then controls those errors with posterior concentration and confidence sets.
- Dynamic programming expresses regret through one-step Bellman errors and transition randomness.The Bellman operator returns the expected one-step value under a policy and MDP.
- The Bellman-error term depends only on the executed policy and states actually visited during the first T periods.Posterior concentration around the true Bellman operator makes this term tend toward zero.
- Confidence sets are constructed from empirical transition and reward estimates observed for each state-action pair.The sets are chosen conservatively so that both the true and sampled MDPs lie inside with high probability.
- The confidence-bound analysis is explicitly not optimized and can be improved by at least a numerical factor.The regret decomposition uses the bound that the per-episode comparison is at most τ.
- Posterior sampling equates the conditional probabilities that the sampled or true MDP falls outside the confidence set.This follows because the sampled MDP is measurable with respect to the episode-start history.
- The analysis completes by combining the confidence-set decomposition with worst-case bounds involving S, A, T, and logarithmic factors.The displayed analysis includes terms proportional to τ and sqrt(SAT log(SAT)).
6 Simulation results
Simulations compare PSRL with UCRL2 on RiverSwim and randomly generated MDPs, including episodic and infinite-horizon settings. PSRL outperformed UCRL2 across every tested environment, with especially strong RiverSwim performance.
- Experimental setup: PSRL was compared with UCRL2 on RiverSwim and randomly generated MDPs, under both episodic resets and an infinite-horizon setting.The episodic experiments reset the state every τ = 20 steps.
- RiverSwim: RiverSwim uses six chained states where moving right is difficult but leads to a much larger reward than moving left.The environment is designed so efficient exploration is required to discover the optimal policy.
- Results: PSRL outperformed UCRL2 across every tested environment in simulations using 20 Monte Carlo runs and 10,000 time steps.The comparison used Dirichlet and normal-gamma priors for transitions and rewards.
- Infinite-horizon results: Figure 2 tracks simulated regret over time on the infinite-horizon RiverSwim environment, where PSRL’s outperformance is described as quite extreme.The figure uses 50 Monte Carlo simulations through 100,000 time steps.
- Infinite-horizon results: In the infinite-horizon case, PSRL can use an episode rule that begins a new episode when visits to any state-action pair double.This adapts an episode mechanism also used by UCRL2 and REGAL.
7 Conclusion
The paper establishes PSRL as a provably efficient reinforcement-learning algorithm rather than merely a heuristic. Its Bayesian regret bounds are among the first for a non-optimistic algorithm and are close to the state of the art.
- PSRL is established as a provably efficient learning algorithm rather than only a heuristic.
- PSRL has Bayesian regret bounds that are among the first for an algorithm not motivated by optimism and are close to the state of the art.The bounds hold in expectation irrespective of prior or model structure.
- The paper characterizes PSRL as conceptually simple, computationally efficient, and able to incorporate prior knowledge.It also reports favorable simulation performance across several domains.
A Relating Bayesian to frequentist regret
The appendix considers Bayesian regret bounds over MDP families with non-zero prior probability and relates them to frequentist guarantees when the true MDP is not impossible under the prior.
- The analysis considers any MDP family with non-zero probability under the prior.
- The resulting bounds can apply even when the true MDP is not distributed according to the prior.
- When the true MDP is not impossible under the prior, the appendix states that asymptotic frequentist regret is close to the theoretical lower bounds in its T-dependence.
B Bounding the sum of confidence set widths
This appendix bounds confidence-set contributions by separating low-visit state-action pairs from frequently visited ones, under rewards and transitions constrained to [0, 1].
- The proof introduces confidence-set width expressions involving state count S, logarithmic factors, and visit counts N_tk(s,a).
- State-action pairs with N_tk(s,a) ≤ τ can contribute fewer than 2τSA visits in total.
- For N_tk(s,a) > τ, the proof relates later counts to the episode-start count through N_t(s,a) + 1 ≤ 2N_tk(s,a).
- The argument assumes that all rewards and transitions are constrained to [0, 1].