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

CardsList
  1. Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model

    Apr 17, 2026Jean Tarbouriech, Matteo Pirotta, Michal Valko +1Markov Decision ProcessesPolicy Learning

  2. Bayesian learning for the stochastic shortest path problem

    Jun 3, 2026Chon Wai Ho, Sumeetpal S. Singh, Jiaqi GuoMarkov Decision ProcessesReinforcement Learning