Q-learning理解、实现以及动态分配应用（二）

太过爱你忘了你带给我的痛 2022-04-12 07:13 262阅读 0赞

## 1.2 K摇摆赌博机 ##

首先我们考虑强化学习最简单的情形：仅考虑一步操作，即在状态x下只需执行一次动作a便能观察到奖赏结果。易知：欲最大化单步奖赏，我们需要知道每个动作带来的期望奖赏值，这样便能选择奖赏值最大的动作来执行。若每个动作的奖赏值为确定值，则只需要将每个动作尝试一遍即可，但大多数情形下，一个动作的奖赏值来源于一个概率分布，因此需要进行多次的尝试。

单步强化学习实质上是K-摇臂赌博机（K-armed bandit）的原型，一般我们尝试动作的次数是有限的，那如何利用有限的次数进行有效地探索呢？这里有两种基本的想法：

*      仅探索法：将尝试的机会平均分给每一个动作，即轮流执行，最终将每个动作的平均奖赏作为期望奖赏的近似值。
 *      仅利用法：将尝试的机会分给当前平均奖赏值最大的动作，隐含着让一部分人先富起来的思想。

可以看出：上述两种方法是相互矛盾的，仅探索法能较好地估算每个动作的期望奖赏，但是没能根据当前的反馈结果调整尝试策略；仅利用法在每次尝试之后都更新尝试策略，符合强化学习的思（tao）维（lu），但容易找不到最优动作。因此需要在这两者之间进行折中。

### 1.2.1 ε-贪心 ###

ε-贪心法基于概率来对探索和利用进行折中，具体而言：在每次尝试时，以ε的概率进行探索，即以均匀概率随机选择一个动作；以1-ε的概率进行利用，即选择当前最优的动作。ε-贪心法只需记录每个动作的当前平均奖赏值与被选中的次数，便可以增量式更新。ε是基于概率进行探索，ε作为随机选择一个摇臂的概率，那么1-ε的概率用于从平均奖赏最大的摇臂里面选择。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

**贪心与动规的关键区别：**

**  看是否用到之前的最优解，如果用到就是动态规划，否则就是贪心，贪心无法解决动态规划的问题，但是动态规划能解决贪心的问题。**

ε-贪心法python代码模拟仿真：

from numpy import random  
K = \[1,2,3,4,5\] \# 总共的摇臂数有5个  
R = \{1:2,2:3,3:5,4:1,5:9\}  \# 各个摇臂对应的奖赏  
prob = \{1:0.6,2:0.5,3:0.2,4:0.7,5:0.05\}  \#各个摇臂对应的概率吐币的概率  
T = 10000  
eplison = 0.1 \#ε探索概率  
count = dict(zip(list(range(1,6)),\[0\]\*5))  \# 计算每个摇臂的摇到的次数

\#zip函数：接受任意多个（包括0个和1个）序列作为参数，返回一个tuple列表

\#使用zip函数, 把key和value的list组合在一起, 再转成字典(dict).  
r = 0  
for i in range(T):  
    Q = dict(zip(list(range(1,6)),\[0\]\*5))  \#  
    if random.random() < eplison:   \#  
        k = random.choice(K)   \#  
    else:  
        k = max(Q,key=Q.get)    \#  
    v = random.choice(\[R\[k\],0\],p=\[prob\[k\],1-prob\[k\]\])    \#  
    r += v  
    Q\[k\] = (Q\[k\]\*count\[k\]+v)/(count\[k\]+1)    \#\# Q(i) 表示第i个摇臂的平均奖赏\# ε-贪心法只需记录每个动作的当前平均奖赏值与被选中的次数，便可以增量式更新

count\[k\] = count\[k\] + 1  
print("end the reword is \{\}".format(r))  \# 输出累计奖赏

*  end the reword is 11754

为了对比，我们在写一种随机选择的方式：

r = 0  
for i in range(T):  
    k = random.choice(K)  
    v = random.choice(\[R\[k\],0\],p=\[prob\[k\],1-prob\[k\]\])  
    r+=v  
print("end the reword is \{\}".format(r))

*  end the reword is 9556

经过我多次运行对比，大家也可以去跑一p，使用ε-贪心算法的结果总是比随机好。

###  **1.2.2 Softmax** ###

**Softmax算法则基于当前每个动作的平均奖赏值来对探索和利用进行折中，Softmax函数将一组值转化为一组概率**，值越大对应的概率也越高，因此当前平均奖赏值越高的动作被选中的几率也越大。Softmax函数如下所示：

![20181202103430572.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 1][]

在贪心算法中，[![image][]][image 1]的取值是由用户选取的。softmax算法中摇臂概率的分配是基于Boltzmann分布[![image][image 2]][image_image 2]

### Boltzmann分布 ###

在统计学习中，如果我们将需要学习的模型看成高温物体，将学习的过程看成一个降温达到热平衡的过程，最终模型的能量将会收敛为一个分布，并且在全局极小能量上下波动。这个过程称为“模拟退火”。而模型能量收敛到的分布称为玻尔兹曼分布（Boltzmann Distribution）。

在统计学中，玻尔兹曼分布给出了一个系统在特定状态能量和系统温度下的概率分布：

![201812021550524.png][]

其中pi是状态i出现的概率，Ei是状态能量，k是玻尔兹曼常数，T是系统的温度，M是系统的状态数量（系统状态是离散的，有限的；找到了一点高中物理原子的电子跃迁的感觉，那状态也是离散的！！！）。所以说，统计学中玻尔兹曼分布的使用是受到了物理中热力学的启发。

从玻尔兹曼分布的定义，我们可以发现系统的两个不同状态的概率之比仅与系统能量有关：

![20181202155134577.png][]

这个比值被称为玻尔兹曼因子（Boltzmann Factor）。

**机器学习模型训练中的最小代价和极大似然的等价性**

在一般的机器学习中，我们有一些观察数据X和对应的分类Y，建立模型函数f，则对应的代价函数为

![20181202155330992.png][]  
我们希望模型输出f(X)逼近分类Y，就要最小化代价函数E(X)。这里的代价函数E(X)其实可以看成系统状态的能量，而最小化的E(X)就是系统的稳态能量了。按照前面所说，它应该服从玻尔兹曼分布。从而，系统获得观察数据X的概率可以估计为

![20181202155408800.png][]

从概率统计的角度看，常用极大似然的思想来估计参数。而在上式中，极大似然等价于最小化系统的能量函数。

许多机器学习的论文一来就把代价函数写成自然常数e的指数，然后通过最大化求参数，其依据就是上式。也有很多论文用代价函数的形式求最小化。这两者通过玻尔兹曼分布联系在一起，是等价的。

转载：[https://blog.csdn.net/hanlin\_tan/article/details/62078935][https_blog.csdn.net_hanlin_tan_article_details_62078935]

### 1.3 有模型学习 ###

若学习任务中的四个要素都已知，即状态空间、动作空间、转移概率以及奖赏函数都已经给出，这样的情形称为“有模型学习”。假设状态空间和动作空间均为有限，即均为离散值，这样我们不用通过尝试便可以对某个策略进行评估。

### 1.3.1 策略评估 ###

前面提到：在模型已知的前提下，我们可以对任意策略的进行评估（后续会给出演算过程）。一般常使用以下两种值函数来评估某个策略的优劣：

*      状态值函数（V）：V（x），即从状态x出发，使用π策略所带来的累积奖赏；
 *      状态-动作值函数（Q）：Q（x,a），即从状态x出发，执行动作a后再使用π策略所带来的累积奖赏。

根据累积奖赏的定义，我们可以引入T步累积奖赏与r折扣累积奖赏：

![2018120210370275.png][]

![20181202103712550.png][]

由于MDP具有马尔可夫性，即现在决定未来，将来和过去无关，我们很容易找到值函数的递归关系：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 2][]

类似地，对于r折扣累积奖赏可以得到：

![20181202103744556.png][]

易知：**当模型已知时，策略的评估问题转化为一种动态规划问题**，即以填表格的形式自底向上，先求解每个状态的单步累积奖赏，再求解每个状态的两步累积奖赏，一直迭代逐步求解出每个状态的T步累积奖赏。算法流程如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 3][]

对于状态-动作值函数，只需通过简单的转化便可得到：

![这里写图片描述][SouthEast]

### **1.3.2 策略改进** ###

理想的策略应能使得每个状态的累积奖赏之和最大，简单来理解就是：不管处于什么状态，只要通过该策略执行动作，总能得到较好的结果。因此对于给定的某个策略，我们需要对其进行改进，从而得到**最优的值函数**。

![20181202103821464.png][]

![20181202103828701.png][]

最优Bellman等式改进策略的方式为：**将策略选择的动作改为当前最优的动作**，而不是像之前那样对每种可能的动作进行求和。易知：选择当前最优动作相当于将所有的概率都赋给累积奖赏值最大的动作，因此每次改进都会使得值函数单调递增。

![20181202103837945.png][]

将策略评估与策略改进结合起来，我们便得到了生成最优策略的方法：先给定一个随机策略，现对该策略进行评估，然后再改进，接着再评估/改进一直到策略收敛、不再发生改变。这便是策略迭代算法，算法流程如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 4][]

可以看出：策略迭代法在每次改进策略后都要对策略进行重新评估，因此比较耗时。若从最优化值函数的角度出发，即先迭代得到最优的值函数，再来计算如何改变策略，这便是值迭代算法，算法流程如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 5][]

### 1.4 蒙特卡罗强化学习 ###

在现实的强化学习任务中，环境的转移函数与奖赏函数往往很难得知，因此我们需要考虑在不依赖于环境参数的条件下建立强化学习模型，这便是免模型学习。蒙特卡罗强化学习便是其中的一种经典方法。

由于模型参数未知，状态值函数不能像之前那样进行全概率展开，从而运用动态规划法求解。一种直接的方法便是通过采样来对策略进行评估/估算其值函数，蒙特卡罗强化学习正是基于采样来估计状态-动作值函数：对采样轨迹中的每一对状态-动作，记录其后的奖赏值之和，作为该状态-动作的一次累积奖赏，通过多次采样后，使用累积奖赏的平均作为状态-动作值的估计，并引入ε-贪心策略保证采样的多样性。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 6][]

在上面的算法流程中，被评估和被改进的都是同一个策略，因此称为**同策略蒙特卡罗强化学习算法**。引入ε-贪心仅是为了便于采样评估，而在使用策略时并不需要ε-贪心，那能否仅在评估时使用ε-贪心策略，而在改进时使用原始策略呢？这便是**异策略蒙特卡罗强化学习算法**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 7][]

### 1.5 AlphaGo原理浅析 ###

本篇一开始便提到强化学习是AlphaGo的核心技术之一，刚好借着这个东风将AlphaGo的工作原理了解一番。正如人类下棋那般“手下一步棋，心想三步棋”，Alphago也正是这个思想，当处于一个状态时，机器会暗地里进行多次的尝试/采样，并基于反馈回来的结果信息改进估值函数，从而最终通过增强版的估值函数来选择最优的落子动作。

其中便涉及到了三个主要的问题：（1）如何确定估值函数（2）如何进行采样（3）如何基于反馈信息改进估值函数，这正对应着AlphaGo的三大核心模块：深度学习、蒙特卡罗搜索树、强化学习。

1.深度学习（拟合估值函数）

由于围棋的状态空间巨大，像蒙特卡罗强化学习那样通过采样来确定值函数就行不通了。在围棋中，状态值函数可以看作为一种局面函数，状态-动作值函数可以看作一种策略函数，若我们能获得这两个估值函数，便可以根据这两个函数来完成：(1)衡量当前局面的价值；(2)选择当前最优的动作。那如何精确地估计这两个估值函数呢？这就用到了深度学习，通过大量的对弈数据自动学习出特征，从而拟合出估值函数。

2.蒙特卡罗搜索树（采样）

蒙特卡罗树是一种经典的搜索框架，它通过反复地采样模拟对局来探索状态空间。具体表现在：从当前状态开始，利用策略函数尽可能选择当前最优的动作，同时也引入随机性来减小估值错误带来的负面影响，从而模拟棋局运行，使得棋盘达到终局或一定步数后停止。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 8][]

> **3.强化学习（调整估值函数）**

在使用蒙特卡罗搜索树进行多次采样后，每次采样都会反馈后续的局面信息（利用局面函数进行评价），根据反馈回来的结果信息自动调整两个估值函数的参数，这便是强化学习的核心思想，最后基于改进后的策略函数选择出当前最优的落子动作。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 9][]

转载：https://blog.csdn.net/u011826404/article/details/75576856

Q-学习的目标是寻找一个策略可以最大化将来获得的报酬。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20220412/0c21268e2f8f444293c6d194e7f53c7e.png
[20181202103430572.png]: /images/20220412/c79c19faf1704c3a941d2624c61e6709.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 1]: /images/20220412/d7e69d91df0f44debc010c78f66f4d7c.png
[image]: /images/20220412/8ccee575f4cc43f3a0b2d6d5c7b26e8a.png
[image 1]: http://images2015.cnblogs.com/blog/509266/201605/509266-20160531091125836-704510800.png
[image 2]: http://images2015.cnblogs.com/blog/509266/201605/509266-20160531091127633-1083977778.png
[image_image 2]: http://images2015.cnblogs.com/blog/509266/201605/509266-20160531091127149-2073513392.png
[201812021550524.png]: /images/20220412/7d469d1908ca4f929b2574b3c7d5a698.png
[20181202155134577.png]: /images/20220412/f859e4bd5caa4682bf0b9acb82e400d7.png
[20181202155330992.png]: /images/20220412/98317cfb12ce410c849c3d3ada74ba12.png
[20181202155408800.png]: /images/20220412/f45abce9099f46119b68140df57eefee.png
[https_blog.csdn.net_hanlin_tan_article_details_62078935]: https://blog.csdn.net/hanlin_tan/article/details/62078935
[2018120210370275.png]: /images/20220412/08391fdcc0d94c92a6cc9ebac42b213f.png
[20181202103712550.png]: /images/20220412/e1d709309cd242c6a26bb8cdb23e9bfe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 2]: /images/20220412/55fe808095384ea0a1320f3a83f318fa.png
[20181202103744556.png]: /images/20220412/5c8ef95431af43379c7c083b31f0fbc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 3]: /images/20220412/60b3367645bf4575ba41160e4da2792b.png
[SouthEast]: /images/20220412/bf6e57bcacd9409986c7e8caa4cad872.png
[20181202103821464.png]: /images/20220412/01d4b43c25364f84a8afa4e6409d8167.png
[20181202103828701.png]: /images/20220412/f2b8aa4194ad4cfca37c70694136dae3.png
[20181202103837945.png]: /images/20220412/df4701d191b14615b512ee92bed20cd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 4]: /images/20220412/8587a38bbde14f89beba6297857b8e7e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 5]: /images/20220412/9d4db44950c54b1fae063022cb6df442.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 6]: /images/20220412/559a0da39c0c433e97ec7e5fbb7baf47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 7]: /images/20220412/9c2e5269ab1c4708b97a971e47a975fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 8]: /images/20220412/5ecb3d7760c4495c9d7a43c0f9ebcd81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 9]: /images/20220412/f502fe41f4d946f2963647f2895d361f.png