Research map / Bandits and online learning / Multi-armed bandits
Fusing Reward and Dueling Feedback in Stochastic 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 fusing absolute (reward) and relative (dueling) feedback in stochastic bandits, deriving a regret lower bound and proposing ElimFusion and DecompFusion algorithms, with DecompFusion matching the lower bound up to a constant under an assumption.
Problem
How to jointly use reward (absolute) and dueling (relative) feedback in stochastic multi-armed bandits to minimize weighted accumulated regret, when both feedback types are gathered each round.
Approach
Derives a lower bound showing that for each suboptimal arm an algorithm only needs to pay the smaller of its reward-based and dueling-based regret costs; ElimFusion shares a candidate arm set across both feedback types, while the decomposition algorithm splits arms into reward-explored and dueling-explored sets and randomizes between exploration and exploitation each round.
Key results
- DecompFusion's aggregated regret is around 41 times lower than ElimFusion in one setting (alpha=0.5).
- ElimFusion outperforms ElimNoFusion by 81.3%, and DecompFusion outperforms MEDNoFusion by 47.5%.
- DecompFusion achieves a T-independent constant regret when alpha=0 or alpha=1, which ElimFusion cannot.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use decomposition fusion instead of ElimFusion | DR-MAB · various simulation settings, α=0.5 | aggregated regret: around 41 times lower | Helped |
| Share one candidate arm set across reward and dueling elimination instead of maintaining separate sets | ElimFusion · DR-MAB | regret upper bound | Helped |
| Use ElimFusion instead of ElimNoFusion | DR-MAB · Figure [ref], α=0.5 | aggregated regret: 81.3% | Helped |
| Use decomposition fusion instead of MEDNoFusion | DR-MAB · Figure [ref], α=0.5 | aggregated regret: 47.5% | Helped |
| Set α to 0 or 1, enabling free exploration through the uncounted feedback type | Decomposition fusion · DR-MAB | regret | Helped |
| Use elimination fusion rather than decomposition fusion at α=0 or α=1 | DR-MAB · DR-MAB | regret: O(log T) | Hurt |
Surprising findings
- The lower bound becomes sub-logarithmic (o(log T)) when alpha is 0 or 1, and DecompFusion achieves constant regret in those cases.
Limitations
- ElimFusion's regret has a suboptimal multiplicative factor K and suboptimal alpha dependence.
- DecompFusion's optimal matching requires the assumption that the most effective dueling competitor is the optimal arm.
- Analysis restricted to Bernoulli reward and dueling distributions.
Experimental setup
Benchmarks: simulated stochastic bandit instances
Metrics: aggregated regret
Baselines: ElimNoFusion MEDNoFusion
Builds on: RMED1 MED KL-UCB successive elimination
Closest papers by meaning
- Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 2024 · similarity 0.91)
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.91)
- On Weak Regret Analysis for Dueling Bandits (NeurIPS 2024 · similarity 0.90)
- p-Mean Regret for Stochastic Bandits (AAAI 2025 · similarity 0.89)
- Borda Regret Minimization for Generalized Linear Dueling Bandits (ICML 2024 · similarity 0.89)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (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.