Sparsified Linear Programming for Zero-Sum Equilibrium Finding

• URL: http://arxiv.org/abs/2006.03451v2
• Date: Mon, 29 Jun 2020 22:23:06 GMT
• Title: Sparsified Linear Programming for Zero-Sum Equilibrium Finding
• Authors: Brian Hu Zhang, Tuomas Sandholm
• Abstract summary: We present a totally different approach to the problem, which is competitive and often orders of magnitude better than the prior state of the art. With experiments on poker endgames, we demonstrate, for the first time, that modern linear program solvers are competitive against even game-specific modern variants of CFR.
• Score: 89.30539368124025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Computational equilibrium finding in large zero-sum extensive-form imperfect-information games has led to significant recent AI breakthroughs. The fastest algorithms for the problem are new forms of counterfactual regret minimization [Brown and Sandholm, 2019]. In this paper we present a totally different approach to the problem, which is competitive and often orders of magnitude better than the prior state of the art. The equilibrium-finding problem can be formulated as a linear program (LP) [Koller et al., 1994], but solving it as an LP has not been scalable due to the memory requirements of LP solvers, which can often be quadratically worse than CFR-based algorithms. We give an efficient practical algorithm that factors a large payoff matrix into a product of two matrices that are typically dramatically sparser. This allows us to express the equilibrium-finding problem as a linear program with size only a logarithmic factor worse than CFR, and thus allows linear program solvers to run on such games. With experiments on poker endgames, we demonstrate in practice, for the first time, that modern linear program solvers are competitive against even game-specific modern variants of CFR in solving large extensive-form games, and can be used to compute exact solutions unlike iterative algorithms like CFR.

Related papers

• Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
  We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium. We also give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium. Our algorithm for approximately optimal EFCE is, to our knowledge, the first that achieves 3 desiderata simultaneously.
  arXiv  Detail & Related papers  (2024-12-22T09:12:05Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Infrequent Resolving Algorithm for Online Linear Programming [3.247415064064425]
  Existing online linear programming (OLP) algorithms fall into two categories: LP-based algorithms and LP-free algorithms. We propose a well-performing algorithm, that solves LPs at a few selected time points and conducts first-order computations at other time points. Our work highlights the value of resolving both at the beginning and the end of the selling horizon, and provides a novel framework to prove the performance guarantee.
  arXiv  Detail & Related papers  (2024-08-01T11:09:01Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  We propose a model-based primal-dual algorithm to learn in an unknown CMDP. We prove that our algorithm achieves sublinear regret without error cancellations.
  arXiv  Detail & Related papers  (2024-02-24T09:47:46Z)
• An efficient, provably exact, practical algorithm for the 0-1 loss linear classification problem [4.418462313508022]
  We show that incremental cell (ICE) can solve the 0-1 loss classification problem exactly in time. This is the first, rigorously-proven, practical algorithm for this long-standing problem.
  arXiv  Detail & Related papers  (2023-06-21T15:41:34Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  We consider the problem of decentralized multi-agent reinforcement learning in Markov games. We show that no algorithm attains no-regret in general-sum games when executed independently by all players. We show that our lower bounds hold even for seemingly easier setting in which all agents are controlled by a centralized algorithm.
  arXiv  Detail & Related papers  (2023-03-22T03:28:12Z)
• A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization [35.003192679045675]
  Non constrained inequality problems can be used to model a number machine learning problems, such as multi-class Neyman oracle. Under such a mild condition of regularity it is difficult to balance reduction alternating value loss and reduction constraint violation. In this paper, we propose a novel primal-dual inequality constrained problems algorithm.
  arXiv  Detail & Related papers  (2022-07-12T16:30:34Z)
• Covariance-Free Sparse Bayesian Learning [62.24008859844098]
  We introduce a new SBL inference algorithm that avoids explicit inversions of the covariance matrix. Our method can be up to thousands of times faster than existing baselines. We showcase how our new algorithm enables SBL to tractably tackle high-dimensional signal recovery problems.
  arXiv  Detail & Related papers  (2021-05-21T16:20:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.