<jupyter_start><jupyter_text>Value Iteration In this notebook, we meet **value iteration** as a first basic method to approach RL problems. Value iteration is a planning algorithm and is therefore an example for [model-based learning](http://rail.eecs.berkeley.edu/deeprlcourse-fa17/f17docs/lecture_9_model_based_rl.pdf). For the code example, we build on the intelligible [blog post by <NAME>](https://medium.com/@m.alzantot/deep-reinforcement-learning-demysitifed-episode-2-policy-iteration-value-iteration-and-q-978f9e89ddaa).  Example: Frozen Lake As motivating example, we consider the game ``Frozen Lake``, which exhibits reasonably small state and action spaces. The [description](https://gym.openai.com/envs/FrozenLake-v0/) reads as follows: *Winter is here. You and your friends were tossing around a frisbee at the park when you made a wild throw that left the frisbee out in the middle of the lake. The water is mostly frozen, but there are a few holes where the ice has melted. If you step into one of those holes, you'll fall into the freezing water. At this time, there's an international frisbee shortage, so it's absolutely imperative that you navigate across the lake and retrieve the disc. However, the ice is slippery, so you won't always move in the direction you intend.*<jupyter_code>import gym
env = gym.make('FrozenLake-v0')
print(env.nS)
print(env.nA)

s = env.reset()
env.render()
env.step(env.action_space.sample())
env.render()<jupyter_output><empty_output><jupyter_text>How do we find a policy to maximize our average chances for reaching the target?  Value Iteration Value iteration is based on the principle of [dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming). To each state $s$ in the state space $S$, we introduce the **value function**$$V^*(s) = \max_{\pi }\mathbb E_{\pi}[R|s_0 = s]$$as the expected rewards when following the optimal policy $\pi = \pi_\mathsf{opt}$. In order to determine $V^*(s)$, we proceed recursively and first initialize $V^0(s) = 0$ for all $s \in S$. When $V^n(s)$ is constructed, we determine an approximation $Q^n(s,a)$ of the **state-value function** via computing the expected rewards for an action $a$ in the action space $A$ given the current value function:$$Q^n(s, a) = \sum_{s' \in S} p(s' | s, a) \big(r(s, a, s') + V^n(s')\big).$$ Then, the value of the new state results from maximizing over all possible actions$$V^{n + 1}(s) = \max_{a \in A} Q^n(s, a).$$ At this point, we understand why value iteration is a model-based approach. The dynamic programming is only feasible if the transition probabilities are known.<jupyter_code>import numpy as np

def dyn_prog(v, env):
    """A dynamic programming step in value iteration
    
    # Arguments
        v: current value function
        env: environment for the problem
    # Result
        updated value function
    """
    v_new = np.zeros(env.nS)
    for s in range(env.nS):
        q_sa = [sum([p * (r + v[ss]) for p, ss, r, _ in env.P[s][a]]) 
                for a in range(env.nA)] 
        v_new[s] = max(q_sa)
    return v_new<jupyter_output><empty_output><jupyter_text>In value iteration, we now derive increasingly precise estimates of the value function by iterating the dynamic-programming step.<jupyter_code>def value_iteration(niter, env):
    """Value iteration
    
    # Arguments
        niter: number of iterations
        env: environment for the problem
    # Result
        estimate for value function after value iteration
    """
    v = np.zeros((iters, env.nS))
    for i in range(iters - 1):
        v[i + 1, :] = dyn_prog(v[i, :], env)        
    return v<jupyter_output><empty_output><jupyter_text>Visualization Now, we visualize how quickly value iteration converges to the true value function.<jupyter_code>import pandas as pd
%matplotlib inline 

niter = int(1.5e2)

val_trace = value_iteration(niter, env)
df = pd.DataFrame(val_trace)
df.plot(legend = False)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10526315789473684, 'fraction_numerical': 0.0057919919415764295, 'mean_word_length': 4.1384217335058215, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 18, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '266189', 'license': 'MIT', 'n_tokens_mistral': 1247, 'n_tokens_neox': 1197, 'n_words': 469, 'path': 'notebooks/valIt.ipynb', 'repo_name': 'Christian-Hirsch/Space_Invaders', 'size': '3982'}