Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources

Rohan Deb, Aadirupa Saha

Abstract

In many real-world online learning scenarios, feedback is provided as pairwise preferences rather than absolute numerical rewards, a framework known as the Dueling Bandit (DB) problem. However, practical applications often operate under strict resource constraints, such as limited advertising budgets or finite inventory. This paper introduces the Constrained Dueling Bandit (CDB) framework, bridging the gap between preference learning and the "Bandits with Knapsacks" literature. We demonstrate that relative feedback introduces unique complexities, making the problem fundamentally harder than its standard bandit counterpart. We propose Constrained D-EXP3, an algorithm that balances preference estimation with cost-awareness, achieving sub-linear regret. Our results, validated on synthetic and real-world car preference datasets, highlight the necessity of budget-pacing in dueling scenarios.

Introduction

The Dueling Bandit (DB) problem is a robust model for scenarios where numerical rewards are difficult to quantify, such as movie recommendations ("Do you prefer Movie A or B?") or search engine optimization. While standard multi-armed bandits (MAB) assume a direct reward signal for every action, DB relies on the outcome of a duel between two arms.

Despite the popularity of DB, existing literature largely ignores the resource constraints that define real-world decision-making. An advertiser has a limited budget; a retailer has finite stock. In standard bandits, these constraints are addressed by the "Bandits with Knapsacks" (BwK) framework. However, the dueling version presents a unique challenge: feedback is relative. To identify the optimal arm, an agent must compare it to others, but if the budget for the "best" arm is exhausted prematurely, the agent may be left with remaining resources but no way to identify the next-best alternative efficiently. This paper explores the solvability of this problem and provides the first algorithmic solution for constrained preference learning.

The Constrained Dueling Bandit Framework

The authors identify that relative feedback acts as a "budget sink." In standard bandits, every pull provides a signal about an arm's absolute value. In the dueling setup, a signal only reveals the difference between two arms. This leads to a critical theoretical insight: if the budget $B$ is too small (specifically $B = o(K/\epsilon^2)$), it becomes impossible to distinguish between arms, resulting in unavoidable linear regret.

Furthermore, without structural assumptions like Strong Stochastic Transitivity (SST)—where preference relations are consistent and predictable—playing sub-optimal arms provides no information about the ranking of the optimal arms. This makes the general CDB problem significantly more difficult than unconstrained versions.

Methodology: Constrained D-EXP3

To address these challenges, the authors propose Constrained D-EXP3 (also known as "Vigilant D-EXP3"). The algorithm is designed around two primary innovations:

  1. Primal-Dual Balancing: The algorithm employs a Lagrangian-based approach to navigate the trade-off between the Borda score (the probability that an arm wins against a randomly chosen opponent) and the resource consumption (the cost associated with pulling that arm).
  2. Dual Distribution Sampling: A common pitfall in constrained bandits is the "same-arm trap." Standard algorithms might pick the same arm twice to maximize reward, but in a dueling setup, comparing an arm to itself ($P(i, i) = 0.5$) yields zero information. Constrained D-EXP3 maintains two distinct probability distributions ($q^x$ and $q^y$) to sample the two arms for each duel, ensuring that comparisons remain informative for preference learning.

Theoretical analysis establishes that Constrained D-EXP3 achieves a sub-linear regret bound of $\tilde{O}\left(\frac{OPT}{B} K^{1/3} T^{2/3}\right)$, proving that the average loss compared to an optimal budget-aware strategy vanishes over time.

Experimental Evaluation

The approach was evaluated using both synthetic and real-world data:

  • Synthetic Environment: A 6-arm setup where Borda scores and costs were intentionally decoupled. For instance, the most preferred arms were also the most expensive. This tested the algorithm's ability to find a middle ground between preference and sustainability.
  • Car Preference Dataset: Utilizing a real-world dataset of 10 car models, the authors derived a preference matrix based on attributes like fuel consumption and transmission type. This provided a realistic landscape for testing how the algorithm handles complex user preferences under simulated budget constraints.

Key Results and Insights

The experiments revealed a clear distinction between budget-aware and budget-blind strategies. Standard dueling bandit algorithms, such as D-Thompson Sampling, often performed well in the early stages but suffered a "crash" once they exhausted the budget on high-cost, high-preference arms. In contrast, Constrained D-EXP3 paced its resource consumption. By occasionally choosing slightly less preferred but significantly cheaper arms, it maintained the ability to learn and earn rewards over the entire time horizon $T$, ultimately yielding higher total utility.

Another significant insight involves the choice of the winner criterion. While the Condorcet winner (an arm that beats all others) is the traditional goal in dueling bandits, it is difficult to estimate under constraints because elimination-based strategies fail if the winner is removed due to budget exhaustion. The authors found the Borda winner to be a more robust benchmark for constrained environments.

Conclusion and Future Work

This paper formalizes the Constrained Dueling Bandit problem and provides a theoretically grounded algorithm to solve it. While Constrained D-EXP3 marks a significant step forward, the authors note several areas for future research. Currently, the algorithm relies on a relatively high budget assumption to maintain its regret bounds. Additionally, while Thompson Sampling variants often outperform EXP3-based methods in unconstrained settings, a "Constrained Dueling Thompson Sampling" algorithm remains an open and promising challenge for the field.

Summary updated

BibTeX
@inproceedings{deb2024think,
  author = {Rohan Deb and Aadirupa Saha},
  title = {{Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=Tkcq4gShqY},
}
Figure