acceptodds
Withdrawn from ICLR 2027

Coordination Has a Price: Social Evidence and Manufactured Tails in Many-Armed Bandits

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

When arms outnumber the horizon, most arms are cold, and a learner can find the good ones in two ways. It can explore broadly, which is why greedy selection works so well in this regime (Bayati et al., 2020), or it can borrow evidence from other participants: endorsements, ratings, co-transactions. An adversary who controls where some of the arms land can exploit both. We first show that breadth has a fixed price. If the learner's side information carries no information about who is adversarial, its expected fraud is at least , where is the number of distinct arms it tries after adversaries defect, the adversarial fraction and their failure rate. Coordination changes this, because coordinated adversaries leave structure. A flag-and-propagate rule that runs one CUSUM statistic per connected group of heavily interacting arms pays at most pulls per ring, independent of , and blocks honest arms with probability at most per starting point. In a standard many-armed environment with 300 arms and 30 seeds, it cuts fraud by 2.4 to 15.5 times for rings of 30 or more and does nothing against solo adversaries, and both bounds hold in every cell. In an environment where arms endorse each other, endorsements cut regret from 149 to 89, a visible ring more than doubles a naive endorsement learner's fraud, and capping positive and negative endorsement counts separately at median plus three MADs brings every self-promoting ring we tried to within 1.8 times the fraud of the same adversaries acting alone, with the regret gain intact. Adding a dense-subgraph detector pushes rings that hide their links below the solo level. Coordinated bad-mouthing of honest arms is contained to the solo baseline via public consensus-residual rater filtering (CRRF), while real fraud benchmarks delineate the domain boundary where uncoordinated review spam merges into mixed giant components governed by graph-blind lower bounds.

Primary area:
learning theory
Keywords:
many-armed bandits, adversarial bandits, social evidence, collusion rings, graph fraud detection, CUSUM, payment routing, robust online learning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_KhJEOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies fraud inspired by many-armed bandit setting, where adversarial arms can also manipulate endorsements. It gives a lower bound linking fraud to the number of distinct arms tried when side information cannot identify attackers. It also studies how interaction patterns can help detect groups of adversarial arms and tests several defenses against manipulated social evidence.

Critical strengths
  1. The paper studies an interesting\textit{interesting} problem: social evidence can help learners find good arms, but adversarial arms can also create misleading evidence.

  2. Theorem 1 and 2 offer a useful contrast between cases where side information reveals nothing about adversarial arms and cases where group structure supports detection.

Critical weaknesses

Weakness: The methods and experiments are hard to follow, making the main contributions difficult to assess.

The paper provides individual definitions and defensive rules, but readers must reconstruct how they fit together across several sections and the appendix. This makes it difficult to understand what each method does, which guarantees apply to it, and what the experiments establish. The following examples illustrate this broader problem.

Section 4 would benefit from end-to-end pseudocode showing how arm selection, rating updates, filtering, and blocking work together. Explicit ETS/ETS-sep sampling equations and a table of method configurations would also help. If graph components change online, the handling of their CUSUM statistics needs clarification.

Section 5.1 summarizes a large experimental suite, but provides no table or figure showing results by condition or the size of the differences between methods. Readers therefore cannot directly assess the claims of “least fraud” and “no loss in reward.”

Table 2 reports regret without attackers and fraud under attacks. These results show separate benefits, but do not show the reward cost of the defenses under attack. The paper should clarify whether “the regret gain intact” refers only to performance without attackers, or provide reward results under the same attack conditions.

The paper does not need to provide a single best algorithm or a joint regret–fraud bound. However, it should clearly explain what its cost analysis establishes, which design principles follow, and how the proposed methods and experiments support those principles.

Questions for authors
  1. Could you provide concise end-to-end pseudocode and explicit ETS/ETS-sep sampling equations, specifying the timing of rating updates, filtering, graph construction, and blocking?

  2. Section 4.1 states that a 30-member ring produces “30 times as many observations per round,” although Section 2 allows only one arm pull per round. Could you explain this statement?

  3. I find the motivation of studying collusion and defenses in many-armed bandits interesting. I would like to understand the choice to focus on fraud rather than also analyze regret. Were there particular technical difficulties in connecting the two? If so, could you explain the main obstacles?

Reviewer_g3GUOpenReview ↗
Rating
1
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates adversarial manipulation in many-armed bandits with social evidence. It establishes theoretical bounds on fraud under different information conditions and proposes graph-based detection and endorsement filtering mechanisms. Experiments across simulated environments demonstrate reductions in fraud while maintaining competitive regret.

Critical strengths
  1. The paper provides theoretical bounds characterizing the relationship between exploration, adversarial coordination, and fraud, offering useful insights into robust bandit learning.

  2. The experiments cover multiple adversarial strategies and bandit algorithms, demonstrating substantial fraud reduction while preserving the benefits of social evidence.

Critical weaknesses
  1. The theoretical guarantees rely on restrictive assumptions, particularly the purity of graph components. The paper's own experiments show that impure components can cause substantial false blocking of honest arms, while real fraud datasets contain predominantly mixed components. This significantly limits the practical applicability of the proposed guarantees.

  2. The experimental validation relies primarily on synthetic environments with predefined adversarial behaviors. Moreover, the robustness guarantee for Thompson sampling against stealthy coordination remains a conjecture. These limitations weaken the evidence for general effectiveness against realistic and adaptive adversaries.

Questions for authors
  1. How does the proposed method perform when adversarial and honest arms form mixed graph components? Can the authors provide additional analysis of false blocking and its impact on regret?

  2. How robust is the proposed method against adaptive adversaries that modify their endorsement patterns or failure rates in response to detection?

Reviewer_1cg2OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies adversarial learning in a many-armed bandit regime where the learner faces far more arms than it can meaningfully sample. The motivating setting is not just “many arms” in the abstract, but a marketplace or routing-like environment where most arms are cold: the learner’s own interaction history covers only a small fraction of the available options. As a result, performance depends either on exploiting the statistical tail of the arm prior (greedy or subsampled methods), or on using external side information such as ratings, endorsements, co-transactions, or interaction graphs. The paper’s central question is what happens when some arms are adversarial and can manipulate precisely this side information.

The first part of the paper formalizes a basic exposure cost. If the learner’s side information is uninformative about which arms are adversarial, then every newly tried arm after the adversaries switch to bad behavior has the base adversarial probability. Thus fraud scales with the learner’s post-switch breadth: E[Fraud]≥ρεE[D]\mathbb{E}[\mathrm{Fraud}] \ge \rho \varepsilon \mathbb{E}[D], where DD is the number of distinct arms tried after the switch. Intuitively, if the graph or side information carries no label signal, then no filtering rule can distinguish an unseen adversarial arm from an unseen honest arm before trying it. This captures the cost of breadth in the many-armed regime.

The positive direction is based on the opposite observation: coordinated adversaries may gain influence by fabricating social evidence, but coordination can also leave statistical structure. The authors assume that heavily interacting arms form connected components that are pure, i.e. each component is either all honest or all adversarial. Under this assumption, they propose a flag-and-propagate rule: run a CUSUM-style change detector at the component level, and once the component appears to have switched to high failure rates, block all arms in that component. The key intuition is that a ring provides many pooled observations, so the learner need not detect each adversarial arm separately. The resulting fraud bound is per adversarial component rather than per arm or per unit of exploration breadth.

The paper then turns to endorsement-style side information. Endorsements are valuable precisely because the learner cannot sample all arms itself: in benign settings, they help identify promising cold arms and reduce regret. But this also creates the main vulnerability: a colluding ring can manufacture endorsements and push its members into the apparent upper tail. The paper argues that naive total-count capping is insufficient, because fake positives can displace honest negatives within the cap. Its proposed fix is to cap positive and negative endorsement counts separately, preventing fabricated positives from washing out negative evidence. For rings that avoid repeated heavy pairwise interactions, the authors add dense-subgraph detection; for bad-mouthing attacks, they filter raters with anomalously high public negative out-degree.

The conceptual takeaway is a dichotomy. If adversaries do not leave usable structure, then side information is effectively graph-blind and the learner pays a breadth-dependent lower bound. If adversaries coordinate enough to manufacture useful social evidence, then that same coordination may create a detectable footprint, allowing the learner to charge fraud at the level of rings rather than individual arms. The experiments support this story in simulation: component-level detection reduces fraud for large rings, separate endorsement caps keep self-promotion near the solo-adversary baseline, dense-block detection catches stealthier self-promotion, and public rater filtering mitigates bad-mouthing.

The main limitation is that the strongest positive result relies on a clean structural assumption. In real review-spam graphs such as YelpChi and Amazon, the authors find that fraud nodes are mostly embedded in mixed components rather than isolated pure fraud components. This suggests the method is most applicable to domains where collusion creates relatively separable interaction rings, rather than to settings where honest and fraudulent activity are entangled around popular targets. Overall, the paper is best understood as formalizing the intuition that side information is necessary in many-armed settings but becomes an attack surface; coordination helps adversaries only insofar as it does not also reveal them.

Critical strengths
  • Clear and useful problem framing: The paper identifies an important tension in many-armed settings: side information is needed because most arms are cold, but that same side information can be manipulated by coordinated adversaries.

  • Clean conceptual dichotomy: The “breadth is taxed / coordination is caught” framing is intuitive and memorable: without informative structure, fraud scales with post-switch breadth; with clean coordinated structure, fraud can be charged at the ring/component level.

  • Simple lower bound with good interpretability: The lower bound E[Fraud]≥ρεE[D]\mathbb{E}[\mathrm{Fraud}] \ge \rho \varepsilon \mathbb{E}[D] is technically straightforward but effectively captures the unavoidable exposure cost of trying new arms when labels are uninformative.

  • Natural component-level detection insight: Pooling evidence at the level of colluding components rather than individual arms is well-motivated and leads to a clear per-ring fraud bound.

  • Practical endorsement-design lesson: The distinction between total endorsement capping and separate positive/negative capping is a useful, concrete insight; it explains why naive winsorization can fail and suggests a simple fix.

  • Coherent experimental story: The simulations are aligned with the paper’s main narrative and test several relevant attack styles, including visible rings, stealthier endorsement rings, and bad-mouthing.

  • Honest discussion of domain boundaries: The real-graph analysis on YelpChi/Amazon usefully shows where the pure-component assumption fails, helping clarify when the proposed structural defenses are likely or unlikely to apply.

  • Readable presentation: The paper is organized around a clear intuition rather than only technical results, making the contribution easy to understand and evaluate.

Critical weaknesses
  • Limited technical novelty: The main theoretical results are clean but largely use standard arguments: the lower bound is an exchangeability/counting argument, and the upper bound follows from standard CUSUM-style change detection once pure components are assumed.

  • Strong structural assumption: The main positive guarantee depends on heavy-edge components being pure, i.e. entirely honest or entirely adversarial. This assumption does much of the work and may be unrealistic in many real settings.

  • Real-graph evidence undercuts the assumption: The authors’ own analysis of YelpChi/Amazon shows that fraud nodes often lie in mixed giant components, suggesting the pure-component assumption fails in common review-spam graphs.

  • Primarily simulation-based validation: The core bandit results are demonstrated in synthetic environments. The simulations support the paper’s internal story, but they do not establish that the approach works in real deployed systems.

  • Algorithms are mostly natural combinations of known tools: FaP is essentially CUSUM run over graph components; FRAUDAR is an existing dense-subgraph detector; winsorization/capping and out-degree filtering are standard robustification ideas.

  • Limited adaptive-adversary analysis: The attacks are mostly scripted. The theory and experiments do not fully address adversaries that adapt to the detector, reduce failure rates when watched, spread endorsements more carefully, or evade negative-outdegree filters.

  • Unclear breadth-regret tradeoff: The lower bound shows fraud scales with breadth, but the paper does not prove that achieving low regret in this regime necessarily requires large post-switch breadth.

  • Domain applicability is narrow: The methods seem most relevant when collusion creates relatively isolated, detectable rings. They are less compelling for settings where fraud and honest behavior are structurally entangled.

  • Some claims feel stronger than the evidence: For example, empirical support for the Thompson-sampling “price of stealth” conjecture is suggestive but not a proof, and fixed-grid simulations cannot establish independence from horizon or ring size.

  • Incremental overall contribution: The paper’s strongest contribution is a clean formalization and synthesis, rather than a fundamentally new algorithm, theory, or empirical discovery.

Questions for authors
  1. How realistic is the pure-component assumption?
    The main positive guarantee relies on heavy-edge components being pure. Beyond the synthetic setup, can you provide evidence from a real mutual-collusion domain where this assumption approximately holds? The YelpChi/Amazon analysis suggests it fails badly for review-spam graphs.

  2. What happens under adaptive adversaries?
    The attacks appear largely scripted. How robust are FaP, separate capping, FRAUDAR, and CRRF to adversaries that adapt their endorsement volume, failure rate, or negative-rating behavior to stay below detection thresholds?

  3. Can you characterize the regret–breadth–fraud tradeoff?
    The lower bound shows fraud scales with post-switch breadth, but does not show when low regret requires large breadth. Can the paper give conditions under which good regret necessarily implies exposure to the breadth lower bound?

  4. How sensitive are the methods to threshold choices?
    Several components depend on thresholds such as heavy-edge cutoff HH, CUSUM threshold hh, median + 3 MAD caps, and FRAUDAR density ratios. How stable are the results under threshold misspecification or across environments?

  5. Can the endorsement defenses be evaded by spreading manipulation across raters or time?
    CRRF seems to rely on colluders having anomalously high negative out-degree. What happens if bad-mouthing is distributed across many colluders so each remains within the public envelope?

  6. What is genuinely new relative to change-detection bandits and graph-fraud detection?
    Since the algorithmic components are largely CUSUM over components, capping, and existing dense-subgraph detection, can the authors clarify precisely which technical or conceptual contribution goes beyond combining known tools in this setting?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.