强化学习2
https://www.bilibili.com/video/BV1sd4y167NS
随机近似和随机梯度下降
随机近似理论
在很多实际问题中，动作并不总是确定性地导致一个确定的结果。比如，在强化学习的状态转移模型中，给定某个状态 sss 和动作 aaa，环境可能以一定的概率转移到多个不同的状态，得到不同的奖励。
重温均值估计问题，对于变量x我们估计期望$\mathbb E$，假设我们手机了独立同分布样本$\{x_i\}^N_{i=1}$
$$ \mathbb{E}[X]\approx\bar{x}:=\frac1N\sum_{i=1}^Nx_i $$
那么如何来计算$\bar{x}$呢。
第一种方式就是相加除以N，它的缺点是需要等到所有的数据收集完毕再求平均。（收集多少算多少，收集完了算完了。）
第二种方法避免了这个缺点，因为它使用了增量和迭代的方式。就是来几个计算几个。
假设
$$w_{k+1}=\frac{1}{k}\sum_{i=1}^{k}x_{i},\quad k=1,2,\ldots $$
因此
$$w_k=\frac{1}{k-1}\sum_{i=1}^{k-1}x_i,\quad k=2,3,\ldots $$
我们可以用 $w_k$ 来表示 $w_{k+1}$
$$\begin{aligned}w_{k+1}=\frac1k\sum_{i=1}^kx_i&=\frac1k\left(\sum_{i=1}^{k-1}x_i+x_k\right)\\&=\frac1k((k-1)w_k+x_k)=w_k-\frac1k(w_k-x_k).\end{aligned}$$
因此我们得到了如下的迭代公式
$$w_{k+1}=w_{k}-\frac{1}{k}(w_{k}-x_{k}).$$
假如在上个时刻计算出$w_k$，那么在新的时刻我们只需要$x_k$就能得到$w_{k+1}$
我们可以这样进行增量计算
$$ \begin{aligned} w_{1}& =x_{1}, \\ w_{2}& =w_1-\frac{1}{1}(w_1-x_1)=x_1, \\ w& _{3}=w_{2}-\frac{1}{2}(w_{2}-x_{2})=x_{1}-\frac{1}{2}(x_{1}-x_{2})=\frac{1}{2}(x_{1}+x_{2}), \\ w_{4}& =w_3-\frac{1}{3}(w_3-x_3)=\frac{1}{3}(x_1+x_2+x_3), \\ &\text{:} \\ w_{k+1}& =\frac{1}{k}\sum_{i=1}^{k}x_{i}. \end{aligned} $$
我们最终的公式就是,它是一种增量的计算思想。
$$ w_{k+1}=w_{k}-\frac{1}{k}(w_{k}-x_{k}) $$
这个算法可以进一步的推广
$$ w_{k+1}=w_{k}-\alpha_k(w_{k}-x_{k}) $$
如果取的是$\alpha$那么这个算法还能回去到$\mathbb E$吗
这个算法也是一个特殊的随机近似算法同时也是一个特殊的随机梯度下降算法。
robbins monro
stochastic approximation（SA 随机近似）
SA代表了一类广泛的随机迭代算法（stochastic iterative algorithm），它被用来求跟或者优化问题。
对比一些其他的球根算法，比如基于梯度下降的算法，SA的强大之处在于它不需要知道方程或者目标函数的表达式，自然也不需要知道倒数或者梯度的表达式。
robbins monro算法检测RM算法
- 它是随机近似领域的一项开创性工作。
- 我们常用的随机梯度下降算法是一种RM算法的特殊形式。
- mean estimation也是一种特殊的RM算法
问题是我们需要求解一个方程，其中w是求解的未知量，g是一个函数
$$ g(w)=0 $$
一般来说，我们会希望这个函数的梯度为0。梯度为0是函数$J(w)$达到最小的一个必要不充分条件。
$$ g(w)=\nabla_wJ(w)=0 $$
右边也有可能是一个常数，这时候可以把常数项移动过来作为一个新的函数。
如何求解g(w)=0呢？
如果g的表达式是已知的，那么有许多方式去求解这个函数。
但是如果g的表达式是未知的怎么办呢？
rm算法是一个迭代式的算法。可以解决这个问题。
$$ w_{k+1}=w_k-a_k\tilde{g}(w_k,\eta_k),\quad k=1,2,3,\ldots $$
- k表示对w第k次的估计。
- $a_k$是一个正系数
- $\tilde{g}(w_k,\eta_k)=g(w_k)+\eta_k$是第$\eta_k$是噪音$\tilde{g}(w_k,\eta_k)$是一个对于$g(w_k)$带噪音的观测
那么现在这个g(w)就是一个黑盒。这个算法是依赖于数据的。w先进入g计算再添加一个噪音，最后输出。
因此这个算法依赖于$\{w_k\}$和噪声输出序列$\tilde{g}(w_k,\eta_k)$。
这是一种哲学的思想，当没有模型的时候就用数据。这里的模型指的就是函数的表达式。
例子
假设我们有一个未知的函数
$$ g(w)=\tanh(w-1) $$
因此该函数在w=1的时候为0
22初始参数$w_1=3,a_k=1/k,\eta_k=0$（简单起见不计算噪声）
这里会计算出$g(w_1)$也就是图中的菱形。其中$w^*$是最优解。也就是x=0；
图中我们可以看到$w_{k+1}$明显要更接近于$w^*$
当$w_k>w*$，那么$g(w_k)>0$：$w_{k+1}=w_k-a_kg(w_k)<w_k$
当$w_k<w^*$，那么我们有$g(w_k)<0$：$w_{k+1}=w_k-a_kg(w_k)>w_k$
这里要求$0<c_1\leq\nabla_wg(w)\leq c_2$也就是说一条曲线的导数是正数，而且这个梯度不能是无限的。
二阶导为正数才是一个凸函数。
可微的凸函数的导数是单调递增的。
对于$\eta_k$我们要求它均值为0，变量是有界的。我们可以从一个概率分布中iid的去采样。
所以要求g是单调递增的（monotonically increasing）。这时候它的解是存在的并且是唯一的。
- 还有$a_k^2$和小于无穷：意味着$a_k$会收敛到0
- 此外我们需要$a_k$的合小于无穷： 但是收敛速度不能太快
什么样的$\{a_k\}$能满足这俩个条件？
$$ a_k=\frac{1}{k} $$
我们可以由这个公式推导
$$ \operatorname*{lim}_{n\to\infty} \left(\sum_{k=1}^{n}\frac{1}{k}-\ln n\right)=\kappa, $$
此外
$$ \sum_{k=1}^\infty\frac1{k^2}=\frac{\pi^2}6<\infty. $$
所以1/k能够很好的满足以上两个条件。
举个例子$g(w)=w^3-5$。不满足第一个条件。因为当w趋向于无穷的时候，它也会趋向于无穷。
一般来说我们会让$a_k$足够小。来更好的接收新的值。
我们将rm算法用回均值估计中。
它是一个rm算法的特殊例子(当$\alpha_k$满足上面俩个条件的时候)
$$ w_{k+1}=w_k+\alpha_k(x_k-w_k). $$
随机梯度下降
略
时序差分
TD算法
TD算法用来求解给定策略$\pi$的state value
TD算法是一个类广泛的算法，这里讲的是最经典的TD算法。TD算法是基于数据来实现强化学习。
数据的表达形式如下,策略是根据给定的$\pi$来生成的
$$ \{(s_t,r_{t+1},s_{t+1})\}_t $$
TD算法是需要用这些数据来估计$\pi$对应的state value
v(s)是state space中的任何一个状态，这个v是用来近似$v_\pi(s)$。t代表的是时刻为t时。$s_t$是t时刻访问到的
算法包含俩部分
$$ v_{t+1}(s_t)=v_t(s_t)-\alpha_t(s_t)\Big[v_t(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})]\Big],\quad(1)\\v_{t+1}(s)=v_t(s),\quad\forall s\neq s_t,\quad(2) $$
也就是说没被当前访问到的就都不变。
我们将第一个算法加一些标注（第二个算法在品势表示的时候被隐藏掉）
$$ \underbrace{v_{t+1}(s_t)}_{\text{new estimate}}=\underbrace{v_t(s_t)}_{\text{current estimate}}-\alpha_t(s_t)\Big[\overbrace{v_t(s_t)-[\underbrace{r_{t+1}+\gamma v_t(s_{t+1})}_{\text{TD target }\bar{v}_t}]}^{\text{TD error }\delta_t}\Big], $$
其中的$\alpha_t(s_t)$是针对于$s_t$计算的一个系数。可以把右边的整体看做修正项。新的估计为旧的估计加上一个修正项来得到的。
TD target 定义为当前得到的即时奖励和下一状态的折扣后的估计值之和：
其中，这里的目标是让$v_t$更加接近 TD target,也就是$\bar v_t$
$$ \bar{v}_t\doteq r_{t+1}+\gamma v(s_{t+1}) $$
w最里面的是TD target，作用是希望$v_t$朝自己的方向进行修改。更加接近target也就是说这是目标。
现在的value和target之间有一个误差。这个误差被称为TD error
先来看TD target ，为什么$\bar v_t$叫做目标函数呢？所以上式就等于如下
$$ \begin{aligned} &&&v_{t+1}(s_{t})=v_{t}(s_{t})-\alpha_{t}(s_{t})\big[v_{t}(s_{t})-\bar{v}_{t}\big] \\ &\Rightarrow && v_{t+1}(s_t)-\bar{v}_t=v_t(s_t)-\bar{v}_t-\alpha_t(s_t)\big[v_t(s_t)-\bar{v}_t\big] \\ &\Rightarrow && v_{t+1}(s_{t})-\bar{v}_{t}=[1-\alpha_{t}(s_{t})][v_{t}(s_{t})-\bar{v}_{t}] \\ &\Rightarrow && |v_{t+1}(s_t)-\bar{v}_t|=|1-\alpha_t(s_t)||v_t(s_t)-\bar{v}_t| \end{aligned} $$
因为这里的$\alpha_t$是一个比较小的正数
$$ 0<1-\alpha_t(s_t)<1 $$
因此我们得到了
$$ |v_{t+1}(s_t)-\bar{v}_t|\leq|v_t(s_t)-\bar{v}_t| $$
这意味着在下一个时刻$v(s_t)$离$\bar v_t$更近了。因此这是一种改进。
如何理解TD error呢？现在的value和target之间有误差
$$ \delta_t=v(s_t)-[r_{t+1}+\gamma v(s_{t+1})]=v(s_t)-\bar v_t $$
可以看到左边在t时刻，右边在t+1的时刻。所以它被称为时序差分。
TD error描述了$v_t$和$v_\pi$之间的误差。因为当$v_t$和$v_\pi$差为0的时候$\delta_t$也为0。
我们将其进行替换。将v替换成$v_\pi$，因为我们希望v能收敛到$v_\pi$
$$ \delta_{\pi,t}\doteq v_\pi(s_t)-[r_{t+1}+\gamma v_\pi(s_{t+1})] $$
TD error是一个新的信息。我们对$v_\pi$做估计之后，这个估计可能是不准确的，然后得到新的experience，我们联系这俩个估计。对原有估计的偏差进行修正。
TD算法做的事情就是给定策略估计state value 也就是policy evaluation
它并不能估计action value也不能搜索最优的策略
TD算法在数学上其实在求解贝尔曼公式。它是在没有模型的情况下求解贝尔曼公式。
我们这里要引入一个新的贝尔曼公式
$$ v_\pi(s)=\mathbb{E}\big[R+\gamma G|S=s\big],\quad s\in\mathcal{S} $$
这个期望可以写成分别对R和对G求期望。我们可以把其中对G求期望的部分单独写出来为
$$ \mathbb{E}[G|S=s]=\sum_a\pi(a|s)\sum_{s'}p(s'|s,a)v_\pi(s')=\mathbb{E}[v_\pi(S')|S=s], $$
也就是说等价为跳到下一个状态，然后对下一个状态求期望。
因此上面的公式可以写成这样的形式
$$ v_\pi(s)=\mathbb{E}\big[R+\gamma v_\pi(S')|S=s\big],\quad s\in\mathcal{S}. $$
这个也被叫做贝尔曼期望公式。
我们可以使用RM算法求解这个公式。
$$ g(w)=g(v(s))=v(s)-\mathbb{E}\big[R+\gamma v_{\pi}(S')|s\big]=0, $$
我们可以通过采样r，s',S'来求解这个公式
$$ \begin{aligned} \tilde{g}(v(s))& =v(s)-\begin{bmatrix}r+\gamma v_{\pi}(s')\end{bmatrix} \\ &=\underbrace{\left(v(s)-\mathbb{E}\big[R+\gamma v_\pi(S')|s\big]\right)}_{g(v(s))}+\underbrace{\left(\mathbb{E}\big[R+\gamma v_\pi(S')|s\big]-\big[r+\gamma v_\pi(s')\big]\right)}_{\eta} \end{aligned} $$
我们带入之后发现和TD算法非常类似，右边是测量误差。公式中k表示的是第k次迭代时的状态。
$$ \begin{aligned} v_{k+1}(s)& \begin{aligned}=v_k(s)-\alpha_k\tilde{g}(v_k(s))\end{aligned} \\ &=v_{k}(s)-\alpha_{k}\Big(v_{k}(s)-\big[r_{k}+\gamma v_{\pi}(s_{k}')\big]\Big),\quad k=1,2,3,\dots \end{aligned} $$
它和TD算法公式十分类似。但是有俩个不同
- 我们要反复得到r和s'的采样。反复从s出发得到r和s'
- 我们还要假设对于一直的任何s'都知道$v_\pi(s')$
为了解决这俩个问题我们
- 将{(s,r,s')}替换成$\{(s_t,r_{t+1},s_{t+1})\}$，因此算法可以利用eposode中的序列样本
- 对于我们不知道$v_\pi(s')$我们可以把他替换成$v_k(s'k)$
对比
TD（Temporal Difference）算法和MC（Monte Carlo）学习是强化学习中用于估计状态价值的两种方法，它们的主要区别在于更新方式和样本效率：
TD算法：
- TD算法是在线的，在接收到reward之后，它可以立即用这些信息来更新state value和action value。
- 因此它能处理连续的任务和episodic任务
- bootstraping的，需要基于初始值进行猜测然后加上新的信息进行猜测。
- TD算法估计的变量是比较少的。
MC learning：
- 它是离线的，得到采样之后必须等收集完毕才能进行更新。
- 它只能在停止之后才能进行计算。
- Non-bootstraping，直接根据当前eposode进行估计
- MC估计的变量会非常多。
sarsa
TD算法只能估计状态值。现在我们介绍sarra算法它可以直接估计action value。它们的形式非常类似。它做的事情也是policy evaluation
因为没有模型，我们需要数据，假设有这样的数据$\{(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})\}_t$
我们可以用这个算法进行更新
$$ \begin{aligned}q_{t+1}(s_t,a_t)&=q_t(s_t,a_t)-\alpha_t(s_t,a_t)\Big[q_t(s_t,a_t)-[r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})]\Big],\\q_{t+1}(s,a)&=q_t(s,a),\quad\forall(s,a)\neq(s_t,a_t),\end{aligned} $$
其中$q(s,a)$是$q_pi(s,a)$的估计值。$q_t$就是在t时刻的估计值。这和我们刚才介绍的TD算法是一模一样的。
除了其中的$v(s_t)$变成了$q(s_t)$。之前是对状态s求他的$v_\pi(s)$。现在是对每一个(s,a)求他的$q_\pi(s,a)$
为什么它叫sarsa算法呢。它是state-action-reward-state-action的缩写。因此sarsa就是action-value版本的TD算法。sarsa求解的贝尔曼公式为
$$ q_\pi(s,a)=\mathbb{E}\left[R+\gamma q_\pi(S^{\prime},A^{\prime})|s,a\right],\quad\forall s,a. $$
它是基于action value 对贝尔曼公式进行表达。它的终极目标是找到一个优化策略
为此我们将sarsa和policy improvement step进行结合。结合之后的算法依然叫做sarsa。
整体的流程
- 如果当前的状态不是targetstate就开始执行代码
- 在t时刻我们得到一个experience$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$
- 基于这个experience我们做一次q-value的更新（计算$\pi_t(s_{t+1})$）
- 然后进行一次策略更新（选一个最大的q-value）
- 循环往复
在更新$q(s_t,a_t)$之后会立即进行策略的更新。它是基于广义策略迭代想法。
使用了$\epsilon$-greedy策略进行更新，访问到尽可能多的sa。
左图展示了最终sarsa的策略
有图是总reward和每个episode的长度。有图的横坐标是episode的数量。纵坐标是每个episode的总reward。右下的图片是episode length。代表需要走多少步。
Q-learning
简介
Q-learning是直接估计optimal action value。因此它不需要去左policy evaluation和policy improvement之间进行交替。
首先是q-learning的公式，第二部分是一样的
$$ \begin{aligned} q_{t+1}(s_t,a_t)& =q_t(s_t,a_t)-\alpha_t(s_t,a_t)\left[q_t(s_t,a_t)-[r_{t+1}+\gamma\max_{a\in\mathcal{A}}q_t(s_{t+1},a)]\right], \\ q_{t+1}(s,a)& =q_t(s,a),\quad\forall(s,a)\neq(s_t,a_t), \end{aligned} $$
对当前访问的$s_t,a_t$需要更新q。从结构上来讲和sarsa很相似。唯一不同的就是TD target的发生了变换。
Q-learning中的TD target是$r_{t+1}+\gamma\max_{a\in\mathcal{A}}q_t(s_{t+1},a)$
而sarsa中的TD target是$r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})$
Q-learning在数学上解决什么问题呢？
它是在求解贝尔曼最优方程
$$ q(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a} q(S_{t+1}, a) \mid S_t = s, A_t = a \right], \quad \forall s, a. $$
这个和之前介绍的贝尔曼最优方程不一样。它有期望，而且是不是基于state value 而是基于action value。
Q-learning有俩个重要的性质，一个是on-policy learning一个是off-policy learning
on-policy和off-policy
行为策略：行为策略是智能体在智能体环境中执行的策略。用于生成经验数据，决定在特定状态下采取哪个动作
目标策略：目标策略是智能体希望优化的策略。它是通过学习行为策略产生的经验数据来更新的策略。
on-policy和off-policy：它们的主要区别在于智能体在更新策略时，是否使用当前策略来进行学习。
强化学习中存在俩个策略一个是
- behavior policy：和环境进行交互生成期望采样。
- target policy：不间断的向前更新并优化策略。
基于俩者我们可以定义俩个算法
- on-policy learning： behavior 策略和target策略是相同的。用这个策略和环境进行交互，交互之后再次改进这个策略。
- off-policy learning：当它们不同的时候就叫做off-policy。用 一个策略和环境进行交互得到大量的经验。然后用这些经验对这个策略进行改进。
sarsa是on-policy策略，而q-learning是off-policy。也就是说q-learning的behavior 策略和target策略是可以不同的。
那么不同有什么好处吗？
我们可以通过其他的策略来基于经验采样来生成优化策略：这样的话behavior策略可以是一个探索性的策略。可以探索所有的state-action pair。基于探索结果对state-action pair的action value。
那么如果有一个强化学习算法如何判断它是on-policy和off-policy？
- 首先看数学上解决的是什么问题。
- 然后看这个算法的视线需要哪些东西。
首先来看sarsa
$$ q_{t+1}(s_t,a_t)&=q_t(s_t,a_t)-\alpha_t(s_t,a_t)\Big[q_t(s_t,a_t)-[r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})]\Big]\\ $$
其中我们需要$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$
如果$(s_t,a_t)$给定了，那么$r_{t+1}和s_{t+1}$和任何策略都没有关系（因为它是由$p(r|s,a),p(s'|s,a)$来决定的，但是我们不知道所以进行采样。）
但其中的$a_{t+1}$是基于$\pi_t(s_{t+1})$。这里的$\pi_t$就是behavior policy同时也是target policy。
整个流程是，初始化$\pi_t$然后用它生成期望，用期望估计$q_{\pi_t}$也就是估计action value。然后再进行改进。所以sarsa是on-policy
在来看看monte carlo
$$ q_\pi(s,a)=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\ldots|S_t=s,A_t=a\right],\quad\forall s,a. $$
先用$\pi$生成期望或者trajectory。然后用它的return来近似估计$q_\pi$。然后用这个$\pi$来改进$q_\pi$。所以它是on-policy
最后是q-learning它是off-policy的
$$ q(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a} q(S_{t+1}, a) \mid S_t = s, A_t = a \right], \quad \forall s, a. $$
贝尔曼公式需要给定一个策略，然后通过贝尔曼公式求出来对应的action value或者state value。但是贝尔曼最优公式不涉及任何策略。所以我们看的是实现它需要什么样的测量。
为了实现q-learning我们需要$(s_t,a_t,r_{t+1},s_{t+1})$
集中如果$(s_t,a_t)$是给定的，那么$r_{t+1},s_{t+1}$不依赖任何策略。
q-learning中的behavior policy是从$s_t$出发，得到$a_t$。而target策略是$q_t$
但是q-learning也可以是off-policy的。
例子
q-learning无论是on-policy还是off-policy，采样数据的时候都是$\epsilon$-greedy算法。但是生成策略的时候off-policy采用的是greedy算法。因为它的行为和目标策略是不统一的。
target和behavior理论上他们也可以是相同的，相同是是不同的一种特殊情况。
让他们强行一致就得到了on-policy的策略。它和sarsa是非常相似的。
我们来看off-policy的版本。我们有一个策略叫做$\pi_b$，它生成了$\{s_0,a_0,r_1,s_1,a_1,r_2\}$
从t=0,1,2,3开始遍历
更新q-value：这一部和on-policy是一样的
$\begin{aligned}&q_{t+1}(s_{t},a_{t}) = q_{t}(s_{t},a_{t}) - \alpha_{t}(s_{t},a_{t})\Big[q(s_{t},a_{t}) - [r_{t+1} +\gamma\max_{a}q_{t}(s_{t+1},a)]\Big]\end{aligned}$
更新目标策略:这时候它是greedy而不是$\epsilon$-greedy
$\begin{aligned}&\pi_{T,t+1}(a|s_{t})=1\text{ if }a=\arg\max_aq_{t+1}(s_t,a)\\&\pi_{T,t+1}(a|s_{t})=0\text{ otherwise}\end{aligned}$
那么这里为什么是$\epsilon$-greedy而不是greedy呢？greedy只利用不探索，而$\epsilon$-greedy加入了一些随机探索。但是现在生成的策略不会用来生成数据。因为生成数据是$\pi_T$的事情。所以我们直接得到最优的策略。
我们来看具体的例子：
它的目标是要找到所有状态的最优策略。上面的sarsa只是知道固定路径的最优策略。
首先我们选定一个behavior policy。然后用它来产生数据。它是一个均匀采样的策略。五个动作每个动作的概率是0.2。策略是off-policy的qlearning！
右下角的图片是我们知道所有格子最优的state value然后算差再求模。
这是一个探索性没那么强的策略。
值函数近似
曲线拟合
之前介绍的temporal difference learning是基于表格的。这节将会介绍基于函数的。
之前的$q_\pi(s,a)$我们是用表格进行模拟的。类似这样
它直观易于分析。但是很难处理非常大的连续的action space。
我们可以考虑s和v的一个坐标轴。我们可以用直线、曲线来拟合这些点。
$$ \hat{v}(s, w) = as + b = \begin{bmatrix} s & 1 \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \phi^T(s) w $$
我们可以把as+b的形式写成俩个向量相乘，第一个向量包含s，第二个向量包含w。这俩个向量相乘还是sa+b
其中w是parameter vector
$\phi(s)$是特征向量（feature vector）
$\hat{v}(s,w)$和w是线性的关系
用直线拟合之后我们只需要存储a和b俩个参数。但是直线拟合的代价就是state value的表示不是那么准确。所以它是值近似。
那么我们可以考虑用曲线拟合
曲线的表达式是，
$$ \hat{v}(s, w) = as^2 + bs + c = [s^2, s, 1] \underbrace{\begin{bmatrix} a \\ b \\ c \end{bmatrix}}_{w} = \phi^T(s) w. $$
在这种情况下它的维度数量增加了，要存储更多的值，但是拟合的精度提高了
它对于s是非线性的函数，对于w是线性的函数。
我们可以继续增加曲线的阶数，以更准确的拟合这些点。但这会带来更多的参数。
核心思想是让他近似$\hat{v}(s,w)\approx v_\pi(s)$.
这样的话我们访问一部分就可以对整条曲线进行更新。
其中$v_\pi(s),\hat v(s,w)$分别是真值和估计值。我们要做的就是找最优的w，让他最接近$v_\pi(s)$。
为了找到最优的w，我们需要俩步
- 第一步是定义目标函数
- 第二部是优化目标函数
目标函数
我们先看目标函数如下
$$ J(w) = \mathbb{E}\left[\left(v_\pi(S) - \hat{v}(S, w)\right)^2\right]. $$
我们的目标是找到w优化这个函数。其中的s是一个随机变量，它一定是有概率分布的
我们先来看uniform distribution（均匀分布）
它的意思是把所有的状态视为同等重要的。每个人求平均时候的权重都是一样的。
$$ J(w)=\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))^2]=\frac{1}{|\mathcal{S}|}\sum_{s\in\mathcal{S}}(v_\pi(s)-\hat{v}(s,w))^2. $$
这样我们就得到了右边的公式。也就是所有的状态的误差的平方然后再求平均。
它的缺点是，所有的状态在很多情况下并不是同等重要的。比如从目标点出发，接近目标的状态应该是更加重要的。
因此第二种方法就是stationary distribution（平稳分布）
它是一个很重要的概念，之后会频繁用到。它描述了马尔科夫过程的long-run behavior（长期行为）。指的是一个系统或算法在经过足够长时间后的表现或特征。它通常描述系统的稳态行为或收敛结果，也就是说，当时间趋近于无穷大时，系统所达到的状态或表现。
我们使用$\{d_\pi(s)\}$来表示，因为是概率分布所以$d_\pi(s)\geq0\text{ and }\sum_{s\in\mathcal{S}}d_\pi(s)=1.$
在这样的情况下我们得到了
$$ J(w)=\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))^2]=\sum_{s\in\mathcal{S}}d_\pi(s)(v_\pi(s)-\hat{v}(s,w))^2. $$
其中的$d_\pi(s)$代表的是权重。某个状态的权重比较大，它估计的误差将会更小一些。
现在介绍一下stationary distribution
- 它是一个状态分布，可以理解为是状态的权重
- 并且是平稳状态下的分布：在agent 根据策略运行了很长的时间之后，在agent在任何状态下的概率可以被描述为一个分布。
- 它也被叫做steady-state distribution或者limiting distribution
- 它在value function approximation和策略梯度方法中扮演了很重要的角色
假设我们有一个策略。产生了episode，$n_\pi(s)$表示s通过$\pi$访问非常长的episode生成的次数
其中比值可以用如下图来描述
图中横坐标是episode的步长，纵坐标是被访问的比值。可以看到每个坐标被访问的概率是不一样的。但最后趋向于平稳。他们最后会收敛到具体的值。蓝色的方块就是s4。图中可以看到我们不需要跑很多次就能找到$d_\pi(s)$
其中他满足
$$ d^T_\pi=d_\pi^TP_\pi $$
在个P是状态转移矩阵。这个P就是贝尔曼公式中的P代表的是$p(s'|s)$的转移概率。因此我们可以手动进行计算。
优化算法和函数
我们已经有了目标函数下一步是如何优化这个目标函数。
为了最小化目标函数J(w)我们可以使用梯度下降算法。
$$ w_{k+1}=w_k-\alpha_k\nabla_wJ(w_k) $$
其中$w_k$表示k次迭代的值，$a_k$是学习率，$\nabla_wJ(w_k)$是目标函数$j(w)$对w求梯度的值。梯度指示了目标函数在该点的变化方向和速率。
我们将公式带入其中得到了
$$ \begin{aligned} \nabla_{w}J(w)& \begin{aligned}=\nabla_w\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))^2]\end{aligned} \\ &=\mathbb{E}[\nabla_w(v_\pi(S)-\hat{v}(S,w))^2] \\ & =2\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))(-\nabla_w\hat{v}(S,w))] \\ &=-2\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))\nabla_w\hat{v}(S,w)] \end{aligned} $$
这样我们就得到了真实的梯度，但是这个true gradient 需要计算一个期望，因此我们用随机梯度下降来替代true gradient
$$ w_{t+1}=w_t+\alpha_t(v_\pi(s_t)-\hat{v}(s_t,w_t))\nabla_w\hat{v}(s_t,w_t), $$
其中$s_t$是S的采样。但是这个算法十几种不能使用，因为我们无法知道$v_\pi(s_t)$
我们可以用蒙特卡洛学习来进行函数的近似。我们用$g_t$也就是discounted return 来替代$v_\pi(s_t)$
$$ w_{t+1}=w_t+\alpha_t(g_t(s_t)-\hat{v}(s_t,w_t))\nabla_w\hat{v}(s_t,w_t), $$
然后使用TD learning进行函数近似。
$$ w_{t+1}=w_t+\alpha_t\left[r_{t+1}+\gamma\hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)\right]\nabla_w\hat{v}(s_t,w_t). $$
实际实现就是
对一个episode中的每一步进行采样，然后使用采样结合上面的公式对w进行更新。
目前的优化算法是在估计给定策略的state value。
那么我们如何选举feature fector呢？，我们可以用polynomial basis， fourier basis等。另外一种方式是使用神经网络来猜测这个函数。
此外如果是线性的情况
这个算法叫做TD learning。其实表格的表示是linear function的一种特例。
例子
我们仍然考虑grid-ward例子，这里是5x5的表格一共25个状态。
我们给定策略$\pi(a|s)=0.2$。我们要估计每一个状态的state value。如果使用基于表格的方法需要存储25个state value
其中$r_{\mathrm{forbidden}}=r_{\mathrm{boundary}}=-1, r_{\mathrm{target}}=1, \mathrm{and} \gamma=0.9.$
我们可以先用基于模型求解贝尔曼公式得到它。我们要把二维的表格画为三维的曲面。高度就是state value。
我们有500个episode，每个episode有500步。每个出发的位置是随机选择的，并且服从随机均匀分布。
为了比较，tabular TD algorithm
我们对比俩者
我们可以看到趋势是对的，但是没有成功拟合。
如果我们想要更号的近似，我们可以用高阶的特征向量和更多的参数。
但是参数不能过多，不然和表格就没什么区别了（一般来说越多效果越好，如上。）
sarsa和Q-learning结合函数近似
Sarsa
之前是在估计是估计state value。而这一章是估计action value。下面的Q-learning是要估计最优action value。
以下就是sarsa和value functionapproximation结合的算法
$$ w_{t+1}=w_t+\alpha_t\Big[r_{t+1}+\gamma\hat{q}(s_{t+1},a_{t+1},w_t)-\hat{q}(s_t,a_t,w_t)\Big]\nabla_w\hat{q}(s_t,a_t,w_t). $$
它把$\hat v$换成了$\hat q$。这个算法还是在做策略评估和策略增强。（给定策略$\pi$估计action value）
Q-learning
直接看公式
$$ w_{t+1}=w_t+\alpha_t\Big[r_{t+1}+\gamma\max_{a\in\mathcal{A}(s_{t+1})}\hat{q}(s_{t+1},a,w_t)-\hat{q}(s_t,a_t,w_t)\Big]\nabla_w\hat{q}(s_t,a_t,w_t), $$
DQN
Deep Q-learning也叫做Deep Q-network
它是Q-learning的一个变种。它是最成功的把深度神经网络引入强化学习的方法。在应用中它取得了非常好的效果。
神经网络在其中扮演的角色是非线性方程。
q-learning的函数近似如下
在经典 Q-learning 中，由于每一步都直接使用更新后的Q值作为新的目标值，网络参数在频繁更新中容易出现震荡不稳定的情况。目标网络通过减少参数更新频率，提供了一个相对稳定的目标，使得训练更加平滑和稳定。
$$ w_{t+1} = w_t + \alpha_t \left[ r_{t+1} + \gamma \max_{a \in \mathcal{A}(s_{t+1})} \hat{q}(s_{t+1}, a, w_t) - \hat{q}(s_t, a_t, w_t) \right] \nabla_w \hat{q}(s_t, a_t, w_t) $$
我们的loss函数如下,括号中的内容就是Q-learning的TD target
$$ J(w) = \mathbb{E} \left[ \left( R + \gamma \max_{a \in \mathcal{A}(S')} \hat{q}(S', a, w) - \hat{q}(S, A, w) \right)^2 \right] $$
其实我们可以想象输入state和action经过权重w之后输出一个$\hat q$
其中(S,A,R,S')是随机变量，它就是贝尔曼最优误差
$$ q(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a \in \mathcal{A}(S_{t+1})} q(S_{t+1}, a) \mid S_t = s, A_t = a \right], \quad \forall s, a $$
也就是说如果达到最优的话贝尔曼最优误差应该是0。
如何去最小化目标函数呢？那就是梯度下降！
如何计算目标函数的梯度呢？也就是说J对于w的梯度。
DQN中假设$ R + \gamma \max_{a \in \mathcal{A}(S')} \hat{q}(S', a, w)$为y，而y中包含了w。假设y中的w是一个常数。这样偏导只相关于$\hat{q}(S, A, w)$中的w。
为了做到这个技巧DQN引入了俩个network
- 第一个main network对应的是$\hat q(s,a,w)$ （有时候也叫online network）
- 另一个network对应的是target network$\hat q(s,a,w_T)$，这里的下标T代表的是target
main network每当有参数进来的时候一直会被更新，而target network隔一段时间复制main network
因此这个函数变成了这样，其中$w_T$是目标网络的参数
分为了俩个部分，在更新的时候我们先假设$w_T$是固定不动的。然后对蓝色的w求梯度。然后去优化J
这样的话我们就可以得到他的梯度
可以看到只有关于蓝色Q的梯度。
这就是DQN的基本思想使用梯度下降来最小化目标函数。
在其中我们要关注几个技巧。
- 它在其中用了俩个网络，main和target network。而不是一个网络。
因为计算梯度的时候非常复杂，所以我们先固定一个再去计算另一个。过程如下
其中$y_T$为$ R + \gamma \max_{a \in \mathcal{A}(S')} \hat{q}(S', a, w)$
- 最初$w$和$w_T$是一样的。
- 每一个迭代中，我们使用来自reply buffer（$\{s,a,r,s'\}$）的小批量采样
- 一个网络参数是w输入是状态s和动作a，输出是$\hat q$。我们希望$\hat q$接近于$\hat y_T$。得到所有的输入输出后，将他们送入main network当中去。
一段时间后main network的参数变换了，将他赋值给$w_T$，继续用$w_T$来训练main network。
- 经验回放
我们在收集数据的时候，是有先后顺序的，但使用他们的时候可以按照自己的方式。我们可以把所有的经验放到一个集合中，这个集合叫做reply buffer。然后使用的时候直接从中拿取就可以了。
我们在取值的时候一定要遵循一个uniform distribution。也就是说每个数据被拿到的概率是相同的。那么为什么要这样做呢？
$$ J(w) = \mathbb{E} \left[ \left( R + \gamma \max_{a \in \mathcal{A}(S')} \hat{q}(S', a, w) - \hat{q}(S, A, w) \right)^2 \right] $$
我们先来看其中S,A的分布，它是一个索引。比如有n个状态，每个状态有5个action。那么我们就可以用S和A来进行索引。它会符合分布d。
当S和A给定了之后，R和S'应该要符合系统的模型。
我们这里假设state-action对的分布是均匀分布的。但是我们采集的时候不一定是均匀分布的收集。我们就不按照顺序进行使用就可以了。这样就可以打破不同采样之间的关联。
为什么之前表格的Q-learning不需要均匀分布呢？这是因为之前没有涉及到状态s和action a的分布。
因为基于表格的方式是在求解贝尔曼最优公式。而DQN是在做值函数近似，也就是需要有scalar的函数去做优化。
所以即便是基于表格的Q-learning也可以使用experience reply。这样我们还可以充分利用所有的数据。
例子
我们先给出off-policy的伪代码。我们假设由一个策略$\pi_b$产生了很多采样$\{(s,a,r,s')\}$
对越每次迭代c次，进行
- 均匀的在集合中进行采样
- 对采样计算出$y_T$,这里的$y_T$指的是期望输出$\hat q$去接近的值。也就是说是真值标签$y_T=r+\gamma \max \hat q(s',a,w_T)$。其中$w_T$是目标网络的参数。
计算方式就是Q-learning中计算的TD target的方式进行计算。 - 然后使用s，a，$y_T$这三个参数来更新main network
在更新了c次之后，将w的值赋值给$w_T$
如果是on-policy的我们可以每次进行更新。如果是off就所有更新完了进行更新。
我们只是用一个episode来训练网络，这个episode是由一个探索性的行为策略得到的。这个episode只有1000步。这里是一个单隐层的神经网络。隐藏层的神经元数量为100.
我们可以使用很少的数据量就能进行学习。
策略梯度方法
基本思想
策略梯度主要用于直接优化agent的策略，以使其能够在环境中做出更优的策略。和基于值的算法如Q-learning不同，策略梯度方法直接学习策略，即给定状态时某一动作的概率分布。
q-learning：估计每个状态动作对的价值（Q值），间接推导出策略。
策略梯度：直接优化策略，直接学习一个状态到动作概率的映射。
之前的方法都是基于值的，现在的方法是基于策略的。直接建立对于策略的目标函数然后直接得到最优的策略。
之前所有的策略都是由表格来表示的。比如想知道某个状态下执行这个动作的概率，我们可以直接在表格中就能找到。我们可以直接通过索引访问或者改变一个量。
现在策略可以被参数化的函数表示
$$ \pi(a|s,\theta) $$
之前我们值函数的时候使用w来表示参数。策略参数使用$\theta$来进行表示。
用函数代替表格的好处和之前是类似的。
输入是s输出是$\pi(a_1,|s,\theta),...,\pi(a_5,|s,\theta)$
如何定义一个最优的策略？
当用表格进行表示，如果它可以最大化每个state value那么策略$\pi$是最优策略。
当用函数进行表示如果可以最大化特定的scalar metrics那么策略$\pi$是最优的
那么如何获取action的可能性。我们需要使用给定函数来计算$\pi(a|s,\theta)$的值。
那么如何更新一个策略？
如果我们使用表格可以之久修改表格进行更新。
如果通过参数化的函数来表示，它只能通过修改参数$\theta$来进行更新。表格表达连续的数据格式会比较乏力。
- 我们需要定义一个目标函数，来定义最优的策略是什么比如$J(\theta)$
- 然后对目标函数进行优化，比如使用基于梯度的方法
$$ \theta_{t+1}=\theta+\alpha\nabla_\theta J(\theta_t) $$
目标函数 1
“metrics”通常指用于评估和监控模型性能的各种指标。
有俩个类型的Metric，第一个metric是平均状态值或者也叫做状态值。它其实就是加权平均
$$ \overline v=\pi\sum d(s)v_\pi(s) $$
其中$v_\pi(s)$是s的state value，d(s)是给s的权重。权重大于等于0，并且权重之和为1(可以理解为状态s被选中的概率)。我们得到的数就是metric
因此上面的目标函数可以写为
$$ \overline v=\mathbb E[v_\pi(S)] $$
同样这也可以写为俩个向量的内积
$$ \overline v\pi\sum d(s)v_\pi(s)=d^T v_\pi $$
之类$v_\pi$就是状态值的向量，d是权重的向量。
那么如何选择分布d呢？
如果d是无关于策略$\pi$的，这种情况比较简单因为metric的梯度是容易计算的。
在这个情况下我们特别指定d为$d_0$,$\overline v_\pi$为$\overline v^0_\pi$
如何选择$d_0$呢我们可以把每一个状态当做相同重要的，因此$d_0(s)=1/|S|$
另一个情况是我们非常关心某一个特定开始的状态，比如游戏总是从某个状态开始。在这种情况下我们可能要对一些状态有所偏好。
因此我们可以给某个state权重为1，其他的为0。这种时候$\overline v_\pi=v_\pi(s_0)$
如果d和$\pi$是有关的
这时候选择d为$d_\pi(s)$它是stationary distribution（稳定分布）。
$$ d^t_\pi P_\pi=d^T_\pi $$
这里的$p_\pi$是转换概率矩阵。
目标函数 2
第二个metric是average one-step reward或者叫做average reward。
$$ \bar{r}_\pi \doteq \sum_{s \in S} d_\pi(s) r_\pi(s) = \mathbb{E} [r_\pi(S)], $$
这里的$r_\pi(s)$是单步的reward。$d_\pi(s)$是权重。其中
$$ r_\pi(s)\doteq\sum_{a\in\mathcal{A}}\pi(a|s)r(s,a) $$
其中
$$ r(s,a)=\mathbb{E}[R|s,a]=\sum_{r}rp(r|s,a) $$
其中的$d_\pi$是stationary distribution。
它还有另外一种形式。
$$ \begin{aligned}&\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\Big[R_{t+1}+R_{t+2}+\cdots+R_{t+n}|S_t=s_0\Big]\\&=\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\sum_{k=1}^nR_{t+k}|S_t=s_0\right]\end{aligned} $$
代表走无线多步的时候，求所有reward的平均。
也可以写成这种形式
$$ \begin{aligned} \operatorname*{lim}_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\sum_{k=1}^{n}R_{t+k}|S_{t}=s_{0}\right]& \begin{aligned}=\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\sum_{k=1}^{n}R_{t+k}\right]\end{aligned} \\ &=\sum_sd_\pi(s)r_\pi(s)=\overline r_\pi \end{aligned} $$
这些metric全是策略的函数，这个策略的函数是$\theta$。不同的$\theta$会得到不同metric的值。我们希望去优化找到最优的$\theta$
此外我们可以证明。
$$ \overline r_\pi=(1-\gamma)\overline v_\pi $$
第一个目标函数：这个指标表示在策略 π 下，基于状态的值函数$v_\pi(s)$ 的加权期望。
第二个目标函数：这个指标表示在策略 π 下的期望奖励（reward）。
目标函数的梯度计算
刚才介绍了一些metric，指的是用来衡量策略性能的指标。之后我们就可以对metric求梯度。
然后我们就可以使用基于策略梯度的方式方法来优化metric。其中梯度计算是策略梯度中最复杂的一部分。
因为我们有不同的metric$\overline v_\pi,\overline r_\pi,\overline v^0 _\pi$。
然后我们需要计算区分discounted 和undiscounted 例子。
我们给出计算梯度的公式
$$ \nabla_{\theta}J(\theta)=\sum_{s\in\mathcal{S}}\eta(s)\sum_{a\in\mathcal{A}}\nabla_{\theta}\pi(a|s,\theta)q_{\pi}(s,a) $$
其中的$J(\theta)$可以是$\overline v_\pi,\overline r_\pi,\overline v^0 _\pi$。
其中的等号可以表示相等，近似，和成比例
$\eta$是状态 的权重或者分布。
上面的公式可以写成这种形式
$$ =\mathbb{E}\Big[\nabla_\theta\ln\pi(A|S,\theta)q_\pi(S,A)\Big] \text{where }S\sim\eta\text{and}A\sim\pi(A|S,\theta). $$
因为我们可以通过采样来近似这个上面的期望，因为我们用了ln所以这里的
$$ \pi(a|s,\theta)>0 $$
为了实现这一点我们可以使用softmax函数。
那么策略函数的形式就是
$$ \pi(a|s,\theta)=\frac{e^{h(s,a,\theta)}}{\sum_{a^{\prime}\in\mathcal{A}}e^{h(s,a^{\prime},\theta)}}, $$
因为对于所有的a来说$\pi(a|s,\theta)>0$，参数策略是随机和探索性的。
梯度上升算法
策略梯度算法是最大化$J(\theta)$
$$ \begin{aligned} \theta_{t+1}& =\theta_t+\alpha\nabla_\theta J(\theta) \\ &=\theta_t+\alpha\mathbb{E}\Big[\nabla_\theta\ln\pi(A|S,\theta_t)q_\pi(S,A)\Big]^* \end{aligned} $$
真实梯度可以换成随机的
$$ \theta_{t+1}=\theta_t+\alpha\nabla_\theta\ln\pi(a_t|s_t,\theta_t)q_\pi(s_t,a_t) $$
但是其中的$q_\pi$是不知道的，它对应的是$\pi$的action value
$$ \theta_{t+1}=\theta_t+\alpha\nabla_\theta\ln\pi(a_t|s_t,\theta_t)q_t(s_t,a_t) $$
因此我们只能近似或者进行采样。
我们可以基于蒙特卡洛方法（reinforce）
$$ \mathbb{E}_{S\sim d,A\sim\pi}\Big[\nabla_\theta\ln\pi(A|S,\theta_t)q_\pi(S,A)\Big]\longrightarrow\nabla_\theta\ln\pi(a|s,\theta_t)q_\pi(s,a) $$
那么如何进行采样呢
首先是如何采样S
S服从d，其中d的分布是$\pi$的长期行为
如何采样A呢？
DQN使用经验回放（Experience Replay）机制，在训练时并不直接用当前策略生成的数据，而是将过去的状态、动作、奖励、下一状态等存储在经验池中，然后从中随机采样进行训练。这种离线回放的方式减少了数据相关性，使训练更加稳定。因此是off-policy的
策略梯度方法（如 REINFORCE、PPO 等）直接对策略进行优化，它们依赖于当前策略与环境的交互产生的数据。策略梯度方法是基于策略生成的轨迹来估计梯度，并根据这些样本的反馈直接调整策略。因为这些方法通常不使用经验回放池，而是需要新的数据来指导策略的更新，因此属于在线策略。这种在线的方式可以更快适应策略的变化，但也可能导致较高的方差和不稳定性。
A服从$\pi(A|S,\theta)$。因此$a_t$可以遵循$s_t$时的$\pi(\theta_t)$进行采样。因此策略梯度算法是on-policy的。因为它的行为策略和目标策略是一致的。
来个一下具体的流程
对于第k个迭代。
选择初始的状态，用当前的参数$\theta$生成策略。$\pi(\theta_k)$假设交互之后得到了episode$\{s_0,a_0,r_1,\ldots,s_{T-1},a_{T-1},r_T\}$
遍历episode每一个元素进行俩个操作
值更新：$q_t(s_t,a_t)=\sum_{k=t+1}^T\gamma^{k-t-1}r_k$：从$s_t,a_t$出发把后面得到的reward都相加。用它更新$\theta_t$得到了$\theta _t+1$
策略更新：$\theta_{t+1}=\theta_{t}+\alpha\nabla_{\theta}\ln\pi(a_{t}|s_{t},\theta_{t})q_{t}(s_{t},a_{t})$：
$\theta_k=\theta_T$
总结一下：
- 我们需要由目标函数
- 求出目标函数的梯度
- 把他放到梯度上升的算法中去对目标函数进行优化
actor critic
QAC
它和之前的策略梯度方法类似，它把基于value的方法引入到了策略梯度中，就得到了actor critic方法。
其中actor代表的是策略更新，这是因为策略是用来采取行动的。
这里的critic代表了策略评估和value estimation，它通过评估来评价策略。
和策略梯度一样，我们需要有一个目标函数可以是$\overline v_\pi,\overline r_\pi,\overline v^0 _\pi$。
然后就可以对梯度进行优化
$$ \begin{aligned} \theta_{t+1}& =\theta_t+\alpha\nabla_\theta J(\theta_t) \\ &=\theta_{t}+\alpha\mathbb{E}_{S\sim\eta,A\sim\pi}\Big[\nabla_{\theta}\operatorname{ln}\pi(A|S,\theta_{t})q_{\pi}(S,A)\Big] \end{aligned} $$
然后把它转换成一个不含有期望的算法
也就是随机梯度上升算法。
$$ \theta_{t+1}=\theta_t+\alpha\nabla_\theta\ln\pi(a_t|s_t,\theta_t)q_t(s_t,a_t) $$
这个算法就是actor！
估计$q_t(s,a)$对应的是critic！它是$q_\pi(S,A)$的近似。
那么如何得到$q_t(s_t,a_t)$呢？
目前我们学习了俩中方法去估计action value
- 蒙特卡洛学习：采样s下a的return作为$q_t$的近似值，这叫做reinforce
- 时序插分：我们使用TD算法来估计action value这种算法通常被叫做actor critic算法。
具体方式如下
QAC算法中有俩个主要的神经网络，分别用于实现actor和critic的功能
actor网络：根据当前的状态生成动作的策略。它学习一个概率分布，已确定在给定状态下选择每个动作的概率。
输入当前的状态，输出动作的概率分布（policy），通常是一个向量，表示该状态下每个动作的概率
使用梯度来更新网络参数，使得选择的动作能在未来获得更高的期望回报
critic网络：评估actor网络所选择的动作的价值。它通过计算state value或者action value来为actor提供反馈。
输入为当前状态和选择的动作，输出为state value的估计。
通过最小化TD error来更新网络参数，从而提高对状态或动作价值的估计准确性。
简单来说
Actor网络是为了做出更好的策略，critic网络是为了对策略是否是好的做出评估他们之间相互进行更新
每个episode有t步
假设当前的状态是$s_t$策略权重是$\theta_t$,跟这个策略生成$\pi(a|s_t,\theta_t)$。根环境进行交互得到$r_{t+1},s_{t+1}$。然后在哪一部得到新的状态$\pi(a|s_{t+1},\theta_t)$和对应的$a_{t+1}$
critic(value update)：其实就是sarsa算法结合上值函数估计，会对w进行更新（其实就是$\theta$）
actor(policy update)：这里就是policy update算法
这个算法同样是on-policy的。
这个算法是最简单的actor citric算法，也被叫做Q actor-Critic算法
A2C
引入baseline来减少估计的方差
a2c是QAC的推广。基本的思想是在QAC当中引入一个新的baseline来减少估计的方差。
$$ \begin{align*} \nabla_{\theta} J(\theta) &= \mathbb{E}_{S \sim \eta, A \sim \pi}\left[\nabla_{\theta} \ln \pi(A|S, \theta_t) q_{\pi}(S, A)\right] \\ &= \mathbb{E}_{S \sim \eta, A \sim \pi}\left[\nabla_{\theta} \ln \pi(A|S, \theta_t)(q_{\pi}(S, A) - b(S))\right] \end{align*} $$
这俩个式子是相同的。b是一个标量的函数，无论b是什么函数他们都是相同的。
在这里我们让$\nabla_\theta J(\theta) = \mathbb{E}[X]$
$$ X(S,A) = \nabla_\theta \ln \pi(A | S, \theta_t) [q(S,A) - b(S)] $$
其中X的期望和b(S)没有任何的关系。
X的方差，和不同的b是有关系的。
我们的目标是选择最优的baseline去最小化X的方差
好处：当我们使用随机采样去接近$\mathbb E[X]$，估计的变化也会变得更小。
一般来说最优的baselone为
$$ b^*(s)=\frac{\mathbb{E}_{A\thicksim\pi}[\|\nabla_\theta\ln\pi(A|s,\theta_t)\|^2q(s,A)]}{\mathbb{E}_{A\thicksim\pi}[\|\nabla_\theta\ln\pi(A|s,\theta_t)\|^2]}. $$
但是它太复杂了，所以我们一般使用
$$ b(s)=\mathbb{E}_{A\sim\pi}[q(s,A)]=v_\pi(s) $$
当$b(s)=v_\pi(s)$
梯度下降算法就是
$$ \begin{aligned} \theta_{t+1}& =\theta_t+\alpha\mathbb{E}\Big[\nabla_\theta\ln\pi(A|S,\theta_t)[q_\pi(S,A)-v_\pi(S)]\Big] \\ &\doteq\theta_t+\alpha\mathbb{E}\Big[\nabla_\theta\ln\pi(A|S,\theta_t)\delta_\pi(S,A)\Big] \end{aligned} $$
其中
$$ \delta_\pi(S,A)\doteq q_\pi(S,A)-v_\pi(S) $$
$\delta_\pi$被叫做advantage function。为什么叫他优势函数呢？因为它在描述俩者的差，$v_\pi$是$q_\pi$在某个状态下的平均值。因此币平均值要打说明action来的更好。
这个算法的随机采样版本就是
$$ \begin{aligned} \theta_{t+1}& =\theta_t+\alpha\nabla_\theta\ln\pi(a_t|s_t,\theta_t)[q_t(s_t,a_t)-v_t(s_t)] \\ &=\theta_t+\alpha\nabla_\theta\ln\pi(a_t|s_t,\theta_t)\delta_t(s_t,a_t) \end{aligned} $$
算法可以表示为
$$ \begin{aligned} \theta_{t+1}& =\theta_t+\alpha\nabla_\theta\ln\pi(a_t|s_t,\theta_t)\delta_t(s_t,a_t) \\ &=\theta_t+\alpha\frac{\nabla_\theta\pi(a_t|s_t,\theta_t)}{\pi(a_t|s_t,\theta_t)}\delta_t(s_t,a_t) \\ &=\theta_t+\alpha\underbrace{\left(\frac{\delta_t(s_t,a_t)}{\pi(a_t|s_t,\theta_t)}\right)}_{\text{step size}}\nabla_\theta\pi(a_t|s_t,\theta_t) \end{aligned} $$
其中的$q_t$变成了$\delta_t$，那么哪个来的更好呢？显然是$\delta_t$更好。因为我们在乎的不是action value的绝对值，而在乎的是它的相对值。
此外我们还可以做如下的替换
$$ \delta_t=q_t(s_t,a_t)-v_t(s_t)\to r_{t+1}+\gamma v_t(s_{t+1})-v_t(s_t) $$
这个替换是合理的，因为
$$ \mathbb{E}[q_\pi(S,A)-v_\pi(S)|S=s_t,A=a_t]=\mathbb{E}\Big[R+\gamma v_\pi(S')-v_\pi(S)|S=s_t,A=a_t\Big] $$
做这样的替换是因为，替换之后我们只需要一个神经网络来近似$v_t$
这样我们就得到了A2C算法如下,它也被称为TD actor-critic算法
每个episode有t个时刻，在第t个时刻进行
我们使用$\pi(a|s_t,\theta_t)$来生成$a_t$，和环境进行交互我们得到了$r_{t+1},s_{t+1}$
用这个我们来计算TD error也就是优势函数：$\delta_t=r_{t+1}+\gamma v(s_{t+1},w_t)-v(s_t,w_t)$
把TD error带入到Critic（value update）当中$w_{t+1}=w_t+\alpha_w\delta_t\nabla_wv(s_t,w_t)$
这个$\delta_t$也可以复用到actor（policy）当中：$\theta_{t+1}=\theta_t+\alpha_\theta\delta_t\nabla_\theta\ln\pi(a_t|s_t,\theta_t)$
然后重复以上循环。所以这个算法是on-policy的算法。