Fair Reinforcement Learning for Just AI
Authors: Ezgi Korkmaz
Venue: ICLR 2026 Poster (2026)
Keywords: reinforcement learning
fairness
fair reinforcement learning
democratic AI
AI alignment
pluralistic AI
ethical AI
responsible AI
computational social choice
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Currently the most powerful AI systems are aligned with human values via reinforcement learning from human feedback. Yet, reinforcement learning from human feedback models human preferences as noisy samples from a single linear ordering of shared human values and is unable to incorporate democratic AI alignment. In particular, the standard approach fails to represent and reflect diverse and conflicting perspectives of human values. Recent research introduced the theoretically principled notion of quantile fairness for training a reinforcement learning policy in the presence of multiple, competing sets of values from different agents. Quite recent work provided an algorithm for achieving quantile fairness in the tabular setting with explicit access to the full set of states, actions and transition probabilities in the MDP. These current methods require solving linear programs with the size of the constraint set given by the number of states and actions, making it unclear how to translate this into practical training algorithms that can only take actions and observe individual transitions from the current state. In this paper, we design and prove the correctness of a new algorithm for quantile fairness that makes efficient use of standard policy optimization as a black-box without any direct dependence on the number of states or actions. We further empirically validate our theoretical results and demonstrate that our algorithm achieves competitive fairness guarantees to the prior work, while being orders of magnitude more efficient with respect to computation and the required number of samples. Our algorithm opens a new avenue for provable fairness guarantees in any setting where standard policy optimization is possible.

Published as a conference paper at ICLR 2026
FAIR REINFORCEMENT LEARNING FOR JUST AI
Ezgi Korkmaz
ABSTRACT
Currently the most powerful AI systems aligned with human values via rein- forcement learning from human feedback. Yet, reinforcement learning from human feedback models human preferences as noisy samples from single linear ordering of shared human values and is unable to incorporate democratic Al alignment. In particular, the standard approach fails to represent and reflect diverse and conflict- ing perspectives of human values. Recent research introduced the theoretically principled notion of quantile fairness for training a reinforcement learning policy in the presence of multiple, competing sets of values from different agents. Quite recent work provided an algorithm for achieving quantile fairness in the tabular set- ting with explicit access to the full set of states, actions and transition probabilities in the MDP. These current methods require solving linear programs with the size of the constraint set given by the number of states and actions, making it unclear how to translate this into practical training algorithms that can only take actions and observe individual transitions from the current state. In this paper, we design and prove the correctness of a new algorithm for quantile fairness that makes efficient use of standard policy optimization dependence on the number of states or actions. We further empirically validate our theoretical results and demonstrate that algorithm achieves competitive fairness guarantees to the prior work, while being orders of magnitude more efficient with respect to computation and the required number of samples. Our algorithm opens a new avenue for provable fairness guarantees in any setting where standard policy optimization is possible.
black-box without any direct
INTRODUCTION
Reinforcement learning is at the core of the most powerful AI agents from scientific and mathematical reasoning to alignment with human values. Standard reinforcement learning reduces collective welfare to the maximization of a single scalar reward, assuming the existence of monolithic reward structure that is fundamentally incapable of representing a multiplicity of diverse and conflicting objectives. While modern AI alignment relies on optimizing toward consensus objective, such models fail to capture heterogeneous and competing human values. As a result there has been growing recognition of the need to develop pluralistic alignment methods (Conitzer et al. 2024 Sorensen et al. 2024), that align Al systems by taking into account the existence of multiple different reward or utility functions representing diverse human preferences. More generally, as powerful AI systems are further integrated into society, it is crucial to develop algorithms that aggregate diverse, competing objectives and human preferences in a rigorous way.
The idea of policy aggregation presents an initial theoretical approach to the problem of value alignment from the preferences of multiple agents (Alamdari al. 2024). The main approach is to apply rigorous methods from computational social choice theory to reinforcement learning with multiple diverse reward functions. However, computational social choice typically deals with preference rankings over discrete sets of alternatives, which cannot be applied to the continuous space of possible stochastic policies in reinforcement learning. The key insight of Alamdari et al. (2024) is that one can still compute continuous analogue of "ranking" for each agent, by assigning each policy a score of q if the agent receives a higher score than a q- yrfarction of all possible alternative policies. Critically, the score only depends the relative ranking of policies in the MDP, and thus provides a theoretically principled way to compare preferences across different agents that may have very different reward scales.

---

Published as a conference paper at ICLR 2026
The prior approach policy aggregation examines multiple approaches designing mechanisms that produce a fair policy given the notion of ranking described above. The authors show that there polynomial time algorithms to compute such fairness mechanisms, under the assumption that full, explicit deseription of the MDP is available. That is, the mechanism needs to have access to the table of transition probabilities in the MDP, and runs in time polynomial in the number of states and actions. Such methods are clearly intractable in the deep learning setting. To design algorithms that can be directly adapted to high dimensional environments, one typically assumes access to policy optimization oracle i.e. a subroutine that can optimize a policy in given MDP. Then, the goal becomes to design a provably oracle-efficiin
algorithm, meaning that the algorithm makes a polynomial number of calls to the policy optimization oracle, and has no other explicit access to the MDP question. Therefore, in this paper, we study the following question:
Are there provably oracle-efficient algorithms for fair reinforcement learning?
Our main results provide a positive answer to the above question.
Our Results. The notion of fairness that we consider is that of quantile faimess introduced by Babichenko al. (2024). This notion states that policy is q q-quantile fair, if it provides return in the top g-th quantile for each agent simultaneously. /Alamdari et al. (022)) provides a provably efficient algorithm achieve q-quantile fairness for the maximum possible value of q. when given explicit access to the full table of transition probabilities of the MDP. Our main result is an oracle-efficient algorithm for q-quantile fair reinforcement learning.
Theorem 1.1 (Informal). Given an MDP with agents, each with a different reward function, there an algorithm that makes ((n) calls to policy optimization oracle, and returns a q-quantile fair policy for the maximum possible value of q-
Technical Overview. To obtain this result, we first have to address a drawback of the initial definition of q-quantile fairness. The quantile is defined by comparing given policy's 's return to that of all possible alternative policies in the MDP. Algorithms for q q-quantile fairness thus naturally rely the ability to estimate quantiles. This is achieved by Alamdari et al. (2024) by sampling from a natural choice of uniform distribution on the set of all possible policies, conditioned on achieving value in the q-th quantile for given reward function. While such sampling can be done in polynomial time given explicit access to the full table of transition probabilities of the MDP, it is intractable in general. In particular, we show in Section 5 that there are MDPs where the fraction of policies with non-zero reward is exponentially small in the number of states of the MDP. This result implies that uniform sampling to estimate the quantile function has exponential sample complexity. To circumvent this issue, we instead consider q q-quantile faimess with respect to a different distribution on policies, induced by individually optimal policies for each agent. We then prove in Section 66. that, using (n) evaluations of policy optimization oracle, it is possible to accurately estimate the quantile function for this distribution.
Next, given the ability to estimate quantiles, the algorithm of Alamdari al. (2024) utilizes linear program defined over the states and actions of the MDP in order to compute a g-quantile fair policy, In Section 6.2] we instead design new algorithm that utilizes the multiplicative weights update method to achieve the same goal, while only requiring O n) calls to a policy evaluation oracle.
RELATED WORK
Most closely related to our work, the notion of fair policy aggregation was introduced by Alamdari et al. (2024), which gave provably efficient algorithms in the setting where the transition function of the MDP is given explicitly as a table of transition probabilities. [Babichenko et al. (2024) defined the notion of quantile fairness in computational social choice theory.
Due to the use of reinforcement learning from human feedback (Christiano et al. 2017 Bai et al.. 2022) for aligning the most advanced AI systems, notions of fairness in reinforcement learning with multiple reward functions are closely related to the application of social choice theory to Al alignment (Conitzer al.) 2024h. Recent research in this direction has discovered that standard RLHF based on the Bradley-Tenn Terry preference model (Bradley & Terry 1952) implicitly aggregates reward functions via the Borda count social-choice rule. Concurrent work has designed RLHF methods
2

---

Published as a conference paper at ICLR 2026
based computing von Neumann winner policy (Swamy et al. 2024 Wang al. 2023) which is equivalent to the rule from social choice theory known as maximal lotteries (Freund & Schapire 1997: Kreweras 1965).
Early work on nulti-objective reinforcement learning While (182)) developed algorithms that find pareto-efficient policies. In the decades since, there has been extensive work on fairness in multi- objective RL, with a significant focus on methods that combine multiple reward functions into a single reward, which is then optimized Reuel & Ma (024). The work of Zhang & Shah (2014) uses regularized maximin objective, which attempts to balance the sum of the rewards against the maximization of the minimum reward. Ogryczak et al. (2013) study the Gini social welfare as its reward combination method. More generally, there has been extensive work focused on various other methods that numerically combine multiple reward functions into a single one e.g. the Gini coefficient or the Nash welfare Ju et al. (2024); |Hayes et al. y: (Siddique et al. (2020). These methods inherently assume that rewards can be normalized and compared across agents. However, when inferring rewards from agent behavior, it is only possible to learn the rewards up to positive affine transformation. These reward-combining methods are not invariant to such transformations, while the policy- aggregation methods we study are.
An entirely different notion of fairness in reinforcement learning is studied in Jabbari et al. (2017) 77). where there is only single reward function, but the notion of fairness is not for the final policy, but for the learning algorithm itself. That is, in an online-learning setting, each action taken during learning may involve real-life consequences (e.g. hiring decision) and the goal is make fair decisions in each state, while still rapidly converging to an optimal policy.
3 PRELIMINARIES
For a natural number n, we use the notation [m] f1...... . n3. A halfspace is a subset of R" given by an affine inequality {i E R" w S b}. A polytope K. S R" is the intersection of finitely many halfspaces. The vertices of a polytope are the points which cannot be realized as the convex combination of two distinct points in the polytope. A simplex in R" is the convex hull of n + 1 linearly independent points, which form the vertices of the simplex. The centroid Ox. of a convex set KC is the uniform average over the points in the set
CK = Vol(K) Je x dr.
When K= con.(Ui,..., (h+1)) is simplex, the centroid takes a particularly simple form, given by the average of the vertices cx = xx+1 v,. An algorithm of Cohen & Hickey (1779) shows that any bounded polytope K. can be decomposed into union of simplices, such that any two simplices in the decomposition intersect in a face, and all vertices of the simplices are vertices of the original polytope. Furthermore, given any vertex i of the polytope K., the decomposition can be chosen such that 8 is a vertex of every simplex in the polytope.
Multi-objective Markoy Decision Process. The problem of producing single policy to best represent the preferences of multiple agents is modelled as a Multi-Objectinn Process (MOMDP). An MOMDP M is given by tuple AS,A, R1, ....... Ra, Pa, 7), where S is finite set of states, A is a finite set of actions, and P : S Sxxxxx A + A(S) is the probability transition function, which gives the probability P(s' s, a) of transitioning to state s' when action is taken in state 8. Each function R, : S x A + IR is the reward function corresponding to the i-th agent, Pa E ASS) is the initial state distribution, and 7 E [0, 1] is the discount factor. policy S > ((A) assigns a probability <a s) of taking action a E AA in state s E S. A policy i for an MOMDP M induces a probability distribution on sequences 80, ag, 81, aj, where so ~ po- a, T(- 5x), and 8c+1 P(- st, az). We will use the notation Pr, and Ex to respectively denote the probability and expectation with respect to this random sequence. The return J((x)) for agent i under policy is given by expected cumulative discounted reward with respect to R,,
Markov Decision
(x(=) = (1 - 7) >)
e Rs (8t, at)
where 80 ~ Po-
3

---

Published as a conference paper at ICLR 2026
We also consider the setting of average retur, where the return for agent i under policy x is given by the expected average reward
J. = lim T00
1
E
Σ
T
(st
Ra
an)
T
For e >> O, a policy π in an MOMDP is e- Pareto optimal for any other policy w' there exists at least one agent such that J((x') < J+(x) c..
mixed policy ş is a probability distribution over stochastic policies т. The return of mixed policy is given by (p) Ex (T))
The state-action value oceupancy measure. While the return agent i under policy æ a complicated function of n, it is linear function of the state- actton value occupancy measure d : x A R given by
d= a) (1 7)) Σ Pr = x)aa((a
In particular J.(T) = E.,o dr (s, (s, (d,, Rd)
Definition 3.1 (State-action value occupancy polytope). The state-action value occupancy polytope O for an MOMDP M is the set of all state-action value measures dz for some policy ı in the MOMDP M. This set is convex polytope given by the constraints
d dy 20, Σ de (s. = (1-,)) ty 3 P(( 18))
a
e'aa'
4 FAIR CEMENT LEARNING OVER CONVEX SETS OF ALTERNATIVES
In classical social choice theory, there is a finite set C' of m possible alternatives, and each agent i has strict ordering 0; : [m]] + C which means that for all j j' agent prefers (j( to (j').. However, these methods cannot be directly applied to the fair reinforcement learning problem, as there is in fact continuous set of stochastic policies π in an MOMDP.
The policy aggregation framework of Alamdari et al. 2024) is based on viewing the state-action value occupancy polytope as the set of alternatives from which the agents will choose policy. If (T) > J+(x') then agent i prefers policy π to policy x', and if (TTT) (TT')) then agent i is indifferent between the two policies. Each return Je therefore induces weak preference ordering on the policies π, and hence on the occupancy measures de E O. The overall goal is to compute a single policy in a way that is fair given the preference orderings of the n agents induced by the rewards RG The individual preference orderings are invariant to positive affine transformations of the rewards R, and thus any algorithm which only takes as input the preference orderings will always output a policy invariant to the same set of transformations. This fact further allows us assume that each individual reward function R; takes values in [0, 1). as this can always be achieved by a positive affine transformation of the original reward.
In order to design fair aggregation policies over the occupancy polytope, we will first need a natural generalization of the notion of ranking from the finite alternative case. In particular, note that an alternative e E C is ranked in the j-th position by agent if and only if uniform random c' E C weakly preferred definition
with probability j/ This observation leads naturally the following
Definition 4.1 (Expected return distribution). Let M be an MOMDP and D be a probability distribu- tion supported on the occupancy polytope O. For v E R the expected return distribution of agent i is given by the cumulative distribution function (t) Pra,~D [J,(T) S v].
In words, the CDF (v) encodes the total probability mass under D of policies that achieve returns at most
The notion fairness that we consider in this paper can now be defined in terms of the quantiles of the expected return distributions for each agent.
4

---

Published as a conference paper at ICLR 2026
Definition 4.2. Let D be probability distribution over the occupancy polytope O of an MOMDP
M. For q E [O, 1] a policy x is q q-quantile fair with respect to D in M if J((=) 2 (q) for all i E [n]. A policy æ is c-max-quantile fair with respect to D if ι is q-quantile fair with respect to D, and there does not exist any (q + e)-quantile fair policy.
Intuitively, q-quantile fairness means that the policy и is preferred to at least a a q-fraction of alternatives by every agent simultancously. Definition 4.2 is generalization of the definition of q-quantile fairness of Alamdari et al. (2024), which considers the special case where D is the uniform distribution over the occupancy polytope O, Our overall goal is design algorithms that achieve q-quantile fairness for as large a value of as possible, which we refer to as max-quantile fairness.
FAIRNESS FROM DISTRIBUTIONS OVER THE OCCUPANCY POLYTOPE
In this section we consider the question of how best choose the distribution D over the occupancy
polytope O that determines the notion of q-quantile fairness in Definition 12 We first show that
choosing the uniform distribution over O can lead computationally intractable estimation problems for estimating the quantile function Fi,D- We then show that choosing D to be uniform on the polytope of individually optimal occupancy measures can resolve this issue.
5.1 THE DRAWBACKS OF UNIFORM
In prior work D chosen be the uniform distribution over the entire scate-occupancy polytope Alamdari et al. (2024). However, we will argue that this choice of 'D may not be particularly meaningful the setting where non-trivial learning necessary to find a policy that achieves non- trivial returns for each agent. For example, in typical deep reinforcement learning problems, randomly selected policy will achieve some trivial level of rewards, but training can converge to a policy that does quite well and learns very complex behavior. Put another way, the number of samples required to randomly draw a policy that performs well in deep reinforcement learning is prohibitively large, and certainly much larger than the training budget of the typical RL algorithm.
In the scenario outlined above, less than a very small fraction of the occupancy polytope achieves non-trivial rewards, which implies that random sampling to estimate FeD will yield little to no information. We formalize this issue with the uniform distribution on O in the following theorem.
Theorem 5.1. There exists an MOMDP M with n 2 2 agents such that for every 2 /2[S|//
(1) There is pareto optimal, (1 (1- e)-quantile fair policy nO with respect to the uniform distribution on O, such that one agent receives a (1 - e) fraction of their maximum return, while all other agents receives less than a /ISI/(2n|S(+1) fraction of their maximum return. (2) There is a pareto optimal, (1 c)--uantill fair policy x² such that all agents receive a 1 fraction of their maximum return.
The proof of Theorem 5.1 appears in Section C To summarize, there is an MOMDP where q-quantile fairness with respect to the uniform measure on O only provides meaningful constraints on the returns when q exponentially close 1 as a function of the number of states. This is significant problem for current algorithms, which require estimating F. from random samples, and thus will have exponentially large sample complexity and runtime in order to achieve meaningful results using q-quantile fairness in the MOMDP of Theorem 5.1
further drawback of current methods is that, to even generate a single approximately uniform random sample from O requires running Markov chain for sampling from convex bodies. However, running such an algorithm requires an explicit description of the polytope O which is not in general available for many MDPs of interest. In particular, such algorithms cannot be implemented efficiently when given access to only a policy optimization oracle for O. Notably, the mixing time of such chains is polynomial in the dimension of the polytope, which for O is O([S) |A)). Such mixing time is completely impractical in settings with very large state spaces, where policy optimization may nevertheless be possible.
5

---

Published as a conference paper at ICLR 2026
5.2 CHOOSING D VIA INDIVIDUALLY OPTIMAL POLICIES
The difficulties described above in choosing D to be the uniform distribution on O arise both because the set of occupancy measures achieving non-trivial rewards can have very small volume, and the task of even drawing a single uniform sample from O may be intractable. We propose avoiding these issues by choosing D be the uniform distribution on a polytope derived from the occupancy measures of individually optimal policies. We will prove that this guarantees that the sample complexity necessary to estimate FiD for non-trivial fairness bounded, and that there an oracle-efficient sampling algorithm for DD. Our approach is to work in an embedding of a subset the occupaney polytope O defined by individually optimal policies. First, we define the reward embedding, which maps each occupancy measure d, to the n-dimensional vector given by the returns of each agent.
Definition 5.2 (Reward embedding). Given an MOMDP M, the reward embedding is the mapping : O - I2 given by ((dx) = (J.(T)....
The reward embedding captures the intuition that we only care about differences between two policies and r' with regards to their returns for each agent i. Next, the main intuition is that we want to focus on q-qunntile fairness over a subset of policies that achieves good rewards. A natural candidate is the polytope defined by the convex hull of individually optimal policies xद for each reward R, respectively.
Definition 5.3 (Optimal reward embedding polytope). Let गं be an optimal policy for agent i.e. o argmax, (T).. The optimal reward embedding polytope induced by -is-.- m the set K conv ((o(dn;) (emm)))))m)m)))))))mmm)))) R" i.c. the reward embeddings of occupancy measures in the convex hull of the individually optimal occupancy measures.
Finally, we choose to be the distribution on induced by the uniform distribution on IC*
Definition 5.4 (Optimal occupancy distribution). The optimal occupancy distribution is given by sampling uniform random point K,, and the sampling uniform random occupancy measure d, from the set & (z).
few remarks are in order. First, an optimal reward embedding polytope K* is invariant to positive affine transformations of the rewards, because the individually optimal policies nī are. Thus, letting D be the uniform distribution on XC* preserves this invariance, a key requirement for fair reinforcement learning. Second, in order to estimate the expected return distribution Ft,D it is not necessary to sample from 4 -=()).. By construction, for each agent i all the occupancy measures d, & -x)(x) give the same return T; = (dxx;; Thus, order to estimate FiD one needs only to sample uniformly from K
In general, it may be that for some individually optimal occupancy measure, the embedding (dd;)) ) is in the interior of the induced polytope XC*,, i.e. that & (cd;; a non-trivial convex combination of the embeddings of some other occupancy measures ((dx;): However, the next proposition shows that every optimal reward embedding polytope can be assumed to be induced by individually optimal occupancy measures dæ3 that correspond to vertices of KC*
......,,,,, T be a set of individually optimal policies, and K* the induced optimal reward embedding polytope. Then there is a set T/....,5?, ,,, of individually optimal policies such that every ((dz)) is vertex of K". Furthermore, this can be efficiently computed by evaluating Je J((zz) (ee))ft for all i.j.
Proposition 5.5. Let Lei mi....,
The proof of Proposition 5.5 appears in Section A We next show that choosing D to be uniform K ensures the existence a q-quantile fair policy π achieving non con-trivial returns for each agent.
Theorem 5.6. Let .i...., ,, be individually optimal policies. For every MOMDP M there is a policy N that is 1 --quantile fair with respect the uniform distribution on KC Furthermore, under every agent receives least 1 --fraction of their maximum possible return.
The proof of Theorem 5.6 appears in Section
B

---

Published as a conference paper at ICLR 2026
6 AN REINFORCEMENT LEARNING
ALGORITHM FOR MAX-QUANTIN FAIR
In this section we design an oracle-efficient algorithm for computing a max mux-quantile fair policy with respect to the optimal occupancy polytope, based on the multiplicative weights update method. In particular, our algorithm solves series of standard RL policy optimization problems, where the single reward is given by weighted combination I = wi R4 ... Wn Rn at each step.
6.1 SAMPLING AND ESTIMATING QUANTILES
As a first step, we need an algorithm for estimating the quantile function P.D when D is the optimal occupancy distribution. Such algorithm follows directly from efficient algorithm for sampling from the optimal occupancy distribution, which we introduce this subsection. The main high-level point is that computing returns (x,) for all i and j gives explicit description of K. as a polytope in n dimensions, and so standard methods for sampling from a polytope apply. While in general this requires Markov chain Monte Carlo, we emphasize that in the case where the vectors 2 (dx;) are linearly independent there is fast, exact sampling method. This case is of particular interest, because for complex practical MDPs with noisy reward estimates, the vectors ((d,;) (J1 .
will be linearly independent with high probability. See Proposition E in Section E for a formal statement and proof. This is especially likely to be the case when reward functions themselves are noisy estimates learned from preferences of the individual agents, as is standard practice in RLHF.
Algorithm Sampling from the optimal occupancy distribution
1: Input: MOMDP M, desired number of samples S
2: Compute the n individually optimal policies मं E argmax, (T) for i [n]
3: If for any policy ((dx;) is not a vertex of K use the method of Proposition 5.5 to replace it with an individually optimal policy that is a vertex.
4: for = to S do
5: if The vectors ((dx;) are linearly independent. then
6: Sample n independent Exp(1) random variables aj for j E [n].
7:
Let B3
2;
Σis ag
8:
Let 0/,. - (T5)( for E [n]]
9:
else
10:
Use the hit-and-run Markov chain to sample an approximately uniform point o K
11:
Let 03,a 2%
12:
end if
13:
end for
Return: The vs. which are samples for each of agents for the value (T( for D.
Algorithm T gives the algorithm for sampling from K When the vectors & (d=rr are linearly independent, KC* is a simplex with n vertices. The uniform distribution on the simplex well-known be given by picking n independent Exp(1) random variables, normalizing them sum one, and selecting the point given by the resulting convex combination of the vertices Devroye (006)). When KC* is a general polytope, the hit-and-rum Markov Chain obtains an approximately uniform sample in ((n²) iterations (Lovász] 1999), , each of which requires solving ((1) n x n linear programs to determine membership of point in IC* (see Section F). We give these results formally in Theorems 6.1 and 6.2 6.22bo... below.
Theorem 6.1. the vectors {d(d;;))= are linearly independent then for each the set {Vi 18 returned by Algorithm 7 is an exactly uniform random sample from Jı(TT) where n ~ D. Further, the algorithm requires n calls to a policy optimization oracle, and otherwise runs in O(ni²) ) time.
s=1
Theorem 6.2. If the vectors {d(d=;)) )== are not linearly independent, then for each i the set ( 15 returned by Algorithm 7 is an approximately random sample from Jı(x) with a D. In this case the algorithm requires n calls to a policy optimization oracle, and requires Ö(n²) solves of an explicit linear program with variables and constraints.
7

---

Published as a conference paper at ICLR 2026
Algorithm 2 Optimal occupancy quantile estimation
1: Input: MOMDP M. q E [0, 1J, target accuracy
2: Draw O ((g(1 - +)/e)² samples Vi,s using Algorithm
3: For each sort Ui...
4: Return: of = [4. an estimate of (1) for each i [n].
Algorithm 3 Oracle-efficient q-quantile fairness
1: Input: MOMDP M, q |0, 1J, target welfare U, target accuracy
2: Set : = for E [n.] u O.
3: Set T (n n= 1)/e², and 1 - Vlog(n 1)/T.
4: Use Algorithm
2 get an estimate 2s of (9) for [n].
5: for 1 7 do
6: Compute Te E argmax, E,(,, + (T))
7: Update w. wf exp(m((; J((T)))).
8: Update 4 uº exp (1 (U E EL (:()))
9: end for
10: Let j be the mixed policy given by the uniform distribution over He for E [7]]
11: Return: If is (q qquantile fair, and achieves total welfare U return μ4, otherwise return "infeasible".
Finally, given the ability to sample from D, we can use standard quantile estimators to compute F from samples. Algorithm gives pseudocode for quantile estimation. The most important point is the sample complexity of Olg(1 - -2) required to estimate (g) within accuracy c.
6.2 COMPUTING A MAX-QUANTILE FAIR POLICY
In this section utilize the ability to efficiently estimate F.D to design oracle-efficient algorithms achieving max quantile fairness. Algorithm takes as input values g. e [0. 1] and returns (g (Q-e)-ae -quunnttee fair mixed policy achieving total welfare at least U -e. e. The algorithm an instance of the multiplicative weights update (MWU) method from online convex optimization. Algorithm then uses Algorithm as subroutine to binary search for a welfare maximizing c-max-quantile fair mixed policy.
Algorithm 4 Oracle-efficiem max-quantile fairness
1: Input: MOMDP M, target accuracy e
2: Binary search over E [0, 1] for the maximum value g" such that running Algorithm 3 with
( q and U = does not return "infeasible".
3: Binary search over U e [0, 1] for the maximum value U* such that running Algorithm 3 with
q = 9" and U U* does not return "infcasible",
4: Return the mixed policy μ output by Algorithm when U U and q = q²
Theorem 6.3. The mixed policy μ. returned by Algorithm (g quqantiee fair, and achieves total welfare at least U
The proof appears in Section
EXPERIMENTS
In this section we run experiments comparing our oracle-efficient max-quantile fairness algorithm to the original max-quantile fairness algorithm of Alamdari et al. (2024). Because consider different distributions on policies for our definition of max max-quantile fairness, the policies output by the two algorithms will in general be different. The environment is the same factory monitoring MDP used by Alamdari et al. (202)) (available under the MIT license), which is itself a modification of an environment introduced by A'mour al. 2020 The setup involves monitoring 5 warehouses
8

---

Published as a conference paper at ICLR 2026
Oraclc-Efficient Max- Mux--uuattile
Original Max- Max--Qunttlee
Egalitarian
Utilitarian
Nash Welfare
0.701 + 0.015
0.654 + 0.010
0.4655 + 0.0581
0.5736 + 0.0471
Gini Coefficient
0.087 0.007
0.066 + 0.003
0.2126 + 0.0209
0.2020 + 0.0182
0.883 + 0.055
0.999 + 0.001
N/A
N/A
Table I: Nash welfare, Gini coefficient, for the oracle-efficient max-quantile fairness, original max- quantile fairness, egalitarian and utilitarian algorithms. Max-quantile q' reported for the two max-quantile fairness algorithms.
to prevent incidents, where only one warehouse can be monitored in each time-step, and each of n = 10 agents incurs different costs for an incident each warehouse. Warehouses can be one of three states normal, risky, or incident. Every unmonitored warehouse has some probability of transferring from normal to risky, and from risky to incident. Monitoring a risky warehouse resets it to the normal state. At the beginning of each experiment, the transition probabilities and the agent costs are randomly sampled from the same set of values as used in Alamdari et al. (2024). The wallclock time to achieve max max-quantis quanttie fairness via our method in this setting is approximately 10 minutes on laptop with an Intel core ultra 7 and 32 GB of RAM. This contrasts with the reported runtime of approximately hours utilizing 20 parallel threads on an AMD EPYC 7502 32-Core Processor with 258GiB system memory reported by the prior method of Alamdari et al. (2024).
Figure shows the sorted returns for each of the agents under the two different algorithms. All agents, except the lowest return one, receive larger rewards under our oracle-efficient method. This is consistent with the intuition that choosing D to be induced by the uniform distribution on KC* will tend to lead the algorithm to consider higher-return policies for each agent.
In Table we report the Nash welfare, Gini coef- ficient, and the maximum quantile q achieved for the normalized agent returns for both our oracle-efficient algorithm and the original max- quantile fair algorithm. As baseline point of comparison we also include the classic utilitar- ian algorithm (which maximizes the sum of the rewards), and the egalitarian algorithm (which
Agent Returns for Max-Quantile Faimess
Cracle- Crade-Effileet Efficeet tuniterm 4*) Original luniform di
Sreetton mummum
maximizes the minimum reward). Both vari- ants of max-quantile fairness outperform these baseline methods. Additionally, the results q" confirm that the issue identified in Theo- rem 5.I is present in this environment. Even with 3- 10th randomly sampled policies, we get q" =1- -1-6 e for 0.001, indicating that nearly all of the policies sampled uniformly from O achieve low returns. In contrast, the maximum quantile found by our oracle-efficient algorithm q" = 0.883, indicating that under the uniform distribution on K one cannot do better than achieving returns in the top 12% for each agent simultaneously. These results indicate that the cample-complexity for estimating P.D. via sampling from KC* is reasonable, while that of sampling from O grows rapidly.
DA
0.-
0.0
Figure 1: Sorted and normalized returns for each of 10 agents monitoring 5 factories.
8 DISCUSSION AND FUTURE WORK
We have designed an oracle-efficien algorithm for max-quantile fair reinforcement learning. That is, in any situation where standard single-reward reinforcement learning is possible, our algorithm provides a cheoretically-fonddee of multiple agents in a provably fair way. One main limitation of our work, is the question of how to obtain the individual reward functions in practical settings, especially for RLHE, Typical RLHF treats human preference rankings from multiple raters as noisy estimates of single ground-truth reward, and it is an open question how best to learn estimates for multiple different rewards in a representative way. Our algorithm be directly plugged into RLHF pipeline where multiple reward models are available. One can simply use any existing policy optimization algorithm in place of the oracle from algorithms.
method for producing a single policy that aggregates the preferences

---

Published as a conference paper at ICLR 2026
REFERENCES
Parand A. Alamdari, Soroush Ebadian, and Ariel D. Procaccia. Policy aggregation. In The Thirty- eighth Annual Conference Neural Information Processing Systems, 2024. URL https
Soopeneeview.ne//ooe -bbbuuiidyyyiUUIxt...
Yakov Babichenko, Michal Feldman, Ron Holzman, and Vishnu V Narayan. Fair division via quantile shares. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, pp.
1246- 2024.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint MrXiv:2204.0586. 2022.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Jacques Cohen and Timothy Hickey. Two algorithms for determining volumes of convex polyhedra. Journal of the ACM (JACM), 26(3):401-414, 1979.
Vincent Conitzer, Rachel Freedman, Jobst Heitzig, Wesley H Holliday, Bob Jacobs, Nathan Lambert, Milan Mossé, Eric Pacuit, Stuart Russell, Hailey Schoelkopf, al. Position: social choice should guide alignment dealing with diverse human feedback. In Proceedings of the 41st International Conference Machine Learning, pp. 93469936639999 9946,,360,00 2024.
Alexander D' Amour, Hansa Srinivasan, James Atwood, Pallavi Baljekar, David Sculley, and Yoni Halpern. Fairness is not static: deeper understanding of long term fairness via simulation studies. In Proceedings of the 2020 Conference Fairness, Accountability, and Transparency, pp. 525-534, 2020.
Lue Devroye. Nonuniform random variate generation. Handbooks operations research and management science, 13:83-121, 2006.
Yoav Freund and Robert E Schapire. A decision-theorede generalization of on-line learning and an application to boosting. Journal of computer and system sciences,
1997.
Conor Hayes, Roxana Rādulescu, Eugenio Bargiacchi, Johan Källström, Matthew Macfarlane, Mathieu Reymond, Timothy Verstraeten, Luisa M Zintgraf, Richard Dazeley, Fredrik Heintz, et al. practical guide multi-objective reinforcement learning and planning. Autonomous Agents and Mulli-Ageni Systems, 36(1) (126, 2022.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4):157-325, 2016.
Shahin Jabbari, Matthew Joseph. Michael Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in reinforcement learning. In International conference on machine learning, pp. 1617-1626. PMLR, 2017.
Peizhong Ju, Amob Ghosh, and Ness Shroff. Achieving faimess in multi-agent mdp using re- inforcement learning. In The Twelfth International Conference on Learning Representations, 2024.
Germain Kreweras. Aggregation of preference orderings. In Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saint--ere France (1-27 July 1960) and of Gösing, Austria (3-27 July 1962), pp- pages 73-79, 1965.
László Lovász. Hit-and-run mixes fast. Mathematical programming. 86:443-461. 1999.
Wlodzimierz Ogryczak, Patrice Pemny and Paul Weng. A compromise programming approach to multiobjective markov decision processes. International Journal of Information Technology & Decision Making, 12005):021110033 2013.
10

---

Published as a conference paper at ICLR 2026
Anka Reuel and Devin Ma. Fairness in reinforcement learning: A survey. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, volume 7, pp. 1218-1230, 2024.
Mark Rudelson and Roman Vershynin. The littlewood-offrrd problem and invertibility of random matrices. Advances in Mathematics, 218(2):600-633, 2008.
Umer Siddique, Paul Weng, and Matthieu Zimmer. Learning fair policies in multi-objeccive (deep) reinforcement learning with average and discounted rewards. In International Conference on Machine Learning, pp. 8905-8915, PMLR, 2020.
Taylor Sorensen, Jared Moore, Jillian Fisher, Mitchell Gordon, Niloofar Mireshghallah, Christo- pher Michael Rytting, Andre Ye, Liwei Jiang. Ximing Lu, Nouha Dziri, al. A roadmap to pluralistic alignment. arXiv preprint arXi::4402.05070, 2024.
Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. A mini- maximalist approach reinforcement learning from human feedback. In Proceedings of the 41st International Conference on Machine Learning, pp. 47345-47377, 2024.
Yuanhao Wang, Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rI? theoretical perspective. Advances Neural Information Processing Systems, 36:76006-76032, 2023.
DJ While. Multi-objective infinite-horizon discounted markov decision processes. Journal of mathematical analysis and applications, 89(2):639-644 1982.
Chongjie Zhang and Julie A Shah. Fairness in multi-agent sequential decision-making, Advances in Neural Information Processing Systems, 27, 2014.

---

Published as a conference paper at ICLR 2026
A PROOF OF PROPOSITION 5.5
In this section we prove Proposition 5.5
Proof of Proposition 5.5 Because K conv (+(dx))) every vertex of KC given by ((dx;) ) for one of the individually optimal policies n.- Let be the smallest index such that ((dx;) is in the relative interior of KC*, and let Eits (x;((d;)) = (dd;;) be a convex combination the vertices of K that yields (.dz)). Thus, by the definition of 4
J5(m3)
Σ (m)) (g
By optimality of n with respect Jj. ()( S (T3) for all i. Therefore, for every with o; it must be that (=Ş) = (Tz). Choose any such with a, 2 and let TTJ n/. and म = कद for i < j. Now inductively applying the same argument yields the desired set of optimal policies n/. where each ((d+)) is vertex of KC*
Testing whether a point a witnessing this can both be solved via linear program with variables a and x constraint matrix derived from the n n matrix of returns J. (T77) (see Section F.. Hence, the overall algorithm runs in time polynomial in given access to an oracle for finding the optimal policies n..
the relative interior of a polytope, and computing the convex combination
B PROOF OF THEOREM 5.6
In this section we prove Theorem 5.6 which shows that g-quantile fairness over the optimal oceu- pancy polytope enjoys improved fairness guarantees when compared to the entire state-action value occupancy polytope.
Proof of Theorem 5.6 The proof of Theorem Alamdari et al. (2024) shows via Grünbaums's inequality that any policy ı corresponding to the centroid of a polytope K. achieves -quantile fairness with respect to the uniform distribution on IC
We now turn to the question of the return of each agent. By Proposition 5.3 the individually optimal policies -i.... n. can assumed to be vertices of K [Chhen Hickey (1979) proves that any polytope can be decomposed into union of simplices with disjoint interiors such that the vertices of each simplex in the decomposition are vertices of the polytope. Furthermore, the decomposition can be chosen such that for any single vertex of the polytope, every simplex in the decomposition has as a vertex.
Thus, for any individually optimal policy पं. the polytope K can be decomposed into set of simplices Ag. each of which has & (dz;) as a vertex. Let Us,k denote the i-th vertex of the simplex A₁ in the decomposition. The centroid cx- of the polytope IC* can therefore be written
CX
Vol(K(*
1
/
rd Σ
Vol(K+)) /
x dx
Vol(Ae) Vol(AC*
1
ViKk-
1=1
The final equality the fact that the centroid of a simplex is the average of its vertices. Since & (dx;;) appears as a vertex each Ag, we conclude the centroid of KC* can be written as a convex combination of the vertices, such that ((d;;) receives weight at least 1 Recall that by positive affine invariance we may assume that all returns are non-negative. Thus, the policy æ induced by any occupancy measure d E x (cx()x)) achieves return at least ! [mT)).
C PROOF OF THEOREM 5.1
In this section we prove Theorem 5.1 demonstrating the sample-complexity issues with the original approach estimating the expected return distribution.
12

---

Published as a conference paper at ICLR 2026
Define .M as follows. There n agents identified with [n]. The state-space space a chain $1,.... Sm m states, and the action space has size n, denoted {a1,..., an }. For each state 8, with j S 1, each action a, with 2 2 transitions to state 81, and action di transitions to state 8j+1, both yielding zero rewards for all agents. For state 8m all actions transition to state 81 and action d, yields reward for agent and reward 0 for all other agents. The initial state distribution Po puts all probability mass on $1.
Proof of Theorem 5.7
uniformly randomly chosen occupancy measure dæ induces policy that takes action dz in state 8; with probability Pij. where for each i E [m]] the vector (pil, ........ Pin)) is an independent, uniformly random sample from the standard simplex with n vertices. Thus, Elpal 1/n for all i, because the centroid of the standard simplex on vertices is (1/n..... 1/n). When starting from state 81, the policy æ must select action aj m times in a row to reach state 8m- Any other choice transitions the agent back to state Thus for any action aj, we have (=(mm; (z) S I P:1- n n- Let 2 V2mm/nn" By Markov's inequality Pr[d (sm: az) 2 (1/mmm . n=) S E. But state 5m is the only state where any agent can receive rewards, and the reward received is at most 1. Thus, (I)(~ 2 v1/(2mn - n²")] S c for each agent i. Hence, the quantile function satisfies (1 - c) /1/(2mn n²m).
Hence (sm an)] I E[pa]
Next, consider the policy x'' that takes action 1 in every state 8, with m, and in state 8m takes action 1 with probability (1- -e) e) and uniform random action in {a2..... an otherwise. The policy n' is pareto optimal, because visits Sm the only state with any rewards with maximum possible probability, and hence any deviation which increases one player's 's reward will decrease another's. Further, N' is (1 qu-uutiee fair because every agent receives return least c/(m(n 1)) > /2/(mn- n²) 2 (1-
Finally, the policy x² that takes action 1 in every state s, with S m 1 and a uniformly random 1 E-fraction of the maximum
action in state 8m receives average return 1 अ for all agents i, which is a
possible average return of (S] for each agent.
D PROOF OF THEOREM 6.3
In this section we provide the proof of Theorem 6.3 regarding the correctness of Algorithm
We first show that our algorithm is an instance of the multiplicative weights update (MWU) method, and the proof then follows from standard regret bounds for MWU (Freund & values w u' are the weights. The losses in each step
Proof of Theorem 6.3
Schapire 1997 Hazan et al. 2016). The corresponding to the w/ weights, and c'(xz)) = Σm= J((T)) - U
are given 4 (T) = )e(
corresponding to the u' weight. Let W = u² + Ex= wof be the total weight in step l. For any policy æ,, the expected loss in step given by the weights then
L(w", u',
u ('
Σ (of(((m)
Wi
(wt + +
Wi (u'U + w(w))
W
The second term above has no dependence and the scaling factor of के also does not affect the maximum over ग,, hence
argmax L(w", u², TT argmax
I(uf + u (')).(TT).
(1)
IT
Let us assume that there exists a policy "t that is q-quantile fair, and achieves total welfare U. Otherwise, Algorithm will necessarily output "infeasible". The regret bounds for MWU imply that for any set of weights w², u"
T
1 T T
L(w" ,,a')) log(n + 1)
Σ L(w u. ,
Σ t=l
(2)
T
/T
13

---

Published as a conference paper at ICLR 2026
In each step of Algorithm
B
i implies that ne E argmax, L(w", u., x). Thus,
Σ T
1
I(w",
1 u², x 2 T
L(w u² x²) 2
t=1
where the final inequality follows from the fact that n² is both q-quantile fair, and achieves total welfare U. i.e. (((x)) 2 0 and c¹ c'(x*) 2 O. Hence, the regret bound ( implies that
T E
L(w" 2r x²)x)) log(n + +1 VT
T
for any choice of weights w', ,u= For each i, specializing the above inequality to the n cases where
" 1, w3 = O for * i, and = 0, implies that the mixed policy satisfies Ji(u) 2 1/ C.
Specializing to the case wi = 0 for all i, and u = 1, implies that μ satisfies J. 2 U as desired.
E LINEAR-INDEPENDENCE FOR NOISY ESTIMATES OF { (o(dx;))
In this section we provide a formal statement and proof showing that rewards estimated by sampling multiple runs of a policy in stochastic MDP will lead to linear independence of the (dd=;) ) with high probability. This is of significant practical relevance, because computing the expected rewards of standard deep reinforcement learning policies is essentially always done by computing the empirical mean of multiple sampled evaluation runs, which have non-trivial variance.
Proposition E.1. Assume that each entry of the vectors ($(dz;) (i is estimated by taking multiple independent samples of the stochastic reward J,(m)), and these stochastic reward estimates are continuous random variables with non-zero variance oz,j. Then this estimate of { > converges to a distribution on vectors that are linearly independent with probability 1.
Proof. Note that each coordinate of each & vector an independent stochastic estimate of the returns of policy xē under reward function Jj computed by averaging the rewards over multiple independent runs. Each such estimate converges to a Gaussian distribution with variance oi.j > 0 by the central limit theorem. Thus, the matrix obtained by stacking all the O vectors together is equal to matrix of the true mean returns, plus independent Gaussian distributed noise with non-zero variance added each coordinate. Such a matrix is full rank with probability (see for example Rudelson ( & Vershynin (2008)), ) and hence the & vector estimates converge to distribution that is linearly independent with probability 1.
F ADDITIONAL DETAILS ON LINEAR PROGRAMS FOR MEMBERSHIP IN KC*
Both Proposition 5.5 and Algorithm D rely on solving an n x n linear program for the problems related to membership of a point in R.F. In this section we provide the linear programs in question. First, for Proposition
5.5) it is necessary determine if a point ((d=;) is convex combination of the other vertices of XC* and if so to determine the weights ay of the convex combination. This problem can be expressed via the following system of linear inequalities in the variables aj for j [n]]
Σ (d,)(d);))))))))))))))()))))(( (dd;;)
jti
Σ aa==1 =1
aj
0
Vj E [n]
which is the problem of finding feasible solution to X linear program.
Similarly, the hit-and-rum and-run walk used for sampling in Algorithm Tin the case that 1C* is not a simplex relies the ability test whether given point E K. This problem can be solved by the following
14

---

Published as a conference paper at ICLR 2026
n. linear program:
Σ
a [j0(dz;)= = v
j=1
9j =1
/=1
aj 20 0
Vj E [n].
15


Reviews:
[{"review_id": "2kqKHKWpy5", "reviewer": "Reviewer_tKms", "summary": "This paper studies the problem of fair policy aggregation, using a quantile notion of fairness. The goal is to find a policy that each agent prefers to a k fraction of alternatives, for the largest feasible k. They build on prior work that addresses this problem for a broader notion of alternatives (the uniform distribution over all policies), but under a much stronger assumption of access to the MDP (known transition dynamics). They give an oracle-efficient algorithm for learning a quantile fair policy with respect to the occupancy measure polytope induced by the optimal policy for each agent, without any assumption of known dynamics or generative model. \n\nThey further show that redefining the set of alternative policies from prior work is necessary in their setting, as efficient algorithms to even estimate quantiles without knowledge of transition dynamics cannot exist if the uniform distribution over all policies is taken as the reference class.", "questions": "Please see weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper gives efficient, provable algorithms for a reasonable fairness notion for preference aggregation. They cleverly set up the comparison class of policies such that their sampling algorithm for estimating quantiles is efficient and their main algorithm for aggregation is a simple application of multiplicative weights.", "weaknesses": "The paper claims only $O(n)$ calls to a policy optimizer are required, but it appears that Algorithm 3 makes $T = \\log(n+1)/\\varepsilon^2$ calls to an optimization oracle, in addition to the $O(n)$ calls required to define the polytope.   \n\n“The key insight of Alamdari et al. (2024) is that one can still compute a continuous analogue of a “ranking” for each agent, by assigning to each policy a score of q if the agent receives a higher score than an q-fraction of all possible alternative policies” -- I think the second \"score\" here should be \"reward\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "Ckbn4SbQ2L", "reviewer": "Reviewer_maiB", "summary": "This paper studies fairness in reinforcement learning with large state-action spaces. More specifically, the work studies a setting with access to a policy optimization oracle and the goal is to obtain q-quantile fairness. The paper provides an algorithm based one multiplicative weights as well as theoretical fairness guarantees. Finally, the algorithm is experimentall evaluated on a tabular MDP.", "questions": "Q1: Can you elaborate on how your work differs from [1].\n\nQ2: Maybe I'm missing something but what happens when 2 agent reward functions oppose each other and there exists no fair allocation?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Clarity**\n* The paper is well written and easy to follow.\n\n**Motivation**\n* The paper tackles an interesting, understudied problem that is of relevance in the time of finetuning LLMs using RL.\n\n**Related Work**\n* The treatment of related work is decent.\n\n**Novelty**\n* I am largely not aware of other work tackling similar problems and I believe that the work is sufficiently novel. One paper that should be highlighted is [1] which seems quite related. They also use an oracle notion in a multi-objective setting to obtain fairness guarantees. The fairness guarantees are slightly different but the manuscript might benefit from differentiating itself from this work (see Q1).\n\n**Theoretical results**\n* I mostly followed the arguments in the paper but did not verify the details of the proofs and parameter settings in the Appendix. However, using online learning techniques in combination with binary search to solve constraint optimization problems in large spaces is quite common and the algorithms as well as corresponding results seem sound.\n\n**Experimental results**\n* The experiments provide some nice intuition into the functionality of the algorithm.\n\n[1] Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces. Eaton et al. ICML 2025.", "weaknesses": "**Clarity**\n* One confusing point to me was the terminology “policy aggregation”. In the introduction, the text refers to rewards that belong to policies but a reward is always defined with respect to an MDP and it refers to optimal policies for each agent. In hindsight, it is obvious what this is referring to but not on a first read of the intro. One needs to read section 3 to understand this part. I think it might make sense to clarify the relationship between agents and rewards in the intro when stating the model.\n\n**Empirical Design and Evidence**\n* The fundamental motivation of the paper is to design algorithms that work in high dimensional settings with neural networks but the experiments are conducted solely on what seems to be a tabular MDP. The manuscript could be strengthened by experiments actually using the complex function approximation objects that the algorithm is designed for.\n\nOverall, the pros outweigh the cons in my eyes and I even though I would like to see some deep learning experiments, prior work seems to have accepted without them (e.g. [1]). I can't find much else to complain about and think this is a solid paper. Thus, I'm willing to err on the side of optimism an recommend acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "PYfHxJmPdF", "reviewer": "Reviewer_Mguy", "summary": "The paper studies a fair multi-objective Markov decision process problem that aims to compute a policy that is fair with respect to the objectives. The paper first introduces a q-quantile fairness notion based on the convex hull of optimal policies for individual objectives, and the authors argue that this notion is more appropriate than the one introduced in previous work. The paper then shows that this new notion makes it possible to find fair policies efficiently using a black-box policy optimization algorithm as its subroutine. Experiments were conducted to evaluate the fairness guarantee the algorithm yields.", "questions": "- Can you respond to the first three weaknesses I mentions?\n\n- In Defintion 3.1, should $\\rho_0(s,a)$ be $\\rho(s)$?\n\n- Line 6 of Algorithm 3, should it be $(\\sum_i w_i^t + u^t) J_i(\\pi)$?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is clearly and nicely written. The results appear solid, and the exposition maintains a good balance between accessibility and mathematical rigor.", "weaknesses": "1. I don't see a strong connection between the model in the paper and RLHF. Most RLHF models are not built on MDPs. \n\n2. Some of the problem setups feel somewhat artificial, potentially constructed for the sake of deriving results. For example, instead of looking at the quantile, why not simply look for solutions that yield x fraction of the maximum attainable value for every agent, and then maximize x? This seems much more straightforward and would simplify much of the analysis, and I don't see any obvious reason why this measure would be less desirable than the one proposed in the paper. In fact, the statement in Theorem 5.1 seems to suggest that we should care more about the fraction of each agent's maximum return.\n\n3. In the paragraph at the top of Page 6, it is stated that the main drawback of existing methods is that they cannot handle large state spaces, whereas policy optimization is still feasible for large state spaces. I am not sure this is a valid argument. While it is true that there are policy optimization algorithms applicable to large state spaces, they generally do not yield exact optimal solutions. This seems critical as the main algorithm in this paper relies on a policy optimization algorithm that computes exact optimal solutions as its subroutine.\n\n4. The sampling methods in Section 6.1 largely follow trivially from existing results.\n\n5. Though the paper is overall clear, I find that it would still benefit from additional explanations and intuition in certain parts. Such as the 1/e-quantile fair guarantee in Proposition 5.5, and MWU-based algorithm (Algorithm 3).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "qIxSKaSkIL", "reviewer": "Reviewer_whs3", "summary": "The paper studies quantile fairness in the context of reinforcement learning. The authors show intrinsic scalability limitations of previous work and propose a slightly different setting where the quantile fairness is measured wrt to the set of optimal policies for different agents rather than all possible policies. This alternative formulation allows for efficient algorithms to identify max-quantile fair policies. The proposed algorithm is evaluated in a synthetic factory monitoring environment and its effectiveness is assess across several different metrics (e.g., Nash welfare, Gini coefficient).", "questions": "* In the formulation of Sect.3 you assume a finite MDP, but later you only assume access to a policy optimization \"oracle\". Could you please clarify where the finite MDP assumption is needed in the algorithm and theoretical results?\n* In L448 you make a high-level comparison on the running time of your algorithm and the previous one. Would it be possible to have a more direct comparison on the same hardware?\n* When I first read the high-level description of the proposed formulation I was concerned that restricting the focus on agent-optimal policies would impose a too serious restriction. For instance, we can imagine problems where a fair policy should trade-off between the rewards of different agents resulting in a behavior that is fairly different than any of the optimal policies. While the definition of optimal occupancy distribution (Def 5.4) could be still quite rich, it is not easy to interpret. I have some questions in this respect\n** Would it be possible to create \"worst-case\" MDPs where the max-quantile fair policy for the optimal occupancy distribution has q*~=0, i.e., the opposite case than in Thm5.1, where basically you restrict the policy space so much that no fair policy is possible.\n** In the worst case of Thm5.1, can you prove that your formulation would have q*>>0?\n** Can you provide some qualitative examples where your formulation is \"meaningful\", i.e., it doesn't exclude policies that are intuitively fair? The empirical results provide some evidence of that, but having a more intuitive illustration would help.\n\nMinor\n* L175: it should be J_i(pi')<J_i(pi) - eps?\n* L300: \\mathcal K -> \\mathcal K^*\n* Alg1: I would suggest to change the letter in \"s=1 to S\" to avoid confusion with states", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The \"negative\" result showing that quantile fairness defined on all policies can be vacuous is very interesting. The intuition behind this result is intuitive (i.e., in a high-dimensional policy space, it is likely that many policies have poor reward, thus making the max-quantile fairness to be very close to 1.0) and sound and it is likely to hold in general. It is then supported by a theoretical derivation, which relies on the construction of a specific worst-case MDP. This result provides a very solid grounding to the need of developing alternative, more practical formulations.\n* The formulation proposed in the paper (i.e., focusing on optimal policies) is sound and it makes the overall setting much more tractable. This is supported both theoretically (Thm 5.6 / 6.1 / 6.2) and empirically (L448) and it builds on a neat result showing how sampling from the policy space which is the image of the convex hull of optimal rewards can be done efficiently.\n* The empirical results provide a good evidence of the properties of the proposed formulation and algorithm. While a direct comparison with the original quantile fairness formulation cannot be done (i.e., they optimize different objectives), the authors study a number of correlated metrics that support the theoretical claims: 1) the method is more efficient; 2) the max-quantile fairness is significantly lower, showing that the method makes a more \"significant\" trade-off between preferences of different agents; 3) Nash and Gini are better; 4) per-agent return is mostly better.", "weaknesses": "* The paper is originally motivated by RLHF and the use of deepRL techniques. While the current paper is clearly a significant step forward in that direction (e.g., the use of an oracle policy optimization routine, instead of assuming perfect knowledge of the underlying MDP and a more efficient algorithm), it still remains \"limited\" to a more theoretical setting without any direct evidence that the proposed method can scale to deepRL and can be applied to RLHF.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)