Why is Posterior Sampling Better than Optimism for Reinforcement Learning?

Ian Osband; Benjamin Van Roy

Source-linked AI summary

Why is Posterior Sampling Better than Optimism for Reinforcement Learning?

Ian Osband, Benjamin Van Roy

arXiv:1607.00215v3Jul 1, 2016stat.MLcs.AIcs.LG

TL;DR

The paper asks why PSRL outperforms optimism-based reinforcement-learning algorithms and uses stochastic-optimism analysis plus experiments to investigate the difference. It establishes an ˜O(H√SAT) Bayesian expected-regret bound for PSRL, improving prior guarantees while highlighting a statistical-efficiency versus computational-tractability tension in OFU.

Problem
The paper studies why PSRL can outperform optimism-based reinforcement-learning algorithms and seeks insight into the source and extent of that performance difference.
Method
The paper analyzes PSRL through stochastic optimism, regret decomposition, and computational experiments in finite-horizon episodic MDPs.
Results
˜O(H√SAT) Bayesian expected regret is established for PSRL, improving on the previous ˜O(H S√AT) bound for any RL algorithm.
Takeaways & Limitations
PSRL offers computationally tractable statistically efficient exploration, while equally efficient OFU approaches may require computationally intractable optimization.
Takeaways & Limitations
The formal analysis focuses on Bayesian expected regret in finite-horizon MDPs, leaving discounted and infinite-horizon settings for future work.

Abstract

from arXiv · show

Computational results demonstrate that posterior sampling for reinforcement learning (PSRL) dramatically outperforms algorithms driven by optimism, such as UCRL2. We provide insight into the extent of this performance boost and the phenomenon that drives it. We leverage this insight to establish an $\tilde{O}(H\sqrt{SAT})$ Bayesian expected regret bound for PSRL in finite-horizon episodic Markov decision processes, where $H$ is the horizon, $S$ is the number of states, $A$ is the number of actions and $T$ is the time elapsed. This improves upon the best previous bound of $\tilde{O}(H S \sqrt{AT})$ for any reinforcement learning algorithm.

1. Introduction

The paper studies exploration in reinforcement learning and contrasts posterior sampling with optimism-based methods. It develops theoretical and computational evidence that PSRL achieves strong statistical efficiency while avoiding key inefficiencies of OFU approaches.

Motivation: Reinforcement learning requires balancing exploration for long-term information against exploitation of near-term rewards.Bayes-optimal dynamic programming is generally computationally intractable beyond toy problems.
Motivation: OFU algorithms choose actions using optimistically biased estimates of future value.They learn when a selected action is not near-optimal because its estimate was overly optimistic.
Motivation: PSRL samples a plausible MDP from the posterior and follows its optimal policy, and computational results show it dramatically outperforms OFU algorithms.The paper aims to explain the extent and source of this performance boost.
Contributions: PSRL matches the statistical efficiency of standard OFU-RL algorithms in Bayesian expectation up to constant factors.The result motivates examining why existing OFU algorithms lose efficiency.
Contributions: ˜O(H√SAT) is established as a Bayesian regret bound for PSRL in finite-horizon episodic MDPs.Here H is the horizon, S the number of states, A the number of actions, and T the elapsed time.
Contributions: Empirical results match the paper’s theoretical predictions, while the analysis identifies a tension between OFU statistical efficiency and computational tractability.The paper argues that an equally efficient OFU algorithm would likely be computationally intractable in general.

2. Problem formulation

The paper formulates Bayesian reinforcement learning for finite-horizon episodic MDPs, defining policies, value functions, histories, regret, and Bayesian expected regret. It situates these guarantees relative to frequentist, Bayesian, and PAC analyses while limiting its formal scope to finite horizons.

2. Problem formulation: The environment is a random finite-horizon MDP with state space S, action space A, horizon H, rewards R*, transitions P*, and initial distribution ρ.At each period, the agent observes a state, selects an action, receives a reward, and transitions to a new state.
2. Problem formulation: A policy maps each state and period to an action, and its value function measures expected cumulative reward under that policy.An optimal policy maximizes the value function for the MDP.
2. Problem formulation: An RL algorithm samples an episode policy from a history-dependent distribution, with histories recording observations before and during interaction.Episodes are indexed by k and periods within episodes by h.
2. Problem formulation: Regret is defined episode by episode relative to the optimal policy for the true MDP and is random because the MDP, algorithm, transitions, and rewards are random.Bayesian expected regret averages this regret over the prior distribution of the true MDP.
2.1. Relating performance guarantees: Frequentist minimax regret bounds apply uniformly over MDPs, whereas Bayesian expected-regret bounds average over a prior and are generally weaker analytical statements.A uniform regret bound implies the corresponding Bayesian bound for priors supported on the modeled MDP class.
2.1. Relating performance guarantees: PAC analyses bound the number of ε-suboptimal decisions rather than cumulative regret.Optimal regret bounds imply optimal sample-complexity bounds, but the converse generally yields only an ˜O(T^2/3) regret bound.
2.1. Relating performance guarantees: The formal formulation focuses on finite-horizon MDPs, leaving discounted and infinite-horizon settings for future analysis.The paper suggests that some insights may carry over but does not analyze those settings.

3. Posterior sampling as stochastic optimism

Posterior sampling and optimism both select policies using statistically plausible models, but they differ in how plausibility is used. OFU maximizes over a confidence set, whereas PSRL samples one plausible MDP and optimizes within it.

Connection to optimism: Posterior sampling can be viewed as a stochastically optimistic reinforcement-learning approach.The paper uses this connection to compare PSRL with optimistic algorithms.
OFU: A typical OFU algorithm constructs a confidence set and jointly maximizes value over policies and MDPs in that set.The resulting policy is followed throughout the episode.
PSRL: PSRL samples one statistically plausible MDP from the posterior and computes its optimal policy before acting for the episode.Its episode loop then follows that policy while updating the observation history.
Analysis strategy: Optimistic-algorithm analyses design confidence sets intended to contain the true MDP with probability at least 1−δ.They then use optimism and concentration arguments to control regret.

2. Decompose the regret in each episode

The regret analysis compares PSRL with optimistic algorithms through stochastic optimism and posterior matching. This yields a general Bayesian-regret relationship and explains why PSRL can retain OFU-level statistical scaling without inheriting OFU confidence-set computation.

3. Decompose the regret in each episode: The analysis treats the imagined optimistic MDP as an auxiliary object and uses its value to decompose episode regret.On the event that the true and imagined MDPs lie in the confidence set, the optimistic regret contribution is nonpositive.
3. Decompose the regret in each episode: The proof controls concentration error by applying concentration results over possible observation trajectories.This is the standard pigeonhole step in the optimistic-analysis recipe.
3. Posterior sampling as stochastic optimism: Stochastic optimism orders random variables through expectations of convex increasing functions.The relation is written X ≽so Y and is connected to second-order stochastic dominance.
3. Posterior sampling as stochastic optimism: PSRL’s sampled value function is stochastically optimistic for the true optimal value function conditional on any history.This observation links posterior sampling to the Bayesian regret of optimistic algorithms.
Theorem 1: Theorem 1 states that PSRL matches any comparable OFU-RL algorithm in Bayesian expected regret, subject to the stated proof structure.The theorem generalizes an earlier special-case result for UCRL2.
Theorem 1: PSRL performs within a factor of 2 of optimistic algorithms including UCRL2, UCFH, and MORMAX under the theorem’s conditions.The proof uses the conditional identity in distribution between the true MDP and the sampled MDP.
Computational consequence: PSRL separates algorithm performance from confidence-set analysis and costs no more computationally than solving one known MDP.This remains true even when the matched OFU algorithm is computationally intractable.

4. Some shortcomings of existing OFU-RL

Existing OFU-RL algorithms can lose statistical efficiency through loose confidence-set construction, with inefficiencies scaling in S and H. Computational illustrations show UCRL2's estimates becoming mis-calibrated while PSRL remains stable, and tighter OFU confidence sets do not change the fundamental scaling.

Loose confidence sets are identified as the source of statistical inefficiency in existing OFU algorithms.The paper questions whether confidence sets that are simultaneously efficient in S and H can be made computationally tractable.
Scaling with S: Naive Monte Carlo estimates concentrate at 1/2 ± ˜O(1/√n), but UCRL confidence sets become increasingly mis-calibrated as S grows.The example uses A=1, H=2, and S=2N+1.
Scaling with S: Independent state-action bounds form rectangular confidence sets whose corners can be far too optimistic when combined across S estimates.The paper contrasts these corners with the underlying distribution's elliptical geometry.
Scaling with H: Algorithms addressing loose dependence on S through data partitioning incur poor dependence on the horizon H.The paper uses a separate toy example to explain why independently optimistic estimates combined through time loosen H dependence.
Computational illustration: In the computational illustrations, OFU estimates become extremely mis-calibrated while PSRL remains stable, and loose confidence sets produce extremely poor regret performance.Figure 5 shows this issue even when transition dynamics are entirely known.

5. Better optimism by sampling

The paper derives tighter Bayesian regret bounds for PSRL, explains their statistical and computational advantages over OFU methods, and tests these predictions empirically.

5. Better optimism by sampling: ˜O(H√SAT) Bayesian regret is established for PSRL, improving the previous ˜O(HS√AT) bound for reinforcement learning algorithms.The result applies to finite-horizon episodic MDPs with independent Dirichlet transition priors.
5.2. From H to √: The analysis suggests PSRL may achieve ˜O(HSAT) regret, although this tighter bound remains a conjecture.The conjecture is described as potentially matching lower bounds up to logarithmic factors, while the relevant lower-bound argument remains unresolved for the analyzed Bayesian setting.
5.1. From S to √: The analysis reduces the dependence on S by showing transition-estimation contributions concentrate at a rate independent of S.The proof uses stochastic optimism and Gaussian–Dirichlet concentration, then extends the argument from two-state MDPs through marginal Beta distributions.
5.2. From H to √: Gaussian PSRL satisfies the proof of the established theorem but not the argument supporting the tighter conjectured bound.This separates the theorem’s proof technique from the additional structure believed necessary for improved horizon dependence.
5.3. An empirical investigation: In experiments, PSRL outperforms Gaussian PSRL, which outperforms UCRL2, with differences increasing with chain length and PSRL becoming many orders more efficient than UCRL2.Experiments used ten random seeds and chain sizes N=2,…,100, with selected regret curves reported for N∈{5,10,30,50}.

6. Conclusion

PSRL combines statistical efficiency with the computational cost of solving a known MDP, while the analyzed finite tabular setting is not representative of most practical problems.

PSRL is orders of magnitude more statistically efficient than UCRL while retaining the same computational cost as solving a known MDP.The paper presents posterior sampling as a computationally tractable approach to statistically efficient exploration.
The finite tabular setting is not a reasonable model for most problems of interest because practical reinforcement learning requires generalization between states and actions.The authors frame the tabular analysis as a way to expose shortcomings of efficient-RL approaches and motivate exploration with generalization.

A. Proof of Lemma 3

The proof of Lemma 3 establishes transition concentration for Dirichlet posterior samples by reducing the relevant random variable to matched Beta and Gaussian variables under stochastic optimism.

The proof extends the two-state argument to general MDPs by inductively considering each component of the sampled transition vector.Each component's contribution is compared with a matched Gaussian random variable.
Lemma 3 analyzes transition concentration for independent Dirichlet transition priors with bounded rewards and additive sub-Gaussian noise.The lemma asserts a high-probability concentration result for the transition contribution.
A Beta random variable is constructed to be stochastically optimistic for the Dirichlet-weighted value variable.The construction preserves the conditional mean while producing a mean-preserving spread.
The Dirichlet construction uses Gamma-variable coupling to represent the relevant transition probability through a ratio of independent Gamma variables.This coupling supports the Beta-versus-Dirichlet dominance argument.
Gaussian tail concentration completes the argument after stochastic optimism transfers the transition estimate to a matched Gaussian bound.The proof applies the Beta-versus-Dirichlet relation, the stochastic-optimism comparison, and Gaussian concentration in sequence.

B. Conjecture of ˜O(

The paper identifies a loose horizon dependence in its transition-error summation and conjectures that anti-correlation across timesteps could remove the extra H factor.

The current analysis sums per-timestep transition bounds independently, producing a loose contribution to the regret bound.The proof assumes each timestep can be maximally bad within one episode.
The hyper-rectangle worst-case geometry over H timesteps introduces an additional ˜O(H) term.The authors contrast this with an intended elliptical geometry.
Worst-case transitions cannot occur sequentially at every timestep because one such transition can eliminate all future value.This creates dependence across timesteps rather than independent per-timestep errors.
The transition effects exhibit an anti-correlation property through the law of total variance, suggesting that combining Lemma 3 with finite-horizon analyses could remove both H factors.The resulting improvement is presented as a conjectural direction rather than a completed bound.
The informal argument does not apply to Gaussian PSRL because its sampled transition contribution does not satisfy the Bellman operators.Empirical results are described as consistent with the conjecture in domains where the algorithms exhibit distinct predicted scalings.

C. Estimation experiments

The experiments evaluate several exploration algorithms in a two-action finite-horizon decision problem, finding poor scaling for optimism-based methods as successor-state count or horizon increases.

The decision problem has two actions, with the second action assigning probability 0.6/N to rewarding states and 0.4/N to non-rewarding states.The environment extends the paper's earlier examples to a full decision problem.
The comparison includes BEB, BOLT, ϵ-greedy, Gaussian PSRL, Optimistic PSRL, PSRL, UCFH, and UCRL2.Optimistic PSRL uses K = 10 samples and takes the maximum over sampled Q-values.
OFU algorithms show poor performance scaling with the number of successor states N when either rewards or transitions are unknown.The paper attributes this pattern to loose estimates in the corresponding figures.
As episode length H increases, UCFH improves upon UCRL2's horizon miscalibration, while BEB and BOLT scale poorly with H.The comparison is reported for the experiment corresponding to Figure 12.

D. Chain experiments

Chain experiments examine Bayesian algorithm scaling, confidence-set rescaling, prior sensitivity, and multiple-sample posterior variants. PSRL scales more gracefully than BEB and BOLT, is robust across broad prior settings, and performs similarly to optimistic PSRL at lower computational cost.

Scaling Bayesian algorithms: BOLT requires S-times more computational cost than PSRL or BEB and can perform poorly in highly stochastic environments, while neither BOLT nor BEB scales as gracefully as PSRL.BOLT comes close to PSRL in scaling but has the stated stochastic-environment and computational-cost drawbacks.
Confidence-set rescaling: Tighter confidence sets can sometimes improve empirical performance for optimism-driven algorithms when confidence sets are rescaled over {0.01,0.03,0.1,0.3,1}.The experiments compare several rescaling magnitudes in response to poor practical performance by provably efficient OFU algorithms.
Prior sensitivity: Gaussian PSRL and PSRL are extremely robust across several orders of magnitude of reward-precision and transition-prior settings on a chain of length N =10.Only large τ values caused problems for some seeds in this environment.
Multiple posterior samples: Optimistic PSRL performs very similarly to PSRL across several values of K, but incurs increased computational cost.The optimistic variant forms optimistic Q-values over K posterior samples, with K ≥1.
Multiple posterior samples: The authors attribute prior comparisons involving timestep-by-timestep resampling to a faulty benchmark, emphasizing that PSRL should not resample every timestep.They relate Optimistic PSRL to BOSS and note that earlier work had suggested K >1 could improve performance.