State Abstraction in RL(Proof)

来自专栏强化学习

介绍

在上篇文章State Abstraction in RL中，介绍了关于状态抽象的一个重要定理。

Theorem 1(Loss bound for a single abstraction). , 以至少的概率有：

$Loss(h, D) leq frac{2}{(1-gamma)^2}(Appr(h) + Estm(h, D, delta))$

$Appr(h) = epsilon_R^h + frac{gamma R_{max} epsilon_T^h}{2(1-gamma)}$

$Etsm(h,D, delta) = frac{R_{max}}{1 - gamma} sqrt{frac{1}{2 n^h(D)} log frac{2 |h(S)||A|}{delta}}$

$n^h(D) = min_{x in h(S), a in A} |D_{x, a}|$

下面给出其证明。

证明是对定理中每一项的具体含义以及相互关系的最好理解方式。

符号约定

在给出具体证明前，需要再给出2个定义，方便证明。

对于给定数据集和抽象，定义运算元 $B_D^h: mathbb{R}^{S imes A} o mathbb{R}^{S imes A}$ 如下：对于任意的值函数 $Q in mathbb{R}^{S imes A}$ ,

$(B_D^h Q)(s,a) = frac{sum_{(r, s) in D_{h(s), a}} (r + gamma V_Q(s))}{|D_{h(s), a}|}$

在这里 $V_Q(s) = max_{a in A} Q(s, a)$ 。接著，我们定义运算元如下:

$(B^hQ)(s,a) = frac{sum_{s: h(s) =h(s)} p(s, a) cdot (BQ)(s, a)}{sum_{s: h(s) =h(s)}p(s, a)}$

在这里，是定义在原始上的贝尔曼最优运算元: ；定义了两个向量的内积。

对于和的理解：1）从概率角度讲，是定义在具体数据集上的；而是对的期望。2）从运算形式讲，两个运算元分别定义了如何把定义在原始的 $Qin mathbb{R} ^{S imes A}$ ，作用到抽象空间的上，得到抽象空间的值函数 $Q^h in mathbb{R}^{h(S) imes A}$ ,最后再把 $Q^h in mathbb{R}^{h(S) imes A}$ 返回到原始。作为一个例子，考虑我们需要衡量原始的与，(由于引入状态抽象而获得的)，的差异。(别忘了抽象空间得到的策略最终是要在原始执行！！！)

理解时，(出于对原始论文的尊重以及一致性)，需要注意到公式中的迭代变数是个选择变数，表示的贡献，不是下一个时刻变数 $s_{t+1}$ ；具体对下个时刻 $s_{t+1}$ 的更新是由完成的。

从定义可以看出，是基于模型，对贝尔曼最优运算元的变形；同理，是对的贝尔曼最优运算元的变形。同时，不难验证 $[Q^*_{M^h_D}]_M, [Q^*_{M^h}]_M$ 分别是的固定点。

引理及证明

Lemma 1. 对于任意贝尔曼最优运算元 (都作用在 $mathbb{R}^{S imes A}$ 上并且具有相同的收缩率 )，分别为他们的固定点，有：

$||Q_1 - Q_2||_{infty} leq frac{||B_1Q_2 - Q_2||_{infty}}{1 - gamma}$

Proof: $egin{align*} ||Q_1 - Q_2||_{infty} &= ||B_1Q_1 - B_1Q_2 + B_1Q_2 - Q_2||_{infty}(对于固定点Q而言，BQ=Q)\ &leq gamma ||Q_1 - Q_2||_{infty} + ||B_1Q_2 - Q_2||_{infty}(贝尔曼最优运算元的收缩性) \ herefore ||Q_1 - Q_2||_{infty} &leq frac{||B_1Q_2 - Q_2||_{infty}}{1 - gamma} end{align*} \$

Lemma 2. 对于任意和确定性的 $Q in R^{S imes A}$ （的界限为 $[0, R_{max}/(1-gamma)]$ ，这里通过的定义——等比数列的无穷级数和很好满足），以至少的概率有，

$||B^h_DQ - B^h_Q||_{infty} leq mathrm{Estm}(h, D, delta)$

Proof:
根据定义 $(B_D^h Q)(s,a) = frac{sum_{(r, s) in D_{h(s), a}} (r + gamma V_Q(s))}{|D_{h(s), a}|}$ ，可以看做 $|D_{h(s), a}|$ 个随机变数的平均值；当 $|D_{h(s),a}|$ 大于0且是确定值时， $(B^hQ)(s,a) = mathbb{E}_D[(B_D^hQ)(s,a)]$ 。根据Hoeffdings Inequality， ,

$mathbb{P}_D{|(B^h_D Q)(s,a) - (B^hQ)(s,a)| geq t} leq 2 exp(- frac{2t^2|D_{x, a}|}{R_{max}^2/(1-gamma)^2})$
如果要使得这个不等式以至少的概率，对于所有成立，根据概率的结合律(union bound law, $Pr( igcup_{i=1}^{n} A_i) leq igcup_{i=1}^{n} P(A_i)$ ）, 只需要以 $delta := frac{delta}{|h(S)||A|}$ 替换上式中的即可(由于和作用的抽象空间的大小为而不是 )。所以，以至少的概率，满足 $t = frac{R_{max}}{1-gamma}sqrt{frac{1}{2n^h(D)}log frac{2|h(S)||A|}{delta}} = mathrm{Estm}(h, D, delta)$

Lemma 3. 定义是原始的贝尔曼最优运算元，对于定义在抽象空间上、任意界限为 $[0, R_{max}/(1-gamma)]$ 的 $Q:mathbb{R}^{h(S) imes A}$ ，有，

$||B[Q]_M - B^h[Q]_M||_{infty} leq mathrm{Appr}(h)$

Proof:
$egin{align*} &|(B[Q]_M)(s,a) - (B^h[Q]_M)(s,a)| \ &=|R(s, a) + gamma langle P(s,a, cdot), [V_Q]_M(cdot) angle -R^h(h(s), a) - gamma langle P^h(h(s), a, cdot), V_Q(cdot)| \ &=|R(s, a) + gamma langle P(s,a, cdot), [V_Q]_M(cdot) -frac{R_max}{2(1-gamma)} angle \ & quad-R^h(h(s), a) - gamma langle P^h(h(s), a, cdot), V_Q(cdot) -frac{R_max}{2(1-gamma)} angle|(常数项与概率的内积为0) \ &= |R(s, a) - R^h(h(s), a)+ gamma langle sum_{s in h^{-1}(cdot)}{P(s,a,s)}, V_Q(cdot) -frac{R_max}{2(1-gamma)} angle \ & qquad - gamma langle P^h(h(s), a, cdot), V_Q(cdot) -frac{R_max}{2(1-gamma)} angle| (注意V_Q是定义在h(S) imes A上，需要对[V_Q]_M转换)\ & leq epsilon_R^h + gamma|langle sum_{s in h^{-1}(cdot)}{P(s,a,s)}, V_Q(cdot) -frac{R_max}{2(1-gamma)} angle - langle P^h(h(s), a, cdot), V_Q(cdot) -frac{R_max}{2(1-gamma)} angle | (三角不等式)\ & leq epsilon_R^h + |langle sum_{s in h^{-1}(cdot)}{P(s,a,s)}-P^h(h(s), a, cdot), V_Q(cdot) - frac{R_{max}}{2(1-gamma)} angle|(注意gamma < 1)\ &leq epsilon_R^h + || sum_{s in h^{-1}(cdot)}{P(s,a,s)}-P^h(h(s), a, cdot)||_{infty} || V_Q(cdot) -frac{R_{max}}{2(1-gamma)}||_{infty} \ & leq epsilon_R^h + epsilon_T^h frac{R_{max}}{2(1-gamma)} = mathrm{Appr}(h). end{align*}$

定理证明

用 $[Q*_{M^h_D}]_M$ 表示抽象空间上的 $Q^*_{M_D^h}$ 转移(lifted)到原始上，也就是说 $[Q^*_{M_D^h}]_M(s) = Q^*_{M^h_D}(h(s))$

$egin{align*} ||V^*_M - V_M^{pi^*_{M^h_D}} || &leq frac{2}{1-gamma} ||Q^*_M - [Q^*_{M^h_D}]_M||_{infty} (mathrm{Singn &Yee}, 1994) \ &leq frac{2}{1-gamma}(||Q^*_M - [Q^*_{M^h}]_M+[Q^*_{M^h}]_M -[Q^*_{M^h_D}]_M||_{infty} ) \ & leq frac{2}{1-gamma}(||Q^*_M - [Q^*_{M^h}]_M||_{infty}+||[Q^*_{M^h}]_M -[Q^*_{M^h_D}]_M||_{infty} ) \ &leq frac{2}{1-gamma}(||Q^*_M - [Q^*_{M^h}]_M||_{infty}+||Q^*_{M^h} -Q^*_{M^h_D}||_{infty} ) (第二项由于B的收缩性) end{align*}$

对于第一项，首先让，应用引理1；然后使用引理3，有：

$egin{align*} ||Q^*_M - [Q^*_{M^h}]_M||_{infty} &leq frac{||B[Q^*_{M^h}]_M - B^h [Q^*_{M^h}]_M||_{infty}}{1-gamma} (mathrm{Lemma ,1})\ & leq frac{mathrm{Appr(h)}}{1- gamma}.(mathrm{Lemma , 3}) end{align*}$

对于第二项，首先让 $B_1 = B^{h}, B_2 =B^h_D$ ，应用引理1；然后使用引理2，有：

$egin{align*} ||Q^*_{M^h} - Q^*_{M_D^h} ||_{infty} & leq frac{||B^h[Q^*_{M^h}]_M - B^h_D[Q^*_{M^h}]_M||_{infty}}{1-gamma} (mathrm{Lemma , 1)} \ & leq frac{mathrm{Estm}(h, D, delta)}{1-gamma} (mathrm{Lemma , 2}) end{align*}$