# Provably Efficient CVaR RL in Low-rank MDPs

arXiv: https://arxiv.org/abs/2311.11965 · HTML: https://mlsanity.com/paper/2311.11965/

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Multi-Task Reinforcement Learning with Context-based Representations](https://mlsanity.com/paper/2102.06177/) (2021)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Invariant Causal Prediction for Block MDPs](https://mlsanity.com/paper/2003.06016/) (2020)
- [Optimizing the CVaR via Sampling](https://mlsanity.com/paper/1404.3862/) (2014)
- [Algorithms for CVaR Optimization in MDPs](https://mlsanity.com/paper/1406.3339/) (2014)
- [Safe Reinforcement Learning on Autonomous Vehicles](https://mlsanity.com/paper/1910.00399/) (2019)
- [Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimization](https://mlsanity.com/paper/2003.01303/) (2020)
- [Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR](https://mlsanity.com/paper/2302.03201/) (2023)
- [Provable RL with Exogenous Distractors via Multistep Inverse Dynamics](https://mlsanity.com/paper/2110.08847/) (2021)
- [Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2210.05650/) (2022)
- [Block Contextual MDPs for Continual Learning](https://mlsanity.com/paper/2110.06972/) (2021)
- [Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Path](https://mlsanity.com/paper/2206.02678/) (2022)
- [Reinforcement Learning in Low-Rank MDPs with Density Features](https://mlsanity.com/paper/2302.02252/) (2023)
- [Learning Robust Options by Conditional Value at Risk Optimization](https://mlsanity.com/paper/1905.09191/) (2019)
- [Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs](https://mlsanity.com/paper/2303.10859/) (2023)
- [Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback](https://mlsanity.com/paper/2307.02842/) (2023)
- [Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations](https://mlsanity.com/paper/2106.11519/) (2021)
- [Approximate Value Iteration for Risk-aware Markov Decision Processes](https://mlsanity.com/paper/1701.01290/) (2017)
- [Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback](https://mlsanity.com/paper/2311.07876/) (2023)

## Built on by (most cited first, 6 of 6)

- [A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2403.06323/) (2024)
- [Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning](https://mlsanity.com/paper/2407.07631/) (2024)
- [Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2503.08934/) (2025)
- [Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2402.18159/) (2024)
- [Constrained Meta Reinforcement Learning with Provable Test-Time Safety](https://mlsanity.com/paper/2601.21845/) (2026)
- [Constrained Language Model Policy Optimization via Risk-aware Stepwise Alignment](https://mlsanity.com/paper/2512.24263/) (2025)

## 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.