Research map / Bandits and online learning / Online convex optimization and games
Regret Analysis of Repeated Delegated Choice
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 delegated choice as an online learning problem where a principal announces eligible sets to screen an agent's solutions, giving regret bounds for myopic and discounting strategic agents with deterministic or stochastic utilities.
Problem
A principal repeatedly delegates selection among an agent's exogenous solutions under misaligned utilities, without prior knowledge of the solution distribution, and must minimize cumulative regret against the best eligible set in hindsight.
Approach
Reformulates delegated choice (Kleinberg and Kleinberg, EC'18) as a repeated Stackelberg game with single-proposal mechanisms; reduces the myopic deterministic case to repeated posted pricing, and handles strategic agents via D-delayed mechanisms with discounting, plus bandit discretization for the stochastic case.
Key results
- Myopic deterministic setting admits regret O(min(K, log log T)) via reduction to repeated posted price mechanism.
- Strategic agent with gamma-discounting and bounded utility gets regret O(K * tgamma * log(tgamma/ymin)) and O(tgamma log(tgamma/ymin) + log T), with Omega(T) lower bound if ymin <= e^{-T}.
- Stochastic myopic setting with UCB1 on discretized thresholds achieves O(sqrt(T log T)) regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the repeated delegated choice algorithm for deterministic utilities with a myopic agent | Repeated delegated choice · Deterministic utility, myopic agent | Stackelberg regret: O(min(K, log log T)) | Helped |
| Use delayed iterative search with known ymin | Repeated delegated choice · Deterministic utility, γ-discounting strategic agent | Worst-case Stackelberg regret: O(Kτγ log (τγ/ymin)) | Helped |
| Shrink eligible sets aggressively instead of sequentially seeking next-best solutions | Repeated delegated choice · Deterministic utility, γ-discounting strategic agent with known ymin | Worst-case Stackelberg regret: O(Kτγ log (τγ/ymin)) -> O(τγ log (τγ/ymin) + log T) | Helped |
| Allow ymin ≤ e^{-T} | Any algorithm against a γ-discounting strategic agent · Deterministic utility | Worst-case Stackelberg regret: Ω(T) | Hurt |
| Assume d-dense solutions and Lipschitz continuity between principal and agent utilities | Delayed progressive search · Deterministic utility, γ-discounting strategic agent | Worst-case Stackelberg regret: O(τγ log (τγ/α) + log (1/d) + dT) | Helped |
| Allow d-dense instances against a strategic agent | Any algorithm · Deterministic utility, γ-discounting strategic agent | Worst-case Stackelberg regret: Ω(dT) | Hurt |
| Use UCB1 over discretized thresholds | Repeated delegated choice · Stochastic utility, myopic agent | Stackelberg regret: O(√(T log T)) | Helped |
| Use delayed successive elimination with perturbed-bandit analysis | Repeated delegated choice · Stochastic utility, γ-discounting strategic agent | Worst-case Stackelberg regret: O(√(T log T) + Tγ log(Tγ max(T/L1, 1/ymin)) log T) | Helped |
| Allow a non-discounting strategic agent | Repeated delegated choice · Deterministic utility | Stackelberg regret: null | Hurt |
Surprising findings
- Sublinear regret is impossible for a non-discounting strategic agent, so a discount factor is necessary.
- Under d-dense and Lipschitz assumptions, a linear Omega(dT) regret term is unavoidable for any algorithm.
Limitations
- Regret bounds depend logarithmically on 1/ymin and linearly on K or dT, which can be vacuous.
- Stochastic strategic result requires strong assumptions such as unique optimum and concavity of f.
Experimental setup
Metrics: cumulative Stackelberg regret
Builds on: Kleinberg and Kleinberg EC'18 delegated choice repeated posted price mechanism delayed mechanism for strategic agents UCB1 successive elimination
Closest papers by meaning
- Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals (ICML 2025 · similarity 0.88)
- A Unifying Framework for Online Optimization with Long-Term Constraints (NeurIPS 2022 · similarity 0.88)
- Online Markov Decision Processes Configuration with Continuous Decision Space (AAAI 2024 · similarity 0.87)
- Incentivized Learning in Principal-Agent Bandit Games (ICML 2024 · similarity 0.87)
- Generalized Principal-Agent Problem with a Learning Agent (ICLR 2025 · similarity 0.86)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · 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.