Symmetric strategy improvement
From MaRDI portal
Publication:3449491
DOI10.1007/978-3-662-47666-6_31zbMATH Open1440.91005arXiv1501.06484OpenAlexW1495265525MaRDI QIDQ3449491FDOQ3449491
Authors: Sven Schewe, Ashutosh Trivedi, Thomas Varghese 
Publication date: 4 November 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Abstract: Symmetry is inherent in the definition of most of the two-player zero-sum games, including parity, mean-payoff, and discounted-payoff games. It is therefore quite surprising that no symmetric analysis techniques for these games exist. We develop a novel symmetric strategy improvement algorithm where, in each iteration, the strategies of both players are improved simultaneously. We show that symmetric strategy improvement defies Friedmann's traps, which shook the belief in the potential of classic strategy improvement to be polynomial.
Full work available at URL: https://arxiv.org/abs/1501.06484
Recommendations
Cites Work
- The complexity of mean payoff games on graphs
- Alternating-time temporal logic
- Title not available (Why is that?)
- Results on the propositional \(\mu\)-calculus
- Title not available (Why is that?)
- A subexponential randomized algorithm for the simple stochastic game problem
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Infinite games played on finite graphs
- An improved algorithm for the evaluation of fixpoint expressions
- Title not available (Why is that?)
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Synthesis of Asynchronous Systems
- Satisfiability and Finite Model Property for the Alternating-Time μ-Calculus
- Title not available (Why is that?)
- From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
- DAG-Width and Parity Games
- Solving Parity Games in Big Steps
- Fast mu-calculus model checking when tree-width is bounded.
- Alternating tree automata, parity games, and modal \(\mu\)-calculus
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
- A superpolynomial lower bound for strategy iteration based on snare memorization
- Non-oblivious strategy improvement
- An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
- An exponential lower bound for the latest deterministic strategy iteration algorithms
- Symmetric strategy improvement
- Exponential lower bounds for policy iteration
Cited In (10)
- Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games
- Parity games with weights
- A delayed promotion policy for parity games
- A delayed promotion policy for parity games
- Priority promotion with Parysian flair
- Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
- Improvement in small progress measures
- Non-oblivious strategy improvement
- Symmetric strategy improvement
- Title not available (Why is that?)
Uses Software
This page was built for publication: Symmetric strategy improvement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449491)
