论文阅读二十一：通过近似因子分解克服强化学习中的维数诅咒

摘要

众所周知，强化学习（RL）算法存在维数灾难，这是指大规模问题往往导致样本复杂度呈指数级增长。常用解决方案是使用深度神经网络进行函数近似。然而，这种方式通常缺少理论保障。为了理论性地解决维数诅咒，我们观察到，许多真实世界问题显示出特定任务的结构，当适当利用时，可以改进RL的样本效率。基于这种见解，我们提出通过将原始马尔可夫决策过程（MDP）近似分解到较小的、独立演化的MDPs来解决维数诅咒。这种因子分解使得在基于模型和无模型的环境中开发样本高效的RL算法成为可能，后者涉及方差减少的Q学习变体。我们为这两种提出的算法提供了改进的样本复杂度保证。值得注意的是，通过MDP的近似因式分解利用模型结构，样本复杂性对状态动作空间大小的依赖性可以呈指数级降低。从数值上讲，我们通过在合成MDP任务和配备风电场的储能控制问题上的实验证明了我们提出的方法的实用性。论文地址

引言

近年来，强化学习已经成为未知环境中解决序列决策问题的流行框架，应用在不同领域，如机器人（Kober等，2013）、运输（Haydari & Yilmaz,2020），功率系统（Chen等，2022），和金融市场（Charpentier等，2021）。尽管显著进展，维数诅咒人仍是RL任务中的主要瓶颈（Sutton & Barto，2018）。具体地，样本复杂度与环境的状态动作空间的维度几何增长，对大规模应用提出挑战。例如，在机器人控制中，即便为单个及其人增加多一个自由度将显著提升控制问题的复杂性（Spong等，2020）。

为了克服样本复杂度的维数诅咒，常用方式是结合函数近似来使用预定义的函数类（如，神经网络）（SUtton & Barto，2018）来近似值函数或策略。随着这种方法在特定应用中工作，这些方法严重依赖函数近似类的设计，裁剪参数微调和其他经验观点。而且，它们通常缺少理论保证。据我们所知，大多数现有的结果局限在具有线性函数近似（Tsitsiklis & Van， 1996；Bhandari等，2018；Srikant & Ying，2019；Chen等，2023）的基础设置。少数例外使用非线性近似（如，神经网络）（Fan等，2020；Xu & Gu, 2020），通常需要为理论分析量身定制的额外假设，这与实际算法产生了差距。因此，在RL中，实现大规模顺序决策问题的可证明样本效率仍然是一个重大挑战（Sutton和Barto，2018）。

形式上，RL问题通常建模为MDP，其中环境由未知转移核和奖励函数表示。重要的是要注意，在许多真实世界应用中，转移概率和奖励函数表现出固有的因子结构，若利用适当，将减轻在样本复杂度中的维数诅咒。作为示例，考虑基于模型的RL，其中维数诅咒转变为评估转移概率（潜在高维度）的挑战。为解决这种挑战，幸运地是，一些部分依赖结构普遍存在于像可持续性努力（Yeh等人，2023）、排队系统（Wei等人，2024）和网络系统（Qu等人，2020）等应用中。具体地，当前状态动作对和下一状态之间的转移依赖不是全连接的，下一状态通常仅依赖于当前状态动作变量的一个子集。例如，在电力系统控制中，电力需求的动态虽然是随机的，但与发电决策无关。类似的，在多代理机器人控制任务中，一个机器人的动作通常不影响其他地理位置遥远的，允许更加局部化和稀疏性的建模和方案。通过在算法设计中识别和利用这些架构，可能显著减少样本复杂度。

一个值得注意的捕捉这种思想的框架是因子分解MDP框架（Osband & Van，2014），其中，原始MDP分解为较小和独立演化的MDPs的集合。此时，整体样本复杂性取决于每个独立DMP的状态动作空间的大小的和（而不是积）。因此，问题大小不再随着问题维度指数缩放，成功地克服了维数诅咒。虽然因子分解MDP框架看起来是一个由前景的方法，它依赖于原始MDP可以完美因子化到一组较小MDPs的假设。这种结构性假设限制了因子分解MDP方法的应用。此外，据我们所知，没有用于因子分解MDP设置的可证明的无模型算法，限制了不需要显式估计环境模型的更加灵活的方法的发展。

贡献

本文中，我们通过提出一种分解MDP到低纬组分的近似分解范式移除了因子分解MDP框架的限制。该方案可以视为因子分解MDP的扩展框架，允许不完全的因子分解模型。构建在这种框架之上，我们开发了可证明的RL算法，用于克服维数诅咒，并相较于先前基于模型和无模型范式的工作取得改进的样本效率。主要贡献总结如下。

MDP的近似因子分解和高效采样 为了解决维数诅咒，我们引入一种近似因子分解的方案，可以灵活分解任意MDP到低纬度组分。该方案通过识别和利用环境模型中的依赖结构，为因子分解操作提供了更大的灵活性，以在样本复杂性和最优性之间找到最佳权衡。使用这些近似因子分解MDPs，我们提出一个多组分因子分解同步采样方法来估计模型，塑造为一个成本优化图着色问题。使用这些近似因子化的MDP，我们提出了一种多分量因子化同步采样方法来估计模型，将其框架化为成本最优的图着色问题。这种方法允许从单个样本中同时采样多个成分，这与之前的分解MDP方法不同，在之前的分解方法中，每个样本只估计一个成分的转变。这种采样方法是降低我们基于模型和无模型算法中样本复杂性的关键。

基于模型的近似因子分解算法 我们开发了一个新颖的基于模型RL算法，利用提出的同步采样方法，并完全利用由近似因子分解识别的低纬度结构。通过分解大型核估计为较小、可管理组分，我们的算法取得可证明的问题依赖的采样复杂性（定理5.1），超越现有标准MDPs的最小最大最优界限（Azar等，2012）。此外，我们的方法推广了分解式 MDP 框架，当应用于这种设置时，可以以多达组件数量的倍数改进最著名的样本复杂度 (Chen et al., 2020) 。关键的技术挑战是解决同步采样和因子化采样中样本之间的统计相关性。在方差分析中，通过控制这些相关性，我们将依赖于组分大小的样本复杂度减少到依赖于最大组分。

采用近似因式分解的无模型方差缩小 Q 学习 我们提出一种无模型方法，采用近似因子分解的方差缩小Q学习（VRQL-AF），其结合同样的同步采样方法。它取得于我们基于模型方法（取决于对数项）相同得问题依赖采样复杂度保证（定理 6.1），超越现有标准MDPs得最小最大最有算法（Wainwright,2019b）。当应用于因子化MDPs(我们设置中得特例)，据我们所知，VRQL-AF是第一个可证明的取得近似最优样本复杂性保证的无模型算法。改进结果来自我们为近似因子化MDP量身定制的因子化经验Bellman算子，并与变量推导方法相结合，以最小化随机迭代算法的方差。这种集成需要精细的统计分析，以严格控制多因子组件的估计误差和迭代方差。

相关工作

我们的工作得益于RL社区中一些关键文献。我们依次讨论如下。

基于模型算法的有限样本分析 我们提出的算法（算法2）遵循基于模型的RL方法，其中学习过程设计模型评估和规划。基于模型的方法已被大量研究（Azar等，2012；Agarwal等，2020；Gheshlaghi等，2013；Sidford等，2018；Azar等，2017；Jin等，2020），在生成模型设置中（Li等，2020），取得 $\mathcal{O}(|\mathcal{S}||\mathcal{A}|\epsilon^{-2}(1 - \gamma)^{-3})$ 最小最大最有样本复杂性。该最小最大最优界限通过考虑最坏情况所有可能的MDPs实现的，没有利用问题中任何其他结构。相反，通过利用该结构进行算法设计，当MDP可以完全因子分解时，我们取得了依赖于状态和动作空间指数下降的样本复杂性。

无模型算法的有限样本分析 我们提出的算法还对齐无模型RL，其不估计模型，而是直接优化策略（Sutton & Barto，2018）。大量文献关注Q学习（Tsitsiklis，1994；Jaakkola等人，1993；Szepesvári，1997；Kearns和Singh，1998；Even-Dar等人，2003；Wainwright，2019a；Chen等人，2024a；Li等人，2024），采用不同的采样设置，证明了最小最大样本复杂度 $\tilde{\mathcal{O}}(|\mathcal{S}||\mathcal{A}|\epsilon^{-2}(1 - \gamma)^{-4})$ 。随着方差减少等进一步改进，Q学习已被证明在生成模型设置中实现了 $\tilde{\mathcal{O}}(|\mathcal{S}||\mathcal{A}|\epsilon^{-2}(1 - \gamma)^{-3})$ 的最小最优样本复杂度（Wainwright，2019b）。相反，我们的工作利用MDPs的近似因子分解结构，进一步增强样本效率。通过设计一个具有方差减少的分解经验贝尔曼算子，我们实现了相对于状态-动作空间大小的样本复杂度的指数级降低（参见定理 6.1），同时匹配对其他参数的极小极大依赖性。

因子化MDPs 我们的模型推广了因子MDP的框架（Boutilier等人，19951999），并将其扩展到考虑近似误差。关于因子MDP的大多数现有工作都是在情景框架中进行的，主要分析后悔表现（Guestrin等人，2003；Osband和Van Roy，2014；Xu和Tewari，2020；Tian等人，2020；Chen等人，2020）。特别是，最先进的结果转化为 $\tilde{\mathcal{O}}(\sum_{k=1}^{K}|\mathcal{X}_k|\epsilon^{-2}(1 - \gamma)^{-3})$ 样本复杂度，其中复杂度随着所有因子分量的状态作用空间大小 $|\mathcal{X}_k|$ 的总和而变化。在此基础上，我们提出了一种因子化同步采样技术，可以使用单个样本同时更新多个组件。通过将其与精细的交叉分量方差分析相结合，我们以实例依赖的方式将样本复杂度降低到 $\tilde{\mathcal{O}}(\text{max}_k|\mathcal{X}_k|\epsilon^{-2}(1 - \gamma)^{-3})$，这仅取决于最大分量大小而不是总和。这一结果与先前研究（Xu 和 Tewari，2020 年；Chen 等人，2020 年）中建立的下限相符，最高可达对数因子。至关重要的是，我们的方法不需要 MDP 表现出完美的可分解性，从而可以更广泛地适用于一般 MDP。

具有函数近似的 RL 为了使RL问题样本对大规模问题有效，一种常见的方法是采用函数近似（Sutton和Barto，2018）。直观地说，关键思想是将RL问题的搜索空间限制在预定义的函数类中，其中每个函数都可以用低维参数指定。这种方法取得了显著的实证成功（Mnih等人，2015；Silver等人，2017）。然而，具有函数近似的RL在理论上并没有得到很好的理解，除非在近似函数类的强结构假设下，例如函数类是线性的（Tsitsiklis和Van Roy，1996；Bhandari等人，2018；Srikant和Ying，2019；Chen等人，2023，2024b），满足Bellman完备性（Fan等人，2020），或其他（Dai等人，2018，Wang等人，2020年）。此外，函数近似通常以近似Q值为目标，而不是利用固有的转移核和奖励函数结构。在这项工作中，我们采用了一种不同的方法，利用近似因式分解结构，而不是实现函数近似。同样值得注意的是，我们的方法非常灵活，可以通过结合函数近似技术进一步扩展，为解决大规模RL问题提供了一个更广泛的框架。

模型和背景

考虑一个有限视野的折扣MDP $M = (S,A,P,r,\gamma)$ ，其中，S是有限状体空间，A是有限动作空间，P是转移核， $P(s'|s,a)$ 表示给定动作a从状态s到s’的转移概率，r: $S \times A \rightarrow [0,1]$ 是奖励函数， $\gamma \in (0,1)$ 是折扣因子。底层MDP（即，转移核P和奖励函数r）的模型参数对于代理是未知的。

在每个时间步，代理基于当前环境状态采取行动，根据转移概率随机转换到下一个状态，并接收一次性奖励。该过程重复，代理的目标是找到一个最有策略，进行动作选择，从而最大化长期折扣累积奖励。更加正式地，策略 $\pi$ 是从状态空间S到动作空间支持的概率分布集的映射。给定策略 $\pi$ ，其Q函数 $Q^{\pi} \in R^{|S||A|}$ 定义为 $Q^{\pi}(s,a) = E_{\pi,P}[\sum_{t=0}^{\infty} \gamma^t r(s_t,a_t) | s_0 = s, a_0 = a]$ ，对于所有 $(s,a) \in S \times A$ , 其中， $E_{\pi,P}[\cdot]$ 表示轨迹是通过按照转换P，并根策略 $\pi$ 选择动作生成的，即， $s_{t+1} \sim P(\cdot | s_t,a_t), a_{t+1} \sim \pi(\cdot | s_{t+1})$ ，其中所有 $t \ge 0$ 。有了上面定义的Q函数，代理的目标是找到最优策略 $\pi^{\star}$ 使得它的相关的Q函数对于所有状态空间对 $(s,a) \in S \times A$ 普遍最大化。已经证明，这种最优策略总是存在的（Puterman，2014）。

求解MDP的核心是贝尔曼最优方程，其指出，最有Q函数，表示为 $Q^{\star}$ ， 是不动点等式Q = H(Q)的唯一解，其中， H： $R^{|S||A|} \rightarrow R^{|S||A|}$ 是贝尔曼最优算子，定义为：

$$[\mathcal{H}(Q)](s,a) = E_{s^{'}\sim P(\cdot|s,a)}\left[r(s,a) + \gamma\underset{a^{'}\in a}{max}Q(s^{'},a^{'})\right]\,, \quad\forall(s,a) \in S \times A\,.$$

此外，一旦得到 $Q^{\star}$ ，最优策略可以通过基于 $Q^{\star}$ 贪婪地选择动作来计算。因此，问题简化为估计最优Q函数 $Q^{\star}$ 。

假设，MDP的模型参数已知。那么，我们可以通过值迭代方法 : $Q_{k+1} = H(Q_k)$ 高效找到 $Q^{\star}$ ，其中 $Q_0$ 任意初始化。由于算子 $\mathcal{H}(\cdot)$ 是关于 $\mathcal{l}_{\infty}$ 范数的收缩映射（Bertsekas和Tsitsiklis，1996；Sutton和Barto，2018；Puterman，2014），Banach不动点定理（Banach，1922）保证了值迭代方法在几何上收敛到 $Q^{\star}$ 。

在RL中，底层MDP的模型参数对于代理是未知的。因此，不可以直接执行值迭代方法来找到最优策略。一种自然地克服这种挑战的方法是首先估计模型参数，通过经验性采样，然后基于估计的模型执行值迭代方法。这杯称为基于模型的方法。另一种方法是求解贝尔曼最优方程，其使用随机近似方法，而不显式估计模型，这导致了诸如Q学习（Watkins & Dayan，2992）的无模型算法。

在本文中，我们研究了一种广泛使用的采样机制设置——生成模型（Kearns等人，2002；Kakade，2003）。它使我们能够查询任何状态-动作对（s，a），以根据潜在的随机转移核和奖励函数获得下一个状态s′和即时奖励r（s，α）的随机样本。

马尔可夫决策过程（MDP）的近似因子分解

我们首先介绍近似因子分解的概念，它是本文贡献的基础。假设每个状态 $s \in S$ 是一个n维向量，且状态空间可以写为 $S = \prod_{i=1}^n S_i$ ， 其中，对于所有 $i \in [n] := \lbrace 1,2,...,n\rbrace$ ， $S_i \subseteq R$ 。类似地，假设每个动作是一个m维向量，且 $A = \prod_{j=1}^m A_j$ ， 对于所有 $j \in [m]$ ， $A_j \subseteq R$ 。随着n和m增加，状态动作对的总数几何增长，这是维数诅咒的来源。本文中，状态 $s \in R^n$ 的每个组分 $s[i] \in S_i$ ，其中 $i \in [n]$ ， 称为子状态。子动作是类似的定义。为了介绍近似因子分解方案，我们开始介绍以下有用的定义：作用域，作用域集和作用域变量。

定义 3.1 考虑因子化的d维集合 $\mathcal{X} = \prod_{i=1}^d \mathcal{X}_i$ ， 其中 $\mathcal{X}_i \subseteq R$ 对于所有 $i \in [d]$。对于任意 $Z \subseteq [d]$ （我们称为作用域），相应的作用域集 $\mathcal{X}[Z]$ 定义为 $\mathcal{X}[Z] = \prod_{i \in Z}\mathcal{X}_i$ 。任意元素 $x[Z] \in \mathcal{X}[Z]$ (一个|Z|维向量)称为作用域变量。

当Z仅包含一个元素，如 Z = {i}， 对于一些 $i \in [d]$ ， 我们表示 $x[i]$ 为 $x[{i}]$ 。
有了定义3.1的帮助，现在我们可以介绍MDP M = （S,A,P,r, $\gamma$ ）的近似因子分解方案。具体地，近似因子分解由元组 $\mathcal{w} = \lbrace\mathcal{w}^P,\mathcal{w}^R\rbrace$ 表示，涉及转移核和奖励函数的操作。我们从转移核开始。

转移核的近似因子分解

转移核的一个因子分解方案 $\mathcal{w}^P$ 由元组 $\mathcal{w}^P = \lbrace K_{\mathcal{w}},\lbrace Z_k^S \subseteq [n] | k \in [K_{\mathcal{w}}\rbrace,\lbrace Z_k^P \subseteq [n + m]| k \in [K_{\mathcal{w}}]\rbrace\rbrace$ ， 其中

• $K_{\mathcal{w}} \in [n]$ 表示我们将转换内核划分为的组件数量；
• $\lbrace Z_k^S | k\in [K_{\mathcal{w}}]\rbrace$ 是n维状态空间 $S = \prod_{i=1}^n S_i$ 的作用域集。此外， $\lbrace Z_k^S | k \in [K_{\mathcal{w}}]\rbrace$ 形成[n]的分区，即 $\cup_{k=1}^{K_{\mathcal{w}}}Z_k^S = [n]$ ，且对于任意 $k_1 \ne k_2$ ， $Z_{k_1}^S \cap Z_{k_2}^S = \emptyset$ 。 对于每个作用域 $Z_k^S \subseteq [n]$ ， 有一个相关作用域集 $S[Z_k^S]$ 。
• $\lbrace Z_k^P | k \in [K_{\mathcal{w}}]\rbrace$ 是联合状态动作空间 $\mathcal{X} := S \times A = \prod_{i=1}^n S_i \prod_{j=1}^m A_i$ 的一个作用域集。例如，考虑具有3维状态空间和2维动作空间的MDP。若 $Z_k^P = \lbrace 1,2,4\rbrace$ ，那么其相关的作用域集 $\mathcal{X}[Z_k^P] = S_1 \times S_2 \times A_1$ 。

为简化符号，我们使用 $-Z_k^S$ 表示[n]中 $Z_k^S$ 的补，即 $-Z_k^S := [n]\ Z_k^S$ 。 因子分解方案 $\mathcal{W}^P$ 用于表征转移核内的分量依赖结构。为了说明我们的近似因式分解方案，我们首先考虑一种特殊情况，即转移核P关于 $\mathcal{ω}^P$ 是完全可因子分解的。即

$$\forall x = (s,a) \in \mathcal{X}, s' \in S, k \in [K_{\mathcal{w}}]: \quad P(s'|x) = \prod_{k=1}^{K_{\mathcal{w}}}P_k(s'[Z_k^S] | x[Z_k^P])\,, \tag{1}$$

其中， $P_k(\cdot| x[Z_k^P])$ 是所有 $x[Z_k^P]$ 的概率分布。方程（1）表明，不同k的 $s'[Z_k^S]$ 转换是独立的，且仅依赖于 $x\mathcal{X}[Z_k^P]$ 中的子状态-子空间对。 允许完美转换和奖励分解（稍后在第3.2节中介绍）的MDP称为因子MDP（Osband和Van Roy，2014）。直观地说，这意味着原始MDP可以分解为 $K_\mathcal{w}$ 个更小的组件，其转换和奖励仅取决于变量的子集，而不是整个状态和动作空间，从而降低了为MDP找到最优策略的复杂性。

如第1节所示，虽然因子化MDP框架是解决维度灾难挑战的一种有前景的方法，但要求底层MDP完全因子化是一个强有力的假设。为了消除这一限制，在这项工作中，我们提出了一种更通用的方案——近似因式分解——它允许转移核是不完全因式分解的，这意味着方程（1）并不完全成立。具体来说，为了开发一个近似的因子分解方案（即，得到方程（1）中“边际”转移概率 $P(s'[Z_k^S] | x[Z_k^P])$ 的估计），我们首先在下面定义一组可行的边际转移概率。对于任何 $k \in [K_{\mathcal{w}}]$ ，设

$$\begin{aligned} \mathcal{P}_k = \big\lbrace &P_k \in R^{|\mathcal{X}[Z_k^P]|\times |[S[Z_k^S]|} |\exist c \in \Sigma^{|\mathcal{X}[-Z_k^P|} \text{such that} \;P_k(s'[Z_k^S] | x[Z_k^P]) \\ &= \underset{x'[-Z_k^P]}{\sum} c[x'[-Z_k^P]]P(s'[Z_k^S]| x[Z_k^P],x'[-Z_k^P]), \forall s'[Z_k^S],x[Z_k^P] \in \mathcal{X}[Z_k^P] \big\rbrace \,, \end{aligned}$$

其中，我们使用 $\Sigma^d$ 表示任意$d \ge 0$ 的d维概率单纯形。然后，对于所有 $k \in [k_ω]$ ，我们任意选择 $P_k\in \mathcal{P}_k$ 。正如我们将在后面的章节中看到的，我们理论结果的发展并不依赖于 $P_k\in\mathcal{P}_k$ 的具体选择。为理解 $\mathcal{P}_k$ 的定义，再次考虑完全因子化设置，其中，对于任意 $x'[-Z_k^P], x"[-Z_k^P] \in \mathcal{X}[-Z_k^P]$ ， $P(s'[Z_k^S]|x[Z_k^P],x'[-Z_k^P]) = P(s'[Z_k^S]|x[Z_k^P],x"[-Z_k^P])$ ，因此 $s'[Z_k^S]$ 的转换不依赖于 $\mathcal{X}[-Z_k^P]$ 中的子状态-子动作对。因此， $\mathcal{P}_k$ 是所有k的单例集，这与方程（1）一致。回到底层MDP不能完全分解的情况，从 $P_k$ 中选择 $\mathcal{P}_k$ 可以被视为一种近似“边际”转移概率的方法。

给定近似方案 $\mathcal{w}^P$ ， 我们将关于转移核的近似误差定义为：

$$\triangle_{\mathcal{w}}^P = \underset{P_1\in\mathcal{P}_1,...,P_{K_{\mathcal{w}}}\in\mathcal{P}_{K_{\mathcal{w}}}}{\text{sup}} \underset{s'\in S,x\in\mathcal{X}}{max} \big|P(s'|x) - \prod_{k=1}^{K_{\mathcal{w}}}P_k(s'[Z_k^S]|x[Z_k^P])\big|\,. \tag{2}$$

为理解 $\triangle_{\mathcal{w}}^P$ ，观察到对于任意 $s'\in S$ 和 $x\in \mathcal{X}$ ，我们有：

$$\begin{aligned} &P(s'|x) - \prod_{k=1}^{K_{\mathcal{w}}}P_k(s'[Z_k^S]|x[Z_k^P]) \\ &= \underbrace{P(s'|x) - \prod_{k=1}^{K_{\mathcal{w}}}P_k(s'[Z_k^S]|x)}_{\triangle_1:\text{error from correlated transitions}} + \underbrace{\prod_{k=1}^{K_{\mathcal{w}}}P_k(s'[Z_k^S]|x) - \prod_{k=1}^{K_{\mathcal{w}}}P_k(s'[Z_k^S]|x[Z_k^P])}_{\triangle_2:\text{error from incomplete dependence}} \,. \end{aligned}$$

右侧第一项 $\triangle_1$ 表示由于忽略不同k的 $s'[Z_k^S]$ 转换之间的相关性而导致的误差，如果来自不同作用域集的子状态的转移是独立的，则该误差为零。右侧第二项 $\triangle_2$ 是由于忽略来自 $x[-Z_k^P]$ 的 $s'[Z_k^S]$ 转换依赖而引起的误差。请注意，当MDP是完全可因子分解的，得到 $\triangle_{\mathcal{w}}^P = 0$ (方程（1）)。

奖励函数的近似因子分解

来到奖励函数，因子分解可以表征为元组 $\mathcal{w}^R - \lbrace\mathcal{l}_{\mathcal{w}},\lbrace Z_i^R \in [n + m] | i \in [\mathcal{l}_{\mathcal{w}}]$ ，其中

• $\mathcal{l}_{\mathcal{w}}$ 是正整数，表示我们分解奖励函数的分量数；
• $\lbrace Z_i^R | i \in [\mathcal{l}_{\mathcal{w}}]$ 是联合状态动作空间 $\mathcal{X}$ 的一个作用域集。
  在这种分解方案下，全局奖励函数 $r(x)$ 由来自 $\lbrace r_i: \mathcal{X}[Z_i^R] \rightarrow [0,1]\rbrace_{i \in [\mathcal{l}_{\mathcal{w}}]}$ 的局部奖励函数的和来近似，其中，每个 $r_i$ 仅依赖于作用域变量 $x[Z_i^R]$ 。类似的，给定奖励函数的近似方案 $\mathcal{w}^R$ ，我们定义其近似误差为：

$$\triangle_{\mathcal{w}}^R = \underset{max}{x\in\mathcal{X}}|r(x) - \sum_{i=1}^{\mathcal{l}_{\mathcal{w}}}r_i(x[Z_i^R])|\,,$$

这是对我们对真实奖励函数的近似偏差的测量。近似误差 $\triangle_{\mathcal{w}}^R$ 是由奖励函数 $r(x)$ 可能依赖作用域集 $\mathcal{X}[Z_i^R]$ 之外的子状态-子空间对引起的。在特例底层MDP可以完全因子化为若干较小MDPs，以及它们的奖励函数的和等于原始奖励函数，有 $\triangle_{\mathcal{w}}^R = 0$ 。

一个说明示例

为了提供直观的理解，我们给出了一个在现实世界应用中应用近似因式分解方案的例子，证明它提供了额外的机会，可以在所需的解精度和样本效率之间实现更好的平衡。特别是，我们考虑了风电场中的储能控制问题。储能控制器（代理）旨在通过灵活地对储能系统进行充电或放电，使实时风力发电输出（状态）与所需的预测值对齐。

该问题可以建模为MDP，其中时间t的状态 $s_t = (w_t, p_t,c_t)$ ，风力发电量 $w_t$ ， 电价 $p_t$ ，和储能的充电状态（SoCial） $c_t$ 。动作 $a_t$ 表示时间t储能充电决定。转换依赖结构可以表示为二分图，如图 1（a）所示。在图中，左侧（LHS）节点表示时间t的状态和动作，而右侧（RHS）的节点表示时间 t+1的状态。节点之间的蓝色实线表示强依赖。例如，电价 $p_{t+1}$ 强依赖于以前的价格 $p_t$ 。而蓝色虚线表示弱依赖性。例如，风力发电量 $w_t$ 可以影响下一步的市场电价 $p_{t+1}$ ，然而相较于先前价格 $p_t$ 的直接影响，它的影响较弱。

图1（b）说明了该MDP的近似因子分解方案，其中系统的动态性被分为三个较小的分量——风力发电的动态性、电价和储能水平。每个组件中都保留了强烈的转移依赖性，但忽略了较弱的依赖性，如风力发电量对电价的影响。这导致了以下转移概率的近似值：

$$\hat{P}(s_{t+1}|s_t,a_t) = P(w_{t+1}|w_t)\cdot P(p_{t+1}|p_t)\cdot (c_{t+1}|c_t,a_t)\,.$$

该近似简化了模型，通过将转移动态性分解到更小、更可管理的组分，同时保留关键依赖。请注意，这个问题不属于因子MDP，因为动态不能完全分解为更小的组件。然而，我们的近似因子分解方案提供了一个更加灵活的框架，允许不完全的因子分解转移动态被分解为更小的组分，同时保持不足够的模型精度。这扩展了因子分解步骤的动作空间，通过针对问题的特定依赖结构进行定制，可以更有效地搜索解决方案准确性和样本效率之间的最佳权衡。

结构采样：多分量因子化同步采样

我们的主要贡献提出量身定制的无模型和基于模型的方法来解决近似因子化MDPs采样效率。这两种方法的核心是高效采样算法，其利用了因子分解结构。本节中，我们介绍这个核心模块，然后将其应用到后续章节中的基于模型和无模型的算法。

为了说明该采样算法的重要性，考虑经典的基于模型RL，其包含两个主要步骤：（1）通过经验性采样来估计转移核和奖励函数，和（2）在估计的模型上执行值迭代（或策略迭代）。采样效率的维数诅咒通常起源于第一步。具体地，为获得相对准确的模型估计，在每个状态-动作对的开始，我们需要对下一个状态进行足够次数的独立采样，导致样本复杂度正比于 $|S||A|$ ， 其与状态动作空间的大小线性缩放（因此，与状态动作空间维度指数性）。通过利用近似因子分解结构，我们开发了更加哦高效的采样算法。为了便于演示，我们在这里专注于估计转换内核。同样的方法也适用于估计奖励函数。

目标是构建原始转移核P的近似 $\hat{P}$ 。我们实现它，是通过构建低维转移概率 \lbrace \hat{P}_k | k \in [K_{\mahtcal{w}}] 的近似 ，然后计算 $\hat{P}$ 根据下式：

$$\hat{P}(s'|x) = \prod_{k=1}^{K_{\mathcal{w}}}\hat{P}(s'[Z_k^S]|x[Z_k^P]) \tag{3}$$

对于所有 $s'\in S$ 和 $x = (s,a) \in S\times A$ 。这种情况，不是从全局状态动作空间采样，我们仅需要从子状态-子动作空间采样。为了评估 $\hat{P}_k(s'[Z_k^S]|x[Z_k^P])$ ，对于任意 $k \in [K_{\mathcal{w}}]$ ，设 $X_k^P$ 定义为 $X_k^P = \lbrace x\in \mathcal{X} | x[-Z_k^P] = x^{default}[-Z_k^P]\rbrace$ ，其中 $x^{default} \in \mathcal{X}$ 是来自 $\mathcal{X}$ 的任意（但固定）元素。从 $X_k^P$ 采样允许我们估计第k个因子化组分的转移核。重要的是，虽然从 $X_k$ 中采样，我们设置 $x[-Z_k^P]$ 为 $x^{default}[-Z_k^P]$ ，因此不需要覆盖余下的状态动作空间。对于每个 $x \in X_k^P$ ，我们采样N次下一状态，产生一组样本 $\lbrace s_{x,i}^k\rbrace_{i\in[N]}$ 。低维经验转移核 $\hat{P}_k$ 然后计算为：

$$\hat{P}_k(s'[Z_k^S] | x[Z_k^P]) = \frac{1}{N} \sum_{i=1}^N 1(s_{x,i}^k[Z_k^S] = s'[Z_k^S]), \quad\forall s'[Z_k^S] \in S[Z_k^S], x\in X_k^P\,. \tag{4}$$

转移核 $\hat{P}$ 的整体估计然后可以使用方程（3）计算。使用这种方式，需要的样本总数是 $\sum_{k=1}^{K_{\mathcal{w}}}|\mathcal{X}[Z_k^P]|N$ 。由于每个组分的子状态-子动作空间的大小的和，即 $\sum_{k=1}^{K_{\mathcal{W}}}|\mathcal{X}[Z_k^P]|$ ，通常非常小（特别低，指数性较小），相较于整体状态-动作空间 |S||A| 的大小 ，需要的样本数明显比经典的基于模型的RL所需要的少。

同步采样特性

上述所述的采样方法可以进一步优化用于改进样本效率，通过利用因子分解方案的结构。先前，我们仅使用样本 $\lbrace s_{x,i}^k\rbrace_{i\in[N]}$ 去构造组分k的估计器 $\hat{P}_k(s'[Z_k^S]|x[Z_k^P])$ 。然而，这些样本可能会被重用来估计其他低维转移核，这取决于它们相关作用域之间的关系。为了将这一想法形式化，我们引入了两种关键策略，利用组分作用域集之间的关系。

具有包含作用域的同步采样 对于任意 $k_1,k_2 \in [K_{\mathcal{w}}]$ 使得 $Z_{k_1}^P \subseteq Z_{k_2}^P$ ，用于估计组分 $k_2$ 的转移核的样本可以重用于估计组分 $k_1$ 。具体地，考虑组分 $k_2$ 的采样集 $X_{k_2}^P = \lbrace x\in\mathcal{X} | x[-Z_{k_2}^P] = x^{default}[-Z_{k_2}^P]$ ，其中 $x^{defualt}[-Z_{k_2}^P]$ 是来自 $\mathcal{X}[-Z_{k_2}^P]$ 的固定的任意元素。通过从每个 $x\in X_{k_2}^P$ 中采样，我们得到下一个状态的样本 $\lbrace s_{x,i}^{k_2}\rbrace_{i\in[N]}$ 。由于 $X_{k_1}^P \subseteq Z_{k_2}^P$ ，这些样本固有地包含组分 $k_1$ 转移的信息。因此，我们可以使用同样的样本，根据方程（4），在 $k = k_1$ 时，估计组分 $k_1$ 的转移概率，其中 采样集 $X_{k_1}^P$ 基于 $X_{k_1}^P$ 定义为：

$$X_{k_1}^P = \lbrace x\in X_{k_2}^P | x[Z_{k_2}^P \ Z_{k_1}^P] = x^{default}[Z_{k_2}^P \ Z_{k_1}^P]\rbrace \,.$$

这里样本的重用改进了整体样本效率，通过避免为组分 $k_1$ 再次采样。

具有专有作用域的同步采样 对于任意 $k_1,k_2 \in [K_{\mathcal{w}}]$ 使得它们的相关作用域不相交，即， $Z_{k_1}^P \cap Z_{k_2}^P = \emptyset$ ，我们可以使用共享样本同时估计两个组分的转移。具体地，定义联合采样集 $X_{k_1,k_2}^P$ 为：

$$X_{k_1,k_2}^P = \lbrace (x[Z_{k_1}^P]_{(i\; mod |\mathcal{X}[Z_{k_1}^P]|+1)},x[Z_{k_2}^P]_{(i\; mod |\mathcal{X}[Z_{k_2}^P|+1),x^{defaulkt}[-(Z_{k_1}^P \cup Z_{k_2}^P)]}) | i \in [D_{max}]\rbrace\,, \tag{5}$$

其中， $D_{max} = max(|\mathcal{X}[Z_{k_1}^P]|, |\mathcal{X}[Z_{k_2}^P]|)$ ， $x[Z_{k_1}^P]$ 表示规定顺序 $\mathcal{X}[Z_{k_1}^P]$ 中第i个元素。模运算确保我们循环遍历每个组件状态动作空间的所有可能值。通过从每个 $x \in X_{k_1,k_2}^P$ 采样N次，我们得到样本 $\lbrace s_{x,i} \rbrace_{i=1}^N$ ，用于根据方程（4）来估计两个组分的转移概率。图2展示具有专用作用域的同步采样示例。这种策略相较于独立地采样每个组分，通过减少需要的样本总数量改进样本效率。

最优成本同步采样策略

基于前面两个关键策略，我们接下来展示我们的采样方法。回顾，我们有 $K_{\mathcal{W}}$ 个组分，与作用域集 $Z_1^P, Z_2^P,...,Z_{K_{\mathcal{w}}}^P$ 相关联。对于每个 $k \in [K_{\mathcal{w}}]$ ，我们定义其对应的采样成本为作用域集 $\mathcal{X}[Z_k^P]$ 的大小。使用包含作用域属性，我们首先忽略作用域集时其他子集的组分。令 $\mathcal{K}_{\mathcal{w}}^{\star}$ 表示剩余组分的集合:

$$\mathcal{K}_{\mathcal{w}}^{\star} = \lbrace k \in [K_{\mathcal{w}}] | \not\exist k_1 \ne k \quad\text{such that}\quad Z_k^P \not\subseteq Z_{k_1}^P\rbrace.$$

接着，为了使用专有作用域特性，我们分解 $\mathcal{K}_{\mathcal{w}}^{\star}$ 到子集 $\lbrace\mathcal{G}_i\rbrace_{1\le i \le k_p}$ （其中， $\mathcal{K}_{\mathcal{p}}$ 表示子集总数）使得每个子集 $\mathcal{G}_i$ 中，组分有不相交的作用域，即 $Z_{k_1}^P \cap Z_{k_2}^P = \emptyset$ ，对于所有 $k_1, k_2 \in \mathcal{G}_i$ 。这使得我们在每个自己内应用具有独有作用域的同步策略。具体地，对于 $\mathcal{K}_{\mathcal{w}}^{\star}$ 每个子集 $\mathcal{G}_k$ ，我们构建联合采样集，如下：

$$X_{\mathcal{G}_k}^P = \big\lbrace \lbrace x[Z_j^P]_{(i \; mod \; |\mathcal{X}[Z_j^P]|+1)} \rbrace_{j\in\mathcal{G}_k},x^{default}[-(\cup_{j\in\mathcal{G}_k}Z_j^P)] | i \in [D_{max,k}] \big\rbrace,$$

其中， $D_{max,k} = max_{j\in\mathcal{G}_k}|\mathcal{X}[Z_j^P]|$ 确保与该集合相关的所有作用域集被采样。因此，采样一个联合采样集的成本由组中最大的作用域集决定：

$$c_k(\mathcal{G}_k) = D_{max,k} = \underset{j\in\mathcal{G}_k}{max}|\mathcal{X}[Z_j^P]|.$$

我们的目标时最小化所有组中的总采样成本：

$$\underset{K_p}{min}\underset{\mathcal{G}_1,...,G_{K_P}}{min}\sum_{k=1}^{K_p} c_k(\mathcal{G}_k).$$

这个问题与图着色问题（GCP）密切相关（Jensen和Toft，2011；Karp，2010）。在附录E中，我们详细阐述了成本最优采样问题与GCP之间的联系，并提供了其计算复杂性的证明。由于这种联系，在实践中有大量成熟的算法可以有效地解决这个问题。该解给出了组 $\mathcal{K}_p \in [K_{\mathcal{w}}]$ 的最佳数量和分割方案 $\lbrace \mathcal{G}\rbrace_{k\in[K_p]}$ 。值得注意的是，$K_p$ 对应于GCP中的色数（Erdos和Hajnal，1966）（所需的最小颜色数）。现有文献表明，在温和条件下，色数通常远小于图中的节点数（Khot，2001；Sopena，1997；Goddard和Xu，2012）。在我们的背景下，这一结果转化为 $\mathcal{K}_p \ll K_{\mathcal{w}}$ ，从而大大降低了采样成本。关于 $\mathcal{K}_p$ 的更深入讨论，请参阅第5.2节。

基于同步采样的MDP模型估计

给定 $\lbrace \mathcal{G}_k\rbrace_{k \in [K_p]}$ 和联合采样集 \lbrace X_{\mathcal{G}k}^P\rbrace{k\in[K_p]}$ ，我们开始采样并估计转移核。