Achieving Fairness in Multi-Agent MDP Using Reinforcement Learning
Authors: Peizhong Ju
Arnob Ghosh
Ness Shroff
Venue: ICLR 2024 poster (2024)
Keywords: Fairness
Multi-Agent Reinforcement Learning
Markov Decision Process
Primary area: learning theory

Abstract: Fairness plays a crucial role in various multi-agent systems (e.g., communication networks, financial markets, etc.). Many multi-agent dynamical interactions can be cast as Markov Decision Processes (MDPs). While existing research has focused on studying fairness in known environments, the exploration of fairness in such systems for unknown environments remains open. In this paper, we propose a  Reinforcement Learning (RL) approach to achieve fairness in multi-agent finite-horizon episodic MDPs. Instead of maximizing the sum of individual agents' value functions, we introduce a fairness function that ensures equitable rewards across agents. Since the classical Bellman's equation does not hold when the sum of individual value functions is not maximized, we cannot use traditional approaches. Instead, in order to explore, we maintain a confidence bound of the unknown environment and then propose an online convex optimization based approach to obtain a policy constrained to this confidence region. We show that such an approach achieves sub-linear regret in terms of the number of episodes. Additionally, we provide a probably approximately correct (PAC) guarantee based on the obtained regret bound. We also propose an offline RL algorithm and bound the optimality gap with respect to the optimal fair solution. To mitigate computational complexity, we introduce a policy-gradient type method for the fair objective. Simulation experiments also demonstrate the efficacy of our approach.

Published as a conference paper at ICLR 2024
ACHIEVING FAIRNESS IN MULTI-AGENT MDP USING REINFORCEMENT LEARNING
Peizhong Ju Department of ECE The Ohio State University Columbus, OH 43210, USA ju Ju..110csu.enn
Arnob Ghosh
ECE Department
New Jersey Institute of Technology Newark, NJ 07102, USA
arnob. srnob.ghosh@njae edd
Ness B. Shroff
Department of ECE and CSE The Ohio State University Columbus, OH 43210, USA shroff. 11@osu.
ABSTRACT
Fairness plays a crucial role in various multi-agent systems (e.g., communication networks, financial markets, etc.). Many multi-agent dynamical interactions be cast as Markov Decision Processes (MDPs). While existing research has fo- cused studying fairness in known environments, provably efficient exploration of fairness in such systems for unknown environments remains open. In this paper, we propose a Reinforcement Learning (RL) approach achieve fairness in multi- agent finite-horizon episodic MDPs. Instead of maximizing the sum of individual agents' value functions. we introduce fairness function that ensures equitable rewards across agents. Since the classical Bellman's 's equation does not hold when the sum of individual value functions is not maximized, we cannot use traditional approaches. Instead, in order to explore, we maintain confidence bound of the unknown environment and then propose an online convex optimization based ap- proach to obtain policy constrained to this confidence region. We show that such an approach achieves sub-linear regret in terms of the number of episodes. Addi- tionally, provide probably approximately correct (PAC) guarantee based on the obtained regret bound. We also propose an offline RL algorithm and bound the optimality gap with respect to the optimal fair solution. To mitigate putational complexity, we introduce a policy-gradient type method for the fair objective. Simulation experiments also demonstrate the efficacy of our approach.
INTRODUCTION
In classical Markov Decision Processes (MDPs), the primary objective is to find policy that max- imizes the reward obtained by a single agent over the course of an episode. However, numerous real-world applications, decisions made by an agent can have an impact on multiple agents or enti- ties. For instance, in a wireless network scenario, each device aims to maximize its own throughput by increasing its transmission power. However, higher transmission power can lead to interference issues for neighboring terminals. Similarly, consider situation where two jobs are competing for single machine; selecting one job results penalty or delay for the other job. The sequential decision-making process as in the above examples can be cast multi-agent episodic MDP where the central decision-make seeks to obtain the best policy for multiple users or agents over a time horizon. Each user agent achieves reward (potentially different) based on the state and action.
Before delving into the concept of an optimal policy, it is necessary to address what constitutes an optimal policy in the given context. While particular policy may be good for one agent, it may not be the best choice for another agent. naive approach could be to maximize the aggregate value functions across all agents, thereby reducing the problem an approach may not be considered "fair" for all agents involved. To illustrate this, consider a scenario where jobs competing for single machine. If one job offers higher reward,
classical MDP. However, such

---

Published as a conference paper at ICLR 2024
central controller that focuses solely maximizing the aggregate reward may allocate the machine exclusively to the job with the higher reward, causing the job with the lower reward to remain in a waiting state indefinitely. In this paper, our objective is to identify fair decision-making making strategies for multi-agent MDP problems, ensuring that all agents are treated equitably.
Drawing inspiration from well-known faimess principles (Arrow, 1965; Pratt, 1978; Atkinson al., 1970), we establish a formalization of fairness as a function of the individual value function of agents. Specifically,, we concentrate on o-fairness, which encompasses both egalitarian or max-min fairness (when a + oo) and proportional fairness (when a 1). The parameter allows us to adjust the level of fairness desired. To illustrate this concept, let's consider our example of two jobs with different rewards competing for the same machine. Proportional fairness dictates that the machine should be accessed with equal probability by both the low-reward and high-reward jobs. Conversely, max-min fairness suggests that the job with the higher reward should access the machine with a probability that is inversely proportional to its reward.
In this work, we seek to determine the policy that maximizes the a-fairness value of the individual value functions of an MDP. Considering that the knowledge of the environment usually unknown beforehand in real-world applications, we consider a Reinforcement Learning (RL)-based approach. However, a significant challenge of non-linearity arises since the central controller is not optimizing the sum of the individual value functions, rendering the classical Bellman equation inapplicable. Consequently, conventional techniques such as value-iteration- hased or policy-gradient--e based ap- proaches cannot be directly employed. To evaluate an online algorithm, regret is widely used met- ric that measures the cumulative performance gap between the online solution in each episode and the optimal solution. While there are algorithms that provide good empirical performance, they do not provide any regret guarantee. Therefore, we aim to develop an algorithm that exhibits sub-linear regret with respect the a-fair solution. Further, since generating new data costly or impossible for some applications, we also seek to develop provably-efficient offline fair RL algorithm, i.e., an algorithm that requires no real-time new data. short, we seek to answer-
Can we attain a fair RI. algorithm with sub-linear regret for multi-agent MDP? Can we develop a provably-eficient fair offline RI. algorithm?
Our Contributions: We summarize our contributions in the following:
regret where is the length of the horizon of each episode, S is the cardinality of state space, A is the cardinality of the action space, and K is the number of episodes. OF is a parameter determined by the types/parameters of the faimess function.
We show that our proposed algorithm achieves Ō (CP(HHNNSVKK
This is the first sub-linear regret bound for the functionn in MDP. We achieve the result by proposing an optimism-based convex optimization framework using state-action occupancy measures. In our algorithm, we use confidence bounds to quantify the eгrоr of the estimated reward and transition probability, with which we relax the constraints on possible values of the state-action occupancy measures to encourage exploration. With any convex optimization solver, our proposed algorithm can be solved efficiently polynomial time. In order to address large state-space problems, we also develop efficient policy- seficy-gradient-base approach that caters to the function approximation setup.
We also propose pessimistic version of the optimization problem and establish the theoretical guarantees for the offline fair RI. setup. In particular, we construct an MDP with a reward function based on the available data such that the value function of the constructed MDP is lower bound of the actual value function for the same policy with high probability. The policy is obtained by solving the convex optimization problem using the occupancy measure on the constructed MDP. We show that the sub- sub-optimality gap of our policy depends on the intrinsic uncertainty multiplied by Cp. This is the first result with theoretical bound for the offline fair RL setup.
2 RELATED WORK
Fairness in resource allocation: Fairness in traditional resource allocation setup has been well studied (Mo& & Walrand, 2000; Kelly et al.. 1998; Lin et al., 2006). RL-based fair resource alloca- tion decision- decision-making has also been considered for resource allocation (Chen et al., 2021; Hao et al., 2023; Jain et al., 2017; Cui et al., 2019). However, theoretical guarantees have not been provided.
2

---

Published as a conference paper at ICLR 2024
Fairness in MDP/RL: Joseph et al. (2016); Liu et al. (2017) considered individual faimesss cri- terion which stipulates that an RL system should make similar decisions for similar individuals. Huang et al. (2022); Schumann et al. (2019); Wen al. (2021) considered a group fairness notion where the main focus on policy is fair to a group of users (refer to Gajane et al. (2022) for details). Jiang & Lu (2019) proposed an approach where they perturbed the reward to make it fair across the users. In contrast to the above, our setup is different as we seek to achieve fairness in terms of value functions (i.e., long-term return) of different agents.
Hossain et al. ;; Bistritz et al. (2020); Barman et al. (2022); Patil et al. (2021) considered Nash social welfare (or, proportional fairness) and other faimesss notions in multi-armed bandit setup. Do et al. (2022) also considered fairness in the contextual bandit setup. However, we consider an RI setup instead of bandit setup. The algorithms designed for bandit setup can not be readily extended to the MDP setup. Further, we consider the generic fairess concept rather than the proportional- fairness concept. Zimmer et al. (2021); Siddique et al. (2020) considered a-fairness and Gini social welfare metrics. However, the regret bounds have not been provided there. Finally, we provide a fair algorithm in an offline RL setup, which has not been considered in most the RL literature.
The closest to our work is Mandal & Gan (2022) which adopted a selfare-basedd axiomatic ap- proach and showed regret bound for Nash social welfare. and max-min fairness. In contrast, considered the ox-based fairness metric and showed regret bound for the generic value of a. Unlike in Mandal & Gan (2022), our approach admits efficient computation. Further, we provided the PAC guarantee and developed an algorithm for offline fair RL with a theoretical guarantee. Finally, we also developed a seaeee-ggrdieet-aseeee algorithm that applicable large state space as well.
Convex and multi-objective MDP: Cheung (2019) obtained regret bound for a specific non-linear function of the objectives. Tarbouriech al. (2020) considered an MDP setup with a convex objec- tive for mafinit-hhorizon setup. Brantley et al. (2020) considered an episodic MDP setting where the objective is maximize a concave function of an individual value function. Unlike all the above works, we consider a setup where the objective is to achieve fairness among multiple agents. Natu- rally, the above papers did not consider the effect of various fairness metrics on the agents. Further, the proof techniques and algorithms also rely on the Lipschitz property, however, the faimess func- tion may not be Lipschitz (e.g., a fairness), hence, the proof techniques and the regret bound are also different. Furthermore, we consider offline setup unlike all the above papers. For detailed literature review, please see Appendix A.
BACKGROUND: TYPES OF FAIRNESS IN RESOURCE ALLOCATION
Fairness in resource allocation in multi-agent systems (especially in networks) has been extensively studied (Lin & Shroff, 2005; 2004; Eryilmaz & Srikant, 2007; Neely et al.. 2008). Specifically, in resource allocation, feasible solution is any vector notes the number of agents, x; denotes the allocated resource to each agent, and F denotes a feasible set determined by some constraints. A fair objective is to allocate resources while maintaining some kind of fairness. As described in Mo & Walrand (2000), the following are some standard definitions of fairness.
[x: 22 xN E F C R where N de-
Proportional Fairness: A solution x' is proportional fair when it is feasible and for any other feasible solution F. the aggregate of proportional change is non-positive:
MM zi-z S.
In particular, for all other allocations, the sum of proportional rate changes with respect to x" is non-positive. Proportional faimness is widely used in network applications such as scheduling.
Max-min fairness:
Max-min fairness wants to get a feasible solution that maximizes the minimum resources of all agents, i.e., max min; 2;. For this solution, no agent can get more resources without sacrificing another agent's ' resources.
(p, a) prooporriion fairness:
Let (p1,... .PN) and a be positive numbers. A solution x" is (p, proppooooli fair when it is feasible and for any other feasible solution æ E F, we have
ΣN
N
Ps 2
$ 0.
3

---

Published as a conference paper at ICLR 2024
When p (1,... 1) and 1, Eq. (2) reduces Eq. (I), i.., the proportionally fair solution.
Besides, by Corollary of Mo & Walrand (2000), the solution of (p, a) proopottionl fair approaches the one of max-min fair - By Lemma of Mo & Walrand (2000), the solution that achieves (p, proppoottiii fairness can be solved by
if a Eptsa(ri); where fa(x) = (1-a))1x'1) other positive a. max 1
flogæ,
When p; = 1 for all i, we denote that by a-fairness in short, which is widely studied in the network- ing literature (Lan et al., 2010). Note that fa is monotonie increasing function, and concave.
SYSTEM MODEL
Multi-agent Finite Horizon MDPs. Let M (N, H) be the finite-horizon MDP, where N denotes the number of agents, A denotes the action space with cardinality A, S denotes the state space with cardinality S, and И is positive integer that denotes the horizon length. At time h 1,2, H, we let (s) a) denote the non-stationary immediate reward for the i-th agent when action is E A at state E S. The transition probability is denoted by ps (s' ( a). Note that this setup can be easily extended to the scenario where agents are also part of the MDP by letting A denote the joint action space of all agents.
4.1
VALUE FUNCTION AND FAIRNESS
The state-action value function of agent i is defined as
" a) = (n, + E Σ
1100(1,)))ls), = 5,an a, u,
1=h+1
The i-th agent's value function is defined
(o) =
= EncA (ala)) (s. (s.
To achieve fairness among each agent's 's return, we optimize different global value function (instead of VTT. (... that sums up each agent's 's return):
(s) = F(V.. VT (+), VT. (i
(3)
where F is some function of every agent's return that can be chosen for fairness. Similar to the fairness objective used in resource allocation literature (Mo & Walrand, 2000), we consider the fol- lowing three possible options of F:
Faux min min(V". (s), VT. (+), (s), .. VI. (,vv) (5)) (max-min fairness), P Prropontonnl
1,(1)
(4)
EM' log ViT (s)
(proportional fairness),
(5)
Fa = ΣE
N I-a V (. (s)
(a fairness where a > 0),
(6)
Note that we have adopted the a-fairness in resource allocation the a-fairness value functions across the agents. Chen al. (2021) also formalized fairness among value functions in network applications. Recently, Zhang et al. (2022) also adopted a-fairness to federated learning setup. In the rest of this paper, we sometimes remove the superscript F in V P (s) for ease of notation.
Remarks and Connections: From (1), maximizing proportional faireess in the value function means that the average relative value function is maximized. In particular, at any other policy, the average relative value function across the agents would be reduced compared to the proportionally fair maximizing policy. Hossain et al. (2021), Mandal & Gan (2022) maximize the product (contrast to the sum) of each agent's value function Hh (T)))()) (also, known as Nash social welfare). By taking the logarithm on the product, it is equivalent to E'propottional (Kelly, 1997) in Eq. (5) in our case. Mandal & Gan (2022) has regret bound for Nash social welfare. Even though the proportional- fair solution is Nash social welfare solution, the regret bound for the Nash social welfare and for the proportional fair case is not comparable. For example, their bound scales OHHN), whereas our regret bound scales (2H22 (shown later in this paper). The proof technique is also different.
4

---

Published as a conference paper at ICLR 2024
When O, recover the utilitarian social welfare where the objective is to maximize the sum of the value functions. On the other hand, a = 0c refers to max-min faimess in value functions. By tuning a, can achieve different fairness metries.
One can view different types of fairesss as achieving different goals in society. For example, max-min fairness aims to make decisions that are beneficial to the weakest users.
Social Impact:
4.2 PERFORMANCE EVALUATION
Define the optimal fair value function corresponding to the optimal policy as
(s) supx (s).
The central controller does not know either the probability or the rewards. Rather, it selects a policy Ty for & E [K] episode. Without loss of generality, we assume that the initial state for all episodes the same and fixed. If the initial state s is drawn from some distribution, then we can construct an artificial initial state that is fixed for all episodes, and the distribution of the actual initial state si determines the transition probability Po (1])e [1l a). We consider the bundit-feedbur central controller only observe the rewards (of all the agents) corresponding to the encountered state-action pair (Agarwal et al., 2011; Dani et al., 2008). We assume the following for the reward:
setup, i.e., the
Assumption 1. The noisy observation of the immediate reward is a random variable fn (s, a), which is in the range [ 1] almost surely where is some positive real number. The mean value of the noisy observation is equal to the true immediate reward, ie., E. (1,, a) = -T.,65(8, (8,
Remark 1. We need f 2 मे because this guarantee (=1)) 2 >> 0 which ensures that Eqs. (5) and (6) are finite. Also, this makes the functions Lipschitz continuous everywhere. We characterize the impact of on the regret/subopimalliy bound in Theorem 1.
We are interested in minimizing the regret Reg(K) over finite time horizon K, given by
Reg(K) = Σ (Vi
(s1)).
The regret characterizes the cumulative sum of the difference at each episode k = 1,2, ... K
between the fair value function and the optimal fair value function.
ONLINE FAIR MARL
5.1 OPTIMAL POLICY WITH COMPLETE INFORMATION
Before we characterize the algorithm when the MDP parameters are unknown, we start from the ideal situation where all parameters of the MDP are known, i.e., complete information. The insight will help us develop an algorithm for the challenging scenario when the parameters are unknown.
For the classical objective that maximizes the sum of all agents' returns, the optimal return and policy can be efficiently calculated by backward induction that utilizes the Bellman equation, i.e,
.um
max.cA { (h,(o)ss)) a) + Eves (s
h+1 (e1)
where V (8) = for all E S. The reason for Eq. (7) that maximize Σ VT (.(
(8) is
N equivalent to solving another single-agent MDP with immediate reward equal to ΣM (1) a).
In contrast, such convenience no longer exists for the faimess objective since Eq. (7) relies on the linearity of V," V. (s) w.r.t. (s). To solve this problem, we alternatively use an occupancy- measure-bace based approach which is inspired by Efroni et al. (2020). Define the occupancy measure
(s, p) Pr(ss, s, a, = a s1.
(8)
The occupancy measure defined by Eq. (8) represents the frequency of the appearance for each state-action pair under the policy the notation of (s, a) when the context is clear.
the environment transition probability p. We will omit p in
With this definition, each agent's 's return can be written linear function w.r.t. of (s, a), i...
VT, (s1) = Es,a, (1)
(s, a) (s,
(9)
5

---

Published as a conference paper at ICLR 2024
Then solve convex optimization of (we use 1-,,,,, to denote N inputs of F(-)):
max F ([nnahhhctoss (s i=1,,,..,,) (..,,.))),.....) qEQ
(i.e., max VT: (81)),
(10)
where Q is a set of linear constraints on ạ to make sure is legit occupancy measure with the tran- sition probability p and initial state 81 (details in Appendix C). Since (10) is convex optimization (proof in Lemma 6 in Appendix B), and thus can be solved efficiently in polynomial time. After we get the occupancy measure q, the corresponding policy be calculated by ne (a(s)))
9h(3,0)
E. Th (3.0")
5.2 ONLINE ALGORITHM WITH UNKNOWN ENVIRONMENT
To construct an online algorithm under the bandit-feedback, a straightforward idea is using the empirical average p, F (precisely defined in Eqs. (31) and (30) in Appendix C) of the unknown transition probability p and reward r to replace the precise ones (10). Due to the imprecision of the empirical average, common strategy is to introduce some confidence interval to balance exploration and exploitation as done in Efroni et al. (2020). Here we briefly show the algorithm. More details are in Appendix C.
Define the confidence interval for (s'|s,) ph (s, such that Ph (s'ls, a) (s'ss,,, a)) S (s, for all h e [H 1], S,
(11)
Define the confidence interval for h.(()) (8, a) as ( (s, a) such that
(o. (k, a) S fh, a), for all (H
(12)
After we get the confidence interval the h-th step during the k-th iteration, we solve the following extended convex optimization:
(LEea.h.v (Th,t)(s, (h.((s,a) zn (s.
max F #E2
(13)
1=1,2,-.,NN
where Z is a set constraints that ensures z is a legit state-action -ee-atiioo--ntttttttee occupancy measure given initial state $1 (characterized by the set of probable transition probabilities, see Appendix C).
Once we have solved 2, we can recover the policy by (als(a)s) = E. =n(s.a,s))
Da'."" (s,aa, The whole algorithm is summarized in Algorithm 1. Mandal & Gan (2022) developed an algorithm using the state-action occupancy measure. However, the algorithm in Mandal & Gan (2022) relies op- timization problem with infinite variables, which does not always have a polynomial solver. In contrast, our approach requires only finite variables and is more efficient.
Algorithm Online FairMARL
1: for k = 1, ... K do
2: Calculate the empirical average ph. (s' a), and r p
(.(6) (s, a).
3: Calculate the confidence intervals 38 (s, a, 8') and (
4:
Compute policy T& by solving (13). Execute the policy Tk-
5:
6:
end for
Theorem 1.
With probability 1 8, we have
Reg(K)= = CF (O(H((NSAS)) + O(H OSHPNS
where Cp is a constant determined by the type of fairness. Specifically,
when = F. (ax fairness)
Cp
when F = Proppotional proopotioonal
I/N when F Fmas-min (max-min fairness)
The notation Ö(-) ignores logarithm terms (such log }.)

---

Published as a conference paper at ICLR 2024
Proof of Theorem is in Appendix C. Here provide proof outline:
First, for the optimism choice of q (i..,, Tt). r. p. we have Vi (s:;f,p) 2 (1((117) when r.p E Mr (which happens with high probability). By the montonocity property of F(.), we thus have Ek (vi-P (s1) (vi' - Vi (6i)
S S vx))((s))
(TTe. ($1; Vi (s1)..)).
Next, we need to bound ditional techniques, we can not use the standard cilfe-difference lemma to bound the above as the Bellman's equation does not hold. Rather, we obtain the bound in two (st:7.))
V VTu. (,) However, unlike the tra-
by CF N max]e[N] VT (s13 V1,00 (s) The value of CF is determined by the Lipchitz stant of the faimess objective function F or the property of the max-min operator. Then we bound the individual differences (T:(,) (1 ($1; p.) using Azuma- huuma-Hoefdding inequality. The result of Theorem 1 then follows.
steps. First, bound the above by CF E -
1,00
Remark 2. For max-min fairesss, the requirement F 2 デ in Assumption 1 can be relaxed.
To the best of our knowledge, this is the first sub-linear regret for a-fair RL. When 0, we recover the single-agent regret (scaled by N) as it is equivalent to the MDP where the reward is E, (h)())) The constant CF decreases a increases. For the max-min fairness, our result matches that of Mandal & Gan (2022), although our algorithm is more efficient.
From regret PAC guarantee: The probably approximately correct (PAC) guarantee shows how many samples are needed to find an e-optimal policy satisfying V (s1) (s1) S & (Jin et al., 2018; Valiant, 1984). Similar to Section 3.1 in Jín al. (2018), order to get the probably approx- imately correct (PAC) guarantee from regret, we can randomly select
Ty for k = .... K. We define such a policy as π mix However, since (s) is not linear w.r.t. the immediate reward
generally VyT"". (F(ss + + E VITa.F(s)) (s). Therefore, compared with Jin et al. (2018), some additional derivation is needed to achieve PAC guarantee from regret in our case. In particular, from Jensen's 's inequality (since F is concave), ViT"h (s1) 2 K Ex=n ViT* (s1). We obtain
Theorem 2. To find e-oplimal policy, with high probability, it suffices to have C number of samples where
C = CF max S O(H2N' Ö(HPNSS*
Proof of Theorem 2 is in Appendix D.
Fair Online Policy Gradient. In the proposed convex-optimizzaion-bae algorithm, the decision variable and the constraints scale with the cardinality of the state space. In order to develop an algorithm for large state space, generally function approximation-based approaches (e.g.. using neu- ral networks) used to approximate the Q function or value function. We can use policy-gradics methods that cater to such a function approximation iproxiinatoonbbasedd approach. In particular, consider a trajec- tory (s), a7, (7) 1=,,,,, . where f% (P). ,FT,)N)) denotes the noisy observation of immediate reward for all agents. We define the return for the i-th agent as (() == -E ())
To calculate the gradient of the fair objective, we can apply the chain rule of VoF(-). We use proportional fairness F Prroportional as an example of calculating the gradient:
Σ Olog
1,(0) (s1))
VoVT. (s1)
VOV. (s1) Vo Σ
log v (31)
1,0) (.(
V To (11)
(V
(s1
1=1
1=1
It is known that V VOVT (51) E- ( log To(a,, [) and Vili E (R(e))))) By using 1,(3)
the empirical average replace EE,, we can get an unbiased estimator of gradient w.r.t. O as follows:
Ipropectional ΣN Eeer TH (r) log (8(7)))))
Eren (r)
For other types of fairness, we can use a similar method. The final expression of the gradient, the rest part of the algorithm, and other related details are in Appendix F. Note that can extend this actor-critic method, and caseline-basee approach. Charac-
approach to the natural terization of the convergence rate of the approaches are beyond the scope of this paper. Interested
7

---

Published as a conference paper at ICLR 2024
readers can refer to Zhang al. (2020); Agarwal al. (2021); Mei al. (2020) for convergence analysis of standard policy gradient.
OFFLINE FAIR MARL
As mentioned in the Introduction, we develop an offline algorithm because for some applications generating new data may not be feasible. In an offline setting, the learner is given a dataset and needs to compute policy only based on this given dataset. One cannot employ a policy and measure its return. Due to this difference, instead of optimism, pessimism is optimal for standard MDP (Xie et al., 2021; Jin et al., 2021b). We develop an offline fair algorithm and analyze its sub- optimality gap. Before delving into the result, need to have some assumptions about the data collection process.
Assumption 2. The dataset (0), 27, (EIN) is compliant with the underlying MDP, i... Vi,
Po(T), = 11, = 2''l <1 ( (0
{(r
=P( an)) ry. sh+1 x' sh = 2h. on a,)))
The above assumption is satisfied when the data is collected by interacting with the environment and the policy is only updated at the end of an episode. Jin et al. (2021b) also uses a similar assumption. Similar to the online algorithm, we denote the empirical estimation p and F on p and r, respectively, for the dataset D. We first define the uncertainty quantizer for the data set which we use to construct MDP with pessimistic reward.
Definition 1. We define the & as the ô-uncenrtainty quantifier with respect to the dataset D as
E 1%,,,, 0). UR (8, 8', | ()) S (s, In (s' 1s, a) pa (8'1s, a)) & (8, 8' Vi,
such that PD(E) 2 1 5.
The values of 87 a, 6), by (s, a, s', 5) are given in Appendix E. They are related to Ph and K The only difference is that the empirical estimation now depends on the dataset rather than the obtained information till episode k in the online version.
We can show that with probability 1 8, for any Vin(()
[PA[V,,0) PolV a)l
Σ (P p H M (,
We then define the pessimistic reward (o)()) as
2x. TM,00 8% (8, H H (,,
Note that we have also subtracted H HE (s, a, 8') in order to ensure the value function attained for the MDP with reward Ta,(s) and empirical probability Pn is less than the value function corre- sponding to the original MDP parameters for the same policy, i..,, ensure pessimism. Note that similar pessimistic estimate is also used in constrained MDP setup (Liu et al., 2021). However, our proof and algorithms are different as we consider fair objective.
To bound the suboptimality, we need an additional assumption that each agent's return under pes- simistic reward should be positive and shouldn't 't be too small. Specifically, need the following assumption.
Assumption 3. (1,69 L.P) 2 e for all i.
The above assumption is required to apply the Lipschitz continuous property (see Lemma 5 in Ap- pendix B). If (n, (s, a) 2 e/ H for every h, i, 5, a, then the above Assumption is trivially satisfied. Also, our analysis would go through using slightly larger r since the true reward value greater than or equal to e/ H. In particular, we can set (o, (8, a) max (Ta,t) (s,a)= - by, (s, a, a),)) e/}}
H E., (s, a, 8'). Hence, it is clear that Assumption 3 is more likely to hold when the uncertainty
8

---

Published as a conference paper at ICLR 2024
on the estimation of in the offline data is small. This is reasonable because when the uncertainty is high, it is unlikely to bound the regret, especially since some fair objectives are unbounded when any agent's is return is near 0.
Our proposed offine algorithm is solving the following convex optimization:
max TEQ
F([
(s, a)] (=1,,,...,))
(14)
h,8,a
where is the same as Q in (10) but with p instead of Similar to the online algorithm, we still use the occupancy measure q to construct convex optimization problem. However, compared with the online version, a key difference is that we use a pessimistic reward instead of the optimistic reward in the objective. Further, the MDP is based on the empirical probability unlike the online setup where we allow the probability to take value within the confidence interval.
6.1 PERFORMANCE GUARANTEE OF THE OFFLINE ALGORITHM
We denote the solution of Eq. (14) as and the corresponding policy as म. The suboptimality of any policy ı is defined by
SubOpt(T;: = (s;r,p) VT" (8;r,)).
Theorem 3. Given offline data D, with probability 1 -
SubOpt(ft s1) I 2N > ((b an, 6) + Σ (sh, On s 6))))
(15)
Antrinsic-Unoerten
To the best of our knowledge, this is the first offline RL result for the a-fairness function. In the standard single-agent MDP, the result also depends the uncertainty quantifier term and intrin- sic uncertainty term that constitutes information theoretic lower limit on optimality-gap (Jin et al., 2021b). Here, scaled by N and Cr. CF the Lipschitz constant which depends on a- fairness function. Further, if the dataset 'D has good coverage over the optimal policy, then the Intrinsic Uncertainty term is small.
Proof of Theorem 3 is in Appendix E. Here we provide a proof sketch: We have SubOpt(ft;s)
V1= -F (s; VT (s: + (VTT'
(s: - (s;
Term
Term 2
+ ( (s:1, F (s:r,p))
(16)
Term
Term 2 of Eq. (16) is non-positive because is the solution of Eq. (14). In standard offline RL literature (Jin et al., 2021b; Xie et al., 2021), Term 3 of Eq. (16) is non-positive because of the pessimism which is proved using Bellman's property. However, since Bellman's property does not hold, we cannot use the standard technique. Rather, we use the fact that F(-) is monotone increasing w.r.t. show Term is non-positive. For Term
use the Lipschitz property of F(-) to show (f:",)s V - (s:..p) < ΣN CrIVT p) VT, (s..,))
(17)
The right-hand side then becomes differences of individual value functions and can be bounded by lemma.
the
NUMERICAL RESULTS
We have conducted experiments on randomly generated MDP environments to verify our online and offline algorithms. Please see Appendix G for details.
CONCLUSION AND FUTURE WORK
In this paper, we develop convex-optinge wwweecoottiizztion-bbee algorithms for both the online and offline fair RL with provable performance guarantee. Potential future directions include studying decentralized fair MARL algorithms and other policy gradient methods along with their convergence. Developing provably-efficient fair RI algorithms beyond tabular setup constitutes future research direction.

---

Published as a conference paper at ICLR 2024
9
ACKNOWLEDGEMENT
This work has been supported in part by NSF grants: CNS-2312836, CNS-2223452, CNS-2225561, USS-21114711, CNS-2106933, a grant from the Army Research Office: W911NF-21-1-0244 and was sponsored by the Army Research Laboratory under Cooperative Agreement Number W91 INF- 23-2-0225. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government authorized to repro- duce and distribute reprints for Government purposes notwithstanding any copyright notation herein. AG was also partly supported by the NJIT startup grant 172884.
REFERENCES
Axel Abels, Diederik Roijers, Tom Lenaerts, Ann Nowé, and Denis Steckelmacher. Dynamic weights in multi-objective deep reinforcement learning. In International Conference Machine Learning, pp. I 11-20. PMLR, 2019.
Alekh Agarwal, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. Advances Neural Information Processing Systems, 24, 2011.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4411-5566 2021.
Kenneth Joseph Arrow. Aspects of the theory of risk-bearing. Helsinki: 1965.
Yrjö Jahnsonian Sätiö,
Anthony B Atkinson et al. On the measurement of inequality. Journal of economic theory, 2(3): 244-263, 1970.
Siddharth Barman, Arindam Khan, Arnb Maiti, and Ayush Sawarni. Fairness and welfare quantifi- cation for regret multi-armed bandits. arXiv preprint arXiv:2205.139300 2022.
llai Bistritz, Tavor Baharav, Amir Leshem, and Nicholas Bambos. My fair bandit: Distributed learning of max-min fairness with multi-player bandits. In International Conference on Machine Learning. pp. 930-940. PMLR, 2020.
Kianté Brantley, Miro Dudik, Thodoris Lykouris. Sobhan Miryoosefi, Max Simehowitz, Aleksan- drs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. Advances in Neural Information Processing Systems, 13:16315-16322 2020.
Jingdi Chen, Yimeng Wang, and Tian Lan. Bringing fairness actor-critic reinforcement learn- ing for network utility optimization. In IEEE INFOCOM 2021-IEEE Conference on Computer Communications, pp. 1-10. IEEE, 2021.
Wang Chi Cheung. Regret minimization for reinforcement learning with vectorial feedback and complex objectives. Advances in Neural Information Processing Systems, 32, 2019.
Jingjing Cui, Yuanwei Liu, and Arumugam Nallanathan. Multi-agent reinforcement learning- resource allocation for uav networks. IEEE Transactions on Wireless Communications, 19(2): 729-743, 2019.
Varsha Dani, Thomas Hayes, and Sham Kakade, Stochastic linear optimization under bandit feedback. 2008
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Zhun Deng, He Sun, Zhiwei Steven Wu, Linjun Zhang, and David C Parkes. Reinforcement learning with stepwise fairness constraints. arXiv preprint arXiv:2211 1.03994, 2022.
10

---

Published as a conference paper at ICLR 2024
Virginie Do, Elvis Dohmatob, Matteo Pirotta, Alessandro Lazaric, and Nicolas Usunier. Contextual bandits with concave rewards, and an application to fair ranking. In The Eleventh International Conference on Learning Representations, 2022.
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for model- reinforcement learning with greedy policies. Advances in Neural Information Processing Systems, 32, 2019.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-explotaatio constrained mdps. arXiv preprint arXi:22003.02189 2020.
Atilla Eryilmaz and Rayadurgam Srikant. Fair resource allocation in wireless networks using queue- length-based scheduling and congestion control. IEEE/ACM transactions on networking, 15(6): 1333-1344, 2007.
Pratik Gajane, Akrati Saxena, Maryam Tavakol, George Fletcher, and Mykola Pechenizkiy. Survey on fair reinforcement learning: Theory and practice. arXiv preprint arXiv:2205. 10032, 2022.
Hao Hao, Changqiao Xu, Wei Zhang, Shujie Yang, and Gabriel-Miro Muntean. Computing of- floading with fairness guarantee: A deep reinforcement learning method. IEEE Transactions on Circuits and Systems for Video Technology, 2023.
Safwan Hossain, Evi Micha, and Nisarg Shah. Fair algorithms for multi-agent multi-armed bandits. Advances in Neural Information Processing Systems, 34:24005-24017 2021.
Wen Huang, Kevin Labille, Xintao Wu, Dongwon Lee, and Neil Heffernan. Achieving user-side fairness contextual bandits. Human- Centric Intelligent Systems, pp. 1-14, 2022.
Rahul Jain, Preeti Ranjan Panda, and Sreenivas Subramoney. Cooperative multi-agent reinforcement learning-based co-optimization of cores, caches, and on-chip network. ACM Transactions on Architecture and Code Optimization (TACO), 14(4):1-25, 2017.
Jiechuan Jiang and Zongqing Lu. Learning fairness in multi-agent systems. Advances in Neural Information Processing Systems, 32, 2019.
Chi Jin, Zeyuan Ahu, Scbastien Bubeck, and Michael Jordan. q-learning provably effi- cient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a simple, efficient, decentral- ized algorithm for multiagent rl. arXiv preprint arXiv:2110.1455: 2021a.
Ying Jin, Zhuoran Yang. and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021b.
Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in learning:
Classic and contextual bandits. Advances in neural information processing systems, 29, 2016.
Frank Kelly, Charging and rate control for elastic traffic. European transactions on Telecommuni- cations, 8(1):33-31 37, 1997.
Frank P Kelly, Aman K Maulloo, and David Kim Hong Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society, 49(3):237-252, 1998.
Tian Lan, David Kao, Mung Chiang, and Ashutosh Sabharwal. An axiomatic theory of fairness in network resource allocation. IEEE, 2010.
Chris Junchi Li, Dongruo Zhou, Quanquan Gu, and Michael Jordan. Learning two-player markov games: Neural function approximation and correlated equilibrium. Advances in Neural Informa- tion Processing Systems, 35:33262-33277 2022.
Xiaojun Lin and Ness B Shroff. Joint rate control and scheduling in multihop wireless networks. In 2004 43rd IEEE Conference on Decision and Control (CDC)IEEE Cat. No. 04CH37601), volume 2, pp. 1489. IEFF, 2004.
11

---

Published as a conference paper at ICLR 2024
Xiaojun Lin and Ness B Shroff. The impact of imperfect scheduling cross-layer rate control in wireless networks. In Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., volume 3, pp. 1804-1814. IEEE, 2005.
Xiaojun Lin, Ness B Shroff, and Rayadurgam Srikant. A tutorial cross-layer optimization in wireless networks. IEEE Journal on Selected areas in Communications, 24(8):1452-144) 2006.
Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34:17133-17193, 2021.
Yang Liu, Goran Radanovic, Christos Dimitrakakis, Debmalya Mandal, and David C Parkes. Cali- brated fairness in bandits. arXiv preprint arXiv:1707.01873 2017.
Debmalya Mandal and Jiarui Gan.
Socially
fair reinforcement learning. arXiv preprint
arXiv:2208. 12584, 2022.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penal- ization. arXiv preprint arXhv:0907.3740. 2009.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pp- 6820-6829. PMLR, 2020.
Blossom Metevier, Stephen Giguere, Sarah Brockman, Ari Kobren, Yuriy Brun, Emma Brunskill, and Philip S Thomas. Offline contextual bandits with high probability fairness guarantees. Ad- vances neural information processing systems, 32, 2019.
Jeonghoon Mo and Jean Walrand. Fair end-to-end window-bast based congestion control. JEEE/ACM Transactions on networking, 86))5566-57,, 2000.
Hossam Mossalam, Yannis M Assael, Diederik M Roijers, and Shimon Whiteson. Multi-objective deep reinforcement learning. arXiv preprint arXiv: 610000207, 2016.
Michael J Necly, Eytan Modiano, and Chih-Ping Li. Fairness and optimal stochastic control for heterogeneous networks. IEEE/ACM Transactions On Networking, 16(2):396-409, 2008.
Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Yadati Narahari. Achieving faimess in the stochas- tic multi-armed bandit problem. The Journal of Machine Learning Research, 22(1):7885-7955, 2021.
John W Pratt. Risk aversion in the small and in the large. In Uncertainty in economics, pp. 59-79. Elsevier, 1978.
Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. A survey of multi- objective sequential decision-making Journal of Artificial Intelligence Research, 48:67-113, 2013.
Candice Schumann, Zhi Lang, Nicholas Mattei, and John P Dickerson. Group fairness in bandit arm 2019.
selection. arXiv preprint
Umer Siddique, Paul Weng, and Matthieu Zimmer. Learning fair policies multi-objective (deep) reinforcement learning with average and discounted rewards. In International Conference Machine Learning, pp. 8905 8915. PMLR, 2020.
Jean Tarbouriech, Shubhanshu Shekhar, Mattco Pirotta, Mohammad Ghavamzadeh, and Alessandro Lazaric. Active model estimation markov decision processes. In Conference on Uncertainty in Artificial Intelligence, pp. 1019-1028, PMLR, 2020.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 134-11111344114) 1984.
Kristof Van Moffaert, Madalina M Drugan, and Ann Nowé. Scalarized multi-objective reinforce- ment learning: Novel design techniques. In 2013 IEEE Symposium on Adaptive Dynamic Pro- gramming and Reinforcement Learning (ADPRL., pp. 191-199. IEFE, 2013.
12

---

Published as a conference paper at ICLR 2024
Min Wen, Osbert Bastani, and Ufuk Topeu. Algorithms for fairness in sequential decision making. In International Conference on Artificial Intelligence and Statistics, pp. 1144-1152. PMLR, 2021.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consisten pessimism for offiine reinforcement learning. Advances neural information processing systems, 34:6683-6694, 2021.
Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan. A generalized algorithm for multi multi-objective reinforcement learning and policy adaptation. Advances neural information processing systems, 32, 2019.
Andrea Zanette and Emma Brunskill. TTghhtr problem-dependen regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learming, pp.
PMLR, 2019.
Chongjie Zhang and Julie A Shah. Fairness in multi-agent sequential decision- making. Advances in Neural Information Processing Systems, 27, 2014.
Guojun Zhang, Saber Malekmohammadi, Xi Chen, and Yaoliang Yu. Proportional faimesss in fed- erated learning. arXiv preprint arXiv:2202.01666 2022.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal Control and Optimization, 58(6): 3586-3612, 2020.
Matthieu Zimmer, Claire Glanois, Umer Siddique, and Paul Weng. Learning fair policies in decen- tralized cooperative multi- agent reinforcement learning. In International Conference on Machine Learning. pp. 12967-12978 PMLR, 2021.
13

---

Published as a conference paper at ICLR 2024
Supplemental Material
A RELATED WORKS IN DETAIL
Fairness in resource allocation: Fairness in traditional resource allocation setup has been well studied (Mo& & Walrand, 2000; Kelly et al., 1998; Lin et al., 2006). RL-based fair resource alloca- tion decision-making has also been considered for resource allocation (Chen et al., 2021; Hao et al., 2023; Jain et al., 2017: Cui et al., 2019). However, theoretical guarantees have not been provided.
Fairness MDP/RL: Zhang& & Shah (2014) proposed max-min fairness in MDP, however, the learning component has not been considered. Joseph et al. (2016); Liu et al. (2017) considered indi- vidual fairness criterion which stipulates that an RL. system should make similar decisions for similar individuals or the worst action should not be selected compared to better one. Huang et al. (2022); Schumann et al. (2019); Wen et al. (2021) considered a group faireess notion where the main focus on policy is fair to a group of users (refer to Gajane al. (2022) for details). Deng et al. (2022); Metevier et al. (2019) considered an approach where fairness is modeled as a constraint to be sat- isfied. (Jiang & Lu, 2019) proposed an approach where they perturbed the reward to make it fair across the users. In contrast to the above, our setup is different as we seek to achieve faimess in terms of value functions (i.e., long-term return) of different agents.
Zimmer et al. (2021); Siddique et al. (2020) considered Gini-faimesss across the value functions of the multiple agents, while we focus on different fairness metrics. Besides, the regret bounds have not been provided there. Hossain et al. (2021): Bistritz et al. (2020); Barman et al. (2022); Patil et al. (2021) considered Nash social welfare (or, proportional fairness) and other fairness notions multi- armed bandit setup. Do et al. (2022) also considered faimess in the contextual bandit setup. How- ever, we consider an RL setup instead of a bandit setup. The algorithms designed for bandit setup can not be readily extended to the MDP setup. Further, we consider the generic fairness concept rather than the proportional-faine -airrnsss-- concept. Finally, we provide a fair algorithm in an offline RL. setup, which has not been considered in most of the fair RL literature.
The closest to our work is Mandal & Gan (2022) which adopted a welfare- axiomatic ap- proach and showed regret bound for Nash social welfare, and max-min faimess. In contrast, we considered the a-based fairness metric and showed regret bound for the generic value of a. Unlike in Mandal & Gan (2022), our approach admits efficient computation. Further, we provided the PAC guarantee and developed an algorithm for offline fair RL with a theoretical guarantee. Finally, we algorithm that applicable large state space as well unlike
also developed a
Mandal & Gan (2022).
Convex and multi-objective MDP: 2013). Most of the approaches considered a single objective by weighing multiple objectives (Van Moffaert et al., 2013; Abels et al., 2019). Few also proposed algorithms to learn Pareto op- timal front (Yang et al., 2019; Mossalam et al., 2016). We consider non-linear function of the mul- tiple value functions and provide a regret bound which was different from the existing approaches. Cheung (2019) obtained regret bound for specific non-linear function of the objectives. Unlike the above, our objective is fairness among multiple agents. Naturally, the above papers did not consider the effect of various faimess metrics the agents. Additionally, they considered infinite-horizon setup rather than an episodic setup which are fundamentally different. Thus, the algorithms are also different. Furthermore, we consider offline setup. Tarbouriech et al. (2020) considered MDP setup with convex objective for infinite-horize the fairness metrics and the offline which we considered. Furthermore, the paper considered sample complexity rather regret bound. Brantley et al. (2020) considered a MDP setting where the objective to maximize a concave function of an individual value function. Unlike the above, we consider a setup where the objective is to achieve fairness among multiple agents. Naturally, the above paper did not consider the effect of various fairness metrics on the agents. Further, the proof techniques and algorithms also rely on the Lipschitz property, however, faimess function may not be Lipschitz d.g..max-minn fairness), hence, the proof techniques are also different. Additionally, our proposed algorithm is computationally much simpler. For example, for the online setup, we only need to solve a convex optimization problem while the algorithm proposed by Brantley et al. (2020) is a bi-level optimization problem where the lower-level problems are convex. Hence, (Brantley et al., 2020)
Our work is related to multi-objective RL (Roijers al.,
setup. However, the above paper also did not consider
14

---

Published as a conference paper at ICLR 2024
needs to solve large number of convex optimization problems each episode. Furthermore, consider offline setup unlike all the above papers.
Multi-agent RL: Another related approach is Multi-agent RL (MARL) which seeks to learn equi- librium (Li et al., 2022; Jin et al., 2021a) in the Markov game. However, our focus is to achieve fairness among the individual value functions. In our setup, the central controller is taking decisions rather than the agents. Hence, the objective is inherently different, and thus, the algorithms and analysis are also different.
However, in all the above setups, the fair policy is largely ignored. Besides, in the above papers, the individual agent takes decision, instead, focus on the setup where the central decision maker is taking the decision. Our focus is to ensure fairness among value functions of individual agents, hence, the setup is inherently different compared the above.
B USEFUL LEMMAS
Lemma 4. Let 31, IN and y1: 12.-
UN be real numbers. We must have
min (1.....,,)
Iz
min
S
max [x,
Yil-
JE(1,2m..)) .N)
(E[N]
Proof. Without loss of generality, we min, de 2 ming Mj- For any arg min, is and any j arg miny Vjj we have
Tt S Ij
which implies that
Iz. Dj* S x. - YJ* S Izj0 yz-
(18)
We thus have
min 24 min Mi
=min min yo
=x++ Vj
[ yor
(by Eq. (18))
max [xg bil
The result of this lemma thus follows.
Lemma 5. Recall the definition of Cp Theorem 1. When Iz y/ 2 6> 0 for all i [N], we must have
F( IN) F(y1, ... UN)I N Cp max [ Vsl
iE(N]
Proof.
When F = F Proppctional have
F(11, 02, [NN
F(hn, U2. ... ",,," ,9N)
N
log x; log 9/
log log (by the triangle inequality)
<N max [log Yogyil iE[N]
<N max b. - -vll-
iE[N]
The last step is by the Lipschitz continuity of log(:) in the domain [c, oo), where ! is the correspond- ing Lipschitz constant.
15

---

Published as a conference paper at ICLR 2024
Similarly, when P Pax since the Lipschitz constant of (1)-= T-a
the domain (c, 00) is ia, we can
show that
F F2 ENN F(y1, V2. ... UN) NN..
max [x, Vil sE[N]
When F = F Fmax-mins by Lemma 4, we have
02, ,N) F(,,,92,". , S max lor - Vil iE[N]
1
=N
max 24
N
N
Notice that in this case Wi, yi is not needed.
In summary, the result of this lemma thus follows.
Lemma 6. (10) a corvex optimization whose value monotone increasing w.r.t the immediate reward r.
Proof. Notice that the constraints of (10) are linear, we only need to prove that the fair objectives in Eqs. (4) (6) are concave w.r.t state-action occupancy measure q and state-action-state occupancy measure z. Notice that 1.(0) is weighted sum of and 2, in order to prove the concavity, it remains to show that Eqs. (4) (6) are concave w.r.t. V 1,00)- Notice that min(-) and log(-) are concave. We only need to verify the concavity of F.. Since
02 xl-aa
1-a
00 a-1
Ox
which is non-positive when x 2 0. Thus, we have also proven the concavity of Fo. Therefore, we have proven that (10) convex optimization.
Notice that r only appears in the objective (i.e., the constraints do not have r), and all F mins F Proopottonall Fa are monotone increasing w.r.t. Thus, the value of (10) monotone increasing w.r.t
The result of this lemma thus follows.
Lemma 7 (Hoeffding's inequality). Let Z1, Zoz, Zu be i.i.. samples of random variable Z E [0, 1}. For any O, must have
ln(2/8)
Pr 2
2
1 1- 8.
71
2n
Lemma 8 (empirical Bernstein inequality (Theorem 4 of (Maurer & Pontil, 2009))). Let
Z1, Ze. Zn be i..d. samples of random variable Z E [0, 1). For any > O. must have
1
2V. ln(4/))
7ln(4/8)
Pr 7
7
2 1 5,
n
3(n - 1)
where VAR,, is the sample variance
VAR, n(n -
Σ ISisisn
(Z, 2,,2
(19)
Lemma 9 (Lemma F.4 of (Dann et al., 2017)). Let Fe Fifori = 1, 2, ... be a filtration and X1, X2, be sequence of Bernoulli random variables with Pr[X; 1[F,-13 P. with P. being F- measurable and X; being F, measurable. For any W 2 0, It holds that
P
Pr exist n: Σ
X1
W
-w
2
t=l
16

---

Published as a conference paper at ICLR 2024
The following is the standard value difference lemma. Its proof can be found in, e.g.. (Dann al., 2017), Lemma E.
Lemma (Value difference lemma). For any two MDPs M' and M" with rewards r' and r" and transition probabilities P' and p", the difference in value functions with respect to the same policy t can be written as
(r' (st, a,, (sc, ac:t))
p
H
+
E prr
(P((5]) at) - (5) (1)
C DETAILS IN SECTION 5
The overall confidence interval is defined as
M == {(0, F) Eq. (11) and Eq. (12)),
i.., the true value of r) in Mg with high probability. We now want to use this confidence interval M& in (10). A possible way is to replace and by (F, E Mr and view f. p as decision
variables. Thus, the objective in (10) now becomes
V F.F.F. (s1). (s
(20)
(P QEQ
It is indeed optimistic solution compared to the real optimal solution because we relax the value of r and p in such optimization (which leads to better objective value). However, is no longer a convex optimization problem because now and p are decision variables. To turn such optimization into a convex one, we need to determine the value of i and á beforehand. To that end, notice the monotonicity of the objective with respect F (proof in Lemma Appendix B). Thus, without affecting the solution of (20), we can let
(s, - h.(6)
(s, (s.
(21)
Now, we only need to determine the value of p. To that end, consider the sute-action-next--ttan occupancy measure 2 (s, a, s':p) pa(s'), a),ā (s, p) Considering Eq. (11), we only need
zn 2s 0, s') - pr (s'(s.a) + (s. s') E 2n(s, for all h E [H - 1]. a,
(22)
2s, 0, 8¹) 2 ph (5'ls,)) 3 (8. a, x)) Eyes zn (8, for all h E [H - 1], 8, 8,
Now we are ready to solve (20) by convex optimization.
C. ABOUT OPTIMIZATION PROBLEMS
In this subsection, we will show details of the optimization problems (10), (20), and (13).
Let pas) denote the probability of the initial state s. (for a fixed initial state st, then μ(()) equals to 1 for s = while equals to 0 otherwise.)
A bout Q (constraints of q):
The following are the constraints that make a legit state-action occupancy measure, i.e., the defi- nition of Q:
Σ (3, = Σ Em-11 a d'm a2)) for all s E S, E [M] (1)
8'.a'
(n)))a) 20
for all S, E A, e [H]
(23)
Σ ()) = pls)
for all s E S.
17

---

Published as a conference paper at ICLR 2024
The constraint Σ., Qh (s) a) E.,a (s(5,a) = for all h (H].
is redundant because the first and the third constraint imply
About Z (constraints of 2):
By the definition of 2, (22) is part of Z. Besides, 2 should also be constrained by Eq. (23). Recall the definition of
Fn (8, a, 8') = pn (8'|1, a)gn (s, a). By summing over the next state s' on both sides of Eq. (24), we have
(24)
E =n( E Em(ss(ss,a)anss..0 (s)
(25)
Summing over a on both sides of Eq. (25), we have
Σ =s, Σa (s)
(26)
Thus, we can rewrite the constraints Q Eq. (23) in the form of 2:
=x) Σ 2h-1(s',a's a',s)
for all s S [H] \ {1},
s'
2n as 20
for all s, a, s.
(27)
Σ 21(s,,,55) mss)
for all s S
In Eq. (27), we get the first constraint by plugging Eq. (26) into the left side of the first constraint of Eq. (23) while plugging Eq. (24) into the right side. We get the third constraint by plugging Eq. (26)
into the third constraint of Eq. (23).
Notice that by replacing g by we have one additional requirement Eq. (24). Using Eq. (25) to replace qb (s, a) in Eq. (24). we can express Eq. (24) as
(x = =h
(s,,,,,)).
(28)
WES
By Eqs. (11) and (28), we have the constraint Eq. (22) (used in the optimization problem (13)).
We now show that (20) is equivalent (13) by the following proposition.
Proposition 11. (20) and (13) are equivalent. In other words, the optimal value of the objective of (20) is equal to the optimal value of the objective of (13).
Proof. By the monotonicity w.r.t shown in Lemma 6, we know that the optimal choice of F in (20) is 3". It remains to show that the effect of choosing optimal of p in (20) is equivalent to Eq. (22). To that end, notice that P does not appear in the objective. Thus, we only need to focus on how affects the constraints of z. Notice that among all constraints in Eqs. (27) and (28), the only one that connects and is Eq. (28). Since the optimal ğ in (20) must be in the confidence interval T 39 p 3r), know that the optimal objective value by using Eq. (22) is at least good as the one by using the optimal p in Eq. (28). From another aspect, For the optimal get by Eq. (22),
can always construct which in the confidence interval [ 3r, P 3P] by letting
sn(s,a,s") Eves (s.0.))
if Σ (8, a,y) + 0,
pn (n'(ss,,))
p
if Σ yes (s, a,y) = 0.
which implies that the optimal objective value by using optimal و in Eq. (28) is at least as good as the by using Eq. (22). The equivalent of these two different approaches is thus follows. I
18

---

Published as a conference paper at ICLR 2024
C.2 PROOF OF THEOREM 1
To prove Theorem 1, we will first introduce the good event and its probability, then prove a regret bound under the good event. Some auxiliary lemmas are needed in the proof. We list them the end of this subsection.
Failure events and the good event
Define the empirical average of the transition probability and the immediate reward at the k-th iteration of Algorithm
k-1
A
(8, a) Σ
(0)) = =a):
(29)
===1
Ph (s' ()) = EN= s% = s, a = =a, sk = =
(30)
max(ni 1oxtttn-(ss,00 (s, 13
E pk'
(1) h.(1) (8, a) 1 (o% = 8, al =
pk- h,10) (8) =
(31)
max max(n/ (m 1 ( (s) 13
Define
8 hh (x, = (s'1s,,), - Dh - (5'(s,
14L%
(32)
max(n/ 1 (s,
3 3max (n f (s,
T.J
(8,)(8,))== max (12
(33)
k- (
(s.
where I.. = 125 AHK and L== = 2n 3SAHNK
We define the following failure events based on confidence intervals in Eq. (11) and Eq. (12).
exist some 8, a, 8', N, ls such that |ph (55'('''),,) - (s 2 ( as,
1 Σ
In as, Iln 3SAH
G" exist some s, a, h, such that n 8-1 (s,a)
(34)
2
jck
G exist some s, a, h, i, & such that
-h7 a) 2 (s, a))
Intuitively, G denotes the case where the transition probability out of the confidence interval, G" denotes the case where the empirical occupancy measure deviates from the actual occupancy measure, and G" denotes the case where the empirical reward is out of the confidence interval. The following lemma estimates the probability of those failure events.
Lemma 12.
We have
Pr[ <
3
Proof. We first focus on the situation on fixed 8, a, 8', r,,,, k.
n
- (x, a) E {0, 1}, then
144
14L
14 4
(8, 4ph 2 (8118, ph (8' a))
>
>
> 2.
3
3
3
Thus, we have
Pr 1h (s'(ss)) (n()sss,a) (h, | (s, E 10,1)]= = 3S2AAH
8
(35)
19

---

Published as a conference paper at ICLR 2024
A- Now consider the case of n n (s, 2 2. We define b1, b2. , where each term
is (oh+1= =s' s under the condition s = and ot = for k = 1.2. ... k 1 (recall the definition of ni (s, a) in Eq. (29)). Thus, 61, 62, .b (ss.a) are n/ (s, a) i.dd samples of Bernoulli distribution with the parameter of the (success) probability pa (s'|s, a). Therefore, the sample variance (defined in Eq. (19)) of these n j-1 -s, a) samples is equal to
Σ
(b. (b,
A k-1 as, (s,a) (s.
isiSiSn, (s,a)-1
Exs 1 s//" = s, af = =a, sht = 5 E ( s = 8, ah = a, h+1 7 8¹)
sk'
n 1 (s, (n - (s,a) -1)
A-1 (s, k-1 (8'18, ph (b'1s,a)) (by Eq. (30))
1 (s)
Ph
22hh (6'1s, a1 Dh ( a))
Thus, by Lemma 8 (where ō = 35 5
) for fixed 8, s',', h, k. we have
40% (s']s, (s'1ss''ss, - Ph (s'(ss' (s))ssa)) In 1252 AHK
Pr
Ph k- (s'(s,a) - pn(s' (s)(|s,)))2
n (s,
7ln 125 AHK
8
3(m) (8, a) 1)
AS
Notice that
7 S
14 when n
x-1 (8, 2 2. We thus have
3(1,, -1)
Pr [Ph (s'(s, (s
[sssssssa]] a) 2 (s. - (2). 352 AHK
(s,
(36)
Combining Eq. (35) and Eq. (36), we thus have
8
Pr - (8, a) - (s'1s, a)) 2 8h (h 1
35a AHK
Applying the union bound by traversing all s, s,a, ..h.k ki we thus have
Pr[G*] S 3'
The result of this lemma thus follows.
Lemma 13. have
Pr( S 3
Proof. For fixed 8, a, h, by Lemma (letting W = In
3SAH
we have
8
35AH
Pr exist le such that n (s, a) S Σ dh
( (s, alp In
3SAH
Applying the union bound by traversing all s, a, h, the result of this lemma thus follows.
Lemma 14. We have
Pr(G") < 3'
20

---

Published as a conference paper at ICLR 2024
Proof. For fixed 8, h, k. by Lemma have
Pr (s. a) ( (s, (s. V n
5 3SAHNK
(s,
Applying the union bound by traversing all s, a, h, i, k. the result of this lemma thus follows. The regret bound under the good event
Lemma 15. If outside the union of all failure events G U GD G", then we must have
SAH
Reg(K) S4CFV 1, K)HNWSAK + 2CFV DT
4ln
+5
HNSA
8'
SAH
+ 8CBV 1g KK) + 400
12g
4ln
+5
HN2
8
28Cr (41m(4 K) 4ln SAH +5)
H2NSAA
=Cr (O(HRNSVAK) +
Proof. Let F* ,², and गh denote the optimal F, P. and policy in (20) in the k-th iteration of Algo- rithm respectively. Since outside G", we have j r. Thus, by Assumption and Remark have
1.6) L.0 (81: f.c ,/) 2 and V (s;7,)) 2c.
(37)
We have
Reg(K)
K
K
(V (s:;,,))
(VT (s: (s1:,,)))) (by optimism, i..., n* and q" are optimal)
K
CpN max N
m 1,(5)
(s1: ph: b²h) ) Vi (81:7, (by Lemma and Eq. (37))
k=1
NC
max [N
[ (s, -rh,(0)sh, h.(1)
+
(s'(s,)) (s'1s V (8': : (D) .D)
P, Ta
(by Lemma 10)
EES
K
< NCN
max E N
Σ
(.( (s. a) rh, (0, an)
(8,,
81, T
k=1
K
H
+ C
Σ
max E
Σ
ph (s'ls, - (,)))s,)))
s1, n
[N
1=1
1=1
Term
(38)
21

---

Published as a conference paper at ICLR 2024
Since outside G" and G", we have
-k-1
h. (s, (
(on, - an) 5 (s,
(39)
ph (s'(s,)) pn(s'ls, a) s 2 ( (s,
(40)
We have
Term A of Eq. (38)
22CFN
Ih
Th (s, (T,,,s)) (by Eq. (39))
(8,0)
L3
N
Σ
hh (5,0)
(by Eq. (33))
max (s, 1)
(8.0)
SAH
+ b))
S2Cr V LTN
2H 2H/SAKln(4+R)) K) SAH
41n 8'
(by Lemma 16)
4hn SAH
-ACFV [) FCF D3
5 HNSA
Since 0 < (111))() < for all h, 8, a, we have
vi (o .p) s H.
(41)
Thus, we have
Term B of Eq. (38)
K H
22C
Th
(8,0) a)
Ehies,,a,s)) (by Eqs. (40) and (41))
1= (s.0)
K
H
<4CpHN
())
V Ph (s'(s,
(a,a)
/max as,
28CpHNSL R
9h Th (s,
+
ΣΣΣ
(by Eq. (32) and
ph (s'ls, s 1)
3
m
()
(8.0)
VS
<ACPHN DA
()
Σ Ph (s
max (s, 1)
(s,a)
28C HNSLL
K
Ih AhTh (s)
(by Mauchy-Schwarz inequality)
3
max(n
(
k-
R= hm (8,0)
K
1
HCN SL
9h (s,a)
max(nn k- (s, (8,
(s.a)
28CHNSSL
K
Oh Th
(s,
ΣΣΣ
(since Eph-sss/lsaa 1)
3
max
(n
(s, 1)
(8.0)
SAH
<8Cr>/ In + K) + +4Cr
T. 4
+ 5) HN223/2A 8
28CrL1 (4 + K) 4lm
SAH 8'
+ 5)
H2 2 A (by Lemma 16).
22

---

Published as a conference paper at ICLR 2024
Some auxiliary lemmas
Define 8' = 3/ and
1 1 Σ jzk
SAH 8'
L (o,a)
an (s, a) 2 In
+
(42)
The following lemmas and proofs are similar to those in (Efroni al., 2019; Zanette & Brunskill, 2019) with different notations. For ease reading, we provide the full proof using the notation of this paper.
Lemma 16. If outside the failure event G", then
K
H
SAH &
Σ
In
(s,0)
I 2H / SAKIn(4 K) + SAH 4ln
+
max(n/ (s. (s,
k=1k=1
8.a
(43)
4h (8)
SAH
ΣΣΣ
$ SAH (41(4++ K) 4ln
+5
(44)
max
k- as,
k=1k=1
Proof. We have
K
H
Th
max(n/ k- (s, a).
1=
1=1
K
H
Th (s, a)
n ( (since n/ (s, 2 1 by Lemma 17)
h=1 8,0
Σ
In
uz (s,
(s, 0. k- n/
1
Σ
Ih T as,
(45)
(s,0)ELe.
k= (s.0)
By Eq. (8), we have
K H
K H Ih (s) S
ΣΣ
Σ
The (s. = KH.
(46)
k=
(s.
k=1 h=1 (s.0)
For the first term of Eq. (45), have
Σ
T (8,a))
n (s,
1= h= Ls.a)
g (s,
Σ
Vantt
(ttt(s (3.0))
nh (s,a)
(s,a)ELu.
H
4h (s,
ΣΣ
E (s,a)ELE,n
Th Th (s)
ΣΣ
(by Cauchy-Sehwarz
Th (s, a)
k=1k=1
KH In)+K) (by Eq. (46) and Lemma 20)
-2H
(SAKIN(44 K).
(47)
23

---

Published as a conference paper at ICLR 2024
By Eq. (47), Eq. (45), and Lemma 19, get Eq. (43). remains to prove Eq. (44). To that end, we have
K
H
On Fi (s, a)
max
(s,a),1}
K
H
9h (s) (8)
(since n/
A (s, a) 2 1 by Lemma 17)
8,0
9h ()
Σ
Ih (8,
nh (s,a)
(s,a]e Tick
k= h= (s.a)
SAH
<4SAH K) + SAH
4hn
+5)
(by Lemma 19 and Lemma 20)
8
SAH
=SAH 41m(44+ K) + 4ln
+
8'
Thus, we have proven Eq. (44). The result of this lemma thus follows.
Lemma 17. If outside the failure event G", for any (s, a) E Lk we must have
th 22 (s, 1}.
n 1 a) 2 max
Σ jsk
Proof. We have
SAH
4-1 (s, a)
Es (s. a)
+ 4
Σ To (8,
(recall the definition of G in Eq. (34))
4
8'
j<k
jck
4h
(s, a) +1
(since (s, a) E LA,
4
j<k
max
TJ (s, a),
(since tht S 1).
isk
Lemma 18. For any (8, a) & Ligh we must have
SAH
Σ
3 (s,
s 4ln
8' +
jSk
Proof. Since (8,a) & Lu.bs we have
SAH
Σ
In (s, < In 8 + 1.
J<k
Thus, we have
SAH
Σ
th To (s, < 4ln
4.
8
JKk
Because Ft < 1, the result of this lemma thus follows.
Lemma 19. have
K
H
SAH 4ln
ΣΣ
Σ
9h (s, S SAH
8 +5
k=
LaA
24

---

Published as a conference paper at ICLR 2024
Proof. Define
0,
if fA* E [K] (s, & Ix B3 otherwise.
(48)
max {k* [K] (s, a) & Lx-
By the definition of Ln, in Eq. (42), we know that
(8,0) & La, for all ls S ks,ahh-
(49)
Therefore, we have
K ΣΣ Σ
K Ih (s) ΣΣΣ
Ih
(s, & La,h)
Aml Ae (e,0)
(s,a) km hml
H haah
Tv (s, a) (by Eq. (48))
(s,a) 1=1 k=1
SAH
SSAH
4ln
5
(by Eq. (49) and Lemma 18).
8
Lemma 20. If outside the failure event G", we must have
4h (s,a) (s,
S 4SAH In(4 K).
k-
n
(e,a)Ehe,n
Proof. We have
K
Tk (s.a)
K
H
In (8,a)
Σ
Σ
(by Lemma 17)
Th (s,a)
Ejsh 9h (s,
k= 1=1
(s,
k= h=1 (s,a)E
H
K
(s,a)
1 ((s,a) E L.,
(50)
Ejsh 9h (s,
(x,0) h= k=
For fixed s, a, h, if
1,2, (s, LR # Ø0 then by the monotonicity of the size of Te, with respect to hi we can define
kea,h = min {K- 1,2,..., (s, E Lu,z)
Thus, we have
(s,
4h (8, a) Ejsk 9h (s,a)
Th
Ejsu 9n (s,a) 1 ((8,a) E Lan
Σ k
Ih (s.a) a)
(51)
4+ Ex.n (s, a)
k=k
The last inequality is because
(s, a) E Lb by the definition of Lg,h in Eq. (42), we have
1 Σ
SAH
In (s, 2 In
+121.
4
jkh
Define functions
Gra.(I)) = (xc [x]]
Un | (s, +
Σ
Ih (8)
(52)
(s.a = % T[x] (s, a).
(53)
25

---

Published as a conference paper at ICLR 2024
T3 Roughly speaking, Gs,a,h (2) is the linear interpolation of the sum of 4h (s. a),, and (x.a,(()) is the step function whose steps 4h Ni
(s, a). We can easily check that when is not integer,
aG (s),,
(54)
Ōx
Notice that the not-differentiable points (i.e., when is an integer) of (a (x) are countable and will not affect the following calculation.
4h (s, a)
+ Σ Ks. k..aniisk In ( (s,a)
a,
K
Is,a. (x)
dx (by Eq. (52) and Eq. (53))
4 G ((,a,,(((1)))
Keaah- 11
pK
g0.a,h dr (since G.,a())) is monotone increasing)
+ (z)
-1
= =In(4 + Ge.a, - 1n(4 + Geaa,haaa 1)) (by Eq. (54))
<In
4+
Σ
In (s)
< <In(44 K).
(55)
By Eq. (55), Eq. (50), and Eq. (51), the result of this lemma thus follows.
L
D PROOF OF THEOREM 2
Proof. For the proof of PAC guarantee, we have
K
Vi (51) VIT (s1) 11 (61)
Σ
(31)
K
1,0
k=1
Because F is a concave function, by Jensen's 's inequality, we have
K
k
1 K
F
K
1,00
1,(0)
(s1)
K
F
[
K
Viaif (s1).
1=1
1=1
Thus,
we have VirF(s) (s1) VietH (s1)
1 EK (vi:((s)) -vitn (s1)
Reg(K K))
By Theorem 1, we know that with high probability Reg(K) (O(H'NSVAR) + 0(HN2 + Thus, by letting
CF
Cr.
K
we can get
K = O' max (o S S
Notice that for each episode we have H samples. Thus, the total number of samples is
C = max (O(HEN3 O(H12 O(
The result thus follows.
26

---

Published as a conference paper at ICLR 2024
E PROOF OF THEOREM 3
Recalling the definition of suboptimality, we get Eq. (16). Term 2 of Eq. (16) is non non-positive because is the solution Eq. (14).
We now bound Term 3. First, we specify the value of b (s, 5) and bg (8, a, s', 6). For the offline setup, we denote nu (s, a, s') as the empirical value within the dataset. Now, set by (s, a, ô) as the value in (12) and bf, (s, s',, ,8) as the value in (32) respectively. From the cilfeediffeeence Lemma, for any i, we have
V (s, (i,,,,ss,,))
Epp
(sn,, -sw)ss
p
Σ
(Pn ans s/1+)) p(on an 1)) V
h=1 444
(56)
From Lemma 12, 13, and 14, we have (s,) a) (8, a)l (8 a, 8), and (p(s,a, 8') p(s,a, s')l $ (8, a, s') with probability 1 - 6. Since, Vh+1(0)) I H. Thus,
V (. Vi,g((,,,
(sh, ab, as, 8h41, o0)
Ep,
Σ
(1ig, an) T(0), an) + 07 (sh, an, 5) + Σ h=1
(57)
Now, by the definition of y, we can bound the above by 0. Finally, using the fact that F(-) monotone increasing, can conclude that Term 3 is bounded by 0.
remains to estimate Term 1. To that end, when the event & (defined in Definition 1) happens, we have
(s (s,())(,aa)
= (8, (),s,,,)) H Σ as, (by the definition of g))
s'eS
(8, aRss,,,s',b (by Definition and the triangle inequality).
(58)
EES
By Assumption we have
FF h.0 (s. H].
F
(59)
27

---

Published as a conference paper at ICLR 2024
Thus, have
apply Lemma 5. Specifically, under Assumption 3 and when the event & happens,
Term I of Eq. (16)
=V- - (s1:T.))
NC max iE|N]
((6) (s1:7,) (1 (by Lemma 5)
N max iE[N]
E [n.c) as) (s. an)
(sh
H
E
T (s'lsn, ph |sh, an)) V (o
(by Lemma 10)
SCpN max E NE[N]
En,(0) (sn: an) - (s,, an)
h=
Cp max IE
(Pn (8'1s,, (8 an)) V (5 R=
(by the triangle inequality)
N
26% (8h, on. 8) + Σ
18 (sk: ab:
s'ES
+ NENE
(by Eqs. (58) and (59) and Definition 1)
E'ES
-2
Uh an. 8) + ai
e'ES
(The expectation E the above equation on the trajectories with optimal policy x on the true MDP with and p.) The result of Theorem thus follows.
F DETAILS OF FAIR ONLINE POLICY GRADIENT
The following proposition gives an estimation of the gradient based on the samples. Proposition 21. After collecting set 'D of trajectories (with the policy wa) where each trajectory T D contains the information (57, 07 T=) then Rd is an unbiased' estimation of the gradient V Vo V (s1).
H Σ
Rig (T) Vo log (o( where i = arg min Σ R(a(T).
mmax-min
D
ie[N] TED
TED h=1
Erep Σm V log To (0g
9 propprtional
E,ED (T)
(60)
i=1
ETED Σ/ (T) lo (a
9a = 1
(Ere (T)
Proof. Based on the chain rule, have the following results.
1. When F = F min- let in arg min V. (s1):
VOV (s1)
V V v (s).
(61)
An unbiased estimation that when [D] De, the estimated value approaches the value.
28

---

Published as a conference paper at ICLR 2024
Notice that V ig almost everywhere if V,
(s1) is continuous w.r.t. O.
2. When F = F propurtional
N log 1,(6) (81)
N VoVi,
1,00 (s1)
Veli (81) = Ve
(62)
1,(0) (81)
When F Fa:
N
N
(oliToP(831) = V
1
yTo
1,(0)
(51)
1-a
1.(1)
(51)
Vo
VoVii (1)).
(63)
It remains approximate Ve
Vi (s) and Vi, (s1) in the above equations. To that end, noticing (.()) (81) Er (r)) we can approximate ((1))) by the empirical average of R(g. i.e.
that V
Σ (T)
(64)
D
TED
Before calculating Va (T)((())) we first list some equations that will be used later.
Probability a trajectory:
H Pr(r = II
pm (s1+1/s an ) (an (anlsn).
(65)
The log- dog-derivative trick:
V Po Pr(r (0) Vo log Pr(r(e).
(66)
3. Log-probabiiltyy of a trajectory:
log Pr(r(0) log II
pa (sh41lsh, (anss())ss) (by Eq. (65))
4=1
H
Σ A=1
log Pa (8 an) log (a(a)ss))
Thus, we have
V Pr(r(0) = Σ v log (e(a
(67)
Notice that to get the above equation, we use the fact that the transition probability p is irrelevant to 0.
29

---

Published as a conference paper at ICLR 2024
Now are ready to calculate V V (51). We have
Vo
V 1,(0) (s1) V E (T)
-Ve /. ((())))
Vo (oP((1(0))(((())
=
(by Eq. (66))
E Vo (rr((())))) (())
= E Reo (T) Vo log Pr(T(0)
H
= E Ro (T)
Σ
Vo log (a())(bn) (by Eq, (67)).
h=1
Thus, approximate V 1,00 (51) by the following empirical average:
H
Σ
(
Ve log To (anlss))
(68)
[D]
P= The result of this proposition thus follows by plugging the empirical estimation Eqs. (64) and (68) into Eqs. (61) to (63).
TED
As an example, we show the whole algorithm for max-min fairnsss in Algorithm 2.
Algorithm Policy Gradient for Max-Min Fairness
1: Initialize: 0, E Rd, step size a' > 0.
2: for each iteration = 0, ... do
3: Collect a set of trajectory 2 by using To, where each trajectory 7 E D contains the infor- mation (sh, at; 11,),=1,,.....1
4: For each collected trajectory, calculate its total reward for each agent
5: For each agent i, get an estimation of its own value function (1,0((5)) +
EtED (T).
D
6: Select the agent with minimum estimated value i arg mi.. ,N V1,10
7:
Calculate the estimated gradient g Rd by
g
R
Vo, log no, (anlan)
D
TED
8: Update the parameters 0/+1 < 0: + a'g.
9:
end for
G SIMULATION RESULTS
In Fig. 1, we plot the curves of V of the optimal policy (dashed red curves) and the curves of the policy calculated by Algorithm (the blue curves) different fair objectives. We can see that for all three different fair objectives, the solution of Algorithm becomes very close to the optimal one after K 550. This validates our theoretical result that the regret scales sub-linearly (Ö since the average regret Ö /K
goes to zero when becomes larger.
K
In Fig. 2, we plot the curves (yF(s1) the optimal policy (dashed red curves) and the curves of the policy calculated by the policy gradient method (the blue curves). We use two-layer fully- connected neural network with ReLU (rectified linear unit) as the policy model. During each iter- ation of the policy gradient algorithm, 20 trajectories generated and collected under the current
30

---

Published as a conference paper at ICLR 2024
(a) max-min fairness
optimal Algo. 1
2.22
2.20
100
200
300
400
500
600
(b) proportional fairness
1.6425
optimal Algo. 1
1.6400
100
200
300
400
500
600
K
(c) fairness (a 5)
0.01900
optimal Algo. 1
0.0195
0
100
200
300 K
400
500
600
Figure I: Curves of (s1) of Algorithm I w.r.t. K for different fair objectives. The solid blue
curve the average of 10 runs with different seeds. The shaded part denotes the range these 10 runs (i.e., the range between the max and the min value).
policy. As shown by Fig. 2, such policy gradient method can achieve the nearly optimal solution within 1000 iterations.
In Figs. 3 and 4, each point of the offline curve is calculated by applying the offline algorithm with the data generated by Algorithm at K-th epoch. We can see that the offline policy is better than the online policy, which is reasonable because the offline policy only needs exploitation (i.e., choose the current best action), while the online policy needs to explore (i.e., try suboptimal actions to estimate the environment).
Figs. 5 and 6 show the cost of fairness. In Fig. 6, the fair optimal solution is evaluated in the classical objective (i.e., the sum individuals' return), compared with the optimal classical (unfair) solution. We can see the gap is not very large, which suggests that the cost of fairness is relatively small. In contrast, Fig. 5, the optimal classical (unfair) solution is evaluated the faimess objective, compared with the optimal fair solution. We can see for some points the gap is significant, which justifies the necessity of fair solution.
G.1 CONFIGURATIONS OF SIMULATIONS
We use synthetic MDP. Each term of the transition probability p is i.i.d. uniformly generated between [0, 1], and then we normalize p to make sure that Eves P(s, a, s') = Every term of the true immediate reward r is f.idd uniformly generated between [0.15, 0.95]. Each noisy observation of immediate reward is drawn from uniform distribution centered at its true value within the range of +0.05 (thus all noisy observations are in [0.1, 1).. Figs. and use = A N = 2 and
H 3. Fig. 3 A = S 3, = 3, H 4. Fig. 4 uses 2,5 2, N 3, H 10. Figs. and use S = 2, H = 3.
31

---

Published as a conference paper at ICLR 2024
(a)
max-min fairness
2.25
optimal
2.00
policy gradient
1.75
200
400
600
800
1000
iteration index
(b) proportional fairness
(st)
VI (st
1.50
optimal
policy gradient
1.25
200
400
600
800
1000
iteration index
(c) fairness (a (a= 5)
-0.02
optimal
policy gradient
0.04
200
400
600
800
1000
iteration index
Figure 2: Curves of VfF(s)) of policy gradient w.r.t. the number of iterations for different fair objectives. The solid blue curve the average of 10 runs with different seeds. The shaded part denotes the range of these 10 runs (i.e., the range between the max and the min value).
max-min fairness
2.4
2.2
optimal
2.0
Algo. (online)
1.8
offline
1.6
1.4
200
400
600
800
1000
K
Figure 3: The curve of the offline algorithm performance w.r.t. the number of data, where the offline data is generated by the Algorithm during the online learning process. Each point is the average of 10 random runs. (A S = N 3, /l = 4)
32

---

Published as a conference paper at ICLR 2024
max-min fairness
6.0
optimal
5.5
Algo. (online)
offline
5.0
4.5
200
400
600
800
1000
K
Figure 4: The curve of the offline algorithm performance w.r.t. the number of data, where the offline data is generated by Algorithm during the online learning process. Each point the average of 10 random runs. (A 2, S = 2, N 3, H 10)
max-min fairness
2-
12
14
(b) proportional fairness
4-
10
12
14
N
(c) fairness (a 5)
0
unfair
opt
14
Figure 5: The value of the fairness objective for the optimal unfair (classical) policy
33

---

Published as a conference paper at ICLR 2024
(a) max- min fairness
Σ, (igg
20
10
i2
14
(b) proportional fairness
20
Σ, Logg
2
4
6
8
10
12
14
N
(c) a fairness (a 5)
Σ (a)()))
fair
opt
14
Figure 6: The value of the classical objective for the optimal fair policy.
34


Reviews:
[{"review_id": "YxlAsxfifv", "reviewer": "Reviewer_uKyX", "summary": "This paper explores the concept of fairness in multi-agent systems in unknown environments, casting the problem as a multi-agent Markov Decision Processes (MDPs) with a fairness-related objective function. The authors propose a Reinforcement Learning (RL) approach that maximizes fairness objectives such as Proportional Fairness and Maximin Fairness. When representing the policy in terms of the visitation measure, this paper shows that the optimal policy can be solved via convex optimization in the space of visitation measures. Based on this observation, a UCB-based online RL algorithm and a pessimism-based offline RL algorithm are proposed.", "questions": "1. Given existing works on UCB-based and pessimism-based RL, what are the technical novelties?\n\n2. Can you run some toy-ish experiments to showcase the performance of the algorithm? In simulation experiments, how do we measure fairness-related regret?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The fairness metric in multi-agent RL has not been extensively studied. This paper extends the UCB and Pessimism, two standard techniques of online and offline RL to this new problem.", "weaknesses": "1. Novelty. It seems that the main novelty of this paper is showing that the optimal fairness-aware policy can be solved by convex optimization in the space of visitation measure. Moreover, the function $F$ is Lipschitz and monotone in each coordinate. Based on this observation, one can easily extend the performance-difference lemma for standard MDP to this new problem. \n\n2. The setting seems a bit restrictive. In particular, this paper considers the centralized setting and assumes all the $N$ agents have the same action $a$. This makes the problem no different from a single-agent MDP with $N$ different reward functions. Moreover, the assumption that the reward function is bounded from below by $\\epsilon/ H$ seems an unnatural assumption. \n\n3. It seems unclear whether the fairness notions studied in this work include most of the common fairness metrics. For example, existing works also study Generalized Gini Social Welfare Function in the context of MARL.", "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": "G951ww7Kx5", "reviewer": "Reviewer_o4PJ", "summary": "This paper aims to address the issue of fairness in multi-agent systems and introduces a fairness function that ensures equitable rewards across agents.\nThe authors propose an online convex optimization-based approach to obtain a policy constrained within a confidence region of the unknown environment.\nAdditionally, the authors demonstrate that their approach achieves sub-linear regret in terms of the number of episodes and provide a probably approximately correct (PAC) guarantee based on the obtained regret bound.\nFurthermore, the authors propose an offline RL algorithm and bound the optimality gap concerning the optimal fair solution.", "questions": "1.\tCould you please provide some examples to demonstrate the effectiveness of fairness in a multi-agent system?\n2.\tI cannot understand what the experiment in the appendix demonstrates. Could you please provide a detailed description？(or how each agent can benefit from the fairness algorithm?)", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is theoretically grounded and introduces fairness algorithms for both online and offline settings. In the online setting, the authors establish a regret bound with a Probably Approximately Correct (PAC) guarantee. \nIn the offline setting, the authors initially demonstrate the suboptimality of the policy.\nOverall, the paper marks a promising start for bringing fairness into Multi-Agent Reinforcement Learning.", "weaknesses": "All concerns relate to the practicality of the method:\n\n1. While the regret bounds are proven with a PAC guarantee, the cardinality of S is often huge in real-world settings, making it difficult to use.\n\n2. Estimating the empirical average of p and r is often challenging in multi-agent settings, and the confidence interval may be unreliable.\n\n3. The occupancy measure is based on the frequency of appearance for each state-action pair, which may be biased and difficult to count since we cannot always experience the entire environment.", "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": "FxAtrxU8G4", "reviewer": "Reviewer_KfsC", "summary": "This paper studies fair MARL. It proposes online and offline RL algorithms and their deep policy gradient counterparts to maximize any fair social welfare from the alpha-fairness class in a multi-agent MDP. To this end, the paper notices that the Bellman operator cannot be readily applied when fairness is a concern, and proposes an alternative based on the occupancy measure. The regret bounds for the proposed algorithms are derived.", "questions": "- Given my comment about the relation to literature, would it perhaps be more fair (pun not intended) to frame the paper as theoretically justifying existing approaches and proposing their new implementations rather than proposing new approaches?\n- End of 5.1: why is the policy defined stochastically instead of deterministic argmax_a q? Wouldn’t the deterministic policy maximize social welfare?\n- Isn’t the online algorithm in 5.2 a variation/extension of UCB for bandits?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- MARL is relevant to the conference; fairness is relevant to MARL.\n- The paper provides an impressive amount of theory. It also explores online and offline settings and extends RL algorithms to deep counterparts. The contributions listed in the Our Contributions section are original and significant.\n- The theory is complemented by simple experiments.", "weaknesses": "Despite the vast contributions, I think the paper somewhat overclaims. I suggest to rewrite some parts of the Abstract, Introduction, and Related work. I elaborate below\n\n- Fairness in (deep) RL, and in particular alpha-fairness, has been studied in multiple prior works. The Related Work section is too concise and does not give the existing literature enough merit. Example: Zimmer et al. 2021 is cited, but is claimed to focus on gini fairness. This is not true: they focus on a general class of fair SW functions, including alpha-fairness, and they have long-term fairness, and they propose a policy gradient algorithm. Another example: Ivanov et al. 2021 is missing, and they have long-term max-min fairness.\n- In abstract, “the exploration of fairness in such systems for unknown environments remains open”. Yet many papers from section 2 are in model-free setting.\n- The experiments are simple. I am not sure how to express it: they are as simple as they could be. One would actually have trouble to come up with simpler experiments. Two to four states, actions, agents, and transitions in an episode, all uniformly generated. This is ok by itself for a theoretical paper: after all, simple experiments are better than no experiments. But the authors claim that “... we also developed a policy-gradient-based algorithm that is applicable to large state space as well.” I would not call four a large number, so there is no evidence for this claim.\n\nOther than these problems, the contribution is primarily theoretical and I only skimmed the theory. I lower my confidence score to reflect this.", "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": "z7rGaZVzCf", "reviewer": "Reviewer_TT7q", "summary": "This paper proposes a fairness function for multi-agent RL that ensures equitable rewards across agents. The authors then propose two algorithms for obtaining the optimal policy; first, they study the online RL setting in which they show that their method achieves sublinear regret in terms of number of episodes. Furthermore, they discuss a policy gradient variant of this method. Second, they propose an offline RL algorithm and bound its optimality gap. Experimental results are carried out on a very limited toy problem.", "questions": "1. Why is the horizon extremely short (H=3) in the experiments in Appendix G? \n2. In Figure 3, why is the offline RL algorithm significantly outperforming the online RL algorithm? I find this a bit surprising because usually online only performs better and more importantly, your proposed online RL algorithm is optimistic whereas your offline RL algorithm is pessimistic.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-motivated and studies an important problem in RL. \n2. The authors provide theoretical analysis of two algorithms for online and offline RL. Although I have not checked the proofs carefully.", "weaknesses": "1. The experimental results are very limited and cast doubts on the applicability of the proposed algorithms:\n* The toy MDPs are very small and have a short horizon.\n* The method is not compared with any other approach from the literature on fair MARL. There is basically no baseline in the experimental results. \n* Since the authors are talking about resource allocation throughout the paper and that problem setting seems to be the main goal. I was surprised to see the experiments are on some randomly generated toy MDPs. \n* I would have preferred to see the experimental results in the main body of the paper, perhaps instead of the proof outlines. \n\n2. I find the paper hard to follow, and I think both the writing and the outline of the paper needs some improvements for more clarity and coherence. Some examples are: \n* Some of the notation is cluttered and overloaded (e.g., equations 10-13) which makes the math hard to understand. \n* While I appreciate the existence of proof outlines, in their current form they are vague (at least to me). Also, I am confused by their positioning in the text; for example, proof outline of Theorem 1 is not immediately after the Theorem.\n* Some section titles are too generic without any useful information. For example Section 5 is titled “Algorithm” whereas Section 6 is titled “Offline Fair MARL”. It makes sense to rename Section 5 to something more informative (e.g., Online Fair MARL).", "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)