🤖 AI

Adaptive Value Decomposition: Coordinating a Varying Number of Agents in Urban Systems

This paper proposes Adaptive Value Decomposition (AVD), a cooperative multi-agent reinforcement learning framework that effectively coordinates a dynamically varying number of agents in urban systems by addressing challenges such as asynchronous decision-making and action homogenization, demonstrating superior performance in real-world bike-sharing redistribution tasks.

Original authors: Yexin Li, Jinjin Guo, Haoyu Zhang, Yuhan Zhao, Yiwen Sun, Zihao Jiao

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yexin Li, Jinjin Guo, Haoyu Zhang, Yuhan Zhao, Yiwen Sun, Zihao Jiao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling city as a giant, living organism. In this organism, there are thousands of "cells" (bike stations) that need to stay healthy with a steady supply of "blood" (bikes). Sometimes, a station runs dry because everyone is riding away; other times, it's clogged because everyone is returning bikes.

To fix this, the city deploys a fleet of "nurses" (redistribution trucks) to move bikes from full stations to empty ones. This sounds simple, but managing these nurses is a nightmare for a computer trying to learn how to do it.

This paper introduces a new smart system called AVD (Adaptive Value Decomposition) to solve three specific headaches that make managing these nurses so difficult:

1. The "Chameleon" Problem: The Team Size Keeps Changing

The Issue: In a real city, you don't always have the same number of trucks. On a rainy Tuesday morning, you might need 10 trucks. On a sunny Sunday afternoon, you might only need 3. Most old computer programs are like rigid robots; they are trained to manage exactly 5 trucks. If you give them 3, they get confused. If you give them 7, they crash.

The AVD Solution: Think of AVD as a flexible conductor for an orchestra.

Old way: The conductor only knows how to lead a 5-piece band. If a violinist leaves, the music stops.
AVD way: The conductor can instantly adapt. If a musician walks in or out of the room, the conductor seamlessly rearranges the sheet music on the fly. AVD learns a "universal language" of coordination that works whether there are 2 trucks or 20. It doesn't care how many agents are in the room; it just knows how to get them to work together.

2. The "Clone" Problem: Everyone Doing the Same Thing

The Issue: To teach these trucks efficiently, computer scientists often give them all the exact same "brain" (shared policy). This is great for learning speed, but it has a side effect: Homogenization.
Imagine a group of clones. If they all see a crowd of people at a coffee shop, they all decide to rush to that same coffee shop at the exact same time. They end up bumping into each other, blocking the door, and getting in each other's way. They are so similar that they stop being a team and start being a traffic jam.

The AVD Solution: AVD introduces a "Spark of Chaos."

It gives each truck a tiny, random "nudge" in its decision-making process.
Imagine the trucks are all wearing the same uniform, but AVD secretly gives them slightly different colored hats.
When they see the same crowd, the truck with the red hat might think, "I'll go to the coffee shop," while the truck with the blue hat thinks, "Actually, I'll check the bakery down the street."
This tiny difference prevents them from all rushing the same spot, ensuring they spread out and cover more ground efficiently.

3. The "Traffic Jam" Problem: Actions Take Different Amounts of Time

The Issue: In real life, moving bikes isn't instant. One truck might be moving 5 bikes to a station 1 mile away (taking 10 minutes). Another might be moving 2 bikes 5 miles away (taking 30 minutes).
Old systems usually force everyone to stop and wait for the slowest truck before making the next move. It's like a relay race where the baton can't be passed until everyone has finished their lap, even if some runners are already done.

The AVD Solution: AVD uses a "Continuous Flow" strategy.

Instead of waiting for everyone to finish, the system lets trucks make decisions the moment they are free.
If Truck A finishes its job in 10 minutes, it immediately gets a new task. Truck B, still driving, keeps driving.
The system coordinates them asynchronously, like a busy kitchen where the chef doesn't wait for the dishwasher to finish a whole load before plating a new dish. They just keep the flow moving.

The Result: A Smoother City

The researchers tested this system using real data from bike-sharing programs in London and Washington, D.C.

The Test: They simulated thousands of days of bike rentals and returns.
The Winner: AVD consistently moved more bikes to where they were needed than any other method.
The Superpower: Even when they trained the system with 4 trucks and then tested it with only 3 (without retraining), it still worked amazingly well. It learned the concept of teamwork, not just a specific number of teammates.

In a Nutshell

This paper presents a smarter way to manage city resources. It teaches computers to manage teams that change size, avoid acting like clones, and keep moving even when tasks take different amounts of time. It's like upgrading from a rigid, stop-and-go traffic light system to a smart, flowing river that adapts to the terrain.

1. Problem Statement

The paper addresses the challenges of coordinating Multi-Agent Systems (MAS) in urban environments, specifically focusing on bike-sharing redistribution. The authors identify three critical limitations in existing Multi-Agent Reinforcement Learning (MARL) methods when applied to real-world urban systems:

Dynamic Agent Population: Most MARL algorithms assume a fixed number of agents. However, in urban systems (e.g., bike-sharing fleets), the number of active agents fluctuates due to operational demands, peak/off-peak cycles, and unexpected events.
Semi-MARL Setting (Asynchronous Actions): Urban agents often execute actions with heterogeneous durations (e.g., travel times vary by distance). This leads to a semi-MARL setting where agents act asynchronously, violating the assumption of fully synchronous action execution common in standard MARL.
Action Homogenization: To improve learning efficiency, MARL methods often share policy parameters across agents. However, when multiple agents face similar observations (e.g., high demand in the same area), shared policies lead to highly homogeneous actions. This reduces coordination quality as agents crowd the same locations rather than covering diverse needs.

2. Methodology: Adaptive Value Decomposition (AVD)

The authors propose Adaptive Value Decomposition (AVD), a cooperative MARL framework designed to handle variable agent populations and mitigate action homogenization.

A. Core Architecture

AVD builds upon the Value Decomposition technique (similar to QMIX) but adapts it for variable agent sets using Hypernetworks and Multi-Head Attention (MHA).

Agent Network: Instead of fixed input dimensions, the agent network uses MHA layers to process the state of the current active agent set ( $V_\tau$ ). This allows the network to generate embeddings that capture semantic relationships between agents regardless of the set size.
Mixing Network: A hypernetwork dynamically generates weights and biases for the mixing function based on the global state and agent embeddings.
Monotonicity Constraint: The mixing function ensures that $\frac{\partial Q_{tot}}{\partial Q_v} \geq 0$ . This guarantees that maximizing individual agent values leads to maximizing the global team value, enabling Decentralized Execution after Centralized Training (CTDE).

B. Mitigating Action Homogenization

To prevent agents from converging on identical behaviors due to shared policies, AVD introduces a lightweight mechanism:

Dispersed Initialization: At the start of each episode, agents are initialized in spatially dispersed locations (clustered based on task-relevant areas) to ensure they begin with diverse local conditions.
Stochastic Perturbation: Small Gaussian noise is injected into the agent embeddings at every decision step. This encourages agents with similar observations to explore slightly different actions, fostering behavioral diversity without breaking the efficiency of parameter sharing.

C. CTDE-based Training-Execution Strategy for Semi-MARL

To handle asynchronous action durations:

Training: The system treats temporally extended actions as step-level transitions. If an agent is still executing a previous action, it continues that action; otherwise, it selects a new one. These transitions are stored in a replay buffer.
Execution: Agents make independent decisions based on their current state. If an action is ongoing, the agent persists with it. The monotonicity constraint ensures that these independent, asynchronous decisions still achieve cooperative optimality.

3. Key Contributions

Algorithmic Innovation (AVD): A cooperative MARL framework that natively supports a variable number of active agents via attention mechanisms and hypernetworks, eliminating the need for padding or fixed-agent assumptions.
Homogenization Mitigation: A novel, lightweight mechanism combining dispersed initialization and stochastic embedding perturbation to maintain behavioral diversity among agents sharing policy parameters.
Semi-MARL Strategy: A tailored CTDE training-execution strategy that accommodates asynchronous action execution with heterogeneous durations, a common feature in urban logistics.
Benchmark Contribution: The release of a high-fidelity bike-sharing simulator capable of instantiating real-world data, serving as a standardized benchmark for urban resource redistribution.

4. Experimental Results

The authors evaluated AVD on real-world bike-sharing datasets from London (Santander Cycles) and Washington, D.C. (Capital Bikeshare).

Performance vs. Baselines: AVD significantly outperformed state-of-the-art baselines, including:
- Heuristics: No Action, Cooperative Greedy, OPT (Optimization-based).
- RL Methods: IDQN (Independent), VDN+, QMIX.
- Key Finding: While QMIX and VDN+ struggled or failed when the agent count changed, AVD maintained stable performance gains. In dynamic settings (agents varying from 4 to 2), AVD outperformed the best dynamic-capable baselines (OPT, VDN+).
Zero-Shot Generalization: Policies trained with 4 agents were deployed directly in scenarios with 3 agents (without retraining). AVD achieved performance comparable to or better than models trained specifically on 3 agents, demonstrating strong generalization to unseen agent cardinalities.
Robustness: In the Washington, D.C. dataset (lower demand, stricter conditions), AVD remained robust, while other baselines (like QMIX and OPT) showed significant performance degradation compared to simpler heuristics.
Ablation Studies: Removing the homogenization mitigation mechanism resulted in consistent performance drops, confirming its necessity for effective coordination.

5. Significance

This work bridges the gap between theoretical MARL algorithms and practical urban system deployment.

Realism: It moves beyond the restrictive "fixed agent, synchronous action" assumptions that limit the applicability of current MARL methods in real-world logistics.
Efficiency vs. Diversity: It solves the trade-off between the computational efficiency of parameter sharing and the need for diverse agent behaviors, a critical issue in crowded urban environments.
Scalability: By supporting dynamic agent populations, AVD offers a scalable solution for urban systems where workforce availability fluctuates, such as ride-sharing, delivery fleets, and emergency response units.
Resource: The release of the simulator provides a valuable tool for the research community to further study multi-agent coordination in dynamic urban settings.