Research map / Reinforcement learning / MDPs and planning
Provably Efficient CVaR RL in Low-rank MDPs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ELA/ELLA, an MLE-based UCB bonus algorithm with a discretized LSVI planning oracle for static CVaR RL in low-rank MDPs, giving polynomial sample and computational complexity.
Problem
Risk-sensitive RL maximizing static CVaR with a fixed risk tolerance in low-rank MDPs with nonlinear function approximation and unknown representations, where prior CVaR RL theory was limited to tabular MDPs.
Approach
Augments the state with the remaining budget, learns low-rank transition embeddings via MLE, adds an elliptical UCB exploration bonus to value iteration, and makes planning tractable by discretizing rewards and budgets and running LSVI-UCB with a CVaR objective over a grid of initial budgets.
Key results
- ELA achieves sample complexity Õ(H^7 A^2 d^4 / (τ^2 ε^2)) for ε-optimal CVaR in low-rank MDPs, with regret Õ(τ^{-1} H^3 A d^2 √K).
- ELLA adds a discretized CVaR-LSVI planner, keeping the MLE oracle calls at the same order and the remaining computation polynomial in H, A, d, 1/υ, 1/τ, 1/ε.
- The sample complexity matches the Rep-UCB dependencies on A and d but has a worse H^7 dependence versus Rep-UCB's H^5.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add CVaR-LSVI with discretized rewards as the planning oracle | ELA · Low-rank MDPs with continuous rewards | computation cost | Helped |
| Round rewards up to the discretization grid | ELLA · Low-rank MDPs with continuous rewards | CVaR approximation error: 0\leq \mathsf{CVaR}_{\tau}(\overline{R}(\pi,i\upsilon))-\mathsf{CVaR}_{\tau}(R(\overline{\pi},i\upsilon))\leq \frac{H\up | Hurt |
Surprising findings
- The paper's stated computational-cost exponents differ between the informal theorem (H^19 ... ε^6) and the continuous-reward theorem (H^29 ... τ^16 ε^16), suggesting inconsistency in the stated bounds.
Limitations
- Sample complexity has a worse horizon dependence (H^7) than Rep-UCB and a loose dependence on τ compared with the Ω(1/(τε^2)) lower bound.
- Requires a finite model class with realizability and an MLE oracle; the planning cost has very large polynomial exponents.
- Discretization of rewards introduces approximation error controlled only by choosing a fine precision υ.
Experimental setup
Metrics: sample complexity regret
Baselines: Rep-UCB CVaR-UCBVI
Builds on: Rep-UCB Flambe CVaR-UCBVI low-rank MDP linear MDP
Closest papers by meaning
- Risk-Sensitive Reward-Free Reinforcement Learning with CVaR (ICML 2024 · similarity 0.91)
- Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback (ICLR 2024 · similarity 0.91)
- A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents (ICML 2025 · similarity 0.91)
- Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation (ICML 2024 · similarity 0.88)
- Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning (ICML 2024 · similarity 0.88)
- Beyond CVaR: Leveraging Static Spectral Risk Measures for Enhanced Decision-Making in Distributional Reinforcement Learning (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.