Cooperative Multi-Agent Reinforcement Learning with Partial Observations

Yan Zhang, Michael M. ZavlanosarXiv 2020 · OpenReview

TL;DR

This paper introduces a novel distributed reinforcement learning method for cooperative multi-agent systems where agents only have partial information about the global state. Their approach uses a "zeroth-order" policy optimization technique that significantly reduces communication overhead and improves learning efficiency compared to existing methods.

What Problem Does This Paper Address?

In many real-world scenarios, like coordinating a fleet of drones or managing a smart grid, multiple agents need to collaborate to achieve a common goal. Traditional Multi-Agent Reinforcement Learning (MARL) algorithms often assume that each agent can see everything – the states and actions of all other agents. This is a huge communication burden, especially in large systems, and can even be a privacy concern. The challenge is to enable effective cooperation when agents can only observe a limited part of the overall situation. This partial observability makes the learning environment appear "non-stationary" to each agent, as the actions of others are constantly changing and not fully known.

Methods

The core contribution is a distributed zeroth-order policy optimization method. Instead of requiring agents to compute exact gradients (which depend on full state information), this method uses "zeroth-order" estimators. These estimators approximate gradients by simply evaluating the objective function at slightly perturbed points, requiring less information.

Key innovations include:

  • Distributed Zeroth-Order Policy Gradient Estimator: They adapt a one-point residual-feedback estimator to the multi-agent, partial-observation setting. This estimator uses historical information to reduce the variance of gradient estimates, leading to faster and more stable learning.
  • Consensus Mechanism: Agents use a consensus protocol to locally estimate the global accumulated reward, which is crucial for the gradient estimation. This allows them to approximate global information without direct communication of states.
  • Value Tracking: To further reduce bias introduced by the consensus mechanism (especially with limited consensus steps), they incorporate a value tracking technique. This uses past estimates to improve the current global reward estimation.

The algorithm is designed to be fully decentralized, meaning each agent only needs to communicate with its neighbors.

Datasets

Not discussed in the paper. The experiments use a simulated stochastic multi-agent multi-stage decision-making problem based on a 4x4 grid scenario where agents manage resources and demands.

Key Insights and Ideas

  • Partial Observability is a Major Hurdle: The paper highlights that standard MARL methods fail under partial observability due to the non-stationary nature of the learning environment.
  • Zeroth-Order Methods are Promising for Decentralization: By avoiding exact gradients, zeroth-order methods offer a path to scalable, decentralized MARL.
  • Variance Reduction is Key: The proposed residual-feedback estimator significantly reduces the variance of policy gradient estimates, leading to more efficient learning than simpler one-point estimators.
  • Consensus is Necessary but Introduces Bias: While consensus helps agents approximate global information, it's imperfect. The value tracking mechanism is a clever way to mitigate this bias.
  • Communication Topology Matters: The effectiveness of the consensus mechanism (and thus the overall algorithm) is influenced by the communication graph structure.

Key Results

  • Improved Sample Efficiency: Numerical experiments show that the proposed residual-feedback estimator is more sample-efficient than existing one-point estimators, both with and without value tracking.
  • Faster Learning: The algorithm with the residual-feedback estimator converges faster and achieves better policies compared to using a standard one-point estimator.
  • Value Tracking Benefits: Value tracking further improves performance, especially when the communication graph doesn't perfectly align with agent interactions, by providing a more accurate global reward estimate.
  • Convergence Guarantees: The paper provides theoretical convergence guarantees, showing that the algorithm converges to a neighborhood of the optimal policy, with the size of this neighborhood depending on parameters like learning rates and consensus steps.

Limitations and Future Work

  • Theoretical Assumptions: The convergence analysis relies on assumptions like the Lipschitz continuity of the smoothed value function, which might be restrictive for certain policy classes.
  • Parameter Tuning: The performance and convergence depend on careful selection of parameters like the exploration step size ($\delta$) and learning rate ($\alpha$), as well as the number of consensus steps ($N_c$).
  • Fixed Communication Graph: The current analysis assumes a fixed communication graph. Extending this to time-varying graphs would be a valuable future direction.
  • Scalability of Consensus: While decentralized, the consensus mechanism's efficiency can still be a bottleneck in extremely large-scale systems.
  • Comparison to Newer Methods: The paper mentions a newer one-point estimator proposed after their submission, which is centralized. Future work could explore integrating their techniques with more advanced decentralized estimators.

Summary updated

Abstract

In this paper, we propose a distributed zeroth-order policy optimization method for Multi-Agent Reinforcement Learning (MARL). Existing MARL algorithms often assume that every agent can observe the states and actions of all the other agents in the network. This can be impractical in large-scale problems, where sharing the state and action information with multi-hop neighbors may incur significant communication overhead. The advantage of the proposed zeroth-order policy optimization method is that it allows the agents to compute the local policy gradients needed to update their local policy functions using local estimates of the global accumulated rewards that depend on partial state and action information only and can be obtained using consensus. Specifically, to calculate the local policy gradients, we develop a new distributed zeroth-order policy gradient estimator that relies on one-point residual-feedback which, compared to existing zeroth-order estimators that also rely on one-point feedback, significantly reduces the variance of the policy gradient estimates improving, in this way, the learning performance. We show that the proposed distributed zeroth-order policy optimization method with constant stepsize converges to the neighborhood of a policy that is a stationary point of the global objective function. The size of this neighborhood depends on the agents' learning rates, the exploration parameters, and the number of consensus steps used to calculate the local estimates of the global accumulated rewards. Moreover, we provide numerical experiments that demonstrate that our new zeroth-order policy gradient estimator is more sample-efficient compared to other existing one-point estimators.
BibTeX
@misc{zhang2020cooperative,
  author = {Yan Zhang and Michael M. Zavlanos},
  title = {{Cooperative Multi-Agent Reinforcement Learning with Partial Observations}},
  year = {2020},
  eprint = {2006.10822},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.10822},
}
Figure