Introduction
In the evolving landscape of machine learning, Reinforcement Learning from Human Feedback (RLHF) has become a cornerstone for aligning large-scale models with human values. However, most existing frameworks for preference-based learning assume that actions are "free." In reality, online decision-making is often governed by strict resource constraints, such as limited computational budgets, human labor hours, or financial costs.
This paper introduces the problem of Preference-based Stochastic Linear Contextual Bandits with Knapsacks (PbLinCBwK). This framework bridges the gap between "Dueling Bandits" (which handle pairwise preferences) and "Bandits with Knapsacks" (which handle resource constraints). We propose the first near-optimal algorithms for this setting, utilizing a novel application of Lyapunov drift analysis to manage budget consumption without requiring the restrictive "warm-up" phases seen in prior literature.
The PbLinCBwK Problem
In a traditional multi-armed bandit problem, a learner receives a numerical reward. In PbLinCBwK, the learner instead observes a preference between two actions (a "duel"). Given a context, the learner chooses two actions $(x_t, y_t)$, and the environment returns a preference based on a latent reward parameter $\theta_*$, typically modeled via the Bradley-Terry model. Simultaneously, each action consumes a resource according to a latent cost parameter $\omega_*$. The process terminates either at time $T$ or when the total budget $B$ is exhausted.
Algorithmic Framework
We propose a primal-dual framework that decouples the estimation of model parameters from the management of the budget. Our approach consists of three primary components:
1. Parameter Estimation
The learner maintains estimates of the reward vector $\theta_*$ and the cost vector $\omega_*$. We use regularized Maximum Likelihood Estimation (MLE) for the preference model and least-squares estimation for the costs. To ensure robust learning, we employ a symmetric action selection strategy for the duels.
2. The Budget Pacer (Dual Module)
To handle the knapsack constraint, we maintain a virtual queue $Q_t$. This queue tracks the cumulative over-consumption of the budget. In optimization terms, $Q_t$ acts as a dynamic Lagrange multiplier. If the budget is being consumed too quickly, $Q_t$ increases, signaling the algorithm to prioritize actions with lower costs, even if they offer lower predicted rewards.
3. Exploration Strategies (Primal Module)
We provide two methods for action selection:
- Algorithm 1 (Optimistic): Uses Upper Confidence Bound (UCB) bonuses to encourage exploration of uncertain actions.
- Algorithm 2 (Randomized): Employs a Thompson Sampling-style approach, adding Gaussian noise to the estimates to facilitate exploration.
Theoretical Contributions
The core theoretical innovation is the use of Lyapunov drift analysis to bound regret. Unlike previous Bandits with Knapsacks (BwK) algorithms that require a large initial budget ($B = \Omega(T^{3/4})$) to estimate the optimal reward-to-cost ratio, our Lyapunov-based approach is adaptive and anytime-valid.
We prove that our algorithms achieve a regret bound of: $$O\left(\left(\kappa + \frac{T\nu^*}{B}\right)\sqrt{T} \log T\right)$$
Here, $\kappa$ represents the difficulty of the preference feedback (the link function's gradient), and $\nu^*$ is the optimal reward-to-cost ratio. Notably, our algorithms remain near-optimal even under the mild condition $B = \Omega(\sqrt{T})$, a significant improvement over the state-of-the-art.
Empirical Evaluation
We validated our framework through two primary experiments:
- Synthetic PbBwK: We compared our algorithms against the "CD-EXP3" baseline in a controlled environment. Our methods demonstrated significantly faster convergence and lower total regret, particularly as the time horizon increased.
- Online Content Moderation: Using the UCI Car Evaluation dataset, we simulated a content moderation task. A moderator must select reviews to display based on user preferences while constrained by a fixed "human evaluation" budget. The results showed that our budget-aware algorithms effectively maximized user satisfaction while staying within resource limits, whereas budget-agnostic methods failed early due to resource exhaustion.
Conclusion
This work provides a robust theoretical and practical foundation for preference-based learning under resource constraints. By replacing traditional warm-up phases with Lyapunov drift analysis, we achieve near-optimal performance in tighter budget regimes. Future work will explore extending this framework to non-linear reward functions and multi-dimensional resource constraints.
Summary updated