acceptodds
Under review as a conference paper at ICLR 2027

Best-Arm Identification in Factored Multi-Agent Bandits via Junction Trees

Abstract

Factored Multi-Agent Multi-Armed Bandits (MAMABs) model cooperative decision problems with exponentially large joint-action spaces and sparse local interactions. In fixed-confidence Best-Arm Identification (BAI), computing the information-optimal sampling allocation remains combinatorial. We derive a Junction-Tree (JT) representation of the characteristic-time program: locally consistent clique marginals characterize feasible sampling allocations, while a gap-augmented dynamic program handles competing joint actions without enumerating the combinatorial action space. The resulting complexity depends on the induced width of the graphical decomposition and a gap-state width measuring the number of cumulative reward gaps retained during elimination. For lattice-valued means, the resulting dynamic program is exact with pseudo-polynomial complexity; for arbitrary real-valued rewards, quantizing this gap dimension yields a certified approximation with a controllable accuracy-complexity trade-off. We further introduce JT Track-and-Stop, (JT-TaS) a -correct algorithm that asymptotically attains the instance-dependent lower bound. Experiments recover the exact optimum on enumerable instances and scale to instances with large joint action spaces.

Primary area:
reinforcement learning
Keywords:
Multi-Armed Bandits, Multi-Agent Bandits, Factored Bandits, Best-Arm Identification, Pure Exploration

Reviews

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

The paper studies fixed-confidence best-arm identification when a joint action's reward is a sum of local factors and each factor reward is observed separately. It starts from the known characteristic-time optimization and represents feasible sampling allocations through junction-tree marginals. A second dynamic program keeps cumulative reward gaps, allowing the optimization to retain each competitor's own gap. This gives an exact conic formulation whose size depends on graph width and gap-state width, together with a quantized approximation for real-valued means. JT Track-and-Stop uses these allocations and a conservative stopping statistic to attain the asymptotic sample-complexity lower bound. Experiments check the optimization against exhaustive solutions and compare sampling efficiency and target-solver runtime on synthetic instances.

Critical strengths
  1. The paper addresses the computational obstacle in the known lower bound. Junction-tree consistency handles feasible allocations, but the more interesting step is the signed gap-state recursion: ordinary max-sum cannot optimize the ratio involving a competitor's squared gap. Theorem 5 turns this recursion into an explicit conic program while allowing correlated sampling allocations. This improves on the restriction used by Vannella et al. [1]. The comparisons with exhaustive optimization across 70 instances in Appendix F.2 help verify that the formulation was implemented correctly.

  2. Quantization is carried through to the stopping rule, rather than used only to produce sampling targets. Proposition 6 controls the offline approximation error; the online grid can shrink without knowing the true minimum gap; and Equation (3) accounts for rounding before declaring a winner. These details matter for the claim of δ\delta-correct, asymptotically optimal identification.

[1] Filippo Vannella, Alexandre Proutiere, and Jaeseong Jeong. Best Arm Identification in Multi-Agent Multi-Armed Bandits. International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research 202:34875–34907, 2023.

Critical weaknesses
  1. The experimental stopping rule is insufficiently documented. Section 7 says the methods share a stopping calibration, but does not identify the implemented threshold, grid constant, or solver tolerances. Equation (63) specifies a theoretical boundary; it is unclear whether that boundary produced Figure 2. Appendix F promises calibration, confidence-level, and quantization results, but the supplied PDF ends after F.2 without them. Since the reported advantage is measured in stopping times, empirical error rates and the actual stopping rule are essential to interpreting the comparison.

  2. The large-instance result demonstrates one allocation solve, rather than the complete identification procedure. The 48-agent binary chain is impressive as an optimization example, but the main online comparisons use five agents and the additional online examples reach six or seven. Figure 2(b) reports target-solver time, while the online figures report samples. There is no corresponding comparison of total time spent constructing targets, solving them, and checking stopping. The paper acknowledges that gap-state width can be large; I therefore see strong evidence for the representation, with less evidence for its practical advantage in large online problems.

Questions for authors
  1. Experimental clarification: Which stopping threshold, quantization constant, and numerical tolerances produced Figure 2? Was Equation (63) used? What error rates were observed, and how were runs that reached a time or sample cap handled?

  2. Implementation clarification: Does Figure 2(b) include construction of gap supports and the conic program? Are total online runtimes available for the same instances used in the sample comparisons? Please also clarify whether the experimental sections announced in Appendix F were omitted from this version.

1 comment

Thank you for the thorough and positive review. We address your experimental and implementation questions below.

Q1 - Experimental clarification. We agree that some of the experimental details were not sufficiently documented in the original submission. We have now clarified the stopping rule, quantization schedule, numerical settings, and empirical error rates. In particular, our experiments use the practical stopping threshold β(t,δ)=log⁡[(1+log⁡(max⁡2,t))/δ]\beta(t,\delta)=\log[(1+\log(\max{2,t}))/\delta], a well-established choice in BAI experiments (see Kaufmann and Koolen, 2021, Sec. 5.1; Wang et al., 2021, Sec. 5.2). We use the same threshold and exact empirical GLR stopping test across all methods to ensure a fair comparison of their sampling efficiency. Regarding empirical correctness, all 1,020 recorded runs underlying Fig. 2(c–e) stopped correctly without reaching their sample caps. We further conducted 1,200 additional calibration trials across four gap and confidence settings, observing zero errors and zero capped runs. These results, together with the corresponding confidence bounds and complete experimental settings, are reported in App. F.

Q2 - Implementation and runtime clarification. We agree that the computational scope of the original experiments deserved a clearer explanation. The exact SOCP formulation of Theorem 5 provides a convex characterization of the characteristic-time problem and allows us to explicitly quantify its variables and constraints. For numerical efficiency, our experiments instead use an LP-based implementation. We have clarified this distinction and documented the numerical settings in Section 6 and Appendix F. The revised manuscript additionally reports online runtimes for the original sample-complexity comparisons and the new large-scale experiments discussed in our response to Reviewer qD7v (Q1). Finally, we thank the reviewer for identifying the incomplete Appendix F. We have restored and updated the missing experimental sections, including numerical validation, sensitivity analyses, and stopping-rule calibration.

Reviewer_qD7vOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies fixed-confidence best-arm identification in factored multi-agent multi-armed bandits, where the global reward splits over local factors and the joint-action space grows exponentially with the number of agents. Its core idea is to rewrite the characteristic-time program behind the fixed-confidence lower bound as an exact convex program on a junction tree: locally consistent bag marginals describe the feasible sampling allocations without a mean-field restriction, and a gap-augmented dynamic program evaluates all competing joint actions without enumerating them. The resulting cost is driven by the induced width of the decomposition and a new gap-state width; lattice-valued means give an exact pseudo-polynomial computation, while arbitrary real-valued means are handled by quantization with a certified approximation. The paper also proposes JT-TaS, a δ\delta-correct algorithm that asymptotically attains the lower bound, and validates both the reformulation and the algorithm experimentally.

Critical strengths
  1. Identifying the induced width and the gap-state width as the quantities controlling the characteristic-time program is a clean and genuinely useful contribution. Representing feasible allocations by locally consistent bag marginals is exact rather than a relaxation, and the gap-augmented message passing finds the worst competitor without ever touching the exponential joint-action space; this is more principled than generic oracle-based combinatorial solvers, which offer no analogous structure-dependent guarantee.

  2. JT-TaS is δ\delta-correct and asymptotically attains the instance-dependent lower bound, with nontrivial pieces supported by thorough appendix proofs. The experiments back the two main claims: the reformulation reproduces the exhaustive characteristic time essentially to numerical precision across several graph families, and preserving action-dependent gaps yields clear statistical savings over the mean-field and common-gap alternatives.

Critical weaknesses
  1. The headline claim is scaling to exponentially large joint-action spaces, but JT-TaS is only run on small, enumerable instances with a handful of agents and a couple of actions per agent. The single large instance (a width-one chain whose action space is astronomically large) exercises only the offline characteristic-time solver, so the actual behavior of the full learning procedure, including target-solve times and the growth in attainable gap states as treewidth or reward ranges increase, remains unverified. This materially weakens the strongest selling point, and end-to-end results on non-enumerable instances would change my assessment.

  2. Even at bounded treewidth the gap-state width can be exponential in the number of agents, as the paper's own example shows, and for arbitrary real-valued means exact computation is only reachable through quantization whose certified resolution scales with the reward range over the minimum gap. The authors are honest about this, but the abstract and introduction still emphasize scaling; a clearer statement that the favorable regime is low treewidth together with small gap-state width or lattice-structured means, and that worst cases are no better than generic combinatorial approaches, would set more accurate expectations.

Questions for authors
  1. Can you report end-to-end JT-TaS results on instances whose joint-action space cannot be enumerated (for example, more agents with treewidth two or three), including stopping times, numbers of retained gap states, and target-solve times? This would directly validate the scalability claim.

  2. How sensitive are the finite-sample results to the quantization constant and to the chosen update and check schedules? It would help to know how much of the practical performance depends on these knobs, since the coarse early grids force target ties.

  3. Is there a structural route to a tighter bound on the gap-state width, for instance under bounded reward-range-to-gap ratios, that would make the exact method usable beyond lattice-valued instances? (Future work)

2 comments

Thank you for the thoughtful and detailed comments. We address your questions below.

Q1 - End-to-end validation beyond enumerable joint actions. We agree that an offline target solve alone does not establish online scalability. We have therefore added complete JT-TaS identification experiments on 32- and 48-agent binary ladders (width 2) and 33- and 48-agent three-row grids (width 3), with up to 2482^{48} joint actions. All target updates, action sampling, and stopping checks are performed without enumerating global actions. All 80 runs across the four instances stopped correctly without reaching their sample caps. The experiments also demonstrate practical computational feasibility, with mean online runtimes between 6.13 and 24.18 seconds. Fig. 3 reports stopping times, retained gap states, and the decomposition of computational costs, with further details in Appendix F.

We also clarify the numerical implementation used for online learning. Rather than repeatedly solving the exact SOCP formulation of Theorem 5, we employ a persistent HiGHS LP approximation with signed-gap constraint generation. To assess its accuracy, we evaluated the resulting allocations against an independently computed, higher-accuracy action-enumerating reference on 153 instances across seven graph families. Under the online solver settings, the mean and maximum relative objective excess were only 0.213% and 0.482%, respectively, across 135 instances; the remaining 18 deliberately coarser tests reached at most 1.862%. An additional nonlinear comparison corroborates the numerical reference. These results support the accuracy of the practical implementation on the tested instances. The full validation is presented in Fig. 7 and Appendix F.

Q2 - Grid resolution and update/check schedules. We agree that these parameters can significantly affect the finite-sample performance of JT-TaS. We have therefore added ablations on the heterogeneous N=5N=5, K=4K=4 chain at minimum gaps Δmin⁡=0.35\Delta_{\min}=0.35 and 0.100.10, using 20 paired trials per setting. The results reveal a clear statistical–computational trade-off: coarser quantization reduces the number of retained gap states but can substantially increase stopping times, particularly on small-gap instances. More frequent target updates reduce sample cost by 29%, at the expense of a 4.8-fold increase in runtime, while less frequent stopping checks reduce runtime by approximately 40% with only a 3.1% increase in samples. We also investigate logarithmic-grid refinement and distinguish empirical-gap-guard rejections from quantized-best ties. Fig. 4 presents the main sensitivity results, with the additional logarithmic-refinement experiments and implementation details reported in Appendix F.

Q3 - Structural gap-state bounds. Low graphical width alone is not sufficient for small exact gap-state width. Even independent binary unary factors with local losses 1+2−i1+2^{-i} have 2N2^N distinct subset-sum gaps although their local range-to-minimum-gap ratios are bounded. We give this example in Appendix D.6. We also show a sufficient condition beyond a common lattice. If local signed-gap increments lie in a fixed dictionary {0,g1,…,gd}\lbrace{0,g_1,\ldots,g_d\rbrace}, every partial gap has one of at most (ρ+dd)\binom{\rho+d}{d} possible values. The bound is polynomial in the number ρ\rho of local factors for fixed dd, including incommensurate real dictionary elements. This identifies arithmetic diversity, alongside induced width, as a condition for exact tractability. Identifying broader structural conditions beyond fixed increment dictionaries remains an important future direction, and is explicitely included in as a future direction in the conclusions.

The reviewer thanks the authors for the responses. The reviewer will keep their positive evaluation.

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

The paper develops a junction-tree formulation of optimal exploration in factored multi-agent bandits and combines it with quantization and Track-and-Stop to obtain a δ-correct, asymptotically optimal algorithm.

Critical strengths
  1. Addresses a concrete computational bottleneck in statistically optimal exploration. Gives an explicit formulation controlled by graphical width and gap-state width.
  2. Validates the formulation against exhaustive optimization and demonstrates sample-efficiency gains over competitive baselines.
Critical weaknesses
  1. Theoretical novelty is limited. Junction-tree consistency and gap-augmented inference build on established techniques [1,2], while the lower bound and asymptotic analysis largely follow existing BAI results [3,4]. The main contribution is their computational integration, whose advance over a direct combination of existing methods could be clearer.
  2. Experimental validation is incomplete in two respects: the finite-sample impact of slow quantization refinement on small-gap instances is insufficiently evaluated, and large-scale tests mainly assess the allocation solver rather than the complete online algorithm’s runtime and scalability.[1] Wainwright and Jordan. Graphical Models, Exponential Families, and Variational Inference, 2008.

[2] Bauer, Nakajima, and Müller. Polynomial-Time Constrained Message Passing for Exact MAP Inference on Discrete Models with Global Dependencies, Mathematics, 2023.

[3] Vannella et al. Best Arm Identification in Multi-Agent Multi-Armed Bandits, ICML 2023.

[4] Garivier and Kaufmann. Optimal Best Arm Identification with Fixed Confidence, COLT 2016.

Questions for authors

What computational capability does the proposed formulation provide beyond applying existing constrained message passing within an established combinatorial Track-and-Stop framework?

1 comment

Thank you for the careful review. We address your questions on novelty and the experimental evaluation below.

Theoretical novelty. We agree that junction-tree consistency, constrained inference and Track-and-Stop are established ingredients, as acknowledged in the paper. The closest work in factored MAMABs, Vannella et al. (ICML 2023), derives the optimal allocation but resorts to a mean-field approximation to avoid its combinatorial computation.

Our contribution is the exact structured optimization of the full characteristic time, without that mean-field restriction. This problem combines two exponentially large objects: a feasible correlated sampling distribution over joint actions and a family of competitors with action-dependent gaps. In Theorem 5, junction-tree bag marginals are decision variables describing feasible allocations. A signed-gap recursion retains competitor-specific gaps in the information objective. The resulting conic formulation jointly optimizes both parts and is equivalent to the original characteristic-time problem, with complexity expressed through graphical and gap-state width. Applying constrained MAP inference for a fixed allocation does not by itself supply this optimization.

As discussed in the Introduction and Related Work (including Wainwright and Jordan, 2008; Bauer et al., 2023; and Vannella et al., 2023) and established by Theorem 5, it is the coupled allocation-competitor optimization, not message passing alone, that constitutes our computational contribution.

Experimental validation. We agree that the original experiments did not fully demonstrate the end-to-end computational benefit. The revised experiments now report complete online JT-TaS on four non-enumerable width-2/3 instances up to 2482^{48} actions, together with finite-sample quantization and scheduling ablations. Fig. 3 measures stopping time, retained gap states and the cost of target optimization and stopping checks. Fig. 4 isolates the small-gap cost of coarse quantization and the trade-off introduced by update and stopping-check frequency. The appendix reports the numerical target validation and detailed experimental protocol. These experiments support the computational claims on the instances tested.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.