Shoot First, Ask Questions Later? Building Rational Agents that Explore and Act Like People
Authors: Gabriel Grand
Valerio Pepe
Joshua B. Tenenbaum
Jacob Andreas
Venue: ICLR 2026 Oral (2026)
Keywords: Bayesian experimental design
information-seeking
question asking
Collaborative Battleship
expected information gain (EIG)
explore-exploit tradeoffs
resource rationality
probabilistic inference
Monte Carlo sampling
symbolic grounding
code generation
reasoning
decision-oriented dialogue
cognitive modeling
human behavior
language model agents
scientific discovery
Primary area: applications to neuroscience & cognitive science
TL;DR: We introduce a collaborative Battleship task to evaluate information-seeking in humans and agents; insights from Bayesian Experimental Design (BED) yield inference-time strategies for building resource-rational agents in discovery settings.

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% → 82% win rate) and frontier models (0% → 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.

Published as a conference paper at ICLR 2026
SHOOT FIRST, ASK QUESTIONS LATER? BUILDING RATIONAL AGENTS THAT EXPLORE AND ACT LIKE PEOPLE
Gabriel Grand Valerio Pepe** Joshua B. Tenenbaum!2 Jacob Andreas
MITT CSAIL MIT Brain and Cognitive Sciences
Harvard SEAS
*Equal contribution
ABSTRACT
Many emerging applications of Al-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 eval- uate and enhance agentic information-seekle seeking.. First, we introduce 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-groundee ers (N=42), we find that many LM agents struggle ask informative questions. produce accurate answers, and identify high-utility actions. To address these gaps, we develop novel Monte Carlo inference strategies for I.Ms 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 ex- pected information gain (EIG) by up 0.227 bits (94.2% of the achievable noise ceiling). Combined, these components yield sharper targeting ++..303-0.374 Fl), and enable weaker LMs, such Llama-4-S 4lama-4-Scout, to outperform both humans (8% + 82% win rate) and frontier models (0% + 67% win rate vs. GPT-5) at 11% of GPT-5's cost. We replicate these findings Guess Who?, where our methods significantly boost accuracy (+28.3-42.4 4 p.p.). demonstrating their general appli- cability for building information-seeking agents.
answers. Compared to human play-
gabegrand. gi thub. io/batteeshhp
INTRODUCTION
Language models (LMs) are rapidly evolving from chat-based assistants into fully-fledged agents that interact with the world. Some of the most exciting applications of conttttinnn scien- tific experiments, conjecturing new mathematical theorems, or discovering novel drugs (Gottweis al., 2025; Lu et al., 2024; Poesia al., 2024; Schmidgall et al., 202oe-involve seeking "hits" in combinatorially vast hypothesis spaces. Traditional accounts of information-sseking assume agents are capable of various rational, probabilistic inferences; e.g., inferring belief' states, reasoning about uncertainty, and navigating explore/exploit tradeoffs (Anderson, 1990; Auer et al., 2002; Lindley, 1956; MacKay, 1992: Sutton & Barto, 2018). To what extent can current LMs, which are typically optimized to answer users' queries (Ouyang et al., 2022; Rafailov et al., 2023), instead ask good questions for themselves? And what strategies can we use to improve their ceormatioonseekinng abilities at inference time?
In this work, we aim to both evaluate and improve the ability of frontier models to ask goal-directed questions and take actions in dynamic environment. Our setting is an adaptation of the classic board game Battleship where players may ask natural language questions to gain information about hidden ships. We further extend this paradigm, which was originally developed to study human question-asking (Rothe et al., 2017; 2018; 2019), into a two-player dialogue and decision- makingg task. We conduct experiments with both strategies that LMs employ against both human behavior and idealized resource rational strategies that combine LMs with Bayesian inference techniques.
and agent-agent pairings, comparing the

---

Published as a conference paper at ICLR 2026
Max postor of (MAP) oddion ove bokie RCMOri x]
Is the purple ship vertical?
No
14 peyle drp reruo?
G3
Optimite infomnaiiity tiile at "Taie
Captain
Spotter
Transtate
Language to-ooda
videa Soother
Figure 1: Illustration of our Collaborative Battleship game. On each turn, the Captain must choose whether to gather information (ask question) or take action (shoot at a tile). The Spotter sees the full board, but can only provide yes/no answers. Fach role requires well-defined forms of internal reasoning (thought hubbles), which we implement Monte Carlo inference over an approximate hypothesis space. This framework allows us to compare both humans and LM agents against idealized Bayesian strategies in a controlled setting.
Our Battleship task tests several distinct cognitive capabilities: (1) Asking informative questions that effectively reduce uncertainty; (2) Providing accurate answers that are grounded in both the current observation state and the dialogue context; (3) Taking strategic actions that leverage available information; (4) Navigating explore/exploit tradeoff's in order to balance information gathering with goal-directed behavior. The minimalistic environment, which shares elements of other challenging text- and grid-based evaluations (Chollet al., 2024; Guertler et al., 2025; Jansen al., 2024; Ke et al., 2024; Wang et al., 2022; Yao et al., 2025), provides ideal testbed for studying Bayesian experimental design (BED; Chaloner & Verdinelli, 1995; Lindley, 1956; Rainforth et al., 2023) in complex state spaces. In particular, questions in Battleship are directly translatable to Python programs; executing these against a sampled "hypothesis space" of game states to compute their expected information gain (EIG) provides a robust way compare the utility of human and model- generated questions.
anfornation-athhering
As the foundation of our study, we collect 126 full human-human game trajectories (N=42 partici- pants), capturing both dialogue and actions. Our BATTLESHIPQQ dataset provides two complemen- tary evaluation settings: SpotterQA, which tests grounded answering on 931 gold yes/no questions with expert annotations for answers and various question features, and CaptainQA, which tests full strategic gameplay under limited questions and shots.
Evaluating current LMs on these benchmarks reveals a wide spectrum of capability. Weaker models like Llama-4-Scout only marginally exceed random baselines on both SpotterQA (62.2% accuracy) and CaptainQA (68.8% win rate vs. random firing), while frontier reasoning models like GPT-5 match or exceed average human performance. On the answering side, we find that Python code gen- eration substantially improves grounding: across 15 LMs, it boosts SpotterQA accuracy by 14.7% over direct answering and chain-of-thoughh baselines, with especially large gains for models such as GPT-4.1 (75.2% + 90.9%) and Claude 4 Opus (86.8% + 94.4%). On the question-asking side, we introduce a simple Bayesian sampling method that substantially improves question quality, raising mean per-question expected information gain (EIG) CaptainQA by up to 0.227 bits 94.2% of the information-theoree tions that have zero information gain (e.g.. Llama-4-Scout: 18.5% of questions; GPT-4o: 14.6%); our method effectively climinates these cases.
ceiling. We also observe that many models tend to ask redundant ques-
In total, we introduce three rational strategies for question-asking (Bayes-Q), move selection (Bayes- M), and mecision-making (Bayes-D). When combined, these strategies yield substantial improve- ments in overall game performance, measured by targeting accuracy (+0.397 Fl for Llama-4- Scout, +0.332 F1 for GPT-4o). Remarkably, these Bayesian enhancements enable even weak LMs to reach superhuman- GPT-5, all while maintaining substantial cost savings (99.7x x for Llama-4-Scout and 2.8x for GPT- 4o relative to GPT-5). Finally, we replicate our experiments on the Guess Who? task from TextArena (Guertler et al.. 2025) and observe similarly significant gains (+42.4 p.p. for Llama-4-Scout and +28.3 p.p. for GPT-4o), demonstrating that our approach generalizes beyond the Battleship domain.
performance, with win rates of 81 81-82% against humans and 67% against
In sum, our work provides both practical and theoretical contributions. Concretely, we introduce reusable evaluation harness for studying agentic iitormation-seekinng and curate novel multimodal dataset, BATTLESHIPQA, that captures rich pragmatic phenomena in grounded dialogue. Concep- tually, we formalize several boyeesia-insppiee inference-time time strategies that can be applied to other discovery settings build rational information-seekinn seeking agents.
2

---

Published as a conference paper at ICLR 2026
2
THE BATTLESHIP GAME
Our environment draws inspiration from the cognitive science literature, where Battleship-lkke tasks have previously been utilized to study human information riformation-seeking behavior. In prior work, single- player participants viewed partially-revealed game boards and decided what tiles to reveal (Gureckis & Markant, 2009; Markant & Gureckis, 2012; 2014) or what questions to ask (Rothe et al., 2017; 2018: 2019). Here, we adapt this paradigm to study both humans and language model agents. Our Collaborative Battleship game (Fig. 1) is played by two players: partially must balance exploration (asking questions) and exploitation (taking shots), and a fully-informed Spotter who must provide accurate answers that are grounded in both the game state and the ongoing dialogue. Further details about the game rules, interface, and data collection are provided in $A.
Captain who
Our work extends the Battleship paradigm along several key dimensions. (1) Full multi-ture games: Prior work was limited to static "snapshots" of game states; here, we simulate full game trajectories. (2) Dialogue setting: To enable multi-turn play, we introduce second player (the Spotter), whose role is necessary to provide real-time answers to the Captain's questions. (3) Python programs: In prior work, questions were represented programs in hand-engineered domain-specific language (DSL), with translation performed either manually (Rothe et al., 2017) or using LMs (Grand et al., 2024). Here, we represent questions with Python programs, which are both more expressive and easier for LMs to generate. (4) Information bottleneck: In prior work, players could in principle ask questions like, "What are the coordinates of all the ships?". To prevent players from asking questions in order to achieve monetary bonuses ($4.1), we deliberately restrict the Spotter to "Yes" or "No" answers. While less open-ended, such information bottlenecks also found in games like Twenty Questions, Guess Who, Mastermind, and the original Battleship- ensure strategic balance and enable the study of explore/exploit decision-making
3 FORMAL FRAMEWORK: BAYESIAN EXPERIMENTAL DESIGN
We cast question selection in our Battleship variant as Bayesian Experimental Design (BED); on each turn we choose to explore- by asking a yes/no question to gain information or to act by firing a hidden tile.
The hidden board is a random variable S E S. The observed partial board x induces the feasible
set Sr = (s E S : s consistent with x: ).
The belief at the start of turn i given history His is II. (8) = Pr(S = s x. H1=)). Intuitively, this belief places weight on every board that could still be true given what we have seen so far.
A natural-language question translates to deterministic function fa S + {0, 1}. The true (noise-freet free) answer is Ag = fS( E {0, For the question asked at turn f, we write A, = fg. (S).
Observation Model (Noisy Spotter) In our setting, the Spotter plays the role of an observation model. Assuming an oracle Spotter, the predictive probability that the true answer will be "yes" is simply
Pt = Pr(A: = Hix) = Σ m.(6) (+))))(()) SES
(I)
We expect that the Spotter (human or AI) may occasionally make mistakes, either because they misread the board, misinterpreted the question, or miscommunicated the answer. Accordingly, we model the Spotter (and language-to-code translation) as a binary symmetric channel BSC(=) with flip probability E E [0, 1. yiclding noisy answer A, E 10.
Bayesian Belief Update. We start with basic model of the Captain as Bayesian ideal observer. After asking qt. the Captain updates their belief by reweighting each candidate board s E Srz by how compatible it is with the observed answer ã {0, 1} under the noise model:
Ts41(s) & (s) [1 E) ffā, = fu. (s)) + E fāā + fg. (s)}
(2)
Intuition. Boards that would have produced the observed answer (c.g., f (s) = ā,) get boosted by factor - E, while boards that would have said the opposite retain some weight because mistakes
3

---

Published as a conference paper at ICLR 2026
possible. This gently shifts mass toward boards consistent with what we saw without discarding alternatives outright when >> 0.
Sequential Monte Carlo (SMC) Approximation. Exact sums over Ste are typically intractable; therefore maintain a weighted particle approximation {(+), wy } which is updated via sequen- tial Monte Carlo (SMC; Doucet et al., 2001) with per-turn resampling: see şB for details.
Expected Information Gain. To decide which of many possible candidate questions qt ask, we adopt standard ceermaationthhooeele approach (MacKay. 1992; Shannon, 1948) that considers the expected information the Captain will gain about the board from its (noisy) answer:
EIG, (q: | x, H1a)) = AS z, H1:+)
(3)
For BSC(s), this admits closed form in terms of the binary entropy Hg:
(g 2; H1.e) Ho(E + 22) p.)
Ho(e), Pr as in (1)
(4)
Intuition. The first term HE + (1 2c) pt) is the uncertainty in the noisy answer we expect to hear; the second term (E) is the uncertainty injected by the channel itself. Their difference is how much uncertainty about the board we expect remove by asking this question. This quantity is maximized when Pt. Rs 2. i.e., when under our current belief the question is about as likely to return "yes" as "no".
3.1 BAYESIAN STRATEGIES FOR EXPLORATION AND ACTION
We now describe three strategies that leverage the formal framework above to (i) ask questions that maximize expected information gain, (ii) select actions that maximize hit probability, and (iii) decide between asking a question or taking an action at each turn. These strategies are not necessarily globally optimal, but rather resource rational in the sense that they the current belief n. to maximize expected utility at each turn.
Asking questions to maximize information gain (QBayes). To maximize expected information gain, a simple strategy is to sample a set of candidate questions Q (e.g., from an LM) and select the one with highest EIGg:
Te E arg max EIG;(g x; His)) QEQ
(5)
Selecting moves to maximize hit probability (MBayss). For a candidate tile (restricted un- revealed locations), define the probability of a hit under the current belief and the corresponding myopic maximum posteriori (MAP) action:
u E arg max ph (u x. M2:); p. p1u((u x1 H1:) = Σ xe(s)1fu contains ship in s} u unrevealed
(6)
SES
Making rational decisions via one-step lookahead (DBayes). There are many possible strategies for deciding whether to ask question take shot; here, we describe simple planning-baat -bsed approach that uses a discounted one-step lookahead to estimate the value of asking a question vs. taking shot.
Expected post-ques qust-quesionn hit probability. For a candidate question qt, we can estimate the next-turn MAP hit probability by marginalizing over possible answers à
hit P++1 (u I, H1., = Σ
hit Pr(A, à x. His 4) P++1 (u x, H1., a). aE(0.1)
Here = =1)===++ 2x) Pe with pa in (1), and the inner hit probability is evaluated under the updated belief given à. Let y E [0, discount the value of information acquired this turn. The strategy proceeds follows:
1. Select potential question of by maximizing EIG via Eq. (5).
2. Compute the pre- and post-question MAP moves ut and uH+1 and corresponding hit probabili- ties in Eqs. (6) and (7).
3. If y (PP11110 (gi x. H1:)) phit (ut H1:), ask q::s otherwise, act (shoot) at ut.
4

---

Published as a conference paper at ICLR 2026
Intuition. When 1, the policy asks question iff the expected one-step improvement in the next- turn MAP hit probability exceeds the current MAP chance; smaller prefers acting sooner. While optimizing over longer horizons is possible, the problem of belief-space planning is PSPACE-ha (Papadimitriou & Tsitsiklis, 1987); in practice one-step lookahead simple and effective.
4 EXPERIMENTS
We present experimental evaluation in three parts. First, in $4.1, we describe our human be- havioral study and dataset, BATTLESHIPQA, in order to build an empirical account human-like information seeking. Next, we present series of experiments that evaluate the ability of LMs to answer and ask questions, leveraging BATTLESHIPQA in two distinct ways. In $4.2, we focus on grounded question-ansswering. evaluating the performance of LMs in answering questions asked by humans. Finally, in $4.3, we focus on question-asking, evaluating the ability of LMs to ask infor- mative questions and make strategic moves in the full game setting.
4.1 EVALUATING HUMAN INFORMATION- COOERMMATION-SEKKING SEEKING BEHAVIOR
We conducted a two-player, synchronous behavioral study in which participants played Collabo- rative Battleship (described in $2). Participants (N=42) were recruited from Prolific and randomly partnered with another participant. Each pair alternated between the Captain and Spotter roles over 6 games, with a total time commitment of 48-60 minutes and average earnings of $12.03-$14.6 14.62/hrr (including bonuses based on targeting score). In total, we collected data for 18 pre-sampled, 8x8 game boards, allocated evenly across pairs. Further details about the experimental design, imple- mentation, and compensation are provided in $A.2.
Analysis of human data. We manually annotated the human data in order to (1) establish set of gold labels for evaluating model performance and (2) categorize the types of questions being asked. First, annotated all questions with "gold answer" label and filtered out questions for which there was inter-annotator disagreement. After this process, we obtained a gold dataset of 931 questions, establishing human accuracy baseline of 92.5%.
Next, we categorized questions into two groups based on whether they could be answered solely from the true board S (simple) required additional context from the game history H1:, (complex). Within the "complex" category, we futher annotated for various linguistic and pragmatic phenomena, such as discooursedeependence (c.g.. "Is it longer than 3 tiles?" where "it" references specific ship), state-dependence (c.g., "Should I keep firing up?"), vagueness (e.g.. "Is there a ship near the center?") and ambiguity (i.e., multiple possible interpretations). Further definitions and details are given in $A.3; illustrated examples are provided in $A.4.
4.2 SPOTTERQA: MODELING QUESTION-ANSWERN
We begin our modeling experiments with focused evaluation of models' performance in the Spotter role, since providing accurate answers is a crucial signal models' ability to reason about the game state. In particular, we interested in two answering strategies that we hypothesize should improve
0.60
0.75
0.70
Taraddng Soore
0.0
8.00
0.85
0.50
0.45
2.5
5.0
7.5
10.0
12.5
Qucsttoos..o Asked
Mean targeting (FI) ques- tions asked for cach buman pair.
(b) Timeline multiple human-human games Battleship single (B02). Fach represents question akked; colors indicate different players.
Figure 2: Human results highlights. (a) Asking questions correlates with performance (p 0.684,
0. 0.002); (b) Different players demonstrate widely varying explorc/exploit strategies; some alternate between asking questions and making moves, while others focus on information
-aooraaiin-gatheringg gathering before taking any actions.
5

---

Published as a conference paper at ICLR 2026
10
Perfbrmance
Aosumeyy
0.7
0.6
04/00
0.
Base
CoT
Code
CoT Code
Complex
(a) By LM
(b) By Spotter Strategy
(c) By Question Complexity
Base LM
CoT
Code
CoT + Code
Human
Figure 3: SpotterQA key results. (a) Accuracy varies significantly across the 15 LMs tested. (b) Across LMs, code generation improves accuracy over direct answering and CoT baselines. (c) Whereas human accuracy remains roughly consistent, LMS degrade significantly on "complex" questions that require context. Dashed lines indicate mean human accuracy 92.5%) w/r/ gold answer labels. Error hars indicate 95% Cls.
performance: Mhain-of-thouge reasoning (CoT; Kojima et al., 2022; Nye et al., 2021; Wei et al., 2022) and language-to-cow translation (Code; Austin et al., 2021; Wong et al., 2023, see $D.1.1 for examples of synthesized programs). We evaluate these two strategies alongside combined CoT Code condition and direct-answer Base LM condition.
Evaluation Details Each item in the SpotterQA benchmark is tuple (gt, A,, I2, H1:1) containing question, answer, observed board, and history from the human experiment. Boards are represented as Numpy arrays (prompting details in SC.3). Since questions are independent given the history, sequences can be split up for efficient parallel processing. Accordingly, we are able to evaluate broad (but non-exhaustive) set of frontier LMs from Anthropic (Anthropic, 2025), Google (Co- manici & Team, 2025), Meta (Grattafiori et al., 2024; Meta AI, 2025), and OpenAl (OpenAI, 2024; 2025a;b:c). We query all models via the OpenRouter API with default parameters.
4.2. RESULTS
Fig. 3 summarizes the results of our SpotterQA evaluation; full details are provided in $D.1. We highlight three key findings:
Qusstion-answering abilities vary widely across models. As seen in Fig. 3a, accuracy varies widely across the 15 LMs tested, ranging from near-chance (52.5%; GPT-4o-mini) 92.8% (o3 mini). Notably, several models (o3, o4-mini, and GPT-5) meet or exceed mean human performance (92.5%). (See Table 3 for full results.)
Code generation consistently improves answering accuracy. Across models (Fig. 3b), we find that code improves SpotterQA by 13.2% absolute accuracy points over Base; combining code gen- eration with chain-of-thought (CoT Code) yields even greater 14.7% gains. A two-sided Mann- Whitney test confirms that these differences are significant (p < 0.001; see Fig. 17). Importantly, for many models, code generation substantially closes the gap between LMs and human perfor- mance: for instance. Claude 4 Opus improves from 86.8% (Base) to 94.4% (CoT + Code), and GPT-4.1 improves from 75.2% (Base) to 90.9% (CoT + Code). These results demonstrate that code generation helps LMs to produce more accurate, grounded answers.
LMs struggle with context-dependent questions. As shown in Fig. 3c, whereas human accuracy remains roughly consistent across simple (92.8%) and complex (91.9%) questions, LMs degrade significantly on complex questions (as defined in $4.1). For instance, GPT-4o's accuracy drops from 72.8% on simple questions to 60.4% on complex ones; similarly, Llama-4-Scout drops from 68.0% 54.0%. Code generation partially mitigates this gap, but even the best model (o3) still falls short of human performance on complex questions (87.4% vs. 91.9%). These results suggest that current LMS still struggle with pragmatic reasoning and context-dependen meanings.
Prior evaluations find that vision language models (VLMs) struggle with spatial reasoning on 2D grids, including Battleship boards (Grand et al., 2024). Accordingly, we serialized representations, following the predominant approach ARC-like tasks (Akyürek et al., 2024; Li et al., 2024; Wang al., 2024).

---

Published as a conference paper at ICLR 2026
4.3 CAPTAINQA: MODELING QUESTION-ASKING
In this section, evaluate the ability of LMs to play the Captain role in the full game setting. We compare a variety of Captain strategies that differ in how they select moves, ask questions, and decide whether to ask shoot (as formalized in $3.1). A summary is provided in Table 1.
Captain
Decision
Question (Q)
(M)
Random
Move
6,J ~ Unif(11, ...,,... 8))
Greedy
Move
arg max:,; sta(-
LM
PLM(
Haa)
PLM( at Haie) ang max ye EIG, Hid
PLM Hi:s)
Bayes-Q
Bayes-M
PLM Ha.r) Qaeer
arg max, by 5 2,, H1a))
Rayes-QM
Manes
Bayes-QMD
Mi (xx) up
(x--1
ge, Ac)
Table 1: Summary of Captain strategies. Random and Greedy are move-only baselines; LMM is pure language model, which the Bayes strategies build upon. Triple-dots indicates inheritance from the row above.
Experimental Details We evaluate each Captain strategy over 54 games (the 18 pre-sampled boards from the human experiment; $4.1, with random seeds per board). Each game enforces the same constraints the human setting: maximum of 15 questions and 40 moves. To control for answer quality, we fix the Spotter to GPT-5 (CoT + Code) for all strategies and set e = 0.1, calibrated from GPT-5's SpotterQA accuracy (64.2). Because each turn involves multiple API queries which must be made sequentially, we restrict CaptainQA evaluation to three representative LMs: Llama-4-Scout (small, non-reasoning). GPT-4o (large. non-reasoning), and GPT-5 (large, maasonnnn-ccpable)) We evaluate every combination of LM and Captain strategy, with the exception of Bayes-QMD, which we were not able to evaluate with GPT-5 due to cost (see Table for breakdown). For D Dayess we set y 0.95 to encode a minor discount for future action. For strategies that use LMs, the prompt includes the current board state and the full game history (see $C.2 for prompting details).
Captain Evaluation Metrics We evaluate Captains using five primary metrics that capture different
aspects of performance:
Targeting Score (F1): Overall metric of ship-sinking performance, balancing both precision and recall. This metric treats the board as binary classification task, where ship tiles correspond to the positive class and water tiles correspond to the negative class.
Move Count: The average number shots taken per game; equivalently, the average game length (max 40
moves; questions do not count towards the move count).
Questions Asked: The average number of questions asked per game (max 15).
Win Rate: A pairwise metric based on board- matched performance in simulated head-to-headd play. For each pair of Captains on the same board, the winner the one that sinks all ships in the fewest moves, with tiebreaking based on targeting score (F1). Since Captains do not play each other directly, this comparison is computed post-hoc over all pairs of games, averaging over boards.
EIG: The average expected information gain of questions asked. We use maximum possible EIG is (o.1. 0.531 bits.
0.1, meaning that the
4.3.1 RESULTS
Fig. 4 summarizes the results of our CaptainQA evaluation; full details are provided in $D.2. We highlight four key findings:
Incorporating Bayesian strategies brings weaker models up to super-human performance. As seen in Fig. 4a, the LM-only strategy shows a wide range of performance, with Llama-4-Scout achieving only 0.367 F1, while GPT-5 reaches 0.716. However, adding Bayesian question, move, and decision strategies (+Bayes-QMD significantly improves performance across all models (c.g.. Llama-4-Scout jumps 0.367 - 0.764 F1, GPT-4o 0.450 - 0.782 F1). Remarkably, with the full Bayesian model, both Llama-4-Scout and GPT-40 outperform both humans (0.82-0.83 win rate vs. humans) as well as the strongest LM (0.67 win rate vs. GPT-5), suggesting that Bayesian strategies can compensate for weaker LM capabilities (see win rates in Fig. 18). The LMs equipped with this full Bayesian model also outperform GPT-5 at a fraction of its cost (=11% % of GPT-5's cost for Llama- 4-Scout, and <355 for GPT-4o, Table 5) Notably, GPT-5 itself does not significantly benefit from Bayesian question or move selection, indicating that it may already be employing effective versions of these strategies internally.
7

---

Published as a conference paper at ICLR 2026
(a) Targeting sccres (F1) by Captain strategy.
(b) Maximizing EIG with Quaees
(c) Question frequency over game duration.
1.0
Targeing Seam (F1)
0.50
0.8
0.45
0.6
(8 0.40
190.00 0.88
0.4
0.30
0.25
Human
Randow
Groedy
Lt
+Bayyw--
+Bayessa
+Byyes-GM
Bayss CMD
0 QUieSOorTa Sart
Human
Baseline
GPT:5
Figure 4: CaptainQA key results. (a) Incorporating Bayesian strategies for questions (Quayss), moves (Masyes) and decisions (Deyyes) brings weaker LMs from near-rande rear-random performance super-human levels. (b) Sampling up to 10 questions with Qaaes yields higher EIG. (c) Daaes helps Llama-4-Scout and GPT-4o to spread out questions over time, more closely matching the behavior of humans and GPT-5.
Inference scaling yields more informative questions for models. As shown Fig. 4b, EIG scales with the number of candidate questions sampled under the Qayes strategy. Across models, we see EIG improvements of up to 0.227 bits per question (up to 94.2% of the info-theoretic ceiling). Additionally, QBayes significantly reduces the proportion of redundant questions (EIG O; Table 4) asked by Llama-4-Scout (18.5% + 0.2%) and GPT-4o (14.6% + 1.2%).. (We find that both humans and GPT-5 rarely ask redundant questions.) These findings illustrate how LMs including models like GPT-5 that already perform extensive test-time reasoning can further benefit from inference scaling techniques designed improve question quality.
Asking high-EIG questions is not sufficient to guarantee strong game performance. While QBayes consistently improves EIG, this does not consistently translate improved game perfor- mance. For instance, both Llama-4-Scout and GPT-4o see significant EIG gains with Q but their targeting scores improve only marginally (+0.021-0.026 F1). This suggests that weaker mod- els may not be able to effectively leverage information into accurate moves. In contrast, MBayes, which explicitly marginalizes over the implications of each question compute ny, provides more reliable mechanism for doing so.
Skilled players ask some questions first, but not all. As seen in Fig. 4c, both humans and GPT- 5 tend to ask several questions early in the game, but also reserve some questions for later turns. In contrast, weaker players (e.g., Llama-4-Scout) tend front-load all 15 questions- this myopic behavior is mitigated by introducing one-step lookahead (Dpayes). which leads to more balanced approach. Interestingly, stronger players (humans, GPT-5) ask fewer questions overall (8.0-8.2 vs. 14.1-14.9), indicating that they both gain more information per question (higher EIG; Table 4) and make more effective use of that information in their moves (higher F1; Fig. 4a).
5 GENERALIZED INFORMATION-SEEKIN GAMES
We extend our Bayesian strategies general family of information-sseking games from TextArena (Guertler et al., 2025). Here, we present results from the board game "Guess Who?" (see ŞE for full details). This game provides distinct testhed from Battleship, as it involves richer, object-relational semantics and requires more complex reasoning about entities and attributes (c.g., age, clothing, facial hair, etc.). As shown in Fig. 5, both GPT-4o and Llama-4-Scout's success rates improve significantly with QMaayes (GPT-40: 0.617 - 0.900; Llama- 4-Scout: 0.300 > 0.724). These results suggest frame- work successfully generalizes to information seeking environ- ments with combinatorial hypothesis spaces.
1.00
Rate
0.75
0.50
+ B
Bayes-M M
Bayes oM
Liama-4-Scon
GPT-4o
Figure 5: Guess Who? Our Bayesian strate- gies yield consistent improvements, replicat- ing the care findings from Bartlehiip.
8

---

Published as a conference paper at ICLR 2026
6 RELATED WORK, DISCUSSION, AND CONCLUSION
Expressing queries and hypotheses with programs. Several notable prior works use language- to-code support efficient probabilistic inferences (Ellis, 2023; Li et al., 2024; Piriyakulkij al., 2024; Wang et al., 2024; Wong et al., 2023). Our work integrates hypothesis-driven reasoning with other recent approaches for planning and rational agent behavior (Chiu al., 2023; Curtis et al., 2025: Ying et al., 2024: 2025).
Eliciting user preferences and clarifying ambiguity. Asking informative questions is critical for many user-facing applications of LMs; recent approaches consider structured prompting (Li al., 2023), entropy reduction (GX-Chen al., 2025; Hu al., 2024; Mazzaccara et al., 2024; Piriyakulkij et al., 2023; Rao & Daumé III, 2018; Yu et al., 2020; Zhang & Choi, 2023), Bayesian inference (Handa et al., 2024; Qiu et al., 2025), and constraint satisfaction (Li et al., 2025).
Human information-seekingg and resource rationality. Our work is broadly informed by "resource rational" accounts that describe how human behavior is shaped by cognitive constraints (Anderson, 1990: Chater & Oaksford, 1999; Icard, 2025; Leider et al., 2025; Lieder & Griffiths, 2020). In information-secking tasks, both children and adults greedy heuristics (Markant et al., 2016; Meder al., 2019; Ruggeri et al., 2016), consider only few hypotheses Vul et al., 2014), and prefer queries that yield easily interpretable information (Cheyette et al., 2023). These ideas motivate our modeling approach, which emphasizes greedy, sample-based strategies over exact planning and inference.
time (Klayman & Ha, 1989;
6.1 LIMITATIONS AND FUTURE WORK
Collaborative Battleship gives rise to many rich pragmatic behaviors. While discussed in $$ A.3 and A.4, in general, these are not explicitly modeled; incorporating techniques based the rational speech acts (RSA) framework (Frank Goodman, 2012; Hawkins et al., 2017: 2023) could yield agents capable of more sophisticated pragmatic reasoning. In particular, people are highly sensitive to the reliability of information (Harris & Corriveau, 2011; Sperber et al., 2010), as reflected inter- actions between human players (e.g., Figs. 14 and 15). In place of fixed e, a more robust approach would be to infer & to account for the differences reliability across individual Spotters. Analo- gously, in scientific settings, agents may need adapt to different levels of aleatoric uncertainty (Hüllermeier & Waegeman, 2021).
Our Bayesian strategies rely on the ability efficiently draw conditional samples s p(s x; H) from a generative "world model." While implementable by hand in a domain like Battleship, in more general settings, we may wish to learn generative model world states represented as code (e.g., via model synthesis architectures (MSA): Wong et al., 2023; 2025) or images; (c.g., via VAEs or diffusion; Alonso et al., 2024; Ha Schmidhuber, 2018). Finally, building agents that collaborate effectively with people is increasingly important (Boiko et al., 2023; Noti et al., 2025); Collaborative Battleship provides an ideal setting for studying human-agent interactions.
6.2 CONCLUSION
In this work, presented a comparative evaluation of human and agent information-seeking We introduced a cognitively-inspieed Collaborative Battleship task designed to replicate the core components of Bayesian Experimental Design (BED), including forming hypotheses about latent variables, asking and answering questions, and leveraging context-dependent information to in- form actions. Our behavioral study provides a rich, multimodal dataset of human interactions, BATTLESHIPQA, enabling systematic comparison with model performance.
Our results highlight both progress and gaps: while smaller models like Llama-4-Scout and GPT-4o struggle to explore and act coherently, larger reasoning models like GPT-5 approach or even sur- pass human-level performance at steep resource costs. Notably, humans themselves are not Bayes- optimal reasoners; in general they do not ask use of all available resources. Nevertheless, people are remarkably good at asking useful questions, providing contextually- grounded answers, and making well-informed guesses. Prioritizing strate- gies that are resource rational is therefore essential if we want to build agents that scale beyond benchmarks to collaborate with people on real-world problems.
questions make exhaustive

---

Published as a conference paper at ICLR 2026
AUTHOR CONTRIBUTIONS
Gabriel Grand Research conceptualization. narrative development, modeling (design and im- plementation), human experiments (design and supervision), analysis (Captain and Spotter experi- ments), figure-making, writing, math and formalization.
Valerio Pepe* Research conceptualization, narrative development, modeling (design and imple- mentation), human experiments (design, implementation, and execution), analysis (Captain and Spotter experiments), writing, TextArena experiments.
Joshua B. Tenenbaum
Senior mentorship, research conceptualization, narrative development, hu- man experiments (design and supervision).
Jacob Andreas Senior mentorship, research conceptualization, narrative development, human ex- periments (design and supervision), analysis of results.
*Equal contribution, co-first authorship.
ACKNOWLEDGMENTS
We thank Brenden Lake, Tomer Ullman, Robert Hawkins, Judy Fan, Lionel Wong, Tan Zhi-Xuan, Belinda Li, Alexis Ross, Sam Cheyette, Guy Davidson, and Graham Todd for helpful discussions and feedback.
The authors gratefully acknowledge support from the Siegel Family Quest for Intelligence, the MIT- IBM Watson AI Lab, the FinTechAI@ CSAIL initiative, the Intel Corporation, AFOSR, DARPA, ONR, and the National Science Foundation (NSF) under grants CCF-2217064 and IIS-2238240. G.G. is additionally supported by a NSF Graduate Research Fellowship under Grant No. 2141064. J.B.T. additionally supported by AFOSR, ONR Science of AI, and Siegel Family Endowment. J.A. is additionally supported by a Sloan Research Fellowship. Any opinions, findings, and conclusions or recommendations expressed this material those of the author(s) and do not necessarily reflect the views of sponsors.
ETHICS STATEMENT
We acknowledge that our research involves human participants and has been conducted with the utmost consideration for ethical standards. The study protocol was reviewed and approved by the MIT Committee on the Use of Humans as Experimental Subjects (COUHES), which serves as the Institutional Review Board (IRB) our institution, ensure compliance with the Ethical Principles and Guidelines for the Protection of Human Subjects of Research, including the Belmont Report principles of respect for persons, beneficence, and justice. All participants provided informed con- sent, and their privacy was protected throughout the study. We are committed to ensuring that our findings are used responsibly and for the benefit of society.
REPRODUCIBILIIT STATRMENT
We strive to make research reproducible by providing detailed descriptions of methods, datasets, and experimental procedures. We encourage other researchers to replicate our findings and build upon our work. All code and data used in experiments, including the full BATTLESHIPQA dataset, are available at gabegranc gi t io/bbttteeshpp.p
USE OF AI ASSISTANCE
We acknowledge the use of Al tools the preparation of this manuscript. Specifically, we utilized language models (LMs) to assist with grammar and style editing, literature review, preparation of figures, general coding assistance, and other tasks. We have reviewed and edited the content to ensure accuracy and clarity, and we take full responsibility for the final version of the manuscript.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Ekin Akyürek, Mehul Damani, Adam Zweiger, Linlu Qiu, Han Guo, Jyothish Pari, Yoon Kim, and Jacob Andreas, The Surprising Effectiveness of Test-Time Training for Few-Shot Learning, 2024. URL https://arxivv.rrg//aaa. 0472/7779.
Abdullah Almaatouq. Joshua Becker, James P. Houghton, Nicolas Paton, Duncan J. Watts, and Mark E. Whiting. Empirica: virtual lab for high-throughput macro-level experiments. Behavior Research Methods, 53(5):2158-2177 2021. ISSN 1554-3528. doi: 1..7788/11322--02--01155
URL htwps:tt/oooo //dpii org/16. 3758/s1 3428 020-01535-9.
Eloi Alonso, Adam Jelley, Vincent Micheli, Anssi Kanervisto, Amos J. Storkey, Tim Pearce, and François Fleuret. Diffusion for world modeling: Visual details matter in atari. In Amir Glober- sons, Lester Mackey, Danielle Belgrave, Angela Fan. Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference Neural Information Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, De- cember 10 15, 2024, 2024. URL http: /ttp://aapeee.ee/e/ misapprrs.iiss.... cctpcpcr.rppp/...ce.e saaper_fillss melles/paper/02// html.
(6bdde0373dd5344500 t-
John R. Anderson. The adaptive character of thought. Lawrence Erlbaum, 1990.
Anthropic. Claude opus 4 & claude sonnet 44--sstte system card, 2025. URL https: http::///ww.atthrpp
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Leurning, 47:235-256, 2002. doi:
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe Le, and Charles Sutton. Program Synthesis with Large Language Models, 2021. URL htttss://axxi..rrrgrrr /ttp://www..r///////.....0
Danii A. Boiko, Robert MacKnight, Ben Kline, and Gabe Gomes, Autonomous chemical research with large language models. Nature, 624(7992):570-578, 2023. ISSN 1476-4687. doi: 10.103 011111566------00 000000072------00000
URL https: http://wwwww..we.eeee/////. nawure..eee.aam Publisher: Nature Publishing Group.
Kathryn Chaloner and Isabella Verdinelli. Bayesian Experimental Design: A Review. Statistical Science, 10(3), 1995. ISSN 0883-4237. doi: 10.1214/s/1 uclid. wcl.dd.orr..bburrrass/ttttttiiia 1-Design Aeeiinnn--Reee////eeee-- http://ewww..11//////111111 /214/s//1177009933 full.
URL ht httt::://prjottttt
/vl/ une- 1ouuue-110/0
imenta
N. Chater and M. Oaksford. Ten years the rational analysis cognition. Trends Cognitive Sciences, 3(2):57-65 65, 1999. ISSN 1879-307X. doi: 10.0066613344-6661199911110111
Samuel J. Cheyette, Frederick Callaway, Neil R. Bramley,Jonathan Jonathan D. Nelson, and Josh Tenenbaum. People seek easily interpretable information. Proceedings of the Annual Meeting of the Cognitive Science Society, 45(45), 2023. URL https:///sschoaarshhppp org/ tem/ 5sm2b484.
Justin Chiu, Wenting Zhao, Derek Chen, Saujas Vaduguru, Alexander Rush, and Daniel Fried. Sym- bolic planning and code generation for grounded dialogue. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Lan- guage Processing, pp. 0436-7 Singapore, 2023. Association for Computational Linguistics. doi: 10. 10.18655/w1//0223.mm// mainlp-mmii.460.. URL htttps://aclantholloe org 20rrg//222..oo ..002..ee0. wttg://2..e...mmmmm..... n60
Francois Chollet, Mike Knoop, Gregory Kamradt, and Bryan Landers. ARC Prize 2024: Technical Report, 2024. URL https: www.rrwwi.oogg/r//eooee 2462.04624..
Gabriel Comanici and the Gemini Team. Gemini 2.5: Pushing the frontier with advanced rea- soning, multimodality, long context, and next generation agentic capabilities. ArXiv preprint, 06261.
abs/2507.06261 2025. URL http:s:///xxxvvo//a/.eee

---

Published as a conference paper at ICLR 2026
Aidan Curtis, Hao Tang, Thiago Veloso, Kevin Ellis, Joshua Tenenbaum, Tomás Lozano-Pérez and Leslie Pack Kaelbling. LLM-Guided Probabilistic Program Induction for POMDP Model Estimation. ArXiv preprint, abs/2505.02216, 2025. URL http::://aaxivvorrgg... wwwp/br/////.././/// 022 16.
Arnaud Doucet, Nando de Freitas, and Neil Gordon. Sequential Monte Carlo Methods in Practice. Springer Science & Business Media, 2001. ISBN 978-0-387-95 146--1
Kevin Ellis. Human-lit feo-shot learning via bayesian reasoning over natural language. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Informa- tion Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, wtt.ffffleeeeee//eeeeeer hat02////aa///aabbbbbb 2aa9b1 (aabb18b9bbbbbba html.
2023. URL httt:::/pppprrs.n..e nips.
Michael C. Frank and Noah D. Goodman. Predicting Pragmatic Reasoning in Language Games. Science, 336(6084):998 998, 2012. doi: 10. 10.1126/science. 1218633. URL https: / /ww..ccien e, http//oo/11..11//scciioo of Science.
scienc
1218633. Publisher: American Association for the Advancement
Juraj Gottweis, Wei-Hung Weng, Alexander Daryin, Tao Tu, Anil Palepu, Petar Sirkovic, Artiom Myaskovsky, Felix Weissenberger, Keran Rong, Ryutaro Tanno, Khaled Saab, Dan Popovici, Jacob Blum, Fan Zhang, Katherine Chou, Avinatan Hassidim, Burak Gokturk, Amin Vahdat, Pushmeet Kohli, Yossi Matias, Andrew Carroll, Kavita Kulkarni, Nenad Tomasev, Yuan Guan, Vikram Dhillon, Eeshit Dhaval Vaishnav, Byron Lee. Tiago R. D. Costa, José R. Penadés, Gary Peltz, Yunhan Xu, Annalisa Pawlosky, Alan Karthikesalingam, and Vivek Natarajan. Towards an AI co-scientist, 2025. URL https: /aaxivv...iv/////a www.ooggg/a............ /atp//2522222 18864.
Gabriel Grand, Valerio Pepe. Jacob Andreas, and Joshua B. Tenenbaum. Loose LIPS Sink Ships: Asking Questions in Battleship with Language-Informel Program Sampling, 2024. URL https: //arxiv.org//bs//20000 19471.
Andrew Grattafiori, Abhimanyu Dubey, and others. The llama 3 herd of models. ArXiv preprint, abs/2407.21783, 2024. URL h/tps://arxiv http:///xii.oorr/as//////// orggabs//407. 21783.
Leon Guertler, Bobby Cheng, Simon Yu, Bo Liu, Leshem Choshen, and Cheston Tan. TextArena, 2025. URL https:///axxi http://org/ab//////ee//// 11442.
Todd Gureckis and Doug Markant. Active Learning Strategies in a Spatial Concept Learning Game. Proceedings of the Annual Meeting of the Cognitive Science Sociery, 31(31), 2009. URL https: / //escholarshipp or org/uc/ / teme 55b5m1 16.
Anthony GX-Chen, Dongyan Lin, Mandana Samiei, Doina Precup, Blake A. Richards, Rob Fergus, and Kenneth Marino. Language Agents Mirror Human Causal Reasoning Biases. How Can We Help Them Think Like Scientists?, 2025. URL https://arxiiv www.xivorrg/bb//5ee00 05612/5555........ 09614.
David Ha and Jürgen Schmidhuber. World Models. ArXiv preprint, abs/ abs/1803.10122, 2018. URL https: http://araai..org///////..000 1012..
Kunal Handa, Yarin Gal, Ellie Pavlick, Noah Goodman, Jacob Andreas, Alex Tamkin, and Be- linda Z. Li. Bayesian Preference Elicitation with Language Models, 2024. URL https:
www.xxi.orggass///o 2400. 05534..
Paul L.
Harris and Kathleen H. Corriveau. Young children's selective trust in informants. Philo- sophical Transactions of the Royal Society B: Biological Sciences. (166(1167):117-111833 2011. ISSN 0962-8436. doi: 00.1098/ssth.20000332. URL https: http::://mcc.cce/ee ncbi. nlm. nih. www...i...........eeeeeeeeee.eee gov/artic 1es/PMC30499991/.
Robert D. Hawkins, Mike Frank, and Noah D. Goodman. Convention-formatton in iterated reference games. Cognitive Science. 2017. URL https: / //www//wwww///////e///// semanticscholart http://ooaar..reeepppe///e/eeeee
https::/www.emmmtticcssset
on-formationninn rere oraere/eeeeesosoooooooooorrrrrra 667F97578834cbbb394
12

---

Published as a conference paper at ICLR 2026
Robert D. Hawkins, Michael Franke, Michael C. Frank, Adele E. Goldberg, Kenny Smith, Thomas L. Griffiths, and Noah D. Goodman. From partners to populations: A hierarchical Bayesian account of coordination and convention. Psychological Review, 130(4):777-0016 2023. ISSN 1939-1471, 0033-295X. doi: 10.1037/rex0000334. URL https: /doii www.iiappp.o............o.. http://i........////////////// -1837/rev0000348.
Zhiyuan Hu, Chumin Liu, Xidong Feng, Yilun Zhao, See-Kiong Ng. Anh Tuan Luu, Junxian He, Pang Wei Koh, and Bryan Hooi. Uncertainty of Thoughts: Uncertainty-Aware Planning Enhances Information Seeking in Large Language Models, 2024. URL https://arxiv, wttp://.rggbbb//22/.2../ 3271.
Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning: an introduction concepts and methods. Machine Learning, 110(3):577-500 2021. ISSN 1573- 0565. doi: 10. 10.10077$109944-01--05500 46-3.
URL http::ttt//iiorrg///eee/// http:///00000/0009900000000000
Thomas Ieard. Resource Rationality, 2025. URL https://philarchhin http:/hhll.rcci....oogr/////ra/ org/rec/ICARRT.
Peter Jansen, Mare-Alexandra Côté, Tushar Khot, Erin Bransom, Bhavana Dalvi Mishra, Bod- hisattwa Prasad Majumder, Oyvind Tafjord, and Peter Clark. Discoveryworld: A virtual environ- ment for developing and evaluating automated scientific discovery agents. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024. URL http: /ttp::://pppperr/ nips. cc/ paper patppppaaeeepppeeeallaa wttp///llls//pee/////// http://ppppe//2///////a//// 13836 F25182394531 htt.:///seeeetteeaaaocaooooaarra
Batrrssssss__add_eeenennrrrrr -ranckkksss__ak..o. html.
Nan Rosemary Ke, Danny P. Sawyer, Hubert Soyer, Martin Engelcke, David P. Reichert, Drew A. Hudson, John Reid, Alexander Lerchner, Danilo Jimenez Rezende, Timothy P. Lillicrap. Michael Mozer, and Jane X. Wang. Can foundation models actively gather information in interactive environments to test hypotheses?, 2024. URL https: //axxiv org/abs/ 2at.s//411..63333
Joshua Klayman and Young-won Ha. Hypothesis testing in rule discovery: Strategy, structure, and content. Journal of Experimental Psychology: Learning, Memory, and Cognition, 15(4):596, 1989. Publisher: American Psychological Association.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Sanmi Koyejo, Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: An- nual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022. URL http: /ttp//aapppaa///e//ee/eee/eeeeee nips. cc/ sacp/ppp__fii __il 1200966e111119911111 -arere/ctoe---ebbaar-t---oooooo Abstract--onference html.
Falk Leider, Frederick Callaway, and Thomas Griffiths. The Rational Use of Cognitive Resources, 2025. Lof__Coonitive_eesourrrr
Belinda Li, Alex Tamkin, Noah Goodman, and Jacob Andreas. Eliciting Human Preferences with Language Models, 2023. URL https://arxiv. /ttp://iiii.rgg//////33// 11589.
Belinda Z. Li, Been Kim, and Zi Wang. QuestBench: Can LLMs ask the right question to acquire information in reasoning tasks? ArXiv preprint, abs/2503.22674, 2025. URI. https: //axxiv.
org/abs/ htgg/abb/503... 22674.
Wen-Ding Li, Keya Hu, Carter Larsen, Yuqing Wu, Simon Alford, Caleb Woo, Spencer M. Dunn, Hao Tang, Michelangelo Naim, Dat Nguyen, Wei-Long Zheng, Zenna Tavares, Yewen Pu, and Kevin Ellis. Combining Induction and Transduction for Abstract Reasoning. 2024. URL https:
//arxiv.co wwwpxxv.org/abs/2220 22222222.. 02272.
Falk Lieder and Thomas L. Griffiths. Resource-rational analysis: Understanding human cognition as the optimal use of limited computational resources. Behavioral and Brain Sciences, 43:e1, 2020. ISSN 0140-525X, 1469- 1825. doi: 10.10177500149255119000XXXX URL httpp://www haantrrdgge..r/cccoe/r/roo////// 900.deefff...///0000600900000000
13

---

Published as a conference paper at ICLR 2026
Dennis V. Lindley. On measure of the information provided by experiment. Annals of Mathe- matical Statistics, 27:986-1005, 1956. doi: (t..214/amm/1117778800
Chris Lu, Cong Lu, Robert Tjarko Lange, Jakob Foerster, Jeff Clune, and David Ha. The AI
Scientist: Towards Fully Automated Open-Ende Ended Scientific Discovery, 2024. URL https:
wlwaaii..rrgabbs///...e 06292.
David JC MacKay. Information-base objective functions for active data selection. Neural Compu- lation, 4:590-604, 1992. doi: 10. 162/neco. 1992.4.4.590.
Bronislaw Malinowski. The meaning of meaning: a study of the influence of language upon thought and of the science of symbolism, volume 29. K. Paul, Trench, Trubner & Company, Limited, 1927.
Doug Markant and Todd Gureckis. Does the utility of information influence sampling behavior? Proceedings of the Annual Meeting of the Cognitive Science Society, 34(34), 2012. URL https: / //escholarshit org/uc/ / tem/ 0fz3d3mw.
Doug Markant and Todd Gureckis. preference for the unpredictable over the informative during self-directed learning. Proceedings of the Annual Meeting of the Cognitive Science Society, 36 (36), 2014. URL
Douglas B Markant, Burr Settles, and Todd M Gureckis. Self-directed learning favors local, rather than global, uncertainty. Cognitive science, 40(1):100-120, 2016. Publisher: Wiley Online Li- brary.
Davide Mazzaccara, Alberto Testoni, and Raffaella Bernardi. Learning to Ask Informative Ques- tions: Enhancing LLMs with Preference Optimization and Expected Information Gain. ArXiv preprint, ab4/2406.17453,, 2024. URL /tttps://axxiv http://axxiivoorra///////// wwtp/rr/////......////// 17453.
Bjöm Meder, Jonathan D Nelson, Matt Jones, and Azzurra Ruggeri. Stepwise versus globally opti- mal search in children and adults. Cognition, 191:103965, 2019. Publisher: Elsevier.
Meta AI. The Llama herd: The beginning of new era of natively multimodal AI innovation, 2025. URL https://aat www..
Learning, 2025. URL www../attaaammmeeeem cww/blog///ccocccccccccccc.oooo.
Gali Noti, Kate Donahue, Jon Kleinberg, and Sigal Oren. Al-Assisted Decision Making with Human 13062.
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowyez, Maarten Bosma, David Luan, Charles Sutton, and Au- gustus Odena. Show Your Work: Scratchpads for Intermediate Computation with Language Mod- cls, 2021. URL https: //axxiv////iiv.a//// wtwpla/..rgg////////eeeee http://bb/211...0000
OpenAl. GPT-4o system card. ArXiv preprint, abs/2410.21276, 2024, URL https:://///x 0bs/2440..2226.
OpenAl. Introducing GPT-4.1 in the API, 2025a. URL http:://ogeeaai.ccm/m//eeee///e
OpenAl. GPT-5 system card, 2025b. URL https::/cche https::/cdd.ooenai.ccmmm
pdf.
OpenAl. OpenAl o3 and o4-mini system card, 2025c. URL httptttt/opeeaiiccoom
4-mini system-cardd/..
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Ad- vances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022. URL http: / / pappps.pprsssse nips. cctpcccp_aaaaaaeeeeeee feaper_filest files/ www.ffflleeperreeeeeee 64a7391 4F58885a001 731 -ow.raettttttttttttt-oooooooooo Abstract-Conference html.
helle/paper/222//hss///// (atpder/222//hahhhhe htthh//beedde55eee
14

---

Published as a conference paper at ICLR 2026
Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of markov decision processes. Mathemattics of Operations Research, 12(3):441-455 1987. ISSN 0364765X, 15265471. URL /t//staabee/39997/555
Top Piriyakulkij, Cassidy Langenfeld, Tuan Anh Le, and Kevin Ellis. Doing experiments and revis- ing rules with natural language and probabilistic reasoning. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Ad- vances in Neural Information Processing Systems 38: Anmual Conference on Neural Information Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024. URL
nips. cc/ pece/pppr__ff__ www.ffllleppppeeee faaper_fileesppaper//2//////// / /ttp://aaaaa.1113333000000006165 sa3bee33--ibstrrct--oofff
html.
Wasu Top Piriyakulkij. Volodymyr Kuleshov, and Kevin Ellis. Active Preference Inference using Language Models and Probabilistic Reasoning, 2023. URL https::/arxxv..orgg org. art..r///aa/....////// 2009.
Gabriel Poesia, David Broman, Nick Haber, and Noah D. Goodman. Learning formal mathematics from intrinsic motivation. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024. URL http:://tpppeeeee 6af9ca Abstrac
ips. wwtpppcr_ppppeeeeeceeeeeeeeeeeee http/pppprfless___////__rar__ /aapae//000///aaaa11000000000010 t-Conference. html.
Linlu Qiu, Fei Sha, Kelsey Allen, Yoon Kim, Tal Linzen, and Sjoerd van Steenkiste. Bayesian Teach- ing Enables Probabilistic Reasoning in Large Language Models. ArXiv preprini, abs/2503.17523, 2025. URL https://arxiv arggabss/5003. 17523.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D. Manning. Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model secretly a reward model. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL http: / http//aappprsseae/eee nips. cc/ paapprrfilessssseppepppppaasseee http://appe//222////// hattaasshh/8bbbeed5555 6647844fe30bbee6cc7- -awere--t-tttaa-----eeeeeee htmll.
Tom Rainforth, Adam Foster, Desi R. Ivanova, and Freddie Bickford Smith. Modern Bayesian Experimental Design, 2023. URL https://arxivv www.orgg///////ee 234....55...
Sudha Rao and Hal Daumé III. Learning to ask good questions: Ranking clarification questions using neural expected value of perfect information. In Iryna Gurevych and Yusuke Miyao (eds.), Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Voluee 1: Long Papers), pp. 2737-2746, Melbourne, Australia, 2018. Association for Computational Linguisties. doi: 1153/661/11P1 12555 URL httpt:::/aclaattttttoe
htte::/acllaninn awo.aaannnnntooooy.oooooo woo.laoooooo.oog//11.1. org/P18-1255.
Anselm Rothe, Brenden M. Lake, and Todd M. Gureckis. Question asking as program generation. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1046-1055, 2017. URL https: httpss///ococeeieeeeeeeeee htwp:r/reeeeiinneeeenie.eeeeeese mmerrip.ccc/pppe. /2017 /aa////aahh/aaa 24681 922922252291335522222 F4 Abstractsstttttt..o. html.
Anselm Rothe, Brenden M. Lake, and Todd M. Gureckis. Do People Ask Good Questions? Com- putational Brain & Behavior, 1(1):69-89, 2018. ISSN 2522-0861, 2522-087X. doi: 10.1007/s4 2 2113-018-0005-5, URL
sprikger..nnn.ecmm com/ 0 1807///42113-088-90005
Anselm Rothe, Brenden M. Lake, and Todd M. Gureckis. Asking goal-oriented questions and learning from answers. Proceedings of the Annual Meeting of the Cognitive Science Society, 41(0), 2019. URL https::/eschooaarr
org/oc//itceeooooooooo 04q6z1mq.
Azzurra Ruggeri, Tania Lombrozo, Thomas L Griffiths, and Fei Xu. Sources of developmental change in the efficiency of information search. Developmental psychology, 52(12):2159, 2016. Publisher: American Psychological Association.
15

---

Published as a conference paper at ICLR 2026
Samuel Schmidgall, Yusheng Su, Ze Wang, Ximeng Sun, Jialian Wu, Xiaodong Yu, Jiang Liu, Michael Moor, Zicheng Liu, and Emad Barsoum. Agent Laboratory: Using LLM Agents as Research Assistants, 2025. URL https: //tx:v////xivv///aa org /btg////b//1/11/1/ 04227.
C. E. Shamnon. A mathematical theory of communication. The Bell System Technical Journal, 27(3):379-422 423, 1948. ISSN 0005-8580. doi: 10. N0.1002/j..538. 7305. 1948.tt11138..... URL
https://ieeexplore ieee. www..eeeeeeee.eeeeeeeooeooooeeee http//docmen///7220000
Dan Sperber, Fabrice Clément, Christophe Heintz, Olivier Mascaro, Hugo Mercier, Gloria Origgi, and Deirdre Wilson. Epistemic Vigilance. Mind & Langnage. 25(4):359-393, 2010. ISSN
1468-0017. doi: 10. 10.1111/j. 468-401811111 2017.200 201 0.000.011. 0.011.999. 394.x.
URL https: /onlineli
brary wi wiley.
1111/j 1468 0017. 2010.1 01394. _eprint:
Press, 2018. URL http://ol.i.iooooo.....oooooooo/
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction (2nd ed.). MIT
net/book/ tteek/tthhhttee ttt/ttheehooboo boobbbookooooo html.
Edward Vul, Noah Goodman, Thomas L Griffiths, and Joshua B Tenenbaum. One and done? Opti- mal decisions from very few samples. Cognitive science, 38(4):599-633) 2014. Publisher: Wiley Online Library.
Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah D. Goodman. Hypothesis search: Inductive reasoning with language models. In The Twelfth International Con- ference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenRe- view.net, 2024. URL https: /tottprv//ppereviieww wttpe/reeeweeeeeeorrneee nett/Forummdd--7UU1GG
Ruoyao Wang, Peter Jansen, Mare-Alex Côté, and Prithviraj Ammanabrolu. ScienceWorld Is your agent smarter than 5th grader? In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Process- ing. pp. 11279-11229 1299.. Abu Dhabi, United Arab Emirates. 2022, Association for Computational Linguistics. doi: 11653/v1/2022// wwtp:/22mmmlmmmii.m77.. main.775. URL https: http:///aaaaaahhoooo org/ 202
2. emmnlp-main 775.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoe V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NewrlPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022. URL http: http:/ppppr....ip..... pcpppppprrrniiipscpppppp.perr httec/ppprreeeeeeeeeeeeeeeepeeee willes/paper/2022/haaaa d560961 3f24ecf 4f aabaaf/llbbbbbba---srttttt-ooooo .tml..
Lionel Wong, Gabriel Grand, Alexander K. Lew, Noah D. Goodman, Vikash K. Mansinghka, Jacob Andreas, and Joshua B. Tenenbaum. From Word Models to World Models: Translating from Natural Language to the Probabilistic Language of Thought, 2023. URL https://arxiv.orr abs/2306. 12672.
Lionel Wong, Katherine M. Collins, Lance Ying, Cedegao E. Zhang, Adrian Weller, Tobias Gersten- berg, Timothy O' Donnell, Alexander Lew, Jacob Andreas, Tyler Brooke-Wilson and Joshua B. World Cognition as On-Demand Synthesis of Probabilistic Mod- cls. Proceedings of the Annual Meeting of the Cognitive Science Society, 47(0), 2025. URL https://escholarship.ooom www.oorg////eeeenee tem/ 4j38w2tg.
Tenenbaum. Modeling Open-World
Jianzhu Yao, Kevin Wang. Ryan Hsieh, Haisu Zhou, Tianqing Zou, Zerui Cheng, Zhangyang Wang, and Pramod Viswanath. SPIN-Bench. How Well Do LLMs Plan Strategically and Reason So- cially?, 2025. URL https: //axivv hrrg/bbs/2500 12349.
Lance Ying, Tan Zhi-Xuan, Lionel Wong, Vikash Mansinghka, and Joshua Tenenbaum. Grounding Language about Belief in a Bayesian Theory-of-Mind. ArXiv preprint, abs/2402.10416, 2024. URL hnttps://arae http:://aaxxvvvvoaa////////
10416.
Lance Ying. Ryan Truong, Katherine M. Collins, Cedegao E. Zhang, Megan Wei, Tyler Brooke- Wilson, Tan Zhi-Xuan, Lionel Wong, and Joshua B. Tenenbaum. Language- Informedd Synthesis of Rational Agent Models for Grounded Theory-of-Mind Reasoning On-The-Fly, 2025. URL
https://arxiv. www.:orgg/bbb/aaseeeo 16755.
16

---

Published as a conference paper at ICLR 2026
Lili Yu, Howard Chen, Sida I. Wang, Tao Lei, and Yoav Artzi. Interactive classification by asking informative questions. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault (eds.), Proceedings of the 58th Anmual Meeting of the Association for Computational Linguisties, pp- 2664-2680, Online, 2020. Association for Computational Linguistics. doi: 1/.260 cl-main.237. URL https:://ccee httts:://eclannhooooo.o///////// acl-main..mmmmmmmmmm 237.
Michael J. Q. Zhang and Eunsol Choi. Clarify When Necessary: Resolving Ambiguity Through Interaction with LMs, 2023. URL httpp:://arxxia org/ ab1/2311 09469.
17

---

Published as a conference paper at ICLR 2026
Appendix
Table of Contents
Battleship
Extended Game Description and Prior Work
A.2 Human Study Details
20
A.3 BATTLESHIPQA Dataset
22
A.4 Illustrated Examples
24
B Sequential Monte Carlo Approximation
28
Prompt Library
29
Shared Components
29
C.2 Captain Prompt
................................
30
C,3 Spotter Prompt
31
D Evaluations
33
D.1 SpotterQA Evaluations
33
D.2
CaptainQA Evaluations
38
E
Guess Who? Experiment
42
E.1
The Guess Who? Game
42
E.2
Example Characters
42
E.3
Modeling QA Behavior
43
E,4
Experimental Details
43
E.5 Results
43
Guess Who? Prompts
18

---

Published as a conference paper at ICLR 2026
A BATTLESHIP
A. EXTENDED GAME DESCRIPTION AND PRIOR WORK
Our environment draws inspiration from the cognitive science literature, where Battleship-lkke tasks have previously been utilized to study human information-seekinn behavior. In prior work, single- player participants viewed partially-reveale game boards and decided what tiles to reveal (Gureckis & Markant, 2009; Markant & Gureckis, 2012; 2014) or what questions to ask (Rothe et al., 2017; 2018; 2019). In particular, Rothe et al. developed a novel approach where individual questions for specific intermediate game states were elicited from participants and translated into programs in a domain domain-speciffe specific language (DSL) in order to compute various formal characteristics, such as the expected information gain (EIG), minimum description length (MDL), and answer type (Boolean, number, color, etc.). A log-linear model was fit to human data in order to determine relative feature importance and to score the likelihood of questions sampled from generative grammar defined over the DSL.
Collaborative Battleship In our Collaborative Battleship game (Fig. 1). players alternate between two roles: the Captain must efficiently navigate explore/exploit tradeoffs in order to gain information about the board through questions and actions, while the Spotter must provide grounded answers to (possibly ambiguous) questions given full visibility of the board. Games start from blank board; at every turn, the Captain chooses whether to (a) reveal a tile by "shooting" or (b) ask a question.
When question is asked, the Spotter- whoo sees the full board-is prompted to answer it. Captains are given a limited budget of 15 questions and 40 shots, which under mild assumptions sufficient to sink all ships. The game ends when either all ships are sunk (team win) the Captain exhausts their shot budget (team loss), Further details about the game rules, interface, and data collection are provided in $A.2.
Key methods contributions Relative to prior studies, our work extends the Battleship paradigm in several key dimensions.
(1) Full multi-turn games: Prior work was limited to one or two-turn snapshots; here, we simulate full games consisting of interleaved sequences of up to 40 moves and 15 questions. (2) Two-player setting: In the multi-turn setting, players need to receive real-time answers to their questions; to facilitate this interaction loop, we introduce a second player to act as "Spotter," detailed above. (3) Python programs: In prior work, question-meanings were manually translated into programs. While follow-up work from Grand et al. (2024) proposed using LMs to automate this process, programs were still restricted questions with Python programs, which are both more expressive and casier in practice for LMs to generate. (4) State space complexity: Prior work used small 6 6 boards; we expand to 8 x boards, ships and position combinations and make question-asking more integral to which allow for more ships
hand- engineered DSL. Here, we represent
skilled play.
Information Bottleneck There is also one key aspect in which our setting is intentionally more restricted. Prior work placed no formal restrictions on questions; in principle, this meant that players could ask questions like, "What are the coordinates of all the ships?"2 Rather than attempt to detect such questions in real-time, we instead simply restrict the Spotter to answer with "Yes" or "No." As discussed in $3, this rule acts as an information bottleneck that limits the channel capacity. While less open-ended than the original setting, this approach is much more directly-enforcent which is critical in our setting where human players are incentivized with real monetary rewards ($4.1) 1), and where teams can and do form ad-hoc conventions across rounds.
"To discourage "rame-breaking" questions, Rothe et al. (2017) instructed participants to only ask questions that could be answered with single word. Nevertheless, there are many ways of constructing nominally "one- word" answer that encodes the game state (e.g., RedB BedB/B3Purmy FFF7..) Since the language of such encodings is undecidable, we instead opt to enforce binary information bottleneck.
19

---

Published as a conference paper at ICLR 2026
A.2
HUMAN STUDY DETAILS
Captain
Spotter
Round
00:51
doage
Miver
Aemare Slace
Novel Laft
Sto
Coolee
Mine
Couadr
Coeee
Nockay mociooe
Yorre Rocaaaa Turcoe pooaatie Touce cumtio
Ceutart (ii touthin
Tax gundica srraiing
Mort
Figure 6: User interface for our Collaborative Battleship experiment, which evaluates information-scckinn in two-player synchronous dialogue environment. The Captain must choose between taking actions and asking questions given limited visibility, while the Spotter sees the whole board, but can only respond with Yes/No. order play human-level, an agent must incorporate grounded language understanding (to answer questions), reasoning about uncertainty (to ask informative questions), and strategic decision making (to balance explore/exploit trade-offss.
A.2.1 STUDY SETUP
We recruited N=42 participants from Prolific (ww.prroifficcom) Participants were required to be located in the United States, fluent in English, and maintain Prolific approval rate of at least 95%.
The study was conducted with IRB approval in multiple sessions that occurred between November 26, 2024 and January 31, 2025. We conducted the study in synchronous, two-player format using the Empirica platform (Almaatouq et al., 2021). Participants were matched via Empirica's 's built-in matchmaking system, which pairs participants they arrive. Participants were required desktop or laptop computer with a modern web browser (Chrome, Firefox, Edge, or Safari). Mobile devices were not supported.
The human study included a tutorial to familiarize participants with the rules of the game; we did not assume prior experience with Battleship. However, did set specific criteria Prolific exclude participants who had previously completed any prior study (c.g., pilot studies) from our group that specifically used the Collaborative Battleship protocol.
Median time to complete the study was 48-60 minutes, depending on the session. Participants earned base rate of $8.00 for completing the study, with performance-contingen bonuses of $0.20 per hit and $$..10 per miss (with bonus floor of $0 such that base pay was always guaranteed). In total, average per- per-pariicipant earnings ranged from
hr.
A.2.2 STIMULUS AND BLOCK DESIGN
We sampled v. 18 unique Battleship boards from the full design space as experimental stimuli. Each board 8 x 8 grid containing exactly four ships-with possible lengths 2, 2,3, 4, and 5- colored red, purple, green, and orange. Boards were labeled B01-B18.
Participants were allocated boards via equal-replication incomplete block design. With N 42 participants organized into 21 pairs (blocks; b = 21), each pair was randomly assigned & = boards. Within each pair, players alternated Captain and Spotter roles across rounds, and board order was randomized. This allocation was designed to ensure uniform coverage: each board appeared in exactly pairs, satisfying bk (18 x 21 x 6).
20

---

Published as a conference paper at ICLR 2026
A.2.3 PARTICIPANT INSTRUCTIONS
Below, we reproduce the full instructions provided to participants before starting the study.
Please read all instructions before accepting this study.
In this study, you will play collaborative version of the board game Battleship with another Prolific participant.
As Captain, you will ask your partner questions about the board to try to get information about the hidden ships.
As Spotter, you will answer questions for your partner, given special knowledge of the ship locations.
Your goal is to reveal all the ships as few moves as possible. By working together effectively as team, you and your partner have the opportunity to earn double though bonus payment!
Earning bonus payment
In addition to the hourly rate, you and your partner are each eligible for bonus of up to $12.00 ($2.00 per round). Your bonus will be determined by how well you work together as a team: the fewer moves it takes to sink all the ships, the higher your total bonus will be.
To maximize your team's bonus, the Captain will need to think carefully about what questions will be most informative, and the Spotter will need answer the Captain's 's questions correctly. Don't rush to complete the study; every hit increases your bonus, but every miss reduces your bonus, so take your time to think through your actions.
As question-asking is a key part of this study's motivation, your bonus is contingent on asking thoughtful questions. We will not issue bonuses for poor quality / copy-pasted questions, move spamming. and other behaviors indicative of low-effort participation.
Your responsibilities
participant
This study is designed to take approximately I hr. Past participants report the game to be fun and engaging. Nevertheless, this is also a cognitively-demandiie
task that will require your full, undivided attention. We ask that you only accept this study if you are prepared to spend the next hour working collaboratively with your partner to play through the game.
Stay engaged and be patient:
Some portions of the game will require you to wait for response from your partner. While participating in the study, ask that you do not navigate away from the study, open other browser tabs, or otherwise attempt to multi-task. Please treat your partner as you would like be treated by responding in timely manner and not making them wait for extended periods.
Attention checks: To ensure that participants remain responsive throughout the whole study, the game enforces time limit on each move. If you exceed this time limit (attention check #1), you will be shown a prompt asking to confirm whether you are still online (attention check #2). you fail both of these attention checks, the study will end, and your submission will be rejected. (If your partner fails the attention checks, your submission will still be accepted, provided that you yourself participated in good faith.)
Manually terminating the study early: at any point you encounter an issue that prevents you from completing the study, please press the "End Experiment" button at the top of the screen. You are still eligible for compensation. On the feedback screen, please make sure to copy the completion code and provide explanation of the issue that prompted you to end the experiment. You may also message us.
Important details
Player ID: Please enter your Prolific ID as your player identifier on the intro screen. (Do not include @ eemail.prolifcccomm in your Player ID.)
Completion code: Please make sure to copy the completion code we provide to you at the end of the study. This is necessary ensure you receive payment.
21

---

Published as a conference paper at ICLR 2026
Matchmaking: You may experience some initial wait times while attempt to match you with another participant. If you are not matched within 10 minutes of starting the study, your game will end automatically, and you to receive compensation for a matchmaking timeout, you must still return the study. you do not return the study, we will not be able issue payment.
eligible for compensation at the hourly rate (totaling $2.50). In order
Network latency:
You may experience some screen flickering, which is due to network latency. the screen goes blank for extended period, you may refresh your browser. (Refreshing will affect your progress in the study.) To minimize your chance of experiencing latency issues, please ensure that you are on stable, fast internet connection.
Bug reports and feedback: Please report any bugs you encounter, Additional bonuses will be given for helpful bug reports and feedback.
A.3 BATTLESHIPQA DATASET
We manually annotated the human data in order (1) establish set of gold labels for evaluating model performance and (2) analyze the types of questions being asked. To validate the accuracy of human answers, annotated all questions with "gold answer" label; questions for which there is 100% inter-annotator agreement were retained. After this process, we obtained gold dataset 931 questions, establishing human accuracy baseline of 92.5%. Additionally, we performed detailed analysis of the question types present in the dataset according to the following taxonomy:
Simple: Simple questions require only the current board state T. answer. For analysis pur-
poses, we designate any question with one or more of the following labels as "complex."
Stateful: Stateful questions require prior board state history {.1...., 11-1 (e.g., "Are any ships touching where I just fired?"").
Discourse: Discourse questions require prior conversation history between players {(91, A1).....
(#-11, (4 At-1)} (e.g., due to ad-hoc convention formation).
Vague: Vague questions require resolving pragmatic aspects of question meaning (e.g.. "mid- "edge, "near"). Prototypically, scalar value that is unclear.
Ambiguous: Ambiguous questions admit multiple possible interpretations, each which could be answered in principle. (e.g.. "Is there a ship F after 5 on G?" could refer to either part or all of row G.)
interpretable even with full context and history- Typically, these do not admit a yes/no answer (e.g.. "Where the green ship?"), or are based on false premmise/misuundessaadnnng about the board state. These questions were removed from the dataset.
Unanswerable: Unanswerable questions
Table 2 shows the distribution of labels in the dataset. Inter-annotator agreement ranged from 94.0- 99. 99,6% further details are given in Fig. 7a.
Gold Label
Count
Percent
Simple
546
58.6
Discourse
212
22.8
Stateful
205
22.0
Vague
49
5.3
Ambiguous
37
4.0
Overall
931
100.0
Table 2: Expert-labed attributes of human questions. (Questions are multi-labed definitions $A.3.)
22

---

Published as a conference paper at ICLR 2026
Correlatinn Matrix of Gold Categories
1.00
0.50
Inter-Anrolator Agreament by Gold Label
Agreement Valuv Value
Cohon's x
0.75
Agreement
Vague
0.05
0.06
1.00
0.01
-0.00
0.00
0.50
-0.25
Ambiguou
0.17
0.12
0.01
1.00
0.04
0.500
0.25
0.00
Unanswerable
0.06
0.01
-0.00
0.04
1.00
Discoume
Staloful
Vague
Antéguous
Unanswerable
-1.00
Disoourge
Statefal
Vague
Amtrgpoous
Unansemmbble
calegory
(a) Inter-anostator agreement statistics across question labels.
(b) Pairwise Pearson correlations between annotation dimensions.
Figure 7: Annotation quality analyses. (a) Inter-annotato agreement demonstrating reliability of gold labels.
(b) Correlation structure among annotated dimensions, indicating which aspects of questions co-vary.
23

---

Published as a conference paper at ICLR 2026
A.4 ILLUSTRATED EXAMPLES
We show selected examples to illustrate the question categories defined in $A.3 as well as other behavioral phenomena of interest in BATTLESHIQQA. Spotter-generated code translations for these examples are provided in $D.1.1. While these examples are handpicked, we also provide a set of candomly-samplees question contexts for both humans and models Tables and
Captain
Spotter
Hoves Left
20
2
3
4 5 678
123
4
5 6
A
A
B
B
C
C
Ship Tracker
D
D RERE
E
PEED
F
G
G
H
H
gamelD: QUJDNZERRRCCESPPRSSPPNGGG roundD:: QUPNLEAAZ2EH0QQPAASTVEEEER
Figure 8: Simple question. In this example, the Captain asks, "Does E7 have a part of ship?" and the Spotter responds, "No." This question is textbook example of simple question, as it can be answered using only the true board state without any additional context.
Captain
Spotter
Moves
2
4
7
1
6 7
Questions Left
A
A
B
B
C
C
Ship Tracker
D
D
Ship Calens
OERL
E
F
G
G
H
H
gamelD: OJDD/Z2RRKACEOTTTTTTANGGG roundiD: CUBNASEEG22022AAAASMMAAAA
Figure 9: Stateful question. this example, the Captain asks, "any parts of undiscovered boat in Row e?". which the Spotter responds "Yes." This question is textbook example stateful question, requires the Spotter to reason about what currently visible in the Captain view.
24

---

Published as a conference paper at ICLR 2026
Captain
Spotter
Moves Left
30
1 2 3
4
8
1
3 4
6 78
Quisiions Lefk
A
A
B
B C D
C
Ship Tracker
D
Ship Caleni
E
SERE
F
G
H
H
gamelD: 0UURSSH0100GUJCEEENNYYY
Figure 10: Discourse-dependent questions. In this example, the Captain asks series of three questions in row: "Is there any horizontal ships left?" (sic); "is it in either first question establishes a discourse context (remaining horizontal ships). making the subsequent questions discourse-dependent. Without this context, the second and third questions are ambiguous (e.g., "it" could refer to any ship).
e?"; "Does it touch E4 C4?" The
Captain
Spotter
Hoves Left
22
1
2
3
4
5
6
8
2
3
4 5 6
8
A
A
B
B
C
C
Ship Tracker
D
D
Ship
E
E
F
F
G
G
H
H
gameD: QUIBBOFEESSSZOOW/CCCORRR roundiD: O1JE86600 DEBE6LLBEDWAAATEEEEMPPPGGG
Figure 11: Vague question. In this example, the Captain asks, "Is red close to green?" This is a textbook example of vague question it requires pragmatic interpretation of fuzzy concept of "closeness" that is inherently subjective. Case in point: while the human Spotter answered, "No" here, the expert annotators unanimously labeled the answer "Yes."
Captain
Spotter
Moves Left
26
2
3 4
5 6 8
123
4
6 8
Quections Left
A
A
B
B
C
C
Ship Tracker
D
D E FEF G
Svip calani
E
F
H
H
Figure 12: Ambiguous question. In this example, the Captain asks, "is one f aafter 5 g?" This question has multiple possible logical interpretations. It seems fairly clear that Captain wants know whether there are any ships on F6-F8, However, in terms Row G, it is ambiguous whether the Captain is interested the corresponding portion (G6-G8), or the whole row. In contrast to the vague questions (e.g.. Fig. 11), both interepretations are well-defined; however, the ambiguity forces the Spotter to choose between multiple possible interpretations when considering
25

---

Published as a conference paper at ICLR 2026
Captain
Spotter
1
2
3
4
5
6
8
2
3
4
5
8
A
A
B
B
C
C
Ship Tracker
D
D E
Svip
E
F G
F
G
H
H
gamelD: D1JFRATTISSEBRCCGZZGPRRO mundiD: QUJSSNDE4SSM9122044XXXRRG
Figure 13: Unanswerable question. In this example, the Captain asks, "where are the ships?" which cannot be answered with "Yes" / "No." Moreover, it is good motivating example for the need to design Collaborative Battleship with binary information bottleneck in the first place, discussed in $2.
Captain
Spotter
Moves Left 36
1 2
3 4 5 7
123
3
4 5 6
8
Questions Left
A
A
B
B
C
C
Ship
D
D EI EERE G
E
F
G
H
H
07J0AN2CHIOO74HHEIS AMAMTFP, roundlD: WWW.HH/TWW.TIHAACRCRRRRRSS
Figure 14: Benevolent lying. In this example, the Captain asks, "Is orange verticle?" (sic), to which the Spotter responds "Yes." Even though orange not vertical, the Spotter's answer is distinctly helpful in context, it causes the Captain to fire B6 the subsequent turn, revealing tile of the Green ship.
Captain
Spotter
Moves Lett
2
3 4
6 8
1
3 4
6 8
Questions Left
A
A
B
C
C
Ship Tracker
D
D
Gvip calani
E
FERM
E
F
EGG
G
H
H
ma CJDNEEN2HHG0T12220L0HZZ..CCC roundi: OJDNEENNGTHHEFFC44B5EE
Figure 15: Epistemic vigilance. In this fascinating exchange, which plays starts by asking whether there a ship prompts the Captain to fire successively at multiple tiles in this region, resulting a prolonged miss streak. Frustrated, the Captain embeds an accusation in their question: "you lied.... Is it on row b?" (to which the Spotter responds "Yes"). On the subsequent game, the Spotter, now acting as the Captain, writes "Nobody lied," before c6 d6." This exchange highlights the behavioral phenomenon
multiple games, the Captain before or d6?" to which the Spotter responds, "Yes." This
clarifying that in their view, "A2 IS of epistemic vigilance (Sperber et al., 2010), where people are sensitive to the reliability of information provided by others, and will actively monitor for potential deception or misunderstanding.
26

---

Published as a conference paper at ICLR 2026
Captain
Spotter
Moves Left 40
1
2 3 4 5
6 8
2
3 4 5
6
8
Questions Left
A
A
B
B
C
C
Ship
D
D
E
FERE
EI
F
G
G
H
H
CIJDAZCHTIAAARRSSSIMNNTT roundiD: DJJDA222206722MASSHHB0TTT
Figure 16: Phatic communication. In this example, the Captain starts the round by exclaiming, "We killin it bro lets do this! LETS DO THIS! lol," before getting down to business: "Alright A C. 47 This example illustrates a surprising number of participants embedded "side comments" into their questions-a clever way to interact with their partner given the constraints of the interface. This hehavior is reminiscent of phatic communication (Malinowski, 1927), where the primary function of an utterance is social rather than informational. In this to build rapport and boost morale, which may be particularly important in
colorful and undeniably human behaviors that elicited by task. Specifically,
the Captain's pep talk collaborative task with monetary incentives on the line.
27

---

Published as a conference paper at ICLR 2026
B SEQUENTIAL MONTE CARLO APPROXIMATION
All of the modeling strategies that we consider involve posterior inference over possible world states E Ste given the current observation history Hi {(gr, (=))==1- However, the space of possible Battleship boards is extremely large ( 23 valid configurations). While it is technically feasible infer ne (s) p(s z, Hi:e) exactly via enumeration, this approach is intractible for other key quantities of interest (e.g., computing and EIG, which require function execution).
We therefore use a sequential Monte Carlo (SMC; Doucet et al., 2001) approach to maintain particle approximation to
Particles. weighted set {(sj, m )) with Σ, (0 1, where each 8j E S is valid (1) the weight of particle time t. We initialize particles
Battleship board configuration, and wj by sampling sj ~ p(s) from the prior distribution over boards, and setting w) 1/N. Posterior update given observation. After observing âe reweight and renormalize:
N
ūj 3 (2) (1 5) 1 fa (3j)) + 1s + La (
(1+1) wj
t -ūy
Wh.
(8)
k=1
Scoring a candidate q. Estimate pr and EIG by
(.(e) Σ 5 [[f]())==1)
EIG. (g) Hy(E + (1-22) ((( Ho(c).
Intuiioon (q) is just the fraction of our current probability mass that predicts "yes" to this question.
28

---

Published as a conference paper at ICLR 2026
C PROMPT LIBRARY
C.I. SHARED COMPONENTS
C.1.1 GAME SETUP PROMPT
System
You are playing the board game Battleship. In this variant of the game, pairs of team to find the location of ships the board.
players collaborate
Each player assigned one of two roles: the 'Captain' or the 'Spotter'. The Captain's role to decide when and where to reveal tiles on board. each turn, the Captain can ask the Spotter question about the board, or make move by guessing tile that they think contains ship.
The Spotter's role is to provide the Captain with information about the hidden tiles. The Spotter has full visibility the board, but can only answer Captain's 's questions with 'Yes' or 'No'.
The board is 8x8 grid, with lettered rows A, B, D. E, F, G, H and numbered columns 1, 3, 4, 6, Coordinates are specified as a row, column pair. For example, C2 is the tile row C, column 2.
There are four ships the board: Green, Red, Purple, and Orange. Ships oriented either horizontally vertically and range from 5 tiles in length.
The board is represented as numpy array with the following symbols:
-1: Hidden
Water
1: Red ship
2: Green ship
3: Purple ship
Orange ship
{[board}}
The ships the board are of the following lengths: ((lengths)). ((shkp_tracker for ship in ships))
Ship Tracker: Unsunk Ship
ship of length ([length)} yet sunk.
Ship Tracker: Sunk Ship
ship of length ([length)) has been sunk. was the ([ship_color_name
C.1.2 REASONING OPTIONS
Reasoning: Direct
Return your answer directly. Do not include any reasoning explanation.
29

---

Published as a conference paper at ICLR 2026
Reasoning: Chain-of- Thought
Please think step-by-step about the task before returning your
C.2 CAPTAIN PROMPT
C.2.1
TASK PROMPTS
Task: Decision
You will be given partially-revealed game board.
Your task is to choose whether you'd like to ask question about the board to gain information, Please answer a single word: "Question' or 'Move', and enclose your final answer in <answer></answer> tags, e.g. <anseer>Qustioo//ansser>>>>>>>>> or <answer>Mov<</nsswe>>>
make
by guessing tile that you think contains ship.
Task: Move
You will be given partially-revealed game board.
Your task is to give the coordinates the hidden tile you think most likely contain a ship tile.
Hidden tiles are marked by '-1'.
Respond with only the coordinates (e.g., A1, B2, etc.), and enclose your answer in <answer></answer> tags, e.g. <answer>A1</answer>
Task: Question
You will be given partially-revealed game board. Your task is to ask single question that will help you gain the most information position You can ask any question, but it must be answerable with a Boolean answer (Yes/No). Make sure to enclose your question in <answer></answer> tags, e.g. <answer>Is the sky blue?</answer>.
possible about
remaining hidden ships on the board.
C.2.2
FULL TEMPLATE
Captain
{(Game Setup Prompt))
Here is the current board: Cicurrent_bbarrd_mmmy...rr
are playing as the Captain. Your objective is find ships on the board as efficiently as possible.
<Insert of the task prompts above (Decision Move Question) here>
You can ask ponuusttions_rmminiinn more questions over the course of the game, and can fire limoves_remainingg more times.
Ship Status: ([sunk_status))
Please think step-by-step about the task before returning your answer.
30

---

Published as a conference paper at ICLR 2026
C.3
SPOTTER PROMPT
C.3.1 VARIANTS
Spotter: Direct
Remember:
You can only answer with 'Yes' or 'No' Please only answer with single word. Enclose your answer in <answer></answer> tags, e.g. <answer>Yes</answer> or (anserr>oos/asswr>>>
Spotter: Code
Your task is to write a Python function that computes the answer to the question.
The function should accept numpy arrays arguments: "true_board" and "partial_board"
The "true_boards is the full board, which is only visible to you as the Spotter. The "partial_board" is the current board that is visible to the captain, which may contain hidden tiles. Your function should return Boolean value, which will be interpreted as 'Yes' or 'No'.
Your function should be defined generically to work with any true and partial board, not just the ones you are given. This means that function must perform operations "true_board", "partial_board", compute answer
both boards in order
Captain's question. Avoid hardcoding the answer. In some situations, the correct answer may depend on the current state of the game. For instance, if the Captain asks, "Are there any ships in Row A?', the answer depends what ships have already been revealed. If there tiles in Row then the answer 'Yes', However, if all ships in A have already been revealed, then the correct answer is 'No', Comparing the "partial_barrt" with the "true_board" will allow you to determine which ship tiles remain unrevealed. Remember: Your goal is to help the Captain find the location of the ships the board, your function should be designed to provide the useful information context.
any unrevealed ship
Your function should be defined as follows: ppythnn
def answer(true board: ndarray,yy, partial_board. np. ndarray) bool: # Your code here
return ANSWER
Your code will executed in environment with "numpy" (namespaced "np") and
a 'board" variable (a numpy representation of the board).
Make sure your code is valid Python and does not contain any syntax errors.
You are responsible for implementing the "answer()" function, but do not invoke it include any other code.
C.3.2 FULL TEMPLATE
Spotter
((Game Setup Prompt))
Here is the partial board, which is the view that is visible to the Captain: sipartialbbarrd..umyyaaraay
Here is the full board, which only you Spotter have access
31

---

Published as a conference paper at ICLR 2026
(Crue_bbard__uupyyerrraa))
You are playing as the Spotter. Your objective is to answer the Captain's questions as accurately as possible.
<Insert of the Spotter variants above (Direct Code) here>
<Insert one of the reasoning options above (Direct / Chain-of-Thoughi here>
Here is the question the Captain asked: Captain (question): ((question_text))
32

---

Published as a conference paper at ICLR 2026
D EVALUATIONS
D.1 SPOTTERQA EVALUATIONS
MODEL
SPOTTER
OVERALL
SIMPLE
COMPLEX
DISCOURSE
STATEFUL
VAGUE
AMBIG.
VALID
Human
0.925
0.928
0.919
0.962
0.941
0.816
0.865
1.000
Anthrople
claude-opus-4
Base
U.868
0.893
0.833
0.836
0.820
0.843
0.816
0.999
0.936
0.864
0.869
0.849
0.843
0.816
0,999
Code
0,937
0.970
0.889
0.859
0.878
0.922
0.868
0.993
CoT + Code
0.944
0.977
0.897
0.892
0.883
0.922
0.789
0,998
Blaueesoonnet
Base
0.834
0.869
0.784
0.765
0.795
0.725
0.868
1,000
CoT
0.904
0.941
0.851
0.831
0.810
0.941
0.816
0,999
Code
0.900
0.906
0.888
0.816
0.996
Col' + Code
0,937
0.970
0.889
0.883
0.888
0.902
0.816
0.997
Google
gemini-2 2.5 2.5-h
Base
0,231
0.293
0,141
0,080
0.117
0.294
0.237
0.306
CoT
0.516
0.564
0.447
0.385
0.424
0.588
0.579
0.578
Code
0.440
0.478
0.386
0.300
0.439
0.490
0.447
0.470
CoT + Code
0.497
0.542
0.432
0.362
0.439
0.588
0.553
0.525
Meta Liama
Ilama 3.1 10.5-405bba0 instruct
Base
0,701
0.771
0.602
0.568
0.600
0.608
0.632
0.998
CoT
0.711
0.760
0.640
0.624
0.659
0.647
0.632
1.000
Code
0.814
0.900
0.692
0.681
0.688
0.686
0.658
0,981
CaT + Code
0,823
0.907
0.702
0.638
0.707
0.765
0.711
0.985
1i-m--3.-700-instmuc
Base
0.622
0.676
0.545
0.512
0.556
0.549
0.605
1.000
CoT
0.608
0.660
0.532
0.526
0.517
0.431
0.658
1,000
Code
CoT + Code
0.795
0.884
0.668
0.624
0.663
0.686
0.605
0.974
luma---mswerick
Base
U.690
0.742
0.614
0.606
0.605
0.667
0.658
1.000
CoT
0.789
0.864
0.681
0.648
0.644
0.686
0.789
1,000
Code
0.797
0.862
0.704
0.662
0.741
0.686
0.632
0.977
CoT Code
0.751
0.742
0.741
0.784
0.632
0.976
Uaaa---scout
Base
0.622
0.680
0,540
0.507
0.512
0.549
0.737
0.997
0,580
Code
0.767
0.839
0.663
0.601
0.634
0.745
0.711
0.958
CoT + Code
0.784
0.864
0.668
0.620
0.663
0.804
0.605
0.958
OpenAl
gpt-4.1
Base
0.752
0.805
0.676
0.700
0.673
0.647
0.579
1.000
CoT
0.681
0.678
0,627
0.605
Code
0.904
0.961
0.823
0.808
0.815
0.443
0.711
0.997
0.999
1-iii
Base
0.686
0.741
0.607
0.563
0.580
0.765
0.553
1.000
0.783
0.676
0.620
0.668
0.824
0.658
1.000
Code
0.899
0.957
0.815
0.793
0.810
0,902
0.763
0.998
CoT + Code
0.896
0.959
0.805
0.789
0.780
0.902
0.711
0.999
gpt-4.1-nano
0.580
Col
0.690
0.750
0.604
0.554
0.571
0.745
0.632
1,000
Code
0.702
CoT Code
0,851
0.923
0.748
0.737
0.751
0,843
0.632
0.987
gpt-4o
Base
0.677
0.728
0.604
0.592
0.590
0.627
0.421
0.988
CoT
0.808
0.862
0.730
0.723
0.717
0.725
0.711
1,000
Code
0.878
0.957
0.763
0.709
0.751
0.843
0.737
0.995
gpt-4o mini
Base
0.525
0.528
0,522
0.507
0.512
0.451
0.553
1.000
Code
0,799
0.862
0.707
0.685
0.654
0.922
0.658
0.992
CoT + Code
0.828
0.905
0.717
0.718
0.702
0.804
0.658
0.982
gpt-5
Base
0.924
0.970
0.859
0.869
0.859
0.863
0.737
1.000
Col
0.926
0.964
0.871
0.873
0.863
0.882
0.757
1,000
Code
CoT + Code
0.940
0.980
0,882
0.878
0.883
0.902
0.737
0.999
Base
0.966
0.863
0.882
1.000
CoT
0.924
0.964
0.866
0.873
0.868
0.882
0.763
1.000
Code
0.925
0.966
0.866
0.873
0.888
0.863
0.763
0.982
CoT Code
0.856
0.868
0.843
0.979
o4-mini
Base
0.927
0.953
0.889
0.887
0.873
0.922
0.789
1,000
Code
0.930
0.977
0,864
0.845
0.854
0.863
0.789
1,000
+ Code
0.968
0.877
0.878
0.922
0.763
0.996
Table 3: SpotterQA: Accuracy breakdown by question type. Valid shows proportion answers returned by each model that followed formatting instructions ($C.3). With the exception of Gemini-2.5. 2.5-shh which frequently returned invalid answers. all other models adhered readily to the answer format.
33

---

Published as a conference paper at ICLR 2026
Spolier Diffemncces
Dal Code
+0,015
+0.044
+0.147
0012
+0.069
+0.152
0.08
Ascurcy
Bienn Got
+0.063
-0.04
-0.00
8-31 teery alordlicenti
CoT Code
Code
COT
Base
Figure 17: Differences in Spotter accuracy between conditions, Asterisks indicate statistical significance based two-sided paired t-test (* 0.05, "* < 0.01, *** 0.001).
D.1.1 EXAMPLE SPOTTER PROGRAMS
Program for Fig. Simple Question, "Does E7 have part of ship?"
def answer (trveerrtrr__baee _borrd: np. nddrraay,
ndarray) bool:
# Map the coordinate E7 zero-based indices row_letter 'E'
col Lol_nnmber+> =
ard(row_letter) - ord('A') @-based row index
col_number
0 0-based column index
# A ship tile is any non-zero value in the true board (1-4)
return True_board[r, c] != 0
Program for Fig. Stateful Question, "any parts of an undiscovered boat in Row e?"
def answer (true_board: np.ndarray, partial_board: np. rdarray) bool:
# Column 5 1-based indexing corresponds to index in 0-based indexing
col_idx
# Safety check: if the boards don't have column 5, return False hrrriaalbbard.shapeeee. <= col_idx:
if true_board, 1 <= col_idx return False
true_col = true_ board[; col_idx] partial_col partial_board[; col [ol_idx]]
"yet to be discovered" ship part a cell that: # contains a ship in the true board (>0) # is not already revealed as that same ship value in the partial board = (true_col > 0) (partial_col != true_col)
return (ool(nnpany) an (nnddssscoo
Program for Fig. 10, Discourse-Dependenn Question, "is it in either row or e?"
import numpy as np
def answer (truuetttrebbodd np. np.ndarray, partial_board: np. ndarray)
bool:
34

---

Published as a conference paper at ICLR 2026
# Identiff ship IDs present the true board (positive numbers) ship_ids [sid
np. ww..niquettuue_bbt sid
for sid in ship_ids:
coords www.arereettueeebbeteeee board == sid)
if coords. continue
rows = coords[:, e]
cols = coords[:, 1]
# Determine orientation: horizontal if all in the same row is sa_horizonnal = un..uniqu (rows) size ==
if is :oriotazzot:::
ship fully revealed only
tiles are revealed as its
on the partial board revealed_mask = (partial_board cols] == sid)
fully_revealed ap.all(revealed_maak)
If any horizontal ship not fully revealed, there are horizontal ships left to find
if not fully_revealed: return True
# No horizontal ships remain unrevealed return False
Program for Fig. 11, Vague Question, "Is red close to green?"
def answer (trverttue__bbtee board: np. ndarray, partial_board. np. addarry -> bool: # Define masks for red (1) and green (2) red = staud_board == 1)
green (true_board 2)
# Compute 4-neighbor adjacency: cells directly up/down/left/rriht of any red
cell
neighbors_od _orrddrrss___rdd_ee_oo www.zeroslkkeeeeeee dtype=bool)
Down neighbors
neighbors_of_red]] :] |= red[:-1, :]
# Up neighbors
lfghhors_of_red[_--1 :] |= red[1: :]
# Right neighbors
siighbors_f_reddie 1:3 |= red[: :-1]
# Left neighbors
ne neighbors_of..m _edd[ :-1] |= red[:, 1:3
any green cell 4-neighbor of red cell, they "close"
return (np.(np.an any (neigghorss_ooffcccoooo & green))
Program for Fig. 12, Ambiguous Question, "is one Fafter or on g?
def (eruerrtrue_bardd
ndarray, partial_board, ndarray)) >> bool: # We interpret the question "Is there any unrevealed ship tile either (a) on row after column 5, or (b)
anywhere on row G?"
# Rows are A-H => indices 0-7; thus F -> 5, G -> 6
# "after 5" means columns 6-8 => 8-based col indices >=
35

---

Published as a conference paper at ICLR 2026
# Mask of unrevealed ship tiles (hidden in partial but ship in true) hidden_ship (partial_board -1) (true_board 0)
# Create row/column index grids rows, cols np. (truceetesstuee_eaeee boaeedbborrd_ee .
# Condit tion (a): on row (index 5) with columns strictly after (indices 5)
cond_f_after5 (rows = 5) (cols >= 5)
# Condition (b): cond_g_any (rows 6)
6 (index 6), any column
# Combined area of interest area_mask cofd_f_ cond_g cond_g_any
# Check any unrevealed ship tile lies the area interest return bool(np. any (hidde & area_mask))
Program for Fig. 14, Benevolent Lying, "Is orange verticle?"
answer (true_board: ndarray par partial_board np. ndarray) bool:
# Determine if the Orange ship (value 4) is oriented vertically on the true board.
coords www..rereetruee_boreee == 4)
if coords.sizz
No orange tiles found; cannot vertical
return False
rows coords[:, 0]
cols coords[:, 1]
unique_rows np. unique (rows). size
unique_cols np. uniqueccols). size size
# Vertical if all tiles share the same column and span multiple rows
return (unique_cols == 1) and (unique_rows 1)
Program for Fig. 15, Epistemic vigilance, "on or before c6 or d6?"
answer (trueebordd np. ndarray, par partial_board. nd. -> bool:
# Interpret the question as:
# "Is there any unrevealed ship tile on before C6 on or before D6?" # i.e., in C, columns 1..6 inclusive, in row D, columns 1..6 inclusive.
only count tiles that are ships true_board and still hidden partial_board
def rc_ (r_to_index(row_lette str, col_num: int): See[row_letter.upperr ord('A') с col_num return r,
mask np. ap..errs_ iieros_iikettrue_bbaa dtype=bool) row_letter, col_num [('C', 6), ('D', 6)]:
r, c rr_to_index(row_letee # Guard against out-of-bounds in case of different board sizes
col_num)
if 0 <= True_board. shapel[]] and 0 <= bruu__bard. shape[1]: mask[r, :c+1] True
# Unrevealed ship tiles: ship on trur_ and not yet revealed on partial_bon board unrevealed_shiip (true_board 0) (partial_board I= true_board)
36

---

Published as a conference paper at ICLR 2026
return (nrppaanyyuurreveaeeesshippp mask))
37

---

Published as a conference paper at ICLR 2026
D.2 CAPTAINQA EVALUATIONS
LLM
CAPTAIN TYPE
F1 SCORE
PRECISION
RECALL
MOVES
QUESTIONS
EIG
REDUNDANT Qs
Human
Human
0.615
0.467
0.968
28.325
8,198
0.351
0.028
Baseline
Random Greedy
0.317
0.210
0.665
40,000
0.000
0.456
28.778
0.000
Llamn---Scout
1.
0.367
0.264
0.630
30.426
14.852
0.242
0.185
+Bayes-Q
0.393
0.284
0.657
29.352
14.833
0.469
0.002
+Bayes-
0.685
0.537
1.000
24.926
14,333
0.266
0.146
Bayes-QM
1.000
21.667
13.907
0.479
Baycs-QMD
0.764
0.639
1,000
21,000
14,981
0.490
0.000
GPT-4o
LM
0.450
0.308
0.863
36.593
14.056
0.296
0.146
+Bayes-Q
0.471
0.324
0.901
36.426
14,296
0.476
0.012
+Bayes-M
+aaes QM
0.753
0.615
1.000
21.074
11,556
0.501
0,003
Rayes-QMD
GPT:5
LM
0.716
0.568
1.000
22,833
7.981
0.470
0.002
Bayes-Q
0.698
0.547
1.000
23,815
7.722
0.499
0.000
+Bayes M
0.708
0.561
1.000
23.333
7.963
0.474
0.000
Rayes-QM
7.167
Table CaptainQA: Overall results. Score (Targeting Score) is the harmonic mean Precision and Recall over the board as a binary classification task. Moves (out of 40) and Questions (out 15) count the total number of moves and questions asked, respectively. EIG (s = 1.0) measures the average expected information gain of questions asked, with ceiling value 0.531. Redundant Qs is the fraction of questions yield information gain (i.e., (g) 0).
Daxine Hamas
0.22
1.2
1.0
112
0.00
Mew
2221
Mawi
OPT-
Ranaline
Liama-d-Soou
GDT-40
GPT-S
Figure 18: Win rate heatmap hetween Captain strategies. The "win rate" metric (defined in $4.2) measures board-matched performance in simulated head-to-head play between two Captains. Each cell in the heatmap table shows the win rate of the row over the column; 0,50 indicates balanced performance, while >0.50 indicates that the row Captain consistently beats the column Captain.
38

---

Published as a conference paper at ICLR 2026
60
is the remaining longth-2 shig drienged horizonaaly?
the ships or orientatonn Is there arship in the top half of board?
40
cupio columnns f...
any ships touching
Is the jangt--3 stip entraly containe within the...
20
t-SNE 2
0
Is there ship B1?
thare ship that vertical...
another ship iioro any par of shipin oplumin (41?
-20
any pari located in any part
40
-60
-50
0
50
t-SNE
Homan
Llama 4 Scout
GPT-40
GPT-5
space human and LM questions. Each point question asked during play. with 2D coordinates obtained by applying t-SNE to PCA-reduced question embeddings, obtained from text- - 3-mlall from OpenAl. Colors indicate different LMs. We annotate small number of representative questions per group, selected via stochastic distance- weighted sampling around per-group PCA centroids. The resulting map highlights that human and model captains occupy overlapping but systematically distinct regions, revealing differences the kinds of questions they prefer to ask.
Figure 19: Visualization
LLM
Captain Type
Input Tokens
Output Tokens
Input Cost (USD)
Output Cost (USD)
Tottl Cost (USD)
Llama-4-Seout
LM
6,882,573
2,156,078
0.55
0.65
1.20
+Bayes-Q
14,211,221
4,5
1.14
1.36
2.50
-Bayss
3,751,304
998,736
0.30
0.30
0.60
+Bayes-QM
-Bayes-QQu
8,79 1,79
2,464,043
0.70
0.74
1.44
Total
44,239,853
13,486,912
3.54
4.05
7,59
GPT--o
LM
7,002,350
1,755,117
17.51
17.55
35.06
+Bayes-Q
15,620899
4,244,231
39.05
81.49
Bayes-M
3,520,367
994,233
8.80
9.94
18.74
Baycs-QM
9,532,203
2,917.634
23.83
29.18
53.01
Bayes-QMD
9,287,099
2,759,823
23.22
27.60
50.82
Total
44,962,910
12,671,038
112.41
126.71
239.12
GPT:5
LM
4,022.670
13,880,517
5.03
138.81
143.83
+Bayes-Q
8,002,611
35,823,591
10.00
358.24
368.24
+Bayes M
2,755,613
7,952,909
3.45
79.53
82.97
MMyessQM
6,074,985
27.092,481
7.59
270.93
278.52
Total
20,855,879
84,749.498
26.07
847.50
873.57
Table 5: Token usage and dollar cost of agents on the CaptainQA benchmark. We report totals summed across all 54 games for each Captain. Note the difference in pricing across LMs spanning two orders of magnitude: while Llama-4-Scou S-outt costs approx. USD total across all experiments, GPT-5 costs approx. 900 USD.
39

---

Published as a conference paper at ICLR 2026
EIG
Question
Board
Model
Captain
Human
0.12
in the bottom left corner?
0.20
is there boat in the bottom right corner
0.42
Is there horizontal ship in row A?
0.44
trigger happy lol, there a ship in F6, F7, G6, or G7?
0.49
Is the ship D4?
0.52
Is orange vert?
0.26
are there any ships in row 4-5
0.40
there any ship the bottom right
0.43
the purple ship surrounded by water
0.48
upper yes, lower no
Table 6: Example questions from human Captains. Questions are randomly sampled from the BATTLESHIPQA dataset.
40

---

Published as a conference paper at ICLR 2026
EIG
Question
Board
Model
Captain
Llama-4-Scout
LM
0.00
Is there ship in A?
+Bayes-Q
0.51
Is there ship in row C. that is of vertical
ship?
+Bayes-M
0.31
Is there a ship in column 5?
+Bayes-QM
0.40
Is there a ship in column extends into row A or B?
+Bayes-QMD
0.53
Is there ship in B that spans than columns starts column or further?
GPT-4o
LM
0.53
Is there at least one ship in the section covering B to B and columns to 4?
+Bayes-Q
0.52
Is there any part of a ship located in rows F or G and columns 1 to 4?
+Bayes-M
0.12
Is there a ship tile rows E1-H4?
+Bayes-QM
0.51
Is any part of ship present in tiles D1, D2, D3,
E7, or HI?
+Bayes-QMe QMD
0.53
Does row F contain any part of a ship?
GPT-5
LM
0.40
Is the length-5 ship on row D?
+Bayes-Q
0.37
Does not-yet- sunk length-2 (green) ship occupy at least one tile in columns 6-8?
+Bayes-M
0.18
Is least of the remaining length 2 ships entirely contained within columns through
-Byees-QM
0.14
Is the remaining length-3 ship located entirely within the top half (rows A-Dy?
Table 7: Example questions from agents. Questions are randomly sampled from game trajectories from the CaptainQA experiment.
41

---

Published as a conference paper at ICLR 2026
E Guess Who? EXPERIMENT
E. THE Guess Who? GAME
In order validate methodological contributions, in this section discuss extension of our framework to another setting, a version of the board game Guess Who?"
This is typically two-player game, where both participants are given the same of 24 human characters, each with a unique combination of given traits (e.g. hair color, eye color, facial hair). Each player selects one character, and players altemnte asking each other binary questions (e.g. 'Is your character wearing hat?") to try to determine what character the other player picked. The objective of the game is to the first player identify the other player's character.
In this experiment, we adapt the "Guess- Whosss-rww----r environment from TextArena (Guertler et al., 2025). This a one-player version the game, where an LM is tasked with identifying character picked randomly from set of 24 in the least amount of moves possible. The LM only gets one guess: the LM ever guesses the wrong character, game ends in a loss.
In the default TextArena setting, LMs get maximum of 40 questions for these 24 characters, mean- ing trivial strategies such as asking "Is your character X?" for all characters are valid. Thus, to incentivize models to attempt interesting strategies, we restrict the question budget to questions, and increase the total number characters to 100.
The new characters are sampled by querying GPT-5 with the existing set of characters in JSON format, and asking to produce 76 more characters like them. The full character list was then validated to ensure no two characters were indistinguishable, and that the game could therefore still be played.
E.2 EXAMPLE CHARACTERS
Two example characters from our of 100 follow:
"name": "Alex",
"gender": "male",
"hair_color": "brown", "hair_style": "short", "eye_color": "brown", "accessories"; ["glasses"], "facial_hair", "mustache", "skin_tone": "light", "hat_type": "none", "hair "hair_texture"; "straight", Seeyewear_styles "round", @mose_shapel "pointed", "ear_size": "medium",
"smile__te "smile_type": "wide", rclothing_styles "casual", "middle-aged", " "complexion": "fair" "cheek_feature"" "dimples"
" "name": "Elena", "gender": "female", "hair_color"" "blonde", "hair_style": "short", "eye_color"" "green", "accessories": ["scarf"], "facial_hair"; "none", "fair",
42

---

Published as a conference paper at ICLR 2026
"hat_type": "none", "hair_texture"" "straight", "eyewear_style": "round",
"nose_shape": "round", "ear Year_size": "small",
tomile_type", "wide",
" "clothing_styyp style": "sporty", aggerange" "middle-agedd,
complexion": "olive", cceek__feeee featurree "freckles"
E.3 MODELING QA BEHAVTOR
We then implement the same LM strategies as Section 4.3, which we sum up in Table 8 below.
Note that since the game is only composed of one guess, the 'Decision' function just confound- ing factor: given the information bottleneck, models should just ask every question they can and guess when they run out of questions. This motivates the definition of this setting's decision func- tion dow (H1.)) below, as well as justifying the removal of the Bayes-QMD condition, since there no rational decision decision-making making ability model.
This also means the symbolic baselines Random and Greedy are no longer useful comparisons, as both would immediately make their guess, picking a character with no prior information, and thus
obtain a success rate around
1%.
100 characters
Player
Decision
Question
Guess
LM
daw (Haa)
PLAC(: Hiaa)
PLA( Hi:e)
+ Bayes: Q
arg max yea EIG, z. Hia)
Rayes-M
PLME a, Hi.))
arg max; s. Te(i a., Hi.e)
Bayes-QM
Qaay
Masss
Table 8: Summary of Guess Who? strategies. As in 1, LM is pure language model strategy, which the Bayes strategies build upon. Triple-dots indicates inheritance from the row above.
QUESTION, GUESS,
If # Questions Asked < 8, Otherwise
dow(H
Figure 20: The decision function for Guess Who? experiment
E.4 EXPERIMENTAL DETAILS
As with the Battleship CaptainQA experiments (Section 4.3), we test GPT-4o and Llama-4-Scout our player (equivalent "Captain", in our Battleship framework) models, fixing GPT-5 as gamemaster (a "Spotter") model to answer the player's questions and provide feedback on the final guess. We do evaluate GPT-5 player model due cost reasons.
We run each of the strategies described in Table for 60 games. We query all models via the OpenRouter API with default parameters.
E.5 RESULTS
A graph showing the results of these experiments available in the main text as Fig. more precise breakdown of the results, including the average EIG per condition and the percentage of redundant questions, is available in Table below.
The results in Table 9 show that the Bayesian strategies propose, originally applied Battleship, also apply to Guess Who?.. In both models, success rate massively increases from the base LM condition to Bayes-QM: GPT-40''s success rate increases from 0.617 0.900, and Llama-4-Scuut's
43

---

Published as a conference paper at ICLR 2026
LLM
Captain Type
Success Rate
EIG
Redundant Qs
Llama-4-Scoon 4-ouout
LM
0.300
0.413
0.006
+Bayes-Q
0,450
0.478
+Bayes-M
0,550
0,436
0
+Bayes- QM
0.724
0.478
4PT44
LM
0.617
0,454
0
+Bayes-Q
0.729
0.512
Bayes-M
0.667
0.455
Bayes-QM
0.900
0.506
Table 9: Guess Who? QA: aggregated success rates and breakdown by model and strategy.
success rate increases from 0.300 to 0.724. As with the Battleship experiments, we can therefore see that Bayesian strategies uplift weak LMs past the performance of much stronger pure LM agents.
The middle conditions Bayes-Q Q and Bayes-M also separately improve as compared to both base con- ditions, suggesting that neither base LM optimally integrates information from all previous questions into its guessing strategy (otherwise we'd see no improvement through Bayes-M), and that neither model is reliably able to ask the optimal question at any given point during the game.
The Bayes-Q and Bayes-QN MMMes-QM conditions also significantly raise EIG (0.454 - 0,506/0.512 for GPT- 4o, and 0.413 - 0.478/0.478 for Llama-4-Scout) Redundant (EIG 0) questions are already rare -P never asks any such question in any condition, -lama-4-Scout only asks then 0.6% of the time in the base LM condition but such questions asked in any condition that optimizes for FIG. This encouraging, since means our FIG-based reranking approach finding better questions than the first question the LM considers.
In general, these results point to the generality of this framework, having brought substantial im- provements the performance of LM agents very different informatiio--seeking domains.
E.6 Guess Who? PROMPTS
E. SYSTEM PROMPT
System
You are playing Guess Who. The other player has selected a character from the list below, and your goal is to guess which character they have selected by asking yes-or-no questions about the character's traits.
can ask questions total, and you have to make your guess after asking all of them. If you guess correctly, you win the game. If you guess incorrectly, you lose the game.
Given this game history:
<history>
[history]
</history>
This is the list of characters you can ask questions about:
<characters>
(characters)
</characters>
This prompt is referred "(context)" when mentioned in other prompts.
44

---

Published as a conference paper at ICLR 2026
E.6.2 PLAYER PROMPTS
Guess
{(context))
Your task to make your one and only guess about character. Make sure you consider the context of the theme and all previous questions and answers.
Guess from the list above.
Please think about your answer step by step. When you have come up with final answer, respond with your guess wrapped in <answer></answer> tags, and optionally square brackets, <answer>Mike<<ansser> <answerr([Miee]</nnswerr
Non-EIG Question
{[context))
Your task to ask single question that will help you gain most information possible about the secret word. You can ask any question, but is must be answerable wi with Boolean answer (yes/no). Make sure your questions are clear, specific and different from ones you have asked previously, to avoid pigeonholing potentially wrong answer too quickly.
You have prremiining.questionnn questions left, including this one.
Please think about your answer step by step. When you have up with your question, please wrap it in <answer></answer> tags: e.g. <answer>Is the character male?</answer>
EIG Question
((context))
Your task is to generate {(k}) question(s) that will help you gain the most information possible about the secret word. Each question must be answerable with Boolean answer (yes/no).
You have (Cremaining_quesstions)) batches of ((k)) question(s) left, including this
Please think about your answer step by step. When you have come up with your question, please return your question(s) as a JSON dictionary with numbered keys, wrapped in <answer></answer> tags like this: <answer><("1"; "Is the character male?". "2": "Do they have mustache?", "3": "Do they have hat?"))</answer)
IMPORTANT: Use proper JSON format with double quotes around both keys and values.
E.6.3 GAME/SAMPLER PROMPTS
Consistency
You are playing Guess Who. Your task is to determine which characters from the list below are consistent with the constraint implied by the question.
45

---

<characters> ([characters)) Published as a conference paper at ICLR 2026
The most recent question is "((question))".
Given the following characters:
</characters>
Respond with a JSON dictionary wrapped in <answer></answer> tags where the keys are the characters and the values are either "yes", if the character satisfies the constraint given the question, or "no" if they not.
<answer(("ccharacter"" "yes", "character2": "no", "character3": "yes") ///////e>/
IMPORTANT: proper JSON format with double quotes around both keys and values.
46


Reviews:
[{"review_id": "X8IIAqKImt", "reviewer": "Reviewer_VQ6M", "summary": "Paper introduces the collaborative battleship game, where a “captain” and a “spotter” collaborate in the game of battleship. The captain must decide between asking the spotter a question, or taking a hit at a board position, thereby having to balance information seeking and reward seeking.\n\nThe authors collected the BATTLESHIPQA human dataset where pairs of humans collaborated to play the game (42 participants, 21 pairs). This establishes human performance, the kind of questions humans ask, and how accurately the human (spotter) responds. \n\nThey then evaluated 15 LMs in the role of the spotter (i.e. Q&A), finding that the best frontier models can do well, but they show greater degradation in hard (i.e. context dependent) questions. Then, they evaluate 3 LMs in the role of the captain, with various “bayes rational” strategies.  The “bayes rational” strategies improve the performance of weak LMs to the level of / slightly beyond GPT-5.\n\nFinally, they extended the bayesian inference framework to other information seeking games and see some performance gains.", "questions": "### On assumptions\n\n**(1)**\nis maximizing EIG (Eq 5, L214) in this game the “right” thing to do to maximize performance of hitting a ship? My understanding is that in some games from previous works (e.g. ActiveACRE, blickets, feature world) [1,2,3], the explicit goal is to find out how the environment works. In these cases, directly optimizing for information gain is the “right” thing to do. \n\nIn battleships, seeking information is only ever in service of the goal of hitting ships. Therefore, rather than computing the post-question hit probability (Eq 7) with the max-EIG question (Eq 5), i.e. $p_{t+1}^{hit} (q_{t}^{*} | x, H)$, shouldn’t we directly find $\\arg\\max_q p_{t+1}^{hit}(q | x, H)$ instead, and use that in the decision rule in L217? Is there no scenario in which this will change which question is selected? This is discussed empirically in L405-412 but it would be good to discuss a bit theoretically as well. \n\n**(2)**\nI do not think the information gained from the “shoot” action is appropriately considered. The act of shooting perfectly reveals information about whether or not a tile contains a ship, akin to asking a noise-less spotter “is there a ship on this tile”. Indeed, for a 8x8 board and a budget of 40 shots, 40/64 = 62.5% of tiles can be revealed this way. Thus, shouldn’t the captain’s decision really be between (i) asking a question based on post-hit probability (per point (1) above), and (ii) choosing a shot that will both hit a current target and/or increase post-hit probability of the next shot? \n\n\n### Minor clarifications\n\n1. What does Figure 3 b and c error bars denote? Please label / state in figure caption\n2. How is the discount factor $\\gamma$ in L216 selected?\n\n---\n\n[1] Piriyakulkij, Top, et al. \"Doing experiments and revising rules with natural language and probabilistic reasoning.\" Advances in Neural Information Processing Systems 37 (2024): 53102-53137.\n\n[2] GX-Chen, Anthony, et al. \"Language Agents Mirror Human Causal Reasoning Biases. How Can We Help Them Think Like Scientists?.\" arXiv preprint arXiv:2505.09614 (2025).\n\n[3] Sawyer, Danny P., et al. \"Can foundation models actively gather information in interactive environments to test hypotheses?.\" arXiv preprint arXiv:2412.06438 (2024).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "There are numerous strengths with this paper. To start, the collaborative battleship game sets up an interesting scenario for the captain agent, where they not only have to balance information seeking vs. reward seeking behaviour, but also maintain uncertainty about the correctness of its collaborator (noisy spotter agent). Information seeking in the space of natural language is an interesting setting to study.\n\nThe human dataset provides valuable information to ground “human level” performance, the type of questions asked, and human-like behaviour. The LM evaluations are comprehensive, with interesting findings including code generation boosting spotter accuracy. The “bayes rational” captain strategies improving worse models to perform at GPT-5 level has useful application implications. \n\nOverall, the paper is very well written and presented.", "weaknesses": "A number of simplifying assumptions were made in the “bayes rational” modelling choices. For instance, modelling with fixed $\\epsilon$ (as the authors already point out) and $\\gamma$ (not sure how this is set), and only modelling single-step look-ahead are simplifying assumptions. I do not think this detracts from the main point of the paper, as to my understanding this paper is about improving empirical performance of weak LMs using some cognitively inspired “bayes rational\" strategies. Nevertheless, it is worth pointing this out for scientific rigour. \n\nHowever, there are a few simplifications that I am quite confused about, and likely warrant deeper discussions. I ask them in the question section below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x9PCP5suCL", "reviewer": "Reviewer_g4p6", "summary": "This paper introduces Collaborative Battleship, a novel two-player task designed to evaluate the trade-offs between information-seeking (asking questions) and exploitation (taking actions) in language model (LM) agents under communication constraints (yes/no answers). The authors collected a human dataset, BATTLESHIPQA (N=42 participants, 126 games), establishing human baselines for question quality and strategic play. They compare human performance to various LMs, finding that while weaker LMs struggle, frontier reasoning models approach human levels. To improve agent rationality, the paper proposes inference-time strategies based on Bayesian Experimental Design (BED), using Sequential Monte Carlo (SMC) to approximate belief states and guide question selection (maximizing EIG), action selection (maximizing hit probability), and the explore/exploit decision (one-step lookahead). These strategies significantly boost performance, enabling weaker LMs (Llama-4-Scout) augmented with Bayesian methods to outperform average humans and stronger LMs like GPT-5 in win rate, at substantially lower computational cost. Findings were replicated on the Guess Who? game. The authors provide IRB approval details and plan to release the dataset and code.", "questions": "1. Could you provide more details on the human study participants? What was their prior experience with Battleship? How were the number of human trials balanced against LM evaluations in terms of total interaction opportunities or budget? \n\n2. Could you please provide performance results (e.g., win rate, F1 score) normalized by computational cost (tokens, latency, API cost)?  Cost-controlled comparisons (e.g., win rate vs. budget curves) would strengthen the claims about efficiency.\n\n3. Can you provide ablations that isolate the capabilities of the Captain (questioner/actor) and Spotter (answerer) roles? For instance, how does a strong Captain perform with a weak Spotter, and vice-versa? How much does the specific code generation strategy contribute to the Spotter's grounding? \n\n4. How sensitive are the results of the Bayesian strategies to hyperparameters like the SMC particle count, the number of candidate questions sampled (k for $Q_{Bayes}$), the decision discount factor ($\\gamma$ for $D_{Bayes}$), and decoding parameters (e.g., temperature)?\n\n5. What was the inter-rater reliability for the manual annotation of human questions and gold answers in BATTLESHIPQA?\n\n6. Consider citing and comparing with SPIN-Bench (Yao et al., 2025) which evaluates LLMs in multi-agent cooperative and strategic settings (like Hanabi)  and documents coordination failures, making it relevant context for evaluating interactive agent strategies.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**Novel Task and Dataset:** Collaborative Battleship provides a clean, interpretable environment for studying the explore/exploit dilemma and grounded communication. The BATTLESHIPQA dataset, collected from human interactions, is a valuable contribution for benchmarking and analysis.\n\n**Principled Bayesian Framework:** The application of BED principles (EIG maximization, belief updating via SMC, MAP action selection) provides a strong theoretical grounding for the proposed inference-time strategies.\n\n**Strong Empirical Results:** The Bayesian strategies demonstrate significant improvements in LM agent performance across multiple metrics (accuracy, EIG, F1, win rate). The finding that augmenting weaker LMs can lead to super-human and SOTA-LM-beating performance at lower cost is particularly compelling.\n\n**Generalization:** Successful replication of performance gains on the Guess Who? task suggests the framework's potential applicability to other information-seeking domains.\n\n**Transparency and Reproducibility:** The paper includes ethical considerations for human subjects, clear plans for releasing code and data, and explicit disclosure of AI assistance.", "weaknesses": "**Limited Scope:** While the paper introduces an interesting method, its evaluation is confined to a specific domain defined by the authors, with generalization demonstrated only on one additional ad-hoc task. This limited scope makes it difficult to assess the method's potential for broader applicability and overall impact.\n\n**\"Surpass Humans\" Claim Qualification:** The claim that augmented LMs surpass human performance needs stronger qualification. Details on human participants' prior experience, the number of trials per condition, and how performance compares when normalizing for computational resources (cost, latency, tokens) are necessary for a fair comparison. The large cost disparity is noted but not integrated into the primary win-rate comparisons.\n\n**Rationality Framing:** The paper frames the goal as building \"rational\" agents using Bayes-optimal principles (BED). However, human behavior often follows boundedly rational heuristics. The evaluation primarily uses game performance (win rate, F1) as a proxy for rationality, potentially conflating task success with optimal information processing under constraints.\n\n**Potential Scaffolding Effects:** The interaction between different components (question generation, answering, strategy selection, potential code generation for grounding) needs further ablation. It's unclear if performance gains could stem from implicit prompt leakage or interactions between modules rather than purely the Bayesian logic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "udnA0KafJk", "reviewer": "Reviewer_QbJw", "summary": "The present paper evaluates and improves the ability of LLMs to ask goal-directed questions and take actions in a dynamic environment. For this, the authors design a novel task called Collaborative Battleship. They run a human study on this task and compare human performance to that of various LLMs. This revealed a performance gap that the authors then subsequently address by developing Bayesian-inspired inference-time strategies for LLMs, leading to significant improvement in LLM performance.", "questions": "The indicator function in Equation 1 seems to be redundant (unless I am missing something).\n\nThe authors find that GPT-5 does not significantly benefit from Bayesian question or move selection. This raises the question of whether the proposed is useful for future models. Do you think that there is a risk of this being the case?\n\nI was a bit confused by the description of Equation 7. Why is \\pi_{t+1}^a introduced but then never used? Why p_{t+1}^{hit} defined as a distribution over questions? That seems strange. Why is u_t^* mentioned twice under step 2?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I enjoyed this paper a lot. It has all the ingredients for a great paper: a new task, human evaluation, a decent set of different models that are evaluated, a novel technique for improving models, and demonstration that the findings generalize to another domain. The paper was exceptionally well written and easy to follow. The method is clean and simple, yet effective. CaptainQA is an interesting agentic test bed for LLMs and the whole methodology fits thematically well into ICLR.", "weaknesses": "I found the usage of the term Bayes-rational weird. Best to my knowledge, this is not an accepted term in the literature. It implies that the strategies developed by the authors are Bayes-optimal, which is not the case (as also noted by the authors). To avoid this confusion, I would suggest using a different term instead.\n\nThere is not so much negative to say about the paper. Perhaps the only downside is that, while the results and methods are interesting, they are not groundbreaking. For me, that is the only reason for giving this paper a score of 8 (instead of the full 10).\n\nMinor:\n* RSA not defined (p9).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)