In classical Markov Decision Processes (MDPs), the primary objective is to find a policy that maximizes the reward obtained by a single agent over the course of an episode. However, in numerous real-world applications, decisions made by an agent can have an impact on multiple agents or entities. 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 a situation where two jobs are competing for a single machine; selecting one job results in a penalty or delay for the other job. The sequential decision-making process as in the above examples can be cast as a multi-agent episodic MDP where the central decision-maker seeks to obtain the best policy for multiple users or agents over a time horizon. Each user or agent achieves a 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 a particular policy may be good for one agent, it may not be the best choice for another agent. A naive approach could be to maximize the aggregate value functions across all agents, thereby reducing the problem to a classical MDP. However, such an approach may not be considered "fair" for all agents involved. To illustrate this, consider a scenario where two jobs are competing for a single machine. If one job offers a higher reward, a Can we attain a fair RL algorithm with sub-linear regret for multi-agent MDP? Can we develop a provably-efficient fair offline RL algorithm?
Our Contributions: We summarize our contributions in the following:
• We show that our proposed algorithm achieves Õ C F (H 2 N S √ AK) regret where H 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. C F is a parameter determined by the types/parameters of the fairness function. • This is the first sub-linear regret bound for the α-fairness function 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 error 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 in polynomial time. In order to address large state-space problems, we also develop an efficient policy-gradient-based approach that caters to the function approximation setup. • We also propose a pessimistic version of the optimization problem and establish the theoretical guarantees for the offline fair RL 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 a 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-optimality gap of our policy depends on the intrinsic uncertainty multiplied by C F . This is the first result with a theoretical bound for the offline fair RL setup.
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 allocation 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 in MDP/RL : Joseph et al. (2016); Liu et al. (2017) considered individual fairness criterion which stipulates that an RL system should make similar decisions for similar individuals. Huang et al. (2022); Schumann et al. (2019); Wen et al. (2021) considered a group fairness notion where the main focus is 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. (2021); Bistritz et al. (2020); Barman et al. (2022); Patil et al. (2021) considered Nash social welfare (or, proportional fairness) and other fairness notions in multi-armed bandit setup. Do et al. (2022) also considered fairness in the contextual bandit setup. However, 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-fairness concept. Zimmer et al. (2021); Siddique et al. (2020) considered α-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 of the RL literature.
The closest to our work is Mandal & Gan (2022) which adopted a welfare-based axiomatic approach and showed regret bound for Nash social welfare, and max-min fairness. In contrast, we considered the α-based fairness metric and showed regret bound for the generic value of α. 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 policy-gradient-based algorithm that is applicable to 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 et al. (2020) considered an MDP setup with a convex objective for infinite-horizon setup. Brantley et al. (2020) considered an episodic MDP setting where the objective is to 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. Naturally, 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 fairness function may not be Lipschitz (e.g., α 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.
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, a feasible solution is any vector
where N denotes the number of agents, x i 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.
Proportional Fairness: A solution x * is proportional fair when it is feasible and for any other feasible solution x ∈ F, the aggregate of proportional change is non-positive:
(1)
In particular, for all other allocations, the sum of proportional rate changes with respect to x * is non-positive. Proportional fairness 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 x∈F min i x i . For this solution, no agent can get more resources without sacrificing another agent's resources.
(p, α)-proportional fairness: Let p = (p 1 , • • • , p N ) and α be positive numbers. A solution x * is (p, α)-proportionally fair when it is feasible and for any other feasible solution x ∈ F, we have
When p = (1, • • • , 1) and α = 1, Eq. ( 2) reduces to Eq. (1), i.e., the proportionally fair solution.
Besides, by Corollary 2 of Mo & Walrand (2000), the solution of (p, α)-proportional fair approaches the one of max-min fair as α → ∞. By Lemma 2 of Mo & Walrand (2000), the solution that achieves (p, α)-proportional fairness can be solved by
When p i = 1 for all i, we denote that by α-fairness in short, which is widely studied in the networking literature (Lan et al., 2010). Note that f α is a monotonic increasing function, and concave.
Multi-agent Finite Horizon MDPs. Let M = (N, S, A, r, p, s 1 , 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 H is a positive integer that denotes the horizon length. At time h = 1, 2, • • • , H, we let r h,(i) (s, a) denote the non-stationary immediate reward for the i-th agent when action is a ∈ A at state s ∈ S. The transition probability is denoted by p h (s ′ |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.
The state-action value function of agent i is defined as
The i-th agent's value function is defined as V π h,(i) (s) := a∈A π h (a|s)Q π h,(i) (s, a). To achieve fairness among each agent's return, we optimize a different global value function (instead of V π,sum 1 (s) that sums up each agent's return):
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 following three possible options of F :
Note that we have adopted the α-fairness in resource allocation to the α-fairness in value functions across the agents.
Chen et al. (2021) also formalized fairness among value functions in network applications. Recently, Zhang et al. ( 2022) also adopted α-fairness to federated learning setup. In the rest of this paper, we sometimes remove the superscript F in V π,F 1 (s) for ease of notation.
Remarks and Connections: From (1), maximizing proportional fairness 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 N i=1 V π 1,(i) (s) (also, known as Nash social welfare). By taking the logarithm on the product, it is equivalent to F proportional (Kelly, 1997) in Eq. ( 5) in our case. Mandal & Gan (2022) has a regret bound for Nash social welfare. Even though the proportionalfair 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 O(H N ), whereas our regret bound scales as O(N H 2 ) (shown later in this paper). The proof technique is also different.
When α = 0, we recover the utilitarian social welfare where the objective is to maximize the sum of the value functions. On the other hand, α = ∞ refers to max-min fairness in value functions. By tuning α, one can achieve different fairness metrics.
Social Impact: One can view different types of fairness as achieving different goals in society. For example, max-min fairness aims to make decisions that are beneficial to the weakest users.
Define the optimal fair value function corresponding to the optimal policy as V * 1 (s) = sup π V π 1 (s). The central controller does not know either the probability or the rewards. Rather, it selects a policy π k for k ∈ [K] episode. Without loss of generality, we assume that the initial state s 1 for all episodes is the same and fixed. If the initial state s 1 is drawn from some distribution, then we can construct an artificial initial state s 0 that is fixed for all episodes, and the distribution of the actual initial state s 1 determines the transition probability p 0 (s 1 |s 0 , a). We consider the bandit-feedback setup, i.e., the central controller can 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: Assumption 1. The noisy observation of the immediate reward is a random variable rh,(i) (s, a), which is in the range [ ǫ H , 1] almost surely where ǫ is some positive real number. The mean value of the noisy observation is equal to the true immediate reward, i.e., E rh,(i) (s, a) = r h,(i) (s, a).
Remark 1. We need r ≥ ǫ H because this guarantee V π 1,(i) (s 1 ) ≥ ǫ > 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/suboptimality bound in Theorem 1.
We are interested in minimizing the regret Reg(K) over finite time horizon K, given by
) . 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.
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 to 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,
where V * ,sum H+1 (s) = 0 for all s ∈ S. The reason for Eq. ( 7) is that maximize
In contrast, such a convenience no longer exists for the fairness objective since Eq. ( 7) relies on the linearity of V π,sum h (s) w.r.t. V π h,(i) (s). To solve this problem, we alternatively use an occupancymeasure-based approach which is inspired by Efroni et al. (2020). Define the occupancy measure
The occupancy measure defined by Eq. ( 8) represents the frequency of the appearance for each state-action pair under the policy π on the environment transition probability p. We will omit p in the notation q π h (s, a; p) when the context is clear. With this definition, each agent's return can be written as a linear function w.r.t. q π h (s, a), i.e., V π 1,(i) (s 1 ) = s,a,h r h,(i) (s, a) • q π h (s, a).
Then we can solve a convex optimization of q (we use
where Q is a set of linear constraints on q to make sure q is a legit occupancy measure with the transition probability p and initial state s 1 (details in Appendix C). Since ( 10) is a 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 can be calculated by π h (a|s) = q h (s,a) a ′ q h (s,a ′ ) .
To construct an online algorithm under the bandit-feedback, a straightforward idea is using the empirical average p, r (precisely defined in Eqs. ( 31) and (30) in Appendix C) of the unknown transition probability p and reward r to replace the precise ones in (10). Due to the imprecision of the empirical average, a 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 r k-1 h,(i) (s, a) as
After we get the confidence interval at the h-th step during the k-th iteration, we solve the following extended convex optimization:
where Z is a set of constraints that ensures z is a legit state-action-next-state occupancy measure given initial state s 1 (characterized by the set of probable transition probabilities, see Appendix C).
Once we have solved z, we can recover the policy by π k,h (a|s) =
. 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 on an optimization problem with infinite variables, which does not always have a polynomial solver. In contrast, our approach requires only finite variables and is more efficient.
Calculate the empirical average p k-1 h (s ′ |s, a), and r k-1 h,(i) (s, a).
Calculate the confidence intervals β p h,k (s, a, s ′ ) and β r h,k (s, a).
Compute policy π k by solving (13).
5:
Execute the policy π k . 6: end for Theorem 1. With probability 1 -δ, we have
where C F is a constant determined by the type of fairness. Specifically,
.
The notation Õ(•) ignores logarithm terms (such as log 1 δ ).
Proof of Theorem 1 is in Appendix C. Here we provide a proof outline:
First, for the optimism choice of q (i.e., π k ), r, p, we have V π k 1 (s 1 ; r, p) ≥ V * 1 (s 1 ; r, p) when r, p ∈ M k (which happens with high probability). By the montonocity property of F (•), we thus have
However, unlike the traditional techniques, we can not use the standard value-difference lemma to bound the above as the Bellman's equation does not hold.
Rather, we obtain the bound in two steps. First, we bound the above by
. The value of C F is determined by the Lipchitz constant of the fairness objective function F or the property of the max-min operator. Then we bound the individual differences
1,(i) (s 1 ; r, p) using Azuma-Hoeffding inequality. The result of Theorem 1 then follows. Remark 2. For max-min fairness, the requirement r ≥ ǫ H in Assumption 1 can be relaxed. To the best of our knowledge, this is the first sub-linear regret for α-fair RL. When α = 0, we recover the single-agent regret (scaled by N ) as it is equivalent to the MDP where the reward is i r h,(i) . The constant C F decreases as α increases. For the max-min fairness, our result matches that of Mandal & Gan (2022), although our algorithm is more efficient.
From regret to PAC guarantee: The probably approximately correct (PAC) guarantee shows how many samples are needed to find an ε-optimal policy π satisfying Jin et al., 2018;Valiant, 1984). Similar to Section 3.1 in Jin et al. (2018), in order to get the probably approximately correct (PAC) guarantee from regret, we can randomly select π
We define such a policy as π mix . However, since Jin et al. (2018), some additional derivation is needed to achieve PAC guarantee from regret in our case. In particular, from Jensen's inequality (since
. We obtain Theorem 2. To find ε-optimal policy, with high probability, it suffices to have C number of samples where
Fair Online Policy Gradient. In the proposed convex-optimization-based 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 neural networks) are used to approximate the Q function or value function. We can use policy-gradient methods that cater to such a function approximation-based approach. In particular, consider a trajec-
denotes the noisy observation of immediate reward for all agents. We define the return for the i-th agent as
To calculate the gradient of the fair objective, we can apply the chain rule of ∇ θ F (•). We use proportional fairness F proportional as an example of calculating the gradient:
.
. By using the empirical average to replace Eτ , we can get an unbiased estimator of gradient w.r.t. θ as follows:
.
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 we can extend this approach to the natural policy-gradient, actor-critic method, and baseline-based approach. Characterization of the convergence rate of the approaches are beyond the scope of this paper. Interested
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 it needs to compute a 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 suboptimality gap. Before delving into the result, we need to have some assumptions about the data collection process. Assumption 2. The dataset
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 r 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 set E as the δ-uncenrtainty quantifier with respect to the dataset D as-
The values of b r h (s, a, δ), b p h (s, a, s ′ , δ) are given in Appendix E. They are related to β r h,k , and β p h,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 -δ, for any V h,(i)
We then define the pessimistic reward r h,(i) as
Note that we have also subtracted H s ′ b p h (s, a, s ′ ) in order to ensure the value function attained for the MDP with reward r h,(i) and empirical probability p h is less than the value function corresponding to the original MDP parameters for the same policy, i.e., 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 a fair objective.
To bound the suboptimality, we need an additional assumption that each agent's return under pessimistic reward r should be positive and shouldn't be too small. Specifically, we need the following assumption.
The above assumption is required to apply the Lipschitz continuous property (see Lemma 5 in Appendix B). If r h,(i) (s, a) ≥ ǫ/H for every h, i, s, a, then the above Assumption is trivially satisfied. Also, our analysis would go through using a slightly larger r since the true reward value is greater than or equal to ǫ/H. In particular, we can set r h,(i) (s, a) = max{r h,(i) (s, a) -b r h (s, a, δ), ǫ/H} -H s ′ b p h (s, a, s ′ ). Hence, it is clear that Assumption 3 is more likely to hold when the uncertainty on the estimation of p 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 F are unbounded when any agent's return is near 0.
Our proposed offline algorithm is solving the following convex optimization:
where Q is the same as Q in (10) but with p instead of p. Similar to the online algorithm, we still use the occupancy measure q to construct a 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 p, unlike the online setup where we allow the probability to take value within the confidence interval.
We denote the solution of Eq. ( 14) as q and the corresponding policy as π. The suboptimality of any policy π is defined by
Theorem 3. Given offline data D, with probability 1 -δ
To the best of our knowledge, this is the first offline RL result for the α-fairness function. In the standard single-agent MDP, the result also depends on the δ uncertainty quantifier term and intrinsic uncertainty term that constitutes information theoretic lower limit on optimality-gap (Jin et al., 2021b). Here, it is scaled by N and C F . C F is the Lipschitz constant which depends on α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
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. r to show Term 3 is non-positive. For Term 1, we use the Lipschitz property of F (•) to show
The right-hand side then becomes differences of individual value functions and can be bounded by the Value-difference lemma.
We have conducted experiments on randomly generated MDP environments to verify our online and offline algorithms. Please see Appendix G for details.
In this paper, we develop convex-optimization-based 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 RL algorithms beyond tabular setup constitutes a future research direction.
Min Wen, Osbert Bastani, and Ufuk Topcu. Algorithms for fairness in sequential decision making. In International Conference on Artificial Intelligence and Statistics, pp. 1144-1152. PMLR, 2021. Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021. Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan. A generalized algorithm for multi-objective reinforcement learning and policy adaptation. Advances in neural information processing systems, 32, 2019. Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. 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 fairness in federated 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 on Control and Optimization, 58(6): 3586-3612, 2020. Matthieu Zimmer, Claire Glanois, Umer Siddique, and Paul Weng. Learning fair policies in decentralized cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 12967-12978. PMLR, 2021.
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 allocation 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. 2019) considered an approach where fairness is modeled as a constraint to be satisfied. (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. 2022) also considered fairness in the contextual bandit setup. However, 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-fairness 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-based axiomatic approach and showed regret bound for Nash social welfare, and max-min fairness. In contrast, we considered the α-based fairness metric and showed regret bound for the generic value of α. 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 policy-gradient-based algorithm that is applicable to large state space as well unlike Mandal & Gan (2022).
Convex and multi-objective MDP: Our work is related to multi-objective RL (Roijers et al., 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 optimal front (Yang et al., 2019;Mossalam et al., 2016). We consider a non-linear function of the multiple value functions and provide a regret bound which was different from the existing approaches. Cheung (2019) obtained regret bound for a 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 fairness metrics on 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 a MDP setup with convex objective for infinite-horizon setup. However, the above paper also did not consider 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 is 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, fairness function may not be Lipschitz (e.g.,max-min 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) needs to solve a large number of convex optimization problems at each episode. Furthermore, we consider offline setup unlike all the above papers.
Multi-agent RL: Another related approach is Multi-agent RL (MARL) which seeks to learn equilibrium (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 a decision, instead, we 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 to the above.
Proof. Without loss of generality, we let min i x i ≥ min j y j . For any i * ∈ arg min i x i and any j * ∈ arg min j y j , we have
which implies that
We thus have
The result of this lemma thus follows.
Lemma 5. Recall the definition of C F in Theorem 1. When x i , y i ≥ ǫ > 0 for all i ∈ [N ], we must have
Proof. When F = F proportional , we have
The last step is by the Lipschitz continuity of log(•) in the domain [ǫ, ∞), where 1 ǫ is the corresponding Lipschitz constant.
Similarly, when F = F α , since the Lipschitz constant of (
When F = F max-min , by Lemma 4, we have
Notice that in this case x i , y i ≥ ǫ is not needed.
In summary, the result of this lemma thus follows.
Lemma 6. ( 10) is a convex optimization whose value is 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) to ( 6) are concave w.r.t. state-action occupancy measure q and state-action-state occupancy measure z. Notice that V π 1,(i) is a weighted sum of q and z, in order to prove the concavity, it remains to show that Eqs. ( 4) to ( 6) are concave w.r.t. V π 1,(i) . Notice that min(•) and log(•) are concave. We only need to verify the concavity of F α . Since
which is non-positive when x ≥ 0. Thus, we have also proven the concavity of F α . Therefore, we have proven that ( 10) is a convex optimization.
Notice that r only appears in the objective (i.e., the constraints do not have r), and all F max-min , F proportional , F α are monotone increasing w.r.t. r. Thus, the value of ( 10) is monotone increasing w.r.t r.
The result of this lemma thus follows.
Lemma 7 (Hoeffding's inequality).
Lemma 8 (empirical Bernstein inequality (Theorem 4 of (Maurer & Pontil, 2009))
where VAR n is the sample variance
Lemma 9 (Lemma F.4 of (Dann et al., 2017)). Let F i for i = 1, 2, • • • be a filtration and X 1 , X 2 , • • • be a sequence of Bernoulli random variables with Pr{X i = 1|F i-1 } = P i with P i being F i-1measurable and X i being F i measurable. For any W ≥ 0, It holds that
The following is the standard value difference lemma. Its proof can be found in, e.g., (Dann et al., 2017), Lemma E.15.
Lemma 10 (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 π can be written as
The overall confidence interval is defined as 11) and Eq. ( 12)} , i.e., the true value of (p, r) is in M k with high probability. We now want to use this confidence interval M k in (10). A possible way is to replace p and r by (r, p) ∈ M k and view r, p as decision variables. Thus, the objective in (10) now becomes
It is indeed an 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, it is no longer a convex optimization problem because now r and p are decision variables. To turn such an optimization into a convex one, we need to determine the value of r and p beforehand. To that end, notice the monotonicity of the objective with respect to r (proof in Lemma 6 in Appendix B). Thus, without affecting the solution of (20), we can let
Now, we only need to determine the value of p. To that end, consider the state-action-next-state occupancy measure z π h (s, a, s ′ ; p) := p h (s ′ |s, a)q π h (s, a; p). Considering Eq. ( 11), we only need
Now we are ready to solve (20) by convex optimization.
In this subsection, we will show details of the optimization problems ( 10), ( 20), and (13).
Let µ(s) denote the probability of the initial state s. (for a fixed initial state s 1 , then µ(s) equals to 1 for s = s 1 while equals to 0 otherwise.)
The following are the constraints that make q a legit state-action occupancy measure, i.e., the definition of Q:
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 at 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 1 as
Define
where L p δ := ln 12S 2 AHK δ and L r δ := 2 ln 3SAHN K δ .
We define the following failure events based on confidence intervals in Eq. ( 11) and Eq. ( 12).
G p := exist some s, a, s ′ , h, k such that
Intuitively, G p denotes the case where the transition probability is out of the confidence interval, G n denotes the case where the empirical occupancy measure deviates from the actual occupancy measure, and G r 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
Proof. We first focus on the situation on fixed s, a, s ′ , h, k.
Thus, we have
Now we consider the case of
samples of Bernoulli distribution with the parameter of the (success) probability p h (s ′ |s, a). Therefore, the sample variance (defined in Eq. ( 19)) of these n k-1 h (s, a) samples is equal to
)) (by Eq. ( 30))
Thus, by Lemma 8 (where δ = δ 3S 2 AHK ), for fixed s, a, s ′ , h, k, we have
Combining Eq. ( 35) and Eq. ( 36), we thus have
Applying the union bound by traversing all s, a, s ′ , h, k, we thus have
The result of this lemma thus follows.
Lemma 13. We have
Proof. For fixed s, a, h, by Lemma 9 (letting W = ln 3SAH δ ), we have
Applying the union bound by traversing all s, a, h, the result of this lemma thus follows.
Lemma 14. We have
Proof. For fixed s, a, h, i, k, by Lemma 7, we have
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 p ∪ G n ∪ G r , then we must have
Proof. Let rk , pk , and π k denote the optimal r, p, and policy in (20) in the k-th iteration of Algorithm 1, respectively. Since outside G r , we have rk ≥ r. Thus, by Assumption 1 and Remark 1, we have
We have
(by optimism, i.e., rk and qk are optimal)
1,(i) (s 1 ; r, p) (by Lemma 5 and Eq. ( 37))
Since outside G r and G p , we have
We have
Term A of Eq. ( 38)
q π k h (s, a)β r h,k (s, a) (by Eq. ( 39))
(by Eq. ( 33))
Since 0 ≤ rk-1 h,(i) (s, a) ≤ 1 for all h, i, s, a, we have
Thus, we have Term B of Eq. ( 38)
β p h,k (s, a, s ′ ) (by Eqs. ( 40) and ( 41))
(by Eq. ( 32) and 1 -p k-1 h (s ′ |s, a) ≤ 1)
(by Cauchy-Schwarz inequality)
Define δ ′ := δ 3 and
The following lemmas and proofs are similar to those in (Efroni et al., 2019;Zanette & Brunskill, 2019) with different notations. For ease of reading, we provide the full proof using the notation of this paper.
Lemma 16. If outside the failure event G n , then
Proof. We have
By Eq. ( 8), we have
For the first term of Eq. ( 45), we have
(by Cauchy-Schwarz inequality) ≤ √ KH 4SAH ln(4 + K) (by Eq. ( 46) and Lemma 20)
By Eq. ( 47), Eq. ( 45), and Lemma 19, we can get Eq. ( 43). It remains to prove Eq. ( 44). To that end, we have Thus, we have proven Eq. ( 44). The result of this lemma thus follows.
Lemma 17. If outside the failure event G n , for any (s, a) ∈ L k,h , we must have
Proof. We have
Lemma 18. For any (s, a) ∈ L k,h , we must have
Proof. Since (s, a) / ∈ L k,h , we have
Thus, we have
j<k q πj h (s, a) < 4 ln SAH δ ′ + 4.
Because q π k h ≤ 1, the result of this lemma thus follows. Lemma 19. We have
By the definition of L k,h in Eq. ( 42), we know that
Therefore, we have
q π k h (s, a) (by Eq. ( 48))
≤SAH 4 ln SAH δ ′ + 5 (by Eq. ( 49) and Lemma 18).
Lemma 20. If outside the failure event G n , we must have
Proof. We have
then by the monotonicity of the size of L k,h with respect to k, we can define
Thus, we have
The last inequality is because (s, a) ∈ L k s,a,h ,h , by the definition of L k,h in Eq. ( 42), we have
G s,a,h (x) := (x -⌊x⌋) • q
g s,a,h (x) := q
Roughly speaking, G s,a,h (x) is the linear interpolation of the sum of q πj h (s, a), and g s,a,h (x) is the step function whose steps are q πj h (s, a). We can easily check that when x is not an integer, ∂G s,a,h (x) ∂x = g s,a,h (x).
(54)
Notice that the not-differentiable points (i.e., when x is an integer) of G s,a,h (s, a)(x) are countable and will not affect the following calculation.
K k=k s,a,h
dx (by Eq. ( 52) and Eq. ( 53))
dx (since G s,a,h (•) is monotone increasing)
= ln(4 + G s,a,h (K))ln(4 + G s,a,h (k s,a,h -1)) (by Eq. ( 54))
By Eq. ( 55), Eq. ( 50), and Eq. ( 51), the result of this lemma thus follows.
Proof. For the proof of PAC guarantee, we have
Because F is a concave function, by Jensen's inequality, we have
Thus, we have
.
By Theorem 1, we know that with high probability
we can get
Notice that for each episode we have H samples. Thus, the total number of samples is
The result thus follows.
Recalling the definition of suboptimality, we get Eq. ( 16). Term 2 of Eq. ( 16) is non-positive because π is the solution of Eq. ( 14).
We now bound Term 3. First, we specify the value of b r h (s, a, δ) and b p h (s, a, s ′ , δ). For the offline setup, we denote n h (s, a, s ′ ) as the empirical value within the dataset. Now, set b r h (s, a, δ) as the value in (12) and b p h (s, a, s ′ , δ) as the value in (32) respectively. From the Value-difference Lemma, for any i, we have
From Lemma 12, 13, and 14, we have
Now, by the definition of r, we can bound the above by 0. Finally, using the fact that F (•) is monotone increasing, we can conclude that Term 3 is bounded by 0.
It remains to estimate Term 1. To that end, when the event E (defined in Definition 1) happens, we have
b p h (s, a, s ′ , δ) (by Definition 1 and the triangle inequality). ( 58)
By Assumption 3, we have
Thus, we can apply Lemma 5. Specifically, under Assumption 3 and when the event E happens, we have Term 1 of Eq. ( 16)
(by the triangle inequality) 58) and ( 59) and Definition 1)
) .
(The expectation E in the above equation is on the trajectories with optimal policy π * on the true MDP with r and p.) The result of Theorem 3 thus follows.
The following proposition gives an estimation of the gradient based on the samples. Proposition 21. After collecting a set D of trajectories (with the policy π θ ) where each trajectory τ ∈ D contains the information
.
(60)
Proof. Based on the chain rule, we have the following results.
It remains to approximate ∇ θ V π θ 1,(i) (s 1 ) and V π θ 1,(i) (s 1 ) in the above equations. To that end, noticing that V π θ 1,(i) (s 1 ) = Eτ R (i) (τ ), we can approximate V π θ 1,(i) (s 1 ) by the empirical average of R (i) , i.e.,
Before calculating ∇ θ V π θ 1,(i) (s 1 ), we first list some equations that will be used later. 1. Probability of a trajectory:
2. The log-derivative trick:
3. Log-probability of a trajectory:
Thus, we have
Notice that to get the above equation, we use the fact that the transition probability p is irrelevant to θ.
∇ θ log π θ (a h |s h ) (by Eq. ( 67)).
Thus, we can approximate ∇ θ V π θ 1,(i) (s 1 ) by the following empirical average:
The result of this proposition thus follows by plugging the empirical estimation Eqs. ( 64) and ( 68) into Eqs. ( 61) to (63).
As an example, we show the whole algorithm for max-min fairness in Algorithm 2.
Algorithm 2 Policy Gradient for Max-Min Fairness
Collect a set of trajectory D by using π θ l where each trajectory τ ∈ D contains the information (s h , a h , r h ) h=1,2,••• ,H .
For each collected trajectory, calculate its total reward for each agent 5:
For each agent i, get an estimation of its own value function V θ l 1,(i) (s 1 ) ←
1 |D| τ ∈D R (i) (τ ).
Select the agent with the minimum estimated value î * θ l ← arg min i∈{1,2,••• ,N } V θ l 1,(i) (s 1 ).
Calculate the estimated gradient g ∈ R d by
∇ θ l log π θ l (a h |s h ).
Update the parameters θ l+1 ← θ l + α ′ g. 9: end for
In Fig. 1, we plot the curves of V F 1 (s 1 ) of the optimal policy (dashed red curves) and the curves of the policy calculated by Algorithm 1 (the blue curves) for different fair objectives. We can see that for all three different fair objectives, the solution of Algorithm 1 becomes very close to the optimal one after K ≥ 550. This validates our theoretical result that the regret scales sub-linearly ( Õ( √ K)) since the average regret Õ( √ K K ) goes to zero when K becomes larger. In Fig. 2, we plot the curves of V F 1 (s 1 ) of the optimal policy (dashed red curves) and the curves of the policy calculated by the policy gradient method (the blue curves). We use a two-layer fullyconnected neural network with ReLU (rectified linear unit) as the policy model. During each iteration of the policy gradient algorithm, 20 trajectories are generated and collected under the current
0 100 200 300 400 500 600 K 2.20 2.22 V F 1 (s 1 ) (a) max-min fairness optimal Algo. 1 0 100 200 300 400 500 600 K 1.6400 1.6425 V F 1 (s 1 ) (b) proportional fairness optimal Algo. 1 0 100 200 300 400 500 600 K -0.0195 -0.0190 V F 1 (s 1 ) (c) α fairness (α = 5) optimal Algo. 1 policy. As shown by Fig. 2, such a 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 1 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 of 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, in Fig. 5, the optimal classical (unfair) solution is evaluated in the fairness objective, compared with the optimal fair solution. We can see for some points the gap is significant, which justifies the necessity of a fair solution.
We use a 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 s ′ ∈S p(s, a, s ′ ) = 1. Every term of the true immediate reward r is i. i.d. uniformly generated between [0.15, 0.95]. Each noisy observation of an immediate reward is drawn from a uniform distribution centered at its true value within the range of ±0.05 (thus all noisy observations are in [0.1, 1]). 0 200 400 600 800 1000 iteration index 1.75 2.00 2.25 V F 1 (s 1 ) (a) max-min fairness optimal policy gradient 0 200 400 600 800 1000 iteration index 1.25 1.50 V F 1 (s 1 ) (b) proportional fairness optimal policy gradient 0 200 400 600 800 1000 iteration index -0.04 -0.02 V F 1 (s 1 ) (c) α fairness (α = 5) optimal policy gradient 0 200 400 600 800 1000 K 1.4 1.6 1.8 2.0 2.2 2.4 V F 1 (s 1 ) max-min fairness optimal Algo. 1 (online) offline 0 200 400 600 800 1000 K 4.5 5.0 5.5 6.0 V F 1 (s 1 ) max-min fairness optimal Algo. 1 (online) offline 2 4 6 8 10 12 14 N 1 2 V F 1 (s 1 ) (a) max-min fairness 2 4 6 8 10 12 14 N 2 4 V F 1 (s 1 ) (b) proportional fairness 2 4 6 8 10 12 14 N -2 0 V F 1 (s 1 ) (c) α fairness (α = 5) unfair opt
An unbiased estimation means that when |D| → ∞, the estimated value approaches the true value.