Policy Evaluation

How do we specify the measure of the quality of a policy?

Finite-horizon

For a given MDP policy $\pi$ and horizon $h$, we define the “horizon $h$ value” of a state, $V_{\pi }^h(s)$. This is the expected sum of rewards given that we start in state $s$, and execute policy $\pi$ for $h$ steps.

We do this by induction on the horizon $h$, which is the number of steps left to go. The base case of is when there are no steps remaining, in which case, no matter what state we’re in, the value is $0$, so:

$$V_{\pi }^0(s)=0$$

Note that the indexing here is reversed! $V^h$ means that there are $h$ steps until the end. Above, $h=0$ means that we are at the end of the process.

Then, we have:

$$(\text{Value of policy at }h+1)=(\text{Reward in state }s)+(\text{Expected horizon }h\text{ value for next state})$$

So, starting with horizons $1$ and $2$, we have:

$$\begin{array}{rl}{V}_{\pi }^1(s)& =0+R(s,\pi (s))\\ V_{\pi }^2(s)& =0+R(s,\pi (s))+\sum _{s^{\prime }}T(s,\pi (s),s^{\prime })\cdot R(s^{\prime },\pi (s^{\prime }))\end{array}$$

Like we mentioned, the summation term is an expected value; we don’t know exactly what state we’re going to end up in but we do know a probability distribution for the possibilities. Recall that:

• $T(s,\pi (s),s^{\prime })$ is the probability of transitioning to state $s^{\prime }$ from state $s$ after taking $\pi (s)$.
• $R(s,\pi (s))$ is the reward for taking action $\pi (s)$ in state $s$.
• In the above, we could replace $\pi (s)$ with action $a$.

In general, this becomes:

$$V_{\pi }^h(s)=R(s,\pi (s))+\sum _{s^{\prime }}T(s,\pi (s),s^{\prime })\cdot V_{\pi }^{h-1}(s^{\prime })$$

Once again, the sum over $s^{\prime }$ is an expected value. We are considering all possible next states of $s^{\prime }$ and computes their average of their $(h-1)$-horizon values, weighted by the probability that the transition function from state $s$ with the action chosen by the policy, $\pi (s)$, assigns to arriving in state $s^{\prime }$.

We can say that a policy ${\pi }_1$ is better than ${\pi }_2$ for horizon $h$, if for all $s\in S$, $V_{{\pi }_1}^h(s)\ge V_{{\pi }_2}^h(s)$ and there exists at least one $s\in S$ such that $V_{{\pi }_1}^h(s)>V_{{\pi }_2}^h(s)$.

Infinite-horizon

For infinite-horizon, we evaluate in terms of the expected discounted infinite-horizon value that the agent will get in the MDP if it executes that policy.

We define the value of a state $s$ under policy $\pi$ as

$$\begin{array}{rl}{V}_{\pi }(s)& =\mathbf{E}[R_0+\gamma R_1+{\gamma }^2{R}_2+\dots |\pi ,S_0=s]\\ & =\mathbf{E}[R_0+\gamma (R_1+\gamma (R_2+\gamma \dots ))|\pi ,S_0=s]\end{array}$$

The expectation of a linear combination of random variables is the linear combination of the expectations, so

$$\begin{array}{rl}{V}_{\pi }(s)& =\mathbf{E}[R_0|\pi ,S_0=s]+\gamma \mathbf{E}[R_1+\gamma (R_2+\gamma \dots )|\pi ,S_0=s]\\ & =R(s,\pi (s))+\gamma \sum _{s^{\prime }}T(s,\pi (s),s^{\prime })V_{\pi }(s^{\prime })\end{array}$$

You could write down one of these equations for each of the $n=|S|$ states. There are $n$ unknowns $V_{\pi }(s)$. These are linear equations, and so it’s easy to solve them using Gaussian elimination to find the value of each state under this policy.