Sublinear regret for learning POMDPs
Yi Xiong, Ningyuan Chen, Xuefeng Gao, Xiang Zhou
Production and Operations Management · 2022 · Volume 31 · Issue 9
Abstract
We study the model-based undiscounted reinforcement learning for partially observable Markov decision processes (POMDPs). The oracle we consider is the optimal policy of the POMDP with a known environment in terms of the average reward over an infinite horizon. We propose a learning algorithm for this problem, building on spectral method-of-moments estimations for hidden Markov models, the belief error control in POMDPs and upper confidence bound methods for online learning. We establish a regret bound ofO(T2/3logT)$O(T^{2/3}\sqrt {\log T})$for the proposed learning algorithm whereTis the learning horizon. This is, to the best of our knowledge, the first algorithm achieving sublinear regret with respect to our oracle for learning general POMDPs.
Keywords
exploration–exploitation, online learning, partially observable MDP, spectral estimator
Enable JavaScript for citation tools and additional paper interactions.