Research map / Bandits and online learning / Online convex optimization and games
Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
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 repeated principal-agent incentive design against adversarially ordered agent types, showing linear regret without known agent behavior and sublinear regret (matching lower bounds up to logs) under known greedy responses or smooth (Lipschitz) responses.
Problem
Repeated principal incentivizing adversarially arriving agents of unknown type to choose among N arms, minimizing regret against the best fixed incentive in hindsight.
Approach
Reduces the greedy-response single-arm incentive problem with known best-response functions to adversarial linear bandits over a discretized incentive set (distinct response patterns over K types), and handles smooth responses via Lipschitz discretization with Tsallis-INF; also gives a polytope-based discretization for multi-arm incentives.
Key results
- Greedy known-response single-arm setting: upper bound O~(min{sqrt(KT log N), K sqrt(T)}) matched by lower bound up to log K factor.
- Unknown greedy response with single-arm incentives: linear Omega(T) regret lower bound for any algorithm.
- Smooth (Lipschitz) response, single-arm: O~((LN)^{1/3} T^{2/3}) upper bound matching Omega(L^{1/3} N^{1/3} T^{2/3}) lower bound up to logs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| provide the principal with the agents’ best-response functions | Greedy choice with single-arm incentives · Adversarial agent arrivals | regret: \Omega(T) -> \tilde\order\left(\min\left\{\sqrt{KT\log(N)}, K \sqrt{T}\right\}\right) | Helped |
| allow incentives on multiple arms instead of at most one arm | Greedy choice with known agent behavior · Adversarial agent arrivals | regret: \tilde\order\left(\min\left\{\sqrt{KT\log(N)}, K \sqrt{T}\right\}\right); \mathcal{O}(K\sqrt{T\log(KT)}) | Mixed |
| assume the agent response varies smoothly with the incentive | Principal-agent problem with unknown agent behavior · Single-arm incentives under adversarial agent arrivals | regret: \Omega(T) -> \order \rbr{L^{1/3}N^{1/3}T^{2/3}} | Helped |
| allow incentives on multiple arms instead of at most one arm | Smooth choice model · Adversarial agent arrivals | regret: \order \rbr{L^{1/3}N^{1/3}T^{2/3}}; \order\rbr{L^{N/(N + 2)}T^{(N + 1)/(N + 2)}} | Mixed |
Surprising findings
- Without knowledge of agent behavior, the problem is intractable under greedy responses, yielding linear regret even with a single agent-type distribution.
- Even tiny incentive changes can drastically shift greedy agent decisions, making non-smooth responses unlearnable without prior knowledge.
Limitations
- Greedy-model upper bounds assume the principal knows the best-response function of each agent type.
- Smooth-model algorithm requires knowledge of the Lipschitz constant L.
- Theoretical only; no experiments reported.
Experimental setup
Metrics: pseudo-regret
Baselines: Tsallis-INF
Builds on: Exp3 for linear bandits Tsallis-INF AdversarialZooming
Closest papers by meaning
- Incentivized Learning in Principal-Agent Bandit Games (ICML 2024 · similarity 0.90)
- Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents (ICML 2025 · similarity 0.89)
- Regret Analysis of Repeated Delegated Choice (AAAI 2024 · similarity 0.88)
- No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! (NeurIPS 2025 · similarity 0.87)
- Learning Optimal Contracts: How to Exploit Small Action Spaces (ICLR 2024 · similarity 0.87)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.86)
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.