mlsanityData to 14 Oct 2026

Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation

arXiv 2605.00654 ↗First posted 1 May 2026cs.LG cs.AI math.OCcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

Key facts. Cited by 1 paper 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.

Builds on

16 of 57 references.

References · 16

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2018Is Q-learning Provably Efficient?cited by 487
  4. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 337
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  7. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  8. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  9. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  10. 2014Algorithms for CVaR Optimization in MDPscited by 99
  11. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 65
  12. 2020Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regretcited by 58
4 more
  1. 2019Provably Efficient Reinforcement Learning with Aggregated Statescited by 20
  2. 2020Markov Decision Processes with Recursive Risk Measurescited by 18
  3. 2020Risk-Averse Learning by Temporal Difference Methodscited by 13
  4. 2017Approximate Value Iteration for Risk-aware Markov Decision Processescited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Mini-Batch Risk-Averse Deep Q-Learning: A Robot Navigation Case Studycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning
  2. 2024Achieving Constant Regret in Linear Markov Decision Processes
  3. 2024Horizon-Free Regret for Linear Markov Decision Processes
  4. 2024No-Regret Reinforcement Learning in Smooth MDPs
  5. 2021Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity
  6. 2024Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality
  7. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  8. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison