Long-Term Fairness with Unknown Dynamics
Authors: Tongxin Yin
Reilly Raab
Mingyan Liu
Yang Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: Long-term Fairness
Dynamics
Reinforcement Learning
TL;DR: Desirable social outcomes that are in conflict with myopic optimization may be realized as solutions to long-term fairness, which we formalize as a reinforcement learning problem.

Abstract: 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 as an online reinforcement learning problem for a policy affecting human populations. This formulation accommodates dynamical control objectives, such as achieving equitable population states, that cannot be incorporated into static formulations of fairness. We demonstrate that algorithmic solutions to the proposed fairness problem can adapt to unknown dynamics and, by sacrificing short-term incentives, drive the policy-population system towards more desirable equilibria. For the proposed setting, we develop an algorithm that adapts recent work in online learning and prove that this algorithm achieves simultaneous probabilistic bounds on cumulative loss and cumulative violations of fairness. In the classification setting subject to group fairness, we compare our proposed algorithm to several baselines, including the repeated retraining of myopic or distributionally robust classifiers, and to a deep reinforcement learning algorithm that lacks fairness guarantees. Our experiments model human populations according to evolutionary game theory and integrate real-world datasets.

Long-Term Fairness with Unknown Dynamics
Tongxin Yin"
Reilly Raab"
Electrical and Computer Engineering
Computer Science and Engineering University of California, Santa Cruz Santa Cruz, CA 95064 rei reillyEucsc. edu
University of Michigan Ann Arbor, MI 18109 tyin@umich. edu
Mingyan Liu
Yang Liu University of California, Santa Cruz ByteDance Research Santa Cruz, CA 95064 yangliuducsc. edu
Electrical and Computer Engineering
University of Michigan Ann Arbor, MI 48109 mingyan&umicc ch. edu
Abstract
While machine learning can myopically reinforce social inequalities, it may also be used to dynamically seek equitable outcomes. this paper, we formalize long-term faimees as online reinforcement learning problem for policy affecting human populations. This formulation accommodates dynamical control objectives, such achieving equitable population states, that cannot be incorporated into static formulations of fairness. We demonstrate that algorithmic solutions to the proposed fairness problem adapt unknown dynamics and, by sacrificing short-term incentives, drive the policy-population system towards more desirable equilibria. For the proposed setting, we develop algorithm that adapts recent work in online learning and prove that this algorithm achieves simultancous probabilistic bounds cumulative loss and cumulative violations of fairness. In the classification setting subject to group fairness, we compare our proposed algorithm to several baselines, including the repeated retraining of myopic or distributionally robust classifiers, and to deep reinforcement learning algorithm that lacks fairess guarantees. Our experiments model human populations according to evolutionary game theory and integrate real-world datasets.
Introduction
As machine learning (ML) algorithms are deployed for tasks with real-world social consequences (e.g., school admissions, loan approval, medical interventions, etc.), the possibility exists for runaway social inequalities (Crawford and Calo, 2016; Chaney et al., 2018; Fuster et al., 2018; Ensign et al., 2018). While "fairness" has become a salient ethical concern contemporary research, the closed-loop dynamics of real-world systems with feedback, i.e., comprising MI-driven decisions and populations that mutually adapt to each other (Fig. in the supplementary material) remain poorly understood. We assert that realistic scenarios often described by fundamentally unknown dynamics: Even with models of human behavior based on rational behavior or evolutionary game theory, utilities and risk-preeerences for dynamics-agnostic formulations of fairness, for which reinforcement learning is natural fit.
generally unknown uncertain. For this reason, we advocate
In this paper, our primary contribution is to consider the problem of long-term fairness, algorith- mie fairness in the context of a dynamically responsive population, as a reinforcement learning (RL)
'These authors contributed equally this work.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

problem subject to constraint. In our formulation, the central learning task is to develop policy that minimizes cumulative loss (e.g.. financial risk, negative educational outcomes, misdiagnoses, etc.) incurred by an agent interacting with a human population up to a finite time horizon, subject to constraints on cumulative "violations of fairness", which we refer to in single time step as disparity and cumulatively as distortion.
Our central hypothesis is that an RL formulation of long-term fairness may allow an agent to learn to sacrifice short-term utility in order to drive the system towards more desirable equilibria. The core practical difficulties posed by our general problem formulation, however, are the potentially unknown dynamics of the system under control, which must be determined by the RL agent online (i.e.. during actual deployment), and the general non-convexity of the losses or constraints considered. Additionally, our problem setting generally requires continuous state and action spaces for the RL agent, which preclude familiar methods that yield performance guarantees in discrete settings.
Our secondary contributions are 1) to show that long-term fairness can be solved within asymptotic, probabilistic bounds under certain dynamical assumptions and 2) to demonstrate that the problem can also be addressed more flexibly with existing RL methods. For theoretical guarantees, we develop L-UCBFair, an online RL method, and prove sublinear bounds on regret (suboptimiality of cumulative loss) and distortion (suboptimality of cumulative disparity) with high probability (Section 3.1). To demonstrate practical solutions without strong safety guarantees, we apply R-TD3, an adaptation of a well-know deep reinforcement learning method (viz.. TD3) to a time-dependen Lagrangian relaxation of the central problem. We compare L-UCBF Fair and R-T33 to several baselines (Section 3.3), including myopic policies, in interaction with simulated populations initialized with synthetic or real-world data and updated according to evolutionary game theory (Section 4).
Finally, this paper considers fairness in terms of statistical regularities across (ideally) socioculturally meaningful groups. While internal conflict exists between different statistical measures of fairness CCorbett-Davie and Goel, 2018), we show that an RL approach to long-term faimnss can mitigate trade-offs between immediately-fair policy decision outcomes (e.g.. acceptance rate disparities (Dwork et al., 2012; Zemel et al., 2013; Feldman et al., 2015)) and causally- population states (e.g., qualification rate (Raab and Liu, 2021; Zhang et al., 2020)). In particular, we show that our proposed solutions can learn to avoid the familiar trap of pursuing short-term faimess metrics only to widen underlying disparities that demand escalating interventions at the expense of utility (Section 5.2).
1.1 Related Work
Our formulation of long-term faimess bridges recent work on "fairness in machine learning", which has developed in response to the proliferation of data-driven methods in society, and "safe rein- forcement learning", which seeks theoretical safety guarantees in the control of uncertain dynamical systems.
Dynamies of Fairness in Machine Learning We distinguish long-temn meng-term& faimnsss from the dynamics of fair allocation problems (Joseph et al., 2016; Jabbari et al., 2017; Tang et al., 2021; Liu et al., 2017) and emphasize side-effects of algorithmic decisions affecting future decision problems. By formalizing long- term faimess in terms of cumulative losses and disparities, we iterate on a developing research trend that accounts for the dynamical response of a human population to deployed algorithmic prediction: both as singular reaction (Liu et al., 201 8; Hu et al., 2019; Hu and Zhang, 2022) or as a sequence of mutual updates between the population and the algorithm (Coate and Loury, 1993; D' Amour et al., 2020; Zhang et al., 2020; Heidari et al., 2019; Wen et al., 2019; Liu et al., 2020; Hu and Chen, 2018; Mouzannar et al., 2019; Williams and Kolter, 2019; Raab and Liu, 2021).
Several prior works have considered the long-term fairness implications in the context of performative stability or optimality (Perdomo et al., 2020) with known, stateless dynamical transitions: Hu and Zhang (2022) characterize the convergence of systems typified by sequential, myopic policies while Hashimoto et al. (2018) contrast myopie policy with a modified objective satisfying distributional robustness. While Mouzannar et al. (2019) and Raab and Liu (2021) address stateful dynamical transitions, the cited works only treat myopic classifiers that optimize immediate utility (subject to fairness constraints) rather than learning to anticipate dynamical population responses. Finally, while Wen et al. (2019) explore reinforcement learning for long-term fairness, the discussion is limited to a tabular explore-thes then-committtttmmm approach over discrete state and action spaces. This approach does not

---

generalize to continuous spaces, where we provide separate and tighter bounds for both utility and disparity.
Safe Reinforcement Learning L-UCBFair furthers recent efforts in safe RI.. While model-based approaches, in which the algorithm learns explicit dynamical model of the environment, constitute one thread of prior work (Efroni et al., 2020; Singh et al., 2020; Brantley et al., 2020; Zheng and Ratliff, 2020; Kalagarla al., 2021; Liu et al., 2021; Ding et al., 2021), leading algorithms in this domain are characterized by significant time and space complexity. Among model-free algorithms, the unknown dynamics of our setting preclude the use of a simulator that allows algorithms to search over arbitrary state-action pairs (Xu et al., 2021; Ding et al., 2020; Bai et al., 2022).
While Wei et al. (2022) introduce model-free simulator-fre free algorithm, the tabular approach they consider is only applicable to discrete state and action spaces, while our setting requires continuous state and action spaces. To tackle continuous state space, Ding et al. (2021) and Ghosh et al. (2022) consider linear dynamics: Ding et al. (2021) develop a primal-dual algorithm with safe exploration, and Ghosh et al. (2022) use a softmax policy design. Both algorithms are based on the work of Jin et al. (2020), which proposed a least squares value iteration (LSVI) method, using an Upper Confidence Bound (UCB) (Auer et al., 2002) estimate a state-action "Q" function. In addition to continuous state spaces, L-UCBFair also addresses continuous action spaces. To our knowledge, L-UCBFair is the first model-free. simulator-fre RL algorithm to provides theoretical safety guarantees for both discrete and continuous state and action spaces. Moreover, L- L-UCBFairr achieves bounds on regret and distortion as tight as any algorithm thus far on discrete action space (Ghosh et al., 2022).
2 Problem Formulation
We motívate our formulation of long-term faimess with binary classification task, though the general formulation we propose is more widely applicable. Given this initial task, we sequentially incorporate fairness constraints, then population dynamics, and then cumulative loss and disparity, before fully formalizing the central problem of optimizing cumulative loss subject to expected dynamics and constraints on cumulative disparity.
For our initial binary classification task, suppose that a random individual, sampled i.i.d. from a fixed population, has features X E Rd label Y {-1,1}, 1}. and demographic group G E g (where& 9 = [n]] for n 2 2). Denote the joint distribution of these variables in the population as = Pr(X, Y, G) such that X, Y, G ~ s. The task is to predict Y (as Y) from X and G by choosing classifier a, where Y ~ a(X, G), minimize the empirical loss L a) 6.9- E [L((Y, Y),, where L denotes some individual loss such as zero-one-loss. In general, we allow arbitrary, (unit-interval) bounded loss functions ((s a) [0, such that the basic classification task min, (s,,a). a).
The standard, "fair" classification task (without a dynamically responsive population) incorporates constraints on the choice of classifier such that the disparity 2 E [0, 1] induced on distribution by a is bounded by some value c E [0, 1]. Formally, the task is min, ((s a) subject to (s, a) s c. A standard measure of disparity D is the violation of "deoogrpphic parity" (Dwork al., 2012). For
example, when G = {g1. g2). (s, a) e.g.
(9)) L (92) where (g) = Pr(Ý=11 G=g).
In this paper, we also wish to consider measures of fairness inherent to the distribution s (c.g.. parity of group qualification rates Pr(Y=1 G=g)). Such measures of fairness can only be affected by changes to and thus require dynamics, which are not captured by the above formulation (Raab and Liu, 2021: Zhang et al., 2020). We will see that such notions of disparity are well-suited to an RL formulation of long-term fairness.
State, action, and policy Adopting the semantics of sequence of dependent classification tasks, we identify the Lime-dependent distribution s, E S of individuals in the population as a state and the chosen classifier a, E A as an action of some algorithmic agent at time т. While state space S is arbitrary, we assume that action space A admits a Euclidean metric, under which it is closed (i.e., A isomorphic to [0, 11 m E Zzo). We specify that a, is sampled stochastically according to the agent's 's current policy r., that is, a, (+r) Additionally, we assume 8, is fully observable at time T E (1, (..). In practice, 8, must be approximated from finitely many empirical samples, though this caveat introduces well- rell-understood errors that vanish in the limit of infinitely many samples.
3

---

Dynamics Moving beyond the one-shot "fair" classification task above, let us now assume that a population may react classification, inducing the distribution s to change. In practice, such "distribution shift" is a well-known, real-world phenomenon that can increase realized loss and disparity when classifiers are fixed (Chen et al., 2022). For classifiers that free update in response to mutating distribution subsequent classification tasks depend on the (stochastic) predictions made in previous tasks. In our formulation, we assume the existence of dynamical kernel P that maps a state and action at time to distribution over possible states at time T + 1. That is, 8r+1 P(,,, ar).
We stipulate that P may be initially unknown, but we assume that it does not explicitly depend on time and may be reasonably approximated learned "online", While real-world dynamics may depend on information other than the current distribution of cuusificationnsspcciiii exogenous parameters, history, or additional variables of state we have identified the dynamical state 8 with the current, fully-observed distribution for simplicity and tractability.
variables Pr(X, Y, G) e.g.,
Reward and utility, value and quality functions Because the standard RL convention is to maximize reward rather than minimize loss, for an RI. agent, we define the instantaneous reward r(sr,a, == L(r,, 0.) [0, 1] and separate "utility" g(8,, 0,)) 1 [(r, a+) [0. 1], where and g do not explicitly depend on time r. We next propose to optimize anticipated cumulative anticipated cumulative utility. Let the index j represent either reward r or utility g. We use the letter V (for "value") to denote the future expected accumulation of j over steps [h,,.., H. (without min-uiicountting starting from state s, using policy æ. Likewise, denote the "quality" of an action a in initial state with the letter Q. For j E (r.g), we define
reward subject to constraints
H (8) =E ) = : (),((,0) =E Σ [sr. az)) | 8h = 5,
H
Lr=h
Note that and Q marginalize over the stochasticity of state transitions 8 ~ P(8 ar) and the sampling of actions a, ~ (8r).. By the boundedness of and, g. the values of V and Q belong to the interval [0, H- + 1].
"Long-term fairness" via reinforcement learning
The central problem explored in this paper is
max
V
subject to
v.1 (s) 2 ē.
We emphasize that this construction considers finite time horizon of H steps, and we denote the optimal value of as π² We first assume that a solution to the problem exists bounded within the interior of the feasible set (i.e., strict feasibiliy or Slater's condition), as in Efroni et al. (2020), Ding et al. (2021), and Ghosh et al. (2022):
Assumption 2.1 (Slater's Condition). By > 0, म. such that V (s) 2 227%
The Online Setting Given initially unknown dynamics, we formulate long-term fairness for the online setting (in which learning is only possible through actual "live" deployment of policy, rather than through simulation). As it is not possible to unconditionally guarantee constraint satisfaction in Eq. (1) over finite number of online steps, instead measure types of regret: the suboptimality of a policy with respect to cumulative incurred loss, denoted Regret, and the suboptimality of a policy with respect to cumulative induced disparity, denoted denoted Drtn for "distortion".
(e, 81) V (s1) V7 (s1) ; Drtn(m, 81) == max [0, VgA (s1)]
(2)
3 Algorithms and Analysis
We show that it is possible to provide guarantees for long term faimess in the online setting. To do this, we develop L-UCBFair,, the first model-free, simulator-fir algorithm to provide such guarantees with continuous state and action spaces. Specifically, we prove probabilistic, sublinear bounds for regret and distortion under linear MDP assumption (Assumption 3.1) and properly chosen parameters (Appendix I. in the supplementary material). We defer proofs to the supplementary material.

---

3.1 L-UCBFair
Episodic MDP L-UCBFair inherits from family of algorithms that treat an episodic Markov decision process (MDP) Jin et al. (2020). Therefore, we first map the long-term faimess problem to the episodic MDP setting, which we denote MDP(S, A, H, P. P. D). The algorithm runs for K episodes, each consisting of H time steps. At the beginning of each episode, which we index with k, the agent commits to sequence of policies n = (xf, ø.. ...: xH for the next steps. each step within an episode, an action of, E A sampled according to policy ni, then the state $/+1 S is sampled according to the transition kernel P(s), af). of is sampled arbitrarily for each episode.
Because L- L-UBrrair predetermines its policy for entire episode, amend our definitions of regret and distortion over all H K time steps by breaking them into a sum over K episodes of length H:
Episodic Regret
Regret (K)
V
(5 Vi (st)) ; Drtn(K) max Σ
c
Va 9.1
(61)
(3)
The Lagrangian Consider the Lagrangian L associated with Eq. (1), with dual variable 0: C(T,V) == V (s) + 1 (V (8) c)
(4)
L-UCBFair approximately solves the primal problem. max, min, C(T, which is non-trivial, since the objective function is seldom concave in practical parameterizations of т. Let v^ denote the optimal value of v; L-UCBFair assumes bound v² S V given parameter V, as described in the supplementary material (Assumption B.
Φ) is linear MDP with feature map o : A + Rd. That is, for any h, there exist signed measures 2h .. ...,....
Assumption 3.1 (Linear MDP). We assume MDP(S,, A,
over S
and vectors Or g.h E Rdd such that, for any (s, E S AxS,
Ph (s' s, = (ø(s, a), (8));; r(s,a) = (o(s, a), Onn):
g(s,a) = (0(s,)), d).0g.))
Assumption 3.1 addresses the curse dimensionality when state space S is the space of distributions over X, Y, G. This assumption is also used by Jin et al. (2020) and Ghosh et al. (2022), and a similar assumption is made by Ding et al. (2021). This assumption is well-justified continuous time if we Hilbert spaces Brunton et al. (2021), but in practice we require limited
allow for anfnite-dimensionn dimensionality for the codomain of Φ. In our experiments, we use a neural network to estimate fcature map offline which approximately satisfies the linear MDP assumption (Appendix D.
3.1.1 Construction
L-UCBFair, "LSVI-UCB for Fairness" (Algorithm 1) is based Least-Squares Value Iteration with an optimistic Upper-Confidence Bound, as LSVI-UCB Jin et al. (2020), For each H-step episode k, L-UCBFair maintains estimates for Q Q2 and a time-indexed policy œ². In each episode, L-UCBFair updates Q Q5. interacts with the environment, and updates the dual variable vk, which is constant over episode k.
LSVI-UCB Jin et al. (2020) The estimation of Q challenging, as is impossible to iterate over all pairs when S and A are continuous and P is unknown. LSVI parameterizes Q7, a) by the linear form W/. á(s, a), as used by Jin et al. (2020), and updates
Fh (8%, a max Qh+1 (sh+1: a) w oTo(sh ) + +s|lw//
Wr + argmnin
aEA
In addition, a "bonus term" 3 (0 ( 1/2 is added to the estimate of Q in Algorithm to encourage exploration.
Adaptive Search Policy Compared to the works of Ding et al. (2021) and Ghosh et (2022), the major challenge face for long-term faimess is continuous action space A, which renders the
5

---

independent computation of Q Q for each action impossible. To handle this issue, we propose an adaptive search policy: Instead of drawing an action directly from a distribution over continuous values, x represents a distribution over finitely many (M). Voronoi partitions of A. After sampling region with a softmax scheme, the agent draws action a uniformly at random from In addition to defining Voronoi partitioning of the action space for the adaptive search policy of L-UCBFair (in the supplementary material), we make the following smoothness assumption, which we use to bound the error introduced by this sampling method:
Assumption 3.2 (Lipschitz). There exists p > such that (l)(s, (((ssa))) plla a' 1l
Dual Update For L- L-UCBFair, the update method for estimating in Eq. (4) is also essential. Since V (s) and V (s) are unknown, we use v,1 (s) and V (8) to estimate them. An estimate for is iteratively updated by performing gradient ascent in the Lagrangian (Eqq (4)) with step-size subject to the assumed upper bound 7 for (Assumption B.1). A similar method also used in Ding et al. (2021); Ghosh et al. (2022).
3.1.2 Analysis
We next bound the regret and distortion, defined Eq. (3), realizable by L-UCBFair. We then compare L-UCBFair with existing algorithms for discrete action spaces and discuss the importance of the number of regions M and the maximum distance es from any action to the center of its corresponding Voronoi partition.
Theorem 3.3 (Boundedness). With probability 1 there exists constant such that L- UCBFair (Algorithm I) achieves
Regret K) S (bCH&VO (1 (V 1)H) : Drtn(K) S 6C(1 + H2 V
VK,
(5)
for parameter values <=1 El S 20(L+))KWV C = log(log( M AdHK//p) and 3 O(dH
For a detailed proof of Theorem 3.3, refer to Appendix B.1. This theorem indicates that L-UCBFair achieves O H bounds for both regret and distortion with high probability. Compared to the algorithms introduced by Ding al. (2021) and Ghosh et al. (2022), which work with discrete action space, L-UCBFair guarantees the same asymptotic bounds on regret and distortion.
3.2 R-TD3
Because assumptions in Section 3.1 (e.g., the linear MDP assumption) are often violated in the real world, we also consider deep reinforcement learning methods as a flexible alternative. Concretely, we apply Delayeeelayed Deep Deterministic Policy Gradient" (TD3) Fujimoto et al. (2018), with an implementation and default parameters provided by the open-source package "Stable Baselines 3" Raffin et al. (2021), on a Lagrangian relaxation of the long-term faimess problem with time- dependent multipliers for the reward and utility terms (Eq. (6)). We term this specific algorithm for long-term fairness R-TD3. While such methods lack provable safety guarantees, they may still confirm our hypothesis that agents trained via RL can learn to sacrifice short-term utility in order to drive dynamics towards preferable long-term states and explicitly incorporate dynamical control objectives provided as functions of state.
To treat the long-term fairness problem (Eq. (1)) using unconstrained optimization techniques (i.c., methods like TD3), we consider time-dependent Lagrangian relaxation: We train R-TD3 optimize
min E dy (x,
Σ T=1
(1- + +2,
(6)
where 87+1 P(s,, =,
Strictly applied, myopic fairness constraints can lead to undesirable dynamics and equilibria Raab and Liu (2021). 1). Eq. (6) relaxes these constraints (hard - soft) for the near future while emphasizing them
long-term. Thus, we hope to develop classifiers that learn to transition to more favorable equilibria.

---

Algorithm L-UCBFair
Input: A set of points (To, I1... JM satisfy Definition B.2. 6, 2
v==0. Wr. a= log( 201+x+8 7 /ttp///KK..-Ccc Vlog(4 log MdT/p).
for episode ko = 2, .... K do Receive the initial state sf.
for step = H, H - 1, do
AA < k- Φ (5% 07) (7) +s
for j (r,g)
wf,n (A -1 - o (5% a (j (5% 07)
vk sh+1 (5
end for for iteration i = 1,.., .M and index E
{r,g} do
1/2 Sig ((..1,)) (AR) -1 ((.
(2,(, 1.) min (() BEi,
end for
exp(a(@f. ( Qt
SMA,* 1.) Σ, expla @C (51))tu (x
Ta K JUEZIN) (M
(-),()) + SaEA (a(a -0 (1, a)da, (. + Sacd xf(a -00 a)da end for
for step h h =1=1... I.... H do
Compute Qi,h (sh 1i). O (sh, 4)), क (4s sh)
Take action of th (.1 s)) and observe 1ht11
k
end for
Vk+1 max { (mi (ir + n n (a- - Vrh, (s1)) / .0}
end for
3.3 Baselines
We compare L-UCBFair and R-TD3 a greedy agent as proxy for a myopic status quo in which policy is repeatedly determined by optimizing for immediate utility, without regard for the population dynamics. This standard known as "Repeated Risk Minimization" (Perdomo et al., 2020; Hu and Zhang, 2022), and we implement it using simple gradient descent on the different classes of (>-parameterized) objective functions f we consider (Eq. (7)). Having adopted a notion of fairness that relies on "groups", presuppose different groups of agents indexed by g, and denote group- conditioned loss as Lg. The objectives that are approximately minimized for each baseline are
Myopic:
f(x) E [ a)].
(7a)
Myopic-Fair: fx(x)) = F. [1 {) + ()) (0.
(7b)
Maxmin:
f(x) F.
max (Lg(s,
(7c)
Maxmin-Fair: fx(T) E
(1 X) max (Lg(s, x8(s,a) , xE (0,
(7d)
g
The two "Maxmin" objectives are related distributionally robust optimization, which has been previously explored in the context of fairness (Hashimoto et al., 2018), while the two "Myopic" objectives are more straight-forward. While our baselines do not guarantee constraint satisfaction, the two objectives labelled " "-Fair" are nonetheless "constraint aware" in precisely the same way as finm that (probabilistically) incurs penalties for violating constraints.
Simulated Environments
To evaluate the proposed algorithms and baselines, we consider a series of binary (Y E (-1,1)) classification tasks on population of two groups G [g1, 923 modeled according to evolutionary
7

---

game theory (using replicator dynamics, as described in Appendix A. in the supplementary material), We consider two families of distributions of real-valued features for the population: One that is purely synthetic, for which X ~ NY, 1), independent of group G, and one that is based on logistic regressions to real-world data, described in Appendix A.2 (in the supplementary material). Both families of distributions over X are parameterized by the joint distribution Pr(Y, G). RI. agents are trained on episodes length H initialized with randomly sampled states.
In order to better handle continuous state space, we make the following assumption, which has been used simplify similar synthetic environments (Raab and Liu, 2021):
Assumption 4.1 (Well-behaved feature). For the purely synthetic setting, we require X to be a "well-behaved" real-valued feature within each group. That is, for each group Pr(Y=1 G-g, X X-r) strictly increases 2.
As intuitive example of Assumption 4.1, if Y represents qualification for fixed loan and X represents credit-score, we require higher credit scores to imply higher likelihood that an individual is qualified for the loan.
Theorem 4.2 (Threshold Bayes- ooytmalytimality).. For each group when Assumption 4.1 is satisfied, the Bayes-optimal, deterministic binary classifier is a threshold policy described by a feature threshold Og for group g- That is, if Z 0g then Y 1; otherwise, -11.
As result of Theorem 4.2, consider our action space to be the space of group-specific thresholds, and denote an individual action as the vector a == (41, az). Nonetheless, we note that Assumption 4.1 is often violated in practice, is in semi-synthetic setting.
Experimental Results
Do RL agents learn to seek favorable equilibria against short-term utility? Is Lagrangian relaxation Eq. (1) sufficient to encourage this behavior? We give positive demonstrations for both questions.
5.1 Losses and Disparities Considered
Our experiments consider losses L which combine true-positive and true-negative rates, i.e.,
(s, = asp(s, a) Btn(s, a)
r(s, a) atp(s, a) + Btn(s,
(8)
where 3 E [o, 1): a)( = Pr... (V=1 and tn(s,a) a) = (V
For disparity 2, we consider functions of the form (s, a) = (11 (92))l that measure violations of demographic parity (DP) (Dwork et al., 2012), equal opportunity (EOp) (Hardt et al., 2016), equalized odds (EO), and qualification rate parity (QR), described Table 1, We note that QR inconsequential for the baseline agents, which ignore the mutability of the population state.
5.2
Results
Our experiments show that algorithms trained with an RL formulation of long-term faimess can drive reactive population toward states with higher utility and fairness than myopic policies. In Fig. I, the baseline policies (i.e., subfigures (a) and (b)), which focus on short-term incentives drive disparate qualification rates and attain lower long-term utility than the RL agents, indicating that short-term utility is misaligned with desirable dynamics in this example. In subfigure (b) in particular, the baseline policy increasingly violates the static fairness condition with time, agreeing with previous results by Raab and Liu (2021). Meanwhile, the RI. algorithms (subfigures (c) and (d)) learn to drive universally high qualification rates, thus allowing policies that capture higher utility with time (subfigure (c)), Fig. 3.
Func.
DP
PY G-g)
QR
Pr (Y=a |==] G=g)
EOp
Pr.,a (Y =1 -=11G=1)
Pr.. =1 Y
EO
Pr. =1 Y=
Table 1: Disparity Functions, where
( a) = (g.a))))
8

---

a) Maxxdoo- Pair. (tp, DP), A=
b) Myooic- Fair. (tp, DP) x=
L-UCBFairr (sp.
R-T-. (tp.
Grgup 2 Quoliticn Rage
Group Qualification Rate
Group I Qualification Rare
Group Qualification Rate
Group Qualification Rate
(tp.
Maxmin
Moxmin- Myopic
R-T03
0.2
0.6 Episodic Mean Loss
1.0
Figure 1: Using modeled population with scalar features fit to the "Adult" dataset (Dua and Graff, 2017) at each time-step to mirror the evolving qualification rates (Appendix A.2), we compare our baseline algorithms L-UCBFair and R-TD3 on the same maximizing true positive rates (tp) subject to demographic parity (DP). Plots (a-d) depict evolving group qualification rates under each algorithm with streamlines (red arrows indicate the author's emphasis), while shading indicating immediate violations of demographic parity. We remark that the corresponding plots for the mon"-Fair" baselines are qualitatively indistinct and omit them for space. In subplot (e), visualize mean episode loss where #5150 for each algorithm.
initial states with the task of
Our central hypothesis, that long-term faimesss via RL may induce algorithm to sacrifice short-term utility for better long-term outcomes, clearly demonstrated in the purely synthetic environment depicted by subfigures (al-a3) of Fig. 2, in which the environment provides higher immediate utility (true-pot positeoosivve rates) but lower long-term utility when a policy chooses initially high acceptance rates. In this case, the RL algorithm (subfigure (a2)) drives the system towards high qualification rates by giving up immediate utility maximized by the myopic agent (subfigure (al)).
a1) Myopic Fair A=
a2) L-UKBPair (sp,
L-)L-OCBFair (tp, (R)
b2) R-T03 (tp. QR)
Quailin Qualificttion State
Diquantty Doaa ficatio (uta)
Group
Group I Qualifictioon Rate
Group Qualifcation Rate
Group Qualification Rate
Group Qualification Rate
(tp. DP)
b3) (tp. QR)
Myopic-Fair
UCB-Fair
UCB-Fair
R-TD3
0.6
0.6
1.0
0.25
0.50
0.75
1.00
Episodic Mean
Episodic Mean
Figure 2: Subfigures (al-a3) compare baseline policy L-UCBFair in purely synthetic envi- ronment on the task maximizing the fraction of true-positive classifications (tp) subject to bounded demographic parity violation (DP). Episode length in this environment is H = 100. Subfigures (b1- b3) compare L-UCBFair to R-TD3 on a similar task subject to bounded qualification rate disparity instead. In both environments, modeled agent utilities translate higher acceptance rates lower qualification rates. Figures (al, a2) and (b1, b2) depict evolving qualification rates with streamlines (red arrows indicate the autho''s emphasis) and use shading indicate fairness violations.
With subfigures (bl-b3) of Fig. 2, we demonstrate the capability RL to incorporate notions of fairness (e.g.. qualification rate parity QR), that are impossible to formulate in the myopic setting. In subfigures (b1-b3), both RI agents learn to satisfy qualification rate parity by driving the state the population towards equal qualification rates by group

---

Finally, our experiments also show that RL algorithms without theoretical guarantees may be applica- ble long-term fairness. In Fig. subfigure (b2), R-TD3 achieves similar qualitative behavior as L-UCBFair (subfigure (b1)) )), that is, driving high qualification at the expense of short-term utility) while achieving lower episodic mean loss (subfigure (b3)).
0.60
0.38
Epizodic Mean Dispartey
0.20
Epieadic Mean los
0.56
My
0.18
0.54
0.52
0.14
0.50
1000
1500
Iterations
Iterations
Figure 3: The mean episodic loss (left) and disparity (right) within 20-step sliding window obtained by L-UCBFair for the (tp, DP) setting of Fig. 1 (a2). We emphasize that both loss and disparity decrease in time, as required for the sublinear regret and distortion guaranteed by (Theorem 3.3).
(tp + 0.8tn, DP)
204 66 steno z
Rusimu Alee
Accumuabe
Grous'
Group
Group qualiication
(a) TD3, no constraint
(b) R-TD3
(c) TD3, no constraint
(d) R-TD3
Figure 4: Comparison of total accumulated disparity (blue) and loss (orange) over single episode of H 150 steps as functions of initial state (initial qualification rates), for R-TD3 and TD3 (no constraint; À = 0) in the semi-synthetic environment (Adult dataset). This figure indicates that the increasingly weighted fairness term in the objective of R-TD3 play role in more rapidly reducing cumulative disparity, in this case by driving the system towards the line of equal qualification rates, at the cost of increased cumulative loss.
Limitations Despite the potential, highlighted by our experiments, for RL-formulation fairness to drive positive long-term social outcomes, it is not possible to truly validate such approaches without deployment on actual populations, which may be practically and ethically fraught. In addition, violations of fairness or decreased utility may be difficult to justify to affected populations and stakeholders, especially when the bounds provided by L-UCBFair, while as tight as any known, rely on assumptions that may be violated in practice.
Concluding remarks Machine learning techniques are frequently deployed in settings in which affected populations will react to the resulting policy, closing a feedback loop that must be accounted for. In such settings, algorithms that prioritize immediate utility static notions of faimess may yield dynamics that are misaligned with these objectives long-term.
In this paper, we have reformulated long ter-term fairness an online reinforcement learning problem (Eq. (1)) address the importance of dynamics. We have shown that algorithmic solutions this problem (e-g., L.-UBFFair) are capable of simultaneous theoretical guarantees regarding cumulative loss and disparity (violations of fairness). We have also shown that these guarantees can relaxed in practice to accommodate a wider class of RI. algorithms, such as R R-TD3. Finally, we emphasize again that the RL framework of long-term fairness allows notions of disparity inherent to the state of population to be explicitly treated, while such definitions are inoperable in the standard, myopic framework of fairness. We hope that our contributions spur interest in long-term mechanisms and incentive structures for machine learning to be driver of positive social change.
This work is partially supported by the National Science Foundation (NSF) under grants IIS 21 12471, IIS IIS-2040800, and CCF-2023495.
Acknowledgements
10

---

References
Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning primal-dual approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3682-3689, 2022.
Kianté Brantley, Miro Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. Advances in Neurul Information Processing Systems, 33:16315-16326, 2020.
Steven L Brunton, Marko Budišié, Eurika Kaiser, and J Nathan Kutz. Modern koopman theory for dynamical systems. arXiv preprint arXiv:2102.12086 2021.
Allison JB Chaney, Brandon M Stewart, and Barbara E Engelhardt. How algorithmic confounding in recommendation systems increases homogeneity and decreases utility. In Proceedings of the 12th ACM Conference on Recommender Systemx, pages 224-232. ACM, 2018.
Yatong Chen, Reilly Raab, Jialu Wang, and Yang Liu. Fairness transferability subject to bounded distribution shift. arXiv preprint S.KIv:22006001229 2022.
Stephen Coate and Glenn C Loury. Will affirmative-action policies eliminate negative stereotypes? The American Economic Review, pages 2220-1240 1993.
Sam Corbett-Davies and Sharad Goel. The measure and mismeasure of fairness: A critical review of fair machine learning. arXiv preprint arXiv: 1808.0008. 2018
Kate Crawford and Ryan Calo. There is blind spot in Al research. Nature News, 538(7625):311, 2016.
Alexander A'mourr, Hansa Srinivasan, James Atwood, Pallavi Baljekar, D Sculley, and Yoni Halpern. Fairness is not static: Deeper understanding of long term faimess via simulation studies. In Proceedings of the 2020 Conference Fairness, Accountability, and Transparency, pages 525-534, 2020.
Dongsheng Ding, Kaiging Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33:8378 003378-8399. 2020.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang. Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, pages 3304-3312. PMLR, 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:///rrrccii...ccc.. uci. edumml.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-explootaaion in constrained mdps. arXiv preprint 20Xiv:2003.02/89 2020.
Danielle Ensign, Sorelle Friedler, Scott Neville, Carlos Scheidegger, and Suresh Venkatasubrama- nian. Runaway feedback loops in predictive policing, In Conference of Fairness, Accountability, and Transparency, 2018
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Emmanouil Zampetakis. Optimal wwwoooimmttio-smoooneeeeo tradeoffs for soft-max functions. Advances Neural Information Processing Systems, 33:2651-2666 2020.

---

Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. proceedings of the 21th ACM SICKDD international conference on knowledge discovery and data mining, pages 259-268, 2015.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International conference on machine learning, pages 1587-1596. PMLR, 2018.
Andreas Fuster, Paul Goldsmith-Pinkhann Tarun Ramadorai, and Ansgar Walther. Predictably unequal? The effects of machine learning credit markets. The Effects of Machine Learning Credit Markets, 2018.
Amob Ghosh, Xingyu Zhou, and Ness Shroff. Provably efficient model-free constrained rl with linear function approximation. arXiv preprint arXiv:2206.1/855 2022.
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning, 2016.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning. pages 1929-1938. PMLR, 2018.
Hoda Heidari, Vedant Nanda, and Krishna Gummadi. On the long-term impact of algorithmic deci- sion policies: Effort unfairness and feature segregation through social learning, the International Conference on Machine Learning (ICML), 2019.
Lily Hu and Yiling Chen. A short-term intervention for long-term fairness in the labor market. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, pages 1389-1398. International World Wide Web Conferences Steering Committee, 2018.
Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 259-268, 2019.
Yaowei Hu and Lu Zhang. Achieving long-term fairness in sequential decision making. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9549-9557, 2022.
Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in reinforcement learning. In International conference on machine learning, pages 1617-1626.
PMLR, 2017.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, PMLR, 2020.
Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. Fairness in learning: Classic and contextual bandits. Advances in neural information processing systems, 29, 2016.
Krishna C Kalagarla, Rahul Jain, and Pierluigi Nuzzo. A sample-efficient algorithm for episodic finite- horizon mdp with constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8030-8037, 2021.
Lydia T Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt. Delayed impact of fair machine learning. In International Conference on Machine Learning, pages 3150-3158. PMLR, 2018.
Lydia T Liu, Ashia Wilson, Nika Haghtalab, Adam Tauman Kalai, Christian Borgs, and Jennifer Chayes. The disparate equilibria of algorithmic decision making when individuals invest rationally. In Proceedings of the 2020 Conference Fairness, Accountability, and Transparency, pages 381-391, 2020.
Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34:17183-17193, 2021.
12

---

Yang Liu, Goran Radanovic, Christos Dimitrakakis, Debmalya Mandal, and David C Parkes. Cali- brated fairness bandits. arXiv preprint arXiv:1707.0185, 2017.
Hussein Mouzannar, Mesrob Ohannessian, and Nathan Srebro. From fair decision making to social equality. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 359-368. ACM, 2019.
Ling Pan, Qingpeng Cai, Qi Meng, Wei Chen, Longbo Huang, and Tie- Yan Liu. Reinforcement learning with dynamic boltzmann softmax updates. arXiv preprint arXiv: (003v::9003059066 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- gish-pefformance deep learning library. Advances Neural Information Processing Systems 32, pages Curran Associates, Inc., 2019.
Juan Perdomo, Tijana Zrnie, Celestine Mendler-Dünnee, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pages 7599-7609. PMLR, 2020.
Reilly Raab and Yang Liu. Unintended selection: Persistent qualification rate disparities and interventions. Advances in Neural Information Processing Systems, 14:26053-26065 2021.
Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah
Dormann. Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1-8, 2021.
Rahul Singh, Abhishek Gupta, and Ness B Shroff. Learning markov decision processes under constraints. arXiv preprini arXiv:2002. 2tt::2002./223333 /2435, 2020.
Wei Tang, Chien-Ju Ho, and Yang Liu. Bandit learning with delayed impact of actions. Advances in Neural Information Processing Systems, 34:26804-26817, 2021.
Honghao Wei, Xin Liu, and Lei Ying. Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In International Conference Artificial Intelligence and Statistics, pages 3274-3307. PMLR, 2022.
Min Wen, Osbert Bastani, and Ufuk Topcu. Fairness with dynamics. arXiv preprint arXiv:1901.08563 2019.
Joshua Williams and Zico Kolter. Dynamic modeling and equilibria in fair decision making. arXiv preprint 191 1.06837, 2019.
Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 11480-10 (1000-1199 1491. PMLR, 2021.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference on machine learning, pages 325-333. PMLR, 2013.
Xueru Zhang, Ruibo Tu, Yang Liu, Mingyan Liu, Hedvig Kjellström, Kun Zhang, and Cheng Zhang How do fair decisions fare in long-term qualification? arXiv preprint arXiv:2010.11330 2020.
Liyuan Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. Learning for Dynamics and Control, pages 629. PMLR, 2020.
13

---

A Simulated Environments:
Supplementary
A.1 Replicator Dynamics
Our use of replicator dynamics closely mirrors that of Raab and Liu (2021) as an "equitable" model of a population: Individuals my be modeled identically, independently of group membership, yet persistent outcome disparities may emerge from disparate initial conditions between groups. For our experiments, we parameterize the evolving distribution Pr(X, Y G), assuming constant group sizes, in terms of "qualification rates" 4g Pr(Y-1 G=9) and update these qualification rates according to the discrete-time replicator dynamics:
WiB t W [
Og it + = (o(t)
W
Wig + (1 -9g
In this model, the fitness W > O of label Y-y in group G-g may be interpreted as the "average utility to the individual" in group g of possessing label y, and thus relative replication rate of label in group g. as agents update their labels by mimicking the successful strategies of in-group peers. We model Wg in terms of acceptance and rejection rates with a group-independedn utility matrix U:
W
Σ 0E(-1.1)
Un Pr- Y-y. G-9).
We choose the matrix U to eliminate dominant strategies (i.c., when agents universally prefer one label over another, independent of classification), assert that agents always prefer acceptance over rejection, and to imply that the costs of qualification greater than the costs of non-qualification among accepted individuals. While other parameterizations U are valid, this choice of parameters guarantees internal equilibrium of the replicator dynamics for Bayes- classifier and "well- behaved" scalar-valued feature X, such that Pr(Y=1 X=x) is monotonically increasing in x (Raab and Liu, 2021).
A.2 Data Synthesis and Processing
In addition a synthetic distribution, for which we assume X NNYY, 1), independent of G, for all time, we also consider real-world distributions when simulating and comparing algorithms for "long- term fairness". In both cases, as mentioned above, we wish to parameterize distributions in terms of qualification rates 49. As we perform binary classification on discrete groups and scalar-valued features, in addition to parameterizing a distribution in terms of 9g. we desire a scalar-valued feature for each example, rather than the multi-dimensionn features common real-world data.
Our solution use an additional learning step for "preprocessing": Given a static dataset D from which (X', Y, G' is drawn i.i.d., (e.g.. the "Adult Data Set" Dua and Graff (2017)), where G varies over an individual's sex and Y corresponds to whether an individual has more than 50,000 USD in annual income, at each time-step, we train a stochastic binary classifier à, such that Y' a(X', G) with loss that re-weights examples by label value according to 4g. That is, at each time step, we solve:
min
E D.D
w (
where
x w (X',Y,
1 1 2
Pr(Y=11CT) (--r)) Pr(Y=-1
1-
and L is zero-one loss. our experiments, we choose ā according to logistic regression. We interpret Pr(ý'=1) drawn from the learned "preprocessing" function à, as a new, scalar feature value X E R mapped from from higher-dimensional features X'. The threshold policy ultimately operates on X.
Assumption 4.1 is as hard to satisfy in general as solving the Bayes-optimal binary classification task over
features. Nonetheless, we expect Assumption 4.1 to be approximately satisfied by such "preprocessing" pipeline. It is important to note that the behavior introduced by retraining a logistic classifier at each time step can yield very different qualitative behavior when compared to the static, purely synthetic distribution, as the distribution of X conditioned on and G also mutates, and Assumption 4.1 may be violated.
14

---

B Deferred Proofs
Without loss of generality, we assume (|o(s, a)ll < for all (s,a) S x A. and max fll (S)II, [|0x1]) S vd for all h E [H].
Assumption B.1 (Y bound for v*). We define parameter y that is assumed to bound the optimal value of Eq. (4). For and satisfying Slater's Condition (Assumption 2.1),
V (81) - V (81)
H =Y
7
In Assumption B.1, y H/7, upper-bounds the optimal dual variable v² an input to L-UCBFair.
Definition B.2. Given set of distinct actions I = (To. Ims] C A, where A is closed set in Euclidean space, define I {a: ||a 1il2 S ||a 1yll2. vj * i) as the subset of actions closer to I, than to īj. i.e., the Voronoi region corresponding to locus 4, with tie-breaking imposed by the order indices Also define the locus function ı(a) - min; argmin,, ||a 1///2.
Lemma B.3. The Voronoi partitioning described above satisfies I4 nZj = 2, vi + j and U A.
-I I =
Proof. We will begin by proving Z, nZ, 2 for all i + j. To establish this, we will assume the contrary, that there exist indices and j such that nZ, f Ø. Without loss of generality, assume i > j. We will denote an arbitrary action within the interaction of I, and I as a' E A.
Considering that a' I, according to the given Definition B.2, we infer that Ja' 1 la' - 1 (since >> 9). However, this assertion contradicts the fact that a' E Ij. which implies la' 12 S aa' I//2- Therefore, I, II Ø for all i i# j.
We then proof U I = A. Since A is closed set, for any E A, there must be a E (1, ................................ such that da ||e [1 S ||a 1112 ja Vj. If da,i < da,j strictly holds for all j. then I. Otherwise define a set J = {ilda, = da J. then Iy where j' argminjeet j.
M).
Theorem B.4. If the number M of distinct loci or regions partitioning A is sufficiently large, there exists a finite set of loci I such that Va I E M, || Till2 S 61.
Proof. Since A is closed in euclidean space, denote N the dimension, = supa, Supan''E, E.A |la a' 1|2- Define an Orthonormal Basis {e1, E2, ... ,eN]. Randomly choose a point a E A, Set it as lo. then
we form a set of loci / = {To + Σ eT + Σ ckęe; E A, k: E Z, - < k < [T]).
We know that | < 12 N. It's not hard to verify that ||a Lill S f/2" N Va E I, Taken
ej 5 V22" N-1 yields the statement.
B.1 Proof of Theorem 3.3
Theorem 3,3 (Boundedness). With probability there exists a constant such that L- L-UCBFair
(Algorithm 1) achieves
Regret KK) (DCHVV d (V + 1)H)VK : Drtn(K) KC(1 + VH d
VK,
(5)
for parameter values <=1 c 20(+7)K S log(log( (M)JHHK)) and OdH V().
Outline The outline of this proof simulates the proof in Ghosh et al. (2022). For brevity, denote PA V 2 (s, = ExrPP(())),)) Vjh+1 (8') for j = r,g- Then
(s, (rn Fs VTA (s,a)
(9)
(T]((s) = (T((:15)7,,m ()
(10)
(mx(- s). (), (8)))) )) = Σ > (s,),
(11)
aeA
15

---

Similar to Efroni et al. (2020), we establish
Regret(A) K) + #/isstortion K)
K
V (s1) Vr (s1)
Σ (b- g,1 (s1))
41 (s1) + u/ Voj (81) (V/i (s1) + us Vigh (51))
T1
K
K
(V (81) - V (s1)) +
(V..
8.1 (81) - Voll (81))
==1
k=1
2²
11 H²K
211
2
Ta
(12)
Ta is easily bounded if rj. The major task remains bound Ti and T2.
Bound Tj and T2. We have following two lemmas.
Lemma B.5
(Boundedness of Tτ). With probability
p/2, we have Ti S
KH
log( M)
2(1 + H)
M)K and 1, we have dk ). Specifically, if a 2(1Y4H)
Ti S (1 + H) + 2K MecIVKK with probability p/2..
Lemma B.6 (Boundedness of T2). Ghosh et al. (2022) With probability p/2, T2 I O (Iv + 1))+H((VKKKK where Ç = log[lo(( (M)oogMM))HH//))
Lemma B.6 follows the same logic Ghosh et al. (2022), and we delay the proof of Lemma B.5 to Section B.2. Now we ready to proof Theorem 3.3.
Proof. For any E [0, V. with prob. -
Regret(K) () + DDistortion(K)
<T T2 + Ts
< 2 k HKlog M
+2KH Mpc O (1+1))
(13)
2m
2
a
Taking v/ = 0, = VKH2 a
Klog M 21+Y+H); 61 = KH there exist constant b,
Regret(K) < VH VK + 2H 4 - 11) 221 K( +) (
2
< {bCH 2 / 1 + (4 + +1)H) KK V(I)
Taking v = v.n y
log M VKH. 2(1 2
Regret(K) K) + + Distoorion K) < (V + +)HVK (1 7IO (H
Following the idea of Efroni et al. (2020), there exists a policy T' such that V. Σk V. By the occupancy measure, Vi and V are linear in oceu-
IE VT,, Vx + pancy measure induced by ग. Thus, the average of K occupancy measure also produces an occupancy measure which induces policy n' and Vax' and 9.1-
We take 0 when EK (b Vig (st) < 0.
16

---

otherwise v = V Hence, we have
VI (01) T (51) max ((c
Σ
V (81)
-V,i (51) - V (s1) + V max (c- Vari (s1),0)
y +1
K HVK - V + 0 (H(SVØK)
$
(14)
K
Since y 21//,, and using the result of Lemma B.15, we have
1 K
y + Ky 0 (HR(V
max (c-
V (5f)
=
K
In this section we proof Lemma B.5 and Lemma B.6.
B.2 Prepare for Lemma B.5
In order to bound TI and T2, we introduce the following lemma.
Lemma B.7. There exists constant B2 such that for any fixed p (0, 1). with probability at least
1 - p/2, the following event holds
k-1
Σ
Vitutz (sh+1) PA P 3.++1 (5% ah) ((xt)-+ S B2dHq
for j {r.g), where q = log [4 (B1 + 1) log(M)dTT/p) for some constant B1.
We delay the proof of Lemma B.7 Appendix B.4.
Lemma B.7 shows the bound of estimated value function V.k and value function ViJ corresponding j.h in given policy k. We now introcuce the following lemma appeared in Ghosh al. (2022). This lemma bounds the difference between the value function without bonus in L-UCBFair and the true value function of any policy æ. This is bounded using their expected difference next step, plus eтror term.
Lemma B.8. Ghosh et al. (2022) There exists an absolute constant 3 = CidH = log(log( (ag(log(M)Adti) M)ATT /p), and for any fixed policy n, for the event defined in Lemma B.7, have
(d(s,a), wiin) Q7 (8. = Pr, (V
Vih++i) (8,0) + (s,
for some Di a) that satisfies | a) s 3 ols a)T (At) ((s,a).
Lemma B.9. Ghosh et al. (2022) With probability least 1 - p/2, (for the event defined in Lemma B.7)
(s.a + 17 +
& (s, + Vx (s, ( Ph, (V VTTH (s, a)
We also introduce the following lemma. This lemma bound the value function by taking L- L-UCrrair policy and greedy policy.
Lemma B.10. Define Vi(()) = maxa (Qta((a)= + Q (.a) the value function corresponding greedy policy, have
log M
dk
(s)( - v/)ss)
+ 2(1 1)
(15)
17

---

Proof.
Define ag the solution of greedy policy,
V (+) (s) = [ (s, 0g) + n n (,)
(16)
-fTTAA 8) (s, (s, + 1 (s, da
(17)
(8, + n (8)
(18)
dk
E SMa x)) (1, (z, 1t) un Og 1i)] + + perp
(19)
5
log E. exp (appa(( (a(0 + (
(20)
a
dk
Σ SMa (8) [0t [.) un [3]] + + H)
(21)
log(M) + 2(1 + Pell
dk
(22)
The first inequality follows from Lemma B. and the second inequality holds because of Proposition 1 in Pan et al. (2019).
B.3 Proof of Lemma B.5
Now we're ready to proof Lemma B.5.
Proof. This proof simulates Lemma 3 in Ghosh et al. (2022).
We use induction to proof this lemma. At step H, we have Q 21. = 0 = Qj,--1 by definition. Under the event in Lemma B. and using Lemma B.8, we have for j = r.9.
(o(s, a), w (s - (. 8Vo(s, (A ((s, a)
Thus (s, a) min (o(s.)), w).)) + B ((s,a) (1 (A+)
( (s, H Qh (s)
From the definition of V/
(+) max ( + vx 1 2 Σ त(a x)) (s, + HT a)] V77 (s)
for any policy Thus, it also holds for n²" the optimal policy. Using Lemma B.10 can get
log M
dk
V Me (s) V (s) <
+ + + H)
Now, suppose that is true till the step h + and consider the step h. Since, it is true till step 1, thus, for any policy
Vitt)) (s, < <H h)( log M + +
dk
PA (VTt
+
From (27) Lemma 10 and the above result, we have for any (8,
( < (s, C (s. h)( log M
dk
+ +2(1 + x PET
a
Hence,
VT (s) < (3) (H h)( log M
dk
+ 2(1 + V) H
-
18

---

Now, again from Lemma 11, we have (s) - Vi (s) - [og(1-41) Thus.
V (8) - (s) - (1 h 1)( log M
dk
+ +
Now, since is true for any poliey n, it will be true for x² From the definition of V have
V. (8) + V (()))))))) - (V (+) + in v (+)) S (H + 1)( log M
+ 2(1 + Y H pEr
a Hence, the result follows by summing over K and considering h = 1.
B.4 Proof' of Lemma B.7
We first define some useful sets. Let 2, =
((),a) -0)
min (w) (, 11 a AEA}
be the set of Q functions, where j E {r. gr. Since the minimum eigen value of no smaller than one the Frobenius norm of A is bounded.
Let V- = (V, V.(+) = - T(a 1,)as(, a))a; Q E 2r, E Eg, v E (0, 21} be the set of Q func- tions, where {r.g). Define
Va E A, 1(a 1.)
SMa ((:((1((())+ Q E 2r Qg. 10, 10.m
JnEI(a;" db
the set of policies.
It's easy to verify V E V/-
Then we introduce the proof of Lemma B.7. To proof Lemma B.7, we need the e-covering number for the set of value funetions(Lemma 1.1hsh et al. (2022)). To achieve this, we need to show if two Q functions and the dual variable v are close, then the bound of policy and value function can be derived(Lemma B.11, Lemma B.12). Though the proof of Lemma B. I and Lemma B.12 are different from Ghosh et al. (2022), we show the results remain the same, thus Lemma B. B.13 still holds. We 'l only introduce Lemma B.13 and omit the proof.
We now proof Lemma B.11.
Lemma B.11. Let be the policy of L UCBFair corressodinng Q Qg. ie.
x[a 1) 1
SMa
(23)
(NEI(A) db
and
#(a 1-) SEEZ(O) db SM. (
=())(
(24)
if 00 -2
Q36 s é' and v i1 s é, then ISaa (I(a | x) - #(a [=) da s 2ac + V + H).
Proof.
(अ(a x) - #(a 2)) da
(25)
Σ
(T([(a) (m) =(((a) x:) da
JaEz
M
db (T x) -5 (1)
BEE;
22a ((a)) ((a)aa(()+(pppff +vQ((, -0)
(26)
19

---

The last inequaity holds because of Theorem 4.4 in Epasto et al. (2020). Using Corollary B.17, we have
[ z) 7(a x)) da 2ac' + y + H)
(27)
Now since have Lemma B.11, further bound the value functions.
Lemma B.12. 1 - 0g - c', where Q3 E 2. then there exists V₂ E V; such that
Via - Vi s H2ae' (1 + H)+
Proof. For any x,
V (8) (+)
L M(a 8) 5) a)da
5(a s))
J. T(a s) (s, a)da J. x(a s) a)da + /. z(a
T(a (s;
< T(a 8) (s, - a)) da + +l[ s)Q a)da - t(a s)
(,(,,
S é' + H (I(a s) - #(a $)) da
S é' + H2ad' (1 + y + H)
Using Lemmas above, we can have the same result presented in Lemma 13 of Ghosh et al. (2022) as following.
Lemma B.13. Ghosh et al. (2022) There exists a V3 Vj parameterized by (iū,,, wg B, B.A. v) such
that dist Vvg, V3) where
V3 V3 = sup Vy(8) v.()))
Let N be the c-covering number for the set Vj. then,
log NY < dllo (1 1+8H
Vdk Vse
[ 1 8d222/// (s(e))) + log (1+ 2)
+ d2 & log
where c' H2a(1+Y+H)44
Lemma B.14. (8, - (s,
2 dK
Proof.
(O. ((s.) o(s, Slwws () o(s (a))
(28)
(29)
(30)
(31)
From Lemma B.16 and Assumption 3.2 get the result.
20

---

B.5 Prior Results
Lemma B.15. Ding et al. (2021) Let v² be the optimal dual variable, and C 2v", then,
V (s1)
V (s1) + +C CClc
cc-
V 9.1 (8i)) S 6,
have
28
c- ge (x1) S
C
Lemma B.16. Jin et al. (2020) For any (k, h), the weight wř,n, satisfies
| S2H 22H
Corollary B.17. If cist (o.. 2.) s dist (og. Qs) s é', and İix - -vxl S e', then, dist (Q+ + Px Q + +n) s <'((1 + y + H).
21

---

C
Additional Figures
a, ~ (s,))
14
Sr+1
8,+1 a(),
Figure 5: The interaction of an algorithmic classifier and a reactive population. Given state 87, the classifier uses policy select action a,, The population, in state Sy, reacts to a, transitioning state to 8,+1, then the process repeats.
Prix-x(C-9t (Dersay)
0.6
0.4
0.2
0.8
1.0
0.0
0.4 0.8
Figure 6: A synthetic distribution is updated according to a dynamical kernel P based on evolutionary dynamics (Appendix A.1), when classifier repeatedly predicts Y=1 iff X 2 0.5. We visualize how the distribution of X and conditional qualification rates Pr(Y=1 X) change in each group E {1 (red, solid), 2 (blue, dashed)). fading the plotted lines over 10 time steps. In this example, the feature values X in each group decrease with time, while the qualification rates of agents at any fixed value of X decrease.
22

---

D Experiments
D.1 Experiment Details
Device and Packages. We run all the experiment on single 1080Ti GPU. We implement the R-TD3 agent using StableBaseline3 (Raffin al., 2021). The neural network is implemented using Pytorch (Paszke et al., 2019). Figures were generated using code included in the supplementary material in less than 24 hours on a single Nvidia RTX A5000.
Using a Neural Network to Learn 6. We use a multi-layer perceptron to learn Φ. Specifically, we sample 100000 data points using random policy, storing s, a, r and g. The inputs of the network state and action, passing through fully connected (fe) layers with size 256, 128, 64, 64. ReLU is used activation function between fc layers, while SoftMax layer is applied after the last fe layer. We treat the outcome of this network as ø. To learn o, we apply two separated fo layers (without bias) with size 1 to é and treat the outputs as predicted r and predicted g. A combination of MSE losses of r and g are adopted. We use Adam the optimizer. Weight decay is set le-4 and learning rate is set to 1e-3, while batch size is 128.
Note that, ò linear regarding r and g. but the linearity of transition kernel cannot captured using such schema. Therefore, equivalently made assumption that there always exists measure M4 such that for given é, the linearity of transition kernel holds. It's stronger assumption than Assumption 3.1.
23

---

D.2 Maximize True-Positives; Synthetic Data
Demographic Parity
Equal Opportunity
Equalized Odds
(A = 2)
1.101
(A = +)
1000
Derrographic Partity
Soual Depertuniy
Equaltted diliileed
UCEFair
trained
steps.
33
2.3
53
Derrggraphic Partiyy
Soual Depertondy
Coral do affocsto 191
Equakied DEES
Oouner www.e www.uuuaannaaamm
d) BD- trained 200,000
stops
G9.6 Sww.ooorrr AMS.
9.2
04
Eploodie Mean Loss
1.00
Egisadic Mean Loss
1.00
Epoodde Mean Loss
0.75
0.75
R-TDS 2e wh
R:TDa es (1.4 4
8.50
0.50
0.50
Episedic
Loss (Over 100 steps)
25
0.25
Myople Fair
Noomin aar
Mysplo-Fai
UCS-Fair
Moamin
UCB
Myopic
UCB-
Table 2: A comparison of baseline and RL policies in purely synthetic environment with the objective of maximizing the cumulative true positive fraction binary classification task (Section 4), subject to three fairness constraints (Section 5.1) (columns). In all cases, the baseline, greedy policies drive the system (indicated by streamlines) to promote low qualification rates in each group (lower left corner of each plot), while the RI agents are able to drive the system to more favorable equilibria characterized by higher qualification rates (upper right). Shading represents local (noncumulative) violations of fairness.
24

---

D.3 Maximize True-Positives; "Adult" Data
Demographic Parity
Equal Opportunity
Equalized Odds
al Myopie Fair 5)
Marmin-Fair +)
Pensscurna Rotls
Soual Depertunkt
L-BORPair trained
2,000
stope.
Canegraztic
Fiu.al Deppenerryyy
Gror2 wow.amaeeon aon mit
8-733
200,000
stegs
Group qualiiictioo
011
03
05
00
Epleodic Mean Loss
Epizadle Mean Loss
Eploode Mean Loss
0.8
0.75
Ba
0.5
0.50
4 ft
Episodic Meun steps)
0.25
R-TD3 wg
Myoopc Far
UCB Far
R-TDS
Myupie Fair
Moxmin fair
R:TD9
Moomin- Fair
UCB-Faiir
Moonn
UCB-
Myop
Table 3: A comparison of baseline and RL policies in semi-synthetic environment incorporating data synthesized from the UCI "Adult Data Set" (Dua and Graff, 2017), as detailed section Appendix A.2. Policies share the objective of maximizing the cumulative true positive fraction of binary classifications (Section 4), subject to three fairness constraints (Section 5.1) (columns). The qualitative difference between the synthetic environment (Table and this, modified environment can be largely explained by the fact that (rxY==[X=x)) not actually monotonically increasing in x, as stipulated by Assumption 4.1. (Appendix A.2)
25

---

D.4 Maximize True-Positives +0.8 True-Negatives; Synthetic Data
Demographic Parity
Equal Opportunity
Equalized Odds
Myoric-Fair 2)
b) Maxmin Fair
(A = $
100
Deroggrathle Hurtey
Foual Deppnrsally
Caral afficction 191
Equakived DEIS
Manee www.uueeeeeettttt
a) R-TOS trained for 200,000 steps
6988 aalloorr 19s.
2.
Epeodie Mean cos
Metaggete
Eppodie Mean oss
Eplaodi Mean Loss
24
8.4
R-TD3 4-
e) Frisodii
Loss (Over 100 steps)
Myopic-Far
Masmin--aa Fair
R-TD3
Myapic-Far
Myoplc-Far
Table 4: comparison of baseline and R-TD3 policies in a purely synthetic environment with the objective of maximizing a weighted combination of the cumulative true positive and true negative fractions of binary classification task (Section 4), subject three fairness constraints (Section 5.1) (columns). In all cases, the baseline, greedy policies drive the system (indicated by streamlines) to I-dimensional manifold the space group qualification rates that is bounded away from universal qualification (upper right corner of each plot), while the RL agents are generally able to drive the system closer to this favorable equilibrium. Shading represents local violations of fairness.
26

---

D.5 Maximize True-Positives +0.8 True-Negatives; "Adult" Data
Demographic Parity
Equal Opportunity
Equalized Odds
Myoric-Fair 2)
Rumar wrt
b) Maxmin Fair 5)
Oreg
croup 2 qualniction rate
trained for 200,000
Group qualfication rabe
Gru3 199
Eploadle Mean Losa
Epiondic Mean Loss
Epleodie Meen Lose
0.4
2.4
00.3
0.3
0.2
Episodic Loss (Uver 150 steps)
2.
Mpople
Massins Fiir
R-TD3
Myosie
Maumins
Myople
Table comparison baseline and R-TD3 policies in a semi-synthetic environment incorporating data synthesized from the UCI "Adult Data Ser" (Dua and Graff, 2017), as detailed in Appendix A.2. Policies share the objective maximizing a weighted combination the cumulative true positive and true negative fractions of binary classification task (Section 4), subject to three faimess constraints (Section 5.1) (columns). This figure indicates a negative result, in which the R-TD3 algorithm does not offer clear benefits over the baseline policies. As noted in the main text, there are theoretical guarantees for the DDT algorithm, and the possibility of such negative results constitute risk for real-world deployments.
27

---

D.6 Training Curves: L-UrBFair
D.6.1
0.50
0.20
0.38
0.34
0.54
0.32
0.32
0.50
302
1.00
3500
2000
530
1838
3300
2030
562
3003
1200
2300
2.12
0:30
16
0.30
31.00
2000
1062
2000
Fonadara
Hansdora
Saratoza
(a) Demographic Parity
(b) Equal Opportunity
(c) Equalized Odds
Figure L-UCBFair 20-step sliding mean & std for the setting in Table 2.
0.37
0.35
2..24
11
0.32
0.30
20.00
0:32
0.29
Eoritern
-0:33
6030
0.332
8322
0.22
M
5 Mv MA
To 0230
0000
En
0015
Beralaae
Iterabore
(a) Demographic Parity
(b) Equal Opportunity
(c) Equalized Odds
Figure 8: L-UCBFair 20-step sliding mean & std for the setting in Table 3.
D.7 Training Curves: R-TD3
0.583
3.25
0445
23
0:43
My
0.42
0402
1
0.75
4225
0.22
15002000
100
Seralora
Larsters
0.00
Aourdatad Dipartyy
20.05
Negh Daan--aaattt
1.00
0.00
30.33
25c
haratone
(a) Demographic Parity
(b) Equal Opportunity
(c) Equalized Odds
Figure 9: R-TD3 100-step sliding mean & std for the setting in Table 3.
28

---

20.34
0.30
3.22
0.23
0.30
dh
00:30
0.2
2.20
0.2
Forration
0.34
0::0
0.25
0.00
0.04
0:00
0.22
236
30c
75c 303
233
1308
275
23L
55t
75k
3000 3356
130K
1736 2016
50k. 25c
T3h 3008 13SK 1.00 3756 2009
(a) Demographic Parity
(b) Equal Opportunity
(c) Equalized Odds
Figure 10: R-TD3 100-step sliding mean & std for the setting in Table 5.
29

---

D.8 Reduction of Utility
Group 2 qualification rate
Reduction of Utility
0.7
0.5
0.3
0.1
0.1
0.3
0.5
0.7
0.9
Group 1 qualification rate
Figure 11: This figure depicts the short-term impact utility of the UCBFair algorithm compared to the greedy, myopic agent that operates without fairness constraints. In this experiment, both algorithms were designed optimize the fraction of true-positive classifications, but only UCBFair was subject to the additional constraint of demographic parity. As the results indicate, the UCBFair algorithm experiences reduction in utility compared to the greedy baseline, but is able drive the system towards state that is preferable in the long term.
30


Reviews:
[{"review_id": "QAF3KRziAp", "reviewer": "Reviewer_nDcm", "summary": "The paper demonstrates that reinforcement learning algorithms can be used to satisfy long term fairness constraints in dynamic environments in which a classifier and population interact while finding high-value equilibria. \n\nThe main approach is to treat the problem as a constrained optimization and optimize the Lagrangian function. The authors use a linear UCB-style algorithm to obtain provable regret bounds on both the cumulative value and constraint violations and demonstrate effectiveness of that algorithm and a less-principled-but-still-practical RL alternative using small simulation studies.\n\nAdapting previous work to the interacting classifier population setting requires handling a continuous action space (setting per-group classifier thresholds) - which the authors handle by showing the continuous action space in this setting can be searched in a discretized manner without losing guarantees.\n\nThe simulation experiments demonstrate that the RL approaches can find good operating points where more myopic policies can end up exacerbating qualification rate disparities.\n", "questions": "1. The shading in figures 1a-d suggests that the demographic parity violation can be mapped to the same state space as qualification parity? Is that really true? For any pair x,y on those plots is there a unique value for the demographic parity violation?\n\n2. How would a purely RL-based long-term reward maximizing agent perform as a baseline (with no fairness constraints)? I would think it might also drive the qualification rates up to the top-right of figures 1a-d, in which case can we be sure it’s the fairness constraints that are actually doing the work here and not just the long-term reward optimization in general?\n", "limitations": "Authors addressed the limitations of their experimental setup with synthetic environments. They might also consider discussing what types of societal inequalities can and cannot be addressed by fairness-in-decision-making style constraints.\n\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Significance & Originality: The authors address an important question: How to design decision-making algorithms for dynamic settings where the underlying dynamics are not well known and the designers want to be both fair and encourage positive societal outcomes overall.\n\nAdding fairness considerations to an RL algorithm with a suitably specified reward function is not a groundbreaking idea, but this work offers a concrete algorithm and practical model-free approach for this question that (as far as I can tell) thus far have not been proposed. \n\nClarity: Paper is very clear and easy to read up to the experiments, setting and notation are clear, as well as the paper’s goals and contributions. \n", "weaknesses": "I found the experiments to be a little bit unclear  in terms of what was being demonstrated with each figure / experiment. What is the role of the fully synthetic vs semi-synthetic experiments? I think the paper could be improved with a clearer exposition of the takeaways from each experiment.\n\nThe authors note that real-world experiments would be necessary to really assess impact of this algorithm. I strongly agree with this sentiment and while I understand that truly real-world experiments can be hard to find, the authors could potentially test across a range of dynamic synthetic environments to give a better sense of the generalizability of the proposed approach.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review, your constructive feedback, and your comments.\n\n### Weaknesses\n\n> I found the experiments to be a little bit unclear…\n\nWe will incorporate more succinct takeaways from the experiments in revision.\n\n*What was demonstrated:* Our experiments seek to confirm our central hypothesis: algorithms for long-term fairness may sacrifice short-term incentives for long-term benefits by driving the system to desirable equilibria. More specifically, *in contrast to myopic algorithms, our algorithms are more consistent in achieving desirable states, less fairness violations in equilibrium, and lower mean loss.* We show this with three types of graphical results:\n\n1. The first, exemplified by Fig 1 (a-d) show the state transitions (i.e., between group qualification rates, which are the x and y axes) driven by different algorithms. Streamlines indicate the next state the corresponding algorithm drives the qualification rates of the two groups to. In these figures, the upper-right corner of the depicted state space, corresponding to higher qualification rates for both groups, is more desirable. Color indicates the degree to which the policy violates fairness in each state, such that lighter color is more desirable (lower fairness violations). \n2. The second type of graph, exemplified by Fig 1 (e), compares the mean loss sustained by different algorithms during deployment. In general, lower mean loss is possible only when the algorithm succeeds in first achieving a more desirable state.\n3. The third, exemplified by Fig 3, shows how mean episodic loss and disparity evolve in time; That these quantities decrease in time validates our claim that L-UCB Fair achieves sublinear regrets.\n\nWe provide many additional experiments in the supplementary material.\n\n*Synthetic vs semi-synthetic settings:* In general, it is difficult to model population response and distribution shift, and models must strive for verisimilitude while remaining interpretable. The synthetic setting provides an idealized setting in which to evaluate our algorithms, while the semi-synthetic setting adds additional real-world complications and serves as a more robust test of our claims, given that we are unable to ethically or realistically deploy our algorithms on real-world populations.\n\n> …the authors could potentially test across a range of dynamic synthetic environments to give a better sense of the generalizability of the proposed approach.\n\nThis is  non-trivial and an active area of ongoing research: We are unaware of existing implementations of synthetic environments that model policy-induced distribution shifts and combine continuous state and action spaces. While off-the-shelf synthetic environments (e.g., for continuous control) exist for reinforcement learning in general, for our setting, which combines fairness and distribution shift, it remains an open research question how to appropriately model how human populations respond to algorithmic policies.\n\n### Questions\n\n> …the demographic parity violation can be mapped to the same state space as qualification parity? ...For any pair x,y on those plots is there a unique value for the demographic parity violation?\n\nThis mapping from state to disparity is induced by the policy: Because the policy maps state to action, and disparity is a function of state and action jointly, each policy induces a mapping from state to disparity. The mapping is one-way however: it is not true in general that each state will result in a unique value of disparity.\n\n> How would a purely RL-based long-term reward maximizing agent perform as a baseline (with no fairness constraints)? … can we be sure it’s the fairness constraints that are actually doing the work here and not just the long-term reward optimization in general?\n\nPlease find the results of running TD3 on (i.e., R-TD3 with lambda fixed to 0) in the rebuttal PDF. In general, it is true that long-term utility may be aligned with fairness, but it is possible that long-term utility alone may work against long-term fairness, in which case the schedule of ever increasing $\\lambda$ is important. For a high-level example, consider college admissions, for which only a finite number of applicants can be admitted. When one “elite” group is privileged to be objectively better prepared for a college’s target curriculum, it is easy to imagine how long-term utility measured only by post-admission success rates would exclude disadvantaged groups, absent fairness interventions.\n\nIn either case, the point remains that myopically “fair” baselines can do active harm, while our formulation of long-term fairness addresses both cumulative utility *and* cumulative fairness violations. Moreover, ours is the first work we are aware of that addresses long-term utility subject to policy-driven distribution shift in human populations that we are aware of.\n\n### Limitations\n\n> Authors … might also consider discussing what types of societal inequalities can and cannot be addressed by fairness-in-decision-making style constraints.\n\nAn inherent strength of our formulation lies in its broad generality: Any real-valued function of state (i.e., distribution) and action (i.e., policy), jointly, is a valid measure of fairness in our work, though L-UCBFair assumes that there exists some (possibly high, but finite dimensional) space for which the measure can be represented as a linear map (Assumption 3.1), and R-TD3 similarly requires that the map is (implicitly) “learnable” by the chosen architecture.\n\nNonetheless, we share the concern that some socially consequential settings are too sensitive to risk to online learning algorithms: Stochastic sampling and exploration may create irreparable or intolerable harm. This is what we mean when we say in the paragraph “Limitations” (line 309) that “violations of fairness or decreased utility may be difficult to justify to affected populations and stakeholders”."}, {"review_id": "XGh5WQB6Lt", "reviewer": "Reviewer_oXaL", "summary": "This paper introduces a new method to ensure long-term fairness in reinforcement learning. The method is compatible with different utility measures (e.g., the accuracy of the classifier when the goal is to predict a label) and different fairness constraints (e.g., demographic parity or equal opportunity). The method is an online reinforcement learning method, so the agent has to interact with its environment in order to improve the quality of the policy, either in the real world or in simulation. The authors introduce two measures of regret, one related to the primary utility goal and one related to the fairness measure, and present an upper bound for both regrets achieved by the proposed algorithm. The paper presents empirical results using a mixture of synthetic and real data.", "questions": "- Could the authors please provide some motivating examples for when an online RL method would be useful/applicable, considering the fact that the policy is updated while being deployed and the regret bounds are only for the final distortion and not the disparity at each timestep (possibly causing intermediate policies to be unfair)?\n- The color scheme in Figure 1 is slightly unclear. The range for the demographic disparity in the first two plots is between zero and 0.005 or zero and 0.07 (a very small interval), but for the proposed method results it is between zero and 1. This makes it harder to compare the fairness measures. Could the authors please clarify this?\n- Why did the authors select only the Myopic-fair baseline for the second experiment? From the first experiment, it seemed like this wasn’t one of the most competitive baselines, so it would be interesting to see how the other baselines perform in this second scenario as well.", "limitations": "The authors discuss the limitations of the work. No major concerns.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- This paper tackles the very important problem of ensuring fairness in a sequential decision-making setting. It uses insights from the - reinforcement learning literature to solve a supervised learning fairness problem.\n- The proposed method extends existing ones to the continuous setting (i.e., continuous states—e.g., attributes—and continuous actions).\n- The paper is very thorough with the mathematical formulation, assumptions, and definitions necessary to fully describe the method.", "weaknesses": "- The proposed method is an online RL method, where the learning process occurs while the policy is applied. This is often not realistic in scenarios where we would like to ensure fairness, as intermediate policies could lead to unfair behavior.\n- My understanding is that the proposed method is an extension of the method presented by Ghosh et al. (2022) for the continuous setting, where the method itself is fairly similar, and the main new contribution is showing that it is possible to achieve the same bound in this new setting. I believe that this could be better clarified in the paper to highlight the novelty of this work more clearly.\n- In the introduction, the authors state that the primary contribution of this work is to consider the problem of long-term fairness as a reinforcement learning problem subject to a constraint. However, previous works have already considered this setting (e.g., the method on which the present work is based).\n- I believe the experiments with R-TD3 are not strongly supporting the argument that an algorithm without theoretical guarantees can still be used for long-term fairness. Applying the method in just two scenarios does not present enough empirical evidence to support the claim that the final policy is still fair, and without any theoretical guarantees, this is essential.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review. We hope that our rebuttal satisfactorily addresses the perceived weaknesses of the submission and questions you have.\n\n### Weaknesses\n\n> The proposed method is an online RL method… intermediate policies could lead to unfair behavior.\n\nUnfortunately, there is likely a greater cost to attempting to learn to model the behavior of human populations in response to currently deployed (and potentially naive) algorithmic policies offline (and off-policy), while currently deployed algorithmic policies do not adaptively attempt to control for fairness. In addition, such a model might differ when we change the hypothesis space of the models, or the application contexts, and probably will change when the external environment for how human users interact with the models changes. \n\nUltimately, if we simultaneously wish to \n* learn to model the how human populations respond to deployed policy,\n* respect fairness,\nand do so in a context-free and data-driven way. Then we fundamentally have an online reinforcement learning problem. \n\nThe real-world use of ML is already online: live experiments (intentional or not) are being run on human populations using current ML policies. It is difficult to maintain the position that we should not be seeking to learn from these live experiments and systematically adapting our algorithms.\n\nIn addition, we point out that short-term violations of “fairness” may be necessary, in certain settings, to drive the system towards desirable equilibria. Our formulation of long-term fairness takes the approach of constraining cumulative violations of fairness.\n\n> My understanding is that the proposed method is an extension of the method presented by Ghosh et al. (2022) for the continuous setting… the main new contribution is showing that it is possible to achieve the same bound in this new setting. I believe that this could be better clarified…\n\nThis understanding is correct; we will adopt this recommendation. While the proof sketch inherits from prior work, the details are novel.  Specifically, as Ghosh et. al. treat a discrete action space, their proof techniques (such as their value function bound, action-value function bound, softmax policy bound, etc.) are not applicable in a continuous setting, and neither is their regret bound (Lemmas 3, 8, 9, 11, 13, 15, 16 of Ghosh et. al.). We solve these issues with the following results:\n\n1. In Lemma B.10, we derive a distinct bound for the difference between $\\bar{V}{h}^{k}(s)$ and $V{h}^{k}(s)$.\n2. In Lemma B.11, we present novel bounds for softmax policies based on different action-value functions and dual variables.\n3. Lemma B.12 provides insights into the disparity of $\\left|V_{j}^{k} - \\widetilde{V}_{j}\\right|$.\n4. We analyze the distinction between $|Q^{k}{j,h}(s, a) - Q^{k}{j,h}(s, I(a))|$ in Lemma B.16.\n\nThe proofs of Lemma B.5, B.7, and Theorem 3.3, likewise, exhibit technical novelty.\n\n> …the authors state that the primary contribution of this work is to consider the problem of long-term fairness as a reinforcement learning problem subject to a constraint. However, previous works have already considered this setting (e.g., the method on which the present work is based).\n\n1. No prior work, to our knowledge, has applied reinforcement learning subject to constraint to the domain of algorithmic fairness, as discussed in Section 1.1 (Dynamics of Fairness in Machine Learning). One of our primary contributions is this formulation and framing of algorithmic fairness.\n2. Formulating realistic settings for algorithmic fairness presents unique challenges (eg. continuous action spaces) which we address for the first time. No prior model-free constrained MDP for continuous action spaces has been theoretically equipped with regret and distortion bounds. \n\n> I believe the experiments with R-TD3 are not strongly supporting the argument that an algorithm without theoretical guarantees can still be used for long-term fairness. … just two scenarios does not present enough empirical evidence to support the claim that the final policy is still fair, and without any theoretical guarantees, this is essential.\n\nThis belief is welcome, and we agree. We are not making the argument that this *specific* algorithm should be used for long-term fairness. Rather, we are claiming that the possibility still exists for a tradeoff between tractability and theoretical guarantees to be exploited, and anticipate additional future work in this direction. In particular, as pointed out in response to Reviewer kVGy, there is ample opportunity for future work to use model-based reinforcement learning or methods from data-driven control when knowledge of transition dynamics is given.\n\n### Questions\n\n> Could the authors please provide some motivating examples for when an online RL method would be useful/applicable, considering … [the approach may cause] intermediate policies to be unfair?\n\nOur regret bounds apply to cumulative suboptimality. As such, the violation of fairness and increased loss at early stages may in fact be necessary, as short-term incentives and long-term benefit may be misaligned in practice (such that myopic policies may steer the system toward undesirable equilibria, as in Fig 1 (b)). This aspect of our work is highlighted in the introduction and further demonstrated in experiments: To guide the system towards more desirable equilibria, an RL formulation of long-term fairness is imperative. \n\n> The color scheme in Figure 1 is slightly unclear…. Could the authors please clarify this?\n\nWe agree that normalizing each figure’s color scale for maximum dynamic range would lead to greater clarity. We have regenerated these figures, providing an example in the rebuttal pdf.\n\n> … it would be interesting to see how the other baselines perform in this second scenario as well.\n\nWe give full comparisons to all baselines in the supplementary material. For this setting, see Column 1 of Table 2."}, {"review_id": "f67uHLfNAP", "reviewer": "Reviewer_iPFQ", "summary": "This paper considers a binary classification task with long-term fairness. The authors formulate the problem as a constrained MDP where the classifier is an action, the distribution is the state, the distribution will shift reacting to an action. The problem aims to optimize the expected long-term reward under the constraints for long-term fairness in expectation. They develop L-UCBFair which is a model-free algorithm to guarantee long-term fairness with continuous state and action spaces.  Under the linear MDP assumption, they prove sublunar regret and disparity with high probability.  Finally, experiment results are given to demonstrate the performance of the proposed algorithm.", "questions": "1. The paper considers a dynamic where the new distribution is affected by the previous distribution and classifier. Can the authors give some concrete motivation examples for such distribution shift?\n2. Can the authors discuss the challenges of solving the MDP with fairness constraints?  What are the differences comparing with standard constrained MDP problems?\n3. How does the complexity of proposed algorithm rely on the space of state and action?", "limitations": "The limitations are listed by the authors.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "I believe the paper has the following strong points.\n+ The paper formulates fairness constrained classification problem as a constrained MDP, which is new to me.\n+ The paper applies linear MDP algorithms and TD3 to the considered problem and prove the regret bound with linear MDP assumption.", "weaknesses": "The paper can still be improved in the following aspects.\n- The paper seems to directly apply LSVI-UCB and TD3 algorithms to solve the considered constrained MDP problem. It would be much better if the authors can discuss how the algorithm design and proof techniques are different from original works in (Jin et al. (2020)) and  Fujimoto et al. (2018).\n- The paper formulates the fairness-constrained classification problem as a MDP problem, but does not give enough motivation. \n- It usually requires a lot of exploration for the constrained RL to achieve low disparity, so I am afraid that the fairness violation can be very high at early stages.\n- The paper is limit in addressing the complexity problem by using constrained RL for this problem.  The action space (classifier) can be very large, which can cause a very large complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper seems to directly apply LSVI-UCB and TD3 algorithms... It would be much better if the authors can discuss how the algorithm design and proof techniques are different from original works in (Jin et al. (2020)) and Fujimoto et al. (2018).\n\nThe L-UCBFair differs from LSVI-UCB (Jin et al. 2020) in important respects:\n\n1. LSVI-UCB constitutes an RL framework devoid of constraints. The objective in Jin et. al.’s paper is to maximize cumulative utility, whereas ours is to optimize utility subject to a fairness constraint. Due to this constraint, we must monitor the value function associated with cumulative fairness violations (i.e., “distortion” in our paper), and derive bounds on  the associated regret. Deviating from the cited work, we employ a primal-dual approach and formulate a policy that takes both the objective and fairness constraint into account (refer to algorithm 1, SM(...)). The resulting proof establishes regret and distortion bounds at O(H^2√d^3K), both with high probability.\n2. LSVI-UCB exclusively applies to discrete action spaces. Without the ability to utilize continuously varying policies, It may be impossible to satisfy fairness conditions, just as it may be impossible to find the roots of an arbitrary polynomial when restricted to integer-valued inputs. For dealing with fairness, our extension of LSVI-UCB with an adaptive search policy is necessary.\n\nSimilarly, R-TD3 differs in an important way from direct application of TD3 (Fujimoto et al. 2018):\n1. The objective on which we use TD3 is a Lagrangian relaxation of the constrained optimization problem with a schedule for the dual variable, where the schedule introduces an additional hyperparameter.\n\n> The paper formulates the fairness-constrained classification problem as a MDP problem, but does not give enough motivation… The paper considers a dynamic where the new distribution is affected by the previous distribution and classifier. Can the authors give some concrete motivation examples for such a distribution shift?\n\n*Regarding motivation and examples:* Deployment bias is a frequent occurrence in machine learning systems where the model interacts frequently with users and the model's outputs have a high impact on users' well-being (e.g., financial decision-making) and preferences (e.g., recommendation system). \n\nImagine two distinct user groups in the loan approval setting, namely Group $A$ and Group $B$. Let's assume that the deployed model has a much higher approval rate for the applicants from Group $A$, and that Group $A$ is in a better position to put loans to productive use through investment. Over time, as users from $A$ receive more financial support, they can further improve their financial position (e.g., by receiving education, by starting their own business) and are likely going to become even more qualified for loans in the future. On the other hand, users from Group $B$ lacked the opportunity to grow financially and were trapped in a low socioeconomic status, hurting chances for future loan applications. In this example, the policy (higher approval rates for Group $A$) and the state (Group $A$’s ability to use loans productively) jointly led to a new state where Group $A$ is even more able to use loans productively than Group $B$, which has become trapped in a state with few prospects and little opportunity for advancement.\n\n*Regarding limitations:* The MDP formulation is quite general; the only restriction it imposes in our use case is an assumption of observability (i.e., that no state variables exist other than the distribution itself). While this assumption is not strictly necessary, it does simplify the formulation and eliminates the need for considering additional state information.\n\n> It usually requires a lot of exploration for the constrained RL to achieve low disparity, so I am afraid that the fairness violation can be very high at early stages.\n\nThis fear is not unfounded, however the violation of fairness and increased loss at early stages may in fact be necessary when short-term incentives and long-term benefit may be misaligned in practice (such that myopic policies may steer the system toward undesirable equilibria, as in Fig 1 (b)). This aspect of our work is highlighted in the introduction and further demonstrated in experiments: To guide the system towards more desirable equilibria, an RL formulation of long-term fairness is imperative, and an online setting is unavoidable (See response to first weakness pointed out by Reviewer oXaL).\n\n> Can the authors discuss the challenges of solving the MDP with fairness constraints? What are the differences compared with standard constrained MDP problems?\n\nFor verisimilitude, the key complications to a standard constrained MPD problem introduced by our consideration of fairness are  \n1. An assumption that the MDP transitions are unknown, necessitating the use of the RL method to derive the policy, given the usual lack of knowledge about real-world dynamics.\n2. The use of continuous action spaces, which are often necessary to satisfy fairness constraints and are ubiquitous in the real-world (e.g., when actions correspond to policy parameters).\nNo prior model-free constrained MDP for continuous action spaces has been theoretically equipped with regret and distortion bounds. Our work breaks new ground by introducing the first algorithm of its kind, providing such guarantees.\n\n> The action space (classifier) can be very large, which can cause large complexity. …. How does the complexity of the proposed algorithm rely on the space of state and action?\n\nState: For state space, our memory requirements are linear in the dimensionality of the learned embedding space ($\\phi$ in the paper).\n\nAction: For action space, our memory requirements are linear in the number of action space regions ($M$ in the paper). As a trade-off, $M$ affects $\\epsilon_I$ (Theorem B.4), and thus regret bounds for the algorithm (Equation 13 and line 526)."}, {"review_id": "YVaLVNVs3V", "reviewer": "Reviewer_kVGy", "summary": "This paper examines the issue of enduring fairness within a dynamically responsive population, framing it as a reinforcement learning (RL) problem with certain constraints. In this scenario, the state distribution is subject to change dynamically based on the actions of the deployed agent. To address this problem, the authors introduce L-UCBFair and R-TD3. L-UCBFair assumes a simplified linear Markov Decision Process, while R-TD3 incorporates existing deep reinforcement learning methods for a more general setting. According to the numerical experiments conducted, the proposed method consistently surpasses the performance of baseline methods. The RL approach enables an agent to learn how to forego short-term utility to steer the system towards more desirable equilibrium states.", "questions": "The issue of long-term fairness can become quite resource-intensive when the agent interacts with the real-world scenarios. Within the existing body of reinforcement learning literature, model-based reinforcement learning methods have been devised to enhance sample efficiency. Could the authors discuss the potential of developing a model-based reinforcement learning approach to tackle the long-term fairness problem addressed in this paper?\n\nMoreover, several queries were raised in the previously mentioned weaknesses section.", "limitations": "The authors followed the PaperChecklist by providing a discussion on the current limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**Originality**:\nThe authors uniquely approach the fairness problem in machine learning within a context where the underlying state distribution dynamically evolves based on the agent's decision. This novel setup extends the static fairness issue found in the existing literature. The dynamic viewpoint introduces the concept of cumulative reward and distortion (cumulative fairness disparity), aptly fitting the method of reinforcement learning. The experiments carried out distinctly highlight the benefits of incorporating a reinforcement learning method, particularly in cases of changing underlying environments.\n\n**Quality and Clarity**:\nThe motivation behind this work is cogently presented in the introduction, while the related works section explores a wide range of existing literature, discussing both fairness issues in non-stationary settings and safe reinforcement learning. The demonstration of numerical experiments is lucidly laid out.\n\n**Significance**:\nThe suggested L-UCBFair and R-TD3 methods surpass the performance of baseline methods. The concept of foregoing short-term utility to guide the system towards more optimal equilibrium states is effectively demonstrated. Furthermore, the author presents a thorough theoretical analysis for the proposed L-UCBFair under the linear Markov Decision Process assumption.", "weaknesses": "**Weakness 1**:\nThe depiction of Algorithm 1 could be clearer. There are several terms defined in the paper that aren't elaborated upon, making comprehension more challenging. Enhancing the clarity in Section 3.1.1 could greatly improve overall readability.\n\n**Weakness 2**:\nThe authors introduce R-TD3 as a broader reinforcement learning method, not reliant on the linear MDP assumption. Could the authors shed more light on the advantages or enhancements that R-TD3 offers in comparison to the foundational method, L-UCBFair?\n\n**Weakness 3**:\nIn the numerical experiments, the authors have designed synthetic simulation environments based on straightforward datasets. However, in the existing literature, public simulators dedicated to long-term simulation, such as \"Fairness is not static: Deeper understanding of long term fairness via simulation studies\", are readily available. Given that this has been mentioned in the related works, could the authors assess their proposed L-UCBFair and R-TD3 in these more complex simulation environments? For instance, situations involving lending, attention allocation, or college admissions could provide further insights.\n\n**Weakness 4**:\nReinforcement learning utilizes long-term planning to maximize rewards and diminish distortion, whereas myopic-fair methods – the basis of all baseline methods used in the paper – only address a one-step optimization issue. Given this, the result presented in Figure 1 seems rather self-evident as one would expect a long-term planning-based RL method to surpass more short-sighted methods. Could the authors compare their proposed method with more robust baseline methods that also consider underlying dynamics?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Depiction of Algorithm 1 could be clearer. Same for Section 3.1.1.\n\nWe express our gratitude for this advice. In the event of acceptance, we intend to enhance the presentation of Algorithm 1 and Section 3.1.1 in the final version. To provide greater clarity, our planned revisions include:\n\n1. Relocating relatively less crucial parameters, such as $\\eta$ and $\\chi$, from the algorithm itself. These parameters will be moved to a new section in the Appendix, where we will elaborate on their specifics.\n2. Segregating the *policy search* details from the primary structure of Algorithm 1. We will introduce a new sub-function dedicated to this aspect. This restructuring aims to maintain the clarity and comprehensibility of the main algorithm. (A potential structure can be provided in .md format.)\n3. Enhancing the alignment between Section 3.1.1 and Algorithm 1 by incorporating annotations in the algorithm using markers such as #LSVI-UCB, #Adaptive Search Policy, and #Dual Update, similar to the bolded text in Section 3.1.1. Furthermore, when introducing concepts like #LSVI-UCB, #Adaptive Search Policy, and #Dual Update in Section 3.1.1, we will explicitly reference the relevant lines in the algorithm to facilitate readers' better understanding of the content.\n\n\n> The authors introduce R-TD3 as a broader reinforcement learning method, not reliant on the linear MDP assumption. Could the authors shed more light on the advantages or enhancements that R-TD3 offers in comparison to the foundational method, L-UCBFair?\n\nThe major advantage of R-TD3 over L-UCBFair is that state-of-the-art deep learning techniques may be used much like R-TD3 (i.e., with a Lagrangian objective subject to scheduled dual variable), potentially providing superior performance, albeit without strong theoretical guarantees. Unlike L-UCBFair, which relies on the linear MDP assumption and thus only trains the weights of the fully connected layer, R-TD3 does not have a requirement for a specific network structure. This makes it suitable for larger and more efficient neural networks, leading to powerful real-world applications involving complicated environments. However, unlike L-UCBFair, R-TD3, as a deep learning framework, does not offer regret guarantees.\n\n> … public simulators dedicated to long-term simulation such as “Fairness is not static: Deeper understanding of long term fairness via simulation studies”, are readily available…, could the authors assess their proposed L-UCBFair and R-TD3 in these more complex simulation environments? For instance, situations involving lending, attention allocation, or college admissions could provide further insights.\n\nWhile the cited package implements the model proposed by Liu’s “Delayed Impact” paper, it uses discrete action spaces (e.g., only seven possible credit score thresholds), in keeping with the capabilities of more established algorithms. To more appropriately demonstrate our work in addressing continuous action spaces, we required a different experimental environment. We agree that additional experimental evaluation may provide further insights, and hope that future work futhers both algorithmic development and experimental settings for our formulation of long-term fairness with continuous state and action spaces.\n\n> Reinforcement learning utilizes long-term planning to maximize rewards and diminish distortion, whereas myopic-fair methods – the basis of all baseline methods used in the paper – only address a one-step optimization issue. Given this, the result presented in Figure 1 seems rather self-evident as one would expect a long-term planning-based RL method to surpass more short-sighted methods. \n\nWe agree that a long-term planning-based RL method should surpass more short-sighted methods in this problem domain (and confirm through experiment that this is so!), and this is why a formulation of long-term fairness, allowing such algorithms to be brought to bear in this domain, is so critical. The state of the art in algorithmic fairness is, sadly, based on myopic classifiers subject to fairness constraints (as listed in Section 1.1). The use of learning techniques to anticipate dynamic population responses to deployed policy and guarantee fairness is nascent. \n\nIt may be presumed that the difficulty of treating continuous action spaces, which are common in real-world settings dealing with fairness constraints affecting human populations, has been a primary reason for the delayed treatment of online or RL leaning methods in algorithmic fairness. Our primary contributions are thus an important step for bringing long-term fairness into focus within this research community.\n\n> Could the authors compare their proposed method with more robust baseline methods that also consider underlying dynamics?\n\nWe take as a primary assumption that the dynamics with which the population reacts to deployed policy is unknown a priori. When dynamics are known, the field of optimal control may be brought to bear, but different dynamics can require different control policies, and this would have to be analyzed on a case-by-case basis. In general, it is true that knowledge of the dynamics can improve performance in the setting of long-term fairness, but at this early stage, we seek generality.\n\n> Model-based RL can enhance model efficiency. What is potential of model-based methods?\n\nAbsolutely, model-based RL can indeed improve performance in specific settings. In particular, when knowledge of the dynamics is known a priori, the class of models can be restricted by this knowledge to improve sample efficiency and performance. Our purpose in this paper has been to provide a general treatment of long-term fairness with minimal assumptions about the specific transition dynamics (i.e., using a linear-MPD assumption), but there is ample room for future work (especially when specialized to specific settings) to adopt model-based RL or approaches deriving from control (e.g., data-driven control).\n"}]

Author rebuttal:
We thank our reviewers for their constructive feedback and questions, as well as pointing out ways in which we could improve our submission (e.g., by highlighting the novelty of our proofs and improving our figures in subtle ways, which we have done).

With the attached PDF, we have regenerated Figure 1 c) as well as Figure 2 a1) and a2) to highlight that the instantaneous disparity achieved by L-UCBFair in these experiments was bounded below 0.32 in violation of Demographic Parity (Table 1).

To address common concerns among our reviewers, we would like to point out that our experimental setup was necessarily non-trivial, as we sought to model continuous state and action spaces. To our knowledge, no existing experimental settings implement continuous state and action spaces specific to the domain of algorithmic fairness, and our evaluation of our methods was not easily extended to other settings without significant effort. We have no doubt that additional synthetic environments will be proposed and implemented in the course of ongoing investigations into the line of inquiry we open with our formulation of long-term fairness.

Additionally, we would like to reiterate that short-term violations of utility, meaning both decreasing loss and increasing fairness, are expected and often necessary in the settings we explore. As stated in the paper, a central motivation of our work is the necessity of sacrificing short-term incentives in order to drive the classifier-population system to more desirable outcomes. We show in our experiments (e.g., Figure 1 a), b), and Figure 2 a)) that myopic fairness constraints, which prioritize short-term fairness, can lead to worse outcomes in the long-run.

Finally, we emphasize that our formulation of long-term fairness as an online reinforcement learning problem is in many ways unavoidable. In particular, while there are risks associated with online learning, the alternative in reality, where interacting with human populations is a slow and costly proposition, is not “offline” learning, but online non-learning, typified by myopic policies.

We appreciate your attention to our submission and the chance to respond to each of our reviewers individually.


Meta-review: My recommendation is to accept the paper.

The authors clearly show that driving dynamical systems toward fair equilibria is an important problem that is not addressed by static or myopic fairness criteria. There is innovation in both problem framing and technical approach (especially finding an effective way to discretize the continuous action space). Reviewer concerns were well-addressed in the rebuttal period. The unconstrained TD3 results should be added to the camera ready to show distinctness between constrained and unconstrained algorithms in real scenarios.
Decision: Accept (poster)