Einführung in Q-Learning: Ein Tutorial für Einsteiger

Reinforcement Learning (RL) ist der Teil des Machine-Learning-Ökosystems, in dem ein Agent durch Interaktion mit seiner Umgebung eine optimale Strategie zur Zielerreichung lernt. Das unterscheidet sich deutlich von überwachten Machine-Learning-Algorithmen, bei denen wir Daten einspeisen und verarbeiten müssen. Reinforcement Learning benötigt keine Datensätze im Voraus. Stattdessen lernt es aus der Umgebung und einem Belohnungssystem, um bessere Entscheidungen zu treffen.

Beispiel: Im Mario-Videospiel führt die Figur eine zufällige Aktion aus (z. B. nach links laufen) und erhält dafür abhängig von dieser Aktion eine Belohnung. Nach der Aktion befindet sich der Agent (Mario) in einem neuen Zustand. Das wiederholt sich, bis die Figur das Ende des Levels erreicht oder stirbt. 

Diese Episode wiederholt sich viele Male, bis Mario lernt, sich in der Umgebung zurechtzufinden – indem er die Belohnungen maximiert. 

Bild: Autor

Wir können Reinforcement Learning in fünf einfache Schritte zerlegen:

1. Der Agent befindet sich im Zustand null in einer Umgebung.
2. Er führt basierend auf einer bestimmten Strategie eine Aktion aus.
3. Er erhält für diese Aktion eine Belohnung oder Strafe.
4. Er lernt aus früheren Zügen und optimiert die Strategie. 
5. Der Prozess wiederholt sich, bis eine optimale Strategie gefunden ist. 

Mehr dazu in unserem Tutorial Introduction to Reinforcement Learning. Dort erfährst du mit Codebeispielen, wie Reinforcement Learning funktioniert. 

In diesem Tutorial lernst du Q-Learning kennen und verstehst, warum wir Deep Q-Learning brauchen. Außerdem erstellen und trainieren wir Q-Learning-Algorithmen von Grund auf mit Numpy und Gymnasium.

Hinweis: Wenn du neu im Machine Learning bist, empfehlen wir dir unseren Machine Learning Scientist with Python-Lernpfad, um Reinforcement Learning und Q-Learning besser zu verstehen. 

Was ist Q-Learning?

Q-Learning ist ein modellfreier, wertbasierter Off-Policy-Algorithmus, der auf Basis des aktuellen Zustands des Agents die beste Abfolge von Aktionen findet. Das „Q“ steht für Quality. Quality beschreibt, wie wertvoll eine Aktion ist, um zukünftige Belohnungen zu maximieren.  

Modellbasierte Algorithmen nutzen Übergangs- und Belohnungsfunktionen, um die optimale Policy zu schätzen und ein Modell zu erstellen. Modellfreie Algorithmen hingegen lernen die Konsequenzen ihrer Aktionen aus Erfahrung – ohne explizite Übergangs- oder Belohnungsfunktion. 

Bei wertbasierten Methoden wird die Wertfunktion trainiert, um zu lernen, welche Zustände wertvoller sind, und entsprechend zu handeln. Policy-basierte Methoden trainieren dagegen direkt die Policy, um zu lernen, welche Aktion in einem bestimmten Zustand auszuführen ist.

Bei Off-Policy bewertet und aktualisiert der Algorithmus eine Policy, die sich von derjenigen unterscheidet, mit der gehandelt wird. Im Gegensatz dazu bewertet und verbessert ein On-Policy-Algorithmus dieselbe Policy, mit der die Aktion ausgeführt wurde.  

Zentrale Begriffe im Q-Learning

Bevor wir in die Funktionsweise von Q-Learning einsteigen, klären wir ein paar wichtige Begriffe für die Grundlagen von Q-Learning. 

• States (s): Die aktuelle Position des Agents in der Umgebung. 
• Action (a): Ein Schritt, den der Agent in einem bestimmten Zustand ausführt. 
• Rewards: Für jede Aktion erhält der Agent eine Belohnung oder Strafe. 
• Episodes: Das Ende einer Phase, in der der Agent keine neue Aktion mehr ausführen kann. Das passiert, wenn das Ziel erreicht oder verfehlt wurde. 
• Q(S_t+1, a): Erwarteter optimaler Q-Wert für eine Aktion in einem bestimmten Zustand. 
• Q(S_t, A_t): Aktuelle Schätzung von Q(S_t+1, a).
• Q-Table: Tabelle, in der der Agent Zustände und Aktionen samt Werten verwaltet.
• Temporal Differences (TD): Methode zur Schätzung des erwarteten Werts von Q(S_t+1, a) unter Nutzung von aktuellem und vorherigem Zustand und Aktion. 

Wie funktioniert Q-Learning?

Wir betrachten im Detail ein Beispiel mit einem zugefrorenen See. In dieser Umgebung muss der Agent vom Start bis zum Ziel gelangen, ohne in Löcher zu fallen. Die beste Strategie ist, den kürzesten Weg zum Ziel zu nehmen. 

Gif: Autor

Q-Table

Der Agent nutzt eine Q-Table, um für jeden Zustand die bestmögliche Aktion anhand der erwarteten Belohnung zu wählen. Einfach gesagt: Die Q-Table ist eine Datenstruktur aus Zuständen und Aktionen, deren Werte wir mit dem Q-Learning-Algorithmus fortlaufend aktualisieren. 

Q-Funktion

Die Q-Funktion verwendet die Bellman-Gleichung und nimmt Zustand (s) und Aktion (a) als Eingabe. Die Gleichung vereinfacht die Berechnung von Zustands- und Zustands-Aktions-Werten. 

Bild von freecodecamp.org

Q-Learning-Algorithmus

Bild: Autor

Q-Table initialisieren

Als Erstes initialisieren wir die Q-Table. Die Spalten entsprechen den Aktionen, die Zeilen den Zuständen.

In unserem Beispiel kann sich die Figur nach oben, unten, links und rechts bewegen. Es gibt also vier mögliche Aktionen und vier Zustände (Start, Idle, falscher Pfad und Ende). Der falsche Pfad entspricht dem Hineinfallen in ein Loch. Wir setzen alle Werte der Q-Table zunächst auf 0. 

Bild: Autor

Eine Aktion wählen

Der zweite Schritt ist simpel. Zu Beginn wählt der Agent eine zufällige Aktion (unten oder rechts). Ab dem zweiten Durchlauf nutzt er die aktualisierte Q-Table, um eine Aktion auszuwählen. 

Eine Aktion ausführen

Das Wählen und Ausführen einer Aktion wiederholt sich viele Male, bis die Trainingsschleife endet. Die erste Aktion und der erste Zustand werden anhand der Q-Table gewählt. In unserem Fall stehen überall Nullen. 

Dann bewegt sich der Agent nach unten und aktualisiert die Q-Table mithilfe der Bellman-Gleichung. Mit jedem Zug aktualisieren wir die Werte in der Q-Table und nutzen sie zugleich für die nächste Entscheidungsfindung. 

Anfangs befindet sich der Agent im Explorationsmodus und wählt zufällige Aktionen, um die Umgebung zu erkunden. Die Epsilon-Greedy-Strategie ist eine einfache Methode, um Exploration und Exploitation auszubalancieren. Epsilon steht für die Wahrscheinlichkeit zu explorieren; je kleiner sie wird, desto mehr wird ausgebeutet. 

Zu Beginn ist Epsilon hoch – der Agent exploriert. Während der Erkundung sinkt Epsilon und der Agent beginnt, die gelernten Werte auszunutzen. Mit jeder Iteration wird der Agent sicherer in der Schätzung der Q-Werte.

Bild: Autor

Im Frozen-Lake-Beispiel kennt der Agent die Umgebung zu Beginn nicht und führt deshalb eine zufällige Aktion aus (nach unten). Wie im Bild zu sehen, wird die Q-Table per Bellman-Gleichung aktualisiert.

Belohnungen messen

Nach der Aktion messen wir Ergebnis und Belohnung. 

• Belohnung fürs Erreichen des Ziels: +1
• Belohnung für den falschen Pfad (ins Loch fallen): 0
• Belohnung für Idle oder Bewegung auf dem Eis: 0. 

Q-Table aktualisieren

Wir aktualisieren die Funktion Q(S_t, A_t) mit der Gleichung. Sie nutzt die geschätzten Q-Werte der vorherigen Episode, die Lernrate und den Temporal-Differences-Fehler. Dieser berechnet sich aus der unmittelbaren Belohnung, der abdiskontierten maximal erwarteten künftigen Belohnung und der früheren Q-Schätzung. 

Der Prozess wird mehrfach wiederholt, bis die Q-Table stabil ist und die Q-Funktion maximiert wurde. 

Bild: Autor | Gleichungsvisualisierung: Thomas Simonini

Anfangs erkundet der Agent die Umgebung, um die Q-Table zu füllen. Sobald die Q-Table ausreichend gelernt hat, beginnt er zu exploitieren und trifft bessere Entscheidungen. 

Bild: Autor

Im Fall des zugefrorenen Sees lernt der Agent, den kürzesten Weg zum Ziel zu nehmen und die Löcher zu umgehen. 

Q-Learning-Python-Tutorial 

In diesem Abschnitt bauen wir unser Q-Learning-Modell von Grund auf mit der Gymnasium-Umgebung, Pygame und Numpy. Das Python-Tutorial ist eine angepasste Version des Notebooks von Thomas Simonini. Es umfasst das Initialisieren von Umgebung und Q-Table, die Definition der Greedy-Policy, das Setzen der Hyperparameter, das Erstellen und Ausführen der Trainings- und Evaluationsschleife sowie die Visualisierung der Ergebnisse.   

Wenn du Probleme beim Erstellen und Ausführen deiner Trainingsschleife hast, findest du hier den Quellcode samt Ausgabe.   

Setup

Virtuelles Display einrichten

Zuerst installieren wir alle Abhängigkeiten, um ein Replay-Video (Gif) zu erzeugen. Wir benötigen einen virtuellen Bildschirm (pyvirtualdisplay), um die Umgebung zu rendern und Frames aufzuzeichnen. 

Hinweis: Mit %%capture unterdrücken wir die Ausgabe der Jupyter-Zelle. 

%%capture
!pip install pyglet==1.5.1
!apt install python-opengl
!apt install ffmpeg
!apt install xvfb
!pip3 install pyvirtualdisplay

# Virtual display
from pyvirtualdisplay import Display

virtual_display = Display(visible=0, size=(1400, 900))
virtual_display.start()

Abhängigkeiten installieren

Jetzt installieren wir die Pakete, mit denen wir die Trainingsschleife erstellen, ausführen und evaluieren. 

• gymnasium: Initialisiert die FrozenLake-v1-Umgebung.
• pygame: UI für FrozenLake-v1.
• numpy: Erstellung und Handhabung der Q-Table.

%%capture
!pip install gymnasium
!pip install pygame
!pip install numpy

!pip install imageio imageio_ffmpeg

Pakete importieren

Jetzt importieren wir die benötigten Bibliotheken. 

• Imageio dient zum Erstellen der Animation. 
• tqdm zeigt Fortschrittsbalken an. 

import numpy as np
import gymnasium as gym
import random
import imageio
from tqdm.notebook import trange

Frozen-Lake-Gymnasium-Umgebung 

Wir erstellen eine nicht rutschige 4x4-Umgebung mit der Frozen Lake Gymnasium Library. 

• Es gibt zwei Grid-Varianten: „4x4“ und „8x8“.
• Wenn is_slippery=True ist, kann der Agent aufgrund der Glätte nicht immer in die gewünschte Richtung laufen. 

Nach der Initialisierung analysieren wir die Umgebung. 

env = gym.make("FrozenLake-v1",map_name="4x4",is_slippery=False)

print("Observation Space", env.observation_space)
print("Sample observation", env.observation_space.sample()) # display a random observation

Es gibt 16 eindeutige Zustände in der Umgebung, die an zufälligen Positionen angezeigt werden. 

Observation Space Discrete(16)
Sample observation 15

Schauen wir uns die Anzahl der Aktionen an und geben eine zufällige Aktion aus. 

Action Space:

• 0: links
• 1: unten
• 2: rechts
• 3: oben

Belohnungsfunktion:

• Ziel erreicht: +1
• Ins Loch gefallen: 0
• Auf dem Eis bleiben: 0

print("Action Space Shape", env.action_space.n)
print("Action Space Sample", env.action_space.sample())

Action Space Shape 4
Action Space Sample 1

Q-Table erstellen und initialisieren

Die Q-Table hat Aktionen als Spalten und Zustände als Zeilen. Über Gymnasium ermitteln wir Action Space und State Space und erstellen daraus die Q-Table. 

state_space = env.observation_space.n
print("There are ", state_space, " possible states")

action_space = env.action_space.n
print("There are ", action_space, " possible actions")

There are  16  possible states
There are  4  possible actions

Zur Initialisierung erzeugen wir ein Numpy-Array der Größe state_space × action_space. In unserem Fall also 16 × 4. 

def initialize_q_table(state_space, action_space):
  Qtable = np.zeros((state_space, action_space))
  return Qtable

Qtable_frozenlake = initialize_q_table(state_space, action_space)

Epsilon-Greedy-Policy

Vorhin haben wir die Epsilon-Greedy-Strategie kennengelernt, die den Trade-off zwischen Exploration und Exploitation steuert. Mit Wahrscheinlichkeit 1 − ɛ wird exploitiert, mit Wahrscheinlichkeit ɛ exploriert. 

In der Funktion epsilon_greedy_policy:

1. Generieren wir eine Zufallszahl zwischen 0 und 1.
2. Ist die Zahl größer als Epsilon, exploitieren wir: Der Agent wählt die Aktion mit dem höchsten Wert für den gegebenen Zustand.
3. Andernfalls explorieren wir (zufällige Aktion). 

def epsilon_greedy_policy(Qtable, state, epsilon):
  random_int = random.uniform(0,1)
  if random_int > epsilon:
    action = np.argmax(Qtable[state])
  else:
    action = env.action_space.sample()
  return action

Greedy-Policy definieren

Q-Learning ist ein Off-Policy-Algorithmus. Das heißt, die Policy zum Handeln und die zum Aktualisieren unterscheiden sich. 

In diesem Beispiel ist die Epsilon-Greedy-Policy die agierende Policy, die Greedy-Policy die aktualisierende. 

Die Greedy-Policy ist auch die finale Policy nach dem Training. Sie wählt den höchsten Zustands-/Aktionswert aus der Q-Table.

def greedy_policy(Qtable, state):
  action = np.argmax(Qtable[state])
  return action

Modell-Hyperparameter

Diese Hyperparameter nutzen wir in der Trainingsschleife. Mit Feintuning erzielst du bessere Ergebnisse. 

Damit der Agent eine gute Wertnäherung lernt, muss er genügend Zustandsraum explorieren. Daher verringern wir Epsilon progressiv. Ist die Abklingrate zu hoch, könnte der Agent zu früh stecken bleiben.

• 10.000 Trainings- und 100 Evaluations-Episoden.
• Lernrate: 0,7.
• Umgebung: "FrozenLake-v1" mit 99 Maximalschritten pro Episode.
• Gamma (Diskontfaktor): 0,95.
• eval_seed: Seed für die Evaluation.
• Epsilon zu Beginn: 1,0; minimale Wahrscheinlichkeit: 0,05.
• Exponentielle Abklingrate für Epsilon: 0,0005.

# Training parameters
n_training_episodes = 10000
learning_rate = 0.7        

# Evaluation parameters
n_eval_episodes = 100      

# Environment parameters
env_id = "FrozenLake-v1"   
max_steps = 99             
gamma = 0.95               
eval_seed = []             

# Exploration parameters
max_epsilon = 1.0           
min_epsilon = 0.05           
decay_rate = 0.0005           

Modelltraining 

In der Trainingsschleife:

1. Erstellen wir eine Schleife über die Trainingsepisoden.
2. Reduzieren wir zuerst Epsilon, da mit jeder Episode weniger Exploration und mehr Exploitation nötig ist. 
3. Setzen wir die Umgebung zurück.
4. Erstellen wir eine geschachtelte Schleife über die Maximalschritte.
5. Wählen wir die Aktion per Epsilon-Greedy-Policy. 
6. Führen wir die Aktion (A_t) aus und beobachten erwartete Belohnung (R_t+1) und Zustand (S_t+1).
7. Führen wir die Aktion (a) aus und beobachten Folgezustand (s') und Belohnung (r).
8. Aktualisieren wir die Q-Funktion mit der Formel. 
9. Wenn done = True, beenden wir die Episode und brechen die Schleife ab.
10. Anschließend setzen wir den aktuellen Zustand auf den neuen Zustand. 
11. Nach allen Trainingsepisoden gibt die Funktion die aktualisierte Q-Table zurück. 

def train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable):
  for episode in trange(n_training_episodes):
 
    epsilon = min_epsilon + (max_epsilon - min_epsilon)*np.exp(-decay_rate*episode)
    # Reset the environment
    state = env.reset()
    step = 0
    done = False

    # repeat
    for step in range(max_steps):
   
      action = epsilon_greedy_policy(Qtable, state, epsilon)

   
      new_state, reward, done, info = env.step(action)

   
      Qtable[state][action] = Qtable[state][action] + learning_rate * (reward + gamma * np.max(Qtable[new_state]) - Qtable[state][action])

      # If done, finish the episode
      if done:
        break
     
      # Our state is the new state
      state = new_state
  return Qtable

Für 10.000 Trainingsepisoden brauchten wir 3 Sekunden. 

Qtable_frozenlake = train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable_frozenlake)

Wie zu sehen ist, enthält die trainierte Q-Table nun Werte. Der Agent kann diese nutzen, um sich in der Umgebung zu orientieren und das Ziel zu erreichen.  

Qtable_frozenlake

array([[0.73509189, 0.77378094, 0.77378094, 0.73509189],
      [0.73509189, 0.        , 0.81450625, 0.77378094],
      [0.77378094, 0.857375  , 0.77378094, 0.81450625],
      [0.81450625, 0.        , 0.77378094, 0.77378094],
      [0.77378094, 0.81450625, 0.        , 0.73509189],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.9025    , 0.        , 0.81450625],
      [0.        , 0.        , 0.        , 0.        ],
      [0.81450625, 0.        , 0.857375  , 0.77378094],
      [0.81450625, 0.9025    , 0.9025    , 0.        ],
      [0.857375  , 0.95      , 0.        , 0.857375  ],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.9025    , 0.95      , 0.857375  ],
      [0.9025    , 0.95      , 1.        , 0.9025    ],
      [0.        , 0.        , 0.        , 0.        ]])

Evaluation

evaluate_agent läuft über n_eval_episodes Episoden und liefert Mittelwert und Standardabweichung der Belohnung. 

1. In der Schleife prüfen wir zunächst, ob ein Evaluations-Seed gesetzt ist. Wenn nicht, setzen wir die Umgebung ohne Seed zurück. 
2. Die innere Schleife läuft bis max_steps.
3. Der Agent wählt in jedem Zustand die Aktion mit der höchsten erwarteten künftigen Belohnung aus der Q-Table. 
4. Wir addieren die Belohnung.
5. Wir aktualisieren den Zustand.
6. Wenn done (Agent fällt ins Loch oder Ziel erreicht), brechen wir ab.
7. Wir speichern die Ergebnisse.
8. Am Ende berechnen wir daraus Mittelwert und Standardabweichung. 

def evaluate_agent(env, max_steps, n_eval_episodes, Q, seed):

  episode_rewards = []
  for episode in range(n_eval_episodes):
    if seed:
      state = env.reset(seed=seed[episode])
    else:
      state = env.reset()
    step = 0
    done = False
    total_rewards_ep = 0
   
    for step in range(max_steps):
      # Take the action (index) that have the maximum reward
      action = np.argmax(Q[state][:])
      new_state, reward, done, info = env.step(action)
      total_rewards_ep += reward
       
      if done:
        break
      state = new_state
    episode_rewards.append(total_rewards_ep)
  mean_reward = np.mean(episode_rewards)
  std_reward = np.std(episode_rewards)

  return mean_reward, std_reward

Wie du siehst, erhalten wir die perfekte Punktzahl bei Null Standardabweichung. Das bedeutet, unser Agent hat in allen 100 Episoden das Ziel erreicht. 

# Evaluate our Agent
mean_reward, std_reward = evaluate_agent(env, max_steps, n_eval_episodes, Qtable_frozenlake, eval_seed)
print(f"Mean_reward={mean_reward:.2f} +/- {std_reward:.2f}")

Mean_reward=1.00 +/- 0.00

Ergebnis visualisieren

Bisher haben wir nur mit Zahlen gearbeitet. Für eine Demo erstellen wir nun ein animiertes Gif des Agents vom Start bis zum Ziel. 

1. Wir setzen die Umgebung mit einer Zufallszahl zwischen 0 und 500 zurück, um den Startzustand zu erzeugen. 
2. Wir rendern die Umgebung als rdb_array, um ein Bild-Array zu erzeugen. 
3. Wir hängen das img an das images-Array an. 
4. In der Schleife führen wir die Schritte gemäß Q-Table aus und rendern bei jedem Schritt ein Bild. 
5. Zum Schluss erzeugen wir mit diesem Array und imageio ein Gif mit einem Frame pro Sekunde. 

def record_video(env, Qtable, out_directory, fps=1):
  images = [] 
  done = False
  state = env.reset(seed=random.randint(0,500))
  img = env.render(mode='rgb_array')
  images.append(img)
  while not done:
    # Take the action (index) that have the maximum expected future reward given that state
    action = np.argmax(Qtable[state][:])
    state, reward, done, info = env.step(action) # We directly put next_state = state for recording logic
    img = env.render(mode='rgb_array')
    images.append(img)
  imageio.mimsave(out_directory, [np.array(img) for i, img in enumerate(images)], fps=fps)

In einem Jupyter-Notebook kannst du das Gif mit IPython.display Image anzeigen. 

video_path="/content/replay.gif"
video_fps=1
record_video(env, Qtable_frozenlake, video_path, video_fps)

from IPython.display import Image
Image('./replay.gif')

Du kannst die Ergebnisse jetzt mit Kolleginnen und Kollegen teilen oder in sozialen Medien posten.