Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs
This work addresses a theoretical problem in formal verification and stochastic control for researchers, providing a complete characterization of strategy complexity, which is incremental as it extends prior results to countable MDPs.
The paper tackles the problem of determining the memory requirements for optimal and near-optimal strategies in countably infinite Markov decision processes with point, total, and mean payoff objectives, establishing that memoryless deterministic strategies suffice in some cases while others require step counters, reward counters, or both.
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 (the sequence of directly seen transition rewards), 2. Total payoff (the sequence of the sums of all rewards so far), and 3. Mean payoff. For each payoff type, the objective is to maximize the probability that the $\liminf$ is non-negative. We establish the complete picture of the strategy complexity of these objectives, i.e., how much memory is necessary and sufficient for $\varepsilon$-optimal (resp. optimal) strategies. Some cases can be won with memoryless deterministic strategies, while others require a step counter, a reward counter, or both.