Normalerweise studiere ich Verstärkungslernen und umgekehrtes Verstärkungslernen, aber kürzlich habe ich gelernt, dass es interessant ist, und versucht, es umzusetzen, sodass ich es als Material für den Adventskalender verwenden werde.

Vorherige Kenntniss

Wir werden den vorausgesetzten Markov-Bestimmungsprozess und die Wertiterationsmethode skizzieren.

Markov Entscheidungsprozess

Der Markov-Entscheidungsprozess (MDP) ist der Prozess des Hinzufügens von Entscheidungsaktionen zum Markov-Prozess (der nächste Status ist ein Prozess mit Markov-Charakter, der nur vom aktuellen Status beeinflusst wird). Ich denke, es gibt viele detaillierte Erklärungen im Internet, deshalb werde ich sie weglassen.

Wertwiederholungsmethode

Die Wertiteration ist eine Art Algorithmus, der als dynamische Planung bezeichnet wird. Ermitteln Sie den Wert von $ s $ in einem bestimmten Status wie folgt.

-Initialisieren Sie $ V $, $ Q $

Wiederholen Sie diesen Vorgang bis zur Konvergenz für $ s $, $ a $:
$ Q (s, a) = R (s) + \ gamma \ sum_ {s ^ {\ prime}} P (s ^ {\ prime} | s, a) V (s ^ {\ prime}) $ Berechnung
V(s)=\max_a Q(s,a)

Implementierung durch einsum

Mit numpy.einsum können Matrixberechnungen mithilfe der Einsteinschen Kontraktionsnotation einfach implementiert werden. In diesem Fall lautet der Term $ \ sum_ {s ^ {\ prime}} P (s ^ {\ prime} | s, a) V (s ^ {\ prime}) $ auf der rechten Seite der obigen Gleichung wie folgt: Kann geschrieben werden.


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

Code

Ich experimentierte mit einem Grundproblem in den Grundlagen des Verstärkungslernens namens Gridworld. Wir haben verglichen, wie sich die Berechnungszeit der Implementierung durch einsum und die Implementierung durch eine gemeinsame Schleife ändert, wenn die Länge einer Seite des Gitters erhöht wird.

`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

Ergebnis

Überwältigender Sieg von einsum.

computing time.png

Was mich glücklich macht, ist, dass zum Beispiel die innere Schleife (interne Verstärkungslernschleife) des umgekehrten Verstärkungslernens schnell gelöst werden kann.

[PYTHON] Einsum Implementierung der Wertiterationsmethode