Online Learning with Sublinear Best-Action Queries

在线学习中，决策者重复选择一组行动之一，目的是最小化产生的总损失。在最近的研究中，关于带有额外预测特征的算法，我们通过允许决策者获取有关要选择的行动的额外信息来重新审视这个问题。特别地，我们研究了“最佳行动查询”的能力，它们预先揭示了给定时间步骤中最佳行动的身份。在实践中，预测特征可能很昂贵，因此我们允许决策者发出最多$k$个这样的查询。我们为不同类型的反馈模型建立了任何算法在给予$k$个最佳行动查询的情况下可以实现的性能的紧密界限。特别地，我们证明，在完全反馈模型中，$k$个查询足以实现$\Theta\left(\min\left\{\sqrt{T}, \frac{T}{k}\right\}\right)$的最优遗憾。这一发现突显了即使是少量（次线性）的查询$k \in \Omega(\sqrt{T})$也能实现遗憾率的显著乘性优势。此外，我们研究了一个具有挑战性的设置，其中唯一可用的反馈是在对应于$k$个最佳行动查询的时间步骤中获得的。在那里，我们提供了一个紧密的遗憾率$\Theta\left(\min\left\{\frac{T}{\sqrt{k}},\frac{T^2}{k^2}\right\}\right)$，这比$k \in \Omega(T^{2/3})$的标签有效预测的标准$\Theta\left(\frac{T}{\sqrt{k}}\right)$遗憾率有所改进。

研究在线学习中，通过最佳动作查询来获取额外预测特征的算法，以达到最小化整体损失的目标。同时考虑了预测特征获取的成本，并限制最大查询次数为k。研究了不同反馈模型下算法的性能界限。

利用最佳动作查询来获取额外预测特征，可以在全反馈模型下达到最优的后悔率。在只有有限反馈模型下，提出了一种新的后悔率界限，相比标准方法有所提高。

论文提出的算法可以帮助决策者在在线学习中获取额外的预测特征，从而最小化整体损失。实验结果表明，即使最大查询次数较少，仍然可以达到较优的后悔率。论文提出的方法在只有有限反馈模型下，相比标准方法有所提高。

最近的相关研究包括：'Online Learning with Feedback Graphs: Beyond Bandits'，'The Power of Localization for Efficiently Learning Linear Separators with Noise'等。