Learning in Observable POMDPs, without Computationally Intractable Oracles
This addresses a foundational issue in reinforcement learning theory by enabling more practical and efficient learning in POMDPs, though it is incremental as it builds on existing observability concepts.
The paper tackles the problem of learning near-optimal policies in Partially Observable Markov Decision Processes (POMDPs) without relying on computationally intractable oracles, by developing the first oracle-free algorithm that runs in quasipolynomial time under observability assumptions.
Much of reinforcement learning theory is built on top of oracles that are computationally hard to implement. Specifically for learning near-optimal policies in Partially Observable Markov Decision Processes (POMDPs), existing algorithms either need to make strong assumptions about the model dynamics (e.g. deterministic transitions) or assume access to an oracle for solving a hard optimistic planning or estimation problem as a subroutine. In this work we develop the first oracle-free learning algorithm for POMDPs under reasonable assumptions. Specifically, we give a quasipolynomial-time end-to-end algorithm for learning in "observable" POMDPs, where observability is the assumption that well-separated distributions over states induce well-separated distributions over observations. Our techniques circumvent the more traditional approach of using the principle of optimism under uncertainty to promote exploration, and instead give a novel application of barycentric spanners to constructing policy covers.