Learning When to Update: A Near-Optimal Timing Bandit Approach

Qiulin Lin; Junyan Su; Liyuan Wang; Minghua Chen

cs.LGSep 29, 2026

Learning When to Update: A Near-Optimal Timing Bandit Approach

Authors: Qiulin Lin, Junyan Su, Liyuan Wang, Minghua Chen

Organizations: City University of Hong Kong,, Hong Kong, China · The Chinese University of Hong Kong (Shenzhen), China

Abstract

Systems operating in dynamic environments require timely updates to sustain performance. For resource-intensive systems such as machine learning models and digital twins, strategically timing updates is essential. Updating too frequently wastes resources, while updating too infrequently leads to costly performance degradation. The problem is particularly challenging when the system's degradation pattern is unknown a priori, as is common in new operating environments. We formalize this challenge as a novel timing bandit problem, where each arm represents a candidate update interval with a fixed update cost and an unknown, stochastic degradation cost. Three structural properties distinguish this setting from standard multi-armed bandits: selecting an interval commits the learner to multiple time slots before the next update; arm costs are composed of per-step degradation costs and a fixed update cost; and selecting a longer interval naturally reveals degradation at every intermediate step, providing consecutive feedback relevant to shorter intervals. By exploiting these structures, we develop Balanced Consecutive Arm Elimination (BCAE). BCAE achieves $\tilde{O}(\sqrt{T})$ regret, improving upon the $\tildeΩ(K\sqrt{T})$ regret of standard bandit algorithms in this setting, where $K$ is the number of candidate update intervals. We further propose an Optimism-Enhanced variant (OE-BCAE) that integrates lower-confidence-bound principles to improve empirical adaptivity while preserving the same regret order. Moreover, the regret bound achieved by our algorithms matches the theoretical lower bound up to logarithmic factors. Simulation results demonstrate that our algorithms achieve low regret and remain stable as both the number of arms and the update cost vary.

Figures & tables

MAB Problems	Timing Decisions	Consecutive Feedback	Arm Cost Composition	Regret
Standard, e.g., ( Lattimore and Szepesvári, 2020 )	✗	✗	✗	$\tilde{O}(\sqrt{KT})^{\star}$
One-Sided, e.g., ( Buccapatnam et al., 2018 ; Zhao and Chen, 2019 ; Li et al., 2021 )	✗	✓	✗	$\tilde{O}(\sqrt{T})^{\star}$
Side Info. ( Caron et al., 2012 )	✗	✓	✗	$\tilde{O}(\sqrt{KT})^{\dagger}$
Batch, e.g., ( Perchet et al., 2016 ; Gao et al., 2019 ; Cao et al., 2023 )	✓	✓	✗	$\tilde{O}(h(\cdot))^{\ddagger}{{}^{\star}}$
Timing Bandit (this work)	✓	✓	✓	$\tilde{O}(\sqrt{T})^{\star}$

Table 1. Comparison with related stochastic multi-armed bandit (MAB) problems.

Figure 1. An illustration of the evolution of model age and the associated degradation cost. At each slot, the model age increments by one if no update is performed and resets to one upon an update. It incurs a random degradation cost following the probability distribution $f_{a}$ at age $a$ .

Figure 2. An illustrative example of timing bandit. Suppose we first pull arm

2

. We will observe the degradation cost of age

1

and age

2

in the following two slots, from which we can derive feedback on arm

1

and arm

2

. The cost of such a pull includes the degradation cost and the update cost (at age

2

), the expectation of which equals

2\cdot\mu_{2}

(according to ( 8 )).

Figure 3. An illustrative example of BCAE in a super-round. Suppose there are 8 arms. Then, the anchor arms are

\{2,4,8\}

. Each square shape represents an observed sample; e.g., pulling arm 8, we have samples from all arms. The numbers represent the values of

i\cdot m_{i}

of the arms after each pull. We see that at the end of the super-round, the values of

i\cdot m_{i}

are within a factor of two of each other, which leads to a balanced confidence interval among all the arms.

Panel of Figure 4 — Figure 4. The performance of comparing algorithms under different parameters.

$\rho$	0	0.3	0.5	0.7	0.9
OE-BCAE ( $\times 10^{5}$ )	8.62	8.63	8.62	8.62	8.62

Table 2. Average regret of OE-BCAE versus the autocorrelation coefficient

\rho

Panel of Figure 5 — Figure 5. Empirical Evaluation on Real Frequency Trace.

Figure 6. Total-cost comparison of OE-BCAE , SA-LCB , and periodic baselines on the real frequency trace.

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 348 papers

Jun 8, 2026

Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees

We study a stochastic multi-armed bandit problem in which the set of available arms expands over time. This setting arises in sequential experimentation when new actions or treatments become available during an ongoing study, making regret against a single best arm in hindsight inappropriate. We instead evaluate performance relative to the best arm currently available, leading to a dynamic-regret criterion for arriving-arm environments. To address the resulting challenges of arrival information discrepancy (AID) and a drifting benchmark (DB), we propose UCB for Arriving Arms (UCB-AA), an elimination-based procedure with an aiding preliminary screening step for newly arrived arms before full competition with incumbent arms. We show that UCB-AA attains regret bounds that depend explicitly on the arrival process, achieves sublinear dynamic regret under regularity conditions on gap evolution, and admits an online extension for unknown horizons. Simulation results show that UCB-AA reduces wasted pulls and maintains a smaller active arm set while preserving competitive regret performance.

Deqi Zheng, Xiaoyang Xu, Yuhong Yang

Qiuzhen College, Tsinghua University · Yau Mathematical Sciences Center, Tsinghua University

Multi-Armed Bandits Dynamic Regret Minimization Sequential Decision Making UCB Algorithms

Ask PDF

Oct 19, 2026

Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs

Low reward variance reduces estimation cost, but does not eliminate monitoring of arms that may improve while unobserved. We refine the variance--variation tradeoff and characterize how both costs depend on supplied variance and variation budgets in bounded, non-stationary multi-armed bandits. Let

A

be the number of arms,

T

the horizon,

B

a bound on consecutive mean variation excluding the initial vector, and

Q

a bound on the sum of the largest per-round reward variances. For every admissible pair

Q,B

, the minimax expected dynamic regret is, within a single logarithmic factor,

\min\{T,\;A+\sqrt{AQ}+(AQBT)^{1/3} +\sqrt{AT}\min\{B,\sqrt B\}\}.

The deterministic boundary

Q=0

is characterized without logarithms. For small positive budgets, a safe calibration phase identifies a common interval containing all future means of surviving arms. Clipping observations to a wider interval reduces the cost of restarting a prior hybrid static-regret algorithm; an original-mean analytical reference controls its residuals without charging the variation of clipped means. Balancing clipping bias and monitoring closes the small-budget noisy regime. Fixed oblivious constructions give the matching lower bound. We also quantify adaptation costs: on a disclosed deterministic one-improvement family, a stationary-regret budget has a matching worst-case change-regret frontier, including a finite improvement pulse. This implies an

Ω((T/A)^{1/4})

loss when one policy competes with all supplied-budget deterministic oracle rates. The budget-free low-noise scheduling problem remains separate.

Xiaojin Zhang

School of Computer Science and Technology, Huazhong University of Science and Technology, China

Multi-Armed Bandits Non-Stationary Bandits Dynamic Regret Minimization Minimax Regret

Ask PDF

Mar 26, 2026

Parameter-Free Dynamic Regret for Unconstrained Linear Bandits

We study dynamic regret minimization in unconstrained adversarial linear bandit problems. In this setting, a learner must minimize the cumulative loss relative to an arbitrary sequence of comparators

\boldsymbol{u}_1,\ldots,\boldsymbol{u}_T

\mathbb{R}^d

, but receives only point-evaluation feedback on each round. We provide a simple approach to combining the guarantees of several bandit algorithms, allowing us to optimally adapt to the number of switches

S_T = \sum_t\mathbb{I}\{\boldsymbol{u}_t \neq \boldsymbol{u}_{t-1}\}

of an arbitrary comparator sequence. In particular, we provide the first algorithm for linear bandits achieving the optimal regret guarantee of order

\mathcal{O}\big(\sqrt{d(1+S_T) T}\big)

up to poly-logarithmic terms without prior knowledge of

S_T

, thus resolving a long-standing open problem.

Alberto Rumi, Andrew Jacobsen, Nicolò Cesa-Bianchi +1

Intesa Sanpaolo Innovation Center

Dynamic Regret Minimization Adversarial Bandits Multi-Armed Bandits

Ask PDF

Abstract

Multi-Armed Bandits

Explore similar work

Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees

Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs

Parameter-Free Dynamic Regret for Unconstrained Linear Bandits