Non-parametric Approximate Dynamic Programming via the Kernel Method

Part of Advances in Neural Information Processing Systems 25 (NIPS 2012)

Bibtex »Metadata »Paper »Supplemental »


Nikhil Bhat, Vivek Farias, Ciamac C. Moallemi


This paper presents a novel non-parametric approximate dynamic programming (ADP) algorithm that enjoys graceful, dimension-independent approximation and sample complexity guarantees. In particular, we establish both theoretically and computationally that our proposal can serve as a viable alternative to state-of-the-art parametric ADP algorithms, freeing the designer from carefully specifying an approximation architecture. We accomplish this by developing a kernel-based mathematical program for ADP. Via a computational study on a controlled queueing network, we show that our non-parametric procedure is competitive with parametric ADP approaches.