We consider two-player stochastic games on a graph. Two-player stochastic games are a generalization of two-player games and Markov decision processes. Each state in the graph is controlled by one of the two players P1 and P2. The game begins by placing a token on the initial state. In each turn, the player controlling the state of the token chooses an action, which then returns a probability distribution over the out-edges from the state. An out-edge is chosen according to this distribution, the token is moved along this edge to a new state, and the turn ends. The game then starts from the new state, and the player who controls this new state chooses an action available from that state.
This continues ad infinitum.
In this work, we consider window mean-payoff objective. Each edge has a rational payoff. The sequence of edges chosen in a play corresponds to a sequence of payoffs. Given an integer l, and a threshold \lambda, the objective of player P1 is to ensure that from every state in a play, for some interval window of length at most l, the mean of the payoffs in the window is at least \lambda. The objective of player P2 is the complement of P1's objective. Window mean-payoff objectives have been studied for two-player games and for Markov decision processes earlier. We study here two-player stochastic games with window objectives.
