Spectral Dynamic Programming: Per-Mode Convergence Rates and Computational Acceleration for American Options

We show that eigendecomposing the transition kernel of a Markov decision process yields a spectral Bellman equation: each eigenmode \(k\) satisfies an independent scalar recurrence \(v_k' = r_k + \gamma \mu_k v_k\), converging at rate \(\gamma |\mu_k| \leq \gamma\), where \(\mu_k\) is the \(k\)-th eigenvalue of the transition matrix. Fast modes (\(|\mu_k| \ll 1\)) converge in a single iteration; slow modes (\(|\mu_k| \approx 1\)) dominate the computational cost. This spectral decomposition has three practical consequences:

(1) Computational acceleration. Standard value iteration applies \(M\) uniform backward steps. Spectral value iteration allocates \(M_k = \lceil \log(1/\varepsilon) / \log(1/\gamma |\mu_k|) \rceil\) iterations per mode, skipping already-converged fast modes. For American basket options on \(n\) assets with the COS method, where the transfer matrix eigenvalues decay exponentially as \(|\mu_k| \sim \rho^{-k}\) (analyticity radius \(\rho > 1\)), this reduces the number of non-trivial backward steps from \(M\) to \(M_{\text{eff}} = \lceil \log(1/\varepsilon) / \log(1/\gamma) \rceil\) on only the \(K_{\text{eff}} = O(\log(1/\varepsilon) / \log \rho)\) modes that have not yet converged. Total work per exercise date: \(O(K_{\text{eff}} \cdot M_{\text{eff}} + N^2)\) vs \(O(N^2)\) for the standard method. When \(K_{\text{eff}} \ll N\) and the eigendecomposition is amortized across an option surface, the dominant cost drops by a factor of \(N / K_{\text{eff}}\).

(2) Shadow prices for risk constraints. Adding VaR or CVaR constraints to the Bellman equation yields a Lagrangian with shadow price \(\lambda^ = \partial V^ / \partial b\), where \(b\) is the risk budget. The shadow price quantifies the cost of each unit of risk limit: "relaxing the VaR constraint by \\(1M increases the portfolio value by \)\lambda^*\(." For constrained LP formulations, risk limits appear as additional rows with interpretable dual variables.

(3) Model-free option bounds. The robust Bellman equation \)V = \max_a \min_\xi [R + \gamma \sum P_\xi V]\( under \)\varepsilon\(-perturbation of the transition kernel is still a contraction at rate \)\gamma(1+\varepsilon) < 1\(. The resulting value function interval \)[V_{\text{low}}, V_{\text{high}}]\( gives model-free option price bounds with width \)O(\varepsilon)\( that narrow monotonically as the uncertainty set shrinks.

All results are machine-verified in Lean 4: 78 theorems across 28 files (Bellman + Extended Bellman gyms), compiled via lake build with zero errors. We benchmark spectral DP against standard COS backward induction on American basket options and show 5--50\)\times$ speedup for concentrated eigenvalue spectra.

Keywords: dynamic programming, spectral decomposition, American options, COS method, convergence rate, eigenvalue, shadow price, robust optimization, Lean