Constrained Multi-Objective Reinforcement Learning with Max-Min Criterion

Multi-objective reinforcement learning (MORL) has evolved from simple scalarization techniques to sophisticated preference-based models, with key contributions from Roijers et al. (2013) and Hayes et al. (2022). Traditional methods primarily optimize weighted sums, which inadequately capture fairness or specific policy preferences. Max-min fairness, inspired by classical optimization, has gained attention for its ability to promote equitable outcomes across objectives, especially in applications like cloud resource management, societal fairness, and traffic control. However, existing max-min MORL algorithms are mostly unconstrained, limiting their practical deployment where resource limits, emission caps, or safety constraints are critical. Recent advances have introduced constrained RL frameworks, but these often lack the ability to handle multiple conflicting objectives with fairness considerations. This gap motivates the development of a unified approach that combines the theoretical rigor of convex optimization with the practical needs of multi-objective decision-making.

The core challenge lies in integrating the max-min fairness criterion with explicit constraints in a computationally tractable manner. Existing algorithms either approximate the max-min objective via lower bounds or rely on inexact gradient estimates, which compromise solution accuracy. Moreover, handling multiple objectives with conflicting goals and constraints simultaneously remains unresolved. This problem is compounded by the non-convexity and non-differentiability of the max-min function, making standard gradient-based methods ineffective. Addressing this requires a reformulation that preserves the problem’s structure, guarantees convergence, and ensures constraint satisfaction, which is non-trivial given the complex interplay between objectives and operational limits.

The key innovations include: 1) reformulating the constrained max-min MORL as a convex optimization over occupancy measures, enabling exact gradient computation; 2) deriving a dual problem that admits a tractable solution with convergence guarantees; 3) integrating entropy regularization to smooth the optimization landscape; 4) designing an alternating optimization algorithm that updates value functions and weights iteratively, ensuring fairness and constraint compliance simultaneously. This approach fundamentally differs from prior heuristic or approximate methods, providing a rigorous theoretical foundation and practical algorithm capable of handling complex multi-objective constrained problems.

• �� Model the multi-objective Markov decision process (MOMDP), defining state, action, transition, reward, and constraint functions.
• �� Reformulate the max-min objective as a convex optimization problem over occupancy measures, incorporating entropy regularization.
• �� Use Lagrangian duality to derive a dual problem involving dual variables u,w, representing target fairness and constraint weights.
• �� Develop an iterative algorithm:
• Fix weights, update the value function Q via a Bellman-like equation incorporating dual variables.
• Compute gradients of the loss function with respect to u,w using value functions under the current policy.
• Update u,w using projected gradient descent, ensuring they stay within feasible regions.
• Extract policies from the updated Q-functions using softmax policies.
• �� Prove convergence by analyzing the smoothness and positive definiteness of the Hessian of the convex program, supported by theoretical bounds.
• �� Implement the algorithm in tabular environments and validate in simulated tasks, measuring convergence speed, fairness, and constraint satisfaction.

Experiments were conducted in randomly generated tabular environments with multiple objectives and constraints, including energy consumption, fairness, and emission limits. Baselines included traditional max-min and unconstrained methods. Metrics evaluated were convergence error, fairness indices, and constraint violation rates. The algorithm consistently converged within 500 iterations, achieving errors below 1e-4. In practical tasks like building thermal control, it reduced energy use by 10% while maintaining temperature balance. Traffic experiments showed a 15% reduction in maximum waiting time and strict emission compliance. Ablation studies confirmed the importance of entropy regularization and dual variable updates for stability and accuracy.

Results demonstrate rapid convergence and superior performance over baselines. In the thermal control task, energy consumption decreased by 10%, temperature variance was within 2°C, and constraints were fully satisfied. Traffic management saw a 15% reduction in maximum queue length, with emission levels below regulatory thresholds. Locomotion tasks achieved balanced gait patterns and energy efficiency, with fair distribution of rewards across objectives. The method maintained robustness under parameter variations, validating the theoretical guarantees and practical applicability.

This framework is applicable in industrial scheduling, smart grids, autonomous vehicles, and urban traffic systems, where multiple conflicting objectives and operational constraints coexist. It enables decision-makers to balance fairness, efficiency, and compliance simultaneously, especially in resource-limited environments. The approach can be integrated with deep reinforcement learning for large-scale problems, facilitating deployment in real-world complex systems such as energy management, transportation, and manufacturing.

Current implementation relies on finite state spaces; extending to continuous domains requires function approximation and introduces approximation errors. Computational costs grow with problem size, demanding scalable algorithms. Sensitivity to hyperparameters like learning rate and regularization coefficient can affect convergence. Robustness to model inaccuracies and environment non-stationarity remains a challenge. Future work should focus on deep learning integration, scalable approximation, and adaptive parameter tuning to enhance real-world deployment.