Posterior sampling closes the gap in stochastic shortest path: OPSRL-SSP drops the extra factor in PSRL-SSP's regret
Synopsis
Online learning for stochastic shortest path (SSP), a reinforcement-learning framework with a unique absorbing goal and expected cumulative cost as the objective, already had a posterior-sampling method, PSRL-SSP, but its regret bound carried an extra factor over the minimax lower bound. OPSRL-SSP augments the state space with a pseudo-state assigned an optimistic boundary value, draws posterior candidates on a logarithmic time-dependent schedule, and adaptively inflates Dirichlet pseudo-counts, so that every state-action pair has an optimistic transition candidate at every epoch start with high probability. The resulting high-probability regret bound has leading term , matching the minimax lower bound, and a cost-perturbation argument extends the analysis to zero-cost SSPs.
Interpretation
Stochastic shortest path now has a posterior-sampling algorithm whose leading regret term is of the same order as the minimax lower bound, , where bounds the optimal policy's expected cost, and are the numbers of states and actions, and is the number of episodes. Previously, PSRL-SSP on the posterior-sampling route performed well empirically but its regret bound retained an extra factor relative to the minimax lower bound, the open question raised by Jafarnia-Jahromi et al. The bound holds with probability at least , and its lower-order state-complexity term matches the level achieved by optimism-in-the-face-of-uncertainty (OFU) algorithms such as EB-SSP and SVI-SSP.
Optimism is injected through structural changes to posterior sampling rather than through explicit confidence sets or exploration bonuses. Optimistic posterior sampling for finite-horizon episodic MDPs relies on a known horizon, whereas SSP episodes have random and potentially unbounded lengths, ruling out static sampling schedules. The algorithm runs in epochs split by two stopping conditions, count doubling and an increase in the number of episodes, and solves a stationary Bellman fixed point on the augmented state space.
The pseudo-state gives every sampled model positive probability of transitioning to a virtual boundary, making the optimistic Bellman operator on the augmented space a strict contraction and lifting one-step optimism to global anytime optimism. Cost minimization requires a different optimistic-prior construction from reward maximization; the pseudo-state rewrites low-cost optimism as a tail event for an auxiliary function. On fixed RandomMDP and GridWorld instances, OPSRL-SSP performs comparably to ULCVI, SVI-SSP, EB-SSP and PSRL-SSP, and outperforms LCB-ADVANTAGE-SSP and -greedy Q-learning.
Perspective
The result concerns tabular stochastic shortest path: finite states and actions, a known cost function, an unknown transition kernel, and a known upper bound on the optimal policy's expected cost; experiments cover two fixed instances, RandomMDP and GridWorld, plus 20 independently generated RandomMDP instances with 20 rollouts each.
The algorithm currently requires knowledge of , and removing that requirement is listed as future work; the theoretically prescribed logarithmic sample count and dynamic pseudo-counts are conservative, the practical implementation uses small fixed hyperparameters, and ablations show that increasing the number of posterior samples slightly raises cumulative regret while the optimistic prior strength shows a U-shaped trade-off.
