Monte Carlo Online Control on Policy improvement (MCOC on P-imp)

Qu'est ce que le Monte Carlo Online Control (MCOC) ?

Le Monte Carlo online control est un algorithme, qui à partir des résultats récoltés, améliore la politique de jeu actuelle, dans le but de trouver la meilleure possible.

Pourquoi utiliser le MCOC ?

Cet algorithme est très utile pour apprendre une politique optimale à partir des intéractions avec l'environnement, car il se base sur son expérience. Cet algorithme est simple et possède un équilibre entre exploration et exploitation, il explore la plus part du temps l'action la plus optimate, mais explore de temps en temps d'autres actions selon $ϵ$.

Réalisation de l'Algorithme

Pour réaliser cet algorithme, nous commençons par initialiser les données suivants : $$Q(s,a)=0,N(S,a)=0,ϵ=1,k=1,{\pi }_i=ϵ-greedy(Q)$$ ou

• s correspond à l'état
• a correspond à l'action
• Q (s, a) correspond à la valeur d'un état en effectuant une action, et en suivant la politique ${\pi }_i$
• N (s, a) correspond au nombre de visite
• $ϵ$ correspond aux taux d'explorations dans la politique $ϵ$-greedy
• ${\pi }_i$ correspond à la politique utilisée
• k correspond au compteur d'épisode

Utilisation de l'algorithme sur CliffWalking-v1

Nous avons utilisé cet algorithme sur l'environnement gymnasium CliffWalking afin de trouver le chemin le plus optimale, et voici le résultat obtenu :

Code de l'algorithme

def MCOC(gamma, num_episodes):
    env = gym.make("CliffWalking-v1")
    num_states = env.observation_space.n
    num_actions = env.action_space.n

    k = 1
    epsilon = 1

    #Q(s, a) & N(s, a) = 0 | Pour tout (s, a), eps = 1 / nb actions
    Q_values = np.zeros((num_states, num_actions))
    N_visits = np.zeros((num_states, num_actions)) # visites
    policy = np.ones((num_states, num_actions)) / num_actions


    #policy evaluation
    for g in range(1, num_episodes + 1):
        episodes = []
        print("epîsode : ", g)
        state, info = env.reset()

        while True:
            #choisir la meilleur action
            best_action = np.argmax(Q_values[state, :])

            #remplir le tab des proba
            for a in range(num_actions):
                if a == best_action:
                    policy[state, a] = 1 - epsilon + (epsilon / num_actions)
                else:
                    policy[state, a] = epsilon / num_actions

            #extraire les prob
            p = [policy[state, a] for a in range(num_actions)]
            p = np.array(p, dtype=float)
            p = p / p.sum()

            #choisir l'action selon p et la jouer
            action = np.random.choice(range(num_actions), p=p)
            next_state, reward, terminated, truncated, _ = env.step(action)
            # stockage echantillons
            episodes.append((state, action, reward))

            #sortir de la boucle si fin du jeu
            if (terminated or truncated):
                break

            state = next_state

        #calculer Gkt
        G = {}
        T = len(episodes)
        G[T-1] = episodes[T-1][2] #dernière recompense

        # Calculer g_kt
        for t in range(T - 2, -1, -1):
            G[t] = episodes[t][2] + gamma * G[t + 1]

        visited = set()
        for t, (state, action, reward) in enumerate(episodes):
            if (state, action) not in visited:
                N_visits[state, action] += 1
                Q_values[state, action] = Q_values[state, action] + (math.sqrt(1 / N_visits[state, action]) * (G[t] - Q_values[state, action]))

        #policy improvement
        k = k + 1
        epsilon = 1 / k

        for state in range(num_states):
            best_action = np.argmax(Q_values[state, :])

            # remplir le tab des proba
            for a in range(num_actions):
                if a == best_action:
                    policy[state, a] = 1 - epsilon + (epsilon / num_actions)
                else:
                    policy[state, a] = epsilon / num_actions
        print(epsilon)
        print(datetime.datetime.now())

    return Q_values, policy

Données utilisées :

$\gamma =0.9,ϵ=1,$

Les essais

• Pour 500 000 essais : L'algorithme a réussi à trouver un chemin valide vers le cookie, mais le chemin n'est pas encore très optimale Nous avons obtenu -21 rewards.

Tableau des Q-values pour 500 000 essais

• Pour $\text{1 500 000}$ essais : L'algorithme a réussi à trouver une politique meilleure que celle d'avant, mais il n'a toujours pas trouver la plus optimale.

Nous avons obtenu -17 rewards, mieux que l'essai d'avant.

Tableau complet des Q-values pour 1 500 00 essai

• Pour $\text{3 000 000}$ essais : Cette fois-ci, ce nombre d'essai a donné le même résultat que pour 1 500 000 essais, avec egalement -17 rewards.

Tableau des Q-values pour 3 M

Conclusion

Il faut effectuer encore des millions d'episodes afin que l'agent puisse tout explorer et trouver la meilleur politique possible, qui donnerait le schéma suivant :

Utilisation de l'algorithme sur Cartpole-v1

Pour utiliser l'algorithme sur cartpole-v1, Nous avons du discretiser l'espace des etats de l'environnement avec une intervalle de 12 car Cartpole possède des états continus, alors que le MCOC nécessite des états discret.

Cartpole-v1 nous fournit les informations suivant :

• Position du chariot : de -4.8 à 4.8
• Vitesse du chariot : -∞ à +∞
• Angle du pôle : −0.418 rad à +0.418 rad
• Vitesse angulaire du pôle : −∞ à +∞

Code de l'algorithme :

def create_bins(num_bins=12):
    return [
        np.linspace(-4.8, 4.8, num_bins),
        np.linspace(-5, 5, num_bins),
        np.linspace(-0.418, 0.418, num_bins),
        np.linspace(-5, 5, num_bins)
    ]

bins = create_bins()


def discretize(state):
    return tuple(int(np.digitize(s, b)) for s, b in zip(state, bins))


def MCOC(gamma, num_episodes):
    env = gym.make("CartPole-v1")

    # 6 bins par dimension → 6^4 = 1296 états
    num_states = 12 ** 4
    num_actions = env.action_space.n

    k = 1
    epsilon = 1

    Q_values = np.zeros((num_states, num_actions))
    N_visits = np.zeros((num_states, num_actions))
    policy = np.ones((num_states, num_actions)) / num_actions
    data = []

    
    for g in range(1, num_episodes + 1):
        episodes = []
        rewardepisode = 0

        state_cont, info = env.reset()
        state = get_index(discretize(state_cont))

        while True:
            # best action
            best_action = np.argmax(Q_values[state, :])

            # remplir proba
            for a in range(num_actions):
                if a == best_action:
                    policy[state, a] = 1 - epsilon + (epsilon / num_actions)
                else:
                    policy[state, a] = epsilon / num_actions

            p = policy[state]
            p = p / p.sum()

            action = np.random.choice(range(num_actions), p=p)
            next_state_cont, reward, terminated, truncated, _ = env.step(action)
            rewardepisode += reward
            data.append((g, rewardepisode))
            next_state = get_index(discretize(next_state_cont))
            episodes.append((state, action, reward))

            if terminated or truncated:
                break

            state = next_state

        
        G = {}
        T = len(episodes)
        G[T - 1] = episodes[T - 1][2]

        for t in range(T - 2, -1, -1):
            G[t] = episodes[t][2] + gamma * G[t + 1]

        visited = set()
        for t, (state, action, reward) in enumerate(episodes):
            if (state, action) not in visited:
                visited.add((state, action))
                N_visits[state, action] += 1
                alpha = math.sqrt(1 / N_visits[state, action])
                Q_values[state, action] += alpha * (G[t] - Q_values[state, action])

    
        k += 1
        epsilon = 1 / k

        for s in range(num_states):
            best_action = np.argmax(Q_values[s, :])
            for a in range(num_actions):
                if a == best_action:
                    policy[s, a] = 1 - epsilon + (epsilon / num_actions)
                else:
                    policy[s, a] = epsilon / num_actions

        print(g , rewardepisode)

    return Q_values, policy, data

Données utilisées :

$\gamma =0.99,bins=10,ϵ=1,k=1$

Essai et Résultat

Nous avons effectué un test de 10 000 episodes sur cartpole avec cet algorithme, et cela fût un front succès. L'algorithme a atteint le reward maximal à atteindre (500), comme on peut le voir dans le graphique en dessous, l'algorithme a été constant, du 1000 ème episode jusqu'à la fin.