Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret

Abstract

We study risk-sensitive reinforcement learning in episodic Markov decision processes with unknown transition kernels, where the goal is to optimize the total reward under the risk measure of exponential utility. We propose two provably efficient model-free algorithms, Risk-Sensitive Value Iteration (RSVI) and Risk-Sensitive Q-learning (RSQ). These algorithms implement a form of risk-sensitive optimism in the face of uncertainty, which adapts to both risk-seeking and risk-averse modes of exploration. We prove that RSVI attains an $\tilde{O}(\lambda (|\beta |H^2)\cdot \sqrt{H^3{S}^{2}AT})$ regret, while RSQ attains an $\tilde{O}(\lambda (|\beta |H^2)\cdot \sqrt{H^{4}SAT})$ regret, where $\lambda (u)=(e^{3u}-1)/u$ for $u>0$. In the above, $\beta$ is the risk parameter of the exponential utility function, $S$ the number of states, $A$ the number of actions, $T$ the total number of timesteps, and $H$ the episode length. On the flip side, we establish a regret lower bound showing that the exponential dependence on $|\beta |$ and $H$ is unavoidable for any algorithm with an $\tilde{O}(\sqrt{T})$ regret (even when the risk objective is on the same scale as the original reward), thus certifying the near-optimality of the proposed algorithms. Our results demonstrate that incorporating risk awareness into reinforcement learning necessitates an exponential cost in $|\beta |$ and $H$, which quantifies the fundamental tradeoff between risk sensitivity (related to aleatoric uncertainty) and sample efficiency (related to epistemic uncertainty). To the best of our knowledge, this is the first regret analysis of risk-sensitive reinforcement learning with the exponential utility.

References in corpus (19)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Lyapunov-based Safe Policy Optimization for Continuous Control
• Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach
• Risk-Aversion in Multi-armed Bandits
• Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measure
• Generalization and Exploration via Randomized Value Functions
• Risk-sensitive Markov control processes
• Algorithms for CVaR Optimization in MDPs
• Estimating Risk and Uncertainty in Deep Reinforcement Learning
• Zero-sum Risk-Sensitive Stochastic Games
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Policy Gradient for Coherent Risk Measures
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Exploration-Exploitation in Constrained MDPs
• Constrained Upper Confidence Reinforcement Learning
• A Block Coordinate Ascent Algorithm for Mean-Variance Optimization
• Generalized Risk-Aversion in Stochastic Multi-Armed Bandits
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• Epistemic Risk-Sensitive Reinforcement Learning

Cited by in corpus (3)

• Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
• On the Convergence and Optimality of Policy Gradient for Markov Coherent Risk
• Mean-Semivariance Policy Optimization via Risk-Averse Reinforcement Learning