基于模型的强化学习

强化学习

RL：智能体[与环境交互]{.underline}以学习良好的决策策略。

环境由[马尔可夫决策过程（MDP）]{.underline}建模：

• $H$： episode 的长度，

• $\mathcal{A}$：可能动作的集合，

• ${S_h}_{h=1}^H$：在时间 $h$ 的可能状态集合，

• $r(s,a)$：在状态 $s$ 执行动作 $a$ 的即时奖励（不失一般性，假设 $r(s,a) \in [0,1]$ 为确定性），

• $P(\cdot \mid s,a)$：状态-动作对 $(s,a)$ 的转移概率。

表格情况

$S_h$（对所有 $h$），$\mathcal{A}$ 均为有限集合。令 $S = \max_h |S_h|$，$A = |\mathcal{A}|$。

总共有 $K$ 个 episode。设 $\pi_k: \bigcup_{h=1}^H S_h \to \mathcal{A}$ 为智能体在第 $k$ 个 episode（$k \in [K]$）选择的（不失一般性为确定性）策略。

损失

$R_T \triangleq \mathbb{E} \sum_{k=1}^K \left[ V^\ast(s_1^k) - V^{\pi_k}(s_1^k) \right], \text{ 其中 } T = KH.$

策略评估

$V^\pi(s_h) = \mathbb{E} \left[ r_h(s_h, a_h) + V^\pi(s_{h+1}) \mid s_{h+1} \sim P_h(\cdot \mid s_h, a_h), a_h = \pi(s_h) \right] = Q^\pi(s_h, \pi(s_h)),$ 其中 $Q^\pi(s_h, a_h) = \mathbb{E} \left[ r_h(s_h, a_h) + V^\pi(s_{h+1}) \mid s_{h+1} \sim P_h(\cdot \mid s_h, a_h) \right].$

最优策略

$V^\ast(s_h) = \max_\pi { V^\pi(s_h) } = \max_{a_h} { Q^\ast(s_h, a_h) },$ 其中 $Q^\ast(s_h, a_h) = \max_\pi { Q^\pi(s_h, a_h) } = \mathbb{E} \left[ r_h(s_h, a_h) + V^\ast(s_{h+1}) \mid s_{h+1} \sim P_h(\cdot \mid s_h, a_h) \right].$

最优极小极大损失

上下界均为 $\widetilde{\mathcal{O}}(H \sqrt{SAT})$（忽略 $\mathrm{polylog}(S,A,H,K)$ 因子）。— 我们算法的目标。

MDP 的过度简化视角：堆叠的多臂老虎机

假设我们已知所有 $h$ 的 $V^\ast_h$。给定 $s_h$，智能体需确定 $\arg\max_{a \in \mathcal{A}} \left\{ r_h(s_h, a) + P_{s_h,a,h} V^\ast_{h+1} \right\}$，这可视为一个具有 $A$ 个臂的老虎机问题。

在状态 $s_h$ 上玩老虎机所造成的总损失：$\widetilde{\mathcal{O}}\left( H \cdot \sqrt{A \cdot N_h(s_h)} \right) \quad \text{（其中，} N_h(s_h): \text{ 访问 } s_h \text{ 的总次数）}.$

因此，MDP 的总损失为： $\sum_{h=1}^H \sum_{s_h \in S_h} \widetilde{\mathcal{O}}\left( H \cdot \sqrt{A \cdot N_h(s_h)} \right) \le \widetilde{\mathcal{O}}\left( H \sqrt{A} \cdot \sqrt{HS} \right) \cdot \sqrt{ \sum_{h=1}^H \sum_{s_h \in S_h} N_h(s_h) }
\le \widetilde{\mathcal{O}}\left( H \sqrt{SAH} \cdot \sqrt{T} \right) = \widetilde{\mathcal{O}}\left( H \sqrt{HSAT} \right).$

需要消除 $\sqrt{H}$ 因子。

通过总方差引理进行方差缩减

回顾（作业1）：若臂 $i$ 的方差为 $V_i$，我们可以构建长度约为 $\sqrt{V_i / T_i(t)}$ 的置信区间（忽略低阶项），且损失可（大致）界于 $\sum_i \sqrt{V_i \cdot T_i}$。

MDP 的总方差引理

令 $V(P, V) \triangleq PV^2 - (PV)^2$。以高概率，我们有 $\sum_{k=1}^K \sum_{h=1}^H V(P_{s_h^k, a_h^k, h}, V^\ast_{h+1}) \le \widetilde{\mathcal{O}}(TH + H^2T). \tag{*}$

利用该引理，总损失（假设 ${V^\ast_h}$ 已知，使用方差感知的老虎机算法）可被界为（忽略对数因子） \(\begin{aligned} \sum_{h=1}^H \sum_{s_h \in S_h} \sum_{a \in \mathcal{A}} \sqrt{V(P_{s_h,a,h}, V^\ast_{h+1}) \cdot N_h(s_h,a)} &\le \sqrt{HSA} \cdot \sqrt{ \sum_{h} \sum_{s_h} \sum_{a} V(P_{s_h,a,h}, V^\ast_{h+1}) \cdot N_h(s_h,a) } \\ &\le \sqrt{HSA \cdot \widetilde{\mathcal{O}}(TH + H^2T)} \le \widetilde{\mathcal{O}}(H \sqrt{SAT}) \quad \text{（当 } T \text{ 很大时）}. \end{aligned}\)

总方差引理的证明

(*) 的左侧 = \(\begin{aligned} &\sum_k \sum_h \left[ P_{s_h^k, a_h^k, h} (V^\ast_{h+1})^2 - \left( P_{s_h^k, a_h^k, h} V^\ast_{h+1} \right)^2 \right] \\ &\le \underbrace{ \sum_k \sum_h \left[ P_{s_h^k, a_h^k, h} (V^\ast_{h+1})^2 - V^\ast_{h+1}(s_{h+1}^k)^2 \right] }_{(**)} + \underbrace{ 2H \cdot \sum_k \sum_h \left| V^\ast_{h}(s_h^k) - P_{s_h^k, a_h^k, h} V^\ast_{h+1} \right| }_{(***)}. \end{aligned}\)

其中，

\[\begin{aligned} (**) &\le \sum_k \sum_h \left[ P_{s_h^k, a_h^k, h} (V^\ast_{h+1})^2 - V^\ast_{h+1}(s_{h+1}^k)^2 \right] \quad \text{（省略 } -V^\ast_{h}(s_h^k)^2\text{）} \\ &\le \widetilde{\mathcal{O}}(H^2T), \quad \text{（以高概率，由Azuma不等式）} \\ (***) &= \sum_k \sum_h \left( V^\ast_{h}(s_h^k) - P_{s_h^k, a_h^k, h} V^\ast_{h+1} \right) \\ &= \sum_k \left[ V^\ast_{1}(s_1^k) + \sum_{h=1}^H \left( V^\ast_{h+1}(s_{h+1}^k) - P_{s_h^k, a_h^k, h} V^\ast_{h+1} \right) \right] \\ &\le KH + \widetilde{\mathcal{O}}(H\sqrt{T}) \quad \text{（以高概率，由Azuma不等式）} \end{aligned}\]

综上，以高概率，我们有 $\text{(*)的左侧} \le \widetilde{\mathcal{O}}(H^2T) + 2H(KH + \widetilde{\mathcal{O}}(H\sqrt{T})) \le \widetilde{\mathcal{O}}(HT + H^2T).$

基于模型的RL

对每个 episode $k \gets 1,2,3,\dots,K$ 执行：

1. 基于过往观测计算 $\widetilde{P}^k$（样本平均值）

2. 计算 $V^k_h(s) = \max_a Q^k_h(s,a)$，其中 $Q^k_h(s,a) = \min \left\{ Q^{k-1}_h(s,a), r_h(s,a) + \widetilde{P}^k_{s,a,h} V^k_{h+1} + b^k_h(s,a) \right\},$ 此处 $b^k_h(s,a) = \widetilde{\mathcal{O}}\left( H \cdot n^k_h(s,a)^{-1/2} \right) \quad \text{（探索奖励）}$ $n^k_h(s,a): \text{ 在 episode } k \text{ 之前访问 } (s,a,h) \text{ 的次数}.$

3. $\pi_k \gets$ 相对于 $Q^k$ 的贪婪策略，运行 $\pi_k$ 于第 $k$ 个 episode。

观察

$V^k_h(s)$ 和 $Q^k_h(s,a)$ 随 $k$ 非增。

声明（习题）

以高概率，对所有 $k$，有 $V^k_h \ge V^\ast_h$，$Q^k_h \ge Q^\ast_h$。

损失分析

第 $k$ 个 episode 中造成的损失：$V^\ast_1(s_1^k) - V^{\pi_k}_1(s_1^k) \le V^k_1(s_1^k) - V^{\pi_k}_1(s_1^k).$

对任意 $h$，我们有

\[\begin{aligned} V^k_h(s_h^k) - V^{\pi_k}_h(s_h^k) &= \max_a \{ Q^k_h(s_h^k, a) \} - Q^{\pi_k}_h(s_h^k, a_h^k) \\ &= Q^k_h(s_h^k, a_h^k) - Q^{\pi_k}_h(s_h^k, a_h^k) \\ &\le \widetilde{P}^k_{s_h^k, a_h^k, h} V^k_{h+1} + b^k_h(s_h^k, a_h^k) - P_{s_h^k, a_h^k, h} V^{\pi_k}_{h+1} \\ &\overset{(?)}{\le} P_{s_h^k, a_h^k, h} V^k_{h+1} + 2b^k_h(s_h^k, a_h^k) - P_{s_h^k, a_h^k, h} V^{\pi_k}_{h+1} \\ &= P_{s_h^k, a_h^k, h} (V^k_{h+1} - V^{\pi_k}_{h+1}) + 2b^k_h(s_h^k, a_h^k). \end{aligned}\]

注记

不等式 (?) 可能不成立，因为可能存在 $V^k_{h+1}(s_{h+1}^{l_1}), \; V^k_{h+1}(s_{h+1}^{l_2}), \; \dots, \; V^k_{h+1}(s_{h+1}^{l_m})$ 之间的相关性，其中 $m = n^k_h(s_h^k, a_h^k)$，$l_i$ 是第 $i$ 次访问 $(s_h^k, a_h^k, h)$ 所在的 episode 编号。

假设不等式 (?) 成立，令 $T_h = - \sum_{k=1}^K (V^k_{h+1} - V^{\pi_k}_{h+1})(s_{h+1}^k) + \sum_{k=1}^K P_{s_h^k, a_h^k, h} (V^k_{h+1} - V^{\pi_k}_{h+1})$，我们有 $\sum_{k=1}^K (V^k_h - V^{\pi_k}_h)(s_h^k) \le \sum_{k=1}^K (V^k_{h+1} - V^{\pi_k}_{h+1})(s_{h+1}^k) + T_h + 2 \sum_{k=1}^K b^k_h(s_h^k, a_h^k).$

因此，总损失上界为

\[\sum_{k=1}^K (V^k_1 - V^{\pi_k}_1)(s_1^k) \le \sum_{h=1}^H T_h + 2 \sum_{h=1}^H \sum_{k=1}^K b^k_h(s_h^k, a_h^k)\] \[\begin{aligned} &\le \widetilde{\mathcal{O}}(H\sqrt{T}) + 2 \sum_{h=1}^H \sum_{k=1}^K b^k_h(s_h^k, a_h^k) \quad \text{（以高概率，由Azuma不等式）} \\ &\le \widetilde{\mathcal{O}}(H\sqrt{T}) + \sum_{s,a,h} \sum_{n=1}^{N_h(s,a)} \widetilde{\mathcal{O}}(H/\sqrt{n}) \\ &\le \widetilde{\mathcal{O}}(H\sqrt{T}) + \sum_{s,a,h} \widetilde{\mathcal{O}}(H \sqrt{N_h(s,a)}) \le \widetilde{\mathcal{O}}(H\sqrt{T}) + H \cdot \widetilde{\mathcal{O}}\left( \sqrt{SAH \cdot \sum_{s,a,h} N_h(s,a)} \right) \\ &\le \widetilde{\mathcal{O}}(H\sqrt{T} + H \sqrt{HSAT}) = \widetilde{\mathcal{O}}(H \sqrt{HSAT}). \end{aligned}\]

修正依赖性问题

方法1

以高概率，$\forall s$，有 $\left| P_{s_h^k, a_h^k, h}(s) - \widetilde{P}^k_{s_h^k, a_h^k, h}(s) \right| \le \widetilde{\mathcal{O}}\left( n^k_h(s_h^k, a_h^k)^{-1/2} \right). \quad \text{（Hoeffding-Azuma）}$

因此，$\left| \left( P_{s_h^k, a_h^k, h} - \widetilde{P}^k_{s_h^k, a_h^k, h} \right) V^k_{h+1} \right| \le SH \cdot \widetilde{\mathcal{O}}\left( n^k_h(s_h^k, a_h^k)^{-1/2} \right) \le S \cdot b^k_h(s_h^k, a_h^k).$

损失上界扩大了 $S$ 倍。

方法2

写为 $\widetilde{P}^k_{s_h^k, a_h^k, h} V^k_{h+1} = \widetilde{P}^k_{s_h^k, a_h^k, h} (V^k_{h+1} - V^\ast_{h+1}) + \widetilde{P}^k_{s_h^k, a_h^k, h} V^\ast_{h+1}$。

对第二项，以高概率，有 $\widetilde{P}^k_{s_h^k, a_h^k, h} V^\ast_{h+1} \le P_{s_h^k, a_h^k, h} V^\ast_{h+1} + b^k_h(s_h^k, a_h^k).$

对第一项，我们使用以下声明。

声明

以高概率， \(\begin{aligned} &\left( \widetilde{P}^k_{s_h^k, a_h^k, h} - P_{s_h^k, a_h^k, h} \right) (V^k_{h+1} - V^\ast_{h+1}) \\ &\le \underbrace{ H \mathbf{1}\left[ n^k_h(s_h^k, a_h^k) \le c \cdot S^6 A^2 H^{16} \log T \right] }_{(\#)} + \underbrace{ \widetilde{\mathcal{O}}\left( SH \cdot n^k_h(s_h^k, a_h^k)^{-1} \right) }_{(\#\#)} + b^k_h(s_h^k, a_h^k). \end{aligned}\)

利用上述声明，我们有 $\widetilde{P}^k_{s_h^k, a_h^k, h} V^k_{h+1} \le P_{s_h^k, a_h^k, h} V^k_{h+1} + (\#) + (\#\#) + 2b^k_h(s_h^k, a_h^k).$

在最终损失上界中，我们有两个额外的低阶项：

\[\begin{aligned} \sum_{h,k} (\#) &\le c \cdot S^6 A^2 H^{16} \log T \cdot H \cdot SAH \le \widetilde{\mathcal{O}}(S^7 A^3 H^{18}). \\ \sum_{h,k} (\#\#) &\le SAH \cdot \widetilde{\mathcal{O}}(SH \cdot \log T) \le \widetilde{\mathcal{O}}(S^2 A H^2). \end{aligned}\]

声明的证明思路

引理（习题） 以高概率，对所有 $s,h,k$，有 $V^k_h(s) - V^\ast_h(s) \le \widetilde{\mathcal{O}}(SAH^8 n^k_h(s)^{-1/2}).$

当 $n^k_h(s_h^k, a_h^k) > c \cdot S^6 A^2 H^{16} \log T$ 时，调用此引理：

1. 对所有 $s$：$P_{s_h^k, a_h^k, h}(s) \ge 1/S^2$，我们有（以高概率）$n^k_{h+1}(s) \ge \frac{c}{2} S^4 A^2 H^{16} \log T, \quad \text{（由 Chernoff 不等式）}$ 因此由该引理：$V^k_{h+1}(s) - V^\ast_{h+1}(s) \le 1/S$。

2. 对所有 $s$：$P_{s_h^k, a_h^k, h}(s) < 1/S^2$，我们有（以高概率）$\widetilde{P}^k_{s_h^k, a_h^k, h}(s) \le P_{s_h^k, a_h^k, h}(s) + \widetilde{\mathcal{O}}\left( S^{-1} \cdot n^k_h(s_h^k, a_h^k)^{-1/2} + n^k_h(s_h^k, a_h^k)^{-1} \right). \quad \text{（由 Bernstein 不等式）}$

综合两种情况，我们有

\[\begin{aligned} &\left( \widetilde{P}^k_{s_h^k, a_h^k, h} - P_{s_h^k, a_h^k, h} \right) (V^k_{h+1} - V^\ast_{h+1}) \\ &\le \sum_{s \text{ 在情况1中}} \left| \left( \widetilde{P}^k_{s_h^k, a_h^k, h} - P_{s_h^k, a_h^k, h} \right)(s) \right| \cdot \frac{1}{S} + \sum_{s \text{ 在情况2中}} \widetilde{\mathcal{O}}\left( S^{-1} \cdot n^k_h(s_h^k, a_h^k)^{-1/2} + n^k_h(s_h^k, a_h^k)^{-1} \right) \cdot H \\ &\overset{\text{（以高概率，方法1）}}{\le} S \cdot \widetilde{\mathcal{O}}\left( n^k_h(s_h^k, a_h^k)^{-1/2} \right) \cdot \frac{1}{S} + \widetilde{\mathcal{O}}\left( n^k_h(s_h^k, a_h^k)^{-1/2} / S \right) \cdot H \cdot S + HS \cdot \widetilde{\mathcal{O}}\left( n^k_h(s_h^k, a_h^k)^{-1} \right) \\ &\le b^k_h(s_h^k, a_h^k) + \widetilde{\mathcal{O}}\left( n^k_h(s_h^k, a_h^k)^{-1} \cdot HS \right). \end{aligned}\]

上置信界值迭代（UCBVI，Azar-Osband-Munos’2017）

UCBVI 算法优化了探索奖励 $b^k_h(s,a)$：$H$ 因子被一个基于经验方差 $\widetilde{P}^k_{s,a,h} (V^k_{h+1})^2 - \left( \widetilde{P}^k_{s,a,h} V^k_{h+1} \right)^2$ 和 Bernstein 不等式推导出的方差感知因子所替代。结合总方差引理，可证 UCBVI 的损失为 $\widetilde{\mathcal{O}}(H \sqrt{SAT})$（当 $T$ 较大时）。