Minimax-Optimality of Posterior Sampling for Reinforcement Learning

arXiv:2609.33246v1 Announce Type: new 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}(dsqrt{H^3K}) rate for linear-mixture MDPs under arbitrary joint parameter priors.

Source: arXiv cs.LG | 2026-09-29