Devising a fair classifier that does not discriminate against different
groups is an important problem in machine learning. Although researchers have
proposed various ways of defining group fairness, most of them only focused on
the immediate fairness, ignoring the long-term impact of a fair classifier
under the dynamic scenario where each individual can improve its feature over
time. Such dynamic scenarios happen in real world, e.g., college admission and
credit loaning, where each rejected sample makes effort to change its features
to get accepted afterwards. In this dynamic setting, the long-term fairness
should equalize the samples' feature distribution across different groups after
the rejected samples make some effort to improve. In order to promote long-term
fairness, we propose a new fairness notion called Equal Improvability (EI),
which equalizes the potential acceptance rate of the rejected samples across
different groups assuming a bounded level of effort will be spent by each
rejected sample. We analyze the properties of EI and its connections with
existing fairness notions. To find a classifier that satisfies the EI
requirement, we propose and study three different approaches that solve
EI-regularized optimization problems. Through experiments on both synthetic and
real datasets, we demonstrate that the proposed EI-regularized algorithms
encourage us to find a fair classifier in terms of EI. Finally, we provide
experimental results on dynamic scenarios which highlight the advantages of our
EI metric in achieving the long-term fairness. Codes are available in a GitHub
repository, see this https URL

提出一种新的公正性指标 EI (即平等的可改进性)，并且提出了三种算法来解决 EI 规则化优化问题。实验结果表明，使用 EI 指标可以实现长期公正性。

Equal Improvability: 一个考虑长期影响的新公平性概念

Equal Improvability: A New Fairness Notion Considering the Long-term  Impact

We study stochastic multi-armed bandits with many players. The players do not
know the number of players, cannot communicate with each other and if multiple
players select a common arm they collide and none of them receive any reward.
We consider the static scenario, where the number of players remains fixed, and
the dynamic scenario, where the players enter and leave at any time. We provide
algorithms based on a novel `trekking approach' that guarantees constant regret
for the static case and sub-linear regret for the dynamic case with high
probability. The trekking approach eliminates the need to estimate the number
of players resulting in fewer collisions and improved regret performance
compared to the state-of-the-art algorithms. We also develop an epoch-less
algorithm that eliminates any requirement of time synchronization across the
players provided each player can detect the presence of other players on an
arm. We validate our theoretical guarantees using simulation based and real
test-bed based experiments.

本文研究了具有许多玩家的随机多臂老虎机。结果表明我们提出的一种新的 “徒步旅行策略” 不需要估计玩家的数量，同时保证了静态情况下常数风险和动态情况下高概率的子线性风险表现。我们还证明了我们的算法的有效性。