Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My lecture of Mat-2.3148 (Finnish) defines dynamic-programming-algorithm so that$J_N(x_N)=g_N(x_N)$ and $J_k(x_k)=\min_{u_k}\left\{g_k(x_k,u_k)+J_{k+1}(f_k(x_k,u_k))\right\}$ where

  • the state $x_k$
  • the state-equation $x_{k+1}=f_k(x_k,u_k)$
  • control $u_k$
  • cost/benefit function $g_k(x_k,u_k)$
  • border-conditions ($x_0$, $x_N$) and
  • target function $J_k(x_k)=\sum g_k(x_k,u_k)$.

Now the next slide uses the Cost-to-go. Suppose discounted a $N$-time-horizon problem so that $J_{N-k}(x)=\min_u\left\{\alpha^{N-k}g(x,u)+J_{N-k+1}(f(x,u))\right\}$ where $k=1,...,N$ and initial condition $J_N(x)=\alpha^N J(x)$. Now the the cost-go-form is

$$V_{k+1}(x)=\min_u\left\{g(x,u)+\alpha V_k(f(x,u))\right\}$$

where the initial condition $V_0(x)=J_N(x)$ and $V_k(x)$ is the optimal cost aka value function when you begin from the state $x$ and with $k$ steps to go.

What is this cost-to-go algorithm? Bounded discounted possibly-infinite-time-horizon problem where we use something-called "cost-to-go" notation?

share|improve this question

1 Answer 1

The DP algorithm is a discrete-time algorithm. Its generalization to continuous time is the Hamilton-Jacobi-Bellmann equation, its derivation from the discrete time on the page 91 of the Bertsimas DP (1995). It is not always possible to execute the DP algorithm due to excessive computational requirements similarly for the HJB. The cost-to-go is an umbrella term used in both contexts such as the DP algorithm and the HJB. Its intuitive meaning is the next step of the recursion, this is my understanding!

We have the cost-function discounted with the value-function. If $α∈(0,1)$, we have a nicely-behaving thing because the geometric-series converging (Betrsimas DP p.308). The $α$ can be considered as a probability to move so the $α^NJ(x)$ would mean the expected cost after N steps.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.