acceptodds
Withdrawn from ICLR 2027

Two-Level Bandits for Collaborator Selection and Sustained Cooperation

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

Abstract

Agentic systems increasingly require one autonomous agent to choose another to work with: which tool-using agent to delegate a multi-turn task to, which client to admit to a federation, which service to contract with for a sustained workflow. Such collaborator selection problems have a two-level structure that is usually studied one level at a time. At the outer level an agent searches a set of uncertain candidates under an interaction budget or deadline (a secretary / best-arm-identification prob- lem); at the inner level, once a candidate is engaged, value is produced only if the two agents sustain cooperation in a repeated game with a defection temptation and noisy execution (an iterated Prisoner’s Dilemma). We formalize the joint problem as a two-level bandit in which the reward of each outer arm is itself the equilibrium payoff of an inner repeated game, give algorithms for it, and complete the associ- ated discounted commitment-stopping problem left open in prior work. We prove three results—an inner cooperation-sustainability threshold γ⋆ = (T −R)/(T −P ), a value-decomposition regret bound showing that ranking candidates by advertised compatibility alone is suboptimal by exactly the cooperation gap, and the optimality of a monotone reservation threshold for discounted commitment—and validate all of them with a reproducible simulation suite. Two-level best-arm identification recovers the truly best collaborator with probability 1.00 at confidence δ=0.05, whereas a compatibility-only selector is captured by a high-capability defector and suffers a persistent value regret of 1.60; critically, its probability of correct selection degrades to zero as its interaction budget grows, because more data only sharpens its estimate of the wrong quantity. Under a costly clock, the textbook 1/e rule captures only 2.2 of the 22.2 units achieved by the optimal reservation policy. Our framework yields concrete design guidance for agent marketplaces, delegation layers, and federated participant selection, and a clean bridge between optimal stopping, bandits, and the evolution of cooperation.

Primary area:
reinforcement learning
Keywords:
Agentic Systems, Multi-Agent Systems, Collaborator Selection, Multi-Armed Bandits, Two-Level Bandits, Best-Arm Identification, Optimal Stopping, Repeated Games, Iterated Prisoner’s Dilemma, Cooperation, Defection, Agent Delegation, Partner Selection, Agent Marketplaces, Federated Learning, Multi-Agent Reinforcement Learning, Discounted Rewards, Reservation Thresholds, Regret Bounds, Autonomous Agents, Agentic AI

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_rhK4OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies a setting where an agent learns which collaborator to select and then interacts with that collaborator over multiple rounds, with the value of the relationship depending on whether they can sustain cooperation.

Critical strengths

I could not identify any particular strengths in the paper in its current form.

Critical weaknesses
  1. The paper violates multiple formatting guidelines. It does not include the mandatory AI use statement and it is not even in ICLR 2027 formatting (it looks like NeurIPS formatting). Also, the abstract on OpenReview is almost completely different from the one in the PDF itself.

  2. I suspect that there’s a lot of AI involvement here without human review. The writing relies heavily on long dashes everywhere, the paper is full of inaccurate statements, vague and unusual phrasings and overly verbose text. It also sounds like the writing wasn’t done by someone familiar with the topic.

    • In the abstract, calling the inner interaction a bandit is misleading and inaccurate. A repeated game is not necessarily a bandit problem. Someone familiar with the topic would likely distinguish between the learning problem and the strategic interaction rather than immediately describe the whole thing as a two-level bandit.
    • In the introduction, "sequential commitment" is not a common term for this phenomenon. It could suggest a commitment game or sequential mechanism rather than exploration followed by a persistent relationship. Also, "candidates of uncertain quality" is somewhat generic. Is quality an exogenous type or does it depend on the incentives created by the relationship? Further, stating "must then sustain a cooperative relationship" assumes cooperation is possible. Whether cooperation can be sustained is exactly what should be investigated here.
    • The introduction is filled with insufficiently edited AI-generated text (“The prevailing engineering practice is to rank candidates by an advertised or statically measured compatibility score…”, “Two mature theories each capture one half of the problem”, “The coupling is the crux” and so on).
  3. I find the discussion rather generic and lacking the level of rigour and professionalism expected in a paper.

    • The connection to the secretary problem and bandits needs to be explained more accurately. The secretary problem and bandits are distinct frameworks, rather than one being a generalisation of the other. The secretary problem often involves sequentially evaluating candidates without being able to return to previously rejected ones, while bandit models allow repeated selection and learning about uncertain rewards. It is therefore misleading to describe bandits simply as generalisations of the secretary problem.
    • I find the references to the IPD and the folk theorem rather generic and somewhat superficial. Both are well-known textbook concepts and simply mentioning them does not give a deep engagement with the relevant literature. The discussion would benefit from a more relevant discussion of repeated games with partner selection, switching and endogenous incentives for cooperation. As it stands, the theoretical framing feels rather introductory and does not clearly establish how the proposed problem relates to existing research or what is genuinely new about it.
    • The discussion about prior work in Section 2 is thin, incomplete and not very deep. It also still does not properly define any of the problems discussed there. The authors assume that the reader is already familiar with bandits, the secretary problem, and stable matchings. Actually, Section 2 feels like another bunch of unrelated and textbook topics put together in a single section, while some of them have no real relevance to the paper. How are stable matchings relevant to this paper? Hint: they are not.
  4. Getting back to the poor writing, the related work also contains a rather odd statement: “Our primitives (secretary/BAI and IPD) are individually classical - so, to answer the natural reviewer question directly: yes, the building blocks are known and the contribution is not a new bandit algorithm or a new PD strategy”. Sadly, the paper is exactly that. It is a combination of several existing things without any technical novelty. The “results” and techniques are all well-known, and simply combined together.

  5. Section 5 says “Code, results (JSON), and figures accompany the paper”, but they are not accompanied with the paper. The authors also forgot to describe the entire experimental setup, which includes defining, e.g., AllC, AllD, TFT, Generous-TFT, Grim, Win-Stay-Lose-Shift (WSLS) and Random.

Questions for authors

None.

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

This paper proposes a novel bandit framework for cooperation in agentic systems, which is a general scenario in Agent AI. The problem, called the two-level bandit problem, consists of two agents: an outer agent selects among uncertain collaborators, while an inner repeated game determines the value of cooperation with the selected agent. The authors formalize this interaction, develop algorithms for joint collaborator selection, and characterize when cooperation can be sustained. They show that selecting agents based only on advertised capability or compatibility can systematically favor high-capability defectors, while accounting for cooperation dynamics identifies the true best collaborator. An optimal reservation policy for discounted commitment is derived and the framework is validated through simulation. The results connect bandit learning, optimal stopping, and cooperation, providing a framework for collaborator selection in agent marketplaces, delegation systems, and federated AI.

Critical strengths
  1. The problem setting is realistic and interesting. In machine learning, the cooperation of two models has unlimited possibilities. They may learn better or worse. Hence, it is a meaningful project.
  2. The definition of reward is novel, which combines the practical scores and the cooperation score between the two intelligent agents. There also exists a trade-off between immediate compatibility and sustained cooperation.
Critical weaknesses
  1. The novelty of the two-level bandit framework is not greatly explained. The main contribution of the paper is a composite reward oracle that combines a compatibility observation with the payoff obtained from an inner-game rollout. Under this assumption, it can be solved by general bandit algorithms such as UCB, round-robin-based algorithms. Hence, the author needs to clarify the fundamental differences between this modeling approach and the standard com- pound or structured reward BAI. Moreover, construct more arms to represent the cooperative relationship among agents would be a easier method to solve the problem.
  2. A concrete theorem and the corresponding proof is needed for a paper. This paper lacks some necessary performance indicators for bandit work, such as cumulative regret. I can not find any theoretical analysis about the regret bound, which implies that the proposed method is not useful in any general scenes.
Questions for authors
  1. There are some formatting issues in this paper. In particular, the “where” statements following the equations should be aligned with the left margin.
  2. For the symbol S in Section 3, it represents both the action set and the reward value, which is unsuitable.
  3. What mixing argument guarantees convergence to a uniform global representation when M(t) is not doubly stochastic?
Reviewer_PP31OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how an agent picks a collaborator from a pool of candidates of uncertain quality and then sustains cooperation with the chosen partner. It frames the problem as a two-level bandit: an outer best-arm-identification loop selects among candidate partners, and an inner discounted iterated Prisoner's Dilemma determines the value of engaging each candidate. A single pull runs a full relationship rollout and returns an unbiased sample of total value, the sum of compatibility and cooperation. The paper proves when cooperation survives, shows that compatibility-only selection incurs a cooperation gap, and completes a previously undefined optimal-stopping formulation of discounted commitment.

Critical strengths
  1. The reward-as-equilibrium framing is novel that neither field addresses. Bandit and secretary work treats each pull's reward as an exogenous draw, and repeated-game theory takes the pairing as given, so the interaction between the two is left unexamined. Making the outer arm's value the equilibrium payoff of an inner cooperation game gives a clean, motivating reformulation of collaborator selection.

  2. The paper turns a practical concern into a provable statement. It shows that ranking candidates by advertised compatibility alone surrenders a cooperation gap that can dominate the decision, and that more data does not help, because the searcher only grows more certain about the wrong arm. This is a testable message for systems that route on capability or reputation scores.

  3. The paper states plainly that the building blocks are classical, argues each claim with transparent reasoning, and validates every result with reproducible simulations, including a phase diagram whose cooperation onset matches the analytic threshold and replicator dynamics aligned with it.

Critical weaknesses
  1. The technical depth is modest. The cooperation threshold is a standard grim-trigger condition, and the value-decomposition bound follows almost directly from the additive form of total value. The paper contributes no new algorithm, no problem-dependent analysis, and no lower bounds, so the novelty rests on the modeling rather than on new mathematics.

  2. The estimation procedure sits awkwardly against the paper's own motivation. Each pull rolls out a full relationship from a cold start, so the model estimates the value of a fresh relationship rather than a sustained one, and identifying the best among a small pool already costs tens of thousands of interactions. The paper does not analyze this total cost, how the rollout horizon should be chosen, or when such spending is justified.

  3. The empirical case rests on constructed instances and simulation. The headline demonstration of compatibility-only failure is engineered by anti-aligning advertised compatibility with cooperative behavior, so the conclusion is largely encoded in the data rather than discovered. There is no real deployment data and little sensitivity analysis of choices such as rollout length and the scale linking compatibility to cooperation.

Questions for authors
  1. The sustainability threshold assumes a grim-trigger partner, while the agent is assumed to play Tit-for-Tat and the experiments use a broader strategy set. Please clarify how the threshold and the measured cooperation values depend on the strategies the two sides play.

  2. Placing compatibility and cooperation on a common per-round scale fixes an exchange rate between the two that is acknowledged as substantive but chosen arbitrarily. A principled justification or a sensitivity analysis of this normalization would strengthen the definition of total value.

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

Related papers

Discussion (0)

Sign in to comment.