Tool Selection under Partial Observability
Abstract
An agent that may call a search API, a code interpreter, a calculator, or no tool at all is acting in a partially observable world: the hidden state includes facts the tools could reveal. We recall the POMDP belief update and the value of perfect information from Kaelbling, Littman, and Cassandra (1998), and we locate Toolformer (Schick et al., 2023) and ReAct (Yao et al., 2023) relative to that model. We do not claim that either system solves the POMDP. This editorial primer is an orientation, not a peer-reviewed research claim.
1. Tools as observation channels
A POMDP is a tuple $(S, A, O, T, Z, R, \gamma)$. The agent never sees $s \in S$; it sees observations $o \in O$ and maintains a belief $b \in \Delta(S)$. After action $a$ and observation $o$, Bayes’ rule gives
with $Z$ the observation kernel and $T$ the transition kernel (Kaelbling, Littman, and Cassandra, 1998, §2). The value of a belief is
In a tool-using agent the action set includes tool names. Calling a search tool is an action whose observation is a snippet; calling a code interpreter returns stdout; calling nothing returns the model’s own token. The hidden state includes the unknown answer, the true program behavior, and any unobserved world facts. That is a POMDP whether or not the implementation keeps an explicit $b$.
2. Value of information
The value of perfect information about a hidden coordinate $H$ at belief $b$ is
It is nonnegative. A myopic tool policy that calls tool $u$ when the expected reduction in loss exceeds the tool’s cost $c_u$ is using a one-step estimate of VPI, not $V^*$. That estimate is
for a myopic utility $U$, typically negative entropy or a downstream accuracy proxy.
Proposition 2 (standard, information-value). If $U$ is the expected reward of an optimal continuation, then $\widehat{\mathrm{VOI}}(b,u) \le V^*(b) - U(b)$ is not in general equal to the advantage of $u$ in $V^*$, because a tool call changes the future information state for many steps. Myopic VOI can refuse a costly tool that would unlock a later plan, and it can accept a cheap tool whose observation is screened off by a later cheaper observation.
We do not attribute this inequality to a single page of Kaelbling et al.; it is the ordinary distinction between one-step lookahead and the POMDP Bellman operator, which that paper develops.
3. What published tool-use systems actually do
Toolformer (Schick, Dwivedi-Yu, Dessì, Raileanu, Lomeli, Hambro, Zettlemoyer, Cancedda, and Scialom, 2023) fine-tunes a language model to insert API calls by self-supervision: a candidate call is kept when it reduces loss on the held-out tokens that follow. That is a myopic, corpus-level estimate of $\widehat{\mathrm{VOI}}$ with $U$ equal to log-probability of upcoming text. It is not an optimal POMDP policy, and the paper does not claim it is.
ReAct (Yao et al., 2023) prompts a model to emit interleaved thoughts and actions. There is no explicit belief state, no Bellman backup, and no VOI computation. The method is an empirical control loop. It can be compared to a POMDP planner as a baseline, not as an instance.
A multi-agent variant — several specialists exchanging messages — enlarges $A$ and $O$ but does not change the accounting. Littman (1994) formulates Markov games for simultaneous-move agents with observed state; once messages are partial, one is back in a POSG, which we do not analyze here. Generative Agents (Park, O’Brien, Cai, Morris, Liang, and Bernstein, 2023) store natural-language memories and retrieve them by embedding similarity. That retrieval is an observation channel. It is not a proven sufficient statistic for $b$.
4. A three-state numerical example
Let $S = \{s_0,s_1,s_2\}$ with $s_0$ the “unknown answer” state and $s_1,s_2$ two mutually exclusive facts. The prior is $b = (\tfrac12,\tfrac14,\tfrac14)$. Action $u$ (a search tool) costs $c_u = 0.1$ and, from $s_1$ or $s_2$, returns a distinguishing observation with probability $1$; from $s_0$ it returns an uninformative observation. Action $n$ (no tool) costs $0$ and yields no information. A downstream guess pays $1$ if the fact is named correctly and $0$ otherwise; guessing under $b$ without a tool has value $\max(1/4,1/4) = 1/4$ if the agent must name $s_1$ or $s_2$, and value $0$ if it may abstain — we take the abstain payoff to be $0$ and the informed payoff, after a distinguishing observation, to be $1$. Then
The myopic policy calls the tool. If the tool were noisy with $Z(\text{correct} \mid s_i,u) = 2/3$, the same arithmetic gives $0.5 \cdot (2/3) + 0.5 \cdot 0 - 0.1 \approx 0.233$, still positive. These numbers check the definition; they are not an empirical result about any API.
5. Evaluation discipline
A tool-use paper should report the tool set, the cost model (latency, money, or tokens), the observation interface, and a no-tool baseline. If the claim is planning quality, compare against a myopic VOI policy and, on small discrete instances, against an exact POMDP backup. If the claim is “the model learned to use tools,” Toolformer’s self-supervised insertion loss is the relevant ancestor, not $V^*$.
6. Limitations
We have recalled published definitions and refused two common identifications: Toolformer is not an optimal planner, and a retrieved memory is not a belief state. We have not solved a POSG, have not treated concurrent multi-tool calls, and have not measured any commercial API. Partial observability is a modeling choice; some tool traces are better described as fully observed MDPs with expensive actions.
References
1. Kaelbling, L. P., Littman, M. L., and Cassandra, A. R. Planning and acting in partially observable stochastic domains. Artificial Intelligence 101(1–2):99–134, 1998. 2. Schick, T., Dwivedi-Yu, J., Dessì, R., Raileanu, R., Lomeli, M., Hambro, E., Zettlemoyer, L., Cancedda, N., and Scialom, T. Toolformer: Language models can teach themselves to use tools. Advances in Neural Information Processing Systems, 2023. 3. Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., and Cao, Y. ReAct: Synergizing reasoning and acting in language models. International Conference on Learning Representations, 2023. 4. Littman, M. L. Markov games as a framework for multi-agent reinforcement learning. Proceedings of the 11th International Conference on Machine Learning, 1994. 5. Park, J. S., O’Brien, J. C., Cai, C. J., Morris, M. R., Liang, P., and Bernstein, M. S. Generative Agents: Interactive simulacra of human behavior. Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology, 2023.
This original editorial primer is an orientation, not a peer-reviewed research claim.