我正在学习 q-learning 并找到了一个维基百科帖子和这个网站。
根据教程和伪代码，我用 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])
}
这篇文章绝不是 R 中 Q-learning 的完整实现。它试图在文章链接的网站和维基百科中回答关于算法描述的 OP。
这里的假设是奖励矩阵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)]链接网站中的所谓术语和维基百科中的“最佳未来价值估计”。为了计算这一点，我们希望在ns第 -th 行上最大化，Q但只考虑对应第 -th 行的Q哪些列的列是有效动作（即，对于 which ）。因此，这是：RnsR[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在旧值Q[cs,ns]和学习值之间“插值” R[cs,ns] + gamma*max(Q[ns, which(R[ns,] > -1)])。正如维基百科所指出的，
在完全确定的环境中，学习率
alpha=1是最优的
将它们全部放在一个函数中：
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