一句话：研究随机博弈中竞技场无关有限记忆策略的充分性，证明其可归约到单玩家随机博弈并给出两组刻画。
本文研究图上随机零和博弈中的策略复杂度问题：在随机环境下面对对抗性对手时，哪些目标需要随机化或记忆才能最优。作者聚焦竞技场无关有限记忆（AIFM）确定性，即所需记忆仅依赖游戏图的有限参数，而不依赖具体竞技场。文章给出三项结果：第一，若某目标存在最优纯 AIFM 策略，则也存在纯 AIFM 子博弈完美策略；第二，将两玩家随机博弈中纯 AIFM 策略充分性的研究归约到一玩家随机博弈（即 MDP）；第三，用目标的两个直观性质刻画 AIFM 策略的充分性。该工作把确定性博弈中的相关研究推广到随机博弈。
We study stochastic zero-sum games on graphs, which are prevalent tools to model decision-making in presence of an antagonistic opponent in a random environment. In this setting, an important question is the one of strategy complexity: what kinds of strategies are sufficient or required to play optimally (e.g., randomization or memory requirements)? Our contributions further the understanding of arena-independent finite-memory (AIFM) determinacy, i.e., the study of objectives for which memory is needed, but in a way that only depends on limited parameters of the game graphs. First, we show that objectives for which pure AIFM strategies suffice to play optimally also admit pure AIFM subgame perfect strategies. Second, we show that we can reduce the study of objectives for which pure AIFM strategies suffice in two-player stochastic games to the easier study of one-player stochastic games (i.e., Markov decision processes). Third, we characterize the sufficiency of AIFM strategies through two intuitive properties of objectives. This work extends a line of research started on deterministic games to stochastic ones.
@article{paperbot2176,
title = {Arena-Independent Finite-Memory Determinacy in Stochastic Games},
author = {Patricia Bouyer and Youssouf Oualhadj and Mickael Randour and Pierre Vandenhove},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 4},
year = {2023},
doi = {10.46298/lmcs-19(4:18)2023}
}