<jupyter_start><jupyter_text><jupyter_code>%pip install -q -U gtbook
import numpy as np
import gtsam
import pandas as pd

import gtbook
import gtbook.display
from gtbook import vacuum
from gtbook.discrete import Variables
VARIABLES = Variables()
def pretty(obj): 
    return gtbook.display.pretty(obj, VARIABLES)
def show(obj, **kwargs): 
    return gtbook.display.show(obj, VARIABLES, **kwargs)

# From section 3.2:
N = 5
X = VARIABLES.discrete_series("X", range(1, N+1), vacuum.rooms)
A = VARIABLES.discrete_series("A", range(1, N), vacuum.action_space)

# From section 3.5:
conditional = gtsam.DiscreteConditional((2,5), [(0,5), (1,4)], vacuum.action_spec)
R = np.empty((5, 4, 5), float)
T = np.empty((5, 4, 5), float)
for assignment, value in conditional.enumerate():
    x, a, y = assignment[0], assignment[1], assignment[2]
    R[x, a, y] = 10.0 if y == vacuum.rooms.index("Living Room") else 0.0
    T[x, a, y] = value<jupyter_output><empty_output><jupyter_text>Reinforcement Learning> We will talk about model-based and model-free learning. **This Section is still in draft mode and was released for adventurous spirits (and TAs) only.**<jupyter_code>from gtbook.display import randomImages
from IPython.display import display
display(randomImages(3, 6, "steampunk", 1))<jupyter_output><empty_output><jupyter_text>Exploring to get Data> Where we gather experience. Let's adapt the `policy_rollout` code from the previous section to generate a whole lot of experiences of the form $(x,a,x',r)$.<jupyter_code>def explore_randomly(x1, horizon=N):
    """Roll out states given a random policy, for given horizon."""
    data = []
    x = x1
    for _ in range(1, horizon):
        a = np.random.choice(4)
        next_state_distribution = gtsam.DiscreteDistribution(X[1], T[x, a])
        x_prime = next_state_distribution.sample()
        data.append((x, a, x_prime, R[x, a, x_prime]))
        x = x_prime
    return data<jupyter_output><empty_output><jupyter_text>Let us use it to create 499 experiences and show the first 10:<jupyter_code>data = explore_randomly(vacuum.rooms.index("Living Room"), horizon=500)
print(data[:10])<jupyter_output>[(0, 2, 0, 10.0), (0, 0, 0, 10.0), (0, 3, 3, 0.0), (3, 0, 2, 0.0), (2, 1, 3, 0.0), (3, 0, 2, 0.0), (2, 2, 2, 0.0), (2, 2, 2, 0.0), (2, 1, 3, 0.0), (3, 0, 2, 0.0)]<jupyter_text>Model-based Reinforcement Learning> Just count, then solve the MDP. We can *estimate* the transition probabilities $T$ and reward table $R$ from the data, and then we can use the algorithms from before to calculate the value function and/or optimal policy.The math is just a variant of what we saw in the learning section of the last chapter. The rewards is easiest:$$R(x,a,x') \approx \frac{1}{N(x,a,x')} \sum_{x,a,x'} r$$where $N(x,a,x')$ counts how many times an experience $(x,a,x')$ was recorded. The transition probabilities are a bit trickier:$$P(x'|x,a) \approx \frac{N(x,a,x)}{N(x,a)}$$where $N(x,a)=\sum_{x'} N(x,a,x')$ is the number of times we took action $a$ in a state $x$. The code associated with that is fairly simple, modulo some numpy trickery to deal with division by zero and *broadcasting* the division:<jupyter_code>R_sum = np.zeros((5, 4, 5), float)
T_count = np.zeros((5, 4, 5), float)
count = np.zeros((5, 4), int)
for x, a, x_prime, r in data:
    R_sum[x, a, x_prime] += r
    T_count[x, a, x_prime] += 1
R_estimate = np.divide(R_sum, T_count, where=T_count!=0)
xa_count = np.sum(T_count, axis=2)
T_estimate = T_count/np.expand_dims(xa_count, axis=-1)<jupyter_output><empty_output><jupyter_text>Above `T_count` corresponds to $N(x,a,x')$, and the variable `xa_count` is $N(x,a)$. It is good to check the latter to see whether our experiences were more or less representative, i.e., visited all state-action pairs:<jupyter_code>xa_count<jupyter_output><empty_output><jupyter_text>This seems pretty good. If not, we can always gather more data, which we encourage you to experiment with.We can compare the ground truth transition probabilities $T$ with the estimated transition probabilities $\hat{T}$, e.g., for the living room:<jupyter_code>print(f"ground truth:\n{T[0]}")
print(f"estimate:\n{np.round(T_estimate[0],2)}")<jupyter_output>ground truth:
[[1.  0.  0.  0.  0. ]
 [0.2 0.8 0.  0.  0. ]
 [1.  0.  0.  0.  0. ]
 [0.2 0.  0.  0.8 0. ]]
estimate:
[[1.   0.   0.   0.   0.  ]
 [0.19 0.81 0.   0.   0.  ]
 [1.   0.   0.   0.   0.  ]
 [0.14 0.   0.   0.86 0.  ]]<jupyter_text>Not bad. And for the rewards:<jupyter_code>print(f"ground truth:\n{R[0]}")
print(f"estimate:\n{np.round(R_estimate[0],2)}")<jupyter_output>ground truth:
[[10.  0.  0.  0.  0.]
 [10.  0.  0.  0.  0.]
 [10.  0.  0.  0.  0.]
 [10.  0.  0.  0.  0.]]
estimate:
[[10.  0.  0.  0.  0.]
 [10.  0.  0.  0.  0.]
 [10.  0.  0.  0.  0.]
 [10.  0.  0.  0.  0.]]<jupyter_text>In summary, learning in this context can simply be done by gathering lots of experiences, and estimating models for how the world behaves.  Model-free Reinforcement Learning> All you need is Q, la la la la. A different, model-free approach is **Q_learning**. In the above we tried to *model* the world by trying estimate the (large) transition and reward tables. However, remember from the previous section that there is a much smaller table of Q-values $Q(x,a)$ that also allow us to act optimally, because we have$$\pi^*(x) = \arg \max_a Q^*(x,a)$$where the Q-values are defined as$$Q^*(x,a) \doteq \bar{R}(x,a) + \gamma \sum_{x'} P(x'|x, a) V^*(x')$$This begs the question whether we can simply learn the Q-values instead, which might be more *sample-efficient*, i.e., we would get more accurate values with less training data, as we have less quantities to estimate.To do this, remember that the Bellman equation can be written as $$V^*(x) = \max_a Q^*(x,a)$$allowing us to rewrite the Q-values from above as $$Q^*(x,a) = \sum_{x'} P(x'|x, a) \{ R(x,a,x') + \gamma \max_{a'} Q^*(x',a') \}$$This gives us a way to estimate the Q-values, as we can approximate the above using a Monte Carlo estimate, summing over our experiences:$$Q^*(x,a) \approx \frac{1}{N(x,a)} \sum_{x,a,x'} R(x,a,x') + \gamma \max_{a'} Q^*(x',a')$$Unfortunately the estimate above *depends* on the optimal Q-values. Hence, the final Q-learning algorithm applies this estimate gradually, by "alpha-blending" between old and new estimates, which also averages over the reward:$$\hat{Q}(x,a) \leftarrow (1-\alpha) \hat{Q}(x,a) + \alpha \{R(x,a,x') +  \gamma \max_{a'} \hat{Q}(x',a') \}$$In code:<jupyter_code>alpha = 0.5 # learning rate
gamma = 0.9 # discount factor
Q = np.zeros((5, 4), float)
for x, a, x_prime, r in data:
    old_Q_estimate = Q[x,a]
    new_Q_estimate = r + gamma * np.max(Q[x_prime])
    Q[x, a] = (1.0-alpha) * old_Q_estimate + alpha * new_Q_estimate
print(Q)<jupyter_output>[[84.81793141 74.78943818 87.23744972 71.16209362]
 [85.78854973 73.52011122 73.02514028 60.90818195]
 [52.42934192 67.64563199 52.22683159 43.43022893]
 [54.28411796 59.33905004 84.23076831 69.8358031 ]
 [68.60452978 53.89759237 65.17961712 60.7351691 ]]
{'fraction_non_alphanumeric': 0.15472289499928765, 'fraction_numerical': 0.06054993588830318, 'mean_word_length': 4.180811808118081, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 37, 'https://': 0, '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': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '29564', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 2890, 'n_tokens_neox': 2622, 'n_words': 859, 'path': 'S36_vacuum_RL.ipynb', 'repo_name': 'gtbook/robotics', 'size': '7019'}