Bellman Error Minimization Via Linear Programming Normalization

Haining Yu

cs.LGOct 2, 2026

Bellman Error Minimization Via Linear Programming Normalization

Authors: Haining Yu

Organizations: Independent Consultant

Abstract

This paper proposes a new functional approximation approach to reduce Bellman error in high-dimensional dynamic programming and Reinforcement Learning problems. Using a classic dynamic programming problem (network capacity control in revenue management) as the motivational example, the paper illustrates that deep neural networks and linear programming approximation algorithms can be combined to derive approximate solutions to dynamic programming problems. Simulation results show the proposed approximation algorithms achieves competitive performance when compared with benchmark.

Figures & tables

Case	$M$	$N$	$T$	$\textbf{x}(0)$
1	14	27	128,962	100
2	14	39	47,811	500
3	14	39	49,827	500
4	14	39	18,684	200

Table 1: BASIC SIMULATION SETTINGS

Case	DECOMP	DNN	FIFO	LP
1	-	-0.3	-10.0	-1.2
2	-	0.4	-27.1	0.3
3	-	-0.3	-32.8	-0.8
4	-	0.3	-31.4	-1.5

Table 2: PERFORMANCE COMPARISON DIFFERENCE FROM DECOMP, IN %

Function Approximation in RL

See all 20 papers

Deep Learning for Dynamic Programming with Recursive Utility
Jul 5, 2026Xianhua Peng, Wu GuoStochastic Optimal Control Dynamic Programming
HSBC Business School, Peking University, University Town, Nanshan District, Shenzhen, 518055, China.
Contraction-Aligned Analysis of Soft Bellman Residual Minimization with Weighted Lp-Norm for Markov Decision Problem
Apr 8, 2026Hyukjun Yang, Han-Dong Lim, Donghwan LeeFunction Approximation in RL Markov Decision Processes
the Department of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, 34141, South Korea
Heavy-Ball Q-Learning with Residual Weighting Correction
Jun 25, 2026Donghwan LeeMomentum Methods Q-Learning
Department of Electrical Engineering Korea Advanced Institute of Science and Technology (KAIST) Daejeon 34141, South Korea

Jul 5, 2026J/K move · Enter open · S save

Deep Learning for Dynamic Programming with Recursive Utility

Xianhua Peng, Wu Guo

HSBC Business School, Peking University, University Town, Nanshan District, Shenzhen, 518055, China.

Stochastic Optimal Control Dynamic Programming

Open paper AskPDF arXiv

We propose the first deep learning algorithm, the Certainty Equivalent Learning (CEL) algorithm, for solving high-dimensional discrete-time dynamic programming problems with recursive utility. Dynamic programming with recursive utility is numerically challenging because the recursive utility does not have an explicit representation and the Bellman equation contains a certainty equivalent that is difficult to evaluate. The CEL algorithm learns this certainty-equivalent value directly with neural networks and jointly approximates value functions, policy functions, and certainty-equivalent functions. The CEL algorithm is mesh-free and simulation-based, allowing high-dimensional state and control spaces, and does not rely on Euler equations, first-order conditions, or differentiability of the state transition function. The CEL algorithm also works for dynamic programming problems with expected utility as expected utility is a special case of recursive utility. We apply the CEL to discounted linear exponential quadratic Gaussian control, small-noise robust control, Epstein-Zin DSGE, and multivariate strategic asset allocation problems. Compared with closed-form and VFI-based benchmarks, the CEL delivers accurate value and policy approximations, remains effective in high-dimensional problems, achieves accuracy comparable to VFI in the small-noise robust-control case, and produces out-of-sample Bellman errors and Euler or first-order residuals that are in the range from 1.0e-4 to 1.0e-3 for most problems.

Abstract

Function Approximation in RL

Explore similar work

Deep Learning for Dynamic Programming with Recursive Utility

Contraction-Aligned Analysis of Soft Bellman Residual Minimization with Weighted Lp-Norm for Markov Decision Problem

Heavy-Ball Q-Learning with Residual Weighting Correction