# Zeroth Order Non-convex optimization with Dueling-Choice Bandits

arXiv: https://arxiv.org/abs/1911.00980 · HTML: https://mlsanity.com/paper/1911.00980/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2019.

## Built on by (most cited first, 11 of 11)

- [Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2205.11140/) (2022)
- [Sample Efficient Preference Alignment in LLMs via Active Exploration](https://mlsanity.com/paper/2312.00267/) (2023)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [Bias-Robust Bayesian Optimization via Dueling Bandits](https://mlsanity.com/paper/2105.11802/) (2021)
- [Bandits with Preference Feedback: A Stackelberg Game Perspective](https://mlsanity.com/paper/2406.16745/) (2024)
- [Large Language Model-Enhanced Multi-Armed Bandits](https://mlsanity.com/paper/2502.01118/) (2025)
- [Kernelized Offline Contextual Dueling Bandits](https://mlsanity.com/paper/2307.11288/) (2023)
- [Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2505.23673/) (2025)
- [Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-Fidelity Feedback](https://mlsanity.com/paper/2110.07232/) (2021)
- [Lipschitz Dueling Bandits over Continuous Action Spaces](https://mlsanity.com/paper/2604.00523/) (2026)
- [A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback](https://mlsanity.com/paper/2604.25025/) (2026)

## Abstract (arXiv)

We consider a novel setting of zeroth order non-convex optimization, where in addition to querying the function value at a given point, we can also duel two points and get the point with the larger function value. We refer to this setting as optimization with dueling-choice bandits since both direct queries and duels are available for optimization. We give the COMP-GP-UCB algorithm based on GP-UCB (Srinivas et al., 2009), where instead of directly querying the point with the maximum Upper Confidence Bound (UCB), we perform a constrained optimization and use comparisons to filter out suboptimal points. COMP-GP-UCB comes with theoretical guarantee of O(fracPhi√T) on simple regret where T is the number of direct queries and Phi is an improved information gain corresponding to a comparison based constraint set that restricts the search space for the optimum. In contrast, in the direct query only setting, Phi depends on the entire domain. Finally, we present experimental results to show the efficacy of our algorithm.