Lipschitz Bandits

Latest papers

9 papers0 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Sep 4, 2026

Dimension-Adaptive Batched Lipschitz Narrowing Without Knowing the Zooming Dimension

The Appropriately Combined Edge-length (ACE) sequence in A-BLiN depends on the zooming dimension

d_z

. This note removes that dependence. The next edge length is selected from the number of cubes that survive the preceding elimination. The resulting Count-Adaptive BLiN algorithm does not use

d_z

or the zooming constant

C_z

, yet it attains

\widetilde{\mathcal O}_d(T^{(d_z+1)/(d_z+2)})

regret with

\mathcal O_d(\log\log T)

batches. Together with the adaptive-grid lower bound in Theorem 10 of the original paper, the optimal batch complexity remains

Θ_d(\log\log T)

when

d_z

is unknown.

Yasong Feng

Lipschitz Bandits Multi-Armed 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

Aug 11, 2026

Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

Motivated by decentralized applications, we study cooperative multi-agent bandits in continuous (Lipschitz) action spaces when the Lipschitz constant is unknown. We consider three information structures: (A)~unobserved actions with common rewards, (B)~observed actions with independent rewards, and (C)~unobserved actions with independent rewards. In each case we design and analyze an algorithm that estimates the Lipschitz constant, chooses a discretization of the joint action space, and applies a cooperative bandit method to the induced discrete problem. Players never communicate once learning starts, so the central difficulty is that they must reach the same discretization from their own data. We prove regret guarantees showing that common rewards and observable actions each supply this agreement for free, and that in their absence agreement can still be bought, through a dithered quantization of the estimate, at no cost in the leading order of the regret.

Ricardo Parada, Chenzhang Zhao, William Chang

University of California, Riverside Riverside, CA, USA · University of California, Los Angeles Los Angeles, CA, USA

Lipschitz Bandits Multi-Armed Bandits Multi-Agent Coordination Multi-Agent Bandits Decentralized MARL

Ask PDF

Aug 8, 2026

Memory--Batch Tradeoffs in Lipschitz Bandits

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=Ω_d(\log\log T)

and

(B-1)W=\widetildeΩ_d(T^{d/(d+2)})

. With one bit of memory, minimax regret is

\widetildeΘ_d(TB^{-1/(d+2)})

under adaptive batch boundaries while

Θ_d(T)

under fixed boundaries.

Zicheng Lyu, Zengfeng Huang

Fudan University Shanghai, China · Fudan University Shanghai Innovation Institute Shanghai, China

Lipschitz Bandits Multi-Armed Bandits

Ask PDF

Jun 22, 2026

Leveraging Similarities in Multi-Armed Bandits

In many online learning and bandit problems, the actions we consider possess inherent similarities--for instance because they share latent traits, tags, or hierarchical structure. We study online learning with a similarity-structured action set, encoded by a rooted tree whose leaves are the actions and whose levels quantify how closely two actions are related. The loss sequence is assumed tree-compatible: losses of similar actions are constrained to be close. We establish an impossibility result showing that usual one-point bandit feedback cannot, in general, leverage range or tree-induced similarity, even under very strong similarity constraints. We then provide a unified set of algorithms which adapt to a wide range of richer feedback models, from semi-bandit feedback down to multi-point bandit protocols, including the minimal two-point feedback setting. We show these algorithms exhibit best-of-both-worlds guarantees and provably exploit action similarities by replacing the number of actions

K

by a similarity-aware effective number of actions

K_{\mathrm{eff}}

in the regret bounds. As an application, we show that under two-point feedback, it is possible to achieve

\sqrt{T}

regret in Lipschitz bandits when

d \leq 2

Khaled Eldowa, Thibaud Rahier, Augustin Cablant +2

Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France · Criteo AI Lab, Paris, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France

Lipschitz Bandits Multi-Armed Bandits Adversarial Bandits

Ask PDF

May 28, 2026

Instance-dependent Stochastic Lipschitz bandit

We study the Lipschitz bandit problem, where a learner sequentially maximizes an unknown Lipschitz function

f

over a domain

\mathcal{X} \subset [0,1]^d

using noisy pointwise evaluations. Existing regret bounds are either worst-case, scaling as

\tildeΘ \left ( T^{d+1/d+2}\right )

, or adaptive via the zooming dimension

d_z

, yielding

\tildeΘ \left ( T^{d_z+1/d_z+2}\right )

. However, such zooming-based guarantees are only partially instance-dependent, as they depend solely on the asymptotic growth of near-optimal level sets and fail to capture finer structural properties of

f

. We provide an analysis and an algorithm that characterizes the regret through integrals of the suboptimality gap of

f

over its level sets. This yields regret bounds that adapt to the local growth of level sets, rather than only their asymptotic behavior. As a corollary, when the set of maximizers has dimension

d^\star>0

, we obtain improved adaptive rates of order

\tilde{\mathcal{O}} \left ( T^{d_z+1 / \max(d_z,d^\star)+2}\right )

strictly improving over classical zooming bounds in this regime. Finally, we extend our analysis to the full-information setting (Lipschitz experts) and show how some of the regularity assumptions can be relaxed.

Marius Potfer, Vianney Perchet

Crest (Fairplay joint team), ENSAE · EDF R&D · Criteo AI Lab

Lipschitz Bandits Multi-Armed Bandits

Ask PDF

Apr 1, 2026

Lipschitz Dueling Bandits over Continuous Action Spaces

We study for the first time, stochastic dueling bandits over continuous action spaces with Lipschitz structure, where feedback is purely comparative. While dueling bandits and Lipschitz bandits have been studied separately, their combination has remained unexplored. We propose the first algorithm for Lipschitz dueling bandits, using round-based exploration and recursive region elimination guided by an adaptive reference arm. We develop new analytical tools for relative feedback and prove a regret bound of

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

, where

d_z

is the zooming dimension of the near-optimal region. Further, our algorithm takes only logarithmic space in terms of the total time horizon, best achievable by any bandit algorithm over a continuous action space.

Mudit Sharma, Shweta Jain, Vaneet Aggarwal +1

Indian Institute of Technology Ropar · Purdue University · Indian Institute of Technology Hyderabad

Lipschitz Bandits Dueling Bandits Multi-Armed Bandits

Ask PDF

Feb 18, 2026

Multi-Agent Lipschitz Bandits

We study the decentralized multi-player stochastic bandit problem over a continuous, Lipschitz-structured action space where hard collisions yield zero reward. Our objective is to design a communication-free policy that maximizes collective reward, while separating coordination costs from learning costs. We propose a modular protocol that first solves the multi-agent coordination problem by identifying and seating players on distinct, high-value regions via a novel maxima-directed search and then decouples the problem into

N

independent single-player Lipschitz bandits. In the consensus regime, we obtain an end-to-end regret bound whose dominant learning term is

\tilde{O}(T^{(d+1)/(d+2)})

, matching the single-player Lipschitz rate; the upfront coordination cost is horizon-independent at fixed confidence and only polylogarithmic in

T

in the expected-regret form. Under an additional public coverage/scheduling assumption for the epochic extension, we also obtain a gap-free

\tilde{O}(T^{(d+1)/(d+2)})

guarantee. We further derive a matching lower bound for the dominant learning term and extend the framework to general distance-threshold collision models.

Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1

University of Colorado Boulder · INRIA Paris

Lipschitz Bandits Multi-Agent Bandits Multi-Armed Bandits Multi-Agent Coordination

Ask PDF

Oct 4, 2025

Batched Bandits with Heavy-Tailed Rewards

The batched multi-armed bandit (MAB) problem, where rewards are collected in batches, is pivotal in applications like clinical trials. While prior work assumes light-tailed reward distributions, real-world scenarios often exhibit heavy-tailed outcomes. This paper addresses this gap by introducing robust batched bandit algorithms for heavy-tailed rewards in both multi-arm and Lipschitz settings. We uncover somewhat surprising phenomena for such problems -- heavier tails require fewer batches to achieve near-optimal regret in the instance-independent setting, as well as the Lipschitz setting. In sharp contrast, in the instance-dependent setting, the number of batches required to achieve near-optimal regret does not depend on the tail heaviness.

Yunwen Guo, Yunlun Shu, Gongyi Zhuo +1

School of Mathematical Sciences, Fudan University, 220 Handan Rd., 200433, Shanghai, China · Shanghai Center for Mathematical Sciences, Fudan University, 220 Handan Rd., 200433, Shanghai, China

Lipschitz Bandits Multi-Armed Bandits Heavy-Tailed Noise Robust Multi-Armed Bandits Heavy-Tailed Distributions

Ask PDF