最近自己会把自己个人博客中的文章陆陆续续的复制到CSDN上来,欢迎大家关注我的 个人博客,以及我的github。
本文主要讲解有关 Q-Learning 算法的内容,主要包括 on-policy 和 off-policy 的概念、Q-Learning 算法的基本思想和算法流程,最后还会讲解一个莫烦大神的例子。
1. on-policy 和 off-policy
on-policy(同策略): 智能体在自己做的过程中学习,即选择动作的策略和更新值函数的策略是同一个策略。;
off-policy(异策略): 智能体在看别人做的过程中学习,即选择动作的策略和更新值函数的策略不是同一个策略。;
上述两种也被译作在线学习和离线学习。
同策略时间差分: sarsa、sarsa( λ \lambda λ)
异策略时间差分: 重要性采样、Q-learning、Deep Q Network
关于时间(时序)差分(TD)算法这里只提一句我的理解:时间差分是和蒙特卡洛(MC)方法相对应的,后者是对一个回合(episode)的数据采样,而前者是对一步或多步的数据采样。采样完毕之后再去计算数据的均值啊之类的。
2. Q-Learning 算法
Q-Learning 就是创造一个 Q 表来指导智能体的行动,Q 表的行是状态,列是动作。一个状态对应的动作的数值越大,则智能体采用该动作的概率越大。Q 表的每个值就是在上篇文章中提到的动作值函数 Q(s,a)。
Q 表更新公式如下:
Q
(
S
t
,
A
t
)
←
Q
(
S
t
,
A
t
)
+
α
[
R
t
+
1
+
γ
⋅
max
Q
(
S
t
+
1
)
−
Q
(
S
t
,
A
t
)
]
Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma\cdot\max Q(S_{t+1})-Q(S_t,A_t)]
Q(St,At)←Q(St,At)+α[Rt+1+γ⋅maxQ(St+1)−Q(St,At)]
其中
γ
\gamma
γ 为衰减值;
α
\alpha
α 是学习率;
max
Q
(
S
t
+
1
)
\max Q(S_{t+1})
maxQ(St+1) 是状态
S
t
+
1
S_{t+1}
St+1 下概率最大的动作对应的 Q 表值,但是在实际行动时并不一定采取该行动;
R
t
+
1
+
γ
max
Q
(
S
t
+
1
)
R_{t+1}+\gamma\max Q(S_{t+1})
Rt+1+γmaxQ(St+1) 是根据贝尔曼方程得到的
Q
(
S
t
+
1
,
A
t
+
1
)
Q(S_{t+1},A_{t+1})
Q(St+1,At+1) 的推导值,后面称为 Q-target;而
Q
(
S
t
,
A
t
)
Q(S_t,A_t)
Q(St,At) 是
Q
(
S
t
+
1
,
A
t
+
1
)
Q(S_{t+1},A_{t+1})
Q(St+1,At+1) 的估计值,后面称为 Q-eval。
R
t
+
1
+
γ
max
Q
(
S
t
+
1
)
−
Q
(
S
t
,
A
t
)
R_{t+1}+\gamma\max Q(S_{t+1})-Q(S_t,A_t)
Rt+1+γmaxQ(St+1)−Q(St,At) 就是两者的误差值,在后面的文章中也称其为 TD-error(时分误差)。
根据动作值函数的定义(见上一篇文章)有:
Q
(
S
1
)
=
R
2
+
γ
Q
(
S
2
)
=
R
2
+
γ
[
R
3
+
γ
Q
(
S
3
)
]
Q(S_1)=R_2+\gamma Q(S_2)=R_2+\gamma [R_3+\gamma Q(S_3)]
Q(S1)=R2+γQ(S2)=R2+γ[R3+γQ(S3)]
= R 2 + γ [ R 3 + γ [ R 4 + γ Q ( S 4 ) ] ] = . . . =R_2+\gamma [R_3+\gamma [R_4+\gamma Q(S_4)]]=... =R2+γ[R3+γ[R4+γQ(S4)]]=...
所以:
Q
(
S
1
)
=
R
2
+
γ
R
3
+
γ
2
R
4
+
γ
3
R
5
+
.
.
.
Q(S_1)=R_2+\gamma R_3+\gamma^2 R_4+\gamma^3 R_5+...
Q(S1)=R2+γR3+γ2R4+γ3R5+...
当
γ
=
1
\gamma=1
γ=1 时:
Q
(
S
1
)
=
R
2
+
R
3
+
R
4
+
R
5
+
.
.
.
Q(S_1)=R_2+R_3+R_4+R_5+...
Q(S1)=R2+R3+R4+R5+...
也就是动作值函数与该状态之后的所有奖励有关,并且其权重相等。
当
γ
=
0
\gamma=0
γ=0 时:
Q
(
S
1
)
=
R
2
Q(S_1)=R_2
Q(S1)=R2
也就是动作值函数只与该状态的前后一个奖励有关。
当
0
<
γ
<
1
0<\gamma<1
0<γ<1 时:
Q
(
S
1
)
=
R
2
+
γ
R
3
+
γ
2
R
4
+
γ
3
R
5
+
.
.
.
Q(S_1)=R_2+\gamma R_3+\gamma^2 R_4+\gamma^3 R_5+...
Q(S1)=R2+γR3+γ2R4+γ3R5+...
也就是说 Q 表实现了奖励值的衰减,离当前状态越远的奖励衰减的越严重。
3. Q-Learning 算法流程
(1)初始化 Q 表(值全为 0 )
(2)根据当前状态选择一个 Action
(3)执行 Action 并获得相应的奖励,以及下一个状态
(4)按照公式更新 Q 表
(5)将下一个状态设为当前状态
(6)重复 2-5 步
值得注意的是在 Q-Learning 算法中有两个“ 策略”,一个是选取动作的策略,另一个是更新 Q 表的策略。这两个策略分别采用的是 ϵ \epsilon ϵ贪婪算法和最大值算法,所以 Q-Learning 是 off-policy 的。
4. 探索-利用困境
如果智能体仅仅按照 Q 表的最大概率指导行动的话,很多状态可能根本没办法达到,学习效率是比较低的,这就是探索-利用困境(Explore-Exploit dilemma)。可以用 ϵ \epsilon ϵ 贪婪( ϵ − G r e e d y \epsilon-Greedy ϵ−Greedy)方法解决。
ϵ \epsilon ϵ 贪婪方法就是设定一个 0 < ϵ < 1 0<\epsilon<1 0<ϵ<1,并以 ϵ \epsilon ϵ 的概率按照 Q 表数值最大的动作行动,以 1 − ϵ 1-\epsilon 1−ϵ 的概率随机行动。
5. Q-Learning 版寻找宝藏的例子
以下代码实现了一个智能体(用字符 ‘o’ 表示)寻找宝藏(用字符 ‘T’ 表示)的强化学习过程,所用的算法是 Q-Learning 算法。当智能体找到宝藏时奖励值为 1,反之为 0。智能体的动作只有两个—— left 和 right,即向左移动和向右移动。程序会显示智能体和宝藏的位置、每个回合的奖励值以及终止状态时 Q 表的情况。
import numpy as np
import pandas as pd
import time
np.random.seed(2)
N_STATES = 6
ACTIONS = ['left', 'right']
EPSILON = 0.9
ALPHA = 0.1
GAMMA = 0.9
MAX_EPISODES = 10 # 回合数
FRESH_TIME = 0.3
def build_q_table(n_states, actions): # 初始化 Q 表
table = pd.DataFrame(
np.zeros((n_states, len(actions))),
columns=actions, # 列的名称
)
return table
def choose_action(state, q_table): # 根据当前状态和 Q 表选择一个动作
# 如果随机数的值大于 EPSIlON 或者 Q 表的当前列都是 0 (即第一次到达该状态)
if (np.random.uniform() > EPSILON or (q_table.iloc[state, :] == 0).all()):
action_name = np.random.choice(ACTIONS) # 随机选择一个动作
else:
action_name = q_table.iloc[state, :].idxmax() # 选择当前状态对应的值最大的动作
return action_name
def get_env_feedback(S, A): # 获取新的状态和对应的奖励
R = 0
if A == "right": # 往右
S_ = S + 1
else: # 往左
S_ = S - 1
if S_ < 0: # 如果到达最左端
S_ = 0
if S_ == N_STATES - 1: # 如果找到宝藏
S_ = "terminal"
R = 1
return S_, R
def update_env(S, episode, step_counter): # 更新环境,主要是用来显示,可以不必搞懂
env_list = ['-'] * (N_STATES - 1) + ['T']
if S == "terminal":
interaction = "Episode %s: total_steps = %s" % (episode + 1, step_counter)
print("\r{}".format(interaction), end="")
time.sleep(2)
print("\r ", end="")
else:
env_list[S] = 'o'
interaction = "".join(env_list)
print("\r{}".format(interaction), end="")
time.sleep(FRESH_TIME)
def q_learning(): # Q-Learning 算法
q_table = build_q_table(N_STATES, ACTIONS)
for episode in range(MAX_EPISODES):
S = 0
step_counter = 0 # 共走了多少步
is_terminal = False
update_env(S, episode, step_counter)
while not is_terminal:
A = choose_action(S, q_table)
S_, R = get_env_feedback(S, A)
# 下面的代码是为了更新 Q 表
q_predict = q_table.loc[S, A]
if S_ != 'terminal':
q_target = R + GAMMA * q_table.iloc[S_, :].max()
else: # 终止状态
q_target = R
is_terminal = True
q_table.loc[S, A] += ALPHA * (q_target - q_predict) # 根据公式更新
S = S_
step_counter += 1
update_env(S, episode, step_counter)
return q_table
if __name__ == "__main__":
q_table = q_learning()
print("\r\nQ-table:\n")
print(q_table)