Exploring how secret information tricks learning agents in games
The Deceptive Bandit Problem: Exploratory Coupling and the Fragility of Multi-Agent Learning
Machine Learning
Summary
When multiple computer programs learn by trying different actions randomly, this randomness is usually assumed to be private and independent. The authors show that if one program secretly learns about another’s random choices, it can cleverly change its own behavior to trick the other. This trickery leads the programs to settle into a new pattern that favors the deceiver. The researchers prove this happens reliably and quickly under certain conditions, highlighting a hidden risk in how these learning systems operate.
What this means in practice
- •For multi-agent system designers: Identify and mitigate vulnerabilities where agents could exploit knowledge about others’ exploration to manipulate outcomes in cooperative or competitive settings.
- •For security engineers: Develop safeguards against adversaries exploiting information leaks in adaptive algorithms controlling resource allocation or automated decision-making.
Authors
Michael Tang, Mahmoud Abdelgalil, Jorge I. Poveda
Abstract
Randomized exploration is central to bandit learning, multi-agent reinforcement learning, and zeroth-order policy search, yet its independence and privacy are usually only treated as technical assumptions. We show that these properties are critical for security purposes and demonstrate how an adversarial agent can exploit privileged information on another agent's exploration. We analyze a deceiver-victim pair in the minimal two-player strongly monotone setting, where a deceptive player obtains leaked signals that are merely correlated with the victim's exploration. We show that, by coupling their own exploratory action with this information, the deceptive player injects an externality that steers the learning dynamics to a new steady state, called the deceptive Nash equilibrium (DNE). We prove that the deceptive bandit learning (DBL) dynamics converge to an arbitrarily small neighborhood of the DNE while retaining optimal convergence rates. Interestingly, our analysis attains these optimal rates while relaxing second-order smoothness conditions from standard bandit optimization literature. We characterize conditions under which deception strictly shifts the steady state and its effect on the deceiver's cost, illustrating the results in a resource-allocation game.