No-Regret Verteiltes Lernen in Subnetz Null-Summen-Spielen

In diesem Papier betrachten wir ein Problem des verteilten Lernens in einem Subnetz Null-Summen-Spiel, in dem Agenten in verschiedenenSubnetzen konkurrieren. Diese Agenten sind durch zeitvariierende Grafen verbunden, wobei jeder Agent seine eigene Kostenfunktion hat und Informationen von seinen Nachbarn empfangen kann. Wir schlagen einen verteilten Mirror-Descent-Algorithmus zur Berechnung eines Nash-Gleichgewichts vor und stellen eine sublineare Bedingung über die Sequenz der Iterationen auf, wenn die Grafen gleichmäßig stark verbunden sind und die Kostenfunktionen konvex-konkav sind. Darüber hinaus beweisen wir seine Konvergenz mit geeignet gewählten abnehmenden Schrittweiten für eine strikt konvex-konkave Kostenfunktion. Wir betrachten auch eine Variante des Algorithmus mit konstanter Schrittweite und legen eine asymptotische Fehlergrenze zwischen den Kostenwerten der laufenden Durchschnittshandlungen und einem Nash-Gleichgewicht fest. Zusätzlich wenden wir den Algorithmus an, um ein gemischtes Strategie-Nash-Gleichgewicht in Subnetz Null-Summen-Finite-Strategie-Spielen zu berechnen, die lediglich konvex-konkave (genauer gesagt, multilineare) Kostenfunktionen haben, und erhalten jeweils ein Konvergenzresultat der letzten Iteration und ein ergodisches Konvergenzresultat unter verschiedenen Annahmen.