Reinforcement Learning with Ex-Post Max-Min Fairness
Authors: Wang Chi Cheung
Zi Yi Ewe
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement learning
fairness
regret minimization
multi-objective optimization
constrained Markov decision processes

Abstract: We consider reinforcement learning with vectorial rewards, where the agent receives a vector of $K\geq 2$ different types of rewards at each time step. The agent aims to maximize the minimum total reward among the $K$ reward types. Different from existing works that focus on maximizing the minimum expected total reward, i.e. \emph{ex-ante max-min fairness}, we maximize the expected minimum total reward, i.e. \emph{ex-post max-min fairness}. Through an example and numerical experiments, we show that the optimal policy for the former objective generally does not converge to optimality under the latter, even as the number of time steps $T$ grows. Our main contribution is a novel algorithm, Online-ReOpt, that achieves near-optimality under our objective, assuming an optimization oracle that returns a near-optimal policy given any scalar reward. The expected objective value under Online-ReOpt is shown to converge to the asymptotic optimum as $T$ increases. Finally, we propose offline variants to ease the burden of online computation in Online-ReOpt, and we propose generalizations from the max-min objective to concave utility maximization.

Under review as a conference paper at ICLR 2022
REINFORCEMENT LEARNING WITH Ex-POST MAX- MIN FAIRNESS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider reinforcement learning with vectorial rewards, where the agent re- ceives vector of K 2 2 different types of rewards at each time step. The agent aims to maximize the minimum total reward among the K reward types. Differ- ent from existing works that focus maximizing the minimum expected total reward, i.e. ex-ante max-min fairness, we maximize the expected minimum total reward, i.c. ex-post max-min fairness. Through example and numerical exper- iments, we show that the optimal policy for the former objective generally does not converge to optimality under the latter, grows. Our main contribution is a novel algorithm, Maline-ReeOp that achieves near-optimality under our objective, assuming an optimization oracle that returns a near-optimal policy given any scalar reward. The expected objective value un- der Online-ReOppi is shown to converge the asymptotic optimum T increases. Finally, we propose offline variants to case the burden of online computation in Online-ReOpt, and we propose generalizations from the max-min objective concave utility maximization.
as the number of time steps T
INTRODUCTION
The prevailing paradigm in reinforcement learning (RL) concerns the maximization of a single scalar reward. On one hand, optimizing single scalar reward is sufficient for modeling simple tasks. On the other hand, in many complex tasks there are often multiple. potentially competing, rewards to be maximized. Expressing the objective function as a single linear combination of the rewards can be constraining and insufficiently expressive for the nature of these complex tasks. In addition, suitable choice of the linear combination is often not clear a priori.
In this work, we consider the reinforcement learning with max-min faimess (RL-MMF) problem. The agent accumulates a vector of K > time-average rewards Vn. = (Vi.T,)) R in T time steps, and aims to maximize E[minge(1.... K) VI.T.s). The maximization objective represents ex-post max max fairness, in contrast to the objective of ex-ante max-min fairness by maximizing minke( K) EV[ir,,).
Our main contributions are the design and analysis of the Online-ReOpt algorithm, which achieves near-optimality for the ex-post max-min faimess objective. More specifically, the objective under Online-ReOpt converges to the optimum as T increases. Our algorithm design involves novel adaptation of the multiplicative weight update method (Arora et al. 2012). conjunction with judiciously designed re-optimization schedule. The schedule ensures that the agent adapts his decision to the total vectorial reward collected at a current time point, while allowing enough time for the currently adopted policy to converge before switching to another policy.
En route, we highlight crucial differences between the ex-ante and ex-post max-min faimness objec- tives, by showing that optimal algorithm for the former needs not converge to the optimality even when increases. Finally, our results are extended to the case of maximizing Elg(Virr)) where is Lipschitz continuous and concave reward function.

---

Under review as a conference paper at ICLR 2022
2
RELATED WORKS
The Reinforcement Learning with Max-Min Fairness (RL-MMF) problem described is related to an emerging body of research on RL with ex-ante concave reward maximization. The class of ex-ante concave reward maximization problems include the maximization of ([[[V] as well as its ex- ante variants, including the long term average variant ((E[limr- Vi:rl) and its infinite horizon discounted reward variant. The function : E + R is assumed to be concave.
The class of ex-ante concave reward maximization problems is studied by the following research works. Chow et al.] (2017) study the case where g is specialized to the Conditional Value-at- objective. Hazan et al. (219)) study the case when 9 models the entropy function over the probability
distribution over the state space, in order to construct a policy which induces a distribution over the
state space that is as close the uniform distribution
possible. |Miryoosefi al. (2019) study
the case of minimizing the distance between [[[] and a target set in Te [ee et al. 2019) study
the objective of state marginal matching. which aims to make the state marginal distribution match a given target state distribution. Pareto optimality of [E[V and its ex-ante variants are studied in
(Mannor & Shimkin, 2004, Gábor et al., 1998 Barrett& & Narayanan, 2008 Van Moffaert & Nowé, 2014]. Lastly, a recent work Zahavy et al. (2021) provides a unifying framework that encompasses many of the previously mentioned works, by studying the problem of maximizing g (V.r) and its ex-ante variants, where is concave and Lipschitz continuous. Our contributions, which concern the ex-post max-min fairness [
VI:T.a] and its generalization to the ex-post concave case, are crucially different from the body of works on the ex-ante case. The difference is further highlighted in the forthcoming Scction 3.2
Additionally, body of works Altman 1999]; Tessler et al. (2019); Le et al. (2019; Liu et al. 2020) study the setting where is a linear function, subject to the constraint that E Vi. (or its ex-ante variants) is contained in convex feasible region, such as polytope. There is another line of research works (Tarbouriech & Lazaric (2019); (2019)//Cheung (2019): Brantley et al. (2020) focusing on various online settings. The works Tarbouriech & Lazaric (2019); 9p: Cheung] (2019) focus on the ex-post setting like ours, but they crucially assume that the underlying y is smooth, which is not the case for our max-min objective nor the case of Lipschitz continuous concave functions. In addition, the optimality gap (quantified by the notion of regret) degrades linearly with the number of states, which makes their applications large scale problems challenging. |Brantley et al. (2020) focus on the ex-ante setting, different from our ex-post setting, and their optimality gap also degrades linearly with the number of states.
3 MODEL
Set up. An instance of the Reinforcement Learning with Max-Min Fairness (RL-MMF) problem is specified by the tuple (S, (1, A, T, O). The set S is finite state space, and $1 E S is the initial state. In the collection A = [A.) bes, the set A, contains the actions that the agent can take when he is at state s. Each set A, is finite. The quantity T E N is the number of time steps.
When the agent takes action a E A, at state s, he receives the array of stochastic outcomes (s', Us, a)). governed by the outcome distribution (s, For brevity, we abbreviate the rela- tionship as (s', (U,,)) ~ O(s.a), The outcome E S is the subsequent state he transits to. The outcome U(s, a) (Ux(*, d)){== is random vector lying in [-1, 1]d almost surely. The random variable Ug(s, a) is the amount of type-k stochastic reward the agent receives. We allow the random variables s', (s,
Ux(s a) to be arbitrarily correlated.
T). the agent observes his current state St. Then, he selects an action a, E Ag.- After that, he receives the stochastic feedback ($141, Vi(Se, at)) O(st, az). We denote Vi(s;, a.) = (Vi, k))) where (St: a.) is the type-k stochastic reward received at time t. The agent select the actions {ar)T= with policy π = { which is a collection functions. For each f, the function ne inputs the history Hi-1 = - (s,, ag Vg(s,, } and the current state {st), and outputs a, E As.. We use the notation og to highlight that the action is chosen under policy π. A policy is stationary if for all t, H St it holds that ny (He-1, st) #(s.) for some function म. where (s)) E A, for all s. With a slight abuse of notation, we identify a stationary policy with the function
Dynamics. At time t E {1....
2

---

Under review as a conference paper at ICLR 2022
Objective. We denote Vi. 1 - Vg(5g a.)) as the time average vectorial reward during time 1 to /. under policy The agent's s over-arching goal is to design a policy that maximizes Elgmin [..r)), where Imin IRK + RR is defined as Imin(u) = mi..e(L....KK) vk- Denoting V as the k-th component of the vector Vi.r, the value Imin (VET) = ming 1.T.& is the minimum time average reward, among the reward types 1, ....., K. The function Jmin is concave, and is 1-L.ischiiz w.r.t. || ol over the domain I2
When K = 1, the RL-MMF problem reduces to the conventional RL problem with scalar reward maximization. The case of K is more subtle. Generally, the optimizing agent needs focus on different reward types in different time steps, contingent upon the amounts of the different reward types the current time step. Since the max-min fairness objective could lead to an intractable optimization problem, we aim to design near-optimal policy for the RL-MMF problem.
3.1 REGRET
We quantify the near-optimality of a policy æ by the notion of regret, which is the difference between benchmark opt( (gmin) and the expected reward E Imin (VE.) )] Formally, the regret of a policy in T time step horizon is
Reg n T') - (gmmn)) Elgmin (Vi.)) )]-
The benchmark (pm(P())in) is fluid approximation to the expected optimum. To define opt(P (()m)((()))) we introduce the notation p =
where p(s'|s, a) is the prob- ability of transiting to s' from s,a. In addition, introduce v = a)) v(s, a) = (s, a)] is the vector of the K expected rewards. The benchmark (p((P((ma)) is the optimal value of the maximization problem P(gmin). For any g : IR. - R, we define
where
P(g): max
Σ
((8,a)x(8.a)
SES,
s.t. Σ a(s
p(s)s' (')(''a')a((''d') s NEST'EA,
Σ
(2a)
a
a(s,a) =1
(2b)
aEE,
2(s, a) 2 0
Ys E S,ae E As.
(2c)
The concave maximization problem P ((mmi) serves fluid relaxation to RL-MMF. For each S, a E As. the variable z(s, a) can be interpreted as the frequency of the agent visiting state s and taking action a. The set of constraints (2a) stipulates that the rate of transiting out of state is equal to the rate of transiting into the state s for each & E S, while the sets of constraints (2b) 2ch require that {a(s, a) } =ES forms a probability distribution over the state-action pairs. Consequently, opt(P (pt(Pn(m))) )) is an asymptotic (in 7') upper bound to the expected optimum.
Our goal is to design a policy æ such that its regre (T)) satisfies
D
Reg(T) = opt( (((mi))) Eiinn (Vi.r)
<
T
holds for all initial state 81 E S and all T' E N, with parameters D, > independent of T' We assume the access an optimization oracle A, which returns near-optimal policy given any scalar
reward. For 0 E RRK define the linear function go RRK as gw = T = Σ Ogak- The oracle A inputs K and outputs policy satisfying
K
D
opt((((g))) Elgo (V (Pt()) - E(0 VIT <
(4)
T
for all initial state 81 E S and all T E N, with parameters D 3 > 0 independent of T'. By assuming 3 > 0, we are assuming that the output policy и is near-optimal, in the sense that the difference opt(P(ga))
E V 1rl converges to O as T tends to the infinity. A higher 3 signifies
We omit the notation with for brevity sake
3

---

Under review as a conference paper at ICLR 2022
faster convergence, representing higher degree of near-optimality. We refer to 1l as scalarization of v, with the resulting scalarized reward being v) v(ss, a) for each s, a.
Our algorithmic frameworks involve invoking A sub-routine different O's. In other words, we assume an algorithmic sub-routine that solves the underlying RL problem with scalar reward (the case of K 1), and delivers an algorithm that ensures max-min faimess (the case of K > 1). Finally, while the main text focuses on Imin- our algorithm design and analysis can be generalized to the case of concave g. as detailed in Appendix C
3.2 COMPARISON BETWEEN MAXIMIZING EigaNN (VT:)) AND JNNN (E(VE.)
Before introducing our algorithms, we illustrate the difference between the objectives of maximizing E Imin (VI.) ]]
and Imin [ [VTr) by the deterministic instance in Figure I
with initial state $1 s".
The figure depicts an instance with K = 2. An are represents an action that leads to transition from its tail to its head. For example, the are from 8 to s represents the action a with p(s 5o a²)) = 1. Likewise, the loop at sf represents the action al with p(s s (aatt) = 1. Each are is labeled with its vectorial reward, which is deterministic. For example, with certainty have V(s", a²d) (o) and Vis", alt) (9)
Figure 1:
States and actions are represented by circles and arcs.
Consider two stationary policies T n², defined as (s") a" a=,, (s9) a (sf) - at and (s(")) = a"", a=",=""""" (s") = a²", .T' (sf) = a The policy T²' always seeks to transit to s and then loop at sf indefinitely, likewise for n². With certainty, Vir (5-9/2) Vi (1-177)
The objective Umin (T))) is maximized by choosing Tan uniformly at random from the collection ( We have E B[[ (1/211/277) leading to the optimal value of 1/2 - 12T).. More
generally, existing research focuses on maximizing 9 (E for certain concave g. and the related objectives of maximizing glimy E(VEr] or g (E a a'Vi a)))), where a (0. 1) the discount factor. In these research works, a near-optimal policy i is constructed by first generating collection IT of stationary policies, then sampling ı uniformly at random from IT.
Interestingly, Tran sub-optimal for maximizing E[]ymin ). Indeed, Pr(ViTm = (1-9/77)
Pr(VIT ('-1/T)- 1/2, so we have E[gmin (Vi.ge) )] for all T. Now, consider the deter- ministic policy Tsw. which first follows ne for the first [T/2] time steps, then follows x" in the remaining [T/2] time steps. We have ViT
1/2 2/T for each he E {1,2), meaning that
Gmin ( 2 1/2 2//T. Note that ymin (B[V 1rr 1) 2 9min (T[(
2/T, so the policy www is also
near-optimal for maximizing Imnn (Fnii (E..))
Altogether, an optimal policy for maximizing Imin [E| VV 1:7 1) can be far from optimal for maximizing
Elgmin ). ]] In addition, for the latter objective, it intuitive to imitate Tsw. which is to partition the horizon into episodes and run suitable stationary policy during each episode. A weakness to Tew is that its partitioning requires the knowledge on T. While our algorithm follows the intuition
to imitate sww we propose alternate partitioning that allows does not require T an input.
4 ONLINE-REOP ALGORITHM FOR RL-MMF
We propose the Online-ReOpp algorithm, displayed in Algorithm The algorithm runs in episodes. An episode m E {1, 2....) starts time ((m) (defined in Line 2p. and ends at time T(m + 1) 1. Before the start of episode m. the algorithm computes the scalarization 2-(m) based on the Mul- tiplicative Weight Update (MWU), which we detail later. Then, the algorithm invokes the opti- mization oracle A, which returns policy T. that is near-optimal for the MDP with scalar rewards I'm (rmm (s, a))s... where I'm (8, a) = 7(m) u(s,a) Note that we only assume a black-box access to A, and the parameters Din, 3 do not need to be input to the Algorithm. Finally, the algorithm runs policy nm during episode m. The Online Re-Opt algorithm is an anytime algorithm, since it does not require T as an input. Rather, requires knowing T only during the terminal time step T. To complete the description of the algorithm, we provide the details about the scalarization.
4

---

Under review as a conference paper at ICLR 2022
Algorithm CollineRReOpl for Ymin
Inputs: Optimization oracle A.
2: Set r(m) = mm for E N.
3: for Episode m - 1, 1......00 .....dd do
4: Define (m)) according (5)
5: Compute policy 7m - A (mm))
6:
for Time = (m)),
(m + do
7:
Choose action a; = mm (8t).
8:
Observe the outcomes Vi(si, at) and the next state 81+1. f then
9:
10:
Break the for loops and terminate the algorithm.
11: end
12: end for
13:
end for
Scalarization by MWU. At time step t, we define the scalarization Dr {De, 1K
exp
T/t-1 Ej=l (s)(
02,k
(5)
- Ej=1 ()in(s),ag)
x= exp
where
Vlog K
9h-
max ((1 1)2/3,11
(6)
In particular, at the start of each episode m, we apply 5 with t (m)) in Line 4 For the case m I, we have & ((1)). 1/K for all k E (I,...,K) meaning that all reward types assigned with the same weight at the beginning. The exponent 2/3 in the learning rate 7r(m)- in 5 is different from the conventional choice of 1/2 (Arora et al. 2012). Our exponent is chosen for optimizing the resulting regret bound from our forthcoming analysis. We follow the approach in Chapter in (Orabona 2019) define time-varying learning rate.
The scalarization 0, by (5) promotes max-min fairness. Consider two reward types k, k' with E (tg (n)) > E (s a,). We have & > 0r,k. meaning that a higher weight is assigned to reward type k' than type k. This implies that there is a higher emphasis on increasing the type-k' reward, which is in shortage as compared type k, than the type-k reward. Hence, max- max-min faimess is promoted.
4.1 THEORETICAL GUARANTEES
We provide the following theoretical guarantee for Online-ReOpt.
Theorem Consider the RL-MMF problem. Online-Rede RROpt, displayed in Algorithm ! satisfies
114 K
144
Reg(T) <
T1/3
TB/3
where Dim B are parameters related to the optimization oracle A.
Theorem [ is generalization result, in the sense that it generalizes the ability of achieving near- the case of K
optimality for the case K the regret of the optimization oracle A diminishes with growing T any RL with scalar reward problem, the regret bound (7) in Theorem also tends to zero as T increases.
Indeed, as long / O, meaning that
Theorem D is proved in Appendix section The first regret term in 7 arises from two sources: (a) the regret of the MWU algorithm,
(b) the update delay on the scalanization due to the episodic structure. To elaborate (b), consider time step t in episode Recall that the scalarization 9, by (5) promotes max- fairness, and idcally we should have employed the policy returned by A(U,) time f. In contrast, in Online-ReOpt the action ag is determined by nns the output of A A(0

---

Under review as a conference paper at ICLR 2022
Item (b) accounts for the regret due using (r(m) rather then th. We crucially use the fact that th are slowly changing in t so that the resulting regret is still diminishing with t.
The second term in (7) is due to the regret of the optimization oracle A. The exponent 3/3 in the term
less than the exponent in 4 as each policy Tm is run for only 7(m 7(m+1))77m) - O ((v(mm)) many time steps. Our design of {Tmm) m= allows shorter time frame for 7m converge to its expected reward, as compared to running a policy for I"' steps in 4 When we increase the episode length 7 (m+ (mm)), the regret due to (b) increases, while the regret due the second term in ( decreases, and vice versa. Our design of {T(m) J.M. strikes an optimal (in terms of our analysis) balance between these two sources of regret.
The regret bound (7) does not feature direct dependence on the sizes of the state and action spaces. The dependence on the hardness of the underlying MDP is only reflected through the parameters Dii, 3. Therefore, apart from the deterioration of the exponent [3 to 3/3 and the first term in ( our algorithm does not introduce any overhead in the generalization from the case of K 1 to the case of K 1. Improving the exponent B/3 in 7 is interesting open question. Finally, Theorem [ is generalized to the case of maximizing a concave utility objective Eig(V where g is Lipschitz continuous and concave. We detail the generalization in the model, algorithm and theoretical results in Appendix C.I
4.2 OFFLINE VARIANTS TO OOLINE-REOPE
While the Online-Re Algorithm achieves near-optimality, the efficiency of its implementation could be hindered by the need of online computation in 5 Algorithm [ Indeed, in order to compute Tm, the agent has to input the optimization oracle A and the scalarization (m(()). which is only known at the end of time step 7(m) 1. the case when the optimization oracle involves heavy computation, for example training deep neural networks, such online computation may not be realistic.
In this section, we propose Offline-ReOpt, which is a variant of Online-ReOpp that does not require invoking during the horizon. The Offlin-Reeptii is obtained from the Online-ReOpp by modifying two lines in Algorithm [1 as enumerated below. The full algorithm of Offline-Redee ReOpt is provided in Appendix section A.
Replace the input of A Line with the input of the policy family 11 = {(0, 10,55 ( The index set Ω is a finite subset of (0 E l& ||01] 1, 2 0}. the collection of all possible scalarizations. For each 9 Ω the policy (1)) is the output of (
2. Replace the online computation in Line 5 with these two lines:
(a) Identify d-(m) E Ω2 that achieves minven ||0 (0(mm))l2
(b) Select policy Tm n. (0)0m))
In item (1), all the policies in II are computed before the execution of the algorithm, unlike the case in Online-ReOpt. Consequently, in item (2), the selection of policy nm does not require invoking the optimization oracle A.
The main idea behind item (2) is that, in the case when the desired scalarization (r(m) does not lie in Ω, chooses the surrogate scalarization á (mm) that is closest (7))) that the resulting policy o. (0, will be reasonable approximation to the desired policy (()))
In order for the surrogate ù (m(m)) to be close to (m))) it is desirable for the finite index set Ω to be so diverse that every scalarization dr(m) would be a close neighborhood of a scalarization in Q. We propose two families of Ω for the desired diversification. The first is the random point family, de- tailed in Appendix section A.2 The family is constructed by sampling random points in the domain (D E RK : | 1, 0 > 0f of all possible scalarizations. The second is the imitation based fam- ily, also detailed in Appendix section The family is constructed by first running Online ReOpt multiple times, then collecting the scalarizations and the corresponding policies generated.

---

Under review as a conference paper at ICLR 2022
5 EXPERIMENTS
We evaluate our proposed algorithms and benchmark algorithms in controlled queueing system involving vectorial rewards. For each of the algorithms, we first run the algorithm for Zpo Zun E independent trials, resulting in the 7po average vectorial reward plot the following three quantities against T::
(V (S
1 We
1 Ezn= =n= EE=1 Imin (v(tr:)) an estimate to E[gmin (V1.T)) ) Ex-post Fairness: V = Zn
Ex-ante Fairness: I' Σ
=1=1 Imin E (((2((
Zm
estimate Imin (v.))
Type rewards for each < K: E[Vi:r,)]
Zm -
1
bn
Ex=1
2
(( estimate 1:T,k
We define the upper and lower error bars respectively as the 75 and 25-percentiles of the data, see Appendix section B.1 for details. For the forthcoming discussions, we denote e₁ as the k-th standard basis vector for ko E ... K} in R In addition, we denote 1g. Oς as the all one vector and the all zero vector in RK
5.1 QUEUING NETWORK
Queuing problems are studied extensively due to their relevance in fields such as manufacturing and in communication systems. our evaluation, we focus on discrete-time qucuing system. The queuing network that we have tested our algorithms on, consisting of two servers and four queues arranged in a bidirectional fashion, has been previously studied in works by Rybko & Stolyar (992), Kumar & Seidman (1990), Chen & Meyn (998). de Farias & Van Roy 2003) and Banijamali al. (2019). This network is shown in Figure
Server 1
Server 2
Queue
Queue 2
-
Figure 2: A bi-directional four-queue network
There are servers in the system. Server 1 only serves Queue or Queue with service rates Ni = 0.3 and = 0.3 respectively, and where Server 2 similarly only serves Queue 2 or Queue the rates of μ/2 0.3 and μ4 = 0.3. Arrivals occur at a rate of X 0.2 and Xę 0.2 at Queues I and 3 respectively. An arrival that gets served at Queue by Server 1 then progresses to Queue 2, and only leaves the system after has been served by Server 2. Likewise, arrivals at Queue have to be served by Server 2, before moving on to Queue 4 to be served by Server in order to leave the system. Each queue has maximum length of L;- = 9, and a customer is rejected at a queue the queue is at its full capacity. Conversely, empty queue remains at length even if an action is taken to serve that queue.
The state of the system is thus defined by the vector æ; (F,,,,, 24,3, F2,4) whereby St,; rep- resents the length of the queue i at time t. At each time step f, decision has to be made by each server serve only one neither of its queues, which
represent by 4-component vector a, = (4,,1, ar,,, 0r,3, or,4) E {0, 134, where ar,; indicates the decision to serve Queue at time and a,,i 0 otherwise. Note that the condition of being able only serve one queue each server naturally imposes the constraints 4,,1 + 0,,4 S 1 and 0r,2 + 4,,3 S 1 at each t, meaning that
A, (a E 10, a1 + a4 & 1, 1, + 0g Σ 1} for each 8.
"To avoid clutter, we omit the upper-script for the algorithm.

---

Under review as a conference paper at ICLR 2022
The transition dynamies for the system then defined by the following equation when 0 21, Ti where refers to the basis vector in R
3t + E1
with probability A
2: + E3
with probability X2
3t +
with probability pidl
1t+1
31 e2
with probability #222
(8)
3t + e4
E3
with probability #3d3
2t
with probability padd
St
otherwise
We define the type-i reward at time as a) Z. for E {L...., 4]. Recall that æτ,i is queue length Queue time L. The reward Vz, a) equal to Queue is empty, and the reward V a) decreases linearly with the length of Queue at time L. In particular, (1, a) = 0 Queue i full. Altogether, the agent's ' reward for Queue i at time positively correlates with the degree of idleness of the Queue. The maximization of 9min (Vi.r) to the minimization of tmmerveergee queue lengths among all queues, hence enforcing all queues to be stable simultaneously.
=
gisa Vi.r,a is equivalent
5.1.1 SIMULATION RESULTS
In our simulation, we evaluate 5 algorithms. Three of them are our proposed algorithms, namely Online-ReOpt, Offtine-ReOpt with Random Point Family and Offline-ReOpt with Imitation based family. The other two are existing baselines. The Meta Algorihtm by Zahavy al. (202T) is the state-of-the-art for maximizing 9min (min(EVVa [V.])) while the longer queue first hcuristic is a well- established algorithm in the queuing theory literature. As the name suggests, each server serves the longer of the two queues at each time round. We ran each of the algorithms with the following parameters: T 100000, Zan 10 and = 100, meaning Zpo Zun gorithms employ the same optimization oracle A, with the same hyper-parameters and architecture, double deep Q-learning network algorithm (Double DQN) by Hasselt et al. (2016).
1000 3 All of the al-
4x-0--
3x30
With
Qunun Nouness
2x:30
200
101
20
Figure Ex-ante Fairness of various algorithms queuing network
Figure plots the quantity T against T under the 5 algorithms. Notice in Figure how the Of- fline and Online-ReOpt algorithms, well the Meta Algorithm by Zahavy al. (2021) perform similarly well in terms of ex-ante fairness. Among them, the Meta Algorithm has the best perfor- mance, since the Re-Optimization schedule in proposed algorithms compromises the ex-ante fairness objective. All algorithms demonstrate converging behavior, in the sense that the error bars diminishes T grows.
Except for Online-ReOOp where set E\t 5 since running an online algorithm for 1000 trials is not as practical running offline algorithm, which only needs be trained once.
8

---

Under review as a conference paper at ICLR 2022
Yfl lelppt diaddion Prei Kon Ry
6x400
3ffino leOpt dwatriis Rocnd Rerig) 2ed ne-laost
<dla Mgaiitii (Taleey 30211
.argr Pee Heuroo:
4x30
3x.00
Figure 4: Ex-post Fairness of various algorithms in queuing network
Figure 4 plots the quantity I against T under the 5 algorithms. In terms of ex-post fairness, the Of- fline and Maline-Reopp algorithms perform significantly better than Meta Algorithm and the Longer Queue First Heuristic. The sub-optimality of the Meta Algorithm corroborates with Section 3.2 that policies designed for the ex-ante fairness objective could be far from optimal for the ex-post fairness objective. While the Meta Algorithm has similar performance to the Longer Queue First heuristic, the former has significantly wider error bar than the latter, meaning that the latter is more stable.
Mery'
1-13-
1319
2400
Figure 5: Type k-rewards for 1 < k < K of various algorithms in a queuing network. Figure is read from left to right, top to bottom.
Figure plots 4; against T' for i E {l..... 4}. In a nutshell, the plotted lines explain the trends in Figure while the error bars shed light on the trends Figure Firstly, the plotted lines indicate that the Meta Algorithm has the highest (or close to the highest) individual average reward o; for each queue, signifying that the Meta Algorithm has the highest E[V for each i fl....,44 4).
This explains the superiority of the Meta Algorithm shown in Figure 3
When we focus on the error bars, the plots in 3 different story. Notably, the error bars for the Meta Algorithm is significantly wider than others, meaning that the Zpo trials of the Meta Algorithm have significantly different results from one another When we unpack the summands .,,..., 24 and compute the minimum reward each trial, it results Figure which is vastly different from Figure 3, signifying the ex-ante and ex-post objectives are fundamentally different.
As a final remark, our numerical experiments do not imply that the Longer Queue Heuristic is worse algorithm than the other 4 algorithms. Indeed, the Longer Queue Heuristic does not require the knowledge of 'y A2, Pi...., (44, whereas the other algorithms crucially uses these parameters for generating their policies. In addition, the Longer Queue Heuristic is computationally much less onerous than the others. Finally, the Longer Queue Heuristic demonstrates converging behaviors in all the plots, in the sense that the error bars diminish when T increases.
*It is helpful to revisit Section 3.2 where Zpo trials would result in ss Zpo/2 outcomes of (1-1/p) and 7pp/2 outcomes of (1-1/T).

---

Under review as a conference paper at ICLR 2022
REFERENCES
E. Altman. Constrained Markov Decision Processes. Chapman and Hall, 1999.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory of Computing. 8(6):211-16, 2012.
Ershad Banijamali, Yasin Abbasi-Yadkori, Mohammad Ghavamzadeh, and Nikos Vlassis. Optimiz- ing over restricted policy class in mdps. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89, pp. 3042-3050. PMLR, 16-18 Apr 2019.
Leon Barrett and Srini Narayanan. Learning all optimal policies with multiple criteria. In Proceed- ings of the 25th International Conference on Machine Learning, ICML '08, pp. 41-47, New York, NY, USA. 2008. Association for Computing Machinery. ISBN 978 9781605582054. doi: 10.1145/1390156. 1390162. BtLLttts::// http://oiiooo//g/////// org/10..//.o.oo.oooo.oo.. 111.11144/11.11990000
Kianté Brantley, Miroslav Dudík, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Alek- sandrs Slivkins, and Wen Sun. Constrained episodic reinforcement learning concave-convex and knapsack settings, In Advances in Neural Information Processing Systems 33, 2020.
R.-R. Chen and S. Meyn. Value iteration and optimization of multiclass queueing networks. In Pro- ceedings of the 37th JEEE Conference on Decision and Control (Cat. No. No.98CH36/71), volume 1, pp. 50-55 1,l.1, 1, 1998. doi: 10.1109/CDC. 1998768889998.878888888888888881 760588.
Wang Chi Cheung. Regret minimization for reinforcement learning with vectorial feedback and complex objectives. In Advances in Neural Information Processing Systems 32, pp. 724-734, 2019.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained rein- forcement learning with percentile risk criteria. J. Mach. Learn. Res., 18(1)=6070-6100, January 2017. ISSN 1532-4435.
D. P. de Farias and B. Van Roy. The linear programming approach approximate dynamic pro- gramming. Operations Research, (6):8500-865, 2003.
Zoltán Gábor, Zsolt Kalmár, and Csaba Szepesvári. Multi-criteria reinforcement learning. In Pro-
ceedings of the Fifteenth International Conference on Machine Learning, ICML '98. pp. 197-205, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc. ISBN 1558605568.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI' 16, pp. 2094-2100. AAAI Press, 2016.
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum en- tropy exploration. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 2681-2691. PMLR, 09-15 Jun 2019.
P.R. Kumar and T.I. Seidman. Dynamic instabilities and stabilization methods in distributed real- time scheduling of manufacturing systems. IEEE Transactions on Automatic Control, 35(3): 289-298, 1990. doi: 10.1109/9.50339,
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Pro- ceedings of the 36th International Conference on Machine Learning, volume 97, pp. 3703-3712. PMLR, 09-15 Jun 2019.
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhut- dinov. Efficient exploration via state marginal matching. CoRR, abs/1906.05274, 2019. URL
http:/ http///wwivv...aaa..a////
05274
Yongshuai Liu, Jiaxin Ding, and Xin Liu. Ipo: Interior-point policy optimization under con- straints. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04))4940-494) Apr. 2020. doi: 10. wwtp0///a..334.4...... URL hattps://o// aaai. www.orrgg............o php/
AAAT SOAT/articlo
10

---

Under review as a conference paper at ICLR 2022
Shie Mannor and Nahum Shimkin. A geometric approach to multi-criterion reinforcement learning. J. Mach. Learn. Res., 5:325- 360, 2004.
Sobhan Miryoosefi, Kianté Brantle,, Hal Daume III, Miro Dudik, and Robert E Schapire. Reinforce- ment learning with convex constraints. In Advances in Neural Information Processing Systems 32, pp. 14093-14102. 2019.
Francesco Orabona. A modern introduction to online learning. CoRR, 0tts/1912.132133 2019.
A. N. Rybko and Alcksandr Stolyar. On the ergodicity of stochastic processes describing functioning of open queueing networks. Problemy Peredachi Informatsii, (3):3-26, July 1992. ISSN 0555- 2923.
Shai Shalev-Shwartz. Online learning: Theory, algorithms, and applications, Jul 2007.
Shai Shalev- Shalrr-Shwartz. Online learning and online convex optimization. Found. Trends Mach. Learn., 4(2):107-194 2012.
Jean Tarbouriech and Alessandro Lazaric. Active exploration in markov decision processes. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, volume 89, pp. 974-982 PMLR, 2019.
Chen Tessler, Daniel J. Mankowitz, and Shie Mannor. Reward constrained policy optimization. In International Conference on Learning Representations, 2019.
Kristof Van Moffaert and Ann Nowé. Multi-objective reinforcement learning using sets of pareto dominating policies. J. Mach. Learn. Res., 15(1):3483-3512, January 2014. ISSN 1532-4435.
Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps. ArXiv, abs/2106.00661, 2021.


Reviews:
[{"review_id": "tgCpwGI1pgZ", "reviewer": "Reviewer_gzxW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "1. Some important related papers need reference: https://arxiv.org/pdf/1909.02940.pdf which seems to solve similar problem. \n2. Note that even though the E[min] and min(E) are shown to be different in an example, the gap is O(1/T), and not really relevant to the problem of regret. Thus, I believe that the algorithm of ex-ante will give the ex-post result with similar regret. \n3. Based on the above, it is unclear why the above paper approach where MDP is estimated using Dirichlet/optimistic sampling and a model based optimization is applied do not work in this setup? As T goes large, E[min] and min(E) will be similar and have gap of O(1/\\sqrt{T}) and can be quantified giving an additional regret term, but other than that, most analysis will be re-used. \n4. The novelty in the approach needs better discussions. \n5. The regret bounds are sub-optimal. Given that oracle for linear reward problem will have \\beta = 1/2, the regret is T^{5/6} which is very large when the model-based algorithms can achieve T^{1/2}. ", "summary_of_the_paper": "This paper considers ex-post max-min fairness, where an RL algorithm is provided with provable guarantees. The difference between ex-ante and ex-post are explained. ", "summary_of_the_review": "The key issue in the paper is the in-efficient regret bound, and the approach novelty needs better explanations. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nboLWc4sq_L", "reviewer": "Reviewer_bwVS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "**Strength:** The problem studied is interesting and well-motivated. The paper also clearly illustrated the difference between ex-ante and ex-post optimizations. The main algorithm presented has a theoretical regret bound. The paper is clearly written overall.\n\n**Weakness:** The main techniques seem to rely on the work of Zahavy et al. (Reward is Enough for Convex MDPs), especially the generalization to concave minimization. Hence, the work looks somewhat incremental from a technical point of view. The authors may want to stress the difference between their work and that of Zahavy et al in the paper and highlight the original contribution. That said, the application of these techniques to the maximin problem is still very interesting.   \n\nThere is one technical question, which might be critical and I hope the authors could clarify: I do not see how Aogrithm 1 avoids getting stuck in a sink state that is undesirable for some reward types. For example, in Figure 1, if there is an additional state $s'$, connected by an arc from $s^o$ and with a self loop generating the same rewards as the self loop at $s^l$; nevertheless, from $s'$ no other states can be reached. In this case, a policy that always seeks to transit to $s'$ and loops there indefinitely is also optimal w.r.t. the second dimension of the reward. Therefore, the oracle $\\Lambda$ may well pick this policy in the first episode, but if this is the case, the agent would loop at $s'$ in the subsequent episodes, obtaining reward $0$ for the first dimension. I wonder how the regret could diminish in this case? Is some assumption of ergodicity relevant here? I don't find any in the paper though. \n\n**Minor comments and suggestions:**\n\nA typo: Right above Section 4: \"...allows does not require...\"\n\nThe figures in the experiment section could be arranged in a better way. They all look overly wide, and those in Figure 5 too small to read. If the space is a concern, I'd sugget putting Figures 3 and 4 side by side to save space for Figure 5.", "summary_of_the_paper": "The paper studies an RL problem, where the rewards are given as a vector at each time step. The goal is to find a policy that balances the total rewards on different dimensions of the reward vector, i.e., one that maximizes the total reward of the worst dimension. More specifically, the paper takes an ex-post perspective and presents an online algorithm that achieves near optimality. An offline variant of this online algorithm is also proposed to alleviate the heavy cost of online computation in some applications. The authors also conducted experiments to evaluate the proposed algorithms.", "summary_of_the_review": "The ex-post maximin fairness problem is interesting and well-motivated. The authors made an effort to develop an algorithm to solve the problem, which looks somewhat incremental from a technical point of view given an existing result by Zahavy et al. (Reward is Enough for Convex MDPs). There is a potential technical issue (see Main Review) which I hope the authors could clarify.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QabIFiPDlNK", "reviewer": "Reviewer_SQsM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strengths:\n1. The authors provide both theorectical analysis and empirical experiments. In the analysis, they use multiplicative weight update to ensure the max-min fairness. In the numerical experiments, the proposed algorithm outperforms previous algorithms significantly.\n\n\nWeaknesses:\n1. The intuition of ex-post max-min fairness is not clear. The authors try to show difference between ex-ante max-min fairness and ex-post max-min fairness. However, the two problems are almost the same for weak communicating MDPs. In weak communicating MDPs,  for any policy $\\pi$, by running $\\pi$ for $T$ steps, $||\\bar{V}_{1:T}-E[\\bar{V}^{\\pi}]||$ is bounded by $\\tilde{O}(K\\sqrt{D/T})$ with high probability, where $V^{\\pi}$ is the expected average reward of $\\pi$ and $D$ is the diameter. The proposed counter example is a non-communicating MDP, which is less important in both theorectical analysis and practical problems (in general, we deal with non-communicating MDPs by dividing it into several weak communicating parts).\n\n2. The requirement of the proposed algorithm is too strong. Online-ReOpt needs to take an oracle to compute a near-optimal policy for any  scalar reward as a subrountine. In general, by online learning it cost $O(SAD/\\epsilon^2)$ to learn an $\\epsilon$-optimal policy in the worst case. Although it is possible to add a subroutine to learn such a policy, it would worse the final regret considering the current regret bound is quite poor.", "summary_of_the_paper": "The paper considers RL problem with a vectorial reward of $K$ dimension. The authors consider to maximize the minimal value function $\\mathbb{E}[g_{min}(\\bar{V}_{1:T})]$ and achieve a regret bound of $O(\\sqrt{logK}T^{\\frac{2}{3}})$ given an oracle to solve the RL problem with scalar reward. The authors also discuss the offline variant of the proposed algorithm. Finally, the authors verify their algorithm with a queuing system.", "summary_of_the_review": "Overall the paper is well written and easy to read. However, given the concerns above, I tend to reject it.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JI2Oa-AgcKP", "reviewer": "Reviewer_oTCf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "First, the paper is well-written and I really enjoy reading the work. \nThe paper proposes a new objective and an asymptotic optimal algorithm. The presentation is clear and intuitive, and the analysis is also very clean. \n\nI mainly have two concerns:\n(i) The motivation for the ex-post objective: The paper provides an example (Section 3.2) to illustrate the difference between ex-post and ex-ante policies. I like the example, but I still don't feel convinced about the necessity of the ex-post objective. Say, if we adopt a linear objective with equal weight or a CVaR objective to the two rewards for this example, would we end up with the same optimal policy as the ex-post? I think it would be great if the author(s) can construct an example, for which the optimal policy of the ex-post objective cannot be recovered by other existing objective functions, like the linear, ex-ante, CVaR, etc. In this sense, it means the ex-post objective provides us with a different class of risk-sensitive/fair policies.\nAlso, from a practical perspective, the numerical experiments should compare the time spent by the two classes of customers in the system, rather than the waiting time for each of the four queues. For instance, customer type 1 may care more about the sum of (rather than each of) the waiting times before Queue 1 and Queue 2. And for fairness purposes, we might want to max-min {Q1 Waiting + Q2 Waiting, Q3 Waiting + Q4 Waiting}. I am not sure if this would complicate the problem setup significantly. Please correct me if I misunderstood the setup here. \n\n(ii) Knowledge of the underlying dynamics (reward and transition): The oracle used by the algorithm requires the knowledge of the underlying reward and transition, at least some estimates of them. Strictly speaking, due to this requirement, I wouldn't call the setup of the paper \"RL\" but more of an MDP or stochastic dynamic programming. It seems to me that this requirement is necessary for both the algorithm and the analysis. I wonder whether asymptotic optimality can still be obtained if we don't have this knowledge. For example, if we replace the true probabilities/rewards in the oracle as their empirical estimates based on the samples observed so far in the online algorithm, my hunch is that the performance guarantee will no longer hold. ", "summary_of_the_paper": "The paper considers the ex-post max-min objective for the vector reward RL problem. The paper provides a simple example to illustrate the difference between ex-ante and ex-post objectives. An MWU-based algorithm is proposed to solve the problem with a provable regret guarantee, where the algorithm resorts to an approximately optimal policy oracle episodically. The algorithm also features a variant that can fully rely on offline solutions. Numerical experiments on a classic queue control problem demonstrate the performance of the algorithm against two existing benchmarks. ", "summary_of_the_review": "Overall, as mentioned above, I think the paper is very elegant. I would look forward to hearing the author(s) comments on my two concerns above. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies an RL problem with vector rewards, where the goal is to maximize the expected minimum total reward (ex-post max-min fairness). This is different from prior works on a similar topic, where the goal is to maximize the minimum expected total reward (ex-ante max-min fairness). The authors propose an algorithm for solving the problem with $O(T^{2 / 3})$ regret and evaluate it.

This paper received two borderline reject and two reject reviews. The reviewers recognize the novelty of the objective. However, they are also concerned with its motivation and that the proposed algorithm relies on strong assumptions, such as that the used oracle knows the underlying reward and transition models, or at least has some estimate of them. At the end, the scores of this paper are not good enough for acceptance. Therefore, it is rejected.
Decision: Reject