Aug, 2018

在 Plackett-Luce 模型中应对 Bandits 问题的 PAC 方法

PDF
TL;DR该研究引入了 PAC Battling-Bandit 问题，通过 Plackett-Luce 子集选择模型在在线学习框架中寻找高置信度的最佳物品，对不同反馈模型下的样本复杂度进行研究，发现利用排名顺序反馈可以从统计效率上提高样本复杂度。
online learningplackett-luce modelsample complexityfeedback modelsstatistical efficiency
发现论文，激发创造
  • 具有子集评价偏好的主动排名

    本研究旨在通过自适应挑选子集并收集偏好反馈，在 Plackett-Luce 模型下解决 PAC 排名问题，提出了新的 pivot trick 技巧，从而实现了在一定概率下识别 n 个项目的 ε- 最优排名，（m-1）/m 降低的样本复杂度和对称排名算法的阶无法提高的。

    Oct, 2018

  • 随机多臂赌博机中多个好臂的 PAC 识别

    在研究中，我们将 n 个武器的随机多臂强盗问题与 PAC 设定结合起来，提出了一种有效的方法来解决从最佳 m 个武器中准确识别 k 个武器的问题，其中 1≤k≤m，同时给出了一些相关算法和下界。

    Jan, 2019

  • 多类别 PAC 型强盗分类的快速速率

    我们研究了具有强化学习反馈的多分类 PAC 学习问题，提出了一种新颖的学习算法将样本复杂度降低到 O ((poly (K) + 1/ε²) log (|H|/δ))，改进了现有问题的边界，同时在一般类别情况下也得到了类似的样本复杂度边界，算法利用随机优化技术通过 Frank-Wolfe 更新计算低方差探索分布。

    Jun, 2024

  • 基于成对和列表查询的 PAC 排名：下界和上界

    本文研究了使用多项式逻辑模型下的 $l（l≥2$)$-wise$ ($l≥2$) 比较的积极 PAC top-k 排名（即 top-k 项目选择）和总排名问题，通过自适应地选择查询组并观察每个查询的最受欢迎项的嘈杂结果，我们要设计排名算法，使用尽可能少的查询来恢复 top-k 或总排名。

    Jun, 2018

  • 随机效用模型下的子集选择最佳项学习

    我们提出了一种基于 PAC 学习的随机效用模型（RUM）的新学习算法，通过使用分层消除和基于两两相对比较的临界统计值进行训练，可以在 O (n/(c^2ε^2) log (k/δ)) 轮内识别出一个具有 ε 优异度的项，其中对于足够敏感于项参数之间的差距 c 的 RUM 的最差情况下双方优势。

    Feb, 2020

  • 引发 Kemeny 排名

    通过对代理人的偏好进行赋值，我们将找到 Kemeny 排名作为对抗式武装强盗问题。我们考虑了采样和不采样的情况，并提供了概率近似正确（PAC）解决方案的算法，同时详细说明了其采样复杂度。如果所有代理人的偏好都是对备选项的严格排名，我们提供了剪枝置信区间的方法，以便更有效地赋值，并提出了几种自适应采样方法进行比较。

    Dec, 2023

  • DP-Dueling：从偏好反馈学习而不损害用户隐私

    在差分隐私的约束下，我们提出了一种首个能够保护用户偏好的活跃学习的差分隐私决策竞争算法，具有接近最优性能的高效计算能力与遗憾边界。

    Mar, 2024

  • 基于偏好的 Dueling Bandits 在线学习：综述

    本研究调查了基于偏好的多臂赌博机和决斗赌博机的最新研究现状及其解决方法，关注于在序贯决策过程中进行的数据反馈和学习，并且考虑了强度信息不可用的情况。

    Jul, 2018

  • 组合赌博机与相对反馈

    本文围绕多项式逻辑选择模型，研究了在线学习中集合选择的组合优化问题及其相关算法，并通过实验验证了理论结果。

    Mar, 2019

  • 自适应多臂识别

    研究了如何在随机赌博机游戏中选择期望回报最高的 K 个赌臂问题，提出了一种基于概率近似正确算法，并引入了难度参数来量化问题难度。通过研究两种算法的采样复杂度，得出了更优的上界，并证明了该上界在某些情况下是紧的。同时得出了引入难度参数的实例相关算法需要额外的对数因子作为代价的下界。

    Jun, 2017