Multi-Agent congestion cost minimization with linear function approximations

Prashant Trivedi, Nandyala HemachandraAISTATS 2023 · OpenReview

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.
Algorithm 2: The Multi-Agent EVI routine used for decentralized value function updates.

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.

Average regret normalized by the number of episodes ($Regret/K$) vs $\sqrt{K}$ for 2 and 3 agents, demonstrating convergence.

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

Abstract

This work considers multiple agents traversing a network from a source node to the goal node. The cost to an agent for traveling a link has a private as well as a congestion component. The agent’s objective is to find a path to the goal node with minimum overall cost in a decentralized way. We model this as a fully decentralized multi-agent reinforcement learning problem and propose a novel multi-agent congestion cost minimization (MACCM) algorithm. Our MACCM algorithm uses linear function approximations of transition probabilities and the global cost function. In the absence of a central controller and to preserve privacy, agents communicate the cost function parameters to their neighbors via a time-varying communication network. Moreover, each agent maintains its estimate of the global state-action value, which is updated via a multi-agent extended value iteration (MAEVI) sub-routine. We show that our MACCM algorithm achieves a sub-linear regret. The proof requires the convergence of cost function parameters, the MAEVI algorithm, and analysis of the regret bounds induced by the MAEVI triggering condition for each agent. We implement our algorithm on a two node network with multiple links to validate it. We first identify the optimal policy, the optimal number of agents going to the goal node in each period. We observe that the average regret is close to zero for 2 and 3 agents. The optimal policy captures the trade-off between the minimum cost of staying at a node and the congestion cost of going to the goal node. Our work is a generalization of learning the stochastic shortest path problem.
BibTeX
@inproceedings{trivedi2023multi,
  author = {Prashant Trivedi and Nandyala Hemachandra},
  title = {{Multi-Agent congestion cost minimization with linear function approximations}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=h3Ry0DNKD6},
}
Figure