Source-linked AI summary
Contextual Dueling Bandits
Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, Masrour Zoghi
TL;DR
The paper studies contextual action selection from limited relative feedback, where the learner seeks a good policy despite ambiguity about what “best” means. It introduces the game-theoretic von Neumann winner, develops online and batch-like algorithms for learning or approximating it, and addresses scalability through classification-oracle methods. The online sparring method handles adversarial data with low regret but scales linearly in the policy-space size, while the other algorithms achieve logarithmic dependence when given the required oracle.
Problem
The paper addresses contextual policy learning from partial pairwise comparisons while relaxing restrictive assumptions and retaining flexibility for very large policy spaces.
Method
It defines a randomized von Neumann winner and develops sparring, Follow-the-Perturbed-Leader, and projected-gradient algorithms for online learning or batch-like approximation.
Results
The paper presents algorithms that approximate or perform as well as a von Neumann winner, including an adversarially robust linear-|Π| method and oracle-based methods with logarithmic dependence on |Π|.
Takeaways & Limitations
A randomized policy that beats or ties every policy provides an always-existing target for contextual dueling-bandit learning.
Takeaways & Limitations
The sparring approach requires time and space proportional to |Π|, while the compact algorithms rely on access to a classification oracle and omit exploitation-round execution details.
Abstract
from arXiv · showhide
We consider the problem of learning to choose actions using contextual information when provided with limited feedback in the form of relative pairwise comparisons. We study this problem in the dueling-bandits framework of Yue et al. (2009), which we extend to incorporate context. Roughly, the learner's goal is to find the best policy, or way of behaving, in some space of policies, although "best" is not always so clearly defined. Here, we propose a new and natural solution concept, rooted in game theory, called a von Neumann winner, a randomized policy that beats or ties every other policy. We show that this notion overcomes important limitations of existing solutions, particularly the Condorcet winner which has typically been used in the past, but which requires strong and often unrealistic assumptions. We then present three efficient algorithms for online learning in our setting, and for approximating a von Neumann winner from batch-like data. The first of these algorithms achieves particularly low regret, even when data is adversarial, although its time and space requirements are linear in the size of the policy space. The other two algorithms require time and space only logarithmic in the size of the policy space when provided access to an oracle for solving classification problems on the space.
1. Introduction
The paper extends dueling bandits to contextual policy learning with partial, relative feedback and seeks methods applicable to very large policy spaces. It introduces a randomized von Neumann winner and develops online and oracle-based algorithms addressing limitations of prior approaches.
- Problem setting: Contextual dueling bandits use user or query context to choose policies from pairwise feedback about candidate actions.The motivating applications include information retrieval and recommender systems, where relative comparisons can be more reliable than absolute labels.
- Problem setting: The policy space Π may be extremely large or infinite, motivating methods with flexibility comparable to supervised learning algorithms.The paper explicitly targets settings where Π is exponential in a reasonable complexity measure.
- Contributions: The paper aims to relax prior modeling restrictions while retaining flexible policy design, including assumptions associated with closely related dueling-bandit methods.The discussion specifically contrasts the approach with DBGD’s convexity assumption.
- Solution concept: A von Neumann winner is a randomized policy that beats or ties every policy, and it is guaranteed to exist without extraneous assumptions.Randomization removes the non-existence issue associated with requiring one deterministic policy to beat every other policy.
- Algorithms: A sparring algorithm runs two Exp4.P copies against one another, achieving good regret but requiring time and space linear in |Π|.This makes the approach impractical when the policy space is enormous, despite its favorable regret and adversarial-data handling.
- Algorithms: Two further algorithms use a classification oracle and achieve data, time, and space requirements that depend logarithmically on |Π|.The oracle finds a minimum-cost policy for costs assigned to actions across contexts.
2. Dueling bandits and the von Neumann winner
Relative pairwise feedback makes the best action ambiguous because a Condorcet winner may not exist. Allowing randomized choices yields the von Neumann winner, which always exists and is characterized through zero-sum game theory.
- Dueling-bandit model: A dueling bandit learner compares pairs of actions through stochastic duels whose outcomes reveal relative rather than absolute quality.The preference matrix records expected duel outcomes and is assumed skew-symmetric, with no further structural assumptions in the paper’s setting.
- Solution concept: A Condorcet winner beats every other action, but dueling-bandit problems without such a winner arise regularly in practice.Thus, the conventional solution concept can fail to provide a target action.
- Solution concept: Randomized action selection eliminates the non-existence problem by seeking a distribution that beats every fixed opponent with probability at least 1/2.This distribution is called a von Neumann winner for the preference matrix.
- Game-theoretic interpretation: The preference matrix defines a zero-sum matrix game in which randomized actions are mixed strategies and the payoff is w^T P u.The von Neumann construction is connected to maxmin and minmax strategies through the minimax theorem.
- Game-theoretic interpretation: A probability vector is a von Neumann winner if and only if it is a maxmin strategy, so every preference matrix has a von Neumann winner.This is the paper’s formal existence result.
3. Incorporating context
The contextual extension treats policies as meta-actions whose pairwise preference is averaged over randomly selected contexts and preference matrices. A contextual von Neumann winner is therefore a distribution over policies that beats or ties every policy, although computing it is challenging for huge policy spaces.
- Contextual setting: In the contextual setting, the learner observes a context while the relevant preference matrix remains hidden and may vary across rounds.The goal is to choose actions as a function of observable context.
- Policies: A policy is a context-to-action mapping drawn from a policy space Π that may be exponentially large.The policy space can represent objects such as decision trees.
- Meta-actions: The contextual reduction treats each policy as a meta-action and constructs a preference matrix M indexed by policies.This converts contextual policy comparison into a non-contextual comparison over meta-actions.
- Meta-actions: A meta-duel between policies samples (x, P) and compares the actions selected by the two policies under that context and preference matrix.The resulting matrix encodes the expected outcome of policy-versus-policy duels.
- Contextual winner: A contextual von Neumann winner is a distribution over policies that beats or ties every opposing policy and must exist.The existence follows by applying the non-contextual result to M.
- Computational challenge: Computing or approximating contextual von Neumann winners is difficult because both Π and its corresponding matrix M can be gigantic.The remainder of the paper therefore focuses on computational methods for this problem.
4. Learning scenarios
The paper studies explore-then-exploit learning from actively collected duel data and fully online learning measured by regret. The first seeks an approximate contextual winner after exploration, while the second seeks sublinear regret against competing policies.
- Learning scenarios: The paper considers explore-then-exploit and fully online learning scenarios.The two settings differ in whether learning ends after an exploration phase or continues across T rounds.
- Explore-then-exploit: In explore-then-exploit, the learner actively selects action pairs for m exploratory duels and outputs an ε-approximate von Neumann winner.The output must beat every policy with probability at least 1/2 − ε/2.
- Fully online learning: In the fully online setting, performance is measured by regret over T rounds with changing preference matrices and policies.The paper defines regret for this contextual, policy-based setting rather than relying only on a static preference matrix.
- Fully online learning: If regret is o(T), the selected action pairs eventually cannot be beaten by any policy in Π.This gives the operational goal for the online learning scenario.
- Regret: The paper notes that its online regret notion specializes to the earlier Condorcet-based notion under the same assumptions, up to constant factors.The equivalence is stated for the standard static-preference setting.
5. Sparring Exp4.P
SparringEXP4.P runs two contextual Exp4.P learners against each other, using duel outcomes as opposing feedback. It supports adversarial data and achieves regret guarantees, but its computation scales linearly with the policy space.
- Algorithm: Exp4.P is suited to this construction because it handles partial information, adversarially generated data, and contextual policies.The algorithm is designed for bandit feedback and expert advice in contextual settings.
- Algorithm: SparringEXP4.P runs row-Exp and column-Exp, two Exp4.P copies that select actions from the revealed context and receive opposite duel feedback.The row learner receives outcome r for its action, while the column learner receives -r.
- Guarantee: Theorem 2 gives SparringEXP4.P a high-probability regret bound for K actions, policy space Π, and horizon T.The supplied theorem statement introduces the bound, while its displayed expression is truncated here.
- Guarantee: The guarantee also holds when the context-preference pairs are selected adversarially rather than randomly.The algorithm can additionally be converted to explore-then-exploit learning by averaging the row learner's distributions over exploration rounds.
- Limitation: The algorithm's very good regret bounds come with time and space requirements proportional to |Π|, limiting practicality for extremely large policy spaces.This linear dependence motivates later oracle-based methods.
6. Explore-then-exploit algorithms with a classification oracle
The explore-then-exploit approach estimates policy-versus-policy preferences from exploration data and solves a compact game over policy vectors. With a classification oracle, SparringFPL and ProjectedGD compute approximate von Neumann winners with explicit sample, oracle, time, and storage guarantees.
- Exploration and estimation: Uniform exploration produces an unbiased estimate of each hidden preference matrix from one randomly selected duel per exploration round.The estimator sets the observed pair's entry to K^2r_i and all other entries to zero.
- Exploration and estimation: Non-adaptive exploration can be preferable in large-scale applications when existing infrastructure cannot support adaptive feedback loops.The paper notes that infrastructure upgrades may be infeasible in the near term.
- Exploration and estimation: The estimated meta-duel outcome for two policies has expectation equal to the corresponding entry of the policy preference matrix.Bernstein's inequality and a union bound provide the associated high-probability uniform control.
- Exploration and estimation: The empirical preference matrix approximates the population matrix closely enough that an approximate maxmin strategy for the empirical matrix suffices for the original problem.This connection underlies the paper's statistical reduction from noisy data to optimization.
- Game reduction: The resulting solution is a (2ε′ + ε)-approximate von Neumann winner when the empirical approximation and optimization errors satisfy their stated conditions.This combines statistical estimation error with the optimization approximation guarantee.
- Game reduction: Policy vectors encode each policy's actions on exploration contexts, and their convex hull converts the enormous policy game into a constrained optimization problem.The block-diagonal matrix B preserves empirical policy-versus-policy payoffs through v_π^T Bv_ρ.
- Oracle-based algorithms: A classification oracle returns the minimum-cost policy for a sequence of action-cost vectors, making the oracle assumption equivalent to cost-sensitive multiclass classification.This assumption is intended to support policy classes that may be extremely large or infinite.
- Oracle-based algorithms: SparringFPL and ProjectedGD solve the policy-hull optimization problem to compute an approximate von Neumann winner.They adapt Follow-the-Perturbed-Leader and online projected gradient descent to maintain the required constraint.
7. Solving the compact game with SparringFPL
SparringFPL solves the compact game by running two FPL players against each other, with classification-oracle calls implementing the optimization over the policy hull. With N = O(K^4/ε^2)(m + ln(1/δ)) steps, it obtains an ε-approximate solution with probability 1−δ.
- Algorithm: SparringFPL solves the compact game by sparring row-FPL and column-FPL, which select strategies against each other in a repeated game.Row-FPL chooses w_t, column-FPL chooses u_t, and their loss vectors are constructed from the game matrix.
- Algorithm: The algorithm uses uniform random perturbations and cumulative opponent strategies to define each FPL decision.The argmin problems are solved over the policy hull C.
- Oracle implementation: Classification-oracle calls implement the argmin expressions, returning vectors in C that correspond to mixtures of policies.The returned vector can be represented as a uniform mixture of N policies.
- Guarantee: N = O(K^4/ε^2)(m + ln(1/δ)) steps suffice to find an ε-approximate solution with probability 1−δ.The parameter choice α = √(2/(K^4N)) yields the stated guarantee.
8. Solving the compact game with ProjectedGD
ProjectedGD solves the compact game by updating a strategy with projected gradient steps while approximating projections back onto the policy hull. Its guarantees depend on the number of outer and inner iterations, with O(K^8/ε^4) oracle calls sufficient for an ε-approximate solution.
- Algorithm: ProjectedGD updates the row strategy with a gradient step and approximately projects the result back onto the policy hull C.Each column strategy is chosen as a best response to the current row strategy.
- Approximate projection: ApproxProject uses a supplied vector in C as an initial guess for projecting an arbitrary vector back onto C.The approximation quality may depend on the initial guess’s proximity to the actual projection.
- Guarantee: With η = 2/(L√N_out), ProjectedGD finds an ε-approximate solution where ε = 2L/√N_out + Lα/2.The guarantee is established for the algorithm’s chosen outer-loop step size.
- Approximate projection: The projection procedure maximizes a function F that is linear in s and concave in v, using repeated game play between best response and online gradient ascent.The maximizing vector is exactly the projection of z onto C, although the algorithm does not require that fact.
- Implementation: The approximate-projection iterations update v_t through convex combinations with best-response vectors, keeping every iterate and the final average in C.Convexity of C ensures v_t and the returned v remain in the policy hull.
- Guarantee: O(K^8/ε^4) oracle calls suffice to obtain an ε-approximate solution to the compact game.The bound follows by optimizing the numbers of inner and outer iterations.
Appendix A. Failure of the Condorcet winner to exist
An experiment using ranker-evaluation dueling bandits finds that Condorcet winners become rapidly less common as the number of rankers increases. The result challenges the practicality of assuming that a Condorcet winner exists, especially in contextual policy spaces.
- Experiment: The experiment replicates a ranker-evaluation setting using probabilistic interleave comparisons and click models simulating user behavior.It considers a family of K-armed dueling-bandit problems.
- Result: The probability that the encountered problems contain a Condorcet winner drops rapidly as the number of rankers grows.This trend is shown in Figure 1.
- Implication: The findings characterize the Condorcet-winner assumption as too unreliable for practical use even in a simple non-contextual example.The paper argues that the assumption is even less realistic for large and diverse contextual policy spaces.
Appendix B. Comparison between the Copeland and von Neumann winners
The comparison finds that von Neumann winners avoid Copeland’s instability and generally align with Copeland winners in sampled MSLR preference matrices, while usually having small supports.
- Copeland winners can lose to non-Copeland arms and change when identical clones are introduced, whereas von Neumann winners beat or tie every arm.
- A duplicated-arm construction excludes a2 from the Copeland winners even though a0, a1, a2, and a3 remain in the von Neumann winner’s support.
- Copeland’s lack of stability under cloning is identified as a major drawback of using its score as a quality measure.
- Over 99.9% of sampled MSLR matrices had a von Neumann winner containing at least one Copeland winner.
- Arms supported by the von Neumann winner tend to have high Copeland scores, or equivalently low Copeland losses.
- Among more than a million sampled MSLR matrices, no von Neumann winner supported more than 5 arms, and most had support size 1 or 3.
Appendix C. Analysis of SparringEXP4.P (proof of Theorem 2)
The SparringEXP4.P analysis constructs unbiased pairwise reward estimates for both learners and applies concentration and adversarial online-learning arguments to establish the theorem’s guarantee.
- For each action pair, the analysis defines a {−1, +1}-valued random variable with expected value equal to the corresponding preference-matrix entry.
- Only the selected action pair is used in the actual duel; the other pairwise reward variables support the mathematical analysis.
- Row-Exp receives rewards based on its comparison with column-Exp’s action, while column-Exp receives the negated rewards for those same comparisons.
- Azuma’s lemma and union bounds provide simultaneous high-probability control over the policy comparisons for both row-Exp and column-Exp.
- The appendix extends the analysis to arbitrary unbiased estimators bounded by L with variance at most V; uniform exploration has both bounds equal to K^2.
- For an ε-approximate solution, the required number of rounds is O(L^2/ε^2)(m + ln(1/δ)), with two oracle calls per round.
- The proof concludes by combining the row and column analyses with the maxmin argument to establish the returned vector’s guarantee.
D.4. Analysis of ProjectedGD: inner loop
The ProjectedGD inner-loop analysis bounds approximate projection error and combines it with the outer procedure to obtain an ε-approximate maxmin solution.
- ApproxProject analyzes the projection of z onto the policy hull using the potential function ∥v*−v_t∥^2.
- The projection analysis uses a step size ν = ∥z − v1∥/√N_in and error parameter δ = 8∥z − v1∥/√N_in.
- The proof controls the inner-loop error using a quadratic inequality, summation over iterations, and the selected step size.
- ApproxProject satisfies the required specification with α = 8/√N_in.
- The combined algorithm achieves ε = 2L/√N_out + 4L/√N_in; choosing N_in = N_out = 36L^2/ε^2 yields O(L^4/ε^4) classification-oracle calls.