Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games
Authors: Dylan J Foster, Noah Golowich, Sham M. Kakade
ICML 2023 | Venue PDF | 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<EMAIL>, Noah Golowich<EMAIL>, Sham M. Kakade<EMAIL>. |
| 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. |