Planned Restlessness: Delayed Meta Bandits with Budgets

Sudipto Guha

cs.LGOct 28, 2026

Planned Restlessness: Delayed Meta Bandits with Budgets

Authors: Sudipto Guha

Abstract

We study episodic finite-horizon Bayesian bandits, or meta-bandits, with independent arms. Each episode draws fresh arm qualities from unknown recurring priors. Observations arrive after known delays, and plays obey hard per-episode caps and total budgets. A play earns reward and informs both the current quality and the recurring prior: the learner must explore, use, and generalize. We formulate a common planning optimization over learning trajectories. Its LP relaxation values experiments through current reward, resource consumption and continuation: the value of future decisions from the learning state produced. Dual prices separate the arms into local programs and certify every admissible policy, including hierarchical Thompson sampling. Execution enforces the hard constraints while preserving the promised learning transitions or accounting for their loss. The framework also represents risk-sensitive objectives and prices purchased observations and buyout options. Delayed reports create planned restlessness: an arm's information changes while it is not played, through reports of its own earlier plays arriving on a known calendar. For stationary priors, finite reward alphabets, bounded report lag and nonbinding budgets, posterior sampling over the recurring priors bounds the price of not knowing them by $O(\sqrt{N})$ over $N$ episodes, with other parameters fixed. For one undelayed $T$ -step episode with arms capped at $T/X$ plays each, we obtain the LP-relative approximation factor $1+(2πX)^{-1/2}+O(X^{-1})$ , improving previous factors, with a matching lower bound for the leading term.

Figures & tables

Panel of Figure 1 — Figure 1: One arm across an episode boundary. Shown are selected stopping nodes $u$ of the current local DAG and starting nodes $v$ of the next. The handoff sends stopping mass $z(u)$ through the fixed probabilities $H_{e}(S,u,v)$ , giving arrival masses $q(v)$ . The continuation is $\sum_{v}q(v)F(v)$ . Each next starting node carries its posterior, remaining budget and pending reports.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Setting	GM13	This paper
Undelayed, any caps	$2$	$2$
Undelayed, caps at most $T/4$	$2$	$<1.363$
Undelayed, caps at most $T/8$	$2$	$<1.211$
Undelayed, caps at most $T/16$	$2$	$<1.132$
Undelayed, caps at most $T/X$ , $X\to\infty$	$2$	$1+(2\pi X)^{-1/2}+O(X^{-1})$
Delay $\delta=\sqrt{T}$ , $T\to\infty$	$\to 66$	$\to 1/c_{X}$

Appendix

Table 1: Approximation factors relative to the single-episode LP; in the delayed rows, GM13’s factor is relative to its delay-respecting relaxation and ours to the undelayed

\mathrm{LP}(P)

, and

y=\delta/\sqrt{T}

. Proposition 3.12 shows that the first and last rows are tight, and Proposition 3.11 that the leading term in the fifth row is necessary for this relaxation.

Multi-Armed Bandits

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

See all 352 papers

Oct 16, 2026

Budgeted Bayesian Bandits for Future Utilization

The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against a primal linear programming relaxation for a more general model. We show that the analyses of both algorithms are tight, even when their relaxations are asymptotically exact. We provide a different efficient algorithm that achieves a 0.43 approximation. We then provide an efficient algorithm whose guarantee approaches 1-e^{-1} approx 0.63 for bounded exchangeable reward observations in a non-vanishing regime, which is asymptotically tight against natural linear programming relaxations. The technique also gives certificates for stopping sequential model evaluation.

Sudipto Guha

Markovian Bandits Multi-Armed Bandits Approximation Algorithms

Ask PDF

Jun 15, 2026

Near-Optimal Stochastic Linear Bandits with Delay

We study stochastic linear bandits with delayed feedback under several delay models and establish near-optimal regret guarantees. Our results identify when delayed linear bandits exhibit the same qualitative behavior as multi-armed bandits (MAB), and when the linear structure creates fundamentally new challenges. Specifically, (1) for loss-independent delays, where the delay does not depend on the realized loss (but potentially depends on the arm), we show that delays incur only an additive regret penalty. Under stochastic delays, this penalty scales with the expected delay, while under adversarial delays, it scales with the maximum number of outstanding observations. Notably, both delay penalties are dimension-free, improving upon the state-of-the-art results; (2) for loss-dependent delays, we show that linear bandits are substantially harder than MAB: unlike in MAB, we prove matching (up to log factors) upper and lower bounds in linear bandits, whose delay penalty depends on the square root of the dimension. (3) for the delay-as-payoff model, a special case of loss-dependent delay, we show that the optimal MAB guarantee, which depends only on the delay of the optimal arm, is also unattainable in linear bandits. Together, these results provide a sharp characterization of how delayed feedback interacts with linear generalization.

Ofir Schlisselberg, Mengxiao Zhang, Yishay Mansour

Tel Aviv University · University of Iowa · Google Research

Bandits with Delayed Feedback Contextual Bandits

Ask PDF

Aug 15, 2026

Lipschitz Bandits with Arbitrary Feedback Delays

The Lipschitz bandit problem extends the traditional multi-armed bandit framework to continuous action spaces by assuming that the reward functions satisfy a Lipschitz condition. This work investigates Lipschitz bandits under arbitrary feedback delays, where reward signals are not received immediately upon taking an action but after an arbitrarily chosen delay. We consider both stochastic and adversarial reward settings, proposing an elimination-based algorithm and an EXP3-based algorithm, respectively. For both settings, our algorithms achieve a regret bound of

\tilde{O}\left(T^{\frac{d_z+1}{d_z+2}}+\sqrt{D}\right)

over a time horizon

T

with total delay

D

, where the main difference between settings lies in the definition of the zooming dimension

d_z

. Our bounds match existing delay-free regret guarantees for Lipschitz bandits and characterize the additional

\tilde{O}(\sqrt{D})

impact introduced by feedback delays.

Yuhao Liu, Yu Chen, Longbo Huang

Institute for Interdisciplinary Information Sciences, Tsinghua University

Lipschitz Bandits Multi-Armed Bandits Bandits with Delayed Feedback Adversarial Bandits

Ask PDF

Abstract

Multi-Armed Bandits

Explore similar work

Budgeted Bayesian Bandits for Future Utilization

Near-Optimal Stochastic Linear Bandits with Delay

Lipschitz Bandits with Arbitrary Feedback Delays