Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation

arXiv:2605.00654v1 Announce Type: new Abstract: 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 Oig(H^2 N^H sqrt{ K}ig), 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.

Source: arXiv cs.LG | 2026-05-04