PaperlayerView exact revision on arXiv

Source-linked AI summary

Lipschitz Bandits with Arbitrary Feedback Delays

Yuhao Liu, Yu Chen, Longbo Huang

arXiv:2608.15036v1cs.LG

TL;DR

The paper asks how Lipschitz bandits can operate when feedback delays are arbitrarily fixed before interaction. It analyzes an elimination-based stochastic algorithm and an EXP3-based adversarial algorithm, showing delay-free regret rates plus delay-dependent penalties. The conclusion gives nearly the same total-delay order in both settings while identifying a parameter-knowledge requirement for the adversarial analysis.

  • Problem

    Lipschitz bandits with delayed feedback remain insufficiently studied under arbitrary delays, beyond prior work restricted to stochastic delay models.

  • Method

    The paper uses an elimination-based algorithm for stochastic rewards and an EXP3-based algorithm with adaptive discretization for adversarial rewards.

  • Results

    Both algorithms recover their corresponding delay-free regret rates, while arbitrary delays add penalties of order ˜O(√(D log D)) in the stochastic setting and O(√(dD log T)) in the adversarial setting.

  • Takeaways & Limitations

    The results characterize delayed feedback's impact on Lipschitz bandit regret through the total delay budget, with nearly the same delay order across the two settings.

  • Takeaways & Limitations

    The adversarial analysis requires a fixed learning rate and therefore prior knowledge of total delay D and zooming dimension d_z.

Abstract

from arXiv · show

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.

1. Introduction

The paper studies Lipschitz bandits when feedback delays are arbitrarily fixed before interaction, addressing a setting less explored than stochastic delays. It develops separate approaches for stochastic and adversarial rewards and analyzes their regret under total delay.

  • Motivation: Lipschitz bandits extend multi-armed bandits to continuous action spaces with smoothly varying expected rewards.The framework uses actions from a metric space and Lipschitz-continuous reward expectations.
  • Research gap: The paper addresses the limited study of Lipschitz bandits with arbitrary delays beyond prior analyses restricted to stochastic delays.The delay sequence can be arbitrarily chosen before the procedure starts.
  • Motivation: Feedback delays prevent agents from immediately using newly generated rewards when selecting subsequent actions.At round t, only rewards whose delays have elapsed are available; delays may be fixed before interaction and revealed upon feedback.
  • Contributions: The stochastic setting investigates an elimination-based algorithm under arbitrary feedback delays.The analysis uses a greedy-based characterization of worst-case delay patterns.
  • Contributions: The adversarial setting designs an EXP3-based algorithm using a zooming schedule and weight-update procedure for arbitrary delays.The adversarial formulation uses a modified notion of zooming dimension.
  • Contributions: Both settings recover delay-free regret rates while adding a regret penalty of order ˜O(√D) from arbitrary feedback delays.The paper frames the delay effect through the total delay budget D.

2. Related Works

Related work covers Lipschitz bandits, extensions involving non-stationarity and corruption, and delayed-feedback bandits. The paper distinguishes its arbitrary-delay setting from prior Lipschitz-bandit work on stochastic delays.

  • Lipschitz Bandits: Lipschitz bandits generalize multi-armed bandits to arbitrary metric spaces and support adaptive techniques with near-optimal regret guarantees.Prior work also adapts finite-armed bandit techniques to continuous or metric action spaces.
  • Lipschitz Bandits: Prior extensions study non-stationary rewards, adversarial corruption, distributional shifts, and alternative reward assumptions.These settings control regret using quantities such as corruption budgets or significant distributional shifts.
  • Delayed Feedback: Liu et al. (2026) studied Lipschitz bandits with stochastic delayed feedback, including bounded and unbounded delays.Their analysis differs from the present work's arbitrary, potentially adversarial delay model.
  • Delayed Feedback: Delayed-feedback research includes stochastic and adversarial multi-armed bandits, modified UCB methods, censored rewards, and arbitrary feedback delays.The broader literature also considers best-of-both-worlds and linear-bandit settings.

3. Results for Stochastic Rewards

For stochastic rewards, the paper applies a phased elimination algorithm that adaptively refines near-optimal regions despite arbitrary delays. Its regret matches the delay-free rate up to an additional delay-dependent term.

  • Setting: The stochastic analysis assumes arbitrary oblivious delays fixed before the first round and unknown until corresponding feedback arrives.Rewards follow a stationary mean function with sub-Gaussian noise in the specialized setting.
  • Scope: The stochastic presentation specializes to [0,1]^d with the ℓ∞ metric, where the covering dimension equals d.The authors state that arbitrary metric spaces can be handled with access to a covering oracle.
  • Algorithm: The algorithm operates in phases over a zooming tree whose nodes partition [0,1]^d into progressively smaller ℓ∞-cubes.Each node at depth h has diameter 2^-h, and each node is partitioned into 2^d children.
  • Algorithm: During each phase, active nodes are sampled until their observed-reward counts reach a threshold, then nodes with large estimated optimality gaps are pruned.The remaining nodes are zoomed into by adding their children to the next active set.
  • Delay adaptation: The algorithm does not require prior knowledge of total delay budget D and adapts to the actual delay.Its analysis characterizes additional pulls caused by delayed observations through a greedy-based inverse-delay argument.
  • Regret bound: ˜O(T^((d_z+1)/(d_z+2))) matches the optimal delay-free Lipschitz-bandit rate, while O(√(D log D)) captures arbitrary-delay regret.The bound is stated with high probability and d_z denotes the instance's c-zooming dimension.
  • Interpretation: The analysis establishes robustness to arbitrary delay sequences even though the algorithm is identical to one previously analyzed only for stochastic delays.The result also recovers the typical finite-armed delay dependence after adaptive discretization.

4. Results for Adversarial Rewards

For adversarial Lipschitz bandits with arbitrary delayed feedback, the paper adapts EXP3 through adaptive discretization and delayed weight updates. The resulting regret has the same structure as the stochastic-delay guarantee, with a zooming-dimension distinction and parameter-knowledge requirements.

  • Algorithm: The algorithm extends EXP3 to Lipschitz bandits using adaptive discretization over active nodes in a zooming tree.At each round, it selects an active node by weight, samples an arm within that node, updates weights when feedback arrives, and zooms when confidence permits.
  • Algorithm: Delayed feedback is handled by scheduling weight updates and transferring updates from zoomed-in nodes to their active descendants.The estimator combines inverse propensity scoring with a confidence correction term.
  • Regret guarantee: Theorem 4.1 gives a regret bound with the same structure as the stochastic-delay result, differing mainly in the definition of the zooming dimension.The adversarial zooming dimension is based on adversarial gaps and is at most the ambient dimension d in the worst case.
  • Regret guarantee: The adversarial guarantee recovers the delay-free result of Podimata & Slivkins when delays do not contribute.The bound’s delay dependence matches established total-delay dependence for traditional finite-armed bandits.
  • Assumptions: Achieving the stated optimal adversarial rate requires prior knowledge of both the total delay budget D and the zooming dimension d_z.The algorithm’s learning-rate choice depends on these parameters.

5. Analysis (Outline)

The analysis separates delay-independent EXP3 regret from delay-induced effects, then controls each through concentration, active-set growth, zooming-dimension arguments, and a delay accounting bound. A greedy inverse-delay argument handles stochastic rewards, while potential analysis bounds adversarial delay costs.

  • Stochastic rewards: In stochastic analysis, delayed feedback can cause nodes to receive more pulls than their delay-free allocation, creating additional phase regret.The total additional pulls are bounded by relating oversampling to the minimum delay needed to generate it.
  • Stochastic rewards: The minimum delay for a fixed oversampling pattern is obtained by greedily postponing the latest outstanding feedback.Sorting additional pulls in non-decreasing order yields the minimum delay for the sequence.
  • Adversarial rewards: The adversarial proof uses an EXP3 potential whose changes occur when feedback is incorporated, while zooming preserves total weight.This produces an estimated-regret decomposition into delay-independent and delay-dependent terms.
  • Adversarial rewards: The proof controls estimation error, active-node growth, and zooming through concentration and adversarial zooming-dimension arguments.These steps convert surrogate regret into actual regret and bound the delay-independent terms.
  • Adversarial rewards: The delay-induced regret is bounded by O(ηD) after summing changes in sampling distributions caused by delayed feedback.Balancing the learning rate η yields the final regret bound.

6. Conclusion

The paper studies Lipschitz bandits with arbitrary, precommitted feedback delays and provides separate algorithms for stochastic and adversarial rewards. Both recover delay-free regret rates while incurring an additional delay-dependent penalty, but the adversarial analysis requires prior problem-parameter knowledge.

  • Contributions: The paper addresses arbitrary feedback delays fixed before interaction and proposes elimination-based and EXP3-based algorithms for stochastic and adversarial rewards.The delay sequence is arbitrary but selected before the interaction begins.
  • Results: Both algorithms recover the state-of-the-art regret rates of their corresponding delay-free settings.The conclusion presents this as a shared guarantee across the two reward models.
  • Results: Feedback delays add a regret penalty of O(dD log T) in the adversarial setting, with nearly the same total-delay order in the compared guarantees.The results characterize how delay affects Lipschitz bandit regret.
  • Limitation: The adversarial analysis requires a fixed learning rate and therefore prior knowledge of total delay D and zooming dimension d_z.Developing parameter-free algorithms is identified as a future direction.

A. Proof of Theorem 3.1

This section provides proofs of Theorem 3.1.

  • The section contains the proofs supporting Theorem 3.1.

A.1. Regret Bound under Clean Events

Under the clean event E, empirical node means remain close to true rewards, ensuring that the optimal arm is never pruned and that active nodes have bounded optimality gaps.

  • Event E bounds every node’s empirical mean error by 4 · 2^-m during each completed phase.The corresponding phase average is based on received rewards and is no longer updated after node removal.
  • The optimal arm is never pruned when event E holds.An induction argument compares the empirical mean of the optimal node with every active node and keeps the latter above the pruning threshold.
  • 32 · 2^-m bounds the optimality gap of every arm in an active node during phase m.The claim is established inductively from the survival of the optimal arm and unpruned nodes across phases.
  • The clean-event claims provide the basis for directly controlling cumulative regret.

A.2. Proof of Theorem 3.1

The proof of Theorem 3.1 controls delayed plays by optimizing the adversary’s delay pattern for each phase. Monotonicity of additional plays then enables a delay-dependent bound.

  • The clean event E holds with probability at least 1 − δ, allowing the analysis to control regret on that event.
  • The phase analysis fixes the total number of additional plays and considers an adversary maximizing them while minimizing the delay budget required.
  • For fixed additional plays, the adversary delays earlier observations until the corresponding node receives its next required observation.This strategy expresses total delay through the ordered nodes processed in the phase.
  • An optimal additional-play sequence is non-decreasing across the ordered nodes.Swapping adjacent values p > q decreases total delay by q + 1, so inversions cannot occur in an optimum.
  • The proof adapts a lemma from Liu et al. (2026) to establish the clean-event analysis used here.

B. Proof of Theorem 4.1

Theorem 4.1’s algorithm maintains delayed-feedback statistics through phases, updates confidence information after received rewards, and zooms into nodes only when their confidence is sufficiently small.

  • The counter τ records how many reward signals have been received, rather than how many actions have been taken.
  • At each round, the agent samples a node from a distribution whose mass is proportional to its weight.
  • When feedback arrives, the algorithm updates the relevant active-node statistics using the received reward.
  • The algorithm zooms into node u exactly when conf_t(u) < t · L(u).
  • The analysis assumes t + d_t ≤ T, which does not affect the algorithm’s performance.

B.1. Main Proof

The main proof combines an EXP3-style potential analysis with concentration and zooming-process lemmas to control delayed updates, active-node growth, and the resulting regret.

  • Main Proof: The potential argument treats EXP3 weight updates explicitly while zooming does not change the potential function.
  • Main Proof: The proof partitions estimated regret into several terms and then applies concentration results to obtain a true regret bound.
  • Main Proof: With probability 1 − O(T^-2), the selected parameter schedule yields the stated regret bound.The schedule uses γ_t = (2 + 4 ln T)β|A_t|.
  • Main Proof: The delayed-update analysis compares observations arriving between pulls and bounds their contribution using the corresponding delays d_t and d_s.
  • Zooming Processes: Active-node geometry supplies lower sampling-probability bounds and constrains deactivation times along parent-child paths.In particular, a non-root node satisfies t_d(u) ≥ 2t_d(v) − 1, and active-node height is O(log T).
  • Bound on Activated Nodes: With probability 1 − O(T^-2), the total number of activated nodes is controlled using the adversarial zooming dimension d_z.The proof uses a greedy ordering of node sizes and concentration bounds across scales.
Loading 2608.15036v1…