Oct, 2021
基于线性实现最优值函数的 MDP 计划的张量计划及少动作下限
TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functions
Gellért Weisz, Csaba Szepesvári, András György
TL;DR本研究考虑了在线规划中基于生成模型的固定时标马尔可夫决策过程（MDP）中的极小化查询复杂度，特别关注线性函数逼近的情况，并基于先前的研究，都采用了广泛的问题类别，提出了 TensorPlan，可在动作数量固定的情况下实现所有相关数量的多项式查询成本，但在本文中，我们在 (ii) 及 (iii) 情况下证明了当动作集大小可以选择为指数函数时查询复杂度为指数级，这意味着相对于对所有状态情况 (iii) 成立的 Du 等人的工作，查询复杂度有惊人的指数级分离，并且我们还证明了 TensorPlan 的上界可用于 (iii) 的情况，并且，对于具有确定性转换和随机奖励的 MDP，TensorPlan 的上界也可用于 (ii) 情况。