Skip to content
DraconiticResearch
Search Sources API
178,970 studies31 sourcesUpdated 20 min ago
PreprintarXiv licencearXiv

Minimax-Optimality of Posterior Sampling for Reinforcement Learning

  • Taewon Goo
  • Kihyuk Hong
Open at sourcePDFDOICite

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 Õ(√(SAH3K)) regret rate under arbitrary joint priors over rewards and transitions. The same proof principle gives the minimax Õ(d√(H3K)) rate for linear-mixture MDPs under arbitrary joint parameter priors.

Related

  1. Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
    Victor Boone, Cyrille Kone, Waris Radji +2
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  2. Nonparametric In-Context Learning under Growing Geometric Complexity: Minimax Optimality and Local Geometry-Adaptivity of Transformers
    Jaehee Seo, Jisu Kim
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  3. Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers
    Naoki Nishikawa, Taiji Suzuki
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. Minimax Regret for Sobolev Kernel-Based Reinforcement Learning
    Haichen Hu, David Simchi-Levi
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  5. Neural Actor--Critic Learning with Minimax Critics and Reflected Langevin Sampling
    Kunqi Huang, Lican Kang, Hongrui Shu +1
    arXivPreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{goo2026minimaxoptimality,
  title = {{Minimax-Optimality of Posterior Sampling for Reinforcement Learning}},
  author = {Taewon Goo and Kihyuk Hong},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.33246},
  eprint = {2609.33246},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.33246},
}
RIS
TY  - UNPB
TI  - Minimax-Optimality of Posterior Sampling for Reinforcement Learning
AU  - Taewon Goo
AU  - Kihyuk Hong
PY  - 2026
DA  - 2026/09/27
PB  - arXiv
DO  - 10.48550/arxiv.2609.33246
UR  - https://arxiv.org/abs/2609.33246
AB  - 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 Õ(√(SAH^3K)) regret rate under arbitrary joint priors over rewards and transitions. The same proof principle gives the minimax Õ(d√(H^3K)) rate for linear-mixture MDPs under arbitrary joint parameter priors.
ER  -