Q-Learning

Le Q-Learning est un algorithme de renforcement (reinforcement learning) utilisé pour apprendre la politique optimale d’un agent dans un environnement. L’agent cherche à maximiser une fonction de récompense cumulée en interagissant avec cet environnement, en prenant des actions et en recevant des récompenses basées sur ces actions.

Le cœur de l’algorithme est l’apprentissage de la fonction Q, qui associe à chaque couple état-action une valeur représentant la « qualité » de l’action prise dans cet état. L’objectif du Q-learning est d’apprendre cette fonction Q, qui permet à l’agent de choisir la meilleure action à chaque étape.

Formule de mise à jour de la fonction Q :

La mise à jour de la fonction Q suit la règle suivante :

$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left( r_t + \gamma \max_a Q(s_{t+1}, a) – Q(s_t, a_t) \right)$

$Q(s_t, a_t)$ : valeur actuelle de la fonction Q pour l’état $s_t$ et l’action $a_t$
$\alpha$ : taux d’apprentissage
$r_t$ : récompense obtenue après avoir pris l’action $a_t$ dans l’état $s_t$
$\gamma$ : facteur de discount qui indique l’importance des récompenses futures
$\max_a Q(s_{t+1}, a)$ : la valeur maximale de la fonction Q dans le prochain état $s_{t+1}$ , pour toutes les actions possibles $a$

Fonctions :

Q-Learning (exemple)

Le Q-Learning est un algorithme d’apprentissage par renforcement qui permet à un agent d’apprendre à prendre des décisions optimales en interagissant avec son environnement. Par exemple, un robot peut utiliser le Q-Learning pour apprendre à naviguer dans un labyrinthe : à chaque déplacement, il reçoit une récompense positive s’il se rapproche de la sortie, ou négative s’il heurte un mur, et ajuste progressivement ses choix pour trouver le chemin le plus efficace.

Exemple de code :

import numpy as np
import random

# Paramètres de la grille
grid_size = 5
goal_state = (4, 4)

# Hyperparamètres Q-learning
alpha = 0.1       # taux d'apprentissage
gamma = 0.9       # facteur de discount
epsilon = 0.2     # taux d'exploration
episodes = 500

# Initialiser la table Q
# (états = positions, actions = 0:haut, 1:bas, 2:gauche, 3:droite)
Q = np.zeros((grid_size, grid_size, 4))

# Fonction pour choisir une action (epsilon-greedy)
def choose_action(state):
    if random.uniform(0, 1) < epsilon:
        return random.randint(0, 3)  # exploration
    else:
        return np.argmax(Q[state[0], state[1]])  # exploitation

# Fonction de transition dans la grille
def take_action(state, action):
    i, j = state
    if action == 0 and i > 0:
        i -= 1
    elif action == 1 and i < grid_size - 1:
        i += 1
    elif action == 2 and j > 0:
        j -= 1
    elif action == 3 and j < grid_size - 1:
        j += 1
    next_state = (i, j)
    reward = 1 if next_state == goal_state else -0.01
    done = next_state == goal_state
    return next_state, reward, done

# Entraînement
for episode in range(episodes):
    state = (0, 0)
    done = False

    while not done:
        action = choose_action(state)
        next_state, reward, done = take_action(state, action)

        # Q-learning update
        best_next_action = np.max(Q[next_state[0], next_state[1]])
        Q[state[0], state[1], action] += alpha * (reward + gamma * best_next_action - Q[state[0], state[1], action])

        state = next_state

print("\nQ-table entraînée :")
print(Q)

# Test du chemin appris
print("\nChemin appris de (0,0) vers (4,4) :")
state = (0, 0)
path = [state]
while state != goal_state:
    action = np.argmax(Q[state[0], state[1]])
    state, _, _ = take_action(state, action)
    path.append(state)

print(path)

Explication du code :

1. Initialisation de l’environnement de grille - Grille de taille `5x5`. - État objectif : position `(4, 4)`. - États représentés par les positions `(i, j)` dans la grille. - 4 actions possibles par état : - `0 = haut`, `1 = bas`, `2 = gauche`, `3 = droite`.
2. Paramètres du Q-learning - `alpha = 0.1` : taux d’apprentissage (learning rate). - `gamma = 0.9` : facteur de discount pour les récompenses futures. - `epsilon = 0.2` : probabilité d’explorer (prendre une action aléatoire). - `episodes = 500` : nombre total d’épisodes d’apprentissage. - Table Q : matrice `Q[i][j][a]` initialisée à 0, où `i,j` sont les coordonnées de l’état et `a` l’action.
3. Stratégie d’exploration (epsilon-greedy) - Avec probabilité `epsilon`, une action aléatoire est choisie (exploration). - Sinon, l’action ayant la plus grande valeur Q est sélectionnée (exploitation). - `np.argmax(Q[state])` permet d’exploiter la politique actuelle.
4. Fonction de transition d’état - Mouvement dans la grille selon l’action choisie, avec limites de bord. - Récompense : - `+1` si l’état objectif `(4, 4)` est atteint. - `-0.01` pour toutes les autres transitions (pénalité légère). - Retourne le `next_state`, la `reward` et un booléen `done`.
5. Entraînement de l’agent - Pour chaque épisode : - L’agent démarre à `(0,0)` et explore jusqu’à atteindre l’objectif. - À chaque étape : - Choix d’une action via epsilon-greedy. - Mise à jour Q selon la formule : `Q[s,a] ← Q[s,a] + α * (r + γ * max(Q[s']) - Q[s,a])` - L’état est mis à jour avec `next_state`.
6. Évaluation : chemin appris
 - Une fois l’apprentissage terminé, l’agent suit la politique apprise à partir de `(0,0)`. - À chaque étape, l’action ayant la plus grande valeur Q est choisie. - Le chemin optimal est affiché jusqu’à atteindre `(4,4)`.