PDP: Parallel Dynamic Programming
PDP：并行动态规划

Ⅰ. INTRODUCTION   I.. 引言

Google DeepMind’s deep reinforcement learning based AlphaGo computer program [1] won the historic Go match against world champion Lee Sedol in March 2016. The combination of Monte-Carlo tree search and deep reinforcement learning makes a breakthrough at Go playing which is believed impossible with brute-force search, and brings artificial intelligence a focus for the year. Most people pay more attention to the intuitive highly brain-like deep learning technologies. However, the other key to AlphaGo’s success, the Principle of Optimality for dynamic programming, has been taken for reinforcement learning (RL). As a matter of fact, dynamic programming plays a very important role in modern reinforcement learning. The victory of AlphaGo is actually also the victory of dynamic programming.
2016 年 3 月，Google DeepMind 基于深度强化学习的 AlphaGo 计算机程序 [1] 赢得了与世界冠军李世石的历史性围棋比赛。蒙特卡洛树搜索和深度强化学习的结合在围棋下法上取得了突破，这被认为在蛮力搜索中是不可能的，并将人工智能作为今年的重点。大多数人更关注直观、高度类脑的深度学习技术。然而，AlphaGo 成功的另一个关键，即动态规划的最优性原则，已被用于强化学习 （RL）。事实上，动态规划在现代强化学习中起着非常重要的作用。AlphaGo 的胜利，其实也是动态规划的胜利。

Dynamic programming [2] has become well-known since 1950s in many fields. In 1977, Werbos combined DP, neural networks and reinforcement learning, and introduced approximate/adaptive dynamic programming (ADP) [3], [4] to solve the “curse of dimensionality” [2]. However, trial-and-error based reinforcement learning and deep learning both focus on engineering complexity and ignore the social complexity. In this article, we suggest another extension of dynamic programming considering both engineering and social complexities, aiming the “paradox of scientific methods” in complex system’s “scientific solutions” [5]. We utilizing big data analytics and the ACP approach [6], [7]: arttificial societies for descriptive anlytics, computational experiments for predictive analytics, and parallel execution for prescriptive analytics. We name our approach Parallel Dynamic Programming.
自 1950 年代以来，动态规划 [ 2] 在许多领域都广为人知。1977 年，Werbos 将 DP、神经网络和强化学习相结合，引入了近似/自适应动态规划 （ADP） [ 3]， [ 4] 来解决“维数诅咒” [ 2]。然而，基于试错法的强化学习和深度学习都关注工程复杂性，而忽略了社会复杂性。在本文中，我们提出了动态规划的另一个扩展，同时考虑了工程和社会复杂性，瞄准了复杂系统的“科学解决方案”中的“科学方法的悖论”[ 5]。我们利用大数据分析和 ACP 方法 [ 6]， [ 7]：人工社会进行描述性分析，计算实验进行预测分析，并行执行进行规范性分析。我们将我们的方法命名为 Parallel Dynamic Programming。

This article is organized as follows. The next section reviews dynamic programming and adaptive dynamic programming. Then, we briefly discuss the neural network structure of ADP and AlphaGo. We present the ACP approach of analytics intelligence in Section IV. In Section V, we introduce the basic structure of parallel dynamic programming. The last section concludes the article.
本文的组织结构如下。下一节将回顾动态规划和自适应动态规划。然后，我们简要讨论了 ADP 和 AlphaGo 的神经网络结构。我们在第 IV 节中介绍了分析智能的 ACP 方法。在第 V 节中，我们介绍了并行动态规划的基本结构。最后一部分是本文的结尾。

Ⅱ. FROM DYNAMIC PROGRAMMING TO ADAPTIVE DYNAMIC PROGRAMMING
II.. 从动态规划到自适应动态规划

Dynamic programming (DP) is a very useful tool in solving optimization and optimal control problems [8]-[10]. The dynamic programming technique rests on a very simple idea, the Bellman’s principle of optimality [2]: “An optimal policy has the property that no matter what the previous decision (i.e., controls) have been, the remaining decisions must constitute an optimal policy with regard to the state resulting from those previous decisions.”
动态规划 （DP） 是解决优化和最优控制问题的非常有用的工具 [ 8]-[ 10]。动态规划技术基于一个非常简单的思想，即贝尔曼最优性原则 [ 2]：“最优策略具有这样一个属性，即无论先前的决策（即控制）是什么，其余的决策都必须构成相对于先前决策产生的状态的最优策略。

DP can easily be applied to the optimal control of discretetime nonlinear systems. Let the system be
DP 可以很容易地应用于离散时间非线性系统的最佳控制。让系统成为

$$x_{k+1}=F_k(x_k,u_k),$$

(1)

where x_k, u_k are the state and control, respectively, and F_k(·) is the system function at time k. Suppose we associate with this plant the performance index function
其中 x _k ， u _k 分别是状态和控制，F _k （·） 是时间 k 的系统函数。假设我们将性能指标函数与该工厂相关联

$$J_i(x_i)=\varphi (N,x_N)+\sum _{k=i}^{N-1}{U}_k(x_k,u_k),$$

(2)

where [i, N] is the time interval of interest. According to the Bellman’s principle of optimality, the optimal performance index function, which aims to minimize, satisfies the following equation
其中 [i， N] 是感兴趣的时间间隔。根据 Bellman 的最优性原则，旨在最小化的最优性能指数函数满足以下方程

$$J_k^{\ast }(x_k)=\underset{u_k}{min}\{U_k(x_k,u_k)+J_{k+1}^{\ast }(x_{k+1})\}.$$

(3)

Equation (3) is the Bellman’s optimality equation. Its importance lies in the fact that it allow us to optimize over only one control vector at a time by working backward from N. It is called the functional equation of dynamic programming and is the basis for computer implementation of the Bellman’s method. However, it is often computationally untenable to obtain the optimal control by directly solving the Bellman equation (3) due to the backward numerical process required for its solution, i.e., as a result of the well-known “curse of dimensionality” [2]. We have to find a series of optimal control actions that must be taken in sequence. This sequence will give the optimal performance index, but the total cost of these actions is unknown until the end of that sequence.
方程 （3） 是 Bellman 最优方程。它的重要性在于，它允许我们从 N 开始逆向工作，一次只优化一个控制向量。它被称为动态规划的函数方程，是 Bellman 方法的计算机实现的基础。然而，通过直接求解 Bellman 方程 （3） 来获得最优控制在计算上通常是站不住脚的，因为求解该方程需要反向数值处理，即众所周知的“维数诅咒”的结果 [ 2]。我们必须找到一系列必须按顺序采取的最佳控制措施。此序列将提供最佳性能指数，但在该序列结束之前，这些作的总成本是未知的。

Approximate dynamic programming, proposed by Werbos [3], [4], builds a critic system to circumvent the “curse of dimensionality” by building a system, called “critic” to approximate the cost function in dynamic programming. The main idea of approximate dynamic programming as shown in Fig. 1. There are three parts in the the structure of approximate dynamic programming, which are dynamic system, the critic module, and the action module, respectively. First, the action module outputs a control policy according to the system state. Second, according to the system implementation, the critic module receives a evaluate signal. Third, a reinforcement signal is created by the critic network, which aims to indicate the action module to find a better control policy, at least not worse. The whole implementation is self-learning and the critic and action modules can be regarded as an agent. According to the principle in Fig. 1, the dynamic programming problem is desired to solve forward-time. In [11], [12], the approximate dynamic programming method was implemented, where each part in Fig. 1 was modeled by a neural network and hence is called “Neuro-Dynamic Programming”. Its several synonyms are used, such as “Adaptive Critic Designs” [13], [14], “Asymptotic Dynamic Programming” [15], “Adaptive Dynamic Programming” [16]-[21], and “Neural Dynamic Programming” [22]. In 2006, the synonyms were unified as “Adaptive Dynamic Programming (ADP)” [23]-[36].
由 Werbos [ 3]， [ 4] 提出的近似动态规划，通过构建一个名为“critic”的系统来近似动态规划中的成本函数，从而构建一个 critic 系统来规避“维度的诅咒”。近似动态规划的主要思想如图 1 所示。近似动态规划的结构体有三个部分，分别是 dynamic system、critic 模块和 action 模块。首先，action module 根据系统状态输出一个控制策略。其次，根据系统实现，critic 模块接收到 evaluate 信号。第三，由 critic 网络制造强化信号，旨在指示 action 模块找到更好的控制策略，至少不会更差。整个实现是自学的，critic 和 action 模块可以看作是一个代理。根据图 1 中的原理，需要解决动态规划问题来解决前向时间问题。在 [ 11]、[ 12] 中，实现了近似动态规划方法，其中图 1 中的每个部分都由神经网络建模，因此称为“神经动力学规划”。使用了它的几个同义词，例如“Adaptive Critic Designs” [ 13]、[ 14]、“Asymptotic Dynamic Programming” [ 15]、“Adaptive Dynamic Programming” [ 16]-[ 21] 和“Neural Dynamic Programming” [ 22]。2006 年，同义词统一为“自适应动态规划 （ADP）” [ 23]-[ 36]。

Figure  1.  ADP structure.

DownLoad: Full-Size Img PowerPoint

Ⅲ. NEURAL NETWORK STRUCTURE OF ADP

HDP is the most basic and widely applied structure of ADP [11], [13]. The structure of HDP is shown in Fig. 2. HDP is a method for estimating the performance index function. Estimating the performance index function for a given policy only requires samples from the instantaneous utility function U, while models of the environment and the instantaneous reward are needed to find the performance index function corresponding to the optimal policy.

Figure  2.  The HDP structure diagram.

DownLoad: Full-Size Img PowerPoint

In the HDP structure, the model network aims to describe the dynamic of the system. The action network aims to approximate the control policy of the system, and the critic network aims to approximate the performance index function. If each neural network in HDP is chosen as three-layer back-propagation (BP) network, then the neural network structure of HDP can be expressed as in Fig. 3.

Figure  3.  Deep neural network structure of HDP.

DownLoad: Full-Size Img PowerPoint

In Fig. 3, we can say that we use three BP neural networks to implement the learning of the optimal control. However, if the three neural networks are regarded as one neural network, then we can say that we implement the learning of the optimal control by at least a nine-layer deep BP network [37]. In this point of view, the structure of HDP is a structure of a deep neural network. For all the other structures of ADP [13], such as dual heuristic programming (DHP), global dual heuristic programming (GDHP), and their action-depended versions, the structures can also be transformed into one deep neural network. Thus, the structure of ADP is naturally a deep neural network. The training target of the deep neural network is desired to force the following error

$$e_k=U_k(x_k,u_k)+J_{k+1}(x_{k+1})-J_k(x_k)$$

(4)

to zero. Obviously, the training error e_k can be chosen as the reinforcement signal, which optimizes the control policy to minimize the distance between e_k and the equilibrium point. Hence, the optimization process by ADP is actually a reinforcement learning process via a deep neural network. This is an amazing similar with the implementation of AlphaGo. Earlier works in [38], [39] also provided neural network based control method with knowledge architecture embed.

Ⅳ. ANALYTICS INTELLIGENCE: FROM ACP TO DPP

Reinforcement learning is a computational approach to understanding and automating goal-directed learning and decision-making. During the implementation process of ADP, it is emphasized that reinforcement learning is a key technique to find a better control policy of the system via trial-and-error. However, it should be pointed out that shortcomings inherently exist for the trial-and-error approach. Many real-world control systems cannot be “tried” sufficiently for the fact of security and cost. Particularly, for systems that involve human and societies (Cyber-Phisical-Social systems, CPSS) [40], sometimes the “error” is intolerable. The success of AlphaGo suggests the possibility of conducting reinforcement learning with a virtual Go-game played by two virtual players. However, we do not know the exact rules or dynamic systems in most of our real-world control and management problems as the Go-game.

Data driven parallel systems in cyberspace are the key to solve the trial-and-error challenge. Two founding pioneers of modern management sciences stated famous maxims for operations: W. Edwords Deming, “In God we trust; all others must bring data” and Peter F. Drucker: “The best way to predict the future is to create it”. Our suggestion is to integrate artificial intelligence and analytics [6]: artificial societies (or systems) for descriptive analytics, computational experiments for predictive analytics, and parallel execution for prescriptive analytics. The DPP (descriptive, predictive and prescriptive) analytics intelligence can be built based on the ACP approach as is shown in Fig. 4.

Figure  4.  The ACP approach of descriptive, predictive, and prescriptive analytics.

DownLoad: Full-Size Img PowerPoint

The representation procedure of descriptive models is to speak with data, which generally aims to tell us “what happened in history”, “when did it happen”, and “why did it happen”. However, in real-world cases, people can only collect “small data” for decision making. Before we make a decision, a lot of possible “futures” (“big data” or artificial societies) are created during the analytics based on the collected “small data”. Moreover, “futures” can be “created” by imaging and designing. Hence, in our ACP approach, the descriptive analytics by artificial societies are not only the model of real-world data, but also the model of virtual “predicted future” and “created future” in cyberspace.

Predictive analysis [41]-[43] should be made according to the descriptive model and historical data to predict the future by reasoning. It tells us “what will happen”, “when will it happen, ” and “why will it happen”. In our ACP approach, predictive analytics are conducting computational experiments to predict the future for certain artificial society with certain control and management policy. “Big data” are created in the computational experiments in cyberspace.

Finally, no matter how many possible futures or policies, we can choose only one to implement in our real world. Hence, after the predictive analytics of different policies and different artificial societies, we reduce the “big data”, extract rules, and create the real future through learning and adaption.In our ACP approach, prescriptive analytics are developed to find benefit policy from predictions based on the descriptive models and historical data through parallel execution. Data are collected for further descriptive analytics and predictive analytics during the parallel execution.

Ⅴ. PARALLEL DYNAMIC PROGRAMMING

In the practice of AlphaGo, one of the key ideas is to extract supervised learning policy, and to improve it to get a suboptimal policy during the reinforcement learning procedure. In parallel dynamic programming (PDP), we suggest the ACP approach for decision making in CPSS with analytics intelligence.

The descriptive analytics of parallel dynamic programming are data driven for systems with unknown or imperfect information. We collect state-action-reward-state data from real-world controls and observations, as is shown in Fig. 5. Since the highly complexity of real-world system, and the highly unpredictable of human behaviors, the data are not directly used for fitting the state equations of the dynamic system. On the contrary, in parallel dynamic programming, we focus on how to construct “possible” data consistent with the real-world observations. Combining these virtual data and the historical real-world data, we can build the artificial systems parallelized to the real-world system. The data driven virtual systems model the state equations of the artificial world, and the objectives of agents. An artificial system in PDP indicates feasibility and possibility, instead of similarity.

Figure  5.  Parallel dynamic programming with three parallel systems.

DownLoad: Full-Size Img PowerPoint

Within each artificial system, the predictive analytics can be viewed as optimal control problems with known dynamics in PDP. Hence, assume we have n-artificial systems (n=3 in Fig. 5) parallelized with the real-world system, we can employ dynamic programming or adaptive dynamic programming to solve the optimal control problems with known state equations in the trial-and-error approach in the virtual parallel system without any cost or risk, and get n optimal (or sub-optimal) decisions. Note that, this procedure is naturally distributed, and previous decisions in real-world can be used as an initial guess in the reinforcement learning iterations to reduce the computation. Then, the computational experiments can be conducted in a bionic manner: based on a voting mechanism n-virtual systems will vote for the n-decisions. Hence, we can get a winning decision and its corresponding critic network. Note that, the computational experiments search for an acceptable artificial system and an admissible decision, rather than the optimal control.

The parallel execution will based on the optimality principle of dynamic programming, and the critic network selected in the computational experiments. We adjust the decision according to the winning critic network and the observed real-world state. The virtual-real system interaction can be conducted by observing states and errors, updating the artificial systems and adjusting the voting mechanism.

The detailed implementation of the PDP algorithm for unknown discrete systems has been conducted and the result is very interesting and promising [44], more works are undertaking and will be reported.

Ⅵ. REMARK AND CONCLUSION

“Scientific solutions” need to satisfy two conditions: triable and repeatable [6]. In real-world systems that involves human and societies, the trial-and-error based reinforcement learning can not be conducted unless we already know the “error” will be harmless. On the other hand, the suggested parallel dynamic programming conduct computational experiments in virtual systems with the idea of optimality principle. Unlike the game of AlphaGo, PDP is based on parallel systems [45], [46] instead of the exact rules of real-world systems, and will be more flexible and feasible for complex problems.