Double Deep Q-Network: DQN mit Stabilitätsupgrades • Aggregata

Einordnung

In einem früheren Post wurde das Prinzip des Deep Q-Networks vorgestellt. Bei genauerer Untersuchung des Netzwerkes stellt sich häufig heraus, dass das Modell unter Overestimation leidet, welches das Training instabil werden lässt.

Overestimation beschreibt das Prinzip, das erwartete Rewards als zu hoch vorhergesagt werden.

Overestimation verringert hierbei die Güte des Trainingsprozesses und sollte damit verringert oder vermieden werden.

Eine weitere Erklärung für Probleme im DQN ist die Tatsache, dass das sogenannte Q-Target kein konstanter Wert ist.

Als Q-Target wir der Term $y_i = r_i + \gamma max_{a'_i} Q(s'_i, a'_i)$ in $L = \frac{1}{N} \sum_{i = 0}^{N - 1} (Q(s_i, a_i) - y_i)^2$ bezeichnet.

Durch die Approximation eines nicht konstanten Wertes ist die Approximation grundsätzlich instabiler. Ein Target-Network verringert die Problematik hierbei. ¹ ²

Die Forschung im Bereich der künstlichen neuronalen Netze erzielte dann ab dem Jahr 2010 Erfolge darin, dieser Algorithmus zu verbessern. Das Ergebnis wurde als Double Deep Q-Network bezeichnet. Im Gegensatz zu Deep Q-Networks verzichtet es hierbei auf Frozen Target-Networks, um unter anderem die oben angesprochene Overestimation weiter zu verringern.

Im Folgenden kann dieser Algorithmus auch als D2QN bezeichnet werden.

Versionen des Algorithmus

Die folgenden Informationen über die verschiedenen Arten des Algorithmus wurden aus der Quelle ³ entnommen.

Das Grundprinzip des Algorithmus besteht darin, dass eine Kombinnation aus zwei verschiedenen Netzwerken verwendet wird, um die Overestimation zu verringern. Dies geschieht dadurch, dass die beiden Netze miteinander trainiert werden, und so den Bias aus den Netzwerk-Updates herausbekommen.

Das Paper dazu kann hier eingesehen werden.

Hasselt, 2010

Double Q-Learning: Extrahiert von 4

Der ursprüngliche Algorithmus aus dem Jahr 2010 beinhaltet zwei verschiedene Netzwerke, welche in einer Art $\epsilon$ -greedy-Schema (mit $\epsilon = 0.5$ ) ausgewählt werden. In jedem Zeitschritt wird ein zufälliges Netzwerk ausgewählt, das Update wird anschließend über den Mean Squared Error des Unterschiedes in der Vorhersage gefittet.

Problematisch bei dieser Implementierung (im Vergleich zu den neueren Alternativen) liegt darin, dass theoretisch jedem Netzwerk lediglich $50 \%$ der generierten Informationen zukommen, die anderen 50 % werden nicht für Updates des anderen Netzwerkes verwendet. Dies verringert die Sample Efficiency des Algorithmus bedeutend. Weiterhin kann das Problem der Overestimation noch weiter verbessert werden.

Sample Efficieny beschreibt wie effizient ein Algorithmus aus den gegebenen Informationen lernen kann; ein effizienter Algorithmus wird mit bedeutend weniger Episoden (Samples) auskommen.

Hasselt, 2015

Double Q-learning: Extrahiert von 4

Der Algorithmus aus dem Jahr 2015 stellt einen großen Meilenstein in der Entwicklung des DDQN-Algorithmus dar. Hier wird das erste Mal ein Primary- und Target-Network eingeführt. Diese beiden Netzwerke sind hierbei nur als teilweise unabhängig definiert, beide werden am Anfang auch klassischerweise mit den identischen Gewichten initialisiert.

Das Primary-Network stellt das Netzwerk dar, welches für die Auswahl der Aktionen in Abhängigkeit des aktuellen Zustands verantwortlich ist.

Das Target-Network stellt das Netzwerk dar, welches die Overestimation verhindert. Es stellt einen “älteren Zustand” des Netzwerkes dar und verhindert das schnelle Vergessen von Informationen, welche bereits durch das Primary-Network gelernt wurden. Das Target-Network “bewertet” damit die ausgewählte Aktion.

Eine wichtige Änderung ist hierbei das Update der Netzwerke. Der Target-Q-Value für das Primary-Network wird hierbei durch die Voraussage des Target-Networks bestimmt und über Mean Squared Error gefittet, während wir bei dem Target-Network ein Soft-Update durchführen:

$\theta' \leftarrow \tau \theta + (1 - \tau) \theta'$

Hierbei gilt für die Konstante $\tau$ klassischerweise die folgende Beschränkung: $\tau \in (0, 1)$ . Für den Grenzfall $\tau = 1$ erhält man zwei identische Netzwerke, für $\tau = 0$ erhält man kein Update auf dem Target-Network. Hierdurch würde es nicht mehr lernen.

Das Original-Paper zu diesem Algorithmus von Hasselt ist hier zu finden.

Fujimoto et al., 2018

Clipped Double Q-Learning: Extrahiert von 4

Eine kleine Verbesserung wurde anschließend noch 2018 veröffentlicht. Man kann die Overestimation noch dadurch verringern, indem man das Minimum der Voraussage von den beiden Netzwerken dafür verwendet, den Target-Q-Value zu berechnen. Ansonsten existiert hier kein Unterschied zu der Veröffentlichung von 2015.

Implementierung

Unter den Imports findet sich nichts Neues, diese sind identisch zu der Implementierung vom Deep Q-Network. Auch das ExperienceMemory ist identisch.

d2qn.py

import datetime
import math
import gym

import numpy as np
import tensorflow as tf
import matplotlib.pyplot as plt

from collections import deque
from tensorflow.python.keras.models import Sequential
from tensorflow.python.keras.layers import Dense, InputLayer
from tensorflow.python.keras.optimizer_v2.adam import Adam

d2qn.py

class ExperienceMemory:
    def __init__(self, memory_length: int=10000, batch_size: int=64, nonunique_experience: bool=True):
        self.memory_length = memory_length
        self.batch_size = batch_size
        self.nonunique_experience = nonunique_experience

        # ** Initialize replay memory D to capacity N **
        self.cstate_memory = deque([], maxlen=self.memory_length)
        self.action_memory = deque([], maxlen=self.memory_length)
        self.reward_memory = deque([], maxlen=self.memory_length)
        self.done_memory = deque([], maxlen=self.memory_length)
        self.pstate_memory = deque([], maxlen=self.memory_length)

    def record(self, cstate, action, reward, done, pstate):
        # Convert states into processable objects
        cstate = tf.expand_dims(tf.convert_to_tensor(cstate), axis=0)
        pstate = tf.expand_dims(tf.convert_to_tensor(pstate), axis=0)

        # Save data
        self.cstate_memory.append(cstate)
        self.action_memory.append(action)
        self.reward_memory.append(reward)
        self.done_memory.append(done)
        self.pstate_memory.append(pstate)

    def return_experience(self):
        # Retrieve experience
        batch_indices = np.random.choice(len(self.cstate_memory), size=self.batch_size, replace=self.nonunique_experience)
        batch_cstate = np.array(list(self.cstate_memory))[batch_indices, :]
        batch_action = np.take(list(self.action_memory), batch_indices)
        batch_reward = np.take(list(self.reward_memory), batch_indices)
        batch_done = np.take(list(self.done_memory), batch_indices)
        batch_pstate = np.array(list(self.pstate_memory))[batch_indices, :]

        # Convert experience into respective tensorflow tensors
        cstates = tf.squeeze(tf.convert_to_tensor(batch_cstate))
        actions = tf.convert_to_tensor(batch_action)
        rewards = tf.convert_to_tensor(batch_reward, dtype=tf.float32)
        dones = tf.convert_to_tensor(batch_done, dtype=tf.int64)
        pstates = tf.squeeze(tf.convert_to_tensor(batch_pstate))

        return (cstates, actions, rewards, dones, pstates)

    def flush_memory(self):
        self.cstate_memory.clear()
        self.action_memory.clear()
        self.reward_memory.clear()
        self.done_memory.clear()
        self.pstate_memory.clear()

d2qn.py

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

    # Network Parameters
    self.alpha = math.pow(10, -3)
    self.gamma = 0.97
    self.epsilon = 0.79
    self.min_epsilon = 0.05
    self.epsilon_decay = 0.85
    self.tau = 0.005

    # Experience Replay Parameters
    self.memory_length = 26000
    self.batch_size = 64
    self.nonunique_experience = True
    
    # ** Initialize replay memory D to capacity N **
    self.experience_memory = ExperienceMemory(self.memory_length, self.batch_size, self.nonunique_experience)

    # ** Initialize action-value function Q with random weights **
    self.primary_model = Sequential([
            InputLayer(input_shape=self.observation_size, name="Input_Layer"),
            Dense(units=128, activation='relu', name='Hidden_Layer_1'),
            Dense(units=self.action_size, activation='linear', name='Output_Layer')], name="Primary-Q-Network")
    self.primary_model.compile(loss="mse", optimizer=Adam(learning_rate=self.alpha))
    self.primary_model.summary()

    self.target_model = Sequential([
            InputLayer(input_shape=self.observation_size, name="Input_Layer"),
            Dense(units=128, activation='relu', name='Hidden_Layer_1'),
            Dense(units=self.action_size, activation='linear', name='Output_Layer')], name="Target-Q-Network")
    self.target_model.set_weights(self.primary_model.get_weights())

    # Define metrics for tensorboard
    self.score_log_path = 'logs/' + datetime.datetime.now().strftime("%Y%m%d-%H%M%S")
    self.score_writer = tf.summary.create_file_writer(self.score_log_path)

  def compute_action(self, observation, evaluation: bool=False):
    if (np.random.uniform(0, 1) < self.epsilon and evaluation == False):
      return np.random.choice(range(self.action_size)) # ** With probability epsilon select a random action a_t **
    else:
      observation = np.expand_dims(observation, axis=0)
      Q_values = self.primary_model([observation])
      return np.argmax(Q_values) # ** Otherwise select a_t = argmax(Q) **

  def update_epsilon_parameter(self):
    self.epsilon = max(self.epsilon * math.exp(-self.epsilon_decay), self.min_epsilon)

  def store_step(self, cstate, action, reward, done, pstate):
    self.experience_memory.record(cstate, action, reward, done, pstate)

In der DDQNAgent-Klasse könnten einem schnell ein paar Änderungen ins Auge fallen. Hier ist eine klare Trennung zwischen primary_network und target_network, welche identisch initialisiert werden müssen. Zusätzlich wurde der Soft-Update-Parameter $\tau \in [0, 1]$ hier definiert. Ansonsten findet sich hierbei keine Änderung.

d2qn.py

  def train(self): # **For each update step**
    # ** Sample random minibatch of transitions from D**
    b_cstate, b_action, b_reward, b_done, b_pstate = self.experience_memory.return_experience()

    # ** Set y_j **
    prediction_primary_model = self.primary_model(b_pstate)
    prediction_target_model = self.target_model(b_pstate)
    q_value_network = np.zeros((self.batch_size,))

    b_done = b_done.numpy()
    max_primary_pred = np.max(prediction_primary_model, axis=1)
    max_target_pred = np.max(prediction_target_model, axis=1)
    min_pred = np.min(np.transpose(np.squeeze([max_primary_pred, max_target_pred])))

    q_value_network = (1 - b_done) * self.gamma * min_pred
    target_q_p = np.add(b_reward, q_value_network)

    # **Perform gradient descent step on Q**
    self.primary_model.train_on_batch(b_cstate, target_q_p)

    # Perform soft updates
    update_target(self.target_model.variables, self.primary_model.variables, self.tau)

Bei der Trainingsfunktion findet man direkt die Änderung zum Deep Q-Network, welche sich in der Berechnung des Q-Targets findet. Hierbei wird diesmal nicht nur primary_network oder target_network verwendet, um das Q-Target zu berechnen, sondern jeweils komponentenweise das Minimum der Vorhersagen. Anschließend wird hierbei das primary_network auf dem Q-Target gefittet und das target_network über ein Soft-Update updatet.

d2qn.py

@tf.function
def update_target(target_weights, weights, tau: float):
    for (target_weight, primary_weight) in zip(target_weights, weights):
        target_weight.assign(primary_weight * tau + target_weight * (1 - tau))

d2qn.py

def training_loop(env, agent: DDQNAgent, max_frames_episode: int):
  current_obs, _ = env.reset()

  episode_reward = 0
  for j in range(max_frames_episode):
    action = agent.compute_action(current_obs)

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

    current_obs = next_obs
    episode_reward += reward

    if done:
      agent.update_epsilon_parameter()
      break

  return episode_reward, agent

def evaluation_loop(env, agent: DDQNAgent, max_frames_episode: int):
  current_obs, _ = env.reset()
  evaluation_reward = 0
  for j in range(max_frames_episode):
    # ** Execute action a_t in emulator and observe reward r_t and image x_{t+1}
    action = agent.compute_action(current_obs, evaluation=True)

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

    # **Storing all information about the last episode in the memory buffer**
    agent.store_step(current_obs, action, reward, done, next_obs)

    # Reseting environment information so that next episode can handle the previous information
    current_obs = next_obs
    evaluation_reward += reward

    if done:
      break
  
  return evaluation_reward, agent

Die Trainings- und Evaluierungsloops orientiert sich am Standard von der Implementierung des Deep Q-Networks’s.

d2qn.py

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

env = gym.make("CartPole-v1")
n_actions = env.action_space.n
observation_shape = env.observation_space.shape[0]

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

agent = DDQNAgent(observation_shape, n_actions)
eval_reward, episode_reward = 0, 0

for i in range(n_episodes):
    # **Observing state of the environment**
    episode_reward, agent = training_loop(env=env, agent=agent, max_frames_episode=max_frames_episode)
    
    print("Training Score in Episode {}: {}".format(i, episode_reward))

    if (i % evaluation_interval == 0):
      # Evaluation loop
      eval_reward, agent = evaluation_loop(env=env, agent=agent, max_frames_episode=max_frames_episode)
      print("Evaluation Score in Episode {}: {}".format(i, eval_reward))

    with agent.score_writer.as_default():
      tf.summary.scalar('Episodic Score', episode_reward, step=i)
      if (i % evaluation_interval == 0):
        tf.summary.scalar('Evaluation Score', eval_reward, step=i)

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

Als Ergebnis erhält man beispielsweise das folgende Diagramm:

Hinweis: Trainingsperformance kann sich von Gerät zu Gerät und entsprechenden Seeds teilweise stark unterscheiden. Allgemeine Reproduzierbarkeit von solchen Ergebnissen ist im Allgemeinen nicht garantierbar.

Hierbei kann man klar erkennen, dass das D2QN am Anfang bedeutend besser traininert als dies das DQN tut. Später flacht der Erfolg allerdings ab, was wahrscheinlich auf eine schlechte Einstellung der Hyperparameter zurückzuführen ist.

Zum Vergleich wurden zwei Netzwerke von ähnlicher Struktur verwendet; beide Netzwerke (dqn_network und primary_network) hatten hierbei die gleiche Anzahl von Neuronen. Dies muss bei praktischer Anwendung nicht zielführend sein sondern gilt hier lediglich der Vergleichbarkeit.

Änderungen

[23.01.2023] Einführung interaktiver Plots, Hinweis auf Nicht-Reproduzierbarkeit von Ergebnissen

Einordnung

Versionen des Algorithmus

Hasselt, 2010

Hasselt, 2015

Fujimoto et al., 2018

Implementierung

Änderungen

Quellen

Footnotes