Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers

• URL: http://arxiv.org/abs/2210.09257v2
• Date: Sat, 15 Apr 2023 12:22:59 GMT
• Title: Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers
• Authors: Luke Marris, Ian Gemp, Thomas Anthony, Andrea Tacchetti, Siqi Liu, Karl Tuyls
• Abstract summary: Solution concepts such as Nash Equilibria, Correlated Equilibria, and Coarse Correlated Equilibria are useful components for many multiagent machine learning algorithms. We introduce the Neural Equilibrium solver which utilizes a special equivariant neural network architecture to approximately solve the space of all games of fixed shape, buying speed and determinism.
• Score: 22.85979978964773
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solution concepts such as Nash Equilibria, Correlated Equilibria, and Coarse Correlated Equilibria are useful components for many multiagent machine learning algorithms. Unfortunately, solving a normal-form game could take prohibitive or non-deterministic time to converge, and could fail. We introduce the Neural Equilibrium Solver which utilizes a special equivariant neural network architecture to approximately solve the space of all games of fixed shape, buying speed and determinism. We define a flexible equilibrium selection framework, that is capable of uniquely selecting an equilibrium that minimizes relative entropy, or maximizes welfare. The network is trained without needing to generate any supervised training data. We show remarkable zero-shot generalization to larger games. We argue that such a network is a powerful component for many possible multiagent algorithms.

Related papers

• Independent Learning in Constrained Markov Potential Games [19.083595175045073]
  Constrained Markov games offer a formal framework for modeling multi-agent reinforcement learning problems. We propose an independent policy gradient algorithm for learning approximate constrained Nash equilibria.
  arXiv  Detail & Related papers  (2024-02-27T20:57:35Z)
• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  We introduce NeuPL-JPSRO, a neural population learning algorithm that benefits from transfer learning of skills and converges to a Coarse Correlated (CCE) of the game. Our work shows that equilibrium convergent population learning can be implemented at scale and in generality.
  arXiv  Detail & Related papers  (2024-01-10T12:56:24Z)
• Robust Adversarial Reinforcement Learning via Bounded Rationality Curricula [23.80052541774509]
  Adversarial Reinforcement Learning trains a protagonist against destabilizing forces exercised by an adversary in a competitive zero-sum Markov game. Finding Nash equilibria requires facing complex saddle point optimization problems, which can be prohibitive to solve. We propose a novel approach for adversarial RL based on entropy regularization to ease the complexity of the saddle point optimization problem.
  arXiv  Detail & Related papers  (2023-11-03T00:00:32Z)
• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  We investigate learning the equilibria in non-stationary multi-agent systems. We show how to test for various types of equilibria by a black-box reduction to single-agent learning.
  arXiv  Detail & Related papers  (2023-06-12T23:48:24Z)
• 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)
• Message Passing Neural PDE Solvers [60.77761603258397]
  We build a neural message passing solver, replacing allally designed components in the graph with backprop-optimized neural function approximators. We show that neural message passing solvers representationally contain some classical methods, such as finite differences, finite volumes, and WENO schemes. We validate our method on various fluid-like flow problems, demonstrating fast, stable, and accurate performance across different domain topologies, equation parameters, discretizations, etc., in 1D and 2D.
  arXiv  Detail & Related papers  (2022-02-07T17:47:46Z)
• Equilibrium Design for Concurrent Games [5.9873770241999]
  In game theory, mechanism design is concerned with the design of incentives so that a desired outcome of the game can be achieved. We study the design of incentives so that a desirable equilibrium is obtained, for instance, an equilibrium satisfying a given temporal logic property. As an application, equilibrium design can be used as an alternative solution to the rational synthesis and verification problems for concurrent games.
  arXiv  Detail & Related papers  (2021-06-18T15:45:45Z)
• Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers [21.462231105582347]
  We propose an algorithm for training agents in n-player, general-sum extensive form games, which provably converges to an equilibrium. We also suggest correlated equilibria (CE) as promising meta-solvers, and propose a novel solution concept Gini Correlated Equilibrium (MGCE) We conduct several experiments using CE meta-solvers for JPSRO and demonstrate convergence on n-player, general-sum games.
  arXiv  Detail & Related papers  (2021-06-17T12:34:18Z)
• Operator Splitting for Learning to Predict Equilibria in Convex Games [26.92001486095397]
  We introduce Nash Fixed Point Networks (N-FPNs), a class of neural networks that naturally output equilibria. N-FPNs are compatible with the recently developed Jacobian-Free Backpropagation technique for training implicit networks. Our experiments show N-FPNs are capable of scaling to problems orders of magnitude larger than existing learned game solvers.
  arXiv  Detail & Related papers  (2021-06-02T02:55:46Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  In large two-player zero-sum imperfect-information games, modern extensions of counterfactual regret minimization (CFR) are currently the practical state of the art for computing a Nash equilibrium. We formalize an online learning setting in which the strategy space is not known to the agent. We give an efficient algorithm that achieves $O(T3/4)$ regret with high probability for that setting, even when the agent faces an adversarial environment.
  arXiv  Detail & Related papers  (2021-03-08T04:03:24Z)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)

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.