Q-learning算法

Q-learning算法的引入

Q-learning算法的步骤与SARSA算法大致相同，唯一不同的地方在于SARSA算法在更新价值函数时会使用\(\epsilon\)-贪婪法，而Q-learning使用的时贪婪法。

Q-learning算法概述

首先基于状态\(S\)，用\(\epsilon\)-贪婪法先择动作\(A\)，然后执行动作\(A\)，得到奖励\(R\)，并进入状态\(S'\)，此时如果是SARSA算法，会继续基于状态\(S'\)使用\(\epsilon\)-贪婪法选择\(A'\)，但是Q-learning不同。

Q-learning基于状态\(S'\)，使用贪婪法选择\(A'\)，也就是说，选择使\(Q(S',a)\)最大的\(a\)作为\(A'\)来更新动作价值函数。数学公式表示如下：

\[ Q(S,A) = Q(S,A) + \alpha(R+\gamma \max_aQ(S',a) - Q(S,A)) \]

此时选择的动作只会用于价值函数的更新，不会真正的执行。价值函数更新后，新的执行动作需要基于\(S'\)使用\(\epsilon\)-贪婪法重新得到。这一点也和SARSA有些不同。SARSA中价值函数更新使用的\(A'\)会作为下一阶段开始i时候的执行动作。

Q-learning算法的流程

算法输入：迭代轮数\(T\)，状态集\(S\)，动作集\(A\)，步长\(\alpha\)，衰减因子\(\gamma\)，探索率\(\epsilon\)

输出：所有的状态和动作对应的价值\(Q\)

1. 随机初始化所有的动作价值\(Q\)，对于终止状态其\(Q\)值为0
2. for i from 1 to T，进行迭代
   1. 初始化\(S\)为当前状态序列的第一个状态
   2. 用\(\epsilon\)-贪婪法在当前状态\(S\)选择出动作\(A\)
   3. 在状态S执行动作\(A\)，得到新状态\(S'\)以及奖励\(R\)
   4. 更新价值函数\(Q(S,A)\)：\(Q(S,A) + \alpha(R+\gamma \max_aQ(S',a) - Q(S,A))\)
   5. \(S = S'\)
   6. 如果\(S'\)是终止状态，当前轮迭代完毕，否则转到步骤2.2

Q-learning算法实现

同样使用Q-learning算法解决了Windy Gridworld的问题，具体代码见我的github。