Search papers, labs, and topics across Lattice.
This paper introduces the first algorithm for stochastic dueling bandits over continuous action spaces with Lipschitz structure, a setting where feedback is purely comparative and actions are continuous. The algorithm uses round-based exploration and recursive region elimination guided by an adaptive reference arm to efficiently explore the action space. The authors prove a regret bound of $\tilde O\left(T^{\frac{d_z+1}{d_z+2}}\right)$, where $d_z$ is the zooming dimension, and demonstrate logarithmic space complexity with respect to the time horizon.
Achieving near-optimal regret in continuous dueling bandits is now possible with just logarithmic space complexity, opening the door to efficient exploration in complex comparative decision-making problems.
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 $\tilde O\left(T^{\frac{d_z+1}{d_z+2}}\right)$, where $d_z$ 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.
