Shoot First, Ask Questions Later? Building Rational Agents that Explore and Act Like People

AI summary

Overview

• Research area: Natural language processing and cognitive science, at the intersection of language-model agents, Bayesian Experimental Design, and human information-seeking behavior.
• Technical level: Advanced. The paper combines formal Bayesian inference (belief updating, expected information gain, sequential Monte Carlo) with large-scale LM benchmarking and a human behavioral study.
• One-sentence scope: The paper introduces a two-player dialogue version of Battleship called Collaborative Battleship, compares 15 language models against 42 human players on asking informative questions, answering them accurately, and deciding when to explore versus act, and shows that Bayesian inference-time strategies can lift weak models to superhuman game performance at a fraction of frontier-model cost.

What This Paper Is About

Many high-stakes AI applications require agents to seek information strategically — forming hypotheses, asking targeted questions, and acting under uncertainty — rather than simply answering user queries. The paper asks whether current language models actually behave like rational agents in such settings, and whether Bayesian inference-time strategies can close the gap. To answer this, the authors build a collaborative dialogue task where one player must decide whether to ask a question or take a shot, and another must answer accurately with only "yes" or "no."

Key Contributions

1. Collaborative Battleship task and BattleshipQA dataset. A two-player adaptation of Battleship in which a partially-informed Captain balances exploration (natural-language yes/no questions translated into Python programs) against exploitation (shooting tiles), while a fully-informed Spotter supplies grounded answers. The authors collected 126 full human-human game trajectories from N=42 participants over 18 pre-sampled 8×8 boards, yielding a gold set of 931 annotated questions with a human accuracy baseline of 92.5%.

2. Two complementary evaluation benchmarks. SpotterQA tests grounded question-answering on the 931 gold questions, annotated for question features such as discourse-dependence, state-dependence, vagueness, and ambiguity. CaptainQA tests full strategic gameplay under a cap of 15 questions and 40 moves per game.

3. Three Bayesian inference-time strategies for language models. Bayes-Q selects questions maximizing expected information gain (EIG); Bayes-M selects moves maximizing hit probability under the current belief; Bayes-D uses a discounted one-step lookahead to decide whether to ask or shoot. These are described as resource rational rather than globally optimal.

4. Generalization to a second information-seeking domain. The framework is replicated on the Guess Who? task from TextArena, showing significant accuracy gains and demonstrating the approach is not specific to Battleship.

Main Findings

• Answering ability varies widely across models. Across the 15 LMs tested on SpotterQA, accuracy ranged from near-chance 52.5% (GPT-4o-mini) to 92.8% (o3 mini). Several models (o3, o4-mini, and GPT-5) met or exceeded mean human performance of 92.5%.

• Code generation substantially improves grounded answering. Code generation improved SpotterQA by 13.2% absolute over the Base direct-answer condition, and combining code generation with chain-of-thought (CoT + Code) yielded even larger 14.7% gains. GPT-4.1 improved from 75.2% (Base) to 90.9% (CoT + Code), and Claude 4 Opus from 86.8% to 94.4%. A two-sided Mann-Whitney U test confirmed these differences (p < 0.001).

• Models degrade on context-dependent questions. Human accuracy stayed roughly consistent between simple (92.8%) and complex (91.9%) questions, whereas GPT-4o dropped from 72.8% to 60.4% and Llama-4-Scout from 68.0% to 54.0%. Code generation partially mitigated the gap, but even the best model, o3, still fell short on complex questions (87.4% vs. 91.9%).

• Bayesian question sampling raises information gain. Bayes-Q raised mean per-question EIG by up to 0.227 bits, reaching up to 94.2% of the noise ceiling. The maximum achievable EIG in the setting is 1 − H_b(0.1) = 0.531 bits.

• Redundant questions are largely eliminated. Llama-4-Scout asked redundant zero-EIG questions 18.5% of the time and GPT-4o 14.6%; Bayes-Q reduced these to 0.2% and 1.2% respectively. Humans and GPT-5 rarely asked redundant questions.

• Bayesian strategies lift weak models to superhuman game play. LM-only targeting scores were 0.367 F1 for Llama-4-Scout and 0.450 F1 for GPT-4o; adding Bayes-QMD raised them to 0.764 and 0.782 F1. Llama-4-Scout jumped 0.367 → 0.764 F1 and GPT-4o 0.450 → 0.782 F1, and the combined agents reached 0.82–0.83 win rate against humans and 0.67 win rate against GPT-5.

• High EIG alone does not guarantee better play. Bayes-Q improved EIG consistently but only moved targeting scores by +0.021–0.026 F1 for Llama-4-Scout and GPT-4o, suggesting weaker models cannot effectively convert information into moves; Bayes-M, which marginalizes over the implications of each question, was the more reliable mechanism.

• Humans and strong models ask fewer, better questions. Humans and GPT-5 asked 8.0–8.2 questions on average versus 14.1–14.9 for weaker players. Weaker models tended to front-load all 15 questions, a myopic pattern mitigated by Bayes-D one-step lookahead.

• Cost efficiency. The Bayesian-enhanced models beat GPT-5 at approximately 1% of GPT-5's cost for Llama-4-Scout and approximately 35% for GPT-4o (reported in the abstract as 99.7× and 2.8× savings relative to GPT-5). Bayesian question or move selection did not significantly benefit GPT-5 itself.

• Results generalize to Guess Who? Bayes-QM improved success rates from 0.617 → 0.900 for GPT-4o and 0.300 → 0.724 for Llama-4-Scout, corresponding to +28.3 and +42.4 percentage-point gains.

• Human question-asking correlates with performance. Mean targeting score (F1) correlated with number of questions asked across human pairs (ρ = 0.684, p < 0.002), and different players showed widely varying explore/exploit strategies.

Methodology in Plain English

The authors built a dialogue version of Battleship in which a Captain sees only part of the board and can either ask a natural-language yes/no question or fire at a hidden tile, while a Spotter sees the whole board and can only answer "yes" or "no." This information bottleneck prevents game-breaking questions like "where are all the ships?"

They first ran a human study: 42 participants on Prolific played six games each in randomly assigned pairs, for 48–60 minutes, earning $12.03–$14.62 per hour including targeting bonuses. All questions were manually annotated with gold answers (931 kept after filtering disagreements), then categorized as "simple" (answerable from the board alone) or "complex" (requiring dialogue history), with additional labels for discourse-dependence, state-dependence, vagueness, and ambiguity.

To make the problem computable, they translated each natural-language question into a Python program that acts as a function from board states to yes/no answers. This lets them sample many plausible hidden boards consistent with what the Captain has observed, and compute quantities like the probability a question returns "yes" and the expected information gain of asking it. They model the Spotter as a noisy binary symmetric channel with flip probability ε (set to 0.1, calibrated from GPT-5's SpotterQA accuracy) and update the belief over boards turn by turn using sequential Monte Carlo with per-turn resampling.

Three strategies follow: Bayes-Q samples candidate questions from a model and picks the one with highest EIG; Bayes-M fires at the tile with highest hit probability under the current belief; Bayes-D compares the current best shot against the expected best shot after asking a question, discounted by γ = 0.95, and asks only when the expected improvement is larger. CaptainQA evaluation covered 54 games (18 boards × 3 seeds) with Llama-4-Scout, GPT-4o, and GPT-5 as Captains, fixing the Spotter to GPT-5 (CoT + Code).

Why This Matters

Impact on research. The paper offers a controlled, cognitively motivated testbed for Bayesian Experimental Design with language models, plus a reusable evaluation harness and a multimodal human dialogue dataset. It shows that resource-rational, sample-based strategies — rather than exact planning — can compensate for weak model capabilities, and it quantifies a persistent gap between human and model pragmatic reasoning on context-dependent questions.

Real-world applications.

• Scientific discovery, where agents must propose experiments or conjectures and choose among combinatorially many hypotheses.
• Medical diagnosis, where targeted questions and test ordering must be balanced against limited resources and time.
• Customer-facing assistants and elicitation tools that need to ask clarifying questions instead of guessing user intent.
• Interactive games, tutoring, and collaborative decision-support systems where agents must coordinate with people under uncertainty.

Industry relevance. The results show that cheap models plus Bayesian inference can outperform much more expensive frontier models on this task while costing roughly 1% as much for Llama-4-Scout, which is a strong argument for inference-time strategy over raw model scale. This matters for deployments where per-query cost and latency constrain design, and suggests that question-selection and action-selection modules can be added around existing models rather than requiring retraining.

Future Directions

• Inferring Spotter reliability rather than fixing it. The paper notes that people are highly sensitive to the reliability of information, and that a more robust approach would infer ε per Spotter instead of using a fixed value; the same idea applies to adapting to aleatoric uncertainty in scientific settings.

• Modeling pragmatics explicitly. Many rich phenomena — discourse-dependence, state-dependence, vagueness, ambiguity — are annotated but not explicitly modeled; techniques from the Rational Speech Acts framework could yield agents capable of more sophisticated pragmatic reasoning.

• Learning the generative world model. The Bayesian strategies require drawing conditional samples from a generative model of world states, which was implementable by hand in Battleship. Generalizing may require learning such models as code (via model synthesis architectures) or as images (via VAEs or diffusion).

• Human-agent collaboration and longer-horizon planning. The current policy uses one-step lookahead because belief-space planning is PSPACE-hard; extending to longer horizons and studying agents that collaborate effectively with people are flagged as open directions.

Target Audience

Researchers and practitioners in NLP, AI agents, and cognitive science who are interested in information-seeking, Bayesian Experimental Design, question asking, or human-model comparison. It is also relevant to engineers building tool-using or diagnostic agents who want concrete evidence that inference-time strategies can substitute for model scale, and to cognitive scientists studying resource rationality and explore/exploit tradeoffs. The paper assumes familiarity with Bayesian inference, Monte Carlo methods, and language-model evaluation, so it is best suited to readers with an intermediate-to-advanced technical background.

Authors’ abstract

Many emerging applications of AI--from scientific discovery to medical diagnosis--require agents to seek information strategically: forming hypotheses, asking targeted questions, and making decisions under uncertainty. In high-stakes settings with limited resources, do language models (LMs) behave like rational agents? Drawing on insights from human cognition, we develop methods to evaluate and enhance agentic information-seeking. First, we introduce a decision-oriented dialogue task called Collaborative Battleship, in which a Captain must balance exploration (asking questions) and action (taking shots), while a Spotter must supply accurate, contextually-grounded answers. Compared to human players (N=42), we find that many LM agents struggle to ask informative questions, produce accurate answers, and identify high-utility actions. To address these gaps, we develop novel Monte Carlo inference strategies for LMs inspired by Bayesian Experimental Design (BED). For Spotter agents, our approach boosts accuracy by up to 14.7% absolute over LM-only baselines; for Captain agents, it raises expected information gain (EIG) by up to 0.227 bits (94.2% of the achievable noise ceiling). Combined, these components yield sharper targeting (+0.303-0.374 F1), and enable weaker LMs, such as Llama-4-Scout, to outperform both humans (8% -&gt; 82% win rate) and frontier models (0% -&gt; 67% win rate vs. GPT-5) at ~1% of GPT-5's cost. We replicate these findings on Guess Who?, where our methods significantly boost accuracy (+28.3-42.4 p.p.), demonstrating their general applicability for building information-seeking agents.