An Objective Improvement Approach to Solving Discounted Payoff Games

Abstract

While discounted payoff games and classic games that reduce to them, like parity and mean-payoff games, are symmetric, their solutions are not. We have taken a fresh view on the constraints that optimal solutions need to satisfy, and devised a novel way to converge to them, which is entirely symmetric. It also challenges the gospel that methods for solving payoff games are either based on strategy improvement or on value iteration.

arXiv commentIn Proceedings GandALF 2023, arXiv:2309.17318

References in corpus (5)

• From Nondeterministic Büchi and Streett Automata to Deterministic Parity Automata
• Succinct progress measures for solving parity games
• Non-oblivious Strategy Improvement
• A Recursive Approach to Solving Parity Games in Quasipolynomial Time
• Smaller Progress Measures and Separating Automata for Parity Games