Approximating the Stationary Bellman Equation by Hierarchical Tensor Products

Mathias Oster, Leon Sallandt, Reinhold SchneiderJournal of Computational Mathematics 2019

Abstract

We treat infinite horizon optimal control problems by solving the associated stationary Hamilton-Jacobi-Bellman (HJB) equation numerically to compute the value function and an optimal feedback law. The dynamical systems under consideration are spatial discretizations of non linear parabolic partial differential equations (PDE), which means that the HJB is non linear and suffers from the curse of dimensionality. Its non linearity is handled by the Policy Iteration algorithm, where the problem is reduced to a sequence of linear, hyperbolic PDEs. These equations remain the computational bottleneck due to their high dimensions. By the method of characteristics these linearized HJB equations can be reformulated via the Koopman operator in the spirit of dynamic programming. The resulting operator equations are solved using a minimal residual method. To overcome numerical infeasability we use low rank hierarchical tensor product approximation/tree-based tensor formats, in particular tensor trains (TT tensors), and multi-polynomials, together with high dimensional quadrature, e.g. Monte-Carlo. By controlling a destabilized version of viscous Burgers and a diffusion equation with unstable reaction term numerical evidences are given.

Introduction

In optimal control, the objective is to determine a feedback law that guides a system to minimize a long-term cost. This typically involves solving the Hamilton-Jacobi-Bellman (HJB) equation to obtain the value function—the minimum cost-to-go from any given state. However, solving the HJB equation for high-dimensional systems, such as those derived from discretized partial differential equations (PDEs), is hindered by two major obstacles: nonlinearity and the "curse of dimensionality." Traditional grid-based methods fail as dimensions increase, necessitating new approaches that exploit underlying structural simplicity for compression.

Methodology

The proposed framework addresses these challenges through a multi-stage pipeline combining iterative linearization, operator theory, and tensor-based compression.

Approximative Policy Iteration

The nonlinear HJB equation is decomposed into a sequence of linear "Bellman-type" equations using Policy Iteration. Starting from an initial control guess, the algorithm iteratively evaluates the current policy and improves it.

Algorithm 2: Approximative Policy Iteration

Koopman Operator and Tensor Trains

Instead of tracking state evolution directly, the authors utilize the Koopman operator to observe the evolution of functions of the state. This reformulates the problem into a linear operator equation solvable via trajectories. To manage the high dimensionality, the value function $v(x)$ is represented using Tensor Trains (TT). This format represents the function as a chain of small, low-rank tensors, reducing storage requirements from exponential ($n^d$) to linear ($d \cdot n \cdot r^2$) with respect to dimension $d$.

Tensor Train representation of the value function v(x) using basis functions

Variational Monte-Carlo (VMC)

To avoid high-dimensional integration, the method employs Monte-Carlo sampling. The residual of the Bellman equation is minimized at specific sample points using an Alternating Least-Squares (ALS) algorithm, which optimizes the tensor chain one core at a time.

Experimental Results

The method was evaluated on two 32-dimensional physical benchmarks: a diffusion equation with an unstable reaction term and a viscous Burgers'-like equation.

Performance and Efficiency

In the 32D diffusion test, the TT-based controller demonstrated significant efficiency, saving approximately 50% of the cost compared to a standard Linear Quadratic Regulator (LQR). The computed value functions were highly accurate, with the Bellman residual dropping significantly throughout the Policy Iteration process.

Robustness and Compression

The proposed approach showed superior robustness; while the LQR controller failed to stabilize the system for 44.3% of random initial states, the H1-regularized TT controller achieved a 100% stabilization rate. Furthermore, the TT format successfully bypassed the curse of dimensionality, representing the 32-dimensional function with only ~5,400 parameters—a massive reduction from the $5^{32}$ points required by a full grid.

Conclusion

This work demonstrates that combining Policy Iteration with Tensor Train approximations effectively bypasses the curse of dimensionality for complex control problems. The use of the Koopman operator suggests potential for model-free applications where only system trajectories are available. Future research will focus on automated rank selection for the tensor formats and extending the framework to stochastic systems.

Reference: Oster, M., Sallandt, L., & Schneider, R. (2021). Approximating the Stationary Bellman Equation by Hierarchical Tensor Products. arXiv:1911.00279v4 [math.OC].

Summary updated

Abstract

We treat infinite horizon optimal control problems by solving the associated stationary Bellman equation numerically to compute the value function and an optimal feedback law. The dynamical systems under consideration are spatial discretizations of non linear parabolic partial differential equations (PDE), which means that the Bellman equation suffers from the curse of dimensionality. Its non linearity is handled by the Policy Iteration algorithm, where the problem is reduced to a sequence of linear equations, which remain the computational bottleneck due to their high dimensions. We reformulate the linearized Bellman equations via the Koopman operator into an operator equation, that is solved using a minimal residual method. Using the Koopman operator we identify a preconditioner for operator equation, which deems essential in our numerical tests. To overcome computational infeasability we use low rank hierarchical tensor product approximation/tree-based tensor formats, in particular tensor trains (TT tensors) and multi-polynomials, together with high-dimensional quadrature, e.g. Monte-Carlo. By controlling a destabilized version of viscous Burgers and a diffusion equation with unstable reaction term numerical evidence is given.
BibTeX
@article{oster2019approximating,
  author = {Mathias Oster and Leon Sallandt and Reinhold Schneider},
  title = {{Approximating the Stationary Bellman Equation by Hierarchical Tensor Products}},
  journal = {Journal of Computational Mathematics},
  year = {2019},
}
Figure