Generalized Linear Markov Decision Process

📄 arXiv: 2506.00818v1 📥 PDF

作者: Sinian Zhang, Kaicheng Zhang, Ziping Xu, Tianxi Cai, Doudou Zhou

分类: stat.ML, cs.LG

发布日期: 2025-06-01

备注: 34 pages, 9 figures

💡 一句话要点

提出广义线性MDP框架，解决传统线性MDP在非线性奖励场景下的局限性

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

关键词: 广义线性模型 马尔可夫决策过程 强化学习 离线强化学习 半监督学习 非线性奖励 样本效率

📋 核心要点

  1. 传统线性MDP假设奖励函数是线性的，这限制了其在实际应用中的适用性，尤其是在奖励具有非线性或离散结构的场景下。
  2. 论文提出了广义线性MDP (GLMDP) 框架，该框架使用广义线性模型 (GLM) 对奖励进行建模，同时保持线性转移动态。
  3. 论文提出了GPEVI和SS-GPEVI两种离线强化学习算法，并在实验中证明了它们在样本效率方面的提升，尤其是在奖励标签有限的情况下。

📝 摘要（中文）

线性马尔可夫决策过程(MDP)框架为强化学习(RL)提供了有原则的基础，具有强大的理论保证和样本效率。然而，它具有限制性的假设——即转移动态和奖励函数在同一特征空间中都是线性的——限制了其在实际领域中的适用性，在实际领域中，奖励通常表现出非线性或离散结构。受到医疗保健和电子商务等应用的推动，在这些应用中，数据稀缺且奖励信号可以是二元的或计数值的，我们提出了广义线性MDP(GLMDP)框架——线性MDP框架的扩展——该框架使用广义线性模型(GLM)对奖励进行建模，同时保持线性转移动态。我们建立了GLMDP关于一个新函数类的贝尔曼完备性，该函数类可以容纳非线性奖励，并开发了两种离线RL算法：广义悲观值迭代(GPEVI)和一个利用标记和未标记轨迹的半监督变体(SS-GPEVI)。我们的算法在策略次优性方面实现了理论保证，并在奖励标签昂贵或有限的情况下证明了改进的样本效率。

🔬 方法详解

问题定义：线性MDP假设转移概率和奖励函数都关于状态特征线性，这在实际问题中通常不成立，例如奖励是二元或者计数类型。因此，需要扩展线性MDP框架，使其能够处理非线性奖励函数，同时保持线性转移动态的优势。

核心思路：核心思路是将奖励函数建模为广义线性模型（GLM），GLM允许奖励函数是状态特征的非线性函数，但仍然保持了较好的数学性质，便于理论分析和算法设计。同时，转移函数仍然保持线性，以便利用线性MDP的优势。

技术框架：GLMDP框架包含以下几个关键部分：1. 状态空间和动作空间；2. 线性转移概率模型，表示为状态特征的线性组合；3. 广义线性奖励模型，使用GLM将状态特征映射到奖励值；4. 贝尔曼方程的扩展，用于处理非线性奖励函数；5. 离线强化学习算法，包括GPEVI和SS-GPEVI。GPEVI是一种悲观的值迭代算法，通过对值函数进行下界估计来保证策略的安全性。SS-GPEVI是GPEVI的半监督变体，利用未标记的轨迹来提高样本效率。

关键创新：最重要的创新点在于提出了GLMDP框架，将线性MDP扩展到非线性奖励函数的情况。此外，还提出了半监督的GPEVI算法，利用未标记数据来提高样本效率，这在奖励标签获取成本高昂的场景下非常重要。

关键设计：GPEVI算法的关键设计在于悲观值函数的估计，通过对值函数进行下界估计，保证了策略的安全性。SS-GPEVI算法的关键设计在于如何有效地利用未标记数据，通过对未标记数据进行聚类或者其他方式的预处理，可以提高算法的性能。具体来说，GPEVI算法通过构建置信区间来估计值函数的下界，而SS-GPEVI算法则利用未标记数据来缩小置信区间，从而提高估计的准确性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文提出了GPEVI和SS-GPEVI两种离线强化学习算法，并在仿真实验中证明了它们的有效性。实验结果表明，在奖励标签有限的情况下，SS-GPEVI算法的性能优于GPEVI算法，并且两种算法都优于传统的线性MDP算法。具体的性能提升幅度未知，需要在论文中查找。

🎯 应用场景

该研究成果可应用于医疗保健和电子商务等领域，在这些领域中，数据稀缺且奖励信号可以是二元的或计数值的。例如，在医疗保健中，可以利用GLMDP来优化治疗方案，其中奖励可以是患者的生存时间或疾病控制情况。在电子商务中，可以利用GLMDP来优化推荐策略，其中奖励可以是用户的点击率或购买金额。该框架在奖励函数非线性但数据量有限的场景下具有重要应用价值。

📄 摘要（原文）

The linear Markov Decision Process (MDP) framework offers a principled foundation for reinforcement learning (RL) with strong theoretical guarantees and sample efficiency. However, its restrictive assumption-that both transition dynamics and reward functions are linear in the same feature space-limits its applicability in real-world domains, where rewards often exhibit nonlinear or discrete structures. Motivated by applications such as healthcare and e-commerce, where data is scarce and reward signals can be binary or count-valued, we propose the Generalized Linear MDP (GLMDP) framework-an extension of the linear MDP framework-that models rewards using generalized linear models (GLMs) while maintaining linear transition dynamics. We establish the Bellman completeness of GLMDPs with respect to a new function class that accommodates nonlinear rewards and develop two offline RL algorithms: Generalized Pessimistic Value Iteration (GPEVI) and a semi-supervised variant (SS-GPEVI) that utilizes both labeled and unlabeled trajectories. Our algorithms achieve theoretical guarantees on policy suboptimality and demonstrate improved sample efficiency in settings where reward labels are expensive or limited.