Data to 14 Oct 2026

On Oracle-Efficient PAC RL with Rich Observations

arXiv 1803.00606 ↗First posted 1 Mar 2018cs.LG stat.MLcited by 71

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 71 papers in the map (data through 14 Oct 2026). First posted on arXiv 1 Mar 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 18; 2022: 16; 2023: 13; 2024: 16; 2025: 3; 2026: 5.

71 papers.

Sort:

By area:

2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 161
2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 70
2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45

38 more

2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 31
2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 18
2022Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learningcited by 18
2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 16
2021Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learningcited by 15
2021Reinforcement Learning in Reward-Mixing MDPscited by 15
2025Qsharp: Provably Optimal Distributional RL for LLM Post-Trainingcited by 15
2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 10
2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 9
2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
2022Interaction-Grounded Learning with Action-inclusive Feedbackcited by 7
2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
2025Replicable Reinforcement Learning with Linear Function Approximationcited by 7
2021Explore and Control with Adversarial Surprisecited by 6
2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 6
2024Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rankcited by 6

50 most cited of 71 All 71 (JSON)