# Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation

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

## Key facts

- Cited by 1 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 16 of its 57 references that are in the map.
- First posted on arXiv 1 May 2026.

## 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, 16 of 16)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Algorithms for CVaR Optimization in MDPs](https://mlsanity.com/paper/1406.3339/) (2014)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret](https://mlsanity.com/paper/2006.13827/) (2020)
- [Provably Efficient Reinforcement Learning with Aggregated States](https://mlsanity.com/paper/1912.06366/) (2019)
- [Markov Decision Processes with Recursive Risk Measures](https://mlsanity.com/paper/2010.07220/) (2020)
- [Risk-Averse Learning by Temporal Difference Methods](https://mlsanity.com/paper/2003.00780/) (2020)
- [Approximate Value Iteration for Risk-aware Markov Decision Processes](https://mlsanity.com/paper/1701.01290/) (2017)

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

- [Mini-Batch Risk-Averse Deep Q-Learning: A Robot Navigation Case Study](https://mlsanity.com/paper/2609.07998/) (2026)

## Abstract (arXiv)

For a risk-averse finite-horizon Markov Decision Problem, we introduce a special class of Markov coherent risk measures, called mini-batch measures. We also define the class of multipattern risk-averse problems that generalizes the class of linear systems. We use both concepts in a feature-based Q-learning method with multipattern Q-factor approximation and we prove a high-probability regret bound of Obig(H2 NH √ Kbig), where H is the horizon, N is the mini-batch size, and K is the number of episodes. We also propose an economical version of the Q-learning method that streamlines the policy evaluation (backward) step. The theoretical results are illustrated on a stochastic assignment problem and a short-horizon multi-armed bandit problem.