Sublinear Regret for Learning POMDPs

2021/07/08 by Xiong Yi, Ningyuan Chen, Xiong, Yi +5
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2107.03635

openalex publication_date 2021/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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)) 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.

Related

• Online Learning for Unknown Partially Observable MDPs
• Learning in Observable POMDPs, without Computationally Intractable Oracles
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
• Lower Bounds for Learning in Revealing POMDPs
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency