Optimal bounds for numerical approximations of infinite horizon problems based on dynamic programming approach

Technical Summary: Optimal Bounds for Numerical Approximations of Infinite Horizon Problems Based on Dynamic Programming Approach

Problem Statement
The paper addresses the numerical approximation of infinite horizon optimal control problems driven by dynamical systems in $\mathbb{R}^n$. The value function for such problems is characterized as the viscosity solution of a first-order nonlinear Hamilton-Jacobi-Bellman (HJB) partial differential equation. While various approximation schemes exist (finite differences, semi-Lagrangian, finite volume), a significant challenge remains in establishing rigorous error bounds for fully discrete methods that include both time and spatial discretization.

Existing literature, specifically referencing works by Falcone and Ferretti [12] and others [9, 11], establishes an error bound of size $O(k/h)$ for fully discrete semi-Lagrangian methods, where $h$ is the time step and $k$ is the spatial mesh size. This bound suggests that as the time step $h$ decreases, the error deteriorates due to the $1/h$ factor. However, the authors note that numerical experiments in the literature (e.g., [4]) do not observe this $1/h$ behavior, suggesting the theoretical bound is suboptimal. The paper aims to resolve this discrepancy by revising the error analysis to prove a tighter bound.

Methodology
The authors propose a new characterization of the fully discrete approximation to derive improved error bounds. The methodology proceeds as follows:

1. Reformulation via Cost Functionals: Instead of relying solely on the standard dynamic programming principle, the authors define a fully discrete cost functional $\hat{J}_{h,k}$. This functional utilizes a linear interpolant operator $I_k$ applied to the system dynamics and running cost at each time step.
2. Characterization of the Solution: Theorem 3 proves that the fully discrete value function $v_{h,k}$ (defined by the discrete dynamic programming equation) is exactly the infimum of this new fully discrete cost functional over the space of admissible control sequences. This mirrors the characterization used for the semi-discrete case in [5].
3. Error Decomposition: The error analysis compares the continuous cost functional $\hat{J}$ with the fully discrete functional $\hat{J}_{h,k}$. The difference is bounded by analyzing the trajectory errors between the continuous system solution $y(t)$ and the discrete interpolated solution $\tilde{y}(t)$, as well as the interpolation errors of the cost and dynamics functions.
4. Regularity Assumptions: The analysis considers different regularity assumptions on the control inputs $u(t)$:
   • Uniformly continuous controls (with a finite number of jump discontinuities).
   • Lipschitz continuous controls.
   • Piecewise constant controls (under a convexity assumption on the set of dynamics/costs).

Key Contributions and Results

• Improved Error Bound: The primary contribution is the proof that the error between the continuous value function $v$ and the fully discrete approximation $v_{h,k}$ is of order $O(h + k)$, rather than the previously cited $O(k/h)$. This establishes first-order convergence in both time and space, consistent with the use of a first-order Euler time discretization and piecewise linear spatial approximation.
• Theorem 4 (General Bound): Under standard Lipschitz assumptions on the system dynamics $f$ and cost $g$, and assuming $\lambda > L$ (where $L$ is a constant derived from the Lipschitz constants), the error is bounded by:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 M_u$$
  where $M_u$ measures the oscillation of the control within time intervals.
• Theorem 6 (Lipschitz Controls): If the controls are Lipschitz continuous, $M_u$ scales with $h$, resulting in the optimal error bound:
  $$|v(y) - v_{h,k}(y)| \leq C(h + k)$$
• Theorem 5 (Uniformly Continuous Controls): If controls are merely uniformly continuous (allowing for a finite number of jumps), the error converges to zero as $h, k \to 0$, though the specific rate depends on the modulus of continuity.
• Piecewise Constant Controls (Theorem 7): Adapting arguments from [6] (originally for finite horizon problems) to the infinite horizon case, the authors prove convergence under a convexity assumption (CA) on the set $\{f(y,u), g(y,u)\}$. However, this adaptation results in a weaker time convergence rate for the infinite horizon case:
  $$|v(y) - v_{h,k}(y)| \leq C_1(h + k) + C_2 (\log h)^2 h^{\frac{1}{1+\beta}}$$
  where $\beta = \frac{\sqrt{n}L_f}{\lambda}$. The authors note this represents a loss of at most half an order in time convergence compared to the finite horizon case, attributed to the infinite time horizon.

Significance and Claims
The paper claims that the new characterization based on optimality arguments successfully explains the numerical behavior observed in practice, where the $1/h$ deterioration predicted by older bounds is not seen. By proving the $O(h+k)$ bound, the authors confirm that the fully discrete semi-Lagrangian method achieves first-order convergence in both time and space under standard regularity assumptions.

The authors modestly suggest that this new characterization, rooted in optimality arguments, holds potential for application to other types of Hamilton-Jacobi-Bellman equations where current convergence rates are suboptimal. They explicitly state that while they recover first-order convergence for Lipschitz controls, weaker regularity (such as Hölder continuity with exponent $\alpha$) yields convergence rates of $O(h^\alpha)$, and the piecewise constant control approach for infinite horizons incurs a logarithmic penalty compared to finite horizon results. The work does not propose new experimental setups but rather provides a theoretical correction to existing error analysis in the field.