admin管理员组文章数量:1658762
论文原文:
https://arxiv/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∣
其中 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)∣
其中
∣
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}|}}
随后可以得到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,
因为是任意的
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∣
后面求不动点可以得到前面的结果(可以求不动点是因为贝尔曼公式是压缩映射,这里不讨论)
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∣
其中
α
\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∣
迭代公式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∣
证明的解析因为太忙了暂时鸽了
本文标签: ConservativeLearningcql
版权声明:本文标题:Conservative Q-Learning(CQL)证明解析 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1729812917a1213542.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论