# Continuum-armed Bandit Optimization with Batch Pairwise Comparison Oracles

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 45 references that are in the map.
- First posted on arXiv 28 May 2025.

## Builds on (most cited first, 6 of 6)

- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Adversarial Dueling Bandits](https://mlsanity.com/paper/2010.14563/) (2020)
- [Regret Analysis for Continuous Dueling Bandit](https://mlsanity.com/paper/1711.07693/) (2017)
- [Optimization of Smooth Functions with Noisy Observations: Local Minimax Rates](https://mlsanity.com/paper/1803.08586/) (2018)
- [Online Pricing with Offline Data: Phase Transition and Inverse Square Law](https://mlsanity.com/paper/1910.08693/) (2019)
- [An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem](https://mlsanity.com/paper/2209.12108/) (2022)

## Abstract (arXiv)

This paper studies a bandit optimization problem where the goal is to maximize a function f(x) over T periods for some unknown strongly concave function f. We consider a new pairwise comparison oracle, where the decision-maker chooses a pair of actions (x, x') for a consecutive number of periods and then obtains an estimate of f(x)-f(x'). We show that such a pairwise comparison oracle finds important applications to joint pricing and inventory replenishment problems and network revenue management. The challenge in this bandit optimization is twofold. First, the decision-maker not only needs to determine a pair of actions (x, x') but also a stopping time n (i.e., the number of queries based on (x, x')). Second, motivated by our inventory application, the estimate of the difference f(x)-f(x') is biased, which is different from existing oracles in stochastic optimization literature. To address these challenges, we first introduce a discretization technique and local polynomial approximation to relate this problem to linear bandits. Then we developed a tournament successive elimination technique to localize the discretized cell and run an interactive batched version of LinUCB algorithm on cells. We establish regret bounds that are optimal up to poly-logarithmic factors. Furthermore, we apply our proposed algorithm and analytical framework to the two operations management problems and obtain results that improve state-of-the-art results in the existing literature.