一句话：完整刻画可数MDP中三类收益目标下ε最优与最优策略所需和充分的内存，给出策略复杂度分类。
论文研究具有实值转移回报的可数无限马尔可夫决策过程（MDP）。每条无限运行产生三种收益序列：逐点收益（直接观察到的转移回报序列）、平均收益（至今回报和除以步数）和总收益（至今回报和）。对每种收益，目标是最大化 liminf 非负的概率。作者建立这些目标的策略复杂度完整图景，即对 ε-最优和最优策略，判定需要何种内存、何种内存足够。结果表明不同情形差异显著：部分可用无记忆确定性策略获胜，部分需要步数计数器、回报计数器或两者兼需。该工作给出匹配的上下界，统一了可数MDP中多类收益目标的策略内存需求分类。
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. Mean payoff (the sequence of the sums of all rewards so far, divided by the number of steps), and 3. Total payoff (the sequence of the sums of all rewards so far). 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.
@article{paperbot2232,
title = {Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs},
author = {Richard Mayr and Eric Munday},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 1},
year = {2023},
doi = {10.46298/lmcs-19(1:16)2023}
}