Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs

Richard Mayr, Eric Munday

We study countably infinite Markov decision processes (MDPs) with real-valued transition rewards. Every infinite run induces the following sequences of payoffs: 1. Point payoff (th…