中国科学技术大学：《人工智能基础》课程教学资源（课件讲稿）Lecture 11 马尔可夫决策过程

马尔可夫决策过程 吉建民 USTC jianminOustc.edu.cn 2022年5月5日 4口卡404三·1怎生0C

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 马尔可夫决策过程 吉建民 USTC jianmin@ustc.edu.cn 2022 年 5 月 5 日

Used Materials Disclaimer:本课件大量采用了Rich Sutton's RL class,David Silver's Deep RL tutorial和其他网络课程课件，也采用了GitHub 中开源代码，以及部分网络博客内容 口·三4，进分双0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Used Materials Disclaimer: 本课件大量采用了 Rich Sutton’s RL class, David Silver’s Deep RL tutorial 和其他网络课程课件，也采用了 GitHub 中开源代码，以及部分网络博客内容

Table of Contents 背景 基础 Markov Processes Markov Reward Process Markov Decision Process Extensions to MDPs (Full Observable)Markov Decision Processes (MDPs) Partial Observable MDPs (POMDPs) 4口◆4⊙t1三1=，￥9QC

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents 背景 基础 Markov Processes Markov Reward Process Markov Decision Process Extensions to MDPs (Full Observable) Markov Decision Processes (MDPs) Partial Observable MDPs (POMDPs)

智能体决策 Static vs.Dynamic Environment Fully Vs. Partially Observable Deterministic VS. What action Stochastic next? Perfect Instantaneous VS. VS. Noisy Durative Percepts Actions 口卡·三4色，是分QC

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 智能体决策

环境的不确定性 确定性的环境 不确定性的环境 a 4口◆4⊙t4三1=，￥9QC

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 环境的不确定性

决策树 Success 0.80 Reward:S100 Planl Failure 0.20 Reward:-S1000 0.70 Success Plan2 Reward:$50 0.30 Failure Decision node:You play Reward:-$10 Chance node:Nature plays ~Plan1的期望效用： EU(P1an1)=100×0.80-1000×0.20=-120 Plan2的期望效用：EU(Plan2)=50×0.70-10×0.30=32 ·最大期望效用(MEU):选择行动A;使得期望效用最大

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 决策树 ▶ Plan1 的期望效用： EU(Plan1) = 100 × 0.80 − 1000 × 0.20 = −120 ▶ Plan2 的期望效用：EU(Plan2) = 50 × 0.70 − 10 × 0.30 = 32 ▶ 最大期望效用（MEU）：选择行动 Ai 使得期望效用最大

马尔可夫性质 当一个随机过程在给定现在状态及所有过去状态情况下，其 未来状态的条件概率分布仅依赖于当前状态 在给定现在状态时，随机过程与过去状态（历史）是条件独 立的 定义 A state st is Markov if and only if Pst+1|st]=P[st+1|51,.,st] ·状态包含了关于历史的所有信息 ·一旦知道当前状态，过去的历史可以完全抛弃 。当前状态足够用来预计未来 这一性质能够简化问题的表示和求解，但提高了对信息全局 性和充分性的要求 口◆4日t1三1声，是90C

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 马尔可夫性质 ▶ 当一个随机过程在给定现在状态及所有过去状态情况下，其 未来状态的条件概率分布仅依赖于当前状态 ▶ 在给定现在状态时，随机过程与过去状态（历史）是条件独 立的 定义 A state st is Markov if and only if P[st+1 | st ] = P[st+1 | s1, . . . ,st ] ▶ 状态包含了关于历史的所有信息 ▶ 一旦知道当前状态，过去的历史可以完全抛弃 ▶ 当前状态足够用来预计未来 ▶ 这一性质能够简化问题的表示和求解，但提高了对信息全局 性和充分性的要求

MDPs概述 ~马尔可夫决策过程(Markov Decision Processes,.MDPs) ·人工智能、决策分析、运筹学、控制论和经济学共同关注 ·大量实际问题可以用MDPs表达、研究 ·MDPs借助于概率作为刻画不确定性的基本手段 ·MDPs类型： ,完全可观察的MDPs(Full Observable MDPs):FOMDPs 完全不可观察的MDPs:NOMDPs 部分可观察的MDPs(Partial Observable MDPs):POMDPs 口卡回t·三4色，是分Q0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . MDPs 概述 ▶ 马尔可夫决策过程（Markov Decision Processes, MDPs） ▶ 人工智能、决策分析、运筹学、控制论和经济学共同关注 ▶ 大量实际问题可以用 MDPs 表达、研究 ▶ MDPs 借助于概率作为刻画不确定性的基本手段 ▶ MDPs 类型： ▶ 完全可观察的 MDPs (Full Observable MDPs): FOMDPs ▶ 完全不可观察的 MDPs: NOMDPs ▶ 部分可观察的 MDPs (Partial Observable MDPs): POMDPs

Table of Contents 背景 基础 Markov Processes Markov Reward Process Markov Decision Process Extensions to MDPs (Full Observable)Markov Decision Processes (MDPs) Partial Observable MDPs (POMDPs) 4口◆4⊙t1三1=，￥9QC

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents 背景 基础 Markov Processes Markov Reward Process Markov Decision Process Extensions to MDPs (Full Observable) Markov Decision Processes (MDPs) Partial Observable MDPs (POMDPs)

Table of Contents 背景 基础 Markov Processes Markov Reward Process Markov Decision Process Extensions to MDPs (Full Observable)Markov Decision Processes (MDPs) Partial Observable MDPs (POMDPs) 口卡B·三4色进分双0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents 背景 基础 Markov Processes Markov Reward Process Markov Decision Process Extensions to MDPs (Full Observable) Markov Decision Processes (MDPs) Partial Observable MDPs (POMDPs)