Multi-agent bandits

Mathematical contract and proof

The actual joint draw is uniform on the product of nonempty candidate sets. Restriction-event counting gives Pr(all draw_i in B_i)=product_i |C_i intersect B_i|/|C_i|. The transition keeps old fixed arms and fixes a new player exactly on collision-free feedback.

If the common candidate set has n arms and player i is unfixed, at most n-1 fixed labels are occupied. Cardinality produces an unused arm. A specific isolated-draw event yields actual fixation probability at least(1/n)((n-1)/n)^(n-1).

For n>=2, m=n-1 and x=m/(m+1) satisfy m log x>=-1 by1-1/x<=log x. Thus x^m>=exp(-1)>=1/4; n=1 is handled directly. This proves the actual statewise hazard1/(4n).

Fixed players never return to unfixed. The actual PMF bind recursion gives Pr(i unfixed at t)<=(1-1/(4n))^t. Finite geometric summation yields sum_(t<T)Pr(i unfixed)<=4n.

For U(s)=number of unfixed players, finite sum interchange proves sum_s p_t(s)U(s)=sum_i Pr(i unfixed). Summing gives total finite expected occupation<=4n². No independence of players waiting times, expected completion time, or full regret statement is inferred.

The actual real deficit is sum of means over S minus the sum of means of collision-free played actions. A fixed player hit by a collision must be hit by an unfixed player. Choosing a partner gives an injection, because two fixed players cannot share an arm. Thus at most U fixed players are hit, and at most2U reference arms are missing from successful fixed actions. Means in[0,1] give the actual per-round deficit<=2U.

All successful actions are distinct and, on the actual state/draw support, belong to S. Their sum is at most the S comparator, proving nonnegative supported deficit. Consequently the finite ENNReal expectation equals the ordinary real PMF-weighted deficit sum after toReal; no negative supported values are discarded. Summing the2U charge against the same constructed state/draw law and consuming occupation<=4n^2 gives actual finite expected coordination mean deficit<=8n^2. The integrated exploration producer and learned-kernel factorization now supply the actual true top-n interface.

Actual iid uniform exploration gives q=(1/k)(1-1/k)^(n-1)>=1/(4k). Conditioning on the reward-independent action schedule fixes collision-free sample times; bounded independent reward MGFs and the count PGF yield P(|mean-mu|>=epsilon/2)<=2exp(-S epsilon^2/(16k)). The all-player/arm union pays delta/2.

Collision-frequency concentration gives |pHat-p|<=1/(10k). With b=1-1/k and q=b^(n-1)>=1/4, real-exponent bounds put the inverse estimate in[n-2/5,n+2/5], strictly within its rounding cell. The repaired all-player log(4k/delta) pays the remaining delta/2.

Finite sorting with a fixed tie order constructs local candidates. The numeric nth-next boundary gap plus strict epsilon/2 errors preserves selected/outside separation, so all actual local population estimates and top sets are correct on an event G with probability>=1-delta; no correct-set oracle is assumed.

The measurable learned path kernel is total on every exploration history. On G it factors to independent common-top-set draws. Actual path/state marginals transfer the8n^2 coordination bound. The all-history comparator and exact phase split then give E[R_H]<=min(nH,n*min(H,S)+8n^2+delta*nH), including H<S and H=0.

Fresh continuation reward arrays extend the same learned law. Finite schedule first moments, signed integrability and Fubini give unconditional expected realized=pseudo regret. Measurable chronological feedback pulls back the exact observed reward sum; its pushforward law supplies the visible regret endpoint. Conditioning this identity on reward-dependent G is not asserted.

The genuine noisy n2/k3 canary proves actual means/gap, source-good-event probability>=3/4 and all-horizon visible bound. A two-round collide-then-separate path has conditional mass1/16 and joint/full reward-law mass>=3/64, with mean coordination charge5/4. This is symbolic probability verification, not a Monte Carlo experiment.