FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs

By Alekh Agarwal, Sham M. Kakade, Akshay Krishnamurthy, Wen Sun. 2020

267 citations recorded by the source corpus.

In order to deal with the curse of dimensionality in reinforcement learning (RL), it is common practice to make parametric assumptions where values or policies are functions of some low dimensional feature space. This work focuses on the representation learning question: how can we learn such features? Under the assumption that the underlying (unknown) dynamics correspond to a low rank transition matrix, we show how the representation learning question is related to a particular non-linear matrix decomposition problem. Structurally, we make precise connections between these low rank MDPs and latent variable models, showing how they significantly generalize prior formulations for representation learning in RL. Algorithmically, we develop FLAMBE, which engages in exploration and representation learning for provably efficient RL in low rank transition models.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistical and Nonlinear Physics

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 Statistical and Nonlinear Physics

Citations in the corpus

Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “Additionally, assumptions about low-rank structure enable a basis for provable generalization while allowing for more complexity than simpler Block MDP models (Agarwal et al., 2020; Uehara et al., 2021; Zhang et al., 2021a).”
Provable Representation Learning for Imitation with Contrastive Fourier Features (2021, background): “, [4, 39]), while to our knowledge no previous work has demonstrated a practical”
Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, methodology): “For online reinforcement learning, existing works on representation learning [Jiang et al., 2017, Agarwal et al., 2020, Modi et al., 2021, Uehara et al., 2021, Sun et al., 2019, Du et al., 2021] often assumed that the transition dynamic can be represented as a linear function of an unknown…”
Provable Rich Observation Reinforcement Learning with Combinatorial Latent States (2021, methodology): “, logarithmically) on the size of observation space? Recent work has addressed this for a rich-observation setting with a non-factored latent state space when certain supervised learning problems are tractable (Du et al., 2019; Misra et al., 2020; Agarwal et al., 2020).”
Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms (2021, background): “A recent line of work studies RL with linear function approximation (see, e.g., Jin et al., 2020; Wang et al., 2019; Cai et al., 2019; Zanette et al., 2020a;b; Agarwal et al., 2020; Neu and Pike-Burke, 2020; Sun et al., 2019) These papers assume certain completeness conditions, as well as the optima”
Representation Learning for Online and Offline RL in Low-rank MDPs (2021, methodology): “A planning procedure for a known linear MDP is also used in F LAMBE , see Section 5.1 in Agarwal et al. (2020b) for details of how to implement this procedure for a known linear MDP with polynomial computation complexity.”