Towards solving 2-TBSG efficiently

DOI10.1080/10556788.2019.1695131zbMath1454.91021arXiv1906.03553OpenAlexW2995864482WikidataQ126530985 ScholiaQ126530985MaRDI QIDQ5135251

Zeyu Jia, Yinyu Ye, ZaiWen Wen

Publication date: 19 November 2020

Published in: Optimization Methods and Software (Search for Journal in Brave)

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

zbMATH Keywords

Markov decision processstrongly polynomial timesimplex strategy iterationtwo-player turn-based stochastic game

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms for discounted stochastic games
• Finite state Markovian decision processes
• The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
• A Simple P-Matrix Linear Complementarity Problem for Discounted Games
• Exponential Lower Bounds for Policy Iteration
• Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor
• A New Complexity Result on Solving the Markov Decision Problem
• The simplex method is strongly polynomial for deterministic Markov decision processes
• Stochastic Games

This page was built for publication: Towards solving 2-TBSG efficiently