Model-free Representation Learning and Exploration in Low-rank MDPs

Abstract

The low rank MDP has emerged as an important model for studying representation learning and exploration in reinforcement learning. With a known representation, several model-free exploration strategies exist. In contrast, all algorithms for the unknown representation setting are model-based, thereby requiring the ability to model the full dynamics. In this work, we present the first model-free representation learning algorithms for low rank MDPs. The key algorithmic contribution is a new minimax representation learning objective, for which we provide variants with differing tradeoffs in their statistical and computational properties. We interleave this representation learning step with an exploration strategy to cover the state space in a reward-free manner. The resulting algorithms are provably sample efficient and can accommodate general function approximation to scale to complex environments.

Changelog v2: Significant reorganization of the paper, added an improved analysis of elliptic planner and updated discussion wrt follow-up work

References in corpus (15)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Learning Invariant Representations for Reinforcement Learning without Reconstruction
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Model-based Reinforcement Learning and the Eluder Dimension
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Reward-Free Exploration for Reinforcement Learning
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL
• The Elliptical Potential Lemma Revisited
• Online Sparse Reinforcement Learning
• Online Model Selection for Reinforcement Learning with Function Approximation

Cited by in corpus (8)

• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
• The Information Geometry of Unsupervised Reinforcement Learning
• A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control