<jupyter_start><jupyter_text>Q-Learning In a [previous notebook](./cem.ipynb), we tackled the problem of learning an approximation to the $Q$-function via the [Cross-Entropy Method](https://link.springer.com/book/10.1007/978-1-4757-4321-0). In its most basic form, table $Q$-learning can only be applied for problems defined on small state spaces. However, when combined with deep learning it evolves into [Deep Q-learning](), which can also be applied to high-dimensional state spaces such as pixel images in [Space Invaders](https://gym.openai.com/envs/SpaceInvaders-v0/).In the present notebook, we consider **Q-Learning** as an alternative. The code is based on the highly recommendable [tutorial by <NAME>]().  Learning the Q-table Tabular Q-learning is based on the **Bellman Equation** for the state-value function $Q^*$ under the optimal policy:$$Q^*(s, a) = r + \gamma\max_{a' \in A} Q^*(s', a'),$$where $\gamma < 1$ is the discount factor and $s'$ is the state of the environment after performing the action $a$ in state $s$. In tabular $Q$-learning, we first collect tuples $(s, a, s', r)$ by having an agent interact with the environment. Then, we push the $Q$-values carefully in the direction of the values indicated by the Bellman Equation. That is, we set$$Q(s, a) \leftarrow Q(s,a) + \alpha \delta,$$where $\alpha > 0$ is a **learning rate** and $$\delta = (r + \gamma \max_{a' \in A} Q(s', a')) - Q(s, a)$$ is the **TD error**.<jupyter_code>lr = 0.8
gamma = .95

def q_step(Q, env, sigma, s):
    """Update the q-values once
    
    # Arguments
        Q: Q function
        env: environment for the problem
        sigma: strength of noise for fuzzy action selection
        s: current state
    # Result
        Q, s, r, d after the step in the environment
    """
    
    a = np.argmax(Q[s, :] + np.random.randn(1, env.nA) * sigma)
    
    ss, r, d, _ = env.step(a)
    
    delta = r + gamma * np.max(Q[ss,:]) - Q[s,a]
    Q[s, a] = Q[s, a] + lr * delta
    
    return Q, ss, r, d<jupyter_output><empty_output><jupyter_text>This approach learns the optimal policy rapidly in small state spaces. However, in larger state spaces it is no longer effective since an enormous number of runs would is necessary to update the $Q$-values of every state-action pair for a reasonably large number of iterations.  Example: Frozen Lake As an example, we return to the game ``Frozen Lake`` that we have considered already when learning about [value iteration](./valIt.ipynb).<jupyter_code>neps = int(1e3)
nsteps = int(1e2)
rList = []
Q = np.zeros((env.nS, env.nA))

for i in range(neps):
    s = env.reset()
    rTot = 0
    for _ in range(nsteps):
        Q, s, r, d = q_step(Q, env, 1 / (i + 1), s)
        rTot +=r
        if(d):
            break
    rList.append(rTot)<jupyter_output><empty_output><jupyter_text>Plotting the moving averages illustrates that we quickly learn a good policy.<jupyter_code>import seaborn as sns
%matplotlib inline
window = int(1e2)

mov_avg = np.convolve(rList, np.ones(window) / window,   'valid')
sns.tsplot(mov_avg)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12403100775193798, 'fraction_numerical': 0.011627906976744186, 'mean_word_length': 3.5678466076696167, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 15, 'https://': 2, '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': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '359771', 'license': 'MIT', 'n_tokens_mistral': 1045, 'n_tokens_neox': 995, 'n_words': 392, 'path': 'notebooks/tabular.ipynb', 'repo_name': 'Christian-Hirsch/Space_Invaders', 'size': '3104'}