# Exercise 3: Dynamic Programming

## 1) Policy Evaluation

After your master thesis you decide to study on and do you beer-bachelor.
Therefore, you have to drink three beers in three different pubs. 
There are six pubs available in town, you start at home and will (hopefully) end up at home. The problem is depicted in the following picture:



In our first example we follow the 50/50 policy. 
So after drinking in a pub - e.g. Auld Triangle, there is a $50 \, \%$ probability to go "up" to the Globetrotter and  $50\, \%$ probability to go "down" to the Black Sheep.
Evaluate the state values using policy evaluation ($v_\mathcal{X} = \mathcal{R}_\mathcal{X} + \gamma \mathcal{P}_{xx'} v_\mathcal{X}$):

\begin{align*}
\begin{bmatrix}
v^{50/50}_{1}\\
.\\
.\\
.\\
v^{50/50}_{n}\\
\end{bmatrix}
=
\begin{bmatrix}
\mathcal{R}^{50/50}_{1}\\
.\\
.\\
.\\
\mathcal{R}^{50/50}_{n}\\
\end{bmatrix}
+
\gamma
\begin{bmatrix}
{p}^{50/50}_{11}&...&{p}^{50/50}_{1n}\\
.& &.\\
.& &.\\
.& &.\\
{p}^{50/50}_{n1}&...&{p}^{50/50}_{nn}\\
\end{bmatrix}
\begin{bmatrix}
v^{50/50}_{1}\\
.\\
.\\
.\\
v^{50/50}_{n}\\
\end{bmatrix}
\end{align*}

The rewards are given as negative numbers next to the arrows and represent the distances between two bars as a penalty.
In this exercise we will set $\gamma = 0.9$. 
In the shown problem we have $n = 8$ states (pubs, including start-home and end-home), ordered as given by the state space:

\begin{align*}
\mathcal{X} =
\left\lbrace \begin{matrix}
\text{Start: Home}\\
\text{Auld Triangle}\\
\text{Lötlampe}\\
\text{Globetrotter}\\
\text{Black Sheep}\\
\text{Limericks}\\
\text{Fat Louis}\\
\text{End: Home}\\
\end{matrix}
\right\rbrace
\end{align*}

Use a little python script to calculate the state values!

## 1) Solution

The state transition matrix is given by:

$\mathcal{P}_{xx'} = 
\begin{bmatrix}
0 & 0.5 & 0.5 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0.5 & 0.5 & 0 & 0 & 0\\
0 & 0 & 0 & 0.5 & 0.5 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0.5 & 0.5 & 0\\
0 & 0 & 0 & 0 & 0 & 0.5 & 0.5 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
\end{bmatrix}
$

By matrix inversion we can calculate the state values for the given policy like already learned in exercise 2 by:
\begin{align}
v_\mathcal{X} &= \mathcal{R}_\mathcal{X} + \gamma \mathcal{P}_{xx'} v_\mathcal{X}\\
v_\mathcal{X} - \gamma \mathcal{P}_{xx'} v_\mathcal{X} &= \mathcal{R}_\mathcal{X}\\
\left( I_6 - \gamma \mathcal{P}_{xx'} \right) v_\mathcal{X} &= \mathcal{R}_\mathcal{X}\\
v_\mathcal{X} &= \left( I_6 - \gamma \mathcal{P}_{xx'} \right)^{-1} \mathcal{R}_\mathcal{X}\\
\end{align}

First, we have to calculate the expected reward using the 50/50 policy. 
Concerning the home state, it is 50 % likely to receive a negative reward of -3 on the way to the Auld Triangle and 50 % likely to receive a negative reward of -1 on the way to Lötlampe. 
So the expected reward is given by: $\mathcal{R}_1 = 0.5 \cdot (-3) + 0.5 \cdot (-1) = -2$

Following this concept, the expected reward vector is given by:

$\mathcal{R} =
\begin{bmatrix}
-2\\
-3\\
-4\\
-4.5\\
-5.5\\
-6\\
-7\\
0
\end{bmatrix}
$

Making use of this knowledge, we can calculate the state values as follows:



```python
import numpy as np

# define given parameters
gamma = 0.9 # discount factor

### BEGIN SOLUTION

P_xx = np.array([[0, 0.5, 0.5,   0,   0,   0,   0,   0],
                 [0,   0,   0, 0.5, 0.5,   0,   0,   0],
                 [0,   0,   0, 0.5, 0.5,   0,   0,   0],
                 [0,   0,   0,   0,   0, 0.5, 0.5,   0],
                 [0,   0,   0,   0,   0, 0.5, 0.5,   0],
                 [0,   0,   0,   0,   0,   0,   0,   1],
                 [0,   0,   0,   0,   0,   0,   0,   1],
                 [0,   0,   0,   0,   0,   0,   0,   1]]) # state trasition probability

r_X = np.array([-2, -3, -4, -4.5, -5.5, -6, -7, 0]) # rewards
r_X = r_X.reshape(-1, 1) # make column vector

v_X = np.matmul(np.linalg.inv(np.eye(8)-gamma*P_xx) , r_X)

### END SOLUTION

print(v_X)

```

    [[-13.9385]
     [-12.765 ]
     [-13.765 ]
     [-10.35  ]
     [-11.35  ]
     [ -6.    ]
     [ -7.    ]
     [  0.    ]]


## 2) Exhaustive Policy Search 

From now on use $\gamma = 1$.

As you have pre knowledge from your master degree, you try to minimize the distance of the way you have to take during your tour in order to have more time in the pubs. Therefore, you perform the following exhaustive search algorithm:

1. Write down all possible path-permutations and calculate the distances.
2. Which is the best path concerning most beer per distance?
3. Derive the formula to calculate the number of necessary path comparisons. 



## 2) Solution

Auld Triangle, Globetrotter, Limericks = -15

Auld Triangle, Globetrotter, Fat Louis = -17

Auld Triangle, Black Sheep, Limericks = -18

Auld Triangle, Black Sheep, Fat Louis = -20

Lötlampe, Black Sheep, Fat Louis = -19

Lötlampe, Black Sheep, Limericks = -17

Lötlampe, Globetrotter, Limericks = -14

Lötlampe, Globetrotter, Fat Louis = -16

Choice of two, three times. Order of chosen actions $\{up, down\}$ is important and number of choices stays the same. The number of different paths is therefore given by: $N^k = 2^3 = 8$. So the number of necessary path comparisons is $N^k -1 = 2^3 -1= 7$.

With number of decisions $k$ and possible options per decision $N$.

## 3) Dynamic Programming - The Idea

Trying out all combinations might not be best for your liver, so you want to solve the problem above using dynamic programming. 

Making use of value iteration, derive the values resulting from the optimal policy: $v_{i+1}^*(x_k) = \text{max}_u (r_{k+1} + v_{i}^*(x_{k+1}))$.

Hint: There is only one policy improvement step needed.

How many value comparisons have to be made?

## 3) Solution

In this situation, we are looking for the state with maximum value denoted by the asterisk $^*$.
At first we initialize all state values with zero and update from start to end using the equation above. 

For the first iteration $i=0$, all state values are zero, so for $i=1$, the best immediate reward is taken as new state value due to $v_{i=1}^*(x_k) = \text{max}_u (r_{k+1} + \underbrace{v_{i=0}^*(x_{k+1}))}_{=0}$.

For $i=2$ we have to consider that the state value $v_{i=1}^*(x_{k+1})$ is not zero anymore.

For example for the "Start" state we have the options: 
1. To A: $v_{i=2}(Start) = -3 -2 = -5$
2. To Lö:$v_{i=2}(Start) = -1 -3 = -4$

As we are looking for the optimal policy (remember $^*$) we take the better value (to Lö).

For the state A we have the options: 
1. To G: $v_{i=2}(A) = -2 -4 = -6$
2. To B: $v_{i=2}(A) = -4 -5 = -9$

...

i \ x   | Start  |   A    |  Lö    |   G    |   B    |  Li    |   F    |  End
-------- | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ 
    0    |   0    |   0    |   0    |   0    |   0    |   0    |   0    |   0
    1    |   -1   |   -2   |   -3   |   -4   |   -5   |   -6   |   -7   |   0
    2    |   -4   |   -6   |   -7  |   -10   |   -11   |   -6   |   -7   |   0
    3    |   ...   |   

This would take a lot of time and it would be better to write a little programm.
But if we change the order of state updates in a clever way, like explained in the lecture, it needs only one iteration to find the result!

Since we know the model, we are able to begin the evaluation in the end state and can derive the final state values directly: 

If in Limericks or Fat Louis, there is no choice of way, so the value of these locations is directly given.

\begin{align}
v(\text{Limericks})&=-6\\
v(\text{Fat Louis})&=-7
\end{align}

If in Globetrotter or Black Sheep, the choice where to go is determined by the distance and the future value:

\begin{align}
v(\text{Globetrotter})&=-4+v(\text{Limericks})=-10 \hspace{0.5cm} \Leftarrow \text{optimal choice}\\
v(\text{Globetrotter})&=-5+v(\text{Fat Louis})=-12
\end{align}

\begin{align}
v(\text{Black Sheep})&=-5+v(\text{Limericks})=-11 \hspace{0.5cm} \Leftarrow \text{optimal choice}\\
v(\text{Black Sheep})&=-6+v(\text{Fat Louis})=-13
\end{align}

And go on like this:

\begin{align}
v(\text{Auld Triangle})&=-2+v(\text{Globetrotter})=-12 \hspace{0.5cm} \Leftarrow \text{optimal choice}\\
v(\text{Auld Triangle})&=-4+v(\text{Black Sheep})=-15
\end{align}

\begin{align}
v(\text{Lötlampe})&=-3+v(\text{Globetrotter})=-13 \hspace{0.5cm} \Leftarrow \text{optimal choice}\\
v(\text{Lötlampe})&=-5+v(\text{Black Sheep})=-16
\end{align}

Finally, we decide where to start:

\begin{align}
v(\text{Home})&=-3+v(\text{Auld Triangle})=-15 \\
v(\text{Home})&=-1+v(\text{Lötlampe})=-14 \hspace{0.5cm} \Leftarrow \text{optimal choice}
\end{align}


i \ x      | Start  |   A    |  Lö    |   G    |   B    |  Li    |   F    |  End
-------- | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ 
    0    |   0    |   0    |   0    |   0    |   0    |   0    |   0    |   0
    1    |   -14  |  -12   |   -13  |   -10  |   -11  |   -6   |   -7   |   0

So we have to calculate the value of 5 states (4 pubs and 1 starting node) for both of the possible choices to be made. The 2 states in direct reach of the terminal node do not allow choices. The number of comparisons is therefore given by $N k -1 = 2 \cdot 3 -1 = 5$ which is much better for large problems than an exhaustive search, if you start clever.



## 4) Value Iteration in Stochastic Environments

All of the pubs have different special offers on some days of the week.
Due to general confusion you have no clue, which day of the week we currently have.
You only know, for example, that Globetrotter has one happy-hour-day per week, but Black Sheep has four days per week.
So, the chance to get a positive reward in the Black Sheep is higher than in the Globetrotter. 

To find the best path we can use the Bellman optimality equation we know from the lecture:

$v_\pi(x_k) = \text{max}_{u_k\in \mathcal{U}} \mathbb{E}\left[R_{k+1} + \gamma v_\pi(X_{k+1}|X_k = x_k, U_k = u_k)\right]$ 

## Comparison to lecture:
In the tree example from lecture we have deterministic rewards and a stochastic state transition.
So $v_\pi(x_k) = \text{max}_{u_k\in \mathcal{U}} r_x^u + \gamma \Sigma_{x_{k+1}\in \mathcal{X}}p_{xx'}^u v_\pi(x_{k+1})$




In our problem we have deterministic state transitions because we reach the bar we plan to visit for sure.
But the reward in our case has a stochastic offset.
If happy-hour-day (randomly, we do not know the weekday), we get an additional positive reward.
The probability to get that is dependent on the number of happy-hour-days per week.
For example:



As can be seen, in Globetrotter we have in 1 of 7 cases (days) an additional happy-hour-reward and in Black Sheep in 4 of 7 cases.

The states are defined in the following order:

$\mathcal{X} = \left\lbrace \begin{matrix}
\text{Start: Home}\\
\text{Auld Triangle}\\
\text{Lötlampe}\\
\text{Globetrotter}\\
\text{Black Sheep}\\
\text{Limericks}\\
\text{Fat Louis}\\
\text{End: Home}\\
\end{matrix}
\right\rbrace$

The probability to get the positive reward (happy hour) is defined by:

$p_{xr_+} = \left[ \begin{matrix}
\frac{3}{7} & \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & 0 & 0\\
\frac{6}{7} & \frac{4}{7} & \frac{4}{7} & \frac{5}{7} & \frac{5}{7} & 0 & 0\\
\end{matrix}
\right]$

                    
$r_{+} = \left[ \begin{matrix}
12 & 16 & 16 & 16 & 16 & 0 & 0\\
6 & 10 & 10 & 8 & 8 & 0 & 0\\
\end{matrix}
\right]$  

The probability to get the no extra reward is $p_{xr_-} = 1 - p_{xr_+}$.
In that case you take the "no extra reward" $r_-$ is zero in all cases.

$r_{-} = \left[ \begin{matrix}
0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0\\
\end{matrix}
\right]$  


The actions to choose are $\textit{up}$ and $\textit{down}$ (for states Li and F, $\textit{up}$ and $\textit{down}$ mean the same).

So if you are at home and you go $\textit{up}$ you get a fixed reward of $-3$ on the way.
With a probability of $p_{x=0,r_+} = \frac{3}{7}$ there is happy hour in the Auld Triangle and you get an additional reward of $+12$. 



1. Examine the pseudocode for value iteration as presented in the lecture. Does this pseudocode already contain the concept of a stochastic reward and where do we find it?
2. Make use of value iteration to (use $\gamma = 1$):
    1. Find the state value for each state
    2. Find the optimal policy
3. Check your solution by dynamic programming by hand like in 3)

### Pseudocode:
***
- **input:** Full model of the MDP i.e. $\left\langle\mathcal{X}, \mathcal{U}, \mathcal{P}, \mathcal{R}, \gamma \right\rangle$
- **parameter:** $\delta>0$ as accuracy termination threshold
- **init:** $v_0(x_k)\, \forall \, x_k\in\mathcal{X}$ arbitrary except $v_0(x_k)=0$ if $x_k$ is terminal
- **repeat** 
    - $\Delta \leftarrow 0 $
    - **for** $\forall \, x_k\in\mathcal{X}$
        - $\tilde{v}\leftarrow \hat{v}(x_k)$
		- $\hat{v}(x_k)\leftarrow  \max_{u_k\in\mathcal{U}}\left(\mathcal{R}^u_x + \gamma\sum_{x_{k+1}\in\mathcal{X}}p_{xx'}^u \hat{v}(x_{k+1})\right)$
		- $\Delta \leftarrow \max\left(\Delta, |\tilde{v}-\hat{v}(x_k) |\right)$
    - **end**
- **until** $\Delta < \delta$
- **output:** Deterministic policy $\pi\approx\pi^*$, such that

$\pi(x_k)\leftarrow  \text{arg} \, \text{max}_{u_k\in\mathcal{U}}\left(\mathcal{R}^u_x + \gamma\sum_{x_{k+1}\in\mathcal{X}}p_{xx'}^u \hat{v}(x_{k+1})\right)$
***
Value iteration (note: compared to policy iteration, value iteration doesn't require an initial policy but only a state-value guess)

## 4) Solution 



```python
import numpy as np
np.set_printoptions(linewidth=100)

r_ways = np.array([[-3, -2, -3, -4, -5, -6, -7],
                   [-1, -4, -5, -5, -6, -6, -7]]) # fixed rewards for the upwards or downwards path

p_xr = np.array([[3/7, 1/7, 1/7, 1/7, 1/7, 0, 0],
                 [6/7, 4/7, 4/7, 5/7, 5/7, 0, 0]]) #probability of success for the upwards or downwards path

r_happy = np.array([[12, 16, 16, 16, 16, 0, 0],
                    [ 6, 10, 10,  8,  8, 0, 0]])

expected_rewards = r_ways + p_xr*r_happy + (1-p_xr)*0
values = np.zeros([8])


delta = 0.1 # lower tolerance boundary

### BEGIN SOLUTION

error = 100

iteration_idx=0
while error > delta:
    iteration_idx += 1
    error = 0
    for state_idx in range(len(values)-1):
        v_tilde = values[state_idx]
        up_value = expected_rewards[0, state_idx] + values[state_idx + (state_idx % 2 + 1)]
        if state_idx == 5 or state_idx == 6:
            down_value = up_value
        else:
            down_value = expected_rewards[1, state_idx] + values[state_idx + (state_idx % 2 + 2)]
        values[state_idx] = np.max([up_value, down_value])
        
        error = np.max([error, np.sum(np.abs(v_tilde-values[state_idx]))])

# Alternative, faster solution
values2 = np.zeros(8)
iteration_idx2 = 0
error = 100
transition_indices = np.arange(1, 8)
transition_indices += 1 - transition_indices % 2  # results in [1 3 3 5 5 7 7]
transition_indices = np.column_stack([transition_indices, transition_indices + 1]).clip(max=7).T
while error > delta:
    iteration_idx2 += 1
    updated_values2 = np.max(expected_rewards + values2[transition_indices], axis=0)
    error = np.abs(values2[:-1] - updated_values2).max()  # last state in values2 is never updated
    values2[:-1] = updated_values2  # terminal state will never be updated
assert np.allclose(values, values2)
assert iteration_idx == iteration_idx2
    
        
### END SOLUTION
print(values)
print(iteration_idx)
```

    [-2.42857143 -5.57142857 -6.57142857 -6.28571429 -7.28571429 -6.         -7.          0.        ]
    5



```python
policy = []
for state_idx in range(len(values)-1):     
    up_value = expected_rewards[0, state_idx] + values[state_idx + (state_idx % 2 + 1)]
    if state_idx == 5 or state_idx == 6:
        down_value = up_value
    else:
        down_value = expected_rewards[1, state_idx] + values[state_idx + (state_idx % 2 + 2)]
    if up_value > down_value:
        policy.append("Up")
    elif up_value < down_value:
        policy.append("Down")
    else:
        policy.append("Graduated! Go home!")        
print(policy)

# Alternative, faster solution
actions = ['Up', 'Down']
states = ['Start: Home', 'Auld Triangle', 'Lötlampe', 'Globetrotter', 'Black Sheep', 'Limericks', 'Fat Louis']
greedy_policy = np.argmax(expected_rewards + values2[transition_indices], axis=0)
for i, (s, p) in enumerate(zip(states, greedy_policy.tolist())):
    # From last two states there is only one direction
    direction = f'Go {actions[p]}' if i < len(states) - 2 else 'Graduated! Go home!' 
    print(f'When in {s} - {direction}')
```

    ['Down', 'Down', 'Down', 'Down', 'Down', 'Graduated! Go home!', 'Graduated! Go home!']
    When in Start: Home - Go Down
    When in Auld Triangle - Go Down
    When in Lötlampe - Go Down
    When in Globetrotter - Go Down
    When in Black Sheep - Go Down
    When in Limericks - Graduated! Go home!
    When in Fat Louis - Graduated! Go home!




74dd8f21f46b11b326d6f0e3a02a47b46c05cd75
ipynb
Jupyter Notebook
exercises/solutions/ex03/Ex3.ipynb
adilsheraz/reinforcement_learning_course_materials
e086ae7dcee2a0c1dbb329c2b25cf583c339c75a
MIT
2020-07-20T08:38:15.000Z
2022-03-31T19:30:35.000Z
exercises/solutions/ex03/Ex3.ipynb
speedhunter001/reinforcement_learning_course_materials
09a211da5707ba61cd653ab9f2a899b08357d6a3
MIT
2020-07-22T07:27:55.000Z
2021-05-12T14:37:08.000Z
exercises/solutions/ex03/Ex3.ipynb
speedhunter001/reinforcement_learning_course_materials
09a211da5707ba61cd653ab9f2a899b08357d6a3
MIT
2020-09-08T17:12:25.000Z
2022-03-31T18:13:08.000Z
Qwen/Qwen-72B
1. YES
2. YES