ABSTRACT
The family of modified problems — forming part of the dynamic programming models studied thus far — gives expression to the optimization of the remaining part of the sequential decision process where a number of decisions have already been made. Consequently, the functional equations that we encountered to this point, relate modified problems to their immediate successors. In this framework an immediate successor of state s ∈ S is a state s′
that can be reached from state s in a single state transition. Thus, in the context of the multistage model, if the process is at stage n and the state s is observed, then an immediate successor of s is any state s′ ∈ S such that s′ = T (n, s, x) for some decision x ∈ D(n, s). Similarly, in the context of our sequential decision model, an immediate
successor of state s ∈ S is any state s′ such that s′ = T (s, x) for some decision x ∈ D(s). This orientation is clearly manifested in the structure of the two generic
functional equations associated with these two types of models:
Multistage decision model:
fn(s) = opt x∈D(n,s)
ρ(n, s, x, fn+1(T (n, s, x))) , n ∈ N, s ∈ S (14.1)
Sequential decision model:
f(s) = opt x∈D(s)
ρ(s, x, f(T (s, x))) , s ∈ S ′ (14.2)
Expressing as they do the optimal return associated with a modified problem as the optimal returns associated with its immediate successors, the orientation of these functional equations is unmistakably “backward”. Note that the orientation is “backward” relative to the direction stipulated by the state transition function T which depicts the dynamics of the decisionmaking process. And so, if the functional equation is seen as the recipe for computing say the value of fj(s) according to (14.1), then the values of fj+1(s
′), s′ = T (j, s, x), x ∈ D(j, s) are computed first. Effectively then, the functional equation is solved for j = N,N − 1, . . . , 1 — in a “backward” order. The roots of this “backward” orientation lie of course in the manner in
which we decompose the objective function of the decision process, and in the property of separability. To have a clearer understanding of this point let us take another look at the concepts of decomposition and separability. This will shed more light on the backward decomposition scheme and it will establish a framework for the formulation of a “forward” decomposition scheme. However, prior to this, I have to explain why the need for a forward scheme
arises at all. To this end I consider a simple example, which illustrates that a backward scheme.
