mlsanityData to 7 Oct 2026

Provably Efficient CVaR RL in Low-rank MDPs

arXiv 2311.11965 ↗First posted 20 Nov 2023cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

We study risk-sensitive Reinforcement Learning (RL), where we aim to maximize the Conditional Value at Risk (CVaR) with a fixed risk tolerance τ. Prior theoretical work studying risk-sensitive RL focuses on the tabular Markov Decision Processes (MDPs) setting. To extend CVaR RL to settings where state space is large, function approximation must be deployed. We study CVaR RL in low-rank MDPs with nonlinear function approximation. Low-rank MDPs assume the underlying transition kernel admits a low-rank decomposition, but unlike prior linear models, low-rank MDPs do not assume the feature or state-action representation is known. We propose a novel Upper Confidence Bound (UCB) bonus-driven algorithm to carefully balance the interplay between exploration, exploitation, and representation learning in CVaR RL. We prove that our algorithm achieves a sample complexity of tildeOleft(fracH7 A2 d4τ2 ε2right) to yield an ε-optimal CVaR, where H is the length of each episode, A is the capacity of action space, and d is the dimension of representations. Computational-wise, we design a novel discretized Least-Squares Value Iteration (LSVI) algorithm for the CVaR objective as the planning oracle and show that we can find the near-optimal policy in a polynomial running time with a Maximum Likelihood Estimation oracle. To our knowledge, this is the first provably efficient CVaR RL algorithm in low-rank MDPs.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 26 of its 42 references that are in the map. First posted on arXiv 20 Nov 2023.

Builds on

26 of 42 references.

References · 26

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2020Learning Invariant Representations for Reinforcement Learning without Reconstructioncited by 424
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  5. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  6. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  7. 2021Multi-Task Reinforcement Learning with Context-based Representationscited by 169
  8. 2015Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approachcited by 162
  9. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  10. 2020Invariant Causal Prediction for Block MDPscited by 104
  11. 2014Optimizing the CVaR via Samplingcited by 98
  12. 2014Algorithms for CVaR Optimization in MDPscited by 98
14 more
  1. 2019Safe Reinforcement Learning on Autonomous Vehiclescited by 48
  2. 2020Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimizationcited by 34
  3. 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
  4. 2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
  5. 2022Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 26
  6. 2021Block Contextual MDPs for Continual Learningcited by 25
  7. 2022Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Pathcited by 21
  8. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  9. 2019Learning Robust Options by Conditional Value at Risk Optimizationcited by 16
  10. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  11. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  12. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 13
  13. 2017Approximate Value Iteration for Risk-aware Markov Decision Processescited by 9
  14. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4

Built on by

Cited by year (2026 to 7 Oct)

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

6 papers.

  1. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 15
  2. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
  3. 2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Modelcited by 4
  4. 2024Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximationcited by 3
  5. 2026Constrained Meta Reinforcement Learning with Provable Test-Time Safetycited by 1
  6. 2025Constrained Language Model Policy Optimization via Risk-aware Stepwise Alignmentcited by 0