We study the computational tractability of PAC reinforcement learning with
rich observations. We present new provably sample-efficient algorithms for
environments with deterministic hidden state dynamics and stochastic rich
observations. These methods operate in an oracle model of computation --
accessing policy and value function classes exclusively through standard
optimization primitives -- and therefore represent computationally efficient
alternatives to prior algorithms that require enumeration. With stochastic
hidden state dynamics, we prove that the only known sample-efficient algorithm,
OLIVE, cannot be implemented in the oracle model. We also present several
examples that illustrate fundamental challenges of tractable PAC reinforcement
learning in such general settings.

本文研究了 PAC 强化学习在富观察力下的计算复杂度，提出了基于确定性隐藏状态动态和随机富观察的可证明的样本有效算法，同时证明了在具有随机隐藏状态动态的情况下，已知样本有效算法 OLIVE 不能在 Oracle 模型中实现，通过几个示例表明了在这样一般的设置中可计算 PAC 强化学习的根本挑战。