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.

该论文介绍了一种基于近似多项式时间算法的部分可观测马可夫决策过程无预言学习算法，该算法不是基于传统的探索 - 利用原则，而是采用几何拓扑中的重心跨度技术构建策略套接，并且通过对状态分布和观测分布的假设来保证合理性。