Online Learning for Unknown Partially Observable MDPs

2021/02/25 by Mehdi Jafarnia-Jahromi, Jafarnia-Jahromi, Mehdi, Rahul Jain +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2102.12661

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

Abstract

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.

Citations

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Model-based Reinforcement Learning and the Eluder Dimension
• (More) Efficient Reinforcement Learning via Posterior Sampling
• Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling

Related

• Sublinear Regret for Learning POMDPs
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
• Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Need
• Posterior Sampling-based Online Learning for Episodic POMDPs
• Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Information