PaperlayerView exact revision on arXiv

Source-linked AI summary

The Deceptive Bandit Problem: Exploratory Coupling and the Fragility of Multi-Agent Learning

Michael Tang, Mahmoud Abdelgalil, Jorge I. Poveda

arXiv:2610.09120v1cs.LGcs.SYeess.SY

TL;DR

Bandit learning often assumes independent, private exploration, but adversaries may obtain correlated information about another agent’s exploration. The paper models how a deceiver can use such information to bias learning in a two-player strongly monotone game. The resulting dynamics converge near a deceptive Nash equilibrium while retaining the deception-free algorithm’s convergence complexity.

  • Problem

    Bandit-feedback convergence relies on independent, private exploration, an assumption that can be fragile when an adversary intercepts or infers another agent’s exploratory behavior.

    Source: §I · p. 1

  • Method

    The paper models a deceiver who couples its own exploration to a noisy signal correlated with the victim’s exploration, inducing an externality in the victim’s gradient estimate.

    Source: §I · p. 1, §IV · p. 3, B. Bandit Feedback Algorithm with… · p. 3

  • Results

    The DBL dynamics converge to an O(δ) RMS neighborhood of the DNE while retaining the deception-free algorithm’s O(d^2/ε^2) complexity.

    Source: A. Convergence Analysis · p. 4, §VIII · p. 7

  • Takeaways & Limitations

    Geometric conditions guarantee that deception shifts the steady state and improves the deceiver’s long-term cost or payoff.

    Source: §VIII · p. 7

    The main analysis considers the minimal two-player strongly monotone setting, while discussing extensions to N-player settings.

    Source: §I · p. 1, §III · p. 2

Abstract

from arXiv · show

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.

I. INTRODUCTION

Bandit learning uses randomized exploration, but its convergence guarantees assume agents’ exploratory policies are independent and private, assumptions vulnerable in adversarial settings. The paper studies how correlated exploration information can alter learning in a two-player strongly monotone game.

I. INTRODUCTION

  • Independent, private exploration underpins bandit-feedback convergence, but an adversary may intercept or infer another agent’s exploratory actions.Bandit feedback consists of cost or payoff measurements used to update policies.Source: §I · p. 1
  • Correlated exploration information can create a persistent bias that changes learning’s long-term outcome.The deceptive player modifies only its own exploration, inducing an externality in the other player’s gradient estimate.Source: §I · p. 1
  • Unlike utility poisoning and adversarial policies, this deceiver manipulates learning through its own feasible exploration; mere noisy, intermittent correlation can suffice.The paper identifies conditional cross-covariance between leakage and exploration as governing the induced bias.Source: §I · p. 1

II. PRELIMINARIES

  • The preliminaries define norm, ball, and projection notation used to describe the game and feasible actions.They specify operator and Euclidean norms, unit balls, and projection onto closed convex sets.Source: §II · p. 2

III. PROBLEM SETUP

  • The analysis focuses on two players minimizing costs over compact convex action sets, with a strongly monotone game pseudogradient and a unique Nash equilibrium.The stated conditions require continuously differentiable costs with Lipschitz gradients and impose first-order smoothness.Source: §III · p. 2

A. Standard Bandit Feedback Algorithm

The standard algorithm estimates gradients from sampled exploratory directions and observed costs. The paper then considers a deceiver who receives information about the victim’s exploration, including noisy, transformed, or intermittent signals.

A. Standard Bandit Feedback Algorithm

  • Each player samples a random direction, takes an exploratory action within search radius δ, observes the resulting cost, and updates its action using a single-point gradient estimate.Projection keeps the next iterate feasible, including when action spaces do not contain the origin.Source: A. Standard Bandit Feedback Algorithm · p. 2

IV. BANDIT FEEDBACK WITH DECEPTION

  • In the deception setting, player 2 intercepts or infers privileged information about player 1’s search policy and, by using it only in its own actions, can manipulate the gradient estimate player 1 uses to learn.Source: §IV · p. 3

A. Information Asymmetry

  • The intercepted signal is modeled as a transformed, noisy observation whose conditional mean transformation is fixed and whose transformation and noise are bounded.The signal may be a noisy measurement of the played action, and missed or late interceptions attenuate mean dither-signal cross-covariance by ρ.Source: A. Information Asymmetry · p. 3
  • The signal represents player 2’s imperfect measurement of player 1’s exploration and may arrive intermittently.The model covers channel leaks, noisy sensing, and intermittent measurements.Source: A. Information Asymmetry · p. 3

B. Bandit Feedback Algorithm with Deception

The section modifies bandit learning by letting the deceptive player couple its exploration to a leaked signal, changing the oblivious player's gradient estimate. The resulting externality defines a shifted steady state when the modified game remains strongly monotone.

B. Bandit Feedback Algorithm with Deception

  • The deceptive player’s exploratory action is constrained to remain feasible even in the worst-case realization of the leaked signal and noise.The exploration radius is adjusted to δc = δ(1 + |c|(Λ̄ + w̄)), with δc < r2.Source: B. Bandit Feedback Algorithm with… · p. 3
  • Coupling the deceptive player’s exploration to the leaked signal adds the externality cΓ⊤∇2J1(xk) to the oblivious player’s gradient estimate.The deceptive player still learns its own gradient up to an O(δ) smoothing bias; the externality does not vanish with δ.Source: B. Bandit Feedback Algorithm with… · p. 3
  • The leaked signal’s fixed cross-covariance produces the same deceptive bias at every iteration, even when its conditional distribution adapts to pre-round history.If the cross-covariance is zero, the signal cannot generate this equilibrium-shifting bias; the authors mention desynchronization and a randomized zero-mean mask as possible defenses.Source: B. Bandit Feedback Algorithm with… · p. 4
  • If the modified pseudogradient remains strongly monotone, condition (13), the game has a unique Nash equilibrium, which is called the deceptive Nash equilibrium (DNE).Source: B. Bandit Feedback Algorithm with… · p. 4

V. MAIN RESULTS

The results establish convergence guarantees for deceptive bandit learning and characterize how deception affects the steady state and the deceiver’s cost. Under the stated conditions, the dynamics approach a neighborhood of the deceptive Nash equilibrium with the deception-free algorithm’s complexity guarantee.

V. MAIN RESULTS

  • The paper’s main results characterize when deception shifts the steady state and how that shift affects the deceiver’s cost.The supplied results state these as part of the analysis, alongside the convergence guarantees.Source: §V · p. 4

A. Convergence Analysis

  • DBL iterates converge to a neighborhood of the DNE with the same O(d^2/ε^2) complexity as the deception-free bandit algorithm.The theorem’s conditions include Assumptions 1–3 and condition (13); the stated rate applies when the step sizes satisfy the specified schedule.Source: A. Convergence Analysis · p. 4
  • The analysis obtains these rates while relaxing the Lipschitz-Jacobian assumption used in, and the same relaxation also applies when c = 0.The proof treats the smoothing bias in the expected gradient as a bounded additive perturbation.Source: A. Convergence Analysis · p. 4
  • Larger |c| permits greater equilibrium displacement and potential long-term expected cost improvement, but reduces monotonicity and increases smoothing-bias bounds.It also contracts player 2’s feasible set, so selecting c creates a design trade-off for the deceiver.Source: A. Convergence Analysis · p. 4

B. Characterization of the DNE and Immunity Conditions

The section identifies when deception shifts the nominal Nash equilibrium and distinguishes leakage-channel immunity from immunity specific to the nominal equilibrium.

B. Characterization of the DNE and Immunity Conditions

C. Impact of Deception

The section examines when deception benefits the deceiver. It links profitable shifts to cross-player effects and notes that the resulting cost improvements can carry over to learning trajectories.

C. Impact of Deception

  • Condition (19) requires both a nonzero Γ⊤∇2J1(x∗) and a nonzero cross derivative ∇1J2 at the nominal equilibrium for an adversarially favorable shift.The first term enables a shift; the second reflects whether the deceiver’s cost responds to the victim’s action.Source: C. Impact of Deception · p. 5
  • When the deceiver’s cost is insensitive to the victim’s actions at the nominal equilibrium, shifting the victim’s steady-state behavior yields no immediate benefit.Source: C. Impact of Deception · p. 5
  • Theorem 1’s cost improvements are realized in long-term expected DBL trajectories when δ is sufficiently small.Source: C. Impact of Deception · p. 5

VI. PROOFS OF MAIN RESULTS

The proof excerpts use stochastic-approximation and projection bounds, and Fig. 2 presents a Monte Carlo study of convergence and cost effects.

VI. PROOFS OF MAIN RESULTS

  • The proof bounds the one-step distance using projection nonexpansiveness and controls the remaining term with an Appendix lemma.Source: A. Proof of Theorem 1 · p. 5
  • A stochastic-approximation comparison and Appendix lemmas are used to establish (17).Source: A. Proof of Theorem 1 · pp. 5–6
  • Fig. 2 reports 300-realization trajectories for convergence near the DNE, nominal and deceptive costs, and steady-state cost change and equilibrium displacement versus c.Source: Figure 2 · p. 6

B. Proof of Theorem 2

The proof establishes local injectivity by contradiction and shows invariance when the externality vanishes at the nominal equilibrium.

B. Proof of Theorem 2

  • For interior x∗, the proof defines g(c) = x∗_c and selects a neighborhood of zero where g(c) remains interior and solves the deceptive equilibrium condition.Source: B. Proof of Theorem 2 · p. 6
  • Assuming two distinct c values share an equilibrium yields Γ⊤∇2J1(ˆx) = 0, contradicting the nonzero externality condition and establishing injectivity.Source: B. Proof of Theorem 2 · p. 6
  • When Γ⊤∇2J1(x∗) = 0, the nominal and deceptive mappings agree at x∗; strong monotonicity then gives equilibrium invariance.Source: B. Proof of Theorem 2 · p. 6

C. Proof of Theorem 3

The proof of Theorem 3 uses a one-sided perturbation argument, while the resource-allocation example shows that correlated exploration can improve the deceiver’s steady-state cost and that countermeasures restore nominal learning trajectories. The conclusion gives an O(δ) RMS convergence guarantee under weaker regularity conditions.

C. Proof of Theorem 3

  • The proof selects a one-sided interval E around zero according to the sign of the derivative at c=0.When the derivative is positive, E is a negative interval; otherwise, it is positive.Source: C. Proof of Theorem 3 · p. 6

VII. NUMERICAL EXAMPLE

  • In the numerical setup, player 2 receives noisy measurements of player 1’s exploration signal with probability 0.75 and uses deception parameter c=0.8.Both players use δ=0.25 and step sizes η_k=3k^-1.Source: §VII · p. 6
  • Countermeasures that suppress same-round dither-signal correlation recover nominal learning trajectories and converge near the Nash equilibrium, while undefended dynamics remain displaced.The example considers an induced dither-signal delay, zero-mean masking, and dither resetting.Source: §VII · p. 6, Figure 3 · p. 7
  • In this example, at c ≈ 1.15, player 2 improves their steady-state cost through deception; trajectories averaged over 300 realizations show how c affects steady-state costs and equilibrium shift.The example falls outside the class of second-order smoothness conditions required in.Source: §VII · p. 6

VIII. CONCLUSION

  • The conclusion states that DBL converges to an O(δ) RMS neighborhood of the deceptive Nash equilibrium under weaker regularity conditions than.It also identifies geometric conditions for a steady-state shift and improved long-term cost or payoff, and notes that the regularity relaxation applies without deception.Source: §VIII · p. 7

IX. APPENDIX

The appendix collects technical lemmas used to prove the main results. Its arguments include almost-sure estimates, expectation calculations, transformed-set bounds, and a scalar-sequence bound.

IX. APPENDIX

  • The appendix introduces technical lemmas used to prove the paper’s main results.Source: §IX · p. 8
  • A transformed feasible set and map are used to establish strong monotonicity and bound the residual using a Lipschitz constant L_c for G_dec.Source: §IX · p. 8
  • Lemma 2 gives estimates for each k that hold almost surely.Source: §IX · p. 8
  • The calculation applies Stokes’ theorem and uses E_k[Λ]=Γ to continue from equation (11).Source: §IX · p. 8
  • A scalar-sequence lemma gives an all-k bound on V_k under q>1 and positive constants A and B.Source: §IX · p. 8
Loading 2610.09120v1…