Value iteration for simple stochastic games: stopping criterion and learning algorithm

DOI10.1016/j.ic.2022.104886OpenAlexW4220720160MaRDI QIDQ2672267

Edon Kelmendi, Julia Eisentraut, Maximilian Weininger, Jan Křetínský

Publication date: 8 June 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.04901

zbMATH Keywords

Markov decision processesreachabilitystochastic gamesvalue iterationprobabilistic verification

Mathematics Subject Classification ID

Stochastic games, stochastic differential games (91A15) Markov and semi-Markov decision processes (90C40) Algorithmic game theory and complexity (91A68)

Related Items (1)

Optimistic and topological value iteration for simple stochastic games

Uses Software

• GAVS
• PRISM
• GIST
• PRISM-games
• Storm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Storm
• Quantitative verification and strategy synthesis for stochastic games
• Strategy improvement for concurrent reachability and turn-based stochastic safety games
• A game-based abstraction-refinement framework for Markov decision processes
• Performance analysis of probabilistic timed automata using digital clocks
• Symmetry breaking in distributed networks
• The complexity of stochastic games
• Probabilistic model checking of deadline properties in the IEEE 1394 fireWire root contention protocol
• A near-optimal polynomial time algorithm for learning in certain classes of stochastic games
• A finite algorithm for the switching control stochastic game
• Robot motion planning: A game-theoretic foundation
• Ensuring the reliability of your model checker: interval iteration for Markov decision processes
• Value iteration for long-run average reward in Markov decision processes
• Widest paths and global propagation in bounded value iteration for stochastic games
• Automatic verification of competitive stochastic systems
• Faster statistical model checking for unbounded temporal properties
• Interval iteration algorithm for MDPs and IMDPs
• Verifying Team Formation Protocols with Probabilistic Model Checking
• Verification of Markov Decision Processes Using Learning Algorithms
• Value Iteration
• The Complexity of Solving Stochastic Games on Graphs
• A theory of the learnable
• Linear Programming and Markov Decision Chains
• On the Complexity of Value Iteration
• Efficient Strategy Iteration for Mean Payoff in Markov Decision Processes
• Approximating Values of Generalized-Reachability Stochastic Games
• Decentralized Q-Learning for Stochastic Teams and Games
• On Nonterminating Stochastic Games
• Attracting tangles to solve parity games
• Value iteration for simple stochastic games: stopping criterion and learning algorithm

This page was built for publication: Value iteration for simple stochastic games: stopping criterion and learning algorithm