强化学习读书笔记 - 04 - 动态规划

强化学习读书笔记 - 04 - 动态规划

学习笔记: Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto c 2014, 2015, 2016 数学符号看不懂的,先看看这里:

动态规划(Dynamic Programming) - 计算最优策略的一组算法。

策略

强化学习的一个主要目的是:找到最优策略。 我们先要明白什么是策略? 策略告诉主体(agent)在当前的状态下,应该选择哪个行动。 我们稍微数据化上面的说法,变成: 策略告诉主体(agent)在每个状态\(s\)下,选择行动\(a\)的可能性。

脑补一下:想象一个矩阵: 每一行代表一个state, 每一列代表一个action, 单元的值是一个取值区间为\([0, 1]\)的小数,代表对应状态-行动的选择概率。

最优策略(Optimal Policy)

最优策略是可以取得最大的长期奖赏的策略。 长期奖赏就是\(G_t\) 因此,我们需要对策略进行价值计算。计算的方法在强化学习读书笔记 - 03 - 有限马尔科夫决策过程讲了。 有两个计算公式:一个是策略的状态价值公式,一个是策略的行动价值公式。 策略的状态价值公式有利于发现哪个状态的价值高。也就是找到最优状态。 策略的行动价值公式有利于发现(在特定状态下)哪个行动的价值高。也就是找到最优行动。

通用策略迭代(Generalized Policy Iteration)

动态规划的基本思想 - 通用策略迭代是:

  1. 先从一个策略\(\pi_0\)开始,
  2. 策略评估(Policy Evaluation) - 得到策略\(\pi_0\)的价值\(v_{\pi_0}\)
  3. 策略改善(Policy Improvement) - 根据价值\(v_{\pi_0}\),优化策略为\(\pi_0\)。
  4. 迭代上面的步骤2和3,直到找到最优价值\(v_*\),因此可以得到最优策略\(\pi_*\)(终止条件:得到了稳定的策略\(\pi\)和策略价值\(v_{pi}\))。

这个被称为通用策略迭代(Generalized Policy Iteration)。 数学表示如下: \[ \pi_0 \xrightarrow{E} v_{\pi_0} \xrightarrow{I} \pi_1 \xrightarrow{E} v_{\pi_1} \xrightarrow{I} \pi_2 \xrightarrow{E} \cdots \xrightarrow{I} \pi_* \xrightarrow{E} v_* \]

因此,我们需要关心两个问题:如何计算策略的价值,以及如何根据策略价值获得一个优化的策略。

策略迭代(Policy Iteration)的实现步骤

步骤如下:请参照书上的图4.1。

  1. 初始化 - 所有状态的价值(比如:都设为0)。 所有的状态\(\mathcal{S} = \{ s_0, s_1,...,s_n\}\)是一个集合。 数学表示:\(\vec{V_0(s)} = [0, \dots, 0]\)
  2. 初始化 - 一个等概率随机策略\(\pi_0\) (the equiprobable random policy) 等概率随机策略 - 意味着每个行动的概率相同。 数学表示: \pi = \begin{bmatrix} \dots & \dots & \dots \\ \dots & \pi(s, a) & \dots \\ \dots & \dots & \dots \\ \end{bmatrix} \\ where \\ \pi \text{ - a matrix for each state s and action a} \\ \pi(s, a) = \begin{cases} \frac{1}{N_a}, \text{a is selected under state s by } \pi \\ 0, otherwise \\ \end{cases} \\ N_a \text{ - the count of actions selected under state s by } \pi 矩阵\(\pi\)就是我们的策略,我们反过来看,如果一个单元的值不是0,说明该策略选择了这个行动,如果为0,说明该策略不选择这个行动。 初始的时候:一个状态\(s\)对应的所有可能行动\(a\),都是有值的。 关键理解: 找到最优策略的过程就是优化矩阵\(\pi\) - 减少每个状态\(s\)选的行动\(a\)
  3. 策略迭代 - 策略评估过程 根据\(\pi\)计算状态价值\(\vec{V_{k+1}(s)}\) 迭代策略评估公式 - iterative policy evaluation - Bellman update rule \begin{align} v_{k+1}(s) & = \mathbb{E}_{\pi} \left [ R_{t+1} + \gamma v_k(S_{t+1}) \ | \ S_t = s \right ] \\ & = \sum_{a} \pi(a|s) \sum_{s',r} p(s',r|s,a) \left [ r + \gamma v_{k}(s') \right], \ \forall s \in \mathcal{S} \end{align}
  4. 策略迭代 - 策略优化过程 根据状态价值\(\vec{V_{k+1}(s)}\),优化策略\(\pi\)。 关键: 优化方法 - 对于每个状态\(s\),只保留可达到最大状态价值的行动。 举例说明: 你是一个初级程序员(5),你有4个选择:成为A: 架构师(10),B: 项目经理(10),C: 测试(8),D: 运营(8)。 括号里的是状态价值。由于架构师(10),项目经理(10)的价值最大。 所以,只保留行动A和B。

数学表示: \begin{align} \pi'(s) & = \underset{a}{argmax} \ q_{\pi}(s, a) \\ & = \underset{a}{argmax} \ \sum_{s', r} p(s',r|s,a) \left [ r + \gamma v_{\pi}(s') \right ] \\ \end{align} \\ \because q_{\pi}(s, \pi'(s)) \ge v(\pi), \ \forall s \in \mathcal{S} \\ \therefore v_{\pi}'(s) \ge v_{\pi}(s) \\ v_{\pi}(s) = v_{\pi}'(s) \\ where \\ \pi'(s) \text{ - action(s) selected under the state s by policy } \pi' 注意:这是一个贪恋的策略(greedy policy),因为只做了一步价值计算。

  1. 迭代结束条件 - 得到了稳定的策略\(\pi\)和策略价值\(v_{pi}\) 策略\(\pi\)稳定 - 即\(\pi_{k+1} = \pi_k\)。

策略评估公式说明

下面这个是第三章讲的策略状态价值公式: \begin{align} v_{\pi}(s) & \doteq \mathbb{E}_{\pi} \left [ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s \right ] \\ & = \sum_{a} \pi(a|s) \sum_{s',r} p(s',r|s,a) \left [ r + \gamma v_{\pi}(s') \right], \ \forall s \in \mathcal{S} \end{align} 可以看出状态\(s\)在策略\(v_pi\)上的价值是由其它状态\(s'\)在策略\(v_pi\)的价值决定的。 简单地想一想,就会发现这个公式难以(不能)被实现。

因此:我们使用了一个迭代的公式: 迭代策略评估公式 - iterative policy evaluation - Bellman update rule \begin{align} v_{k+1}(s) & = \mathbb{E}_{\pi} \left [ R_{t+1} + \gamma v_k(S_{t+1}) \ | \ S_t = s \right ] \\ & = \sum_{a} \pi(a|s) \sum_{s',r} p(s',r|s,a) \left [ r + \gamma v_{k}(s') \right], \ \forall s \in \mathcal{S} \end{align} 这个公式和策略状态价值公式很像。 仔细比较一下,就会发现这个公式的\(v_{k+1}(s)\)是由\(v_{k}(s')\)计算得到的。 这就有了可行性。为什么呢?因为我们可以定义\(v_0(s) = 0, \ \forall s \in \mathcal{S}\)。 这样就可以计算\(v_1(s), \ \forall s \in \mathcal{S}\),以此类推,经过多次迭代(\(k \to \infty\)), \(v_k \cong v_{\pi}\)。

价值迭代(Value Iteration)

价值迭代方法是对上面所描述的方法的一种简化: 在策略评估过程中,对于每个状态\(s\),只找最优(价值是最大的)行动\(a\)。这样可以减少空间的使用。

  1. 初始化 - 所有状态的价值(比如:都设为0)。
  2. 初始化 - 一个等概率随机策略\(\pi_0\) (the equiprobable random policy)
  3. 策略评估 对于每个状态\(s\),只找最优(价值是最大的)行动\(a\)。 数学表示: 简化策略评估迭代公式 \begin{align} v_{k+1}(s) & \doteq \underset{a}{max} \ \mathbb{E} \left [ R_{t+1} + \gamma v_k(S_{t+1}) \ | \ S_t = s , A_t = a\right ] \\ & = \underset{a}{max} \ \sum_{s',r} p(s',r|s,a) \left [ r + \gamma v_{k}(s') \right] \end{align} \\ where \\ \underset{a}{max}(.) \text{ - get the max value } \forall a \in \mathcal{A(s)}
  4. 策略优化 没有变化。

总结

通用策略迭代(DPI)是一个强化学习的核心思想,影响了几乎所有的强化学习方法。 通用策略迭代(DPI)的通用思想是:两个循环交互的过程,迭代价值方法(value function)和迭代优化策略方法。

动态规划(DP)对复杂的问题来说,可能不具有可行性。主要原因是问题状态的数量很大,导致计算代价太大。

参照

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

塔说 | 如何理解深度神经网络中的泛化理论?

前言 近年来的深度神经网络研究进展往往都重方法而轻理论,但理论研究能够帮助我们更好地理解深度学习成功背后的真正原因,并有望为进一步的研究指明方向。近日,普林斯顿...

40560
来自专栏目标检测和深度学习

2017年历史文章汇总|深度学习

11820
来自专栏机器人网

零基础入门深度学习工作原理?人人都能看懂!

在入门学习深度学习之前,有必要先了解一下深度学习的工作原理。著名程序猿小哥 Radu Raicea 特意为入门学习者写了一篇文章,利用一个票价预测工具的例子解释...

10730
来自专栏机器之心

吴恩达授课,斯坦福CS230深度学习课程资源开放

课程地址:https://web.stanford.edu/class/cs230/

11220
来自专栏人工智能头条

特征选择算法在微博应用中的演进历程

19830
来自专栏机器之心

深度 | 思考VC维与PAC:如何理解深度神经网络中的泛化理论?

39540
来自专栏数据派THU

揭秘深度学习成功的数学原因:从全局最优性到学习表征不变性

来源:机器之心 本文长度为4900字,建议阅读7分钟 本文为深层网络的若干属性,如全局最优性、几何稳定性、学习表征不变性,提供了一个数学证明。 近年来,深度学习...

29070
来自专栏刘明的小酒馆

深度学习入门与自然语言理解

深度学习是机器学习领域的一个分支,也可以说是该领域近些年来的最大突破之一。

54690
来自专栏机器之心

揭秘深度学习成功的数学原因:从全局最优性到学习表征不变性

42790
来自专栏MyBlog

关于强化学习(1)

来源于Simple statistical gradient-following algorithms for connectionist reinforcem...

21230

扫码关注云+社区

领取腾讯云代金券