The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games

DOI10.1007/978-3-642-39053-1_29MaRDI QIDQ5326375zbMATH OpenOpenAlexFDO

Authors Thomas Dueholm Hansen, Rasmus Ibsen-Jensen

Publication date 5 August 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Interior-point methods (90C51) Stochastic games, stochastic differential games (91A15)

Abstract: We study the problem of solving discounted, two player, turn based, stochastic games (2TBSGs). Jurdzinski and Savani showed that 2TBSGs with deterministic transitions can be reduced to solving $P$-matrix linear complementarity problems (LCPs). We show that the same reduction works for general 2TBSGs. This implies that a number of interior point methods for solving $P$-matrix LCPs can be used to solve 2TBSGs. We consider two such algorithms. First, we consider the unified interior point method of Kojima, Megiddo, Noma, and Yoshise, which runs in time $O((1+kappa)n^{3.5}L)$, where $kappa$ is a parameter that depends on the $nimesn$ matrix $M$ defining the LCP, and $L$ is the number of bits in the representation of $M$. Second, we consider the interior point potential reduction algorithm of Kojima, Megiddo, and Ye, which runs in time $O(frac-deltaheta{n}^{4}logepsilo{n}^{-1})$, where $delta$ and $heta$ are parameters that depend on $M$, and $epsilon$ describes the quality of the solution. For 2TBSGs with $n$ states and discount factor $gamma$ we prove that in the worst case $kappa=Theta(n/(1-gamma{)}^2)$, $-delta=Theta(sqrtn/(1-gamma))$, and $1/heta=Theta(n/(1-gamma{)}^2)$. The lower bounds for $kappa$, $-delta$, and $1/heta$ are obtained using the same family of deterministic games.

Recommendations

• An Interior-Point Differentiable Path-Following Method to Compute Stationary Equilibria in Stochastic Games
• scientific article; zbMATH DE number 3963605
• Exact algorithms for solving stochastic games
• The complexity of solving stochastic games on graphs
• An interior-point algorithm for matrix games
• On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness
• Complexity bounds for approximately solving discounted MDPs by value iterations
• Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor

Cited in

(7)

• Unique end of potential line
• Linear complementarity and P-matrices for stochastic games
• A Simple P-Matrix Linear Complementarity Problem for Discounted Games
• Unique End of Potential Line
• Towards solving 2-TBSG efficiently
• Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
• Two choices are enough for P-LCPs, USOs, and colorful tangents

This page was built for publication: The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326375)