The Deceptive Bandit Problem: Exploratory Coupling and the Fragility of Multi-Agent Learning
Authors: Michael Tang, Mahmoud Abdelgalil, Jorge I. Poveda
Organizations: Electrical and Computer Engineering Department at the University of California, San Diego, La Jolla, CA, USA · Mechanical and Aerospace Engineering Department at the University at Buffalo, State University of New York, Buffalo, NY, USA
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.
Figures & tables
Fig. 1: Exploration leakage and coupling in a two-player game with bandit feedback.
Fig. 2: Monte Carlo study over M=300 realizations. Left: convergence to a neighborhood of the DNE. Middle: nominal and deceptive cost trajectories. Right: the deceptive player’s steady-state cost change as a function of c , and the equilibrium displacement.
Fig. 3: Convergence of the action profile with deception countermeasures implemented at each stage. One-step delay: player 2 uses Θ1,k−1 during stage k . Zero-mean mask: player 1 privately flips the sign of the dither with probability 21 after leakage. Dither refresh: player 1 resamples the dither after leakage.