Learning to act under incentives: a UCB-based approach to the Principal-Agent problem

Decision-making under uncertainty is a central challenge in economics, operations research and learning theory. In many real-world scenarios, decision-makers have to act repeatedly in stochastic environments in spite of limited knowledge of the underlying dynamics. When such decisions are shaped by external incentives, the interaction can be modeled through the Principal–Agent framework. This thesis investigates the learning problem faced by an agent operating in such a framework, where the environment’s dynamics are fully unknown. We first propose a UCB-based algorithm for a single-state formulation, in which each action induces a probability distribution over outcomes and payments depend solely on the realized outcomes. We then extend this approach to the multi-state Principal–Agent Markov Decision Process (PAMDP), designing an algorithm that incorporates optimism into both state transitions and value estimates. We establish sublinear regret bounds for both algorithms, thereby ensuring asymptotic optimality in their respective settings. Theoretical guarantees are complemented by empirical evaluations in synthetic environments, which illustrate how the proposed algorithms efficiently adapt to changing incentives and how different contractual structures influence the agent’s behavior. Overall, the study acts as bridge between contract theory and incentive-driven online decision-making, showing how agents can learn robustly when their reward functions are externally specified through a sequence of outcome-dependent payments.

I processi decisionali in condizioni di incertezza rappresentano una sfida centrale in economia, ricerca operativa e teoria dell'apprendimento. In molti scenari reali, degli agenti devono prendere decisioni ripetutamente in ambienti stocastici nonostante una conoscenza limitata delle dinamiche sottostanti. Quando tali decisioni sono influenzate da incentivi esterni, l'interazione può essere modellata attraverso il framework Principale-Agente. Questa tesi indaga il problema di apprendimento affrontato da un agente che opera in tale framework, in cui le dinamiche dell'ambiente sono completamente sconosciute. Proponiamo un algoritmo basato su Upper Confidence Bound (UCB) per uno scenario a singolo stato, in cui ogni azione induce una distribuzione di probabilità sui risultati e i pagamenti dipendono esclusivamente dai risultati conseguiti. Estendiamo quindi questo approccio al modello multi-stato noto come Principal-Agent Markov Decision Process (PAMDP), progettando un algoritmo che incorpora l'ottimismo sia nelle stime di transizione che in quelle di valore tra stati. Stabiliamo bound di regret sublineari per entrambi gli algoritmi, garantendo così l'ottimalità asintotica nei rispettivi contesti. Le garanzie teoriche sono integrate da valutazioni empiriche in ambienti sintetici, che illustrano come gli algoritmi proposti si adattino efficacemente a incentivi variabili e come diverse strutture contrattuali influenzino il comportamento dell'agente. Nel complesso, questa tesi mette in relazione tecniche di teoria dei contratti e online decision-making, mostrando come gli agenti possano imparare quando la loro utilità dipende da una sequenza di pagamenti esogeni che dipendono da risultati osservabili.