# Q-learning for Quantile MDPs: A Decomposition, Performance, and Convergence Analysis

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 19 of its 52 references that are in the map.
- First posted on arXiv 31 Oct 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Distributional Reinforcement Learning with Quantile Regression](https://mlsanity.com/paper/1710.10044/) (2017)
- [Implicit Quantile Networks for Distributional Reinforcement Learning](https://mlsanity.com/paper/1806.06923/) (2018)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [Risk-sensitive Reinforcement Learning](https://mlsanity.com/paper/1311.2097/) (2013)
- [Algorithms for CVaR Optimization in MDPs](https://mlsanity.com/paper/1406.3339/) (2014)
- [Being Optimistic to Be Conservative: Quickly Learning a CVaR Policy](https://mlsanity.com/paper/1911.01546/) (2019)
- [How Should a Robot Assess Risk? Towards an Axiomatic Theory of Risk in Robotics](https://mlsanity.com/paper/1710.11040/) (2017)
- [Partial Policy Iteration for L1-Robust Markov Decision Processes](https://mlsanity.com/paper/2006.09484/) (2020)
- [An Analysis of Quantile Temporal-Difference Learning](https://mlsanity.com/paper/2301.04462/) (2023)
- [On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processes](https://mlsanity.com/paper/2304.12477/) (2023)
- [Risk-averse autonomous systems: A brief history and recent developments from the perspective of optimal control](https://mlsanity.com/paper/2109.08947/) (2021)
- [An Alternative to Variance: Gini Deviation for Risk-averse Policy Gradient](https://mlsanity.com/paper/2307.08873/) (2023)
- [Wasserstein Distributionally Robust Motion Control for Collision Avoidance Using Conditional Value-at-Risk](https://mlsanity.com/paper/2001.04727/) (2020)
- [Prospect-theoretic Q-learning](https://mlsanity.com/paper/2104.05311/) (2021)
- [Quantile Reinforcement Learning](https://mlsanity.com/paper/1611.00862/) (2016)
- [Risk-Sensitive Optimal Execution via a Conditional Value-at-Risk Objective](https://mlsanity.com/paper/2201.11962/) (2022)

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

- [Planning and Learning in Average Risk-aware MDPs](https://mlsanity.com/paper/2503.17629/) (2025)
- [Risk-Averse Total-Reward Reinforcement Learning](https://mlsanity.com/paper/2506.21683/) (2025)
- [Boosting CVaR Policy Optimization with Quantile Gradients](https://mlsanity.com/paper/2601.22100/) (2026)
- [Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity](https://mlsanity.com/paper/2602.03778/) (2026)
- [Stochastic Minimum-Cost Reach-Avoid Reinforcement Learning](https://mlsanity.com/paper/2605.11975/) (2026)
- [Online Policy Evaluation for MDPs with Dynamic UBSR Measures](https://mlsanity.com/paper/2607.23030/) (2026)

## Abstract (arXiv)

In Markov decision processes (MDPs), quantile risk measures such as Value-at-Risk are a standard metric for modeling RL agents' preferences for certain outcomes. This paper proposes a new Q-learning algorithm for quantile optimization in MDPs with strong convergence and performance guarantees. The algorithm leverages a new, simple dynamic program (DP) decomposition for quantile MDPs. Compared with prior work, our DP decomposition requires neither known transition probabilities nor solving complex saddle point equations and serves as a suitable foundation for other model-free RL algorithms. Our numerical results in tabular domains show that our Q-learning algorithm converges to its DP variant and outperforms earlier algorithms.