Handhabbare und erlernbare Begriffe von Gleichgewichten in Auktionen und Spielen

Die Erfolge des maschinellen Lernens in den letzten Jahren haben das Interesse geweckt, theoretische Garantien für Lernalgorithmen zu erhalten. Leider ist die derzeitige Theorie nicht in der Lage, solche Garantien in Bezug auf die Konvergenz zu Gleichgewichten oder Wohlfahrtsgrenzen zu etablieren. Auktionen und nicht-konkave Spiele sind zwei Hauptbeispiele. Dies hat in jüngster Zeit die Forschung dazu motiviert, die Grenzen des traditionellen No-Regret-Lernens bei der Erklärung der Konvergenz zum Gleichgewicht zu ermitteln. Der vorliegende Vorschlag enthält zwei Forschungslinien, um diese Fortschritte zu erweitern. Der erste sucht nach strengeren Garantien für allgemein verwendete Lernalgorithmen in Auktionssituationen, indem er stärkere Begriffe des Gleichgewichts nutzt. Neuere Arbeiten deuten darauf hin, dass in jedem Normalformspiel, wenn Spieler den Online-Gradientenaufstieg als Lernalgorithmus verwenden, sie verschwindendes Bedauern gegenüber jeder Strategieabweichung haben, die durch Gradientenfelder von Funktionen erzeugt wird. Einige dieser Funktionen erzeugen lineare Gleichgewichtsbedingungen. Daher konvergieren die Lernenden in dieser Situation zu einem Gleichgewichtsbegriff, der zwischen dem eines groben korrelierten Gleichgewichts und dem eines korrelierten Gleichgewichts liegt. Daher können stärkere Garantien hinsichtlich der Konvergenz sowie bessere Schranken für den Preis der Anarchie durch Dualität der konvexen Programmierung in einem geeigneten primär-dualen Rahmen erhalten werden. Da die korrelierten Gleichgewichte dieser Auktionen eindeutig sind, würde dies eine bisher unbekannte Erklärung für das beobachtete Lernverhalten liefern. Der zweite Teil untersucht Begriffe des lokalen korrelierten Gleichgewichts, die durch Vektorfelder erzeugt werden, mit dem Ziel, ihre Ausdrucksfähigkeit, ihre rechnerische Komplexität sowie ihr zugehöriges dynamisches Verhalten zu charakterisieren. Erstens versuchen wir, Verstärkungen von groben korrelierten Gleichgewichten zu untersuchen, die eine Beschreibung des erlernbaren Verhaltens für eine breitere Palette von Lernalgorithmen als Online-Gradientenaufstieg ermöglichen. Zweitens ist eine Minimierung des Bedauerns auch dann möglich, wenn die Erzeuger des Bedauerns keine konservativen Vektorfelder sind und Zugang zu Festkommaberechnungen haben. Dies wirft die Frage nach der Komplexität des Auffindens solcher „no-regret“-Ergebnisse auf. Drittens versuchen wir durch die Betrachtung von Bedauern gegen Vektorfelder mit Nicht-Null-Krümmung zu untersuchen, inwieweit zyklisches Verhalten beim Lernen vermieden werden kann.

DFG-Verfahren WBP Stipendium

Internationaler Bezug Großbritannien

Gastgeber Professor Paul Goldberg