Press "Enter" to skip to content

【强化学习】Markov Decision Processes

强化学习(RL)问题可以通过下图描述

RL中的代理和环境:

 

代理在观察环境状态 后决定采取哪些行动

 

环境基于代理采取的行动 ,从一个状态 过渡到另一个状态 并产生奖励

 

我们只能为代理设计动作选择算法(即策略),而不能控制环境的演变

 

(2)RL中的环境

 

环境决定 状态 的演化方式 以及观察动作 后 发出的奖励数量

 

在数学上,环境由两个概率分布来描述,即

状态转换:
回报:

根据代理是否知道分布,可以将RL分为两类:基于模型的RL和不基于模型的RL

 

(3)RL的策略

 

策略:观察环境状态s后确定采取的行动

 

在数学上,策略可以由条件概率分布表示: ,其中

 

(4)RL的目标

 

找到一个策略 ,使平均累积奖励 最大,其中 是折扣因子

 

(5)RL举例

 

问题描述:

 

(1) 状态:agent的位置

 

(2) 行动:North,East,South,West

 

(3) 回报:每步-1

每个状态学习的策略如下:

2.Markov决策过程

 

从数学上讲,所有RL问题都可以表述为MDP

 

(1)Markov过程

 

马尔可夫过程:状态 根据转移概率 顺序生成,如:

 

该序列具有Markov属性,这在数学上意味着:

 

这表示,给定现在,未来就独立于过去。即,在当前状态下,所有历史信息都可以丢弃。

 

马尔可夫过程可以表示为元祖<S,P>,其中S是 状态空间 ,P是 状态转移矩阵 。其中

 

Markov过程举例

这样一个马尔科夫过程的状态转移矩阵为

而所有以 为其实状态的策略为:

(2)Markov奖励过程

 

马尔可夫回报过程(MRP):与每个状态的奖励相关联的马尔可夫过程:

 

MRP可以由四元组 表示。其中S是所有可能状态的集合,P是概率转移矩阵,R是给定状态s的回报函数 , 是折扣因子

 

Markov回报过程

 

回报:是时间t之后的折扣后总奖励,即

 

 

回报举例

以上图,在t=1时,可能回报 是:

(在t=0时,状态s0为Class 1,t=1时,状态s1为Sleep)

折扣因子 的作用:

1)确保收敛

 

2)不确定性未完全体现

 

3)近期奖励比远期奖励更有价值

两种特殊情况

1) 表示代理仅关心即时奖励

 

2) 表示代认为所有未来状态的回报同样重要

 

(3)Markov决策过程

 

马尔可夫决策过程(MDP):与每个状态的决策相关的MRP:

 

MDP由五元组 表示。其中S是所有状态的集合,A是行为的集合,P是概率转移矩阵 ,R是给定状态s和行为a的回报函数 , 是折扣因子。

 

MDP举例

策略

 

策略 是给定状态的行为的条件分布:

 

策略决定在不同状态采取哪种行动

 

政策仅取决于当前状态,与历史无关

 

策略是固定的(与时间无关)

 

给定一个MDP 和一个策略 ,随机序列可以根据 、回报函数 和概率转移矩阵 得出:

 

3.Value Functions

 

(1)State-Value Function

 

状态值函数 :策略 下以状态s开始的序列的平均回报

 

其中 为折扣后总回报; 是根据策略 生成的序列的平均值

 

例如,C1的状态值是在策略 下以C1开头的序列的平均收益

备注:我们假设值v(s)与时间步长t是相互独立的,即MDP是固定的

 

State-Value Functions举例

 

给定策略的状态值,其中 = 0.9

(2)Action-Value Function

 

行为值函数 :从状态-动作对(s,a)开始的序列的平均回报

 

在不同的策略 下,回报函数 通常不同。所以期望是关于策略 的。

 

4.Bellman Expectation Equations

 

贝尔曼期望方程:状态值

 

在策略 下,回报函数 可以写成

从 ,我们有

其中

 

这就是状态值Bellman期望方程,它通过线性方程关联不同状态的状态值

 

详细推导过程如下:

在倒数第二个“=”中,我们将 和 分别表示为a和s’

贝尔曼期望方程

可以用下面的树来说明

和 的关系

 

用 表示 :

用 表示 :

贝尔曼期望方程式:行动值

 

给定状态s和行为a,从 的定义,行动值函数满足

5.Bellman Optimality Equations

 

最优值函数

 

最优状态值函数 :所有策略的最大值函数

 

最优行为值函数 :所有策略的最大行为值函数

 

那幺问题来了, 和 的最佳状态值是否可以在两种不同的策略 和 下实现?

 

最优策略的存在性

 

更优策略的定义:一个策略 优于另一个策略 当且仅当 。即 iff

 

存在定理:对于任何MDP,始终存在至少一个优于或等于所有其他策略的策略,即,存在 使得

 

换句话说,存在一个策略 ,在执行这个策略时:

 

可以实现最优状态值函数

 

可以实现最优行为值函数

 

证明略。

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注