主动学习与被动学习的区别#
主动学习：策略未固定，智能体可以主动选择动作来探索环境，改进策略π \pi π π ∗ \pi^* π ∗
被动学习：给定策略π \pi π V π ( s ) V^\pi(s) V π ( s ) Q π ( s , a ) Q^\pi(s, a) Q π ( s , a )
两者的典型学习方法#
被动学习：TD(0)和蒙特卡洛方法(MC)
主动学习：SARSA、Q-learning、DQN
被动学习方法# 被动学习的输入是一个固定的策略π \pi π V π ( s ) V^\pi(s) V π ( s ) Q π ( s , a ) Q^\pi(s, a) Q π ( s , a )
如果环境的状态转移概率P ( s ′ ∣ s , a ) P(s'|s, a) P ( s ′ ∣ s , a ) R ( s , a ) R(s, a) R ( s , a ) 模型已知 ，否则称为模型未知
模型未知# 蒙特卡洛方法(MC)# 直接让智能体从某状态出发，按给定策略π \pi π G t G_t G t
V π ( s ) ← V π ( s ) + α [ G t − V π ( s ) ] V^\pi(s) \leftarrow V^\pi(s) + \alpha [G_t - V^\pi(s)] V π ( s ) ← V π ( s ) + α [ G t − V π ( s )] 特点：
需要等待回合结束才能计算回报G t G_t G t
无偏，但方差较大
TIP α \alpha α 0 < α ≤ 1 0 < \alpha \leq 1 0 < α ≤ 1
时序差分法TD(0)# 无须等待完整回合结束，每步都可更新
由于：
G t = r t + γ G t + 1 G_t = r_{t} + \gamma G_{t+1} G t = r t + γ G t + 1 但是G t + 1 G_{t+1} G t + 1 V π ( s t + 1 ) V^\pi(s_{t+1}) V π ( s t + 1 )
G t ≈ r t + γ V π ( s t + 1 ) G_t \approx r_{t} + \gamma V^\pi(s_{t+1}) G t ≈ r t + γ V π ( s t + 1 ) 代入更新公式得TD(0)更新公式 ：
V π ( s t ) ← V π ( s t ) + α [ r t + γ V π ( s t + 1 ) − V π ( s t ) ] V^\pi(s_t) \leftarrow V^\pi(s_t) + \alpha [r_{t} + \gamma V^\pi(s_{t+1}) - V^\pi(s_t)] V π ( s t ) ← V π ( s t ) + α [ r t + γ V π ( s t + 1 ) − V π ( s t )] 主动学习方法# 为了让智能体能发现更优策略避免陷入局部最优，需要平衡探索(exploration)和利用(exploitation)，常用的办法是为策略引入随机性，例如ϵ \epsilon ϵ
ϵ \epsilon ϵ # 以概率ϵ \epsilon ϵ 1 − ϵ 1-\epsilon 1 − ϵ
a t = { 随机选择一个动作 a ∈ A ( s t ) , p < ϵ arg max a Q ( s t , a ) , p ≥ ϵ a_t = \begin{cases}
\text{随机选择一个动作 }a \in A(s_t), & p < \epsilon\\
\arg\max_{a} Q(s_t, a), & p \geq \epsilon
\end{cases} a t = { 随机选择一个动作 a ∈ A ( s t ) , arg max a Q ( s t , a ) , p < ϵ p ≥ ϵ WARNING 真正选中贪心动作的概率并非1 − ϵ 1-\epsilon 1 − ϵ ( 1 − ϵ ) + ϵ ∣ A ( s t ) ∣ (1-\epsilon) + \dfrac{\epsilon}{|A(s_t)|} ( 1 − ϵ ) + ∣ A ( s t ) ∣ ϵ
ϵ \epsilon ϵ # 常见做法：
ϵ k = max ( ϵ min , ϵ 0 ⋅ λ k ) \epsilon_k = \max(\epsilon_{\min}, \epsilon_0 \cdot \lambda^k) ϵ k = max ( ϵ m i n , ϵ 0 ⋅ λ k )
ϵ 0 \epsilon_0 ϵ 0 ϵ min \epsilon_{\min} ϵ m i n λ \lambda λ k k k 主动学习中的时序差分方法# SARSA# 1 : 初始化每个 Q ( s , a ) 为 0 2 : for 周期 i = 1 to M do 3 : for 时间步 t = 0 to T − 1 do 4 : 根据当前策略 π 选择动作 a t 并执行 , 得到 r t + 1 , s t + 1 5 : 根据当前策略 π 在 s t + 1 选择动作 a t + 1 6 : Q ( s t , a t ) target = r t + 1 + γ Q ( s t + 1 , a t + 1 ) 7 : Q ( s t , a t ) ← Q ( s t , a t ) + α [ Q ( s t , a t ) target − Q ( s t , a t ) ] 8 : 结束循环 9 : 结束循环 10 : 返回 Q ( s , a ) \boxed{
\begin{array}{rl}
1: & \text{初始化每个 }Q(s, a)\text{ 为 }0\\
2: & \text{for 周期 }i=1 \text{ to }M \text{ do}\\
3: & \qquad \text{for 时间步 }t=0 \text{ to }T-1 \text{ do}\\
4: & \qquad \qquad \text{根据当前策略 }\pi\text{选择动作 }a_t\text{并执行},\text{得到 }r_{t+1}, s_{t+1}\\
5: & \qquad \qquad \text{根据当前策略 }\pi\text{在 }s_{t+1}\text{选择动作 }a_{t+1}\\
6: & \qquad \qquad Q(s_t, a_t)_{\text{target}} = r_{t+1} + \gamma Q(s_{t+1}, a_{t+1})\\
7: & \qquad \qquad Q(s_t, a_t) \gets Q(s_t, a_t) + \alpha [Q(s_t, a_t)_{\text{target}} - Q(s_t, a_t)]\\
8: & \qquad \text{结束循环}\\
9: & \text{结束循环}\\
10: & \text{返回 }Q(s, a)
\end{array}
} 1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 初始化每个 Q ( s , a ) 为 0 for 周期 i = 1 to M do for 时间步 t = 0 to T − 1 do 根据当前策略 π 选择动作 a t 并执行 , 得到 r t + 1 , s t + 1 根据当前策略 π 在 s t + 1 选择动作 a t + 1 Q ( s t , a t ) target = r t + 1 + γ Q ( s t + 1 , a t + 1 ) Q ( s t , a t ) ← Q ( s t , a t ) + α [ Q ( s t , a t ) target − Q ( s t , a t )] 结束循环 结束循环 返回 Q ( s , a )
α \alpha α 0 < α ≤ 1 0 < \alpha \leq 1 0 < α ≤ 1 SARSA选择动作基于旧的策略π \pi π on-policy (在线)算法。行为策略和目标策略相同 。策略中的随机因素如果选择了奖励较低的动作，则会影响到Q值的更新，导致Q值收敛到一个较低的值。从而学习到更保守 的策略。
TIP SARSA是S → A → R → S ′ → A ′ S \rightarrow A \rightarrow R \rightarrow S' \rightarrow A' S → A → R → S ′ → A ′
Q-learning# 1 : 初始化每个 Q ( s , a ) 为 0 2 : for 周期 i = 1 to M do 3 : for 时间步 t = 0 to T − 1 do 4 : 根据当前策略 π 选择动作 a t 并执行 , 得到 r t + 1 , s t + 1 5 : Q ( s t , a t ) target = r t + 1 + γ max a Q ( s t + 1 , a ) 6 : Q ( s t , a t ) ← Q ( s t , a t ) + α [ Q ( s t , a t ) target − Q ( s t , a t ) ] 7 : 结束循环 8 : 结束循环 9 : 返回 Q ( s , a ) \boxed{
\begin{array}{rl}
1: & \text{初始化每个 }Q(s, a)\text{ 为 }0\\
2: & \text{for 周期 }i=1 \text{ to }M \text{ do}\\
3: & \qquad \text{for 时间步 }t=0 \text{ to }T-1 \text{ do}\\
4: & \qquad \qquad \text{根据当前策略 }\pi\text{选择动作 }a_t\text{并执行},\text{得到 }r_{t+1}, s_{t+1}\\
5: & \qquad \qquad Q(s_t, a_t)_{\text{target}} = r_{t+1} + \gamma \max_{a} Q(s_{t+1}, a)\\
6: & \qquad \qquad Q(s_t, a_t) \gets Q(s_t, a_t) + \alpha [Q(s_t, a_t)_{\text{target}} - Q(s_t, a_t)]\\
7: & \qquad \text{结束循环}\\
8: & \text{结束循环}\\
9: & \text{返回 }Q(s, a)
\end{array}
} 1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 初始化每个 Q ( s , a ) 为 0 for 周期 i = 1 to M do for 时间步 t = 0 to T − 1 do 根据当前策略 π 选择动作 a t 并执行 , 得到 r t + 1 , s t + 1 Q ( s t , a t ) target = r t + 1 + γ max a Q ( s t + 1 , a ) Q ( s t , a t ) ← Q ( s t , a t ) + α [ Q ( s t , a t ) target − Q ( s t , a t )] 结束循环 结束循环 返回 Q ( s , a ) Q-learning选择动作直接用最大的Q ( s t + 1 , a ) Q(s_{t+1}, a) Q ( s t + 1 , a ) off-policy (离线)算法。行为策略和目标策略不同 。即使策略的随机性导致选择了奖励较低的动作，也不会拉低Q值，Q值始终选择历史最优，Q值会收敛到一个较高的值，从而学习到更激进 的策略。
