自适应动态规划（编程）

自适应动态规划是寻找随机过程中的最优（或近乎最优）控制策略以评估随机过程，与普通的动态规划不同的是，自适应动态规划里随机过程中的奖励（reward）和转换（transition）依赖于未知的参数。 自适应动态规划问题可以使用长期平均估值（long run average）和渐近折扣总值（asymptotic discounted total value）来评估计算，属于马尔可夫决策过程家族的一员。

自适应动态规划，简单地说就是将最新的信息纳入决策过程。例如一个卖鞋的小商店老板可通过自适应动态规划算法来实现库存管理，商店老板每个星期结束后会统计商店卖出的鞋子以及剩余的鞋子数量，然后根据自己对未来需求的了解和评估来决定新鞋的订购量。这里，鞋子订单的大小可以通过使用动态规划的模型和方法来计算。但在接下来的几周，他对未来的需求和价格的预测和评估可能会发生变化，因此，他对鞋子的定价、订购量等都可能发生改变。这种类型的行为，即将最新的信息纳入决策，称为自适应。不考虑自适应（adaptive）这个特征，上述店主的行为是一个马尔可夫决策过程，也称为随机动态规划（stochastic dynamic programming）；而附加特征称为自适应，其中决策者（店主）并不完全知道影响当前回报和未来发展的一些参数。因此，决策情况会根据对这些参数的认识而改变。决策者的目标是对未知参数进行估计并改进，找到一个最佳策略可以最大化他的长期预期回报。

来源：

Wikipedia: https://en.wikipedia.org/wiki/Dynamic_programming

URL: https://www.eolss.net/sample-chapters/C02/E6-05-05-07.pdf

发展历史

1973年， Bernard Widrow等提出了一种通过惩罚和奖励来调整学习的方法。这种方法不同于监督学习和非监督学习，它有一个校正（critic）来指导学习，好的动作给奖励（reward），坏的动作给惩罚（punishment），所以也叫Learning with a Critic 或者Bootstrap Adaptation Learning。

图片来源：

Wikipedia: Wang, F. Y., Zhang, H., & Liu, D. (2009). Adaptive dynamic programming: An introduction. IEEE computational intelligence magazine, 4(2).

1977年，Paul Werbos介绍了一种求解自适应动态规划的方法，该方法后来被称为自适应校正设计（Adaptive Critic Designs）。自适应校正设计有许多同义词，包括近似动态规划（Approximate Dynamic Programming），渐近的动态规划（Asymptotic Dynamic Programming），自适应动态规划（Adaptive Dynamic Programming），启发式动态规划（Heuristic Dynamic Programming），神经动态规划（Neuro-Dynamic Programming）和强化学习（Reinforcement Learning）。

1992年，Paul Werbos给出了自适应动态规划算法的计算复杂度分析，提出了启发式动态规划（Heuristic Dynamic Programming）和双启发式规划（Dual Heuristic Programming）两个自适应动态规划方法。

1996年，Bertsekas和Tsitsiklis发表了Neuro-dynamic programming论文，详细介绍了神经动态规划算法的概况。

1997年，Prokhorov等发表了Adaptive critic designs一文，介绍了一系列用于神经控制的自适应设计方法。

近些年，自适应动态规划被广泛应用于寻找最优策略，结合强化学习、值函数估计（value function approximation）等最新方法，可以稳定收敛于最优解。

主要事件

发展分析

瓶颈

和动态规划类似，对于大规模的状态空间，自适应动态规划算法是不适应的。

未来发展方向

自适应动态规划结合强化学习、深度学习等最新技术，运用于最优控制，可提高最优策略的学习效率，增强算法的稳定性和健壮性。

Contributor: Yufeng Xiong