Die Stichprobenkomplexität von Stackelberg-Spielen

Stackelberg-Spiele (SGs) sind die grundlegendsten und angesehensten Modelle für strategische Interaktionen, die irgendeine Form von Verpflichtung beinhalten. Darüber hinaus bilden sie die Basis für elaboriertere Modelle dieser Art, wie z.B. bayesianische Überredung und Principal-Agent-Probleme. Das Angehen von Lernaufgaben in SGs und verwandten Modellen ist entscheidend, um sie in der Praxis zu operationalisieren, wo Modellparameter in der Regel unbekannt sind. In diesem Papier überprüfen wir die Stichprobenkomplexität des Lernens einer optimalen Strategie zur Verpflichtung in SGs. Wir bieten einen neuartigen Algorithmus an, der (i) keine der einschränkenden Annahmen erfordert, die von modernen Ansätzen gemacht werden, und (ii) mit einem Kompromiss zwischen Stichprobenkomplexität und Beendigungswahrscheinlichkeit umgeht, der entsteht, wenn die Repräsentation der Strategien des Führers eine endliche Präzision hat. Ein solcher Kompromiss wurde von bestehenden Algorithmen völlig vernachlässigt, und wenn er nicht richtig gehandhabt wird, kann dies dazu führen, dass sie exponentiell viele Stichproben verwenden. Unser Algorithmus erfordert neuartige Techniken, die auch den Weg zur Lösung von Lernproblemen in anderen Modellen mit Verpflichtungen, die in der realen Welt allgegenwärtig sind, ebnen.