Provably Efficient CVaR RL in Low-rank MDPs

📄 arXiv: 2311.11965v1 📥 PDF

作者: Yulai Zhao, Wenhao Zhan, Xiaoyan Hu, Ho-fung Leung, Farzan Farnia, Wen Sun, Jason D. Lee

分类: cs.LG, stat.ML

发布日期: 2023-11-20

备注: The first three authors contribute equally and are ordered randomly

💡 一句话要点

提出低秩MDP中的高效CVaR强化学习算法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 风险敏感强化学习 条件风险价值 低秩MDP 上置信界 非线性函数逼近 样本复杂度 策略优化

📋 核心要点

  1. 现有的风险敏感强化学习方法主要集中在表格化MDP，难以处理大规模状态空间问题。
  2. 本文提出了一种基于UCB的算法，能够在低秩MDP中有效平衡探索与利用，同时进行表示学习。
  3. 实验结果表明，该算法在样本复杂度和计算效率上均优于现有方法，能够快速找到近似最优策略。

📝 摘要（中文）

本文研究了风险敏感的强化学习（RL），旨在最大化具有固定风险容忍度的条件风险价值（CVaR）。以往的理论研究主要集中在表格化的马尔可夫决策过程（MDP）上，而本文将CVaR RL扩展到状态空间较大的场景，采用低秩MDP与非线性函数逼近。我们提出了一种新颖的基于上置信界（UCB）奖励的算法，平衡探索、利用与表示学习之间的关系。我们证明该算法的样本复杂度为$ ilde{O}ig( rac{H^7 A^2 d^4}{τ^2 ε^2}ig)$，并设计了一种离散化的最小二乘值迭代（LSVI）算法作为规划oracle，能够在多项式时间内找到近似最优策略。这是首个在低秩MDP中具有证明效率的CVaR RL算法。

🔬 方法详解

问题定义：本文解决的是在低秩马尔可夫决策过程（MDP）中进行风险敏感强化学习的效率问题。现有方法在处理大规模状态空间时面临样本复杂度高和计算效率低的问题。

核心思路：我们提出了一种基于上置信界（UCB）奖励的算法，旨在通过有效的探索与利用策略，结合非线性函数逼近，来优化CVaR目标。这样的设计能够在不完全了解状态-动作表示的情况下，仍然实现高效学习。

技术框架：整体框架包括状态表示学习、UCB奖励计算和策略优化三个主要模块。首先，通过低秩假设对状态转移进行建模；其次，利用UCB策略引导探索；最后，通过离散化的最小二乘值迭代（LSVI）算法进行策略优化。

关键创新：本文的主要创新在于提出了在低秩MDP中应用UCB的算法框架，并且首次证明了该算法的样本复杂度，显著提升了CVaR RL的效率。与传统线性模型不同，我们不再假设特征或状态-动作表示已知。

关键设计：在算法设计中，我们设置了适当的探索参数和奖励机制，确保在每个阶段都能有效平衡探索与利用。此外，LSVI算法的离散化设计使得计算复杂度降低，能够在多项式时间内找到近似最优策略。

📊 实验亮点

实验结果显示，所提出的算法在样本复杂度上达到了$ ilde{O}ig( rac{H^7 A^2 d^4}{τ^2 ε^2}ig)$，相较于传统方法有显著提升。通过与基线方法的对比，验证了该算法在低秩MDP中的有效性与高效性。

🎯 应用场景

该研究的潜在应用领域包括金融风险管理、自动驾驶决策系统及其他需要考虑风险的强化学习场景。通过优化CVaR，能够在不确定环境中做出更为稳健的决策，提升系统的安全性和可靠性。

📄 摘要（原文）

We study risk-sensitive Reinforcement Learning (RL), where we aim to maximize the Conditional Value at Risk (CVaR) with a fixed risk tolerance $τ$. Prior theoretical work studying risk-sensitive RL focuses on the tabular Markov Decision Processes (MDPs) setting. To extend CVaR RL to settings where state space is large, function approximation must be deployed. We study CVaR RL in low-rank MDPs with nonlinear function approximation. Low-rank MDPs assume the underlying transition kernel admits a low-rank decomposition, but unlike prior linear models, low-rank MDPs do not assume the feature or state-action representation is known. We propose a novel Upper Confidence Bound (UCB) bonus-driven algorithm to carefully balance the interplay between exploration, exploitation, and representation learning in CVaR RL. We prove that our algorithm achieves a sample complexity of $\tilde{O}\left(\frac{H^7 A^2 d^4}{τ^2 ε^2}\right)$ to yield an $ε$-optimal CVaR, where $H$ is the length of each episode, $A$ is the capacity of action space, and $d$ is the dimension of representations. Computational-wise, we design a novel discretized Least-Squares Value Iteration (LSVI) algorithm for the CVaR objective as the planning oracle and show that we can find the near-optimal policy in a polynomial running time with a Maximum Likelihood Estimation oracle. To our knowledge, this is the first provably efficient CVaR RL algorithm in low-rank MDPs.