Der Actor-Critic Algorithmus: Der Schlüssel zum effizienten Reinforcement Learning

Einordnung

Sample Efficiency und Exploration Stability sind zwei von vielen Problemen, die beim value-basierten Reinforcement Learning wie DQN oder D2QN auftreten können. Aus dieser Problematik heraus wurde unter anderem der Actor-Critic-Algorithmus entwickelt, der diese Probleme (weitestgehend) beseitigt.

Der Actor-Critic-Algorithmus ist ein On-Policy-Algorithmus aus dem Bereich des Reinforcement Learning, der die Vorteile sowohl von Policy-basierten als auch von Value-basierten Verfahren kombiniert. Sowohl die Value Function als auch die Policy Function werden hier gleichzeitig gelernt, was es dem Agenten ermöglicht, sein Verhalten in komplexen und dynamischen Umgebungen effizient zu verbessern. Im Vergleich zu anderen Deep Reinforcement Learning Algorithmen erlaubt Actor-Critic auch die Behandlung von nicht-stationären Umgebungen und hochdimensionalen Observation Spaces. Im Folgenden möchte ich diesen Algorithmus erläutern.

Dieser Algorithmus wird teilweise auch als “REINFORCE with Baseline” bezeichnet. In diesem Beitrag wird er als Actor-Critic-Algorithmus bezeichnet.

Hintergrund des Algorithmus

In unseren bisherigen Beiträgen zum Thema Deep Reinforcement Learning haben wir uns auf sogenanntes value-basierte Reinforcement Learning beschränkt. Die Grundidee dabei ist, dass wir versuchen den Reward einer bestimmten Aktion unter einem gegebenen Zustand vorherzusagen. In sich selbst ist dies kein schlechter Ansatz, aber es gibt einige Probleme, vor allem in Bezug auf die Effizienz der Algorithmen.

In diesem Artikel kombinieren wir value-basiertes Reinforcement Learning mit policy-basiertem Reinforcement Learning. Für beide Teile verwenden wir jeweils ein neuronales Netz, das folgende Aufgaben erfüllt:

1. Actor Network (Policy): In diesem neuronalen Netz versuchen wir eine Parametrisierung unserer Aktionsvorhersage abzubilden. Das bedeutet, dass durch die Eingabe eines Zustands der Umgebung dieses neuronale Netz uns eine Wahrscheinlichkeitsverteilung liefern soll, welche Aktionen der Agent in der Umgebung verwenden soll. Das Ziel des Actors ist es, den in Zukunft zu erhaltenden discounted Return zu maximieren. Die Strategie des Agenten wird dabei durch das Feedback aus der Umgebung und die Einschätzungen des Critics aktualisiert.

2. Critic Network (Value Function): In diesem neuronalen Netz versuchen wir, eine Value Function abzubilden, die die zukünftigen Belohnungen für entweder ein gegebenes Zustands-Aktions-Paar oder nur einen Zustand der Umgebung schätzen soll. Die Rolle des Critics besteht darin, dem Agenten eine Schätzung der erwarteten zukünftigen Belohnungen zu liefern.

Zusammenfassend kann gesagt werden, dass die Policy versucht, eine auszuwählende Aktion zu finden, während die Value Function versucht, uns zu sagen, wie gut unsere ausgewählte Aktion (oder ihr Ergebnis) ist. Durch die Verwendung sowohl einer Policy als auch einer Value Function (anstatt nur einer Value Function wie beim DQN) nutzen wir unsere Trainingsinformationen effizienter, indem wir beide neuronalen Netze gleichzeitig trainieren. ¹

Zusätzlich zu dieser grundlegenden Änderung verwenden wir in diesem Algorithmus nicht $\epsilon$-Greedy für die Exploration, sondern eine softmax Activation Function. Der Hintergrund dazu ist im Kapitel Vor- und Nachteile beschrieben.

Implementierung

Wir beginnen damit, alle notwendigen Imports in unser Skript einzufügen.

import pandas as pd
import plotly.express as px
import tensorflow as tf
import tensorflow_probability as tfp
import numpy as np

import gym

from tensorflow.python.keras import Sequential
from tensorflow.python.keras.optimizer_v2.adam import Adam
from tensorflow.python.keras.layers import InputLayer, Dense
from tensorflow.python.keras.metrics import Mean

from tensorflow_probability import distributions

Dann definieren wir eine Hilfsfunktion, die uns eine Möglichkeit gibt, einen moving average zu berechnen.

def avg_n(list1, n = 50):
    if (len(list1) > n):
        return np.average(list1[len(list1) - n:len(list1)])
    else:
        return np.average(list1[0:len(list1)])

Im nächsten Schritt wird ein Experience Memory erstellt. Im Gegensatz zu den Experience Memories von z.B. Deep Q Network begnügen wir uns hier mit einem Replay Buffer, der die Informationen zu einer Episode einfach in der Reihenfolge hält, in der sie erzeugt wurden. Ein Batching oder Shuffling der Samples ist hier nicht vorgesehen. Hintergrunde hierzu finden sich im Kapitel Vor- und Nachteile.

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 = tf.convert_to_tensor(self.cstate_memory)
        batch_actions = tf.convert_to_tensor(self.action_memory)
        batch_rewards = self.reward_memory.copy()
        batch_pstates = tf.convert_to_tensor(self.pstate_memory)

        return (batch_cstates, batch_actions, batch_rewards, batch_pstates)

Im Folgenden wird eine Actor-Critic-Klasse definiert, die alle notwendigen Funktionen für die Initialisierung, das Speichern von Samples und das Training enthält. Wir beginnen mit der Initialisierung der Klasse und allen Funktionen, die mit dem Replay Memory zu tun haben:

class ACAgent:
    def __init__(self, observation_size, action_size):
        self.observation_size = observation_size
        self.action_size = action_size

        self.gamma = 0.85 # Discount Factor
        self.alpha1 = 10e-5 # Learning Rate
        self.alpha2 = 10e-2 # Learning Rate

        self.memory = TrajectoryExperienceMemory()

        self.actor_model = Sequential([
            InputLayer(input_shape=self.observation_size),
            Dense(units=64, activation='relu',),
            Dense(units=self.action_size, activation='softmax')],
            name="AC_Actor-Network")

        self.critic_model = Sequential([
            InputLayer(input_shape=self.observation_size),
            Dense(units=64, activation='relu'),
            Dense(units=64, activation='relu'),
            Dense(units=1, activation=None)],
            name="AC_Critic-Network")

        self.actor_optimizer = Adam(learning_rate=self.alpha1)
        self.critic_optimizer = Adam(learning_rate=self.alpha2)

    def store_episode(self, cstate, action, reward, pstate):
        cstate = tf.expand_dims(cstate, axis=0)
        pstate = tf.expand_dims(pstate, axis=0)
        self.memory.record(cstate, action, reward, pstate)

    def flush_memory(self):
        self.memory.flush_memory()

In der oben beschriebenen Methode __init__([...]) geschieht folgendes:

1. Wir beginnen damit, die notwendigen Informationen zu liefern, um zu bestimmen, welche Dimensionen unser Observation Space und unser Action Space haben.

2. Anschließend werden die Hyperparameter $\gamma$, $\alpha_1$, $\alpha_2$ definiert. Bei $\gamma$ handelt es sich um den Discount Factor, der bestimmt wie stark vergangene Informationen im Training gewichtet werden. Bei $\alpha_1$ und $\alpha_2$ handelt es sich um die Learning Rates der beiden neuronalen Netze, wobei sich der Index $1$ sich auf den Actor und der Index $2$ auf den Critic bezieht.

3. Im nächsten Schritt werden die beiden neuronalen Netze self.actor_model und self.critic_model zusammen mit dem Experience Memory initialisiert. Hierbei ist darauf zu achten, dass der Actor im letzten Layer eine softmax-Activation besitzt, da diese den Output in eine Wahrscheinlichkeitsverteilung umwandelt. Für den Critic besitzt der Layer nur ein Neuron, da mit diesem Netz eine eindimensionale Regression durchgeführt werden soll.

4. Zuletzt werden die beiden Optimizer initialisiert. Dabei werden die beiden zuvor definierten Learning Rates übergeben.

Die beiden Funktionen store_episode([...]) und clear_episode([...]) werden für die Verwaltung des Experience Memories verwendet.

Im nächsten Schritt wird eine Implementierung betrachtet, wie eine Aktion aus einem Input entnommen werden kann:

@tf.function
def sample_action(self, observation):
    observation = tf.expand_dims(observation, axis=0)
    prob = self.actor_model(observation)

    distribution = tfp.distributions.Categorical(probs=prob, dtype=tf.float32)
    action = distribution.sample()
    return int(action[0])

Die Funktion sample_action besteht aus folgenden Schritten:

1. Zunächst wird die Dimension der Eingabedaten um eine Dimension erhöht. Dies liegt daran, dass die hier verwendete Implementierung eines neuronalen Netzes eine Reihe von Eingangsdaten auf diese Weise übergeben möchte.

2. Im nächsten Schritt werden die angepassten Daten dem neuronalen Netz zur Verarbeitung übergeben.

3. Im letzten Schritt werden die hier ausgegebenen Daten verwendet, um eine Aktion aus der Wahrscheinlichkeitsverteilung zu extrahieren. Dies wird durch eine kategorische Wahrscheinlichkeitsverteilung erreicht, die durch das Paket tensorflow_probability bereitgestellt wird.

Wenn eine Umgebung verwendet wird, die stetige Einwirkungswerte anstatt diskreter Werte übergeben möchte, kann tfp.distributions.Categorical nicht verwendet werden. Stattdessen muss eine Wahrscheinlichkeitsverteilung verwendet werden, die speziell für diesen Anwendungsfall entwickelt wurde, z. B. eine Normalverteilung.

Im letzten Schritt der Definition der Actor-Critic-Klasse benötigen wir nun noch Funktionalität bezüglich des Trainings. Eine Implementierung könnte hier wie folgt aussehen:

def actor_loss(self, probs, action, reward):
    distribution = tfp.distributions.Categorical(probs=probs, dtype=tf.float32)
    log_probs = distribution.log_prob(action)
    actor_loss = - log_probs * reward

    return actor_loss

def train(self, cstates, actions, discounted_rewards, pstates):
    ## Update critic network
    cstates = tf.squeeze(cstates, axis=1)
    pstates = tf.squeeze(pstates, axis=1)

    with tf.GradientTape() as tape1:
        c_value = tf.squeeze(self.critic_model(cstates, training=True))
        p_value = tf.squeeze(self.critic_model(pstates, training=True))

        mask = tf.eye(c_value.shape[0])[-1, :] - 1 # Unit vector - 1
        temp_difference = discounted_rewards - self.gamma * (mask * p_value) - c_value

        critic_loss = tf.square(temp_difference)

    critic_gradients = tape1.gradient(critic_loss, self.critic_model.trainable_variables)
    self.critic_optimizer.apply_gradients(zip(critic_gradients, self.critic_model.trainable_variables))

    ## Update Actor Model incrementally
    cstates = tf.expand_dims(cstates, axis=1)
    for i in range(temp_difference.shape[0]):
        with tf.GradientTape() as tape2:
            probs = self.actor_model(cstates[i], training=True)
            actor_loss = self.actor_loss(probs, actions[i], temp_difference[i])

        actor_gradients = tape2.gradient(actor_loss, self.actor_model.trainable_variables)
        self.actor_optimizer.apply_gradients(zip(actor_gradients, self.actor_model.trainable_variables))

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

Im nächsten Schritt unserer Code-Definition verwenden wir nun die Funktion training_loop für die Trainingsschleife. Diese ist äquivalent zu den Trainingsschleifen des Algorithmus “Deep Q Network” implementiert.

def training_loop(env, agent: ACAgent, max_frames_episode):
  current_obs, _ = env.reset()
  episode_reward = 0

  agent.flush_memory()

  for j in range(max_frames_episode):
    action = agent.sample_action(current_obs).numpy()

    next_obs, reward, done, _, _ = env.step(action)
    next_obs = np.array(next_obs)

    agent.store_episode(current_obs, action, reward, next_obs)

    current_obs = next_obs
    episode_reward += reward

    if done:
      break

  return episode_reward, agent

Zum Schluss müssen noch alle Definitionen und Befehle eingegeben werden, die notwendig sind, um das Training zu starten:

n_episodes, max_frames_episode, current_episode, avg_length, evaluation_interval = 1000, 500, 0, 50, 10
episodic_reward, avg_reward, evaluation_rewards = [], [], []

env = gym.make("CartPole-v1")

seed = 69
tf.random.set_seed(seed)
np.random.seed(seed)

n_actions = env.action_space.n
observation_shape = env.observation_space.shape[0]

agent = ACAgent(observation_shape, n_actions)

for i in range(n_episodes):
    current_episode += 1
    episode_reward, agent = training_loop(env, agent, max_frames_episode)

    episodic_reward.append(episode_reward)
    current_average = avg_n(episodic_reward, n=avg_length)
    avg_reward.append(current_average)
    agent.update()

    print(f"[i={i}] Episodic reward: {episode_reward} | Current running average reward: {current_average}")

Nach der Ausführung des oben definierten Skripts können wir alle berechneten Daten auswerten. Im Folgenden haben wir dazu einmal den Episodic Reward über $50$ Episoden gemittelt und über den Trainingsverlauf dargestellt:

Um die hier berechneten Daten noch besser einordnen zu können, haben wir auch eine Visualisierung der Daten des Actor-Critic-Algorithmus im Vergleich zu denen des “Deep Q Network”-Algorithmus vorbereitet.

Aus den hier vorliegenden Daten lässt sich interpretieren, dass der Actor-Critic-Algorithmus einen erheblichen technologischen Fortschritt gegenüber dem mittlerweile relativ alten “Deep Q Network”-Algorithmus darstellt. Bereits innerhalb der ersten $100$ Episoden zeigt sich ein signifikanter Leistungsunterschied, der sich über die verbleibenden $900$ Episoden verstärkt.

Vor- und Nachteile

Der Actor-Critic-Algorithmus ist ein populärer Algorithmus aus dem Bereich des Deep Reinforcement Learning. Durch die Kombination von value-basierten Methoden durch den Critic und policy-basierten Methoden durch den Actor ergeben sich spezifische Vor- und Nachteile.

Vorteile

Effektivität und Skalierbarkeit

Durch den Einsatz von Policy-based Reinforcement Learning können wir mit diesem Algorithmus hochdimensionale Probleme effizienter optimieren als mit value-basierten Verfahren. ^{2 3}

Sample Efficiency und Stabilität

Durch die Verwendung von value-basiertem Reinforcement Learning sind wir in der Lage, mit diesem Algorithmus eine sehr gute Sample Efficiency und Stabilität zu erreichen. Dies macht den Algorithmus zu einer zuverlässigen Option für Reinforcement Learning Anwendungen. ²

Balance zwischen der Exploration und Exploitation

Mit Hilfe der softmax Activation Function können wir einen Vektor von numerischen Werten in einen Wahrscheinlichkeitsverteilungsvektor umwandeln. Aus diesem Vektor können wir dann unsere Aktionen zufällig ziehen. ⁴ Dabei können wir die Exploration und die Exploitation im Verfahren wie folgt beschreiben:

1. Exploration: Durch die Umwandlung in einen Wahrscheinlichkeitsverteilungsvektor haben wir immer eine Restwahrscheinlichkeit, dass eine Aktion mit geringer Wahrscheinlichkeit gezogen wird. Dies fördert die Exploration, da der Agent im Laufe der Zeit verschiedene Aktionen ausprobieren wird, die normalerweise nicht vom Modell vorhergesagt worden wären.

2. Exploitation: Durch die Anwendung der Softmax-Funktion werden die Aktionen mit den höchsten numerischen Werten auch später die höchsten Wahrscheinlichkeiten haben. Durch diese Eigenschaft wird unser Verfahren weiterhin mit höherer Wahrscheinlichkeit die Aktionen auswählen, die der Agent als die besten wahrnimmt.

Parallelisierbarkeit

Eine Möglichkeit zur Verbesserung des Algorithmus ist die Parallelisierung. Hierbei werden mehrere parallele Instanzen der Umgebung inklusive einzelner Actor-Critic-Modelle initialisiert, die in regelmäßigen Abständen synchronisiert werden, häufig durch ein zentrales Modell, das nicht direkt auf einer Instanz trainiert wird und nur zur Synchronisation dient. Diese Verbesserung ist stabiler und effizienter, da Daten über die einzelnen Instanzen dekorreliert werden und somit mehr Trainingsinformationen generiert werden, als wenn dies nur von einer einzigen Instanz generiert wird. ^{5 6}

Weitere Informationen hierzu können in dem Paper zum Asynchronous Advantage Actor Critic (A3C) gefunden werden.

Nachteile

Konvergenzschwierigkeiten

Bei dem Actor-Critic-Algorithmus kann es zu Konvergenzproblemen kommen. In einer anderen Formulierung wird sas Verhalten unseres Agenten wird durch die Schrittweite $\alpha$ und durch das folgende Update bestimmt, welches sich aus der Policy-Gradient-Updatefunktion ergibt:

Bei einer solchen Aktualisierung können zwei Arten von Problemen auftreten:

1. Overshooting: Die Aktualisierung verfehlt das Maximum der Belohnung und landet in einem Bereich des Parameterraums, in dem wir ein suboptimales Ergebnis in Bezug auf die Belohnung erhalten.

2. Undershooting: Durch die Verwendung einer unnötig kleinen Schrittweite benötigen wir eine große Anzahl von Aktualisierungen, um das Optimum unserer Modellparameter zu erreichen.

Im Bereich des Supervised Learnings stellt Overshooting kein allzu großes Problem dar. Bei konstanten Daten ist der Optimizer in der Lage, ein Overshooting in der nächsten Trainingsepisode zu korrigieren. Undershooting führt jedoch auch hier zu einer Verlangsamung der Konvergenz.

Im Gegensatz zum Supervised Learning ist das Overshooting im Bereich der Policy Gradient Algorithmen des Deep Reinforcement Learning jedoch potenziell dramatisch. Wenn eine Parameteraktualisierung zu einem schlechten Modellverhalten führt, kann es sein, dass aus zukünftigen Aktualisierungen keine nützlichen Informationen mehr gewonnen werden können. Dies kann letztlich dazu führen, dass sich das Modell aufgrund eines einzigen schlechten Updates nie wieder verbessert und somit keinen Lerneffekt mehr aufweist. ⁷

Probleme mit der Konvergenzgarantie

Die Konvergenzgarantie ist ein wichtiger Aspekt der Reinforcement-Learning-Theorie. Die Konvergenzgarantie stellt sicher, dass der Algorithmus am Ende eine optimale oder nahezu optimale Lösung findet. Für Actor-Critic-Methoden kann die Konvergenz jedoch aus mehreren Gründen schwierig sein: ¹

1. Zwei Netzwerke: Actor-Critic-Methoden verwenden zwei getrennte Netzwerke (das Actor- und das Critic-Netzwerk), die gleichzeitig trainiert werden müssen. Dies kann zu Instabilitäten führen, da Verbesserungen oder Verschlechterungen in einem Netzwerk die Leistung des anderen Netzwerks beeinflussen können.

2. Hohe Varianz: Actor-Critic-Methoden können eine hohe Varianz in den Gradientenschätzungen aufweisen. Dies kann dazu führen, dass der Algorithmus in lokalen Minima stecken bleibt oder nicht konvergiert.

Sensitivität bezüglich der Hyperparameter

Der Actor-Critic-Algorithmus weist eine hohe Sensitivität gegenüber den Hyperparametern auf. Dies bedeutet, dass die Wahl der Hyperparameter einen starken Einfluss auf das Ergebnis des Trainings und die resultierende Leistung des Modells haben kann. Dies hat im Wesentlichen zwei Ursachen:

1. Statt nur einem neuronalen Netz wie beim Deep Q Network Algorithmus stehen hier zwei neuronale Netze zur Verfügung. Dadurch ergibt sich eine deutlich höhere Anzahl von Hyperparametern, die für das Training relevant sind.

Grundsätzlich kann versucht werden, ein gemeinsames neuronales Netz für Actor und Critic zu trainieren. Dabei werden die Daten in das neuronale Netz eingegeben und im Verlauf des Netzes wird dann eine Trennung vorgenommen und zwei Datenausgaben definiert: Einmal die Wahrscheinlichkeitsverteilung für den Actor und den Regressionswert für den Critic. Dies ist z.B. mit der Tensorflow Functional API möglich, beseitigt aber nicht das Problem von mehr Hyperparametern. Es wird lediglich versucht, den Hyperparameterraum zu verkleinern. Außerdem gibt es keine Garantie, dass dies tatsächlich zu besseren Ergebnissen führt als mit zwei verschiedenen Netzen.

2. Höhere Varianz der Gradienten: Eine potenziell höhere Varianz in den Gradienten wird durch die kombinierte Schätzung der Aktualisierungen sowohl aus dem Actor Network als auch aus dem Critic Network erreicht.

Insgesamt bedeutet die Hyperparametersensitivität für den Algorithmus, dass häufiger als bei anderen Algorithmen eine Hyperparameteroptimierung durchgeführt werden muss, um optimale Ergebnisse zu erzielen. ⁸

Geringere Sample Efficiency

Im Vergleich zu Off-Policy Algorithmen aus dem Bereich des Reinforcement Learning wird hier eine andere Art von Memory Buffer verwendet. Im Memory Buffer der Off-Policy-Algorithmen können wir viele Informationen aus der Vergangenheit speichern und wiederverwenden. Bei On-Policy-Algorithmen ist dies grundsätzlich nicht zielführend, da die Wiederverwendung alter Informationen nicht zwangsläufig zu einer Verbesserung der Modellleistung führt. ⁹

Anmerkung des Autors: In meinen Experimenten mit einem Off-Policy Memory Buffer ist der Lernprozess sogar komplett zusammengebrochen, so dass das Modell überhaupt nicht mehr gelernt hat. Dieses Verhalten ist wahrscheinlich auf das Policy-Gradient-Theorem zurückzuführen.

Es ist wichtig festzuhalten, dass trotz dieser Herausforderungen Actor-Critic-Methoden in der Praxis oft gut funktionieren und für viele Aufgaben erfolgreich eingesetzt werden. Es gibt auch viele Varianten und Verbesserungen der grundlegenden Actor-Critic-Methode, die darauf abzielen, diese Probleme zu verringern.

TL;DR

Im Rahmen dieses Posts haben wir eine Weiterentwicklung im Bereich des Deep Reinforcement Learning vorgestellt: Den Actor-Critic-Algorithmus. Dieser zeichnet sich dadurch aus, dass neben einem Value Network zusätzlich ein Policy Network verwendet und trainiert wird. Die Vorteile dieses Algorithmus liegen beispielsweise in der Effizienz des Lernprozesses sowie in der Fähigkeit, mit hochdimensionalen Daten umgehen zu können. Auf der anderen Seite stehen die Sensitivität gegenüber Hyperparametern oder potentielle Konvergenzprobleme, die auftreten können und den Lernprozess dieses Algorithmus behindern können.

Quellen