cs.LGNov 8, 2026

OPSRL-SSP: Optimistic Posterior Sampling for Stochastic Shortest Path with Minimax-Optimal Regret

Authors: Yiming Xu, Xian Wei, Cheng Chen

Organizations: MoE Engineering Research Center of HW/SW Co-design Technology and Application East China Normal University

Abstract

We study online reinforcement learning for the stochastic shortest path (SSP) problem with unknown transition dynamics. Although existing posterior-sampling methods perform well empirically on SSPs, their regret guarantees do not achieve the minimax-optimal order. We address this limitation by proposing OPSRL-SSP, an optimistic posterior-sampling algorithm for the SSP setting. The algorithm operates in epochs and uses a logarithmic, time-dependent schedule for the number of posterior samples. To induce optimism, we augment the transition model with a pseudo-state assigned an optimistic boundary value. We establish a high-probability regret bound of O~(B⋆SAK+B⋆S2A)\tilde{O}(B_\star \sqrt{SAK} + B_\star S^2 A), where B⋆B_\star is an upper bound on the expected cost of the optimal policy, SS and AA are the numbers of states and actions, respectively, and KK is the number of episodes. In addition, we extend the analysis to general zero-cost SSPs using a universal cost-perturbation argument. The leading term matches the minimax lower bound Ω(B⋆SAK)Ω(B_\star \sqrt{SAK}), thereby addressing the open problem raised by Jafarnia-Jahromi et al. [19] for posterior sampling in the SSP setting.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Apr 17, 2026

Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model

We study the sample complexity of learning an εε-optimal policy in the Stochastic Shortest Path (SSP) problem. We first derive sample complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with SS states, AA actions, minimum cost cmin⁡c_{\min}, and maximum expected cost of the optimal policy over all states B⋆B_{\star}, where any algorithm requires at least Ω(SAB⋆3/(cmin⁡ε2))Ω(SAB_{\star}^3/(c_{\min}ε^2)) samples to return an εε-optimal policy with high probability. Surprisingly, this implies that whenever cmin⁡=0c_{\min} = 0 an SSP problem may not be learnable, thus revealing that learning in SSPs is strictly harder than in the finite-horizon and discounted settings. We complement this lower bound with an algorithm that matches it, up to logarithmic factors, in the general case, and an algorithm that matches it up to logarithmic factors even when cmin⁡=0c_{\min} = 0, but only under the condition that the optimal policy has a bounded hitting time to the goal state.
Sep 27, 2026

Minimax-Optimality of Posterior Sampling for Reinforcement Learning

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 O~(SAH3K)\widetilde{O}(\sqrt{SAH^3K}) regret rate under arbitrary joint priors over rewards and transitions. The same proof principle gives the minimax O~(dH3K)\widetilde{O}(d\sqrt{H^3K}) rate for linear-mixture MDPs under arbitrary joint parameter priors.
Jun 3, 2026

Bayesian learning for the stochastic shortest path problem

Sequential decision-making problems are often modelled as a Markov decision process (MDP). We focus on the stochastic shortest path (SSP) problem, which is an infinite-horizon undiscounted MDP with absorbing terminal states. We develop a Bayesian framework to learn the optimal decision strategy through interactions with the decision-making task. Specifically, we learn the optimal action-value function Q∗Q^*, but unlike many existing Bayesian approaches, we do not rely on unrealistic modelling assumptions and ad-hoc approximations. Our approach is to directly construct the posterior beliefs for Q∗Q^* through Bellman's optimality equations. For deterministic rewards, we characterise the posterior as a distribution with a manifold density. To facilitate simpler inference, we relax the likelihood so that a Lebesgue density exists. The flip side is to create unidentifiability issues. Specifically, the relaxed posterior can have significant mass on improper decision rules, while the exact posterior will not. We also calculate the exact posterior probabilities for optimal action selections for the tabular parametrisation of Q∗Q^*, a Gaussian likelihood relaxation and a Gaussian prior, which is useful in benchmarking studies. Numerical studies on variants of the Deep Sea benchmark verify our findings. We demonstrate that our framework faithfully quantifies uncertainty and, compared to other temporal-difference-based Bayesian methodologies, is more data efficient. We conclude with recommendations for future work.