Posterior sampling achieves optimal exploration rates in reinforcement learning
Minimax-Optimality of Posterior Sampling for Reinforcement Learning
Machine Learning
Summary
Reinforcement learning helps computers learn to make decisions through trial and error. One popular method, posterior sampling, was simple but it wasn’t clear if it worked as well as possible in the most general situations. The authors show that this method actually does achieve the best possible performance in terms of learning speed and decision quality, even with complex prior knowledge. They used mathematical tools to carefully analyze why it works so well, confirming its effectiveness without extra assumptions.
What this means in practice
- •For reinforcement learning engineers: Design reinforcement learning agents with assured best-case learning speed using vanilla posterior sampling under general priors.
- •For autonomous robotics teams: Build exploration strategies in robots that have theoretical guarantees on efficiency without needing restrictive assumptions about the environment.
A theory result. No direct application yet.
Authors
Taewon Goo, Kihyuk Hong
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.