Stochastic Shortest Path with Sparse Adversarial Costs
Emmeran Johnson, Alberto Rumi, Ciara Pike-Burke, Patrick Rebeschini · 2025
Read Stochastic Shortest Path with Sparse Adversarial Costs by Emmeran Johnson, Alberto Rumi, Ciara Pike-Burke, Patrick Rebeschini (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00637.txt.
Introduction
Emmeran Johnson, Alberto Rumi, Ciara Pike-Burke, and Patrick Rebeschini study adversarial shortest path problems where costs are sparse. A learner repeatedly routes through a network while an adversary sets costs, and feedback is full information. Known bounds for mirror descent with negative-entropy regularization grow with the log of the whole state-action space, even when only a few pairs ever cost anything. The authors show that worst-case bound is optimal, yet blind to sparsity.
Negative entropy provably fails to adapt: its regret still scales with the log of the state count on sparse problems. A family of power-norm regularizers adapts instead, scaling with the log of the number of costly pairs, and a matching lower bound proves that optimal. With unknown transitions, though, sparsity stops helping: minimax regret grows polynomially with the full space regardless.
Catalog record
| CREATOR | Emmeran Johnson, Alberto Rumi, Ciara Pike-Burke, Patrick Rebeschini |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-00637
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stochastic Shortest Path with Sparse Adversarial Costs Emmeran Johnson, Alberto Rumi, Ciara Pike-Burke, Patrick Rebeschini 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 S A \sqrt{\log SA} , where S A 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 ≪ S A 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 log S \sqrt{\log S} on sparse problems. Instead, we propose a family of ℓ r \ell_{r} -norm regularizers ( r ∈ ( 1 , 2 ) r\in(1,2) ) that adapts to the sparsity and achieves regret scaling with log M \sqrt{\log M} instead of log S A \sqrt{\log SA} . We show this is optimal via a matching lower bound, highlighting that M M captures the effective dimension of the problem instead of S A 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 S A SA . 1 Department of Mathematics, Imperial College London 2 Università degli Studi di Milano 3 CENTAI Institute 4 Department of Statistics, University of Oxford 1 Introduction The Stochastic Shortest Path (SSP) problem is a fundamental model in reinforcement learning [ 1 , 32 ] , which describes tasks where an agent interacts with an environment over episodes and must reach a designated goal state within each episode while minimizing accumulated costs. This covers problems such as car navigation while trying to avoid traffic jams, or internet routing. Recently, this classical setting has been extended to the adversarial regime, where costs may vary arbitrarily between episodes [ 28 , 8 , 6 , 38 ] and the goal is to obtain theoretical guarantees robust to any cost-generation mechanism. Under full-information feedback where the full cost vector is observed after each episode and known transitions, current algorithms achieve regret bounds that scale as \mathcal{O}\left(\sqrt{DKT_{\star}\log SAT_{\star}}\right) , where D is the diameter (the smallest expected hitting time of any policy from any state), T_{\star} is the expected hitting time of the optimal policy, S is the number of states, A is the number of actions, and K is the number of episodes. These bounds are independent of any cost structure and are shown to be minimax optimal up to logarithmic factors in [ 8 ] . In SSP, the size of the state-action space SA – which we consider and refer to as the dimension of the problem – appears in the minimax regret as \sqrt{\log SA} . While in the worst-case this is unimprovable (we show this in Theorem 3.1 ), many real-world problems have costs with structural properties that may be leveraged for improved regret. A common property often considered in the statistics and machine learning literature [ 36 ] is sparsity, which can naturally arise for SSP problems. For instance, in the car navigation example, the number of traffic jams is usually much smaller than the number of roads. Motivated by this, we consider sparse SSP problems where M , the maximum number of state-action pairs with non-zero cost in an episode, can be much smaller than SA . In such scenarios, the regret bounds should capture some dependence on M , reflecting an improvement in performance on easier sparse problems as M\rightarrow 1 and recovering the standard bounds on worst-case problems as M\rightarrow SA . In fact, for the so-called experts setting 1 1 1 The experts setting is the single-state full-information feedback A -action online learning problem [ 5 , 14 ] . ( S=1 ), the minimax regret scales with {\sqrt{KMA^{-1}\log A}} instead of {\sqrt{K\log A}} in the worst-case [ 19 ] , providing a polynomial improvement in the dimension A . Furthermore, this is achieved with Online Mirror Descent (OMD) with negative entropy regularization. However for SSP where the problem dimension also includes the size of the state space S , we show that existing approaches also based on OMD with the same negative entropy regularization [ 8 ] fail to exploit sparse costs. We construct a sparse SSP problem where this algorithm suffers \sqrt{\log S} regret ( Theorem 3.1 ), providing no improvement in terms of S compared to the minimax regret for the non-sparse worst-case M=SA problem. The failure of existing SSP methods to exploit sparsity, let alone match the polynomial improvements from the experts setting, leads us to ask the following questions: Does sparsity improve the minimax-regret in the full-information feedback SSP problem? How much? We answer the first question positively for the known-transition case by designing a family of regularizers based on \ell_{r} -norms for r\in(1,2) for which we show a \mathcal{O}(\sqrt{DKT_{\star}\log MT_{\star}}) regret bound that depends logarithmically on the sparsity level M , rather than on the size of the state-action space SA , without requiring the knowledge of M in advance. This family of regularizers interpolates between the negative entropy and the squared Euclidean norm (see Section 4 ), allowing flexibility for much weaker regularization on sparse points in sparse settings and recovering existing algorithms (and guarantees) in the non-sparse setting. We show that the above \sqrt{\log M} dependence on M is unimprovable by constructing a matching lower bound. Interestingly, this establishes that the benefit of sparsity in SSP is logarithmic in SA instead of polynomial, as in the simpler experts problem, thus answering the second question. It also highlights that M plays the role of effective dimension, replacing the general dimension SA in controlling the scaling of the minimax regret. While the benefits of sparsity in SSP are only logarithmic, we emphasize that due to the often combinatorial nature of the state-action space, these improvements can be significant. For instance, in many problems the size of the state-action space grows exponentially in some parameters, while the assigned costs remain linear or even constant. This occurs in many real-world problems (e.g. [ 31 , 30 ] ) in which settings exploiting sparsity can lead to polynomial improvements. Finally, it is natural to ask whether sparsity may provide similar benefits in the unknown transition setting. However, in Theorem 5.1 , we show a lower bound with polynomial dependence on SA in a sparse SSP instance with unknown transitions. This illustrates that in the unknown transition setting the sparsity level M does not play the same role of effective dimension, and that the general dimension SA is crucial in controlling the scaling of the minimax regret polynomially, motivating our focus on the known transitions setting. In particular, this result shows that sparse problems with combinatorial state-action spaces will remain very challenging. Our results provide a complete characterisation of the benefits of sparsity in removing dimension dependence (i.e. SA ) for adversarial SSP problems under full-information feedback. 1.1 Contributions We highlight our main contributions below: