Policy Iteration for Stationary Discounted Hamilton--Jacobi--Bellman Equations: A Viscosity Approach

This paper resolves the ill-posed nature of policy iteration for stationary discounted Hamilton–Jacobi–Bellman equations by introducing a monotone semi-discrete scheme with artificial viscosity, which ensures geometric convergence to a unique discrete solution and provides sharp error estimates that decouple iteration and discretization errors.

The Gist

Imagine you are trying to navigate a massive, foggy maze to find the exit with the least amount of effort. You have a map, but it's not perfect, and the rules of the maze change slightly depending on where you are. This is essentially what Optimal Control is: finding the best path or strategy for a system (like a robot, a financial portfolio, or a self-driving car) over a long period.

In mathematics, this problem is described by a complex equation called the Hamilton–Jacobi–Bellman (HJB) equation. Solving this equation tells you the "perfect" strategy.

However, there's a catch. In the real world (and in continuous mathematics), the "perfect map" (the solution) is often jagged and rough. It has sharp corners where the slope (gradient) suddenly changes or doesn't exist at all.

The Problem: The "Blind" Navigator

The paper tackles a specific method called Policy Iteration (PI). Think of PI as a game of "Hot and Cold" played by a computer:

1. Guess a strategy: "I'll always turn left."
2. Evaluate: "Okay, if I turn left, how much trouble will I get into?"
3. Improve: "Based on that trouble, I should actually turn right here."
4. Repeat: Do this over and over until you can't get any better.

The Glitch: In the continuous, "foggy" world of the HJB equation, Step 3 (Improvement) requires knowing the exact slope of the map at every single point. But because the map is jagged (mathematicians call this a "viscosity solution"), the slope often doesn't exist at the sharp corners. It's like trying to measure the steepness of a cliff edge with a ruler; the ruler just doesn't fit. The computer gets stuck because it can't calculate the next step.

The Solution: Adding "Artificial Fog" (Viscosity)

The authors, Namkyeong Cho and Yeoneung Kim, came up with a clever fix. They realized that if you can't measure the slope on the jagged cliff, you should smooth out the cliff first.

They introduced a technique called Artificial Viscosity.

• The Metaphor: Imagine the jagged cliff is made of sharp rocks. The authors pour a thick, smooth syrup (viscosity) over the rocks. The syrup fills in the cracks and rounds off the sharp edges.
• The Result: Now, the map is smooth. You can easily measure the slope everywhere. The computer can finally perform the "Improve" step without getting stuck.

They didn't just smooth it out randomly; they did it in a very specific, "monotone" way. This ensures that the computer never gets confused about which way is "up" or "down," keeping the logic stable.

The Magic of the "Discount"

The paper focuses on Infinite-Horizon Discounted problems.

• The Metaphor: Imagine you are playing a game where points you get today are worth 100%, but points you get tomorrow are worth 90%, and points next week are worth 81%, and so on. This is the "discount factor."
• Why it matters: This discount acts like a magnetic pull. It prevents the computer from wandering off into infinity. It forces the "Hot and Cold" game to settle down quickly. The authors proved that because of this discount, the computer doesn't just slowly get better; it gets better geometrically (exponentially fast). It's like the game has a built-in "turbo button" that speeds up convergence.

The Trade-Off: The "Decay-Then-Plateau" Effect

The paper also discovered a fascinating relationship between how detailed your map is (mesh size) and how many times you play the game (iterations).

• The Analogy: Imagine you are trying to draw a picture.
  • Iteration Error: This is how well you are learning the shape. At first, your drawing looks terrible, but with every sketch, it gets much better.
  • Discretization Error: This is the limit of your pencil. No matter how good you get at drawing, if your pencil is too thick, you can't draw a hair-thin line.

The authors showed that if you keep drawing (iterating) with a thick pencil (coarse grid), your drawing will get better and better until it hits a "ceiling." Once you hit that ceiling, drawing more doesn't help because the pencil is the problem, not your skill.

The Big Insight: To get a super-precise picture, you need a finer pencil (smaller grid). But here's the kicker: The finer your pencil, the slower your learning speed. If you want a very detailed map, you have to play the "Hot and Cold" game many more times to see the same improvement.

Summary of the Breakthrough

1. The Problem: Standard methods fail because the mathematical map is too jagged to measure.
2. The Fix: They added "syrup" (artificial viscosity) to smooth the map, making it measurable and stable.
3. The Speed: They proved that because of the "discount" (valuing the present more than the future), the method converges incredibly fast.
4. The Reality Check: They provided a formula showing exactly how many times you need to run the calculation based on how detailed you want your map to be.

In everyday terms: The authors built a robust, stable, and fast engine for solving complex navigation problems. They figured out how to smooth out the rough edges that usually break the engine, and they gave us a manual that tells us exactly how much fuel (computing power) we need to get to our destination.

Technical Summary

1. Problem Statement

The paper addresses deterministic infinite-horizon discounted optimal control problems. The value function $V(x)$ for such problems is characterized as the unique bounded viscosity solution to the stationary Hamilton–Jacobi–Bellman (HJB) equation:
$$\lambda V(x) + H(x, \nabla V(x)) = 0$$
where $\lambda > 0$ is the discount factor and $H$ is the Hamiltonian.

The Core Challenge:
While Policy Iteration (PI) is a standard and effective algorithm in discrete settings (Markov Decision Processes), its application to continuous-space deterministic control is ill-posed at the PDE level.

• Regularity Issue: The value function $V$ is generally only Lipschitz continuous; its gradient $\nabla V$ may not exist pointwise or be continuous.
• Ill-posed Improvement Step: The classical policy improvement step, $\alpha_{n+1}(x) = \arg\min_a \{c(x,a) + \nabla V_n(x) \cdot f(x,a)\}$, requires evaluating $\nabla V_n$ pointwise. Since $\nabla V_n$ is undefined on sets of measure zero for viscosity solutions, the nonlinear operator mapping $V_n \to V_{n+1}$ is not well-defined in a stable functional sense.
• Gap: Existing rigorous convergence results for PI in continuous time rely on stochastic diffusion (which provides regularization) or specific linear-quadratic structures. Deterministic cases lack these stabilizing mechanisms.

2. Methodology

The authors propose a monotone semi-discrete formulation that introduces artificial viscosity to regularize the problem while preserving the structure necessary for Policy Iteration.

A. Semi-Discrete Scheme

Instead of solving the continuous PDE directly, they introduce a spatial discretization with mesh size $h$.

1. Discrete Operators: They replace the continuous gradient $\nabla$ with a centered discrete gradient $\nabla_h$ and introduce a discrete Laplacian $\Delta_h$.
2. Artificial Viscosity: A term $N_h \Delta_h V^h$ is added to the equation, where $N_h \propto O(h)$. The semi-discrete equation becomes:
   $$\lambda V^h(x) + H(x, \nabla_h V^h(x)) = N_h \Delta_h V^h(x)$$
   Here, $N$ is a constant chosen large enough (specifically $N \ge \max\{1, \|f\|_\infty/2\}$) to ensure the finite-difference stencil is monotone.
3. Monotonicity: This artificial viscosity ensures the discrete operator satisfies a comparison principle, which is crucial for stability and convergence.

B. The Algorithm (Semi-Discrete PI)

The algorithm alternates between two steps, now well-defined due to the discrete gradients:

1. Policy Evaluation: Given a policy $\alpha_n$, solve the linear resolvent equation:
   $$L^h_{\alpha_n} V^h_n = 0$$
   where $L^h_\alpha$ is the linearized discrete operator. Due to the discount term $\lambda$, this is a contraction mapping.
2. Policy Improvement: Update the policy using the discrete gradient:
   $$\alpha_{n+1}(x) = \alpha(x, \nabla_h V^h_n(x))$$
   Since $\nabla_h$ depends only on neighboring grid points, this step is pointwise well-defined even if the underlying continuous function is non-smooth.

3. Key Contributions

The paper provides three major theoretical contributions:

1. Well-Posedness and Monotonicity:

   • They prove that the semi-discrete PI sequence $\{V^h_n\}$ is well-defined, monotone decreasing ($V^h_{n+1} \le V^h_n$), and converges to the unique solution of the discrete Bellman equation.
   • This resolves the ill-posedness of continuous PI by shifting the analysis to a monotone finite-difference framework.

2. Geometric Convergence (Fixed $h$):

   • For a fixed mesh size $h$, the PI sequence converges geometrically to the discrete solution $V^h$.
   • Mechanism: Unlike finite-horizon problems where convergence is driven by time evolution (Gronwall estimates), here convergence is driven by the resolvent structure induced by the discount factor $\lambda$.
   • The contraction factor is $\beta_h = \frac{2dN/h}{\lambda + 2dN/h} < 1$.

3. Error Analysis and Decomposition:

   • Vanishing Viscosity Estimate: They establish a sharp error bound between the discrete solution $V^h$ and the continuous viscosity solution $V$:
     $$\|V^h - V\|_{L^\infty} \lesssim \sqrt{h}$$
     This matches the optimal rate for first-order Hamilton–Jacobi equations.
   • Unified Error Bound: They derive a total error decomposition separating iteration error from discretization error:
     $$\|V^h_n - V\|_{L^\infty} \le C_1 \beta_h^n + C_2 \sqrt{h}$$
   • The $nh$-Coupling: A critical insight is that the effective convergence rate depends on the product $nh$. As the mesh is refined ($h \to 0$), the contraction factor $\beta_h \to 1$, slowing down convergence. To maintain accuracy, the iteration count $n$ must scale as $n \sim \frac{1}{h} \log(1/h)$.

4. Results

• Theoretical: The paper rigorously proves the existence of the discrete solution, the monotonicity of the PI sequence, and the geometric convergence rate. It clarifies the distinct convergence mechanisms between finite-horizon (parabolic) and infinite-horizon discounted (elliptic/resolvent) settings.
• Numerical:
  • 1D Quadratic Control: Experiments confirm the geometric decay of the value iterates for fixed $h$. The error curves exhibit a "decay-then-plateau" behavior, where the error stops decreasing once it hits the discretization floor ($\sqrt{h}$).
  • 2D Nonlinear Benchmark: A manufactured solution benchmark in 2D with complex, non-separable dynamics confirms that the method works for nonlinear problems. The value iterates converge monotonically to the discrete reference solution.
  • PINN Comparison: A supplementary experiment using Physics-Informed Neural Networks (PINNs) without boundary supervision suggests the framework's potential compatibility with modern neural solvers, though this is not the primary focus.

5. Significance

• Foundational Rigor: This work provides the first rigorous PDE-level analysis of Policy Iteration for deterministic infinite-horizon control, filling a gap between discrete MDP theory and continuous control.
• Algorithmic Stability: It demonstrates that adding artificial viscosity is not just a numerical trick but a necessary structural component to make PI well-posed in the absence of stochastic diffusion.
• Computational Insight: The discovery of the $nh$-coupling offers a practical guideline for computational efficiency. It warns that simply refining the grid ($h \to 0$) without increasing iterations ($n$) will not improve the solution, as the iteration error will dominate.
• Broader Impact: The framework complements recent developments in entropy-regularized control and exploratory reinforcement learning, highlighting that structural ingredients like monotonicity and regularization are essential for the stability of policy-iteration-type algorithms in continuous spaces.

In summary, the paper successfully bridges the gap between discrete dynamic programming and continuous PDE analysis by introducing a monotone semi-discrete scheme, proving its convergence properties, and quantifying the trade-offs between spatial resolution and iteration complexity.