强化学习

参考教材

强化学习导论 — 强化学习导论 (qiwihui.com)

深度强化学习（全）_哔哩哔哩_bilibili

世界冠军带你从零实践强化学习_哔哩哔哩_bilibili

何为强化学习？其核心思想就是让智能体agent再环境environment中学习，根据环境的状态state，执行动作action，并根据环境的反馈reward(奖励)来指导更好的动作。其reward是延迟的，只有最后才知道reward。这更贴近生活，我们做了一件事往往在很久以后才能评判此事的结果。

强化学习是一种学习如何将状态映射到动作，以获得最大奖励的学习机制。学习者不会被告知要采取哪些动作，而是必须通过尝试来发现哪些动作会产生最大的回报。在最有趣和最具挑战性的案例中，动作不仅可以影响直接奖励，还可以影响下一个状态，并通过下一个状态，影响到随后而来的奖励。这两个特征 - 试错法和延迟奖励 - 是强化学习的两个最重要的可区别特征

强化学习和监督学习的区别何在呢？

主要来说，监督学习输出是一个认知，比如分类问题，我们要知道这张图片是什么。而强化学习输出是一个动作action，即我们要怎么做。

比如上图中，监督学习告诉我们这是一只灰熊，而强化学习让我们赶快装死。

Agent学习的两种方法：

基于价值的学习方法value-based:agent在每一次决策时都衡量不同策略的价值，选择价值最大的路线。常见算法有：

sarsa
Q-learning
DQN

有点类似于广度优先搜索有没有？

基于策略的学习方法：policy-based：就是一条路走到头再回过头来衡量哪条路线reward更高

随机性策略算法

emm，类似深度优先搜索咯

强化学习的分类多种多样，具体可以看下图：

专业术语定义

State：状态
Agent:需要学习做出动作的主体
Policy $\pi$:在状态为s的情况下做出动作a的概率密度。
$$
\pi(a\vert s)=p(A=a\vert S=s)
$$
reward:R
p:状态转移概率：
$$
p(s’\vert s,a)=p(S’=s’\vert S=s,A=a)
$$
Return:
$$
G_t=R_t+R_{t+1}+…+R_T
$$
Discount retuen:

$$
G_T=R_t+\gamma R_{t+1}+\gamma^2R_{t+2}+…
$$

强化学习任务通常使用马尔科夫决策过程MDP来描述：机器处于环境E中，状态空间为X，其中每个状态$x\in X$是机器感知到的环境的描述，机器能采取的动作构成了动作空间A ，若某个动作$$a\in A$$ 作用在当前状态x上，则潜在的转移函数P将使得环境从当前状态按某种概率转移到另一个状态，同时，环境会根据潜在的“奖赏函数R”反馈给机器一个奖赏。

一个简单的给西瓜浇水的马尔可夫决策过程如图所示，一共有四个状态：缺水、健康、溢水、凋亡，和两个动作：浇水、不浇水，再每一步转移后，若状态是保持瓜苗健康则获得奖赏1，缺水或溢水获得奖赏-1，死亡获得奖赏-100且无法恢复。

model-based：p函数和r函数已知

model-free：p函数和r函数未知

策略迭代

状态价值函数$Q(s_t,a_t)$：表示在状态$s_t$下执行$a_t$所能获得的价值

比如此图中，熊吼叫的时候为当前状态，此时执行动作一：装死的价值为0，执行动作二：跑路的价值为-90，那表示此种情形下装死比跑路好。同理，熊转身离开时，跑路比装死更好。

注意状态价值函数表格是由模型学习所得。

**状态值-动作函数$Q(s_t,a_t)$**表示在状态$s_t$时采取$a_t$动作后所获得的累积奖赏的期望：(在状态$s_t$时采取$a_t$动作的分数)
$$
Q_\pi(s_t,a_t)=E_\pi(G_t\vert S_t=s_t,A_t=a_t)
$$
Optimal action-value function：表示当前状态下执行动作的最大分数
$$
Q^*(s_t,a_t)=\max_\pi Q_\pi (s_t,a_t)
$$

**状态值函数：$V(s_t)$**表示在状态$s_t$后所获得的累积奖赏代码期望：（在状态$s_t$时的分数）
$$
V(s_t)=E_\pi(G_t\vert s_t)=E_A[Q_\pi(s_t,A))]=\sum_{a\in A}\pi(s_t,a)Q(s_t,a)
$$

那么对应的T步Q,V函数为：
$$
\begin{cases}
V_T^\pi(s)=E_\pi(\frac{1}{T}\sum_{t=1}^TR_t \vert s_0=s)\\
Q_T^\pi(s,a)=E_\pi(\frac{1}{T}\sum_{t=1}^TR_t \vert s_0=s,a_0=a)
\end{cases}
$$
$\gamma$折扣Q,V函数为：

$$
\begin{cases}
V_\gamma ^\pi(s)=E_\pi(\frac{1}{T}\sum_{t=0}^{T-1}\gamma^tR_{t+1} \vert s_0=s)\\
Q_\gamma ^\pi(s,a)=E_\pi(\frac{1}{T}\sum_{t=0}^{T-1}\gamma ^tR_{t+1} \vert s_0=s,a_0=a)
\end{cases}
$$

对T步V函数进行一下展开：

$$
\begin{aligned}
V_T^\pi(s)&=E_\pi(\frac{1}{T}\sum_{t=1}^TR_t \vert s_0=s)\\
&=\sum_{a \in A}\pi(s,a)E_\pi(\frac{1}{T}\sum_{t=1}^TR_t \vert s_0=s,a_0=a)\\
&=\sum_{a \in A}\pi(s,a)[\frac{1}{T}E_{\pi}(R_1\vert s_0=s,a_0=a)+E_\pi(\frac{1}{T}\sum_{t=2}^TR_t \vert s_0=s,a_0=a)]
\end{aligned}
$$

其中：

$$
E_{\pi}(R_1\vert s_0=s,a_0=a)=\sum_{s’\in S}P(s_1=s’\vert s_0=s,a_0=a )E_{\pi}[R_{1}\vert s_0=s,a_0=a]
$$

$$
\begin{aligned}
E_\pi(\sum_{t=2}^TR_t \vert s_0=s,a_0=a)&=\sum_{s’\in S}P(s_1=s’\vert s_0=s,a_0=a )E_{\pi}[\sum_{t=1}^{T-1}R_t\vert s_0=s’]\\
&=\sum_{s’\in S}P(s_1=s’\vert s_0=s,a_0=a )(T-1)V_{T}^{\pi}(s’)
\end{aligned}
$$

那么：
$$
\begin{aligned}
V_T^\pi(s)&=E_{\pi}[\frac{1}{T}R_1+\frac{T-1}{T}\frac{1}{T-1}\sum_{t=2}^TR_t\vert s_0=s]\\
&=\sum_{a \in A}\pi(s,a)\sum_{s’\in S}P(s_1=s’\vert s_0=s,a_0=a )(\frac{1}{T}E_{\pi}[R_{1}\vert s_0=s,a_0=a]+\frac{T-1}{T}E_{\pi}[\sum_{t=1}^{T-1}R_t\vert s_0=s’])\\
&=\sum_{a \in A}\pi(s,a)\sum_{s’\in S}P(s_1=s’\vert s_0=s,a_0=a )(\frac{1}{T}E_{\pi}[R_{1}\vert s_0=s,a_0=a]+\frac{T-1}{T}V_{T-1}^\pi(s’))
\end{aligned}
$$

如此我们就得到了V函数的递推公式：

如果令：
$$
P_{s\rightarrow s’}^a=P(s_1=s’\vert s_0=s,a_0=a )
$$

$$
R_{s\rightarrow s’}^\pi=E_{\pi}[R_{1}\vert s_0=s,a_0=a]
$$

那么我们可得：
$$
\begin{cases}
V_T^\pi=\sum_{a \in A}\pi(s,a)\sum_{s’\in S}P_{s\rightarrow s’}^a(\frac{1}{T}R_{s\rightarrow s’}^\pi+\frac{T-1}{T}V_{T-1}^\pi(s’))\\
Q_T^\pi=\sum_{s’\in S}P_{s\rightarrow s’}^a(\frac{1}{T}R_{s\rightarrow s’}^\pi+\frac{T-1}{T}V_{T-1}^\pi(s’))
\end{cases}
$$

$$
\begin{cases}
V_\gamma^\pi=\sum_{a \in A}\pi(s,a)\sum_{s’\in S}P_{s\rightarrow s’}^a(R_{s\rightarrow s’}^\pi+\gamma V_\gamma^\pi(s’))\\
Q_\gamma^\pi=\sum_{s’\in S}P_{s\rightarrow s’}^a(R_{s\rightarrow s’}^\pi+\gamma V_\gamma^\pi(s’))
\end{cases}
$$

通过迭代求出策略$\pi$情况下Q,V函数的过程我们就称其为：策略评估

求出以上Q,V函数后，我们接下来需要根据这两个函数对策略$\pi$进行改进，我们称其为：策略改进

策略评估与策略改进不断交替迭代就是所谓的 广义策略迭代算法：GPL

对于理想化的策略，我们肯定希望其能最大化累计奖励v:
$$
\pi^*=\arg\max_\pi \sum_{s \in S}V^\pi(s)
$$
那么强化学习的问题定义可以转化为：

给定马尔可夫决策过程MDP={S,A,P,R,$\gamma$}，寻找一个最有策略$\pi^*$，对任意$s \in S$使得$V_{\pi^*}(S)$的值最大

那我们将每个状态选取动作时直接取Q函数最大的动作，不久能使V最大了吗，即：

$$
V^(s)=\max_{a \in A}Q^{\pi^}(s,a)
$$

$$
\begin{cases}
Q_T^(s,a)=\sum_{s’\in S}P_{s\rightarrow s’}^a(\frac{1}{T}R_{s\rightarrow s’}^\pi+\frac{T-1}{T}\max_{a’ \in A}Q_{t-1}^(s’,a’))\\
Q_\gamma^\pi=\sum_{s’\in S}P_{s\rightarrow s’}^a(R_{s\rightarrow s’}^\pi+\gamma \max_{a’ \in A}Q_{\gamma}^*(s’,a’))
\end{cases}
$$

不妨令动作改变后的策略为$\pi’$，改变动作的条件为$Q^\pi(s,\pi’(s))\geq V^\pi(s)$,那么根据Q函数递推式，可得：

$$
\begin{aligned}
V^\pi(s)&\leq Q^\pi(s,\pi’(s))\\
&=\sum_{s’\in S}P_{s\rightarrow s’}^{\pi’(s)}(R_{s\rightarrow s’}^{\pi’(s)}+\gamma V^\pi(s’))\\
&\leq \sum_{s’\in S}P_{s\rightarrow s’}^{\pi’(s)}(R_{s\rightarrow s’}^{\pi’(s)}+\gamma Q^\pi(s’,\pi’(s’)))\\
&=…\\
&=V^{\pi’}(s)
\end{aligned}
$$
由此可见值函数对于策略每一点改进都是单调递增的，因此对于当前策略$\pi$,我们可以放心的将其改进为：

$$
\pi’(s)=\arg\max_{a \in A}Q^{\pi}(s,a)
$$

$$
\begin{cases}
V_T^\pi=\max_{a \in A}\sum_{s’\in S}P_{s\rightarrow s’}^a(\frac{1}{T}R_{s\rightarrow s’}^a+\frac{T-1}{T}V_{T-1}^(s’))\\
V_\gamma^\pi=\max_{a \in A}\sum_{s’\in S}P_{s\rightarrow s’}^a(R_{s\rightarrow s’}^a+\gamma V_\gamma^(s’))
\end{cases}
$$

值迭代

求Optimal action-value function：表示当前状态下执行动作的最大分数
$$
Q^(s_t,a_t)=\max_\pi Q_\pi (s_t,a_t)
$$
我们就可以根据所求的$Q^(s_t,a_t)$判断执行何种动作：
$$
a^=\arg\max_aQ^(s,a)
$$
我们需要做的就是去近似$Q^*$函数