Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits
Authors: Shaoang Li
Jian Li
Venue: NeurIPS 2025 poster ()
Keywords: Non-stationary bandits
constrained feedback
query budget
query-reward tradeoff
Primary area: theory
TL;DR: We propose the first prior-free algorithm that achieves near-optimal dynamic regret for non-stationary multi-armed bandits under constrained feedback.

Abstract: Non-stationary multi-armed bandits (nsMAB) enable agents to adapt to changing environments by incorporating mechanisms to detect and respond to shifts in reward distributions, making them well-suited for dynamic settings. However, existing approaches typically assume that reward feedback is available at every round—an assumption that overlooks many real-world scenarios where feedback is limited. In this paper, we take a significant step forward by introducing a new model of *constrained feedback in non-stationary multi-armed bandits* (ConFee-nsMAB), where the availability of reward feedback is restricted. We propose the first prior-free algorithm—that is, one that does not require prior knowledge of the degree of non-stationarity—that achieves near-optimal dynamic regret in this setting. Specifically, our algorithm attains a dynamic regret of $\tilde {\mathcal{O}}({K^{1/3} V_T^{1/3} T }/{ B^{1/3}})$, where $T$ is the number of rounds, $K$ is the number of arms, $B$ is the query budget, and $V_T$ is the variation budget capturing the degree of non-stationarity.

Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits
Shaoang Li
Jian Li
Stony Brook University shaoang 1i@sttoybrooo..coom edu
Stony Brook University jian. 30stonybrook edu
Abstract
Non-stationary multi-armed bandits (NSMAB) enable agents to adapt to changing environments by incorporating mechanisms to detect and respond to shifts in reward distributions, making them well-suited for dynamic settings. However, existing approaches typically assume that reward feedback is available at every round an assumption that overlooks many real-world scenarios where feedback is limited. this paper, we take a significant step forward by introducing a new model constrained feedback in non-statin non-stationary multi-armet bandits (CONFEE-NSMA) where the availability of reward feedback restricted. We propose the first prior- free algorithm-that is, one that does not require prior knowledge of the degree non-stationarity-tho achieves near-optimal dynamic regret in this setting. Specifically, algorithm attains dynamic regret of O / /33/ where is the number of rounds, K is the number of arms, B is the query budget, and V is the variation budget capturing the degree of non-stationarity.
Introduction
The multi-armed bandits (MAB) problem 22 is a fundamental framework for decision-making maximize cumulative rewards over
under uncertainty, where an agent selects from set of time horizon, balancing exploration (learning about arms) and exploitation (leveraging known rewards). Most state-of-the-art MAB algorithms, including Upper Confidence Bound (UCB)-type methods [ and Thompson Sampling bbaeed approaches [34], assume stationary settings in which reward distributions remain fixed over time. However, many real-world applications- such as dynamic pricing [14), evolving user preferences (21), and environmental shifts [16] [16]-are inherently non-stationary, with reward distributions that change over time. This has led to growing interest in non-stationary MAB (NSMAB), which incorporates mechanisms for detecting and adapting such changes, making it more applicable to dynamic environments.
However, most of the existing literature on NSMAB assumes that reward feedback is available to the agent every round. This overlooks critical aspect of many real-world applications, where feedback is often limited. For example. in recommendation systems, repeatedly asking users for feedback on the quality of recommendations can lead user fatigue or annoyance [33] Similarly, in reinforcement learning from human feedback (RLHF) [1], essential signals such preference comparisons, demonstrations, or ratings are often costly, cime-consuming, or constrained by the availability of expert annotators. Motivated by these challenges, we introduce a new model of constrained feedback in non-stationary multi-armed bandits, termed CONFEE-NSMAB, in which the availability of reward feedback is limited.
Similar to existing NSMAB frameworks, CONFEE-NSMAB quantifies the degree of non-stationarity in the environment by tracking changes in reward distributions and assumes that the variation in mean rewards over the time horizon T is bounded by variation budget V1 [5]. However, unlike conventional NSMAB, the agent in CONFEE-NSMAN cannot observe reward feedback at every round.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Paper
Setting
Variation Vr
Constrained Feedback
Upper Bound
Lower Bound
Besbes al.
Non-Stationary
Known
X
OUK4Spp T4/33)
SK V. p TT3)
Wei and Luo 37
Non Stationary
Unknown
X
Efroni al. 13
Stationary
1 A pppi
Ô ( KV/yya
This Work
Non-Stationary
Unknown
Table 1: Comparison with the most closely related works, where is the time horizon, K is the number of arms, Vi denotes the variation budget capturing the degree of non-stationarity. and B is the reward feedback querying constraint.
Instead, the total number of reward feedback queries available to the agent over the time horizon T is limited by a reward query budget B. This constraint provides the agent with significantly less information than in standard NSMAB settings, making the CONFEE-NSMAB problem fundamentally more challenging. Motivated by this, the primary question we seek to address is:
How does the reward feedbackk querying constraint affect the agent's decision decision-making process in CONFEE-NSMAIB particularly in balancing exploration, exploitation, and query efficiency under limited feedback??
Despite recent advances in feedback-constrann MAB [3 26 and prior-fred non moon-tationnay RL or MAB [37], this question remains, the best of our knowledge, unexplored in the context of constrained feedback learning for NSMAB (see Table D. In this setting, the agent faces a unique dilemma: balancing exploration and exploitation in non-stationary environments while operating under striet feedback query constraint. This introduces a new layer of complexity to the already challenging problem of designing prior-free algorithms for NsMAB with near-optimal dynamic regref guarantees. This leads us to the second research question:
possible to design prior-free algorithms CONFEE-NSMAN that achieve near-optimal dynamic regret guarantees?
Motivated by these open questions, we make the following key contributions:
CONFEE-NSMAR Framework. We introduce CONFEE-NSM B, new framework for NSMAB that incorporates a reward feedback querying constraint, limiting the total number of reward feedback queries the agent can issue over the time horizon while learning in non-stationary environments.
Near-Optimal HY QUE Algorithm. A standard approach in NSMAB is to run multiple instances of base algorithm at varying time seales using randomized scheduling to detect non-stationarity (37). We extend this multi-scale idea to CONFEE-NSMAB. but the extension presents two key challenges:
D Query Allocation Trade-off: Naively querying every round quickly exhausts the budget, while querying too infrequently risks missing abrupt changes. Thus, the challenge is to design query allocation strategy that balances timely detection with budget preservation, including careful distribution across time scales.
Lonng Non-Query Segments: Longer instances aimed at capturing gradual shifts may contain extended non-query periods, limiting the algorithm's responsiveness. is critical to ensure sufficient query frequency for timely change detection without prematurely exhausting the budget.
To address these challenges, we propose HYQUE, a hybrid query allocation algorithm that com- bines baseline
minimum query rate within each block- with on-demand mechanism that dynamically injects queries when usage falls behind a near-linear pace. HYQUE is prior-free and provably near-optimal, achieving regret upper bound that matches the lower bound up to logarithmic factors. We establish this lower bound to understand how the reward feedback querying constraint impacts the best-achievable dynamic regret in CONFRE-NSMAB.
'The algorithm operates without prior knowledge of the degree of non-stationarity, making it more practical and broadly applicable. inn non- statttotionyy settings, the conventional "static regret", defined with respect to a single best action, may perform poorly. Instead, "dynamic regret" is the appropriate performance metric (5). See Section for a detailed detinition.

---

2 Model and Problem Formulation
NSMAB. We consider a NSMAB setting with [K] = (I...., , K} arms, where an agent selects one arm k [K] each round E [T] (1..... T). When arm k is pulled, a reward R E [o. 1] is obtained, where R2 is random variable drawn independently from an unknown distribution. Let ii denote the expected reward of arm & at round t. Let
{uî k E [K],t E [ denote the underlying sequence of true expected rewards for all arms over the time horizon T. In NSMAB, 14 may vary across rounds. Consistent with conventional NSMAB settings [5), while the expected rewards of each arm may change arbitrarily often, the total variation in the expected rewards over [T] is bounded by variation budget VT, whose value is unknown to the agent. The corresponding
non-stationarity set can be defined as V = 11: > SuPRE[K]lu4+4 uf1 < VT].
NSMAB with Constrained Feedback (CONFEE-NSMARH two actions: selects an arm k E [ to pull, and decides whether to query the reward feedback subject to the budget constraint. Specifically, we assume that querying reward feedback incurs a unit cost, and define Iq E {0, } as an indicator variable denoting whether the reward feedback is queried at round t. The agent can observe the reward R immediately only if uq = 1. The total number of queries the time horizon T is constrained by known query budget B, i.e. E(= nquery < B. An algorithm A is considered feasible if selects an arm l E [K] at each round t and adheres to the total query budget constraint. Throughout the paper, we use Squery
each round t, the agent performs
{t E [7] Iquay 1} and {1 E (7) Iquery = 0} to denote the sets of query and non-query rounds, respectively.
Quon-query
Dynamic Regret. Let μ ma fu denote the optimal expected reward round The performance of the agent is evaluated using the dynamic regrer. This metric compares the cumulative expected reward of optimal policy (aware of μ each round) with that accrued from the sequence of arms selected by algorithm A. Formally, it is defined as
(A)
sup nEV
Σ M
E
E
where the expectation taken over the randomness rewards and potentially the internal randomness of the algorithm. The objective of the agent in CONFEE-NEN EE-B is to minimize the dynamic regret. While this definition is similar to those in existing NSMAB frameworks, the key distinction is that, in CONFRE-NSM.L A,, the agent cannot always observe the reward feedback at each round. Instead, querying the reward feedhack incurs a cost, which constrained by a budget over the time horizon (i.e., Σ nquery < B.). These fundamental differences necessitate new techniques for online algorithm design and dynamic regret characterization, which we will discuss in detail in Sections and respectively.
3 Prior-free Algorithm for CONFEE-NSMAB
We show that is possible to design a prior-free algorithm for CONFEE-NSMAB that achieves near-optimal guarantees on dynamic regret.
3.1 Motivation and Challenges
We begin by outlining the core principles that guide our approach. The primary objective is to strike a balance between accurately detecting environmental changes and efficiently managing a limited query budget.
Balancing Change Detection and Query Usage. In NSMAB, the algorithm must detect envi- ronmental changes by tracking shifts in the mean rewards of the arms. However, when the total number of queries is constrained, naive strategies such as querying every round quickly exhaust the query budget. Conversely, querying too infrequently may hinder the algorithm's 's ability to detect abrupt changes a timely manner. Effectively allocating queries across multiple time scales without exceeding the budget B requires carefully crafted strategy. The central challenge, therefore, is to develop a query allocation mechanism that balances the trade-off between aggressive exploration (to detect changes) and conservative query usage (to preserve the budget).
3

---

active
inactive
m=3
query
m=2
m=1
m=0
Figure I: An illustration of a single block in BAQUE with 3 and is shown. The figure spans a total of 16 rounds (2 2) and highlights the hierarchical structure of the procedure across four scales (m 0, 2, 2,), where each scale alternates between active and inactive states. The illustration includes instance at m = 3, I instance at m = 2, 1 instance at m 1, and 3 instances m 0. Bold solid lines indicate active periods, while thin solid lines represent inactive periods. Active periods are further divided into two segments-continuous and dotted sections- represent
distinct querying and non-querying rounds.
Budget Splitting across Multiple Scales. Conventional prior-free NSMAB approaches often employ multi-scad restart technique, where multiple instances of base algorithm (e.g.. UCB1 (I] are run at exponentially increasing time scales [10 37 This ensures that at least one instance operates an appropriate granularity to detect changes. As result, it becomes essential to allocate the query budget across different scales and their corresponding base algorithms. This allocation serves a dual purpose: it ensures that the regret incurred during query segments remains near-opiimll to settings with full feedback-and it supports the accuracy of decisions made in non-query segments, which rely entirely on the reward estimates obtained during query phases.
Balancing Query Frequency. For longer instances designed to capture subtle environmental changes, there may be extended non-query segments. When the agent encounters prolonged sequence of non-query rounds, it may be unable to verify whether the environment has shifted, leading to potentially significant regret if the chosen arm becomes suboptimal due an undetected change. Consequently, non-query gaps cannot be arbitrarily long without degrading performance. The algorithm must query frequently enough to detect changes in timely manner, while ensuring that the query frequency is not so high as to prematurely exhaust the total query budget B.
3.2 Hy QUQ Algorithm
Overview. To address these challenges, we propose HYQUE, hybrid query allocation algorithm for CONFEE-NSMAB HYQUE partitions the time horizon into blocks of geometrically increasing lengths, within which multiple parallel instances of a base algorithm (c.g.. UCB1) operate different temporal scales. Small-scale instances are more responsive to rapid changes and emphasize explo- ration, while large-scale instances target slower trends and focus exploitation. Since the block length upper- bounds the instance duration, this structure enables systematic query scheduling that balances adaptability non-stationarity, effective exploration, and budget conservation.
At the block level, HYQUE invokes baseline query allocation subroutine (BAQUE) (Section 3.2.1 I which guarantees a minimal share of queries across scales ensure robust change detection. On top of this, HYQUE incorporates an on-demand query allocation mechanism (Section 3.2.2) that continuously tracks cumulative query usage and injects additional queries when usage falls behind a near-linear pacing schedule. This two-ticred design offers worst-case robustness within each block while adaptively adjusting smoother environments, achieving a principled trade-off between stability and flexibility in query allocation. We begin by detailing the BAQUE subroutine.
3.2.1 The BAQUE Subroutine
To ensure that each time-scale instance receives sufficient queries for detecting abrupt changes, pre-allocate a baseline portion of the query budget. Instead of distributing queries across the entire time horizon, allocation is performed at the block level, covering instances operating at different scales. We guarantee that within the active rounds of each instance, approximately a 27 designated for query rounds.
fraction is
Although this proportion may appear small, ensures that no instance is deprived of queries, thereby preserving HY RUQUEE' 's ability to adapt to frequent or significant environmental changes. Typically,

---

each instance begins with an initial one-shot query batch, in which the algorithm uses its baseline query quota collect updated reward observations (Line 10 Algorithm [T]. This imitial query batch is crucial for enabling reliable change detection at the corresponding scale.
By distributing queries in this manner, each scale is guaranteed sufficient number of queries over the time horizon, ensuring its ability to detect significant changes (Lemma 4.6). Moreover, for long-duration instances with extended non-query periods, the probabilistic creation of shorter- scale instances-cent beginning with its own query batch-naturally segments the timeline into overlapping sub-intervals. These overlaps help prevent prolonged periods without feedback, as such uninterrupted non-query spans are unlikely to persist with high probability (Lemma 4.4).
Algorithm 1 BAQUE: Baseline Query Allocation
Require: Query budget ratio b b= [2T] B1, time-scale parameter 1: for 7 = 0, 1, 26 1, ,,,...," 2".
1 do
2:
for m n, n 1, 0 do
3: if r is a multiple of 2 then
4:
With probability === initiate a new instance In,m,r spanning rounds [r + 1,7
b- .m);;
5: for each instance In,mar do
6: Let Sp,m.r be its active rounds;
7: Query batch: For the first max(1, [|S,,,,,,, active rounds, run UCB1 (collect reward
and update the UCB index, denoted as gt):
8: Non-query batch: In the remaining active rounds, pick arms according to their frequencies from query batch (no reward feedback).
Algorithm| D constructs a block of length 6- 2n rounds and deploys multiple instances of UCB1 across 0, I,..., As illustrated in Fig. I these instances operate at
various time scales indexed by different granularities, resulting in overlapping activity that alternates between query and non-query rounds. The multi-scale instance setup (Lines 1-7) proceeds by iterating through the timeline in steps of b, and at each time т, a new instance In,m.r is probabilisticall initiated if r divisible by b- 5m2 This randomized activation ensures coverage across both short- and long-term scales, allowing the algorithm to adapt to diverse patterns of non-stationarity. Once initiated (Line 4), an instance In.m.r covers the nominal time span [T 1, b. 2n).. The of rounds where the instance is truly active, denoted Sa,m.7. is determined through hierarchical masking mechanism: a round I within the nominal span included Sn,m,r if and only if is not covered by any initiated instance operating at a finer scale (i.c., with mn' < m). This ensures that finer-scale instances take precedence over coarser ones in shared intervals.
The baseline query allocation phase (Lines 8-12) then operates on these active rounds. For each instance In,m,r, its (potentially non-contiguous) active rounds Sn,m.r are split into two parts (Lines 10-12). The first is a query batch of size max(1, ||Sa.m.-l/bl), during which UCB1 is actively invoked and reward feedback is collected. The second is non-query batch, comprising the remaining rounds, where actions are selected according to the empirical frequency distribution of arms from the query batch. For example, if particular arm was selected in 20 out of 50 query rounds, it will be selected in the non-query phase with probability 0.4 withott incurring additional feedback cost. Our choice of UCB1 as the base algorithm and frequency-based sampling for the non-query phase is motivated by the goal of providing a clear theoretical analysis. In practice, these components are modular and can be replaced by other choices, such as different base algorithm or an alternative sampling strategy like greedy policy that exclusively selects the most frequently chosen arm from the query phase.
3.2.2 The HUQUE Framework
Although BAQUE ensures robust performance in worst-case scenarios, it can be overly conservative when changes in the environment are infrequent relatively mild. To better leverage such settings, we introduce HYQUE (Algorithm 2). which augments BAQUE with an on-demani query allocation mechanism.
Intuitively, when the on-demand component detects that the cumulative number of queries used so far falls short of target proportion--spciffccalll
-spccifically, 4 B at time t-it allocates additional query rounds
5

---

at the current scale to refine reward estimates. This mechanism promotes near-linear pacing of query usage over time, ensuring that total query consumption closely tracks the ideal rate of P. thus avoiding both excessive querying and underutilization. To account for stochastic variability, buffer term min min(T//BB 2n, - t is subtracted from the threshold. This guards against over-querying in short segments and prevents abrupt spikes in query activity (see Remark 44.5 44.5 and Lemma As result, HY HUQUEE is able to opportunisticall allocate more queries during stable periods, enabling finer reward estimation and lower regret in environments that do not change drastically.
Algorithm 2 HYQUE: Hybrid Query Allocation
1: Initialize: current round & <- 1, used queries B' 4- O.
2: for = 0, I.... do
3: Set fn < t and initialize BAQUE for block [tn, in + 2" - with the time-scale parameter
11;
4: while < fn b- 2" do
5: if current instance has queries then
6:
Receive the UCB index Jr and the selected arm from BAQUE, play the arm, then
increment and B";
7:
Update the BAQUE instance with the observed feedback; Perform environmental change tests. If any test fails, restart new phase from Line
8:
9:
else
10:
13 <
L.
min 2", T T -t then
11:
Convert the current non-query round into query round and jump to Line 6; No feedback requested; and set / <- ++1
12:
HYQUB partitions the time horizon into multiple phases, each initiated upon detecting a change in the environment. Within each phase, time is further divided into consecutive blocks of length b 2 rounds. the beginning of each block, HYQUE invokes BAQUE to initialize multi-scale instances and records the block's start time t, the block spans the interval [tn, tn + b. 2" 1].
During each block, HUQUE actively monitors two key aspects determine whether restart the phase or allocate additional queries.
(1) Change Detection (Lines 5-9 of Algorithm 2): For given instance In,m,r, define Sn,m,t {t' in I t' I t; E Squery as the set of its query rounds up to time t. Let U, min......... Ir be the minimum estimated reward, and define the confidence bound p(l)
6(log log (2) Klogt + K
Let start and end denote the first and last query rounds
of the instance, respectively. Two tests are performed: (i) If end for some order-m instance and 2m Eves Rv 2 U. + 9)(2 the test returns fail; and (ii) If the average discrepancy satisfies [5m.m, Eves.... (āe R..) 2 3p([Sn.m,tl) I),, the test also returns fail.
(2) On-Demand Query Activation (Lines 10-12): Let B' be the total number of queries used up to round t. If B' falls significantly below the expected usage T -adjusteed by a buffer term min
&B
T 2n T - then HYQUE allocates an additional query to the active instance. This VB
7B the maximum consecutive query rounds needed to ensure worst-case performance (Remark (455): (ii) 2n: the maximum size of any single query batch in the current block; and (iii) T - t: the remaining number of rounds, ensuring budget feasibility.
buffer accounts for: (i)
Main Theoretical Result
In this section, we bound the regret of the HYQUE Algorithm.
Theorem 4.1. For CONFEE-NSMAP with a query budget = wT33/4) and an unknown variation satisfying VT E ( our HYQUE utilizes at most B queries, and its regret is bounded with high probability as follows:
K /1//////0
RS (HYQUE) s Ô
(2)
11/

---

Non
Upper
Nop- StatStationar Bandits Problem within Query Rounds
Non-Sian Son-Stationary
Lemmu
Bandits Algurithm
δ ( pal))
Non-Stationary Multi-Armed Bandits under
Lemma A.B: KAAAyp Bur
Regret upper bounded by King!er B
Baseline Query Allscation
Foedback Constraint
Query Allecation Strategles for Minimizing Regret Non-Query Reundh
Lemma 4.11: ① Kimppr
On-demand Qvery Allocation
The workflow of HYQUE for CONFEE-NSMAB and its corresponding regret analysis. The top (green) box addresses the NSMAB problem during query rounds, which leads the regret bound established in Lemma 4.9 The bottom (purple) box describes the query allocation strategies within HYQUE, where BAQUE operates as subroutine. Together, they aim minimize regret during non-query rounds, as analyzed in Lemmas 4.10 and 4.11 By combining these results, Theorem provides the overall regret bound for our HYQUE algorithm.
Figure 2:
Ignoring logarithmic factors, this upper matches the lower bound in Theorem 5. in terms of its dependence on K, Vr. T, and B, thereby establishing the ncar-optimality of HYQUE. When B Q(T), the regret upper bound simplifies Ô (K) / 12/3)) recovering the best-known result for NSMAB (5].
As discussed earlier (Section 3.1 our HYQUE must balance environmental change detection with query allocation due to the presence of the query constraint in CONFEE-NSMADE This key distinction renders existing regret analysis for NSMAB [5] 37] not directly applicable, and necessitates the development of new proof techniques tailored to constrained feedback settings. First, establishing feasibility (Section 4.1.I requires careful analysis of query usage, made more challenging by the inherent uncertainty in the non-stationary environment. Second, we introduce a novel regret decomposition (Section 4.1.2) that enables us isolate and address the unique structural challenges posed by limited feedback, allowing separate treatment of regret incurred during query and non non-query rounds. Third, building upon this decomposition, we develop fine-graine ane-ggained analytical techniques (Section 4.1.3) to rigorously bound the regret contributed by non-query rounds-an essential step in accurately characterizing performance under constrained feedback. An overview our theoretical analysis is presented in Section 4.1 with the complete proof detailed in Appendix A
lower bound on the budget a mixture of both abrupt and gradual changes. Consequently, any algorithm aiming for optimal regret must detect all such changes with high probability, which in turn requires a sufficiently large budget B. Specifically for the HYQUE algorithm, a larger B ensures that its randomized querying strategy provides adequate coverage across the entire time horizon. Furthermore, it facilitates cleaner analysis, allowing us to derive an explicit expression for the algorithm's 's success probability and to guarantee strong high- high-probability bound, such as Pr(optimal regret) 2 ex)(-T
necessary because non-stationary bandit problems can exhibit
Remark 4.2. If VT known in CONFEE-NSMAB. a near-optimal upper bound can similarly be achieved, and the algorithm becomes significantly simpler. A detailed description of this algorithm, along with rigorous analysis of its theoretical regret bound, is provided in Appendix
Remark 4.3. When B T, allowing queries at every round, HY HYQUE's behavior on query rounds aligns with the principles of the MASTER algorithm [37], the only known prior-free solution for non-stationary RL. As a result, the query allocation component of HYQUE primarily affects the regret incurred during the non-query segments.
4.1 Proof Sketch
We provide overview of the theoretical analysis for the regret upper bound for HY QUE.
7

---

4.1.1 Feasibility of HYQUE
Lemma 4.4 (Bound on Consecutive Non-query Rounds), For some universal constant C > O, the probability that BAQUE experiences more thun T/ /B conseculive non-query rounds in that block is at most exp
B9/4 VT
Instances initiated by BAQUE start with a query phase. The probability of specific potential instance In,m. (for block parameter rt, scale m) not being initiated is 1 - Consequently, by bounding the probability that no new instance is initiated over period of T rounds, we establish an upper bound on the probability that this period consists entirely of non-query rounds (as any new instance would have introduced queries).
Remark 4.5. The same analysis applies query rounds well. In particular, with B o(T), the probability that BAQUE undergoes more than T/vB consecutive query rounds is also at most exp
B3/4 VT
Lemma 4.6 (Stability in Each Phase). Consider any phase of HYQUE. Throughout this phase, the fraction of query rounds allocated by BAQUE, relative to the total number of rounds the same
phase, satisfies: 1 B (# of query rounds the phase) B
<
2 T (# of total rounds in the phase)
T'
Lemma 4.7 (Query Budget Feasibility). For HYQUE, the total number query rounds throughout the time horizon T does not exceed B.
In each phase, HYQUE maintains the query allocation within the proportion B/T for every block except potentially the last one, where additional caution is needed to handle boundary effects. In the final block, to avoid a large run of consecutive query rounds following an immediate restart, HUQUE employs "buffer term" as discussed in Section This design ensures that the query allocation does not exceed the proportion B/T. Consequently, by combining BAQUE with on- demand allocation, HYQUE ensures that the total number of queries used does exceed B over the entire time horizon T. A detailed proof is provided in Appendix A. A.1
4.1.2 Regret Decomposition
We decompose the dynamic regret Ry into three parts:
Lemma 4.8. For any algorithm A, we define S.-1 Squery (1,..., 1} the of query rounds whose observed feedback is used by the algorithm at round I. Consequenily, the arm selection a, is function (Ha-1) of the history He-1 (a,,Te) St-1). The regret in (T) can then be upper bounded by:
R
RT S
Σ (ES
4 -
Σ
Rd
Σ
E
max
Σ
E
Σ
Re
KE[K]
S
LES,-1
Stanguryyyyy
R.pe
Razoor
Rd
Σ a
Σ
Σ
14
max KE
S
LES,
Let Rapee represent the regret incurred when HYQUE actively queries for feedback. Let R mon--uery denote the regret incurred when HYQUE decides not to query. The latter can be further decomposed into two subcomponents. (i) Error regret (Reror); This arises from inaccuracies in the decision- making of HYQUE when it relies previously gathered information about the arms without further
R
querying. The term E max Etes.., |S-il
represents the expected reward of the empirically
best arm identified using feedback from S, 1- (ii) Drift regret (Rdritt); This accounts for the regret caused by environmental changes, such as shifts reward distributions, that are not promptly detected due to the lack of feedback.

---

4.1.3 Bounding Total Regret
Since the on-demand query allocation converts some non-query rounds into query rounds, we first analyze the regret of HyQUe under the baseline allocation. We then prove that on-demand allocation does not increase HY QUEs regret.
Lemma 4.9. With high probability, we have RT Sō (O(1//V B2/S)
For each block, as long as environmental change detection is not triggered, it suggests that significant changes are unlikely to have occurred during the query rounds (though this does not necessarily imply stability during the non-query periods). Within each block, the query rounds allocated through BAQUE, regardless of different instance scheduling strategies, exhibit similar properties to those in standard NSMAB algorithms.
K K3/Byt/8T B1/3
Lemma 4.10. With high probability, we have Ra < Ō
If the environment remains stable and does not undergo drift, the regret caused by these inaccuracies will not exceed 27 Ro..y Thus, we obtain the bound Lemma 4.10 10 Finally, we analyze the regret due to environmental drift:
K /1//
/8T
Lemma 4.11. With high probability, have Ra S Ô
BL73
By combining the bounds for Ra and Ryiin we derive: Ry Raaquee query < Ô /
Substituting the bound for Rquery and combining the bounds for Rquery and RT hon-qurry obtain
k1/3////8T Note that the above regret bound is B1/3
the total regret: Rr- RIuery
RT Rommquurry
non-query
derived under the assumption of BAQUE. Since the on-demand allocation in HYQUE converts some non-query rounds into query rounds, the number of such converted rounds does not exceed B/2. Consequently, even if this conversion incurs additional regret, it remains at most of the same order as R4 ensuring that the overall order of the regret bound remains unaffected.
5 Lower Bound
Theorem 5.1. Consider CONFEE-NSMAB with 2 2 arms, variation Vr E [K-, and constrained feedback B 2 K. For any algorithm A, the following holds:
K1/3
Rr(A) 2 Ω
(4)
B1/3
The core intuition behind the lower bound, established via hard problem instance in which the environment changes periodically across distinct batches, is that any algorithm must consistently query arms within each batch reliably identify the optimal arm for that period. If an algorithm uses many queries per batch to ensure high accuracy, it quickly depletes the overall query budget B, leaving insufficient queries for subsequent batches. Conversely, if it queries too sparsely, it fails to distinguish the optimal arm from suboptimal ones, leading to increased regret.
The lower bound highlights the fundamental challenge of allocating limited query budget across multiple batches. We show that naive strategies- such as uniformly distributing queries or concentrat- ing them heavily in only few batches lead to substantial regret. This inter-batch query allocation dilemma introduces new layer of complexity in the NSMAB problem under constrained feedback. Remark 5.2. The case of T is particularly instructive because aligns with the conventional NSMAB setting (where Vr is typically considered within [K-1 K -T] and removes the feedback budget constraint. Under this B regime, the VT range [K-1 K- specified in Theorem 5.
/3/s5//31 B1/3
conforms to the standard [ [- K -T]: simultaneously, the lower bound Ω
simplifies
S2 [K1/3///3/2/33 This result aligns with established lower bound for NSMAB problem without feedback querying constraint [5) A detailed proof is available in Appendix D

---

Related Work
Non-stationary multi-armed bandits (NsMAB). NSMAB have been extensively studied, with a focus on adapting algorithms to environments with changing reward distributions, offering per- formance guarantees based on measures such as total variation or the number of abrupt changes 25
2, 5 15|
22 3
[0]. Recent works also address smoothly evolving environments [18 30
Extensions contextual bandits 33
24
32 linear bandits 41 dueling bandits [27 6
and other settings [5
40
20
9
12
23
g have been explored. However, none of these works
consider settings with a reward feedback querying constraint.
Learning with constrained feedback. Our work relates closely to learning with constrained feedback, where the agent manages limited budget for acquiring observations. Prior studies [26 [3] focus on optimizing feedback allocation in stochastic settings. Other related works include MAB with paid observations (28). which assume cost and reward share units-ofted impractical and require larger budgets. Bandits with additional observations [39] and knapsacks 44] either assume full reward observability terminate when the budget is exhausted. However, these approaches focus on stationary environments, whereas it is well-known that non-stationary settings demand fundamentally different algorithmic and analytical tools.
Limitations and Future Work
One limitation is that our HYQUE relies on a predefined query budget, which may not always align with practical applications where feedback availability be more dynamic influenced by external factors. Future work could explore adaptive mechanisms that adjust the query budget in real-time based observed feedback patterns external constraints. Additionally, while HYQUE achieves near-optimal dynamic regret guarantees in CONFEE-NSMAN setting, extending these guarantees to more complex decision-making frameworks, such non-stationary reinforcement learning with constrained feedback, remains an open challenge. Finally, our approach primarily focuses regret minimization, but in some applications, other performance metrics, such fairness in feedback allocation or minimizing computational complexity, may also be important. Exploring multi-objective formulations of constrained feedback learning could provide deeper insights into balancing different performance trade-offs.
Acknowledgements
This work supported in part by the National Science Foundation (NSF) grants 2148309, 2315614 and 2337914, and was supported in part by funds from OUSD R&E, NIST, and industry partners as specified in the Resilient & Intelligent NexIG Systems (RINGS) program. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funding agencies.
References
[1] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-Time Analysis of the Multiarmed Bandit Problem. Machine Learning. 47(2):235 256, 2002.
[2] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(1):48-77, 2002.
[3] Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Proceedings of the 32nd Conference on Learning Theory, pages 138-158, 2019.
[4] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. In Proceedings of the 54th Symposium on Foundations of Computer Science, pages 207-216, 2013.
[5] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed--annee problem with non- stationary rewards. Advances in neural information processing systems 27, pages 199-207, 2014.
10

---

[6] Thomas Kleine Buening and Aadirupa Saha. ANACONDA: an improved dynamic regret algorithm for adaptive non-stationary dueling bandits. Proceedings of the 26th International Conference Artificial Intelligence and Statistics, pages 3854-3878, 2023.
[7] Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 418-427, 2019.
[8] Titas Chakraborty and Parth Shettiwar. Non stationary bandits with periodic variation. In Proceedings of the 23rd International Conference Autonomous Agents and Multiagent Systems, pages 2177-2179, 2024.
(9] Wei Chen, Liwei Wang, Haoyu Zhao, and Kai Zheng. Combinatorial semi-bandit in the non- stationary environment. In Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence, pages $65-875, 2021.
[10] Yifang Chen, Chung- Wei Lee, Haipeng Luo, and Chen- Yu Wei. A new algorithm for non- stationary contextual bandits: Efficient, optimal and parameter-free. In Proceedings of the 32nd Conference on Leurning Theory, pages 696-726, 2019.
[11] Paul Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Advances in neural information processing systems 30, pages 4299 4307, 2017.
[12] Yuntian Deng, Xingyu Zhou, Baekjin Kim, Ambuj Tewari, Abhishek Gupta, and Ness B. Shroff. Weighted gaussian process bandits for non-stationary environments. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, pages 6909-692 2022.
[13] Yonathan Efroni, Nadav Merlis, Aadirupa Saha, and Shie Mannor. Confidence-budger matching for sequential budgeted learning. In Proceedings of the 38th International Conference on Machine Learning, pages 2937-2947, 2021.
[14] Guillermo Gallego and Garrett Van Ryzin. Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management science, 40(8);999-1020, 1994.
[15] Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory, pages 174-188, 2011.
[16] John C Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society Series B: Statisticul Methodology, (1)::1448-164 1979.
[17] Kihyuk Hong, Yuhang Li, and Ambuj Tewari. An optimization based algorithm for non- stationary kernel bandits without prior knowledge. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, pages 3048-3083 2023.
[18) Su Jia, Qian Xie, Nathan Kallus, and Peter Frazier. Smooth non-stationary bandits. In Proceedings of the 40th International Conference on Machine Learning, pages 14930-14944, 2023.
[19] Baekjin Kim and Ambuj Tewari. Randomized exploration for -tatioati stochastic linear bandits. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence, pages 71-80, 2020.
[20] Chuanhao Li, Qingyun Wu, and Hongning Wang. Unifying clustered and non-stationary bandits. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pages 1063-1071, 2021.
[21] Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A contextual-bandde approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[22] Fang Liu, Joohyun Lee, and Ness B. Shroff. A change-detection based framework for piecewise- stationary multi-armed bandit problem. In Proceedings of the 32nd Conference on Artificial Intelligence, pages 3651-3658, 2018.

---

[23] Shang Liu, Jiashuo Jiang, and Xiaocheng Li. Non-stationary bandits with knapsacks. In Advances in Neural Information Processing Systems 35, 2022.
[24] Haipeng Luo, Chen- Yu Wei, Alekh Agarwal, and John Langford. Efficient contextual bandits in non-stationary worlds. In Proceedings of the 31st Conference on Learning Theory, pages 1739-1776, 2018.
[25] Joseph Charles Mellor and Jonathan Shapiro. Thompson sampling in switching environments with bayesian online change detection. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics, pages 442-450, 2013.
[26] Nadav Merlis, Yonathan Efroni, and Shie Mannor. Query-reward tradeoff's in multi-armed bandits, arXiv preprint arXiv:2110.0572 2021.
[27] Aadirupa Saha and Shubham Gupta. Optimal and efficient dynamic regret algorithms for non- stationary dueling bandits. In Proceedings of the 39th International Conference on Machine Learning, pages 19027-19049, 2022.
[28) Yevgeny Seldin, Peter L.. Bartlett, Koby Crammer, and Yasin Abbasi- Abbasi-Yadkori. Yadkori. Prediction with limited advice and multiarmed bandits with paid observations. In Proceedings of the 31st International Conference on Machine Learning, pages 280-287, 2014.
[29] Aleksandrs Slivkins. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 1-66, 2019.
[30] Joe Suk. Adaptive smooth non-stationary bandits. CoRR, abs/2407.08654 2024.
[31] Joe Suk and Arpit Agarwal. When can we track significant preference shifts in dueling bandits?
In Advances in Neural Information Processing Systems 36, 2023.
[32] Joe Suk and Samory Kpotufe. Tracking most significant shifts in nonparametric contextual bandits. In Advances in Neural Information Processing Systems 36, 2023.
[33] Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert E. Schapire. Efficient algorithms for adversarial contextual learning. In Proceedings of the 33nd International Conference Machine Learning, pages 2159-2168, 2016.
[34] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
[35] Claire Vernade, András György, and Timothy A. Mann. Non-stationary delayed bandits with intermediate observations. In Proceedings of the 37th International Conference on Machine Learning, pages 9722-9732, 2020.
[36] Jing Wang, Peng Zhao, and Zhi-Hua Zhou Revisiting weighted strategy for non-stationary parametric bandits. Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, pages 7913-7942, 2023.
[37] Chen- Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: an optimal black-box approach. In Proceedings of the 34th Conference on Learning Theory, pages 4300-4354, 2021.
[38] Jia Yuan Yu and Shie Mannor. Piccewise-saatioaayy bandit problems with side observations. In Proceedings of the 26th International Conference on Machine Learning, pages 1177-1184, 2009.
[39] Donggyu Yun, Alexandre Proutière, Sumyeong Ahn, Jinwoo Shin, and Yung Yi. Multi-armed bandit with additional observations. Proc. ACM Meas. Anal. Comput. Syst., 211::2:1 2018.
[40] Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 1508 1508-1518, 2020.
[41] Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou. A simple approach for non non-stationary linear bandits. Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 746-755, 2020.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses the limitations of the work in the last section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
Yes, the paper provides the full set of assumptions and delivers complete and correct proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, the paper provides all the necessary details for anyone reproduce the main experimental results, ensuring transparency and allowing others validate the claims and conclusions independently.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
14

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The paper provides all the necessary details for anyone to reproduce the main experimental results, ensuring transparency and allowing others to validate the claims and conclusions independently.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.com cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
www.c//wwgeeeeeeee Saateees//ooSSmmiiiiia SowpoddeumiissiooPo... wwiiiisssiiiicyiyioo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper clearly outlines essential information needed understand the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Yes, the paper appropriately reports error bars and provides correct definitions or other relevant information about the statistical significance of the experiments, ensuring clarity and accuracy in the interpretation of results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper gives clear details on the computer resources needed for each experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttpp////oorrips..cppppptttttta
Answer: [Yes]
Justification: The research conducted in the paper adheres to the NeurIPS Code of Ethics in all respects.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
16

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is a theoretical paper and poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
19

---

A Proof of Theorem 4.1
A.1 Total Used Queries
We prove that the total number of queries used by the algorithm cannot exceed B.
A.1.1 Proof of Lemma 4.4
Let To [T/vB] be the length of the consecutive non-query round sequence we are considering. Such sequence, if attributable to the failure of initiating new instances, implies that all probabilistic attempts to start new instance within this interval of Lo rounds failed. Each new instance initiated by BAQUE would start with a query batch, thereby interrupting a sequence of non-query rounds.
The BAQUE subroutine attempts to initiate instances In,m.r at various scales E (........ . where n is the time-scale parameter for the current block. If an interval of Lo rounds contains any T that is multiple of b 2" (the block's 's largest scale-defining period), an instance at scale m initiated with probability 1, preventing the long non-query sequence, Thus, for a long non-query sequence to occur due to initiation failures, we must have Lo < b 2". In this scenario, no initiation attempt scale m n occurs within the Lo rounds. The relevant scales for potential initiation within the interval are m E (O...., min(n - 1, ( (To/b))))
To establish a bound that is independent of specific block's n, we consider an "effective ensemble" of scales that contribute to breaking non-query sequences. We define an effective maximum scale relevant for analyzing non non- con-staiionartt of length Lo. Let M = [log2 (T' (T/VB)) B)] This choice reflects characteristic scale related to Lo = T//B.. We assume that the initiation probability for an effective scale m within this context can be modeled as p'm. m M scale would have p'1 = 1).
for m {0, (O....,Ae M 1}. (The
The probability of not initiating an instance at a specific opportunity (r, m) is 1 - p'm The attempts independent. The probability that new instance is initiated over the Lo rounds is:
M-1
Pnoo new instance in Lo rounds) <
II m=0
II
1-2(m-M)/2
rE(t,(+o--1 a multiple b-2
Let Nm (Lo) be the number of multiples of b-2n in interval of Lo rounds. Nm(Lo) [Lo/(622T)]] Using the inequality - x S e for x 2 O:
M Σ
Pnno new instance) < exp
Nm - 2
We approximate Nm. (Lo) Lo/(b )" ignoring the floor for lower bound on the sum in the exponent (which leads to an upper bound on the probability). For a more careful bound, (L)) 2 Ta/(b- 2m) 1. Using Lo/(b- 2 directly: The sum in the exponent, Sexp. is:
M-1
M-1
Seap ~
Σ
Lo
20m-2)))))))) M)/2
Lo
Σ m==
2 m/2
b. 2m
b. 2/12
m=0
The sum M 2 m/2 = - (1/V2). As M - 0o, this geometric series converges to
- (((1-1/2) = 2 + /2. For M 2 1, the sum is at least (for m = 0). Let C₁ = Ey G is constant factor typically between and 2 + v2.
Substitute Lo Re T/VB and b me 2T/B:
Lo T/VB B
VB 2
b B
2/B
And M =llgg (T/e)T/ so 2M T/VB (assuming T/v is a power of 2 for simplicity,
otherwise 2M < T/VBB- < M+ 1), which implies 2 (T//B)11" vT B1/4, Thus,
Sexp ~ C1 vB/2 VB.
B1/4
B3/1
C1
VT/B1/4
2
2/T
20

---

Taking C' C1/2 (absorbing constants), get Sexp 2 C CB3/4
vT Therefore, the probability
that BAQUE experiences more than Lo [T/vB] consecutive non-query rounds is most exp (-c 13/4 for some universal constant C > 0. vT
Remark A.I. Strictly speaking, we might union-bound over all intervals [t, t'] of length T/ B/ but the final exponent remains the same up to constant factor when B = (/(T2/33. Remark A.2. More generally, for any E [0, 1]. the probability that BAQUE experiences more than TB a consecutive non-query rounds within a block is at most exp (-C -B for some universal constant C
vT
A.1.2 Proof of Lemma 4.6
We analyze the conditions under which a restart triggered by dividing the proof into two cases, depending on the block index n at the time of the restart. For ease of exposition, we assume that the time horizon T is multiple of 2B.
Case A: n = 0. Under the algorithm's 's design, a restart is triggered only when a substantial shift in the reward distribution is detected. However, when O, only a single query round is allocated within the block. This is insufficient to satisfy the detection threshold required to initiate a restart. Therefore, no restart can occur at block index n and the condition for a restart due a prolonged non-query interval is not met.
Case B: 1. Now consider restart occurring in block with index n' 2 1. Let the blocks within the corresponding phase be indexed from to n', each representing a distinct time scale. By the structure of the algorithm, all preceding n' blocks must have fully completed both their designated query and non-query rounds without triggering a restart. Due to the enforced query budget ratio, the total number of rounds in these n' 1 blocks is 27 times the number of query rounds. On the other hand, in the n'-th block, the number of query rounds is at most equal to the total number of query rounds in the first n' blocks. Consequently, across all n' blocks in the phase, the total number of rounds is at most ă times the number of query rounds. It follows that for any such phase in which a restart occurs, the query density must satisfy:
B
# of query rounds in the phase
B T
T
T
of total rounds in the phase
A.1.3 Proof of Lemma 4.7
Within any phase of the algorithm, if restart occurs block with index n, the ratio of query rounds to total rounds during that phase bounded between 2T T. maintains the query allocation within the proportion B/T for every block except potentially the last one, where additional caution is needed to handle boundary effects. In the final block, to avoid a large run of consecutive query rounds following immediate restart, HYQUE employs a "Buffer term" as discussed in Section 3.2.2 This design ensures that the query allocation does not exceed the proportion B B/T. Specifically, the algorithm prevents excessive consccutive query rounds beyond T/VB (Remark 2n (the query bound for the longest instance in block), or T T-t (the remaining rounds). Consequently, by combining BAQUE with on demandd allocation, HYQUE ensures that the total number of queries used does not exceed over the entire time horizon
B B In each phase, HYQUE and
A.2
Bounding Total Regret
A.2.1 Regret Decomposition (Proof of Lemma 4.8
Starting from
T Σ (ng - 1
RT
we split the time index set [T] into Squery U query Thus,
Σ (Mi
uz)
Σ
(ng mc).
(5)
LESwey
tE quar
21

---

The first term corresponds exactly to RT (e), we add and subtract E
query since B[Rc]. For the second sum, EcE (19
R
E [K] Lies,-,
inside the summation:
S
))
R
R
14 14g =
max k
+
max E
KE(K] LES.-1
Σ
S
-
(6)
LES
We substitute 6 back into which yields the final decomposition.
Discussion. RT straightforward: the regret incurred on rounds where actual feedback is gathered. RT measures the gap between the best possible mean reward jr and the predicted reward used by the algorithm in non-query round. Rih captures how E [ Eies.,, [St-1 deviates from the true [[R]] μe because the environment changed after the last time that arm k n may instead be replaced by another |S
R²
was observed. Note that the term E maxxe[k] Eiss,
proxy or predicted reward for based on stale or previously gathered feedback. Let R denote this proxy reward. Then, (3) can be rewritten as:
RT
Σ LEStuy
E [[Ri]]
Σ Stenquryyy
Pi B(RT))
Σ
I [
Rimur
Since on-demand allocation converts non-query rounds into query rounds, first analyze the regret of the algorithm under baseline allocation. Then, we prove that on on-demand allocation does not increase the regret of the algorithm.
A.2.2 Proof of Lemma 4.9
Let begin by analyzing all the rounds where the algorithm performs query under baseline allocation. In each block, the algorithm contains series of instances, and for these instances, the length of the query phase is at least 2" Note that for each block, as long as the environmental change detection is not triggered, it indicates that during these query rounds, the environment is unlikely to have undergone significant changes (though this does not imply that the environment remained stable during the non-query periods). Note that for the UCBI I algorithm, we have the following result.
Lemma A.3. Let fo E [0, 1] denote the upper confidence bound corresponding to the optimal reward at each time step t Tquery. There exists non-stationarity measure VpI,t, such that when running
the UCB1 algorithm, for all E [T], provided that V(I,1) S Klogt + K the following holds:
E
F.2 min ft TE[1,(]
V(,x),
K logt
K + + Vi14i
-R)
Proof. We adapt the standard UCB1 analysis to account for a limited amount of non-stationarity VI1.q-- Concretely, treat the environment as "approximately stationary" up total variation VIL. in the optimal arm 's reward. Recall that in purely stationary K-armed bandit, UCB1 maintains an estimate μu of each arm's mean reward plus a confidence bonus CB² so that the upper confidence bound is
F = 1 + CB
A common choice is
2 log
CB*
n
22

---

where n is the number of times arm & has been pulled up to time т. Then the standard analysis (cf. shows that, for large T,
K log
0 )
and Σ (1t Re) S
T
assuming a stationary reward distribution with mean μ² for each arm Now suppose the reward distribution changes slowly, that the optimal reward ft max f4 may shift but the total variation on [1, #] is bounded by Vn..j. In particular, f7 can differ from ft by at most Ei=r |52+1 We incorporate this into the UCB analysis:
fžl Vp.4
Lower bounding fr. Let k" be the best arm at some time [1, By stationarity analysis up to time T,
1 is valid upper confidence bound for μ Then
S p S Fe
(since the UCB1 algorithm's bound only grows over time).
Meanwhile, f 2 8z -V14 by the definition of variation. Combining, ft 2 f 2 ft + Vi,.j. or equivalently
fe 2 min fi - V(1x)- rE]1,]]
This proves the first inequality in the lemma.
Bounding the per-round difference (Jr Rt). In standard UCB we know that, up to 7 the difference between the UCB and actual reward is controlled if the environment is effectively stationary in [1, Since we allow total variation VI.. the environment can shift the actual reward R, away from the estimated bound by at most V1.4]- Summation from to yields
V KKlgg K
EG.- R+)
Σ
K Klogt + K
4) + Vp.4j.
Dividing by t proves
1 Σ -f)
K Klogt
K +
+ V(ia)-
t
This completes the proof.
From this, we see that the UCB1 algorithm is capable of handling near-stationary environments. In contrast, Algorithm follows a probabilistic scheduling mechanism that deploys multi-scale instances. Our goal is that, despite its more complex structure, retains the same fundamental property-namely. the ability to handle ntar-stationary environments effectively. When addressing the non-stationary bandit problem (which, restricted to query rounds only, reduces to a standard non-stationary bandit setting), we adopt structure similar to the MASTER algorithm [. Although the introduction baseline query allocation modifies the structure, the core analytical techniques
remain comparable. By leveraging similar proof strategy (Lemma 3 in 37) ), establish that our framework achieves the same theoretical guarantees.
Within each phase, there are different instances In,m.r, where use Sn,m.r to denote the set of all active rounds corresponding to each instance, parameterized by n and m. To distinguish between query rounds and non-query rounds, let Squery = Sn,m,r n Squery represent the set of all active query rounds in instance In,m.r, and let Shon = S Sn,m.r O. Snoon-query denote the set of all active non-query rounds in In,m.r- Then we have the following result:
Lemma A.4. Let ît log, T'L,, p(t) = Klogt + and p(t) 6n log(T/8))(()) Algori thm 1
with imput n S log, T guarantees the following: for any instance In..m.7 that A Aloori thm Imain- tains and any round index f. E Squery let [start,n] denote the total variation over the round set
23

---

Istart, t| n S As long as Viuery
[start,s) S p((S n,
)). we have, with probability at least 1 - T.
9t 2 min f² Viueery [start,)]'
rElstart
0 R+) S M(1) + n Viuuery
[stard,]]
T=start
Apart from the structural differences in each block, if we consider only the query rounds allocated by the baseline allocation, the HY QUE algorithm and the MASTER algorithm exhibit no fundamental differences. This aligns with our intuition that, for the CONFEE-NSMABB problem, when B = T, the problem effectively reduces the non-stationary bandits setting. Consequently, for R we can derive a near-optimal regret bound for the non-stationary bandits problem as a function of B rather than T. Therefore, the regret corresponding query rounds can be bounded as:
Ry S 6 (K//v 1/3 B2/3).
A.2.3 Proof of Lemma 4.10
Building upon Lemma 4.9 and we now consider Ro which arises from inaccuracies in the algorithm's s decision- decision-making making. In Algorithm 2 due to potential restarts, multiple phases p = 2, ... may exist. Thus, we obtain:
R
RT
Σ
E
max
Σ
E
Σ
RS
KE(K]
S
BES.-1
Σ
Σ
E
max KE(K
E
Squary
R
E
Σ
R
P. LESn,m,
Steey
gumr m.
Shon-query Snmi
Σ
E
max KE[K]
Σ
R
E
Σ
R
S
p.n.m
EEST
LEST
E
Σ
R
E
Σ
R
LESu,m,
2 Su00-query
Shhnngr Sn,m.7
Rauar
Σ
E
Σ
R
E
Σ SEN--OO
R
Squery|
P.n.m
LESH
27
δ (K1/V/2/3 B2/3)
+
B2/3" VT
B
σ T K2/3 V2/3
B1/3
Explanation of the derivation: The first line defines Rep by summing. over every non-query round, the gap between an idealized "best average reward" (which could have been inferred from previous query feedback) and the actual reward collected. The second line refines this sum by grouping the non- query rounds across different phases and different multi-scal instances (n, m, T). The third line [Stiqquay]
factors out the ratio in form that highlights how each non-query round effectively "relies" on the estimates from the query segment. The fourth line then bounds the difference in these sums by relating max, Σ, R& Σ, R to the query regret R multiplied by factor reflecting the non-query to query ratio. In addition, it isolates a leftover term that accounts for how the environment might have shifted between the query and non-query parts. The fifth line substitutes known estimates for Riueery and applics prior Lemma 4.9 and Remark A.2 yielding main contributions the order of _ k1//1,11/ B2/3 and
rewriting the maximum average reward max, Eiesyey R /|STtm,
Vr. The sixth and final line combines these two contributions with B w(T3/4) and
13/3
V
K VB.

---

A.2.4 Proof of Lemma
Finally, we analyze the regret due to environmental drift. As a result, there are at least vB non-query segments, and each non-query segment has a length of at most (b 1)vB. Consequently, the regret due to environmental drift is bounded by:
R
drift RT
Σ
Σ
E
max
kE(K]
DES.-1
R Squery
Σ
Σ
Hi E
max KE[K
Σ
p,n,m IES
BES.....
T T.K1/3. V
T
VT V
B2/3
B1/3
Explanation of the derivation: the first line, we define the "drift" component R4 by summing, over each non-query round t Suon-query, the gap between μ4 (the true best mean reward at time and the proxy-based estimate that was used. In the second line, we reorganize this summation by phases p and multi-scall instance indices (n, m. r), noting that non-query rounds in each instance In.m, rely on historical query information Sp,m,, Finally, in the thind line, we invoke two key facts: (i) the environment's drift between query and non-query segments maximal length of a non-query interval, thus contributing at most R273 Vr additional regret, and
be controlled by bounding the
(ii) under = (T3/4) and Vr < 'V',B, this quantity falls within Ö(" K /3/3//// Hence, even if the environment may change during non-query intervals, the total extra cost is dominated by the same main order of regret.
///3
A.2.5 Total Regret
Combining the bounds for R7 and Rdrin we obtain:
T T-K3/3 v 1/3
Ry
query <ō
B1/3
Substituting the bound for Ryuery and combining the bounds for R.q. and R. Bea-quer the total regret given by:
T K1/3 1/3
Rr = R.q.ery + RTT
Bon-query
<
B1/3
This has been established under baseline query allocation alone. We now show that our on-demand mechanism-whice may convert certain non-query rounds into query rounds (or vice versa) whenever the actual usage lags behind (or overshoots) an approximate linear pace B do-osss not inflate this overall regret bound. Let BAQUE be the set of query rounds chosen by the baseline allocation, and let QoQQi denote the additional query rounds triggered by on- on-demand scheduling. By design, on- demand scheduling only triggers new queries the total used so far is below LB T miimmmm/V Min[[B,TT' T-t).
Consequently, the number of such converted rounds does not exceed B/2, ensuring that: QUDQUE < B/2. Now consider two scenarios:
Scenario A (Baseline only). The algorithm uses only the baseline queries RAQUE incurring k3/S////
regret Ö (
B173
Scenario (Baseline On-deeandd, The algorithm has QBAQUE U godQue as query rounds. Suppose it ends up with R. OuQue total regret.
Each newly allocated query round might cause partial suboptimal pulls, but bounding analy- sis based on UCB1 analysis shows that O additional query steps can only add at most / [QDQQE
K log T' to the query query-phase regret. Because @ouQue < B/2, this is at most
25

---

the order of the baseline query regret RT or smaller. Meanwhile, those same converted rounds lower the non-query portion; effectivelyy the error from stale estimates in scenario should be that in scenario A.
Consequently, even if this conversion incurs additional regret, the difference is at most constant factor times R4 which does not affect the overall order of the regret bound.
B Algorithm for Known Variation Setting
B.1 The Rexp3B Algorithm
Algorithm 3 Rexp3B: Rexp3 algorithm with Budgeted feedback
1: Inputs: Feedback budget B, time horizon T, variation budget VT, and number of arms K.
2: Set Ar T-K log 1/5
Ag
Ar and min 1. (e- 1)
log K
B¹/3. V
3: Initialize / for all E [K].
4: jorj= 1, ..... [T/ do
5: Set the current batch's start time t = (j- 1)Ar.
6: for t 7 + 1,.... min (T, + } do
7:
For each E [K], set
w
p =
w
K
8:
Draw an arm k E [K] according to the distribution Receive reward R, For K', set X.K' RK /pt and for any + k' set X
{ K
1k=1
9:
11:
For all ls E [K], update:
xx* K
wf+1 w/ exp
12:
for + AB + +l....... min (T, + Ar} do
13:
Select uniformly at random from the set faye t' = 1,...,, AB)
The Rexp3B algorithm operates by dividing the time horizon T into discrete batches, dynamically adjusting its query strategy based on the allocated feedback budget and the known variation budget Vz. Initially, the time horizon T is partitioned into batches of size Ay, ensuring a balanced allocation of resources across time. Within each batch, the algorithm allocates subset of A steps to query phase. During this phase, employs the EXP3 strategy to select arms and actively request feedback, prioritizing arms with higher estimated rewards by assigning them greater selection probabilities. After the query phase, the algorithm transitions to a non-query phase for the remaining Ar AB steps of the batch. In this phase, the algorithm selects arms without requesting additional feedback, relying instead on the information gathered during the query phase. Specifically, it uniformly randomly selects an arm from the of arms chosen during the current batch's 's query phase. practice. this sampling strategy could be replaced by others, such as greedily selecting the arm with the highest weight from the query phase.
To achieve the desired regret bounds, the algorithm parameters are carefully configured, including the batch size Ar, the learning rate y, and the number of query steps per batch An. These parameter settings enable Rexp3B to balance query and non-query steps while strictly adhering to the feedback budget. Furthermore, the algorithm accommodates the non-stationary nature of the environment by adjusting its behavior in accordance with the known variation budget Vr. As result, the Rexp3B algorithm is theoretically guaranteed to achieve the desired regret bounds, providing an effective solution for multi-armed bandit problems characterized by budgeted feedback and non-stationary rewards.
Theorem B.1 (Regret Bound for Rexp3B). Under the known variation setting with variation Vr [K-1 -- the Rexp3B algorithm uses at most B query rounds and satisfies the following regret
26

---

bound:
k2/ayg// B1/3
Rr S Ö
B.2
Regret Analysis (Proof of Theorem B.1
As discussed in Section 4.1.2 the regret Ry can be expressed as:
RT= RT + RT Ruaqqurryy
-RT RT + RT
The term R7t represents the regret incurred during the time steps when the algorithm actively queries for feedback. The term Ri quoon-ueryy captures the regret incurred when the algorithm decides not query for feedback. This component can be further decomposed into subcomponents, The first, Ro arises from inaccuracies in the algorithm's decision-making when it relies on previously gathered information about the arms without further querying. The second subcomponent, RTTh. accounts for the regret caused by environmental changes, such as shifts in the reward distributions, that are not promptly detected due to the absence of feedback.
Stepl: Bounding R.T...
The term R.q.ery is the regret arising from the AB query rounds each batch. Fix 7 2 1, and VT E [K'1, K- We partition the time horizon T into a sequence of batches .i,...,7 Tm of size Âr each (except possibly the last batch). Let 7,meory denote the set of query rounds in batch T [I....,m) m... We decompose the regret Roary as:
quuory
Σ
Σ
Rs
Σ
Σ LIET
(1
- me)
Lte
(7)
Σ Σ IET,
Σ
R
E
Σ
R
E
Σ
Rs
kE[K]
KEEK] TET)
TE
LIET LIE
Ja.i
Here, J1,j is the expected loss associated with using single action over batch j. and J2.j is the expected regret relative to the best static action in batch j. Let Vj denote the total variation in expected rewards during batch
Vn = Σ max 1 - 11 IET,
RE(K]
We note that:
1 11l S Vi-
max kE
j=1
Let ky be arm with the best expected performance over Tieeryy
ky E arg max KE[K]
Σ
LEY
Then,
Σ
Hi
Σ
Pr
Σ
R
E
max RE(K]
Σ
R
KE[K]
TET pay
TET
IETT
For term J1,j, we have:
J1
Σ
-
max
Σ
R
S
Σ TET
(ut
k3
S
22V,AB.
(8)
KE[K]
1ET
LET
27

---

For term J2,j, using the standard regret bound for the EXP3 algorithm in adversarial settings, we
have:
J2 = E
max kelk]
Σ
R
E
Σ
Rs
- 22
1)A log K.
(9)
LET,
LETT
We substitute 8 and 9 into 7 and sum over all m
batches. This yields the total regret
incurred during all query rounds:
RT
2ve DIl-V Ank log 2V
f=1
AT +1) .2 +
2 VT.V.-
Step2:
Bounding RT
non-query
In the remaining ÂT Ag steps of each batch (denote them by T T.mon-quer)) the algorithm does not request feedback. The main concern here is that the environment might "drift" substantially in these non-query steps without being detected. We start with the term RT We have:
R
Rovor R.
E
max KE[K] SES:-1
Σ
E
R
S
LIE Stiooqqayyy
Rk
Σ
Σ
max KE(K]
Σ
ITquery
Σ
R
j=1 TET
LET T
T mon--ueery
max ke
Σ
R
E
Σ
R
EET
TET
J2
IT. non-query
+
query
Σ LET
Rr
E
Σ
m
AT AB
2
Vle 1)ABK log + V,AT
An
j=1
(e
1)K K
$ 2T
A2V,
A
Explanation of the derivation: We decompose the error term Re by initially defining (Line 1) the sum over non-query rounds of the difference between hypothetical "best average reward" inferred from prior query feedback and the actual total reward in those non-query rounds. We then reorganize this sum by batches 1,..., m (Line 2), where each batch has a query part 7, and non-query part T, non--uuury (Line 3). At this stage, the bracketed term J2., compares the "best possible reward sums" in query rounds the algorithm's 's chosen sums, bounded by the adversarial regret argument. Substituting known estimates yields the expression in Line 4, where the ratio Ar-Ag reflects how many non-query rounds depend on each query segment, and V, captures environment
Ag
28

---

variation within that batch. Then we consider RT
R
R
Σ
14
Σ
E
kEIKi
S
BES.-1
R
Σ
14
E
[E(K]
BET Quiaqurr
2
(Ar - AB)
j=1
VT VT. AT
2
+1 (AT- - AB)
AT
T
VT
2 (T + AT)
S <VVAT.
T
Explanation of the derivation: We similarly define the drift term R4 (Line 1) as the gap between the true best mean reward jd in each non-query round and the "best average feedback" constructed from query data. We again partition by batches (Line 2) and argue (Line 3) that each batch's 's drift can be bounded by the product of non-query length (AT AB) and local measure of variation V,, Accumulating over batches and simplifying (Line 6-6) shows that the drift contribution is also capped, typically at (VV ÅT).
Therefore, the regret during the exploitation phase can be bounded as:
(e 1)K log K
RT
query
RT + Rdrin S 6V.AT + 27,
A
Step3: Combining and Minimizing Over AT
The total regret could be bounded
R₁ Rquarry RT Ronon-uurry non-query
(Tr T
T +1
(e 1) log
2V -V K + 24 AV 2T
=
Ar
A B
By choosing the batch size Ar
AT T (K log K)2/3
B1/3 2/2/3
we minimize the cumulative regret to:
T (K log K) 1/3, 1/3
R S
B1/3
C Extensions
In this section, we show that our framework naturally accommodates more general non-stationary learning problems, including contextual bandits, linear bandits, and certain reinforcement learning (RL) scenarios. Concretely, one only needs to replace the base algorithm (UCB1 in default BAQUE) with corresponding algorithm ALG suited to the target setting (e.g., a linear bandit algorithm or contextual bandit procedure).
C.1 Extended Baseline Allocation: BAQUE with ALG
Algorithm I explanation. Compared with Algorithm D in Section I. we replace UCB1 by generic
base algorithm ALG. The p(.) and p(2") criteria follow from Assumption C.2 ensuring the instance
p[2m)

---

Algorithm 4 Extended BAQUE for General Base Algorithm ALG
Require: Query budget ratio b [27) B3. time-scale parameter non-increasing function p(-). for 7 = 0.
2b ,...,,
do
2:
for m n, nt 1, . do
3:
if r is multiple of 2 then
4:
With probability A12")
initiate a new instance In,,, spanning rounds [T + 1,
p(2"))
b 2m);
5: for each instance In.m.r do
6:
Let Su,m,r be its active rounds;
7:
Query batch: For the first max(1, [ISm.m,r//b]] active rounds, run ALG, collecting rewards
and updating the index Jt. which is fe in Assumption C.2
8: Non-query batch: In the remaining active rounds, pick arms according to their frequencies from query batch (no reward feedback).
scheduling probabilities remain consistent with the required non-stationarity measure V and error margin.
Remark C.1. Figure ! (carlier) remains unchanged: we still have multi-scale instances, each with query batch and non-query batch. Only the internal UCB1 logic is replaced by ALG, which might be, e.g., linear bandit algorithm contextual bandit procedure.
C.2 Extended Hybrid Framework: HYQUE with ALG
Algorithm 5 Extended HYQUE
1: Initialize: current round & <- 1, used queries B' 0.
2: for = 0, 1,... do
3: Set Ln <- 1 and initialize BAQUE for block [m, ln + b- 2 1] with the time-scale parameter
4:
while < fn 6- 2n do
5:
current instance has queries then
6:
Receive index and selected arm from BAQUE, play it, increment i and B'; Update BAQUE instance with the observed feedback;
7:
8:
Perform environmental change tests. If any test fails, restart phase from Line 2;
9:
else
10:
if B' B min (T/iB, 1) then
11:
Convert the current non-query round into a query round and jump to Line 6; No feedback requested: t + +.
12:
This is direct generalization of Algorithm Qn the main text, except we embed ALG inside BAQUE. The environment-change tests remain the same, or adapt to ALG's specific estimates of reward. The on-demand logic remains: if the total used queries B' is far below T we convert that round into query.
(gerithhm$eexplnnnaa
C.3 General Conditions on the Base Algorithm ALG
The following assumption from Wei and Luo (37 ensure that ALG yields upper confidence estimates for the optimal reward under bounded non-stationarity.
Assumption C.2 (37). ALG outputs an auxiliary quantity fc E [0, 1] at each time step t. There exists non-stationarity measure V and non-increatt non-increasing function p: [T] - R such that when running ALG, the following conditions hold for all E [T) provided that Vi.. $ p(t):
1.
min f Vi2.g re 1.
Σ (f. r+) s p(1) V/L.t--
30

---

This guarantees hold with probability at least 1 5 7 Additionally, p(t) 2 1 Vi non-decreasing function.
and C(t) tp(t) is
This assumption ensures that the base algorithm (ALG) provides reliable estimates of the optimal reward and maintains controlled discrepancy between the auxiliary outputs and the actual rewards. The function p(t) captures the uncertainty or error margin, which decreases over time.
Implication. Under Assumption C.2 the entire analysis remains the same, simply replacing UCB1 with ALG, and ensuring the scheduling probabilities scale via p(-) as indicated. This yields near- optimal dynamic regret for broader class of non-stationary settings, matching the idea of the MASTER algorithm [37] but now budgeted by B queries thanks to our hybrid query method.
D Proof of Theorem 5.1
We construct family of problem instances and analyze the regret that any algorithm must incur on these instances.
Step 1: Batching the Horizon and Constructing Reward Means
Partition the time horizon into m batches, each of size A (except possibly the last). Denote
T {t: (j 1)A + min
j j= 1,..,,,,m
We will choose A later to balance the terms in the lower bound. For small 0 < S 4 (also determined later), define family V of reward sequences such that:
n E 1 2 + + for all E [K], E [T];
In each batch Ty. exactly one "good" arm ky has mean 1 + s, while all others remain These means are constant within each batch (no within-batch variation).
The total variation over time for any E V is:
Te A
sup k
p
(m 1)e
Hence if we set
E E VTA T
A
then V" C V, ensuring all such sequences are valid under the variation budget Vr-
Step Single-Batch Analysis under Feedback Budget
In each batch T,. we analyze the expected regret under the constraint of the corresponding query budget By allocated to this batch. For any algorithm A, define:
(k) E (# times arm k is pulled in batch ;)]
(k) E times feedback arm is actually observed batch j)]
Because the total feedback across all batches is at most B, we have
Σ KE(K]
B[n)())] S BB
B S B.
5=1
We aim to lower bound the regret in each batch Ty. accounting for the limited feedback. Let v/ be an instance with all arms having mean 1. and let v/ differ only by giving arm ky a mean of ( + s) in batch j. Let P. and IP,, be the probability measures (over entire batch's observation process) under and v', respectively. The Kullback-Leibler divergence satisfies
(LPP,, P.,) s Ey [n](k,)] KL
1 2 4
31

---

Here ( 2 +)) = 2 for S By Pinsker's inequality,
[. Bnll Il v (T,, PP:),
where |l the maximum absolute value of f. Taking f = ny mi(kk) (kz), which is clearly most A in magnitude (the arm cannot be pulled more than A times in that batch), we get
(nbn)(())]] - E, [n, (ky))l
A v (LL & AE 2Bn
Then we have
(ng S EnIn [n) (ky)l Ae < 2 22
(10)
To further bound E (kg)): we use the following result:
Lemma D.1 (Efroni et al. [3].. Let 2, E R for some n 2 2, and assume that Ei= 24 S X and Ei=1 & Y. Then, for any E (1,2) and B 2 3a a-1 there exists an index & E [n] such that T& I and yk I @Y simultaneousty. n
Let 1. 15, na (1 and yı = Ev (n for [K]. Then,
Σ ok S A,
Σ kE[K]
yk Bj-
kE[K]
By Lemma
D.1 there exists an arm kj such that:
aA
5A
3
15Bj
Fk
yk,
S
K
4K
K
K
Substituting the above two terms into (10).
we have
5A
15B,
E (n,(r))
Aev
4K
K
Let R2 denote the expected regret in batch j. Under v/, the expected regret in batch is at least:
R2 e (A EV (k;)))
Therefore,
5A
30B;
5
30BB
RS ME A
A
As
EV
(11)
4K
K
4K
Step Summing Regret over m Batches
We have m = [T/A] batches in total. Summing
11 over j = 1,..., m yields:
5
30B;
Rr(A)
Σ
R
Ae
EV
4K
K
j=1
30BA
> (m
1)Ae
1
4K EV
(12)
KT
5
30BA
2
Te
2
4K
KT
We choose and A such that:
V1 A
30BA A
1
81
T
KT
8
Recall that E
V T
Substituting, we have:
V
30BA
1
T
KT
8"
32

---

Therefore,
KT
1/3
VA
VT
KT
1/3
K1/3/1//
A
1920V?B
T
T
1920V
19201/3B1/3
Since K 2, 5 4k
g. S0:
5
5
1
2
1
4K
8
8
We substitute these A, back into 12
Te R
K
K KV/VV///TT
1920 B/3
8 19201/// 1/
B1/3
KV/3/1/31 B1/3
This shows that any algorithm A limited to B queries suffers Ω case, completing the proof.
regret in the worst
E Experiment Results
In this section, compare different query allocation strategies. We base our comparison on the Rexp3B-Sampl. algorithm (Appendix [B), which assumes a known variation budget Vz, as its structure is more easily adapted to accommodate different allocation policies.
Environments. We evaluate all algorithms across three distinct non-stationary environments. In all settings, the time horizon is set T 200, 000, the number of arms is K 5, and all non- optimal arms provide a baseline reward of /luue = 0.5. First, we use a standard Piecewise Stationary environment, where the time horizon is divided into 40 equal epochs. In each epoch, single optimal arm's 's reward elevated, and this optimal arm cycles deterministically at each change point. This setting, with a query budget of B 100, 000 and total variation V 20. We also test Random Changepoints environment with randomly distributed change points, and Low Query Budget environment where the budget is reduced to B 20, 000. All are executed machine equipped with a 12th Gen Intel(R) Core(TM) 29002X processor.
Baselines. We compare our main algorithm, Rexp3B-Sample with frequency-basel sampling in non-query phase, against four baselines. The Bexp3B-Grreed baseline follows the same batched structure but commits line also uses batched approach but distributes its queries uniformly within each batch. The Explore- Explore-Then--e Then-Commis (ETC) baseline classic strategy that expends its entire query budget in an initial exploration phase before committing to fixed policy. Finally, the Random bascline selects arms uniformly random, serving as performance lower bound.
purely greedy strategy non-query phase. The Uniform Query base-
Results. Figure 3 presents the cumulative regret of all algorithms across the three environments. Across all settings, the Sexp3B-Greedy strategy consistently achieves the best performance. In contrast, Uniform Query performs poorly, due to its delayed exploration within each batch. The Bexp3B-Sampl. algorithm delivers middle-ground performance, appearing conservative these non-adversarial environments. The Explore wwweooreee---ooeeee its initial query phase but degrades to random-like performance after its budget is exhausted.
(ETC) strategy performs well during
33

---

Recoll Sample
Aopill-Carpe Jedarr Qpelity Explor-Cavren
Aopill- Jidaar Explors-Crven
Dneornckeryy Eiztne-Comm
Cumuebbve Royne
Damu Regne
8.00
0.00
0.25
Time
400
Time
400
Piecewise stationary.
(b) Random changepoints.
(c) Lowe query budget.
Figure 3: Regret with different non-statioanry environments.
34


Reviews:
[{"review_id": "S8LqezgYth", "reviewer": "Reviewer_9p5b", "summary": "This paper studies non-stationary multi-armed bandits when the learner has a limited querying budget. The model is inspired by the well-known paper by Besbes et al. 2014, where the goal is to maintain a regret guarantee that is parameterized by how much the instance is “non-stationary”. The tweak with respect to this well-studied model is that the learner can only observe the current loss it experiences at most $B_T$ times. Note, in a stationary environment, there is no reason to delay issuing such queries (as the distributions do not change), while in the adversarial setting — where the benchmark is the best fixed action — a valid strategy consists in spreading the queries uniformly.", "questions": "If we were to drop the requirement that $V_T$ is unknown, would the algorithm by Besbes et al, combined with uniform querying (i.e., at each time step the learner issues a query with probability $B_T/T$) provide the same result? If this is the case, maybe it is worth mentioning, so that it is clear that the difficulty lies in spreading the querying budget between the parallel algorithms.", "limitations": "nothing to add here", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Providing non-trivial regret guarantees against the best dynamic strategy in online learning is a hard and interesting problem. Moreover, the study of “label-efficient” (i.e., that issues a sublinear number of queries) algorithms is also well motivated and has been studied extensively (see, for instance Minimizing Regret with Label Efficient Prediction, Cesa-Bianchi, Lugosi, and Stoltz, COLT 04).\n\nThe authors provide matching upper and lower bounds, the algorithm is clearly presented, and the technical contribution is non-trivial. At a high level, the approach consists of running in parallel multiple algorithms, each one is tailored to a specific non-stationarity in the reward sequences. There is an extra difficulty given by the fact that the algorithm has to partition the query budget between these parallel algorithms.", "was_revised": true, "final_justification": "I confirm my initial rating", "rebuttal": "Thank you very much for your constructive comments, as well as giving the positive rating of our work. Here we would like to address the reviewer's concerns as follows:\n\n>**Question #1: If we were to drop the requirement that $V_T$ is unknown, would the algorithm by Besbes et al, combined with uniform querying (i.e., at each time step the learner issues a query with probability $B/T$) provide the same result? If this is the case, maybe it is worth mentioning, so that it is clear that the difficulty lies in spreading the querying budget between the parallel algorithms.**\n\n**Our Response:** Thank you for this insightful question, which helps clarify both the core challenges of our setting and our contributions.\nWhile the strategy of combining the algorithm of Besbes et al. with uniform querying may appear reasonable, it would not achieve the optimal regret, even if the total variation $V_T$ were known in advance.\nThe sub-optimality is evident in both stationary and non-stationary environments.\n\n*   **Stationary Case ($V_T=0$):**\n    The optimal algorithm adopts an explore-first strategy that exhausts the entire query budget in the first $B$ rounds, and subsequently achieves a regret of $\\mathcal{O}(T\\sqrt{K/B})$.\n    In contrast, uniform querying would sparsely distribute these $B$ queries over the entire horizon $T$. This means the learner would continue to make decisions based on highly uncertain estimates for a prolonged period, leading to significantly higher regret. It fundamentally fails to balance exploration and exploitation under a budget.\n\n*   **Non-Stationary Case ($V_T > 0$):**\n    In the non-stationary setting, the trade-off becomes more complex. While using all queries upfront is no longer optimal, a uniform querying policy remains an inefficient solution because it cannot perform the **adaptive, dynamic budget management** that is required. An effective strategy must achieve the following:\n\n    *   **Responsiveness to Environmental Volatility:** Environmental changes can be both rapid and gradual. An optimal policy must therefore be able to detect and adapt to different scales of change. It should increase its query frequency to track rapid shifts, while also detecting slower, long-term drifts and conserving its budget during stable phases to avoid premature exhaustion. A uniform policy, with its fixed rate, lacks this dynamic capability entirely. In contrast, our algorithm is designed to ensure detection capabilities across these different types of environmental changes.\n\n    *   **Balanced Query Use:** An intelligent agent should allocate its scarce queries when they are most valuable. A uniform policy queries at a fixed rate, wasting its budget during periods of high certainty and failing to provide crucial information during moments of high ambiguity. Our approach, by contrast, links querying decisions to the state of uncertainty, thereby preventing the premature or wasteful exhaustion of the budget.\n\n    *   **Strategic Budget Pacing:** A uniform policy naively spreads the budget, which is an inefficient, open-loop strategy. Our adaptive approach, in contrast, strategically paces its budget. It might spend more cautiously at the beginning to ensure it has queries left to handle potential changes late in the horizon, while also being ready to spend aggressively if the environment proves highly volatile early on."}, {"review_id": "p1MvXMGfpZ", "reviewer": "Reviewer_nnUf", "summary": "This paper addresses the problem of non-stationary multi-armed bandits under a constrained feedback budget. The authors introduce a new framework, CONFEE-NSMAB, where the constrained feedback is in the form of the total number of times it can query for reward. The authors propose an algorithm for this setting and analyze its regret. The authors also show a lower bound for the problem.", "questions": "Aside from the questions mentioned in the comments above, can the authors comment on (1) the computational complexity of the proposed algorithm, (2) the connection between NSMAB and restless multi-armed bandits [1], and (3) if their algorithm can handle them?\n\n[1] Liu, Haoyang, Keqin Liu, and Qing Zhao. \"Learning in a changing world: Restless multi-armed bandit with unknown dynamics.\" IEEE Transactions on Information Theory 59.3 (2012): 1902-1916.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is generally well-written and easy to follow. The method is motivated well and described clearly. \n\nThe paper studies an important problem that have real-world relevance. It would be helpful if the authors can comment on how non-stationary bandits are applied in the real world v.s. considering it as a full RL problem.\n\nI am concerned about the modeling assumption of a finite variation budget V_T. It would be helpful if the authors can comment on its effect using a concrete real-world example. The algorithm uses a query budget ratio b = ceil(2T/B). It would be helpful if the authors can provide more intuition on the selection of this value. Additionally, more detailed comments on the computational complexity would strengthen the paper. Otherwise the algorithm shows novelty, especially the query allocation mechanism. The technical proofs appear to be sound. \n\nWhile the paper is theory in nature, some comments on the empirical performance would be useful.", "was_revised": true, "final_justification": "The author provided detailed and satisfactory response to my comments. I will keep my rating for now.", "rebuttal": "Thank you very much for your constructive comments, as well as giving the positive rating of our work. Here we would like to address the reviewer's concerns as follows:\n\n>**Weakness #1: It would be helpful if the authors can comment on how non-stationary bandits are applied in the real world v.s. considering it as a full RL problem.**\n\n**Our Response:** Whether to model the problem as a non-stationary bandit or a full RL task hinges on state-action coupling: if actions do not (or only negligibly) influence future reward distributions, a bandit abstraction is both sufficient and far more sample-efficient than learning a full Markov Decision Process (MDP) in reinforcement learning.\n\n**Practice.** Non-stationary bandits is well-motivated by many real-world applications. For example:\n*   **Recommender Systems and Ad Placement:** The popularity of news articles, products, or advertisements naturally fluctuates over time due to external influences such as trending topics, seasonal demand, or user fatigue.\n*   **A/B/n Testing in Marketing:** The effectiveness of website designs, pricing strategies, or ad creatives can degrade over time. A non-stationary bandit can adaptively allocate traffic to the currently best-performing option while remaining sensitive to such changes.\n\n**When RL is needed.** If actions **do** change the state (robotics, game playing, inventory control), an MDP is necessary.\n\nIn summary, non-stationary bandits and full reinforcement learning are not competing paradigms, but rather complementary tools designed for fundamentally different problem classes. Our work focuses on the important and widely applicable setting (e.g., ads, content ranking, A/B/n tests) where the environment changes autonomously over time (exogenous shifts dominate).\nWe show how to handle these shifts and a strict query budget, a regime where full RL would add complexity without benefit. We will add this clarification and citations in the final version.\n\n>**Weakness #2: I am concerned about the modeling assumption of a finite variation budget $V_T$. It would be helpful if the authors can comment on its effect using a concrete real-world example.**\n\n**Our Response:** The \"finite\" assumption is mild: for any bounded reward process observed over a finite horizon $T$, the total $\\ell_\\infty$ variation $ \\sum_{t=1}^{T-1} \\sup_{k\\in [K]} \\bigl|\\mu_{t+1}^k - \\mu_{t}^k\\bigr|$ is *always* finite. Our theory merely parameterizes performance in that quantity.\n\n**Practical scale.**\nFor instance, in a **clothing-recommendation platform** with thousands of Stock Keeping Unit (SKUs), performance metrics like click-through rates often exhibit slow, seasonal changes. A typical change might be on the order of $\\approx 0.02$ per SKU per season, leading to a small annual variation budget, e.g., $V_T \\approx 0.08$. In contrast, a **breaking-news feed** during a major event like the 2024 U.S. election is far more volatile. Per-topic Click-Through Rate (CTR) can swing by as much as 0.4 every hour, potentially yielding a total variation $V_T \\approx 150$ in just one week.\nBoth are plausible, finite values, yet they differ by three orders of magnitude. Our regret bound is designed to handle this diversity, as it automatically interpolates between these extremes through its $V_T^{1/3}$ dependency.\n\n**Necessity.** If $V_T$ were allowed to grow arbitrarily fast (e.g., adversarially reset each round so $V_T=\\Theta(T)$), sub-linear regret is information-theoretically impossible—one must query every round. Bounding $V_T$ is therefore standard (Besbes et al., 2014) and delineates the learnable regime.\n\n**Monitoring in practice.** Platforms typically track moving-window reward drift; the cumulative sum of detected shifts offers an online estimate of $V_T$, letting practitioners gauge whether the theoretical assumptions hold.\n\n>**Weakness #3: The algorithm uses a query budget ratio b = ceil(2T/B). It would be helpful if the authors can provide more intuition on the selection of this value.**\n\n**Our Response:**\nIf we ignore other considerations, the query budget ratio should ideally be set to $T/B$, which evenly allocates the query budget across all instances. However, in a non-stationary environment, any detected change point triggers a restart of all current instances. This leads to a disproportionately higher consumption of queries. Therefore, the query budget ratio must be designed more conservatively to account for such events.\nAs demonstrated in Lemma 4.6, allocating a $1/b$ fraction of rounds for queries within each block ensures that, even in the worst-case scenario, the overall proportion of query rounds remains bounded by $B/T$. **This step is critical for establishing that the total number of query rounds over the entire horizon $T$ does not exceed the budget $B$, as shown in Lemma 4.7.** Choosing a smaller allocation might lead to underutilization of the query budget, resulting in intervals with insufficient queries to yield meaningful information. Conversely, selecting a larger allocation risks prematurely exhausting the query budget. Thus, the choice of $b$ effectively balances these concerns and is integral to the correctness and efficiency of the algorithm.\n\n>**Weakness #4, and Question #1: the computational complexity of the proposed algorithm**\n\n**Our Response:** The overall computational complexity of our algorithm is primarily determined by the complexity of the base bandit algorithm used within each instance. For example, in our paper, we instantiate the base algorithm as UCB1, which incurs a per-round time complexity of $\\mathcal{O}(K)$ due to the need to compute and compare the UCB indices of all $K$ arms.\nApart from this, all other operations in our framework have amortized constant time complexity per round. Therefore, the total time complexity of our algorithm is $\\mathcal{O}(B K + T)$. This complexity is standard in the bandit literature and aligns with the computational guarantees of most classical algorithms.\n\n>**Questions #2 and #3: the connection between NSMAB and restless multi-armed bandits, and if their algorithm in restless multi-armed bandits can handle them?**\n\n**Our Response:**\nWe appreciate the reviewer for raising RMAB. Although “restless multi-armed bandits” (RMAB) share the word bandit with our problem, the two models address fundamentally different settings. In our non-stationary MAB each arm is *stateless*: its mean reward can drift over time, but that drift is entirely exogenous and unaffected by the learner’s actions. The agent’s challenge is simply to track those drifting means, deciding—under a strict global query budget $B$—when to observe rewards to minimize dynamic regret. An RMAB arm, in contrast, is *stateful*, *i.e.*, is a full Markov decision process (MDP) whose state evolves according to action-dependent transition probabilities; whether the learner plays or rests the arm actively changes its future reward distribution. Consequently RMAB algorithms rely on observing the state every time an arm is activated, estimating or assuming transition kernels, and optimizing long-term discounted reward, not adversarial regret. Because they require unrestricted feedback and exploit state-transition structure absent from our model, RMAB techniques cannot be applied to the constrained-feedback, stateless, exogenously drifting bandit setting studied in this paper."}, {"review_id": "5BzwhfN3sZ", "reviewer": "Reviewer_E74N", "summary": "The authors consider the non-stationary multi-armed bandit problem with an observation budget of $B$ total observations. They design an algorithm which guarantees a dynamic regret bound of $\\widetilde O \\left( K^{1/3} V_T^{1/3} T/B^{1/3} \\right)$ where $V_T$ is the total variation, or the degree of non-stationarity of the environment, and moreover their algorithm does not require prior knowledge of $V_T$. The authors also prove a matching lower bound showing that their algorithm is optimal up to logarithmic factors. The suggested algorithm exhibits a balance between tracking the non-stationarity of the environment while maintaining a low amount of queries in order to not exceed the total budget.", "questions": "I refer the authors to my previous point under the \"Weaknesses\" section. To summarize, my question is which of the two versions of Theorem 4.1 is the correct version, and whatever the answer, why is such an assumption necessary, that is, where is it used in the proof.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n* The problem of non-stationary MAB with limited observations is interesting and well-motivated, and this seems to be the first work which combines the two variants.\n* The authors support the optimality of their results by exhibiting a matching lower bound.\n* The analysis seems nontrivial, and the authors clearly explain the need of a delicate balance between tracking the changes in the environment while simultaneously using a small number of queries.\n\nWeaknesses:\n\n* There seems to be a discrepancy between the two versions of the statement of Theorem 4.1 - one as presented in the main submission and another in the attached supplementary material. The two versions differ in the regime under which the regret bound holds - in the main submission the authors claim their bound holds as long as $B = \\Omega(T^{2/3})$, and in the supplementary version they claim that it holds as long as $B = \\omega(T^{3/4})$. I am not sure which version is the intended final version. If it the second version, the authors need to be absolutely clear about it as it implies that the main statement as presented in the submission is technically unsound. Even assuming the correct regime is when $B = \\Omega(T^{2/3})$, it still seems to me that this assumption may not be necessary, as the bound itself seems to yield nontrivial dependence on $T$ whenever $B = \\omega(1)$ with respect to $T$. I ask that the authors address this issue, as their response could highly affect my overall rating.", "was_revised": true, "final_justification": "After reading the author's rebuttal, I understand that the correct version of the main result is the one in the supplementary material. As the authors properly explained why the assumption on the budget is needed for their algorithm and analysis, my main concern was alleviated and I increased my score accordingly.", "rebuttal": "Thank you for your constructive comments as well as giving the positive rating of our work. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper.\n\n>**Weakness #1, Question #1: There seems to be a discrepancy between the two versions of the statement of Theorem 4.1 - one as presented in the main submission and another in the attached supplementary material ... this assumption may not be necessary, as the bound itself seems to yield nontrivial dependence on whenever $B = \\omega(1)$ with respect to $T$.**\n\n**Our Response:** Thank you for pointing this out. The discrepancy is **a typesetting mistake** introduced during final formatting: the main PDF inadvertently retained an earlier draft of Theorem 4.1, whereas **the supplementary file (including the main paper + references + appendices) contains the correct, fully proved statement**. The supplementary version is the one we prove.\nBelow we clarify from several perspectives:\n\n1.  **Correct Statement:**\n\n    **Theorem 4.1** (supplementary version). For ConFee-nsMAB with $B = \\omega(T^{3/4})$ and an unknown variation satisfying $V_T \\in [K^{-1}, K^{-1}\\sqrt{B}]$, our HyQue utilizes at most $B$ queries, and its regret is bounded with high probability as follows:\n    $$\n    \\mathcal{R}_T(\\text{HyQue}) \\leq \\tilde{\\mathcal{O}}\\left( \\frac{K^{1/3} V_T^{1/3} T}{B^{1/3}} \\right).\n    $$\n\n    We adopt the stronger condition $B = \\omega(T^{3/4})$ as stated in the supplementary file because it enables us to present a **clean and simple** high-probability guarantee $\\Pr(\\text{optimal regret})\\geq(1-\\exp(-T^{\\Omega(1)}))$. This condition facilitates a more interpretable and rigorous statement of our performance guarantees. In contrast, while setting $B = \\Omega(T^{2/3})$ can still ensure the valid regret guarantee, the corresponding probability is not available in a closed or interpretable form.\n\n2.  **Why is a lower bound on $B$ necessary?**\n\n    If $B$ is too small, sub-linear regret is information-theoretically impossible. Consider an environment that flips the identity of the best arm every $\\Theta(\\sqrt{T})$ rounds (total $\\approx \\sqrt{T}$ change points). Detecting each change with constant probability requires at least one query per segment, so any algorithm with $B=o(\\sqrt{T})$ necessarily misses $\\Omega(\\sqrt{T})$ change points and suffers $\\Omega(T)$ regret. This shows a requirement of $B\\gtrsim T^{1/2}$ is unavoidable in the worst case of highly non-stationary environments.\n\n3.  **Why does the probability expression become simpler when $B=\\omega(T^{3/4})$?**\n\n    In the preceding discussion, we provided a simple example to illustrate the necessity of a lower bound on $B$. That example involved an environment in which each change point induces an identical magnitude of change. In contrast, non-stationary bandit problems in general can involve a mixture of both abrupt and gradual changes. Therefore, any algorithm aiming to achieve optimal regret must ensure, with high probability, that it can detect all such changes. This necessitates a larger budget $B$.\n\n    Our algorithm maintains multiple parallel instances and must guard against failure across all of them. It needs to allocate sufficient queries to detect changes while also avoiding long sequences of non-query rounds. Such gaps hinder the detection of environmental shifts and can result in prolonged suboptimal performance. Since our algorithm employs randomized querying, the probability of encountering excessively long non-query segments decreases as $B$ increases. In this sense, a larger $B$ ensures that the randomized querying strategy provides adequate coverage across the entire time horizon.\n    It also facilitates a cleaner analysis, allowing us to derive an explicit expression for the algorithm’s success probability.\n    In our earlier version, we used a threshold of $B = \\Omega(T^{2/3})$, which was insufficient to guarantee a clean and strong high-probability bound such as $\\Pr(\\text{optimal regret}) \\geq 1 - \\exp(-T^{\\Omega(1)})$. This motivated a more thorough understanding of the problem. In the initial submission, we mistakenly did not update the corresponding assumption in Theorem 4.1, but fortunately, this was corrected in the supplementary version. **the supplementary file (including the main paper + references + appendices) ensures consistency with all other parts of the paper, as this assumption was in fact the only substantive difference.**\n\nIn summary, **Theorem 4.1 on Page 6 of the main paper in the supplementary version** already contains the complete and correct analysis. We will ensure that the final version is fully consistent with the supplementary material and will incorporate the relevant discussion regarding the choice of $B$."}, {"review_id": "ie0wTLwcjS", "reviewer": "Reviewer_ndtv", "summary": "This paper studies non-stationary multi-armed bandits (NSMAB) under the constrained feedback setting, where the reward feedback is limited. Given a query budget $B$,  the total number of reward feedback queries available to the agent over the time horizon $T$ is limited by a reward query budget $B$. This problem is named the constrained feedback in non-stationary multi-armed bandits (CONFEE-NSMAB)\nThere are two main focuses: \"How does the query budget constraint affect the problem difficulty?\" and \"Can we construct an algorithm that works well in CONFEE-NSMAB without knowing the degree of non-stationarity?\".\nThe authors introduced a nearly-optimal algorithm that does not require any knowledge of the degree of non-stationarity.", "questions": "- If we do not know anything about the non-stationarity, what is the point of \"detecting\" environmental changes? \n- Is deriving a distribution-dependent regret bound too hard for a non-stationary bandit?\n- Even when we know $V_{T}$, this algorithm can be applied to the non-stationary bandit. Isn't it necessary to compare the proposed algorithm with existing algorithms for cases when we know $V_{T}$? Conversely, I think it is valuable to compare the proposed algorithm with existing algorithms with $V_{T}=T$.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- They showed an algorithm that is nearly-optimal for CONFEE-NSMAB. Both upper and lower bounds of regret is provided.\n- Proof sketches are provided, which makes it more convincing.\n\n\nWeakness\n- There is no experiment, which makes it hard to evaluate the advantage of the proposed algorithm.\n- The authors did not provide any distribution-dependent regret.\n- If we do not know anything about the non-stationarity, what is the point of \"detecting\" environmental changes? This part is unclear.", "was_revised": true, "final_justification": "My concerns during the initial review—particularly regarding why a distribution-dependent bound was not provided—have been resolved. As for the numerical experiments, the authors mentioned that improved results will be included in the revised version, which I look forward to. For these reasons, I have raised my score by one point.", "rebuttal": "Thank you for your constructive comments. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper.\n\n>**Weakness #1: There is no experiment, which makes it hard to evaluate the advantage of the proposed algorithm.**\n\n**Our Response:** We appreciate the reviewer’s concern. Our submission is positioned as a theoretical paper: the main contribution is a new constrained–feedback model (CONFEE-NSMAB), a matching lower bound, and the first prior-free algorithm that attains this bound. In keeping with many closely related works whose primary contribution lies in theoretical analysis (e.g., Besbes et al. 2014; Wei and Luo 2021), we establish the performance guarantees of our algorithm entirely through rigorous proofs.\n\nNonetheless, we would like to provide numerical results in the final version, as we understand that they can be useful for readers to better understand the behavior of the algorithms. In the camera-ready version, we would therefore include a concise simulation study including but not limited to (i) Verify the regret rate: using synthetic environments with controllable $K, V_T, B$, we will plot $\\text{Regret}$ vs. $T$ and confirm the $\\tilde{\\mathcal{O}}(K^{1/3}V_T^{1/3}T/B^{1/3})$ scaling. (ii) Compare against baselines: We will test Besbes et al. with uniform querying, sliding-window UCB with a fixed horizon of $B$ queries, and a naive “explore-first” strategy. HYQUE consistently achieves lower regret—especially when $B \\ll T$ or $V_T$ is moderate—demonstrating the value of adaptive query pacing. (iii) Illustrate budget utilization: We will show that HYQUE respects the query budget by design, while baselines either under-use or prematurely exhaust $B$.\n\n>**Weakness #2 and Question #2: The authors did not provide any distribution-dependent regret. Is deriving a distribution-dependent regret bound too hard for a non-stationary bandit?**\n\n**Our Response:** We share the reviewer’s interest in distribution-dependent (or instance-dependent) guarantees. In the fully non-stationary setting we study, however, defining a “gap” analogous to the stationary $\\Delta_i$ is inherently problematic.\n\nIn the classic stationary MAB setting, each arm’s mean reward $\\mu_i$ is fixed, so the gap $\\Delta_i=\\mu^*-\\mu_i$ is constant throughout the horizon. Regret can then be expressed in an instance-dependent form such as $\\mathcal{O}(\\log T / \\Delta)$.\n\nBy contrast, in our non-stationary MAB setting, the means $\\mu_i(t)$ evolve over time (subject only to a global variation budget $V_T$). The instantaneous gap $\\Delta_i(t)=\\mu^*(t)-\\mu_i(t)$ may change arbitrarily often, so a single scalar no longer captures problem difficulty. The dominant cost now becomes *tracking* the shifting optimum rather than identifying it once.\n\nFor this reason, the field has standardized on **minimax** guarantees that scale with global measures of non-stationarity such as $V_T$ or the number of change points $\\Upsilon_T$ (e.g., Besbes et al.’14; Auer et al.’19; Wei & Luo ’21). Our result follows this paradigm, providing a regret bound that is optimal (up to logs) in $K, V_T, T$, and the query budget $B$.\n\n>**Weakness #3 and Question #1: If we do not know anything about the non-stationarity, what is the point of \"detecting\" environmental changes?**\n\n**Our Response:** Even without prior knowledge of how or when the environment will change, *online change detection* is crucial for keeping dynamic regret sublinear. The goal is not to predict future changes but to recognize—using only data observed so far—when historical estimates have become unreliable.\n\n-   **Why detect?** Dynamic regret comprises: (i) estimation error while an estimate is fresh, and (ii) staleness error accumulated if the learner keeps exploiting an arm after its mean reward has dropped. Without detection, the second term can grow linearly in the length of an unnoticed drift segment, overwhelming the bound. Prompt detection lets the algorithm discard stale statistics, restart estimation, and quickly recover near-optimal play.\n\n-   **How detect with no prior?** At each query round, we test whether recent empirical rewards are still inside the high-probability confidence region of the current model (Alg. 2, Lines 5–9). A statistically significant deviation—quantified by the data-driven radius $\\hat{\\rho}(\\cdot)$ (Lines 203-209)—triggers a restart. The test uses only observed rewards and standard concentration inequalities. It needs no parametric knowledge of the drift pattern.\n\nIn short, change detection is the mechanism that keeps a prior-free learner competitive under arbitrary, adversarial variation—it is about recognizing when the present diverges from the past, not forecasting the future.\n\n>**Question #3: Even when we know $V_T$, this algorithm can be applied to the non-stationary bandit. Isn't it necessary to compare the proposed algorithm with existing algorithms for cases when we know $V_T$? Conversely, I think it is valuable to compare the proposed algorithm with existing algorithms with $V_T = T$.**\n\n**Our Response:** We address both regimes (when $V_T$ is known and when $V_T=T$) in Appendix C and summarize below:\n\n**Known $V_T$ but query-budget constrained ($B<T$):**\n*   *Existing algorithms.* Prior work that exploits a known variation budget (e.g., Besbes et al.’14) assumes **full feedback** at every round. They cannot be applied under a strict query budget.\n*   *Our adaptation.* Appendix C shows that, once $V_T$ is revealed, HYQUE simplifies to a single-scale schedule and achieves the optimal $\\tilde{\\mathcal{O}}(K^{1/3} V_T^{1/3} T/B^{1/3})$ regret. To our knowledge, no other algorithm attains this optimal order under **limited feedback**, so a direct benchmark does not exist.\n\n**Extreme variation $V_T = T$:**\nWhen the environment can change by $\\mathcal{O}(1)$ every round, learning is information-theoretically impossible unless the learner queries almost every round. Even with full feedback the minimax regret is $\\Omega(T)$ (Besbes et al.’14).\nIf, on the other hand, the query budget also scales as $B=T$, HYQUE reduces to the standard non-stationary-bandit algorithm (equivalent to MASTER/Besbes) and recovers the optimal $\\tilde{\\mathcal{O}}(K^{1/3}T^{2/3})$ bound, as noted in Lines 223–224."}]

Author rebuttal:

Meta-review: This paper studies a non-stationary multi-armed bandit problem with a constrained feedback, where the number of queries is limited. The authors proposed an algorithm achieving the near-optimal dynamic regret, with tight dependence on the time horizon, number of queries, number of arms, and the total variation. In addition, the algorithm is agnostic to the knowledge of the total variation, which is an intriguing aspect. 

This paper is unanimously appreciated by all reviewers, due to the soundness in the theoretical framework and proposed algorithm, and tightness of the result. However, since the main algorithmic ideas come from existing work on non-stationary MAB and a black-box approach for achieving adaptation, the support is not with great enthusiasm. Therefore, I recommend to accept this paper as a poster.
Decision: Accept (poster)