A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning

Abstract

Representation learning lies at the heart of the empirical success of deep learning for dealing with the curse of dimensionality. However, the power of representation learning has not been fully exploited yet in reinforcement learning (RL), due to i), the trade-off between expressiveness and tractability; and ii), the coupling between exploration and representation learning. In this paper, we first reveal the fact that under some noise assumption in the stochastic control model, we can obtain the linear spectral feature of its corresponding Markov transition operator in closed-form for free. Based on this observation, we propose Spectral Dynamics Embedding (SPEDE), which breaks the trade-off and completes optimistic exploration for representation learning by exploiting the structure of the noise. We provide rigorous theoretical analysis of SPEDE, and demonstrate the practical superior performance over the existing state-of-the-art empirical algorithms on several benchmarks.

UAI 2022. The first two authors contribute equally

References in corpus (12)

• MOPO: Model-based Offline Policy Optimization
• Benchmarking Model-Based Reinforcement Learning
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
• On Lower Bounds for Regret in 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
• Active Learning for Nonlinear System Identification with Guarantees
• Information Theoretic Regret Bounds for Online Nonlinear Control
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Provable Representation Learning for Imitation with Contrastive Fourier Features