Information-Theoretic Bounded Rationality
Pedro A. Ortega

ope@seas.upenn.edu

University of Pennsylvania
Philadelphia, PA 19104, USA

arXiv:1512.06789v1 [stat.ML] 21 Dec 2015

Daniel A. Braun

daniel.braun@tuebingen.mpg.de

Max Planck Institute for Intelligent Systems
Max Planck Institute for Biological Cybernetics
72076 Tübingen, Germany

Justin Dyer

jsdyer@google.com

Google Inc.
Mountain View, CA 94043, USA

Kee-Eung Kim

kekim@cs.kaist.ac.kr

Korea Advanced Institute of Science and Technology
Daejeon, Korea 305-701

Naftali Tishby

tishby@cs.huji.ac.il

The Hebrew University
Jerusalem, 91904, Israel

Abstract
Bounded rationality, that is, decision-making and planning under resource limitations,
is widely regarded as an important open problem in artificial intelligence, reinforcement
learning, computational neuroscience and economics. This paper offers a consolidated presentation of a theory of bounded rationality based on information-theoretic ideas. We
provide a conceptual justification for using the free energy functional as the objective function for characterizing bounded-rational decisions. This functional possesses three crucial
properties: it controls the size of the solution space; it has Monte Carlo planners that are
exact, yet bypass the need for exhaustive search; and it captures model uncertainty arising
from lack of evidence or from interacting with other agents having unknown intentions.
We discuss the single-step decision-making case, and show how to extend it to sequential
decisions using equivalence transformations. This extension yields a very general class of
decision problems that encompass classical decision rules (e.g. Expectimax and Minimax)
as limit cases, as well as trust- and risk-sensitive planning.

c December 2015 by the authors. All rights reserved.

Ortega et al.

Contents
1 Introduction
1.1 A Short Algorithmic Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
4
6

2 Preliminaries in Expected Utility Theory
2.1 Variational principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Subjective expected utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Two open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7
7
8
10

3 The
3.1
3.2
3.3

Mathematical Structure of Boundedness
12
Meta-reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Incomplete Information and Interrupted Deliberation . . . . . . . . . . . . . . . . . . . . . . . 13
Commensurability of utility and information . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4 Single-Step Decisions
4.1 Bounded-rational decisions
4.2 Stochastic choice . . . . . .
4.3 Equivalence . . . . . . . . .
4.4 Comparison . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

18
18
20
24
27

5 Sequential Decisions
5.1 Bounded-rational decision trees . . . . .
5.2 Derivation of the free energy functional
5.3 Bellman recursion and its solution . . .
5.4 Recursive rejection sampling . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

28
29
32
34
35

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

6 Discussion
38
6.1 Relation to literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.2 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
A Proofs
A.1 Proof to Theorem 2

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

41
41

Information-Theoretic Bounded Rationality

1. Introduction
It is hard to overstate the influence that the economic idea of perfect rationality has had
on our way of designing artificial agents [Russell and Norvig, 2010]. Today, many of us
in the fields of artificial intelligence, control theory, and reinforcement learning, design our
agents by encoding the desired behavior into an objective function that the agents must
optimize in expectation. By doing so, we are relying on the theory of subjective expected
utility (SEU), the standard economic theory of decision making under uncertainty [Von
Neumann and Morgenstern, 1944, Savage, 1954]. SEU theory has an immense intuitive
appeal, and its pervasiveness in today’s mindset is reflected in many widely-spread beliefs:
e.g. that probabilities and utilities are orthogonal concepts; that two options with the same
expected utility are equivalent; and that randomizing can never improve upon an optimal
deterministic choice. Put simply, if we find ourselves violating SEU theory, we would feel
strongly compelled to revise our choice.
Simultaneously, it is also well-understood that SEU theory prescribes policies that are
intractable to calculate save for very restricted problem classes. This was recognized soon
after expected utility theory was formulated [Simon, 1956]. In agent design, it became especially apparent more recently, as we continue to struggle in tackling problems of moderate
complexity in spite of our deeper understanding of the planning problem [Duff, 2002, Hutter,
2004, Legg, 2008, Ortega, 2011] and the vast computing power available to us. For instance,
there are efficient algorithms to calculate the optimal policy of a known Markov decision
process (MDP) [Bertsekas and Tsitsiklis, 1996], but no efficient algorithm to calculate the
exact optimal policy of an unknown MDP or a partially observable MDP [Papadimitriou
and Tsitsiklis, 1987]. Due to this, in practice we either make severe domain-specific simplifications, as in linear-quadratic-Gaussian control problems [Stengel, 1994]; or we approximate
the “gold standard” prescribed by SEU theory, exemplified by the reinforcement learning
algorithms based on stochastic approximations [Sutton and Barto, 1998, Szepesvári, 2010]
and Monte-Carlo tree search [Kocsis and Szepesvári, 2006, Veness et al., 2011, Mnih et al.,
2013].
Recently, there has been a renewed interested in models of bounded rationality [Simon, 1972]. Rather than approximating perfect rationality, these models seek to formalize
decision-making with limited resources such as the time, energy, memory, and computational
effort allocated for arriving at a decision. The specific way in which this is achieved varies
across these accounts. For instance, epsilon-optimality only requires policies to be “close
enough” to the optimum [Dixon, 2001]; metalevel rationality proposes optimizing a trade-off
between utilities and computational costs [Zilberstein, 2008]; bounded optimality restricts
the computational complexity of the programs implementing the optimal policy [Russell
and Subramanian, 1995]; an approach that we might label procedural bounded rationality
attempts to explicitly model the limitations in the decision-making procedures [Rubinstein,
1998]; and finally, the heuristics approach argues that general optimality principles ought to
be abandoned altogether in favor of collections of simple heuristics [Gigerenzer and Selten,
2001].
Here we are concerned with a particular flavor of bounded rationality, which we might
call “information-theoretic” due to its underlying rationale. While this approach solves
many of the shortcomings of perfect rationality in a simple and elegant way, it has not
3

Ortega et al.

yet attained widespread acceptance from the mainstream community in spite of roughly a
decade of research in the machine learning literature. As is the case with many emerging
fields of research, this is partly due to the lack of consensus on the interpretation of the
mathematical quantities involved. Nonetheless, a great deal of the basics are well-established
and ready for their widespread adoption; in particular, some of the algorithmic implications
are much better understood today. Our goal here is to provide a consolidated view of some
of the basic ideas of the theory and to sketch the intimate connections to other fields.
1.1 A Short Algorithmic Illustration
Perfect Rationality. Let Π = {π1 , π2 , . . . , πN } be a finite set of N ∈ N candidate choices
or policies, and let U : Π → [0, 1] be a utility function mapping each policy into the unit
interval. Consider the problem of finding a maximizing element π ∗ ∈ Π. For simplicity we
assume that, given an element π ∈ Π, its utility U (π) can be evaluated in a constant number
of computation steps. Imposing no particular structure on Π, we find π ∗ by sequentially
evaluating each utility U (π) and returning the best found in the end.

Procedure PerfectlyRationalChoice(Π, U )
π ∗ ← π1 ∈ Π
foreach π ∈ {π2 , π3 , . . . , πN } do
if U (π) ≥ U (π ∗ ) then π ∗ ← π
end
return π ∗
This exhaustive evaluation algorithm works well if N is small, but it does not scale to the
case when N is very large. In real-world tasks, such very large decision spaces are not the
exception but rather the norm, and an agent faces them in most stages of its informationprocessing pipeline (e.g. attention focus, model selection, action selection). In these cases,
the agent does not have enough resources to exhaustively evaluate each element in Π; rather,
it only manages to inspect a negligible subset of K  N elements in Π, where K depends
on the agent’s limitations.
Bounded Rationality. We model this limitation as a constraint on the agent’s information capacity of relating utility functions with decisions. This limitation changes the
nature of the decision problem in a fundamental way; indeed, information constraints yield
optimal choice algorithms that look very unusual to someone who is used to the traditional
optimization paradigm.
One simple and general way of implementing the decision process is as follows. A
bounded rational agent inspects the choices until it finds one that is satisficing. The order
of inspection is random: the agent draws (without replacement) the candidate policies from
a distribution Q that reflects the prior knowledge about the good choices. Then, for each
proposed element π ∼ Q, the agent decides whether π is good enough using a stochastic
criterion that depends both on the utility and the capacity. Importantly, the agent can
inspect the policies in parallel as is illustrated in the following pseudo-code.
4

Information-Theoretic Bounded Rationality

Procedure BoundedRationalChoice(Π, U, α, U ∗ )
repeat in parallel
π∼Q
u ∼ U[0, 1]
if u ≤ exp{α(U (π) − U ∗ )} then return π
end
The stochastic criterion is parametrized by α ∈ R and U ∗ ∈ [0, 1] which jointly determine
the size of the solution space and thereby the choice difficulty. The parameter α is known
as the inverse temperature, and it plays the role of the degree of rationality; whereas U ∗ is
an aspiration level which is typically chosen to be the maximum utility that can be attained
in principle, i.e. U ∗ = 1 in our example.
The behavior of this algorithm is exemplified in Fig. 1. In this simulation, the size N of
the policy space Π was set to one million. The utilities were constructed by first mapping
N uniformly spaced points in the unit interval into f (x) = x2 and then randomly assigning
these values to the policies in Π. For the prior Q we chose a uniform prior. Together,
the utility and the prior determine the shape of the choice space illustrated in the left
panel. The remaining panels show the performance of the algorithm in terms of the utility
(center panel) and the number of inspected policies before a satisficing policy was found
(right panel). This simulation shows two important aspects of the algorithm. First, the
performance in utility is marginally decreasing in the search effort, as illustrated by the
concavity of U (α) and the roughly proportional dependency between search effort and α.
Second, the parameter α essentially controls the performance of the algorithm. In contrast,
it is easy to see that this performance is unaffected by the size of the set of policies, as long
as the shape of the choice space is preserved.
Properties. Although the algorithm seems counter-intuitive at a first glance, it has the
following advantages:
1. Use of prior knowledge. If the agent possesses a distribution Q over Π, where Q(π)
denotes the probability of π being the best policy, then it can exploit this knowledge.
In particular, if it already knows the maximizer π ∗ , i.e. if Q is a degenerate distribution
given by a Kronecker delta function δ[π = π ∗ ], then it will only query said policy.
2. Protection from adversarial enumeration. If the agent were to inspect the policies
using a fixed deterministic order, then it could fall prey to an adversarial shuffling
of the utilities. The above randomization technique protects the agent from such an
attack.
3. Control of complexity. The agent can control the size of the solution space by choosing
an appropriate value for the α parameter. More precisely, |α| ≈ 0 corresponds to an
easy problem in which most proposals π ∼ P will be accepted; and |α|  0 is a hard
problem.
5

Ortega et al.

Choice Index (Normalised)

Performance in Search

Inspected Policies

Performance in Utility

Utility

Utility

Choice Space

Inverse Temperature

Inverse Temperature

Figure 1: Simulation of bounded-rational choices. The left panel shows the shape of the
utility function for 100 randomly chosen policies out of one million. These are
shown both in the way the agent sees them (◦-markers) and sorted in ascending
order of the utility (•-markers). The shaded area under the curve is an important
factor in determining the difficulty of the policy search problem. The center and
right panels illustrate the performance as a function of the inverse temperature,
measured in terms of the utility (center panel) and the number of inspected
policies before acceptance (right panel). Both panels show the mean (black curve)
and the bands capturing 80% of the choices excluding the first and last decile
(shaded area). The values were calculated from 300 samples per setting of the
inverse temperature.

4. Parallel. The policies can be inspected in parallel, in contrast to perfect rationality1 .
Technically, this is possible because “π ∗ is satisficing” is a statement in propositional
logic. Instead, “π ∗ is a maximizer”, which can be rewritten as “for every policy π, π ∗
has larger utility than π”, is a statement in first-order logic with a universal quantifier
that depends on exhaustive inspection.
The above basic choice algorithm is very general. Apart from modeling intractability, it can
be used to represent choices under model uncertainty, risk and ambiguity sensitivity, and
other players’ attitudes towards the agent. In the main text, we will see how to derive the
algorithm from first principles, how to model general information constraints in decision
making, and how to extend the basic decision-making scheme to sequential scenarios.
1.2 Outlook
In the next section we briefly review the ideas behind SEU theory. We touch upon twoplayer games in order to motivate a central concept: the certainty-equivalent. The section
then finishes with two open problems of SEU theory: intractability and model uncertainty.
1. The running time of exhaustive search can be brought down to O(log N ) through dynamic programming
and parallelism, but the number of inspected policies is still N .

6

Information-Theoretic Bounded Rationality

Section 3 lays out the basic conceptual framework of information-theoretic bounded rationality. We analyze the operational characterization of having limited resources for deliberation, and state the main mathematical assumptions. From these, we then derive the free
energy functional as the replacement for the expected utility in decision making. Section 4
applies the free energy functional to single-step decision problems. It serves the purpose of
further sharpening the intuition behind the free energy functional, both from a theoretical
and practical view. In particular, the notion of equivalence of bounded-rational decision
problems is introduced, along with practical rejection sampling algorithms. Section 5 extends the free energy functional to sequential decisions. We will see that the notion of
equivalence plays a crucial role in the construction and interpretation of bounded rational decision trees. We show how such decision trees subsume many special decision rules
that represent risk-sensitivity and model uncertainty. The section finishes with a recursive
rejection sampling algorithm for solving bounded-rational decision trees. The last section
discusses the relation to the literature and concludes.

2. Preliminaries in Expected Utility Theory
Before we introduce the ideas that underlie bounded-rational decision-making, in this section
we will set the stage by briefly reviewing SEU theory.
Notation. Sets are denoted with calligraphic letters such as in X . The set ∆(X ) corresponds to the simplex over X , i.e. the set of all probability distributions over X . The
symbols Pr and E stand for the probability measure and expectation respectively, relative
to some probability space with sample space Ω. Conditional probabilities are defined as
Pr(A|B) :=

Pr(A ∩ B)
Pr(B)

(1)

where A, B ⊂ Ω are measurable subsets, and where B is such that Pr(B) 6= 0.
2.1 Variational principles
The behavior of an agent is typically described in one of two ways: either dynamically, by
directly specifying the agent’s actions under any contingency; or teleologically, by specifying a variational problem (e.g. a convex objective function) that has the agent’s policy
as its optimal solution. While these two descriptive methods can be used to represent the
same policy, the teleological description has a greater explanatory power because in addition it encodes a preference relation which justifies why the policy was preferred over the
alternatives2 .
Because of the explanatory power of variational principles, they are widely used to justify
design choices. For example, virtually every sequential decision-making algorithm is conceived as a maximum expected utility problem. This encompasses popular problem classes
such as multi-armed bandits, Markov decision processes (MDPs) and partially observable
Markov decision processes (POMDPs)—see Russell and Norvig [2010] for a discussion. In
2. Notice also that in this sense, the qualifier “optimal” is a statement that only holds relative to the
objective function. That is, “being optimal” is by no means an absolute statement, because given any
policy, one can always engineer a variational principle that is extremized by it.

7

Ortega et al.

learning theory, regret minimization [Loomes and Sugden, 1982] is another popular variational principle to choose between learning algorithms [Cesa-Bianchi and Lugosi, 2006].
2.2 Subjective expected utility
Today, the theory of subjective expected utility [Savage, 1954] is the de facto theory of
rationality in artificial intelligence and reinforcement learning [Russell and Norvig, 2010].
The bedrock of the theory is a representation theorem stating that the preferences of a
rational agent can be described in terms of comparisons between expected utilities. The
qualifiers “subjective” and “expected” in its name derive from the fact that both the utility
function and the belief distribution are assumed to be properties that are specific to each
agent, and that the utility of a random realization is equated with the expected utility over
the individual realizations.
Decision problem. Let X and Y be two finite sets, the former corresponding to the set
of actions available to the agent and the latter to the set of observations generated by the
environment in response to an action. A realization is a pair (x, y) ∈ X × Y. Furthermore,
let U : (X × Y) → R be a utility function, such that U (x, y) represents the desirability of the
realization (x, y) ∈ (X × Y); and let Q(·|·) be a conditional probability distribution where
Q(y|x) represents the probability of the observation y ∈ Y given the action x ∈ X .
Optimal policy. The agent’s goal is to choose a policy that yields the highest expected
utility; in other words, a probability distribution P ∈ ∆(X ) over actions that maximizes
the functional (see Fig. 2)

X
X
X
Q(y|x)U (x, y) .
(2)
EU [P̃ ] :=
P̃ (x)E[U |x] =
P̃ (x)
x

x

y

Thus, an optimal policy is any distribution P with no support over suboptimal actions, that
is, P (x) = 0 whenever E[U |x] ≤ maxz E[U |z]. In particular, because the expected utility is
linear in the policy’s probabilities, one can always choose a solution that is a vertex of the
probability simplex ∆(X ):
(
1 if x = x∗ := arg maxx E[U |x]
P (x) = δxx∗ =
(3)
0 otherwise,
where δ is the Kronecker delta. Hence, there always exists a deterministic optimal policy.
Utility distribution. Given the optimal policy, the utility U becomes a well-defined
random variable with probability distribution
X

Pr(U = u) = Pr (x, y) : U (x, y) = u =
P (x)Q(y|x).
U −1 (u)

Even though the optimal policy might be deterministic, the utility of the ensuing realization
is in general a non-degenerate random variable. Notably, perfectly rational agents are
insensitive to the higher-order moments of the utility: so two actions yielding utilities
having very different variances are regarded as being equal if their expectations are the
same.
8

Information-Theoretic Bounded Rationality

max
min

Figure 2: Expected Utility Theory. Left: A decision problem can be represented as a tree
with two levels. Choosing a policy amounts to assigning transition probabilities
for the decision node located at the root (4), subject to the fixed transition
probabilities in the chance nodes ( ) and the utilities at the leaves (). Right:
Mathematically, this is equivalent to choosing a member P of the simplex over
actions ∆(X ) that maximizes the convex combination over conditional expected
utilities E[U |x].

Friends and foes. What happens when the environment is yet another agent? According
to game theory [Von Neumann and Morgenstern, 1944], we can model this situation again
as a decision problem, but with the crucial difference that the agent lacks the conditional
probability distribution Q(·|·) over observations that it needs in order evaluate expected
utilities. Instead, the agent possesses a second utility function V : (X ×Y) → R representing
the desires of the environment. Game theory then invokes a solution concept, most notably
the Nash equilibrium, in order to propose a substitute for the missing distribution Q(·|·)
based on U and V , thereby transforming the original problem into as a well-defined decision
problem.
To simplify, we assume that the agent chooses first and the environment second, and
we restrict ourselves to two special cases: (a) the fully adversarial case U (x, y) = −V (x, y);
and (b) the fully friendly case U (x, y) = V (x, y). The Nash equilibrium then yields the
decision rules [Osborne and Rubinstein, 1999]


X
P = arg max
P̃ (x) min Q̃(y|x)U (x, y) ,
(4)
P̃

Q̃

x



X
P = arg max
P̃ (x) max Q̃(y|x)U (x, y)
P̃

(5)

Q̃

x

for the two cases respectively. Comparing these to (2), we observe two properties. First,
the overall objective function appears to arise from a modular composition of two nested
choices: the outer for the agent and the inner for the environment. Second, there are
essentially three ways in which the utilities of a choice are aggregated—namely through
maximization, expectation, and minimization—depending on the nature of the choice.
Certainty-equivalent. An agent plans ahead by recursively aggregating future value into
present value. As we have seen, it does so by summarizing the value of each choice using one
of three aggregation types: minimization (5), representing an adversarial choice; expectation ( ), representing an indifferent (random) choice; and maximization (4), representing
9

Ortega et al.

a friendly choice. This summarized value is known as the certainty-equivalent, because if the
agent were to substitute a choice with multiple alternatives with an equivalent (degenerate)
choice with a single alternative, the latter would have this value (see Fig. 3). Notice that for
planning purposes, it is irrelevant whether the decision is made by the agent or not; to the
agent, what matters is the degree to which an outcome (be it an action or an observation)
contributes positively to its objective function (as encoded by one of the three possible aggregation operators). Indeed, another (concise) way to describe subjective expected utility
theory is that the certainty-equivalent of random outcomes is given by the expectation.
a)

-1

b)

2

1

-1

c)

2

2

1

-1

2

1

-1

Figure 3: Decision problems (top row) and their certainty-equivalents (bottom row).

2.3 Two open problems
We finish this section by presenting two very common situations in which the application
of perfect rationality does not seem to be the right thing to do: very large choice spaces
and model uncertainty.
Very large choice spaces. Consider the problem of choosing the longest straw in a
given collection. Expected utility theory works well when the number of elements is small
enough so that the agent can exhaustively measure all their lengths and report the longest
found. This is the case in the situation depicted in Fig. 4a, where it is easily seen that the
top-most straw is the longest. The situation of Fig. 4b however appears to be very different.
Here, the number of straws is very large and their arrangement is unstructured. The lack
of structure prevents us from grouping the straws for simplifying our search, i.e. there
are no symmetries for defining equivalence classes that would reduce the cardinality of our
search space. Consequently, there is no obvious improvement over testing some elements
by picking at random until finding one that is sufficiently good.
Model uncertainty. Consider a task in which you must choose one of two boxes containing 100 black and white balls. After your choice is announced, a ball is drawn at random
from the box, and you win $100 if the color is black (or nothing otherwise). If you get to see
the contents of the two boxes then you would choose the box containing a larger proportion
of black balls. For instance, in Fig. 5a you would choose the left box. However, which box
would you choose in the situation shown in Fig. 5b? In his seminal paper, Ellsberg [1961]
10

Information-Theoretic Bounded Rationality

a)

b)

Figure 4: Very large choice spaces. a) Perfect rationality can capture decision problems
involving a small number of choices. b) However, perfect rationality is intractable
in very large and unstructured choice spaces.

showed that most of people bet on the left box. A simple explanation for this phenomenon
is that people fill the missing information of the right box by enumerating all the possible
combinations of 100 black and white balls, attaching prior probabilities to them in a riskaverse way. Thus, such prior beliefs assigns a larger marginal probability to the loosing
color—in this case, “white”.
Now, assume that you place your bet, but no ball is drawn. Instead, you are asked to
revise your bet. The contents of the boxes are assured to stay exactly the same, but now
you are told that this time you win for “white” rather than “black”. Would you change your
bet? Empirically, most of the people stick with their initial bet. However, there is no single
prior distribution over combinations that can predict this particular preference pattern, as
this would contradict expected utility theory. Are people thus irrational? Perhaps, but it
is worthy to point out that L. J. Savage, who formulated subjective expected utility theory,
was among the people who violated the theory [Ellsberg, 1961].
a)

b)

50/50

25/75

50/50

?

Figure 5: The Ellsberg paradox. a) Two boxes with known proportions of black and white
balls. b) Two boxes where only the proportions of the left box are known.

11

Ortega et al.

One explanation for this apparent paradox is that the right box of second experiment
involves unknown probabilities3 which affect the net value of a choice. In this case, people
might actually have a uniform model over combinations of black and white balls, but they
nevertheless discount the value of the box as an expression of distrust in the model. On
the other hand, there are people who perceive increased net values in some situations.
Such could be the case, for instance, if they knew and trusted the person who set up the
experiment. We will see later in the text how this interaction between the trust in the
beliefs and the utility can be modeled using the bounded-rational framework.

3. The Mathematical Structure of Boundedness
We now tackle the problem of formalizing boundedness. First, we will pursue an obvious
route, namely that of meta-reasoning. While meta-reasoning models can model important
aspects of complex decision-making (e.g. preliminary resource allocation and reasoning
about other agents), it ultimately falls short in adequately modeling bounded-rationality.
3.1 Meta-reasoning
One straightforward attempt to address the problem of intractability of expected utility
theory is through meta-reasoning [Zilberstein, 2008], i.e. by letting the agent reason about
the very costs of choosing a policy. The rationale is that, an agent can avoid prohibitive
costs by finding a trade-off between the utility of a policy and the cost of evaluating said
policy.
Formal solution. The argument proceeds as follows. Let U : Π → R be a bounded
utility function that maps each policy π ∈ Π into a value U (π) in the unit interval. A
perfectly-rational agent then solves the problem
max U (π),
π∈Π

(6)

and uses any solution π ∗ as its policy. Rather than solving (6) which is deemed to be too
hard, a meta-level rational agent solves the problem
n
o
max U (π) − C(π) ,
(7)
π∈Π

where C(π) ∈ R+ is a positive penalization term due to the cost of evaluating the policy π
that is spent by the agent’s policy-search algorithm, e.g. time or space complexity of a
Turing machine.
Criticism. While the idea of meta-reasoning is intuitively appealing, it fails to simplify
the original decision problem. This is seen by defining U 0 (π) := U (π) − C(π) and noting
that the agent’s meta-level reasoning maximizes the objective function
max U 0 (π),
π∈Π

(8)

3. Importantly, the economic literature distinguishes between risk (= known probabilities) and ambiguities
(= unknown probabilities) [Knight, 1921, Ellsberg, 1961]. Savage defined subjective expected utility
theory as a theory of decision making under risk. There is currently no widely agreed upon definition of
ambiguities, although there exist proposals, such as the framework of variational preferences [Maccheroni
et al., 2006].

12

Information-Theoretic Bounded Rationality

which is itself another perfectly-rational decision problem. But then, the rationale of metareasoning tells us that evaluating the meta-level utilities U 0 (π) should come with penalizations C 0 (π) due to the costs incurred by the policy-search algorithm that is used at the
meta-level. . .
There are two problems with this scheme. First, it is quickly seen that this line of
reasoning leads to an infinite regress when carried to its logical conclusion. Every time the
agent instantiates a meta-level to reason about lower-level costs, it generates new costs at
the meta-level. Second, the problem at a meta-level is typically harder than the lower-level
one. How can we circumvent these problems?
3.2 Incomplete Information and Interrupted Deliberation
The central problem with meta-reasoning lies in its self-referential logic: whenever an agent
attempts to reason about its own costs of reasoning, it creates a new perfectly-rational
decision problem at the meta-level that comes with additional costs that are left out. Due
to this, we conclude that it is impossible for an agent to fully apprehend its own resources
of deliberation. Notice that this does not prevent agents from using meta-reasoning; it just
excludes meta-reasoning as a formal solution to the bounded-rationality problem.
Formal solution. The problem can be solved by modeling the agent’s deliberation as a
game of incomplete information or Bayesian game [Harsanyi, 1967]. Such a game allows
us to represent the agent’s ignorance about the very objective function it is supposed to
optimize. Loosely speaking, it allows us to model the “unknown uncertainties” (as opposed
to “known uncertainties”) that the agent has about its goals. We refer the reader to the
texts on game theory by Osborne and Rubinstein [1999] or Leyton-Brown and Shoham
[2008] for an introduction to Bayesian games.
We model the agent’s decision as single-player game of incomplete information. For this,
it is useful to distinguish between the agent’s alleged objective and the perceived objective
as seen by an external observer. The agent is equipped with an objective function U (π) that
it attempts to optimize with respect to the policy π ∈ Π. However, it unexpectedly runs
out of resources, effectively being interrupted at an indeterminate point in its deliberation,
and forced to commit to a suboptimal policy π ◦ ∈ Π. From an external observer’s point of
view, π ◦ ∈ Π appears to be the result of an intentional deliberation seeking to optimize an
alternative objective function U (π) − C(π) that trades off utilities and deliberation costs.
Formally, let C be a discrete set of penalization functions of the form C : Π → R that
model different interruptions. Then, the agent does not solve a particular problem, but
rather a collection of problems given by
n
o
∀C ∈ C,
max U (π) − C(π) .
(9)
π∈Π

∗ for any penalization function C ∈ C.
In other words, the agent finds an optimal policy πC
This abstract multi-valued optimization might appear unusual. However, one simple
way of thinking about it is in terms of an any-time optimization. In this scheme, the
agent’s computation generates “intermediate” solutions π1 , π2 , . . . to

U − C1 ,

U − C2 ,
13

U − C3 ,

...

Ortega et al.

respectively, where C1 , C2 , . . . is an exhaustive enumeration of C. This ordering of C is
not specified by (9); however, one can link this to computational resources by demanding
an ascending ordering C1 (π1 ) ≤ C2 (π2 ) ≤ . . . of penalization. Nature secretly chooses a
penalization function C ◦ ∈ C, which is only revealed when the agent produces the solution π ◦
to U − C ◦ . This causes the computation to stop and the agent to return π ◦ . Now, notice
that since the agent does not know C ◦ , its computational process can be regarded as an a
priori specification of the solution to the multi-valued optimization problem (9).
3.3 Commensurability of utility and information
The fact that finding a good policy comes at a cost that changes the net value of the agent’s
pay-off suggests that utilities and search costs should be translatable into each other, i.e.
they should be commensurable. The aim of this section is to present a precise relationship
between the two quantities. This relationship, while straightforward, has rich and conceptually non-trivial consequences that significantly challenge our familiar understanding of
decision-making.

Search. We first introduce a search model that will serve as a concrete example for our
exposition. In this model, the agent searches by repeatedly obtaining a random point from
a very large and unstructured domain until a desired target is hit. For this, we consider
a finite sample space Ω and a probability measure Pr that assigns a probability Pr(S) to
every subset S ⊂ Ω; a reference set B ⊂ Ω with Pr(B) 6= 0; and a target set A ⊂ B ⊂ Ω.
In each round, the agent samples a point ω from the conditional probability distribution
Pr(·|B). If ω falls within the target set A, then the agent stops. Otherwise, the next round
begins and the sampling procedure is repeated.
The components of this model are interpreted as follows. The agent’s prior knowledge
is modeled using the reference set B. The points that lie outside of B are those that
are never inspected by the agent (e.g. because it knows that these points are undesirable
or because they are simply inaccessible). Every choice of a reference set induces a prior
distribution Pr(·|B). Furthermore, the difficulty of finding the target is relative: The number
of samples N that the agent has to inspect up until hitting the target depends upon the
relative size of A with respect to B, which is given by the conditional probability Pr(A|B).
Thereby, N is a random variable that follows a geometric distribution N ∼ G(p) with
success probability p := Pr(A|B), having the expected value

E[N ] =

1
.
Pr(A|B)

(10)

Decision complexity. Based on the previous search model, we now define the decision
complexity C(A|B) as a measure of the cost required to specify a target set A given a
reference B, where A and B are arbitrary measurable subsets of the sample space Ω with
Pr(B) 6= 0. We impose the following properties on the measure C:
14

Information-Theoretic Bounded Rationality

a) Functional form: For every A, B such that A ⊂ B ⊂ Ω,
C(A|B) := f ◦ Pr(A|B),
where f is a continuous, real-valued mapping.
b) Additivity: For every A, B, C such that A ⊂ B ⊂ C ⊂ Ω,
C(A|C) = C(B|C) + C(A|B).
c) Monotonicity: For every A, B, C, D such that A ⊂ B ⊂ Ω and C ⊂ D ⊂ Ω,
⇐⇒

Pr(A|B) > Pr(C|D)

=
a)

C(A|B) < C(C|D).

+
b)

<
c)

Figure 6: Decision complexity. In each figure, the reference and target sets are depicted by
light and dark-colored areas respectively. a) The complexity varies continuously
with the target A and the reference B. b) The complexity can be decomposed
additively. c) The complexity decreases monotonically when increasing the conditional probability.
How does C look like? We first observe that the desideratum (a) allows us to restrict our
attention only to continuous functions f that map the unit interval [0, 1] into real numbers.
Then, the desiderata (b) and (c) imply that any f must fulfill the functional equation
f (pq) = f (p) + f (q)

(11)

for any p, q ∈ [0, 1] subject to the constraint f (p) < f (q) whenever p > q. It is well-known
that any solution to the previous functional equation must be of the form
f (p) = −

1
log p,
α

(12)

where α > 0 is an arbitrary positive number. Thus, the complexity measure is given by
C(A|B) = −

1
1
log P (A|B) = log E[N ],
α
α

(13)

that is, proportional to the Shannon information − log Pr(A|B) of A given B. This shows
that the decision complexity is proportional to the minimal amount of bits necessary to
15

Ortega et al.

b)

a)

Figure 7: Deliberation as search. a) An agent’s deliberation is a transformation of prior
choice probabilities Q(x) into posterior choice probabilities P (x). The relative
changes reflect the agent’s preferences. b) To understand the complexity of this
transformation, we model it as a search process with the convention Q(x) =
Pr(x|Q) and P (x) = Pr(x|P ), where P ⊂ Q ⊂ Ω.

specify a choice and proportional to the logarithm of the expected number of points E[N ]
that the agent has to sample before finding the target.
Utility. Let us take one step back to revisit the concept of utility. Utilities were originally
envisioned as auxiliary quantities for conceptualizing preferences in terms of simple numerical comparisons. In turn, a preference is an empirical tendency for choosing one course of
action over another that the agent repeats under similar circumstances. In the economic
literature, this rationale that links probability of choice and preferences is known as revealed
preferences [Samuelson, 1938].
It is interesting to note that subjective expected utility is a theory that is particularly
stringent in its behavioral demands, because it assumes that an agent will unequivocally
choose the exact same course of action whenever it faces an equivalent situation—rather than
just displaying a tendency towards repeating a choice. Intuitively though, it seems natural to
admit weaker forms of preferences. For instance, consider the situation in Fig. 7a depicting
an agent’s choice probabilities Q(x) and P (x) before and after deliberation respectively.
Even though the agent does not commit to any particular choice, it is plausible that its
preference relation  is such that x2  x3  x1 , meaning that U (x2 ) > U (x3 ) > U (x1 ) for
an appropriately defined notion of utility.
Free energy. We have discussed several concepts such as decisions, choice probabilities,
utilities, and so forth. Our next step consists in reducing these to a single primitive concept:
decision complexity. This synthesis is desirable both due the theoretical parsimony as well
as the integrated picture of decision-making that it delivers. To proceed, we first note that
an agent’s deliberation process transforming a prior Q into a posterior P can be cast in
terms of a search process where Q and P are the reference and target sets respectively. As
illustrated in Fig. 7b, the set of available choices X forms a partition of the sample space Ω.
The distributions P and Q are encoded as nested subsets P ⊂ Q ⊂ Ω using the notational
convention
P (x) := Pr(x|P )
and
Q(x) := Pr(x|Q),
(14)
16

Information-Theoretic Bounded Rationality

that is, where the two sets induce distributions over the choices through conditioning. With
these definitions in place, we can now derive an expression for the complexity C(P |Q) in
terms of choice-specific complexities C(x ∩ P |x ∩ Q):
1
log Pr(P |Q)
α


Pr(x|P )Pr(x|Q)
1X
Pr(x|P ) log Pr(P |Q)
=−
α x
Pr(x|P )Pr(x|Q)
1X
Pr(x ∩ P |Q)
1X
Pr(x|P )
=−
Pr(x|P ) log
+
Pr(x|P ) log
α x
Pr(x|Q)
α x
Pr(x|Q)
X
Pr(x|P )
1X
Pr(x|P ) log
Pr(x|P )C(x ∩ P |x ∩ Q) +
.
=
α
Pr(x|Q)
x
x

C(P |Q) = −

(15)

The first equality is obtained through an application of the definition (13). The second
equality is obtained by multiplying the constant term Pr(P |Q) with another term that
equals one and subsequently taking the expectation with respect to P (x|P ). Separating the
terms in the logarithm into two different sums and using the product rule Pr(x ∩ P |Q) =
Pr(x|P ) · Pr(P |Q) gives the third equality (note that P ∩ Q = P ). The last step of the
derivation is another application of (13). If we now use the convention (14) we get
C(P |Q) =

X

P (x)C(x ∩ P |x ∩ Q) +

x

1X
P (x)
.
P (x) log
α x
Q(x)

(16)

How can we interpret this last expression? In essence, it relates the decision complexities
of two different states of knowledge. If the agent’s state of knowledge is (x ∩ Q), then the
complexity of finding the target (x ∩ P ) is equal to C(x ∩ P |x ∩ Q). This assumes that the
agent knows that the resulting choice will be x for sure. However, since the agent does not
know the final choice, then (16) says that the total complexity of deliberation is equal to
the average choice-specific complexities plus a penalty (given by the KL-divergence) due
to not knowing of the future outcome. Put differently, the certainty-equivalent complexity
of an uncertain choice is larger than the expected complexity. This constitutes the most
important deviation from subjective expected utility theory.
Equation (16) derived above can now be turned into a variational principle by observing
that the r.h.s. is convex in the posterior choice probabilities. Thus, define utilities as
quantities that, up to a constant C ∈ R, are equal to negative complexities:
U (x) := −C(x ∩ P |x ∩ Q) + C.
Then, subtracting C from (16) and taking the negative gives the functional
F [P̃ ] :=

X

P̃ (x)U (x) −

x

1X
P̃ (x)
P̃ (x) log
,
α x
Q(x)

(17)

which now is concave in P̃ and, when maximized, minimizes the complexity of transforming Q into P subject to the utilities U (x). Equation (17) is the so-called free energy func17

Ortega et al.

tional, or simply the free energy 4 , and it will serve as the foundation for the approach to
bounded-rational decision making of this work.

4. Single-Step Decisions
4.1 Bounded-rational decisions
In this section we will take the free energy functional (17) as the objective function for
modeling bounded-rational decision making. We will first focus on simple one-step decisions
and explore their conceptual and algorithmic implications.
Decision problem. A bounded-rational agent, when deliberating, transforms prior choice
probabilities into posterior choice probabilities in order to maximize the expected utility—
but it does so subject to information constraints. Formally, a bounded-rational decision
problem is a tuple (α, X , Q, U ), where: α ∈ R is the inverse temperature which acts as a
rationality parameter; X is a finite set of possible outcomes; Q ∈ ∆(X ) is a prior probability
distribution over X representing a prior policy; and U : X → R is a real-valued mapping of
the outcomes called the utility function.
Goal. Given a bounded-rational decision problem (α, X , Q, U ), the goal consists in finding
the posterior policy P ∈ ∆(X ) that extremizes the free energy functional
F [P̃ ] :=

X

P̃ (x)U (x) −

x

|

{z

}

Expected Utility

P̃ (x)
1X
.
P̃ (x) log
α x
Q(x)
{z
}
|

(18)

Information Cost

Thus, the free energy functional captures a fundamental decision-theoretic trade-off: it
corresponds to the expected utility, regularized by the information cost of representing the
final distribution P using the base distribution Q. The functional is illustrated in Fig. 8.
Inverse temperature. The inverse temperature α controls the trade-off between utilities
and information costs by setting the exchange rate between units of information (in bits) and
units of utility (in utiles). An agent’s deliberation process can be affected by a number of
disparate factors imposing information constraints; nonetheless, here the central assumption
is that all of them can ultimately be condensed into the single parameter α.
Furthermore, notice that we have extended the domain of α to the real values R. The
sign of α determines the type of optimization: when α > 0 is positive, then the free energy
functional Fα is concave in P̃ and the posterior policy P is the maximizer ; and when α < 0
is negative, then F is convex in P̃ and P is the minimizer. We will further elaborate on the
meaning of the negative values later when analyzing sequential decisions.
Optimal choice. The optimal solution to (18) is given by the Gibbs distribution
X
1
P (x) =
Q(x) exp{αU (x)},
Zα =
Q(x) exp{αU (x)},
Zα
x

(19)

4. Here we adopt this terminology to relate to existing work on statistical mechanical approaches to control.
To be precise however, in the statistical mechanical literature this functional corresponds to (a shifted
version of) the negative free energy difference. This is because utilities are negative energies, and because
(17) characterizes the difference between two free energy potentials.

18

Information-Theoretic Bounded Rationality

Expected Utility

KL-Divergence

Free Energy

Figure 8: The Free Energy Functional. A bounded-rational decision-problem combines a
linear and a non-linear cost function, the first being the expected utility and the
latter the KL-divergence of the posterior from the prior choice probabilities. The
optimal distribution is the point on the linear subspace (defined by the expected
utility and the inverse temperature) that minimizes the KL-divergence to the
prior. In information geometry, this point is known as the information projection
of the prior onto the linear subspace [Csiszár and Schields, 2004].

where the normalizing constant Zα is the partition function. Inspecting (19), we see that the
optimal choice probabilities P (x) is a standard Bayesian posterior5 obtained by multiplying
the prior Q(x) with a likelihood term that grows monotonically with the utility U (x).
The inverse temperature controls the balance between the prior Q(x) and the modifier
exp{αU (x)}.
Certainty-equivalent. To understand the value that the agent assigns to a given decision
problem, we need to calculate its certainty-equivalent. To do so, we insert the optimal choice
probabilities (19) into the free energy functional (18), obtaining the expression
X

1
1
F := F [P ] = log Zα = log
Q(x)eαU (x) .
(20)
α
α
x
In the text, we will always use the notation F [·] (with functional brackets) for the free
energy and F (without brackets) for the certainty-equivalent. An interesting property of
the certainty-equivalent is revealed when we analyze its change with the inverse temperature
α (Fig. 9). Obviously, the more the agent is in control, the more effectively it can control
the outcome, and thus the higher it values the decision problem. In particular, the value
and the choice probabilities take the following limits,
α → +∞

1
α

log Zα = max U (x)

α→0

1
α

log Zα =

x

X

Q(x)U (x)

P (x) = Umax (x)
P (x) = Q(x)

x

α → −∞

1
α

log Zα = min U (x)
x

5. We will further elaborate on this connection later in the text.

19

P (x) = Umin (x),

Ortega et al.

a)

b)

Figure 9: Certainty-equivalent and optimal choice. a) The certainty-equivalent α1 log Zα ,
seen as a function of the inverse temperature α ∈ R, has a sigmoidal shape that
moves between min U and max U , passing through E[U ] at α = 0. Panel (b) shows
three optimal choice distributions for selected values of α. Notice that α2 = 0,
P (x) = Q(x).

where Umax and Umin are the uniform distribution over the maximizing and minimizing
subsets
Xmax := {x ∈ X : U (x) = max
U (x0 )}
0
x

Xmin := {x ∈ X : U (x) = min
U (x0 )}
0
x

respectively. Here we see that the inverse temperature α plays the role of a boundedness
parameter and that the single expression α1 log Z is a generalization of the classical concept
of value in reinforcement learning (see Fig. 10).
4.2 Stochastic choice
A perfectly-rational agent must always choose the alternative with the highest expected
utility. In general, this operation cannot be done without exhaustive enumeration, which is
more often than not intractable. In contrast, we expect a bounded-rational agent to inspect
only a subset of alternatives until it finds one that is good enough—that is, a satisficing
choice. Furthermore, the effort put into analyzing the alternatives should scale with the
agent’s level of rationality. A central feature of information-theoretic bounded rationality
is that this “algorithmic” property of analyzing just a subset is built right into the theory.
20

Information-Theoretic Bounded Rationality

b)

a)

-1

2

low

1

c)

d)

-1

2

1

-1

2

1

-1

2

1

-1

2

1

-1

2

1

-1

2

1

high
0

Figure 10: Approximation of the classical decision rules using bounded-rational decision
problems. a) We represent a bounded-rational decision problem using a colored
square node, where the color encodes the inverse temperature. b–d) Classical
decision rules and their bounded-rational approximations.

More precisely, this simplification is achieved by noticing that acting optimally amounts
to obtaining just one random sample from the posterior choice distribution. Any other
choice scheme that does not conform to the posterior choice probabilities, such as picking the
mode of the distribution for instance, violates the agent’s information constraints modeled
by the objective function. We review a basic sampling scheme that is readily suggested by
the specific shape of the posterior distribution.
Rejection sampling. The simplest sampling scheme is immediately suggested by the
form of the posterior choice distribution (19), illustrated in Fig. 11. If we interpret Q as
prior knowledge that is readily available to the agent in the form of random samples, then it
can filter them to generate samples from P using rejection sampling. This works as follows:
the agent first draws a sample x from Q and then accepts it with probability

∗
A(x|U ∗ ) = min 1, eα[U (x)−U ] ,

(21)

where U ∗ ∈ R is a target value set by the agent. This is repeated until a sample is
accepted. Notice that this sampling scheme does not require the agent to draw the samples
sequentially: indeed, rejection sampling can be parallelized by drawing many samples and
returning any of the accepted choices. The next theorem guarantees that rejection sampling
does indeed generate a sample from P .
Theorem 1. Rejection sampling with acceptance probability (21) produces the correct distribution as long as U ∗ ≥ maxx {U (x)} when α ≥ 0 and U ∗ ≤ minx {U (x)} when α ≤ 0.
Proof. First, we need a constant c such that for all x, P (x) ≤ c·Q(x). The smallest constant
is given by
∗
P (x)
eαU
eαU (x)
≤P
= c.
=P
0 αU (x0 )
0 αU (x0 )
Q(x)
x0 Q(x )e
x0 Q(x )e
21

Ortega et al.

a)

b)

Figure 11: Choosing optimally amounts to sampling from the posterior choice distribution
P (x) ∝ Q(x) exp{αU (x)} using rejection sampling. a) A utility function U (x)
and a target utility U ∗ . b) The choice is phrased as a search process where the
agent attempts to land a sample into the target set (dark area). Generating
any choice corresponds to obtaining a successful Bernoulli random variate Z ∼
B(pα ), where the probability of success is equal to pα = Zα / exp{αU ∗ }.

These inequalities hold whenever U ∗ is chosen as U ∗ = maxx U (x) if α ≥ 0 and U ∗ =
minx U (x) if α ≤ 0. Hence, given a sample x from Q, the acceptance probability is
P (x)
=
c · Q(x)

1
αU (x)
Z Q(x)e
1
αU ∗
Z Q(x)e

=

eαU (x)
.
eαU ∗

Efficiency. Notice that rejection sampling is equal to the search process defined in 3.3,
where the probability of the target set is equal to
X
Zα
∗
pα =
Q(x)eα[U (x)−U ] = αU ∗ .
(22)
e
x
In other words, obtaining any sample is equivalent to obtaining a successful Bernoulli
random variate B(pα ). Thus, the number of samples until acceptance Nα follows a geometric
distribution G(pα ), and the expected value is E[Nα ] = 1/pα . Furthermore, the number of
samples Nα (δ) needed so as to guarantee acceptance with a small failure probability δ > 0
is given by


log δ
.
(23)
Nα (δ) =
log(1 − pα )
This function is plotted in Fig. 12a.
Limit efficiency. What is the most efficient sampler? Assume w.l.g. that the inverse
temperature α is fixed and strictly positive. From the definition of utilities (14) and the
probability-complexity equivalence (13) we get
U (x) = −C(x ∩ P |x ∩ Q) + C =
22

1
log Pr(x ∩ P |x ∩ Q) + C.
α

Information-Theoretic Bounded Rationality

Inspecting Fig. 11b, we see that in rejection sampling the probability of finding any posterior
choice is such that Pr(x ∩ P |x ∩ Q) = exp{U (x) − U ∗ }. Using this substitution implies
U (x) = U (x) − U ∗ + C

=⇒

U ∗ = C,

(24)

that is, the target utility U ∗ is exactly equal to the offset C that transforms complexities
into utilities. Thus, choosing an inverse temperature α and a target utility U ∗ indirectly
determine the decision complexities and thereby also the probability of accepting a sample pα . Since decision complexities are positive and their absolute differences fixed through
the utilities, the optimal choice of the target utility must be
U ∗ = max{U (x)}.
x

(25)

Picking a smaller value for U ∗ is not permitted, as it would violate the assumptions about
the underlying search model (Sec. 3.3).
a)

b)

250

200

150

100

50

0

0

0.2

0.4

0.6

0.8

1

Figure 12: a) Number of samples until acceptance. b) Granularity. Increasing the resolution
of the choice set from X to (X × Y) does not change the success probability.

Granularity. Typically, one would expect that the number of samples to be inspected
before making a decision depends on the number of available options. However, in the
bounded-rational case, this is not so. Indeed, we can augment the granularity of the choice
set without affecting the agent’s decision effort. This is seen as follows. Assume that
we extend the choice set from X to (X × Y), with the understanding that every pair
(x, y) ∈ (X × Y) is a sub-choice of x ∈ X . Then, the utilities U (x) correspond to the
certainty-equivalents of the utilities U (x, y), that is
X

1
1
αU (x,y)
Q(y|x)e
U (x) = log Zα (x) = log
.
(26)
α
α
y∈x
Inserting this into the partition function for x, we get
X
X
Zα =
Q(x)eαU (x) =
Q(x, y)eαU (x,y) ,
x

x,y

23

Ortega et al.

that is, the partition function Zα is independent of the level of resolution of the choice
set. This, in turn, guarantees that the success probability of rejection sampling pα =
Zα / exp{αU ∗ } stays the same no matter how we partition the choice set.
4.3 Equivalence
There is more than one way to represent a given choice pattern. Two different decision
problems can lead to identical transformations of prior choice probabilities Q into posterior
choice probabilities P , and have the same certainty-equivalent. When these two conditions
are fulfilled, we say that these decision problems are equivalent. The concept of equivalence
is important because a given decision problem can be re-expressed in a more convenient
form when necessary. This will prove to be essential when analyzing sequential decision
problems later in the text.
Formal relation. Consider two equivalent bounded-rational decision problems (α, X , Q, U )
and (β, X , Q, V ) with non-zero inverse temperatures α, β 6= 0. Then, their certaintyequivalents are equal, that is,
1
1
log Zα = log Zβ ,
(27)
α
β
P
P
where the partition functions are Zα = x Q(x) exp{αU (x)} and Zβ = x Q(x) exp{βV (x)}
respectively. The optimal choice probabilities of the second decision problem are equal to
P (x) =



1
exp βV (x) = exp β[V (x) −
Zβ

1
β


log Zβ ] = exp β[V (x) −

1
α

log Zα ] ,

where the last equality substitutes one certainty-equivalent for the other. Since these probabilities are equal to the ones of the first decision problem, we have

exp β[V (x) −

1
α


log Zα ] = exp α[U (x) −

1
α

Then, taking the logarithm and rearranging gives


α
1
1
V (x) = U (x) +
−
log Zα .
β
α β

log Zα ]}.

(28)

Thus, (28) is an explicit formula for the relation between the inverse temperatures α, β
and utilities U (x), V (x) of two equivalent bounded-rational decision problems. Essentially,
equivalent decision problems have utilities that are scaled versions of each other around the
axis defined by the certainty-equivalent (see Fig. 13). From the figure, we see that increasing
the inverse temperature by a factor c requires decreasing the distance of the utilities to the
certainty-equivalent by a factor 1/c, so that the product is maintained at all times.
Sampling from equivalent decision problems. In rejection sampling, the success
probabilities pα and pβ of two equivalent decision problems (α, X , Q, U ) and (β, X , Q, V )
respectively are the same, that is,
pα =

Zβ
Zα
= pβ ,
∗ =
αU
e
eβV ∗
24

(29)

Information-Theoretic Bounded Rationality

Figure 13: Equivalent bounded-rational decision problems. The plot shows the utility
curves for three equivalent decision problems with inverse temperatures α = 1, 12
and −1 respectively. The resulting utilities are scaled versions of each other with
respect to the symmetry axis given by the certainty-equivalent α1 log Zα .

as long as their target utilities U ∗ and V ∗ obey the relation (28), i.e.


α ∗
1
1
∗
V = U +
−
log Zα .
β
α β

(30)

An important problem is to sample directly from a decision problem (β, X , Q, V ) given the
inverse temperature α and the target utility U ∗ of an equivalent decision problem. A naive
way of doing so consists in using (30) and α1 log Zα = β1 log Zβ to derive an explicit formula
for V ∗ :


α ∗
α 1
∗
V = U + 1−
log Zβ .
β
β β
This formula requires integrating over the choice set to obtain the partition function Zβ .
However, this is a costly operation that does not scale to very large choice spaces: recall
that all we are allowed to do is inspecting the utilities V (x) for a few samples obtained
from Q(x). Instead, we can relate the success probability pα to the samples obtained from
(β, X , Q, V ). This is seen by rewriting pα as follows:
 h
 h
i
i
1
1
∗
∗
pα = exp α
log Zα − U
= exp α log Zβ − U
.
α
β
Then we express the inverse temperature as α = ( αβ )·β and simplify the previous expression
to


α
Zβ
β
pα = p ,
where
p :=
.
(31)
eβU ∗
This result has a convenient operational interpretation. The original problem, which consisted in obtaining one successful Bernoulli sample with success probability pα has been
25

Ortega et al.

rephrased as the problem of obtaining αβ successful Bernoulli samples with probability of
success p. Intuitively, the reason behind this change is that the new success probability p can
be larger/smaller than the original success probability pα , resulting in a more/less challenging search problem: therefore, (31) equalizes the search complexity by demanding less/more
successful samples. Note that this conversion only works if the resulting rejection sampling
problem fulfills the conditions of Theorem 1, that is: U ∗ ≥ maxx {V (x)} for strictly positive
β, or U ∗ ≤ V (x) for strictly negative β. To use (31) effectively, we need to identify algorithms to sample an arbitrary, possibly non-integer amount of ξ ∈ R consecutive Bernoulli
successes based only on a sampler for B(p), which in turn depends on the choice sampler
Q. We first consider three base cases and then explain the general case.
Case ξ ∈ N. If ξ is a natural number, then the Bernoulli random variate Z ∼ B(pξ ) is obtained in the obvious way by attempting to generate ξ consecutive Bernoulli B(p) successes.
If all of them succeed, then B is a success; otherwise Z is a failure (see Algorithm 1).
Algorithm 1: Rejection-sampling trial for ξ ∈ N
input : A target U ∗ , a number ξ ∈ N, and a choice sampler Q
output: A sample x or failure 
for n = 1, . . . , ξ do
Draw x ∼ Q(x) and u ∼ U(0, 1)
if u > exp{β[V (x) − U ∗ ]} then return 
end
return x
Case ξ ∈ (0, 1). If ξ is in the unit interval, then the Bernoulli success for B(pξ ) is easier
to generate than for B(p). Thus, we can tolerate a certain number of failures from B(p).
The precise number is based the following theorem.
Theorem 2. Let Z be a Bernoulli random variate with bias (1 − fN ) where

fN =

N
X

bn ,

and

bn = (−1)n+1

n=1

ξ(ξ − 1)(ξ − 2) · · · (ξ − n + 1)
n!

for 0 < ξ < 1 and where N is a Geometric random variate with probability of success p.
Then, Z is a Bernoulli random variate with bias pξ .
An efficient use of this sampling scheme is as follows. First, we generate an upper bound
f ∗ ∼ U(0, 1) that will fix the maximum number of tolerated failures and initialize the “trial
counter” to f = 0. Then, we repeatedly attempt to generate a successful Bernoulli sample
Z ∼ B(p) as long as f < f ∗ . If it succeeds, we return the sample; otherwise, we add a small
penalty to the counter f and repeat—see Algorithm 2.
26

Information-Theoretic Bounded Rationality

Algorithm 2: Rejection-sampling trial for ξ ∈ (0, 1)
input : A target U ∗ , a number ξ ∈ (0, 1), and a choice sampler Q
output: A sample x or failure 
f ∗ ∼ U(0, 1)
Set b ← −1, f ← 0, and k ← 1
Draw x ∼ Q(x) and u ∼ U(0, 1)
while u > exp{β[V (x) − U ∗ ]} do
Set b ← −b · (ξ−k+1)
, f ← f + b, and k ← k + 1
k
Draw x ∼ Q(x) and u ∼ U(0, 1)
if f ∗ ≤ f then return 
end
return x
Case ξ = −1. If ξ is −1, then the interpretation of the target utility U ∗ is flipped: an
upper-bound becomes a lower-bound and vice versa. The resulting success probability is
then equal to
∗
eβU
pα =
.
Zβ
We do not know how to efficiently generate a sample from the inverse partition function.
Instead, we use the following trick: we invert our acceptance criterion by basing our comparison on reciprocal probabilities as shown in Algorithm 3.
Algorithm 3: Rejection-sampling trial for ξ = −1
input : A target U ∗ and a choice sampler Q
output: A sample x or failure 
Draw x ∼ Q(x) and u ∼ U(0, 1)
if 1/u < exp{β[V (x) − U ∗ ]} then return  return x
General case. The rejection sampling algorithm for an arbitrary value of ξ ∈ R is constructed from the preceding three cases. First, the sign of ξ determines whether we will base
our acceptance criterion on either probabilities or reciprocal probabilities. Then, we decompose the absolute value |ξ| into its integer and unit-interval parts, applying the associated
algorithms to generate a choice.
4.4 Comparison
We finish this section with a brief comparison of decision-making based upon expected utility
versus free energy. Table 1 tabulates the differences according to several criteria explained
in the following. The rationality paradigm refers to general decision-making rationale of the
agent. We have seen that perfect rationality and bounded rationality can be regarded as
choice models that are valid approximations to different scales or domain sizes. The different
scales, in turn, suggest different search strategies and search scopes: the perfect rational
agent can use a fixed, deterministic rule that exploits the symmetries in the choice set in
order to single out the optimal choice; while the bounded-rational agent has to settle on a
27

Ortega et al.

satisficing choice found through random inspection—as if it were a search in a pile of straw.
The two objective functions also differ in their dependency on the choice probabilities. The
functional form is such that this dependency is linear in the expected utility case and nonlinear in the free energy case. Because of this, the perfectly rational agent’s preferences
depend only upon the expected value of the utility; whereas a bounded-rational agent also
takes into account the higher-order moments of the utility’s distribution (utility sensitivity),
which is easily seen through a Taylor expansion of the KL-divergence term of the free energy.
Table 1: Comparison of Decision Rules.
Objective function
Rationality paradigm
Preferred domain size
Search strategy
Search scope
Functional form
Utility sensitivity

Expected Utility

Free Energy

perfect
small
deterministic
complete
linear
first moment

bounded
large
randomized
incomplete
non-linear
all moments

5. Sequential Decisions
In the previous section we have fleshed out the basic theory for single-step bounded-rational
decision making. In real-world applications however, agents have to plan ahead over multiple
time steps and interact with another system called the environment. In these sequential
decision problems, agents have to devise a policy—that is, a decision plan—that prescribes
how to act under any situation that the agent might encounter in the future.

max

max

E

E

min

max

max

max

E

E

min

min

Figure 14: Decision trees
Like in single-step decision problems, policies are chosen using a decision rule. The classical decision rules that are used in the literature depend upon the type of system the agent
is interacting with. Three such decision rules that are popular are: Expectimax, when the
agent is interacting with a stochastic environment; Minimax, where the agent is playing
against an adversary; and Expectiminimax in games with both an adversary and chance
elements such as in Backgammon. The dynamical structure of the interactions between
the agent and the environment is captured in a decision tree (or a game tree) like those
28

Information-Theoretic Bounded Rationality

illustrated in Figure 14. These decision trees were built from composing the primitives 5,
, and 4 (discussed in Section 2.2) representing an adversarial, stochastic, and friendly
transition respectively. The optimal solution is then obtained using dynamic programming6
by recursively calculating the certainty-equivalent, and then taking the transition promising
the highest value. Notice that, for planning purposes, it is immaterial whether the transitions are eventually taken by the agent or by the environment: all what matters is the
degree to which a particular transition contributes towards the agent’s overall objective.
Thus, a max-node 4 can stand both for the agent’s action or another player’s cooperative
move for instance.

a)

b)

E

max
E
min

Figure 15: A bounded-rational approximation. Classical decision trees, such as the Expectiminimax decision tree, can be approximated with a bounded-rational decision
tree (b) by substituting the classical nodes with bounded-rational counterparts.
Recall that the nodes are color-coded, with darker nodes corresponding to higher
inverse temperatures.

These classical decision trees can be approximated by bounded-rational decision trees.
Recall from Section 2.2 that the classical certainty-equivalent operators 5, , and 4 can
be approximated by bounded-rational decision problems with appropriately chosen inverse
temperatures. The very same idea can be used to substitute the nodes in a classical decision
tree (see e.g. Figure 15).
This approximation immediately suggests a much broader class of bounded-rational
sequential decision problems that is interesting in its own right. The decision trees in this
class are such that each node can have its own inverse temperature to model a variety
of information constraints that result from resource limitations, risk, and trust sensitivity.
Figure 16 illustrates some example decision types. Our next goal is to formalize these
bounded-rational decision trees, explain how they follow from the single-step case, and
present a sampling algorithm to solve them.
5.1 Bounded-rational decision trees
Definition. A bounded-rational decision tree is a tuple (T, X , α, Q, R, F ) with the following components. T ∈ N is the horizon, i.e. the depth of the tree. X is the set of interactions
6. Also known as “solving the Bellman optimality equations” in the control and reinforcement learning
literature, and backtracking in the economics literature.

29

Ortega et al.

a)

b)

e)

anti-rational

rational
risk-seeking,
cooperative

d

c

c)

a

d)

risk-averse,
adversarial
b

Figure 16: Map of bounded-rational decision rules. Panels (a–d) depict several two-step
decision problems, where the agent and environment interact with inverse temperatures α and β respectively: a) case α  0, β ≈ 0 approximates expected
utility; b) case α  0, β  0 is an approximation of a minimax/robust decision;
c) case α > 0, β ≈ 0 is a bounded-rational control of a stochastic environment; and d) α > 0, β > 0 corresponds to risk-seeking bounded-rational control.
Panel (e) shows a map of the decision rules.

or transitions of the tree. We assume that it is finite, but potentially very large. Together
with the horizon, it gives rise to an associated set of states (or nodes) of the tree S, defined
as
T
[
S :=
X t.
t=0

Each member s ∈ S is a path of length t ≤ T that uniquely identifies a node in the
tree. Excepting the (empty) root node  ∈ S, every other member s0 ∈ S can be reached
from a preceding node s ∈ S as long as sx = s0 for a transition x ∈ X . The function
α : S → R is the inverse temperature function, and it assigns an inverse temperature
α(s) to each node s ∈ S in the tree. We will assume that α(s) 6= 0 for all s ∈ S. The
conditional probability distribution Q(·|·) defines the prior transition probabilities: thus,
0
Q(x|s) corresponds to the probability
P of moving to node s = sx ∈ S from s ∈ S via
the transition x ∈ X . Obviously, x Q(x|s) = 1 for each node s ∈ S. Every transition
has, in turn, an associated conditional reward R(x|s) ∈ R. We assume that these rewards
are additive, so that R(uv|w) = R(u|w) + R(u|v, w) for any disjoint sets u, v, w. Finally,
F : S → R is the terminal certainty-equivalent function which attaches a value F (s) to each
terminal state s ∈ X T . Fig. 17 shows an example.
Sequence of interactions. The bounded-rational decision tree models a (prior) probability distribution over random sequences X1 , . . . , XT of length T . It suggests a chronological generative model: at time t, i.e. after having observed the t − 1 previous interactions
X<t = x<t , it draws the next interaction Xt from the conditional Q(Xt |X<t ). The agent
has the ability to influence the course of realization of the interaction sequence by changing
30

Information-Theoretic Bounded Rationality

a)

b)

D
C

D
C

C

C

Figure 17: Bounded-rational decision trees. Panel (a) shows a simple bounded-rational
decision tree with two steps and X = {1, 2}. These can be used to model
complicated situations such as the Ellsberg Paradox discussed in Section 2.3
shown in panel (b). This tree models the following three random variables: θ, the
proportion of black & white balls in the box (only two of its 101 children nodes
are shown); D, the agent’s bet on the left or right urn; and C, corresponding
to the color of the ball drawn from the chosen box. We do not annotate the
transitions with rewards, as we assume that they are all equal to zero. Notice
that the initial choice of θ is made adversarially (α < 0) in spite of the uniform
prior over the 101 possible combinations. Because of this, the agent biases his
bet towards the left box, irrespective of whether black (x = 1) or white (x = 0)
wins.

the prior Q into a posterior P . However, the extent to which it can do so depends on the
state’s inverse temperature.
Free energy. As in the single-step scenario, the objective function optimized by the agent
is the free energy functional. For bounded-rational decision trees, the free energy functional
F [P̃ ] is given by

F [P̃ ] =

X

P̃ (x≤T )

x≤T

X
T 
t=1



1
P̃ (xt |x<t )
R(xt |x<t ) −
log
+ F (x≤T ) .
α(x<t )
Q(xt |x<t )

(32)

Inspection of (32) reveals that it is an expectation taken w.r.t. the realizations of the tree,
where each node s ∈ S contributes a free energy term of the form
X
x

P (x|s)R(x|s) −

1 X
P̃ (x|s)
P (x|s) log
α(s) x
Q(x|s)

that is specific to the transition. In addition, each leaf supplies an extra term F (s), which
can be thought of as the certainty-equivalent of the future after time step T that is not
explicitly represented in the decision-tree.
31

Ortega et al.

5.2 Derivation of the free energy functional
The free energy functional for decision trees is not arbitrary: it is derived from the free
energy functional for the single-step case via equivalence transformations. The derivation
is conceptually straightforward (see Fig. 18), although notationally cumbersome.
Construction. Our goal is to transform a bounded-rational decision problem represented
by the tuple (β, X T , Q, V ) into a bounded-rational decision tree (T, X , α, Q, R, F ), where the
inverse temperature function α is prescribed and the rewards R and F are to be determined,
and where the other members T , X and Q stay fixed. The free energy functional of the
single-step decision problem is
F [P̃ ] =

X

P̃ (x≤T )V (x≤T ) −

x≤T

1X
P̃ (x≤T )
P̃ (x≤T ) log
.
βx
Q(x≤T )

(33)

≤T

This free energy with the inverse temperature β and utility function V can be restated as
an equivalent bounded-rational decision problem with inverse temperature α() and utility
function U , where α() is the prescribed value for the root node of the desired decision
tree. The subindex in U is just to remind us that the utility function is paired to inverse
temperature α() of the root node. This yields
F [P̃ ] =

X

P̃ (x≤T )U (x≤T ) −

x≤T

1 X
P̃ (x≤T )
P̃ (x≤T ) log
.
α() x
Q(x≤T )

(34)

≤T

Recall that this does not change the resulting optimal choice, as equivalent decision problems
share the prior, the posterior, and the certainty-equivalent. In Fig. 18, this corresponds to
the transformation from (a) to (b).
In order to introduce step-wise reinforcements of decision trees, we assume that the
utilities can be recursively broken down into a sum of an instantaneous reward plus the
utility of the remaining tail. For the first step, this is
U (x≤T ) = R(x1 ) + U (x2:T |x1 ),

(35)

where R(x1 ) is the reward of the first step and U (x2:T |x1 ) is the utility of the tail x2:T
rooted at x1 . How much reward we place in R(x1 ) is arbitrary, as long as all the paths
starting with x1 put the same amount of reward into this transition. Substituting this back
into (33) and rearranging yields


X
1 X
P̃ (x≤T )
F [P̃ ] =
P̃ (x≤T ) R(x1 ) + U (x2:T |x1 ) −
P̃ (x≤T ) log
α() x
Q(x≤T )
x≤T
≤T


X
1
P̃ (x1 )
=
P̃ (x1 ) R(x1 ) −
log
+ F [P̃ ](x1 ) ,
(36)
α()
Q(x
)
1
x
1

where we have defined the free energies F [P̃ ](x1 ) as
F [P̃ ](x1 ) =

X

P̃ (x2:T )U (x2:T |x1 ) −

x2:T

1 X
P̃ (x2:T |x1 )
P̃ (x2:T |x1 ) log
.
α() x
Q(x2:T |x1 )
2:T

32

(37)

Information-Theoretic Bounded Rationality

a)

c)

b)

d)

Figure 18: Construction of a bounded-rational decision tree. Panel a: Starting from a
(single-step) bounded-rational decision problem over a product space X T , we
apply an equivalence transformation to set a new inverse temperature, split
each choice into a transition (head) and a tail sequence, and then recur on the
tails until the desired bounded-rational decision tree is fully built (Panels b–d).

Note that through this operation, we have split the original single-step decision problem over
choices x≤T ∈ X T into a two-step decision problem in which the first step is a choice among
the x1 ∈ X and the second among the tails x2:T ∈ X T −1 . That is, each initial choice x1
leads to separate single-step decision problem of the form (α(), X T −1 , Q(·|x1 ), U ).
We now continue this process for t = 2, 3, . . . , T − 1, recurring in a breadth-first fashion
on the nested free energies F [P̃ ](x1 ), F [P̃ ](x≤2 ), . . . , F [P̃ ](x≤T −2 ). Every time we do so,
we first substitute the decision problem with an equivalent one having inverse temperature
α(x≤t ), utility function Ux≤t , and then split the utilities into a reward R(xt |x<t ) and a tail
utility Ux≤t (xt+1:T |x≤t ). This results in the following expression of nested free energies:
F [P̃ ] =

X


P̃ (x1 ) R(x1 ) −

x1

+

X

1
P̃ (x1 )
log
α()
Q(x1 )


P̃ (x2 |x1 ) R(x2 |x1 ) −

x2

1
P̃ (x2 |x1 )
log
α(x1 )
Q(x2 |x1 )

..
.
+

X





P̃ (xT −1 |x<T −1 ) F [P̃ ](x<T ) · · ·
.

(38)

xT −1

Finally, for the base case of the recursion given by the collection of the innermost free
energies F [P̃ ](x<T ), which are equal to
F [P̃ ](x<T ) =

X

P (xT |x<T )Ux<T (xT |x<T ) −

xT

X
1
P̃ (xT |x<T )
P (xT |x<T ) log
,
α(x<T ) x
Q(xT |x<T )
T

we split the utilities arbitrarily into a reward R(xT |x<T ) and a terminal free energy F (x≤T ),
that is,
Ux<T (xT |x<T ) = R(xT |x<T ) + F (x≤T ).
33

Ortega et al.

Inserting this back into (38) and rearranging the probabilities gives the desired free energy
functional for the bounded rational decision tree (32).
Insights from the construction. This derivation shows that the multi-step case does
not require introducing any additional theory—everything can be reduced to the building
blocks already developed in Section 4 for the single-step case.
It is worthwhile pointing out that the sequence of steps we took in order to derive the
decision tree’s free energy functional from the single-step decision problem is completely
reversible. It is easy to see how to extend this procedure to formulate an algorithm that
takes any source decision-tree and transforms it into another equivalent decision tree with
a prescribed inverse temperature function. In other words, every bounded-rational decision
tree (T, X , α, Q, R, F ) can be transformed into another one (T, X , α0 , Q, R0 , F 0 ) with an
arbitrarily chosen inverse temperature function α0 as long as both α and α0 are non-zero.
In this case, we say that these decision trees are equivalent.
This equivalence relation induces a quotient space (i.e. a set of equivalence classes) on
the set of bounded-rational decision trees that has rather counterintuitive properties. For
instance, it turns out that a bounded-rational Minimax decision-problem can be turned
into an equivalent anti-rational, risk-seeking decision-problem, where the agent picks an
deleterious action in the hope that the environment will save it!
5.3 Bellman recursion and its solution
Given a bounded-rational decision tree (T, X , α, Q, R, F ), we can express its associated free
energy functional (32) as a Bellman recursion. The Bellman recursion has the advantage of
offering a simplified, functional view of the sequential planning problem that facilitates the
characterization of the optimal policy.
Free energy. The recursive form of the free energy functional is readily obtained from
the nested form of the free energy (38). First, for each leaf node s ∈ S we equate the free
energy functional to the certainty-equivalent, that is, F [P̃ ](s) = F (s). These correspond to
the base cases of the recursion. Then, for each internal node s ∈ S, we have
F [P̃ ](s) =

X


P (x|s) R(x|s) −

x


1
P̃ (x|s)
log
+ F [P̃ ](sx) .
α(s)
Q(x|s)

(39)

This was obtained by exploiting the self-similar structure of (38).
Certainty-equivalent. Before we state the optimal solution, it is convenient to first
present the recursive characterization of the certainty-equivalent. For this, consider an internal node s ∈ S. Once the certainty-equivalents F (sx) of its children nodes become available, the multi-step decision problem rooted at s reduces to a single-step decision problem
(α(s), X , Q(·|s), Us ) where the utility function is given by the sum Us (x) := R(x|s) + F (sx)
of the instantaneous reward and the summarized future rewards for all x ∈ X . Hence, using
the formula for the certainty-equivalent (20) we get

h
i
X
1
F (s) =
log
Q(x|s) exp α(s) R(x|s) + F (sx) .
(40)
α(s)
x
34

Information-Theoretic Bounded Rationality

a)

b)

Figure 19: a) The certainty-equivalent F (s) of the node s ∈ S is calculated from the transition probabilities Q(x|s), immediate rewards R(x|s), and certainty-equivalents
F (sx) of its children nodes. b) When a path’s inverse temperature changes
from α(s) to α(sx), then the sampler must equalize this transition by requiring
α(sx)/α(s) successful samples from the subtree rather than just one.

This can be regarded as an operator on the transition probabilities, rewards and free energies
of the child nodes (Figure 19a).
Optimal solution. Similarly, given an internal node s ∈ S and the certainty-equivalents
F (sx) of its children nodes, the optimal decision at s is obtained immediately from the
equation for the single-step case (19):

h
i
1
P (x|s) =
Q(x|s) exp α(s) R(x|s) + F (sx) ,
(41)
Z(s)
where Z(s) is the partition function which normalizes the probabilities. Notice that the
immediate rewards R(x|s) (given α(s) and the Q(x|s)) do not form an alternative representation of the probabilities P (x|s). Rather, a complete specification requires taking the
sums R(x|s) + F (sx) as primitives for the representation.
5.4 Recursive rejection sampling
Similarly to the single-step decision case, choosing an optimal action amounts to sampling
from the optimal choice distribution (41). The naive way of doing this consists in computing (41) recursively and then to sample from it. A second, slightly more elaborate
way, consists in transforming the original bounded-rational decision tree into a single-step
decision problem by setting every node’s inverse temperature to a single value β using
equivalence transformations, and then to sample an optimal choice using rejection sampling as explained in Section 4.2. Unfortunately, both aforementioned methods depend on
computing the free energies F (sx), and this operation does not scale to very large choice
spaces.
Instead, we can sample a path τ ∈ X T from (41) using a recursive form of rejection
sampling without ever calculating a free energy. To do so, we first make the following two
observations that follow immediately from the single-step case. First, the probability of
obtaining any successful sample using rejection sampling is a Bernoulli random variable
35

Ortega et al.

with success probability




Z(s)
eα(s)U ∗ (s)

=

X
x

n
h
io
exp α(s) R(x|s) + F (sx)
n
o
Q(x|s)
,
exp α(s)U ∗ (s)

(42)

where U ∗ (s) is a given target utility for node s ∈ S that has to be either larger than
maxx {R(x|s) + F (sx)} if α(s) > 0 or smaller than minx {R(x|s) + F (sx)} if α(s) < 0
respectively. Second, the free energy and the partition function are related as
F (s) =

1
log Z(s).
α(s)

(43)

If s ∈ S is an internal node, then we can use the latter equation to substitute the free energies
in expression (42). This in turn allows us to rewrite the success probability recursively:
io
n
h
1
 X

log
Z(sx)
exp
α(s)
R(x|s)
+
α(sx)
Z(s)
n
o
=
Q(x|s)
∗ (s)
α(s)U
e
exp α(s)U ∗ (s)
x
io
n
h
1
log Z(sx)
exp α(s) α(sx)
X
n
h
io
=
Q(x|s)
∗ (s) − R(x|s)
exp
α(s)
U
x
=

X


Q(x|s)

x

Z(sx)
α(sx)U ∗ (sx)

e

 α(sx)
α(s)

,

(44)

where we have defined U ∗ (sx) := U ∗ (s) − R(x|s) as the target utility for the subtree rooted
as sx ∈ S. Thus, (44) says that obtaining a sample from an internal node s ∈ S amounts to
first picking a random transition x ∈ X and then obtaining α(sx)/α(s) successful samples
from the subtree rooted at sx ∈ S, which we know is an equivalent subtree having inverse
temperature α(sx)—see Figure 19b. We have already seen in Section 4.3 how to sample this
operation using (modifications of) the rejection sampling algorithm. If s ∈ S is a terminal
node instead, then we can treat it as a normal single-step decision problem and sample a
choice using rejection sampling.
A detailed pseudocode for this recursive rejection sampling algorithm is listed in Algorithm 4. The function sample(s, U ∗ , σ) takes as arguments a node s ∈ S; a target utility
U ∗ for the whole path; and a sign-flag σ ∈ {−1, +1}, which keeps track of whether we are
using normal (σ = +1) or reciprocal probabilities (σ = −1) in the rejection sampling step
due to the possible change of sign in the inverse temperature. It returns either an accepted
path τ ∈ X T or  if the proposal is rejected. Planning is invoked on the root node by
executing sample(, U ∗ , 1), where U ∗ is the global target utility. For this recursive sampler
to return a path drawn from the correct distribution, the value of U ∗ must be chosen so as
to be larger than the rewards of any path, i.e. for all x≤T ∈ X T ,
U∗ ≥

T
X

R(xt |x<t ) + F (x≤T )

t=1

36

Information-Theoretic Bounded Rationality

Algorithm 4: sample(s, U ∗ , σ)
input : A state s, a target utility U ∗ , and a sign σ
output: An accepted trajectory τ , otherwise 
Proposal:
x ∼ Q(x|s)
Base case:
if sx is a leaf then
u ∼ U(0, 1)
p ← exp{α(s)(R(x|s) + F (sx) − U ∗ )}
if (σ > 0 and u ≤ p) then return sx if (σ < 0 and 1/u ≥ p) then
return sx return 
end
Recursion:
σ ← σ · sign(α(s)/α(sx))
ξ ← abs(α(s)/α(sx))
begin Attempt to generate bξc successful samples.
for 1, . . . , bξc do
τ ← sample(sx, U ∗ − R(x|s), σ)
if τ =  then return 
end
if ξ = bξc then return τ
end
begin Attempt to generate ξ − bξc successful samples.
u ∼ U(0, 1)
a ← bξc − ξ
set b ← −1, f ← 0, and k ← 1
τ ← sample(sx, U ∗ − R(x|s), σ)
while τ =  do
set b ← −b · (a − k + 1)/k, f ← f + b, and k ← k + 1
τ ← sample(sx, U ∗ − R(x|s), σ)
if u ≤ f then return 
end
return τ
end

37

Ortega et al.

whenever the root node’s inverse temperature α() > 0 is strictly positive; or smaller than
the rewards of any path whenever α() < 0.
Finally we note that, as in the single-step case, the agent can parallelize the recursive
rejection sampler by simultaneously exploring many stochastically generated paths, and
then return any of the accepted ones.

6. Discussion
6.1 Relation to literature
In this paper we have presented a summary of an information-theoretic model of boundedrational decision-making that has precursors in the economic literature [McKelvey and
Palfrey, 1995, Mattsson and Weibull, 2002, Wolpert, 2004, Sims, 2003, 2005, 2006, 2011]
and that has emerged through the application of information-theoretic methods to stochastic
control and to perception-action systems [see e.g. Mitter and Newton, 2005, Kappen, 2005,
Todorov, 2006, 2009, Theodorou et al., 2010, Theodorou, 2015, Still, 2009, Still and Precup,
2012, van den Broek et al., 2010, Friston, 2010, Peters et al., 2010, Tishby and Polani, 2011,
Kappen et al., 2012, Neumann and Peters, 2012, Rawlik and Toussaint, 2012, Rubin et al.,
2012, Fox and Tishby, 2012, Neumann and Peters, 2013, Grau-Moya et al., 2013, Tishby
and Zaslavsky, 2015, Tanaka et al., 2015, Mohamed and Rezende, 2015, Genewein et al.,
2015, Leibfried and Braun, 2015]. In particular, the connection between the free energy
functional and bounded rationality, the identification of the free energy extremum as the
certainty-equivalent in sequential games, and the implementation of the utility-complexity
trade-off based on sampling algorithms, were developed in a series of publications within
this community [see e.g. Braun et al., 2011, Ortega and Braun, 2011, 2013, Ortega et al.,
2014, 2015]. The most distinguishing feature of this approach to bounded rationality is the
formalization of resources in terms of information.
Historical roots. The problem of bounded rational decision-making gained popularity
in the 1950s originating in the work by Herbert Simon [Simon, 1956, 1972, 1984]. Simon
proposed that bounded rational agents do not optimize, but satisfice—that is, they do not
search for the absolute best option, but rather settle for an option that is good enough.
Since then the research field for bounded rational decision-making has considerably diversified leading to a split between optimization-based approaches and approaches that dismiss
optimization as a misleading concept altogether [Lipman, 1995, Russell, 1995, Russell and
Subramanian, 1995, Aumann, 1997, Rubinstein, 1998, Gigerenzer and Selten, 2001]. In
particular, the formulation as a constrained optimization problem is argued to lead to an
infinite regress, and the paradoxical situation that a bounded rational agent would have
to solve a more complex (i.e. constrained) optimization problem than a perfectly rational
agent. Information-theoretic bounded rationality provides a middle ground here, as the
agent randomly samples choices, but does not incur into a meta-optimization, because the
random search simply stops when resources run out. In fact, the equations for informationtheoretic bounded rational agent can be interpreted as a stochastic satisficing procedure
instantiated by rejection sampling.
KL-Control. From the vantage point of an external observer, information-theoretic bounded
rational agents appear to trade off any gains in utility against the additional information38

Information-Theoretic Bounded Rationality

theoretic complexity as measured by the KL-divergence between a prior decision strategy
and a posterior decision strategy after deliberation. Recently, a number of studies have
suggested the use of the relative entropy as a cost function for control, which is sometimes referred to as KL-Control [Todorov, 2006, 2009, Kappen et al., 2012]. In the work
by Todorov [2006], the transition probabilities of a Markov decision process are controlled
directly, and the control costs are given by the KL-divergence between the controlled dynamics and the passive dynamics described by a baseline distribution. This framework has
also been extended to the continuous case, leading to the formulation of path integral control
[Kappen, 2005, Theodorou et al., 2010]. Conceptually, the most important difference to the
bounded-rational interpretation is that in KL-Control the stochasticity of choice is thought
to arise from environmental passive dynamics rather than being a direct consequence of
limited information capacities.
Psychology. In the psychological and econometric literature, stochastic choice rules have
extensively been studied starting with Luce [1959], extending through McFadden [1974],
Meginnis [1976], Fudenberg and Kreps [1993], McKelvey and Palfrey [1995] and Mattsson
and Weibull [2002]. The vast majority of models has concentrated on logit choice models
based on the Boltzmann distribution which includes the softmax rule that is popular in
the reinforcement learning literature [Sutton and Barto, 1998]. McFadden [1974] has shown
that such Boltzmann-like choice rules can arise, for example, when utilities are contaminated
with additive noise following an extreme value distribution. From the physics literature, it is
also well-known that Boltzmann distributions arise in the context of variational principles
in the free energy implying a trade-off between utility and entropic resource costs. The
information-theoretic model of bounded rationality generalizes these ubiquitous logit choice
models by allowing arbitrary prior distributions, as for example in McKelvey and Palfrey
[1995]. This corresponds to a trade-off in utility gains and additional resource costs incurred
by deviating from the prior, which ultimately entails a variational principle in a free energy
difference.
Economics. In the economic literature, variational principles for choice have been suggested in the context of variational preference models [Maccheroni et al., 2006]. In variational preference models the certainty-equivalent value of a choice consists of two terms:
the expected utility and an ambiguity index. A particular instance of the variational preference model is the multiplier preference model where the ambiguity index is given by a
Kullback-Leibler divergence [Hansen and Sargent, 2008]. In particular, it has been proposed that multiplier preference models allow dealing with model uncertainty, where the
KL-divergence indicates the degree of model uncertainty. Free energy variational principles
also appear in variational Bayesian inference. In this case the utility function is given by
the negative log-likelihood and the free energy trade-off captures the transformation from
Bayesian prior to posterior. The variational Bayes framework has recently also been proposed as a theoretical framework to understand brain function [Friston, 2009, 2010] where
perception is modeled as variational Bayesian inference over hidden causes of observations.
Computational approaches. While the free energy functional does not depend on
domain-specific assumptions, the exact relationship between information-theoretic constraints and the standard measures of algorithmic complexity in computer science (e.g.
space and time) is not known. In contrast, the notion of bounded optimality defines the
39

Ortega et al.

optimal policy as the program that achieves the highest utility score on a particular machine given complexity constraints, and oftentimes relies on meta-reasoning for practical
implementations [Horvitz, 1989, Russell and Subramanian, 1995]. This view has recently
experienced a revival in computational neuroscience under the name of computational rationality [Lieder et al., 2014, Lewis et al., 2014, Griffiths et al., 2015, Gershman et al.,
2015]. Another recent approach to model bounded resources with profound implications is
space-time embedded intelligence in which agents are treated as local computation patterns
within a global computation of the world [Orseau and Ring, 2012]. It remains an interesting challenge for the future to extend the framework of information-theoretic bounded
rationality to the realm of programs and to relate it to notions of algorithmic complexity.
6.2 Conclusions
The original question we have addressed is: how do agents make decisions in very large and
unstructured choice spaces? The need for solving this question is becoming increasingly
critical, as these decision spaces are ubiquitous in modern agent systems. To answer this,
we have formalized resource limitations as information constraints, and then replaced the
objective function of subjective expected utility theory with the free energy functional. An
advantage of the free energy functional is that its optimal solution has a clear operational
interpretation. As a result, the optimal solution is a fully parallelizable stochastic choice
strategy that strikes a trade-off between the utility and the search effort.
Perhaps more fundamentally though, the theory lays out a general method to model reasoning under information constraints that arise as symptoms of intractability, model uncertainty, or other causes. This feature becomes especially apparent in the sequential decision
case, where a bounded-rational decision-tree captures an agent’s dynamics of trust—both
in its own ability to shape & predict the future, and in the other players’ intentions. We
have seen that model uncertainty biases the value estimates of an agent, forcing it to pay
attention to the higher-order moments of the utility.
For the sake of parsimony of the exposition, in this work we have refrained from elaborating on specific applications or extensions. There are obvious connections to Bayesian
statistics that we have not fleshed out. Furthermore, the ideas outlined here can be applied
to any choice process that is typically subject to information constraints, among them:
attention focus and generation of random features; model selection and inference in probabilistic programming; and planning in active learning, Bayesian optimization, multi-agent
systems and partially-observable Markov decision processes. The success of the theory will
ultimately depend on its usefulness in these application domains.
Acknowledgments
The authors would like to thank Daniel Polani, Bert J. Kappen, and Evangelos Theodorou,
who provided innumerable insights during many discussions. This study was funded by
the Israeli Science Foundation Center of Excellence, the DARPA MSEE Project, the Intel
Collaborative Research Institute for Computational Intelligence (ICRI-CI), and the Emmy
Noether Grant BR 4164/1-1.
40

Information-Theoretic Bounded Rationality

Appendix A. Proofs
A.1 Proof to Theorem 2
Proof. By expanding h(p) = pξ around p0 = 1, Taylor’s theorem asserts that
pξ = 1 − ξ(1 − p) +

ξ(ξ − 1)(ξ − 2)
ξ(ξ − 1)
(1 − p)2 −
(1 − p)3 + · · ·
2!
3!

Since 0 < ξ < 1, each term after the first is negative, hence
pξ = 1 −

∞
X

bn (1 − p)n

bn := (−1)n+1

where

n=1

ξ(ξ − 1)(ξ − 2) · · · (ξ − n + 1)
n!

(45)

and where the 0 ≤ bn ≤ 1 are known a priori. Hence,
ξ

1−p =

∞
X

n

bn (1 − p) =

n=1

∞
X

∞
∞
n
X
X
X
bn
(1 − p)n+k p =
bk

n=1

n=1

k=0

!
(1 − p)n p,

k=0

where the second equality follows from multiplying the term (1 − p)n with
1=p·p

−1

=p

∞
X

(1 − p)k

k=0

and
Pn the third from a diagonal enumeration of the summands. Define f0 := 0 and fn :=
k=0 bk for n ≥ 1. Since from (45),
1 = 1 − 0ξ =

∞
X

bn ,

n=1

we know that 0 ≤ fn ≤ 1 for all n ≥ 0 as well. Finally,
ξ

p =1−

∞
X

n

fn (1 − p) p =

n=1

∞
X

(1 − fn )(1 − p)n p

n=1

corresponds to the expectation of (1 − fn ), where n follows a Geometric distribution with
probability of success p. To obtain a Bernoulli random variable u with bias pξ , we can
sample n first and then generate a Bernoulli random variable u|n with bias 1 − fn .

References
R. J. Aumann. Rationality and Bounded Rationality. Games and Economic Behavior, 28:
42–67, 1997.
D. P. Bertsekas and J. N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.
ISBN 1886529108.
D. A. Braun and P. A. Ortega. Information-theoretic bounded rationality and epsilonoptimality. Entropy, 16(8):4662–4676, 2014.
41

Ortega et al.

D. A. Braun, P. A. Ortega, E. Theodorou, and S. Schaal. Path integral control and bounded
rationality. In IEEE Symposium on adaptive dynamic programming and reinforcement
learning, pages 202–209, 2011.
N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University
Press, 2006.
I. Csiszár and P. C. Schields. Information Theory and Statistics: A Tutorial. NOW Publishers, 2004.
H. Dixon. Some thoughts on economic theory and artificial intelligence. In Surfing Economics: Essays for the Enquiring Economist. Palgrave, 2001.
M. O. Duff. Optimal learning: computational procedures for bayes-adaptive markov decision
processes. PhD thesis, University of Massachusetts Amherst, 2002. Director-Andrew
Barto.
D. Ellsberg. Risk, Ambiguity and the Savage Axioms. The Quaterly Journal of Economics,
75:643–669, 1961.
R. Fox and N. Tishby. Bounded Planning in Passive POMDPs. In ICML, pages 1775–1782,
2012.
K. Friston. The free-energy principle: a rough guide to the brain? Trends in Cognitive
Science, 13:293–301, 2009.
K. Friston. The free-energy principle: a unified brain theory? Nature Review Neuroscience,
11:127–138, 2010.
D. Fudenberg and D. Kreps. Learning mixed equilibria. Games and Economic Behavior, 5:
320–367, 1993.
T. Genewein, F. Leibfried, J. Grau-Moya, and D. A. Braun. Bounded rationality, abstraction
and hierarchical decision-making: an information-theoretic optimality principle. Frontiers
in Robotics and AI, 2(27), 2015.
S. J. Gershman, E. J. Horvitz, and J. B. Tenenbaum. Computational rationality: A converging paradigm for intelligence in brains, minds, and machines. Science, 349(6245):
273–8, 2015.
G. Gigerenzer and R. Selten. Bounded rationality: the adaptive toolbox. MIT Press, Cambridge, MA, 2001.
J. Grau-Moya, E. Hez, G. Pezzulo, and D. A. Braun. The effect of model uncertainty on
cooperation in sensorimotor interactions. Journal of The Royal Society Interface, 10(87),
2013.
T. L. Griffiths, F. Lieder, and N. D. Goodman. Rational use of cognitive resources: Levels
of analysis between the computational and the algorithmic. Topics in Cognitive Science,
7(2):217–229, 2015.
42

Information-Theoretic Bounded Rationality

L.P. Hansen and T.J. Sargent. Robustness. Princeton University Press, Princeton, 2008.
J. Harsanyi. Games with Incomplete Information Played by ”Bayesian” Players. Management Science, 14(3):159–182, 1967.
E. J. Horvitz. Reasoning about beliefs and actions under computational resource constraints.
In Uncertainty in Artificial Intelligence, 1989.
M. Hutter. Universal Artificial Intelligence: Sequential Decisions based on Algorithmic
Probability. Springer, Berlin, 2004.
H. J. Kappen. A linear theory for control of non-linear stochastic systems. Physical Review
Letters, 95:200201, 2005.
H. J. Kappen, V. Gómez, and M. Opper. Optimal control as a graphical model inference
problem. Machine Learning, 1:1–11, 2012.
F.H. Knight. Risk, Uncertainty, and Profit. Houghton Mifflin, Boston, 1921.
L. Kocsis and C. Szepesvári. Bandit based Monte-Carlo Planning. In Proceedings of ECML,
pages 282–203, 2006.
S. Legg. Machine Super Intelligence. PhD thesis, Department of Informatics, University of
Lugano, June 2008.
F. Leibfried and D. A. Braun. A Reward-Maximizing Spiking Neuron as a Bounded Rational
Decision Maker. Neural Computation, 27(8):1686–1720, 2015.
R. L. Lewis, A. Howes, and S. Singh. Computational rationality: linking mechanism and
behavior through bounded utility maximization. Topics in Cognitive Science, 6(2):279–
311, 2014.
K. Leyton-Brown and Y. Shoham. Essentials of Game Theory: A Concise Multidisciplinary
Introduction. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan
& Claypool Publishers, 2008.
F. Lieder, D. Plunkett, J. B. Hamrick, S. J. Russell, N. J. Hay, and T. L. Griffiths. Algorithm
selection by rational metareasoning as a model of human strategy selection. In Advances
in Neural Information Processing Systems 27, 2014.
B. Lipman. Information processing and bounded rationality: a survey. Canadian Journal
of Economics, 28:42–67, 1995.
G. Loomes and R. Sugden. Regret theory: An alternative approach to rational choice under
uncertainty. Economic Journal, 92:805–824, 1982.
R. D. Luce. Individual choice behavior. Wiley, Oxford, 1959.
F. Maccheroni, M. Marinacci, and A. Rustichini. Ambiguity aversion, robustness, and the
variational representation of preferences. Econometrica, 74:1447–1498, 2006.
43

Ortega et al.

L.-G. Mattsson and J. W. Weibull. Probabilistic choice and procedurally bounded rationality. Games and Economic Behavior, 41(1):61–78, 2002.
D. McFadden. Conditional logit analysis of qualitative choice behavior. In P. Zarembka,
editor, Frontiers in econometrics. Academic Press, New York, 1974.
R. D. McKelvey and T. R. Palfrey. Quantal Response Equilibria for Normal Form Games.
Games and Economic Behavior, 10(1):6–38, July 1995.
J. R. Meginnis. A new class of symmetric utility rules for gambles, subjective marginal
probability functions, and a generalized Bayes’ rule. In Proceedings of the American
Statistical Association, Business and Economic Statistics Section, pages 471–476, 1976.
S. K. Mitter and N. J. Newton. Information and Entropy Flow in the Kalman-Bucy Filter.
Journal of Statistical Physics, 118:145–176, 2005.
V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Human-level control through deep reinforcement learning. Nauture, 518(518):
529–533, 2013.
S. Mohamed and D. J. Rezende. Variational Information Maximisation for Intrinsically
Motivated Reinforcement Learning. In NIPS, 2015.
D. C. Neumann and J. Peters. Hierarchical relative entropy policy search. In Proceedings
of the International Conference on Artificial Intelligence and Statistics, 2012.
D. C. Neumann and J. Peters. Autonomous reinforcement learning with hierarchical REPS.
In Proceedings of the International Joint Conference on Neural Networks, 2013.
L. Orseau and Mark Ring. Space-Time embedded intelligence. Artificial General Intelligence, pages 209–218, 2012.
P. A. Ortega. A unified framework for resource-bounded autonomous agents interacting
with unknown environments. PhD thesis, Department of Engineering, University of Cambridge, UK, 2011.
P. A. Ortega and D. A. Braun. Information, utility and bounded rationality. In Lecture
notes on artificial intelligence, volume 6830, pages 269–274, 2011.
P. A. Ortega and D. A. Braun. Free Energy and the Generalized Optimality Equations
for Sequential Decision Making. In European Workshop on Reinforcement Learning
(EWRL’10), 2012.
P. A. Ortega and D. A. Braun. Thermodynamics as a Theory of Decision-Making with
Information Processing Costs. Proceedings of the Royal Society A 20120683, 2013.
P. A. Ortega and D. D. Lee. An Adversarial Interpretation of Information-Theoretic
Bounded Rationality. In Twenty-Eight AAAI Conference on Artificial Intelligence
(AAAI), 2014.
44

Information-Theoretic Bounded Rationality

P. A. Ortega, D. A. Braun, and N. Tishby. Monte Carlo Methods for Exact & Efficient
Solution of the Generalized Optimality Equations. In IEEE International Conference on
Robotics and Automation (ICRA), 2014.
P. A. Ortega, K.-E. Kim, and D. D. Lee. Reactive Bandits with Attitude. In 18th International Conference on Artificial Intelligence and Statistics (AISTATS), 2015.
M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1999.
C. H. Papadimitriou and J. N. Tsitsiklis. The Complexity of Markov Decision Processes.
Mathematics of Operations Research, 12(3):441–450, 1987.
J. Peters, K. Mülling, and Y. Altün. Relative entropy policy search. In AAAI, 2010.
K. Rawlik and M. Vijayakumar S. Toussaint. On stochastic optimal control and reinforcement learning by approximate inference. In Proceedings Robotics: Science and Systems.
MIT Press, 2012.
J. Rubin, O. Shamir, and N. Tishby. Trading value and information in MDPs. In Decision
making with imperfect decision makers. Springer, 2012.
A. Rubinstein. Modeling Bounded Rationality. MIT Press, Cambridge, MA, 1998.
S. J. Russell. Rationality and Intelligence. In Chris Mellish, editor, Proceedings of the
Fourteenth International Joint Conference on Artificial Intelligence, pages 950–957, San
Francisco, 1995. Morgan Kaufmann.
S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall,
Englewood Cliffs, NJ, 3rd edition edition, 2010.
S. J. Russell and D. Subramanian. Provably bounded-optimal agents. Journal of Artificial
Intelligence Research, 3:575–609, 1995.
P. Samuelson. A Note on the Pure Theory of Consumers’ Behaviour. Economica, 5(17):
61–71, 1938.
L. J. Savage. The Foundations of Statistics. John Wiley and Sons, New York, 1954. ISBN
0-486-62349-1.
H. A. Simon. Rational choice and the structure of the environment. Psychological Review,
63(2):129–38, 1956.
H. A. Simon. Theories of Bounded Rationality. In C.B. Radner and R. Radner, editors,
Decision and Organization, pages 161–176. North Holland Publ., Amsterdam, 1972.
H. A. Simon. Models of Bounded Rationality. MIT Press, Cambridge, MA, 1984.
C. A. Sims. Implications of rational inattention. Journal of Monetary Economics, 50(3):
665–690, April 2003.
C. A. Sims. Rational inattention: A research agenda. In Proceedings of the Deutsche
Bundesbank. Deutsche Bundesbank Research Center, 2005.
45

Ortega et al.

C. A. Sims. Rational inattention: Beyond the linear-quadratic case. American Economic
Review, 96(2):158–163, 2006.
C. A. Sims. Rational inattention and monetary economics. In Handbook of monetary
economics. Elsevier, 2011.
R. F. Stengel. Optimal Control and Estimation. Dover Books on Mathematics. Dover
Publications, 1994.
S. Still. An information-theoretic approach to interactive learning. Europhysics Letters, 85:
28005, 2009.
S. Still and D. Precup. An information-theoretic approach to curiosity-driven reinforcement
learning. Theory in Biosciences, 131(3):139–148, 2012.
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press,
Cambridge, MA, 1998.
C. Szepesvári. Algorithms for Reinforcement Learning. Synthesis Lectures on Artificial
Intelligence and Machine Learning. Morgan and Claypool Publishers, 2010.
T. Tanaka, P. M. Esfahani, and S. K. Mitter. LQG Control with Minimal Information:
Three-Stage Separation Principle and SDP-based Solution Synthesis. arXiv:1510.04214,
2015.
E. Theodorou, J. Buchli, and S. Schaal. A generalized path integral approach to reinforcement learning. Journal of Machine Learning Research, 11:3137–3181, 2010.
E. A. Theodorou. Nonlinear Stochastic Control and Information Theoretic Dualities: Connections, Interdependencies and Thermodynamic Interpretations. Entropy, 17(5):3352–
3375, 2015.
N. Tishby and D. Polani. Perception-Action Cycle, chapter Information Theory of Decisions
and Actions, pages 601–636. Springer New York, 2011.
N. Tishby and N Zaslavsky. Deep learning and the information bottleneck principle. In
ITW, pages 1–5, 2015.
E. Todorov. Linearly solvable Markov decision problems. In Advances in Neural Information
Processing Systems, volume 19, pages 1369–1376, 2006.
E. Todorov. Efficient computation of optimal actions. Proceedings of the National Academy
of Sciences U.S.A., 106:11478–11483, 2009.
B. van den Broek, W. Wiegerinck, and H. J. Kappen. Risk Sensitive Path Integral Control.
In UAI, pages 615–622, 2010.
J. Veness, M. Ng, M. Hutter, W. Uther, and D. Silver. A Monte-Carlo AIXI Approximation.
Journal of Artificial Intelligence Research, 40:95–142, 2011.
46

Information-Theoretic Bounded Rationality

J. Von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton
University Press, Princeton, 1944. ISBN 0691119937.
D. H. Wolpert. Information theory - the bridge connecting bounded rational game theory
and statistical physics. In D. Braha and Y. Bar-Yam, editors, Complex Engineering Systems, chapter Information theory - the bridge connecting bounded rational game theory
and statistical physics. Perseus Books, 2004.
S. Zilberstein. Metareasoning and Bounded Rationality. Asociation for the Advancement
of Artificial Intelligence, 2008.

47

