图片来自网络
研究背景
随着信息技术的发展，算法在各类在线决策中扮演着越来越重要的角色。然而，随着算法应用的普及，公平性问题日益受到关注。在现实应用中，常常存在对算法进行公平性约束的需求，以确保不同群体在决策中的平等对待。然而，如何在保持决策效用的同时，实现公平性，成为了一个具有挑战性的课题。近年来，在线优化和机器学习领域的发展为这一问题的解决提供了新的思路，尤其是在数据交易的背景下，通过购买和使用不同质量的数据信息源，决策者能够更准确地推断用户的敏感属性，从而更好地平衡公平性和效用。然而，这也带来了新的问题，即如何在不完全信息的情况下，结合数据交易有效地进行公平性决策，既确保购买数据的成本效益，又达到公平性目标。
研究方法
本研究[1]提出了一种结合在线优化和多臂赌博机（multi-armed bandit）算法的公平性决策方法。如图1所示，该方法分为两个主要部分：信息源选择和分配决策。
图1 算法流程
首先，在信息源选择部分，研究者使用了EXP3算法，这是一种广泛应用于多臂赌博机问题的策略。EXP3算法适用于处理未知环境中的决策问题，特别是在面临多个选择时。该算法通过动态调整每个信息源的选择概率，使得算法在长远过程中既能探索新的可能性，又能利用已有的最优选择。EXP3算法的核心在于根据过去的选择和奖励，计算每个信息源的“虚拟奖励”。具体来说，对于每个时间步，算法首先随机选择一个信息源，观察其返回的上下文数据，然后基于该数据估计该信息源的潜在奖励，并使用这一信息更新所有信息源的选择概率。
在实际操作中，EXP3算法通过引入一个“虚拟奖励”函数，该函数不仅考虑了实际奖励，还结合了与公平性相关的惩罚项。虚拟奖励的计算公式为：
(其中，为当前的对偶参数，为选择的信息源上下文数据，为选择该信息源的成本。)
其次，在分配决策部分，研究者采用了基于梯度下降法的优化策略，以在动态环境中最小化决策中的公平性惩罚。具体来说，算法在每个时间步都要计算一个分配策略，该策略不仅要考虑当前上下文数据和信息源，还要结合算法的历史决策，逐步调整以达到最优的公平性和效用平衡。这个过程包括计算一个“分配决策变量”，该变量决定了是否选择当前的用户。分配决策的计算公式为：
也就是说，当预期效用大于或等于公平性惩罚时，算法选择当前用户。反之，则不选择。在更新算法参数方面，每个时间步都会更新对偶参数，以反映当前决策的公平性影响。具体来说，研究者使用了以下更新规则：
（其中，为学习率，为当前的最优公平性目标，为当前的实际分配结果。）通过这种方式，算法能够在多轮决策中不断优化，实现对公平性和效用的动态平衡。
研究结果
研究结果表明，该算法在处理多信息源和公平性约束的在线决策问题上表现出色。具体而言，该算法的遗憾值（regret）呈现出次线性增长，说明算法能够随着时间的推移逐步逼近最优解。此外，实验还展示了在不同的惩罚参数和信息源价格设定下，算法的效用和公平性表现。研究发现，当信息成本较高时，算法倾向于减少信息购买，从而可能导致公平性下降；而当公平性惩罚较高时，算法则会更倾向于选择能确保公平性的策略，即使这意味着效用的降低。这些结果为进一步优化在线决策中的公平性提供了重要的参考。
此外，图2展示了几种算法在不同时间步（T）下的总效用表现。红线代表的Algorithm 1明显优于其他算法，特别是在长时间步下，接近最优解（OPT）的表现。相比之下，没有信息源选择的Algorithm 1（蓝线）表现较差，几乎保持恒定效用，显示了信息源选择的重要性。绿色的Greedy Algorithm效用随着时间步增长反而下降，进一步证明了Algorithm 1在处理多信息源和公平性约束的在线决策问题上的优势。
图2 算法随时间变化的性能表现
相关论文
[1] Molina M, Gast N, Loiseau P, et al. Trading-off price for data quality to achieve fair online allocation[J]. Advances in Neural Information Processing Systems, 2023, 36: 40096-40139.
写在最后
我们的文章可以转载了呢~欢迎转载与转发呦
想了解更多前沿科技与资讯？
长按二维码关注我们！
欢迎点击右上方分享到朋友圈
香港中文大学（深圳）
网络通信与经济学实验室
微信号 : ncel_cuhk
