Overcoming the curse of dimensionality in dynamic programming by tensor decompositions

大约60年前，理查德·贝尔曼（Richard Bellman）在提到通过动态规划（DP）解决多阶段决策过程所带来的压倒性计算复杂性时，创造了“维度诅咒”这一表达，从而导致了著名的贝尔曼方程。如今，维数诅咒已经成为数值分析、压缩感知和机器学习等不同领域共享的普遍表达。然而，在动态系统控制的最优反馈律的计算中，其意义仍然是最明显的。考虑一个简单的钟摆，它的特征是两个变量，质量的位置和速度。一个经典的证明是通过自适应移动基座使钟摆稳定在不稳定的向上位置。为了合成对随机波动（例如来自空气）具有鲁棒性的基座执行器的控制信号，需要计算一个反馈映射，作为位置和速度的二维函数。该反馈映射满足二维偏微分方程（PDE），该方程一般没有解析解。用数值方法求解它需要用n个点对位置和速度进行离散化。然而，反馈映射中的未知数总数为n^2，对应于位置点和速度点的所有组合，因此计算时间较长。对于d个变量，直接数值解的复杂性以n^d呈指数增长。即使是一个简单的四旋翼飞行器模型也由12个变量来描述，而在粒子物理学或观点动力学中的现代应用需要对动力系统进行最优控制，而动力系统又是由数百或数千个变量离散的偏微分方程。然而，这样的系统通常非常特殊，因为每个变量仅由动力学中的邻近变量有效地驱动。在这种情况下，所寻求的反馈映射允许（几乎）分离变量的张量近似。这使我们能够显著地降低计算复杂性，尽管以引入一些错误为代价，但许多操作仅随着变量的数量呈多项式增长。这个错误可以通过使用强化学习的方法来进一步纠正，类似于那些让人工围棋选手获胜的方法。

Almost 60 years ago Richard Bellman coined the expression ``curse of dimensionality'' when referring to the overwhelming computational complexity associated with the solution of multi-stage decision processes through dynamic programming (DP), leading to the well-known Bellman equation.Nowadays the curse of dimensionality has become an ubiquitous expression shared in different fields such as numerical analysis, compressed sensing and machine learning. However, it is in the computation of optimal feedback laws for the control of dynamical systems where its meaning continues to be most evident.Consider a simple pendulum, which is characterised by two variables, the position of the mass, and its velocity.A classical demonstration is the stabilisation of the pendulum in the unstable upwards position by moving the base adaptively.To synthesize the control signal for the actuator of the base that would be robust to stochastic fluctuations (e.g. from the air),one needs to compute a feedback map as a two-dimensional function of the position and velocity.This feedback map satisfies the two-dimensional partial differential equation (PDE), which has no analytic solution in general.Solving it numerically requires a discretisation of both the position and velocity with some n points.However, the total number of unknowns in the feedback map is n^2, corresponding to all combinations of the position and velocity points,and therefore the computations take longer.For d variables, the complexity of the straightforward numerical solutions grows exponentially as n^d.Even a simple quadrocopter model is described by 12 variables, and modern applications in particle physics or opinion dynamics require optimal control of dynamical systems, which are in turn PDEs, discretised with hundreds or thousands of variables.However, such systems are often very special in the sense that each variable is driven effectively by only neighbouring variables in the dynamics.In this case, the sought feedback map admits a tensor approximation with (almost) separated variables.This allows us to reduce the computational complexity dramatically, to a number of operations growing only polynomially with the number of variables, albeit at a price of introducing some error.This error can be further corrected by using methods from reinforcement learning, similar to those that made the winning artificial Go player.