Reasoning about Reasoning by Nested Conditioning:
Modeling Theory of Mind with Probabilistic Programs
A. Stuhlmüllera , N. D. Goodmanba Department of Brain and Cognitive Sciences, Massachusetts Institute of Technologyb Department of Psychology, Stanford University

Abstract
A wide range of human reasoning patterns can be explained as conditioning in probabilistic models; however, conditioning has traditionally been viewed as an operation
applied to such models, not represented in such models. We describe how probabilistic
programs can explicitly represent conditioning as part of a model. This enables us todescribe reasoning about others’ reasoning using nested conditioning. Much of humanreasoning is about the beliefs, desires, and intentions of other people; we use probabilistic
programs to formalize these inferences in a way that captures the flexibility and inherent
uncertainty of reasoning about other agents. We express examples from game theory,
artificial intelligence, and linguistics as recursive probabilistic programs and illustrate
how this representation language makes it easy to explore new directions in each of thesefields. We discuss the algorithmic challenges posed by these kinds of models and describe
how Dynamic Programming techniques can help address these challenges.

1. Introduction
Reasoning about the beliefs, desires, and intentions of other agents—theory of mind —is a central part of human cognition and a critical challenge for human-like artificial
intelligence. Reasoning about an opponent is critical in competitive situations, whilereasoning about a compatriot is critical for cooperation, communication, and maintaining social connections. A variety of approaches have been suggested to explain humans’
theory of mind. These include informal approaches from philosophy and psychology,
and formal approaches from logic, game theory, artificial intelligence, and, more recently,
Bayesian cognitive science. Many of the older approaches neglect a critical aspect of human reasoning—uncertainty—while recent probabilistic approaches tend to treat theoryof mind as a special mechanism that cannot be described in a common representationalframework with other aspects of mental representation. In this paper, we discuss how
probabilistic programming, a recent merger of programming languages and Bayesianstatistics, makes it possible to concisely represent complex multi-agent reasoning scenarios. This formalism, by representing reasoning itself as a program, exposes an essential
contiguity with more basic mental representations.
Email addresses: ast@mit.edu (A. Stuhlmüller), ngoodman@stanford.edu (N. D. Goodman)
Preprint submitted to Elsevier
February 14, 2013

Probability theory provides tools for modeling reasoning under uncertainty: distributions formalize agents’ beliefs, conditional updating formalizes updating of beliefs basedon evidence or assertions. This approach can capture a wide range of reasoning patterns, including induction and non-monotonic inference. In cognitive science, probabilistic methods have been very successful at capturing aspects of human learning andreasoning [33]. However, the fact that conditioning is an operation applied to such models
and not itself represented in such models makes it difficult to accommodate full theory ofmind: We would like to view reasoning as probabilistic inference and reasoning about others’ reasoning as inference about inference; however, if inference is not itself represented
as a probabilistic model we cannot formulate inference about inference in probabilistic
terms.
Probabilistic programming is a new, and highly expressive, approach to probabilistic
modeling. A probabilistic program defines a stochastic generative process that can makeuse of arbitrary deterministic computation. In probabilistic programs, conditioning itself
can be defined as an ordinary function within the modeling language. By expressing
conditioning as a function in a probabilistic program, we represent knowledge about thereasoning processes of agents in the same terms as other knowledge. Because conditioning can be used in every way an ordinary function can, including composition with
arbitrary other functions, we may easily express nested conditioning: we can condition
any random variable, including random variables that are defined in terms of other conditioned random variables. Nested conditioning describes reasoning about reasoning andthis makes theory of mind amenable to the kind of statistical analysis that has been
applied to the study of mental representation more generally.
The probabilistic program view goes beyond other probabilistic views by extending
compositionality from a restricted model specification language to a Turing-complete
language, which allows arbitrary composition of reasoning processes. For example, themulti-agent influence diagrams proposed by Koller and Milch [18] combine the expressive
power of graphical models with the analytical tools of game theory, but their focus is not
on representing knowledge that players’ might have about other players’ reasoning.
From a philosophical perspective, the nested conditioning approach supports the ideathat the mental machinery underlying theory of mind is not necessarily a specialized
module. Instead, it can be expressed in, and potentially acquired from, more generalprimitives for representing the world and means of composing these primitives. Indeed,
the primitives needed to express conditioning as a probabilistic program are quite elementary: control structure, random choice, and recursive functions. This suggests that
representations needed for complex theory of mind may be more elementary than often
thought—though constructing and reasoning with these representations can be tricky.
The probabilistic programs we use here are essentially declarative probabilistic knowledge: they describe representations of (social) knowledge and inferences that follow, butthey do not describe the process of inference itself. That is, as models of human cognition, the models we present here should be seen as a computational-level descriptions[21]—a normative abstraction that helps understand what kind of problem the humanmind solves in social reasoning, not a proposal for a particular process or strategy used
to solve these problems. Indeed, there are significant challenges to even computing the
distributions implied by these models. We suggest algorithms for addressing the practical problems of modeling without intending to make a strong algorithmic claim abouthuman cognition.
2

In the following, we first present background on computational modeling using probabilistic programs, then show examples of how programs with nested conditioning concisely
express reasoning about agents in game theory, artificial intelligence, and linguistics. We
then describe the challenges in computing the predictions of these models. Finally, we
sketch a generic Dynamic Programming inference algorithm for probabilistic programsand explain how it can help address some of these practical challenges.
2. Representing distributions as probabilistic programs
A probabilistic program is a program in a universal programming language withprimitives for sampling from probability distributions, such as Bernoulli, Gaussian, andPoisson. Execution of such a program leads to a series of computations and random
choices. Probabilistic programs thus describe models of the stochastic generation of results, implying a distribution on return values. In our examples, we use Church [13],a probabilistic programming language based on the stochastic lambda calculus. This
calculus is universal in the sense that it can be used to define any computable discrete
probability distribution [6] (and indeed, continuous distributions when encoded via rational approximation).
Church is a close relative of the functional programming language Scheme [1]. In thislanguage, function application is written in prefix notation:(+ 3 2) → 5
The same applies to conditionals:(if (> 3 2) true false) → true
Functions are first-class values and can be defined using λ. For example,(λ (x) (* x 2)) → <function object>refers to a function that doubles its argument. Values can be bound to variables using
define and, for explicit scope, with let:
(let ([y 3]) (+ y 4)) → 7
For function definitions,(define (double x) (* x 2))
is short for:(define double (λ (x) (* x 2)))
The random primitive (flip p) samples from a Bernoulli distribution: it returns true
with probability p, false with probability 1−p. By composing random primitives such as
flip with deterministic computation, we can build complex distributions. For example,
the expression(sum (repeat 5 (λ () (if (flip .5) 0 1))))
induces the Binomial distribution shown in Figure 1. The meaning of a complex Church
program can be understood via its sampling semantics: a single execution returns asample from the distribution defined by the program; conversely, the histogram of (many)
samples from the program defines its distribution on return values.
A Church program describes knowledge with uncertainty, and can be used to capture
many effects of reasoning under uncertainty. As an example of reasoning under uncertainty, consider the following situation, depicted in Figure 2: We are presented with three
3

0.3
0.0

Probability

0

1

2

3

4

5

Figure 1: A Binomial(5, .5) distribution.
opaque urns, each of which contains some unknown number of red and black balls. We
do not know the proportion of red balls in each urn, and we don’t know how similar the
proportions of red balls are between urns, but we have reason to suspect that the urns
could be similar, as they all were filled at the same factory. We are asked to predictthe proportion of red balls in the third urn (1) before making any observations, (2) after
observing 15 balls drawn from the first urn, 14 of which are red, and (3) after observing
in addition 15 balls drawn from the second urn, only one of which is red.
Intuitively, observing the first 15 balls, almost all of which are red, has two plausible
explanations: either all urns have a high proportion of red balls, or all urns have differing
proportions of red balls and this particular urn happens to have a high proportion of redballs. We don’t know which of these is right and therefore have not learned about theoverall bias of the urns yet, but we can predict a higher proportion of red balls for urn
3. After we observe in addition 15 balls drawn from urn 2, almost all of which areblack, it becomes unlikely that all urns have similar proportions, hence our predictedproportion of red balls for urn 3 goes down again and we predict that the urns are biased
towards very high and very low proportions of red balls. Notice that this reasoning is
non-monotonic: our degree of confidence that “urns mostly contain red balls” goes up
with the first evidence, but decreases with the second evidence.
Figure 3 shows how to model this situation in Church. Figure 4 shows the predictions
derived from the model for conditions 1-3. In Church, conditional distributions aredefined using the query operator, which takes as arguments a list of definitions describing
a generative model, a query expression, and a condition, and which returns a sample fromthe conditional distribution. (This query syntax is much like the standard mathematicalnotation for conditionals, P (q|c), but makes the model explicit.) The predictions of themodel in Figure 3 match the non-monotonic intuition sketched above. More generally, awide range of reasoning patterns are naturally modeled as conditioning in probabilistic
models, including explaining away, screening off, and Occam’s razor [see 14].
In sharp contrast to less expressive modeling languages, and traditional statisticalnotation, conditioning is not a special primitive in Church. Figure 5 shows how to define
a generative model that samples from a conditional distribution. The procedure joint
draws samples from a prior distribution. The predicate condition? takes a sample andreturns true if the condition of interest holds. The function rejection-query simply
keeps on drawing samples from the prior until it encounters a sample that satisfies the4Condition 2

Condition 1

1

2

3

2

1

?

Condition 3

3
?

1

2

3
?

Figure 2: A simple scenario that requires reasoning under uncertainty: Drawing balls
from urns, we want to guess for each condition (1) whether and how the urns are biased
overall and (2) the likely proportion of red balls for the third urn.
condition, in which case it returns the sample. The critical difference from simpler languages is the ability to “keep sampling until”: marrying random choice with universal
computation enables stochastic recursion, which makes it simple to define the operationof conditioning. Of course, drawing conditional samples using rejection-query is very
inefficient when the probability of satisfying the condition is low. However, we can distinguish model specification from the process that is actually used to infer the distribution
implied by the model. From this point of view rejection-query is an elegant definitionof the distribution of interest, while the implementation we will use to compute this
distribution remains unspecified. Thus the practical problem of inference is the problem of efficiently computing the marginal distribution of a probabilistic program, i.e., its
distribution on return values.
3. Modeling theory of mind as nested conditioning
In the previous section we briefly sketched the probabilistic programming approachto capturing uncertain knowledge. We described how the operation of conditioning itself
could be represented as an ordinary function in Church, query. This representation
opens up an intriguing possibility: we can nest a call to the query function within othercalls to this function. If we view query as capturing reasoning, then such nested models
will capture reasoning about reasoning. We now illustrate how this approach can beused to capture multi-agent reasoning, using examples from game theory, linguistics,
and artificial intelligence.
3.1. Schelling coordination games
As a first illustration of our approach to theory of mind, consider a coordination
game of the kind discussed by Schelling [28]: Two agents, Alice and Bob, want to meet,
and they share the common knowledge that there are two possible meeting locations,one of them slightly more popular than the other. Each agent is modeled as making an
inference about where it would be best to go. This can be formalized as a conditional
distribution: “my location conditioned on my partner choosing the same location.” Since
each agent starts with the bias that the other agent is more likely to go to the more
popular place, they are yet more likely to go to this place themselves. This reasoning5

( query; ; model( define bias ( uniform 0 10) )( define red-bias ( uniform 0 bias ) )( define black-bias (- bias red-bias ) )( define urn->proportion-red( mem(λ ( urn )( first ( beta (+ .4 red-bias ) (+ .4 black-bias ) ) ) ) ) )( define ( sample-urn urn )( if ( flip ( urn->proportion-red urn ) )' red' black ) ); ; query expression( urn->proportion-red 3); ; condition( equal? ( repeat 15 (λ () ( sample-urn 1) ) )'( red red red red red red red red
red red red red red red black ) ) )Figure 3: A hierarchical model of urn draws in Church. This program formalizes reasoning about condition 2 of the urn scenario in Figure 2, implemented as conditional
sampling using the query operator. It takes as arguments a model (given as a sequenceof definitions), an expression of interest, and a condition (an expression that evaluates
to true or false). This model first samples a bias, splits the bias into red and black,and then defines how the urns’ proportions of red balls depend on the biases. The function urn->proportion-red is memoized such that it always returns the same proportion
when asked about the same urn. By contrast, the function sample-urn always flips a
new coin to determine whether to return a red or black ball, with the coin weighted by
the given urn’s proportion of red balls. Given this model, we sample the proportion of
red balls in the third urn conditioned on observing 1 black and 14 red draws from thefirst urn.

6Percent of Total

Condition 1

50

Condition 2

Condition 3

40
30
20
10
0
0

2

4

6

8

10 0

2

4

6

8

10 0

2

4

6

8

10

Inferred overall bias of the urns

Percent of Total

Condition 1

Condition 2

Condition 3

30
20
10
0
0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0

Predicted proportion of red balls in urn 3

Figure 4: Urn scenario predictions derived from the Church model in Figure 3. Before
seeing any draws, the model predicts uniform uncertainty about the overall bias, andmostly uniform uncertainty about the proportion of red balls in urn 3 (with extreme
values being a bit more likely). After seeing 15 balls drawn from urn 1, 14 of which are
red, the model still cannot judge how much the urns are biased, since it has seen only
draws from a single urn. However, it would predict that, if the urns are biased, they arebiased towards red, and therefore predicts that the proportion of red balls is likely to behigh for urn 3. After seeing an additional 15 balls from urn 2, 14 of which are black, themodel predicts that it is likely that the urns do not have directional bias, and predicts
that the balls in urn 3 are most likely to be either all red or all black, but with significant
probability on other proportions, since we have seen only two urns.

7

( define ( rejection-query joint condition? )( let ([ sample ( joint ) ])( if ( condition? sample )sample( rejection-query joint condition? ) ) ) )Figure 5: The conditioning operator query can be defined as a Church function. It takes
as arguments joint, a stochastic function without arguments that samples from a priordistribution, and condition?, a function that checks whether a given sample satisfies
the condition of interest. It calls itself recursively until it finds a sample that satisfies thecondition, which it then returns. The query syntax used in the remainder of the paper—
which takes as arguments a model, query expression, and condition—can be turned intoa call to rejection-query using a simple syntactic transform.

( define ( sample-location )( if ( flip .55)
' popular-bar' unpopular-bar ) )( define ( alice depth )( query( define alice-location ( sample-location ) )alice-location( equal? alice-location ( bob (- depth 1) ) ) ) )( define ( bob depth )( query( define bob-location ( sample-location ) )bob-location( or (= depth 0)( equal? bob-location ( alice depth ) ) ) ) )Figure 6: A Schelling coordination game in Church. Two agents, Alice and Bob, wantto meet. They choose which bar to go to by recursively reasoning about one another.

8

0.8
0.4
0.0

Probability

Popular bar
Unpopular bar

2

4

6

8

10

Depth of recursion
Figure 7: As the depth of recursive reasoning increases, the agents’ actions converge toa focal point in the Schelling coordination game shown in Figure 6.
proceeds recursively, increasing the chance that the agents will go to the popular place.
Each stage of this recursion is a conditional distribution.
This is an instance of planning as inference: we transform the problem of finding highutility actions into the problem of computing a conditional distribution. The problem ofmaximizing expected utility can generally be translated into a likelihood maximization
problem [34]. We are interested in modeling agents which choose only approximately
optimally. This can be achieved using softmax-optimal decision-making, where an action
a is chosen in proportion to its exponentiatedexpected utility under a belief distribution
P (s), i.e., P (a) ∝ exp αEP (s) [U (a; s)] . We follow this approach throughout this paper,
however we simplify by using a single-sample approximation to estimate the expectedutility, and assume a shared prior belief distribution, except where we note otherwise.
Figure 6 shows how to use the planning-as-inference idea to formalize recursive reasoning in the Schelling coordination game as a Church program. The parameter depth
controls the number of levels of recursive reasoning. Figure 7 shows how the marginal
distribution changes as a function of this parameter. As the depth increases, the agents’actions converge on the focal point of the game—they always go to the popular location.
This illustrates a common pattern when modeling agents using probabilistic programs,
namely the use of goal predicates instead of utility functions. It is possible to express
choice in proportion to utility explicitly (by conditioning on a coin flip with a weightcorresponding to the exponentiated utility of the outcome), but it is often equivalent todirectly condition on the desired outcome (goal). This results in concise models that are
intuitively appealing, since they match how we tend to think about our plans: not interms of an explicit ordering on outcomes, but as aimed at achieving particular goals.
Uncertainty, including uncertainty about other players’ uncertainty, can also be mod9

( define ( speaker access state depth )( query( define sentence ( sentence-prior ) )sentence( equal? ( belief state access )( listener access sentence depth ) ) ) )( define ( listener speaker-access sentence depth )( query( define state ( state-prior ) )state( if (= 0 depth )( sentence state )( equal? sentence( speaker speaker-access state (- depth 1) ) ) ) ) )Figure 8: Pragmatic reasoning in language understanding as recursively nested conditioning. For the full model specification, see appendix.
eled using the standard tools of game theory, but the strengths of these tools lie elsewhere(e.g., amenability to analysis with respect to equilibria). In a discussion of games withincomplete information, Kreps [20] writes:“If we wanted something really complex, we could imagine that player 3
has an assessment concerning player 2’s assessment of player 3’s assessmentof player 1’s utility function. (If you think this is painful to read, imagine
having to draw the corresponding extensive form.)”
Probabilistic programs make it easy to concisely express facts about other players’ state ofmind. For example, the coordination game can easily be modified to capture false beliefs(see appendix): Bob believes that Alice wants to meet him, and Alice knows this, but infact Alice wants to avoid Bob. The compositional nature of probabilistic programs allows
anything that can be expressed on its own to become the subject of others’ reasoning,
including agents’ beliefs and reasoning steps. This is key for accurately modeling theinteraction between agents who can represent other agents as intelligent reasoners.
3.2. Language understanding
Communication can be seen as a special case of decision-making in a multi-agent
context: a speaker chooses utterances given an intended interpretation, and a listenerchooses an interpretation given an utterance. We build on the rational speech-act theoryof language understanding [8]: listeners model speakers as choosing their utterances
approximately optimally based on social goals such as conveying information. Listeners
then interpret utterances by “inverting” this model using Bayesian inference and drawing
inferences about, among other things, the state of the world that caused the speaker tochoose this utterance. This can again be seen as an instance of planning as inference,
if we model the choice of utterances and interpretations as samples from conditional
distributions.
10

0.6

Speaker has full knowledge

Probability

Probability

Speaker has partial knowledge

0.4
0.2

0

1

2

3

0.6
0.4
0.2

0

Interpretation of “some”

1

2

3

Interpretation of “some”

Figure 9: Predictions of the language understanding model shown in Figure 8. Whenthe speaker has knowledge of the state of all 3 objects, the listener interprets “some” aslikey to imply “not all”. When the speaker has access to only 2 out of 3 objects, this
implicature is cancelled and “some” is compatible with referring to all objects.
The basic tenet of pragmatics is that listeners sometimes make inferences that differ
from those that directly follow from the literal meaning of an utterance. Consider thesentence “some of the apples are red.” In general, we take the speaker to mean that
not all of the apples are red. This effect is called a scalar implicature [16]. The rational
speech-act theory predicts that such effects are sensitive to the listener’s beliefs about
the speaker’s knowledge of the state of the world. For example, if there are three apples
in total, and if the speaker has only seen one of the apples (and it was red), then the
speaker’s utterance “some of the apples are red” does not imply that not all of them arered. This effect has been confirmed experimentally in Goodman and Stuhlmüller [12].
Figure 8 shows one way to model speaker and listener in this situation. The speakerchooses a sentence conditioned on the listener inferring the intended state of the world
when hearing this sentence; the listener chooses an interpretation conditioned on the
speaker selecting the given utterance when intending this meaning. After a few iterations(determined by the depth parameter), this mutual recursion bottoms out and the speaker
interprets the utterance literally, i.e., the speaker chooses an intended state conditionedon the given sentence being true of this state. Figure 9 shows model predictions thatmirror the implicature-cancelling effect found in experiments—the probability that all
three apples are red, after hearing “some of the apples are red,” is much less when the
speaker has seen all the apples.
The predicted interaction between the listener’s interpretation and the speaker’s
knowledge does not depend on the particular choice of words and intended meanings,
but is a more general result of the fact that the speaker is modeled as choosing words
based on expected utility. We can easily replace the set of words used in the model toderive predictions about pragmatic inferences in other contexts. We can also change theshared background knowledge to derive predictions for interpretations in other contexts,
all without changing the core model of language understanding. This is an example ofthe particular kind of modularity that results from representing agents and their mental11

( define ( exp-utility outcome player )( cond [( win? player outcome ) 1.0][( draw? outcome ) 0.1]
[ else 0.01]) )( define ( sample-action state player )( query( define action ( action-prior state ) )( define outcome ( sample-outcome state action player ) )action( flip ( exp-utility outcome player ) ) ) )( define ( sample-outcome state action player )( let ([ next-state ( transition state action player ) ])( if ( terminal? next-state )next-state( let ([ next-player ( other-player player ) ])( sample-outcome next-state( sample-action next-state next-player )next-player ) ) ) ) )( define start-state'((0 o 0)(o x x)(0 o 0) ) )( sample-action start-state 'x )Figure 10: Tic-tac-toe in Church. Each player chooses actions by sampling an action,
simulating the game until the end, and choosing actions in proportion to how likely they
are to lead to a successful outcome at the end of the game. This mental simulation
includes reasoning about both players’ reasoning at all future game steps, including theirreasoning about the other player. For the definition of functions such as action-priorand transition, see appendix.
content as functional probabilistic programs: A priori, different model parts are independent and can thus easily be replaced with alternatives. A posteriori, i.e., as the result ofconditioning, nontrivial dependencies between different model elements can arise, suchas those between speaker’s knowledge and listener’s interpretation.
3.3. Game playing
Theory of mind is an essential part of playing games such as chess and Go. Each
player chooses moves depending on their beliefs about the other players, including theirbeliefs about the other players’ beliefs. As in the Schelling coordination game, this kindof reasoning can be modeled using the planning-as-inference transformation: actions arechosen conditional on ultimately leading to a successful outcome. Whereas the Schelling
coordination game is a one-shot setting, many games require sequential decision-making.
12

C

D

0.0 0.2 0.4 0.6 0.8 1.0

BMarginal probability

A

A

B

C

D

Figure 11: Where should X move next? This plot shows the predictions derived from themodel in Figure 10. B and D are more likely to lead to a successful outcome, therefore
they are more likely to be chosen.
Moves made in one turn depend on the expected consequences for subsequent turns, andon each player’s decision-making strategy in subsequent turns.
As a simple example of a two-player game with sequential decision-making, consider
Tic-tac-toe. Figure 10 shows the core of a Church implementation of a player. Figure
11 shows a simple prediction by this model that matches our intuitions: in a situation
where X is not directly threatened and where X has two possible types of moves, one ofwhich opens up a double threat, the forking move will be chosen, as it allows X to win
two turns from now.
The player implemented in Church recursively reasons about the future moves ofanother player who implements the same strategy. In the first round, player X samples
an action conditioned on the game that starts with player X taking this action ultimately
leading to a win for player X. Sampling from this conditioned distribution requires asample from another conditioned distribution, namely from the distribution on player
O’s action in round two, which is conditioned on player O ultimately winning. This inturn depends on player X’s action in round three, and so on, until the game tree bottoms
out at a win for one of the players or at a draw.
The functions sample-action and sample-outcome make no mention of Tic-tac-toe
in particular—they are a fully generic implementation of approximately optimal decisionmaking in a setting where two players take turns. By supplying different implementations of functions such action-prior and transition, we can use the same framework
to model other games. This suggests that, to some extent, representation of players andgames can be studied independently, with interesting predictions arising from their interaction. For example, from a psychological perspective, one can ask whether and when aplayer model that judges actions by sampling a single outcome matches empirical data,
and when a more strongly optimizing model is more accurate.
Representing sequential decision-making in games as probabilistic programs naturally lends itself to interesting extensions. Instead of modeling both players as identicalthinkers, we can model their particular strategic tendencies, their potentially approximate evaluation of game states, their beliefs about who they are playing, and their process13( define ( agent t raised-hands others-blue-eyes )( query( define my-blue-eyes ( if ( flip baserate ) 1 0) )( define total-blue-eyes (+ my-blue-eyes others-blue-eyes ) )my-blue-eyes( and (> total-blue-eyes 0)(! (λ () (= raised-hands ( run-game 0 t 0 total-blue-eyes ) ) )2) ) ) )( define ( get-raised-hands t raised-hands true-blue-eyes )(+ ( sum-repeat (λ () ( agent t raised-hands (- true-blue-eyes 1) ) )true-blue-eyes )( sum-repeat (λ () ( agent t raised-hands true-blue-eyes ) )(- num-agents true-blue-eyes ) ) ) )( define ( run-game start end raised-hands true-blue-eyes )( if (>= start end )raised-hands( run-game (+ start 1)end( get-raised-hands start raised-hands
true-blue-eyes )true-blue-eyes ) ) )Figure 12: Church implementation of a stochastic version of the blue-eyed islanders
puzzle. For the full specification, see appendix.
of learning about the other player from past moves. This could be used, for instance,
to build computer opponents that reason about the human player’s state of mind andthat use sophisticated tactics such as “misleading the player,” not because such tactics
are built-in, but as a consequence of rational planning with a model that represents thehuman player’s model of the situation. This would have relatively little effect in a gamelike Tic-tac-toe, but an enormous effect in games like Go and Poker.
3.4. Induction puzzles
Induction puzzles are an instance of multi-agent reasoning that goes beyond thetwo-player case. Typically, induction puzzles describes a scenario involving multiple
agents that are all assumed to go through similar reasoning steps. In such a scenario,
the outcome can usually be determined inductively by first solving a simple case, thenassuming that all agents know the solution to this simple case, which in turn makes
another case simple to solve for all agents.
We consider a stochastic version of the blue-eyed islanders puzzle (also known as
the muddy children and cheating husbands problem), a well-known problem in epistemic
logic [9, 31]. The setup is as follows: There is a tribe on a remote island. Out of the npeople in this tribe, m have blue eyes. Their religion forbids them to know their own
eye color, or even to discuss the topic. Therefore, everyone sees the eye color of every
other islander, but does not know their own eye color. If an islander discovers their eye
14

Probability‘At least one of you has blue eyes.’
Day 1

Day 2

Day 3

Day 4

0.8
0.6
0.4
0.2
0.0
0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

Number of islanders announcing their eye color

Probability’‘At least one of you has blue eyes and a twitchy hand.’
Day 1

Day 2

Day 3

Day 4

0.6
0.4
0.2
0.0
0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

Number of islanders announcing their eye color

Figure 13: Model predictions for a stochastic version of the blue-eyed islanders puzzle
with population size 4, all islanders blue-eyed. Four days after the foreigner makes hisannouncement, the islanders are likely to realize that they have blue eyes. However, if
the foreigner (truthfully) states that one of the blue-eyed islanders has a twitchy handand mistakenly announces that she has blue eyes 10% of the time, this inference becomesmuch less pronounced.

15

color, they have to publicly announce this the next day at noon. All islanders are highly
logical. One day, a foreigner comes to the island and—speaking to the entire tribe—hetruthfully says: “At least one of you has blue eyes.” What happens next?
Intuitively, the solution is as follows. If there is only one islander with blue eyes, theislander will see that no other person has blue eyes and will announce their knowledge
the next day. If no islander does so the next day, then everyone knows that there are atleast two islanders with blue eyes. Since each of the two islanders with blue eyes only
observes one other blue-eyed islander, they can deduce that they must have blue eyes
themselves, and so the two blue-eyed islanders announce their eye colors on the secondday. Generalizing this line of reasoning, all m blue-eyed islanders announce their eye
color on the m-th day.
Figure 20 shows a formalization of a stochastic version of this puzzle. We have
converted a multi-agent sequential planning problem into an inference problem that uses
nested conditioning to model recursive reasoning. In this model, we have increased the
optimization strength of action selection in softmax-optimal sampling (α) by conditioning
on two successes instead of one, thus moving part of the way from probability matching
to utility maximization.
Figure 13 shows the corresponding model predictions for population size 4 when all
islanders are blue-eyed: on the 4th day, it is most likely that all islanders decide toannounce their eye color. In this version, the probability of an islander making theannouncement is proportional to their estimate for how likely they are to have blue eyes.
The induction that happens as a result of this conversion differs from the backwardsinduction in the previous section. In playing games, the current action is chosen basedon reasoning about the likely future outcome of the game, which depends on modelingthe other agents’ future reasoning. In this induction puzzle, the current action is chosen
based on current beliefs (“do I have blue eyes or not?”), which are the result of explaining
past observations (“how many islanders have made the announcement?”) by reasoning
about other agents’ past reasoning.
One of the main attractions of probabilistic programming as a modeling frameworkis that it is easy to rapidly prototype complex probabilistic models, since implementations of probabilistic programming languages provide generic inference algorithms; it is
not necessary to design model-specific algorithms. This is highly useful in multi-agent
scenarios, where complex interdependencies between agents’ conditional inferences canmake it difficult to “see” what the outcome of a model change is. For example, what if
the foreigner had said to the islanders: “At least one of you has blue eyes, and raises theirhand by accident 10% of the time.” Changing the model to account for this requires one
additional line of code (see appendix). The predictions are shown in Figure 13. It stilltakes four days for the islanders to realize with some uncertainty what their eye color is,but each islander is less certain and therefore less likely to make the announcement.
The idea of common knowledge is central to both versions of this induction puzzle.
Before the foreigner makes his announcement, every islander already knows that there is
at least one other islander with blue eyes simply by observing the others’ eye colors. By
speaking in front of the entire tribe, the foreigner causes this fact to become common
knowledge: now, everyone knows that everyone knows this fact, and everyone knows thateveryone knows that everyone knows, and so on. This idea is reflected in the Church
program by the condition (> total-blue-eyes 0). This condition applies both to theislander whose reasoning is modeled, to his mental model of other islanders’ reasoning,16

to the mental models of their mental models, and so on. If we remove this condition, theeffect of all islanders inferring their eye color on the m-th day goes away. By representing
this multi-agent reasoning scenario as a probabilistic program, we have formalized ahypothesis about what it means to have common knowledge, and we are able to explore
the implications of this hypothesis.
4. Inference algorithms
Probabilistic programs that use stochastic recursion to express nested conditioning
can represent a wide and flexible space of multi-agent reasoning, as described above,
but it can be difficult to compute the predictions of these models. We now explain thechallenges of computing the distributions defined by models with nested conditioning, andthen sketch a Dynamic Programming algorithm that addresses some of these challenges.
4.1. Multiply-intractable distributions
Given a probabilistic program, our goal is to estimate its distribution on return values. This is often easy for probabilistic programs without conditioning (i.e., without
query). For instance, when the expected program runtime is small, we can estimate the
distribution on return values using samples we get by repeatedly running the program.
However, when a program contains recursion the time it takes to run the program cangrow large even for small programs. Programs that contain a single level of conditioning implemented by rejection sampling already require in expectation 1/p recursive calls
when we condition on an event with probability p. Since it is common to condition
on low-probability events, this is often infeasible. For this reason, many algorithms forapproximately sampling from conditional distributions have been developed, including
Markov Chain Monte Carlo (MCMC), importance sampling, and variational methods.
Instead of directly attempting to sample from a program’s distribution on return
values, consider the goal of sampling from a program’s distribution on executions. An
execution corresponds to a complete sequences of random choices and determines a return
value. For an unconditioned program, the probability of an execution is the product of
all random choices that occur within this execution, and thus is easy to compute. For a
conditioned program, the probability of an execution is only proportional to this product,since the condition rules out some executions, redistributing their mass on the “allowed”
executions. Computing this probability exactly is often intractable, as it requires integrating over all program executions. Many algorithms for approximate inference require
only the unnormalized probability (i.e. the probability up to an unknown normalizing
constant). However, in the setting of nested conditioning, even the unnormalized probability can be difficult to compute.
For example, consider the program in Figure 14. This program could model thefollowing situation: Two agents play a game in which each agent needs to name a number
between 0 and 9 and they win if their numbers add up to 13. The first player knows
this, and he knows that the second player gets to see the number the first player chooses,
but the second player mistakenly thinks that the two win if their numbers add up to any
number greater than 8 (and the first player knows this as well). What number should
the first player choose?
17( query( define a ( sample-integer 10) )( define b( query( define c ( sample-integer 10) )c(> (+ a c ) 8) ) )a(= (+ a b ) 13) )Figure 14: A simple program with nested conditioning.
In this game, we can write the probability of a program state as follows:
p(a)p(b|a)δa+b=13 (a, b)
0
0 0
0 0
0
0
a0 ,b0 p(a )p(b |a )δa +b =13 (a , b )p(a, b|a + b = 13) = P∝ p(a)p(b|a)δa+b=13 (a, b)
Here, δa+b=13 (a, b) is the delta function that returns 1 if a + b = 13 is satisfied, otherwise
0. The distribution p(b|a) is itself defined in terms of a conditional distribution q:q(b|a)δa+b>8 (a, b)000b0 q(b |a)δa+b >8 (a, b )p(b|a) = q(b|a, a + b > 8) = P

Making use of the fact that p(a) and q(b|a) are uniformly distributed, the unnormalized
probability of a program state isδa+b=13 (a, b)p(a, b|a + b = 13) ∝ P.
00b0 δa+b >8 (a, b )Intuitively, this means that the probability of a state (a, b) is inversely proportional to
the number of assignments b0 that the second player could have chosen to make the sum
a + b0 greater than 8, since each such assignment reduces the chance that the second
player chooses the assignment that makes a + b = 13 true. The first player is best off
choosing a = 4, such that for the second player, the goal of making their sum greaterthan 8 coincides as much as possible with the goal of making their sum equal to 13.
From the perspective of inference, the relevant insight is that computing the unnormalized probability requires us to sum over the state space of the inner query. That is,even the unnormalized probability of the outer query depends on the normalizing constant of the inner query. While this is easy to compute for the given toy problem, it istypically difficult and makes inference in models with nested queries challenging.
To generalize this line of reasoning, assume that we are interested in sampling froma distributionp(y)δc1 (y)p(y|c1 ) = R∝ p(y)δc1 (y).
p(y)δc1 (y) dy
Here, y is a program state, c1 isR a condition on that state, p(y)δc1 (y) is the unnormalized probability of y, and Zy = p(y)δc1 (y) dy is the normalization constant.
18

Suppose that the distribution on program states p(y) factors as follows:p(y) = p(y1 , y2 ) = p(y1 )p(y2 |y1 )Assume further that p(y2 |y1 ) is defined in terms of a conditional distribution itself, i.e.,
we are describing a distribution defined in terms of a query within a query1 :p(y2 |y1 ) = q(y2 |y1 , c2 )=Rq(y2 |y1 )δc2 (y2 )q(y2 |y1 )δc2 (y2 ) dy2

Then, the unnormalized probability of a state y is:p(y|c1 ) ∝ p(y1 )p(y2 |y1 )δc1 (y)=p(y1 )q(y2 |y1 )δc2 (y2 )δc1 (y)R
q(y2 |y1 )δc2 (y2 ) dy2

Note that the denominator depends on y2 and thus on y. It affects the relative probabilities of different y and cannot be ignored, even if we are only interested in the unnormalized
probability. As a consequence, evaluation of unnormalized p(y|c1 ) requires integratingover the domain of y2 , which is often intractable. Since inference methods such as MCMC
are used to approximately sample from distributions that are “intractable” in the sensethat we cannot compute the normalization constant, models with nested conditioning
are called doubly-intractable.
Learning the parameters of a graphical model is an example of such a problem: foreach parameter setting, we need to integrate over the space of all explanations of thedata in order to compute a value proportional to the likelihood of the data. Whileauxiliary variable techniques can make sampling tractable in special cases [23], Murray
and Ghahramani [22] conjecture that for general undirected models, there exists notractable MCMC scheme that results in the correct stationary distribution.
Most of the examples we have seen define a nesting of conditional distributions ofdepth greater than 2. For such multiply-intractable distributions, the difficulty of evaluating f increases exponentially in the depth. If we assume that q(y2 |y1 ) factors into an
unconditioned and a conditioned distribution, and if we reason analogously to the steps
above, we conclude that naive computation of the unnormalized probability of a single
program execution y requires us to solve a multiple integral, thwarting existing methods
for approximate inference.
4.2. Dynamic Programming
Since existing methods of approximate inference are intractable for models with nested
query, we instead pursue exact inference methods that exploit shared subcomputation to
perform tractable inference for modestly sized state spaces. For example, Figure 15 showsthat the inference time for the language understanding model presented in Section 3.2
1 Note that in the term q(y |y , c ) there is an ambiguity: y is a parameter to this function, while
2 1 2
1
c2 is a condition. This is a common ambiguity in probability notation that is clarified in probabilistic
program notation.

19

5
4
3
1

2

Time (s)

1

2

3

4

5

6

7

Depth of recursive reasoning
Figure 15: Increase in dynamic programming inference time for the scalar implicaturemodel (Figure 8) as a function of nested conditioning depth. Each point on the plotcorresponds to a run of our algorithm on the model with a given depth.
grows linearly in the depth of nested conditioning, whereas expected inference time forrejection, and for MCMC with rejection for the inner queries, would grow exponentially.
All of the model predictions shown in Section 3 have been computed using this algorithm.
We present this dynamic programming algorithm as a practical tool for modeling, not as
an hypothesis about human processing; the structural insights this algorithm leverages,
however, may prove useful in future exploration of the processes of social cognition. We
next sketch this inference technique; for more technical background see Stuhlmüller andGoodman [30].
4.2.1. Approach
Our starting point is this: we are given an interpreter for a probabilistic programming
language and a probabilistic program, and we want to compute the marginal distributionof this program. In other words, we want to compute the distribution on return values
that we would sample from if we executed the program using this interpreter.
We assume that the interpreter is functional and defined recursively, i.e., in the processof evaluating a particular program, it calls itself and thus reduces the overall problemof evaluation to the problem of evaluating a number of smaller objects. Each of thesesubproblems has a unique distribution on solutions, and in the process of marginalization,some subproblems may occur multiple times. Our algorithm is based on the idea that we
can detect repeated, identical subproblems and that we can then solve each subproblem
only once, reusing the results for future occurrences of the same problem.
In Church, subproblems correspond to subexpressions with environments. For example, computing the marginal distribution of the Church program (and (flip) (or20

(flip) (flip))) involves computing the distribution of (flip) and of (or (flip)(flip)). In the setting of nested conditioning, the problem of computing the marginal
distribution of a query that contains other queries may be such that the same inner query
can be reused for many different settings of the parameters of the outer query.
To understand what makes marginalization with reuse of computation challenging,compare to simplified versions of the problem. If we were trying to ensure reuse of
repeated subcomputations for a deterministic interpreter, we could simply memoize it.
For a stochastic language, we could imagine a similar approach: use the interpreter torecursively compute and cache the distribution for each unique interpreter call, computing
all subdistributions required by a call before we compute the distribution of the callitself. However, consider the program shown in Figure 16. In order to compute the
distribution of the first if-branch of (game true), we need to know the distributionof (game (not true)), but this in turn depends on the distribution of (game true).
These self-recursive dependencies make direct caching impossible, as it would lead toinfinite regress. A similar pattern is present in queries that are defined via rejection
sampling. Our algorithm addresses this challenge by first transforming the program into
an intermediate structure that makes these dependencies explicit, then computing themarginal distribution from this structure in a way that is sensitive to the dependencies.
We first describe the interface the interpreter needs to satisfy such that we can use it
to acquire sufficient information about the program to build our intermediate structure.
We then present this structure and the steps of the algorithm.
By default, an interpreter takes a program and evaluates it, finally returning a single
value. In order to control the evaluation process in a way that lets us acquire information
about the structure of a program’s distribution, we require that the interpreter is acoroutine that interrupts its evaluation and returns its current state whenever it (1)makes a recursive subcall, (2) samples a primitive random choice, and (3) returns aterminal value. Each of these cases will correspond to a particular way of building
structure in our intermediate representation.
For our intermediate representation, we desire that it factors out all “deterministic” computation, leaving only probability calculations, i.e., sums and products, andthat it makes explicit the dependencies between the distributions resulting from subcomputations. Sum-product networks [26] satisfy the former requirement. We extend
the formalism to factored sum-product networks in order to satisfy the latter: A factored
sum-product network (FSPN) over variables x1 , . . . , xd is defined as a directed graph witha uniquely labeled root node r. The internal nodes are sums and products. The leaves areindicators x1 , . . . , xd and x̄1 , . . . , x̄d , and reference nodes (y, ~x), where y is another nodeand ~x a vector of indicator values. Each edge (i, j) from a sum node i has a non-negative
weight wij .
P Let Ch(y) denote the children of node
Q y. The value V(y, ~x) of a node y is defined as
w
V(z,
~
x
)
if
y
is
a
sum,
as
x) if y is a product, as 1~xj =xj if y isyzz∈Ch(y)z∈Ch(y) V(z, ~an indicator xj , and as V(z, w)~ if y is a reference (z, w).
~ We denote the factored sumproduct network F as a function of the indicator variables ~x = (x1 , . . . , xd , x̄1 , . . . , x̄d )by F (~x) = V(r, ~x). For any given ~x, the value of the FSPN is the solution to the systemof equations F (~x) (if a unique solution exists).
We use FSPNs to describe marginal distributions and indicators to query the probabilities of marginal values. To simplify notation, we write indicators as 1v , denoting the xi
21

0.0 0.2 0.4 0.6 0.8 1.0

Marginal probability

True( define ( game player )( if ( flip .6)( not ( game ( not player ) ) )( if player( flip .2)( flip .7) ) ) )p r 1 :T = .4 · .2 + .6 · p r 2 :F
p r 1 :F = .4 · .8 + .6 · p r 2 :T

p r 2 :T = .4 · .7 + .6 · p r 1 :F
p r 2 :F = .4 · .3 + .6 · p r 1 :F

( game true )(game true)(game false)

r1

r2

�

�

0.4

0.8

1F

�

0.2

False

0.6

0.4

�

�

1.0

1.0

0.3

1T

�

�

1T

r2 : F

1F

1F

r2 : T

0.7

0.6

�

1.0

1.0

1T

�

�

1T

r1 : F1F

r1 : T

Figure 16: An example of applying the Dynamic Programming algorithm to a simple
Church program. The program is compiled to a factored sum-product network, which
directly corresponds to a system of equations that can be solved to infer the marginal
distribution.
22

corresponding to value v. We write reference nodes as r : v, denoting (r, [0, 0, . . . , 0, 1, 0, . . . , 0]),where the only indicator entry that is 1 corresponds to value v. Negated indicators x̄iare not used by our algorithm.
In the following, we refer to “root nodes” in addition to the node types introduced
above. These nodes always have exactly one child and can hence be of either type sum
or product. The networks we build are sets of trees. Each node will be associated with aunique (ancestor) root node. Root nodes will correspond to subproblems. One of theseroot nodes is the root node referred to in the definition of a FSPN; it corresponds to theoverall problem of computing the marginal distribution of the starting state of the given
probabilistic program. In the illustration of the process our algorithm uses to build a
FSPN, we depict in addition to the previously built node nprev and the weight of theedge from this node to the current node, wprev , the root node r that is associated withthe previous and current node.
4.2.2. Algorithm
The algorithm proceeds in three steps. Figure 16 shows the result of applying eachof the steps to a simple self-recursive program. For pseudocode, see the appendix.
1. Compile program to FSPN.
We initialize the FSPN with a single node r. Our algorithm maintains a queue oftasks, each of which is a tuple of a thunk f (a function without arguments), a previous
node nprev , and an edge weight wprev (a probability). The queue is initialized to a task
for the first interpreter call, (λ.I(s), r, 1). While the queue is not empty, the algorithm
takes the first task in the queue and evaluates the function call f (). There are three
types of values that this function call can return: random choices, terminal values, andsubcalls. We manipulate FSPN and queue depending on the type of this value:
A random choice is a tuple (c, ~v , p~) of a continuation c, a list of values ~v , and a listof probabilities p~. The continuation c is a formal object that captures the current stateof the computation; it can be called with a value to resume evaluation. ~v and p~ specify
the distribution of the random choice
P where we interrupted evaluation. We modify the
FSPN by connecting a sum node
to nprev using wprev :rrn prevn prevw prevw prev�For each value-probability
pair, we then add to the queue the task of exploring c(v)Pwith previous nodeand edge weight p. This reflects the fact that the marginal
probability of any value under the current subproblem r is the sum of the probabilitiesof this value being returned for each of the ways of proceeding from the current program
state, weighted by the probability of choosing each such way.
23

A terminal value v is treated depending on whether it is a new value for current root
node r or whether it has been encountered before. If it has been encountered before, we
simply add an indicator node for this variable to the FSPN, reflecting that for a program
state that directly returns value v, the marginal probability is 1 for this value and 0
otherwise:rr

n prevn prevw prevw prevv

If we encounter v for the first time under root node r, this means that we just learned
something about the set of support values of the subproblem corresponding to r. If
this subproblem is used elsewhere, new parts of the program’s state space just became
accessible to us. To store where a subproblem is used, we associate a list of callbacks
with each root node. A callback is a pair of a node n (the node corresponding to theprogram state that referred to r’s subproblem) and a continuation c (for proceeding fromthat program state, given a return value for r’s subproblem). Given a new value v, we
can build graph structure and store a queue entry for each such callback, reflecting that
it is possible to continue from n with the
Q marginal probability of v under r. For every
callback (ni , ci ), we add a product node i and a reference node Q
r : v under node ni , andadd to the queue the task of exploring ci (v) with previous node i :rrn prevn1...

n prevnn

w prev

n1

...

nn

w prev
�v

Callbacks (n 1 , c 1 ), . . . , (n n , c n )associated with r .

r :v

�

1

n

r :v

A subcall is a pair of a continuation c and an interpreter argument s. This is where
we share repeated subcomputations: depending on whether we have seen s before or not,we proceed to explore this subcall and build graph structure, otherwise we simply referto existing structure.
P
If we encounter s for the first time, we connect a sum node
to nprev , reflectingthat the probability of any marginal value under r will be a sum of the probability ofthis value under all ways of continuing using different return values from subproblem s,
24

weighted by the probability of these return values. We also add a new root node rS to
the graph which represents the subproblem s and its marginal distribution:
rS

r

r

n prevn prevw prevw prev�

We add to the P
queue the task of exploring the interpreter call I(s) with previousP
node rS , and add ( , c) to the callbacks of rS such that graph structure underwill
be built if marginal values for I(s) are found.
P
under
If we have seen the interpreter argument s before, we also add a sum nodenprev , but then look up the existing root node rS for subproblem S. If marginal valuesforP this subproblem are already known, we can immediately build graph structure underthat refers to the marginal probability of these values, and we can explore the current
continuation c using thesevalue vi supported by S, we
Q values. For each known return P
build a product node i and reference node
r
:
v
under
and add to the queue theSiQtask of exploring c(vi ) with previous node .
rSrn prev

1v 1

...

rS

r
n prev

1v n

w prev

1v 1

...

1v n

w prev

v 1 . . . v n are values in the
support of subcomputation S.

�r S :v 1�...

�r S :v nP
As before, we also P
add ( , c) to the callbacks of rS in order to continue building
graph structure under
if more marginal values of rS are found in the future.
This process terminates once the queue is empty. Alternatively, it is possible to boundthe graph size, which results in lower bounds on the true marginal probabilities.
2. Convert FSPN to equations.
Following the value equations given in Section 4.2.1, we can directly convert a factored
sum-product network into a system of polynomial equations. In addition, it is sometimes
25possible to reduce the time spent in the next step by applying a simple substitution-based
equation simplifier.
3. Solve equations to get marginal distribution.
For probabilistic programs, the generated system of equations tends to be sparse,reflecting the fact that most interpreter calls that occur within the possible executionsof a program do not depend on most other calls. We therefore cluster the equations into
strongly connected components and solve the clusters of equations in topological order.
Computing a topological order of strongly connected components is linear in the size ofthe graph [32]. By solving in topological order we know that all probabilities required tocompute the solution of a component have been computed once we reach this component.
To solve components, we use fixed-point iteration and Newton’s method. Exploring theuse of other solution methods is a potential venue for future performance improvements.
In sum, the method described here involves creating an intermediate representation, a
FSPN, from a probabilistic program, which can then be efficiently solved to compute therequired distribution. This method often makes nested query models useful in practice:
we have used it for all of the examples above, and further evaluate it in comparison toother algorithms in Stuhlmüller and Goodman [30].
5. Discussion
Our approach to theory of mind is based on a long history of both informal andcomputational accounts of theory of mind [e.g., 35, 15, 5, 11]. For an outline of existing
logical and probabilistic approaches from the perspective of building cognitive architectures, see Bello [4]. While much of the relevant work on cognitive architectures aims totake into account resource constraints of the agents that are modeled, this is not our goal;
we have presented tools for computational-level modeling of agents’ reasoning in multiagent scenarios. Such models constitute a normative standard that can be comparedto actual patterns in human reasoning, which in turn may help us devise process-leveldescriptions of the same phenomena.
Most directly, we build on the Bayesian approach to theory of mind [2, 3], which takes
the principle of rational action to be central to the concept of intentional agency: all else
being equal, agents are expected to choose actions that satisfy their goals as effectively
as possible. Given a probabilistic generative model of an agent’s planning process thathas this property, and given observations, Bayesian theory of mind simply proposes that
we can infer the hidden internal states of the agent—beliefs, desires, and goals—by
inverting this model, i.e., by conditioning. By viewing conditioning as a function thatis represented in a probabilistic program, we have presented a simple, unified formalism
for implementing Bayesian theory of mind, and for extending it to settings such as therecursive reasoning scenarios presented in this paper.
Philosophically, our approach suggests that it may be possible to acquire the mental
machinery for theory of mind from simpler primitives such as control structure, random
choice, and recursive functions. Specialized mental modules—such as a “belief box” anda “desire box” [24]—might arise simply as a consequence of an agent’s attempt to explain
her observations in a parsimonious way, or might not turn out to be necessary to explain
our cognitive capabilities in the first place.
26

The proposed inference algorithm is related to and inspired by a long tradition ofalgorithms which use dynamic programming to exploit reusable structure in the natural
language processing, logic programming, and functional programming literatures. For
example, it is known that, in general, exactly solving problems such as marginalization for
arbitrary recursive programs leads to systems of nonlinear equations [see, e.g., commentsin 7]. Klein and Manning [17] exploit strongly connected components of the computationgraph for PCFGs to perform efficient exact marginalization in a way similar to the present
algorithm. It is beyond the scope of this paper to review the many connections withindividual algorithms presented in the literature. Instead, we focus on three systems
which attempt to use dynamic programming to provide general inference algorithms foruniversal, probabilistic (or, more generally, weighted) programming languages: IBAL,PRISM, and Dyna.
The most closely related system to the present work is the functional programming
language IBAL, a probabilistic variant of ML [25]. IBAL provides an exact marginalization algorithm for discrete probabilistic models, which is based on a generalizationof variable elimination applied to computation graphs. The graph used by this algorithm also exploits sharable subcomputations across the evaluation of the probabilistic
program. However, the present algorithm is more general than the IBAL algorithm in
an important way. The IBAL algorithm relies on acyclic computation graphs; this isequivalent to the requirement that the computation be evidence-finite [19]—there must
only be a finite number of computations which can give rise to the observed evidence.
By contrast, our algorithm handles many cases of evidence-infinite computation. For example, the simple recursive program shown in Figure 16, which has finite support {true,
false} but an infinite number of computations which give rise to each support value,cannot be marginalized by IBAL, but is correctly handled by our algorithm. Practicalexamples of such evidence-infinite computations include many of the nested-query models
for multi-agent reasoning that we have described above.
Another system which is similar to the present work is PRISM, a probabilistic generalization of Prolog, which also makes use of dynamic programming to provide a generalinference algorithm. Although PRISM is able to recover many standard algorithms forproblems such as PCFG estimation (e.g., the inside-outside algorithm), like IBAL, it
cannot handle evidence-infinite computations [27].
A somewhat different approach is Dyna [7], a programming language for expressing
weighted deductive logic programs. Dyna makes use of generalizations of parsing-asdeduction [29] and semi-ring parsing [10] to compile weighted logic programs into highly
optimized dynamic programs. Dyna differs from our algorithm in the target level ofabstraction. Our algorithm is focused on the problem of rapid prototyping of models
for which no standard dynamic programming algorithm exists. The programmer simply provides an interpreter, and our algorithm automatically exploits whatever sharing
is exposed by the structure of the recursive calls made in the process of computing
the marginal distribution for a particular model. By contrast, Dyna is a language for
abstractly expressing specific dynamic programming algorithms and compiling these algorithms to highly efficient code. It allows the programmer lower-level control overalgorithm specification, but it also requires the programmer to specify these algorithmic
details.

27

6. Conclusion
We have described how probabilistic programs can represent multi-agent scenarios
by modeling each agent’s reasoning as conditional sampling. Since conditioning is anoperation that can be defined within such models, it can become the subject of otheragents’ reasoning. This representation goes beyond existing formalisms, such as graphicalmodels, where conditioning is more naturally seen as an operation that is applied to amodel, but not itself represented. We have discussed inference challenges posed by thismodeling technique and sketched a Dynamic Programming algorithm that can provide
tractable inference for small state spaces by merging identical subproblems.
There are many research opportunities related to this way of studying theory ofmind, both regarding modeling and algorithms. For modeling, one avenue is to translate
existing models used in fields such as game theory and linguistics into the frameworkof probabilistic programs. Extensions of these models that are difficult to express using
existing modeling languages, but that are natural using this new approach, will suggest
themselves. Further, integration of diverse aspects of social cognition will be fosteredby representing them in a common representational system—libraries of probabilistic
program components for cognition can be naturally integrated into a more complete
architecture.
At the algorithmic level, it seems likely that exact inference will not scale to models
with realistic state spaces. This poses the practical question of finding approximate
inference algorithms that work in the setting of nested queries, and the scientific questionof understanding how humans cope with the same. For some versions of these problems,
scalable algorithms have already been introduced; for example, Monte Carlo tree searchfor playing the board game Go. It may be possible to construct inference algorithms
for probabilistic programs that reduce to such known algorithms in restricted settings.
Conversely, studying the psychological process of inference—which may implicate parallel
processing, simulation, and significant resource bounds—may suggest new algorithms tosolve the engineering challenges of inference.
Viewing theory of mind as reasoning about reasoning and formalizing this as nested
conditioning is appealing on both philosophical and scientific grounds. By realizing theory of mind in a uniform representational framework for reasoning under uncertainty, we
expose essential assumptions and provide opportunities for constructing more complex,
and realistic, models of social reasoning.
Acknowledgements
We thank John McCoy, Thomas Icard, and Lewis Fishgold for comments; Daniel
Roy and Timothy O’Donnell for contributions to early stages of work on the proposed
algorithm; and ONR grant N00014-09-0124 for funding.
References[1] H. Abelson and G. J. Sussman. Structure and Interpretation of Computer Programs. MIT Press,
Cambridge, MA, USA, 2nd edition, 1996. ISBN 0262011530.
[2] C. Baker, J. Tenenbaum, and R. Saxe. Bayesian models of human action understanding. Advancesin Neural Information Processing Systems, 18:99, 2006.

28

[3] C. L. Baker, R. R. Saxe, and J. Tenenbaum. Bayesian theory of mind: Modeling joint belief-desire
attribution. Proceedings of the Thirty-Second Annual Conference of the Cognitive Science Society,
2011.
[4] P. Bello. Cognitive Foundations for a Computational Theory of Mindreading. Advances in Cognitive
Systems.
[5] P. Bello and N. Cassimatis. Developmental accounts of theory-of-mind acquisition: Achieving clarity
via computational cognitive modeling. 28th Annual Conference of the Cognitive Science Society,
Vancouver, Canada, 2006.
[6] U. Dal Lago and M. Zorzi. Probabilistic Operational Semantics for the Lambda Calculus. RAIRO- Theoretical Informatics and Applications, (46):413–450, 2012.
[7] J. Eisner, E. Goldlust, and N. A. Smith. Compiling comp ling: Practical weighted dynamic programming and the dyna language. In Proceedings of Human Language Technologies and the Conferenceon Empirical Methods in Natural Language Processing (HLT/EMNLP), 2005.
[8] M. C. Frank and N. Goodman. Predicting Pragmatic Reasoning in Language Games. Science, 336(6084):998–998, May 2012.
[9] G. Gamow and M. Stern. Puzzle-math, 1958.
[10] J. Goodman. Semiring parsing. Computational Linguistics, 25(4), 1999.
[11] N. Goodman, C. L. Baker, E. B. Bonawitz, V. K. Mansinghka, A. Gopnik, H. Wellman, L. Schulz,
and J. Tenenbaum. Intuitive theories of mind: A rational approach to false belief. Proceedings ofthe twenty-eighth annual conference of the cognitive science society, pages 1382–1387, 2006.
[12] N. D. Goodman and A. Stuhlmüller. Knowledge and implicature: Modeling language understanding
as social cognition. In Proceedings of the Thirty-Fourth Annual Conference of the Cognitive Science
Society, 2012.
[13] N. D. Goodman, V. Mansinghka, D. M. Roy, K. Bonawitz, and J. B. Tenenbaum. Church: alanguage for generative models. Proceedings of the 24th Conference in Uncertainty in Artificial
Intelligence, pages 220–229, 2008.
[14] N. D. Goodman, J. B. Tenenbaum, T. J. O’Donnell, and the Church Working Group. Probabilistic
models of cognition, 2011. URL http://projects.csail.mit.edu/church/wiki/Church.
[15] A. Gopnik, A. N. Meltzoff, NetLibrary, and Inc. Words, thoughts, and theories. 1998.
[16] L. R. Horn. Implicature. In The Handbook of Pragmatics. Blackwell Publishing Ltd, Oxford, UK,
Jan. 2006.
[17] D. Klein and C. D. Manning. An O(n3 ) agenda–based chart parser for arbitrary probabilistic
context–free grammars. Technical report, Stanford University, 2001.
[18] D. Koller and B. Milch. Multi-agent influence diagrams for representing and solving games. Gamesand Economic Behavior, 45(1):181–221, 2003.
[19] D. Koller, D. McAllester, and A. Pfeffer. Effective bayesian inference for stochastic programs. In
Proceedings of the National Conference on Artificial Intelligence, pages 740–747, 1997.
[20] D. M. Kreps. A Course in Microeconomic Theory. pages 1–859, Oct. 2011.
[21] D. Marr. Vision: A computational investigation into the human representation and processing ofvisual information. Henry Holt and Co., Inc. New York, NY, USA, Jan 1982.
[22] I. Murray and Z. Ghahramani. Bayesian learning in undirected graphical models: approximate
MCMC algorithms. Proceedings of the 20th conference on Uncertainty in artificial intelligence,
pages 392–399, 2004.
[23] I. Murray, Z. Ghahramani, and D. MacKay. Mcmc for doubly-intractable distributions. Proceedingsof the 22nd Annual Conference on Uncertainty in Artificial Intelligence (UAI), pages 359–366,
2006.
[24] S. Nichols and S. P. Stich. Mindreading: An Integrated Account of Pretence, Self-Awareness, andUnderstanding Other Minds. Oxford University Press, USA, Oct. 2003.
[25] A. Pfeffer. IBAL: A probabilistic rational programming language. In Proceedings of the International Joint Conferences on Artificial Intelligence, 2001.
[26] H. Poon and P. Domingos. Sum-product networks: A new deep architecture. Proc. 12th Conf. on
Uncertainty in Artificial Intelligence, pages 337–346, 2011.
[27] T. Sato. Generative Modeling by PRISM. In P. Hill and D. Warren, editors, Logic Programming,volume 5649 of Lecture Notes in Computer Science, chapter 4, pages 24–35. Springer, Berlin,
Heidelberg, 2009. ISBN 978-3-642-02845-8. doi: 10.1007/978-3-642-02846-5\ 4.
[28] T. C. Schelling. The Strategy of Conflict. Harvard University Press, 1960.
[29] S. M. Shieber, Y. Schabes, and F. C. N. Pereira. Principles and implementation of deductive
parsing. The Journal of Logic Programming, 24(1-2):3–36, 1995.
[30] A. Stuhlmüller and N. D. Goodman. A dynamic programming algorithm for inference in recursive

29

probabilistic programs. 2012.
[31] T. Tao. Poincaré’s Legacies. Pages from Year Two of a Mathematical Blog. Amer MathematicalSociety, 2009.
[32] R. Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1(2):146–160, 1972.
[33] J. B. Tenenbaum, C. Kemp, T. L. Griffiths, and N. D. Goodman. How to grow a mind: Statistics,
structure, and abstraction. Science, 331(6022):1279–1285, 2011.
[34] M. Toussaint, S. Harmeling, and A. Storkey. Probabilistic inference for solving (PO) MDPs. Institutefor Adaptive and Neural Computation, 2006.
[35] H. M. Wellman. The child’s theory of mind. The MIT Press, Oct. 1992.

30

Appendix( define ( sample-location )( if ( flip .55)
' popular-bar' unpopular-bar ) )( define ( alice* depth )( query( define alice*-location ( sample-location ) )alice*-location( not ( equal? alice*-location ( bob (- depth 1) ) ) ) ) )( define ( alice depth )( query( define alice-location ( sample-location ) )alice-location( equal? alice-location ( bob (- depth 1) ) ) ) )( define ( bob depth )( query( define bob-location ( sample-location ) )bob-location( or (= depth 0)( equal? bob-location ( alice depth ) ) ) ) )( alice* 5)

Figure 17: A version of the Schelling coordination game with false beliefs: Bob believes
that Alice wants to meet him, and Alice knows this, but in fact Alice wants to avoid
Bob.

31

( define ( belief actual-state access )( map (λ ( ac st pr ) ( if ac st ( sample pr ) ) )accessactual-state( substate-priors ) ) )( define ( baserate ) 0.8)
( define ( substate-priors )( list (λ () ( flip ( baserate ) ) )(λ () ( flip ( baserate ) ) )(λ () ( flip ( baserate ) ) ) ) )( define ( state-prior )( map sample ( substate-priors ) ) )( define ( sentence-prior )( uniform-draw ( list all-p some-p none-p ) ) )( define ( all-p state ) ( all state ) )( define ( some-p state ) ( any state ) )( define ( none-p state ) ( not ( some-p state ) ) )( define ( speaker access state depth )( query( define sentence ( sentence-prior ) )sentence( equal? ( belief state access )( listener access sentence depth ) ) ) )( define ( listener speaker-access sentence depth )( query( define state ( state-prior ) )state( if (= 0 depth )( sentence state )( equal? sentence( speaker speaker-access state (- depth 1) ) ) ) ) )( define ( num-true state )( sum ( map (λ ( x ) ( if x 1 0) ) state ) ) ); ; without full knowledge:( num-true ( listener '(# t # t # f ) some-p 5) ); ; with full knowledge:( num-true ( listener '(# t # t # t ) some-p 5) )Figure 18: A model for pragmatic inferences like “some implies not-all.”32

( define ( valid−move? move s t a t e )( e q u a l ? ( l i s t − r e f ( l i s t − r e f s t a t e ( f i r s t move ) )( s e c o n d move ) )0) )( define ( a c t i o n − p r i o r s t a t e )( query( define a c t i o n ( l i s t ( s a m p l e − i n t e g e r 3 ) ( s a m p l e − i n t e g e r 3 ) ) )action( valid−move? a c t i o n s t a t e ) ) )( define ( t r a n s i t i o n s t a t e a c t i o n p l a y e r )( map ( λ ( row i )( map ( λ ( s j )( if ( e q u a l ? ( l i s t i j ) a c t i o n )players))row( i o t a ( l e n g t h row ) ) ) )state( iota ( length state ) ) ) )( define ( d i a g 1 s t a t e )( map ( λ ( x i ) ( l i s t − r e f x i ) )state ( iota ( length state ) ) ) )( define ( d i a g 2 s t a t e )( let ( [ l e n ( l e n g t h s t a t e ) ] )( map ( λ ( x i ) ( l i s t − r e f x (− l e n (+ i 1 ) ) ) )state ( iota len ) ) ) )( define ( win? p l a y e r s t a t e )( let ( [ c h e c k ( λ ( e l t s ) ( a l l ( map ( λ ( x ) ( eq? x p l a y e r ) ) e l t s ) ) ) ] )( any ( map c h e c k( l i s t ( f i r s t s t a t e ) ( second s t a t e ) ( t h i r d s t a t e )( map f i r s t s t a t e ) ( map s e c o n d s t a t e ) ( map t h i r d s t a t e )( diag1 s t a t e ) ( diag2 s t a t e ) ) ) ) ) )( define ( f l a t t e n l s t )( a p p l y append l s t ) )( define ( t e r m i n a l ? s t a t e )( a l l ( map ( λ ( x ) ( not ( e q u a l ? x 0 ) ) )( flatten state ) ) ) )( define ( o t h e r − p l a y e r p l a y e r )( if ( eq? p l a y e r ' x ) ' o ' x ) )( define ( draw? outcome )( and ( not ( win? ' x outcome ) )( not ( win? ' o outcome ) ) ) )Figure 19: Helper functions for the Tic-tac-toe game.

33

( define num-agents 4)( define baserate .045)( define (! thunk n )( if (= n 0)
true
( and ( thunk ) (! thunk (- n 1) ) ) ) )( define (% sum-repeat proc n s )( if (= n 0)s(% sum-repeat proc(- n 1)(+ s ( proc ) ) ) ) )( define ( sum-repeat proc n )(% sum-repeat proc n 0) )( define ( agent t raised-hands others-blue-eyes )( query( define my-blue-eyes ( if ( flip baserate ) 1 0) )( define total-blue-eyes (+ my-blue-eyes others-blue-eyes ) )my-blue-eyes( and (> total-blue-eyes 0)(! (λ () (= raised-hands ( run-game 0 t 0 total-blue-eyes ) ) )2) ) ) )( define ( get-raised-hands t raised-hands true-blue-eyes )(+ ( sum-repeat (λ () ( agent t raised-hands (- true-blue-eyes 1) ) )true-blue-eyes )( sum-repeat (λ () ( agent t raised-hands true-blue-eyes ) )(- num-agents true-blue-eyes ) ) ) )( define ( g et - ra is e d- h an ds / tw i tc h t raised-hands true-blue-eyes )(+ ( sum-repeat (λ () ( agent t raised-hands (- true-blue-eyes 1) ) )(- true-blue-eyes 1) )( sum-repeat (λ () ( agent t raised-hands true-blue-eyes ) )(- num-agents (+ true-blue-eyes ) ) )( if ( flip .1) 1 ( agent t raised-hands (- true-blue-eyes 1) ) ) ) )( define ( run-game start end raised-hands true-blue-eyes )( if (>= start end )raised-hands( run-game (+ start 1)end( get-raised-hands start raised-hands
true-blue-eyes )true-blue-eyes ) ) )( run-game 0 4 0 4)

34
Figure 20: Church implementation of a stochastic version of the blue-eyed islanders
puzzle. This code includes an alternative implementation of get-raised-hands for thesetting where the foreigner announces (truthfully) that one of the blue-eyed islanders
sometimes raises her hand by accident.

procedure BuildFSPN(I, xinit )G = Graph()r = G.addNode(root)
Q = [(λ.I(xinit ), r, 1.0)]
terminals, callbacks, subproblem = {}, {}, {}while Q is not empty do(f, nprev , wprev ) = Q.pop()
x = f ()
if x is a value v thenncur = G.addNode(indicator, v)
r = G.root[nprev ]if v ∈/ terminals[r] thenfor all (n0 , c) in callbacks[r] doprocessTerminal(G, Q, r, v, n0 , c)end forterminals[r].add(v)end ifelse if x is a random choice (c, ~v , p~) thenncur = G.addNode(sum)for all v, p ∈ ~v , p~ do
Q.enqueue(λ.c(v), ncur , p)
end forelse if x is a subcall (c, s) thenncur = G.addNode(sum)if s ∈/ subproblem.keys() thenr = G.addNode(root)
subproblem[s] = r
Q.enqueue(λ.I(s), r, 1.0)else
r = subproblem[s]for all v ∈ terminals[r] doprocessTerminal(G, Q, r, v, ncur , c)end forend ifcallbacks[r].add((ncur , c))end ifG.addEdge(nprev , ncur , wprev )end whilereturn G
end procedure
procedure ProcessTerminal(G, Q, nroot , v, nprev , c)nprod = G.addNode(product)
nref = G.addNode(ref, nroot , v)
G.addEdge(nprev , nprod , 1.0)
G.addEdge(nprod , nref , 1.0)
Q.enqueue(λ.c(v), nprod , 1.0)
end procedure

Figure 21: Compiling probabilistic programs to factored sum-product networks.
35