Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Dueling

本文研究了从不完美的人类反馈中学习（LIHF），这是由于人类潜在的非理性或对真实偏好的感知不完美所引发的。我们将经典的Dueling Bandit问题重新审视为从比较人类反馈中学习的模型，并通过将人类反馈的不完美性视为对用户效用的不可知污染来丰富它。我们首先确定了LIHF的基本限制，并证明了即使已知总污染$C$并且污染随时间平稳衰减（即，用户反馈变得越来越准确），也存在$\Omega(\max\{T^{1/2},C\})$的遗憾下限。然后，我们转向设计鲁棒的算法，适用于具有任意污染和未知$C$的实际情况。我们的关键发现是，基于梯度的算法通过变化学习率在污染下具有平稳的效率-鲁棒性权衡。具体而言，在一般的凹用户效用下，Yue和Joachims（2009）的Dueling Bandit Gradient Descent（DBGD）可以调整以实现对于任何给定参数$\alpha\in(0,\frac{1}{4}]$的遗憾$O(T^{1-\alpha} + T^{\alpha} C)$。此外，据我们所知，这个结果使我们能够确定标准DBGD（$\alpha=1/4$的情况）的遗憾下限为$\Omega(T^{3/4})$。对于强凹用户效用，我们展示了更好的权衡：存在一个算法，对于任何给定的$\alpha\in[\frac{1}{2},1)$，可以实现$O(T^{\alpha} + T^{\frac{1}{2}(1-\alpha)}C)$的遗憾。我们的理论洞见得到了对真实世界推荐数据的广泛实验的证实。

研究从不完美的人类反馈中学习的问题，提出了一种新的模型，即带有不完美反馈的Dueling Bandit问题，并探讨了该问题的理论下限和算法设计。

使用梯度下降算法来处理带有不完美反馈的Dueling Bandit问题，并通过调整学习率来平衡效率和鲁棒性。

论文提出的算法在真实世界的数据集上进行了广泛的实验，并取得了良好的效果。此外，论文还证明了标准DBGD算法的理论下限，值得关注。

相关研究包括使用不同算法来解决Dueling Bandit问题，如LinUCB算法和Exp3算法等。