Value Improvement

Définition de l’environnement

On considère le même environnement que pour les autres méthodes, afin de permettre une comparaison cohérente :

states = ["North", "South", "East", "West"]
actions = ["clock", "anti-clock", "stay"]
gamma = 0.9  
horizon = 10

Définition de Value Improvement

Value Improvement est un algorithme utilisé pour calculer la meilleure policy dans un MDP. Il sert à déterminer quelle est la meilleure action à faire dans chaque état pour maximiser la récompense cumulée.

Pour cela Value Improvement va appliquer de manière répétée l’équation de Bellman optimale :

$$V_{k+1}(s)=\underset{\alpha }{\max }\left[R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }\mid s,\alpha )V_k(s^{\prime })\right]$$

Une fois les valeurs optimales trouvées, on en déduit la politique optimale :

$${\pi }_{k+1}(s)=arg\underset{\alpha }{\max }\left[R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }\mid s,\alpha )V^{\ast }(s^{\prime })\right]$$

Étape 1 — Initialisation

On commence avec une valeur d’état nulle pour tous les états :

$$V_0(s)=0\forall s$$

Pour chaque état s :
    V[s] ← 0

Étape 2 — Itération de la valeur

Pour chaque état, on applique Bellman Optimality :

$$V_{k+1}(s)=\underset{\alpha }{\max }(R(s,a)+\gamma \cdot V_k(P(s,a)))$$

(Note : transitions déterministes → un seul s’ possible)

Pour iteration = 1 à H :
    Pour chaque état s :
        valeurs_actions = liste vide
        
        Pour chaque action a :
            s' = P(s, a)
            q = R(s,a) + gamma * V[s']
            ajouter q à valeurs_actions
        
        V_temp[s] = max(valeurs_actions)
    
    V = V_temp

À la fin, on obtient une estimation de $V^{\ast }(s)$.

Étape 3 — Extraction de la politique optimale

Une fois que les valeurs des états sont stabilisées, on choisit pour chaque état l’action qui maximise la valeur attendue :

$${\pi }^{\ast }(s)=arg\underset{\alpha }{\max }\left[R(s,a)+\gamma \cdot V(P(s,a))\right]$$

Pour chaque état s :
    meilleur_score = -∞
    meilleure_action = null
    
    Pour chaque action a :
        s' = P(s, a)
        q = R(s,a) + gamma * V[s']
        
        Si q > meilleur_score :
            meilleur_score = q
            meilleure_action = a
    
    policy[s] = meilleure_action

Résultat final attendu

Après convergence, Value Improvement retourne :

• La politique optimale ${\pi }^{\ast }(s)$
• Les valeurs optimales d’état $V^{\ast }(s)$

Différence avec Policy Evaluation / Policy Improvement