强化学习Q-Learning算法

前言

学习这个算法有一段时间了，但是因为自己犯懒一直没有整理。现整理一下，一方面有刚入门的同学可以参考，另一方面哪里写错或者理解不深的还请大家及时指正。

基本概念

基本概念

首先列出一些强化学习中的基本概念，主要是为了帮助自己回忆起学习这个算法的过程。

1. 状态值函数：智能体在状态 s s s 处的累计回报的期望值被称为智能在在采用策略 π \pi π 时在状态 s s s 处的状态值函数。用公式表示如下： v π ( s ) = E [ ∑ k = 0 ∞ γ k R t + k + 1 ∣ S t = s ] v_{\pi}\left(s\right) = \mathbb{E}\left[\sum_{k=0}^{\infty}\gamma^{k}\mathcal{R}_{t+k+1}|S_{t}=s\right] vπ​(s)=E[k=0∑∞​γkRt+k+1​∣St​=s]
   不同的策略 π \pi π 在相同的状态 s s s 下对应的状态值函数是不同的，因为策略 π \pi π 本身会影响智能体处在某一状态是的行为，进而改变累计回报 G \mathcal{G} G 。
2. 状态-行为值函数：智能体在状态 s s s 处执行动作 a a a 所获得的累计回报的期望值被定义为智能体在策略 π \pi π 时处在状态 s s s 处执行动作 a a a 的状态-行为值函数。用公式表示如下： q π ( s , a ) = E π [ ∑ k = 0 ∞ γ k R t + k + 1 ∣ S t = s , A t = a ] q_{\pi}\left(s,a\right)=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty}\gamma^{k}\mathcal{R}_{t+k+1}|S_{t}=s, A_{t}=a\right] qπ​(s,a)=Eπ​[k=0∑∞​γkRt+k+1​∣St​=s,At​=a]

递推关系

智能体的状态值函数和状态行为值函数之间存在一种递推关系。下图给出四种递推关系：

1. v π ( s ) → q π ( s , a ) v_{\pi}\left(s\right)\rightarrow q_{\pi}\left(s,a\right) vπ​(s)→qπ​(s,a) v π ( s ) = ∑ a ∈ A π ( a ∣ s ) q π ( s , a ) v_{\pi}\left(s\right)=\sum_{a\in A}\pi\left(a|s\right)q_{\pi}\left(s,a\right) vπ​(s)=a∈A∑​π(a∣s)qπ​(s,a)
2. v π ( s ) → v π ( s ′ ) v_{\pi}\left(s\right)\rightarrow v_{\pi}\left(s'\right) vπ​(s)→vπ​(s′) v π ( s ) = ∑ a ∈ A π ( a ∣ s ) [ R s a + γ ∑ s ′ P s s ′ a v π ( s ′ ) ] v_{\pi}\left(s\right)=\sum_{a\in A}\pi\left(a|s\right)\left[R_{s}^{a}+\gamma\sum_{s'}P_{ss'}^{a}v_{\pi}\left(s'\right)\right] vπ​(s)=a∈A∑​π(a∣s)[Rsa​+γs′∑​Pss′a​vπ​(s′)]
3. q π ( s , a ) → v π ( s ′ ) q_{\pi}\left(s,a\right)\rightarrow v_{\pi}\left(s'\right) qπ​(s,a)→vπ​(s′) q π ( s , a ) = R s a + γ ∑ s ′ P s s ′ a v π ( s ′ ) q_{\pi}\left(s,a\right)=R_{s}^{a}+\gamma\sum_{s'}P_{ss'}^{a}v_{\pi}\left(s'\right) qπ​(s,a)=Rsa​+γs′∑​Pss′a​vπ​(s′)
4. q π ( s , a ) → q π ( s ′ , a ′ ) q_{\pi}\left(s,a\right)\rightarrow q_{\pi}\left(s',a'\right) qπ​(s,a)→qπ​(s′,a′) q π ( s , a ) = R s a + γ ∑ s ′ P s s ′ a [ ∑ a ′ ∈ A π ( s ′ ∣ a ′ ) q π ( s ′ , a ′ ) ] q_{\pi}\left(s,a\right)=R_{s}^{a}+\gamma\sum_{s'}P_{ss'}^{a}\left[\sum_{a'\in A}\pi\left(s'|a'\right)q_{\pi}\left(s',a'\right)\right] qπ​(s,a)=Rsa​+γs′∑​Pss′a​[a′∈A∑​π(s′∣a′)qπ​(s′,a′)]

Q-learning基本原理

Q-Learning算法是一种基于表格的值函数迭代的强化学习算法。这个方法最大的特点就是建立一张Q值表(Q-Table)，算法迭代时Q值表不停地被更新，直至最后表中数据收敛。等到Q值表收敛后，智能体可以根据每个状态的行为值函数的大小来确定最优策略。Q值表示意如下：

智能体在探索时，按照下式的方式来更新Q-Table：
N e w Q ( s , a ) = Q ( s , a ) + α R ( s , a ) + γ max ⁡ a ′ ∈ A Q ( s ′ , a ′ ) − Q ( s , a ) ⏟ Δ Q ( s , a ) NewQ\left(s,a\right)=Q\left(s,a\right)+\alpha\underbrace{R\left(s,a\right)+\gamma\max_{a'\in A}Q\left(s',a'\right)- Q\left(s,a\right)}_{\Delta Q\left(s,a\right)} NewQ(s,a)=Q(s,a)+αΔQ(s,a) R(s,a)+γa′∈Amax​Q(s′,a′)−Q(s,a)​​

下面举一个例子来简单说明Q-Table的更新过程：
例：有一智能体，状态集合为 { 0 , 1 } \left\{0,1\right\} {0,1}，动作集合为 { + , − } \left\{+,-\right\} {+,−}，即时奖励 R ( s , a ) = − 1 R\left(s,a\right)=-1 R(s,a)=−1，折扣因子 γ = 0.8 \gamma=0.8 γ=0.8，学习率 α = 0.1 \alpha=0.1 α=0.1，环境的规则为： 0 → + 1 0\xrightarrow{+}1 0+ ​1， 0 → − 0 0\xrightarrow{-}0 0− ​0， 1 → + 1 1\xrightarrow{+}1 1+ ​1， 1 → − 0 1\xrightarrow{-}0 1− ​0，执行某一动作之后的状态转移概率是1，初始状态是0，初始化Q-Table为：

智能体执行动作 + + +之后， Q ( 0 , + ) Q\left(0,+\right) Q(0,+)会被更新为：
Q ( 0 , + ) = 0.0 + 0.1 × [ − 1 + 0.8 max ⁡ ( Q ( 1 , + ) , Q ( 1 , − ) ) − 0.0 ] = − 0.1 Q\left(0,+\right)=0.0+0.1\times\left[-1+0.8\max\left(Q\left(1,+\right),Q\left(1,-\right)\right)-0.0\right]=-0.1 Q(0,+)=0.0+0.1×[−1+0.8max(Q(1,+),Q(1,−))−0.0]=−0.1
进而Q-Table会被更新为：

注意事项

1. Q-Learning 是一个基于值函数迭代的方式，利用 Q 函数来寻找最优的 Action
2. 为了能够更好地更新 Q 值表，就需要更好地探索环境，因此需要多次执行随机策略以更好地“遍历”整个环境
3. 为了平衡探索与寻优，在经过一定回合的随机探索之后，需要智能体以一定的概率 ϵ 执行“最优”策略，并且 ϵ 应随着学习回合数的增加而增加
4. 算法收敛之后，也可以保持一定概率的探索，以防止陷入局部最优

局限性

Q-Learning算法是有自己的局限性的，主要体现在以下几点：

1. 当Q-Table的规模比较大时，算法迭代收敛时间非常长。
2. 如果智能体探索不充分，很有可能造成算法陷入局部最优。
3. 奖励函数设置如果不合理，很有可能陷入局部最优。
4. Q-Learning无法解决连续状态和连续动作的强化学习问题。

仿真

可以使用网上莫烦Python大神的代码，在OpenAI Gym下做仿真；也可以自己使用图形显示平台自己编写各种简单的仿真环境，然后编写代码测试。我使用的是OpenCV+PyTorch平台，代码一方面稍微有些长（因为还有绘图和调试程序），另一方面网上各种大神的代码，相比之下我的真的是没啥价值，如果有小伙伴想交流，可以私信。贴上一幅图，自己的仿真结果（Low得很…）。
迭代回合数：356
最优路径： [ 0 , 0 ] → [ 1 , 0 ] → [ 2 , 0 ] → [ 3 , 0 ] → [ 4 , 0 ] → [ 4 , 1 ] → [ 5 , 1 ] → [ 6 , 1 ] → [ 6 , 2 ] → [ 6 , 3 ] → [ 6 , 4 ] → [ 6 , 5 ] → [ 6 , 6 ] → [ 7 , 6 ] → [ 7 , 7 ] \left[0,0\right]\rightarrow\left[1,0\right]\rightarrow\left[2,0\right]\rightarrow\left[3,0\right]\rightarrow\left[4,0\right]\rightarrow\left[4,1\right]\rightarrow\left[5,1\right]\rightarrow\left[6,1\right]\rightarrow\left[6,2\right]\rightarrow\left[6,3\right]\rightarrow\left[6,4\right]\rightarrow\left[6,5\right]\rightarrow\left[6,6\right]\rightarrow\left[7,6\right]\rightarrow\left[7,7\right] [0,0]→[1,0]→[2,0]→[3,0]→[4,0]→[4,1]→[5,1]→[6,1]→[6,2]→[6,3]→[6,4]→[6,5]→[6,6]→[7,6]→[7,7]。