3 papers
cs.GT2021
A Generic Strategy Improvement Method for Simple Stochastic Games
D. Auger, X. Badin de Montjoye, Y. Strozecki
We present a generic strategy iteration algorithm (GSIA) to find an optimal strategy of a simple stochastic game (SSG). We prove the correctness of GSIA, and derive a general compl…
cs.DS2019
Solving Simple Stochastic Games with few Random Nodes faster using Bland's Rule
David Auger, Pierre Coucheney, Yann Strozecki
The best algorithm so far for solving Simple Stochastic Games is Ludwig's randomized algorithm which works in expected time. We first give a simpler iterative var…
cs.GT2011
Multiple Tree for Partially Observable Monte-Carlo Tree Search
David Auger
We propose an algorithm for computing approximate Nash equilibria of partially observable games using Monte-Carlo tree search based on recent bandit methods. We obtain experimental…