Stochastic shortest path with sparse adversarial costs
File(s)
Accepted version
Author(s)
Johnson, Emmeran
Rumi, Alberto
Pike-Burke, Ciara
Rebeschini, Patrick
Type
Conference Paper
Abstract
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 ?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 ! 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 ?log S on sparse problems. Instead, we propose a family of ℓr -norm regularizers (r P p1, 2q) that adapts to the sparsity and achieves regret scaling with ?log M instead of ?log SA. We show this is
optimal via a matching lower bound, highlighting that M 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.
optimal via a matching lower bound, highlighting that M 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.
Date Issued
2025-12-02
Date Acceptance
2025-09-18
Citation
Advances in Neural Information Processing Systems, 2025, 38, pp.124859-124900
ISSN
1049-5258
Publisher
Curran Associates, Inc.
Start Page
124859
End Page
124900
Journal / Book Title
Advances in Neural Information Processing Systems
Volume
38
Copyright Statement
© 2025 Neural Information Processing Systems Foundation, Inc. (NeurIPS).
Source
Neural Information Processing Systems (NeurIPS 2025)
Publication Status
Published online
Start Date
2025-12-02
Finish Date
2025-12-07
Coverage Spatial
San Diego, CA, USA