Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Borda Regret Minimization for Generalized Linear Dueling Bandits
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.
Studies Borda regret minimization for generalized linear dueling bandits, proving an Omega(d^{2/3}T^{2/3}) lower bound and giving an explore-then-commit algorithm (BETC-GLM) and an EXP3-type algorithm (BEXP3) that nearly match it.
Problem
Identifying the Borda winner in dueling bandits with contextual pair features while minimizing cumulative Borda regret, without assuming transitivity or a coherent ranking.
Approach
Uses pairwise contextual features with a generalized linear preference model and a Borda-based regret; an explore-then-commit algorithm with G-optimal design for the stochastic case and an EXP3-style exponential-weights algorithm with one-sample unbiased Borda estimates for the adversarial case, plus a matching hard-instance lower bound built from bit representations.
Key results
- Proves an Omega(d^{2/3}T^{2/3}) Borda regret lower bound for stochastic and adversarial linear dueling bandits.
- BETC-GLM achieves regret O(kappa^{-1} d^{2/3} T^{2/3} sqrt(log(T/(d delta)))) with tuned tau and epsilon, matching the lower bound up to logs.
- BEXP3 achieves O((d log K)^{1/3} T^{2/3}) regret in the adversarial linear setting; experiments show both proposed methods beat UCB-Borda, DEXP3 and ETC-Borda in cumulative regret over T=10^6.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BETC-GLM, which exploits contextual features | Borda regret minimization · Generated hard case | cumulative Borda regret | Helped |
| use BEXP3, which exploits contextual features | Borda regret minimization · Generated hard case | cumulative Borda regret | Helped |
| use BETC-GLM, which exploits contextual features | Borda regret minimization · EventTime | cumulative Borda regret | Helped |
| use BEXP3 in place of a baseline | Borda regret minimization · EventTime | cumulative Borda regret | Helped |
Surprising findings
- UCB-Borda suffers linear regret because its second arm is sampled uniformly at random, which is inherent to its per-round regret definition.
Limitations
- Upper bounds depend on the link-function constant kappa and assume a G-optimal design (exact or approximated with Frank-Wolfe).
- The EXP3-type algorithm uses a shifted Borda estimate and is designed for the linear model, not the general GLM; the structured Bradley-Terry case is excluded from the analysis.
Experimental setup
Datasets: EventTime
Benchmarks: synthetic hard instance (d=6, K=128) EventTime
Metrics: cumulative Borda regret
Baselines: UCB-Borda DEXP3 ETC-Borda BETC-GLM
Builds on: Dueling-Exp3 (DEXP3) generalized linear bandits (Li et al. 2017) linear stochastic transitivity dueling bandits
Closest papers by meaning
- Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 2024 · similarity 0.93)
- On Weak Regret Analysis for Dueling Bandits (NeurIPS 2024 · similarity 0.93)
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.91)
- Feel-Good Thompson Sampling for Contextual Dueling Bandits (ICML 2024 · similarity 0.90)
- Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback (ICML 2025 · similarity 0.89)
- Fusing Reward and Dueling Feedback in Stochastic Bandits (ICML 2025 · similarity 0.89)
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.