Wie implementiert man q-learning in R?

Question

Ich lerne über q-Learning und fand eine Wikipedia-Post und diese website.

Nach den Tutorials und Pseudo-Code schrieb ich so viel in R

#q-learning example 
#http://mnemstudio.org/path-finding-q-learning-tutorial.htm 
#https://en.wikipedia.org/wiki/Q-learning 

set.seed(2016) 
iter=100 
dimension=5; 
alpha=0.1 #learning rate 
gamma=0.8 #exploration/ discount factor 

# n x n matrix 
Q=matrix(rep(0, len=dimension*dimension), nrow = dimension) 
Q 

# R -1 is fire pit,0 safe path and 100 Goal state######## 
R=matrix(sample(-1:0, dimension*dimension,replace=T,prob=c(1,2)), nrow = dimension) 
R[dimension,dimension]=100 
R #reward matrix 
################ 

for(i in 1:iter){ 
    row=sample(1:dimension,1) 
    col=sample(1:dimension,1) 
    I=Q[row,col] #randomly choosing initial state 

    Q[row,col]=Q[row,col]+alpha*(R[row,col]+gamma*max(Qdash-Q[row,col]) 
    #equation from wikipedia 

} 

Aber ich habe Probleme in max(Qdash-Q[row,col], welche laut der Webseite ist Max[Q(next state, all actions)] Wie ich programmatisch alle Aktionen für die nächsten Zustand suchen?

Das zweite Problem ist der Pseudo-Code

Do While the goal state hasn't been reached. 

Select one among all possible actions for the current state. 
Using this possible action, consider going to the next state. 
Get maximum Q value for this next state based on all possible actions. 
Compute: Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)] 
Set the next state as the current state. 
End Do 

es diese

durch nein Ist

while(Q<100){ 
Q[row,col]=Q[row,col]+alpha*(R[row,col]+gamma*max(Qdash-Q[row,col]) 
} 

Answer 1

Dieser Beitrag bedeutet in R. eine vollständige Implementierung von Q-Learning Es ist ein Versuch, zu beantworten das OP bezüglich der Beschreibung des Algorithmus in der Website verlinkt in der Post und in Wikipedia.

Die Annahme hier ist, dass die Belohnung Matrix R wie auf der Website beschrieben ist. Nämlich, dass es Belohnungswerte für mögliche Aktionen als nicht negative Zahlen codiert und -1 in der Matrix Nullwerte darstellen (d. H. Wo es keine mögliche Aktion gibt, um in diesen Zustand überzugehen).

Mit diesem Aufbau wird eine R Implementierung des Q Update:

Q[cs,ns] <- Q[cs,ns] + alpha*(R[cs,ns] + gamma*max(Q[ns, which(R[ns,] > -1)]) - Q[cs,ns]) 

wo

1. cs den aktuellen Zustand an dem aktuellen Punkt in dem Pfad ist.
2. ns ist der neue Zustand basierend auf einer (zufällig) gewählten Aktion im aktuellen Zustand. Diese Aktion wird aus der Sammlung möglicher Aktionen im aktuellen Zustand (d. H. Für die R[cs,] > -1) ausgewählt. Da der Zustandsübergang selbst hier deterministisch ist, ist die Aktion der Übergang in den neuen Zustand.

3. Für diese Aktion, die zu ns führt, möchten wir ihren maximalen (zukünftigen) Wert über alle möglichen Aktionen hinzufügen, die bei ns vorgenommen werden können. Dies ist der sogenannte Max[Q(next state, all actions)] Begriff auf der verlinkten Website und die "Schätzung des optimalen zukünftigen Wertes" in Wikipedia. Um dies zu berechnen, wollen wir über die ns -te Reihe von Q maximieren, aber nur Spalten von Q betrachten, für die Spalten von R an der entsprechenden ns -ten Reihe gültige Aktionen sind (d. H. Für welche). Daher ist dies:

   max(Q[ns, which(R[ns,] > -1)]) 
   

   Eine Interpretation dieses Wertes ist ein Ein-Schritt nach vorne schauen Wert oder eine Schätzung der Kosten-to-go in der dynamischen Programmierung.

4. Die Gleichung in der verknüpften Website ist der Spezialfall, in dem alpha, die Lernrate, 1 ist.

   Q[cs,ns] <- (1-alpha)*Q[cs,ns] + alpha*(R[cs,ns] + gamma*max(Q[ns, which(R[ns,] > -1)])) 
   

   wo alpha „interpoliert“ zwischen dem alten Wert Q[cs,ns] und dem gelernten Wert R[cs,ns] + gamma*max(Q[ns, which(R[ns,] > -1)]): Wir können die Gleichung in Wikipedia als anzuzeigen.Wie in Wikipedia erwähnt,

   In vollständig deterministischen Umgebungen ist eine Lernrate von alpha=1 optimal

sie alle zusammen in eine Funktion Putting:

q.learn <- function(R, N, alpha, gamma, tgt.state) { 
    ## initialize Q to be zero matrix, same size as R 
    Q <- matrix(rep(0,length(R)), nrow=nrow(R)) 
    ## loop over episodes 
    for (i in 1:N) { 
    ## for each episode, choose an initial state at random 
    cs <- sample(1:nrow(R), 1) 
    ## iterate until we get to the tgt.state 
    while (1) { 
     ## choose next state from possible actions at current state 
     ## Note: if only one possible action, then choose it; 
     ## otherwise, choose one at random 
     next.states <- which(R[cs,] > -1) 
     if (length(next.states)==1) 
     ns <- next.states 
     else 
     ns <- sample(next.states,1) 
     ## this is the update 
     Q[cs,ns] <- Q[cs,ns] + alpha*(R[cs,ns] + gamma*max(Q[ns, which(R[ns,] > -1)]) - Q[cs,ns]) 
     ## break out of while loop if target state is reached 
     ## otherwise, set next.state as current.state and repeat  
     if (ns == tgt.state) break 
     cs <- ns 
    } 
    } 
    ## return resulting Q normalized by max value 
    return(100*Q/max(Q)) 
} 

wo die Eingangs Parameter sind:

1. R ist die Belohnungen Matrix als
2. N ist die Anzahl der Episoden im Blog definiert
3. alpha wird die Lernrate
4. gamma ist der Abzinsungsfaktor
5. tgt.state wird der Zielzustand des Problems iterieren .

das Beispiel in der verknüpften Webseite als Test verwenden:

N <- 1000 
alpha <- 1 
gamma <- 0.8 
tgt.state <- 6 
R <- matrix(c(-1,-1,-1,-1,0,-1,-1,-1,-1,0,-1,0,-1,-1,-1,0,-1,-1,-1,0,0,-1,0,-1,0,-1,-1,0,-1,0,-1,100,-1,-1,100,100),nrow=6) 
print(R) 
##  [,1] [,2] [,3] [,4] [,5] [,6] 
##[1,] -1 -1 -1 -1 0 -1 
##[2,] -1 -1 -1 0 -1 100 
##[3,] -1 -1 -1 0 -1 -1 
##[4,] -1 0 0 -1 0 -1 
##[5,] 0 -1 -1 0 -1 100 
##[6,] -1 0 -1 -1 0 100 

Q <- q.learn(R,iter,alpha,gamma,tgt.state) 
print(Q) 
##  [,1] [,2] [,3] [,4] [,5]  [,6] 
##[1,] 0 0 0.0 0 80 0.00000 
##[2,] 0 0 0.0 64 0 100.00000 
##[3,] 0 0 0.0 64 0 0.00000 
##[4,] 0 80 51.2 0 80 0.00000 
##[5,] 64 0 0.0 64 0 100.00000 
##[6,] 0 80 0.0 0 80 99.99994