Monte Carlo Query Search: Active Capability Assessment of AI Agents

Black-box AI (BBAI) systems, including foundation-model agents, are increasingly used for sequential decision making. Safe deployment requires methods for characterizing what such systems can do, when they can do it, and what outcomes may result. We introduce Monte Carlo Query Synthesis (MCQS), an active query-synthesis method for learning symbolic stochastic capability models of BBAIs. MCQS models capabilities as conditional probability distributions over outcomes and formulates capability learning as an active learning problem over policies. Our approach uses Monte Carlo tree search to synthesize queries that induce BBAI execution trajectories with high discriminative value between extremal hypothesis models: the lattice meet and join corresponding to the most pessimistic and optimistic hypotheses consistent with the observations. Executing these queries with the agent yields information-rich state-action trajectories that speed up learning by pruning inconsistent hypotheses. We prove soundness, completeness, and convergence properties under standard realizability and sampling assumptions. Experiments with multiple BBAI systems show that MCQS learns accurate capability models more efficiently than baseline query strategies.