Primal-Dual Representation Learning for Low-Rank Constrained MDPs

📄 arXiv: 2610.30756v1 📥 PDF

作者: Chenhao Zhou, Chao Zhang, Wensong Bai, Hanbin Zhao, Hui Qian

分类: cs.LG

发布日期: 2026-10-22

备注: Accepted at NeurIPS 2026

💡 一句话要点

提出REP-PD-TEG以解决低秩约束MDP中的表示学习问题

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

关键词: 约束马尔可夫决策过程 表示学习 低秩模型 策略优化 最大似然学习

📋 核心要点

  1. 现有方法在低秩约束MDP中难以同时学习转移表示和控制约束违规，导致效率低下。
  2. 论文提出REP-PD-TEG算法，通过最大似然学习转移特征，并使用乐观拉格朗日目标进行规划。
  3. REP-PD-TEG在软累积违规设置下实现了最优的回报策略界限，并提供了理论保证，具有显著的样本效率提升。

📝 摘要（中文）

表示学习显著提高了无约束连续状态马尔可夫决策过程（MDP）的效率，但其在约束MDP（CMDP）中的扩展面临挑战，因为必须在控制约束违规的同时学习转移表示。本文研究了低秩CMDP的表示学习，并提出了REP-PD-TEG算法，适用于软累积违规设置。该算法通过衰减的ε-贪婪混合执行策略与环境交互，利用收集的样本通过最大似然学习转移特征。基于学习到的特征，构建不确定性奖励并使用乐观拉格朗日目标进行规划，以获得回报策略。我们证明了回报策略的遗憾和软违规保证，并量化了衰减ε-贪婪探索的影响。REP-PD-TEG实现了最优的$ ilde O( ext{sqrt}(K))$回报策略界限，并在探索性动作收费时给出了$ ilde O(K^{3/4})$的整体样本界限。

🔬 方法详解

问题定义：本文旨在解决低秩约束马尔可夫决策过程（CMDP）中的表示学习问题。现有方法在控制约束违规的同时，难以有效学习转移表示，导致性能受限。

核心思路：论文提出REP-PD-TEG算法，采用衰减的ε-贪婪策略与环境交互，利用收集的样本进行转移特征的最大似然学习，从而在保证约束控制的前提下优化策略。

技术框架：该方法分为两个主要阶段：特征学习阶段和策略规划阶段。在特征学习阶段，算法通过与环境的交互收集样本并学习转移特征；在策略规划阶段，基于学习到的特征构建不确定性奖励，并使用乐观拉格朗日目标进行规划。

关键创新：REP-PD-TEG是首个在低秩连续状态CMDP中提供理论保证的表示学习方法，能够同时处理软累积违规和硬违规控制，显著提升了策略的有效性。

关键设计：算法中采用了衰减的ε-贪婪策略，设置了最大似然损失函数，并通过优化拉格朗日目标进行策略规划，确保了在探索性动作收费情况下的样本效率。

🖼️ 关键图片

fig_0

📊 实验亮点

REP-PD-TEG在软累积违规设置下实现了最优的回报策略界限$ ilde O( ext{sqrt}(K))$，并在探索性动作收费时提供了$ ilde O(K^{3/4})$的整体样本界限，显著优于现有方法，展示了良好的理论性能和实际应用潜力。

🎯 应用场景

该研究的潜在应用领域包括机器人控制、自动驾驶、智能制造等需要在复杂环境中进行决策的场景。通过有效的表示学习和约束控制，能够提升系统的安全性和效率，具有重要的实际价值和未来影响。

📄 摘要（原文）

Representation learning has substantially improved the efficiency of unconstrained continuous-state Markov Decision Processes (MDPs), but its extension to Constrained MDPs (CMDPs) is difficult because the transition representation must be learned while constraint violation is controlled. In this paper, we study representation learning for low-rank CMDPs with continuous state spaces, and propose REP-PD-TEG for the soft cumulative-violation setting. In the feature learning period, the algorithm interacts with the environment using a decaying-$ε$-greedy mixture execution policy, and uses the collected samples to learn transition features by maximum likelihood. Based on the learned features, it constructs uncertainty bonuses and plans with an optimistic Lagrangian objective to obtain the return policy. We prove regret and soft-violation guarantees for the return policies, and quantify the influence of the decaying-$ε$-greedy exploration. In particular, REP-PD-TEG achieves the optimal $\widetilde O(\sqrt K)$ return policy bound, and gives a $\widetilde O(K^{3/4})$ overall sample bound when exploratory actions are charged. For the stricter hard cumulative violation, where feasibility must be verified episode by episode, we propose REP-PD-H-TEG. It plans under a bonus-corrected lower-confidence utility certificate with the learned representation, and performs a stabilized dual search to obtain the return policy, yielding regret and hard-violation bounds. Together, these results give the first theoretically guaranteed representation-learning method for low-rank continuous-state CMDPs with both soft cumulative guarantees and certified hard-violation control.