研究如何在对手型代理到来时,通过激励策略最小化长期损失。
Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
- 基于代理类型预知最优选择,设计可实现亚线性后悔的算法。
- 在激励响应平滑条件下,算法后悔上界为约T^{2/3}量级。
- 支持同时激励多个选项,适用于动态合作场景中的决策优化。
我们首次研究有限时域T内的重复委托-代理问题,其中主事人需与K≥2种类型的代理依次交互,且代理到来顺序由对手决定。每轮主事人从N个选项中选择一个进行激励,代理根据自身效用和激励选择行动,主事人获得对应回报。目标是最小化相对于事后最优激励的后悔值。在未知代理行为时,问题变得不可行,导致线性后悔。我们分析两种可实现亚线性后悔的情形:第一种,主事人知晓每类代理对任意激励的贪婪选择;在此设定下,提出算法后悔界为O(min{√(KT log N), K√T}),并给出几乎匹配的下界。第二种,代理响应随激励变化光滑,受利普希茨常数L≥1控制;在此设定下,算法后悔界为~O((LN)^{1/3}T^{2/3}),并建立匹配下界(对数因子内)。最后,我们扩展了两种情形的算法,允许每轮同时激励多个选项。
原文摘要 · Abstract (English)
We initiate the study of a repeated principal-agent problem over a finite horizon $T$, where a principal sequentially interacts with $K\geq 2$ types of agents arriving in an adversarial order. At each round, the principal strategically chooses one of the $N$ arms to incentivize for an arriving agent of unknown type. The agent then chooses an arm based on its own utility and the provided incentive, and the principal receives a corresponding reward. The objective is to minimize regret against the best incentive in hindsight. Without prior knowledge of agent behavior, we show that the problem becomes intractable, leading to linear regret. We analyze two key settings where sublinear regret is achievable. In the first setting, the principal knows the arm each agent type would select greedily for any given incentive. Under this setting, we propose an algorithm that achieves a regret bound of $O(\min\{\sqrt{KT\log N},K\sqrt{T}\})$ and provide a matching lower bound up to a $\log K$ factor. In the second setting, an agent's response varies smoothly with the incentive and is governed by a Lipschitz constant $L\geq 1$. Under this setting, we show that there is an algorithm with a regret bound of $\tilde{O}((LN)^{1/3}T^{2/3})$ and establish a matching lower bound up to logarithmic factors. Finally, we extend our algorithmic results for both settings by allowing the principal to incentivize multiple arms simultaneously in each round.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。