Kernel-Based Approximate Dynamic Programming by Brett Bethke

Large-scale dynamic programming problems arise frequently in mutli-agent planning problems. Unfortunately, the curse of dimensionality prevents these problems from being solved exactly in reasonable time using current computational resources. The current project is investigating applying a number of techniques from machine learning (in particular, kernel-based methods) to learn the structure of the cost-to-go function in large-scale dynamic programs and compute an approximate solution quickly. The new algorithms we have developed are able to construct a cost-to-go function that explicitly forces the Bellman residuals to zero at a number of sampled states.

Related publications