为什么需要第二种算法
“折扣决策与价值迭代”一课把最优价值向量 算作 Bellman 更新的极限,再读出贪心策略。价值迭代要得到精确答案,需要无限多次扫描。策略迭代利用另一个事实:固定的策略可以通过解线性方程组精确评估,而针对该精确价值作贪心一步只会有益无害。有限的决策问题只有有限个平稳策略,因此评估与改进交替进行,必在有限轮后停在最优策略。本单元证明这些论断,沿用价值迭代一课的记号:有限状态集 、有限动作集 、转移概率 、奖励 、折扣 ,以及 Bellman 算子 。
定义
定义 34.1.1
(平稳策略及其算子)
平稳确定性策略是函数 ,对每个状态有 。记 ,并令 为元素 的矩阵,其每一行都是概率向量。对价值向量 定义
定义 34.1.2
(策略价值、动作价值与贪心策略)
的价值 是期望折扣回报 。对向量 ,动作价值为 。若对每个 , 都使 最大,就称 对 贪心,等价于 。向量之间的不等式逐分量理解。
评估、单调性与改进
定理 34.1.3
(策略评估)
矩阵 可逆,,且 是 的唯一解。
证明
(由范数界得到可逆性)
若 ,则 。 的每一行都是概率向量,故 ,从而 。因 ,,所以矩阵可逆, 恰有一个解。对第一步转移取条件,得 ,所以 就是该解。
概念视角分析
把评估看成期望奖励的折扣和
因为 ,逆矩阵是收敛级数:
分量 是从 出发、在时刻 的期望奖励,所以这正是把 定义为期望折扣回报、再对时间求和。线性方程组是我们实际计算用的描述;级数描述则解释了为什么该解就是策略的价值,以及为什么需要 。
引理 34.1.4
(备份算子的单调性)
若 ,则 且 。
证明
(更大的价值给出更大的备份)
权重 非负,所以每个 ;较小数的最大值也较小。
定理 34.1.5
(策略改进)
设 对 贪心,则 。此外,若 ,则 ,从而 。
证明
(反复应用贪心备份)
因 贪心,。反复应用 并用单调性引理,对所有 有 。由价值迭代一课的压缩论证,,即 的唯一不动点。对不等式取极限得 。若 ,则 ,所以 是 的不动点,即 。
定理针对精确的价值 陈述。实际中不精确评估的变体,需要另外论证。
算法及其终止
策略迭代。 从任意策略 开始。对 :
- *评估:*解 得 。
- *改进:*对每个 ,令 。若 ,则取 ;否则任选一个使其最大的动作。
- 若 ,停止并返回 。
“若现有动作已达最大值就保留”这条规则是必要的。
定理 34.1.6
(策略迭代终止于最优策略)
策略迭代至多评估 次便停止,所返回的策略是最优的,价值为 。
证明
(严格上升的价值不会重复策略)
由策略改进定理,。设 。若 ,定理给出 ,于是 ,即现有动作在每个状态都达到最大值,按保留规则便得 ,与 矛盾。所以价值向量不减,且每次改变策略时都严格不同;因此没有策略会重复出现。策略只有 个,故过程必停止。在停止的策略处,,即 ,所以 , 达到最优价值。
证明透视
每个条件各自提供什么
不显然的一步,是把“策略改变了”转成“价值严格上升了”。精确评估加上贪心改进,给出 ;保留规则则保证,只有在某个动作严格更好时策略才会改变,因而排除 。一个不减、而且每步都不同的序列不会回到先前的价值,也就不会回到先前的策略,再由策略集有限便完成论证。去掉保留规则,中间一步就失效,下面的反例会说明;去掉 ,连评估一步也可能无解。
每一轮需要解一个线性方程组(高斯(Gauss)消元为 ),加上改进步骤的 ;价值迭代每次扫描只需后者,但要达到精度 ,所需扫描次数按 增长。界 远大于实际常见的轮数,但这是此处所证的界。
反例模式
在平局的最大值之间来回切换永不停止
论断:任何选取最大化动作的改进步骤都会终止。取一个状态和两个动作 ,各自奖励 并回到该状态,。对任一策略,,故 ,且 。两个策略都是最优的。若规则总是改选另一个达到最大值的动作,就会 交替下去而永不停止,尽管每个策略早已最优。保留规则则立即停止,因为 。修正后的论断需要这条规则:只有在存在严格更好的动作时才更换动作。
例题
例题 34.1.7
(两状态问题的两轮迭代)
两个状态 ,折扣 。状态 :动作 奖励 ,以各 的概率转移到 或 ;动作 奖励 ,留在 。状态 :动作 奖励 ,留在 ;动作 奖励 ,以各 的概率转移到 或 。以 开始。
评估 。 得 ; 得 。故 。
改进。 以 :,;,。所以 。
评估 。 方程为 与 。相减得 。把 代入第一式:,所以 ,。确实 。
改进。 ,;,。现有动作均达最大值,故 ,算法停止。因此 ,最优策略为 ,共评估两次。
例题 34.1.8
(同一个评估写成矩阵方程)
对上例的 , 的两行都是 ,。于是
行列式为 。方程组乘以 得 与 。由第一式 ,代入得 ,所以 ,,与前面的向量相同。两行都满足 :,以及 。
例题 34.1.9
(折扣为零的边界情形)
在第一个例题中取 。此时 ,,评估毫不费力。由 得 ,改进只是比较即时奖励:,。所以 ,;下一次改进时现有动作已达最大值,算法在两次评估后停止。 时完全不顾未来,贪心改进恰好就是选即时奖励最大的动作; 时则不然,见下一节。
常见错误与细微之处
常见错误
(对奖励而不是对价值作改进)
选取即时奖励 最大的动作会忽略未来,未必改进策略。设状态 有动作 (奖励 ,留在 )与动作 (奖励 ,转移到状态 ),状态 只有一个动作 (奖励 ,留在 );。对 ,,。若改选即时奖励较大的动作,得到 ,。以价值为准的检验比较 与 ,故保留 。
常见错误
(折扣为一时仍使用评估步骤)
的可逆性用了 。若 ,且只有一个状态、一个奖励为 并留在原处的动作,则 , 奇异,方程 无解。上述形式的策略迭代是折扣情形的算法。
习题
快速检查
(在第一个例题中评估策略 。)
先解状态 的方程。
解答 · 答案
对 :,故 。于是 ,,。价值为 。
快速检查
(第一个例题中策略 的价值为 。作一步改进。新策略的价值是否更大?)
算出全部四个动作价值。
解答 · 答案
以 :,,故保留 。,,故改为 。新策略为 ,价值 。
快速检查
(在第一个例题中,从 开始策略迭代。共作多少次评估?)
使用该例题已求得的价值。
解答 · 答案
一次。评估得 ,在此价值下两个状态的现有动作都达到最大值(,),故 ,算法立即停止。
练习 34.1.10
(在第一个例题中评估 ,并作一次改进。)
核心
解答(3)
- 1
评估策略
得 。然后 ,所以 ,。价值为 。
- 2
计算动作价值
关键一步
,。又 ,。
- 3
逐个状态决定保留或改换
状态 :,改为 。状态 :,保留 。新策略为 。
练习 34.1.11
(设 ,,。证明 可逆,并求 。)
核心
解答(3)
- 1
用行列式证明可逆
的行列式为 ,故可逆。
- 2
解线性方程组
关键一步
方程为 与 。第二式给出 ,所以 ,得 ,。
- 3
验算 Bellman 方程
,且 。所以 。