Méthodes de Monte Carlo

Reinforcement Learning avec Gymnasium en Python

Fouad Trad

Machine Learning Engineer

Récapitulatif : apprentissage fondé sur un modèle

S'appuient sur la dynamique de l'environnement
Aucune interaction avec l'environnement

Image montrant les schémas des algorithmes d'itération de politique et d'itération de valeur, vus dans la vidéo précédente.

Apprentissage sans modèle

Ne dépend pas de la dynamique de l'environnement
L'agent interagit avec l'environnement
Apprend la politique par essais et erreurs
Mieux adapté aux applications réelles

Image d'un robot interagissant avec un environnement d'échecs.

Méthodes de Monte Carlo

Techniques sans modèle
Estiment les valeurs Q à partir des épisodes

Image montrant la structure d'un épisode recueilli, comprenant états, actions, récompenses et retours.

Méthodes de Monte Carlo

Techniques sans modèle
Estiment les valeurs Q à partir des épisodes

Image montrant la deuxième étape de l'estimation des valeurs Q et l'apparence d'une table Q, avec un nombre de lignes égal au nombre d'états et un nombre de colonnes égal au nombre d'actions.

Méthodes de Monte Carlo

Techniques sans modèle
Estiment les valeurs Q à partir des épisodes

Image montrant l'étape finale pour obtenir la politique optimale, qui associe chaque état à l'action optimale.

Deux méthodes : first-visit, every-visit

Monde en grille personnalisé

Image montrant le monde en grille personnalisé incluant 6 états, avec 2 rangées et 3 colonnes, numérotés de l'angle supérieur gauche (0) à l'angle inférieur droit (5). L'agent est à l'état 3, une montagne à l'état 4, et l'objectif à l'état 5.png

Recueillir deux épisodes

Image montrant le premier épisode recueilli en termes d'états, d'actions, de récompenses et de retours.

Image montrant le deuxième épisode recueilli en termes d'états, d'actions, de récompenses et de retours.

Estimer les valeurs Q

Image montrant les états, actions, récompenses et retours recueillis pour les deux épisodes.

Table Q : tableau des valeurs Q

Image montrant une table Q vide à remplir.

Q(4, gauche), Q(4, haut) et Q(1, bas)

Image montrant les états, actions, récompenses et retours recueillis pour les deux épisodes avec (4, gauche), (4, haut) et (1, bas) mis en évidence.

(s,a) apparaît une fois -> remplir avec le retour

Table Q avec les valeurs de (4, gauche), (4, haut) et (1, bas) remplies.

Q(4, droite)

Image montrant les états, actions, récompenses et retours recueillis pour les deux épisodes avec (4, droite) mis en évidence dans les deux épisodes

(s,a) survient une fois par épisode -> moyenne

Table Q avec la valeur de (4, droite) remplie par la moyenne des retours des deux épisodes.

Q(3, droite) - Monte Carlo « first-visit »

Image montrant les états, actions, récompenses et retours recueillis pour les deux épisodes avec (3, droite) mis en évidence seulement pour la première occurrence dans les deux épisodes

Moyenne de la première visite à (s,a) dans les épisodes

Table Q avec la valeur de (3, droite) remplie par la moyenne des retours des lignes en surbrillance (premières occurrences de (3, droite)).

Q(3, droite) - Monte Carlo « every-visit »

Image montrant les états, actions, récompenses et retours recueillis pour les deux épisodes avec (3, droite) mis en évidence à chaque occurrence dans les deux épisodes

Moyenne de chaque visite à (s,a) dans les épisodes

Table Q avec la valeur de (3, droite) remplie par la moyenne des retours des lignes en surbrillance (toutes les occurrences de (3, droite)).

Générer un épisode

def generate_episode():
    episode = []
    state, info = env.reset()

    terminated = False
    while not terminated:
        action = env.action_space.sample()

        next_state, reward, terminated, truncated, info = env.step(action)

        episode.append((state, action, reward))
        state = next_state

    return episode

Monte Carlo « first-visit »

def first_visit_mc(num_episodes):
    Q = np.zeros((num_states, num_actions))
    returns_sum = np.zeros((num_states, num_actions))
    returns_count = np.zeros((num_states, num_actions))


    for i in range(num_episodes):
        episode = generate_episode()
        visited_states_actions = set()

        for j, (state, action, reward) in enumerate(episode):

            if (state, action) not in visited_states:

                returns_sum[state, action] += sum([x[2] for x in episode[j:]])

                returns_count[state, action] += 1
                visited_states_actions.add((state, action))


    nonzero_counts = returns_count != 0

    Q[nonzero_counts] = returns_sum[nonzero_counts] / returns_count[nonzero_counts]
    return Q

Monte Carlo « every-visit »

def every_visit_mc(num_episodes):
    Q = np.zeros((num_states, num_actions))
    returns_sum = np.zeros((num_states, num_actions))
    returns_count = np.zeros((num_states, num_actions))    

    for i in range(num_episodes):
        episode = generate_episode()  

        for j, (state, action, reward) in enumerate(episode):

            returns_sum[state, action] += sum([x[2] for x in episode[j:]])
            returns_count[state, action] += 1


    nonzero_counts = returns_count != 0
    Q[nonzero_counts] = returns_sum[nonzero_counts] / returns_count[nonzero_counts]
    return Q

Obtenir la politique optimale

def get_policy():
    policy = {state: np.argmax(Q[state]) for state in range(num_states)}    
    return policy

Mettre le tout ensemble

Q = first_visit_mc(1000)

policy_first_visit = get_policy()

print("First-visit policy: \n", policy_first_visit)

Q = every_visit_mc(1000)

policy_every_visit = get_policy()

print("Every-visit policy: \n", policy_every_visit)

First-visit policy:
{0: 2, 1: 2, 2: 1, 
 3: 2, 4: 2, 5: 0}

Every-visit policy:
{0: 2, 1: 2, 2: 1, 
 3: 2, 4: 2, 5: 0}

Image montrant la politique optimale avec l'action optimale à prendre dans chaque état sous forme de flèches.

Passons à la pratique !

Reinforcement Learning avec Gymnasium en Python