  While machine learning can myopically reinforce social inequalities, it may
also be used to dynamically seek equitable outcomes. In this paper, we
formalize long-term fairness in the context of online reinforcement learning.
This formulation can accommodate dynamical control objectives, such as driving
equity inherent in the state of a population, that cannot be incorporated into
static formulations of fairness. We demonstrate that this framing allows an
algorithm to adapt to unknown dynamics by sacrificing short-term incentives to
drive a classifier-population system towards more desirable equilibria. For the
proposed setting, we develop an algorithm that adapts recent work in online
learning. We prove that this algorithm achieves simultaneous probabilistic
bounds on cumulative loss and cumulative violations of fairness (as statistical
regularities between demographic groups). We compare our proposed algorithm to
the repeated retraining of myopic classifiers, as a baseline, and to a deep
reinforcement learning algorithm that lacks safety guarantees. Our experiments
model human populations according to evolutionary game theory and integrate
real-world datasets.
