Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Chen-Yu Wei;Mehdi Jafarnia-Jahromi;Haipeng Luo;Rahul Jain
中科院分区：
文献类型：
--
作者：
Chen-Yu Wei;Mehdi Jafarnia-Jahromi;Haipeng Luo;Rahul Jain
提出了几种基于线性函数逼近的马尔可夫决策过程学习算法。利用乐观原理并假设MDP具有线性结构，我们首先提出了一种具有最优$\ widdetilde {O}(\sqrt{T})$后悔的计算效率较低的算法和另一种具有$\ widdetilde {O}(T^{3/4})$后悔的计算效率较高的算法，其中$T$为交互次数。接下来，从对抗性线性强盗（adversarial linear bandits）中获得灵感，我们在不同的假设集下开发了另一种使用$\ widdetilde {O}(\sqrt{T})$ regret的高效算法，改进了Hao等人（2020）使用$\ widdetilde {O}(T^{2/3})$ regret的最佳现有结果。此外，我们将该算法与Kakade（2002）提出的自然策略梯度算法（Natural Policy Gradient algorithm）联系起来，并表明我们的分析改进了Agarwal等人（2020）最近给出的样本复杂度界。
We develop several new algorithms for learning Markov Decision Processes in an infinite-horizon average-reward setting with linear function approximation. Using the optimism principle and assuming that the MDP has a linear structure, we first propose a computationally inefficient algorithm with optimal $\widetilde{O}(\sqrt{T})$ regret and another computationally efficient variant with $\widetilde{O}(T^{3/4})$ regret, where $T$ is the number of interactions. Next, taking inspiration from adversarial linear bandits, we develop yet another efficient algorithm with $\widetilde{O}(\sqrt{T})$ regret under a different set of assumptions, improving the best existing result by Hao et al. (2020) with $\widetilde{O}(T^{2/3})$ regret. Moreover, we draw a connection between this algorithm and the Natural Policy Gradient algorithm proposed by Kakade (2002), and show that our analysis improves the sample complexity bound recently given by Agarwal et al. (2020).