On Oracle-Efficient PAC RL with Rich Observations

By Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, J. Langford, Robert E. Schapire. 2018

107 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “…answers to the above problem in recent development of PAC exploration in rich-observation problems (Krishnamurthy et al., 2016; Jiang et al., 2017; Dann et al., 2018), where a general low-rank condition (a.k.a. Bellman rank (Jiang et al., 2017)) has been identiﬁed that enables sample-efﬁcient…”
Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms (2021, background): “We comment that OLIVE is computationally inefficient in general because implementing the optimistic planning part requires solving an NP-hard problem in the worst case (Dann et al., 2018).”
On Value Functions and the Agent-Environment Boundary (2019, background): “It automatically implies Q ∈ F (for finite F ) hence is stronger than realizability, but replacing this assumption with realizability can cause FQI to diverge [Van Roy, 1994, Gordon, 1995, Tsitsiklis and Van Roy, 1997] or have exponential sample complexity [Dann et al., 2018].”
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes (2019, background): “We note that the property of LBPE(θ) = 0 for all θ ∈ Θ is related to notions such as policy completeness from prior work [Dann et al., 2018], further motivating this error as a relevant measure of the expressivity of a policy class.”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, methodology): “To appropriately measure the sample complexity (see Jiang and Agarwal [2018]), we consider a normalized notion: we are interested in the number of episodes it takes to provably discover a policy whose value is ε near to that of the optimal value, where the value is measured by the normalized…”
Representation Learning for Online and Offline RL in Low-rank MDPs (2021, methodology): “These works require additional assumptions such as deterministic transitions (Dann et al., 2018), reachability (Misra et al., 2020; Du et al., 2019a), strong Bellman closure (Foster et al., 2020), and strong unsupervised learning oracles (Feng et al., 2020).”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “, 2019), as well as nonlinear ones (Wen and Van Roy, 2017; Jiang et al., 2017; Dann et al., 2018; Du et al., 2019b; Dong et al., 2019; Du et al., 2019a).”