Multivariate Adaptive Regression Spline Based Framework For Statistically Parsimonious Adaptive Dynamic Programming

Abstract

Central to Dynamic Programming (DP) is the `cost-to-go' or `future value' function, which is obtained via actually solving the Bellman's equation and central to Approximate Dynamic Programming (ADP) is the use of an approximation of the future value function. The exact DP algorithm seeks to compute and store a table consisting of one cost-to-go value for each point in the state space and its usefulness is limited by the curse of dimensionality, which renders the methodology computationally intractable in the face of real life problems with high dimensional state space and in the face of continuous state variables. ADP methodology seeks to address and redress the issue of the curse of dimensionality by not seeking to compute the future value function exactly and at each point of the state space; rather opting for an approximation of the future value function in the domain of the state space. The existing ADP methodologies have successfully handled the `continuous' state variables through discretization of the state space and estimation of the cost-to-go or future value function and have been challenged in scenarios involving a mix of `continuous' and `categorical' or qualitative state variables.The first part of this dissertation research seeks to develop a flexible, nonparametric statistical modeling method which can capture complex non-linearity in data comprised of a mix of continuous and categorical variables and can be used to approximate future value functions in stochastic dynamic programming (SDP) problems with a mix of continuous and categorical state variables. This dissertation proposes a statistical modeling method, called `TreeMARS' which combines the versatility of the tree-models with the flexibility of the multivariate adaptive regression splines (MARS). An extension of the proposed model, called `Boosted TreeMARS', is also presented. Comparisons are made to the tree-regression model that uses a similar concept, but only permits the use of linear regression at the terminal nodes. Comparisons are presented on a 10-dimensional simulated data set. The second part of the dissertation research, seeking statistical parsimony, proposes a sequential statistical modeling methodology utilizing the `sequential' concept from the Design and Analysis of Computer Experiments (DACE) to make the grid `only fine enough' for the `efficient' discretization and then using multivariate adaptive regression splines methods to approximate future value functions. This methodology can be extended in future to use tree-based multivariate adaptive regression spline models to approximate future value functions involving a mix of continuous and categorical state variables. This sequential grid discretization is nothing but sequential exploration of state and this concept of sequential exploration of state space provides a statistically parsimonious approximate dynamic programming methodology which `adaptively' captures the important variables from the state space and builds approximations around these quantities while seeking approximation of the future value functions, by using the adaptive and flexible modeling methodology.