Skip to content

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

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Agents form hypotheses and seek information strategically in high-stakes settings

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

LMs deployed as agentic information-seekers fail at rational question selection, grounded answering, and explore/exploit tradeoffs compared to humans. The authors introduce Collaborative Battleship as a controlled testbed and three Monte Carlo inference strategies grounded in Bayesian Experimental Design (BED) that, when combined, lift weak models like Llama-4-Scout to 82% win rate against humans and 67% against GPT-5 at ~1% of GPT-5's cost.

Problem

LMs are increasingly used as agents that must seek information strategically (e.g., scientific discovery, medical diagnosis), but it is unknown whether they behave like rational agents under resource constraints. Existing evaluations lack controlled settings that decouple question quality, answer accuracy, and action selection while also enabling comparison against human behavior and Bayesian-optimal strategies.

Method

Collaborative Battleship: A two-player game on an 8×8 grid. The Captain interleaves yes/no natural-language questions (≤15) and shots (≤40); the Spotter answers from the full board. Questions are compiled to Python programs executed against a particle approximation of the board hypothesis space \(\mathcal{S}\).

The formal framework is Bayesian Experimental Design (BED): - Belief state \(\pi_t(s) = \Pr(S = s \mid x, H_{1:t})\) maintained via Sequential Monte Carlo (SMC) over board particles. - Spotter modeled as a binary symmetric channel \(\text{BSC}(\varepsilon)\); Bayesian belief update: \(\pi_{t+1}(s) \propto \pi_t(s)\bigl[(1-\varepsilon)\mathbf{1}\{\tilde{a}_t = f_{q_t}(s)\} + \varepsilon\,\mathbf{1}\{\tilde{a}_t \neq f_{q_t}(s)\}\bigr]\). - Expected Information Gain: \(\text{EIG}_\varepsilon(q_t) = H_b\!\bigl(\varepsilon + (1-2\varepsilon)p_t\bigr) - H_b(\varepsilon)\), maximized when \(p_t \approx \frac{1}{2}\).

Three Bayesian inference-time strategies: - Bayes-Q: Sample candidate questions from the LM; select \(q^* = \arg\max_q \text{EIG}_\varepsilon(q)\). - Bayes-M: Select shot \(u^* = \arg\max_u p_t^{\text{hit}}(u \mid x, H_{1:t})\) (MAP under particle belief). - Bayes-D: One-step lookahead decision between asking and shooting: ask iff discounted expected post-question MAP hit probability \(\gamma\hat{p}_{t+1}^{\text{hit}}\) exceeds current MAP hit probability \(p_t^{\text{hit}}(u^*_t)\); \(\gamma = 0.95\).

For the Spotter, language-to-code translation (LM generates Python programs verified against board arrays) is used to improve grounded answering accuracy.

Key Contributions

  • Collaborative Battleship game + BATTLESHIP QA dataset: 126 full human trajectories (N=42), 931 gold-annotated yes/no QA pairs (SpotterQA) with pragmatic annotations (discourse-dependence, state-dependence, vagueness, ambiguity), and full strategic game evaluation (CaptainQA).
  • SpotterQA benchmark: Evaluation of 15 frontier LMs on grounded yes/no answering; establishes that code generation (+14.7 p.p. CoT+Code over Base) and CoT improve accuracy significantly.
  • Three Bayesian inference-time strategies (Bayes-Q, Bayes-M, Bayes-D) requiring no fine-tuning, applicable at inference time to any LM.
  • Replication on Guess Who? (TextArena), demonstrating generality.

Results

  • SpotterQA accuracy (direct → CoT+Code): GPT-4.1: 75.2% → 90.9%; Claude 4 Opus: 86.8% → 94.4%; mean improvement +14.7 p.p. (Mann-Whitney \(p < 0.001\)). Human baseline: 92.5%.
  • LMs on complex (context-dependent) questions: GPT-4o drops from 72.8% (simple) to 60.4% (complex); Llama-4-Scout from 68.0% to 54.0%. Best model (o3) achieves 87.4% on complex vs. 91.9% human.
  • CaptainQA targeting score (F1):
  • Llama-4-Scout LM-only: 0.367 → Bayes-QMD: 0.764 (+0.397 F1)
  • GPT-4o LM-only: 0.450 → Bayes-QMD: 0.782 (+0.332 F1)
  • Win rates with Bayes-QMD: Llama-4-Scout vs. humans 8% → 82%; vs. GPT-5 0% → 67%.
  • EIG improvement: Bayes-Q raises mean per-question EIG by up to 0.227 bits (94.2% of the noise ceiling of 0.531 bits at \(\varepsilon=0.1\)); eliminates redundant zero-EIG questions (e.g., Llama-4-Scout: 18.5% → ~0%).
  • Cost: Llama-4-Scout + Bayes-QMD ≈1% of GPT-5 cost; GPT-4o + Bayes-QMD ≈35%.
  • Guess Who? replication: +42.4 p.p. accuracy for Llama-4-Scout, +28.3 p.p. for GPT-4o.

Limitations

  • CaptainQA evaluation restricted to three LMs (Llama-4-Scout, GPT-4o, GPT-5) due to sequential multi-API-call cost per turn; Bayes-QMD not evaluated with GPT-5.
  • Bayesian strategies rely on a tractable, enumerable hypothesis space; direct extension to open-ended discovery settings requires hypothesis space approximation.
  • One-step lookahead (Bayes-D) is not globally optimal; belief-space planning over longer horizons is PSPACE-hard.
  • SMC approximation quality degrades with hypothesis space size; the 8×8 grid is relatively small.
  • Code generation approach requires LMs capable of writing executable Python; less applicable to non-code-capable models.
  • Human study sample is limited (N=42 Prolific participants); may not represent expert information-seekers.

Relevance to Agentic AI / LLM Agents

This paper directly addresses the inference-time rationality gap in LM agents tasked with active information gathering—a core bottleneck for agentic pipelines in scientific and diagnostic settings. The Bayes-Q/M/D framework demonstrates that structured, program-mediated Bayesian reasoning layered on top of LM generation (without fine-tuning) can overcome weak base model capabilities, offering a practical blueprint for boosting agent performance in any domain with a computable hypothesis space. The finding that weaker models + Bayesian scaffolding outperform frontier models at 1% cost is directly relevant to cost-efficient agentic system design. The BATTLESHIP QA benchmark also provides a rare controlled environment for studying explore/exploit tradeoffs—an underexplored but critical axis in multi-step agentic reasoning.