目录
1. TD预测
TD是另一种对最优策略的学习方法，本节讲述TD预测，即使用TD求解策略
π
\pi
π
的值函数
v
π
(
s
)
v_{\pi}(s)
v
π
(
s
)
。
TD预测被称为 DP 和 MC 的结合体，DP是 期望更新+自举bootstrap，MC是 采样更新 + 样本估计。而
TD则是采样更新 + 自举
，即
值函数
V
(
S
t
)
V(S_t)
V
(
S
t
)
更新基于采样得到的
V
(
S
t
+
i
)
V(S_{t+i})
V
(
S
t
+
i
)
的结果
。
如果
i
=
1
i=1
i
=
1
，就为TD(0)单步TD算法，否则就为多步TD
当然动态特性
p
(
s
′
,
a
∣
s
,
a
)
p(s’,a|s,a)
p
(
s
′
,
a
∣
s
,
a
)
对于TD也是未知的。
1.1. TD(0)算法
根据采样更新与自举的思想，TD(0)的状态值函数预测式为
V
(
S
t
)
=
V
(
S
t
)
+
α
[
R
t
+
1
+
γ
V
(
S
t
+
1
)
−
V
(
S
t
)
]
(1)
V(S_t) = V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) – V(S_t)] \tag{1}
V
(
S
t
)
=
V
(
S
t
)
+
α
[
R
t
+
1
+
γ
V
(
S
t
+
1
)
−
V
(
S
t
)
]
(
1
)
先给出一些定义：
TD目标
：指
R
t
+
1
+
γ
V
(
S
t
+
1
)
R_{t+1} + \gamma V(S_{t+1})
R
t
+
1
+
γ
V
(
S
t
+
1
)
TD误差
：指
R
t
+
1
+
γ
V
(
S
t
+
1
)
−
V
(
S
t
)
R_{t+1} + \gamma V(S_{t+1}) – V(S_t)
R
t
+
1
+
γ
V
(
S
t
+
1
)
−
V
(
S
t
)
步长\学习率
：指
α
\alpha
α
如何理解上述定义呢？
结合图一看就明白了。对于状态
s
s
s
，所有包含
s
s
s
的episode均会使值函数的估计值
V
(
s
)
V(s)
V
(
s
)
朝着TD目标走长度为
α
\alpha
α
倍TD误差 的一步，而获得新的
V
(
s
)
V(s)
V
(
s
)
。就是经过这样不断地走，最终会接近
v
π
(
s
)
v_{\pi}(s)
v
π
(
s
)
。
有没有想到梯度下降中的步长的概念？意思其实是一样的，同样的可以使用非恒定学习率，例如
1
s
的
更
新
次
数
\frac{1}{s的更新次数}
s
的
更
新
次
数
1
，即越接近
v
π
(
s
)
v_{\pi}(s)
v
π
(
s
)
学习率越小，这样
V
(
s
)
V(s)
V
(
s
)
就变成了采样取平均的方法。取平均的确会收敛概率为1，但这样收敛较慢，且对于非平稳问题则不太合适。
由此特征可以看到DP和MC的影子，深刻理解TD算法的思想：
-
采样更新：可以看到
(1
)
(1)
(
1
)
中更新的状态是与
tt
t
有关的，即
V(
S
t
)
V(S_t)
V
(
S
t
)
的更新是基于样本采样得出的
单个
后继节点的值函数，即
St
+
1
S_{t+1}
S
t
+
1
。
只不过MC中用的是当前样本算得的
Gt
G_t
G
t
，TD中直接用的估计结果V。 -
自举：式子中状态的值函数
V(
S
t
)
V(S_t)
V
(
S
t
)
需要用到 已存在的 其他状态的值函数
V(
S
t
+
1
)
V(S_{t+1})
V
(
S
t
+
1
)
所以式子
(1
)
(1)
(
1
)
中的
Rt
+
1
+
γ
V
(
S
t
+
1
)
R_{t+1} + \gamma V(S_{t+1})
R
t
+
1
+
γ
V
(
S
t
+
1
)
到底叫不叫样本？ 叫吧，可这个值涉及到多次迭代的估计值。不叫吧，可这又是采样得来的，而且
V(
S
t
)
V(S_t)
V
(
S
t
)
的更新只看样本给出的下一个状态
V(
S
t
+
1
)
V(S_{t+1})
V
(
S
t
+
1
)
。
\quad
因此TD的核心思想是
对于状态
ss
s
，步步采样，用估计值函数
V(
s
′
)
V(s’)
V
(
s
′
)
更新
（而非样本回报
Gt
G_t
G
t
）
上代码
V TDEvaluation(S,A,R,policy,alpha,gamma,maxEpisodeNum)
{
V(S) = 0;
episode = 1;
for episode = 1:maxEpisodeNum
{
s = random(S);
while(s != terminalState)
{
a = policy(s);
s' = updateState(s,a);
r = reward(s,a,s');
V(s) = V(s) + alpha*( r + gamma*V(s') - V(s) );
s = s';
}
}
return V(S);
}
2. 同轨TD控制：Sarsa
这里讨论经典的同轨的TD控制方法Sarsa。既然是同轨法，即行动策略 和 目标策略 相同，就必须考虑最优策略是确定性策略，即选择行动状态函数最大的动作时，这样的行动策略会带来的样本探索受限的问题（
动态规划与蒙特卡洛方法
中如是说）
2.1.
ϵ
\epsilon
ϵ
-软性策略 (
ϵ
\epsilon
ϵ
-greedy)
思路是将确定性策略改成
近似确定性
，即以较大概率
1
−
ϵ
1-\epsilon
1
−
ϵ
选择
max
a
q
π
(
s
,
a
)
\max_aq_{\pi}(s,a)
max
a
q
π
(
s
,
a
)
，以较小概率
ϵ
\epsilon
ϵ
选择其他行为。因此要满足
1
−
ϵ
>
>
ϵ
1-\epsilon >> \epsilon
1
−
ϵ
>
>
ϵ
。
该策略如下：
Action policy(state,Q,epsilon)
{
if( rand(0,1) < epsilon )
return randomActions(state);
else
return argmax(Action,Q(state,:));
}
这样的软性策略，实际上对于新样本的采集（行动策略）会以很小的概率
ϵ
\epsilon
ϵ
进行，因此Sarsa算法的特点就是点的探索会比较保守。
2.2. 算法流程
与公式
(
1
)
(1)
(
1
)
类似，得到
Q
(
s
,
a
)
Q(s,a)
Q
(
s
,
a
)
的更新公式：
Q
(
s
,
a
)
=
Q
(
s
,
a
)
+
α
[
R
(
s
,
a
)
+
γ
Q
(
s
′
,
a
′
)
−
Q
(
s
,
a
)
]
Q(s, a) = Q(s, a) + \alpha [ R(s,a) + \gamma Q(s’,a’) -Q(s,a)]
Q
(
s
,
a
)
=
Q
(
s
,
a
)
+
α
[
R
(
s
,
a
)
+
γ
Q
(
s
′
,
a
′
)
−
Q
(
s
,
a
)
]
注意到公式中出现了新状态的新动作
a
′
a’
a
′
，该新动作也是通过
ϵ
\epsilon
ϵ
-软性策略得到的。
整体代码如下，由于
policy()
是选取动作值函数
Q(s,:)
最大的动作，因此更新
Q(s,a)
就是控制。
policy Sarsa(S,A,R,epsilon,alpha,gamma,maxEpisodeNum)
{
Q(S,A) = 0;
episode = 1;
for episode = 1:maxEpisodeNum
{
s = random(S);
a = policy(s);
while(s != terminalState)
{
s' = updateState(s,a);
a' = policy(s',Q,epsilon);
r = reward(s,a,s');
Q(s,a) = Q(s,a) + alpha*( r + gamma*Q(s',a') - Q(s,a) );
s = s';
a = a';
}
}
return policy(S,Q,epsilon);
}
3. 离轨TD控制：Q学习
3.1. 基本思想
Q-Learning算法是一种强化学习算法，通过智能体在环境中不断地训练进而得出一种模型，在该模型下实现智能体的决策。
Q-Learning 的思想 是将智能体划分为多个可能的
状态
，每个状态之间通过某种
行为
相互转换（
类似于状态机，也类似于离散系统控制中的系统状态x(k)和控制信号u(k)
），在某种状态下采取不同的行为会得到不同的
收益reward
。
智能体的行为选择 是基于
获得的期望总体收益q最大
进行的，即在状态
s
s
s
下采取策略
a
a
a
是因为这样才能使未来期望的总收益达到最大
因此需要记录 所有状态的所有行为的
期望总体收益
，即
Q
(
s
,
a
)
Q(s,a)
Q
(
s
,
a
)
。
（注意策略
a
a
a
是基于未来所有收益的期望值，而非眼下的收益reward，一种动态规划思想）
Q-learning算法是一种 针对特定场景下边决策边训练的强化学习算法。主要变量如下
状态
s
s
s
，
行为
a
a
a
，
收益
r
e
w
a
r
d
(
s
,
a
)
reward(s,a)
r
e
w
a
r
d
(
s
,
a
)
，
动作值函数Q-table
Q
(
s
,
a
)
Q(s,a)
Q
(
s
,
a
)
，
且系统状态
s
s
s
会在
a
a
a
的作用下发生转移，即
s
j
=
a
i
j
(
s
i
)
s_j = a_{ij}(s_i)
s
j
=
a
i
j
(
s
i
)
（注意reward和Q-table的输入是两个：状态 和 行为，而不只是状态。即使转移到相同的状态s，也可能有不同的收益，
r
e
w
a
r
d
(
s
i
,
a
i
j
)
≠
r
e
w
a
r
d
(
s
k
,
a
k
j
)
reward(s_i ,a_{ij}) ≠ reward(s_k ,a_{kj})
r
e
w
a
r
d
(
s
i
,
a
i
j
)
=
r
e
w
a
r
d
(
s
k
,
a
k
j
)
）
Q-learning的训练的过程只是 不断重复两步
思维决策、Q-table更新
1.1.节中智能体的行为选择 是基于获得的
期望总体收益q最大
进行的，这里的
期望总体收益
指的就是Q-table的值。
因此智能体的选择很简单，取Q最大值对应的
a
a
a
即可，如果当前状态为
s
s
s
则选择的行为
a
a
a
应当满足
a
=
a
m
a = a_m
a
=
a
m
,
where
a
m
a_m
a
m
s.t.
Q
(
s
,
a
m
)
=
m
a
x
{
Q
(
s
,
a
1
)
,
Q
(
s
,
a
2
)
,
.
.
.
,
Q
(
s
,
a
n
)
}
Q(s, a_m) = max\{Q(s,a_1),Q(s,a_2),…,Q(s,a_n) \}
Q
(
s
,
a
m
)
=
m
a
x
{
Q
(
s
,
a
1
)
,
Q
(
s
,
a
2
)
,
.
.
.
,
Q
(
s
,
a
n
)
}
。
Q-table中
Q
(
s
,
a
)
Q(s,a)
Q
(
s
,
a
)
表示状态
s
s
s
下采取
a
a
a
的得到的期望总体收益。
总体收益
的含义是指，从状态
s
s
s
采取动作
a
a
a
到
s
′
s’
s
′
开始到算法结束的所有收益之和。但是从
s
′
s’
s
′
到算法终止策略有很多，因此这样的收益有很多，但有一个期望值。
期望的总体收益
则是指从状态为
s
s
s
，采取动作
a
a
a
转移至
s
′
s’
s
′
，如果接下来都采取最佳策略的总体收益。
最佳策略
则是如1.2.1所讲，期望总体收益q最大的那个选择策略。
因此根据动态规划思想，
Q
(
s
,
a
)
Q(s,a)
Q
(
s
,
a
)
就应该包含：状态
s
s
s
采取动作
a
a
a
的收益 和
s
′
s’
s
′
的期望总体收益。
Q
(
s
,
a
)
=
r
e
w
a
r
d
(
s
,
a
)
+
γ
E
[
Q
(
s
′
)
]
Q(s, a) = reward(s,a) + \gamma E[Q(s’)]
Q
(
s
,
a
)
=
r
e
w
a
r
d
(
s
,
a
)
+
γ
E
[
Q
(
s
′
)
]
=
r
e
w
a
r
d
(
s
,
a
)
+
γ
m
a
x
a
{
Q
(
s
′
,
a
)
}
\quad\quad\quad= reward(s,a) + \gamma max_{a}\{Q(s’,a)\}
=
r
e
w
a
r
d
(
s
,
a
)
+
γ
m
a
x
a
{
Q
(
s
′
,
a
)
}
其中
s
′
=
a
(
s
)
s’ = a(s)
s
′
=
a
(
s
)
，
E
[
Q
(
s
′
)
]
E[Q(s’)]
E
[
Q
(
s
′
)
]
表示
s
′
s’
s
′
状态的总体收益的期望值，
γ
\gamma
γ
表示折扣因子，用于确定延迟回报与当前回报的相对比例， 越大表明延迟回报的重要程度越高。
迭代过程中
Q
(
s
,
a
)
Q(s, a)
Q
(
s
,
a
)
是不断修正地过程，因此将
Q
(
s
,
a
)
Q(s, a)
Q
(
s
,
a
)
变为过去的估计值 和 当前的现实值得加权和（
Kalman滤波器既视感
）
Q
(
s
,
a
)
=
Q
(
s
,
a
)
+
ϵ
(
R
(
s
,
a
)
+
γ
m
a
x
a
{
Q
(
s
′
,
a
)
}
)
Q(s, a) = Q(s, a) + \epsilon ( R(s,a) + \gamma max_{a}\{Q(s’,a)\} )
Q
(
s
,
a
)
=
Q
(
s
,
a
)
+
ϵ
(
R
(
s
,
a
)
+
γ
m
a
x
a
{
Q
(
s
′
,
a
)
}
)
其中
ϵ
\epsilon
ϵ
表示学习率。
3.2. 算法流程
对Q-learning算法进行一个流程总结，可能直接看伪代码更加清晰。
QLearning(initialState,endState,reward,N)
{
episode = 1;
s = initialState;
while(episode < N)
{
a = chooseAction(s,Qfun);
sNew = updateState(s,a);
Qfun = updateQ(Qfun,reward,s,a,sNew);
s = sNew;
if(sNew == endState)
{
s = initialState;
episode++;
}
}
}
动作选择、状态更新 和 Qtable更新细节如下
action chooseAction(currentState,Qfun,prob)
{
if(rand(0,1) > prob)
return rand(all Actions within currentState);
bestAction = first Action;
for each Action in currentState:
if(Qfun(currentState,Action) > Qfun(currentState,bestAction))
bestAction = Action;
return bestAction;
}
newState updateState(currentState,action) //与系统动力学有关
Qfun updateQ(Qfun,reward,currentState,currentAction,newState,gamma,epsilon)
{
s = currentState;
a = currentAction;
sNew = newState;
Qfun(s,a) += epsilon * (reward(s,a) +gamma * max(Qfun(sNew,:)) );
return Qfun(s,a);
}
参考资料
-
https://www.bilibili.com/video/BV13W411Y75P?p=5
-
https://blog.csdn.net/itplus/article/details/9361915
-
https://baijiahao.baidu.com/s?id=1597978859962737001&wfr=spider&for=pc
-
https://blog.csdn.net/wlm_py/article/details/101301986
X. 动态规划法DP、蒙特卡洛法MC 和 时序差分法TD的比较
X.1. 核心思想
X.2. 算法特点