2019/09/13 by Corto Mascle, Mascle, Corto, Mahsa Shirmohammadi +3 · 1 citation
Computer Science · Mathematics · #Reinforcement Learning in Robotics #Markov Chains and Monte Carlo Methods #Distributed systems and fault tolerance
paper · pdf · doi:10.48550/arxiv.1909.06420
Bertrand et al. [1] (LMCS 2019) describe two-player zero-sum games in which one player tries to achieve a reachability objective in n games (on the same finite arena) simultaneously by broadcasting actions, and where the opponent has full control of resolving non-deterministic choices. They show EXPTIME completeness for the question if such games can be won for every number n of games. We consider the almost-sure variant in which the opponent randomizes their actions, and where the player tries to achieve the reachability objective eventually with probability one. The lower bound construction in [1] does not directly carry over to this randomized setting. In this note we show EXPTIME hardness for the almost-sure problem by reduction from Countdown Games.