# A Convex Programming-based Algorithm for Mean Payoff Stochastic Games with Perfect Information

arXiv: https://arxiv.org/abs/1610.06681 · HTML: https://mlsanity.com/paper/1610.06681/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2016.

## Built on by (most cited first, 2 of 2)

- [On the convex formulations of robust Markov decision processes](https://mlsanity.com/paper/2209.10187/) (2022)
- [Resilient Strategies for Stochastic Systems: How Much Does It Take to Break a Winning Strategy?](https://mlsanity.com/paper/2602.24191/) (2026)

## Abstract (arXiv)

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G = (V, E), with local rewards r: E → ZZ, and three types of positions: black VB, white VW, and random VR forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when |VR|=0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant.