论文原文：
https://arxiv.org/abs/2006.04779
参考：
CQL证明解析
概统 集中不等式介绍（一）
概统 集中不等式介绍（二）
迭代公式1和定理1
CQL的第一个迭代公式如下：
Q ^ k + 1 ← a r g min Q α E s ∼ D , a ∼ μ ( a ∣ s ) [ Q ( s , a ) ] + 1 2 E s , a ∼ D [ ( Q ( s , a ) − B ^ π Q ^ k ( s , a ) ) 2 ] \hat{Q}^{k+1} \gets arg \min_{Q} \alpha \mathbb{E}_{s\sim \mathcal{D},a\sim\mu(a|s)}[Q(s,a)]+\frac{1}{2}\mathbb{E}_{s,a\sim\mathcal{D}}\left[ \left(Q(s,a)-\hat{\mathcal{B}}^{\pi}\hat{Q}^k(s,a) \right)^2\right] Q^k+1←argQminαEs∼D,a∼μ(a∣s)[Q(s,a)]+21Es,a∼D[(Q(s,a)−B^πQ^k(s,a))2]
其中 B \mathcal{B} B就是贝尔曼迭代算子，就是常见的那个贝尔曼迭代公式， D \mathcal{D} D就是数据集， ^ \hat{} ^ 表示估计（由数据集估计）， π \pi π表示当前在训练的策略， μ \mu μ的 s s s分布和数据集的策略 π β \pi_{\beta} πβ一致，也就是说 μ ( s , a ) = d π β ( s ) μ ( a ∣ s ) \mu(s,a)=d^{\pi_\beta(s)}\mu(a|s) μ(s,a)=dπβ(s)μ(a∣s)。
相比于传统的Q-Learning的目标函数，该公式多了一项左边的：最小化Q函数在一个特定策略（不同于采样策略）下的值，这样可以让 Q Q Q的估计更保守， Q ^ π \hat{Q}^\pi Q^π是 Q π Q^\pi Qπ的逐点下界。
第一个定理如下：
对任意 μ \mu μ with s u p p μ ⊂ s u p p π ^ β supp\mu\subset supp\hat{\pi}_\beta suppμ⊂suppπ^β，有 ≥ 1 − δ \ge 1-\delta ≥1−δ概率:
∀ s ∈ D , a , Q ^ π ( s , a ) ≤ Q π ( s , a ) − α [ ( I − γ P π ) − 1 μ π ^ β ] ( s , a ) + [ ( I − γ P π ) − 1 C r , T , δ ( 1 − γ ) ∣ D ∣ ] ( s , a ) \forall s \in \mathcal{D},a,\ \hat{Q}^{\pi}(s,a)\le Q^{\pi}(s,a) - \alpha\left[ (I-\gamma P^\pi)^{-1}\frac{\mu}{\hat{\pi}_\beta}\right](s,a)+\left[ (I-\gamma P^\pi)^{-1}\frac{C_{r,T,\delta}}{(1-\gamma)\sqrt{|\mathcal{D}|}}\right](s,a) ∀s∈D,a, Q^π(s,a)≤Qπ(s,a)−α[(I−γPπ)−1π^βμ](s,a)+[(I−γPπ)−1(1−γ)∣D∣ Cr,T,δ](s,a)
其中 P P P表示状态转移矩阵， B π Q = r + γ P π Q , P π Q ( s , a ) = E s ′ ∼ T ( s ′ ∣ s , a ) , a ′ ∼ π ( a ′ ∣ s ′ ) [ Q ( s ′ , a ′ ) ] \mathcal{B}^\pi Q=r+\gamma P^\pi Q, P^\pi Q(s,a)=\mathbb{E}_{s'\sim T(s'|s,a),a'\sim\pi(a'|s')}[Q(s',a')] BπQ=r+γPπQ,PπQ(s,a)=Es′∼T(s′∣s,a),a′∼π(a′∣s′)[Q(s′,a′)]
此外，作者表明 α \alpha α大于某个阈值，就可以克服采样误差和函数逼近误差，虽然有些时候取决于 Q Q Q但是可以通过Q的上界来得到最差情况的 α \alpha α——在Q-Learning里， Q Q Q的上下界如下：
[ − 2 R m a x 1 − γ , 2 R m a x 1 − γ ] \left[ \frac{-2R_{max}}{1-\gamma}, \frac{2R_{max}}{1-\gamma}\right] [1−γ−2Rmax,1−γ2Rmax]
对于这个上下界，我只会简单的归纳证明（只证明上界）：
首先对于初值， Q ≤ R m a x < 2 R m a x 1 − γ Q\le R_{max}<\frac{2R_{max}}{1-\gamma} Q≤Rmax<1−γ2Rmax
然后，对于每一次迭代，假设 Q k ≤ 2 R m a x 1 − γ Q^{k}\le \frac{2R_{max}}{1-\gamma} Qk≤1−γ2Rmax，则 Q k + 1 ( s , a ) = r + γ m a x [ Q k ( s ′ , a ′ ) ] ≤ R m a x + γ ∗ 2 R m a x 1 − γ = 1 + γ 1 − γ R m a x < 2 1 − γ R m a x Q^{k+1}(s,a)=r + \gamma max[Q^{k}(s',a')] \le R_{max}+\gamma*\frac{2R_{max}}{1-\gamma}=\frac{1+\gamma}{1-\gamma}R_{max}<\frac{2}{1-\gamma}R_{max} Qk+1(s,a)=r+γmax[Qk(s′,a′)]≤Rmax+γ∗1−γ2Rmax=1−γ1+γRmax<1−γ2Rmax
此外，随着数据集的增大，仅仅需要一个很小的 α \alpha α来满足保守性
证明
接下来证明上面公式的保守性，为了方便求导，左边这项要转化一下：
E s ∼ D , a ∼ μ ( a ∣ s ) [ Q ( s , a ) ] = E s ∼ D [ ∫ a μ ( a ∣ s ) Q ( s , a ) ] = E s ∼ D [ ∫ a π ^ β ( a ∣ s ) μ ( a ∣ s ) π ^ β ( a ∣ s ) Q ( s , a ) ] = E s , a ∼ D [ μ ( a ∣ s ) π ^ β ( a ∣ s ) Q ( s , a ) ] \mathbb{E}_{s\sim \mathcal{D},a\sim \mu (a|s)}[Q(s,a)] = \mathbb{E}_{s\sim \mathcal{D}}[\int_a\mu(a|s) Q(s,a)] =\mathbb{E}_{s\sim \mathcal{D}}[\int_a\hat{\pi}_{\beta}(a|s)\frac{\mu(a|s)}{\hat{\pi}_{\beta}(a|s)} Q(s,a)] =\mathbb{E}_{s,a\sim \mathcal{D}}[\frac{\mu(a|s)}{\hat{\pi}_{\beta}(a|s)} Q(s,a)] Es∼D,a∼μ(a∣s)[Q(s,a)]=Es∼D[∫aμ(a∣s)Q(s,a)]=Es∼D[∫aπ^β(a∣s)π^β(a∣s)μ(a∣s)Q(s,a)]=Es,a∼D[π^β(a∣s)μ(a∣s)Q(s,a)]
于是令一阶导为零得到：
∀ s , a ∈ D , k , Q ^ k + 1 ( s , a ) = B ^ π Q ^ k ( s , a ) − α μ ( a ∣ s ) π ^ β ( a ∣ s ) \forall s,a \in \mathcal{D},k,\ \hat{Q}^{k+1}(s,a)=\hat{\mathcal{B}}^{\pi}\hat{Q}^k(s,a) - \alpha\frac{\mu(a|s)}{\hat{\pi}_{\beta}(a|s)} ∀s,a∈D,k, Q^k+1(s,a)=B^πQ^k(s,a)−απ^β(a∣s)μ(a∣s)
于是得到：
Q ^ k + 1 ≤ B ^ π Q ^ k ( s , a ) \hat{Q}^{k+1}\le\hat{\mathcal{B}}^{\pi}\hat{Q}^k(s,a) Q^k+1≤B^πQ^k(s,a)
我们最后要的是估计的 Q ^ \hat{Q} Q^和真实的 Q Q Q的关系，需要进一步推导，这是因为实际过程中，我们往往有各种误差，比如采样误差、函数逼近误差，我们往往需要更进一步估计上下界，用概统的方法得到大概率下的结果，之后需要得到基于采样（经验）估计的 Q , B Q,\mathcal{B} Q,B(带 ^ \hat{} ^ 的)和实际之间的大概率误差上界。这往往要用到集中不等式。这些不等式可以告诉你数据分布在某范围的上界或者下界，常见的有马尔科夫不等式、切比雪夫不等式等。这边摘几个公式感受一下，具体的可以看参考链接的证明。
马尔科夫不等式（Markov’s inequality）
若 X X X是一个非负随机变量，且 a > 0 a>0 a>0，那么
P ( X ≥ a ) ≤ E [ X ] a \mathbb{P}(X\ge a)\le \frac{\mathbb{E}[X]}{a} P(X≥a)≤aE[X]
切比雪夫不等式（Chebyshev’s inequality）
若 X X X是一个随机变量，其方差为 σ 2 ∈ ( 0 , ∞ ) \sigma^2\in (0, \infty) σ2∈(0,∞)，那么
P ( ∣ X − E [ X ] ∣ > t σ ) ≤ 1 t 2 \mathbb{P}(|X-\mathbb{E}[X]|>t\sigma) \le \frac{1}{t^2} P(∣X−E[X]∣>tσ)≤t21
坎泰利不等式（Cantelli’s inequality）
若 X X X是一个随机变量，其方差为 σ 2 ∈ ( 0 , ∞ ) \sigma^2\in(0,\infty) σ2∈(0,∞)，那么对于 λ > 0 \lambda>0 λ>0
P ( X − E [ X ] ≥ λ ) ≤ σ 2 σ 2 + λ 2 \mathbb{P}(X-\mathbb{E}[X]\ge\lambda)\le\frac{\sigma^2}{\sigma^2+\lambda^2} P(X−E[X]≥λ)≤σ2+λ2σ2
佩利-齐格蒙德不等式（Paley-Zygmund inequality）
若 X X X是一个非负随机变量，且 t ∈ [ 0 , 1 ] t\in[0,1] t∈[0,1]，那么
( X > t E [ X ] ) ≥ ( 1 − t ) 2 E [ X ] 2 E [ X 2 ] \mathbb(X>t\mathbb{E}[X])\ge(1-t)^2\frac{\mathbb{E}[X]^2}{\mathbb{E}[X^2]} (X>tE[X])≥(1−t)2E[X2]E[X]2
霍夫丁不等式（Hoeffding’s inequality）
对于有界独立随机变量之和 S S S，若随机变量 X i X_i Xi在区间 [ a i , b i ] [a_i,b_i] [ai,bi]上取值，那么
P ( ∣ S n − E [ S n ] ∣ ≥ ϵ ) ≤ 2 exp ( − 2 ϵ 2 ∑ i = 1 n ( b i − a i ) 2 ) \mathbb{P}(|S_n-\mathbb{E}[S_n]|\ge\epsilon)\le2\exp({-\frac{2\epsilon^2}{\sum_{i=1}^{n}(b_i-a_i)^2}}) P(∣Sn−E[Sn]∣≥ϵ)≤2exp(−∑i=1n(bi−ai)22ϵ2)
伯恩斯坦不等式（Bernstein’s inequality）
令 X 1 , ⋯ , X n X_1,\cdots,X_n X1,⋯,Xn为独立随机变量，使得对于任意 i ∈ { 1 , ⋯ , n } i\in\{1,\cdots,n\} i∈{1,⋯,n}， E [ X i ] = 0 \mathbb{E}[X_i]=0 E[Xi]=0，且 ∣ X i ∣ ≤ c |X_i|\le c ∣Xi∣≤c，令 σ 2 = 1 n ∑ i = 1 n V a r ( X i ) \sigma^2=\frac{1}{n}\sum_{i=1}^{n}Var(X_i) σ2=n1∑i=1nVar(Xi)，则
P ( 1 n ∑ i = 1 n X i ≥ ϵ ) ≤ exp ( − n ϵ 2 2 σ 2 + 2 c ϵ / 3 ) \mathbb{P}(\frac{1}{n}\sum_{i=1}^{n}X_i\ge\epsilon)\le \exp(-\frac{n\epsilon^2}{2\sigma^2+2c\epsilon/3}) P(n1i=1∑nXi≥ϵ)≤exp(−2σ2+2cϵ/3nϵ2)
下面继续证明
首先假设如下with high probability(w.h.p.) ≥ 1 − δ , δ ∈ ( 0 , 1 ) \ge1-\delta,\delta\in(0,1) ≥1−δ,δ∈(0,1):
∣ r − r ( s , a ) ∣ ≤ C r , δ ∣ D ( s , a ) ∣ , ∣ ∣ T ^ ( s ′ ∣ s , a ) − T ( s ′ ∣ s , a ) ∣ ∣ 1 ≤ C r , δ ∣ D ( s , a ) ∣ |r-r(s,a)|\le\frac{C_{r,\delta}}{\sqrt{|\mathcal{D}(s,a)|}},||\hat{T}(s'|s,a)-T(s'|s,a)||_1\le\frac{C_{r,\delta}}{\sqrt{|\mathcal{D}(s,a)|}} ∣r−r(s,a)∣≤∣D(s,a)∣ Cr,δ,∣∣T^(s′∣s,a)−T(s′∣s,a)∣∣1≤∣D(s,a)∣ Cr,δ
其中 ∣ D ∣ |\mathcal{D}| ∣D∣是数据集里面状态-动作对的个数，这样的假设是来自论文Near-optimal Regret Bounds for Reinforcement Learning，这样假设保证了数据的集中性。但是为什么这样假设？我认为是通过集中不等式反推的，但是我不知道怎么推的
然后得到
∣ ( B ^ π Q ^ k ) − ( B π Q ^ k ) ∣ = ∣ ( r − r ( s , a ) ) + γ ∑ s ′ ( T ^ ( s ′ ∣ s , a ) − T ( s ′ ∣ s , a ) E π ( a ′ ∣ s ′ ) [ Q ^ k ( s ′ , a ′ ) ] ) ∣ ≤ ∣ ( r − r ( s , a ) ) ∣ + ∣ γ ∑ s ′ ( T ^ ( s ′ ∣ s , a ) − T ( s ′ ∣ s , a ) E π ( a ′ ∣ s ′ ) [ Q ^ k ( s ′ , a ′ ) ] ) ∣ ≤ C r , δ ∣ D ∣ + 2 γ C T , δ R max ( 1 − γ ) ∣ D ∣ \left| \left(\hat{\mathcal{B}}^\pi \hat{Q}^k\right)-\left(\mathcal{B}^\pi \hat{Q}^k\right)\right| = \left| (r-r(s,a))+\gamma\sum_{s'}\left(\hat{T}(s'|s,a)-T(s'|s,a)\mathbb{E}_{\pi(a'|s')}\left[\hat{Q}^k(s',a')\right]\right)\right|\\ \le \left| (r-r(s,a))\right|+\left| \gamma\sum_{s'}\left(\hat{T}(s'|s,a)-T(s'|s,a)\mathbb{E}_{\pi(a'|s')}\left[\hat{Q}^k(s',a')\right]\right)\right| \\ \le \frac{C_{r,\delta}}{\sqrt{|\mathcal{D}|}}+\frac{2\gamma C_{T,\delta}R_{\max}}{(1-\gamma)\sqrt{|\mathcal{D}|}} (B^πQ^k)−(BπQ^k) = (r−r(s,a))+γs′∑(T^(s′∣s,a)−T(s′∣s,a)Eπ(a′∣s′)[Q^k(s′,a′)]) ≤∣(r−r(s,a))∣+ γs′∑(T^(s′∣s,a)−T(s′∣s,a)Eπ(a′∣s′)[Q^k(s′,a′)]) ≤∣D∣ Cr,δ+(1−γ)∣D∣ 2γCT,δRmax
随后可以得到w.h.p.
∀ Q , s , a ∈ D , ∣ B ^ π Q ( s , a ) − B π Q ( s , a ) ∣ ≤ C r , T , δ R max ( 1 − γ ) ∣ D ∣ \forall Q,s,a\in\mathcal{D},\left| \hat{\mathcal{B}}^\pi Q(s,a)-\mathcal{B}^\pi Q(s,a)\right|\le\frac{C_{r,T,\delta}R_{\max}}{(1-\gamma)\sqrt{|\mathcal{D}|}} ∀Q,s,a∈D, B^πQ(s,a)−BπQ(s,a) ≤(1−γ)∣D∣ Cr,T,δRmax
因为是任意的 Q Q Q，所以
Q ^ k + 1 ( s , a ) = B ^ π Q ^ k ( s , a ) − α μ ( a ∣ s ) π ^ β ( a ∣ s ) ≤ B π Q ^ k ( s , a ) − α μ ( a ∣ s ) π ^ β ( a ∣ s ) + C r , T , δ R max ( 1 − γ ) ∣ D ∣ \hat{Q}^{k+1}(s,a)=\hat{\mathcal{B}}^{\pi}\hat{Q}^k(s,a) - \alpha\frac{\mu(a|s)}{\hat{\pi}_{\beta}(a|s)}\le\mathcal{B}^{\pi}\hat{Q}^k(s,a) - \alpha\frac{\mu(a|s)}{\hat{\pi}_{\beta}(a|s)} + \frac{C_{r,T,\delta}R_{\max}}{(1-\gamma)\sqrt{|\mathcal{D}|}}\\ Q^k+1(s,a)=B^πQ^k(s,a)−απ^β(a∣s)μ(a∣s)≤BπQ^k(s,a)−απ^β(a∣s)μ(a∣s)+(1−γ)∣D∣ Cr,T,δRmax
后面求不动点可以得到前面的结果（可以求不动点是因为贝尔曼公式是压缩映射，这里不讨论）
Q ^ π ( s , a ) ≤ ( I − γ P π ) − 1 [ R − α μ π ^ β + C r , T , δ R max ( 1 − γ ) ∣ D ∣ ] ≤ Q π ( s , a ) − α [ ( I − γ P π ) − 1 μ π ^ β ] ( s , a ) + [ ( I − γ P π ) − 1 C r , T , δ ( 1 − γ ) ∣ D ∣ ] ( s , a ) \hat{Q}^{\pi}(s,a)\le(I-\gamma P^\pi)^{-1}\left[ R-\alpha\frac{\mu}{\hat{\pi}_\beta}+ \frac{C_{r,T,\delta}R_{\max}}{(1-\gamma)\sqrt{|\mathcal{D}|}} \right] \\\le Q^{\pi}(s,a) - \alpha\left[ (I-\gamma P^\pi)^{-1}\frac{\mu}{\hat{\pi}_\beta}\right](s,a)+\left[ (I-\gamma P^\pi)^{-1}\frac{C_{r,T,\delta}}{(1-\gamma)\sqrt{|\mathcal{D}|}} \right](s,a) Q^π(s,a)≤(I−γPπ)−1[R−απ^βμ+(1−γ)∣D∣ Cr,T,δRmax]≤Qπ(s,a)−α[(I−γPπ)−1π^βμ](s,a)+[(I−γPπ)−1(1−γ)∣D∣ Cr,T,δ](s,a)
其中 α \alpha α会随着数据集的增大而减小，此外，当 B ^ π = B π , C r , T , δ R max ( 1 − γ ) ∣ D ∣ ≈ 0 \hat{\mathcal{B}}^\pi=\mathcal{B}^\pi,\frac{C_{r,T,\delta}R_{\max}}{(1-\gamma)\sqrt{|\mathcal{D}|}} \approx0 B^π=Bπ,(1−γ)∣D∣ Cr,T,δRmax≈0，此时 α \alpha α只用 ≥ 0 \ge0 ≥0
迭代公式2和定理2
公式1可以得到 Q π Q^\pi Qπ的逐点下界，如果只关注于 V π V^\pi Vπ，我们可以添加一项新的，目的是最大化 V π V^\pi Vπ，这样可以得到更紧的下界。
Q ^ k + 1 ← a r g min Q α ( E s ∼ D , a ∼ μ ( a ∣ s ) [ Q ( s , a ) ] − E s ∼ D , a ∼ π β ^ ( a ∣ s ) [ Q ( s , a ) ] ) + 1 2 E s , a ∼ D [ ( Q ( s , a ) − B ^ π Q ^ k ( s , a ) ) 2 ] \hat{Q}^{k+1} \gets arg \min_{Q} \alpha( \mathbb{E}_{s\sim \mathcal{D},a\sim\mu(a|s)}[Q(s,a)]-\mathbb{E}_{s\sim \mathcal{D},a\sim\hat{\pi_{\beta}}(a|s)}[Q(s,a)])+\frac{1}{2}\mathbb{E}_{s,a\sim\mathcal{D}}\left[ \left(Q(s,a)-\hat{\mathcal{B}}^{\pi}\hat{Q}^k(s,a) \right)^2\right] Q^k+1←argQminα(Es∼D,a∼μ(a∣s)[Q(s,a)]−Es∼D,a∼πβ^(a∣s)[Q(s,a)])+21Es,a∼D[(Q(s,a)−B^πQ^k(s,a))2]
这个公式里我们不能得到逐点下界，但是能得到当 μ ( a ∣ s ) = π ( a ∣ s ) \mu(a|s)=\pi(a|s) μ(a∣s)=π(a∣s)， E π ( a ∣ s ) [ Q π ^ ( s , a ) ] ≤ V π ( s ) \mathbb{E}_{\pi(a|s)}[\hat{Q^\pi}(s,a)]\le V^{\pi}(s) Eπ(a∣s)[Qπ^(s,a)]≤Vπ(s)，而且得在最大化项（新加的这项）为 a ∼ π ^ β a\sim \hat{\pi}_\beta a∼π^β才能得到这个结论
定理2如下：
∀ s ∈ D , V ^ π ( s ) − α [ ( I − γ P π ) − 1 E π [ π π ^ β − 1 ] ] ( s ) + [ ( I − γ P π ) − 1 C r , T , δ R max ( 1 − γ ) ∣ D ∣ ] ( s ) \forall s\in\mathcal{D},\hat{V}^\pi(s)-\alpha\left[ (I-\gamma P^\pi)^{-1}\mathbb{E}_\pi\left[ \frac{\pi}{\hat{\pi}_\beta}-1\right]\right](s)+\left[ (I-\gamma P^\pi)^{-1} \frac{C_{r,T,\delta}R_{\max}}{(1-\gamma)\sqrt{|\mathcal{D}|}}\right](s) ∀s∈D,V^π(s)−α[(I−γPπ)−1Eπ[π^βπ−1]](s)+[(I−γPπ)−1(1−γ)∣D∣ Cr,T,δRmax](s)
证明的解析因为太忙了暂时鸽了