Expected Total Cost of an MDP Starting from a State

Topics: Policy Improvement Method for MDPs - Markov Decision Process

---

(definition)

In the context of an MDP, let $V_i^n\{r\}$ be the expected total cost of a system that starts in state $i$ and evolves over $n$ periods, given a specific policy $r$. This will be:

$$V_i^n\{k\}=C_{ik}+\alpha \sum _{j=0}^m{p}_{ij}\{k\}{V}_j^{n-1}\{r\}$$

…where $C_{ik}$ is the cost of making the decision $k$ in the state $i$ (as defined by the policy $r$) and $\alpha$ is the discount factor. If there is no discount, then $\alpha =1$, as is the case when using the standard policy improvement method (cf. the discounted version).

Explanation

Notice that this sum is basically the sum of:

• $C_{ik}$, the cost of the first period, when the system goes from $i$ to another state $j$.
• ${\sum }_{j=0}^m{p}_{ij}\{k\}{V}_j^{n-1}\{r\}$, the weighted sum of the total costs that could be incurred by continuing from another state $j$ (and still following the same policy $r$).

Do not forget that these calculations take into consideration a given policy $r$, which defines which decision $k$ is made in which state $i$.