# Stochastic games

2018 / 04 / 04

This post is to plan to list some reference about Stochastic Games.

## Positive results

#### Paper of reviews

- Worst-case Analysis of Strategy Iteration and the Simplex Method, thesis

#### Polynomial results for discounted MDP and 2TBSG

- The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate, (paper)
- Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor, (paper)

#### Polynomial results for deterministic MDP

- The simplex method is strongly polynomial for deterministic Markov decision processes, (paper)

## Negetave results

#### Policy iteration for stochastic MDP

- Exponential Lower Bounds For Policy Iteration, (paper)
- The complexity of Policy Iteration is exponential for discounted Markov Decision Processes, (paper)

#### Policy iteration for deterministic MDP

- Lower bounds for Howardâ€™s algorithm for finding Minimum Mean-Cost Cycles, (paper)
- Improved and Generalized Upper Bounds on the Complexity of Policy Iteration, (paper)

## LCP for 2TBSG

#### LCP formulation

- The complexity of interior point methods for solving discounted turn-based stochastic games, (paper)