Minimax-Optimality of Posterior Sampling for Reinforcement Learning

Taewon Goo; Kihyuk Hong

cs.LGSep 27, 2026

Minimax-Optimality of Posterior Sampling for Reinforcement Learning

Authors: Taewon Goo, Kihyuk Hong

Organizations: KAIST

Abstract

Posterior sampling for reinforcement learning (PSRL) is one of the simplest and most effective exploration methods, but a basic question has remained open: does unmodified PSRL achieve minimax regret without structural assumptions on the prior? We answer yes. Exact vanilla PSRL is minimax optimal in leading-order Bayesian regret under arbitrary correlated priors. The difficulty is that a posterior-sampled transition model is coupled with its own continuation value. We overcome this with a common empirical transition reference that isolates the resulting value mismatch and a Bellman-based variance argument that controls it without an extra leading-order state-space factor. For finite-horizon, time-inhomogeneous tabular MDPs with unknown stochastic rewards, this yields the minimax $\widetilde{O}(\sqrt{SAH^3K})$ regret rate under arbitrary joint priors over rewards and transitions. The same proof principle gives the minimax $\widetilde{O}(d\sqrt{H^3K})$ rate for linear-mixture MDPs under arbitrary joint parameter priors.

Figures & tables

Work	Time	Prior	Rewards	Bayesian regret	Comparison
Tabular MDPs
Osband et al. [20]	Homog.	Arbitrary	Unknown stochastic	$\widetilde{O}(S\sqrt{AH^{3}K})$	gap $\sqrt{SH}$
Osband and Van Roy [22]	Homog.	Independent Dirichlet rows	Independent reward prior; sub-Gaussian noise	$\widetilde{O}(\sqrt{SAH^{3}K})$	gap $\sqrt{H}$
Moradipari et al. [19]	Inhomog.	Independent stages/components; consistency and occupancy assumptions	Unknown; independent of transitions	$\widetilde{O}(\lambda H\sqrt{SAK})+T_{0}$	worst-case gap $\sqrt{H}$ $T_{0}$ prior-dependent
This work	Inhomog.	Arbitrary joint	Unknown stochastic	$\boldsymbol{\widetilde{O}(\sqrt{SAH^{3}K})}$	minimax
Linear-mixture MDPs

Table 1: Selected Bayesian regret guarantees for exact vanilla PSRL over

K

episodes of horizon

H

, with

S

states,

A

actions, parameter dimension

d

, and logarithmic factors suppressed. Comparisons use the corresponding minimax rates:

\widetilde{\Theta}(\sqrt{SAH^{2}K})

for homogeneous tabular MDPs,

\widetilde{\Theta}(\sqrt{SAH^{3}K})

for time-inhomogeneous tabular MDPs, and

\widetilde{\Theta}(d\sqrt{H^{3}K})

for linear-mixture MDPs [ 5 , 9 , 31 , 33 ] . For [ 19 ] ,

\lambda\leq H+1

is a prior-dependent value diameter and

T_{0}

a prior-dependent burn-in; their result also requires sufficiently large

K

. Linear-mixture rows use the standard bounded-feature and bounded-parameter assumptions.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 1 — Figure 1: At stage one the MDP moves uniformly from $s_{0}$ to an intermediate state $s_{j}$ . At stage two, the unique optimal action $a_{j}^{\star}$ transitions to $g$ and every other action transitions to $b$ .

Explore similar work

Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces
Mar 9, 2026Hamish Flynn, Joe Watson, Ingmar Posner +1RL Control Regret Minimization in RL
Carnegie Mellon University · University of Oxford · Technical University of Darmstadt +2
Bayesian Learning in Episodic Zero-Sum Games
Mar 21, 2026Chang-Wei Yueh, Andy Zhao, Ashutosh Nayyar +1Zero-Sum Games Bayesian RL
Department of Electrical and Computer Engineering at the University of Southern California
Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers
Oct 6, 2026Naoki Nishikawa, Taiji SuzukiReward Modeling Transformer-Based RL
The University of Tokyo, RIKEN AIP

Mar 9, 2026J/K move · Enter open · S save

Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces

Hamish Flynn, Joe Watson, Ingmar Posner, Jan Peters

Carnegie Mellon University · University of Oxford · Technical University of Darmstadt+2

RL Control Regret Minimization in RL Reinforcement Learning Bayesian RL Gaussian Processes Posterior Sampling

Open paper AskPDF arXiv

We analyze the Bayesian regret of the Gaussian process posterior sampling reinforcement learning (GP-PSRL) algorithm. Posterior sampling is a heuristic for decision-making under uncertainty that has been used to develop successful algorithms for a variety of continuous control problems. However, theoretical work on GP-PSRL is limited. All known regret bounds either have a sub-optimal growth rate, require strong smoothness assumptions, or fail to properly account for the fact that the set of possible system states is unbounded. Through a recursive application of the Borell-Tsirelson-Ibragimov-Sudakov inequality, we show that, with high probability, the states actually visited by the algorithm are contained within a ball of near-constant radius. We then use the chaining method to control the regret suffered by GP-PSRL under weak smoothness conditions. Our main result is a Bayesian regret bound of the order

\widetilde{\mathcal{O}}(H\sqrt{γ_TT})

, where

H

is the horizon,

T

is the number of time steps and

γ_T

is the expected information gain. With this result, we resolve the limitations with prior theoretical work on PSRL, and provide the theoretical foundation and tools for analyzing PSRL in complex settings.

Abstract

Explore similar work

Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces

Bayesian Learning in Episodic Zero-Sum Games

Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers