Group Fairness in Reinforcement Learning
Authors: Harsh Satija
Alessandro Lazaric
Matteo Pirotta
Joelle Pineau
Venue: Accepted by TMLR ()

Abstract: We pose and study the problem of satisfying fairness in the online Reinforcement Learning (RL) setting. We focus on the group notions of fairness, according to which agents belonging to different groups should have similar performance based on some given measure. We consider the setting of maximizing return in an unknown environment (unknown transition and reward function) and show that it is possible to have RL algorithms that learn the best fair policies without violating the fairness requirements at any point in time during the learning process. In the tabular finite-horizon episodic setting, we provide an algorithm that combines the principle of optimism and pessimism under uncertainty to achieve zero fairness violation with arbitrarily high probability while also maintaining sub-linear regret guarantees. For the high-dimensional Deep-RL setting, we present algorithms based on the performance-difference style approximate policy improvement update step and we report encouraging empirical results on various traditional RL-inspired benchmarks showing that our algorithms display the desired behavior of learning the optimal policy while performing a fair learning process.

Published in Transactions on Machine Learning Research (04/2023)
Group Fairness in Reinforcement Learning
Harsh Satija
McGill University, Mile
Alessandro Lazaric
lazaric@metta.oo com
Meta AI (FAIR)
Matteo Pirotta
Virotta@@meta.cmm com
Meta AT (FATR)
Joelle Pincau
spineau@es.megillcom
McGill Universily, Mila, Meta AI (FAIR)
Reviewed on OpenReview: https: // openreview. wet.:/eeeeerrtreeeeeeeeeeeeeeeee forum? id= JkIH/MeC33
Abstract
We pose and study the problem of satisfying fairness in the online Reinforcement Learning (RL) setting. We focus on the group notions of fairness, according to which agents belonging to different groups should have similar performance based on some given measure. We consider the setting of maximizing return in an unknown environment (unknown transition and reward function) and show that it is possible to have RI. algorithms that learn the best fair policies without violating the fairness requirements at any point in time during the learning process. In the tabular finitehorizon episodic setting, we provide an algorithm that combines the principle of optimism and pessimism under uncertainty to achieve zero fairness violation with arbitrarily high probability while also maintaining sub-linear regret guaranlees. For the high-dimensional Deep-RL setting, we present algorithms based on the performance-differrnnce style approximate policy improvement update step and report encouraging empirical results various traditional RL-inspired benchmarks showing that our algorithms display the desired behavior of learning the optimal policy while performing a fair learning process.
1 Introduction
With an ever-increasing number of automated decision-makee malsionnmaking algorithms deployed around us, it becomes important to cautious of the risks and biases that can result due to the nature which these algorithms are being trained. Reinforcement Learning (RT,, Sutton, 1988) has emerged as a powerful paradigm for learning in the sequential docision-making setting. At the same time, several studics have demonstrated that it even more important to control for fairness in sequential decision-making, constraints without considering feedback effects of the policy can lead to further discrepancy (Liu et al., 2018). Therefore, in this paper, we focus on the concerns related to imposing fairness not only to the RL optimization problem but also during the learning process.
imposing fairness
We first clarify what we mean by fairness. At an abstract level, fairness can defined as the absence of discrimination. This definition requires us define some measure of discrimination, and then the fairness property defined w.r.t. that measure. For this work, we focus the category of Group fairness. This definition of fairness based notion of protected subgroups and measure across groups The subgroups

---

Published in Transactions on Machine Learning Research (04/2023)
are defined on the choice of some sensitive attributes (such as race, gender, ethnicity, etc.), and measure that is required for comparing the outcomes of different subgroups (such as false-positive rate or classification error). Fairness is then defined in terms of requiring equal measure for different protected subgroups. A majority of definitions fairness falls under this category, such as demographic parity (Dwork et al., 2012), disporate impact (Feldman al., 2015); equality of opportumity and equalized odds (Hardt al., 2016).
Example 1 (College admissions): Consider a scenario where an RL agent assists the college admissions process to accept candidates every semester. A candidate's information consists of sensitive features representative of their demographic information (like socio-economic background gender) and non-sensitive features like their standardized test scores. Duc to resource constraints, the college can only admit limited number of candidates during every admission cycle. Suppose the college consistently admits candidates from one demographic group over the other. In that case, it can create a feedback loop where candidates from that particular group are encouraged to apply more and vice versa (Immorlica et al., 2019; Garg al., 2020; Puranik et al., 2022). From an equity and diversity perspoctive, one can motivate the need create feedback loops for the minority groups to reverse existing (rends (Emelianov el. al., 2020). Thus, under this fairness requirement, the admissions agent should admit the top-scoring candidates such that the long-term disparity between demographics should be below some target over all the admission cycles.
Example 2 (Credit lending): Consider another scenario where an RT-based credit lending system assists a bank by filtering loan applicants. The lending agent interacts with applicants having features consisting of both sensitive attributes (like demographics) and non-sensitive attributes (like credit score). An applicant might file for multiple loans over a span of time, and for any given application, the lending agent needs decide whether to approve or reject an application maximize the number of loan repayments for the bank. The problem is sequential as both the repayment and defaults the granted loans take over some time, during which the applicant's 's non-sensitive features can change due to the agent's actions (for instance, credit score might decrease for applicants that are unable to repay in time). Furthermore, the applicants in different demographics can have different dynamics (how the croditworthiness of cach group evolves) and other initial starting non-sensitive stale distributions (like credit score distributions). Recent works on imposing fairness in the credit lending domain have highlighted the caution regarding the long-term effect of deploying such decision-making systems these systems have to potential to increase further the disparity between groups (Liu et al., 2018; Castelnovo et al., 2021; D' Amour et al., 2020; Fuster et al., 2022). Thus, external regulations like the Furopean AT Act. (The Furopean Commission, 2021) might require that such a system not exhibit. discriminatory behaviour toward different population segments. Under this requirement, the policies deployed by our algorithm should not exhibit behaviour that contributes to the existing disparity between groups, such as rejecting more applications from particular demographic compared to the other.
Although we motivate the problem in the credit lending and college admissions domain, the evidence related to the biased nature of deployed algorithms is substantial and can be found in variety of settings such hiring, ads and marketing (Miller, 2015; Dastin, 2018; Datta et al., 2015; Celis et al., 2019; Fu et al., 2020).
1.1 Contributions and limitations
We now highlight how introducing the fairness requirement in the RL framework changes its different aspects. First, the fairness requirement changes the definition of the optimal policy; the learning objective becomes to find the policy that maximizes the reward in restricted class of policies that satisfy the fairness property. Additionally, at any point in the learning process, the policy executed by the agent should meet the fairness criteria. This makes applying traditional RL exploration strategies, such as those based on optimism under uncertainty, particularly challenging for this setting as being optimistic can lead to being unfair.
(a) Traditional
(b) Fair
Figure 1: Toy grid-world example demon-
strating traditional fair optimal policies.
Example 3 (Four-rooms grid): Consider the modified four-room domain in Figure that contains two subgroups: the circle agents that start in the upper-left corner and the diamond agents in the lower-left corner.
2

---

Published in Transactions on Machine Learning Research (04/2023)
The state is defined both by the position of the agent in the grid (non-sensitive attribute) and the shape of the agent (sensitive altribute). The goal is to reach the cell containing the gold star in the least amount of steps. Both subgroups start at similar distance from the goal, but the transition dynamics of circle agents is deterministic whereas the diamond agents have very stochastic dynamics. Thus, the trajectories taken by the circle agents via traditional RL optimal policy are shorter compared to the diamond agents (Figure 1a). Enforcing the group fairness constraints here leads to slightly longer trajectories for circle agents (Figure 1b) and we observe that both subgroups now take similar time to reach the goal to satisfy the fairness criteria.
We aim to answer the following question in this work: Can we design algorithms that respect the given fairness constraints throughout the policy improvement learning procedure and achieve good performance In Section 3, we show it is possible to have an algorithm with high probability guarantees on performance and fairness during the learning in the tabular episodic RL setting. This is achieved by leveraging the principle of combining optimism and pessimism, as previously used in constrained bandits (Amani et al., 2019; Pacchiano et al., 2021), constrained MDPs (Wachi and Sui, 2020; Liu et al., 2021) and robust-RL, (Curi et al., 2021). We apply this principle to the fairness setting with unknown MDP parameters for balancing the exploration and fairness trade-off to simultaneously achieve zero fairness constraint violation during learning, and sub-lincar regret. In Section 4, we present scalable and practical Deep-RL algorithm that uses a trust-region-basee based update rule to approximate guarantees on the fairness violation. This approach is based on the raintr policy improvement performance bounds proposed by Achiam et al. (2017) and allows us to extend the Deep-RL algorithms such as PPO (Schulman et al., 2017) to our setting. In Section 4.3, we provide empirical evidence that our approach is indeed able to achieve good performance while achieving the fairness requirement on simulated robotic locomotion and navigation tasks.
We now identify some of the limitations of our approach. First, note that we neither impose any structure the environment nor consider the case where there is any information sharing within the groups. This makes our setting different from the multi-agent setting as the agents interact with the environment independently and do not interact with other agents in any form. Our setting is closer to the typical singlo-agent RL setting, with the added caveal that the environment can behave differently for some populations of agents.
Next, we work in the context of the traditional group fairness definitions and do not investigate the effectiveness of these definitions. In practice, selecting particular algorithmic fairness definition for any domain can be quite challenging as the fairness demands can be formulated under different perspectives and scenarios. This is further exacerbated by the fact that there is no consensus on a universally accepted definition of algorithmic fairness and some fairness definitions are at odds with each other (Chouldechova, 2017; Pleiss et al., 2017). We are not advocating that using existing group- notions of fairness will address all the concerns related to fairness in the sequential decision-making setting. This is a rather complex problem, and the solution will potentially be more involved than either a single kind of fairness definition (Awasthi et al., 2020). Our work should be viewed as the first step toward this bigger goal where we establish the general results regarding satisfying group- based notions of fairness in the context of the RL paradigm.
Finally, our approach is based on enforcing the fairness requirements by directly restricting the policy space. This implies that guaranteeing fairness can limit the scope of available policies and can come at a performance cost for some groups. As such, given a group fairness requirement, our approach can potentially penalize the higher-performing groups (as in Example 2) to match the performance of the lessor-performing subgroups (within some margin), whereas an ideal scenario would have been to increase the performance of the latter. We will revisit this limitation in Section 5 and propose possible workarounds against this for future work.
1.2 Related work
Fairness in machine learning is an active field of research (Mehrabi et al., 2019; Pessach and Shmuuei, 2020; Gajane et al., 2022). A number of recent works have specifically explored various aspects of the fair-RL setting. Jabbari et al. (2017) study the problem of fairness in online RL setting and Doroudi el al. (2017); Nabi et al. (2019) study the problem in offline RL setting, however, they work with different non group specific notions of fairness has no notion of sensitive attributes or groups. Siddique et al. (2020) study a notion of fairness based on social welfare functions the multi-objective RL setting and provide methods to adapt the traditional RL techniques to their modified objective. Mandal and Gan (2022) study the problem
3

---

Published in Transactions on Machine Learning Research (04/2023)
of selecting a mcasure that ensures fairness in the multi-agent RL setting. They propose properties that fair policy should satisly and provide an algorithm to find such fair optimal policy in the unknown multi-agent, MDP. Their notion of fairness is different from the group-based fairness we consider in this work.
The problem studied in this work is closely related to the one studied in the Constrained MDPs (CMDPs, Altman, 1999). The focus in CMDPs is to find policy that maximizes the return in some restricted policy class, where the constraints that define the restricted policy space are based on the additional feedback signals from the environment. The main difference in our setting and CMDPs is how the constraints on the policy space are being defined. In CMDPs, constraint is based solely on return defined w.r.t. a single reward signal, and multiple constraints differs only in the corresponding reward signals while all the other environment parameters remain the same. Whereas in our setting, given a fairness criteria, the constraints are based on the returns belonging to different populations that may differ due to variation in any possible environment parameters. As a result, the constraints in our case are based on a combination of multiple returns, each of which can differ in either reward signal or the transition dynamics. Despite this difference, we build on the works on exploration in CMDPs (Achiam et al., 2017; Tessler et al., 2018; Chow et al., 2019; Zhang et al., 2020; Efroni et al., 2020; Liu et al., 2021).
A closcly related work to ours is the recent work by Wen et al. (2021) who incorporate the group fairness criteria as a constraint in the CMDP framework. Similar to Wen et al. (2021) we also make an assumption that the sensitive attributes (like race) do not change via interactions with the environment. However, the formulation in Wen et al. (2021) requires that populations corresponding to different sensitive attributes to share the same environment transition dynamics. Instead our work addresses a more general setting where the different populations can differ in any of the environment parameters, including the transition dynamics. Furthermore, in the approach proposed by Wen et al. (2021) the policy is only updated once throughout the entire learning process. Finally, they also assume that the uniform exploration policy is fair, which is not true in general, and can violate the fairness constraints any number of times.
2 Problem setting in finite-horizon episodic MDPs
For any positive integer n, let [n] denotes the set {1,..., m). An episodic Markov Decision Process (MDP, Bellman, 1957) is denoted as M = A,, n,, H), where S = [N] and A = [A] denoles the finile state and action sets, H denotes the horizon or length of the episode, and тд :S x A - [o, 1] denotes the reward function at time step h E [H]. The transition model is denoted by P.(-Is, a) E A Ys E ES,Va. E A, where As denotes the |S| dimeennnsll probability simplex. (s's'ss, a) denotes the probability of transitioning to state s' after taking an action from state at time step h E [H]] The initial state distribution is denoted by / E As, where μ²s) denotes the probability of the agent starting in state 8.
P,r,
A non-stationary policy in this setting is defined as π. [H] x S + As. We abuse the notation and use na (als) to denote the probability of taking action a in state s at time step h. The expected return of a policy at some state s E S is defined by the value function (, P) = Ep, Σn (S,, Sh = s], where A, ~ (-(S.) and S2+1 ~ (-]S,, At). The return of the policy is defined by (r; P) = Es
P)].
The occupancy measure d= of a policy æ denotes the set of distributions generated by executing the policy स and is defined as dī (8, a; p,, P) = [S, 8, An alSa ~ nr, P, m]] Pr(S, 8, A. alSa ~ M,, PT (Efroni et al., 2020). Using the occupancy measure, the return of a policy can be reformulated as [T Ensaa (s, n. (srn(s,a) (Altman, 1999; Puterman, 2014). The traditional RL. optimal policy w.r.t. reward function r is defined as arg max, (= P).
2.1 Introducing fairness
We focus on the fairness definition based on groups where different sub-populations of agents are interacting with the environment independently. We assume the agent's state space is jointly comprised of sensitive attributes that are required for defining a notion of group, and environment specific features that determine how the agent navigates in the environment. For instance, in a recommender systems context, the agent specific sensitive attributes can be race, gender, nationality, etc. whereas the environment specific attributes
4

---

Published in Transactions on Machine Learning Research (04/2023)
can be budget, past order history, preferred categories. We also assume that interactions with the environment do not change the agent's sensitive attributes. Formally, these assumptions can be defined as: Assumption 2.1 (Separable and observable attributes). We assume the state space 8 is jointly composed of sensitive-attribute Z and non-sensitive attributes S, i.e., ==2 2 x XS.
Assumption 2.2 (Consistent sensitive attributes). We assume that an agent's sensitive attributes remain constand throughoul episode. This implies that the transilion function al any h E [H] salisfies (r(5'(,,) Pa 8) = (,,) = =²1 relation, where Pr. (,,,8,,,,,00 is the underlying transition function associated with non-sensitive altributes and 2 2 Z.
Definition 2.1 (Subgroup). We refer to the population of agents associated with particular sensitive attribute E Z as the subgroup associated with 2. The initial non-sensitive state distribution associated with particular subgroup Z is denoted by nd Asg and defined as (x(3) Pr(3]=) PH(sT v3 E S, where Pr(z) E=Esu(E 8) is a normalizing constant.
u(z.3)
For an agent belonging to subgroup z E Z, (8) denotes the probability of the agent starting the episode in the non-scnsitive state 3. Similarly, we use P= to denote the subgroup spocific transition function corresponding to the non-sensitive attribules, i.e., P=,M (5'6, a) = Px |2, 8, a). Note that the definition of policy remains unchanged, i.e, it depends on both á and z. We can thus define the subgroup specific returns for any policy as:
(r = E ((,) P.)].
Simui
We work with a particular group fairness criteria known as demographic parily (Dwork et al., 2012; Zafar et al., 2017). Informally, the demographic parity constraint requires that different subgroups should have similar returns. Formally, in our setting it is defined as follows.
Definition 2.2 (Demographic fairness). For some 0, that denotes an acceptable margin of error, policy satisfies demographic fairness criteria if (r, P) - JJ (r. Pr) S vi 2 (i.5) E z².
The decision maker's reward might or might not be aligned with the reward of the demographics. For instance, in the grid world navigation scenario, there is no distinction between the reward of the mecision-maker and the demographics with the reward being reaching the goal quickly. Whereas in the credit lending scenario, the decision-makerss 's reward is to maximize the bank's profits via loan repayments, whereas the demographics reward is to get more loans. We consider the general case where the decision maker's reward can be different and denote it by 4n : S x A + [0, 1]. Let x* denote the optimal policy that maximizes the return among the class of policies that satisfy the above fairness condition, i.e.
" = arg max J (L,
(2)
s.t. -
Vi 2 jiije 2
Note that the primary objective in Equation (2) is concerned with maximizing the cumulative returns for all subgroups w.r.t. the decision-maker's reward function whereas as the fairness constraint based on the demographics reward function r. When all the MDP parameters are known, it is possible devise a Linear Programming (LP) solution to the problem in Equation (2). The details of the LP solver are provided in Appendix B. In Appendix B.3, show how other group fairness definitions, such equality of opportunity and equalized odds (Hardt et al., 2016), can be formulated and solved in our setting.
In order to avoid making any assumption regarding the feasibility of the problem, we make the following assumption regarding an initial fair policy:
Assumption 2.3 (Initial feasible policy). The algorithm has access to a policy x0 that satisfies the fairness constraints in Equation (2). We also assumee |J (r. P) -J" (r. P)I S e <e, v(i.j) E 2² and the value of e is known to the algoritio..
Having an initial fair policy ensures that the problem in Equation (2) is always feasible, even in the case when the agent is unaware of the MDP parameters it can always interact with the environment. without.
5

---

Published in Transactions on Machine Learning Research (04/2023)
violating fairness constraints via x². Assumption 2.3 will not be valid if either Equation (2) is unfeasible, or none of feasible policies satisfy the strict inequality condition, i.e., none of them have any margin for exploration. From a practical perspective, any known sub-optimal policy that the algorithm practitioner regards as fair can be used, by controlling the acceptable fairness threshold c.
We acknowledge that Assumption 2.3 is a strong assumption as it requíres the algorithm practitioner to have fair exploration policy with some margin. We want to highlight that the learning problem we consider in this work is also quite challenging, hence the reliance a stronger assumption. When the learning algorithm has neither any information about the environment nor any access to some initial fair exploration policy, it cannot avoid unfair decisions in the first episode of learning itsclf, as any potential interaction with the environment might lead to a fairness violation at the beginning of the learning process. Similar assumptions are also made in safe RL literature (Pacchiano et al., 2021; Liu et al., 2021; Bura et al., 2022). The assumption is not unrealistic, as the practitioner can use any existing strategy, even if it incurs low rewards, to initialize the algorithm. The strict incquality in the initial exploration policy is required to leave some margin of crror for the agent to be able to explore where the dependence on the margin term e - e is also captured in the regret bounds in Theorem 3.2.
Note that it is possible to leverage the techniques from Efroni et al. (2020) and provide a sublinear regret result without such an assumption, however, doing so does not guarantee zero fairness violation during the learning process. We can then only guarantee that the number of violations decreases over time. Finally, it is possible to devise algorithms for the simpler problem of recovering a fair policy. While this will remove the necessity of having access to a fair initial policy, the algorithm will only be guaranteed to deploy a sublinear number of unfair policies. However, this is outside the scope of this work.
2.2 Motivating example
We expand on the credit lending example provided in the Section 1 to better illustrate our setting. We build on the lending environment from D' D'mmour et al. (2020); Wen et al. (2021) where the agent is making applicant filtering decisions on behalf of a financial institution. An applicant applies for multiple loans over a span of time and the agent is tasked to accept or reject the application, i.c., A= (GRANT, REJECT). The applicant features consists of non-sensitive attributes based on credit score 5 = =1....... CMAX), where the probability that an applicant successfully repays the loan is a deterministic function of the credit score denoted by & $ + [0, The bank makes a profit of interest T on successful repayment of granted loan and suffers a loss of principal Ps on default, i.c., I(-, S, GRANT) = E( (1 - Pp
There are two group of candidates Z = {high, low> that have different initial credit score distribution as well as dynamics of how the credit score evolves due to agent's actions. The initial credit-score distribution of the group high skews more towards the higher ranges with a higher mean of initial credit score compared to the low group. For both the groups, if granted a loan, a successful repayment of a loan leads to improvement. of the applicant's credit score by ct whereas a default causes the credit score to decrease by c However, the dynamics of both groups differ on rejection where an applicant from the group low is affected more and suffers possible decrease in ability to repay future loans. This is modeled by decreasing the credit score of applicants in group low by c with a probability v on rejection, where V is a hyper-parameter that denotes the handicap. The candidates in the group high do not experience any change in credit score on rejection. The candidates are applying for loans because they need credit, thus the reward of the candidates is based on whether or not they were given loan, r(2, 5, a) = 1[ = GRANT]. Therefore, the fairness constraint. here ensures that a near equal amount of loans are given to both the groups. This prevents the agent from significantly rejecting more loans from the disadvantaged group, that was disadvantaged due to possible history of financial oppression in the first place. In this setting, the traditional non-fair RL algorithms will focus solely on maximizing the bank profits leading to rejecting more applicants from the low group and further increasing the existing disparity.
Finally, an initial policy that grants the loans to every applicant regardless of their credit score can be used for Assumption 2.3. Even though this policy might be quite sub-optimal in maximizing the bank profits, but since it approves loans with same rate for both the groups (c" = 0), it can be used to drive the initial exploration for any choice of margin.
6

---

Published in Transactions on Machine Learning Research (04/2023)
3 Algorithm for the unknown model and reward setting
We now turn our attention to the setting where the agent only has access to the subgroup specific initial non-sensitive state distributions uı, Vz E 2, and relies on the observed (sampled) rewards and transitions to improve its performance over time. For clarity, we present our method for the case where groups are sampled uniformly for each episode (or Pr(z)= = 1 1/1 V2 E 2). We relax this assumption later and show that our results also extend to the general case of non-uniform group sampling distributions.
We assume that the algorithm interacts with the environment for total of K episodes, with each episode being H steps long. For each episode & [K], a subgroup z is selected uniformly from Z and then the corresponding initial state (Zf, S)) is sampled from uzz The agent then exccutes the non-stationary policy at that current episode n², where the agent takes an action Af, on state (2k.5%) at the time step h transitions state 1 St. where - Z and Sh
(- Sh. Af) (Assumption 2.2), 5k
and receives the rewards (2 Sh where 5% is zero mcan Reg(K;1) = E (1, Jx P)). Given some initial fair exploration policy x0 (Assumption 2.3), our goal is to design learning algorithı that can (i) satisfy the fairness requirement with arbitrarily high probability throughout the learning, and (ii) achieve a sub-linear cumulative regret in the mumber of episodes.
Sk A = (Z S A + Sh and (2) b A/ = 4, Sh A% + chi We define the cumulative regret in the traditional sense as
To guarantee the fairness requirement holds throughout the learning, we construct a set that contains the possible policies that are fair (with high-confidence) based on the general principle of the optimism in face of uncertainty (Auer et al., 2008; Efroni et al., 2020; Liu et al., 2021). We want this set to contain the policy updates, based the current MDP estimates, that ensure we do not violate the fairness constraints in the true MDP with high confidence. However, optimism alone is not sufficient to construct such set as want the fairness guarantee to hold in the true MDP model and not just in the best possible optimistic MDP model (formal argument provided in Appendix C.1). Therefore, we use the techniques from Liu et al. (2021) that combine both optimism and pessimism to construct reward estimates to achieve this goal.
At each episode k; we denote the empirical estimates of the rewards and transition model at time step h based on the episodes [l,...,k k- by Ph, 0% and Pt For a given value of 8 E (0, 1), we denote the uncertainty estimate for the empirical transition and rewards by, (2, 8,))
log ((
max
where (2, F, denotes the number of times the state-action tuple (z, 3, a) was observed at time step h so far V(2, a, h) e Z xxxxxA Ax [H]. We define the optimistic and pessimistic reward estimates as:
((2,8, (0
(3)
a)) f2, -1 11+
With high confidence, we want an optimistically estimated return to be greater than the underlying true return and vice versa, even when accounting and integrating the uncertainty due to rewards and transitions over the horizon. The constants for the optimistic and pessimistic rewards in Equation (3) are defined to get the corresponding properties for the associated returns as described in Appendix C.3.
The key step in our approach that is different from Liu et al. (2021) is that for pair of subgroups i,j Z², we optimistically estimate the return for the one subgroup and al the same time pessimistically estimate the return for the other subgroup to ensure that the fairness constraint still holds true with high-confidence. We define the set of policies that satisfy the fairness guarantees based on the optimistic and pessimistic reward estimaat estimates as:
(p) (7 p JJ((" ph) Se. π
WZj;; ( Z². Vi (1.j) E z².)²
(4)
J7 (7+ pk) - J (r*,, pk) S
7

---

Published in Transactions on Machine Learning Research (04/2023)
where have omitted the conditions for A for the sake of brevity. The final set of policies available to the algorithm to execute at episode l is chosen from the high-confidence set IT defined as:
if J. (rh, phy JJ (r* Ph) > (//2 Vi 2 J: (1,1) E?
(m)),
or (F (F - (F"((", ,h) 2 otherwise.
(5)
The first case denotes the scenario where the pk, pk parameters are not well estimated and as such the agent needs to gather more data by executing the known initial fair policy TO. We now present a result stating that policies chosen from TT do not violate the fairness guarantees for any of the subgroups throughout the learning duration with arbitrarily high probability.
Theorem 3.1 (Fairness violation). Given an input confidence parameter å (0, and an initial foir policy TO, the construction of II ensures that there are no fairness violations at ony episode in the learning procedure in the true enviromment with high probabilily (1 6), i.e., for any E IT*
Pr (r (r. P) E 1- v(i.)) E E
(6)
The proof of the above claim is presented in Appendix C.4. Even though selecting just any policy from II will satisfy the fairness guarantees, we also care about efficiency of the exploration. In order to achieve sub-linear regret, we incorporate another optimistic reward estimate that is defined as:
(z, (2, (2,
where a; 1 IZIS|H SH(1+12 (8 is another scaling factor with 17 = (c- c)).
To conclude, for episode k [K], the maximum performing policy within the set IIf w.I.t. the new optimistic reward is selected to be executed as n², i.e.
T E arg J"" (i .h)) #ET
(8)
The above optimization problem can be solved in similar manner the LPP formulation in Section 2.1. The complete algorithm is presented in Algorithm and the exact formulation of LP for solving Equation (8) is given in Appendix C.5.
Theorem 3.2 (Regret Bound). For any d E (0, 1), with probability 1 - 8, executing x² from Equation (8) at every episode k E [K] incurs in a regret of at most
Reg(K; H
H 27281191111 |ZUISPAIK + min 113
where Ö(-) hides polylogarithméc terms.
The first term in the above result corresponds to the difference from using estimated parameters instead of the true MDP parameters. This term is consistent with the result of Liu et al. (2021) in the context of CMDPs, where this quantity takes the form Ö H² of constraint violation for CMDPs and we assume |S] |z||š). In (Efroni et al., 2020), this term takes the form ò Õ(H² 1 1 but they do not guarantee zero constraint violation during learning. The second term in Equation (9) (independent of K) represents the upper bound on the amount of time the agent needs to resort to executing TO due to inaccurately estimated MDP parameters. In (Liu et al., 2021), this term when defined in context of a CMDP with a single constraint, takes the form H | In our result, we have an additional factor of | to account. for constraints in our case that are defined pairwise.
nc / (() Here πJC denotes the exploration margin terms
min(ric n
As mentioned earlier, we currently sample z Z uniformly for each episode (or Pr(2) 1/12], Z). However, this might not be the case in reality different, populations might not be always represented equally.
8

---

Published in Transactions on Machine Learning Research (04/2023)
Algorithm 1 LP based algorithm for Section 3
Input: n², , K
1: Initialize: N2(2, 8, O, v(2,8,,,)) E 2xxx A x [M].
2: for k= ,,...,K K do
3: Update the empirical estimates Pk pk,pk, p*
4: Compute the optimistic and pessimistic reward estimates ,r,
5: Set nh t- Null
6:
for 2 (i.j) E z²: do
if J (rt, - Pt) > (e+ (2/2)
V (I5" (r*,, ph) - J (r", ph) (c + 22222 then (r*,
8:
Set k +
9:
end if end for
10:
11:
if n² = Null then
Set T + arg ma J (n((,, phk).
12:
13:
end if
14:
Execute n
in
the
true environment
and collect a
trajectory
S SK, A r (Z). Sk.
Sk h A), wh E [H];
Šk
15:
Update counters (2 Sp Ab), vh E [A];
16: end for
In Appendix C.7, we show that our approach can be easily extended to the setting with any arbitrary Az by also incorporating the Pr(z) term in the definition of subgroup specific returns. The results regarding fairness violations and regret Theorems 3.1 and 3.2 remain valid even in this extended setting.
To summarize, we build on the methodology of Liu et al. (2021), defined in the context of traditional CMDP setting, and extend it to the setting of group-based fairness constraints. We show that the proposed approach still maintains desirable properties of achieving good performance while respecting the given fairness constraints. The methodology of Liu et al. (2021) only requires pessimism the constraints as the safety constraints in CMDPs are based entirely on a single reward function. However, the group fairness constraints we consider in this work require pairwise treatment of returns the statistics of different groups considered. When introducing more than one reward function in the constraint, a single reward scaling technique such as pessimism fails to be sufficient anymore and instead we require techniques that can carefully balance the different notions of reward scaling. This combination of optimistic and pessimistic reward shaping and balancing in the fairness constraints, along with the pairwise nature of group constraints, requires substantial effort and new results (like Lemma C.6 and proof for Theorem 3.1) to exlend the analysis techniques from Liu et al. (2021).
Cumeerte
Carvedes
Fermer S0S609
Tim--cape
Time-daps
T me-2a2e
Tim--thge
Timeestaps
Time-092x
MCP
A2 = 0.19
(b) Az 0.9]
(c) Az = [0.5.
Figure 2: Regret and fairness violations on the credit landing environment for different underlying group distributions, where Ag denotes [Pr(high), Pr(low)]. In all the scenarios, our proposed approach achieves sub-linear regret and close zero fairness violations.
We provide an empirical study validating the above results on the credit lending environment (Section 2.2) well as a variation of the classic RiverSwim environment. (Strehl and Littman, 2008) in Appendix D. We
9

---

Published in Transactions on Machine Learning Research (04/2023)
compare our method with an MLE baseline that starts with x² and then builds the MLE estimates of the MDP parameters. The MLF baseline then uses the estimated parameters in the LP solver (Appendix B) to get a policy to execute at an episode k. We show the results for credit lending environment in Figure 2 where we see that the proposed algorithm can reach good performance and sub-lincar regret while maintaining the zero fairness violation property across different group distributions. While the MLE baseline incurs a very low regret, however comes at a cost of large number of fairness violations. We provide all the additional environment and experimentation details in Appendix D where we show the properties of our method also hold true for the RiverSwim environment. Finally, note that Liu et al. (2021) do not provide any empirical evidence of their approaches for the unknown MDPs.
4 The infinite-horizon and high-dimensional Deep- RL setting
Much of the recent interest in RL is in the Deep-RL setting where the state and/or action spaces are high dimensional and non-linear dunetion-aprooximatoss are used for policy and value estimation. As the state and/or action spaces can be infinite, the LP-based approaches from the previous sections are not applicable in this setting anymore. Rather, most of the practical algorithms in this setting fall into the category of approximate policy iteration that are usually implemented in an actor-critie learning control architecture with policy gradient-based updates (Sutton and Barlo, 2018).
In order to be consistent with the other works in this space, we make the following modifications to our setting, We now consider the hime-homogeneom infinite horizon setting. where E [0, 1) denotes the discount factor. Let T ~ æ denote a trajectory т = AI,..,. sampled from the MDP using the stationary policy 9, Le, S1 ~ Ar ~ ((11))),(+11 ~ P(-(S,,A)) The infinite-horizon discounted return associ- ated with a stationary policy æ and reward function is denoted by J(T; = ETT = The value and state-action value functions are defined as V=(ssr) = Erwr 7'r,, and Q" (s{ssa; r) = E (r(S, Ac][S] 8, A a] respectively. The advantage function is de- fined AF arr) = (s)(s,arr) -Vsss)). The discounted future state visitation distribution is defined by d' = (1 7) 7 E Pr(S = s|)).
s]
When introducing fairness in this setting, we assume 2 is a finite set (countable number of subgroups) but the non-sensitive attribute space S can be potentially infinile. Additionally, we use n. : S + A to denote stationary policy associated with a subgroup 2 E 2, i.e, मं (=(a|2.8) a E A, E $}). The complete policy can be denoted by π { ( The discounted return of subgroup z under Tı is denoted by J(z)). Finally, similarly to the Scction 2.1, the subgroup specific quantitics can also be defined for the infuite-horrzon setting, i.e., uu. d=, V Q and AT
4.1 Trust-region based fair policy updates
We base our approach on the trust-region based local policy gradient methods that focus on iteratively updating the policy such that it maximizes the return over local neighbourhood of the current policy (Kakade, 2003; Peters et al., 2010; Pirotta et al., 2013; Schulman et al., 2015). Using the methodology of Constrained Policy Optimization (CPO, Achiam et al., 2017), we present a result that extends the trust-region based updates to our setting with fairness constraints.
Proposition 4.1. Let and n' denote two arbilvary policies such that there erists only one subgroup for which the associated policies differ, i.e., B=r E n, + T/. Then for any j Z Z # i, the policy performance difference J. [(1k;)) - ((T;:)) associated with ni and nt is bounded as:
V21er'
J & n
E and? annt .r.
A (5, + (1 (1- v (KI(T((1m:)55)
[ (als)
V2reI (1-7) (DKc(T(1T))1)
J 2 J.j
E and
A7(5,a;))
1
where 5T' max; [awn; [A] (8, (, az r)],, and DEL. denotes the KL divergence.
10

---

Published in Transactions on Machine Learning Research (04/2023)
The proof is provided in Appendix E. This result allows to quantify the difference in returns of two different policies associated with a particular subgroup (T4, ma) ma) without the need of sampling from the distribution di Therefore, these computable upper and lower bounds can be used to control the performance difference and enforce the fairness requirement.
Let Hl denote the class of parameterized policies and o denote the policy for subgroup i at some iteration k. The trust-region based update procedure for updating o. takes the following form:
R+1
arg max H. (x.
E annd *
(8,
(10)
A (5,a;T) Se
s.t. u. R. +u E Brud?" amit
vj + iije 2,u u {-1,1)
where (xI(F.lIT)) = snadt [xx[(T]]
hyper-parameter that controls the size of the trust-region update, and u is an indicator for incorporating both upper and lower bounds.
4.2 Practical algorithm
Consider the scenario where each subgroup's policy is parameterized independently, for instance, each of the subgroup can have their separate neural networks. If the optimization problem in Equation (10) can be solved exactly, then we can use it as an inner loop of an algorithm that updates only one subgroup's policy at a time while ensuring that each update satisfies that fairness requirement.
In practice, solving Equation (10) is usually quite challenging as roquires inverting the high-dimensional Fisher information matrix, which makes it computationally expensive and difficult to implement. It is possible to devise approximate analytical solution based on Taylor approximations (Achiam et al., 2017; Yang et al., 2020), but that requires approximating the Hessian. Therefore, focus approaches that only rely on the first-order gradient information and make approximations around that. We consider two such approaches and describe them briefly below:
This category of methods solves the optimization problem first in the non-parametrie policy space and then projects the computed non-parametric solution policy back to the parameter space (Abdolmaleki et al., 2018; 2020; Zhang et al., 2020). We use the methodology from First-Order Constrained Optimization in Policy Space (FOCOPS, Zhang et al., 2020) and give the full details on how the FOCOPS approach can be used in our setting in Appendix F.1.
baseed approach:
Lagrangian- approach: There also exists penalty-based approaches that convert the problem into single objective via the Lagrangian method (Tessler et al., 2018; Chow et al., 2017; 2019), where the penalty coefficient is also updated at every iteration to enforce the constraints. Full details of the Lagrangian method can be found in Appendix F.2.
While both of the above approaches are easy to implement, the FOCOPS based approach provides approximate bounds on worst-case constraint violation, whereas that remains an open question in the case of Lagrangian methods, The complete algorithms are presented in Appendix F.
4.3 Deep-RL experiments
Environments: For the first set of experiments, we modify the Half-Cheetah-v33 environment from the OpenAl gym (Brockman et al., 2016) to create two additional subgroups with different dynamics: one with 2x the feet. size of the default. Half-Cheetah-v3, and another with 10x friction than the default setting. We use the default reward function across all the three subgroups.
We also design a navigation task based on Point environment (Duan et al., 2016), where we have two different subgroups corresponding to two different sizes of the Point agent (default and 5x). The task is to navigate
11

---

Published in Transactions on Machine Learning Research (04/2023)
302
352
300
402
120
202
130
200
300 200
(a) 10x friction
(b) 2x feet size
(c) Default size
(d) 5x agent size
Figure 3: Different environments for the DeepRL experiments: Half-Choctar variation with 10x friction but default size (Figure 3b) and the 2xfeet size (Figure 3a), and Navigation enviromments with default size point agent (Figure 3c) and 5x size (Figure 3d).
through the maze to reach the goal located in the top-left location. The agent receives a per-step penalty of -0.05, and reaching the goal leads to reward of +1.0 and episode termination. Additionally, there are two different openings of different sizes in the maze. The smaller point agent can pass through the smaller opening on the left (Figure 3c) lcading to episodes of smaller length (and higher return), whereas the larger agent needs to navigale through the opening on the right (Figure 3d) to reach the goal leading to a relatively longer episode length (and lesser return). Note that, for both the environments we do not make any distinction between the agent and docision-maker's reward, i.c., r r.
Baselines: We benchmark different variations of the Proximal Policy Optimization algorithm (PPO, Schulman et al., 2017). We follow the methodology described in Section 4.2 to get two fair versions of the PPO algorithms: FOC-PPO (projection based) and Lagrangian- PPO (Lagrangian based). We also include the traditional PPO algorithm as a baseline to get an estimate of the trade-off in performance due to the fairness requirement.
Results: For both the experiment settings we compare the baselines across three different levels of fairness thresholds (e E (high, medium, low3). Due to space constraints, we present only selected results that highlight the representative behaviour among the different environments and e configurations. We report the results for all configurations in Appendix G. For each iteration of the algorithm, the same amount of training data is used for every subgroup's 's policy update. Note that PPO bascline is agnostic to the fairness threshold and therefore its behavior does not vary across changing
A high e value denotes the scenario where the acceptable fairness gap is so large that it can never be violated during learning (Figure 4a). We observe that both the algorithms are able to perform competitively with PPO, with the latter performing slightly better than the rest. Both the medium and low e values denote the scenario where the algorithms need trade-off the performance for fairness satisfactions. In Figure 4b, we see that the traditional PPO bascline ends up violating the fairness constraint whereas both Lagrangian-PPO and FOC-PPO are able to satisfy the fairness constraints throughout learning. For the navigation environment, the initial random policy is exploratory enough to reach the goal faster for the smaller sized agents compared to the larger sized agents. As a result, our assumption about having an initial fair policy does not hold anymore in this task, and we observe a high fairness gap during the initial part of the learning for all the baselines (Figure 4c). In spite of that, as the training progresses Lagrangian-PPO and FOC-PPO are able to reduce this fairness gap the specified acceptable threshold and maintain over the course of training while reaching the goal state. Another interesting phenomena that we observe is the fair algorithms delay the learning for the smaller agents subgroup until the larger groups have learned to reach the goal consistently (the dip in learning curve of smaller subgroup in the rightmost subplot in Figure 4c).
Across the different experimental selting,, we observe that both FOC-PPO and Lagrangian-PPo are able to satisfy the fairness guarantees, with the performance of FOC-PPO only marginally better than Lagrangian- PPO in terms of cumulative returns. More dctails about the experiments, including environment and architecture details, Syper-parameter selection procedure, generalization analysis and results with a minimal implementation of the PPO baseline, be found in Appendix G.
12

---

Published in Transactions on Machine Learning Research (04/2023)
Falmess gap,
subgroupe
Big-feel subgrouu
High-friction subgroup
Default subgroup
Cumu metum
Eswodic retum
Estodo robu
Difirrnnce
Eocoddo
Timb
POC-Pr
LagargansPig
PPO
(a.) Half-Cheetah variations with high fairness threshold (e = 10, 000).
Feirneee gap.
All subgroupe
Big-feet subgroup
High-frictio subgroup
Default subgroup
8
Epioode cenodieeettrr returrr
Epiiodio
Diferencc
T mm--llaa
Time-lapa
Time-stage
Tima-stapa
Time-stapa
FOC-FO
LPgonsannFOO
(b) Half-Cheetah variations with medium fairness threshold (e 1000).
Falmess gap.
All subgroups
Big size subgroup
Default size subgroup
Dimononnss in ratuma
Cumuuldivee relurn
Epieadic relum
36
Time-etops
Time-steps
Time-stepe
Lagrangian
(c) Navigation task with low fairness threshold = 0.5).
Figure 4: Learning curves for different environments with different. fairness thresholds. The first subplot each row denotes the fairness gap (maximum of absolute difference of returns between subgroups) and the black dotted horizontal line denotes the specified acceptable fairness threshold (c). The second subplot in each row denotes the cumulative return for all subgroups, and the rest of the subplots in the row denote the subgroup specific returns. The x-axis denote the number of samples used during the learning. The solid colored lines represent the smoothed mean over 10 random seeds for different baselines (with weight=0.9) and the colored shaded regions represent the normal 95% confidence interval. Plots for running mean over the last 100 episodes are included Appendix G.
5 Discussion
In this work, we pose and study the problem of satisfying group fairness requirement in the online RI. setting where unfair decisions should be avoided throughout learning, Our main contribution is to show we can leverage methods from the constrained MDPs literature to satisfy this problem leading to new algorithmic solutions to this open problem. We also provide empirical evidence in support of our proposed algorithms on a variety of synthetic domains: discrete classic control tasks, continuous control robotic locomotion and navigation lasks, with extensive complementary analysis in the appendices. We based most of our empirical studies traditional RL domains, which convenient to validate the properties of our algorithms, but where fairness is not an inherent issuc. The next step is to apply our techniques in real-world domains where fairness the primary concern.
As mentioned in Section 1.1, a limitation of our work is that we enforce the fairness constraints only via restricting the policy space. This is also reflected in the navigation experiments Section 4.3, where we observe that our methods end up penalizing the higher- performing subgroups to match the performance of the perforiperoo subgroups. An interesting future line of work can be explore ways to increase the
13

---

Published in Transactions on Machine Learning Research (04/2023)
performance of the lower-perfomiin possibly by modifying the environment itself. Consider the scenario where the system designer has some partial control over part of the environment dynamics and can decide to modify them by paying some cost. In this setting, the task becomes to find a configuration of the environment along with a policy such that the resulting system is fair and allows various subgroups to achieve similar levels of high performance.
However, the problem described above is significantly harder than the problem we originally considered in Section 2. As the agent decisions can change the environment dynamics itself, all the past experiences of the learning algorithm can become obsolete unless we introduce even stronger assumptions regarding either the environment or initial fair exploration policies. If the system designer can afford to relax the requirement of not violating any fairness constraint during the learning procedure, then we should be able to leverage the recent advances in configuring environments via RL to take a step toward this problem of inclusive environment design. For instance, the framework of Configurable MDPs (Metelli* et al., 2018; Metelli et al., 2019) provides tools for finding the environment and policy configuration that achieves maximum performance in absence of any other constraints. We conjecture that. their methodology can be used in conjunction with our work but we leave that for future work.
We acknowledge that Assumption 2.3 is indeed strong. However, as we mentioned in Section 2, this is necessary for RL algorithms that do not violate the fairness constraints during the entire learning procedure. A promising approach towards the practical relaxation of this assumption can be to consider the setting where instead of having access to an explicit fair policy, the learning algorithu has access to an offline dataset collected under some fair policy. The recent advances in policy muning and hybrid-RL methods (Xie et al., 2021; Wagenmaker and Pacchiano, 2022; Song et al., 2023) indicate that we might be able to extract approximately fair policy from the offline dataset. We can then use the extracted policy to initialize the algorithm in Section 3, but further studies need to be conducted regarding the impact of such an approach on regret and fairness guarantees.
We also note that our results regarding the regret bounds in Section 3 can be improved further by using Bernstein's 's catcontration inequalities- analysis (Maurer and Pontil, 2009). This is a known result traditional MDPs (Azar et al., 2017) and has also been applied in the CMDP setting (Efroni et al., 2020; Bura et al., 2022). We leave this for future work, as our primary focus is not to improve the results in the exploration of CMDPs but rather to show how these results can be extended to different setting where they are traditionally not employed.
Our work docs not impose any structure on the environment or the subgroup dynamics, and as such, it is difficult. to do something different than treating them independently. Considering structured problems is another interesting avenue for future rescarch as well as identifying common parts of the dynamics (if possible). A more interesting setting would be one in which some information-shaaring between groups is possible, e.g. while there might be some differences in the dynamics for each group, there is some similarity, so information on the performance of one group could be used to learn for another group.
Finally, our analysis is limited to discrete subgroups, which corresponds to precise fairness criteria. Future work should investigate broader notions of fairness, and extensions to the multi-agent and multi-objective settings where subgroups can have conflicting interests or shared global resource constraints.
Broader Impact Statement
Our algorithms can help in reducing a particular notion of bias (group based) during the learning for the RL based systems (Sections 1 and 2). We also provide the conditions under which the proposed algorithms can attain these theoretical guarantees (Section 3). As mentioned in Sections 1.1 and 5, our notion of fairness is enforced by penalizing the members of the highest performing subgroup to match the performance of the lowest performing subgroups (within some margin). Therefore we caution against deploying our algorithms in settings where such notion of fairness might not be suitable.
14

---

Published in Transactions on Machine Learning Research (04/2023)
Acknowledgments
The authors would like to thank NSERC (Natural Sciences and Engineering Research Council), IVADO (Institut de valorisation des données) and CIFAR (Canadian Institute for Advanced Research) for funding McGill in support of this research. The computational component of this research was enabled in part by support provided by Calcul Québoc (www. www.ccaalllqueeec.coom ca), Compute Canada. (www. www.conputecanaaa.co ca) and Mila's s IDT team.
15

---

Published in Transactions on Machine Learning Research (04/2023)
References
Abdolmaleki, A., Huang, S., Hasenclever, L., Neunert, M., Song, F., Zambelli, M., Martins, M., Heess, N., Hadsell, R., and Riedmiller, M. (2020). A distributional view on multi-objective policy optimization. In International Conference on Machine Learning, pages 11 22. PMLR.
Abdohmaleki, A., Springenberg. J. T., Tassa, Y., Munos, R., Heess, N., and Riedmiller, M. (2018). Maximum posteriori policy optimisation. XrXiv preprinl 10011806..000 180:080000020.
Achiam, J., Held, D., Tamar, A., and Abbecl, P. (2017). Constrained policy optimization. arXiv preprint 170.:1005.1000
Altman, E. (1999). Constrained Markov decision processes, volume CRC Press.
Amani, S., Alizadeh, M., and Thrampoulidis, C. (2019). Linear stochastic bandits under safety constraints. arXiv preprint ar Xiv: 100.00800 05814.
Andrychowicz, M., Raichuk, A., Stanczyk, P., Orsini, M., Girgin, S., Marinier, R., Hussenot, L.,, Geist, M., Pictquin, O., Michalski, M., et al. (2020). What matters in on-policy reinforcement learning? large-scale empirical study. arXiv preprint arXi::2006.0330 05990.
Auer, P., Jaksch, T., and Ortner, R. (2008). Ncar-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21.
Awasthi, P., Cortes, C., Mansour, Y., and Mohri, M. (2020). Beyond individual and group fairness. arXiv preprint (rXi::2008.09490
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages
PMLR.
Bellman, R. (1957). A markovian decision process. Journal of mathemalics and mechanics, pages 679 684.
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016).
Openai gym. orXiv preprint ar Xrx::11666. Xix::1606.01540. 01540.
Bura, A., Hasanzadezomuzy, A., Kalathil, D., Shakkottai, S., and Chamberland, J.-F. (2022). Dope: Doubly optimistic and pessimistic exploration for safe reinforcement learning, In Advances in Neural Information Processing Systems.
Castelnovo, A., Malandri, L., Mercorio, F., Mezzanzanica, M., and Cosentini, A. (2021). Towards fairness through time. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 647-663. 663. Springer.
Celis, E., Mchrotra, A., and Vishnoi, N. (2019). Toward controlling discrimination in online ad auctions. In International Conference on Machine Learning, pages
PMLR.
Chouldechova, A. (2017). Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 6(2):153-163
Chow, Y., Ghavamzadeh, M., Janson, I.., and Pavone, M. (2017). Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070
6012) 6120.
Chow, Y., Nachum, O., Faust, A., Duenez-Guzman, E., and Ghavamzadeh, M. (2019). Lyapunov-basod safe policy optimization for contimuous control. arXie preprint orXiw:1901.1009.
Curi, S., Bogunovic, I., and Krause, A. (2021). Combining pessimism with optimism for robust and efficient. model-based deep reinforcement learning. arXie preprint or 0iv::21033.1036
D' A'mouu,, A., Srinivasan, H., Atwood, J., Baljckar, P., Sculley, D., and Halpern, Y. (2020). Fairness is not static: deeper understanding of long term fairness via simulation studies. In Proceedings of the 2020 Conference Fairness, Accountability, and Transparency, pages 525-534.
16

---

Published in Transactions on Machine Learning Research (04/2023)
Dann, C., Lattimore, T., and Brunskill, E. (2017). Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Xiviv preprint or Xin: 0mm:1733007100
Dastin, J. (2018).
Amazon
scraps
secret
recruiting tool that https: www. reuters, com/ article/
showed bias against
women.
us us=amazon-com-
20tool-that--hooee-- -aoiisssaggaainn wwwaaaanttoameseeeeeaaaa (dmtemennnidUSSKKMMKMK.K..
Datta; A., Tschantz, M. C., and Datta, A. (2015). Automated experiments on ad privacy settings: A tale of opacity, choice, and discrimination. Proceedings on prisacy enhancing technologies, 2015(1):2--112
Diamond, S. and Boyd, S. (2016). CVXPY: A Python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5 5.
Doroudi, S., Thomas, P. S., and Brunskill, E. (2017). Importance sampling for fair policy selection. Grantee Submission.
Duan, Y., Chen, X., Houthooft, R., Schulman, J., and Abbeel, P. (2016). Benchmarking deep reinforcement learning for continuous control. In International conference on machine learning, pages 1329 1338. PMLR.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012). Fairness through awareness. In Proceedings of the 3rd innovalions in theorelical computer science conference, pages 214 116.
Efroni, Y., Mannor, S., and Pirolta, M. (2020). Exploration-exxplottaiion coustrained mdps. arXiv preprinl arXiv:2003.0211
Emelianov, V., Gast, N., Gummadi, K. P., and Loiseau, P. (2020). On fair selection in the presence of implicit variance. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 649-675.
Engstrom, L., Tlas, A., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L.,, and Madry, A. (2020). Implemen- tation matters in deep policy gradients: A case study on ppo and trpo arXiv preprint ar Xix:22005.12799
Feldman, M., Friedler, S. A., Moeller, J., Scheidegger, C., and Venkatasubraamaiin, S. (2015). Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 259 268.
Fu, Z., Xian, Y., Gao, R., Zhao, J., Huang, Q. Ge, Y., Xu, S., Geng, S., Shah, C., Zhang, Y., et al. (2020). Pairness-aware explainable recommendation over knowledge graphs. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 69 78.
Fuster, A., Goldsmith-Pinnhamn. P., Ramadorai, T., and Walther, A. (2022). Predictably unequal? the effects of machine learning on credit markets. The Journal of Finance, 77(1):5-47.
Gajanc, P., Saxena, A., Tavakol, M., Fletcher, G., and Pochenizkiy, M. (2022). Survey on fair reinforcement learning: Theory and practice. arXiv preprint mxXi::2205.100..
Garg, N., Li, H., and Monachou, F. (2020). Dropping standardized testing for admissions trades off information and access. arXiv preprint arXim:2010.04300
Hardt, M., Price, F., and Srebro, N. (2016). Equality of opportunity in supervised learning. arXiv preprint wrXi::1610.02413.
Huang, S., Dossa, R. F. J., Ye, C., and Braga, J. (2021). Cleanrl: High-quality single-file implementations of deep reinforcement lcarning algorithms.
Immorlica, N., Ligett, K., and Ziani, J. (2019). Access to population-level signaling as a source of incquality. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 249-258.
Jabbari, S., Joseph, M., Kearns, M., Morgenstern, J., and Roth, A. (2017). Fairness in reinforcement learning. In International Conference on Machine Learning, pages 1617-1626. PMLR.
17

---

Published in Transactions on Machine Learning Research (04/2023)
Kakade, S. M. (2003). On the sample complerity of reinforcement learning. University of London, University College London (United Kingdom).
Kanagawa, Y. and Kaneko, T. (2020). Diverse exploration via infomax options. arXi preprint arXiv:2010.02556.
Liu, L. T., Dean, S., Rolf, F.,, Simchowitz, M., and Hardt, M. (2018). Delayed impact of fair machine learning. In International Conference on Machine Learning, pages 3150 3158. PMLR.
Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C. (2021). Learning policies with zero or bounded constraint violation for constrained mdps. arXiv preprint arXiv:2106.022
Mandal, D. and Gan, J. (2022). Socially fair reinforcement learning. orXiv preprint arXiv:2208.1258.
Maurer, A. and Pontil, M. (2009). Empirical bernstein bounds and sample variance penalization. arXiv preprint arXi:00907.3740.
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., and Galstyan, A. (2019). A survey bias and fairness in machine learning. arXiv preprint 1908:
Metelli, A. M., Ghelfi, E., and Restelli, M. (2019). Reinforcement learning in configurable continuous environments. In Proceedings of the 36th Internalional Conference on Machine Learning (ICML), volume 97, pages 4546-4555. PMLR.
Metelli*, M., Mutti*, M., and Restelli, M. (2018). Configurable markov decision processes. Tn Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pages 3488-3499
Miller, C. C. (2015). Can an algorithm hire better than a human. The New York Times, 25.
Nabi, R., Malinsky, D., and Shpitser, (2019). Learning optimal fair policies. In International Conference Machine Learning, pages 4674-4682. PMLR.
Pacchiano, A., Ghavamzadeh, M., Bartlett, P., and Jiang, H. (2021). Stochastic bandits with linear constraints. In International Conference on Artificial Intelligence and Statistics, pages 2827-2835. PMLR.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. (2019). Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32.
Pessach, D. and Shmueli, E. (2020). Algorithmic fairness. arXiv preprint arXi::2011.09784
Peters, J., Mulling, K., and Altun, Y. (2010). Relative entropy policy search. In Senenly-Fourrte AAAI Conference on Artificial Intelligence.
Pirotta, M., Restelli, M., Pecorino, A., and Calandriello, D. (2013). Safe policy iteration. In International Conference on Machine Learning, pages 307-315. PMLR.
Pleiss, G., Raghavan, M., Wu, F., Kleinberg, J., and Weinberger, K. Q. (2017). On fairness and calibration. Advances in neural information processing systems, 30.
Puranik, B., Madhow, U., and Pedarsani, R. (2022). Dynamic positive reinforcement for long-term fairness. In ICML 2022 Workshop on Responsible Decision Making in Dynamic Environments.
Puterman, M. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015). Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. Xiu preprint arXi::1777.066347
18

---

Published in Transactions on Machine Learning Research (04/2023)
Siddique, U., Weng. P., and Zimmer, M. (2020). Learning fair policies in multi-objective (deep) reinforcement learning with average and discounted rewards. In International Conference on Machine Learning, pages 8905 8915. PMLR.
Song, Y., Zhou, Y., Sekhari, A., Bagnell, D., Krishnamurthy, A., and Sun, W. (2023). Hybrid RL: Using both offiine and online data can make RL efficient. In The Eleventh International Conference Learning Representations.
Strehl, A. L. and Littman, M. L. (2008). An analysis of model-based interval estimation for markov decision processes. Journal of Compuler and System Sciences, 74(8):1309-153 1331.
Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine learning, 3(1):9 44.
Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
Tessler, C., Mankowitz, D. J., and Mannor, S. (2018). Reward constrained policy optimization. arXic preprint WrXii:1805.1107)
The European Commission (2021). A european approach to artificial intelligence. https: // Nigital-strategy. ec. europa. eu/ en/ ptw.cielceee//op paropean-approache wtwpacc--rrriiicaa-meeleleeeeeee
Todorov, E., Erez, T., and Tassa, Y. (2012). Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference Intelligent Robots and Systems, pages 5026 5033. IEEE.
Wachi, and Sui, Y. (2020). Safe reinforcement learning ronstd markov decision processes. Tn International Conference on Machine Learning, pages 9797 9806. PMLR.
Wagenmaker, A. and Pacchiano, A. (2022). Leveraging offline data in online reinforcement learning. arxiv preprint arXiv:2211.04974
Wen, M., Bastani, O., and Topeu, U. (2021). Algorithms for fairness in sequential decision making. In Banerjec, A. and Fukumizu, K., editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1144-1152. PMLR.
Xie, T., Jiang, N., Wang, H., Xiong, C., and Bai, Y. (2021). Policy finetunigg Bridging sample-efficient offline and online reinforcement learning. Advances in newral information processing systems, 34:27395-27407,
Yang, T.-Y., Rosca, J., Narasimhan, K., and Ramadge, P. J. (2020). Projection-based constrained policy optimization. arXiv preprint ar xrXi:2210.000 03152.
Zafar, M. B., Valera, I., Rogriguez, M. G., and Gummadi, K. P. (2017). Fairness constraints: Mechanisms for lair classification. In Artificial Intelligence and Statistics, pages 962 970. PMLR.
Zhang, Y., Vuong, Q., and Ross, K. W. (2020). First order constrained optimization in policy space. ar preprint 2xfr:2002.06506
Zimin, A. and Neu, G. (2013). Online learning in episodic markovian decision processes by relative entropy policy search. In Newral Information Processing Systems 26.
19

---

Published in Transactions on Machine Learning Research (04/2023)
A
Notation
Table 1: Notation
General MDPs:
denotes the entire MDP
S
stale-space
A
action-space
initial starting state distribution
reward function (can be non-stationary (s a) stationary r(s.a))
H
horizon length for finite-horizon episodic MDPs
P
transition model (can be non-stationary (s a) or stationary p())(s,))
policies (can be stationary T (aas) or non-stationary ne (a(s))
S.
state observed at time step action taken at time step h reward observed at time step value function under policy starting at state at time step h for MDP with reward function and transition P
Ah
(s;r,)
return of a policy π for MDP with reward function r and transition P d7 (5, P) occupancy measure of policy for state and action a at time step when starting with initial distribution μ and transition
(r,
Introducing fairness:
Z
set of sensitive attributes that define subgroups non-sensitive state space non-sensitive state observed at time step
$
St
subgroup specific initial non-sensitive starting state distribution
Pa
subgroup specific transition function corresponding to the non-sensitive altributes
Pz. (8)3,8))))
P)
return for a subgroup under policy æ with reward function r and transition Pa (starting
from p=)
policy corresponding to subgroup z
I
decision maker's reward function (can be non-stationary 41(s, or stationary ((s, a)) specified fairness threshold
0
initial feasible and fair policy fairness margin corresponding to n
Algorithm for the unknown model and reward setting:
noise in the observed reward confidence parameter empirical estimate of the reward function for time step h at episode k empirical estimate of the transition function for time step h at episode k uncertainly estimate for lime step h at episode k optimistically and pessimistically scaled reward estimates high confidence set consisting of fair policies optimistically scaled reward estimate scaling factor associated with exploration margin, 7) = (c-c) c))
pk
Pk
8k
k
TA
I
ph
Or
The infinite-horizon and high-dimelsional Deep- RL setting
20

---

Published in Transactions on Machine Learning Research (04/2023)
discount factor associated with MDP for the infinite-horizon setting sampled trajectory
(T)
horiion return under stationary policy x
(TL)
infinite-horizon return associated with subgroup z under policy a
())
advantage function under the policy T. for the subgroup 2
(({)) - JT,))
K
trust-region parameter
DKL
KL divergence
&
worst case error for subgroup in Proposition 4.1
Ilg
parameterized policy space
Linear Programming solution for
episodic MDPs
B.1
Linear Programming based solver
Note that any policy x Z x S [H] + AA can be decomposed into set of [Z] sub-policies. A policy associated with particular subgroup
Z is denoted with т2, where n. S [H] + AA: with (als) being the probability of taking action a in state (2 at time step h E [H]. Thus, the complete policy at an )
episode k E [K] is denoted by the n² =
The occupancy measure associated with a particular subgroup 2 E and its corresponding policy T= is defined as:
di as P.) = E[ = 8, A, = S Piz P.. n2l
(11)
Pr s, A₁ =a 81 u.. mg).
Similarly, the return associated with a particular subgroup w.r.t. a reward function g: 2 A can be written as:
(g P)
Σ
( a: M,, (2,
(12)
h,3,a
The subgroup specific occupancy measure should satisfy the properties of an occupancy measure (Zimin and Neu, 2013; Efroni et al., 2020), i.c.,
Σ dh (5, a) Σ
V S,
(13)
8',a'
dh (3,00 a) 20
Vā,a E S x A.
for all h E [H) 1. For and corresponding initial distribution Øz, we have
Σ
c (3.a) = -x)
V3.
(14)
For any policy и and 2, a, h E Z 5 Ax [H] we define the combined occupancy measure over the entire orginal state-space S as:
di ((2, 3), a) Pr(2) (3.
(15)
We show that the final occupancy measure returned by the above formulation satisfies the properties of a valid occupancy measure in Lemma B.1. This allows us to reformulate the problem in Equation (2) to a Linear Program where the optimization variables are measures. The optimal solutions to the LP define the optimal Markov policy through occupancy measure where,
($,
T T = E. di (3,a')
((.. Ax [H].
(16)
21

---

Published in Transactions on Machine Learning Research (04/2023)
The final LP program takes the following form:
max
Σ Σ (())
(17)
s.t.
dk (5,
Σ (8, Se
Vizj; (1,5) E z
3,3,a
b,5,a
(r,P)
(r.)))
Σ ch - (3.a)
2x x [H]
3/,a
Σ di (5, (3)
Ex
(3,
V2, Exla,hexSSxxn
Finally, Proposition B.1 (bclow) we show that the above LP is able find the solution of the problem in Equation (2).
B.2 Supporting results for LP formulation
Lemma B.1. For any policy n, the occupancy measure d= Equation (15) valid occupancy measure and satisfies the following properties of an occupancy mensure:
Σ [ =1
4h [H]
(18)
8,0
Σ (s)))))== = -
(19)
s'.0
(7,)))) (((s,)200 20
Vs, xxa.h
(20)
Proof. Recall that, for any policy and 2,3, x 8 Ax [M], the combined occupancy measure S is defined as (Equation (15)):
(()(,)), (((e))))))=p(((<<<<)))) di (5,0)
(21)
Part 1: From Equation (13) we know that for any E 2,
(5, 20
Va, 8 [H]
As, Pr(z) 20, Vz 2
Pr(:)d (5, 2
V2, e x 5 x
(H).
()) 2
V2, E (2 x 5) x A x [H]
(s, 0
Vs, E A x [1],
which implies that the property in Equation (20) is valid.
Part 2: From the construction in Equation (13) we know that for any 2 E Z
Σ (3, = ,7
43, h
3'a
The above equation can be rewritten as,
Σ
(3 Σ Ph-1(32,,3, =/10;
V2, 8, h
4
2.8.aa
22

---

Published in Transactions on Machine Learning Research (04/2023)
Multiplying both sides by Pr(z), get:
(3( = Σ
V2, 8, h
8',8'a a'
Replacing Pr(z)d, (5, by (2, a) from Equation (15):
Σ ()) = [[]
V2, h
8',8'
As we are only considering case where z' = 2 in RHS (due to 1[2 2')), we can replace d% ,') with ( (2',,','')
[.( EE -
Vz, 8, h
From the definition of transition function in Assumption 2.1 and substituting (z', 8) with s', we gel:
Σ di ((, ΣΣ
Pa-1 (2,8 8 ( (=',8',
Y2, 8, h
2/88'
Σ (s,0)) = ΣΣ ( 155 (d')d')
4s, h
8'
Hence, the property in Equation (19) is also valid.
Part 3: We show the property in Equation (18) true using induction. First for the base case fix = 1,
and we need to show Eno di a) =1
Σ dis,a) E Σ d (s
Σ (
(by definition of d" eq. (21))
= Σ> Σ Pr(z)
d (3)
By conston (Equation (14)), we have En (3, = (8), V8, therefore:
ΣΣ (r())
From Definition 2.1, we have u(z, = (r()) or Exez = -Ere (z))) Therefore, we get:
Σ ds = ΣΣ ((2.8)
= 1
(By definition of μ)
We have shown that En, di (s) = 1. Note that have already proved that Equation (19) is true. For
h 2, Vs E S, we have:
(s, = Σ dl
23

---

Published in Transactions on Machine Learning Research (04/2023)
By summing E S, we get:
(s) Σ Σ Pi(sss',
s'
Σ di (s',a')
Similarly, by summing over the first constraint in Equation (19) over s for different values of iteratively we can show that Σ.,a df (8, a) = 4h Thereefr,,,, d' valid probability measure.
Lemma B.2. For any policy and any arbitrary reward function g [M] 8 A R, have the following relation between the cumulative return and subgroup specific returns:
() = Σ (r
Proof.
[" Σ
b,2,8,a
Σ (),,)
h,a 2,8
(z)
(From Equation (15))
b,a
Σ Pr(:) Σ
((,
h,0,3
Σ (r(
(From Equation (12))
Proposition B.1. The LP Equation (17) returns the solution π² to Equation (2).
Proof. Let x² denote the optimal solution Equation (2), and let æ' denote the solution returned by the LP. Note that the problem is feasible due to Assumption 2.3.
As -" is the solution to Equation (2), it must satisfy the fairness criteria and have valid occupancy measure. From Lemma B.1 and the fairness constraint in the construction of LP (the first constraint in Equation (17)), all the valid occupancy measures that satisfy fairness constraint are feasible points in the LP. As occupancy measure corresponding to л a fcasible point the LP, we can denote its return as J (1,
If x' is the solution returned by the LP,, that implies that x' satisfies the fairness criteria and also has the maximum return over all the feasible points, i.e.,
However, '²" is the solution Equation (2), therefore n' must also be a solution Equation (2).
24

---

Published in Transactions on Machine Learning Research (04/2023)
B.3 Extension to other Group fairness definitions
For all the valid A the Linear Program for the Demographic parily based fairness constraints can be written in the following form:
max ΣΣ (()a,,))
(22)
A,2,8
Σ (,, (5, (),,5)(()
E4(65.aan h,5,a
Vi 2 (1.5) E z².
s.
A,3.a
= Jp(r,P)
Equality of Opportunity: Informally, this fairness constraint is defined having equal rates measure (such as true positive rate) for the qualified sub-populations for all subgroups (Hardt et al., 2016). In our setting, this implies that the subgroup space (2) can be further decomposed into qualified (21) and unqualified (Zo) groups, ie., 2 x Zo.
For all the valid Λ the Linear Program for this definition takes the following form:
max Σ
Σ
dh ((2, 8), ((2)((2))).0)
(23)
h,2,8
s.t. -)
Vi M ji (i,j) z
Note that the only difference of the above equation with with Equation (22) is that the constraints are defined only for the pairs belonging in the qualified subgroups (Z1) instead of pver all possible subgroups (Z).
Equalized Odds: This fairness constraint similar to the Equality of Opportunity case, with the difference that it requires equal rates mcasure for both the qualified and unqualified population for all subgroups (Hardt et al., 2016). Assuming, Z Z Zo, the Linear Program takes the following form Vi A
max Σ
dh ((z, 5), a)4, ((2,8),0)
(24)
h,2,8
s. t.
(r; -) (r, P) St
Wi (1,j) E 27.
(T - Jr, P) Se
Vi WiJj; (i,j) E 2/.
The main difference between the three formulations Demographic parity (used our main paper), Equality of Opportunity and Equalized Odds-is the number of subgroup pairs on which the constraint is being defined. In Demographie parity, all the possible combinations two definitions only a proportion of the possible pairs is included in the constraints. Thus, approach can be transferred directly to other settings by appropriately removing the unnecessary constraints for each definition.
being considered, whereas in the other
C Proofs for episodic case
C.1 Why optimism alone might not be enough
The core idea in optimism-based approaches to select the MDP model that yields the best return among the set of all possible MDP models. Let pk, R² and _ denote the confidence sets based empirical estimates that contain the true transition and reward models with high confidence. Thus, by using only the optimism in the face of uncertainty approach, the policy to execute at episode k can be found by solving the following problem:
* k pk
J'),
arg max PECER EP
s.t. -
N2J,E Z
25

---

Published in Transactions on Machine Learning Research (04/2023)
However, the solution policy from the above optimization problem only guarantees the constraint satisfaction w.r.t. to the best optimistic MDP model and not the true MDP. To expand, we can get guarantees on [J]" (r", Jÿ (rh, Ph),, whereas we are interested in the guarantees on [ Pr P) JJ (r. P)L-
C.2 High probability good event
We follow the notation and proof technique from Liu et al. (2021) for this section. The goal to have high confidence guarantees based some probability parameter 0 < 5 < 1 given by the user. In order to do that, we first define high probability event & that is required for analyzing the performance guarantees of the algorithm.
Let {Frlk20 denotes the filtration with = a ( 2K AA R I. )ee( wk [K] and Fo being the trivial sigma algebra. The set of deployed policies [>"]ee( is a predictable process w.r.t. filtration (a2o Recall that (2, 8, a) is the number of times the state-action tuple (2, was observed at time step h in the episodes [1....,k k - 1]. Thus, (2, 8, a) E FR-1-
In our setting, the algorithm has access to jız and additionally we sample 2 ~ 2 uniformly for each episode, or Pr(z) = 1/1zj, Vz. Therefore, the joint je is also accessible as y(z, = (3V2), Z x & (Definition 2.1). We can therefore define the expectation operator Ey.P,-|] w.r.t. stochastic trajectory (S,, Aeu according to Markov chain induced by (H, mT). Next we formally state the noise assumption on the reward function,
Assumption C.1 (Sub--aaussian-noiss)) We assume the reward noise voriables are zero mean 1/2-sub- Goussian, i.e., Fi-h| = O, EEeexp(Ach) S (op(A>/4),W) AA E IR, where Fu denotes the alaggeraa generated by random variables up to episode k wh E [H],k k E [K].
Therefore, for each (z, 8, a, h) E 2 x $ x [H], the empirical estimates of the rewards and transition based on the observations so far are defined as:
(12,8 E 1 (HK = SK = 8, A a, 2/
h+1 =', 2', 8¹)
(25)
max (Mx (2)
() = E 1 1(% 2, 5% 8, A/ = =0)(r(22, (,,,,,,))) max
(26)
(2, E 1(k = SK = A/ =0)(((2,8,,) + (2,,5, a))
(27)
(Nx
Next, for an event sequence SL.K, that is predictable w.r.t. {F)k2, i.e. Gh E Fx-1, Ak E [K], we define the event:
Eg(o) = VVK' E [K],
K' H
19 (z, 8)
< <4 + + In K'g + 4ln 2HK
max NZ (2,
1= h=1 2,
K' H
(g (z, 8,0)
ΣΣΣ
< 6H 6 Š|A + 2H /
max (2, 5, 1)
A= 1-1h=1aa 2,5
2HK
22| A In K3 + 5ln
8
where K2= = === 19)), and a=* is the occupancy measure of policy nh, ie, d (2,8,a) = P,r (1(2)
2, 2 A = F-1l
Let (n) be the event associated with the trivial predictable event sequence Ga = Ω. Vk E [K]. where Ω is the sample space. Similarly, let Gi,x- (JFF' (1** pk) - J3 o (r p4) > (c (0)2) V (Jz"(1* (r pob " ph)) >
26

---

Published in Transactions on Machine Learning Research (04/2023)
(e + 2)/2), E Z KEjK, where v denotes the logical OR operator. Note that the event sequence KiK. is also predictable w.r.t. (Fu)uzo- Let (6) denote the event (g)(6) defined by the event sequence G.K.
Good event & is defined as:
8 (vA vk [K] vh [l] V 2 8,
(2(2,,,0) 5)), (,,,
( - (22, S (2,,,,))
(P2 - PR 2, a)l - (2, 3' 32 /
(
(28)
where (2, (2..a) C and C = 10g(4
Lemma C.1. For a given value of E (0, 1), the event. & occurs with probability at least
Proof. We can get the above results directly using Lemma A.1 (Liu et al., 2021). As the rest of our analysis is based on this good event, for completeness, we briefly present their proof extended to our setting below.
For each (2, h) E x x A [H], we first define dataset of K mutually independent samples of reward and next state collected under the true MDP model as (2 8, a, h), [, 8, a, h),, S (2, a, h) Let pm (" 8, a),,, in (2, 8, a, h) and P'[(|2, &, h) be the corresponding running empirical means for the samples h) We can then define the failure events:
[1' B, h), a,
F [3,, a [A, (2,2, 8(n).}
F [3z, 3, a, h (2, 8, - (1(2,, 2 {(n),)
(,0)) F.P = A2, 8, 0, 2 5 (1,, B())),
where B(n) V m) C. We also define another event,
UUUPUUUUUUUUOOO Egen = (Pr(U (P" U P.FF)) (e E
Let m,(2,5,a,) denote the quantity (2,5,) +
Then the problem our setting can be simulated as following: at an episode k taking action in state 2, time-step h, we get the sample (2, a, h), h), (,,(t,,,, 5, a, h), (tu(t,,,, (2, a, h)). Therefore, the set
(2, 8, h), (2(2,,, a),, h). S" 5, a, h)] already contains all the samples drawn in the learning problem and the sample averages calculated by the algorithms are:
(2, (1, At 8'1,,, (,)) (aro))))(("(((mmm) (1"(() (z, a, h,, mul..all (z, 8, a, h), (mn (1 h,)
As a result the Egen implies E, and it sufficient to show that Egen occurs with probability at least 8.
Using Lemma H.4 and union bound, we get the result that (g( Eo(//4) occurs with probability at least ž - 5/2 Next, we define 8' = 2(2))|)+2)) that satisfies the relation 8 1 < 8'. To see that,
2 2 2||5
(since | > 1)
46 < 26 2|
48 40 2
28 ž|
26([31|5) + 2) < 48 2|
8 8|2||
<
2( +2)
or,
< 8'.
4
27

---

Published in Transactions on Machine Learning Research (04/2023)
For Fi, by Hoeffding's Inequality and Union bound, we have:
8
8'
Pr(u )
|| (x)((=(()))())) = K| 4
12||5|
which is equivalent to the event Pr(u Fx) 2 bound, we also get:
8'
For F using Hoeffding's Inequality and Union
[2
8
Pr(um
& S = 4
S
12
which is equivalent to the event Pr(u n=1 F 21 Union bound, we get:
8'
Finally, for FP. by Hoeffding's Inequality and
2||S|
Pr(uk= < K| | exp(=n(((n))) S
Therefore for the event Pr F P U )) using the definition of 8', have:
) < Pr(u F.P) Pr(u F.) + Pr(u F.) s 8 (1+ (2|15)
5
2
Or, the event Pr UF ) 2 1- 8/22
Finally, combining the above results we get that the event Pr(u holds with probability at least 5 or Eoen holds with probability 1 1 6, that implies & holds with probability 1-5.
U.. UF (F n ( 246
All the results in the rest of this section are conditioned on the good event & defined above.
C.3 Supporting Results based on Optimistic and Pessimistic MDP Estimates
Recall that at an episode we define the optimistic and pessimistic reward estimates as following 8, (12,8,a,1) e Z S A x [H]
8), =
Lemma C.2. On good event E, for any policy and E Z, using the optimistic reward estimate leads to higher estimated return compared to the true return, i.e.,
Pr S (F ph).
Proof.
For any k, h, z, 8, a we assume the sample point w E E:
r)) - 1,,,,,,,,, = - =
(,(2,,,,) (1 + +2 rn(2,
(From definition eq. (3))
> (1 + (2155
(due E)
2 (2,
Additionally,
(8) Z
EPE -
H Σ =
28

---

Published in Transactions on Machine Learning Research (04/2023)
where (a) holds due to Holder's inequality. Using Value difference lemma (Lemma. H.2), for any policy a, have:
J (r": ph) (r P)
11
= E
(r, Sn, An) - (,, A,) +
(h Pa)(E', P1M P)) F/) ,'
Σ
H
2 E
S (2, Sn. Ad) - -215)11)H Sr Fk-1
Am
N 0.
Therefore we have,
(r P) S 15 Ph..
Lemma C.3. For ony policy ग and E 2, using the pessimistic reward estimate leads to lower estimated return compared to the true return, i.e., FO ph) S (r,
Proof. For any k, h, 8,a, a, we assume the sample point E &:
(, ()) = - r,,,,,,
-(1 [1=+ r2, 8,
(From definition eq. (3))
s (-1 2
(due to E)
Additionally,
H H H -21
where we get (a) via the Holder's inequality. Using value difference lemma (Lemma H.2), for any policy n, have:
1 (r PM) [r P)
E
(2, And - (2( + E(E
(e,,,, FM-1
2/.8'
< Σ
121|S H2, Sr, Av) + 12
H (2, Sm. Aw)
5.
Therefore,
G pb) < P).
Lemma C.4. For any policy n and E Z, the difference in returns using the optimistic reward estimate and the brue relurn can be bounded in terms of Bk as,
( fot) (r; P) 2 H (8 pK).
29

---

Published in Transactions on Machine Learning Research (04/2023)
Proof. For any k, h assume the sample point E:
= (
= 1,(2,
= (1+ += 3,),,3,a) $ (1+ (
(From definition eq- (3))
(due E)
I (2 + (2
Additionally,
Σ(P - 1 P) S H =',8'
- (2, 3,
2',8'
where we get (a) via the Holder's inequality. Using Value difference lemma (Lemma H.2), for any policy n,
we have:
J (F+, ph) P)
E
(z, Shy An)) (2,2, Sn, An) +
E(Ph -Pa)(E,, 8'12, As) ( PT)
21,3'
H
2(1 + ()) Sn. An)
S E
= 2(1 | H )ok).
Therefore we have,
JT pa) Jr, P) 21 +11))T))J p*).
Lemma C.5. For any policy and E Z, the difference in returns using the pessimistic reward estimate and the true return can be bounded in terms of 3h as,
J (r, P) (r pK) < 2(1 (8) ph)..
Proof. For any k, l,, 2, 8, a, we assume the sample point &: 3,,2,, (n(2, = 3, =
(2, -(1 2 -,, 5,a)
(From definition eq. (3))
2 (-1 - -205
(due to E)
2 -2 + (11
Additionally,
- - 31 T 2'.8
H H (2, = (1,
where (a) holds due to Holder's inequality. Using value difference lemma (Lemma H.2), for any policy n, have:
1 - P)
H
E
ch(2, Sn, And (2. Σ(P)
-PA-PP)(d P.)(2' 31.. (2',8,, Fr-1
H
E
Σ
-2 + | 121 Sn. An) Fm-1
1111
- 2 1 | PM))
30

---

Published in Transactions on Machine Learning Research (04/2023)
Therefore,
(r P) -) JE Ph) < 2(1 18 PM
C.4 Proof for Theorem 3.1
W.l.o.g, let {i,j] denote any pair of subgroups in 2 For TO we have [J," (r) J/ of initial fair policy (Assumption 2.3). We will now show that the our construction of II Equation (4)
(r, P)] I by definition
satisfies the zero constraint violation property for any such pair of subgroup.
Part 1: In the first part of the proof, will show that on the good event E, for any k E [K] and policy I E II,,
P)
Proof. Using Lemma C.2 w.r.t. 2 == i and F, we have:
ph)
(29)
Similarly, using Lemma C.3 w.rtt 2 == and r, we get (r pR) S JJ P), or,
Jf - J1( ph)
(30)
From Equations (29) and (30), we have:
JF - JJ ph.)
(31)
Note that from the definition of IT we know any policy in 1 satisfies the constraint:
(" (1 ph) se.
Therefore, we have the following relation:
(r, P) - JJ S) (T f - J7(1 (1",, ph) Se.
Part 2: Now we will present the result that shows on the good event E, for any k E [K] and policy a E 11$.
(r, P)
Proof. Using Lemma C.2 w.r.t. 2 = j and F, we have:
S PM)
(32)
Now, using Lemma C.3 w.r.t. and r, get (r² pk) S JJ (r, or,
JJ, P) < -J (1"1 ph)
(33)
from Equations (32) and (33), we have:
J(, pa) - JJ PM).
Note that from the definition of II,,, we know any policy in II's satisfies the constraint:
15 - J (rxt, ph) Se.
Therefore, we have the following relation:
J7 -
17 pry SM.
Se.
31

---

Published in Transactions on Machine Learning Research (04/2023)
Finally, we know that episode k, either x² policy from I will be deployed. We already know that [J (r, P)-J) JJ (r, P)] S by definition initial fair policy from Assumption 2.3. From the results from Parts and 2 above, we get that on the good event &, for any l E [K] and policy π E ny J7 P) - J (r, P) Se and (r, P) (r. (r. P) c, or,
JJ Jr, -J9 JJ (r,
The above argument holds truc for any pair of subgroups. Extending this argument to all the pairs of subgroups we get,
- (2,.((,))) E2?
C.5
LP formulation for Section
The algorithm in Algorithm 1 requires solving an LP that takes the following form:
max
Σ Σ
3), a(),))
(34)
h,2,3 a
s. s.t. Σ d (5, (3,
E oh (3.0)) h,a,a
#2 E,j,e E Z
b,3,0
PM)
(3.
de (3.
W2 i,j Z
h,3,0
Σ
h (8,0) = Σ
Pk (d)
&2,8, $ (H] \
8'a
Σ d (5, = (8)
()) 20
2 Ax [H]
C.6 Proof for Theorem 3.2
Change w.r.t. I.
When the fk f* parameters are not well estimated, the LP in Equation (34) might not be feasible itself. In that case, the only available policy to exccute is T0 and [T* As the algorithm proccods with gathering dala via executing xº, the Equation (34) event become feasible. However, the algorithm will continue to execute x even when the problem becomes feasible as long there exists at least one pair subgroup i, E 2 for which either J (7* pk)- -J -J (L*t, pk) 2 (e (e+e")/2 or JJ (Ft, (,) - JT ( (,*,pk) 2 (E + e e))2 (from the definition of I in Equation (5)). From Assumption 2.3, know that TO satisfies the fairness condition with strict inequality, or e < (c + +)/2 < c. Therefore, eventually after enough rounds of [T = 1, the above condition will be not valid anymore and at that point the algorithm can proceed with using solution based on the estimated parameters from Equation (34). Additionally, at that time, we know that all the policies that close enough to =0, which are infinitely many will also be feasible solutions or [I1 = =c.
We use the proof techniques from Liu et al. (2021) where we decompose the regret in three terms, then analyze each of individual terms separately and combine them later for the final result. First, notice that the
32

---

Published in Transactions on Machine Learning Research (04/2023)
regret can be decomposed as:
K
Reg(K;1) = Σ 1 (1, 5 - (
(1)
1(11 1) ( (LP) ("*, pt)
(1))
K
+
1(II" > 1) (rt - -
(35)
(111)
For the first term, we have the following result that gives an upper bound on the number of episodes required for exploration by T0.
Lemma C.6. On good event E, E 1 = S C", where
C" = (e - H
Proof. Recall that [[T*| when there is at least one pair of subgroups i,j g² for which the fairness constraint was violated w.r.t. T": J (T* ph) - J (r*t pk) 2 (e+ 22/2 V J7 (F) - J (c* ph) 2
(c+2 We will use the indicator 1[III* 1; to denote that if pair i,j violates this constraint.
Wlog, assume that a subgroup pair i,j 2 violates this constraint. Note that IIT = 1 if either of the following conditions is true:
(Case A) J (F* p (rk,pt
-J
2 (e2, which we will denote by the event 1([II*) = 1; Asg) =
I(J," (rh, ph)) - J5 (1=t, ph) 2 (e + 22) where n ==, and
(Case B) J5 (Th, J (,-h pk)= z (e + e)2 that is denoted by 1(II*) Br.).
In context of i,j, either of these two scenarios can be responsible for III* 1. Therefore, we have:
k
K
K 1 1(TT = 1; A;) + Σ 1 = 1; B,,))
1 ITT = 1;1,))
k=1
k=1
Now, we define K' = Eksl 1([IT* = 1;1,)). We have,
(e- )
K
1 1(IT%) = 1; (c- (
K" Σ
2
k=1
K
(c+ c9)
Σ
1(114) = 1;2,))
- cc))
2
K
(E+
[e+e])
Σ
1 Ais)
0
+ Σ
1 11 Bis)
-0)
2
k=1
k=1
33

---

Published in Transactions on Machine Learning Research (04/2023)
For the first term in the above equation corresponding to Case A, ii.. 1([IT) 1; Ai,), we have
1 1;),,) (E+te) -c0)
2
_ |(|1=11 = A(s) (NJF (Ft, (h)) - - (J) (r, - (r))
1
1; 1;; (J= (rb, J (r, (J) 1 1; (J (r, JJ (1),
A.I
A.2
where (a) holds because Th = TO when |IT = and J ( - JJ (h) 2 (c + e (from definition
of Case A), and J (r, P) - J () S e due to Assumption 2.3. For the A.1 term above, we will use Lemma H.3 with
Fh rul = 1 + (1+ 1 r
= | Th + (1 + H
S 8% + (1 + 2 $11
S (2 + HH)
Now we can directly apply Lemma H.3 to get the following result that bounds A.1,
A.1 A. ō H 1 + H /
Similarly for term A.2, we have:
k = |r - (hr - (1+12]))))) 1hh -nh
Ih PA +1+
S h (1+ H2(
< (2 + 1211)))))
Again applying Lemma H.3 we get,
A.2 Ô 0 12 1 (1SPIPPAAI)
Therefore,
Σ 1 = 1; A1.)
(l++0) .) =
- (11 HH2 /
2
The analysis for 1(1I*) 1; Br,)) is analogous and leads to the following result:
K 1 = 1: B1,)
(ktt)) -e) -2) =
H -
2
Combining the results for I 1 = 1; Ai.s) and 1([T*) = 1; Biy):
(c (c-c) c) K" = δ 0 ( |A| + H2 SPIEPLAAK
2
34

---

Published in Transactions on Machine Learning Research (04/2023)
Using Lemma H.5 for K', there exists some parameter C' such that,
@min ( ( e0)
H 11
K" C²=
Now we must consider that | = if the constraint w.r.t. TO in Equation (5) violated for any of the subgroup pairs. Note that we have the relation,
K
1
1)
Σ E =1(1))1;;1)))) 1;1,5) k
The inner term of the above expression can be bounded using the above result w.r.b. K'. We also know that the number of pairs of subgroups bounded by |2|?, therefore we have:
H 11
1 1) S C"
= c²==""
min ( en)}
We use the following result for the high high-probability bound for the (II) term in Equation (35). Lemma C.7. For ai 1 |2||8|11 8/ + (2]5(// -"), on good event E,
Σ Eum 1) (J (1, - (it, ph)) so.
Proof. In our setting, we sample a subgroup uniformly from Z at the beginning of cach episode,
Pr(z)= = 1/ vz. From Lemma B.2, we have:
K
Σ
1011 > 1) (J" (1, - Jx (T, (T, (T.)
K
1(IT*) > 1) Σ Pr(z) (1,P) - - -i" (P,P"))
k=1
2E
K
1(IT*)
> 1) Σ
J - (i (it,Ph))
(36)
|
2E2
Therefore, it suffices to show that ELEZ (JF (LPP) (1= pk) holds true for the case when [II*] >
We will show that this statement holds true for cases when n² 11 and x" & 11* for any k E [K]. When =² II* using Lemma C.2 with the relation that (2, 3, h) 2 (z, 8, h) Vz, s, h, it can be shown that for any 2,
PK) 2 J P)
Multiplying the above inequality on both sides with Pr(z) and summing over all 2 Z, we have:
JH pK) 2 J P)
(37)
However, as t is the solution of Equation
(8) and |II > 1, we have:
f (Th pbk) > ~ (i ph.)
(38)
35

---

Published in Transactions on Machine Learning Research (04/2023)
From, Equation (37) and Equation (38), when |II > 1 and ''' E III, then for any & E [K]:
1 1 > 1) (J ((,
- (1 pt) s 0.
We will now focus the case when n² & |1I for the rest of the proof. We will first show this result for a pair of subgroups and then exlend it to the general case. Wlog, assumee that we have pair {i,i} E 2 Let By denote an independent Bernoulli distributed random variable with mean nh. Using this, we can define a probabilistic mixed policy as:
* = B T" +
(1 - )=
Let 7% E [0, be the largest coefficient that satisfies,
(F ph) JJ (1) Sc
(39)
If J (Ft, 1
(r", pP)) < e, then 7h = 1. Else, the equality holds in Equation (39). Therefore,
m (Fhe pt) + (1 - - " (Tre po) 5 (r,, pt) - (1 - -7 (r",, pa)
7k JJ (Ft phy Jj (rr, p&i) + (1 7xm (Ji" (Fr JJ" (r",, (r²,pt) pPt)
(a)
S 78 JJr (r*t ph) - Jj (1*, )b)) + (1 - 7k)
2
c (+ e
( (TM puky - J (1", pay) + (1 - 7m)
= 7m
2
+ 74 JF (r, - Jj (r. P)) - - JJ. (r; P) - -r; (r: P))
JT (r+,,,, (r,, pdi) - Jj (1t, pi)) - P) (r,
(T P1)
$ 7k
=
(ctre)
(JF (r, JJ (r: ()) +11-)))
+ Th
2
Sc
(ct(C)
(c+c0)
= =n(s)) +
+
-9k
Yik
2
2
+ E E- ②
c
=7k AJ
2 +
(40)
where (a) holds because |II$ > 1 which implies FF (pp - 15"h (rttt < ()2 for all subgroup pairs (Equation (5)), and (JT' (r, P) - JJ P)) I because x¹ satisfies the fariness constraint by definition. We also denote AJK, = (J (rh (eM.Pt)-3
- JJ (1*h, (r)) (J.' (r. P) - JJ (r, P)) for readability.
Note that from Equation (31), we know that for any n.
PT (F,, - (T -
therefore for π "::
J (,+ (p)) - Jデ (,r,, pb)) - J (r, P) () (r, PI)= 20,
)
or, AJ&. 1. 2 0.
36

---

Published in Transactions on Machine Learning Research (04/2023)
Therefore, AJt + (2c-c))/22000 (::00 < <c). Plugging this back to Equation (40) we get,
E-c 7 2 c e +2())[))
(41)
By Lemma C.4 for any policy x and 2 = i, (r ph) (r; P) - 21 ($1 Pt).
(42)
Similarly, by Lemma C.5 for any policy π and j.
(r, - (1 ph) S 2(1 + [3 )M.
(43)
Adding Equations (42) and (43) for any policy x:
(F , pht) - J. P) + (r, -) ph.
$ 22 (11+1812)HH) (J JJ pk)
(P) J5 pb)) P)
< 2(1 + |8||Z|H) (JT( pay + J7 (3t,pt))
EJr (8k, (,k)
Here we also introduce the notation for return w.r.t. only two subgroups JT P) P) for any reward function 9 and dynamics P. Thus, we have the following relation for any policy a and any pair j.j E 2
AJr, S 2(1 (1)( P))
(44)
Although # might both not a Markov policy, from Lemma D.3 of Liu et al. (2021) (Theorem 6.1(1) of Altman (1999)); we can find a randomized Markov policy a* that matches the occupation distributions of z under transition probabilities ps with -= .k) J= (g, pk) for any g.
From the definition of n (Equation (8)) and * E II,, we have:
JEJ (i*, (i*, ph) 2 JE's (i'e pk) = Jel (ixt pkk
= JJ (1tt po) + (1- (E) PA)
20
2 7k Ji (it ph)
c c- e
2 c- 0 k,)
Joj (it jok)
(Substitute to using Equation (41))
c
JTi (i', psk)
(Using Equation (44))
0 + 4(1 + SH)HE (ok, Dky
To make JE (10, Phg-= 2 JD (1, P), it is sufficient to show:
c c + 441(1 8 H) (3+ pk) J. (1,
(1, ph)
2 JG (1,
or,
(6- (E-e") (JT. (1t p J. (1, P)) > 401 + 13 (Bt pP (7' )
(45)
37

---

Published in Transactions on Machine Learning Research (04/2023)
From value difference lemma (Lemma H.2), for any 2 E Z,
J Cih ph)
J P)
(z, Sp, As) - (1, An) + E(PA- - ANN |
E
h=1
2/,3'
H
2
E
(ar 1 2 || (z, Shy And Fx-1
A=1
= (ar 1 -
(0+ ph.
Using the above result separately for a = and & = j we have:
J. (1,, pM - J (1, P) 2 (an - 1- 1 PM),
JJ J7 (1, ph) - JJ P), 2 1 12(1( (8h
Adding the above two equations, we get:
JC PM, - Ji (on-1- (a-- -2 pa).
If we use aq 1 |2||S/ + ( 2H, then
411+12|5HH) JEJ (1"h ph)- - Jíj (1, (c- JrJ (8* pM22H.
As the the maximum value of J. (ik, fai) is 2H, therefore the Equation (45) is always satisfied. This implics
JZ (i*, ph) 2 JE, (), or J (ik, p (i+, p*) 2 J (), (1, P) for any k and for any {i,j} E z
with | 1.
Using the above result for consecutive pairs of subgroups (11,2), (2, (12) - 1, 12)) (121,1),, and adding them together we get
2
2
>
J
> 2 Σ
J (l,
==1
#=1
or,
Σ
Js (1, - (p) so
ZEZ
Therefore, using Equation (36), J (1, P) - y (7k,, pby s 0 for any A with I1I > 1.
The last term (III) in Equation (35) is bounded directly using the Lemma B.4 of Liu et al. (2021) with the value of oz. We provide the result here for completeness.
Lemma C.8. On good event E,
K
-aM 1 1 > 1) (Jr (10, ph) Jmh (.p))))) = =ō ((c-c9 -0((=e)) VISM + (c-c"
H3
H118812M|111
38

---

Published in Transactions on Machine Learning Research (04/2023)
Proof. As 12 rml 11% 4 + an - (1 + ai) by Lemma H.3,
K
1(114) > 1) (J (1², phi - - -J, (1,
Js (i", ph) Jx PIl
0
(as + H 1/11) / + * 111SP1ZPP/A)
H
-
= Ō
(e- e0) /IA
(E-E))
Combining the results for terms (T), (II) and (III) derived above, we get
K
H c- V 12 S/3/AK
11 min e²), (E e0)
Σ Js -r,
J Ô
C.7 Extension to non-uniform Az
In our current setup, we sample 2 ~ Z uniformly for each episode (or Pr(z) = 1/1 42 E 2). As such, the optimization problem takes the form:
max
Σ P)
(46)
2
s. s.
- -
W j Jj
where the 1/|z] acts as positive multiplieative constant and can be ignored from an optimization perspective. As we mentioned in Section 3, this scenario might not be the case in reality as different populations might not be always represented cqually. In this section, we will show how our approach can be extended to the set setting with any arbitrary Az, given that the Ag is also know to the algorithm. We will do so by taking the Pr(z) term into account in the definition of the subgroup specific returns.
P)
(V Zii, P)] 71]
(81,2)mH
E (V Ziir P)] Z1] Zrdaz SImPa
= Pr(z))
E ( Z1;r, Simp.
(47)
In the setting considered in the main paper, where the algorithms can sample trajectories from each subgroup for every iteration of the algorithm, Pr(z) = 1/ Vz Z, and as such the 1/|z]| term can be ignored in the definition subgroup specific returns (Equation (1)).
For this new setling, the problem in Equation (2) takes the following form:
max I7
ΣJJ
(48)
s s. t. -T
W W2j
The Assumption 2.3 also modifies accordingly in this setting, i.e., we assume that |J=² (r. P) - JØ (r, S 0 <e, Vi,j 2 and the value of d is known the algorithm.
39

---

Published in Transactions on Machine Learning Research (04/2023)
Note that the LP based solution is still valid to this setting the constraints are still linear even with the addition of Pr(z) term. In the rest of this section, will show that the results from Section 3 are still valid in new setting for the same choice of optimistic and pessimistic reward estimates.
In this setting, we can define the set fair policies IT (analogous to Equation
(4)) at an episode & E [K]
as:
1 (r ph) Sc, ( x JJ( phy Jr (t) c,
wi i
n
(49)
Vi J: i.j 2
The final set of policies now chosen from the high-confidence II defined as:
if (Ft, ph) - (r ph) > (e+ 22/2, or Jf ph) J (1*t ph) > (e+ + 02//,
(m)),
(50)
n
otherwise.
The result from Theorem 3.1 is still valid in the setting, i.e, given an input confidence parameter d E (0. 1) and an initial fair policy n², the construction of I ensures that there are no fairness violations at any episode in the learning procedure in the true environment with high probability (1 - d), i.e. for any E fi,
Pr (1JF J/. P)| sc) 21
Vi,j E z 4k E [K].
(51)
The proof follows the exact same steps as in Appendix C.4 but context with P). We describe the proof sketch briefly below:
Proof. To see that the Part 1 of the proof from Appendix C.4 holds true, notice that from Lemma C.2 w.r.t.
and F, we have:
J) S) JE PM)
Pr(1) P) S PP()) PM)
or,
(r. P) و JF Ph).
Similarly, from Lemma C.3 w.r.t. == j and r, we get
- JJ P) < (1" -()
Combining the above relations, we have:
J(r J,,, ( ,/, (r,
From the definition of fT'. we know any policy in E T&. satisfies the constraint:
[T (1" pm) Se.
Therefore, we have the following relation:
(r. P) Jj Jr phy - Jj (1
ph) Sc.
The proof of Part 2 of Appendix C.4 follows the same steps, and get:
JJ P) JF
J -)
p Je p4)
Finally, from the same argument as the last step of Appendix C.4, we know that either ²0 deployed in an episode (which is fair) policy from îiК will be deployed. We have shown in Parts 1 and 2 above that
40

---

Published in Transactions on Machine Learning Research (04/2023)
the good event &, for any & E [K] and policy Iiy, P) (r and [r P) (r, or;
(r, P)l s.
Extending this argument to all the pairs of subgroups get, vijjijee z².
-J
The result from Theorem 3.2 also holds true in this setting for the same definition of Th (Equation (7)). We will describe the proof sketch briefly below:
Note that the results from Lemma C.6 and Lemma C.8 extend directly to this setting by replacing the term J (1, P) with (,, P) and then following the exact same steps in the corresponding proofs. For Lemma C.7, notice that we have:
K
L(I111 > 1) (J (5 (1,P) (14, (1))
k=1
1(1TH 1) ΣPrrr Pr(z) J (1, (1,
J (1x pho)
(from Lemma B.2)
=E2
= Σ
1(TT 1)
jr' (1, - Juh (ith ph))
(52)
=EZ
Therefore, it sulfices to show that Elez (f'
holds true for the case when [TT >
From here, the same steps from the proof of Lemma C.7 can be followed by replacing the term Jr (1, P) with Jr (1, P).
D Tabular experiments
The goal for the experiments to validate if the proposed algorithm in Section 3 achieves: (1) zero constraint. violation (with probability 1 8), and (ii) incurs a sub-linear regret.
D.1 RiverSwim
Environment: We take the RiverSwim enviromment (1S) = 7, H - 10, 10 =2) (Strehl and Littman, 2008)
and make the following modifications to suit our fairness setting:
There two subgroups (| 2), with different P. and μz- In terms of Pz, the major distinction between the subgroups is that one group has more stochastic transitions (Figure 5a) compared to the other (Figure 5b). In terms of difference in M4z the more stochastic subgroup (Figure 5a) starts the episode in the leftmost state with high probability (Hhigh ($1 =) 0.999) and uniformly from the other states. Similarly, the less stochastic subgroup (Figure 5b) starts at the second from left state with high probability (Now (S, = 2) = 0.999) and uniformly from the other states.
There is no distinction between the decision-maker and demographics rewards, i.c. I= r in this case.
Another important distinction from classic river swim environment is the presence of a halfway state where the agent receives reward higher than the initial state but lesser than the rightmost state. Therefore, reward at reaching right-most state = +1.0, at initial state= 0.01, halfway point 0.1.
In this setting, the traditional noi-fair RL algorithms will generate different optimal policies for different subgroups that have distinctively different, behaviour. For the subgroup with higher stochasticity that starts
41

---

Published in Transactions on Machine Learning Research (04/2023)
0.4
0.6
0.6
0.6
0.6
0.6
0.6
0.6
0.35
0.35
0.35
0.35
0.35
1
0.05
0.05
3
0.05
0.05
5
0.05
0.4
7
0.01
I= 0.1
1.0
(a) Higher stochasticity subgroup
0.4
0.05
0.05
0.05
0.05
0.6
0.6
0.6
0.9
0.9
0.9
0.9
0.9
0.05
0.05
3
0.05
0.05
5
0.05
0.4
7
0.01
I=
0.1
r == 1.0
(b) Lower stochasticity subgroup
Figure 5: Description of the modified RiwerSwim environment. Figure 5a denotes the transition dynamics for the higher stochasticity subgroup, and Figure 5b denotes the transition dynamics for the other subgroup. The nodes in the graph denote the non-sensitive states and r denotes the reward function (that is same for both the subgroups). The solid arrows denote the transitions corresponding to taking the right action, and the dashed arrows denote left action. The number above arrows denotes the probability that action will result in the corresponding transition.
furthest from the rightmost state, the agent under the traditional RL optimal policy for this subgroup stays close to the halfway point (that gives a return of 0.4167), whereas for the subgroup with lesser stochasticity, the agent under the traditional RL optimal policy for this subgroup reaches the right-most state and stays there (return of 3.1901).
For the experiments, instead of sampling only a single trajectory from one subgroup at an iteration, we instead sample one trajectory from both subgroups for elficiency. Additionally, we use the time- sime-homogeneous transition and reward functions to simplify the experimentation setting, We present the experimentation methodology in Algorithm 2, and introduce the experiment design and input parameters below:
Experiment methodology:
e denotes the fairness gap corresponding to the initial fair exploration policy. We use an alternate reward function, along with the e 0.1 and true MDP transition function P to construct the corresponding n". The alternate reward function is similar to the true reward, with the difference that there is no reward for the rightmost state. This allows us to get a TO that can reach the midway point quite easily, but has very low probability of reaching to the rightmost state. The motivation behind this to start with an inefficient fair-cxploration strategy.
7: The final fairness constraint is = c + This is set to 1.0 as it allows the agent to reach till the end but forces the agent to not stay there in order to prevent violating the fairness criteria.
K The number of episodes to run the algorithm K = 20k.
8 0.1, the high-probability constant (or the failuro-rate).
B, confidence set scaling parameter: If we do not scale the confidence sets 3* then would take the algorithm millions of episodes before making a switch from the initial policy (i.c., algorithm behaves conservatively). Due computational reasons, we scale the 8 to have more sensible confidence sets.
42

---

Published in Transactions on Machine Learning Research (04/2023)
Evaluation criteria: We plot the following quantities for different algorithms during the learning:
Cumulative regret, Reg(K;1) EK= (J (1, -
Cumulative regret w..t. TT,
The returns for both of the subgroups throughout the learning (JT")
Number of unfair policies executed so far,
Faiture-rate (6): The average number of time the executed policy violated the fairness constraints,
The fairness gap at each iteration ex,
Whether the algorithm is using x² or not.
We consider the Maximum Likelihood Estimation (MLE) based baseline for the comparison. The MLE baseline starts with T² and then simply builds the MLE estimates of the MDP parameters. Tt then uses the estimated parameters in the LP solver in Equation (17) directly to get a policy to execute at an episode k.
Baselines:
A Algorithm Experiment procedure for RiverSwim
Input: Env, e", K, PI-Algorithm and B.
1: Calculate nO based using the true MDP paramcters and alternate reward.
2: Set = ④ + 7).
Compute म² using Equation (17) using true MDP parameters, calculate J Initialize: (2(2, 8, 8,0) (2, a) 0, v(2, 2 A.
5: for h = 0,1,..,, K do
6: if 82, (² 2 (2, 5, then
Update the empirical model "h; Estimate 3 and multiply it with B;
8:
Estimate optimistic/ pptimistic/pessimisti pessimistic reward estimates it, ,
9:
10:
Find n* based on the input algorithm;
11:
Nº +- No
12:
end if
13:
for I, ...... [3| do
14:
Get imitial state Z St jم.- Execute x in the true environment and collect trajectory (% A R2), vh E [A] Update counters (Z Sk, A&). Vh E [H];
15:
16:
17:
end for
18: end for
Hypothesis: As the initial fair policy T² mostly discovers the reward at the halfway state, inefficient exploration strategy will have difficulty discovering the rightmostt state. Therefore, we expect the MLE baseline to have difficulty in exploration and accumulate higher regret. Note that the probability of reaching right-most state under 70 quite small but non-zero. As such, once the MLE baseline is able to discover the reward at the rightmost state, we would expect to violate the fairness constraints as the MLE baseline does not take into account the uncertainty associated with the transitions.
Compared to MLE, we expect out algorithm to discover the rightmost state quickly and achieve regret, while maintaining failure rate of less that 8 and incurring very low constraint violations over the learning.
Before diving into results, we note that the only cocfficient B. When B + 1, the algorithm behaves conservatively and needs more samples to switch from " (no computational advantage), and when B - then the algorithm behaves similar MLE baseline (as I z 0, and there is no consideration of uncertainty). For this task, found that the scaling values in range
Results:
in our experiments is the scaling
43

---

Published in Transactions on Machine Learning Research (04/2023)
Cumueerv
1000
1:00
for
Epocis, coloodes
to Epochs, spiccees
Epochs, aptccdes
Avg amroun of th mimess of was erecuted
Curuuastee famesss visicion
Taimen
40C colsodes
OM apisades
230
-/: -i episodes
Epochs
.nit
eptscdes
Epocts.
Figure 6: River swim enviromment with a starting xO with an inefficient exploration strategy, i.e., T0 has very low probability of discovering the right most state (Finc-tuned B hyper-parameter).
[10-3, [10-8,10-4] tend to achieve this computational speedup without affecting the behavior of the algorithm. We present the results for B = 3 x 10 in Figure 6, and highlight the following observations !
We observe that for the most of the training, the MLE baseline accumulates a linear-regret rate, which then plateaus once it discovers the rightmost state. Compared to MLE, our algorithm achieves sub-lincar regret throughout the learning. We note that our algorithm's regret has not plateaued, i.e., there is still some scope of improvement, which might resolve with more amount of samples.
Cumulative regret (Figure 6: Row 1, Column 1):
Cumulative regret w.r.t. T² (Figure 6: Row 1, Column 2): We observe that our algorithm has consistently negative regret w.r.t. T", i.e., it performs better that TO consistently over the training. The MLE baseline accumulates a positive regret in the beginning and performs worse than baseline (e.g., it stays at the left most state possibly due to incorrect transition estimates), and afters a while it performs as good as baseline (able to reach halfway state consistently), and then it eventually discovers the rightmost state and after which the regret w.r.t. TO goes down.
The returns for both the subgroups through-out learning (Figure 6: Row 1, Column 3,4): These plots depict when the different algorithms were able to achieve different reward states. For instance, we see for the second subgroup (Row 1, column 4), our algorithm is able to achieve a return greater Ihan 1 (able to discover the rightmost state) quite early in training.
The number of unfair policies executed over the learning (Figure 6: Row 2, Column 1): The total number of times our algorithm violated the fair constraints is 3, compared to the Re 2.5k violations for the MLE approach. For our algorithm, the violations occurred when it first switched from TO (as evident in the small peak in failure-rate plot), whereas for MLE, the fairness violations occurred when the MLE agent discovered the rightmost state but had inaccurate transition estimates.
Faihuro-rate (Figure 6: Row 2, Column 2): We observe that the average failure rate of our algorithm is < 0.1, whereas the MLE baselines violates this property.
The fairness gap at each iteration c (Figure 6: Row 2, Column 3): We observe that our algorithm quickly reaches closer to the specified fairness threshold. We also observe that once the algorithm reaches close to the specified e value, the learning also slows down (not much change in the cumulative regret rate) as there is less margin for deviating from policy.
I Another result. for 10-4 is presented in Figure 7, where we observe similar trends but requires more samples.
44

---

Published in Transactions on Machine Learning Research (04/2023)
Average amount of times x² was used (Figure 6: Row 2, Column 4): We observe that the algorithm quickly switches from x² (in about 200 episodes).
Cumuretye
1.0
Comdlativo
200
-000
146
colsodes
Do Epochs, unt spicodes
Epochs, eptocdes
Aug emour of dines was crec atd
Canulatve fainecs volaton
0um
Ma
Epochs, uni
mciscoles
Epocto, unit opisades
Epochs, Lnnt epiicdes
Eoochs, 20.0 episades
Figure 7: River swim enviromment with a starting n7 with an inefficient exploration strategy, i.e., TO has very low probability discovering the right most state (B =0-44.
Additional details: We used cvxpy (Diamond and Boyd, 2016) with the default parameters for solving all the different LP problems. In torms of compute, on an Intel(R) XR) CPU E5-2623 v3 (3.00GHz), 20k iterations of the algorithm take about 5 hours.
D.2 Credit lending
The MDP description follows Section 2.2. The horizon is set to H = 5, handicap for the low group is set as T = 0.7, and the target is set to 0.11. The traditional (unfair) RL policy leads to a gap of = 50 approved between the groups with a profit for the bank 13.64, whereas a fair policy with c = 0.11 leads to gap of s 10 loans and the bank return of 13.58. All the additional details can be found in the accompanying code.
Environment:
Evaluation methodology, criteria and baselines We the similar methodology and baselines as in Appendix D.1, except that now only sample one subgroup from the specified Az at the beginning of each episode. As a result, different subgroups might now be have uneven amount of learning experience.
Results: As in Appendix D.1, we use the scaling coefficient hyper-parameter B for computational speedup. We show the results for B 5e 4 in Figure
E Proof of Proposition 4.1
Proof. We omit the r term in the notation for the associated return, value and advantage functions for the sake of clarity. Recall that æ and n' denote two arbitrary policies such that there exists only one subgroup for which the associated policies differ, i.e., F E 2 n, + n/. The value function associated with any policy स for subgroup
is denoted by VT.
Using Lemma H.6 with TŚ and f = V/7, we get:
1
((m))
E [V) +
18,(5, a, 3')]
(53)
3riph
Y and.
45

---

Published in Transactions on Machine Learning Research (04/2023)
Epicadic retum
Epieodic return 1
Epleadic rotum 's I
Frequency
Epicadic
Time-stops
Time-stops
Time-stpps steps
Time-stops
Time-steps
MLE
Gur
(a) Ag [0.1, 0.9
Episodic riturn
Episodic return
Episodic return
Frequencyy
Epicadic
Time-steps
Time-steps
Time steps
Time-steps
Timee-steps
MLE
Ours
(b) A = [0.9, 0.1]
Epioodic return
Eptoodic return
Coloodic return
Freauency
Eploodic
Timessteps
Time-steps
Time-steeps
Time-steps
Time-steps
MLE
Our
(c) A2 = (0.5,
Figure 8: Learning curves for the credit lending task with different Ag. The subplots in each row denote the following (from left to right): cumulative regret, number of fairness violations, fairness gap between the groups, return of group high, return of group low. The x-axis denote the number of samples used during the learning.
where 0,(5,a,3) r (V (5). Similarly, for ny using Lemma H.6 with f VJ", we get:
J(Tz)) = E'' (5)
E and amnt 5 5'm
[5,(5, a, 8').
(54)
1-
where 8)) = r((,,),
V) -7
From the above two relations, we have:
- J(T)) - - E [VT
E (V)
Term
+ 1 1-y y
E (,,
E
(5, 8')]
(55)
Brud?
i-d
amn
8'~PP
s'mPi
Term 2
46

---

Published in Transactions on Machine Learning Research (04/2023)
The quantity in the Term 1 of the above Equation (55) denotes the difference in the returns of the subgroups under the policy a and can be written as:
E [V,
E 5ma5
(3) ((..) J(T,)= J.
(56)
Smap
Notice that we do not require any any samples from गद to estimate the above quantity. However, this is not the case for the second term in Equation (55) as it requires samples from di We will now follow the same methodology from (Lemma 2, Achiam et al., 2017) to bound the second term so that we do not require the samples from d. We provide the proof below for completeness.
We focus on the first quantity in the Term of Equation (55) (La-dy a (3, a, a)))), Let 85' E RRIS
denote the vector with 8 (8) = Ee [6: (5, 35)[5]. Using this, we get the relation:
(5,(5, 8')] ( d. 55 =
(TT -
(T d.. 5,1
amm..
g'PPt
Using Hölder's inequality: for any p.q s., + =1
[7.855" 8,
d.'
11,
s E
[6,(3, a, s') s (c.,05 05
d..
3.-
(57)
Brd
amai
s
For p and q = 0o, we get:
|55
di
2Dvv [|d"),
where 5/' = max; Pa (,, 8']] is the worst case error. Plugging this back in Term 2 for Equa- tion (55),
E
(8, a.))
E kndy
(5, a, 8')]
8rud?"
unvyy
amt; s'mPt
8f s'
1
(df 53 2DD 11d 1 (d7,57))
(where 87 Eawn, (ō3 a, 33))
1
(a(3)) 0,(5,,,8)] + +DDrv 11am)e (al3)
<
E
E.
18,(3, a,
1-7
knd amii 8'
auT: 8/ P.
(by Importance Sampling: Essay [0,(3, a, 3')] = Esad
8, 6,(5,a, a, 3))
m)(a[s)
x'-P
s'
Note that the term Ev (02(3, a, 8²)1=, 5, a] = Ev (r(2,) 8), + V = (3, i.e.,
the advantage estimate associated with n, for subgroup z. Additionally, from Lemma H.7, we know:
27 (1-)
1 d=
E.
and
47

---

Published in Transactions on Machine Learning Research (04/2023)
where Drv Prv(Tl1TT))6 E. m[(als) =e(a|s)]. Therefore the quantity in Equation (55) becomes,
J S J. +
1
E ardd
[|((8)) TT(als)
(3
E [45 a amt; 8'~1P
1-1
2
E snd
(T((m(mm)
(1
7)²
Additionally, for any policy and subgroup 2, have (A] a)] by the definition of the advantage function. Thus,
E
[b,)))]]
= E
E a3) = 0. Brudy amyy
LIE
amayy
Putting these term back ion Equation (55), we get:
[ क. (a|
27
J. S J,
A (3, +
(1 (1 (1-2)
Dr Drv (Till:
andd ama,
From (Corollary 3 Achiam et al., 2017), we can replace the term Ea-dy (DTV ( [))[3]] that gives us:
with v (xt
(1(33
a)) + V27e5
JT S J
+
E fndd am-m
(1 (1-7) S (TT(m(())))
Similarly, using the Hölder's inequality in the other direction in Equation (57) gives us the lower bound:
ni(a|3)
V2rgT'
AT(5,a)
(1 (1-7) [KL(TT||=)]
(<(3))
fnd?
F Practical Deep-RL algorithm methodology
Consider the scenario where each subgroup's policy is parameterized independently and they have their separate neural networks. As we mentioned in Section 4.2, if the Equation (10) can be solved exactly, then we can use it to construct an algorithn that only updates one subgroup at time, while ensuring each update satisfies the fairness requirement. We present the algorithm based on this methodology in Algorithm 3.
F.1 FOCOPS methodology
In this section we will describe in detail how the FOCOPS (Zhang et al., 2020) methodology can be used to solve the problem Equation (10) based solely on the first-order approximations. For ease of exposition, we will show the approach for only two subgroups (z {i,j)) however the approach also valid for any number of subgroups. Instead of solving Equation (10) directly, we will follow the FOCOPS approach, under which two-step approach will be taken following:
48

---

Published in Transactions on Machine Learning Research (04/2023)
Algorithm General algorithm methodology for the Deep-RL case
Input: n" 00 E 1lg, Vz E K,
_0 ..... x 2 denotes the parameterized input fair policy where T denotes the separate x² o = {=1
policy network for the subgroup 2. for k= 0,
do
for E 2 do
Sample trajectories for each subgroup = क.. VIE Z. Get Te 0+1 using the update rule in Equation (10) with मे = The and = 2.
4:
5:
The algorithm only updates one subgroup at a time. end for All the subgroups have been updated once.
end for
Step 1: Given some policy ,, the first step is to find the optimal update policy of by solving the optimization problem in Equation (10) in in the non-parameterized policy space, i.c., solve the following optimization problem for zon-parameterized π, E (and not IIg):
[A7" (5,
(58)
R.Elf
Brdd?" or amot
A (5, (;r)
S. s.t.
E
cc
andd do
1 1-7
A (B,a;r)
bgj
E
Se
1-7
drude amots
Sk
We have the following result that follows directly from Theorem 1 of Zhang et al. (2020).
Lemma F.1 (Restatement of Theorem 1 of Zhang et al. (2020)). Let b, = (1-7) (c
(c-Jtj" G-J )2t and
82 (1 (e J 2 "x Th is feasible solution, the optimal policy for Equation (58) takes the form:
क: (a(3) = n. (a|s)
Gx exp (1 (A:""(,;;
(5, 12 (5, U2A," (5, (B.a:)))
(59)
AF" (s. a;1) - un (3, a: r) + +22 (3, arr)) is a partition func- tion which ensures that the Equation (59) is a valid probability distribution, and X, v and V2 are solutions to the optimization problem:
where Gx. wn (8) -a T0 (al exp X
min A. 20.020
25 + un mzd2 + A
[log Gx.I..2))))..
(60)
and; % amm;
Proof. We need to show that the problem in eq. (58) is convex w.r.t. = (m:(al))) : 3 E S, A}. The objective in Equation (58) is linear w.r.t. n. As Jo .h is also constant w.r.t Ji the constraint in Equation (58) is also lincar. Finally, the KL constraint Σ3 dr (R) S K, is the same as Theorem of Zhang et al. (2020) and is also linear. From here we can directly follow the steps from Theorem of Zhang et al. (2020).
49

---

Published in Transactions on Machine Learning Research (04/2023)
The optimal policy xj found in the previous step is now projected back to the parameterized policy space Nlp by solving for the closest policy to xx ie:
Step 2:
( = E (x)(
and 2
where xf Hg is the projected policy which is going to approximate the optimal update policy and then used later as T Instead solving for x;. we can use the Corollary Zhang et (2020) with the form of optimal policy derived in the Lemma F.1. This allows us rewrite the gradient of [()) as:
VoL(o)
E [=Dk<(=?1))))8)) amd
where,
(eDKL(T)|<))) (T!
E
(3. + 12 (s. (s. (A7" (s,a;)) - 11
Ti Bx (als)
The above expression allows to estimate the gradient update from the samples generated from n. without the need of exact optimal policy update TH-
Estimating X, M1, and V2: Note that we still need the parameters X, V1 V/ from solving the dual Equation (60) at every iteration. Solving this impractical for high sigh-dimensional state and action spaces, and Zhang et al. (2020) propose the following approximations for estimating the values for X, U1 and V2:
corresponds the trust-region constraint and Zhang et al. (2020) found that, in practice, fixed value of À found through parametrr sweeping works in practice.
Unlike A, Zhang et al. (2020) claim that and need to be continuously adapted during the training. The heuristic proposed by them is based on closeness approximation, (E, (Baad="* [4q (8, (8)) x
E Bandr"* "am [AF (8, a))] = 0), and takes the following form for our problem:
J a
V1 proj
1/ proj.
where a is the step size the interval [0, Vmaxx] where Vmax is another hyper-parameter.
and proj, is projection operator that projects 11, to
The final updates take the form:
1 N
VoL(O)
V VoDKi DKii(T [<]]< [sm]]
V Von! (an 1B))
(AT"* (A anil) - 12 A7 (8n, 12 (8n (min I(sn), (61)
Ox n (a, (5n)
where N denotes the sample collected under d=" and 1(xa) = 1 (x is in indicator function
that ensures only the states that satisfy the T. xfth condition are used for the updates. The complete algorithm is provided in Algorithm 4.
50

---

Published in Transactions on Machine Learning Research (04/2023)
Algorithm 4 FOC-PPO for |2| =
Initialize: Subgroup policies л² { m²] E Ng value functions VT. (Vr-0, 12200 E Ver, Vl. (V/.9, v2.0) E V subgroup specific constraint parameters "f. V 0, Va E Z.
Input: Fairness threshold e, trust-region parameter K, maximum projection bound Pmaxx learning rate for vf, v5 updates a, temperature parameter X, GAE parameter, discount factor y, learning rates for policy networks Og and value networks ov.
for == 0, 1,... do Generate batch data of M episodes of length T using the current policies for both subgroups of and
Updating policy for 1st subgroup (mf²).
4: Estimate the average difference in returns between the two subgroups based on batch data J m
5: Estimate the advantage functions AT (5r), A7 (;1) using GAE. Get the bootstrapped target value function for critic updates.
Update vi, vú corresponding to this subgroup:
v + proj [v} a (e J122 5
2 + projor [u3 a c Jl.2 k
)},
7:
for 1= 0,0, 1,... # update epochs do for mb = 0, I.... # mini-batches do Sample a minibatch of size Mb.
10:
Calculate the loss function for the critics using MSE loss (i))
11:
Update the value networks:
o o av V (or))
ij t of av V (v
12:
Update the policy:
01 - 01 0x VoL, (01),
where,
Mb
1 Mb
Vo,
Vo DoD DrL ( (m?
V u (an (n)
(A7" (8n; anil) Us ARA (Bn, U2A (Bn, Senaaii)) ((bm),
X ON (3,15,))
13:
end for
14:
if
1 Mb EM ΣT- DKL(Tillz) [Bce] >> k then
15:
exit the update loop;
16:
end if end for
17:
> Similar procedure for updating the policy for 2nd subgroup, (Tf²), but we sample trajectories w.r.t.
18:
11 and the it compute the corresponding J7 mett1
#1
19: end for
51

---

Published in Transactions on Machine Learning Research (04/2023)
F.2 Lagrangian based approach
As mentioned in Section 4, the Lagrangian based approaches use adaptive penalty coellicients to enforce the constraints. Borrowing the description from Zhang et al. (2020): for an objective function f(0) and constraint g(0) S the Lagrangian methods solve the problem max, ming20 f(0) - vg(0) where v denotes the Lagrango multiplier or the penalty coefficient. The optimization problem is solved in two steps: a maximization step w.r.t. and minimization step for the penalty coefficient. v.
We now describe how the Lagrangian methodology based on PPO can be applied out setting. We again show the procedure only for Z = {i.j], but the approach is general and can be applied to any mumber of subgroups. W.l.o.g, assume that we are only updating the policy for subgroup i, x. where where 0 denotes only the parameters of the policy network. Let L()) denote the traditional PPO objective function for return
maximization and let (J) = J.. 2x
2x
E
smatt amit
A x (s.0:r)
1-7
Then the update rule in Equation (10), in
context to only 0, can be re-written as:
max L(Ø)
s.t.
AJ:(0) e
AJ,(0) E 0
Using the Lagrangian methodology, the augmented objective with penalty coefficients V1, M2 can be written
E(0, - - (AJ.(()
-) - 12 -)(
(62)
For the maximization step we take the gradient w.r.t. and we get the update of the form:
(als) (AF" (AF" (3,a;)) mA + (5,
V,L(0,u),,2) Vo min
(al3)
(al3) 21 (als)
1 1 t (10++)(A"" -1 - u2AR" (B, ) (63)
clip
where & denotes the PPO-specifie clipping coefficient, and clip denotes the clip operator that clamps the value of x (a[_) to [1 -. + range. For the minimization step apply gradient descent w.r.t. 21 and
2n (a(s)
get the following update rule:
11 + projelm a Jü o ) 1/2 - projolu- a (c+ Jo 2 ,0
In the above update rule for Vi, 1/2 we have made similar approximations as in the projection based method described in Appendix F.1.
G Additional details for the Deep-RL experiments
G.1 Environment Details
We build on the Half-Cheetah-v3 environment from OpenAT Gym (Brockman et al., 2016) for the locomotion based experiments. We use the default implementation of Half-Chocttah-33 as one subgroup, and make the following adjustments for the other two subgroups based on the MuJoCo guidelines (Todorov el al., 2012):
We create the subgroup with 2x the default feet size by incrcasing the size parameter in the body model associated with the default Calf-Chhetah-v3. We modify the flags associated with back and front feet only (bfoot and ffoot).
52

---

Published in Transactions on Machine Learning Research (04/2023)
We create the subgroup with 10x the default friction by increasing the global friction parameter in the body model associated with the default. Half-Cheetah-v3. We modify the geom flag under the default section in the model file.
For the point maze navigation, we build top of the open source library mujoco (attps://github com/kng htmm///ggy//mmjcooooooao maze). The parameters for the size of the point agent paramcters are increased to 5x the default size based on the torso section of the body model.
The implementations for both the environments provided in the supplemental material.
G.2 Architecture and
selection procedure
We use the same network architecture for both the tasks. We follow the same network architecture as Huang et al. (2021); Zhang et al. (2020), where we have two-layered neural network with tanh activation for both the policy and value networks. The policy is modeled as Gaussian, where the network outputs the mean and state-independent log standard deviations. The same pre-processing procedure as Huang et al. (2021) is followed for both the lasks. We use PyTorch (Paszke et al., 2019) for implementing the Deep-RL algorithms.
For the algorithm specific hyper-perameters, we follow the guidelines from FOCOPS (Zhang et al., 2020). We set the max hyper-parametts to a very large value 1000.0 and do not fine tuned it. We found that the learning rale for the , parameters lypically works best in the range [0.01, 0.1] for our lasks, and we ended up using a = 0.01 for the our experiments. For the hyper- ppper-parametes, we did seper-parameter search in range (1.0, 3.0, 10.0} and used 1.0 for the maze navigation tasks and À 1.5 for the Chof-Ch tasks. The initial values for all the V1, 1/2 parameters are set to O. The other parameters, such as mini-batch size, number of updates, trust-region size, clipping parameter, etc. taken from the PPO-based libraries which we build our implementations, i.e., Huang et al. (2021) for the environments and Kanagawa and Kaneko (2020) for the maze navigation based experiments.
based locomotion
G.3 Additional results
From implementation point of view, the state-of-the-art implementations of PPO include many code level optimizations (Engstrom et al., 2020; Andrychowicz et al., 2020; Huang et al., 2021) that were not part of the originally proposed algorithm on which we base our fair versions. As result, we include both the variations of PPO in our basclines. We refer to the version with all the code level optimizations as PPO and the minimal version that is more consistent with the other fair baselines as Minimal-PPO.
We present the results for both the tasks and different level of fairness thresholds below:
Half- Cheetah task with e (high, medium, low} is presented in Figure 9 (with smoothing) and Figure 10 (with rumning average).
Point Navigation task with E (high, medium, low} is presented in Figure 11 (with smoothing) and Figure 12 (with running average).
In terms of compute, on Nvidia Quadro RTX 8000 GPU with AMD EPYC 7502 32-Core Processor, the navigation experiments take about 3 hours to run with 16 CPU cores and Half Cheetah experiments take about 7 hours to run with a single CPU core.
G.4 Generalization results
We train the algorithms with a fixed random seed in a train environment, and then evaluate the performance of the am on ten lest environments, each with a different random seed. We present the aggregated results on the test environments for the both the tasks and the lowest e setting in Figure 13. We observe that even though the fair versions of the PPO (FOC-PPO and Lagrangian-PPO) are not able perfectly satisfy the fairness requirement, they perform vastly superior to the unfair basclines (PPO and Minimal-PPO PPO) in this aspect.
53

---

Published in Transactions on Machine Learning Research (04/2023)
gap, E
subgroups
Big-feel subgroup
High-fristion subgroup
Dafault subgroup
Diffrreno retumms
Cammusatvve neturn
Epecotic retar
Epcodle return
Time-steps
Time stops
Timo 0000s
Timp-stepe
Time-stepe
FPg
MrinnaPPP
(a) Half-Cheete Cheetah
High fairness threshold.
Fairness gap.
subgroups
Big-feet suboroup
High-friction subgroup
Default subgroup
Eprodde retur
Oifforencs
Time stops
Time-stopo
(b) Hall-Cheetah: Medium fairness threshold.
Fairness
All subgroups
Big-feet subgroup
High-friction subgroup
Defsult subgroup
Escodie retun
Estond retuun mm
Curra Wwtiiiiiee
Diffrrence
Esoodd
Time-stops
FOC-PFO
Lagingg PPO
Minine PPO
PPO
(c) Half-Cheetah: Low fairness threshold.
Figure 9: Learning curves for Half-Cheetah environment with different fairness thresholds. The first subplot in each row denotes the fairness gap (maximum of absolute difference of returns between subgroups) and the black dotted horizontal line denotes the specified acceptaale fairness threshold (e). The second subplot in each row denotes the cumulative return for all subgroups, and the rest of the subplots in the row denote the subgroup specific returns. The x-axis denote the number of samples used during the learning. The solid colored lines represent the smoothed mean over 10 random seeds for different baselines (with weight=0.9) and the colored shaded regions represent the normal 95% confidence interval.
54

---

Published in Transactions on Machine Learning Research (04/2023)
gap, E
subgroupe
Big-feet subgroup
High-fristion subgroup
Default subgroup
Difference retumms
Commusatvv neturn
Eprootic return
Epcodl return
Time-steps
Time stops
Time 00805
Time-stegs
Time-stape
FPg
Mrinsl
(a) Half-Cheetee Cheetah
High fairness threshold.
Fairness
subgroups
Big-feet suboroup
High-friction
Default subgroup
Eproode returr 36
Oifforenos
8
Time-sto steps
500p5
(b) Hall-Cheetah: Medium fairness threshold.
Fairness
All subgroups
Big-feet subgroup
High-friction subgroup
Defsult subgroup
Escode rotunn
Estodd return mm
Diftrrenee
Curra betioa
Eplodde
Time-stops
FOC-PPO PPO
Minin PPO
PPO
(c) Half-Cheetah: Low fairness threshold.
Figure 10: Learning curves for Half-Cheetah environment with different. fairness thresholds. The first subplot in each row denotes the fairness gap (maximum of absolute difference of returns between subgroups) and the black dotted horizontal line denotes the specified acceptaale fairness threshold (e). The second subplot in each row denotes the cumulative return for all subgroups, and the rest of the subplots in the row denote the subgroup specific returns. The x-axis denote the number of samples used during the learning. The solid colored lines represent the running mean over the last 100 episodes for 10 random seeds for different baselines and the colored shaded regions represent the normal 95% confidence interval.
55

---

Published in Transactions on Machine Learning Research (04/2023)
Faimess
All subgroups
Big size subgroup
Default size subgroup
Epeedd return
Cumulattio
Epstadic
20
Point-Navigation High fairness threshold.
pap.
subgroups
subgroup
subgroup
Gum www.eattooooooo rotum
Esteodereeaa
Diforancca X
T Timo-dlaps
Tima-stops
TIme-4tops
Time-slpp
FDC-PP
an-PPg
( Point-Navigation: Medium fairness threshold.
Felmess
size subgroup
Default size
Diftranos in retums
Cumuuetive roturn
Eploodic retumn
10
28
25
46
19
Time-staps
15
86
10
05
Time-diepe
20
25
40
63
16
Time-slaps
15
16
43
FOC
Laganngan-PPg PPO
WinniiFF
RPO
(c) Point-Navviation: Low fairness threshold.
Figure 11: Learning curves for Point Navigation environment with different fairness thresholds. The first subplot each row denotes the fairness gap (maximum of absolute difference returns between subgroups) and the black dotted horizontal line denotes the specified acceptable fairness threshold (c). The second subplot in each row denotes the cumulative return for all subgroups, and the rest of the subplots in the row denote the subgroup specific returns. The x-axis denote the number of samples used during the learning. The solid colored lines represent the smoothed mean over 10 random seeds for different baselines (with weight- and the colored shaded regions represent the normal 95% confidence interval.
56

---

Published in Transactions on Machine Learning Research (04/2023)
Faimess
All subgroups
Big size subgroup
Default size subgroup
Cumulattin raturn
Epeedd return
Diforrenss
Epsledic
20
Point- Naitt-Vavigttion: High fairness threshold.
subgroups
subgroup
subgroup
Difurancc mnnuma
Cummule www.oaattioooooooo rotum
Essooderelaa
1
T Time-dlaps
Tima-stops
TIme-4tops
Time-llpp
FDC-PP
b Point-Navigation: Medium fairness threshold.
Falmess
size subgroup
Default size
Diftranos in retums
Cumuletivee roturn
Epioodle return
10
28
26
46
19
Time-staps
15
86
35
10
05
Time-diepe
20
25
40
03
Time-slaps
15
16
43
FOC
Laganggan-PPg
WinniiFF
RPO
(c) Point-Navviation: Low fairness threshold.
Figure 12: Learning curves for Point Navigation environment with different fairness thresholds. The first subplot each row denotes the fairness gap (maximum of absolute difference returns between subgroups) and the black dotted horizontal line denotes the specified acceptable fairness threshold (c). The second subplot in each row denotes the cumulative return for all subgroups, and the rest of the subplots in the row denote the subgroup specific returns. The x-axis denote the number of samples used during the learning. The solid colored lines represent the running mean over the last 100 episodes for 10 random seeds for different baselines and the colored shaded regions represent the normal 95% confidence interval.
57

---

Published in Transactions on Machine Learning Research (04/2023)
Half-Chestah Variations Big-Feet High-Friction Default Half- Cheetah-ee with 500 Fairness gap.
All subgroups
8006
in
Cumulctive
800
150
2ne
Time-stope
Time-stepe
FCC PPO
Lagrangion PFO
Ninmal PPO
PPO
(a) Half-Cheelah: Test time results low fairness threshold.
Navigation: Big Regular Point Subgroups with 0.5
Fairees gap.
All subgrous
Cumulattve
Time-slepe
Time-slege
FOC-PPO
Lagranglan-PPO PPO
MI-imaPPO
PPO
(b) Point-Navigation: Test time results low fairness threshold.
Figure 13: Test time performance plots for the Half- Cheff-hheeth and Point-Navigation environments with low 10 unseen environment instantiation with different random seeds. The first subplot in each row denotes the fairness gap (maximum of absolute difference of returns between subgroups) and the black dotted horizontal line denotes the specified acceptable fairness threshold (c). The second subplot. in each row denotes the cumulative return for all subgroups. The x-axis denote the number of samples used during the learning. The solid colored lines represent the smoothed mean over random sceds for different baselincs (with weight=0.9) and the colored shaded regions represent the normal 95% confidence interval.
58

---

Published in Transactions on Machine Learning Research (04/2023)
H Other supporting results
Lemma H.1 (Hoeffding's inequality for sub-Gaussian random variables). Let ; .n be n independent random variables such that X; ~ sub Gaussian(o"). Let = En X; we have,
ntt²
- ntt
Pr(X 2 1) S exp
and Pr(X S -1) S exp 2
2a²
When o² = 1/2, i.e., XI...., Xn are 1/2-sub- Gaub-GGnsiinn random variables, we have:
Pr(X 2 t) exp (-nt²) and Pr(X - -t) S exp (-nt²)
= (8, A, H, g, P) and Lemma H.2 (Value difference lemma, Dann et al. (2017), Lemma E. E.1 Let =
M' = (S, A. ur H,g', P`) be two MDPs with different non-slationary reward funclions (g.9') g') and transition functions (P, P"). Then, for any policy n, we have the following relation:
(psg'' ,') - J" (1ig,
H
E
(S An) - An) + E(P% - PA Fa-1
P.P
(Sa, As) - -S An) + E(P PP)s-Pa('' An) id'i,, Fr-
Lemma H.3 (Lemma D.4 of Liu al. (2021)). Let 91:K be a sequence of events such that G Fk for each &e [K]. Suppose lg*h او I aB3 a 1. On good event E, for any K' s K,
K'
(G (²) _ (). < (3a + 3V2H V S11Z) A
+ 0((HH118112P144)
where K¹g =EKI 19)))
Lemma H.4 (Lemma D.5 of Liu et al. (2021)). Given sequence of events Gv.K that Gk E (F)x-1 for each 6, for any K' < K,
k E [K]. With probability at least 6,
1d (2) < 4H 2 $ + 2H|Z| KG 41n max (2,,
2HK
8
2,3,a
1(Gr)d (z, a,
ΣΣΣ
< 611 + 2H / / |/|K + 2H 21| In K3-
Imax(NN(ee 3, a,),
+ 2HK
where (2, a) denotes the namber of times the state-action tuple (z, 5,a)) was observed at time step h so far in episodes [l,..., - 1], K/- = Ek_ 1(xx), and d= is the occupancy measure of policy nh ie, d (2, a) E. (1 2, S =, 3, a) FR-
Lemma H.5 (Lemma D.6 of Liu et al. (2021)). Suppose 0 S x S + byIz for some a, b 0,
x S
b2
Lemma H.6 (Restatement of Lemma. 1 of Achiam et al. (2017)). For any subgroup E 2, function f: BR and any policy we have:
+ E (r((2,)), [((()))))))+++((())) f(3))
((Tx) = E.
[f(3]] + I-
Smp
snd! a-ms J-P.
59

---

Published in Transactions on Machine Learning Research (04/2023)
Proof. From the definition of d we have:
d = (1 - E
= (1 -1- -
1=0
where uz. d
R S denote the vector form of the estimates. Multiplying by (1-9P.) on both sides and taking inner product with vector f R
(1 PP = (1 - 7)
(1 - 7) E [[+]]+ E enudl
hS(3)
- E [ʃ(3) = O.
Brujte
8nd
E'PP
Adding the above relation with the definition of J(Tz) = I-y
1 E End (r(ss,)) we get:
amiz
3'mP=
J(TZ)= = E [S(3)
+
E and
[[((2, 8), +75(3') - [(3))
1-7
F'mP.
Lemma H.7 (Achiam et al. (2017), Lemma 3). The divergence between discounted future state visitation
distributions Joy' d3 is bounded by average divergence the policies Ti and ni:
|oy' - d5
27 [DTT((F'((T](e)))
(1 7) snd7
where (T]((T||(T(a)) 1/2 Ea (alss) x[a|s)]-
60


Reviews:
[{"review_id": "U5DSVIkmRD", "reviewer": "Reviewer_xP8J", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThe authors present a nice application of optimism and pessimism under uncertainty in the setting of different subgroups of agents.  While in Liu et al 2018 optimism is used for reward estimates and pessimism is used for cost estimates in a constrained MDP, in this paper these principles are used to balance the rewards of the various subgroups so that pairwise parity between the subgroups in expected returns is achieved.\n\n## Weakness\n\nThe motivation for studying fairness in terms algorithmic discrimination in an RL setting is not clear.  The example the authors use in the introduction is one of strategic classification where the institute creating the classification model and deploying it observes how the users behave after the entire model is re-learned.  In the credit example used, frequent decisions are not made, so the equivalence to sequential decision making seems weak.\n\nBesides the motivation, the notion of fairness used by the authors does not seem to be as similar to algorithmic fairness as claimed.  In this paper what makes the subgroups distinct are environmental \"features\" such as the initial state distribution of an agent in a given episode, the state transition probabilities, etc.  As such, the optimal policy maximizes overall cumulative return while minimizing the differences in return between the subgroups.  On the type of examples in the paper, this means a suer may take a long path on the grid or line so that the cumulative rewards are equal.  While this structural understanding of the difference between subgroups is clear, is does not seem to relate to any realistic problems where such a situation is a concern for fairness. \n\nAssumption 2.3, on which the entire analysis rests, seems unrealistic.  The authors state \"note that it is possible to leverage the techniques from Efroni et al 2003 and provide a sublinear regret result without such an assumption, however, doing so does not guarantee zero fairness violation...\", but don't explain how this violation is not guaranteed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the notion of group fairness in the online reinforcement learning (RL) setting.  In particular, by 'group' they refer to agents that belong to a certain subgroup defined on sensitive features such as race, gender, etc.  The groups are distinguished by their environment dynamics; that is, state transition probabilities and the initial state distribution.  The fairness metric is \"demographic fairness\", which is defined as parity (or near parity) in terms of subgroup specific returns for the policy, between all pairs of subgroups.\n\nIn the setting considered in the paper, finite-horizon episodic MDPs,  an agent's state space is composed of sensitive features that define the agent's subgroup, and environment specific features that determine how the agent navigates in the environment, such as the stochasticity represented in the state transition probabilities.  At the start of each episode, a subgroup is selected for the agent according to some given probability distribution.  The environment specific features such as the initial state distribution and the transition function are set based on the sensitive feature/subgroup membership selected.\n\nThe optimal policy is then one that maximizes the expected return.   For incorporating a  fairness constraint, the authors define a subgroup-specific return which is the expected value function which is the cumulative rewards in an episode, with the expectation over the randomness in the initial state (this randomness, the probability of an initial state is specific to the subgroup).   The optimal policy in this scenario then is one that maximizes the overall expected return with the constraint of minimizing pairwise differences in subgroup-specific returns.\n\nFor the proposed algorithm, the authors assume (Assumption 2.3) access to a policy $\\pi^0$ that is a feasible policy - i.e. satisfied the fairness constraints.  The learning process starts with this policy, and remains in this policy until each pairwise difference in subgroup-specific returns is below a certain threshold.  If above the threshold, the policy that maximizes the overall return is selected for the given episode.  The trajectory, and counters corresponding to state-action tuple visits, are then updated based on this policy. This iteration continues for all episodes, and a final policy derived from this algorithm is determined.  The reward estimates are shaped by optimism (sum of empirical reward estimate and uncertainty for one subgroup) and pessimism (empirical reward estimate subtracted by the uncertainty for a different subgroup). The optimistic and pessimistic reward shaping follows closely Liu et 2021 with the difference being that in Liu et 2021 pessimism is expressed in the cost estimate and in this paper the cost is reflected through the subtraction of uncertainty from the reward rather than a separate cost function.  The authors provide theorems for regret bounds.\n\nThe authors then consider the infinite horizon by setting a discount factor, and deriving a different stationary policy for each subgroup.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Motivation:  The authors should motivate why fairness is important in the specific RL settings used in the paper.  The feedback classification model and credit dataset used as examples are not relevant here because in this RL setting the agents are not strategically modifying their environment features.  So what sort of realistic problem in an RL setting would have a fairness concern?\n\nExplanation:  the various counters and constants that appear in the optimistic and pessimistic estimates under uncertainty are not explained - an intuition into these variables, such as how the scale of optimism or pessimism varies under what conditions would be helpful.\n\nMore discussion should be provided on why the techniques of Efroni et al 2003 can provide a sublinear regret but not zero fairness violation.  (At the end of Section 2)\n\nNotation:  the authors often use $\\forall i \\ge j; i,j \\in \\mathcal{Z}^2$ for what I think mean, which is all pairs in $\\mathcal{Z}^2$.  If the latter is right, then perhaps notation like $\\forall (i,j) \\in \\mathcal{Z}^2$ might be more suitable?.", "broader_impact_concerns": "Broader Impact Statement is included.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Iw1vhnZq1y", "reviewer": "Reviewer_TMDP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "------------------------------------------\nStrengths:\n------------------------------------------\n--The long-term effects of the fairness in machine learning is an under-studied topic. Hence, the paper tackles an important problem.\n\n--The paper is well-written and the details are easy to follow.\n\n--The paper takes an honest stance in acknowledging the limitation and broader impacts.\n\n------------------------------------------\nWeaknesses:\n------------------------------------------\n--The proposed notion of fairness requires a bit of justification. The authors provide a motivating example but I do not find the motivating example to be convincing. It would help to demonstrate what are the rewards, what is the objective and how the proposed notion of fairness guards against long-term discrimination.\n\n--As the authors mention Assumption 2.3 is very restrictive. Can the analysis be extended to the case that $\\epsilon^0$ is unknown? Are there ways to quantify when this assumption holds?\n\n--The algorithmic approaches taken by the authors bear great similarity with the approaches for constrained MDP. There is a discussion about this at the end of section 3, which I find to be insufficient.\n\nOverall, I think this paper as not as strong for a top tier ML conference but can be a worthwhile addition to TMLR if the requested changes are addressed adequately.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies a fairness notion for sequential decision-making. The definition of this notion requires that each state should be visited with a minimum frequency in the stationary distribution and hence can be interpreted as a constraint on the fairness-unconstrained problem. Inspired by stochastic mirror descent, the paper designs an algorithm for the fairness-constrained problem. The paper provides sample complexity analysis as well as derivatoin to show that algorithm converges to an almost optimal fair solution under specific assumptions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Many of the limitations mentioned above in the weaknesses section are marked either as future work or limitations by the authors. So I am not sure to what degree the authors can or are willing to address them. However, I think, there are certain changes that are essential before the paper becomes accepted.\n\n--A better and more clear motivating example is required to at least justify the merits of the new definition and framework.\n\n--Can the authors address my question about assumption 2.3? It would be great if the motivating example provided also show that the assumption can be satisfied.\n\n--A more through comparison of current algorithmic approaches for constrained MDP and the paper's approach is required.", "broader_impact_concerns": "The paper does a good job of maintaining broader impact. Similar to many other machine learning settings, enforcing fairness can impose a cost in the utility. The authors argue that this cost might lead to \"levelling down\" where the utility of all groups decrease. It would be good to argue a bit more about the degree in which such an affect can happen and whether there are additional assumptions which can help to avoid these consequences.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Fjbqb07aeE", "reviewer": "Reviewer_c84y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The study of fairness in ML has received much attention recently and this work fills a gap in that literature. \n- The experimental results demonstrate the effectiveness of the proposed approach in practice. In settings where the fairness threshold is easy to meet, it performs almost as well as algorithms which do not take into account fairness, while in settings where the fairness threshold is much more difficult to meet, it ensures there are no fairness violations, while naive approaches do violate fairness. \n\n\nWeaknesses:\n- The upper bound is probably not optimal ($S^3$ dependence on states, likely suboptimal $H$ dependence), and no discussion of optimality is given. It’s also not clear if the dependence on $\\eta$ (the fairness threshold) is tight. Furthermore, the algorithmic techniques seem very standard. \n- As is noted by the authors, assumption of an initial fair policy is rather strong—typically the goal of fair ML is to derive such a fair policy in the first place. I understand that this is necessary if the goal is to have no fairness violations while learning, but it would be interesting to relax this assumption, even at the cost of some fairness violations. Alternatively, it could be helpful to try to motivate the need for this assumption by practical settings where no fairness violations are acceptable, and where it’s feasible to obtain an initial fair policy (say from offline data or prior knowledge of the environment). \n- I do not find the motivating example compelling (see comment below), and as such, this paper lacks a nice practical motivation. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies the question of fairness in reinforcement learning (RL). In particular, they consider group fairness, where the goal is to ensure that the performance of a policy is nearly the same one each “group”, e.g. the portion of the population with a given protected attributed. They first propose an algorithm based on the principles of optimism and pessimism in the tabular setting which, given access to an initial fair policy, is able to achieve $O(\\sqrt{K})$ regret while ensuring fairness throughout learning. They next provide a TRPO-inspired algorithm to learn fair policies in infinite state-space settings, and demonstrate its efficacy on several deep RL benchmarks. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I was somewhat confused how the lending example in the introduction is an RL problem. In particular, it seems like in this setting, the only action the lending system can take is to either accept or reject a loan application when it arrives. There is no sequence of actions that must be taken, and therefore no sequential dynamics the lending system is interacting with. While there may be a sequential nature to the problem in terms of loan repayment, I would see this as better modeled by a bandit with delayed feedback. It should be explained more clearly how this is an RL problem, or a different example used. \n- It is stated after Theorem 3.2 that the protected attributes are selected uniformly. This seems like an important simplification, and it would be helpful to state at an earlier point (e.g. when the setting is introduced). I would also encourage the authors to expand on the discussion in Appendix C.7, work out the full result for arbitrary protected attribute distributions, and simply state that as the main theorem. \n- In the experiments, are the protected attributes sampled uniformly? It would be helpful to include an experiment where this is not the case, and there is a large discrepancy between the sampling probabilities. \n- The following paper should also be cited: \nMandal, Debmalya, and Jiarui Gan. \"Socially fair reinforcement learning.\" arXiv preprint arXiv:2208.12584 (2022).", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I think the paper could benefit from another round minor revision, where the focus is given to these two remaining concerns of the reviewers.  I wonder if there isn't another example besides bank loans that might illustrate the idea and approach better.  Maybe degree-program and course pre-requisite design where program outcomes might want to be made fair?  I hope the authors give this some thought in their revision.
Decision: Accept (poster)