Combining deep learning and linear programming cuts dynamic programming errors
Bellman Error Minimization Via Linear Programming Normalization
Machine Learning
Summary
Dynamic programming helps make decisions over time but can be hard in large problems. The authors show how using deep learning together with a math technique called linear programming can better estimate solutions to these problems. They tested their approach on a network control problem and found it works well compared to existing methods. This method aims to reduce errors in the Bellman equation, a key tool for planning and learning.
What this means in practice
- •For network capacity planners: Improve dynamic control decisions in network traffic and bandwidth allocation with more accurate approximations of future outcomes.
- •For revenue management teams: Generate better pricing and inventory control rules for services and products by minimizing error in dynamic programming models.
Authors
Haining Yu
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.