OPSRL-SSP: Optimistic Posterior Sampling for Stochastic Shortest Path with Minimax-Optimal Regret
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 , where is an upper bound on the expected cost of the optimal policy, and are the numbers of states and actions, respectively, and 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 , thereby addressing the open problem raised by Jafarnia-Jahromi et al. [19] for posterior sampling in the SSP setting.
Figures & tables
| Algorithm | Approach | Regret Bound | Horizon-Free |
|---|---|---|---|
| UC-SSP [ 32 ] | OFU | No | |
| Bernstein-SSP [ 28 ] | OFU | No | |
| ULCVI [ 13 ] | OFU | No | |
| EB-SSP [ 34 ] | OFU | Yes | |
| LCB-ADVANTAGE-SSP [ 9 ] | OFU | No | |
| SVI-SSP [ 9 ] | OFU | Yes |
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
| Notation | Meaning |
|---|---|
| state space of size | |
| action space of size | |
| physical state space including the goal state, | |
| internal augmented state space used for optimistic planning, | |
| fixed initial state | |
| absorbing goal state |
| Algorithm | RandomMDP | GridWorld |
|---|---|---|
| Q-learning ( -greedy) | ||
| LCB-ADVANTAGE-SSP | , , | , , |
| UC-SSP | ||
| Bernstein-SSP | ||
| ULCVI | , | , |
| EB-SSP |
| Method | Configuration |
|---|---|
| OPSRL-SSP | pseudo_mass , prior , |
| PSRL-SSP | default |
| ULCVI | , |
| EB-SSP | |
| LCB-ADVANTAGE-SSP | , , |
| UC-SSP |
| Method | nAUC | |
|---|---|---|
| OPSRL-SSP | ||
| PSRL-SSP | ||
| ULCVI | ||
| EB-SSP | ||
| LCB-ADVANTAGE-SSP | ||
| UC-SSP |
Reinforcement Learning
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
See all 1,852 papers