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

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 $\delta$-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.