PaperlayerView exact revision on arXiv

Source-linked AI summary

Unifying Clustered and Non-stationary Bandits

Chuanhao Li, Qingyun Wu, Hongning Wang

arXiv:2009.02463v1cs.LGstat.ML

TL;DR

Contextual bandit methods commonly assume time-invariant rewards, limiting their fit to settings with changing user interests. This paper uses tests of homogeneity to unify change detection and online clustering, and reports regret analysis and empirical validation in clustered, non-stationary environments.

  • Problem

    Contextual bandits commonly assume a time-invariant context-to-reward mapping, while changing interests and dependent users motivate non-stationary and clustered settings that have been studied separately.

    Source: §1 · pp. 1–2

  • Method

    The paper tests whether observations in a bandit model share a distribution with new observations or with observations from another model.

    Source: §1 · p. 2

  • Results

    The authors report an upper regret bound matching the ideal algorithm's bound up to a constant and empirical validation in non-stationary, clustered environments.

    Source: §5 · p. 13

  • Takeaways & Limitations

    The unified framework can support clustered non-stationary learning, resetting individual models after detected changes and merging models determined to be identical.

    Source: §1 · p. 2

    Change detection and cluster identification operate at the user level, and computations are centralized rather than asynchronous and distributed.

    Source: §5 · p. 13

Abstract

from arXiv · show

Non-stationary bandits and online clustering of bandits lift the restrictive assumptions in contextual bandits and provide solutions to many important real-world scenarios. Though the essence in solving these two problems overlaps considerably, they have been studied independently. In this paper, we connect these two strands of bandit research under the notion of test of homogeneity, which seamlessly addresses change detection for non-stationary bandit and cluster identification for online clustering of bandit in a unified solution framework. Rigorous regret analysis and extensive empirical evaluations demonstrate the value of our proposed solution, especially its flexibility in handling various environment assumptions.

1. Introduction

Contextual bandits often assume time-invariant rewards, limiting their fit to populations with changing interests or dependent users. The paper unifies change detection and cluster identification as tests of homogeneity between observations.

1. Introduction

  • Non-stationary bandits handle time-varying rewards, while online clustering identifies users whose bandit models are related.Piecewise-stationary settings have abrupt, unknown change points and remain stationary between changes; clustering instead groups users sharing a model.Source: §1 · pp. 1–2
  • Both research strands use goodness-of-fit ideas: change detection tests observations over time, while clustering tests similarity between bandit models.Change detection compares observed rewards or estimated reward quality in consecutive-observation windows; clustering compares model parameters or arm-specific reward estimates.Source: §1 · p. 2
  • The paper unifies the problems by testing whether observations in one model share a distribution with new observations or those from another model.The first comparison addresses change detection; the second addresses cluster identification.Source: §1 · p. 2
  • The framework is intended to support more flexible bandit models, including clustered non-stationary settings where models reset after detected changes and merge when identical.The paper reports rigorous regret analysis and empirical evaluations, emphasizing flexibility across environment assumptions.Source: §1 · p. 2

2. Related work

Related work treats non-stationary bandits and online clustering separately, though both can be understood through tests of homogeneity. Existing methods detect changes over time or assess relatedness between users' models.

2. Related work

  • For abruptly changing environments, prior non-stationary methods detect change points and reset models, or use tests that assess homogeneity over observation sequences.Approaches include likelihood-ratio tests, cumulative sum control charts, and generalized likelihood-ratio tests.Source: §2 · p. 2
  • Both lines of work assess whether observations or models are homogeneous, using different measures for temporal change and user relatedness.Non-stationary methods examine observation sequences over time, while clustering methods compare models associated with users or arms.Source: §2 · pp. 2–3
  • Online clustering methods infer user or arm groupings from estimated model-parameter differences or projected differences on individual arms.These methods assess whether observations associated with individual models are homogeneous.Source: §2 · pp. 2–3

3. Methodology

The methodology unifies change detection and model clustering through homogeneity testing in a bandit setting with per-user nonstationarity and shared parameters. It analyzes DyClu’s regret using high-probability results and a good/bad-event decomposition based on change detection and clustering.

3.1 Problem formulation

  • A general linear contextual bandit setting models users with potentially changing reward parameters and parameters shared across users and time, subsuming clustered and piecewise-stationary cases.The setup assumes detectable changes, separated unique parameters, and i.i.d. sub-Gaussian contexts with full-rank covariance.Source: §3.1 · pp. 3–4

3.2 Test statistic for homogeneity

  • The homogeneity test compares a pooled-estimator statistic with a threshold, avoiding estimator-distance tests that are effective only when both datasets have sufficient observations.The threshold controls type-I error, while type-II error also depends on the underlying parameters and noise variance.Source: §3.2 · pp. 5, 7
  • Useful type-II error control requires rank-sufficient designs and adequate parameter separation relative to noise; the test is uniformly most powerful at any specificity level.Its two error types correspond to early or late change detection and to missed or incorrect neighborhood assignments in clustering.Source: §3.2 · p. 7

3.3 Algorithm

  • DyClu uses a two-level hierarchy: per-user interval models support change detection, while homogeneity tests cluster current and outdated models for cross-time and cross-user reuse.It detects changes using a one-sample test with a sliding-window statistic, then aggregates sufficient statistics from neighboring models for UCB arm selection.Source: §3.3 · pp. 7–9

3.4 Regret analysis

  • DyClu’s upper regret bound under Assumptions 1–3 follows from separating correctly aggregated observations from errors in change detection or clustering.The analysis applies high-probability results and bounds bad-event occurrences using Lemmas 2 and 3.Source: §3.4 · p. 9
  • With one stationary user, DyClu achieves the same regret order as LinUCB.This setting has no late-detection regret, and clustering failures add only a constant depending on environment variables.Source: §3.4 · p. 10
  • With stationary users, DyClu achieves the same regret order as CLUB, with no late-detection regret and only constant regret from clustering failures.Source: §3.4 · p. 10
  • In the piecewise-stationary setting, DyClu’s regret depends on unique bandit parameters rather than stationary-period count, enabling lower regret when mappings recur.Unlike dLinUCB, DyClu can reuse observations from earlier stationary periods when they share the same parameter.Source: §3.4 · p. 10

4. Experiments

The experiments compare DyClu with stationary, non-stationary, and clustered-bandit baselines on synthetic environments and LastFM. DyClu performs best across the reported synthetic regimes and sensitivity settings, and improves normalized reward on LastFM.

4.1 Experiment setup and baselines

  • DyClu was tested against LinUCB, dLinUCB, adTS, and CLUB on synthetic data and LastFM, with oracle-LinUCB included in simulations.LastFM experiments used a processed dataset to simulate clustered non-stationarity; the synthetic experiments also included three environment settings.Source: §4 · p. 10, §4.1 · p. 11

4.2 Experiment results

  • Across all three synthetic settings, DyClu outperformed baselines and stayed closest to oracle-LinUCB, including asynchronous changes with shared parameters.The settings cover stationary clustering, piecewise stationarity, and their combination.Source: Figure 2 · p. 11, §4.2 · p. 11
  • DyClu outperformed baselines in all 9 settings; regret rose with more unique parameters, stationary periods, or Gaussian noise.The reported trends align with the regret analysis: more parameters split observations across smaller clusters, while more periods and noise affect detection or estimation.Source: Table 1 · p. 12, §4.2 · p. 12
  • DyClu improved normalized accumulated reward over baselines on LastFM, with its clearest advantage early in learning.Early on, local user models have fewer observations, making reward estimation, change detection, and clustering more difficult.Source: Figure 3 · p. 12, §4.2 · p. 12

5. Conclusion

The paper unifies non-stationary bandits and online clustering through homogeneity tests, with regret analysis and empirical evaluations supporting the approach. Its current user-level, centralized design leaves arm-level contextualization and asynchronous or distributed updates as directions for further work.

5. Conclusion

  • Homogeneity tests unify change detection and cluster identification, and the proposed approach is evaluated in non-stationary and clustered environments.The paper reports an upper regret bound matching the ideal algorithm up to a constant and empirical evaluations validating effectiveness.Source: §5 · p. 13
  • Change detection and cluster identification currently operate at the user level; arm-level contextualization remains a possible extension.The conclusion cites prior work on arm-level contextualization as a direction for future research.Source: §5 · p. 13
  • Computations are centralized, while asynchronous and distributed model updates are described as more practical.Source: §5 · p. 13

Appendix A. Notations used in this paper

Appendix A points readers to Table 2 for the paper's notation and descriptions.

Appendix A. Notations used in this paper

Appendix B. Proof of Lemma 4

The proof bounds early detection as a type-I error of the homogeneity test, using a Hoeffding inequality.

Appendix B. Proof of Lemma 4

  • Early detection is treated as a type-I error when the test rejects homogeneity despite no change, and its probability is bounded using Hoeffding's inequality.The text states the expectation bound in terms of F(υe; 1, 0) before applying the inequality.Source: Appendix B · p. 17
  • The proof invokes a 2-sub-Gaussian condition before applying Hoeffding's inequality.Source: Appendix B · p. 17

Appendix C. Proof of Theorem 5

Appendix C proves the upper regret bound by comparing the learner with an ideal algorithm that knows the true change points and clustering structure. The bound separates the reference algorithm's regret from additional regret due to late detection and incorrect clustering.

Appendix C. Proof of Theorem 5

  • The proof divides the upper-bound argument into establishing Eq. (3) and bounding its second and third terms with Lemmas 6 and 7.Source: Appendix C · p. 17
  • The learner uses observations from an estimated neighborhood because the true parameter-associated observation set is unavailable.The proof defines the estimated count using the neighborhood and the unique parameter index associated with the learner's history.Source: Appendix C · p. 17
  • A bad event can arise when missed change detection leaves the user's neighborhood incorrect, or when cluster identification is incorrect.The proof distinguishes late detection from incorrect clustering as sources of additional regret.Source: Appendix C · p. 18
  • The first regret-bound term matches an ideal reference algorithm with exact change points and clustering structure.That algorithm groups observations by their unique bandit parameter and aggregates them for arm selection.Source: Appendix C · pp. 17–18
  • Late detection and incorrect cluster identification contribute separate added-regret terms beyond the reference algorithm's regret.The proof bounds these terms in Lemmas 6 and 7, respectively.Source: Appendix C · pp. 18–19
  • The final upper regret bound combines Eq. (3) with the bounds from Lemmas 6 and 7, with a stated probability guarantee.Source: Appendix C · p. 19

C.1 Proof of Eq (3)

The proof bounds regret by separating times when DyClu uses the correct user-model cluster from times when detection or clustering fails. Under the good event it applies UCB to pooled observations; under the bad event it uses a bounded per-round regret.

C.1 Proof of Eq (3)

  • The bad event covers late detection and failures to cluster users with the same underlying bandit parameter correctly.These failures include incorrectly adding models to, or omitting models from, the estimated cluster.Source: §C.1 · p. 19
  • Under the good event, DyClu selects arms with UCB scores computed from observations associated with the user’s current bandit parameter.The analysis represents these observations using the reference algorithm’s notation.Source: §C.1 · p. 19
  • When the wrong cluster is used for arm selection, the proof bounds instantaneous regret by 2 using unit-norm parameter and context assumptions.The accumulated bound also includes the reference algorithm’s regret bound.Source: §C.1 · pp. 20–21

C.2 Proof of Lemma 6

The proof controls late detections by lower-bounding detection probability after a change and bounding the resulting number of missed detections. The window-size condition supports that detection bound, which then bounds the late-detection contribution to regret.

C.2 Proof of Lemma 6

  • A sliding window satisfying the stated lower-bound condition supports a detection probability of at least 1 − δ_e after a change.The detection bound follows from the preceding probability argument and the environment-dependent ψ_e.Source: §C.2 · pp. 21–22
  • The late-detection bound is developed per stationary period, whose count is tied to each user’s assumed number of change points.The proof follows a technique similar to Wu et al. (2018), Theorem 3.2.Source: §C.2 · pp. 22–23
  • With detection probability at least 1 − δ_e, the number of late detections after a change follows a geometric distribution.The proof uses this distribution to obtain a high-probability bound on late detections.Source: §C.2 · pp. 22–23
  • The proof bounds the late-detection contribution to the intermediate regret bound by controlling the total number of late detections.A late detection occurs when the learner fails to detect a change in the user’s underlying bandit parameter.Source: §C.2 · pp. 21, 23

C.3 Proof of Lemma 7

The proof bounds clustering errors using homogeneity-test error probabilities and controls periods with insufficiently informative observation histories. It also notes that the probability of correct clustering after a positive test depends on the population being tested.

C.3 Proof of Lemma 7

  • When two histories share the same underlying parameter, failure to cluster them together corresponds to the homogeneity test’s type-I error.The proof uses its upper bound to control the cluster-identification contribution to regret.Source: §C.3 · pp. 23, 25
  • When two histories have different underlying parameters, clustering them together corresponds to type-II error, with a nontrivial bound requiring informative design matrices.If either matrix is rank-deficient, the parameter difference may lie in its null space, making the noncentrality parameter zero.Source: §C.3 · p. 23
  • The probability that a positive homogeneity test reflects equal parameters depends on the population, ranging from 1 when all models match to 0 when all are unique.The proof relates this probability to population proportions of positive and negative instances.Source: §C.3 · pp. 24–25
  • The third regret term counts times when a user’s history has a small minimum eigenvalue, and the proof bounds these times across stationary periods.It uses the maximum number of rank-one context updates needed to reach a minimum-eigenvalue threshold, denoted HD.Source: §C.3 · pp. 25–26

Appendix D. Technical lemmas

The appendix supplies technical lemmas used in the proofs, including a concentration inequality and a lower bound on the minimum eigenvalue of an observation-history correlation matrix.

Appendix D. Technical lemmas

  • Lemma 15 states a Hoeffding inequality for independent variables with means and sub-Gaussian parameters.The stated result applies for h ≥ 0.Source: Appendix D · p. 26
  • Lemma 16 assumes contexts are generated i.i.d. from a sub-Gaussian random vector with a full-rank second-moment matrix.It also bounds the random vector’s variance relative to the matrix’s minimum eigenvalue.Source: Appendix D · p. 26
  • Under the technical-lemma assumptions, the appendix gives a lower bound on the minimum eigenvalue of an observation-history correlation matrix.The bound concerns the correlation matrix of history H.Source: Appendix D · p. 26
Loading 2009.02463v1…