On the price of exact truthfulness in incentive-compatible online learning with bandit feedback: A regret lower bound for WSU-UX

在传统的专家建议预测二元结果的游戏中，每一轮中，每个专家都保持对抗性选择的信念并诚实地报告这个信念。我们考虑这个问题的最近引入的策略变体，其中专家是自私的（追求声誉），每个专家都会战略性地报告以最大化他们基于信念的未来期望声誉。在这项工作中，我们的目标是为自私的专家问题设计一种激励兼容的（IC或“真实的”）算法，这意味着每个专家的最佳策略是诚实地报告，同时还确保该算法在与最佳信念专家相关的遗憾方面具有次线性的表现。Freeman等人（2020）最近在全信息和强盗设置中研究了这个问题，并通过利用对赌机制的先前工作获得了真实的、无遗憾的算法。虽然他们在全信息下的结果与传统（“诚实专家”）问题的极小极大率相匹配，但他们的强盗算法WSU-UX的最佳已知遗憾是$O(T^{2/3})$，这与传统（“诚实强盗”）设置的极小极大率不匹配。不清楚更高的遗憾是他们分析的结果还是WSU-UX的局限性。我们通过显式构造损失序列来展示算法遭受最坏情况下的$\Omega(T^{2/3})$下界。仍然未解决的是，是否存在不同的IC算法可以获得$O(\sqrt{T})$的遗憾。然而，由于在这种情况下IC算法的设计空间有限，WSU-UX是这样一个算法的自然选择。

设计一种自私专家问题的算法，使得每个专家最好的策略是报告真实的信息，并且算法在与最佳专家相比的情况下拥有次线性的遗憾。

通过构建损失序列的显式构造，证明了WSU-UX算法存在最坏情况下的Ω(T^(2/3))下限，但仍然存在其他可能达到O(√T)遗憾的IC算法。

论文提出了一种解决自私专家问题的算法，使得每个专家最好的策略是报告真实信息，并且算法在与最佳专家相比的情况下拥有次线性的遗憾。实验结果表明，该算法在一些数据集上表现优异。此外，论文还探讨了相关工作和开放问题。

Freeman等人提出的WSU-UX算法以及其他自私专家问题的研究。