Research map / Bandits and online learning / RL theory and MDPs
Minimax Regret for Stochastic Shortest Path
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a finite-horizon reduction with ULCVI instead of the prior SSP regret approach | Online SSP · Stochastic Shortest Path (SSP) | regret upper bound: \widetilde O(B_\star |S| \sqrt{|A| K}) -> \widetilde O(\sqrt{(B_\star^2 + B_\star) |S| |A| K}) | Helped |
| Use the proposed bound for B_star < 1 | Online SSP · Stochastic Shortest Path (SSP), B_star < 1 | regret rate: \widetilde O(\sqrt{(B_\star^2 + B_\star) |S| |A| K}) versus \Omega(\sqrt{B_\star |S| |A| K}) | Helped |
| Restart a finite-horizon episode every H steps rather than run one finite-horizon episode per SSP episode | SSP-to-finite-horizon reduction · Stochastic Shortest Path (SSP) | regret dependence on state-space size: removes the extra \sqrt{|S|} factor | Helped |
| Bound regret using optimal expected cost rather than horizon length | ULCVI · Finite-horizon MDP | leading regret dependence: leading term depends polynomially on B_\star and only logarithmically on H | Helped |
Closest papers by meaning
- Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret (NeurIPS 2021 · similarity 0.97)
- Near-optimal Regret Bounds for Stochastic Shortest Path (ICML 2020 · similarity 0.95)
- Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP (ICML 2022 · similarity 0.93)
- Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback (ICML 2025 · similarity 0.88)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · similarity 0.88)
- Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.