A Doubly Robust Approach to Sparse Reinforcement Learning

📄 arXiv: 2310.15286v1 📥 PDF

作者: Wonyoung Kim, Garud Iyengar, Assaf Zeevi

分类: stat.ML, cs.LG

发布日期: 2023-10-23

💡 一句话要点

提出双重稳健算法以解决稀疏强化学习问题

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

关键词: 稀疏强化学习 马尔可夫决策过程 后悔最小化 双重稳健方法 特征向量 策略更新 数值实验

📋 核心要点

  1. 现有的稀疏线性马尔可夫决策过程算法需要已知稀疏参数和oracle访问，限制了其应用。
  2. 本文提出的算法结合双重稳健方法，利用所有动作的特征向量，克服了现有方法的局限性。
  3. 实验结果表明，所提算法在后悔界限上优于现有方法，且在数值实验中表现出色。

📝 摘要（中文）

本文提出了一种新的后悔最小化算法，针对状态转移分布为观察特征线性函数的稀疏线性马尔可夫决策过程（SMDP）。先前的算法需要已知稀疏参数和对未知策略的oracle访问。我们通过结合双重稳健方法，利用所有动作的特征向量，并采用新颖的分析技术，使算法能够使用所有周期的数据。所提算法的后悔界限为$ ilde{O}(σ^{-1}{ ext{min}} s{ ext{star}} H ext{sqrt}(N))$，其中$σ_{ ext{min}}$为特征向量平均Gram矩阵的最小特征值，$s_{ ext{star}}$为稀疏参数，$H$为每个回合的长度，$N$为回合数。我们提供了一个新的SMDP子类的下界，匹配上界至对数因子。数值实验支持理论结果，展示了算法的优越性能。

🔬 方法详解

问题定义：本文解决的是稀疏线性马尔可夫决策过程（SMDP）中的后悔最小化问题。现有方法依赖于已知的稀疏参数和oracle访问，限制了其适用性和灵活性。

核心思路：我们提出的算法结合了双重稳健方法，允许使用所有动作的特征向量，并通过新颖的分析技术，利用所有周期的数据，从而克服了现有方法的限制。

技术框架：算法的整体架构包括数据收集、特征提取、后悔计算和策略更新四个主要模块。数据收集阶段从多个回合中获取信息，特征提取阶段则提取每个动作的特征向量。后悔计算模块使用双重稳健方法来评估策略的表现，最后策略更新模块根据计算结果调整策略。

关键创新：本文的主要创新在于结合双重稳健方法与新分析技术，使得算法能够在不知道稀疏参数的情况下，仍然有效地利用所有可用数据。这一设计显著提高了算法的灵活性和适用性。

关键设计：算法中的关键参数包括特征向量的选择和后悔计算的方式。损失函数设计为考虑所有动作的特征向量，确保算法在每个回合中都能有效学习。

📊 实验亮点

实验结果显示，所提算法在后悔界限上达到了$ ilde{O}(σ^{-1}{ ext{min}} s{ ext{star}} H ext{sqrt}(N))$，与现有算法相比，后悔值显著降低，且在多个测试场景中表现出优越的性能，验证了理论分析的有效性。

🎯 应用场景

该研究的潜在应用领域包括机器人控制、自动驾驶、个性化推荐系统等。通过提高稀疏强化学习算法的灵活性和性能，能够在复杂环境中实现更高效的决策制定，具有重要的实际价值和未来影响。

📄 摘要（原文）

We propose a new regret minimization algorithm for episodic sparse linear Markov decision process (SMDP) where the state-transition distribution is a linear function of observed features. The only previously known algorithm for SMDP requires the knowledge of the sparsity parameter and oracle access to an unknown policy. We overcome these limitations by combining the doubly robust method that allows one to use feature vectors of \emph{all} actions with a novel analysis technique that enables the algorithm to use data from all periods in all episodes. The regret of the proposed algorithm is $\tilde{O}(σ^{-1}{\min} s{\star} H \sqrt{N})$, where $σ_{\min}$ denotes the restrictive the minimum eigenvalue of the average Gram matrix of feature vectors, $s_\star$ is the sparsity parameter, $H$ is the length of an episode, and $N$ is the number of rounds. We provide a lower regret bound that matches the upper bound up to logarithmic factors on a newly identified subclass of SMDPs. Our numerical experiments support our theoretical results and demonstrate the superior performance of our algorithm.