Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation
Abstract
For a risk-averse finite-horizon Markov Decision Process, 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 reduce to linear MDPs in the risk-neutral case. 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 𝒪̃(d3/2HNH−1√K), where d is the number of features, H is the horizon, N≥2 is the mini-batch size, K is the number of episodes, and 𝒪̃ hides logarithmic factors. 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.
Related
- Independent Reinforcement Learning in Discounted Markov Games
- Continuous-Time Mean-Variance Portfolio Selection Reinforcement Learning Problems for a Markov Regime-Switching System with No-Shorting Constraints
- Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift
- Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
- Markov-driven self-similar measures and non-homogeneous slicing
BibTeX
@misc{ruszczynski2026reinforcement,
title = {{Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation}},
author = {Andrzej Ruszczynski and Tiangang Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.00654},
eprint = {2605.00654},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.00654},
}
RIS
TY - UNPB
TI - Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation
AU - Andrzej Ruszczynski
AU - Tiangang Zhang
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2605.00654
UR - https://arxiv.org/abs/2605.00654
AB - For a risk-averse finite-horizon Markov Decision Process, 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 reduce to linear MDPs in the risk-neutral case. 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 𝒪̃(d^3/2HN^H−1√K), where d is the number of features, H is the horizon, N≥2 is the mini-batch size, K is the number of episodes, and 𝒪̃ hides logarithmic factors. 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.
ER -