  This paper studies an accelerated fitted value iteration (FVI) algorithm to
solve high-dimensional Markov decision processes (MDPs). FVI is an approximate
dynamic programming algorithm that has desirable theoretical properties.
However, it can be intractable when the action space is finite but
vector-valued. To solve such MDPs via FVI, we first approximate the value
functions by a two-layer neural network (NN) with rectified linear units (ReLU)
being activation functions. We then verify that such approximators are strong
enough for the MDP. To speed up the FVI, we recast the action selection problem
as a two-stage stochastic programming problem, where the resulting recourse
function comes from the two-layer NN. Then, the action selection problem is
solved with a specialized multi-cut decomposition algorithm. More specifically,
we design valid cuts by exploiting the structure of the approximated value
functions to update the actions. We prove that the decomposition can find the
global optimal solution in a finite number of iterations and the overall
accelerated FVI is consistent. Finally, we verify the performance of the FVI
algorithm via a multi-facility capacity investment problem (MCIP). A
comprehensive numerical study is implemented, where the results show that the
FVI is significantly accelerated without sacrificing too much in precision.
