Jul, 2023
具有时间变化的几何折扣的马尔可夫决策过程
Markov Decision Processes with Time-Varying Geometric Discounting
Jiarui Gan, Annika Hennes, Rupak Majumdar, Debmalya Mandal, Goran Radanovic
TL;DR研究了时间变动折扣率的无限时间段马尔可夫决策过程，以一个博弈论的视角看待每一个时间步骤为一个独立决策者，研究了所得到博弈的次游戏最佳均衡点（SPE）以及相关的算法问题。提出了 SPE 的存在性的构造性证明，证明了计算 SPE 的 EXPTIME 难度，同时证明了在较弱的假设条件下存在一个近似 SPE（ε-SPE）。提供了计算 ε-SPE 的算法，并提供了时间复杂度上界，该上界是基于时间变动折扣率的收敛特性的函数。