Technical Summary: GraphAllocBench

1. Problem Statement

Multi-Objective Reinforcement Learning (MORL) addresses environments where agents must balance multiple, often conflicting objectives. A prominent approach, Preference-Conditioned Policy Learning (PCPL), trains a single policy conditioned on user-specified preference weights, enabling runtime adaptation to arbitrary trade-offs without retraining.

However, existing PCPL benchmarks suffer from significant limitations:

• Restricted Scope: They rely heavily on toy tasks (e.g., 2D grid worlds like Deep Sea Treasure) or fixed continuous optimization problems (e.g., DTLZ, WFG).
• Lack of Scalability and Flexibility: Current testbeds lack the ability to scale observations, actions, and dependency structures. They often feature fixed objective functions and simple topologies, failing to stress-test the robustness of PCPL methods in complex, high-dimensional scenarios.
• Evaluation Gaps: Standard metrics like Hypervolume (HV) often fail to capture prediction reliability or the degree to which a policy adheres to specific preference inputs, particularly in the presence of non-convex or discontinuous Pareto fronts.

2. Methodology

2.1 CityPlannerEnv: A Novel Sandbox

To address these gaps, the authors introduce CityPlannerEnv, a Gymnasium-based sandbox environment inspired by city-scale resource allocation.

• Structure: The environment models a bipartite graph connecting Resources (e.g., water, labor) and Demands (e.g., housing, transit).
• Mechanics: Agents perform sequential allocation by adding or removing production units for specific demands at each time step. This draws inspiration from the Multi-step Colonel Blotto Game.
• Customizability:
  • Objectives: Users can define custom objective functions using elementary mathematical operations (linear, quadratic, sinusoidal, step functions, etc.) over subsets of productions. This allows for the engineering of diverse Pareto Front geometries (convex, non-convex, multi-segment, oscillatory).
  • Scalability: The environment supports arbitrary numbers of resources, demands, and objectives, scaling up to massive dependency graphs.

2.2 GraphAllocBench: The Benchmark Suite

Built upon CityPlannerEnv, GraphAllocBench consists of 19 challenging evaluation problems categorized into six groups:

• Baseline: Smooth, convex Pareto fronts.
• Complex Landscapes: Problems with oscillatory, multi-segment, and sparse reward signals.
• Scalability: Problems increasing the number of demands (expanding action/observation spaces) and scaling to 5 objectives.
• Structural Complexity: Problems utilizing non-fully-connected and randomized bipartite dependency graphs.
• High-Dimensional Stress Tests: Large-scale problems with 100 demands and 100 resources.

2.3 Evaluation Metrics

Beyond the standard Hypervolume (HV), the paper proposes two supplementary metrics to address specific failure modes:

1. Proportion of Non-Dominated Solutions (PNDS): Measures the fraction of predicted solutions that are non-dominated. This assesses prediction reliability and helps identify if an agent is trapped in local optima, independent of the ideal Pareto Front.
2. Ordering Score (OS): A rank-correlation metric (Spearman) that evaluates how well the agent's objective values align with the input preference weights. It measures preference consistency rather than proximity to the Pareto Front, making it robust to magnitude differences and scalarization choices.

2.4 Algorithms and Baselines

The authors evaluate several state-of-the-art PCPL algorithms (PD-MORL, Envelope Q-Learning, PSL) and propose a new baseline: PCPL-PPO.

• PCPL-PPO: Uses Proximal Policy Optimization (PPO) with Smooth Tchebycheff Scalarization.
• Feature Extractors:
  • MLP: Standard Multi-Layer Perceptron.
  • HGNN: A Heterogeneous Graph Neural Network (using Graph Attention Networks) designed to capture the complex bipartite structure of the environment.
  • Preference Conditioning: The HGNN architecture incorporates preference vectors via concatenation at node embeddings and preference-conditioned attention pooling to enhance robustness to varying inputs.

3. Key Results

3.1 Benchmark Performance

Experiments across 19 problems reveal distinct failure modes that Hypervolume alone fails to capture:

• Hypervolume vs. Reliability: On several problems (e.g., Problem 5c), Pareto Set Learning (PSL) achieved the highest Hypervolume, but PCPL-PPO achieved superior PNDS and Ordering Scores. This indicates that high coverage does not guarantee reliable, preference-aligned predictions.
• Challenging Landscapes: PCPL-PPO demonstrated greater robustness on problems with sparse rewards, sharp reward changes, and non-convex Pareto fronts compared to other methods.
• Failure Modes: Agents struggled with local optima traps (Problem 2b) and discontinuous fronts (Problem 1c), often collapsing to suboptimal solutions or failing to generalize across the full Pareto front.

3.2 MLP vs. HGNN on Large Graphs

In high-dimensional settings (100x100 graphs, Problems 6a–6c):

• Hypervolume: HGNN-based approaches significantly outperformed MLP-based baselines, with the HGNN+AttentionPool variant achieving the highest Hypervolume scores.
• Preference Alignment: Interestingly, the MLP achieved higher Ordering Scores than the HGNN variants. This suggests a trade-off: while HGNNs better capture global coverage and scale to complex structures, MLPs may find more locally preference-aligned solutions.
• Efficiency: HGNN models had fewer parameters than the MLP baseline, as MLP parameters scale quadratically with the flattened allocation matrix size.

4. Significance and Contributions

The paper claims the following contributions:

1. GraphAllocBench: A flexible, graph-based benchmark that moves beyond toy tasks to capture complex resource allocation scenarios with customizable objectives, discrete non-convex Pareto fronts, and high-dimensional scalability.
2. Novel Evaluation Metrics: The introduction of PNDS and OS provides a more nuanced evaluation of PCPL algorithms, specifically addressing the limitations of Hypervolume in assessing prediction reliability and preference consistency.
3. Graph-Aware PCPL: The demonstration that HGNNs can learn preference-conditioned policies in complex dependency structures, offering a scalable alternative to MLPs for high-dimensional allocation tasks, while highlighting an open challenge regarding the trade-off between global coverage and per-objective preference alignment.

The authors position GraphAllocBench as a versatile testbed for advancing research in preference-aware many-objective policy learning, noting that future work will extend the benchmark to include richer dependency structures and environmental uncertainty.