Overcoming the curse of dimensionality in dynamic programming by tensor decompositions

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

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.