Introduction
In modern machine learning, preference-based feedback has become a cornerstone for aligning models with human values. From recommendation systems and search engine optimization to the fine-tuning of Large Language Models (LLMs) via Reinforcement Learning from Human Feedback (RLHF), it is often more practical to collect relative comparisons (e.g., "User prefers A over B") than absolute numerical scores. This paradigm is formalized as the Dueling Bandit problem.
However, preference data is inherently sensitive. A user’s choice between two options—whether they be medical treatments, news articles, or consumer products—can reveal deeply personal information. While Differential Privacy (DP) has emerged as the gold standard for data protection, its application to the active learning setting of dueling bandits remained largely unexplored. This paper introduces the first DP algorithms for dueling bandits, providing a framework to protect user privacy without significantly compromising the efficiency of the learning process.
The Privacy-Utility Trade-off in Dueling Bandits
The core challenge in designing private dueling bandit algorithms lies in the "regret"—the cumulative loss incurred by the learner when choosing suboptimal items during the exploration phase. To satisfy DP requirements, an algorithm must inject noise into its decision-making process to mask the influence of any single preference observation. The authors investigate whether this noise leads to a significant increase in regret and whether there are scenarios where privacy can be achieved "for free."
Methodological Framework
The authors propose two distinct algorithmic approaches tailored to the nature of the decision space: finite sets of items and general (potentially infinite) $d$-dimensional vector spaces.
1. DP-EBS-Elimination (Finite Case)
For scenarios involving a fixed set of $K$ items, the authors introduce DP-EBS-Elimination. This algorithm utilizes a round-robin comparison strategy and ranks items based on the Effective Borda Score (EBS), which represents the average probability of an item winning against all others in the set.
To ensure privacy, the algorithm incorporates a Binary Tree Mechanism. This mechanism adds calibrated noise to the win-loss counts over time, allowing the learner to maintain an accurate but private estimate of item rewards. This approach ensures that the cumulative feedback from any specific user interaction remains protected.
2. GOptimal-DPDB (General/Infinite Case)
In more complex settings where items are represented as $d$-dimensional vectors, the authors propose GOptimal-DPDB. This algorithm operates in discrete phases and employs G-Optimal Design to identify a small "core-set" of representative items for testing.
By focusing on this core-set, the algorithm can efficiently estimate the underlying reward vector using a Maximum Likelihood Estimator (MLE). Privacy is maintained by adding Laplace noise to the aggregated preference responses before the MLE is calculated. This structure allows the algorithm to leverage the geometric properties of the decision space, such as confidence ellipsoids, to guide exploration.
Key Results and "Privacy for Free"
The paper provides a rigorous theoretical analysis of the proposed algorithms, establishing both upper bounds on regret and information-theoretic lower bounds.
- Finite Arm Performance: The DP-EBS-Elimination algorithm achieves a regret bound of $O\left(\sum_{i=2}^K \frac{\log(KT)}{\Delta_i} + \frac{K}{\epsilon}\right)$. The first term represents the standard cost of learning in non-private settings, while the second term, $O(K/\epsilon)$, is the specific "price of privacy." The authors prove this is order-optimal, meaning no private algorithm can perform significantly better.
- Infinite Arm Performance: For $d$-dimensional spaces, the regret is bounded by $\tilde{O}\left(\frac{d^6}{\kappa\epsilon} + \frac{d\sqrt{T}}{\kappa}\right)$, where $\kappa$ is the sensitivity of the preference (link) function.
- The "Privacy for Free" Phenomenon: A significant insight of the study is that in the $d$-dimensional setting, when the time horizon $T$ is sufficiently large relative to the dimension $d$, the privacy-related term in the regret bound becomes negligible. In these instances, the cost of maintaining strict user privacy does not meaningfully degrade the long-term performance of the learner.
Discussion and Future Directions
This work bridges the gap between preference-based learning and differential privacy, but it also highlights several avenues for future research. Currently, the models assume a utility-based structure, where preferences are derived from underlying scores. This does not yet account for non-transitive or cyclic preferences (e.g., "rock-paper-scissors" scenarios).
Furthermore, the algorithms are designed for static environments where rewards do not change over time. Extending these private mechanisms to dynamic or adversarial settings, as well as developing personalized models that protect individual privacy while learning unique user preferences, remains a critical challenge for the field.
Summary updated