Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Bandits with Preference Feedback: A Stackelberg Game Perspective
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MaxMinLCB, a zero-sum Stackelberg game over LCB-based action pairs for dueling bandits with kernelized (RKHS) utilities, backed by new anytime-valid preference-based confidence sequences for kernelized logistic estimators.
Problem
Bandit optimization over infinite continuous domains with only pairwise preference feedback, where the learner must jointly choose two actions and balance exploration and exploitation for nonlinear (RKHS) utilities.
Approach
Jointly select the action pair as the equilibrium of a zero-sum Leader-Follower Stackelberg game on the LCB of the preference function, paired with kernelized logistic confidence sequences built via a dueling kernel that removes the regression-based assumptions of prior work.
Key results
- On Ackley with T=2000, MaxMinLCB attains dueling regret 56 ± 2 versus 65 ± 0.5 for MultiSBM and 72 ± 2 for Doubler.
- MaxMinLCB has the lowest regret on 6 of 8 test problems, e.g., Eggholder 113 ± 6 vs 134 ± 3 for MultiSBM.
- Theoretical anytime dueling regret of O(gamma_T sqrt(T)), improving the concurrent likelihood-ratio analysis by a factor of T^{1/4}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Stackelberg MaxMinLCB acquisition function instead of MultiSBM | Kernelized preference-feedback bandits · Branin | dueling regret: 104 ± 13 vs 89 ± 13 | Hurt |
| Use the Stackelberg MaxMinLCB acquisition function instead of MultiSBM | Kernelized preference-feedback bandits · Matyas | dueling regret: 125 ± 5 vs 106 ± 7 | Hurt |
| Use the Stackelberg MaxMinLCB acquisition function instead of MultiSBM | Kernelized preference-feedback bandits · Rosenbrock | dueling regret: 27 ± 4 vs 25 ± 5 | Hurt |
| Use the Stackelberg MaxMinLCB acquisition function instead of MultiSBM | Kernelized preference-feedback bandits · Ackley | dueling regret: 56 ± 2 vs 65 ± 0.5 | Helped |
| Use the Stackelberg MaxMinLCB acquisition function instead of MultiSBM | Kernelized preference-feedback bandits · Eggholder | dueling regret: 113 ± 6 vs 134 ± 3 | Helped |
| Use the Stackelberg MaxMinLCB acquisition function instead of IDS | Kernelized preference-feedback bandits · Hoelder | dueling regret: 141 ± 26 vs 132 ± 15 | Hurt |
| Use the Stackelberg MaxMinLCB acquisition function instead of MultiSBM | Kernelized preference-feedback bandits · Michalewicz | dueling regret: 138 ± 14 vs 155 ± 10 | Helped |
| Use the Stackelberg MaxMinLCB acquisition function instead of MultiSBM | Kernelized preference-feedback bandits · Yelp | dueling regret: 175 ± 22 vs 199 ± 25 | Helped |
| Use kernelized logistic estimation rather than kernelized ridge-regression estimation | Logistic GP-UCB · Ackley logistic-feedback bandit | cumulative regret | Helped |
Surprising findings
- MultiSBM outperforms MaxMinLCB on the smooth Matyas function (106 vs 125), and RUCB and MultiSBM match or beat MaxMinLCB on Branin and Matyas.
Limitations
- Regret bound is proven for the Leader's action restricted to the plausible-maximizer set M_t, which is not what the experiments use; the unrestricted case is only conjectured.
- Theory assumes RKHS norm bounds and a specific kernel regularity assumption; the sigmoid-based bound depends on kappa and L constants.
- Experiments use a uniform mesh of 100 points for test functions and only simulated preference feedback, with the Yelp experiment using collaborative-filtering-imputed ratings.
Experimental setup
Datasets: Yelp restaurant reviews
Benchmarks: Branin Matyas Rosenbrock Ackley Eggholder Hoelder Michalewicz Yelp
Metrics: cumulative dueling regret
Baselines: Doubler MultiSBM RUCB MaxInfo IDS GP-UCB UCB LogUCB
Builds on: MaxInfo IDS LGP-UCB GP-UCB
Closest papers by meaning
- Greedy Sampling Is Provably Efficient For RLHF (NeurIPS 2025 · similarity 0.89)
- A Minimaximalist Approach to Reinforcement Learning from Human Feedback (ICML 2024 · similarity 0.89)
- Combinatorial Reinforcement Learning with Preference Feedback (ICML 2025 · similarity 0.89)
- DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback (ICLR 2025 · similarity 0.88)
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.88)
- Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.