下面通过一个例子来先容value function approaximation的根本头脑。
假设现在有 ∣ S ∣ |S| ∣S∣个状态，基于给定的策略，每个状态都有一个state value（用下图中的离散点表示，每一个离散点代表状态s对应的state value v(s)）。假如状态s的数量非常多，那么储存就耗费很大空间，因此渴望用一个函数来拟合这些点。
起首，用一个直线来拟合这些点。如下图所示。 w w w里面包含a和b，是parameter vector; ϕ ( s ) \phi(s) ϕ(s)是特性向量。
v π ( s ) v_{\pi}(s) vπ(s)是state value的真实值， v ^ ( s , w ) \hat{v}(s,w) v^(s,w)是state value的近似值。
我们的目标是找到一个最优的 w w w，使得对于每一个状态 s s s， v ^ ( s , w ) \hat{v}(s,w) v^(s,w)都能最好地近似 v π ( s ) v_{\pi}(s) vπ(s)。
为了寻找最优的 w w w，我们定义如下目标函数：
值得指出的是， S S S是一个随机变量，既然是一个随机变量，这个随机变量就是有概率分布的。那么S的概率分布是什么呢？有几种方式来定义S的概率分布。
第一种方式是均匀分布。这种方式下，每一个状态的权重都是一样的，一共有 ∣ S ∣ |S| ∣S∣个状态，那每一个状态的权重就是 1 / ∣ S ∣ 1/|S| 1/∣S∣。但这样的缺点在于，并不是每一个状态都是划一重要，有的状态更重要，我们必要这样的状态权重高一点，盘算的误差小一点。
第二种方式是stationary distribution。在这种方式下，从某一个状态开始，不断地和环境举行交互，交互许多次之后，就达到了一种安稳的状态，在这种安稳的状态下，能够盘算出，每一个状态出现的概率是多少。这个概率分布用 d π ( s ) d_{\pi}(s) dπ(s)来表示，基于 d π ( s ) d_{\pi}(s) dπ(s)可以把目标函数写成如下图所示的形式。 d π ( s ) d_{\pi}(s) dπ(s)实际上饰演了权重的角色。
stationary distribution是状态state 的概率分布，从当前状态出发，跑了许多许多步之后达到的一种安稳的分布。它也被称作steady-state distribbution或者limiting distribution。
下图展示了一个例子。用 n π ( s ) n_{\pi}(s) nπ(s)表示在基于 π \pi π的策略基础上，在一个很长的episode中，访问s的次数。 d π ( s ) d_{\pi}(s) dπ(s)是比值效果，表示状态被访问的概率。右下角的图表示，随着步长越来越长，比值渐渐趋于稳定。
三、原理-优化算法和函数选择
优化算法
用梯度下降方法求解优化目标。下图给出了梯度下降算法，以及盘算了目标函数 J ( w ) J(w) J(w)的梯度。
而这个梯度算出来是有期望的，期望不太好算，以是下面使用随机梯度来代替真实的梯度。
但是这个算法仍然是不好实施的，由于 v π ( s t ) v_{\pi}(s_t) vπ(st)的值是不知道的。可以用其他量来代替 v π ( s t ) v_{\pi}(s_t) vπ(st)。
第一种方法：Monte Carlo的方法。用 g ( t ) g(t) g(t)来代替 v π ( s t ) v_{\pi}(s_t) vπ(st)， g ( t ) g(t) g(t)是在某一个episode中从状态 s t s_t st出发所得到的discounted return。（这个头脑就是和蒙特卡洛方法一致的）
第二种方法：TD learning的方法。把 v π ( s t ) v_{\pi}(s_t) vπ(st)用下式来代替。
函数选择
怎样选择函数 v ^ ( s , w ) \hat{v}(s,w) v^(s,w)呢？
第一种方法，是用线性函数linear function作为 v ^ ( s , w ) \hat{v}(s,w) v^(s,w)。（以前常用）
第二种方法，是用神经网络作为一种非线性函数近似。神经网络的输入是状态state，输出是近似的效果 v ^ ( s , w ) \hat{v}(s,w) v^(s,w)。网络权重是 w w w。（现在常用）
下面看一下线性的环境。假如 v ^ ( s , w ) \hat{v}(s,w) v^(s,w)用线性函数表示，则其梯度为 ϕ ( s ) \phi(s) ϕ(s)，把这个梯度应用到TD算法中，就得到如下图3所示的效果。这也被称作TD-Linear。
Linear function approximation的优劣势：
劣势：很难去选择一个好的feature vector。（好的拟合函数）
上风：相对于非线性函数，线性函数的理论性质能被很好地分析；线性函数的表征能力相对还是比力强的。
四、原理-示例与分析
Sarsa with function approximation
下图是Sarsa和value function approaximation相联合后的算法。和上一节讲到的TD算法相比，就是把 v ^ ( s t ) \hat{v}(s_t) v^(st)换成 q ^ ( s t , a t ) \hat{q}(s_t,a_t) q^(st,at)。这里本质上仍然是在做policy evaluation，action value q ^ = ϕ T w \hat{q}=\phi^Tw q^=ϕTw。
下图是伪代码。起首在当前状态 s t s_t st的环境下遵循策略选择动作 a t a_t at，产生 r t + 1 r_{t+1} rt+1和 s t + 1 s_{t+1} st+1，然后在新的状态下遵循策略选择新的动作 a t + 1 a_{t+1} at+1。然后举行value update 过程，对参数w举行更新，这里本质上仍然是在做policy evaluation。再举行policy update过程，这里接纳的是 ϵ \epsilon ϵ-greedy的方法。
下图展示了将Sarsa和linear function approximation联合的例子。使命是从某一状态出发，到达目标状态。
Q-learning with function approximation
算法如下：
这是Q-learning with function approximation（on policy）版本的伪代码。
下图展示了将Q-learning和linear function approximation联合的例子。使命是从某一状态出发，到达目标状态。
六、Deep Q-learning (DQN) 根本原理
DQN把深度神经网络引入到强化学习中。下图的 J ( w ) J(w) J(w)展示了DQN的目标函数/损失函数。假如达到最优的话，loss function应该是即是0。
设计两个网络，在main network中，参数是w，w是一直被更新的，有新的采样进来的时候，就会被更新。但在target network中，参数是 w T w_T wT，这个参数不是一直被更新的，隔一段时间之后，会把main network中的参数w的值给赋值过来。末了， w w w和 w T w_T wT都能收敛到最优的值。
以是它的梯度公式最终是写成这样的：
值得强调的是，DQN使用了两个网络，main network和target network，其参数分别是 w w w和 w T w_T wT。在每次迭代中，从replay buffer中提取一些sample，使得输出的效果尽量接近 y T y_T yT。训练一段时间后，参数 w w w的值变化了，把这个值赋给 w T w_T wT， w T w_T wT再用来训练这个 w w w。
七、Deep Q-learning (DQN) Experience replay（履历回放）
什么是履历回放？
在收集数据experience samples的时候，是有肯定的先后次序的，但是在使用数据的时候，并不肯定要遵循这个次序。我们把这些数据存到一个 B B B聚会集（从状态s出发，接纳action a，得到reward r，跳转到下一个状态s’），这个聚集的名字叫replay buffer。
每次训练神经网络的时候，从这个replay buffer中抽取一些mini-batch的随机样本。这些样本的抽取叫做experience replay，这必要遵循均匀分布。
为什么要履历回放？
为什么要在deep Q-learning中使用experience replay？为什么这个replay必须遵循均匀分布呢？
把 ( S , A ) (S,A) (S,A)当成一个索引，将其当成一个随机变量。给定 ( S , A ) (S,A) (S,A)后， R R R和 S ′ S' S′都服从体系的模子。假设 ( S , A ) (S,A) (S,A)服从均匀分布（由于我们没有先验知识，无法判断哪些 ( s , a ) (s,a) (s,a)重要，哪些不重要，以是我们只能让它服从均匀分布）。
初始的策略 π b \pi_b πb产生了许多sample，这些sample被存在聚集 B B B中。下面在每一个iteration中，起首从聚集 B B B中举行随机的采样，然后对采样举行进一步的处理，盘算 y T y_T yT（渴望近似值 q ^ \hat{q} q^尽可能地接近 y T y_T yT）。然后把 ( s , a , y T ) (s,a,y_T) (s,a,yT)送入到神经网络中举行训练。每颠末C次迭代，就把 w w w赋值给 w T w_T wT。
例子：
使命是对所有的state action pair，去找到其optimal action value。一些具体的设置如下图所示。必要留意的是，这里设计的神经网络很简单，只有三层：隐藏层、输入层、输出层，隐藏层只有100个神经元。
