Year: 2021

Abstract:
We consider reinforcement learning with vectorial rewards, where the agent receives a vector of K ≥ 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. ex-ante max-min fairness, we maximize the expected minimum total reward, i.e. 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.

text: We consider reinforcement learning with vectorial rewards, where the agent receives a vector of K ≥ 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. ex-ante max-min fairness, we maximize the expected minimum total reward, i.e. 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.

heading: 1 INTRODUCTION
text: The prevailing paradigm in reinforcement learning (RL) concerns the maximization of a single scalar reward. On one hand, optimizing a 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, a suitable choice of the linear combination is often not clear a priori.
In this work, we consider the reinforcement learning with max-min fairness (RL-MMF) problem. The agent accumulates a vector of K ≥ 1 time-average rewards V̄1:T = (V̄1:T,k)Kk=1 ∈ RK in T time steps, and aims to maximize E[mink∈{1,...,K} V̄1:T,k]. The maximization objective represents ex-post max-min fairness, in contrast to the objective of ex-ante max-min fairness by maximizing mink∈{1,...,K} E[V̄1:T,k].
Our main contributions are the design and analysis of the Online-ReOpt algorithm, which achieves near-optimality for the ex-post max-min fairness objective. More specifically, the objective under Online-ReOpt converges to the optimum as T increases. Our algorithm design involves a novel adaptation of the multiplicative weight update method (Arora et al., 2012), in conjunction with a 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 fairness objectives, by showing that an optimal algorithm for the former needs not converge to the optimality even when T increases. Finally, our results are extended to the case of maximizing E[g(V̄1:T )], where g is a Lipschitz continuous and concave reward function.

heading: 2 RELATED WORKS
text: 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 g(E[V̄1:T ]), as well as its exante variants, including the long term average variant g(E[limT→∞ V̄1:T ]) and its infinite horizon discounted reward variant. The function g : RK → 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-Risk objective. Hazan et al. (2019) study the case when g 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 to the uniform distribution as possible. Miryoosefi et al. (2019) study the case of minimizing the distance between E[V̄1:T ] and a target set in RK . Lee 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̄1:T ] and its ex-ante variants are studied in (Mannor & Shimkin, 2004; Gábor et al., 1998; Barrett & Narayanan, 2008; Van Moffaert & Nowé, 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(E[V̄1:T ]) and its ex-ante variants, where g is concave and Lipschitz continuous. Our contributions, which concern the ex-post max-min fairness E[mink∈{1,...,K} V̄1:T,k] 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 Section 3.2.
Additionally, a body of works Altman (1999); Tessler et al. (2019); Le et al. (2019); Liu et al. (2020) study the setting where g is a linear function, subject to the constraint that E[V̄1:T ] (or its ex-ante variants) is contained in a convex feasible region, such as a polytope. There is another line of research works Tarbouriech & Lazaric (2019); Cheung (2019); Brantley et al. (2020) focusing on various online settings. The works Tarbouriech & Lazaric (2019); Cheung (2019) focus on the ex-post setting like ours, but they crucially assume that the underlying g 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 to 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.

heading: 3 MODEL
text: Set up. An instance of the Reinforcement Learning with Max-Min Fairness (RL-MMF) problem is specified by the tuple (S, s1,A, T,O). The set S is a finite state space, and s1 ∈ S is the initial state. In the collection A = {As}s∈S , the set As contains the actions that the agent can take when he is at state s. Each set As is finite. The quantity T ∈ N is the number of time steps. When the agent takes action a ∈ As at state s, he receives the array of stochastic outcomes (s′, U(s, a)), governed by the outcome distribution O(s, a). For brevity, we abbreviate the relationship as (s′, U(s, a)) ∼ O(s, a). The outcome s′ ∈ S is the subsequent state he transits to. The outcome U(s, a) = (Uk(s, a))Kk=1 is a random vector lying in [−1, 1]K almost surely. The random variable Uk(s, a) is the amount of type-k stochastic reward the agent receives. We allow the random variables s′, U1(s, a), . . . UK(s, a) to be arbitrarily correlated.
Dynamics. At time t ∈ {1, . . . T}, the agent observes his current state st. Then, he selects an action at ∈ Ast . After that, he receives the stochastic feedback (st+1, Vt(st, at)) ∼ O(st, at). We denote Vt(st, at) = (Vt,k(st, at)) K k=1, where Vt,k(st, at) is the type-k stochastic reward received at time t. The agent select the actions {at}Tt=1 with a policy π = {πt}Tt=1, which is a collection of functions. For each t, the function πt inputs the history Ht−1 = ∪t−1q=1{sq, aq, Vq(sq, aq)} and the current state {st}, and outputs at ∈ Ast . We use the notation aπt to highlight that the action is chosen under policy π. A policy π is stationary if for all t,Ht−1, st it holds that πt(Ht−1, st) = π̄(st) for some function π̄, where π̄(s) ∈ As for all s. With a slight abuse of notation, we identify a stationary policy with the function π̄.
Objective. We denote V̄ π1:t = 1t ∑t q=1 Vq(sq, a π q ) as the time average vectorial reward during time 1 to t under policy π. The agent’s over-arching goal is to design a policy π that maximizes E[gmin(V̄ π1:T )], where gmin : RK → R is defined as gmin(v) = mink∈{1,...,K} vk. Denoting V̄ π1:T,k as the k-th component of the vector V̄ π1:T , the value gmin(V̄ π 1:T ) = mink V̄ π 1:T,k is the minimum time average reward, among the reward types 1, . . . ,K. The function gmin is concave, and is 1-Lipschitz w.r.t. ‖ · ‖∞ over the domain RK . When K = 1, the RL-MMF problem reduces to the conventional RL problem with scalar reward maximization. The case of K > 1 is more subtle. Generally, the optimizing agent needs to focus on different reward types in different time steps, contingent upon the amounts of the different reward types at the current time step. Since the max-min fairness objective could lead to an intractable optimization problem, we aim to design a near-optimal policy for the RL-MMF problem.

heading: 3.1 REGRET
text: We quantify the near-optimality of a policy π by the notion of regret, which is the difference between a benchmark opt(P(gmin)) and the expected reward E[gmin(V̄ π1:T )]. Formally, the regret of a policy π in a T time step horizon is
Reg(π, T ) = opt(P(gmin))− E[gmin(V̄ π1:T )]. (1)
The benchmark opt(P(gmin)) is a fluid approximation to the expected optimum. To define opt(P(gmin)), we introduce the notation p = {p(s′|s, a)}s∈S,a∈As , where p(s′|s, a) is the probability of transiting to s′ from s, a. In addition, we introduce v = {v(s, a)}s∈S,a∈As , where v(s, a) = E[U(s, a)] is the vector of the K expected rewards. The benchmark opt(P(gmin)) is the optimal value of the maximization problem P(gmin). For any g : RK → R, we define
P(g): max x g  ∑ s∈S,a∈As v(s, a)x(s, a)  s.t.
∑ a∈As x(s, a) = ∑ s′∈S,a′∈As′ p(s|s′, a′)x(s′, a′) ∀s ∈ S (2a)
∑ s∈S,a∈As x(s, a) = 1 (2b)
x(s, a) ≥ 0 ∀s ∈ S, a ∈ As. (2c)
The concave maximization problem P(gmin) serves as a fluid relaxation to RL-MMF. For each s ∈ S, a ∈ As, the variable x(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 a state s is equal to the rate of transiting into the state s for each s ∈ S , while the sets of constraints (2b , 2c) require that {x(s, a)}s∈S,a∈As forms a probability distribution over the state-action pairs. Consequently, opt(P(gmin)) is an asymptotic (in T ) upper bound to the expected optimum.
Our goal is to design a policy π such that its regret1 Reg(T ) satisfies
Reg(T ) = opt(P(gmin))− E[gmin(V̄ π1:T )] ≤ D
T γ (3)
holds for all initial state s1 ∈ S and all T ∈ N, with parameters D, γ > 0 independent of T . We assume the access to an optimization oracle Λ, which returns a near-optimal policy given any scalar reward. For ϑ ∈ RK , define the linear function gϑ : RK → R as gϑ(w) = ϑ>w = ∑K k=1 ϑkwk. The oracle Λ inputs ϑ ∈ RK , and outputs a policy π satisfying
opt(P(gϑ))− E[gϑ(V̄ π1:T )] = opt(P(gϑ))− E[ϑ>V̄ π1:T ] ≤ Dlin T β
(4)
for all initial state s1 ∈ S and all T ∈ N, with parameters Dlin, β > 0 independent of T . By assuming β > 0, we are assuming that the output policy π is near-optimal, in the sense that the difference opt(P(gϑ))− E[ϑ>V̄ π1:T ] converges to 0 as T tends to the infinity. A higher β signifies a
1We omit the notation with π for brevity sake
faster convergence, representing a higher degree of near-optimality. We refer to ϑ as a scalarization of v, with the resulting scalarized reward being ϑ>v(s, a) for each s, a.
Our algorithmic frameworks involve invoking Λ as a sub-routine on different ϑ’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 fairness (the case of K ≥ 1). Finally, while the main text focuses on gmin, our algorithm design and analysis can be generalized to the case of concave g, as detailed in Appendix C.
3.2 COMPARISON BETWEEN MAXIMIZING E[gMIN(V̄ π1:T )] AND gMIN(E[V̄ π1:T ])
Before introducing our algorithms, we illustrate the difference between the objectives of maximizing E[gmin(V̄ π1:T )] and gmin(E[V̄ π1:T ]) by the deterministic instance in Figure 1, with initial state s1 = so.
)(00)( ( )
The figure depicts an instance with K = 2. An arc represents an action that leads to a transition from its tail to its head. For example, the arc from so to s` represents the action ao`, with p(s` | so, ao`) = 1. Likewise, the loop at s` represents the action a`` with p(s` | s`, a``) = 1. Each arc is labeled with its vectorial reward, which is deterministic. For example, with certainty we have V (so, ao`) = ( 0 0 ) and V (s`, a``) = ( 0 1 ) .
Consider two stationary policies π`, πr, defined as π`(sr) = aro, π`(so) = ao`, π`(s`) = a`` and πr(sr) = arr, πr(so) = aor, πr(s`) = a`o. The policy π` always seeks to transit to s`, and then loop at s` indefinitely, likewise for πr. With certainty, V̄ π ` 1:T = ( 0 1−1/T ) , V̄ π r 1:T = ( 1−1/T 0 ) .
The objective gmin(E[V̄ π1:T ]) is maximized by choosing πran uniformly at random from the collection {π`, πr}. We have E[V̄ πran1:T ] = ( 1/2−1/(2T ) 1/2−1/(2T ) ) , leading to the optimal value of 1/2 − 1/(2T ). More generally, existing research focuses on maximizing g(E[V̄ π1:T ]) for certain concave g, and the related objectives of maximizing g(limT→∞ E[V̄ π1:T ]) or g(E[ ∑∞ t=1 α tVt(st, a π t )]), where α ∈ (0, 1) is the discount factor. In these research works, a near-optimal policy π is constructed by first generating a collection Π of stationary policies, then sampling π uniformly at random from Π.
Interestingly, πran is sub-optimal for maximizing E[gmin(V̄ π1:T )]. Indeed, Pr(V̄ πran 1:T =
( 0 1−1/T ) ) =
Pr(V̄ πran1:T = ( 1−1/T 0 ) ) = 1/2, so we have E[gmin(V̄ πran1:T )] = 0 for all T . Now, consider the deterministic policy πsw, which first follows π` for the first bT/2c time steps, then follows πr in the remaining dT/2e time steps. We have V̄ πsw1:T,k ≥ 1/2 − 2/T for each k ∈ {1, 2}, meaning that gmin(V̄ πsw 1:T ) ≥ 1/2− 2/T . Note that gmin(E[V̄ πsw 1:T ]) ≥ gmin(E[V̄ πran 1:T ])− 2/T , so the policy πsw is also near-optimal for maximizing gmin(E[V̄ π1:T ]).
Altogether, an optimal policy for maximizing gmin(E[V̄ π1:T ]) can be far from optimal for maximizing E[gmin(V̄ π1:T )]. In addition, for the latter objective, it is intuitive to imitate πsw, which is to partition the horizon into episodes and run a suitable stationary policy during each episode. A weakness to πsw is that its partitioning requires the knowledge on T . While our algorithm follows the intuition to imitate πsw, we propose an alternate partitioning that allows does not require T as an input.

heading: 4 ONLINE-REOPT ALGORITHM FOR RL-MMF
text: We propose the Online-ReOpt algorithm, displayed in Algorithm 1. The algorithm runs in episodes. An episode m ∈ {1, 2, . . .} starts at time τ(m) (defined in Line 2), and ends at time τ(m+ 1)− 1. Before the start of episode m, the algorithm computes the scalarization ϑτ(m) based on the Multiplicative Weight Update (MWU), which we detail later. Then, the algorithm invokes the optimization oracle Λ, which returns a policy πm that is near-optimal for the MDP with scalar rewards rm = {rm(s, a)}s,a, where rm(s, a) = ϑ>τ(m)v(s, a). Note that we only assume a black-box access to Λ, and the parametersDlin, β do not need to be input to the Algorithm. Finally, the algorithm runs policy πm during episode m. The Online Re-Opt algorithm is an anytime algorithm, since it does not require T as an input. Rather, it requires knowing T only during the terminal time step T . To complete the description of the algorithm, we provide the details about the scalarization.
Algorithm 1 Online-ReOpt for gmin 1: Inputs: Optimization oracle Λ. 2: Set τ(m) = bm3/2c for m ∈ N. 3: for Episode m = 1, 2, . . . do 4: Define ϑτ(m) according to (5). 5: Compute policy πm ← Λ(ϑτ(m)). 6: for Time t = τ(m), . . . , τ(m+ 1)− 1 do 7: Choose action at = πm(st). 8: Observe the outcomes Vt(st, at) and the next state st+1. 9: if t = T then 10: Break the for loops and terminate the algorithm. 11: end if 12: end for 13: end for
Scalarization by MWU. At a time step t, we define the scalarization ϑt = {ϑt,k}Kk=1 as
ϑt,k = exp
[ −ηt−1 ∑t−1 j=1 Vj,k(sj , aj) ] ∑K κ=1 exp [ −ηt−1 ∑t−1 j=1 Vj,κ(sj , aj)
] , (5) where
ηt−1 =
√ logK
max{(t− 1)2/3, 1} . (6)
In particular, at the start of each episode m, we apply (5) with t = τ(m) in Line 4. For the case m = 1, we have ϑτ(1),k = 1/K for all k ∈ {1, . . . ,K}, meaning that all reward types are assigned with the same weight at the beginning. The exponent 2/3 in the learning rate ητ(m)−1 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 7 in (Orabona, 2019) to define a time-varying learning rate. The scalarization ϑt by (5) promotes max-min fairness. Consider two reward types k, k′ with∑t−1 q=1 Vq,k(sq, aq) > ∑t−1 q=1 Vq,k′(sq, aq). We have ϑt,k′ > ϑt,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 to type k, than the type-k reward. Hence, max-min fairness is promoted.

heading: 4.1 THEORETICAL GUARANTEES
text: We provide the following theoretical guarantee for Online-ReOpt.
Theorem 1 Consider the RL-MMF problem. Online-ReOpt, displayed in Algorithm 1, satisfies
Reg(T ) ≤ 114 √ logK
T 1/3 + 144Dlin T β/3 , (7)
where Dlin, β are parameters related to the optimization oracle Λ.
Theorem 1 is a generalization result, in the sense that it generalizes the ability of achieving nearoptimality for the case of K = 1 to the case of K ≥ 1. Indeed, as long as β > 0, meaning that the regret of the optimization oracle Λ diminishes with a growing T on any RL with scalar reward problem, the regret bound (7) in Theorem 1 also tends to zero as T increases.
Theorem 1 is proved in Appendix section C.3. The first regret term in (7) arises from two sources: (a) the regret of the MWU algorithm, (b) the update delay on the scalarization due to the episodic structure. To elaborate on (b), consider a time step t in episodem. Recall that the scalarization ϑt by (5) promotes max-min fairness, and ideally we should have employed the policy returned by Λ(ϑt) at time t. In contrast, in Online-ReOpt the action at is determined by πm, the output of Λ(ϑτ(m)).
Item (b) accounts for the regret due to using ϑτ(m) rather then ϑt. We crucially use the fact that ϑt 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 Λ. The exponent β/3 in the term is less than the exponent β in (4), as each policy πm is run for only τ(m+1)− τ(m) = O( √ τ(m)) many time steps. Our design of {τ(m)}Mm=1 allows a shorter time frame for πm to converge to its expected reward, as compared to running a policy for T steps in (4). When we increase the episode length τ(m+1)−τ(m), the regret due to (b) increases, while the regret due to the second term in (7) decreases, and vice versa. Our design of {τ(m)}Mm=1 strikes an optimal (in terms of our analysis) balance between these two sources of regret.
The regret bound (7) does not feature a 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 Dlin, β. Therefore, apart from the deterioration of the exponent β to β/3 and the first term in (7), 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 β/3 in (7) is an interesting open question. Finally, Theorem 1 is generalized to the case of maximizing a concave utility objective E[g(V̄ π1:T )], where g is Lipschitz continuous and concave. We detail the generalization in the model, algorithm and theoretical results in Appendix C.1.

heading: 4.2 OFFLINE VARIANTS TO ONLINE-REOPT
text: While the Online-ReOpt Algorithm achieves near-optimality, the efficiency of its implementation could be hindered by the need of online computation in Line 5 in Algorithm 1. Indeed, in order to compute πm, the agent has to input the optimization oracle Λ and the scalarization ϑτ(m), which is only known at the end of time step τ(m) − 1. In 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-ReOpt that does not require invoking Λ during the horizon. The Offline-ReOpt is obtained from the Online-ReOpt by modifying two lines in Algorithm 1, as enumerated below. The full algorithm of Offline-ReOpt is provided in Appendix section A.1.
1. Replace the input of Λ in Line 1 with the input of the policy family Π = {(ϑ, π(ϑ))}ϑ∈Ω. The index set Ω is a finite subset of {ϑ ∈ RK : ‖ϑ‖1 = 1, ϑ ≥ 0}, the collection of all possible scalarizations. For each ϑ ∈ Ω, the policy π(ϑ) is the output of Λ(ϑ).
2. Replace the online computation in Line 5 with these two lines:
(a) Identify ϑ̃τ(m) ∈ Ω that achieves minϑ∈Ω ∥∥ϑ− ϑτ(m)∥∥1 .
(b) Select policy πm = π(ϑ̃τ(m)).
In item (1), all the policies in Π are computed before the execution of the algorithm, unlike the case in Online-ReOpt. Consequently, in item (2), the selection of policy πm does not require invoking the optimization oracle Λ.
The main idea behind item (2) is that, in the case when the desired scalarization ϑτ(m) does not lie in Ω, we chooses the surrogate scalarization ϑ̃τ(m) that is closest to ϑτ(m), so that the resulting policy π(ϑ̃τ(m)) will be a reasonable approximation to the desired policy π(ϑτ(m)).
In order for the surrogate ϑ̃τ(m) to be close to ϑτ(m), it is desirable for the finite index set Ω to be so diverse that every scalarization ϑτ(m) would be in a close neighborhood of a scalarization in Ω. We propose two families of Ω for the desired diversification. The first is the random point family, detailed in Appendix section A.2. The family is constructed by sampling random points in the domain {ϑ ∈ RK : ‖ϑ‖1 = 1, θ ≥ 0} of all possible scalarizations. The second is the imitation based family, also detailed in Appendix section A.2. The family is constructed by first running Online-ReOpt multiple times, then collecting the scalarizations and the corresponding policies generated.

heading: 5 EXPERIMENTS
text: We evaluate our proposed algorithms and benchmark algorithms in a controlled queueing system involving vectorial rewards. For each of the algorithms, we first run the algorithm for Zpo = Zan×Ξ independent trials, resulting in the Zpo average vectorial rewards2 {V̄ (zan,ξ)1:T }1≤zan≤Zan,1≤ξ≤Ξ. We plot the following three quantities against T :
• Ex-post Fairness: Ψ̄ = 1Zan 1 Ξ ∑Zan zan=1 ∑Ξ ξ=1 gmin ( V̄ (zan,ξ) 1:T ) , an estimate to E[gmin(V̄1:T )].
• Ex-ante Fairness: Γ̄ = 1Zan ∑Zan zan=1 gmin ( 1 Ξ ∑Ξ ξ=1 V̄ (zan,ξ) 1:T ) , an estimate to gmin(E[V̄1:T ]).
• Type k rewards for each 1 ≤ k ≤ K: Φ̄k = 1Zan 1 Ξ ∑Zan zan=1 ∑Ξ ξ=1 V̄ (zan,ξ) 1:T,k , an estimate to
E[V̄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 ek as the k-th standard basis vector for k ∈ {1, . . .K} in RK . In addition, we denote 1K , 0K as the all one vector and the all zero vector in RK .

heading: 5.1 QUEUING NETWORK
text: Queuing problems are studied extensively due to their relevance in fields such as manufacturing and in communication systems. In our evaluation, we focus on a discrete-time queuing 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 (1992), Kumar & Seidman (1990), Chen & Meyn (1998), de Farias & Van Roy (2003) and Banijamali et al. (2019). This network is shown in Figure 2.
There are two servers in the system. Server 1 only serves Queue 1 or Queue 4 with service rates µ1 = 0.3 and µ4 = 0.3 respectively, and where Server 2 similarly only serves Queue 2 or Queue 3 at the rates of µ2 = 0.3 and µ3 = 0.3. Arrivals occur at a rate of λ1 = 0.2 and λ2 = 0.2 at Queues 1 and 3 respectively. An arrival that gets served at Queue 1 by Server 1 then progresses to Queue 2, and only leaves the system after it has been served by Server 2. Likewise, arrivals at Queue 3 have to be served by Server 2, before moving on to Queue 4 to be served by Server 1 in order to leave the system. Each queue i has a maximum length of Li = 9, and a customer is rejected at a queue if the queue is at its full capacity. Conversely, an empty queue remains at length 0 even if an action is taken to serve that queue.
The state of the system is thus defined by the vector xt = (xt,1, xt,2, xt,3, xt,4) whereby xt,i represents the length of the queue i at time t. At each time step t, a decision has to be made by each server to serve only one or neither of its queues, which we can represent by a 4-component vector at = (at,1, at,2, at,3, at,4) ∈ {0, 1}4, where at,i = 1 indicates the decision to serve Queue i at time t, and at,i = 0 otherwise. Note that the condition of being able to only serve one queue at each server naturally imposes the constraints at,1 + at,4 ≤ 1 and at,2 + at,3 ≤ 1 at each t, meaning that As = {a ∈ {0, 1}4 : a1 + a4 ≤ 1, a2 + a3 ≤ 1} for each s.
2To avoid clutter, we omit the upper-script for the algorithm.
The transition dynamics for the system can then defined by the following equation when 0 < xt,i < Li, where ei refers to the basis vector in R4:
xt+1 =  xt + e1 with probability λ1 xt + e3 with probability λ2 xt + e2 − e1 with probability µ1a1 xt − e2 with probability µ2a2 xt + e4 − e3 with probability µ3a3 xt − e4 with probability µ4a4 xt otherwise
(8)
We define the type-i reward at time t as Vt,i(x,a) = 1− xt,iLi , for i ∈ {1, . . . , 4}. Recall that xt,i is the queue length of Queue i at time t. The reward Vt,i(x,a) is equal to 1 if Queue i is empty, and the reward Vt,i(x,a) decreases linearly with the length of Queue i at time t. In particular, Vt,i(x,a) = 0 if Queue i is full. Altogether, the agent’s reward for Queue i at time t positively correlates with the degree of idleness of the Queue. The maximization of gmin(V̄1:T ) = min1≤i≤4 V̄1:T,i is equivalent to the minimization of time-average queue lengths among all queues, hence enforcing all queues to be stable simultaneously.

heading: 5.1.1 SIMULATION RESULTS
text: In our simulation, we evaluate 5 algorithms. Three of them are our proposed algorithms, namely Online-ReOpt, Offline-ReOpt with Random Point Family and Offline-ReOpt with Imitation based family. The other two are existing baselines. The Meta Algorihtm by Zahavy et al. (2021) is the state-of-the-art for maximizing gmin(E[V̄1:T ]), while the longer queue first heuristic is a wellestablished 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 = Zan × Ξ = 1000.3 All of the algorithms employ the same optimization oracle Λ, with the same hyper-parameters and architecture, a double deep Q-learning network algorithm (Double DQN) by Hasselt et al. (2016).
Figure 3 plots the quantity Ψ̄ against T under the 5 algorithms. Notice in Figure 3 how the Offline and Online-ReOpt algorithms, as well as the Meta Algorithm by Zahavy et al. (2021) perform similarly well in terms of ex-ante fairness. Among them, the Meta Algorithm has the best performance, since the Re-Optimization schedule in our proposed algorithms compromises the ex-ante fairness objective. All algorithms demonstrate converging behavior, in the sense that the error bars diminishes as T grows.
3Except for Online-ReOpt, where we set Ξ = 5 since running an online algorithm for 1000 trials is not as practical as running an offline algorithm, which only needs to be trained once.
Figure 4 plots the quantity Γ̄ against T under the 5 algorithms. In terms of ex-post fairness, the Offline and Online-ReOpt 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 a similar performance to the Longer Queue First heuristic, the former has a significantly wider error bar than the latter, meaning that the latter is more stable.
Figure 5 plots Φi against T for i ∈ {1, . . . , 4}. In a nutshell, the plotted lines explain the trends in Figure 3, while the error bars shed light on the trends in Figure 4. Firstly, the plotted lines indicate that the Meta Algorithm has the highest (or close to the highest) individual average reward Φi for each queue, signifying that the Meta Algorithm has the highest E[V̄1:T,i] for each i ∈ {1, . . . , 4}. This explains the superiority of the Meta Algorithm shown in Figure 3.
When we focus on the error bars, the plots in Figure 5 tell a 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.4 When we unpack the summands in Φ1, . . . ,Φ4 and compute the minimum reward in each trial, it results in Figure 4, 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 a worse algorithm than the other 4 algorithms. Indeed, the Longer Queue Heuristic does not require the knowledge of λ1, λ2, µ1, . . . , µ4, whereas the other 4 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.
4It is helpful to revisit Section 3.2, where Zpo trials would result in ≈ Zpo/2 outcomes of (
0 1−1/T
) and
≈ Zpo/2 outcomes of ( 1−1/T
0
) .

Review summaries:
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.

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.

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.