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

We consider online reinforcement learning for the Stochastic Shortest Path (SSP) problem with unknown transition dynamics. Since standard posterior sampling in SSP lacks an explicit mechanism to enforce uniform optimism and therefore fails to attain minimax-optimal regret, we propose OPSRL-SSP, the first optimistic posterior sampling algorithm for the SSP problem. The algorithm operates in epochs and uses a logarithmic, time-dependent posterior sampling schedule. To ensure optimism, it incorporates a pseudo-state with an optimistic value evaluation into the posterior distribution. We establish a high-probability regret bound of $\tilde{\mathcal{O}}(B_{\star }\sqrt{SAK}+B_{\star }{S}^{2}A)$, where $B_{\star }$ is an upper bound on the expected cost of the optimal policy, $S$ and $A$ are the numbers of states and actions, respectively, and $K$ is the number of episodes. The key technical challenge is to turn these optimistic posterior samples into a uniform optimism guarantee despite the random and potentially unbounded episode lengths of SSP. We address this through an SSP-specific analysis based on dynamic posterior inflation and a contraction argument over the pseudo-state-augmented model. In addition, we extend the analysis to general zero-cost SSPs via a universal cost-perturbation argument. Our dominant term matches the minimax lower bound $\Omega (B_{\star }\sqrt{SAK})$, thereby answering the open problem raised by jafarniajahromi2021onlinelearningstochasticshortest for posterior sampling in the SSP setting.