On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks

• URL: http://arxiv.org/abs/2409.12882v2
• Date: Sun, 22 Sep 2024 03:11:54 GMT
• Title: On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks
• Authors: Hairi, Minghong Fang, Zifan Zhang, Alvaro Velasquez, Jia Liu,
• Abstract summary: We study a fully-decentralized multi-agent policy evaluation problem in the presence of up to $f$ faulty agents. In particular, we focus on the so-called Byzantine faulty model with model poisoning setting.
• Score: 12.696705862929337
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study a fully-decentralized multi-agent policy evaluation problem, which is an important sub-problem in cooperative multi-agent reinforcement learning, in the presence of up to $f$ faulty agents. In particular, we focus on the so-called Byzantine faulty model with model poisoning setting. In general, policy evaluation is to evaluate the value function of any given policy. In cooperative multi-agent system, the system-wide rewards are usually modeled as the uniform average of rewards from all agents. We investigate the multi-agent policy evaluation problem in the presence of Byzantine agents, particularly in the setting of heterogeneous local rewards. Ideally, the goal of the agents is to evaluate the accumulated system-wide rewards, which are uniform average of rewards of the normal agents for a given policy. It means that all agents agree upon common values (the consensus part) and furthermore, the consensus values are the value functions (the convergence part). However, we prove that this goal is not achievable. Instead, we consider a relaxed version of the problem, where the goal of the agents is to evaluate accumulated system-wide reward, which is an appropriately weighted average reward of the normal agents. We further prove that there is no correct algorithm that can guarantee that the total number of positive weights exceeds $|\mathcal{N}|-f $, where $|\mathcal{N}|$ is the number of normal agents. Towards the end, we propose a Byzantine-tolerant decentralized temporal difference algorithm that can guarantee asymptotic consensus under scalar function approximation. We then empirically test the effective of the proposed algorithm.

Related papers

• Multi-Agent Stochastic Bandits Robust to Adversarial Corruptions [6.234292942334148]
  We propose a multi-agent cooperative learning algorithm that is robust to adversarial corruptions. As a side-product, our algorithm also improves the state-of-the-art regret bounds when reducing to both the single-agent and homogeneous multi-agent scenarios.
  arXiv  Detail & Related papers  (2024-11-12T20:20:26Z)
• Towards Fast Rates for Federated and Multi-Task Reinforcement Learning [34.34798425737858]
  We propose Fast-FedPG, a novel federated policy algorithm with a carefully designed bias-correction mechanism. Under a gradient-domination condition, we prove that our algorithm guarantees (i) fast linear convergence with exact gradients, and (ii) sub-linear rates that enjoy a linear speedup w.r.t. the number of agents with noisy, truncated policy gradients.
  arXiv  Detail & Related papers  (2024-09-09T02:59:17Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  Multi-armed bandits are a sequential-decision-making framework, where, at each interaction step, the learner selects an arm and observes a reward. We consider the scenario in which the learner has access to a set of mediators, each of which selects the arms on the agent's behalf according to a and possibly unknown policy. We propose a sequential decision-making strategy for discovering the best arm under the assumption that the mediators' policies are known to the learner.
  arXiv  Detail & Related papers  (2023-08-29T18:18:21Z)
• Estimating and Incentivizing Imperfect-Knowledge Agents with Hidden Rewards [4.742123770879715]
  In practice, incentive providers often cannot observe the reward realizations of incentivized agents. This paper explores a repeated adverse selection game between a self-interested learning agent and a learning principal. We introduce an estimator whose only input is the history of principal's incentives and agent's choices.
  arXiv  Detail & Related papers  (2023-08-13T08:12:01Z)
• Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning [139.53668999720605]
  We present a multi-agent PPO algorithm in which the local policy of each agent is updated similarly to vanilla PPO. We prove that with standard regularity conditions on the Markov game and problem-dependent quantities, our algorithm converges to the globally optimal policy at a sublinear rate.
  arXiv  Detail & Related papers  (2023-05-08T16:20:03Z)
• Resilient Consensus-based Multi-agent Reinforcement Learning [22.774403531759592]
  We consider a fully decentralized network, where each agent receives a local reward and observes global state and action. We show that in the presence of Byzantine agents, whose estimation and communication strategies are completely arbitrary, the estimates of the cooperative agents converge to a bounded consensus value with probability one. We prove that the policy of the cooperative agents converges with probability one to a bounded neighborhood around a local maximizer of their team-average objective function.
  arXiv  Detail & Related papers  (2021-11-12T15:38:01Z)
• Dealing with Non-Stationarity in Multi-Agent Reinforcement Learning via Trust Region Decomposition [52.06086375833474]
  Non-stationarity is one thorny issue in multi-agent reinforcement learning. We introduce a $delta$-stationarity measurement to explicitly model the stationarity of a policy sequence. We propose a trust region decomposition network based on message passing to estimate the joint policy divergence.
  arXiv  Detail & Related papers  (2021-02-21T14:46:50Z)
• Multi-agent Policy Optimization with Approximatively Synchronous Advantage Estimation [55.96893934962757]
  In multi-agent system, polices of different agents need to be evaluated jointly. In current methods, value functions or advantage functions use counter-factual joint actions which are evaluated asynchronously. In this work, we propose the approximatively synchronous advantage estimation.
  arXiv  Detail & Related papers  (2020-12-07T07:29:19Z)
• Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning [55.20040781688844]
  QMIX is a novel value-based method that can train decentralised policies in a centralised end-to-end fashion. We propose the StarCraft Multi-Agent Challenge (SMAC) as a new benchmark for deep multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-19T16:51:51Z)
• FACMAC: Factored Multi-Agent Centralised Policy Gradients [103.30380537282517]
  We propose FACtored Multi-Agent Centralised policy gradients (FACMAC) It is a new method for cooperative multi-agent reinforcement learning in both discrete and continuous action spaces. We evaluate FACMAC on variants of the multi-agent particle environments, a novel multi-agent MuJoCo benchmark, and a challenging set of StarCraft II micromanagement tasks.
  arXiv  Detail & Related papers  (2020-03-14T21:29:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.