Automated Approach for Solving Infinite-state Polynomial Reachability Games

• URL: http://arxiv.org/abs/2605.10169v1
• Date: Mon, 11 May 2026 08:19:14 GMT
• Title: Automated Approach for Solving Infinite-state Polynomial Reachability Games
• Abstract summary: We study turn-based reachability games on infinite-state graphs defined over valuations of a finite set of real variables.<n>We propose ranking certificates for reachability games, a sound and complete proof rule for proving that $texttREACH$ player has a winning strategy from the specified initial state.<n>Our experiments demonstrate the ability of our method to solve challenging examples from the literature that were out of the reach of existing methods.
• Score: 9.066824933763142
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reachability games are two-player games played on a graph, where the objective of $\texttt{REACH}$ player is to reach the target set whereas the objective of $\texttt{SAFE}$ player is to stay away from the target set. Reachability games have important applications in artificial intelligence and reactive synthesis, and many of these applications give rise to infinite-state reachability games. In this paper, we study turn-based reachability games on infinite-state graphs defined over valuations of a finite set of real variables. We consider the problem of determining the existence of and computing a winning strategy for $\texttt{REACH}$ player. Our contributions are twofold. First, we propose ranking certificates for reachability games, a sound and complete proof rule for proving that $\texttt{REACH}$ player has a winning strategy from the specified initial state. Second, we consider polynomial reachability games, where transitions and objectives are described by polynomial constraints over real variables, and propose a fully automated algorithm for computing a winning strategy for $\texttt{REACH}$ player together with a formal correctness witness in the form of a ranking certificate. The algorithm is sound, semi-complete, and runs in sub-exponential time. Our experiments demonstrate the ability of our method to solve challenging examples from the literature that were out of the reach of existing methods. Specifically, for the classical Cinderella-Stepmother game, we are able to compute an optimal winning strategy for an arbitrary precision parameter for the first time.

Related papers

• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  We show that for a large family of games, there exists a simple black-box reduction that transforms the average iterates of an uncoupled learning dynamics into the last iterates of a new uncoupled learning dynamics.<n>Our reduction applies to games where each player's utility is linear in both their own strategy and the joint strategy of all opponents.
  arXiv  Detail & Related papers  (2025-06-04T00:24:14Z)
• Mastering Strategy Card Game (Legends of Code and Magic) via End-to-End Policy and Optimistic Smooth Fictitious Play [11.480308614644041]
  We study a two-stage strategy card game Legends of Code and Magic. We propose an end-to-end policy to address the difficulties that arise in multi-stage game. Our approach wins double championships of COG2022 competition.
  arXiv  Detail & Related papers  (2023-03-07T17:55:28Z)
• Learning to Play Stochastic Two-player Perfect-Information Games without Knowledge [5.071342645033634]
  We extend the Descent framework, which enables learning and planning in the context of two-player games with perfect information. We evaluate them on the game Ein wurfelt! against state-of-the-art algorithms. It is our generalization of Descent which obtains the best results.
  arXiv  Detail & Related papers  (2023-02-08T20:27:45Z)
• 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)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
  arXiv  Detail & Related papers  (2022-07-25T18:29:16Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  We show that regret can be obtained for general convex and compact strategy sets. Our dynamics are on an instantiation of optimistic follow-the-regularized-bounds over an appropriately emphlifted space. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret.
  arXiv  Detail & Related papers  (2022-06-17T12:58:58Z)
• A Ranking Game for Imitation Learning [22.028680861819215]
  We treat imitation as a two-player ranking-based Stackelberg game between a $textitpolicy$ and a $textitreward$ function. This game encompasses a large subset of both inverse reinforcement learning (IRL) methods and methods which learn from offline preferences. We theoretically analyze the requirements of the loss function used for ranking policy performances to facilitate near-optimal imitation learning at equilibrium.
  arXiv  Detail & Related papers  (2022-02-07T19:38:22Z)
• Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic Games with Independent Chains [2.132096006921048]
  We consider a class of $n$-player games in which players have their own internal state/action spaces while they are coupled through their payoff functions. For this class of games, we first show that finding a stationary Nash (NE) policy without any assumption on the reward functions is interactable. We develop algorithms based on dual averaging and dual mirror descent, which converge to the set of $epsilon$-NE policies.
  arXiv  Detail & Related papers  (2022-01-28T16:27:21Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
  arXiv  Detail & Related papers  (2021-11-07T21:15:35Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  We study reinforcement learning for two-player zero-sum Markov games with simultaneous moves. We propose an algorithm Nash-UCRL-VTR based on the principle "Optimism-in-Face-of-Uncertainty" We show that Nash-UCRL-VTR can provably achieve an $tildeO(dHsqrtT)$ regret, where $d$ is the linear function dimension.
  arXiv  Detail & Related papers  (2021-02-15T09:09:16Z)
• Complexity and Algorithms for Exploiting Quantal Opponents in Large Two-Player Games [16.43565579998679]
  Solution concepts of traditional game theory assume entirely rational players; therefore, their ability to exploit subrational opponents is limited. This paper aims to analyze and propose scalable algorithms for computing effective and robust strategies against a quantal opponent in normal-form and extensive-form games.
  arXiv  Detail & Related papers  (2020-09-30T09:14:56Z)
• Equilibria for Games with Combined Qualitative and Quantitative Objectives [15.590197778287616]
  We study concurrent games in which each player is a process that is assumed to act independently and strategically. Our main result is that deciding the existence of a strict epsilon Nash equilibrium in such games is 2ExpTime-complete.
  arXiv  Detail & Related papers  (2020-08-13T01:56:24Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  We focus on self-play algorithms which learn the optimal policy by playing against itself without any direct supervision. We propose an optimistic variant of the emphNash Q-learning algorithm with sample complexity $tildemathcalO(SAB)$, and a new emphNash V-learning algorithm with sample complexity $tildemathcalO(S(A+B))$.
  arXiv  Detail & Related papers  (2020-06-22T05:00:13Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

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.