Ist das sicher die schnellste Route?

https://www.google.com/maps

Fahrzeit kann stark schwanken.

https://commons.wikimedia.org/wiki/File:Traffic_jam_in_Bangkok.JPG

Zustand $s$ + Aktion $a$ $\rightarrow$ Zustand $Succ(s, a)$
Deterministisch

Markov Decision Process

Benannt nach Andrei Markow, da sie das Konzept der Markow-Ketten erweitern.

Konzept stammt aus den 1950er-60er Jahren.

Anwendungsgebiete:

• Roboter trifft auf unbekanntes Hindernis
• Ausfall einer Aktuators
• Schwankender Ertrag eines Feldes
• Wechselnde Kundennachfrage

Wirklich deterministisch sind die wenigsten Probleme.

Beispiel: Würfelspiel

• Du startest mit 0 Talern.
• Du kannst wählen, ob du weitermachst oder aufhörst.
• Wenn du aufhörst bekommst du 10 Taler.
• Wenn du weitermachst bekommst du 4 Taler und wir würfeln:
  • 1-2: Das Spiel endet.
  • 4-6: Du kannst noch eine Runde spielen.

Start Weitermachen Aufhören

Gewinn: 0

Würfelwurf: -

Wahrscheinlichkeitstheorie

• Zufallsvariablen $X$
• Werte von ZV $X=x$
• Wahrscheinlichkeiten $P(X=x)$
• Wahrscheinlichkeitsverteilung $P(X)$
• Erwartungswert $E(X) = \sum_x x P(X=x)$
• Bedingte Wahrscheinlichkeit $P(X=x | Y=y)$

Angenommen wir hören immer direkt auf

Gewinn (Erwartungswert): $10$

Angenommen wir spielen immer weiter

Gewinn (Erwartungswert):
$4 + \frac{2}{3} \cdot 4 + \frac{2}{3} \cdot \frac{2}{3} \cdot 4 + \frac{2}{3} \cdot \frac{2}{3} \cdot \frac{2}{3} \cdot 4 + \ldots$

$= 4 \cdot \sum_{i=0}^{\infty} (\frac{2}{3})^i$ $= 4 \cdot \frac{1}{1-\frac{2}{3}} = 4 \cdot 3 = 12$

Macht eine gemischte Strategie Sinn?
Z.B. 2 x "weitermachen" und dann aufhören?

Nein, den Würfel interessiert nicht, ob wir vorher schon gespielt haben, oder nicht.

→ Markov Eigenschaft (Historie irrelevant; Zustand hat kein Gedächtnis)

Modellierung

Wir wollen ein generelles Framework, das auch mit Problemen umgehen kann, die wir nicht direkt lösen können.

Neben den Zuständen brauchen wir Knoten, welche die Zufallsentscheidung repräsentieren (Chance nodes).

Ein MDP besteht aus:

• Einer Menge an möglichen Zuständen $S$
• Einem initialen Zustand $s_{start}$
• Einer Menge von Zielzuständen $S_{target}$, bzw. Funktion $IsEnd(s)$
• Aktionen die in einem bestimmten Zustand gemacht werden können $\text{Actions}(s)$
• $T(s, a, s') = P(s' | s,a)$: Wahrscheinlichkeit, dass wir von $s$ durch $a$ nach $s'$ kommen (Es muss gelten: $\sum_{s' \in S} T(s, a, s') = 1$)
• $Reward(s, a, s')$: Gewinn, wenn wir aus $s$ durch $a$ nach $s'$ gehen
• Discount Faktor $0 \leq \gamma \leq 1$

Unterschiede zu Suchproblemen

• Aus $Succ(s,a)$ wird $T(s, a, s')$
• Aus $Cost(s,a)$ wird $Reward(s, a, s')$
  • $\min f(x) = \max -f(x)$

Jupyter

          class SlotmachineMDP:
              def __init__(self, n):
                  self.n = n

              def start_state(self):
                  return 1

              def is_end(self, state):
                  return state == self.n

              def actions(self, state):
                  result = []
                  if state + 1 <= self.n:
                      result.append('linker Hebel')
                  if state * 2 <= self.n:
                      result.append('rechter Hebel')
                  return result

              def succ_prob_and_reward(self, state, action):
                  # Return list of (newState, probability, reward) triples
                  result = []

                  if action == "linker Hebel":
                      result.append((state + 1, 1., -1.))
                  if action == "rechter Hebel":
                      result.append((state * 2, 0.5, -2.))
                      result.append((state, 0.5, -2.))

                  return result

              def discount(self):
                  return 1.

              def states(self):
                  return list(range(1, self.N+1))
        

Was ist eine Lösung für ein MDP?

Ein Pfad wie bei den Suchproblemen reicht nicht aus.

Wir wollen ein Regelwerk, was wir in welcher Situation machen.

Eine Policy $\pi$ ist ein Mapping von jedem Zustand $s$ auf eine Aktion $a \in \text{Actions}(s)$.

Eine Policy führt zu einem Random Walk.

Die Utility einer Policy ist die Summe der Rewards auf dem Pfad / Episode. (Zufallsvariable)

Der Value einer Policy ist der Erwartungswert der Utility. Diesen wollen wir maximieren.

Policy: $\pi(Aktiv) = Weitermachen$

Value: 12

Exkurs: Maximierung Erwartungswert

Wir haben einen Besitz von 1000 Talern und stehen vor folgender Entscheidung:
Option A: Mit 50% Wahrscheinlichtkeit bekommen wir 100 und ansonsten verlieren wir 80 Taler.
Option B: Mit 1% Wahrscheinlichkeit bekommen wir 500 000 und ansonsten verlieren wir 1000 Taler.

Wir sind (oft zu recht) risikoavers. Ein Ergebnis mit maximalem Erwartungswert ist manchmal doch unerwünscht.

Discounting

Der Discounting Faktor $\gamma$ verringert der Wert zukünftiger Rewards.

Wenn wir Rewards $[r_1, r_2, r_3, r_4, \ldots]$ auf dem Pfad einsammeln, dann gilt:
Utility $u = r_1 + \gamma r_2 + \gamma^2 r_3 + \gamma^3 r_4 + \ldots$

Bei einem Pfad mit vier mal Weitermachen bekommen wir:

Intuitive Motivation für Discount: Lieber den Spatz in der Hand, als die Taube auf dem Dach.

Finanzmathematisch: Anstatt auf mein Geld zu warten, hätte ich es mit Zinsen anlegen können.

Welchen Discount Faktor wir nehmen hängt komplett davon ab, was wir modellieren und erreichten wollen.

Bewertung einer Policy

Value: Sei $V_\pi(s)$ die erwartete Utility (Value) von Policy $\pi$ im Zustand $s$.

Q-value: Sei $Q_\pi(s,a)$ die erwartete Utility, wenn wir Aktion $a$ im Zustand $s$ nehmen.

Rekursiver Zusammenhang zwischen $V$ und $Q$

\[ V_\pi(s) = \begin{cases} 0 & if\ IsEnd(s) \\ Q_\pi(s, \pi(s)) & else \end{cases} \]

\[ Q_\pi(s, a) = \sum_{s' \in S} T(s, a, s') (Reward(s, a, s') + \gamma V_\pi(s')) \]

Beispiel: Würfelspiel

Unsere Policy sei $\pi(\text{Aktiv}) = \text{Weitermachen}$.

$V_\pi(\text{Beendet}) = 0$

$V_\pi(\text{Aktiv}) = Q_\pi(\text{Aktiv}, \text{Weitermachen})$

$= \frac{1}{3}(4 + V_\pi(\text{Beendet})) + \frac{2}{3}(4 + V_\pi(\text{Aktiv}))$

$= \frac{4}{3} + \frac{8}{3} + \frac{2}{3} V_\pi(\text{Aktiv})$

$\Rightarrow \frac{1}{3} V_\pi(\text{Aktiv}) = 4$

$\Rightarrow V_\pi(\text{Aktiv}) = 12$

Können wir den Value immer so explizit berechnen?

Im Prinzip Ja:
\[ V_\pi = M \cdot V_\pi \] wobei $M$ eine $|S| \times |S|$ Matrix ist.

Aber: Das Gleichungssystem explizit lösen ist aufwendig
(z.B. mit Gauß Verfahren $O(|S|^3)$).

Policy Evaluation Algorithmus

Idee: Iterative Lösung.

• Starte mit $V_\pi^0(s) \leftarrow 0$ für alle Zustände $s$.
• Für Iteration $t = 1, 2, 3, \ldots$ :
  • Für jeden Zustand $s \in S$:
    • \[ V_\pi^t(s) \leftarrow \underbrace{\sum_{s' \in S} T(s,\pi(s), s') (Reward(s, \pi(s), s') + \gamma V_\pi^{t-1}(s'))}_{Q_\pi^{t-1}(s, \pi(s))} \]

Wie viele Iterationen brauchen wir?

Bis sich unsere $V$ Werte nicht mehr groß ändern:
\[ \max_{s\in S} |V_\pi^t (s) - V_\pi^{t-1}(s)| \leq \epsilon \]

In der Praxis konvergiert der Algorithmus recht schnell.

Speicherbedarf?

Pro Zustand brauchen wir den aktuellen und den letzten $V$ Wert. Also $2 |S|$.

Beispiel: Würfelspiel

Jupyter

Beispiel: Inselüberquerung

Wir starten im Westen einer Insel. Wir können in eine von 4 Richtungen wandern und am Ende entweder in den Vulkan fallen (-50) oder bei einer malerischen Bucht (+20) oder einem kleinen Dorf (+2) enden. Bei jedem Schritt können wir aber Pech haben und in eine falsche Richtung abrutschen.

Jupyter

Nächster Schritt: Wie finden wir eine optimale Policy?

\[ V_\text{opt}(s) = \max_\pi V_\pi(s) \] sei der maximale Value, den eine Policy erreichen kann.

In unseren rekursiven Definitionen ändert sich wenig:

\[ V_\text{opt} = \begin{cases} 0 & if\ IsEnd(s) \\ {\color{green} \max_{a \in \text{Actions}(s)}} Q_{\color{green} opt}(s, {\color{green} a}) & else \end{cases} \]

\[ Q_\text{opt}(s, a) = \sum_{s' \in S} T(s, a, s') (Reward(s, a, s') + \gamma V_{\color{green} opt}(s')) \]

Wenn wir $Q_\text{opt}$ kennen, dann kennen wir auch die optimale Policy:

\[ \pi_\text{opt}(s) = \operatornamewithlimits{arg\,max}_{a \in \text{Actions}(s)} Q_\text{opt}(s, a) \]

Value Iteration Algorithmus (Bellman, 1957)

• Starte mit $V_\text{opt}^0(s) \leftarrow 0$ für alle Zustände $s$.
• Für Iteration $t = 1, 2, 3, \ldots$ :
  • Für jeden Zustand $s \in S$:
    • \[ V_\text{opt}^t(s) \leftarrow \max_{a \in \text{Actions}(s)} \underbrace{\sum_{s' \in S} T(s,a, s') (Reward(s, a, s') + \gamma V_\text{opt}^{t-1}(s'))}_{Q_\text{opt}^{t-1}(s, a)} \]

Wie kommen wir an die Policy?

Nebenprodukt aus dem Algorithmus (das $a$, welches $Q_\text{opt}$ maximiert, berechnen wir ja in jedem Schritt).

Jupyter

          def value_iteration(mdp):
              # initialize
              V = {}
              for state in mdp.states():
                  V[state] = 0.

              pi = {}

              def Q(state, action):
                  return sum( prob * (reward + mdp.discount() * V[new_state]) \
                            for new_state, prob, reward in mdp.succ_prob_and_reward(state, action))

              iteration = 0
              while True:
                  iteration += 1

                  new_V = {}
                  for state in mdp.states():
                      if mdp.is_end(state):
                          # End states are always known
                          new_V[state] = 0.
                          pi[state] = "None"
                      else:
                          new_V[state], pi[state] = max( (Q(state, action), action) for action in mdp.actions(state) )

                  if max(abs(V[state] - new_V[state]) for state in mdp.states()) < 1e-6:
                      break

                  V = new_V

              return V, pi
        

Value iteration konvergiert wenn eines der beiden Kriterien gilt:

• discount $\gamma < 1$
• MDP Graph ist azyklisch

Policy evaluation: $(\text{MDP}, \pi) \to V_\pi$

Value iteration: $\text{MDP} \to (Q_\text{opt}, \pi_\text{opt})$

Wir verwenden das gleiche Grundrezept wir bei der Suche

• Dynamic programming berechnet $FutureCost(s)$
• Policy evaluation berechnet $V_\pi(s)$
• Value iteration berechnet $V_\text{opt}(s)$

Rezept:

• Rekursive Definition aufschreiben: \[V_\pi(s) = \ldots V_\pi(s') \ldots\]
• Iterativen Algorithmus programmieren, der die Gleichheit als Zuweisung umsetzt.

MDP

• Einer Menge an möglichen Zuständen $S$
• Einem initialen Zustand $s_{start}$
• Einer Menge von Zielzuständen $S_{target}$, bzw. Funktion $IsEnd(s)$
• Aktionen die in einem bestimmten Zustand gemacht werden können $\text{Actions}(s)$
• $T(s, a, s') = P(s' | s,a)$: Wahrscheinlichkeit, dass wir von $s$ durch $a$ nach $s'$ kommen (Es muss gelten: $\sum_{s' \in S} T(s, a, s') = 1$)
• $Reward(s, a, s')$: Gewinn, wenn wir aus $s$ durch $a$ nach $s'$ gehen
• Discount Faktor $0 \leq \gamma \leq 1$

Was ist, wenn wir $T$ und $Reward$ nicht kennen?

Mystery Buttons

In jeder Runde können wir A oder B wählen.

Start A B

Zustand:

Rewards:

Reinforcement Learning Algorithmus (Template)

• Zu jedem Zeitpunkt $t = 1, 2, 3, \ldots$
• Wähle eine Aktion $a_t = \pi_\text{act}(s_{t-1})$ (Wie?)
• Erhalte Reward $r_t$ und ermittle neuen Zustand $s_{t}$
• Update eigene Parameter / Modell der Welt (Wie?)

Model-based Monte Carlo

Beispiel Episoden unseres Würfelspiels:

• ${\color{red} A}; w, 4, {\color{red} A}; w, 4, {\color{red} B}$
• ${\color{red} A}; a, 10, {\color{red} B}$
• ${\color{red} A}; w, 4, {\color{red} A}; w, 4, {\color{red} A}; w, 4, {\color{red} B}$
• ${\color{red} A}; w, 4, {\color{red} A}; w, 4, {\color{red} B}$

Was machen wir damit?

Daten in Form von Episoden: ${\color{red} s_0}; a_1, r_1, {\color{red} s_1}; a_2, r_2, {\color{red} s_2}; \ldots a_n, r_n, {\color{red} s_n};$

Idee: Wir schätzen $T(s, a, s')$ und $Reward(s, a, s')$ von unserem MDP.

$\widehat{Reward}(s,a,s') = r$ wie beobachtet

$\hat T(s,a,s') = \frac{\text{Wie oft passiert }(s,a,s')}{\text{Wie oft passiert }(s,a)}$

Model-Based Value Iteration

$\pi(\text{Aktiv}) = \text{Weitermachen}$

Bei den Aktionen, die wir wählen, konvergieren wir zu den echten Wahrscheinlichkeiten
(Gesetz der großen Zahl, Ergodic Theorem)

Mit unserem abgeschätzten $MDP(\hat T, \widehat{Reward})$ können wir den Value Iteration Algorithmus verwenden um eine Policy zu ermitteln.

Problem

Aktionen, die nicht in unserer Policy sind, sehen wir nie.

Wir müssen den Zustandsraum erkunden um alle Parameter zu lernen.

Wir brauchen eine Policy $\pi$, die aktiv erkundet.

\[ \pi(\text{Aktiv}) = \begin{cases} \text{Weitermachen} & \text{In 50\% der Fälle} \\ \text{Aufhören} & \text{else} \end{cases} \]

Model-basiert $\to$ Model-free

\[ \pi_\text{opt}(s) = \operatornamewithlimits{arg\,max}_{a \in \text{Actions}(s)} Q_\text{opt}(s, a) \] \[ \hat Q_\text{opt}(s,a) = \sum_{s' \in S} {\color{red} \hat T(s,a,s')} ({\color{red} \widehat{Reward}(s,a,s')} + \gamma \hat V_\text{opt}(s')) \]

Um eine Policy zu bestimmen brauchen wir nur $Q_\text{opt}(s,a)$.

Idee: Wir versuchen $Q_\text{opt}(s,a)$ direkt abzuschätzen.

Episode: ${\color{red} s_0}; a_1, r_1, {\color{red} s_1}; a_2, r_2, {\color{red} s_2}; \ldots a_n, r_n, {\color{red} s_n}$

Utility $u_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \ldots$

$Q_\pi(s,a)$ ist die erwartete Utility, wenn wir in $s$ sind, jetzt $a$ machen und dann $\pi$ folgen.

$Q_\pi(s_{t-1}, a_t) = \mathbb{E}(u_t)$

\[ \pi(\text{Aktiv}) = \text{Weitermachen} \]

Wichtig: Wir schätzen hier $Q_\pi$, nicht $Q_\text{opt}$

• "On-policy": Der berechnete Wert hängt von der Policy ab
• "Off-policy": Der berechnete Wert kann auch für eine andere Policy verwendet werden.

Model-based Monte Carlo ist off-policy: Wir bekommen mit verschiedenen Policies das gleiche Modell

Wie können wir $\hat Q_\pi$ im Betrieb updaten?

Für jede Beobachtung $(s,a,u)$ machen wir das Update \[ \hat Q_\pi(s,a) \gets (1-\eta) \hat Q_\pi(s,a) + \eta u \] \[ \eta = \frac{1}{1 + \text{\# updates von (s,a)}} \]

Wir haben nun die Freiheit, den Parameter $\eta$ auch anders zu wählen

Zum Beispiel: \[ \eta = \frac{1}{\sqrt{\text{\# updates von (s,a)}}} \] Folge: $\eta$ schrumpft langsamer.

Gut, wenn die Welt nicht statisch ist oder wir unsere Policy ändern.

\[ \hat Q_\pi(s,a) \gets (1-\eta) \hat Q_\pi(s,a) + \eta u \]

Equivalente Formulierung: \[ \hat Q_\pi(s,a) \gets \hat Q_\pi(s,a) - \eta({\color{red} \underbrace{\hat Q_\pi(s,a)}_{\text{prediction}}} - {\color{blue} \underbrace{u}_{\text{target}}}) \]

Entspricht stochastic gradient descent für mit Zielfunktion $(\hat Q_\pi(s,a) - u)^2$

Model-based vs Model-free

• Wenn unser Model (hinreichend) gut ist, dann fahren wir Model-based meistens besser:
  • Dateneffizienter
  • Bessere Performance
  • Bessere Ergebnisse
  • Einfacher zu analysieren
• Je komplexer das Problem, umso schwieriger ist es ein akurater Model zu finden

Jupyter

Wir verwenden die beobachteten Utilities $u$ um $Q_\pi$ abzuschätzen.

Problem: Für lange Episoden kann $u$ sehr daneben liegen.

Lange Episoden → Exponentiell viele Möglichkeiten → hohe Varianz)

Idee: Statt $u_t$ verwenden wir $r_{t} + \gamma \hat Q_\pi(s_{t-1}, a_t)$

Kombination aus Daten $r$ und unserem Wissen $\hat Q_\pi(s_{t-1}, a_t)$.

Verlassen uns darauf, dass unser Estimate schon gut ist. Man spricht hier auch von "Bootstrapping"

Aktuell: $\hat Q_\pi(\text{Aktiv}, \text{weitermachen}) = 11$

Jupyter

Achtung: Beim Implementieren müssen wir auch an edge cases denken!

Letzten Reward nehmen wir nur mit, wenn wir für die letzten zwei Datenpunkte $(s_{t-1}, a_t, r_t)$ der Episode das Update machen: \[ \hat Q_\pi(s_{t-1},a_t) \gets (1-\eta) \hat Q_\pi(s_{t-1},a_t) + \eta r_t \]

Hohe Varianz, kein Bias vs kleine Varianz, Bias

Frage: Welche der folgenden Algorithmen erlauben uns $Q_\text{opt}(s,a)$ abzuschätzen?

• Model-based Monte Carlo
• Model-free Monte Carlo
• SARSA

Problem: Model-free MC und SARSA schätzen $Q_\pi$ ab, aber nur mit $Q_\text{opt}$ können wir eine optimale Policy definieren.

Zur Erinnerung: \[ Q_\text{opt}(s, a) = \sum_{s' \in S} T(s, a, s') (Reward(s, a, s') + \gamma V_\text{opt}(s')) \]

Jupyter

Reinforcement Learning Algorithmus (Template)

• Zu jedem Zeitpunkt $t = 1, 2, 3, \ldots$
• Wähle eine Aktion $a_t = \pi_\text{act}(s_{t-1})$ (Wie?)
• Erhalte Reward $r_t$ und ermittle neuen Zustand $s_{t}$
• Update eigene Parameter / Modell der Welt (!)

Wie wählen wir unsere Policy $\pi_\text{act}$?

Exploration vs Exploitation

Extrem 1: No exploration, all exploitation

\[ \pi_\text{act}(s) = \operatornamewithlimits{arg\,max}_{a \in \text{Actions}(s)} \hat Q_\text{opt}(s,a) \]

Jupyter

Extrem 2: All exploration, no exploitation

\[ \pi_\text{act}(s) = \text{Zufälliges } a \in \text{Actions}(s) \]

Jupyter

Wir brauchen einen Mittelweg zwischen Exploration und Exploitation

Jupyter

Problem: Wenn die Menge aller Zustände $S$ sehr groß ist, haben wir keine Chance alle zu erkunden.

Update Funktion beim Q-Learning: \[ \hat Q_\text{opt}(s_{t-1},a_t) \gets (1-\eta) {\color{red} \underbrace{\hat Q_\text{opt}(s_{t-1},a_t)}_{\text{prediction}}} + \eta {\color{blue} \underbrace{(r_t + \gamma \hat V_\text{opt}(s_{t}))}_{\text{target}}} \]

Jedes $\hat Q_\text{opt}(s_{t-1},a_t)$ hat einen eigenen Wert.
Wir lernen diese auswendig und können nicht auf unbekannte $(s,a)$ generalisieren.

Function approximation

Wir definieren uns Features $\phi(s,a)$ und lernen dann Gewichte $w$ mit: \[ \hat Q_\text{opt}(s,a; w) = w \cdot \phi(s,a) \]

$\Rightarrow$ Lineare Regression

Ich muss $(s,a)$ nicht gesehen haben um $w \cdot \phi(s,a)$ zu berechnen.

Entspricht linearer Regression mit Zielfunktion: \[ ({\color{red} \underbrace{\hat Q_\text{opt}(s_{t-1}, a_t; w)}_{\text{prediction}}} - {\color{blue}\underbrace{(r_t + \gamma \hat V_\text{opt}(s_{t}))}_\text{target}})^2 \]

Wie könnten Features aussehen?

PS: Das reicht noch nicht für die Vulkan Insel

Modeling: MDP

Inference: Policy evaluation, Value iteration

Learning: Reinforcement Learning

Klassifikation (e.g. Log. Regression, Neural Nets): Kein Zustand, supervised

Reinforcement learning (e.g. Q-Learning): Zustand, partial supervised

Partial supervised: Wir bekommen gelegentlich Rewards, aber nicht die ideale Lösung.

Ausblick: Deep Reinforcement Learning

Idee: Verwende Neuronale Netzwerke für $\hat Q_\text{opt}$ und $\pi$.

Google DeepMind, 2013: Atari Spiele basierend auf rohen Pixeln

https://www.deepmind.com/blog/deep-reinforcement-learning

https://openai.com/blog/solving-rubiks-cube/