在本文中，我们将学习贝尔曼方程和价值函数。
 
 
回报和返还（return）
 正如前面所讨论的，强化学习agent如何最大化累积未来的回报。用于描述累积未来回报的词是返还，通常用R表示。我们还使用一个下标t来表示某个时间步长的返还。在数学符号中，它是这样的:
 
 
 
 
如果我们让这个级数趋于无穷，那么我们最终会得到无限的返还，这对于问题的定义并没有太大意义。因此，只有在我们期望返还的级数终止时，这个方程才有意义。我们将这种总是终止的任务称为“插曲式”（episodic）。纸牌游戏是解释“插曲式”问题的好例子。“插曲”开始于对每个人发牌，并且不可避免地会随着游戏规则的不同而结束。然后，下一“插曲”又开始了另一回合的游戏。
 
 
相比使用未来的累积回报作为返还，更常见的是使用未来的累积折现回报（cumulative discounted reward）:
 
 
 
 
其中0<γ<1。以这种方式定义返还的两个好处是，返还在无穷级数中得到了很好的定义，而且它把更大的权重给了更早的回报，这意味着我们更关心即将得到的回报，而不是将来会得到更多的回报。我们为γ选择的值越小就越正确。这种情况在我们让γ等于0或1时就可以看到。如果γ等于1，这个方程就变成了对所有的回报都同样的关心，无论在什么时候。另一方面，当γ等于0时，我们只关心眼前的回报，而不关心以后的回报。这将导致我们的算法极其短视。它将学会采取目前最好的行动，但不会考虑行动对未来的影响。
 
 
策略
 一个策略，写成π(s, a)，描述了一种行动方式。它是一个函数，能够采取一个状态和一个行动，并返回在那个状态下采取这个行动的概率。因此，对于一个给定的状态，即
 
 
 
 
必须是真实的。在下面的例子中，当我们“饥饿”的时候，我们可以在两种行为之间做出选择，要么“吃”，要么“不吃”。
 
 
 
 
我们的策略应该描述如何在每个状态中采取行动，所以一个等概率的随机策略看起来就像
 
 
 
 
，在这里
 
 
 
 
（Eat）是行为“吃”，而
 
 
 
 
（Don’t Eat）是“不吃”。这意味着，如果你处于“饥饿”状态，选择“吃”和“不吃”的概率是相等的。
 
 
我们在强化学习中的目标是学习一种最优策略，定义为
 
 
 
 
。最优策略告诉我们如何采取行动来最大化每个状态的返还。因为这是一个很简单的例子，所以很容易看出，在这种情况下，最优策略是在“饥饿”时总是“吃”，那么就是
 
 
 
 
。在这个实例中，对于许多马尔可夫决策来说，最优策略是确定的。每个状态都有一个最优的行动。有时这被写成
 
 
 
 
，它是从状态到这些状态中的最优行动的映射。
 
 
价值函数
 为了学习最优策略，我们利用了价值函数。在强化学习中有两种类型的价值函数:状态值函数（state value function），用V(s)表示，和行动值函数，用Q(s，a)表示。
 
 
状态值函数在遵循策略时描述一个状态的值。当从状态的行为以我们的策略π开始时，这就是预期的返还。
 
 
 
 
需要注意的是，即使在相同的环境中，价值函数也会根据策略发生变化。这是因为状态的价值取决于你的行动，因为你在那个特定的状态下的行动会影响你期望看到的回报。同时还要注意期望的重要性。期望（expectation）就像一个平均值;它就是你期望看到的返还。我们使用期望的原因是当你到达一个状态后会发生一些随机事件。你可能有一个随机的策略，这意味着我们需要把我们采取的所有不同行动的结果结合起来。此外，转换函数（transition function）可以是随机的，也就是说，我们可能不会以100%的概率结束任何状态。请记住上面的例子:当你选择一个行动时，环境将返回下一个状态。即使给出一个行动，也可能会有多个状态返还。当我们看贝尔曼方程时，会看到更多这样的情况。期望将所有这些随机因素考虑在内。
 
 
我们将使用的另一个价值函数是行动值函数。行动值函数告诉我们当跟随某个策略时，在某些状态下执行某个行动的值。给出状态和在π下的行动，这是期望的返还:
 
 
 
 
对状态值函数的注释同样适用于行动值函数。根据该策略，期望将考虑未来行动的随机性，以及来自环境的返还状态的随机性。
 
 
贝尔曼方程
 理查德·贝尔曼推导出了以下公式，让我们可以开始解决这些马尔可夫决策问题。贝尔曼方程在强化学习中无处不在，对于理解强化算法的工作原理是非常必要的。但在我们了解贝尔曼方程之前，我们需要一个更有用的符号，定义为
 
 
 
 
和
 
 
 
 
，如下所示:
 
 
 
 
 
 
是过渡概率。如果我们从状态s开始，然后采取行动a，我们就会得到状态
 
 
 
 
和概率
 
 
 
 
。
 
 
 
 
 
 
是另一种写为期望(或平均)回报的方式，我们从状态s开始，采取行动a，然后移动到状态
 
 
 
 
。
 
 
最后，有了这些条件，我们就可以推导出贝尔曼方程了。我们将考虑贝尔曼方程的状态值函数。根据返还的定义，我们可以重写方程(1)，如下所示:
 
 
 
 
如果我们从求和中得到第一个回报，我们可以这样重写它:
 
 
 
 
这里的期望描述的是，如果我们继续遵循策略π的状态s，我们期望返还的是什么。通过对所有可能的行动和所有可能的返还状态的求和，可以明确地编写为期望。下面的两个方程可以帮助我们完成下一个步骤。
 
 
 
 
通过在这两个部分之间分配期望，我们就可以把我们的方程转化成：
 
 
 
 
注意，方程（1）与这个方程的末尾形式相同。我们可以替换它，得到：
 
 
 
 
贝尔曼方程的行动值函数可以以类似的方式进行推导。本文结尾有具体过程，其结果如下：
 
 
 
 
贝尔曼方程的重要性在于，它们让我们表达了其它状态的价值。这意味着，如果我们知道
 
 
 
 
的值，我们可以很容易地计算出
 
 
 
 
的值。这为计算每个状态值的迭代方法打开了大门，因为如果我们知道下一个状态的值，我们就可以知道当前状态的值。最重要的事情是我们需要记住一些编号方程。最后，在贝尔曼方程中，我们可以开始研究如何计算最优策略，并编码我们的第一个强化学习agent。
 
 
在我们推导出贝尔曼方程的过程中，我们得到了这一系列的方程，从方程(2)开始:
 
 
 
 

 

   
  
 
    
    
    
    
    
  
 
 

在明白了马尔科夫流程了(上一节)之后,我们可以真正的谈一谈策略
 
首先:什么是策略
 
策略就是智能体在面对不同的S(状态)时选择动作过程一般用π表示, 所以可知实际上策略就是我们要的最终成果, 而策略又分为两种: 决定性策略和随机性策略
 
决定性策略
 
决定性策略是一种状态与动作的映射关系, 是一种将状态与动作相互绑定的一种状态, 比如开车, 看到红灯则停止, 看见绿灯则运行, 策略在中间起到映射的作用, 可以将策略理解成工厂, 输入状态得到相应的动作表示为:
 S --> 策略 --> A : π S->A
 
随机性策略
 
随机性策略是一种状态和动作对概率的一个映射,之前捡垃圾的机器人就是一个很典型的随机性策略, 比如: 机器人在电量高的时候是否去搜索是不确定的, 这时候政策课可以表示为:
 S,A --> 策略 -->S状态下选择A动作的概率
 可表示为: $\pi (a|s)=P(A_t=a|S_t=s)$
 
状态值函数
 
对于策略来说它的重点是要确定他的策略值函数
 
 也就是对于每个状态, 如果智能体从s开始, 在所有时间步内根据该策略选择运作, 预期的回报
 然后我们就可以通过选择走到预期回报高的地方来努力得到最高的回报, 以经典的网格世界为例
 我们以这个网格为例, 机器人初始状态在原点位置, 我们的目标是到达旗子位置, 我们设定为智能体每次移动获得奖励-1, 当经过山时奖励为-3, 我们的目的是以最大奖励到达旗子位置
 为了达到这个目标我们要计算出在每个网格的预期的奖励值也就是状态值, 然后我们只要通过走预期值较高的状态就能达到我们的目的, 那我们要怎么计算状态值就是我们现在的问题
 
我们首先假设以从左到右, 从上到下的方式行走可以计算出每个网格的状态值
 
 也很容易理解, 每个网格的状态值等于下个状态的状态值加上走到这里所得到的预期奖励, 通常还有一个折扣率 状态值=下一个状态值+折扣率*预期奖励, 这里为了方便不考虑折扣率, 这就是贝尔曼方程, 贝尔曼预期方程
 这一状态的值 = 即时奖励 + 下一状态的折扣值
 但是一般的MDP中 智能体并非始终能完全控制下一个状态是什么, 而且奖励也是从概率分布中抽取的, 所以如果是确定性策略应该为:
 
 随机性策略应该为
 
 
至于如何真正得到我们的状态值, 容易想到, 如果只有九个方格我们可以用解方程的方式来拿到值, 但是在实际的应用中使用解方程的方式来算肯定是不现实, 一般我们会采用迭代的方式来计算值, 这个我们在下一节说, 首先要理解什么事状态值以及状态值函数, 他是怎么来的
 
动作值函数
 
在知道状态值了之后我们就可以尝试理解动作值函数了, 首先假设我们已经得到了状态值函数, 我们的想法是走到状态值高的地方相对来说我们就可以得到更高的预期收益, 但是当智能体在做出一个动作的时候是不能确定是否能够到达预期期望较高的网格(为了简化问题, 解释动作值, 我们在接下来的例子中每个动作的预期状态是确定的, 在我们下一节的实际代码中我们会采取不确定的形式), 我们在每个状态下真正能决定的是采取什么样的动作, 所以当我们只要采取预期期望较高的动作就可以了
 那么我们要怎么去计算我们的动作值呢? 依然以上面的网格世界为例:
 
 我们已经拿到了各个网格的状态值,不难发现在网格世界中, 最多有四个动作上下左右(边框及角落的有三个和两个动作), 我们用这样的网格表示四个动作的预期值:
 
 这个值要怎么计算呢? 很简单, 只要使得这个动作的奖励加上这个动作所有的可能达到的状态乘以概率就可以了(这里达到的状态是确定的为1), 这就拿到了这个网格世界的动作值函数, 如图(你可以试着自己计算):
 
 我们用公式表示一下动作值:
 
 解释一下这个公式, 这个公式是:
 在s状态下a动作的预期奖励为 对于在s状态下采取a动作每个可能的下一状态及得到相应奖励的概率乘以到达下一个状态的概率加上折扣倍的下一状态的状态值
 理解起来可能有些复杂, 我们已经从理论上证明了这个公式, 如果你有兴趣的话可以看一下他的数学推导, 我放在最后
 
总结
 
这时候我们就可以去讨论这几个词的意义了 策略、状态值、动作值
 
通过上面的讲解我们可以发现, 我们通过策略得到状态值, 通过状态值可以得到动作值, 但是你发现了吗如果我们得到了动作值之后如果我们在每个状态都采用预期奖励高的动作那么就得到了一个新的、更好的策略, 那么我们就引出了我们计算最优策略的办法, 我们可以先随便指定一个随机策略, 然后通过不断迭代的方式得到更好的策略, 直到策略收敛, 我们在下一节将用代码实现, 这里我们先写一下流程:
 
新建一个随机策略
 ->计算策略值
 ->计算动作值
 ->得到更优的策略
 if 新策略 == 当前策略:
 返回这个策略
 else:
 返回第一步
 
附录
 

1.python函数如何返回多个值    
 
        Python函数的返回语句return严格意义上来说只能返回一个值，可以是任何类型，因此，可以通过返回一个“tuple”（定值表）类型值来间接达到返回多个值的目的。示例代码如下：
 
def    res ( x, y ):
 
         a = x % y
 
         b = (x-a) / y
 
         return(a,b)    #也可以写作  return a,b
 
2.调用函数时分别接收多个值
 
   接收python返回的多个值时有两种方法，一种是建立变量进行接收，一种是操作字符串的方式进行接收，示例代码分别如下：
 
（1）操作字符串方式
 
  result = res(2,1)
 
  print(res[0],res[1])   #打印结果为：2，1
 
（2）建立变量方式
 
  r1,r2 = res(2,1)
 
  print(r1,r2)    #打印结果为：2，1
 
3.返回值为空或无返回值
 
     在Python中，当程序执行到return的时候，程序将停止执行函数内余下的语句。return并不是必须的，当没有return, 或者return后面没有返回值时，函数将自动返回None。None是Python中的一个特别的数据类型，用来表示什么都没有，相当于C语言中的NULL。None多用于关键字参数传递的默认值。示例代码如下：
 
a = None
 
b = None
 
def  res(x,y):
 
       a = x%y
 
       b = (x-a) / y 
 
result = res(2,1)
 
print(result)    #结果应为“None"

问题背景：

 A：这个函数的圈复杂度降不下去了，只能这样了


 B：现在的圈复杂度是多少？


 A：17


 B：这么高，怎么会降不了？


 A：要拆函数也可以拆，只是不想拆出那么多没意义的函数。


 


问题描述：

 怎样的函数才算是有意义的函数？


 比如这样的函数有没有意义？


 （1）只被调用一次的函数


 （2）只有一句实现内容的函数


 （3）函数很多的参数


 比如一个函数，有很多局部变量，如果要拆成多个函数，那么每个函数都要传递这些局部变量，会造成函数的参数很多。


 



 在直接回答这个问题之前，先分析一下把一个大函数拆分多个小函数的优点与缺点。


 


拆分函数的优点：

 （1）抽象级上的封装，一个函数里的所有语句都是同一个抽象级的


 （2）相关概念的封装，一个函数里的所有语句都是为了做同一件事，达到同一个目的


 （3）不相关概念的区分，不同的事分别放在不同的函数里，改名相互干扰


 （4）让代码更易阅读


 总结：读得方便


 


拆分函数的缺点：

 （1）加一个函数麻烦，又只被调用一次，写得不值


 （2）写得时候需要跳跃思考


 第一遍写代码时，常常是想到哪就写到哪，不管是业务逻辑还是算法细节，都是按照执行顺序一步一步地往下写


 但拆分函数时，不是按照执行顺序去思考代码的，而是按照抽象级去思考代码的。


 （3）函数调用开销


 这通常是最次要的原因，几乎可以忽略


 （4）代码相关耦合性太高，难以拆分


 就像《问题描述》中的（3）


 （5）拆分函数又要考虑起名字的问题


 总结：写得不方便


 


回到前面的问题：

 一个函数到底有没有意义，说到底就是写得方便与读得方便的权衡问题。


 怎样权衡呢，这里以数组与链表的区别为例。


 数组和链表都是线性结构的数据组织方式，究竟哪种方式更好呢？


 应该说各有各的优缺点。数组方式相对链表来说读效率高O(1)，写效率低O(n)。链表方式相对数组方式来说，读效率低O(n/2)，写效率高O(n/2)。


 在实际应用中，以读为主的实现通常用数组，以写为组的实现通过用链表。


 在拆分函数这个问题上，我们要考虑我们在开发过程中，是以写为主？还是以读为主？


 Uncle Bob刚好在这方便做过一些统计，他发现，即使是在开发过程中，大部分时间也是在读代码的。


 那么更何况后期维护，即使是修改代码，也是要以读懂代码为基础的。


 很显然，我们的开发是以读为主的，因此，便于阅读的代码就是有意义的代码。适当地牺牲“写的方便性”来实现“读的方便性”是有必要的。


 


就事论事：

 （1）只被调用一次的函数是否有意义？


 答：如果它有助于阅读，就是有意义的，比如init();


 （2）只有一句实现内容的函数是否有意义？


 答：如果它有助于阅读，就是有意义的，比如将多个判断条件合并


 （3）有很参数的函数是否有意义？


 答：如果“读得方便”的代价是“写得很不方便”，这并不意味着它不应该被拆分。而是说明这个函数本身设计不合理。它不只要被拆分，更要被重构。


 


怎样让函数变成有意义：

 （1）在第一次写代码时，常常是跟着灵感走，所以会写得杂乱无章，如果用TDD会好一点


 （2）即使在写的时候没有TDD，最终也是要把UT补全的。


 （3）有了UT，就可以放心大胆地重构，这是一个很大的话题


 


哪些代码可以拆分？

 （1）函数缩进达到3级。（假设一开始是1级）


 （2）函数长度超过12行


 （3）几乎相似的代码出现了3遍


 （4）判断条件3个以上


 （5）函数参数3个以上


 （6）不得不使用注释


 （7）代码逻辑明显分成几块