Dueling Bandits with Weak Regret¶
约 1943 个字 4 张图片 预计阅读时间 6 分钟
Abstract
- Tag: Dueling Bandits, Weak Regret, Winner Stays.
- Proceedings of the 34 th International Conference on Machine Learning, Sydney, Australia, PMLR 70, 2017.
- Origin Paper Link
- 文中图片均来自论文。
0 Most Important Things¶
1 Introduction¶
背景故事：考虑在个性化推荐内容中的老虎机学习问题，其中反馈是通过隐式的成对比较获得的。我们向用户提供成对的项目，记录关于哪个提供的项目更受偏好的隐性反馈，旨在快速了解用户对项目的偏好，同时确保我们未能提供高质量项目的时间比例很小。
形式化看，我们可能提供给用户的项目被称为摇臂/Arms，通过一系列决斗/Duels 来了解这些摇臂，在每次决斗中，我们拉动两个摇臂，并从用户那里接收带噪声的反馈，告知哪个摇臂更受偏好。当一个摇臂在决斗中被偏好时，我们称该摇臂赢得了决斗。
弱后悔对应于只要将孔多塞赢家选为决斗中的任何一个臂即可避免后悔，比如 Grubhub 和 UberEATS 这样的食品配送服务提供的应用内餐馆推荐，只有当用户最偏好的餐馆没有被推荐的时候，用户才会遭受后悔。例子还包括在 Twitch 等平台上推荐在线主播等。
2 Related Work¶
迄今为止的大多数工作都关注强遗憾/Strong Regret，我们已经知道，对于任何算法，到时间 \(T\) 为止的最坏情况累积期望强遗憾是 \(\Omega(N\log(T))\)。在 Finite-Horizon 设定和孔多塞赢家假设下，已经提出了一些能够达到此下界的算法：Interleaved Filter (IF) 和 Beat the Mean (BTM)。Relative Upper Confidence Bound (RUCB) 也在 Horizonless 设定下达到了此下界。Relative Minimum Empirical Divergence (RMED) 是第一个其遗憾界与此下界相匹配的算法。Copeland Confidence Bound (CCB) 和 Scalable Copeland Bandits (SCB) 是两个在不存在孔多塞赢家的情况下达到最优遗憾界的算法。
利用强遗憾严格大于弱遗憾的事实，可以设计出弱遗憾界为 \(O(N\log(T))\) 的算法。
使用成对比较的主动学习/Active Learning 也与我们的工作密切相关。Query Selection Algorithm (QSA) 使用期望 \(d\log(N)\) 次操作来排序 \(N\) 个臂，其中 \(d\) 是臂嵌入空间的维度。使用自适应成对比较可以进行 top-k 元素选择，有一种通用的 Racing 算法，专注于最小化样本复杂度。
3 Problem Formulation¶
对于 \(N\) 个摇臂，在每个时间点 \(t=1, 2, \dots\)，系统在两个摇臂之间进行一次决斗/Duel。用户随后提供二元反馈，决定哪个摇臂赢得决斗。这个二元反馈是随机的，并且在给定展示的臂对的条件下，与所有过去的交互是条件独立的。我们令 \(p_{i,j}\) 表示当展示臂 \(i\) 和 \(j\) 时，用户给出偏好臂 \(i\) 反馈的概率。如果用户偏好臂 \(i\) 胜过臂 \(j\)，我们假设 \(p_{i,j} > 0.5\)。我们也假设对称性：\(p_{i,j} = 1 - p_{j,i}\)。
我们假设臂 1 是一个孔多塞赢家/Condorcet Winner，即对于 \(i=2, \dots, N\)，有 \(p_{1,i} > 0.5\)。在一些结果中，我们还考虑臂具有全序/Total Order 的设定，即臂可以被排序，使得对于所有 \(i < j\)，都有 \(p_{i,j} > 0.5\)。全序假设蕴含了传递性。
我们令 \(p = \min\limits_{p_{i,j}>0.5} p_{i,j} > 0.5\) 为用户选择更优臂的概率的一个下界。
我们考虑二元形式的弱遗憾和强遗憾。在某时间点产生的单周期弱遗憾定义为：如果我们选择的两个臂中没有包含最佳臂，则 \(r(t) = 1\)，否则 \(r(t) = 0\)。单周期强遗憾定义为：如果我们没有两次都选择最佳臂，则 \(r(t) = 1\)，否则 \(r(t) = 0\)。后面也会定义 Utility-Based 的弱遗憾和强遗憾。注意我们使用相同的符号 \(r(t)\) 来表示强遗憾和弱遗憾，并依赖上下文来区分这两种情况。在这两种情况下，我们将直到时间 \(T\) 的累积遗憾/Cumulative Regret 定义为 \(R(T) = \sum_{t=1}^T r(t)\)。我们通过算法的期望累积遗憾来衡量其性能。
4 Winner Stays¶
4.1 Winner Stays with Weak Regret¶
定义 \(q_{i,j}(t)\) 为在时间 \(t\) 以及之前决斗中，臂 \(i\) 击败臂 \(j\) 的次数，定义 \(C(t,i) = \sum_{j \neq i} (q_{i,j}(t) - q_{j,i}(t))\)。\(C(t,i)\) 是截至时间 \(t\) 臂 \(i\) 赢得的决斗次数与输掉的决斗次数之差，也就是所谓的净胜场数。
选择策略为：在每一个时间点都选择当前 \(C(t-1, \cdot)\) 值最高的两个臂 \(i_t\) 和 \(j_t\) 进行决斗。另一个关键点在于打破平局的规则：在选择参与决斗的臂的时候，都优先选择上一轮参与决斗的臂（只要其是得分最高的摇臂之一），并且算法倾向于在接下来的一小段时间点都选择这两个摇臂（只要它们仍然是得分最高的摇臂之一）。
WS-W 的选择过程可以被组织成迭代/Iteration 和轮/Round，每一个迭代由一系列对同一对摇臂的选择组成，而每一轮由一系列迭代组成，其中在某一次迭代中失败的摇臂不会在后续的迭代中被选择，直到下一轮开始。
Winner Stays 的特性使得 WS-W 的过程由一系列的轮组成，每一轮都是 \(N-1\) 次迭代的序列，并且在一个迭代中失败的臂直到下一轮才会被重新访问。比如在第一轮结束之后，最终的胜者 \(Z(1)\) 将会有 \(C(t, Z(1)) = N-1\)，而所有其他臂 \(j \neq Z(1)\) 则有 \(C(t, j) = -1\)。
4.2 Analysis of WS-W¶
对于第 \(\ell\) 轮的开始，记其时间点为 \(t_{\ell}\)，前一轮的胜者为 \(Z(\ell-1)\)，且其净胜点为 \(C(t_{\ell}-1, Z(\ell-1)) = (N - 1)(\ell - 1)\)，并且对于所有 \(j \neq Z(\ell-1)\)，有 \(C(t_{\ell}-1, j) = -\ell + 1\)。同时定义在第 \(\ell\) 轮的第 \(k\) 次迭代开始的时间点，也就是在第 \(\ell\) 轮中第一次拉动第 \(k\) 对不同臂的时间点，记为 \(t_{\ell,k}\)，并且定义 \(T_{\ell,k}\) 为这次迭代中连续拉动这对臂的次数。
定义术语：在一对臂 \(i\) 和 \(j\) 的决斗中，如果 \(p_{i,j} > 0.5\)，则称 \(i\) 为较好臂，\(j\) 为较差臂。我们称在第 \(\ell\) 轮的第 \(k\) 次迭代开始时，得分 \(C(t_{\ell,k}-1, i) > 0\) 的臂 \(i\) 为擂主/Incumbent，另一个臂 \(j\) 为挑战者/Challenger。
Lemma 1：第 \(\ell\) 轮的第 \(k\) 次迭代的长度 \(T_{\ell,k}\) 的期望上界如下界定：如果擂主比挑战者差，则上界为 \(\frac{N(l-1)+k}{2p-1}\)，如果擂主比挑战者好，则上界为 \(\frac{1}{2p-1}\)。
Lemma 2：在全序关系的假设下，给定到时间点 \(t_{\ell, k}\) 为止的历史信息，该时间点未来的迭代中，擂主比挑战者差的迭代的数量的上界为 \(\frac{2p^2}{(2p-1)^3}\left(\log(N) + 1\right)\)。
Lemma 3：令 \(L\) 为最小的 \(\ell\)，使得在此之后没有擂主比挑战者更差的轮，则 \(P(L \ge \ell) \le ((1 - p) / p)^{\ell}\)。
由于 \(p > 0.5\)，所以 \(\frac{1-p}{p} < 1\)，因此该引理其实表明了随着对决轮数的增加，擂主比挑战者更差的情况会越来越少。
定义如下示性函数：
- \(B(\ell, k)\) 为 1 当且仅当在第 \(\ell\) 轮的第 \(k\) 次迭代中，擂主比挑战者好，\(\overline{B}(\ell, k) = 1 - B(\ell, k)\)；
- \(D(\ell)\) 为 1 当且仅当第一个摇臂（最优的摇臂）是第 \(\ell\) 轮第 1 次迭代的擂主，\(\overline{D}(\ell) = 1 - D(\ell)\)；
- \(V(\ell, k)\) 为 1 当且仅当 \(D(\ell) = 1\) 且最优摇臂在第 \(\ell\) 轮的第 \(k\) 次迭代之前输掉了（在第 1 轮到第 \(k-1\) 次迭代中输掉了）。
在第 \(\ell\) 轮的第 \(k\) 次迭代中，只有 \(\overline{D}(l) = 1\) 或者对某个 \(k^{\prime} < k\) 有 \(V(l,k^{\prime}) = 1\) 时，才会产生弱遗憾。
Lemma 4：在全序关系及孔多塞赢家设定下：
在将所有的迭代分为擂主优于挑战者和擂主劣于挑战者这两种情况下，这恰好就是擂主优于挑战者且产生弱遗憾的两种情况（如果擂主优于挑战者，那么所有产生弱遗憾的情况都满足上面两个情况之一，考虑某一轮使得 \(\overline{D}(l) = 1\) 且 \(B(l,k) = 1\) 那么或许在某一次迭代中，最优臂成为了擂主或者挑战者，这样弱遗憾就消除了，但是我们将其使用仍然产生弱遗憾 bound 住）。
Lemma 5：在全序关系设置下：
- \(\mathbb{E}[\sum_{k=1}^{N-1} \overline{D}(\ell) \overline{B}(\ell, k) T_{\ell, k}]\) 上界为 \(((1 - p) / p)^{\ell - 1} \frac{2 N \ell p^2}{(2p-1)^4} \left(\log(N) + 1\right)\)；
- \(\mathbb{E}[\sum_{k=1}^{N-1} V(\ell, k) \overline{B}(\ell, k) T_{\ell, k}]\) 上界为 \(((1 - p) / p)^{\ell} \frac{2N \ell p^2}{(2p-1)^4} (\log(N) + 1)\)。
Theorem 1：在全序关系设置下，WS-W 的累积期望弱遗憾上界为 \(\left[\frac{2p^{3}}{(2p-1)^{6}}N(\log(N)+1)+\frac{N}{(2p-1)^{2}}\right]\)。
Proof Sketch
Theorem 2：在孔多塞赢家设置下，WS-W 的累积期望弱遗憾上界为 \(\left[\frac{N}{(2p-1)^{2}}+\frac{pN^{2}}{(2p-1)^{3}}\right]\)。
Proof Sketch
4.3 Winner Stays with Strong Regret¶
WS-S 将 WS-W 的算法作为子程序，并且使用一个机制来保证强遗憾在一定范围内。具体而言，WS-S 的每一轮都分为 Exploration 和 Exploitation 两个阶段，在 Exploration 阶段，WS-S 会使用 WS-W 的算法来选择臂，而在 Exploitation 阶段，WS-S 会连续摇动选择的最佳摇臂 \(\beta\) 的指数次，调整 \(\beta\) 的大小平衡了这两个阶段的长度。
Theorem 3：在全序关系设置下，WS-S 的累积期望强遗憾上界为 \(\left[\frac{2p^{3}}{(2p-1)^{6}}N(\log(N)+1)+\frac{N \log_{\beta}(T (\beta - 1))}{2p-1}\right]\)，其中 \(1 < \beta \leq \frac{p}{1-p}\)。