Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning算法介绍
Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning是强化学习的算法之一,
Q
\mathrm{Q}
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning的主要目的就是学习状态动作价值函数的
Q
(
s
,
a
)
Q(s,a)
Q(s,a),其中
Q
(
s
,
a
)
Q(s,a)
Q(s,a)表示的是在给定当前状态
s
s
s和采取动作
a
a
a之后能够获得的收益期望。
Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning利用状态
s
s
s和动作
a
a
a张成一个
Q
Q
Q表来储存
Q
Q
Q值,然后根据
Q
Q
Q值来选取能够获得最大收益的动作。
Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning采用是值迭代的方法进行求解,其核心的迭代公式为
Q
k
+
1
(
s
,
a
)
=
∑
s
^
∈
S
p
(
s
^
∣
s
,
a
)
[
R
(
s
,
a
)
+
γ
⋅
max
a
^
∈
A
{
Q
k
(
s
^
,
a
^
)
}
]
Q_{k+1}(s,a)=\sum\limits_{\hat{s}\in\mathcal{S}}p(\hat{s}|s,a)\left[R(s,a)+\gamma \cdot \max\limits_{\hat{a}\in \mathcal{A}}\{Q_k(\hat{s},\hat{a})\}\right]
Qk+1(s,a)=s^∈S∑p(s^∣s,a)[R(s,a)+γ⋅a^∈Amax{Qk(s^,a^)}]其中
Q
k
+
1
(
s
,
a
)
Q_{k+1}(s,a)
Qk+1(s,a)第
k
+
1
k+1
k+1次迭代函数,
s
s
s和
a
a
a分别表示的是当前的状态和执行的动作并且它们分别属于状态空间
S
\mathcal{S}
S和动作空间
A
\mathcal{A}
A,
R
(
s
,
a
)
R(s,a)
R(s,a)表示的是在状态
s
s
s执行动作
a
a
a后的即时奖励,
s
^
\hat{s}
s^和
a
^
\hat{a}
a^表示的是下一个的状态和行为,
p
(
s
^
∣
s
,
a
)
p(\hat{s}|s,a)
p(s^∣s,a)表示的是状态转移概率,
γ
\gamma
γ表示的是折扣系数。
当动作空间
A
\mathcal{A}
A中的动作
a
a
a划分的足够细时候,给定当前状态
s
s
s和执行的动作
a
a
a,就能够明确确定下一个状态
s
^
\hat{s}
s^,进而则有
p
(
s
^
∣
s
,
a
)
=
1
p(\hat{s}|s,a)=1
p(s^∣s,a)=1,对上迭代公式进一步化简则有
Q
k
+
1
(
s
,
a
)
=
R
(
s
,
a
)
+
γ
⋅
max
a
^
∈
A
{
Q
k
(
s
^
,
a
^
)
}
Q_{k+1}(s,a)=R(s,a)+\gamma \cdot \max\limits_{\hat{a}\in \mathcal{A}}\{Q_k(\hat{s},\hat{a})\}
Qk+1(s,a)=R(s,a)+γ⋅a^∈Amax{Qk(s^,a^)}一般情况下
Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning算法用到的都是以上的迭代公式。
Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning具体实例
如下左半图显示,该图共有六个状态,五个房间分别是状态
0,
1
1
1,
2
2
2,
3
3
3和
4
4
4,以及房间外状态
5
5
5,右半图为左半图的状态转移过程的抽象示意图。现在的问题是如果有一个人在任意的一个房间里,给他支个招让他走出房间外。我们就可以通过强化学习中的
Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning方法来解决这个问题。
在解决这个问题之前需要先确定奖励矩阵
R
R
R,其元素表示的是当一个给定一个状态
s
s
s,当执行某个动作
a
a
a后,它的即时奖励
R
(
s
,
a
)
R(s,a)
R(s,a)的取值。规定当走出房间外到达状态
5
5
5的动作奖励为
100
100
100,如果没有走出房间外但在房间内可以走通的是奖励为
0,如果房间内也不能走通的动作奖励为
−
1
-1
−1。奖励矩阵
R
R
R具体取值如下所示。
R
=
[
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
1
100
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
1
100
−
1
−
1
−
1
100
]
R=\left[\begin{array}{rrrrrr}-1&-1&-1&-1&0&-1\\-1&-1&-1&0&-1&100\\-1&-1&-1&0&-1&-1\\-1&0&0&-1&0&-1\\0&-1&-1&0&-1&100\\-1&0&-1&-1&0&100\end{array}\right]
R=⎣⎢⎢⎢⎢⎢⎢⎡−1−1−1−10−1−1−1−10−10−1−1−10−1−1−100−10−10−1−10−10−1100−1−1100100⎦⎥⎥⎥⎥⎥⎥⎤
- 首先确定折扣系数
γ
=
0.8
\gamma=0.8
γ=0.8,并将
Q
Q
Q初始化为一个零矩阵:
Q
=
[
]
Q=\left[\begin{array}{cccccc}0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}\right]
Q=⎣⎢⎢⎢⎢⎢⎢⎡000000000000000000000000000000000000⎦⎥⎥⎥⎥⎥⎥⎤ - 第一轮第一次迭代随机选择初始状态为房间
1
1
1,然后观察矩阵
R
R
R的第二行(对应房间
1
1
1或者状态
1
1
1),这一行中有两个非负值,即当前状态
1
1
1的下一步行为有两种可能:转至状态
3
3
3或
5
5
5,此时选择随机选择转至状态
5
5
5。观察矩阵
R
R
R的第六行(对应房间
5
5
5或者状态
5
5
5),这一行有三个非负值,即当前状态
5
5
5的下一步行为有三种可能:转至状态
1
1
1,
4
4
4或
5
5
5。根据
Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning值迭代公式则有
Q
(
1
,
5
)
=
R
(
1
,
5
)
+
0.8
×
max
{
Q
(
5
,
1
)
,
Q
(
5
,
4
)
,
Q
(
5
,
5
)
}
=
100
+
0.8
×
max
{
,
,
}
=
100
\begin{aligned}Q(1,5)&=R(1,5)+0.8 \times \max\left\{Q(5,1),Q(5,4),Q(5,5)\right\}\\&=100+0.8 \times \max \{0,0,0\}\\&=100\end{aligned}
Q(1,5)=R(1,5)+0.8×max{Q(5,1),Q(5,4),Q(5,5)}=100+0.8×max{0,0,0}=100则此时将矩阵
Q
(
1
,
5
)
Q(1,5)
Q(1,5)位置(即该矩阵的第二行第六列)用
100
100
100进行数值更新。
Q
=
[
100
]
Q=\left[\begin{array}{cccccc}0&0&0&0&0&0\\0&0&0&0&0&100\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}\right]
Q=⎣⎢⎢⎢⎢⎢⎢⎡00000000000000000000000000000001000000⎦⎥⎥⎥⎥⎥⎥⎤ - 第一轮第二次迭代随机选择状态为房间
3
3
3,然后观察矩阵
R
R
R的第四行(对应房间
3
3
3或者状态
3
3
3),这一行中有三个非负值,即当前状态
3
3
3的下一步行为有三种可能:转至状态
1
1
1,
2
2
2或
4
4
4,此时随机选择转至状态
1
1
1。观察矩阵
R
R
R的第二行(对应房间
1
1
1或者状态
1
1
1),这一行中有两个非负值,即当前状态
1
1
1的下一步行为有两种可能:转至状态
3
3
3或
5
5
5。根据
Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning值迭代公式则有
Q
(
3
,
1
)
=
R
(
3
,
1
)
+
0.8
×
max
{
Q
(
1
,
3
)
,
Q
(
1
,
5
)
}
=
+
0.8
×
max
{
,
100
}
=
80
\begin{aligned}Q(3,1)&=R(3,1)+0.8 \times \max\left\{Q(1,3),Q(1,5)\right\}\\&=0+0.8 \times \max \{0,100\}\\&=80\end{aligned}
Q(3,1)=R(3,1)+0.8×max{Q(1,3),Q(1,5)}=0+0.8×max{0,100}=80则此时将矩阵
Q
(
3
,
1
)
Q(3,1)
Q(3,1)位置(即该矩阵的第二行第六列)用
80
80
80进行数值更新。
Q
=
[
100
80
]
Q=\left[\begin{array}{cccccc}0&0&0&0&0&0\\0&0&0&0&0&100\\0&0&0&0&0&0\\0&80&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}\right]
Q=⎣⎢⎢⎢⎢⎢⎢⎡000000000800000000000000000000001000000⎦⎥⎥⎥⎥⎥⎥⎤ - 经过多轮迭代之后直至
Q
Q
Q矩阵收敛,则此时的
Q
Q
Q即为所求,最后对
Q
Q
Q矩阵进行归一化。
Q
=
[
400
320
500
320
400
256
400
320
320
500
400
400
500
]
⟹
Q
=
[
80
64
100
64
80
51
80
64
64
100
80
80
100
]
Q=\left[\begin{array}{cccccc}0&0&0&0&400&0\\0&0&0&320&0&500\\0&0&0&320&0&0\\0&400&256&0&400&0\\320&0&0&320&0&500\\0&400&0&0&400&500\end{array}\right]\Longrightarrow Q=\left[\begin{array}{cccccc}0&0&0&0&80&0\\0&0&0&64&0&100\\0&0&0&64&0&0\\0&80&51&0&80&0\\64&0&0&64&0&100\\0&80&0&0&80&100\end{array}\right]
Q=⎣⎢⎢⎢⎢⎢⎢⎡00003200000400040000025600032032003200400004000400050000500500⎦⎥⎥⎥⎥⎥⎥⎤⟹Q=⎣⎢⎢⎢⎢⎢⎢⎡0000640000800800005100064640640800080080010000100100⎦⎥⎥⎥⎥⎥⎥⎤
下图表示的是经过
Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning算法学习之后得到的最终的状态转移示意图,其中每个带有箭头的线上标明这个动作对应的即时收益。所以不管在哪个状态下,只要利用贪心策略找即时收益最大的行为就可以走出房间。
以上实例中
Q
Q
Q–
L
e
a
r
n
i
n
g
\mathrm{Learning}
Learning算法的完整代码如下所示,代码比较简单大约50行就可以完整实现该功能
import numpy as np
import os
import random
def random_action(V):
index_list = []
for index, s in enumerate(list(V)):
if s >= 0:
index_list.append(index)
return random.choice(index_list)
def reward_setting(state_num, action_num):
R = -1 * np.ones((state_num , action_num))
R[0,4] = 0
R[1,3] = 0
R[1,5] = 100
R[2,3] = 0
R[3,1] = 0
R[3,2] = 0
R[3,4] = 0
R[4,0] = 0
R[4,3] = 0
R[4,5] = 100
R[5,1] = 0
R[5,4] = 0
R[5,5] = 100
return R
if __name__ == '__main__':
action_num = 6
state_num = 6
gamma = 0.8
epoch_number = 200
condition_stop = 5
Q = np.zeros((state_num , action_num))
R = reward_setting(state_num , action_num)
for epoch in range(epoch_number):
for s in range(state_num):
loop = True
while loop:
# Obtain random action a
a = random_action(R[s,:])
# Calculate maximum Q value
q_max = np.max(Q[a,:])
# Bellman optimal iteration equation
Q[s,a] = R[s,a] + gamma * q_max
s = a
if s == condition_stop:
loop = False
Q = (Q / 5).astype(int)
print(Q)
实验结果如下所示,大约训练200轮之后
Q
Q
Q矩阵就可以收敛到理论值,并且理论推导与实验结果一致。
版权声明:本文为博主鬼道2021原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/qq_38406029/article/details/121392140