强化学习

1 基本概念

• State：agent相对于环境的状态，$s_1,s_2,...s_9$

• State space：state的集合

• Action：每个状态的可能行为，$A(s)$

• State transition：状态转移，$p(s_2|s_1,a)$

• Policy：告诉智能体在某个状态应该采取哪个行动，用π条件概率表示。

  • $\pi (a_1|s_1)=k$表示在状态s1采取a1行动的概率

• Reward：正数为奖励，负数为惩罚，集合为$R(s,a)$，概率为$p(r,|s,a)$

• Trajectory：state-action-reward链

• Return：基于一个Trajectory得到的reward之和

• Discounted return：加一个discount rate $\gamma \in [0,1)$，防止return加到无穷，值越小越注重近处的reward

• Episode和continuing tasks：前者表示到target state后就不动了，后者会继续。实际中会将target state看做普通state，可能会跳出target，就将episode转换成continuing tasks。

2 贝尔曼公式（Bellman equation）

• State value：从一个状态出发得到的平均return，就是discounted return的期望，多个Trajectory得到的return和的平均值

$$v_{\pi }(s)=\mathbb{E}[G_t|S_t=s]$$

• Bellman equation：

$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[R_{t+1}|S_t=s]+\gamma \mathbb{E}[G_{t+1}|S_t=s]\\ & =\sum _a\pi (a|s)\sum _{r}p(r|s,a)r+\gamma \sum _a\pi (a|s)\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\\ & =\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]\end{array}$$

• 矩阵形式

$$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$$

• 求解

$$v_{k+1}=r_{\pi }+\gamma P_{\pi }{v}_k$$

• Action value：从一个状态出发并选择一个Action的平均return

$$q_{\pi }(a,s)=\mathbb{E}[G_t|S_t=s,A_t=a]$$$$v_{\pi }(s)=\sum _a\pi (a|s)q_{\pi }(a,s)$$

3 贝尔曼最优公式（Bellman optimality equation）

• Bellman optimality equation

$$\begin{array}{rl}v(s)& =\underset{\pi }{\max }\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v(s^{\prime })]\\ & =\underset{\pi }{\max }\sum _a\pi (a|s)q(a,s)\end{array}$$$$v=f(v)=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }v)$$

• 求解：

$$\begin{array}{r}\underset{\pi }{\max }\sum _a\pi (a|s)q(s,a)=\underset{a\in A(s)}{\max }q(s,a)\\ \pi (a|s)=\{\begin{array}{ll}1& a=a^{\ast }\\ 0& a\ne a^{\ast }\end{array}\\ a^{\ast }=argma{x}_{a}q(a,s)\end{array}$$

4 迭代算法

Value iteration

$$v_{k+1}=f(v_k)=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_k)$$

• policy update

已知v带入算策略π

$${\pi }_{k+1}=arg\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_k)$$

• value update

得到的π带入计算下一个v，这里的v不是贝尔曼解

$$v_{k+1}=r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_k$$

Policy iteration

• policy evaluation

已知策略π，循环迭代j趋于无穷大时算出最优的v

$$v_{\pi k}^{(j+1)}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{\pi k}^{(j)}$$

• policy improvement

得到的v再计算新的策略π

$${\pi }_{k+1}=arg\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_{\pi k})$$

靠近目标状态的地方先到达最优策略

Truncated policy iteration

与policy iteration相比j不需要趋于无穷大，只要达到一个阈值即可

5 蒙特卡洛方法（Model free）

平均数近似期望

• MC Basic

就是Policy iteration在policy evaluation计算Action value 即q(a,s)时，采样大量return数据求平均作为q的期望，然后选最大的q的策略，与原Policy iteration相比不需要先计算state value（v)

使用Initial-visit method，在episode中访问一个s、a时，剩下的来估计这个s、a的Action value

• MC Exploring Starts

提高计算效率，在episode中从后往前计算q

• MC without exploring start

  • $\epsilon$-greedy policy：非确定性策略

  $$\pi (a|s)=\{\begin{array}{ll}1-\frac{\epsilon }{|A(s)|}(|A(s)|-1)& greedyaction(q_{\pi }^{\ast }(s,a)\\ \frac{\epsilon }{|A(s)|}& others\end{array}$$

  |A(s)|是action的个数

  • MC Epsilon-Greedy

  策略集合使用ε-greedy policy，具有一定的探索性，ε越接近1探索性越强

6 随机近似理论与随机梯度下降

• 求平均数的迭代算法

$$\begin{array}{rl}{w}_{k+1}& =\frac{1}{k}\sum _{i=1}^k{x}_i\\ w_k& =\frac{1}{k-1}\sum _{i=1}^{k-1}{x}_i\\ w_{k+1}& =w_k-\frac{1}{k}(w_k-x_k)\end{array}$$

• Stochastic approximation（随机近似）：使用随机+迭代的算法解决求解方程或优化问题，不需知道方程表达式。

  • Robbins-Monro算法：求$g(w)=0$的问题，

  $$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k\tilde{g}(w_k,{\eta }_k)\\ \tilde{g}(w_k,{\eta }_k)& =g(w_k)+{\eta }_k\end{array}$$

  收敛条件：

  $$\{\begin{array}{ll}0<c_1\le {\nabla }_{w}g(w)\le c2& g(w)必须递增，相当于凸函数的梯度是g(w)\\ {\sum }_{k=1}^{\infty }{a}_k=\infty and{\sum }_{k=1}^{\infty }{a}_k^2<\infty & 表示a_k收敛于0但不要太快\\ \mathbb{E}[{\eta }_k|H_k]=0and\mathbb{E}[{\eta }_k^2|H_k]<\infty & 噪声的均值是0方差有限\end{array}$$

• 梯度下降

  • 梯度下降GD：

    $$w_{k+1}=w_k-{\alpha }_k{\nabla }_w\mathbb{E}[f(w_k,X)]=w_k-{\alpha }_k\mathbb{E}[{\nabla }_{w}f(w_k,X)]$$

  • 批量梯度下降BGD(无模型时平均代替期望)：

    $$\mathbb{E}[{\nabla }_{w}f(w_k,X)]\approx \frac{1}{n}\sum _{i=1}^n{\nabla }_{w}f(w_k,x_i)$$

  • 随机梯度下降SGD：

    $$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$$

7 时序差分方法（Temporal-Difference）

• 求state value的TD算法

$$\{\begin{array}{ll}{v}_{t+1}(s_t)=v_t(s_t)-{\alpha }_t(s_t)[v_t(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})]]& s=s_t\\ v_{t+1}(s)=v_t(s)& s\ne s_t\end{array}$$

• 求action value的TD算法

  • Sarsa $(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$

$$\{\begin{array}{ll}{q}_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})]]& (s,a)=(s_t,a_t)\\ q_{t+1}(s,a)=q_t(s,a)& (s,a)\ne (s_t,a_t)\end{array}$$

Expected Sarsa

$$\{\begin{array}{ll}{q}_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma \mathbb{E}[q_t(s_{t+1},A)]]& (s,a)=(s_t,a_t)\\ q_{t+1}(s,a)=q_t(s,a)& (s,a)\ne (s_t,a_t)\end{array}$$$$\mathbb{E}[q_t(s_{t+1},A])]=\sum _a{\pi }_t(a|s_{t+1})q_t(s_{t+1},a)=v_t(s_{t+1})$$

上图为MC、Sarsa和n-step Sarsa方法的对比，主要是action value计算展开的个数不同

蒙特卡洛方法需要等所有时刻的采样值得到才可以更新（offline），Sarsa方法得到一次就可以（online），n-step的话属于折中。

只求解贝尔曼方程，不能直接估计出最优策略

• Q-learning

$$\{\begin{array}{ll}{q}_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma \underset{a\in A}{\max }{q}_t(s_{t+1},a)]]& (s,a)=(s_t,a_t)\\ q_{t+1}(s,a)=q_t(s,a)& (s,a)\ne (s_t,a_t)\end{array}$$

用来求解贝尔曼最优公式，使用$(s_t,a_t,r_{t+1},s_{t+1})$

• on-policy和off-policy，前者behavior策略和target策略相同，后者不同。

  • behavior策略：与环境交互生成experience

  • target策略：最终更新得到的最优策略

  • Sarsa：$(s_t,a_t)$给定，$r_{t+1}$和$s_{t+1}$不依赖于策略，而是模型的概率，而$a_{t+1}$是在$s_{t+1}$状态下根据${\pi }_t(s_{t+1})$策略生成并采样得到的，所以${\pi }_t$是behavior策略，根据${\pi }_t$得到action value，再用action value更新${\pi }_t$得到${\pi }_{t+1}$，所以所以${\pi }_t$也是target策略，所以Sarsa是on-policy

  • MC也是on-policy的，与Sarsa类似

  • Q-learning，它的behavior策略是从$s_t$出发根据一个策略${\pi }_b$得到$a_t$，而target策略是找到计算得到的q最大的action对应的策略作为target策略${\pi }_a$时，${\pi }_b$不会更新只用来生成数据，二者不一样所以是off-policy。当更新target策略使用ε-greedy，${\pi }_b$既要生成数据，又要被更新，所以是on-policy。理解为策略${\pi }_b$用来探索，找出最优${\pi }_a$

8 值函数近似

state value

使用函数来拟合原来的state value，离散变连续：$v_{\pi }(s)\to \hat{v}(s,w)$

object function：$J(w)=\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w){)}^2]$，平稳分布来求E

随机梯度下降法优化：

$$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)$$

由于不知道$v_{\pi }(s_t)$，使用MC和TD方法来解决：

• MC：$w_{t+1}=w_t+{\alpha }_t(g_t-\hat{v}(s_t,w_t)){\nabla }_w\hat{v}(s_t,w_t)$，gt是从一个状态沿episode出发得到的Discounted return。

• TD：$w_{t+1}=w_t+{\alpha }_t(r_{t+1}+\gamma \hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)){\nabla }_w\hat{v}(s_t,w_t)$

当使用线性函数来拟合时，可以写成：$\hat{v}(s,w)={\varphi }^T(s)w$

• TD_linear：$w_{t+1}=w_t+{\alpha }_t(r_{t+1}+\gamma {\varphi }^T(s_{t+1})w_t-{\varphi }^T(s_t)w_t)\varphi (s_t)$

action value

• sarsa：

在policy evaluation阶段计算的是$w_{t+1}$而不是直接计算$q_{t+1}$，带入到$\hat{q}(s,a,w)$得到q，再进入policy improvement阶段。

$w_{t+1}=w_t+{\alpha }_t(r_{t+1}+\gamma \hat{q}(s_{t+1},a_{t+1},w_t)-\hat{q}(s_t,a_t,w_t)){\nabla }_w\hat{q}(s_t,a_t,w_t)$

• q-learning：

$$w_{t+1}=w_t+{\alpha }_t(r_{t+1}+\gamma \underset{a\in A(s_{t+1})}{\max }\hat{q}(s_{t+1},a,w_t)-\hat{q}(s_t,a_t,w_t)){\nabla }_w\hat{q}(s_t,a_t,w_t)$$

DQN

object function：$J(w)=\mathbb{E}[R+\gamma \underset{a\in A(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w_T)-\hat{q}(S,A,w){)}^2]$

定义了两个网络main network和target network，参数分别为w和$w_t$，在求梯度时将target中的w看做常数$w_T$，w不断优化，$w_T$隔段时间将w的值赋过来。

9 策略梯度方法

函数表示策略：$\pi (a|s,\theta )$

metrics to define optimal policies

• average value：

$$\stackrel{-}{v_{\pi }}=\sum _{s\in \mathcal{S}}d(s)v_{\pi }(s)=\mathbb{E}[v_{\pi }(S)]=d^T{v}_{\pi }=\mathbb{E}[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}]$$

1. d与$\pi$没有关系，写成d0，可以是状态个数分之一，一视同仁，也可以是关注某个状态令其d0等于1其余等于0

2. 与$\pi$有关，写成$d_{\pi }(s)$

• average reward：

$$\begin{array}{rl}\stackrel{-}{r_{\pi }}& =\sum _{s\in \mathcal{S}}{d}_{\pi }(s)r_{\pi }(s)=\mathbb{E}[r_{\pi }(S)]=\underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}[\sum _{k=1}^n{R}_{t+k}]\\ r_{\pi }(s)& \stackrel{.}{=}\sum _{a\in \mathcal{A}}\pi (a|s)r(s,a)\\ r(s,a)& =\mathbb{E}[R|s,a]=\sum _{r}p(r|s,a)\end{array}$$

Gradients of the metrics

$$\begin{array}{rl}{\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)\\ & ={\mathbb{E}}_{S\in \eta ,A\in \pi }[{\nabla }_{\theta }ln\pi (A|S,\theta )q_{\pi }(S,A)]\end{array}$$

Gradient-ascent

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha {\nabla }_{\theta }ln\pi (a_t|s_t,{\theta }_t)q_t(s_t,a_t)\\ & ={\theta }_t+\alpha (\frac{q_t(s_t,a_t)}{\pi (a_t|s_t,{\theta }_t)}){\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t)\end{array}$$

• $q_t(s_t,a_t)$较大时，说明前一个策略的action value大，充分利用前面的策略（exploitation）

• $\pi (a_t|s_t,{\theta }_t)$较小时，说明前一个策略选择at的概率小的话，下一次会选择更大的概率（exploration）

$q_t$通过蒙特卡洛方法给定一个episode返回的return，这样的话就是reinforce。

10 Actor-Critic方法

• Actor：生成策略的过程。

$${\theta }_{t+1}={\theta }_t+\alpha {\nabla }_{\theta }ln\pi (a_t|s_t,{\theta }_t)q_t(s_t,a_t)$$

• Critic：评估策略的action value或state value，估计$q_t$

1. QAC：Critic使用Sarsa+值函数估计，Actor使用前面的梯度上升的策略更新算法

2. Advantage actor-critic（A2C）

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha \mathbb{E}[{\nabla }_{\theta }ln\pi (A|S,{\theta }_t)[q_{\pi }(S,A)-v_{\pi }(S)]]\\ & ={\theta }_t+\alpha \mathbb{E}[{\nabla }_{\theta }ln\pi (A|S,{\theta }_t){\delta }_{\pi }(S,A)]\\ {\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{array}$$

减小方差

3. 重要性采样

将on-policy转成off-policy，使用重要性采样，behavior policy为$\beta (a|s)$，target policy为$\pi (a|s,{\theta }_0)$

4. DPG

前面的方法都是$\pi (a|s,\theta )\in [0,1]$，神经网络拟合时输入s，输出不同a的π，这要求a的个数有限。

$$a=\mu (s,\theta )\stackrel{.}{=}\mu (s)$$$$J(\theta )=\mathbb{E}[v_{\mu }(s)]=\sum _{s\in \mathcal{S}}{d}_0(s)v_{\mu }(s)$$