acceptodds
Under review as a conference paper at ICLR 2027

Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

Abstract

We study nonstationary generalized linear bandits (GLBs), where the expected reward is modeled through a nonlinear link function with an unknown *time-varying* parameter. This framework encompasses a broad class of reward models, including linear, Bernoulli, and binomial rewards. Existing approaches are predominantly based on maximum-likelihood estimation (MLE), using sliding-window, restart, or discounting mechanisms to handle nonstationarity. Although these methods achieve statistically efficient regret guarantees, they generally require revisiting past observations at every round, which leads to computation and memory costs that grow with time; moreover, several of them rely on a non-convex projection step. In this paper, we propose **DOMD-GLB**, a new algorithm for nonstationary GLBs that utilizes *discounted online mirror descent (DOMD)* for parameter estimation, thereby incurring only computation and memory costs per round. We prove dynamic regret bounds of order in drifting environments and in piecewise-stationary environments, where denotes the feature dimension, the time horizon, the path length, the number of change points, and a curvature parameter associated with the link function, while substantially improving computational efficiency over prior work. To the best of our knowledge, this is the first algorithm for nonstationary GLBs with per-round computation and memory costs independent of time.

Primary area:
learning theory
Keywords:
Bandit, Generalized Linear Bandits, Nonstationary Bandit, Online Mirror Descent

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_dw3COpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies a nonstationary linear bandit problem where the rewards follow a generalized linear model, depending on the inner product of an unknown parameter θ with the action. Prior work has addressed this problem with MLE-based methods. Instead, the authors propose a more efficient algorithm based on mirror descent, which has previously been used for generalized linear bandits, but only in the stationary case. The algorithm has a per-round computational cost which is totally independent of the time t, and it achieves the best known rates in some cases. The paper is supported mainly by theory, along with some numerical experiments.

Critical strengths
  1. The exposition is very clear. The paper explains the problem setting, the body of related work, and how the present paper relates to, combines, and improves upon it. In particular, the story of the recent developments on which this paper builds is very nice, and it gives a real sense of what is known in this space. The method is also explained well, including the role of each variable throughout, for example the recurring discussion of A versus H. This matters because it makes the contribution easy to situate and assess, even for a reader who is not an expert in this specific area.

  2. The algorithm is computationally efficient, with a per-round cost independent of t, and it matches the best known rates in some cases. The empirical results are also quite nice.

Critical weaknesses

I did not find critical weaknesses. My main question is about the size of the gain relative to existing methods such as MASTER, which I describe below.

Questions for authors

Clarifications:

  1. In Section 3.1, I am not sure tau was defined. I assume it is a known parameter?

  2. In the discussion after Theorem 2, I have some questions about the comparison with the MASTER algorithm of Wei & Luo, and whether the proposed algorithm is really better. What type of algorithm is MASTER? The computational difference is only log(t) versus constant, which is not that large. Can you expand upon what makes time varying action sets an important difference? What changes in the algorithm or analysis? Later, in the experiments, I see that MASTER performs badly so I guess this is an important distinction.

  3. In the discussion after Theorem 3, the note about the 1/c_μ factor: Do the authors think this is a problem with the algorithm or with the analysis? The empirical observation that the present method out-performs SCB-PW-WeightUCB is interesting.

Suggestions:

  1. The proof sketch is appreciated, but it is still dense at times. For example, how should I think about the mix loss at a higher level, beyond its precise mathematical definition? In step 3 of the proof of Theorem 1, by the end it seems that the supermartingale argument is broken by nonstationarity, but that discounting provides a different argument for concentration. This higher-level message (on the importance of discounting) might be nice to highlight or to bring to the front of the sketch.

  2. I appreciate the comparisons with the most recent mirror descent work by Zhang, but at times these edge on being too much for a reader who has not read that paper. It would help to make these comparisons more self-contained, or to keep only the ones which are needed to understand the present contribution.

6 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/5]

We thank the reviewer for the thoughtful questions and helpful suggestions. We also appreciate the overall positive initial evaluation. We address each point below.


Is τ\tau a known parameter?

Yes, τ\tau is a fixed, known dispersion parameter of the reward distribution, and g(τ)>0g(\tau)>0 is the corresponding dispersion term. We will define τ\tau explicitly in Section 3.1.


Clarification of MASTER

1. What type of algorithm is MASTER?

MASTER is an adaptive restart meta-algorithm that wraps a base learner, such as GLM-UCB, and decides when to restart learning. It schedules several copies of the base learner over different time scales, such as 1,2,4,8,…1,2,4,8,\ldots rounds. Shorter copies help detect recent changes, while longer copies learn from a longer history. MASTER compares predictions and observed rewards across these intervals and restarts when the discrepancy is too large to be explained by statistical uncertainty under a stable environment. This allows adaptation without knowing the nonstationarity budget.

Maintaining these different time scales requires storing up to O(log⁡t)O(\log t) base-learner instances. Although only one instance acts and updates in each round, the paused instances must preserve their states so that they can resume later. This explains the logarithmic overhead, but the total computation and memory costs also include those of the base learners. For example, a GLM-UCB instance holding tt observations requires O(td)O(td) memory to store the data. Computing its MLE using a standard dense Newton method costs O(td2+d3)O(td^2+d^3) per optimization iteration and requires additional O(d2)O(d^2) memory for the Hessian. The nonconvex projection introduces a further computational cost. In contrast, our DOMD-GLB maintains a single estimator and requires only O(d3)O(d^3) computation and O(d2)O(d^2) memory per round for estimation, both independent of tt.

2. What specifically breaks in the existing analysis when action sets vary over time?

According to MASTER’s fixed-action GLB analysis, sufficiently small parameter variation prevents unnecessary restarts with high probability. The key is that, with a fixed action set, a stable parameter implies a stable optimal reward level. MASTER can therefore compare reward levels across time to detect changes. When action sets vary, however, better available actions can produce higher rewards even when the parameter remains unchanged. The comparison used to rule out unnecessary restarts then loses its justification.

a) Why does the fixed action set matter?

Let vs⋆:=max⁡x∈Xμ(x⊤θs⋆)v_s^\star:=\max_{x\in\mathcal X}\mu(x^\top\theta_s^\star) denote the best achievable mean reward at round ss. Because both rounds have the same feasible actions, the Lipschitz property of μ\mu and ∣x∣2≤1\\|x\\|_2\le1 imply

∣vs+1⋆−vs⋆∣≤max⁡x∈X∣μ(x⊤θs+1⋆)−μ(x⊤θs⋆)∣≤kμ∣θs+1⋆−θs⋆∣2.|v_{s+1}^\star-v_s^\star|\le\max_{x\in\mathcal X}|\mu(x^\top\theta_{s+1}^\star)-\mu(x^\top\theta_s^\star)|\le k_\mu\\|\theta_{s+1}^\star-\theta_s^\star\\|_2.

Thus, any change in the optimal reward must come from a change in the parameter. For a block B=[b,t]B=[b,t], let PB:=∑s=bt−1∣θs+1⋆−θs⋆∣2P_B:=\sum_{s=b}^{t-1}\\|\theta_{s+1}^\star-\theta_s^\star\\|_2. The preceding inequality gives

max⁡s∈Bvs⋆−min⁡s∈Bvs⋆≤kμPB.\max_{s\in B}v_s^\star-\min_{s\in B}v_s^\star\le k_\mu P_B.

In particular, for any subinterval I⊆BI\subseteq B,

1∣I∣∑s∈Ivs⋆−min⁡u∈Bvu⋆≤kμPB.\frac{1}{|I|}\sum_{s\in I}v_s^\star-\min_{u\in B}v_u^\star\le k_\mu P_B.

This means that a recent interval cannot offer substantially higher optimal rewards than an earlier part of the block unless the parameter has changed substantially.

b) Where does MASTER use this comparison?

MASTER maintains Ut:=min⁡s∈Bg~sU_t:=\min_{s\in B}\widetilde g_s, where g~s\widetilde g_s is the optimistic value reported by the active learner. Thus, UtU_t is the smallest optimistic reward estimate recorded in the current block.

At the end of a scheduled interval II, Test 1 compares its average observed reward, rˉI:=∣I∣−1∑s∈Irs\bar r_I:=|I|^{-1}\sum_{s\in I}r_s, with this historical estimate. It triggers a restart if

rˉI≥Ut+9ρ^(∣I∣),\bar r_I\ge U_t+9\widehat\rho(|I|),

where ρ^(∣I∣)\widehat\rho(|I|) is a statistical tolerance. Intuitively, the test asks: “Are recent rewards substantially higher than an earlier optimistic estimate suggested was possible?”

To justify this test, Lemma 23 of Wei and Luo (2021) uses the following inequalities on its high-probability event:

Ut≥min⁡s∈Bvs⋆−ΔB≥1∣I∣∑s∈Ivs⋆−3ΔB,U_t\ge\min_{s\in B}v_s^\star-\Delta_B\ge\frac{1}{|I|}\sum_{s\in I}v_s^\star-3\Delta_B,

where ΔB\Delta_B is their variation measure, proportional to PBP_B in the fixed-action GLB instantiation. The second inequality is the critical comparison: it ensures that an earlier, lower reward level remains a useful reference for the recent interval. Together with reward concentration, this prevents Test 1 from triggering when parameter variation is sufficiently small.

AuthorsOpenReview ↗

Official Comment by Authors [2/5]

c) Why does that inequality fail when the action set changes?

Consider a situation where better actions become available while the reward parameter remains unchanged. MASTER’s detection test may interpret the resulting increase in rewards as a signal of parameter change, even though only the available choices have changed. The following example illustrates why its existing analysis cannot rule out such unnecessary restarts using parameter variation alone.

Consider a one-dimensional logistic bandit with μ(z)=σ(z):=(1+e−z)−1\mu(z)=\sigma(z):=(1+e^{-z})^{-1} and a constant parameter θs⋆=1\theta_s^\star=1. Suppose the available actions are {−1,0}\{-1,0\} in the first phase and {0,1}\{0,1\} in the second phase.

In the first phase, the best available action is x=0x=0, giving an optimal mean reward of 1/21/2. In the second phase, the newly available action x=1x=1 increases the optimal mean reward to σ(1)≈0.731\sigma(1)\approx0.731. Each action’s mean reward remains unchanged; the increase comes entirely from the availability of a better action.

Let BB contain both phases and let II lie entirely in the second phase. Then

PB=0,min⁡s∈Bvs⋆=12,1∣I∣∑s∈Ivs⋆=σ(1)>12.P_B=0,\qquad \min_{s\in B}v_s^\star=\frac12,\qquad \frac{1}{|I|}\sum_{s\in I}v_s^\star=\sigma(1)>\frac12.

If we attempted to extend the analysis while keeping ΔB\Delta_B proportional to parameter variation alone, we would have ΔB=0\Delta_B=0. The critical inequality in part (b) would then require 12≥σ(1),\frac12\ge\sigma(1), which is false. Thus, a constant parameter no longer ensures that recent optimal rewards remain close to the historical minimum, and parameter variation alone cannot justify the comparison used in the existing proof. Without this comparison, the proof can no longer rule out unnecessary restarts when action sets change.


Is the additional cμc_\mu dependence an algorithmic or analytical limitation?

We believe that the additional cμc_\mu dependence in the leading term is due to looseness in our current analysis. With a slight refinement of the analysis, the leading regret term in the piecewise-stationary setting improves from O~(cμ−1/3d2/3ΓT1/3T2/3)\widetilde O(c_\mu^{-1/3}d^{2/3}\Gamma_T^{1/3}T^{2/3}) to O~(d2/3ΓT1/3T2/3)\widetilde O(d^{2/3}\Gamma_T^{1/3}T^{2/3}). The refinement uses the same DOMD update and action-selection rule. The improvement comes from preserving local curvature in the regret analysis instead of replacing it by the global lower bound cμc_\mu too early. The remaining cμc_\mu dependence appears in terms of lower order in TT when the other parameters are fixed, so the resulting guarantee is not entirely independent of cμc_\mu.

We explain the main idea and proof outline below. We work on the high-probability confidence event of Theorem 1 and consider γ∈[1/2,1)\gamma\in[1/2,1). Throughout, O~\widetilde O suppresses logarithmic factors, and we omit coefficients depending on SS, RR, kμk_\mu, and g(τ)g(\tau) to highlight the dependence on dd, TT, ΓT\Gamma_T, and cμc_\mu.

1. Where the current analysis loses precision. The quantity ∣xt∣Ht−1\\|x_t\\|_{H_t^{-1}} measures the uncertainty in the selected action’s direction: a larger value means that the discounted information matrix HtH_t provides less information in that direction. We use βT+1(δ)\beta_{T+1}(\delta) as a common upper bound on the confidence radii.

Away from change points, our current proof bounds the instantaneous regret by 2kμβT+1(δ)∣xt∣Ht−12k_\mu\beta_{T+1}(\delta)\\|x_t\\|_{H_t^{-1}}, together with a small contribution from observations collected before the latest change. Here, kμk_\mu is a uniform upper bound on the slope of the reward function. To sum these uncertainty terms, the proof then replaces the local curvature contributions by the uniform lower bound cμc_\mu, obtaining

∑t=1T∣xt∣Ht−12=O~(dcμ(1+T(1−γ))).\sum_{t=1}^T \\|x_t\\|_{H_t^{-1}}^2 = \widetilde O(\frac{d}{c_\mu}(1+T(1-\gamma))).

Thus, the current analysis uses a global upper bound on the slope to control the reward difference and a global lower bound to control information accumulation. This loses the connection between these two quantities and introduces the additional curvature dependence.

2. Preserve the connection between reward sensitivity and information. The local curvature μ′(xt⊤θt+1)\mu'(x_t^\top\theta_{t+1}) is precisely the quantity incorporated into the matrix update:

Ht+1=γHt+(1−γ)λI+μ′(xt⊤θt+1)g(τ)xtxt⊤.H_{t+1} = \gamma H_t+(1-\gamma)\lambda I+\frac{\mu'(x_t^\top\theta_{t+1})}{g(\tau)}x_tx_t^\top.

The key is to express the regret using this same local curvature, instead of immediately replacing the relevant slope by kμk_\mu.

To see how, let Δt=(xt⋆−xt)⊤θt⋆\Delta_t=(x_t^\star-x_t)^\top\theta_t^\star be the gap between the optimal and selected actions before applying the link function. The action-selection rule and confidence bound give

Δt≤2βT+1(δ)∥xt∥Ht−1+2ιVtλ,\Delta_t\le 2\beta_{T+1}(\delta)\|x_t\|_{H_t^{-1}}+\frac{2\iota V_t}{\sqrt{\lambda}},

where the term involving VtV_t accounts for the remaining influence of past parameter changes.

AuthorsOpenReview ↗

Official Comment by Authors [3/5]

A Taylor expansion bounds the instantaneous regret as follows:

instantaneous regret at round t≤μ′(xt⊤θt⋆)Δt+Rkμ2Δt2.\text{instantaneous regret at round }t \le \mu'(x_t^\top\theta_t^\star)\Delta_t+\frac{Rk_\mu}{2}\Delta_t^2.

Here, we use the manuscript’s self-concordance property ∣μ′′∣≤Rμ′≤Rkμ|\mu''|\le R\mu'\le Rk_\mu.

We next connect the slope at the true parameter, μ′(xt⊤θt⋆)\mu'(x_t^\top\theta_t^\star), to the curvature accumulated by the algorithm, μ′(xt⊤θt+1)\mu'(x_t^\top\theta_{t+1}). Since ∣μ′′∣≤Rkμ|\mu''|\le Rk_\mu, the mean value theorem bounds the absolute difference between these slopes by Rkμ∣xt⊤(θt⋆−θt+1)∣Rk_\mu|x_t^\top(\theta_t^\star-\theta_{t+1})|. Thus, it suffices to control the error in the linear predictor associated with the updated estimate θt+1\theta_{t+1}.

On rounds where θt+1⋆=θt⋆\theta_{t+1}^\star=\theta_t^\star, this error is controlled by the confidence bound at t+1t+1. Moreover, Ht+1⪰γHtH_{t+1}\succeq\gamma H_t implies ∣xt∣Ht+1−1≤γ−1/2∣xt∣Ht−1\\|x_t\\|_{H_{t+1}^{-1}}\le\gamma^{-1/2}\\|x_t\\|_{H_t^{-1}}. Combining these observations gives

μ′(xt⊤θt⋆)≤μ′(xt⊤θt+1)+RkμβT+1(δ)γ∣xt∣Ht−1+RkμιVt+1λ.\mu'(x_t^\top\theta_t^\star) \le \mu'(x_t^\top\theta_{t+1})+\frac{Rk_\mu\beta_{T+1}(\delta)}{\sqrt{\gamma}}\\|x_t\\|_{H_t^{-1}}+\frac{Rk_\mu\iota V_{t+1}}{\sqrt{\lambda}}.

The last term again reflects past parameter changes. We refer to contributions involving VtV_t or Vt+1V_{t+1} as drift-tail terms; Lemma D.2 controls their sum on rounds sufficiently far from a change point.

We now substitute this slope bound into the Taylor expansion and apply the bound on Δt\Delta_t. To control the quadratic term, we also use Δt≤2S\Delta_t\le 2S, which gives

Δt2≤4βT+12(δ)∣xt∣Ht−12+8SιVtλ.\Delta_t^2\le 4\beta_{T+1}^2(\delta)\\|x_t\\|_{H_t^{-1}}^2+\frac{8S\iota V_t}{\sqrt{\lambda}}.

Together with ∣xt∣Ht−1≤1/λ\\|x_t\\|_{H_t^{-1}}\le 1/\sqrt{\lambda}, these inequalities yield

instantaneous regret at round t≤2βT+1(δ)μ′(xt⊤θt+1)∣xt∣Ht−1+2Rkμ(1+γ−1/2)βT+12(δ)∣xt∣Ht−12+drift-tail terms.\text{instantaneous regret at round }t \le 2\beta_{T+1}(\delta)\mu'(x_t^\top\theta_{t+1})\\|x_t\\|_{H_t^{-1}}+2Rk_\mu(1+\gamma^{-1/2})\beta_{T+1}^2(\delta)\\|x_t\\|_{H_t^{-1}}^2+\text{drift-tail terms}.

The first term captures the main statistical uncertainty using the same local curvature that enters the matrix update. The second accounts for the slope-comparison error and the Taylor remainder.

3. Sum the main term without using the global lower bound on curvature. Because the matrix update accumulates μ′(xt⊤θt+1)xtxt⊤/g(τ)\mu'(x_t^\top\theta_{t+1})x_tx_t^\top/g(\tau), the discounted elliptical-potential argument directly controls the curvature-weighted uncertainty:

∑t=1Tμ′(xt⊤θt+1)∣xt∣Ht−12=O~(d(1+T(1−γ))).\sum_{t=1}^T \mu'(x_t^\top\theta_{t+1})\\|x_t\\|_{H_t^{-1}}^2 = \widetilde O(d(1+T(1-\gamma))).

This bound has no inverse dependence on cμc_\mu. Since μ′(xt⊤θt+1)≤kμ\mu'(x_t^\top\theta_{t+1})\le k_\mu, Cauchy–Schwarz gives

βT+1(δ)∑t=1Tμ′(xt⊤θt+1)∣xt∣Ht−1≤βT+1(δ)kμT∑t=1Tμ′(xt⊤θt+1)∣xt∣Ht−12=O~(dT+dT1−γ).\beta_{T+1}(\delta)\sum_{t=1}^T \mu'(x_t^\top\theta_{t+1})\\|x_t\\|_{H_t^{-1}} \le \beta_{T+1}(\delta)\sqrt{k_\mu T\sum_{t=1}^T \mu'(x_t^\top\theta_{t+1})\\|x_t\\|_{H_t^{-1}}^2} = \widetilde O(d\sqrt T+dT\sqrt{1-\gamma}).

Here, we use βT+1(δ)=O~(d)\beta_{T+1}(\delta)=\widetilde O(\sqrt d) under the parameter choices in the manuscript, with the other problem parameters suppressed as described above. This is the step that removes the global curvature dependence from the main statistical term.

The quadratic remainder still requires the unweighted uncertainty bound, giving

βT+12(δ)∑t=1T∣xt∣Ht−12=O~(d2cμ(1+T(1−γ))).\beta_{T+1}^2(\delta)\sum_{t=1}^T\\|x_t\\|_{H_t^{-1}}^2 = \widetilde O(\frac{d^2}{c_\mu}(1+T(1-\gamma))).

Since these statistical terms are nonnegative, their sums over all rounds also bound their contributions over the subset of rounds considered in Step 2.

4. Handle changes and combine the bounds. Piecewise stationarity allows us to set aside a short period after each change point. After DD rounds without a change, the contribution of earlier segments is suppressed by a factor of order γD/2\gamma^{D/2}. Choosing D=O~(1/(1−γ))D=\widetilde O(1/(1-\gamma)), with a sufficiently large logarithmic factor, makes the total drift-tail contribution at most O(ΓT)O(\Gamma_T) by Lemma D.2.

We also set aside the at most ΓT\Gamma_T rounds immediately preceding a change, so that the comparison using the confidence bound at t+1t+1 is valid. Thus, at most ΓT(D+1)\Gamma_T(D+1) rounds are excluded around change points. Since each round incurs regret at most RR, their total contribution is O~(ΓT/(1−γ))\widetilde O(\Gamma_T/(1-\gamma)). The first and last rounds can be treated separately at an additional cost of at most 2R2R, which is absorbed into the bound below.

Adding the main statistical term, the quadratic remainder, and the contributions associated with change points gives

Reg⁡T=O~(dT+dT1−γ+d2cμ(1+T(1−γ))+ΓT1−γ).\operatorname{Reg}_T = \widetilde O(d\sqrt T+dT\sqrt{1-\gamma}+\frac{d^2}{c_\mu}(1+T(1-\gamma))+\frac{\Gamma_T}{1-\gamma}). In the intermediate regime where 1−γ≍(ΓT/(dT))2/31-\gamma\asymp(\Gamma_T/(dT))^{2/3} is admissible, this becomes

Reg⁡T=O~(dT+d2/3ΓT1/3T2/3+d2cμ+d4/3ΓT2/3T1/3cμ).\operatorname{Reg}_T = \widetilde O(d\sqrt T+d^{2/3}\Gamma_T^{1/3}T^{2/3}+\frac{d^2}{c_\mu}+\frac{d^{4/3}\Gamma_T^{2/3}T^{1/3}}{c_\mu}). The T2/3T^{2/3} term therefore has no cμc_\mu dependence. The remaining dependence appears in terms of lower order in TT when the other parameters are fixed; these terms can still matter when cμc_\mu is small.

Reviewer_nfucOpenReview ↗
Rating
3
Confidence
4(+1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes DOMD-GLB, a discounted online mirror descent algorithm for nonstationary generalized linear bandits with time-varying action sets. It aims to avoid the growing computational and memory costs of existing methods that repeatedly estimate MLE using past observations. DOMD-GLB maintains a parameter estimate and a discounted curvature matrix through one-pass updates. The authors develop a discounted mix-loss confidence analysis that explicitly accounts for parameter drift and derive dynamic regret guarantees for both drifting and piecewise-stationary environments, with per-round estimation costs independent of time.

DOMD-GLB is then evaluated on synthetic logistic-bandit problems with gradual parameter drift and a single abrupt change, comparing cumulative dynamic regret and computation time against several existing methods. In the low-dimensional settings, DOMD-GLB achieves lower regret than the reported baselines while maintaining approximately constant per-round runtime.

Critical strengths
  1. Computationally efficient one-pass estimation: DOMD-GLB replaces repeated weighted MLE with recursive updates that require only O(d3)O(d^3) computation and O(d2)O(d^2) memory per round, independent of the time horizon. This addresses a clear computational limitation of existing MLE-based approaches while retaining competitive dynamic regret guarantees in nonstationary environments.

  2. A unified analysis of different nonstationary environments: The paper develops a discounted confidence analysis that explicitly accounts for parameter drift, adapting the mirror-descent geometry and mix-loss concentration arguments to the nonstationary setting. It further provides dynamic regret bounds for both continuously drifting and piecewise-stationary environments within the same algorithmic framework.

Critical weaknesses
  1. DOMD-GLB extends the stationary one-pass GLB-OMD method of Zhang et al. [1] through exponential discounting, a natural way to handle nonstationarity. In piecewise-stationary environments, periodically restarting the existing estimator appears capable of a comparable regret order with similarly time-independent estimation costs. The paper does not sufficiently distinguish the benefits of discounted OMD from this simpler alternative, particularly in terms of what is gained in continuously drifting environments.

  2. The experiments are restricted to synthetic logistic bandits with d=5d=5, using one smooth drift pattern and one abrupt parameter change. Although the reported regret and runtime results are favorable, these settings provide limited evidence about performance in higher dimensions, other reward models, or more complex nonstationary environments. The absence of a restarted one-pass OMD baseline also makes it difficult to isolate the benefits of discounting. Even for a theory-oriented paper, the experimental evidence is narrow relative to the scope of the proposed method.

[1] Zhang et al. (2025). Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update. NeurIPS 2025.

Questions for authors
  1. What does exponential discounting achieve beyond periodically restarting the existing one-pass GLB-OMD algorithm [1]? In the piecewise-stationary setting, a restarted version appears capable of a comparable regret order while retaining time-independent per-round estimation costs. Does DOMD-GLB offer a more substantial advantage for continuously drifting parameters?

  2. All experiments use synthetic logistic bandits with d=5d=5, despite computational efficiency being a central motivation. Does the favorable regret–runtime tradeoff persist as the dimension increases, given the O(d3)O(d^3) per-round estimation cost? Even a focused scaling comparison would make the practical advantage more convincing.

  3. Some theoretical and experimental descriptions appear inconsistent. Section 3.1 allows general dispersion g(τ)g(\tau), but Proposition 1 seems to omit its effect in the self-concordance bound. Does Theorem 1 remain valid as stated? Also, the discussion of SCB-PW-WeightUCB cites Equation (17) of [2], whereas its piecewise-stationary selection rule appears in Equation (51). Which rule was implemented? I do encourage the authors to check the consistency of notation, cross-references and claims throughout the paper.

[1] Zhang et al. (2025). Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update. NeurIPS 2025.

[2] Wang et al. (2023). Revisiting Weighted Strategy for Non-Stationary Parametric Bandits. AISTATS 2023.

5 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/4]

We sincerely thank the reviewer for carefully reading our paper and providing insightful feedback. Your comments have helped us strengthen the paper considerably. We also appreciate the overall positive initial evaluation. Below, we address the reviewer’s concerns.


Comparison with a simple baseline: Restart + GLB-OMD

Although Restart + GLB-OMD has not been formally proposed in prior work, we agree that it is a natural baseline and worth comparing with our method both theoretically and empirically

1. Theoretical comparison with Restart + GLB-OMD.

In piecewise-stationary environments, as the reviewer pointed out, we also believe that periodic restarting can yield a comparable dynamic regret guarantee. We can divide the horizon into blocks of length HH and restart GLB-OMD at the beginning of each block. The stationary analysis applies to blocks containing no parameter change. Since at most ΓT\Gamma_T blocks contain changes and each incurs at most O(H)O(H) regret under bounded rewards, these blocks contribute at most O(ΓTH)O(\Gamma_T H) regret in total. Writing rstat(H)r_{\mathrm{stat}}(H) for the stationary GLB-OMD regret bound over HH rounds, this gives RTrestart≤⌈T/H⌉rstat(H)+O(ΓTH)R_T^{\mathrm{restart}}\le \lceil T/H\rceil r_{\mathrm{stat}}(H)+O(\Gamma_T H), with logarithmic adjustments for the confidence levels across blocks. Choosing an appropriate HH thus provides a natural route to a dynamic regret guarantee while preserving time-independent per-round estimation costs.

However, in gradually drifting environments, the extension is not direct. We believe that the stationary confidence analysis needs to account for the resulting estimation bias. For a restart block beginning at round bb, the stationary GLB-OMD analysis establishes a confidence bound of the form ∣θ^t−θ⋆∣Ht≤βt,b\\|\hat{\theta}_t-\theta^\star\\|_{H_t} \leq\beta_{t,b}, where HtH_t is the curvature matrix accumulated within the block and βt,b\beta_{t,b} is the corresponding statistical radius. Under drift, however, the target is the current parameter θt⋆\theta_t^\star, whereas earlier observations were generated under potentially different parameters θs⋆\theta_s^\star.

To see where the additional error enters, the deterministic OMD argument, with suitable algorithmic parameters, gives ∣θ^t−θt⋆∣Ht2≤4λS2+2η∑s=bt−1[ℓs(θt⋆)−ℓs(θ^s+1)]−23∑s=bt−1∣θ^s+1−θ^s∣Hs2.\\|\hat{\theta}_t-\theta_t^\star\\|_{H_t}^2\leq 4\lambda S^2+2\eta\sum_{s=b}^{t-1}[\ell_s(\theta_t^\star)-\ell_s(\hat{\theta}_{s+1})]-\frac{2}{3}\sum_{s=b}^{t-1}\\|\hat{\theta}_{s+1}-\hat{\theta}_s\\|_{H_s}^2.

This follows by applying the comparator inequality underlying the stationary analysis of Zhang et al. [1] to θt⋆\theta_t^\star. Following their analysis, define the mix-loss as ms:=−log⁡Eθ∼Πs[exp⁡(−ℓs(θ))]m_s:=-\log\mathbb{E}_{\theta\sim\Pi_s}[\exp(-\ell_s(\theta))], where Πs=N(θ^s,αHs−1)\Pi_s=\mathcal{N}(\hat{\theta}_s,\alpha H_s^{-1}) and α=3η/2\alpha=3\eta/2. Each loss difference then decomposes as ℓs(θt⋆)−ℓs(θ^s+1)=[ℓs(θs⋆)−ms]+[ms−ℓs(θ^s+1)]+[ℓs(θt⋆)−ℓs(θs⋆)].\ell_s(\theta_t^\star)-\ell_s(\hat{\theta}_{s+1})=[\ell_s(\theta_s^\star)-m_s]+[m_s-\ell_s(\hat{\theta}_{s+1})]+[\ell_s(\theta_t^\star)-\ell_s(\theta_s^\star)].

The second term [ms−ℓs(θ^s+1)][m_s-\ell_s(\hat{\theta}_{s+1})] can be controlled directly using Lemma 6 of Zhang et al. [1], whose movement term cancels the negative movement term in the OMD inequality after summation. The first and third terms require nonstationary concentration and loss-drift control, respectively, corresponding to our Lemma B.2 (Fixed-time discounted mix-loss concentration) and Lemma B.4 (Drift-loss bound). After resetting and reindexing each block, these terms appear amenable to the undiscounted (γ=1\gamma=1) versions of our arguments. As in our Theorem 1, the resulting confidence bound would include an additional term accounting for the cumulative parameter variation (e.g., Vt\mathcal{V}_t) within the current restart block.

This suggests that our analysis could also provide a foundation for establishing guarantees for Restart + GLB-OMD under gradual drift. We view this potential applicability beyond discounting as a strength of our framework and an interesting extension that could further strengthen the theoretical contribution of our paper.

AuthorsOpenReview ↗

Official Comment by Authors [2/4]

2. Experimental comparison. Following the reviewer’s suggestion, we added Restart+GLB-OMD to directly compare periodic restarting with discounting. The table below reports cumulative dynamic regret at T=5000T=5000, averaged over 20 runs, with standard deviations in parentheses. Here, SS is the parameter-norm bound, and the final column reports the percentage reduction in mean regret achieved by DOMD-GLB relative to Restart+GLB-OMD.

EnvironmentSSRestart+GLB-OMDDOMD-GLB (ours)Reduction in mean regret
Drifting1357.0 (37.4)73.0 (23.2)79.6%
Drifting3485.2 (30.3)75.3 (33.6)84.5%
Piecewise-stationary1398.8 (44.0)239.5 (36.2)39.9%
Piecewise-stationary3505.8 (32.4)411.6 (42.7)18.6%

The additional experiments show substantially lower regret for DOMD-GLB under continuous drift and a smaller but consistent improvement under piecewise stationarity. The larger gains under continuous drift support our motivation for gradual forgetting. These results complement our theoretical discussion above: the stationary guarantee of GLB-OMD does not directly establish a guarantee for its restarted version under within-block drift, which requires additional analysis. The empirical advantage of discounting under continuous drift is also consistent with the findings of Wang et al. [2, Sections 1 and 7], who report advantages of weighted strategies over restart-based methods in gradually evolving environments.

We thank the reviewer for this constructive feedback. It prompted an informative additional comparison and helped us clarify the scope of our contribution and strengthen the empirical evaluation.

[1] Zhang, Y.-J., Xu, S.-A., Zhao, P., and Sugiyama, M. (2025). Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update. NeurIPS.

[2] Wang, J., Zhao, P., and Zhou, Z.-H. (2023). Revisiting Weighted Strategy for Non-stationary Parametric Bandits. AISTATS.


Additional experiments

We have expanded the evaluation along three axes: dimension, reward model, and parameter trajectory. We also added Restart+GLB-OMD to isolate the effect of discounting from the use of a one-pass estimator.

To provide a fairer experimental comparison, as suggested by Reviewer APUU, we separately tuned the confidence-radius multiplier for each algorithm and experimental configuration over 0.1,0.2,0.5,1.0\\{0.1,0.2,0.5,1.0\\} using 20 random seeds. We report the results for the multiplier achieving the lowest mean cumulative regret at the final round. Throughout the tables below, regret denotes mean cumulative dynamic regret at T=5000T=5000, with standard deviations in parentheses. The two lowest mean regrets in each configuration are highlighted in bold.

1. Does DOMD-GLB maintain low regret and computational efficiency as the dimension increases?

To directly address Question 2, we evaluated d∈5,10,20d\in\\{5,10,20\\} in both drifting and piecewise-stationary environments, using Bernoulli rewards and S=1S=1. The tables report both regret and mean total computation time over all T=5000T=5000 rounds.

Drifting

Algorithmd=5d=5: RegretTime (s)d=10d=10: RegretTime (s)d=20d=20: RegretTime (s)
GLB-OMD206.9 (19.3)1.18268.8 (32.7)1.82369.8 (25.1)1.96
Restart+GLB-OMD357.0 (37.4)1.34377.7 (38.3)1.21348.9 (29.1)1.32
RestartGLB420.4 (25.7)37.02394.6 (25.1)41.76354.5 (26.5)58.38
MASTER+GLM-UCB798.1 (21.6)20.12698.8 (10.3)20.82538.3 (4.4)20.26
BVD-GLM-UCB621.5 (18.9)6383.50562.3 (15.8)6499.66461.1 (4.1)6339.63
SCB-WeightUCB82.9 (21.6)9.51118.3 (27.4)9.00180.2 (35.9)11.61
DOMD-GLB (ours)73.0 (23.1)1.47104.4 (41.6)1.22167.4 (38.4)1.49

Piecewise-stationary

Algorithmd=5d=5: RegretTime (s)d=10d=10: RegretTime (s)d=20d=20: RegretTime (s)
GLB-OMD723.2 (31.8)1.08618.8 (16.6)1.67484.3 (20.2)1.36
Restart+GLB-OMD398.8 (44.0)1.33386.7 (36.9)1.37358.3 (35.0)1.39
D-GLUCB304.0 (30.8)27.04347.3 (35.4)12.13355.7 (29.3)12.66
MASTER+GLM-UCB811.2 (19.8)22.60705.3 (10.6)19.38542.4 (4.6)21.20
SC-D-GLUCB563.3 (30.5)10.09520.8 (27.9)10.59437.4 (25.7)11.43
SCB-PW-WeightUCB283.4 (39.3)9.66316.8 (27.6)10.26348.9 (34.8)10.76
DOMD-GLB (ours)239.5 (36.2)1.24291.8 (34.1)1.35372.5 (42.8)1.29
AuthorsOpenReview ↗

Official Comment by Authors [3/4]

DOMD-GLB achieves the lowest mean regret at all three dimensions. Compared with SCB-WeightUCB, which has the second-lowest mean regret in each configuration, DOMD-GLB is approximately 6.5–7.8 times faster at matching dimensions. Its runtime is also close to that of the stationary and restarted one-pass OMD baselines, while its regret is substantially lower.

DOMD-GLB achieves the lowest mean regret at d=5d=5 and d=10d=10. At d=20d=20, it ranks fourth, with mean regret approximately 6.8% above that of SCB-PW-WeightUCB, the best-performing method in this configuration. Across the three dimensions, DOMD-GLB is approximately 7.6–8.3 times faster than SCB-PW-WeightUCB.

These comparisons extend the empirical evidence for DOMD-GLB’s computational efficiency beyond the original d=5d=5 setting.

2. Does the performance extend beyond logistic Bernoulli rewards?

To address the reward-model concern in Weakness 2, we added Binomial and Poisson observations under both forms of nonstationarity. With z=x⊤θtz=x^\top\theta_t, the additional models are Y∼Binomial(4,σ(z))Y\sim\mathrm{Binomial}(4,\sigma(z)) and Y∼Poisson(ez)Y\sim\mathrm{Poisson}(e^z). The Binomial model tests bounded count rewards with mean 4σ(z)4\sigma(z). The Poisson model tests a different mean link, eze^z, and unbounded observations. We therefore treat the Poisson experiments as an empirical evaluation beyond the bounded-reward assumption of our theory.

Drifting

AlgorithmBernoulliBinomial(4)Poisson
GLB-OMD211.9 (43.1)630.8 (58.0)999.8 (56.9)
Restart+GLB-OMD354.5 (40.2)822.1 (79.7)1286.0 (116.1)
RestartGLB410.3 (27.6)1097.2 (55.1)5074.6 (32.9)
MASTER+GLM-UCB807.0 (22.1)3009.0 (94.9)5703.4 (41.6)
BVD-GLM-UCB612.4 (13.5)1611.6 (55.2)5453.3 (29.8)
SCB-WeightUCB82.0 (25.1)226.1 (35.5)3452.2 (18.5)
DOMD-GLB (ours)63.8 (14.0)144.1 (21.5)146.7 (56.6)

Piecewise-stationary

AlgorithmBernoulliBinomial(4)Poisson
GLB-OMD730.5 (28.3)2714.5 (69.6)4449.5 (19.4)
Restart+GLB-OMD387.0 (37.7)982.1 (91.7)1488.1 (140.0)
D-GLUCB317.1 (21.6)1193.5 (113.0)4094.7 (40.7)
MASTER+GLM-UCB815.7 (24.4)3039.1 (90.3)5752.9 (47.0)
SC-D-GLUCB565.5 (27.8)1627.0 (44.7)4470.9 (46.8)
SCB-PW-WeightUCB283.0 (39.5)1019.1 (51.5)3643.9 (17.6)
DOMD-GLB (ours)239.5 (36.2)1057.3 (70.4)953.5 (63.3)

DOMD-GLB achieves the lowest mean regret in five of the six configurations, including all three drifting environments and the piecewise-stationary Bernoulli and Poisson environments. In the remaining configuration with piecewise-stationary Binomial rewards, its mean regret is within 8% of the best-performing baseline. These results support its empirical effectiveness across the tested reward models, including bounded count rewards and a Poisson model beyond the scope of our current theoretical guarantees.

3. Does the performance extend beyond one smooth trajectory and one abrupt change?

To address the concern about limited nonstationarity patterns, we evaluated six trajectories with different temporal and geometric characteristics. These experiments use Bernoulli rewards with T=5000T=5000, d=5d=5, and S=1S=1.

  • Drifting — Rotation (One Turn): The parameter completes one full rotation along a circle on the unit sphere within a fixed plane.
  • Drifting — Rotation (Half Turn): The parameter completes approximately half a rotation along the same circle.
  • Drifting — Random Walk: At each round, we add independent Gaussian noise ϵt∼N(0,0.0052Id)\epsilon_t\sim\mathcal{N}(0,0.005^2I_d) and project onto the unit ball: θt+1=Π∣θ∣2≤1(θt+ϵt)\theta_{t+1}=\Pi_{\\{\\|\theta\\|_2\leq1\\}}(\theta_t+\epsilon_t). Both direction and magnitude can vary across all dimensions.
  • Piecewise-stationary — One Fixed Changepoint: The parameter remains constant within each segment and reverses direction halfway through the horizon.
  • Piecewise-stationary — One Random Changepoint: The change time is sampled as τ∼Unif100,…,T−100\tau\sim\mathrm{Unif}\\{100,\ldots,T-100\\}. The parameter is θt=v1\theta_t=v_1 for t≤τt\leq\tau and θt=v2\theta_t=v_2 thereafter, where vi=gi/∣gi∣2v_i=g_i/\\|g_i\\|_2 and g1,g2∼i.i.d.N(0,Id)g_1,g_2\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,I_d), independently of τ\tau. Thus, both the change time and the parameter directions are random.
  • Piecewise-stationary — Two Fixed Changepoints: The parameter reverses direction at approximately one-third and two-thirds of the horizon, creating three stationary segments.
Reviewer_APUUOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies nonstationary generalized linear bandits and proposes an algorithm based on discounted online mirror descent. It replaces repeated weighted maximum likelihood estimation with an incremental update whose computation and memory requirements do not grow with the number of rounds. The paper establishes a uniform confidence bound and derives dynamic regret guarantees for drifting and piecewise stationary environments. Validation consists of synthetic logistic bandit experiments against several baselines, showing competitive regret and nearly constant per round runtime in the tested settings.

Critical strengths

The algorithm avoids storing and repeatedly processing past observations and does not require the nonconvex projection used by several existing methods. This offers a practical advantage for long running online applications and is a major factor supporting acceptance.

The authors address the challenges introduced by discounted geometry, uniform concentration, and parameter drift. The resulting drifting regret rate matches that of a representative weighted likelihood method while supporting time varying action sets, making the contribution more than a straightforward estimator replacement.

Critical weaknesses

The optimized regret guarantees require oracle tuning. The discount factor depends on the unknown path length in drifting environments and on the unknown number of changes in piecewise stationary environments. Thus, although one algorithm applies to both settings, its strongest guarantees are not available without prior knowledge of nonstationarity, limiting practical relevance.

The empirical evidence is not sufficiently comprehensive or conclusive. Experiments are limited to low dimensional synthetic logistic problems with a few specific parameter trajectories. Some baselines operate outside their established theoretical settings, nonconvex projections are approximated, and all confidence radii receive a common scaling. These factors weaken the fairness of comparisons and prevent the results from firmly supporting broad empirical superiority.

Questions for authors

Please address the concerns raised in the Weaknesses section. I am willing to reconsider and increase my score.

5 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/4]

We sincerely thank the reviewer for taking the time to review our paper and provide constructive feedback. We also appreciate the overall positive initial evaluation. Below, we address the reviewer’s concerns.


Regarding oracle tuning and practical applicability

To address the reviewer’s concerns about oracle tuning, we outline a possible BOB-based extension that would not require prior knowledge of PTP_T or ΓT\Gamma_T. We also provide empirical results showing that a discount factor chosen using only dd and TT can achieve performance comparable to that obtained with oracle tuning.

1. Adapting to unknown nonstationarity via BOB

While our optimized regret guarantees require tuning the discount factor using PTP_T or ΓT\Gamma_T, a natural extension is to select it through a bandit-over-bandit (BOB) procedure, following the approaches studied or discussed by Faury et al. (2021), Russac et al. (2021), and Wang et al. (2026, Appendix H) [1].

We expect that a similar BOB extension of DOMD-GLB could provide regret guarantees without prior knowledge of PTP_T or ΓT\Gamma_T, under exogenous time-varying action sets. The procedure would select a discount factor for each block and restart DOMD-GLB at block boundaries. The BOB bounds presented by Faury et al. (2021), Russac et al. (2021), and Wang et al. (2026, Appendix H) [1] all include an additional term with d1/2T3/4d^{1/2}T^{3/4} scaling, up to logarithmic factors and model-dependent coefficients. We expect a similar additional term for DOMD-GLB. In the piecewise-stationary setting, this term could worsen the dependence on TT from T2/3T^{2/3} to T3/4T^{3/4} when the number of changes is small, as also occurs in the BOB extension discussed by Russac et al. (2021).

Since establishing a formal guarantee for this extension requires a separate analysis and additional time, we will include this discussion and the full proof in the revised manuscript.

[1] Jing Wang, Peng Zhao, and Zhi-Hua Zhou. Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs. arXiv:2601.01069, 2026. https://arxiv.org/abs/2601.01069.

2. Empirical evaluation of a discount factor independent of PTP_T and ΓT\Gamma_T

Though obtaining the budget-optimized regret rates requires tuning the discount factor using unknown PTP_T or ΓT\Gamma_T, Theorems 2 and 3 provide regret bounds for every fixed γ∈[1/T,1)\gamma \in [1/T,1), including choices made without knowledge of either budget. Once γ\gamma is specified, both the parameter update and the action-selection rule are implementable without either budget. The prior knowledge is therefore needed to optimize the theoretical bounds over γ\gamma.

To directly examine the practical implications of this tuning requirement, we conducted additional experiments using simple choices of γ\gamma that depend only on dd and TT. The tables below report the mean cumulative dynamic regret over 20 runs at T=5000T=5000, with S=1S=1 and standard deviations in parentheses.

Drifting setting

AlgorithmCumulative regret at T=5000T=5000
GLB-OMD141.9 (17.8)
RestartGLB379.1 (28.7)
MASTER+GLM-UCB833.1 (19.9)
BVD-GLM-UCB546.6 (24.5)
SCB-WeightUCB149.3 (20.9)
DOMD-GLB (known PTP_T)94.9 (35.3)
DOMD-GLB (γ=1−(dT)−1/2\gamma=1-(dT)^{-1/2})83.5 (29.6)
DOMD-GLB (γ=1−T−1/2\gamma=1-T^{-1/2})91.8 (37.0)

Piecewise-stationary setting

AlgorithmCumulative regret at T=5000T=5000
GLB-OMD783.2 (14.5)
D-GLUCB311.3 (28.2)
MASTER+GLM-UCB836.8 (18.0)
SC-D-GLUCB425.0 (23.2)
SCB-PW-WeightUCB310.8 (26.2)
DOMD-GLB (known ΓT\Gamma_T)268.7 (41.7)
DOMD-GLB (γ=1−(dT)−2/3\gamma=1-(dT)^{-2/3})358.9 (40.3)
DOMD-GLB (γ=1−T−2/3\gamma=1-T^{-2/3})264.7 (35.9)

In the drifting setting, both choices that do not use PTP_T yield lower mean regret than the budget-informed choice. In the piecewise-stationary setting, the simple TT-only choice achieves comparable performance to the choice using known ΓT\Gamma_T. Thus, simple discount factors requiring no knowledge of the nonstationarity budget can achieve comparable performance to budget-informed tuning in the tested environments.

Our main contribution is a computationally efficient DOMD estimator and its regret analysis under both forms of nonstationarity, with per-round computation and memory independent of the elapsed number of rounds. These additional experiments support its practical usefulness when the budget is unknown. Matching the regret rates achieved with a known budget, without prior knowledge of that budget, remains an open direction.

AuthorsOpenReview ↗

Official Comment by Authors [2/4]

Additional experiments

We have expanded the evaluation to examine confidence-radius tuning, higher dimensions, additional reward distributions, and different nonstationary parameter trajectories. We address each concern separately below.

1. Confidence-radius search

To address the concern about applying a common scaling factor to all confidence radii, we tuned the multiplier applied to each algorithm’s theoretical confidence bound separately for each experimental configuration. We evaluated each multiplier in 0.1,0.2,0.5,1.0\\{0.1, 0.2, 0.5, 1.0\\} over 20 random seeds and plotted the results for the multiplier achieving the lowest mean cumulative regret at the final round. All results below follow this procedure. We expect this algorithm- and configuration-specific tuning to provide a fairer comparison.

Below, we additionally included a simple restarted variant of GLB-OMD (Restart+GLB-OMD) in response to Reviewer nfuc’s suggestion, although its theoretical regret guarantee does not directly extend to the drifting setting.

2. Varying dimension

We extended the evaluation to d∈5,10,20d \in \\{5,10,20\\} under both drifting and piecewise-stationary environments, with T=5000T=5000 and S=1S=1 (20 random seeds). The tables below report mean cumulative dynamic regret, with standard deviations in parentheses. Time denotes the mean total computation time over T=5000T=5000 rounds, measured in seconds. The two lowest regrets in each dimension are highlighted in bold.

Drifting

Algorithmd=5d=5: RegretTime (s)d=10d=10: RegretTime (s)d=20d=20: RegretTime (s)
GLB-OMD206.9 (19.3)1.18268.8 (32.7)1.82369.8 (25.1)1.96
Restart+GLB-OMD357.0 (37.4)1.34377.7 (38.3)1.21348.9 (29.1)1.32
RestartGLB420.4 (25.7)37.02394.6 (25.1)41.76354.5 (26.5)58.38
MASTER+GLM-UCB798.1 (21.6)20.12698.8 (10.3)20.82538.3 (4.4)20.26
BVD-GLM-UCB621.5 (18.9)6383.50562.3 (15.8)6499.66461.1 (4.1)6339.63
SCB-WeightUCB82.9 (21.6)9.51118.3 (27.4)9.00180.2 (35.9)11.61
DOMD-GLB (ours)73.0 (23.1)1.47104.4 (41.6)1.22167.4 (38.4)1.49

Piecewise-stationary

Algorithmd=5d=5: RegretTime (s)d=10d=10: RegretTime (s)d=20d=20: RegretTime (s)
GLB-OMD723.2 (31.8)1.08618.8 (16.6)1.67484.3 (20.2)1.36
Restart+GLB-OMD398.8 (44.0)1.33386.7 (36.9)1.37358.3 (35.0)1.39
D-GLUCB304.0 (30.8)27.04347.3 (35.4)12.13355.7 (29.3)12.66
MASTER+GLM-UCB811.2 (19.8)22.60705.3 (10.6)19.38542.4 (4.6)21.20
SC-D-GLUCB563.3 (30.5)10.09520.8 (27.9)10.59437.4 (25.7)11.43
SCB-PW-WeightUCB283.4 (39.3)9.66316.8 (27.6)10.26348.9 (34.8)10.76
DOMD-GLB (ours)239.5 (36.2)1.24291.8 (34.1)1.35372.5 (42.8)1.29

DOMD-GLB achieves the lowest mean regret in the drifting environments across all tested dimensions. Its total computation time over T=5000T=5000 rounds is approximately 1.22–1.49 seconds, compared with 9.00–11.61 seconds for SCB-WeightUCB, which has the second-lowest regret. This corresponds to a 6.5–7.8× speedup at matching dimensions.

In the piecewise-stationary experiments, DOMD-GLB achieves the lowest mean regret at d=5d=5 and d=10d=10. At d=20d=20, SCB-PW-WeightUCB achieves the lowest regret, while DOMD-GLB ranks fourth. Across all three dimensions, DOMD-GLB requires only 1.24–1.35 seconds for T=5000T=5000 rounds, compared with9.66–10.76 seconds for SCB-PW-WeightUCB, making it 7.6–8.3× faster.

3. Additional reward models: Binomial and Poisson

We expanded the evaluation beyond Bernoulli rewards to include Binomial and Poisson observations under both forms of nonstationarity. Specifically, with z=x⊤θtz=x^\top\theta_t, we consider Y∼Binomial(4,σ(z))Y \sim \mathrm{Binomial}(4,\sigma(z)) and Y∼Poisson(ez)Y \sim \mathrm{Poisson}(e^z). The Binomial model extends the evaluation to bounded count rewards, with mean 4σ(z)4\sigma(z). The Poisson model introduces a different mean link, eze^z, and unbounded count observations, providing an additional empirical evaluation beyond the bounded-reward assumption of our theoretical analysis.

AuthorsOpenReview ↗

Official Comment by Authors [3/4]

The tables below report mean cumulative dynamic regret at T=5000T=5000, with standard deviations in parentheses. The two lowest mean regrets in each column are highlighted in bold.

Drifting

AlgorithmBernoulliBinomial(4)Poisson
GLB-OMD211.9 (43.1)630.8 (58.0)999.8 (56.9)
Restart+GLB-OMD354.5 (40.2)822.1 (79.7)1286.0 (116.1)
RestartGLB410.3 (27.6)1097.2 (55.1)5074.6 (32.9)
MASTER+GLM-UCB807.0 (22.1)3009.0 (94.9)5703.4 (41.6)
BVD-GLM-UCB612.4 (13.5)1611.6 (55.2)5453.3 (29.8)
SCB-WeightUCB82.0 (25.1)226.1 (35.5)3452.2 (18.5)
DOMD-GLB (ours)63.8 (14.0)144.1 (21.5)146.7 (56.6)

Piecewise-stationary

AlgorithmBernoulliBinomial(4)Poisson
GLB-OMD730.5 (28.3)2714.5 (69.6)4449.5 (19.4)
Restart+GLB-OMD387.0 (37.7)982.1 (91.7)1488.1 (140.0)
D-GLUCB317.1 (21.6)1193.5 (113.0)4094.7 (40.7)
MASTER+GLM-UCB815.7 (24.4)3039.1 (90.3)5752.9 (47.0)
SC-D-GLUCB565.5 (27.8)1627.0 (44.7)4470.9 (46.8)
SCB-PW-WeightUCB283.0 (39.5)1019.1 (51.5)3643.9 (17.6)
DOMD-GLB (ours)239.5 (36.2)1057.3 (70.4)953.5 (63.3)

DOMD-GLB demonstrates consistently strong performance across all six tested combinations of reward model and nonstationarity setting. It achieves the lowest mean regret in all three drifting environments and in the piecewise-stationary Bernoulli and Poisson environments. In the remaining setting with piecewise-stationary Binomial rewards, its mean regret is within 8% of the best-performing baseline. These comparisons suggest that its favorable empirical performance extends beyond Bernoulli rewards and is robust across the tested reward distributions and forms of nonstationarity.

4. Different parameter trajectories

We expanded the evaluation to six environments with different temporal and geometric patterns of nonstationarity. All settings use Bernoulli rewards with T=5000T=5000, d=5d=5, and S=1S=1.

  • Drifting — Rotation (One Turn): The parameter completes one full rotation along a circle on the surface of the unit ball, within a fixed plane.
  • Drifting — Rotation (Half Turn): The parameter completes approximately half a rotation along the same circle on the surface of the unit ball.
  • Drifting — Random Walk: At each round, we add independent Gaussian noise ϵt∼N(0,0.0052Id)\epsilon_t \sim \mathcal{N}(0,0.005^2 I_d) to the parameter and project the result onto the unit ball: θt+1=Π∣θ∣2≤1(θt+ϵt)\theta_{t+1}=\Pi_{\\{\\|\theta\\|_2\le1\\}}(\theta_t+\epsilon_t). This allows both its direction and magnitude to vary across all dimensions.
  • Piecewise-stationary — One Fixed Changepoint: The parameter remains constant within each segment and reverses direction at t=T/2t=T/2.
  • Piecewise-stationary — One Random Changepoint: We sample the first segment length uniformly as τ∼Unif100,…,T−100\tau \sim \mathrm{Unif}\\{100,\ldots,T-100\\}, ensuring that both segments contain at least 100 rounds. The parameter is θt=v1\theta_t=v_1 for t≤τt\le\tau and θt=v2\theta_t=v_2 thereafter, where vi=gi/∣gi∣2v_i=g_i/\\|g_i\\|_2 and g1,g2∼i.i.d.N(0,Id)g_1,g_2\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,I_d), independently of τ\tau. Thus, both the change time and the new direction are random.
  • Piecewise-stationary — Two Fixed Changepoints: The parameter reverses direction at t=T/3t=T/3 and t=2T/3t=2T/3, creating three stationary segments.

The tables below summarize the supplied regret statistics at T=5000T=5000, with standard deviations in parentheses. The two lowest mean regrets in each column are highlighted in bold.

Drifting

AlgorithmRotation (One Turn)Rotation (Half Turn)Random Walk
GLB-OMD211.8 (43.1)459.4 (61.3)364.2 (56.5)
Restart+GLB-OMD354.5 (40.2)307.8 (40.4)548.7 (31.1)
RestartGLB410.3 (27.6)404.6 (18.4)611.2 (32.4)
MASTER+GLM-UCB807.0 (22.0)819.0 (19.1)747.7 (51.5)
BVD-GLM-UCB612.4 (13.5)587.0 (19.0)660.0 (35.2)
SCB-WeightUCB82.0 (25.1)316.3 (40.6)142.3 (32.3)
DOMD-GLB (ours)63.8 (14.0)257.4 (51.4)118.3 (39.5)

Piecewise-stationary

AlgorithmOne Fixed ChangepointOne Random ChangepointTwo Fixed Changepoints
GLB-OMD730.5 (28.2)306.2 (135.0)643.0 (37.0)
Restart+GLB-OMD387.0 (37.7)259.5 (45.1)356.1 (28.4)
D-GLUCB317.1 (21.6)234.2 (71.2)526.9 (26.0)
MASTER+GLM-UCB815.7 (24.4)827.9 (17.4)817.7 (21.4)
SC-D-GLUCB565.5 (27.8)279.3 (136.2)581.8 (14.9)
SCB-PW-WeightUCB283.0 (39.4)237.0 (91.5)504.7 (30.7)
DOMD-GLB (ours)239.5 (36.2)199.3 (75.4)314.0 (52.6)

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.