Research map / Reinforcement learning / Policy gradient and actor-critic
The Max-Min Formulation of Multi-Objective Reinforcement Learning: From Theory to a Model-Free Algorithm
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a model-free value-based algorithm for max-min multi-objective RL, combining entropy-regularized LP/convex duality with a Gaussian-smoothing linear-regression gradient estimate for the weight vector.
Problem
Multi-objective RL with a max-min (egalitarian) fairness objective over K reward dimensions, where existing methods (weighted sum, utilitarian, Fair-DQN style) either fail to find the max-min policy or need the model; the goal is a model-free algorithm that solves max-min MORL.
Approach
Reformulate max-min MORL as an LP and its dual, add entropy regularization to make the problem convex and recover the policy explicitly, then optimize the scalarization weights over the simplex via soft value iteration alternated with a regression-based (Gaussian smoothing) gradient estimate of the dual objective.
Key results
- In Four-Room, the proposed method reaches return vector (0.96, 2.88) with min 0.96, versus 0.60 for MDQN and 0.76 for Utilitarian.
- On traffic light control, the proposed method achieves better max-min performance than baselines and reduces the across-direction return std to 174.8 versus 937.2 for Utilitarian.
- Ablation: disabling weight learning widens the North-South vs East-West gap; a sufficient number of perturbed samples (around N=20) is needed for accurate weight gradients.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed max-min method instead of MDQN | Four-Room · Four-Room | Min: 0.60 -> 0.96 | Helped |
| Use the proposed max-min method instead of Utilitarian | Four-Room · Four-Room | Min: 0.76 -> 0.96 | Helped |
| Use the proposed max-min method instead of Utilitarian | Traffic light control · Traffic light control | Standard deviation across four dimensions: 937.2 -> 174.8 | Helped |
| Add learned weight updates instead of keeping uniformly initialized weights (ablation) | Proposed method · Traffic light control | Minimum return across four dimensions | Helped |
| Increase the number of perturbed samples N for linear regression (ablation) | Proposed method · Traffic light control | Minimum return across four dimensions | Helped |
Surprising findings
- Naively solving the unregularized LP (P1) recovers the optimal max-min value but not necessarily an optimal max-min policy, due to indeterminacy in the primal recovery.
Limitations
- Max-min Pareto point may not lie on the equalizer line, so the weighted-max-min recovery argument does not always hold (e.g., Four-Room).
- Entropy-regularized solution is only approximately max-min as the temperature alpha goes to zero.
- Experiments are limited to small tabular-style benchmarks and a single traffic simulator.
Experimental setup
Datasets: Four-Room traffic light control simulation Species Conservation
Benchmarks: Four-Room traffic light control Species Conservation
Metrics: max-min value min_k E[sum_t gamma^t r_t^(k)] per-dimension expected discounted return
Baselines: Utilitarian DQN Fair Min-DQN (MDQN)
Builds on: soft Q-learning deep Q-network Fair-DQN linear programming formulation of RL Gaussian smoothing gradient estimation
Closest papers by meaning
- Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach (NeurIPS 2025 · similarity 0.94)
- An Analytical Study of Utility Functions in Multi-Objective Reinforcement Learning (NeurIPS 2024 · similarity 0.89)
- Reward Dimension Reduction for Scalable Multi-Objective Reinforcement Learning (ICLR 2025 · similarity 0.88)
- An Offline Adaptation Framework for Constrained Multi-Objective Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
- Preference Conditioned Multi-Objective Reinforcement Learning: Decomposed, Diversity-Driven Policy Optimization (NeurIPS 2026 · similarity 0.88)
- Preference Optimization on Pareto Sets: On a Theory of Multi-Objective Optimization (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.