Graphallocbench Enables Flexible Multi-Objective Policy Learning with Diverse Preference Conditions

Researchers are tackling the challenge of creating adaptable artificial intelligence capable of balancing multiple, often competing, goals through preference-conditioned policy learning in multi-objective reinforcement learning. Zhiheng Jiang from University of California, Los Angeles, Yunzhe Wang and Ryan Marr from USC Institute for Creative Technologies, along with Ellen Novoseller, Benjamin T Files, Volkan Ustun et al, have introduced GraphAllocBench, a new benchmark designed to assess progress in this field. This benchmark addresses a critical gap in current evaluation methods, which often rely on simplistic scenarios, by offering a realistic and scalable resource allocation environment inspired by city management. GraphAllocBench not only provides a diverse set of problems but also introduces novel metrics for evaluating how well AI systems adhere to specified preferences, promising to accelerate development of more flexible and intelligent multi-objective decision-making systems.

GraphAllocBench offers a diverse suite of problems with varying objective functions, preference conditions, and high-dimensional scalability, enabling more robust evaluation of PCPL methods. This finding paves the way for the application of graph-based methods, such as Graph Neural Networks, to complex, high-dimensional combinatorial allocation tasks. CityPlannerEnv models resource allocation as a sequential problem represented through bipartite resource-demand dependency graphs, mirroring the challenges faced in real-world city planning.

The environment simulates how cities allocate limited resources to meet diverse and often conflicting demands, reducing congestion, fostering economic growth, and promoting sustainability, all while adapting to changing preferences. Agents within CityPlannerEnv incrementally allocate resources by adding or removing productions for each demand, pursuing custom-defined objectives based on user preferences. This incremental allocation mechanism draws inspiration from the Multi-step Colonel Blotto Game, a model for competitive resource allocation on graphs. The benchmark includes test problems spanning diverse optimisation challenges, including difficult objective functions, non-convex Pareto fronts, sparse observation spaces, complex dependency structures, and high-dimensional graph observations. Through rigorous experimentation, the researchers demonstrate that GraphAllocBench not only challenges existing MORL methods but also provides a platform for developing and evaluating more sophisticated PCPL algorithms capable of handling complex, real-world resource allocation problems.

CityPlannerEnv and GraphAllocBench benchmark development are ongoing

The study engineered this environment to address limitations in existing multi-objective reinforcement learning (MORL) benchmarks, which often lack realism and scalability. Agents within the environment allocate resources by adding or removing productions for each demand at each time step, pursuing custom-defined objectives aligned with user preferences. This work pioneered an incremental allocation mechanism inspired by the Multi-step Colonel Blotto Game, a model for competitive resource allocation on graphs. The team implemented dependencies between resources and demands as bipartite graphs, enabling objectives to be defined over any subset of productions.

PNDS directly captures preference consistency, while OS complements the widely used hypervolume metric. Results indicate that graph-based methods, such as Graph Neural Networks, are particularly well-suited for complex, high-dimensional combinatorial allocation tasks within this framework. The innovative methodology enables a more nuanced evaluation of PCPL algorithms and facilitates progress in adapting policies to arbitrary trade-offs at run-time.

GraphAllocBench evaluates preference-conditioned multi-objective reinforcement learning algorithms

Results demonstrate that PCPL policies trained using Proximal Policy Optimization (PPO) on GraphAllocBench exhibit varying performance depending on the problem structure. For Problems 1a-c, which feature sharp changes in reward signals, the team recorded significantly higher variance and worse approximations of the Pareto Front compared to a baseline with a smooth objective function. Tests prove that non-convex Pareto Fronts, such as those in Problems 1c and 3b, pose challenges for accurate representation, even with smooth Tchebycheff Scalarization. Measurements confirm that unbalanced objectives, exemplified by Problem 2c, where one objective receives a sparser reward, result in a lower-quality approximation of intermediate values on the Pareto Front.

The study recorded instances of agents falling into local optima traps, as observed in Problem 2b, where the PCPL agent collapsed to local solutions and failed to generalize to the global Pareto front. For problems 6a-c, involving a large number of resources and productions, scientists implemented a Heterogeneous Graph Neural Network (HGNN) to represent the complex demand-resource dependencies. The HGNN-based feature extractor utilizes multiple Graph Attention Networks, one for each node type (Demand, Resource, Unallocated), with stacked layers and residual connections. Researchers hope to show that flexible pooling methods like Mean/Max Pooling and Attention Pooling can capture global information more effectively than MLPs, improving performance in complex combinatorial allocation tasks.

GraphAllocBench assesses preference learning in resource allocation scenarios

This benchmark addresses a gap in existing evaluations, which are often limited to simple tasks and fixed environments, by offering a more realistic and scalable platform for testing algorithms. Notably, equipping the PPO algorithm with a Heterogeneous Graph Neural Network feature extractor significantly outperformed standard MLP baselines, particularly on larger, more complex graphs. The authors acknowledge that the current benchmark focuses on specific dependency structures and lacks features like efficiency metrics or environmental uncertainty. Future work aims to address these limitations by incorporating richer dependencies, simulating events such as natural disasters, and evaluating risk-aware decision-making. GraphAllocBench therefore establishes a versatile and extensible testbed for advancing research in preference-aware many-objective policy learning, offering a valuable tool for developing algorithms capable of handling complex combinatorial allocation tasks.