Non-stationary Bandit Convex Optimization: A Comprehensive Study

1. Novelty and contributions of this work, and differences from existing work

Thank you for this constructive feedback. While non-stationary Bandit Convex Optimization has been studied before [7, 13, 14, 33], our work provides the following meaningful advances:

Unifying study: Attaining optimal performance for general non-stationary Convex Bandit Optimization is hard (see point 3 below), and the field currently lacks a comprehensive, unified treatment. Existing works study different aspects of the problem in isolation: [7, 14] focus on dynamic regret $R^{\text{dyn}}(T, \Delta)$, while [13, 33] address path-length regret $R^{\text{path}}(T, P).$ As we illustrate in Fig. 1 and formalize in Proposition 1, the dynamic regret and path-length regret can both be upper bounded using the switching regret $R^{\text{swi}}(T, S)$, but the reverse does not necessarily hold, suggesting that our results may be more fundamental. This work is the first to systematically unify and extend previously scattered results, establishing a complete picture of the state-of-the-art. We also prove lower bounds and derive parameter-free guarantees by applying the Bandit-over-Bandit framework, which offer baselines for future research on this topic.

Technical contributions: Our proposed algorithms represent rigorous adaptations of established techniques, as detailed in lines 115-127 for TEWA-SE and lines 128-135 for cExO. Both algorithms build upon long lines of prior work.

• TEWA-SE: We adapt sleeping experts and MetaGrad-type adaptivity techniques from Online Convex Optimization [21-23] to the bandit setting. Key modifications include replacing exact gradients with one-point bandit gradient estimates, and designing a quadratic surrogate function (see point 2 below). These adaptations require non-trivial technical work, including careful bias-variance trade-offs and detailed analysis of tilted exponentially weighted averaging with noisy gradient estimates.
• cExO: The cExO algorithm builds on the exploration by optimization approach from [27] by adding a novel clipping step. Though not polynomial-time computable, cExO achieves the first minimax-optimal result for switching regret and dynamic regret w.r.t. $T, S$ and $\Delta$.

Moreover, to clarify how our work differs from prior work, we would like to emphasize the following points:

• The reduction from $R^{\text{path}}(T, P)$ to $R^{\text{swi}}(T, S)$ in Proposition 1 is new and employs simple geometric arguments (see Lemma 1 and its proof from line 863). To better position our work relative to existing work, we will add a remark discussing this reduction technique and referencing [17], noting that while our unified approach through $R^{\text{swi}}(T, S)$ simplifies the analysis of $R^{\text{path}}(T, P)$, it may yield slightly looser bounds on $R^{\text{path}}(T, P)$ compared to direct analysis.
• We detail in point 2 below how the quadratic surrogate loss we tailored for TEWA-SE differs from its direct precursor in [23]. We will also emphasize this in the revised manuscript.
• To our knowledge, the $d^{\frac{4}{5}}P^{\frac{2}{5}}T^{\frac{3}{5}}$ lower bound for path-length regret in Theorem 4 is new and improves upon the only existing result, the $d\sqrt{PT}$ lower bound from [13, Theorem 5], w.r.t. $T$. This is attained by leveraging a different construction of a hard instance of loss functions.

2. Differences between TEWA-SE and prior work

Thank you for this comment. You are right that TEWA-SE builds on Zhang et al. [23] from Online Convex Optimization, which allows access to exact gradients. Apart from replacing exact gradients with one-point gradient estimates, we have also made a technical adaptation in the surrogate loss for TEWA-SE which we will explain more explicitly in the revised manuscript. While Zhang et al. [23] and the original MetaGrad paper [21] use $\eta^2||\boldsymbol{g}_t||^2||\boldsymbol{x}_t-\boldsymbol{x}||^2$ and $\eta^2(\boldsymbol{g}_t^\top(\boldsymbol{x}_t-\boldsymbol{x}))^2$ as the quadratic term for the surrogate loss, we use $\eta^2 G^2||\boldsymbol{x}_t-\boldsymbol{x}||^2$ in our surrogate loss $\ell_t^\eta(\boldsymbol{x})=-\eta\boldsymbol{g}_t^\top(\boldsymbol{x}_t-\boldsymbol{x})+\eta^2G^2||\boldsymbol{x}_t-\boldsymbol{x}||^2$ in (11), where $G$ is a high probability upper bound on $||\boldsymbol{g}_t||$ as in (10).

The surrogate loss from [23] or [21] necessitates an additional condition relating $\mathbb{E}[||\boldsymbol{g}_t||]$ and $\mathbb{E}[||\boldsymbol{g}_t||^2]$ (or $\mathbb{E}[\boldsymbol{g}_t\boldsymbol{g}_t^\top]$) to be satisfied in the analysis, see e.g. [21, Theorem 2]. When working with tilted exponentially weighted average with noisy gradient estimates, directly using their quadratic term would complicate the proof. Our choice of the quadratic term, inspired by [22], simplifies this particular aspect of the proof.

3. Why harder to achieve optimality in non-stationary convex bandits than in multi-armed bandits

Thank you for this insightful comment. As we detail in lines 136-141, the techniques that achieve optimal regret in multi-armed bandits under non-stationarity (with known non-stationarity measures) cannot be directly applied to Bandit Convex Optimization (BCO). The continuous action space in BCO requires fundamentally different approaches.

Achieving optimal time-dependence in BCO is challenging even for static regret, as noted in lines 130-132 and in point 2 of the review by Reviewer NBQt. The current state-of-the-art Fokkema el al. (2024) and Suggala et al. (2024) use the bandit version of the online Newton step for stochastic unconstrained BCO from Lattimore and György (2023) to achieve the optimal $\sqrt{T}$ time dependence (modulo polylogarithms). It remains unclear whether first-order methods, including our proposed TEWA-SE algorithm, can achieve the optimal rate, especially in the more challenging non-stationary environments. We will add a brief discussion on this before the "Conclusion" section in the revised manuscript.

To handle non-stationary environments, an interesting future direction is to combine TEWA-SE's aggregation mechanism with second-order expert algorithms similar to that in Fokkema et al. (2024) and Suggala et al. (2024). Another idea is to explore whether incorporating a restart criterion, similar to line 11 of Algorithm 1 in Fokkema et al. (2024) or line 15 of Algorithm 1 in Suggala et al. (2021), could enable change-detection and improve regret guarantees compared to TEWA-SE.

References:

• Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, and Jack J Mayo. Online newton method for bandit convex optimisation. In Conference on Learning Theory, pages 1713–1714. PMLR, 2024.
• Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, and Elad Hazan. Second order methods for bandit optimization and control. In Conference on Learning Theory, pages 4691–4763. PMLR, 2024.
• Tor Lattimore and András György. A second-order method for stochastic bandit convex optimisation. In Conference on Learning Theory, pages 2067–2094. PMLR, 2023.
• Arun Sai Suggala, Pradeep Ravikumar, and Praneeth Netrapalli. Efficient bandit convex optimization: Beyond linear losses. In Conference on Learning Theory, pages 4008–4067. PMLR, 2021.
• (Numbered references above correspond to the bibliography in the submitted manuscript.)

1. Optimal dependence on strong-convexity parameter $\alpha$

Thank you for this insightful question. To the best of our knowledge, the optimal dependence on the strong convexity parameter $\alpha$ remains an open question with some intriguing gaps between upper and lower bounds.

For static regret in adversarial Bandit Convex Optimization, the two tightest lower bounds we are aware of are [68, Theorem 7] by Shamir, which gives a $d\sqrt{T}$ lower bound with no dependence on $\alpha$, and [67, Theorem 6.1] by Akhavan et al. (with Hölder exponent equals 2), which implies a lower bound on the order of $d\sqrt{T}/\max(\alpha,1)$.

• For $\alpha\lesssim 1$, the latter reduces to $d\sqrt{T}$ independent of $\alpha$, while existing upper bounds from [32, 69] achieve $d\sqrt{T}/\sqrt{\alpha}$. This suggests that the $1/\alpha$ dependence in our adaptive regret upper bound (15) in Theorem 1 is likely suboptimal.
• For $\alpha\gtrsim 1$, our $d\sqrt{\textsf{B}}/\alpha$ adaptive regret upper bound in (15) appears to match the $d\sqrt{T}/\alpha$ lower bound from [67]. However, this comparison is not definitive because both results suppress dependence on the smoothness parameter, which could affect the true relationship between these bounds.

To improve clarity, we will update the sentence starting on line 214 to read: "We further note that our bound for the strongly-convex case has a $\tfrac{1}{\alpha}$ dependency, which is suboptimal compared to the $\frac{1}{\sqrt{\alpha}}$ dependency in [32, 69] for static regret in BCO for $\alpha\lesssim 1$."

2. Adaptive regret of $\mathcal{O}(\textsf{B}^{\frac{2}{3}})$ via alternative choice of $h$ in (34) for convex and smooth functions

Thank you for this important comment. We appreciate the opportunity to clarify the assumptions and scope of our results. Our results for TEWA-SE address two cases: (i) general convex and Lipschitz functions, and (ii) the special case of strongly-convex and smooth functions. Importantly, the presented results for the convex case do not exploit smoothness assumptions. We will clarify this in the main text of the revised manuscript, rather than relegating it to footnote 1 on p.3.

Convex and Lipschitz functions: For this setting, $\sqrt{d}T^{\frac{3}{4}}$ is a classical static regret rate in bandit optimization, see e.g., [24, Theorem 3.3]. Since our TEWA-SE algorithm employs the one-point gradient estimate from [24], our adaptive regret upper bound in (34) naturally inherits a leading term of order $\sqrt{d}\textsf{B}^{\frac{3}{4}}$.

For brevity, our current manuscript proves the upper bounds for TEWA-SE for both the general convex case and the strongly-convex case using smoothness assumptions, with footnote 1 noting that the convex case guarantee can alternatively be obtained using only Lipschitz-continuity. In the revised manuscript, we will restructure our proofs to match the minimal assumptions: (i) prove the general convex case directly using only Lipschitz-continuity, and (ii) separately prove the strongly-convex case using smoothness.

In the revised proof for the convex case, the smoothness-dependent term $\beta(q-p+1)h^2$ in (34) will be replaced by $2L(q-p+1)h$ under the Lipschitz-only assumption, where $L$ denotes the Lipschitz constant. Using our current parameter choice $h=\sqrt{d}\textsf{B}^{-\frac{1}{4}}$, we will have $2L(q-p+1)h\lesssim\sqrt{d}\textsf{B}^{\frac{3}{4}}$, which preserves the same $\sqrt{d}\textsf{B}^{\frac{3}{4}}$ rate from the original analysis.

Convex and smooth functions: To avoid confusion, the revised manuscript will focus exclusively on cases (i) and (ii) described above. However, to answer your separate questions about convex and smooth functions:

• Clarification on $\textsf{B}^{\frac{2}{3}}$ rate: You are correct that choosing $h=d^{\frac{1}{3}}\textsf{B}^{-\frac{1}{6}}$ in (34) which currently assumes convexity and smoothness would yield an adaptive regret of order $d^{\frac{2}{3}}\textsf{B}^{\frac{2}{3}}$. The $\textsf{B}^{\frac{2}{3}}$ term aligns with the time-dependence in the static regret upper bound of [29, Theorem 3].
• Clarification on choice of $h$: TEWA-SE is designed to adapt to unknown curvature of the loss functions. Therefore, it is not feasible to choose different $h$ a priori for different functions, e.g., $h=d^{\frac{1}{3}}\textsf{B}^{-\frac{1}{6}}$ if the functions are convex and smooth, or $h=\sqrt{d}\textsf{B}^{-\frac{1}{4}}$ if they are strongly-convex and smooth. Our current proof uses $h=\sqrt{d}\textsf{B}^{-\frac{1}{4}}$ throughout. While fixing $h=d^{\frac{1}{3}}\textsf{B}^{-\frac{1}{6}}$ would yield a $d^{\frac{2}{3}}\textsf{B}^{\frac{2}{3}}$ adaptive regret for the convex case, this would compromise the minimax-optimality we achieve for the strongly-convex case in switching regret and dynamic regret.

3. Alternative choice of $h$ for parameter-free adaptive regret and path-length regret

Thank you for this detailed question. We respond to your question point-to-point:

• You are correct that $h$ is the only parameter of TEWA-SE that is tuned using the non-stationarity measures such as $S, \Delta$ and $P$. As you note, choosing $h$ to be order of $T^{-\frac{1}{6}}$ independently of $\textsf{B}$ would yield an adaptive regret of $\textsf{B}^{\frac{1}{2}}T^{\frac{1}{6}}$ in (34) for the convex and smooth case, and $\textsf{B}T^{-\frac{1}{3}}+T^{\frac{1}{3}}$ in (41) for the strongly-convex and smooth case. However, this approach sacrifices the minimax-optimality of switching regret and dynamic regret in the strongly-convex setting.
• We should clarify that our tuning of $h$ does not require knowledge of the smoothness parameter $\beta$.
• Regarding your derivation of the parameter-free path-length regret, thank you for working through this analysis. If we understand correctly, your expressions (modulo a typo) were obtained through the following steps:

$

R^{\text{path}}(T, P) &\stackrel{\text{(a)}}{\le}R^{\text{swi}}(T, S')+\tfrac{P}{r}\big\lceil\tfrac{T}{S'}\big\rceil\\ &\stackrel{\text{(b)}}{\le} 2 S'\cdot R^{\text{ada}}(\big\lceil \tfrac{T}{S'}\big\rceil, T) + \tfrac{P}{r}\big\lceil \tfrac{T}{S'}\big\rceil\\ &\stackrel{\text{(c)}}{\lesssim} S'\cdot \Big(\tfrac{d}{h}\sqrt{\tfrac{T}{S'}} + \tfrac{T}{S'}h^2\Big) + \tfrac{P}{r}\tfrac{T}{S'}\\ &\stackrel{\text{(d)}}{\lesssim}Th^2+P^{\frac{1}{3}}T^{\frac{2}{3}}h^{-\frac{2}{3}},

$

where (a) applies Proposition 1, (b) converts adaptive to switching regret as we do on line 860 (Lemma 1), (c) substitutes the adaptive regret bound from (34), and (d) optimizes by choosing $S'=P^{\frac{2}{3}}T^{\frac{1}{3}}h^{\frac{2}{3}}$. Finally, setting $h$ to be of order $T^{-\frac{1}{8}}$ simplifies the bound above into $P^{\frac{1}{3}}T^{\frac{3}{4}}$. While this approach avoids tuning $h$ based on $P$, it still requires knowledge of $P$ to set $S'$. In contrast, the presented Bandit-over-Bandit (BoB) approach is truly parameter-free by using an adversarial bandit algorithm to adaptively select $h$ for TEWA-SE in each epoch, without prior knowledge of any non-stationarity measures.

• If we instead set $S'=T^{\frac{1}{3}}h^{\frac{2}{3}}$ independent of $P$ in step (d), the resulting bound becomes $PT^{\frac{3}{4}}$, which scales linearly in $P$. When $P$ is small, this bound is tighter than our $P^{\frac{1}{5}}T^{\frac{4}{5}}+T^{\frac{5}{6}}$ bound obtained using BoB. However, it becomes vacuous when $P\gtrsim T^{\frac{1}{4}}$. Our goal is to provide a non-vacuous bound for all $P=o(T)$, which BoB achieves.

4. Polynomial-time complexity of TEWA-SE

Yes, the computational complexity of TEWA-SE is $\mathcal{O}(\log^2 T)$ per round, as we reasoned in the paragraph containing equation (26) and stated below it. We describe this as polynomial-time because the overall computational complexity across the entire time horizon $T$ is polynomial in $T$.

5. Response to remark on $B^d$ vs. $\textsf{B}$ notation

Thank you. To distinguish from the parameter $\textsf{B}$ in TEWA-SE, we will use $\mathbb{B}^d$ and $\partial \mathbb{B}^d$ to denote the unit ball and unit sphere in the revised manuscript.

References: Numbered references above correspond to the bibliography in the submitted manuscript.

1. Reasons for slack between upper and lower bounds for path-length regret for cExO

Thank you for this insightful comment. As far as we can see, there are three potential sources of slack between our upper and lower bounds for cExO: (i) our lower bound construction in Theorem 4 may not be tight, (ii) the cExO algorithm design itself may be suboptimal, or (iii) our upper bound analysis may have introduced looseness through the reduction result in Proposition 1, which bounds path-length regret $R^{\text{path}}(T, P)$ through switching regret $R^{\text{swi}}(T, S)$. We examine each in turn:

• (i) Though our $d^{\frac{4}{5}}P^{\frac{2}{5}}T^{\frac{3}{5}}$ lower bound shows better $T$-dependence than the $d\sqrt{PT}$ from [13, Theorem 5] (the only other result in the literature), we are unsure about the true minimax rate. While we also don't see slack in the lower bound, a $T^\frac{3}{5}$ rate is uncommon and we wouldn't be surprised if the cExO upper bound is tight.
• (ii) Alternatively, a potential source of sub-optimality in cExO stems from the fact that cExO performs OMD over the distribution space rather than directly over the action set. The latter would allow us to derive path-length regret bounds more directly.
• (iii) Our Proposition 1 unifies the regret analysis by bounding $R^{\text{path}}(T, P)$ and $R^{\text{dyn}}(T, \Delta)$ through $R^{\text{swi}}(T, S)$. However, this simple approach may yield slightly looser bounds for $R^{\text{path}}(T, P)$ compared to direct analysis, as noted in [17].

We will include a brief discussion on the above in the revised manuscript.

2. MetaGrad combined with convolution-based estimator from Bubeck et al. (2017)

Thank you for this thoughtful suggestion. As you note, MetaGrad is a first-order algorithm, where the quadratic term $\eta^2(\boldsymbol{g}_t^\top(\boldsymbol{x}_t-\boldsymbol{x}))^2$ in the surrogate loss uses only a simple outer product of the gradient estimate $\boldsymbol{g}_t\in\mathbb{R}^d$. Our TEWA-SE adaptation of MetaGrad inherits this first-order property, which is likely the reason why it achieves optimal rates for strongly-convex functions, but cannot attain optimality for general convex functions without incorporating second-order information. We will add a brief discussion on this before the "Conclusion" section in the revised manuscript.

The kernel-based (or convolution-based) estimator from Bubeck et al. (2017) offers a promising approach to address this limitation. It adaptively exploits second-order structure through the covariance of the current exponential weights distribution, essentially capturing the geometry of where the algorithm currently believes the optimum lies. Replacing the simple gradient outer product with this adaptive kernel-based estimator as the quadratic term in TEWA-SE's surrogate loss could in theory improve our regret bounds. However, implementing this integration would require careful analysis of how the kernel-based estimates interact with TEWA-SE's sleeping experts framework. This is an interesting direction for future work.

More broadly, your suggestion of leveraging second-order methods is very promising. Given that the online Newton methods from Fokkema et al. (2024) and Suggala et al. (2024) provide the state-of-the-art static regret for adversarial convex bandits, a natural future direction is to extend such methods to non-stationary environments.

3. Second-order methods and tracking capabilities

Thank you for this insightful question. In a setting similar to ours, we are not aware of any existing work that uses second-order methods to track changes in the environment for the purpose of minimizing switching, dynamic, or path-length regret. We would be grateful if you could point us to any such work. Nevertheless, a promising direction could be to incorporate a restart criterion, similar to the one used in line 15 of Algorithm 1 in Suggala et al. (2021), or line 11 of Algorithm 1 in Fokkema et al. (2024), which may enable tracking capabilities and potentially yield improved regret guarantees.

4. Response to remark on missing references

Thank you for pointing out two missing references in Bandit Convex Optimization (BCO). We will include both papers at line 108 in the revised manuscript.

Indeed, Suggala et al. (2024) appeared concurrently with Fokkema et al. (2024) and presents an online Newton step algorithm that achieves optimal $\sqrt{T}$ static regret for a class of convex functions with well-conditioned Hessians. Both Suggala et al. (2024) and Fokkema et al. (2024) build upon the bandit version of the online Newton step for stochastic unconstrained BCO from Lattimore and György (2023), which we will also reference at line 108. Finally, the restart condition in Fokkema et al. (2024) is derived from Suggala et al. (2021), making the latter a key reference for understanding the historical connections.

References:

• Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 72–85, 2017.
• Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, and Jack J Mayo. Online newton method for bandit convex optimisation. In Conference on Learning Theory, pages 1713–1714. PMLR, 2024.
• Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, and Elad Hazan. Second order methods for bandit optimization and control. In Conference on Learning Theory, pages 4691–4763. PMLR, 2024.
• Tor Lattimore and András György. A second-order method for stochastic bandit convex optimisation. In Conference on Learning Theory, pages 2067–2094. PMLR, 2023.
• Arun Sai Suggala, Pradeep Ravikumar, and Praneeth Netrapalli. Efficient bandit convex optimization: Beyond linear losses. In Conference on Learning Theory, pages 4008–4067. PMLR, 2021.
• (Numbered references above correspond to the bibliography in the submitted manuscript.)

Response to remarks on organization and presentation

Thank you for your constructive feedback. We aimed to provide a comprehensive study because the field currently lacks a unfied treatment of non-stationary Convex Bandit Optimization. However, we agree that the presentation could be made more accessible.

As we note in lines 105-114, existing works study different aspects of the problem in isolation: [7, 14] focus on dynamic regret $R^{\text{dyn}}(T, \Delta)$, while [13, 33] address path-length regret $R^{\text{path}}(T, P)$. As we illustrate in Fig. 1 and formalize in Proposition 1, the dynamic regret and path-length regret can both be upper bounded using the switching regret $R^{\text{swi}}(T, S)$, but the reverse does not necessarily hold, suggesting that our results may be more fundamental. This work is the first to systematically unify and extend previously scattered results, establishing a complete picture of the state-of-the-art. We also prove lower bounds and derive parameter-free guarantees.

In the revision, we will emphasize in the "Introduction" section before Section 1.1 that adaptive regret $R^{\text{ada}}(\textsf{B}, T)$ and switching regret $R^{\text{swi}}(T, S)$ are the primary focus of this work, and that dynamic regret and path-length regret can be bounded using $R^{\text{ada}}(\textsf{B}, T)$ and $R^{\text{swi}}(T, S)$. We will expand our discussion of Fig. 1 which visually clarifies the conversions between different regret notions. We will also expand Section 1.3 where we formally present the conversion results (Proposition 1) to provide clearer intuition before diving into technical details.

References: Numbered references above correspond to the bibliography in the submitted manuscript.

1. Response to remarks on novelty of TEWA-SE and connections to prior work

Thank you for this comment.

TEWA-SE: Indeed, our proposed TEWA-SE algorithm represents rigorous adaptations of established techniques, as detailed in lines 115-127. We adapt sleeping experts and MetaGrad-type adaptivity techniques from Online Convex Optimization [21-23] to the bandit setting. Key modifications include replacing exact gradients with one-point bandit gradient estimates, and designing a quadratic surrogate function. These adaptations require non-trivial technical work, including careful bias-variance trade-offs and detailed analysis of tilted exponentially weighted averaging with noisy gradient estimates.

To further clarify how TEWA-SE differs from its precursor [23], we would like to emphasize that our surrogate loss design differs from both [23] and the original MetaGrad paper [21]. We will describe this more explicitly in the revised manuscript. While [23] and [21] use $\eta^2||\boldsymbol{g}_t||^2||\boldsymbol{x}_t-\boldsymbol{x}||^2$ and $\eta^2(\boldsymbol{g}_t^\top(\boldsymbol{x}_t-\boldsymbol{x}))^2$ as the quadratic term for the surrogate loss, we use $\eta^2G^2||\boldsymbol{x}_t-\boldsymbol{x}||^2$ in our surrogate loss $\ell_t^\eta(\boldsymbol{x})=-\eta\boldsymbol{g}_t^\top(\boldsymbol{x}_t-\boldsymbol{x})+\eta^2G^2||\boldsymbol{x}_t-\boldsymbol{x}||^2$ in (11), where $G$ is a high probability upper bound on $||\boldsymbol{g}_t||$, as shown in (10).

The surrogate loss from [23] or [21] necessitates an additional condition relating $\mathbb{E}[||\boldsymbol{g}_t\|]$ and $\mathbb{E}[||\boldsymbol{g}_t||^2]$ (or $\mathbb{E}[\boldsymbol{g}_t\boldsymbol{g}_t^\top]$) to be satisfied in the analysis, see e.g., [21, Theorem 2]. When working with tilted exponentially weighted average with noisy gradient estimates, directly using their quadratic term would complicate the proof. Our choice of the quadratic term, inspired by [22], simplifies this particular aspect of the proof.

Broader connections to prior work: Attaining optimal performance for general non-stationary Convex Bandit Optimization is hard, and the field currently lacks a comprehensive, unified treatment. Existing works study different aspects of the problem in isolation: [7, 14] focus on dynamic regret $R^{\text{dyn}}(T, \Delta)$, while [13, 33] address path-length regret $R^{\text{path}}(T, P).$ As we illustrate in Fig. 1 and formalize in Proposition 1, the dynamic regret and path-length regret can both be upper bounded using the switching regret $R^{\text{swi}}(T, S)$, but the reverse does not necessarily hold, suggesting that our results may be more fundamental. This work is the first to systematically unify and extend previously scattered results, establishing a complete picture of the state-of-the-art. We also prove lower bounds and derive parameter-free guarantees by applying the Bandit-over-Bandit framework, which offer baselines for future research on this topic.

Furthermore, to clarify how our work compares with prior work, we would like to emphasize the following points:

• The reduction from $R^{\text{path}}(T, P)$ to $R^{\text{swi}}(T, S)$ in Proposition 1 is new and employs simple geometric arguments (see Lemma 2 and its proof from line 863). To better position our work relative to existing work, we will add a remark discussing this reduction technique and referencing [17], noting that while our unified approach through $R^{\text{swi}}(T, S)$ simplifies the analysis of $R^{\text{path}}(T, P)$, it may yield slightly looser bounds on $R^{\text{path}}(T, P)$ compared to direct analysis.
• To our knowledge, the $d^{\frac{4}{5}}P^{\frac{2}{5}}T^{\frac{3}{5}}$ lower bound for path-length regret in Theorem 4 is new and improves upon the only existing result, the $d\sqrt{PT}$ lower bound from [13, Theorem 5], w.r.t. $T$. This is attained by leveraging a different construction of a hard instance of loss functions.

2. Response to remark on limitations of cExO

The cExO algorithm builds on a long line of work, as detailed in lines 128-135 of our manuscript. Specifically, it adapts the exploration by optimization approach from [27] by adding a novel clipping step. Though not polynomial-time computable, cExO achieves the first minimax-optimal result for switching regret and dynamic regret w.r.t. $T, S$ and $\Delta$. Moreover, obtaining optimal regret guarantees in non-stationary environments is inherently more challenging than in the static setting. The suboptimal dependence on $d$ in our upper bound is unsurprising since even the best known static regret bounds of Fokkema et al. (2024) and Suggala et al. (2024) suffer from similar dimensional dependence.

References:

• Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, and Jack J Mayo. Online newton method for bandit convex optimisation. In Conference on Learning Theory, pages 1713–1714. PMLR, 2024.
• Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, and Elad Hazan. Second order methods for bandit optimization and control. In Conference on Learning Theory, pages 4691–4763. PMLR, 2024.
• (Numbered references above correspond to the bibliography in the submitted manuscript.)