- 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
-
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.
-
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:
-
In Section 3.1, I am not sure tau was defined. I assume it is a known parameter?
-
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.
-
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:
-
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.
-
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
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 and a constant parameter . Suppose the available actions are in the first phase and in the second phase.
In the first phase, the best available action is , giving an optimal mean reward of . In the second phase, the newly available action increases the optimal mean reward to . Each action’s mean reward remains unchanged; the increase comes entirely from the availability of a better action.
Let contain both phases and let lie entirely in the second phase. Then
If we attempted to extend the analysis while keeping proportional to parameter variation alone, we would have . The critical inequality in part (b) would then require 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 dependence an algorithmic or analytical limitation?
We believe that the additional 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 to . 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 too early. The remaining dependence appears in terms of lower order in when the other parameters are fixed, so the resulting guarantee is not entirely independent of .
We explain the main idea and proof outline below. We work on the high-probability confidence event of Theorem 1 and consider . Throughout, suppresses logarithmic factors, and we omit coefficients depending on , , , and to highlight the dependence on , , , and .
1. Where the current analysis loses precision. The quantity measures the uncertainty in the selected action’s direction: a larger value means that the discounted information matrix provides less information in that direction. We use as a common upper bound on the confidence radii.
Away from change points, our current proof bounds the instantaneous regret by , together with a small contribution from observations collected before the latest change. Here, 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 , obtaining
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 is precisely the quantity incorporated into the matrix update:
The key is to express the regret using this same local curvature, instead of immediately replacing the relevant slope by .
To see how, let be the gap between the optimal and selected actions before applying the link function. The action-selection rule and confidence bound give
where the term involving accounts for the remaining influence of past parameter changes.
Official Comment by Authors [3/5]
A Taylor expansion bounds the instantaneous regret as follows:
Here, we use the manuscript’s self-concordance property .
We next connect the slope at the true parameter, , to the curvature accumulated by the algorithm, . Since , the mean value theorem bounds the absolute difference between these slopes by . Thus, it suffices to control the error in the linear predictor associated with the updated estimate .
On rounds where , this error is controlled by the confidence bound at . Moreover, implies . Combining these observations gives
The last term again reflects past parameter changes. We refer to contributions involving or 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 . To control the quadratic term, we also use , which gives
Together with , these inequalities yield
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 , the discounted elliptical-potential argument directly controls the curvature-weighted uncertainty:
This bound has no inverse dependence on . Since , Cauchy–Schwarz gives
Here, we use 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
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 rounds without a change, the contribution of earlier segments is suppressed by a factor of order . Choosing , with a sufficiently large logarithmic factor, makes the total drift-tail contribution at most by Lemma D.2.
We also set aside the at most rounds immediately preceding a change, so that the comparison using the confidence bound at is valid. Thus, at most rounds are excluded around change points. Since each round incurs regret at most , their total contribution is . The first and last rounds can be treated separately at an additional cost of at most , which is absorbed into the bound below.
Adding the main statistical term, the quadratic remainder, and the contributions associated with change points gives
In the intermediate regime where is admissible, this becomes
The term therefore has no dependence. The remaining dependence appears in terms of lower order in when the other parameters are fixed; these terms can still matter when is small.
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 τ a known parameter?
Yes, τ is a fixed, known dispersion parameter of the reward distribution, and g(τ)>0 is the corresponding dispersion term. We will define τ 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,… 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(logt) 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 t observations requires O(td) memory to store the data. Computing its MLE using a standard dense Newton method costs O(td2+d3) per optimization iteration and requires additional O(d2) 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) computation and O(d2) memory per round for estimation, both independent of t.
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⋆:=maxx∈Xμ(x⊤θs⋆) denote the best achievable mean reward at round s. Because both rounds have the same feasible actions, the Lipschitz property of μ and ∣x∣2≤1 imply
∣vs+1⋆−vs⋆∣≤maxx∈X∣μ(x⊤θs+1⋆)−μ(x⊤θs⋆)∣≤kμ∣θs+1⋆−θs⋆∣2.
Thus, any change in the optimal reward must come from a change in the parameter. For a block B=[b,t], let PB:=∑s=bt−1∣θs+1⋆−θs⋆∣2. The preceding inequality gives
maxs∈Bvs⋆−mins∈Bvs⋆≤kμPB.
In particular, for any subinterval I⊆B,
∣I∣1∑s∈Ivs⋆−minu∈Bvu⋆≤kμPB.
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:=mins∈Bgs, where gs is the optimistic value reported by the active learner. Thus, Ut is the smallest optimistic reward estimate recorded in the current block.
At the end of a scheduled interval I, Test 1 compares its average observed reward, rˉI:=∣I∣−1∑s∈Irs, with this historical estimate. It triggers a restart if
rˉI≥Ut+9ρ(∣I∣),
where ρ(∣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≥mins∈Bvs⋆−ΔB≥∣I∣1∑s∈Ivs⋆−3ΔB,
where ΔB is their variation measure, proportional to PB 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.