Verständnis der Rolle des Abzinsungsfaktors beim Lernen zur Stärkung

43

Ich unterrichte mich selbst über das Lernen der Bestärkung und versuche, das Konzept der ermäßigten Belohnung zu verstehen. Die Belohnung ist also notwendig, um dem System mitzuteilen, welche State-Action-Paare gut und welche schlecht sind. Aber was ich nicht verstehe, ist, warum die vergünstigte Belohnung notwendig ist. Warum sollte es wichtig sein, ob ein guter Zustand eher bald als später erreicht wird?

Ich verstehe, dass dies in bestimmten Fällen relevant ist. Wenn Sie zum Beispiel verstärktes Lernen verwenden, um an der Börse zu handeln, ist es vorteilhafter, Gewinne eher früher als später zu erzielen. Das liegt daran, dass Sie mit diesem Geld jetzt Dinge tun können, die wünschenswerter sind, als später Dinge mit diesem Geld zu tun.

In den meisten Fällen verstehe ich jedoch nicht, warum die Diskontierung sinnvoll ist. Angenommen, Sie möchten, dass ein Roboter lernt, wie man durch einen Raum navigiert, um zur anderen Seite zu gelangen, wo es Strafen gibt, wenn er mit einem Hindernis kollidiert. Wenn es keinen Abzinsungsfaktor gäbe, würde es lernen, die andere Seite perfekt zu erreichen, ohne auf irgendwelche Hindernisse zu stoßen. Es kann eine lange Zeit dauern, bis es dort ankommt, aber irgendwann wird es dort ankommen.

Wenn wir der Belohnung jedoch einen Rabatt gewähren, wird der Roboter aufgefordert, die andere Seite des Raums schnell zu erreichen, selbst wenn er auf dem Weg mit Gegenständen kollidieren muss. Dies ist eindeutig kein wünschenswertes Ergebnis. Sicher, Sie möchten, dass der Roboter schnell auf die andere Seite kommt, aber nicht, wenn dies bedeutet, dass er auf dem Weg mit Gegenständen kollidieren muss.

Meine Intuition ist also, dass jede Form von Abzinsungsfaktor tatsächlich zu einer suboptimalen Lösung führt. Und die Wahl des Abzinsungsfaktors scheint oft willkürlich zu sein - viele Methoden, die ich gesehen habe, haben ihn einfach auf 0,9 gesetzt. Dies scheint mir sehr naiv zu sein und einen willkürlichen Kompromiss zwischen der optimalen Lösung und der schnellsten Lösung zu geben, während dieser Kompromiss in Wirklichkeit sehr wichtig ist.

Kann mir bitte jemand helfen, das alles zu verstehen? Dankeschön :)

Karnivaurus
quelle

Antworten:

36

TL; DR.

Die Tatsache, dass der Abzinsungssatz zwangsläufig kleiner als 1 ist, ist ein mathematischer Trick, um eine unendliche Summe endlich zu machen. Dies hilft, die Konvergenz bestimmter Algorithmen zu beweisen.

In der Praxis könnte der Abzinsungsfaktor verwendet werden, um die Tatsache zu modellieren, dass der Entscheidungsträger sich nicht sicher ist, ob im nächsten Entscheidungszeitpunkt die Welt (z. B. Umgebung / Spiel / Prozess ) enden wird.

Zum Beispiel:

Wenn der Entscheider ein Roboter ist, kann der Abzinsungsfaktor die Wahrscheinlichkeit sein, dass der Roboter zum nächsten Zeitpunkt ausgeschaltet wird (die Welt endet in der vorherigen Terminologie). Aus diesem Grund ist der Roboter kurzsichtig und optimiert nicht die Summenbelohnung, sondern die reduzierte Summenbelohnung.

Rabattfaktor kleiner als 1 (im Detail)

Um genauer zu antworten, warum der Diskontsatz kleiner als eins sein muss, werde ich zuerst die Markov-Entscheidungsprozesse (MDPs) einführen.

Verstärkungslerntechniken können verwendet werden, um MDPs zu lösen. Ein MDP bietet einen mathematischen Rahmen für die Modellierung von Entscheidungssituationen, in denen die Ergebnisse teilweise zufällig sind und teilweise von den Entscheidungsträgern kontrolliert werden. Ein MDP wird über einen Zustandsraum , einen Aktionsraum , eine Funktion der Übergangswahrscheinlichkeiten zwischen Zuständen (abhängig von der Aktion des Entscheidungsträgers) und eine Belohnungsfunktion definiert.SA

In seiner Grundeinstellung ergreift und handelt der Entscheidungsträger und erhält eine Belohnung von der Umgebung, und die Umgebung ändert ihren Zustand. Dann spürt der Entscheider den Zustand der Umgebung, ergreift Maßnahmen, erhält eine Belohnung und so weiter. Die Zustandsübergänge sind probabilistisch und hängen ausschließlich vom tatsächlichen Zustand und den Maßnahmen des Entscheidungsträgers ab. Die Belohnung, die der Entscheidungsträger erhält, hängt von den ergriffenen Maßnahmen sowie vom ursprünglichen und vom neuen Zustand der Umwelt ab.

Eine Belohnung wird erhalten, wenn die Aktion im Zustand und die Umgebung / das System wechselt in den Zustand nachdem der Entscheidungsträger die Aktion . Der Entscheider folgt einer Richtlinie: , die für jeden Status eine Aktion . Damit die Richtlinie dem Entscheidungsträger mitteilt, welche Maßnahmen in den einzelnen Bundesstaaten zu ergreifen sind. Die Policy kann auch zufällig gewählt werden, spielt aber im Moment keine Rolle.Rai(sj,sk)aisjskaiπ π():SAsjSaiAπ

Ziel ist es, eine Politik zu finden , so dassπ

maxπ:S(n)ailimTE{n=1TβnRxi(S(n),S(n+1))}(1),
ββ<1 wobei der Abzinsungsfaktor ist und .ββ<1

Beachten Sie, dass das oben genannte Optimierungsproblem einen unendlichen Zeithorizont hat ( ) und das Ziel darin besteht, die Summe der Belohnungen zu maximieren (die Belohnung wird mit multipliziert ). Dies wird in der Regel als MDP-Problem mit einem unendlichen Preisnachlasshorizont bezeichnet .TdiscountedRβn

Das Problem heißt diskontiert, weil . Wenn es kein reduziertes Problem wäre die Summe nicht konvergieren. Alle Policen, die zu jedem Zeitpunkt im Durchschnitt eine positive Belohnung erhalten, summieren sich zu unendlich. Dies wäre ein Belohnungskriterium für eine unendliche Horizontsumme und kein gutes Optimierungskriterium.β<1β=1

Hier ist ein Spielzeugbeispiel, um dir zu zeigen, was ich meine:

Angenommen, es gibt nur zwei mögliche Aktionen: und die Belohnungsfunktion ist gleich wenn , und wenn (Belohnung hängt nicht vom Status ab).a=0,1R1a=10a=0

Es ist klar, dass die Politik, die mehr Belohnung erhält, darin besteht, immer die Aktion und niemals die Aktion . Ich werde diese Richtlinie . Ich werde mit einer anderen Richtlinie , die Aktion mit geringer Wahrscheinlichkeit , andernfalls Aktion .a=1a=0πππa=1α<<1a=0

Im unendlichen Horizont wird die Gleichung (1) zu (die Summe einer geometrischen Reihe) für Richtlinie während für Richtlinie Gleichung (1) zu . Da , ist eine bessere Richtlinie als . Tatsächlich ist die optimale Richtlinie.11βππα1β11β>α1βπππ

Im unendlichen Horizont konvergiert die Summenbelohnungskriterium ( ) Gleichung (1) für keine der Richtlinien (sie summiert sich zu Unendlich). Während also Policy höhere Belohnungen erzielt als beide Policies nach diesen Kriterien gleich. Dies ist einer der Gründe, warum die Kriterien für die Belohnung einer unendlichen Horizontsumme nicht nützlich sind.β=1ππ

Wie ich bereits erwähnt habe, führt dass die Summe in Gleichung (1) konvergiert.β<1

Andere Optimalitätskriterien

Es gibt andere Optimalitätskriterien, die nicht festlegen, dass :β<1

Das endliche Horizontkriterium für den Fall, dass das Ziel darin besteht, die abgezinste Belohnung zu maximieren, bis der ZeithorizontT

maxπ:S(n)aiE{n=1TβnRxi(S(n),S(n+1))},

für und endlich.β1T

In den Durchschnittsbelohnungskriterien für den unendlichen Horizont lautet das Ziel

maxπ:S(n)ailimTE{n=1T1TRxi(S(n),S(n+1))},

Endnote

Abhängig von den Optimalitätskriterien würde man einen anderen Algorithmus verwenden, um die optimale Richtlinie zu finden. Zum Beispiel würde die optimale Politik der Probleme mit dem endlichen Horizont sowohl vom Zustand als auch vom tatsächlichen Zeitpunkt abhängen. Die meisten Reinforcement-Learning-Algorithmen (wie SARSA oder Q-Learning) konvergieren nur für die unendlichen Horizontkriterien mit reduzierter Belohnung zur optimalen Richtlinie (dasselbe gilt für die dynamischen Programmieralgorithmen). Für die durchschnittlichen Belohnungskriterien gibt es keinen Algorithmus, von dem gezeigt wurde, dass er zur optimalen Richtlinie konvergiert. Man kann jedoch R-Learning verwenden, das eine gute Leistung aufweist, wenn auch keine gute theoretische Konvergenz.

PolBM
quelle
1
Hast du eine Idee, was ich lesen soll, um alle Chinesen in deiner Antwort zu verstehen?
Thibaut Noah
@thibautnoah Dies ist meiner Meinung nach die beste Referenz für Reinforcement Learning: Eine Einführung von Sutton und Barto. [ people.inf.elte.hu/lorincz/Files/RL_2006/SuttonBook.pdf]
PolBM
Vielen Dank, Kumpel, wird wahrscheinlich ein weiteres Buch über Mathematik brauchen, aber ich denke, es ist ein Anfang;)
Thibaut Noah
6

Sie haben Recht, dass der Abzinsungsfaktor (sogenanntes - beachten Sie, dass sich dieser von von TD- ) wie eine "Dringlichkeit des Lebens" wirkt und daher Teil des Problems ist - genau wie in Menschenleben: Manche Menschen leben so, als würden sie für immer leben. Manche Menschen leben so, als würden sie morgen sterben.λ λγλλ

Neil G
quelle
1

TL; DR: Abzinsungsfaktoren sind mit Zeithorizonten verbunden. Längere Zeithorizonte haben viel mehr haben Varianz , da sie mehr irrelevante Informationen enthalten, während kurze Zeithorizonte sind voreingenommen gegenüber nur kurzfristige Gewinne.

Der Abzinsungsfaktor bestimmt im Wesentlichen, inwieweit sich die Lernenden für die Belohnungen in der fernen Zukunft im Vergleich zu denen in der unmittelbaren Zukunft interessieren. Wenn , ist der Agent vollständig kurzsichtig und erfährt nur von Aktionen, die eine sofortige Belohnung ergeben. Wenn , bewertet der Agent jede seiner Aktionen basierend auf der Gesamtsumme aller seiner zukünftigen Belohnungen.γ=0γ=1

Warum wollen Sie also nicht immer so hoch wie möglich machen? Nun, die meisten Aktionen haben keine dauerhaften Auswirkungen. Angenommen, Sie möchten sich am ersten Tag eines jeden Monats einen Smoothie gönnen und müssen sich entscheiden, ob Sie einen Blaubeer-Smoothie oder einen Erdbeer-Smoothie erhalten. Als guter Bestärker beurteilen Sie die Qualität Ihrer Entscheidung danach, wie hoch Ihre späteren Belohnungen sind. Wenn Ihr Zeithorizont sehr kurz ist, werden Sie nur die unmittelbaren Belohnungen berücksichtigen, z. B. wie lecker Ihr Smoothie ist. Bei einem längeren Zeithorizont, wie z. B. einigen Stunden, können Sie auch Dinge berücksichtigen, die auf eine Magenverstimmung hindeuten. Aber wenn Ihr Zeithorizont den ganzen Monat dauert, dann jede einzelne Sache, bei der Sie sich den ganzen Monat über gut oder schlecht fühlenγBerücksichtigen Sie, ob Sie die richtige Smoothie-Entscheidung getroffen haben oder nicht. Sie werden eine Menge irrelevanter Informationen berücksichtigen, und daher wird Ihr Urteil sehr unterschiedlich ausfallen und es wird schwer zu lernen sein.

Das Auswählen eines bestimmten Werts von entspricht dem Auswählen eines Zeithorizonts. Es hilft, die reduzierte Belohnung eines Agenten umzuschreiben als wo ich mich identifiziere und . Der Wert explizit den Zeithorizont an, der einem Abzinsungsfaktor zugeordnet ist. entspricht und Belohnungen, die viel mehr alsγG

Gt=Rt+γRt+1+γ2Rt+2+=k=0γkRt+k=Δt=0eΔt/τRt+Δt
γ=e1/τkΔtτγ=1τ=τZeitschritte in der Zukunft werden exponentiell unterdrückt. Im Allgemeinen sollten Sie einen Rabattfaktor so auswählen, dass der Zeithorizont alle relevanten Belohnungen für eine bestimmte Aktion enthält, jedoch nicht mehr.

Clwainwright
quelle