Lipschitz Dueling Bandits over Continuous Action Spaces

2026-04-01 · Mudit Sharma, Shweta Jain, Vaneet Aggarwal, Ganesh Ghalme arxiv

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.

📄 PDF Abstract BibTeX arXiv:2604.00523

Code (0)

등록된 구현이 없습니다.

KLUCB Approach to Copeland Bandits

2019-02-07 · Nischal Agrawal, Prasanna Chaporkar

Multi-armed bandit(MAB) problem is a reinforcement learning framework where an agent tries to maximise her profit by proper selection of actions through absolute feedback for each action. The dueling bandits problem is a…

Information Retrieval Reinforcement Learning Retrieval Thompson Sampling

Simple Algorithms for Dueling Bandits

2019-06-18 · Tyler Lekang, Andrew Lamperski

In this paper, we present simple algorithms for Dueling Bandits. We prove that the algorithms have regret bounds for time horizon T of order O(T^rho ) with 1/2 <= rho <= 3/4, which importantly do not depend on any prefer…

Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms

2014-05-19 · Stefan Magureanu, Richard Combes, Alexandre Proutiere

We consider stochastic multi-armed bandit problems where the expected reward is a Lipschitz function of the arm, and where the set of arms is either discrete or continuous. For discrete Lipschitz bandits, we derive asymp…

Multi-Armed Bandits

Utility-based Dueling Bandits as a Partial Monitoring Game

2015-07-10 · Pratik Gajane, Tanguy Urvoy

Partial monitoring is a generic framework for sequential decision-making with incomplete feedback. It encompasses a wide class of problems such as dueling bandits, learning with expect advice, dynamic pricing, dark pools…

Decision Making Sequential Decision Making

Double Thompson Sampling for Dueling Bandits

2016-04-25 · NeurIPS 2016 12 · Huasen Wu, Xin Liu

In this paper, we propose a Double Thompson Sampling (D-TS) algorithm for dueling bandit problems. As indicated by its name, D-TS selects both the first and the second candidates according to Thompson Sampling. Specifica…

Thompson Sampling