Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Yue Wu;Dongruo Zhou;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Yue Wu;Dongruo Zhou;Quanquan Gu
我们研究了具有线性函数近似的无限时域平均奖励设置中的强化学习，其中底层马尔可夫决策过程（MDP）的转移概率函数在当前状态，动作和下一状态的特征映射上具有线性形式。我们提出了一个新的算法UCRL 2-VTR，它可以看作是UCRL 2算法的线性函数逼近的扩展。我们发现，UCRL 2-VTR与伯恩斯坦型奖金可以实现$\tilde{O}（d\sqrt{DT}）$的遗憾，其中$d$是特征映射的尺寸，$T$是地平线，和$\sqrt{D}$是直径的MDP。我们还证明了一个匹配的下界$\tilde{\Omega}（d\sqrt{DT}）$，这表明建议的UCRL 2-VTR是最小最大最优的对数因子。据我们所知，我们的算法是第一个近极大极小最优RL算法的函数近似在无限水平平均奖励设置。
We study reinforcement learning in an infinite-horizon average-reward setting with linear function approximation, where the transition probability function of the underlying Markov Decision Process (MDP) admits a linear form over a feature mapping of the current state, action, and next state. We propose a new algorithm UCRL2-VTR, which can be seen as an extension of the UCRL2 algorithm with linear function approximation. We show that UCRL2-VTR with Bernstein-type bonus can achieve a regret of $\tilde{O}(d\sqrt{DT})$, where $d$ is the dimension of the feature mapping, $T$ is the horizon, and $\sqrt{D}$ is the diameter of the MDP. We also prove a matching lower bound $\tilde{\Omega}(d\sqrt{DT})$, which suggests that the proposed UCRL2-VTR is minimax optimal up to logarithmic factors. To the best of our knowledge, our algorithm is the first nearly minimax optimal RL algorithm with function approximation in the infinite-horizon average-reward setting.