{"id":"78c2a304-a252-453e-a4c4-d146f568a043","arxiv_id":"2501.17882","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"A decentralized policy for heterogeneous multiplayer bandits is claimed to achieve O(log^{1+δ}T + W) regret under adversarial zero-reward attacks using one-bit communication.","lead":"This paper designs a decentralized learning rule for several players sharing slot machines, where an adversary can make any machine pay zero and players cannot tell an attack from a collision. The proposed policy is claimed to achieve regret that grows logarithmically with time plus the number of attack periods, using only one-bit communication.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Matching-phase analysis treats the joint state process as a homogeneous regular perturbed Markov chain, but the adversarial vector w_t is only constrained pointwise and may vary arbitrarily; P^ε is time-dependent, so Lemma 1 and Theorem 1 are not derived.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing flaw: the matching-phase proof requires a fixed homogeneous Markov chain, but the attack process is arbitrary time-varying. I read the full proof in Appendix E and confirm that Lemma 4 asserts regularity of a perturbed Markov process without ever specifying the distribution of w_t, and Lemma 9 invokes the Markov-chain Chernoff bound as if a stationary distribution and mixing time exist. The system model in Section II gives only a pointwise positivity condition on P{w_t,m=0}, which does not imply stationarity or even a well-defined averaging over attacks. Therefore the probability bound on F^ℓ, and hence the exploitation-phase regret bound, is not derived. I agree with REJECT rather than CONDITIONAL: the issue is not a missing constant or a tightened tail bound but the core mechanism by which the algorithm is claimed to identify the optimal action profile under adversarial attacks. The paper may be salvageable by adding an explicit i.i.d. or stationary assumption on w_t and reworking Lemma 9, but Theorem 1 as stated is not proven.","tokens_in":20729,"tokens_out":5256,"duration_ms":67677,"concrete_test":"Take a minimal instance with K=M=2 and mean rewards such that the optimal profile is (arm 1, arm 2). Run the matching phase of Algorithm 2 under a deterministic alternating attack schedule w_t = (1,0) on odd t and (0,1) on even t, which satisfies P{w_t,m=0}>0 pointwise. Compute the exact time-inhomogeneous transition probabilities and check whether the quantity μ in equation (52) can be defined as a single stationary probability independent of t. Then simulate the empirical frequency with which the joint state equals the optimal content state over the matching phase for small ε; if this frequency oscillates with the attack phase or fails to exceed 1/2 uniformly, the stochastic-potential argument and Lemma 1 collapse, and the regret bound of Theorem 1 is not supported as stated.","verdict_should_be":"REJECT","load_bearing_attack":"The load-bearing step is the derivation of Lemma 1 / Lemma 9 in Appendix E, which supplies the event F^ℓ used to bound exploitation regret in the proof of Theorem 1. The matching-phase process is analyzed as a regular perturbed Markov chain with a fixed transition matrix P^ε (Appendix C, Lemma 4), and Lemma 9 applies the Chernoff–Hoeffding bound for Markov chains of Chung et al., which requires a unique stationary distribution and a fixed mixing time. But in the stated model of Section II, the adversarial vector w_t is only constrained by P{w_t,m=0}>0 at each time; no i.i.d., stationary, or ergodic assumption on w_t is made. The actual transition probabilities in Algorithm 2 depend on w_t through the utility in equation (13): a discontent or exploring player becomes content with probability ε^{1-u_k(a,w_t)}, so P^ε changes from time step to time step. Consequently there is no single stationary distribution μ, no fixed mixing time T, and no time-independent stochastic potential. Equations (50)-(62) therefore do not follow, Lemma 1 is unproved, and the exploitation-phase regret bound R3 in Section IV and Appendix B is unsupported. This is not a minor technicality: the claimed O(log^{1+δ} T + W) regret bound rests directly on this matching guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a decentralized multi-player multi-armed bandit with heterogeneous arm reward distributions, zero rewards on collisions, and adversarial attacks that mimic collisions. Players use a common epoch-based policy with exploration, a matching phase based on a perturbed Markov chain, and exploitation, communicating with one bit during the matching phase. The main claim (Theorem 1) is an expected regret bound of O(log^{1+δ} T + W), where W is the total number of time units with an attack on at least one arm. The proof decomposes regret into exploration, matching, and exploitation phases, and relies on a matching-phase lemma (Lemma 1 / Lemma 9) that bounds the probability of not selecting the optimal action profile by an exponentially small quantity.","tokens_in":20971,"tokens_out":7225,"duration_ms":83235,"significance":"If the main result were fully established, it would be a meaningful advance: a decentralized, heterogeneous multi-player bandit policy that uses only one-bit communication and is provably robust to adversarial attacks, with regret logarithmic in the horizon plus an additive term linear in the total attack time. The paper builds on established machinery, notably the payoff-based learning framework of Marden, Young, and Pao [18], Young's theory of regular perturbed Markov chains [25], and the Chernoff-Hoeffding bounds for Markov chains of Chung et al. [11]. However, the central matching-phase analysis currently rests on an unproven and, under the stated model, generally false assumption that the players' joint state process is a time-homogeneous regular perturbed Markov chain. Because the attack vector w_t is allowed to vary arbitrarily subject only to a pointwise positive probability of no attack, the transition probabilities depend on time, so the stationary-distribution and mixing-time arguments used in Lemma 9 do not apply. This gap is load-bearing for Theorem 1, and I do not see a local repair within the current model and proof structure.","major_comments":[{"comment":"The matching-phase analysis treats the joint state process as a homogeneous regular perturbed Markov chain with a fixed transition matrix P^ε, but under the model in Section II the transition probabilities depend on the realized attack vector w_t. In Algorithm 2, a discontent or exploring player becomes content with probability ε^{1−u_k(a,w_t)}, and u_k is defined through Eq. (13) using the attack-dependent reward. The paper only assumes P{w_t,m=0}>0 for each m and t, with no stationarity, i.i.d., or ergodic condition on w_t. Consequently there is no fixed P^ε, no unique stationary distribution μ, and no fixed mixing time T to which [11, Theorem 3] can be applied. Equations (50)–(62) in Appendix E therefore do not follow as written, Lemma 1 / Lemma 9 is unproved, and the exploitation-phase regret bound R3 in Section IV and Appendix B is unsupported.","section":"Appendix E, Lemma 4 and Lemma 9"},{"comment":"The sample-count identity used in the proof of Lemma 2 is not justified by Algorithm 3 as written. Lemma 2 states that the number of reward samples for arm m obtained after the exploration phase of epoch i is T0 ∑_{j=1}^i j^δ, implying that estimates are accumulated across epochs. Algorithm 3, however, only describes collecting T0 i^δ non-zero observations in epoch i and updating the estimated mean with the average of the observations from that epoch; no cumulative storage or averaging over previous epochs is stated. If cumulative averaging is intended, this must be made explicit in the algorithm and accounted for in the update rule. If not, the bound in Eq. (14), and hence the derived bound P(E^ℓ) ≤ 2KM e^{−ℓ} used in Eq. (24) of Appendix B, does not follow from the stated procedure.","section":"Appendix A, Lemma 2 and Algorithm 3"}],"minor_comments":[{"comment":"The phrase 'bounded away from zero, i.e., P{w_t,m=0} > 0' conflates a uniform lower bound with pointwise positivity; if a uniform lower bound is needed for the probabilistic analysis, it should be stated as inf_t P{w_t,m=0} ≥ η > 0.","section":"Section II"},{"comment":"The paper assumes K < M in the model, but the experiments in Section VI set K = M = 3; either the assumption should be K ≤ M or the experimental configuration should be justified separately.","section":"Section II and Section VI"},{"comment":"The experiments set δ = 0, while Theorem 1 requires 0 < δ < 1; the exposition should clarify whether the experiments are intended only as illustrations outside the theorem's parameter regime.","section":"Section VI"},{"comment":"In the definition of event F^ℓ, the phrase 'for all n ∈ [N]' uses an undefined N; it should presumably be n ∈ [M] or be removed.","section":"Appendix B"},{"comment":"There are several typographical errors, including 'are are' in Section III, 'stoachastically' in Appendix E, and 'at lease one player' in the proof of Lemma 6; these should be corrected in revision.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper goes after a real gap—heterogeneous multi-player bandits under adversarial collision-style attacks, with only one-bit communication. The algorithm is a plausible adaptation of Marden-Young-Pao with a mood-sync step, and the regret claim O(log^{1+δ} T + W) is the right kind of target. The experiments, though limited (K=M=3, δ=0), are consistent with the claim. But the main theorem is not proven as stated.\n\nThe matching-phase analysis models the joint state as a homogeneous regular perturbed Markov chain with a fixed P^ε, and Lemma 9 invokes Chung et al.'s Chernoff–Hoeffding for Markov chains with a unique stationary distribution and fixed mixing time. Under the stated adversary, w_t is only constrained by P{w_t,m=0}>0 at each t; it can vary arbitrarily, and the transition probabilities in Algorithm 2 depend on w_t through the utility (equation (13)). So there is no single P^ε, no stationary distribution μ, no fixed mixing time, and the stochastic potential argument in Appendix E does not apply. Lemma 1 and the exploitation-phase regret bound R3 are unsupported. This is not a footnote; the headline bound stands on that lemma.\n\nA second, smaller issue: Section II says P{w_t,m=0} is 'bounded away from zero' but then defines it as merely >0; without a uniform lower bound, the exploration phase duration is not controlled by T0ℓ^δ + W^ℓ_exp as claimed, and the bound could degrade. That one is fixable by stating a uniform lower bound or by folding the expected waiting time into W.\n\nThe paper does several things well. The one-bit mood synchronization is a sensible workaround for the interdependence violation caused by the altered state update, and the authors are upfront about why [18] cannot be applied directly. The new setting is meaningfully different from [17] (homogeneous) and [6],[7],[16] (no attacks). The self-citations are modest.\n\nIf the authors can either prove the matching guarantee for time-varying attacks or explicitly restrict the adversary to a stationary/i.i.d. process, the paper would be a solid contribution. As it stands, the central argument has a load-bearing hole. I would send it to peer review—the setting and approach deserve referee time—but I would not cite it until the matching-phase proof is repaired.","headline":"Main theorem rests on treating time-varying attacks as a fixed Markov chain; the setting is new and the algorithm plausible, but the proof has a load-bearing gap.","tokens_in":21561,"tokens_out":3158,"would_cite":false,"duration_ms":34276,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","91A26","60J20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes a decentralized multi-player bandit policy that, using only one-bit communication rounds, keeps expected regret at order logarithm of the horizon plus total attack time.","keywords":["multi-player multi-armed bandits","adversarial attacks","heterogeneous reward distributions","decentralized learning","one-bit communication","regret bounds","stochastically stable states","collision feedback"],"falsifier":"Run the proposed policy with $K=M=3$ under a deliberately non-stationary attack pattern, such as attacks hitting arm 1 only during the first half of every matching phase and never during the second half. If the players' content-state frequencies fail to concentrate on the optimal assignment as the matching phases grow, the fixed transition-matrix assumption behind the matching-phase guarantee is refuted; if they still concentrate, the assumption is stronger than the algorithm actually needs.","tokens_in":20452,"feed_emoji":"🛡️","tokens_out":11715,"duration_ms":106228,"temperature":0.7,"pith_summary":"Multi-player bandit problems ask how users sharing a set of arms should learn good arms when collisions destroy rewards. This paper studies the harder case in which reward distributions differ among players and an adversary can zero out any attacked arm, making an attack indistinguishable from a collision. It claims that one shared policy, with no central coordinator and only one-bit messages exchanged during $O(\\log T)$ time steps, keeps expected regret at $O(\\log^{1+\\delta}T + W)$, where $W$ counts the total time at least one arm was under attack. The horizon dependence is only a $\\delta$-power above the standard logarithmic lower bound, so the cost of adversarial attacks is isolated as an additive term. If correct, this would mean uncoordinated systems such as dynamic spectrum access can tolerate jamming without heavy communication or knowledge of the attacker's strategy.","feed_headline":"One-bit talk beats bandit attackers to near-log regret","feed_subtitle":"Decentralized players lose only a logarithmic amount, plus the total time an arm is attacked.","key_machinery":"The load-bearing object is the matching-phase Markov chain over joint player states that include a baseline arm, a baseline utility, and a mood of content or discontent, analyzed through the theory of regular perturbed Markov chains and stochastic potential. The paper's modification is a state update that keeps a content player content whenever they play their baseline arm, together with a one-bit synchronization round in which each player learns whether all players are content; together these restore the property of interdependence that the underlying payoff-based learning rule needs. Stochastic potential then selects the joint state whose baseline actions maximize the sum of estimated utilities under no attack, and an exponential concentration inequality for Markov chains converts that selection into a high-probability guarantee for the exploitation phase.","core_discovery":"Under zero-reward collisions, heterogeneous player reward distributions, and attacks that zero out any attacked arm, the paper claims that the optimal assignment of players to arms can still be identified and exploited with high probability. The proposed epoch-based policy runs an exploration phase that discards attacked reward observations, a matching phase that adapts a payoff-based distributed learning rule by forcing content players who play their baseline arm to remain content, and a one-bit mood-synchronization step that prevents a mixture of content and discontent players from being an absorbing configuration. The matching phase is analyzed as a regular perturbed Markov chain, whose stochastically stable state is the utility-maximizing action profile under no attack; exponential concentration bounds then show the exploitation phase plays that profile except with probability exponentially small in the epoch index. Summing the three phases over $O(\\log T)$ epochs yields $R(T)=O(\\log^{1+\\delta}T+W)$.","pith_inferences":["A natural test is an adaptive adversary that chooses which arm to attack based on the players' past actions; the algorithm itself uses no attack statistics, but the proof's time-homogeneity assumption would need an explicit handle for such a model.","The one-bit mood synchronization could be replaced by a scheme that forces collisions as communication, which might transfer this argument to fully communication-free settings at the price of additional collision regret.","If attacks are budget-constrained rather than arbitrary, the additive $W$ term suggests a clean trade-off curve: regret is logarithmic in the horizon plus the adversary's total budget, which could support a minimax comparison.","The unique-optimal-assignment assumption could likely be relaxed to a tie-breaking rule; the stochastic-potential framework would then need to show that the protocol selects one of the optimal profiles rather than cycling among them."],"forward_implications":["Uncoordinated spectrum-access users can tolerate an adversary that zeros out any subset of arms at any time, losing only the time actually attacked plus a near-logarithmic term.","The total communication cost is only $O(\\log^{1+\\delta} T)$ one-bit messages, so robustness does not require a dedicated control channel.","Players never need to distinguish an attack from a collision; the policy treats both as zero rewards and still converges to the optimal assignment.","In attack-free periods, when $W=0$, the guarantee reduces to $O(\\log^{1+\\delta} T)$, recovering the near-logarithmic behavior of no-adversary heterogeneous multi-player bandit baselines.","The algorithm does not require knowledge of the gap between the best and second-best assignments, so it is parameter-light in the problem instance."],"supporting_citations":[{"why":"Supplies the payoff-based distributed learning dynamics that the matching phase adapts; its interdependence condition motivates the one-bit synchronization step.","marker":"[18]"},{"why":"Provides the regular perturbed Markov chain and stochastic potential framework used to identify the stochastically stable joint state.","marker":"[25]"},{"why":"Establishes the zero-reward-on-collision decentralized multi-player bandit baseline whose matching-phase analysis this paper extends to adversarial attacks.","marker":"[6]"},{"why":"Provides the heterogeneous multi-player bandit analysis with non-zero rewards on collisions whose estimation and concentration arguments are adapted.","marker":"[16]"},{"why":"Supplies the exponential concentration inequality for Markov chains used to bound the probability that the exploitation phase misses the optimal action profile.","marker":"[11]"},{"why":"Offers the proof technique for stochastic potential under disturbances that is adapted to adversarial attacks.","marker":"[21]"},{"why":"Inspires the bit-valued communication step that synchronizes the players' moods in the matching phase.","marker":"[20]"},{"why":"Poses the adversarial-collision robustness problem in multi-player bandits that this paper strengthens to heterogeneous rewards.","marker":"[17]"},{"why":"Gives the logarithmic lower bound for stochastic bandits against which the near order-optimal regret claim is measured.","marker":"[14]"}],"fun_headline_variants":["One-bit gossip beats adversarial attacks in multi-player bandits","Distributed bandits fight attackers, stay near-optimal with a single bit","Adversary-proof bandit learning via sparse one-bit communication","Collision-aware bandits resist attacks with one-bit coordination"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The matching-phase convergence proof assumes that the sequence of adversarial attacks makes the players' joint state process a time-homogeneous Markov chain with a single fixed transition matrix; the stated model only guarantees that each arm has a positive chance of being unattacked at every step.","fun_headline_variants_meta":{"raw":{"variants":["One-bit gossip beats adversarial attacks in multi-player bandits","Distributed bandits fight attackers, stay near-optimal with a single bit","Adversary-proof bandit learning via sparse one-bit communication","Collision-aware bandits resist attacks with one-bit coordination"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000331,"raw_usage":{"total_tokens":1855,"prompt_tokens":969,"completion_tokens":886,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":585,"completion_tokens_details":{"reasoning_tokens":814}},"tokens_in":585,"tokens_out":886,"duration_ms":8154,"temperature":1.0,"reasoning_tokens":814,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:39:47.160867+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proposed policy with $K=M=3$ under a deliberately non-stationary attack pattern, such as attacks hitting arm 1 only during the first half of every matching phase and never during the second half. If the players' content-state frequencies fail to concentrate on the optimal assignment as the matching phases grow, the fixed transition-matrix assumption behind the matching-phase guarantee is refuted; if they still concentrate, the assumption is stronger than the algorithm actually needs.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the payoff-based distributed learning dynamics that the matching phase adapts; its interdependence condition motivates the one-bit synchronization step."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the regular perturbed Markov chain and stochastic potential framework used to identify the stochastically stable joint state."},{"cited_title":"Bistritz and A","cited_arxiv_id":null,"evidence_quote":"Establishes the zero-reward-on-collision decentralized multi-player bandit baseline whose matching-phase analysis this paper extends to adversarial attacks."},{"cited_title":"Magesh and V","cited_arxiv_id":null,"evidence_quote":"Provides the heterogeneous multi-player bandit analysis with non-zero rewards on collisions whose estimation and concentration arguments are adapted."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the exponential concentration inequality for Markov chains used to bound the probability that the exploitation phase misses the optimal action profile."},{"cited_title":"Ramesh, M","cited_arxiv_id":null,"evidence_quote":"Offers the proof technique for stochastic potential under disturbances that is adapted to adversarial attacks."},{"cited_title":"Menon and J","cited_arxiv_id":null,"evidence_quote":"Inspires the bit-valued communication step that synchronizes the players' moods in the matching phase."},{"cited_title":"Multi-Player Bandits Robust to Adversarial Collisions","cited_arxiv_id":"2211.07817","evidence_quote":"Poses the adversarial-collision robustness problem in multi-player bandits that this paper strengthens to heterogeneous rewards."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the logarithmic lower bound for stochastic bandits against which the near order-optimal regret claim is measured."}],"review_version":1}