Contextual Bandits and Imitation Learning via Preference-Based Active Queries

Contributions

2. Related Work

3. Preliminaries

我们主要考虑两种设定：上下文老虎机/Contextual Bandits 设定和模仿学习/Imitation Learning 设定。

3.1 Contextual Bandits Setting

Contextual Dueling Bandit 下，我们假设有一个 Context Set $\mathcal{X}$ 和一个动作空间 $\mathcal{A}=[A]$。在每一轮 $t\in [T]$ 中，环境会对抗性的/Adversarially 选择一个上下文 $x_t$，学习者的任务是决定是否向专家发起查询。如果决定查询，就选择一个动作对 $(a_t,b_t)\in \mathcal{A}\times \mathcal{A}$，随后会收到一个 带噪声的反馈 $y_t\in \{-1,1\}$，指示 $a_t$ 和 $b_t$ 哪个更好。

形式化来讲，我们假设专家依赖于一个偏好函数/Preference Function $f^{\star }:\mathcal{X}\times \mathcal{A}\times \mathcal{A}\to [-1,1]$。基于这个偏好函数，其带噪声的反馈 $y_t$ 按照下述方式进行采样：

$$\text{Pr}(a_t\succ b_t\mid x_t)=\text{Pr}(y_t=1\mid x_t,a_t,b_t)=\varphi (f^{\star }(x_t,a_t,b_t))$$

其中 $\varphi :[-1,1]\to [0,1]$ 是链接函数/Link Function，其满足 $\varphi (-d)+\varphi (d)=1$。如果学习者不进行查询，它仍然需要选择一对动作，但是不受到任何反馈，$Z_t\in \{0,1\}$ 指示学习者是否在第 $t$ 轮进行了查询。对于偏好函数，其一般要假设满足一定的关于序关系的性质：

Assumption：我们假设 $f^{\star }$ 在函数类 $\mathcal{F}$ 中，且函数类 $\mathcal{F}$ 中的所有函数都满足以下两个性质：传递性/Transitivity，对于任何上下文 $x\in \mathcal{X}$ 和动作 $a,b,c\in \mathcal{A}$，如果 $f(x,a,b)>0$ 且 $f(x,b,c)>0$，那么 $f(x,a,c)>0$；反对称性/Anti-symmetry，对于任何上下文 $x\in \mathcal{X}$ 和动作 $a,b\in \mathcal{A}$，有 $f(x,a,b)=-f(x,b,a)$。

传递性意味着偏好是可以排序的,反对称性决定了偏好方向的一致性，即如果 $a$ 比 $b$ 好，那么 $b$ 一定比 $a$，这就避免了回环，因此最优摇臂一定存在。最优臂定义位对于任意 $f\in \mathcal{F}$ 和上下文 $x\in \mathcal{X}$，存在一个臂 $a\in \mathcal{A}$，使得对于任意臂 $b\in \mathcal{A}$ 都有 $f(x,a,b)\ge 0$。我们将这个最佳臂不失一般性地记为 ${\pi }_f(x):=a$。

我们直接可以将偏好函数 $f^{\star }$ 建模为奖励差值的形式：假设存在一个奖励函数 $r^{\star }:\mathcal{X}\times \mathcal{A}\to [0,1]$，我们直接定义 $f^{\star }(x,a,b)=r^{\star }(x,a)-r^{\star }(x,b)$。在这种情况下，通常会选择 $\varphi (d)=1/(1+\exp (-d))$，这对应了 Bradley-Terry-Luce/BTL 模型，在实践中这样的模型用于学习奖励模型。

对于上下文老虎机设定，学习者的目标是最小化遗憾/Regret 和查询次数/Queries，定义如下：

$${\mathrm{Regret}}_T^{\mathrm{CB}}:=\sum _{t=1}^T\left(f^{\star }(x_t,{\pi }_{f^{\star }}(x_t),a_t)+f^{\star }(x_t,{\pi }_{f^{\star }}(x_t),b_t)\right),{\mathrm{Queries}}_T^{\mathrm{CB}}:=\sum _{t=1}^T{Z}_t.$$

3.2 Imitation Learning Setting

Imitation Learning 设定中，我们考虑一个有限视界/Finite-Horizon 的 MDP，由元组 $M(\mathcal{X},\mathcal{A},r,P,H)$ 定义，其中 $\mathcal{X}$ 是状态空间，$\mathcal{A}$ 是动作空间，$P$ 是转移函数，$r:\mathcal{X}\times \mathcal{A}\to [0,1]$ 是奖励函数，$H$ 是每一集的长度。

交互过程如下面所述：在每一集 $t\in [T]$ 开始时，学习者接收到一个初始状态 $x_{t,0}$（这也可以是对抗的）。然后，学习者与环境交互 $H$ 步。在每一步 $h$，学习者首先决定是否进行查询。如果进行查询，学习者需要选择一对动作 $(a_{t,h},b_{t,h})\in \mathcal{A}\times \mathcal{A}$，随后会收到一个反馈 $y_{t,h}\in \{-1,1\}$，指示从专家角度看哪个动作更优。这里的反馈采样自：

$$\text{Pr}(a_{t,h}\succ b_{t,h}\mid x_{t,h},h)=\text{Pr}(y_{t,h}=1\mid x_{t,h},a_{t,h},b_{t,h},h)=\varphi (f_h^{\star }(x_{t,h},a_{t,h},b_{t,h})).$$

剩余基本上和在 Contextual Bandits 设定中一样，无论学习者是否进行了查询，它随后都会从 $a_{t,h},b_{t,h}$ 选择一个动作并转移，在 $H$ 步之后，下一集开始。$Z_{t,h}\in \{0,1\}$ 指示学习者是否决定在第 $t$ 集的第 $h$ 步进行查询。我们假设函数空间 $\mathcal{F}$ 是 $H$ 个类的乘积，即 $\mathcal{F}={\mathcal{F}}_0\times \cdots \times {\mathcal{F}}_{H-1}$，其中对于每个 $h$，我们使用 ${\mathcal{F}}_h=\{f:\mathcal{X}\times \mathcal{A}\times \mathcal{A}\to [-1,1]\}$ 来建模 $f_h^{\star }$，并假设 ${\mathcal{F}}_h$ 满足传递性和反对称性假设。

策略/Policy 是一个映射 $\pi :\mathcal{X}\to \Delta (\mathcal{A})$。对应定义价值函数和动作价值函数。在模仿学习设定下，我们假设专家具有一个马尔可夫策略/Markov Policy ${\pi }_e$，并且专家的偏好依赖于 ${\pi }_e$ 下的后续累积奖励/Reward-to-Go 来决定偏好，形式化讲就是 $f_h^{\star }(x,a,b)=Q_h^{{\pi }_e}(x,a)-Q_h^{{\pi }_e}(x,b)$。因此，学习者的目标仍然是最小化遗憾和查询次数：

$${\mathrm{Regret}}_T^{\mathrm{IL}}:=\sum _{t=1}^T\left(V_0^{{\pi }_e}(x_{t,0})-V_0^{{\pi }_t}(x_{t,0})\right),{\mathrm{Queries}}_T^{\mathrm{IL}}:=\sum _{t=1}^T\sum _{h=0}^{H-1}{Z}_{t,h}.$$

3.3 Link Function and Online Regression Oracle

我们一般假设 $\varphi$ 是某个 $\alpha$-强凸函数 $\Phi :[-1,1]\to \mathbb{R}$ 的导数，并将相关联的损失函数定义为 ${\ell }_{\varphi }(d,y)=\Phi (d)-d(y+1)/2$。此外，我们的算法利用了一个在线回归预言机/Online Regression Oracle，在线地输出一个函数 $f_t\in \mathcal{F}$，对于任意数据序列在 $\mathcal{F}$ 上具有次线性的遗憾保证：

Assumption：我们假设学习者可以使用一个 Online Regression Oracle，对于任意序列 $\{(x_1,a_1,b_1,y_1),\dots ,(x_T,a_T,b_T,y_T)\}$，这里序列每一项的标签 $y_t$ 生成自 $y_t\sim \varphi (f^{\ast }(x_t,a_t,b_t))$，我们有：

$$\sum _{t=1}^T{\ell }_{\varphi }\left(f_t(x_t,a_t,b_t),y_t\right)-\underset{f\in \mathcal{F}}{\inf }{\ell }_{\varphi }\left(f(x_t,a_t,b_t),y_t\right)\le {\rm Y}(\mathcal{F},T)$$

这里的上界 ${\rm Y}(\mathcal{F},T)$ 相对于 $T$ 次线性增长。若上下文清晰，我们定义 ${\rm Y}:={\rm Y}(\mathcal{F},T)$。这里的 ${\rm Y}$ 代表遗憾上界，在许多情况下通常是 $T$ 或函数类 $\mathcal{F}$ 复杂度/大小的对数阶。

要理解这里的设计，我们需要先了解算法的机制：算法大致流程是在每一轮 $t$ 之前都可以得到一个偏好函数 $f_t$，然后基于这个函数计算出版本空间/Version Space ${\mathcal{F}}_t$ 与候选摇臂集/Set of Candidate Arms ${\mathcal{A}}_t$，随后基于这些集合来计算不确定度及其阈值，从而决定是否进行查询。在决定查询之后，才可以获得该轮的反馈 $y_t$，并将 $(x_t,a_t,b_t,y_t)$ 添加到数据集中，进而根据 Oracle 来得到新一轮的偏好函数 $f_{t+1}$。

因此，Oracle 需要设计为在线地最小化某种回归损失，而不是朴素的经验风险最小化，其遗憾是相对于整个在线学习过程的，计算每一轮老的偏好函数 $f_t$ 在新数据点 $(x_t,a_t,b_t,y_t)$ 上的损失，进而拥有根据数据迭代和预测未来的能力。这样的设计使得算法和理论均模块化，

4. Algorithm on Contextual Dueling Bandits

AROURA 算法原为 Active Preference Query for Contextual Bandits 算法，在每一轮 $t\in [T]$ 中