Preliminary of RL Ⅰ：Markov & Value function

马尔可夫决策过程MDP

马尔可夫模型的几类子模型

各种马尔可夫子模型的关系:

马尔可夫决策过程

一个马尔可夫决策过程由一个五元组构成  :

• S: 表示状态集(states)，有​  ，​  表示第i步的状态。
• A: 表示一组动作(actions)，有  ​，  ​表示第i步的动作。
•  : 表示状态转移概率。​  表示的是在当前​  状态下，经过  ​作用后，会转移到的其他状态的概率分布情况。比如，在状态 s 下执行动作​，转移到 s' 的概率可以表示为  ​。
•  : R是回报函数(reward function)。有些回报函数状态 ​S 的函数，可以简化为  ​。如果一组​  转移到了下个状态  ​，那么回报函数可记为  ​。如果  ​对应的下个状态 s' 是唯一的，那么回报函数也可以记为​ 。
•  ​: discount rate，作为未来回报的折扣。

MDP 的动态过程如下：某个智能体(agent)的初始状态为​  ，然后从 A 中挑选一个动作  ​执行，执行后，agent 按​  概率随机转移到了下一个​  状态，  ​。然后再执行一个动作​  ，就转移到了  ​，接下来再执行​…，我们可以用下面的图表示状态转移的过程。

如果回报r是根据状态s和动作a得到的，则MDP还可以表示成下图：

值函数(value function)

强化学习学到的是一个从环境状态到动作的映射（即行为策略），记为策略​  。而强化学习往往又具有延迟回报的特点: 如果在第 n 步输掉了棋，那么只有状态​  和动作  ​获得了立即回报​  ，前面的所有状态立即回报均为0。所以对于之前的任意状态s和动作a，立即回报函数 r(s,a) 无法说明策略的好坏。因而需要定义值函数(value function，又叫效用函数)来表明当前状态下策略π的长期影响。

状态值函数(state value function)

重点看第三个式子

其中：

a)是采用策略π的情况下未来有限h步的期望立即回报总和；

b)是采用策略π的情况下期望的平均回报；

c)是值函数最常见的形式，式中γ∈[0,1]称为折合因子，表明了未来的回报相对于当前回报的重要程度。特别的，γ=0时，相当于只考虑立即不考虑长期回报，γ=1时，将长期回报和立即回报看得同等重要。

给定策略π和初始状态s，则动作  ​，下个时刻将以概率​  转向下个状态  ​，那么上式的期望可以拆开，可以重写为：

注意：在​  中，π和初始状态s是我们给定的，而初始动作a是由策略π和状态s决定的，即a=π(s)。

动作值函数(action value function Q函数)

给定当前状态s和当前动作a，在未来遵循策略π，那么系统将以概率p(s'|s,a)转向下个状态s'，上式可以重写为：

在  中，不仅策略 π 和初始状态 s 是我们给定的，当前的动作 a 也是我们给定的，这是  和  ​的主要区别。

在得到值函数后，即可列出MDP的最优策略：

即我们的目标是寻找的是在任意初始条件s下，能够最大化值函数的策略π*。

Reference:

转自 Kintoki's blog