Q-Learning

这部分主要参考 [1], [2]

MDP

\(\displaystyle V_{\pi}(s)=\mathbb{E}_{s_t,a_t}[\sum_{t=0}^{\infty}\gamma^tR(s_t,a_t)|s_0=s]\) 表示从当前状态出发的期望收益

\(\displaystyle Q_{\pi}(s,a)=R(s,a)+\mathbb{E}_{s_t,a_t}[\sum_{t=1}^{\infty}\gamma^tR(s_t,a_t)|s_1=s,a_1=a]\) 表示从当前状态采取某动作的期望收益

\(R(s,a)\) 表示状态 \(s\) 采取动作 \(a\) 的收益

\(\gamma\in[0,1)\) 是折扣因子, 为了累计收益不发散到 \(\infty\)

累积的收益 \(G_t=r_t+\gamma r_{t+1}+\gamma^2 r_{t+2}+\cdots\)

表示最关心当前的收益, 其次是未来

Bellman Equations

一般的贝尔曼方程

\[V_{\pi}(s)=\sum_{a\in A}\pi(a|s)Q_{\pi}(s,a)\]

\[Q_{\pi}(s,a)=R(s,a)+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)V_{\pi}(s')\]

迭代形式为

\[V_{\pi}(s)=\sum_{a\in A}\pi(a|s)[R(s,a)+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)V_{\pi}(s')]\tag{1}\]

\[Q_{\pi}(s,a)=R(s,a)+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)\sum_{a'\in A}\pi(a'|s')Q_{\pi}(s',a')\tag{2}\]

贝尔曼最优方程

由

\[\pi^{* }(s)=\argmax_{a\in A}Q^{* }(s,a)\]

得出最优方程:

\[V^{* }(s)=\max_{a\in A}Q^{* }(s,a)\]

\[Q^{* }(s,a)=\mathbb{E}[R(s,a)]+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)V^{* }(s')\]

迭代形式为

\[V^{* }(s)=\max_{a\in A}\set{\mathbb{E}[R(s,a)]+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)V^{* }(s')}\tag{3}\]

贝尔曼最优算子

\[(\Gamma f)(s,a) =R(s,a)+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)\max_{a'\in A}f(s',a' )\]

\[=R(s,a)+\gamma \mathbb{E}_{u\sim \mathbb P[\cdot |s,a]}[\max_{a'\in A}f(u,a')]\tag{4}\]

在确定性环境下:

\[(\Gamma f)(s,a) =R(s,a)+\gamma \max_{a'\in A}f(s',a' )\]

那么 \(Q^{* }\) 为算子的一个不动点

即

\[(\Gamma Q^{* })(s,a) =R(s,a)+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)\max_{a'\in A}Q^{* }(s',a' )\]

\[=R(s,a)+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)V^{* }(s')\]

\[=Q^{* }(s,a)\]

在确定性环境下:

\[(\Gamma Q^{* })(s,a) =R(s,a)+\gamma \max_{a'\in A}Q^{* }(s',a' )=Q^{* }(s,a)\tag{5}\]

线性规划

用线性规划解决贝尔曼方程问题

对于 \((1)\) 式的最大化形式, 可以转换成

\[\forall a\in A, V^{* }(s)\geq \mathbb{E}[R(s,a)]+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)V^{* }(s')\]

这变成了一个线性规划的约束条件

所以我们想找到最优的 \(V^{* }(s)\), 就需要让不等号取等

也就是要最小化 \(\set{V^{* }(s)|s\in S}\) 中的所有元素

所以转化成 LP:

\[\mathrm{minimize}\sum_{s\in S}\alpha(s)V^{* }(s)\]

\[\forall s\in S, a\in A, V^{* }(s)\geq \mathbb{E}[R(s,a)]+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)V^{* }(s')\]

其中 \(\alpha(s)\) 是任意的系数, 满足

\[\alpha(s)>0,\sum_{s\in S}\alpha(s)=1\]

例如取

\[\displaystyle \alpha(s)=\frac{1}{|S|}\]

一些定理

\(\underline{定理1}\)

\[(\forall s\in S, \mathbb{E}_{a\sim \pi'(s)}[Q_{\pi'}(s,a)]\geq \mathbb{E}_{a\sim \pi(s)}[Q_{\pi}(s,a)])\Longrightarrow (\forall s \in S, V_{\pi'}(s)\geq V_{\pi}(s))\]

\(\underline{证明}\)

将 \(V_{\pi}(s)\) 展开, 迭代着写一下就行了

\(\underline{定理2}\)

\(\pi\) 是最优的当且仅当对于 \((s,a)\in S\times A\) 满足

\[a\in \argmax_{a'\in A}Q_{\pi}(s,a')\]

\(\underline{证明}\)

\(\Longleftarrow\)

构造一个 \(\pi'\) 使得 \(\pi'\) 选择 \(\argmax_{a'\in A}Q_{\pi}(s,a')\) 而 \(\pi\) 不选择

这会得出对某个 \(s\) 满足 \(V_{\pi'}(s)>V_{\pi}(s)\)

所以不是最优

\(\Longrightarrow\)

如果 \(\pi'\) 不是最优, 那就有一步 \(s\) 不选择最优的 \(\argmax_{a'\in A}Q_{\pi}(s,a')\)

所以 \(\pi'\) 就不满足右边条件

\(\underline{定理3}\)

有限 MDP 一定存在最优策略 \(\pi^*\)

\(\underline{证明}\)

存在一个 \(\pi^{* }\) 使得他能最大化 \(\sum_{s\in S}V_{\pi^{* }}(s)\)

如果这个 \(\pi^{* }\) 不是最优, 就存在某个状态 \(a\not\in \argmax_{a'\in A}Q_{\pi^{* }}(s,a')\)

那么构造选择 \(\argmax_{a'\in A}Q_{\pi^{* }}(s,a')\) 的策略 \(\pi\), 根据定理1 就会存在 \(V_{\pi}(s)\geq V_{\pi^{* }}(s)\), 那么与 \(\pi^{* }\) 能最大化 \(\sum_{s\in S}V_{\pi^{* }}(s)\) 矛盾

算法

选择策略

使用 \(\epsilon-\text{greedy}\), 以 \(\epsilon\) 的概率尝试新动作, \(1-\epsilon\) 概率使用当前动作价值函数选择动作

更新价值函数

使用 \(new = old + step \times (target - old)\) 的方式来迭代更新 \(Q(s,a)\)

所以在确定性环境中有

\[Q(s,a)\leftarrow Q(s,a)+\alpha(R(s,a)+\gamma \max_{a'\in A}Q(s',a')-Q(s,a))\]

根据 \((3)\) 式, 即

\[Q(s,a)\leftarrow Q(s,a)+\alpha[(\Gamma Q)(s,a)-Q(s,a)]\]

算法流程

alt text

收敛性

假设第 \(n\) 步得到的动作价值函数为 \(Q_n\), 我们要证明

\[\lim_{n\to\infty}Q_n = Q^{* }\]

我们定义

\[\Delta_n=\max_{s,a}|Q_n(s,a)-Q^{* }(s,a)|\]

那么写出 \(Q_{n+1}\) 的表达式

\[Q_{n+1}(s,a)=Q_n(s,a)+\alpha((\Gamma Q_n)(s,a)-Q_n(s,a))\]

\[=\alpha (\Gamma Q_n)(s,a) + (1-\alpha)Q_n(s,a)\]

可以发现 \(Q_{n+1}(s,a)=(\Gamma Q_n)(s,a)\)

同时

\[Q^{* }(s,a)=(1-\alpha)Q^{* }(s,a)+\alpha Q^{* }(s,a)\]

\[=\alpha (\Gamma Q^{* })(s,a)+(1-\alpha)Q^{* }(s,a)\]

所以

\[\Delta_{n+1}=|Q_{n+1}(s,a)-Q^{* }(s,a)|\]

\[=|\alpha[ (\Gamma Q_n)(s,a)- (\Gamma Q^{* })(s,a)]+(1-\alpha)[Q_n(s,a)-Q^{* }(s,a)]|\]

\[\leq \alpha|(\Gamma Q_n)(s,a)- (\Gamma Q^{* })(s,a)|+(1-\alpha)|Q_n(s,a)-Q^{* }(s,a)|\]

同时

\[|Q_n(s,a)-Q^{* }(s,a)|\leq \max_{s',a}|Q_n(s',a)-Q^{* }(s',a)|=\Delta_n\]

\[|(\Gamma Q_n)(s,a)- (\Gamma Q^{* })(s,a)|=|R(s,a)+\gamma \max_{a'\in A}Q_n(s',a' )-R(s,a)-\gamma \max_{a'\in A}Q^{* }(s',a' )|\]

\[\leq \gamma \max_{a'\in A}|Q_n(s',a')-Q^{* }(s',a')|\]

\[\leq \gamma \max_{s''\in S,a'\in A}|Q_n(s'',a')-Q^{* }(s'',a')|=\gamma \Delta_n\]

所以

\[\Delta_{n+1}\leq (\alpha\gamma+1-\alpha)\Delta_n\]

而常数 \(\alpha\gamma+1-\alpha<1\)

所以 \(\Delta_n\) 收敛到 \(0\)

即 \(Q_n\) 收敛到 \(Q^{* }\)

不确定性环境的证明类似

Deep Q-Learning Network

强化学习的策略在 Q-Learning 里是以表格的形式存在

如果数据量变大, 表格也会变大

所以退而使用神经网络拟合这个策略函数

Policy Iteration

与 Q learning 一样是近似值函数方法

(approximate value function method)

包括 policy evaluation 和 policy improvement 两个部分

policy evaluation

可以看到 \(V(s)\) 直接按照一般贝尔曼方程更新:

\[V_{\pi}(s)=\sum_{a\in A}\pi(a|s)[R(s,a)+\gamma \sum_{s'\in S}\mathbb{P}(s'|s,a)V_{\pi}(s')]\]

\[=\sum_{a\in A}\pi(a|s)\sum_{s'\in S} \mathbb{P}(s'|s,a)[R(s,a,s')+\gamma V_{\pi}(s')]\]

由于 \(\pi\) 可以是确定性的策略, 所以 \(\sum_{a\in A}\pi(a|s)\) 这一项直接取 \(1\)

\[V_{\pi}(s)=\sum_{s'\in S} \mathbb{P}(s'|s,a)[R(s,a,s')+\gamma V_{\pi}(s')]\]

其中 \(a=\pi(s)\)

当值函数在每一个状态与上一步的差都小于一个阈值 \(\theta\), 说明收敛, 停止评估过程

policy improvement

按照上面类似的方法更新策略函数:

\[\pi(s)=\argmax_a\sum_{s'\in S} \mathbb{P}(s'|s,a)[R(s,a,s')+\gamma V_{\pi}(s')]\]

最后输出一个确定性策略

Value Iteration

另一个近似值函数方法

在第一个循环里, 不再使用确定性策略 \(\pi(s)\) 在确定 \(a\), 而是直接枚举 \(a\), \(V(s)\) 取最大

最后不再循环, 直接输出更新后的确定性策略 \(\pi(s)\)

Importance Sampling

definition

我们要计算某个目标函数 \(f(x)\) 在某分布 \(p(x)\) 下的期望:

\[\mathbb E_{x\sim p}[f(x)]=\int f(x)p(x)\text dx\]

但是 \(p(x)\) 采样困难

所以可以用另一个易采样分布 \(q(x)\) 来估计原本的期望:

\[\mathbb E_{x\sim p}[f(x)]=\mathbb E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]=\int f(x)\frac{p(x)}{q(x)}\cdot q(x)\text dx\]

其中 \(\displaystyle \frac{p(x)}{q(x)}\) 是重要性权重

注意从 \(p\) 中采样 \(x\) 可能会相当困难, 但是计算 \(p(x)\) 相对简单, 这就是重要性采样的作用

采样得到的样本为

\[s_p=\frac 1n\sum_{i=1,x^{i}\sim p}^nf(x^i)\]

\[s_q=\frac 1n\sum_{i=1,x^{i}\sim q}^n\frac{p(x^{i})f(x^i)}{q(x^i)}\]

满足

\[\mathbb E[s_p]=\mathbb E[s_q]=s\]

\[\text{Var}[s_p]=\text{Var}[f(x)]/n\]

\[\text{Var}[s_q]=\text{Var}[\frac{p(x)f(x)}{q(x)}]/n\]

对于 \(s_q\), 当取 \(q^{* }(x)=\frac{p(x)|f(x)|}{Z}\) 时方差最小

其中 \(Z\) 是标准化常数, 保证 \(q^{* }\) 和为 \(1\)

事实上, 当 \(f(x)\) 不变号, \(\text{Var}[s_{q^{* } }]=0\)

意味着最优的情况下只需要一次采样

当然这个不实际的

不同的 \(q\) 取法可以降低方差

biased importance sampling

不要求 \(q,p\) 的标准化

\[s_{BIS}=\frac{\sum_{i=1}^n\frac{p(x^i)}{q(x^i)} f(x^i)}{\sum_{i=1}^n\frac{p(x^i)}{q(x^i)} }\]

\[\frac{\sum_{i=1}^n\frac{\tilde p(x^i)}{\tilde q(x^i)} f(x^i)}{\sum_{i=1}^n\frac{\tilde p(x^i)}{\tilde q(x^i)} }\]

其中 \(\tilde p, \tilde q\) 是 \(p,q\) 的未标准化版本, \(x^i\) 是从 \(q\) 采样得到

这个采样是有偏的, 即 \(\mathbb E[s_{BIS}]\not= s\)

但是由于

\[\mathbb E_{x\sim q}[\frac{p(x)}{q(x)}]=\int p(x)\frac{p(x)}{q(x)}\text dx=\int p(x)\text dx = 1\]

所以在 \(n\to\infty\) 时分母趋向于 \(1\), \(\lim_{n\to\infty}s_{BIS}=s\)

所以是渐近无偏, 实际有偏

how to choose \(q\)

一般 \(q\) 选择一个简单的分布方便采样

但是如果 \(x\) 维数很高, 那么很可能出现 \(q>>p|f|\) 的情况, 使得采样过小导致无效

同时极小可能会出现 \(q<<p|f|\), 导致某次采样过大

off-policy

需要一个生成数据用的策略: \(\mu(a|s)\)

待优化的目标策略: \(\pi(a|s)\)

可以用重要性采样做 Off-Policy Policy Gradient:

\[\nabla J(\theta)=\mathbb E_{s\sim \mu}[\frac{\pi_\theta(a|s)}{\mu(a|s)}\nabla\log\pi_\theta(a|s)Q_\pi(s,a)]\]

KL divergence

definition

记

\[\int_X P(x)\text dx=\int_X \text dP\]

(注意前面是 \(P\) 是概率密度, 后面 \(P\) 是分布函数)

那么 KL 散度定义为

\[D_{KL}=-\int_X\log_2(P(x)/Q(x))\text dP\]

即 \(-\log_2(P/Q)\) 的 \(P-\text{expectation}\)

同时定义\(Q\) 对 \(P\) 的交叉熵

\[H(P,Q)=-\int_X\log_2(Q(x))\text dP\]

KL 散度实际上是 \(P\) 的自熵与 \(P,Q\) 的交叉熵的差:

\[D_{KL}=H(P,P)-H(P,Q)=-[\int_X\log_2(P(x))\text dP-\int_X\log_2(Q(x))\text dP]\]

可以看出它实际表示分布 \(Q\) 与 \(P\) 的编码信息的期望差异程度 (相似度)

property of KL divergence

非负性:

\(D_{KL}\geq 0\), 当且仅当 \(P=Q\) 时取等
凸性
链式法则:

给出联合分布 \(P(x,y),Q(x,y)\)

对于条件概率的 KL 散度的期望是

\[\mathbb E_{x\sim P_X}[D_{KL}(P(y|x),Q(y|x))]=\int_XD_{KL}(P(y|x),Q(y|x))\text dP_X\]

其中 \(P_X\) 是 \(P(x,y)\) 的 \(x\) 边际分布

那么有

\[D_{KL}(P(x,y),Q(x,y))=D_{KL}(P_X,Q_X)+\mathbb E_{x\sim P_X}[D_{KL}(P(y|x),Q(y|x))]\]

\(\underline{证明:}\)

\[\because P(x,y)=P_X(x)P(y|x)\]

\[Q(x,y)=Q_X(x)Q(y|x)\]

\[\therefore D_{KL}(P(x,y),Q(x,y))=-\int_{X,Y}P(x, y)\log_2(P(x,y)/Q(x,y))\text dx\text dy\]

\[=-[\int_{X,Y}P_X(x)P(y|x)\log_2(P_X(x)/Q_X(x))\text dx\text dy + \int_{X,Y}P_X(x)P(y|x)\log_2(P(y|x)/Q(y|x))\text dx\text dy]\]

\[=-[\int_{X}P_X(x)\log_2(P_X(x)/Q_X(x))\set{\int_YP(y|x)\text dy}\text dx + \int_{X}P_X(x)\set{\int_YP(y|x)\log_2(P(y|x)/Q(y|x))\text dy}\text dx]\]

由于 \(\displaystyle \int_Y P(y|x)\text dy=1\), 所以

\[=-[\int_{X}P_X(x)\log_2(P_X(x)/Q_X(x))\text dx + \int_{X}P_X(x)D_{KL}(P(y|x),Q(y|x))\text dx]\]

\[=D_{KL}(P_X,Q_X)+\mathbb E_{x\sim P_X}[D_{KL}(P(y|x),Q(y|x))]\]
独立性

由 \(3\) 可以得到当 \(X,Y\) 独立时

\[D_{KL}(P(x,y),Q(x,y))=D_{KL}(P_X,Q_X)+D_{KL}(P_Y,Q_Y)\]

这正好体现了独立的信息是可加的

It is not a metric

KL 散度不是一般意义上的度量 (距离), 因为不满足对称性和三角不等式

即使构造出 \(D_{KL}^{* }(P,Q)=\frac 12(D_{KL}(P,Q)+D_{KL}(Q,P))\) 满足对称性, 也无法满足三角不等式

connections with statistical concepts

mutual information

对于联合分布 \(P(x,y)\), 定义互信息为

\[I_P(X,Y)=-\int_{X,Y}\log_2(P(x,y)/[P_X(x)\cdot P_Y(y)])\text dP\]

令 \(P_\perp(x,y)=P_X(x)\cdot P_Y(y)\) 为 \(P\) 的分解 (factorization), 即分解成两个分量

那么 \(I_P(X,Y)=H(P, P_\perp)\)

这样看, 互信息表示了联合分布与其分量的差异程度

maximum likelihood estimation

最大似然估计里我们希望最大化 \(L(\theta|x)=P(x|\theta)\)

假设采样足够多数据得到的实际的频率分布为 \(f\)

期望对数似然希望最大化 \(\mathbb E_f[\log_2(P(x|\theta))]\), 即

\[\theta^{* }=\argmax_\theta \mathbb E_f[\log_2(P(x|\theta))]\]

这正是使 \(f(x)\) 与 \(P(x|\theta)\) 的 KL 散度最小化的 \(\theta\), 因为:

\[\argmin_\theta D_{KL}(f,P(.|\theta))\]

\[=\argmin_\theta \int_Xf(x)\cdot \log_2(P(x|\theta)/f(x))\text dx\]

\[=\argmin_\theta -H(f,f)+H(f,P(.|\theta))\]

\[=\argmin_\theta H(f,P(.|\theta))\]

\[=\argmax_\theta \int_X f(x)\log_2(P(x|\theta))\text dx\]

\[=\argmax_\theta \mathbb E_f[\log_2(P(x|\theta))]\]

期望对数似然有什么意义?

Policy Gradient Methods for Reinforcement Learning with Function Approximation

见博客

Approximately Optimal Approximate Reinforcement Learning

见博客

TRPO

Trust Region Policy Optimization

DPO

Direct Preference Optimization

PPO

Proximal Policy Optimization

GRPO

Group Relative Policy Optimization

参考: