Online Learning for Unknown Partially Observable MDPs
Online Learning for Unknown Partially Observable MDPs
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Mehdi Jafarnia-Jahromi;Rahul Jain;A. Nayyar
中科院分区：
文献类型：
--
作者：
Mehdi Jafarnia-Jahromi;Rahul Jain;A. Nayyar
解决部分可观察马尔可夫决策过程 (POMDP) 很困难。当模型未知时，学习 POMDP 的最佳控制器会更加困难。未知 POMDP 的最优控制器的在线学习更加困难，这需要使用遗憾最小化算法来有效地权衡探索和利用，从而进行有效的学习，目前还没有解决方案。在本文中，我们考虑了具有未知转换模型（尽管已知观察模型）的无限范围平均成本 POMDP。我们提出了一种基于自然后采样的强化学习算法（PSRL-POMDP），并表明当参数集有限时，它实现了 $O(\log T)$ 的后悔界限，其中 $T$ 是时间范围。在一般情况下（连续参数集），我们表明该算法在两个技术假设下实现了 $O (T^{2/3})$ 遗憾。据我们所知，这是第一个针对 POMDP 的在线 RL 算法，并且具有次线性遗憾。
Solving Partially Observable Markov Decision Processes (POMDPs) is hard. Learning optimal controllers for POMDPs when the model is unknown is harder. Online learning of optimal controllers for unknown POMDPs, which requires efficient learning using regret-minimizing algorithms that effectively tradeoff exploration and exploitation, is even harder, and no solution exists currently. In this paper, we consider infinite-horizon average-cost POMDPs with unknown transition model, though a known observation model. We propose a natural posterior sampling-based reinforcement learning algorithm (PSRL-POMDP) and show that it achieves a regret bound of $O(\log T)$, where $T$ is the time horizon, when the parameter set is finite. In the general case (continuous parameter set), we show that the algorithm achieves $O (T^{2/3})$ regret under two technical assumptions. To the best of our knowledge, this is the first online RL algorithm for POMDPs and has sub-linear regret.