Research map / Bandits and online learning / Multi-armed bandits
Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation
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.
Introduces the strategic click-bandit, where arms strategically choose click-through rates to maximize their own utility, and proposes the payment-free incentive-aware algorithm UCB-S that achieves sublinear regret under any Nash equilibrium.
Problem
Multi-armed bandit recommendation where items (arms) strategically choose click-through rates to attract allocations, so classical bandit algorithms suffer linear regret in the presence of clickbait.
Approach
Models arms as strategic agents choosing click-rates; designs UCB-S, an incentive-aware UCB variant that eliminates arms whose click-rate deviates from a utility-dependent target, so that equilibrium strategies are near-truthful and regret is sublinear under all Nash equilibria.
Key results
- UCB-S achieves sublinear strong strategic regret under any Nash equilibrium of the arms' strategic game, with dependence on T and K shown to be near-optimal.
- Proposition 4.1 shows incentive-unaware algorithms such as UCB suffer linear regret when arms strategize.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use incentive-aware UCB-S instead of an incentive-unaware algorithm | Strategic click-bandit · Strategic click-bandit | regret | Helped |
Surprising findings
- Incentive-unaware algorithms like standard UCB suffer linear regret because strategic arms inflate click-rates.
Limitations
- Regret bound scales with 1/s*(mu_i), which can be vacuous when optimal click-rate is near zero.
- Requires forcing arms to maintain click-rates, raising practical and ethical concerns.
- Nash equilibrium may not be unique and arms' convergence to equilibrium is not guaranteed.
Experimental setup
Metrics: strong strategic regret regret upper and lower bounds
Baselines: UCB incentive-unaware bandit algorithms
Builds on: UCB
Closest papers by meaning
- Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender System (ICML 2026 · similarity 0.90)
- Bandit Learning with Joint Effect of Incentivized Sampling, Delayed Sampling Feedback, and Self-Reinforcing User Preferences (ICLR 2022 · similarity 0.90)
- Incentivized Bandit Learning with Self-Reinforcing User Preferences (ICML 2021 · similarity 0.89)
- Strategic Linear Contextual Bandits (NeurIPS 2024 · similarity 0.89)
- Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning (ICML 2024 · similarity 0.87)
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.87)
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.