Research map / Bandits and online learning / Online convex optimization and games
Incentivized Learning in Principal-Agent Bandit Games
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 IPA-style incentive learning for principal-agent bandits: binary search estimates minimal incentives per arm, then a black-box bandit (UCB) learns the principal's rewards, with a contextual extension via multidimensional binary search and corrupted linear bandits.
Problem
A principal repeatedly interacts with a self-interested greedy agent via incentives, not knowing the agent's rewards or her own reward distributions; she must learn incentives to maximize her own utility (minimize regret) in multi-armed and linear contextual bandit settings.
Approach
Decouple learning the agent's preferences (binary search for minimal incentive per arm, or multidimensional binary search on the agent's reward vector in the contextual case) from learning the principal's mean rewards via a black-box bandit algorithm run on shifted rewards; the estimation error acts as a bounded corruption.
Key results
- On a 5-arm toy instance with T=10,000 (100 runs), the proposed IPA-based algorithm's regret is nearly equal to the UCB Oracle baseline that knows optimal incentives.
- The multi-armed algorithm with UCB subroutine achieves distribution-free regret of order sqrt(TK log T) and instance-dependent log T regret, nearly matching lower bounds.
- The contextual algorithm achieves regret O(d sqrt(T) log T) via corrupted linear bandits with Corral, with the number of binary-search steps bounded by 192 d log(dT).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use IPA instead of Principal ε-Greedy | 5-arm bandit · 5-arm bandit | cumulative regret | Helped |
| Use UCB with known shifted arm means instead of learning incentives | IPA · 5-arm bandit | cumulative regret | No clear effect |
| Set Principal ε-Greedy exploration steps below m=500 | Principal ε-Greedy · 5-arm bandit | mean regret | Hurt |
| Set Principal ε-Greedy exploration steps above m=500 | Principal ε-Greedy · 5-arm bandit | regret | Hurt |
Surprising findings
- The principal's epsilon-Greedy baseline performs poorly and is sensitive to its exploration hyperparameter m, while the proposed method needs no tuning.
Limitations
- Assumes a greedy, myopic agent with no information rent or strategic lying.
- Contextual algorithm is not implemented or experimentally evaluated due to computational complexity of the projected volume subroutine.
- Assumes deterministic agent rewards known to the agent and noise assumptions (1-subgaussian).
Experimental setup
Benchmarks: 5-arm synthetic bandit instance
Metrics: cumulative regret
Baselines: Principal epsilon-Greedy UCB Oracle
Builds on: UCB Corral Principal epsilon-Greedy (Zhu et al.) stochastic linear bandits
Closest papers by meaning
- Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents (ICML 2025 · similarity 0.93)
- Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals (ICML 2025 · similarity 0.90)
- Generalized Principal-Agent Problem with a Learning Agent (ICLR 2025 · similarity 0.89)
- Regret Analysis of Repeated Delegated Choice (AAAI 2024 · similarity 0.87)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.87)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · 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.