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.

该论文提出了一种多智能体强化学习算法以实现分散式的最小化拥塞成本，该算法使用线性函数逼近过渡概率和全局成本函数，通过一个多智能体扩展价值迭代子例程维护全局状态动作值的估计，并通过动态通信网络共享成本函数参数以保护隐私。

使用线性函数逼近的多智能体拥塞成本最小化

Multi-Agent Congestion Cost Minimization With Linear Function Approximations

This paper studies Stochastic Shortest Path (SSP) problems in known and
unknown environments from the perspective of convex optimisation. It first
recalls results in the known parameter case, and develops understanding through
different proofs. It then focuses on the unknown parameter case, where it
studies extended value iteration (EVI) operators. This includes the existing
operators used in Rosenberg et al. [26] and Tarbouriech et al. [31] based on
the l-1 norm and supremum norm, as well as defining EVI operators corresponding
to other norms and divergences, such as the KL-divergence. This paper shows in
general how the EVI operators relate to convex programs, and the form of their
dual, where strong duality is exhibited.
This paper then focuses on whether the bounds from finite horizon research of
Neu and Pike-Burke [21] can be applied to these extended value iteration
operators in the SSP setting. It shows that similar bounds to [21] for these
operators exist, however they lead to operators that are not in general
monotone and have more complex convergence properties. In a special case we
observe oscillating behaviour. This paper generates open questions on how
research may progress, with several examples that require further examination.

本文从凸优化的角度研究了已知和未知环境中的随机最短路径问题，回顾了已知参数情况下的结果，并通过不同的证明发展了理解。其后专注于未知参数情况，在此基础上研究了扩展值迭代算子，包括现有算子和定义了其他算子。本文表明了 EVI 算子与凸规划的关系及其对偶形式，同时提出了一些进一步研究的问题。