Paper deep dive
Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness
Chenyu Gan
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 10/6/2026, 9:58:36 AM
Summary
This paper presents a constructive communication and synchronization protocol for adversarial multiplayer bandits with K arms and m labeled players, operating without collision information, shared randomness, or external communication channels. The authors design a Monte Carlo public constructor that publishes tables before the adversary selects reward sequences. The protocol achieves a square-root regret bound of O(K^{5/2} sqrt(T) log^2(T)) with high probability, improving upon previous bounds that had higher exponents of T. The method uses positive reward observations to synchronize players and establish a common learning schedule, charging communication delays to the support of positive rewards.
Entities (8)
Relation Signals (6)
Chenyu Gan → affiliatedwith → Tsinghua University
confidence 99% · Chenyu Gan Affiliation: Tsinghua University
Adversarial Multiplayer Bandits → hasconstraint → Collision Information
confidence 96% · without collision information, shared randomness, or an external communication channel.
Adversarial Multiplayer Bandits → hasconstraint → Shared Randomness
confidence 96% · without collision information, shared randomness, or an external communication channel.
Monte Carlo Public Constructor → achieves → Regret Bound
confidence 95% · We design a constructive communication and synchronization protocol with a Monte Carlo public constructor... its fixed published output satisfies R_T ≤ C K^{5/2} sqrt(T) log^2(2Km(T+1))
Bubeck, Li, Peres, and Sellke → studied → Adversarial Multiplayer Bandits
confidence 92% · this is the loss model without collision information studied by Bubeck, Li, Peres, and Sellke [9].
Regret Bound → improvesupon → Bubeck, Li, Peres, and Sellke
confidence 90% · For the main bound... our bound improves the exponent of T from 1-1/(2m) to 1/2... This disproves the first conjecture in [9, Section 2.5]
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study adversarial multiplayer bandits with $K$ arms and $2\le m<K$ labeled players, without collision information, shared randomness, or an external communication channel. We design a constructive communication and synchronization protocol with a Monte Carlo public constructor. With probability at least $1-CN^{-32}$ over preprocessing, where $N=2Km(T+1)$, its fixed published output satisfies \[ R_T\le C K^{5/2}\sqrt T\log^2(2Km(T+1)) \] simultaneously for every oblivious reward sequence chosen after preprocessing. Here $R_T$ is expected regret over the players' private execution randomness. Positive reward observations establish a common learning schedule and synchronize players before learning begins. The cost of delayed communication is charged to the support of positive rewards, ensuring that periods with little useful feedback incur only limited regret. A slow--fast learning procedure then maintains valid reward estimates while assignments and scores are exchanged.
Tags
Links
- Source: https://arxiv.org/abs/2610.05688v1
- Canonical: https://arxiv.org/abs/2610.05688v1
Trouble viewing inline? Open PDF directly →
Full Text
262,519 characters extracted from source content.
Expand or collapse full text
Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness Chenyu Gan Affiliation: Tsinghua University Abstract We study adversarial multiplayer bandits with K arms and 2≤m<K2≤ m<K labeled players, without collision information, shared randomness, or an external communication channel. We design a constructive communication and synchronization protocol with a Monte Carlo public constructor. With probability at least 1−CN−321-CN^-32 over preprocessing, where N=2Km(T+1)N=2Km(T+1), its fixed published output satisfies RT≤CK5/2Tlog2(2Km(T+1))R_T≤ CK^5/2 T ^2(2Km(T+1)) simultaneously for every oblivious reward sequence chosen after preprocessing. Here RTR_T is expected regret over the players’ private execution randomness. Positive reward observations establish a common learning schedule and synchronize players before learning begins. The cost of delayed communication is charged to the support of positive rewards, ensuring that periods with little useful feedback incur only limited regret. A slow–fast learning procedure then maintains valid reward estimates while assignments and scores are exchanged. Contents 1 Introduction 2 Related work 3 The algorithm in brief 4 Initialization 5 The slow–fast learner 6 Assignment and score communication 7 Scheduling and local implementation 8 Proof of the main theorem 9 Finite computation and sampling A Exceptional executions B Public construction and bootstrap communication References 1 Introduction In a multiplayer bandit problem, several players choose arms at the same time and see only their own rewards. If two players choose the same arm, both receive reward zero. A player who observes zero cannot tell whether the arm had zero reward or a collision occurred. Thus the same observations must be used for learning and coordination. We study the adversarial model in which the players have neither collision information nor shared randomness. We give a constructive strategy with regret Om,K(Tlog2(T+1))O_m,K( T ^2(T+1)) for fixed m,Km,K. The players establish a common learning schedule using only their private randomness and ordinary reward observations, then learn while communicating assignment updates. 1.1 Model and result Let 2≤m<K2≤ m<K and T≥1T≥ 1 be integers. Write [q]=1,…,q[q]=\1,…,q\ for a positive integer q. There are m players with distinct labels in 0,…,m−1\0,…,m-1\ and K arms. The players know K,m,TK,m,T and have a common clock. Before any private random choices, an oblivious adversary fixes rewards rt(a)∈[0,1]r_t(a)∈[0,1] for every t∈[T]t∈[T] and a∈[K]a∈[K]. Player i chooses Ai,t∈[K]A_i,t∈[K] and observes only Yi,t=rt(Ai,t)Aj,t≠Ai,t for every j≠i.Y_i,t=r_t(A_i,t)1\A_j,t≠ A_i,t for every j≠ i\. (1) Here E1\E\ equals one when E holds and zero otherwise. An action may depend on the player’s label, the time, its previous actions and observations, and its private random variables. The private randomness of different players is initially independent. There is no additional communication channel and no initially common random seed. The constructive model also permits public preprocessing: a Monte Carlo constructor samples finite tables depending only on K,m,TK,m,T, then publishes all of them before the adversary chooses the reward matrix. No preprocessing randomness remains secret. The execution randomness of the players is independent of preprocessing and initially independent across players. Regret below is conditional on a fixed published output. Fixing a successful output instead gives deterministic tables in the original model. For x∈ℝKx ^K and S⊆[K]S [K], put x(S)=∑a∈Sxax(S)= _a∈ Sx_a, and let =S⊆[K]:|S|=mS=\S [K]:|S|=m\. Identify rtr_t with its vector of arm rewards. Expected regret is RT=max∑t=1TS∈rt(S)−∑t=1T∑i=0m−1Yi,t.R_T= _S _t=1^Tr_t(S)-E _t=1^T _i=0^m-1Y_i,t. (2) The expectation is over the players’ private randomness. Under the substitution ℓt(a)=1−rt(a) _t(a)=1-r_t(a), this is the loss model without collision information studied by Bubeck, Li, Peres, and Sellke [9]. For the main bound, set N=2Km(T+1),Λ=logN.N=2Km(T+1), = N. Here N is a convenient size parameter and Λ its logarithm. Constants denoted by c,Cc,C are positive and universal, and their values may change between appearances. The notation x≲yx y means x≤Cyx≤ Cy, and x≍yx y means both inequalities. In particular, no dependence on K,m,TK,m,T is hidden in these constants. Theorem 1 (Constructive regret bound). For every 2≤m<K2≤ m<K and T≥1T≥ 1, there is a Monte Carlo public constructor and a finite-arithmetic private-randomness strategy in model (1). With probability at least 1−CN−321-CN^-32 over preprocessing, its fixed published output satisfies, simultaneously for all oblivious reward matrices, RT≲K5/2TΛ2.R_T K^5/2 T ^2. (3) The adversary may select its matrix after inspecting that output. The public description has O(N4logN)O(N^4 N) bits and setup takes O~(N4) O(N^4) bit operations. Total online bootstrap decoding uses O~(N5/2) O(N^5/2) bit operations; the remaining learner also has polynomial bit complexity. For m=Km=K, player i always choosing arm i+1i+1 gives zero regret. The case m=1m=1 is the ordinary adversarial bandit problem and requires no communication. Comparison with the previous bound. For oblivious adversarial multiplayer bandits with neither collision information nor shared randomness, the only previously known general sublinear upper bound is that of Bubeck et al. [9, Theorem 21]: O~(mK3/2T1−1/(2m)) O(mK^3/2T^1-1/(2m)). For fixed m,Km,K, our bound improves the exponent of T from 1−1/(2m)1-1/(2m) to 1/21/2, matching the standard Ω(T) ( T) adversarial-bandit lower bound up to logarithmic factors. In particular, for m=2m=2 and fixed K≥3K≥ 3, we obtain OK(Tlog2(T+1))=o(T2/3)O_K( T ^2(T+1))=o(T^2/3). This disproves the first conjecture in [9, Section 2.5] that the two-player regret in this setting is Ω(T2/3) (T^2/3). Theorem 1 has a successful public output for each K,m,TK,m,T; fixing it before rewards are chosen gives deterministic tables visible to the adversary, while the players use only independent private randomness during execution. 1.2 Positive support and regret A positive reward proves that the observed arm had no collision: Yi,t>0⟹Aj,t≠Ai,t(j≠i).Y_i,t>0 A_j,t≠ A_i,t (j≠ i). (4) The communication protocol uses this implication to reject incorrect messages. Its duration may be large in calendar time. To measure the relevant delay, define the support at time t and its cumulative value by gt=∑a=1Krt(a)>0,G(t)=∑u=1tgu.g_t= _a=1^K1\r_t(a)>0\, G(t)= _u=1^tg_u. (5) Since rt(S)≤gtr_t(S)≤ g_t, the comparator earns at most the positive support on any interval. We therefore charge communication delay to increments of G. After rewards are rounded, the same notation refers to the rounded rewards. 1.3 Why communication is possible in this model There are two information problems. First, the receiver cannot identify a collision from a zero reward. The usual binary protocol “collide for zero, avoid for one” is therefore not a reliable bit channel: the second action also produces zero whenever the underlying reward is zero. In particular, an all-zero reward interval carries no observable message. We assume neither a positive lower bound on rewards nor a bound on the length of an all-zero interval. Positive observations still give one-sided information. If a receiver plays arm a and receives a positive reward, every candidate message that would have caused a collision on a is false. A zero observation rejects no candidate. Repeated positive observations can therefore remove false messages. The arm arrays also ensure that the actions of the other players do not remove all such observations. Second, the players initially have no common random row for arm choices, codes, recording decisions, or assignment updates. The protocol first communicates the root player’s private row index by means of deterministic public arrays and independent private column choices. Only then does it use the selected learning row. 1.4 Organization. Section 3 outlines the protocol and analysis. Section 4 establishes a shared public row and bounds the cost of initialization. Section 5 develops the slow–fast learner and proves its regret bound. Sections 6 and 7 specify communication, local updates, and scheduling, and bound the cost of delayed messages and interruptions. Section 8 combines these bounds and transfers the product-stream analysis to the published table. Section 9 gives finite samplers and computational bounds. Appendix A analyzes exceptional executions; Appendix B constructs the public table and proves its uniform and bootstrap communication guarantees. Acknowledgement of AI use. The author used OpenAI’s GPT-6-astra to assist in developing the public-table construction and protocol design, and OpenAI’s GPT-6-sol to assist in drafting and revising proofs. The author verified the correctness and originality of all content, including references. 2 Related work Stochastic rewards. Anantharam, Varaiya, and Walrand [2] studied the stochastic bandit problem with multiple plays under centralized control. For decentralized players whose simultaneous choices can collide, Liu and Zhao [15] established logarithmic regret bounds; subsequent algorithms include the musical-chairs approach of Rosenski, Shamir, and Szlak [17]. Bubeck and Budzinski [8] gave an O(TlogT)O( T T) regret strategy for two players and three arms with shared randomness and no communication that avoids collisions with high probability. Bubeck, Budzinski, and Sellke [7] extended the high-probability collision-free guarantee and O~(T) O( T) regret to arbitrary numbers of players and arms, again using shared randomness. Bonnefoi et al. [4] introduced the setting in which players observe rewards but cannot distinguish a collision from a zero reward, and Besson and Kaufmann [3] also studied this feedback model. Lugosi and Mehrabian [16] gave the first regret guarantees without collision information or shared randomness: an instance-dependent logarithmic bound and, when a positive lower bound on the mean of the m-th best arm is known, a gap-free square-root-type bound. Boursier and Perchet [6] obtained an instance-dependent bound in the no-collision-information setting by communicating through deliberate collisions, assuming a known positive lower bound on every arm mean. Shi, Xiong, Shen, and Yang [19] used error-correcting codes for this communication. Huang, Combes, and Trinh [14] gave an instance-dependent algorithm that does not require a lower bound on the smallest arm mean. Adversarial rewards. Alatur, Levy, and Krause [1] gave the first decentralized adversarial multiplayer bandit algorithm with sublinear regret, obtaining a O~(T2/3) O(T^2/3) bound with collision information. Bubeck, Li, Peres, and Sellke [9] obtained a O~(T) O( T) bound for two players with collision information. Without collision information or shared randomness, they proved O~(KT3/4) O(KT^3/4) regret for two players and O~(mK3/2T1−1/(2m)) O(mK^3/2T^1-1/(2m)) for m players, against an oblivious adversary. They also showed that an adaptive adversary can force linear regret without shared randomness. Shi and Shen [18] studied the no-collision-information model through an attackability parameter and proved sublinear regret under conditions on that parameter using coded collision communication. 3 The algorithm in brief The players must learn which arms reward them while keeping their choices collision-free. Following the slow–fast approach of Bubeck et al. [9], one player acts as a coordinator and can change arms frequently; the other m−1m-1 players keep assignments long enough to communicate observations. The rule for choosing the coordinator’s arm is deliberately biased: choosing uniformly can make a promising arm hard to observe once the other arms have been assigned. Section 5 gives the rule and its regret analysis. Messages can take several rounds. The players therefore record a small sample of observations in a way that has the same learning law during ordinary play, assignment delivery, and score collection. A player can save an observation before learning its assignment and decide later whether it belongs in the sample. If a new assignment is proposed while scores are being collected, the next assignment must account for that proposal; simply restarting from the current learning weights would lose information about why collection began. The recording and communication rules appear in Sections 6 and 7. The delay costs regret only when positive rewards were available. This lets the proof charge communication to the number of arms with positive rewards rather than to calendar time. The main theorem combines this charge with the learner’s regret bound in Section 8. The players begin without shared random bits. Before play, a constructor publishes a table of independent control rows. The coordinator privately selects one row and communicates its index during initialization. On a successful initialization all players use that row; failures are paid for in expected regret. The analysis first studies an independent random row and then shows that a suitable fixed published table works for every oblivious reward sequence chosen after publication. The initialization and public-table arguments are in Section 4 and Appendix B. Figure 1 shows the physical workflow. Once, before play. Algorithm 10 publishes the table. The coordinator chooses a row; followers draw private keys. Each round. Every player runs Algorithm 8. Before arm choice. The active coordinator calls StartRound in Algorithm 7. On a new assignment, Algorithm 9 samples the follower arms. Inactive or reserved round. Algorithm 12 uses a bootstrap arm to forward the row index. Play and observe. Active, nonreserved round. Algorithm 5 chooses the arm; Algorithm 4 sends a message when needed. Play and observe. After a learning-round observation. Algorithm 6 records DATA; Algorithm 4 decodes when needed. Algorithm 8 applies messages and receipts; the coordinator calls FinishRound in Algorithm 7. Only at a complete bootstrap-block boundary. Algorithm 12 calls Algorithm 11 if row digits or keys are still missing. Algorithm 1 checks activation while inactive. On other rounds, skip this block. Advance to the next round; stop after round T. Figure 1: Physical workflow. The reference correction (Algorithm 2) and logical learner (Algorithm 3) are only used for analysis, so they are not included. 4 Initialization Initialization has two purposes: establish a common table row and ensure that every follower is active before the first learning assignment. This section bounds its cost by positive reward support; the bootstrap communication rules are in Appendix B. We use the per-round support gtg_t and cumulative support G(t)G(t) defined in (5). The public table has M=N2M=N^2 rows. For row j, write Cj,tC_j,t for its reserved-round indicator at time t and RjR_j for its independent learning/control symbols. Let CAC_A be a sufficiently large universal constant, whose required size is fixed in the proof of Lemma 29, and set Akey:=⌈CAN⌉A_ key:= C_AN . This is the authentication-key alphabet size. After publication, each follower draws an independent key Ui∼Unif([Akey])U_i ([A_ key]), and the root independently draws J∼Unif([M])J ([M]). The selected learning/control row is RJR_J. The uniform draws in the algorithms below and in Appendix B specify the exact distributions used in the proofs. Their finite implementation uses the following bounded sampler. Set acap:=⌈45log2N⌉.a_ cap:= 45 _2N . (6) For a set S of size q>1q>1, BUnif(S)BUnif(S) makes at most acapa_ cap independent attempts. In each attempt it draws ⌈log2q⌉ _2q fair bits, interprets them as X∈0,…,2⌈log2q⌉−1X∈\0,…,2 _2q -1\, and accepts the (X+1)(X+1)-th element of S if X<qX<q. For q=1q=1 it returns the sole element without drawing bits. If all attempts are rejected, it reports exhaustion; a private call returns the first element of S, whereas the public constructor publishes the fixed-arm fallback flag and stops. All calls use fresh independent bits. The root index and follower keys, as well as the uniform choices during bootstrap, are implemented by these calls. Each call is coupled to its exact-uniform counterpart by the same rejection stream; their outputs agree unless the cap is exhausted. The finite public constructor obtains a Bernoulli variable with rational parameter r/sr/s by testing whether BUnif([s])≤rBUnif([s])≤ r; it generates permutations by bounded Fisher–Yates exchanges [10]. 4.1 Activation and launch Let C0C_0 be a sufficiently large universal constant, whose required size is fixed in the proof of Lemma 29. Set n:=⌈C03KT⌉,n:= C_0^3 KT , the number of rounds in one bootstrap block. For each complete block b, write Ib:=(b−1)n+1,…,bn.I_b:=\(b-1)n+1,…,bn\. (7) Let ℒi,b⊆IbL_i,b I_b be player i’s listening positions, defined in Appendix B.3. When player i declares a row, write J^i J_i for its index; the root has J^0=J J_0=J. Set p:=min1/4,1/⌈T⌉,α0:=2−40.p:= \1/4,1/ T \, _0:=2^-40. Here p is the probability that a public row reserves a given round for bootstrap communication, while α0 _0 is the probability that an array column listens at a given position. We call a player informed exactly when J^i≠⊥ J_i≠ . An informed player’s local clock is Ci(bn)=Kα0p∑b′≤b∑t∈Ib′t∈ℒi,b′CJ^i,tYi,t>0.C_i(bn)= K _0p _b ≤ b _t∈ I_b 1\t _i,b \C_ J_i,t1\Y_i,t>0\. (8) The sum includes observations made before J^i J_i was known. Let bN:=⌈log2(N+1)⌉,V:=K5/2TΛ2,V^:=K2⌈KT⌉bN2.b_N:= _2(N+1) , V:=K^5/2 T ^2, V:=K^2 KT b_N^2. The quantity V is the target regret scale, and V^≍V V V is an integer-valued proxy convenient for parameter choices. Define the follower activation threshold for the support-estimating clock Qboot:=C08(V^+KbN2/p),Q_ boot:=C_0^8 ( V+Kb_N^2/p ), (9) and fix an integer cact>128e+1c_ act>128e+1. The root uses the larger threshold cactQbootc_ actQ_ boot; the gap guarantees that the followers activate before the root launches. Algorithm 1 Activation and launch at player i 1: Initially inactive; only the root knows J. 2: for each bootstrap block in calendar order do 3: Choose its bootstrap message, then a fresh private array column, by Algorithm 12. 4: While inactive, play its array arm on every round. 5: While active, play its array arm on declared reserved rounds and use the learning protocol on other rounds. 6: Store the bootstrap observations; when active, use the sparse DATA list of Section 7.3. 7: if the block is complete with endpoint t then 8: Decode the block, update digits and child lists, and compute Ci(t)C_i(t) if informed. 9: if t<Tt<T, informed, and inactive then 10: if i≠0i≠ 0 and Ci(t)≥QbootC_i(t)≥ Q_ boot then 11: Activate from round t+1t+1. 12: else if i=0i=0 and C0(t)≥cactQbootC_0(t)≥ c_ actQ_ boot then 13: Activate from round t+1t+1. 14: end if 15: end if 16: end if 17: end for Lemma 2 (The root launches after every follower is active). Suppose every player knows J whenever any player activates. For this lemma, define Ci(t)C_i(t) by (8) with J in place of J^i J_i, even before player i is informed. Assume that, at every complete-block boundary t, these counts satisfy G(t)8e−Qboot2≤Ci(t)≤8G(t)+Qboot2(0≤i<m). G(t)8e- Q_ boot2≤ C_i(t)≤ 8G(t)+ Q_ boot2 (0≤ i<m). (10) If the root activates after boundary t, every follower is active from round t+1t+1. The support before root activation, or throughout the horizon if it never activates, is at most [8e(cact+1/2)+1]Qboot, [8e(c_ act+1/2)+1 ]Q_ boot, provided Kn≤QbootKn≤ Q_ boot. Proof. The root’s threshold and the clock upper bound give G(t) G(t) ≥cact−1/28Qboot ≥ c_ act-1/28Q_ boot >16eQboot. >16eQ_ boot. For every follower, the lower bound then gives Ci(t)≥G(t)8e−Qboot2>32Qboot.C_i(t)≥ G(t)8e- Q_ boot2> 32Q_ boot. Every follower is informed under the hypothesis on declarations, so the activation rule has activated it by the next round. For the support bound, let s be the first complete boundary with G(s)≥8e(cact+1/2)QbootG(s)≥ 8e(c_ act+1/2)Q_ boot, if it exists. At this boundary the root’s lower clock bound gives C0(s)≥cactQbootC_0(s)≥ c_ actQ_ boot. If s<Ts<T, the root therefore activates by s+1s+1. The first-crossing property and the bound of KnKn on one block’s support give G(s)≤8e(cact+1/2)Qboot+Kn.G(s)≤ 8e(c_ act+1/2)Q_ boot+Kn. This also bounds the full horizon when s=Ts=T. If no such complete boundary exists, the support in complete blocks is below the crossing level, and the final incomplete block adds at most KnKn. In both cases Kn≤QbootKn≤ Q_ boot proves the claim. ∎ Let k⋆:=minm,K−m.k_ := \m,K-m\. Let CbC_b be a sufficiently large universal branch constant, chosen last in the proof of Theorem 1. We call k⋆T>CbV^k_ T>C_b V (11) the construction branch; on the complementary branch the players use a fixed assignment to m distinct arms. The initialization guarantee also uses the following array parameters. Fix a rational constant 0<cϵ≤10<c_ε≤ 1, let CSC_S be a sufficiently large universal constant fixed in the proof of Lemma 29, and write d:=m−1d:=m-1. Define L:=⌈C0KbN⌉,e∗:=⌈C04K2bN2⌉,ℓcol:=⌈L/K⌉.L:= C_0Kb_N , e_*:= C_0^4K^2b_N^2 , _ col:= L/K . Here L is the candidate-list scale, e∗e_* is the positive-observation quota required before raw bootstrap decoding, and ℓcol _ col is the disjoint-column scale used in the array arguments. Set ϵarr _ arr :=cϵK3bN2m3T, :=c_ε K^3b_N^2m^3T, (12) Γ :=Kn+mbN+bN, :=Kn+mb_N+b_N, Scol S_ col :=⌈CSmaxdℓcolΓϵarr,m2KbNα0⌉. := C_S \ d _ col _ arr, m^2Kb_N _0 \ . The quantity ϵarr _ arr is the allowed exceptional-column fraction, Γ is the input-count scale used in the uniform union bounds, and ScolS_ col is the number of public array columns. Finally, the finite public control sampler uses Lbit:=⌈64log2N⌉L_ bit:= 64 _2N bits per sampler coordinate. Let Bblk:=⌊T/n⌋B_ blk:= T/n denote the number of complete bootstrap blocks. The exact-uniform private draws in Algorithm 12, including the initial choices of J and UiU_i, are realized by the bounded sampler of (6). Proposition 3 (Constructive initialization). Assume the construction branch (11), and fix public masks and arm arrays satisfying Lemmas 33 and 29. The probability below is over the root index and players’ private randomness. For every deterministic reward matrix, set Δboot=Cm2Bblk(ϵarr+dℓcol/Scol+L/Akey)+N−2+N−1+N−40+CmTe−C0Λ. _ boot=Cm^2B_ blk( _ arr+d _ col/S_ col+L/A_ key)+N^-2+N^-1+N^-40+CmTe^-C_0 . (13) There is a reference initialization, coupled to the actual protocol by the same root index, private keys, and bootstrap columns, and an event ℰbootE_ boot with Pr(ℰbootc)≤Δboot (E_ boot^c)≤ _ boot, such that: (i) On ℰbootE_ boot, the two initializations have identical bootstrap states and activation times. If any player activates, then every player has recovered J and every child-key list is initialized before that activation. Every follower is active when the root launches. (i) On every reference path, each follower is active when the root launches, and the support before that launch is at most [8e(cact+1/2)+1]Qboot[8e(c_ act+1/2)+1]Q_ boot. Conditional on the reward matrix, masks, and arrays, the reference bootstrap states and activation times are independent of all learning/control rows. Every control-row access in the reference execution uses RJR_J. Proof. Recovery before activation. Call a complete block informative when its support is at least 128Ke∗/α0128Ke_*/ _0. Apply Proposition 32 with δprop=N−2 _ prop=N^-2, and write its required number of informative blocks as rboot=1+⌈8L(2⌊log2m⌋+log(mN2))⌉=O(KΛ2).r_ boot=1+ 8L(2 _2m + (mN^2)) =O(K ^2). At any complete-block boundary preceding the rbootr_ bootth informative block, there are at most rboot−1r_ boot-1 informative blocks. Each such block contributes at most KnKn support, and each other block contributes less than 128Ke∗/α0128Ke_*/ _0. Therefore G(t)≤Hboot:=128Ke∗Tα0n+(rboot−1)Kn<Qboot/16.G(t)≤ H_ boot:= 128Ke_*T _0n+(r_ boot-1)Kn<Q_ boot/16. (14) The definitions of e∗e_*, L, and n give Hboot=O(V)H_ boot=O(V); the choice of the universal constant C0C_0 gives the strict inequality and also Kn≤QbootKn≤ Q_ boot. Reference construction. Let sfs_ f be the first complete boundary with G(sf)≥16eQbootG(s_ f)≥ 16eQ_ boot, and let srs_ r be the first complete boundary with G(sr)≥8e(cact+1/2)QbootG(s_ r)≥ 8e(c_ act+1/2)Q_ boot. Set either boundary to +∞+∞ if it does not exist. Let tat_ a be the first boundary at which the actual activation rule activates a player, or +∞+∞ if none exists, and put τ:=minsf,taτ:= \s_ f,t_ a\. Since an activation takes effect only in the next round, all actions through τ are bootstrap actions. In particular, no learning/control row is read before the correction at τ. As in Appendix B.2, write J−1=J0+AkeyJ1J-1=J_0+A_ keyJ_1. Here J^i,k J_i,k is player i’s estimate of digit JkJ_k, ℋijH_ij is player i’s stored key list for child j, and ⊥ marks an unknown digit or absent list. The following auxiliary procedure defines the reference on every sample path, including paths on which bootstrap recovery fails. Algorithm 2 True-row reference correction (proof only) 1: Copy actual bootstrap updates through τ. 2: if τ<+∞τ<+∞ then 3: Before any control-row access, set J^i,k=Jk J_i,k=J_k for every i and k∈0,1k∈\0,1\. 4: for each parent-child edge (i,j)(i,j) do 5: if ℋij=⊥H_ij= or Uj∉ℋijU_j _ij then 6: Set ℋij=UjH_ij=\U_j\. 7: end if 8: end for 9: Recompute every clock from saved observations with mask CJC_J. 10: Preserve activation flags already set; continue the local activation rule using the corrected clocks. 11: Continue bootstrap forwarding with the corrected digits and child-key lists. 12: end if 13: if sf<Ts_ f<T then 14: Activate any remaining inactive followers from sf+1s_ f+1. 15: end if 16: if sr<Ts_ r<T then 17: Activate the root from sr+1s_ r+1 if still inactive, and launch as in Algorithm 1. 18: end if 19: Whenever the root activates, activate every remaining inactive follower from the same next round. Let priv C_ priv be the set of bounded private sampler calls made during initialization and bootstrap, including the root-index and authentication-key calls, and define ℰcap:=⋂c∈privcall c accepts within acap attempts.E_ cap:= _c∈ C_ priv\call $c$ accepts within $a_ cap$ attempts\. (15) Singleton calls satisfy this event automatically. Probability of agreement. Couple each capped private draw to an uncapped uniform draw using the same rejection stream. Define the events in the following probability estimates using these uncapped draws; their states agree with the implemented protocol on ℰcapE_ cap. Let ℰmaskE_ mask be the event that the uncapped root row J satisfies (100) for the fixed reward support. Property (i) of Lemma 33 and the uniform choice of J give Pr(ℰmaskc)≤1/N (E_ mask^c)≤ 1/N. The reference uses its array action on every true reserved round, and each block’s message is fixed before its fresh column is drawn. Thus Lemma 34 applies on ℰmaskE_ mask. Let ℰclkE_ clk be the event that (10) holds for every player and complete boundary in the uncapped reference. Then Pr(ℰclkc∩ℰmask)≤CmTe−C0Λ. (E_ clk^c _ mask)≤ CmTe^-C_0 . Let ℰrecE_ rec be the event of Proposition 32 for the all-bootstrap auxiliary execution, coupled to the actual and reference executions by their common private choices. That proposition, with δprop=N−2 _ prop=N^-2, yields Pr(ℰrecc)≤Cm2Bblk(ϵarr+dℓcol/Scol+L/Akey)+N−2. (E_ rec^c)≤ Cm^2B_ blk( _ arr+d _ col/S_ col+L/A_ key)+N^-2. To bound Pr(ℰcapc) (E_ cap^c), observe that a draw from a set of size q succeeds in one rejection attempt with probability at least 1/21/2; this is also true for q=1q=1, when no rejection is needed. Algorithm 12 makes at most four private draws per player and block. Including the initial keys and root index, the number of draws is at most 4m⌈T/n⌉+m≤N4m T/n +m≤ N. Therefore Pr(ℰcapc)≤N2−acap≤N−44≤N−40. (E_ cap^c)≤ N2^-a_ cap≤ N^-44≤ N^-40. Define ℰboot:=ℰmask∩ℰclk∩ℰrec∩ℰcap.E_ boot:=E_ mask _ clk _ rec _ cap. The union bound gives Pr(ℰbootc)≤Δboot (E_ boot^c)≤ _ boot. We prove pathwise agreement on ℰbootE_ boot. Through τ, the actual, reference, and all-bootstrap executions have the same bootstrap actions and observations; induction over the completed blocks gives the same digit estimates and child-key lists. Property (i) of Proposition 32 makes every declared row equal to J. Hence the clock used at a first activation boundary t equals its true-row clock. Since the smallest activation threshold is QbootQ_ boot, the upper bound in (10) implies Qboot≤8G(t)+Qboot/2,G(t)≥Qboot/16.Q_ boot≤ 8G(t)+Q_ boot/2, G(t)≥ Q_ boot/16. By (14), t cannot precede the rbootr_ bootth informative block. The same conclusion holds if τ=sfτ=s_ f, because G(sf)≥16eQbootG(s_ f)≥ 16eQ_ boot. Proposition 32 therefore implies that, whenever τ<+∞τ<+∞, every player knows J and every child list contains the true key at τ. The corrections in Algorithm 2 then change no bootstrap field or clock on ℰbootE_ boot. At sf<Ts_ f<T, the lower clock bound gives, for every follower, Ci(sf)≥16eQboot8e−Qboot2=32Qboot>Qboot.C_i(s_ f)≥ 16eQ_ boot8e- Q_ boot2= 32Q_ boot>Q_ boot. At sr<Ts_ r<T, it gives C0(sr)≥8e(cact+1/2)Qboot8e−Qboot2=cactQboot.C_0(s_ r)≥ 8e(c_ act+1/2)Q_ boot8e- Q_ boot2=c_ actQ_ boot. Thus both forced activations coincide with decisions of the actual activation rule. If the root activates earlier, the hypotheses of Lemma 2 hold, so its followers are already active from the next round. Induction over the remaining block boundaries shows that the actual and reference bootstrap states and activation times coincide on ℰbootE_ boot. Pathwise support and independence. Put Hr=8e(cact+1/2)QbootH_ r=8e(c_ act+1/2)Q_ boot. At its first crossing boundary srs_ r, if one exists, the increase in support over the preceding complete boundary is at most KnKn; hence G(sr)≤Hr+KnG(s_ r)≤ H_ r+Kn. If there is no such boundary, the complete blocks contribute less than HrH_ r, and the final incomplete block contributes at most KnKn. The reference root activates no later than sr+1s_ r+1 when sr<Ts_ r<T. Consequently, on every reference path, the support before root activation, or over the full horizon if it never activates, is at most Hr+Kn≤[8e(cact+1/2)+1]QbootH_ r+Kn≤[8e(c_ act+1/2)+1]Q_ boot. The final rule of Algorithm 2 activates every follower no later than the root’s launch. Fix the reward matrix, masks, and arrays. Let ℱbootF_ boot be generated by J, the follower keys, and all private bootstrap randomness; it is independent of the learning/control rows. Through τ, only bootstrap actions occur, so τ and the bootstrap history through τ are ℱbootF_ boot-measurable. The reference correction, when needed, and subsequent bootstrap updates use only this information. Induction over blocks thus makes every reference bootstrap state and activation time ℱbootF_ boot-measurable. The correction precedes the first control-row access, and every such access uses RJR_J. ∎ 5 The slow–fast learner We analyze the slow–fast learner in the product-stream execution of Section 3. 5.1 A set distribution with one fast arm The coordinator is player 00, and the slow players are 1,…,m−11,…,m-1. For positive arm weights w, define (w) (w) =em(w)=∑|S|=m∏i∈Swi, =e_m(w)= _|S|=m _i∈ Sw_i, Qw(S) Q_w(S) =∏i∈Swi(w), = _i∈ Sw_iZ(w), θw(i) _w(i) =∑S∋iQw(S). = _S iQ_w(S). Here eke_k denotes the degree-k elementary symmetric sum. At the start of an active episode, freeze the current weights as the anchor w¯ w. A later assignment does not change w¯ w or the recording rates below. After drawing an m-set S, choose its fast arm j with probability αj(S)=w¯j−1∑i∈Sw¯i−1. _j(S)= w_j^-1 _i∈ S w_i^-1. (16) The remaining set U=S∖jU=S \j\ has m−1m-1 arms, assigned in increasing arm-label order to the slow players. Let pw(U)=∑j∉UQw(U∪j)αj(U∪j).p_w(U)= _j∉ UQ_w(U∪\j\) _j(U∪\j\). Writing sU=∑i∈Uw¯i−1s_U= _i∈ U w_i^-1, the conditional law of the fast arm is qw(j∣U)=wj/(1+sUw¯j)∑k∉Uwk/(1+sUw¯k).q_w(j U)= w_j/(1+s_U w_j) _k∉ Uw_k/(1+s_U w_k). (17) Lemma 4 (Polynomial marginal bounds). Suppose w¯i≤wi≤2w¯i w_i≤ w_i≤ 2 w_i for every i. Then, for every (m−1)(m-1)-set U and i∉Ui∉ U, qw(i∣U) q_w(i U) ≥θw¯(i)2(K−m+1), ≥ _ w(i)2(K-m+1), (18) θw(i) _w(i) ≤2θw¯(i). ≤ 2 _ w(i). Proof. Put v=w¯v= w, fix i∉Ui∉ U, and write s=∑b∈Uvb−1s= _b∈ Uv_b^-1 and gU(x)=x/(1+sx)g_U(x)=x/(1+sx). For any m-set B avoiding i, retaining the products containing b in em(v−i)e_m(v_-i) gives em(v−i)∑b∈Bvb−1 e_m(v_-i) _b∈ Bv_b^-1 ≥∑b∈Bem−1(v−i,b) ≥ _b∈ Be_m-1(v_-\i,b\) =∑V⊆[K]∖i|V|=m−1|B∖V|∏k∈Vvk = _ subarraycV [K] \i\\\ |V|=m-1 subarray|B V| _k∈ Vv_k ≥em−1(v−i). ≥ e_m-1(v_-i). The last inequality uses |B∖V|≥1|B V|≥ 1. For j∉Uj∉ U with j≠ij≠ i, take B=U∪jB=U∪\j\ and set R=vi(s+vj−1)R=v_i(s+v_j^-1). The inclusion odds of i are at most R, so θv(i)≤R1+R≤R1+svi=gU(vi)gU(vj). _v(i)≤ R1+R≤ R1+sv_i= g_U(v_i)g_U(v_j). For j=ij=i, the last comparison follows from θv(i)≤1 _v(i)≤ 1. Summing θv(i)gU(vj)≤gU(vi) _v(i)g_U(v_j)≤ g_U(v_i) over the K−m+1K-m+1 outside arms gives qv(i∣U)=gU(vi)∑j∉UgU(vj)≥θv(i)K−m+1.q_v(i U)= g_U(v_i) _j∉ Ug_U(v_j)≥ _v(i)K-m+1. In (17), replacing v by w multiplies each unnormalized mass by wj/vj∈[1,2]w_j/v_j∈[1,2]. Thus qw(i∣U)≥qv(i∣U)/2q_w(i U)≥ q_v(i U)/2, which proves the first inequality in (18). Finally, the inclusion odds of i are θw(i)/(1−θw(i))=wiem−1(w−i)/em(w−i) _w(i)/(1- _w(i))=w_ie_m-1(w_-i)/e_m(w_-i). Fix j≠ij≠ i and let Ek=ek(w−i,j)E_k=e_k(w_-\i,j\). Holding all other weights fixed, these odds equal wiEm−1+wjEm−2Em+wjEm−1.w_i E_m-1+w_jE_m-2E_m+w_jE_m-1. Their derivative with respect to wjw_j has the sign of Em−2Em−Em−12≤0E_m-2E_m-E_m-1^2≤ 0 by Newton’s inequalities for elementary symmetric sums (Hardy, Littlewood, and Pólya [11]). Thus increasing another arm’s weight cannot increase inclusion of i. Increasing wiw_i by at most a factor two increases its inclusion probability by at most two. Increase the other weights first and then wiw_i to obtain θw(i)≤2θw¯(i) _w(i)≤ 2 _ w(i). ∎ 5.2 A sparse estimate and infrequent refreshes Recall N=2Km(T+1)N=2Km(T+1). Let Lstab=⌈log2(2K(T+1)N8)⌉L_ stab= _2(2K(T+1)N^8) be the concentration scale that keeps weights stable within an episode. Set A=256A=256 to be a fixed constant. Let η be the learning rate, subject to the cap below; it determines β and H: 0<η 0<η ≤(2AmKLstab)−1, ≤(2AmKL_ stab)^-1, β β =2ηLstab, =2η L_ stab, H H =⌊(16η)−1⌋. = (16η)^-1 . Here β is a lower bound on recording rates, and H bounds the episode length. An active episode ends at the next multiple of H, clipped at T+1T+1. If collection is still unfinished, updates remain frozen until the next commitment starts a new active episode. At each episode start, use the frozen anchor w¯ w to set ξi _i =2⌈log2maxβ,θw¯(i)/(AmK)⌉, =2 _2 \β, _ w(i)/(AmK)\ , (19) γ γ =A4(K−m+1)ηLstab, = A4(K-m+1)η L_ stab, qγ q^γ =(1−γ)q+γUnif([K]∖U). =(1-γ)q+γ ([K] U). Here ξi _i is the recording rate for arm i, and γ is the uniform-exploration probability. The law qγ(⋅∣U)q^γ(· U) mixes qw(⋅∣U)q_w(· U) with the uniform law on arms outside U. If w¯≤w≤2w¯ w≤ w≤ 2 w, the rates satisfy β≤ξi β≤ _i ≤2AmK, ≤ 2AmK, (20) qγ(i∣U) q^γ(i U) ≥16ξi(i∉U), ≥ 16 _i (i∉ U), θw(i)ξi _w(i) _i ≤2AmK, ≤ 2AmK, ∑iθw(i)ξi _i _w(i) _i ≤2AmK2. ≤ 2AmK^2. To check these bounds, dyadic rounding gives the first line. Lemma 4 and γ≤(K−m+1)/(8mK)≤1/16γ≤(K-m+1)/(8mK)≤ 1/16 give, for i∉Ui∉ U, (1−γ)qw(i∣U) (1-γ)q_w(i U) ≥θw¯(i)8mK=32θw¯(i)AmK, ≥ _ w(i)8mK=32 _ w(i)AmK, γK−m+1 γK-m+1 =32β. =32β. The two terms of the mixture therefore give qγ(i∣U)≥16ξiq^γ(i U)≥ 16 _i. The remaining bounds follow from θw(i)≤2θw¯(i) _w(i)≤ 2 _ w(i) and ξi≥θw¯(i)/(AmK) _i≥ _ w(i)/(AmK). Also ∑iξi≤2/(Am)≤1 _i _i≤ 2/(Am)≤ 1, as required for the sparse law below. Recall the bit-length scale bN=⌈log2(N+1)⌉b_N= _2(N+1) from Section 4.1. Use D=22bND=2^2b_N as the reward quantization denominator: round each reward down to a multiple of 1/D1/D and denote the result by rt(i)r_t(i). This changes regret by at most mT/DmT/D. Store integer scores ziz_i, initially zero, and set wi=(1+1/D)ziw_i=(1+1/D)^z_i. Fix the oblivious reward matrix and the reserved rounds. In the product-stream experiment, the prescribed symbols at distinct rounds are independent, with the laws specified by the protocol. Each logical refresh uses a uniform variable independent of the history through its current estimate. Let ℱtF_t be the history immediately before the current round’s symbols are exposed, including the scores, the current slow set UtU_t, and all preceding observations and decisions. In particular, the recording rates and whether learning is enabled are ℱtF_t-measurable. The current fast-arm draw is not included. On an active nonreserved round with learning unfrozen, let ItI_t be the arm selected for recording, or ⊥ if none is selected. Its required conditional law is Pr(It=i∣ℱt) (I_t=i _t) =ξi(i∈[K]), = _i (i∈[K]), (21) Pr(It=⊥∣ℱt) (I_t= _t) =1−∑iξi. =1- _i _i. The rates are frozen for the episode, so this law is the same for every slow set. If It=iI_t=i, its quantized estimate is r~t(i)=1ηD⌊Dηrt(i)ξi⌋. r_t(i)= 1η D Dη r_t(i) _i . (22) All other coordinates of r~t r_t are zero. If no arm is selected, or the round is inactive, reserved, or frozen, then r~t=0 r_t=0. When i is selected, add ⌊Dηrt(i)/ξi⌋ Dη r_t(i)/ _i to ziz_i. Since η/ξi≤1/(2Lstab)η/ _i≤ 1/(2L_ stab), each increment is at most D and every score lies in [0,TD][0,TD]. Write pt=pwtp_t=p_w_t for the slow-set distribution before round t. Set h=4AmKηh=4AmKη as the probability of proposing a new slow set after a score update. The learning-rate cap gives h≤1/4h≤ 1/4. The proposed set has distribution ρt(U)=pt+1(U)−(1−h)pt(U)h. _t(U)= p_t+1(U)-(1-h)p_t(U)h. (23) Lemma 5 below shows that ρt _t is a probability distribution while the weights remain stable. After the score update on each active nonreserved round with learning unfrozen, the logical learner uses a bit Bt∼Bernoulli(h)B_t (h), independent of the history through that update; set Bt=0B_t=0 on all other rounds. The event Bt=1B_t=1 is a proposal. On an unfrozen round, the logical learner draws its next slow set from ρt _t if Bt=1B_t=1, and retains the current set if Bt=0B_t=0. During a live assignment this is the bit supplied by the public row. During collection the logical learner uses independent auxiliary bits, while the corresponding public coordinates remain unread. Section 7 integrates these logical refreshes into the distribution of the next assignment. No proposal is used on a frozen round. We call this the logical learner: its scores and slow set change at the prescribed update and proposal times, without waiting for messages. Algorithm 3 Logical slow–fast learner 1: Initialize zi=0z_i=0 and wi=1w_i=1 for every arm i. 2: for each active episode of at most H rounds do 3: Freeze w¯=w w=w; compute the rates ξi _i and mixing probability γ. 4: Draw the slow set U∼pwU p_w and assign its arms to slow players in increasing order. 5: for each active nonreserved round t with learning unfrozen do 6: Draw the coordinator’s fast arm jt∼qwtγ(⋅∣U)j_t q_w_t^γ(· U). 7: Obtain a recorded arm ItI_t with the conditional law (21). 8: if It=i∈[K]I_t=i∈[K] then 9: Form r~t(i) r_t(i) by (22) and add ⌊Dηrt(i)/ξi⌋ Dη r_t(i)/ _i to ziz_i. 10: Update wi=(1+1/D)ziw_i=(1+1/D)^z_i. 11: end if 12: Draw the proposal bit Bt∼Bernoulli(h)B_t (h). 13: if Bt=1B_t=1 then 14: Draw the next slow set from ρt _t. 15: end if 16: end for 17: end for For analysis on exceptional paths, use the following bounded continuation after the first weight-doubling update. Keep the logical scores fixed, set all subsequent logical estimates to zero, and perform no further logical refreshes. Whenever a later auxiliary reward is evaluated, use Ut=1,…,m−1U_t=\1,…,m-1\ and jt=mj_t=m. This convention affects only paths with a stability failure and keeps each auxiliary reward in [0,m][0,m]; a decoder failure alone does not stop or alter the logical learner. Lemma 5 (Stability and fixed refresh probability). Outside an event of probability at most N−8N^-8, every active episode satisfies w¯≤wt<2w¯ w≤ w_t<2 w. On this event, each one-coordinate update obeys pt+1(U)≥(1−h)pt(U).p_t+1(U)≥(1-h)p_t(U). (24) Proof. For an episode starting at τ, let g be its next grid boundary and define the first weight-doubling round by τ∗=inft∈[τ,g):maxiwt+1,i/w¯i≥2, _*= \t∈[τ,g): _iw_t+1,i/ w_i≥ 2\, with inf∅=+∞ =+∞. Fix arm i and condition on the history immediately before the initial slow-set draw. Set Xt(i)=τ≤t<g,t≤τ∗log(wt+1,i/wt,i).X_t(i)=1\τ≤ t<g,\ t≤ _*\ (w_t+1,i/w_t,i). The indicator t≤τ∗1\t≤ _*\ means that no earlier update has doubled a weight, so it is ℱtF_t-measurable. It includes the update at t=τ∗t= _* and excludes every later update. On a learning round with t≤τ∗t≤ _*, (20) gives ξi≥β=2ηLstab _i≥β=2η L_ stab and hence 0≤Xt(i)≤η/ξi≤1/(2Lstab)0≤ X_t(i)≤η/ _i≤ 1/(2L_ stab). The event It=iI_t=i has conditional probability ξi _i by (21). The oblivious reward rt(i)r_t(i) and frozen rate ξi _i are ℱtF_t-measurable. Therefore, on an enabled round with t≤τ∗t≤ _*, [Xt(i)∣ℱt] [X_t(i) _t] =ξilog(1+1/D)⌊Dηrt(i)ξi⌋ = _i (1+1/D) Dη r_t(i) _i ≤ηrt(i)≤η. ≤η r_t(i)≤η. On other rounds Xt(i)=0X_t(i)=0, so the same bounds hold. Convexity of the exponential gives [e2LstabXt(i)∣ℱt]≤1+2(e−1)Lstab[Xt(i)∣ℱt]≤e2(e−1)Lstabη.E[e^2L_ stabX_t(i) _t]≤ 1+2(e-1)L_ stabE[X_t(i) _t]≤ e^2(e-1)L_ stabη. An episode contains at most H rounds. Iterating this bound, with zero increments after the episode ends, gives exp(2Lstab∑tXt(i))≤exp(2(e−1)LstabHη)≤exp((e−1)Lstab/8).E (2L_ stab _tX_t(i) )≤ (2(e-1)L_ stabHη)≤ ((e-1)L_ stab/8). If arm i doubles during this episode, then ∑tXt(i)≥log2 _tX_t(i)≥ 2. Markov’s inequality bounds this probability by exp(−[2log2−(e−1)/8]Lstab)≤2−Lstab. (-[2 2-(e-1)/8]L_ stab )≤ 2^-L_ stab. By the definition of LstabL_ stab, this is at most N−8/(2K(T+1))N^-8/(2K(T+1)). A union bound over at most KTKT arm–episode pairs proves the stability claim. For a one-arm update at i, write x=log(wt+1,i/wt,i)≤ηrt(i)/ξi≤1x= (w_t+1,i/w_t,i)≤η r_t(i)/ _i≤ 1. Since ex−1≤2xe^x-1≤ 2x, (20) gives (wt+1)(wt)=1+θwt(i)(ex−1)≤1+2θwt(i)η/ξi≤1+h. Z(w_t+1)Z(w_t)=1+ _w_t(i)(e^x-1)≤ 1+2 _w_t(i)η/ _i≤ 1+h. For every j∉Uj∉ U, the weights only increase, so the preceding bound on (wt+1)/(wt)Z(w_t+1)/Z(w_t) gives Qwt+1(U∪j)Qwt(U∪j) Q_w_t+1(U∪\j\)Q_w_t(U∪\j\) =(wt)(wt+1)∏i∈U∪jwt+1,iwt,i = Z(w_t)Z(w_t+1) _i∈ U∪\j\ w_t+1,iw_t,i ≥11+h. ≥ 11+h. The coefficients αj(U∪j) _j(U∪\j\) depend only on the frozen anchor w¯ w and are nonnegative. Summing the last inequality yields pt+1(U) p_t+1(U) =∑j∉Uαj(U∪j)Qwt+1(U∪j) = _j∉ U _j(U∪\j\)Q_w_t+1(U∪\j\) ≥11+h∑j∉Uαj(U∪j)Qwt(U∪j) ≥ 11+h _j∉ U _j(U∪\j\)Q_w_t(U∪\j\) =pt(U)1+h≥(1−h)pt(U). = p_t(U)1+h≥(1-h)p_t(U). ∎ By (24), every term of the proposed law (23) is nonnegative; its terms sum to one. Thus the refresh step in Algorithm 3 is valid on the stability event. 5.3 Learning bound For an episode starting at τ, let ℋτH_τ be the full history immediately before its initial slow-set draw. Its next grid boundary g=minT+1,H(⌊τ/H⌋+1)g= \T+1,H( τ/H +1)\ and recording rates are fixed under this conditioning. Define the smaller history ℰt=σ(ℋτ,r~τ,…,r~t−1),τ≤t<g.E_t=σ (H_τ, r_τ,…, r_t-1 ), τ≤ t<g. Thus ℰtE_t records the episode’s initial history and subsequent estimates, and omits subsequent proposals and communication observations. The scores and ptp_t are ℰtE_t-measurable. Lemma 6 (Conditional slow-set law). For each round t of the episode, Pr(Ut=U∣ℰt)=pt(U)on t≤τ∗. (U_t=U _t)=p_t(U) \t≤ _*\. The event that no previous weight doubling has occurred is ℰtE_t-measurable. The identity therefore applies on the weight-doubling round itself. Proof. The initial draw gives the identity at t=τt=τ. Suppose it holds at t and that no earlier update doubled a weight. The law in (21), followed by the deterministic formula (22), defines a probability kernel KtK_t for r~t r_t. This kernel depends only on the frozen rates, the fixed reward vector, and whether the round is enabled. All these quantities are ℰtE_t-measurable. In particular, for every set C of possible estimates, Pr(r~t∈C∣ℱt)=Kt(C). ( r_t∈ C _t)=K_t(C). For each slow set U, the tower property now gives Pr(Ut=U,r~t∈C∣ℰt) (U_t=U, r_t∈ C _t) =[Ut=UKt(C)∣ℰt] =E[1\U_t=U\K_t(C) _t] =pt(U)Kt(C). =p_t(U)K_t(C). Consequently revealing the estimate leaves the conditional law of UtU_t equal to ptp_t. On an enabled nonreserved round, the proposal bit is independent of the history through that estimate. Its refresh draw has law ρt _t and is independent of the preceding slow set. Therefore Pr(Ut+1=U∣ℰt+1) (U_t+1=U _t+1) =(1−h)pt(U)+hρt(U) =(1-h)p_t(U)+h _t(U) =pt+1(U). =p_t+1(U). On a reserved round the estimate is zero and neither distribution changes. This proves the induction until the first doubling. Whether an earlier update doubled a weight is determined by the estimates already included in ℰtE_t. Restricting to this event therefore does not add information about UtU_t beyond ℰtE_t, which proves the last assertion. ∎ Let A be the rounds of the product-stream execution on which learning is active, the round is nonreserved, and score updates are unfrozen. Before the first weight-doubling update, the logical learner’s UtU_t changes immediately at each proposal, as in Algorithm 3, and on t∈t its fast arm jtj_t is drawn from qwtγ(⋅∣Ut)q^γ_w_t(· U_t). Afterwards use the bounded continuation specified above. For a fixed comparator m-set S, define Raux(S)=∑t∈(rt(S)−rt(Ut)−rt(jt)).R_ aux(S)=E _t (r_t(S)-r_t(U_t)-r_t(j_t) ). Proposition 7 (Auxiliary learning bound). For any fixed m-set S chosen independently of the players’ randomness, Raux(S)≤2log(Km)η+(2AmK2+A4(K−m+1)Lstab)ηT+mTηD+CmTN−8.R_ aux(S)≤ 2 Kmη+(2AmK^2+ A4(K-m+1)L_ stab)η T+ mTη D+CmTN^-8. (25) In particular, S may maximize the original oblivious reward matrix; it is not chosen after seeing the random active rounds. Proof. In this proof, τ∗ _* denotes the first weight-doubling round in any episode, with τ∗=+∞ _*=+∞ if no weight doubles. The event t≤τ∗\t≤ _*\ is determined by the current episode’s initial history and its estimates before t. First relate the distribution of the played arms to QwQ_w. For j∉Uj∉ U, (16) gives αj(U∪j)=11+sUw¯j. _j(U∪\j\)= 11+s_U w_j. Hence Qw(U∪j)αj(U∪j)=∏i∈Uwi(w)wj1+sUw¯j.Q_w(U∪\j\) _j(U∪\j\)= _i∈ Uw_iZ(w) w_j1+s_U w_j. The factor before the last fraction does not depend on j. Summing over j∉Uj∉ U gives pw(U)p_w(U), and normalizing gives (17). Consequently, pw(U)qw(j∣U)=Qw(U∪j)αj(U∪j).p_w(U)q_w(j U)=Q_w(U∪\j\) _j(U∪\j\). If the fast arm is drawn from qwtq_w_t without uniform mixing, then for every m-set S′S , Pr(Ut∪jt=S′∣ℰt) (U_t∪\j_t\=S _t) =∑j∈S′pwt(S′∖j)qwt(j∣S′∖j) = _j∈ S p_w_t(S \j\)q_w_t(j S \j\) =Qwt(S′)∑j∈S′αj(S′) =Q_w_t(S ) _j∈ S _j(S ) =Qwt(S′). =Q_w_t(S ). Its conditional expected reward is therefore [rt(Ut)+rt(jt)∣ℰt] [r_t(U_t)+r_t(j_t) _t] =∑S′Qwt(S′)rt(S′) = _S Q_w_t(S )r_t(S ) =∑iθwt(i)rt(i). = _i _w_t(i)r_t(i). The actual law qwtγq^γ_w_t mixes the fast arm with a uniform draw with probability γ. This leaves UtU_t unchanged and can lower the expected reward by at most γ, because each arm’s reward lies in [0,1][0,1]. Thus, under the actual law, [rt(Ut)+rt(jt)∣ℰt]≥∑iθwt(i)rt(i)−γ.E[r_t(U_t)+r_t(j_t) _t]≥ _i _w_t(i)r_t(i)-γ. For an m-set S, write r~t(S)=∑i∈Sr~t(i) r_t(S)= _i∈ S r_t(i). Put λ=Dlog(1+1/D)η∈[η/2,η]λ=D (1+1/D)η∈[η/2,η]. If arm i is recorded, its log-weight increment is x=λr~t(i)∈[0,1]x=λ r_t(i)∈[0,1]. Hence log(wt+1)(wt)=log(1+θwt(i)(ex−1))≤θwt(i)(x+x2). Z(w_t+1)Z(w_t)= (1+ _w_t(i)(e^x-1) )≤ _w_t(i)(x+x^2). The same inequality is trivial when no arm is recorded. Since at most one coordinate of r~t r_t is nonzero, summing the one-step bound and telescoping the logarithms gives log(wT+1)(w1) Z(w_T+1)Z(w_1) =∑tlog(wt+1)(wt) = _t Z(w_t+1)Z(w_t) ≤λ∑t,iθwt(i)r~t(i)+λ2∑t,iθwt(i)r~t(i)2. ≤λ _t,i _w_t(i) r_t(i)+λ^2 _t,i _w_t(i) r_t(i)^2. On the other hand, the weight product for S is one term of (wT+1)Z(w_T+1). Since (w1)=(Km)Z(w_1)= Km and ∏i∈SwT+1,i=exp(λ∑tr~t(S)) _i∈ Sw_T+1,i= (λ _t r_t(S)), log(wT+1)(w1) Z(w_T+1)Z(w_1) ≥log∏i∈SwT+1,i(Km) ≥ _i∈ Sw_T+1,i Km =λ∑tr~t(S)−log(Km). =λ _t r_t(S)- Km. Combine the upper and lower bounds, subtract the linear term from both sides, and divide by λ to obtain ∑t(r~t(S)−∑iθwt(i)r~t(i))≤log(Km)λ+λ∑t∑iθwt(i)r~t(i)2. _t ( r_t(S)- _i _w_t(i) r_t(i) )≤ Kmλ+λ _t _i _w_t(i) r_t(i)^2. The weights persist across episodes, so this pays log(Km) Km only once. On an enabled round before a previous weight doubling, the recording law and the floor in the update give [r~t(i)∣ℱt] [ r_t(i) _t] =ξiηD⌊Dηrt(i)ξi⌋, = _iη D Dη r_t(i) _i , rt(i)−ξiηD r_t(i)- _iη D ≤[r~t(i)∣ℱt]≤rt(i). [ r_t(i) _t]≤ r_t(i). Likewise, [r~t(i)2∣ℱt] [ r_t(i)^2 _t] =ξi(ηD)2⌊Dηrt(i)ξi⌋2 = _i(η D)^2 Dη r_t(i) _i ^2 ≤rt(i)2ξi. ≤ r_t(i)^2 _i. Since θwt(i)≥0 _w_t(i)≥ 0 and the weights are ℱtF_t-measurable, the first pair of bounds implies rt(S)−∑iθwt(i)rt(i) r_t(S)- _i _w_t(i)r_t(i) ≤ ≤ ∑i∈S([r~t(i)∣ℱt]+ξiηD)−∑iθwt(i)[r~t(i)∣ℱt] _i∈ S (E[ r_t(i) _t]+ _iη D )- _i _w_t(i)E[ r_t(i) _t] = = [r~t(S)−∑iθwt(i)r~t(i)|ℱt]+∑i∈SξiηD. \! [ r_t(S)- _i _w_t(i) r_t(i)\, |\,F_t ]+ _i∈ S _iη D. Here ∑i∈Sξi≤m _i∈ S _i≤ m, since 0≤ξi≤10≤ _i≤ 1. The second-moment bound and (20) give [∑iθwt(i)r~t(i)2|ℱt] \! [ _i _w_t(i) r_t(i)^2\, |\,F_t ] ≤∑iθwt(i)rt(i)2ξi ≤ _i _w_t(i)r_t(i)^2 _i ≤∑iθwt(i)ξi≤2AmK2. ≤ _i _w_t(i) _i≤ 2AmK^2. To sum the conditional reward inequalities over random episode starts, condition first on ℋτH_τ. If the episode starts at τ, its rounds with enabled estimates, before a stability stop, are exactly t∈[T]:τ≤t<g,t is nonreserved.\t∈[T]:τ≤ t<g,\ t is nonreserved\. The displayed set is fixed under that conditioning; collection within the episode does not freeze estimates. Multiply its round-t summand by t≤τ∗1\t≤ _*\. This indicator is ℰtE_t-measurable, so Lemma 6 still gives the conditional reward inequality on each retained round. At a later episode’s random start, condition on its new ℋτH_τ and apply the same argument. Summing these conditional expectations accounts for every retained round exactly once. No conditioning on successful decoding is used. In the potential inequality, set all estimates after the first weight-doubling round to zero and keep the weights fixed thereafter. The potential calculation remains valid for this stopped sequence. Take its expectation. Write ∗A_* for the rounds of A up to and including that first doubling round. The conditional reward bound just proved gives ∑t∈∗(rt(S)−rt(Ut)−rt(jt)) _t _* (r_t(S)-r_t(U_t)-r_t(j_t) ) ≤∑t∈∗(rt(S)−∑iθwt(i)rt(i))+γT. _t _* (r_t(S)- _i _w_t(i)r_t(i) )+γ T. Here |∗|≤T|A_*|≤ T. Applying the conditional estimate comparison on each retained round and then the potential inequality gives ∑t∈∗(rt(S)−∑iθwt(i)rt(i)) _t _* (r_t(S)- _i _w_t(i)r_t(i) ) ≤∑t∈∗(r~t(S)−∑iθwt(i)r~t(i))+mTηD _t _* ( r_t(S)- _i _w_t(i) r_t(i) )+ mTη D ≤log(Km)λ+λ∑t∈∗∑iθwt(i)r~t(i)2+mTηD ≤ Kmλ+ _t _* _i _w_t(i) r_t(i)^2+ mTη D ≤2log(Km)η+2AmK2ηT+mTηD. ≤ 2 Kmη+2AmK^2η T+ mTη D. For the last line we used the conditional second-moment inequality, λ≤ηλ≤η, and 1/λ≤2/η1/λ≤ 2/η. Substituting γ=A4(K−m+1)ηLstabγ= A4(K-m+1)η L_ stab into the conditional reward bound therefore yields ∑t∈∗(rt(S)−rt(Ut)−rt(jt)) _t _* (r_t(S)-r_t(U_t)-r_t(j_t) ) ≤2log(Km)η+(2AmK2+A4(K−m+1)Lstab)ηT+mTηD. ≤ 2 Kmη+ (2AmK^2+ A4(K-m+1)L_ stab )η T+ mTη D. For the first doubling round, its pre-round weights still satisfy w¯i≤wt,i<2w¯i w_i≤ w_t,i<2 w_i. Thus both conditional moment bounds and (20) apply to its update. Every omitted round belongs to an execution with a weight doubling. Since each omitted regret summand is at most m, Raux(S)≤∑t∈∗(rt(S)−rt(Ut)−rt(jt))+mTPr(some weight doubles).R_ aux(S) _t _* (r_t(S)-r_t(U_t)-r_t(j_t) )+mT (some weight doubles). Lemma 5 bounds the last probability by N−8N^-8. This completes the proof. ∎ 6 Assignment and score communication Use the history ℱtF_t of Section 5 after any commitment at the start of round t and before its physical arm choices. It includes the resulting assignment and all previously used coordinates; it excludes the current slot, pilots, arm tuple, hash, fast-arm draw, thinning coordinate, and all still-unread proposal coordinates. Thus the local states and outgoing words are ℱtF_t-measurable. In the product-stream execution the current physical coordinates have their prescribed independent laws conditional on ℱtF_t. Write Yi,tY_i,t for the quantized observation, using the convention for rtr_t in Section 5. The slot τt _t on a nonreserved round has the following law. Slot Probability Role DATA 1/21/2 Play arms and possibly record one reward. DOWN 1/41/4 Send an assignment and confirm that its recipient decoded it. UP 1/41/4 Return a score, or certify that the coordinator received all assignment receipts. 6.1 Message decoding and support cost On each DOWN or UP round, the row selects kt∈[d]k_t∈[d] uniformly and supplies an independent uniform injective arm tuple (R0,t,…,Rd,t)∈[K]d+1(R_0,t,…,R_d,t)∈[K]^d+1. Conditional on kt=ik_t=i, DOWN goes from the coordinator to player i; UP goes from player i to the coordinator. Write RjR_j when the round is clear. Every integer field uses ⌈log2(TD+1)⌉ _2(TD+1) bits, where D is the score quantization denominator of Section 5. A DOWN record has four fields; an UP record has three fields followed by a zero field. Both have length B=4⌈log2(TD+1)⌉B=4 _2(TD+1) . Section 7.2 gives the encoding and field bounds. For each round and each direction and selected player, independently draw ct∈2Bc_t _2^B and bt∈2b_t _2, and define Ht(u)=ct⋅u⊕bt.H_t(u)=c_t· u b_t. On DOWN the sender and receiver arms are R0R_0 and RiR_i; on UP they are RiR_i and R0R_0. Hash zero forces a collision, so a positive receiver observation supplies the equation ct⋅u=1⊕bt.c_t· u=1 b_t. A zero observation supplies no equation. Set δ=N−8δ=N^-8 as the communication-error budget. The decoder uses batches of Qdec=B+⌈log2(2N12/δ)⌉Q_ dec=B+ _2(2N^12/δ) (26) positive observations. Each directed channel stores one initially empty batch. Call a message M∗M^* awaited on a directed channel while the receiver has not accepted it and, on every selected active nonreserved round, the sender encodes M∗M^* and the receiver runs DecodeStepDecodeStep. Algorithm 4 One affine message channel 1: procedure SendArm(u,Rsend,Rreceiveu,R_ send,R_ receive) 2: if Ht(u)=0H_t(u)=0 then 3: return RreceiveR_ receive. 4: else 5: return RsendR_ send. 6: end if 7: end procedure 8: procedure DecodeStep(W,YW,Y) 9: An enabled receiver channel, its equation batch W, and the current observed reward Y. 10: if Y>0Y>0 then 11: Append ct⋅u=1⊕btc_t· u=1 b_t to W. 12: end if 13: if |W|<Qdec|W|<Q_ dec then 14: return ⊥ . 15: end if 16: Solve the system W over 2BF_2^B. 17: Let M be its unique solution if one exists, and ⊥ otherwise. 18: Set W←∅W← . 19: return M. 20: end procedure Lemma 8 (Message decoding). Consider the product-stream protocol with correct initialization, stopped before a stability or feasibility failure. With probability at least 1−δ/N41-δ/N^4, no completed batch has a unique solution different from the word currently encoded on its channel that passes (40), and no completed batch formed entirely from one fixed awaited word has multiple solutions. On this event, an awaited word is accepted within 2Qdec2Q_ dec positive receiver observations after its sender fixes that word, provided service continues. Each decoder decision takes O(QdecB2)=O(log3N)O(Q_ decB^2)=O( ^3N) bit operations. Appendix A.2 proves this lemma. A decoder failure is a wrong acceptance or a nonunique system in a complete batch whose observations all come from the fixed awaited word. A decoder failure contributes at most mTδ/N4mTδ/N^4 to expected regret. The next lemma bounds the cumulative charge of parallel tasks when each pending task’s conditional service probability is at least a fixed multiple of the round’s charge and each task has a service quota. It is used for assignment delivery (Lemma 12), follower release (Lemma 13), and score collection (Lemma 21). Fix one service phase. Let σ be its first round and ϑ its first excluded round, where 1≤σ≤ϑ≤T+11≤σ≤ ≤ T+1 are stopping times for the pre-round histories (ℱt)(F_t). Thus a phase terminated after round t has ϑ=t+1 =t+1. For σ≤t<ϑσ≤ t< , let Pt⊆[d]P_t [d] be the ℱtF_t-measurable set of tasks still unresolved at the start of round t; assume Pt+1⊆PtP_t+1 P_t while the phase continues. A task may represent a fixed-message decoder, a receipt, or a release certificate. Task i is pending at t precisely when i∈Pti∈ P_t. Define the predictable eligibility indicator At=σ≤t<ϑ,t nonreserved,Pt≠∅.A_t=1\σ≤ t< ,\ t nonreserved,\ P_t≠ \. For task i, specify an event observable by the end of round t and let Xi,t∈0,1X_i,t∈\0,1\ indicate its occurrence; set Xi,t=0X_i,t=0 if the slot or selected player cannot serve i. One occurrence Xi,t=1X_i,t=1 is a service observation, which need not itself complete the task. Write Ji,t=Ati∈Pt,Ni(v)=∑t=1vJi,tXi,t.J_i,t=A_t1\i∈ P_t\, N_i(v)= _t=1^vJ_i,tX_i,t. For t outside the phase set Pt=∅P_t= . The phase’s support charge is Gwait=∑t=1TAtgt,G_ wait= _t=1^TA_tg_t, where gtg_t is defined in (5). We impose a positive integer quota q through the condition Ji,t=1⟹Ni(t−1)<qJ_i,t=1 N_i(t-1)<q: a task cannot be pending on an eligible round after its q-th service observation. Lemma 9 (Cost of parallel service). For a phase as above, fix an integer q≥1q≥ 1, a>0a>0, and ℱtF_t-measurable ωt∈[0,K] _t∈[0,K]. Suppose the quota q condition holds and, on Ji,t=1\J_i,t=1\, [Xi,t∣ℱt]≥aωtE[X_i,t _t]≥ a _t for every i∈[d]i∈[d] and t≤Tt≤ T. Then each task satisfies ∑t=1TJi,tωt≤qa.E _t=1^TJ_i,t _t≤ qa. The total phase charge satisfies ∑t=1TAtωt≤q+logd(1−e−1)a.E _t=1^TA_t _t≤ q+ d(1-e^-1)a. (27) In particular, ωt=gt _t=g_t bounds GwaitEG_ wait. Both bounds also hold conditional on the phase-start history ℱσF_σ. Proof. The variables Ji,tJ_i,t and ωt _t are ℱtF_t-measurable. For i∈[d]i∈[d] and v≤Tv≤ T, set Gi(v)=∑t=1vJi,tωt.G_i(v)= _t=1^vJ_i,t _t. The quota condition gives Ni(T)≤qN_i(T)≤ q: a q-th success can be counted, but no later eligible round can count another. Therefore aGi(T) aEG_i(T) ≤∑t=1T[Ji,t[Xi,t∣ℱt]] ≤ _t=1^TE[J_i,tE[X_i,t _t]] =Ni(T)≤q. =EN_i(T)≤ q. For the total charge, put κ=1−e−1κ=1-e^-1 and define Zi(v)=exp(κaGi(v)−Ni(v)).Z_i(v)= \! (κ aG_i(v)-N_i(v) ). On Ji,t=1\J_i,t=1\, since Xi,tX_i,t is Bernoulli, [e−Xi,t∣ℱt]=1−κ[Xi,t∣ℱt]≤e−κaωt.E[e^-X_i,t _t]=1- [X_i,t _t]≤ e^-κ a _t. On Ji,t=0\J_i,t=0\, Zi(t)=Zi(t−1)Z_i(t)=Z_i(t-1). Hence [Zi(t)∣ℱt]≤Zi(t−1).E[Z_i(t) _t]≤ Z_i(t-1). Thus (Zi(v))v=0T(Z_i(v))_v=0^T is a nonnegative supermartingale for the post-round histories, with Zi(0)=1Z_i(0)=1. Let G(v)=∑t=1vAtωtG(v)= _t=1^vA_t _t. Monotonicity of the pending set gives the pathwise identity G(T)=maxi∈[d]Gi(T)G(T)= _i∈[d]G_i(T). Indeed, if a round is positively charged, a task pending at the last such round was pending at every earlier charged round. Its total charge is therefore G(T)G(T); the reverse inequality follows from Ji,t≤AtJ_i,t≤ A_t. If no round is charged, both sides are zero. Since Ni(T)≤qN_i(T)≤ q and Zi(T)≤1EZ_i(T)≤ 1, eκaG(T) ^κ aG(T) =maxi∈[d]eκaGi(T) =E _i∈[d]e^κ aG_i(T) ≤∑i=1deκaGi(T)≤deq. ≤ _i=1^dEe^κ aG_i(T)≤ de^q. Jensen’s inequality yields κaG(T)≤q+logdκ aEG(T)≤ q+ d, which is (27). Before σ, all Ji,tJ_i,t vanish, so Gi(σ−1)=Ni(σ−1)=0G_i(σ-1)=N_i(σ-1)=0. The same tower, supermartingale, and conditional Jensen arguments, started at ℱσF_σ, prove the conditional bounds. ∎ 6.2 One assignment: delivery and play At a nonreserved assignment time σ, the coordinator chooses U=a1<⋯<adU=\a_1<·s<a_d\ and assigns aia_i to player i. Write F=[K]∖UF=[K] U. Choose the auxiliary arm e∈Fe∈ F to minimize w¯e w_e, breaking ties by arm label. The coordinator retains its score register zaiz_a_i for each assigned arm and sends the fixed DOWN records MiDOWN=(σ,ai,e,−log2ξai).M_i DOWN=(σ,a_i,e,- _2 _a_i). (28) A follower accumulates only its score increments after σ, starting from zero; it does not need the initial score. During an assignment, ⊆[d]P [d] contains the followers whose receipts are missing. A receipt for i is the event τt=DOWN,kt=i,Ht(MiDOWN)=0,Y0,t>0.\ _t=DOWN,\ k_t=i,\ H_t(M_i DOWN)=0,\ Y_0,t>0\. For the action state statei∈0,1,2state_i∈\0,1,2\ specified in Section 7.2, call follower i unoccupied if statei=0state_i=0, pending if statei=1state_i=1, and released if statei=2state_i=2. It is occupied exactly when statei∈1,2state_i∈\1,2\. These terms concern the current live assignment; bootstrap row knowledge is defined separately in Section 4. Follower i stores its last decoded start σi _i, increment sum SiS_i, and last increment δi _i, initially zero. Their update rules are in Section 7.2. On DATA, the row supplies independent uniform pilot arms P0,…,Pd∈[K]P_0,…,P_d∈[K]. On DOWN or UP selecting i, define the receiver arm R=Ri,on DOWN,R0,on UP.R= casesR_i,&on DOWN,\\ R_0,&on UP. cases Algorithm 5 Choose the arms on one active nonreserved round 1: On DOWN or UP, let i be the selected follower and define R as above. 2: if the coordinator’s assignment is live and =∅P= then 3: The coordinator draws and plays Xt∼qwtγ(⋅∣U)X_t q^γ_w_t(· U) using its independent sampler coordinate. 4: else if the slot is DATA then 5: The coordinator plays P0P_0. 6: else if DOWN selects i∈i then 7: The coordinator plays SendArm(MiDOWN,R0,RiM_i DOWN,R_0,R_i). 8: else 9: The coordinator plays R0R_0. 10: end if 11: for each follower j do 12: if j is unoccupied then 13: if the slot is DATA then 14: Player j plays PjP_j. 15: else if UP selects j then 16: Player j plays SendArm((σj,Sj,δj),Rj,R0( _j,S_j, _j),R_j,R_0). 17: else 18: Player j plays RjR_j. 19: end if 20: else if j is released or the slot is DATA then 21: Player j plays aja_j. 22: else if UP selects j and R0=eR_0=e then 23: Player j plays e. 24: else if aj=Ra_j=R then 25: Player j plays e. 26: else 27: Player j plays aja_j. 28: end if 29: end for The arm rule also applies during score collection. A pending follower i becomes released exactly on the event Yi,t>0∩(τt=UP,kt=i,R0=e∪τt=DATA,P0=ai).\Y_i,t>0\∩ (\ _t=UP,\ k_t=i,\ R_0=e\∪\ _t=DATA,\ P_0=a_i\ ). These are the UP and DATA certificates. Lemma 10 (The auxiliary arm has bounded fast probability). Suppose w¯j≤wj≤2w¯j w_j≤ w_j≤ 2 w_j for every arm j, and let e minimize w¯j w_j over j∈F=[K]∖Uj∈ F=[K] U. Then qwγ(e∣U)≤23.q^γ_w(e U)≤ 23. Proof. Recall sU=∑i∈Uw¯i−1s_U= _i∈ U w_i^-1 from (17). The function x/(1+sUx)x/(1+s_Ux) is increasing on (0,∞)(0,∞). For every j∈F∖ej∈ F \e\, minimality of w¯e w_e and the weight bounds give wj1+sUw¯j w_j1+s_U w_j ≥w¯j1+sUw¯j≥w¯e1+sUw¯e, ≥ w_j1+s_U w_j≥ w_e1+s_U w_e, w¯e1+sUw¯e w_e1+s_U w_e ≥12we1+sUw¯e. ≥ 12 w_e1+s_U w_e. Using the conditional fast-arm formula, we obtain 1qw(e∣U) 1q_w(e U) =1+∑j∈F∖ewj/(1+sUw¯j)we/(1+sUw¯e) =1+ _j∈ F \e\ w_j/(1+s_U w_j)w_e/(1+s_U w_e) ≥1+|F|−12. ≥ 1+ |F|-12. Thus qw(e∣U)≤2/(|F|+1)q_w(e U)≤ 2/(|F|+1). Since |F|=K−m+1≥2|F|=K-m+1≥ 2 and 0≤γ≤10≤γ≤ 1, the mixture satisfies qwγ(e∣U)≤(1−γ)2|F|+1+γ|F|≤23.q^γ_w(e U)≤(1-γ) 2|F|+1+ γ|F|≤ 23. ∎ Lemma 11 (Deterministic avoidance and receipts). Consider a reference execution during a live assignment. While ≠∅P≠ , no follower is released. On DOWN selecting i∈i , every pending follower j satisfies Aj,t≠RiA_j,t≠ R_i. On such a round, Yi,t Y_i,t =Ht(MiDOWN)rt(Ri) =H_t(M_i DOWN)r_t(R_i) if i is unoccupied, i is unoccupied, Y0,t Y_0,t =rt(Ri) =r_t(R_i) if i is pending and Ht(MiDOWN)=0. i is pending and H_t(M_i DOWN)=0. In particular, a receipt for i implies that i was occupied at the start of the round. Proof. At commitment no follower has decoded the new assignment, so none is released. Suppose ≠∅P≠ at the start of round t. The two possible release events imply, respectively, τt=UP,kt=i,R0=e _t=UP,\ k_t=i,\ R_0=e ⟹A0,t=Ai,t=e, A_0,t=A_i,t=e, τt=DATA,P0=ai _t=DATA,\ P_0=a_i ⟹A0,t=Ai,t=ai. A_0,t=A_i,t=a_i. Both give Yi,t=0Y_i,t=0. Thus neither event can change a pending follower into a released one. Induction over rounds proves the first assertion. Now fix a DOWN round selecting i∈i . Every pending follower j obeys Aj,t=aj,aj≠Ri,e,aj=Ri.A_j,t= casesa_j,&a_j≠ R_i,\\ e,&a_j=R_i. cases In the second case Ri=aj∈UR_i=a_j∈ U whereas e∉Ue∉ U. Both cases therefore give Aj,t≠RiA_j,t≠ R_i. An unoccupied player i plays RiR_i on DOWN. If the hash bit is zero, the coordinator also plays RiR_i, making its reward zero. Therefore Yi,t=Y0,t=0Y_i,t=Y_0,t=0 in this case, and a positive receipt is impossible while i is unoccupied. Suppose i is unoccupied and the hash bit is one. The coordinator plays R0≠RiR_0≠ R_i. Each other unoccupied player j plays Rj≠RiR_j≠ R_i because the tuple is injective. Every pending player avoids RiR_i by the first paragraph. Hence player i is alone on RiR_i and observes rt(Ri)r_t(R_i). If i is pending and the hash bit is zero, the coordinator plays RiR_i. Pending players avoid that arm. Every unoccupied player has a label different from i and uses its distinct tuple arm. Thus the coordinator is alone on RiR_i and observes rt(Ri)r_t(R_i). ∎ Lemma 12 (Assignment and receipt cost). Before a decoder failure, each unresolved DOWN message has positive-test probability at least Pr(Xi,t=1∣ℱt)≥gt8dK (X_i,t=1 _t)≥ g_t8dK (29) on every nonreserved round of its assignment. Once player i has decoded, its missing receipt has the same conditional lower bound. Let σ be a commitment time, and let GhandG_ hand be the support on nonreserved rounds from σ through the last receipt, stopped before the next cutoff or at the horizon, and including the round of a decoder failure if one occurs first. Conditional on the pre-round history ℱσF_σ, [Ghand∣ℱσ]≤2K+8dK1−e−1(2Qdec+2logd+3).E[G_ hand _σ]≤ 2K+ 8dK1-e^-1(2Q_ dec+2 d+3). Proof. The slot is DOWN and selects i with probability 1/(4d)1/(4d). Conditional on ℱtF_t and the arm tuple, the fresh affine hash of the fixed message is a fair bit. Also RiR_i is uniform in [K][K]. If i is unoccupied, Lemma 11 gives a positive receiver observation whenever the bit is one and rt(Ri)>0r_t(R_i)>0. Therefore Pr(Xi,t=1∣ℱt)=14⋅1d⋅12⋅gtK=gt8dK. (X_i,t=1 _t)= 14· 1d· 12· g_tK= g_t8dK. If i has decoded and its receipt is missing, the same lemma gives a positive coordinator observation whenever the bit is zero and rt(Ri)>0r_t(R_i)>0. Its receipt probability is again gt/(8dK)g_t/(8dK). Every receipt is valid. For the first phase, let PtP_t contain the followers whose DOWN word has not been accepted before round t, and set Xi,t=τt=DOWN,kt=i,Yi,t>0.X_i,t=1\ _t=DOWN,\ k_t=i,\ Y_i,t>0\. Stop this phase when Pt=∅P_t= , at an interruption, at a decoder failure, or at the horizon. Before a decoder failure, Lemma 8 gives quota q=2Qdecq=2Q_ dec for each fixed DOWN word, and (29) gives a=1/(8dK)a=1/(8dK) with ωt=gt _t=g_t. Lemma 9 therefore bounds its expected support by K+8dK1−e−1(2Qdec+logd+1).K+ 8dK1-e^-1(2Q_ dec+ d+1). If all DOWN words are accepted before truncation, start the second phase on the next round. Now Pt=i:i’s receipt is missing before round tP_t=\i:$i$'s receipt is missing before round $t$\ and Xi,t=τt=DOWN,kt=i,Ht(MiDOWN)=0,Y0,t>0.X_i,t=1\ _t=DOWN,\ k_t=i,\ H_t(M_i DOWN)=0,\ Y_0,t>0\. Every such event removes i from PtP_t, so q=1q=1; the receipt hazard in (29) again gives a=1/(8dK)a=1/(8dK). Conditioning on this phase’s start and applying Lemma 9 gives K+8dK1−e−1(logd+2).K+ 8dK1-e^-1( d+2). Earlier receipts require no further service. The two phase bounds hold conditional on their respective start histories because the later slot, tuple, and hash coordinates are fresh. Applying the tower property at the second phase’s start gives the displayed bound conditional on ℱσF_σ. Truncation only decreases the nonnegative support sums. ∎ Write χt(j)=rt(j)>0 _t(j)=1\r_t(j)>0\. Lemma 13 (Local release and its cost). After the last assignment receipt, while player i remains pending and the stability bounds hold, its UP-certificate probability is at least χt(e)12dK. _t(e)12dK. (30) Its DATA-certificate probability is χt(ai)/(2K) _t(a_i)/(2K). Use the coordinator’s draw XtX_t as the logical fast arm. Let T consist of the nonreserved rounds after the last receipt and before the next interruption, truncated at the horizon or just after a charged failure. Then ∑t∈(rt(U)+rt(Xt)−∑i=0dYi,t)≤3dK+12dK1−e−1(logd+2). _t (r_t(U)+r_t(X_t)- _i=0^dY_i,t )≤ 3dK+ 12dK1-e^-1( d+2). (31) Proof. By Lemma 11, every follower is occupied when the last receipt arrives, and no follower has yet been released. Thereafter the coordinator always plays Xt∈FX_t∈ F. Suppose UP selects a pending player i and R0=eR_0=e. Player i plays e. Every other pending player j plays aja_j, since aj≠ea_j≠ e; released players also stay on their distinct assigned arms. Therefore, conditional on this slot and tuple event, i receives a positive reward exactly when rt(e)>0r_t(e)>0 and Xt≠eX_t≠ e. The independent fast sampler and Lemma 10 give Pr(τt=UP,kt=i,R0=e,Yi,t>0∣ℱt) ( _t=UP,k_t=i,R_0=e,Y_i,t>0 _t) = = 14dK(1−qwtγ(e∣U))χt(e)≥χt(e)12dK. 14dK(1-q^γ_w_t(e U)) _t(e)≥ _t(e)12dK. On DATA, every slow player stays on its assigned arm and the coordinator chooses from F. Thus player i observes rt(ai)r_t(a_i). The independent event P0=aiP_0=a_i has probability 1/K1/K, and DATA has probability 1/21/2. Therefore Pr(τt=DATA,P0=ai,Yi,t>0∣ℱt)=χt(ai)2K. ( _t=DATA,P_0=a_i,Y_i,t>0 _t)= _t(a_i)2K. Define the predictable charge ωt=qwtγ(e∣U)χt(e)∈[0,1]. _t=q^γ_w_t(e U) _t(e)∈[0,1]. On the interval T, take Pt=i:statei=1 before round tP_t=\i:state_i=1 before round t\ and At=t∈,Pt≠∅.A_t=1\t ,\ P_t≠ \. For this phase set Xi,t=τt=UP,kt=i,R0=e,Yi,t>0.X_i,t=1\ _t=UP,\ k_t=i,\ R_0=e,\ Y_i,t>0\. The displayed event is an UP certificate, so it removes i from PtP_t by the next round; no follower reenters PtP_t before the interruption. Thus q=1q=1. On Ji,t=1\J_i,t=1\ the preceding hazard calculation gives [Xi,t∣ℱt]≥χt(e)12dK≥ωt12dK.E[X_i,t _t]≥ _t(e)12dK≥ _t12dK. Lemma 9 with a=1/(12dK)a=1/(12dK) gives ∑t∈Pt≠∅ωt≤K+12dK1−e−1(logd+2).E _t 1\P_t≠ \ _t≤ K+ 12dK1-e^-1( d+2). (32) The follower’s local certificate determines its removal; the coordinator need not observe that removal. For the reward comparison, each pending follower satisfies Ai,t∈ai,eA_i,t∈\a_i,e\ and every released follower satisfies Ai,t=aiA_i,t=a_i. Since the aia_i are distinct and e∈Fe∈ F, a released follower has Yi,t=rt(ai)Y_i,t=r_t(a_i). A pending follower has Yi,t≥0Y_i,t≥ 0, so in either case Yi,t≥rt(ai)−χt(ai)i is pending.Y_i,t≥ r_t(a_i)- _t(a_i)1\i is pending\. The coordinator can collide with a follower only if Xt=eX_t=e and some follower is pending. Hence Y0,t≥rt(Xt)−rt(e)Xt=e,some follower pending.Y_0,t≥ r_t(X_t)-r_t(e)1\X_t=e,\ some follower pending\. Subtracting these inequalities from the logical reward gives rt(U)+rt(Xt)−∑i=0dYi,t≤ r_t(U)+r_t(X_t)- _i=0^dY_i,t≤ ∑i pendingχt(ai)+rt(e)Xt=e,some follower pending. _i pending _t(a_i)+r_t(e)1\X_t=e,\ some follower pending\. (33) Membership in T and the set PtP_t are determined before round t. For each i∈[d]i∈[d], the DATA-certificate probability calculated above therefore gives 12K∑t∈i∈Ptχt(ai) 12KE _t 1\i∈ P_t\ _t(a_i) =∑t∈i∈Ptτt=DATA,P0=ai,Yi,t>0 =E _t 1\i∈ P_t\1\ _t=DATA,\ P_0=a_i,\ Y_i,t>0\ ≤1. ≤ 1. The last inequality is pathwise: that certificate changes stateistate_i from 11 to 22, so it cannot be counted again before the interruption. Summing over i bounds the expected first term on the right of (33) by 2dK2dK. For the second term, the fast-arm draw has conditional law qwtγ(⋅∣U)q^γ_w_t(· U), and rt(e)≤χt(e)r_t(e)≤ _t(e). Thus [t∈,Pt≠∅rt(e)Xt=e|ℱt]= \! [1\t ,\ P_t≠ \r_t(e)1\X_t=e\\, |\,F_t ]= t∈,Pt≠∅rt(e)qwtγ(e∣U) 1\t ,\ P_t≠ \r_t(e)q^γ_w_t(e U) ≤ ≤ t∈,Pt≠∅ωt. 1\t ,\ P_t≠ \ _t. Taking expectations in (33), summing over t∈t , and using (32) yields ∑t∈(rt(U)+rt(Xt)−∑i=0dYi,t) _t (r_t(U)+r_t(X_t)- _i=0^dY_i,t ) ≤2dK+K+12dK1−e−1(logd+2) ≤ 2dK+K+ 12dK1-e^-1( d+2) ≤3dK+12dK1−e−1(logd+2), ≤ 3dK+ 12dK1-e^-1( d+2), where the last step uses d≥1d≥ 1. ∎ 6.3 Recording rewards and delayed local sums During an assignment, follower i owns arm aia_i and the coordinator owns F. During collection the coordinator owns all arms. Ownership specifies whose observation can supply an arm’s increment. On DATA the row independently selects the recorder source: the coordinator with probability s0=1/2s_0=1/2, or follower i with probability si=1/(2d)s_i=1/(2d). Write Vt∈[0,1]V_t∈[0,1] for the independent coordinate used to thin the observation. For an owner i of arm j, let πi(j) _i(j) be the conditional probability that it plays j on DATA. The other d players’ pilots avoid j with probability ζ=(1−1/K)d≥14.ζ=(1-1/K)^d≥ 14. Define the recording mask for player i observing arm j by i,t(j):=Pℓ,t≠j for every ℓ≠i. Mask_i,t(j):=1\P_ ,t≠ j for every ≠ i\. (34) The test uses every other player’s public pilot coordinate, including dummy pilots of players whose DATA action is an assigned or fast arm. These d coordinates are independent of the owner’s action, so the conditional probability that the mask equals one is always ζ. For the coordinator, score updates are frozen exactly when σ>0σ>0 and t≥gt≥ g, using its registers after StartRound(t)StartRound(t); a new commitment resets g>tg>t and enables updates again. Algorithm 6 Record a DATA increment or one candidate observation 1: One player’s local arm and observation; the output increment is initially zero. 2: On a non-DATA round, stop. 3: Let i be this player. If the public recorder source is not i, stop. 4: Let j and Yi,tY_i,t be its own arm and reward; read VtV_t. 5: if i is an unoccupied follower then 6: if Pℓ,t≠jP_ ,t≠ j for every ℓ≠i ≠ i then 7: Append (t,j,Yi,t,Vt)(t,j,Y_i,t,V_t) to ℬiB_i. 8: end if 9: Stop. 10: end if 11: if i=0i=0, σ>0σ>0, and t≥gt≥ g after StartRound(t)StartRound(t) then 12: Stop. 13: end if 14: if i does not own j or i,t(j)=0 Mask_i,t(j)=0 then 15: Stop. 16: end if 17: if Vt≤ξj/((1/2)siπi(j)ζ)V_t≤ _j/((1/2)s_i _i(j)ζ) then 18: Set the output increment to Δt(j)=⌊DηYi,t/ξj⌋ _t(j)= Dη Y_i,t/ _j . 19: if i=0i=0 then 20: Outside collection, add Δt(j) _t(j) to zjz_j; during collection, pass it to the cumulative update in Algorithm 7. 21: else 22: Add Δt(j) _t(j) to follower i’s local sum SiS_i. 23: end if 24: end if For analysis, let It=jI_t=j when arm j’s owner passes the DATA source, recording-mask, and thinning tests of Algorithm 6; otherwise let It=⊥I_t= . For an unoccupied follower, these tests use its saved observation and the true assignment, even if it has not decoded by the horizon. On an active nonreserved round with learning unfrozen, define, for j∈[K]j∈[K], Δt(j):=It=j⌊Dηrt(j)ξj⌋. _t(j):=1\I_t=j\ Dη r_t(j) _j . Set Δt=0 _t=0 on every other round. At most one coordinate of Δt _t is nonzero. Lemma 14 (Physical recording law). In the reference product-stream execution, on every active nonreserved round with learning unfrozen, the arm ItI_t defined above satisfies (21). On It=jI_t=j, the owner’s observation is rt(j)r_t(j), so its increment is the one specified by (22). Proof. First, d=m−1≤K−2d=m-1≤ K-2 and log(1−x)≥−x/(1−x) (1-x)≥-x/(1-x) for 0≤x<10≤ x<1 give ζ=(1−1/K)d≥exp(−d/(K−1))≥e−1>14.ζ=(1-1/K)^d≥ (-d/(K-1))≥ e^-1> 14. Fix arm j and its owner i conditional on ℱtF_t. The owner’s DATA action is independent of all other pilot coordinates. Thus the probability that DATA occurs, source i is selected, the owner plays j, and the mask holds is 12siπi(j)ζ. 12s_i _i(j)ζ. On this event the owner is alone on j. An unoccupied nonowner uses its pilot, which the mask makes different from j. An occupied slow nonowner uses its distinct assigned arm. A pilot coordinator avoids j by the mask; a fast coordinator chooses from F, outside every slow assigned arm. During collection every physical player uses its pilot. This covers every DATA state. An unoccupied follower has πi(j)=1/K _i(j)=1/K for its assigned arm, whereas an occupied follower has πi(j)=1 _i(j)=1. The coordinator has π0(j)=1/K _0(j)=1/K during collection and while assignment receipts are missing. After all receipts it has π0(j)=qwtγ(j∣U) _0(j)=q^γ_w_t(j U) for j∈Fj∈ F. Therefore 12siπi(j)ζ≥1/(16mK),pilot coordinator or slow owner,qwtγ(j∣U)/16,fast owner. 12s_i _i(j)ζ≥ cases1/(16mK),&pilot coordinator or slow owner,\\ q^γ_w_t(j U)/16,&fast owner. cases The first lower bound is at least ξj _j, since ξj≤2/(AmK)≤1/(16mK) _j≤ 2/(AmK)≤ 1/(16mK). The second is at least ξj _j by (20). In particular, the thinning probability ξj(1/2)siπi(j)ζ _j(1/2)s_i _i(j)ζ (35) belongs to [0,1][0,1]. Multiplication of the raw observation and thinning probabilities gives Pr(It=j∣ℱt) (I_t=j _t) =12siπi(j)ζξj(1/2)siπi(j)ζ = 12s_i _i(j)ζ _j(1/2)s_i _i(j)ζ =ξj. = _j. The remaining probability is 1−∑jξj1- _j _j. The retained observation equals rt(j)r_t(j), so its increment is ⌊Dηrt(j)/ξj⌋ Dη r_t(j)/ _j , as required. ∎ For an unoccupied follower i assigned arm aia_i, we have si=1/(2d)s_i=1/(2d) and πi(ai)=1/K _i(a_i)=1/K. Thus the raw DATA/source/action/mask event has probability ζ/(4dK)ζ/(4dK), and its conditional thinning probability is ξaiζ/(4dK)=4dK 2−hiζ. _a_iζ/(4dK)= 4dK\,2^-h_iζ. This gives the threshold in ψhi _h_i of (41). 7 Scheduling and local implementation For analysis, the reference execution uses the corrected initialization of Section 4 and rejects any decoded word other than the word currently encoded on that channel. Such a rejection does not stop score updates. 7.1 The cutoff and the collection state For an assignment committed at round σ, define g(σ)=minT+1,H(⌊σ/H⌋+1)g(σ)= \T+1,H ( σ/H +1 )\ as the next grid boundary, clipped at the end of the horizon. This clipping changes no action through round T and keeps the stored counter in [T+1][T+1]. Recall that BtB_t is the proposal bit of Section 5 and equals zero on reserved rounds. A public interruption occurs at the start of round u if u=g(σ)u=g(σ) or Bu−1=1B_u-1=1. The assignment’s cutoff is u(σ)=min(g(σ)∪s+1:σ≤s<T,Bs=1∪T+1).u(σ)= (\g(σ)\∪\s+1:σ≤ s<T,\ B_s=1\∪\T+1\ ). For the reference execution, define the calendar-round score by Zj(r):=∑s<rΔs(j),j∈[K].Z_j(r):= _s<r _s(j), j∈[K]. Here Δs _s is the increment of Section 6.3; an increment computed after decoding is attributed to its observation round. Hence Zj(r+1)−Zj(r)=Δr(j)Z_j(r+1)-Z_j(r)= _r(j). After StartRound(t)StartRound(t), the coordinator’s score updates are frozen exactly when σ>0σ>0 and t≥gt≥ g. Thus collection continues recording with the old rates before the old grid boundary, and records no increments from that boundary until a new commitment. At that commitment the anchor and rates are renewed and the new g exceeds t. For a collection interval [u,t)[u,t), define the cumulative increment vector c(t)=∑r=ut−1Δr.c(t)= _r=u^t-1 _r. Algorithm 7 Coordinator updates before and after a round 1: The coordinator is active; initially σ=0σ=0 and g=T+1g=T+1. 2: procedure StartRound(t) 3: if σ>0σ>0, u=T+1u=T+1, and either t=gt=g or Bt−1=1B_t-1=1 then 4: Set u←tu← t and ←[d]P←[d]. 5: Set c←0c← 0 and preserve the known entries of z(u)z(u) and Δu−1 _u-1. 6: Set κ←(1−h)/hκ←(1-h)/h if u<gu<g, and κ←0κ← 0 otherwise. 7: end if 8: if t is nonreserved and either σ=0σ=0 or (u≤t and =∅)(u≤ t and P= ) then 9: if σ=0σ=0 then 10: Initialize every score to zero and every weight to one. 11: else 12: Recover z(u)z(u) and Δu−1 _u-1; set z(t)←z(u)+cz(t)← z(u)+c. 13: end if 14: if σ=0σ=0 or t≥gt≥ g then 15: Renew the anchor and rates by (19); draw U∼pwtU p_w_t by Algorithm 9. 16: else 17: Recover wu−1,wuw_u-1,w_u by Lemma 15; draw U∼νtU _t by Algorithm 9. 18: end if 19: Write U=a1<⋯<adU=\a_1<·s<a_d\ and choose e∈argminj∉Uw¯je∈ _j∉ U w_j, breaking ties by label. 20: Retain zai(t)z_a_i(t) as base scores and construct (t,ai,e,−log2ξai)(t,a_i,e,- _2 _a_i) for each follower i. 21: Set σ←tσ← t and u←T+1u← T+1. 22: Set g←g(t)g← g(t) and ←[d]P←[d]. 23: end if 24: end procedure 25: procedure FinishRound(t,Δt, _t)⊳ Called once after a nonreserved round 26: if u≤tu≤ t then 27: Set c←c+Δtc← c+ _t. 28: if t<gt<g then 29: Set κ←(1−h)κ←(1-h)κ. 30: end if 31: else 32: Read the live assignment’s proposal bit BtB_t. 33: end if 34: end procedure Lemma 15 (Recovery from accumulated increments). Suppose an assignment committed at σ has cutoff u, and its collection ends with a commitment at t. Assume the coordinator retained z(σ)=Z(σ)z(σ)=Z(σ) and, for every i∈[d]i∈[d], obtains Si(u)=∑s=σu−1Δs(ai)S_i(u)= _s=σ^u-1 _s(a_i) and Δu−1(ai) _u-1(a_i). These values and the coordinator’s increments determine Z(t)=Z(u)+c(t),Z(u−1)=Z(u)−Δu−1.Z(t)=Z(u)+c(t), Z(u-1)=Z(u)- _u-1. (36) At this commitment t, the coordinator’s reconstructed register vector satisfies z(t)=Z(t)z(t)=Z(t). Consequently the coordinator can compute wu−1,wu,wtw_u-1,w_u,w_t without retaining the intermediate collection updates. Proof. Ownership changes to the coordinator at u. It knows the old recording rates and every DATA observation used for an increment from u onward. It can therefore compute Δr _r even if some old slow-arm scores Zj(u)Z_j(u) are missing. Starting from c(u)=0c(u)=0, induction over the collection rounds gives c(t)=∑r=ut−1Δr=Z(t)−Z(u).c(t)= _r=u^t-1 _r=Z(t)-Z(u). For each slow arm aia_i, the returned SiS_i sums exactly its increments on [σ,u)[σ,u). Adding the retained initial score zai(σ)=Zai(σ)z_a_i(σ)=Z_a_i(σ) gives Zai(u)Z_a_i(u). The coordinator knows the other cutoff scores from its own observations, so its reconstructed snapshot satisfies z(u)=Z(u)z(u)=Z(u). The supplied data give Δu−1(ai) _u-1(a_i) for every slow arm; the coordinator knows the remaining coordinates from its own observations. Subtracting this vector from Z(u)Z(u) gives Z(u−1)Z(u-1), while z(t)=z(u)+c(t)=Z(t)z(t)=z(u)+c(t)=Z(t) by Algorithm 7. Thus (36) holds. Finally, wr,j=(1+1/D)Zj(r)w_r,j=(1+1/D)^Z_j(r) determines the three weight vectors. No other collection score vector is needed. ∎ 7.2 Local state, message words, and acceptance For an assignment starting at σ, the coordinator retains (σ,(ai)i∈[d],e,(zai(σ))i∈[d])(σ,(a_i)_i∈[d],e,(z_a_i(σ))_i∈[d]). Its structured DOWN record is MiDOWN=(σ,ai,e,−log2ξai)M_i DOWN=(σ,a_i,e,- _2 _a_i) from (28). Follower i retains the last accepted DOWN record (σi,ai,ei,hi)( _i,a_i,e_i,h_i), its increment sum SiS_i, its last increment δi _i, and an action state with values statei=0,unoccupied,1,pending,2,released.state_i= cases0,&unoccupied,\\ 1,&pending,\\ 2,&released. cases Initially (σi,Si,δi,statei)=(0,0,0,0)( _i,S_i, _i,state_i)=(0,0,0,0); the other DOWN fields are unused until the first acceptance. At an interruption, states 11 and 22 become 00, while (σi,Si,δi)( _i,S_i, _i) is retained. On an active nonreserved round, the structured UP record offered by follower i at the arm-choice step is Mi,tUP=(σi,Si,δi),τt=UP,kt=i,statei=0,∅,otherwise.M_i,t UP= cases( _i,S_i, _i),& _t=UP,\ k_t=i,\ state_i=0,\\ ,&otherwise. cases (37) Before any DOWN acceptance, the UP record in (37), when offered, is (0,0,0)(0,0,0). During a known live assignment, statei∈1,2state_i∈\1,2\, so the follower encodes no UP record. While it is unoccupied, its triple remains fixed until it accepts a newer DOWN record. For an assignment (σ,ai)(σ,a_i) with cutoff u, define its ENDPOINT record by MiEND=(σ,∑s=σu−1Δs(ai),Δu−1(ai)),M_i END= (σ, _s=σ^u-1 _s(a_i), _u-1(a_i) ), (38) Once the follower has formed this record, it offers it on its UP channel while statei=0state_i=0, according to (37). Set L=⌈log2(TD+1)⌉L= _2(TD+1) and B=4LB=4L. Let binL:0,…,2L−1→2Lbin_L:\0,…,2^L-1\ _2^L be the binary decomposition. Writing ∥\| for concatenation, encode the two record types by EncDOWN(σ,a,e,h) _ DOWN(σ,a,e,h) =binL(σ)|binL(a)‖binL(e)‖binL(h), =bin_L(σ)\|bin_L(a)\|bin_L(e)\|bin_L(h), (39) EncUP(σ,S,δ) _ UP(σ,S,δ) =binL(σ)|binL(S)‖binL(δ)‖0L. =bin_L(σ)\|bin_L(S)\|bin_L(δ)\|0^L. Here 0L0^L is the all-zero L-bit block. Define the sets of syntactically valid records by ℳDOWN=(σ,a,e,h):σ∈[T],a,e∈[K],a≠e,h∈0,…,4bN,β≤2−h≤2AmK, _ DOWN= \(σ,a,e,h):\ σ∈[T],\ a,e∈[K],\ a≠ e,h∈\0,…,4b_N\,\ β≤ 2^-h≤ 2AmK \, and ℳUP=(0,0,0)∪([T]×0,…,TD×0,…,D).M_ UP=\(0,0,0)\∪ ([T]×\0,…,TD\×\0,…,D\ ). For a decoded bit word w=w1|w2‖w3‖w4w=w_1\|w_2\|w_3\|w_4 with wr∈2Lw_r _2^L, put xr=binL−1(wr)x_r=bin_L^-1(w_r). The slot determines which parser is applied: ParseDOWN(w)=(x1,x2,x3,x4),(x1,x2,x3,x4)∈ℳDOWN,⊥,otherwise,Parse_ DOWN(w)= cases(x_1,x_2,x_3,x_4),&(x_1,x_2,x_3,x_4) _ DOWN,\\ ,&otherwise, cases ParseUP(w)=(x1,x2,x3),w4=0L,(x1,x2,x3)∈ℳUP,⊥,otherwise.Parse_ UP(w)= cases(x_1,x_2,x_3),&w_4=0^L,\ (x_1,x_2,x_3) _ UP,\\ ,&otherwise. cases Set ParseDOWN(⊥)=ParseUP(⊥)=⊥Parse_ DOWN( )=Parse_ UP( )= . For a parsed record M, write M.σM.σ for its first field, and M.S,M.ΔM.S,M. for the second and third fields of an UP record. Lemma 16 (Message field bounds). On every locally valid prefix of Algorithms 7 and 8, the outgoing DOWN records belong to ℳDOWNM_ DOWN, and the offered UP records belong to ℳUPM_ UP. Every field lies in [0,TD][0,TD], so (39) is valid. Proof. An assignment start lies in [T][T], and its distinct arms ai,ea_i,e lie in [K]⊆[0,D][K] [0,D]. By (19) and (20), ξai=2−hi _a_i=2^-h_i is dyadic and satisfies β≤ξai≤2/(AmK)β≤ _a_i≤ 2/(AmK). The construction-branch tuning of Section 8 gives η≥N−4η≥ N^-4 and therefore ξai≥N−4 _a_i≥ N^-4. Since hi=−log2ξaih_i=- _2 _a_i is an integer, 0≤hi≤4log2N≤4bN≤D.0≤ h_i≤ 4 _2N≤ 4b_N≤ D. Thus MiDOWN∈ℳDOWNM_i DOWN _ DOWN. Initially the UP record is (0,0,0)(0,0,0). Subsequently σi∈[T] _i∈[T]. For y∈[0,1]y∈[0,1] and an admissible exponent h, (41) and β≤2−hβ≤ 2^-h give 0≤ψh(y,v)≤Dη 2hy≤Dη/β≤D.0≤ _h(y,v)≤ Dη\,2^hy≤ Dη/β≤ D. The recorder also returns increments in [0,D][0,D]. The sum SiS_i contains at most one such integer per round by (43), and δi _i is one increment; hence 0≤Si≤TD0≤ S_i≤ TD, 0≤δi≤D0≤ _i≤ D. Thus each offered UP record lies in ℳUPM_ UP. As T≥1T≥ 1, all four fields of either record lie in [0,TD][0,TD]. ∎ At a full-batch decoder decision after round t, let M be the parsed DOWN or UP record, or ⊥ . The local acceptance tests are Acci,tDOWN(M)=1 _i,t DOWN(M)=1 ⟺M∈ℳDOWN,σi<M.σ≤t, \ M _ DOWN, _i<M.σ≤ t, (40) Acci,tUP(M)=1 _i,t UP(M)=1 ⟺M∈ℳUP,u≤t,i∈,M.σ=σ. \ M _ UP, u≤ t, i , M.σ=σ. Parsing checks the word’s format; acceptance checks its relation to the receiver’s state. Neither test alone establishes that the decoded record was actually sent. 7.3 Delayed increments from a sparse observation list In Algorithm 6, each follower maintains a log to record its observation. For each follower i∈[d]i∈[d], let ℬiB_i be its initially empty, time-ordered list of candidate observation records. On a round s that i’s declared public row marks nonreserved and DATA, it appends (s,Pi,s,Yi,s,Vs)(s,P_i,s,Y_i,s,V_s) if and only if i is active and unoccupied,source=i,Pℓ,s≠Pi,s(∀ℓ≠i). gatheredi is active and unoccupied, =i,\\ P_ ,s≠ P_i,s (∀ ≠ i). gathered The slot, source, pilot arms, and VsV_s are read from that row; Yi,sY_i,s is the follower’s quantized observation. The append rule does not test Yi,s>0Y_i,s>0 or apply thinning. It also runs before learning launch and during frozen collection whenever the displayed conditions hold. In the product experiment VsV_s is uniform in [0,1][0,1]; the finite implementation uses the corresponding rational coordinate of Section 9.1. On accepting a DOWN word, the follower filters the current list by (43) and then empties it, as specified in Algorithm 8. Recall ζ=(1−1/K)dζ=(1-1/K)^d from Section 6.3. For a rate exponent h, define the contribution of one saved observation by ψh(y,v)=v≤4dK 2−hζ⌊Dη 2hy⌋. _h(y,v)=1\! \v≤ 4dK\,2^-hζ \ Dη\,2^hy . (41) This is the recorder’s thinning and increment rule for a pilot owner. In particular, a record with reward zero contributes zero. After accepting M=(σ,a,e,h)M=(σ,a,e,h) on round t, the follower computes the exclusive endpoint of the observations it must process: ℓ=min(t+1∪g(σ):g(σ)≤t∪s+1:σ≤s<t,Bs=1). = (\t+1\∪\g(σ):g(σ)≤ t\∪\s+1:σ≤ s<t,\ B_s=1\ ). (42) It uses the clipped boundary g(σ)g(σ) and the public row’s past proposal coordinates. To evaluate the minimum, the follower scans BsB_s, σ≤s<tσ≤ s<t, stopping at the first Bs=1B_s=1 or g(σ)g(σ); reserved rounds contribute Bs=0B_s=0 without reading a coordinate. It has not read these bits before acceptance, and if ℓ≤t ≤ t, proposal coordinates from collection rounds in [ℓ,t)[ ,t) remain unread. The proposal BtB_t acts only at the start of round t+1t+1. Thus ℓ=t+1 =t+1 means that the decoded assignment is still live through round t; ℓ≤t ≤ t is its first cutoff. Its recovered sum and last increment are Si S_i =∑(s,j,y,v)∈ℬiσ≤s<ℓ,j=aψh(y,v), = _ subarrayc(s,j,y,v) _i\\ σ≤ s< ,\ j=a subarray _h(y,v), (43) δi _i =∑(s,j,y,v)∈ℬis=ℓ−1,j=aψh(y,v). = _ subarrayc(s,j,y,v) _i\\ s= -1,\ j=a subarray _h(y,v). The second sum contains at most one record. An empty sum is zero. Set statei=1state_i=1 if ℓ=t+1 =t+1, and set statei=0state_i=0 otherwise. Lemma 17 (Exact recovery from sparse records). On a reference execution, the values in (43) equal ∑s=σℓ−1Δs(a) _s=σ -1 _s(a) and Δℓ−1(a) _ -1(a). Proof. Fix a DOWN acceptance after round t, with decoded word (σ,a,e,h)(σ,a,e,h), and let u be this assignment’s first cutoff. Equation (42) gives ℓ=minu,t+1 = \u,t+1\. For s∈[σ,ℓ)s∈[σ, ), player i is active, unoccupied, and owns a. Define the round event Es=s is nonreserved DATA,source=i,Pi,s=a,Pj,s≠a(j≠i).E_s=\s is nonreserved DATA,\ source=i,\ P_i,s=a,\ P_j,s≠ a\ (j≠ i)\. The mask and source tests in Algorithm 6 imply Δs(a)=0 _s(a)=0 on EscE_s^c. On EsE_s, the raw observation probability and thinning threshold are, respectively, 1212d1Kζ=ζ4dK,ξaζ/(4dK)=4dK 2−hζ. 12 12d 1Kζ= ζ4dK, _aζ/(4dK)= 4dK\,2^-hζ. Thus the recorder’s integer update is the pathwise identity Δs(a)=Esψh(Yi,s,Vs)(σ≤s<ℓ). _s(a)=1\E_s\ _h(Y_i,s,V_s) (σ≤ s< ). (44) The logging test is exactly EsE_s, and no record in [σ,ℓ)[σ, ) is erased before this DOWN acceptance: a newer assignment cannot start before the current ENDPOINT is accepted. There is at most one record at each time. Hence ∑(s,j,y,v)∈ℬij=aσ≤s<ℓψh(y,v)=∑s=σℓ−1Δs(a). _ subarrayc(s,j,y,v) _i\\ j=a subarray1\σ≤ s< \ _h(y,v)= _s=σ -1 _s(a). Restricting the same equality to s=ℓ−1s= -1 proves the assertion for δi _i. ∎ 7.4 One local event rule Algorithm 8 One round of the local protocol at player i 1: if i=0i=0, the coordinator is active, and its local state is not † then 2: Apply StartRound(t)StartRound(t) of Algorithm 7. 3: else if i>0i>0, its state is not † , statei∈1,2state_i∈\1,2\, and the assignment is interrupted at t then 4: Set statei←0state_i← 0 and keep Si,δiS_i, _i fixed. 5: end if 6: if the player is inactive or its declared row reserves t then 7: Play its bootstrap-array arm and observe the reward. 8: If i>0i>0, its state is not † , and statei∈1,2state_i∈\1,2\, set δi←0 _i← 0. 9: Apply any complete-block bootstrap update and activation; return. 10: end if 11: if the local state is † then 12: Play arm i+1i+1; apply any complete-block bootstrap update; return. 13: end if 14: Use Algorithm 5 to choose an arm; observe and quantize its reward. 15: Apply Algorithm 6 once. 16: If i>0i>0 was known and live at the arm-choice step, set δi _i to its returned increment, or zero if none was returned. 17: if DOWN selects i>0i>0 and i was unoccupied at the arm-choice step then 18: Feed its observation to DecodeStepDecodeStep in Algorithm 4; parse its output as DOWN to obtain M. 19: if Acci,tDOWN(M)=1Acc_i,t DOWN(M)=1 then 20: Store (σi,ai,ei,hi)←M( _i,a_i,e_i,h_i)← M. 21: Compute ℓ by (42) and (Si,δi)(S_i, _i) by (43). 22: Set statei←ℓ=t+1state_i 1\ =t+1\; discard ℓ and empty ℬiB_i. 23: end if 24: else if i=0i=0, u≤tu≤ t, and UP selects j∈j then 25: Feed its observation to j’s DecodeStepDecodeStep; parse its output as UP to obtain M. 26: if Accj,tUP(M)=1Acc_j,t UP(M)=1 then 27: Store zaj(u)←zaj(σ)+M.Sz_a_j(u)← z_a_j(σ)+M.S and Δu−1(aj)←M.Δ _u-1(a_j)← M. . 28: Remove j from P. 29: end if 30: end if 31: if i=0i=0, t<ut<u, P was nonempty at the arm-choice step, and DOWN selected j then 32: If Ht(MjDOWN)=0H_t(M_j DOWN)=0 and its reward is positive, remove j from P. 33: else if i>0i>0 was pending at the arm-choice step then 34: Set statei←2state_i← 2 if UP selected i, R0=eiR_0=e_i, and its reward is positive, or if DATA has P0=aiP_0=a_i and its reward is positive. 35: end if 36: if i=0i=0 then 37: Apply FinishRound(t,Δt)FinishRound(t, _t) of Algorithm 7 to its returned increment. 38: else if statei∈1,2state_i∈\1,2\ then 39: Read BtB_t after the update. 40: end if 41: Apply any complete-block bootstrap update and activation. Each player has an absorbing local error state † . In this state it performs no learning or transport updates, plays arm i+1i+1 on active nonreserved rounds, and follows its bootstrap-array rule on declared reserved rounds. A player enters † if a local operation has an input or computed output outside its prescribed domain. Appendix A defines the checked operations precisely. Lemma 18 (Local state and sum invariants). Consider the reference execution immediately after round t. If follower i has not applied a DOWN word, then statei=σi=Si=δi=0state_i= _i=S_i= _i=0. Otherwise let σ=σiσ= _i be its last applied assignment and let u be that assignment’s first cutoff, with u=T+1u=T+1 if no cutoff occurs in the horizon. Then Si S_i =∑s=σminu,t+1−1Δs(ai), = _s=σ \u,t+1\-1 _s(a_i), δi _i =Δminu,t+1−1(ai), = _ \u,t+1\-1(a_i), statei=0 _i=0 ⟺u≤t. u≤ t. When t<ut<u, the state is 22 if a release certificate has occurred since this DOWN acceptance, and is 11 otherwise. Proof. Put Lt=minu,t+1L_t= \u,t+1\. We induct over rounds, restarting at each DOWN acceptance. Before the first acceptance, Algorithm 8 gives (statei,σi,Si,δi)=(0,0,0,0)(state_i, _i,S_i, _i)=(0,0,0,0). At a DOWN acceptance after round t, the cutoff scan gives ℓ=Lt =L_t, and Lemma 17 gives Si=∑s=σLt−1Δs(ai),δi=ΔLt−1(ai).S_i= _s=σ^L_t-1 _s(a_i), _i= _L_t-1(a_i). The follower was unoccupied at the arm-choice step, so no release test occurs on this round. The algorithm sets statei=Lt=t+1state_i=1\L_t=t+1\, proving the state assertion at acceptance. Suppose the claim holds after round t−1t-1 and no DOWN word is accepted on round t. If t<ut<u, then Lt=t+1L_t=t+1. On a nonreserved round the recorder supplies Δt(ai) _t(a_i); on a reserved round both this increment and the reset value of δi _i are zero. Hence Si(t)=Si(t−1)+Δt(ai),δi(t)=Δt(ai).S_i(t)=S_i(t-1)+ _t(a_i), _i(t)= _t(a_i). The state stays in 1,2\1,2\ and changes from 11 to 22 precisely upon a release certificate. If t=ut=u, the start-of-round interruption sets the state to 00 and preserves Si,δiS_i, _i; if t>ut>u, these registers remain unchanged. In both cases Lt=uL_t=u, so the formulas hold. This completes the induction. ∎ Lemma 19 (Assignment identities and fixed replies). In the reference execution, every follower applies each assignment at most once. Each assignment has one cutoff and one ENDPOINT per follower. After its cutoff is known, the derived UP word stays fixed until the next DOWN word is applied. During a known live assignment no UP message is encoded. No later assignment is committed before all current ENDPOINTs have been accepted. When a known live follower becomes unoccupied, its DOWN batch is empty. At each assignment’s first cutoff, every coordinator UP batch is empty. An interruption that leaves a follower unoccupied preserves its existing partial DOWN batch. Proof. For successive DOWN acceptances by player i, the predicate (40) requires σinew>σiold _i new> _i old. Hence an assignment start is applied at most once. Fix an assignment (σ,ai)(σ,a_i) with first cutoff u. If its DOWN word is accepted before u, Lemma 18 at the end of round u−1u-1 gives (σi,Si,δi)=(σ,∑s=σu−1Δs(ai),Δu−1(ai))=MiEND.( _i,S_i, _i)= (σ, _s=σ^u-1 _s(a_i), _u-1(a_i) )=M_i END. If acceptance occurs after round t≥ut≥ u, then ℓ=u =u in (42), and Lemma 17 gives the same triple. In either case the state becomes 00 at the cutoff or acceptance. While it is 00, Algorithm 8 does not change SiS_i or δi _i except at a newer DOWN acceptance. Thus the ENDPOINT is unique and fixed. When the state is 11 or 22, Algorithm 5 does not encode an UP word. At the cutoff, =[d]P=[d]. An accepted UP word removes i only if i∈i and its start field equals σ. In the reference execution that word is MiENDM_i END. Algorithm 7 commits a successor only after =∅P= , so every current ENDPOINT is accepted before the next assignment. Let WiDW_i D and WiUW_i U denote the DOWN and UP equation batches. Initially both are empty. At a DOWN acceptance after round v, the full-batch decision gives WiD(v)=∅W_i D(v)= . For v<s<uv<s<u, the known live follower’s DOWN decoder is disabled, so WiD(s)=WiD(v)=∅W_i D(s)=W_i D(v)= . Thus its batch is empty at the first cutoff. If the cutoff precedes DOWN acceptance, the interruption performs no decoder step and leaves the existing partial WiDW_i D unchanged. If ENDPOINT i is accepted after round v, then WiU(v)=∅W_i U(v)= and i∉i . The UP decoder is disabled while i∉i and throughout the next live assignment. Hence WiUW_i U remains empty from v through that assignment’s first cutoff. Every i is removed before the next commitment; induction over assignments proves the UP assertion. ∎ 7.5 Integrating the unobserved refreshes Let t0t_0 be the first commitment. Algorithm 7 initializes the coordinator’s scores, so z(t0)=0=Z(t0)z(t_0)=0=Z(t_0) because all earlier increments vanish. Suppose z(σ)=Z(σ)z(σ)=Z(σ) at a commitment σ. Lemma 19 supplies the correct ENDPOINTs, and Lemma 15 yields z(t)=Z(t)z(t)=Z(t) at the next commitment t. Hence, by induction, the coordinator’s retained register satisfies zai(t)=Zai(t)z_a_i(t)=Z_a_i(t) for each newly selected arm aia_i at every commitment t. Lemma 20 (The assignment law after collection). Let (U^r,z^(r))( U_r, z(r)) be the slow set and score vector of Algorithm 3. Let Z(r)Z(r) be the calendar-round score defined above, and let Uphys(r)U phys(r) be its assigned slow set on a live round. These executions admit a coupling that preserves the product-uniform law of the reference sampler coordinates and, almost surely, satisfies Z(r) Z(r) =z^(r) = z(r) from launch, before the first stability failure, launch, before the first stability failure, Uphys(r) U phys(r) =U^r = U_r on every live round before that failure. every live round before that failure. Suppose the reference coordinator commits at round t after an assignment starting at σ with cutoff u, before stability failure. Let t−G_t^- be generated by the physical states, actions, observations, and coordinates read before the commitment sampler at t, together with (Δs)s<t( _s)_s<t; unread coordinates are excluded. Write pr=pwrp_r=p_w_r. Under the coupling, for every U∈([K]d)U∈ [K]d, Pr(U^t=U∣t−)=:πt(U)=νt(U):=pt(U)+κt(pu(U)−pu−1(U)),t<g(σ),pt(U),t≥g(σ), ( U_t=U _t^-)=: _t(U)= cases _t(U):=p_t(U)+ _t (p_u(U)-p_u-1(U) ),&t<g(σ),\\ p_t(U),&t≥ g(σ), cases (45) where κt _t is the coefficient of Algorithm 7. Proof. We construct the coupling inductively over physical commitments. Scores and live assignments. Initially both executions have zero scores. Suppose that at a physical commitment the two score vectors agree and the physical slow set is coupled to the logical slow set. On every subsequent round on which recording is enabled, Lemma 14 gives the physical recorded arm and increment the same conditional law as the estimate step of Algorithm 3. We therefore use the same (Ir,Δr)(I_r, _r) in both executions. On rounds on which recording is disabled, set Δr=0 _r=0 in both. Hence, since both score vectors receive the same increments, Z(r)=z^(r)Z(r)= z(r) until the first stability failure. While the assignment is live, use the same proposal bit in the two executions. When the physical coordinator draws a fast arm, use that same draw for the logical learner; otherwise draw the logical fast arm independently from its prescribed conditional law. Thus the two slow sets agree throughout the live assignment, up to their common cutoff u. The logical slow-set law during collection. Fix an assignment starting at σ, with cutoff u, whose next physical commitment is at t. During collection, the physical protocol does not use the logical slow set or the auxiliary proposal/refresh coordinates of Algorithm 3. Moreover, the physical proposal coordinates of collection rounds are not read. Hence the physical collection path, the commitment time t, and t−G_t^- may be generated first, and the independent logical refresh coordinates may be generated afterwards without changing their joint law. Let ℋtH_t be t−G_t^- enlarged by all earlier physical-row coordinates, including those not read by the protocol. For u≤r≤tu≤ r≤ t, write μr(U):=Pr(U^r=U∣ℋt). _r(U):= ( U_r=U _t). First suppose that t<g(σ)t<g(σ). Then the cutoff at u was caused by Bu−1=1B_u-1=1, so μu=ρu−1. _u= _u-1. On a nonreserved collection round r, Algorithm 3 gives μr+1=(1−h)μr+hρr. _r+1=(1-h) _r+h _r. Using hρr=pr+1−(1−h)prh _r=p_r+1-(1-h)p_r from (23), we obtain μr+1−pr+1=(1−h)(μr−pr). _r+1-p_r+1=(1-h)( _r-p_r). On reserved rounds both sides remain unchanged. If nu,t:=#r∈[u,t):r is nonreserved,n_u,t:=\#\r∈[u,t):r is nonreserved\, iteration therefore gives μt−pt _t-p_t =(1−h)nu,t(ρu−1−pu) =(1-h)^n_u,t( _u-1-p_u) =(1−h)nu,t+1h(pu−pu−1). = (1-h)^n_u,t+1h(p_u-p_u-1). Algorithm 7 initializes κ=(1−h)/hκ=(1-h)/h at the cutoff and multiplies it by 1−h1-h on each nonreserved collection round. Thus κt=(1−h)nu,t+1h, _t= (1-h)^n_u,t+1h, and consequently μt(U)=pt(U)+κt(pu(U)−pu−1(U))=νt(U). _t(U)=p_t(U)+ _t (p_u(U)-p_u-1(U) )= _t(U). If instead t≥g(σ)t≥ g(σ), the old episode is frozen at g(σ)g(σ) and the commitment at t starts a new episode. Hence Algorithm 3 draws U^t∼pt, U_t p_t, so μt=pt _t=p_t. In either case, Pr(U^t=U∣ℋt)=πt(U). ( U_t=U _t)= _t(U). Since πt _t is t−G_t^--measurable, the tower property also gives Pr(U^t=U∣t−)=πt(U), ( U_t=U _t^-)= _t(U), which proves (45). Coupling the commitment sampler. It remains to make the physical commitment choose exactly U^t U_t without changing the product law of its sampler coordinates. Fix a realization hth_t of the enlarged history ℋtH_t. Let Fht(v)F_h_t(v) be the commitment sampler’s output when its K+1K+1 scalar coordinates are v∈[0,1)K+1v∈[0,1)^K+1, and let λ be product Lebesgue measure on that cube. By Lemma 24, the law of Fht(v)F_h_t(v) is πt _t: it is νt _t within the episode and ptp_t at an initial or post-grid commitment. The logical slow set has the same conditional law even given ℋtH_t. Conditional on U^t=U U_t=U with πt(U)>0 _t(U)>0, sample the physical coordinate vector with distribution Fht(v)=Uλ(dv)πt(U). 1\F_h_t(v)=U\λ(dv) _t(U). The two outputs agree. For every measurable set D0D_0 in the cube, averaging over the logical set gives Pr(v∈D0∣ℋt=ht)=∑Uλ(D0∩Fht−1(U))=λ(D0). (v∈ D_0 _t=h_t)= _Uλ (D_0∩ F_h_t^-1(U) )=λ(D_0). Zero-probability sets U require no conditional choice. Hence the physical vector remains product-uniform and independent of all earlier physical-row coordinates, including unread ones. Subsequent coordinates are drawn freshly. The coupling may correlate this vector with the auxiliary logical randomness, which imposes no restriction on the physical protocol’s marginal law. Induction over commitments now gives Z(r)=z^(r)Z(r)= z(r) before the first stability failure and Uphys(r)=U^rU phys(r)= U_r on every live round before that failure, completing the proof. ∎ 7.6 Score collection and total cost of interruptions In the product-stream reference execution, fix the rounded reward matrix and reserved mask. Fix a transfer starting at a stopping time s: a cutoff starts score collection, while the first commitment starts the initial transfer. Let C contain nonreserved rounds from the cutoff through the round before the next commitment. Let ℋH contain nonreserved rounds from that commitment through the last DOWN receipt, or through the round before the next cutoff if a receipt remains missing. Let ℛR contain the subsequent nonreserved rounds before that cutoff. For the initial transfer =∅C= and ℋH begins at s; any later phase is empty if its start does not occur. Include a round on which a failure is detected, and stop all phases thereafter or at the horizon. Here a failure is a decoder failure of Lemma 8 or the first weight-doubling update. Use the capped support envelope g¯t:=minm,gt. g_t:= \m,g_t\. Both a comparator’s reward and the reward of any logical m-set are at most g¯t g_t. This nonnegative envelope permits comparison with the full auxiliary regret even when that regret is negative on selected communication rounds. Define the phase bounds Bcol B_ col :=2K+16dK1−e−1(2Qdec+logd+1), :=2K+ 16dK1-e^-1(2Q_ dec+ d+1), Bhand B_ hand :=2K+8dK1−e−1(2Qdec+2logd+3), :=2K+ 8dK1-e^-1(2Q_ dec+2 d+3), Brel B_ rel :=3dK+12dK1−e−1(logd+2), :=3dK+ 12dK1-e^-1( d+2), and their sum Ctr C_ tr :=Bcol+Bhand+Brel :=B_ col+B_ hand+B_ rel (46) =O(dK[Qdec+logd+1])=O(mKΛ). =O\! (dK[Q_ dec+ d+1] )=O(mK ). Lemma 21 (Conditional support-envelope cost of one transfer). Define the stopped transfer charge by Js:=∑t∈∪ℋg¯t+∑t∈ℛ(rt(Ut)+rt(Xt)−∑i=0dYi,t). J_s:= _t g_t+ _t (r_t(U_t)+r_t(X_t)- _i=0^dY_i,t ). (47) Then conditional on the pre-round history ℱsF_s, [Js∣ℱs]≤Ctr.E[J_s _s]≤ C_ tr. Proof. By Lemma 19, an old DOWN message stays fixed while it remains undecoded. On DOWN selecting its unoccupied recipient i, every other slow player uses a distinct tuple arm. Hash bit one makes the coordinator use R0≠RiR_0≠ R_i. While this DOWN decoder is pending, its conditional positive-test probability is Pr(τt=DOWN,kt=i,Yi,t>0∣ℱt)=14⋅1d⋅12⋅gtK=gt8dK. ( _t=DOWN,\,k_t=i,\,Y_i,t>0 _t)= 14· 1d· 12· g_tK= g_t8dK. This is the same lower bound as (29). Once player i forms its UP score, the word stays fixed. On UP selecting i, the coordinator listens on R0R_0. Every other slow player uses a distinct RjR_j, and hash bit one makes player i use Ri≠R0R_i≠ R_0. While this UP decoder is pending, its conditional positive-test probability is likewise Pr(τt=UP,kt=i,Y0,t>0∣ℱt)=14⋅1d⋅12⋅gtK=gt8dK. ( _t=UP,\,k_t=i,\,Y_0,t>0 _t)= 14· 1d· 12· g_tK= g_t8dK. In the first phase, let PtP_t contain exactly the followers whose old DOWN word remains unaccepted before round t, and take Xi,t=τt=DOWN,kt=i,Yi,t>0X_i,t=1\ _t=DOWN,\,k_t=i,\,Y_i,t>0\. The phase ends when this set empties or collection is truncated. Each old DOWN word is fixed; Lemma 8 gives q=2Qdecq=2Q_ dec, and the DOWN hazard above gives a=1/(8dK)a=1/(8dK) for ωt=gt _t=g_t. If the first phase is not truncated, the second phase starts at u when all old DOWN words were accepted before u; otherwise it starts on the round after their last acceptance. In that phase let PtP_t be the followers whose current ENDPOINT remains unaccepted, and set Xi,t=τt=UP,kt=i,Y0,t>0X_i,t=1\ _t=UP,\,k_t=i,\,Y_0,t>0\. Lemma 19 makes each owed ENDPOINT fixed; the same decoder quota and the UP hazard above apply. Lemma 9, conditional on the start of either phase, bounds that phase’s expected support by K+8dK1−e−1(2Qdec+logd+1).K+ 8dK1-e^-1(2Q_ dec+ d+1). If =∅C= there is no charge. Otherwise the tower property at the second phase’s start gives [∑t∈gt|ℱs]≤2[K+8dK1−e−1(2Qdec+logd+1)]=Bcol.E\! [ _t g_t\, |\,F_s ]≤ 2 [K+ 8dK1-e^-1(2Q_ dec+ d+1) ]=B_ col. DOWN and UP channels may both operate during either phase; the partition only assigns each round’s gtg_t to one bound. Earlier accepted ENDPOINTs are omitted from the second PtP_t. Repeated interruptions do not change the fixed cutoff or either message, so they do not reset a batch. If handover starts at a commitment σH _ H, Lemma 12, applied conditional on ℱσHF_ _ H, gives [∑t∈ℋgt|ℱσH]≤Bhand.E\! [ _t g_t\, |\,F_ _ H ]≤ B_ hand. If release starts at round σR _ R, the DATA-certificate calculation and weighted service bound in the proof of Lemma 13 apply conditional on ℱσRF_ _ R. Thus (31) gives [∑t∈ℛ(rt(Ut)+rt(Xt)−∑i=0dYi,t)|ℱσR]≤Brel.E\! [ _t (r_t(U_t)+r_t(X_t)- _i=0^dY_i,t )\, |\,F_ _ R ]≤ B_ rel. For t∈∪ℋt , g¯t≤gt g_t≤ g_t, so the collection and handover support bounds apply to the new charge. Empty phases contribute zero. Applying the tower property at the starts of handover and release, and summing the three phase bounds, gives [Js∣ℱs]≤Bcol+Bhand+Brel=Ctr.E[J_s _s]≤ B_ col+B_ hand+B_ rel=C_ tr. ∎ Proposition 22 (Total stopped transport envelope). Consider the product-stream reference execution launched with zero scores and a fixed reserved mask. Let τbad _ bad be the first decoder failure or first weight-doubling update, with value T+1T+1 if neither occurs. Include its round in the phase charges and stop afterwards. Let ∗,ℋ∗,ℛ∗C_*,H_*,R_* be the disjoint unions of these stopped collection, handover, and release phases. Define Jstop:=∑t∈∗∪ℋ∗g¯t+∑t∈ℛ∗(rt(Ut)+rt(Xt)−∑i=0dYi,t).J_ stop:= _t _* _* g_t+ _t _* (r_t(U_t)+r_t(X_t)- _i=0^dY_i,t ). With CtrC_ tr from (46), δ=N−8δ=N^-8, and A=256A=256, Jstop≤Ctr[(4AmK+32)ηT+2].EJ_ stop≤ C_ tr [(4AmK+32)η T+2 ]. (48) Moreover, Pr(τbad≤T)≤2δ ( _ bad≤ T)≤ 2δ. Proof. Number of transfers. For each round t, let LtL_t indicate that the live assignment’s proposal coordinate is read before the stopping event, and let P=∑t=1TLtBtP= _t=1^TL_tB_t. Immediately before that coordinate is read, LtL_t is determined and BtB_t is Bernoulli with parameter h=4AmKηh=4AmKη. Hence [LtBt∣ℱtprop]=hLt,P=h∑t=1TLt≤hT,E[L_tB_t _t prop]=hL_t, =h _t=1^TEL_t≤ hT, where ℱtpropF_t prop is the history immediately before a possible proposal read. Let M count transfers started through τbad _ bad. Apart from the initial transfer, a transfer begins only after a read proposal or at a grid boundary; a grid boundary inside collection starts no additional transfer. Allowing one final incomplete transfer, M≤P+⌊T/H⌋+2.M≤ P+ T/H +2. Since H=⌊(16η)−1⌋≥(32η)−1H= (16η)^-1 ≥(32η)^-1, M≤(4AmK+32)ηT+2.EM≤(4AmK+32)η T+2. (49) Conditional envelope charges. For k∈[T+1]k∈[T+1], let σk _k be the start of the k-th counted transfer, or T+1T+1 if it does not occur. Set Jk=JσkJ_k=J_ _k for an existing transfer, using Lemma 21’s stopped phases, and set Jk=0J_k=0 otherwise. Each summand is in [−m,m][-m,m], so these charges are integrable. That lemma gives [Jk∣ℱσk]≤Ctrσk≤T.E[J_k _ _k]≤ C_ tr1\ _k≤ T\. Since M=∑kσk≤TM= _k1\ _k≤ T\, the tower property yields ∑kJk≤CtrM.E _kJ_k≤ C_ trEM. (50) Collection ends before the next commitment round; handover includes its last receipt round; release starts on the following round and ends before the next cutoff. Thus the phase sets of distinct transfers are disjoint and cover every nonreserved round from launch through minτbad,T \ _ bad,T\. In particular, ∑kJk=Jstop _kJ_k=J_ stop, which proves (48). Failure probability. The decoder bound applies before a weight doubling, and the stability bound controls the first weight doubling. Consequently, Pr(τbad≤T)≤δN4+N−8≤2δ. ( _ bad≤ T)≤ δN^4+N^-8≤ 2δ. The failure round is included because its actions and rewards occur before the decoder decision or weight update detecting the failure. No learning-regret estimate has been conditioned on this event or truncated at a decoder failure; the full auxiliary sum is used in Section 8. ∎ 8 Proof of the main theorem Proof of Theorem 1. Use the array constants chosen in the proof of Lemma 29 and the message quota (26). The transport proofs give an absolute constant in Ctr=O(mKΛ)C_ tr=O(mK ). Choose C1C_1 large enough to dominate it and all learning coefficients, and then enlarge the branch constant CbC_b one final time if necessary. Rational tuning. Let =⌈log2((Km)+1)⌉J= _2( Km+1) and W=C1m2K2bNW=C_1m^2K^2b_N. Use the largest power of two η satisfying η≤(2AmKLstab)−1,η2WT≤.η≤(2AmKL_ stab)^-1, η^2WT . Here Lstab=⌈log2(2K(T+1)N8)⌉=O(Λ)L_ stab= _2(2K(T+1)N^8) =O( ). The quantity /(WT) J/(WT) satisfies the first constraint whenever T≥4A2m2K2Lstab2W=4A2Lstab2C1bN.T≥ 4A^2m^2K^2L_ stab^2JW= 4A^2L_ stab^2JC_1b_N. The right side is at most CΛCJ . Since (Km)≤2K Km≤ 2^K, we have ≤K+1J≤ K+1. On the construction branch, k⋆≤Kk_ ≤ K gives KT KT ≥k⋆T>CbV^≥CbK5/2TΛ2, ≥ k_ T>C_b V≥ C_bK^5/2 T ^2, T T >Cb2K3Λ4. >C_b^2K^3 ^4. Choosing CbC_b sufficiently large therefore ensures the rate cap. The largest-dyadic rule yields 12WT<η≤WT. 12 JWT<η≤ JWT. (51) Also ≍log(Km)J Km. The lower bound above gives η≥c/(mKTΛ)≥c/N2η≥ c/(mK T )≥ c/N^2 for a universal c>0c>0. Increasing CbC_b ensures N≥c−1/2N≥ c^-1/2, and hence η≥N−4η≥ N^-4, as required by the finite-arithmetic bounds in Section 9. Whole-row concentration. Let 0G_0 be the event that Algorithm 10 publishes a complete table whose masks and arm arrays satisfy Lemma 29 and Lemma 33. Their failure bounds give Pr(0)≥1−CN−40 (G_0)≥ 1-CN^-40. Fix masks and arrays in 0G_0, and let 1,…,M R_1,…, R_M be the independent finite control rows sampled by the constructor. For a denominator-D reward matrix r and j∈[M]j∈[M], let Fj,r(Rj)∈[−mT,mT]F_j,r(R_j)∈[-mT,mT] be the conditional expected regret under reference execution, where the expectation is taken over private bootstrap randomness conditional on J=jJ=j and on the realized row RjR_j. Put ℰ:=Efalse∪Eamb∪Estab,Ej,r(Rj):=Pr(ℰ∣J=j,Rj)∈[0,1],E:=E_ false∪ E_ amb∪ E_ stab, E_j,r(R_j):= (E J=j,R_j)∈[0,1], where EfalseE_ false and EambE_ amb are the decoder events of Appendix A.2, and EstabE_ stab is the weight-stability failure of Lemma 5. The reference uses the corrected bootstrap state and rejects a decoded word other than the current encoded word. Its correction precedes every control access, so Fj,rF_j,r and Ej,rE_j,r depend on RjR_j alone as j varies. Write μF(r):=1M∑j=1MFj,r(j),μE(r):=1M∑j=1MEj,r(j), _F(r):= 1M _j=1^MEF_j,r( R_j), _E(r):= 1M _j=1^MEE_j,r( R_j), and F¯r:=1M∑jFj,r(Rj),E¯r:=1M∑jEj,r(Rj). F_r:= 1M _jF_j,r(R_j), E_r:= 1M _jE_j,r(R_j). For fixed r, independence across j and Hoeffding’s inequality [12] yield PrF¯r>μF(r)+V \ F_r> _F(r)+V \ ≤e−MV2/(2m2T2), ≤ e^-MV^2/(2m^2T^2), PrE¯r>μE(r)+VmT \ E_r> _E(r)+ VmT \ ≤e−2MV2/(m2T2). ≤ e^-2MV^2/(m^2T^2). There are (D+1)KT(D+1)^KT denominator-D matrices, and MV22m2T2≥2K7TΛ4>KTlog(D+1)+40Λ+log2. MV^22m^2T^2≥ 2K^7T ^4>KT (D+1)+40 + 2. Let GrowG_ row be the event that the following inequalities hold simultaneously F¯r F_r ≤μF(r)+V, ≤ _F(r)+V, (52) E¯r E_r ≤μE(r)+VmT. ≤ _E(r)+ VmT. (53) Thus a union bound, conditional on 0G_0, gives an event rowG_ row with Pr(rowc∣0)≤CN−40 (G_ row^c _0)≤ CN^-40. Hence pub:=0∩rowG_ pub:=G_0 _ row has probability at least 1−CN−321-CN^-32. Regret decomposition. Fix a public output in pubG_ pub and a rounded reward matrix r. On ℰboot∩ℰcE_ boot ^c, Proposition 3 couples initialization, the decoder rule couples subsequent messages, and Lemma 27 excludes a local domain error. If ℜTact R_T act and ℜTref R_T ref are the two complete realized regrets, then |ℜTact−ℜTref|≤2mTℰbootc∪ℰ.| R_T act- R_T ref|≤ 2mT1\E_ boot^c \. Taking expectations conditional on the published output gives RT(r)≤F¯r+2mT(Δboot+E¯r).R_T(r)≤ F_r+2mT( _ boot+ E_r). (54) Recall the two product-stream estimates needed for the reference. Write the auxiliary-learning bound and the stopped transport bound, with the failure-tail allowance established below, as ℒη _η :=2log(Km)η+(2AmK2+A4(K−m+1)Lstab)ηT+mTηD+CmTN−8, := 2 Kmη+ (2AmK^2+ A4(K-m+1)L_ stab )η T+ mTη D+CmTN^-8, η _η :=Ctr[(4AmK+32)ηT+2]+4mTδ. :=C_ tr [(4AmK+32)η T+2 ]+4mTδ. Let τL∈[T+1] _ L∈[T+1] be the reference launch round, with τL=T+1 _ L=T+1 if no launch occurs. For every comparator S∈S , rt(S)≤gtr_t(S)≤ g_t, so Proposition 3(i) gives ∑t<τLrt(S)≤G(τL−1)≤CQboot. _t< _ Lr_t(S)≤ G( _ L-1)≤ CQ_ boot. Lemma 33(i) bounds the reserved-round charge by m(2pT+C0Λ)m(2pT+C_0 ). Here is the pathwise accounting that connects the two estimates. Fix S∈S and put ct=rt(S)c_t=r_t(S), ℓt=rt(Ut)+rt(jt) _t=r_t(U_t)+r_t(j_t), and yt=∑iYi,ty_t= _iY_i,t on enabled rounds. Let τbad _ bad and JstopJ_ stop be as in Proposition 22. On an enabled collection or handover round through τbad _ bad, ct−yt=(ct−ℓt)+(ℓt−yt)≤(ct−ℓt)+g¯t,c_t-y_t=(c_t- _t)+( _t-y_t)≤(c_t- _t)+ g_t, because ℓt≤g¯t=minm,gt _t≤ g_t= \m,g_t\ and yt≥0y_t≥ 0. On a frozen collection round, the auxiliary learner has no summand and ct−yt≤g¯tc_t-y_t≤ g_t. On a release round, the coupling of Lemma 20 identifies jt=Xtj_t=X_t, so its remaining discrepancy ℓt−yt _t-y_t is included in JstopJ_ stop. Retain the full auxiliary sum over A defined in Section 5. Its tail after τbad _ bad is at least −mTτbad≤T-mT1\ _ bad≤ T\, and the actual-regret tail is at most mTτbad≤TmT1\ _ bad≤ T\. Consequently, ℜTref(S)≤ R_T ref(S)≤ CQboot+m(2pT+C0Λ)+∑t∈(ct−ℓt)+Jstop CQ_ boot+m(2pT+C_0 )+ _t (c_t- _t)+J_ stop (55) +2mTτbad≤T. +2mT1\ _ bad≤ T\. The failure round itself is included in the valid comparison since its rewards precede the failure-detecting update. Taking expectations uses the full auxiliary bound of Proposition 7, the stopped envelope bound, and Pr(τbad≤T)≤2δ ( _ bad≤ T)≤ 2δ. In particular, it does not condition the learner on successful decoding or stop its estimate filtration at a decoder failure. Lemma 25 transfers both complete-reference regret and the event probability from ideal product rows to finite product rows with allowance ϵsamp _ samp. The accounting above and the decoder and stability bounds give μF(r) _F(r) ≤CQboot+m(2pT+C0Λ)+ℒη+η+2mTϵsamp, ≤ CQ_ boot+m(2pT+C_0 )+L_η+T_η+2mT _ samp, (56) μE(r) _E(r) ≤δ/N4+N−8+ϵsamp. ≤δ/N^4+N^-8+ _ samp. (57) Combining (52)–(57) with (54) gives RT(r)≤ R_T(r)≤ CQboot+m(2pT+C0Λ)+ℒη+η+CV CQ_ boot+m(2pT+C_0 )+L_η+T_η+CV (58) +CmT(Δboot+δ+N−8+ϵsamp). +CmT( _ boot+δ+N^-8+ _ samp). The choice of C1C_1 makes W=C1m2K2bNW=C_1m^2K^2b_N dominate the coefficients of ηTη T in ℒη+ηL_η+T_η. Indeed, Ctr=O(mKΛ)C_ tr=O(mK ), Lstab=O(Λ)L_ stab=O( ), and bN≍Λb_N . Since log(Km)≤(log2) Km≤( 2)J, the combined inequality becomes RT(r)≤C[ R_T(r)≤ C [ Qboot+mpT+mKΛ+V+η+WηT+mTηD Q_ boot+mpT+mK +V+ Jη+Wη T+ mTη D (59) +mT(Δboot+δ+N−8+ϵsamp)]. +mT( _ boot+δ+N^-8+ _ samp) ]. Bounds for the terms. Appendix B.9 gives dℓcol/Scol≤ϵarrd _ col/S_ col≤ _ arr and L/Akey≤ϵarr/(8e)L/A_ key≤ _ arr/(8e). Using Bblk≤T/nB_ blk≤ T/n in (13), then ϵarr=cϵK3bN2/(m3T) _ arr=c_εK^3b_N^2/(m^3T), gives mTΔboot≤Cm3T2ϵarrn+O(1)=O(K3TbN2n)+O(1)=O(V).mT _ boot≤ C m^3T^2 _ arrn+O(1)=O\! ( K^3Tb_N^2n )+O(1)=O(V). The remaining terms of (13) contribute O(1)O(1) because mT/N=O(1)mT/N=O(1) and m2T2e−C0Λ=O(1)m^2T^2e^-C_0 =O(1). Also Lbit≥64log2NL_ bit≥ 64 _2N and δ=N−8δ=N^-8 imply mT(δ+N−8+ϵsamp)≤CmT(N−8+(K2+bN)TN−64)=O(1).mT(δ+N^-8+ _ samp)≤ CmT (N^-8+(K^2+b_N)TN^-64 )=O(1). The dyadic choice of η in (51) gives η+WηT≤CWT≤CmKTΛlog(Km)≤CV. Jη+Wη T≤ C JWT≤ CmK T Km≤ CV. Since D≥N2D≥ N^2, mTηD≤2mTDWT≤CKΛT=O(V). mTη D≤ 2mTD WTJ≤ CK JT=O(V). Finally, pT≤TpT≤ T and 1/p≤4+2T1/p≤ 4+2 T yield Qboot=O(V)Q_ boot=O(V) and mpT+mKΛ=O(V)mpT+mK =O(V). Substitution in (59) proves RT(r)=O(V)R_T(r)=O(V) for every rounded matrix on the fixed public output. For an arbitrary original reward matrix rorigr orig, rounding down changes each comparator reward by at most m/Dm/D per round, whereas the actual unrounded reward is at least the rounded reward. Consequently, RT(rorig)≤RT(r)+mTD=O(V).R_T(r orig)≤ R_T(r)+ mTD=O(V). All bounds hold simultaneously for every rounded matrix on the same output in pubG_ pub, and the rounding comparison is pathwise. This proves the required quantifier over all oblivious reward matrices. On the complementary parameter branch use a fixed assignment to m distinct arms. For two m-sets S,S′S,S , |S∖S′|≤k⋆|S S |≤ k_ , so rt(S)−rt(S′)≤k⋆r_t(S)-r_t(S )≤ k_ . The resulting regret is at most k⋆T≤CbV^=O(V)k_ T≤ C_b V=O(V). This proves (3) for every horizon. The computational bounds follow from Section 9 below. ∎ 9 Finite computation and sampling We bound the computations performed by the preceding protocol. At each commitment, Algorithm 7 draws an assignment using Algorithm 9 below: the initial and post-grid draws use one product distribution, and a within-episode draw after collection uses three signed product terms. The two-term refresh in Algorithm 3 belongs to the logical execution; the physical coordinator implements its accumulated effect at commitment. Algorithm 10 constructs the finite public rows used for these draws and for control. During play, Algorithm 12 calls the bootstrap decoder Algorithm 11 at complete block boundaries, whereas Algorithm 8 calls the control decoder Algorithm 4 on enabled DOWN and UP channels. Arithmetic model. We use a random-access bit-cost model with numerical inputs K,m,TK,m,T. For a reward observation Y∈[0,1]Y∈[0,1], the feedback interface supplies ⌊DY⌋ DY , including D when Y=1Y=1. Thus processing an arbitrary real reward requires only its prescribed quantization. All subsequent operations use integers, rational numbers, and random bits. 9.1 A direct sampler for the assignment law For 1≤r≤31≤ r≤ 3, let v(1),…,v(r)∈ℚ>0Kv^(1),…,v^(r) _>0^K be weight vectors and let c1,…,cr∈ℚc_1,…,c_r be coefficients. The coefficients may have either sign. Define the mass of an m-set by f(S)=∑ℓ=1rcℓ∏i∈Svi(ℓ).f(S)= _ =1^rc_ _i∈ Sv_i^( ). (60) For each component, define suffix sums Eℓ(i,k)=∑A⊆i,…,K|A|=k∏j∈Avj(ℓ).E_ (i,k)= _ subarraycA \i,…,K\\\ |A|=k subarray _j∈ Av_j^( ). An empty product is one; an impossible subset size gives zero. In particular, Eℓ(K+1,0)=1E_ (K+1,0)=1 and Eℓ(K+1,k)=0E_ (K+1,k)=0 for k≠0k≠ 0. The recurrence is Eℓ(i,k)=Eℓ(i+1,k)+vi(ℓ)Eℓ(i+1,k−1).E_ (i,k)=E_ (i+1,k)+v_i^( )E_ (i+1,k-1). (61) Algorithm 9 Direct subset sampling and orientation 1: Weight vectors and coefficients in (60), with f(S)≥0f(S)≥ 0 and ∑|S|=mf(S)=1 _|S|=mf(S)=1; anchor w¯ w. 2: Compute Eℓ(i,k)E_ (i,k) by (61) for i=K,…,1i=K,…,1 and k=0,…,mk=0,…,m. 3: Set S←∅S← , k←mk← m, and aℓ←cℓa_ ← c_ for ℓ=1,…,r =1,…,r. 4: for i=1,…,Ki=1,…,K do 5: Compute W=∑ℓ=1raℓEℓ(i,k)W= _ =1^ra_ E_ (i,k) and Win=∑ℓ=1raℓvi(ℓ)Eℓ(i+1,k−1)W_ in= _ =1^ra_ v_i^( )E_ (i+1,k-1). 6: if W≤0W≤ 0 or Win∉[0,W]W_ in∉[0,W] then 7: Enter the local error state of Appendix A.1 and stop. 8: end if 9: if an independent uniform coordinate is less than Win/W_ in/W then 10: Set S←S∪iS← S∪\i\ and k←k−1k← k-1. 11: Set aℓ←aℓvi(ℓ)a_ ← a_ v_i^( ) for every ℓ . 12: end if 13: end for 14: Draw j∈Sj∈ S with probabilities αj(S) _j(S) from (16). 15: Return U=S∖jU=S \j\. Lemma 23 (Sampling nonnegative sums of products). Under its stated hypotheses, Algorithm 9 samples S with law f. Its output satisfies Pr(U)=∑j∉Uf(U∪j)αj(U∪j). (U)= _j∉ Uf(U∪\j\) _j(U∪\j\). It uses O(rKm)O(rKm) rational operations and at most K+1K+1 uniform coordinates. Every reached prefix has W>0W>0, so the local error test never fires under exact sampling. Proof. Fix i∈[K]i∈[K] and a prefix A⊆1,…,i−1A \1,…,i-1\ reached before arm i is processed. With k=m−|A|k=m-|A|, its compatible completions are (A,i)=A∪B:B⊆i,…,K,|B|=k.C(A,i)=\A∪ B:B \i,…,K\,\ |B|=k\. The algorithm has aℓ=cℓ∏j∈Avj(ℓ)a_ =c_ _j∈ Av_j^( ). Expanding the suffix sums in (61) gives W W =∑S∈(A,i)f(S), = _S (A,i)f(S), Win W_ in =∑S∈(A,i)i∈Sf(S). = _ subarraycS (A,i)\\ i∈ S subarrayf(S). In particular, 0≤Win≤W0≤ W_ in≤ W. We prove by induction on i that the probability of reaching a prefix A equals its completion mass W. At i=1i=1 this mass is ∑|S|=mf(S)=1 _|S|=mf(S)=1. If a reached prefix has mass W>0W>0, the two branches in Algorithm 9 have probabilities Pr(reach A∪i)=WWinW=Win, (reach A∪\i\)=W W_ inW=W_ in, and Pr(reach A after rejecting i)=W(1−WinW)=W−Win. (reach A after rejecting i)=W (1- W_ inW )=W-W_ in. Both equal the completion masses of their respective prefixes. A zero-mass branch is reached with probability zero, so every evaluated denominator is positive. At i=K+1i=K+1, the completion mass of a reached m-set S is f(S)f(S). Conditional on S, the independent orientation coordinate removes j∈Sj∈ S with probability αj(S) _j(S). Summing over j proves the stated law of U. There are r(K+1)(m+1)r(K+1)(m+1) suffix entries, each using at most one addition and one multiplication. The loop uses O(rK)O(rK) further operations and at most K coordinates; orientation uses O(m)O(m) operations and one coordinate. The totals are O(rKm)O(rKm) exact rational operations and at most K+1K+1 coordinates. ∎ Lemma 24 (Direct sampling after collection). Suppose an assignment ends at cutoff u, and collection finishes at commitment t before the next grid boundary and before stability failure. Let nu,tn_u,t count the nonreserved rounds in [u,t)[u,t), set κ=(1−h)nu,t+1/hκ=(1-h)^n_u,t+1/h, and define ft(S)=Qwt(S)+κ(Qwu(S)−Qwu−1(S)).f_t(S)=Q_w_t(S)+κ (Q_w_u(S)-Q_w_u-1(S) ). (62) Then ftf_t is a probability distribution. Algorithm 9 with the three components (v(1),c1)=(wt,1(wt)),(v(2),c2)=(wu,κ(wu)),(v(3),c3)=(wu−1,−κ(wu−1))(v^(1),c_1)= (w_t, 1Z(w_t) ), (v^(2),c_2)= (w_u, κZ(w_u) ), (v^(3),c_3)= (w_u-1, -κZ(w_u-1) ) returns the within-episode commitment law νt _t used by Algorithm 7. With one component (wt,1/(wt))(w_t,1/Z(w_t)), its output law is pwtp_w_t, the initial and post-grid commitment law in that algorithm. For comparison, the logical refresh law ρs _s in (23) is sampled using the two components (v(1),c1)=(ws+1,1h(ws+1)),(v(2),c2)=(ws,−1−h(ws)).(v^(1),c_1)= (w_s+1, 1hZ(w_s+1) ), (v^(2),c_2)= (w_s,- 1-hhZ(w_s) ). Proof. For every permitted update before stability failure, Lemma 5 gives Qws+1(S)≥Qws(S)1+h≥(1−h)Qws(S).Q_w_s+1(S)≥ Q_w_s(S)1+h≥(1-h)Q_w_s(S). In particular, the update on round u−1u-1 satisfies Qwu(S)≥(1−h)Qwu−1(S)Q_w_u(S)≥(1-h)Q_w_u-1(S). Scores do not change on reserved rounds, so iteration over the nu,tn_u,t nonreserved rounds of [u,t)[u,t) gives Qwt(S)≥(1−h)nu,tQwu(S).Q_w_t(S)≥(1-h)^n_u,tQ_w_u(S). Substitute κ=(1−h)nu,t+1/hκ=(1-h)^n_u,t+1/h into (62). The preceding two inequalities imply ft(S) f_t(S) =Qwt(S)+κ(Qwu(S)−Qwu−1(S)) =Q_w_t(S)+κ (Q_w_u(S)-Q_w_u-1(S) ) ≥(1−h)nu,th(Qwu(S)−(1−h)Qwu−1(S)) ≥ (1-h)^n_u,th (Q_w_u(S)-(1-h)Q_w_u-1(S) ) ≥0. ≥ 0. Since each Q has total mass one, ∑|S|=mft(S)=1 _|S|=mf_t(S)=1. Thus ftf_t is a probability distribution. The anchor w¯ w is fixed during the episode, so the orientation probabilities αj(S) _j(S) are identical in all three terms of ftf_t. Applying (16) term by term gives ∑j∉Uft(U∪j)αj(U∪j) _j∉ Uf_t(U∪\j\) _j(U∪\j\) =pwt(U)+κ(pwu(U)−pwu−1(U)) =p_w_t(U)+κ (p_w_u(U)-p_w_u-1(U) ) =νt(U). = _t(U). The last equality is (45), and Lemma 23 now gives the three-component sampler. With one component the same lemma samples QwtQ_w_t and then pwtp_w_t after orientation. For the two-component logical refresh at round s, the set mass is Qws+1(S)−(1−h)Qws(S)h≥0. Q_w_s+1(S)-(1-h)Q_w_s(S)h≥ 0. Its total mass is (1−(1−h))/h=1(1-(1-h))/h=1. The orientation identity and (23) give the law ρs _s. ∎ The point of Lemmas 23, 24 and Algorithm 9 is computational. Directly tabulating the commitment law over all m-subsets would require Θ((Km)) ( Km) probabilities, which is exponential in general. Lemma 24 represents the required law using three product components, and Lemma 23 samples from this representation in O(Km)O(Km) rational operations without enumerating the state space. Lemma 25 (Finite sampler coupling). For every fixed reward matrix and reserved row, we can couple the finite and ideal reference executions as follows. Define their projected behavioral trace to contain actions, observations, comparison and decoder outcomes, encoded and accepted words, and all score, clock, and local-state registers. Exclude raw sampler coordinates. In a saved record (s,j,y,v)(s,j,y,v), replace the raw field v by its vector of all admissible future contributions (ψk(y,v))k∈ℤ∩[0,4bN], ( _k(y,v) )_k ∩[0,4b_N], where ψk _k is defined in (41). This projection is for analysis only; the implementation still stores v. Let ideal Tr_ ideal and finite Tr_ finite denote these projected traces. Then Pr(ideal≠finite)≤C(K2+bN)T2−Lbit=ϵsamp. ( Tr_ ideal≠ Tr_ finite)≤ C(K^2+b_N)T2^-L_ bit= _ samp. For any functional of Tr with range in [−mT,mT][-mT,mT], the two expectations differ by at most 2mTϵsamp2mT _ samp; for any event determined by Tr, the two probabilities differ by at most ϵsamp _ samp. Proof. Put ε=2−Lbit =2^-L_ bit and :=rowC:=C_ row, the fixed coordinate namespace defined in Subsection B.4. For the selected row J, abbreviate Vs,c:=VJ,s,cV_s,c:=V_J,s,c. For (s,c)∈[T]×(s,c)∈[T]×C, couple Vs,c∼Unif([0,1))V_s,c ([0,1)) to Vs,c(L)=ε⌊Vs,c/ε⌋.V_s,c^(L)= V_s,c/ . Couple the masks, certified code, bootstrap arrays, and affine-hash bits identically in the two executions. Their bounded-sampler exhaustion is accounted for separately in the public-construction analysis. The row is sampled before play, but its coordinates are exposed in the order the protocol reads them. If the same threshold a∈[0,1]a∈[0,1] is applied to a paired coordinate, then unequal Boolean results imply Vs,c∈[a,a+ε).V_s,c∈[a,a+ ). (63) A draw with q outcomes has at most q−1q-1 cumulative thresholds. Algorithm 10 reserves independent coordinates for each potential call site in a control row, even when its branch is not taken. The injective tuple (R0,…,Rd)(R_0,…,R_d) of Section 6 can be generated by successive uniform draws from sets of sizes K,K−1,…,K−m+1K,K-1,…,K-m+1. Its rrth draw, 0≤r<m0≤ r<m, has K−r−1K-r-1 cumulative boundaries. On DATA, Algorithm 5 uses the m independent pilot arms P0,…,PdP_0,…,P_d, each with K−1K-1 boundaries; its coordinator fast-arm draw has |[K]∖U|−1=K−m|[K] U|-1=K-m boundaries. The row’s three-way slot choice has two boundaries. Its selected follower and DATA recorder-source choices have d−1d-1 and m−1m-1; the proposal bit of Algorithm 3 and the immediate thinning test of Algorithm 6 have one each. In Algorithm 9, the loop over i∈[K]i∈[K] makes at most K binary inclusion comparisons, and the final orientation among m arms has at most m−1m-1 boundaries. Therefore, with BrowB_ row denoting the boundary budget for comparisons made at that round and for its fixed proposal bit, Brow B_ row :=∑r=0m−1(K−r−1)+m(K−1)+(K−m) := _r=0^m-1(K-r-1)+m(K-1)+(K-m) +[2+(d−1)+(m−1)+1+1]+K+(m−1) + [2+(d-1)+(m-1)+1+1 ]+K+(m-1) =2mK+2K−(m2)≤2K2+2K=O(K2). =2mK+2K- m2≤ 2K^2+2K=O(K^2). There are at most 2m+K+7=O(K)2m+K+7=O(K) coordinate call sites in this allocation. For each potential call (s,c)(s,c), let ℋs,c H_s,c be the sigma-field generated by the masks, code, bootstrap arrays, affine-hash bits, J, private bootstrap randomness, and the protocol history and scalar row coordinates exposed before this call, but not Vs,cV_s,c. This is an exposure sigma-field: the protocol has not used the remaining published coordinates to determine the current threshold. Let As,cA_s,c be the set of cumulative thresholds determined by ℋs,c H_s,c, with As,c=∅A_s,c= if the call is skipped. The independence of J and the control rows (Proposition 3) gives Vs,c⟂ℋs,c.V_s,c\ \!\!\! \ H_s,c. Thus the other construction randomness may affect As,cA_s,c but does not affect the following conditional estimate. Define Eon:=⋃s=1T⋃c∈⋃a∈As,cVs,c∈[a,a+ε).E_ on:= _s=1^T\ _c \ _a∈ A_s,c\V_s,c∈[a,a+ )\. Conditioning before each coordinate and using (63) gives Pr(Eon)≤∑s,c[PrVs,c∈⋃a∈As,c[a,a+ε)|ℋs,c]≤ε∑s,c|As,c|≤TBrowε≤CK2Tε. (E_ on)≤ _s,cE\! [ \! \V_s,c∈ _a∈ A_s,c[a,a+ )\, |\, H_s,c \ ]≤ _s,cE|A_s,c|≤ TB_ row ≤ CK^2T . (64) A thinning coordinate saved by an unoccupied follower is tested only after a DOWN acceptance. Its namespace is cthin=thinc_ thin=thin, distinct from the independent recorder-source coordinate recrec. Write Vs:=Vs,cthinV_s:=V_s,c_ thin and Vs(L):=Vs,cthin(L)V_s^(L):=V_s,c_ thin^(L). If the parsed rate exponent is k, its thinning threshold in (41) is ak=4dK2−k/ζa_k=4dK2^-k/ζ, where k∈ℤ∩[0,4bN]k ∩[0,4b_N] by the DOWN parsing range. Define the fixed set and event :=ak:k∈ℤ∩[0,4bN]∩[0,1], :=\a_k:k ∩[0,4b_N]\∩[0,1], Erec E_ rec :=⋃s=1T⋃a∈Vs≤a≠Vs(L)≤a. := _s=1^T\ _a \1\V_s≤ a\ 1\V_s^(L)≤ a\\. The event includes every recorder position, whether or not it is eventually saved. Since ||≤4bN+1|D|≤ 4b_N+1, (63) and a union bound give Pr(Erec)≤T(4bN+1)ε. (E_ rec)≤ T(4b_N+1) . (65) This bound is uniform over the exponent selected by any later parsed DOWN word, including an incorrectly accepted one. If ak>1a_k>1, both thinning indicators equal one, so it needs no entry in D. Consequently, by (41), on EreccE_ rec^c we have ψk(y,Vs)=ψk(y,Vs(L))for all s∈[T],k∈ℤ∩[0,4bN],y∈[0,1]. _k(y,V_s)= _k(y,V_s^(L)) all s∈[T],\ k ∩[0,4b_N],\ y∈[0,1]. (66) On (Eon∪Erec)c(E_ on∪ E_ rec)^c, induction over local operations gives identical projected traces. Online comparisons agree until the first possible difference, and (66) makes every admissible later use of paired saved records agree. The raw fields VsV_s and Vs(L)V_s^(L) need not be numerically equal and are not part of the projection. Equations (64) and (65) yield the claimed probability bound. Let F,FL∈[−mT,mT]F,F_L∈[-mT,mT] be the values of the same functional of ideal,finite Tr_ ideal, Tr_ finite. They agree when the traces agree, so |F−FL|≤|F−FL|≤2mTPr(F≠FL)≤2mTϵsamp.|EF-EF_L| |F-F_L|≤ 2mT (F≠ F_L)≤ 2mT _ samp. Applying the same inequality to event indicators gives the event bound. ∎ The complete reference regret and the decoder and stability events are determined by this projected trace. Thus replacing the ideal coordinates by their LbitL_ bit-bit implementations changes those expectations by at most 2mTϵsamp2mT _ samp and those event probabilities by at most ϵsamp _ samp, as required in the main proof. 9.2 Storage and bit complexity Proposition 26 (Finite implementation complexity). On the construction branch, the public description has O(N4logN)O(N^4 N) bits and can be constructed using O~(N4) O(N^4) bit operations. The total bootstrap-decoding cost is O~(N5/2) O(N^5/2), and the total post-initialization communication-decoding cost is O(mTlog3N)O(mT ^3N) on every execution. The latter improves to O(Tlog3N)O(T ^3N) when all active players use the same row. All remaining online computations have polynomial bit complexity in K,m,TK,m,T. Moreover, the bounded integer-sampling implementation is total, and the probability that any capped constructor or private-bootstrap draw reaches its cap is at most N−40N^-40. Proof. We use the parameter estimates established in the proof of Lemma 29: mB+=O(N),Scol=O(N3/2),Qarr=O(N2),mB_+=O( N), S_ col=O(N^3/2), Q_ arr=O(N^2), together with mT≤N,K2T≤N2,mT≤ N, K^2T≤ N^2, and the fact that every arm, message, column, and sampler coordinate has O(logN)O( N) bits. Public construction. The raw arm arrays contain O(mTScol)O(mTS_ col) entries, while the stored message permutations contain O(mB+ScolQarr)=O(N4)O(mB_+S_ colQ_ arr)=O(N^4) labels. The reserved masks use MT≤N3MT≤ N^3 bits. By Lemma 25, the finite learning/control rows contain O(K2)O(K^2) O(logN)O( N)-bit coordinates per row and time, and hence use O(MTK2logN)=O(N4logN)O(MTK^2 N)=O(N^4 N) bits. The certified code is only polylogarithmic in N. Thus the entire published description has O(N4logN)O(N^4 N) bits. The same counts show that the constructor performs at most O(N4)O(N^4) finite sampling, permutation, and table-entry operations. Each such operation involves O(logN)O( N)-bit quantities and bounded rejection sampling with O(logN)O( N) attempts. Hence the total construction cost is O~(N4) O(N^4) bit operations. Decoding. At a complete bootstrap block boundary, checking one sender column requires a pass over at most n positions and Gaussian elimination in O(logN)O( N) binary unknowns. Its cost is therefore O(nlog2N).O(n ^2N). Each receiver has at most three neighboring senders, so the number of sender-column checks over all blocks is O(mB+Scol)O(mB_+S_ col). Since B+n≤2TB_+n≤ 2T, O(mB+Scolnlog2N) O(mB_+S_ coln ^2N) =O(mTScollog2N) =O(mTS_ col ^2N) =O~(N5/2). = O(N^5/2). For the post-initialization affine channels, B,Qdec=O(logN).B,Q_ dec=O( N). A full decoder decision solves at most QdecQ_ dec equations in B binary unknowns and hence costs O(log3N)O( ^3N) bit operations. Each player makes at most one channel decision on a calendar round, so the unconditional total cost is O(mTlog3N).O(mT ^3N). When all active players use the same row, its common slot and selected follower enable at most one receiver channel per round. This gives O(Tlog3N)O(T ^3N) for synchronized executions, including the reference. Remaining online computation. It remains only to check that exact learner and scheduling arithmetic uses polynomial-size operands and polynomially many operations. The quantization denominator satisfies D=O(N2)D=O(N^2) and every score lies in [0,TD][0,TD]. Hence an exact weight wi=(D+1D)ziw_i= ( D+1D )^z_i has numerator and denominator of polynomial bit length. Products, elementary-symmetric-sum dynamic programs, and the at most three rational components used by the commitment sampler therefore also have polynomial bit length. The proposal probability h has O(logN)O( N) bits, while κ=(1−h)nu,t+1h,nu,t≤T,κ= (1-h)^n_u,t+1h, n_u,t≤ T, has polynomial bit length as well. All message fields have O(logN)O( N) bits. There are at most T commitments and O(mT)O(mT) local round updates. The loops appearing in the learner, recorder, scheduler, and direct sampler have lengths polynomial in K and m, and the sparse observation lists contain at most T records per follower. Consequently all remaining online computations use polynomially many arithmetic, comparison, hashing, and list operations on polynomial-bit operands. Their total bit complexity is therefore polynomial in K,m,TK,m,T. Finally, the constructor and private bootstrap together make O(N4)O(N^4) bounded uniform-integer draws, and hence at most N5N^5 such draws after enlarging the fixed branch constant if necessary. A single rejection attempt succeeds with probability at least 1/21/2, so with acap=⌈45log2N⌉a_ cap= 45 _2N a particular call reaches its cap with probability at most 2−acap2^-a_ cap. Therefore Prsome bounded sampler reaches its cap≤N52−acap≤N−40. \some bounded sampler reaches its cap\≤ N^52^-a_ cap≤ N^-40. The prescribed fallback rules define the execution even on this event, so the finite implementation is total. ∎ Appendix A Exceptional executions The decoder estimates apply through the first weight doubling. A decoder failure does not terminate or condition the logical learner in the reference execution. A.1 A total local algorithm The following convention defines every action even after an erroneous declaration or decode. It uses one absorbing error state, denoted † , for each player. Before performing a local operation, check that its inputs belong to their stated finite domains. In particular, arm labels must belong to [K][K], scores to ℤ∩[0,TD]Z∩[0,TD], increments to ℤ∩[0,D]Z∩[0,D], and time fields to [0,T+1][0,T+1]. Every required denominator must be positive. Each Bernoulli parameter, including a thinning or mixture parameter, must belong to [0,1][0,1]. For the slow-set sampler, apply these checks to the scalar probabilities and normalizers that its successive sampling steps actually evaluate (Section 9.1). The local record must specify exactly one applicable action branch. A computed value is checked before it is stored or used in another operation. Let Φ be one specified local operation, with input domain dom(Φ)dom( ) and allowed output set ΦD_ . Apply its total extension Φ¯(x)=Φ(x),x≠†,x∈dom(Φ),Φ(x)∈Φ,†,otherwise. (x)= cases (x),&x≠ ,\ x ( ),\ (x) _ ,\\ ,&otherwise. cases (67) The first branch evaluates the operation only after its input-domain checks. Once the state is † , no learning or transport update is performed. A decoder rejection is an ordinary operation and does not enter † . In the error state the player plays arm i+1i+1 on active nonreserved rounds and continues its bootstrap-array action on declared reserved rounds. Since 0≤i≤d=m−1<K0≤ i≤ d=m-1<K, this arm always exists. Bootstrap updates and activation retain their own specified finite-domain convention. Lemma 27 (The error state is unused on valid executions). Use the construction-branch rate choice of Section 8 and suppose the public constructor has published a table. If the bootstrap states and activation times agree with the reference execution, every accepted message is the message currently sent, and the feasibility and stability bounds of Section 5 hold through round t. Then no learning or transport operation enters † by round t. Proof. Order the learning and transport operations through round t by round, within-round step, and player label, and write them as 1,…,L o_1,…, o_L. We prove by induction on q that after 1,…,q o_1,…, o_q no player is in † , the physical and reference local registers agree, and the registers and calendar-round scores satisfy the following bounds. For 1≤s≤t1≤ s≤ t, 0≤v≤t+10≤ v≤ t+1, j∈[K]j∈[K], and i∈[d]i∈[d], they are Δs(j) _s(j) ∈ℤ∩[0,D], ∩[0,D], Zj(v) Z_j(v) =∑r<vΔr(j)∈ℤ∩[0,TD], = _r<v _r(j) ∩[0,TD], (68) Si,cj S_i,c_j ∈ℤ∩[0,TD], ∩[0,TD], δi _i ∈ℤ∩[0,D], ∩[0,D], statei _i ∈0,1,2, ∈\0,1,2\, ⊆[d]. [d]. The assertion holds for q=0q=0: bootstrap states and activation times agree by hypothesis, z=S=δ=0z=S=δ=0, the UP placeholder is (0,0,0)(0,0,0), and the published table supplies symbols in their prescribed alphabets. Assume the assertion holds through q o_q for some q<Lq<L. Since every accepted word is the currently encoded word, Lemmas 17, 18, and 19 apply to this common prefix. Increments and score registers. For each selected owner i and arm j, feasibility gives N−4≤ξjN^-4≤ _j and η≤ξj≤2/(AmK)η≤ _j≤ 2/(AmK). Since Yi,s∈[0,1]Y_i,s∈[0,1], the recorder’s increment satisfies Δs(j)=⌊DηYi,s/ξj⌋,Is=j,0,Is≠j,0≤Δs(j)≤D. _s(j)= cases Dη Y_i,s/ _j ,&I_s=j,\\ 0,&I_s≠ j, cases 0≤ _s(j)≤ D. Every score and collection sum contains at most T such increments, so it lies in [0,TD][0,TD]. Lemma 17 gives the same bound for a follower’s sum after delayed DOWN acceptance. At a commitment, either σ=0σ=0 or =∅P= by Algorithm 7. In the first case the coordinator sets z(t)=0=Z(t)z(t)=0=Z(t). In the second, Lemma 15 gives zai(u) z_a_i(u) =zai(σ)+Si=Zai(u), =z_a_i(σ)+S_i=Z_a_i(u), z(t) z(t) =z(u)+c(t)=Z(t), =z(u)+c(t)=Z(t), Z(u−1) Z(u-1) =Z(u)−Δu−1. =Z(u)- _u-1. Lemma 18 supplies the asserted value of SiS_i; the induction hypothesis supplies z(σ)=Z(σ)z(σ)=Z(σ). Hence the reconstructed scores lie in [0,TD][0,TD]. Sampling operations and probabilities. The parameter and stability bounds yield wj w_j =(1+1/D)zj>0, =(1+1/D)^z_j>0, 0<h 0<h =4AmKη≤14, =4AmKη≤ 14, 0≤γ 0≤γ ≤1. ≤ 1. Lemma 5 gives ρs≥0 _s≥ 0 and ∑Uρs(U)=1 _U _s(U)=1. For its direct sampler, the underlying m-set mass is fsρ(S)=Qws+1(S)−(1−h)Qws(S)h≥0,∑|S|=mfsρ(S)=1.f_s^ρ(S)= Q_w_s+1(S)-(1-h)Q_w_s(S)h≥ 0, _|S|=mf_s^ρ(S)=1. Lemmas 20 and 24 give the same properties for the within-episode mass ftf_t; at an initial or grid commitment the mass is QwtQ_w_t. Write f for any of these nonnegative m-set laws. At a sampler prefix (A,i)(A,i), its total and inclusion masses are W W =∑S∈(A,i)f(S), = _S (A,i)f(S), Win W_ in =∑S∈(A,i)i∈Sf(S), = _ subarraycS (A,i)\\ i∈ S subarrayf(S), 0 0 ≤Win≤W. ≤ W_ in≤ W. Initially W=1W=1. If W>0W>0 and the coordinate v∈[0,1)v∈[0,1), the chosen branch has mass W′=Win,v<Win/W,W−Win,v≥Win/W>0.W = casesW_ in,&v<W_ in/W,\\ W-W_ in,&v≥ W_ in/W cases>0. Indeed, the first branch requires Win>vW≥0W_ in>vW≥ 0; the second requires Win≤vW<W_ in≤ vW<W. Thus W>0W>0 at every reached prefix, also for finite coordinates. At termination |S|=m|S|=m and ∑k∈Sw¯k−1>0 _k∈ S w_k^-1>0, so orientation chooses j∈Sj∈ S. For U=S∖jU=S \j\, the fast-arm denominator satisfies ∑k∉Uwk1+sUw¯k>0. _k∉ U w_k1+s_U w_k>0. Moreover |U|=d|U|=d and |[K]∖U|=K−m+1≥2|[K] U|=K-m+1≥ 2. For each selected owner i and arm j, feasibility and (35) also give 0≤ξj(1/2)siπi(j)ζ≤1.0≤ _j(1/2)s_i _i(j)ζ≤ 1. The denominator is positive because siπi(j)>0s_i _i(j)>0 on the owner event and ζ>0ζ>0. The arm rule chooses an element of [K][K], and the recorder chooses at most one Is∈[K]∪⊥I_s∈[K]∪\ \. Message fields and local transitions. At a commitment the DOWN word and, at a cutoff, the ENDPOINT word are MiDOWN=(σ,ai,e,−log2ξai),MiEND=(σ,Si,δi).M_i DOWN=(σ,a_i,e,- _2 _a_i), M_i END=(σ,S_i, _i). The bounds above and Lemma 16 put these words in their parsing alphabets. The decoder output belongs to ⊥∪0,1B\ \∪\0,1\^B; a nonparsing word is rejected, while an accepted word is current by hypothesis. Lemmas 18 and 19 give statei∈0,1,2state_i∈\0,1,2\ and ⊆[d]P [d]. At the first cutoff, c=0c=0 and =[d]P=[d]. The cutoff lies in [T+1][T+1], and the coefficient remains defined since κ∈0,1−h(1−h)q:q∈0,…,T,h>0.κ∈ \0, 1-hh(1-h)^q:q∈\0,…,T\ \, h>0. The local record, published row, and current observation determine exactly one action branch. Thus q+1 o_q+1 has a valid input, produces an allowed output, and makes the same update in the physical and reference executions. It does not enter † and preserves (68), proving the induction step. Taking q=Lq=L proves the claim through round t. ∎ A.2 Decoder error bound Proof of Lemma 8. Work in the product-stream reference execution, through the first round of a stability or feasibility failure; stop each batch thereafter or at the horizon. Put Q=QdecQ=Q_ dec. For one completed batch on a directed channel, let r1<⋯<rQr_1<·s<r_Q be its positive-test rounds, and let Mr∈2B∪⊥M_r _2^B∪\ \ be the word encoded on that channel at round r. An admissible wrong word was not sent in its batch. Suppose a candidate M passes the acceptance test at a decision time t but M≠MtM≠ M_t. Then Mrq≠M(q∈[Q]).M_r_q≠ M (q∈[Q]). (69) Indeed, suppose Mrq=M_r_q=M for some q. On a DOWN channel, M is a fixed assignment record with start field σ=M.σ=M.σ. Let t−P_t^- be the value of P at the arm-choice step of round t, and let σi(t−) _i(t^-) be follower i’s last accepted DOWN start before its decoder decision at t. Suppose first that the coordinator still retains the assignment starting at σ. On a DOWN round selecting i, it encodes M whenever i∈t−i _t^- by Algorithm 5. Hence Mt≠M_t≠ M implies i∉t−i _t^-. If t precedes this assignment’s cutoff, i was removed from P by a DOWN receipt in an earlier round. Lemma 11 implies that i was occupied when that receipt occurred. At the start of this assignment i was unoccupied, and in the reference execution it can become occupied only by accepting M; thus i accepted M before round t. If t is at or after the cutoff, P was reset to [d][d] there, so i∉t−i _t^- implies that the coordinator accepted i’s ENDPOINT before round t. By Lemma 19, that ENDPOINT is offered only after i accepts M. Suppose instead that a successor assignment has been committed by round t. By Lemma 19, the coordinator accepted i’s ENDPOINT for the σ-assignment before that commitment. Hence i accepted M in both cases. Since accepted DOWN start fields strictly increase, every case gives σi(t−)≥M.σ _i(t^-)≥ M.σ, contradicting the DOWN acceptance condition σi(t−)<M.σ _i(t^-)<M.σ in (40). On an UP channel, acceptance requires M.σ=σ>0M.σ=σ>0 and i∈i , so M is not the initial placeholder. By Lemma 19, this assignment’s ENDPOINT remains fixed until a newer DOWN record is applied. A successor assignment cannot be committed before this ENDPOINT is accepted. Hence, if Mt≠M_t≠ M, either i∉i or the current assignment has start time greater than M.σM.σ. Both contradict UP acceptance. This proves (69). One-batch estimate. Fix a channel (UP or DOWN), a batch start α, and a deterministic candidate M∈2BM _2^B. Recall from Section 6.1 that this channel’s round-r hash is Hr(x)=cr⋅x⊕brH_r(x)=c_r· x b_r, with a fresh pair (cr,br)(c_r,b_r). Let τq _q be the round of the q-th positive test in this batch before stopping, with τq=∞ _q=∞ if that test does not occur. Set Dq:=τq<∞,Mτj≠M,Hτj(M)=1 for all j≤q.D_q:=\ _q<∞,\ M_ _j≠ M,\ H_ _j(M)=1 for all j≤ q\. Conditional on the history ℋαH_α at the batch start, we claim Pr(DQ∣ℋα)≤2−Q. (D_Q _α)≤ 2^-Q. (70) To prove this, let ℋr−H_r^- contain the information available before (cr,br)(c_r,b_r) is read. Let ArA_r indicate that round r adds a positive test to this batch. If Mr∉M,⊥M_r∉\M, \, the affine hash values (Hr(Mr),Hr(M))(H_r(M_r),H_r(M)) are independent fair bits conditional on ℋr−H_r^-. If Mr=⊥M_r= , the channel action and ArA_r do not use this hash, including before activation. Consequently, [ArMr≠M,Hr(M)=1∣ℋr−]=12[ArMr≠M∣ℋr−].E\! [A_r1\M_r≠ M,\ H_r(M)=1\ _r^- ]= 12E\! [A_r1\M_r≠ M\ _r^- ]. (71) Write Nr−1N_r-1 for the number of tests already in the batch before round r, and let Iq,rI_q,r indicate that the batch is active, Nr−1=q−1N_r-1=q-1, and Dq−1D_q-1 holds. This indicator is ℋr−H_r^--measurable. Summing (71) over the possible round of the q-th positive test gives Pr(Dq∣ℋα)=12[∑r=αTIq,rArMr≠M|ℋα]≤12Pr(Dq−1∣ℋα). (D_q _α)= 12E\! [ _r=α^TI_q,rA_r1\M_r≠ M\\, |\,H_α ]≤ 12 (D_q-1 _α). The inequality holds because the q-th test can occur only once. Iteration for q=1,…,Qq=1,…,Q proves (70). Union bound and decoding time. Let EfalseE_ false be the event that a completed batch has a unique solution M≠MtM≠ M_t passing the acceptance test. Such an M solves every retained equation, so Hrq(M)=1H_r_q(M)=1; (69) supplies Mrq≠M_r_q≠ M. There are at most 2d2d channels (UP or DOWN for each follower), and each has (T+1)(T+1) possible batch-start rounds α∈[T+1]α∈[T+1]. Thus there are at most 2d(T+1)2d(T+1) batches and 2B2^B candidate words per batch. Since N=2Km(T+1)N=2Km(T+1), (26) and (70) give Pr(Efalse)≤2d(T+1)2B−Q≤N82B−Q≤δ2N4. (E_ false)≤ 2d(T+1)2^B-Q≤ N^82^B-Q≤ δ2N^4. Let EambE_ amb be the event that a batch consisting of positive tests of one fixed awaited word M∗M^* has more than one solution. The transmitted M∗M^* solves every equation. Any other solution M satisfies Mrq=M∗≠M_r_q=M^*≠ M and Hrq(M)=1H_r_q(M)=1 for all q. The same conditional estimate and union bound yield Pr(Eamb)≤δ2N4. (E_ amb)≤ δ2N^4. The bound is uniform when M∗M^* is chosen from the batch-start history. The union bound gives Pr(Efalse∪Eamb)≤δ/N4. (E_ false∪ E_ amb)≤δ/N^4. On (Efalse∪Eamb)c(E_ false∪ E_ amb)^c, no completed batch has a unique solution different from the word currently encoded on its channel that passes (40), and no completed batch formed entirely from one fixed awaited word has multiple solutions. Suppose M∗M^* becomes awaited when its receiver’s batch contains n∈0,…,Q−1n∈\0,…,Q-1\ equations. After Q−nQ-n further positive receiver observations, the decoder decides that batch and clears it. The batch may contain equations from a preceding word. If M∗M^* is still awaited, the next Q positive observations form a new batch whose transmitted word is M∗M^* throughout. Hence M∗M^* solves every equation in the new batch; on EambcE_ amb^c it is the unique solution and passes (40). Thus, if service continues for (Q−n)+Q≤2Q(Q-n)+Q≤ 2Q further positive observations, M∗M^* is accepted. Finally, solving Q binary equations in B unknowns costs O(QB2)=O(log3N)O(QB^2)=O( ^3N) bit operations by Gaussian elimination; parsing costs O(B)O(B). This proves all assertions. ∎ Appendix B Public construction and bootstrap communication This appendix specifies the public table and proves its simultaneous guarantees. The mask and arm-array properties hold for all reward supports and actual bootstrap messages; the finite-row bound holds for all rounded reward matrices. The constructor samples once and does not test these universal properties of its output. As throughout the paper, c,C>0c,C>0 denote universal constants whose values may change between appearances. All probability arguments in this appendix use the exact sampling laws displayed in the algorithms. The bounded implementation is compared to those laws by the rejection-stream coupling of Section 4, with cap exhaustion charged separately. B.1 Public construction and reserved masks Recall from Section 4 that M=N2M=N^2 is the number of published learning/control rows. Recall also the construction branch (11), the fixed concentration constant C0C_0, the reserved-round probability p, the bootstrap block length n, and the finite-coordinate precision Lbit=⌈64log2N⌉L_ bit= 64 _2N . These are precisely the parameters needed by the public constructor below. Algorithm 10 samples the masks, certified code, bootstrap arrays, and finite learning/control rows in that order, using fresh randomness at each stage. Algorithm 10 Construct and publish the public table 1: K,m,TK,m,T. 2: if k⋆T≤CbV^k_ T≤ C_b V then 3: Publish the fixed-arm fallback flag; stop. 4: end if 5: Sample Cj,t∼Bernoulli(p)C_j,t (p) independently for j∈[M]j∈[M] and t∈[T]t∈[T]. 6: Using randomness independent of the masks, construct the certified code G of Subsection B.3. 7: if code certification fails then 8: Publish the fixed-arm fallback flag; stop. 9: end if 10: Sample the label permutations and raw arm-array coordinates of Subsections B.2 and B.3. 11: Independently sample M finite learning/control rows as defined in Subsection B.4, using LbitL_ bit bits per scalar coordinate and independent fair affine-hash bits. 12: Publish all masks, the certified code G, every label permutation πs,b,w _s,b,w, all raw arm-array coordinates, and all learning/control rows. On successful construction, the published table has the following components. The index ranges and sampling laws for the bootstrap columns are specified in the cited subsections. Component Stored data Detailed construction Masks C=(Cq,t)q∈[M],t∈[T]C=(C_q,t)_q∈[M],\,t∈[T], with Cq,t∈0,1C_q,t∈\0,1\. Algorithm 10. Code G∈2Harr×BarrG _2^H_ arr× B_ arr, shared by all bootstrap columns. Subsection B.3 and Lemma 28. Bootstrap arrays For each player s, block b, and column w, the published permutation πs,b,w _s,b,w; for each position t, the variables λs,b,w,t _s,b,w,t, bs,b,w(t)b_s,b,w(t), (a0,s,b,w,t,a1,s,b,w,t)(a_0,s,b,w,t,a_1,s,b,w,t), js,b,w,tj_s,b,w,t, and zs,b,w,tz_s,b,w,t, determining the arm maps cs,b,w,t(ν)c_s,b,w,t(ν) and ds,b,w,t(ν)d_s,b,w,t(ν). Subsections B.2 and B.3; Figure 2. Control rows (Rq)q∈[M](R_q)_q∈[M], with the finite coordinate and hash namespaces specified in Subsection B.4. Subsection B.4. Table 1: Components of the public table on the construction branch. The decoder uses the published rows of G in (84). The maps cs,b,w,tc_s,b,w,t and ds,b,w,td_s,b,w,t are determined by G and the published raw coordinates and need not be sampled separately. The code constructor does not inspect C. Thus G is independent of C, and the primitive bootstrap-column draws have their stated laws conditional on every fixed mask realization. The fixed-mask condition in Lemma 29 is used when proving its reserved-position property A7. Algorithm 10 specifies exact sampling laws. Its finite realization replaces each finite-set uniform draw by the bounded sampler of (6) and publishes the fixed-arm fallback flag immediately if a public call exhausts its cap. On the event of no public exhaustion, its output agrees with the exact-sampling construction under the rejection-stream coupling. For the rest of this appendix abbreviate A:=AkeyA:=A_ key, the authentication-key alphabet size defined in Section 4. Use the player labels 0,…,m−10,…,m-1 of Section 5, with root 00. Each nonroot i has parent ⌊(i−1)/2⌋ (i-1)/2 and ordered children 2i+1,2i+22i+1,2i+2 whenever these labels are below m. Write di≤2d_i≤ 2 for its number of children. B.2 Scalar messages Independently of the root’s uniform J∈[M]J∈[M], each nonroot player draws a uniform authentication key Ui∈[A]U_i∈[A]. The root has no parent and, since m≥2m≥ 2, is an informed internal node; its rule never uses a key. Encode J−1=J0+AJ1J-1=J_0+AJ_1, with J0,J1∈0,…,A−1J_0,J_1∈\0,…,A-1\. Let ⊥ denote the distinguished absent/unknown symbol, which is not an element of [A][A]. For u∈[A]u∈[A] and 0≤c<di0≤ c<d_i, k∈0,1k∈\0,1\, 0≤v<A0≤ v<A, and e∈[A]∪⊥e∈[A]∪\ \, define DISC(u):=u−1,DISC(u):=u-1, and ROOT(c,k,v,e):=A+((2c+k)A+v)(A+1)+0,e=⊥,e,e∈[A].ROOT(c,k,v,e):=A+((2c+k)A+v)(A+1)+ cases0,&e= ,\\ e,&e∈[A]. cases As these arguments range over their stated domains, the DISC and ROOT labels give a bijection onto 0,…,A+2diA(A+1)−1\0,…,A+2d_iA(A+1)-1\. Denote this native alphabet by ℳi M_i; thus |ℳi|=A+2diA(A+1)=O(A2)| M_i|=A+2d_iA(A+1)=O(A^2). Set Barr=⌈log2maxi|ℳi|⌉B_ arr= _2 _i| M_i| , the raw-address width, and pad all alphabets to Qarr=2BarrQ_ arr=2^B_ arr labels; unused labels are invalid. Recall ScolS_ col from (12) and abbreviate S0:=ScolS_0:=S_ col. To index both complete blocks and the possible final incomplete block, set B+:=⌈Tn⌉,Ib+:=(b−1)n+1,…,minbn,T,b∈[B+].B_+:= Tn , I_b^+:=\(b-1)n+1,…, \bn,T\\, b∈[B_+]. For every player s∈0,…,m−1s∈\0,…,m-1\, block b∈[B+]b∈[B_+], and column w∈[S0]w∈[S_0], store an independent uniform permutation πs,b,w _s,b,w of the QarrQ_ arr labels and its inverse. Raw addresses are ν∈2Barrν _2^B_ arr. To send a native label μ in sender–block pair (s,b)(s,b), first fix the complete message, then choose a fresh uniform column w and use address πs,b,w−1(μ) _s,b,w^-1(μ). When s and b are fixed, we suppress them and write simply πw _w. B.3 Certified code and raw arm arrays Lemma 28 supplies a short binary linear code with this separation property and an exact polynomial-time certificate. Lemma 28 (Certified binary code). For every integer B≥1B≥ 1, there is a randomized algorithm which, on success, outputs an integer H′H and a matrix G∈2H′×B,G _2^H × B, which satisfies, H′≤1024B,rank2(G)=B,minx∈2B∖0∥Gx∥1≥H′8.H ≤ 1024B, _F_2(G)=B, _x _2^B \0\ Gx _1≥ H 8. (72) Moreover, each trial uses poly(B)poly(B) bit operations and has success probability at least 3/43/4. Consequently, after ⌈80log2N⌉ 80 _2N independent trials, the probability that no code is produced is at most N−100N^-100. Proof. Set r=⌈log2(4(B+1))⌉,q=2r,k=⌈Br⌉.r= _2(4(B+1)) , q=2^r, k= Br . (73) Then 4(B+1)≤q<8(B+1),2k≤2(B+1)≤q.4(B+1)≤ q<8(B+1), 2k≤ 2(B+1)≤ q. (74) We first construct an inner binary code of dimension r. Sample a matrix A∼Unif(2128r×r),A (F_2^128r× r ), meaning that all 128r2128r^2 entries of A are independent fair bits. For a fixed u∈2r∖0u _2^r \0\, the coordinates of AuAu are independent fair bits, and therefore ∥Au∥1∼Bin(128r,1/2),∥Au∥1=64r. Au _1 (128r,1/2), Au _1=64r. The lower-tail Chernoff bound [5, Chapter 2] gives Pr∥Au∥1<32r≤exp(−(1/2)22 64r)=e−8r. \! \ Au _1<32r \≤ \! (- (1/2)^22\,64r )=e^-8r. (75) Hence, by a union bound over the 2r−12^r-1 nonzero inputs, Prminu≠0∥Au∥1<32r≤(2r−1)e−8r<e−(8−log2)r<14. \! \ _u≠ 0 Au _1<32r \≤(2^r-1)e^-8r<e^-(8- 2)r< 14. (76) The trial accepts A precisely when ∥Au∥1≥32rfor every u∈2r∖0. Au _1≥ 32r every u _2^r \0\. (77) Because 2r=q=O(B)2^r=q=O(B) by (74), this condition is checked exactly by enumerating all nonzero u, using polynomially many bit operations. Next construct the outer evaluation code. Enumerate monic binary polynomials of degree r until an irreducible polynomial h is found, and identify q=2[Z]/(h(Z)).F_q=F_2[Z]/(h(Z)). There are 2r=O(B)2^r=O(B) monic degree-r candidates, and irreducibility is checked by exact polynomial arithmetic, so this step also takes poly(B)poly(B) bit operations. Let ϕ:q⟶2rφ:F_q _2^r be the coordinate isomorphism in the polynomial basis 1,Z,…,Zr−11,Z,…,Z^r-1, and define the certified inner encoder E(a)=Aϕ(a)∈2128r.E(a)=Aφ(a) _2^128r. Choose 2k2k distinct elements β1,…,β2k∈q _1,…, _2k _q, which is possible by (74). For x∈2Bx _2^B, append kr−Bkr-B zero bits and split the resulting krkr-bit vector into k consecutive blocks in 2rF_2^r. Via ϕ−1φ^-1, denote the corresponding field elements by a0(x),…,ak−1(x)∈qa_0(x),…,a_k-1(x) _q, and set px(X)=∑s=0k−1as(x)Xs∈q[X].p_x(X)= _s=0^k-1a_s(x)X^s _q[X]. (78) Define C(x)=(E(px(β1)),…,E(px(β2k)))∈2H′,H′=2k(128r)=256kr.C(x)= (E(p_x( _1)),…,E(p_x( _2k)) ) _2^H , H =2k(128r)=256kr. (79) Every map appearing in (79) is 2F_2-linear, so there is a binary matrix G∈2H′×BG _2^H × B such that C(x)=GxC(x)=Gx. If x≠0x≠ 0, then pxp_x is a nonzero polynomial of degree at most k−1k-1. It therefore has at most k−1k-1 roots in qF_q. Among the 2k2k distinct evaluation points, #j∈[2k]:px(βj)≠0≥2k−(k−1)=k+1.\#\j∈[2k]:p_x( _j)≠ 0\≥ 2k-(k-1)=k+1. (80) For every such j, ϕ(px(βj))≠0φ(p_x( _j))≠ 0, so the exact inner certificate (77) implies ∥(E(px(βj))∥1≥32r. (E(p_x( _j)) _1≥ 32r. Summing the ℓ1 _1 norm of the 2k2k disjoint blocks in (79) gives ∥Gx∥1=∥C(x)∥1≥32r(k+1)≥32rk=H′8. Gx _1= C(x) _1≥ 32r(k+1)≥ 32rk= H 8. (81) Thus Gx≠0Gx≠ 0 for every x≠0x≠ 0, so rank2(G)=Brank_F_2(G)=B as well. It remains to bound the length and the failure probability. Since k=⌈B/r⌉k= B/r , then kr≤B+r.kr≤ B+r. For B≥1B≥ 1, 4(B+1)≤23B4(B+1)≤ 2^3B, hence r≤3Br≤ 3B and therefore H′=256kr≤256(B+r)≤1024B.H =256kr≤ 256(B+r)≤ 1024B. (82) The matrix G can be materialized by evaluating C on the B standard basis vectors, again in poly(B)poly(B) bit operations. Finally, by (76), one trial fails with probability at most 1/41/4, and therefore (1/4)⌈80log2N⌉≤2−160log2N=N−160≤N−100.(1/4) 80 _2N ≤ 2^-160 _2N=N^-160≤ N^-100. This proves the lemma. ∎ Apply Lemma 28 with B=BarrB=B_ arr and denote its returned matrix by G∈2Harr×BarrG _2^H_ arr× B_ arr. Write its rows as Gj∈2BarrG_j _2^B_ arr, j∈[Harr]j∈[H_ arr]. We now define one raw arm array formally. Recall that α0 _0 is the listening probability. For every player s∈0,…,m−1s∈\0,…,m-1\, block b∈[B+]b∈[B_+], column w∈[S0]w∈[S_0], and position t∈Ib+t∈ I_b^+, independently sample λs,b,w,t∼Bernoulli(α0),bs,b,w(t)∼Unif([K]), _s,b,w,t ( _0), b_s,b,w(t) ([K]), (a0,s,b,w,t,a1,s,b,w,t)∼Unif(a0,a1)∈[K]2:a0≠a1,(a_0,s,b,w,t,a_1,s,b,w,t) \(a_0,a_1)∈[K]^2:a_0≠ a_1\, js,b,w,t∼Unif([Harr]),zs,b,w,t∼Unif(2).j_s,b,w,t ([H_ arr]), z_s,b,w,t (F_2). Thus js,b,w,tj_s,b,w,t is the sampled code-row index and zs,b,w,t∈0,1z_s,b,w,t∈\0,1\ is the fair binary offset. Define the listening set of column (s,b,w)(s,b,w) by ℒs,b,w:=t∈Ib+:λs,b,w,t=1.L_s,b,w:=\t∈ I_b^+: _s,b,w,t=1\. When the player s and block b are fixed, we suppress those indices and write ℒwL_w, bw(t)b_w(t), (a0,a1)(a_0,a_1), jw,tj_w,t, and zw,tz_w,t. Set cν,w(t) c_ν,w(t) =aGjw,t⋅ν⊕zw,t, =a_G_j_w,t·ν\, \,z_w,t, (83) dν,w(t) d_ν,w(t) =bw(t),t∈ℒw,cν,w(t),t∉ℒw. = casesb_w(t),&t _w,\\ c_ν,w(t),&t _w. cases With all indices restored, the address-dependent arm maps in Table 1 are cs,b,w,t(ν):=cν,w(t),ds,b,w,t(ν):=dν,w(t)(ν∈2Barr,t∈Ib+).c_s,b,w,t(ν):=c_ν,w(t), d_s,b,w,t(ν):=d_ν,w(t) (ν _2^B_ arr,\ t∈ I_b^+). The fresh offset makes any fixed candidate’s arm uniform independently of its row index. Symbols are independent across positions and columns; addresses in the same column are correlated. The permutations are therefore retained explicitly and are not replaced by identity labels. Player s, block b: S0S_0 public columns w∈[S0]w∈[S_0]μ∈ℳs→πw−1ν∈2Barrμ∈ M_s \ _w^-1\ ν _2^B_ arr position listen arm pair row offset t1t_1 λw,t1 _w,t_1 bw(t1)b_w(t_1) (a0,w,t1,a1,w,t1)(a_0,w,t_1,a_1,w,t_1) jw,t1j_w,t_1 zw,t1z_w,t_1 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ trt_r λw,tr _w,t_r bw(tr)b_w(t_r) (a0,w,tr,a1,w,tr)(a_0,w,t_r,a_1,w,t_r) jw,trj_w,t_r zw,trz_w,t_r Gjw,t⋅ν⊕zw,t∈0,1⟶cν,w(t)=aGjw,t⋅ν⊕zw,tG_j_w,t·ν z_w,t∈\0,1\ 8.50012pt 8.50012ptc_ν,w(t)=a_G_j_w,t·ν z_w,tdν,w(t)=bw(t),λw,t=1,cν,w(t),λw,t=0.d_ν,w(t)= casesb_w(t),& _w,t=1,\\ c_ν,w(t),& _w,t=0. cases Figure 2: One public arm-array column, where Ib+=t1<⋯<trI_b^+=\t_1<·s<t_r\. The code matrix G is shared across columns; a0,a1a_0,a_1 in the candidate formula are the pair stored at position t. Player and block indices are suppressed inside the column. Thus a column stores πw _w and (λw,t,bw(t),(a0,w,t,a1,w,t),jw,t,zw,t)t∈Ib+( _w,t,b_w(t),(a_0,w,t,a_1,w,t),j_w,t,z_w,t)_t∈ I_b^+. The functions cν,wc_ν,w and dν,wd_ν,w are computed from these data and the shared matrix G. B.4 Finite learning/control rows Let B=4⌈log2(TD+1)⌉B=4 _2(TD+1) be the message width from Section 6. The fixed scalar-coordinate namespace is row= _ row= slot,sel,rec,fast,thin,prop \slot,sel,rec,fast,thin,prop\ ∪tupler,pilotr:0≤r<m∪commitr:1≤r≤K+1. ∪\tuple_r,pilot_r:0≤ r<m\∪\commit_r:1≤ r≤ K+1\. It has 2m+K+72m+K+7 elements. For each (q,t,c)∈[M]×[T]×row(q,t,c)∈[M]×[T]×C_ row, independently draw an integer Zq,t,cZ_q,t,c uniformly from 0,…,2Lbit−1\0,…,2^L_ bit-1\ using LbitL_ bit fair bits, and publish Vq,t,c(L)=2−LbitZq,t,c.V_q,t,c^(L)=2^-L_ bitZ_q,t,c. For analysis, the coupled ideal row instead uses independent Vq,t,c∼Unif([0,1))V_q,t,c ([0,1)), with Vq,t,c(L)=2−Lbit⌊2LbitVq,t,c⌋V_q,t,c^(L)=2^-L_ bit 2^L_ bitV_q,t,c . The continuous coordinates are not published. The names slot,sel,recslot,sel,rec choose the slot, selected follower, and DATA recorder source. The tuplertuple_r and pilotrpilot_r coordinates choose the injective arm tuple and DATA pilots; fastfast chooses the fast arm, while thinthin and propprop supply their binary tests. The K+1K+1 commitment coordinates supply Algorithm 9. For every (q,t,σ,i)∈[M]×[T]×DOWN,UP×[d](q,t,σ,i)∈[M]×[T]×\DOWN,UP\×[d], independently sample (cq,t,σ,i,bq,t,σ,i)∼Unif(2B×2),(c_q,t,σ,i,b_q,t,σ,i) (F_2^B×F_2), independently of all scalar coordinates. The published finite row is Rq:=((Vq,t,c(L))t,c,(cq,t,σ,i,bq,t,σ,i)t,σ,i).R_q:= ((V_q,t,c^(L))_t,c,(c_q,t,σ,i,b_q,t,σ,i)_t,σ,i ). Rows are independent across q and independent of the masks and bootstrap arrays. On a selected DOWN or UP channel, the affine hash is u↦cq,t,σ,i⋅u⊕bq,t,σ,iu c_q,t,σ,i· u b_q,t,σ,i. B.5 Bootstrap decoding and outward protocol Fix a block b and a receiver i. Let wiw_i be the column chosen by i for this block, and abbreviate ℒi:=ℒi,b,wiL_i:=L_i,b,w_i and bi(t):=bi,b,wi(t)b_i(t):=b_i,b,w_i(t). Let Ai,b⊆Ib+A_i,b I_b^+ be the positions at which i follows its bootstrap array action. Its positive listening set is Pi,b:=t∈ℒi∩Ai,b:Yi,t>0,P_i,b:=\t _i∩ A_i,b:Y_i,t>0\, where Yi,tY_i,t is its observed reward. Before activation, Ai,b=Ib+A_i,b=I_b^+; after activation, it consists of the declared reserved positions. Write P=Pi,bP=P_i,b when i,bi,b are fixed, and call |P|≥e∗|P|≥ e_* the positive-observation quota. The receiver knows the labels of its parent and children from the fixed tree, but a positive observation carries no sender label. To test one neighbor j, the receiver compares the same set P with every public column (j,b,w)(j,b,w), w∈[S0]w∈[S_0]. Here j is a candidate sender: it selects an array family and the native alphabet ℳj M_j; it is not inferred from an observation. For this test abbreviate ℒw:=ℒj,b,wL_w:=L_j,b,w, ak,w,t:=ak,j,b,w,ta_k,w,t:=a_k,j,b,w,t, rw(t):=j,b,w,tr_w(t):=j_j,b,w,t, and zw,t:=zj,b,w,tz_w,t:=z_j,b,w,t. The index rw(t)∈[Harr]r_w(t)∈[H_ arr] selects a row of G, whereas j labels the candidate sender. If t∈P∖ℒwt∈ P _w and bi(t)=ak,w,tb_i(t)=a_k,w,t for k∈0,1k∈\0,1\, a candidate address ν can explain the positive observation only if its candidate arm avoids bi(t)b_i(t). By (83), this condition is the exclusion equation Grw(t)⋅ν=(1−k)⊕zw,t.G_r_w(t)·ν=(1-k) z_w,t. (84) The two stored arms are distinct, so k is unique whenever such an equation exists. Coverage requires that each row h∈[Harr]h∈[H_ arr] occurs in at least ⌈|P|/(64KHarr)⌉ |P|/(64KH_ arr) (85) exclusion equations. A solution ν also has to pass ∑t∈P∩ℒwcj,b,w,t(ν)=bi(t)≤(64α0/K)|P|. _t∈ P _w1\c_j,b,w,t(ν)=b_i(t)\≤(64 _0/K)|P|. (86) Algorithm 11 performs this test separately for each possible column of the specified candidate sender. Its output may contain several pairs and does not assert which player caused any individual positive observation. Algorithm 11 Decode the public columns of candidate sender j 1: Complete block b, receiver i, candidate neighbor j, Pi,bP_i,b, and receiver listening arms (bi(t))t∈Pi,b(b_i(t))_t∈ P_i,b. 2: Di←j,b←∅D_i← j,b← . 3: if |Pi,b|<e∗|P_i,b|<e_* then 4: return Di←j,bD_i← j,b. 5: end if 6: for each public column w∈[S0]w∈[S_0] of player j in block b do 7: For each t∈Pi,b∖ℒj,b,wt∈ P_i,b _j,b,w with bi(t)=ak,w,tb_i(t)=a_k,w,t for some k∈0,1k∈\0,1\, add equation (84). 8: if each row h∈[Harr]h∈[H_ arr] occurs at least ⌈|Pi,b|/(64KHarr)⌉ |P_i,b|/(64KH_ arr) times then 9: Solve the equations over 2F_2. 10: if they have a unique solution ν and ν satisfies (86) then 11: μ←πj,b,w(ν)μ← _j,b,w(ν). 12: if μ∈ℳjμ∈ M_j then 13: Append (w,μ)(w,μ) to Di←j,bD_i← j,b. 14: end if 15: end if 16: end if 17: end for 18: return Di←j,bD_i← j,b in increasing column order. Define the set of retained native labels by Reti←j,b:=μ∈ℳj:(w,μ)∈Di←j,b for some w∈[S0].Ret_i← j,b:=\μ∈ M_j:(w,μ)∈ D_i← j,b for some w∈[S_0]\. The actual message of player j in block b is denoted μj,b _j,b. The decoder does not receive μj,b _j,b; its possible retention is analyzed below. Player i stores two digits J^i,0,J^i,1 J_i,0, J_i,1 and, for each child j, a key list ℋijH_ij. The root starts with digits (J0,J1)(J_0,J_1); every other digit and every child list starts at ⊥ . Each is filled at most once. The row declared by i is J^i=1+J^i,0+AJ^i,1,J^i,0,J^i,1≠⊥, 1+J^i,0+AJ^i,1∈[M],⊥,otherwise. J_i= cases1+ J_i,0+A J_i,1,& gathered J_i,0, J_i,1≠ ,\ 1+ J_i,0+A J_i,1∈[M], gathered\\ ,&otherwise. cases (87) Thus i is informed exactly when J^i≠⊥ J_i≠ . It parses a completed block if J^i=⊥ J_i= or some child list is ⊥ . Since d0≥1d_0≥ 1 and J^0=J J_0=J, the root never sends DISC. Algorithm 12 constructs one message per block. At its end, the receiver calls Algorithm 11 once for each neighbor whose message is needed, always using its own Pi,bP_i,b. The child’s DISC field supplies a possible key; a parent’s ROOT label supplies a digit only when its destination and echo equal the receiver’s child index and private key. Algorithm 12 Outward bootstrap at player i 1: for each block b in calendar order do 2: if J^i=⊥ J_i= or di=0d_i=0 then 3: μ←DISC(Ui)μ (U_i). 4: else 5: Draw c∼Unif(0,…,di−1)c (\0,…,d_i-1\) and k∼Unif(0,1)k (\0,1\) independently; set j←2i+1+cj← 2i+1+c. 6: Set e←⊥e← if ℋij=⊥H_ij= ; otherwise draw e∼Unif(ℋij)e (H_ij). 7: μ←ROOT(c,k,J^i,k,e)μ (c,k, J_i,k,e). 8: end if 9: Draw a fresh wi∼Unif([S0])w_i ([S_0]) independently; set ν←πi,b,wi−1(μ)ν← _i,b,w_i^-1(μ). 10: At each position t∈Ib+t∈ I_b^+, play di,b,wi,t(ν)d_i,b,w_i,t(ν) while inactive and on declared reserved rounds while active; otherwise use the learning protocol. 11: Form Pi,bP_i,b from positive observations at positions t∈ℒi,b,wit _i,b,w_i where the bootstrap arm was played. 12: if block b is complete and parsing is required then 13: for each child j with ℋij=⊥H_ij= do 14: Run Algorithm 11 for (i,j,b)(i,j,b) and set H←u∈[A]:DISC(u)∈Reti←j,bH←\u∈[A]:DISC(u) _i← j,b\. 15: if H≠∅H≠ then 16: ℋij←HH_ij← H. 17: end if 18: end for 19: if i≠0i≠ 0 and some J^i,k=⊥ J_i,k= then 20: Set pi←⌊(i−1)/2⌋p_i← (i-1)/2 and ci←i−(2pi+1)c_i← i-(2p_i+1); run the decoder for (i,pi,b)(i,p_i,b). 21: for k∈0,1k∈\0,1\ with J^i,k=⊥ J_i,k= do 22: Vi,k←v∈0,…,A−1:ROOT(ci,k,v,Ui)∈Reti←pi,bV_i,k←\v∈\0,…,A-1\:ROOT(c_i,k,v,U_i) _i← p_i,b\. 23: if Vi,k≠∅V_i,k≠ then 24: J^i,k←minVi,k J_i,k← V_i,k. 25: end if 26: end for 27: end if 28: end if 29: At a complete boundary, apply Algorithm 1 after these updates. 30: end for B.6 Uniform array properties Set κarr:=218,hexc:=e∗128κarrK. _ arr:=2^18, h_ exc:= e_*128 _ arrK. The constant κarr _ arr separates the two classes of raw candidates below, while hexch_ exc is the allowed number of exceptional positions in the uniform array properties. Recall that ϵarr _ arr from (12) is the allowed exceptional-column fraction. For a complete block IbI_b, fix a support χ∈0,1Ib×[K]χ∈\0,1\^I_b×[K] and set Gχ:=∑t∈Ib∑a∈[K]χt(a)G_χ:= _t∈ I_b _a∈[K] _t(a). Fix arbitrary receiver listening choices (ℒi,bi)(L_i,b_i), with ℒi⊆IbL_i I_b and bi:Ib→[K]b_i:I_b→[K], and put E:=t∈ℒi:χt(bi(t))=1,s:=|E|.E:=\t _i: _t(b_i(t))=1\, s:=|E|. Call a pair y=(ν,w)y=(ν,w) a raw entry and abbreviate cy(t):=cν,w(t)c_y(t):=c_ν,w(t) and dy(t):=dν,w(t)d_y(t):=d_ν,w(t). For a tuple x=(xj)j≠ix=(x_j)_j≠ i of other players’ raw entries, let dxj(t)=dj,b,wj,t(νj)d_x_j(t)=d_j,b,w_j,t( _j) when xj=(νj,wj)x_j=( _j,w_j), and define Px:=t∈E:dxj(t)≠bi(t) for all j≠i.P_x:=\t∈ E:d_x_j(t)≠ b_i(t) for all j≠ i\. (88) For a raw entry y=(ν,w)y=(ν,w) put Iy:=t∈E∖ℒw:cy(t)=bi(t)I_y:=\t∈ E _w:c_y(t)=b_i(t)\ and Jy:=t∈E∩ℒw:cy(t)=bi(t)J_y:=\t∈ E _w:c_y(t)=b_i(t)\. An entry is class 1 if max|Iy|,|Jy|<s/(κarrK) \|I_y|,|J_y|\<s/( _ arrK), and class 2 otherwise. These classes depend on raw arrays and receiver choices, not on transmitted labels or private history. Recall that, for the positive listening set PxP_x, quota means |Px|≥e∗|P_x|≥ e_*. Recall also that a native label is retained when it is returned by Algorithm 11; its class is the class of the raw entry that produced it. Before stating the uniform properties, recall the array-scale parameters introduced in Section 4: d=m−1,L=⌈C0KbN⌉,e∗=⌈C04K2bN2⌉,ℓcol=⌈L/K⌉,d=m-1, L= C_0Kb_N , e_*= C_0^4K^2b_N^2 , _ col= L/K , ϵarr=cϵK3bN2m3T,S0=Scol. _ arr=c_ε K^3b_N^2m^3T, S_0=S_ col. Here L is the candidate-list scale, e∗e_* is the required number of positive listening observations before raw decoding, ℓcol _ col is the disjoint-column scale used in the array arguments, ϵarr _ arr is the allowed exceptional-column fraction, and S0S_0 is the number of public array columns. Recall also that α0=2−40 _0=2^-40 is the listening probability and that n is the bootstrap block length from (7). For a complete block b and a positive set P⊆IbP I_b, write Di←j,b(P)D_i← j,b(P) for the output of Algorithm 11 when receiver i tests player j using P. For (A5) and (A8), fix a complete block b, players i≠ji≠ j, a support χ, receiver choices (ℒi,bi)(L_i,b_i), and a message μj∈ℳj _j∈ M_j. For each target column w, put yw:=(πj,b,w−1(μj),w),Pw(x−i,−j):=Pxwith xj=yw,y_w:= ( _j,b,w^-1( _j),w ), P_w(x_-i,-j):=P_x x_j=y_w, where x−i,−j=(xk)k∉i,jx_-i,-j=(x_k)_k∉\i,j\ consists of fixed raw entries. Write i,j,b,w(P) Cov_i,j,b,w(P) if the exclusion equations for column (j,b,w)(j,b,w) satisfy (85). Lemma 29 (Uniform sampled arm arrays). On the construction branch (11), fix any reserved mask matrix (Cq,t)(C_q,t), with probability at least 1−CarrN−401-C_ arrN^-40 the code is certified and the following hold simultaneously for every complete block and all specified inputs. Here CarrC_ arr is universal; the probability is over the remaining public-construction randomness. (A1) For any L raw entries from distinct columns of one player, outside at most hexch_ exc positions every arm occurs among their cy(t)c_y(t) at least L/(2K)L/(2K) times. We call this property A1′. (A2) Fix a receiver and ℓcol _ col tuples, each containing one raw entry of every other player. If each player’s columns are distinct across the tuples, then outside one set of at most hexch_ exc positions, for every arm a at least ℓcol/16 _ col/16 tuples have all their played arms different from a. (A3) For every player s, native label μ∈ℳsμ∈ M_s, set E′⊆IbE I_b with |E′|≥e∗|E |≥ e_*, and map β:Ib→[K]β:I_b→[K], |w∈[S0]:∑t∈E′∩ℒs,b,wcs,b,w,t(πs,b,w−1(μ))=β(t)>2α0|E′|K|≤ϵarrS0. | \w∈[S_0]: _t∈ E _s,b,w1\c_s,b,w,t( _s,b,w^-1(μ))=β(t)\> 2 _0|E |K \ |≤ _ arrS_0. (A4) For every support χ∈0,1Ib×[K]χ∈\0,1\^I_b×[K] with Gχ≥2Ke∗/α0G_χ≥ 2Ke_*/ _0 and every receiver i, |w∈[S0]:∑t∈ℒi,b,wχt(bi,b,w(t))<α0Gχ2K|≤ϵarrS0. | \w∈[S_0]: _t _i,b,w _t(b_i,b,w(t))< _0G_χ2K \ |≤ _ arrS_0. (A5) Fix the common data above with dj≥1d_j≥ 1, messages (μk)k∉i,j( _k)_k∉\i,j\, a child destination cdest∈0,…,dj−1c_ dest∈\0,…,d_j-1\, and an echo u∈[A]u∈[A]. Conditional on the public table, if every nonreceiver player chooses an independent uniform column and transmits its fixed message, the probability that quota holds and the decoder retains an incorrect class-2 ROOT label with destination cdestc_ dest and echo u is at most ϵarr _ arr. (A6) For every player, position, and arm a, the fraction of columns listening on a lies in [α0/(2K),2α0/K][ _0/(2K),2 _0/K]. For each native message, the fraction whose played arm is a is at most (1+1/m)/K(1+1/m)/K. (A7) For every mask row q∈[M]q∈[M], player s, and column w∈[S0]w∈[S_0], set ℛq,b:=t∈Ib:Cq,t=1R_q,b:=\t∈ I_b:C_q,t=1\. Then |ℒs,b,w∩ℛq,b|≤2α0|ℛq,b|+C0Λ.|L_s,b,w _q,b|≤ 2 _0|R_q,b|+C_0 . (A8) Fix the common data above and x−i,−jx_-i,-j. At most ϵarrS0 _ arrS_0 target columns w satisfy |Pw(x−i,−j)|≥e∗|P_w(x_-i,-j)|≥ e_* but fail i,j,b,w(Pw(x−i,−j)) Cov_i,j,b,w(P_w(x_-i,-j)). B.7 List bounds, authentication and recovery The results of this subsection are stated for the all-bootstrap auxiliary execution with exact-uniform private draws. In Proposition 3 we couple this execution to the physical initialization. Since the two executions agree until the first activation, and the support bound below implies that recovery occurs before any activation on the good event, the recovery guarantees transfer to the physical initialization. Recall that hexch_ exc is the allowed exceptional-position count and ϵarr _ arr is the exceptional-column fraction. For the fixed support and receiver listening choices used above, recall E=t∈ℒi:χt(bi(t))=1,s=|E|,E=\t _i: _t(b_i(t))=1\, s=|E|, and, for a tuple x of the other senders’ raw entries, Px⊆EP_x E is the resulting positive listening set defined in (88). Lemma 30 (Candidate retention). For a fixed sender, receiver, and block, let C be the set of raw entries (ν,w)(ν,w) that pass the coverage, unique-solution, and overlap tests of Algorithm 11. Then ||<L.|C|<L. Let (μ⋆,w⋆)(μ ,w ) be the sender’s actual native message and column, and let ν⋆=πw⋆−1(μ⋆)ν = _w ^-1(μ ), y⋆=(ν⋆,w⋆)y =(ν ,w ). Conditional on the precolumn history, private keys, receiver column, and current messages, Pr(|Px|≥e∗ and y⋆∉)≤2ϵarr+dℓcolS0. \! (|P_x|≥ e_* and y )≤ 2 _ arr+ d _ colS_0. Proof. Suppose L candidates survive for positive set PxP_x, and denote them by y1,…,yLy_1,…,y_L. The decoder gives at most one candidate per column. Property A1′ therefore applies, and gives ∑k=1L∑t∈Pxcyk(t)=bi(t) _k=1^L _t∈ P_x1\c_y_k(t)=b_i(t)\ ≥L2K(|Px|−hexc) ≥ L2K(|P_x|-h_ exc) ≥L|Px|4K. ≥ L|P_x|4K. The second inequality uses |Px|≥e∗|P_x|≥ e_* and hexc≤e∗/2h_ exc≤ e_*/2. Each surviving candidate satisfies the exclusion equations, so every counted match lies in its own listening set. Summing (86) consequently gives ∑k=1L∑t∈Pxcyk(t)=bi(t)≤64α0L|Px|K. _k=1^L _t∈ P_x1\c_y_k(t)=b_i(t)\≤ 64 _0L|P_x|K. This contradicts 64α0<1/464 _0<1/4, and proves the list bound. Fix the conditioning in the statement. Then E, s, and each sender’s native message are fixed, while the d sender columns remain independent and uniform. If s<e∗s<e_*, then |Px|≤s<e∗|P_x|≤ s<e_*, so the event |Px|≥e∗\|P_x|≥ e_*\ is impossible. Assume s≥e∗s≥ e_* and call a column tuple deficient when |Px|<s/32|P_x|<s/32. If ℓcol _ col deficient tuples x(1),…,x(ℓcol)x^(1),…,x^( _ col) used distinct columns within each sender, A2 would imply ∑k=1ℓcol|Px(k)| _k=1 _ col|P_x^(k)| ≥ℓcol16(s−hexc) ≥ _ col16(s-h_ exc) >ℓcols32, > _ cols32, contrary to their deficiency. Choose a maximal family disjoint in every sender’s column. It has fewer than ℓcol _ col members, and every deficient tuple shares some sender-column pair with this family. There are at most dℓcold _ col such pairs; each has probability 1/S01/S_0. The union bound proves Pr|Px|<s/32≤dℓcol/S0. \|P_x|<s/32\≤ d _ col/S_0. (89) The true address always satisfies the exclusion equations. Property A3 fails for its column with probability at most ϵarr _ arr. Outside that event and deficiency, its overlap count satisfies ∑t∈Px∩ℒwcπw−1(μ),w(t)=bi(t) _t∈ P_x _w1\c_ _w^-1(μ),w(t)=b_i(t)\ ≤2α0sK ≤ 2 _0sK ≤64α0|Px|K. ≤ 64 _0|P_x|K. For coverage, first fix the other senders’ actual columns. A8 bounds by ϵarr _ arr the conditional probability that |Px|≥e∗|P_x|≥ e_* while coverage fails for the target’s independent uniform column. Averaging over the fixed columns preserves this bound. Under coverage, injectivity makes the true address the unique solution. Hence the event |Px|≥e∗∩y⋆∉\|P_x|≥ e_*\∩\y \ is contained in the union of the A3 exception, deficiency, and the A8 exception, whose total probability is at most 2ϵarr+dℓcol/S02 _ arr+d _ col/S_0. ∎ For a nonroot player i, put p(i):=⌊i−12⌋,ciloc:=i−(2p(i)+1)∈0,1,p(i):= i-12 , c_i loc:=i-(2p(i)+1)∈\0,1\, so that p(i)p(i) is the parent of i and cilocc_i loc is the local child index used in a ROOT label sent from p(i)p(i) to i. Define the false authenticated-ROOT event i,b:=∃k∈0,1,v∈0,…,A−1:ROOT(ciloc,k,v,Ui)∈Reti←p(i),b,ROOT(ciloc,k,v,Ui)≠μp(i),b. F_i,b:= \ array[]c∃\,k∈\0,1\,\ v∈\0,…,A-1\:\\[-1.0pt] ROOT(c_i loc,k,v,U_i) _i← p(i),b,\\[-1.0pt] ROOT(c_i loc,k,v,U_i)≠ _p(i),b array \. (90) Lemma 31 (Authentication of a root digit). Fix a complete block b and a nonroot player i. Then Pr(i,b)≤ϵarr+dℓcolS0+LA. ( F_i,b)≤ _ arr+ d _ colS_0+ LA. Proof. Fix b and i, and suppress these indices in the notation for the fixed receiver. Thus E is its potential positive listening set, s=|E|s=|E|, and P=Pi,bP=P_i,b is its actual positive listening set. If s<e∗s<e_*, then |P|≤s<e∗|P|≤ s<e_*, so Algorithm 11 returns the empty list and i,b F_i,b is impossible. Assume henceforth that s≥e∗s≥ e_*. We first record two deterministic consequences of A1′ and the code distance. There are fewer than L columns containing a class-1 raw address. Indeed, if y1,…,yLy_1,…,y_L were class-1 addresses in distinct columns, then their class definition and A1′ would give 2LsκarrK>∑q=1L(|Iyq|+|Jyq|)≥L(s−hexc)2K≥Ls4K, 2Ls _ arrK> _q=1^L (|I_y_q|+|J_y_q| )≥ L(s-h_ exc)2K≥ Ls4K, contradicting κarr>8 _ arr>8. Next consider a column w for which there exists a set P′⊆EP E with |P′|≥s/32|P |≥ s/32 such that the exclusion equations generated by P′P satisfy the coverage condition (85). Call such a P′P a witness for w. A witness column contains at most one class-1 raw address. To prove this, suppose that y=(ν,w)y=(ν,w) and y′=(ν′,w)y =(ν ,w) were distinct class-1 addresses in the same witness column. Lemma 28 gives at least Harr/8H_ arr/8 code rows on which GνGν and Gν′Gν differ. For each such row, coverage supplies at least ⌈|P′|/(64KHarr)⌉ |P |/(64KH_ arr) usable occurrences. At every such occurrence exactly one of cy(t)c_y(t) and cy′(t)c_y (t) equals the receiver arm bi(t)b_i(t). Hence |Iy|+|Iy′|≥Harr8⌈|P′|64KHarr⌉≥s16384K.|I_y|+|I_y |≥ H_ arr8 |P |64KH_ arr ≥ s16384K. On the other hand, since both addresses are class 1, |Iy|+|Iy′|<2sκarrK=s131072K,|I_y|+|I_y |< 2s _ arrK= s131072K, a contradiction. For each witness column w that contains a class-1 raw address, let (νw,w)( _w,w) denote that unique address and put μw:=πw(νw) _w:= _w( _w). Define i,b:=e∈[A]:∃w,k∈0,1,v∈0,…,A−1 with μw=ROOT(ciloc,k,v,e).D_i,b:= \e∈[A]:∃\,w,\ k∈\0,1\,\ v∈\0,…,A-1\ with _w=ROOT(c_i loc,k,v,e) \. Because fewer than L columns contain a class-1 address, |i,b|<L|D_i,b|<L. Moreover, i,bD_i,b is determined by the public arrays, the fixed reward support, and player i’s fresh receiver column in block b; that fresh column is independent of the private key UiU_i. Consequently PrUi∈i,b=[|i,b|A]≤LA. \U_i _i,b\=E [ |D_i,b|A ]≤ LA. (91) Let i,b:=|Pi,b|<s/32 D_i,b:=\|P_i,b|<s/32\ be the deficiency event. By (89), Pr(i,b)≤dℓcolS0. ( D_i,b)≤ d _ colS_0. (92) Suppose that i,b D_i,b does not occur and that a false retained ROOT label contributing to i,b F_i,b is produced by a class-1 raw address. Since the label is retained, its column satisfies coverage for the actual set Pi,bP_i,b; since |Pi,b|≥s/32|P_i,b|≥ s/32, the set Pi,bP_i,b is a witness for that column. The retained label has echo UiU_i, so by the definition of i,bD_i,b we must have Ui∈i,bU_i _i,b. Thus the class-1 part of i,b F_i,b is contained in i,b∪Ui∈i,b. D_i,b∪\U_i _i,b\. Equations (91)–(92) therefore bound its probability by dℓcol/S0+L/Ad _ col/S_0+L/A. It remains to control false retained ROOT labels produced by class-2 raw addresses. For each fixed value u∈[A]u∈[A], apply A5 with destination cilocc_i loc and echo u. A retained label can occur only when |Pi,b|≥e∗|P_i,b|≥ e_*, so A5 gives probability at most ϵarr _ arr that an incorrect class-2 ROOT label with that destination and echo is retained. Averaging this bound over the uniform key UiU_i yields Pri,b occurs through a class-2 raw address≤ϵarr. \ F_i,b occurs through a class-2 raw address\≤ _ arr. Combining the class-1 and class-2 cases proves the lemma. ∎ Let htree=⌊log2m⌋h_ tree= _2m be the tree height. Let :=(i,j):j∈2i+1,2i+2,j<mT:=\(i,j):j∈\2i+1,2i+2\,\ j<m\ be the set of parent-child edges, with the parent written first. For a complete block b∈[Bblk]b∈[B_ blk], write χ(b)χ^(b) for its support matrix and Gb:=∑t,aχt(b)(a).G_b:= _t,aχ^(b)_t(a). Define the set of informative block indices by ℐ:=b∈[Bblk]:Gb≥128Ke∗α0.I:= \b∈[B_ blk]:G_b≥ 128Ke_* _0 \. Write R:=|ℐ|R:=|I|, and when R≥qR≥ q let bqb_q denote the qqth smallest element of ℐI. Recall from Subsection B.5 that J^i,k J_i,k is player i’s stored estimate of digit JkJ_k and ℋijH_ij is the child-key list stored by player i for child j. For b=0,1,…,Bblkb=0,1,…,B_ blk, write J^i,k[b] J_i,k^[b], J^i[b] J_i^[b], and ℋij[b]H_ij^[b] for the corresponding stored values immediately after the decoding/list updates of complete block b, with b=0b=0 denoting their initial values. Proposition 32 (Outward recovery). Fix δprop∈(0,1) _ prop∈(0,1) and set rboot:=1+⌈8L(2htree+log(m/δprop))⌉.r_ boot:=1+ 8L (2h_ tree+ (m/ _ prop) ) . There is an event recG_ rec such that Pr(recc)≤Cm2Bblk(ϵarr+dℓcolS0+LA)+δprop, (G_ rec^c)≤ Cm^2B_ blk ( _ arr+ d _ colS_0+ LA )+ _ prop, (93) and on recG_ rec the following statements hold simultaneously: (i) For every b∈0,…,Bblkb∈\0,…,B_ blk\, every player i, and k∈0,1k∈\0,1\, J^i,k[b]≠⊥⟹J^i,k[b]=Jk. J_i,k^[b]≠ J_i,k^[b]=J_k. (i) For every b∈0,…,Bblkb∈\0,…,B_ blk\ and every (i,j)∈(i,j) , ℋij[b]≠⊥⟹Uj∈ℋij[b]and|ℋij[b]|<L.H_ij^[b]≠ U_j _ij^[b] |H_ij^[b]|<L. (i) If R≥1R≥ 1, then every child list is initialized after the first informative block: ℋij[b1]≠⊥for every (i,j)∈.H_ij^[b_1]≠ every (i,j) . (iv) If R≥rbootR≥ r_ boot, then every player is informed after the rbootr_ bootth informative block: J^i[brboot]=Jfor every i∈0,…,m−1. J_i^[b_r_ boot]=J every i∈\0,…,m-1\. Moreover, if R<rbootR<r_ boot, then the support in complete blocks obeys ∑b=1BblkGb≤128Ke∗Tα0n+(rboot−1)Kn. _b=1^B_ blkG_b≤ 128Ke_*T _0n+(r_ boot-1)Kn. (94) Proof. Let →:=(r,s):(r,s)∈ or (s,r)∈, T:=\(r,s):(r,s) or (s,r) \, where the first coordinate is the receiver and the second is the sender. Define ℬquota _ quota :=⋃b∈ℐ⋃i=0m−1|Pi,b|<e∗, := _b \ _i=0^m-1\|P_i,b|<e_*\, ℬrej _ rej :=⋃b=1Bblk⋃(i,j)∈→(|Pi,b|≥e∗∩μj,b∉Reti←j,b), := _b=1^B_ blk\ _(i,j)∈ T (\|P_i,b|≥ e_*\∩\ _j,b _i← j,b\ ), ℬfalse _ false :=⋃b=1Bblk⋃i=1m−1i,b, := _b=1^B_ blk\ _i=1^m-1 F_i,b, ℬ :=ℬquota∪ℬrej∪ℬfalse. :=B_ quota _ rej _ false. These three events are, respectively, failure to obtain the positive quota in an informative block, rejection of an actual neighboring message despite meeting the quota, and retention of a false authenticated ROOT label. Fix b∈ℐb and a receiver i. A4 gives si,b≥α0Gb2K≥64e∗s_i,b≥ _0G_b2K≥ 64e_* outside a set of receiver columns of probability at most ϵarr _ arr. Conditional on such a receiver column, (89) gives |Pi,b|≥si,b/32≥2e∗|P_i,b|≥ s_i,b/32≥ 2e_* except with probability at most dℓcol/S0d _ col/S_0. Hence Pr|Pi,b|<e∗≤ϵarr+dℓcolS0. \|P_i,b|<e_*\≤ _ arr+ d _ colS_0. For each directed neighboring pair (i,j)(i,j) and block b, Lemma 30 gives Pr(|Pi,b|≥e∗,μj,b∉Reti←j,b)≤2ϵarr+dℓcolS0. (|P_i,b|≥ e_*,\ _j,b _i← j,b )≤ 2 _ arr+ d _ colS_0. Lemma 31 gives, for every nonroot i and block b, Pr(i,b)≤ϵarr+dℓcolS0+LA. ( F_i,b)≤ _ arr+ d _ colS_0+ LA. There are at most mBblkmB_ blk quota tests, m2Bblkm^2B_ blk directed-neighbor rejection tests, and (m−1)Bblk(m-1)B_ blk false-authentication tests. A union bound therefore gives Pr(ℬ)≤Cm2Bblk(ϵarr+dℓcolS0+LA). (B)≤ Cm^2B_ blk ( _ arr+ d _ colS_0+ LA ). (95) We next prove the first three conclusions on ℬcB^c. For b=0,1,…,Bblkb=0,1,…,B_ blk let (b) Inv(b) be the conjunction of J^i,k[b]≠⊥ J_i,k^[b]≠ ⟹J^i,k[b]=Jk J_i,k^[b]=J_k (0≤i<m,k∈0,1), (0≤ i<m,\ k∈\0,1\), (96) ℋij[b]≠⊥ _ij^[b]≠ ⟹Uj∈ℋij[b],|ℋij[b]|<L U_j _ij^[b], |H_ij^[b]|<L ((i,j)∈). ((i,j) ). (97) Initially, the root stores J0,J1J_0,J_1, every nonroot digit is ⊥ , and every child list is ⊥ , so (0) Inv(0) holds. Assume (b−1) Inv(b-1) and consider the updates at the end of complete block b. First fix a nonroot player i and a digit k∈0,1k∈\0,1\ that is ⊥ before the update. If the digit remains ⊥ , there is nothing to prove. Otherwise Algorithm 12 stores a value v from a retained label ROOT(ciloc,k,v,Ui)∈Reti←p(i),b.ROOT(c_i loc,k,v,U_i) _i← p(i),b. Since ℬfalseB_ false does not occur, this retained label equals the actual parent message μp(i),b _p(i),b. Hence the parent was informed when the block message was chosen and sent μp(i),b=ROOT(ciloc,k,J^p(i),k[b−1],Ui). _p(i),b=ROOT(c_i loc,k, J_p(i),k^[b-1],U_i). By (96), J^p(i),k[b−1]=Jk J_p(i),k^[b-1]=J_k, so the newly stored value is v=Jkv=J_k. Thus (96) is preserved. Now fix a parent-child edge (i,j)∈(i,j) . If ℋij[b−1]≠⊥H_ij^[b-1]≠ , the list is immutable and (97) is preserved. Suppose instead that ℋij[b−1]=⊥H_ij^[b-1]= . Since child lists are immutable, this list was ⊥ in every earlier block. We claim that J^j[b−1]=⊥ J_j^[b-1]= . Otherwise player j must previously have stored at least one digit from a retained label ROOT(cjloc,k,v,Uj)ROOT(c_j loc,k,v,U_j). But while ℋij=⊥H_ij= , every actual message of parent i addressed to j has echo ⊥ ; messages not addressed to j have a different local-child field, and an uninformed parent sends a DISC label. Thus such a retained authenticated ROOT label could not equal the actual parent message, so some event j,b′ F_j,b would have occurred in an earlier block b′<b <b, contradicting ℬfalsecB_ false^c. Hence J^j[b−1]=⊥ J_j^[b-1]= , and player j sends μj,b=DISC(Uj) _j,b=DISC(U_j) in block b. If ℋijH_ij remains ⊥ after decoding block b, then (97) is vacuous. If it is initialized, the child-decoder output used by player i is nonempty, so Algorithm 11 necessarily has |Pi,b|≥e∗|P_i,b|≥ e_*. Since ℬrejB_ rej does not occur, the actual child message DISC(Uj)DISC(U_j) belongs to Reti←j,bRet_i← j,b. Therefore the newly stored list contains UjU_j. Lemma 30 gives fewer than L raw candidates and hence fewer than L retained native labels, so the stored DISC-key list has size below L. This proves (97) and completes the induction. If R≥1R≥ 1, consider the first informative block b1b_1. For any edge (i,j)(i,j) whose child list is still ⊥ at the start of this block, the preceding argument shows that j sends DISC(Uj)DISC(U_j). Since ℬquotaB_ quota does not occur, |Pi,b1|≥e∗|P_i,b_1|≥ e_*, and since ℬrejB_ rej does not occur, this actual DISC label is retained. Thus every such list is initialized in block b1b_1. This proves conclusions (i)–(i) on ℬcB^c. It remains to prove the finite informative-block recovery time. Fix a root-to-node path v0=0,v1,…,vh,h≤htree.v_0=0,v_1,…,v_h, h≤ h_ tree. Assume R≥rbootR≥ r_ boot. The first informative block b1b_1 has already initialized all child lists. For q=1,…,rboot−1q=1,…,r_ boot-1, regard bq+1b_q+1 as trial q, and let ℱq−1F_q-1 contain all private choices revealed before the message choices of that block. On a history on which no event in ℬB has yet occurred and the path is not yet fully informed, let vℓqv_ _q be the first uninformed vertex on the path and choose deterministically one missing digit kq∈0,1k_q∈\0,1\ of that vertex. Its parent vℓq−1v_ _q-1 is informed. By conclusions (i)–(i), its list for child vℓqv_ _q contains UvℓqU_v_ _q and has size below L. Let ZqZ_q be the indicator that in block bq+1b_q+1 this parent chooses that child, digit kqk_q, and echo UvℓqU_v_ _q. Conditional on ℱq−1F_q-1, Pr(Zq=1∣ℱq−1)≥12⋅12⋅1L=:p0=14L. (Z_q=1 _q-1)≥ 12· 12· 1L=:p_0= 14L. If a bad event in ℬB has already occurred or the path has already become fully informed, extend the probability space by defining ZqZ_q to be an independent Bernoulli(p0)(p_0) variable. With this extension, for every q, [e−Zq∣ℱq−1]≤1−(1−e−1)p0,E[e^-Z_q _q-1]≤ 1-(1-e^-1)p_0, and iteration gives exp(−∑q=1rZq)≤exp−r(1−e−1)p0(r≥1).E (- _q=1^rZ_q )≤ \-r(1-e^-1)p_0\ (r≥ 1). (98) On ℬcB^c, whenever Zq=1Z_q=1, the actual parent message is ROOT(cvℓqloc,kq,Jkq,Uvℓq).ROOT(c_v_ _q loc,k_q,J_k_q,U_v_ _q). Because block bq+1b_q+1 is informative, ℬquotacB_ quota^c gives quota at the child, and ℬrejcB_ rej^c ensures that the actual message is retained. Finally ℬfalsecB_ false^c ensures that no different retained ROOT label with the same destination and authentication key can be chosen instead. Hence player vℓqv_ _q stores the previously missing digit JkqJ_k_q. Thus each success Zq=1Z_q=1 delivers one new digit on the path. Since at most two digits are needed on each of the h edges, the event that ℬcB^c holds and the path is still unfinished after r trials implies ∑q=1rZq<2h≤2htree. _q=1^rZ_q<2h≤ 2h_ tree. By Markov’s inequality and (98), Prℬc and the path is unfinished after r trials \B^c and the path is unfinished after r trials\ ≤ ≤ Pre−∑q=1rZq>e−2htree≤exp2htree−r(1−e−1)p0. \e^- _q=1^rZ_q>e^-2h_ tree \≤ \2h_ tree-r(1-e^-1)p_0\. For r=rboot−1r=r_ boot-1, r(1−e−1)p0≥2(1−e−1)(2htree+logmδprop)≥2htree+logmδprop,r(1-e^-1)p_0≥ 2(1-e^-1) (2h_ tree+ m _ prop )≥ 2h_ tree+ m _ prop, because 2(1−e−1)>12(1-e^-1)>1. Hence the preceding probability is at most δprop/m _ prop/m. A union bound over the at most m root-to-node paths gives Pr(ℬc∩R≥rboot∩∃i:J^i[brboot]≠J)≤δprop. (B^c∩\R≥ r_ boot\∩\∃ i: J_i^[b_r_ boot]≠ J\ )≤ _ prop. (99) Combining (95) and (99), and letting recG_ rec be the event on which conclusions (i)–(iv) hold, proves (93). Finally suppose R<rbootR<r_ boot. Each informative complete block has support at most KnKn, so their total support is at most (rboot−1)Kn(r_ boot-1)Kn. Every noninformative complete block satisfies Gb<128Ke∗/α0G_b<128Ke_*/ _0, and there are at most Bblk≤T/nB_ blk≤ T/n such blocks. Therefore ∑b=1BblkGb≤(rboot−1)Kn+128Ke∗Tα0n, _b=1^B_ blkG_b≤(r_ boot-1)Kn+ 128Ke_*T _0n, which is (94). ∎ B.8 Reserved masks and bootstrap clocks For a support matrix χ∈0,1T×Kχ∈\0,1\^T× K, write gt=∑aχt(a)g_t= _a _t(a) and G(t)=∑u≤tguG(t)= _u≤ tg_u. Lemma 33 (Uniform reserved masks). With probability at least 1−CN−401-CN^-40, the sampled masks satisfy both properties below. (i) Every row has at most 2pT+C0Λ2pT+C_0 reserved positions, and every complete block in every row has at most 2pn+C0Λ2pn+C_0 . (i) For every support matrix χ, all but at most M/NM/N rows satisfy, at every complete-block boundary t, 12pG(t)−KC0Λ≤∑u≤tCj,ugu≤2pG(t)+KC0Λ. 12pG(t)-KC_0 ≤ _u≤ tC_j,ug_u≤ 2pG(t)+KC_0 . (100) Proof. Fix χ, a row j, and a complete-block boundary t. Put X=∑u≤tCj,ugu/KX= _u≤ tC_j,ug_u/K and μ=pG(t)/Kμ=pG(t)/K. For a∈[0,1]a∈[0,1], convexity gives ea−1≤(e−1)ae^a-1≤(e-1)a and e−a−1≤−(1−e−1)ae^-a-1≤-(1-e^-1)a. Independence implies eX ^X =∏u≤t(1+p(egu/K−1))≤e(e−1)μ, = _u≤ t (1+p(e^g_u/K-1) )≤ e^(e-1)μ, e−X ^-X =∏u≤t(1+p(e−gu/K−1))≤e−(1−e−1)μ. = _u≤ t (1+p(e^-g_u/K-1) )≤ e^-(1-e^-1)μ. Since e−1<2e-1<2 and 1−e−1>1/21-e^-1>1/2, Markov’s inequality yields PrX>2μ+C0Λ \X>2μ+C_0 \ ≤e−C0Λ, ≤ e^-C_0 , PrX<μ/2−C0Λ \X<μ/2-C_0 \ ≤e−C0Λ. ≤ e^-C_0 . Let a row be bad for χ if either inequality fails at some complete-block boundary. There are at most T such boundaries, so its probability is at most 2Te−C0Λ≤N−302Te^-C_0 ≤ N^-30. The bad-row indicators are independent across j. As M=N2M=N^2, Prmore than M/N rows fail≤(eN−29)N. \more than M/N rows fail\≤(eN^-29)^N. There are 2KT2^KT support matrices and KT≤N/4KT≤ N/4. Consequently the probability that (i) fails is at most expKTlog2+N(1−29logN)≤N−40. \KT 2+N(1-29 N)\≤ N^-40. For (i), apply the upper exponential-moment bound with every weight equal to one, first on [T][T] and then on each complete block. Each count exceeds twice its mean plus C0ΛC_0 with probability at most e−C0Λe^-C_0 . The union over at most M(T+1)M(T+1) counts is at most N−40N^-40 after increasing C0C_0. This proves both claims. ∎ Lemma 34 (Bootstrap clock concentration). Fix a deterministic reward matrix, the players’ private keys, and the root index J. Assume that row J satisfies both reserved-mask properties of Lemma 33 for the reward support in (5), and use the public arrays of Lemma 29. In each block, choose the bootstrap messages before drawing fresh columns independently and uniformly from [Scol][S_ col], conditional on the preceding history. All players use the corresponding communication sequences on reserved rounds; their actions on other rounds may be arbitrary. Let ℒi,b⊆IbL_i,b I_b be player i’s listening positions in block b, expressed in calendar time. Write Ct=CJ,tC_t=C_J,t for the selected row’s reserved indicator and GC(t)=∑u≤tCuguG_C(t)= _u≤ tC_ug_u for its cumulative reserved support. Define the true-row counts Xi,b X_i,b =∑t∈Ibt∈ℒi,bCtYi,t>0, = _t∈ I_b1\t _i,b\C_t1\Y_i,t>0\, i(t) _i(t) =Kα0p∑b:bn≤tXi,b. = K _0p _b:bn≤ tX_i,b. These counts are defined mathematically even before a player recovers the true table row. Recall the activation threshold QbootQ_ boot from (9). With probability at least 1−CmTe−C0Λ1-CmTe^-C_0 , simultaneously for every player and complete-block boundary t, G(t)8e−Qboot2≤i(t)≤8G(t)+Qboot2. G(t)8e- Q_ boot2 _i(t)≤ 8G(t)+ Q_ boot2. (101) Here C is universal. Proof. Let ℱb−1F_b-1 contain the public arrays, fixed private keys, root index, and all choices before block b’s fresh columns. In particular, each player’s block message is ℱb−1F_b-1-measurable. For t∈Ibt∈ I_b and a∈[K]a∈[K] with Ct=1C_t=1 and rt(a)>0r_t(a)>0, property (A6) gives probability between α0/(2K) _0/(2K) and 2α0/K2 _0/K that player i listens on arm a. For each other player, the probability of playing that arm is at most (1+1/m)/K≤1/m(1+1/m)/K≤ 1/m, since K≥m+1K≥ m+1. Let Li,t,aL_i,t,a be the event that player i listens on arm a at t, and let Aj,tA_j,t denote player j’s chosen arm. Conditional independence of columns across players gives the exact factorization Pr(Li,t,a∩⋂j≠iAj,t≠a∣ℱb−1)=Pr(Li,t,a∣ℱb−1)∏j≠iPr(Aj,t≠a∣ℱb−1). \! (L_i,t,a∩ _j≠ i\A_j,t≠ a\ _b-1 )= (L_i,t,a _b-1) _j≠ i (A_j,t≠ a _b-1). Moreover, Prall other players avoid a∣ℱb−1≥(1−1/m)m−1≥e−1. \all other players avoid a _b-1\≥(1-1/m)^m-1≥ e^-1. The last inequality follows from log(1−x)≥−x/(1−x) (1-x)≥-x/(1-x) at x=1/mx=1/m. The event in the factorization is precisely a positive listening observation on arm a. Put GC,b=∑t∈IbCtgtG_C,b= _t∈ I_bC_tg_t. Summing over supported reserved pairs gives α02eKGC,b≤[Xi,b∣ℱb−1]≤2α0KGC,b. _02eKG_C,b [X_i,b _b-1]≤ 2 _0KG_C,b. (102) Property (A7) and Lemma 33(i) give the pathwise increment bound 0≤Xi,b≤2α0(2pn+C0Λ)+C0Λ≤4α0pn+3C0Λ=:b∗.0≤ X_i,b≤ 2 _0(2pn+C_0 )+C_0 ≤ 4 _0pn+3C_0 =:b_*. For each player and complete-block prefix, the exponential-supermartingale Chernoff bound of Howard, Ramdas, McAuliffe, and Sekhon [13], applied with (102) and 0≤Xi,b≤b∗0≤ X_i,b≤ b_*, gives, with failure probability at most 2e−C0Λ2e^-C_0 , α04eKGC(t)−b∗C0Λ≤∑b:bn≤tXi,b≤4α0KGC(t)+b∗C0Λ. _04eKG_C(t)-b_*C_0 ≤ _b:bn≤ tX_i,b≤ 4 _0KG_C(t)+b_*C_0 . A union bound over at most mTmT player–boundary pairs makes these inequalities simultaneous. Multiply by K/(α0p)K/( _0p) and use (100). The resulting slopes are 1/(8e)1/(8e) and 88. Each additive error is bounded by 4C0KΛp+4C0KnΛ+3C02KΛ2α0p. 4C_0K p+4C_0Kn + 3C_0^2K ^2 _0p. To compare with the threshold, use n≤2C03KTn≤ 2C_0^3 KT, Λ≤bN ≤ b_N, and V^≥K5/2TΛ2 V≥ K^5/2 T ^2. Then the preceding error is at most 8C04V^+(4C0+3C02α0)KbN2p.8C_0^4 V+ (4C_0+ 3C_0^2 _0 ) Kb_N^2p. Choose the fixed universal C0C_0 so that 8C04≤C08/28C_0^4≤ C_0^8/2 and 4C0+3C02/α0≤C08/24C_0+3C_0^2/ _0≤ C_0^8/2. The error is then at most Qboot/2Q_ boot/2, which proves (101). ∎ B.9 Proof of the public-array lemma Proof of Lemma 29. Condition first on an arbitrary certified output G of Lemma 28. All estimates below are uniform in these choices. At the end we add the code-certification failure probability. Parameter bounds. On the construction branch, enlarging CbC_b gives T>Cb2K3Λ4,n≤T,T>C_b^2K^3 ^4, n≤ T, 0<ϵarr<1,Γ≍Kn.0< _ arr<1, Kn. Moreover n≤2C03KTn≤ 2C_0^3 KT and L≤2C0KbNL≤ 2C_0Kb_N. By the definitions of A and ϵarr _ arr, choosing CA≥32eC0/cϵC_A≥ 32eC_0/c_ε yields ϵarrA2eL≥cϵCA2eC0K3bNm2T+1T≥4KΛ. _ arrA2eL≥ c_εC_A2eC_0 K^3b_Nm^2 T+1T≥ 4K . We shall also use LA≤ϵarr8e,ϵarr≥cϵN. LA≤ _ arr8e, _ arr≥ c_εN. ϵarrS0≥CSdℓcolΓ. _ arrS_0≥ C_Sd _ col . The first term in (12) dominates the second on this branch, so S0=O(N3/2)S_0=O(N^3/2). The definitions give A=O(N)A=O(N) and Qarr=O(N2)Q_ arr=O(N^2); hence every alphabet and column-count logarithm is O(Λ)O( ). A1′ and A2. Fix one family of entries and one position t. For A1′, distinct columns give independent uniform candidate arms. For A2, the tuples are independent at t, and within each tuple the d played arms are independent and uniform. Since d≤K−2d≤ K-2, (1−1/K)d≥e−d/(K−1)≥e−1.(1-1/K)^d≥ e^-d/(K-1)≥ e^-1. Chernoff’s inequality [5], followed by a union over a∈[K]a∈[K], bounds the respective probabilities that t is bad by q1:=Ke−L/(8K),q2:=Ke−ℓcol/(8e).q_1:=Ke^-L/(8K), q_2:=Ke^- _ col/(8e). For either property these bad-position indicators are independent over t. Since L/K,ℓcol≥C0bNL/K, _ col≥ C_0b_N, a sufficiently large C0C_0 makes q:=max(q1,q2)≤hexc/(ne2)q:= (q_1,q_2)≤ h_ exc/(ne^2). If hexc≤nh_ exc≤ n, the binomial upper tail gives Prmore than hexc bad positions≤(enq/hexc)hexc≤e−hexc. \more than h_ exc bad positions\≤(enq/h_ exc)^h_ exc≤ e^-h_ exc. For hexc>nh_ exc>n both properties are automatic. The logarithm of the number of players, blocks, and admissible families is O(Llog(QarrS0)+ℓcolmlog(QarrS0)+Λ)=O(C0KΛ2).O\! (L (Q_ arrS_0)+ _ colm (Q_ arrS_0)+ )=O(C_0K ^2). Because hexc≥C04KΛ2/(128κarr)h_ exc≥ C_0^4K ^2/(128 _ arr), the union bound makes the failure probability for A1′–A2 at most N−40N^-40. A3 and A4. For fixed (μ,E′,β)(μ,E ,β), the count in A3 has law Bin(|E′|,α0/K)Bin(|E |, _0/K), even when the actual address of μ is fixed. Its upper-tail probability is at most e−cα0e∗/Ke^-c _0e_*/K. For A4, the count in one receiver column is a sum of independent indicators with mean α0Gχ/K≥2e∗ _0G_χ/K≥ 2e_*; its lower-tail probability is at most e−ce∗e^-ce_*. Both bounds are at most N−30N^-30 for large C0C_0. For either fixed input, columns are independent. If X counts their failures, binomial domination and ϵarr≥cϵ/N _ arr≥ c_ε/N give PrX>ϵarrS0≤(eN−30ϵarr)ϵarrS0≤e−cϵarrS0Λ. \X> _ arrS_0\≤ ( eN^-30 _ arr ) _ arrS_0≤ e^-c _ arrS_0 . (103) The A3 inputs number at most poly(N)2nKnQarrpoly(N)2^nK^nQ_ arr and the A4 inputs at most poly(N)2Knpoly(N)2^Kn. Their logarithms are O(Γ)O( ). Thus ϵarrS0≥CSdℓcolΓ _ arrS_0≥ C_Sd _ col makes their combined failure at most CN−40CN^-40. A5: raw candidates. Work on A1′–A2. Fix the data in A5, all nontarget permutations, and the target’s actual address πj,b,w−1(μj) _j,b,w^-1( _j) in each column w. For a tuple =(wk)k≠i∈[S0]dw=(w_k)_k≠ i∈[S_0]^d, put xk():=(πk,b,wk−1(μk),wk)x_k(w):=( _k,b,w_k^-1( _k),w_k) for k∉i,jk∉\i,j\ and P:=Pwj((xk())k∉i,j)P_w:=P_w_j((x_k(w))_k∉\i,j\). Let C_w contain the target’s raw entries passing quota, exclusion, coverage, uniqueness, and overlap for P_w. These tests do not use the target’s remaining permutation labels. Each column contributes at most one entry to C_w. If it contained L entries y1,…,yLy_1,…,y_L, then A1′ and hexc≤e∗/2≤|P|/2h_ exc≤ e_*/2≤|P_w|/2 would give ∑k=1L∑t∈Pcyk(t)=bi(t)≥L2K(|P|−hexc)≥L|P|4K. _k=1^L _t∈ P_w1\c_y_k(t)=b_i(t)\≥ L2K(|P_w|-h_ exc)≥ L|P_w|4K. Exclusion places each match in the corresponding listening set, while overlap bounds the sum by 64α0L|P|/K<L|P|/(4K)64 _0L|P_w|/K<L|P_w|/(4K). Thus ||<L|C_w|<L. For a class-2 raw entry y, set Wy:=|:y∈|,D0:=dℓcolS0d−1.W_y:=|\w:y _w\|, D_0:=d _ colS_0^d-1. We claim that 0≤Wy≤D0,∑yWy<LS0d.0≤ W_y≤ D_0, _yW_y<LS_0^d. (104) The sum counts pairs (,y)(w,y) with y∈y _w. To bound WyW_y, suppose ℓcol _ col counted tuples have distinct columns within each sender, and denote them by (1),…,(ℓcol)w^(1),…,w^( _ col). Quota implies s≥e∗s≥ e_* and hence hexc≤s/(128κarrK)h_ exc≤ s/(128 _ arrK). If |Iy|≥s/(κarrK)|I_y|≥ s/( _ arrK), A2 gives ∑r=1ℓcol|P(r)∩Iy|≥ℓcol16(|Iy|−hexc)>0, _r=1 _ col|P_w^(r)∩ I_y|≥ _ col16(|I_y|-h_ exc)>0, contrary to exclusion for y. Otherwise class 2 gives |Jy|≥s/(κarrK)|J_y|≥ s/( _ arrK), and A2 gives ∑r=1ℓcol|P(r)∩Jy|≥ℓcols32κarrK>64α0ℓcolsK. _r=1 _ col|P_w^(r)∩ J_y|≥ _ cols32 _ arrK> 64 _0 _ colsK. This contradicts overlap, since |P(r)|≤s|P_w^(r)|≤ s and α0<1/(2048κarr) _0<1/(2048 _ arr). Therefore a maximal family of counted tuples with disjoint columns in every sender has fewer than ℓcol _ col members. Every counted tuple shares one of fewer than dℓcold _ col sender-column pairs with that family; each pair lies in S0d−1S_0^d-1 tuples. This proves (104). A5: permutation labels. Condition further on the raw arrays. The weights WyW_y are fixed. Actual target addresses cannot produce an incorrect label; conditional on their locations, the remaining labels are uniformly permuted within each column, independently between columns. At most 2A2A ROOT labels have the specified destination and echo. Since dj≥1d_j≥ 1, Qarr−1≥A2Q_ arr-1≥ A^2, so for k distinct remaining addresses in one column, Prall k labels qualify≤(2A)k(Qarr−1)k≤ϕk,ϕ:=2/A. \all k labels qualify\≤ (2A)_k(Q_ arr-1)_k≤φ^k, φ:=2/A. Independence between columns gives the bound ϕ|D|φ^|D| for any set D of remaining addresses. Let ℋH be the sigma-field generated by the fixed A5 input, the nontarget permutations, the target actual-message locations, and all raw arm-array coordinates. Let ιy _y indicate that a remaining class-2 address carries such a label, and put Z=∑yWyιyZ= _yW_y _y. Every tuple counted as bad in A5 contributes at least one to Z. Expanding the product below and using (104) gives, for λ>0λ>0, [eλZ∣ℋ] [e^λ Z ] =[∏y1+(eλWy−1)ιy∣ℋ] =E\! [ _y\1+(e^λ W_y-1) _y\ ] ≤∏y1+ϕ(eλWy−1) ≤ _y\1+φ(e^λ W_y-1)\ ≤expϕLS0dD0(eλD0−1). ≤ \! \ φ LS_0^dD_0(e^λ D_0-1) \. Here eλw−1≤w(eλD0−1)/D0e^λ w-1≤ w(e^λ D_0-1)/D_0 for 0≤w≤D00≤ w≤ D_0. Taking λ=D0−1log(ϵarr/(ϕL))>0λ=D_0^-1 ( _ arr/(φ L))>0 and applying Markov’s inequality gives PrZ>ϵarrS0d∣ℋ≤exp−ϵarrS0dℓcollogϵarrA2eL. \Z> _ arrS_0^d \≤ \! \- _ arrS_0d _ col _ arrA2eL \. (105) The A5 probability is the number of bad tuples divided by S0dS_0^d; thus (105) bounds its failure. The number of external input choices is at most poly(N)2Kn(2K)nQarrmApoly(N)2^Kn(2K)^nQ_ arr^mA, whose logarithm is O(Γ)O( ). The parameter bounds above and a union bound make the probability of A5 failure together with A1′–A2 success at most N−40N^-40. A6 and A7. For fixed player, block, position, and arm, the number of columns listening on that arm is Bin(S0,α0/K)Bin(S_0, _0/K). For a fixed native message, the number whose played arm is that arm is Bin(S0,1/K)Bin(S_0,1/K). Chernoff bounds for the two failures in A6 are, respectively, 2e−cα0S0/Kande−cS0/(m2K).2e^-c _0S_0/K e^-cS_0/(m^2K). The second term of (12) makes their exponents arbitrarily large multiples of Λ by increasing CSC_S. There are O(mTKQarr)=O(N3)O(mTKQ_ arr)=O(N^3) index choices, so A6 fails with probability at most CN−40CN^-40. For A7, the masks are fixed. For each player, block, column, and mask row, let X=|ℒw∩ℛq,b|X=|L_w _q,b| and μ=α0|ℛq,b|μ= _0|R_q,b|. Then X is binomial and eX≤e(e−1)μ,PrX>2μ+C0Λ≤e−C0Λ.Ee^X≤ e^(e-1)μ, \X>2μ+C_0 \≤ e^-C_0 . There are at most mBblkS0M=O(N9/2)mB_ blkS_0M=O(N^9/2) choices. Increasing C0C_0 makes their union probability at most N−40N^-40. A8. Fix its common data and x−i,−jx_-i,-j. Condition on the nontarget raw arrays and entries and on the target permutations. Then the target’s address ywy_w is fixed in each column, whereas its raw arm coordinates remain independent over w. Put F:=t∈E:dxk(t)≠bi(t) for every k∉i,j.F:=\t∈ E:d_x_k(t)≠ b_i(t) for every k∉\i,j\\. For every target column w, Pw(x−i,−j)⊆FP_w(x_-i,-j) F. If |F|<e∗|F|<e_*, A8 is immediate. Otherwise let f0=|F|f_0=|F|. For w∈[S0]w∈[S_0] and code row h∈[Harr]h∈[H_ arr], count the positions t∈Ft∈ F where the target does not listen, uses row h, and leaves bi(t)b_i(t) as its unplayed pair endpoint; call this count Xw,hX_w,h. The fair offset and independent pair give Xw,h∼Bin(f0,1−α0KHarr).X_w,h (f_0, 1- _0KH_ arr ). Each counted position belongs to Pw(x−i,−j)P_w(x_-i,-j) and supplies an exclusion equation in row h. For large C0C_0, e∗≥128KHarre_*≥ 128KH_ arr; thus f0≥e∗f_0≥ e_* implies ⌈f064KHarr⌉≤(1−α0)f02KHarr. f_064KH_ arr ≤ (1- _0)f_02KH_ arr. Chernoff’s inequality and a union over h give PrminhXw,h<⌈f064KHarr⌉≤Harre−ce∗/(KHarr)≤N−30. \! \ _hX_w,h< f_064KH_ arr \≤ H_ arre^-ce_*/(KH_ arr)≤ N^-30. Since |Pw|≤f0|P_w|≤ f_0, the complementary event implies i,j,b,w(Pw) Cov_i,j,b,w(P_w). Target columns are independent under the stated conditioning. Apply (103), then union over the external inputs, whose number has logarithm O(Kn+nlog(2K)+mlog(QarrS0)+Λ)=O(Γ)O(Kn+n (2K)+m (Q_ arrS_0)+ )=O( ). The failure probability is at most N−40N^-40, uniformly under the conditioning. This argument does not condition on PwP_w. Finally, union the failures of A1′–A4 and A6–A8, the A5 failure on A1′–A2 success, and code-certification failure. Their probability is at most CarrN−40C_ arrN^-40. ∎ References [ALK20] P. Alatur, K. Y. Levy, and A. Krause (2020) Multi-player bandits: the adversarial case. Journal of Machine Learning Research 21 (77), p. 1–23. Note: https://w.jmlr.org/papers/v21/19-912.html Cited by: §2. [AVW87] V. Anantharam, P. Varaiya, and J. Walrand (1987) Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays—part i: i.i.d. rewards. IEEE Transactions on Automatic Control 32 (11), p. 968–976. Note: https://doi.org/10.1109/TAC.1987.1104491 Cited by: §2. [BK18] L. Besson and E. Kaufmann (2018) Multi-player bandits revisited. In Proceedings of Algorithmic Learning Theory, Proceedings of Machine Learning Research, Vol. 83, p. 56–92. Note: https://proceedings.mlr.press/v83/besson18a.html Cited by: §2. [BBM+18] R. Bonnefoi, L. Besson, C. Moy, E. Kaufmann, and J. Palicot (2018) Multi-armed bandit learning in IoT networks: learning helps even in non-stationary settings. In Cognitive Radio Oriented Wireless Networks, p. 173–185. Note: https://doi.org/10.1007/978-3-319-76207-4_15 Cited by: §2. [BLM13] S. Boucheron, G. Lugosi, and P. Massart (2013) Concentration inequalities: a nonasymptotic theory of independence. Oxford University Press. Note: https://doi.org/10.1093/acprof:oso/9780199535255.001.0001 Cited by: §B.3, §B.9. [BP19] E. Boursier and V. Perchet (2019) SIC-MMAB: synchronisation involves communication in multiplayer multi-armed bandits. In Advances in Neural Information Processing Systems 32, p. 12071–12080. Note: https://proceedings.neurips.c/paper_files/paper/2019/hash/c4127b9194fe8562c64dc0f5bf2c93bc-Abstract.html Cited by: §2. [BBS21] S. Bubeck, T. Budzinski, and M. Sellke (2021) Cooperative and stochastic multi-player multi-armed bandit: optimal regret with neither communication nor collisions. In Proceedings of the 34th Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 134, p. 821–822. Note: https://proceedings.mlr.press/v134/bubeck21b.html Cited by: §2. [B20] S. Bubeck and T. Budzinski (2020) Coordination without communication: optimal regret in two players multi-armed bandits. In Proceedings of the 33rd Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 125, p. 916–939. Note: https://proceedings.mlr.press/v125/bubeck20a.html Cited by: §2. [BLP+20] S. Bubeck, Y. Li, Y. Peres, and M. Sellke (2020) Non-stochastic multi-player multi-armed bandits: optimal rate with collision information, sublinear without. In Proceedings of the 33rd Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 125, p. 961–987. Note: https://proceedings.mlr.press/v125/bubeck20c.html Cited by: §1.1, §1.1, §2, §3. [DUR64] R. Durstenfeld (1964) Algorithm 235: random permutation. Communications of the ACM 7 (7), p. 420. Cited by: §4. [HLP52] G. H. Hardy, J. E. Littlewood, and G. Pólya (1952) Inequalities. 2 edition, Cambridge University Press. Cited by: §5.1. [HOE63] W. Hoeffding (1963) Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58 (301), p. 13–30. Note: https://doi.org/10.1080/01621459.1963.10500830 Cited by: §8. [HRM+20] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon (2020) Time-uniform chernoff bounds via nonnegative supermartingales. Probability Surveys 17. Note: https://doi.org/10.1214/18-PS321 Cited by: §B.8. [HCT22] W. Huang, R. Combes, and C. Trinh (2022) Towards optimal algorithms for multi-player bandits without collision sensing information. In Proceedings of the 35th Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 178, p. 1990–2012. Note: https://proceedings.mlr.press/v178/huang22a.html Cited by: §2. [LZ10] K. Liu and Q. Zhao (2010) Distributed learning in multi-armed bandit with multiple players. IEEE Transactions on Signal Processing 58 (11), p. 5667–5681. Note: https://doi.org/10.1109/TSP.2010.2062509 Cited by: §2. [LM22] G. Lugosi and A. Mehrabian (2022) Multiplayer bandits without observing collision information. Mathematics of Operations Research 47 (2), p. 1247–1265. Note: https://doi.org/10.1287/moor.2021.1168 Cited by: §2. [RSS16] J. Rosenski, O. Shamir, and L. Szlak (2016) Multi-player bandits—a musical chairs approach. In Proceedings of the 33rd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 48, p. 155–163. Note: https://proceedings.mlr.press/v48/rosenski16.html Cited by: §2. [S21] C. Shi and C. Shen (2021) On no-sensing adversarial multi-player multi-armed bandits with collision communications. IEEE Journal on Selected Areas in Information Theory 2 (2), p. 515–533. Note: https://doi.org/10.1109/JSAIT.2021.3076027 Cited by: §2. [SXS+20] C. Shi, W. Xiong, C. Shen, and J. Yang (2020) Decentralized multi-player multi-armed bandits with no collision information. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 108, p. 1519–1528. Note: https://proceedings.mlr.press/v108/shi20a.html Cited by: §2.