欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

强化学习(3)-定义问题

Agent–Environment Interface

有两个很重要的组件,agent和environment,agent可以看做是「learner and decision-maker」,和agent交互的外部因素的总和是environment。

QQ20170410-154458

反馈

前面我们说过,每一次预测价值的时候,需要考虑的不仅仅是下一步获得的收益,需要考虑下一步到到结束的整体收益,而是整体的收益,站在反馈的角度,根据实际的情况,可以将「任务」分为两类。

episodic tasks

就是回合类任务,两个回合之间没有任何关系,例如下棋。任务进入「结束状态」,之后reset所有变量重新来过,对状态t时刻,对未来的收益预估为:

\(G_t=R_{t+1} + R_{t+2}+...+R_T\)

其中T表示回合结束。

continuing tasks

持续类任务,就是没有明显的切割点,任务会一直持续下去,在t时刻,对未来的收益预估为:

\(G_t=R_{t+1} + \gamma R_{t+2} + \gamma R_{t+2}+...=\sum_{k=1}^{\propto }\gamma R_{t+k}\)

其中 \(0<\gamma <1\)

统一表示

上面两种形式,是否可以通过一种同意的形式表示?接下来介绍的就是一种通过引入特殊的「终结」状态,如下图:

QQ20170412-221810

马尔科夫性

通俗的说,马尔科夫性就是说当前状态只和前一个状态有关系。

强化学习的框架下,在时刻t,状态和反馈的联合概率可以表示为:

QQ20170413-222916

满足马尔科夫性之后的公式变为:

QQ20170413-222925

在下棋的场景下,最优的行为,只和当前的棋盘局势(状态)有关。

 

马尔科夫决策过程

对强化学习的进一步假设,本书中主要讨论的场景就是两个回合满足「马尔科夫性」,下面是具体的定义,对于状态来说:

QQ20170413-225211

这个式子被称为「转移概率」,有种HMM的感觉。。

对于反馈来说: QQ20170413-225218

到这里,重要的两个东西定义清楚了。

扫地机器人

机器人的状态转移图如下图,其中low和high表示电量状态,具体为: QQ20170413-230056

转移概率和期望收益为:

QQ20170413-225953

价值函数

寻找最优的行为,是强化学习的和核心问题,那么如何衡量一个行为的好坏呢?就需要价值函数进行量化。

选择行为的时候,我们可以用不同的策略,当然也可以只有一种策略,例如前文介绍的Bandit问题的「贪心策略」。对状态 \(s\) ,行为 \(a\) 在策略 \(\pi\) 下被选择的概率为: \(\pi(a|s)\)

使用 \(v_{\pi}(s)\) 表示在状态 \(s\) 下,使用策略 \(\pi\) 带来的期望收益,具体公式为:

QQ20170414-111905

我们的目标是得到具体的行为,所以还需要计算给定行为下的「期望收益」,具体公式为:

QQ20170414-112139

蒙特卡罗近似

了解投针试验的同学应该不陌生,是对分布进行预估的有效方法,上面两个分布 \(v_{\pi}(s)\)\(q_{\pi}(s,a)\) 的预估也可以通过这种方式,数据充足的情况下,通过大数定律直接求平均就可以收敛到真实值;如果状态空间很大,就需要考虑通过模型的方式学(拟合)出来合理的预估值。

Bellman equation

细心的你可能已经发现,由于强化学习整个是一个循环(重复过程),所以满足马尔科夫性的条件下(下一个状态只和当前状态有关),关于状态价值的递推公式为:

QQ20170414-113416

上面式子也称为「Bellman equation」,其中有两个重要的分布和一个预估:

  1. 已知状态和策略,行为的分布,即 \(\pi(a|s)\)
  2. 已知状态和行为,下一个状态的分布,即 \(p(s'|s,a)\)
  3. 已知状态、行为和下一个状态,价值的预估,即 \(r(s,a,s')\)

下图很好的表示了这个推理(生成)的过程:

QQ20170414-145648

QQ20170415-083944

QQ20170415-083951

 

最优策略

纵观整个过程,我们的目标是在给定的状态(环境)下,得到最优的长期回报。如果有多个策略,首先我们要选择一个合适的策略,有下面两个场景:

  1. 已知状态 \(s\) 求最优的 \(v_{\pi}(s)\) ,即: \(v_*(s)=\max_{\pi}v_{\pi}(s)\)
  2. 已知状态 \(s\) 和行为 \(a\) ,求最优的 \(q_*(s,a)\) ,即 \(q_*(s,a)=\max_{\pi}q_{\pi}(s,a)\)

使用 \(v_*(s)\) 表示 \(q_*(s,a)\)

QQ20170415-095752

Bellman optimality equation

前面我们介绍了Bellman equation,是对当前状态「所有策略」的期望收益的预估,实际中我们需要作出具体的决策,所以我们需要计算「最优策略」给我们带来的收益,微观上来说,我们需要得到在当前状态下一个最优的「行为」。

过程可以用下图表示:

QQ20170415-101842

具体的方程为:

QQ20170415-102532

站在实现的角度,上面的求解过程可以使用dp的方法,类似HMM中的Viterbi。

资料

《Reinforcement Learning: An Introduction》第三章

未经允许不得转载:大数据算法 » 强化学习(3)-定义问题

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站