Fachkonzept: Verzögerte Belohnung

Das Problem verzögerter Belohnungen

Im letzten Abschnitt hat man gesehen, dass selbst in dem Fall, dass eine erfolgreiche Abfolge von Aktionen mehrfach durchlaufen wurde, dies nicht dazu führt, dass diese Abfolge auch als optimal erkannt und gelernt wird, wenn die Q-Werte gleich den unmittelbaren Belohnungen gesetzt werden. Der Grund hierfür ist leicht zu verstehen: Spielt nur die unmittelbare Belohnung eine Rolle, dann wird vollständig die Folgesituation ignoriert. Ob die Folgesitutation also für die Zukunft aussichtsreich ist oder vollkommen hoffnungslos ist dem Verfahren dann vollkommen egal.

Beispiel im Spiel

Zu einer erfolgreichen Abfolge von Aktionen gehört bei unserem Spiel insbesondere, dass man irgendwann das "Buch nehmen" muss. Diese Aktion jedoch kostet, so wie das Spiel konstruiert ist, 90 Punkte, wird also im Grunde genommen bestraft. Die Aktion "Weglaufen" hingegen kostet nur 40 Punkte, hat also unmittelbar einen besseren Effekt. Das einzige Problem ist nur, dass das Weglaufen in eine Situation führt, in der es nichts mehr weiteres zu gewinnen gibt, während die "Investition" in ein Buch zu den gewinnbringenden Folgesituationen führt.

Beispiel im "richtigen Leben"

Ähnliche Situationen gibt es auch im "richtigen Leben". Vor einer Klassenarbeit steht man als Schüler z.B. vor der Wahl, ob man lieber für die Arbeit lernen oder sich einen vergnügten Abend mit Freunden im Kino machen soll. Unnötig zu sagen, welche der Aktionen "Lernen" und "Kino" die größere unmittelbare Belohnung bringt (naja: es kommt auf den Film und die Freunde an). Trotzdem entscheiden sich in einer solchen Situation viele Schüler für's Lernen. Warum? Weil die beiden Aktionen zu unterschiedlichen Folgesituationen führen, nämlich "Ich kann die Aufgaben lösen" bzw. "Ich kann nix". Je nach Situation sind die zu erwartenden zukünftigen Belohnungen sehr unterschiedlich. Durch Lebenserfahrung hat man gelernt, dass man manchmal einen Verzicht auf unmittelbare Belohnung "investieren" muss, um in der Zunkunft dann umso mehr Belohnung herauszuschlagen. Dabei handeln verschiedene Personen oft unterschiedlich: Manche Personen entscheiden tatsächlich eher "kurzsichtig" und sind übermäßig auf die unmittelbare Belohnung fixiert. Andere handeln vorausschauender und versuchen, eine Abschätzung der künftigen Konsequenzen in ihre Entscheidungen stärker mit einzubeziehen.

Berücksichtigung zukünftiger Belohnungen

Wie kann man unsere Lernregel so erweitern, dass auch die zukünftig zu erwartenden Belohnungen mit einbezogen werden? Was wir in der Funktion übergeben bekommen, ist nur die nächste Situation. Doch welche zu erwartende Belohnung gehört zu dieser Situation?

Hier helfen die Q-Werte zu dieser nächsten Situation und den verschiedenen Aktionen. Denn die Q-Werte beschreiben ja genau, wie gut eine bestimmte Aktion bei einer bestimmten Situation ist. Doch welche dieser Q-Werte soll man bei der Berechnung berücksichtigen?

Eine auf den ersten Blick plausible Möglichkeit wäre es z.B., einen Mittelwert über die Q-Werte zu allen möglichen Aktionen in dieser Situation zu bilden. Besonders schlau ist das bei näherem Hinsehen allerdings nicht. Denn es könnte ja sein, dass genau eine der Aktionen eine wirklich gute Belohnung verspricht, während alle anderen furchtbar schlechte Belohnungen (bzw. Bestrafungen) nach sich ziehen. Dann würde diese Situation einen sehr schlechten Mittelwert erzielen, obwohl durch cleveres Handeln in Wirklichkeit eine sehr gute Belohnung zu erzielen wäre.

Deshalb ist es sinnvoll, nicht den Mittelwert über alle möglichen Aktionen zu bilden, sondern tatsächlich nur den Q-Wert der besten der möglichen Aktion zu berücksichtigen. Dieser sollte mit dem Belohnungswert verrechnet werden. Für die beste Aktion in einer Situation haben wir ja bereits die Funktion beste_aktion implementiert. Diese kann man nutzen. Nun ist ein solcher Q-Wert im Grunde nur eine Schätzung für Dinge, die in der Zukunft passieren, während die unmittelbare Belohung $r$ deutlich handfester ist. Deshalb führt man einen Faktor $\gamma \lt 1$ ein (griech.: gamma), der beschreibt, wie viel man auf die Schätzung für die Zukunft vertraut. Mit diesem wird der Q-Wert für die beste Aktion in der Folgesituation multipliziert und zur Belohnung addiert. Das kann man so direkt im Programm implementieren, man kann aber auch noch einen Blick auf eine etwas mathematischere Darstellung werfen.

Mathematische Formulierung

Sei $s$ eine Situation und $a$ die Aktion, die vom Agenten gewählt wurde (gierig oder $\varepsilon$-gierig). Sei weiterhin $r$ die aus der Aktion resultierende Belohnung und $s'$ die Folgesituation, in der sich der Agent nach Ausführen der Aktion $a$ befindet. Sei $\gamma$ der Wert für das Vertrauen in die Vorhersage der Zukunft. Dann wird der Q-Wert $Q(s,a)$ wie folgt gesetzt: \begin{equation} Q(s,a) \leftarrow r + \gamma \cdot \max_{a'} Q(s',a') \end{equation} Das gilt natürlich nur, wenn es in der Folgesituation $s'$ überhaupt noch Aktionen gibt, die der Agent ausführen kann. Ist dies nicht der Fall, so gilt wieder der einfache Fall: \begin{equation} Q(s,a) \leftarrow r \end{equation}