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

# The Deceptive Bandit Problem:Exploratory Coupling and the Fragility of Multi-Agent Learning
Source: [https://arxiv.org/html/2610.09120](https://arxiv.org/html/2610.09120)
Mahmoud AbdelgalilJorge I\. Poveda††thanks:M\. Tang and J\. I\. Poveda are with the Electrical and Computer Engineering Department at the University of California, San Diego, La Jolla, CA, USA\. M\. Abdelgalil is with the Mechanical and Aerospace Engineering Department at the University at Buffalo, State University of New York, Buffalo, NY, USA\.††thanks:This work was supported in part by NSF grants DGE\-2545911, CMMI 2228791, and the DARPA grant HR0011\-25\-3\-0225\.

###### 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 relaxingsecond\-order smoothnessconditions 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 aresource\-allocation game\.

## IIntroduction

Multi\-agent learning has attracted significant attention in recent years with applications spanning many domains\. In many of these applications, agents do not have access to gradient information and must instead rely solely on*bandit feedback*\[[1](https://arxiv.org/html/2610.09120#bib.bib1)\], i\.e\., measurements of their cost/payoff functions, to update their policies\. This has motivated a rich body of literature on*multi\-agent bandit learning*, where agents simultaneously explore their action spaces and exploit observed costs/payoffs to find optimal policies\. Example applications include resource allocation\[[2](https://arxiv.org/html/2610.09120#bib.bib2)\], distributed and networked systems\[[3](https://arxiv.org/html/2610.09120#bib.bib3),[4](https://arxiv.org/html/2610.09120#bib.bib4),[5](https://arxiv.org/html/2610.09120#bib.bib5)\], robotics\[[6](https://arxiv.org/html/2610.09120#bib.bib6)\], and financial decision\-making\[[7](https://arxiv.org/html/2610.09120#bib.bib7),[8](https://arxiv.org/html/2610.09120#bib.bib8)\]\. More broadly, randomized exploration is a basic ingredient of many learning methods, including stochastic approximation\[[9](https://arxiv.org/html/2610.09120#bib.bib9)\], multi\-agent reinforcement learning\[[10](https://arxiv.org/html/2610.09120#bib.bib10)\], and zeroth\-order policy search\[[11](https://arxiv.org/html/2610.09120#bib.bib11)\]\. If agents learn through bandit feedback, the convergence to the Nash equilibrium \(NE\)\[[12](https://arxiv.org/html/2610.09120#bib.bib12),[13](https://arxiv.org/html/2610.09120#bib.bib13),[14](https://arxiv.org/html/2610.09120#bib.bib14)\]relies on the assumption that the exploratory policies used by different agents are*independent*and*private*\. However, in an open, networked, or competitive environment, such an assumption is fragile; an adversarial agent can*intercept*or*infer*privileged information about the exploratory actions of other agents\[[15](https://arxiv.org/html/2610.09120#bib.bib15),[16](https://arxiv.org/html/2610.09120#bib.bib16),[17](https://arxiv.org/html/2610.09120#bib.bib17)\]\.

*Contributions:*We expose a security vulnerability in exploration\-driven multi\-agent learning: information correlated with an agent’s exploratory behavior can be amplified into a persistent bias that changes the long\-term outcome of learning\. To isolate the core mechanism, we formalize it in two\-player strongly monotone games, where a deceptive player modifies only its own exploration using a noisy signal correlated with the oblivious player’s current dither; extensions toNN\-player settings are also discussed\. This unilateral coupling induces an externality in the oblivious player’s gradient estimate, scaled by the dither\-signal correlation term\. We prove that the resulting*deceptive bandit learning*\(DBL\) dynamics converge to a small neighborhood of a new steady state, a*deceptive*Nash equilibrium \(DNE\), with non\-asymptotic mean\-square guarantees\. Our analysis attains the optimal convergence rates from\[[18](https://arxiv.org/html/2610.09120#bib.bib18)\]while relaxing theirsecond\-order smoothnessconditions on the players’ costs; to our knowledge, this relaxation is also novel in the deception\-free setting\. We characterize when deception strictly shifts the equilibrium and provide geometric conditions under which this shift improves the deceiver’s steady\-state cost\. Conversely, we also outline some defense strategies against deception that eliminate the induced bias\. We then illustrate our main results on a resource\-allocation game\.

*Related Literature:*Other works that study the vulnerabilities of multi\-agent learning algorithms include utility measurement poisoning\[[19](https://arxiv.org/html/2610.09120#bib.bib19),[20](https://arxiv.org/html/2610.09120#bib.bib20)\], adversarial policies\[[21](https://arxiv.org/html/2610.09120#bib.bib21)\], and continuous\-time equilibrium seeking\[[22](https://arxiv.org/html/2610.09120#bib.bib22),[23](https://arxiv.org/html/2610.09120#bib.bib23)\]\. Unlike\[[19](https://arxiv.org/html/2610.09120#bib.bib19),[20](https://arxiv.org/html/2610.09120#bib.bib20),[21](https://arxiv.org/html/2610.09120#bib.bib21)\], the deceiver in our setting never tampers with the victim’s cost measurements, but manipulates learning solely through its own feasible exploratory action\. In\[[22](https://arxiv.org/html/2610.09120#bib.bib22)\], the deterministic sinusoidal probe structure means that knowledge of the victim’s exploration frequency suffices to reproduce its exploration signal;\[[23](https://arxiv.org/html/2610.09120#bib.bib23)\]requires exact real\-time measurements of an OU\-driven probe\. Both study unconstrained continuous\-time dynamics and establish local practical asymptotic guarantees under multiple vanishing parameter limits\. In contrast, our setting does not require exact reconstruction or real\-time measurements of the exploration signal; mere correlation suffices, as our deceiver receives only a noisy, possibly intermittent, randomly transformed, history\-adaptive signal correlated with the current dither\. We show that the conditional cross\-covariance between leakage and exploration exactly governs the induced bias in the victim’s gradient estimator\. For constrained, discrete\-time bandit play, this yields, to our knowledge, the first non\-asymptotic analysis of adversarial exploration coupling in multi\-agent learning, with mean\-square convergence guarantees\.

## IIPreliminaries

Given a matrixA∈ℝn×mA\\in\\mathbb\{R\}^\{n\\times m\}, we use‖A‖\\left\\lVert A\\right\\rVertto denote the operator norm ofAA\. IfAAis a vector, then‖A‖\\left\\lVert A\\right\\rVertevaluates to the Euclidean norm ofAA\. Iff:ℝn→ℝmf:\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}^\{m\}is differentiable, then∇f:ℝn→ℝn×m\\nabla f:\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}^\{n\\times m\}denotes the transpose of the Jacobian offf\. We use𝕊n=\{s∈ℝn:‖s‖=1\}\\mathbb\{S\}^\{n\}=\\\{s\\in\\mathbb\{R\}^\{n\}:\\left\\lVert s\\right\\rVert=1\\\}and𝔹n=\{s∈ℝn:‖s‖≤1\}\\mathbb\{B\}^\{n\}=\\\{s\\in\\mathbb\{R\}^\{n\}:\\left\\lVert s\\right\\rVert\\leq 1\\\}to denote the unit sphere and ball inℝn\\mathbb\{R\}^\{n\}, respectively\. We denote the ball aroundp∈ℝnp\\in\\mathbb\{R\}^\{n\}of radiusr\>0r\>0by𝔹r​\(p\)=\{s∈ℝn:‖p−s‖≤r\}\\mathbb\{B\}\_\{r\}\(p\)=\\\{s\\in\\mathbb\{R\}^\{n\}:\\left\\lVert p\-s\\right\\rVert\\leq r\\\}\. For a closed convex setE⊂ℝnE\\subset\\mathbb\{R\}^\{n\}, the projection operator is defined asProjE​\(x\)=arg​minp∈E⁡‖x−p‖\\text\{Proj\}\_\{E\}\(x\)=\\argmin\_\{p\\in E\}\\left\\lVert x\-p\\right\\rVert\. We useint​E\\text\{int\}~Eto denote the interior of the setEE\.

## IIIProblem Setup

We focus on a two\-player game, the minimal setting containing a deceiver\-victim pair; the generalization toNN\-player settings is discussed in Remark[2](https://arxiv.org/html/2610.09120#Thmremark2)\. Playeriiselects an actionxix\_\{i\}from an action space𝒳i⊂ℝn\\mathcal\{X\}\_\{i\}\\subset\\mathbb\{R\}^\{n\}with the goal of minimizing their costJi:𝒳1×𝒳2→ℝJ\_\{i\}:\\mathcal\{X\}\_\{1\}\\times\\mathcal\{X\}\_\{2\}\\to\\mathbb\{R\}\. The joint action profile is given byx=\(x1,x2\)∈𝒳x=\(x\_\{1\},x\_\{2\}\)\\in\\mathcal\{X\}, where𝒳=𝒳1×𝒳2\\mathcal\{X\}=\\mathcal\{X\}\_\{1\}\\times\\mathcal\{X\}\_\{2\}denotes the game’s joint action space\. A pointx∗x^\{\*\}is said to be a*Nash equilibrium \(NE\)*if each player has no incentive to unilaterally change their action, i\.e\.,

xi∗∈arg​minxi∈𝒳i⁡Ji​\(xi,x3−i∗\),i∈\{1,2\},x\_\{i\}^\{\*\}\\in\\argmin\_\{x\_\{i\}\\in\\mathcal\{X\}\_\{i\}\}J\_\{i\}\(x\_\{i\};x\_\{3\-i\}^\{\*\}\),\\quad i\\in\\\{1,2\\\},\(1\)where we useJi​\(xi,x3−i\)J\_\{i\}\(x\_\{i\};x\_\{3\-i\}\)andJi​\(x\)J\_\{i\}\(x\)interchangeably\. Given the costs, the*pseudogradient*of the game is defined as:

𝒢⁡\(x\):=\[∇1J1​\(x\)∇2J2​\(x\)\],\\mathcal\{G\}\(x\):=\\begin\{bmatrix\}\\nabla\_\{1\}J\_\{1\}\(x\)\\\\ \\nabla\_\{2\}J\_\{2\}\(x\)\\end\{bmatrix\},\(2\)where∇i\(⋅\)\\nabla\_\{i\}\(\\cdot\)represents differentiation with respect toxix\_\{i\}\. We impose the following assumptions on the game parameters:

###### Assumption 1\.

For eachi∈\{1,2\}i\\in\\\{1,2\\\}andj∈\{1,2\}j\\in\\\{1,2\\\}, the following hold:

1. 1\.The set𝒳i\\mathcal\{X\}\_\{i\}is compact and convex, and there existspi∈𝒳ip\_\{i\}\\in\\mathcal\{X\}\_\{i\},ri\>0r\_\{i\}\>0such that𝔹r1​\(p1\)×𝔹r2​\(p2\)⊂𝒳\\mathbb\{B\}\_\{r\_\{1\}\}\(p\_\{1\}\)\\times\\mathbb\{B\}\_\{r\_\{2\}\}\(p\_\{2\}\)\\subset\\mathcal\{X\}\.
2. 2\.The functionJi​\(x\)J\_\{i\}\(x\)is continuously differentiable on an open neighborhood of𝒳\\mathcal\{X\}, and there existsLi​j\>0L\_\{ij\}\>0such that the function∇jJi​\(x\)\\nabla\_\{j\}J\_\{i\}\(x\)isLi​jL\_\{ij\}\-Lipschitz on𝒳\\mathcal\{X\}\.
3. 3\.There existsγ\>0\\gamma\>0such that the operator𝒢⁡\(⋅\)\\mathcal\{G\}\(\\cdot\)isγ\\gamma\-strongly monotone over𝒳\\mathcal\{X\}, i\.e\., the following holds ⟨𝒢⁡\(x\)−𝒢⁡\(y\),x−y⟩≥γ​‖x−y‖2,\\left\\langle\\mathcal\{G\}\(x\)\-\\mathcal\{G\}\(y\),\\,x\-y\\right\\rangle\\geq\\gamma\\left\\lVert x\-y\\right\\rVert^\{2\},\(3\)for allx,y∈𝒳x,y\\in\\mathcal\{X\}\.□\\square

Conditions 1\-3 are standard in continuous\-action bandit learning\[[1](https://arxiv.org/html/2610.09120#bib.bib1),[24](https://arxiv.org/html/2610.09120#bib.bib24),[25](https://arxiv.org/html/2610.09120#bib.bib25)\]; note that only first\-order smoothness is imposed\. Games with pseudogradients that satisfy \([3](https://arxiv.org/html/2610.09120#S3.E3)\) are referred to as*γ\\gamma\-strongly monotone*, which are ubiquitous in the game theory literature\[[24](https://arxiv.org/html/2610.09120#bib.bib24),[26](https://arxiv.org/html/2610.09120#bib.bib26),[27](https://arxiv.org/html/2610.09120#bib.bib27)\]\. It is well\-known that in games where Assumption[1](https://arxiv.org/html/2610.09120#Thmassumption1)holds, the Nash equilibriumx∗x^\{\*\}is unique and satisfies the following variational inequality

⟨𝒢⁡\(x∗\),x−x∗⟩≥0,∀x∈𝒳\.\\left\\langle\\mathcal\{G\}\(x^\{\*\}\),\\,x\-x^\{\*\}\\right\\rangle\\geq 0,\\quad\\forall x\\in\\mathcal\{X\}\.\(4\)Hence, we say that an action profilex∗∈𝒳x^\{\*\}\\in\\mathcal\{X\}is a “*Nash equilibrium of\(𝒢,𝒳\)\(\\mathcal\{G\},\\mathcal\{X\}\)*” if \([4](https://arxiv.org/html/2610.09120#S3.E4)\) holds\.

### III\-AStandard Bandit Feedback Algorithm

For our work, we will study the bandit feedback\-based algorithm from\[[1](https://arxiv.org/html/2610.09120#bib.bib1),[25](https://arxiv.org/html/2610.09120#bib.bib25),[18](https://arxiv.org/html/2610.09120#bib.bib18)\], which can be implemented by the agents to learn the Nash equilibrium by only using measurements of their cost functions\. At each time stepkk, playeriisamples a vectorμi,k∈𝕊n\\mu\_\{i,k\}\\in\\mathbb\{S\}^\{n\}uniformly at random and computes the following intermediate exploration step

x¯i,k=xi,k\+δ​μi,k,\\bar\{x\}\_\{i,k\}=x\_\{i,k\}\+\\delta\\mu\_\{i,k\},\(5\)whereδ∈\(0,mini⁡ri\)\\delta\\in\(0,\\min\_\{i\}r\_\{i\}\)is the search radius andxi,kx\_\{i,k\}is the action of playeriiat thekk\-th iteration\. For notational convenience, we assume all players use the same perturbation radiusδ\\delta\. This is quite standard\[[25](https://arxiv.org/html/2610.09120#bib.bib25),[18](https://arxiv.org/html/2610.09120#bib.bib18)\], and the case of heterogeneousδi\\delta\_\{i\}is discussed in Remark[2](https://arxiv.org/html/2610.09120#Thmremark2)\. Playeriithen performs the actionx¯i,k\\bar\{x\}\_\{i,k\}, observes their resulting costJi​\(x¯k\)J\_\{i\}\(\\bar\{x\}\_\{k\}\)\(withx¯k=\(x¯1,k,x¯2,k\)\\bar\{x\}\_\{k\}=\(\\bar\{x\}\_\{1,k\},\\bar\{x\}\_\{2,k\}\)\), and updates their action:

xi,k\+1=Proj𝒳iδ​\(xi,k−ηk​nδ​Ji​\(x¯k\)​μi,k\),x\_\{i,k\+1\}=\\text\{Proj\}\_\{\\mathcal\{X\}\_\{i\}^\{\\delta\}\}\\left\(x\_\{i,k\}\-\\eta\_\{k\}\\frac\{n\}\{\\delta\}J\_\{i\}\(\\bar\{x\}\_\{k\}\)\\mu\_\{i,k\}\\right\),\(6\)where𝒳iδ=pi\+\(1−δri\)​\(𝒳i−pi\)\\mathcal\{X\}\_\{i\}^\{\\delta\}=p\_\{i\}\+\(1\-\\frac\{\\delta\}\{r\_\{i\}\}\)\(\\mathcal\{X\}\_\{i\}\-p\_\{i\}\); intuitively, this is a homothetic contraction of𝒳i\\mathcal\{X\}\_\{i\}towards the pointpip\_\{i\}\(from Assumption[1](https://arxiv.org/html/2610.09120#Thmassumption1)\)\. The projection operator in \([6](https://arxiv.org/html/2610.09120#S3.E6)\) ensures that the action profile at the next iterate, specified in \([5](https://arxiv.org/html/2610.09120#S3.E5)\), remains feasible\. This type of feasibility adjustment, which is common in bandit learning\[[25](https://arxiv.org/html/2610.09120#bib.bib25)\], generalizes the contraction\(1−δ\)​𝒳i\(1\-\\delta\)\\mathcal\{X\}\_\{i\}from\[[18](https://arxiv.org/html/2610.09120#bib.bib18)\]and allows us to consider action spaces that need not contain the origin\. Both players use a common learning rateηk\\eta\_\{k\}that satisfies the standard assumption\[[9](https://arxiv.org/html/2610.09120#bib.bib9)\]:

###### Assumption 2\.

The sequence\{ηk\}k=1∞\\\{\\eta\_\{k\}\\\}\_\{k=1\}^\{\\infty\}satisfies:

limk→∞ηk=0,∑k=1∞ηk=∞,\\lim\_\{k\\to\\infty\}\\eta\_\{k\}=0,\\quad\\sum\_\{k=1\}^\{\\infty\}\\eta\_\{k\}=\\infty,\(7\)andηk\>0\\eta\_\{k\}\>0for eachk∈ℕk\\in\\mathbb\{N\}\.□\\square

The algorithm \([5](https://arxiv.org/html/2610.09120#S3.E5)\)\-\([6](https://arxiv.org/html/2610.09120#S3.E6)\) has been covered extensively in the*bandit optimization*literature\[[1](https://arxiv.org/html/2610.09120#bib.bib1),[18](https://arxiv.org/html/2610.09120#bib.bib18),[25](https://arxiv.org/html/2610.09120#bib.bib25),[26](https://arxiv.org/html/2610.09120#bib.bib26)\], and the main intuition behind it is in the signalnδ​Ji​\(x¯k\)​μi,k\\frac\{n\}\{\\delta\}J\_\{i\}\(\\bar\{x\}\_\{k\}\)\\mu\_\{i,k\}from \([6](https://arxiv.org/html/2610.09120#S3.E6)\), which serves as a single\-point stochastic gradient estimator\. More precisely, its conditional expectation equals the gradient of a suitably smoothed version ofJiJ\_\{i\}, which differs from∇iJi​\(xk\)\\nabla\_\{i\}J\_\{i\}\(x\_\{k\}\)by an𝒪⁡\(δ\)\\mathcal\{O\}\(\\delta\)term under Assumption[1](https://arxiv.org/html/2610.09120#Thmassumption1)\(wherexk=\(x1,k,x2,k\)x\_\{k\}=\(x\_\{1,k\},x\_\{2,k\}\)\)\. Hence, \([6](https://arxiv.org/html/2610.09120#S3.E6)\) can be interpreted as a noisy gradient descent update on a slightly perturbed game\. Under Assumptions[1](https://arxiv.org/html/2610.09120#Thmassumption1)\-[2](https://arxiv.org/html/2610.09120#Thmassumption2)and independent exploration, these dynamics are known to efficiently learn the unique NE\.

## IVBandit Feedback with Deception

The convergence guarantees of exploration\-based algorithms, such as \([5](https://arxiv.org/html/2610.09120#S3.E5)\)\-\([6](https://arxiv.org/html/2610.09120#S3.E6)\), rely on the premise that agents conduct their exploration independently and without interference\. However, in competitive, adversarial, or asymmetric environments, these independence and privacy assumptions can break down\[[15](https://arxiv.org/html/2610.09120#bib.bib15),[16](https://arxiv.org/html/2610.09120#bib.bib16),[17](https://arxiv.org/html/2610.09120#bib.bib17)\]\. In games, the signals available to the players form an information structure separate from the actions and costs\[[28](https://arxiv.org/html/2610.09120#bib.bib28)\]\. Models of espionage or information leakage study settings where one player receives noisy or partial information about an opponent’s selected strategy or realized randomization\[[29](https://arxiv.org/html/2610.09120#bib.bib29),[30](https://arxiv.org/html/2610.09120#bib.bib30),[31](https://arxiv.org/html/2610.09120#bib.bib31)\]\. These works motivate the need to examine analogous asymmetries in bandit learning, where the leaked randomization is now the mechanism by which each player learns\.

Specifically, we consider a setting where player 2 intercepts or infers privileged information regarding player 1’s search policy\. If player 2 integrates this information into only their own actions, they can manipulate the gradient estimate that player 1 uses to learn\. Here, we call player 2 the*deceptive*player, while player 1 is the*oblivious*player\. This section formalizes the structure of the leaked information, the DBL dynamics, and their long\-term effects on learning\.

### IV\-AInformation Asymmetry

Suppose that at each iterationkk, each player selects a search directionμi,k∈𝕊n\\mu\_\{i,k\}\\in\\mathbb\{S\}^\{n\}independently and uniformly at random, but player 2 also receives a signalΘ1,k∈ℝn\\Theta\_\{1,k\}\\in\\mathbb\{R\}^\{n\}possibly containing privileged information regardingμ1,k\\mu\_\{1,k\}\. We useℱk\\mathcal\{F\}\_\{k\}to denote the pre\-round history up to stagekk, and assume thatΘ1,k\\Theta\_\{1,k\}satisfies the following structural condition:

###### Assumption 3\.

Fork∈ℕ∪\{0\}k\\in\\mathbb\{N\}\\cup\\\{0\\\}, the signalΘ1,k∈ℝn\\Theta\_\{1,k\}\\in\\mathbb\{R\}^\{n\}takes the form

Θ1,k=Λk​μ1,k\+wk,\\Theta\_\{1,k\}=\\Lambda\_\{k\}\\mu\_\{1,k\}\+w\_\{k\},\(8\)where, conditional onℱk\\mathcal\{F\}\_\{k\}, the following hold almost surely:

1. 1\.The directionsμ1,k\\mu\_\{1,k\}andμ2,k\\mu\_\{2,k\}are independent and uniformly distributed on𝕊n\\mathbb\{S\}^\{n\}\. Moreover, the pair\(Λk,wk\)\(\\Lambda\_\{k\},w\_\{k\}\)is conditionally independent of\(μ1,k,μ2,k\)\(\\mu\_\{1,k\},\\mu\_\{2,k\}\)\.
2. 2\.There exists a matrixΓ∈ℝn×n\\Gamma\\in\\mathbb\{R\}^\{n\\times n\}, independent ofkk, such that𝔼k​\[Λk\]=Γ\\mathbb\{E\}\_\{k\}\[\\Lambda\_\{k\}\]=\\Gammaa\.s, where𝔼k\[⋅\]:=𝔼\[⋅\|ℱk\]\\mathbb\{E\}\_\{k\}\[~\\cdot~\]:=\\mathbb\{E\}\[~\\cdot~\|\\mathcal\{F\}\_\{k\}\]\.
3. 3\.There exists constantsΛ¯,w¯\>0\\bar\{\\Lambda\},\\bar\{w\}\>0such that‖Λk‖≤Λ¯\\left\\lVert\\Lambda\_\{k\}\\right\\rVert\\leq\\bar\{\\Lambda\}and‖wk‖≤w¯\\left\\lVert w\_\{k\}\\right\\rVert\\leq\\bar\{w\}a\.s\.

All random variables are defined on the filtered probability space\(Ω,ℱ,\{ℱk\}k≥0,ℙ\)\(\\Omega,\\mathcal\{F\},\\\{\\mathcal\{F\}\_\{k\}\\\}\_\{k\\geq 0\},\\mathbb\{P\}\), with pre\-round history given by theσ\\sigma\-algebraℱk=σ⁡\(x0,\{μ1,ℓ,μ2,ℓ,Λℓ,wℓ\}ℓ<k\)\\mathcal\{F\}\_\{k\}=\\sigma\(x\_\{0\},\\\{\\mu\_\{1,\\ell\},\\mu\_\{2,\\ell\},\\Lambda\_\{\\ell\},w\_\{\\ell\}\\\}\_\{\\ell<k\}\)\.□\\square

Assumption[3](https://arxiv.org/html/2610.09120#Thmassumption3)captures a range of interception scenarios, such as channel leaks, noisy sensing, and intermittent measurements\. In a practical context,Θ1,k\\Theta\_\{1,k\}represents player 2’s imperfect measurement of player 1’s exploratory behavior\.

The structure of \([8](https://arxiv.org/html/2610.09120#S4.E8)\) isolates two fundamental sources of imperfection in this observation\. The random matrixΛk\\Lambda\_\{k\}models the transformation, attenuation, or scaling of the intercepted signal\. The existence ofΓ\\Gammaensures that the dither\-signal cross\-covariance is well\-behaved\. Meanwhile,wkw\_\{k\}captures ambient measurement noise or channel interference, which we do not require to be zero mean\. More generally, sinceμ1,k=1δ​\(x¯1,k−x1,k\)\\mu\_\{1,k\}=\\frac\{1\}\{\\delta\}\(\\bar\{x\}\_\{1,k\}\-x\_\{1,k\}\), the signalΘ1,k\\Theta\_\{1,k\}may also be a noisy measurement of the played actionx¯1,k\\bar\{x\}\_\{1,k\}rather than the actual dither\. Notably, the formulation \([8](https://arxiv.org/html/2610.09120#S4.E8)\) also allows for intermittently available measurements\. Indeed, suppose that at stagekkthe signal is only intercepted with probabilityρ∈\(0,1\]\\rho\\in\(0,1\]\. TakingΛk=bk​Λ~k\\Lambda\_\{k\}=b\_\{k\}\\widetilde\{\\Lambda\}\_\{k\}andwk=bk​w~kw\_\{k\}=b\_\{k\}\\widetilde\{w\}\_\{k\}withbk\|ℱk∼Bernoulli​\(ρ\)b\_\{k\}\|\\mathcal\{F\}\_\{k\}\\sim\\text\{Bernoulli\}\(\\rho\)\(independent of the dithers andw~k,Λ~k\\widetilde\{w\}\_\{k\},\\widetilde\{\\Lambda\}\_\{k\}\) givesΓ=ρ​Γ~\\Gamma=\\rho\\widetilde\{\\Gamma\}, whereΓ~=𝔼k​\[Λ~k\]\\widetilde\{\\Gamma\}=\\mathbb\{E\}\_\{k\}\[\\widetilde\{\\Lambda\}\_\{k\}\]\. Hence, missed or late interceptions merely attenuate the mean dither\-signal cross\-covariance byρ\\rho\.

### IV\-BBandit Feedback Algorithm with Deception

With the information asymmetry formally defined, we now construct the modified learning dynamics\. We assume player 1 remains oblivious to deception and continues to execute the standard bandit dynamics given below

x¯1,k\\displaystyle\\bar\{x\}\_\{1,k\}=x1,k\+δ​μ1,k\\displaystyle=x\_\{1,k\}\+\\delta\\mu\_\{1,k\}\(9a\)x1,k\+1\\displaystyle x\_\{1,k\+1\}=Proj𝒳1δ​\(x1,k−ηk​nδ​J1​\(x¯k\)​μ1,k\)\.\\displaystyle=\\text\{Proj\}\_\{\\mathcal\{X\}\_\{1\}^\{\\delta\}\}\\left\(x\_\{1,k\}\-\\eta\_\{k\}\\frac\{n\}\{\\delta\}J\_\{1\}\(\\bar\{x\}\_\{k\}\)\\mu\_\{1,k\}\\right\)\.\(9b\)Meanwhile, suppose that player 2 exploits the leaked signal by actively coupling their exploration with player 1’s search direction\. Before the stagekkcosts are realized, player 2 injects the signalΘ1,k\\Theta\_\{1,k\}into their exploration step with a tunable gaincc\. The dynamics implemented by player 2 are:

x¯2,k\\displaystyle\\bar\{x\}\_\{2,k\}=x2,k\+δ​μ2,k\+c​δ​Θ1,k\\displaystyle=x\_\{2,k\}\+\\delta\\mu\_\{2,k\}\+c\\delta\\Theta\_\{1,k\}\(10a\)x2,k\+1\\displaystyle x\_\{2,k\+1\}=Proj𝒳2δc​\(x2,k−ηk​nδ​J2​\(x¯k\)​μ2,k\),\\displaystyle=\\text\{Proj\}\_\{\\mathcal\{X\}\_\{2\}^\{\{\\delta\_\{c\}\}\}\}\\left\(x\_\{2,k\}\-\\eta\_\{k\}\\frac\{n\}\{\\delta\}J\_\{2\}\(\\bar\{x\}\_\{k\}\)\\mu\_\{2,k\}\\right\),\(10b\)whereδc=δ⁡\(1\+\|c\|​\(Λ¯\+w¯\)\)\{\\delta\_\{c\}\}=\\delta\(1\+\|c\|\(\\bar\{\\Lambda\}\+\\bar\{w\}\)\), and we assume thatδ,c\\delta,care chosen such thatδc<r2\\delta\_\{c\}<r\_\{2\}\. The formulation ofδc\\delta\_\{c\}guarantees that even in the worst\-case realization ofΛk\\Lambda\_\{k\}andwkw\_\{k\}, player 2’s exploratory action remains feasible\. We will call system \([9](https://arxiv.org/html/2610.09120#S4.E9)\)\-\([10](https://arxiv.org/html/2610.09120#S4.E10)\) the*deceptive bandit learning \(DBL\) dynamics*\.

![Refer to caption](https://arxiv.org/html/2610.09120v1/spsa_dec_iblock.png)Fig\. 1:Exploration leakage and coupling in a two\-player game with bandit feedback\.The subtlety behind the proposed deception mechanism can be observed through the expected gradient signal, given byg^i,k=nδ​Ji​\(x¯k\)​μi,k\\widehat\{g\}\_\{i,k\}=\\frac\{n\}\{\\delta\}J\_\{i\}\(\\bar\{x\}\_\{k\}\)\\mu\_\{i,k\}\. Computing the smoothed average ofg^i,k\\widehat\{g\}\_\{i,k\}aroundxkx\_\{k\}\(details in the Appendix\) yields:

𝔼k​\[g^1,k\]\\displaystyle\\mathbb\{E\}\_\{k\}\[\\widehat\{g\}\_\{1,k\}\]=∇1J1​\(xk\)\+c​Γ⊤​∇2J1​\(xk\)\+β1,kδ\\displaystyle=\\nabla\_\{1\}J\_\{1\}\(x\_\{k\}\)\+c\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x\_\{k\}\)\+\\beta\_\{1,k\}^\{\\delta\}\(11a\)𝔼k​\[g^2,k\]\\displaystyle\\mathbb\{E\}\_\{k\}\[\\widehat\{g\}\_\{2,k\}\]=∇2J2​\(xk\)\+β2,kδ,\\displaystyle=\\nabla\_\{2\}J\_\{2\}\(x\_\{k\}\)\+\\beta\_\{2,k\}^\{\\delta\},\(11b\)whereβ1,kδ\\beta\_\{1,k\}^\{\\delta\}andβ2,kδ\\beta\_\{2,k\}^\{\\delta\}areℱk\\mathcal\{F\}\_\{k\}\-measurable𝒪⁡\(δ\)\\mathcal\{O\}\(\\delta\)smoothing biases, with bounds provided in Lemma[2](https://arxiv.org/html/2610.09120#Thmlemma2)of the Appendix; such biases are present even in the nominal \(c=0c=0\) algorithm\. The distinctive effect of deception is the induced externalityc​Γ⊤​∇2J1​\(xk\)c\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x\_\{k\}\), which does not vanish withδ\\delta\.The system \([11](https://arxiv.org/html/2610.09120#S4.E11)\) reveals that while player 2 still learns their gradient up to the𝒪⁡\(δ\)\\mathcal\{O\}\(\\delta\)bias, player 1 now learns a flawed estimate affected by this externality\.

Motivated by \([11](https://arxiv.org/html/2610.09120#S4.E11)\), we propose the notion of a*deceptive pseudogradient*, which is given by

𝒢cdec​\(x\)=\[∇1J1​\(x\)\+c​Γ⊤​∇2J1​\(x\)∇2J2​\(x\)\]\.\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(x\)=\\begin\{bmatrix\}\\nabla\_\{1\}J\_\{1\}\(x\)\+c\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x\)\\\\ \\nabla\_\{2\}J\_\{2\}\(x\)\\end\{bmatrix\}\.\(12\)For the modified learning dynamics to converge,𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}must remain well\-behaved\. Specifically, the injection of the deceptive externalityc​Γ⊤​∇2J1​\(x\)c\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x\)must not destroy the monotonicity of the nominal game\. By leveraging the Lipschitz continuity of∇2J1​\(⋅\)\\nabla\_\{2\}J\_\{1\}\(\\cdot\)obtained from Assumption[1](https://arxiv.org/html/2610.09120#Thmassumption1), it is straightforward to verify that𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}remains strongly monotone as long as the following condition is satisfied:

γc:=γ−\|c\|​L12​‖Γ‖\>0,\\gamma\_\{c\}:=\\gamma\-\|c\|L\_\{12\}\\left\\lVert\\Gamma\\right\\rVert\>0,\(13\)whereL12L\_\{12\}is the Lipschitz constant of∇2J1​\(⋅\)\\nabla\_\{2\}J\_\{1\}\(\\cdot\)\. If \([13](https://arxiv.org/html/2610.09120#S4.E13)\) holds, there exists a unique Nash equilibrium of\(𝒢cdec,𝒳\)\(\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\},\\mathcal\{X\}\), which we call the*deceptive Nash equilibrium \(DNE\)*\. This is formalized in the following definition:

###### Definition 1\.

Suppose that𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}, given in \([12](https://arxiv.org/html/2610.09120#S4.E12)\), is strongly monotone\. The deceptive Nash equilibrium, denotedxc∗x\_\{c\}^\{\*\}, is the unique point in𝒳\\mathcal\{X\}that satisfies the following

⟨𝒢cdec​\(xc∗\),x−xc∗⟩≥0,\\left\\langle\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(x\_\{c\}^\{\*\}\),\\,x\-x\_\{c\}^\{\*\}\\right\\rangle\\geq 0,\(14\)for allx∈𝒳x\\in\\mathcal\{X\}\.□\\square

Equations \([12](https://arxiv.org/html/2610.09120#S4.E12)\), \([14](https://arxiv.org/html/2610.09120#S4.E14)\) identify a new potential steady state induced by the deception mechanism\. This raises two natural questions: do the DBL dynamics approach this DNE, and how does the DNE compare with the nominal NE? We answer these questions next\.

## VMain Results

We establish convergence guarantees for the DBL dynamics, then characterize when deception shifts the steady state and benefits the deceiver\.

### V\-AConvergence Analysis

Because the coupled gradient estimators now track𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}, the first question is how closely the DBL iterates approach the DNE and at what rate\. We provide both guarantees in the following theorem:

###### Theorem 1\.

Consider the DBL dynamics \([9](https://arxiv.org/html/2610.09120#S4.E9)\)\-\([10](https://arxiv.org/html/2610.09120#S4.E10)\) under Assumptions[1](https://arxiv.org/html/2610.09120#Thmassumption1)\-[3](https://arxiv.org/html/2610.09120#Thmassumption3), where \([13](https://arxiv.org/html/2610.09120#S4.E13)\) holds\. Then, there existsR\>0R\>0such that, for anyx0∈𝒳1δ×𝒳2δcx\_\{0\}\\in\\mathcal\{X\}\_\{1\}^\{\\delta\}\\times\\mathcal\{X\}\_\{2\}^\{\\delta\_\{c\}\}andδ\\deltasatisfying

0<δ<min⁡\{r1,r21\+\|c\|\(Λ¯\+w¯\)\}:=rc,0<\\delta<\\min\\left\\\{r\_\{1\},\\frac\{r\_\{2\}\}\{1\+\|c\|\(\\bar\{\\Lambda\}\+\\bar\{w\}\)\}\\right\\\}:=r\_\{c\},\(15\)the following bound holds

lim supk→∞𝔼⁡\[‖xk−xc∗‖2\]≤R​δ2\.\\limsup\_\{k\\to\\infty\}\\mathbb\{E\}\[\\left\\lVert x\_\{k\}\-x\_\{c\}^\{\*\}\\right\\rVert^\{2\}\]\\leq R\\delta^\{2\}\.\(16\)If the step sizes also satisfyη0≥0\\eta\_\{0\}\\geq 0andηk=qγc​k\\eta\_\{k\}=\\frac\{q\}\{\\gamma\_\{c\}k\}fork≥1k\\geq 1, whereq\>1q\>1andγc=γ−L12​\|c\|​‖Γ‖\\gamma\_\{c\}=\\gamma\-L\_\{12\}\|c\|\\left\\lVert\\Gamma\\right\\rVert, then there also existsM\>0M\>0such that the following holds

𝔼⁡\[‖xk−xc∗‖2\]≤Mδ2​k\+R​δ2,\\mathbb\{E\}\[\\left\\lVert x\_\{k\}\-x\_\{c\}^\{\*\}\\right\\rVert^\{2\}\]\\leq\\frac\{M\}\{\\delta^\{2\}k\}\+R\\delta^\{2\},\(17\)for allk∈ℕk\\in\\mathbb\{N\}andδ∈\(0,rc\)\\delta\\in\(0,r\_\{c\}\)\.

Thus, while player 1 remains oblivious and continues to execute the nominal bandit update, the joint dynamics converge to a neighborhood of the shifted DNE\. From \([17](https://arxiv.org/html/2610.09120#S5.E17)\), we see that the DBL dynamics inherit the same𝒪⁡\(d2/ε2\)\\mathcal\{O\}\(d^\{2\}/\{\\varepsilon^\{2\}\}\)complexity guarantees from\[[18](https://arxiv.org/html/2610.09120#bib.bib18)\], whered=2​n=dim​𝒳d=2n=\\text\{dim\}~\\mathcal\{X\}:

###### Corollary 1\.

Under the conditions of Theorem[1](https://arxiv.org/html/2610.09120#Thmthm1)for which \([17](https://arxiv.org/html/2610.09120#S5.E17)\) holds, for anyε\>0\\varepsilon\>0sufficiently small, choosingδ2=ε\(2​R\)\\delta^\{2\}=\\frac\{\\varepsilon\}\{\(2R\)\}andk≥4​M​Rε2k\\geq\\frac\{4MR\}\{\\varepsilon^\{2\}\}yields𝔼⁡\[‖xk−xc∗‖2\]≤ε\\mathbb\{E\}\[\\left\\lVert x\_\{k\}\-x\_\{c\}^\{\*\}\\right\\rVert^\{2\}\]\\leq\\varepsilon, whereM,RM,Rare given in Section[VI\-A](https://arxiv.org/html/2610.09120#S6.SS1)\. Consequently, the DBL dynamics attain the same𝒪⁡\(d2/ε2\)\\mathcal\{O\}\(d^\{2\}/\\varepsilon^\{2\}\)complexity as the deception\-free bandit algorithm from\[[18](https://arxiv.org/html/2610.09120#bib.bib18)\]\.

### V\-BCharacterization of the DNE and Immunity Conditions

We established convergence to a neighborhood of the DNE, which is characterized by the variational inequality \([14](https://arxiv.org/html/2610.09120#S4.E14)\)\. It is evident from \([14](https://arxiv.org/html/2610.09120#S4.E14)\) that the steady state conditions are altered under deception, but a fundamental question remains: when is the DNE actually different from the nominal NE? Equation \([18](https://arxiv.org/html/2610.09120#S5.E18)\) bounds the magnitude of this shift, but we now ask when it is nonzero\. Furthermore, in what situations does deception actually improve the cost of the deceiver?

To isolate the effect of the deception from the complexities of active constraints, our vulnerability characterization focuses on interior nominal NE, which is a practical operating condition in many real\-world settings\[[32](https://arxiv.org/html/2610.09120#bib.bib32),[33](https://arxiv.org/html/2610.09120#bib.bib33),[34](https://arxiv.org/html/2610.09120#bib.bib34)\]\. Specifically, we find that interior NE are locally steerable via deception whenever the externalityΓ⊤​∇2J1​\(⋅\)\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(\\cdot\)is nonzero at the nominal NE\. Conversely, the equilibrium is invariant wheneverΓ⊤​∇2J1​\(x∗\)=0\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x^\{\*\}\)=0, even ifx∗x^\{\*\}is not necessarily an interior NE\. Thus, the zero\-correlation conditionΓ=0\\Gamma=0from Remark[1](https://arxiv.org/html/2610.09120#Thmremark1)provides a sufficient universal defense against this particular deception mechanism\. Meanwhile, nonzeroΓ\\Gammacan still yield immunity ifrange⁡\(Γ\)⟂∇2J1​\(x∗\)\\operatorname\{range\}\(\\Gamma\)\\perp\\nabla\_\{2\}J\_\{1\}\(x^\{\\ast\}\), i\.e\., when the leakage carries no information about the externality\. We formalize these ideas in the following theorem:

![Refer to caption](https://arxiv.org/html/2610.09120v1/dec_x.png)

![Refer to caption](https://arxiv.org/html/2610.09120v1/dec_j.png)

![Refer to caption](https://arxiv.org/html/2610.09120v1/dec_ssc.png)

Fig\. 2:Monte Carlo study overM=300M=300realizations\. 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 ofcc, and the equilibrium displacement\.###### Theorem 2\.

Suppose that Assumptions[1](https://arxiv.org/html/2610.09120#Thmassumption1)and[3](https://arxiv.org/html/2610.09120#Thmassumption3)hold\. Ifx∗∈int​𝒳x^\{\*\}\\in\\text\{int\}~\\mathcal\{X\}andΓ⊤​∇2J1​\(x∗\)≠0\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x^\{\*\}\)\\neq 0, then the mappingc↦xc∗c\\mapsto x^\{\*\}\_\{c\}is injective on a neighborhood of 0\. If insteadΓ⊤​∇2J1​\(x∗\)=0\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x^\{\*\}\)=0, thenxc∗=x∗x\_\{c\}^\{\*\}=x^\{\*\}for allccwhere𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}is strongly monotone\.

### V\-CImpact of Deception

While Theorem[2](https://arxiv.org/html/2610.09120#Thmthm2)tells us when the deceiver can steer the dynamics to a new steady state, it is common in practical scenarios that the deceiver is interested in improving their own well\-being\. If the mappingc→xc∗c\\to x\_\{c\}^\{\*\}is differentiable around 0, we can evaluate the local sensitivity ofJ2J\_\{2\}tocc\. Thus, the question of whether deception is profitable naturally reduces to characterizing this derivative and identifying when it does not vanish\. These conditions are formalized below:

###### Theorem 3\.

Suppose that Assumptions[1](https://arxiv.org/html/2610.09120#Thmassumption1)and[3](https://arxiv.org/html/2610.09120#Thmassumption3)hold, where𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}is continuously differentiable andx∗∈int​𝒳x^\{\*\}\\in\\text\{int\}~\\mathcal\{X\}\. If the following holds:

\[∇1J2​\(x∗\)0\]⊤∇𝒢\(x∗\)−⁣⊤\[Γ⊤​∇2J1​\(x∗\)0\]≠0,\\begin\{bmatrix\}\\nabla\_\{1\}J\_\{2\}\(x^\{\*\}\)\\\\ 0\\end\{bmatrix\}^\{\\top\}\\nabla\\mathcal\{G\}\(x^\{\*\}\)^\{\-\\top\}\\begin\{bmatrix\}\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x^\{\*\}\)\\\\ 0\\end\{bmatrix\}\\neq 0,\(19\)there exists a nonempty open intervalℰ⊂ℝ\\mathcal\{E\}\\subset\\mathbb\{R\}such that, for allc∈ℰc\\in\\mathcal\{E\},𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}is strongly monotone andJ2​\(xc∗\)<J2​\(x∗\)J\_\{2\}\(x\_\{c\}^\{\*\}\)<J\_\{2\}\(x^\{\*\}\)\.

Theorem[3](https://arxiv.org/html/2610.09120#Thmthm3)provides some important geometric intuition behind the mechanics of an adversarially favorable shift\. Naturally, for \([19](https://arxiv.org/html/2610.09120#S5.E19)\) to hold, the termΓ⊤​∇2J1​\(x∗\)\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x^\{\*\}\)cannot be zero\. This parallels Theorem[2](https://arxiv.org/html/2610.09120#Thmthm2), which established that this nonzero externality was needed for injectivity of the mappingc↦xc∗c\\mapsto x\_\{c\}^\{\*\}\. Without this condition, the DNE remains atx∗x^\{\*\}, which implies that the steady state cost function values will also be unchanged\. Surprisingly, condition \([19](https://arxiv.org/html/2610.09120#S5.E19)\) also requires that the other cross derivative∇1J2​\(⋅\)\\nabla\_\{1\}J\_\{2\}\(\\cdot\)is nonzero at the NE\. Intuitively, this makes sense: if the deceiver’s cost is completely insensitive to the victim’s actions at the nominal equilibrium, shifting the victim’s steady\-state behavior yields no immediate benefit\. Theorem[1](https://arxiv.org/html/2610.09120#Thmthm1)then tells us that the cost improvements in Theorem[3](https://arxiv.org/html/2610.09120#Thmthm3)can be realized in the long\-term expected DBL trajectories wheneverδ\\deltais sufficiently small\.

## VIProofs of Main Results

### VI\-AProof of Theorem[1](https://arxiv.org/html/2610.09120#Thmthm1)

Let𝒳cδ:=𝒳1δ×𝒳2δc\\mathcal\{X\}^\{\\delta\}\_\{c\}:=\\mathcal\{X\}\_\{1\}^\{\\delta\}\\times\\mathcal\{X\}\_\{2\}^\{\\delta\_\{c\}\}, and letxc,δ∗x\_\{c,\\delta\}^\{\*\}denote the unique Nash equilibrium of\(𝒢cdec,𝒳cδ\)\(\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\},\\mathcal\{X\}^\{\\delta\}\_\{c\}\)\. DefineG^k=nδ​\(J1​\(x¯k\)​μ1,k,J2​\(x¯k\)​μ2,k\)\\widehat\{G\}\_\{k\}=\\frac\{n\}\{\\delta\}\(J\_\{1\}\(\\bar\{x\}\_\{k\}\)\\mu\_\{1,k\},J\_\{2\}\(\\bar\{x\}\_\{k\}\)\\mu\_\{2,k\}\)\. Lettingek=xk−xc,δ∗e\_\{k\}=x\_\{k\}\-x^\{\*\}\_\{c,\\delta\}, for eachk≥0k\\geq 0we have:

𝔼⁡\[‖xk−xc∗‖2\]\\displaystyle\\mathbb\{E\}\[\\left\\lVert x\_\{k\}\-x\_\{c\}^\{\*\}\\right\\rVert^\{2\}\]≤2​𝔼​\[‖ek‖2\]\+2​‖xc,δ∗−xc∗‖2\.\\displaystyle\\leq 2\\mathbb\{E\}\\left\[\\left\\lVert e\_\{k\}\\right\\rVert^\{2\}\\right\]\+2\\left\\lVert x\_\{c,\\delta\}^\{\*\}\-x\_\{c\}^\{\*\}\\right\\rVert^\{2\}\.\(20\)By construction,xkx\_\{k\}andeke\_\{k\}areℱk\\mathcal\{F\}\_\{k\}\-measurable for everykk\.To upper bound \([20](https://arxiv.org/html/2610.09120#S6.E20)\), let us consider the first term, since the second term can be upper bounded with Lemma[1](https://arxiv.org/html/2610.09120#Thmlemma1)in the Appendix\. Sincexc,δ∗∈𝒳cδx\_\{c,\\delta\}^\{\*\}\\in\\mathcal\{X\}^\{\\delta\}\_\{c\}, we can leverage the non\-expansiveness of the projection operator to obtain:

𝔼k​\[‖ek\+1‖2\]≤𝔼k​\[‖xk−ηk​G^k−xc,δ∗‖2\]\\displaystyle\\mathbb\{E\}\_\{k\}\\left\[\\left\\lVert e\_\{k\+1\}\\right\\rVert^\{2\}\\right\]\\leq\\mathbb\{E\}\_\{k\}\\left\[\\left\\lVert x\_\{k\}\-\\eta\_\{k\}\\widehat\{G\}\_\{k\}\-x\_\{c,\\delta\}^\{\*\}\\right\\rVert^\{2\}\\right\]≤𝔼k​\[‖ek‖2\]\+ηk2​𝔼k​\[‖G^k‖2\]−2​ηk​⟨𝔼k​\[G^k\],ek⟩\.\\displaystyle~~~~\\leq\\mathbb\{E\}\_\{k\}\\left\[\\left\\lVert e\_\{k\}\\right\\rVert^\{2\}\\right\]\+\\eta\_\{k\}^\{2\}\\mathbb\{E\}\_\{k\}\\left\[\\left\\lVert\\widehat\{G\}\_\{k\}\\right\\rVert^\{2\}\\right\]\-2\\eta\_\{k\}\\left\\langle\\mathbb\{E\}\_\{k\}\\left\[\\widehat\{G\}\_\{k\}\\right\],\\,e\_\{k\}\\right\\rangle\.LetΔkδ=\(β1,kδ,β2,kδ\)\\Delta\_\{k\}^\{\\delta\}=\(\\beta\_\{1,k\}^\{\\delta\},\\beta\_\{2,k\}^\{\\delta\}\), whereβ1,kδ\\beta\_\{1,k\}^\{\\delta\}andβ2,kδ\\beta\_\{2,k\}^\{\\delta\}are from \([11](https://arxiv.org/html/2610.09120#S4.E11)\) and satisfy the bounds given in Lemma[2](https://arxiv.org/html/2610.09120#Thmlemma2)from the Appendix\. Let𝒥=supi∈\{1,2\}supx∈𝒳\|Ji​\(x\)\|\\mathcal\{J\}=\\sup\_\{i\\in\\\{1,2\\\}\}\\sup\_\{x\\in\\mathcal\{X\}\}\|J\_\{i\}\(x\)\|, which is finite\. Since𝔼k​\[G^k\]=𝒢cdec​\(xk\)\+Δkδ\\mathbb\{E\}\_\{k\}\[\\widehat\{G\}\_\{k\}\]=\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(x\_\{k\}\)\+\\Delta\_\{k\}^\{\\delta\}, we obtain:

𝔼k​\[‖ek\+1‖2\]\\displaystyle\\mathbb\{E\}\_\{k\}\\left\[\\left\\lVert e\_\{k\+1\}\\right\\rVert^\{2\}\\right\]≤𝔼k​\[‖ek‖2\]−2​ηk​𝔼k​\[⟨𝒢cdec​\(xk\),ek⟩\]\\displaystyle\\leq\\mathbb\{E\}\_\{k\}\\left\[\\left\\lVert e\_\{k\}\\right\\rVert^\{2\}\\right\]\-2\\eta\_\{k\}\\mathbb\{E\}\_\{k\}\\left\[\\left\\langle\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(x\_\{k\}\),\\,e\_\{k\}\\right\\rangle\\right\]\+2​n2​ηk2​𝒥2δ2−2​ηk​𝔼k​\[⟨Δkδ,ek⟩\]​a\.s\.\\displaystyle~~~\+\\frac\{2n^\{2\}\\eta\_\{k\}^\{2\}\\mathcal\{J\}^\{2\}\}\{\\delta^\{2\}\}\-2\\eta\_\{k\}\\mathbb\{E\}\_\{k\}\\left\[\\left\\langle\\Delta\_\{k\}^\{\\delta\},\\,e\_\{k\}\\right\\rangle\\right\]\\text\{ a\.s\.\}By the definition ofeke\_\{k\}andxc,δ∗x\_\{c,\\delta\}^\{\*\}, we know that the following holds for allxk∈𝒳cδx\_\{k\}\\in\\mathcal\{X\}\_\{c\}^\{\\delta\}:

⟨𝒢cdec​\(xk\),ek⟩≥γc​‖ek‖2\.\\left\\langle\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(x\_\{k\}\),\\,e\_\{k\}\\right\\rangle\\geq\\gamma\_\{c\}\\left\\lVert e\_\{k\}\\right\\rVert^\{2\}\.\(21\)We can also apply Young’s inequality to obtain

\|⟨Δkδ,ek⟩\|\\displaystyle\|\\left\\langle\\Delta\_\{k\}^\{\\delta\},\\,e\_\{k\}\\right\\rangle\|≤γc2​‖ek‖2\+12​γc​‖Δkδ‖2\.\\displaystyle\\leq\\frac\{\\gamma\_\{c\}\}\{2\}\\left\\lVert e\_\{k\}\\right\\rVert^\{2\}\+\\frac\{1\}\{2\\gamma\_\{c\}\}\\left\\lVert\\Delta\_\{k\}^\{\\delta\}\\right\\rVert^\{2\}\.\(22\)By Lemma[2](https://arxiv.org/html/2610.09120#Thmlemma2)in the Appendix, there existsα\>0\\alpha\>0such that‖Δkδ‖2≤α​δ2\\left\\lVert\\Delta\_\{k\}^\{\\delta\}\\right\\rVert^\{2\}\\leq\\alpha\\delta^\{2\}almost surely for eachkk\. We can then combine \([21](https://arxiv.org/html/2610.09120#S6.E21)\) with \([22](https://arxiv.org/html/2610.09120#S6.E22)\) and take the total expectation overℱk\\mathcal\{F\}\_\{k\}to obtain

𝔼⁡\[‖ek\+1‖2\]\\displaystyle\\mathbb\{E\}\\left\[\\left\\lVert e\_\{k\+1\}\\right\\rVert^\{2\}\\right\]≤\(1−ηk​γc\)​𝔼​\[‖ek‖2\]\+2​n2​ηk2​𝒥2δ2\+α​ηk​δ2γc\.\\displaystyle\\leq\(1\-\\eta\_\{k\}\\gamma\_\{c\}\)\\mathbb\{E\}\\left\[\\left\\lVert e\_\{k\}\\right\\rVert^\{2\}\\right\]\+\\frac\{2n^\{2\}\\eta\_\{k\}^\{2\}\\mathcal\{J\}^\{2\}\}\{\\delta^\{2\}\}\+\\frac\{\\alpha\\eta\_\{k\}\\delta^\{2\}\}\{\\gamma\_\{c\}\}\.\(23\)A standard stochastic approximation comparison\[[35](https://arxiv.org/html/2610.09120#bib.bib35)\]gives:

lim supk→∞𝔼⁡\[‖xk−xc,δ∗‖2\]≤α​δ2γc2\.\\limsup\_\{k\\to\\infty\}\\mathbb\{E\}\\left\[\\left\\lVert x\_\{k\}\-x^\{\*\}\_\{c,\\delta\}\\right\\rVert^\{2\}\\right\]\\leq\\frac\{\\alpha\\delta^\{2\}\}\{\\gamma\_\{c\}^\{2\}\}\.\(24\)We combine \([20](https://arxiv.org/html/2610.09120#S6.E20)\), \([24](https://arxiv.org/html/2610.09120#S6.E24)\), and \([28](https://arxiv.org/html/2610.09120#S9.E28)\) from Lemma[1](https://arxiv.org/html/2610.09120#Thmlemma1)in the Appendix to prove \([16](https://arxiv.org/html/2610.09120#S5.E16)\), withR=2​αγc2\+2rc2​\(1\+Lcγc\)2​‖xc∗−p‖2R=\\frac\{2\\alpha\}\{\\gamma\_\{c\}^\{2\}\}\+\\frac\{2\}\{r\_\{c\}^\{2\}\}\(1\+\\frac\{L\_\{c\}\}\{\\gamma\_\{c\}\}\)^\{2\}\\left\\lVert x\_\{c\}^\{\*\}\-p\\right\\rVert^\{2\}\. To establish \([17](https://arxiv.org/html/2610.09120#S5.E17)\), we apply Lemma[3](https://arxiv.org/html/2610.09120#Thmlemma3)in the Appendix to \([23](https://arxiv.org/html/2610.09120#S6.E23)\) and obtainC\>0C\>0such that the following estimate holds for allk∈ℕk\\in\\mathbb\{N\}andδ∈\(0,rc\)\\delta\\in\(0,r\_\{c\}\):

𝔼⁡\[‖xk−xc,δ∗‖2\]≤2​n2​C​𝒥2γc2​δ2​k\+α​δ2γc2\.\\mathbb\{E\}\\left\[\\left\\lVert x\_\{k\}\-x\_\{c,\\delta\}^\{\*\}\\right\\rVert^\{2\}\\right\]\\leq\\frac\{2n^\{2\}C\\mathcal\{J\}^\{2\}\}\{\\gamma\_\{c\}^\{2\}\\delta^\{2\}k\}\+\\frac\{\\alpha\\delta^\{2\}\}\{\\gamma\_\{c\}^\{2\}\}\.\(25\)We substitute \([25](https://arxiv.org/html/2610.09120#S6.E25)\) into \([20](https://arxiv.org/html/2610.09120#S6.E20)\) and apply Lemma[1](https://arxiv.org/html/2610.09120#Thmlemma1)from the Appendix to \([20](https://arxiv.org/html/2610.09120#S6.E20)\) and obtain \([17](https://arxiv.org/html/2610.09120#S5.E17)\), withC=max⁡\{q2q−1,γc2​rc2​⌈q⌉​maxx,y∈𝒳​‖x−y‖22​n2​𝒥2\}C=\\max\\left\\\{\\frac\{q^\{2\}\}\{q\-1\},\\frac\{\\gamma\_\{c\}^\{2\}r\_\{c\}^\{2\}\\lceil q\\rceil\\max\_\{x,y\\in\\mathcal\{X\}\}\\left\\lVert x\-y\\right\\rVert^\{2\}\}\{2n^\{2\}\\mathcal\{J\}^\{2\}\}\\right\\\},M=4​C​n2​𝒥2γc2M=\\frac\{4Cn^\{2\}\\mathcal\{J\}^\{2\}\}\{\\gamma\_\{c\}^\{2\}\}\.■\\blacksquare

### VI\-BProof of Theorem[2](https://arxiv.org/html/2610.09120#Thmthm2)

We start by proving the first part\. Sincex∗∈int​𝒳x^\{\*\}\\in\\text\{int\}~\\mathcal\{X\}, we know that𝒢⁡\(x∗\)=0\\mathcal\{G\}\(x^\{\*\}\)=0\. Letε=γL12​‖Γ‖\\varepsilon=\\frac\{\\gamma\}\{L\_\{12\}\\left\\lVert\\Gamma\\right\\rVert\}, and we define the mappingg:\(−ε,ε\)→𝒳g:\(\-\\varepsilon,\\varepsilon\)\\to\\mathcal\{X\}given byg⁡\(c\)=xc∗g\(c\)=x\_\{c\}^\{\*\}\. Sincex∗∈int​𝒳x^\{\*\}\\in\\text\{int\}~\\mathcal\{X\}and \([18](https://arxiv.org/html/2610.09120#S5.E18)\) holds forc∈\(−ε,ε\)c\\in\(\-\\varepsilon,\\varepsilon\), there exists a neighborhoodℰ⊂\(−ε,ε\)\\mathcal\{E\}\\subset\(\-\\varepsilon,\\varepsilon\)of 0 such thatg⁡\(ℰ\)⊂int​𝒳g\(\\mathcal\{E\}\)\\subset\\text\{int\}~\\mathcal\{X\}, and hence𝒢cdec​\(g⁡\(c\)\)=0\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(g\(c\)\)=0for allc∈ℰc\\in\\mathcal\{E\}\. If we consider somec1,c2∈ℰc\_\{1\},c\_\{2\}\\in\\mathcal\{E\}withc1≠c2c\_\{1\}\\neq c\_\{2\}, we have

𝒢⁡\(g⁡\(ci\)\)\+ci​\[Γ⊤​∇2J1​\(g⁡\(ci\)\)0\]=0,\\mathcal\{G\}\(g\(c\_\{i\}\)\)\+c\_\{i\}\\begin\{bmatrix\}\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(g\(c\_\{i\}\)\)\\\\ 0\\end\{bmatrix\}=0,\(26\)fori∈\{1,2\}i\\in\\\{1,2\\\}\. If we suppose thatg⁡\(c1\)=g⁡\(c2\)=x^g\(c\_\{1\}\)=g\(c\_\{2\}\)=\\hat\{x\}, we consider the equation \([26](https://arxiv.org/html/2610.09120#S6.E26)\) fori=1i=1,i=2i=2and subtract to obtain

\(c1−c2\)​\[Γ⊤​∇2J1​\(x^\)0\]=0\.\(c\_\{1\}\-c\_\{2\}\)\\begin\{bmatrix\}\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(\\hat\{x\}\)\\\\ 0\\end\{bmatrix\}=0\.\(27\)Sincec1−c2≠0c\_\{1\}\-c\_\{2\}\\neq 0, the equation \([27](https://arxiv.org/html/2610.09120#S6.E27)\) is only valid ifΓ⊤​∇2J1​\(x^\)=0\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(\\hat\{x\}\)=0\. This would imply that𝒢⁡\(x^\)=0\\mathcal\{G\}\(\\hat\{x\}\)=0, so by the uniqueness of the NE, we conclude thatx^=x∗\\hat\{x\}=x^\{\*\}\. However, we also assumed thatΓ⊤​∇2J1​\(x∗\)≠0\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x^\{\*\}\)\\neq 0, so we arrive at a contradiction\. Hence,ggis injective onℰ\\mathcal\{E\}, which proves the first part\. For the second part,Γ⊤​∇2J1​\(x∗\)=0\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x^\{\\ast\}\)=0implies𝒢cdec​\(x∗\)=𝒢⁡\(x∗\)\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(x^\{\\ast\}\)=\\mathcal\{G\}\(x^\{\\ast\}\)\. Sincex∗x^\{\\ast\}solves \([4](https://arxiv.org/html/2610.09120#S3.E4)\), it also solves \([14](https://arxiv.org/html/2610.09120#S4.E14)\)\. Strong monotonicity of𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}then yieldsxc∗=x∗x\_\{c\}^\{\\ast\}=x^\{\\ast\}\.■\\blacksquare

### VI\-CProof of Theorem[3](https://arxiv.org/html/2610.09120#Thmthm3)

Since𝒢\\mathcal\{G\}is strongly monotone, the implicit function theorem yields∂xc∗∂c\|c=0=−∇𝒢\(x∗\)−⁣⊤\[Γ⊤​∇2J1​\(x∗\)0\]\.\\left\.\\frac\{\\partial x\_\{c\}^\{\*\}\}\{\\partial c\}\\right\|\_\{c=0\}=\-\\nabla\\mathcal\{G\}\(x^\{\*\}\)^\{\-\\top\}\\begin\{bmatrix\}\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x^\{\*\}\)\\\\ 0\\end\{bmatrix\}\.Sincex∗∈int​𝒳x^\{\*\}\\in\\text\{int\}~\\mathcal\{X\}, also have∇2J2​\(x∗\)=0\\nabla\_\{2\}J\_\{2\}\(x^\{\*\}\)=0\. A straightforward application of chain rule reveals that the left hand side of \([19](https://arxiv.org/html/2610.09120#S5.E19)\) precisely equals−∂J2​\(xc∗\)∂c\|c=0\-\\frac\{\\partial J\_\{2\}\(x\_\{c\}^\{\*\}\)\}\{\\partial c\}\|\_\{c=0\}\. If∂J2​\(xc∗\)∂c\|c=0\>0\\frac\{\\partial J\_\{2\}\(x\_\{c\}^\{\*\}\)\}\{\\partial c\}\|\_\{c=0\}\>0, we can findε~∈\(0,ε\)\\widetilde\{\\varepsilon\}\\in\(0,\\varepsilon\)such that the result holds forℰ=\(−ε~,0\)\\mathcal\{E\}=\(\-\\widetilde\{\\varepsilon\},0\),whereε\\varepsilonis obtained from the proof of Theorem[2](https://arxiv.org/html/2610.09120#Thmthm2)\.Otherwise, we will haveℰ=\(0,ε~\)\\mathcal\{E\}=\(0,\\widetilde\{\\varepsilon\}\)\.■\\blacksquare

## VIINumerical Example

To illustrate our results, we apply them to a stylized two\-player resource allocation problem\. Consider two players allocating demand across two shared resources\. Playeriihas actionxi∈ℝ2x\_\{i\}\\in\\mathbb\{R\}^\{2\}, where thejj\-th component of their action specifies the amount of demand assigned to resourcejj\. The cost function of playeriiis expressed in the form

Ji​\(x\)=‖xi‖2\+xi⊤​x3−i\+qi⊤​xi\+λ​∑j=12\[xi​j−τi​j\]\+52,J\_\{i\}\(x\)=\\left\\lVert x\_\{i\}\\right\\rVert^\{2\}\+x\_\{i\}^\{\\top\}x\_\{3\-i\}\+q\_\{i\}^\{\\top\}x\_\{i\}\+\\lambda\\sum\_\{j=1\}^\{2\}\[x\_\{ij\}\-\\tau\_\{ij\}\]\_\{\+\}^\{\\frac\{5\}\{2\}\},where\[⋅\]\+:=max⁡\{0,⋅\}\[\\cdot\]\_\{\+\}:=\\max\\\{0,\\cdot\\\}and the first three terms model private allocation costs, cross\-player congestion, and linear allocation value, respectively\. The final term is a soft capacity penalty, whereτi​j\\tau\_\{ij\}is playerii’s reference allocation for resourcejj\. Here, we will useλ=0\.12\\lambda=0\.12,q1=\(−4,−5\),q2=\(−6,−4\),τ1=\(23,2\)q\_\{1\}=\(\-4,\-5\),q\_\{2\}=\(\-6,\-4\),\\tau\_\{1\}=\(\\frac\{2\}\{3\},2\),τ2=\(83,1\)\\tau\_\{2\}=\(\\frac\{8\}\{3\},1\), and𝒳1=𝒳2=\[0,5\]2\\mathcal\{X\}\_\{1\}=\\mathcal\{X\}\_\{2\}=\[0,5\]^\{2\}\. This example satisfies Assumption[1](https://arxiv.org/html/2610.09120#Thmassumption1)and falls outside the class of second\-order smoothness conditions required in\[[18](https://arxiv.org/html/2610.09120#bib.bib18)\]\.

To seek the Nash equilibriumx∗=\(\(2/3,2\),\(8/3,1\)\)x^\{\*\}=\(\(2/3,2\),\(8/3,1\)\), each player uses a learning algorithm based on bandit feedback\. Player 1 implements \([9](https://arxiv.org/html/2610.09120#S4.E9)\), while, at each stage, player 2 obtains noisy measurements ofμ1,k\\mu\_\{1,k\}with probability0\.750\.75, which are stored in a signalΘ1,k∈ℝ2\\Theta\_\{1,k\}\\in\\mathbb\{R\}^\{2\}that assumes the form given in \([8](https://arxiv.org/html/2610.09120#S4.E8)\)\. We haveΛk=bk​\(𝕀2\+Ξk\)\\Lambda\_\{k\}=b\_\{k\}\(\\mathbb\{I\}\_\{2\}\+\\Xi\_\{k\}\)wherebk∼Bernoulli​\(0\.75\)b\_\{k\}\\sim\\text\{Bernoulli\}\(0\.75\)and, for eachk∈ℕk\\in\\mathbb\{N\}, each entry of the random matrixΞk\\Xi\_\{k\}is sampled independently and uniformly on\[−0\.15,0\.15\]\[\-0\.15,0\.15\]\. The additive noise satisfieswk=0\.1​bk​zkw\_\{k\}=0\.1b\_\{k\}z\_\{k\}, where the components ofzkz\_\{k\}are independent standard Gaussian random variables truncated to\[−3,3\]\[\-3,3\]\. Player 2 implements the dynamics \([10](https://arxiv.org/html/2610.09120#S4.E10)\) withc=0\.8c=0\.8, and each player usesδ=0\.25\\delta=0\.25with step sizesηk=3​k−1\\eta\_\{k\}=\{3\}\{k^\{\-1\}\}\. It is verifiable that𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}is strongly monotone and the DNE is given by\(xc∗\)1≈\(0\.48,1\.44\)\(x\_\{c\}^\{\*\}\)\_\{1\}\\approx\(0\.48,1\.44\)and\(xc∗\)2≈\(2\.76,1\.26\)\(x\_\{c\}^\{\*\}\)\_\{2\}\\approx\(2\.76,1\.26\)\. SinceJ2​\(x∗\)−J2​\(xc∗\)≈1\.15J\_\{2\}\(x^\{\*\}\)\-J\_\{2\}\(x\_\{c\}^\{\*\}\)\\approx 1\.15, player 2 improves their steady state cost through deception\. The averaged trajectories ofJiJ\_\{i\}andxxtaken over 300 realizations are given in Figure[2](https://arxiv.org/html/2610.09120#S5.F2), which also illustrates how the parameterccaffects the steady\-state costs and equilibrium shift\.Figure[3](https://arxiv.org/html/2610.09120#S7.F3)shows that countermeasures that suppress the same\-round dither\-signal correlation, which include an induced dither\-signal delay, zero\-mean masking, and dither resetting, recover the nominal learning trajectories and converge to a neighborhood of the NE, while the undefended dynamics remain displaced\.

![Refer to caption](https://arxiv.org/html/2610.09120v1/dec_bandit_counter.png)Fig\. 3:Convergence of the action profile with deception countermeasures implemented at each stage\. One\-step delay: player 2 usesΘ1,k−1\\Theta\_\{1,k\-1\}during stagekk\. Zero\-mean mask: player 1 privately flips the sign of the dither with probability12\\frac\{1\}\{2\}after leakage\. Dither refresh: player 1 resamples the dither after leakage\.
## VIIIConclusion

We introduced a novel framework for deceptive bandit learning in strongly monotone games, demonstrating that noisy information correlated with an opponent’s exploration can induce an externality that steers the joint action profile toward a deceptive Nash equilibrium\. We then proved that the DBL dynamics converge to a𝒪⁡\(δ\)\\mathcal\{O\}\(\\delta\)RMS neighborhood of the DNE, establishing optimal rates under weaker regularity conditions than\[[18](https://arxiv.org/html/2610.09120#bib.bib18)\]and revealing a novel relaxation that also applies in the deception\-free setting\. Furthermore, we established geometric conditions under which the deception mechanism is guaranteed to shift the steady state and improve the deceiver’s long\-term cost/payoff\. Our results were illustrated in a two\-player resource allocation setting\. Future directions include extending the ideas to asynchronous games, studying the effect of the network topology, and investigating active countermeasures against deception\.

## References

- \[1\]A\. Flaxman, A\. Kalai, and H\. McMahan, “Online convex optimization in the bandit setting: Gradient descent without a gradient,” in*Proceedings of the Annual ACM\-SIAM Symposium on Discrete Algorithms*, 2005, pp\. 385–394\.
- \[2\]P\. Landgren, V\. Srivastava, and N\. E\. Leonard, “Distributed cooperative decision making in multi\-agent multi\-armed bandits,”*Automatica*, vol\. 125, p\. 109445, 2021\.
- \[3\]K\. Liu and Q\. Zhao, “Distributed learning in multi\-armed bandit with multiple players,”*IEEE transactions on signal processing*, vol\. 58, no\. 11, pp\. 5667–5681, 2010\.
- \[4\]S\. Shahrampour, A\. Rakhlin, and A\. Jadbabaie, “Multi\-armed bandits in multi\-agent networks,” in*2017 IEEE International Conference on Acoustics, Speech and Signal Processing \(ICASSP\)*\. IEEE, 2017, pp\. 2786–2790\.
- \[5\]J\. Zhu and J\. Liu, “Distributed multiarmed bandits,”*IEEE Transactions on Automatic Control*, vol\. 68, no\. 5, pp\. 3025–3040, 2023\.
- \[6\]A\. Sankararaman, A\. Ganesh, and S\. Shakkottai, “Social learning in multi agent multi armed bandits,”*Proceedings of the ACM on Measurement and Analysis of Computing Systems*, vol\. 3, no\. 3, pp\. 1–35, 2019\.
- \[7\]K\. Misra, E\. M\. Schwartz, and J\. Abernethy, “Dynamic online pricing with incomplete information using multiarmed bandit experiments,”*Marketing Science*, vol\. 38, no\. 2, pp\. 226–252, 2019\.
- \[8\]J\. W\. Mueller, V\. Syrgkanis, and M\. Taddy, “Low\-rank bandit methods for high\-dimensional dynamic pricing,”*Advances in Neural Information Processing Systems*, vol\. 32, 2019\.
- \[9\]J\. Spall, “Multivariate stochastic approximation using a simultaneous perturbation gradient approximation,”*IEEE Transactions on Automatic Control*, vol\. 37, no\. 3, pp\. 332–341, 1992\.
- \[10\]M\. L\. Littman, “Markov games as a framework for multi\-agent reinforcement learning,” in*Machine learning proceedings 1994*\. Elsevier, 1994, pp\. 157–163\.
- \[11\]D\. Malik*et al\.*, “Derivative\-free methods for policy optimization: Guarantees for linear quadratic systems,” in*The 22nd international conference on artificial intelligence and statistics*\. PMLR, 2019, pp\. 2916–2925\.
- \[12\]J\. R\. Marden, H\. P\. Young, G\. Arslan, and J\. S\. Shamma, “Payoff\-based dynamics for multiplayer weakly acyclic games,”*SIAM Journal on Control and Optimization*, vol\. 48, no\. 1, pp\. 373–396, 2009\.
- \[13\]T\. Tatarenko and M\. Kamgarpour, “Learning generalized Nash equilibria in a class of convex games,”*IEEE Transactions on Automatic Control*, vol\. 64, no\. 4, pp\. 1426–1439, 2018\.
- \[14\]Y\. Pang and G\. Hu, “Distributed Nash equilibrium seeking with limited cost function knowledge via a consensus\-based gradient\-free method,”*IEEE Transactions on Automatic Control*, vol\. 66, no\. 4, pp\. 1832–1839, 2020\.
- \[15\]K\. G\. Vamvoudakis*et al\.*, “Deception in game theory and control: A tutorial,” in*2025 American Control Conference \(ACC\)*\. IEEE, 2025, pp\. 2146–2163\.
- \[16\]M\. Ye, G\. Hu, L\. Xie, and S\. Xu, “Differentially private distributed Nash equilibrium seeking for aggregative games,”*IEEE Transactions on Automatic Control*, vol\. 67, no\. 5, pp\. 2451–2458, 2021\.
- \[17\]E\. Boursier and V\. Perchet, “Selfish robustness and equilibria in multi\-player bandits,” in*Conference on Learning Theory*\. PMLR, 2020, pp\. 530–581\.
- \[18\]D\. Drusvyatskiy, M\. Fazel, and L\. J\. Ratliff, “Improved rates for derivative free gradient play in strongly monotone games,” in*2022 IEEE 61st Conference on Decision and Control \(CDC\)*, 2022, pp\. 3403–3408\.
- \[19\]F\. Yao, Y\. Cheng, E\. Wei, and H\. Xu, “Single\-agent poisoning attacks suffice to ruin multi\-agent learning,” in*The Thirteenth International Conference on Learning Representations*, 2025\.
- \[20\]Y\. Wu, J\. McMahan, X\. Zhu, and Q\. Xie, “Reward poisoning attacks on offline multi\-agent reinforcement learning,” in*Proceedings of the AAAI conference on artificial intelligence*, vol\. 37, no\. 9, 2023, pp\. 10 426–10 434\.
- \[21\]A\. Gleave, M\. Dennis, C\. Wild, N\. Kant, S\. Levine, and S\. Russell, “Adversarial policies: Attacking deep reinforcement learning,”*arXiv preprint arXiv:1905\.10615*, 2019\.
- \[22\]M\. Tang, U\. Javed, X\. Chen, M\. Krstić, and J\. I\. Poveda, “Deception in Nash equilibrium seeking,”*IEEE Transactions on Automatic Control*, vol\. 70, no\. 12, pp\. 7984–7999, 2025\.
- \[23\]M\. Tang, M\. Krstic, and J\. Poveda, “Stochastic real\-time deception in Nash equilibrium seeking for games with quadratic payoffs,” in*7th Annual Learning for Dynamics & Control Conference*\. PMLR, 2025, pp\. 635–646\.
- \[24\]Y\.\-H\. Yan, P\. Zhao, and Z\.\-H\. Zhou, “Fast rates in time\-varying strongly monotone games,” in*International Conference on Machine Learning*\. PMLR, 2023, pp\. 39 138–39 164\.
- \[25\]M\. Bravo, D\. Leslie, and P\. Mertikopoulos, “Bandit learning in concave n\-person games,”*Advances in Neural Information Processing Systems*, vol\. 31, 2018\.
- \[26\]W\. Ba, T\. Lin, J\. Zhang, and Z\. Zhou, “Doubly optimal no\-regret online learning in strongly monotone games with bandit feedback,”*Operations Research*, vol\. 73, no\. 6, pp\. 3219–3244, 2025\.
- \[27\]M\. Jordan, T\. Lin, and Z\. Zhou, “Adaptive, doubly optimal no\-regret learning in strongly monotone and exp\-concave games with gradient feedback,”*Operations Research*, vol\. 73, no\. 3, pp\. 1675–1702, 2025\.
- \[28\]D\. Bergemann and S\. Morris, “Bayes correlated equilibrium and the comparison of information structures in games,”*Theoretical Economics*, vol\. 11, no\. 2, pp\. 487–522, 2016\.
- \[29\]E\. Solan and L\. Yariv, “Games with espionage,”*Games and Economic Behavior*, vol\. 47, no\. 1, pp\. 172–199, 2004\.
- \[30\]N\. Alon, Y\. Emek, M\. Feldman, and M\. Tennenholtz, “Adversarial leakage in games,”*SIAM Journal on Discrete Mathematics*, vol\. 27, no\. 1, pp\. 363–385, 2013\.
- \[31\]M\. S\. Alvim, K\. Chatzikokolakis, Y\. Kawamoto, and C\. Palamidessi, “Information leakage games,” in*International Conference on Decision and Game Theory for Security*\. Springer, 2017, pp\. 437–457\.
- \[32\]P\. Frihauf, M\. Krstic, and T\. Basar, “Nash equilibrium seeking in noncooperative games,”*IEEE Transactions on Automatic Control*, vol\. 57, no\. 5, pp\. 1192–1207, 2012\.
- \[33\]B\. Gao and L\. Pavel, “Bandit learning with regularized second\-order mirror descent,” in*2022 IEEE 61st Conference on Decision and Control \(CDC\)*, 2022, pp\. 5731–5738\.
- \[34\]J\. Perolat*et al\.*, “From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization,” in*ICML*\. PMLR, 2021, pp\. 8525–8535\.
- \[35\]B\. Polyak,*Introduction to Optimization*, ser\. Translations series in mathematics and engineering\. Optimization Software, Publications Division, 1987\.

## IXAppendix

Here we present several technical lemmas that are used to prove our main results\.

###### Lemma 1\.

Suppose𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}isγc\\gamma\_\{c\}\-strongly monotone, and letxc,δ∗x^\{\*\}\_\{c,\\delta\}denote a Nash equilibrium of\(𝒢cdec,𝒳1δ×𝒳2δc\)\(\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\},\\mathcal\{X\}\_\{1\}^\{\\delta\}\\times\\mathcal\{X\}\_\{2\}^\{\\delta\_\{c\}\}\), whereδ\\deltasatisfies \([15](https://arxiv.org/html/2610.09120#S5.E15)\)\. Then, the following holds

‖xc∗−xc,δ∗‖≤dc​\(1\+Lcγc\)​‖xc∗−p‖,\\left\\lVert x^\{\*\}\_\{c\}\-x^\{\*\}\_\{c,\\delta\}\\right\\rVert\\leq\{\\color\[rgb\]\{0,0,0\}d\_\{c\}\}\\left\(1\+\\frac\{L\_\{c\}\}\{\\gamma\_\{c\}\}\\right\)\\left\\lVert x\_\{c\}^\{\*\}\-p\\right\\rVert,\(28\)wheredc=max⁡\(δr1,δcr2\)d\_\{c\}=\\max\\left\(\\frac\{\\delta\}\{r\_\{1\}\},\\frac\{\\delta\_\{c\}\}\{r\_\{2\}\}\\right\),Lc:=\|c\|​‖Γ‖​L12\+L112\+L222L\_\{c\}:=\|c\|\\left\\lVert\\Gamma\\right\\rVert L\_\{12\}\+\\sqrt\{L\_\{11\}^\{2\}\+L\_\{22\}^\{2\}\}, andp=\(p1,p2\)p=\(p\_\{1\},p\_\{2\}\)\.

###### Proof\.

Define𝒳cδ:=𝒳1δ×𝒳2δc\\mathcal\{X\}^\{\\delta\}\_\{c\}:=\\mathcal\{X\}\_\{1\}^\{\\delta\}\\times\\mathcal\{X\}\_\{2\}^\{\\delta\_\{c\}\}, which is convex and compact\. Lettingp=\(p1,p2\)p=\(p\_\{1\},p\_\{2\}\), we define the following matrix and transformation:

𝒟:=\[\(1−δr1\)​𝕀n00\(1−δcr2\)​𝕀n\],T⁡\(x\)=𝒟⁡\(x−p\)\+p\.\\mathcal\{D\}:=\\begin\{bmatrix\}\\left\(1\-\\frac\{\\delta\}\{r\_\{1\}\}\\right\)\\mathbb\{I\}\_\{n\}&0\\\\ 0&\\left\(1\-\\frac\{\\delta\_\{c\}\}\{r\_\{2\}\}\\right\)\\mathbb\{I\}\_\{n\}\\end\{bmatrix\},~~~T\(x\)=\\mathcal\{D\}\(x\-p\)\+p\.Note that𝒳cδ=T⁡\(𝒳\)\\mathcal\{X\}\_\{c\}^\{\\delta\}=T\(\\mathcal\{X\}\)\. By the strong monotonicity of𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}, it also follows that the mappingx↦𝒢cdec​\(x\)\+𝒩𝒳cδ​\(x\)x\\mapsto\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(x\)\+\\mathcal\{N\}\_\{\\mathcal\{X\}^\{\\delta\}\_\{c\}\}\(x\)is alsoγc\\gamma\_\{c\}\-strongly monotone, where𝒩𝒳cδ​\(x\)\\mathcal\{N\}\_\{\\mathcal\{X\}^\{\\delta\}\_\{c\}\}\(x\)is the normal cone of𝒳cδ\\mathcal\{X\}^\{\\delta\}\_\{c\}at the pointxx\. We then obtain

γc​‖T⁡\(xc∗\)−xc,δ∗‖≤infv∈𝒢cdec​\(T⁡\(xc∗\)\)\+𝒩𝒳cδ​\(T⁡\(xc∗\)\)‖v‖\.\\gamma\_\{c\}\\left\\lVert T\(x\_\{c\}^\{\*\}\)\-x^\{\*\}\_\{c,\\delta\}\\right\\rVert\\leq\\inf\_\{v\\in\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(T\(x\_\{c\}^\{\*\}\)\)\+\\mathcal\{N\}\_\{\\mathcal\{X\}^\{\\delta\}\_\{c\}\}\(T\(x\_\{c\}^\{\*\}\)\)\}\\left\\lVert v\\right\\rVert\.Sincexc∗x^\{\*\}\_\{c\}is a DNE, we have that0∈𝒢cdec​\(xc∗\)\+𝒩𝒳​\(xc∗\)\.0\\in\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(x^\{\*\}\_\{c\}\)\+\\mathcal\{N\}\_\{\\mathcal\{X\}\}\(x^\{\*\}\_\{c\}\)\.Using the fact that𝒩𝒳cδ​\(T⁡\(xc∗\)\)=𝒩𝒳​\(xc∗\)\\mathcal\{N\}\_\{\\mathcal\{X\}^\{\\delta\}\_\{c\}\}\(T\(x\_\{c\}^\{\*\}\)\)=\\mathcal\{N\}\_\{\\mathcal\{X\}\}\(x\_\{c\}^\{\*\}\), we obtain

infv∈𝒢cdec​\(T⁡\(xc∗\)\)\+𝒩𝒳cδ​\(T⁡\(xc∗\)\)‖v‖\\displaystyle\\inf\_\{v\\in\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(T\(x\_\{c\}^\{\*\}\)\)\+\\mathcal\{N\}\_\{\\mathcal\{X\}^\{\\delta\}\_\{c\}\}\(T\(x\_\{c\}^\{\*\}\)\)\}\\left\\lVert v\\right\\rVert=infv∈𝒢cdec​\(T⁡\(xc∗\)\)\+𝒩𝒳​\(xc∗\)‖v‖\\displaystyle=\\inf\_\{v\\in\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(T\(x\_\{c\}^\{\*\}\)\)\+\\mathcal\{N\}\_\{\\mathcal\{X\}\}\(x^\{\*\}\_\{c\}\)\}\\left\\lVert v\\right\\rVert≤‖𝒢cdec​\(T⁡\(xc∗\)\)−𝒢cdec​\(xc∗\)‖\\displaystyle\\leq\\left\\lVert\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(T\(x\_\{c\}^\{\*\}\)\)\-\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\(x\_\{c\}^\{\*\}\)\\right\\rVert≤Lc​‖\(𝒟−𝕀2​n\)​\(xc∗−p\)‖\\displaystyle\\leq L\_\{c\}\\left\\lVert\(\\mathcal\{D\}\-\\mathbb\{I\}\_\{2n\}\)\(x\_\{c\}^\{\*\}\-p\)\\right\\rVert≤Lc​dc​‖xc∗−p‖,\\displaystyle\\leq L\_\{c\}\{\\color\[rgb\]\{0,0,0\}d\_\{c\}\}\\left\\lVert x\_\{c\}^\{\*\}\-p\\right\\rVert,whereLcL\_\{c\}is a Lipschitz constant of𝒢cdec\\mathcal\{G\}^\{\\text\{dec\}\}\_\{c\}\. By combining the above computations, we obtain

‖xc∗−xc,δ∗‖\\displaystyle\\left\\lVert x^\{\*\}\_\{c\}\-x^\{\*\}\_\{c,\\delta\}\\right\\rVert≤‖xc∗−T⁡\(xc∗\)‖\+‖T⁡\(xc∗\)−xc,δ∗‖\\displaystyle\\leq\\left\\lVert x\_\{c\}^\{\*\}\-T\(x\_\{c\}^\{\*\}\)\\right\\rVert\+\\left\\lVert T\(x\_\{c\}^\{\*\}\)\-x^\{\*\}\_\{c,\\delta\}\\right\\rVert≤dc​\(1\+Lcγc\)​‖xc∗−p‖,\\displaystyle\\leq\{\\color\[rgb\]\{0,0,0\}d\_\{c\}\}\\left\(1\+\\frac\{L\_\{c\}\}\{\\gamma\_\{c\}\}\\right\)\\left\\lVert x\_\{c\}^\{\*\}\-p\\right\\rVert,as desired\. ∎

###### Lemma 2\.

In \([11](https://arxiv.org/html/2610.09120#S4.E11)\), for eachk∈ℕk\\in\\mathbb\{N\}, the following estimates hold almost surely:

‖β1,kδ‖\\displaystyle\\left\\lVert\\beta\_\{1,k\}^\{\\delta\}\\right\\rVert≤δ⁡\(L11\+\|c\|​Λ¯​L12\)​\(2\+\|c\|​\(Λ¯\+w¯\)\)\\displaystyle\\leq\\delta\(L\_\{11\}\+\|c\|\\bar\{\\Lambda\}L\_\{12\}\)\(2\+\|c\|\(\\bar\{\\Lambda\}\+\\bar\{w\}\)\)\(29a\)‖β2,kδ‖\\displaystyle\\left\\lVert\\beta\_\{2,k\}^\{\\delta\}\\right\\rVert≤δ​L22​\(2\+\|c\|​\(Λ¯\+w¯\)\)\.\\displaystyle\\leq\\delta L\_\{22\}\(2\+\|c\|\(\\bar\{\\Lambda\}\+\\bar\{w\}\)\)\.\(29b\)

###### Proof\.

Givenk∈ℕk\\in\\mathbb\{N\}, we recall that

x¯k=\[x1,k\+δ​μ1,kx2,k\+δ​μ2,k\+c​δ​\(Λk​μ1,k\+wk\)\]\.\\bar\{x\}\_\{k\}=\\begin\{bmatrix\}x\_\{1,k\}\+\\delta\\mu\_\{1,k\}\\\\ x\_\{2,k\}\+\\delta\\mu\_\{2,k\}\+c\\delta\(\\Lambda\_\{k\}\\mu\_\{1,k\}\+w\_\{k\}\)\\end\{bmatrix\}\.\(30\)Sincekkwill remain fixed, we drop it from the subscripts for notational convenience\. By Stokes’ theorem:

𝔼k​\[nδ​J1​\(x¯\)​μ1\]\\displaystyle\\mathbb\{E\}\_\{k\}\\left\[\\frac\{n\}\{\\delta\}J\_\{1\}\(\\bar\{x\}\)\\mu\_\{1\}\\right\]=𝔼kμ1∼B,μ2∼S​\[∇1J1​\(x¯\)\+c​Λ⊤​∇2J1​\(x¯\)\]\\displaystyle=\\mathbb\{E\}\_\{k\}^\{\\mu\_\{1\}\\sim B,\\mu\_\{2\}\\sim S\}\\left\[\\nabla\_\{1\}J\_\{1\}\(\\bar\{x\}\)\+c\\Lambda^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(\\bar\{x\}\)\\right\]𝔼k​\[nδ​J2​\(x¯\)​μ2\]\\displaystyle\\mathbb\{E\}\_\{k\}\\left\[\\frac\{n\}\{\\delta\}J\_\{2\}\(\\bar\{x\}\)\\mu\_\{2\}\\right\]=𝔼kμ1∼S,μ2∼B​\[∇2J2​\(x¯\)\],\\displaystyle=\\mathbb\{E\}\_\{k\}^\{\\mu\_\{1\}\\sim S,\\mu\_\{2\}\\sim B\}\\left\[\\nabla\_\{2\}J\_\{2\}\(\\bar\{x\}\)\\right\],whereSSandBBare uniform distributions over𝕊n\\mathbb\{S\}^\{n\}and𝔹n\\mathbb\{B\}^\{n\}, respectively\. Since𝔼k​\[Λ\]=Γ\\mathbb\{E\}\_\{k\}\[\\Lambda\]=\\Gamma, we can continue from \([11](https://arxiv.org/html/2610.09120#S4.E11)\) to obtain

‖β1δ‖\\displaystyle\\left\\lVert\\beta\_\{1\}^\{\\delta\}\\right\\rVert≤\|𝔼kμ1∼B,μ2∼S​\[∇1J1​\(x¯\)\+c​Λ⊤​∇2J1​\(x¯\)\]\\displaystyle\\leq\\big\\\|\\mathbb\{E\}\_\{k\}^\{\\mu\_\{1\}\\sim B,\\mu\_\{2\}\\sim S\}\\left\[\\nabla\_\{1\}J\_\{1\}\(\\bar\{x\}\)\+c\\Lambda^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(\\bar\{x\}\)\\right\]−∇1J1\(x\)−cΓ⊤∇2J1\(x\)∥\\displaystyle~~~\-\\nabla\_\{1\}J\_\{1\}\(x\)\-c\\Gamma^\{\\top\}\\nabla\_\{2\}J\_\{1\}\(x\)\\big\\\|≤𝔼kμ1∼B,μ2∼S\[‖∇1J1\(x¯\)−∇1J1\(x\)‖\\displaystyle\\leq\\mathbb\{E\}\_\{k\}^\{\\mu\_\{1\}\\sim B,\\mu\_\{2\}\\sim S\}\\big\[\\left\\lVert\\nabla\_\{1\}J\_\{1\}\(\\bar\{x\}\)\-\\nabla\_\{1\}J\_\{1\}\(x\)\\right\\rVert\+‖cΛ⊤\(∇2J1\(x¯\)−∇2J1\(x\)\)‖\]\\displaystyle~~~\+\\left\\lVert c\\Lambda^\{\\top\}\(\\nabla\_\{2\}J\_\{1\}\(\\bar\{x\}\)\-\\nabla\_\{2\}J\_\{1\}\(x\)\)\\right\\rVert\\big\]≤𝔼kμ1∼B,μ2∼S​\[\(L11\+\|c\|​‖Λ‖​L12\)​‖x¯−x‖\],\\displaystyle\\leq\\mathbb\{E\}\_\{k\}^\{\\mu\_\{1\}\\sim B,\\mu\_\{2\}\\sim S\}\\left\[\\left\(L\_\{11\}\+\|c\|\\left\\lVert\\Lambda\\right\\rVert L\_\{12\}\\right\)\\left\\lVert\\bar\{x\}\-x\\right\\rVert\\right\],and

‖β2δ‖\\displaystyle\\left\\lVert\\beta\_\{2\}^\{\\delta\}\\right\\rVert≤𝔼kμ1∼S,μ2∼B​\[‖∇2J2​\(x¯\)−∇2J2​\(x\)‖\]\\displaystyle\\leq\\mathbb\{E\}\_\{k\}^\{\\mu\_\{1\}\\sim S,\\mu\_\{2\}\\sim B\}\\left\[\\left\\lVert\\nabla\_\{2\}J\_\{2\}\(\\bar\{x\}\)\-\\nabla\_\{2\}J\_\{2\}\(x\)\\right\\rVert\\right\]≤𝔼kμ1∼S,μ2∼B​\[L22​‖x¯−x‖\]\.\\displaystyle\\leq\\mathbb\{E\}\_\{k\}^\{\\mu\_\{1\}\\sim S,\\mu\_\{2\}\\sim B\}\\left\[L\_\{22\}\\left\\lVert\\bar\{x\}\-x\\right\\rVert\\right\]\.The result is obtained by substituting \([30](https://arxiv.org/html/2610.09120#S9.E30)\) into the above expressions and using the facts that‖μi‖≤1\\left\\lVert\\mu\_\{i\}\\right\\rVert\\leq 1and‖Λ‖≤Λ¯\\left\\lVert\\Lambda\\right\\rVert\\leq\\bar\{\\Lambda\}almost surely\. ∎

###### Lemma 3\.

Consider a nonnegative sequence\{Vk\}k=1∞\\\{V\_\{k\}\\\}\_\{k=1\}^\{\\infty\}satisfyingVk\+1≤\(1−ak\)​Vk\+A​ak2\+B​ak,V\_\{k\+1\}\\leq\(1\-a\_\{k\}\)V\_\{k\}\+Aa\_\{k\}^\{2\}\+Ba\_\{k\},whereak=qka\_\{k\}=\\frac\{q\}\{k\}for someq\>1q\>1, andA,B\>0A,B\>0\. Then, there existsC\>0C\>0such thatVk≤C​Ak\+BV\_\{k\}\\leq\\frac\{CA\}\{k\}\+Bfor allk∈ℕk\\in\\mathbb\{N\}\.

###### Proof\.

The desired bound clearly holds fork≤⌈q⌉k\\leq\\lceil q\\rceil, since we can always chooseC≥1A​maxk≤⌈q⌉​k​VkC\\geq\\frac\{1\}\{A\}\\max\_\{k\\leq\\lceil q\\rceil\}kV\_\{k\}, so suppose it holds for somek≥⌈q⌉k\\geq\\lceil q\\rceil\. By the inductive hypothesis, we haveVk\+1≤C​A​\(k−q\)\+A​q2k2\+BV\_\{k\+1\}\\leq\\frac\{CA\(k\-q\)\+Aq^\{2\}\}\{k^\{2\}\}\+B\. It suffices to showC​A​\(k−q\)\+A​q2k2≤C​Ak\+1,\\frac\{CA\(k\-q\)\+Aq^\{2\}\}\{k^\{2\}\}\\leq\\frac\{CA\}\{k\+1\},which can be equivalently rearranged intok⁡\(C​A​\(1−q\)\+A​q2\)−C​A​q\+A​q2≤0\.k\\left\(CA\(1\-q\)\+Aq^\{2\}\\right\)\-CAq\+Aq^\{2\}\\leq 0\.Direct computation shows that this holds for allk∈ℕk\\in\\mathbb\{N\}whenC≥q2q−1C\\geq\\frac\{q^\{2\}\}\{q\-1\}\. We setC≥max⁡\{q2q−1,1A​maxk≤⌈q⌉​k​Vk\}C\\geq\\max\\left\\\{\\frac\{q^\{2\}\}\{q\-1\},\\frac\{1\}\{A\}\\max\_\{k\\leq\\lceil q\\rceil\}kV\_\{k\}\\right\\\}to conclude\. ∎