Research map / Reinforcement learning / MDPs and planning
Risk-Sensitive Reward-Free Reinforcement Learning with CVaR
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 a CVaR-based risk-sensitive reward-free RL framework with an exploration algorithm (CVaR-RF-UCRL), near-optimal sample complexity bounds, and CVaR value-iteration planners for tabular MDPs.
Problem
Efficient exploration for risk-sensitive RL (CVaR objective) in the reward-free setting, where a single exploration phase must support planning for any reward function.
Approach
Extends reward-free RL (Jin et al., 2020) to CVaR objectives by using an augmented state (s, b) with budget tracking, a UCB-style greedy exploration with a τ-dependent stopping rule, and planning via CVaR value iteration (with reward discretization for tractability).
Key results
- CVaR-RF-UCRL is (ϵ, δ)-PAC with sample complexity Õ(S²AH⁴/(ϵ²τ²)).
- A lower bound Ω(S²AH²/(τϵ²)) is proved for any CVaR-RF exploration algorithm, matching the upper bound up to H² and 1/τ factors.
- In grid-world experiments with τ=0.05 and ϵ=0.1, the CVaR gap between true and empirical transitions is 0.05 (4.308 vs. 4.258), below the ϵ threshold.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the empirical transition probabilities from CVaR-RF-UCRL instead of the true transition probabilities | CVaR-VI-DISC · Reward setup 1, τ=0.05 | CVaR: 4.308 -> 4.258 (Error 0.05) | No clear effect |
| Use the empirical transition probabilities from CVaR-RF-UCRL instead of the true transition probabilities | CVaR-VI-DISC · Reward setup 1, τ=0.95 | CVaR: 4.960 -> 4.954 (Error 0.006) | No clear effect |
| Use the empirical transition probabilities from CVaR-RF-UCRL instead of the true transition probabilities | CVaR-VI-DISC · Reward setup 2, τ=0.05 | CVaR: 1.852 -> 1.829 (Error 0.023) | No clear effect |
| Use the empirical transition probabilities from CVaR-RF-UCRL instead of the true transition probabilities | CVaR-VI-DISC · Reward setup 2, τ=0.95 | CVaR: 1.993 -> 1.990 (Error 0.003) | No clear effect |
Limitations
- Upper bound is loose by factors H² and 1/τ relative to the lower bound, so not minimax-optimal in H and τ.
- Planning assumes an approximate CVaR solver error bound; the analysis is for tabular MDPs only.
- Experiments are limited to a single small grid-world with simple reward setups.
Experimental setup
Datasets: synthetic grid-world MDP (21x21 states, 4 actions)
Benchmarks: 21x21 grid-world with two reward setups
Metrics: CVaR value under true vs. empirical transitions absolute CVaR error state visitation counts
Builds on: reward-free RL (Jin et al., 2020) Kaufmann et al., 2021 UCRL-based reward-free exploration CVaR value iteration (Wang et al., 2023) augmented MDP for CVaR (Bäuerle & Ott, 2011)
Closest papers by meaning
- A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents (ICML 2025 · similarity 0.91)
- Provably Efficient CVaR RL in Low-rank MDPs (ICLR 2024 · similarity 0.91)
- Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback (ICLR 2024 · similarity 0.91)
- Balance Reward and Safety Optimization for Safe Reinforcement Learning: A Perspective of Gradient Manipulation (AAAI 2024 · similarity 0.89)
- Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning (ICML 2024 · similarity 0.89)
- Beyond Optimism: Exploration With Partially Observable Rewards (NeurIPS 2024 · similarity 0.88)
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.