Multi-Agent Congestion Cost Minimization With Linear Function Approximations
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 15 of its 34 references that are in the map. First posted on arXiv 26 Jan 2023.
Builds on
15 of 34 references.
References · 15
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
- 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
- 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 189
- 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
- 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
- 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
- 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
- 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
- 2021Minimax Regret for Stochastic Shortest Pathcited by 30
- 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
- 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
Built on by
Citing papers per year: 2025: 1.
1 paper.