Abstract:We study risk-sensitive reinforcement learning in finite discounted MDPs, where a generative model of the MDP is assumed to be available. We consider a family or risk measures called the optimized certainty equivalent (OCE), which includes important risk measures such as entropic risk, CVaR, and mean-variance. Our focus is on the sample complexities of learning the optimal state-action value function (value learning) and an optimal policy (policy learning) under recursive OCE. We provide an exact characterization of utility functions $u$ for which the corresponding OCE defines an objective that is PAC-learnable. We analyze a simple model-based approach and derive PAC sample complexity bounds. We establish that whenever $u$ does not have full domain $\text{dom}(u)\neq \mathbb{R}$, the corresponding problem is not PAC-learnable. Finally, we establish corresponding lower bounds for both value and policy learning, demonstrating tightness in the size $SA$ of state-action space, and for a more restricted class of utilities, we derive lower bounds that makes the dependence on the effective horizon $\frac{1}{1-\gamma}$ explicit. Specifically, for $\text{CVaR}_\tau$ we show that the correct dependence on $\tau$ is $\frac{1}{\tau^2}$, thus improving by a factor of $\frac{1}{\tau}$ over state-of-the-art although our bound has a suboptimal dependence on $\frac{1}{1-\gamma}$.
| Comments: | Accepted to RLC 2026. arXiv admin note: substantial text overlap with arXiv:2506.00286 |
| Subjects: | Machine Learning (cs.LG); Systems and Control (eess.SY); Machine Learning (stat.ML) |
| Cite as: | arXiv:2605.21763 [cs.LG] |
| (or arXiv:2605.21763v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.21763 arXiv-issued DOI via DataCite (pending registration) |
From: Mohammad Sadegh Talebi [view email]
[v1]
Wed, 20 May 2026 21:53:51 UTC (40 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。