Research map / Bandits and online learning / RL theory and MDPs
Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms 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 implicit finite-horizon approximation in analysis rather than explicitly implementing the horizon reduction | SSP regret-minimization template · Stochastic Shortest Path | regret bound | Helped |
| Use sparse one-step planning updates instead of full planning | SVI-SSP · Stochastic Shortest Path | time complexity: \tilo{\nicefrac{B_\star S^2A}{\cmin}} vs. \tilo{\nicefrac{B_\star^2S^5A}{\cmin^2}} | Helped |
| Remove the reference-advantage second update (ablation) | LCB-Advantage-SSP · Stochastic Shortest Path | regret bound: \sqrt{H} | Hurt |
| Update the reference value function only once instead of repeatedly (ablation) | LCB-Advantage-SSP · Stochastic Shortest Path | reference-value regret cost: \tilO{\frac{B_\star^2H^3S^2A}{\rho}} vs. \tilO{\frac{B_\star^2H^3S^2A}{\rho^2}} | Hurt |
| Use the less frequent initial update schedule rather than updating on each of the first H visits (ablation) | SVI-SSP · Stochastic Shortest Path | lower-order regret term: poly(H) | Hurt |
| Clip costs to epsilon when the minimum cost is unknown or zero (ablation) | LCB-Advantage-SSP · Stochastic Shortest Path with unknown or zero minimum cost | regret bound: \tilO{K^{4/5}} | Hurt |
| Use naive epsilon-greedy exploration with vanilla Q learning instead of LCB-Advantage-SSP | SSP model-free learning · Experiments | convergence rate | Hurt |
| Use SVI-SSP rather than other model-based algorithms | SSP model-based learning · Experiments | time spent in updates | Helped |
Closest papers by meaning
- Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret (NeurIPS 2021 · similarity 0.93)
- Minimax Regret for Stochastic Shortest Path (NeurIPS 2021 · similarity 0.92)
- Efficient Constraint Generation for Stochastic Shortest Path Problems (AAAI 2024 · similarity 0.87)
- Stochastic Shortest Path with Sparse Adversarial Costs (NeurIPS 2025 · similarity 0.87)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.86)
- Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems (NeurIPS 2025 · similarity 0.85)
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.