Q-Learning: Die Basics von Reinforcement Learning

Einordnung

Reinforcement Learning hat viel Aufsehen erregt. Modelle wie AlphaGo oder AlphaStar haben große Erfolge erzielt und das Interesse an entsprechenden Modellen in verschiedenen Bereichen stark erhöht. Heute stelle ich einen der grundlegendsten Algorithmen vor, den das Reinforcement Learning in seinen Anfängen hervorgebracht hat: Das Q-Learning.

Q-Learning wird manchmal auch Q-Table genannt, in Anlehnung an die Matrix, die dem Verfahren zugrunde liegt. Im Folgenden wird der Begriff Q-Learning verwendet.

Mathematische Grundlagen

Bei Q-Learning handelt es sich in den Implementierungen häufig um eine einfache Matrix, die in einer Dimension mit der Anzahl der möglichen Eingangsbeobachtungen und in der anderen Dimension mit Nullen für die Anzahl der möglichen Aktionen initialisiert wird. Anschließend wird durch die Update-Formel

die State-Values entsprechender Observationen iterativ angepasst. Diese Gleichung wird auch als Bellmann-Gleichung bezeichnet.

In der Gleichung oben steht $s_t$ für die Beobachtung zum Zeitpunkt $t \in \mathbb{N}$, $a_t \in A$ für die gewählte Aktion zum Zeitpunkt $t$ und $r_t$ für den Reward, welcher zum Zeitpunkt $t$ nach Anwendung der Aktion $a_t$ gewährt wurde. Der Raum aller möglichen Aktionen wird mit $A$ bezeichnet. ^{1 2 3}

Typischerweise wird der Endzustand nie in der Update-Formel aktualisiert. In diesem Fall kann entweder der Wert der Belohnung als Zustandswert verwendet werden, oder es wird darauf verzichtet, wie es in der Implementierung weiter unten der Fall sein wird.

Darüber hinaus verwendet Q-Learning auch Epsilon-Greedy für die Exploration. Hierbei handelt es sich um ein Random Sampling im Bereich $[0, 1]$. Wenn die gezogene Stichprobe kleiner als Epsilon ist, wird eine zufällige Aktion ausgewählt, andernfalls wird eine Aktion nach Auswertung ausgewählt. ⁴

Im Gegensatz zu vielen anderen Reinforcement Learning Algorithmen, die auf künstlichen neuronalen Netzen basieren, konnte gezeigt werden, dass Q-Learning prinzipiell eine garantierte Konvergenz aufweisen kann. Dies ist allerdings unter sehr technischen Voraussetzungen möglich, welche in der Realität meist ignoriert werden. Mehr Informationen dazu in dieser Quelle.

Q-Learning kann in seiner Grundversion nur mit diskreten Zustands- und Aktionsräumen umgehen. Entsprechende Workarounds werden im Verlaufe des Posts vorgestellt.

Die Parameter

Die Lernrate

Der Parameter $\alpha$ beschreibt wie beim Rest der “Reinforcement Learning”-Algorithmen auch die Learning Rate, welche sich im Bereich $\alpha \in [0, 1]$ bewegen sollte.

Dieser Parameter beschreibt die Gewichtung, mit der neue Informationen im Algorithmus verarbeitet werden. Höhere Werte von Alpha gewichten dabei neue Informationen (deutlich) stärker als alte Informationen, als dies bei (sehr) kleinen Werten der Fall wäre.

Im Extremfall von $\alpha = 0$ lernt der Agent nichts, da Änderungen durch die Update-Formel nicht in die Q-Table einfließen können.

In vollständig deterministischen Umgebungen ist eine Lernrate von $\alpha = 1$ optimal. In stochastischen Umgebungen sollte dieser Wert geringer liegen.

Trotz der Konvergenzgarantie unter technischen Bedingungen wird in der Realität meist ein konstanter, vorgegebener Wert verwendet. Auch ohne Konvergenzgarantie konvergiert der Algorithmus häufig und verhält sich in der Lernphase robust. ⁵

Gamma

Gamma als Discounting Factor bestimmt eine entsprechend zu maximierende Zielgröße. Bei großen Gamma-Werten versucht der Algorithmus, die langfristigen Belohnungen zu maximieren, während ein kleines Gamma eher zu kurzfristigen Optimierungen führt.

Wird Gamma größer oder gleich eins gewählt, kann es zu einer Divergenz im Algorithmus kommen und die Zustandswerte nähern sich immer mehr dem Wert unendlich an. Daher sollte Gamma kleiner als eins gewählt werden. ¹

Wahl der Anfangsbedingungen

Aufgrund der iterativen Natur des Algorithmus muss in der ersten Iteration des Algorithmus eine Anfangsbedingung eingegeben werden. Diese Bedingung bildet die Grundlage für die Lösung der Aufgabe.

Hohe Anfangszustandswerte können dazu führen, dass der Algorithmus eher neue Kombinationen ausprobiert, da ausprobierte Beobachtungs-Aktionskombinationen durch die Aktualisierungsformel schnell niedrigere Werte aufweisen und entsprechend neue Aktionen mit höherer Wahrscheinlichkeit ausgewählt werden. ¹

Anmerkung des Autors: In der Praxis wird häufig einfach eine Nullmatrix initialisiert, da dies nicht sehr aufwendig ist. Die Ergebnisse sind in der Regel gut.

Q-Learning auf kontinuierlichen Räumen

Q-Learning hat grundsätzlich die Einschränkung, dass sehr große Dimensionen oder unendlich viele Punkte für die Anzahl der Beobachtungen und Aktionen große Speichermengen erfordern oder nicht direkt unterstützt werden. Um Q-Learning auf kontinuierlichen Räumen zum Laufen zu bringen, gibt es daher grundsätzlich zwei verschiedene Möglichkeiten

Diskretisierung des Raumes

Um das Problem eines diskreten Raumes mit unendlich vielen Punkten zu umgehen, kann der Raum relativ einfach als Menge endlicher Punkte angenommen werden. ¹

Dies kann auch für sehr große Räume (mit sehr vielen Datenpunkten) verwendet werden. Dabei werden mehrere Datenpunkte zu einem Datenpunkt zusammengefasst.

Funktionsapproximation auf dem Raum

Grundsätzlich kann das Problem auch dadurch gelöst werden, dass ein angepasstes neuronales Netz zur Regression verwendet wird, um den kontinuierlichen Input in einen diskreten Input bzw. den (diskreten) Output in einen kontinuierlichen Output zu transformieren. ¹

Hinweis des Autors: Auch wenn beide Verfahren in ihren Grundprinzipien zur Lösung des Problems beitragen, führen sie teilweise zu ineffizienten Lernprozessen - unter anderem verursacht durch den Fluch der Dimensionalität.

Implementierung

Im Folgenden wird eine einfache Version vom Q-Learning implementiert, welche das Taxi-Problem lösen soll. Wir beginnen mit den notwendigen Imports und em Experience Buffer.

import numpy as np
import gym

class TrajectoryExperienceMemory:
    def __init__(self):
        self.cstate_memory, self.action_memory, self.reward_memory, self.pstate_memory = [], [], [], []

    def record(self, cstate, action, reward, pstate):
        self.cstate_memory.append(cstate)
        self.action_memory.append(action)
        self.reward_memory.append(reward)
        self.pstate_memory.append(pstate)

    def flush_memory(self):
        self.cstate_memory, self.action_memory, self.reward_memory, self.pstate_memory = [], [], [], []

    def return_experience(self):
        batch_cstates = np.array(self.cstate_memory, dtype=np.int64)
        batch_actions = np.array(self.action_memory, dtype=np.int64)
        batch_rewards = np.array(self.reward_memory, dtype=np.float64)
        batch_pstates = np.array(self.pstate_memory, dtype=np.int64)

        return (batch_cstates, batch_actions, batch_rewards, batch_pstates)

Als nächstes wird hierbei der Algorithmus für das Q-Learning implementiert. Diese Version beinhaltet einen linearen $\epsilon$-Decay mit relativ gerinem Decay-Wert.

class QAgent:
    def __init__(self, observations: int, actions: int) -> None:
        self.observations = observations
        self.actions = actions

        # Learning Parameters
        self.alpha, self.gamma = 0.8, 0.99

        # Exploration Parameters
        self.epsilon, self.epsilon_decay = 1, 0.0001

        # Initialize Q-Matrix
        self.q = np.zeros((self.observations, self.actions))

        # Initialize Experience Replay
        self.memory = TrajectoryExperienceMemory()

    def sample_action(self, observation: int):
        if (np.random.random() < self.epsilon):
            self.epsilon -= self.epsilon_decay
            return np.random.randint(0, self.actions - 1)
        else:
            return np.argmax(self.q[observation])
    
    def store_step(self, cstate: int, action: int, reward: float, pstate: int):
        self.memory.record(cstate, action, reward, pstate)

    def update(self):
        cstates, actions, rewards, pstates = self.memory.return_experience()

        for i in range(len(cstates)):
            # Perform Q-Update according to Bellman Equation
            self.q[cstates[i], actions[i]] = self.q[cstates[i], actions[i]] + self.alpha * (rewards[i] + self.gamma * np.max(self.q[pstates[i]]) - self.q[cstates[i], actions[i]]) 

Als Letztes wird hierbei noch die Training Loop implementiert, um das Training umzusetzen.

env = gym.make("FrozenLake-v1")
agent = QAgent(16, 4)

episodes = 10000
episodic_rewards = []

for episode in range(episodes):
    cstate, _ = env.reset()
    done, episodic_reward = False, 0

    while (done == False):
        cstate = int(cstate)
        action = agent.sample_action(cstate)
        pstate, reward, done, _, _ = env.step(action)
        episodic_reward += reward

        agent.store_step(cstate, action, reward, pstate)

        cstate = pstate

    print(f"Episodic Reward in Episode {episode}: {episodic_reward}")
    episodic_rewards.append(episodic_reward)
    agent.update()

Die Ergebnisse einer Implementierung ohne $\epsilon$-Decay sind im Folgenden visualisiert:

Epsilon Decay

Weiterhin ist es üblich, entsprechend den $\epsilon$-Wertes über das Training durch einen Decay zu steuern, ähnlich zum Deep Q-Network. Hierbei ist es ebenso wichtig, einen Minimalwert $\epsilon_{min}$ für $\epsilon$ festzulegen, damit immer ein gewisses Maß an Exploration aufrechterhalten wird.

Ein Decay kann beispielsweise über einen exponentiellen oder linearen Abfall erreicht werden. Ergebnisse hierzu sind im Folgenden visualisiert worden:

Üblicherweise sind diese Ergebnisse mit einem $\epsilon$-Decay besser, aufgrund einer effizienteren Exploration zu Beginn des Trainings und einer effizienteren Exploitation in späteren Episoden des Trainings. Dies ist hier nicht der Fall, sollte allerdings klassisch mit implementiert werden.

Quellen