2 A generic ADP algorithm
Equation (2) (or (3)) is typically solved by stepping backward in time, where it is necessary to loop
over all the potential states to compute V
t
(S
t
) for each state S
t
. For this reason, classical dynamic
programming is often referred to as backward dynamic programming. The requirement of looping
over all the states is the first computational step that cannot be performed when the state variable
is a vector, or even a scalar continuous variable.
Approximate dynamic programming takes a very different approach. In most ADP algorithms,
we step forward in time following a single sample path. Assume we are modeling a finite horizon
problem. We are going to iteratively simulate this problem. At iteration n, assume at time t that
we are in state S
n
t
. Now assume that we have a policy of some sort that produces a decision x
n
t
. In
approximate dynamic programming, we are typically solving a problem that can be written
ˆv
n
t
= max
x
t
C(S
n
t
, x
t
) + γE{
¯
V
n−1
t+1
(S
M
(S
n
t
, x
t
, W
t+1
))|S
t
}
. (4)
Here,
¯
V
n−1
t+1
(S
t+1
) is an approximation of the value of being in state S
t+1
= S
M
(S
n
t
, x
t
, W
t+1
) at time
t + 1. If we are modeling a problem in steady state, we drop the subscript t everywhere, recognizing
that W is a random variable. We note that x
t
here can be a vector, where the maximization problem
might require the use of a linear, nonlinear or integer programming package. Let x
n
t
be the value of
x
t
that solves this optimization problem. We can use ˆv
n
t
to update our approximation of the value
function. For example, if we are using a lookup table representation, we might use
¯
V
n
t
(S
n
t
) = (1 − α
n−1
)
¯
V
n−1
t
(S
n
t
) + α
n−1
ˆv
n
t
, (5)
where α
n−1
is a stepsize between 0 and 1 (more on this later).
Now we are going to use Monte Carlo methods to sample our vector of random variables which
we denote by W
n
t+1
, representing the new information that would have first been learned between
time t and t + 1. The next state would be given by
S
n
t+1
= S
M
(S
n
t
, x
n
t
, W
n
t+1
).
The overall algorithm is given in figure 1. This is a very basic version of an ADP algorithm, one
which would generally not work in practice. But it illustrates some of the basic elements of an ADP
algorithm. First, it steps forward in time, using a randomly sampled set of outcomes, visiting one
state at a time. Second, it makes decisions using some sort of statistical approximation of a value
function, although it is unlikely that we would use a lookup table representation. Third, we use
information gathered as we step forward in time to update our value function approximation, almost
always using some sort of recursive statistics.
The algorithm in figure 1 goes under different names. It is a basic “forward pass” algorithm where
we step forward in time, updating value functions as we progress. Another variation involves simu-
lating forward through the horizon without updating the value function. Then, after the simulation
is done, we step backward through time, using information about the entire future trajectory.
We have written the algorithm in the context of a finite horizon problem. For infinite horizon
problems, simply drop the subscript t everywhere, remembering that you have to keep track of the
“current” and “future” state.
3
