基于Lyapunov的弱耦合MDP样本复杂度分析

# 1 引言 来源：https://arxiv.org/html/2606.14095

# 基于李雅普诺夫的弱耦合马尔可夫决策过程样本复杂度分析

Tianhao Wu\(^1\), Matthew Zurek\(^2\), Weina Wang\(^3\), Qiaomin Xie\(^1\)

1. 工业与系统工程系，威斯康星大学麦迪逊分校，电子邮件：[email protected]
2. 计算机科学系，威斯康星大学麦迪逊分校，电子邮件：[email protected]
3. 计算机科学系，卡内基梅隆大学，电子邮件：[email protected]
4. 工业与系统工程系，威斯康星大学麦迪逊分校，电子邮件：[email protected]

**摘要** 本文研究了在生成模型下，平均奖励弱耦合马尔可夫决策过程（WCMDP）和多臂赌博机（RB）中学习的样本复杂度。若简单归约为表格型MDP，则由于状态-动作空间随臂数 \(N\) 呈指数级增长，会导致极高的复杂度界限。通过利用弱耦合结构，我们证明可以在样本复杂度和计算复杂度均为 \(N\) 的多项式函数的情况下学习到近似最优策略。具体来说，我们分析了“插件法”，即对从数据中估计出的经验模型应用高效的规划算法。对于完全异构的WCMDP，我们建立了首个具有多项式复杂度的有限样本PAC保证，且最优性差距为 \(O(1/\sqrt{N})\)。对于同构RB，我们进一步证明在温和的结构性假设下可以达到更小的最优性差距。我们工作的一个主要技术贡献是提出了一种新的基于李雅普诺夫（Lyapunov）的分析框架。与依赖难以控制的偏差函数的经典方法不同，我们的框架使用显式构造的李雅普诺夫函数，并结合真实模型与经验模型之间的漂移转移技术。该框架中一个具有独立意义的关键步骤是对底层线性规划（LP）松弛进行细粒度的扰动分析，这为分析基于LP的策略和弱耦合系统提供了一个通用工具。

**关键词** 弱耦合马尔可夫决策过程，多臂赌博机，样本复杂度，李雅普诺夫分析

具有共享资源的大规模决策问题广泛存在于现代工程系统中，包括在线广告(Boutilier and Lu2016 (https://arxiv.org/html/2606.14095#bib.bib5), Zhou et al.2023 (https://arxiv.org/html/2606.14095#bib.bib49))、机器维护(Glazebrook et al.2005 (https://arxiv.org/html/2606.14095#bib.bib9))、作业调度(Yu et al.2018 (https://arxiv.org/html/2606.14095#bib.bib47))、监视(Villar2016 (https://arxiv.org/html/2606.14095#bib.bib35))以及医疗运筹(Biswas et al.2021 (https://arxiv.org/html/2606.14095#bib.bib4))等。这些复杂系统的一个常见建模范式是*弱耦合马尔可夫决策过程* (WCMDP)(Hawkins2003 (https://arxiv.org/html/2606.14095#bib.bib10))，它包含 \(N\) 个臂/子系统，每个臂本身也是一个MDP。在异构WCMDP中，每个臂根据自身动态演化，但它们的动作通过几个全局约束耦合在一起。目标是找到一个策略，在无限时间范围内最大化长期平均奖励。一个突出的特例是*（同构）多臂赌博机* (RB) 模型(Whittle1988 (https://arxiv.org/html/2606.14095#bib.bib42))，其中所有臂共享相同的MDP模型，且动作空间为二进制（激活/不激活）。在RB中，只有一个约束限制每个时间步激活臂的总数。

在WCMDP和RB中学习是具有挑战性的：当被视为单个MDP时，WCMDP/RB的状态-动作空间 \(\bm{\mathcal{S}} \times \bm{\mathcal{A}}\) 是各臂状态-动作空间的乘积，因此基数随臂数 \(N\) 呈指数增长。最近的工作已基本解决了*表格型平均奖励* MDP的样本复杂度问题，并确立了 \(\Theta(|\bm{\mathcal{S}} \times \bm{\mathcal{A}}|)\) 样本量的必要性(Wang et al.2022 (https://arxiv.org/html/2606.14095#bib.bib36),2024a (https://arxiv.org/html/2606.14095#bib.bib38), Zurek and Chen2025b (https://arxiv.org/html/2606.14095#bib.bib52), Zurek and Chen2025a (https://arxiv.org/html/2606.14095#bib.bib51))。将这些结果直接套用到WCMDP和RB上，忽略了弱耦合结构，会导致样本复杂度随 \(N\) 呈指数增长。即使是规划问题——在已知转移动态的情况下求解*精确*最优策略——由于巨大的状态空间，在计算上也是难以处理的。尽管如此，近期工作在规划问题上取得了显著进展，并开发了可高效计算的近似最优策略(Zhang et al.2025 (https://arxiv.org/html/2606.14095#bib.bib48), Hong et al.2024a (https://arxiv.org/html/2606.14095#bib.bib12),b (https://arxiv.org/html/2606.14095#bib.bib13), Yan et al.2024 (https://arxiv.org/html/2606.14095#bib.bib46), Gast et al.2024 (https://arxiv.org/html/2606.14095#bib.bib8))。本文考虑学习设定，并解决了以下关键问题：

> *如何在平均奖励WCMDP（或RB）中学习近似最优策略，同时避免对臂数 \(N\) 产生指数依赖？*

我们回答了这个问题，针对完全异构的WCMDP和同构RB，在能够访问生成模型的情况下，证明了可以通过利用弱耦合结构实现*关于 \(N\) 多项式*的复杂度。特别地，我们开发了一种*插件法*，将高效的规划算法——具体而言，针对WCMDP的ID策略(Zhang et al.2025 (https://arxiv.org/html/2606.14095#bib.bib48))和针对RB的二集合策略(Hong et al.2024a (https://arxiv.org/html/2606.14095#bib.bib12))——应用于从数据中估计出的经验模型。对于完全异构的WCMDP，我们建立了首个*有限样本（PAC）* 最优性差距保证，其中样本复杂度和计算复杂度均关于 \(N\) 呈多项式增长，以获得最优性差距为 \(O(1/\sqrt{N})\) 的近似最优策略。对于RB，我们进一步证明在温和的结构性假设下，可以实现任意 \(\beta > 0\) 的最优性差距 \(O(1/N^{\beta})\)。

本文的一个主要技术贡献是新的*基于李雅普诺夫* 的分析框架。经典的插件法样本复杂度分析使用标准模拟引理，该引理依赖于MDP的偏差函数（a.k.a. 相对值函数）(Zurek and Chen2024 (https://arxiv.org/html/2606.14095#bib.bib50), Li et al.2020 (https://arxiv.org/html/2606.14095#bib.bib21), Agarwal et al.2020 (https://arxiv.org/html/2606.14095#bib.bib1))。偏差函数通常是隐式的且难以控制，尤其是在我们采用复杂的规划算法时。我们的方法用显式构造的*李雅普诺夫函数*替代了偏差函数的作用。具体来说，我们的框架首先对所采用的规划算法在真实系统中进行李雅普诺夫漂移分析，然后利用漂移转移技术，通过显式界定李雅普诺夫函数的范数来分析经验系统。只要规划算法允许进行李雅普诺夫漂移分析，该框架就适用，从而为分析平均奖励弱耦合系统中的插件法提供了强大工具。我们在第5节 (https://arxiv.org/html/2606.14095#S5) 中详细介绍了该框架。

作为实现李雅普诺夫框架的关键步骤，我们为与RB相关的线性规划（LP）松弛开发了细粒度的扰动分析。该分析适用于任何输入受到扰动的情况，包括但不限于基于采样的估计。除了作为证明中的技术工具外，该扰动结果还揭示了使用此LP构造的策略固有一种鲁棒性：在适当的技术条件下，该策略对于受扰动的输入是稳定的，即除了一个状态外，其他所有状态下的动作保持不变，而在这个状态中，动作概率会进行调整以满足扰动下的约束。由于许多WCMDP和RB的控制方案依赖于求解此LP松弛的变体，我们的扰动结果可以用作分析其他算法的鲁棒性模块，包括在WCMDP和RB文献中广泛研究的各种索引和LP优先级策略(Weber and Weiss1990 (https://arxiv.org/html/2606.14095#bib.bib41), Verloop2016 (https://arxiv.org/html/2606.14095#bib.bib34), Gast et al.2024 (https://arxiv.org/html/2606.14095#bib.bib8), Hodge and Glazebrook2015 (https://arxiv.org/html/2606.14095#bib.bib11))。

##### 相关工作。我们沿以下三个维度回顾相关工作。

*平均奖励RB/WCMDP的规划。* 对于RB，经典的起点是Whittle索引策略(Whittle1988 (https://arxiv.org/html/2606.14095#bib.bib42), Weber and Weiss1990 (https://arxiv.org/html/2606.14095#bib.bib41))，它源于拉格朗日松弛，并在问题满足可索引性时产生索引规则。然而，可索引性可能不成立或难以验证，即使成立，Whittle索引策略在有限系统中也未必最优。近期工作在平均奖励下的渐近最优性方面取得了进展：Hong et al. (2024b (https://arxiv.org/html/2606.14095#bib.bib13)) 表明单链/非周期条件是渐近最优的充分条件，而Hong et al. (2024a (https://arxiv.org/html/2606.14095#bib.bib12)) 在没有全局吸引子假设的情况下获得了指数级渐近最优性差距。从RB延伸到一般的WCMDP，Meuleau et al. (1998 (https://arxiv.org/html/2606.14095#bib.bib24)) 提出了带有贪婪两阶段启发式的马尔可夫任务分解，而近期基于李雅普诺夫的分析获得了完全异构WCMDP的最优性差距如 \(O(1/\sqrt{N})\) (Zhang et al.2025 (https://arxiv.org/html/2606.14095#bib.bib48))。这些结果属于规划范畴，并未直接提供在臂动态未知时的有限样本学习保证。

*平均奖励RB/WCMDP的学习。* 一条研究线关注平均奖励RB的在线学习，集中于遗憾保证。早期论文考虑针对简单基准策略的弱遗憾(Dai et al.2011 (https://arxiv.org/html/2606.14095#bib.bib6), Liu et al.2011 (https://arxiv.org/html/2606.14095#bib.bib23), Tekin and Liu2012 (https://arxiv.org/html/2606.14095#bib.bib32))。其他结果获得了针对更强基准的次线性遗憾，但要么计算复杂度呈指数增长(Ortner et al.2012 (https://arxiv.org/html/2606.14095#bib.bib28))，要么只适用于特殊RB类别如生灭臂(Wang et al.2020 (https://arxiv.org/html/2606.14095#bib.bib40))。在多动作平均奖励RB中，Xiong et al. (2022 (https://arxiv.org/html/2606.14095#bib.bib44)) 开发了基于LP的索引策略，该策略渐近最优，并设计了针对该索引策略的 \(\widetilde{O}(\sqrt{T})\) 遗憾学习算法。基于汤普森采样的算法也有研究(Jung et al.2019 (https://arxiv.org/html/2606.14095#bib.bib16))。这些遗憾结果并不直接意味着本文研究的PAC/样本复杂度保证，因为对于平均奖励MDP，没有通用的遗憾到PAC的转换(Tuynman et al.2024 (https://arxiv.org/html/2606.14095#bib.bib33))。一些论文研究了RB学习算法的收敛性(Avrachenkov and Borkar2022 (https://arxiv.org/html/2606.14095#bib.bib3), Avrachenkov et al.2024 (https://arxiv.org/html/2606.14095#bib.bib2), Killian et al.2021 (https://arxiv.org/html/2606.14095#bib.bib18)) 以及WCMDP (El Shar and Jiang2023 (https://arxiv.org/html/2606.14095#bib.bib7))，但它们没有提供有限样本的最优性差距界限。最近结合函数近似的Q学习方法旨在学习Whittle索引策略(Xiong and Li2023 (https://arxiv.org/html/2606.14095#bib.bib43), Xiong et al.2024 (https://arxiv.org/html/2606.14095#bib.bib45))；它们的有限时间收敛结果并未直接转化为本文所考虑的最优性差距的样本复杂度界限。对于有限时域或折扣目标，基于拉格朗日松弛、Q学习和深度强化学习的方法也被提出(Killian et al.2021 (https://arxiv.org/html/2606.14095#bib.bib18), Robledo et al.2022 (https://arxiv.org/html/2606.14095#bib.bib31), Killian et al.2022 (https://arxiv.org/html/2606.14095#bib.bib19), Nakhleh et al.2021 (https://arxiv.org/html/2606.14095#bib.bib26), Robledo et al.2024 (https://arxiv.org/html/2606.14095#bib.bib30))，但保证大多是渐近的或针对不同的性能标准。

*表格型平均奖励MDP的样本复杂度。* 近期工作获得了单臂表格型平均奖励MDP的尖锐样本复杂度界限。对于具有混合时间界 \(t_{\mathrm{mix}}\) 的一致混合或一致遍历MDP，Wang et al. (2024b (https://arxiv.org/html/2606.14095#bib.bib39)) 获得了极小极大最优样本复杂度 \(\widetilde{O}(S A t_{\mathrm{mix}} / \varepsilon^2)\)，与对数因子内的下界匹配；另见Jin and Sidford (2021 (https://arxiv.org/html/2606.14095#bib.bib15))。对于弱通信MDP，Zurek and Chen (2025b (https://arxiv.org/html/2606.14095#bib.bib52)) 建立了极小极大最优界限 \(\widetilde{O}(S A H / \varepsilon^2)\)，其中 \(H = \mathrm{sp}(h^\star)\) 是最优偏差函数的跨度。Wang et al. (2022 (https://arxiv.org/html/2606.14095#bib.bib36)) 的早期工作给出了相关的上下界，而最一般的多链设定则利用瞬态时间参数进行了刻画。无参数和自适应算法也已开发(Tuynman et al.2024 (https://arxiv.org/html/2606.14095#bib.bib33), Neu and Okolo2024 (https://arxiv.org/html/2606.14095#bib.bib27), Zurek and Chen2024 (https://arxiv.org/html/2606.14095#bib.bib50), Lee et al.2025 (https://arxiv.org/html/2606.14095#bib.bib20), Zurek and Chen2025a (https://arxiv.org/html/2606.14095#bib.bib51))。这些PAC/样本复杂度保证是针对单臂表格型MDP的；简单将其应用于 \(N\) 臂的WCMDP或RB会导致对 \(N\) 的指数依赖，因为联合状态-动作空间是指数级大的。

## 2 问题设定

### 2.1 弱耦合马尔可夫决策过程

一个弱耦合MDP由 \(N\) 个臂组成。每个臂 \(i \in [N] \triangleq \{1,2,\dots,N\}\) 本身与一个MDP \(\mathcal{M}_i = (\mathcal{S}, \mathcal{A}, P_i, r_i, (c_{k,i})_{k \in [K]})\) 相关联。这里 \(\mathcal{S}\) 和 \(\mathcal{A}\) 分别是状态和动作空间，均为有限集，满足 \(|\mathcal{S}| = S, |\mathcal{A}| = A\)；\(P_i(s_i' \mid s_i, a_i)\) 是从状态 \(s_i\) 在动作 \(a_i\) 下转移到状态 \(s_i'\) 的转移概率；\(r_i\) 是奖励函数；\(c_{k,i}\) 是成本函数（共有 \(K\) 种成本类型）。当臂 \(i\) 处于状态 \(s_i\) 并采取动作 \(a_i\) 时，它产生奖励 \(r_i(s_i, a_i)\) 和每种类型 \(k\) 的成本 \(c_{k,i}(s_i, a_i)\)。我们假设奖励函数取值在 \([0, r\)