Policy Improvement Method for MDPs

Topics: Markov Decision Process

---

The policy improvement method can be used to find the optimal policy for a given MDP.

This method works by, given a policy, relating the expected total costs starting from a state ($V_i\{r\}$) with the expected long term cost for the policy ($g\{r_n\}$).

There is a slightly different version of this method that takes into consideration a discount factor.

Algorithm §

This method is an iterative algorithm. We will use $n$ as the iteration number.

Step 0 §

Before we can formally begin, we need to arbitrarily choose a viable policy $r_1$ as our starting policy ($n=1$, first iteration).

Step 1 §

The first step is to solve the following linear equation system:

$$\{\begin{array}{llc}g\{r_n\}& =C_{ik}+{\sum }_{j=0}^m{p}_{ij}\{k\}{V}_j\{r_n\}-V_i\{r_n\}& \text{ for i = 0, 1, ..., m}\\ V_m\{r_n\}& =0& \end{array}$$

…where $C_{ik}$ is the cost of making the decision $k$ in the state $i$ (as defined by the policy) and $p_{ij}\{k\}$ the transition probability from $i$ to $j$ when making the decision $k$ (as defined by the policy).

We’ll thus obtain:

• $g\{r_n\}$, the expected long term cost for the policy $r_n$
• Every $V_i\{r_n\}$, the expected total cost starting from a state $i$ given the policy $r_n$
  • …where $V_m\{r_n\}$, the expected total cost starting from the last state in the list of states, is set to be $0$.

Step 2 §

The second step consists in finding an alternative policy $r_{n+1}$ such that, in every state $i$, $d_i\{r_{n+1}\}=k$ is the optimal decision to make. To do so, we will use the values previously we previously obtained (more specifically, every $V_i\{r_n\}$).

That is, for every state $i$, we will plug these values into the expressions:

$$C_{ik}+\sum _{j=0}^m{p}_{ij}\{k\}{V}_j\{r_n\}-V_i\{r_n\}\text{for k = 1, 2, ..., K}$$

…having one for every decision that can be made in $i$. We will then pick the decision that yields the optimal result (the smallest if we deal with true costs, the largest if we deal with earnings). This will result in a new alternative policy $r_{n+1}$.

Step 3 §

The third and last step is to determine whether we’ve obtained the optimal policy or not, continuing with another iteration if it is not the case.

If $r_{n+1}=r_n$, then we have the optimal policy. If not, then we shall make another iteration ($n\leftarrow n+1$ and back to step 1).