Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Strategic Linear Contextual 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 strategic linear contextual bandits where arms misreport contexts, and proposes grim-trigger mechanisms (GGTM for known theta, OptGTM for unknown theta) that make truthfulness an approximate Nash equilibrium while keeping regret sublinear.
Problem
Linear contextual bandits where self-interested arms (e.g., sellers in a recommender) misreport privately observed contexts to maximize how often they are selected, so standard learners suffer linear regret.
Approach
Treats the bandit algorithm as mechanism design without payments: a grim-trigger rule eliminates an arm permanently when its reported contexts are inconsistent with observed rewards, using optimistic/pessimistic confidence bounds with per-arm estimators so manipulation is bounded without knowing theta or the corruption budget.
Key results
- OptGTM's strategic regret stays stable across 20 epochs of arm adaptation, while LinUCB's regret grows and nearly matches uniform sampling in the final epoch (K=5, d=5, 10 runs).
- Truthful reporting is an O~(d sqrt(KT))-Nash equilibrium under OptGTM with regret O~(d sqrt(KT)) when arms are truthful.
- Under every Nash equilibrium, OptGTM's strategic regret is O~(d K^2 sqrt(KT)); incentive-unaware algorithms like LinUCB suffer linear regret under their induced equilibria.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OptGTM rather than LinUCB as arms adapt their reported contexts | Strategic linear contextual bandits · Final epoch after strategic arms adapt | strategic regret | Helped |
| Use OptGTM rather than LinUCB when arms report truthfully | Strategic linear contextual bandits · Epoch 0, truthful arms | regret | Hurt |
| Account for strategic context misreporting with OptGTM rather than an incentive-unaware algorithm | Strategic linear contextual bandits · Non-trivial instances, Nash equilibrium | regret | Helped |
| Use OptGTM with truthful arms rather than the standard non-strategic regret benchmark | OptGTM · Strategic linear contextual bandits, truthful arms | strategic regret | Hurt |
Surprising findings
- Incentive-unaware algorithms such as LinUCB and greedy selection suffer linear regret on any non-trivial instance when arms best-respond, because the only Nash equilibrium is maximal gaming.
- LinUCB outperforms OptGTM when arms are truthful (epoch 0), since OptGTM pays a cost for maintaining per-arm estimators.
Limitations
- Assumes arms never under-report their (optimistic) value relative to their true value, which the paper shows can be exploited in some instances.
- The K^2 factor in the worst-case strategic regret bound is likely suboptimal; conjectured optimal is O(d sqrt(KT)).
Experimental setup
Benchmarks: simulated strategic linear contextual bandit
Metrics: strategic regret arm utility (number of selections)
Baselines: LinUCB incentive-unaware greedy algorithm RobustBandit uniform random selection
Builds on: LinUCB grim trigger strategy robust linear bandits with adversarial corruptions
Closest papers by meaning
- Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation (ICLR 2024 · similarity 0.89)
- Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates (ICML 2026 · similarity 0.89)
- Conservative Contextual Bandits: Beyond Linear Representations (ICLR 2025 · similarity 0.87)
- Learning to Recommend in Unknown Games (NeurIPS 2026 · similarity 0.87)
- Mechanism design augmented with output advice (NeurIPS 2024 · similarity 0.87)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · 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.