Learning optimal strategies in Stackelberg games

Stackelberg games are one of the most widely adopted models involving some form of commitment. In these games, a leader commits to a strategy beforehand, so that a follower can play a best response according to such a strategy. In real-world applications, the parameters of the model are usually unknown. To overcome this issue, different works have addressed the problem of learning in settings based on Stackelberg games. In this Thesis, we study the problem of learning an optimal commitment when the leader does not know the follower's utility and can commit to any mixed strategy defined over a finite set of actions. The leader plays multiple times the same game with a fixed follower. First, we revise existing learning algorithms in this setting. In doing so, we unveil some technical and conceptual flaws in these works. In particular, we provide instances where these approaches fail, and others where the number of samples they require far exceeds the claimed theoretical value. Then, we propose an algorithm to properly learn an optimal commitment in a Stackelberg game. Our algorithm has polynomial sample complexity when the number of actions of one player is constant, matching an existing lower bound. Additionally, it does not require some of the most limiting assumptions of previous works.

I giochi di Stackelberg sono alcuni dei modelli con una qualche forma d'impegno più utilizzati. In questi giochi un leader s'impegna in anticipo a giocare una certa strategia. Successivamente, un follower risponde in maniera ottimale a tale strategia. Nelle applicazioni reali i parametri del modello solitamente non sono noti. Per superare questo ostacolo, molti lavori hanno affrontato il problema di dover imparare in scenari basati sui giochi di Stackelberg. In questa Tesi, studiamo il problema di dover imparare una strategia ottimale quando il leader non conosce l'utilità del follower, e può impegnarsi a giocare qualsiasi strategia mista definita su un insieme finito di azioni. Il leader interagisce più volte con lo stesso follower in un gioco costante. Per prima cosa, riesaminiamo gli algoritmi esistenti in questo scenario. Così facendo, mostriamo alcuni difetti, sia tecnici che concettuali, in questi lavori. In particolare, proponiamo alcune istanze in cui questi approcci falliscono, ed altre in cui il numero d'interazioni che richiedono supera di molto il valore dichiarato. Successivamente, sviluppiamo un algoritmo per imparare correttamente una strategia ottimale in un gioco di Stackelberg. Il nostro algoritmo ha complessità polinomiale quando il numero di azioni di un giocatore è costante, eguagliano un precedente limite inferiore. In più, non richiede alcune delle ipotesi più restrittive dei lavori precedenti.