On Oracle-Efficient PAC RL with Rich Observations

Abstract

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.

arXiv commentappeared at NeurIPS 18; full paper including appendix; updated style file

Cited by in corpus (19)

• Information-Theoretic Considerations in Batch Reinforcement Learning
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Minimax Weight and Q-Function Learning for Off-Policy Evaluation
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• $Q$-learning with Logarithmic Regret
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning
• PAC Reinforcement Learning without Real-World Feedback
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP