Online Contract Design With Unknown Technology

*Hidden-action principal-agent problems* model scenarios in which a principal induces an agent to take a costly and *unobservable* action through the provision of outcome-dependent payments. These problems find application in a variety of real-world settings, such as crowdsourcing, online labor platforms, and machine learning task delegation. Recently, much of the literature has focused on how to handle the principal’s *uncertainty* about the agent and the surrounding environment, which is often the main challenge in practice. One prominent approach is to adopt an *online learning* framework, where the principal repeatedly interacts with the agent to learn optimal payments from experience. However, existing learning algorithms, while achieving regret that scales sublinearly in the number of interaction rounds $T$, typically suffer from an exponential dependence on the size of the problem instance. In this paper, we show that this problematic exponential growth can be avoided by assuming that the principal has knowledge of a set of possible actions of the agent, while remaining unaware of which actions are actually available---an assumption that is reasonable in many real-world settings.

Machine learning systems increasingly rely on external agents or providers to perform tasks, such as crowdsourcing workers, online freelancers, or companies training AI models on behalf of clients. These agents are free to choose how to complete the task and receive payment based on the produced outcome. A central challenge is to design payment schemes that reliably incentivize good behavior when there is uncertainty about the actions available to the agent. Our work studies how to learn effective contracts in these uncertain environments. Previous approaches can learn good contracts over time, but they may require exponentially many interactions with the agent. We show that this exponential barrier can be avoided under a realistic assumption: the principal knows a broad set of possible actions the agent might take, even if they do not know which actions are truly feasible. We develop a new learning algorithm that efficiently identifies groups of similar actions and uses them to compute near-optimal contracts. Our results provide the first learning guarantees in this setting that scale polynomially with the problem size, making online contract design significantly more practical for applications involving AI systems and digital marketplaces.