Mean-Payoff-Parity and Lifting Strategies from MDPs to 2-Player Stochastic Games

Mohan Dantam, Richard Mayr

We consider the strategy complexity (i.e., memory and randomization) of optimal strategies in turn-based 2-player zero-sum stochastic games. Results in [Gimbert,Kelmendi:2023] show…