Source-linked AI summary
Lipschitz Bandits with Stochastic Delayed Feedback
Zhongxuan Liu, Yue Kang, Thomas C. M. Lee
TL;DR
The paper introduces Lipschitz bandits with stochastic delayed feedback, where rewards in continuous metric action spaces arrive after random delays. It proposes delay-aware algorithms for bounded and unbounded delays, showing regret guarantees that preserve delay-free rates up to delay-dependent terms and are nearly optimal for unbounded delays.
Problem
The paper addresses how to learn in Lipschitz bandits when rewards are delayed or missing, a setting with limited prior understanding beyond discrete action spaces.
Method
It develops Delayed Zooming for bounded delays and Delayed Lipschitz Phased Pruning (DLPP) for unbounded delays, using delay-aware updates and scheduled accumulation of reliable feedback.
Results
Bounded delays retain the optimal delay-free regret rate up to an additive term scaling with τmax, while unbounded delays achieve the delay-free rate with quantile-dependent terms and a nearly matching lower bound.
Takeaways & Limitations
The proposed algorithms provide sublinear-regret guarantees for both bounded and unbounded stochastic delays in Lipschitz bandits.
Takeaways & Limitations
Delayed Zooming requires bounded delays; extending it to unbounded delays without additional assumptions on the delay distribution remains open.
Abstract
from arXiv · showhide
The Lipschitz bandit problem extends stochastic bandits to a continuous action set defined over a metric space, where the expected reward function satisfies a Lipschitz condition. In this work, we introduce a new problem of Lipschitz bandit in the presence of stochastic delayed feedback, where the rewards are not observed immediately but after a random delay. We consider both bounded and unbounded stochastic delays, and design algorithms that attain sublinear regret guarantees in each setting. For bounded delays, we propose a delay-aware zooming algorithm that retains the optimal performance of the delay-free setting up to an additional term that scales with the maximal delay $\tau_{\max}$. For unbounded delays, we propose a novel phased learning strategy that accumulates reliable feedback over carefully scheduled intervals, and establish a regret lower bound showing that our method is nearly optimal up to logarithmic factors. Finally, we present experimental results to demonstrate the efficiency of our algorithms under various delay scenarios.
1 INTRODUCTION
This paper introduces Lipschitz bandits with stochastic delayed feedback, addressing the limited understanding of delays in continuous metric action spaces. It develops separate methods for bounded and unbounded delays, with sublinear-regret guarantees and supporting experiments.
- The paper studies delayed feedback in Lipschitz bandits, where continuous metric action spaces and Lipschitz rewards make stale observations especially challenging.Existing delayed-feedback work largely focuses on discrete-action settings, while Lipschitz-bandit methods rely on prompt feedback to refine partitions and confidence estimates.
- For bounded delays, the delay-aware zooming algorithm recovers the optimal delay-free regret bound with an additional term scaling with the maximal delay τmax.
- For unbounded delays, DLPP accumulates reliable feedback over scheduled intervals and achieves the delay-free regret rate with an additive dependence on delay-distribution quantiles.
- The unbounded-delay analysis also establishes a regret lower bound showing that the proposed guarantee is nearly optimal up to logarithmic factors.
- Experiments show that the methods retain sublinear regret and perform efficiently across varied reward functions and delay settings.
2 RELATED WORK
Prior work covers Lipschitz bandits and delayed feedback separately, but delayed-feedback research has mainly addressed discrete-action bandits. The paper positions its contribution at their intersection.
- Lipschitz bandits extend continuum-armed bandits to general metric spaces and are commonly handled by uniform or adaptive discretization with standard bandit algorithms.Related methods include UCB, Thompson Sampling, and elimination-based techniques.
- Delayed stochastic bandit research has studied UCB modifications, censored feedback, phase-based elimination, and unbounded delays through delay-distribution quantiles.
- Existing delayed-feedback literature predominantly concerns discrete action spaces, leaving limited understanding of delayed observations in Lipschitz bandits.
3 PROBLEM SETTINGS AND PRELIMINARIES
The problem is a Lipschitz bandit on a compact doubling metric space with stochastic rewards and delayed, possibly missing observations. Its complexity is characterized by covering and zooming dimensions, while regret counts all generated rewards.
- A Lipschitz-bandit instance consists of a compact doubling metric space and an unknown 1-Lipschitz expected reward function µ mapping actions to [0, 1].
- At each round, the agent selects an action and a stochastic reward is generated, while classical feedback would be observed immediately after the round.
- With stochastic delays, feedback arrives as an action-reward pair after an unknown delay, without revealing the original round or delay; infinite delays represent missing feedback.Delays are assumed independent of both the chosen arm and the realized reward.
- The observed filtration H_t contains feedback available by the start of round t and records delayed information according to whether its arrival time precedes the current round.
- The objective is to minimize cumulative regret based on all generated rewards rather than only rewards observed by horizon T.The action gap is defined as ∆(x) = µ* − µ(x).
- Covering dimension measures the metric-space complexity, whereas zooming dimension measures the complexity of the near-optimal region and can be substantially smaller in benign instances.Zooming dimension depends on the unknown reward function and therefore is not revealed to the agent.
4 DELAY WITH BOUNDED SUPPORT: DELAYED ZOOMING ALGORITHM
For bounded stochastic delays, Delayed Zooming adapts UCB-based adaptive discretization by using observed feedback and lazy updates, preserving delay-free regret up to a maximal-delay penalty.
- Algorithm: The method maintains a covered active arm set, activates uncovered arms, and selects an active arm with the largest UCB index.This combines adaptive discretization with confidence-based selection to focus on high-reward regions.
- Algorithm: The algorithm replaces pull counts with observed-reward counts when computing empirical means and confidence radii under delayed feedback.This modification uses only available feedback because pending rewards and their observations are unavailable in real time.
- Algorithm: Lazy updates cache excessive incoming feedback so an inactive arm’s confidence radius cannot shrink below half its value at its last pull.The cache is cleared when the arm is pulled again, restoring the suboptimality-gap analysis.
- Regret guarantee: Delayed Zooming maintains the non-delayed regret rate with an additive penalty depending on the maximum delay.When delays vanish, the bound recovers the Lipschitz-bandit rate; for finite action spaces, it recovers the bounded-delay finite-bandit form.
- Scope: The analysis assumes delays are bounded, although the algorithm also performs well under unbounded delays in experiments.The bounded-support assumption guarantees feedback is eventually observed within τmax rounds.
5 DELAY WITH UNBOUNDED SUPPORT: DELAYED LIPSCHITZ PHASED PRUNING
For unbounded or missing feedback, DLPP learns in phases by sampling active balls, pruning poorly performing regions, and refining survivors; its regret depends on delay quantiles and is nearly optimal up to logarithmic factors.
- Motivation: The method is designed for settings where feedback may be missing or censored, corresponding to infinite delays.This motivates replacing the bounded-delay assumption with phased accumulation of reliable observations.
- Scope and novelty: DLPP applies to compact doubling metric spaces and individual reward delays, without batched communication constraints.Unlike the contrasted approach, it samples uniformly from remaining balls rather than repeatedly sampling one cube.
- Phased learning: Each phase uniformly samples active balls until sufficient feedback is collected, then removes balls whose empirical means are sufficiently below the best observed mean.The sample threshold is chosen so ball means concentrate with high probability.
- Phased learning: After pruning, DLPP constructs finer coverings of surviving regions and proceeds with exponentially smaller ball radii.This focuses later phases on regions containing near-optimal arms.
- Regret guarantee: DLPP achieves the non-delayed regret rate with an additive dependence on quantiles of the delay distribution.The bound can be optimized over a quantile p, and its delay penalty does not scale with the zooming dimension.
6 LOWER BOUND
The lower-bound construction uses delays that are finite with probability p and infinite otherwise, showing that delayed Lipschitz-bandit regret essentially matches the upper bound up to logarithmic factors.
- Construction: The hard delay distribution returns a fixed delay τ0 with probability p and missing feedback otherwise.The missing-feedback component produces an additional lower-bound term beyond the non-delayed Lipschitz-bandit contribution.
- Proof strategy: A Bernoulli coupling simulates a delayed Lipschitz-bandit algorithm by aligning the original and delayed procedures with probability p.This reduction preserves the existing Lipschitz-bandit lower-bound rate while exposing delay effects.
- Lower-bound result: The lower bound essentially matches the upper bound, establishing near-optimality up to logarithmic factors.Its construction includes a delay-dependent cost from receiving no feedback during the initial τ0 rounds.
7 EXPERIMENTS
Experiments evaluate Delayed Zooming and DLPP across bounded and unbounded delays, multiple reward functions, and varying average-delay levels. Both methods show sublinear regret, with algorithmic differences across one- and two-dimensional functions.
- Experimental setup: The study uses triangle, sine, and two-dimensional reward functions under uniform bounded delays and geometric unbounded delays, with E[τ] ∈ {20, 50} plus a no-delay baseline.Experiments use T = 60,000, δ = 0.01, and averages over B = 30 independent trials.
- Results: Both proposed algorithms exhibit sublinear cumulative regret under bounded and unbounded delay settings.Delayed feedback remains on the same scale as the non-delayed case, while larger expected delays produce higher cumulative regret.
- Results: DLPP is more efficient than Delayed Zooming for the two-dimensional reward functions.The reported advantage is attributed to DLPP’s pruning and discretization strategy.
- Results: Delayed Zooming has lower regret than DLPP for the one-dimensional reward functions but higher regret for the two-dimensional functions.
- Results: DLPP’s regret curve is approximately piecewise linear because it samples uniformly from surviving balls within each phase.
8 CONCLUSION
The conclusion presents delayed Lipschitz bandits as a new problem and gives separate algorithms for bounded and unbounded stochastic delays. Delayed Zooming matches delay-free performance up to maximal-delay dependence, while DLPP achieves nearly optimal bounds with quantile dependence and supporting experiments.
- Conclusion: The paper introduces Lipschitz bandits with stochastic delayed feedback and develops algorithms for bounded and unbounded delays.
- Bounded delays: For bounded delays, Delayed Zooming matches the optimal delay-free regret performance up to an additive term scaling with τmax.
- Unbounded delays: For unbounded delays, DLPP accumulates reliable feedback over scheduled intervals and achieves near-optimal regret bounds with an additional dependence on delay-distribution quantiles.
- Unbounded delays: The lower bound for unbounded delays nearly matches the DLPP upper bound up to logarithmic factors.
- Limitation: Delayed Zooming requires bounded delays, and extending it to unbounded delays without additional distributional assumptions remains open.
A.2 PROOF OF THEOREM 1
The proof of Theorem 1 controls bounded-delay regret through confidence radii, active-ball separation, and scale-dependent counting. These ingredients support a zooming-dimension regret bound with an additional maximal-delay term.
- Regret bound: The proof combines the scale-wise counting argument with bounded-delay control to derive the stated regret bound.The displayed bound includes an additional term involving τmax and T alongside the delay-free zooming terms.
- Zooming analysis: At scale r_i = 2^-i, the number of active arms is bounded by the zooming number N_z(r_i), yielding scale-dependent counting through the zooming dimension d_z.
B.2 PROOF OF THEOREM 3
Theorem 3 analyzes DLPP by relating played-ball counts to observed feedback through delay quantiles. Optimizing over the quantile and phase parameters yields the upper bound, while the proof controls regret across completed phases and surviving balls.
- Quantile-dependent feedback: DLPP relates the number of times a ball is played to the number of observed rewards using delay quantiles.This converts delayed feedback into a quantile-dependent contribution to the regret bound.
- Phase sampling: Round-robin sampling within each phase adds only logarithmic dependence on the number of active balls.
- Late-phase control: After phase M, every played ball has regret bounded by 16r_M, allowing the remaining regret to be controlled through the phase radius and zooming number.
- Regret bound: The regret decomposition combines early-phase, late-phase, and delay terms into the theorem’s upper bound.The displayed intermediate terms include 16 · 2^-M · T, 32 · 2^(d_z+1)M · c · 2^4 log T, and 16(Q(p) + 1)(3d_z + 1).
- Parameter optimization: Because the bound holds for every p ∈ (0, 1], minimizing over p gives the lowest stated upper bound.
C ANALYSIS OF LOWER BOUND
The lower-bound analysis adapts a non-delayed Lipschitz-bandit lower bound to stochastic delays through a reduction and an explicit missing-feedback construction. It shows that delay quantiles impose unavoidable regret while preserving the underlying Lipschitz-bandit difficulty.
- Lower-bound reduction: The reduction transforms any delayed Lipschitz-bandit algorithm into a non-delayed algorithm by Bernoulli-sampling rounds in which feedback is available.The construction uses delays of 0 with probability p and infinity otherwise, allowing the simulated algorithm to interact with a non-delayed environment over a reduced number of rounds.
- Initial-period lower bound: A delay distribution with delay τ0 occurring with probability p and missing feedback otherwise leaves the learner without feedback during the first τ0 rounds.During this initial period, the learner cannot distinguish among arms and is no better than uniform random play.
- Initial-period lower bound: The initial feedback-free period alone contributes at least τ0 times the average suboptimality gap to expected regret.The average suboptimality gap is denoted by ¯∆, so the unavoidable initial contribution is τ0 ¯∆.
D ADDITIONAL EXPERIMENTAL DETAILS
The additional details explain how the algorithms accommodate unknown noise scales and identify the simulation setup used to report final cumulative regrets. The reported table summarizes results at T = 60000 under the Section 7 experiments.
- Noise adaptation: If the sub-Gaussian noise parameter σ differs from one, the algorithms can be modified using σ-dependent confidence and sampling requirements.Delayed Zooming scales its confidence radius by σ, while DLPP scales each phase’s required observations by σ^2.
- Noise adaptation: Higher noise variability requires either wider confidence radii or more observations per ball to maintain sufficient exploration.The adjustment addresses increased uncertainty in reward estimates.
- Simulation reporting: Final cumulative regrets at T = 60000 are reported in Table 1 for the simulations from Section 7.The table contains numerical values corresponding to Figure 1’s experimental settings.