Skip to content
返回搜索结果

多目标动态规划——序贯决策中的帕累托最优策略

提出者
Extension of Bellman (1957); formalized by multiple authors from 1970s onward
年份
1957-1975
类型
Exact optimization — recursive multi-objective decomposition
类别
Simulation / optimization

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

多目标动态规划(MODP)将经典的贝尔曼动态规划扩展到决策者需要在多个阶段同时优化几个相互竞争的目标的场景。它不产生单一的最优策略,而是产生一个帕累托最优策略集——每个策略代表一个独特的权衡剖面——通过将向量值函数向后传播通过状态空间。

方法背后的直觉

在单目标动态规划中,每个状态带有一个最优值和一个最优动作。多目标动态规划通过在每个状态存储一组非支配的累积奖励向量的帕累托前沿来推广这一概念。当算法向后遍历决策阶段时,它会合并和修剪这些帕累托集,以便只有真正非支配的策略能够存活到最后阶段。结果不是单一的答案,而是一个完整的权衡曲面,决策者可以从中选择最符合其偏好的策略,而无需预先指定权重。

历史学

多目标动态规划建立在理查德·贝尔曼于 1957 年发表的基础性动态规划框架之上。通过运筹学文献在 20 世纪 70 年代和 80 年代出现了向量目标扩展,这得益于在水资源管理、军事规划和经济政策中的应用。该领域随着多目标优化理论的发展而成熟,关键贡献包括形式化帕累托值函数递归和修剪算法。它仍然是一个活跃的研究领域,特别是在具有多个奖励信号的马尔可夫决策过程的背景下。

何时使用

当决策在多个序贯阶段展开时,当至少有两个目标发生冲突时,以及当状态和动作空间足够小可以枚举或离散化时,使用 MODP。它非常适合于时间资源分配、多阶段项目调度以及序贯健康或环境政策评估,这些场景需要帕累托完整的解决方案。当状态空间非常大时(维度灾难使得精确帕累托前沿计算不可行),当目标可以很容易地在分析前合并为单个标量时,或者当问题结构是非马尔可夫的时(未来奖励取决于当前状态之外的历史),不要使用。

局限与注意事项

  • 严重受维度灾难的影响:计算成本和内存随状态变量和目标的数量呈指数增长。
  • 需要离散或离散化的状态空间,这可能为连续问题引入近似误差。
  • 每个状态存储的非支配策略数量可能非常大,使得精确方法对于具有三个或四个以上目标的问题不切实际。
  • 假设马尔可夫性质——最优未来动作仅取决于当前状态,而不取决于过去决策的历史。
  • 实现比单目标动态规划复杂得多,需要在每个状态进行有效的帕累托支配检查和集合管理。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 提供完整的帕累托最优策略集,使决策者能够全面了解目标权衡,而无需强制提前指定权重。
  • 保证模型内的精确帕累托最优性——对于可处理规模的问题,没有启发式近似。
  • 自然地处理序贯和分阶段的决策结构,而大多数其他多目标方法需要人工重构问题。
  • 将优化阶段与偏好获取阶段分开,允许在计算出前沿后应用利益相关者的偏好。
  • 自然地扩展到随机设置,通过在每个状态存储期望向量值的帕累托集。

应用

  • 多阶段水库管理同时平衡防洪、灌溉供水和水力发电。
  • 序贯癌症治疗计划,在治疗周期中优化肿瘤控制、毒性和生活质量。
  • 多周期投资组合优化,在投资视野中平衡回报、风险和流动性限制。
  • 环境政策评估,针对必须在经济成本、碳减排和生物多样性影响之间进行权衡的政策。
  • 物流网络中的多目标路由和调度,具有相互竞争的成本、时间和可靠性目标。
  • 研发项目组合中的序贯资源分配,平衡预算效率、创新潜力和上市时间。

使用方式

使用方式

1

定义多阶段决策问题:一组阶段 t = 1, ..., T,一个状态空间 S,一个动作空间 A,一个转移函数,以及一个向量奖励函数 r(s, a) = (r1, r2, ..., rk),其中 k 个目标。在此阶段不需要标量权重。

2

枚举或离散化状态空间。对于阶段 T 的每个终端状态,将帕累托集初始化为包含终端奖励向量的单例集。这些边界值锚定了向后递归。

3

在每个状态 s 和阶段 t,将向量值函数 V(s, t) 定义为从 (s, t) 到终端阶段可达的所有非支配累积奖励向量的集合。用帕累托非支配性取代标量贝尔曼最优性:如果向量 v 在每个目标上至少一样好,并且在至少一个目标上严格更好,则称 v 支配 v'。

4

从阶段 T 向后扫描到阶段 1。在每个 (s, t),通过将即时奖励 r(s, a) 与后继状态 s' 的 V(s', t+1) 中的每个元素结合,为每个可行动作 a 计算候选向量值。对所有动作取并集并修剪支配向量,只保留 V(s, t) 的帕累托前沿。

5

在初始状态下,V(s0, 1) 包含帕累托最优累积奖励向量的完整集合。每个向量对应一个独特的策略。将此帕累托前沿呈现给决策者,决策者可以根据其优先级选择首选策略,或事后应用标量化(例如,加权和)。

常见陷阱

  • 将多目标 DP 与简单地为每个目标分别运行动态规划混淆——该方法会错过帕累托前沿的非凸区域。
  • 在应用该方法之前,未能验证状态空间是否真正是马尔可夫的——隐藏的状态变量将使递归无效。
  • 低估每个状态下帕累托集的大小,导致具有多个目标或长视野的问题出现内存耗尽。
  • 将 MODP 应用于连续或高维状态空间而不采用具有收敛保证的近似方案,产生不可靠的结果。
  • 将完整的帕累托前沿呈现给决策者,而没有支持偏好获取的工具,使他们因过多的策略选项而不知所措。

常见问题

多目标动态规划与简单地为每个目标分别运行动态规划有何不同?

分别运行每个目标的 DP 会产生单独的单目标最优解,这些解通常无法同时实现,并且完全错过了权衡结构。MODP 将向量值帕累托集通过状态空间传播,捕获了任何单一策略可实现的目标值的所有非支配组合——包括加权和方法无法找到的帕累托前沿中的解。

维度灾难何时使 MODP 不切实际?

当状态空间具有超过少数几个离散变量时,当规划视野非常长时,或者当目标数量超过三个或四个时(导致每个状态的帕累托前沿呈指数增长),MODP 会变得难以处理。在这种情况下,通常首选近似方法,如多目标强化学习或启发式帕累托搜索。

MODP 能处理转移或奖励中的不确定性吗?

是的。在随机设置中,向量值函数存储期望的帕累托最优奖励向量,这些向量是通过对后继状态的概率加权求和计算得出的。这自然地扩展到多目标马尔可夫决策过程(MOMDP),尽管随机性会进一步增加计算需求。

我需要在运行 MODP 之前指定目标权重吗?

否——这是 MODP 的关键优势之一。在优化阶段不需要权重或偏好信息。算法计算完整的帕累托前沿,决策者之后应用其偏好来选择特定的策略。

MODP 输出什么,应该如何解释?

MODP 输出一组帕累托最优策略,每个策略都与一组累积目标值向量相关联。没有单一策略在所有目标上都支配所有其他策略。决策者检查此前沿以识别符合其优先级排序的策略,通常借助散点图或目标向量的平行坐标图等可视化工具。

相关方法

参考文献

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.

    ISBN:9780691079516
    已复制。
  2. Daellenbach, H. G., & Flood, R. L. (1992). Multi-objective dynamic programming. European Journal of Operational Research, 56(2), 215-225.

    打开出版物文献
    已复制。