We thank the reviewer for their thorough feedback. We address your comments and question below.

Weaknesses:

1. (Minor W) I would format equation under l170 over a single line.

• Thank you for this suggestion.

Questions

Q1: 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)?

• 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.

Q2: 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?

• 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.

• 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.

• 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.

• Further work is needed to understand which algorithmic techniques remain effective under unknown transitions, and how sparsity can be exploited in this regime.

[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.

We thank the reviewer for their constructive and thorough feedback. We address your comments, suggestions and questions below.

Weaknesses

1. A bit hard to follow for someone who is not an expert in the area.

• 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.

Questions

Q1: In the definition of D (equation 148) you swap the min and max. Why is this justified?

• Sorry for the confusing typo, as the reviewer points out the definition is actually max_{s}min_{\pi} the correct definition.

Q2: 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.

• 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.

Q3: Should $K > MT$ be $K > MT_\star$ in the statement of theorem 4.3? Otherwise what is T?

• This is again a typo sorry, we will fix it in the camera ready.

Q4: 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?

• 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.

Minor comments

Why does $\eta$ matter in the statement of Theorem 4.1? It’s just a parameter in the proof no?

• 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.

• Thank for you for the useful other minor comments and suggestions - we will amend these in the final version.

[3] Cutkosky, Ashok, and Francesco Orabona. "Black-box reductions for parameter-free online learning in banach spaces." Conference On Learning Theory. PMLR, 2018.

[4] Jacobsen, Andrew, and Ashok Cutkosky. "Parameter-free mirror descent." Conference on Learning Theory. PMLR, 2022.

We thank the reviewer for their thorough feedback. We address your comments and question below.

Weaknesses

1. 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.

• 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.

• 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.

• 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.

2. 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.

• 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.

• 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.

3. 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.

• 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.

Questions

Q1: 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.

• 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.

• 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.

[1] Zhao, Peng, Long-Fei Li, and Zhi-Hua Zhou. "Dynamic regret of online Markov decision processes." International Conference on Machine Learning. PMLR, 2022.

[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.