Research map / Bandits and online learning / Online convex optimization and games
Generalized Principal-Agent Problem with a Learning Agent
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.
Reduces repeated generalized principal-agent problems with a no-regret or no-swap-regret learning agent to approximate-best-response problems, giving tight bounds on the principal's achievable utility around the Stackelberg value.
Problem
Principal-agent problems (Bayesian persuasion, Stackelberg games, contract design) where the principal lacks commitment power and the agent learns to respond over repeated rounds; how much can the principal gain versus the classic best-responding Stackelberg value U*?
Approach
Reduces the learning-agent setting to a one-shot problem with an approximately best-responding agent: no-regret agents yield a maxmin objective U* - Theta(sqrt(Reg/T)), while no-swap-regret agents cap the principal at U* + O(SReg/T), with a mean-based counterexample where the principal can exceed U*.
Key results
- Against a no-regret agent, the principal obtains at least U* - O(sqrt(Reg(T)/T)) with a fixed strategy; the sqrt dependence is tight.
- Against a no-swap-regret agent, the principal cannot exceed U* + O(SReg(T)/T), and this is tight.
- In a Bayesian persuasion instance, a mean-based (no-regret, not no-swap-regret) receiver can be exploited to get utility about 1/2 - O(sqrt(gamma)), well above U* = 0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a fixed strategy against an agent with contextual regret CReg(T) | Generalized principal-agent problems without agent private information · Generalized principal-agent problems | average utility: U^* - O\big(\sqrt{\tfrac{\mathrm{CReg}(T)}{T}}\big) | Hurt |
| Use an adaptive strategy against an agent with contextual swap-regret CSReg(T) | Generalized principal-agent problems without agent private information · Generalized principal-agent problems | average utility: U^* + O\big(\tfrac{\mathrm{CSReg}(T)}{T}\big) | No clear effect |
| Switch the signaling scheme after the first T/2 rounds | Sender facing a γ-mean-based receiver · Bayesian persuasion instance with two states and three actions | average sender utility: \approx \frac{1}{2} - O(\sqrt\gamma) | Helped |
| Use a contextual no-swap-regret learning agent instead of a mean-based no-regret agent | Principal in generalized principal-agent problems · Generalized principal-agent problems | average principal utility: U^* + O\big(\tfrac{\mathrm{CSReg}(T)}{T}\big) | Hurt |
| Allow randomized rather than deterministic δ-best responses | Principal's maxmin objective in unconstrained generalized principal-agent problems · Generalized principal-agent problems without constraints | maxmin utility: U^* - \mathrm{diam}(\mathcal X) L \tfrac{\delta}{G}; U^* - 2 \sqrt{\tfrac{2B L}{G} \mathrm{diam}(\mathcal X) \delta} | Mixed |
| Use randomized approximate best responses in the tight Bayesian persuasion example | Principal's maxmin objective · Bayesian persuasion with prior 0 < μ₀ < 1/2 | maxmin sender utility: U^* - 2\sqrt{2\mu_0\delta} + \delta | Hurt |
| Use a randomized δ-approximate response that favors the sender | Sender in the tight Bayesian persuasion example · Bayesian persuasion with prior 0 < μ₀ < 1/2 | maxmax sender utility: U^* + \delta | Helped |
Surprising findings
- Against no-regret learners the principal's worst-case loss scales with the square root of average regret, not linearly.
- Against mean-based no-regret learners the principal can significantly exceed the Stackelberg value U*.
Limitations
- null
Experimental setup
Metrics: principal average utility approximate best response objective
Builds on: Stackelberg games with learning followers contextual bandits swap regret reductions
Closest papers by meaning
- Learning Optimal Contracts: How to Exploit Small Action Spaces (ICLR 2024 · similarity 0.89)
- Incentivized Learning in Principal-Agent Bandit Games (ICML 2024 · similarity 0.89)
- Learning in Online Principal-Agent Interactions: The Power of Menus (AAAI 2024 · similarity 0.89)
- Contracting with a Learning Agent (NeurIPS 2024 · similarity 0.88)
- Contract Design Under Approximate Best Responses (ICML 2025 · similarity 0.88)
- Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents (ICML 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.