machine-learning-notes
  • 封面
  • 目录
  • 前言
  • 个人前言
  • 机器学习前言
    • 什么是机器学习和模式识别
    • 机器学习的应用
    • 机器学习的流程
    • 不同的机器学习算法对相同数据预测效果不同
    • 快速入门机器学习
    • 机器学习需要参考哪些书
    • 机器学习的学习路径
    • 深度学习的学习路径
    • 互联网机器学习特定岗位所需技能
  • 机器学习面试
  • 数学基础
  • 微积分
    • 泰勒展开
    • e的直观认识
    • 傅里叶变换
    • 希尔伯特空间
  • 线性代数
    • 范数
    • 矩阵求导
    • 特征值
    • 奇异值分解
  • 概率与信息论
    • 综述概率论基本定义
    • 概率论与贝叶斯先验
    • 正态分布
    • 贝叶斯概率
    • 概率符号说明
    • 共轭先验
    • 信息论
  • 数值计算与优化
    • 最小二乘法
    • 等式约束的拉格朗日乘子法
    • 凸优化
      • 凸集和凸函数
      • 凸优化问题
  • 梯度下降算法
    • 随机梯度下降SGD
    • 动量法Momentum
    • 牛顿动量Nesterov
    • AdaGrad
    • RMSprop
    • Adadelta
    • Adam
    • Nadam
    • AMSGrad
    • AdasMax
  • 概率图模型
    • 概率图模型概论
    • 概率图简介
  • 编程基础
  • linux
    • linux常用命令
    • shell
      • 输入输出重定向
  • python
    • python简介
    • python语法
      • 基础语法
      • 数据结构
      • 过程控制
      • 函数
      • 类和对象
      • 文件操作
      • 正则表达式
    • python库
      • numpy
      • pandas
      • scipy
      • matplotlib
      • scikit-learn
    • python应用
      • 排序算法
  • 数据结构与算法
    • 数据结构
    • 算法思想
      • 排序
        • 堆排序
        • 归并排序
        • 快速排序
      • 递归
    • 剑指offer
      • 链表
      • 二叉树
      • 数组
      • 字符串
      • 栈和队列
      • 递归
      • 动态规划
      • 其他
    • leetcode
    • 编程语言
      • c++
  • Hadoop
    • Hadoop简介
    • MapReduce
  • Hive
  • Spark
  • TensorFlow
    • TensorFlow1.0
      • TensorFlow基础
      • TensorFlow基础概念解析
      • TensorFlow机器学习基础
      • Tensorflow分布式架构
    • TensorFlow2.0
  • PyTorch
  • 机器学习
  • 机器学习概论
  • 特征工程
  • 感知机
  • k近邻
  • 朴素贝叶斯
  • 线性模型
    • 最大熵模型
    • 指数族分布与广义线性模型
    • 线性回归
      • Ridge回归(岭回归)
      • Lasso回归
    • Logistic回归-对数几率回归
  • 决策树
  • 支持向量机
    • 线性可分支持向量机与硬间隔最大化
    • 线性支持向量机与软间隔最大化
    • 非线性支持向量机与核函数
    • 序列最小最优化算法SMO
    • SVM总结
  • 集成学习
    • Bagging
      • 随机森林
    • Boosting
      • AdaBoost
      • GradientBoosting
        • GBDT
        • XGBoost
          • XGBoost理论
          • XGBoost实践
    • Stacking
  • 降维
    • PCA主成分分析
    • 流形学习
  • EM算法
  • HMM隐马尔科夫模型
  • CRF条件随机场
  • 聚类
    • k均值聚类
    • 高斯混合模型
  • 主题模型
    • LDA隐狄利克雷分布
  • 知识点
    • 损失函数
    • 负采样
  • 机器学习算法总结
  • 深度学习
  • 深度学习概论
  • ANN人工神经网络
  • 知识点
    • Batch Normalization
  • CNN卷积神经网络
  • 深度学习优化算法
  • RNN循环神经网络
  • LSTM长短期记忆网络
  • GRU门控循环单元
  • GNN图神经网络
    • GNN图神经网络综述
    • GCN图卷积网络
      • GCN图卷积网络初步理解
      • GCN图卷积网络的numpy简单实现
      • GCN图卷积网络本质理解
      • GCN图卷积网络全面理解
      • SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS ICLR2017
  • 神经网络架构搜索
    • Weight-Agnostic-Neural-Networks Google2019
  • 强化学习
  • 强化学习概论
  • 马尔科夫决策过程
  • 动态规划
  • 无模型方法一:蒙特卡洛
  • 无模型方法二:时间差分
  • 无模型方法三:多步自举
  • 函数近似和深度网络
  • 策略梯度算法
  • 深度强化学习
  • 基于模型的强化学习
  • 强化学习前景
  • 自然语言处理
  • 自然语言处理概论
  • 自然语言
  • 语言模型和中文分词
  • word2vec
    • word2vec概述
    • word2vec算法原理
    • word2vec源码分析
    • word2vec实践
  • Seq2Seq模型和Attention机制
  • Self-Attention和Transformer
  • 知识图谱
  • 推荐系统
  • 推荐系统概论
  • 基础知识
  • 进阶知识
    • 机器学习
      • Factorization Machines ICDM2010
    • embedding
      • Network Embedding
        • LINE: Large-scale Information Network Embedding
    • 深度学习
      • DeepFM: A Factorization-Machine based Neural Network for CTR Prediction 2017
      • DSSM: Learning Deep Structured Semantic Models for Web Search using Clickthrough Data CIKM2013
    • 图卷积网络
      • Graph Convolutional Neural Networks for Web-Scale Recommender Systems KDD2018
    • 强化学习
      • DRN基于深度强化学习的新闻推荐模型
  • 业界应用
    • YouTube
      • Deep Neural Networks for YouTube Recommendations RecSys2016
    • Alibaba
      • Learning Tree-based Deep Model for Recommender Systems KDD2018
      • Deep Interest Network for Click-Through Rate Prediction KDD2018
      • DSIN:Deep Session Interest Network for Click-Through Rate Prediction IJCAI2019
Powered by GitBook
On this page
  • 马尔科夫决策过程
  • 本章在学习地图中的位置
  • 马尔科夫决策过程简介
  • 符号约定
  • 马尔科夫过程
  • 马尔科夫性
  • 状态转移矩阵
  • 状态转移函数
  • 马尔科夫过程
  • 片段
  • 马尔科夫链的例子
  • 马尔科夫奖励过程
  • 马尔科夫奖励过程例子
  • 回报值
  • 再聊片段
  • 再聊衰减值
  • 值函数
  • 例子:回报值和值函数
  • MRPs中的贝尔曼方程
  • 马尔科夫决策过程
  • 马尔科夫决策过程的定义
  • 策略
  • MDPs和MRPs之间的关系
  • MDPs中的值函数
  • 贝尔曼期望方程
  • 最优值函数
  • 最优策略
  • v*与q*的相互转化
  • 贝尔曼最优方程
  • MDPs的扩展
  • 无穷或连续MDPs
  • 部分可观测MDPs
  • 无衰减MDPs
  • 参考文献

Was this helpful?

马尔科夫决策过程

Previous强化学习概论Next动态规划

Last updated 5 years ago

Was this helpful?

马尔科夫决策过程

本章在学习地图中的位置

马尔科夫决策过程是强化学习的数学基础,也是将强化学习从直观定义到数学定义的一个桥梁。

马尔科夫决策过程简介

  • 马尔科夫决策过程(Markov Decision Process, MDPs)是对强化学习问题的数学描述。

  • 要求环境是全观测的。(原因后述)

  • 几乎所有的RL问题都能用MDPs来描述

    • 最优控制问题可以描述成连续MDPs

    • 部分观测问题可以转化成POMDPs

    • 赌博机问题是只有一个状态的MDPs

注:虽然大部分RL问题都可以转化成MDPs,但是在我写的笔记中所描述的MDPs是在全观测的情况下。

符号约定

  • 用大写字母表示随机变量:例如

    S,A,RS,A,RS,A,R
  • 用小写字母表示某一个具体的值

    s,a,rs,a,rs,a,r
  • 用空心字母表示统计运算符

    E,P\mathbb{E,P}E,P
  • 用花体字母表示集合或函数(注:这里没用花体表示是因为gitbook不支持渲染花体\cal{})

    S,A,PS,A,PS,A,P

马尔科夫过程

马尔科夫性

只要知道现在,将来和过去是条件独立的。

定义:

如果在t时刻的状态St满足如下等式,那么这个状态被称为马尔科夫状态,或者说该状态满足马尔科夫性:

P[St+1∣St]=P[St+1∣S1,...,St]\mathbb{P}[S_{t+1}|S_t]=\mathbb{P}[S_{t+1}|S_1,...,S_t]P[St+1​∣St​]=P[St+1​∣S1​,...,St​]
  • 状态St包含了所有历史相关信息(注:这里的相关指与问题相关,可能有一些问题无关的信息没有在St中)

  • 或者说历史的所有状态的相关信息都在当前状态St上体现出来

  • 一旦St知道了,那么S1,S2,...,St-1都可以被抛弃

  • 数学上可以认为:状态是将来的充分统计量

  • 因此,这里要求环境全观测(马尔科夫性与状态的定义息息相关,比如打砖块,就要求状态是当前画面帧和上一次的画面帧,不然得不到砖块下落速度)

  • 例子

    • 下棋时,只用关心当前局面

    • 打俄罗斯方块时,只用关心屏幕

  • 有了马尔科夫状态之后

    • 定义状态转移矩阵

    • 忽略时间的影响

状态转移矩阵

定义:

状态转移概率指从一个马尔科夫状态s跳转到后继状态(successor state)s‘的概率

Pss′=P[St+1=s′∣St=s]{P}_{ss'}=\mathbb{P}[S_{t+1}=s'|S_t=s]Pss′​=P[St+1​=s′∣St​=s]

所有的状态组成行,所有的后继状态组成列,我们得到状态转移矩阵

P=[P11...P1n⋮⋱⋮Pn1...Pnn]\begin{aligned} {P}= \begin{bmatrix} {P}_{11} & ... & {P}_{1n}\\ \vdots & \ddots & \vdots\\ {P}_{n1} & ... & {P}_{nn}\\ \end{bmatrix} \end{aligned}P=​P11​⋮Pn1​​...⋱...​P1n​⋮Pnn​​​​
  • n表示状态的个数

  • 由于P代表了整个状态转移的集合,所以用花体

  • 每行元素相加等于1

状态转移函数

我们也可以将状态转移概率写成函数的形式

Pss′=P[St+1=s′∣St=s]{P}_{ss'}=\mathbb{P}[S_{t+1}=s'|S_t=s]Pss′​=P[St+1​=s′∣St​=s]
  • 状态转移概率到下一各状态的和为1,即

    ∑s′P(s′∣s)=1\sum_{s'}\mathbb{P}(s'|s)=1s′∑​P(s′∣s)=1
  • 状态数量太多或者是无穷大(连续状态)时,更适合使用状态转移函数,此时

    ∫s′P(s′∣s)=1\int_{s'}\mathbb{P}(s'|s)=1∫s′​P(s′∣s)=1

马尔科夫过程

一个马尔科夫过程(Markov process, MP)是一个无记忆的随机过程,即一些马尔科夫状态的序列

定义:

马尔科夫过程可以由一个二元组来定义\

  • S代表了状态的集合

  • P代表了状态转移概率矩阵

    Pss′=P[St+1=s′∣St=s]{P}_{ss'}=\mathbb{P}[S_{t+1}=s'|S_t=s]Pss′​=P[St+1​=s′∣St​=s]

注:虽然我们有时候并不知道P的具体值,但是通常我们假设P是存在且稳定的

注:当P不稳定时,是不稳定环境,需要在线学习,快速学习

马尔科夫过程的例子:

  • 一个学生每天需要学习三个科目,然后通过测验

  • 不过也有可能只学完两个科目之后直接睡觉

  • 一旦挂科,有可能需要重新学习某些科目

  • 用椭圆表示普通状态,每一条线上的数字表示从一个状态跳转到另一个状态的概率

  • 方块表示终止(terminal)状态

  • 终止状态的定义有两种:

    • 时间终止

    • 状态终止

由于马尔科夫过程可以用图中的方块和线条组成,所以可以称马尔科夫过程为马尔科夫链(MDPs chain)

片段

定义:

强化学习中,从初始状态S1到终止状态的序列过程,被称为一个片段(episode)

S1,S2,...,STS_1,S_2,...,S_TS1​,S2​,...,ST​
  • 如果一个任务总以终止状态结束,那么这个任务被称为片段(episodic task)

  • 如果一个任务会没有终止状态,会被无限执行下去,这被称为连续性任务(continuing task)

马尔科夫链的例子

片段:

假设初始状态是“科目一”,从这个马尔科夫链中,我们可能采样到如下的片段

  • “科目一”,“科目二”,“睡觉”

  • “科目一”,“科目二”,“科目三”,“通过”,“睡觉”

  • “科目一”,“玩手机”,“玩手机”,... ,“玩手机”,“科目一”,“科目二”,“睡觉”

  • “科目一”,“科目二”,“科目三”,“挂科”,“科目二”,“科目三”,“挂科”,“科目一”,“科目二”,“科目三”,“挂科”,“科目三”,“通过”,“睡觉”

转移矩阵

分别用s1~s7代表“科目一”,“科目二”,“科目三”,“通过”,“挂科”,“玩手机”,“睡觉”

P=[−0.5−−−0.5−−−0.8−−−0.2−−−0.60.4−−−−−−−−1.00.20.40.4−−−−0.1−−−−0.9−−−−−−−1.0]{P}= \begin{bmatrix} -& 0.5 & -& -& -& 0.5 & -\\ -& -& 0.8 & -& -& -& 0.2\\ -& -& -& 0.6 & 0.4 & -& -\\ -& -& -& -&- & -& 1.0\\ 0.2 & 0.4 & 0.4 & -& -& -& -\\ 0.1 & -& -& -& -& 0.9 & -\\ -& -& -& -&- & -& 1.0\\ \end{bmatrix}P=​−−−−0.20.1−​0.5−−−0.4−−​−0.8−−0.4−−​−−0.6−−−−​−−0.4−−−−​0.5−−−−0.9−​−0.2−1.0−−1.0​​

马尔科夫奖励过程

接下来我们在马尔科夫过程中加一个强化学习中三大交互学习组成中最重要的一个:奖励,这也是强化学习和其他机器学习问题中比较大的一个区别。

马尔科夫过程主要描述的是状态之间的转移关系,在这个转移关系上赋予不同的奖励值即得到了马尔科夫奖励过程。

定义:

马尔科夫奖励过程(Markov Reward Process,MRP)过程由一个四元组组成\

  • S代表了状态的集合

  • P描述了状态转移矩阵

    Pss′=P[St+1=s′∣St=s]{P}_{ss'}=\mathbb{P}[S_{t+1}=s'|S_t=s]Pss′​=P[St+1​=s′∣St​=s]
  • R表示奖励函数,R(s)描述了在状态s的奖励,

    R(s)=E[Rt+1∣St=s]{R}(s)=\mathbb{E}[R_{t+1}|S_t=s]R(s)=E[Rt+1​∣St​=s]
  • γ表示衰减引子,

    γ∈[0,1]\gamma\in [0,1]γ∈[0,1]

马尔科夫奖励过程例子

回报值

  • 奖励值:对每一个状态的评价

  • 回报值:对每一个片段的评价

定义:

回报值(return Gt)是从时间t处开始的累计衰减奖励。

  • 对于片段性任务:

    Gt=Rt+1+γRt+2+...+γT−t−1RT=∑k=0T−t−1γkRt+k−1\begin{aligned} G_t&=R_{t+1}+\gamma R_{t+2}+...+\gamma^{T-t-1}R_T\\ &=\sum_{k=0}^{T-t-1}\gamma^kR_{t+k-1} \end{aligned}Gt​​=Rt+1​+γRt+2​+...+γT−t−1RT​=k=0∑T−t−1​γkRt+k−1​​
  • 对于连续性任务:

    Gt=Rt+1+γRt+2+γ2Rt+3+...=∑k=0∞γkRt+k+1\begin{aligned} G_t&=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...\\ &=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1} \end{aligned}Gt​​=Rt+1​+γRt+2​+γ2Rt+3​+...=k=0∑∞​γkRt+k+1​​

再聊片段

  • 终止状态等价于自身转移概率为1,奖励为0的状态

  • 因此我们能够将片段性任务和连续性任务统一表达:

    Gt=∑k=0T−t−1γkRt+k+1G_t=\sum_{k=0}^{T-t-1}\gamma^kR_{t+k+1}Gt​=k=0∑T−t−1​γkRt+k+1​

    这里当T=∞时,表示连续性任务,否则即为片段性任务。

再聊衰减值

为什么我们要使用这样的衰减指数值?

  • 直观感觉

    • 影响未来的因素不仅仅包含当前

    • 我们对未来的把握也是逐渐衰减的

    • 一般情况下,我们更关注短时间的反馈

  • 数学便利

    • 一个参数就描述了整个衰减过程,只需要调节这一个参数γ就可以来调节长时奖励和短时奖励的权衡(trade-off)

    • 指数衰减形式又很容易进行数学分析

    • 指数衰减是对回报值的有界保证,避免了循环MRP和连续性MRP情况下回报值变成无穷大

注:在一些特殊情况,也可以使用γ=1的回报值

值函数

为什么要值函数?

  • 回报值是一次片段的结果,存在很大的样本偏差

  • 回报值的脚标是t,值函数关注的是状态s

值函数定义:

一个马尔科夫奖励过程MRP的值函数定义如下:

v(s)=E[Gt∣St=s]v(s)=\mathbb{E}[G_t|S_t=s]v(s)=E[Gt​∣St​=s]

也是就是从这个状态出发的所有片段的回报值的按照概率加权的平均值(即期望值)。

  • 这里的值函数针对的是状态s,所以称为状态值函数,又称V函数

  • Gt是一个随机变量

  • 这里使用小写的v函数,代表了真实存在的值函数

例子:回报值和值函数

回报值

针对初始状态S1=“科目一”,且γ=0.5计算不同片段的回报值

  • "科目一",“科目二”,“睡觉”

    g1=(−2)+0.5×(−2)+0.52×(0)=−3\begin{aligned} g_1&=(-2)+0.5\times (-2)+0.5^2\times (0)\\ &=-3 \end{aligned}g1​​=(−2)+0.5×(−2)+0.52×(0)=−3​
  • "科目一",“科目二”,“科目三”,“通过”,“睡觉”

    g1=(−2)+0.5×(−2)+0.52×(−2)+0.53×(10)+0.54×(0)=−2.25\begin{aligned} g_1&=(-2)+0.5\times (-2)+0.5^2\times (-2)+0.5^3\times (10)+0.5^4\times (0)\\ &=-2.25 \end{aligned}g1​​=(−2)+0.5×(−2)+0.52×(−2)+0.53×(10)+0.54×(0)=−2.25​
  • "科目一",“玩手机”,“玩手机”,“玩手机”,"科目一",“科目二”,“睡觉”

    g1=(−2)+0.5×(−1)+0.52×(−1)+0.53×(−1)+0.54×(−2)+0.55×(−2)+0.56×(0)=−3.0625\begin{aligned} g_1=&(-2)+0.5\times (-1)+0.5^2\times (-1)+0.5^3\times (-1)\\ &+0.5^4\times (-2)+0.5^5\times (-2)+0.5^6\times (0)\\ =&-3.0625 \end{aligned}g1​==​(−2)+0.5×(−1)+0.52×(−1)+0.53×(−1)+0.54×(−2)+0.55×(−2)+0.56×(0)−3.0625​
  • "科目一",“科目二”,“科目三”,“挂科”,“科目二”,“科目三”,“挂科”,"科目一",“科目二”,“科目三”,“挂科”,“科目三”,“通过”,“睡觉”

    g1=(−2)+0.5×(−2)+0.52×(−2)+...=−4.4214...\begin{aligned} g_1&=(-2)+0.5\times (-2)+0.5^2\times (-2)+...\\ &=-4.4214... \end{aligned}g1​​=(−2)+0.5×(−2)+0.52×(−2)+...=−4.4214...​

虽然都是从相同的初始状态开始,但是不同的片段有不同的回报值,而值函数是它们的期望值。

针对例子的V函数值

当γ=0时

当γ=1时

MRPs中的贝尔曼方程

值函数的表达式可以分解成两部分

  • 瞬时奖励$R_{t+1}$

  • 后继状态$S_{t+1}$的值函数乘上一个衰减系数

v(s)=E[Gt∣St=s]=E[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E[Rt+1+γ(Rt+2+γRt+3+...)∣St=s]=E[Rt+1+γGt+1∣St=s]=E[Rt+1+γv(St+1)∣St=s]\begin{aligned} v(s)&=\mathbb{E}[G_t|S_t=s]\\ &=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...|S_t=s]\\ &=\mathbb{E}[R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+...)|S_t=s]\\ &=\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ &=\mathbb{E}[R_{t+1}+\gamma v(S_{t+1})|S_t=s]\\ \end{aligned}v(s)​=E[Gt​∣St​=s]=E[Rt+1​+γRt+2​+γ2Rt+3​+...∣St​=s]=E[Rt+1​+γ(Rt+2​+γRt+3​+...)∣St​=s]=E[Rt+1​+γGt+1​∣St​=s]=E[Rt+1​+γv(St+1​)∣St​=s]​
  • 体现了v(s)与v($S_{t+1}$)之间的迭代关系

  • 这是强化学习中的理论核心之一

  • 注意s小写,$S_{t+1}$大写

如果我们已知转移矩阵P,那么

v(s)=E[Rt+1+γv(St+1)∣St=s]=E[Rt+1∣St=s]+γE[v(St+1)∣St=s]=R(s)+γ∑s′∈SPss′v(s′)\begin{aligned} v(s)&=\mathbb{E}[R_{t+1}+\gamma v(S_{t+1})|S_t=s]\\ &=\mathbb{E}[R_{t+1}|S_t=s]+\gamma\mathbb{E}[v(S_{t+1})|S_t=s]\\ &={R}(s)+\gamma\sum_{s'\in S}{P}_{ss'}v(s') \end{aligned}v(s)​=E[Rt+1​+γv(St+1​)∣St​=s]=E[Rt+1​∣St​=s]+γE[v(St+1​)∣St​=s]=R(s)+γs′∈S∑​Pss′​v(s′)​

![value-ss'](pic/value-ss'.png)

图中我们可以用v(s1),v(s2),v(s3)去计算v(s0)。

针对例子的贝尔曼方程

当γ=1时,我们来看下一状态可能性最多的“科目三”状态:

0.6=(−2)+0.6×10+0.4×(−0.85)0.6=(-2)+0.6\times 10+0.4\times(-0.85)0.6=(−2)+0.6×10+0.4×(−0.85)

贝尔曼方程的矩阵形式

使用矩阵-向量的形式表达贝尔曼方程,即

v=R+γPvv={R}+\gamma{P}vv=R+γPv

假设状态集合为

S=s1,s2,...,sn{S}={s_1,s_2,...,s_n}S=s1​,s2​,...,sn​

,那么

[v(s1)⋮v(sn)]=[R(s1)⋮R(sn)]+γ[P11...P1n⋮⋱⋮Pn1...Pnn][v(s1)⋮v(sn)]\begin{aligned} \begin{bmatrix} v(s_1)\\ \vdots\\ v(s_n)\\ \end{bmatrix} = \begin{bmatrix} {R}(s_1)\\ \vdots\\ {R}(s_n)\\ \end{bmatrix} + \gamma \begin{bmatrix} {P}_{11} & ... & {P}_{1n}\\ \vdots & \ddots & \vdots\\ {P}_{n1} & ... & {P}_{nn}\\ \end{bmatrix} \end{aligned} \begin{bmatrix} v(s_1)\\ \vdots\\ v(s_n)\\ \end{bmatrix}​v(s1​)⋮v(sn​)​​=​R(s1​)⋮R(sn​)​​+γ​P11​⋮Pn1​​...⋱...​P1n​⋮Pnn​​​​​v(s1​)⋮v(sn​)​​

贝尔曼方程本质上是一个线性方程,可以直接解

v=R+γPv(1−γP)v=Rv=(1−γP)−1R\begin{aligned} v&={R}+\gamma{P}v\\ (1-\gamma{P})v&={R}\\ v&=(1-\gamma{P})^{-1}{R} \end{aligned}v(1−γP)vv​=R+γPv=R=(1−γP)−1R​
  • 计算复杂度O(n^3)

  • 要求已知状态转移矩阵P

  • 直接求解的方式仅限于小的MRPs

马尔科夫决策过程

马尔科夫决策过程的定义

与马尔科夫过程MP和马尔科夫奖励过程MRP的区别:

  • MP和MRP中,我们都是作为观察者,去观察其中的状态转移现象,去计算回报值。

  • 对于一个RL问题,我们更希望去改变状态转移的流程,去最大化回报值。

  • 通过在MRP中引入决策,即得到了马尔科夫决策过程(Markov Decision Process,MDPs)

马尔科夫决策过程的定义

一个马尔科夫决策过程(MDPs)由一个五元组构成

<S,A,P,R,γ><{S,A,P,R,\gamma}><S,A,P,R,γ>
  • S代表了状态的集合

  • A代表了动作的集合

  • P描述了状态转移矩阵

    Pss′a=P[St+1=s′∣St=s,At=a]{P}_{ss'}^a=\mathbb{P}[S_{t+1}=s'|S_t=s,A_t=a]Pss′a​=P[St+1​=s′∣St​=s,At​=a]
  • R表示奖励函数,R(s,a)描述了在状态s做动作a的奖励

    R(s,a)=E[Rt+1∣St=s,At=a]{R}(s,a)=\mathbb{E}[R_{t+1}|S_t=s,A_t=a]R(s,a)=E[Rt+1​∣St​=s,At​=a]
  • γ表示衰减引子,γ∈[0,1]

MDPs例子

  • 针对状态的奖励变成了针对\的奖励

  • 能通过动作进行控制的状态转移由原来的状态转移概率特换成了动作

  • MDP只关注那些可以做出决策的动作

  • 被动的状态转移关系被压缩成一个状态

    • “被动”指无论做任何动作,状态都会发生跳转。这样的状态不属于MDPs中考虑的状态

    • 原图中,由于“通过”后一定会去“睡觉”,因此进行了压缩

    • 原图中,“挂科”后的跳转不受控制

注:图中除了在“科目三”的状态上执行“不复习”动作外,其他的所有状态跳转都是不确定性的,我们通过在不同的状态上执行不同的动作,即可实现不同的状态跳转。

策略

我们将之前的MRPs中的状态转移矩阵分成了两个部分

  • 能被智能体控制的策略,Policy

  • MDPs中的转移矩阵P(不受智能体控制,认为是环境的一部分)

策略的定义:

在MDPs中,一个策略(Policy)π是给定状态下的动作的概率分布

π(a∣s)=P[At=a∣St=s]\pi(a|s)=\mathbb{P}[A_t=a|S_t=s]π(a∣s)=P[At​=a∣St​=s]

策略的特点

  • 策略是对智能体行为的全部描述

  • MDPs中的策略是基于马尔科夫状态的(而不是基于历史)

  • 策略是时间稳定的,只与状态s有关,与时间t无关

  • 策略是RL问题的终极目标

  • 如果策略的概率分布输出都是独热的(one-hot)的,那么成为确定性策略,否则即为随机性策略

MDPs和MRPs之间的关系

对于一个MDP问题\,如果给定了策略π

  • MDP将会退化成MRP,

    <S,Pπ,Rπ,γ><{S},{P}^{\pi},{R}^{\pi},\gamma><S,Pπ,Rπ,γ>
  • 此时

    Pss′π=∑a∈Aπ(a∣s)Pss′aRsπ=∑a∈Aπ(a∣s)Rsa\begin{aligned} {P}_{ss'}^{\pi}&=\sum_{a\in {A}}\pi(a|s){P}_{ss'}^a\\ {R}_s^{\pi}&=\sum_{a\in {A}}\pi(a|s){R}_{s}^a \end{aligned}Pss′π​Rsπ​​=a∈A∑​π(a∣s)Pss′a​=a∈A∑​π(a∣s)Rsa​​

注:注意由于策略π代表:1,一个动作;2,一个动作分布,所以有时候,π和a会存在一定的混淆。

MDPs中的值函数

在MDPs问题中,由于动作的引入,值函数分为了两种:

  1. 状态值函数(V函数)

  2. 状态动作值函数(Q函数)

定义:

MDPs中的状态值函数是从状态s开始,使用策略π得到的期望回报值

vπ(s)=Eπ[Gt∣St=s]v_{\pi}(s)=\mathbb{E}_{\pi}[G_t|S_t=s]vπ​(s)=Eπ​[Gt​∣St​=s]

定义:

MDPs中的状态动作值函数是从状态s开始,执行动作a,然后对接下来的状态使用策略π得到的期望回报值

qπ(s,a)=Eπ[Gt∣St=s,At=a]q_{\pi}(s,a)=\mathbb{E}_{\pi}[G_t|S_t=s,A_t=a]qπ​(s,a)=Eπ​[Gt​∣St​=s,At​=a]

这个怎么理解呢?

假设一条马尔可夫链为s1, a1, s2, a2, s3, a3 ......

q(s, a)表示初始状态和初始动作确定了s=s1, a=a1,之后的动作a2, a3,...都是来自策略π的:a2,a3,...服从π

也就是与下式是等价的:

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

Qπ(s,a)=∑s′∈SP(s′∣s,a)[R(s′∣s,a)+γVπ(s′)]Q^{\pi}(s,a)=\sum_{s'\in S}P(s'|s,a)[R(s'|s,a)+\gamma V^{\pi}(s')]Qπ(s,a)=s′∈S∑​P(s′∣s,a)[R(s′∣s,a)+γVπ(s′)]

注:在MDPs中,任何不说明策略π的情况下,讨论值函数都是在耍流氓!

贝尔曼期望方程

和MRP相似,MDPs中的值函数也能分为瞬时奖励和后继状态的值函数两部分

vπ(s)=Eπ[Rt+1+γvπ(St+1)∣St=s]qπ(s,a)=Eπ[Rt+1+γqπ(St+1,At+1)∣St=s,At=a]\begin{aligned} v_{\pi}(s)&=\mathbb{E}_{\pi}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t=s]\\ q_{\pi}(s,a)&=\mathbb{E}_{\pi}[R_{t+1}+\gamma q_{\pi}(S_{t+1},A_{t+1})|S_t=s,A_t=a]\\ \end{aligned}vπ​(s)qπ​(s,a)​=Eπ​[Rt+1​+γvπ​(St+1​)∣St​=s]=Eπ​[Rt+1​+γqπ​(St+1​,At+1​)∣St​=s,At​=a]​

例子:

  • 当对于所有的s和a,都有π(a|s)=0.5时,v_π(s)如上图

  • 将图中的圆圈状态从上到下从左到右

    分别记为s1,s2,s3,s4,将终止状态记

    为s5,则对于所有的s和a,当π(a|s)=0.5时,状态转移矩阵为

P=[0.50.5−−−0.5−0.5−−−−−0.50.5−0.10.20.20.5−−−−1]{P}= \begin{bmatrix} 0.5 & 0.5 & -& -& -\\ 0.5 & -& 0.5 & -& -\\ -& -& -& 0.5 & 0.5 \\ -& 0.1 & 0.2 & 0.2 & 0.5 \\ - & - & - & -& 1\\ \end{bmatrix}P=​0.50.5−−−​0.5−−0.1−​−0.5−0.2−​−−0.50.2−​−−0.50.51​​

V函数与Q函数之间的相互转化

vπ(s)=∑a∈Aπ(a∣s)qπ(s,a)v_{\pi}(s)=\sum_{a\in {A}}\pi(a|s)q_{\pi}(s,a)vπ​(s)=a∈A∑​π(a∣s)qπ​(s,a)

注:本质上是全概率公式

qπ(s,a)=R(s,a)+γ∑s′∈SPss′avπ(s′)q_{\pi}(s,a)={R}(s,a)+\gamma\sum_{s'\in S}{P}_{ss'}^av_{\pi}(s')qπ​(s,a)=R(s,a)+γs′∈S∑​Pss′a​vπ​(s′)

贝尔曼期望方程—V函数

vπ(s)=∑a∈Aπ(a∣s)qπ(s,a)=∑a∈Aπ(a∣s)(R(s,a)+γ∑s′∈SPss′avπ(s′))\begin{aligned} v_{\pi}(s)&=\sum_{a\in{A}}\pi(a|s)q_{\pi}(s,a)\\ &=\sum_{a\in {A}}\pi(a|s)\left({R}(s,a)+\gamma\sum_{s'\in S}{P}_{ss'}^av_{\pi}(s')\right) \end{aligned}vπ​(s)​=a∈A∑​π(a∣s)qπ​(s,a)=a∈A∑​π(a∣s)(R(s,a)+γs′∈S∑​Pss′a​vπ​(s′))​

实际上等价于

vπ(s)=Eπ[Rt+1+γvπ(St+1)∣St=s]v_{\pi}(s)=\mathbb{E}_{\pi}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t=s]vπ​(s)=Eπ​[Rt+1​+γvπ​(St+1​)∣St​=s]

为什么?

贝尔曼期望方程—Q函数

qπ(s,a)=R(s,a)+γ∑ss′a∑a′∈Aπ(a′∣s′)qπ(s′,a′)q_{\pi}(s,a)={R}(s,a)+\gamma\sum_{ss'}^a\sum_{a'\in{A}}\pi(a'|s')q_{\pi}(s',a')qπ​(s,a)=R(s,a)+γss′∑a​a′∈A∑​π(a′∣s′)qπ​(s′,a′)

实际上等价于

qπ(s,a)=E[Rt+1+γqπ(St+1,At+1)∣St=s,At=a]q_{\pi}(s,a)=\mathbb{E}[R_{t+1}+\gamma q_{\pi}(S_{t+1},A_{t+1})|S_t=s,A_t=a]qπ​(s,a)=E[Rt+1​+γqπ​(St+1​,At+1​)∣St​=s,At​=a]

,为什么?

贝尔曼期望方程例子

当γ=1,π(a|s)=0.5时

2.8=0.5×(10+0)+0.5×(−5+0.2×(−3.6)+0.4×0.4+0.4×2.8)2.8=0.5\times (10+0)+0.5\times (-5+0.2\times(-3.6)+0.4\times 0.4+0.4\times 2.8)2.8=0.5×(10+0)+0.5×(−5+0.2×(−3.6)+0.4×0.4+0.4×2.8)

贝尔曼期望方程的矩阵形式

MDPs下的贝尔曼期望方程和MRP的形式相同。

vπ=RT+γPπvπv_{\pi}={R}^T+\gamma{P}^{\pi}v_{\pi}vπ​=RT+γPπvπ​

同样地,可以直接求解

vπ=(I−γPπ)−1Rπv_{\pi}=(I-\gamma{P}^{\pi})^{-1}{R}^{\pi}vπ​=(I−γPπ)−1Rπ

求解的要求:

  • 已知π(a|s)

  • 已知P(s'|s,a)

最优值函数

之前值函数,以及贝尔曼期望方程针对的都是给定策略π的情况,是一个评价的问题。

现在我们来考虑强化学习中的优化问题,即找出最好的策略。

定义:

最优值函数指的是在所有策略中的值函数最大值,其中包括最优V函数和最优Q函数

v∗(s)=maxπ vπ(s)q∗(s,a)=maxπ qπ(s,a)\begin{aligned} v_*(s)&=\mathop{\text{max}}_{\pi}\ v_{\pi}(s)\\ q_*(s,a)&=\mathop{\text{max}}_{\pi}\ q_{\pi}(s,a) \end{aligned}v∗​(s)q∗​(s,a)​=maxπ​ vπ​(s)=maxπ​ qπ​(s,a)​
  • 最优值函数指的是一个MDP中所能达到的最佳性能

  • 如果我们找到最优值函数,即相当于这个MDP已经解决了

最优V函数

当γ=1时的最优V函数v*(s)

最优Q函数

当γ=1时的最优Q函数q*(s,a)

最优策略

为了比较不同策略的好坏,我们首先应该定义策略的比较关系

π≥π′ifvπ(s)≥vπ′(s), ∀s\pi\geq\pi'\quad\text{if}\quad v_{\pi}(s)\geq v_{\pi'}(s),\ \forall sπ≥π′ifvπ​(s)≥vπ′​(s), ∀s

最优策略定理

对于任何MDPs问题

  • 总存在一个策略π,要好于或等于其他所有的策略,π\>π,∀π

  • 所有的最优策略都能够实现最优的V函数

    vπ∗(s)=v∗(s)v_{\pi*}(s)=v_*(s)vπ∗​(s)=v∗​(s)
  • 所有的最优策略都能够实现最优的Q函数

    qπ∗(s,a)=q∗(s,a)q_{\pi*}(s,a)=q_*(s,a)qπ∗​(s,a)=q∗​(s,a)

怎么得到最优策略

我们已知了最优Q函数之后,我们能够马上求出最优策略,只要根据q*(s,a)选择相应的动作即可。

π∗(a∣s)={1if a = arg maxa∈Aq∗(s,a)0otherwise\begin{aligned} \pi_*(a|s)= \left\{\begin{matrix} &1\quad&\text{if a = arg }\mathop{\text{max}}_{a\in A}q_*(s,a)\\ &0\quad&\text{otherwise} \end{matrix}\right. \end{aligned}π∗​(a∣s)={​10​if a = arg maxa∈A​q∗​(s,a)otherwise​​
  • 可以看出对于任何MDPs问题,总存在一个确定性的最优策略

  • 如果已知最优V函数,能不能找到最优策略呢?

最优策略例子

当γ=1时的最优策略π*(a|s)

v*与q*的相互转化

  • 之前我们已经讨论了vπ(s)和qπ(s,a)之前的关系——贝尔曼期望方程

  • 同样地,v*(s)和q*(s,a)也存在着递归的关系——贝尔曼最优方程

v->q:

v∗(s)=maxa q∗(s,a)v_*(s)=\mathop{\text{max}}_a\ q_*(s,a)v∗​(s)=maxa​ q∗​(s,a)

和贝尔曼期望方程的关系:

v∗(s)=vπ∗(s)=∑a∈Aπ∗(a∣s)qπ(s,a)=maxa qπ∗(s,a)v_*(s)=v_{\pi*}(s)=\sum_{a\in A}\pi_*(a|s)q_{\pi}(s,a)=\mathop{\text{max}}_a\ q_{\pi*}(s,a)v∗​(s)=vπ∗​(s)=a∈A∑​π∗​(a∣s)qπ​(s,a)=maxa​ qπ∗​(s,a)

上式很好理解,因为最优动作对应的概率为1嘛。

q->v:

q∗(s,a)=R(s,a)+γ∑s′∈SPss′av∗(s′)q_*(s,a)=R(s,a)+\gamma\sum_{s'\in S}P_{ss'}^av_*(s')q∗​(s,a)=R(s,a)+γs′∈S∑​Pss′a​v∗​(s′)

贝尔曼最优方程

最优V函数

v∗(s)=maxa[R(s,a)+γ∑s′∈SPss′av∗(s′)]v_*(s)=\mathop{\text{max}}_a[R(s,a)+\gamma\sum_{s'\in S}P_{ss'}^av_*(s')]v∗​(s)=maxa​[R(s,a)+γs′∈S∑​Pss′a​v∗​(s′)]

最优Q函数

q∗(s,a)=R(s,a)+γ∑s′∈SPss′a maxa′ q∗(s′,a′)q_*(s,a)=R(s,a)+\gamma\sum_{s'\in S}P_{ss'}^a\ \mathop{\text{max}}_{a'}\ q_*(s',a')q∗​(s,a)=R(s,a)+γs′∈S∑​Pss′a​ maxa′​ q∗​(s′,a′)

和贝尔曼期望方程的关系

  • 贝尔曼最优方程本质上就是利用了π*的特点,将求期望的算子转化成了max_a

  • 在贝尔曼期望方程中,π是已知的。而贝尔曼最优方程中,π*是未知的。

  • 解贝尔曼期望方程的过程即对应了评价,解贝尔曼最优方程的过程即对应了优化。

解贝尔曼最优方程

  • 贝尔曼最优方程不是线性的

  • 一般很难有闭式的解

  • 可以使用迭代优化的方法去解

    • 值迭代

    • 策略迭代

    • Q学习

    • SARSA

    • ...

MDPs的扩展

  • 无穷或连续MDPs

  • 部分可观测MDPs(Partially observable MDPs, POMDPs)

  • 无衰减MDPs

无穷或连续MDPs

  • 动作空间或状态空间无限可数

  • 动作空间或状态空间无限不可数 (连续)

  • 时间连续

部分可观测MDPs

  • 此时观测不等于状态Ot≠St

  • POMDPs由七元组成

    <S,A,O,P,R,Z,γ><S,A,O,P,R,Z,\gamma><S,A,O,P,R,Z,γ>
  • 其中Z是观测函数

    Zs′oa=P[Ot+1=o∣St+1=s′,At=a]Z_{s'o}^a=\mathbb{P}[O_{t+1}=o|S_{t+1}=s',A_t=a]Zs′oa​=P[Ot+1​=o∣St+1​=s′,At​=a]
  • 观测不满足马尔科夫性,因此也不满足贝尔曼方程

  • 状态未知,隐马尔科夫过程

  • 有时对于POMDPs来说,最优的策略是随机性的

无衰减MDPs

  • 用于各态历经马尔科夫决策过程

    • 各态历经性:平稳随机过程的一种特性

  • 存在独立于状态的平均奖赏ρ^π

  • 求值函数时,需要减去该平均奖赏,否则有可能奖赏爆炸

参考文献

本章内容是该课程这节课的笔记。

注:具体证明参考

《Total Expected Discounted Reward MDPs: Existence of Optimal Policies 》
《强化学习理论与实践》第二章:马尔科夫决策过程
返回顶层目录
本章在学习地图中的位置
马尔科夫决策过程简介
符号约定
马尔科夫过程
马尔科夫性
状态转移矩阵
状态转移函数
马尔科夫过程
片段
马尔科夫链的例子
马尔科夫奖励过程
马尔科夫奖励过程例子
回报值
再聊片段
再聊衰减值
值函数
例子:回报值和值函数
回报值
针对例子的V函数值
MRPs中的贝尔曼方程
针对例子的贝尔曼方程
贝尔曼方程的矩阵形式
马尔科夫决策过程
马尔科夫决策过程的定义
MDPs例子
策略
MDPs和MRPs之间的关系
MDPs中的值函数
贝尔曼期望方程
V函数与Q函数之间的相互转化
贝尔曼期望方程—V函数
贝尔曼期望方程—Q函数
贝尔曼期望方程例子
贝尔曼期望方程的矩阵形式
最优值函数
最优V函数
最优Q函数
最优策略
最优策略定理
怎么得到最优策略
最优策略例子
v*与q*的相互转化
贝尔曼最优方程
最优V函数
最优Q函数
和贝尔曼期望方程的关系
解贝尔曼最优方程
MDPs的扩展
无穷或连续MDPs
部分可观测MDPs
无衰减MDPs
learning-map
MP-example
MP-example
markov-reward-process-example1
slice
markov-reward-process-example1
value-function-gamma-0
value-function-gamma-1
bellman-equation-example1
MDPs-example1
MDPs-bellman-expectation-equation-example1
v-q-convert
q-v-convert
v-q-v-convert
q-v-q-convert
MDPs-bellman-expectation-equation-example2
optimal-v-function
optimal-q-function
optimal-policies-example
bellman-optical-equition
bellman-optical-equition-2
bellman-optical-equition-V-function
bellman-optical-equition-Q-function