---
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
---

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

(projects:frozen-lake:dynamic-programming)=
# Dynamic Programming

Read [](reinforcement:dynamic-programming) before you start.

In this project (and all others of this project series) we use the grid world simulator [Frozen Lake](https://gymnasium.farama.org/environments/toy_text/frozen_lake/) originally developed by [OpenAI](https://openai.com/) in their `gym` package (until they removed the 'non' in 'non-profit organization) and now maintained by the non-profit [Farama Foundation](https://farama.org/) in their `gymnasium` package. See [Announcing The Farama Foundation](https://farama.org/Announcing-The-Farama-Foundation) for some more background information on this transition.

**Task:** Read about [Gymnasium](https://gymnasium.farama.org/) and the [Frozen Lake simulator](https://gymnasium.farama.org/environments/toy_text/frozen_lake/). Then install Gymnasium.

## The Environment

**Task:** Create the standard 8-by-8 Frozen Lake environment object and render the environment. Use `is_slippery=True`

**Solution:**

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

+++ {"user_expressions": []}

**Task:** Write your own `render` function for getting a more pleasant rendering. It should take the environment as argument. The frozen lake map is contained as list of lists (rows) in `env.desc`. Note that we want to test dynamic programming. So we do not care about a starting position, because we will solve the problem for all starting positions at once.

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

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

**Task:** Get the environment dynamics for $p(s',r,s,a)$ for all arguments (four dimensional array). Relevant information is in `env.P`. Check that $p(0,0,0,0)=2/3$, else your solution is not correct.

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

+++ {"user_expressions": []}

## Value Iteration

**Task:** Implement asynchronous value iteration to get the optimal state-value function $v_\ast$. Use $\gamma=1$. Show values in an 8-by-8 grid.

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

+++ {"user_expressions": []}

**Task:** From optimal state values get optimal action values.

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

+++ {"user_expressions": []}

**Task:** Get an optimal policy from optimal action values.

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

+++ {"user_expressions": []}

**Task:** Visualize the policy.

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

+++ {"user_expressions": []}

**Task:** Run your code with the following parameters and explain what you see (optimal value function, optimal policy):
* `slippery=False`, $\gamma=0.5$
* `slippery=False`, $\gamma=0$
* `slippery=False`, $\gamma=1$
* `slippery=True`, $\gamma=0.5$
* `slippery=True`, $\gamma=0$
* `slippery=True`, $\gamma=1$

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

## Policy Iteration

**Task:** Implement policy iteration for state values. Use a deterministic random initial policy.

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