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

We study countably infinite Markov decision processes (MDPs) with real-valuedtransition rewards. Every infinite run induces the following sequences ofpayoffs: 1. Point payoff (the sequence of directly seen transition rewards), 2.Mean payoff (the sequence of the sums of all rewards so far, divided by thenumber of steps), and 3. Total payoff (the sequence of the sums of all rewardsso far). For each payoff type, the objective is to maximize the probabilitythat the $\liminf$ is non-negative. We establish the complete picture of thestrategy complexity of these objectives, i.e., how much memory is necessary andsufficient for $\varepsilon$-optimal (resp. optimal) strategies. Some cases canbe won with memoryless deterministic strategies, while others require a stepcounter, a reward counter, or both.Comment: arXiv admin note: substantial text overlap with arXiv:2107.0328