Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR
Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR
复制标题
DOI：
10.48550/arxiv.2302.03201
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Kaiwen Wang;Nathan Kallus;Wen Sun
中科院分区：
文献类型：
--
作者：
Kaiwen Wang;Nathan Kallus;Wen Sun
本文研究风险敏感强化学习(RL)，重点研究具有风险容忍度的条件风险价值(CVAR)的目标。从多臂盗贼(MAB)出发，我们证明了极小极大CVaR的缺失率为$\Omega(Sqrt{\tau^{-1}AK})$，其中$A$是动作数，$K$是片数，并且它是通过具有新颖的Bernstein奖金的上置信限算法来实现的。对于表格马尔可夫决策过程(MDP)中的在线RL，我们证明了一个极小极大后悔下界：$Omega(Sqrt(-1)SAK})$(具有归一化累积报酬)，其中$S$是状态数，并提出了一种新的奖金驱动的价值迭代方法。我们证明了在连续性的假设下，我们的算法达到了最优的遗憾值O(-1)，并且总体上达到了近似最优的错误值O(-1)，这对于常数的值是极小极大最优的。这在最佳可用范围上有所改进。通过适当地离散化奖励，我们的算法在计算上是高效的。
In this paper, we study risk-sensitive Reinforcement Learning (RL), focusing on the objective of Conditional Value at Risk (CVaR) with risk tolerance $\tau$. Starting with multi-arm bandits (MABs), we show the minimax CVaR regret rate is $\Omega(\sqrt{\tau^{-1}AK})$, where $A$ is the number of actions and $K$ is the number of episodes, and that it is achieved by an Upper Confidence Bound algorithm with a novel Bernstein bonus. For online RL in tabular Markov Decision Processes (MDPs), we show a minimax regret lower bound of $\Omega(\sqrt{\tau^{-1}SAK})$ (with normalized cumulative rewards), where $S$ is the number of states, and we propose a novel bonus-driven Value Iteration procedure. We show that our algorithm achieves the optimal regret of $\widetilde O(\sqrt{\tau^{-1}SAK})$ under a continuity assumption and in general attains a near-optimal regret of $\widetilde O(\tau^{-1}\sqrt{SAK})$, which is minimax-optimal for constant $\tau$. This improves on the best available bounds. By discretizing rewards appropriately, our algorithms are computationally efficient.