价值函数的近似表示
之前介绍的强化学习方法使用的都是有限个状态集合\(S\)，而当遇到连续的状态时，则需要价值函数的近似表示。
价值函数的近似表示方法
价值函数的近似表示拥有几种方法。一是引入一个状态价值函数\(\hat{v}\)，这个函数由参数\(w\)表示，并接受状态\(s\)作为输入，计算后得到状态\(s\)的价值。即:
\[ \hat{v}(s, w) \approx v_{\pi}(s) \]
类似的，引入一个动作价值函数\(\hat{q}\)，这个函数由参数\(w\)表示，并接受状态\(s\)与动作\(a\)作为输入，计算后得到动作价值。即：
\[ \hat{q}(s,a,w) \approx q_{\pi}(s,a) \]
价值函数的近似表示通常使用神经网络。神经网络的使用主要有以下三种情况。
对于状态价值函数， 神经网络的输入是状态\(s\)的特征向量，输出是状态价值\(\hat{v}(s, w)\)。对于动作价值函数，有两种方法，一种是输入状态\(s\)的特征向量和动作\(a\)，输出对应的动作价值\(\hat{q}(s,a,w)\)，另一种是只输入状态\(s\)的特征向量，动作集合有多少个动作就有多少个输出\(\hat{q}(s,a_i,w)\)。这里隐含了我们的动作是有限个的离散动作。
Deep Q-Learning算法思路
Deep Q-Learning算法的基本思路来源于Q-learning。 但是和Q-Learning不同的地方在于，它的Q值的计算不是直接通过状态值\(s\)和动作来计算，而是通过上面讲到的Q网络来计算的。这个Q网络是一个神经网络，我们一般简称Deep Q-Learning为DQN。
DQN的输入是状态s对应的状态向量\(\phi(s)\)， 输出是所有动作在该状态下的动作价值函数Q。Q网络可以是DNN，CNN或者RNN，没有具体的网络结构要求。
DQN主要使用的技巧是经验回放（experience replay）,即将每次和环境交互得到的奖励与状态更新情况都保存起来，用于后面目标Q值的更新。
通过经验回放得到的目标Q值和通过Q网络计算得到的Q值存在误差时，可以通过梯度反向传播来更新神经网络的参数\(w\)直到当\(w\)收敛。
算法输入：迭代轮数\(T\)，状态特征维度\(n\)，动作集\(A\)，步长\(\alpha\)，衰减因子\(\gamma\)，探索率\(\epsilon\)，Q网络结构，批量梯度下降的样本数\(m\)。
输出：Q网络参数
随机初始化Q网络的所有参数\(w\)， 基于\(w\)初始化所有的状态和动作对应的价值\(Q\)。清空经验回放的集合\(D\)。
for i from 1 to T，进行迭代。
初始化S为当前状态序列的第一个状态, 拿到其特征向量\(\phi(S)\)
在Q网络中使用\(\phi(S)\)作为输入，得到Q网络的所有动作对应的Q值输出。用ϵ−贪婪法在当前Q值输出中选择对应的动作A
在状态\(S\)执行当前动作\(A\),得到新状态\(S'\)对应的特征向量\(\phi(S')\)和奖励\(R\),是否终止状态is_end
将\(\{\phi(S),A,R,\phi(S'),is\_end\}\)这个五元组存入经验回放集合\(D\)
\[S=S'\]
从经验回放集合\(D\)中采样\(m\)个样本\(\{\phi(S_j),A_j,R_j,\phi(S'_j),is\_end_j\}, j=1,2.,,,m\)，计算当前Q值\(y_j\)：
\[ y_j= \begin{cases} R_j& {is\_end_j\; is \;true}\\ R_j + \gamma\max_{a'}Q(\phi(S'_j),A'_j,w) & {is\_end_j \;is\; false} \end{cases} \]
7.使用均方差损失函数,通过神经网络的梯度反向传播来更新Q网络的所有参数\(w\)
\[ \frac{1}{m}\sum\limits_{j=1}^m(y_j-Q(\phi(S_j),A_j,w))^2 \]
8.如果\(S'\)是终止状态，当前轮迭代完毕，否则转到步骤2.2
上述2.6以及2.7步骤中的Q值计算都要通过Q网络计算得到。实际应用中为了算法更好的收敛探索率需要随着迭代的进行而减小。
Deep Q-Learning算法实现
下面使用OpenAi Gym中的CartPole-v0游戏来作为算法实现的游戏。具体算法请参照我的github。