mlsanityData to 7 Oct 2026

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

arXiv 2111.11485 ↗First posted 22 Nov 2021stat.ML cs.AI cs.LGcited by 24

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). Builds on 43 of its 71 references that are in the map. First posted on arXiv 22 Nov 2021.

Builds on

43 of 71 references.

References · 43

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  2. 2013Auto-Encoding Variational Bayescited by 3,980
  3. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  4. 2016Variational Inference: A Review for Statisticianscited by 1,466
  5. 2018Learning Latent Dynamics for Planning from Pixelscited by 1,221
  6. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  7. 2018Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Modelscited by 748
  8. 2020MOPO: Model-based Offline Policy Optimizationcited by 630
  9. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  10. 2018Is Q-learning Provably Efficient?cited by 485
  11. 2015Embed to Control: A Locally Linear Latent Dynamics Model for Control from Raw Imagescited by 266
  12. 2013Learning to Optimize Via Posterior Samplingcited by 253
31 more
  1. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  2. 2018Model-Ensemble Trust-Region Policy Optimizationcited by 214
  3. 2019DeepMDP: Learning Continuous Latent Space Models for Representation Learningcited by 204
  4. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  5. 2017Bridging the Gap Between Value and Policy Based Reinforcement Learningcited by 178
  6. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  7. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  8. 2019Benchmarking Model-Based Reinforcement Learningcited by 158
  9. 2018Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guaranteescited by 138
  10. 2019Scalable methods for computing state similarity in deterministic Markov Decision Processescited by 133
  11. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  12. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  13. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  14. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  15. 2020Naive Exploration is Optimal for Online LQRcited by 111
  16. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
  17. 2018Model-Based Reinforcement Learning via Meta-Policy Optimizationcited by 99
  18. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  19. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  20. 2017Convergence of Langevin MCMC in KL-divergencecited by 86
  21. 2018The Laplacian in RL: Learning Representations with Efficient Approximationscited by 83
  22. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  23. 2020Active Learning for Nonlinear System Identification with Guaranteescited by 78
  24. 2016Deep Successor Reinforcement Learningcited by 72
  25. 2019Learning Linear-Quadratic Regulators Efficiently with only √T Regretcited by 67
  26. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  27. 2014Scalable Kernel Methods via Doubly Stochastic Gradientscited by 36
  28. 2021Provable Representation Learning for Imitation with Contrastive Fourier Featurescited by 34
  29. 2018State Aggregation Learning from Markov Transition Datacited by 20
  30. 2018Spectral State Compression of Markov Processescited by 18
  31. 2021Towards Automatic Evaluation of Dialog Systems: A Model-Free Off-Policy Evaluation Approachcited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 3; 2024: 6; 2025: 3; 2026: 4.

24 papers.

Sort:

By area:

  1. 2024RLHF from Heterogeneous Feedback via Personalization and Preference Aggregationcited by 71
  2. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  3. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
  4. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  5. 2025Towards General-Purpose Model-Free Reinforcement Learningcited by 40
  6. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  7. 2022Spectral Decomposition Representation for Reinforcement Learningcited by 35
  8. 2024Diffusion Spectral Representation for Reinforcement Learningcited by 15
  9. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
  10. 2022Latent Variable Representation for Reinforcement Learningcited by 14
  11. 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
  12. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
12 more
  1. 2024No-Regret Reinforcement Learning in Smooth MDPscited by 6
  2. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  3. 2024Primal-Dual Spectral Representation for Off-policy Evaluationcited by 4
  4. 2023Stochastic Nonlinear Control via Finite-dimensional Spectral Dynamic Embeddingcited by 3
  5. 2025Spectral Representation-based Reinforcement Learningcited by 3
  6. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  7. 2025AmorLIP: Efficient Language-Image Pretraining via Amortizationcited by 2
  8. 2024Efficient Duple Perturbation Robustness in Low-rank MDPscited by 0
  9. 2026Spectral Ghost in Representation Learning: from Component Analysis to Self-Supervised Learningcited by 0
  10. 2026Unifying Model-Free Efficiency and Model-Based Representations via Latent Dynamicscited by 0
  11. 2026Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPscited by 0
  12. 2026Learning Expressive and Compositional Motion Representation via Spectral Skillscited by 0