Research map / Bandits and online learning / RL theory and MDPs
Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
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 an OAFP oracle with κ_t = 9d | SSP algorithm with linear function approximation · Stochastic shortest path (SSP) | regret: R(K) = \tilde{O} \Big( \sqrt{ B_\star^3 d^3 K / c_{min} } + B_\star^{2} d^3 / c_{min}\Big) | Helped |
| Compute OAFPs by iterating the empirical Bellman operator with κ_t = 54 d t^{1/3} | SSP algorithm with linear function approximation · Stochastic shortest path (SSP) | regret: R(K) = \tilde{O} \Big( B_\star^{\frac{11}{6}} d^{\frac{3}{2}} ( K / c_{min} )^{\frac{5}{6}} + B_\star^6 d^9 c_{min}^{-5} | Helped |
| Assume all stationary policies are proper and use contraction-based OAFP iteration | End-to-end OAFP algorithm · Stochastic shortest path (SSP), all stationary policies proper | regret: R(K) & = \tilde{O} \Big( B_\star^{\frac{7}{4}} d^{\frac{3}{2}} ( K / c_{min} )^{\frac{3}{4}} N_t^{1/2} + B_\star^4 d^6 N | Helped |
| Use orthogonal features with κ_t = 9d | End-to-end OAFP algorithm · Stochastic shortest path (SSP), orthogonal features | regret: R(K) = \tilde{O} \Big( \sqrt{ B_\star^3 d^3 K / c_{min} } + B_\star^{2} d^3 / c_{min}\Big) | Helped |
| Perturb zero or vanishing costs by adding η in the empirical operator | OAFP algorithm · Stochastic shortest path with zero/vanishing costs | regret: K^{(4λ+2)/(2λ+3)} regret | Helped |
| Use κ_t scaling as t^λ with an OAFP oracle | Algorithm with OAFP oracle · Stochastic shortest path (SSP) | regret: K^{\frac{1}{2} + \lambda} | Mixed |
| Use a fixed iteration limit N_t = t^{2γ} when contraction parameters are unavailable | OAFP computation oracle · Stochastic shortest path (SSP) | regret: K^{\frac{3}{4} + \gamma} | Hurt |
Closest papers by meaning
- Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP (ICML 2022 · similarity 0.91)
- Efficient Constraint Generation for Stochastic Shortest Path Problems (AAAI 2024 · similarity 0.86)
- Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems (NeurIPS 2025 · similarity 0.86)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.85)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.85)
- Cumulative Regret Analysis of the Piyavskii–Shubert Algorithm and Its Variants for Global Optimization (AAAI 2024 · 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.