optimale Taktik | Erwartungswert von Summen

11.04.2008, 10:27

aRo

optimale Taktik | Erwartungswert von Summen

Hallo!

Ich hoffe ihr könnt mir bei diesem Thema helfen - denn es geht eigentlich um künstliche Intelligenz. Das Problem ist es, eine optimale Taktik $\begin{eqnarray*} \pi^* \end{eqnarray*}$ zu finden.

Also, die Situation: Wir haben einen Agenten in einer vollständig beobachtbaren Umgebung. Der Agent möchte zu einem Terminalzustand, führt er jedoch die entsprechende Aktion aus, kann es mit einer bestimmten Wahrscheinlichkeit passieren, dass er stattdessen rechtwinklig zur gewünschten Richtung läuft. Man kann also nicht einfach die kürzeste Zustandsfolge angeben, sondern muss dem Agenten eine Taktik geben, die ihm sagt, was er in jeder Situation machen soll.

Um das ganze interessant zu machen, macht der Agent einen "Gewinn" (üblichweise <0) auf jedem Zustand, den er erreicht, so dass er möglichst schnell zum Terminalzustand will.

Nun könnte man den Gewinn einer Zustandsfolge so beschreiben:
$\begin{eqnarray*} U_h([s_0,s_1,s_2,...]) =R(s_0)+\gamma R(s_1)+\gamma^2R(s_2)+... \end{eqnarray*}$
wobei Uh die Zustandsfolge, s0 ein Zustand und y eine Zahl zwischen 0 und 1 ist, mit der sich beispielsweise die Gegenwart "betonen lässt".

Eine optimale Taktik wäre dann eine Takitk, die die bestmögliche erwartete Summe der Gewinne liefert. Dabei ist zu beachten, dass eine Taktik ja aufgrund der unabsichtlich auftretenden Aktionen viele Zustandsfolgen erzeugen kann.

Als Formel wird angegeben:
$\begin{eqnarray*} \pi^* = \text{argmax} E [\sum_{t=0}^\infty {\gamma^t \cdot R(s_t|\pi] } \end{eqnarray*}$ , wobei unter dem argmax noch ein pi steht.

Ich hoffe mit diesem Hintergrundwissen könnt ihr mir diese Formel etwas erläutern. Ich nehme an, dass pi unter argmax soll heißen, dass wir das Maximum aller pi suchen. Das pi bei dem R soll wahrscheinlich andeuten, dass der Zustand s_t unter der Taktik pi erzeugt wurde. Was ist E? Die Wahrscheinlichkeit?
Irgendwie muss ich doch für die Bewertung einer Taktik die erwartete Gewinnsumme ausrechnen, also muss ich Wahrscheinlichkeiten berücksichtigen, mit der eine bestimmte Summenfolge auftritt.
Mein Problem ist hier glaube ich einfach, dass ich diese Formel nicht richtig zu lesen verstehe.

Hoffe jemand hat Ahnung oder denkt sich in die Materie ein wenig ein!

Danke!!

11.04.2008, 18:15

Mazze

Auf diesen Beitrag antworten »

Zitat:

Um das ganze interessant zu machen, macht der Agent einen "Gewinn" (üblichweise <0) auf jedem Zustand, den er erreicht, so dass er möglichst schnell zum Terminalzustand will.

Hier sollte näher spezifiziert werden. State-win, state-action win oder action win?

Hierbei handelt es sich, neben der Bellman-Gleichung, um die globale Formel im Reinforcement Learning. Die Policy $\begin{eqnarray*} \pi_* \end{eqnarray*}$ maximiert den zu erwarteten Gewinn. Entsprechend ist das E in Deiner Formel der Erwartungswert. Deine Wahrscheinlichkeiten gehen also ein wenn Du den Erwartungswert aufschreibst.
Richtig erkannt wird über alle möglichen Policys $\begin{eqnarray*} \pi \end{eqnarray*}$ maximiert.

Zitat:

Irgendwie muss ich doch für die Bewertung einer Taktik die erwartete Gewinnsumme ausrechnen, also muss ich Wahrscheinlichkeiten berücksichtigen, mit der eine bestimmte Summenfolge auftritt.

Ich würde an Deiner Stelle nicht die Policy optimieren, sondern den zugehörigen Value. (Value-Iteration). Die Bellman-gleichung ist

$\begin{eqnarray*} V^\pi(s) = E_\pi(R_t|s_t = s) = \sum_{a}\pi(s,a)\sum_{s'}P_{ss'}^a[R_{ss'}^{a} + \gamma V_\pi(s')] \end{eqnarray*}$

Das ist ein nichtlineares Gleichungssystem. Unter der annahme das die Rewards konstant sind wird es zu einem linearen System, aber normalerweise muss man zur Lösung iterative Verfahren nehmen. Wenn wir den Value berechnet haben ist die optimale Policy

$\begin{eqnarray*} \pi_*(s) = \text{argmax}_a\sum_{s'}P_{ss'}^a*[R_{ss'} + V^*(s')] \end{eqnarray*}$

So bekommst Du also deine Taktik. Wie man die Value-Function optimiert und alles andere zum Reinforcement-Learning findet man hier. Das komplette Buch "Reinforcement Learning" von Sutton ist dort im HTML format zu haben (PDF nur ausgewählte Kapitel).

Neue Frage »

Antworten »

optimale Taktik | Erwartungswert von Summen

Verwandte Themen