We study principal-agent problems in which a principal commits to an
outcome-dependent payment scheme -- called contract -- in order to induce an
agent to take a costly, unobservable action leading to favorable outcomes. We
consider a generalization of the classical (single-round) version of the
problem in which the principal interacts with the agent by committing to
contracts over multiple rounds. The principal has no information about the
agent, and they have to learn an optimal contract by only observing the outcome
realized at each round. We focus on settings in which the size of the agent's
action space is small. We design an algorithm that learns an
approximately-optimal contract with high probability in a number of rounds
polynomial in the size of the outcome space, when the number of actions is
constant. Our algorithm solves an open problem by Zhu et al.[2022]. Moreover,
it can also be employed to provide a $\tilde{\mathcal{O}}(T^{4/5})$ regret
bound in the related online learning setting in which the principal aims at
maximizing their cumulative utility, thus considerably improving
previously-known regret bounds.

研究主体 - 代理问题中的主体为了引导代理采取成本高且不可观察的行动以获得有利结果而承诺一种与结果相关的支付方案，考虑了与代理进行多轮合同承诺的问题的推广，设计了一种算法，在观察到每轮的结果后，能够以高概率学习到近似最优的合同，对于行动空间较小的情景，在最优合同学习方面取得了突破性进展，并在相关在线学习环境下用于最大化主体累积效用以提供近似为 O (T^4/5) 的遗憾上界，从而明显改善了之前已知的遗憾上界。