cs.LGApr 1, 2026
SaveLipschitz Dueling Bandits over Continuous Action Spaces
Organizations: Indian Institute of Technology Ropar · Purdue University · Indian Institute of Technology Hyderabad
Abstract
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 , where 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.
Figures & tables
Figure 1: Performance of ARC-DuelLi over 50 runs. (a) Final reference arms concentrate near the optimal arm. (b) Decay of the gap across rounds, showing convergence of the reference arm. (c) Cumulative regret compared against a uniform discretization baseline (Interleaved Filter).The solid curves denote averages over runs, and the shaded regions represent standard deviation.
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
| Symbol | Meaning |
|---|---|
| Problem Setup | |
| Action space, | |
| Dimension of action space | |
| Metric on (typically ) | |
| Unknown reward / utility function | |
| Transfer function | |
Table 1: Notation used throughout the paper
Figure 2: Performance of ARC-DuelLi with randomly initialized reference arms over 10 runs. (a) Reference arms converge toward the optimal arm. (b) The optimality gap decreases across rounds. (c) Cumulative regret remains comparable to the fixed-initialization setting.
Figure 3: Performance of ARC-DuelLi under scaled rewards in . (a) Reference arms converge toward the optimal arm despite the larger reward scale. (b) The gap decreases across rounds, indicating consistent improvement in the reference arm. (c) Cumulative regret compared with a uniform discretization baseline, showing superior performance of ARC-DuelLi . The solid curves denote averages over runs, and the shaded regions represent standard deviation.
Figure 4: Performance of ARC-DuelLi on the Flat reward function, averaged over independent runs. From left to right: (a) evolution of the reference arm overlaid on the utility landscape, illustrating convergence toward the optimal region, (b) convergence of the optimality gap with the shaded region denoting one standard deviation, and (c) cumulative regret as a function of the number of comparisons.
Figure 5: Performance of ARC-DuelLi on the Plateau reward function, averaged over independent runs. From left to right: (a) evolution of the reference arm on the utility landscape, (b) convergence of the optimality gap with one standard deviation, and (c) cumulative regret over time.
Figure 6: Performance of ARC-DuelLi on the Quadratic reward function, averaged over independent runs. From left to right: (a) convergence of the reference arm on the utility landscape, (b) convergence of the optimality gap with one standard deviation, and (c) cumulative regret as the learning process progresses.
Figure 7: Performance of ARC-DuelLi on the Ridge reward function, averaged over independent runs. From left to right: (a) convergence of the reference arm toward the optimal ridge, (b) convergence of the optimality gap with one standard deviation, and (c) cumulative regret over time.
Figure 8: Performance of ARC-DuelLi on the Sharp reward function, averaged over independent runs. From left to right: (a) convergence of the reference arm on the utility landscape, (b) convergence of the optimality gap with one standard deviation, and (c) cumulative regret as a function of the number of comparisons.
Figure 9: Performance of ARC-DuelLi on the Two Peaks reward function, averaged over independent runs. From left to right: (a) convergence of the reference arm toward the global optimum despite the presence of a competing local optimum, (b) convergence of the optimality gap with one standard deviation, and (c) cumulative regret over time.
Figure 10: Performance of ARC-DuelLi under five transfer functions—sigmoid, arctangent, probit, linear, and hyperbolic tangent—averaged over independent runs. From left to right: (a) convergence of the reference arm, (b) convergence of the preference gap with one standard deviation, and (c) cumulative regret over time. .
Figure 11: Convergence of the preference gap for higher-dimensional action spaces under ARC-DuelLi . Panel (a) shows the convergence of for an ambient dimension of , while Panel (b) shows the corresponding convergence for . In both settings, the preference gap decreases with the number of rounds, indicating that the reference arm progressively approaches the optimal arm.