Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach

Novelty and Relation to Park et al. (2024) (Weaknesses 1)

We 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.

Moreover, 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.

[Ref.] Park et al., "The max-min formulation of multi-objective reinforcement learning: From theory to a model-free algorithm," ICML, Jul. 2024

More on Complexity Comparison (Weaknesses 2, Question 6)

Thank 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.

Regarding 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.

Regarding Writings (Weaknesses 3, Question 7)

We 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.

Clarification on Max-Min Objective (Questions 1)

We 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.

Regarding Policy Parameterization Beyond Softmax (Questions 2)

We 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.

Deeper Theoretical Analysis on $\tau_w$ (Questions 3)

The 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.

Regarding 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.

[Impact of $\tau_w$ on Convergence Speed]

From 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.

[Impact of $\tau_w$ on Suboptimality Value Gap by Regularization]

Let the optimal solutions for the regularized game be $w_r^\*,\pi_r^\*$. Let the optimal solutions for unregularized game be $w^\*,\pi^\*$.

We 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: $|V_{w_r^\*}^{\pi_r^\*}-V_{w^\*}^{\pi^\*}|\le \frac{\tau\log|A|}{1-\gamma}+\tau_w\log K$. Note that, suboptimality value gap by regularization is linear in $\tau,\tau_w$.

[Trade-off Between Convergence Speed and Suboptimality Gap Induced by $\tau_w$]

To 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.

We hope this analysis addresses your concern regarding the deeper analysis on impacts of $\tau_w$ on convergence and suboptimality gap.

Control of Estimation Error (Questions 4)

The 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.

Investigating how to correct for error propagation when value estimates are considerably inaccurate in deep RL remains an interesting direction for future work.

Additional Baselines (Questions 5)

Thank 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.

As 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.

[Appendix. Proof for Suboptimality Value Gap by Regularization]

Let 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^\*)$.

Similarly, let the optimal solutions for unregularized game be $w^\*(\pi) := arg\min_w \langle w,V^\pi\rangle$, $\pi^\*:=arg\max_\pi \min_w \langle w,V^\pi\rangle$. Let $w^\* = w^*(\pi^\*)$.

1). lower bound

$V_{w_r^\*}^{\pi_r^\*} + \tau\tilde{H}(\pi_r^\*)-\tau_w H(w_r^\*)$

$= \max_\pi\min_w \langle w,V^\pi\rangle+\tau\tilde{H}(\pi)-\tau_w H(w)$

$\ge \min_w \langle w,V^{\pi^\*}\rangle+\tau\tilde{H}(\pi^\*)-\tau_w H(w)$

$=\langle w_r^\*(\pi^*),V^{\pi^\*}\rangle+\tau\tilde{H}(\pi^\*)-\tau_w H(w_r^\*(\pi^\*))$

$=\langle w^\*,V^{\pi^\*}\rangle + \langle w_r^\*(\pi^\*)-w^\*, V^{\pi^\*}\rangle + \tau\tilde{H}(\pi^\*)-\tau_w H(w_r^\*(\pi^\*)).$

Since $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

$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.$

We show that $\langle w_r^\*(\pi^\*)-w^\*, V^{\pi^\*}\rangle\ge0$.

For simplicity, we denote $V^{\pi^\*}_k$ as $V_k$. Without 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}$. Note 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$. By definition, $w^\* = w^\*(\pi^\*) = (1,0,\ldots,0)$. Then,

$\langle w_r^\*(\pi^\*)-w^\*, V^{\pi^\*}\rangle$

$= (x_1-1)V_1+x_2V_2+\cdots+x_KV_K$

$=-\tau_w(x_1-1)\log Sx_1-\tau_wx_2\log Sx_2-\cdots-\tau_wx_K\log Sx_K$

$=-\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)$

$=\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)$

$\ge \tau_w\cdot 0$ since $x_1\ge x_k>0$ and equality holds when $x_k=\frac{1}{K},\forall k$.

Therefore, we conclude that the suboptimality gap has lower bound $- \frac{\tau\log|A|}{1-\gamma}-\tau_w\log K$.

2). upper bound

$V_{w^\*}^{\pi^\*}$

$= \max_\pi\min_w \langle w,V^\pi\rangle$

$\ge \min_w \langle w,V^{\pi_r^\*}\rangle$

$=\langle w^\*(\pi_r^\*),V^{\pi_r^\*}\rangle$

$=\langle w_r^\*,V^{\pi_r^\*}\rangle - \langle w_r^\* - w^\*(\pi_r^\*), V^{\pi_r^\*}\rangle.$

Thus, $V_{w_r^\*}^{\pi_r^\*} - V^{\pi^\*}_{w^\*} \le \langle w_r^\* - w^\*(\pi_r^\*), V^{\pi_r^\*}\rangle$.

Following the same logic in 1), the equation (1) results in,

$\langle w_r^\* - w^\*(\pi_r^\*), V^{\pi_r^\*}\rangle$

$=-\tau_w(x_1-1)\log x_1-\tau_wx_2\log x_2-\cdots-\tau_wx_K\log x_K$

$=\tau_w(\log x_1 -\sum_k x_k\log x_k)$

$< \tau_w (0 + \log K)~(\because H(x)\le\log K).$

Therefore, we obtain upper bound $\tau_w \log K$.

Combining 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$.

We thank the reviewer for valuable comments. Below is our response to the reviewer's comments.

Novelty and Comparison with the Work of Cousins et al. (Question 1)

Thanks 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):

$\max_{d} \min_{1 \leq k \leq K} \sum_{s,a} d(s,a) r^{(k)}(s,a)$ $\sum_{a'} d(s',a') = \mu_0(s') + \gamma \sum_{s,a} P(s' | s,a) d(s,a) ~~ \forall s'$ $d(s,a) \geq 0, ~~ \forall (s,a),$

where $r^{(k)}(s,a)$ is the $k$-objective reward function.
This 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.

Our 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 $c$ as

$\max_{d(s,a), c} c$ $\sum_{s,a} r^{(k)}(s,a) d(s,a) \geq c, ~ 1 \leq k \leq K$ $\sum_{a'} d(s',a') = \mu_0(s') + \gamma \sum_{s,a} P(s' | s,a) d(s,a) ~~ \forall s'$ $d(s,a) \geq 0, ~~ \forall (s,a).$

Again, we do not solve this problem (requiring the model) directly. We consider the dual problem of this problem, given by

$\min_{w \in \Delta^K, v} \sum_s \mu_0(s) v(s)$ $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)$

where $\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)

$\min_{w \in \Delta^K}\sum_s \mu_0(s) v_{w}^\*(s) ~~~~~Eq.(R1)$

where $v_w^\*$ is the unique fixed point of the following operator:

$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]$

Thus, $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.

[Ref.] Park et al., "The max-min formulation of multi-objective reinforcement learning: From theory to a model-free algorithm," ICML, Jul. 2024

Novelty Compared to Other Primal-Dual Algorithms (Question 2)

Now, 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:

$\max_\pi V_r^\pi ~~s.t.~~~ V_{u^i}^\pi \ge c_i, \forall i.~~~ Eq.(R2)$

The strong duality (Paternain et al. 2019) of this problem says

$\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)$

where $L(\pi,\lambda) = V_r^\pi + \sum_i \lambda_i (V_{u^i}^\pi -c_i).$

Note 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 $\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.

In 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.

Now, consider the work of Eaton et al. [5] and the approach suggested by the reviewer. Eaton et al. basically considered constrained MDP: $\max_\pi V_r^\pi ~~s.t.~~~ V_{u^i}^\pi \ge c_i, \forall i.$

Consider the max-min approach, stated in the 2nd line after eq. (2) of Eaton et al.'s paper and suggested by the reviewer:

$\max_{\pi,c} ~c$ s.t. $V_{u^i}^\pi \ge c, ~\forall i.~~ Eq.(R4)$

Its Lagrangian is given by $L(\pi,c,\lambda) = c + \lambda_i (V_{u^i}^\pi-c).$

Eaton 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:

As seen, our algorithms (ARAM ad ERAM) significantly outperform GGF-PPO and GGF-PPO with time-averaged $\lambda$ (FairFictRL).

As 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.

In 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.).

Considering 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.

Other Comments and Questions

[How is epsilon chosen in Theorem 4.1?]

Any $\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.

[How does the regularized Q value compare to the unregularized?']

For 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, $|V_{w_r^\*}^{\pi_r^\*}-V_{w^\*}^{\pi^\*}|\le \frac{\tau\log|A|}{1-\gamma}+\tau_w\log K.$

This 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.

[Larger tabular experiments]

Please 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.

Choice of $\tau,\tau_w$ and $\lambda$ (Weakness 1)

Thank you for pointing out this important issue. Regarding $\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: Recall the ERAM update rule: $w_{t+1}=softmax(-\frac{1-\beta}{\tau_w}V_t+\beta\log w_t)$.

The 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.

To capture this balance, we compare the average magnitude of the two terms at convergence. Let $\frac{1-\beta}{\tau_w}\frac{1}{K} \sum_k V_k^{last}$ and $\beta H(w^{last})$ denote 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.

Similarly, 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.

This 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. Averaging 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.

We will clarify this heuristic in the revised version and consider analyzing its robustness more formally in future work.

Convergence Speed, Suboptimality Bound, and Trade-off Induced by $\tau,\tau_w$ (Weakness 2, Question 1)

Thank you very much for drawing our attention to these important points—they are highly valuable for strengthening our theoretical analysis.

[Convergence Speed]

From 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.
Note that with fixed learning rates $\eta,\lambda$, larger $\tau,\tau_w$ results in smaller $\rho$ and thus, faster convergence.

[Suboptimality Gap of Values by Regularization]

Let the optimal solutions for the regularized game be $w_r^\*,\pi_r^\*$. Similarly, let the optimal solutions for unregularized game be $w^\*,\pi^\*$.

We 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: $|V_{w_r^\*}^{\pi_r^\*}-V_{w^\*}^{\pi^\*}|\le\frac{\tau\log|A|}{1-\gamma}+\tau_w\log K.$ Note that, suboptimality gap of value by regularization is linear in $\tau,\tau_w$.

[Trade-off Between Convergence Speed and Suboptimality Gap]

To 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.

We appreciate the question and will include this analysis in our revision.

Complexity of Softmax and Convergence in Sparsity-Promoting Variants (Questions 2)

[Complexity of Softmax]

The 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.

[Convergence in Sparsity-Promoting Variants]

Regarding 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.

As 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.

Intuitively, 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.

Designing 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.

Fisher Matrix Approximation and Required Accuracy (Questions 3)

In 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.

In our analysis, the required accuracy primarily concerns the value estimates, rather than the Fisher matrix itself.

For 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.

In 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.

[Ref.] Cen, Shicong, et al. "Fast global convergence of natural policy gradient methods with entropy regularization." Operations Research 70.4 (2022): 2563-2578.

Validity of the Adaptive Scheme (Questions 4)

We 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.

Recall the ARAM update: $w_{t+1} = softmax(-\frac{1-\beta}{\tau_w}V^t + \beta\log w_t + (1-\beta)\log c_t)$ where $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: $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$. This shows that ARAM is equivalent to ERAM with an effective (time-varying) reward function that depends on the correlation with the current minimal objective.

This 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}$. The 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.

Although 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.

Discussion on DR-RL (Questions 5)

We 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.

Importance of Minimax Theorem 3.1 (Weakness 1)

We 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.

In 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.

Regarding Sample Complexity (Weakness 2)

We 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.

Novelty of Regularization Technique (Weakness 3)

We 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.

Regarding Writings (Weakness 4)

Thank 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.

Convergence in Park et al. (Questions 1)

The 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).

[Ref.] Nesterov, Yurii, and Vladimir Spokoiny. "Random gradient-free minimization of convex functions." Foundations of Computational Mathematics 17.2 (2017): 527-566.

Relation to Zero-Sum Markov Games (Questions 2)

Thank 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$.

To 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$.

This 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.

Key Theoretical Contributions (Questions 3)

As 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.

To 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.

[Ref.] Cen, Shicong, et al. "Fast global convergence of natural policy gradient methods with entropy regularization." Operations Research 70.4 (2022): 2563-2578.

Thank you for the positive assessment and for engaging in the discussion; your feedback has been greatly valuable.

We will revise the writing around Theorem 3.1 in the revised version to clarify our intent and avoid any potential misleading points you mentioned. We will also add a comparison and discussion with prior work on zero-sum Markov games.