🔢 mathematics

Cost-Aware Distributed Online Learning with Strict Rejection Behavior against Adversarial Agents

This paper proposes a cost-aware distributed online learning framework that employs strict rejection behavior and an adaptive state-evolution rate adjustment mechanism to achieve robust, low-cost convergence against adversarial agents in multi-agent systems.

Original authors: Yuhan Suo, Senchun Chai, Xudong Zhao, Yuanqing Xia, and Runqi Chai

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuhan Suo, Senchun Chai, Xudong Zhao, Yuanqing Xia, and Runqi Chai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to decide where to go for dinner. They are all in a chat group, sharing their preferences, and trying to agree on a single restaurant. This is a Multi-Agent System.

Now, imagine that one or two people in the group are "trolls." They aren't just suggesting bad restaurants; they are shouting out fake locations, lying about the food quality, and trying to drag the whole group toward a place that doesn't exist or is terrible.

This paper is about how the honest friends can still figure out the best restaurant without immediately kicking the trolls out of the group (which might be impossible if the trolls are hiding their identities or if the group needs everyone to keep the chat active).

Here is the breakdown of the paper's solution using simple analogies:

1. The Problem: The "Boomerang" Effect

Usually, when a group tries to agree, they average out everyone's opinions. If a troll says, "Let's go to the North Pole!" and the others say, "Let's go to the park," the average might be a snowy field. The group gets confused and wastes time correcting their path.

The authors realized that in the messy middle stage—before you are 100% sure who the troll is—just trying to "average" the information is dangerous. It causes the group to swing wildly back and forth, wasting a lot of energy (cost) and time.

2. The Solution: "Strict Rejection" (The Bouncer)

Instead of trying to calculate a perfect average that includes the troll's crazy suggestion, the paper proposes a "Strict Rejection" rule.

Think of the honest friends as having a bouncer at the door of their decision-making process.

Old Way: "Okay, the troll says North Pole. Let's take 50% of that and 50% of the Park. We'll go to the Snowy Field." (Result: Confusion and wasted energy).
New Way: "Whoa, that suggestion is way too far from what we expect. It's suspicious. We are going to reject that specific input entirely and not let it pull us off course."

This is the "Strict Rejection Behavior." It's like saying, "I see you shouting, but I'm not listening to that specific noise right now."

3. The Smart Twist: "Cost-Aware" Learning (The Budget Manager)

Here is the tricky part. If you reject everything too aggressively, you might accidentally ignore a real friend who is just having a bad day. If you reject nothing, the trolls win.

The paper introduces a "Cost-Aware" system. Imagine the group has a limited budget of "energy" or "patience."

Early Stage (High Cost): When the group first notices the trolls, they are confused. The system says, "Okay, let's slow down. Don't rush to make a decision. We will move very carefully to avoid wasting energy on the trolls' lies."
Later Stage (Low Cost): Once the group has figured out who the trolls are (or at least isolated their influence), the system says, "Great, we know the danger. Now let's speed up and finish the decision quickly."

The paper creates a mathematical "schedule" (like a traffic light system) that tells the agents: "Right now, move slowly to save energy. Later, you can move fast."

4. The Two-Layer System (The Captain and the Crew)

The authors designed a two-layer system to make this work:

The Inner Layer (The Crew): These are the agents actually doing the work (moving, sensing, talking). They follow a fixed rhythm for a while.
The Outer Layer (The Captain): This is the smart brain that watches the whole situation. Every few minutes, the Captain checks: "Are the trolls causing too much chaos? Are we wasting too much energy?"
- If yes, the Captain adjusts the "speed limit" (the evolution rate) for the crew.
- If no, the Captain lets them speed up.

The Captain doesn't change the crew's path directly; it just changes how fast they are allowed to react. This prevents the system from getting "jittery" and wasting energy.

5. The Real-World Test: The Satellite Team

To prove this works, the authors simulated a team of satellites trying to catch a target (like a piece of space debris).

The Scenario: One satellite is "hacked" and lies about where the debris is, trying to make the team miss or crash.
The Result:
- Without the new method: The team gets confused by the lie, swings wildly, and almost crashes into the debris because they reacted too late.
- With the new method: The team spots the lie, "rejects" the bad data, slows down their reaction to be safe, and then smoothly adjusts their course to catch the debris perfectly.

Summary

This paper teaches us that in a world full of liars and hackers, being stubborn is sometimes better than being flexible.

Instead of trying to mathematically average out the lies (which is expensive and slow), the best strategy is to strictly reject the obvious nonsense immediately. But to do this safely, you need a smart manager that knows when to be slow and careful (to save energy) and when to speed up and finish the job.

It's like driving a car in a foggy storm: You don't try to guess the exact path of every pothole (that's too costly); you just refuse to drive off the road (strict rejection) and you drive slowly until the fog clears, then you speed up.

1. Problem Statement

The paper addresses the challenge of distributed online learning in Multi-Agent Systems (MAS) under adversarial influence.

Context: In open, dynamic networks (e.g., sensor networks, satellite swarms), agents must cooperatively update their states based on streaming local information.
The Threat: Malicious agents can inject false information or strategically manipulate states. While existing research focuses on resilient consensus (achieving agreement despite attacks) or secure fusion (filtering bad data), they often overlook the inefficiency and excessive cost incurred during the defense process.
The Gap: In real-world scenarios, malicious agents cannot be instantly isolated; there is a transient phase where normal agents must react to manipulated information. This leads to:
- State overshoot and repeated corrections.
- Amplified state evolution costs (the energy or effort required to adapt).
- Inefficiency in reaching the optimal state.
Core Question: How to design a mechanism that adaptively regulates the state evolution rate to maintain robustness against malicious inputs while minimizing unnecessary long-term costs, without relying on immediate, perfect isolation of attackers.

2. Methodology

The authors propose a Cost-Aware Distributed Online Learning Framework featuring Strict Rejection Behavior and a Two-Time-Scale Adaptive Update Mechanism.

A. Strict Rejection Behavior (The "Boomerang Effect")

Instead of standard consensus (averaging neighbors), the paper introduces an adversarial fusion rule inspired by the "Boomerang Effect."

Mechanism: If the state gap between an agent and a neighbor exceeds a threshold ( $\varepsilon$ ), the fusion rule applies a repulsive term rather than an attractive one.
Function: This prevents normal agents from assimilating extreme or malicious information. If a neighbor's state is too far off, the agent actively pushes its own state away from that neighbor, effectively "rejecting" the malicious influence.
Cost Characterization: The paper theoretically proves that while this rejection ensures safety, it can amplify state evolution costs if not managed, as agents may over-correct.

B. Adaptive Evolution-Rate Adjustment (Two-Time-Scale Framework)

To balance robustness (rejection) and cost efficiency, the authors decouple the learning process into two time scales:

Fast Time Scale (Inner Loop): Agents evolve their states within a fixed period using a periodic schedule. The dynamics are governed by a Periodic Discrete-Time Algebraic Riccati Equation (PDARE).
Slow Time Scale (Outer Loop): The evolution rate ( $\gamma$ $γ$ ) is adjusted periodically (every $T$ $T$ steps) based on an online optimization problem.
- Objective: The outer layer solves a constrained optimization problem to select an evolution rate schedule ( $\gamma^s$ $γ^{s}$ ) that balances:
  - Tracking a reference target (based on warning signals or risk indicators).
  - Maintaining temporal consistency (inertia) to avoid abrupt changes.
  - Adhering to admissibility constraints (ensuring system stability).
- Formulation: The update is formulated as a Euclidean quadratic projection onto a time-varying admissible set, regularized by a trust-region constraint.

C. Theoretical Analysis

Well-Posedness: The authors prove that the adaptive schedule remains within a compact set where the PDARE admits a unique, stabilizing, positive-definite solution.
Regularity: They establish that the Riccati solution and feedback gains are Lipschitz continuous with respect to the evolution rate, ensuring smooth transitions.
Stability: Using a Two-Time-Scale Lyapunov framework, they prove practical stability of the closed-loop system. The system is shown to converge to a bounded neighborhood of the optimal state, with the bound determined by the magnitude of malicious disturbances and the drift of the reference target.

3. Key Contributions

Cost-Aware Framework: Unlike traditional methods focusing solely on convergence, this paper explicitly models and minimizes the state evolution cost induced by adversarial interactions.
Strict Rejection Mechanism: Introduces a "Boomerang" fusion rule that mathematically encodes the behavior of strictly rejecting extreme/malicious inputs, preventing their assimilation.
Adaptive Rate Control: Proposes a novel two-time-scale adaptive mechanism that dynamically tunes the learning speed. This allows the system to be aggressive (fast convergence) when safe and conservative (slow, low-cost adaptation) when under attack.
Rigorous Stability Guarantees: Provides a comprehensive theoretical proof of the system's well-posedness, regularity, and practical stability under adversarial disturbances.

4. Results

The paper validates the approach through extensive simulations and a specific application scenario.

A. Numerical Simulations (10-Agent Network)

Scenario: 4 normal agents and 6 malicious agents.
Findings:
- Without the proposed method: Normal agents fail to converge, and state evolution costs rise indefinitely.
- With Trust-Based Methods (Baseline): Agents converge slowly, but costs remain high due to conservative fusion.
- With Proposed Method: The system achieves a robust and low-cost convergence. The adaptive mechanism reduces early-stage costs by slowing down evolution during the attack, then accelerates once malicious links are effectively isolated.
- Metrics: The proposed method showed a wider "best interval" for balancing cost vs. convergence steps compared to fixed-rate or pure trust-based methods, indicating superior flexibility.

B. Application: Multi-Satellite Target Tracking

Scenario: A Type-A satellite (capturer) fuses data from 4 Type-B satellites (sensors), one of which is compromised and injects bias to delay the capture decision.
Outcome:
- Normal Fusion: The central satellite is misled, delaying the capture decision until it is dangerously close to the target (increasing collision risk).
- Strict Rejection: The central satellite detects the anomaly, rejects the biased data, and makes the capture decision earlier (at a safer distance), significantly improving mission safety and success rates.

5. Significance

Paradigm Shift: Moves the focus from "achieving consensus despite attacks" to "achieving consensus efficiently despite attacks." It acknowledges that defense has a cost and optimizes for it.
Practical Relevance: The "Strict Rejection" behavior is highly applicable to real-world systems like social networks (rejecting hate speech/extremism), financial systems (filtering fraud), and cyber-physical systems (satellite/UAV swarms) where immediate isolation is impossible.
Theoretical Advancement: The integration of PDARE-based control with online optimization for rate adaptation provides a new theoretical toolset for designing resilient, cost-effective distributed learning systems.

In summary, this paper presents a sophisticated control-theoretic approach to distributed learning that not only defends against malicious agents but does so in a way that is economical, ensuring the system does not waste resources fighting an attack it cannot immediately eliminate.