Sample-Efficient Reinforcement Learning of Undercomplete POMDPs
Sample-Efficient Reinforcement Learning of Undercomplete POMDPs
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Chi Jin;S. Kakade;A. Krishnamurthy;Qinghua Liu
中科院分区：
文献类型：
--
作者：
Chi Jin;S. Kakade;A. Krishnamurthy;Qinghua Liu
在许多强化学习应用中，部分可观察性是一个常见的挑战，它需要智能体保持记忆，推断潜在状态，并将过去的信息整合到探索中。这一挑战导致了学习一般部分可观察马尔可夫决策过程（pomdp）的许多计算和统计困难结果。这项工作表明，这些硬度障碍并不妨碍对pomdp丰富而有趣的子类进行有效的强化学习。特别地，我们提出了一种样本效率算法，om - ucb，用于偶发性有限不完全pomdp，其中观察的数量大于潜在状态的数量，并且探索对于学习至关重要，从而将我们的结果与先前的工作区分开来。OOM-UCB实现了$O(1/\epsilon^2)$的最优样本复杂度，用于寻找$\epsilon$最优策略，并且在所有其他相关量中都是多项式。作为一个有趣的特殊情况，我们还提供了具有确定性状态转移的pomdp的计算和统计效率的算法。
Partial observability is a common challenge in many reinforcement learning applications, which requires an agent to maintain memory, infer latent states, and integrate this past information into exploration. This challenge leads to a number of computational and statistical hardness results for learning general Partially Observable Markov Decision Processes (POMDPs). This work shows that these hardness barriers do not preclude efficient reinforcement learning for rich and interesting subclasses of POMDPs. In particular, we present a sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs, where the number of observations is larger than the number of latent states and where exploration is essential for learning, thus distinguishing our results from prior works. OOM-UCB achieves an optimal sample complexity of $O(1/\epsilon^2)$ for finding an $\epsilon$-optimal policy, along with being polynomial in all other relevant quantities. As an interesting special case, we also provide a computationally and statistically efficient algorithm for POMDPs with deterministic state transitions.