Lipschitz Bandits with Arbitrary Feedback Delays

• URL: http://arxiv.org/abs/2608.15036v1
• Date: Sat, 15 Aug 2026 04:39:49 GMT
• Title: Lipschitz Bandits with Arbitrary Feedback Delays
• Abstract summary: 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.<n>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.
• Score: 33.531774470131644
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.

Related papers

• Lipschitz Dueling Bandits over Continuous Action Spaces [40.308173981781046]
  We study dueling bandits over continuous action spaces with Lipschitz structure.<n>We propose the first algorithm for Lipschitz dueling bandits, using round-based exploration.<n>Our algorithm takes only logarithmic space in terms of the total time horizon, best achievable by any bandit algorithm over a continuous action space.
  arXiv  Detail & Related papers  (2026-04-01T06:07:33Z)
• A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
  We introduce a continuous-time model under which regret decomposes into a delay-independent learning term and a delay-induced drift term.<n>For bandit convex optimization, we significantly improve existing regret bounds, with delay-dependent terms matching state-of-the-art first-order rates.
  arXiv  Detail & Related papers  (2026-02-02T18:17:34Z)
• Lipschitz Bandits with Stochastic Delayed Feedback [3.0594138391611967]
  We introduce a new problem of Lipschitz bandit in the presence of delayed feedback.<n>We design algorithms that attain sublinear regret guarantees in each setting.<n>We present experimental results to demonstrate the efficiency of our algorithms under various delay scenarios.
  arXiv  Detail & Related papers  (2025-09-30T22:07:17Z)
• Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting [22.208290858529672]
  We investigate the online nonsubmodular optimization with delayed feedback in the bandit setting.<n>We propose a novel method, namely DBGD-NF, which employs the one-point gradient estimator.<n>We also extend DBGD-NF by employing a blocking update mechanism to decouple the joint effect of the delays and bandit feedback.
  arXiv  Detail & Related papers  (2025-08-01T11:00:19Z)
• Non-Stationary Lipschitz Bandits [6.596201106451449]
  We study the problem of non-stationary Lipschitz bandits, where the number of actions is infinite and the reward function, satisfying a Lipschitz assumption, can change arbitrarily over time.<n>We design an algorithm that adaptively tracks the recently introduced notion of significant shifts, defined by large deviations of the cumulative reward function.
  arXiv  Detail & Related papers  (2025-05-24T21:23:19Z)
• Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs [60.7808741738461]
  We study online learning with oblivious delays under a novel clairvoyance'' that limits how many past rounds can be tracked simultaneously for delayed feedback.<n>Our algorithms achieve minimax regrets across all capacity levels, with performance degrading gracefully under suboptimal capacity.
  arXiv  Detail & Related papers  (2025-03-25T17:20:39Z)
• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  bandit convex optimization (BCO) with delayed feedback, where only the loss value of the action is revealed under a delay. We develop a novel algorithm, and prove that it enjoys a regret bound of $O(sqrtnT3/4+sqrtdT)$ in general. We show that the proposed algorithm can improve the regret bound to $O((nT)2/3log/3T+dlog T)$ for strongly convex functions.
  arXiv  Detail & Related papers  (2024-02-14T13:08:26Z)
• Robust Lipschitz Bandits to Adversarial Corruptions [61.85150061213987]
  Lipschitz bandit is a variant of bandits that deals with a continuous arm set defined on a metric space. In this paper, we introduce a new problem of Lipschitz bandits in the presence of adversarial corruptions. Our work presents the first line of robust Lipschitz bandit algorithms that can achieve sub-linear regret under both types of adversary.
  arXiv  Detail & Related papers  (2023-05-29T18:16:59Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  We study a distributed multi-armed bandit where a client supplies the learner with communication-constrained feedback. We propose a multi-phase bandit algorithm, $mathttUEtext-UCB++$, which matches this lower bound to a minor additive factor.
  arXiv  Detail & Related papers  (2023-04-25T09:31:20Z)
• Smooth Non-Stationary Bandits [49.19728527803684]
  We study a non-stationary bandits problem where each arm's mean reward sequence can be embedded into a $beta$-H"older function. We show the first separation between the smooth (i.e., $betage 2$) and non-smooth (i.e., $beta=1$) regimes by presenting a policy with $tilde O(k4/5 T3/5)$ regret on any $k$-armed, $2$-H"older instance.
  arXiv  Detail & Related papers  (2023-01-29T06:03:20Z)
• Lipschitz Bandits with Batched Feedback [24.605942770966973]
  We introduce a novel landscape-aware algorithm, called Batched Lipschitz Narrowing (BLiN), that optimally solves this problem. Our theoretical lower bound implies that $Omega(loglog T)$ batches are necessary for any algorithm to achieve the optimal regret.
  arXiv  Detail & Related papers  (2021-10-19T03:59:45Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.