Abstract
We consider the problem of reward maximization in the dueling bandit setup along with constraints on resource consumption. As in the classic dueling bandits, at each round the learner has to choose a pair of items from a set of $K$ items and observe a relative feedback for the current pair. Additionally, for both items, the learner also observes a vector of resource consumptions. The objective of the learner is to maximize the cumulative reward, while ensuring that the total consumption of any resource is within the allocated budget. We show that due to the relative nature of the feedback, the problem is more difficult than its bandit counterpart and that without further assumptions the problem is not learnable from a regret minimization perspective. Thereafter, by exploiting assumptions on the available budget, we provide an EXP3 based dueling algorithm that also considers the associated consumptions and show that it achieves an $\tilde{\mathcal{O}}\left(\big({\frac{OPT^{(b)}}{B}}+1\big)K^{1/3}T^{2/3}\right)$ regret, where $OPT^{(b)}$ is the optimal value and $B$ is the available budget. Finally, we provide numerical simulations to demonstrate the efficacy of our proposed method.
1. Introduction
The Multi-Armed Bandit (MAB) framework has long been the standard for modeling sequential decision-making under uncertainty. However, many real-world applications—ranging from recommendation systems to clinical trials—rely on relative feedback (e.g., "User preferred Movie A over Movie B") rather than absolute numerical rewards. This has led to the development of the Dueling Bandits (DB) framework.
While DB models are effective, they often overlook a critical operational reality: resource constraints. In practice, every comparison or "duel" may consume finite resources such as time, energy, or budget. If a learner exhausts these resources on uninformative comparisons, they fail to identify the optimal items. This paper introduces the Constrained Dueling Bandits (Constrained-DB) framework to address this gap, exploring the theoretical limits and providing a robust algorithmic solution.
2. The Hardness of Relative Feedback
A central contribution of this work is the demonstration that Constrained-DB is fundamentally more difficult than its standard bandit counterpart (Constrained-MAB). In a standard bandit setting, playing an arm yields a direct reward signal. In a dueling setting, the learner must pair two arms to receive information.
This interdependence creates a "relative penalty." The authors prove that without sufficient budget ($B = o(K/\epsilon^2)$), the problem is not learnable from a regret minimization perspective, potentially leading to linear regret. Essentially, if the budget is too tight, the learner cannot statistically distinguish the best arm from its competitors before resources run out. However, by assuming properties like Strong Stochastic Transitivity (if A > B and B > C, then A is significantly better than C), the learner can infer relationships without direct, costly comparisons, making the problem tractable even under tighter constraints.
3. Methodology: Vigilant D-EXP3
To navigate the trade-off between preference learning and resource conservation, the authors propose Vigilant D-EXP3. This algorithm is designed to maximize the Borda winner's reward—the arm with the highest average win rate—while respecting budget limits.
3.1 Primal-Dual Framework
Vigilant D-EXP3 utilizes a primal-dual approach. It maintains Lagrange multipliers that act as dynamic penalties for resource consumption. As a specific resource nears exhaustion, the penalty for choosing arms that consume that resource increases, forcing the algorithm to "pace" its spending.
3.2 Sparring and Shifted Borda Scores
The algorithm employs a "sparring" technique, maintaining two probability distributions (one for each side of the duel) updated via an exponential weights (EXP3) rule. A key mathematical innovation is the use of Shifted Borda Scores. By shifting these scores, the authors decouple the two arms in a duel into separate optimization problems, significantly simplifying the learning process in a constrained environment.
4. Empirical Evaluation
The researchers validated Vigilant D-EXP3 using both synthetic and real-world datasets.
- Synthetic Simulations: In environments where high-reward arms were also high-cost, standard algorithms like D-EXP3 and Dueling Thompson Sampling (D-TS) failed by exhausting the budget prematurely. Vigilant D-EXP3 successfully identified "value" arms—those with high reward-to-cost ratios—and maintained performance throughout the experiment.
- Car Preference Dataset: Using real-world car preference data from a 2013 study, the authors simulated a constrained recommendation engine. Vigilant D-EXP3 consistently outperformed benchmarks, demonstrating its ability to adapt to complex, real-world preference matrices where budget management is essential.
5. Conclusion
The study of Constrained Dueling Bandits reveals that relative feedback introduces unique challenges for resource-aware learning. Vigilant D-EXP3 provides a theoretically grounded and empirically effective solution, achieving a regret bound of $\tilde{O}((\frac{OPT}{B} + 1) K^{1/3} T^{2/3})$.
Future research directions include closing the "Condorcet Gap" by developing budget-aware algorithms for Condorcet winners and exploring "Constrained Thompson Sampling" to leverage the empirical strengths of Bayesian methods in these settings. Additionally, making the algorithm fully parameter-free by removing the need for a "warm-up" phase to estimate budget parameters remains an open challenge.
Summary updated