Timezone: »

FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
Alekh Agarwal · Sham Kakade · Akshay Krishnamurthy · Wen Sun

Tue Dec 08 06:30 AM -- 06:45 AM (PST) @ Orals & Spotlights: Reinforcement Learning

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, such as block MDPs, 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. On a technical level, our analysis eliminates reachability assumptions that appear in prior results on the simpler block MDP model and may be of independent interest.

Author Information

Alekh Agarwal (Microsoft Research)
Sham Kakade (University of Washington & Microsoft Research)
Akshay Krishnamurthy (Microsoft)
Wen Sun (Cornell University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors