Abstract
This work considers multiple agents traversing a network from a source node to a goal node, where the cost of traveling a link includes both a private component and a public congestion component. We model this as a fully decentralized multi-agent reinforcement learning (MARL) problem and propose the Multi-Agent Congestion Cost Minimization (MACCM) algorithm. MACCM utilizes linear function approximations for transition probabilities and global cost functions. To preserve privacy and operate without a central controller, agents communicate cost function parameters to neighbors via a time-varying network. Each agent maintains an estimate of the global state-action value, updated via a Multi-Agent Extended Value Iteration (MAEVI) sub-routine. We prove that MACCM achieves sub-linear regret. Empirical validation on a two-node network demonstrates that the algorithm successfully identifies optimal policies, with average regret approaching zero for 2 and 3 agents as it learns the trade-off between waiting costs and congestion penalties.
Introduction
Shortest path problems are fundamental to routing and logistics. However, traditional models often assume a single agent, ignoring the reality that independent agents competing for the same path create congestion, thereby increasing costs for everyone. Furthermore, an agent's true cost is often a hybrid of public congestion and private factors, such as vehicle-specific fuel efficiency. This paper addresses the challenge of finding optimal paths for multiple agents to minimize overall congestion cost in a completely decentralized manner, without requiring agents to reveal private actions or costs.
Methodology
The MACCM algorithm addresses the exponential growth of state and action spaces in multi-agent environments through several key innovations:
- Linear Function Approximations: Transition probabilities are modeled using Linear Mixture MDPs, and global cost functions are similarly approximated to manage complexity.
- Privacy-Preserving Consensus: Instead of sharing raw actions or costs, agents maintain and share parameterized estimates of the global cost function with immediate neighbors. Over time, these parameters converge to the true global values.
- Optimism in the Face of Uncertainty (OFU): Agents use optimistic estimates of state-action values to guide their routing decisions.
- Multi-Agent Extended Value Iteration (MAEVI): To manage the computational burden of value function updates, the MAEVI sub-routine is triggered only when specific "doubling criteria" are met, reflecting the diminishing returns of learning over time.
Experimental Validation and Results
The algorithm was evaluated using a custom simulated environment consisting of a 2-node network with multiple links. While structurally simple, this setup serves as a "hard instance" in RL literature because the state and action spaces scale exponentially with the number of agents, testing the algorithm's ability to handle high-dimensional coordination.
Theoretical and Empirical Performance
The authors mathematically prove that MACCM achieves a sub-linear regret bound of $\tilde{O}(B^{1.5} d \sqrt{nK/c_{min}})$. This theoretical guarantee ensures that as the number of episodes ($K$) increases, the algorithm's performance converges toward the optimal policy.
Empirically, the algorithm successfully learned the optimal departure sequence, effectively balancing the cost of staying at a node versus the congestion penalty of moving. As shown in the regret analysis, the average regret ($Regret/K$) converges toward zero for both 2-agent and 3-agent scenarios over 7,000 episodes.
Conclusion and Future Work
MACCM successfully generalizes the Stochastic Shortest Path (SSP) problem to a multi-agent domain with coupled congestion costs. While the MAEVI routine currently presents a computational bottleneck for scaling to many agents, it provides a robust framework for privacy-preserving decentralized learning. Future research will focus on developing tighter regret bounds, exploring parameterized policy spaces, and incorporating hard capacity constraints on network links to handle more complex real-world scenarios.
Summary updated