Sunday, July 31, 2011

Notes on Dynamic Systems and the Value Function

Dynamic systems can be described by differential and difference equations. Without a loss of generality, consider a dynamic system represented by a difference equation: $$x_{k+1}=f\left(x_{k}\right)$$. The state of the system is represented by $$x$$ and the function $$f$$ is the mapping from one state to the next. One way to characterize a dynamic system is with an additive cost: $$J$$. An additive cost summarizes the cost of operation for the system from some initial state, $$x_{0}$$. To ensure that the sums are finite an exponential weighting factor, $$alpha$$, is introduced. This factor has a value between between 0 and 1.  Under some circumstances, $$alpha$$ can be equal to one. One special case is where the system is guaranteed to eventually enter a zero cost state. However, in general, it will need to be less than one. This additive cost is a function of each initial condition:

 $$J\left(x_{0}\right)=\sum_{k=0}^{\infty}\left(\alpha^{k}\cdot c\left(x_{k}\right)\right)$$. (1)

The value of the additive cost can be solved using the dynamic programming equations:

 $$V\left(x\right)=c\left(x\right)+\alpha^{k}\cdot V\left(f\left(x\right)\right)$$. (2)

The function $$V$$ is referred to as the value function.