Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
Authors: Eric Eaton
Marcel Hussing
Michael Kearns
Aaron Roth
Sikata Bela Sengupta
Jessica Sorrell
Venue: ICML 2025 poster (2025)
Keywords: Machine Learning
Reinforcement Learning
Fairness
Multi-Group
Minimax
ICML
Primary area: reinforcement_learning
TL;DR: We consider a type of multi-objective RL problem in the context of fairness with a large number of intersecting groups and provide oracle-efficient algorithms for the settings of both tabular and large state-space MDPs.

Abstract: In traditional reinforcement learning (RL), the learner aims to solve a single objective optimization problem: find the policy that maximizes expected reward. However, in many real-world settings, it is important to optimize over multiple objectives simultaneously. For example, when we are interested in fairness, states might have feature annotations corresponding to multiple (intersecting) demographic groups to whom reward accrues, and our goal might be to maximize the reward of the group receiving the minimal reward.   In this work, we consider a multi-objective optimization problem in which each objective is defined by a state-based reweighting of a single scalar reward function. This generalizes the problem of maximizing the reward of the minimum reward group. We provide oracle-efficient algorithms to solve these multi-objective RL problems even when the number of objectives is very large --- for tabular MDPs, as well as for large MDPs when the group functions have additional structure. The contribution of this paper is that we are able to solve this class of multi-objective RL problems with a possibly *exponentially* large class of constraints over intersecting groups in both tabular and large state space MDPs in an oracle-efficient manner. Finally, we experimentally validate our theoretical results and demonstrate applications on a preferential attachment graph MDP.

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
Eric Eaton Marcel Hussing" 1*
Michael Kearns |*
Aaron Roth
Sikata Bela Sengupta
|*
Jessica Sorrell 2*
Abstract
1. Introduction
There are number of reinforcement learning (RL) settings in which states correspond to either individuals or groups, each with their own properties, and actions correspond to the provision of goods or services among the states (Wen et al., 2021; Satija et al., 2023). For example, we could consider a road network of neighborhoods and the sequential distribu- tion of disaster relief over the region (Li et al., 2024), a set of critical locations and touring these locations provide surveillance, hospital resources (e.g., beds, ventilators) and their allocation. In scenarios like these, what should we optimize for? If we optimize for a single objective, then the benefits of the actions may accrue disproportionately to some groups of people or locations over others. there are natural groupings of states whose welfare we are concerned about (such as neighborhood demographies or disease sub- populations), then a natural fairness-motivtedd objective is minimax optimization: to maximize the reward that ac- crues to the group obtaining the minimum reward. Minimax objectives over groups have recently been studied in classi- fication problems (Martinez er al., 2020; Diana et al., 2021), and have the attractive property that they Pareto-dominat solutions that seek to equalize reward across groups; every group will have higher reward in minimax solution than they would in any equal reward solution. Problems like this are examples of RL problems with constraints (Calvo- Fullana et al., 2023; Dudik et al., 2020).
In traditional reinforcement learning (RL), the learner aims to solve single objective optimiza- tion problem: find the policy that maximizes ex- pected reward. However, in many real-world set- tings, it is important to optimize over multiple objectives simultaneously. For example, when we are interested in fairness, states might have feature annotations corresponding to multiple (intersect- ing) demographic groups to whom reward accrues, and our goal might be to maximize the reward of the group receiving the minimal reward. In this work, we consider multi-objective optimization problem in which each objective is defined by a state-based reweighting of single scalar reward function. This generalizes the problem of maxi- mizing the reward of the minimum reward group. We provide oracle-efficient algorithms solve these multi-objective RL problems even when the number of objectives is very large for tabu- lar MDPs, as well as for large MDPs when the group functions have additional structure. The contribution of this paper is that we are able to solve this class of multi-objective RL problems with a possibly exponentially large class of con- straints over intersecting groups both tabular and large state space MDPs in an oracle-efficient manner. Finally, we experimentally validate our theoretical results and demonstrate applications on a preferential attachment graph MDP.
However, as noted by Kearns et al. (2018) (in a classifica- tion setting), especially in fairness motivated problems, insufficient satisfy these kinds of constraints marginally, For example, suppose have demographic groups defined by race, gender, and income, which are not mutually exclu- sive in that no attribute determines the value of any other. Satisfying constraints marginally on, c.g., racial groups does not guarantee that the corresponding constraints are satis- fied on intersectional groups, defined by race and gender or gender and income. In general, if we have groupings of in- dividuals, there are 2d intersectional groups an enormous number for even modestly large values of d.
'Equal contribution 'Department of Computer and Informa- tion Science, University of Pennsylvania. Philadelphia. USA 'Department of Computer Science, Johns Hopkins University, Baltimore, Maryland, USA. Correspondence to: Sikata Sengupta <sikata @wwss.ssuuse.... udu...
In this paper, we study constrained RI problem in the episodic setting that generalizes the problem of minimax group faireess, and is able to efficiently handle exponen-
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
tially many constraints for example, those that arise from considering all intersections of grouping functions. We consider a problem in which the states s E 8 of MDP are annotated by feature vectors (e.g., describing the demographies of a population corresponding to state s). There is a collection of group functions G contain- ing functions g : S + {0.1} indicating (as a function of the features at a state s) whether is a member of group g or not. The groups can be arbitrarily intersecting. Every state/action pair (s, a) is associated with reward r(8,a) a) that accrues to each group g such that g(s) = 1. Given a policy n, the expected reward that accrues to group 9 is (T) = Ex [Ei r(5,, (s))(ss)), and the group- wise minimax reward maximization problem is to solve max, ming (T). Our goal to give oracle-efficient al- gorithms for solving this problem over large state and con- straint spaces i..., computational reductions to uncon- strained RL problems and optimization problems over G.
algorithm we give in Section 3.2), this algorithm has
the advantage of simplicity (and not requiring separator
set structure on 9) and is what we use in experiments; we find that empirically it works quite well.
In the above results, what actually find is a distribution over policies that are minimax-optimal in expectation. But, this naively means that for any fixed policy in the support of our distribution, the constraints might be badly violated. This would be concerning in settings in which we care about a single episode rather than the average over many episodes and has simple fix, described in Appendix A.4. Informally, we replace constraints of the form g(x) 0 with constraints of the form max [Z() < 0 which preserves convexity and eliminates the possibility that "slack" in the constraints on some policies cancel out in expectation with constraint violation in others. This is because by taking only the positive part of the constraint violation, we penalize our solution for constraint violation without rewarding it for slack.
1.1. Our Results
We give three main results:
We evaluate FairFictRL (Algorithm 4) on Barabási-Allerr graphs (Barabási & Pósfai, 2016) with groups assigned based on the degree distribution of nodes. We show that our algorithm converges efficiently to a solution with low average constraint violations for all groups, while still opti- mizing the global objective. See Section 4.
1. For MDPs with only polynomially many states - i.e., the tabular setting - we give an efficient reduction to a linear optimization oracle over G that optimally solves the constrained RL problem with constraints defined by G. independently of the cardinality of G. Here the oracle we need is for a batch/offline optimization prob- lem, which is substantially easier than the RL/control problem. See Section 3.1.
1.2. Related Work
1.2.1. FAIR REINFORCEMENT LEARNING
2.
For large MDPs, (which we cannot solve efficiently in the worst case, even in the standard singlc-objective setting), we give an efficient reduction from the prob- lem of optimally solving the contrained RL problem with constraints from G to two problems: 1) the prob- lem of finding the optimal policy in the standard (un- constrained) single-objective RL problem, and 2) the batch/offline optimization problem over g. Here we need to assume that G has special structure namely polynomial-sized separator set (Dudík
There are many notions of fairness in RL that are distinct from what we study in this paper. Jabbari et al. (2017) define notion of fairness that requires that the algorithm never play one action with higher probability over another unless the long-term reward of the optimal policy after playing the first action is higher than the second. Cousins et al. (2024) consider a welfare-centric notion of fair RL that encompasses a broad class of functions over a set of benefi- ciaries. They develop model of adversarially KWIK (knows-what-it-knonn
that it has et al., 2020)- - but fortunately the class of boolean con- junctions that define the 2d "intersectional" constraints given d groupings of the data have this structure. See Section 3.2.
learning) and provide the algorithm E (equitable E²). It is important to note that their results mainly hold only for the tabular MDP setting. Michailidis et al. (2024) use a flcxible form of Lorenz dominance to en- sure more equitable distribution of rewards and empirically demonstrate success of their method for real-world transport planning problems. Wen et al. (2021) consider model-based and model-free approaches to constrained fair RL problems and study these in the context of bank offering loans to individuals. However, these methods do not extend for a very large number of overlapping groups Satija et al. (2023) consider demographic fairness by constraining the group pair-wise difference in performances and provide theoretical guarantees for their algorithms in the tabular setting with an
3. For arbitrary grouping functions (which may not have small separator sets), we give an algorithm that makes iterative calls to standard RL algorithm for the unconstrained problem and an optimization oracle over G that provably converges to the optimal constrained policy - albeit without a polynomial time conver- gence bound. See Section 3.3. Despite the lack of a polynomial-time convergence bound (in contrast to the
2

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
empirical demonstration of success for larger state spaces. See Reuel & Ma (2024) for survey of this literature. Aside from our differing objective, we differentiate from this liter- ature by giving algorithms and theory that are able to handle both 1) very large number of intersecting groups, and 2) provable guarantees beyond the tabular setting.
2. Model and Preliminaries
We consider an episodic fixed-horizon Markov decision pro- cess (MDP) (Puterman, 2014) which can be formalized as tuple M (S. A, Ph, rh 1t), where S is the set of states, A is the set of actions, H is the horizon, rh : S x - [0, 1] is the reward function at time h, PA specifies the transition dynamics at time h, and f is the initial state distribution. For simplicity, and without loss of generality, we assume re- wards and transition dynamics are time-invariant, and denote them by r and P respectively. Without loss of generality, we assume that rewards are bounded within [0, 1].
1.2.2. CONSTRAINED REINFORCEMEN LEARNING
Calvo-Fullana al. (2023) consider the problem of con- strained RL, especially for continuous state and action spaces. In their setting, they have reward functions and optimize global cumulative reward subject to each of the m value functions for the given policy being at least as large as some threshold. To do this, they constructed aug- mented state-space MDPs and formulate the corresponding Lagrangian (with regularization) of this optimization prob- lem. They provide an efficient Primal-Dual algorithm (using different scalarized reward optimization for the learner and online gradient descent (no-regret) for the regulator). Sim- ilar to Calvo-Fullana et al., Müller et al. (2024) provide Primal- Dual algorithms and construct their Lagrangian with regularization and optimistic exploration. They prove last- iterate convergence of their algorithm, enabling them to avoid error cancellations. Ding al. (2023) also prove non-asymptotic convergence of their policy iterates for their gradient--basdddddd primal-dual algorithms via regulariza- tion or optimism.
Throughout the paper. [M] will denote the set {0. NN. 1}. We will indicate a sequence of elements 81, . 81 by $1:t We write r ~ U()) to denote sampling from the uniform distribution over set S, and y ~ Lap(p) to denote sampling from the Laplace distribution with parameter p.
In the beginning, an initial state sy is sampled from j. At any time h [M] the agent is in some state 8h & and chooses an action ap E A based on function TT map- ping from states to distributions over actions II : S + AA. As a consequence, the agent traverses to a new next state 8h+1 sampled from P(-Is,, az) and obtains a reward r(sk, (n). The sequence of functions Tr used by the agent is referred to as its policy, and is denoted " (TT (mn)neez) he(H]] A trajectory is the sequence of (state, action) pairs {(sh, an) taken by the agent over an episode of length H. In standard RL, the goal of the learner is to maximize the expected cumulative reward Exo-p,r(ED (EE H r(s;, over episodes of length H. We further define the value function as the expected cumula- tive return of following some policy π from some state as V Ee .... -1 r(st, [=, = s]. Due the finite horizon of the episodic setting, we will also need to refer to the expected cumulative reward from state under policy π from time h [H]. We denote this time-specific value function by V/ (s) = Ep EE[EE H-1 r(st, at) $4. s). For the remainder of the paper, when indices for horizon h are not listed, assume h = 0.
Miryoosefi et al. (2019) also study the problem of RL with convex constraints similarly observing a d-dimensional re- ward vector rather than a scalar. They also formulate this problem as zero-sum game between learner and regulator playing best-response vs. online gradient descent (no-regret). These algorithms require enumerating the constraints; in contrast we give "oracle efficient" algorithms that require only optimizing over the constraints, and hence can handle extremely large collections of constraints efficiently.
1.2.3. SULTMMMLUUBBETII CLASSIFICATION PROBLEMS
Agarwal et al. (2018) consider the problem of fairness in the binary classification setting and reduce this problem to a sequence (in a repeated zero-sum game between a learner and regulator) of cost-sensitive classification problems to provide a randomized classifier with low general error while (in expectation) satisfying the constraints. Kearns et al. (2018) extend Agarwal et al. (2018) to settings with a very large number of overlapping groups. They propose sta- tistical notions of fairness that take into account "fairess gerrymandering" over this large number of subgroups and reduce their problem to a sequence of weak agnostic learn- ing problems. We extend this style of algorithm from the classification to the RL. setting.
We consider a setting in which each state is assigned a feature vector x E X' over d attributes. Alternatively, we can directly think of states as feature vectors themselves. We then define set of functions G, where each function g G. X - {0, 1} represents membership in the group {ar E X g(x) = 1}.
We denote the feature vector associated with state 8 by ass), and use the shorthand g(sx) = g(x(s))). Then, for each state visited, the scalar reward r(s, a) will be given to all groups of which x is a member. So, at time t, group g receives r(st, at ()(()) Note that, more generally, we could have reward function defined over features and actions r(z, a) and think about r(z, a))(2)) as the corresponding
3

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
reward the groups to which belongs.
Defining the following compact convex set A
A = E R ||lla s cc
Now, we can formulate our problem in terms of repeated zero-sum game between a learner and a regulator. The learner is trying to find policy from a class of policies IT to optimize the expected cumulative reward (across all groups) and the regulator is trying to minimize the learner's payoff by finding groups with the lowest expected cumulative re- ward for the selected policy.
the resulting minimax problem under this formulation would be maxnean minxex U(D,)) Notice that in both cases, since the action spaces of both players are compact and convex, and the objective is affine in both variables, the con- ditions necessary for Sion's minimax theorem hold (Sion, 1958).
H-1 r(ss, an (s)g(8))ss s] Let (TT) = Es-,,, P.m hh=
Definition 2.1 (Regulator's 's Regret), For a given transcript of { [D,, A,, U(D,, (x)D,,,)))e 1=1 we define the Adversary's 's regret Xx)
and note that it is equivalent to the average reward for- mulation V = H REEH E. (r(s, (x)g(s;) and (T)((T = H BrE[m] E..x. at)]. We can consider the following minimax reward problem:
to be:
EA ((U(D.,))) minxes E [U,,,,
[T]]
Definition 2.2 (u-approximate minimax equilibrium).
max DEAlI
TーD
(I)
(D, is a v approximaae minimax equilibrium if:
subject to E [T) a, VgEg. A
U(D = min UDO, A) +v XEΛ
We call the formulation of Problem 1 a minimax reward problem because the solution that optimizes global cumula- tive reward subject to those constraints still is member of the set of minimax solutions to the problem:
U(D,)) max U(D,A) -v DEAT
Definition 2.3 (Regulator's Best Response Function).
0 if nothing violated
max min E (T)] PEALIEAAE TND g~6
Bestx
(3)
Ces
which can be solved by setting the global objective to be an optimization over o, as mentioned below. It is worth noting that while the ellipsoid method ordinarily might have been able to handle an exponential number of constraints itself, given the large dimension of the primal player's action space it may be computationally inefficient for class of problems. In order to solve this class of problems, we first formulate their Lagrangians. The resulting Lagrangian of Problem 2 is:
where k is the index of the largest constraint violated. When the number of constraints is extremely large, this best re- sponse function may need to invoke an Optimization Oracle as defined in Subsection 2.1.
For each given À selected by the regulator, we can construct the transformed scalarized reward function for the learner as follows:
(x(8,; or) = (r(se, at) + Egges 29
a))
L(D,A) AND
E
(ioo( (T) Egeg X2 (V) (T)
a)]
To see this:
H
We make couple of observations. First, notice that for = 0 this problem always has a feasible solution. More- over, if we make the objective of the optimization problem rather than Vtoo then this becomes analogous to the min- imax formulation in Problem 2. Additionally, we could always choose to set 0g 's that are tailored to the individual groups rather than using a single global value a across all groups. Finally, we can use this framework to solve a more general class of group constrained RL problems with constraints that are linear (and sometimes even convex) in the distribution over policies D. We can define the average reward objective of this problem as follows:
Σ rx(s),a))
H
= Esc
(r(s), + Σ
((r(s)) - -
"H' 111
gEG
H
H ((t,, - a]]
= Eeg
r(s + +
gEg
= (T)(())
(VV
gEg
(4)
Thus, we can define the MDP (S P,p, with the modified rewards and maximizing
U(D,A)= = E [1(8,, (z)
az) + Σ ((r((s,):))(11) ;]]
m>D
[E[H]
gEg
EIAD Baga
P

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
will provide policy which we can represent the selection of with distribution variable D that will also minimize the objective. Recall that in sequential play, the second player can achieve the value of the game via deterministic response. We once again can define the corresponding function purely in terms of feature vectors æ rather than purely in terms of states.
Algorithm MORL-BRNR (Multi-Objective RL-
Approximate Min-Max RL Algorithm)
1: Input: bound C, best-response error 9 groups, reward function, access to MDP M
2: Initialize Ag =0
3: for t = 1...., do
A4+1 no-regret-updaaee( A C) note that this will run one iteration of the subsequent no-regret algorithms /
2.1. Oracles
provided
The learner and regulator will make use of the oracles de- fined below. While we state them as strict optimizers, we observe that e-approximate versions of these oracles suffice for our applications.
6: D. = Er= d Eiz dv
7: end for
8: return (rrr)r)
Definition 2.4 (Lin-OPT Oracle). linear optimization oracle for G, Lin- Li)-OPT(c) = arg minges (ggnee (gs,c), where gs denotes the vector (g(5)), ..................... ((5ss))
and regulator in MORL-BRNR [Algorithm 1J.
T
T
Σ
E RND.
(U(,, Xe)
min XEA
E
(U( A)]
Definition 2.5 (OPT Oracle). An optimization oracle for G, (PT 1::z c) argmin (g c), where Is... denotes the vector
DD
S <reg(T, C,
where reg(T, C, is sublinear in T.
Definition 2.6 (Learner' ' Best Response Oracle), We define OUU, A) to be the best response oracle for the learner on input MDP Mx. That is, it returns arg maxp (D, A), where D point mass distribution, concentrated on single policy We will frequently use the notation T. to refer to the policy on which a best response D; is supported. We use O (U, A) to denote e-approximate best response.
In this paper, we will provide this form of a regret guarantee for the regulator with two different algorithms.
Theorem 3.2 (Approximate Min-Max). For sequence of distributions over best-response policies (D1...., DT) and Lagrangian weights from no-regret updates (Ai, XT) maintained by the learner and regulator, MORL-BRNR [Al- gorithm 1] returns a v-approximate saddle point solution (D,A) of
The learner's s best response oracle captures the assumption that for given scalar reward, one is able to run standard RL algorithm to learn an optimal policy for that given MDP. Note that in the tabular MDP setting this assumption can be realized by existing efficient algorithms for learning near- optimal policies, such as E (Kearns & Singh, 2002) or
Proof. Provided in Appendix A.1.
3.1. Tabular MDPs
R-max (Brafman & Tennenholtz, 2002).
In the case of tabular MDPs, we adapt the algorithm Follow the Perturbed Leader (FTPL) given by (Kalai & Vempala, 2005) learning setting.
3. Algorithms and Theoretical Results
Lemma 3.3 (FTPL. Regret). For any sequence (D:) se-
We will present our theoretical results in the following man- ner. For the settings of tabular MDPs and large state spaces with structured groups, we will first provide a general al- gorithm and analysis in terms of arbitrary no-regret al- gorithm used by the regulator. We will then provide the specific regret analysis corresponding each no-regret al- gorithm/setting used by the regulator. Finally, for the setting of large state spaces with general groups, we will provide a different algorithm and provide corresponding analysis. We use a modified version of the algorithm presented in (Agarwal al., 2018) in Algorithm 1.
lected by the learner. for T 2 max 32c 20 with probability least - 5,
In 2
h Σ U(Dr,Ad) - min XEA
H
Σ
Proof. Proof provided in Appendix A.2.
Corollary 3.4 (Tabular Apx- With probabil- ity at least 1 8, using Algoritim 1 with FTPL (Al- gorithm 2) converges to a v-approximate equilibrium in poly(}, 1 [S], log ll).
Theorem 3.1. (Informal)(No-Ke Regret Player Guarantee] For a sequence of best-response policies (Di..., Dr) and Lagrangian weights (A1,..., Xr) maintained by the learner
5

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
Algorithm 2 FTPL in Tabular MDPs
Algorithm 3 Contextual FTPL in Large State Space MDPs
1: Input: 9 groups, r reward function, access to MDP M,
1: Input: 9 groups, Fi:d sequence of separator elements,
1=
2/S/T
C
r reward function, access to MDP M. p = V Td77
|og [g]
2: Initialize cumulative losses co(s) = 0 Vs
2: Initialize Ao =0
3: fort= -,...., do
3: for 1 = ,,..., do
4: Receive D, from the Learner
4: Receive D. from the Learner
5: Sample noise vector N M((, 1111))
Draw f/2 Lap(p) independently for -- d
6: Define (5 DID cs(s cumulative cost seen
6: Let $7-1 $1:0-1||a1:d be the sequence of contexts
played thus far, concatenated with the sequence of separator set elements
so far
7: 9r +-inn-OPT(c" NN)
7: Let v = -1--11 be the sequence of actions played thus far, concatenated with the sequence of noise elements
8: Assign Xg,t based on the selection of 9i (i.e. Cea for
min group k from St. 0 elsewhere)
9: Sample (st, at) by executing a trajectory under Dr
and returning (8p: ax), for h ~ ((H)
gt OPT( w
10: Observe (s{) (())aa))
9:
Assign X based on the selection of gt
10: Sample (st, 02) by executing a trajectory under Dr and returning (sh, ax) for h ~ U(H)).
11: end for
11: Observe 3/2 = r(5,, (z) and receive (ege(s))
Proof. For 7 S 1/2 and e < 5. this satisfies the no-regret condition necessary for Theorem 3.2 to hold in the corre- sponding time specified by Lemma 3.3
12:
end for
Neel et al. (2019) note that many discrete concept classes that are well-studied in the PAC learning literature in d- dimensions like boolean conjunctions, disjunctions, parities, and halfspaces defined over the boolean hypercube have separator sets of size d. In our setting, we make use of the fact that we can represent group membership in terms of conjunctions over the d-dimensional feature space.
3.2. Large State Space MDPs and Groups with Separator Sets
When we are no longer in the tabular setting (and therefore cannot directly run FTPL over S), it is computationally in- efficient to run FTPL over a very large collection of groups Therefore, we utilize a contextual variant of FTPL (Syrgka- nis et al., 2016; Dudík et al., 2020), which is computationally efficient in very large action spaces. We briefly recall the set- ting of contextual FTPL, and formulate our learning problem in this setting. At each time step 1, the adversary (learnrr) selects a context E Σ and and action Y/ E y. The reg- ulator then chooses a policy 1/. E V and receives payoff ((b(o)) )e). To capture our reinforcement learning prob- lem, we take Σ S = [0, 1]. and Vे = G. The choices of the adversary at round will be determined by the policy D, learned by the best response oracle round l. The adversary selects its context and action by first sampling h ~ ((HH) and executing a trajectory 7 under D, to obtain (sh, an). The adversary then selects its action to be y/ = r(se, az), for ag = (s). The payoff function received by the regula- tor is then ((((s)).r((; a:)) = g(*)))(ss,)) a:).
Lemma 3.6 (Contextual FTPL. Regret). For any sequence C2/20/2 log [
of costs et, for T 2 O probability at least 1 1 8, the expected regret of FTPL
+ C In( (g) 1), with
7
H
H U(D
U(D..A)
min XEA
Σ
t=1
Proof. Proof provided in Appendix A.3.
Corollary 3.7 (Contextual FTPL Apx-Minimax). With prob- ability least 1 8, using Algorithm I with Contextual FTPL (Algorithm 3) converges u-approximate equilib- rium in poly( (2, 1.2 d, (9l).
Proof. For S 2, e 5. Theorem 3.2's no-regret condi- tions are satisfied in the times specified by Lemma 3.6.
The contextual FTPL algorithms of (Syrgkanis al., 2016; Dudík al., 2020) efficient even in our setting of large state spaces and large G only under the assumption of sepa- rator sets for the class of groups G.
3.3. Large State Space MDPs with General Groups
For large state spaces with general group structure, we uti- lize Fair and Fictitious Play (Follow the Leader (FTL) vs FTL) (Brown, 1949). Fictitious Play is easier to implement as it is a deterministic algorithm and it only requires one or- acle call per player. However, it is only theoretically known to converge to an equilibrium in the limit.
Definition 3.5 (Separator (Goldman et al., 1993; Syrgkanis et al., 2016)). A set X C S is a separator for groups g if for any two groups g. E 9 there exists a context & E S such that gss) # (s)).. . For a separator X of size |X| = d, we use Fi:d to denote a sequence of separator set elements.
6

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
10
18
18
19
19
14
24
15
15
(a)
(b)
Figure 1. Depiction of the Barabási-Alhert graph other nodes. Every state also has self-loop action to remain in place. The groups are assigned depending on the number of outgoing edges. All nodes with 2 outgoing edges are Group nodes with outgoing edges are Group and all others are Group 2. Rewards r(s, a) are assigned as 0.1 for all in Group 1, 0.2 for all nodes in Group 1 and 0.3 for nodes in Group 2. The start state is random node the graph in every episode. Figure (a) shows occupancy distribution the (non-fair) optimal policy. As we can see, the non-fair policy's goal is to quickly get to one of the nodes with 5 edges (Group 2) and stay there indefinitely to accumulate reward. After running our FairFictRL algorithm in Figure (b), distribution over nodes almost evenly spread across all nodes. The only outlier is node 8, it is the only node that belongs to Group and thus requires large visitation number to satisfy our constraints.
MDP. Nodes correspond states and actions deterministic moves
Algorithm 4 FairFictRL
4. Experimental Results
1: Input: bound C, best-response e, G groups. reward function, access to MDP M
The experimental section focuses on an evaluation of the FairFictRL algorithm. FairFictRL a very easy to imple- ment version of our framework and even though it only has asymptotic guarantees, will demonstrate that it can quickly converge to desirable solutions in practice.
2: Initialize XØ = and A = Ag
3: Initialize D, by selecting policy in II
4: for = 1,..., T do
5: D. E (TL((,-1,C)) using (
returns
maxp UDD, S4-1)
4.1. MDP construction
6: A FTL(D,-1, C*) using Best (De-1)
returns
Preferential attachment graphs commonly used model of social networks exhibiting a "rich get richer" distri- bution of connectivity. We construct multi-objective RL task based on such graphs using the Barabási-Albert model (Barabási Pósfai, 2016). in which nodes with higher degree tend to have higher probability of forming connections with newer nodes on the network. In rounds, node is added the graph until the final number of nodes is reached. Each new node forms ne new connections with probability proportional to the degree of existing nodes. Using this model, we construct the following graph MDP. The state space corresponds to the nodes on the graph and actions edge selection on the current node. There is a scalar reward of r(s, a) each time edge selected from node. Each node is assigned to possibly several intersecting groups based its degree. A learner is trying to traverse the graph with the goal of maximizing total cumulative reward, while maintaining that all groups receive at least average reward a/ H. The graph we consider is depicted in Figure 1.
7: D. : E1E De; Åe- Ei
8: end for
9: return (Dr,
Lemma 3.8 (FairFict Convergence). (Robinson, 1951) Fair- FictPlay converges in the limit an equilibrium.
Robinson (1951) showed that fictious play converges in the limit equilibrium. Daskalakis & Pan (2014) showed that the convergence can be exponentially slow in the worst- case, at least with adversarially selected tie- tie-breaking rules. Nevertheless, in non-adversarial settings it appears to be a practical algorithm. We use this algorithm in our exper- iments and also empirically demonstrate that it performs well, despite other algorithms' stronger theoretical guaran- tees.

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
4.2. FairFictRL, Evaluation
0.30
Group 0
First, we run FairFictRL with a minimum value of average group reward that we want to achieve of f 0.04. Given the reward stucture in the graph, it is not the case that all groups will obtain this reward under the optimal policy. We use standard value iteration as an oracle for the learner; for nigher-dimensione problems, this could be substituted with a deep RL algorithm. The regulator runs the policy returned by the learner for 500 episodes to obtain an average reward estimate and best responds according to Definition 2.3 with C'e 25. The results are shown in Figure 2.
Croup
0.25
Group 2
V*
Average Reward
0.15
0.05
0.00
0.01
0.02
0.03
0.04
Minimum Average Reward per Group
Figure 3. Total average reward compared to per-group average reward for varying a. As the fairness constraint increases, total reward decreases while group rewards equal out until eventually all groups obtain the same average reward.
0.30
Group
Group
5. Conclusion and Future Work
0.25
Group
Average Group Rewards
0.20
We consider MDPs with possibly an exponentially large number of intersecting groups over states. For solving a class of corresponding constrained or multi-objective optimization problems over these very large number of objectives, we provide several oracle-efficient algorithms. Namely, we provide algorithms for tabular MDPs and large state-spaces with separator sets over groups. In these ap- proaches, we reduce the learner's problem to that of standard RL with one scalarized objective to learn a near-optimal policy. We reduce the regulator's problem to one of lin- ear optimization. We also provide a version of Fictitious Play for large state-spaces with general group functions that has provable asymptotic guarantees. In practice, our experi- ments showed that they converge quickly for the preferential attachment graphs provided in our paper.
0.15
0.10
0.05
0.00
20
40
60
80
100
Iteration
Figure 2. Average reward groups during of FairFictRL on the MDP depicted in Figure 1 for = 0.04. The optimal move any Group node
(non-fair) bchavior in the MDP and stay there indefinitely, which achieves at most 0.3 average reward. run FairFictRI,, the leamned mixture policy quickly ensures that all groups obtain at least Y average reward.
Limitations and Future Work Of course, each of these reductions relies on our ability to efficiently implement our Best Response and Optimization oracles. Moreover, many of our results are reliant on boolean group structure. would be interesting to extend results beyond exponen- tially large group classes to infinite group function classes. We also hope to apply these results to the setting of Rein- forcement Learning with Human Feedback, especially with access to more fine-grained subgroup data.
As can see, after only a few iterations, all groups obtain 0.04 average reward, which is consistently upheld through- out the execution of the algorithm. Furthermore, we demon- strate in Figure that this corresponds to a more evenly distributed occupancy of the graph.
A Acknowledgements
Finally, we analyze the Pareto frontier between fairness and maximum cumulative reward that be obtained by varying values of a in Figure 3. The results highlight that by increasing the minimum average reward that we enforce, our algorithm equalizes the rewards between all groups more an more. This comes at the expense of total reward tot which highlights the trade-off between fairness and optimality.
This research was partially supported by the Simons collab- oration algorithmic fairness, NSF grants FAI-2147212 and SCFF-2217022 the Army Research Office under MURI award W91 10F201-1100000 -0080, the DARPA Triage Challenge under award HR001 1240015 and by the University of Pennsylvania ASSET center. Any opinions, findings, and
8

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
conclusion recommendations expressed in this material those of the authors and do necessarily reflect the view of DARPA, the Army, the US government. We would also like to thank Alejandro Ribeiro for his discus- sions with us. We would also like to thank Michael Dinitz for helpful conversations with us.
References
Agarwal, A., Beygelzimer, A., Dudik, M., Langford, J., and Wallach, H. A reductions approach to fair classification. In International conference on machine learning, pp. 60- 69. PMLR, 2018.
Barabási, A.-L. and Pósfai, M. Network science. Cam- bridge University Press, 2016. ISBN 177070766 1107076269.
Impact Statement
This paper provides largely theoretical work algorithms to give guarantees of RI. algorithms to large number of possibly intersecting groups in both the tabular and large state-space setting. We hope that this work will be used to consider more seriously the guarantees to more marginalized groups of standard sequential-deco -decision making algorithms and hope that more work is built consider variety of guarantees that ensure fairness in the form definition that is best for each application. We do not feel that there are any major societal consequences (especially of negative nature) that need to be highlighted here.
Brafman, R. and Tennenholtz. M. R-max-a general poly- nomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct): 213-231, 2002.
Brown, G. W. Some notes on computation of games solu- tions. Rand Corporation, 1949.
Calvo-Fullana, M., Paternain, S., Chamon, L. F., and Ribeiro, A. State augmented constrained reinforcement learning: Overcoming the limitations of learning with rewards. IEEE Transactions on Automatic Control, 2023.
Cousins, C., Asadi, K., Lobo, E., and Littman, M. On welfare-centric fair reinforcement learning. In Reinforce- ment Learning Conference, 2024.
Daskalakis, C. and Pan, Q. A counter-example to karlin's strong conjecture for fictitious play. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 11-20. IEEE, 2014.
Diana, E., Gill, W., Kearns, M., Kenthapadi, K., and Roth, Minimax group fairness: Algorithms and experiments. In Proceedings of the 2021 AAAI/ACM Conference on Al, Ethics, and Society, pp. 66-76, 2021.
Ding, D., Wei, C.-Y., Zhang, K., and Ribeiro, A. Last- iterate convergent policy gradient primal-dual methods for constrained mdps. Advances in Neural Information Processing Systems, 36:661 (1166138-66000) 2023.
Dudík, M., Haghtalab, N., Luo, H., Schapire, R. F.,, Syrgka- nis, V., and Vaughan, J. W. Oracle-efficient online learn- ing and auction design. Journal of the ACM (JACM), 67 (5):1-57, 2020.
Freund, and Schapire, R. E. Game theory, on-line pre- diction and boosting. In Proceedings of the ninth annual conference Computational learning theory, pp. 325- 332, 1996.
Goldman, S. A., Kearns, M. J., and Schapire, R. E. Exact identification of read-once formulas using fixed points of amplification functions. SIAM Journal on Computing. 22 (4):705-726, 1993.
9

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
Jabbari, S., Joseph, M., Kearns, M., Morgenstern, J., and Roth, A. Fairness in reinforcement learning. In Interna- tional conference machine learning, pp. 1617-1626. PMLR. 2017.
Reuel, A. and Ma, D. Fairness in reinforcement learning: A survey. In Proceedings ofe AAAI/ACM Conference AI, Ethics, and Society, volume 7, pp. 1218-1230, 2024,
Robinson, iterative method of solving game. Annals of mathematics, 54(2):296-30,, 1951.
Kalai, A. and Vempala, S. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-333 2005.
Roth, A. (ed.). Learning in Games. Philadelphia, PA, 2024.
Satija, H., Lazaric, A., Pirotta, M., and Pineau, J. Group fair- ness in reinforcement learning. Transactions on Machine Learning Research, 2023.
Kearns, M. and Singh, S. Near optr-mltimal reinforcement learn- ing in polynomial time. Machine learning, 49:209-232, 2002.
Sion, M. On general minimax theorems. 1958.
Kearns, M., Neel, S., Roth, A., and Wu, Z. S. Preventing fairness gerrymandering: Auditing and learning for sub- group fairness. International conference on machine learning, pp. 2564-2572. PMLR, 2018.
Syrgkanis, V., Krishnamurthy, A., and Schapire, R. Efficient algorithms for adversarial contextual learning. Interna- tional Conference on Machine Learning, pp. 2159-2168. PMLR, 2016.
Langley, P. Crafting papers machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Wen, M., Bastani, O., and Topcu, U. Algorithms for fairness in sequential decision making. International Confer- ence on Artificial Intelligence and Statistics, pp. 114- 1152. PMLR, 2021.
Li, D., Zhang, Z., Alizadch, B., Zhang, Z., Duffield, N., Meyer, M. A., Thompson, C. M., Gao, H., and Behzadan, A. H. A reinforcement learning-based routing algorithm for large street networks. International Journal of Geo- graphical Information Science, 38(2):183 185-21,,, 2024.
Martinez, N., Bertran, M., and Sapiro, G. Minimax pareto fairness: A multi objective perspective. In International conference on machine learning, pp. 6755 PMLR, 2020.
Michailidis, D., Röpke, W., Roijers, D. M., Ghebreab, S., and Santos, F. P. Scalable multi-objective reinforcement learning with fairness guarantees using lorenz dominance. arXiv preprint 2rXiv:2411.18199 2024.
Miryoosefi, S., Brantley, K., Daume III, H., Dudik, M., and Schapire, R. E. Reinforcement learning with convex constraints. Advances in neural information processing systems, 32, 2019.
Müller, A., Alatur, P., Cevher, V., Ramponi, G., and He, N. Truly no-regret learning in constrained mdps. In Inter- national Conference on Machine Learning, pp. 36605- 36653, PMLR, 2024.
Neel, S. V. Roth, A. L., and Wu, Z. S. How use heuristics for differential privacy. In 2019 IEEE 60th Annual Sym- posium Foundations of Computer Science (FOCS), pp.
72-93. IEEE, 2019.
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
10

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
A. Appendix
A.1. Proof of Theorem 3.2
We want to show that + ΣΣ Ae: $ T
Σ Dr converge to an approximate minimax solution of the game if we have that
Σ (D((.
min Dwin
& (R,
and that
Σ [U(
- E [U(DnA) regg((T,C,)
max
λEA
which are sublinear in T. We want to show that:
First for any X,
want to show: U(DT,A) A) 2 UDDT, AT) 1 (r))
(5)
( 1
U(fr,>) A)= = U
Σ Drnd)
(linear D)
(6)
T
T
T Σ A(D,,A)
T
1 (U(D,, T (ega(TT.C,) C,n) (because no-regret)
(8)
T
((DD,)))) 1 (C:)
(because apx-best response)
(9)
T
UDDr, )T) - C,,) -e (because linearity)
(10)
(11)
Second for any D,
want to show: U(D S U(Dr Sr) + (T,)
(12)
1 T
U(D = T t=1
U(D,))
(13)
1
U(D +c (because D, is apx- response)
(14)
(()), 1
$
(re C,7) +e (because no-regret)
(15)
T
= U(Dr, ST) 1 CT) (because linearity)
(16)
Thus, for any X, D:
U(D, 1 - SU(T)))))))))))))))))))))))))))) (e) +e
So vf 2 1 rege (T, (T,C, Y) + then we have gotten an approximate minimax solution using (Freund & Schapire, 1996). Note that this algorithm makes O(T) best-response oracle queries and (TT) Lin-OPT queries for the learner and regulator respectively.

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
A.2. Proof of Lemma 3.3
Proof. (Kalai & Vempala, 2005) and (Roth, 2024), FTPL's regret can be bounded by
+ Σ (r(s
min 1 T gEg
Σ (r(s)) ())))(())))))
vT
80 of
For For T>
we have that
T
T
Σ (r(se, (()))
min
Σ (r(s,, (())(()))) $ C gEg T
71
Recall the definition of (T+) = H E Er (+)g(++))- Define Y, = +(((se, (())) (r(8), (r))),++)) THr
1 ((V% (TT)) - (V)())))). We can show that the difference sequence {Y:) forms a Martingale Difference Sequence.
Therefore E, Yt also forms a Martingale. Using Azuma-Hoeffdingg inequality, for any À E A
1 - (r))))))))))(())) - (r(s), (z)))
((VD) (T+)) (v 2 ) S exxp
-2
Pr
TH
C
Union bounding over all groups, we want
-2T
2|9 exp
S 6.
C
Therefore, for T 2 C² In (2g))) ), with probability at least 1 - 8, for all groups E g, 2c3
min(((st,, ax))g((e))
min
s 72
gEg
TH
9Eg
Therefore,
(99 (T+))
min gE9 TH
1
Σ (v9
5
+
C
Notice that
T
T
(r(s), ((())))))(())))) - min
(()s),))))(55)))
gEg
1=1
T
T
a ((te ar) + +r(s, a))((())))))
-mmin gE9
Σ
r(s,, at) + (r)(s,))))(s)) a
H
T
H
[=1
Similarly,
1 T
T
1
(V (v)))
min
Σ (v)
TH
gEG TH
(=1
t=1
T
T
tot (me) + V (TT) aa)
(min
ptt (T)) + V9(T)) - -a)
TH
H
gEG TH
H
1=1
11 + 72
C
To see the final connection with the objective U, we need to introduce X. Observe that we could have defined the action space of FTPL in terms E A, where for every g. A E R and (s) = Cg(s). That is, every selection of g E G has a corresponding 2 E A which puts weight C on the dimension corresponding to the gth group. is important to distinguish different representations of X.
|g)-dimensional vector over groups \", however, an [S]-dimensional vector
12

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
over the state space for the selected group g. We acknowledge that overload this notation because X without mention of state refer the weight placed by the regulator that group. Hence, for given selected À E A, (s) to denote the corresponding group selected out of that regulator weight assignment and then its corresponding values over the state space. This notation makes explicit the implicit relationship between group selection and À selection. We a by the corresponding \ (st) or {*(x)) value To get Ca (notice that the vector À E R191 is C' times one-hot encoding). Similarly, H
the notation
can scale the above terms r(se, at (8)) и and r(8t, a (*)((*)) и
r8e, ae) )0)))*((s))
Ca and r(sr, ai (s)) "I
T
T
1 ylod (Te)) (Te) J H
Σ 1 9EG
1
Σ
V9 (v a))) - (
1
Vlol (TT) (Te) min
Σ
19
Σ
(V (v a)))
TH
H
DEG gEG
TH
S m + 72
Finally,
1 H
min 1 H
T Σ
Σ
U(D s
X T
for 71:72 2 and noting that n,, is the policy specified by Dr-
A.3. Proof of Lemma 3.6
Proof. We utilize (Syrgkanis et al., 2016) and (Dudik et al., 2020) for our regret bound and construction. (Syrgkanis et al., 2016) prove that for Laplace noise Lap(p) and groups with separator X of size d = |X], their contextual FTPL. algorithm enjoys regret
T
(r(se, (c))g((s)))
min gEg
Σ (r(s a:)))(si) T
1
(i))
5o
pd T
E
Vdlog((9i)
T
ges
ges
pf
1=1
d3/4
log
G
0
VT
for optimal choice of p. and runs in time poly(d, T, Tolog(( (og(())). Therefore, for the below condition to hold, we would need d223/2 log
T
7f
We will use similar notation and arguments to the proof of Lemma 3.3. For T > C2 log
T Σ (r(se: (8))
T
-
min
Σ 1=1
(r(s), ()))((()))))))))))
71 -
gEg T
C
Once again, we use a similar argument the proof of Lemma 3.3, Using Azuma huuma-Hoffdiiggs inequality for given X,
Pr (r(s, (r(se, (()()))))))(s)))
(V (mx)) (V*(T)))) 2 exp -2T
TH
C²
Union bounding over all groups, we want
-2Th2 2
2/9 exp
C < 6.
Therefore, for T 2
C² In (111) with probability at least 2ng
6, for all groups g E G
1 }- (1r(s) (( (s)))))))))))))))))))))))))))( - (an(r(ss.a)))(ss)))
((V (V
min
s ?2
gEō
TH
gEG
C
Therefore,
1 ((V)
21 72
(v
min gEG
<
TH
TH
C
13

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
Finally using very similar argument to the proof of Lemma 3.3 relate to X,
1
1 Σ U(D1, A) S
U(De: Ax) -min XEA T
T
for Y1, 72 =
A.4. Error Cancellations
Recall the constrained RL problem:
E [Vto((T) anD
max DEALI
subject to RnD
E
[T)
Vgg E
In this section, we will use the shorthand AV (T) to denote the average reward rather than ( and (V*(m) for the
average reward to group g. Now, we will also define AV (D) Bg~D[AVion (=) and (V) Eg D[VV [AV*
Now define (D) AV*(D) and f(D) AV Now, rewrite the constrained RL problem
max
F(D)
DEAMI
subject to h (D) 0, E g
Now, notice that (D) is affine (and therefore convex) in D and 0 is constant max(h²(D),0f is convex in D. Therefore, rewrite optimization problem
max
f(D)
DEAT
subject to max(h < 0, Vg E
Notice that the feasibility sets over D are the same between these two problems. Now, we can write the following Lagrangian.
L(D, J(D) Σ ((max((((()))))
9Eg
The conditions of Sion's minimax theorem still hold for this Lagrangian. Observe that for this objective, when considering the notion of average violations, one does not face the issue error cancellations because the max term is always nonnegative. For the learner, we can define new scalarized reward function in terms of the regulator's selection of À for which it can utilize the standard approximate best response oracle. Observe now however, that k9 D)) is now convex in D rather than linear, but we still need provide estimates of max()+(D)) 0}.
Define k(x) max (r, 0)- We to bound (k()(DD)) k(h0 (D)) Notice, that get good estimate of hD())) we will sample from this procedure and average the following: sample policy from D, and generate a trajectory, then uniformly sample a time step h and receive the corresponding an, r(s,, ax). Now, we will average a sufficiently large number of terms ft r(sh, ah (g(s)) to get estimate for (D) within c' using Hoeffding's 's inequality. Union-bounding over groups, we want 2|gle 2nc" < 8', which requires 2 222 d
In(2[0]) We would like é' e O ( (because of its
contribution overall regret). Therefore, would like T |m((2)91) Now assume that with probability least 1 8', for all g E G. (D) - (D)) < é'. is important to note however, that since the objective is now concave D, rather than linear.
Tx(s,, = r((e ar) - - X max((+
9Eg
Notice that this reward has some error from the "true" scalarized reward and therefore, our learner will be approximate best responding.
14

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
Theorem A.1 (Approximate Min-Max Error Cancellation). For sequence of distributions over best-response policies
(Di,.,, Dr) and Lagrangian weights from no-regret updates (A1y...g Xr) maintained by the learner and regulator, MORL- BRNR [Algorithm| 1] returns a v-approximate saddle point solution (D, 2) of L.
Proof.
First for any X,
1
want to show: C(Dr, 1) C(Dr, Ar)
C,) -e
(17)
1
C(DT, A) L
Σ
Dr,
(linear in D)
(18)
T
T
(()
(concavity inD)
(19)
T
(C(Ds, Ae)) (egA(T, (because no-regret)
(20)
C(D Ar) 1 (T,
(because apx-best response)
(21)
= C(Dr, )x) T reg)(T,C,n) C,n) - (because linearity)
1
(22)
(23)
Second for any D,
want to show: L(D,Ar) s C(Dr, 2r) - Ce)
C,7) te
(24)
L(D,\r)
T Σ ((D,N))
1
(25)
L(Dr, + (because D, apx-best response)
(26)
T
$ T
Σ L(D,, (7)) + reg)(T, C,77 +
(because no-regret)
(27)
s ((Dr, + rega(TT C,7) +e
(because concavity)
(28)
Thus, for any X, D:
C(D, 1 (Te)
1 A) Fregu(T,C,)) +
if 2 (T, + c, then we have gotten an approximate minimax solution using (Freund & Schapire, 1996). Note that this algorithm makes O(T) best-response oracle queries and O(T) Lin-OPT queries for the learner and regulator respectively.
Furthermore, notice that if we wanted to return one policy rather than D (deterministic), we could evaluate our selection of policies and based upon the best performing one could make a probabilistic argument for how likely that single policy is to simultaneously satisfy all constraints.
1. GENERALIZED FTPL
We still get our regret bound with respect to y for sufficient polynomial sample complexity.
15

---

Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
Algorithm 5 Contextual FTPL Error Cancellation
1: Input: 9 group functions, 21:d sequence of separator elements, reward function, access to MDP M,
log G
Td
number of samples per iteration
2: Initialize λg =
3: for = ,...., .' do
4: Receive D. from the Learner
5: Draw ~ Lap(p) independently for = 1,..,, d
6: For all g E G, let I = (9e(a1)...... 9t....---9((( (ra)) in the following:
Select 9: such that Li=o (gt) - at, I ((1 ((g) + + I + c for all
7: Assign d based on the selection of
8: Generate n samples of {st, a,, r(s a;)}== by creating n independent trajectories of D2 and uniformly sampling
from [H] in each one and computing an estimate of average reward and define Vt., = r(s;,))))
9: Receive ce(ge) max a T 1==1 (r.:gs))))
10:
end for
Lemma A.2 (Contextual FTPL Regret), For any sequence of costs ct for T 2 O (C2
log
C²
with In( (1(1)))
+
2/2
probability at least - 8, the expected regret of iTPL
min
A)
Proof. Although the sample complexity of our result changes-(now we require n? samples rather than purely earlier), the regret bound from Lemma 3.6 should still hold with 7/1 7/2 شnة Also observe 8'
Corollary A.3 (Contextual FTPL Apx-Minimax with Error Cancellations). With probability least 1 8, using Algorithm 1 with Generalized FTPL (Algorithm 5) converges to v-approximate equilibrium in poly( 4,, 3 d, log G))
Proof. For < 2 and e S 5/2 + é', this satisfies the no-regret condition necessary for Theorem A.I to hold in the corresponding time specified by Lemma A.2
A.4.2. FICTIOUS PLAY
Notice that for Ficitious Play, all the convergence results discussed for Algorithm still hold.
Algorithm FairFictRL. Error Cancellation
Input: bound C, best-response error c, 9 groups, r reward function, access to MDP M
2: Initialize AØ and X Xg
3: Initialize D; by selecting a policy in
4: for t 1.....7 T do
5: D. E (T C) using Oc(, St-1)
returns max L(D, Št-1) returns max, L(D(-1,))
6: A (TL(D,,>) --1 C) using Best, (D,-1)
D. = Drs d, Σt
8: end for
9: return
(Dr,ir
16


Reviews:
[{"review_id": "b1TPCxudeU", "reviewer": "Reviewer_xri7", "summary": "This paper explores the problem of intersectional fairness in reinforcement learning (RL) with large state and constraint spaces, proposing several oracle-efficient algorithms to optimize multiple objectives simultaneously while ensuring fairness across intersecting demographic groups. The authors provide theoretical guarantees for their algorithms and validate their effectiveness through experiments on a preferential attachment graph MDP.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer xri7, \n\nWe appreciate the positive assessment of our work.\n\n**Deep RL experiments** As we highlight in  Section 5 on Future Work, we completely agree that deep learning poses an interesting future direction for this type of work. However, the current manuscript is largely a theoretical contribution and we believe that moving to deep learning will come with its own challenges and open questions such as studying the effects of potentially sub-optimal oracles in practice, which will likely warrant a different type of publication. Our experiments primarily aim to verify the effectiveness of our FairFictRL algorithm. This algorithm is very easy to implement but, unlike our other algorithms, it does not come with with polynomial-time guarantees. Yet, our experiments validate that this easy version of the algorithm might be a feasible alternative in practice.\n\n\n**Applications** Fairness in Reinforcement learning plays a large role in various applications such as healthcare or loan approval. However, we believe that one of the most interesting applications in our current timeline is the application to Reinforcement Learning from Human Feedback (RLHF). Our technique could be a step towards preventing LLMs from outputting discriminatory or toxic prompts to various (intersectional) groups. We will update the paper to include additional discussion of this application.", "claims_and_evidence": "good", "methods_and_evaluation_criteria": "good", "theoretical_claims": "good", "experimental_designs_or_analyses": "good", "relation_to_broader_scientific_literature": "good", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "see questions", "other_comments_or_suggestions": "see questions", "questions_for_authors": "This paper explores the problem of intersectional fairness in reinforcement learning (RL) with large state and constraint spaces, proposing several oracle-efficient algorithms to optimize multiple objectives simultaneously while ensuring fairness across intersecting demographic groups. The authors provide theoretical guarantees for their algorithms and validate their effectiveness through experiments on a preferential attachment graph MDP. I am unfamiliar with this specific area of research, so my comments may not be highly technical, but I have a couple of concerns.\n\nFirstly, why did the authors not conduct experiments using deep reinforcement learning algorithms? Given that deep RL is widely used in complex, high-dimensional problems, it would be interesting to see how well the proposed methods perform in such settings. This could provide more insights into the scalability and practical applicability of the algorithms.\n\nSecondly, I am interested in the potential applications of this work. The authors mention fairness in RL, which is a critical issue in many real-world scenarios. However, it would be helpful to discuss more specific scenarios where this algorithm could be particularly impactful.", "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": "", "extra_scores": {}}, {"review_id": "XvUZeR5cY8", "reviewer": "Reviewer_sNea", "summary": "This paper studies a constrained RL problem in the episodic setting that generalizes the problem of minimax group fairness, allowing for exponentially many group fairness constraints due to the intersection of grouping functions. The authors focus on developing oracle-efficient algorithms for solving this problem in large state and constraint spaces. Their key contribution lies in providing solutions for three scenarios: tabular MDPs, large state space MDPs with separator sets assumed groups, and large state space MDPs with general groups. They propose two FTPL-based algorithms for the first two settings, and a Fictitious Play-based algorithm for the third. Theoretically, they provide regret bound for the first two settings. The effectiveness of the third algorithm is demonstrated empirically through a graph-based simulation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer sNea,\n\nThank you for your positive assessment of our work and your feedback.\n\n**Additional Experimental Simulations** The experimental study that we\nprovide is used to highlight the applicability of our FairFictRL algorithm. Fictitious Play is easy to implement in practice because it only relies on Follow the\nLeader for both players and does not require noise generation that scales with the\ndimension of the action space. However it does not come with polynomial-time\nguarantees and our experiments aim to verify that it is still a good choice in\npractice. The Follow the Perturbed Leader-based algorithms themselves already\nhave provable guarantees to converge, and we believe that adding additional\nexperiments here may distract from the main message of the experimental section.\n\n**Optimization Oracles and Experiments** In our experiments we consider a\ntabular MDP, for which the best response oracle is implemented via value iteration. The\nregulator can select the group that minimizes the past cumulative cost by iterating over the groups,\nbecause the number of groups is small in this experiment; in practice would need to use a stronger\noptimization oracle that is able to do linear optimization efficiently. In the case\nof conjunctions, this might also involve Integer Linear Programs or Mixed Integer\nPrograms. Regarding MDP access, none of our algorithms require direct access to the MDPs. We only assume access to the\nMDP in our experimental section, in which we use value iteration to implement our best response oracle.\nWe will update the wording in the manuscript to make this more clear. \nNote that to implement the best response oracle, we simply need to be able to optimize a\ngiven specified reward function within an MDP, which can be done with standard\nRL methods. These do not need to depend on access\nto the MDP. We simply choose value iteration because the goal of the\nexperimental section is not to evaluate different oracles but rather to evaluate\nour FairFictRL algorithm under the proposed assumptions.\n\n**Separator sets** The separator assumption directly affects our computational efficiency via the dependence of d in the bound given in Lemma 3.6.\nSince we are providing oracle-efficient algorithms, our primary computational-\ncomplexity analysis comes from the number of rounds our algorithm runs for\ngiven that we make O(T) oracle calls.", "claims_and_evidence": "The claims presented in the paper are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed method provides a reasonable solution to the problem.", "theoretical_claims": "I did not verify the correctness of the proofs.", "experimental_designs_or_analyses": "The numerical studies would benefit from further experimentation. Specifically, given the paper's focus on large state and constraint spaces, experiments should be added to examine such scenarios. Additionally, simulation studies should be conducted to verify the validity of the two FTPL algorithms.", "relation_to_broader_scientific_literature": "This work relates to prior research in fair RL and constrained RL. Rather than solving constrained RL problems by enumerating the constraints, the authors propose oracle-efficient algorithms.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths: \n       1. The paper studies a interest problem in fair RL with a large number of intersecting groups. \n       2. The authors provide oracle-efficient algorithms that can handle a large number of constraints efficiently, which is crucial in practical where the number of groups can be very large.\n       3.The graph-based simulation study is novel and easy to understand.\n\nWeakness:\n       1. The paper would benefit from additional numerical experimentation to further validate the proposed algorithms.", "other_comments_or_suggestions": "It would be beneficial for readers to have a clearer explanation of how the separator assumption impacts the computational efficiency of Algorithm 3.", "questions_for_authors": "1. Could you please clarify how Algorithm 4 is implemented in the numerical study? For instance, could you provide details on the implementation of the Best Response and Optimization oracles?\n\n2.  If the MDP is not accessible, do you have any insights on how your algorithms could be adapted?", "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": "", "extra_scores": {}}, {"review_id": "AImmJufvWK", "reviewer": "Reviewer_zwEM", "summary": "This paper investigates an interesting problem of intersectional fairness in RL. Unlike standard fairness approaches in RL, this work formulates fairness as a multi-objective optimization problem. Specifically, the goal is to optimize fairness and efficiency by maximizing the utility of the least advantaged group when demographic groups are available. The authors propose oracle-efficient algorithms for solving both tabular and large-scale MDPs. Theoretical results are provided, and experiments on a synthetic graph MDP validate the approach.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer zwEM,\n\nThank you for acknowledging the significant theoretical contribution of our work and the detailed feedback on our submission.\n\n**Individual Fairness** The notion of fairness we consider represents a middle ground between fully statistical notions of fairness and fully individual notions. By considering a sufficiently rich set of subgroups (rather than just the $d$ individual attributes or all individuals), we are able to provide algorithms that are tractable even for large state spaces while having meaningful guarantees for more fine-grained portions of the population. We believe this to be a valuable step towards methods that deal with the great variety of preferences and characteristics that individuals can exhibit, reflecting the vast diversity found within human sub-populations.\n\n**Pareto Optimal Fairness** This is a great point. You are correct in that the minimax optimization does not imply pareto optimality. However, what we can claim is that the minimax solution Pareto-dominates the solution that tries to equalize rewards across groups. We will clarify this in the text. We also do agree (as Figure 3 shows) that overall efficiency or optimality may be sacrificed when trying to optimize with fairness constraints in mind. This may unfortunately be unavoidable in many settings. \n\n**Empirical Scope** \nAs we highlight in Section 5, we completely agree that more realistic scenarios pose an interesting future direction. However, the current manuscript is largely a theoretical contribution and we believe that moving to more complex oracle settings will come with its own challenges and open questions. These include studying the effects of potentially sub-optimal oracles, which will likely warrant a different type of publication. Our experiments primarily aim to verify the effectiveness of our FairFictRL algorithm. This algorithm is easy to implement but it does not come with polynomial-time guarantees. Thus, our experiments validate that this algorithm is a feasible alternative in practice.\n\n**Baseline methods**\nWe appreciate the feedback on this. We view the main claim of the experimental section to be that our proposed FairFictRL algorithm is practical and we do not believe that the addition of baselines would strengthen this claim substantially.\n\n**Other Notions of Fairness**\nThis is a great point. We agree that other notions like leximin fairness are very interesting. In fact, an idea for future work might be to adapt our method to iteratively solve for leximin fairness as in [1]. However, even in this classification setting, leximin fairness is a very subtle and technically unstable concept. In addition, it can become computationally challenging when the number of groups is large as one may have to iterate over all groups. Instead, our method is able to handle a broad class of linear/convex fairness constraints or objectives and can be implemented efficiently. That being said, there are still many other interesting fairness notions that one could explore and we are excited about doing so in the future.\n\n**Group/Objective Scaling** Our proposed method scales with the log of the number of groups as can be seen in Lemma $3.3$ for tabular MDPs and Lemma $3.6$ for large state spaces. This is one of the key strengths of our contribution as it allows us to handle exponentially many groups.\n\n**Approximate Lin-OPT**\nOur optimization oracle assumption is mainly stating that we are able to do linear optimization efficiently in practice. \nFor this, interior point methods or barrier methods work well in the case of continuous spaces and in the case of conjunctions, integer linear programs and mixed integer programs work effectively. We are happy to extend the discussion on this by adding text akin to the previous sentences to the paper.\n\n**Large and continuous state-action spaces** \nOur methods already give provable guarantees for large spaces as we are able to make use of Algorithm $3$, which gives poly-time guarantees when we have group separator structure, or Algorithm $4$ for spaces without any group structure assumptions, but with an asymptotic guarantee. Here, one challenge would be to implement the policy oracle as mentioned before. One could hope to approximate solutions via standard deep RL techniques, which in many settings may be feasible. Yet, in various problems these algorithms may not return optimal policies in every execution [2]. As stated before we believe that moving to more complex oracle settings will come with its own challenges that lie beyond the scope of this manuscript.\n\n[1] Lexicographically Fair Learning: Algorithms and Generalization. Emily Diana et al. FORC 2021.\n\n[2] Deep Reinforcement Learning that Matters. Peter Henderson et al. AAAI 2018.", "claims_and_evidence": "Most of the paper claims are well-supported through theoretical results and empirical validation in synthetic graph MDP. However, the claim that the method achieves Pareto dominance in the synthetic graph MDP is questionable. Optimizing only for the minimum group utility ignores the needs of other groups, which may sacrifice overall efficiency and Pareto optimality.", "methods_and_evaluation_criteria": "While the paper addresses an important gap in fair RL, its practical applicability and scalability require further investigations. The experiments are limited to simple, small, tabular MDP, which may not generalize well to more complex RL settings.", "theoretical_claims": "The theoretical results, particularly the no-regret guarantees in Theorems 3.1 and 3.2, appear correct to me. The discussion in the main paper is clear, but I have not verified the full proofs in the appendix.", "experimental_designs_or_analyses": "The paper lacks fair RL baseline comparisons. While related works (e.g., Satija et al., 2023) are cited, they are not included as baselines in the experiments. The experimental evaluations are also limited. I believe testing the method on real-world environments such as college admissions, healthcare, or loan approval etc would significantly strengthen the paper.", "relation_to_broader_scientific_literature": "The paper makes a significant theoretical contribution by introducing intersectional fairness in RL, a relatively unexplored area. It adapts a technique from classification fairness (fictitious play) to sequential decision-making in RL and demonstrate its applicability to RL. While the theoretical insights are valuable, additional empirical validation would enhance its impact.", "essential_references_not_discussed": "The paper adequately discusses related work.", "other_strengths_and_weaknesses": "Strengths: \n\n* The paper introduces an important and novel problem of intersectional fairness in RL.\n* The theoretical results, particularly the no-regret guarantees, are well-establish and provide enough justification for the proposed method.\n* The paper proposed oracle-efficient algorithms that scale to both tabular and large-scale MDPs.\n* The approach adapts fictitious play from classification fairness to RL, demonstrating its applicability to sequential decision-making with large state spaces.\n\nWeaknesses: \n* The paper focuses on group fairness (specifically minimax) but does not consider individual fairness, which is often more practical in RL and real-world applications. Could the approach be extended to an individual fairness setting?\n* The minimax objective optimizes for the worst-off group but may sacrifice total utility and fail to ensure proportional or Pareto-optimal fairness.\n* The experimental evaluations are only in a synthetic MDP with only three groups, which does not reflect the complexity of real-world RL applications with a large number of demographic groups.\n* Moreover, the paper also lacks comparisons to fair RL methods.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "* Can the proposed method accommodate other fairness notions, such as leximin or proportional fairness, beyond minimax?\n* How does the proposed method scale with a higher number of objectives (e.g., 10)? In such cases, the number of intersectional groups could be 1024. Would the approach remain computationally tractable?\n* How would Lin-OPT/OPT be approximated in practice for large group sizes?\n* Are there relevant baseline methods that could be included for comparison, both in terms of fairness and efficiency?\n* How does the method generalize to real-world RL environments, where state/action spaces are large or continuous?", "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": "", "extra_scores": {}}, {"review_id": "A3LJNZWoli", "reviewer": "Reviewer_Gqfm", "summary": "The paper addresses intersectional fairness in reinforcement learning (RL) with exponentially many constraints arising from overlapping groups. The authors propose oracle-efficient algorithms for three settings: 1) tabular MDPs, 2) large MDPs with structured groups (via separator sets), and 3) general groups (using Fictitious Play). The key idea is to reduce the constrained RL problem to a minimax game between a learner (optimizing policies) and a regulator (enforcing group fairness), leveraging optimization oracles to handle large constraint sets. Theoretical guarantees include sublinear regret and convergence to approximate equilibria. Experiments on a preferential attachment graph MDP demonstrate that their method ensures minimum reward guarantees for all groups, balancing fairness and total reward.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Gqfm, \n\nThank you for your positive assessment of our work.\n\n**Empirical Scope** \nAs we highlight in Section 5 on Future Work, we completely agree that moving towards more realistic scenarios with these algorithms poses an interesting future direction for our work. However, the current manuscript is largely a theoretical contribution and we believe that moving to more complex oracle settings will come with its own challenges and open questions. These include studying the effects of potentially sub-optimal oracles in practice, which will likely warrant a different type of publication. Our experiments primarily aim to verify the effectiveness of our FairFictRL algorithm. This algorithm is easy to implement but it does not come with with polynomial-time guarantees. Thus, our experiments validate that this easy version of the algorithm might be a feasible alternative in practice.\n\n**Optimization Oracle Assumption** Our optimization oracle assumption is  mainly stating that we are able to do linear optimization efficiently in practice. Algorithms to achieve this exist in practice. For example, in the case of continuous space, interior point methods or barrier methods work well and in the case of conjunctions, integer linear programs and mixed integer programs, etc. work effectively in practice. For best response oracles one may hope to resort to deep reinforcement learning algorithms that may return policies close to optimal. We are happy to extend the discussion on this by adding text akin to the previous sentences to the paper.\n\n**Computational Complexity and Scaling** Since we provide oracle efficient algorithms, the run time (which we bound in our lemmas) is the core component of our computational complexity. Our algorithms mainly make O(T) oracle calls total, comprising the majority of the computation within each round; the only other computation is the sampling of noise vectors of size $O(d)$ or $O(|S|)$ at each round for the Follow the Perturbed Leader base algorithms. We will update our paper to include a statement highlighting the computational complexity of our algorithms. Lemma $3.3$ shows that the computational complexity of our algorithm for tabular MDPs scales logarithmically in $|\\mathcal{G}|$ and polynomially in $|S|$. Lemma $3.6$ shows that the computational complexity of our algorithm for continuous spaces and groups with separator structor scales with the size of the separator set $d$ and $\\ln(|\\mathcal{G}|)$. We believe that the impact of the number of groups on scaling to larger settings in practice would be negligible.\n\n**Baseline Methods** \nWe appreciate the question. We have not implemented any baselines in this setting and we are not aware of any baselines that would be suitable. We view the main claim of the experimental section as validating that our proposed FairFictRL algorithm works. We do not believe that the addition of baselines would strengthen this claim substantially.", "claims_and_evidence": "see the comments below", "methods_and_evaluation_criteria": "see the comments below", "theoretical_claims": "see the comments below", "experimental_designs_or_analyses": "see the comments below", "relation_to_broader_scientific_literature": "see the comments below", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n\n- Novel integration of optimization oracles for exponentially many constraints.\n\n- Theoretical contributions in oracle-efficient RL with intersectional fairness.\n\nWeaknesses:\n\n- Practical reliance on strong oracles (e.g., Lin-OPT) without discussing implementability.\n\n- Limited empirical scope (one synthetic MDP).\n\n- No discussion of computational complexity for large-scale deployments.", "other_comments_or_suggestions": "NA", "questions_for_authors": "- The theory supports exponential groups, but experiments use only three. How does the performance scale with $d$? A response showing linear/polynomial scaling would strengthen the claim.\n- How does the method compare to the baseline methods?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of intersectional fairness in RL with large state and constraint spaces. All the reviewers agreed that the theoretical contribution is novel and interesting, particularly the design of oracle-efficient algorithms with a large number of objectives. The paper might benefit from improved experimental and/or simulation frameworks. However, I believe that the contribution of the paper is mainly theoretical.
Decision: Accept (poster)