NIPS Proceedingsβ

On Oracle-Efficient PAC RL with Rich Observations

Part of: Advances in Neural Information Processing Systems 31 (NIPS 2018)

[PDF] [BibTeX] [Supplemental] [Reviews]


Conference Event Type: Poster


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.