Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach
Authors: Woohyeon Byeon
Giseung Park
Jongseong Chae
Amir Leshem
Youngchul Sung
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement learning
Multi-objective reinforcement learning
Primary area: reinforcement_learning

Abstract: In this paper, we propose a provably convergent and practical framework for multi-objective reinforcement learning with max-min criterion. From a game-theoretic perspective, we reformulate max-min multi-objective reinforcement learning as a two-player zero-sum regularized continuous game and introduce an efficient algorithm based on mirror descent. Our approach simplifies the policy update while ensuring global last-iterate convergence. 
We provide a comprehensive theoretical analysis on our algorithm, including iteration complexity under both exact and approximate policy evaluations, as well as sample complexity bounds. 
To further enhance performance, we modify the proposed algorithm with adaptive regularization.
Our experiments demonstrate the convergence behavior of the proposed algorithm in tabular settings, and our implementation for deep reinforcement learning significantly outperforms  previous baselines in many MORL environments.

Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoreth Approach
Woohyeon Byeon'
Giseung Park2
Jongseong Chae'
Amir Leshem²
Youngchul Sung!*
Abstract
In this paper, we propose provably convergent and practical framework for multi-objective reinforcement learning with max-min criterion. From a game-theoretic perspective, we reformulate max-min multi-objective reinforcement learning as two-player zero-sum regularized continuous game and introduce an efficient algorithm based on mirror descent. Our approach simplifies the policy update while ensuring global last-iterate convergence. We provide comprehensive theoretical analysis on our algorithm, including iteration complexity under both exact and approximate policy evaluations, well as sample complexity bounds. To further enhance performance, we modify the proposed algorithm with adaptive regularization. Our experiments demonstrate the convergence behavior the proposed algorithm in tabular settings, and our implementation for deep reinforcement learning significantly outperforms previous baselines in many MORL environments.
Introduction
Reinforcement Learning (RL) focuses on sequential decision maasionnmaking in Markov Decision Processes (MDPs), which have been extensively studied both theoretically and practically. However, in several practical decision-making problems such as autonomous vehicles, resource allocation and communication, multiple objectives should be simultaneously optimized instead of conventional
single objective (27 23 24 60) These scenarios motivate the development of Multi Aujti--bjecttve
Reinforcement Learning (MORL), extension of RL in which the reward function yields vector rather than a scalar. In recent years, MORL has seen significant progresses [6 50) [1 37 20]. A widely-adopted approach MORL is the utility-based approach [46] 22]. which formulated as follows: for a utility function u (also called scalarization function), solve max, u(V" ..... V&),, where π policy and V is the value function of the k-th objective. As long the utility function is non-decreasing in the sense of Pareto dominance, the optimal policy for u(Vi u.., VV is also Pareto optimal 446
Although many previous works on MORL considered the weighted sum utility function 61
the weighted sum utility function is the desired design metrie in many cases, especially when considering the application of MORL to resource allocation where faimesss is an important issue. For example, consider scheduling of cloud computing resources, in which a computing job is typically divided into multiple subtasks and each subtask is performed by different resource and completed subtasks are combined to finish the overall job 47 57). In this case, the overall time for finishing the
'Shool of Electrical Engincering, KAIST, Republic of Korca, Uniiersity of Toronto Robotics Institute, Canada, FFaultyy of Engincering, Blan University, Israel. *Correspondence to: Youngchul Sung <yc- sung @ ka.st.aackrs.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

job is determined by the maximum of subtask completion times. Consider another example of traffic signal light control at an intersection combining multiple roads. One can consider the waiting time at each road and may want to minimize the maximum of the waiting times of all roads for fairness on the drivers at all roads rather than to minimize the sum of the waiting times. Hence, the min-max (or equivalently max-min with negation of objectives) criterion naturally arises in many real-world
resource allocation problems as well as other application domains [13 42 63 34 29 2 17], where
fairness is important. (Please see Appendix B for comparison with other scalarizartion criteria
including proportional fairness.)
In this paper, we consider this max-min MORL, where the utility function is the minimum function: mink=1..... 2i and the resulting problem given by max, ming=1..... K V With the increasing relevance of max-min MORL, Park et al. [37] recently proposed a model-free algorithm for max-min MORI. through a convex formulation to circumvent the non-differentiability of min operation. Although their work provides model froee--free algorithm to solve exact max-min MORL in contrast to previous approximation methods [9 39 50 or model-based approaches [14] to max-min MORL, their algorithm suffers from high memory requirement and computational costs and only guarantees average-iterate convergence. this paper, we further advance max-min MORL and propose fast algorithm for max-min MORL with last-iterate convergence and significantly improved efficiency in computing time and required memory by reformulating max-min MORL as a awo-player zero-sum sum game.
u(
Our contributions are summarized follows:
We propose a single-loop algorithm for entropy-regularizzed max-min MORL by leveraging appro- priate regularization to derive a closed-form update.
Our algorithm can be viewed as a primal-dual algorithm and we provide a theoretical analysis the proposed algorithm in the tabular case, including global last-iterate convergence, iteration complexity, and sample complexity.
We demonstrate convergence behavior through numerical simulations in the tabular case and show that our deep reinforcement learning implementation significantly outperforms existing baselines in several MORL environments including a realistic traffic signal control task.
2 Background
Multi-objective Markov decision process A multi-objective Markov decision process (MOMDP) extends a standard MDP by incorporating a vector-valued reward function. Formally, a MOMDP is defined as (5, A, P. js, r, 7) with state space S, action space A, transition P 5 A - ASS), where (XX) denotes the set of probability distributions on set X, initial state distribution
A(S) and discount factor y E (0, 1). Unlike single-objective MDPs, the reward function r : S x A + R is vector-valued with r(s, a) = (r: (8, (ls.aa........ F (s, a)), where K is the number of objectives. An agent sequentially interacts with an environment by taking an action from its stationary policy : 5 - (A)) Unlike single-objective settings, the agent seeks to optimize all components of the reward vector simultancously in some manner.
The multi-objective state value of a policy π is defined as V = Ep,x [E I'r(st, E R and V/r denotes the k-th element of V The multi-objective state value with entropy regularization is defined as V E,.57 [E, 7 (r(*t, a.) - log 7 (a, (s, 1x)1 E R where 7 is a regularization coefficient, 1x is a K -ddimensional vector all of which entries are 1, and V denotes the k-th (w=(1,, ... w (K)) A denotes weight vector, where K is the (K - ))-simplex, i.e., A K = [w] 2 0 Vi, w(1) +... + 1). For weight vector w, we define the weighted value as V = (wr, V*y and the weighted soft value as w.r (w. VT), where (.--) denotes inner product. The soft values can be decomposed as Vr, V + 7 (T)) Vk and V V + + (T), where i/ (T) E -, log π (a, (s;) is the expected cumulative entropy of policy A summary of notations is provided in Appendix A
element of vector V Throughout this paper,
Max-min MORL Since the value function for MORL is vector-valued, optimizing the value function V over cannot be defined as in single-objective RL. Thus, max-min MORL considers the following max-min optimization: max; ming=1,.... K V. However, it is known that max-min MORL may yield the indeterminacy of its solution and entropy regularization resolves the possible

---

indeterminacy of max-min MORL solution [37. So, in this paper, instead of max-min MORL, we can consider the following entropy-regullrized max-min MORL problem:
max
min k=
VE + ++))
which converges to max-mix MORL -> O. It can be shown that the value gap between the entropy unregularized and regularized problems is proportional to the coefficent т. Due to the non- con-litear max-min MORL cannot be solved
of the min operator, max-min MORL or cntropy-regularizg directly using standard RL methods, requiring a specialized framework such as 37 or approximate
approaches [19 39 (0].
Mirror descent and natural policy gradient Mirror descent (MD) 36 a general optimization framework that subsumes popular algorithms such as gradient descent and the multiplicative weights update [6]. has been widely applied in learning dynamics across various games 65 7 59]
Formally, the update rule for MD can be expressed in primal domain as
T++1 = max ZEA
( - (Ir,
(2)
where f() is the objective function, À step size, and D the Bregman divergence induced by continuously differentiable and strictly convex function vú, defined as (I, v) = (/)r)) sh()) (Vv(y), x y), Vx, E X. MD basically implements steepest descent in a manifold of which Riemannian metric is given by the Hessian of De. capturing relevant geometry of the optimization variable space. In reinforcement learning, the natural policy gradient (NPG) can be interpreted as a
MD variant for MDPs with the Fisher information metric 226 36 48]
3 The Proposed Method
Our goal in this paper is solve the general problem ( We here develop a single-loop algorithm by interpreting
max-min MORL ( as learning Nash equilibrium in a two-player zero-sum game and exploiting theory of learning in games.
3.1 Max-min versus min-max
In this section, we derive Theorem 3.1, which serves as the initial step for our reformulation of the untropy-regularee max-min MORL problem (1) two-player zero-sum game.
Our key idea begins with the fact that the entropy-regularized max-min MORL problem is equivalent to the following problem 37
Minimization Reformulation min V wEAK K
where V is the optimal soft value under the scalarized reward (w, r). Here, the equivalence of problems means that both problems have the same optimal value and an optimal solution of one problem yields an optimal solution of the other. The equivalence was first shown [37] and a brief explanation of this equivalence is provided in Appendix [ for readers' convenience.
The next enabling step is that the problem ① involving minimization over discrete variable can be converted to minimization over continuous variable w E A as follows [9]
max min V = max min (w, V.), WEAR
(4)
where (w, VF) = EEE VK) k.r. and w(k) is the k-th element of weight vector w. This can easily be seen by considering the case in which we have a single minimum V for some k'. In this case, the minimizing w is given by (0.... 0, 1, O........ O) with at the k'th position. Note that while the two problems in (4) yield the same optimal value, the minimizers are not always in one-to-one correspondence. When the minimum is attained at multiple k indices, the corresponding optimal weights w form convex combination of those indices and lie on the boundary of the simplex. Theorem below formally bridges this gap by proving equivalence of optimal solutions.
Furthermore, due to ", A max, (w, VF) by its definition, the problem can be rewritten as
min max (w, V
(5)
we A
3

---

Combining these relations, we have the following equivalence between the max- max-min problem (=()) and the min-max problem (
i.c.,
max min (wc, V+) = min max V?).
(6)
WEAR
wEA
Note that the max-min value is not equal to the min-max value in general. Since value functions
in RL. are non-concave in policy even with direct parameterization [2, the equality (6) cannot be
directly induced from the minimax theorem [5].
From this special relation that the max-min value equals the min-max value in our case, the existence of saddle point is guaranteed in Proposition FI Appendix [.I] Once the existence of a saddle point guaranteed, Theorem e.neeabbiiss the equivalence of this saddle point (i.e., Nash equilibrium) in (6) and the solution of catropy-regulany
max-min MORL [ i... it suffices to find a Nash equilibrium O solve entropy-regularize max-min MORL.
Theorem 3.1. Let (ft, w)
be a saddle point in (6) Then, it is a solution to the entropy-regularized
max-min MORL ①
Proof: See Appendix
Now, based on Theorem 3.1] we will reformulate entropy-regularived max-min MORL as learning a Nash equilibrium achieving equality of (6) in the two-player zero-sum game whose payoff functions are given by (w, V7) and -(w, V?) for efficient algorithm construction.
3.2 Two-plaer zero-sum regularized continuous game formulation
We first define a two-player zero-sum continuous game G as follows. There are two players; Learner and Adversary. The player Learner corresponds to the RL agent in the MOMDP who learns the policy parameter O. We define the strategy space of Learner as X Learner = θ c IR which the space of policy parameters in the MOMDP. In other words, Learner takes continuous strategy O O which indicates the parameter of policy. The player Adversary has the strategy space Xadv = =A and takes continuous strategy
A K The utility functions of the two players are defined as
" Learner (0, w) = (we, V= Laa w).
In this game, Learner tries to maximize its utility (w, V and Adversary sary tries maximize its utility- -w, V i.e., minimize (w, V=*). In NE of this game, max-mi min and min-max values become the same and (6) achieved to yield our policy solution.
Instead of learning a NE in G, however, we solve the following regularized game RG, which is judiciously designed our advantage for efficient algorithm construction. The regularized game Rg has the same players and strategy spaces as the original game G. Instead, RG has utility functions regularized from the utility functions of G. Formally, the utility functions of RG are defined as RG
W Learner (0, (w, V**) + (mo) -T., (w) Adv (0, w),
(8)
(w.
where H()) = E,, [-E, nd log x (a, [s)] as already defined, H(w) = - EE w(k) log wkk). and and Tuo are positive coefficients.
Now, let us explain why we solve the new regularized game Rg instead of solving G. For Learner. the main reason for adding entropy regularization (TT)) avoid the indeterminacy problem as already explained [37] In short, stationary deterministic policies are insufficient for max-min MORL since there exists an MOMDP that has only a stochastic optimal policy for max-min MORL 46
For Adversary, adding - (w) regularization, Adversary minimizes (w. V Tee H(w). That is. Adversary minimizes (w, V while increasing the entropy H(w). Note that Learner maximizes min A (w, V= with its policy иe. Without - H (w) regularization, w achieving min (w, VF} would be one-hot vector focusing only on the worst dimension of V However, with (w)) regularization, the elements of the w vector will be spread out to incorporate multiple objective dimensions for Learner's 's optimization. This speeds up learning and we can achieve last-iterate convergence rather than average- average-iterate iterate convergence, which will be proven in Section 4 In addition, unlike other strongly convex regularizations such as squared 12-norm, our choice of negative entropy regularization enables closed-form solution for the MD update of w shown in [12 in Section 3.3 This closed-fie form update due to our (w)) regularization significantly simplifies the optimization process and reduces computational overhead.

---

3.3 The ERAM algorithm: Entropy-regularizee adversary for max-min MORL
We propose ERAM caatrooyy-Rgularizedd Adversary for Max-min MORL), an efficient algorithm to solve max-min MORL via a game-theoreti perspective. Based on the reformulation of the problem as two-player zero-sum game, we leverage equilibrium learning methods and introduce a variant of the MD algorithm to find Nash equilibrium in RG.
RG First, we update the policy parameter with the MD objective on u Learner with step size 7 as follows:
0 0 = arg max Vv u Learner Learner((0 (0r, we); 0) (0,00.))
Rg
Note that the objective in D can be viewed as the Lagrangian of the optimization of the linear approxi- Rg
mation of Learner's utility around current 0g (i.e., u Learner (0,, wt) + (Vo u LLarner wy), 8 ()) under constraint (8, 0e). Here, choose the convex function s for the Bregman divergence to be the negative Shannon entropy to make the Bregman divergence the KL-divergence, which yields the Fisher information matrix (FIM) Hessian matrix and is relevant to statistical manifolds: That is, Ty is a probablity distribution with coordinate 0, and {mO) forms a statistical manifold where FIM is 5 Then, the optimization with such conservatism in RL leads to natural policy
RG
an invariant metric
gradient (NPG)
5
36
26
48
The NPG update rule is given by 11
Ot11 = +
w. V
(10)
where F(0)- (dd " VV log (a(a V log my (a) s)]] is the FIM, 1) is a step size for NPG, iseudo-inverse [25] In the discrete tabular case, with softmax
and i denotes the policy parameterization, i.e., To(als) E. . R (S) AI, which is general enough to cover non-negative stochastic policies, we have the closed-form for NPG update (
ea
To (als) Z (t, s)
1
(To, (als)) exp -1 Qwi
(wir-(s.a))
(11)
where 1 97 approximation for Te. NPG can easily be implemented with compatible function approximation (55) In the case of general nonlinear neural network parameterization, the computation of FIM difficult but the NPG update for 0 can readily be replaced with TRPO [48] or PPO [49] of which purpose is to
T and 7 (t, s) is normalization constant. In the case of linear function
solve such wrngeecce-consrringg policy optimization. We will use PPO for deep implementation.
For the update of the strategy w of Adversary, we use variant of MD objective RC with step Add
size À as follows:
W++1 arg max A(V (. (-(w, VTl. ( |uwwn w) + H()) - Dv(w, w.).
(12)
WEAK
Note that 7 (TT) is irrelevant to w update, and Tw H (w) is outside of the gradient. Again, we choose the Bregman divergence to be the KL divergence, considering {w} forms a weight simplex A K manifold identical the probability simplex of K outcomes. With this choice, we have the following
closed-form solution to 12 [9:
(-1-BV=0, + Blog wy
Wy41 softmax
(13)
Twn
where B AI In this way, we circumvent any complicated iterative procedure to update wy-
Note that we could have derived another closed-form solution to W/+1 for conventional MD on u Rg which yields the same solution in (13) with 3 Arg- We prefer the modified MD update because the resulting closed-form solution employs B Ar.+II which is guaranteed to lie in (0, 1)
Ade"
for any choice of hyperparameters and Tur We note that (11) and (13) together lead to an NE of the
game RG, as shown in Section 4
3.4 The ARAM algorithm: Adaptively adversary for max-min MORL
Although ERAM provides an efficient model-free algorithm based on PPO and closed-form update of Wt, the performance can further be improved by detailing the w, update. We here develop Adaptively
5

---

Regularized Adversary for Max-min MORL (ARAM,, a variant of ERAM. In ARAM, we adopt an adaptive regularization method that extends the standard entropy regularization. Note that the regularizer H(w) in the Adversary's update rule [2) can be expressed as the KI. divergence from the uniform reference weight 11K, i.c. (w) = - DKL (w || 1
+ log K. Thus, increasing entropy is equivalent to minimizing the distance from the uniform reference. In ARAM, we replaced the uniform reference K 1k with dynamically computed vector E A AK, leading to the regularizer -D [ ||c) instead of H (w), where e captures the correlation between each reward component and the worst- perrs--erooring objective in the previous iteration. That is, the i-th element of the reference vector e obtained as
KK, where i' is the index of the worst-performing objective at the previous iteration batch and the expectation is replaced with sample expectation. Thus, ERAM minimizes (we, V while trying to keep close to 1x, i.e., considering all objective dimensions equally. On the other hand, ARAM minimizes (we, V while putting more emphasis on poorly-performing objective dimensions but not solely on the worst dimension, enabling joint optimization of multiple objective dimensions unlike previous GGF-PPO (50) which optimizes only the worst dimension at each batch. Again, a closed-form formula for the update in ARAM can be derived and more on ARAM is provided in
= (a (s)))))
(14)
Appendix D
Summarizing the above. the psdudo-codes of the proposed algorithms are in Appendix code is provided at atthtpss buattps://gthhbb. com/ wwtcccoo///hcceeeee wwwywon/wennneeeee /RAM- ARAM
E
Our source
4 Theoretical Analysis
In this section, we provide theoretical analysis of ERAM with respect to convergence, iteration complexity, and sample complexity under the assumption of tabular MOMDP in which the closed- form update (IT) for 9 is available with the softmax policy parameterization of Re (a)ss,,, while leaving theoretical analysis of more complicated ARAM as a possible future work. Note that the term "global convergence" means "convergence regardless of initial condition". and the term "last-iterate convergence of sequence F2 to x means "r, - x² as t + oo", whereas the term "average-iterate convergence" means" + ΣT It + x= as + oo", which does not imply Ie + x² in general.
Note that for (IT) and (13) we need to know the action value function since the state value function can readily be obtained from the action value function by summing over actions. We consider two cases regarding the knowledge of the action value function, exact and approximate policy evaluation cases, for proof of convergence.
Global convergence with exact policy evaluation: Theorem 4.1 shows the last-iterate convergence of Algorithm [ when policy evaluation is exact.
Theorem 4.1. Let ] and (we) are the sequences generated by Algorithm 7 and let m. = mo, Then, the optimality gaps satisfy the following:
|| log T" loo Te a0 S Ci(p(n,A))
(15)
| - we 1o S C2(p(1, X)]²
(16)
1 -. Q Qui S Cslp(n, A)]*
(17)
for some C1, Cz, Ca. where 12K (max, o. ra(s.a)++ [A)? > and e E (0, co) for some cy-
< p(n,)) S - & < 1 with 7
c(1 <(1-2) Tw N
7(1-7)
Proof: See Appendix
For last-iterate convergence of policy and weight, the step size of weight-update À == O(e²) should have a smaller scale than the step size of NPG 17 O(e). We note that if y O(c), then it suffices for À to have a smaller scale at least Oee)), p > 1. Our choice À = O(e²) is one possible choice that satisfies this condition. In intuitive sense, the policy is required to be updated faster than the weight.
Corollary 4.2. Let the desired accuracy error tolerance be denoted by cace- To achieve log Tt
log lo S Ecco: I|w= - welloo I Eaces 1|QT - lloo S tace with 1) s(1-7)
(1
softmax policy and exact policy evaluation, Algorithm I requires at most 0 2 log 1 iterations.

---

Global convergence with approximate policy evaluation: When exact policy evaluation is not available, our algorithm can be adapted to use approximate value estimates with bounded error. We establish that the last-iterate convergence guarantee still holds under this relaxed setting.
Theorem 4.3. Assume that the estimated values Qu,, and Q% satisfy I1 - ru < 6 and
112% Oi lbe < ō for any n, we k. Let {0e}t and {we}e be the sequences generated by Algorithm
a modified version of Algorithm I for approximate policy evaluation provided in Appendix F and let Te --. Then, the optimality gaps satisfy the following:
|| log xt' - -log Tell - Cippin 111² D
(18)
1|00 well ~ S C2lp(n, AlI' D25/62
(19)
1 1u:T Q 2 S Cslpin, AiI + +D8/22
(20)
where 0 < i(n, A) 1- 5 ffre E (0, co) with the same condition in Theorem 4.1 except for the values of D1, D2, Dg and 60.
Proof similar to that of Theorem and is provided in Appendix H
Corollary 4.4. Let the accuracy error tolerance be denoted by Eaee- Assume that the estimation
error â is sufficiently small to satisfy ô S Staas i = 1,2,3. To achieve || log π - log Te 1oo S
D. 2eace; | welloo S Deace, and |Q Q Twr S Deac with 1) <(1-))
Tw
softmax policy with approximate policy evaluation, Algorithm 2 requires at most Oc 2 log iterations. Furthermore, with estimation error 8 O under Assumptions J.1 and J.2 provided in Appendix | by employing fresh samples for the policy evaluation for each objective at every iteration and taking the union bound for all objectives and all O log race iterations, Algorithm
2 requires at most Ō state-action puir.
(1-7)-0422 X 0 log Eace
K
=Ū
K
samples per each
Remark 4.5. It can be shown that the difference between the optimal value function induced the regularized game RG and that of the unregularized counterpart (i.e., RG with = Tup 0) is bounddd lineurly in the regularization coesficients T and Tw- This implies that the optimal solution of the regularized game yields a value fanction close to that of the original max-min MORL problem (i.e., ① with T 0), as long as the regularization coefficients are sufficiently small.
Proofs of Corollaries 4.2 and are provided in Appendix | and details for the sample complexity analysis are provided in Appendix !
5 Related Works
Max-min MORL The utility-based approach is key aspect of MORL, as it incorporates fairness and reflects user preferences [46] (2]. To capture broader notions of fairness, recent studies have adopted non-linear utility functions. Cousins et al. [14] considered model-based approach to fair RL but this method is applicable to small finite problems. Fan et al.
19 analyzed faimess through
the lens of the Nash social welfare function, while Peng and Fain value iteration framework for general non-linear welfare functions, including the min operator. These works focused on optimizing the objective Er, [ming Ee Errsr at)], which is not the true min value ming Ey [E, ('rx(*t, {t)], to simplify the problem. Siddique et al. (50) studied fair policy learning in MORL using the generalized Gini social welfare function, which includes max-min fairness as a special case. GGF-DQN, their DQN-based method, optimizes again the surrogate objective E, [ming Σ. 7'rx( )t) due to the difficulty in constructing a Bellman operator under the non- lineariyy of the min operator. GGF-PPO, their policy-based method, performs PPO update every iteration batch based on the current minimum objective value dimension. Note that if we remove H Hww) by setting Tu = 0 and remove De (w, w:) in our w update (12), then the strategy w of Adversary is the one-hot vector with element I at the minimum dimension of V and this case corresponds to GGF-PPO. Hence, our work can be considered as a generalization of GGF-PPO. However, when w constrained to switching among one-hot vectors as GGF-PPO, only average- iterate convergence is guaranteed (6). Note that our method has H (w) encouraging to consider
33 proposed a reward-aware
7

---

multiple dimensions simultaneously and (w, we) preventing rapid jumps in w for last-iterate convergence. Performance improvement will be shown Section 6
For max-min fairness based on direct optimization of ming E, IΣ; 7'r (8t, az)], Park et al. 37 proposed theoretical framework based on primal-dual convex programming for maximum-entropy reinforcement learning. To implement this framework, they introduced model-free double-loop algorithm: the inner loop computes a stochastic zeroth-order gradient estimator using Gaussian smoothing. and the outer loop performs projected gradient descent with the estimated gradient. The complexity of this method is far beyond that of our current method.
Game-theoretis learning with regularization Regularization techniques have been widely used to compute Nash equilibria in game- thme-theoretic settings. APMD []] analyzes MD under smooth monotone game assumptions, which do not hold in our Rl-based setting due to the non-monotonicity of the value gradients. In addition, APMD applies MD to all agents, whereas NPG for the learner and MD for the adversary, which better suits deep RI. implementations. Perolat al. [40] studied two-player zero-sum Markov games based on replicator dynamics and provided an asymptotic convergence analysis using Lyapunov techniques. Aggarwal et al. [3] focused on regularized linear-quadratic games and established non-asymprotic convergence guarantees. Zeng et al. (64] proposed a regularized gradient descent-ascent method for two-player zero-sum Markov games and provided monastyptoticc analysis. In contrast these approaches, our method addresses one RL learner and non-RL adversary, and is specifically tailored to max-min criterion for MORL. We also provide non-asymptotii convergence for our method. For a detailed discussion of zero-sum Markov game literature, we refer the reader to Appendix K
combine RL--oriented
a heterogeneous setting with
Primal-dual methods and distributtionally-rouus RL Several constrained RL methods adopt a primal-dual framework to solve constrained MDPs, where Lagrangian function is formulated and an alternating optimization procedure applied maximize over the policy and minimize over the Lagrange multipliers [10 33
32 17 [8]. Although our algorithm can be viewed as one work differs from these approaches in that the weight w lies
instance of primal-dual algorithms, in probability simplex, whereas Lagrange multipliers of these works reside in the non non-negative quadrant. In addition, due w E A K we employ entropy regularization H (w) instead of the w|| regularization used in Müller et al. [33], which allows us to obtain a closed-for form solution for the w-update without requiring projected gradient descent used in Efroni al. 18 Müller et
Distributionally-roouss reinforcement learning (DR-RL) typically addresses transition uncertainty 52 can define uncertainty set in the reward space and apply a max-min formulation to achieve robustness. Our setting corresponds to a finite uncertainty set {ri..... ., TK), J. where the regularization term captures such internalized reward uncertainty, in a manner similar to how DR-RL handles transition uncertainty. For infinite uncertainty sets, DR-RL could potentially be extended to analyze robustness in terms of a distribution over the reward space.
16 30
Analogously, in reward-uncertain MDPs 44
Experiments
6.1 Numerical results in tabular setting
We empirically demonstrate the convergence of our algorithm in tabular MOMDP settings. We considered three types of tab- ular MOMDPs with different sizes: (1S), |A), K) (2, 2, 2). (3.3, 3. 6). and (4, 4). As the suboptimality measure, we used the Nash gap. common metric in game theory [53] 38), de- fined as Nash_Gap(0, w) (maxæ (w, V (w V=*)) + ((w, y (w', V=*)). This measures how far the stral- egy tuple (0, w:) is from a Nash equilibrium in the unregularized game.
1214
60
Nash
Step
Figure 1: Nash gap
Figure shows that the Nash gap of Algorithm decreases quickly over time all three tabular settings. Each curve represents the average over 50 randomly generated instances, with shaded areas showing standard deviation. We also present the convergence behavior of ARAM with approximate policy evaluation in the tabular settings in Figure 7 in Appendix L
8

---

6.2 Experimental results in traffic signal control
To evaluate the effectiveness of our algorithm in real-world multi-objective problems, we conducted experiments in the traffic signal control simulation environment [4]. At four-road intersection, the agent controlled traffic signals based on traffic state information and received a reward vector composed of the negative total waiting times. Rewards were defined either per road (4 objectives) or per lane (16 objectives). We considered three scenarios: Base-4, Asym-4, and Asym- 16, which differ in the number of objectives and traffic flow symmetry, as explained in Appendix M.
We compared our method against GGF-DQN, GGF-PPO [50), Park et al. [37], and Avg-DQN. Avg-DQN optimizes the average re- ward R F rk, reflecting simple sum approaches. GGF-
E3:
DON optimizes surrogate objective, Eg mmnng E. ( dz)], which yields a lower bound on the true max-min objective ming Eg Ex 7 (5e, 0z)] via Jensen's inequality. GGF-PPO per- forms a PPO update on the objective of minimum value at each itera- tion. contrast, the method of Park et al. (37 directly solves the tar- get problem (I) without relying on surrogate, using projected gradi- ent descent with smoothed gradient estimate via Gaussian smooth- ing. We evaluated the max-min performance the minimum of the empirical return vector, i.e., min; R₂ N Σ E, f'ri at), averaged over = 32 episodes and five random seeds. (Simulation details are provided Ap- pendix M.I)
Figure 2: Traffic signal control environment
Environments
ARAM
ERAM
Park al. (37
GGF-PPO
GGF-DQN Avg-DQN
Base-4
-1160
-1387
-1681
-1731
-1838
-2774
Asym-4
-2696
-2732
-3510
-3501
-3053
-4245
Asym-16
-15043
-17334
-23663
-21663
-17792
-27499
Table 1: Max-min performance in traffic signal control. Bold: best; underline: second-best.
Table reports the max-min performance across the traffic signal control environments. ARAM consistently outperforms all baselines across all environments. ERAM achieves comparable results while maintaining architectural simplicity, and both methods directly optimize the target objective without relying on surrogate losses.
More experimental results on other environments such as the species conservation environment [5] 1O-Reacher environment (20), and Four-Room environment (2 are provided in Appendix showing the superior max-min performance of our algorithms.
6.3 Complexity comparison
Convergence behavior Our method guarantees last- iterate convergence, unlike Park et al. [37]. which en- sures only average-iterate convergence. Figure iillus- trates this difference simple MOMDPs with two states, two actions, and two objectives. We present results on three representative randomly generated MOMDPs to ensure visual clarity; the same color is used to indicate same MOMDP instance across the two plots. each
Subapimailty
12- 10-
case, AM consistently approaches the true optimal
Value Suboptimrality
14
value, up to a gap determined by the regularization coef- ficient, while the baseline cxhibits oscillatory behavior.
20
Memory efficiency To assess memory efficiency, we compared the number of model parameters used in each weight update. As in the original implementation, Park et al. [37] employs 20 copies of the Q-network, re- sulting 274,084 parameters per update in the Base- 4 and Asym-4 environments (4-dimensional reward), and 274,096 parameters Asym-16 (16-dimensional re- ward). In contrast, method uses only 13,704 and 14,484 parameters,
Stop
Figure 3: Convergence comparison in ran- dom tabular MOMDPs: ERAM (top) vs. Park et al. (37] (bottom). Colors indicate different random MOMDPs.

---

to reductions of approximately 95% and 94.7%. Despite this drastic reduction, our method achieves superior max max-min performance, as shown in T
Computational cost efficiency To evaluate the computational complexity of our method, we compared the training wall-time across different environments, Park et al. [37] relies on an exten- sive soft Q-learning procedure for each weight update, leading to significantly longer training times. In contrast, our single-loop approach updates the weight and policy simultaneously, substantially reducing overall training time. ERAM achieved training time reductions of approximately 67.8% in Base-4, 63.8% in Asym-4, and 68.4% in Asym-16, 16. Similarly, ARAM achieved reductions of approximately 65.5% Base-4, 63.7% in Asym-4, and 67.6% in A6ym-16. Although ARAM includes
Envs
ERAM
ARAM
Park et al.
67
GGF-PPO
Base-4
111 + 2.6
120 + 3.9
346 # 14
122 + 4.0
Asym-4
2.4
87.4 2.4
241 # 6.3
84.8 + 2.2
Asym-16
35
365 + 20
1125 95
394 + 5.5
Table 2: Training wall time (minutes), averaged over five seeds.
additional step for computing correlation vectors, this overhead does not noticeably increase the total runtime. Overall, the computational complexity of ARAM is almost the same that of ERAM. All experiments were conducted independently on the same hardware to ensure a fair comparison. See Table 2 for a full summary. Note that the memory requirement and computational complexity of ERAM and ARAM are at the same level of GGF-PPO since our w update uses a closed-form solution and the size of w is only the number of objectives.
6.4 Ablation study
Since Learner of our algorithm is PPO in deep RL cases, ablation study regarding Learner can refer to PPO, and we focus on ablation study Adcersary whose update given by (3) for ERAM or 40 for ARAM with two hyperparameters À and Tw- The algorithms are not sensitive when B not near ERAM or not near in ARAM. When
O, ERAM effectively omits the mirror descent term, allowing to observe the impact of MD. When 3 == 1, ARAM ignores the adaptive regularizer, highlighting its contribution to performance. Please see Appendix M.3 and Figure 8 for more.
7 Conclusion
In this paper, we have considered MORL with max-min criterion. Exploiting the special max-min and min-max equivalence in this problem, we have reformulated max-min MORL as a two-player zero-sum regularized continuous game. We have proven the existence of a NE of this game, which yields max-min MORL policy. Then, have proposed efficient algorithms find NE of this game, where the learner can use conventional PPO to update its strategy and the adversary updates its strategy based on a closed-form formula. We have proven last-iterate convergence of the algorithms in the tabular case and demonstrated that the proposed algorithms significantly outperform existing max-min MORL methods. The proposed max-min MORL algorithm has the complexity of PPO and can be used practically for many world resource allocation problems.
8 Acknowledgments
This work was supported by the National Research Foundation Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2025- 00557589, Generative Model Based Efficient Reinforce- ment Learning Algorithms for Multi-modal Expansion in Generalized Environments) and by the Ministry of Innovation, Science & Technology, Israel grant 1001556423 and ISF grant 2197/22.
10

---

References
[1] Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, and Atsushi Iwasaki. Adaptively perturbed mirror descent for learning in games. In Forty-first International Conference Machine Learning. 2024.
[2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
[3] Shubham Aggarwal, Melih Bastopcu, Tamer Başar, et al. Policy optimization finds nash equilibrium in regularized general-sum lq games. 63rd IEEE Conference on Decision and Control, CDC 2024, Milan, Italy, December 16-19, 2024, pages
2024.
[4] Lucas N. Alegre. SUMO-RL. htttps///ggtbub..cc/aaaaaaaaaaae
2019.
[5] Shun-ichi Amari. Information Geometry and Its Applications, volume 194. Springer, 2016.
[6] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta-algorithm and applications. Theory of Computing, 8(1):121-164, 2012.
[7] Yu Bai, Chi Jin, Song Mei, Ziang Song, and Tiancheng Yu. Efficient phi-regret minimization in extensive-form games via online mirror descent. Advances in Neural Information Processing Systems, 35:22313-22322 2022.
[8] Toygun Basaklar, Suat Gumussoy, and Umit Y. Ogras. Pd-morl: Preference-driven multi- objective reinforcement learning algorithm. In The Eleventh International Conference on Learning Representations, 2023.
[9] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[10] Miguel Calvo-Fullana, Santiago Paternain, Luiz FO Chamon, and Alejandro Ribeiro. State augmented constrained reinforcement learning: Overcoming the limitations of learning with rewards. IEEE Transactions on Automatic Control, 69(7):4275 2023.
[11) Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4): 2563-2578. 2022.
[12] Shicong Cen, Yuejie Chi, Simon S Du, and Lin Xiao. Faster last-iterate convergence policy optimization in zero-sum markov games. arXiv preprint arXiv:2210.010500 2022.
[13] Iadine Chadès, Janelle MR Curtis, and Tara G Martin. Setting realistic recovery targets for two interacting endangered species, sea otter and northern abalone. Conservation Biology. 26(6): 1016-1025, 2012.
[14] Cyrus Cousins, Kavosh Asadi, Elita Lobo, and Michael Littman. On welfare-centric fair reinforcement learning. In Reinforcement Learning Conference, 2024.
[15] Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33:5527-5540, 2020.
[16] Esther Derman and Shie Mannor. Distributional robustness and regularization in reinforcement learning. arXiv preprint arXiv:2003.02894 2020.
[17] Eric Eaton, Marcel Hussing, Michael Kearns, Aaron Roth, Sikata Bela Sengupta, and Jessica Sorrell. Intersectional fairness in reinforcement learning with large state and constraint spaces. arXiv preprint arXiv:2502.11 11828, 2025.
[18) Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploiiation in constrained mdps. arXiv preprint arXhv:2003.02189, 2020.

---

[19] Ziming Fan, Nianli Peng, Muhang Tian, and Brandon Fain. Welfare and faimess in multi- objective reinforeement learning. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '23, page 1991-1999, Richland, SC, 2023. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781450394321.
[20] Florian Felten, Lucas N. Alegre, Ann Nowé, Ana C. Bazzan, El Ghazali Talbi, Grégoire Danoy, and Bruno C. da Silva. A toolkit for reliable benchmarking and research in multi- objective reinforcement learning. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS 2023), 2023.
[21] Seungyul Han and Youngchul Sung. A max-min entropy framework for reinforcement learning. In Advances in Neural Information Processing Systems, 2021.
[22] Conor F Hayes, Roxana Rădulescu, Eugenio Bargiacchi, Johan Källström, Matthew Macfarlane, Mathieu Reymond, Timothy Verstraeten, Luisa M Zintgraf, Richard Dazeley, Fredrik Heintz, al. A practical guide to multi-objective reinforcement learning and planning. Autonomous Agents and Multi-Agent Systems, 36(1):26, 2022.
[23] Xiangkun He and Chen Lv. Toward personalized decision making for autonomous vehicles: a constrained multi-objecctvve reinforcement learning technique. Transportation Research Part C: Emerging Technologies, 156: 144:2, 2023.
[24] Yuanzhi He, Biao Sheng, Hao Yin, Di Yan, and Yingchao Zhang. Multi-objective deep reinforce- ment learning based time-frequency resource allocation for multi-beam satellite communications. China Communications, 19(1):77-91, 2022.
[25] Roger A Horn and Charles R Johnson. Matrix Analysis. Cambridge University Press, 2012.
[26] Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On the linear convergence of natural policy gradient algorithm. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 3794-3799. IEEE, 2021.
[27] Changjian Li and Krzysztof Czarnecki. Urban driving with multi-objective deep reinforcement learning. In Proceedings of the 18th International Conference Autonomous Agents and MultiAgeni Systems, 2019.
[28] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 13:12861-1287,, 2020.
[29] Peng Li, Song Guo, and Zixue Cheng. Max-min lifetime optimization for cooperative commu- nications in multi-channel wireless networks. IEEE Trunsactions Purallel and Distributed Systems, 1536):153 2013.
[30] Zhishuai Liu, Weixin Wang, and Pan Xu. Upper and lower bounds for distributionally robust off-dynamics reinforcement learning. arXiv preprint arXiv:2409.2052/ 2024.
[31] Haoye Lu, Daniel Herman, and Yaoliang Yu. Multi-objective reinforcement learning: Convexity, stationarity and pareto optimality. In The Eleventh International Conference on Learning Representations, 2022.
[32] Sobhan Miryoosefi, Kianté Brantley, Hal Daume III, Miro Dudik, and Robert Schapire. Reinforcement learning with convex constraints. Advances in neural information processing systems, 32, 2019.
[33] Adrian Müller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, and Niao He. Truly no-regret learning in constrained mdps. arXiv preprint 4rXiv:2402.15776, 2024.
[34] Dritan Nace and Michal Pióro. Max-min fairness and its applications to routing and load- balancing in communication networks: a tutorial. IEEE Communications Surveys Tutorials, 10(4):5-17, 2008
12

---

[35] Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
[36] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[37] Giseung Park, Woohyeon Byeon, Seongmin Kim, Elad Havakuk, Amir Leshem, and Youngchul Sung. The max-min formulation of multi-objective reinforcement learning: From theory to model-free algorithm. Forty-first International Conference on Machine Learning, 2024.
[38] Nikolas Patris and Ioannis Panageas. Learning nash equilibria in rank- games. In The Twelfth International Conference on Learning Representations, 2024. URL httpss://openreviei
[39] Nianli Peng and Brandon Fain. Nonlinear multi-objective reinforcement learning with provable guarantees. arXiv preprint www.iv:2311.22555 2023.
[40] Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(6623):990-999) 2022.
[41] Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
[42] Majid Raeis and Alberto Geon-Gareia. deep reinforcement learning approach for fair traffic signal control. In 202/ IEEE International Intelligent Transportation Systems Conference (ITSC), pages 2512-2518. IEEE, 2021.
[43] Antonin Raffnn, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. BaslleBas: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1-8, 2021. URL http://jmlz: wrggpapprs/v222
20- 10-1364.he html
[44] Kevin Regan and Craig Boutilier. Robust policy computation in reward-uncertain mdps using nondominated policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, pages 112--1133, 2010.
[45] Tyrrell Rockafellar. Conver Analysis, volume 11. Princeton University Press, 1997.
[46] Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. A survey of multi-objective sequential decision-making, Journal of Artificial Intelligence Research, 48: 67-113, 2013.
[47] Abusayeed Saifullah, David Ferry, Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher D. Gill. Parallel real-time scheduling of dags. IEEE Trans. Parallel Distributed Syst. 25(12): 3242-3252, 2014. doi: 1LL1199/PDD.221332299999
[48] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pages 1889-1897. PMLR, 2015.
[49] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 1207:0/777.63477 2017.
[50] Umer Siddique, Paul Weng, and Matthieu Zimmer. Learning fair policies in multi-objective (deep) reinforcement learning with average and discounted rewards. In International Conference on Machine Learning, pages 8905-8915. PMLR, 2020.
[51] Umer Siddique, Abhinav Sinha, and Yongcan Cao. Fairness in preference-bast based reinforcement learning. arXiv preprint arXiv:2306. 09995, 2023.
[52] Flena Smirnova, Elvis Dohmatob, and Jérémie Mary. Distributionally robust reinforcement learning, arXiv preprint arXiv: 2019.
13

---

[53] Zhuoqing Song, Jason D. Lee, and Zhuoran Yang. Can we find nash equilibria at a linear rate in markov games? In The Eleventh Internationaa Conference on Learning Representations, 2023.
URI
[54] Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
[55] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems, 12, 1999.
[56] Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: standard interface for reinforcement learning environments. arXiv preprint arXiv:2407.17032. 2024.
[57] Kankan Wang. Xu Jiang, Nan Guan, Di Liu, Weichen Liu, and Qingxu Deng. Real-time scheduling of DAG tasks with arbitrary deadlines. ACM Trans. Design Autom. Electr. Syst., 24 (6):66:1-6622,, 2019. doi: 10. 10/1345/3358603
[58) Chen-Yu Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinitehhorizon competitive markov games. In Conference on learning theory, pages 4259-4299. PMLR, 2021.
[59] Andre Wibisono, Molei Tao, and Georgios Piliouras. Alternating mirror descent for constrained min-max games. Advances in Neural Information Processing Systems, 35:35201-35211 2022.
[60] Yuanyuan Xu, Kun Zhu, Xu, and Jiequ Ji. Deep reinforcement learning for multi-objective resource allocation in multi-platoon cooperative vehicular networks. IEEE Transactions Wireless Communications, 22(9):6185-6198 2023.
[61] 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.
[62] Tong Yang, Shicong Cen, Yuting Wei, Yuxin Chen, and Yuejie Chi. Federated natural policy gradient methods for multi-task reinforcement learning. Advances Neural Information Processing Systems, 2024.
[63] Ephraim Zehavi, Amir Leshem, Ronny Levanda, and Zhu Han. Weighted max-min resource allocation for frequency selective channels. IEEE Transactions on Signal Processing, 61(15): 3723 3732, 2013.
[64] Sihan Zeng, Thinh Doan, and Justin Romberg. Regularized gradient descent ascent for two- player zero-sum markov games. Advances in Neural Information Processing Systems, 35: 34546-34558, 2022.
[65] Wenhao Zhan, Jason Lee, and Zhuoran Yang. Decentralized optimistic hyperpolicy mirror descent: Provably no-regret learning in markov games. In The Eleventh International Conference on Learning Representations, 2023.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and introduction clearly reflect the theoretical contributions and experimental findings presented in the paper.
Guidelines:
14

---

The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the
contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Appendix O
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide the assumptions and proofs for Theorem 3.1 Theorem 4.1 The-
orem Corollary 4.2, and Corollary 4.4 in Appendix F.2 Appendix Appendix Appendix and Appendix]]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
15

---

The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
The experimental environments are described in Appendices and and the hyperparameters are provided in Appendix (..2
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- spen-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the source code for the traffic signal control experiment, which constitutes the main experimental result the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
16

---

Please see the NeurIPS code and data submission guidelines (https://nips.co htapa///ggiidee//eeeubbiiiii
conossooiissiioooococccc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https / /nips..c/publll cemolliccguiiese gwwdee/ddeeeee /eddeSSud wwwbbbmmssioooooiiooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental setups and environments are described in Appendix and M The source code is provided and hyperparameters are listed in Appendix M.2
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We used five random seeds for the deep RL benchmarks in Section 6.2 and Appendix N and fifty random seeds for the tabular settings in Section and Appendix L Figure T and Table 2 the standard deviation across seeds, with shaded areas in the figure and numerical values in the table. Figure shows results from three random seeds for improved visual clarity.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
17

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Device specifications provided in Appendix M.2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:/:://euiiss..ee www.eerris.ccpppppeeeee httpppp/ppppppp..attccccccccaeea
Answer: [Yes]
Justification:
The research fully complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the social impacts in Appendix O
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
18

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper does not pose risks of misuse requiring special safeguards.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We use Stable Baselines3 (MIT license), SUMO-RL (MIT license), and MO- Gymnasium (MIT license), all of which are properly cited and used in compliance with their respective licenses.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwpprswi www.wwtthth.....c com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
19

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or human-subject research.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The research does not involve human subjects and therefore does not require IRB approval.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact core methodology, scientific rigorousness, originality of the research, declaration is not required.
20

---

Answer: [NA]
Justification:
The research does not involve LLMs as an important or original component of
the methodology.
Guidelines:
The answer NA means that the core method development in this research does not
involve LLMs as any important, original, non non-standarr components.
Please refer to our LLM policy (https: ptttps://neurip... cetpourrpscccoooffeeeeeee / for what should or should not be described.
21

---

A
Glossary
Notations
Descriptions
MOMDP
space
Action space
Transition dynamies
Initial state distribution
oulri-objective reward in the MOMDP
objectives,
objeett reward
k-th coordiaate of vector reward r. & I...,
Discount factor
S.
Policy, Policy space
0,
Policy parameter, Policy purameter space
weight, action Adversary
Values
V
Fyg (-f- r'r(st ae] & IR, Value vector under policy the MOMDP
YE
Eyer Zito I're (Pe ). k-th coordinate of value under policy the MOMDP. A*
Vr
(or, Vay Z vr(A) the weighted value for
Eua Li 7 ((((ee [ - log [ogg((oss:]]
B., soft value vector with K objectives and entropy confficient
VE
8-th coredinate soft value vector
(w, V?) Ep.s >, (ue, r(sr. a.); 7 llgg [ax e R. soft value with scalar reward (w,r)
Q.
optimal
scalar reward (uc,
Constants
Entropy coefficient for NPG
Entrogy coellicient for mirror descent
Step NPG Step size for mirror descent oz
Mathematical Notations
A
KK 1)-Simplex, Lc., (w é RR E w(k) 1, (x( 0, I.... K)
(r.0)
inner product for any Rd.
Hiw)
wikk log wik)) Shamnon entropy for
((())
E, log [()l
softmux((r)
E sed for any a e R2
Zrans Sol -l-oe--vocter with dimeasion df
L
DKL
Kullback Leibler divergence
[ normm i.e., ||=]]] Dim an)
Rd
bo norm. Le.. |affas max,
Table 3: Notations in the main paper
B Relationship between Max-Min Fairness and Other Fairness Criteria in
MORL
We can consider three major scalarization methods for MORL, as follows:
Sum return maximization
K
max
W
(21)
Max-min optimization
max mon (wy Vi, ... WK VK}
(22)
Proportionally-fair (PF) optimization
log V
(23)
Here, Wi.... /K are some given weighting factors. We consider the weighted version of all three methods above for full generality.
The sum return maximization for given weights is simple single-objective RL for which there are many existing algorithms. Hence, the problem is rather simple.
Consider the PF problem. Since the logarithm function is differentiable, the policy gradient of the PF objective 23 can easily be obtained. That is, let use V instead of V, to show the dependence of
22

---

return on the policy parameter & explicitly. Then,
a
0
80 iy log Vi
Σ
W V 00
(24)
Note that 0V.
00 is nothing but the conventional policy gradient, which is given by Va log (s (s, a) [54]. Hence, it is rather straightforward to solve the PF problem for MORL and we only need to track individual functions.
In contrast, the max-min problem does not allow such direct differentiation and becomes more complicated. Hence, specialized method is needed as in [37] approximate approaches were considered as [9 [9] [5]. In this paper, we solve the exact max-min MORL problem and provide very efficient algorithm for this problem.
V2
2x
b
y
X xty=c
Figure 4: Relationship between max-min fairness and other fairness notions in MORL.
Figure|4illuse Fillustrates the solution of each method for equal weights with two objectives. the figure, all of points b. c, and d are Pareto optimal. The max-min solution, point a. corresponds to the Pareto-optimal point that achieves Pareto efficiency with Vı = V/ due to equalizer rule [63]. Note that by weighting Wi and u2, to the same equalizer rule, e.g., Point b in the figure.
achieve the Pareto-houndary point which wi Vi uy V2 due
Point e is the sum return maximization point on which the Pareto brretd-buundary is tangential with the straight line Vi + 1/2 = for some c. Again, we can change the slope of the line by considering weights wi Vi + w2 1/2 c.
Point d is the PF point on which Pareto-boundary tangential the curve V V/2 because Σ, log Vi = log II. V, Note that the PF point is a compromised point between the sum maximization point and the max-min point.
for some d'
C Brief Summary of the Prior Work: Convex Optimization Formulation of Max-Min MORL (37]
Based on the fact that value function is linear in state-action occupancy measure 54 Park et al. 37 rewrote the max-min MORL without entropy regularization in terms of state-action occupancy measure (PO in Park al. (37])
PO: max min
Σ ()ass))
(25)
Σ d(s's a') =p(s') + Σ
AA
(26)
d(s, a) 20. Vs. a.
(27)
By taking dual problem and linear programming formulation of value iteration 411, Park et has shown that solving PO is equivalent to solving the following convex optimization problem P2.
The convexity of the objective function in P2, and the equivalence of PO and P2 are addressed in Theorem 3.1 and Theorem 3.2 in Park et al. 37 respectively.
23

---

P2 in Park et al.
[37
min
Σ [m(s)V((s)
(28)
WEAK
where (-) is optimal value function with linearly scalarized reward (w, r(s,a)):
However, this value iteration based method can fail to find optimal policy in max-min MORL even in simple one-state MOMDP [46 33.. This issue is called indeterminacy; that is, there exists an MOMDP which has no nax-min optimal policy, which is stationary and deterministic. To circumvent this issue, [37] adopted entropy regularization to ensure the policy stochastic and established convex programming reformulation similar to above:
PO:: max min E ( -
(29)
k=l....K 8,0
Σ d(s''a') =p(d)) +7 Σ ()dlss, AA
(30)
d(s, a) 20, Vs,a
(31)
where (als) = E. d(s,a))'
d(a.a)
Similar to above, solving PO' is equivalent to solving the following convex optimization problem P2'. The convexity of the objective function in P2', and the equivalence of PO' and P2' are addressed in Theorem 4.1 and Theorem 4.2 in Park et al. 37 respectively.
P2' in Park et al.
min Vu(s)Verrs))
(32)
WEAR
where V (-) is the soft optimal value function with scalar reward (w, a)) which is the solution of soft Bellman equation in v.
(s)) = T log Σ expl ((w, ((u,,,)) + Σ P(s)(s,))0(s"))) Vs
D More on Adaptive Regularization of Adversary
With the adaptive regularizer -DxL(wlle), where
c((T.) sofumax (B(ea))dT. [ra(s,a) re (x, a)) )
(33)
and where in denotes the index of the worst-performing objective at iteration i, i.e. V < V for all k i,..,, K, the Adversary's update rule in Equation (12) becomes:
Wi+1 arg max A(V N (-(w, V )) www=w w) \T DKL((ll))))) DKL (w]lw))
(34)
WEAR
arg max (-AV + At logloo log w., w) (AT + 1) ((x) WEAK
(35)
(- 1- + (1 (1-6) (1) loge + Bog wt, w)) + H(w).
arg max
(36)
WEAK
Twr
This leads to the following closed-form solution 9
(- (-1-8 T
Wh-1 softmax
v= + 3 log wt (1 (1-3) log e(T+))
(37)
Tur
The pseudo-code of the deep RL implementation of ARAM combined with PPO is provided in Section 33
24

---

E
Pseudo Codes
E.1
ERAM
Algorithm 1 Adversary with regularizer for max-min MORL employing exact policy evaluation
Input: initial policy parameter l. initial weight wo, number of iterations T, NPG step size 1), MD step size A, regularizer coefficients: Tw
for 1 to I do
Evaluate current policy and obtain V
0++1 +- 0, + 11 (0.) Eke w/ VoV Tm
update Learner's strategy
Wt+1 softmax 1- 3log Wi
update Aduersary's strategy in closed form
Tw
end for Return: TT: WT
In the tabular case with softmax policy, the update simplified as
To (als) x (als)) expl 1
(s,a))
(38)
In the deep learning setting, the 0 update can be replaced with PPO 49 and the corresponding update is seen Appendix E.3
E.2 ERAM with Approximate Policy Evaluation
Algorithm ERAM employing approximate policy evaluation
initial policy parameter fg initial weight wo. number of iterations T, NPG step size n), MD step size A, regularizer coefficients: Tw
Input:
for t = to T do
Obtain approximate policy evaluation TH. for current policy me
O +- 0, f) Σk k= wi (k) v update Learner's strategy with V egg. 39
Wt+1 softmax(
1- v
V 3 log w.)
> update Adversary's 's strategy
Tw
end for
Return: Tr. WT
In the tabular case with softmax policy, the update with approximate policy evaluation is simplified
Ta (als) x (To, (als)) exp( 1 - a OT (s, (s,)))
(39)
In the deep learning setting, the update can be replaced with PPO update is seen in Appendix E.3
44 and the corresponding
25

---

E.3
ARAM with PPO for the Learner Update
Algorithm& 3 Adversary with adaptive regularizer for min MORL with multi-objective variant of
PPO
Input:
policy network my and state-value vector network V initial parameters fu. Φu. clip coeffi-
cient Ectip= initial weight wo, number of iterations T, MD step size X, regularizaion coefficients:
TPPO, Tuc for tor1=11 to T do
Collect samples from To, and update critic buffer Beritic
V. v= Va.
Get estimate of value for current policy with current critic network
Compute oz:
( = softmax (B(sa))ar |ra () k=1
Update Learner's ' strategy with PPO
Optimize (0; ft, we) to obtain 8,+1
Optimize Leritse to obtain Φ1+1 Update Adversary's strategy
(-1-9V V.+ 3 log w/ + (1 - 3) log a
Wi+1 f- sofumax
(40)
Tw
end for
Return: TT. WT
Here, (etip(0; 0c, wx) = F add" [min a) (wx, Ass a)), ()), - tctip, 1 + <clip) (we,, A(s a))} + TPPo H (To (-[s)) with estimated vector advantage (s, a) E RRK, and
heritic( (6) E Bert....rrgc) V (s) Vattaggell]] with the estimated return vector at replacing V starget-
The closed-fore form update formula for Adversary strategy w with the D(wl (c)) regularizer is shown above.
F Supplementary Materials for Section 3
F.1 Existence of a saddle point in
Proposition F.1. If max, min (w, min max, (w, V2) holds, then saddle point of (w, V exists.
Proof. By assumption, max, win (w, ViT) = min max, VT) (1)holds By extreme value theorem, w² == arg min Ax max, (w, VF) ((2) and ~* arg max min (w, V
-(3) exist. (Note that the policy space II A(A) 1s| is compact due Tychonoff's theorem.) Then,
{w*, V 2 min (w. V;")
(41)
max max V (:: (3))
(42)
min max V=) (:: (1))
(43)
-max(w", V (:: (2))
(44)
2(w", V
(45)
Therefore,
(w", V.) < max(w", V (w", V min V S (w, V ) Vu, n.
(46)
This implies that (w", "w",="" -) a saddle point of (w, V.), which concludes the existence of saddle point of (w, V.).
D
26

---

F.2 Proof for Theorem 3.1
Proof. Let (ū, w) be saddle point 6 and for any w A define x (w) argmaz, (w. V.). Let w" be the optimal solution of minimization reformulation of entropy-regullrizee max-min MORL
3
By Theorem 4.2 in Park et al.
137.
if w is any optimal solution of (3) whose objective func- with the domain A" the policy defined by (w]aas)
tion is V V.5
V.
(.)
Qi Pir (c.u) Vir exp
Q (6.0)
exp
an optimal solution of entropy-
7
regularized max-min MORL I where Q and V uir are soft optimal values for scalar reward (w,r). Therefore, we show that v is an optimal solution of (3). This concludes that the induced policy (als)) == exp MORL
C2 (( (4.a))a) (+)) is an optimal solution of eetropy-rrgullrizeed max-min
exp
By the definition of saddle point,
(w. V = (00, V S (w, V?), Vw, n
(47)
In particular, = x (w) by 47 i.e. क is soft optimal policy for scalar reward (w, r). Then,
(w, V min (w', V (::
(48)
w'
min(u'' V. (10) (: n" (w)
(49)
S(w", (=)(
(50)
Sww", (w"(w")
(51)
$ (w. V (w))
(52)
(:. wt is an optimal solution of with objective function V A V.T(()
(,, V (+))
(53)
=(w, V (: = x (w))
(54)
Therefore, (w) V = (w", V (mn)), which means that i is an optimal solution of 3 Then, for any s, a,
Vi (s, (8, a) V2 (5)
nu (a|s) = exp
(55)
@T (s, (s,
-V
(s)
(6) (:. definition of x-)))
cxp
(56)
7
V Q (s, a) -V (s)
(---- (5))
exp
(57)
(a]s) (t. is soft optimal policy for scalar reward (w,r)) r)).
(58)
Therefore, ग an optimal solution of entropy regupy-regullrrizedd max-min MORL (T)
F.3 Remark for replacing MD with NPG
Remark F2. The MD update rule 13 can be written as
3 V
Wi+1 (Ie) x ( exp
4k 1, 1....,K K.
(59)
Recall that the NPG update with softmax policy (1I) is
(1-a
QF (s,10)
To, (als) (TO, (als)) exp
(60)
We can observe that the update rules for MD and NPG have similur structures under the softmax policy family. This gives an intuition for why replacing MD on ( with NPG does not appear be absurd.
27

---

G Proof of Theorem 4.1
Note that the strategy of Learner is policy parameter 0,, it suffice to analyze the convergence of resulting policy n == 00.- Similar to [1,, we define auxiliary variables that are needed for our proof.
5o(s, a) = exp( (f.
(61)
(s+1(s, a) (E)((s, 1= Quc.. (8.0)
(62)
No (k) = exp(- -V; (Tw))l
(63)
Kit (k) (kx( -
(64)
(x* w0) ) Nash equilibrium in RG
(65)
Qw,r :=Q & mmx Q (soft optimal Q-value w.r.t. reward (w,r))
(66)
W1,7 :VV="() A max V (soft optimal V-value w.r.. reward (w,r))
(67)
In words, -s and Ne are unnormalized (r(-ss) and respectively. That is, Tr(als) (((s, Vt,s, a and we(k) = (e(4//|] Vi, k.
G.1 Introducing optimality gaps
Optimality gap for æ
We note the i-Lippchitzeess of log-sum-exponential (Ise) function, which was also mentioned in
Define the function Ise(x) == log Σ cx:, For 2, y E Rd
[
(se(v)
(Vlse(z), y)1
(where= = = 1xr + (1 l)y for some E (0, 1), by mean value theorem)
(soflmaxx - m)
e = 1|
5| x y|1,o
vlloo.
d j==
ez
Then, for each 8, a,
log "r"""""a (als) log (a|s) =1 w (8,0)/T w² (s)/T) - (logE((s, a) log (s,-))))
=1( (s, (s, log (1 a)) [+))+(()// log (8, II))
2h (s, a)/T log (s)
+ (see(Qu -e (s, )/T) - Ee a))l
Vo .- (s) Lse(Qu T/) holds for soft optimal value)
< (s, log a) + 10 or (8, a)/a log (x,
(: I.Lipscchitzeeessoffff of lse)
= =21Q
(s,
where the first equality utilized the fact that n²" = RBR(w") (regularized best-response), i.e. soft optimal policy with respect to reward (w", r). and the property of soft value function and soft optimal
@ (s.a) -V7" Vi (0) established in 35
policy (als) exp
Therefore.
|log "t - log क. wello < -1Q log Exlloo-
(68)
In words, the term Q T log Eolooo bounds the gap between policy m. in 1-th iteration and Nash policy T². Optimality gap for
28

---

Lemma G.1. w| w/ I ll log w log w'll bos. Vw, w E inr(( where the logarithm is taken element-wisely and D) denotes interior of set D.
Proof. L. int( (), interior of simplex. and define f(x) log æ1, ...... log FK ! for any E int(A Let a = f(x), f(y) and g(z) fe ...., c
, 1T for any R By the mean
value theorem for multi-variate function 9.
g(b) - (())- [c) a)
where (c) is Jacobian matrix of g at and c= ta + (1 - ttb, t E (0, 1). Specifically, the Jacobian matrix becomes diagonal matrix (c) diag(e ,...,, Then,
(la(b) g(a)ll x (c) a) s ||]
alloc max ..... et
H|b e
allxx
Here, since T4, < (:: n,y E int(A*)) )), = logı; < 0 and b; = log yi < 0. Hence, C to; + (1 t)b; O. These results in m ..... ,..., eeh } 1. By plugging
f(x).
b = fly) above, we conclude that yy - 02|>0 logy - log y for y E int A ).
Due to the lemma G.I suffice to analyze log w' log we
I so instead of I|ue we oloc. Note that wx is the best-response to nT with respect to u Rg since (T" w²) is Nash equilibrium in Rg, and w² can be written as below.
w' arg max - (w. V + Tu ((w)
(69)
WEAM
1
softmax
V
(70)
Tw
Using this,
exp
Kr (k())
log woww"" (k: - loog wa(k) = log
log
(71)
||<5:|]
cxp
V
1/2
Tw
1
1
Vi
log Kic (A:)
(lsee
V - Ise(log K:))
(72)
Tw
Tw
By taking absolute value for both side and applying triangular inequality, log w" (k) log w. (k)l
1
V log (k)] + |(se(
V - Ise Ke)
(73)
Tar
Tio
$ V log (k)) +
V log Kis 1100
(74)
Tul
Tar
(:: 1-Liipshhitzness of Ise)
(75)
By taking mazy for both sides, obtain the following bound.
2
log w" log we lo I
V log Kelloo
(76)
Tw
In particular, combining this bound with the lemma |w=" Welloo log w" log w/ ol I
G.
obtain the following bounds.
2
V
Tw log Killoo
(77)
Tar
Optimality gap for soft Q The optimality gap for soft Q at iteration can be expressed as follows.
||Q Q 1l,o
(78)
Supplementary term
Following [11], we use the following supplementary term which helps to analyze the optimality gap for soft Q.
max(0, (0, min (Q 1 7 log {,)
(79)
29

---

G.2 Recursive bounds for optimality gaps and supplementary term
We establish recursive bounds for the following three optimality gaps and the supplementary term: 1 7 log Sellso (optimality gap for policy (68). 11 Q (optimality gap for soft
Q function), - V Tu log Ke so (optimality gap for (77) and max(0, ming,a (Q
log {+)] (supplementary term, used for optimality gap for soft Q function). After then, following 11]. we establish linear system with these optimality gaps to show convergence.
Recursive bounds: optimality gap for policy For each as,
TTe log ( a) _ a) Talog (1
(:
(80)
= =a( (s, a) log (1(,
(81)
+ (1 - a) (,,s a) (s,
(82)
Thus,
1 log E+tt/lo S <allQu log &o + (1 ax)ll
Q wwarlles lbo
(83)
Recursive bounds:
optimality gap for soft Q function Since æ (thus, is max player and w min-player in our two-player zero-sum regularized game, we cannot guarantee monotonicity of (s, a) in t. Thus, we establish both upper and lower bounds for Q (s. Q=t,-- a) Qutti.r a)
and these will offer an upper bound for !Q Qwiti (s, a)), thus upper bound for ||QT a) Ts+1 (3)
1) Upper bound For each 8, a,
(s, 1 -
(84)
=(w", r(s, + +1B-r((ss V (w - -E (
(85)
=(w" - w r(s,)(ss,a)) + 7 B VV (s')
(86)
BBu E. Me (1)0) @1+ with (8', log xet1 aa))
(87)
= (w" - w1t1 r(s, a)) + B. IT log logglg ( [11]
(d' Q 1 (8, log (41((',a') |E(+1
(88)
(89)
=(w" - w r(t1,
(90)
ty P (1))))) | |T log le Qut qit (o' 1/0 - - log (s )lla - -AA
(91)
-yBe- (110)) al 18) 1 m (s', a') 7 log (s d')] -B)
(92)
In the third line, the second term used V V w², since n" is the best-response to w² with respect to R9 and the third term used soft Bellman equation. In the fourth line, used V (8")
T llog -i, (d',)/T ||| which holds for soft optimal value function.
We can easily upper bound the line 900), (w" W141, We41, a)), by Krmav - w due to
H ölder inequality and ||r(s, a)ll & Krmaz Vs, a where Tmaz = maXg, (Tx(s,)), ()). By (77.
(w" (01,1,r(s,0)
(93)
< Kr <Krmaulle W141lloo
(94)
2K 2Krmax
V - Tw log K141
(95)
Tw
From now, we derive the upper bound for (A).
30

---

For each
+ Flog lle Qu- (0.))/7 1 - r log l1 (s, 1 =T(lse(Q (s, 3/T) Lse(log Ee+1 (s,
(96)
(97)
ST . (s, 1/T r log f1+1 ) )l (:: 1-Lipschitzness of (se)
(98)
= 1Q (8, log (8, 1lo
(99)
$ 1Q log E141ll0
(100)
Therefore,
(A) = =B log lle P( (0=, (6'1)111))))))1) 7og (s'
P(
(101)
SyB,' Pt Q t log llool
(102)
=>11 - T log 11
(103)
From now, we derive the upper bound for (B).
To establish the upper bound, following Cen et al. 11 and Yang et al. [62]. we use supplementary term. For each s, a,
@ Q (s, log (
(104)
min m (Q ( log (og 8,0
(105)
then,
(Quee (8, - r log ((+1(8,a))
(106)
I - 1 w.-1, (s, t log (s)
(107)
S max
min (QTit). (s, log (s)
(108)
s,a
Using the last term, establish the upper bound for (B) as follows.
(B) = - B. P(laa)), m (11s) ( 10:11.. (s', a') Flog =log
(109)
- [max 1 min ( ( (s, 7 log (8,
(110)
=a
T++ 1 (s, (og
(111)
s.8
Combining (95).
For each 103 and 111b, obtain the upper bound for optimality gap for soft Q as follows.
Qi' (s, Q (s, a)
(112)
2K 2Krmaz ||
V Ter logooog + 1 log E1t1
(113)
Tw
+y ma
min Q ( log (s)) 8,a
(114)
=U
(115)
As mentioned, we derive the lower bound for Q (s, a) - a) and finally combine with the upper bound 112 to conclude the upper bound for ||Q (s, a) Q%. (s, a)ll
31

---

2 r (8.a) - (
(116)
=(w= - ((+1.r(s,a) + + (s') - 11 (s')
(117)
=( =(w² w wt+1, (())
+ / ((w", V2 (s')) (w++1 - =² + w", ((T-i(())))
(118)
(wo - r(s, + V (5') - V (5)) + fw" W1+11 Vit ( |M
(119)
(w 11.11 a) |V (s')]} + yE (V (5') -v=r, (5')
|
(120)
= (w0 - wi+1, 0 (8, .)) + E V ir (8') - // (6')
(121)
2 - Qr,mar,h 11 - Wt+1 20 +0
(122)
2 V Tw log ket1 1o00 (: 77
2 Qr.marl
(123)
Tw
=: U B2
(124)
where Qr.mand, = maxa,s,a (s, = K(rmaz +r log 1A) In the first inequality, the first term I-y is from Hölder inequality and the second term is from V (+() 2 (s), Vs since (T", w²) is Nash equilibrium in RG. For simplicity, we denote Qr,mas
Tman + log [A]
I-y
From -UB₂ < Qw (8, Qwit S UB (from 112) and 116)). obtain ||@-- - @w 1100 I (U,
Note that since Tmar I Q Qumaa UB2 dominates the first term in U.),. By combining the upper bound (112) and the lower bound [116 conclude the recursive bound for optimality gap of soft Q function as follows.
1Q - Quitt 70c
(125)
2K 2KQrmmar || V Tw lo41ll + + T log Ert1lloo
(126)
Tw
+7 max
min m (witt) (s, - T log (8;
(127)
8.0
Note that the terms in the right-hand side, which are the terms for t + 1, will be boiled down to the
terms for by using recursive bounds.
Recursive bounds: optimality gap for w For each k = I....,K. K,
V Tw log ke+1 (k)
(128)
=B( K + (1 ()(-) - Bwg - - -11-1)(- (-(-)))))) (:: 66
(129)
- VA - Tw log (k)) + (1 (-)))-VV + -V.t)-
(130)
Thus,
- V Tw log K (I:)
(131)
<8 VV Tw log K2 [k)] + (1 [1- - VI. + Vey
(132)
<B V Tw log kz (k) + (1 -1-3)) - 1Q . -T log log
(133)
where the last inequality is due the lemma 15 in Yang et al. 62). applying with x* (-1s)
softmax(Q". Q (s. and me(- = softmax(log (s, and M Imae (1+2 log IAl following Yang et al. [62].
By taking maxk, we obtain the upper bound for optimality gap of w as follows.
M
|| - V Tw log 1eggeelllos S B1| - V - - log kelloo + (1 3) 1
-log E
(134)
32

---

Recursive bounds: supplementary term
Qwiti (5,a) 1og -i -
(135)
1 (s, ralogEr(s, - (1-
(: 62
(136)
=Q Weeii (s, -
Qwa (s. a( (s, a) - log (((
(137)
To establish a lower bound for the term (witi,7(5,a) a)
Q u (s,
Qutt (8, () Q (s,a)
(138)
=(Quit) ( (8, a) Quit a)) +
- - (8,
(139)
20 2Q (s,
Q ()
(140)
= =(w141- Wt, 1 as)
(141)
2 @r.aar, | we lo (:. Hölder inequality)
(142)
2 Qr,maz.1 log Wi+1 log we (:. lemma G.I]
(143)
Ktt
2 2Q, mmar /1 log k2+11 log 0o (t' |
Wt and I-Lipschitzness of Ise)
(144)
= 2Q 2...ma (1 19)
Tw log Kip Keeloo
(145)
Tar
2Q 7imax, (1 3) (1 V V 10 + V
Tw log Kirll oo)
(146)
Twr
2Qr.man.,, (1 3) M
11 log lel + V= - Tw log riel
(147)
Tw
The third line is due to performance improvement lemma of NPG with fixed reward (Cen et al. M lemma 1), which implies Q (s, a) Q ( 2 0, Vt, For completeness, we provide the statement of the lemma below.
Lemma G.2. (Performance improvement by NPG with fixed scalar reward; adaptation of Lemma
in Cen et al. (11
For 0 < 7
V = v Snd 7e41 (
+ (Tx
where JT+ is a stationary distribution induced by policy Ti-1 and initial state distribution 1744
i.e., dy (s) -11-)) E., Ei=o P (st s(so)u(So).
Pr
As a result, @ (s, a) Q (s, a) 2 for any s, a
The last inequality 1477) is due to the lemma 15 in Yang et al. 62 applying with ग (-1s) softmar Q (8, //T) and TH (-(ss)) somoolo (e(s,
Plugging 147 into 137 results in the following bound.
Q (8,
1 (s.
(148)
Q Wiir ((, a) - Q (s, a) + aQQu, (s, - - - -og (s(s
(149)
2Qr.mar,1, (1 3) 10 log Eooo + V Tw log Relloo)
(150)
Tw +a(Qu,, - log a))
(151)
which implies
(Q (witt) - log (s))))a)sa))
(152)
2Q 2Qr,mar,1 (1 (8) .M 11 - log + 1||- V." -w log Ki loo)
(153)
Tw
-a( (8 (s,,a))
(154)
33

---

By taking maX,,a for both sides,
min (s (8, - 7 Flogootg1ll (1+1(,,)))
(155)
6,0
2Q r.moz. 11 B) M
- 11 Flog + -|1 V Tw log Ki 1oo)
(156)
Tur
a mmin(Q wis (8,a) - r log (8)
(157)
8,0
2QQ.max,11 (1 B) M
110 T fol +11 V. - Tw log Ki 1lo0)
(158)
Tw
+a +a max - min ( 20 (8, logg
(159)
5,a
Since the last line is non-negative,
[0, - min/ ( (8, a) - log (1,
(160)
<a (0-mmnn(20 w (8, a) Eog
(161)
2Qr,maz,h, (1 3)
M
110 T log Eo + +| V - -T log Kr olo)
(162)
Tw
G.3 Linear system for optimality gaps
For simplicity, we denote the three optimality gaps and supplementary term as follows.
G(m) ==1l@ r log Eo
(163)
G(Q+) : ==110 -0ii-1lo
(164)
G(w)) : V Tw log K4 lloc
(165)
H; := max (0, min ( mist 7 log Et)
(166)
The recursive bound for these G(TL), G(Qr), G(Q)), and H, are summarized below. 2K 2KQ TT, G(w++1) + G((Te=+) + 7711411
G((Q+1) <
(:: 125
Tw
G(T++1) SaG((T)) + +(1 (1-a)G(Q2)
S(a + (1 - (1-))))(m)) + (1 - a)( 2KQr,man G(w)) H,H,)
Tw
by the bound for G(Q++1) above)
G(w++1) S3G(wr) + (1- M G(m))
(:: 134
H4n SaH, 2K BKMQQ.ma rr.ma 3) G(
2KQ m. (1 B) G(wi)
2KQ
(:: 160
The This can be written into the following linear system.
Tw
G(mT+))
+ (1 a0 M(1-8)
2KQ maz (1-a)
(1 (1-a) a)?
G(
Tw
G(w++1)
3
G(w) Hi
(167)
Het1
2KMQ- 2K 10-00
2KQ max (1-8)
TTw
Tu
where M Tmuo (1o 2
(1->)²
T-
Aro+1
Let the transition matrix above be A(y, A). Since A(7, >) is non-negative matrix, by Berron-Frobente Theorem (25). A(n, X) has eigenvalue which equal to spectral radius. The characteristic
34

---

polynomial is simplified as follows.
[(x) (xr a){ (a (1- - 3)
(168)
=:/1(z)
2K MQ r.maz
- a)) 3)}
(169)
TTw
=IX
2K LKMQT T max (1 (1- - (2x -23)
(170)
TTw
=;((a)
Take step size 17 and X to satisfy a = 1 1- e and B = 1 - 62, Le., take 1j = =(1-2) and A = 22
(T)
Note that the polynomial f1 has zeros at a (1- < Let f2(x)) fi(x) - a)) - 13)
((1=a)(
then (2( = (1 - 7 - X)(1 - aa)(1=1 - :3).
2K M MQr.max
2K 2(rmar + T log [A])
X
Qr.maz
(171)
(1-
TTw
TTm
4KQ2, T.maz
(172)
TTw (1-
1 1-7
(173)
3
by assumption on Tw. Therefore, fa(1) > 0 which implies that the zeros of fz. namely æ1 S 22
are less than 1. This implies that the first term of f. i.e. (x f2))),, has three distinct zeros
at a = 1- c < a + (1-a)))) a)7 = c11 7) 3 = 1 e² for c < r. Furthermore,
(x (f)(z) - X(1 - a) B))
(1) c(1-9- (11--- X) where X is independent
of For the last term, g(1) has value ? 4KMQr. r.max 5 < 7 7)65 For < 5,, f(1
TTe
3 (1-)) > O. Note that since 7, < 1, e already satisfies < 4. Therefore, 22, the maximal zero of (e (2- moves to x42 the maximal zero of f(x) = (x a2) g(z) which is still 2/2 < 1(Otherwise, f(z) S 0). Denote this z²- as p(n, A), which is the spectral radius of A(n, A).
c1-17- X) g(1) > e(1 7 1-2) 5 7) > (22
Specifically, for x= 2
2 direct calculation results
f(x) =
Y
X)e²
2
3-7- 7
37
1
X)e
+
1
(174)
2
4
2
8
>( 1 7
--7 7
37
11
Jeje (: xx x1-
-
(175)
6
4
2
3
3
d
= =(2(1 7) - (4 + 5y - 672 )c)
12 0
(176)
by assumption
2(1->) -693
Therefore, p(n, A) < 1 + <1
G((Tt)) G(wn) The linear system (167)
For simplicity, let x,t
leads to
H,
G(Te), G(w,), H, S |x || S p(n, \ |
(177)
for some norm. Finally, by (68)
125) and 173). conclude the following.
log म log ne 11o0
xoolp(n, A)
(178)
7
2
| - -wllox
< |1ol|e(T, A)*
(179)
Tw
((1-)) + 27)]|xxlll((n.A X)
1Q - Qua 11.0 5(
(180)
3M
where p(y. A) <1 1 - _ with choice of 1) <(1-7) and x (
2
35

---

Remark G.3. The condition for e is e < cn == min 2(1-)) 7 can be simplified with
lighter bound. Since 3 < 4 + 5y 6n < 121 for (0,1), -45 S 2(1-7)
and 4407 67 - 7} 4407-612 In particular, we can take stronger condition
2(1-2)
thus, 60 min 2(1 1)
20-7)
c << = 48(1-1) Condition for X becomes
then, from x= Tu(1-ay 2. Tw'
X satisfies the
121
condition for Condition for becomes < () which also satisfies the condition for by nr < <.
H Proof of Theorem 4.3
Now suppose that we can access only an approximate policy evaluation (i.e. estimate for soft Q- function). Let an approximate policy evaluation for given π with reward (w, r) be Q We assume that ||@ū,, - I 6, VIT, w, 8, a (Assumption J.2
We conduct similar analysis in Appendix G with approximate policy evaluation and derive linear system.
Similar to the appendix
define auxiliary variables.
Eo(s, a) = exp(("". (s, (/1))))/))11ll
(181)
11 a) = (E,(s,)))) a) -- Que (2,0)
(182)
Ro (k) = exp( V. /Tw) (lmook
(183)
Ret1 (k) = (R, V.
(184)
Te. policy and weight at t-th iteration
(185)
(x" Nash equilibrium in RG
(186)
2 Va,- exact policy evaluations
(187)
Q Wirt
V approximate policy evaluations
(188)
Lec. estimators for soft optimal value for given policy æ and reward (w, r).
(189)
Q v approximate policy evaluations
(190)
Lee. estimators for soft optimal value for given policy æ and vector reward r.
(191)
Q = == m,
(wn) A max Q (soft optimal Q-value w.r.t. reward (w, r))
(192)
VMr = (w)(w) A max W (soft optimal V-value w.r.t reward (w, r))
(193)
W.7
Note that <((-(s) (s, (I, also holds for the case with approximate evaluation by the definition of &x.
Performance difference of NPG with approximate evaluation
Before deriving the bound for the equation above, we first adapt performance difference lemma with approximate evaluation to our setting.
Performance difference for va with approximate evaluation becomes
Vš++1 (s) Viele (s) W1+1.7
(194)
(s) ViTe+ (s) + VIT (s)
V (s)
(195)
2
(wi41 Wt, VI--
1
Q
11 (::
lemma 4)
(196)
2 Vr.mar 1|Weet,,1Wtt11 - -weloo
(197)
- ? 2
Qr.mar,l |1 willos
8,
(198)
36

---

and performance difference for Q taa with approximate evaluation becomes
Q o ( a) Q wi.7 - (5,a)
(199)
[wi+1 We, WG, ((,r() + 7B [V (5') - Vilee (s')]
(200)
2nd
KrmazllWet - wello 7QT,maz, //w6+1 wello- 1
(201)
270
Qr.mo 1101+1 welloo 1 1-7
(202)
H.1 Recursive bounds for with approximate evaluation
Recursive bounds with approximate evaluation: optimality gap for policy For each (s, a).
( log log
(203)
- Ta lor a) - (1 - a) wr, (8, (:: 1821
(1-a)
(204)
=a a) log ( (1 aQ (8, - (8,
(205)
=a(Q% (8, (s, log (o))
(206)
+(1 ( (s. - Qwa (s) + (1 a) - (s,
(s)
(207)
Thus,
|1Q log Eog S all log (1 a)
Q bloc (1 a)ō.
(208)
Recursive bounds with approximate evaluation: optimality gap for soft Q function 1) Upper
bound
Similar the case with exact evaluation, start from the following identity.
( - Quitl
(209)
=(w" - ((,,,)(s
(210)
+7 log ||e Q5= (s' (6'.)// log (lEe+1 (s', (s') - log (s',
(211)
(212)
2 2Kr 2Krmar V - Tw log 1l
(213)
Tw
+>|lQ=* - T log 11
(214)
+7 max min fain(Qum:t (Q#:t) (s, T log (s,
(215)
8,0
where the last inequality is derived by the similar logic in the case with exact evaluation.
2) Lower bound Similar to the case with exact evaluation,
2Q 2Qr.max.ly
Th a)
||
V
Tu log R 1loo-
(216)
Combining the upper bound and the lower bound, obtain the following upper bound for the optimality gap.
11 Qut+t
(217)
2K OKQr,mar
V
Tw Ret a/o0 +11 log 20
(218)
Tw
+7 max min
m 10:41 (s, log 1og
(219)
8.0
37

---

Recursive bounds with approximate evaluation: optimality gap for w For each k =1,..... I,...,K. K,
Vil log 1k+
(220)
= (VE-) + (1- B) V Tw T log R4 (k) () (:: 184
(221)
= VV, Tw log Fig (k:)) + (1 B) ( + V[t) + (1 - ()( V V
(222)
Then, for the same logic in the case with exact evaluation, obtain the following bound.
|| V - Tu log Fe+ 11100
(223)
M - < V Twr log Rieloo + +1 ()- -10-))
log Eo Eolgol (1 (1-3)6
(224)
Recursive bounds with approximate evaluation: supplementary term
Q 10 ( - r log Ee+ (8, a)
(225)
Q (8 a) - Ta log (( a) - -1-aap a (8, (::018)
(226)
Qwitl (8, a) - Ta Ec(3, a) - (1 - (1-a) (1 a) - Q (s, + (s,,)(
(227)
- (s, a) (s,aa
(228)
+a(Q (8, a) - Ta log (e a)) (1 () W..T (8, (s,
(229)
Modify 138) with approximate evaluation as follows.
Q (s,a) - a)
(230)
-(Q (8, a) Q (s, a)) (QTH (s, Q (s,a)) a))
(231)
278
2 201n ( - Qutt a) Qr.aaz, |11411 welloo
(:: (19))
(232)
275
-w0+1 we, 1. Q m,,z || weel
(233)
1-
278
2 - Qr.mar 1 - wolloo -r,,maaaa... 1//611111111
w/ 1100 - 1-7
(:: Hölder inequality) (234)
278
2Q, T, mazzz
log w1+1 l1
log we 11
(:. -eemma G.I
(235)
1
1-7
276
Ra
2 m llg Re41 log Relloo
(t:: W/ =
Vt and I-Lipschitzness of Ise)
Re
(236)
4Q 4QT.mand1s (1 (1-
278
Tar log Rz
100000
(237)
Two
1 1-7
4Qr,mand1 (1 33
V
V Je
Te
V 1ox0 +|| V
Tan log Ri |lo0)
Tuo
(238)
2-8
(239)
1-
4Q r.maadds (1 (1- ()( M
2
(8+ 7
10
Eog +
- - log Rellz))
(240)
Twe
38

---

Plugging 240 into 229 obtain
Q 1.1 (8, u) T log 1 (8,
(241)
2 4Q 4Qr,max,t, 3) (5 + - 11 u",r - log + +11 V - Twr lo [loc)l)))
M
2-0
(242)
-
+a(Q (8, Ta log Eo(3, a)) - (1 - a:d
(243)
4Q 4Q..maz,1, 3) M
1 log Eolloo +11- -V -w log 22
(244)
Tw
+a(Q (8, Ta log (())
(245)
27 4Q 4QT.max.d - B) ( '
(246)
5M
Tw
By reversing the sign of both sides, taking m and max(0, +) as in the case with exact evaluation, we obtain the following bound.
max (0, min
m
(0 (8, log ((,
(247)
8,0
max min ( (s, Tog
(248)
8.0
4K IKQr 07,aar() (1 (3)
M
+
11 log Eell + V - Tw Rog
(249)
Tw
21 tn
4KQ (1 3) )78
+ max(0, ((1 (11-a)) a1
(250)
Tw
H.2 Linear system with approximate evaluation
For simplicity, we denote the three optimality gaps and supplementary term as follows, with slight abuse of notation.
G(m)) ==1 - log El
(251)
G(Qr) : == - -QW,
(252)
G(w:) : - V Tw log Rs lloc
(253)
H, :=::mm: max(0, (0, min( min(Qur wist T log E.)
(254)
2KQr. r.mas G(w++1) 7 7
G(Q++)) S
(:: 217
Tvo
G(T(+1) S aG(T)) + (1(=)) (1 - a).
(:: 2008
2K 2KQT.mar G(w)) +HHH) + +(1 a)6
(a + (1-a + + (1)
Tw
(:: by the bound for G(Q++1) above)
G(w++1) < (G(w:) + (1- M G(TT) + (1 (1-3)0
(:: (244
4KMQ (1 B) G(TT) +
4KQ 1x.mmmax( 3) G(wi)
H41 S aH, +
(:: 250
TTw
Tw
27
4KQr.man (1 3)133
maax(0, ()
138
Tur Therefore, the resulting linear system becomes the following.
G(T++1) G(we+1) Hex
a + (1-a) M(1-9)
2K max (1-a)
(1 x)7 G(
3 4K mo (1
G(wz)
+ Ey
(255)
4KMQ. -
Hi
a
39

---

where
1
y
1 1 8
(256)
max (0, (1 a1) 27
4K 1r.
M Tmaz (1 + 7) 2r 7) log |A|
T1
a
1
and
(257)
(1 - -7)
1-7
ATw
Let the transition matrix above be A(17, A). The characteristic polynomial is simplified as follows.
f(x) = (z - (a + (1 - a)))))) [x - a) 2KMQT (1 aa - (x -a)
(258)
(259)
TTw
4KMQ, r max (1 - aa (3 3) (x 1 -23)
(260)
TTw
p(n, A), the spectral radius of Å(n,, A) satisfies p(n, A) < 1 う 1 with assumption X 2K MK...mm 21-7)
For the same analysis in Appendix
- and ύj =(1-2) X
[1- with
e 6D == min( 127 21 1 >}. T/w
More tightly, since 3 4 + 117 12x² <
313 for
48
7 E (0,1), 1+11--12 - y and we can take tighter condition S c c == min 96(1 1
2(1-7)
313
27
To satisfy the condition for required condition for it suffice for 1/ and À to satisfy the range X < 5
and 1) < (0(1-))
(Te)) G(wr
Using i(n, A) < <1- & and by letting x,
(slightly different from Gince this x, contains
He
different auxiliary variables), recursive application of the linear system (255) results in the following.
X S A(m, + (I+ ... A(n, 10
(261)
which results in
G(T,), G(wz), H1, < |x,|| Sp(n, |) |1 + 1 - p(n A)
p(n, 2) |1
(262)
Sp(n. 2)0||>0|1| +
1 1 1-p(n. A) 1/3/116
(263)
2112/11
+
c² 8
(264)
for some norm. Therefore,
2
(11x0|1<(7 X) 211y11 8)
|| log n'" log Tellox
(265)
7
2
(11x011p(1). 2) + 21|y1|
Ilw0 w|1o0
5
8)
(266)
Twr
22
[[(1- -7)
2|/81
11 - T @wi
5(
+ +2)) X pp( 2) +
8)
(267)
3M
c²
where p(n. A) < with choice of 1 <(1-7) and X Fu (1-
2
I Proof of Corollaries 4.2 and 4.4
Proof of Corollary 4.2 For each i = 2,3, to achieve C,[p(n, A)]* I Coce, it suffices to find t
which satisties Cspp(n 2) C 11--- - Eaco. Then, log C₁ + log(1 5 = logg Eace- Since
log(1 5 x - for small e, this results in t (log C. log cace) 0 log -.
40

---

Proof of Corollary 4.4 For each i = 1,2,3, to achieve Ö A]I + D S 2Eace with
8 - Eace suffices to find which satisfies [, A)}' + D < C, 21 + 2aace D
i.e. C e Cace. For the same logic in the case of exact policy evaluation, iteration complexity becomes at most O log )
The derivation and analysis for sample complexity is in Appendix
J Sample Complexity under Approximate Policy Evaluation
Assumption J.1. We assume access a generative model that allows sampling next states from P(. 8, 8,a) (.a)foo for any (8,a), as in Li et al. (28).
Assumption J.2. For any given error bound ö, policy and weight E A we have access to an estimate Q and Q7 of value functions Q and Q which satisfy [|Q - Q < 5 and
|| 1f <, respectively.
As discussed in et al. (28). Assumption can be achieved for any fixed и and any k-th objective within error 11 - Q7, bloe I with high probability if the number of samples per each state-
actions pair exceeds the order of Ô (1-7)-82) under Assumption J.1 By employing fresh samples for the policy evaluation for each objective at every iteration and using union bound, ||ē; - Q7 = max; 1 lo, < 8 is achieved with high probability if the number of samples per each state-actions pair is exceeds the order of Ô Ō(1 (11-))8))) )- In partieular, since Q is soft value function with scalar reward (w, r), we need samples exceeding the order of Ô
(1 (1-788 to
estimate. Since δ ( (1= (:: w update requires vector value +++ (1-7)982
(: π update
requires scalar value 2 =Ō ((- ). we used Ô (1-71-88 in Corollary 4.4
K Discussion on Two-player Zero-sum Markov Games
We provide a detailed discussion on how our framework relates to the literature on two-player zero-sum Markov games (2pOs MGs).
Problem Settings. Our target problem, eetropy-regularized max-min MORL, be viewed as a two-player zero-sum Markov game in which the minimization player (the adversary) has a state- independent policy w, and the transition is determined solely by the maximization player (the learner), since P(s'|s, a) independent of w. We also aim to find an Cace- FReE as considered in several prior works.
Algorithmic Settings. Table summarizes the algorithmic settings of method and existing studies on two-player zero-sum Markov games. Here, "symm" denotes symmetric regularization and learning-rate structures, while "asym" denotes asymmetric ones. In 2p0s MGs, symmetric regularization is natural because both players use policies as their strategies with cumulative entropy H (T) the order of log LAI In contrast, in ERAM, the adversary uses weight as its strategy 1-7
with com-cuuulaiive entropy H (w) on the order of log K, which justifies the use of asymmetric regularization coefficients.
We carefully reviewed the proof of Theorem in Cen al. 12 and found it to be applicable to the MORI. setting under symmetric learning rates and regularization (1) X, Tw) by using 1 (w)) or by absorbing 1-,, into Tw. thereby yielding asymmetric coefficients. Nevertheless, a direct application remains challenging because our setting lacks these symmetric conditions. Our proof instead relies on asymmetrie learning rates for last-iterate convergence (see Section 4) and asymmetric regularization (see Algorithmic Settings above).
Techniques for Proof.
41

---

Table 4: Comparison algorithmic settings in two-player zero-sum Markov games.
Reference
Entropy Reg.
Reg. Coef.
Base Method
Policy Param.
Learning Rates
Daskalakis et al.
13
X
none symm
PG PG
direct
asym
Zeng al. 64
softmax
asym
Wei et al.
58
V
OGDA OMWU NPG, MD
direct
symm
Cen
12
symm
direct
symm
ERAM (Ours)
V
asym
softmax
asym
The result of Cen al. (2023) applies MORL in the symmetric case because its key step, Eq. (14), has a state-dependent right-hand side (RHS) that ultimately bounded by || || removing all state dependence. Hence, both the state-dependent policy in MGs and the state-independent w in MORL satisfy the same recursive bounds as Lemma 2-4 of Cen et al. (2023). In our setting, however, since w is already iate-indeeen and there is only one RL learner, find that adapting the proof in Cen et al. (2022) is sufficient for our analysis.
Convergence Speed. Cen et al. (2023) provides a convergence error bound of O((1 (1 7)m/4 4)* while our method achieves at most -((1-e2 22/2)") S 0(1-
The proof in (1 7)/1/4 Hence, convergence rate is comparable to that of prior work and does not conflict with their results. (Note that (1 21 does not violate (0, co 48(1 121) (Remark G.3). for sufficiently close to 1.) This discussion highlights that while the mathematical foundation of ERAM aligns closely with existing analyses in two-player zero-sum Markov games, asymmetric learning-rate structure and the non-monotone nature of value gradients in RL motivate a distinct line of analysis tailored to the MORL framework.
-
Appendix G shows that if we take 2 (1 - 7)2 we have 1 Ar
L Supplementary Material for Numerical Results in Tabular MOMDPs
For each tabular MOMDP, transition matrix and reward function is randomly generated. The reward function has range 20). For all experiment, we used y 0.95, T = Tu 0.05, 0.01 and 0.0001. The following graphs show last-iterate convergence behaviors for value Ver, and weight w. For simplicity, report we (1), the first element of the weight w, iteration t.
The figures below show the last-iterate convergence behavior values (v and the first component of weights (wx(1) resulting from Algorithm
(1S), A) (2
(1S). A|, K) = (3,3,6)
(1 AA, = (4, 4, 4)
Figure 5: Last-iterate convergence of values in three types of MOMDPs, each with 50 randomly generated instances.
42

---

([S). |AI (2,
(15), [) = (3,3,6)
(1)). AI, = (4,
Figure 6: Last-iterate convergence of (((1) in three types of MOMDPs, each with 50 randomly generated instances.
We also evaluated ARAM in tabular settings. To demon- strate the effectiveness of ARAM, we considered two types of tabular MOMDPs with increased number of objectives (K = 10): ([$), [A], K) = (2,2,10) 10) and (4, 4, 10). We used 7 0.95, T Tw 0.05, 7) 0.01 and À = 0.0001. Similar to ERAM, the Nash gap of ARAM decreases rapidly over time in both environments, as shown in Figure Each curve represents the average over 50 randomly generated instances, with shaded areas showing standard deviation.
Nesh
20
10
0
1000
2000
3000
4000
5000
Step
Figure 7: Nash gap for ARAM
M More on the Traffic Signal Control Experiment
M.1 Traffic signal control environment
We evaluate our method in traffic signal control simulation environment with three scenarios: Base-4, Asym-4, and Asym-16. Each scenario simulates a four-way intersection with four roads (North, East, South, and West), where each road consists of four lanes. Vehicles arrive from the four directions with specified inflow proportions and can proceed straight, turn left, or turn right.
In the Base-4 scenario, 75% of arriving vehicles proceed straight, and the remaining 25% make left or right turns with equal probability. Among the trright-goiin vehicles, the proportions from West to East, East to West, North South, and South North are [0.1, 0.1, 0.4, 0.4]. The reward 4-dimensional, where each element represents the negative total waiting time on a road. The simulation includes 10,000 vehicles and is trained for 100,000 time steps.
The Asym-4 scenario shares the same reward structure as Base-4 but introduces asymmetry in the traffic inflow, which is set to [0.4, 0.1. 0.4, 0.1] across the four directions. Additionally, the turning probabilities vary by incoming direction to better reflect realistic traffic patterns. The scenario uses 4,000 vehicles and is also trained for 100,000 time steps.
The Asym- 16 scenario uses the same asymmetric inflow Asym-4 but increases the granularity of the reward by assigning one reward per lane, resulting in 16-dimensional reward vector. Each element corresponds to the negative waiting time of specific lane. This scenario includes 4,000 vehicles and is trained for 200,000 time steps.
For completeness, we provide the max-min performance under the metric of Park et al. 37 in the following table (see 5). Let π denote the max-min optimal policy, and let n seed, denote the final policy obtained from training with fixed seed seed, The metric used in the prior work [37 averages over all seeds and then takes the minimum, i.e., ming 1 Σ Egsoed, |E, 7r a.)). In contrast, our metric computes the max-min performance for each seed and then averages the results, i.e., E ming E,nea Σ,, 7"re(8t, 4+)]. . If x seed, = = seed, T², the value
vectors Vo are identical to V* and both metrics yield the same measurement. However, seeds seed, are not exactly the same, the metric in the prior work averages returns that are from different policies, which does not accurately reflect each learned policy's 's true performance. Thus, evaluate the max-min performance of each policy separately and then average the results.
43

---

Environments
ARAM
ERAM
Park et al. 337
GGF-PPO
GGF-DQN
Avg-DQN
Base-4
-1140
-1387
-1455
-1603
-1838
-2774
Asym-4
-2589
-2568
-3510
-3094
-2670
-4245
Asym-16
-14399
-15259
-17754
-19569
-16477
-27499
Table 5: Max-min performance in traffic signal control. Bold: best; underline: second-best.
M.2
Experimental Setup
The PPO hyperparameters are listed in the table below. We use the default network architecture and optimizer settings provided by Stable-Baseliness 44. For entries with multiple values, the best-performing one was selected based on validation performance.
PPO hyperparameter
value
entropy coefficient value loss coefficient gae coefficient clip range optimizer hidden layer sizes for actor network hidden layer sizes for critic network
le-6
0.5
0.95
0.2
Adam
[64, 64]
[64, 64]
activation function epochs
Tanh
2, 4, 6, 8
rollout steps
64, 128
batch size
16, 32
learning rate
0.001, 0.002, 0.003
Table 6: PPO hyperparameters for ERAM and ARAM
The main hyperparameters for ERAM and ARAM are À and B Tw). which appear in the closed-form updates of in both ERAM 13 and ARAM (40). The best-performing hyperparameters were selected for each traf- {0.01, 0.25, 0.33, 0.5, 0.67, 0.75, 0.99) and
(i.e.
fie scenario from the search over 8 E {0.001, 0.002, 0.003, 0.01, 0.02, 0.03, 0.1, 0.2, 0.3). and their influence is analyzed in the ablation study. In addition, all experiments were conducted machine equipped with two Intel Xcon Gold 6238R CPUs.
In each traffic scenario, the selected hyperparameters are listed in the following order: (epochs, rollout steps, batch size, learning rate, X, ().
ERAM
ARAM
Base-4
(8, 128, 32, 0.001, 0.2, 0.67)
(8, 128, 32, 0.001, 0.1, 0.67)
Asym-4
(4, 128, 32, 0.003, 0.03, 0.67)
(4, 128, 32, 0.003, 0.03, 0.25)
Asym-16 16
(8, 128, 32, 0.001, 0.2, 0.5)
(8, 128, 32, 0.001, 0.2, 0.01)
Table 7: Selected hyperparameters for ERAM and ARAM in each traffic scenario
M.3 Ablation study
As mentioned above, we conducted an ablation study on À and X (then, Tu = ( 1)/A is automatically determined), which are the main components of the closed-form update rules for w in both ERAM (3) and ARAM (40). Figure & presents the ablation study À and B for ERAM and ARAM across different traffic scenarios. Each heatmap visualizes the minimum return obtained for varying (A, 3) combinations. In each heatmap, red indicates lower minimum return, while blue indicates higher minimum return.
44

---

-1300
0.001
0.002
-2000
Mín return waiting time)
0.002
(-wa taiting time)
0.003
0.003
-1400
0.01
0.01
0.02
0.02
-1500
-4000
0.03
0.03
-1600
-6000
0.3
-1700
0.01 2.303 0.5 0.670.750.99
0.01
0.25
0.33
0.5
0.670.750.99
8
ERAM Base-4
ARAM in Basc-4
-3000
-2800
Min return Wa King time]
3500
-3000
(-walting
0.01
4000
-300
-4500
3440
-5000
5500
0.3
0.01 2.0.0. 0.5 0.670.750.99
0.01
0.25
0.5 0.670.750.99
ERAM Asym-4
ARAM Asym-4
0.001
0.001
0.002
20000
Min return (- Waiting time)
-1600
Min retum wwatting time)
0.003
72500
17000
0.01
0.01
25000
0.02
-18000
0.03
27500
-9900
-20000
32500
0.010. 250.33 0.5 0.679.750.99
0.010.250.33
0.010.250.33 0.5 0.670.750.99
ERAM in Asym-16
ARAM Asym-16
Figure 8: Ablation results on À and 3 for ERAM and ARAM across traffic scenarios
45

---

N
Additional Experimental Results
ARAM
ERAM
Park et al. [37
GGF-PPO
GGF-DQN
Avg-DQN
Spec. Cons.
31
27
27
27
22
4
MO-Reacher
25.27
25.13
23.54
24.32
23.90
22.44
Four Room
1.80
1.56
1.02
1.47
0.02
0.12
Table Max-min performance in species conservation environment, MO-Reacher environment, and
Four-room environment
The Species Conservation environment (SC) [51] com- monly used benchmark in MORL, aims to promote the conservation of species in an ecological simulation via multi-objective reinforcement learning. This environment includes two species: sea otters (an endangered predator) and northern abalone (their prey). The state space captures population information, and the action space consists of five discrete actions. The agent aims to achieve fair conser- vation of both species by treating their population levels as a vector-valued reward.
X
2
X
X
X
S
X
X
X
2 2
X
2
MO-Reacher environment (MR) [20] is a multi-objective extension of Reacher [56]. This environment has 6- dimensional observation space containing the sine and cosine values of the central and elbow joint angles, as well as their angular velocities. It has a discrete action space consisting of torques applied to the central and elbow joints, where each torque can take one of three values: -1, 0, or 1. As an extension of the standard Reacher environment, MO-Reacher includes four targets. The reward function defined based on the distance between the tip of the arm and each target as follows: 3.
Figure 9: The map for Four-Room envi- ronment
(tip's position) - (target i's position)||
The Four-Room (FR) environment 20 contains two types of collectible items, labeled 1 and Figure 9 shows the map used in the Four-Room environment. The agent starts at the center of the map, marked as "S". Cells marked "X" represent walls. Each episode terminates after maximum of 200 steps. The agent collects items 1 and 2 throughout the episode, and the numbers of each collected item constitute the wvo-dimensional objective reward.
In all environments, we trained for a total of 100,000 timesteps. Table demoonstrtts the superior max-min performance of our algorithms in all environments.
O Limitations and Broader Impacts
The max-min criterion works best when objectives are homogeneous, such as having the same units. Extending it to heterogeneous objectives is an interesting direction for future work. While our theory focuses on softmax policy parameterization, analyzing last-iterate convergence under more general settings, such as linear function approximation, remains valuable research direction.
Our work max-min MORL may have several broader impacts. The proposed algorithm can be applied to real-world resource allocation problems where fairness or robustness across competing objectives is critical, such as transportation, healthcare, and public infrastructure. Moreover, the max- min criterion may contribute to more robust preference modeling in RL fine-tuning of large language models (LLMss, especially in the context of preference alignment. In such applications, max-min training can mitigate the influence of outlier preferences and help ensure consistency across diverse feedback signals. Because our algorithms are both memory-efficien and computation-effie -effccceen,,,,,,,, may be particularly suitable for training large-scale models under practical resource constraints. While our method is general and does not directly involve deployment, we note that any reinforcement learning system deployed in sensitive domains should be carefully audited for fairness, safety, and long-term behavior. We believe our approach supports these goals by improving robustness in multi-objective Docision-making
46


Reviews:
[{"review_id": "aRMTtVv7YA", "reviewer": "Reviewer_rcWu", "summary": "This paper introduces a game-theoretic framework for multi-objective reinforcement learning (MORL) with a max-min criterion. The authors reformulate the problem as a two-player zero-sum game and propose ERAM, an efficient single-loop algorithm with provable last-iterate convergence in tabular settings with softmax parameterization. They also present ARAM, a variant with adaptive regularization for improved performance. The method achieves gains in computational and memory efficiency over prior work, such as Park et al. [2024], and demonstrates better results in traffic signal control.", "questions": "1. Could you explain in more detail why Park et al. only provide average-iterate convergence? I did not see this explicitly mentioned in their paper.\n\n2. Could you discuss the relationship between this work and existing last-iterate convergence results for zero-sum Markov games? For example, would min-max MORL be a special case of those settings? How does your result compare to theirs? See Faster Last-Iterate Convergence of Policy Optimization in Zero-Sum Markov Games, for instance.\n\n3. Could you elaborate on the key theoretical contributions of this paper?", "limitations": "Yes, the authors have addressed the limitations and potential negative societal impacts of their work. Another limitation is that the theoretical analysis is restricted to tabular MOMDPs with softmax parameterization, and the sample complexity guarantees are not perfect.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The minimax game formulation proposed is novel in the context of MORL.\n2. The paper provides the first last-iterate convergence guarantee for softmax parameterization in tabular MORL.\n3. The proposed algorithm is clean and insightful, and a practical variant is also presented.\n4. The experimental results demonstrate improvements over prior work (Park et al.), with better computational and space efficiency.\n\nWeaknesses:\n1. The minimax theorem result feels standard. It seems that by representing the policy in the occupancy measure space—where everything becomes convex-concave and the policy space is convex and compact—the result could follow directly from von Neumann’s minimax theorem.\n2. The theoretical analysis for the tabular setting largely follows standard NPG analysis. The sample complexity bound $(1/\\epsilon^6 \\epsilon_{\\mathrm{acc}}^2)$ is not particularly strong.\n3. The use of entropy regularization in ERAM for achieving last-iterate convergence is fairly common.\n4. The writing could be improved. The theoretical sections, such as Section 3.1, would benefit from clearer structure, with formal statements of lemmas and proofs; the current presentation is difficult to read. The overall organization could be significantly improved: for example, I suggest moving the related work section earlier in the paper. Since ARAM is the central algorithm of this work, it deserves more emphasis—ideally its own subsection rather than being described briefly in the related work. For Section 6.3, the comparison with Park et al. would be stronger if accompanied by a more detailed description of their algorithm in the appendix.\n\nMinor issues:\n1. It is unnecessary to repeatedly cite basic results from convex optimization or information theory whenever entropy/optimization is used.", "was_revised": true, "final_justification": "The authors have addressed all of my concerns, and the paper provides insightful theory along with interesting experiments, making a valuable contribution to the field.", "rebuttal": "**Importance of Minimax Theorem 3.1 (Weakness 1)**\n \nWe agree that, when formulated over the space of occupancy measures $d$, the problem becomes a convex-concave optimization and the minimax theorem can be applied more directly. While this formulation is theoretically elegant, we instead choose to express the problem in terms of $(w, \\pi)$, where optimization is carried out in the policy space. This choice allows us to leverage advanced policy optimization methods, such as PPO, and serves as a foundation for applying minimax-based reasoning in deep RL settings.\n\nIn this formulation, the minimax result is non-trivial because the value function is not concave in $\\pi$. Our Theorem 3.1 shows not only that the max-min and min-max values coincide, but also that they share the same optimal solution. This insight provides a theoretical justification for solving the max-min MORL problem via direct policy optimization, bridging minimax theory with practical deep RL algorithms.\n\n\n\n**Regarding Sample Complexity (Weakness 2)**\n\nWe would like to clarify that our goal is not to claim an improvement in sample complexity over standard NPG analysis. Rather, our intention is to demonstrate that it is possible to obtain a solution to the max-min MORL problem under a finite sample complexity regime via our algorithm. This is included to ensure theoretical completeness and to support the validity of our overall framework.\n\n\n**Novelty of Regularization Technique (Weakness 3)**\n\nWe agree that entropy regularization is a fairly common tool for achieving last-iterate convergence. Our work takes  one step further by introducing an adaptive regularization scheme (ARAM) that captures correlations across objectives. This design is motivated by the practical challenges of real-world multi-objective problems and, to the best of our knowledge, is novel in this context.\n\n\n**Regarding Writings (Weakness 4)**\n\nThank you for the helpful suggestions. We will revise the theoretical sections to present lemmas and proofs more formally for clarity. We also agree that moving the related work section earlier and presenting ARAM in its own subsection would improve the overall organization, and we will revise the paper accordingly. Lastly, we will include a more detailed description of Park et al.'s algorithm in the appendix to strengthen the comparison.\n\n\n**Convergence in Park et al. (Questions 1)**\n\nThe reason Park et al. only provide average-iterate convergence is that their weight update is based on projected gradient descent, not on the original objective but on a Gaussian smoothing of the objective. Theorem 6 in Nesterov (2017) establishes only average-iterate convergence guarantees for this optimization method (referred to as $RS_\\mu$ in their paper).\n\n[Ref.] Nesterov, Yurii, and Vladimir Spokoiny. \"Random gradient-free minimization of convex functions.\" Foundations of Computational Mathematics 17.2 (2017): 527-566.\n\n\n**Relation to Zero-Sum Markov Games (Questions 2)**\n\nThank you for the thoughtful question. The key difference lies in the fact that, in zero-sum Markov games (MGs), both players operate over the same strategy space—typically the policy space $\\Pi = \\\\{\\pi|\\pi:S\\to\\Delta(A)\\\\}$. In contrast, our setting involves asymmetric strategy spaces: the learner's strategy space is the policy space $\\Pi$, while the adversary operates over the weights, i.e., $w \\in \\Delta^K$.\n\nTo investigate whether our setting could be framed as a special case of an MG, consider defining a new action space for the adversary as $[K] = \\{1, \\ldots, K\\}$, allowing $w \\in \\Delta^K$ to be interpreted as a policy over $[K]$. However, in our formulation, the same $w$ must be applied across all states. That is, we may view the adversary’s strategy as a state-independent policy $\\pi_w^{MG}: s \\mapsto w \\in \\Delta([K])$ for all $s \\in S$.\n    \nThis corresponds to a constrained subset of the full MG policy space $\\Delta([K])^S$, and restricts the adversary to state-independent strategies. As such, our setting becomes a constrained optimization problem over a restricted policy class, which cannot, in general, be addressed by techniques designed for unconstrained MGs. Furthermore, in MGs there is no guarantee that the optimal policy for the adversary would be state-independent. Hence, our problem is not a special case of existing MG formulations, and last-iterate convergence results for MGs are not directly applicable here.\n\n\n**Key Theoretical Contributions (Questions 3)**\n\nAs discussed in our response to Weakness 1, one of the central theoretical contributions of our work is the reformulation of the max-min MORL problem into a two-player zero-sum game in terms of the pair $(w,\\pi)$, rather than over the occupancy measure space. This reformulation enables the use of policy optimization methods, which are more scalable and practical. Despite the fact that the value function is non-concave in $\\pi$, starting from deriving that the max-min and min-max values are equal, we prove that our game formulation indeed solves the original max-min MORL objective by finding a Nash equilibrium.\n\nTo the best of our knowledge, our work is the first to provide a provable last-iterate convergence guarantee for the max-min MORL setting. In our proof, we build upon prior results on the monotonic improvement of value functions under NPG with softmax policy and entropy regularization (Cen et al. 2022). However, unlike standard NPG analysis with regularization, the presence of an adversary in the max-min setup breaks the monotonic improvement of $V_{w_t}^{\\pi_t}$. As a result, we derive a lower bound on the change in the value function (which can be negative due to adversary), which plays a critical role in establishing convergence. This treatment of the non-monotonicity introduced by the adversary is a key technical distinction of our proof.\n\n[Ref.] Cen, Shicong, et al. \"Fast global convergence of natural policy gradient methods with entropy regularization.\" Operations Research 70.4 (2022): 2563-2578."}, {"review_id": "wffxIWZ5FU", "reviewer": "Reviewer_xubR", "summary": "This paper reformulates entropy-regularized max-min multi-objective reinforcement learning as a two-player zero-sum game and introduces ERAM/ARAM, single-loop algorithms that combine natural policy gradients for the agent with a closed-form mirror-descent adversary. The authors establish global last-iterate convergence and finite-sample guarantees, while empirical studies show faster convergence and lower memory use than prior double-loop approaches across standard control benchmarks.", "questions": "1. How does the bias introduced by non-zero $\\tau$ and $\\tau_w$ trade off against convergence speed, and can the authors derive bounds quantifying the gap to the unregularized max-min optimum?\n2. The mirror-descent step computes a soft-max over the full K-dimensional value vector each iteration. When K is large, what is the update’s time/space complexity and can a sparsity-promoting or low-rank variant preserve the same convergence guarantees?\n3. The natural policy-gradient update assumes access to the exact inverse Fisher matrix. In practice this is approximated (e.g., diagonal or K-FAC). What accuracy is required for last-iterate convergence to hold, and could an adaptive scheme bound the error introduced by these approximations?\n4. In ARAM, the KL-regularization term uses a baseline distribution $c$ that is updated over time to highlight poorly performing objectives. Because $c$ now varies with the iteration, the effective optimization objective changes. Does this time-varying regularizer invalidate the convergence analysis that assumes a fixed objective, and what constraints on the update rule for $c$ (e.g., step size, update frequency, contraction conditions) would preserve the theoretical guarantees while retaining the empirical gains?\n5. An open question: the paper would be strengthened by positioning its max–min objective within the broader distributionally-robust reinforcement learning (DR-RL) literature [1][2][3]. Can you add a further discussion on this field?\n\nReference:\n\n[1] Smirnova, Elena, Elvis Dohmatob, and Jérémie Mary. \"Distributionally robust reinforcement learning.\" arXiv preprint arXiv:1902.08708 (2019).\n\n[2] Derman, Esther, and Shie Mannor. \"Distributional robustness and regularization in reinforcement learning.\" arXiv preprint arXiv:2003.02894 (2020).\n\n[3] Liu, Zhishuai, Weixin Wang, and Pan Xu. \"Upper and lower bounds for distributionally robust off-dynamics reinforcement learning.\" arXiv preprint arXiv:2409.20521 (2024).", "limitations": "There is no potential negative societal impact in this work. The limitation of methodology is mentioned in **Weaknesses**.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. ERAM/ARAM eliminate the costly inner loop and large Q-function ensembles required by prior work via an analytic adversary update, which reduces parameters by $\\approx 95$% while retaining direct optimisation of the true max-min objective.\n2. The paper provides global last-iterate convergence, explicit $\\tilde{O}(\\epsilon^{-6})$ sample complexity and iteration bounds under approximate evaluation. This result strengthens theoretical correctness beyond average-iterate results.\n3. ARAM generalizes ERAM with data-driven KL regularization on the adversary and shows adaptive entropy can sharpen worst-case returns without altering algorithmic complexity.\n\n\nWeaknesses:\n1. Convergence proofs assume fixed $\\tau, \\tau_w, \\lambda$. However, empirical performance varies markedly with these coefficients and no principled tuning rule or robustness bound is provided.\n2. The algorithm optimizes a surrogate that differs from the exact max-min objective whenever $\\tau$ or $\\tau_w>0$, yet the paper gives no bound on the resulting sub-optimality.", "was_revised": true, "final_justification": "I’m satisfied with the author's response and my questions have been fully addressed. After reading the other review and response, I believe this is a solid work and have decided to raise my rating.", "rebuttal": "**Choice of $\\tau,\\tau_w$ and $\\lambda$ (Weakness 1)**\n\nThank you for pointing out this important issue. \nRegarding $\\tau$, we followed the default entropy coefficient used in PPO as provided in the stable-baselines3 library. For the newly introduced coefficients $\\tau_w$ and $\\lambda$ in our algorithm, we propose the following heuristic to guide their selection:\n    Recall the ERAM update rule: $w_{t+1}=softmax(-\\frac{1-\\beta}{\\tau_w}V_t+\\beta\\log w_t)$.\n    \nThe key idea for coefficient selection is to *balance the scale* of the two terms inside the softmax. If the value term dominates, the weight update collapses toward minimum-objective selection (similar to GGF-PPO). Conversely, if the $\\log w$ term dominates, the update becomes overly conservative and largely ignores the current value estimates.\n    \nTo capture this balance, we compare the average magnitude of the two terms at convergence. Let\n$\\frac{1-\\beta}{\\tau_w}\\frac{1}{K} \\sum_k V_k^{last}$ and $\\beta H(w^{last})$\ndenote the respective contributions of the value and regularization terms, where $H(w^{last})$ is the entropy of the final $w$. In our experiments, we found that the regularization term was approximately: 0.18\\% of the value term in Base-4, 1.5\\% in Asym-4, and 0.1\\% in Asym-16.\n\nSimilarly, we examined the ratio between the average regularization term, $\\beta H(w^{last}) + (1 - \\beta) H(c^{last})$, and the value term, $\\frac{1 - \\beta}{\\tau_w} \\frac{1}{K} \\sum_k V_k^{last}$, in ARAM, and observed the following results: 1.69\\% in Base-4, 6.8\\% in Asym-4, 25.4\\% in Asym-16.\n\n\nThis suggests a practical heuristic: prior to the main training run, conduct a short preliminary run to estimate average $V, H(w)$ and $H(c)$, then set $\\lambda,\\tau_w$ such that the regularization term lies in the range of 0.1\\%-2\\% of the value term for ERAM.\nAveraging across tasks, we recommend targeting a regularization-to-value ratio of around 10\\% as a practical starting point for ARAM. In practice, this approach may help inform the initial choice or tuning range of the coefficients.\n\nWe will clarify this heuristic in the revised version and consider analyzing its robustness more formally in future work.\n\n**Convergence Speed, Suboptimality Bound, and Trade-off Induced by $\\tau,\\tau_w$ (Weakness 2, Question 1)**\n\nThank you very much for drawing our attention to these important points—they are highly valuable for strengthening our theoretical analysis.\n\n[Convergence Speed]\n\nFrom Theorem 4.1, the speed of convergence is determined by the base $\\rho$, which is guaranteed to be $0<\\rho\\le1-\\frac{\\epsilon^2}{2}$ where $\\epsilon$ is a parameter connects the scales of learning rates $\\eta$ and $\\lambda$. From the parameterization used in our proof (Appendix F.3), $\\epsilon = O(\\eta\\tau) = O(\\sqrt{\\lambda\\tau_w})$. This says that the speed is determined not only by $\\tau,\\tau_w$, but the product with learning rates.  \nNote that with fixed learning rates $\\eta,\\lambda$, larger $\\tau,\\tau_w$ results in smaller $\\rho$ and thus, faster convergence.\n\n[Suboptimality Gap of Values by Regularization]\n\nLet the optimal solutions for the regularized game be $w_r^\\*,\\pi_r^\\*$.\nSimilarly, let the optimal solutions for unregularized game be $w^\\*,\\pi^\\*$.\n\nWe derive the bound for the gap between \"unregularized\" values, that are used for metric in our experiments (e.g. traffic). Please see the end of the response of the Reviewer 5Y2u for the full proof of the following result: \n$$|V_{w_r^\\*}^{\\pi_r^\\*}-V_{w^\\*}^{\\pi^\\*}|\\le\\frac{\\tau\\log|A|}{1-\\gamma}+\\tau_w\\log K.$$\nNote that, suboptimality gap of value by regularization is linear in $\\tau,\\tau_w$.\n\n[Trade-off Between Convergence Speed and Suboptimality Gap]\n\nTo sum up, for fixed learning rates $\\eta$ and $\\lambda$, the regularization coefficients $\\tau$ and $\\tau_w$ involve a trade-off: larger $\\tau$ and $\\tau_w$ lead to faster convergence but also increase the suboptimality gap in value.\n\nWe appreciate the question and will include this analysis in our revision.\n\n\n**Complexity of Softmax and Convergence in Sparsity-Promoting Variants (Questions 2)**\n\n[Complexity of Softmax]\n\nThe built-in softmax in PyTorch operates with $O(K)$ time and space complexity. We also compare against GGF-PPO which updates only the minimal objective without using softmax in the weight update. The training wall-clock time of ERAM and ARAM is comparable to that of GGF-PPO.\n\n|Environments|ERAM| ARAM|GGF-PPO|\n|-|-|-|-|\n|Base-4|111±2.6|120±3.9|122±4.0|\n|Asym-4|87.2±2.4|87.4±2.4|84.8±2.2|\n|Asym-16|356±27|365±20|394±5.5|\n\n[Convergence in Sparsity-Promoting Variants] \n\nRegarding sparsity-promoting or low-rank variants, we believe this is a compelling direction. We implemented two heuristics based on ARAM. The first, topM-c, updates only the top-$M$ objectives most correlated with the current minimum: we compute the ARAM weight, select the top-$M$ by correlation, mask the others to 0, and renormalize. The second, topM-w, selects the top-$M$ elements from the ARAM weight vector and renormalizes them. We used the best-performing ARAM hyperparameters with $M=5$ in the Asym-16 setting, which has a relatively large number of objectives.\n\n|Environment|ARAM|ERAM|top5-c|top5-w|\n|-|-|-|-|-|\n|Asym-16|-15043|-17334|-15913|-16551|\n\nAs shown in the table, even simple heuristics perform fairly well and exhibit stable convergence. This suggests that more intelligent sparsity-promotion methods could be beneficial when $K$ becomes large. While we do not provide a rigorous convergence guarantee for the sparsity-promoting variants, we offer the following intuitive perspective.\n\nIntuitively, if the selected subsets vary with little overlap across iterations, the behavior may resemble the jumping dynamics of GGF-PPO. If they consistently overlap, the method may inherit ARAM's conservatism. In practice, the degree of overlap would depend on the structure of the objectives and may vary over time.\n\nDesigning a variant that maintains sufficient overlap could strike a balance between sparsity and stability, and we see this as a promising direction for future work.\n\n**Fisher Matrix Approximation and Required Accuracy (Questions 3)**\n\nIn our analysis of NPG with softmax policy parameterization, the inverse Fisher matrix cancels out in the update expression (please see eq. (16) in Cen et al. (2022)). As a result, there is no need to approximate or bound this term within the proof.\n\nIn our analysis, the required accuracy primarily concerns the value estimates, rather than the Fisher matrix itself.\n\nFor ERAM, as shown in Theorem 4.3, we prove that if the value estimates can be approximated within an error bound $\\delta$, then last-iterate convergence is achieved up to an $O(\\delta)$ residual error. This ensures robustness to approximation errors in practice.\n\nIn the case of ARAM, we do not provide a rigorous bound for error, but empirically observe improved stability and performance. We agree that developing an adaptive scheme to bound approximation errors—especially under practical approximations of the Fisher matrix—is a promising direction for future theoretical investigation.\n\n[Ref.] Cen, Shicong, et al. \"Fast global convergence of natural policy gradient methods with entropy regularization.\" Operations Research 70.4 (2022): 2563-2578.\n\n\n**Validity of the Adaptive Scheme (Questions 4)**\n\nWe acknowledge that ARAM was introduced to improve practical performance, motivated by real-world scenarios where objectives may be correlated. While we do not provide a formal convergence guarantee, we offer the following insight into how ARAM works and how $\\tau_w$ influences the update, aiming to illustrate the qualitative behavior and the role of $\\tau_w$ in stabilizing the updates.\n\nRecall the ARAM update: \n$w_{t+1} = softmax(-\\frac{1-\\beta}{\\tau_w}V^t + \\beta\\log w_t + (1-\\beta)\\log c_t)$ \nwhere $c_t = softmax(E_{(s,a)\\sim d^t}[r_k(s,a)r_{i_t'}(s,a)])$ is the empirical correlation with the minimal objective $i_t'$. Using the fact that $V_k^t = \\frac{1}{1-\\gamma} E_{d^t}[r_k]$, this update can be rewritten as: \n$w_{t+1} = softmax(-\\frac{1-\\beta}{\\tau_w}(V^t[r_k(1-\\tau_w(1-\\gamma)r_{i_t'})]) + \\beta\\log w_t(k))_{k=1}^K$ where $V^t[r]$ is a value by $\\pi_t$ and given scalar reward function $r$.\nThis shows that ARAM is equivalent to ERAM with an effective (time-varying) reward function that depends on the correlation with the current minimal objective.\n\nThis modification has an intuitive interpretation: when $r_k$ and $r_{i_t'}$ are positively correlated and $r_{i_t'}$ is large enough so that $1-\\tau_w(1-\\gamma)r_{i_t'}<0$, the effective reward for objective $k$ changes the sign, encouraging to increase weight on $k$—as it is helpful for the weakest objective. Note that in ERAM, larger rewards always lead to lower weights in order to maximize the minimum, due to the negative coefficient $-\\frac{1-\\beta}{\\tau}$.\nThe parameter $\\tau_w$ controls the sensitivity of this adjustment: A smaller $\\tau_w$ imposes a stricter criterion for considering an objective as helpful to the minimal one (thus, behaves like ERAM), while a larger $\\tau_w$ makes this criterion more lenient.\n\nAlthough this is not a formal guarantee—due to the time-varying nature of the effective reward and its dependence on the evolving policy—we hope this analysis provides helpful intuition about the adaptive mechanism in ARAM.\n\n**Discussion on DR-RL (Questions 5)**\n\nWe appreciate the suggestion and references on DR-RL. DR-RL typically tackles transition uncertainty. Similarly, in reward-uncertain MDPs, one can define an uncertainty set in reward space and apply max–min for robustness. Our case fits the finite uncertainty set $\\\\{r_k\\\\}$, with regularization capturing this internalized reward uncertainty, analogous to how DR-RL treats transition uncertainty. For infinite sets, DR-RL seem applicable for analysis in terms of distribution over reward space. We'll add this in revision for further related works. Thanks."}, {"review_id": "I0cnOuycOR", "reviewer": "Reviewer_6FTU", "summary": "This work gives an algorithm for multi-objective reinforcement learning (MORL), specifically entropy-regularized maxmin MORL. The algorithm formulates the MORL problem as a two-player zero sum game in which the learner updates its policy using natural policy gradient updates and the adversary uses mirror descent to select a strategy from the simplex over objectives. In the case of tabular MDPs, last-iterate convergence guarantees are given. The algorithm is empirically evaluated in a tabular MDP as well as a traffic signal control environment.", "questions": "- What is the novel theoretical contribution over the work of Cousins et al?\n- How does this work compare to the existing MORL literature that uses primal dual algorithms?", "limitations": "See comments above", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 1, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper studies the interesting and important problem of multi-objective reinforcement learning, provides a novel algorithm, and supports the usefulness of the algorithm both theoretically and empirically.\n\nWeaknesses:\nThe paper omits a great deal of relevant literature and so it’s very unclear what the novel contribution is. I’ve included some related work on constrained and fair RL that I think the authors should compare to. Notably, the work of Cousins et al [2] solves a more general version of the minmax  problem in tabular settings, and so should be discussed in detail. \n\nThe paper also claims that the minmax objective presents a unique challenge, but (as observed in [5]), the minmax objective can be handled as a constrained optimization problem, where the values for constraints are also optimized. \n\nThe presentation of the theoretical guarantees is also a bit hard to interpret. How is epsilon chosen in Theorem 4.1? Also how does the regularized Q value compare to the unregularized? It would be good to have more discussion about the consequences of regularization, beyond the justification of regularization for the purposes of simplifying the analysis of mirror descent. \n\nLarger experiments for the tabular setting would also strengthen the empirical evaluation.\n\nMissing citations: \n\n[1] M. Calvo-Fullana, S. Paternain, L. F. Chamon, and A. Ribeiro. State augmented constrained reinforcement learning: Overcoming the limitations of learning with rewards.\n\n[2] C. Cousins, K. Asadi, E. Lobo, and M. L. Littman. On welfare-centric fair reinforcement learning.\n\n[3] A. Muller, P. Alatur, V. Cevher, G. Ramponi, and N. He. Truly no-regret learning in constrained mdps. \n\n[4] S. Miryoosefi, K. Brantley, H. Daume III, M. Dudik, and R. E. Schapire. Reinforcement learning with convex constraints. \n\n[5] E. Eaton, M. Hussing, M. Kearns, A. Roth, S. Sengupta, J. Sorrell. Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces.", "was_revised": true, "final_justification": "I appreciate the detailed and thoughtful rebuttal from the authors, as well as the commitment to include the relevant related work in an updated version. While the author's explanations did help clarify how the proposed algorithm differs from similar existing work, it seems from the rebuttal that the contribution is more one of practical improvements in some settings, as opposed to a novel theoretical contribution. In light of this, I think the paper would be significantly strengthened by more thorough and diverse experimental comparison to existing model-based and primal dual MORL algorithms. I have increased my score based on the comments in the rebuttal, but think the work would be much improved by being rewritten with a deeper awareness of the related work in mind.", "rebuttal": "We thank the reviewer for valuable comments.\nBelow is our response to the reviewer's comments.\n\n\n**Novelty and Comparison with the Work of Cousins et al. (Question 1)**  \n\nThanks for introducing relevant existing works. We will include relevant related works in the revision.  Here, we would like to explain our contribution and difference from the existing works.  We agree that the max-min or more general utility MORL problem can be formulated using the occupancy measure d(s,a):\n\n$$\\max_{d} \\min_{1 \\leq k \\leq K}  \\sum_{s,a} d(s,a) r^{(k)}(s,a)$$\n$$\\sum_{a'} d(s',a') = \\mu_0(s') + \\gamma \\sum_{s,a} P(s' | s,a) d(s,a) ~~ \\forall s'$$\n$$d(s,a) \\geq 0, ~~ \\forall (s,a), $$\n\nwhere $r^{(k)}(s,a)$ is the $k$-objective reward function.  \nThis was noted in Eq. (9) of Park et al. 2024 and Eq. (3) of Cousins et al. 2024 [2]. The method of Cousins et al. is model-based: it learns the model $P$ and $r^{(k)}$, then solves the convex optimization problem using a solver. This restricts the algorithm to finite state-action spaces. Algorithm 1 of Cousins et al. consists of an exploration phase to learn the model and an exploitation phase to solve the optimization. In finite settings, the model can eventually be learned via visitation-count methods by the law of large numbers, and the algorithm will converge. However, this is not practical in realistic environments. For example, in the Four-room MORL environment with $|S|=5248$, $|A|=4$ and two objectives, the required samples by Cousins et al. is $m_{knw} \\approx 131,001,956,377,564$ for $\\epsilon=\\delta=0.1$. This is clearly impractical. So, the paper of Cousins et al. does not have any numerical example. \n\nOur whole idea and contribution is to circumvent the model learning and develop a model-free algorithm applicable to even continuous state-action spaces.  As mentioned by the reviewer, the above optimization can be written using a slack variable \n$c$ as\n\n$$\\max_{d(s,a), c} c$$\n$$\\sum_{s,a} r^{(k)}(s,a) d(s,a) \\geq c, ~ 1 \\leq k \\leq K$$\n$$\\sum_{a'} d(s',a') = \\mu_0(s') + \\gamma \\sum_{s,a} P(s' | s,a) d(s,a) ~~ \\forall s'$$\n$$d(s,a) \\geq 0, ~~ \\forall (s,a).$$\n\nAgain, we do not solve this problem (requiring the model) directly. We consider the dual problem of this problem, given by\n\n$$\\min_{w \\in \\Delta^K, v} \\sum_s \\mu_0(s) v(s)$$\n$$v(s) \\geq \\sum_{k=1}^K w_k r^{(k)}(s,a) + \\gamma \\sum_{s'}P(s'|s,a)v(s'), ~ \\forall (s,a) $$\n\nwhere  $\\mu_0$ is the initial state distribution and $$\\Delta^K :=\\\\{ w=[w_1,\\cdots,w_K]^T\\in R^K | \\sum_{k=1}^K w_k = 1; ~ w_k \\geq 0, ~ \\forall k\\\\}$$ is the $(K-1)$-simplex. Note that now the Lagrange dual variable $w$ is on the probability simplex not in the positive first quadrant as in the references the reviewer suggested. The above problem involves inequality difficult to handle. One can further show the above dual problem is equivalent to  (Park et al. 2024)\n\n$$\\min_{w \\in \\Delta^K}\\sum_s \\mu_0(s) v_{w}^\\*(s) ~~~~~Eq.(R1)$$\n\nwhere $v_w^\\*$ is the unique fixed point of the following operator: \n\n$$ T_w^\\* v(s) := \\max_a \\left[ \\sum_{k=1}^K w_k r^{(k)}(s,a)+ \\gamma \\sum_{s'} P(s'|s,a) v(s') \\right]$$\n\nThus, $v_w^\\*(s)$ is basically the optimal value function of the weighted reward $\\sum_k w_kr^{(k)}$. The optimal value function can be learned in a model-free manner using various methods, eliminating the need to learn the model $P$ and $r^{(k)}$. A similar derivation is possible for the entropy-regularized case. Our algorithm can be applied to a real-world problem of 16-lane traffic control. Now, we hope that the reviewer recognizes our contribution as compared to the work of Cousins et al.  We will mention the model-based approaches like Cousins et al. are available for small problems.\n\n[Ref.]  Park et al., \"The max-min formulation of multi-objective reinforcement learning: From theory to a model-free algorithm,\" ICML, Jul. 2024\n\n\n\n**Novelty Compared to Other Primal-Dual Algorithms (Question 2)**   \n\nNow, consider the start state $s_0$ problem where $\\mu_0$ is a delta on $s_0$.  Eq. (R1) becomes $\\min_{w \\in \\Delta^K} v_w^\\*(s_0)$ which is equivalent to our initial problem  $\\max_{\\pi} \\min_k V_k^\\pi(s_0)=\\max_{\\pi} \\min_{w \\in \\Delta^K}  \\langle w,V^\\pi(s_0)\\rangle$.  Note that this max-min and min-max equivalence is different from conventional max-min and min-max equivalence considered in constrained MDPs (Paternain et al. 2019, Efroni et al. 2020, Muller et al. 2024), where the following problem was considered:\n\n$$\\max_\\pi V_r^\\pi ~~s.t.~~~ V_{u^i}^\\pi \\ge c_i, \\forall i.~~~ Eq.(R2)$$\n\nThe strong duality (Paternain et al. 2019) of this problem says \n\n$$\\max_\\pi \\min_{\\lambda \\in R_{\\ge 0}^K}  L(\\pi,\\lambda)  = \\min_{\\lambda \\in R_{\\ge 0}^K} \\max_\\pi L(\\pi,\\lambda) ~~~ Eq. (R3)$$\n\nwhere\n$$ L(\\pi,\\lambda) = V_r^\\pi + \\sum_i \\lambda_i (V_{u^i}^\\pi -c_i).$$\n\nNote that due to $\\lambda \\in R_{\\ge 0}^K$ (i.e., positive quadrant), the left-hand side of Eq. (R3) is simply restating Eq. (R2).  If $V_{u^i}^\\pi -c_i \\ge 0 $, then $\\lambda_i=0$ and \n$\\max_\\pi \\min_{\\lambda \\in R_{\\ge 0}^K}  L(\\pi,\\lambda) = \\max_\\pi V_r^\\pi$.  If  $V_{u^i}^\\pi -c_i < 0$, then $\\lambda_i=\\infty$ and the problem becomes infeasible. The max-min and min-max equivalence in our paper does not enjoy such simplification because the dual variable $w$ lie in the probability simplex. So, the max-min and min-max equivalence and the proof of NE in our paper are a new result.\n\nIn fact, due to the fact $w \\in \\Delta^K$, we considered the entropy regularization $H(w)$ instead of $||w||^2$ of Muller et al. 2024.  Thus, we have a closed-form solution for $w$ udpate, not requiring projected gradient descent used in Effroni et al. 2020, Muller et al. 2024.  The role of $H(w)$ will be explained further below.\n\nNow, consider the work of Eaton et al. [5] and  the approach suggested by the reviewer. Eaton et al. basically considered constrained MDP:\n$$\\max_\\pi V_r^\\pi ~~s.t.~~~ V_{u^i}^\\pi \\ge c_i, \\forall i.$$\n\nConsider the max-min approach, stated in the 2nd line after eq. (2) of Eaton et al.'s paper and suggested by the reviewer:\n\n$\\max_{\\pi,c} ~c$   s.t. $V_{u^i}^\\pi  \\ge c, ~\\forall i.~~ Eq.(R4)$\n\n\nIts Lagrangian is given by\n$$L(\\pi,c,\\lambda) = c + \\lambda_i (V_{u^i}^\\pi-c).$$\n\nEaton et al.'s method is a primal-dual algorithm with a primal step solving $\\pi, c$ given $\\lambda$, and a dual step solving $\\lambda_i$ given $\\pi, c$. Their dual step (Lin-OPT and OPT) yields a scaled one-hot vector $C e_k$ for the worst value index $k$. While they did not consider deep implementations, combining PPO (as RL solver) with their dual update reduces to GGF-PPO of Siddique et al., which we already include. Their Algorithm 4 (FairFictRL) accumulates $\\lambda$ over time. We evaluated this version of GGF-PPO during revision, and the result is shown below:\n\n| Environments | ARAM   | ERAM   | GGF-PPO | FairFictRL with PPO|\n|-|-|-|-|-|\n| Base-4 | -1160  | -1387  | -1731   | -3477 |\n| Asym-4 | -2696  | -2732  | -3501   | -4359 |\n| Asym-16 | -15043 | -17334 | -21663  | -28970 |\n\nAs seen, our algorithms (ARAM ad ERAM) significantly outperform GGF-PPO and GGF-PPO with time-averaged $\\lambda$ (FairFictRL).\n\nAs mentioned in our paper, we adopted $H(w)$ regularization, which spreads out the weighting factor across multiple objective dimensions. With this, we achieved the last-iterate convergence and significant performance improvement.  Furthermore, in our ARAM we went one step further to devise more intelligent regularization. Please see the last part of Section 5 of our paper.\n\nIn summary, our algorithm is **model-free** and falls into the category of primal-dual algorithms. Unlike primal-dual algorithms for conventional constrained MDPs,  our algorithm exploits the special properties of max-min multi-objective RL, e.g. **the dual variable lies in the probability simplex**. With our **entropy regularization on the dual variable**, we have **closed-form updates** for the dual variable, **went beyond straightforward primal-dual algorithms like GGF-PPO or Eaton et al.'s**, and achieved **significant performance improvement** over existing methods (at least 30 \\% longest waiting time reduction for asymmetric 16-line traffic junction control. Please see the paper for simulation details.).\n\nConsidering these clear contributions, noted by other reviewers, we would like to kindly ask the reviewer to reconsider the evaluation.  We will include missing references with proper explanation in our revision. \n\n\n \n**Other Comments and Questions**\n\n\n[How is epsilon chosen in Theorem 4.1?]  \n\nAny $\\epsilon\\in (0,\\epsilon_0)$ where $\\epsilon_0 = \\frac{2(1-\\gamma)}{4+5\\gamma-6\\gamma^2}$ can be chosen in Theorem 4.1. Note that $\\frac{2(1-\\gamma)}{4+5\\gamma-6\\gamma^2} \\ge \\frac{48(1-\\gamma)}{121}>0$ for $\\gamma<1$.Please see Remark F.3 for detailed derivations.\n\n\n[How does the regularized Q value compare to the unregularized?']\n\n\nFor an optimal solution $\\pi_r^\\*, w_r^\\*$ of the regularized game $\\max_\\pi \\min_{w \\in \\Delta^K} \\langle w, V^\\pi \\rangle + \\tau \\tilde{H}(\\pi)-\\tau_w H(w)$ and an optimal solution $\\pi^\\*, w^\\*$ of the unregularized game $\\max_\\pi \\min_{w \\in \\Delta^K} \\langle w, V^\\pi \\rangle$, we derived a bound on the gap in unregularized values, \n$$|V_{w_r^\\*}^{\\pi_r^\\*}-V_{w^\\*}^{\\pi^\\*}|\\le \\frac{\\tau\\log|A|}{1-\\gamma}+\\tau_w\\log K.$$\n\nThis is because the original problem is defined without regularization, and thus the unregularized value remains the primary performance metric of interest. For proof, please see the end of the response to Reviewer 5Y2u.\n\n\n\n[Larger tabular experiments]  \n\nPlease note that the 16-lane traffic control problem has continuous states and is a real-world problem. The paper already includes a tabular experiment with a large state space in Appendix M, the Four-Room environment, which has a state space of size 5,248. Our algorithm outperforms the baselines in terms of max-min performance and achieves a minimum return of 1.8, which is close to the ground-truth optimal return of 2."}, {"review_id": "U6ScsZWeft", "reviewer": "Reviewer_5Y2u", "summary": "The paper addresses the max-min multi-objective reinforcement learning problem and reformulate it into two-player zero-sum regularized continuous game. In addition, the paper proposes “entropy-regularized adversary for max-min MORL” algorithm for policy update. Authors have proven last-iterate convergence with exact policy evaluation and approximate policy evaluation. They further extend it to “adaptively regularized adversary for max-min MORL” algorithm. Finally, they test the proposed algorithms in tabular setting and traffic signal control.", "questions": "1. In the introduction section, the authors introduce the background of the min-max criterion, which is not consistent with the problem of the max min research in the paper.\n2. The paper demonstrates last-iterate convergence in tabular MDPs. However, in practical applications, function approximation (e.g., neural networks) is more commonly employed. It would be beneficial to further investigate whether convergence can still be maintained when the policy parameterization extends beyond softmax, particularly in cases involving linear function approximation, which represents an intermediate level of complexity.\n3. The theoretical justification for the regularization parameter τ_w appears somewhat tenuous. The paper sets a condition that τ_w must be greater than a certain complex expression (Theorem 4.1), yet this threshold is fixed at 0.05 in the experiments. A deeper analysis of the impact of τ_w on the convergence speed would be valuable.\n4. The description of error propagation mechanisms in the case of approximate policy evaluation is insufficiently clear. Theorem 4.3 provides an error term involving δ, but does not explain how to control the accumulation of errors during the iteration process. This is particularly relevant in deep reinforcement learning, where value function estimation may be biased. It would be helpful to further discuss the cascading effects of updates to the weight vector w.\n5. Providing additional baseline comparisons from works such as Welfare and Fairness in Multi-Objective Reinforcement Learning [12] and Multi-Objective Reinforcement Learning: Convexity, Stationarity, and Pareto Optimality [23] would strengthen the argument and enhance the persuasiveness of the paper.\n6. In the related work section, the authors claim that the paper is a generalization of GGF-PPO, but in the Memory and Computational cost section, it only compared with [27].\n7. Minor:\n(1) The order of the paper “checklist” and “appendix” is wrong.\n(2) Some first-occurrence abbreviations are undefined, such as MORL on line 12 and GGF on line 251.\n(3) The indefinite article is misused with “a MOMDP” on line 57, and “a NE” throughout the paper.\n(4) There's a typo in the subtitle of line 131: “Two-plaer zero-sum regularized continuous game formulation”.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\nTransform multi-objective reinforcement learning into a study from the perspective of game theory\n\nWeaknesses:\n1. It has a high correlation with paper [27] and the innovation is not significant.\n2. The experimental part is not comprehensive enough. The main issue lies in the comparison with [27].\n3. The author's writing is not rigorous enough and there are many minor mistakes.", "was_revised": true, "final_justification": "The paper now makes a compelling case for its algorithmic and theoretical advancements in MORL. We look forward to seeing the new version!", "rebuttal": "**Novelty and Relation to Park et al. (2024) (Weaknesses 1)**\n\nWe acknowledge that Park et al. (2024) serves as an important starting point for our work, and we do address the same overarching problem. However, our approach is fundamentally different: we propose a novel game-theoretic formulation that leads to a distinct algorithm from Park et al. (2024). Our method requires significantly fewer model parameters and substantially reduces training time, resulting in improved memory and computational efficiency.\n\nMoreover, real-world problems often involve correlated objectives. To address this, we introduce a new mechanism that explicitly accounts for inter-objective correlations during learning, which in turn improves the max-min performance.\n\n[Ref.] Park et al., \"The max-min formulation of multi-objective reinforcement learning: From theory to a model-free algorithm,\" ICML, Jul. 2024\n\n**More on Complexity Comparison (Weaknesses 2, Question 6)**\n\nThank you for pointing this out. In terms of memory usage, ERAM and ARAM use the same PPO backbone as GGF-PPO, and the only additional parameters come from storing the weight vector $w$, which adds just 4 parameters in Base-4 and Asym-4, and 16 in Asym-16.\n\nRegarding computational cost, we presented the training wall-clock time in the table. Across all three environments, ERAM, ARAM, and GGF-PPO exhibited comparable computational cost. We will clarify these comparisons and include GGF-PPO in the revised version of Section 6.3.\n\n|Environments|ERAM|ARAM|GGF-PPO|\n|-|-|-|-|\n|Base-4|111±2.6|120±3.9|122±4.0|\n|Asym-4|87.2±2.4|87.4±2.4|84.8±2.2|\n|Asym-16|356±27|365±20|394±5.5|\n\n\n**Regarding Writings (Weaknesses 3, Question 7)**\n\nWe appreciate your careful attention to detail. We will correct all the noted issues in the revised version, including the section order, missing abbreviation definitions, article usage, and the typo in the subtitle.\n\n\n**Clarification on Max-Min Objective (Questions 1)**\n\nWe suspect the confusion may have come from the phrase “min-max (or max-min) criterion” on line 34, and we apologize for the lack of clarity. To clarify, our objective is a max-min problem. We mentioned min-max to note that a min-max cost problem is equivalent to a max-min reward problem, assuming the reward is defined as the negative of the cost. We hope this clears up the misunderstanding.\n\n**Regarding Policy Parameterization Beyond Softmax (Questions 2)**\n\nWe agree that analyzing convergence under more advanced policy parameterizations—such as linear function approximation—is an important and interesting direction. However, this lies beyond the scope of the current work. Convergence analysis even for linear function approximation is not easy, as shown in Baird's example. We consider this a promising avenue for future research.\n\n**Deeper Theoretical Analysis on $\\tau_w$ (Questions 3)** \n\nThe lower bound on $\\tau_w$ given in Theorem 4.1 is a sufficient condition for convergence. In tabular cases, where the environments are relatively small, we fixed a relatively small $\\tau_w = 0.05$ for simplicity.\n\nRegarding deeper theoretical analysis of the impact of $\\tau_w$, we would like to clarify the trade-off between convergence speed and the suboptimality value gap induced by regularization. \n\n[Impact of $\\tau_w$ on Convergence Speed]\n\nFrom Theorem 4.1, the speed of convergence is determined by the base $\\rho$, which is guaranteed to be $0<\\rho\\le1-\\frac{\\epsilon^2}{2}$ where $\\epsilon$ is a parameter connects the scales of learning rates $\\eta$ and $\\lambda$. From the parameterization used in our proof (Appendix F.3), $\\epsilon = O(\\sqrt{\\lambda\\tau_w})$. This says that the speed is determined not only by $\\tau_w$, but the product with learning rate $\\lambda$. Note that with fixed learning rate $\\lambda$, larger $\\tau_w$ results in smaller $\\rho$ and thus, faster convergence.\n\n[Impact of $\\tau_w$ on Suboptimality Value Gap by Regularization]\n\nLet the optimal solutions for the regularized game be $w_r^\\*,\\pi_r^\\*$.\nLet the optimal solutions for unregularized game be $w^\\*,\\pi^\\*$.\n\nWe derived a bound for the gap between the two values, that are used for metric in our experiments (e.g. traffic). Please see the end of this response for full proof for the bound: \n$|V_{w_r^\\*}^{\\pi_r^\\*}-V_{w^\\*}^{\\pi^\\*}|\\le \\frac{\\tau\\log|A|}{1-\\gamma}+\\tau_w\\log K$.\nNote that, suboptimality value gap by regularization is linear in $\\tau,\\tau_w$.\n\n[Trade-off Between Convergence Speed and Suboptimality Gap Induced by $\\tau_w$]\n\nTo sum up, for fixed learning rate $\\lambda$, the regularization coefficient $\\tau_w$ involves a trade-off between convergence speed and suboptimality gap: larger $\\tau_w$ lead to faster convergence but also increase the suboptimality gap in value.\n\nWe hope this analysis addresses your concern regarding the deeper analysis on impacts of $\\tau_w$ on convergence and suboptimality gap.\n\n\n**Control of Estimation Error (Questions 4)**\n\n\nThe key contribution of Theorem 4.3 is that ERAM provably converges in tabular MOMDPs without requiring explicit control of error accumulation. While Theorem 4.1 with exact policy evaluation shows that the suboptimality bound decays as $\\rho^t$, Theorem 4.3 with approximate policy evaluation provides a bound of the form $\\hat{\\rho}^t + O(\\delta)$, where $\\delta$ denotes the value estimation error. In other words, the result explicitly shows that the impact of error accumulation grows linearly with $\\delta$. This suggests that, in deep RL, as long as function approximation is sufficiently accurate, error accumulation does not explode—supporting the practical stability of our approach. \n\nInvestigating how to correct for error propagation when value estimates are considerably inaccurate in deep RL remains an interesting direction for future work.\n\n\n**Additional Baselines (Questions 5)**\n\nThank you for the helpful suggestions. Regarding [12], we implemented Welfare Q-Learning in [12] using the egalitarian objective ($W = \\min$). For the Four-Room environment, we directly used the official tabular implementation provided by the authors. Since their work does not include a deep RL version, we extended it ourselves by adapting it to a DQN-based implementation for the traffic environments.\n\n|Environments|ARAM|ERAM|WQL [12]|\n|-|-|-|-|\n|Base-4|-1160|-1387|-1688|\n|Asym-4|-2696|-2732|-5412|\n|Asym-16|-15043|-17334|-15639|\n|Four Room|1.80|1.56|0.89|\n\nAs for [23], the focus of that work is on recovering the Pareto front using linear preferences. This differs from our setting, which aims to find the max-min solution. Even if the full Pareto front were recovered, identifying the specific linear preference corresponding to the max-min point would be nontrivial. Hence, while related, their method does not directly address our objective.\n\n[Appendix. Proof for Suboptimality Value Gap by Regularization]\n\nLet the optimal solutions for regularized game be $w_r^\\*(\\pi) := arg\\min_w \\langle w,V^\\pi\\rangle+\\tau\\tilde{H}(\\pi)-\\tau_w H(w)$, $\\pi_r^\\*:=arg\\max_\\pi \\min_w \\langle w,V^\\pi\\rangle+\\tau\\tilde{H}(\\pi)-\\tau_w H(w)$. Let $w_r^\\* := w_r^\\*(\\pi_r^\\*)$.\n\nSimilarly, let the optimal solutions for unregularized game be $w^\\*(\\pi) := arg\\min_w \\langle w,V^\\pi\\rangle$, \n$\\pi^\\*:=arg\\max_\\pi \\min_w \\langle w,V^\\pi\\rangle$. Let $w^\\* = w^*(\\pi^\\*)$.\n\n1). lower bound\n\n$V_{w_r^\\*}^{\\pi_r^\\*} + \\tau\\tilde{H}(\\pi_r^\\*)-\\tau_w H(w_r^\\*)$\n\n$= \\max_\\pi\\min_w \\langle w,V^\\pi\\rangle+\\tau\\tilde{H}(\\pi)-\\tau_w H(w)$\n\n$\\ge \\min_w \\langle w,V^{\\pi^\\*}\\rangle+\\tau\\tilde{H}(\\pi^\\*)-\\tau_w H(w)$\n\n$=\\langle w_r^\\*(\\pi^*),V^{\\pi^\\*}\\rangle+\\tau\\tilde{H}(\\pi^\\*)-\\tau_w H(w_r^\\*(\\pi^\\*))$\n\n$=\\langle w^\\*,V^{\\pi^\\*}\\rangle + \\langle w_r^\\*(\\pi^\\*)-w^\\*, V^{\\pi^\\*}\\rangle + \\tau\\tilde{H}(\\pi^\\*)-\\tau_w H(w_r^\\*(\\pi^\\*)).$\n\nSince $0\\le \\tilde{H}(\\pi)\\le \\frac{\\log|A|}{1-\\gamma}$ and $0\\le H(w)\\le\\log K$ for any $\\pi$ and $w\\in\\Delta^K$, we obtain\n\n$V_{w_r^*}^{\\pi_r^\\*} - V_{w^\\*}^{\\pi^\\*} \\ge \\langle w_r^\\*(\\pi^\\*)-w^\\*, V^{\\pi^\\*}\\rangle - \\frac{\\tau\\log|A|}{1-\\gamma}-\\tau_w\\log K.$\n\nWe show that $\\langle w_r^\\*(\\pi^\\*)-w^\\*, V^{\\pi^\\*}\\rangle\\ge0$.\n\nFor simplicity, we denote $V^{\\pi^\\*}_k$ as $V_k$.\nWithout loss of generality, assume that $0<V_1\\le \\cdots \\le V_k$. Let $x_k = \\frac{e^{-V_k/\\tau_w}}{S}$ where $S=\\sum_i e^{-V_i/\\tau_w}$.\nNote that this $x$ is the solution of $arg\\min_w \\langle w,V^{\\pi^\\*}\\rangle-\\tau_w H(w)$, thus $x=w_r^\\*(\\pi^\\*)$, and satisfies $x_K\\le\\cdots\\le x_1\\le1$.\nBy definition, $w^\\* = w^\\*(\\pi^\\*) = (1,0,\\ldots,0)$. Then,\n\n$\\langle w_r^\\*(\\pi^\\*)-w^\\*, V^{\\pi^\\*}\\rangle$\n\n$= (x_1-1)V_1+x_2V_2+\\cdots+x_KV_K$\n\n$=-\\tau_w(x_1-1)\\log Sx_1-\\tau_wx_2\\log Sx_2-\\cdots-\\tau_wx_K\\log Sx_K$\n\n$=-\\tau_w(x_1-1)\\log x_1-\\tau_wx_2\\log x_2-\\cdots-\\tau_wx_K\\log x_K~(\\because \\sum_k x_k=1)~~-(1)$\n\n$=\\tau_w (x_2\\log\\frac{x_1}{x_2}+\\cdots+x_2\\log\\frac{x_1}{x_2})~(\\because \\sum_k x_k=1)$\n\n$\\ge \\tau_w\\cdot 0$ since $x_1\\ge x_k>0$ and equality holds when $x_k=\\frac{1}{K},\\forall k$.\n\nTherefore, we conclude that the suboptimality gap has lower bound $- \\frac{\\tau\\log|A|}{1-\\gamma}-\\tau_w\\log K$.\n\n2). upper bound\n\n$V_{w^\\*}^{\\pi^\\*}$\n\n$= \\max_\\pi\\min_w \\langle w,V^\\pi\\rangle$\n\n$\\ge \\min_w \\langle w,V^{\\pi_r^\\*}\\rangle$\n\n$=\\langle w^\\*(\\pi_r^\\*),V^{\\pi_r^\\*}\\rangle$\n\n$=\\langle w_r^\\*,V^{\\pi_r^\\*}\\rangle - \\langle w_r^\\* - w^\\*(\\pi_r^\\*), V^{\\pi_r^\\*}\\rangle.$\n\nThus, $V_{w_r^\\*}^{\\pi_r^\\*} - V^{\\pi^\\*}_{w^\\*} \\le \\langle w_r^\\* - w^\\*(\\pi_r^\\*), V^{\\pi_r^\\*}\\rangle$.\n\nFollowing the same logic in 1), the equation (1) results in,\n\n$\\langle w_r^\\* - w^\\*(\\pi_r^\\*), V^{\\pi_r^\\*}\\rangle$\n\n$=-\\tau_w(x_1-1)\\log x_1-\\tau_wx_2\\log x_2-\\cdots-\\tau_wx_K\\log x_K$\n\n$=\\tau_w(\\log x_1 -\\sum_k x_k\\log x_k)$\n\n$< \\tau_w (0 + \\log K)~(\\because H(x)\\le\\log K).$\n\nTherefore, we obtain upper bound $\\tau_w \\log K$.\n\nCombining 1) and 2), we obtain the suboptimality value gap $|V_{w_r^\\*}^{\\pi_r^\\*}-V_{w^\\*}^{\\pi^\\*}|\\le \\frac{\\tau\\log|A|}{1-\\gamma}+\\tau_w\\log K$."}]

Author rebuttal:

Meta-review: This paper proposes a game-theoretic framework for max-min multi-objective reinforcement learning with efficient single-loop algorithms and provable last-iterate convergence. Reviewers appreciated the theoretical insights, the adaptive regularization scheme, and the strong empirical improvements over prior work. Some concerns remain regarding clarity, missing related work, and limited novelty beyond practical contributions, but the authors’ rebuttal addressed most issues satisfactorily. Overall, I find the paper technically sound and recommend its acceptance as a poster.
Decision: Accept (poster)