Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation

Zhaoxian Wu, Han Shen, Tianyi Chen, Qing LingICASSP 2021 · OpenReview

TL;DR

This paper tackles the challenge of evaluating policies in multi-agent reinforcement learning (MARL) systems where some agents might be malicious (Byzantine). They introduce "Byrd-TD(λ)," a novel algorithm that uses a robust "trimmed mean" aggregation to filter out bad data from Byzantine agents, enabling accurate policy evaluation even in adversarial settings.

What Problem Does This Paper Address?

In multi-agent reinforcement learning (MARL), agents often need to learn and evaluate policies collaboratively. A common approach is decentralized Temporal Difference (TD) learning, where agents share information to estimate the value of a policy. However, this breaks down if some agents are "Byzantine" – meaning they can send arbitrary, malicious data. This can lead to inaccurate learning and prevent the system from understanding the true value of a policy. Existing methods for handling Byzantine agents often rely on a central coordinator, which isn't suitable for decentralized MARL. This paper addresses this gap by proposing a decentralized method that's robust to Byzantine behavior.

Methods

The core of the proposed solution is the Byzantine-resilient decentralized TD(λ) (Byrd-TD(λ)) algorithm. It builds upon the standard TD(λ) learning framework but introduces a crucial modification in how agents aggregate information from their neighbors. Instead of a simple average (mean), Byrd-TD(λ) uses a trimmed mean.

Here's how it works:

  1. Local Updates: Each agent performs its own TD(λ) update based on its local observations and rewards.
  2. Robust Aggregation (Trimmed Mean): When agents share their learned parameters (model updates), each honest agent receives parameters from its neighbors. Before averaging these parameters, the agent identifies and discards a certain number of the "outlier" values (the smallest and largest) on a per-coordinate basis. This is the "trimmed mean" step. The number of values to discard is determined by an estimate of the number of Byzantine agents.
  3. Consensus and Convergence: The algorithm is designed to achieve consensus among honest agents (they all converge to a similar estimate) and to converge to the true value function, even in the presence of Byzantine agents. The theoretical analysis provides finite-time convergence rates and asymptotic learning error bounds.

Datasets

Not discussed in the paper. The experiments use a simulated cooperative navigation task, which is a standard MARL benchmark.

Key Insights and Ideas

  • Trimmed Mean as a Shield: The trimmed mean aggregation is surprisingly effective at filtering out adversarial inputs from Byzantine agents without requiring a central authority. It's like having a robust voting system where extreme or suspicious votes are ignored.
  • Decentralized Robustness is Tricky: Analyzing decentralized learning with Byzantine agents is significantly harder than centralized versions. The errors from malicious agents can propagate through the network, and the updates don't always follow standard gradient descent, making theoretical analysis challenging.
  • Network Topology Matters: The convergence rate and accuracy are influenced by the network structure. Denser networks and those with fewer "bottlenecks" (where a few agents have many incoming connections) tend to lead to faster convergence and lower errors.
  • Parameter Tuning is Key: The parameter λ in TD(λ) plays a dual role. While it typically balances approximation accuracy and convergence speed, its impact becomes more complex in the presence of Byzantine agents. The paper suggests that higher reward heterogeneity or unsaturated networks might benefit from smaller λ values.

Key Results

  • Byzantine Resilience: The proposed Byrd-TD(λ) algorithm demonstrates significant robustness against Byzantine attacks, as shown in numerical experiments. While standard decentralized TD(λ) with mean aggregation fails under attacks, Byrd-TD(λ) with trimmed mean aggregation maintains performance.
  • Convergence Guarantees: The paper provides theoretical guarantees for both finite-time convergence and asymptotic learning error. The convergence rate is shown to be influenced by network topology and the number of Byzantine agents.
  • Empirical Validation: Experiments on a cooperative navigation task show that Byrd-TD(λ) can accurately learn linear value function estimates even when Byzantine agents are present and actively trying to disrupt the learning process (e.g., with sign-flipping attacks).

Limitations and Future Work

  • Estimating Byzantine Agents: The current algorithm assumes knowledge of the number of Byzantine agents (or at least an upper bound) to set the trimming parameter qn. A natural extension would be to adaptively estimate this bound.
  • Generalization to Non-Linear Approximations: The current work focuses on linear function approximation. Extending the Byzantine-resilient approach to non-linear function approximators (like neural networks) would be a significant advancement.
  • More Complex Attacks: While the paper tests various attacks (sign-flipping, same value, Gaussian noise), exploring resilience against more sophisticated, coordinated Byzantine attacks could be a future direction.

Summary updated

Abstract

This paper considers the policy evaluation problem in reinforcement learning with agents of a decentralized and directed network. The focus is on decentralized temporal-difference (TD) learning with linear function approximation in the presence of unreliable or even malicious agents, termed as Byzantine agents. In order to evaluate the quality of a fixed policy in a common environment, agents usually run decentralized TD(λ) collaboratively. However, when some Byzantine agents behave adversarially, decentralized TD(λ) is unable to learn an accurate linear approximation for the true value function. We propose a trimmed-mean based decentralized TD(λ) algorithm to perform policy evaluation in this setting. We establish the finite-time convergence rate, as well as the asymptotic learning error that depends on the number of Byzantine agents. Numerical experiments corroborate the robustness of the proposed algorithm.
BibTeX
@inproceedings{wu2021byzantine,
  author = {Zhaoxian Wu and Han Shen and Tianyi Chen and Qing Ling},
  title = {{Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=XBj7gVpbDLd},
}
Figure