Skip to main content
The policy π\pi is evaluated when we have produced the state-value function vπ(s)v_\pi(s) for all states. In other words when we know the expected discounted returns that each state can offer us. Suppose we have two states: S={s1,s2}S = \{s_1, s_2\}, and a deterministic policy π\pi that always chooses action aa. The dynamics are:
  • From s1s_1, action leads to s2s_2 with reward 22
  • From s2s_2, action leads to s1s_1 with reward 00
Let γ=0.9\gamma = 0.9 and the state transition matrix under π\pi: Pπ=[0110]P^\pi = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}
  • Reward vector:
rπ=[20]r^\pi = \begin{bmatrix} 2 \\ 0 \end{bmatrix} From the Bellman expectation equation: vπ=rπ+γPπvπv^\pi = r^\pi + \gamma P^\pi v^\pi Rewriting: (I−γPπ)vπ=rπ(I - \gamma P^\pi) v^\pi = r^\pi Compute: I−γPπ=[1001]−0.9⋅[0110]=[1−0.9−0.91]I - \gamma P^\pi = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} - 0.9 \cdot \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & -0.9 \\ -0.9 & 1 \end{bmatrix} Solve: [1−0.9−0.91][v1v2]=[20]\begin{bmatrix} 1 & -0.9 \\ -0.9 & 1 \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \end{bmatrix} Solving gives: v1=2+0.9v21,v2=0.9v1⇒v1=2+0.81v1⇒v1(1−0.81)=2⇒v1=20.19≈10.526,v2≈9.474v_1 = \frac{2 + 0.9 v_2}{1}, \quad v_2 = 0.9 v_1 \Rightarrow v_1 = 2 + 0.81 v_1 \Rightarrow v_1(1 - 0.81) = 2 \Rightarrow v_1 = \frac{2}{0.19} \approx 10.526, \quad v_2 \approx 9.474

​
Iterative Policy Evaluation

This method is based on the recognition that the Bellman operator is contractive. We can apply the Bellman expectation backup equations repeatedly in an iterative fashion and converge to the state-value function of the policy. We start at k=0k=0 by initializing all state-value function (a vector) to v0(s)=0v_0(s)=0. In each iteration kk we start with the state value function of the previous iteration vk(s)v_k(s) and apply the Bellman expectation backup as prescribed by the one step lookahead tree below that is decorated relative to what we have seen in the Bellman expectation backup with the iteration information. This is called the synchronous backup formulation as we are updating all the elements of the value function vector at the same time. policy-evaluation-tree Tree representation of the state-value function with one step look ahead across iterations. The Bellman expectation backup is given by, vk+1(s)=∑a∈Aπ(a∣s)(Rsa+γ∑s′∈SPss′avk(s′))v_{k+1}(s) = \sum_{a \in \mathcal A} \pi(a|s) \left( \mathcal R_s^a + \gamma \sum_{s^\prime \in \mathcal S} \mathcal{P}^a_{ss^\prime} v_k(s^\prime) \right) and in vector form, vk+1=Rπ+γPπvk\mathbf{v}^{k+1} = \mathbf{\mathcal R}^\pi + \gamma \mathbf{\mathcal P}^\pi \mathbf{v}^k
A simple scalar contraction that illustrates the idea behind iterative policy evaluation is:xk+1=c+γxkx_{k+1} = c + \gamma x_kwhere:
  • cc is a constant (analogous to reward),
  • γ∈[0,1)\gamma \in [0, 1) is the contraction factor (analogous to the discount factor in MDPs).
This scalar recurrence mimics the vector version:vk+1=rπ+γPπvkv_{k+1} = r^\pi + \gamma P^\pi v_kbut in one dimension, where PπP^\pi is just the scalar 1. Solving for the fixed point x=c+γxx = c + \gamma x:x(1−γ)=c⇒x=c1−γx (1 - \gamma) = c \Rightarrow x = \frac{c}{1 - \gamma}Just like in policy evaluation, this converges because the operator T(x)=c+γxT(x) = c + \gamma x is a contraction mapping when γ<1\gamma < 1.
This will converge to x=21−0.9=20x = \frac{2}{1 - 0.9} = 20.
To implement the iterative approach to the MDP solution for the trivial two state problem, we start with initial guess: v0=[00]v_0 = \begin{bmatrix} 0 \\ 0 \end{bmatrix} Update iteratively: Iteration 1: v1=rπ+γPπv0=[20]+0.9⋅[00]=[20]v_1 = r^\pi + \gamma P^\pi v_0 = \begin{bmatrix} 2 \\ 0 \end{bmatrix} + 0.9 \cdot \begin{bmatrix} 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \end{bmatrix} Iteration 2: v2=rπ+γPπv1=[20]+0.9⋅[02]=[21.8]v_2 = r^\pi + \gamma P^\pi v_1 = \begin{bmatrix} 2 \\ 0 \end{bmatrix} + 0.9 \cdot \begin{bmatrix} 0 \\ 2 \end{bmatrix} = \begin{bmatrix} 2 \\ 1.8 \end{bmatrix} Iteration 3: Pπv2=[1.82]⇒v3=[20]+0.9⋅[1.82]=[3.621.8]P^\pi v_2 = \begin{bmatrix} 1.8 \\ 2 \end{bmatrix} \Rightarrow v_3 = \begin{bmatrix} 2 \\ 0 \end{bmatrix} + 0.9 \cdot \begin{bmatrix} 1.8 \\ 2 \end{bmatrix} = \begin{bmatrix} 3.62 \\ 1.8 \end{bmatrix} Iteration 4: Pπv3=[1.83.62]⇒v4=[20]+0.9⋅[1.83.62]=[3.623.258]P^\pi v_3 = \begin{bmatrix} 1.8 \\ 3.62 \end{bmatrix} \Rightarrow v_4 = \begin{bmatrix} 2 \\ 0 \end{bmatrix} + 0.9 \cdot \begin{bmatrix} 1.8 \\ 3.62 \end{bmatrix} = \begin{bmatrix} 3.62 \\ 3.258 \end{bmatrix} Continuing this will converge to: vπ≈[10.5269.474]v^\pi \approx \begin{bmatrix} 10.526 \\ 9.474 \end{bmatrix} which matches the exact solution from the linear system.

​
Policy Evaluation - Minigrid Examples

The following examples are based on the minigrid - empty environment.

​
Iterative Method

​
Policy Evaluation using Ray

The problem here is trivial and in practice Ray is often used to parallelize computations. For more information see the Ray documentation and Ray RLlib
Edit this page on GitHub or file an issue.