# Exercise 2: Markov Chains and Markov Decision Processes (MDP) 

This exercise deals with the formal handling of Markov chains and Markov decision processes. 

## 1) Markov Chain: State Transition
The graph shows the last beer problem. 
The nodes show the states.
The arrows define the possible transitions to other states and the numbers besides the arrows define the propability of the corresponding transition.
If you are for example in the state "Inital Beer", with 30% propability you go to have a pizza, with 60% propability you meet friends and with 10% propability you end up sleeping.

Define the state transition probability matrix $\mathcal{P}_{xx'}$ of the graph shown in the figure below!



With $p_k = \begin{bmatrix}
\text{Pr}_k \lbrace \text{Inital Beer} \rbrace \\
\text{Pr}_k \lbrace \text{Meet Friends} \rbrace \\
\text{Pr}_k \lbrace \text{Pizza} \rbrace \\
\text{Pr}_k \lbrace \text{Another Beer} \rbrace \\
\text{Pr}_k \lbrace \text{"Last Beer"}\rbrace \\
\text{Pr}_k \lbrace \text{Sleep} \rbrace \\
\end{bmatrix}^\text{T}$

YOUR ANSWER HERE

## 2 ) Markov Chain: Stationary State
Using $p = p \mathcal{P}$, calculate the stationary state probability.

Please note that the sum of the state propabilities equals one for any specific point in time.

YOUR ANSWER HERE

## 3) Markov Reward Process: Evaluating States

In the following rewards for every state are defined.

Given the reward distribution $r_\mathcal{X}$, calculate the state-values $v_\mathcal{X}$.  

The states are defined by:
$\mathcal{X} = \left\lbrace \begin{matrix}
\text{Inital Beer}\\
\text{Meet Friends}\\
\text{Pizza}\\
\text{Another Beer}\\
\text{"Last Beer"}\\
\text{Sleep}\\
\end{matrix}
\right\rbrace$

The rewards are defined by:
$r_\mathcal{X} = \begin{bmatrix}
+1\\
+1\\
+2\\
+1\\
-3\\
0\\
\end{bmatrix}$

The state-value is defined by the state-value Bellman equation: $v_\mathcal{X} = r_\mathcal{X} + \gamma \mathcal{P}_{xx'} v_\mathcal{X}$. Assume that $\gamma = 0.9$ and write a Python program to calculate $v_\mathcal{X}$. Which state is most promising? Why?

Which state is most promising when $\gamma = 0.1$?

YOUR ANSWER HERE


```python
import numpy as np

# define given parameters
gamma = 0.1 # discount factor

# YOUR CODE HERE
raise NotImplementedError()

print(v_X)

```

## 4) Markov Decision Process: State Transition

The graph shows an MDP.
The nodes are the states. 
In every state you can choose between two actions (Lazy or Productive). 
Taken actions impact the state transition probability to the next state.
If you for example have a "Hangover" and decide to be "Productive", there is a 30% chance for you to "Visit Lecture" and a 70% chance to stay in the "Hangover" state.

Define the lazy state transition probabilitiy $\mathcal{P}_{xx'}^{u=\text{Lazy}}$ and the productive state transition probability $\mathcal{P}_{xx'}^{u=\text{Productive}}$ of the graph shown in the figure below.



With $p_k = \begin{bmatrix}
\text{Pr}_k \lbrace \text{Hangover} \rbrace \\
\text{Pr}_k \lbrace \text{Sleep} \rbrace \\
\text{Pr}_k \lbrace \text{More Sleep} \rbrace \\
\text{Pr}_k \lbrace \text{Visit Lecture} \rbrace \\
\text{Pr}_k \lbrace \text{Study}\rbrace \\
\text{Pr}_k \lbrace \text{Pass the Exam} \rbrace \\
\end{bmatrix}^\text{T}$

## 4) Solution


\begin{align}
\mathcal{P}_{xx'}^{u=\text{Lazy}}&=\begin{bmatrix}
0 & 1 & 0 & 0 & 0   & 0\\
0 & 0 & 1 & 0 & 0   & 0\\
0 & 0 & 1 & 0 & 0   & 0\\
0 & 0 & 0 & 0 & 0.8 & 0.2\\ 
0 & 0 & 1 & 0 & 0   & 0\\
0 & 0 & 0 & 0 & 0   & 1\\
\end{bmatrix}\\
\mathcal{P}_{xx'}^{u=\text{Productive}}&=\begin{bmatrix}
0.7 & 0 & 0   & 0.3 & 0   & 0\\
0   & 0 & 0.4 & 0.6 & 0   & 0\\
0   & 0 & 0.5 & 0   & 0.5 & 0\\
0   & 0 & 0   & 0   & 1   & 0\\ 
0   & 0 & 0   & 0   & 0.1 & 0.9\\
0   & 0 & 0   & 0   & 0   & 1\\
\end{bmatrix}
\end{align}

## 5) Markov Decision Process: Trivial Policy Evaluation

The rewards for this problem are defined by:
$r_\mathcal{X} = r_\mathcal{X}^{u=\text{Productive}} = r_\mathcal{X}^{u=\text{Lazy}} = \begin{bmatrix}
-1\\
-1\\
-1\\
-1\\
-1\\
0\\
\end{bmatrix}$.

How can we interprete these rewards?
Evaluate both the lazy policy and the productive policy using $\gamma = 0.9$.

Bonus question: Can we evaluate the state-value of $\lbrace x=\text{More Sleep}, u=\text{Lazy}\rbrace$ for an infinite time horizon without the use of the Bellman equation?

YOUR ANSWER HERE


```python
import numpy as np

# YOUR CODE HERE
raise NotImplementedError()
```


```python
# Bonus question: Can we evaluate the state-value of {𝑥=More Sleep,𝑢=Lazy} for an infinite time horizon without the use of the Bellman equation?


# YOUR CODE HERE
raise NotImplementedError()
```

## 6) Action-Value Function Evalution

Now, the policy is defined by:
\begin{align}
\pi(u_k=\text{Productive} | x_k)&=\alpha,\\
\pi(u_k=\text{Lazy} | x_k)&=1-\alpha, \forall x_k \in \mathcal{X}
\end{align}

Calculate action-values for the problem as described using the 'fifty-fifty' policy ($\alpha = 0.5$) according to the Bellman Expectation Equation: $q_\pi(x_k, u_k) = \mathcal{R}^u_x + \gamma \sum_{x_{k+1} \in \mathcal{X}} p^u_{xx'} v_\pi(x_{k+1})$ $\forall x_k, u_k \in \mathcal{X}, \mathcal{U}$.

## 6) Solution



```python
import numpy as np

gamma = 0.9
alpha = 0.5
no_states = 6
no_actions = 2
r_X = np.array([-1, -1, -1, -1, -1, 0]).reshape(-1, 1)
q_XU = np.zeros([no_states, no_actions])
# YOUR CODE HERE
raise NotImplementedError()
```

## 7) Markov Decision Problem: Stochastic Policy Evalution

Plot the state-value of the states "Lecture" and "Study" for different $\alpha$. What do we see? Why?

## 7) Solution


```python
import numpy as np
import matplotlib.pyplot as plt
plt.style.use('seaborn-talk')

n = 6 # dimension of state space
no_of_samples = 1000

alphas = np.linspace(0, 1, no_of_samples)
v_n_alpha = np.zeros([n, no_of_samples])

# YOUR CODE HERE
raise NotImplementedError()
```


```python
plt.figure(figsize=[10, 6])
states = ["Hangover", "Sleep", "More Sleep", "Visit Lecture", "Study", "Pass Exam"]
alphas = alphas.flatten()
for state, vnalp in zip(states, v_n_alpha):
    ls = '--' if state in ['Visit Lecture', 'Study'] else '-'
    plt.plot(alphas, vnalp, ls=ls, label=r"$x=${}".format(state))
    
plt.legend()
plt.xlabel(r"$\alpha$")
plt.ylabel(r"$v_\pi(x)$")
plt.xlim([0, 1])
plt.ylim([-10, 0])
```

YOUR ANSWER HERE

2008c07407d76bfb64b67241186a18ae775a48e9
ipynb
Jupyter Notebook
exercises/templates/ex02/Ex2.ipynb
adilsheraz/reinforcement_learning_course_materials
e086ae7dcee2a0c1dbb329c2b25cf583c339c75a
MIT
2020-07-20T08:38:15.000Z
2022-03-31T19:30:35.000Z
exercises/templates/ex02/Ex2.ipynb
speedhunter001/reinforcement_learning_course_materials
09a211da5707ba61cd653ab9f2a899b08357d6a3
MIT
2020-07-22T07:27:55.000Z
2021-05-12T14:37:08.000Z
exercises/templates/ex02/Ex2.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