The Effect of Quadrature on the Convergence of Policy Iteration for Hamilton-Jacobi-Bellman Equations

Technical Summary: The Effect of Quadrature on the Convergence of Policy Iteration for Hamilton–Jacobi–Bellman Equations

Problem Statement
The paper addresses a specific numerical instability encountered when implementing Policy Iteration (PI) algorithms for Hamilton–Jacobi–Bellman (HJB) equations within modern finite element software libraries (e.g., Firedrake, NGSolve). While PI is theoretically known to exhibit asymptotic superlinear convergence for a wide range of problem settings and discretizations, recent observations indicate that implementations in modern libraries often fail to converge or converge only linearly. The authors identify the root cause as the automatic selection of nonmatching quadrature schemes for different terms within the variational formulation of the problem. In older software implementations, a single quadrature scheme was typically enforced for all terms; modern libraries, however, allow users to express equations in variational form where the library automatically selects quadratures for individual terms. This autonomy can lead to discrepancies between the quadrature rules used for the stiffness matrix (left-hand side) and the source terms (right-hand side), breaking the mathematical equivalence required for superlinear convergence.

Methodology
The authors analyze this phenomenon using a second-order semilinear HJB equation of the form $-\Delta u + H(x, \nabla u) = 0$, where the Hamiltonian $H$ is defined as the maximum of a set of linear functions involving control-dependent drift and running costs.

1. Theoretical Framework: The paper reviews the standard PI algorithm, which linearizes the HJB equation at each iteration based on an optimal feedback control. Under exact integration and arithmetic, the "nonresidual" form (solving for the new iterate directly) and the "residual" form (solving for the update step) are mathematically equivalent and both yield superlinear convergence.
2. Discretization Analysis: The authors examine the finite element discretization of these forms. They demonstrate that when numerical quadrature is introduced, the equivalence between the nonresidual and residual forms holds only if the quadrature nodes and weights are matching (identical) for all terms in the bilinear and linear forms.
3. Nonmatching Scenario: If the library selects different quadrature rules for the left-hand side (stiffness matrix) and the right-hand side (source vector), the two forms define different sequences of iterates. The paper hypothesizes that this mismatch destroys the superlinear convergence properties, potentially reducing the method to linear convergence or causing divergence.

Numerical Experiments
To validate these hypotheses, the authors conducted numerical experiments using the NGSolve library (with analogous results observed in Firedrake).

• Test Case: A 2D HJB equation on a square domain with a nonsmooth Hamiltonian, where the optimal control is discontinuous. The exact solution is known ($u(x) = \sin x_1 \sin x_2$).
• Setup: The authors compared the performance of PI under two conditions:
  1. Default Automatic Quadrature: The library selects quadratures independently for each term.
  2. Prescribed Matching Quadrature: The user explicitly enforces the same quadrature rule for all terms.
• Results:
  • Nonresidual Form: Under default automatic quadrature, the nonresidual form failed to converge entirely. Under matching quadrature, it recovered superlinear convergence.
  • Residual Form: Under default automatic quadrature, the residual form converged, but only at a linear rate (characteristic of inexact Newton methods). Under matching quadrature, it also achieved superlinear convergence.
  • Observation: The loss of equivalence between the residual and nonresidual forms in the default setting confirmed the presence of quadrature mismatch.

Key Contributions

• Identification of a Hidden Failure Mode: The paper isolates a specific cause for the failure of Policy Iteration in modern finite element environments: the inadvertent use of nonmatching quadratures by automatic selection algorithms.
• Theoretical Clarification: It clarifies that the equivalence between the residual and nonresidual formulations of PI, which is trivial under exact integration, is fragile and depends strictly on the consistency of numerical integration schemes.
• Practical Remedy: The authors demonstrate that the issue is easily resolved by enforcing matching quadrature rules across all terms in the variational formulation, thereby restoring the expected superlinear convergence.

Significance and Claims
The paper claims that while Policy Iteration is generally robust to errors such as inexact linear algebra, it is sensitive to the consistency of numerical integration in modern variational frameworks. The significance of this work lies in explaining why robust algorithms may fail in contemporary software environments and providing a simple, actionable fix. The authors do not propose new algorithms or future theoretical developments; rather, they offer a diagnostic explanation for observed convergence failures. They assert that enforcing matching quadrature is sufficient to recover the theoretical superlinear convergence rates predicted by existing semismooth Newton analysis. The work serves as a cautionary note for practitioners using high-level finite element libraries to ensure that quadrature consistency is maintained when solving nonlinear HJB equations.