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

AI summary

Overview

• Research area: Multi-objective reinforcement learning (MORL), specifically the max-min (fairness-oriented) criterion, approached through game theory, convex optimization and no-regret learning.
• Technical level: Advanced. The paper mixes stochastic games, mirror descent / natural policy gradient theory, entropy regularization, and finite-time convergence/complexity analysis.
• Scope: The paper reformulates entropy-regularized max-min MORL as a two-player zero-sum regularized continuous game, proposes two practical algorithms (ERAM and ARAM) built on that reformulation, and provides last-iterate convergence, iteration-complexity and sample-complexity guarantees in the tabular setting.

What This Paper Is About

Standard MORL rewards are vectors rather than scalars, and a widely used way to handle them is a scalarization (utility) function. This paper targets the specific case where the utility is the minimum over objectives, i.e. max over policies of the minimum objective value — a criterion that matters whenever fairness across objectives is the goal. The problem is that the min operator is non-linear and non-differentiable, so ordinary RL methods do not apply, and the most closely related prior model-free algorithm (Park et al.) is model-free but has high memory and compute cost and only guarantees average-iterate convergence. The paper's goal is to build a single-loop, memory-efficient algorithm with a closed-form adversary update and provable last-iterate convergence.

Key Contributions

1. A single-loop algorithm for entropy-regularized max-min MORL. The authors reformulate the problem as a two-player zero-sum regularized continuous game (Learner = policy, Adversary = weight vector w on the simplex) and use entropy regularization on both players to obtain a closed-form update for w, avoiding an inner optimization loop.
2. A primal-dual theoretical analysis in the tabular case. The paper proves global last-iterate convergence (rather than average-iterate), derives iteration complexity for both exact and approximate policy evaluation, and derives a sample-complexity bound.
3. An adaptively regularized variant, ARAM. ARAM replaces the uniform reference distribution behind the entropy regularizer with a dynamically computed reference vector c that captures correlation between each reward component and the worst-performing objective in the previous iteration batch.
4. Empirical validation in tabular and deep settings. Convergence behavior is demonstrated in tabular simulations, and a PPO-based deep implementation is reported to significantly outperform previous baselines across several MORL environments, including a realistic traffic signal control task.

Main Findings

• Saddle-point equivalence. Theorem 3.1 shows that if (π̄, w̄) is a saddle point of the min-max form min_{w∈Δ^K} max_π ⟨w, V_τ^π⟩, then π̄ solves the entropy-regularized max-min MORL problem. The max-min value equals the min-max value here, even though value functions are non-concave in the policy, so the equality cannot be obtained from the standard minimax theorem.
• Closed-form updates. The policy update in the tabular softmax case is π_{θ_{t+1}}(a|s) = (1/Z_π(t,s)) (π_{θ_t}(a|s))^α exp((1-α)/τ · Q_{w_t,τ}^{π_{θ_t}}(s,a)) with α = 1 - ητ/(1-γ). The adversary update is w_{t+1} = softmax(-(1-β)/τ_w · V^{π_{θ_t}} + β log w_t) with β = 1/(λτ_w + 1) ∈ (0,1) for any choice of λ and τ_w. The authors note that a conventional MD update would give β = 1 - λτ_w, so the modified form was preferred because β ∈ (0,1) is guaranteed.
• Global last-iterate convergence with exact policy evaluation (Theorem 4.1). The gaps decay geometrically: ‖log π* - log π_t‖_∞ ≤ C₁[ρ(η,λ)]^t, ‖w* - w_t‖_∞ ≤ C₂[ρ(η,λ)]^t, and ‖Q^{π*}_{w*,τ} - Q^{π_t}_{w_t,τ}‖_∞ ≤ C₃[ρ(η,λ)]^t, where 0 < ρ(η,λ) ≤ 1 - ε²/2 < 1, subject to η = ε(1-γ)/τ, τ_w ≥ 12K(max_{s,a,k}|r_k(s,a)| + τ log|A|)² / (τ(1-γ)⁴) > 0, and ε ∈ (0, ε₀).
• Two-timescale structure. The weight step size should be smaller-scaled than the policy step size: λ = O(ε²) versus η = O(ε). Intuitively, the policy must be updated faster than the weight. More generally, λ = O(ε^p) with p > 1 suffices.
• Iteration complexity (Corollary 4.2). With exact policy evaluation, softmax policy and the stated step sizes, reaching ε_acc accuracy in ‖log π* - log π_t‖_∞, ‖w* - w_t‖_∞ and the Q gap requires at most O((1/ε²) log(1/ε_acc)) iterations.
• Robustness to approximate policy evaluation (Theorem 4.3, Corollary 4.4). If value estimates satisfy ‖Q̂^π_{w,τ} - Q^π_{w,τ}‖_∞ < δ and ‖Q̂_k^π - Q_k^π‖_∞ < δ for any π, w, k, convergence still holds, but the bounds gain additive D̂ᵢ δ/ε² terms. The same O((1/ε²) log(1/ε_acc)) iteration count applies to achieve 2ε_acc accuracy, provided δ ≤ ε²ε_acc/D̂ᵢ.
• Sample complexity (Corollary 4.4). Using fresh samples for policy evaluation for each objective at every iteration and a union bound over objectives and iterations, Algorithm 2 requires at most Õ(K / ((1-γ)³ ε⁶ ε_acc²)) samples per state-action pair.
• Regularization gap (Remark 4.5). The difference between the optimal value function induced by the regularized game and that of the unregularized counterpart (τ = τ_w = 0) is upper-bounded linearly in τ and τ_w, so sufficiently small regularization coefficients keep the solution close to the original max-min MORL problem.
• Generality over GGF-PPO. The paper argues that setting τ_w = 0 and removing the Bregman divergence D_ψ(w, w_t) from its w update reduces the method to GGF-PPO, where w collapses to a one-hot vector on the minimum value dimension, and that this one-hot regime only admits average-iterate convergence.
• ARAM's adaptive reference. ARAM uses c_i = softmax(E_{s,a}[r_i(s,a) r_{i'}(s,a)]) for i = 1, ..., K, where i' is the index of the worst-performing objective at the previous iteration batch and the expectation is replaced by a sample expectation. This spreads emphasis across poorly performing objectives without focusing solely on the worst one (unlike GGF-PPO).
• Experiment numbers. The provided content is truncated before the experimental section, so specific benchmark names, environment counts, dataset sizes, and numeric scores are not reported in the supplied text. The paper states only that the deep RL implementation (using PPO) "significantly outperforms previous baselines in many MORL environments," including a realistic traffic signal control task.
• Code release. Source code is at https://github.com/whbyeon/ERAM-ARAM.

Methodology in Plain English

1. Turn the fairness objective into a game. The max-min objective asks for a policy that maximizes the smallest of K value functions. Because min over K discrete objectives is awkward to optimize, the authors first rewrite it as a min over a continuous weight vector w on the probability simplex: max_π min_{w∈Δ^K} ⟨w, V_τ^π⟩. This converts the discrete selection into a continuous variable that can be optimized by gradient-type methods.
2. Flip the order of max and min. The reformulation of Park et al. shows the problem is equivalent to minimizing the optimal soft value over w. Combining the two gives an equality between a max-min problem and a min-max problem, which is exactly the shape of a two-player zero-sum game. The paper proves that a saddle point of this game yields a solution of the original entropy-regularized max-min MORL problem.
3. Regularize both players. The Learner (policy) gets an entropy regularizer so that stochastic optimal policies are representable — the paper notes that stationary deterministic policies are insufficient for max-min MORL because some MOMDPs have only a stochastic optimal policy. The Adversary (weights) gets a negative-entropy regularizer. This deliberately stops w from collapsing to a one-hot vector on the worst objective, spreads attention across multiple objectives, speeds up learning, and — critically — makes last-iterate convergence provable. The choice of negative entropy rather than squared l₂ also makes the update closed-form.
4. Use mirror descent with KL divergence. Both updates are written as mirror-descent steps with a KL-divergence Bregman divergence. For the policy this amounts to natural policy gradient. In the tabular softmax case this produces a multiplicative, exponentiated policy update; the weight update produces a softmax expression mixing the negative value vector with log w_t.
5. For deep RL, swap in PPO. Because computing the Fisher information matrix is difficult with general nonlinear neural network parameterization, the authors replace the NPG step with TRPO/PPO, and use PPO in the deep implementation.
6. Add an adaptive twist for performance. ARAM generalizes the entropy regularizer, which is a KL divergence from the uniform distribution, into a KL divergence from a dynamically updated reference c computed from the correlation between each objective's reward and the currently worst-performing objective. The closed-form weight update is retained.
7. Analyze in the tabular case. All convergence, iteration-complexity and sample-complexity results are proved for tabular MOMDPs with a softmax policy, first under exact policy evaluation and then under bounded approximate evaluation error.

Why This Matters

Impact on research. The paper shifts max-min MORL from a double-loop or bilevel construction to a single-loop primal-dual game formulation with a closed-form adversary step. It upgrades the guarantee from average-iterate to global last-iterate convergence, which is a stronger and more practically meaningful notion, and it supplies finite-time iteration and sample complexity bounds — two quantities that were not available for the closest prior model-free max-min MORL algorithm. It also positions GGF-PPO as a special case of its own update, giving a unified view of a family of fairness-oriented MORL methods.

Real-world applications (as listed in the paper):

• Autonomous vehicles, where safety, comfort, and progress objectives must be traded off simultaneously.
• Resource allocation and communication systems, where fairness across users or tasks matters more than total throughput.
• Cloud computing resource scheduling, where a job is split into subtasks run on different resources and total job time is the maximum of subtask completion times — a natural max-min structure.
• Traffic signal control at intersections, where the goal is to minimize the maximum waiting time across all roads rather than the sum, for fairness across drivers.

The paper also discusses proportional fairness and other scalarization criteria in its appendix.

Industry relevance. Any deployment that must serve many agents or users fairly — cloud schedulers, network resource managers, traffic control systems, robotics fleets — can frame its objective as max-min. The closed-form weight update and single-loop structure matter directly for engineering cost, since they reduce memory footprint and compute relative to double-loop or model-based alternatives, and the deep RL implementation is a PPO-based drop-in style extension that practitioners can adopt.

Future Directions

• Theory for ARAM. The paper explicitly leaves theoretical analysis of the adaptively regularized variant (ARAM) as future work; only ERAM is analyzed.
• Theory beyond the tabular case. The convergence, iteration-complexity and sample-complexity results assume a tabular MOMDP with softmax policy parameterization and a closed-form policy update. Extending the guarantees to linear function approximation or general neural network policies is not established here.
• Tighter sample complexity. The reported bound is Õ(K / ((1-γ)³ ε⁶ ε_acc²)) samples per state-action pair, which has a high polynomial dependence on 1/ε; reducing this dependence is a natural open problem.
• Broader utility functions. The formulation is specialized to the min utility; whether the same game-theoretic single-loop construction extends to other non-linear social welfare functions (for example Nash social welfare or the wider generalized Gini family discussed in the related work) is an open question.

Target Audience

This paper is best suited for researchers and graduate students working on multi-objective reinforcement learning, fair or constrained RL, game-theoretic learning and multi-agent optimization, and the theory of mirror descent and natural policy gradient. It is also relevant to theoretically inclined engineers who need convergence guarantees for fairness-critical decision systems such as traffic control, cloud scheduling, and communication resource allocation. Readers without a background in convex optimization, stochastic games, or policy gradient theory will find the theoretical sections demanding; the game reformulation and the algorithmic recipes (ERAM/ARAM) are the most accessible parts.

Authors’ 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.