Online Learning for Unknown Partially Observable MDPs

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.

References in corpus (13)

• (More) Efficient Reinforcement Learning via Posterior Sampling
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Model-based Reinforcement Learning and the Eluder Dimension
• Learning-based Control of Unknown Linear Systems with Thompson Sampling
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Exploration-Enhanced POLITEX
• Approximate information state for approximate planning and reinforcement learning in partially observed systems
• Policy Gradient in Partially Observable Environments: Approximation and Convergence
• Adaptive Approximate Policy Iteration
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints

Cited by in corpus (2)

• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning