acceptodds
Under review as a conference paper at ICLR 2027

Nonstationary Multi-Armed Bandits with Heterogeneous Arm Classes

Abstract

In real-world applications such as online recommendation, nonstationarity is rarely uniform: trending items fluctuate rapidly, while the broader catalog remains stable. Existing nonstationary bandit algorithms ignore this structure, incurring regret that scales with the global product of total arms and total switches. To address this, we formulate nonstationary multi-armed bandits with heterogeneous arm classes, where arms are partitioned into known classes of sizes with individual change budgets . We design an adaptive algorithm requiring no prior knowledge of these budgets that achieves expected dynamic regret of order , tightly pairing each class's volatility with only its own size. Finally, we establish complementary lower bounds showing that this rate is optimal up to logarithmic factors for fixed , and that the class-search overhead is fundamentally unavoidable in general.

Primary area:
learning theory
Keywords:
Non stationary Bandits, Regret, Dynamic Regret, Online Learning

Reviews

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

This paper studies nonstationary multi-armed bandits with heterogeneous arm classes, where different classes have different sizes and change budgets. The authors introduce a class-dependent difficulty measure D=∑m(Lm+1)KmD=\sum_m (L_m+1)K_m and propose EBF-H, which combines class-isolated change detection with exponential backfilling to avoid unnecessary global resets. They prove an expected dynamic regret bound of O~(MTD)\widetilde{O}(\sqrt{MTD}), and provide lower bounds.

Critical strengths
  1. Meaningful problem formulation. The paper considers a natural limitation of standard nonstationary bandit models: nonstationarity may be highly heterogeneous across different subsets of arms. Modeling class-specific change budgets and pairing each class’s volatility with its own size provides a sensible refinement of the usual global switching-budget formulation.

  2. Complete and technically substantial theoretical results. The paper develops a coherent theoretical framework, including the EBF-H algorithm, an adaptive extension that does not require prior knowledge of the change budgets, an upper bound of O~(MTD)\widetilde{O}(\sqrt{MTD}), and complementary lower bounds. These results provide a fairly deep characterization of the problem.

Critical weaknesses
  1. The practical motivation of the problem is not yet sufficiently justified. While heterogeneous nonstationarity across different arm groups is intuitively plausible, the paper does not provide empirical evidence or concrete real-world data demonstrating that this structure is prevalent or that the proposed class-dependent model is necessary in practice. Moreover, the method assumes that the arm partition into classes is known in advance, which may be a strong assumption in realistic applications.

  2. Limited practical applicability. The proposed algorithms have high computational complexity (reported as O(K2T5)O(K^2T^5)), which makes direct deployment in large-scale online applications difficult. In addition, the paper contains no numerical experiments, even on synthetic instances, to illustrate the finite-sample behavior or the practical advantage of exploiting heterogeneous change budgets. These limitations weaken the practical impact, although they are less critical for a primarily theoretical contribution.

  3. The novelty could be positioned more clearly. The idea of exploiting localized nonstationarity and avoiding unnecessary global resets is natural, and the paper would benefit from a sharper explanation of what is fundamentally new relative to existing structured or nonstationary bandit approaches. In my view, the strongest novelty lies in the class-dependent complexity measure, the corresponding regret guarantees, and the complementary lower bounds, rather than the localized-reset intuition itself. This positioning issue is not fatal, but clearer differentiation would strengthen the contribution.

Questions for authors
  1. Can the authors provide some evidence showing that heterogeneous class-specific nonstationarity is an important practical phenomenon, and that the assumed class structure is realistically available?

  2. Given the high computational complexity of the proposed algorithms, can the authors discuss practical approximations or modifications that could make the framework more computationally feasible, even if they sacrifice some theoretical optimality?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 49Ca

We thank the reviewer for the thoughtful reading and positive assessment of our work. We address the raised concerns below.

1. Motivation and the supplied partition.

Wang et al. [1] study how attention to online content evolves. For Digg news, Figure 2B reports different attention-decay patterns across categories: among those examined, attention to politics decays fastest and to health persists longest. This motivates allowing temporal dynamics to differ across identifiable content groups.

MIND [2] addresses whether group membership can be available before learning. It provides editor-assigned news categories and clicks/non-clicks on displayed articles. In a stylized, noncontextual problem with a fixed catalogue, articles are arms, categories define classes, and a click is a binary reward. Thus, existing metadata can supply the partition without learning group membership from rewards.

These references have complementary roles: [1] supports heterogeneous temporal behavior; [2] demonstrates available grouping information. Together, they motivate our abstraction of heterogeneous temporal dynamics across arm classes; We will add them as motivating examples to the introduction.

We emphasize AEBF-H takes only the horizon and partition as inputs; it does not require the class change budgets or advance identification of which classes will change frequently. Class members may have different means and change at different times: the budget counts rounds when any member changes. No minimum change magnitude or spacing is required.

Within the model, the guarantee holds for any fixed partition, with MM and D=∑m(Lm+1)KmD=\sum_m(L_m+1)K_m quantifying its bound. Taking M=1M=1 recovers the classical global switching guarantee without knowing the change budget (Theorem D.1).

2. Computational feasibility and practical modifications.

Both of our algorithms admit exact total runtime O((T2+KT)log⁡(2T))O((T^2+KT)\log(2T)), preserving their regret guarantees. The stated O(K2T5)O(K^2T^5) cost comes from naive interval-pair enumeration chosen for simplicity; it is not intrinsic. A more sohisticated implementation achived the desired runtime is stated next.

For each arm and observation count, retain the minimum/maximum empirical means over consecutive observation blocks in its current phase. Since radii depend only on counts, these extrema optimize both one- and three-radius target/blocker bounds, preserving certificate feasibility and maximal gaps.

There are O(t)O(t) records per history at round tt. Sorting three-radius lower bounds and storing the best two one-radius lower bounds from distinct arms in each suffix answers all certificate queries in O(tlog⁡(2t))O(t\log(2t)). Extrema update in O(t)O(t) after an observation and also give exact change detection. AEBF-H uses both histories and FIFO service-deadline queues; monitoring and recency bookkeeping costs O(KTlog⁡(2T))O(KT\log(2T)) in total, amortized over obligation updates. With compatible fixed tie-breaking, sampling decisions and regret guarantees are unchanged. We will include this implementation argument.

Further practical options include geometrically spaced observation-block lengths, testing at checkpoints, or bounded recent histories. These reduce statistics, test frequency, or memory, but change the tests or detection delays and would require additional analysis.

We note our work is theoretical and, as in AdSwitch (Auer et al., 2019), does not include empirical heuristics or experiments.

3. Novelty and positioning.

We thank the reviewer for recognizing the value of our class-dependent complexity, regret guarantees, and complementary lower bounds. We agree that these are central aspects of our novelty. We will emphasize them more clearly, together with the substantial algorithmic and analytical work required to obtain them: cross-class blocking certificates, multiscale recency, and the adaptive history separation and auxiliary coupling. These mechanisms handle comparisons and monitoring across asynchronous histories, enabling the refined O~(MTD)\widetilde O(\sqrt{MTD}) guarantee, including without known class budgets in AEBF-H.

We will foreground this combined contribution, explicitly credit the monitoring ideas inherited from AdSwitch and earlier local-restart methods such as CUSUM-UCB and local GLR-klUCB, and correct the blanket global-reset statement.

We thank the reviewer again for the constructive feedback and welcome further discussion. If these clarifications address your concerns, we would be grateful if you would consider revising your score upward.

[1] Wang et al. (2016). The Collective Direction of Attention Diffusion. Scientific Reports.

[2] Wu et al. (2020). MIND: A Large-scale Dataset for News Recommendation. ACL.

I appreciate the additional references provided in the rebuttal, but I remain unconvinced that the specific problem studied in this paper is sufficiently prevalent and practically important. The cited examples demonstrate heterogeneous attention patterns and the availability of class labels, but do not directly establish that real-world bandit rewards exhibit distinct class-specific switching budgets. Therefore, the practical significance of the proposed problem formulation remains unclear to me.

We thank the reviewer for clarifying the concern. We respectfully disagree that the significance of a theoretical contribution depends on exhibiting a dataset that exactly follows a class-specific switching-budget model.

As with standard switching, variation, corruption, or path-length budgets, the quantities LmL_m are ex-post complexity measures used to characterize an environment; they are not assumed to appear explicitly in a dataset. Moreover, AEBF-H does not know these budgets or which classes are volatile. The relevant question is whether the proposed structure is natural and leads to a genuinely different learning problem.

Our model is a natural refinement between a single global change process and completely unrelated arm-wise nonstationarity. In many applications, arms have meaningful metadata-defined groups—for example, news topics, product categories, advertising campaigns, or geographic markets—and changes may be localized to one group while observations from others remain informative. The references in our rebuttal support the plausibility of heterogeneous temporal behavior and the availability of such group information.

Our paper then proves that exploiting this structure is mathematically consequential. Existing global-switching guarantees couple the global number of changes with the full arm set, whereas our complexity D=∑m(Lm+1)KmD=\sum_m(L_m+1)K_m pairs each class’s nonstationarity only with its own size. To the best of our knowledge, this is the first algorithmic and theoretical study of this class-dependent switching model. We formulate the problem, provide algorithms for both known and unknown class budgets, prove a class-dependent upper bound, and establish complementary lower bounds identifying the costs of within-class relearning and cross-class search.

We do not claim that this work gives the final minimax characterization or the most efficient possible algorithm for every class configuration. Its contribution is to identify and formalize a meaningful gap in the existing theory, provide the first upper and lower bounds for the resulting problem, and open a new direction for sharper rates and more efficient algorithms.

Accordingly, we do not believe that the absence of a dataset exactly exposing class-specific switching budgets should outweigh the paper’s theoretical novelty and depth. We would appreciate it if the reviewer reconsidered the reduced score in light of the paper’s intended theoretical contribution.

Reviewer_BWv1OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies piecewise-stationary multi-armed bandits in which the KK arms are partitioned into MM known classes, each with its own budget LmL_m on the number of distribution changes. The authors argue that the standard global switching budget overstates the difficulty when changes are concentrated in a few small classes, and measure difficulty instead by D=∑m=1M(Lm+1)KmD = \sum_{m=1}^{M} (L_m + 1) K_m. The proposed algorithm, EBF-H, combines (i) class-isolated change detection, so that a detected shift resets only the affected class; (ii) a good/bad arm classification based on confidence-interval certificates that may span different classes; (iii) an "exponential backfill" schedule that randomly re-examines bad arms at dyadic gap scales, with refresh probabilities calibrated to each class's volatility; and (iv) a two-stage sampling rule that draws a class uniformly and then an arm by a multi-scale recency rule. The main result is an expected dynamic regret bound of O~(MTD)\tilde{O}(\sqrt{MTD}), and an adaptive variant, AEBF-H, attains the same rate without knowing {Lm}m=1M\lbrace L_m\rbrace _{m=1}^{M}. The paper also proves an Ω(TD)\Omega(\sqrt{TD}) lower bound for every class configuration whenever T≥2DT \ge 2D, so the upper bound is tight up to logarithmic factors for fixed MM, and an Ω(MKT)\Omega(\sqrt{MKT}) lower bound on a balanced family with Km=K/MK_m = K/M and Lm=2L_m = 2 whenever T≥6MKT \ge 6MK, which the authors interpret as showing that the M\sqrt{M} overhead is unavoidable in general. The paper is purely theoretical.

Critical strengths
  1. A well-motivated refinement of the switching budget. The class-structured model is natural, recovers the classical setting at M=1M = 1, and the direct-sum lower bound Ω(TD)\Omega(\sqrt{TD}) (Theorem 5.1) convincingly establishes DD as the right per-class quantity: samples collected in one class cannot amortize the cost of changes in another.
  2. Nontrivial handling of asynchronous, class-local resets. Once classes reset at different times, a bad arm may be certified against an arm whose phase started elsewhere, so the single-episode logic of global-reset methods no longer applies. The cross-class certificates together with the blocking-arm property (Proposition 4.3), the decomposition over maximal static intervals, and the multi-scale recency rule that ties sampling to MSI counts (Lemma B.9) resolve this cleanly.
  3. A careful budget-free extension. AEBF-H decouples the launch randomness from the classification trajectory through separate classification/detection histories and an auxiliary-execution argument, a rigorous treatment of the feedback loop created by data-dependent monitoring rates.
Critical weaknesses
  1. Relationship to AdSwitch. The monitoring mechanism shares several key ingredients with AdSwitch (Auer et al., 2019): randomized multi-scale sampling obligations for bad arms, launch probabilities proportional to 2−jL/(KT)2^{-j}\sqrt{L/(KT)} with on the order of 22jlog⁡T2^{2j}\log T samples per check, an interval-based change test, and, in AEBF-H, the detected-change count in place of the unknown budget. However, Auer et al. (2019) is currently cited only for the problem setup and the lower bounds. A direct comparison with AdSwitch would help clarify which components are inherited and which are new (e.g., class-local resets, cross-class certificates, and the class/scale sampling rule). In addition, local-restart detectors such as CUSUM-UCB (Liu et al., 2018) and GLR-klUCB (Besson et al., 2022) seem relevant to the claim in Section 1 that existing methods reset globally.

  2. When the bound improves on global-budget rates. Since the guarantee is O~(MTD)\tilde{O}(\sqrt{MTD}), improving on O~((L+1)KT)\tilde{O}(\sqrt{(L+1)KT}) requires MD<(L+1)KMD < (L+1)K, not only D<(L+1)KD < (L+1)K as suggested in the introduction. The two conditions can differ substantially: when all classes are stationary, the bound becomes O~(MKT)\tilde{O}(\sqrt{MKT}) rather than O~(KT)\tilde{O}(\sqrt{KT}). Making this condition explicit, and perhaps noting that merging classes recovers the global rate when budgets are known, would make the benefit easier to assess.

  3. Lack of empirical evidence. The paper contains no experiments, and the O(K2T5)O(K^2T^5) running time makes the exact algorithm difficult to apply. Even a small simulation would help show whether class-local resets deliver the expected benefit in practice.

Questions for authors
  1. Where exactly does the M\sqrt{M} factor enter, and is it necessary when only a few classes are volatile? In the analysis, M\sqrt{M} arises through two mechanisms: (a) the dominance-gap charge of Term (i) (Lemma B.11) and the pre-refresh waiting cost of Term (iii) (Lemma B.13, Region 1) scale as ∑mT(Lm+1)Km\sum_m \sqrt{T(L_m+1)K_m}, which Cauchy–Schwarz bounds by MTD\sqrt{MTD} but which can be much smaller when DD is concentrated in a few classes; and (b) the eligible-arm confidence sum (Lemma B.9), where the uniform class draw gives p=1/(M(Jmax⁡+1))p = 1/(M(J_{\max}+1)) and hence a M\sqrt{M} factor regardless of how DD is distributed (the class thresholds ζm\zeta_m in Lemma B.13 also scale with MM). When only a few classes are volatile, could the dependence on MM be reduced, for instance by treating all classes without detected resets as a single class, which would remove the contribution of stationary classes to both (a) and (b), or by sampling classes non-uniformly?
  2. Can the algorithm be made never worse than AdSwitch, i.e., attain O~(min⁡{MTD,(L+1)KT})\tilde{O}(\min\lbrace \sqrt{MTD}, \sqrt{(L+1)KT}\rbrace ), and can AEBF-H achieve this without knowledge of the budgets?
2 comments
AuthorsOpenReview ↗

Response to Reviewer BWv1

We thank the reviewer for the thoughtful feedback and positive assessment. We hope the next answers will address your questions.

1. Few volatile classes and the M\sqrt M factor.

We note that known-stationary classes do not force a growing class-search penalty. If VV classes can change, pool the remaining classes into one, giving M′M' classes. This preserves D=∑m(Lm+1)KmD=\sum_m(L_m+1)K_m and gives M′≤V+1M' \le V+1 , hence O~(M′TD)\widetilde O(\sqrt{M'TD}) by Theorem 3.1. Theorem D.1 gives the same improvement for AEBF-H without knowing the remaining budgets. If all classes are stationary, this recovers O~(KT)\widetilde O(\sqrt{KT}).

Pooling addresses both sources identified by the reviewer: stationary terms in ∑mT(Lm+1)Km\sum_m\sqrt{T(L_m+1)K_m} become one term (Lemmas B.11/B.13), and M′M' replaces MM in Lemma B.9's sampling probability and the detection thresholds. Thus the improvement is not limited to Cauchy–Schwarz.

Stationary identities must be known: no detected reset does not rule out an undetected change. This extra step affects only the analysis, as described above.

2. Can we be no worse than AdSwitch?

With valid bounds, choosing the partition gives a leading guarantee no worse than the corresponding global-budget rate. Given class budgets and a global bound Lˉ\bar L, retain the partition if MD≤(Lˉ+1)KMD\le(\bar L+1)K; otherwise merge all arms. Theorem 3.1 gives O~(min⁡{MTD,(Lˉ+1)KT})\widetilde O(\min\{\sqrt{MTD},\sqrt{(\bar L+1)KT}\}), with no selection regret.

Writing LL for the actual global change count, improvement requires MD<(L+1)KMD<(L+1)K. Synchronized changes give D=(L+1)KD=(L+1)K, explaining the benefit of merging. Individual budgets imply Lˉ=min⁡{T−1,∑mLm}\bar L=\min\{T-1,\sum_mL_m\}, which may exceed LL; the requested minimum in actual LL follows when Lˉ=L\bar L=L.

The global rate is also available without budgets: AEBF-H with one merged class gives O~((L+1)KT)\widetilde O(\sqrt{(L+1)KT}) without knowing LL (Theorem D.1). Automatic budget-free selection of the better localized/global rate is not established by our current results.

3. Technical contribution and prior work.

Our central challenge is preserving class-local histories while proving the refined DD-dependent guarantee. Redesigning classification, sampling and adaptive monitoring for asynchronous phases, together with their analysis, is our technical core.

We inherit AdSwitch's idea of confidence-based good/bad classification, interval testing, dyadic checks with 2−j2^{-j} launch scaling and O~(22j)\widetilde O(2^{2j}) samples, detected-change adaptation and recency scheduling. Its shared-interval count argument (Section 4.3, used in Section 4.6.1) requires continuous eligibility. Another class's reset can invalidate a certificate, so current goodness no longer supplies this premise.

Our mechanisms resolve these difficulties:

  • Phase-valid cross-class certificates with three-radius margins and maximal one-radius gaps, coordinated with the reset test, yield a currently good selected blocker (Proposition 4.3).
  • Randomized class/scale selection and 2j2^j-pull recency enable confidence charging to class-specific maximal static intervals without continuous eligibility (Lemma B.9).
  • Separate histories, monitoring candidates independent of obligations, and the auxiliary coupling establish the launch-seed independence needed for waiting times (Lemma D.12).

We will credit CUSUM-UCB (Liu et al., 2018) and local GLR-klUCB (Besson et al., 2022) and correct the blanket global-reset claim. Their analyses impose change-spacing conditions; our guarantee requires neither minimum change magnitude nor spacing.

4. Computation and empirical scope.

Our contribution is theoretical; as in AdSwitch (Auer et al., 2019), we do not include experiments. The O(K2T5)O(K^2T^5) implementation enumerates interval pairs for simplicity; its cost is not intrinsic. Both of our algorithms admit runtime O((T2+KT)log⁡(2T))O((T^2+KT)\log(2T)) for the next more sophisticated implementation.

For each arm and observation count, retain minimum/maximum empirical means over consecutive observation blocks in its current phase. Since radii depend only on counts, these extrema optimize target/blocker bounds at multipliers 1 and 3, preserving feasibility and maximal certificate gaps. There are O(t)O(t) records per history. Sorting three-radius lower bounds and storing the best two one-radius lower bounds from distinct arms in each suffix answers all certificate queries in O(tlog⁡(2t))O(t\log(2t)).

Extrema update in O(t)O(t) per observation and also give exact change detection. AEBF-H applies this to both histories and uses FIFO service-deadline queues. Total monitoring and recency bookkeeping is O(KTlog⁡(2T))O(KT\log(2T)), amortized over obligation insertions/removals. With compatible fixed tie-breaking, sampling decisions and regret guarantees are unchanged. We will include the implementation argument.

We thank the reviewer again and welcome further discussion. If these clarifications address your concerns, we would be grateful if you would consider revising your score upward.

Thank you for the clear and detailed response. The pooling argument answers my first question, and I appreciate the clarification that it requires knowing which classes are stationary. The answer to my second question is also helpful: the minimum of the two rates is attainable with known budgets, while budget-free selection remains open. The explicit list of components inherited from AdSwitch and the corrected discussion of local-restart detectors address my main concern about attribution. I would encourage including these points in the revision, together with the condition MD<(L+1)KMD < (L+1)K and the O((T2+KT)log⁡T)O((T^2+KT)\log T) implementation argument. I maintain my positive assessment.

Reviewer_kXcKOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies piecewise-stationary stochastic multi-armed bandits with a known partition of the arms into classes, where class mm has KmK_m arms and a change budget LmL_m. It introduces the complexity measure D=∑m(Lm+1)KmD=\sum_m(L_m+1)K_m to capture the localization of nonstationarity. The proposed EBF-H algorithm combines class-specific resets, confidence-based arm classification, and multiscale monitoring of previously suboptimal arms. It achieves expected dynamic regret O~(MTD)\widetilde O(\sqrt{MTD}) when the class budgets are known. The paper also establishes a general Ω(TD)\Omega(\sqrt{TD}) lower bound and an Ω(MKT)\Omega(\sqrt{MKT}) lower bound for balanced classes with two changes per class.

Critical strengths
  1. The paper addresses an important and well-motivated problem in nonstationary multi-armed bandits.
  2. The theoretical analysis is thorough and well written, making the main ideas and theoretical results easy to follow.
Critical weaknesses

The distinction between this study and the most relevant prior work is not sufficiently discussed, which influences the assessment of its contribution. For instance, the ADSWITCH algorithm proposed by Auer et al. (2019) already incorporates the classification of arms into “good” and “bad,” employs multi-scale sampling obligations, and features a mechanism that adjusts the monitoring rate based on the number of detected changes; meanwhile, the GLR-klUCB algorithm by Besson et al. (2022) also explores the concept of local restarts. Consequently, merely highlighting local restarts and the re-monitoring of bad arms is insufficient to clearly demonstrate the methodological innovations of this paper.

Questions for authors
  1. Please clarify the novelty of the proposed approach through a more detailed comparison with existing work. In particular, which mechanisms are retained from ADSWITCH? At which specific step does the original proof argument break down when moving from global episodes to class-specific phases? Moreover, what distinct challenges are addressed by the blocking-arm structure, multi-scale recency rule, and two-history design, respectively, and why can these challenges not be handled directly by existing methods?
  2. Under what conditions does incorporating a class partition lead to improved performance compared with approaches that do not exploit such a partition? The granularity of the partition may also affect algorithmic performance. In particular, when many classes undergo changes simultaneously, the total number of global switches may remain relatively small, in which case the additional factor of MM introduced by the class partition could offset or even outweigh the benefits of localization. Please discuss this trade-off.
  3. Theorem 5.2 establishes the necessity of a M\sqrt{M} dependence for a specific balanced family, while Section 6 acknowledges that the general imbalanced case remains open. Could the authors clarify the parameter regimes in which the proposed regret bound is guaranteed to improve upon the global switching bound? Conversely, under what conditions might the upper bound established in the paper be loose? For instance, when all Lm=0L_m=0, the proposed bound becomes O~(MKT)\widetilde{O}(\sqrt{MKT}), whereas ignoring the partition yields O~(KT)\widetilde{O}(\sqrt{KT}). Can a more refined analysis recover the latter rate in this setting, or is the current bound inherently loose in this case?
2 comments
AuthorsOpenReview ↗

Response to Reviewer kXcK

We thank the reviewer for the thoughtful feedback and positive assessment. Below we adress the raised questions.

1. Novelty and relationship to AdSwitch

Our core contribution is the redesign and analysis needed to obtain O~(MTD)\widetilde O(\sqrt{MTD}) with class-specific restarts. Preserving other classes' observations when one class resets enables accounting through D=∑m(Lm+1)KmD=\sum_m(L_m+1)K_m, but requires controlling comparisons and monitoring across asynchronous histories.

AdSwitch's sample-count comparison (Auer et al., 2019, Sections 4.3 and 4.6.1) requires eligibility throughout a shared interval. Another class's reset can invalidate an arm's certificate and make it good without changing its own phase or stationary interval. Current good status therefore does not imply continuous eligibility, so this argument does not transfer directly. Global accounting would restore K(Lglobal+1)K(L_{\mathrm{global}}+1).

We inherit AdSwitch's idea of confidence-based good/bad classification, interval-based detection, dyadic monitoring with 2−j2^{-j} launch scaling and O~(22j)\widetilde O(2^{2j}) samples per check, detected-change adaptation, and recency-based scheduling. Beyond class-calibrated monitoring, our core mechanisms are:

  • Certificate construction. Equation (2) compares intervals valid for each arm's own phase, using three-radius separation and maximizing a one-radius gap. Coordinated with the reset test, this yields Proposition 4.3: the selected blocker is currently classified as good. This supplies the representatives for the regret decomposition in Equation (4).

  • Multiscale recency and confidence accounting. EBF-H randomizes over eligible classes and scales, then selects by the earliest 2j2^j-th most recent pull within the phase. Lemma B.9 constructs a comparable-confidence arm selected with probability at least 1/[M(Jmax⁡+1)]1/[M(J_{\max}+1)], avoiding continuous-eligibility requirements. On the concentration event, uncertainty is charged to class-specific maximal static intervals, with at most ∑m(2Lm+1)Km≤2D\sum_m(2L_m+1)K_m\le2D arm–interval pairs.

  • Adaptive histories and independence. AEBF-H records additional monitoring samples only for detection, selects monitoring candidates independently of obligations, and discards fallback observations. Lemma D.12 handles the remaining dependence through resets: an auxiliary execution suppresses the target class's resets and freezes a hard-round sequence independent of the relevant launch seeds, conditional on the other randomness. This yields the waiting-time argument; replacing global reset counts with local counts alone does not.

Local restarts also appear in CUSUM-UCB (Liu et al., 2018) and GLR-klUCB (Besson et al., 2022). CUSUM-UCB assumes a known detectability threshold and change separation; GLR-klUCB needs no change magnitudes as input, but its local-restart guarantees impose magnitude-dependent spacing. Our guarantee requires neither minimum change magnitude nor spacing, and AEBF-H needs no class budgets. We will clarify this comparison and correct the introduction's statement about global resets.

2. When does the partition help?

Thank you for highlighting this trade-off. The leading-term improvement condition is MD<(Lglobal+1)KMD<(L_{\mathrm{global}}+1)K, where LglobalL_{\mathrm{global}} counts distinct global change rounds.

For M=2M=2, (K1,L1)=(10,100)(K_1,L_1)=(10,100) and (K2,L2)=(990,0)(K_2,L_2)=(990,0), with 100 realized changes, D=2000D=2000 and MD=4000MD=4000, versus (Lglobal+1)K=101000(L_{\mathrm{global}}+1)K=101000. Conversely, synchronized changes with Lm=LL_m=L give D=(L+1)KD=(L+1)K and an extra M\sqrt M in our bound. Thus, reducing DD alone does not guarantee improvement.

3. Stationarity and optimality

We emphasize that known stationary classes need not be counted separately. Merge all zero-budget classes into one. This preserves DD and gives Meff=V+1{a zero-budget class exists}M_{\mathrm{eff}}=V+\mathbf{1}\{\text{a zero-budget class exists}\}, where VV counts positive-budget classes. Theorem 3.1 then gives O~(MeffTD)\widetilde O(\sqrt{M_{\mathrm{eff}}TD}). When all budgets are zero, Meff=1M_{\mathrm{eff}}=1 and D=KD=K, recovering O~(KT)\widetilde O(\sqrt{KT}). Thus, the loose unmerged stationary bound is resolved by preprocessing, without a new analysis. Automatic pooling when stationarity is unknown is a separate question.

Our lower bounds establish complementary worst-case necessities:

  • Learning: Theorem 5.1 gives Ω(TD)\Omega(\sqrt{TD}) for arbitrary configurations when T≥2DT\ge2D, matching our bound up to logarithms for fixed MM.
  • Class search: Theorem 5.2 gives Ω(MKT)\Omega(\sqrt{MKT}) for Km=K/MK_m=K/M, Lm=2L_m=2, when T≥6MKT\ge6MK. Here D=3KD=3K, so it matches Ω(MTD)\Omega(\sqrt{MTD}) even as MM grows.

Lemma C.2 also accommodates unequal class sizes through designated arms, under its budget and horizon conditions. A full minimax characterization of imbalanced configurations remains open.

We thank the reviewer again and welcome further discussion. If these clarifications address your concerns, we would be grateful if you would consider revising your score upward.

Thank you for the detailed response. One clarification remains regarding stationary-class pooling. My understanding is that this requires prior knowledge of which classes are stationary and modifies the input partition before running the algorithm; it does not establish automatic adaptation to unknown stationary classes under the original partition.

Overall, the response strengthens my assessment of the theoretical contribution. I maintain my rating.

Reviewer_GM5tOpenReview ↗
Rating
3
Confidence
1
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies nonstationary multi armed bandits in which arms are partitioned into known classes with different change budgets. It proposes EBF-H, which combines class specific change detection with exponential backfill to preserve observations from stable classes while monitoring potentially improved arms. The paper proves an expected dynamic regret bound of O~(MTD)\widetilde{O}(\sqrt{MTD}), extends the result to unknown change budgets, and establishes complementary lower bounds showing near optimality for fixed MM and the necessity of class search overhead in balanced settings.

Critical strengths
  1. Meaningful structural refinement of nonstationary bandits. The class specific formulation pairs each group’s volatility with only its own size, yielding an instance complexity that can be substantially smaller than the standard global change measure. This captures an important form of localized nonstationarity while recovering the classical switching bandit setting as a special case.

  2. Strong theoretical characterization. The paper provides algorithms for both known and unknown class change budgets, proves the same O~(MTD)\widetilde{O}(\sqrt{MTD}) dynamic regret rate for both, and establishes complementary lower bounds for within class learning and cross class search. This combination makes the contribution substantially more complete than an isolated upper bound.

Critical weaknesses
  1. The general minimax characterization remains incomplete. For arbitrary class configurations, the upper bound is O~(MTD)\widetilde{O}(\sqrt{MTD}), whereas the general lower bound is only Ω(TD)\Omega(\sqrt{TD}). The additional M\sqrt{M} factor is shown necessary only for a balanced family with two changes per class, leaving a potentially substantial gap when MM grows or the classes are highly imbalanced.

  2. The proposed algorithms are computationally impractical. Exact implementation requires O(K2T5)O(K^2T^5) time because it searches over all interval comparisons, and the paper provides neither an efficient approximation nor empirical evidence that the mechanism remains effective when simplified. This substantially limits the connection between the theoretical contribution and the motivating large scale applications.

Questions for authors
  1. What is the strongest minimax conclusion that can be drawn for general imbalanced class configurations? In particular, is there evidence that the M\sqrt{M} gap between the general upper and lower bounds is unavoidable beyond the balanced two change construction?

  2. Is the stated O(K2T5)O(K^2T^5) runtime intrinsic to EBF-H, or can the interval tests and arm classification be implemented more efficiently without changing the algorithm or regret guarantee? A substantially lower implementation cost would materially affect the paper’s practical significance.

1 comment
AuthorsOpenReview ↗

Response to Reviewer GM5t

We thank the reviewer for the careful reading and positive assessment of our paper. Below, we address the questions and concerns raised.

1. Scope of the minimax result and imbalanced configurations.

We emphasize that the worst-case necessity of the leading factors appearing in our upper bound is established by our two lower bounds:

  • The learning cost TD\sqrt{TD}. Theorem 5.1 proves an Ω(TD)\Omega(\sqrt{TD}) lower bound for arbitrary class sizes and change budgets, provided T≥2DT\ge2D. Together with Theorem 3.1, this establishes optimality up to logarithmic factors when the number of classes is fixed.
  • The additional class-search factor M\sqrt{M}. Theorem 5.2 proves an Ω(MKT)\Omega(\sqrt{MKT}) lower bound for the family Km=K/MK_m=K/M, Lm=2L_m=2, provided T≥6MKT\ge6MK. Since D=3KD=3K on this family, the lower bound is Ω(MTD)\Omega(\sqrt{MTD}). Thus, the learning and class-search costs appear jointly in instances matching our upper bound even when MM grows.

The underlying class-search construction also accommodates unequal class sizes. Lemma C.2 is formulated using designated arms within each participating class. Specifically, let SS be any subset of nn classes satisfying Lm≥2L_m\ge2 for every m∈Sm\in S, and set k=min⁡m∈SKmk=\min_{m\in S}K_m. Applying the construction to kk designated arms in each selected class, while keeping all remaining arms at the stationary baseline, gives

E[RegretT]≥1512nkT,nk≥2,T≥6n2k.\mathbb E[\mathrm{Regret}_T]\ge\frac{1}{512}n\sqrt{kT},\qquad nk\ge2,\quad T\ge6n^2k.

This embeds class-search hardness within an otherwise arbitrarily imbalanced partition; the classes themselves need not have equal sizes. We will state this consequence explicitly in the paper. Further characterizing how the learning and class-search costs interact across more general imbalanced configurations is an interesting direction for future work.

2. The stated runtime is not intrinsic.

The stated O(K2T5)O(K^2T^5) runtime corresponds to a naive implementation that exhaustively enumerates pairs of intervals. We presented this implementation for simplicity; its computational cost is not intrinsic to the algorithms. Both EBF-H and AEBF-H admit a more efficient exact implementation with total running time O((T2+KT)log⁡(2T))O\big((T^2+KT)\log(2T)\big), while preserving their sampling decisions and regret guarantees. We describe the implementation below.

The key observation is that the confidence radius depends only on the observation count. For each arm and each count nn, it is therefore sufficient to retain the minimum and maximum empirical means over consecutive blocks of nn observations in its current phase. For the target arm in a certificate, the minimum-mean block minimizes both the one-radius and three-radius upper bounds. For the blocking arm, the maximum-mean block maximizes both corresponding lower bounds. These extrema therefore preserve the exact certificate feasibility test and the maximum certificate gap.

At round tt, there are O(t)O(t) such records per history, since the retained observation counts sum to at most t−1t-1. Sorting source records by their three-radius lower bounds and storing the best two one-radius lower bounds from distinct arms in each suffix allows all certificate queries to be answered in O(tlog⁡(2t))O(t\log(2t)) time. Each query selects the suffix satisfying its strict certificate threshold. Keeping two distinct arms ensures that the blocker can be chosen to differ from the target.

Each new observation creates one new observation block ending at that observation for every possible block length. Using prefix sums, the extrema can therefore be updated in O(t)O(t) time. Change detection uses the same extrema.

The adaptive algorithm applies this reduction to both of its histories and maintains monitoring obligations in FIFO service-deadline queues. Each obligation is inserted and removed at most once, so its bookkeeping cost is amortized. Together, monitoring, launch, and recency bookkeeping require O(KTlog⁡(2T))O(KT\log(2T)) total time. Combining this with the interval-processing costs gives the stated O((T2+KT)log⁡(2T))O\big((T^2+KT)\log(2T)\big) runtime.

These operations preserve the tests, maximum dominance gaps, and a compatible fixed tie-breaking rule, so no change to the regret analysis is required. We will include the implementation details and update the complexity statements for both algorithms. Further reducing the quadratic dependence on the horizon is an interesting direction for improving practical scalability.

We thank the reviewer again for the constructive feedback and positive assessment of our work, and we welcome further discussion. If these clarifications address your concerns, we would appreciate your considering an upward revision of your score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.