Stochastic shortest path with sparse adversarial costs

Preprint

We study the adversarial Stochastic Shortest Path (SSP) problem with sparse costs under full-information feedback. In the known transition setting, existing bounds based on Online Mirror Descent (OMD) with negative-entropy regularization scale with $\sqrt{\log(SA)}$, where $SA$ is the size of the state-action space. While we show that this is optimal in the worst-case, this bound fails to capture the benefits of sparsity when only a small number $M \ll SA$ of state-action pairs incur cost. In fact, we also show that the negative-entropy is inherently non-adaptive to sparsity: it provably incurs regret scaling with $\sqrt{\log(S)}$ on sparse problems. Instead, we propose a family of $\ell_{r}$-norm regularizers ($r \in (1,2)$) that adapts to the sparsity and achieves regret scaling with $\sqrt{\log(M)}$ instead of $\sqrt{\log(SA)}$. We show this is optimal via a matching lower bound, highlighting that  captures the effective dimension of the problem instead of $SA$. Finally, in the unknown transition setting the benefits of sparsity are limited: we prove that even on sparse problems, the minimax regret for any learner scales polynomially with $SA$.

Authors: Johnson, E; Rumi, A; Pike-Burke, C; Rebeschini, P

• Publication status: Published
• Peer review status: Not peer reviewed
• Preprint server: arXiv
• Publication date: 2025-11-01
• DOI: 10.48550/arXiv.2511.00637
• EISSN: 2331-8422
• Language: English