Research map / Bandits and online learning / Online convex optimization and games
Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
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 principal-agent bandit games where the agent is a self-interested learner (empirical-mean maximizer, possibly exploring) and proposes phased-elimination algorithms with improved regret bounds in i.i.d. and linear reward settings.
Problem
Repeated principal-agent bandit games in which the principal can only indirectly explore an unknown environment by incentivizing an agent who itself learns reward estimates and may explore, rather than being an oracle agent with true means.
Approach
Phased elimination that plays bad arms moderately often to stabilize the agent's estimators, uses an asymmetric-check binary search for incentive estimation, and, for exploratory agents, repeats searches and uses median-based trustworthy elimination, plus a conservative multi-scale cutting-plane search for linear rewards.
Key results
- Self-interested greedy agent with i.i.d. rewards: regret O~(sqrt(KT)), matching the Omega(sqrt(KT)) lower bound up to log factors.
- Exploratory agent with i.i.d. rewards: regret O~(T^{2/3}), improving the prior O~(T^{11/12}) bound; under the reduced oracle-agent exploration model, O~(sqrt(KT)).
- Linear rewards with self-interested agent: regret O~(d^{4/3} T^{2/3}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed phased-elimination algorithm instead of the prior exploratory-agent algorithm | Principal-agent bandit game with an exploratory oracle agent · i.i.d. rewards | regret bound: \otil(T^{\nicefrac{11}{12}}) -> \otil(\sqrt{KT}) | Helped |
| Allow arbitrary exploration while using the robust exploratory-agent algorithm | Principal-agent bandit game · i.i.d. rewards, exploratory learning agent | regret bound: \otil(T^{\nicefrac{11}{12}}) -> \otil(T^{\nicefrac{2}{3}}) | Mixed |
| Use the proposed linear algorithm with conservative cuts | Principal-agent bandit game with a self-interested learning agent · Linear rewards | regret bound | Mixed |
Surprising findings
- Playing bad arms deliberately (rather than permanently eliminating them) is necessary to stabilize the agent's estimators and aid incentive search.
Limitations
- Gap between upper and lower bounds in the linear setting remains open, with an extra factor of d.
- Exploratory agent i.i.d. bound O~(T^{2/3}) is not matched to the lower bound.
- Gap-dependent bounds are not achieved because bad arms are still played.
Experimental setup
Metrics: expected cumulative regret
Baselines: Wu et al. 2022 oracle-agent algorithm Zhu et al. 2023 exploratory agent algorithm (T^{11/12}) IPA C-IPA
Builds on: Multiscale Steiner Potential G-optimal design phased elimination
Closest papers by meaning
- Incentivized Learning in Principal-Agent Bandit Games (ICML 2024 · similarity 0.93)
- Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals (ICML 2025 · similarity 0.89)
- Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs (AAAI 2024 · similarity 0.87)
- A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning (ICLR 2024 · similarity 0.87)
- Generalized Principal-Agent Problem with a Learning Agent (ICLR 2025 · similarity 0.87)
- Impact of Decentralized Learning on Player Utilities in Stackelberg Games (ICML 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.