Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract)

• URL: http://arxiv.org/abs/2210.09924v2
• Date: Thu, 27 Jul 2023 08:55:04 GMT
• Title: Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract)
• Authors: Tobias Hecking and Swathy Muthukrishnan and Alexander Weinert
• Abstract summary: We present an incomplete-time approach to determining the winning regions of parity games via graph neural networks. It correctly determines the winning regions of $$60% of the games in our data set and only incurs minor errors in the remaining ones.
• Score: 68.8204255655161
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Solving parity games is a major building block for numerous applications in reactive program verification and synthesis. While they can be solved efficiently in practice, no known approach has a polynomial worst-case runtime complexity. We present a incomplete polynomial-time approach to determining the winning regions of parity games via graph neural networks. Our evaluation on 900 randomly generated parity games shows that this approach is effective and efficient in practice. It correctly determines the winning regions of $\sim$60\% of the games in our data set and only incurs minor errors in the remaining ones. We believe that this approach can be extended to efficiently solve parity games as well.

Related papers

• Runtime analysis of a coevolutionary algorithm on impartial combinatorial games [1.104960878651584]
  Coevolutionary algorithms (CoEAs) evolve a population of individuals by iteratively selecting the strongest based on their interactions against contemporaries, and using those selected as parents for the following generation. However, the successful application of CoEAs for game playing is difficult due to pathological behaviours such as cycling, an issue especially critical for games with in runtime payoff landscapes. In this paper, we push the scope of analysis to discover an optimal strategy for an impartial game. This result applies to any impartial game, and for many games the implied bound is or quasipolynomial as a function of the number of
  arXiv  Detail & Related papers  (2024-09-06T10:39:17Z)
• History Filtering in Imperfect Information Games: Algorithms and Complexity [16.23892847804002]
  We introduce and analyze the computational aspects and tractability of filtering histories for subgame decomposition. We show that constructing a single history from the root of the subgame is generally intractable. We also introduce a novel Markov Chain Monte Carlo-based generation algorithm for trick-taking card games.
  arXiv  Detail & Related papers  (2023-11-24T18:34:36Z)
• 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)
• Convergence analysis and acceleration of the smoothing methods for solving extensive-form games [0.6875312133832078]
  We consider an extended-form game with two players and zero-sum, i.e., the sum of their payoffs is always zero. In such games, the problem of finding the optimal strategy can be formulated as a bilinear saddle-point problem. To solve such large-scale bilinear saddle-point problems, the excessive gap technique (EGT), a smoothing method, has been studied. Our goal is to improve the smoothing method for solving extensive-form games so that it can be applied to large-scale games.
  arXiv  Detail & Related papers  (2023-03-20T11:57:13Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Public Information Representation for Adversarial Team Games [31.29335755664997]
  adversarial team games reside in the asymmetric information available to the team members during the play. Our algorithms convert a sequential team game with adversaries to a classical two-player zero-sum game. Due to the NP-hard nature of the problem, the resulting Public Team game may be exponentially larger than the original one.
  arXiv  Detail & Related papers  (2022-01-25T15:07:12Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  Combinatorial bandits generalize multi-armed bandits, where the agent chooses sets of arms and observes a noisy reward for each arm contained in the chosen set. We focus on the pure-exploration problem of identifying the best arm with fixed confidence, as well as a more general setting, where the structure of the answer set differs from the one of the action set. Based on a projection-free online learning algorithm for finite polytopes, it is the first computationally efficient algorithm which is convexally optimal and has competitive empirical performance.
  arXiv  Detail & Related papers  (2021-01-21T10:35:09Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  We study exploration in multi-armed bandits when we have access to a divisible resource that can be allocated in varying amounts to arm pulls. We focus in particular on the allocation of distributed computing resources, where we may obtain results faster by allocating more resources per pull.
  arXiv  Detail & Related papers  (2020-10-31T18:19:29Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
  arXiv  Detail & Related papers  (2020-09-21T17:51:57Z)

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.