Programmation dynamique

Policy Evaluation

Résolution exacte

Reprenons l'exemple précédent, un environement dans lequel la politique est fixée :

Question: comment calculer la valeur de cette politique ?

On peut pour chaque état écrire une équation de Bellman. Par exemple, pour l'état B :

$$V(B) = 1 + \gamma V(BB)$$

Ici, l'environnement est particulièrement simple, il n'y a pas de transitions aléatoires.

On pourrait mettre l'ensemble de ces équations sous forme matricielle :

$$\underbrace{ \begin{bmatrix} V(I) \\ V(B) \\ V(R) \\ V(BB) \\ V(BR) \\ V(RR) \end{bmatrix} }_V = \underbrace{ \begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \\ 10 \\ 20 \end{bmatrix} }_R + % I B R BB BR RR \gamma \underbrace{ \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} }_P \underbrace{ \begin{bmatrix} V(I) \\ V(B) \\ V(R) \\ V(BB) \\ V(BR) \\ V(RR) \\ \end{bmatrix} }_V$$

Et résoudre le système linéaire :

$$V = R + \gamma P V$$ $$(I - \gamma P) V = R$$ $$V = (I - \gamma P)^{-1} R$$

C'est ce que fait le code Python ci-desous.

import numpy as np

states = ["I", "B", "R", "BB", "BR", "RR"]

R = np.array([1., 1., 1., 0., 10., 20.])
P = np.array([
    [0., 1., 0., 0., 0., 0.],
    [0., 0., 0., 1., 0., 0.],
    [0., 0., 0., 0., 1., 0.],
    [0., 0., 0., 0., 0., 0.],
    [0., 0., 0., 0., 0., 0.],
    [0., 0., 0., 0., 0., 0.],
])
gamma = 1.

V = np.linalg.pinv(np.eye(P.shape[0]) - gamma*P) @ R

for name, v in zip(states, V):
    print("V[%s] = %.5f" % (name, v))

Qui produira la sortie suivante:

V[I] = 2.00000
V[B] = 1.00000
V[R] = 11.00000
V[BB] = 0.00000
V[BR] = 10.00000
V[RR] = 20.00000

Cette solution fonctionne, mais est particulièrement inefficace. En effet, la complexité de l'inversion d'une matrice est en $O(n^3)$, ce qui est très coûteux.

Solution itérative

Dans la pratique, on utilisera plutôt une solution itérative. On initialise la valeur de chaque état à 0, puis on répètera la mise à jour suivante :

$$V(s) \leftarrow \sum_{s'} P(s'|s, \pi(s)) \left[ R(s'|s, \pi(s)) + \gamma V(s') \right]$$

Pour chaque état. L'algorithme continuera jusqu'à ce que $V(S)$ ne change plus.

L'algorithme peut alors s'écrire :

Reinforcement learning: an introduction, second edition, page 97

Dans l'algorithme ci-dessus, la politique est elle aussi aléatoire, d'où l'apparition de $\pi(a|s)$, la probabilité de choisir l'action $a$ depuis l'état $s$. Par simplification nous n'avons pas réglé ce cas.

Exemple

Exécutons cet algorithme sur le problème de l'étudiant :

En vert, la fonction de valeur est initialement à $0$ partout. En violet, on représente l'ordre de parcours des états utilisé dans le for each (cet ordre a une importance dans l'algorithme).

Voici les itérations successives :

Après 2 itérations, la fonction de valeur a déjà convergé, plus aucune mise à jour n'est nécessaire.

Amélioration d'une politique

Politique gourmande

Pour une fonction de valeur $V$ donnée, on appellera la politique gourmande $\hat \pi^V$ la politique qui choisit toujours l'action qui maximise la fonction de valeur à l'étape suivante :

$$\hat \pi^V(s) = \arg\max_a \sum_{s'} P(s'|s, a) \left[ R(a, s, s') + \gamma V(s') \right]$$

Exemple

En repartant de l'itération 2 ci-dessus, obtenue par l'évaluation d'une politique (médiocre) dans l'environnement de l'étudiant :

On pourrait construire une nouvelle politique en appliquant la logique gourmande pour chaque état. Par exemple, pour l'état R, on a le choix entre:

Action boire: $r = 1$, état d'arrivé BR, retour estimé $1 + V(BR) = 11$
Action reviser: $r = 0$, état d'arrivé RR, retour estimé $0 + V(RR) = 20$

C'est donc cette deuxième action qui est choisie.

Intuitivement, l'évaluation "propage" la valeur à travers l'environnement, et l'amélioration de la politique modifie la politique pour choisir les actions qui maximisent cette valeur.

Policy Iteration

Intuition

Nous avons maintenant deux opérateurs:

Policy evaluation:

Calcul de $V^\pi$, la fonction de valeur d'une politique $\pi$,

Policy improvement:

Calcul de $\hat \pi^V$, la politique gourmande d'une fonction de valeur $V$.

Nous pouvons donc suivre l'algorithme suivant :

Initialiser une fonction de valeur $V$ à $0$
Calculer la politique gourmande $\hat \pi^{V}$
Calculer la nouvelle fonction de valeur $V'$ de la politique $\hat \pi^{V}$
Répéter les étapes 2 et 3 jusqu'à convergence

Politique optimale

Bonne nouvelle

En suivant cette alternance (évaluation/amélioration), nous sommes assurés de converger vers une politique optimale.

C'est un schéma que nous retrouverons dans tous les algorithmes d'apprentissage par renforcement.

Algorithme

Reinforcement learning: an introduction, second edition, page 102

Value Iteration

L'algorithme de policy iteration nécessite une alternance entre calcul de la politique gourmande et calcul de la fonction de valeur. Il est nécessaire d'obtenir la fonction de valeur avant de pouvoir calculer la nouvelle politique gourmande.

Une amélioration possible est de mettre (virtuellement) à jour la politique gourmande à chaque itération de la fonction de valeur. C'est ce que fait l'algorithme de value iteration.

Reinforcement learning: an introduction, second edition, page 105