analiza aiqbench
This paper establishes that vanilla Posterior Sampling for Reinforcement Learning (PSRL) achieves minimax optimality in leading-order Bayesian regret, even under arbitrary correlated priors without structural assumptions. By resolving the coupling between sampled transition models and continuation values through an empirical reference and Bellman-based variance arguments, it proves optimal regret rates for both tabular and linear-mixture MDPs. This theoretical advance solidifies PSRL as a robust exploration method with guaranteed performance bounds across diverse prior distributions.
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}(d\sqrt{H^3K})$ rate for linear-mixture MDPs under arbitrary joint parameter priors.
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.
Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2609.33246 [cs.LG]
(or arXiv:2609.33246v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.33246 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 234 cuvinte
Subiecte conexe
Full Bayesian Reinforcement Learning via LF-IBIS
arXiv · 21 iul. 2026
The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret
arXiv · 16 oct. 2026
Agentic Monte Carlo: Simulating Reinforcement Learning for Black-Box Agents
arXiv · 6 iun. 2026
Elicitation without Backpropagation: Steering Model Behavior by Optimizing the Latent Posterior
arXiv · 22 iul. 2026