Posterior sampling closes the gap in stochastic shortest path: OPSRL-SSP drops the extra factor in PSRL-SSP's regret
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.