Research map / Bandits and online learning / Online convex optimization and games
Learning Optimal Contracts: How to Exploit Small Action Spaces
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.
Designs a Discover-and-Cover algorithm that learns an approximately optimal bounded contract in a number of rounds polynomial in the number of outcomes when the agent's action count is constant, and yields an O~(T^{4/5}) regret bound in online principal-agent learning.
Problem
Learning optimal contracts in hidden-action principal-agent problems when the principal only observes stochastic outcomes, not the agent's action, with sample complexity and regret that scale badly with the number of outcomes m.
Approach
Groups agent actions into meta-actions with similar outcome distributions, discovered online, and approximately covers the contract space with approximate best-response regions via upper/lower polytope bounds refined by binary search; this avoids exponential dependence on m when the number of actions n is constant.
Key results
- Algorithm learns a rho-optimal bounded contract with probability 1-delta in O~(m^n * I * rho^-4 log(1/delta)) rounds when the number of agent actions n is constant.
- Explore-then-commit algorithm achieves regret O~(m^n * I * log(1/delta) * T^{4/5}) with high probability, improving on the O~(T^{1-1/(2m+1)}) bound of prior work for m >= 3.
- Shows an impossibility result: no algorithm can find a kappa-optimal contract over unbounded payments with fewer than any given number of rounds, motivating the bounded-payment formulation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Discover-and-Cover with a constant number of agent actions | Online principal-agent learning · Online principal-agent learning | regret: \widetilde{\mathcal{O}}(T^{1-1/(2m+1)}) -> \widetilde{\mathcal{O}}(T^{4/5}) | Helped |
Surprising findings
- Learning optimal contracts over unbounded payments is impossible in finite rounds for some absolute constants, motivating bounded payments.
Limitations
- Round complexity is exponential in the number of actions n (m^n factor), so it is only polynomial for constant n.
- Requires bounded payments B; general unbounded contracts cannot be learned with finite samples.
- Relies on approximate best-response regions and a trial-and-error restart each time a new meta-action is discovered.
Experimental setup
Metrics: sample complexity (rounds) cumulative Stackelberg regret
Baselines: Zhu et al. 2023 regret bound
Builds on: Stackelberg commitment learning (Peng et al. 2019 style) explore-then-commit
Closest papers by meaning
- Contracting with a Learning Agent (NeurIPS 2024 · similarity 0.92)
- Contract Design Under Approximate Best Responses (ICML 2025 · similarity 0.91)
- Generalized Principal-Agent Problem with a Learning Agent (ICLR 2025 · similarity 0.89)
- Learning in Online Principal-Agent Interactions: The Power of Menus (AAAI 2024 · similarity 0.88)
- Incentivized Learning in Principal-Agent Bandit Games (ICML 2024 · similarity 0.87)
- Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals (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.