Online Convex Optimization with Dueling Feedback
cs.LG
Submitted: 2026-08-15
Updated: 2026-09-28
License: http://creativecommons.org/licenses/by-sa/4.0/
The gist: We study online convex optimization with dueling (pairwise comparison) feedback, where the learner observes only a binary preference between two queried points.
Terminology
Abstract
We study online convex optimization with dueling (pairwise comparison) feedback, where the learner observes only a binary preference between two queried points. While dueling feedback is well understood in discrete or stochastic settings, the adversarial convex setting has remained unexplored. We propose a simple reduction that converts dueling feedback into approximate gradients, enabling the use of standard first-order methods. We show that regret guarantees transfer under this reduction, yielding the first results for this setting, including O(T 3/4) static, adaptive, and dynamic regret. Under additional structure, we obtain improved rates of O(T 2/3) for smooth objectives and O(sqrt T T) for strongly convex functions.
Sources
- BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access
- Lipschitz Dueling Bandits over Continuous Action Spaces
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks