Showing cs.GTShow all
3 papers · 1 filter
cs.GT2022
Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs
David Auger, Pierre Coucheney, Loric Duhaze
A rotor walk in a directed graph can be thought of as a deterministic version of a Markov Chain, where a pebble moves from vertex to vertex following a simple rule until a terminal…
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.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…