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
- 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 an algorithm that achieves a constant regret while solving LPs only $O(loglog T)$ times over the time horizon $T$.
Our algorithm can guarantee a constant regret by solving LPs $O(loglog T)$ times, and an $Oleft(T(1/2+epsilon)Mright)$ regret by solving LPs only $M$ times.
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) - Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
In a Stackelberg congestion game (SCG), a leader aims to maximize their own gain by anticipating and manipulating the equilibrium state at which the followers settle by playing a congestion game.
Here, we attempt to tackle this computational challenge by marrying traditional methodologies with the latest differentiable programming techniques in machine learning.
We propose two new local search algorithms for SCGs. The first is a gradient descent algorithm that obtains the derivatives by unrolling ILD via differentiable programming.
The second algorithm adds a twist by cutting short the followers' evolution trajectory.
arXiv Detail & Related papers (2022-09-15T21:32:23Z) - A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for
Nonconvex Functional Constrained Optimization [27.07082875330508]
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) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
We introduce a new inference scheme that avoids explicit construction of the covariance matrix.
Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm.
On several simulations, our method scales better than existing approaches in computation time and memory.
arXiv Detail & Related papers (2022-02-25T16:35:26Z) - Coordinate Linear Variance Reduction for Generalized Linear Programming [27.365677554732304]
We show that the linear structure in the problem can be used to design an efficient, scalable first-order algorithm.
textscclvr yields improved complexity results for (GLP) that depend on the max row norm of the linear constraint matrix in (GLP) rather than the spectral norm.
arXiv Detail & Related papers (2021-11-02T18:57:23Z) - 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) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem.
Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm.
Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
arXiv Detail & Related papers (2020-08-12T08:52:50Z)
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.