Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
Authors: Brian Zhang, Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we develop efficient parameterized algorithms for regimes between these two extremes. We introduce the set of k-mediator deviations, which generalize the untimed communication deviations recently introduced by Zhang, Farina and Sandholm [2024] to the case of having multiple mediators, and we develop algorithms for minimizing the regret with respect to this set of deviations in N O(k)/ϵ2 rounds. Moreover, by relating k-mediator deviations to low-degree polynomials, we show that regret minimization against degree-k polynomial swap deviations is achievable in N O(kd)3/ϵ2 rounds, where d is the depth of the game, assuming a constant branching factor. |
| Researcher Affiliation | Collaboration | Brian Hu Zhang Carnegie Mellon University bhzhang@cs.cmu.edu Ioannis Anagnostides Carnegie Mellon University ianagnos@cs.cmu.edu Gabriele Farina MIT gfarina@mit.edu Tuomas Sandholm Carnegie Mellon University Strategic Machine, Inc. Strategy Robot, Inc. Optimized Markets, Inc. sandholm@cs.cmu.edu |
| Pseudocode | Yes | Algorithm 1: Φ-regret minimizer using fixed points in expectation |
| Open Source Code | No | The paper does not include any statement or link indicating that the source code for the described methodology is openly available. |
| Open Datasets | No | This is a theoretical paper focused on algorithms and proofs; it does not involve the use of datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper without experimental validation on datasets, thus no dataset splits (training, validation, test) are mentioned. |
| Hardware Specification | No | This is a theoretical paper that does not report on experiments, and therefore, no hardware specifications are provided. |
| Software Dependencies | No | This is a theoretical paper that does not report on experiments, and therefore, no software dependencies with specific version numbers are mentioned. |
| Experiment Setup | No | This is a theoretical paper that does not report on experiments, and therefore, no experimental setup details like hyperparameters or training settings are provided. |