Stochastic Shortest Path with Sparse Adversarial Costs
Authors: Emmeran Johnson
Alberto Rumi
Ciara Pike-Burke
Patrick Rebeschini
Venue: NeurIPS 2025 poster ()
Keywords: SSP
sparsity
OMD
Primary area: theory
TL;DR: We study the stochastic shortest path problem with sparse adversarial costs and under known transitions characterize the minimax regret achieved by OMD with a novel $\ell_r$-norm regularizer with $r \in [1,2]$.

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 $\sqrt{\log S A}$, 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 novel 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 $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$.

Stochastic Shortest Path with Sparse Adversarial Costs
Emmeran Johnson
Alberto R 2,3*
Ciara Pike-Burke'
Patrick Rebeschini
Department of Mathematics, Imperial College London
2 Università degli Studi di Milano
CENTAI Institute
4 Department of Statistics, University of Oxford
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 y vlog 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 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 f,-norm regularizers (r (1) that adapts to the sparsity and achieves regret scaling with /log MM instead of /log SA. We show this is optimal via 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: prove that on sparse problems, the minimax regret for any learner scales polynomially with SA.
Introduction
The Stochastic Shortest Path (SSP) problem is a fundamental model in reinforcement learning 1 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 g 66 38 and the goal is to obtain theoretical guarantees robust to any cost- -est-eeerrtion 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 O (VDTT) log SAT.), where D the diameter (the smallest expected hitting time of any policy from any state), T. 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 shown to be minimax optimal up to logarithmic factors in 8
32
In SSP, the size of the state-action space SA - which we consider and refer to as the dimension the problem appears in the minimax regret as / vlog SAA. While in the worst-case this is unimprovable (we show this in Theorem 3.T). 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 navigation example, the number of traffic jams 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 episode, can be much smaller than SA.
In such scenarios, the regret bounds should capture some dependence on M, reflecting an improve- ment in performance on easier sparse problems as + 1 and recovering the standard bounds on
$ Equal contribution, corresponding author: emmeran. jw..jooooon1mmmmpriaalll uk
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

worst-case problems as M - SA. In fact, for the so-called experts setting (S 1), the minimax regret scales with v VKMA- log A instead of vK log A in the worst-case [9] providing polyno- mial 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 the state space S, we show that existing approaches also based on OMD with the same negative entropy regularization [ fail to exploit sparse costs. We construct sparse SSP problem where this algorithm suffers vlog 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 é,-norms for E (1, 2) for which we show a ((VDTT. log MT.) 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 D allowing flexibility for much weaker regularization sparse points in sparse settings and recovering existing algorithms (and guarantees) in the non-sparse setting.
We show that the above v Vlog M dependence on M is unimprovable by constructing matching lower bound. Interestingly, this establishes that the benefit of sparsity in SSP is logarithmic in S A instead of polynomial, as in the simpler experts problem, thus answering the second question. 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 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, is natural to ask whether sparsity may provide similar benefits in the unknown transition setting. However, in Theorem 5. we show a lower bound with polynomial dependence on SA in 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 S A 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. S.A for adversarial SSP problems under full-information feedback.
1.1 Contributions
We highlight our main contributions below:
We design family of f,-norm (r E (1, regularizers for OMD that allows interpolation between the negative entropy and squared Euclidean norm, adjusting its geometry to the sparsity of the cost functions (see Section 4. The regularizer naturally plugs into the standard OMD analysis.
We show OMD with the above regularizer achieves parsity-adaption regret bounds of order O (VDKT. log MT.) (Theorem 4.1). We also give parameter- free version achieving the same bound (Theorem (.44 that does not require prior knowledge of the sparsity level M nor the expected hitting time of the optimal policy T. (the only unknown parameters).
We establish lower bound of order Ω (VDKT. log M) (Theorem 4.6 matching regret
guarantees up to a logarithmic factor of T. (already present in prior work (8) and improving over g in the M S.A non-sparse setting by including the vlog SA dependence.
The experts setting is the single-state iill-information feedback A-action online learning problem 5
14

---

We show that OMD with the negative entropy used in prior work 28 8 suffers regret at least Q( DovKlog S) even when M (Theorem 3.1). This rules out the negative entropy as a viable regularizer in the sparse setting and provides justification for the use of our regularizer.
We establish that results independent of SA are not achievable in the unknown transitions setting via lower bound in the sparse (M 1) setting of order 52 (DVSAK) (Theorem 5.1
Proving these results requires new technical ideas. For the general sparse lower-bound, we derive a result on the expectation of the maximum of asymmetric zero-mi eero random walks, generalizing the result for the symmetric case from [25] The cenediiveeetroo-specciiie lower-bound relies on the careful design of an MDP with skewed initial occupancy measures that highlights both the reasons for the failure of the negative entropy well as the more general difficulty of the stochastic nature of SSP problems.
Technical Contributions:
1.2 Related works
Regret minimisation for SSP problems under full cullinforrmtion feedback was initiated by a line of 9 17.. In the adversarial setting, it was first studied by [28] in the known transition case. Their bounds were later improved by [.. There have since been
work studying stochastic costs 32 29 33
many extensions: 6 consider the unknown transition setting, (38] establish dynamic regret bounds,
10 consider a policy optimisation approach in the unknown transition setting.
Regret minimisation for SSP problems under bandit feedback where only the costs of the visited state-action pairs in an episode are revealed to the learner has also been studied both in the stochastic [10] and adversarial settings 88 [10] In the ad adversarial known transition setting, the minimax regret is of the order / sparse SSP problem with bandit feedback and understand if the regret scales with v /M instead of VSA, in which case M would play the same role of effective dimension as in the setting we consider.
(ignoring log terms) [8]. It is an interesting future direction to study the
Regret minimisation with sparse costs was studied in the classical online learning setting [19] (S = 1). The minimax regret goes from O( A) to O( D(VKMA- log A) under full- information feedback (experts problem). For rewards instead of costs, it goes from O( V(vK log A) to O(vK log M), which matches the benefits of sparsity we establish for the SSP problem with costs. Note that we restrict our focus to costs since it is unclear how to interpret rewards within the SSP framework. Under bandit feedback, the sparse minimax regret goes from Ā(VKA) to Ö(vKM) for both rewards and costs [. The above minimax regrets can also be achieved by sparse-agnostic Finally, sparsity was also considered in the case of stochastic losses by 20).
methods 19 34
2
Preliminaries
2.1
Problem setting
We consider the Stochastic Shortest Path (SSP) problem with adversarial costs. The environment along with a sequence of k=1 chosen by an oblivious adversary over K episodes. S is the state space with cardinality S = SS,, and su E S the fixed starting state. The goal state g is a special absorbing state not included in S. .A is the action space with cardinality A = |.A] and assume for simplicity that it is the same in every state. Let r = S x A denote the set of all state-action pairs. The dynamics in the MDP are given by the known transition function P, where P(s'|s, 1s, a) specifies the probability of moving to state s' E S o (g) after taking action a in state 8.
is modeled as a Markov Decision Process (MDP) M = (S, P, su. g)
cost functions {cx] K
Each episode begins in state 50 and proceeds with the learner selecting actions until the goal state g is reached. When the goal state is reached, the current episode ends and a new one begins. At the start of each episode k, the adversary selects cost function e I 10. 1]. assigning cost each state-action pair. We denote the sparsity level as M max; (s.r))rr [Tcu,(,, a) 0} the maximum number of non-zero costs in an episode. We work in the full-information setting where the entire function Ck is revealed to the learner at the end of the episode. The objective is to minimize the total cost over all episodes, which requires a balance of minimizing the accumulated costs while ensuring the goal state is reached efficiently.
We use super-scripts to denote the time-step within an episode and sub-scripts to denote the episode: e.g. (st, af) refers to the state-action pair at the 1-th time-step of the k-th episode. We sometimes omit the sub-script when referring to an arbitrary episode. We now define some important concepts:
3

---

A stationary policy is a mapping such that T(-|s) is probability distribution over the choice of action a ~ [[|ss) in state s. policy called proper it reaches the goal g in finite time from any initial state in S with probability one, and improper if not. Let pp be the set of all stationary proper policies. We assume the existence of least one proper policy.
The expected hitting time 7" (s) is the expected number of steps required to reach from state s under æ. Letting I (s) be the random number of time-steps used to reach the goal state when executing policy π in an episode starting from state 8, then 7 (*)s) B (s)]. For any proper policy म. (s) and 7 (s) are finite for all S.
The fast policy 7 is the deterministic policy that minimizes the worst-state expected hitting time, and the diameter D of the MDP is the corresponding expected hitting time:
f arg min T T*) (s),
D max T (s) seS sell,
max min T (s)s.
x
SES
SES
Since the transition function P is known, both the fast policy Ty and the diameter D can be computed offline prior to the learning process. We assume > 1.
The cost-to-go function J S [0. (0) is the expected cost suffered during episode executing policy æ and starting from state s. given a cost function c and proper policy л. defined as
(s)s)
(T(() E Σ
a'st,a')
where the expectation with respect to the randomness the action sampling and state transitions. We use J to denote the cost-to-go from the initial state so using the cost function сı in episode k.
The regret Rg is the primary measure of performance by which the learner is evaluated. difference between the total cost over all episodes of the policies ....... т chosen by the learner, and the total cost of the best proper deterministic policy in hindsight, n arg minxell, > JØ:
the
K
I (80)
K
RK =
Σ
Ch
Σ
J
The occupancy measure dr
R of proper policy is the expected number of visits to state-action pairs in an episode executing policy starting from so:
I. (e0)
In (x a) =
Ifs'= = =, = P. so
The marginal (s) = Exe (8, a) gives the expected number of visits to state Given a vector q R5 if it corresponds to valid occupancy measure, the corresponding policy Ty can be recovered via normalization as (a|s) q(s, a)/ Σ. q(s, a') [39 28
2.2 SSP as online linear optimisation and online mirror descent
Occupancy measures allow the cost-to-go be expressed in linear form:
J
Σ an (s, ((),)))(()))) (s.a)er
C4)
If the learner executes stationary proper policy Fe in episode k, the expected regret can thus be reformulated as an online linear optimisation problem on the space of occupancy measures:
E [[R]] -E-
AT..
yn Cx)
Online linear optimisation is well studied problem and can be solved using Online Mirror Descent (OMD) (see e.g. (24)). In the SSP framework, OMD is applied the space of occupancy measures corresponding to proper policies with expected hitting time bounded by some T defined as:
A(T) = q Σ ((s,0) T, Vse S: Σ (( (s,a)er
Σ (K
P(s)s' p(s(ssa')g(s'.d)) = =I(s = ss
aEA

---

The first constraint ensures the expected hitting time is bounded by T. while the second is a flow constraint ensuring the vector corresponds to the occupancy measure of a policy. The regret bounds of OMD will hold against any fixed comparator policy as long as T is large enough such that A(T) contains the occupancy measure of the optimal policy, i.c. dr* A(T) or I > T. where we denote by T. = T (sa) the expected hitting time of π.. OMD with a strictly convex differentiable regularizer sb and step-size ii selects occupancy measures computed through the update
q1
arg min (b()), gEA(T)
+++1
arg min { (g. (k) + Pp)( qEL(T))
v) is the Bregman divergence with respect to th. This update can be computed efficiently for all the regularizers we will discuss (see Appendix [B. As discussed in the previous section, we can easily recover via normalization the corresponding policy
where (1, (xx) (b()) (v
Tye that will be executed by the learner.
If the regularizer satisfies for some a any q E TR and all k: > 1:
( E [V)(g,) V(((s)) - nc*] = (ry(g)) z VV
(2)
(this is satisfied by many common regularizers), then a standard result (see e.g. Theorem 6 in Theorem 5.5 in (3) gives the following general regret bound for OMD:
(ak Ox Ck) & Mgr)) - ((a))
K
Σ
ca le
2x
Penalty
Stability
where 1qlla = E.a..' a ((s, a) A((s(s, a), (s', ('s'ss a') for matrix A e R Various regret bounds can be obtained by instantiating the above with different regularizers. In particular, g use the negative-entropy to obtain O a (VDKT. log SAT.) regret bound.
Failure of negative entropy regularization
In the general non-sparse setting, OVVDKT. log SAT.). which in the non-sparse setting has optimal dependence on SA (as we show later Theorem [4.).. Despite this success, the negative entropy fails benefit from sparsity in its dependence on S, shown by the result below. As we will see in Section 4 this establishes the negative entropy as sub-optimal choice for sparse SSP problems.
use the negative entropy to achieve a regret of
Theorem 3.1. For any > 6, there exists an SSP instance with a fixed horizon of sparsity level
M 3, action space of size A = 2 and state space of size S such that the regret of OMD 7 with negative-nntropy regularization and any step-size n > O after K episodes is E [Rk] = Mmin( log S, K)).
This result shows that despite the SSP instance being sparse (M = 3), the regret of OMD with negative entropy regularization nevertheless scales vlog S, which is the same dependence S as in the non-sparse setting. For sparse problems, the negative entropy provides no improvement on the regret with respect S. This highlights that existing approaches and regularizers are inadequate to appropriately exploit sparse problems and motivates considering alternate regularizers specifically designed for the geometry of sparse problems, as do in the next section.
To better understand the failure of negative entropy regularization in sparse settings, we highlight the main intuition behind the lower bound construction and defer the details of the proof to Appendix A
Proof intuition:
The key idea is to reduce SSP to an experts problem with 2 actions and heavily skewed initial distribution over the actions. The initial occupancy measure played by OMD in (I is arg MiT) (k))). For most regularizers, including the negative entropy, this encourages qI to be uniform across the state-action space while maintaining the constraints on the flow and expected hitting time. Since we consider a fixed-horizon MDP, only the flow constraint is relevant.
Consider the SSP problem shown in Figure I with N S - 2. Since 81, & constitute large majority of the states (especially for large N). ()()) is mainly affected by the values of in these
5

---

B1 02
80
8
Figure MDP for the reduction to skewed experts problem with 2 actions: {so, 8g. $1,..,,8 (N S 2), A {a1. a2). The transitions are given by p(syl E A, for > 1: p(=]1=0:00 02) 1/N. (1 a) 1 for all E A.
(sglss:a) a1) = 1, p(g]sg. a) for all
states. In order minimize (g)), 9I needs ensure the expected number of visits to these N states is sufficiently high. However since for any and any i > 1, g(s;) x (Ss. 02), for 41 (s;) to be sufficiently large then qı( a2) needs to be much larger (by factor of N). This results qi being heavily skewed towards in so. For the negative entropy, this gives specifically Qı (su, a1) 2 VN
If the costs in all states but so are set to O, the problem is sparse (M 2) and reduces to experts problem with 2 actions where the initial probability for the first action, which in our case 9i (80, ai), scales as L/V... The regret for OMD with the negative entropy in this setting can be shown to scale for any step-size at least as 9 K log N) Ω / log S), providing the dependence from the statement the theorem. To prove this formally for the SSP reduction, we use the above construction coupled with non-skewed reduction and careful setting of the costs. We include the details in Appendix[A]
Finally, we remark that this failure comes from the negative entropy stretching euclidean distance near the boundary of the space in such a way that two nearby points in terms of euclidean distance can be arbitrarily far in terms of negative entropy. This makes it hard for OMD to recover from the initial N increases) unless the step-size is unreasonably
occupancy measure @ı (30, a1) I/VN (- large. This property does not generalize to all regularizers and fact provides insights for designing regularizer to appropriately handle sparsity. In particular, the regularizer we consider in the next section does not suffer from the same issue because the stretching of euclidean distance is finite since its gradient does not diverge at the boundary (i.e. q(s, a) 0) unlike the negative entropy.
The benefits of sparsity
In this section, we show that it is possible to achieve regret bound of order O(V DKT. (og(MT.), where M is the maximum number of non-zero entries in the cost. This is our main result and together with the lower bound in Theorem 4.6 establishes that the sparsity level M acts as a measure of effective dimension instead of the state-action space size SA for SSP with full-information feedback.
In the previous section, we showed and discussed that the negative entropy, the regularizer used in OMD by existing methods, is inadequate to handle sparse SSP problems. Motivated by this failure, we consider alternate regularizers. However, identifying a suitable regularizer poses two key challenges. Firstly, it must work for SSP and the associated technical complexities compared to other simpler online learning problems. In particular, it needs to match the dependence in terms of the other non-sparsity--ellie relattd quantities appearing in the regret of the negative entropy (i.e. D, T., K). Second, it must explicitly leverage sparsity to improve performance. We propose the following family of regularizers parameterised by >>> 1:
(g( = (-1 [alltt//) = (-1+ Σ Σ 1g(s, 4)11+
SE ae
As 00, the regularizer Equation converges to the negative entropy. On the other hand, as p - 1, the regularizer converges to the squared Euclidean norm that enforces much weaker regularization on sparse points. Therefore, thp allows smooth interpolation between dense and sparse regimes via the tunable parameter p (see Figure 2 for comparison). In particular, tip for small p

---

0.70
Bregman Divergence
0.65
0.60
Dzy (ar 11
D (1
0.35
Du(a v)
0.50
0
20
40
100
p
Figure 2: Bregman Divergence between a deterministic distribution [0, and the uniform distribution y = [1/2, 1/2] for our regularizer Up,, squared Euclidean norm the and negative entropy H for increasing values of p.
induces an OMD update that is able to easily move to and away from the boundary of the space, making it robust the skewed initial oceupancy measure on the SSP instance which caused the failure of the negative entropy in Section 3 The parameter p also controls a trade-off between the
stability and penalty term in (3). which ultimately will enable the removal of the dependence on S.A.
Versions of this family of regularizers can be found in the convex optimization literature [8 22 As far as we are aware, its use with OMD novel. A regularizer involving an r-norm with r [1 has
been used but the norm is squared rather than to the power of (see e.g. Section 6.7 in (24). Our regularizer is also similar flavor to the Tsallis-entropy in the sense that converges to the negative entropy in the limit of its parameter.
We note that OMD with the above regularizer can be implemented efficiently for any p: the projection
step of OMD over ((T) can be written as a convex optimization problem as in (28), which can be solved efficiently (details in Appendix B).
We can now turn to our main result, which establishes regret bounds that scale with the sparsity level M for OMD with the regularizer in (4) when M known.
Theorem 4.1. Consider OMD with Up as regularizer. If is such that qu E A(T), 1
V KDMUE p = log(TM), then E [Rx] & O(VDKTlog(MTT)
pTi+1/p
We present below the outline of the proof and include the missing details in Appendix
Proof. It can shown that tip satisfies the condition 2 with a = 1, allowing us to use the bound in
3 starting point. Using that q. E A(T), we bound the Penalty term:
(p(g.) (9) (
|1..1111/// / < 1p-la-11++11
1+1/p < <p. <p-T1+1/ +1/p
(5)
can also be shown that (2) = diag p+ (-1p) Using that (x a)² & ck cx(s,,), we get
(s(
IcallG & Σ
||cx|l2 Σ
5,a |cll12 2h (s,
ca(s, a)
1-1/p
||ca|| Σ
qu (x((a))
(6)
[c*ll1
||ca|] / (ck, qb) 1-11/ & 1/ max (1 (ck, {x)} 1111 (ck, <ck,g)))
where the key step 6 uses Jensen's 's inequality on the concave function x² 1-1pp (p 1) and probability distribution / cx Plugging this into the Stability term and combining with (5)
K
nM
M/D
1/2
K
Qk q- Ck)
(k. cx)
7
2
2

---

K
TTTLi//
n/
K
9k 9 ,Ck)
E
Σ
go, (9,, Ck)
//
2
2
2
K
2ppp2+1/p
qr,, Ck)
"1
where the last step uses that > (g., Ca) E I (gxy, Ck) & K Kl4 11,,11114lee & DK, D & 1 and
p21+1/ 77 E 4/p = nM /p 2 > 1/2. Tuning 17 = KDM
1/p for sufficiently (so 17 E 4M-1/p
large K) and p log(TM) gives the result.
Provided we can suitably select T x T. (see Section 4.1 this result establishes that sparsity does
lead to an improvement in the minimax regret. In Section 4.2 we show that the dependence on M and
SA is optimal, ruling out polynomial improvements from sparsity such in the experts setting [19]. This highlights that M acts as the effective dimension of the problem instead of SA. In particular, the sparsity level M is constant, then we obtain a dimension cnmmensioon-ndeeeddenn regret of (VDDK log Tog
Remark 4.2. Although we express the bound in terms of the sparsity level M, it can be seen that the amalysis above holds more generally if M is instead an upper bound on the &g norm of the costs: M = maxe||ck 1- This relaxation allows our result cover "softly sparse" cost structures and aligns with the notion of first-order bounds commonly studied in the online learning literature [23 37 35).
Remark 4.3. The above result does not recover the M/ A polynomial improvement in the special case of the expert setting. This can be recovered through a regret bound of slightly different flavor which includes the hitting time of the uniform policy. We include the details and subtleties Appendix but the upshot is that the necessity to reach the goal state in SSP creates fundamental difference in the benefits of sparsity compared to the expert setting.
4.1 Sparse-agnostic parameter-free upper bound
The procedure in Theorem 4.4 assumes knowledge of the spansity level M to tune the parameter p of our regularizer and uses knowledge of the expected hitting time of the optimal policy T. to consider OMD over the space of suitable occupancy measures. We now adapt existing techniques to remove both of these assumptions and derive fully parameter-free guarantees.
For the unknown sparsity level, we use the same approach as in [19]. We divide the K episodes into batches. Within each batch, we independently run OMD tuning the parameter p of our regularizer with the sparsity level observed up to the current batch, described in Algorithm in Appendix C.2
For the unknown expected hitting time of the optimal policy T., we can exploit the same meta- algorithm technique as in [8). using the sparse agnostic algorithms introduced above as base learners. We run N z log K instances of Algorithm| | where the j-th instance sets its parameter T b(j) > 2 Therefore, there exists good instance j. such that b(j.) is close to the unknown T.. The regret of a scale-invariant meta-algorithm, described for completeness in Algorithm in Appendix C.2 closely matches that of this good instance.
Together, these two techniques yield the following parameter-free regret bound (proof in Ap- pendix
Theorem 4.4. K > max max(T., T. log(T.M)) and T. > e, Algorithm guarantees E [Rx] & D
Ö(VDKT. (og.T.T + T.). where the notation Ô hides double-logarithhn factors.
The leading term matches the regret bound from Theorem 4.1 while the second does not depend on M or K. Therefore, running a procedure that does not assume knowledge of M and T. comes at no additional cost in terms of the regret bound (up to double-logarithmr
factors). We also note that is common for log-log factors to be ignored in parameter free results with expert-like algorithms [12 [6]. It is also possible to obtain a bound that holds with high- probability since the high- sigbbbbbbbbbltty analysis given in [8] can casily be adapted to work with our regularizer.
Remark 4.5. The assumption K > & log(T, M) or K 3 fo (og(T.SA) in the non-sparse setting is actually non-restrictive since required for the upper-bound to be meaningful:
T.
DKT, (o) S.KKK =
K
log(T.M).
D
8

---

In particular, it is likely that there is gap between the behavior of the minimax regret between the "low- now-dimensional" setting which we study and a high higg-diimesio setting where K To log(T, The high-dimensional problem is yet to be explored, even in the non-adversarial setting and could be an interesting avenue of future research. Indeed, all prior works on SSP have implicitly studied the problem in tow-dimension, which comes with an implicit assumption that K is sufficiently large.
4.2 Lower bound
In this section, we provide a general lower bound for sparse SSP problems.
Theorem 4.6. For any D, D,T., K, S. A with T" = D 3 log S. S(A 400, K 3 5007" and M 3 101, there exists an SSP instance with stochastic M-sparse costs, states and A actions such that its diameter is D, the expected hitting time of the optimal policy is T", and the expected regret with respect to the randomness of the losses for any learner after episodes is [| > Q(VKT log M).
D log M
For general M (> 100), the lower bound matches the upper bound established in Theorem 4.1 in its dependence on M, characterizing the minimax regret for general sparse problems (up to log term). For M SA,, our result gives a (oggk lower bound improving on the ((vKTD lower bound of [8] In particular, this establishes the optimal dependence on the size of the state-action space SAA in the minimax regret for the general non-sparse SSP problem.
The proof is based on the combination of an SSP instance from [8] and proba- bilistic costs construction, which then requires some non-trivial arguments to extend to the sparse SSP problem. We give an overview of the construction and defer the details to Appendix B
Proof intuition:
The MDP construction is essentially a reduction a non-sparse experts problem with (M) actions. First, there is reduction to an experts problem with (SSA) actions. Then within these, there are O(M) good actions, while the remaining are bad. The good actions suffer small costs in expectation and can lead directly to the goal-state. The bad actions are zero-cost but all lead to the same unique bad state, where only one action leads to the goal-state and suffers high cost. This allows big proportion of the actions to be bad while still guaranteeing sparsity and forcing the learner to only consider the ((M) ) good actions, completing the reduction to the non-sparse experts problem with ((M) actions.
However, we cannot directly apply lower bounds for the experts problem because of subtleties in the reduction and the cost cost-generating mechanism. We use a similar approach to the experts lower bounds by sampling the costs i.i.d. from a Bernoulli distribution, however with a scaled parameter to ensure the reduction above holds. The regret in this stochastic environment can then be expressed as the maximum of asymmetric zero-mean i...d. random walks, capturing how much better the optimal policy can be by choosing the best action after the i.i.d. Bernoulli costs have been sampled for all episodes. The result then follows from a technical result on the expectation of this maximum that we derive in Appendix G We note that the reduction and costs are constructed in such way that the diameter of the MDP and expected hitting time of the optimal policy are indeed D and T..
5 Unknown transition setting
In this section, we consider the setting where the transitions are unknown and show through the following lower bound that the benefits of sparsity are limited.
Theorem 5.1. For any D, K, S, A with S 2.A 16, D3 2 and K 3 SA, there exists an SSP instance with M = 1, S states and A actions such that its diameter is D and the expected regret for any learner without knowledge of the transitions after K episodes is [[ > Q(DvSAA)..
The above result establishes that the minimax regret for the unknown transition setting must scale polynomially with SA, regardless of the sparsity. In particular, this highlights the limited benefits of sparsity in removing the dependence the state-action space size in the unknown transition setting, which is in stark contrast to the known transition setting.
The proof is based on an SSP instance used by 29 to prove an ((DV SAK) lower bound in the unknown transition non-sparse setting. It turns out that this instance can be adapted such that the cost only non-zero for single state-action pair, while keeping the regret lower bound unchanged, giving the above result. We include the details in Appendix

---

6 Conclusion, limitations and future-work
In this work, we studied the SSP problem under sparse adversarial costs and full-information feedback. When the transitions are known, we have shown that existing methods fail to appropriately exploit sparsity. Instead, we designed family of regularizers to use with Online Mirror Descent that allowed us to characterize the sparse minimax regret, establishing the extent of the benefits of sparsity in this setting. When the transitions are unknown, we showed that even the sparse minimax regret scales polynomially in the size of the acte-nctionn space, suggesting fundamental limits in such settings.
Our results open up many further directions of research. In particular. we established the benefits of sparsity under known transition as limited to logarithmic, however, there could be structural properties of MDP that could break this logarithmic limit and achieve polynomial benefits. Moreover, we have limited our focus to the adversarial full-information feedback setting, but the study of sparse SSP problems other settings, such as partial feedback, stochastic environments, or structured decision problems remains unexplored.
Acknowledgments and Disclosure of Funding
Emmeran Johnson is funded by EPSRC through the Modern Statistics and Statistical Machine Learn- ing (StatML) CDT (grant no. EP/S023151/1) Alberto Rumi was funded by European Lighthouse of Al for Sustainability project (ELIAS). Patrick Rebeschini was funded by UK Research and Innovation (UKRI) under the UK government's 's Horizon Europe funding guarantee (grant no. EP/Y02833//1).
We would like to thank the reviewers and meta-reviewers for their time and feedback.
References
[1] Dimitri P Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathematics of Operations Research, 16(3):580 -5555, 1991.
[2] A. V. Boyd. Inequalities for mills' ratio. Reports of Statistical Application Research (Union of Japanese Scientists and Engineers), 6(1959):44446, 1959.
[3] Sébastien Bubeck and Nicolo Cesa-Bianchi Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
[4] Sébastien Bubeck, Michael Cohen, and Yuanzhi Li. Sparsity, variance and curvature in multi- armed bandits. Proceedings of Algorithmic Learning Theory, 83:1 2018.
[5] Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire, and Manfred Warmuth. How to use expert advice. Journal of the ACM (JACM), 44(3):427-485, 1997.
[6] Liyu Chen and Haipeng Luo. Finding the stochastic shortest path with low regret: the adversarial cost and unknown transition case. Proceedings of the 38th International Conference on Machine Learning, 199:1651-1666 2021.
[7] Liyu Chen, Mchdi Jafarnia- Jahromi, Rahul Jain, and Haipeng Luo. Implicit finite-horizon approximation and efficient optimal algorithms for stochastic shortest path. Advances in Neural Information Processing Systems, 34: 10849-1086,, 2021.
[8] Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. Proceedings of the 34th Conference on Learning Theory, 1:4:1180-125. 2021.
[9] Liyu Chen, Rahul Jain, and Haipeng Luo. Improved no- no-regret algorithms for stochastic shortest path with linear MDP. Proceedings of the 39th International Conference Machine Learning, 162:3204-3245, 2022.
[10] Liyu Chen, Haipeng Luo, and Aviv Rosenberg. Policy optimization for stochastic shortest path. Proceedings of the 35th Conference on Learning Theory, 178:982-1046, 2022.
[11] Alon Cohen, Yonathan Efroni, Yishay Mansour, and Aviv Rosenberg. Minimax regret for stochastic shortest path, Advances in Neural Information Processing Systems, 34:28350-28361, 2021.
10

---

[12] Ashok Cutkosky and Francesco Orabona. Black-box box reductions for parameter-fre online learn- ing banach spaces. In Proceedings of the 31st Conference On Learning Theory, volume 75, pages 1493-1529, 2018.
[13] Benjamin Doemr An elementary analysis of the probability that binomial random variable exceeds its expectation. Statistics & Probability Letters, 139:67-74, 2018.
[14] Yoav Freund and Robert E Schapire. A -heooeic generalization of on-line learning and an application boosting. Journal of Computer and System Sciences, 55(1): 1997.
[15] Armengol Gasull and Frederic Utzet. Approximating mills ratio. Journal of Mathematical Analysis and Applications, 420(2):1832-116) 2014.
[16] Andrew Jacobsen and Ashok Cutkosky, Parameter-free mirror descent. In Proceedings of 35th Conference on Learning Theory, volume 178, pages 4160-4211, 2022.
[17] Mchdi bafarnaaJahroma Liyu Chen, Rahul Jain, and Haipeng Luo. Posterior sampling- based online learning for the stochastic shortest path model. Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence, 216:922- 2023.
[18] Anatoli B. Juditsky and Arkadi S. Nemirovski. First Order Methods for Nonsmooth Convex Large-Scale Optimization, I: General Purpose Methods. In Optimization for Machine Learning. pages 1-28. MIT Press, 2010.
[19] Joon Kwon and Vianney Perchet. Gains and losses are fundamentally different in regret minimization: The sparse case. Journal of Machine Learning Research, 17(227):1-32, 2016.
[20] Joon Kwon, Vianney Perchet, and Claire Vernade. Sparse stochastic bandits. In Proceedings of the 30th Conference on Learning Theory, volume 65, pages 1269-1270, 2017.
[21] Brendan D McKay, On littleoood's estimate for the binomial distribution. Advances in Applied Probability, ((()):75-4445 1989.
[22] Yurüi Nesterov and Arkadi Nemirovski. On first-order algorithms for 11/nuclear norm minimiza- tion. Acta Numerica, 22:509-575, 2013.
[23] Gergely Neu. First-order regret bounds for combinatorial Conference Learning Theory, 1211-11377 2015.
Proceedings of the 28th
[24] Francesco Orabona. modern introduction to online learning. Preprint 19Xv:1912..3211.
2019.
[25] Francesco Orabona and Dávid Pál. Optimal non-asymptotic lower bound on the minimax regret of learning with expert advice. Preprint arXiv:1511.02176. 2015.
[26] Christos Pelekis and Jan Ramon. A lower bound on the probability that a binomial random variable exceeding its mean. Statistics & Probability Letters, 119:305-309, 2016.
[27] Herbert Robbins. A remark on stirling's 's formula. The American mathematical monthly, 62(1):
26-29, 1955.
[28] Aviv Rosenberg and Yishay Mansour. Stochastic shortest path with adversarially changing costs. Proceedings of the 30th International Joint Conference on Artificial Intelligence, 2021.
[29] Aviv Rosenberg, Alon Cohen, Yishay Mansour, and Haim Kaplan. Near-optimal regret bounds for stochastic shortest path. Proceedings of the 37th International Conference on Machine Learning, 119:8210-8219, 2020.
[30] Rongye Shi, Peter Steenkiste, and Manuela M. Veloso. Sc-m*: A multi-agent path planning algorithm with soft-collision constraint on allocation of common resources. Applied Sciences, (19), 2019.
[31] Pavel Surynek, T. K. Satish Kumar, and Sven Koenig. Multi-agent path finding with capacity constraints. In Advances in Artificial Intelligence, 2019.

---

[32] Jean Tarbouriech, Evrard Garcelon, Michal Valko, Matteo Pirotta, and Alessandro Lazaric. No- regret exploration goal-oriented reinforcement learning. Proceedings of the 37th International Conference Machine Learning. 119:9428-944 -9437, 2020.
[33] Jean Tarbouriech, Runlong Zhou, Simon S Du, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Stochastic shortest path: Minimax, parameter-free and towards horizon- regret. Advances in Neural Information Processing Systems, 34:684336855555 2021.
[34] Taira Tsuchiya, Shinji Ito, and Junya Honda. Stability-penalty-adaee follow-therregularie leader: Sparsity, game-dependency, and fest-of-both-worlds. Advances in Neural Information Processing Systems, 36:47406-47437 2023.
[35] Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First-order regret in reinforcement learning with línear function approximation: A robust estimation approach. Proceedings of the 39th International Conference on Machine Learning. 162:22384 002:22384-22429, 22429, 2022.
[36] Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.
[37] Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. Proceedings of the 31st Conference On Learning Theory, 75:1263-111 12913-119,122 2018.
[38] Peng Zhao, Long-Fei Li, and Zhi-Hua Zhou. Dynamic regret of online Markov decision processes. Proceedings of the 39th International Conference on Machine Learning, 162: 26865-26894, 2022.
[39] Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. Advances in Neural Information Processing Systems, 26, 2013.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the contributions section of the Introduction, have pointers and references to where all the results we claim can be found.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
13

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All of the theoretical results we present are followed by proofs or pointers references to the appendices where the proofs can be found.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
14

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co) hublicc/guides//odeeSuubiss ooo.oooeeeeuuiiiiiooooooooiiii for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https /nipp.cc//ppppp http://pwlc.ggguueeeeeeeeeeeeeee /ooeeS/// ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
15

---

7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula. call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative етror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://p///aaappp..oo//////////e
Answer: [Yes]
Justification: Our work is purely theoretical and conforms with the code of ethics.
16

---

Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is purely theoretical and poses no societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work purely theoretical and poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
17

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, snperswithcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/coddemoodll as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
18

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality the research, declaration is required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMss as any important, original, or non-standard components.
Please refer to our LLM policy htte::///eerrpeecccc///feerrreep for what should or should be described.
19

---

A Failure of the negative entropy
In this appendix, we prove our lower bound result for OMD with the negative entropy from Section We first restate the result.
Theorem 3.1. For any 6. there exists an SSP instance with a fixed horizon of sparsity level M 3, action space of size A = 2 and state space of size S such that the regret of OMD 7 with negative-entropy regularization and any step-size n > 0 after K episodes is E [Rx] = 1 minn V log S,
Proof. Fix even, = 6, = and N S 5. We first describe the SSP instance. Consider the following MDP M (S,A, p. So, 80.9), where S {so, sú $6 s N: $1 J and A {a,, 02).
The transitions and costs (in each episode k) are defined as:
Sp: p(s su, a) p(s so, a) 1/2 and (s a) = 0 for all a E A. p
o p(s sb a) for all a E A and en (sb, a1) = - ca(sb' ( 02) 1/2.
s p an) 1, p(s 1=0 02) 1/N and e (sf a1) 0, (sf. (16))a2)))))))))))))))
p(glof a) = and ca (o, a) for all E
k/. r(ols))) and ca (zg: a) 0 for all A.
s. p(glsp.al a) 1 and Ck (s a) 0 for all a A.
An illustration is given Figure This SSP instance has fixed horizon of 3 the sense that all policies have hitting time of exactly 3 (the states s and s are added to guarantee this). As result we have that T. D 3. Also note that there are at most 3 state-action pairs that have non-zero cost, therefore the sparsity level M = 3.
start
0.5, 0
0.5, 0
(22 N
sbi
R
1+
02 1/2
1 0
01
R s
R
NN
Figure 3: Diagram illustrating MDP construction for the proof of Theorem 3.1 When an action is not specified for an edge, then both actions give the same transition and cost. If an edge has number in black, it is transition probability; if does not then the transition is deterministic. The costs are given in red. The formal description of the MDP is given above.
From Appendix B. in 28 (we can ignore the optimization over because we are in a fixed horizon setting), the update of OMD with negative entropy for any k > 0 can be computed by solving convex optimization problem:
(s+1(s, a) (s, " (s,0), where
(s, v(s) nex(s, a) Σ p(s' p(sssss,))0(5))
uk+1 arg De(()),
Dz(U) Σ Σ
as) (
(2,)))) v(so).
86S aeA
20

---

with qu(s, a) = 1 and co(s,a) = O. This allows us to compute exactly the points played by the algorithm on the SSP instance described above, and in turn compute the regret, from which the result will follow.
In the following few pages, compute the occupancy measures played by OMD with the negative entropy on the SSP instance described earlier for all episodes, using the convex optimization problem above. We begin by computing expressions for [s, a) in each state:
B5(so, a) v(00) 1o((tt) 2²0()()) for all E A
BE(s a) =0(s)) - nox( a) v(s))) for all a A
BK(65) = =v(s))
BB a1) = =((s)) - =((s))
By a2) u(()²) nek (s 02)
1 Ei=
v(s n 02) s(s
N since by symmetry v(s = ((s{²) for all i > and any v solving the convex optimization
problem specified in the OMD update.
(y a) v(s(t) u((f() for all a a
. By a) v(ss)) for all E A
Plugging these into the optimization problem, we obtain (recall the notation ((s) = EaE g(s, a)):
Uk+1 arg min Dx(v)= arg min Σ Σ qu( a)e - v(su)
8ES aEd
ga (so. a1) -..0l))) + qu (so: 02)e -006
= arg min
0
qu(s an mea (1
(s az) -ea
( an ) + qu
(= ( -()))) ( ag)c .2))
qu(s an ((s)) (x )(5)))
(s )e (x + (s q (())
-so)
gx (x()) ((50) -0.0(()))
= arg min
( (tt)) (s -tt) -2)
* ((()))
+ ( a1 a1 -666 + (s -o0
(e
(
- vs0)).
This being convex optimization problem, it can be solved by differentiating and setting to 0:
@Da(t) qu (s0)e 0.550)
0
do(5o)
&Dz(v) -0.5gx(so) c(0)) (edo u.st(ct) ga (st: an = - and u(s5)) qu (8/ ( nea -nat))) v(2))(
do(16)
-0.5 + 90(8// an "(()) ( -ac az) m(5)) + qn(o6 ( (20 -
21

---

(D)
(56 , ai -oal qu(66; nor (2) vloh) + qu (sg))e)))))
(1))
( - 00
@Du(t)
0.5ya (80) (.00)) + gx(0 a ( (x az ( -o))
Ou(s)')
0.5 + qb (5
+ g ( az - (22
(D&(v)
N
qx 02)e ) -
(
26(55)
0
ou(sft)
(D)
+ (x ) 0.
Let's look specifically at the case 0 = -1,90()) =1,0()))))1 2, 2,,0(( a) = 0 for all sE S, a E A). For the left part of the MDP we have:
(D)
20(()))-0(55) = 0.5 cllbb) 0(25
dv(s6)
0Du(v)
=0
c((ot) =0.25 cd(ot)
0.255
du(sf)
0.25²
9n as
a) = Bi(b)aa
= 0.25, for all a A.
0.25
For the right part of the MDP, we have:
(D)
) = 0- = c(())) + ((66)))o((f)) =.5 = cl(hi) R
0.5
((())) + <(*f)
(D)
= 0 = (0(5f)-n(66) "(f))
c²(aa²)
(s
pu(sR)
V2N
(b)
0 (( -(())) (0)))
e ('
1
c 0.5v(ag)
cu(sg)
c(+8)
0.5
0.50(s))
+ -D.5((5
(.su(sb!)
0.5
v2 + 22N
0.25
(V2+ + v2N)²
(1 (1) = e Bilo .1)) -(()))
V2 O.5((
0.5
1 VN
0.5 N
9 (8 (2) Pii3s .z)) (c())))(((())
V2No0.50l 0.50(00)
1 VN
( a) =e Po .) -(()))
0.50(50)
0.25
V2N
VN + VN)
0.25
n1 a) = Bi a)
(
1 N
Let's now look at general > 1: Since qu an occupancy measure, it satisfies the properties of the dynamics of the MDP (see the definition of ((T) in Section 2 and we have that for any E S: EIEA ga(s, a) = Eves EVEAp(s)s', a' (') a') + Ifs }u). In particular, this gives
s = sy: qx = 1
stt qu (st)) (55g)((5)) 0.5
22

---

g 9k (k(s)) = (s())) 0.5
s. 9s (8()
0.5gu (su) 0.5 (=(50 (1))
R. 9h (8)))
9a (xf))
(0 02)
This leads the following simplifications in the derivatives of Dx(u):
(Du(u) (((5e))00.e(())>))) -0.50())) =0
du(6))
(Dx(v) -0. + (s a1 noaallin a1) + (1/2- (00ss/((ss./)) (1))) menlo a2) -2)
20(s6)
(Dx(6) 0.5 0.5 c
do(s))
(Dv(v) 0.5 + (s . ( + (1/2 - qu (50 a1) (60))= =
(Dx(u)
#1 22) ( + (0 02 )e (((f())) = = c'((0") = 2
(u(sf)
(D)(v)
( aj) + (s a "()))))))))) =0 = c<(of) = ou(+"))
Left part of the MDP:
TDi(u) 00- = (k(56' 01 "(o)))- 11ah
+ (0.5 - ( (x(b); (4860-0-) = 0.5
ou(sf)
(x())
0.5
(s ai)e-
1+(-)}
+ (0.5 (8/, a1)))-0.5n
k+ 1 = cx(bb)
0.5
0.25 + 0.25e -.55g 0.5g
(2 a1) 9n (s a1 ) Bilch ((6)))(
0.5
+ e 0.5m
k+1=3
cn(ob)
0.5
9i (1 an a1)e- + (0.5
(st an a1))e-0.55)
cl(b))
0.5
e
0.25
T- T-e 0.07 e + 0.5e-0.3g
0.5
-U.3m
22 (2)
The 0,0y
q3(s), a1) = (2(5///0000 an)e
(60- = 0.25
0.5
A even
( 01) 1+ 6-.50
A odd
q 01) -0.25,
where the last two lines follow by straightforward induction. Hence the losses suffered by OMD on the left part of the MDP are:
1+ (-1)*
(5 (1) (st a1) + ca (s (st, 02)
q ( .1)
+0.5 (0.5 - qx(sb, (1))
2
(-1)*
(e((obaa ai)
+0.25
K/2
0.25K + 0.5
Σ
12
( an) (st
23

---

K/2
= 0.25K + 0.5
Σ
0.5
0..5
+ 0.5g
F=1
K 0.5
0.25 - 0.25c
0.5n
0.25K + 0.5
2
1+ 0.50
K
0.5n
0.25K +
16
1
1
e
0.5m
K
17
0.25K +
min
16
5
2
Right part of the MDP:
@Da(u)
0 c0(66)
0.5
Th (50 )e
(s()) "(58)) + (1/2 qu
(s a. (aaa)e=-000
(D)(t)
= v(s)) = 11 + 20(x
ou(s(t)
(D)(
= 0 v(())) = )(s
ou(sfi)
0.5
(3 R a1 ae)e 0.5u(a)) + (1/2 qx(sB
0.5
0.5
0.50()))
( Rt a1) + (1/2 - au (50 a1) ue
( a1) + q (s a2)e-0.5m U.5m
Uk+1 R a1) = qu (50 ande ( c0 m1l ( a1 ())e ((83) (s an )e (.0))))))
q (s R a1)
9k+1(sb R. a1) = 0.5 ( R a1) + (1/2 9b (sp Dee-0.5
(s+ R 01)
1 an)
R a1)
= 0.5n (= R 01)
(s .2)
(1/2 1 (5 a1))
(1/2
ou q R
a1
)e
0.5n
Tk R .2)
(s 01)
R a1)
0.5
0.5ky
0.5kn
0.5ky
( .2)
q1 (3 02)
R
0.5 N
0.5
0.5VN
(50 a2)
0.5kg
VN
0.5mk
This also holds for l = 0 (as shown above). Hence, the losses suffered by OMD on the right part of the MDP are
K
K
0.5VN
(s a2)) (2))x
=
VN
0.5kg
K++
0.5VN
K+I
0.5e 0.50
dr = 0.5K
N + 0.5 dx
+ 0.5nz
K+1
0.5K
log( V + c.
7
1 (og(VN + 0.55m)
0.5K
log( N + 0.5((K+1))
=
L
17
1
0.5K
log( 2e log(2e 03)(((11))
log vNV
assuming VN & 0.5n((+1)
"
= 0.5K 0.5(K K + 1)
log 2 +
log N
2n
1 log
N
-0.5 + 2m 4
24

---

If /N= > (.5n((+1) then we have
1 log(v/ (O(VVN-- + e0 + - log( + 6.6n)
1
N + c..5n
0.5K
0.5K + log
1
"
VN + e0.5n((+1)
e. +1) c0.5n
0.5K + log
2e0.5n((K1l)
"
1
0.5K
+ "
log
0.25K,
using that -be-k 3 c- 0.25K2 since cosh(x) > 1. So we have
1
N
( 02)cx 02) min 0.5
log
0.25k
(8)
21
Combining the losses from the left part in and from the right part in
8
we have:
K
K Σ
ake ch)
a ar)cx (s a1) + qu(s a2)cx(s 02)
+
Σ
9x (2)cx(5
A=1
K
{
! 1 5' 2 min -0.5 +
1
N
0.25K
min
log 0.25K
16
2m
4
Regret lower-bound: consider g. defined as follows:
(.(s0, a) 1/2 for all A (st u2) 1/2. (-( an)
qu(s a) = 1/4 for all a a A
(. a1) = 1/2, g. (s a2) = 0, (, a)
(.(5f 1/4 for all E A
is straightforward to check that satisfies the flow constraints and is an occupancy measure. We obtain
K
K
qus
Ck
Σ
(.b a2)
0.5 = 0.25K
K
7 1
Rx
>
q..
ck)
min
5' + min
-0.5 + log 0.25K
16
2n 4
min
{
2V
1
K log
N
K
0.5.
32
Recalling that N S 5, have Rx (mmin K log S, S,K3) for an MDP where the sparsity level M = 3, concluding the proof.
25

---

B Efficient implementation of OMD using our regularizer
In this section, we describe how the OMD update with our regularizer from Section defined in (4) can be computed efficiently. This closely follows Appendix B.1 of (28), who provide similar description for the negative entropy.
Recall the regularizer ()(()) = -PE LuEA ((E (ll,,a)++/8 - for q R 200 We have
Vitp(() - (p 1) a
The Bregman divergence defined as:
Dv, (9.9) v)((1) 11p(4 - (V 9)
= =E Σ p. -p-((a)))-p(
(p+ Σ ( as((s
Σ Σ ('s,,a)) 11 (ss,a) 1p a(s,a) - (p+ 1) ass,a))mn
Recall that OMD with the above regularizer computes the occupancy measures as follows see
0h+1 = arg min {1) (g, (+) + Day (1, (1.91)
Q1 = arg min pp(()) (T)
gEA(T)
As shown in [2 (Theorem 6.15), each of these steps can be split into an unconstrained minimization step, and projection step. Thus, qi can be computed follows
of arg min (1)
9e 20
Q1 arg arg min D (q. (q. (1)))). gEA(T)
where of has closed-from solution (f a) 1 for every S and E A. Similarly, 4++1 is computed as follows for every kt = I,... K
1 = arg min (nin(r:- (g, (x) + (w
RER
0k+1 arg min D (g. sktz),
(EA(T)
where again 41+1 has closed-from solution (s, a) (s,(sa)) cx a) ])
for every
and A (follows from straightforwardly differentiating above objective and setting 0 and accounting for the non-negativity of occupancy measures)- we use notation = max a).
For the projection step, we start by formulating it as constrained convex optimization problem:
min Dv, (g, pe+1) s.t. geRT
Σ a((s
Σ SES d'EA
Σ
I(s =os
e S
asA
Σ
((s a) & T
((s,a)
V(s,a) e e
The problem can be solved by considering the Lagrangian with Lagrange multipliers À and {r(s)] ses:
C(g, = D dl+i)) + x(2 (Σ Σ
q(ss, a) - -T) + Σ v(s) Σ P(s)s',a')g(f + Ifs = tos Σ a(s,a))
#6S asA
(g, (k.z)) + Σ Σ
((s) Σ
P(s 1 a))(s)))(s))))))))))) -e(s) + v(s0) XI,
S A
e'eS
26

---

Differentiating the Lagrangian with respect to any q(s, a) and setting to 0, we get
2 = Velp(a)(sa)) (),,)) + +
Σ P(((s, v(s)
Ōq(s,a) (p+ 10++)) (p + 1) (s, 1/8 + +
e'ES
Σ
P(s')s,a)u((8 -s(s) 0.
s'ES
(k+1(s,0)= ( A Ev's P(s'ls, v(s)
p+1
This formula is also valid for k- 0 by setting co(s, a) 0 and (o a) for every s S and
a E A.
To compute the value of X and at the optimum, we write the dual problem D(A, v) ming C(g, v)
by substituting 4k+1 back into L:
D(A, v) = Dep (9k+1. 9 +
Σ Σ
(s) Σ P(((),.))u(s)) - u(s)) + v((0)) - XT.
aEAA
s'eS
Recall that (8,0) [qn(s,a) 2 (s,1(s)))):
-
(ignoring terms independent of X, v, e.g.
Dv, (gk+1, 11+1) = Σ Σ
(o, a) 1110 1111///))00///11))))//11/ + gu+1 (s. [pq]+ (1, a) - (p + 1) ur]
#ES aEA
0 Σ
Σ
(s, [p(4htt(s,0)) 1)
A Eies P(o'|s, a)u(s') - - v(s)
p+1
S&S asA
- + 18,
(s, a) p / A E P(s'|s, (1o()s))v(s') - -(())
Σ Σ
p +
NES
(o+ 1))k+1(s,
since if (1,+1(s,)) = 0. then the whole term is 0
Σ
(s+1(s, a): (s) p+1 (A+ +
Σ P(s''ss - e(s)) }
8ES aEA
SES
- D() Σ Σ
(8,1(,,)) [<)4)2(8,0) p+1 (X+ Σ P(5'),,))0(s') -(())
85S aEA
S'ES
+A+ Σ P(s'(s,))u(s)) - m(8)]] [()) v(so) XT
SES
( (s,6)1 X+ Eves P P(dls,))v(()) P661scco(6) e(so) XT
Σ Σ (s+1(s, a)
p+1
SES aEA
Σ
Σ
Ih+ (s, a) 1+1// + XT
gh (s, x Eves P(s'is, a)((s) v(5)
- 1 + v(so) XT.
Σ
Σ
p+1
Maximizing the dual gives and equivalently, we minimize the negation of the dual:
X+ Evs P(s')s,a)o(s)) v(s) 1+p
A U6411 arg min
Σ [[ SES DEA
v(so) + XT.
A20.r
p+1
This is a convex optimization problem subject only to non-negativity constraints, and can be efficiently solved using iterative methods e.g. gradient descent).
27

---

C The benefits of sparsity upper bounds
We restate the main theorem proved in Section 4 Theorem 4.1. Consider OMD with upp as regularizer. If > e is such that Ou- E A(T),
V pTI+1pp KDAFE p log(T'M), then E [Rk]]
o O(VDKTlog(MTT)
We include the missing details from the proof given in Section 4 First, recall from 4 that
(p(9) p (-1 + |1q [1/l11/p)) = (-1+
(g a) 221pp)
aEA
@1/p(9) (p+ 1)g(s, a)
6q(8,a) a)
( 1
Eq(s,a) 20+,))000)))
(i)p(() = diag (p+1 1
-1/1-1)) (
Vibp(() (p + 1)
p
We implicitly assumed here that v is defined on B. 20- The missing details are:
1pp satisfies the condition with
Vpp(1) Velp(g)); Vitp(as) nick (s $ de (s,a)
((8,0) (b((,a)
1
91-1/p(s,a) (2 2 (
1-1/0 (s.
9k
V (pp(g) diag (pfigt-112) 1/):: follows directly from the expression for (2)pp(g) above.
We now turn to the description of the parameter-free algorithm and the proof of its corresponding regret bound (Theorem 4.4).
C.1 Sparse-agnostic bound
For the unknown sparsity level, we use the same approach as in 19), dividing the episode horizon into segments, where each segment will run OMD from scratch with an increasing sparsity level guess. Crucially, there will be at most O(log log M) such segments.
Define
M max l. the true sparsity level across the horizon.
== 1log, log, M). J. the maximum number of segments.
m(b) 22 the assumed sparsity level during the b-th segment (or interval T(b) below). The reason to use a double exponential is that this aganse-agnostic procedure brings an extra B factor the regret bound: if we use 26 then B Ollog M) which harms the regret bound.
for 1 < b & T(b) min (1 < k K l|cllo > m(b)), the first episode in which the sparsity level of the loss vector exceeds mbb) We also define 7(0) = and r(B) = K.
Using this notation, we can partition the horizon [K] as intervals ((b)))e(p according to the episodes 7(6) where the thresholds m(b) are first exceeded. For 1 & b b B:
I(b) [r + 1b)) if r( - 1) < (b)) Ø
if if 1) = 7(b)
Let by min (b (b)) > k) be the index of the only interval which episode k belongs.
Now we define the OMD parameters used interval T(b), in which we essentially use the parameters from Theorem 4.1 assuming the sparsity level is m(b):
28

---

Algorithm Sparse-Agnostic Mirror Descent
Input: T, K Initialize: - log 2T,, - - (TtDD///DD222) b b 1, Q1 - arg min geA(T) vp(9))
for 1..... do
Play 9h and Observe Cj
||cx lo & 22d then
gk+1 arg yEAr (q. cb) Des 9k)
else
b - llogz logg c* oolol
p log 22
1 - (DD22))
(DK22pp)
4k+1 - arg gE((T) (g)
end if
end for
the parameter of our regularizer is p(b) log(m(b)T).
1(b)2
the step-size is 1)(b) (
Recall that our regularizer with parameter p is given by v)(4) = p (-1(1111)))) (-1+ |1 1+1p/) At episode k,
1+1/2)
we use the parameter p(by.) defined above, i.e. using the index value by of the interval T(bg) to which episode & belongs to. The OMD update is then defined by:
((b()))
m/(bb)
Σ
CW
k = L K
Mick, (eT((w))
The full procedure is given in Algorithm I The following lemma shows the cost of being sparse- agnostic is an additive T term and a double- logaritbig factor in the sparsity level M. Lemma C.1. Consider running Algorithm 7 IsT e such that gx- E ATT), then E [Rk] & o TB
O(TB + (KTTllggMTT)
Proof. Fix (interval) E [B]. On the time interval (b). we run OMD with regularizer (p(h)) learning rate yy(b) and we consider the (expected) interval regret R(b) ΣkE (Tr,, (k) min Σ (gxt, cx). Crucially we know that up to the last time step of the interval, we have bound mb) the sparsity for all rounds but the last.
Since J < for any k, we just consider the regret on the rounds not including 7(b) for which we suffer regret of at most T':
R(b)
Σ (an yo,, CK) T kE/(b)
Σ
(axz - aar, CR).
kE/(b) kxc((h)
For the other rounds we follow similar steps as in the proof of Theorem 4.1
(AT Iz,, cx) x p(b)T1+1/p(0)
v)(b)
Σ
|c0ll//1000 9x) +
17b)
2
(E)(6)
keT())
k<r(())
p(b)TL+1/p0)
n)bb (b) 1/p(0)
Σ
((ck 9k) + 1)
n(b)
2
ke ((B)
(b)
Σ
(p yr,, CK)
1
p 1/p(b))
7 (B) 1/p(0) 1/7()()
Σ (ct
77bb) ml ((6))(()11))) (1)(()))(())
((bb)
kE)
kEl
(b)
k<r(())
29

---

2p(0)72+1/p(6)
+ (((b)m(())um l/ph))
Σ
(ck, Fm + 1)
n(b)
RE((b)
b<T(())
2p(6)72+1//(0)
n(b) + (b)
Σ
(Ck (x*) 11;
ke/(b)
where we used that 1-m(0)m(b))ppp E 2 which is the case if SeT log((M)) using how we
defined n6)) Using 77(b) = V Dkm(b))/m()) we have
R(b)) & T (())) (Km()))O (2+ EkErcol(ens (or)
DK
Ekerce (cx. 1)
$ T TDKe log m(()))) ( (2+
DK
TT v PTDDellg(MM (2+ (cer, (mx) +
DK
where we used that p(b) log m(b)T) and that
b BEBELE logz logg M m(b) 22" < x22" 222211ox 1loz long =2 M M²
log (o((m(b)r) log (o((Mer) &log(MMT).
Then
B ElRk] & Σ R(b) bm1
B
>
k(t (ck, ax*) +
< TB + De
(2B +
Σ
DK
b=1
K
= TB + D2TDKelog(MTT)
(BB +
+
Σ k=1
(cv.
D
DK
< TB /BB/2TKeellgge
where the last step uses that Σ Kun,
Ek & K Klaxy/llckkl DK and
D 2
C.2
Fully parameter-free bound
We now turn our attention the unknown hitting time of the optimal policy T., where we can exploit the same technique presented in [8].
We N log K instances of Algorithm 1 where the j-th instance will its parameter T as b(j) which is roughly 21, so that there always exists an instance j. such that b(j-) is close to the unknown T.. Specifically, we run a scale invariant meta algorithm with correction term in obtain the desired bound (details in Algorithm 2b.
D log(T.M)) and T. > e, Algorithu guarantees E [RR]] < ò Ó (VDKT. log(M.T. T.). where the notation Ô hides
Theorem 4.4. If K > max(T., T.
Proof.
We closely follow the steps the proof of Theorem 2 in g We have
b(1) T (so) so for all instances A(b(j)) is non-empty and the instance is well-defined.
Let j* be the index of the instance with smallest b(j*) that is larger than T i.e. MG") T, b(j"). This instance exists since b(N) K > T..
2
30

---

Algorithm 2 Fully Parameter-Frre Online Mirror Descent for Sparse SSPs
Define jo nog2 T (80)] 1,b(j)
2 N
Mog2 K
jo. 7
(v D
-1/2
Define pp(p) = -ソ-1 n7 p))
Initialize: P1 AN. such that (i()) mn Vj
Initialize: instances of Algorithm 1 with j- th instance = b(j)
for k 1,.... K do
Obtain occupancy measures of for j [N]
Sample jt ~ pk, execute policy induced by oh
Receive Cę and send it to all instances.
Compute (j) = (T. Ck). a& (}) 4n, (nj
Update P arg peap (p, lu + an) D& (p.
end for
We start by decomposing the regret into the regret of the meta algorithm w.r. finding j. and the regret of the j. instance wet. the best policy:
K Σ
E [
=
Pa ci)
1=1
k=1
K
Σ
Pi Pa ok)
- , Σ <g gr .t)
K Σ
=
(pn eja lx) +
Ag qu* ck
Meta-Rogret
je Regret
where we consider Pk: lg as N-dimensional vectors and ej. as the basis vector with the j. coordinate equal to 1.
C.I the j. Reggret bounded by (BB... + B DDVDDb... logG)))) =
By Lemma
O BT. + B DT. log(T.M)
This also allows to say that:
K ym. (k) + +0 +O(BT. log(Ko
Σ
Ck)
k=1
(yaya (k) +0 BT. B DT. log(T. DTg. M)
DK + O BT. + BV DT, (T..Koo(TT.M) (TM)
which we will make use of just below.
For the meta algorithm regret, we can use Lemma 12 of g which guarantees that:
2 + log
N
((G.)
E
(p eg,, (x) = =
+ 4n, b(j.)
<g ck)
Mīj
k-1
2 + 2lgog
bli+) [Ny)
0
b(1)
+ 4nj, b(j.) DK + BT. + B DT. log..o)
n75
31

---

log T.
0
na no T. (DK v VDTK log(Li
D1.
logTT
A/. DT.K
Tii
DT,K DigKlogg.
where we used
the notation Ô to ignore double-logarithin factors.
K b
T. D
log (T.M).
log T.
11.
DT.K-
D>
Combining everything gives the result.
32

---

D State level sparsity
In this section, we consider a different notion of state-level sparsity:
M' max
H(c(((s,) 0} < A.
GEA
From Theorem in [8) we have a cumulative loss bound for a version of OMD with negative entropy regularisation:
K
B & Ō
E
J
from which we can exploit the state-level sparsity:
(sp)
J
E
( ('),a =0
Law (50)
E
cu(s", Tu: Tu: st s =su
Ia (50)
E
Cx a)) P;
P. Tun 60
KMM'
E IT.
uu. sol
A
K M'
(T)),)
A
where nu is the uniform policy (T (als) = A/A) and T is its corresponding hitting-time. This gives the following regret bound:
M' (s))) E [Rx] & ( KT.
A
We can actually relate this result back original notion of sparsity since we know that M' M. If M & A, then we can non-trivially bound M' by M and achieve a regret of Ö 60v KT. (s0))
This result highlights that is possible to achieve polynomial improvements from sparsity if we consider state-level sparsity M' M < A. However, this comes the cost of (su) factor. In the worst case, this additional factor will cancel the polynomial improvement. could be an interesting avenue of future research understand specific structural properties of the MDP that may lead to real polynomial improvements.
In the experts setting (S 1), we have M M' and (s)(s)) 1 and this bound recovers the M improvement of the expert setting. This provides some further insights into the performance of OMD with negative entropy regularisation and that in particular issues arise when there is at least state with non-sparse costs even though most other states may have sparse costs.
33

---

E The benefits of sparsity lower bound under sparsity
In this appendix, we prove our sparse lower bound result from Section [4.2] We first restate the result. Theorem 4.6. For any D, T., K, A with T > D > 3 3lgg S. S(A- 400, K > 800T log and M 3 101, there exists SSP instance with stochastic M-sparse costs, S states and A actions such that its diameter D, the expected hittnng time of the optimal policy is T", and the expected regret with respect the randomness of the losses for any learner after K episodes is [[ 2 D(VKTTD Dlog M).
D
Proof. Fix =
S/2 2
2. Fix = 2B+1 2 2
8/2
Fix = min M - 1, (A
Fix 1) M 3
T T. - B 1, with T. D.
We first describe the SSP instance with stochastic costs. Consider the following MDP M (S, A. p. So g) illustrated in Figure and that we formally define below.
80
01
a22
a/2
81
82
8N-1
SN
Figure 4: Diagram illustrating MDP construction for the proof of Theorem 4.6 Details given below.
The first part of the states represented by binary tree of depth B + 2 and allow to formerly consider the N states at the bottom of the tree that matter, while avoiding an assumption on the existence of state with A S actions was done in prior work [8]. Each non-leaf node corresponds to state with two actions transitioning (deterministically) to the left or right child respectively. The total number of nodes in the tree is
B
Σ
2' = 2B2 1 2
Log 8/2 Tng
S 1 = 2 - 1 = 1
The total number leaf nodes N B
4. Denote the set of states corresponding to the leaf nodes by S₃ = {$1.-.., & The root node 8g- There is also one additional state denoted by f
>
(recall that the number of states in the tree S 1).
We consider the same action set across each state: A = {ai, CA-1, ay }. In the states of the binary tree where we have only described two actions, same state deterministically with 0 cost.
consider the other actions to remain in the
The transitions and costs are defined as follows:
For all states and actions in the that leaves, the transitions specified above.
The costs are all 0.
For Szi and aj E A
34

---

- jif = f. then p(flss, = 1 and c (s; ag) 0.
- j e A-1] 1} and j+ (A-1)((i)))) & L, then p(g]s; 0z) T p(s:|si, az) =
1
1 # and the cost is an independent sample from a Bernoulli distribution at each
episode k: cx((8,, (z)
Ber
Dt'
27
- i E {I,..., A 1} and j + (A-
- 1) (i - 1) > L, then aj is the same as ay, i.c.
p(f)s;,a,) and c* (S,, az) = O.
For /.
- - =..((ff..a) az) = 1- tor and c* (f. ay) = 1.
-
for all aj E AMar), (f) = and (f( 0.
Denote the above distribution for C by D. In each episode there are at most L+ & M non-zero costs, ensuring the condition sparsity is respected.
For E {I...., N) let Ar correspond to the actions in state s; E St which can transition directly to and A', corresponds to the actions which deterministically transition to f (e.g. if (4 - 1). I.
then Ar { )) For any proper policy ı independent of the stochastically generated costs
in episode k, we have
Eeg~ D [ (s:)] = EennD
Σ
t(alss) (((( a) + (1 JK(s)) + JE()) Σ (alss))
aedi
addi
Σ T(als)) (Be, (Beg-[[cs(Si,a) (1 (1-
1 11
Beg L Jh (sil]) D'. Σ
T(als))
T
a
Of
= Σ T(als:)
D'
+ (1-7))m- + D' -1 Σ T(als;)
2T
A.
asd,
1 = Ex [ [J] (1-
Σ a(alss))
D'
Σ T(a|si) + DD (1 Σ
T(a|ss)
T
2T
acA:
atAi
a
D' 2T
LeE,, T(alss) DD' (1-Eoed T(als:)
Eaed.
ReyDD [ [J[(s))]
1- 1-(1- (1 7t) E.EA,
T' ELEA a(alss) + + 1- ExEd, <(lsss))
1
D'
2
+ EaCA, x(a|ss) + (1 IneA, x(alss)
D'
2
The optimal policy x' is the policy that takes actions in the binary tree to reach state s;- and then Ex= Ck (s,s,,,)) a,). We have J (so) J (sx-)
nt" (ay- (sz-) for i*, " migmin,,,ee and for any 1: 2 1
J (sx) = cu(ss, azr) + (1-
1 T7 )
J (sc)
J (so) ('(x((;r,aa))))
K
k as))
Σ J (so) = T" Σ co(()r, T'
Σ
min
( iii (gig
Hence,
D'
k
E
D
Rx 2 2
K
E
min
Σ
co(s ag)
c cp
35

---

T
D''
K
E
min (A-
Σ c(()),a))]
2T
#D
K
cx((8) m;))]
T
C D
Lijijt (A-1)risl
max
2T
We now apply Theorem M > 101) and n K
G.I with
D'
2.2
100 (since S(A - 1) 400 and
SO0T.
log M E
400T" D
log M >
200 log d. We obtain:
0.02T' / (x(1-
D'
D'
sup E[ x0
R
[k
log I. 1.57
ei
cl...e
2T
2T
0 Mog
since L x M/8. Note that since T. 2 D, the hitting-time of the fast-policy is D' + B and the hitting time of the optimal is T + +B+1 1 = T., required. This concludes the proof. O
36

---

Lower bound under unknown transitions
Theorem 5.1. For any D, K, S, with > 2,A 2 16, D 2 and K E SA, there exists an SSP instance with M 1, S states and A actions such that its diameter is D and the expected regret for any learner without knowledge of the transitions after K episodes is [[ > Q(Dv/SK))
an
a.
On
Figure base case
Proof. The idea is to inject sparsity into the lower bound construction (29] and to see if sparsity helps. Imagine the simple SSP in Figure [ where state 8o there A available actions, all with zero cost, while in the state f there is only one deterministic action with unit cost going back 8g- Among them, there exists P(g So. a) D ell(a * a.), and consequently, P(f s0, a) = 1 - D + el(a * a.). The cost therefore only suffered when the selected action transitions to the f state. This will therefore not increase the hitting time of any proper deterministic policy while still inducing the desired sparsity.
action a, such that the transition probabilities
given by:
Clearly, the optimal policy plays a. at every time step to reach the goal fast possible and therefore (su) D 1.
Now, denote with N₂ the number of steps that the learner spends in in episode & and Ng the number of steps that the learner picks action a, in episode Note that Ng also the total cost that the learner suffers during episode i minus one (since the last transition will not be paid). Thanks to our construction we can still prove Lemma C. I in 29
follows:
Lemma F.1.
B[Nx] J = eI [N+ Ng]
Proof.
30 P[st sol
E
Σ
t-1
+
P[se sul
t=2
1
P[st su 8141 su, Q a.]P[s141
su, a:-1 a.)
t=2
2
P[
80
81+1 = s0, a * a.]
80; a # a.]
1=2
1
1
8
1 c
8
1
P[S++1 80,0 a.]
P[s++1 04-1 * a.)
D
D
Rearranging gives:
E E - D= NEl
Adding and subtracting 1 gives the desired result.
37

---

Hence:
K 4
K Σ J (50)
E [[Rx]
Σ
Σ
Ca kk. db)
E [MM]] - J c[. N
where = -- N and N _k=1 N Since we recovered Lemma C. in (29 as the starting
block of the proof, following the derivation we can lower bound N in expectation and upper bound the expected value of N to retrieve
Lemma F.2 (Theorem C.4 in 291). Suppose that D 3 10,) and A >> 16, for the problem described above we have:
2K A
E B[Rx] > eKD
-EA
8
Now consider the following MDP. Let S be the set of states disregarding g and So- The initial state so has only one action which leads uniformly at random into one of the states 8 S, where each one has its
optimal action o.. Then the transition distributions are defined s)
1/D, P(s az,s) s) 1 1/D, and P(g a) = (1 - c)/D, P(s a, = 1 - (1 c) for any other action E Affa)). Note that for each state, the learner is faced with simple problem as the one described above. Therefore, we can apply Lemma F.2 for each state separately and lower bound the learner's expected regret the sum of the regrets suffered at each state, which would depend on the number of times each state E S is visited from the initial state. Since reaching each state has uniform probability, there are many states (constant fraction) that chosen O O(K/S) K/S) times. Summing the regret bounds and choosing e, gives the desired bound.
Denote by Ke the number of episodes the state S is visited:
E[Rx]
Σ E SES
eK,D D
1
2E1
2K A
eKD
2E
2 A
EE
K3/2
8
8
SES
Then:
Σ 3/2 < Σ BBLK.VVEIK3
B Σ
S
K
K2
S2
+
K(S
$2
1)
K
KV3
2K 5
S
S
Leading to:
cKD
2K
E [k]] >
2 DK
>
DVSAK
8
SA
1024
for = 1//4////// K > SA, concluding the proof.
38

---

G Lower bound on the maximum of asymmetric zero-mean random walks
We extend the lower bound of [25] to asymmetric zero-mean random walks. We consider p > 1/2 because it simplifies the proof below (lower-bounding & by and upper-bounding C. in proof below) and is what we need the proof Section 4.6 in Appendix (we use p = D-//21""
Theorem G.1. Fix pe [
1. Consider random walks Z," Σt= X3, where
x;
P.
w.p. p
1--p p. w:p.
I > 200 log d (also ensures that < 1 +
and d > 100. Then,
E
max
Z."
> 0.02 np(1 p) log d 1.5.
LEtEd
Proof. We follow the same lines as generalize to p > 1/2.
25 who show a special case of the result for 1/2. We
Consider ((n) Σr= - X,, random- of length n, then B, 7(m) + pn B(n, p). Binomial
distribution with parameters n and p.
G.1 1st part of the proof:
The 1st part of the proof is all about providing lower bound on P(B, 2 pm + 1)
10 for any
te [1, np 1].
Lemma G.2 (Generalized version of Lemma 4 of [25]. Theorem 2 (11). Let n, k be integers
satisfying > and pm & & n. Define I = 1p(l--pa pp(1-p)n'' Then Bn B(n, satisfies
pm
n2 1) pt 1/ n 1/2 h
1- ((x)
P(Bn k)
((x)
where (bx)) is the PDF of standard Normal and ((x) is the CDF The proof can be found in (27).
Denote D(p, q) p log + (1 pp) log
I-p I-q as the KL-divergence between two Bernoullis.
Lemma G.3 (Generalized version of Theorem of (25)). Let n, k be integers satisfying n 2 1, and up & k & n. Define x k-pn Then B. ~ ()n,)) satisfies
vp(1-p)m
exp (nD((a p)) 1- ((x)
P(Bn > k)
2/
((x)
Proof. For n, we verify the statement of the theorem directly. The left hand side is (Bn, >
v)) = n². The right hand side is smaller because exp - DDD (1.2) p" and for x v n 0,
we have (-((w)) ((x)
2 (see e.g. Section 3.3
15
For np & le we first bound the binomial coefficient (*). Stirling's formula for the factorial 27 gives for any n 2 1,
2nn
n
n! <e 1/12 / -
2
Since 0 < np & k 1, we can use this approximation for k n and n - k and obtain
12
n!
k:
klnn - kj!
nd "
(e1/12k.ke -k 22rk) (el/12
k)n-ke (00)0nn))222(( /20(n k))
c e// x
(m- k
kk)=-)
39

---

1
1
n exp( ( -nD
m.
k
p) /V k(n k)
1
e1/6 2n p²(1 p)
since
D ( nn" (m
+ (1
k ) log
1 - k/m
k
nip
n hi
11(1 (1 - p)
log
log
log
n
npp
n
1-p
k
n
n k
= eexp (nD
k n
mp)) k
nn(1 p) n h
n-
= -1(11
p)m=- k (m)
n-k
h
k n k
Since h: 3 1, we can write the binomial coefficient as
(n-1)
k (w)) By Lemma G.2 we have
(--1)
n
P(B, > k)
v
n
n
p
(1)
m-
1-((x)
k- 1
δ(x)
n k n1)
k1/2 (1 p) nー 1 1-4(x)
v
px
k
Φ(x)
1
k
p² 1² p) n- 1+1/2
k
b)
1 1- ((x)
exp
-n n
2/ /
2TT
vn
knn - k)
p²(1 p) nー
((x)
k
1-P P
k
pP] }
1- (xx)
exp
nD
e
2n
n n
p
n
((z)
The result follows from
for np & k x n 1
up
For ks pn + xn, the 2nd-order Taylor approximation of u(x) D(
D(p + x. around 0
x² pp(1-p is
We define vh [-p, 1 - p] R as the ratio of the divergence and the approximation:
2p(1 p)
(xx) D(p + x)
x22
In particular, we have that (xx) p(1-p)
(I+))( for [0, - p). This can be shown using
Taylor's theorem on u(x): for some = E [0,
2122
1
1
x²²
x²
D(p + x.
x²a
+
2
+p
1-p- 2
2
2(z + p) p - 2)
x²
x²
& D(p + x, &
2p(1 p)
2(x + p)(1 p-x)) x)
since (x+p1(1-p-z) is increasing on [0,1-1] p).
Let te np + 1] be a real number. By Lemma G.3 and Lemma I in 25 (also Mill's ratio for
standard Gaussian 22), we have
P(Bn > pn + 1o-t-1 1) = PBB,, > [pn + t 11)
exp -nD [mm+e-1) p)
e1/6 V 2m
pp + t 11-
+ v 2m
Vp(1-p)n
exp
-n
pm-+ P)
e2/6V/T
π tt
+ 2TT
/p(1 -pjn
exp
-nD(p +.
π
c1/0/211
+ 2m
v p(1 ppa
1
t
1
= =c- 1/6 exp(
vb
(10)
2pp1 p)
/
+ 2
v /pp[1 1pp(1pp)
40

---

G.2 2nd part of the proof:
We can now turn to the actual proof of the result. Define the event A equal to the case that at least one of the - is greater equal to CV/pp(1 p) log d - 1. We will show this event / threshold controls the expectation of the maximum. First, we define C and provide some upper and lower
bounds for it. Denote by [dd V2
2 2log d log d
then
1
2 log log d
1
C = n(d,n)
2
f(d).
(11)
Val /20(3 p) logd)
log d
V 006 (v((v/ /20 -p) logd
We bound the two factors separately:
2p(1-p) logd
[0, 1 (1 p)] for n > T0 log d and so
2
TO
1< & (= + (1 - p(1-p)
1 p (1 p
10
(12)
2)
9
The function f(d) is in 25
decreasing on (1, e1, increasing on (00), and
lima-roo f(d) 22. Therefore for all d e [5, o0),
1.12 & f(c²) & f(d) & max V2) V2
This gives for n >/ 200,20 P_ log d,
1-p
1.12
& C(d,n) 22
(13)
110
Since p > 1/2, if n > 20 log d, then n above implics:
p(1 p) logd logd (if d > 8) and > 200 log d. The
200
1< CV np(1 p) log np & np 1.
(14)
Finally, we bound the quantity of interest:
E
max Z
max
2T A
P(A) + E
max Z,¹ AAA.A
- -(1-(())
TeiEd
leiEd
max 1s
AA
P(A) + 2 AA
(I-P(A))
E
max 1&
4
P(A) R. 1((" <
<Cvnp(1 p) log d - 1] (1-))(
max 2 P(A) + (z <0 (1-P(A)) by 14
lsled
(Cv rp(1 - p) log d 1) IP(A) + E 2 1m) (z(²m) <0| (1- P(A).
(15)
First, we lower bound E
(1))
zz(1 (m)
< 0 Let 3
For n >
p(1-p) p) log d.
200
[itt
we have n
205
200+ and 3 < 9
<p(1-p)
#(1-p)p
Then Lemma 2.2 in 26 combined with Lemma 8 in 13 give that for Yn ~ B(n, 1 - p):
10
Yr Yn > n(1 - p)] < (n11 - p) + ///pppppp11-- - p) < n(1 p) 9 Vnp(1 - p).
Since B, ((n) + pm B p) can be written as n Yn, we have:
\ z E 0 E Bal B, & np np
41

---

E
Yn Yn < up np
n
E
Y Yn 3 n21 - p) np
10
3 n(1 p)
V nnp(1 p)) np
= 10
npp - p).
(16)
9
Next, we lower-bound P(A):
P(A) - P(A9)
[P| ([(z(m) < <Cvnpp(1 - p) log d - 11)
Bn < np mpppp( p) log d -11) 11)
PP
1 P Bn np + CV np(11 Cv p) log d - 11)
d. Bn > np + CV np(11 p) log d - 11)
2 exp
since x &
c-1/6 exp 2p(1 p) (6 Cv ppp logd
Conp( loge
3 1 exp
-dd
using 10) and 14
V2nC V np(1 pp) log
v /mp(1-7 7)
c 1/6 exp (-2 p(1 logd/n) C² logd
exp
V d 2
c 166 (CC (01--v log
exp
VT d
c 1/6 x v((
Abill oi loxd
> exp
by 13)
2 n log d +2
We now use that 11-5 -/ 122p1112 -p) log d/v)
= log d by the definition of C in
11 Hence, we obtain:
116 log d
2 log + ) )
1/0 log d
P(A) > 1- exp
2 log d + 2 = g(d), for g(d) cxp
(17)
Putting everything together: we plug (16) and 17 into 15) get
10
max
z
> (Cvnp(1 - p) log d 1) (1 ((d)
9 g(d)
np(1 p)
f(d) (1- g(()) (Vnp(1- p) log d 2) g(d) g(d)/np(11 p)
10
using 11
Ve(V
5p(1-p)lng logd
f(d) -g(d))
(Vrp(1 p) log -22)
10
g(d) (d) //ppp111111 p)
using 12
V10/9
9
[(d)(( g(d))
g(d)
(())(1 g(d))
= = nppp - logd.
V10/9
v log(d)
V10/9
> 0.02 np(1 p) log d 1.5,
for > result.
100 (we also used that / /pp(1 p) log > 2 in the 2nd inequality). This gives the
42


Reviews:
[{"review_id": "iQIcKXu0Ji", "reviewer": "Reviewer_9PaL", "summary": "This work considers the adversarial stochastic shortest path (SSP) problem with sparse costs in the full-information feedback setting. With known transition P, this work improves the previous best known result $O(\\sqrt{DK{T_{\\*}} \\log ({T_{\\*}}SA)})$ to $O(\\sqrt{DKT\\_{\\*} \\log (T\\_{\\*}M)})$, where $D$ is the diameter, $K$ is the number of episodes, ${T_{\\*}}$ is the expected hitting time of the optimal policy, $M$ is the sparsity parameter, and $S$ and $A$ are the state and action space size, respectively. This is achieved by a new regularizer proposed by the authors, which regularizes the (1+1/p)-norm of the occupancy measures. The authors propose two algorithms, one requiring the knowledge of $M$ and the other being a parameter-free one, without requiring the knowledge of $M$. For the same problem, the authors prove a lower bound of ${\\Omega}(\\sqrt{DK{T\\_{\\*}}\\log (M)})$, showing the tightness of the dependence on $M$ in the regret upper bound. The authors also prove an algorithm-specific lower bound, showing that the canonical Shannon entropy is not able to achieve the same regret upper bound. With unknown transition P, the authors prove a regret lower bound $\\Omega(D\\sqrt{SAK})$.", "questions": "1. Could the authors please further explain the intuition on Line 223-229? I do not quite understand why “inducing an OMD update at points near the boundary of the space that can only move to new points in very close proximity” prevents the algorithms from obtaining a sparsity-dependent bound.", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n1. The results are new.\n\n**Weaknesses**\n1. **Significance**: Though the results are new to the literature, I am a bit concerned about the significance of the results. In particular, the authors obtain the upper bound of $O(\\sqrt{DK{T_{\\*}} \\log (T_{\\*}M)})$ in the full-information setting. Though the dependence on $M$ indeed matches the proved lower bound, the improvement from $O(\\sqrt{\\log (SA)})$ to $O(\\sqrt{\\log M})$ against previous work [1] does not seem to be very valuable to me. Further, I find that the improvement does not even recover it in the special case of the expert setting (i.e., $S=1$). On Line 39, the author mention that $O(\\sqrt{\\log A})$ has been improved to $O(\\sqrt{\\log A^{\\frac{M}{A}}})$ in the expert setting. However, letting $S=1$, the work actually achieves the improvement from $O(\\sqrt{\\log A})$ to $O(\\sqrt{\\log M})$. Yet, $\\sqrt{\\log M}\\ge \\sqrt{\\log A^{\\frac{M}{A}}}$ for all $M\\in (1,A]$. I would instead suggest the authors investigate whether significant improvements are possible in, e.g., the bandit-feedback setting.\n2. **Parameter-free case**: Theorem 4.3 in this work shows that it is possible to achieve the sparsity-dependent upper bound in the parameter-free case. However, I notice that this only holds for a sufficiently large $K$ (specifically, $K\\ge MT_*$). When the losses are not so “sparse”, this essentially means that $K\\ge SAT_*$ is required. As such, I think this limits the applicability of the proposed algorithm.\n\n[1] Chen et al. Minimax regret for stochastic shortest path with adversarial costs and known transition. COLT, 2021.", "was_revised": true, "final_justification": "My concern regarding the significance of the results remains unresolved.", "rebuttal": "We thank the reviewer for their thorough feedback. We address your comments and question below.\n\n# Weaknesses\n\n1. Significance: Though the results are new to the literature, I am a bit concerned about the significance of the results. In particular, the authors obtain the upper bound of $\\mathcal{O}(\\sqrt{DKT_\\star\\log(T_{\\star} SA)})$ in the full-information setting. Though the dependence on $M$ indeed matches the proved lower bound, the improvement from $\\mathcal{O}(\\sqrt{\\log(SA)})$ to $\\mathcal{O}(\\sqrt{\\log(M)})$ against previous work does not seem to be very valuable to me. \n\n- **While the improvement from $\\log(SA)$ to $\\log(M)$ is logarithmic, the gain is practically significant in scenarios where $SA$ is exponential in problem parameters (e.g., navigation or scheduling tasks). In such cases, $log(M)\\ll log(SA)$ yields non-trivial and actionable improvements in regret.**\n\n- **Furthermore, an important aspect of our work is also showing that the gain cannot be more than logarithmic without further assumptions, thus fully characterising one aspect of optimal regret under sparsity.**\n\n- **We also emphasize the novelty of the regularizer we propose. In particular, it could be of independent interest to tackle more general sparse problems, specifically since it allows interpolation between the negative entropy and squared Euclidean norm, two common regularizers which induce contrasting behaviors on OMD.**\n\n2. Further, I find that the improvement does not even recover it in the special case of the expert setting (i.e., $S =  1$). On Line 39, the author mention that $\\mathcal{O}(\\sqrt{\\log(A)})$ has been improved to $\\mathcal{O}(\\sqrt{\\log(A^{M/A})})$ in the expert setting. However, letting $S = 1$, the work actually achieves the improvement from $\\mathcal{O}(\\sqrt{\\log(A)})$ to $\\mathcal{O}(\\sqrt{\\log(M)})$. Yet, $\\sqrt{\\log(SA)} \\ge \\sqrt{\\log A^{M/A}}$ for all $M \\in (1,A]$. I would instead suggest the authors investigate whether significant improvements are possible in, e.g., the bandit-feedback setting.\n\n- **This is an interesting point. The notion of sparsity we consider is over the state-action space: $M = \\max_k \\sum_{(s,a) \\in \\Gamma} I[c_k(s,a) > 0]$. However, if we instead consider sparsity at a state-level: $M’ = \\max_{k, s \\in \\mathcal{S}} \\sum_{a \\in \\mathcal{A}} I [c_k(s,a) > 0] \\leq A$, then using negative entropy regularisation and a cumulative loss bound [1], it is fairly straight-forward to show a regret bound of the form (ignoring log-factors) $\\sqrt{K T^\\star \\frac{M’}{A} T^u(s_0)}$, where $T^u(s_0)$ is the hitting time of the uniform policy. This bound recovers the $M/A$ improvement of the expert setting when $S=1$. This result provides some further insights into the performance of OMD with negative entropy regularisation and that in particular issues arise when there is at least 1 state with non-sparse costs even though most other states may have sparse costs.**\n\n- **Now going back to our original notion of sparsity, we know that $M’ \\leq M$. If $M \\leq A$, then we can non-trivially bound $M’$ by $M$ and achieve a regret of $\\sqrt{K T^\\star \\frac{M}{A} T^u(s_0)}$. In particular, if $S = 1$, then this is the case and we can recover the polynomial improvement of the expert setting. The reason we did not include these insights was that bounding $M’$ by $M$ can be loose and if it is known that $S=1$, then applying an experts algorithm is the more obvious choice. However, these subtleties are quite important and we will include a section on this in the appendix of the final version.**\n\n3. Parameter-free case: Theorem 4.3 in this work shows that it is possible to achieve the sparsity-dependent upper bound in the parameter-free case. However, I notice that this only holds for a sufficiently large $K$ (specifically, “$K \\ge MT$”). When the losses are not so “sparse”, this essentially means that $K \\ge SAT$ is required. As such, I think this limits the applicability of the proposed algorithm. \n\n- **We do not view this assumption as restrictive or limiting the applications of the algorithms because these types of bounds are usually considered for sufficiently large $K$ (e.g. in [2], Theorem 9, they have a similar condition $K = \\Omega(SA)$ in the bandit setting). This is also because the study of what is achievable for “small” K (< SA for example) corresponds to a fundamentally different high-dimensional version of the problem. In fact, it is not obvious that sub-linear regret is even achievable in this setting. Therefore we view the condition $K \\ge MT_\\star$ as a mild technical requirement in the parameter-free reduction, ensuring sufficient episodes per batch to learn effectively.**\n\n# Questions\n\nQ1: Could the authors please further explain the intuition on Line 223-229? I do not quite understand why “inducing an OMD update at points near the boundary of the space that can only move to new points in very close proximity” prevents the algorithms from obtaining a sparsity-dependent bound.\n\n- **Here are some more details. In what follows, we use the Euclidean distance as an alternative to measure distances but it could be other types of Bregman divergence such as the one of the regularizer we propose.**\n\n- **The main point is that the negative entropy’s gradient diverges on the boundary of the space. As a result, near the boundary of the space, the Bregman divergence of the negative entropy (the KL) between two points can be very large while those two points are very close in terms of other Bregman divergences like the Euclidean distance. If in a round, the algorithm is playing a point (in our case an occupancy measure) that is very close to the boundary (in terms of Euclidean distance), then the update of the point will be very close to the original point (again in terms of Euclidean distance) because in terms of the KL divergence it is not close. While this property can be crucial in some settings, for sparse problems this appears to be prohibitive because this is the property/intuition we use to design the MDP construction on which OMD with negative entropy regularization fails.**\n\n\n\n\n[1] Zhao, Peng, Long-Fei Li, and Zhi-Hua Zhou. \"Dynamic regret of online Markov decision processes.\" International Conference on Machine Learning. PMLR, 2022.\n\n[2] Chen, Liyu, Haipeng Luo, and Chen-Yu Wei. \"Minimax regret for stochastic shortest path with adversarial costs and known transition.\" Conference on Learning Theory. PMLR, 2021."}, {"review_id": "ejwPUP7vKm", "reviewer": "Reviewer_Txzu", "summary": "The authors study the stochastic shortest path problem under sparsity. In particular, they show the online mirror descent (OMB) with entropy regularization does not take advantage of sparsity in general, and introduce a new family of regularizers which can. With the new regularizers, they prove a bound on the regret of OMB which scales with the sparsity instead of the absolute size of the state space. They also prove a lower bound which matches their upper bound up to logarithmic factors.", "questions": "# Questions: \n- In the definition of D (equation 148) you swap the min and max. Why is this justified? \n- Theorem 3.1 is very interesting. Do you have any idea how common these instances are in which negative-entropy regularization fails to get the right (ie sparse) rate? Is it possible to generalize your proof to a statement such as: For any S, any M and any A, there exists an SSP instance with regret $\\Omega(\\sqrt{DKT_* \\log (SAT_*)})$? That is, showing that for all parameters, there exists an SSP instance which won’t take advantage of the sparsity. \n- Should $K\\geq MT$ be $K\\geq MT_*$ in the statement of theorem 4.3? Otherwise what is T?\n- Couldn’t the bound of Theorem 4.3 be worse than the status quo if K is very large? The second term vanishes, but if K is large enough such that $\\log(\\log(K)\\sqrt{T_\\*}) > \\log(T^\\*SA)$  then theorem 4.3 is looser than $O(DKT_*\\log(SAT^*))$? So perhaps you need to state the result with an upper bound on K as well? \n\n# Minor comments\n- Line 142: “a proper policy” -> “one proper policy” \n- Maybe move line 158 upwards to where you are discussing hitting times? Feels out of place \n- Why does $\\eta$ matter in the statement of Theorem 4.1? It’s just a parameter in the proof no?\n- Missing square root on the regret in line 273 I think", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths \n- Sparsity is a very natural setting to consider. \n- They provide a new algorithm and both upper and lower bounds \n\n# Weaknesses\n- A bit hard to follow for someone who is not an expert in the area \n- Some concerns I have about Theorem 4.3; see below.", "was_revised": true, "final_justification": "Maintaining my original score. I appreciate that the gains are not massive, but they are still gains.", "rebuttal": "We thank the reviewer for their constructive and thorough feedback. We address your comments, suggestions and questions below.\n\n# Weaknesses\n1. A bit hard to follow for someone who is not an expert in the area.\n- **We are aware that this setting of adversarial SSP problems is quite notation-heavy and contains a lot of technical concepts. We tried to present the setting as clearly as possible.**\n\n# Questions\n\nQ1: In the definition of D (equation 148) you swap the min and max. Why is this justified?\n\n- **Sorry for the confusing typo, as the reviewer points out the definition is actually max_{s}min_{\\pi} the correct definition.**\n\nQ2: Theorem 3.1 is very interesting. Do you have any idea how common these instances are in which negative-entropy regularization fails to get the right (ie sparse) rate? Is it possible to generalize your proof to a statement such as: For any S, any M and any A, there exists an SSP instance with regret ? That is, showing that for all parameters, there exists an SSP instance which won’t take advantage of the sparsity.\n\n- **The SSP instance we constructed is specifically designed to make the negative-entropy regularization fail. While we tried other constructions on which it did not always fail, it is unclear how pervasive this behaviour is more generally. We believe it should be possible to extend this result beyond $M = 3$ and $A=2$  but at the expense of an even more tedious analysis so since the purpose of this result was to show that Theorem 4.1 (our sparse upper-bound) cannot be achieved with negative entropy regularization, we presented Theorem 3.1.**\n\nQ3: Should $K > MT$ be $K > MT_\\star$ in the statement of theorem 4.3? Otherwise what is T?\n\n- **This is again a typo sorry, we will fix it in the camera ready.**\n\nQ4: Couldn’t the bound of Theorem 4.3 be worse than the status quo if K is very large? The second term vanishes, but if K is large enough such that  then theorem 4.3 is looser than ? So perhaps you need to state the result with an upper bound on K as well?\n\n- **Yes this correct though usually the parameter free results obtained with expert-like algorithms are consider up to loglog factors (e.g. [3, 4] for references), we will clarify better such a discussion in the camera ready version.**\n\n# Minor comments\n\nWhy does $\\eta$ matter in the statement of Theorem 4.1? It’s just a parameter in the proof no?\n\n- **Yes, it is how the eta is set in the algorithm in order to obtain the result, it is in the theorem statement for completeness.**\n\n- **Thank for you for the useful other minor comments and suggestions - we will amend these in the final version.**\n\n[3] Cutkosky, Ashok, and Francesco Orabona. \"Black-box reductions for parameter-free online learning in banach spaces.\" Conference On Learning Theory. PMLR, 2018.\n\n[4] Jacobsen, Andrew, and Ashok Cutkosky. \"Parameter-free mirror descent.\" Conference on Learning Theory. PMLR, 2022."}, {"review_id": "WUy1fiF5M2", "reviewer": "Reviewer_fyrC", "summary": "The paper addresses adversarial Stochastic Shortest Pash (SSP) with sparse costs under full-information feedback. The main take is that such sparsity should lead to a regret bound scaling with some measure of sparsity of the problem, and not with the space size. Indeed, while negative entropy regularised OMD leads to bounds scaling as SA in general, the authors show that it scales as S on sparse problem. Motivated by this, they propose a new regularisation for OMD (smoothly interpolating between neg-entropy and l2 norm) which leads to a regret scaling with the sparsity of the problem. Additionally, the authors instantiate a parameter-free version of the same algorithm that does not require knowledge of the sparsity level nor the hitting time of the optimal policy. Finally, the authors show lower bounds ( for some regimes of the sparsity factor M) matching the upper bound over these instances. The authors also show that this bound does not hold under bandit feedback, in which the M factor is substituted by SA again, regardless of the sparsity, suggesting that without further assumptions, sparsity cannot be exploited effectually under non-full feedback settings.\n\n\n**Overall Motivation for Rating**:\n\nIn general, I am not strongly leaning towards accept just because (1) I have *not* carefully read the proofs and (2) I have some knowledge of the related works but I would not call me an expert. My current score will change conditioned on: a satisfactory rebuttal showing that my questions are not so well founded; whether other reviewers raise some major concerns I was not aware of but I might agree with ex-post.", "questions": "- The lower bound goes towards non-sparse problem more than sparse ones, as it holds for M > 100. Do the authors have a take on this, or some intuition on what could happen for sparser problem (M<100)?\n- Can the authors better articulate on the limitations suggested by Thm 5.1? Which sub-portions of the algorithmic solutions could be nonetheless employed for unknown transition settings?\n\nMy current score will be undergo the following changes:\n- increased: whether my questions will be addressed properly, and further discussions about them will be included in the manuscript.\n- decreased: whether other reviewers raise some *major* concerns I was not aware of but I might agree with post discussion.\n- Kept the same: whether the answers were not addressed.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "In the following, I will refer to Strengths with (S) and Weaknesses with (W), line numbering with (l#)\n\n**Quality**: \n\n(S) The work reaches a good quality overall and it is self-sufficient in covering a problem and pointing to limitations and next step.\n\n**Clarity**:\n\n(S) The paper is extremely well written, it does introduce all the concepts clearly and it does address all the relevant limitations.\n\n(Minor W) I would format equation under l170 over a single line.\n\n**Significance**: \n\n(Minor W) Full-information feedback might sound limiting, yet I believe that (S) a formal characterisation of the problem is still relevant and provides an important stepping stone towards more realistic settings, and the authors provided enough tools to go towards this direction.\n\n**Originality**:\n\n(S) The proposed regularisation is interesting and novel (as far as I am aware of), and the counterexamples on standard neg-entropy OMD limitations are a pretty nice rethorical tool.\n(Very Minor W) Most of the other proof structures of the lower bounds are based on previous works, which is yet pretty common.", "was_revised": true, "final_justification": "The paper addresses a relevant problem and introduces an interesting analyses, and as all my concerns were addressed in the rebuttal phase I am positive to raise my score from 4 to 5. \nNonetheless, I missed some relevant typos and factors noted by other reviewers, thus I might not be able to champion this paper with high confidence, I might need a discussion with other reviewers then.", "rebuttal": "We thank the reviewer for their thorough feedback. We address your comments and question below.\n\n# Weaknesses:\n\n1. (Minor W) I would format equation under l170 over a single line.\n\n- **Thank you for this suggestion.**\n\n# Questions\n\nQ1: The lower bound goes towards non-sparse problem more than sparse ones, as it holds for M > 100. Do the authors have a take on this, or some intuition on what could happen for sparser problem (M<100)?\n \n- **We don’t believe that this condition on $M > 100$ is necessary. It appears from the technical result on the expectation of the maximum of $d$ asymmetric zero-mean random-walks (Theorem F.1). We prove this result for $d \\geq 100$ but do not believe this condition is necessary. The bottleneck is really this specific technical result and provided a more refined analysis of this expectation becomes available, this would immediately apply to our SSP lower-bound. However, achieving this refined result is a highly technical non-trivial task.**\n\nQ2: Can the authors better articulate on the limitations suggested by Thm 5.1? Which sub-portions of the algorithmic solutions could be nonetheless employed for unknown transition settings?\n\n- **Theorem 5.1 highlights a key limitation in the unknown transitions setting: it establishes that sparsity in the MDP structure does not eliminate the $\\sqrt{SA}$ dependence in the regret bound, even in sparse instances. This result is somewhat surprising, as it suggests that the learner cannot leverage sparsity to bypass the worst-case dependence on the size of the state-action space.**\n\n- **Nonetheless, this lower bound does not preclude the possibility that sparsity may still offer improvements within the unavoidable dependence, it could indeed still reduce the polynomial dependence though not completely remove it. In this sense, components of our algorithm, including our sparsity-aware regularizer, could still be beneficial in the unknown-transition setting, even if the full elimination of $\\sqrt{SA}$ is not possible.**\n\n- **Our decision not to explore this setting comes also from the fact that even in the non-sparse case, the optimal regret bound is still an open question, with a polynomial gap of $\\sqrt{S}$ between the best known upper and lower bound [5] . Without a minimax characterization of the optimal non-sparse regret, it is premature to rigorously quantify the gains brought by sparsity. We included Theorem 5.1 primarily to provide a conceptual insight: while sparsity helps in the main setting we considered, it does not change the fundamental lower bound structure in the unknown transition case, reinforcing the complexity of the problem.**\n\n- **Further work is needed to understand which algorithmic techniques remain effective under unknown transitions, and how sparsity can be exploited in this regime.**\n\n\n[5] Chen, Liyu, and Haipeng Luo. \"Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case.\" International Conference on Machine Learning. PMLR, 2021."}]

Author rebuttal:

Meta-review: This work studies an important problem in online/reinforcement learning known as Stochastic Shortest Paths. The focus is on investigating the role of sparsity of costs in regret bounds. The main contributions include the observation that (logarithmic) scaling with the full action space is inherent to entropic mirror-descent algorithms, while a different regularizer, based on the p-norm attains bounds scaling logarithmically with sparsity. Reviewers appreciate the technical novelty of the work, but have serious concerns about its relevance: some of the assumed bounds on the instance parameter may render this algorithm inapplicable to any reasonable instance. 

Despite these concerns, I believe the technical parts of this work are solid contributions. Furthermore, once the theoretical possibilities are established, follow up work can concentrate on mitigating these limitations, and turning these ideas into practical methods.

I recommend acceptance of this paper, but I encourage authors to take the following steps for their final version:
1. Include a thorough discussion about limitations and challenges towards making the algorithm practical. I think this could be a good instance to perhaps propose some interesting open problems.
2. To my knowledge, the "novel regularizer" (4) has been used for decades in convex optimization. Versions of it can be traced back to the Nemirovski-Yudin monograph, and it can be found more explicitly in recent surveys, e.g. https://www2.isye.gatech.edu/~nemirovs/ActaFinal_2013.pdf. It seems to me that this regularizer may also have connections with Tsallis entropy. My suggestion is then to put this regularization idea in perspective, and cite some relevant works.
Decision: Accept (poster)