  In this paper, we consider the stochastic iterative counterpart of the value
iteration scheme wherein only noisy and possibly biased approximations of the
Bellman operator are available. We call this counterpart as the approximate
value iteration (AVI) scheme. Neural networks are often used as function
approximators, in order to counter Bellman's curse of dimensionality. In this
paper, they are used to approximate the Bellman operator. Since neural networks
are typically trained using sample data, errors and biases may be introduced.
The design of AVI accounts for implementations with biased approximations of
the Bellman operator and sampling errors. We present verifiable sufficient
conditions under which AVI is stable (almost surely bounded) and converges to a
fixed point of the approximate Bellman operator. To ensure the stability of
AVI, we present three different yet related sets of sufficient conditions that
are based on the existence of an appropriate Lyapunov function. These Lyapunov
function based conditions are easily verifiable and new to the literature. The
verifiability is enhanced by the fact that a recipe for the construction of the
necessary Lyapunov function is also provided. We also show that the stability
analysis of AVI can be readily extended to the general case of set-valued
stochastic approximations. Finally, we show that AVI can also be used in more
general circumstances, i.e., for finding fixed points of contractive set-valued
maps.
