Non-Stationary Lipschitz Bandits

We thank the reviewer for the careful analysis.

Differences with Suk and Kpotufe (2023)

While it is true that Suk and Kpotufe (2023) also operate in blocks and discretize the context space accordingly, their estimation strategy does not involve multi-scale replays. Once the context is discretized and observed, their analysis focuses on estimating the mean rewards of a fixed and finite set of $K$ actions, using replays of these same actions. Our algorithm must face three fundamental challenges: (i) scheduling (potentially simultaneous) replays at different depths, (ii) leveraging the information collected across different scales, and (iii) tracking the regret contribution from all scales simultaneously. In our regret analysis, each action $x_t \in [0,1]$ belongs to several bins across discretization levels, and we explicitly quantify the regret incurred at each scale. Moreover, to decide which bin to activate at a given depth and time step, we introduce a principled strategy for (a) scheduling replays at specific scales and (b) selecting the appropriate bin at a given active depth through a carefully designed sampling algorithm.

We will incorporate this discussion at the beginning of the proof sketch in Section 5 to clarify the novelty and technical depth of our theoretical contribution.

$\log(T)$ in the definition of significant shift

While it is true that previous works do not include a logarithmic factor in the definition of a significant shift (e.g. Suk and Kpotufe 2022), we observe that incorporating a $\log(T)$ term has no impact on the regret analysis, while leading to a strictly sharper metric: the number of significant shifts can only decrease with the added log factor, making the metric sharper.

On restarts at each block

Restarting estimates at the beginning of each block is primarily a theoretical simplification that facilitates a clean application of the doubling trick (see line 625 of our supplementary material). This strategy simplifies the regret decomposition and analysis, at the expense of only a constant numerical factor in the regret bound.

Presentation

We thank the reviewer for pointing out this presentation issue. If the paper is accepted, we will use the additional allowed page in the supplementary material to include visual illustrations of the dyadic tree structure in the main text to improve clarity.

Extension to smooth bandits (same answer as scsD and kQLa)

Our algorithm and analysis can easily be adapted beyond $1$-Lipschitz reward function, and still enjoy minimax optimal rate. For the sake of space, we give a sketch of proof of this generalization (similarly to Appendix G for the multi-dimensional setting).

Our method generalizes to $(\kappa, \beta)$-Hölder mean rewards $(\mu_t)_t$ satisfying:

$\forall x,x'\in[0,1],\quad |\mu_t(x)-\mu_t(x')| \leq \kappa|x - x'|^\beta.$ In the stationary setting with horizon $\tau$, the minimax regret is $\tau^{\frac{1+\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}}$, achieved by discretizing into $K_\text{opt}(\tau,\kappa,\beta) = \tau^{\frac{1}{1+2\beta}}\kappa^{\frac{2}{1+2\beta}}$ bins (Kleinberg, 2004). This motivates defining significant regret over $[s_1,s_2]$ as:

$\sum_{t=s_1}^{s_2} \delta_t(x) \geq \log(T)(s_2 - s_1)^{\frac{1+\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}}.$ We consider blocks of size $\tau_{l,m+1}-\tau_{l,m}=2^{m(1+2\beta)}/\kappa^2$, yielding $2^m$ bins and expected regret of $2^{m(1+\beta)}$ over this block if the rewards are stable enough. Replays at depth $d$ last $\ell(d) = 2^{d(1+2\beta)}/\kappa^2$ and use $2^d$ bins. The bias for estimating the cumulative reward gap is $4(s_2 - s_1)\kappa/2^{d\beta}$. This motivates the new eviction rule:

$\max_{B'}\sum_{t=s_1}^{s_2} \hat\delta_t(B',B) > c_0\log(T)\sqrt{(s_2-s_1)2^d} + 4\kappa(s_2 - s_1)/2^{d\beta},$ where the $c_0\approx 20$ is exactly the same as in the 1-Lipschitz setting.

Replay at depth $d$ starting at round $s$ is scheduled with probability:

$p_{s,d} = \frac{1}{\kappa} \cdot \frac{2^{d(1+2\beta)/2}}{\sqrt{s - \tau_{l,m}}} \quad (d < m).$ Each block includes $2^{(1+2\beta)(m-d)/2}$ replays at depth $d$, each incurring regret $2^{((1+2\beta)(m-d) + 2d(1+\beta))/2}$. Summing over all dephs $d < m$ gives total replay regret $\mathcal{O}(2^{m(1+\beta)})$, matching the optimal bound per block.

The expected replay interval at depth $d$ is (up to numerical constants that do not depend on $\kappa$ and $\beta$) $2^{(1+2\beta)(m+d)/2}$, while shifts of size $2^{-d\beta}$ become detectable within $2^{m(1+\beta)}$ rounds. Each episode $t_{l+1}-t_l$ has at most $M_l = \log_2((t_{l+1}-t_l)\kappa)/(1+2\beta)$ blocks, and the regret per episode is upper bounded as

$\sum_{m=1}^{M_l} 2^{m(1+\beta)} \leq (t_{l+1}-t_l)^{\frac{1+\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}}.$ Thus, the total dynamic regret of $`MBDE`$ is upper bounded as:

$\mathbb{E}[R_T] \leq \tilde{\mathcal{O}}\left(T^{\frac{1+\beta}{1+2\beta}} \tilde{L}_T^{\frac{\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}} \right).$ $\tilde{\mathcal{O}}(\cdot)$ only hides poly-logarithmic factors and numerical constant that does not depend on $\kappa$ or $\beta$.

With the exact same arguments as in our Lower bound proof (Appendix F), we show that this rate is indeed minimax-optimal with respect to $T, \tilde{L}_T, \kappa$ and $\beta$.

Numerical results (same answer as VifP, kQLa and 9z8n)

We implemented our algorithm and evaluated its performance. Because of the NeurIPS policy, we cannot share code at this stage but will release it upon acceptance.

We benchmark against two baselines: $`BinningUCB (no restart)`$, which uses $K(T)\propto T^{1/3}$ and never resets, and $`BinningUCB (oracle)`$, which knows the true change points $\tau_i$ and resets its estimate at the end phase. At each phase, it uses the optimal per-phase discretization $K_i \propto (\tau_{i+1}-\tau_i)^{1/3}$.

We simulate a $1$-Lipschitz, piecewise-linear reward on $[0,1]$ with a peak shifting from $x=0.3$ to $x=0.7$ every $10^5$ rounds over horizon $T=10^6$, inducing $\tilde{L}_T = 10$ significant shifts. Regret is averaged over $100$ runs (rounded to nearest integer).

Our method adapts to non-stationarity via replays, significantly outperforming $`BUCB (no restart)`$.

Computational complexity (same answer as VifP, kQLa and 9z8n)

Our algorithm is feasible for small-scale problems, as shown in experiments, but we acknowledge that its time and memory complexity limits its scalability. We detail the worst-case computational cost below.

In a block of length $\tau_{l,m+1}-\tau_{l,m}=8^m$, the algorithm maintains $\sum_{d=1}^m 2^d = \mathcal{O}(2^m)$ bins. Estimating bin means costs $\mathcal{O}(2^m)$ per round. Additionally, it performs the statistical test $\textcolor{red}{(\star)}$ over all bin pair of bins $(B_1, B_2)$ at each depth $d$, with $\mathcal{O}(4^d)$ pairs, totaling $\mathcal{O}(4^m)$ across depths. For each pair, it checks all intervals of the form $[s_1, t] \subseteq [\tau_{l,m}, t]$, leading to $\mathcal{O}(8^m)$ possibilities. Therefore, the total per-round worst-case time complexity is $\mathcal{O}(2^m + 4^m \cdot 8^m) = \mathcal{O}(32^m)$, and the per-round worst-case memory complexity is $\mathcal{O}(8^m)$.

Since $m \leq \log(T)$, we conclude that $`MBDE`$ has an overall worst-case time complexity $\mathcal{O}(T^6)$ and memory $\mathcal{O}(T^4)$: both polynomial in $T$. For small $m$ (e.g., $m \leq 5$), runtime is manageable for some problem instances. Designing adaptive, efficient algorithms with optimal regret remains an important open direction, even in $K$-armed settings (Gerogiannis et al., 2024).

We will add a paragraph discussing the computational complexity in the main text.

References

• Kleinberg. "Nearly tight bounds for the continuum-armed bandit problem." NIPS 2004.
• Suk and Kpotufe. "Tracking most significant shifts in nonparametric contextual bandits." Neurips 2023.
• Gerogiannis, Huang and Veeravalli. Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible? AISTATS 2025.

We thank the reviewer for the feedback.

Three-way tradeoff (same answer as scsD)

The three-way tradeoff refers to the balance our algorithm must deal between: (i) exploration, via replays to detect changes; (ii) exploitation, by choosing bins with the highest estimated rewards; and (iii) discretization level, that is, choosing the appropriate discretization depth at each time step. This third dimension arises specifically from our setting of Lipschitz mean reward functions that change over time. We will clarify this in Section 1.1.

Presentation and readability

We thank the reviewer for pointing the flaws in our presentation. We will add figures to enhance comprehension in the supplementary allowed page if our paper is accepted.

Numerical results (same answer as VifP, 9z8n and GmBd)

We implemented our algorithm and evaluated its performance. Because of the NeurIPS policy, we cannot share code at this stage but will release it upon acceptance.

We benchmark against two baselines: $`BinningUCB (no restart)`$, which uses $K(T)\propto T^{1/3}$ and never resets, and $`BinningUCB (oracle)`$, which knows the true change points $\tau_i$ and resets its estimate at the end phase. At each phase, it uses the optimal per-phase discretization $K_i \propto (\tau_{i+1}-\tau_i)^{1/3}$.

We simulate a $1$-Lipschitz, piecewise-linear reward on $[0,1]$ with a peak shifting from $x=0.3$ to $x=0.7$ every $10^5$ rounds over horizon $T=10^6$, inducing $\tilde{L}_T = 10$ significant shifts. Regret is averaged over $100$ runs (rounded to nearest integer).

Our method adapts to non-stationarity via replays, significantly outperforming $`BUCB (no restart)`$.

Computational complexity (same answer as VifP, 9z8n and GmBd)

Our algorithm is feasible for small-scale problems, as shown in experiments, but we acknowledge that its time and memory complexity limits its scalability. We detail the worst-case computational cost below.

In a block of length $\tau_{l,m+1}-\tau_{l,m}=8^m$, the algorithm maintains $\sum_{d=1}^m 2^d = \mathcal{O}(2^m)$ bins. Estimating bin means costs $\mathcal{O}(2^m)$ per round. Additionally, it performs the statistical test $\textcolor{red}{(\star)}$ over all bin pair of bins $(B_1, B_2)$ at each depth $d$, with $\mathcal{O}(4^d)$ pairs, totaling $\mathcal{O}(4^m)$ across depths. For each pair, it checks all intervals of the form $[s_1, t] \subseteq [\tau_{l,m}, t]$, leading to $\mathcal{O}(8^m)$ possibilities. Therefore, the total per-round worst-case time complexity is $\mathcal{O}(2^m + 4^m \cdot 8^m) = \mathcal{O}(32^m)$, and the per-round worst-case memory complexity is $\mathcal{O}(8^m)$.

Since $m \leq \log(T)$, we conclude that $`MBDE`$ has an overall worst-case time complexity $\mathcal{O}(T^6)$ and memory $\mathcal{O}(T^4)$: both polynomial in $T$. For small $m$ (e.g., $m \leq 5$), runtime is manageable for some problem instances. Designing adaptive, efficient algorithms with optimal regret remains an important open direction, even in $K$-armed settings (Gerogiannis et al., 2024).

We will add a paragraph discussing the computational complexity in the main text.

Extension to smooth bandits (same answer as scsD and GmBd)

Our algorithm and analysis can easily be adapted beyond $1$-Lipschitz reward function, and still enjoy minimax optimal rate. For the sake of space, we give a sketch of proof of this generalization (similarly to Appendix G for the multi-dimensional setting).

Our method generalizes to $(\kappa, \beta)$-Hölder mean rewards $(\mu_t)_t$ satisfying:

$\forall x,x'\in[0,1],\quad |\mu_t(x)-\mu_t(x')| \leq \kappa|x - x'|^\beta.$

In the stationary setting with horizon $\tau$, the minimax regret is $\tau^{\frac{1+\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}}$, achieved by discretizing into $K_\text{opt}(\tau,\kappa,\beta) = \tau^{\frac{1}{1+2\beta}}\kappa^{\frac{2}{1+2\beta}}$ bins (Kleinberg, 2004). This motivates defining significant regret over $[s_1,s_2]$ as:

$\sum_{t=s_1}^{s_2} \delta_t(x) \geq \log(T)(s_2 - s_1)^{\frac{1+\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}}.$

We consider blocks of size $\tau_{l,m+1}-\tau_{l,m}=2^{m(1+2\beta)}/\kappa^2$, yielding $2^m$ bins and expected regret of $2^{m(1+\beta)}$ over this block if the rewards are stable enough. Replays at depth $d$ last $\ell(d) = 2^{d(1+2\beta)}/\kappa^2$ and use $2^d$ bins. The bias for estimating the cumulative reward gap is $4(s_2 - s_1)\kappa/2^{d\beta}$. This motivates the new eviction rule:

$\max_{B'}\sum_{t=s_1}^{s_2} \hat\delta_t(B',B) > c_0\log(T)\sqrt{(s_2-s_1)2^d} + 4\kappa(s_2 - s_1)/2^{d\beta},$

where the $c_0\approx 20$ is exactly the same as in the 1-Lipschitz setting.

Replay at depth $d$ starting at round $s$ is scheduled with probability:

$p_{s,d} = \frac{1}{\kappa} \cdot \frac{2^{d(1+2\beta)/2}}{\sqrt{s - \tau_{l,m}}} \quad (d < m).$

Each block includes $2^{(1+2\beta)(m-d)/2}$ replays at depth $d$, each incurring regret $2^{((1+2\beta)(m-d) + 2d(1+\beta))/2}$. Summing over all dephs $d < m$ gives total replay regret $\mathcal{O}(2^{m(1+\beta)})$, matching the optimal bound per block.

The expected replay interval at depth $d$ is (up to numerical constants that do not depend on $\kappa$ and $\beta$) $2^{(1+2\beta)(m+d)/2}$, while shifts of size $2^{-d\beta}$ become detectable within $2^{m(1+\beta)}$ rounds. Each episode $t_{l+1}-t_l$ has at most $M_l = \log_2((t_{l+1}-t_l)\kappa)/(1+2\beta)$ blocks, and the regret per episode is upper bounded as

$\sum_{m=1}^{M_l} 2^{m(1+\beta)} \leq (t_{l+1}-t_l)^{\frac{1+\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}}.$

Thus, the total dynamic regret of $`MBDE`$ is upper bounded as:

$\mathbb{E}[R_T] \leq \tilde{\mathcal{O}}\left(T^{\frac{1+\beta}{1+2\beta}} \tilde{L}_T^{\frac{\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}} \right).$ $\tilde{\mathcal{O}}(\cdot)$ only hides poly-logarithmic factors and numerical constant that does not depend on $\kappa$ or $\beta$.

With the exact same arguments as in our Lower bound proof (Appendix F), we show that this rate is indeed minimax-optimal with respect to $T, \tilde{L}_T, \kappa$ and $\beta$.

Technical novelty (same answer as VifP)

The main challenge in our setting lies in estimating a continuous, non-stationary mean reward function without prior knowledge of the magnitude of distributional shifts—or, equivalently, the discretization level and time scale at which such shifts become detectable. Coarse discretizations are essential to rapidly detect large shifts, while finer discretizations are required to capture smaller yet statistically significant changes. This motivates a multi-scale replay framework in which each scale contributes adaptively based on the magnitude of the underlying shift.

To address this challenge, we propose a hierarchical replay mechanism spanning multiple scales, where each scale corresponds to a different discretization of the action space $[0,1]$. In contrast, prior works that track significant shifts operate in the $K$-armed setting, where the action space remains fixed and finite even when contexts are continuous. Their replay mechanisms and regret analyses therefore rely on a fixed set of arms, without the need to estimate or track reward changes across multiple scales.

Our algorithm must face three fundamental challenges: (i) scheduling (potentially simultaneous) replays at different depths, (ii) leveraging the information collected across different scales, and (iii) tracking the regret contribution from all scales simultaneously. In our regret analysis, each action $x_t \in [0,1]$ belongs to several bins across discretization levels, and we explicitly quantify the regret incurred at each scale. Moreover, to decide which bin to activate at a given depth and time step, we introduce a principled strategy for (a) scheduling replays at specific scales and (b) selecting the appropriate bin at a given active depth through a carefully designed sampling algorithm.

We will incorporate this discussion at the beginning of the proof sketch in Section 5 to clarify the novelty and technical depth of our theoretical contribution.

References

• Kleinberg. "Nearly tight bounds for the continuum-armed bandit problem." NIPS 2004.

We thank the reviewer for the feedback.

Numerical results (same answer as VifP, kQLa and GmBd)

We implemented our algorithm and evaluated its performance. Because of the NeurIPS policy, we cannot share code at this stage but will release it upon acceptance.

We benchmark against two baselines: $`BinningUCB (no restart)`$, which uses $K(T)\propto T^{1/3}$ and never resets, and $`BinningUCB (oracle)`$, which knows the true change points $\tau_i$ and resets its estimate at the end phase. At each phase, it uses the optimal per-phase discretization $K_i \propto (\tau_{i+1}-\tau_i)^{1/3}$.

We simulate a $1$-Lipschitz, piecewise-linear reward on $[0,1]$ with a peak shifting from $x=0.3$ to $x=0.7$ every $10^5$ rounds over horizon $T=10^6$, inducing $\tilde{L}_T = 10$ significant shifts. Regret is averaged over $100$ runs (rounded to nearest integer).

Our method adapts to non-stationarity via replays, significantly outperforming $`BUCB (no restart)`$.

Computational complexity (same answer as VifP, kQLa and GmBd)

Our algorithm is feasible for small-scale problems, as shown in experiments, but we acknowledge that its time and memory complexity limits its scalability. We detail the worst-case computational cost below.

In a block of length $\tau_{l,m+1}-\tau_{l,m}=8^m$, the algorithm maintains $\sum_{d=1}^m 2^d = \mathcal{O}(2^m)$ bins. Estimating bin means costs $\mathcal{O}(2^m)$ per round. Additionally, it performs the statistical test $\textcolor{red}{(\star)}$ over all bin pair of bins $(B_1, B_2)$ at each depth $d$, with $\mathcal{O}(4^d)$ pairs, totaling $\mathcal{O}(4^m)$ across depths. For each pair, it checks all intervals of the form $[s_1, t] \subseteq [\tau_{l,m}, t]$, leading to $\mathcal{O}(8^m)$ possibilities. Therefore, the total per-round worst-case time complexity is $\mathcal{O}(2^m + 4^m \cdot 8^m) = \mathcal{O}(32^m)$, and the per-round worst-case memory complexity is $\mathcal{O}(8^m)$.

Since $m \leq \log(T)$, we conclude that $`MBDE`$ has an overall worst-case time complexity $\mathcal{O}(T^6)$ and memory $\mathcal{O}(T^4)$: both polynomial in $T$. For small $m$ (e.g., $m \leq 5$), runtime is manageable for some problem instances. Designing adaptive, efficient algorithms with optimal regret remains an important open direction, even in $K$-armed settings (Gerogiannis et al., 2024).

We will add a paragraph discussing the computational complexity in the main text.

Differences with Suk and Kim (2025)

Suk and Kim (2025) study the non-stationary version of infinite-armed bandits with reservoir distribution: at each round $t$, the learner selects an action $a_t \in [0,1]$ and observes a noisy reward $Y_t(a_t)$ with mean $\mu_t(a_t)$, where $\mu_t(a_t)$ itself is drawn from a time-varying distribution $\nu_t(a_t)$. Crucially, this reservoir distribution $\nu_t(a_t)$ evolves over time depending on the learner’s past actions. Their primary assumption concerns the proportion of arms with low expected rewards, but they do not impose any smoothness or regularity conditions on the reward function $\mu_t(\cdot)$. In other words, similar actions do not necessarily yield similar expected rewards, so there is no structure to exploit.

This lack of smoothness means that exploration strategies cannot benefit from generalizing across nearby arms, and thus do not employ discretization of the action space. Instead, their algorithms rely on subsampling techniques tailored to handle the complexity of the reservoir distributions. Due to these differences, their setting and methods relate more closely to rotting bandits literature, which deals with non-stationary rewards that evolve over time in ways independent of spatial smoothness.

We will make it clear in our related work subsection.

Notations for actions

While we agree that in $K$-armed contextual bandit settings, it is standard to denote the context by $x$ and the action by $a$, this convention does not necessarily carry over to the Lipschitz bandits literature. In fact, denoting actions by $x$ is common in this litterature, e.g. in Bubeck et al. (2011) and Kleinberg et al. (2019).

Clarifications on the definition of significant shift

• The interval $[s_1, s_2[$ depends on $x$: each arm may incur significant regret over a different interval. A significant shift is said to occur when all arms have experienced such significant regret over their respective intervals.
• This notion of significant regret is indeed derived from previous work by Suk and coauthors: across all settings (including ours), it refers to an interval over which the regret of an arm exceeds the minimax rate for that setting. In our case, this threshold is $\tilde{O}(t^{1/3})$. Consequently, the definition of a significant shift remains consistent across all settings that adopt this significant shift framework.

Concrete benefit of the significant shift metric (same answer as VifP)

Consider a recommendation system with a continuous pool of content (e.g., movies), indexed by $x \in [0,1]$, where nearby values of $x$ correspond to similar content types. Suppose there exists two regions of high and comparable user preference, centered around $x_1 = 0.3$ and $x_2 = 0.7$. Imagine a scenario where preferences near $x_1$ remain stable over time (e.g., a timeless classic), while preferences near $x_2$ undergo very frequent changes (e.g., a trending topic that evolves daily).

In this case, an algorithm that consistently recommends content near $x_1$ would incur little to no regret, even though the underlying reward function changes frequently in other regions. From a global perspective, the number of changes or the total variation in mean reward could be as large as $L_T = V_T= \mathcal{O}(T)$. An algorithm that relies solely on such metrics would unnecessarily restart its estimates too frequently, as it would overestimate the effective difficulty of the problem. This leads to both theoretical suboptimality and practical inefficiency. However, under our framework, such changes do not constitute a significant shift. This example shows a key strength of our metric: it captures only those changes that are statistically consequential to learning, rather than indiscriminately counting all shifts in the environment.

We will include this example at the end of Section 2.2 to further clarify the motivation for our definition.

Notation $f_{t-1, B}$

True, thank you for pointing this!

References

• Bubeck, Munos, Stoltz, and Szepesvári (2011). X-Armed Bandits. JMLR.
• Kleinberg, Slivkins, and Upfal. Bandits and experts in metric spaces (2019). Journal of the ACM.
• Suk and Kim. Tracking most significant shifts in infinite-armed bandits. ICML 2025.

We thank the reviewer for the feedback.

Extension to other Lipschitz constants (same answer as kQLa and GmBd)

Our algorithm and analysis can easily be adapted beyond $1$-Lipschitz reward function, and still enjoy minimax optimal rate. For the sake of space, we give a sketch of proof of this generalization (similarly to Appendix G for the multi-dimensional setting).

Our method generalizes to $(\kappa, \beta)$-Hölder mean rewards $(\mu_t)_t$ satisfying:

$\forall x,x'\in[0,1],\quad |\mu_t(x)-\mu_t(x')| \leq \kappa|x - x'|^\beta.$

In the stationary setting with horizon $\tau$, the minimax regret is $\tau^{\frac{1+\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}}$, achieved by discretizing into $K_\text{opt}(\tau,\kappa,\beta) = \tau^{\frac{1}{1+2\beta}}\kappa^{\frac{2}{1+2\beta}}$ bins (Kleinberg, 2004). This motivates defining significant regret over $[s_1,s_2]$ as:

$\sum_{t=s_1}^{s_2} \delta_t(x) \geq \log(T)(s_2 - s_1)^{\frac{1+\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}}.$

We consider blocks of size $\tau_{l,m+1}-\tau_{l,m}=2^{m(1+2\beta)}/\kappa^2$, yielding $2^m$ bins and expected regret of $2^{m(1+\beta)}$ over this block if the rewards are stable enough. Replays at depth $d$ last $\ell(d) = 2^{d(1+2\beta)}/\kappa^2$ and use $2^d$ bins. The bias for estimating the cumulative reward gap is $4(s_2 - s_1)\kappa/2^{d\beta}$. This motivates the new eviction rule:

$\max_{B'}\sum_{t=s_1}^{s_2} \hat\delta_t(B',B) > c_0\log(T)\sqrt{(s_2-s_1)2^d} + 4\kappa(s_2 - s_1)/2^{d\beta},$

where the $c_0\approx 20$ is exactly the same as in the 1-Lipschitz setting.

Replay at depth $d$ starting at round $s$ is scheduled with probability:

$p_{s,d} = \frac{1}{\kappa} \cdot \frac{2^{d(1+2\beta)/2}}{\sqrt{s - \tau_{l,m}}} \quad (d < m).$

Each block includes $2^{(1+2\beta)(m-d)/2}$ replays at depth $d$, each incurring regret $2^{((1+2\beta)(m-d) + 2d(1+\beta))/2}$. Summing over all dephs $d < m$ gives total replay regret $\mathcal{O}(2^{m(1+\beta)})$, matching the optimal bound per block.

The expected replay interval at depth $d$ is (up to numerical constants that do not depend on $\kappa$ and $\beta$) $2^{(1+2\beta)(m+d)/2}$, while shifts of size $2^{-d\beta}$ become detectable within $2^{m(1+\beta)}$ rounds. Each episode $t_{l+1}-t_l$ has at most $M_l = \log_2((t_{l+1}-t_l)\kappa)/(1+2\beta)$ blocks, and the regret per episode is upper bounded as

$\sum_{m=1}^{M_l} 2^{m(1+\beta)} \leq (t_{l+1}-t_l)^{\frac{1+\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}}.$

Thus, the total dynamic regret of $`MBDE`$ is upper bounded as:

$\mathbb{E}[R_T] \leq \tilde{\mathcal{O}}\left(T^{\frac{1+\beta}{1+2\beta}} \tilde{L}_T^{\frac{\beta}{1+2\beta}} \kappa^{\frac{1}{1+2\beta}} \right).$ $\tilde{\mathcal{O}}(\cdot)$ only hides poly-logarithmic factors and numerical constant that does not depend on $\kappa$ or $\beta$.

With the exact same arguments as in our Lower bound proof (Appendix F), we show that this rate is indeed minimax-optimal with respect to $T, \tilde{L}_T, \kappa$ and $\beta$.

Locally stationary

By locally stationary phases, we mean time intervals for which the reward function does not change. We thank the reviewer for pointing this flaw and we will clarify it in the final version.

Three-way tradeoff (same answer as kQLa)

The three-way tradeoff refers to the balance our algorithm must deal between: (i) exploration, via replays to detect changes; (ii) exploitation, by choosing bins with the highest estimated rewards; and (iii) discretization level, that is, choosing the appropriate discretization depth at each time step. This third dimension arises specifically from our setting of Lipschitz mean reward functions that change over time. We will clarify this in Section 1.1.

Extension to multi-dimension

Yes, we showed how to adapt our algorithm and analysis in $p-$dimensional action space in Appendix G.

References

• Kleinberg. "Nearly tight bounds for the continuum-armed bandit problem." NIPS 2004.

We thank the reviewer for the comment.

Presentation

We appreciate the feedback regarding the presentation and will improve it by including an illustrative figure of the sampling scheme (Algorithm 2) in the main text, using the space provided in the additional page if our paper is accepted.

Concrete benefits of the significant shift metric (same answer as 9z8n)

Consider a recommendation system with a continuous pool of content (e.g., movies), indexed by $x \in [0,1]$, where nearby values of $x$ correspond to similar content types. Suppose there exists two regions of high and comparable user preference, centered around $x_1 = 0.3$ and $x_2 = 0.7$. Imagine a scenario where preferences near $x_1$ remain stable over time (e.g., a timeless classic), while preferences near $x_2$ undergo very frequent changes (e.g., a trending topic that evolves daily).

In this case, an algorithm that consistently recommends content near $x_1$ would incur little to no regret, even though the underlying reward function changes frequently in other regions. From a global perspective, the number of changes or the total variation in mean reward could be as large as $L_T = V_T= \mathcal{O}(T)$. An algorithm that relies solely on such metrics would unnecessarily restart its estimates too frequently, as it would overestimate the effective difficulty of the problem. This leads to both theoretical suboptimality and practical inefficiency. However, under our framework, such changes do not constitute a significant shift. This example shows a key strength of our metric: it captures only those changes that are statistically consequential to learning, rather than indiscriminately counting all shifts in the environment.

We will include this example at the end of Section 2.2 to further clarify the motivation for our definition.

Constant $c_0$

The constant $c_0$ is given in our theoretical analysis (see line 568, in the supplementary material): $c_0 = 3 + 7(e - 1)\sqrt{2} \approx 20.$ This constant is derived from the confidence bounds of Proposition 2, and ensures that the test procedure $\textcolor{red}{(\star)}$ used to trigger bin evictions is theoretically valid. However, this theoretically justified choice leads to conservative behavior in practice: bins are evicted only when the statistical evidence is strong. To balance theory with empirical performance, we use a smaller constant in our numerical experiments (see the numerical results paragraph in this rebuttal, where we specifically choose $c_0 = 1$), which leads to faster elimination and better regret in practice.

Unique challenges in our analysis (same answer as kQLa)

The main challenge in our setting lies in estimating a continuous, non-stationary mean reward function without prior knowledge of the magnitude of distributional shifts—or, equivalently, the discretization level and time scale at which such shifts become detectable. Coarse discretizations are essential to rapidly detect large shifts, while finer discretizations are required to capture smaller yet statistically significant changes. This motivates a multi-scale replay framework in which each scale contributes adaptively based on the magnitude of the underlying shift.

To address this challenge, we propose a hierarchical replay mechanism spanning multiple scales, where each scale corresponds to a different discretization of the action space $[0,1]$. In contrast, prior works that track significant shifts operate in the $K$-armed setting, where the action space remains fixed and finite even when contexts are continuous. Their replay mechanisms and regret analyses therefore rely on a fixed set of arms, without the need to estimate or track reward changes across multiple scales.

Our algorithm must face three fundamental challenges: (i) scheduling (potentially simultaneous) replays at different depths, (ii) leveraging the information collected across different scales, and (iii) tracking the regret contribution from all scales simultaneously. In our regret analysis, each action $x_t \in [0,1]$ belongs to several bins across discretization levels, and we explicitly quantify the regret incurred at each scale. Moreover, to decide which bin to activate at a given depth and time step, we introduce a principled strategy for (a) scheduling replays at specific scales and (b) selecting the appropriate bin at a given active depth through a carefully designed sampling algorithm.

We will incorporate this discussion at the beginning of the proof sketch in Section 5 to clarify the novelty and technical depth of our theoretical contribution.

Numerical results (same answer as kQLa, 9z8n and GmBd)

We implemented our algorithm and evaluated its performance. Because of the NeurIPS policy, we cannot share code at this stage but will release it upon acceptance.

We benchmark against two baselines: $`BinningUCB (no restart)`$, which uses $K(T)\propto T^{1/3}$ and never resets, and $`BinningUCB (oracle)`$, which knows the true change points $\tau_i$ and resets its estimate at the end phase. At each phase, it uses the optimal per-phase discretization $K_i \propto (\tau_{i+1}-\tau_i)^{1/3}$.

We simulate a $1$-Lipschitz, piecewise-linear reward on $[0,1]$ with a peak shifting from $x=0.3$ to $x=0.7$ every $10^5$ rounds over horizon $T=10^6$, inducing $\tilde{L}_T = 10$ significant shifts. Regret is averaged over $100$ runs (rounded to nearest integer).

Our method adapts to non-stationarity via replays, significantly outperforming $`BUCB (no restart)`$.

Computational complexity (same answer as kQLa, 9z8n and GmBd)

Our algorithm is feasible for small-scale problems, as shown in experiments, but we acknowledge that its time and memory complexity limits its scalability. We detail the worst-case computational cost below.

In a block of length $\tau_{l,m+1}-\tau_{l,m}=8^m$, the algorithm maintains $\sum_{d=1}^m 2^d = \mathcal{O}(2^m)$ bins. Estimating bin means costs $\mathcal{O}(2^m)$ per round. Additionally, it performs the statistical test $\textcolor{red}{(\star)}$ over all bin pair of bins $(B_1, B_2)$ at each depth $d$, with $\mathcal{O}(4^d)$ pairs, totaling $\mathcal{O}(4^m)$ across depths. For each pair, it checks all intervals of the form $[s_1, t] \subseteq [\tau_{l,m}, t]$, leading to $\mathcal{O}(8^m)$ possibilities. Therefore, the total per-round worst-case time complexity is $\mathcal{O}(2^m + 4^m \cdot 8^m) = \mathcal{O}(32^m)$, and the per-round worst-case memory complexity is $\mathcal{O}(8^m)$.

Since $m \leq \log(T)$, we conclude that $`MBDE`$ has an overall worst-case time complexity $\mathcal{O}(T^6)$ and memory $\mathcal{O}(T^4)$: both polynomial in $T$. For small $m$ (e.g., $m \leq 5$), runtime is manageable for some problem instances. Designing adaptive, efficient algorithms with optimal regret remains an important open direction, even in $K$-armed settings (Gerogiannis et al., 2024).

We will add a paragraph discussing the computational complexity in the main text.

References

• Wei and Luo. "Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach." COLT 2021.
• Suk and Kpotufe. "Tracking most significant shifts in nonparametric contextual bandits." Neurips 2023.
• Gerogiannis, Huang and Veeravalli. Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible? AISTATS 2025.