Source-linked AI summary
Weighted Linear Bandits for Non-Stationary Environments
Yoan Russac, Claire Vernade, Olivier Cappé
TL;DR
Changing preferences can make past bandit observations obsolete, motivating adaptive learning for linear rewards with time-varying parameters. The paper develops D-LinUCB using weighted least-squares and exponential discounting, and reports high-probability dynamic-regret guarantees for changing environments, including a bound matching a known lower-bound order under horizon-dependent tuning.
Problem
In linear-bandit problems with evolving preferences, past interaction data becomes progressively obsolete, motivating adaptive learning rather than periodic restarts.
Source: §1 · p. 1Method
D-LinUCB combines weighted least-squares with exponential weights to adapt a linear-bandit learner to changing parameters.
Source: §1 · p. 2, §3 · p. 4, §3.1 · p. 4Results
With horizon- and variation-dependent tuning of γ, D-LinUCB has a high-probability regret upper bound of the same order as a lower bound established for a specific non-contextual setting [4].
Source: §3.2 · p. 6Takeaways & Limitations
The weighted least-squares deviation results are presented as useful beyond non-stationary bandits, including heteroscedastic environments and class-imbalance situations.
Source: §1 · p. 1, §2 · p. 3The analysis assumes bounded action vectors and bounded time-varying parameter norms.
Source: §1.1 · p. 2
Abstract
from arXiv · showhide
We consider a stochastic linear bandit model in which the available actions correspond to arbitrary context vectors whose associated rewards follow a non-stationary linear regression model. In this setting, the unknown regression parameter is allowed to vary in time. To address this problem, we propose D-LinUCB, a novel optimistic algorithm based on discounted linear regression, where exponential weights are used to smoothly forget the past. This involves studying the deviations of the sequential weighted least-squares estimator under generic assumptions. As a by-product, we obtain novel deviation results that can be used beyond non-stationary environments. We provide theoretical guarantees on the behavior of D-LinUCB in both slowly-varying and abruptly-changing environments. We obtain an upper bound on the dynamic regret that is of order d^{2/3} B\_T^{1/3}T^{2/3}, where B\_T is a measure of non-stationarity (d and T being, respectively, dimension and horizon). This rate is known to be optimal. We also illustrate the empirical performance of D-LinUCB and compare it with recently proposed alternatives in simulated environments.
1 Introduction
The introduction frames linear bandits as a setting where changing preferences make old observations obsolete, and motivates adaptive learning through weighted least-squares. It presents new deviation results and D-LinUCB, while situating the work among approaches to changing environments.
1 Introduction
- Online recommendation motivates adaptation because evolving item interests make collected interaction data progressively obsolete, favoring forgetting over periodic restarts.The paper models this as a linear-bandit parameter that evolves over time.Source: §1 · p. 1, §1.1 · p. 2
- The paper extends deviation inequalities to sequential weighted least-squares, with potential use in non-stationary bandits, heteroscedastic settings, and class-imbalance situations.The extension also advances analysis of heteroscedastic environments [18].Source: §1 · p. 1
- D-LinUCB uses exponential weights for adaptive linear bandits and is fully recursive, requiring no storage of past actions and having numerical complexity comparable to LinUCB.Its analysis covers abruptly changing and slowly varying environments.Source: §1 · p. 2
1.1 Model and Notations
- The model allows arbitrary feasible action sets and time-varying parameters, with bounded actions and parameter norms; its goal is dynamic regret against the changing optimal action.Special action sets recover non-contextual multi-armed bandits and contextual bandits with shared time-varying context vectors.Source: §1.1 · p. 2
1.2 Related Work
- A variation budget covers both slowly varying and abruptly changing parameters; prior linear-bandit work used sliding windows, while discount-factor methods can be implemented recursively.The cited sliding-window linear-bandit result has dynamic regret order O(d^2/3 B_T^1/3 T^2/3).Source: §1.2 · pp. 2–3
- Change-point approaches include methods requiring prior knowledge of gaps or the change count; a contextual pool-of-LinUCB approach may not adapt to slow drift.Sliding-window and change-point methods require storing past actions, unlike discount-factor methods.Source: §1.2 · p. 3
2 Confidence Bounds for Weighted Linear Bandits
This section develops concentration results for weighted regularized least-squares in sequential settings, where current regressors can depend on past random outcomes. Its deviation bound accounts for the squared weights that determine estimator variance and extends to heteroscedastic and non-stationary models.
2 Confidence Bounds for Weighted Linear Bandits
- The section extends concentration analysis to weighted regularized least-squares with general weights and regularization in sequential learning, where regressors may depend on past outcomes.The authors describe the bound as potentially useful beyond the paper's specific model.Source: §2 · p. 3
- When weights vary, the deviation bound uses a matrix tied to squared weights because the estimator's variance depends on those squares.With unit weights and matching regularization, the standard least-squares result is recovered.Source: §2 · p. 4
- The estimator is scale-invariant when all weights and the regularization parameter are multiplied by the same constant; the confidence construction chooses its auxiliary parameter accordingly.This makes the associated upper bound scale-invariant as well.Source: §2 · p. 4
- The results extend to heteroscedastic noise and to the non-stationary model, with the extension relying on bounded parameter norms.For heteroscedastic noise, the noise scale is assumed measurable from past information.Source: §2 · p. 4
3 Application to Non-stationary Linear Bandits
D-LinUCB applies weighted least-squares with exponential discounting to adapt linear bandits to changing parameters. Its analysis provides regret guarantees for abrupt and gradual change, with a high-probability bound whose order matches a known lower bound under horizon-dependent tuning.
3 Application to Non-stationary Linear Bandits
- The proposed algorithm and analysis target both abruptly changing and slowly drifting parameters.The paper presents this as reliable performance across both types of environments.Source: §3 · p. 4
3.1 The D-LinUCB Algorithm
- D-LinUCB uses exponentially increasing weights w_t=γ^-t, with 0<γ<1, to reduce the influence of older observations as parameters change.The algorithm also uses increasing regularization; a scale-invariant form supports numerical stability and recursive updates.Source: §3.1 · pp. 4–5
3.2 Analysis
- The regret analysis separates non-stationarity bias from the confidence-bound contribution, using an analysis parameter D to control how much recent parameter variation contributes.The true parameter need not lie in the confidence ellipsoid; the proof instead uses an action-dependent surrogate that does belong with high probability.Source: §3.2 · pp. 5–6
- With discount factor γ tuned using the horizon and variation bound, D-LinUCB's high-probability regret upper bound has the same order as a lower bound established in a specific non-contextual setting.The guarantee requires horizon-dependent tuning of γ.Source: §3.2 · p. 6
4 Experiments
Experiments compare D-LinUCB with sliding-window and change-detection alternatives in abrupt and slowly varying synthetic settings and a high-dimensional interaction-data simulation. Adaptation benefits depend on the environment, with a trade-off between using all available data and recovering after a breakpoint.
4 Experiments
- The experiments compare D-LinUCB with dLinUCB and SW-LinUCB, and include an oracle that restarts at known change-points for abrupt changes.The oracle’s regret serves as an empirical lower bound on optimal behavior in abruptly changing environments.Source: §4 · pp. 6–7
4.1 Synthetic data in abruptly-changing or slowly-varying scenarios
- In abrupt changes, dLinUCB often misses breakpoints—the second was detected in none of 100 runs—while D-LinUCB and SW-LinUCB estimators track the changing parameter with delay.LinUCB suffers linear regret for long periods after the last change-point.Source: Figure 1 · p. 7, §4.1 · pp. 7–8
- Under slow variation, D-LinUCB and SW-LinUCB are robust and track the parameter effectively, while LinUCB and dLinUCB lag behind.LinUCB can eventually catch up if the stationary period is longer.Source: Figure 1 · p. 7, §4.1 · p. 8
4.2 Simulation based on a real dataset
- After partial inversion, D-LinUCB and SW-LinUCB adapt faster and significantly outperform non-adaptive policies, while LinUCB performs better during the initial stationary period.The comparison uses 50-dimensional contexts from Criteo traffic data; LinUCB-OR performs best overall.Source: Figure 2 · p. 8, §4.2 · p. 8
A.1 Preliminary results
This section develops deviation results for sequential weighted least-squares under predictable weights and σ-subgaussian noise. Time-dependent probability measures support the sequential regularizations used in the concentration argument.
A.1 Preliminary results
- Integrating the process with a time-dependent probability measure is the key step for allowing sequential regularizations in the concentration inequality.The approach is inspired by the method of mixtures; time-dependent regularization is needed with exponential weights to avoid the vanishing effect of regularization.Source: §A.1 · pp. 11–12
- The proof develops fixed-time and stopped versions of preliminary lemmas before stating the main deviation result.The stopped version is given for Gaussian random vectors, and the deviation result is stated for predictable positive weights.Source: §A.1 · p. 12
- The section establishes a deviation inequality for predictable positive weights, extending results to sequential weighted least-squares.The analysis assumes conditionally σ-subgaussian noise.Source: §A.1 · pp. 11–12
A.2 Proof of Theorem 1
Theorem 1 is established for a stationary environment under a parameter-norm condition. The following analysis considers a non-stationary parameter that may evolve over time.
A.2 Proof of Theorem 1
- Theorem 1 is proved under stationarity, with the parameter norm bounded by 1/√µ_t at each time.Source: §A.2 · pp. 13–14
- The proof combines a high-probability bound on the noise term with a determinant upper bound for the weighted design matrix.Source: §A.2 · p. 14
B D-LinUCB Analysis
- In the D-LinUCB analysis, the environment is non-stationary when the unknown parameter θ⋆ may evolve over time.The reward generation process is stated to follow Equation (1).Source: B D-LinUCB Analysis · p. 14
B.1 Preliminary results
The preliminary results specialize weighted concentration and determinant bounds to geometrically discounted weights. They support confidence-set membership and control of action norms.
B.1 Preliminary results
- A determinant inequality bounds the weighted design matrix when action norms are bounded by L, with a geometric-weight form given in Corollary 2.Source: §B.1 · p. 15
- For weights w_t = γ^−t with 0 < γ < 1, Corollary 3 gives a deviation bound used to show that θ̄_t belongs to C_{t−1} with high probability.Source: §B.1 · p. 15
B.2 Control of the norm of actions
- The next subsection establishes a proposition controlling action norms using Lemma 4.Source: §B.2 · p. 16
B.3 Proof of Theorem 2
Theorem 2’s proof bounds instantaneous regret on a high-probability confidence event. It handles the deviation term and the bias term with different techniques.
B.3 Proof of Theorem 2
- On the event that θ̄_t lies in C_t, which holds with probability at least 1 − δ, the proof upper-bounds instantaneous regret.Source: §B.3 · p. 17
- The regret bound treats the deviation term with a non-stationary extension of Theorem 1 and the bias term separately.Source: §B.3 · pp. 17–18
- The passage specifies that for vectors x with Euclidean norm at most 1, the relevant indices p range from t−D through t−1.Source: §B.3 · p. 18
B.4 Proof of Corollary 1
The proof combines three terms and neglects logarithmic factors to obtain its stated result.
B.4 Proof of Corollary 1
- The proof snippets relate the target quantity to dimension and non-stationarity terms, but do not provide a complete readable bound.The displayed expressions are incomplete in the supplied passage text.Source: §B.4 · p. 19
- The proof adds three terms to derive the desired result.The passage does not specify the three terms in readable form.Source: §B.4 · p. 19
- Logarithmic factors are neglected in the final step.The stated conclusion follows after this simplification.Source: §B.4 · p. 19
C A new analysis of the SW-LinUCB algorithm
The authors give a new analysis of SW-LinUCB because they identify gaps in its previous proof, and note that weighted-model deviation inequalities do not apply to this analysis.
C A new analysis of the SW-LinUCB algorithm
- The new SW-LinUCB analysis addresses gaps identified in the earlier proof [11].The authors challenge both a lemma's applicability to a sliding window and a theorem's use of a fixed-direction result for a random action.Source: C A new analysis of the SW-LinUCB… · p. 19
- A fixed-direction deviation bound cannot be substituted with the action set when that set is strongly related to the estimator.The passage identifies this substitution in equation (42) of [11].Source: C A new analysis of the SW-LinUCB… · p. 19
- The authors place this analysis in the appendix because the weighted-model deviation inequalities cannot be used for it.They nevertheless say it provides new insights on the sliding-window problem.Source: C A new analysis of the SW-LinUCB… · p. 19
C.1 Deviation inequality
The sliding-window analysis treats estimates based on recent observations and develops deviation and design-matrix bounds despite the loss of information from discarding old actions.
C.1 Deviation inequality
- The estimate uses only the last l observations, and the analysis introduces a fictive regression model for an instantaneous deviation bound.The fictive model receives the same information as the true model over the window.Source: §C.1 · pp. 19–20
- At time t, the sliding-window update adds a new action and removes the oldest, so the supermartingale property used in prior reasoning no longer holds.The authors therefore say the reasoning in cannot be applied directly.Source: §C.1 · p. 20
- For the sliding-window setting, Proposition 5 states an instantaneous deviation inequality and Proposition 6 introduces a determinant inequality for the design matrix.The supplied passages do not expose the full bounds.Source: §C.1 · pp. 20–21
- Proposition 7 gives a further high-probability result for the sliding-window model.Its full statement is not included in the supplied passage text.Source: §C.1 · p. 21
C.2 Regret analysis
The SW-LinUCB regret analysis derives high-probability bounds and asymptotic rates, while noting costs associated with discarded observations and a larger confidence radius.
C.2 Regret analysis
- The regret analysis uses the confidence ellipsoid and combines deviation and bias bounds.The deviation term is handled using Proposition 8.Source: §C.2 · pp. 21, 23
- For t>l, information discarded by the sliding window contributes a logarithmic term to the regret bound.The passage identifies this as the cost of losing information at each step.Source: §C.2 · p. 21
- A union bound makes the confidence radius larger than the one suggested in [11], and the authors say this was not accounted for in SW-LinUCB simulations.This qualifies the implementation used in the comparison experiments.Source: §C.2 · p. 21
- With known B_T, choosing l = (dT/B_T)^(2/3) gives SW-LinUCB an asymptotic high-probability regret upper bound of O~(d^(2/3)B_T^(1/3)T^(2/3)).The bound omits logarithmic terms.Source: §C.2 · p. 25
- With unknown B_T, choosing l = d^(2/3)T^(2/3) gives an asymptotic high-probability regret upper bound of O~(d^(2/3)B_T T^(2/3)).The result is stated for T tending to infinity.Source: §C.2 · p. 25