Learning optimal contracts with small action spaces

In our work, we explore the complex domain of principal-agent problems, where a principal strategically uses an outcome-dependent payment scheme, called a contract, to incentivize an agent to perform a costly but unobservable action that ultimately leads to favourable outcomes. Our investigation takes a step beyond the classical single-round formulation of the problem, extending it to a multi-round scenario in which the principal engages in a series of interactions with the agent through contract commitments. This extended formulation poses a heightened challenge, as the principal operates without any prior knowledge of the agent. The principal’s task is to learn an optimal contract simply by observing the outcomes realised in each round. A distinctive feature of our focus is on scenarios characterised by a relatively small size of the agent’s action space. In response to this complex problem space, we propose a novel algorithm. This algorithm demonstrates the ability to learn an approximately optimal contract with high probability within a polynomial number of rounds, a significant advance when the number of actions remains constant. In particular, our algorithm successfully tackles an open problem posed by Zhu et al [2022]. Furthermore, the versatility of our algorithm extends beyond the realm of principal-agent problems. It can be seamlessly applied to obtain a regret bound of O(T 4/5) in the context of online learning. In this scenario, the principal’s objective is to maximise cumulative utility, which is a significant improvement over previously established regret bounds. In summary, our work not only addresses a fundamental challenge in principal-agent problems, but also contributes to the broader landscape of online learning by providing more efficient solutions and significantly advancing the state of the art in regret bounds.

Nel seguente lavoro, esploriamo il complesso dominio dei problemi principal-agente, in cui un principal utilizza strategicamente uno schema di pagamento dipendente dal risultato, chiamato contratto, per incentivare un agente a svolgere un’azione costosa ma non os- servabile che alla fine porta a risultati favorevoli. La nostra indagine fa un passo avanti rispetto alla classica formulazione a turno singolo del problema, estendendolo a uno sce- nario multi-turno in cui il principal si impegna in una serie di interazioni con l’agente attraverso impegni contrattuali. Questa formulazione estesa pone una sfida maggiore, poiché il principal opera senza alcuna conoscenza preliminare dell’agente. Il compito del principal è imparare un contratto ottimale semplicemente osservando i risultati realiz- zati in ogni turno. Una caratteristica distintiva del nostro approccio è la concentrazione su scenari caratterizzati da una dimensione relativamente piccola dello spazio di azione dell’agente. In risposta a questo complesso spazio di problemi, proponiamo un nuovo algoritmo. Questo algoritmo dimostra la capacità di imparare un contratto approssima- tivamente ottimale con alta probabilità entro un numero polinomiale di turni, un avanza- mento significativo quando il numero di azioni rimane costante. In particolare, il nostro algoritmo affronta con successo un problema aperto posto da Zhu et al [2022]. Inoltre, la versatilità del nostro algoritmo si estende oltre il regno dei problemi principal-agente. Può essere applicato senza soluzione di continuità per ottenere un limite di regret di O(T 4/5) nel contesto dell’apprendimento online. In questo scenario, l’obiettivo del principal è mas- simizzare l’utilità cumulativa, il che rappresenta un miglioramento significativo rispetto ai limiti di regret precedentemente stabiliti. In sintesi, il nostro lavoro non solo affronta una sfida fondamentale nei problemi principal-agente, ma contribuisce anche al panorama più ampio dell’apprendimento online fornendo soluzioni più efficienti e facendo avanzare significativamente lo stato dell’arte nei limiti di regret.