一个聚合近似动态规划中的误差界限-计算机科学-机器学习-动态规划.pdf

一个聚合近似动态规划中的误差界限∗

YuchaoLiandDimitriBertsekas

2025年7月

本摘要

译我们考虑一个针对折扣有限状态无限时间动态规划（DP）问题的通用聚

中合框架。它定义了一个聚合问题，其最优成本函数可以通过离线精确DP获

得，然后作为在线强化学习（RL）方案中的终端成本近似值使用。我们推导出

1

v聚合问题与原问题之间最优成本函数误差的一个界。该界最初由Tsitsiklis

4和vanRoy[TvR96]对于硬聚合同一类问题得出。我们的界限与此类似，但

2应用范围广泛得多，包括软聚合和基于特征的聚合方案。

3

1

0

7.1聚合框架

0

5

2我们将重点研究具有标准折扣无限时间范围的马尔可夫决策问题，该

:问题包含个状态。状态及其后续状态将分别用和表示。状态

v

i转换在控制下根据转移概率在离散时间发生，并在阶段生

x

r

a成成本，其中是折扣因子。

我们考虑确定性平稳策略，使得对于每个，是属于有限约束集

的一个控制。我们用表示从状态开始经过无限阶段的的总折

现期望成本，用表示所有中的最小值，并且用和表示

具有分量以及,的维向量。

我们首先考虑在第二作者的2012年教材中首次描述的一般聚合框架

[Ber12]（参见图1），这遵循了之前更专业化的框架。特别是，我们引入了

一个有限子集的集合状态，并用诸如和等符号表示，同时还包括以

下两种概率分布类型：

∗本工作在亚利桑那州立大学坦佩分校富尔顿计算与增强智能学院完成。

1

(a)对于每个聚合状态，在上的概率分布，用

表示，并称为分解概率为。

(b)对于每个原始系统状态，在上的概率分布，表示为

并称为聚集概率的。

聚合和分解概率可以视为我们聚合架构的参数。连同聚合状态集，它

们定义了一个动态规划问题，称为{聚合问题。在这个动态规划问题中，相

应的动态系统包括原始状态空间的两个副本以及聚合状态，转移

和相关成本如图1所示。特别是，在聚合问题中的单次转移从一个聚合状态

开始，涉及三个阶段并最终到达另一个聚合状态，如下所示：

(i)从聚合状态，我们根据生成一个无成本转换到原始系统状态。

(ii)我们根据生成原始系统状态和之间的转换，成本为。

（iii）从原始系统状态，我们生成一个无成本的转换到聚合状态，根据

。

我们引入聚合问题的最优成本向量