Sublinear regret for learning POMDPs. Issue 9 (15th July 2022)

• Record Type: Journal Article
• Authors: Xiong, Yi; Chen, Ningyuan; Gao, Xuefeng; Zhou, Xiang
• Is Part Of: Production and operations management. Volume 31:Issue 9(2022)
• Page Start: 3491
• Page End: 3504
• Publication Date: 2022-07-15
• Subjects: exploration–exploitation -- online learning -- partially observable MDP -- spectral estimator; Production management -- Periodicals; 658.505
• DOI: 10.1111/poms.13778
• Languages: English
• ISSNs: 1059-1478

Abstract

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 of O ( T 2 / 3 log T ) $O(T^{2/3}\sqrt {\log T})$ for the proposed learning algorithm where T is 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.