Reinforcement Learning

Reinforcement Learning

Bestärkendes Lernen bzw. Verstärkendes Lernen (engl. Reinforcement Learning) ist eine Variante des Maschinellen Lernens, bei dem ein Agent (ein Computerprogramm) lediglich durch ein System von Belohnung und Bestrafung lernt, seinen Nutzen zu optimieren.

Inhaltsverzeichnis

Einführung

Betrachtet wird ein dynamisches System - bestehend aus einem Agenten und seiner Umgebung (der Welt) - in diskreten Zeitschritten t=0,1,2,...\,\!. Zu jedem Zeitpunkt t\,\! befindet sich die Welt in einem Zustand z_t\in Z und der Agent wählt eine Aktion a_t \in A(z_t) aus. Daraufhin geht die Welt in den Zustand z_{t+1}\in Z und der Agent erhält eine Belohnung b_t\in B.

Erwarteter Gewinn

Ziel ist es den erwarteten Gewinn (engl. expected return)

B_t = \sum_{k=0}^N \delta^k\cdot b_{t+k+1} mit  0\le\delta\le 1

zu maximieren. Der erwartete Gewinn ist also so etwas wie die erwartete Gesamtbelohnung. Dabei nennt man \delta\,\! den Diskontierungsfaktor (engl. discount factor). Bei episodischen Problemen, d. h. die Welt geht nach einer endlichen Anzahl von Schritten in einen Endzustand über (wie z. B. eine Schachpartie), eignet sich der Diskontierungsfaktor \delta=1\,\!. In diesem Fall wird jede Belohnung b_{t+k+1}\,\! gleich gewertet. Bei kontinuierlichen Problemen (N=\infty) muss man ein \delta<1\,\! wählen, damit die unendliche Reihe B_t\,\! konvergiert. Für \delta=0\,\! zählt nur die aktuelle Belohnung b_t\,\!; alle zukünftigen Belohnungen werden ignoriert. Geht \delta\,\! gegen 1, wird der Agent weitsichtiger.

Strategien

Beim Bestärkenden Lernen verfolgt der Agent eine Strategie (engl. policy). Üblicherweise wird die Strategie als eine Funktion s:Z \rightarrow A(Z) betrachtet, die jedem Zustand eine Aktion zuweist. Jedoch sind auch nichtdeterministische Strategien (oder gemischte Strategien) möglich, sodass eine Aktion mit einer bestimmten Wahrscheinlichkeit ausgewählt wird. Im Allgemeinen wird eine Strategie demnach als bedingte Wahrscheinlichkeitsverteilung definiert: s(z,a) = p(a|s) \quad.

Markow-Entscheidungsprozess

Bestärkendes Lernen wird häufig als Markow-Entscheidungsprozess (engl. Markov Decision Process) aufgefasst. Charakteristisch ist die Annahme, dass die Markow-Eigenschaft erfüllt ist:

p(z_{t+1},r_{t+1}|z_{0:t},a_{0:t},b_{0:t})=p(z_{t+1},r_{t+1}|z_{t},a_{t})\,\!.

Zentrale Begriffe eines Markow-Entscheidungsprozess sind das Aktionsmodell (oder Transitionswahrscheinlichkeit) und die erwartete Belohnung im nächsten Zeitschritt (engl. expected reward). Das Aktionsmodell p(z_{t+1}|z_{t},a_{t})\,\! ist die bedingte Wahrscheinlichkeitsverteilung, dass die Welt von Zustand z_{t}\,\! in Zustand z_{t+1}\,\! übergeht, falls der Agent die Aktion a_t\,\! ausgewählt hat. Im deterministischen Fall ist das Aktionsmodell einfach eine Funktion, die einem Zustands-Aktions-Paar einen neuen Zustand zuordnet. Die Erwartete Belohnung ist folgendermaßen definiert

b(z_t,z_{t+1},a_t):=E\{b_{t+1}|z_t,z_{t+1},a_t\}\,\!.

Approximation

Bei unendlichen Zustandsräumen muss diese Nutzenfunktion approximiert werden, z. B. mit Neuronalen Netzen oder Gaußschen Prozessen.

Simultanes Lernen mehrerer Agenten

Soll mehr als ein Agent lernen, kann selbst bei kooperativen Agenten, außer in trivialen Fällen, die Konvergenz der Lernvorgänge (bislang) nicht mehr garantiert werden. Trotzdem kann unter Zuhilfenahme von Heuristiken oft ein in der Praxis nützliches Verhalten gelernt werden, da der worst case selten auftritt.[1]

Literatur

  • Richard Sutton, Andrew Barto: Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998 (Online-Version)
  • Stuart Russell, Peter Norvig: Künstliche Intelligenz: Ein moderner Ansatz. Pearson Studium, August 2004, ISBN 3827370892 (deutsche Übersetzung der 2. Auflage) Kapitel 21.
  1. J. F. Knabe: Kooperatives Reinforcement Lernen in Multiagentensystemen. B. Sc. Thesis, Universität Osnabrück, 2005. http://www.panmental.de/papers/CooperativeRLinMAS.pdf

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Reinforcement learning — Inspired by related psychological theory, in computer science, reinforcement learning is a sub area of machine learning concerned with how an agent ought to take actions in an environment so as to maximize some notion of long term reward .… …   Wikipedia

  • Reinforcement — Reinforce redirects here. For the Magical Girl Lyrical Nanoha character, see Reinforce (Nanoha). This article is about the term used in operant conditioning. For the construction materials reinforcement, see Rebar. For reinforcement learning in… …   Wikipedia

  • Learning classifier system — A learning classifier system, or LCS, is a machine learning system with close links to reinforcement learning and genetic algorithms. First described by John Holland, his LCS consisted of a population of binary rules on which a genetic algorithm… …   Wikipedia

  • learning — /lerr ning/, n. 1. knowledge acquired by systematic study in any field of scholarly application. 2. the act or process of acquiring knowledge or skill. 3. Psychol. the modification of behavior through practice, training, or experience. [bef. 900; …   Universalium

  • Learning Automata — A branch of the theory of Adaptive control is devoted to learning automata surveyed by Narendra and Thathachar which were originally described explicitly as finite state automata. ReferencesPhilip Aranzulla and John Mellor.Narendra K., Thathachar …   Wikipedia

  • learning theory — ▪ psychology Introduction       any of the proposals put forth to explain changes in behaviour produced by practice, as opposed to other factors, e.g., physiological development.       A common goal in defining any psychological (psychology)… …   Universalium

  • Learning theory (education) — In psychology and education, a common definition of learning is a process that brings together cognitive, emotional, and enviromental influences and experiences for acquiring, enhancing, or making changes in one s knowledge, skills, values, and… …   Wikipedia

  • Learning — Learn and Learned redirect here. For other uses, see Learn (disambiguation) and Learned (disambiguation). Neuropsychology Topics …   Wikipedia

  • reinforcement — /riɪnˈfɔsmənt / (say reein fawsmuhnt) noun 1. the act of reinforcing. 2. the state of being reinforced. 3. something that reinforces or strengthens. 4. (often plural) an additional supply of troops, ships, etc., for a military or naval force. 5.… …  

  • Temporal difference learning — is a prediction method. It has been mostly used for solving the reinforcement learning problem. TD learning is a combination of Monte Carlo ideas and dynamic programming (DP) ideas. [2] TD resembles a Monte Carlo method because it learns by… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”