[PYTHON] Implémentation Einsum de la méthode d'itération de valeur

J'étudie habituellement l'apprentissage par renforcement et l'apprentissage par renforcement inverse, mais récemment j'ai appris que c'était intéressant et j'ai essayé de le mettre en œuvre, donc je vais l'utiliser comme matériel pour le calendrier de l'Avent.

Connaissance préalable

Nous présenterons le processus de détermination de Markov prérequis et la méthode d'itération de valeur.

Processus décisionnel de Markov

Le processus de décision de Markov (MDP) est le processus d'ajout d'actions de prise de décision au processus de Markov (l'état suivant est un processus de nature markovienne qui n'est affecté que par l'état actuel). Je pense qu'il existe de nombreuses explications détaillées sur le net, je les omettrai donc.

Méthode de répétition des valeurs

L'itération de valeur est un type d'algorithme appelé planification dynamique. Trouvez la valeur de $ s $ dans un certain état par la procédure suivante.

-Initialiser $ V $, $ Q $

• Répéter jusqu'à la convergence pour $ s $, $ a $:
• $ Q (s, a) = R (s) + \ gamma \ sum_ {s ^ {\ prime}} P (s ^ {\ prime} | s, a) V (s ^ {\ prime}) $ Calcul
• V(s)=\max_a Q(s,a)

Implémentation par einsum

numpy.einsum facilite la mise en œuvre de calculs matriciels en utilisant la notation de contraction d'Einstein. Dans ce cas, le terme $ \ sum_ {s ^ {\ prime}} P (s ^ {\ prime} | s, a) V (s ^ {\ prime}) $ du côté droit de l'équation ci-dessus est le suivant: Peut être écrit.

np.einsum("ijk,k->ij", P, V)

code

J'ai expérimenté un problème de base dans les bases de l'apprentissage par renforcement appelé Gridworld. Nous avons comparé comment le temps de calcul de l'implémentation par einsum et de l'implémentation par une boucle commune change lorsque la longueur d'un côté de la Grille est augmentée.

vi.py

# -*- coding: utf-8 -*-

import numpy as np
from makeP import makeProb
import time

for statenum in range(2, 101):

    list_einsum = []
    list_loop = []

    for ite in range(100):
        print(".", end="", flush=True)
        x_size = statenum
        y_size = statenum

        n_states = int(x_size * y_size)

        P = makeProb(x_size, y_size)

        R = np.ones(n_states)*-0.01
        R[int(n_states-1)] = 1

        Q = np.zeros((n_states, 4))
        V = np.zeros(n_states)

        delta = np.inf
        eps = 0.0

        gamma = 0.95

        t1 = time.time()
        for _ in range(10000):
            Q = R[:, None] + gamma * np.einsum("ijk,k->ij", P, V)
            V = np.max(Q, axis=1)
        t2 = time.time()
        list_einsum.append(t2-t1)

        Q = np.zeros((n_states, 4))
        V = np.zeros(n_states)

        t1 = time.time()
        for _ in range(10000):
            for s in range(n_states):
                for a in range(4):
                    Q[s][a] = R[s, None] + gamma * np.dot(P[s,a,:], V)
                V[s] = np.max(Q[s, :])
        t2 = time.time()
        list_loop.append(t2-t1)
    print("")
    ar_einsum = np.array(list_einsum)
    ar_loop = np.array(list_loop)

    print("EINSUM: ", "size: ", statenum, "mean: ", np.mean(ar_einsum), "median: ", np.median(ar_einsum), "stdev: ", np.std(ar_einsum))
    print("LOOP  : ", "size: ", statenum, "mean: ", np.mean(ar_loop),   "median: ", np.median(ar_loop),   "stdev: ", np.std(ar_loop))

makeP.py

# -*- coding: utf-8 -*-

import numpy as np

def makeProb(x_size, y_size, n_action=4):
    # make transition prob

    n_states = x_size*y_size
    # S, A, S'
    P = np.zeros(( n_states, n_action, n_states ))



    for s in range(n_states):

        #left is wall
        if s%x_size == 0:
            if s == 0:
                P[0][1][5] = 1
                P[0][3][1] = 1
            elif s > (x_size*(y_size-1)-1):
                P[s][0][s-x_size] = 1
                P[s][3][s+1] = 1
            else:
                P[s][0][s-x_size] = 1
                P[s][1][s+x_size] = 1
                P[s][3][s+1] = 1

        #right is wall
        elif (s+1)%x_size == 0:
            if s == (x_size*y_size-1):
                P[s][0][s-x_size] = 1
                P[s][2][s-1] = 1
            elif s < x_size:
                P[s][1][s+x_size] = 1
                P[s][2][s-1]=1
            else:
                P[s][0][s-x_size] = 1
                P[s][1][s+x_size] = 1
                P[s][2][s-1] = 1

        #upper is wall
        elif s < x_size and s%x_size!=0 and (s+1)%x_size !=0 :
            P[s][1][s+x_size] = 1
            P[s][2][s-1] = 1
            P[s][3][s+1] = 1

        #lower is wall
        elif s > (x_size*(y_size-1)-1) and s%x_size!=0 and (s+1)%x_size !=0:
            P[s][0][s-x_size] = 1
            P[s][2][s-1] = 1
            P[s][3][s+1] = 1

        else:
            P[s][0][s-x_size] = 1
            P[s][1][s+x_size] = 1
            P[s][2][s-1] = 1
            P[s][3][s+1] = 1

    return P

résultat

Victoire écrasante d'Einsum.

Ce qui me rend heureux, c'est que, par exemple, la boucle interne (boucle d'apprentissage par renforcement interne) de l'apprentissage par renforcement inverse peut être résolue rapidement.