Notebook

MDPs und Reinforcement Learning¶

Gegeben sei die folgende Umgebung mit 4 Räumen, die durch Türen verbunden sind. Die Räume sind von 0 bis 3 nummeriert und 4 bedeutet draußen. Ein Roboter soll, nachdem er in einigem beliebigen Raum positioniert wurde, durch Q-learning den Weg nach draußen finden, d.h., 4 (draußen) ist der Zielzustand. Alle Türen die nach draußen führen haben ein Reward von 100 und alle anderen 0.

Modellieren Sie die Räume als einen Graph, in dem die Räume als Zustände (Knoten) und die Türverbindungen als Transitionen gegeben sind. Notieren Sie die Rewards für jede Transition.
Geben Sie die Reward-Matrix R, die die Rewards zwischen den Zustände beschreibt. Unmögliche Transitionen bekommen ein Reward von -1.
Geben Sie die initiale Q-Matrix an! Nehmen Sie dabei an, dass der Roboter die Anzahl der Räume kennt.
Berechnen Sie die Rewards für eine “Episode”, die im Raum 1 anfängt. Benutzen Sie den discount factor $\gamma = 0.5$. Benutzen Sie dafür die folgende Formel (diese resultiert aus der Standardregel für die Lernrate $\alpha = 1$): $Q(state, action) = R(state, action) + \gamma ∗ max[Q(next state, all actions)]$. Dabei sollen die Aktionen so gewählt werden, das der Roboter die Räume in der folgenden Reihenfolge besucht: 1 → 3 → 1 → 2 → 4. Geben Sie die resultierende Q-Matrix an!

Q-Learning¶

Betrachten Sie das folgende Reinforcement-Learning-Problem:

Es gibt 6 Zustände $s_0,\dots,s_5$ und 4 Aktionen UpC, Up, Left, Right. Die Aktionen funktionieren wie folgt:

UpC: Der Agent geht hoch, außer in $s_4$ und $s_5$ , wo nichts passiert. Reward: -1
Right: Der Agent bewegt sich nach rechts, in $s_0$,$s_2$, $s_4$, mit Reward 0. In den anderen Zuständen passiert nichts, und der Reward ist -1.
Left: Der Agent bewegt sich nach links, in $s_1$, $s_3$ , $s_5$ , mit Reward 0. In $s_0$ passiert nichts, und der Reward ist -1. In $s_2$ ist der Reward -100, und er bleibt in $s_2$ . In $s_4$ ist der Reward 10, der Agent landet in $s_0$.
Up: Mit Wahrscheinlichkeit 0.8, wie upC, mit Reward 0. Mit Wahrscheinlichkeit 0.1, gehe nach links, und mit Wahrscheinlichkeit 0.1 nach rechts (mit dem Reward, den die jeweilige Left oder Right Aktion hätte).

Aufgaben¶

Implementieren Sie eine Funktion reward, die den Reward für einen Zustand s, eine Aktion a und einen Nachfolge-Zustand s' ausrechnet. Die Reward-Funktion soll wie oben angegeben gestaltet sein. Die Zustände sollen als natürliche Zahlen 0 bis 5 modelliert werden, die Aktionen als Paare von Strings: Der erste String soll angeben, welche Aktion ausgewählt wurde, der zweite String, welche Aktion tatsächlich ausgeführt wurde (gewählte Aktionen: right, left und upC und up, ausgeführte Aktionen: right, left und upC). 5 Punkte.

In [ ]:

import numpy as np

def reward(s,a,snew):
    #TODO
    return None 

Implementieren Sie die Funktion performAction, die für einen Zustand s und eine gewählte Aktion a, die tatsächlich ausgeführte Aktion, und den Nachfolge-Zustand berechnet und als Paar zurückgibt. Das bedeutet, wenn als gewählte Aktion up übergeben wird, soll upC, left oder right entsprechend der oben beschriebenen Wahrscheinlichkeiten ausgeführt werden. 5 Punkte.

In [ ]:

#returns pair of actual performed action, and state
def performAction(s,a1):
    #TODO
    return None 

#Test: 
performAction(0,"up") #sollte entweder ("upC",2) oder ("left",0) oder ("right",1) zurückliefern

Der folgende Code erzeugt eine zufällige Sequenz von Aktionen und daraus resultierenden Zuständen. Diese Sequenz soll später verwendet werden, um ihren Q-Learning-Algorithmus zu testen.

In [ ]:

import numpy as np

#gleichverteilt 100 Aktionen auswählen
a1s = np.random.choice(np.array(["up","upC","left","right"]),size=100,replace=True)

a1s
states = [0]
actions = []

#Berechne und speichere tatsächlich ausgeführte Aktionen, und Zustands-Folge
for i in range(len(a1s)):
    sanew = performAction(states[i],a1s[i])
    actions = actions + [(a1s[i],sanew[0])]
    states = states + [sanew[1]]

print(states)
print(actions)

Implementieren Sie die Funktion qLearn, die für eine Sequenz von Aktionen und Zuständen (so wie oben erzeugt), eine Q-Matrix durch Q-Learning berechnet. Die initiale Q-Matrix soll nur aus Nullen bestehen. Benutzen Sie folgende Formel (diese resultiert aus der Standardregel für die Lernrate $\alpha = 1$):

$Q(s,a) = r_{s,a} + \gamma \ max_{a'}(Q(a(s),a')$ (wobei $a(s)$ den Nachfolge-Zustand von $s$, für die Aktion $a$, bezeichnet). 10 Punkte.

In [ ]:

def qLearn(actions,states,gamma=0.5):
    return Q
Q = qLearn(actions,states)
print(Q)

Betrachten Sie die resultierende Q-Matrix. Hat ihr Algorithmus eine intuitiv sinnvolle Policy gelernt? 2 Punkte