Discounted cost

In Formulation 10.2, the cost functional in Item 6 must be defined carefully to ensure that finite values are always obtained, even though the number of stages tends to infinity. The discounted cost model provides one simple way to achieve this by rapidly decreasing costs in future stages. Its definition is based on the standard geometric series. For any real parameter $ \alpha \in (0,1)$,

$\displaystyle \lim_{K \to \infty} \left( \sum_{k=0}^K \alpha^k \right) = {1 \over 1 - \alpha}.$ (10.65)

The simplest case, $ \alpha = 1/2$, yields $ 1+1/2+1/4+1/8+\cdots$, which clearly converges to $ 2$.

Now let $ \alpha \in (0,1)$ denote a discount factor, which is applied in the definition of a cost functional:

$\displaystyle L({\tilde{x}},{\tilde{u}},{\tilde{\theta}}) = \lim_{K \to \infty} \left( \sum_{k=0}^K \alpha^k l(x_k,u_k,\theta_k) \right).$ (10.66)

Let $ l_k$ denote the cost, $ l(x_k,u_k,\theta_k)$, received at stage $ k$. For convenience in this setting, the first stage is $ k = 0$, as opposed to $ k=1$, which has been used previously. As the maximum stage, $ K$, increases, the diminished importance of costs far in the future can easily be observed, as indicated in Figure 10.10.

Figure 10.10: The cost magnitudes decease exponentially over the stages.
\begin{figure}\begin{center}
\begin{tabular}{lll}
Stage & & $L^*_K$  \hline
...
...l_3 + \alpha^4 l_4$ \\
& $\vdots$ \\
\end{tabular}\end{center}
\end{figure}

The rate of cost decrease depends strongly on $ \alpha$. For example, if $ \alpha = 1/2$, the costs decrease very rapidly. If $ \alpha =
0.999$, the convergence to zero is much slower. The trade-off is that with a large value of $ \alpha$, more stages are taken into account, and the designed plan is usually of higher quality. If a small value of $ \alpha$ is used, methods such as value iteration converge much more quickly; however, the solution quality may be poor because of ``short sightedness.''

The term $ l(x_k,u_k,\theta_k)$ in (10.67) assumes different values depending on $ x_k$, $ u_k$, and $ \theta_k$. Since there are only a finite number of possibilities, they must be bounded by some positive constant $ c$.10.1 Hence,

$\displaystyle \lim_{K \to \infty} \left( \sum_{k=0}^K \alpha^k l(x_k,u_k,\theta...
...K \to \infty} \left( \sum_{k=0}^K \alpha^k c \right) \leq {c \over 1- \alpha} ,$ (10.67)

which means that $ L({\tilde{x}},{\tilde{u}},{\tilde{\theta}})$ is bounded from above, as desired. A similar lower bound can be constructed, which ensures that the resulting total cost is always finite.

Steven M LaValle 2012-04-20