Skip to content

Memory--Batch Tradeoffs in Lipschitz Bandits

Aug 2026 · 0 citations · 42 references
Computer Science Mathematics

TL;DR

The analysis separates fine-scale comparisons from the regional information needed to allocate their samples at low regret, which separates fine-scale comparisons from the regional information needed to allocate their samples at low regret.

Abstract

Lipschitz bandits admit near-optimal regret $\widetilde O_d(T^{(d+1)/(d+2)})$ with little memory under full adaptivity, or with few batches under unrestricted memory. We characterize the minimax expected pseudo-regret over $T$ rounds with $W$ bits of memory and at most $B$ batches in dimension $d$. For every memory budget $W$, we prove a lower bound of order $T^{\frac{d+2}{d+3}} (1+(B-1)W)^{-\frac{1}{d(d+3)}}$. When $W\gtrsim_d\log(eT)$, algorithms with fixed batch boundaries attain, up to logarithmic factors, the larger of this bound and the optimal $B$-batch regret with unrestricted memory. The analysis separates fine-scale comparisons from the regional information needed to allocate their samples at low regret. Attaining $\widetilde O_d(T^{(d+1)/(d+2)})$ regret requires both $B=\Omega_d(\log\log T)$ and $(B-1)W=\widetilde{\Omega}_d(T^{d/(d+2)})$. With one bit of memory, minimax regret is $\widetilde\Theta_d(TB^{-1/(d+2)})$ under adaptive batch boundaries while $\Theta_d(T)$ under fixed boundaries.

View source

Similar papers

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For $K$-armed bandits with $A$ optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 20...

Kaixuan Ji, Qi-Wei Di, Qing-Yue Zhao et al. · 0 citations

Lower Bounds for Linear-Oracle Online Learning

Can a constant number of linear minimizations per round improve on the $T^{3/4}$ regret rate of online Frank-Wolfe on general convex sets? Weibel et al. conjectured that fixed-coefficient methods cannot. We prove their conjecture and extend the lower bound to every deterministic learner in an oracle-only model. The lea...

Mohit Sinha · 0 citations
#machine learning Preprint Aug 2026

Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits

The results resolve the open question raised in the literature concerning the sharp arm-dependent regret--instability frontier and develop a new offline top-prefix representation that removes path dependence from online decisions.

Kai-Fei Wang, Yin-Yu Ye, Han Zhong · 0 citations
#machine learning Preprint Sep 2026

Bandits with Probing: Optimal Regret and the Limits of Winner Feedback

A learner probes at most $k$ of $n$ arms each round, receives the maximum of their rewards in $[0,1]$, and competes with the best fixed arm. When does the probing advantage pay for learning? We determine two minimax laws. Under independent stochastic rewards with winner feedback (the maximum and a winning label), or on...

Yong-Jie Guan · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.