---
jupytext:
  formats: content_md///md:myst,content///ipynb
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.14.4
kernelspec:
  display_name: Python 3 (ipykernel)
  language: python
  name: python3
---

+++ {"user_expressions": [], "tags": []}

(exercises:reinforcement:markov)=
# Markov Decision Processes

Before solving these exercises you should have read [](reinforcement:markov).

We consider a tiny 3-by-3 grid world.

![The 3-by-3 grid world](grid-3-by-3.svg)

State information contains the agent's position only. Actions are 'go left', 'go right', 'go up', 'go down'. Invalid actions do not change state. Moving to cell 5 yields reward 1 and places the agent randomly on 2, 4, 6 or 8. All other rewards are 0.

## Environment

**Task:** How many different states do we have in this grid world? Is moving in this grid world and collecting as much reward as possible an episodic or a continuing task? Is the task stationary or non-stationary?

**Solution:**

```{code-cell} ipython3
# your answer
```

**Task:** Write down the environment dynamics $p$ for the grid world defined above.

**Solution:**

```{code-cell} ipython3
# your answer
```

## Policies

**Task:** Write down the uniformly random policy for the grid world.

**Solution:**

```{code-cell} ipython3
# your answer
```

**Task:** Find a deterministic policy that maximizes return (with discount factor $\gamma<1$).

**Solution:**

```{code-cell} ipython3
# your answer
```

**Task:** Are there policies that maximize return for $\gamma=1$, but not for $\gamma<1$?

**Solution:**

```{code-cell} ipython3
# your answer
```

## Bellman Equations

**Task:** Write down the Bellman equations for state values for the deterministic policy 1→2→3→6→9→8→7→4→5. Solve the equations for different $\gamma$ (try $\gamma=1$, too). Then calculate action values from the state values.

**Solution:**

```{code-cell} ipython3
# your answer
```

**Task:** Calculate the state-value function for your return maximizing policy from above. Prove that the policy is indeed optimal.

**Solution:**

```{code-cell} ipython3
:tags: []
:user_expressions: []

# your answer
```
