- 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 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 , and provide lower bounds.
Critical strengths
-
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.
-
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 , and complementary lower bounds. These results provide a fairly deep characterization of the problem.
Critical weaknesses
-
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.
-
Limited practical applicability. The proposed algorithms have high computational complexity (reported as ), 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.
-
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
-
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?
-
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
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 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 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.
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 M and D=∑m(Lm+1)Km quantifying its bound. Taking M=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)), preserving their regret guarantees. The stated O(K2T5) 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) records per history at round t. 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)). Extrema update in 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)) 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) 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.