Apprentissage par renforcement

📐 L'essentiel à connaître

Tout ce qu'il faut pour réussir les annales sur l'apprentissage par renforcement : formules clés, méthode pas à pas pour Value Iteration, mise à jour du Q-Learning, et réflexes d'exercice (modéliser une grille, nombre de MAJ de V, critères d'arrêt).

1 · MDP & propriété de Markov

Un MDP est le quintuplet $(S, A, T, R, \gamma)$ :

$S$ : ensemble d'états · $A$ : ensemble d'actions
$T(s, a, s')$ : probabilité de passer de $s$ à $s'$ avec l'action $a$
$R(s, a)$ : récompense (moyenne) reçue après l'action
$\gamma \in [0, 1[$ : facteur d'actualisation

Propriété de Markov : le futur ne dépend que du présent, pas du passé (processus « sans mémoire »).

2 · Fonction de valeur & équation de Bellman

$$V^\pi(s) = \mathbb{E}^\pi\!\left[ \sum_{t=0}^{\infty} \gamma^t \, r_t \right] \qquad V^*(s) = \max_\pi V^\pi(s)$$

Équation de Bellman (optimalité) $$V^*(s) = \max_a \left[ R(s, a) + \gamma \sum_{s'} T(s, a, s') \, V^*(s') \right]$$ $$\pi^*(s) = \text{argmax}_a \left[ R(s, a) + \gamma \sum_{s'} T(s, a, s') \, V^*(s') \right]$$

3 · Value Iteration (modèle connu)

$$Q(s, a) = R(s, a) + \gamma \sum_{s'} T(s, a, s') \, V_k(s') \qquad V_{k+1}(s) = \max_a Q(s, a)$$

📝 Méthode pas à pas (entamer / dérouler)

Initialiser $V_0(s) = 0$ pour tout état $s$.
Itération 1 : comme $V_0 = 0$ partout, $V_1(s) = \max_a \big[R(s,a) + \gamma \cdot 0\big] = \max_a R(s, a)$.
→ chaque case reçoit le maximum de ses récompenses immédiates (ex : les cases adjacentes à la cible obtiennent la récompense de la cible).
Itérations suivantes : $V_{k+1}(s) = \max_a \big[R(s,a) + \gamma \, V_k(s')\big]$. La valeur de la cible diffuse d'une case par itération, amortie par $\gamma$.
On s'arrête à la convergence, puis on déduit $\pi^*$ par argmax.

4 · Q-Learning (model-free)

Règle de mise à jour $$Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$$

$\alpha$ (learning rate, $\in [0,1]$) : compromis ancienne valeur / nouvelle valeur. $\alpha \to 0$ : on garde l'ancien $Q$ ; $\alpha \to 1$ : on remplace par la cible.
$\gamma$ (actualisation) : poids du futur. $\gamma \to 0$ : court terme ; $\gamma \to 1$ : long terme.
$\varepsilon$-greedy : avec proba $\varepsilon$ action aléatoire (exploration), sinon $\text{argmax}_a Q$ (exploitation). $\varepsilon \to 0$ : exploitation ; $\varepsilon \to 1$ : exploration.

Comment lire / utiliser l'output

Value Iteration renvoie $V^*(s)$ (une valeur par état) → on en déduit $\pi^*(s) = \text{argmax}_a \big[R(s,a) + \gamma \sum_{s'} T(s,a,s') V^*(s')\big]$.
Q-Learning renvoie la table $Q(s, a)$ (une valeur par couple état-action) → on en déduit $V^*(s) = \max_a Q^*(s,a)$ et $\pi^*(s) = \text{argmax}_a Q^*(s, a)$.

5 · Réflexes annales

Modéliser une grille : états $S$ = cases ; actions $A$ = {↑ ↓ ← →}
Transition $T$ déterministe ; hors grille / mur → on reste sur place
Récompense $R$ selon le barème du sujet (cible $+$, piège $-$, sinon pénalité légère)
Piège et cible = états absorbants (terminaux)
Nb de MAJ de $V(s)$ sur $N$ itérations : chaque état non absorbant est mis à jour $N$ fois
Les états absorbants (piège, cible) ne sont PAS mis à jour → 0 fois
Ex : grille 5×5, 2 absorbants, 1000 itér. → 23 états × 1000, 2 × 0
Critère d'arrêt 1 : nombre maximal d'itérations atteint
Critère d'arrêt 2 : $\max_s |V_{k+1}(s) - V_k(s)| < \varepsilon$ (convergence)
Entamer VI : $V_0 = 0$ → $V_1(s) = \max_a R(s, a)$
Déduire $\pi^*$ : argmax de l'action menant au voisin de plus grande valeur
Q-Learning : model-free → pas besoin de connaître $T$ ni $R$
Exploration vs exploitation gérée par $\varepsilon$ ($\varepsilon$-greedy)

📄 Ressources du cours

📥 Télécharger les slides · 🔗 Ouvrir dans un nouvel onglet · 📝 Ouvrir le TD/TP

🎥 Vidéos recommandées

🇫🇷 Q-Learning: Model Free Reinforcement Learning and Temporal Difference Learning
Steve Brunton · 35:35 · 96k vues — Here we describe Q-learning, which is one of the most popular methods in reinforcement learning. Q-learning is a type of temporal difference learning. We d...
🇫🇷 Q-learning - Explained!
CodeEmporium · 11:54 · 24k vues — Let's talk about one of the more important concepts in reinforcement learning: q-learningABOUT ME⭕ Subscribe: https://www.youtube.com/c/CodeEmporium?sub_conf
🇬🇧 #1. Q Learning Algorithm Solved Example | Reinforcement Learning | Machine Learning by Mahesh Huddar
Mahesh Huddar · 11:11 · 142k vues — #1. Q Learning Algorithm Solved Example | Reinforcement Learning | Machine Learning by Mahesh HuddarIntroduction to Reinforcement Learning: https://www.youtu...

1. Idée générale

L'apprentissage par renforcement est un type d'apprentissage où un agent apprend à agir dans un environnement grâce à ses interactions avec celui-ci.

L'agent fait une action, reçoit un retour de l'environnement, puis ajuste son comportement pour améliorer ses choix futurs.

Agent → action → Environnement → récompense → Agent (ou punition)

Le principe est donc basé sur :

essai → erreur → récompense / punition → amélioration

L'objectif de l'agent est de choisir ses actions de manière à maximiser le cumul des récompenses à long terme.

2. Agent, environnement, état, action, récompense

Un problème d'apprentissage par renforcement contient plusieurs éléments importants :

Élément	Définition	Exemple
Agent	Celui qui prend les décisions	Robot, joueur
Environnement	Le monde dans lequel l'agent agit	Grille, labyrinthe
État $S$	La situation actuelle de l'environnement	Position de l'agent, case actuelle
Action	Un choix possible de l'agent	Haut, bas, gauche, droite
Récompense	Retour donné par l'environnement après une action	$+1$, $-1$, $0$

3. Déroulement d'une interaction

Le déroulement d'une interaction agent ↔ environnement se fait en 5 étapes :

L'agent observe l'état courant $S$
Il choisit une action $A$
L'environnement change d'état
L'agent reçoit une récompense $R$
L'agent utilise cette information pour améliorer sa stratégie

Schéma
Environnement ←—— Récompense R, Perception π(S) ——→ Agent
Environnement ←—— Action A ——— Agent

L'agent doit donc apprendre à associer une action à chaque état — c'est ce qu'on appelle apprendre une stratégie.

4. Stratégie ou Policy

Une stratégie définit le comportement de l'agent.

Cas déterministe

$$\pi : S \to A$$

À chaque état $S$ on associe une action $A$.

Exemple $\pi(S_1) = $ droite, $\pi(S_2) = $ bas, $\pi(S_3) = $ haut, …

L'agent ne cherche pas seulement une action bonne immédiatement, mais une stratégie qui maximise le gain à long terme.

Cas probabiliste

Une stratégie peut aussi être probabiliste : à chaque état, l'agent tire une action selon une distribution de probabilités.

Selon le modèle utilisé pour pondérer les actions, le déroulement de l'agent peut être différent même dans le même environnement.

5. Propriété de Markov

Propriété de Markov Le futur dépend uniquement du présent et pas de l'historique. $$P(X_{t+1} = y \mid X_t = x, X_{t-1} = x_{t-1}, \ldots, X_0 = x_0) = P(X_{t+1} = y \mid X_t = x)$$

Autrement dit, le futur dépend du présent, pas du passé.

Chaîne de Markov

Une chaîne de Markov est une suite d'états qui respecte la propriété de Markov. On a une suite $X_0 \to X_1 \to X_2 \to \ldots$ — chaque état dépend uniquement de l'état précédent.

Exemple Course → Course → Pause

Dans une chaîne de Markov, on peut résumer les probabilités de passage avec une matrice de transition.

Matrice de transition

Elle contient les probabilités de passer d'un état à un autre :

$$P_{ij} = P(X_{t+1} = j \mid X_t = i) = \text{proba de passer de l'état } i \text{ à l'état } j$$

Propriétés :

La matrice a une ligne par état de départ et une colonne par état d'arrivée
La somme de chaque ligne vaut 1, car à partir d'un état on doit forcément aller vers un des états possibles

6. Processus de décision Markovien (MDP)

Une chaîne de Markov ne contient que des états et des transitions. Mais en apprentissage par renforcement, il faut aussi modéliser les actions.

On utilise donc un Processus de Décision Markovien (MDP).

Un MDP est défini par

$S$ : ensemble d'états
$A$ : ensemble d'actions
$T(s, a, s')$ : probabilité de passer de l'état $s$ à l'état $s'$ avec l'action $a$
$R(s, a)$ : récompense reçue après l'action
$\gamma$ : facteur d'actualisation

7. Fonction de valeur $V^\pi(S)$

La valeur d'un état mesure ce que l'agent peut espérer gagner à long terme en partant de cet état.

Pour une stratégie donnée $\pi$ :

$$V^\pi(S) = \text{valeur de l'état } S \text{ si l'agent suit la stratégie } \pi$$ $$V^\pi(S) = \mathbb{E}^\pi\!\left[ \sum_{t=0}^{\infty} \gamma^t \, r_t \right]$$

8. Valeur optimale $V^*(S)$

La valeur optimale d'un état est la meilleure valeur possible qu'on peut obtenir à partir de cet état :

$$V^*(S) = \max_\pi \mathbb{E}\!\left[ \sum_{t=0}^{\infty} \gamma^t \, r_t \right]$$

C'est le meilleur cumul de gain possible à partir de cet état.

9. Les 3 modèles d'optimalité

Il y a 3 façons de prendre en compte le futur dans les décisions de l'agent :

a) Modèle à horizon fini (MHF)

On regarde seulement les $h$ prochaines récompenses :

$$G = \sum_{t=0}^{h} r_t$$

Pour $h = 3$ : $G = r_1 + r_2 + r_3$. Modèle utile quand on veut optimiser sur un horizon limité.

b) Modèle à horizon infini (MHI) avec facteur d'actualisation

On prend en compte toutes les récompenses futures, mais les récompenses lointaines comptent moins :

$$G = \sum_{t=0}^{\infty} \gamma^t \, r_t, \quad 0 \le \gamma \le 1$$

$\gamma$ est le facteur d'actualisation.

📌 Interprétation

$\gamma$ proche de 0 → l'agent privilégie le court terme
$\gamma$ proche de 1 → l'agent prend fortement en compte le long terme

c) Modèle à récompense moyenne

On regarde la récompense moyenne à long terme :

$$\lim_{h \to \infty} \frac{1}{h} \sum_{t=0}^{h} r_t$$

L'objectif est d'avoir la meilleure moyenne de récompense sur une longue période.

10. Équation de Bellman

Elle permet de relier la valeur d'un état aux valeurs des états suivants.

Pour un MDP

$$V^*(S) = \max_a \left[ R(s, a) + \gamma \sum_{s'} T(s, a, s') \, V^*(s') \right]$$

Pour une chaîne de Markov

$$V(S) = R_s + \gamma \sum_{s'} P_{s, s'} \, V(s')$$

Interprétation Valeur d'un état = récompense immédiate + futures récompenses actualisées.

On prend la valeur de chaque état et on multiplie par la probabilité d'être dans cet état.

11. Value Iteration

Value Iteration est un algorithme qui permet d'approcher $V^*(S)$.

Objectif : trouver la stratégie optimale $\pi^*$.

Principe

Initialiser les valeurs $V(S)$ à 0 ou à des valeurs aléatoires
Répéter plusieurs fois :
- Pour chaque état $s$ :
  - Pour chaque action $a$ : calculer la valeur possible $Q(s, a)$
  - Garder le maximum : $V(s) = \max_a Q(s, a)$
Quand les valeurs se stabilisent, on déduit la stratégie optimale

Formules clés

$$Q(s, a) = R(s, a) + \gamma \sum_{s'} T(s, a, s') \, V(s')$$ $$V(s) = \max_a Q(s, a)$$

12. Policy Iteration

Policy Iteration est un autre algorithme pour trouver une stratégie optimale. Contrairement à Value Iteration, il manipule directement la stratégie.

Principe

Choisir une stratégie initiale $\pi$
Évaluer cette stratégie en calculant $V^\pi$
Améliorer la stratégie en choisissant de meilleures actions
Répéter jusqu'à ce que la stratégie ne change plus

À retenir

Value Iteration cherche d'abord $V^*$
Policy Iteration améliore directement $\pi$

13. Q-Learning

Le Q-Learning est un algorithme model-free : on ne connaît pas le modèle (T, R) à l'avance. L'agent apprend directement à partir de ses interactions avec l'environnement.

Il apprend la qualité d'une action dans un état :

$Q(s, a)$ = qualité de faire l'action $a$ dans l'état $s$.
Plus précisément, $Q^*(s, a)$ représente la récompense cumulée moyenne si l'agent :

Est dans l'état $s$
Exécute l'action $a$
Se comporte de manière optimale ensuite

Une fois la table $Q$ apprise, on peut déduire la stratégie optimale :

$$V^*(s) = \max_a Q^*(s, a) \qquad \pi^*(s) = \mathrm{argmax}_a \; Q^*(s, a)$$

Exploration vs Exploitation

Dans Q-Learning, l'agent doit choisir entre 2 comportements pour savoir quelle action exécuter :

🎯 Exploitation
Il choisit l'action qui semble être la meilleure. C'est-à-dire l'action avec la meilleure valeur $Q(s, a)$.

🔍 Exploration
Il choisit une action aléatoire pour découvrir de nouvelles possibilités.

Pour choisir, on utilise un paramètre $\varepsilon$ — le taux d'exploration (de manière aléatoire) :

$0 \longleftarrow \varepsilon \longrightarrow 1$
On choisit Exploitation ←→ On choisit Exploration

MAJ du Q-Learning

La formule principale du Q-Learning est :

$$Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$$

$\alpha$ (learning rate) : compromis ancienne valeur / nouvelle valeur
$r$ : récompense reçue
$\max_{a'} Q(s', a')$ : meilleure valeur future depuis le nouvel état
$\gamma$ : facteur d'actualisation

Déroulement de l'algorithme

Tant que le critère d'arrêt n'est pas atteint (ex : nb_iter < N) :
Commencer dans un état $S_0$ de départ
Tant qu'on n'a pas atteint un certain événement :
- Choisir une action $a$ (avec ε-greedy : Exploit ou Explore)
- Exécuter l'action $a$, observer la récompense $r$
- Mettre à jour $Q(s, a)$ avec la formule ci-dessus

14. Convergence du Q-Learning

Critère d'arrêt Le Q-Learning s'arrête lorsqu'il converge vers $Q^*$ — c'est-à-dire quand les valeurs qu'on calcule se stabilisent.

🧪 Simulation interactive

Lance l'agent dans une grille 3×3 et observe comment la table Q évolue par essai-erreur. Départ en bas à gauche, objectif 🏆 (+1) en haut à droite, piège 💀 (−1) au centre. Joue avec les hyperparamètres (α, γ, ε) pour voir leur effet.

α mémoire γ futur ε exploration

★ Réviser le chapitre

Pour vérifier ta compréhension

Quel est le principe de l'apprentissage par renforcement ?

Un agent apprend à agir dans un environnement par essai-erreur. Boucle : observer l'état $S$ → choisir une action $A$ → l'environnement change d'état → recevoir une récompense $R$ → ajuster la stratégie. Objectif : maximiser le cumul des récompenses à long terme.

Quelle est la propriété de Markov et pourquoi est-elle utile ?

$P(X_{t+1} = y \mid X_t, X_{t-1}, \ldots, X_0) = P(X_{t+1} = y \mid X_t)$. Le futur dépend uniquement du présent, pas du passé. Utile car cela permet de modéliser le problème avec une matrice de transition (chaîne de Markov) ou un MDP, sans avoir à stocker tout l'historique des états.

Quels sont les 5 composants d'un MDP ?

Un Processus de Décision Markovien est défini par :

$S$ : ensemble d'états
$A$ : ensemble d'actions
$T(s, a, s')$ : probabilité de passer de $s$ à $s'$ avec l'action $a$
$R(s, a)$ : récompense reçue après l'action
$\gamma$ : facteur d'actualisation

Quels sont les 3 modèles d'optimalité possibles ?

(a) Modèle à horizon fini (MHF) : on regarde les $h$ prochaines récompenses ($G = \sum_{t=0}^{h} r_t$).
(b) Modèle à horizon infini (MHI) avec facteur d'actualisation $\gamma$ : toutes les récompenses, pondérées ($G = \sum_t \gamma^t r_t$). $\gamma \to 0$ = court terme, $\gamma \to 1$ = long terme.
(c) Modèle à récompense moyenne : $\lim_{h \to \infty} \frac{1}{h} \sum r_t$.

Quelle est la différence entre Value Iteration et Policy Iteration ?

Value Iteration cherche d'abord $V^*(S)$ en itérant l'équation de Bellman, puis déduit la stratégie optimale $\pi^*$. Policy Iteration manipule directement la stratégie : choisir $\pi$ initiale → l'évaluer ($V^\pi$) → l'améliorer → répéter jusqu'à ce qu'elle ne change plus.

Qu'est-ce qui rend le Q-Learning « model-free » ?

Le Q-Learning ne suppose pas connu le modèle de l'environnement (transitions $T$, récompenses $R$). L'agent apprend directement à partir de ses interactions avec l'environnement la qualité $Q(s, a)$ d'une action dans un état. Une fois la table $Q^*$ apprise, on déduit $\pi^*(s) = \mathrm{argmax}_a Q^*(s, a)$.

Que représente le paramètre $\varepsilon$ et que se passe-t-il aux extrêmes ?

$\varepsilon$ est le taux d'exploration dans la stratégie ε-greedy. Avec probabilité $\varepsilon$, l'agent choisit une action aléatoire (exploration) ; avec probabilité $1 - \varepsilon$, il choisit l'action de meilleure valeur $Q$ (exploitation). $\varepsilon = 0$ = 100 % exploitation. $\varepsilon = 1$ = 100 % exploration aléatoire.

🃏 Flashcards éclair

Clique pour retourner.

Principe RL

1 boucle.

tourne →

essai → erreur → récompense/punition → amélioration.

5 éléments

du problème RL.

Agent · Environnement · État $S$ · Action $A$ · Récompense $R$

Stratégie π

Déterministe vs probabiliste.

Déterministe : $\pi : S \to A$.
Probabiliste : distribution sur les actions.

Markov

Propriété.

Le futur dépend uniquement du présent, pas du passé.

MDP

5 composants.

$(S, A, T, R, \gamma)$

γ (gamma)

Rôle.

Facteur d'actualisation $\in [0, 1]$.
$\to 0$ : court terme.
$\to 1$ : long terme.

Bellman

Équation pour $V^*$.

$V^*(s) = \max_a [R(s,a) + \gamma \sum_{s'} T(s,a,s') V^*(s')]$

Value Iteration

Idée.

Itérer Bellman jusqu'à stabilisation de $V$. Puis déduire $\pi^*$.

Policy Iteration

Idée.

Évaluer $\pi$ (calculer $V^\pi$), améliorer $\pi$, répéter jusqu'à stabilité.

Q-Learning

Spécificité.

Model-free : apprend $Q(s,a)$ sans connaître $T, R$. Par interaction.

MAJ Q

Formule.

$Q \leftarrow Q + \alpha [r + \gamma \max_{a'} Q(s', a') - Q]$

ε-greedy

Compromis.

Avec proba $\varepsilon$ : action aléatoire (exploration).
Sinon : meilleure $Q$ (exploitation).

🎯 Quiz QCM

1.Quel est l'objectif d'un agent en apprentissage par renforcement ?

Minimiser le nombre d'actions
Reproduire les actions d'un expert
Maximiser le cumul des récompenses à long terme
Trouver le chemin le plus court

L'agent ne cherche pas la meilleure action immédiate, mais la stratégie qui maximise le gain global.

2.Quelle propriété caractérise une chaîne de Markov ?

Le passé détermine le futur
Le futur dépend uniquement du présent
Tous les états sont équiprobables
Les actions ne sont pas modélisées

C'est la propriété de Markov. La somme de chaque ligne de la matrice de transition vaut 1.

3.Que prend en compte le modèle à horizon infini avec $\gamma$ proche de 1 ?

Seules les 3 prochaines récompenses
La récompense moyenne
Une seule récompense, la suivante
Fortement le long terme

$\gamma \to 0$ = privilégie le court terme. $\gamma \to 1$ = prend fortement en compte le long terme.

4.Pourquoi le Q-Learning est-il dit « model-free » ?

Il n'utilise pas de réseau de neurones
Il n'a pas besoin d'environnement
Il n'a pas besoin de connaître $T$ et $R$ à l'avance
Il n'a pas de paramètres à apprendre

L'agent apprend $Q(s,a)$ directement par interaction avec l'environnement, sans modèle préalable.

5.Avec $\varepsilon = 0$ dans la stratégie ε-greedy, que fait l'agent ?

Il explore aléatoirement à chaque pas
Il exploite toujours la meilleure action connue
Il alterne 50/50 entre exploration et exploitation
Il s'arrête

$\varepsilon = 0$ = pas d'exploration aléatoire = 100 % exploitation. Risque : rester bloqué sur une stratégie sous-optimale.

6.Que vaut $V^*(s)$ une fois la table $Q^*$ apprise ?

$Q^*(s, a)$ pour l'action $a$ choisie au hasard
$\sum_a Q^*(s, a)$
$\max_a Q^*(s, a)$
$\min_a Q^*(s, a)$

$V^*(s) = \max_a Q^*(s, a)$. Et $\pi^*(s) = \mathrm{argmax}_a Q^*(s, a)$.

📋 Anti-sèche du chapitre

Principe : essai → erreur → récompense → amélioration
Objectif : maximiser cumul des récompenses LT
Élements : agent, env, état $S$, action $A$, récompense $R$
Stratégie $\pi : S \to A$ (déterministe ou probabiliste)
Markov : futur dépend du présent, pas du passé
Matrice transition : somme par ligne = 1
MDP = ($S, A, T, R, \gamma$)
$V^\pi(S)$ = espérance des récompenses cumulées
$V^*(S) = \max_\pi V^\pi(S)$
3 modèles d'optimalité : horizon fini, infini (γ), récompense moyenne
$\gamma \to 0$ : court terme · $\gamma \to 1$ : long terme
Bellman : $V^*(s) = \max_a [R + \gamma \sum T V^*]$
Value Iteration : approche $V^*$ par itérations
Policy Iteration : améliore $\pi$ directement
Q-Learning = model-free, apprend $Q(s, a)$
$\pi^*(s) = \mathrm{argmax}_a Q^*(s, a)$
ε-greedy : ε = taux exploration aléatoire
$\varepsilon \to 0$ : exploitation · $\varepsilon \to 1$ : exploration
MAJ Q : $Q \leftarrow Q + \alpha [r + \gamma \max Q' - Q]$
α = learning rate
Convergence = valeurs Q se stabilisent