强化学习

强化学习的主要任务就是通过在环境中不断地尝试，根据尝试获得的反馈信息调整策略，最终生成一个较好的策略π，机器根据这个策略便能知道在什么状态下应该执行什么动作。

我觉得比较重要的几个观点：

RL is learning from trial and error interaction with the world.

RL is training by rewards and punishments.

增强学习的研究建立在经典物理学的范畴上，也就是没有量子计算也没有相对论。这个世界的时间是可以分割成一个一个时间片的，并且有完全的先后顺序，因此可以形成这样的状态，动作和反馈系列。这些数据样本是进行增强学习的基础。

另一个很重要的假设就是

「上帝不掷筛子！」

在增强学习的世界，我们相信如果输入是确定的，那么输出也一定是确定的。试想一下，有一个机械臂在练习掷筛子，以掷出 6 点作为目标。但是如果无论机械臂如何调整其关节的角度及扭矩，掷出的点数永远是随机的，那么无论如何也不可能通过算法使机械臂达成目标。因此，增强学习算法要有用，就是相信在增强学习中每一次参数的调整都会对世界造成确定性的影响。

马尔可夫决策过程（Markov Decision Processes,MDPs）

MDPs 简单说就是一个智能体（Agent）采取行动（Action）从而改变自己的状态（State）获得奖励（Reward）与环境（Environment）发生交互的循环过程。

MDP 的策略完全取决于当前状态（Only present matters），这也是它马尔可夫性质的体现。

其可以简单表示为： M=<S,A,Ps,a,R>M=<S,A,P_{s,a},R>

 

基本概念

  1. s∈Ss∈S：有限状态 state 集合，s 表示某个特定状态
  2. a∈Aa∈A：有限动作 action 集合，a 表示某个特定动作
  3. Transition Model T(S,a,S′)∼Pr(s′∣s,a)T(S,a,S')∼P_r(s'|s,a) ： Transition Model, 根据当前状态 ss 和动作 aa 预测下一个状态 s′s'，这里的 PrP_r 表示从 ss 采取行动 aa 转移到 s′s' 的概率
  4. Reward R(s,a)=E[Rt+1∣s,a]R(s,a)=E[R_{t+1}|s,a]：表示 agent 采取某个动作后的即时奖励，它还有 R(s,a,s’)R(s, a, s’), R(s) 等表现形式，采用不同的形式，其意义略有不同
  5. Policy π(s)→aπ(s)→a：根据当前 state 来产生 action，可表现为 a=π(s)a=π(s) 或 π(a∣s)=P[a∣s]π(a|s)=P[a|s]，后者表示某种状态下执行某个动作的概率

强化学习的本质是学习从环境状态到动作的映射（即行为策略）。而仅仅使用立即回报r(s,a)肯定是不够的(一个策略π的长期影响才是至关重要的).

一些概念引入

问题的分类，按照 P,RP,R 是否已知进行分类

 

回报（Return）：

U(s0 s1 s2⋯)U(s_0 \,s_1\,s_2⋯) 与 折扣率（discount）γ∈[0,1]γ∈[0,1]： U 代表执行一组 action 后所有状态累计的 reward 之和，但由于直接的 reward 相加在无限时间序列中会导致无偏向，而且会产生状态的无限循环。因此在这个 Utility（效用） 函数里引入 γγ 折扣率这一概念，令往后的状态所反馈回来的 reward 乘上这个 discount 系数，这样意味着当下的 reward 比未来反馈的 reward 更重要，这也比较符合直觉。定义

U(s0 s1 s2⋯)=∑t=0∞γtR(st), 0≤γ<1≤∑t=0∞γtRmax=Rmax1−γU(s_0\,s_1\,s_2⋯)=∑_{t=0}^∞γ^tR(s_t), \,0≤γ<1\\ ≤∑_{t=0}^∞γ^tR_{max}=\dfrac{R_{max}}{1−γ}

由于我们引入了 discount，可以看到我们把一个无限长度的问题转换成了一个拥有最大值上限的问题。

强化学习的目的是最大化长期未来奖励，即寻找最大的 U。（注：回报也作 G 表示）

基于回报（return），我们再引入两个函数

  • 状态价值函数：V(s)=E[Ut∣St=s]V(s)=E[U_t|S_t=s]，意义为基于 t 时刻的状态 s 能获得的未来回报（reward ）的期望，加入动作选择策略后可表示为 Vπ(s)=Eπ[Ut∣St=s](Ut=Rt+1+γRt+2+⋯+γT−t−1RT)V_π(s)=E_π[U_t|S_t=s](U_t=R_{t+1}+γR_{t+2}+⋯+γ^{T−t−1}R_T)
  • 动作价值函数：Qπ(s,a)=Eπ[Ut∣St=s,At=a]Q_π(s,a)=E_π[U_t|S_t=s,A_t=a]，意义为基于 t 时刻的状态 s，选择一个 action 后能获得的未来回报（return）的期望

价值函数用来衡量某一状态或动作 - 状态的优劣，即对智能体来说是否值得选择某一状态或在某一状态下执行某一动作。

引出价值函数，对于获取最优的策略 Policy 这个目标，我们就会有两种方法：

  • 直接优化策略 或者 使得回报更高；
  • 通过估计 value function 来间接获得优化的策略。道理很简单，既然我知道每一种状态的优劣，那么我就知道我应该怎么选择了，而这种选择就是我们想要的策略。

当然了，还有第三种做法就是融合上面的两种做法，这也就是以后会讲到的 actor-critic 算法。

所以最开始的PPT的图也可以这样表示：

 

Value Function 价值函数

这部分主要引自：

https://zhuanlan.zhihu.com/p/21262246

https://zhuanlan.zhihu.com/p/21340755

https://www.zhihu.com/column/c_1297485212247425024

我们用一个例子来说明 Value Function 的含义与重要性。

这是一个投资决策问题：假如我们有一笔 X 美刀的资金，我们眼前有三种选择来使用这笔资金：

  • 使用资金进行股票投资
  • 使用资金进行买房投资
  • 使用资金购买书籍，科研设备等提升资金

那么，我们就面临如何做选择的问题。这里假设我们只能选择其中的一个做选择。

我们先来解释一下直接基于 Policy 的方法是怎样的。

直接基于 Policy 的意思就是我们有一套 Policy 策略，我们基于这个策略进行操作，比如可以有如下所示的策略：

1
2
3
4
5
6
if 资金 X > 500000:
   选择股票投资
else if 资金 X > 100000:
   选择房产投资
else:
   选择买书，买设备自我提升

那么上面的伪代码就是表示一个极其简单的策略。这个策略只考虑资金量，输入资金量，输出决策方式。如果把 Policy 策略看做是一个黑箱，那么基于策略的方法就是：

那么如果不是基于 Policy 策略直接做出决策，我们还有什么办法呢？

显然有，而且大家可以从上面的简单策略看到一个最大的缺陷，就是上面的策略完全不考虑每一种选择未来的价值。我们做决策是有目的的，那就是为了最大化未来的回报 Result 是不是？那么对于上面的投资选择问题，我们的目标就是希望我们的投资回报率最高。因此，上面的简单策略竟然完全不考虑每一种选择的价值，而仅考虑资金量，显然是一种欠考虑的方法。因此，我们是不是应该评估一下每一种选择的潜在价值呢？耶，价值 Value 出来了，是不是？通过对价值的评估，我们也就可以有如下的做决策的方法：

我们就评估每一种状态（选择 + 资金量）的价值，然后选择价值最高的作为最后的决策。

比如说：

1
2
3
4
5
6
7
if 投资股市:
    因为股市低迷，价值为 - 100
if 投资房产 + 资金量 > 100000:
    因为房产泡沫还没破，各地房价还在涨，价值为 + 500
if 提升自己 + 资金量 < 100000:
    当前人工智能潜力巨大，资金又不算太大，投资自己价值为 + 1000
...(更多的评估价值的方法）

OK, 假设现在我们有 50000 的资金，那么根据我们的价值估算方法，选择投资自己的价值最大，为 + 1000，因此我们就选择投资自己作为决策结果。

从数学的角度，我们常常会用一个函数 来表示一个状态的价值，也可以用 来表示状态及某一个动作的价值。我们上面的例子就是来评估某一个状态下动作的价值，然后根据价值做出判断。实际上我们这里也是有策略的，我们的策略更简单：

1
2
if 某一个决策的价值最大：
    选择这个决策

这就是价值函数的意义。在后面的文章当中，我们还会发现，其实我们还可以同时使用策略加价值评估的方法来联合给出决策，这种算法就是所谓的 「Actor-Critic」 算法

为什么引出Value Function？

我们是为了得到最优策略，所以想通过评估状态的价值来引导决策。在MDP的世界，每个状态下的价值是确定的，即存在一个唯一的值来表示某一个状态。也就是说存在一个和策略无关的值来表示某一个状态。然后我们就可以利用这个状态的价值来进行决策。也就是说这里有一个先有鸡还是先有蛋的问题。我们是先有价值，还是先有策略。这里当然是先有价值，然后再进行决策。

但是，很显然，我们很难得到这个Value Function。要么是因为我们不是完全可观察的环境，要么就是我们根本无法计算这个Value Function。我们唯一能做的就是去估计这个Value Function。

怎么估计？

唯一的方法就是反复试验。

但是试验的过程中我们肯定得采取某一个策略，否则试验进行不下去。因此我们得到的reward都是在这个策略之下得到的，所以我们得到的value function显然也就是在这个策略下得到的value function。这只是实际得到的value function。

因此，我们就想，如果使用不同的策略进行无数次的实验，然后把最大的value function作为真正的value function。这样可以吗？这样当然可以啊。因为最大的value function肯定是唯一的。我们保证了唯一性，也就是可以基于这个来做判断。而使用最大值其实也是显而易见的，代表这这个状态的最大可能。既然每个状态的最大可能价值知道了，我们也就可以根据这个最大可能价值来做判断，得到的策略也就是最优策略Optimal Policy。这就实现了我们的初衷：得到状态的价值Value Function。

Bellman方程

没错，就是算法课讲的那种Bellman方程（编者注）

在上文我们介绍了Value Function价值函数，所以为了解决增强学习的问题，一个显而易见的做法就是----

我们需要估算Value Function

是的，只要我们能够计算出价值函数，那么最优决策也就得到了。因此，问题就变成了如何计算Value Function？

怎么估算价值呢？

我们还是先想想我们人是怎么估算的？我们还是以上面的投资决策问题来作为例子

一般我们基于以下几种情况来做评估：

  • 其他人的选择。比如有很多人投资股市失败，因此我们就会降低我们投资股票的价值。
  • 自己的反复试验。我们常常不是只做一次选择，而是做了很多次选择，从而收获了所谓的“经验”的东西。我们根据经验来评估选择的价值。比如我们做了好几次投资楼市的选择，结果大获成功，因此我们就会认为投资楼市是不错的选择。
  • 基于理性分析。我们根据我们已有的知识对当前的情况做分析，从而做出一定的判断。
  • 基于感性的逻辑。比如选择投资自己到人工智能领域。虽然我们大约觉得人工智能前景很好，但是我们真正要投资自己到这个领域有时候仅仅是出于一种热爱或者说一种理想主义。就是不管别人觉得好不好，反正我觉得好，我就这么选了。

计算机要如何才能评估价值呢？

  • 其他人的选择。不好意思，计算机只有自己，没有其他人。也许你会说多台计算机。如果是共用一个“大脑”做分布式计算，那还是只有自己。
  • 基于理性分析。不好意思，计算机在面对问题时往往什么都不知道，比如基于屏幕玩Atari游戏，计算机压根不知道看到的像素是个什么东西。它没有人类的先验知识，无法分析。（当然啦，先使用监督学习然后再增强学习的AlphaGo就是有先验知识的情况下做的增强学习）
  • 基于感性的逻辑。不好意思，计算机目前还产生不了感性。

那么，基于自己的反复试验呢？耶，这个可以啊。计算机这方面比人类强多了，可以24小时不分昼夜的反复试验，然后对价值做出正确的判断。

所以，Value Function从分析上是可以评估出来的，那具体该怎么评估呢？

我们下面将不得不引入点数学公式，虽然也会非常好理解。

还记得回报Result的基本定义吗？就是所有Reward的累加（带衰减系数discount factor）

Gt=Rt+1+λRt+2+...=∑k=0∞λkRt+k+1G_t=R_t+1+λR_{t+2}+...=\sum_{k=0}^∞λ^kR_{t+k+1}

那么Value Function该如何定义？也很简单，就是期望的回报啊！期望的回报越高，价值显然也就越大，也就越值得去选择。用数学来定义就是如下：

v(s)=E[Gt∣St=s]v(s)=E[G_t|S_t=s]（原文的E很特别，不会打）

接下来，我们把上式展开如下：

v(s)=E[Gt∣St=s]=E[Rt+1+λRt+2+λ2Rt+3+...∣St=s]=E[Rt+1+λ(Rt+2+λRt+3+...)∣St=s]=E[Rt+1+λGt+1∣St=s]=E[Rt+1+λv(St+1)∣St=s]\begin{aligned} v(s) &=E[G_t|S_t=s] \\ &=E[R_{t+1}+λR_{t+2}+λ^2R_{t+3}+...|S_t=s]\\ &=E[R_{t+1}+λ(R_{t+2}+λR_{t+3}+...)|S_t=s]\\ &=E[R_{t+1}+λG_{t+1}|S_t=s]\\ &=E[R_{t+1}+λv(S_{t+1})|S_t=s] \end{aligned}

因此，

v(s)=E[Rt+1+λv(St+1)∣St=s]v(s)=E[R_{t+1}+λv(S_{t+1})|S_t=s]

上面这个公式就是Bellman方程的基本形态。从公式上看，当前状态的价值和下一步的价值以及当前的反馈Reward有关。

它表明Value Function是可以通过迭代来进行计算的

 

迭代与Q-learning 算法

考虑下面这个简单的迷宫问题:

从入口(Start)走到出口(Goal)就算胜利. 小方格的位置就是我们状态S, 行为Action只有四种(上下左右), 回报函数就定为每远离一步Goal, 回报-1.

 

价值迭代

如果使用价值迭代算法，我们更新每个状态 ss 的长期价值 V(s)V(s)，这个价值是立即回报 r(s,a)r(s,a) 与下一个状态 s+1s+1 的长期价值的综合(想想是不是很有道理?)，从而获得更新:

有两个点要注意:

  1. 每次迭代, 对于每个状态 ss, 都要更新价值函数 V(s)V(s)
  2. 对于每个状态 ss的价值更新, 需要考虑所有行动Action的可能性, 这就非常消耗时间.

最后可以训练出所有状态s的价值, 大概是下面这样:

值得注意的是, 如果价值迭代完成后, 每个状态下一步的策略也就有了(选下一步价值较高的格子走, 就可以了)

 

策略迭代

如果使用收敛较快的策略迭代算法, 每次迭代我们分两步走:

第一步: 先任意假设一个策略 πkπ_k , 使用这个策略迭代价值函数直到收敛,

最后得到的 V(s)V(s) 就是我们用策略 πkπ_k , 能够取得的最好价值函数 V(s)V(s)了(其实是策略的一种评估)

第二步: 我们重新审视每个状态所有可能的行动Action, 优化策略 πkπ_k, 看看有没有更好的Action可以替代老的Action:

这样就最终优化了策略函数 πkπ_k 最终效果大概是这样的:

这就是策略迭代, 最后得到了每个状态应有的最佳策略.

正如我们开头说的, “是先用自己的”套路”边试边学, 还是把所有情况都考虑之后再总结”, 正是策略迭代与价值迭代的区别, 我们需要权衡考虑。

 

参考

https://zhuanlan.zhihu.com/p/134089340

https://github.com/Vay-keen/Machine-learning-learning-notes

https://github.com/familyld/Machine_Learning

https://zhuanlan.zhihu.com/p/25994179

https://leovan.me/cn/2018/12/ensemble-learning/

https://easyai.tech/ai-definition/ensemble-learning/

https://zhuanlan.zhihu.com/p/72415675

https://www.zhihu.com/question/63492375

https://www.zhihu.com/question/27068705

https://www.zhihu.com/question/19725590/answer/241988854

https://tangshusen.me/2018/10/27/SVM/

https://www.joinquant.com/view/community/detail/a98b7021e7391c62f6369207242700b2

https://zhuanlan.zhihu.com/p/79531731

https://github.com/Charmve/PaperWeeklyAI/blob/master/03_Maiwei AI PaperWeekly/03_机器学习%26深度学习理论/机器学习算法之——K最近邻(k-Nearest Neighbor，KNN)分类算法原理讲解.md

https://blog.csdn.net/zc02051126/article/details/49618633

https://zhuanlan.zhihu.com/p/127022333

https://0809zheng.github.io/2020/03/30/ridge.html

https://www.cnblogs.com/wuliytTaotao/p/10837533.html

https://link.springer.com/referenceworkentry/10.1007/978-1-4899-7687-1_910#Sec13186

http://palm.seu.edu.cn/zhangml/files/mla11-mll.pdf

https://blog.csdn.net/zwqjoy/article/details/80431496

https://ryuchen.club/posts/0x000034/ (推荐）

https://zhuanlan.zhihu.com/p/78798251

https://zhuanlan.zhihu.com/p/622244758

https://www.biaodianfu.com/hierarchical-clustering.html

https://zhuanlan.zhihu.com/p/411533418

https://zhuanlan.zhihu.com/p/33196506

https://www.cnblogs.com/wry789/p/13125658.html

https://blog.csdn.net/qq_41485273/article/details/113178117

https://www.jianshu.com/p/7d4323c28716

http://lunarnai.cn/2019/01/02/watermelon-chap-13/

【周志华机器学习】十三、半监督学习

https://zhuanlan.zhihu.com/p/411533418

https://www.huaxiaozhuan.com/统计学习/chapters/12_semi_supervised.html

https://blog.csdn.net/tyh70537/article/details/80244490

https://zhuanlan.zhihu.com/p/37747650

7125messi.github.io

https://blog.csdn.net/qq_40722827/article/details/104515955

https://www.cnblogs.com/dyl222/p/11055756.html

https://www.zhihu.com/tardis/zm/art/392908965

https://blog.csdn.net/j123kaishichufa/article/details/7679682

https://www.cnblogs.com/heaad/archive/2011/01/02/1924088.html

https://www.cnblogs.com/stevenlk/p/6543628.html

baidinghub.github.io-PCA

baidinghub.github.io-LDA

等等