The paper proves that vanilla posterior sampling for (PSRL) achieves minimax optimal regret without any structural assumptions on the prior distribution over MDP parameters. This resolves a long-standing open question. The result holds for tabular MDPs with unknown stochastic rewards and for linear-mixture MDPs. For tabular, time-inhomogeneous MDPs with S states, A actions, horizon H, and K episodes, the regret is O~(sqrt(SAH^3 K)). For linear-mixture MDPs with parameter dimension d, the regret is O~(d sqrt(H^3 K)). Both rates match the minimax lower bounds, establishing optimality. The key technical innovation is a new analysis that handles the coupling between posterior-sampled transition models and their continuation values using a common empirical transition reference and a Bellman-based variance argument.
Unmodified posterior sampling achieves minimax regret in reinforcement learning
For tabular and linear-mixture MDPs, vanilla PSRL attains the minimax regret rate without structural assumptions on the prior.
In one line
Posterior sampling for reinforcement learning is minimax optimal without structural prior assumptions.
Before you read this
An idea this paper builds onRead it as
Goo and Hong prove that exact vanilla posterior sampling for reinforcement learning (PSRL) is minimax optimal in leading-order Bayesian regret for finite-horizon time-inhomogeneous tabular MDPs with unknown stochastic rewards, achieving the rate Õ(√(SAH³K)).
The authors studied the Bayesian regret of unmodified posterior sampling for (PSRL) in finite-horizon, time-inhomogeneous Markov decision processes.
How it works
before and afterThe Daily Edition
The front page in your inbox each weekday morning: the lead, the picks, and why each one earned its place.