mlsanityData to 13 Oct 2026

Primal-Dual Spectral Representation for Off-policy Evaluation

arXiv 2410.17538 ↗First posted 23 Oct 2024cs.LG cs.AI math.OCcited by 4

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Off-policy evaluation (OPE) is one of the most fundamental problems in reinforcement learning (RL) to estimate the expected long-term payoff of a given target policy with only experiences from another behavior policy that is potentially unknown. The distribution correction estimation (DICE) family of estimators have advanced the state of the art in OPE by breaking the curse of horizon. However, the major bottleneck of applying DICE estimators lies in the difficulty of solving the saddle-point optimization involved, especially with neural network implementations. In this paper, we tackle this challenge by establishing a linear representation of value function and stationary distribution correction ratio, i.e., primal and dual variables in the DICE framework, using the spectral decomposition of the transition operator. Such primal-dual representation not only bypasses the non-convex non-concave optimization in vanilla DICE, therefore enabling an computational efficient algorithm, but also paves the way for more efficient utilization of historical data. We highlight that our algorithm, SpectralDICE, is the first to leverage the linear representation of primal-dual variables that is both computation and sample efficient, the performance of which is supported by a rigorous theoretical sample complexity guarantee and a thorough empirical evaluation on various benchmarks.

Key facts. Cited by 4 papers in the map (data through 13 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 47 of its 68 references that are in the map. First posted on arXiv 23 Oct 2024.

Builds on

47 of 68 references.

References · 47

  1. 2018QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulationcited by 731
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 515
  3. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
  4. 2021Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Losscited by 312
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  7. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 285
  8. 2019Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialogcited by 284
  9. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  10. 2019Batch Policy Learning under Constraintscited by 243
  11. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  12. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
35 more
  1. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  2. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 188
  3. 2018Top-K Off-Policy Correction for a REINFORCE Recommender Systemcited by 181
  4. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 161
  5. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  6. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  7. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  8. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  9. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  10. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 118
  11. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
  12. 2021Benchmarks for Deep Off-Policy Evaluationcited by 89
  13. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  14. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 70
  15. 2020CoinDICE: Off-Policy Confidence Interval Estimationcited by 64
  16. 2018Evaluating Reinforcement Learning Algorithms in Observational Health Settingscited by 60
  17. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  18. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
  19. 2022Spectral Decomposition Representation for Reinforcement Learningcited by 35
  20. 2018Importance Sampling Policy Evaluation with an Estimated Behavior Policycited by 34
  21. 2021Autoregressive Dynamics Models for Offline Policy Evaluation and Optimizationcited by 33
  22. 2020Offline Policy Selection under Uncertaintycited by 31
  23. 2021Offline Reinforcement Learning for Autonomous Driving with Safety and Exploration Enhancementcited by 29
  24. 2020Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluationcited by 28
  25. 2022Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learningcited by 26
  26. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  27. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 18
  28. 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
  29. 2021Towards Automatic Evaluation of Dialog Systems: A Model-Free Off-Policy Evaluation Approachcited by 16
  30. 2024Diffusion Spectral Representation for Reinforcement Learningcited by 15
  31. 2022Latent Variable Representation for Reinforcement Learningcited by 14
  32. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  33. 2024Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximationcited by 10
  34. 2018Composable Action-Conditioned Predictors: Flexible Off-Policy Learning for Robot Navigationcited by 9
  35. 2023Marginalized Importance Sampling for Off-Environment Policy Evaluationcited by 5

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Spectral Representation-based Reinforcement Learningcited by 3
  2. 2025Outcome-Aware Spectral Feature Learning for Instrumental Variable Regressioncited by 2
  3. 2025Toward Scalable and Valid Conditional Independence Testing with Spectral Representationscited by 1
  4. 2026Spectral Ghost in Representation Learning: from Component Analysis to Self-Supervised Learningcited by 0