Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Lipschitz Dueling Bandits over Continuous Action Spaces

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Causal and structured bandits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces ARC-DuelLi, a recursive zooming-style algorithm for stochastic dueling bandits over Lipschitz continuous action spaces that uses a per-round fixed reference arm to get regret O~(T^{(d_z+1)/(d_z+2)}) with O(d log T) memory.

Problem

Stochastic dueling bandits over continuous Lipschitz action spaces with only noisy pairwise comparison feedback; prior work covers only finite/convex action spaces or scalar-reward Lipschitz bandits.

Approach

Use a round-wise fixed reference arm so that pairwise comparisons become a common scalar score across regions, enabling safe recursive cube elimination guided by an adaptively chosen reference arm, with a depth-first implementation using logarithmic memory.

Key results

• Regret bound O~(T^{(d_z+1)/(d_z+2)}) for ARC-DuelLi under bi-Lipschitz transfer function, with matching lower bound for linear transfer via reduction from scalar Lipschitz bandits.
• Reduction shows any dueling algorithm with linear transfer induces a scalar-feedback algorithm with exactly twice the regret.
• On a synthetic 2D instance, reference arms initialized at (0.9,0.9) converge toward the optimum (0.3,0.1), and cumulative regret outperforms an Interleaved Filter uniform-discretization baseline.

Limitations

• Requires knowledge of the zooming dimension to set exploration depth
• Relies on bi-Lipschitz transfer assumption and known upper Lipschitz constant Gamma
• Experiments limited to a single synthetic 2D instance

Experimental setup

Benchmarks: synthetic 2D continuous dueling bandit instance

Metrics: cumulative regret preference gap of reference arm to optimum

Baselines: Interleaved Filter

Builds on: zooming algorithm Interleaved Filter recursive zooming algorithm for Lipschitz bandits

Closest papers by meaning

• Lipschitz Bandits with Stochastic Delayed Feedback (ICLR 2026 · similarity 0.90)
• Non-Stationary Lipschitz Bandits (NeurIPS 2025 · similarity 0.89)
• Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 2024 · similarity 0.89)
• Fusing Reward and Dueling Feedback in Stochastic Bandits (ICML 2025 · similarity 0.89)
• Feel-Good Thompson Sampling for Contextual Dueling Bandits (ICML 2024 · similarity 0.89)
• On Weak Regret Analysis for Dueling Bandits (NeurIPS 2024 · similarity 0.88)