mlsanityData to 7 Oct 2026

Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations

arXiv 2106.11519 ↗First posted 22 Jun 2021cs.LG cs.AI cs.SYcited by 13

Not on the map. Why?

Abstract (arXiv)

There have been many recent advances on provably efficient Reinforcement Learning (RL) in problems with rich observation spaces. However, all these works share a strong realizability assumption about the optimal value function of the true MDP. Such realizability assumptions are often too strong to hold in practice. In this work, we consider the more realistic setting of agnostic RL with rich observation spaces and a fixed class of policies Pi that may not contain any near-optimal policy. We provide an algorithm for this setting whose error is bounded in terms of the rank d of the underlying MDP. Specifically, our algorithm enjoys a sample complexity bound of widetildeOleft((H4d K3d log |Pi|)/ε2right) where H is the length of episodes, K is the number of actions and ε>0 is the desired sub-optimality. We also provide a nearly matching lower bound for this agnostic setting that shows that the exponential dependence on rank is unavoidable, without further assumptions.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 32 of its 63 references that are in the map. First posted on arXiv 22 Jun 2021.

Builds on

32 of 63 references.

References · 32

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  7. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  8. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  10. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  11. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  12. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
20 more
  1. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  2. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  3. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  4. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  5. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  6. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  7. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  8. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  9. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  10. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  11. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  12. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  13. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  14. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  15. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  16. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  17. 2020Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimationcited by 25
  18. 2013Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributionscited by 18
  19. 2021An L2 Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximationcited by 13
  20. 2013Regret Bounds for Reinforcement Learning with Policy Advicecited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 4; 2024: 1; 2025: 1; 2026: 2.

13 papers.

Sort:

By area:

  1. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  3. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  4. 2022On the Complexity of Adversarial Decision Makingcited by 32
  5. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
  6. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  7. 2023Provably Efficient CVaR RL in Low-rank MDPscited by 6
  8. 2023Parameterized Projected Bellman Operatorcited by 3
  9. 2023Eigensubspace of Temporal-Difference Dynamics and How It Improves Value Approximation in Reinforcement Learningcited by 2
  10. 2024Provable Interactive Learning with Hindsight Instruction Feedbackcited by 1
  11. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learningcited by 1
  12. 2026PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structurecited by 0
1 more
  1. 2026The Sample Complexity of Policy Learning with Mu-Resetscited by 0