Research map / Bandits and online learning / RL theory and MDPs

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

NeurIPS 2026 · Bandits and online learning › RL theory and MDPs · approach: Stochastic shortest path

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes OPSRL-SSP, an optimistic posterior sampling algorithm for online reinforcement learning in stochastic shortest path problems with unknown transitions, claimed to achieve minimax-optimal regret.

Problem

Online reinforcement learning for stochastic shortest path (SSP) with unknown transition dynamics; standard posterior sampling lacks an explicit mechanism for uniform optimism and so does not attain minimax-optimal regret.

Approach

Adds an explicit optimism mechanism to posterior sampling for SSP, operating in epochs with a logarithmic-type component, yielding the first optimistic posterior sampling algorithm for SSP with minimax-optimal regret.

Key results

• Claims OPSRL-SSP is the first optimistic posterior sampling algorithm for SSP and attains minimax-optimal regret.

Experimental setup

Metrics: regret

Baselines: standard posterior sampling for SSP

Builds on: posterior sampling for reinforcement learning

Closest papers by meaning

• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret (NeurIPS 2021 · similarity 0.93)
• Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees (NeurIPS 2022 · similarity 0.92)
• NeoRL: Efficient Exploration for Nonepisodic RL (NeurIPS 2024 · similarity 0.89)
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.89)
• SOMBRL: Scalable and Optimistic Model-Based RL (NeurIPS 2025 · similarity 0.89)
• Minimax Optimal Reinforcement Learning with Quasi-Optimism (ICLR 2025 · similarity 0.88)