常见概念
马尔科夫决策过程(Markov DecisionProcess, MDP). 强化学习的数学基础和建模工具, 通常由状态空间, 动作空间, 奖励函数, 状态转移函数, 折扣率等组合.
马尔科夫性质(Markov Property). 马尔科夫性质指的是下一个状态仅依赖于当前的时刻下的状态和动作.
环境(Environment). 环境是一种比较宏观上的概念, 比如下棋游戏中整个棋盘与双方玩家都处于同一个环境中. 在每个时刻下环境都会有一个状态, 这个状态可以理解为对当前时刻环境的概括.
状态空间(State Space). 指所有可能存在的状态的集合, 通常用花体字 $\mathcal{S}$. 状态空间可以是离散的也可以是连续的, 可以是有限集合也可以是无限集合.
动作空间(Action Space). 动作是指智能体在当前状态下所做出的决策. 而动作空间则是指所有可能动作的集合$\mathcal{A}$.
奖励(Reward). 智能体在执行一个动作之后环境返回给智能体的一个数值. 奖励通常由我们自己定义的奖励函数来决定数值的大小.
状态转移(State Transition). 指智能体从当前 $t$ 时刻的状态 $s$ 转移到下一个状态 $s'$ 的过程. 这个过程可能是随机的, 并且强化学习通常都假设状态转移是随机的, 其随机性来自于环境本身. 这个过程可以用状态转移函数(State Transition Function)来描述:
$$ p_t(S'|s,a) = \mathbb{P}(S^{'}_{t+1} = s' | S_t=s, A_t = a) $$在当前状态 $s$, 执行动作 $a$, 环境变成 $s'$ 的概率.
策略(Policy). 指如何通过观察到的状态做出决策, 即如何从动作空间中选取一个动作, 策略可以是确定性的也可以是随机性的. 而强化学习的目标就是训练一个策略函数. 在随机性策略中, 策略函数的输入会是状态 $s$ 和动作 $a$, 并告诉我们每个动作的概率值. 此时如果让策略函数 $\pi$ 来做出操作, 则会根据概率进行一个随机采样. 决定性策略则可以看做是随机性策略的一种特例, 即概率全部都集中在一种动作上.
轨迹(Trajectory). 在一个episode中所有状态 $s$, 动作 $a$ 和奖励 $r$ 的集合.
回报(Return). 回报由即时奖励和未来奖励组成, 强化学习的目标就是寻找一个策略函数可以使这个回报最大化, 被训练出来的策略就叫最优策略(Optimum Policy).
$$ G_{t} = R_t + R_{t+1} + R_{t+1} + \dots + R_{n} $$折扣回报. 在MDP中通常会对未来的回报做个折扣率.
$$ G_{t} = R_t + \gamma \cdot R_{t+1} + \gamma^2 \cdot R_{t+1} + \dots + \gamma^{n-t} \cdot R_{n} $$状态值(State Value)与贝尔曼方程(Bellman Equation)
当我们沿着一个轨迹就可以获得一个折扣回报:
$$ G_{t} = R_t + \gamma \cdot R_{t+1} + \gamma^2 \cdot R_{t+1} + \dots + \gamma^{n-t} \cdot R_{n} $$由于 $G_t$ 是由随机变量组成的, 因此它本身也是随机变量. 那我们要如何评估 $G_t$ 来判断回报的好坏? 在这里我们可以通过计算他的期望来消去随机变量的影响:
$$ v_\pi(s)=\mathbb{E}[G_t|S_t=s] $$这里的 $v_\pi(s)$ 被称为状态价值函数(State-value Function). 我们可以看到这个函数依赖于当前状态 $s$ 和策略 $\pi$ 但并不依赖于时刻 $t$. 因为我们通常会假设环境所处的系统是平稳的, 不会随着时间变化.
首先, $G_{t}$ 可以被写成:
$$ \begin{aligned} G_{t} &= R_{t+1} + \gamma \cdot R_{t+1} + \gamma^2 \cdot R_{t+1} + \dots \\ &= R_{t+1} + \gamma (\cdot R_{t+1} + \gamma \cdot R_{t+1} + \dots )\\ &= R_{t+1} + \gamma G_{t+1} \end{aligned} $$因此我们可以进一步对状态价值函数进行展开.
$$ \begin{aligned} v_{\pi}(s) &= \mathbb{E}[G_t | S_t = s] \\ &= \mathbb{E}[R_{t+1} + \gamma G_{t+1} | S_t = s] \\ &= \mathbb{E}[R_{t+1} | S_t = s] + \gamma \mathbb{E}[G_{t+1} | S_t = s]. \end{aligned} $$第一项 $\mathbb{E}[R_{t+1} | S_t = s]$ 可以基于全期望公式进行展开.
$$ \begin{aligned} \mathbb{E}[R_{t+1}|S_t = s] &= \sum_{a \in \mathcal{A}} \pi(a|s) \mathbb{E}[R_{t+1}|S_t = s, A_t = a] \\ &= \sum_{a \in \mathcal{A}} \pi(a|s) \sum_{r \in \mathcal{R}} p(r|s, a)r. \end{aligned} $$第二项 $\mathbb{E}[G_{t+1} | S_t = s]$ 是未来奖励的期望值. 也可以被进一步展开.
$$ \begin{aligned} \mathbb{E}[G_{t+1}|S_t = s] &= \sum_{s' \in S} \mathbb{E}[G_{t+1}|S_t = s, S_{t+1} = s']p(s'|s) \\ &= \sum_{s' \in S} \mathbb{E}[G_{t+1}|S_{t+1} = s']p(s'|s) \quad (\text{由于马尔可夫性质}) \\ &= \sum_{s' \in S} v_\pi(s')p(s'|s) \\ &= \sum_{s' \in S} v_\pi(s') \sum_{a \in A} p(s'|s, a)\pi(a|s). \end{aligned} $$将展开后的两项代入原式:
$$ \begin{aligned} v_{\pi}(s) &= \mathbb{E}[R_{t+1} | S_t = s] + \gamma \mathbb{E}[G_{t+1} | S_t = s] \\ &= \underbrace{\sum_{a \in \mathcal{A}} \pi(a|s) \sum_{r \in \mathcal{R}} p(r|s, a) r}_{\text{即时奖励的期望}} + \underbrace{\gamma \sum_{a \in \mathcal{A}} \pi(a|s)\sum_{s' \in \mathcal{S}} p(s'|s, a) v_{\pi}(s')}_{\text{未来奖励的期望}} \\ &= \sum_{a \in \mathcal{A}} \pi(a|s) \left[ \sum_{r \in \mathcal{R}} p(r|s, a) r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s, a) v_{\pi}(s') \right], \quad s \in \mathcal{S}. \end{aligned} $$上方式子就是著名的贝尔曼方程, 它描述了不同状态值之间的关系, 是设计和分析强化学习的基本工具. 其中 $v_\pi(s) $ 和 $ v_\pi(s')$ 是需要计算的状态值, 为未知量. $\pi(a|s)$ 是一个给定的策略, 为已知量. $p(r|s,a)$ 和 $p(s'|s,a)$代表系统模型, 可以是已知量也可以是未知量.
贝尔曼方程有多种等价形式:
$$ v_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \sum_{s' \in \mathcal{S}} \sum_{r \in \mathcal{R}} p(s', r|s, a) [r + \gamma v_\pi(s')]. $$这个式子可以通过全概率公式的到
$$ p(s'|s, a) = \sum_{r \in \mathcal{R}} p(s', r|s, a), \\ p(r|s, a) = \sum_{s' \in \mathcal{S}} p(s', r|s, a). $$- 第二个常见的形式是贝尔曼期望方程(Bellman Expectation Equation), 通过代入 $\mathbb{E}[G_{t+1}|S_t = s] = \sum_a \pi(a|s) \sum_{s'} p(s'|s, a) v_\pi(s') = \mathbb{E}[v_\pi(S_{t+1})|S_t = s],$ 得到.
- 奖励 $r$ 在某些情况下可能只依赖于下一个状态 $s'$, 即奖励可以写成 $r(s')$. 此时会有 $p(r(s′)∣s,a)=p(s′∣s,a)p(r(s′)∣s,a)=p(s′∣s,a)$ 并得到另一个表达式
矩阵-向量形式
为了推导出矩阵-向量形式, 首先将式(2.9)中的贝尔曼方程重写为
$$ v_{\pi}(s) = r_{\pi}(s) + \gamma \sum_{s' \in S} p_{\pi}(s'|s)v_{\pi}(s') $$其中
$$ \begin{aligned} r_{\pi}(s) &\doteq \sum_{a \in A} \pi(a|s) \sum_{r \in R} p(r|s, a)r,\\ p_{\pi}(s'|s) &\doteq \sum_{a \in A} \pi(a|s)p(s'|s, a). \end{aligned} $$这里 $r_{\pi}(s)$ 表示即时奖励的期望值, 而 $p_{\pi}(s'|s)$ 代表在策略 $\pi$ 下从状态 $s$ 经过一步转移到状态 $s'$ 的概率.
为了写成矩阵-向量形式, 需要对状态进行编号. 如果有 $n = |S|$ 个状态, 那么给这 $n$ 个状态编号为 ${s_1, s_2, \dots, s_n}$. 对于状态 $s_i$, 可以写成
$$ v_\pi(s_i) = r_\pi(s_i) + \gamma \sum_{s_j \in S} p_\pi(s_j|s_i)v_\pi(s_j) $$定义 $v_\pi = [v_\pi(s_1), \dots, v_\pi(s_n)]^T \in \mathbb{R}^n$, $r_\pi = [r_\pi(s_1), \dots, r_\pi(s_n)]^T \in \mathbb{R}^n$, 以及 $P_\pi \in \mathbb{R}^{n \times n}$, 其中 $P_\pi$ 满足 $[P_\pi]{ij} = p\pi(s_j|s_i)$. 此时上式可以用下列矩阵-向量形式来表示:
$$ v_\pi = r_\pi + \gamma P_\pi v_\pi $$这里 $v_\pi$ 是待解的未知量, 而 $\gamma$, $r_\pi$, $P_\pi$ 是已知量. 说这么多话其实就是展开后用矩阵的形式来表达, 参考以下例子
将例图中的具体数值代入后可得
$$ \begin{bmatrix} v_\pi(s_1) \\ v_\pi(s_2) \\ v_\pi(s_3) \\ v_\pi(s_4) \end{bmatrix} = \begin{bmatrix} 0.5(0) + 0.5(-1) \\ 1 \\ 1 \\ 1 \end{bmatrix} + \gamma \begin{bmatrix} 0 & 0.5 & 0.5 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} v_\pi(s_1) \\ v_\pi(s_2) \\ v_\pi(s_3) \\ v_\pi(s_4) \end{bmatrix}. $$动作值(Action Value)
状态值用来计算当前状态的好坏, 这个数值是统计了当前状态下所有动作的期望. 同理, 我们也会有动作值. 在每个状态下我们都可以组成很多个 状态-动作配对(State-action Pair) $(s,a)$ 其动作值的定义为
$$ q_\pi(s,a)=E[G_t|S_t = s, A_t=a] $$从上式中不难看出动作值被定义为在一个状态 $s$ 时采取动作 $a$ 后获得回报的期望值. 动作值有时候也被称为 状态-动作值 , 因为他取决于状态和动作的配对.
实际上, 这个动作值就来取自于状态值中:
$$ \underbrace{\mathbb{E}[G_t | S_t = s]}_{v_\pi(s)} = \sum_{a \in \mathcal{A}} \underbrace{\mathbb{E}[G_t | S_t = s, A_t = a]}_{q_\pi(s,a)} \pi(a | s). $$因此:
$$ \begin{aligned} v_\pi(s)&=\sum_{a \in A}\pi(a|s)q_\pi(s,a) \\ &= \mathbb{E}_{A_t \sim\pi(s)}[q_\pi(s,A_t)] \end{aligned} $$其二, 因为状态值也可以有如下表达式:
$$ v_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \underbrace{\left[ \sum_{r \in \mathcal{R}} p(r|s, a) r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s, a) v_{\pi}(s') \right]}_{q_\pi(s,a)} $$因此实际上动作值是一个包含状态值变量的期望值:
$$ \begin{aligned} q_{\pi}(s, a) &= \sum_{r \in \mathcal{R}} p(r|s, a)r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s, a)v_{\pi}(s') \\ &= \mathbb{E}[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t = s, A_t = a]. \end{aligned} $$策略更新
假如我们有如图上的一个环境, 在这个环境中可以进行上右下左和呆在原地5个动作, 分别代表了 $a_{1\sim5}$, 并且有一个已知的策略. 那么我们可以根据直觉, 和回报=即时奖励+未来回报快速的得出每个状态的贝尔曼方程:
$$ \begin{aligned} v_\pi(s_1) &= -1 + \gamma v_\pi(s_2) \\ v_\pi(s_2) &= 1 + \gamma v_\pi(s_3) \\ v_\pi(s_3) &= 1 + \gamma v_\pi(s_4) \\ v_\pi(s_4) &= 1 + \gamma v_\pi(s_4) \\ \end{aligned} $$设 $\gamma = 0.9$, 可以快速得出
$$ v_\pi(s_4)=v_\pi(s_3)=v_\pi(s_2) = 10, \\ v_\pi(s_1) = 8 $$很明显 我们需要对状态 $s_1$ 进行策略选择上的优化, 因此我们可以首先计算出这个状态下所有的动作值
$$ \begin{aligned} q_{\pi}(s_1, a_1) &= -1 + \gamma v_{\pi}(s_1) = 6.2, \\ q_{\pi}(s_1, a_2) &= -1 + \gamma v_{\pi}(s_2) = 8, \\ q_{\pi}(s_1, a_3) &= 0 + \gamma v_{\pi}(s_3) = 9, \\ q_{\pi}(s_1, a_4) &= -1 + \gamma v_{\pi}(s_1) = 6.2, \\ q_{\pi}(s_1, a_5) &= 0 + \gamma v_{\pi}(s_1) = 7.2. \end{aligned} $$通过比较可以看出策略 $q_\pi(s_1, a_3)$ 的回报最高的, 这也符合我们的直觉. 因此不论从直觉推断还是数理推断, 我们都应该更新策略使在状态 $s_1$ 时选择动作 $a_3$.
以上例子就是策略更新最简单的一个步骤, 在这个环境中其他状态和策略都有良好的选择, 只有 $s_1$ 的状态值较差.
最优策略(Optimal Policy)
假如我们存在一个策略 $\pi$, 它在任意的状态 $s\in S$ 下状态值都大于等于其他所有策略 $\pi$. 那么该策略为最优策略 $\pi^*$
$$ v_\pi^*(s) ≥ v_\pi(s), \text{for all }s \in S $$上述定义表明了一个最优策略在每一个状态下比所有其他策略都有更高的状态值, 但也要批判性思考一下以下问题.
- 存在性: 这样的策略真的存在吗?
- 唯一性: 这样的最优策略是唯一的吗?
- 随机性: 最优策略是随机性的还是确定性的?
- 算法: 有什么算法可以求出最优策略和最优状态值?
贝尔曼最优方程(Bellman Optimality Equation)
贝尔曼方程(BOE)是用来分析和求解出最优策略和最优状态的工具, 对于每个 $s \in S$, 贝尔曼最优方程的表达式如下:
$$ \begin{aligned} v(s) &= \max_{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a|s) \left( \sum_{r \in \mathcal{R}} p(r|s, a)r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s, a)v(s') \right) \\ &= \max_{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a|s) q(s, a), \\ \end{aligned} $$其中 $v(s), s(s')$ 是需要求解的变量; $\pi(s)$表示状态 $s$ 的策略; $\Pi(s)$ 是在状态 $s$ 下所有可能策略的集合; 并且
$$ q(s, a) \doteq \sum_{r \in \mathcal{R}} p(r|s, a)r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s, a)v(s') $$首先, 来看一个例题. 给定 $q_1, q_2, q_3 \in \mathbb{R}$, 我们希望能找到 $c_1, c_2, c_3$的最优值从而求解下例的问题:
$$ \mathop{max}\limits_{c_1, c_2, c_3}\sum^3_{i=1}c_iq_i = \mathop{max}\limits_{c_1, c_2, c_3}(c_1q_1 + c_2q_2 + c_3q_3), $$其中 $c_1+c_2+c_3 = 1$ 且 $c_1, c_2, c_3 \geq 0$.
首先不论取数如何 $q_1, q_2, q_3$ 当中一定有一个是最大值, 那我们可以在不失一般性的情况下假设 $q_3 \geq q_2, q_1$. 接着我们回到这个问题本身, 如果我们先暂时忽略掉式子中的 $\mathop{max}\limits_{c_1, c_2, c_3}$ . 在 $c_1+c_2+c_3 = 1$ 的前提下式子 $\sum^3_{i=1}c_iq_i = (c_1q_1 + c_2q_2 + c_3q_3)$ 实际上就是在计算期望. 因此这个最优值问题实际上就是概率分布下的加权平均最大化问题, 期望永远只会小于等于最大值, 因此我们只要让 $c_3 \gg c_2, c_1$. 那么最优解一定是最极端的 $c^_3=1, c^_2=c^*_1=0$, 这是因为
$$ q_3=(c_1+c_2+c_3)q_3=c_1q_3+c_2q_3+c_3q_3 \geq c_1q_1+c_2q_2+c_3q_3 $$顺着上述例子的启发, 我们知道 $\sum_{a \in \mathcal{A}} \pi(a|s)=1$, 便可以有
$$ \sum_{a \in \mathcal{A}} \pi(a|s) q(s, a) \leq \sum_{a \in \mathcal{A}} \pi(a|s) \max_{a \in \mathcal{A}} q(s, a) = \max_{a \in \mathcal{A}} q(s, a), $$即 $\sum_{a \in \mathcal{A}} \pi(a|s) q(s, a)$ 的最大值是 $\max_{a \in \mathcal{A}} q(s, a)$, 而且成立的条件是
$$ \pi(a|s) = \begin{cases} 1, & a = a^*, \\ 0, & a \neq a^*. \end{cases} $$其中 $a^*=arg\ max_a \ q(s,a)$. 因此最优策略 $\pi(s)$ 应该选择具有最大 $q(s,a)$的动作, 这个小节也和该小节最开始给的例子完全一样. 因此在解决了右侧的优化问题之后, 贝尔曼最优方程就退化成了 $v(s)=max_{a\in \mathcal{A}} \ q(s,a)$.
矩阵-向量形式
状态空间:
$$ \mathcal{S} = \{s_1, s_2, \ldots, s_n\} $$贝尔曼最优方程的标量形式为:
$$ v(s) = \max_{\pi \in \Pi} \left( r_\pi(s) + \gamma \sum_{s' \in \mathcal{S}} p_\pi(s'|s)v(s') \right) $$其中:
$$ r_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a|s)\sum_{r \in \mathcal{R}} p(r|s,a)r $$ $$ p_\pi(s'|s) = \sum_{a \in \mathcal{A}} \pi(a|s)p(s'|s,a) $$对于每个状态 $s_i$, 有:
$$ v(s_i) = \max_{\pi \in \Pi} \left( r_\pi(s_i) + \gamma \sum_{j=1}^{n} p_\pi(s_j|s_i)v(s_j) \right) $$写成矩阵-向量形式:
$$ \begin{bmatrix} v(s_1) \\ v(s_2) \\ \vdots \\ v(s_n) \end{bmatrix} = \max_{\pi \in \Pi} \left( \begin{bmatrix} r_\pi(s_1) \\ r_\pi(s_2) \\ \vdots \\ r_\pi(s_n) \end{bmatrix} + \gamma \begin{bmatrix} p_\pi(s_1|s_1) & p_\pi(s_2|s_1) & \cdots & p_\pi(s_n|s_1) \\ p_\pi(s_1|s_2) & p_\pi(s_2|s_2) & \cdots & p_\pi(s_n|s_2) \\ \vdots & \vdots & \ddots & \vdots \\ p_\pi(s_1|s_n) & p_\pi(s_2|s_n) & \cdots & p_\pi(s_n|s_n) \end{bmatrix} \begin{bmatrix} v(s_1) \\ v(s_2) \\ \vdots \\ v(s_n) \end{bmatrix} \right) $$简写为:
$$ v = \max_{\pi \in \Pi}(r_\pi + \gamma P_\pi v) $$其中:
$$ [v]_i = v(s_i) $$ $$ [r_\pi]_i = r_\pi(s_i) $$ $$ [P_\pi]_{ij} = p_\pi(s_j|s_i) $$这里的 $\max_\pi$ 是逐元素取最大, 在这里即是对多列举证中, 对每行元素中只保留最大的一个. 比如第一行的元素 $p_\pi(s_1|s_1) p_\pi(s_2|s_1) \cdots p_\pi(s_n|s_1)$ 中 $p_\pi(s_1|s_1)$ 最大, 那其他元素都会被剔除只保留第一个元素. 由于 $\pi$ 的最优值由 $v$ 决定, 上式的右侧实际上是关于 $v$ 的函数
$$ f(v) = \max_{\pi \in \Pi}(r_\pi + \gamma P_\pi v) $$然后贝尔曼最优方程可以简介的表达为
$$ v = f(v) $$巴拿赫不动点定理(Banach Fixed-Point Theorem)
巴拿赫不动点定理又称压缩映射定理(Contraction Mapping Theorem), 该定理首先遵循不动点性质
在一个完备空间 $X$ 中, 任意压缩映射 (contraction) $f : X \rightarrow X$ 都存在一个不动点 $x^*$。
即对于任意初始点 $x$, 不断迭代应用映射 $f$:
$$ f(f(f(\cdots f(x)\cdots))) = x^* $$
最终都会收敛到同一个不动点 $x^*$
例: $f(x) = \sqrt{x}$ 是压缩映射函数
可以看出, 不论取值如何在无限次迭代之后都会收敛到不动点 $x^*$ , 在这个例子中不动点就是 $(1,1)$. 其次遵循压缩性质.
如果存在一个 $\gamma\in(0,1)$ ,使得
$$ ||f(x_1)-f(x_2)|| \leq \gamma||x_1-x_2|| $$
例: 已知 $f(x)=\sqrt{x}$ 是压缩映射函数, 且 $x_1=0.2, x_2=0.4$. 那么:
$$ \begin{aligned} ||f(x_1)-f(x_2)|| &\leq \gamma||x_1-x_2|| \\ ||\sqrt{0.2} - \sqrt{0.4}|| &\leq \gamma||0.2-0.4|| \end{aligned} $$很明显左边比右边小, 因为两点 $x_1,x_2$ 的数值在套入函数 $f(x)$ 之后会向不动点 $x^*$ 收敛. 并且呈 $\gamma$ 比例缩放. 总结起来就可以获得最终的巴拿赫不动点定理.
对于方程 $x=f(x)$, 其中 $x$ 和 $f(x)$ 是实数向量. 当满足以下性质时, 那么函数 $f$ 是一个压缩映射:
存在性1: 存在一个不动点 $x^\ast$ . 满足 $f(x^\ast) = x^\ast$ .
存在性2: 存在 $\gamma \in (0, 1)$ 使得 $||f(x_1) - f(x_2)|| \leq \gamma||x_1 - x_2||$
唯一性: 不动点 $x^*$ 是唯一的
算法: 考虑以下迭代算法:
$$ x_{k+1} = f(x_k) $$
其中 $k=0, 1,2, \dots$ . 给定任意一个初始值 $x_0$, 当 $k \rightarrow \infty$ 时, $x_k \rightarrow x^*$. 并且收敛速度是指数性的.
例1: $x=f(x)=0.5x, x \in \mathbb{R}$. $x=0$是不动点, $f(x)=0.5x$ 是一个压缩映射, 因为 $||0.5x_1-0.5x_2||=0.5||x_1-x_2|| \leq \gamma||x_1-x_2||, \gamma \in [0.5, 1)$
贝尔曼最优方程中的压缩映射定理
考虑任意两个向量 $v_1, v_2 \in \mathbb{R}^{|S|}$, 假设
$$ \pi_1^* = \arg\max_{\pi}(r_\pi + \gamma P_\pi v_1) $$和
$$ \pi_2^* = \arg\max_{\pi}(r_\pi + \gamma P_\pi v_2). $$因为 $\pi_1^$ 是 $v_1$ 的最优策略, 因此 $\pi_2^$ 策略应用在 $v_1$ 时的回报至少不会比 $\pi_1^*$ 更优. 反之同理, 那么
$$ f(v_1) = \max_{\pi}(r_\pi + \gamma P_\pi v_1) = r_{\pi_1^*} + \gamma P_{\pi_1^*}v_1 \ge r_{\pi_2^*} + \gamma P_{\pi_2^*}v_1, $$ $$ f(v_2) = \max_{\pi}(r_\pi + \gamma P_\pi v_2) = r_{\pi_2^*} + \gamma P_{\pi_2^*}v_2 \ge r_{\pi_1^*} + \gamma P_{\pi_1^*}v_2. $$其中 "$\ge$" 是逐元素比较。因此,
$$ \begin{aligned} f(v_1) - f(v_2) &= r_{\pi_1^*} + \gamma P_{\pi_1^*}v_1 - \left( r_{\pi_2^*} + \gamma P_{\pi_2^*}v_2 \right) \\ &\le r_{\pi_1^*} + \gamma P_{\pi_1^*}v_1 - \left( r_{\pi_1^*} + \gamma P_{\pi_1^*}v_2 \right) \\ &= \gamma P_{\pi_1^*}(v_1 - v_2). \end{aligned} $$类似地, 可以证明
$$ f(v_2) - f(v_1) \le \gamma P_{\pi_2^*}(v_2 - v_1). $$因此,
$$ \gamma P_{\pi_2^*}(v_1 - v_2) \le f(v_1) - f(v_2) \le \gamma P_{\pi_1^*}(v_1 - v_2). $$定义
$$ z = \max \left\{ \left|\gamma P_{\pi_2^*}(v_1-v_2)\right|, \left|\gamma P_{\pi_1^*}(v_1-v_2)\right| \right\} \in \mathbb{R}^{|S|}, $$其中 $\max(\cdot)$ 和 $|\cdot|$ 也是逐元素操作. 根据定义, $z \ge 0$. 一方面, 由上面两式可以得到
$$ -z \le \gamma P_{\pi_2^*}(v_1-v_2) \le f(v_1)-f(v_2) \le \gamma P_{\pi_1^*}(v_1-v_2) \le z, $$上式其实就是利用绝对值和逐元素取出所有元素中的最大值, 这意味着
$$ |f(v_1)-f(v_2)| \le z. $$进而可以推出
$$ \|f(v_1)-f(v_2)\|_\infty \le \|z\|_\infty. $$另一方面, 假设 $z_i$ 是 $z$ 的第 $i$ 个元素, $p_i^{\mathrm T}$ 和 $q_i^{\mathrm T}$ 分别代表 $P_{\pi_1^}$ 和 $P_{\pi_2^}$ 的第 $i$ 行, 那么有
$$ z_i = \max \left\{ \gamma\left|p_i^{\mathrm T}(v_1-v_2)\right|, \gamma\left|q_i^{\mathrm T}(v_1-v_2)\right| \right\}. $$由于 $p_i$ 中所有元素都大于或等于 0 且所有元素之和等于 1, 而 $p_i^{\mathrm T}(v_1-v_2)$ 其实就是对 $v_1-v_2$ 做加权平均, 加权平均无法超过最大值. 而最大值
$$ \left|p_i^{\mathrm T}(v_1-v_2)\right| \le p_i^{\mathrm T}|v_1-v_2| \le \|v_1-v_2\|_\infty. $$同理可得
$$ \left|q_i^{\mathrm T}(v_1-v_2)\right| \le \|v_1-v_2\|_\infty. $$因此, 我们有
$$ z_i \le \gamma\|v_1-v_2\|_\infty, $$进而可得
$$ \|z\|_\infty = \max_i |z_i| \le \gamma\|v_1-v_2\|_\infty. $$将此不等式代入式 $|f(v_1)-f(v_2)|\infty \le|z|\infty.$可得
$$ \|f(v_1)-f(v_2)\|_\infty \le \gamma\|v_1-v_2\|_\infty. $$至此就完成了对 $f(v)$ 的压缩性质的证明.
从贝尔曼最优方程到最优策略
求解最优状态值: 如果 $v^*$ 是贝尔曼最优方程的解, 那么它满足
$$ v^* = f(v^*) = \max_{\pi \in \Pi}(r_\pi + \gamma P_\pi v^*). $$显然, $v^*$ 是一个不动点. 根据压缩映射定理, 有如下重要结论.
贝尔曼最优方程
$$ v = f(v) = \max_{\pi \in \Pi}(r_\pi + \gamma P_\pi v) $$始终存在唯一解 $v^*$, 该解可以通过如下迭代算法求解:
$$ v_{k+1} = f(v_k) = \max_{\pi \in \Pi}(r_\pi + \gamma P_\pi v_k), \qquad k = 0,1,2,\ldots $$对任意给定的 $v_0$, 当 $k \rightarrow \infty$ 时, $v_k$ 以指数速度收敛至 $v^*$.
再根据压缩定理本身的性质, 我们就能够解答以下问题:
- 存在性: 解是一定存在的, 因为压缩映射函数在多次迭代后就会收敛到不动点.
- 唯一性: 不动点是唯一的, 因而解也是唯一的.
- 算法: 可以通过不断的迭代求出解, 这个也被叫为值迭代.
求解最优策略 $\pi^{}$: 一旦得到了 $v^{}$ 的值, 就可以通过下式求解得到一个最优策略:
$$ \pi^* = \arg\max_{\pi \in \Pi}(r_\pi + \gamma P_\pi v^*). \tag{3.6} $$现在将式上式代入贝尔曼最优方程中可得
$$ v^* = r_{\pi^*} + \gamma P_{\pi^*}v^*. $$因此, $v^{\ast} = v_{\pi^{\ast}}$ 是策略 $\pi^*$ 的状态值. 从上式可以看出, 贝尔曼最优方程是一个特殊的贝尔曼方程, 其对应的策略是 $\pi^{\ast}$. 最优策略实际上是由最优状态值推导出来的. $v^{\ast}$ 是一种价值评价体系, 它评价每个状态本身的价值(从该状态出发所能获得的最大期望回报). 而 $\pi^{\ast}$ 则可以根据这种价值评价体系选择动作, 使得未来进入价值最高的状态, 从而获得最大回报.
证明最优性: 如果 $v^\ast$ 和 $\pi^\ast$ 都是贝尔曼最优方程的解, 那么 $v^\ast$ 是最优状态值, 而 $\pi^\ast$ 是最优策略, 即对于任意其他策略 $\pi$ 都有
$$ v^\ast=v_{\pi^\ast} \geq v_\pi $$其中 $v_\pi$ 是策略 $\pi$ 的状态值. 证明过程:
假设 $\pi$ 是任意一个策略, 其贝尔曼方程为
$$ v_\pi = r_\pi + \gamma P_\pi v_\pi. $$由于
$$ v^* = \max_{\pi}(r_\pi + \gamma P_\pi v^*) = r_{\pi^*} + \gamma P_{\pi^*}v^* \ge r_\pi + \gamma P_\pi v^*, $$因此有
$$ \begin{aligned} v^* - v_\pi &\ge (r_\pi + \gamma P_\pi v^*) - (r_\pi + \gamma P_\pi v_\pi) \\ &= \gamma P_\pi (v^* - v_\pi). \end{aligned} $$反复应用上述不等式可得
$$ v^* - v_\pi \ge \gamma P_\pi (v^* - v_\pi) \ge \gamma^2 P_\pi^2 (v^* - v_\pi) \ge \cdots \ge \gamma^n P_\pi^n (v^* - v_\pi). $$由此可以推出
$$ v^* - v_\pi \ge \lim_{n \to \infty} \gamma^n P_\pi^n (v^* - v_\pi) = 0. $$上式右侧等于 0 是因为 $\gamma < 1$ 且 $P_\pi^n$ 所有元素都大于或等于 0 且小于或等于 1. 最后, 因为 $v^* \ge v_\pi$ 对于任何策略 $\pi$ 都成立, 所以 $\pi^$ 是最优策略且 $v^$ 是最优状态值。
最优策略 $\pi$ 的随机性:
最优策略的矩阵-向量形式是 $\pi^* = \arg\max_{\pi}(r_\pi + \gamma P_\pi v^*)$, 其按元素展开的形式为
$$ \pi^*(s) = \arg\max_{\pi \in \Pi} \sum_{a \in \mathcal{A}} \pi(a|s) \left( \underbrace{ \sum_{r \in \mathcal{R}} p(r|s,a)r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a)v^*(s') }_{q^*(s,a)} \right), \qquad s \in \mathcal{S}. $$为了最大化 $\sum_{a \in \mathcal{A}}\pi(a|s)q^(s,a)$, 策略 $\pi(s)$ 应该选择对应最大 $q^(s,a)$ 的动作, 这是因为
$$ \sum_{a \in \mathcal{A}} \pi(a|s)q^*(s,a) \le \sum_{a \in \mathcal{A}} \pi(a|s)\max_{a \in \mathcal{A}} q^*(s,a) = \max_{a \in \mathcal{A}} q^*(s,a). $$因此我们可以得出策略 $\pi$ 总是存在一个确定性的贪婪策略(Greedy Policy)是最优的. 之所以被称为贪婪策略是因为它总是选择具有最大$q^*(s,a)$ 值的动作. 接着就可以得出以下定理.
假设 $v^*$ 是贝尔曼最优方程的最优状态值解, 那么下面的确定性贪婪策略是一个最优策略:
$$ \pi^*(a|s) = \begin{cases} 1, & a = a^*(s), \\ 0, & a \ne a^*(s), \end{cases} \qquad s \in \mathcal{S}, \tag{3.7} $$其中
$$ a^*(s) = \arg\max_a q^*(a,s), $$且
$$ q^*(s,a) \doteq \sum_{r \in \mathcal{R}}p(r|s,a)r + \gamma \sum_{s' \in \mathcal{S}}p(s'|s,a)v^*(s'). $$最优策略 $\pi^\ast$ 的两个重要属性:
- 最优策略的唯一性: 尽管 $v^\ast$ 的值是唯一的, 但并不代表对应于 $v^\ast$ 的最优策略 $\pi^\ast$ 是唯一的. 因为可能存在两条不完全相同的轨迹但却有同样回报的情况在, 具体看下例
图中两个策略都是最优策略, 因此最优策略可能不是唯一的.
- 最优策略的随机性: 上例同时也证明了最优策略可以是随机的或者是确定的. 但不论如何总是会存在一个确定性的策略.