Research map / Bandits and online learning / Online convex optimization and games
Stochastic Shortest Path with Sparse Adversarial Costs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that negative-entropy OMD fails to exploit sparsity in adversarial SSP with known transitions, proposes an l_r-norm-based (r in (1,2)) regularizer achieving sqrt(log M) regret with matching lower bound, and shows sparsity does not remove polynomial SA dependence under unknown transitions.
Problem
Minimax regret of adversarial stochastic shortest path with sparse costs under full-information feedback, where the regret dimension is SA; whether sparsity (M nonzero costs per episode) can reduce dependence on SA in known and unknown transition settings.
Approach
Replace the negative-entropy regularizer in OMD with a parameterized family psi_p(q) = p(-1 + sum |q|^{1+1/p}) that interpolates between squared Euclidean and negative entropy; with p tuned to log(TM) it yields regret depending on log M instead of log SA, and negative entropy is shown to inherently fail on sparse instances.
Key results
- OMD with the l_r-type regularizer achieves regret O(sqrt(DKT log(MT))) in the known-transition setting, with a parameter-free variant adding only a T_star term.
- A matching lower bound Omega(sqrt(K T_star D log M)) holds for general sparse SSP, giving optimal sqrt(log SA) dependence in the non-sparse case.
- Negative-entropy OMD suffers Omega(sqrt(K log S)) regret even with sparsity M=3.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the ℓr-norm regularizer ψp instead of negative entropy | OMD for known-transition SSP with sparse costs · Known-transition SSP, M-sparse costs | regret dependence on dimension: √log SA -> √log M | Helped |
| Use negative-entropy regularization on an SSP with M = 3 | OMD for known-transition SSP · Known-transition SSP, M = 3 | regret dependence on state count: Ω(min{√(K log S), K}) | Hurt |
| Make transitions unknown, even with M = 1 | SSP learner · Unknown-transition SSP, M = 1 | regret dependence on state-action space: Ω(D√(SAK)) | Hurt |
Surprising findings
- Negative entropy, the standard regularizer in SSP OMD, provably fails to adapt to sparsity, incurring sqrt(log S) regret even when M=3.
- In the unknown transition setting, even sparse problems with M=1 suffer regret polynomial in SA (Omega(D sqrt(SAK))).
Limitations
- Benefits of sparsity under known transitions are only logarithmic in SA.
- Analysis restricted to adversarial full-information feedback; bandit, stochastic and partial feedback not treated.
- Lower bound for general sparse case requires M at least about 100 and K large enough.
Experimental setup
Metrics: regret
Baselines: OMD with negative entropy regularization
Builds on: online mirror descent negative entropy OMD for SSP
Closest papers by meaning
- Online Composite Optimization Between Stochastic and Adversarial Environments (NeurIPS 2024 · similarity 0.88)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.87)
- Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback (NeurIPS 2024 · similarity 0.87)
- A Single-Step, Sharpness-Aware Minimization is All You Need to Achieve Efficient and Accurate Sparse Training (NeurIPS 2024 · similarity 0.86)
- Parameter-free Algorithms for the Stochastically Extended Adversarial Model (NeurIPS 2025 · similarity 0.86)
- The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations (ICML 2025 · similarity 0.86)
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.