FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs

Abstract

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.

arXiv commentNew algorithm and analysis to remove the reachability assumption

References in corpus (22)

• #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Generalization and Equilibrium in Generative Adversarial Nets (GANs)
• From $\epsilon$-entropy to KL-entropy: Analysis of minimum information complexity density estimation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Implicit Reparameterization Gradients
• The Benefit of Multitask Representation Learning
• Provably Efficient Maximum Entropy Exploration
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably efficient RL with Rich Observations via Latent State Decoding
• The Sample-Complexity of General Reinforcement Learning
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Reward-Free Exploration for Reinforcement Learning
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• Contrastive estimation reveals topic posterior information to linear models
• Provably Efficient Exploration in Policy Optimization
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank

Cited by in corpus (29)

• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Structure in Deep Reinforcement Learning: A Survey and Open Problems
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Nonstationary Reinforcement Learning with Linear Function Approximation
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Robust Policy Gradient against Strong Data Corruption
• Online learning in MDPs with linear function approximation and bandit feedback
• Provable Representation Learning for Imitation with Contrastive Fourier Features
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Representation Learning for Online and Offline RL in Low-rank MDPs
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Minimax Rates for Conditional Density Estimation via Empirical Entropy
• DeepAveragers: Offline Reinforcement Learning by Solving Derived Non-Parametric MDPs
• Online Sparse Reinforcement Learning
• Interactive Learning from Activity Description
• Randomized Value Functions via Posterior State-Abstraction Sampling
• A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• PerSim: Data-Efficient Offline Reinforcement Learning with Heterogeneous Agents via Personalized Simulators
• The Information Geometry of Unsupervised Reinforcement Learning
• Logistic Q-Learning
• Provable RL with Exogenous Distractors via Multistep Inverse Dynamics
• On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control
• Sparsity in Partially Controllable Linear Systems