Provably efficient RL with Rich Observations via Latent State Decoding

By Simon Shaolei Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dud'ik, J. Langford. 2019

254 citations recorded by the source corpus.

We study the exploration problem in episodic MDPs with rich observations generated from a small number of latent states. Under certain identifiability assumptions, we demonstrate how to estimate a mapping from the observations to latent states inductively through a sequence of regression and clustering steps—where previously decoded latent states provide labels for later regression problems—and use it to construct good exploration policies. We provide finite-sample guarantees on the quality of the learned state decoding function and exploration policies, and complement our theory with an empirical evaluation on a class of hard exploration problems. Our method exponentially improves over Q-learning with naive exploration, even when Q-learning has cheating access to latent states.

Subfields: Artificial Intelligence

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

Citations in the corpus

Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “In recent work, Zhang et al. (2020); Hansen-Estruch, Zhang, Nair, Yin, and Levine (2022); Ashcraft, Stoler, Ewulum, and Agarwala (2022) connect invariant causal prediction to model-irrelevance state abstractions to learn invariant representations in the Block MDP setting (Du et al., 2019b).”
Block Contextual MDPs for Continual Learning (2021, background): “This additional relaxation of the original CMDP deﬁnition as a form of Block MDP (Du et al., 2019) was previously introduced in Sodhani et al. (2021b) for the multi-task setting where the agent focuses on a subset of the whole space for a speciﬁc task, which we again present here for clarity: Deﬁnit”
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle (2019, background): “Finally, a recent series of work introduced contextual decision processes (CDPs) [22, 17, 9, 32, 11] and developed algorithms with polynomial sample complexity guarantees.”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “…have been proposed using linear function approximators (Abbasi-Yadkori et al., 2019a,b; Jin et al., 2019; Yang and Wang, 2019a; Zanette et al., 2019; Du et al., 2019b; Cai et al., 2019; Wang et al., 2019), as well as nonlinear ones (Wen and Van Roy, 2017; Jiang et al., 2017; Dann et al., 2018; Du…”
Can Foundation Models Perform Zero-Shot Task Specification For Robot Manipulation? (2022, methodology): “Informally, this setting has been widely studied and was characterized more formally by Du et al. (2019) as “Block MDPs”.”
Learning Markov State Abstractions for Deep Reinforcement Learning (2021, background): “Block MDPs conveniently avoid potential issues arising from partial observability by assuming that each observation uniquely identiﬁes the unobserved state that generated it.”
Preference-based Reinforcement Learning with Finite-Time Guarantees (2020, methodology): “[14,23] considers computing a policy cover by exploring the state space using a similar synthetic function as PEPS.”
Multi-Task Reinforcement Learning with Context-based Representations (2021, methodology): “These natural language descriptions have been utilized in single-task RL setups like goal-oriented RL (Chevalier-Boisvert et al., 2019; Luketina et al., 2019; Jiang et al., 2019).”
On Reward-Free Reinforcement Learning with Linear Function Approximation (2020, background): “…for the tabular case, while the reward-free setting is ﬁrst formalized in Jin et al. [2020], algorithms in earlier works also guarantee to collect a polynomial-size dataset with coverage guarantees [Brafman and Tennenholtz, 2002, Hazan et al., 2018, Du et al., 2019a, Misra et al., 2019].”
Learning Domain Invariant Representations in Goal-conditioned Block MDPs (2021, background): “Most importantly, X E = ∪e∈EX e satisfies the disjoint property [14], i.”
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? (2019, methodology): “Later work gave computationally efﬁcient algorithms for certain special cases (Dann et al., 2018; Du et al., 2019a; Yang & Wang, 2019b; Jin et al., 2019).”
FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, methodology): “The natural representation learning goal is to recover the latent states, and Du et al. (2019b); Misra et al. (2019) show that this can be done, in concert with exploration, in a statistically and computationally efﬁcient manner.”
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).”
Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, background): “Several theoretical works [Du et al., 2019, Misra et al., 2020, Foster et al., 2020b] have studied the Block MDP where the dynamics are governed by a discrete latent state space and proposed algorithms based on decoding the latent state space from the observations.”
Provable Rich Observation Reinforcement Learning with Combinatorial Latent States (2021, methodology): “We use the result of Du et al. (2019) stated in Lemma 30 (setting ε set to d% using Corollary 9) to write: |Pπ̂(E)− Pπ̄(E)| = |Pπ̂(E)− PϕR(E)| ≤ 2d%H (34) Let ϕ : S◦ → A be any policy on real state space and let ϕ̂ : Ŝ → A be the induced policy on learned state space given by ϕ̂(ŝ) = ϕ ◦ θ(ŝ) =…”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, background): “…sample complexity does not depend on |S| [Li et al., 2011, Wen and Van Roy, 2017, Krishnamurthy et al., 2016, Jiang et al., 2017, Dann et al., 2018, Du et al., 2019b, Feng et al., 2020, Du et al., 2019c, Zhong et al., 2019, Yang and Wang, 2019, Jin et al., 2019, Du et al., 2019a, Roy and Dong,…”
Reward-Free Exploration for Reinforcement Learning (2020, methodology): “Second, one can extract the exploration component of recent results for RL with function approximation [Du et al., 2019, Misra et al., 2019].”
Invariant Causal Prediction for Block MDPs (2020, background): “Block MDPs (Du et al., 2019) are described by a tuple hS,A,X , p, q, Ri with a finite, unobservable state space S , finite action space A, and possibly infinite, but observable space X . p denotes the latent transition distribution p(s0|s, a) for s, s0 2 S, a 2 A, q is the (possibly stochastic)…”