Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games
Authors: Dylan J Foster, Noah Golowich, Sham M. Kakade
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide a decisive negative resolution to this problem, both from a computational and statistical perspective. We show that: 1. Under the assumption that PPAD-hard problems cannot be solved in polynomial time, there is no polynomial-time algorithm that attains noregret in general-sum Markov games when executed independently by all players, even when the game is known to the algorithm designer and the number of players is a small constant. 2. When the game is unknown, no algorithm, efficient or otherwise, can achieve no-regret without observing exponentially many episodes in the number of players. These results are proven via lower bounds for a simpler problem we refer to as SPARSECCE |
| Researcher Affiliation | Collaboration | 1Microsoft Research 2Massachusetts Institute of Technology 3Harvard University. Correspondence to: Dylan J. Foster<dylanfoster@microsoft.com>, Noah Golowich<nzg@mit.edu>, Sham M. Kakade<sham@seas.harvard.edu>. |
| Pseudocode | Yes | Algorithm 1 Algorithm to compute Nash equilibrium used in proof of Theorem 3.2. ... Algorithm 2 Algorithm to compute Nash equilibrium used in proof of Theorem E.1. |
| Open Source Code | No | The paper does not contain any statements about making code open-source, providing links to repositories, or including code in supplementary materials. |
| Open Datasets | No | This is a theoretical paper that does not involve empirical experiments with datasets. Therefore, there is no mention of publicly available datasets. |
| Dataset Splits | No | This is a theoretical paper that does not involve empirical experiments with datasets. Therefore, there is no mention of training/test/validation splits. |
| Hardware Specification | No | This is a theoretical paper and does not describe any computational experiments or hardware used to run them. |
| Software Dependencies | No | This is a theoretical paper that proves mathematical results and describes algorithms abstractly. It does not mention specific software dependencies with version numbers required for reproducibility. |
| Experiment Setup | No | This is a theoretical paper that focuses on mathematical proofs and algorithm design. It does not include an 'Experimental Setup' section with hyperparameters or training settings because no empirical experiments are conducted. |