如何在 R 中实现 q-learning？

Question

我正在学习 q-learning 并找到了维基百科 post 和这个 website。

根据教程和伪代码，我在 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

}

但我在 max(Qdash-Q[row,col] 中遇到问题，根据网站是 Max[Q(next state, all actions)] 我如何以编程方式搜索下一个状态的所有操作？

第二个问题就是这段伪代码

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

是这个吗

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

Answer 1

这个 post 绝不是 Q-learning 在 R 中的完整实现。它试图回答 OP 关于 [=87 中链接的网站中算法的描述=] 和维基百科。

此处假设奖励矩阵R如网站所述。也就是说，它将可能动作的奖励值编码为非负数，矩阵中的 -1 表示空值（即，没有可能的动作转换到该状态）。

使用此设置，Q 更新的 R 实现是：

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

哪里

cs 是路径中当前点的当前状态。
ns 是基于当前状态（随机）选择的动作的新状态。该动作是从当前状态下的可能动作集合中选择的（即，R[cs,] > -1）。由于这里的状态转换本身是确定性的，所以动作就是转换到新的状态。
对于导致 ns 的此操作，我们希望将其最大（未来）值添加到可以在 ns 处执行的所有可能操作。这就是链接网站中所谓的 Max[Q(next state, all actions)] 术语和维基百科中的 "estimate of optimal future value" 术语。为了计算这个，我们想要最大化 Q 的第 ns 行，但只考虑 Q 的列，其中 R 的列在相应的 [=18=第 ] 行是有效的操作（即 R[ns,] > -1）。因此，这是：
```
max(Q[ns, which(R[ns,] > -1)])
```
对该值的解释是一步前瞻值或动态规划中对成本的估计。
链接网站中的方程式是学习率 alpha 为 1 的特例。我们可以查看维基百科中的等式：
```
Q[cs,ns] <- (1-alpha)*Q[cs,ns] + alpha*(R[cs,ns] + gamma*max(Q[ns, which(R[ns,] > -1)]))
```
其中 alpha "interpolates" 介于旧值 Q[cs,ns] 和学习值 R[cs,ns] + gamma*max(Q[ns, which(R[ns,] > -1)]) 之间。如维基百科所述，

In fully deterministic environments, a learning rate of alpha=1 is optimal

将它们组合成一个函数：

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))
}

其中输入参数为：

R是博文中定义的奖励矩阵
N是要迭代的剧集数
alpha是学习率
gamma为折扣系数
tgt.state是问题的目标状态。

使用链接网站中的示例作为测试：

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

如何在 R 中实现 q-learning？

How to implement q-learning in R?

r

q-learning