学习增强学习

Tags:

马尔可夫决策过程

马尔可夫决策过程(Markov decision process,下文简称MDP),可用来处理一些最优化问题,譬如非常出名的动态规划问题,以及本文的核心——增强学习问题。

MDP的定义

MDP包含5个东西:\(S、A、P、R、\gamma \)

  • S(State),指的是目标系统的所有状态的集合

  • A(Action),状态之间的转换行为。可以把状态S想象成一堆节点,而A就是各个节点之间的有向连线集合

  • P(probability),\(P_{a}(s,s')\),某状态\(s\)通过某行为a进入另一个状态\(s'\)的概率

  • R(Rewawrd),\(R_{a}(s,s')\),某状态\(s\)通过某行为a进入另一个状态\(s'\)能获得的奖励值

  • \(\gamma \) (Discount Factor),用于奖励值计算的一个系数,表示非立即奖励(future rewards)相对于立即奖励(present rewards)的重要程度,当为1时表示同等重要,小于1时表示非立即奖励要打个折,等于0时表示只考虑立即奖励。因此有\( 0 \leq \gamma \leq 1 \)。注意,\(\gamma \) 是一个常数

因为一般来说,状态之间是有时间先后顺序的(拓扑结构),所以每个状态s有它自己的固有属性t,表示这个s处于时间轴上的位置。

在MDP的定义中没有指出S、A是不是有限集合(finite),但在实际应用MDP时,必然是有限的。

MDP的直观表示是一个有向图:

1.png (from wiki)

MDP的核心问题

MDP的核心核心是找出一个最理想的策略函数\(\pi ^{*} (s)\)给做决策的人,这个\(\pi ^{*}(s)\)决定了当处于状态s时,应采取哪个行为a,即\( a_{t} = \pi ^{*} (s_{t})\)。

这个问题的解决方案是:求出一个叫做折算累积奖励(discounted cumulative reward)多项式的最大值,此时的\(\pi (s)\)就是最优解\(\pi ^{*}(s)\)。公式化表示就是:

\[ r_{t} = R_{ a_{t} }(s_{t}, s_{t+1} ) \]

\[ V ^{\pi } (s_{t}) = r_{t} + \gamma r_{t+1} + \gamma ^{2} r_{t+2} + \cdots = \sum _{i=0}^{\infty }\gamma ^{i}r_{t+i} \]

\[\pi ^{*} = argmax V ^{\pi } (s) \]

获得\(\pi ^{*} (s)\)后,就可以应用了,即对任意一个\(s_{t}\),都可以算出最理想的行为\( a^{*}_{t} = \pi ^{*} (s_{t})\)。

注意:\( V ^{\pi } (s_{t}) \)的实现不是唯一的,还有其他各种各样的公式可以选择,严格来说并不是MDP定义的一部分。

Q函数

评估函数Q的公式定义:

\[ Q(s,a) = r_{immediate}(s,a) + \gamma V^{ \pi ^{*} }(s') \]

用文字解释:Q的值为从状态s执行动作a所获得的立即奖励再加上后续遵循最优策略时的V值,V用\(\gamma \)折算。

并且有:

\[\pi ^{*} = argmax Q(s,a) \]

V函数和Q函数的关系:

\[ V^{ \pi ^{*} } = \max _{a'}Q(s,a') \]

用这个式子重写Q的定义式:

\[ Q(s,a) = r_{immediate}(s,a) + \gamma \max _{a'}Q(s',a') \]

确定性MDP系统的基于Q函数的增强学习算法

在增强学习中,要学习的函数是Q函数而不是\( V^{ \pi ^{*} } \)函数。这是因为后者是关于s的一元函数,计算过程要求知道每个状态\(s_{t}\)的最佳\(a_{t}\),否则就算不出\(r_{t}\)了;而Q函数是关于s、a的二元函数,不需要知道最佳\(a_{t}\),而仅仅需要知道\( r_{immediate}(s,a) \)的值(右边的\( \gamma \max _{a'}Q(s',a') \)是递归式,熟悉动态规划的童鞋就知道Q可以计算出来的,实际上Q就是一个Bellman方程);当算出所有Q(s,a)的值后,根据\( a_{t} = argmax Q(s_{t},a) \),就可以知道\( \pi ^{*} \)。

Q学习算法的流程如下:

  1. 建一个二维表Q(s,a),并把所有表项Q(s,a)初始化成0

  2. 重复迭代:

    1. 根据当前状态s,选一个动作a并执行
    2. 得到立即奖励r:\( r = R_{ a }(s, s') \)
    3. 更新表项:\( Q(s,a) = r + \gamma \max _{a'}Q(s', a') \) 【向后传播(back propagation)】
    4. 进入新状态s':\( s = s' \)
(未经授权禁止转载)
Written on June 11, 2016

博主将十分感谢对本文章的任意金额的打赏^_^