ICMAPE: In-Context Multiagent Pure Exploration

Xinyi Hu; Alessio Russo; Aldo Pacchiano

cs.LGSep 27, 2026

ICMAPE: In-Context Multiagent Pure Exploration

Authors: Xinyi Hu, Alessio Russo, Aldo Pacchiano

Organizations: Boston University · Broad Institute of MIT and Harvard

Abstract

In some multi-agent systems, the quantity to be optimized is not an externally specified reward but the information acquired about unknown properties of the environment as done in active sequential hypothesis testing (ASHT) problems. However, the ASHT literature tends to focus on finite single-agent problems with well-specified models, while there is currently a gap for practical multi-agent methods that can perform active sequential testing. We fill this gap with ICMAPE, a Bayesian learning-based framework for decentralized multi-agent pure-exploration driven by inference objectives. ICMAPE converts the fixed-confidence identification objective into a reward derived from inference confidence, so that standard reinforcement learning machinery can be applied to decentralized pure exploration. It jointly learns a centralized neural inference network that estimates a posterior distribution over hypotheses from global trajectory data, and decentralized policies that select actions from local observation histories and learn when to stop collecting data once the target confidence is reached. On two synthetic benchmarks and a Maryland nitrate concentration monitoring task based on real-world data, ICMAPE-TD3 achieves target accuracy with fewer exploration steps.

Figures & tables

Figure 1 : Training dynamics in A3P5 and A5P3. Curves are averaged over three random seeds and smoothed with an exponential moving average parameter of $0.2$ .

Figure 2 : Bandit Capacity Accuracy and Average Stopping Step. “I” denotes ICMAPE. “C” denotes centralized baselines. In (a) A3P5, the TD3-EnvR bar represents TD3 trained to maximize the environmental reward Error bars indicate one standard deviation.

Variant	Inf. Reward	Learned Stop	Step Cost	Accuracy	Avg. Stop Time
Full ICMAPE-TD3	✓	✓	✓	0.91	13.5
Environment-reward TD3	✗	✓	✓	0.21	47.0
Fixed-threshold stopping	✓	✗	✓	0.70	37.3
No sampling cost	✓	✓	✗	0.90	50.0

Table 1 : Ablation study on ICMAPE-TD3 in A3P5.

Figure 3 : Signal Source Localization Accuracy and Average Stopping Step. The TS bar is the Thompson Sampling guiding exploration strategy. Error bars indicate one standard deviation.

Figure 4 : Nitrate Concentration Accuracy and Average Samples. Error bars indicate one standard deviation.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

\widehat{H}_{\tau}=\arg\max_{H\in\mathcal{H}}p_{\psi}(H\mid\mathcal{D}_{\tau}).

Appendix

Algorithm 2 ICMAPE Inference

Parameter	Value
$q_{i}$	$0.95$
$d_{\text{min}}$	10
$\lambda$	$0.3$
$\sigma$	$0.07$
$n$	$25$
$m$	$5$

Appendix

Table 2 : Environment parameters for signal source localization.

Figure 5 : Example of Agent 3’s signal field $Y^{(3)}$ . Red $\times$ : true source; blue $\times$ : distractor.

Panel of Figure 6 — Figure 6 : GP-estimated nitrate concentration fields across Maryland for three representative years. Each map is constructed from year-round average concentrations at monitoring sites for that year. Spatial patterns shift notably across years, illustrating the inter-year variability that motivates training on multiple years and evaluating generalization on held-out years.

Year	Raw Data Points	Avg. Var.	Avg. Sigma
2000	10,693	0.265	0.515
2001	10,146	0.287	0.536
2002	11,063	0.249	0.499
2003	11,542	0.264	0.514
2004	11,769	0.421	0.649
2005	10,326	0.238	0.488

Appendix

Table 3: Per-year data statistics for GP field generation. Avg. Var. denotes the mean GP posterior variance over valid Maryland grid cells in log-transformed concentration space, and Avg. Sigma is its square root.

Symbol / Parameter	Value	Description
$\mathcal{X}$	$n\times n$ grid	Discretized Maryland sensing domain
$n$	$20$	Grid resolution along each spatial dimension
$\mathcal{X}_{\mathrm{valid}}$	valid grid cells	Cells inside the region of interest with historical monitoring support
$N_{\mathrm{valid}}$	$\|\mathcal{X}_{\mathrm{valid}}\|$	Number of valid sensing locations
$M$	$6$	Number of agents
$T$	$40$	Maximum episode horizon

Appendix

Table 4: Main variables and parameters used in the Maryland nitrate concentration monitoring environment.

Figure 7 : Training dynamics in A3P5 and A5P3. For each setting, we report the average stopping time and posterior confidence. Curves are averaged over three random seeds and smoothed with an exponential moving average parameter of $0.2$ .

Confidence Bin	Mean Confidence	Empirical Accuracy	$\|\Delta\|$	Samples ( $n$ )
$[0.0,0.1)$	0.03	0.03	0.00	69,777
$[0.1,0.2)$	0.14	0.13	0.01	13,284
$[0.2,0.3)$	0.23	0.22	0.01	8,793
$[0.3,0.4)$	0.34	0.33	0.01	6,280
$[0.4,0.5)$	0.46	0.44	0.02	8,143
$[0.5,0.6)$	0.53	0.53	0.00	1,127

Appendix

Table 5 : Posterior calibration in A3P5. Predicted confidence closely tracks empirical accuracy across all ten bins.

Figure 8 : Survival plots for the bandit environments. The survival probability measures the fraction of runs that have not yet selected the stopping action at each timestep. Curves are averaged over three random seeds for each method.

Panel of Figure 9 — Figure 9 : Robustness analysis under different scaled Beta priors over arm means. Panels (a) and (c) show inference accuracy, while panels (b) and (d) show average stopping time. The top row corresponds to the A3P5 setting and the bottom row corresponds to the A5P3 setting.

Panel of Figure 10 — Figure 10 : Robustness analysis under different Dirichlet priors over arm capacities. Left: A3P5 setting. Right: A5P3 setting.

$t$	Joint action	Count	$n_{\text{active}}$	%
0	$(2,2,2,2,2)$	10,000	10,000	100.0
1	$(2,2,2,2,2)$	10,000	10,000	100.0
2	$(2,2,2,2,2)$	10,000	10,000	100.0
3	$(2,0,2,2,2)$	10,000	10,000	100.0
4	$(2,0,0,2,2)$	10,000	10,000	100.0
5	$(0,0,0,0,0)$	10,000	10,000	100.0

Appendix

Table 6: Most common joint exploration action at each step across 10,000 sampled environments (A3P5) under the greedy ICMAPE-TD3 policy. At step

t

, only environments still active (stopping time

\geq t

) are counted (

n_{\text{active}}

). The joint action

(a^{(1)},a^{(2)},a^{(3)},a^{(4)},a^{(5)})

lists the arm index (0–2) pulled by each player in the modal joint action. Steps beyond

t{=}15

are omitted as all environments have stopped.

1 player stopping simultaneously
Combination	Count	% vol. stops	% all envs
$\{P_{5}\}$	1,778	17.8	17.8
$\{P_{4}\}$	1,056	10.6	10.6
$\{P_{1}\}$	947	9.5	9.5
$\{P_{3}\}$	10	0.1	0.1
2 players stopping simultaneously

Appendix

Table 7: Frequency of joint stop-action combinations across 10,000 sampled environments (A3P5). A combination is recorded when one or more players simultaneously select the stop action at the terminal step. % vol. is the fraction of voluntary-stop episodes; % all is the fraction of all 10,000 environments.

Figure 11 : Signal Source Localization Training Dynamics. Curves are averaged over three random seeds and smoothed with an exponential moving average parameter of

0.2

Figure 12 : Survival plots for the signal source localization environment. The survival probability measures the fraction of runs that have not yet selected the stopping action at each timestep. Curves are averaged over three random seeds for each method.

Figure 13 : Inference accuracy as a function of the Manhattan distance between the true signal source and the distractor. Larger distances generally make the two sources easier to distinguish. Results are computed over 10,000 sampled instances for each distance value.

Figure 14 : Robustness analysis under different scaled Beta priors over distractor intensity in the signal source localization environment. The heatmap reports inference accuracy for different choices of $(\alpha,\beta)$ , with distractor intensities scaled to lie in $[0,0.7]$ .

$t$	Agent 1	Agent 2	Agent 3	$n_{\text{active}}$
0	dn (100.0%)	dn (100.0%)	rt ( 0 99.9%)	10,000
1	dn (100.0%)	dn (100.0%)	rt ( 0 94.6%)	9,994
2	rt (100.0%)	dn (100.0%)	rt ( 0 92.6%)	9,459
3	up (100.0%)	dn (100.0%)	up ( 0 95.2%)	8,759
4	up (100.0%)	dn (100.0%)	up ( 0 93.0%)	8,338
5	up (100.0%)	dn (100.0%)	up ( 0 87.5%)	7,755

Appendix

Table 8: Most common action for each agent at each step across active environments under the greedy ICMAPE-TD3 policy in the signal localization (10,000 samples). Each cell in the table reports the agent action and its frequency among the

n_{\text{active}}

environments still running at that step. Action labels: up

=

up dn

=

down, lf

=

left, rt

=

right; STOP

=

stop action. Agent 1 and agent 2 maintains a fully deterministic trajectory throughout

1 robot stopping simultaneously
Combination	Count	% vol. stops	% all envs
$\{P_{2}\}$	5,095	50.9	50.9
$\{P_{3}\}$	4,165	41.6	41.6
2 robots stopping simultaneously
$\{P_{2},P_{3}\}$	740	7.4	7.4

Appendix

Table 9: Frequency of joint stop-action combinations across 10,000 sampled environments in the robot wildfire task (Signal Localization). % vol. is the fraction of voluntary-stop episodes; % all is the fraction of all 10,000 environments.

Explore similar work

Jul 13, 2026cs.MA

Multi-Agent LLMs Fail to Explore Each Other

Exploration is essential for reliable autonomy in multi-agent systems, yet it remains unclear whether large language model (LLM) agents can explore effectively when interacting with one another. We show that modern LLM agents fail to do so, often exhibiting myopic and polarized interaction patterns that lead to suboptimal coordination and increased regret. We formalize this challenge as the Multi-Agent Exploration problem, modeling it as a partially observable stochastic game (POSG) problem in which agents must probe peers to infer their capabilities and identify effective interaction strategies. To address this, we introduce Multi- Agent Contextual Exploration (MACE), a lightweight framework that explicitly promotes exploration through structured peer selection. Across both contextual and parametric diversity settings, MACE substantially improves exploration behavior and downstream task performance. We further show theoretically that the value of exploration increases with agent diversity. Overall, our results highlight a fundamental limitation of current LLM agents and underscore the importance of explicitly guided exploration for reliable multi-agent autonomy. Code will be released in https://github.com/deeplearning-wisc/mace

Hyeong Kyu Choi, Jiatong Li, Wendi Li +2

University of Wisconsin–Madison · University of California, Santa Barbara

Observable Stochastic Game Diversity

Ask PDF

Oct 28, 2025cs.MA

MASPRM: Multi-Agent System Process Reward Model

Inference-time search over multi-agent systems (MAS) wastes compute when it cannot identify which agent's intermediate message advanced progress. We present the Multi-Agent System Process Reward Model (MASPRM), which scores routed transcripts (ordered sequences of messages between agents) and acts as an inference controller for step-level beam search (SBS) and Monte Carlo Tree Search (MCTS). MASPRM is trained from multi-agent MCTS rollouts labeled only with terminal outcome rewards, without human step-level annotations. We evaluate on GSM8K, MATH, MMLU, and LogiQA. Under matched scorer size and comparable MCTS budget, MASPRM exceeds a size-matched ORM by

+2.0

+3.0

points at 1.5B and

+4.1

+14.5

at 7B across all four benchmarks, with additional scorer-scaling gains over policy likelihood at 7B (avg

+13.4

under MCTS). MASPRM also improves ranking quality, reducing Hit@1 to Hit@5 gaps by up to

10.3

points, with the largest gains under stepwise search that uses intermediate decisions. Code: https://github.com/milad1378yz/MASPRM

Milad Yazdani, Mahdi Mostajabdaveh, Zirui Zhou +1

Department of Electrical and Computer Engineering, University of British Columbia, Vancouver, BC V6T1Z4, Canada · Huawei Technologies Canada, Burnaby, BC V5C6S7, Canada

Process Reward Model Beam Search Destination-Only Scoring

Ask PDF

Jun 29, 2026cs.AI

HyPOLE: Hyperproperty-Guided Multi-Agent Reinforcement Learning under Partial Observation

Formal specification is a powerful tool to guide the learning process and provides significant advantages over reward shaping: (1) mathematical rigor; (2) expressiveness to specify objectives and constraints, and (3) the ability to define tactics to achieve objectives. However, these benefits remain largely unexplored in the context of Multi-Agent Reinforcement Learning (MARL). This paper introduces HyPOLE, a novel framework for MARL under partial observability, where learning is guided by the expressive power of the so-called hyperproperties and, in particular, the temporal logic HyperLTL. We integrate Centralized Training for Decentralized Execution (CTDE) techniques with HyPOLE to synthesize decentralized policies, and our evaluation on SMAC, MessySMAC, and WildFire benchmark demonstrates clear advantages over baselines.

Arshia Rafieioskouei, Tzu-Han Hsu, Matthew Lucas +1

Department of Computer Science and Engineering, Michigan State University, MI, USA.

Multi-Agent Reinforcement Learning Partial Observability Signal Temporal Logic

Ask PDF