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 $

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.

computing time.png

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.

Recommended Posts

Implémentation Einsum de la méthode d'itération de valeur
Mise en œuvre et expérience de la méthode de clustering convexe
Clustering de méthodes de clustering
Implémentation de la méthode de gradient 1
Parallélisation de la méthode de classe
Implémentation de la condition de jugement d'authenticité d'objet à l'aide de la méthode __bool__
Implémentation de la séquence de Fibonacci
Résumé de la méthode d'essai
[Deep Learning from scratch] Implémentation de la méthode Momentum et de la méthode AdaGrad
Augmentez la vitesse de la méthode Monte Carlo de l'implémentation de découpage Cython.
Une implémentation Python simple de la méthode k-voisinage (k-NN)
Vérification et mise en œuvre de la méthode de reconstruction vidéo en utilisant GRU et Autoencoder
Implémentation de la méthode ML-EM, algorithme de reconstruction en coupe pour scanner
Implémentation informatique quantique de Quantum Walk 2
Implémentation de TF-IDF à l'aide de gensim
[python] Valeur de l'objet fonction (?)
Explication et mise en œuvre de SocialFoceModel
Mise en œuvre de la théorie des jeux - Le dilemme du prisonnier -
Mise en œuvre d'une analyse de composants indépendante
Résumé de la méthode d'implémentation Unity IAP
Implémentation informatique quantique de Quantum Walk 3
Implémentation Python du filtre à particules
Comportement de la méthode pandas rolling ()
Implémentation du tri rapide en Python
Implémentation informatique quantique de Quantum Walk 1
Apprentissage par renforcement profond 2 Mise en œuvre de l'apprentissage par renforcement
Implémentation de Scale-Space pour SIFT
Explication mathématique de la recherche de dichotomie et de trisection et méthode de mise en œuvre sans bogues
[Python] Implémentation de la méthode Nelder – Mead et sauvegarde des images GIF par matplotlib
J'ai essayé de résumer la méthode de mise en œuvre fréquemment utilisée de pytest-mock
[Recommandation] Résumé des avantages et des inconvénients de la méthode de filtrage / mise en œuvre basée sur le contenu et coopérative