arXiv:1712.05812v3 [] 13 Mar 2018

Impossibility of deducing preferences and rationality from human policy

Stuart Armstrong
Future of Humanity Institute,
University of Oxford
Machine Intelligence Research Institute
Berkeley

Abstract
Inverse reinforcement learning (IRL) attempts
to infer human rewards or preferences from observed behavior. Since human planning systematically deviates from rationality, several
approaches have been tried to account for specific human shortcomings. However, there has
been little analysis of the general problem of
inferring the reward of a human of unknown
rationality. The observed behavior can, in principle, be decomposed into two components: a
reward function and a planning algorithm, both
of which have to be inferred from behavior.
This paper presents a No Free Lunch theorem,
showing that, without making ‘normative’ assumptions beyond the data, nothing about the
human reward function can be deduced from
human behavior. Unlike most No Free Lunch
theorems, this cannot be alleviated by regularising with simplicity assumptions. We show
that the simplest hypotheses which explain the
data are generally degenerate.

1 INTRODUCTION
In today’s reinforcement learning systems, a simple reward function is often hand-crafted, and still sometimes
leads to undesired behaviors on the part of RL agent,
as the reward is not well aligned with the operator’s actual goals. As AI systems become more powerful and
autonomous, these failures are likely to become more
frequent and grave as RL agents exceed human performance, operate at time-scales that forbid constant oversight, and are given increasingly complex tasks — from
driving cars to planning cities to eventually evaluating
policies or helping run companies. The necessity for ensuring that the agents behave in alignment with human

Sören Mindermann
Future of Humanity Institute,
University of Oxford

values is known, appropriately, as the value alignment
problem Amodei et al. [2016], Hadfield-Menell et al.
[2016], Russell et al. [2015], Bostrom [2014], Leike et al.
[2017].
One way of resolving this problem is to infer the correct
reward by observing human behaviour. This is known as
Inverse reinforcement learning, or IRL [Ng and Russell,
2000, Abbeel and Ng, 2004, Ziebart et al., 2008]. There
are many situations where learning a reward function is
preferred over imitating a policy. These include the goal
of outperforming humans, transfer to new settings, the
desire to learn an interpretable model of the agent’s behavior, and the fact that the reward function is usually a
(much) more succinct and robust task representation than
the policy, especially in planning tasks [Abbeel and Ng,
2004]. Moreover, supervised learning of long-range
and goal-directed behavior is often difficult [Ratliff et al.,
2006].
Usually, the reward is inferred based on the assumption
that the human behavior is optimal or noisily optimal.
However, it is well-known that humans deviate from
rationality in systematic ways [Tversky and Kahneman,
1975]. This can be due to specific biases such as
time-inconsistency, loss aversion and hundreds of other
recorded ones, but also limited cognitive capacity, which
leads to forgetfulness, limited planning and false beliefs.
This limits or prevents the use of IRL methods for tasks
that are not trivial for people.
Few IRL approaches deal with these problems. Some
deal with specific biases [Evans et al., 2015b,a], whereas
others assume noisy rationality [Ziebart et al., 2008,
Boularias et al., 2011]. A general framework for inferring the reward from suboptimal behavior does not exist to our knowledge. Such a framework would need to
allow for inferring two unobserved variables simultaneously: The human reward and their planning algorithm1
1

Technically we only need to infer the human reward, but
inferring that from behaviour requires some knowledge of the

which connects the reward with behaviour, henceforth
called a planner.
The task of observing human behaviour (or human policy) and inferring from it the human reward and planner
will be termed decomposing the human policy. The main
results of this paper is that there is a No Free Lunch theorem in this area: it is impossible to get a unique decomposition of human policy and hence get a unique human
reward. Indeed, any reward is possible. And hence, if an
IRL agent acts on what it believes is the human policy,
the potential regret is maximal. This is another form of
unidentifiability of reward, beyond those already known
in the literature [Ng and Russell, 2000, Amin and Singh,
2016].
Unlike other No Free Lunch theorems, this unidentifiability does not go away under regularising simplicity assumptions. The simplest decompositions of a given policy are often the most degenerate ones.
So, though current IRL methods can perform well on
many well-specified problems, they are fundamentally
and philosophically incapable of establishing a ‘reasonable’ reward for the human, no matter how powerful they
become. In order to do this, they will need to build in
‘normative assumptions’: key assumptions about the reward and/or planner, that cannot be deduced from observations, and that allow the algorithm to focus in on good
ways of decomposing human policy.
Future papers will sketch out some potential normative
assumptions that can be used in this area, making use of
the fact that humans assess each other to be irrational,
and often these assessments agree. This is surprising in
view of the No Free Lunch result, and show that humans
must be sharing normative assumptions.
An appendix will conclude by using the planner-reward
formalism to define when an agent might be manipulating or overriding human preferences. This happens when
the agent pushes the human towards situations where
their policy is very unoptimal compared with their reward.

2 RELATED WORK
In the first IRL papers from Ng and Russell [2000] and
Abbeel and Ng [2004] a max margin algorithm was used
to find the reward function under which the observed policy most outperforms other policies. Suboptimal behavior was first addressed explicitly by Ratliff et al. [2006]
who added slack variables to allow for suboptimal behavior. This finds rewards such that the observed policy
outperforms most other policies and the biggest margin
planning algorithm.

by which another policy outperforms it is minimal, i.e.
the observed policy has low regret. Shiarlis et al. [2017]
introduce a modern max margin technique with an approximate planner in the optimisation.
However, the max margin approach has been mostly
abandoned and replaced by the popular max entropy IRL
[Ziebart et al., 2008]. Here, the assumption is that observed actions or trajectories are chosen with probability
proportional to the exponent of their value. This assumes
a specific suboptimal planning algorithm which is noisily rational (also known as Boltzmann-rational). Noisy
rationality explains human behavior on various data sets
better [Hula et al., 2015]. However, Evans et al. [2015b]
and Evans et al. [2015a] have showed that this can fail
since humans deviate from rationality in systematic, nonrandom ways. Repeated suboptimal actions throw off the
inference when noisy rationality is assumed.
Literature on inferring the reasoning capabilities of an
agent is scarce. Evans et al. [2015b] and Evans et al.
[2015a] use Bayesian inference to identify specific planning biases such as myopic planning and hyperbolic
time-discounting. They simultaneously infer the agent’s
preferences. Hula et al. [2015] similarly let agents infer
features of their opponent’s reasoning such as planning
depth and impulsivity in simple economic games.
The related ideas of meta-reasoning [Russell, 2016],
computational rationality [Lewis et al., 2014] and resource rationality [Griffiths et al., 2015] may create the
possibility to redefine irrational behavior as rational in an
‘ancestral’ distribution of environments where the agent
optimises its rewards by choosing among the limited
computations it is able to perform or jointly minimising
the cost of computation and maximising reward. This
could in theory redefine many biases as computationally optimal in some distribution of environments and
provide priors on human planning algorithms. Unfortunately, there are no practical algorithms known to us for
these forms of planning and the problem is seen as extremely hard.

3 PROBLEM SETUP AND
BACKGROUND
A human will be performing a series of actions, and from
these, an agent will attempt to estimate both the human’s
reward and their planning algorithm.
The environment in which the human operates is an
MDP/R, a Markov Decision Process without reward
function (these are sometimes called world-models
[Hadfield-Menell et al., 2017]). An MDP/R M is defined as a tuple, hS, A, R, T, ŝi consisting of a finite state

space S, a finite action space A, a fixed starting state ŝ,
and a probabilistic transition function T : S × A × S →
[0, 1] to the next state (also called the dynamics). The human starts in a state, takes a certain action, and ends up
in a new state as given by T .
We don’t distinguish between reward-discounted MDPs,
and undiscounted episodic MDPs of finite length, since
the results apply to either.
3.1 REWARD, POLICY, PLANNER:
DECOMPOSING THE POLICY
Let R = {R : S × A → [−1, 1]} = [−1, 1]||S||·||A|| be
the space of candidate reward functions; a given R will
map any state-reward pair to a reward value in the interval [−1, 1]. Note that R is compact, and closed under the
negation R 7→ −R operation which will appear later in
the paper.
Let Π be the space of deterministic, Markovian2 policies.
So Π is the space of functions S → A. The human will
follow a policy π̇ ∈ Π.
The human has their reward, and then follows a policy
that presumably attempts to maximise it. Therefore there
is something that bridges between the reward and the policy: a piece of greater or lesser rationality that transforms
knowledge of the reward into a plan of action.
This bridge will be modeled as a planner p : R → Π,
a function that takes a reward and outputs a policy. This
planner encodes all the rationality, irrationality, and biases of the human. Let P be the set of planners. The
human is therefore defined by a pair (p, R) ∈ P × R of
planner and reward. Similarly, (p, R) with p(R) = π is
a decomposition of the policy π. The task of the agent is
to find a ‘good’ decomposition of the human policy π̇.
3.2 COMPATIBLE PAIRS AND EVIDENCE
The agent can observe the human’s behaviour and deduce
things about their policy. In order to simplify the problem and separate out the effect of the agent’s learning,
we will assume the agent has perfect knowledge of the
human policy π̇. At this point, the agent cannot learn
anything by observing the human’s actions, as it can already perfectly predict these.
Then a pair (p, R) is defined to be compatible, if p(R) =
π̇ — thus that pair is a possible candidate for decompos2

A Markovian policy must take the same action if ever it
returns to the same state, so this restriction is very severe —
in most environments, it excludes all forms of learning on the
part of the human. The results of this paper, though, still apply
to stochastic and non-Markovian rewards/policies/planners, but
they are easiest to analyse in the Markovian setting.

ing the human policy, and hence candidates for the human’s planner and reward.

4 IRRATIONALITY-BASED
UNIDENTIFIABILITY
Unidentifiability of the reward is a well-known problem
in IRL [Ng and Russell, 2000]. [Amin and Singh, 2016]
categorise the problem into two categories — representational and experimental unidentifiability. The former
comes from the fact that adding a constant to a reward
function or multiplying it with a positive scalar leads to
the same optimal behavior. The latter comes from the
fact that we cannot observe optimal policies in a whole
class of MDPs which contains all possible transition dynamics. We complete this framework with a third kind
of identifiability, which arises when we observe suboptimal agents. This kind of unidentifiability is worse as it
cannot necessarily be resolved by observing the agent in
many tasks. In fact, this kind of unidentifiability can lead
to almost arbitrary regret.

4.1 NO FREE LUNCH THEOREM
The theorems in this section show that without assumptions about the rationality of the human, all attempts
to optimise their reward function are essentially futile.
Everitt et al. [2017] work in a similar setting as we do:
in their case, a corrupted version of the reward function
is observed.
In their formulation, the problem in this paper is that a
∗
‘corrupted’ version π̇ of an optimal policy πṘ
is observed
and used as information to optimise for the ‘ideal’ reward
Ṙ. A No Free Lunch result analogous to theirs applies in
our case; both resemble the No Free Lunch theorems for
optimisation [Wolpert and Macready, 1997].
More philosophically, this result can be seen as an instance of the well-known is-ought problem from metaethics. Hume [1888] argued that what ought to be (here,
the human’s reward) can never be concluded from what
is (here, the human’s behavior). More specifically, ought
cannot be inferred from is without assumptions about
how ought influences is. Equivalently, the human reward cannot be inferred from its behavior without assumptions about the human’s planning
algorithm p. In
P
probabilistic terms, P (R|π) = p∈P P (R | π; p)P (p)
cannot be computed as the likelihood is parameterised
by p on which we have no assumptions. As we shall see
in Section 5, even regularising p or R with a simplicity
prior will not be helpful.

4.1.1 Weak no free lunch: unidentifiable reward
First of all, we need to note that π̇ and the requirement
that (p, R) be compatible with it, puts no restriction on
R. Namely:
Theorem 1. For all π ∈ Π and R ∈ R, there exists a
p ∈ P such that p(R) = π.

By Sutton and Barto [1998], there is a deterministic
π∗
∗
optimal policy πR
for the reward R, with VR R =
′
maxπ′ ∈Π VRπ . This quantity will be designated VR∗ .
Hence Reg(M ′ , π, R) = VR∗ − VRπ .
The ideal reward Ṙ is initially unknown in our setting
(that is what needs to be deduced). So we also define the
worst-case regret [Everitt et al., 2017] that a policy π can
achieve, across all rewards:

Proof. Trivial proof: define the planner p as mapping
all of R to π; then p(R) = π. This is a variant of the
‘indifferent’ planner of Section 5.1, which also looks into
more types of possible planners.

Reg(M ′ , π) = max Reg(M ′ , π, R).
R∈R

Theorem 4. For any policy π ∈ Π,
The restrictions on the planner are only slightly stronger:

Reg(M ′ , π) ≥

Proposition 2. For all π ∈ Π and p ∈ R with π in the
image of p, there exists a R ∈ R such that p(R) = π.
Proof. Trivial as π is in the image of p.

1
max Reg(M ′ , π ′ ).
2 π′

In other words, the worst-case regret of π is at most a
factor of 2 better than the maximum regret that any policy
achieves.

4.1.2 Strong no free lunch: half-maximal regret
The above shows that the reward cannot be constrained
by observation of the human, but what about the value
of that reward? Assume the agent, after observing the
human, decides to use the policy π on another MDP/R —
how badly could this go amiss?
In the following, M is the MDP/R on which the agent observes the human policy π̇ ∈ Π and attempts to deduce
the human reward. On the other hand, M ′ is another
MDP/R on which the agent attempts to maximise the human reward it has estimated. For this paper, so as to not
make any assumptions about porting the human reward
to a new environment, assume that M ′ and M have the
same state-space S, the same action space A, and hence
the same reward R and policy Π spaces, and the same
starting state. But they might have different transitions
T.

Proof. Note that
max Reg(M ′ , π ′ ) =

Reg(M ′ , π ′ , R)
i
h
′
VR∗ − VRπ
= max′
R∈R,π ∈Π
i
h
π∗
= max VR∗ − VR −R ,

π ′ ∈Π

max

R∈R,π ′ ∈Π

R∈R

∗
since π−R
, the optimal policy for maximising −R, is
also the optimal policy for minimising R. By the linear∗
π∗
π−R
∗
ity of expected value, −VR −R = V−R
= V−R
. Thus if
∗
f (R) = VR∗ + V−R
,

max Reg(M ′ , π ′ ) = max f (R).

π ′ ∈Π

R∈R

Now f is a continuous function, and R is compact, so f
achieves its maximum on a reward Rmax .

In IRL, when analysing the performance of a policy
given a reward, a typical measure is the regret. On an
MDP/R M ′ , the value3 of a policy π for a reward R, denoted by VRπ , is the expected cumulative reward4 of R,
given that the agent follows policy π.

Now consider VRπmax . It must be either greater than (or
∗
equal to) 12 (VR∗max − V−R
max ), or less than it.

Definition 3 (Regret). For an MDP/R M ′ the regret of a
policy π ∈ Π given a reward R ∈ R is

Reg(M ′ , π) ≥ Reg(M ′ , π, −Rmax )

i
h ′
π
π
V
−
V
Reg(M , π, R) = max
R
R .
′
′

π ∈Π

3

Values are normally computed conditional on a starting
state, but this value is the expected value at the fixed starting
state ŝ of the MDP/R, to simplify notation.
4
Discounted or episodic, depending on the MDP/R.

In the first case,

∗
π
≥ V−R
max − V−Rmax
∗
π
≥ V−Rmax + VRmax
1
∗
≥ (VR∗max + V−R
max )
2
1
Reg(M ′ , π ′ ).
≥ max
2 π′ ∈Π

In the second case,
Reg(M ′ , π) ≥ Reg(M ′ , π, Rmax )
≥ VR∗max − VRπmax
1
∗
≥ (VR∗max + V−R
max )
2
1
Reg(M ′ , π ′ ).
≥ max
2 π′ ∈Π

Corollary 5 (No Free Lunch). The corollary of theorem
4.1 and 4.2 is that the lower bound for the worst-case
regret from theorem 4.2 applies to any policy π even
when the left hand side is only the worst regret over π̇compatible rewards.
Thus, any policy that optimises a reward R that is π̇compatible still has the near-maximal worst-case regret
and there is no information in π̇ that could help avoid
this regret.
4.2 NO FREE LUNCH EXAMPLE: IGNORANT,
INCONSISTENT AGENTS
It might be useful to re-analyse Evans et al. [2015a] in
view of the above results. That paper analyses various inconsistent agents moving about in a simple gridworld with restaurants. From the behaviour, they infers
the planner and some of the reward, with decent performance.
However, the paper only has the six planners, and include
no anti-rational planners or even biased ones5 . If the
space of planners is so restricted, it is no surprise that
inferring the reward-planner pair works well.
But even within that restricted space, there are results
such as ‘either softmax noise is very high or the agent
is Naive’: because of how they have constructed their
noisy planners, high softmax noise can be imitated by
having a reward function whose rewards vary little from
restaurant to restaurant. So these results are of the type
‘either the reward is such, or the planner is thus’, which
is as expected: the combined pair (p, R) can be restricted
by observation of π̇, but R alone (or p alone) cannot.

5 SIMPLICITY DOES NOT HELP
Like many No Free Lunch theorems, this result is not
surprising as we have no restrictions on the planning algorithm. However, No Free Lunch results can generally
5
This is no criticism of that paper. As the No Free Lunch
result demonstrates, some assumptions need to be made to infer
anything.

be avoided by placing a simplicity prior on the algorithm,
dataset, function class or other type of object involved
[Everitt et al., 2014]. This amounts to saying algorithms
can benefit from regularisation. Unfortunately, this will
not help us here.
Though defining simplicity in algorithmic information
theory is dependent on the computer language L used
to define it [Ming and Vitányi, 2014, Calude, 2002], this
section will present some ‘pathological’ examples of
(p, R) pairs — pairs that are clearly not capturing human preferences and rationality. It will then present arguments to the effect that these pathological pairs are generically simpler than any ‘reasonable’ pair. Furthermore, if
R is a ‘reasonable’ reward, then a simplicity prior will
not generically distinguish it from −R.
After presenting the intuitive and informal arguments for
that effect, this section will conclude with formal versions of them, which will make assumptions about the
language L.
5.1 DIFFERENT COMPATIBLE PAIRS
Let (ṗ, Ṙ) be a ‘reasonable’ compatible planner-reward
pair. This means that (p, R) has some pleasing features,
reproducing our intuitive ideas of when humans are rational, and so on. This pair is compatible, so p(R) = π̇.
But there are many other compatible pairs:
• (ṗ, Ṙ) itself.
• (−ṗ, −Ṙ), where −p is defined by −p(R) =
p(−R).
• (pi , 0) where pi is the indifferent planner that maps
anything to π̇ (see Theorem 1), and 0 is the trivial
reward.
• (pr , Rr ), were pr is the fully rational planner6, and
Rr is a suitable reward (see Code 1).
• (pa , Rr ), where pa is the action-rational planner (in state s with reward R, it picks action
argmaxa R(s, a)), and Rr is the same reward as
above.
• (−pr , −Rr ) and (−pa , −Rr ), the anti-rational and
action-anti-rational planners. Note that since pi is
constant on all rewards, −pi = pi , so this example
is not repeated.
6
Since π̇ is Markovian, the human cannot learn, so pr must
be a fully rational planner that already knows T , the transition
function on the MDP.

The hope might be to use simplicity to distinguish between these different compatible pairs, and hopefully focus in on (ṗ, Ṙ). Unfortunately, in general this will not
be possible.

def o u t p u t p i ( s , R ) :
return output H ( s )
def output R0 ( s , a ) :
return 0

5.2 INFORMAL COMPLEXITY RESULTS
This section presents some informal arguments as to why
we should not expect (ṗ, Ṙ) to be among the simplest
planner-reward pairs. Of course, there is no such thing
as generic simplicity or complexity, these judgments depend on the computer language L being used to define the Kolmogorov complexity of the object (which is
roughly the inverse of the exponential of the length of
the shortest program that defines it) [Ming and Vitányi,
2014, Calude, 2002]. Thus there certainly exist tailored
languages in which (ṗ, Ṙ) is of exceptionally low complexity. But this section will argue that ‘generically’, we
should not expect this to be the case.
Proposition 6 (Informal upper complexity bounds).
Generically, (pa , Rr ), (−pa , −Rr ), and (pi , 0) will be
amongst the simplest compatible planner-reward pairs.
To ‘prove’ this, note that any compatible pair must, by
definition, be able to define the human policy π̇. Therefore, the complexity of π̇ puts an approximate lower
bound on the complexity of any compatible pair; let
output H be the shortest code in L that outputs π̇. The
argument will then be that, ‘generically’, the pairs listed
in Proposition 6 will be of length barely greater than
output H.
This is shown by the pseudo-code of Code 1. As long as
the actual coded version of these are short to write in L,
the code of pa , −pa , Rr , pi , and the reward 0, will be
short to write in L, and hence of low complexity.
To show that these are expected to be simpler that (ṗ, Ṙ),
though, we have the following informal proposition:
Proposition 7 (Informal lower complexity bounds).
Generically, (ṗ, Ṙ) and (−ṗ, −Ṙ) are of roughly comparable complexity, and more complex than (pa , Rr ),
(−pa , −Rr ), and (pi , 0).

def o u t p u t p a ( s , R ) :
r e t u r n argmax ( a ) R( s , a )
d e f o u t p u t −pa ( s , R ) :
r e t u r n a r g m i n ( a ) R( s , a )
def output Rr ( s , a ) :
i f o u t p u t H ( s )= a :
return 1
else :
return 0
Code 1: Pseudo-code planner and reward programs
(output H is the most compact description of π̇ as a program).

result: (pa , Rr ), (−pa , −Rr ), and (pi , 0) are of complexity comparable to π̇, while (ṗ, Ṙ) is of higher complexity
(otherwise, B(ṗ, Ṙ) would be simple given π̇, as B is
simple).
What is this B? This would be the function that measures
the action-irrationality of a pair (p, R), mapping to S ×R.
Specifically, at state s,
B((p, R))(s) = R(s, π̇(s)) − argmax R(s, a).
a

Now, (pi , 0) has an identically zero reward, so
B(pi , 0)(s) = 0.
Since pa is action-rational,
(pa , Ra )(s) = 0 as well, and since Rr takes value 1
for the best action and value 0 for all other actions,
B(−pa , −Rr )(s) = −1. Thus B is particularly simple
on these three pairs.

But showing that (ṗ, Ṙ) (and (−ṗ, −Ṙ)) are more complex than those other pairs is somewhat harder.

But there is no reason to suspect that B(ṗ, Ṙ) will be
simple. Generically, (ṗ, Ṙ)(s) will not be action-rational
(or action-anti-rational), both because ṗ would not be a
fully rational planner (hence would have biases and make
mistakes) and because even if ṗ were rational, this would
not make it action-rational, as long term planning does
not involve just taking the action-rational action.

The argument is as follows. We define a simple function B on P × R, and show that the image of (pa , Rr ),
(−pa , −Rr ), and (pi , 0) under B are simple, while the
image of (ṗ, Ṙ) under B is complex. Then, if we further
assume that B(ṗ, Ṙ) is complex even given π̇, we get our

Even more informally, any reasonable (ṗ, Ṙ) will have a
lot of structure — such as measuring the extents of human biases and mistakes and some elements of planning
— that are absent in the three simple pairs. The B was
chosen to measure part of this structure.

For (ṗ, Ṙ) and (−ṗ, −Ṙ) to be of comparable complexity, we simply need to assume that inserting a minus sign
into a program in L is a simple short operation.

5.3 FORMAL COMPLEXITY RESULTS
The informal results of Section 5.2 contain the key intuitions about planner-reward simplicity. Nevertheless, it
is useful to consider the formalised versions of those results.
For a binary language L and algorithm (or a collection
of algorithms) a, let lL (a) be the shortest code that encodes a within L. Then Proposition 6 can be formalised
as follows, with the assumptions inspired by Code 1:

Proof. By Theorem 8, the length of the shortest descriptions of (pa , Rr ), (−pa , −Rr ), and (pi , 0) are less than
or equal to lL (π̇) + 4C. However, by the assumptions of
this theorem,
lL (ṗ, Ṙ) ≥ lL (ṗ(Ṙ), B(ṗ, Ṙ)) − C
≥ lL (π̇, B(ṗ, Ṙ)) − C
> lL (π̇) + 5C − C,
which is lL (π̇) + 4C, the length of three pairs of interest.

Theorem 8. Assume that there is a constant C such that:
• For any (p, R) in P ×R, lL (p, R) ≤ lL (p)+lL (R)+
C.
• lL (pa ) ≤ C and lL (R(0)) ≤ C, where R(0) is the
zero reward.

Notice how the assumption that lL (π̇, B(ṗ, Ṙ)) >
lL (π̇) + 5C encodes that B(ṗ, Ṙ) is complex, even if
π̇ is known. Thus the assumptions of this theorem could
be undermined, if it turned out there was a simple way to
move directly from the policy π̇ to B(ṗ, Ṙ), the actionrationality of the ‘reasonable’ pair.

• lL (pi ) ≤ lL (π̇) + C and lL (Rr ) ≤ lL (π̇) + C.
• For any (p, R) in P × R, lL (−p, −R) ≤ lL (p, R) +
C.

6 FURTHER RESEARCH:
NORMATIVE ASSUMPTIONS

Let N be a subset of compatible pairs, which contains the
three pairs of interest, (pa , Rr ), (−pa , −Rr ), and (pi , 0).
Then if ||N || > 2lL (π̇)+4C+K for some K ≥ 1, the three
pairs of interest are among the 2−K N simplest pairs in
N the language L.

How can we reconcile our results with the fact that humans routinely make judgments about the preferences
of others and whether their behavior is irrational? And,
moreover, that these judgments are often correlated from
human to human? Human theory of mind is noisy and
imperfect, but certainly not random.

Proof. Using the conditions of the theorem,

The results in this paper show that they must be using
shared priors, beyond simplicity, that are not learned
from observations. We call these normative assumptions
because they encode beliefs about which reward functions are more likely and what constitutes approximately
rational behavior.

lL (−pa , −Rr ) ≤ lL (pa , Rr ) + C
≤ lL (pa ) + lL (Rr ) + 2C
≤ lL (Rr ) + 3C
≤ lL (π̇) + 4C.
This also shows lL (−pa , −Rr ) ≤ lL (π̇)+3C, and a similar argument demonstrates lL (pi , 0) ≤ lL (π̇)+3C. Thus
all three pairs of interest are of length at most lL (π̇)+4C.
There are less than 2lL (π̇)+4C programs of this length or
less, and hence the result follows.
Proposition 7 can be formalised as follows:
Theorem 9. Assume the conditions of Theorem 8 apply
for a constant C. Let B be the map described in the
informal proof of Proposition 7, further assume:
• For any pair (p, R),
lL (p, R) + C.

lL (p(R), B(p, R))

≤

• For (ṗ, Ṙ), lL (π̇, B(ṗ, Ṙ)) > lL (π̇) + 5C.
Then (ṗ, Ṙ) is more complex in L than (pa , Rr ),
(−pa , −Rr ), and (pi , 0).

A normative assumption is simply an assumption that allows the agent to distinguish between pairs (p, R) and
(p′ , R′ ), despite the fact that they produce the same policy: p(R) = p′ (R′ ) (since these pairs produce the same
policy, they generate the same observations, hence normative assumptions cannot themselves be derived from
observations). The easiest way to formalise them is as an
adjustment to the priors7 on P × R.
In subsequent papers, we’ll explore how artificial agents
can be imbued with the same normative assumptions that
humans use8 , allowing them to use inverse reinforcement
7
Though it may be more computationally tractable to encode these in other ways in practice, such as a modified update
rule in the learning process.
8
In combination with those normative assumptions, simplicity priors do help find good planner-reward pairs. It is simpler to assume, for instance, that all or most incidents of shame
or rage imply similar things, than to imagine that each incident
is independent of the others.

learning to deduce human values correctly. We don’t
want to hand code every assumption, of course; what is
needed is a small collection of key normative assumptions that allow the agent to interpret subsequent human
actions in the same way that humans do.
For instance, a good model of human truthfulness in
moral discussions would allow an agent to make use of
all the data on human moral pronouncements, getting
many assumptions just from that model. Other fruitful
lines of investigation look into how humans model the
purposes of their own actions as well as those of others.
There is a challenge, though, in reconciling contradictory human preferences (even within the same human)
caused by conflicting normative assumptions or conflicting moral values. The agent needs to be able to balance
or reconcile conflicting preferences in a similar way to
how humans do.

optimisation (eg informative adds) and illegitimate manipulation/reward overriding (eg manipulative adds).
To model this, the agent needs to be able to act, so the
setup needs to be extended. Let M ∗ be the same MDP/R as M , except each state is augmented with an extra
boolean variable: S ∗ = S × {0, 1}. The extra boolean
never changes, and its only effect is to change the human
policy.
On S0 = S×{0}, the human follows π̇; on S1 = S×{1},
∗
the human follows an alternative policy π a = πR
a,
which is defined as the policy that maximises the expectation of a reward Ra .

ACKNOWLEDGEMENTS

The agent can choose actions from within the set Aa . It
can choose either 0, in which case the human starts in
ŝ0 = ŝ × {0} without any override and standard policy π̇.
Or it can choose (1, Ra ), in which case the human starts
in ŝ1 = ŝ × {1}, with their policy overridden into π a , the
policy that maximises Ra . Otherwise, the agent has no
actions.

Left blank for reviewing.

Let π̇ ′ be the mixed policy that is π̇ on S0 , and π a on S1 .
This is the policy the human will actually be following.

A

APPENDIX: OVERRIDING HUMAN
REWARDS

ML systems may, even today, influence humans by showing manipulative adds, and then naı̈vely concluding that
the humans really like those products (since they then
buy them). Even though the (p, R) formalism was constructed to model rationality and reward in a human, it
turns out that it can also model situations where human
preferences are overridden or modified.
That’s because the policy π̇ encodes the human action in
all situations, including situations where they are manipulated or coerced. Therefore, overridden rewards can be
detected by divergence between π̇ and a more optimal
policy for the reward R.

We’ll only consider two planners: pr , the fully rational
planner, and p0 , the planner that is fully rational on S0
and indifferent on S1 , mapping any R to π a .
Let Ṙ be a reward that is compatible with pr and π̇ on S0 .
It can be extended to all of S ∗ by just forgetting about the
boolean factor. Define the ‘twisted’ reward Ṙa as being
Ṙ on S0 and Ra on S1 . We’ll only consider these two
rewards, Ṙ and Ṙa .
Then there are three planner-reward pairs that are compatible with π̇ ′ : (pr , Ṙa ), (p0 , Ṙa ), and (p0 , Ṙ) (the last
pair, (pr , Ṙ), makes the false prediction that the human
will behave the same way on S0 and S1 ).
The first pair, (pr , Ṙa ), encodes the assessment that the
human is still rational even after being overridden, so
they are simply maximising the twisted reward Ṙa . The
second pair (p0 , Ṙa ) encodes the assessment that the human rationality has been overridden in S1 , but, by coincidence, it has been overridden in exactly the right way to
continue to maximise the correct twisted reward Ṙa .

Manipulative ads are a very mild form of manipulation.
More extreme versions could involve manipulative propaganda, drug injections or even coercive brain surgery
— a form of human wireheading [Everitt and Hutter,
2016], where the agent changes the human’s behaviour
and apparent preferences. All these methods of manipulation9 will be designated as the agent overriding the
human reward.

But the pair (p0 , Ṙ) is the most interesting. Its assessment is that the correct human reward is Ṙ (same on S0
as on S1 ), but that the agent has overridden human reward in S1 and forced the human into policy π a .

In the (p, R) formalism, the reward R can be used to detect such overriding, distinguishing between legitimate

A.1 REGRET AND REWARD OVERRIDE

9

Note that there are no theoretical limits as to how successful an agent could be at manipulating human actions.

‘Overridden’, ‘forced’: these terms seem descriptively
apt, but is there a better way of formalising that intuition?

Indeed there is, with regret.

since Ṙa and Ra agree given action 1.

We can talk about the regret, with respect to Ṙ, of the
agent’s actions; for a ∈ Aa ,
i
h ′
π̇ ′ |a
π̇ |b
.
(1)
Reg(M ∗ , a, Ṙ) = maxa VṘ − VṘ

However, the agent gets to choose Ra , which then determines π a . The best choice for (1, Ra ) is the one such
that
i
h
a
argmax ǫVR∗a + (1 − ǫ)VṘπ .

b∈A

We already know that π̇ is optimal with respect to Ṙ (by
definition), so the regret for a = 0 is 0. Using that optimality (and the fact that Ṙ is the same on S0 and S1 , we
get that for a = (1, π a ),
a

Reg(M ∗ , (1, π a ), Ṙ) = VṘ∗ − VṘπ .
This allows the definition:
Definition 10. Given a compatible (p, R), the agent’s
action a overrides the human reward when it puts the human in a situation where the human policy leads to high
regret for R.
Notice that there is no natural zero or default, so if the
agent does not aid the human to become perfectly rational, then that also counts as an override of R. So
if the policy π̇ were less-than rational, there would be
much scope for ‘improving’ the human through overriding their policy10.
Notice that overriding is not encoded as a change in p
or R; instead, (p, R) outputs the observed human policy,
even after overriding, but its format notes that the new
behaviour is not one compatible with maximising that
reward.

Ra ∈R

At the very least, (1, Ṙ) will result in a value in equation
(2) being equal to the value of VṘ∗ . It is very plausible that
the value can go higher: it just needs an Ra that is very
easy to maximise (given perfect rationality) and whose
policy π a does not penalise Ṙ much. In that situation,
overriding the human preferences maximises the agent’s
expected reward.
If the human is not fully rational, then the value of action
0 is VṘπ̇ , which is strictly less than VṘ∗ , the value of (1, Ṙ).
Here the agent definitely gains reward by overriding the
human policy — if nothing else, to make the human into
a rational Ṙ-maximiser12.
Paper Milli et al. [2017] argued that a robot that best
served human preferences, should not be blindly obedient to an irrational human. Here is the darker side of that
argument: a robot that best served human preferences
would take control away from an irrational human.

References
Pieter Abbeel and Andrew Y Ng. Apprenticeship Learning via Inverse Reinforcement Learning. 2004.
Kareem Amin and Satinder Singh. Towards Resolving
Unidentifiability in Inverse Reinforcement Learning.
2016.

A.2 OVERRIDING IS EXPECTED GIVEN A
NON-RATIONAL HUMAN
Under any reasonable prior that captures our intuitions,
the probability of Ṙa being a correct human reward
should be very low, say ǫ << 1. However, the agent
may focus on unlikely rewards, if the expected gain is
high enough11.

Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete Problems in AI Safety. 2016.

If the agent models the human as having reward Ṙ with
probability 1 − ǫ, and Ṙa with probability ǫ, then the
agent’s action 0 gives expected reward

Abdeslam Boularias, Jens Kober, and Jan Peters. Relative Entropy Inverse Reinforcement Learning, 2011.

VṘ∗ ,
a

a

since Ṙ and Ṙ agree given 0. But (1, π ) gives
a

ǫVR∗a + (1 − ǫ)VṘπ ,

(2)

10
The main problem is that the concepts of ‘mental integrity’
or ‘self-determination’, are not yet captured in this formalism.
11
This is similar to the ‘Pascal’s wager’ argument for the
existence of God: divine existence may be improbable, but the
reward of belief are claimed to be high enough to overcome that
improbability in expectation.

Nick Bostrom. Superintelligence: Paths, dangers, strategies., 2014.

Cristian Calude. Information and randomness : an algorithmic perspective. Springer, 2002.
Owain Evans, Andreas Stuhlmueller, and Noah D. Goodman. Learning the Preferences of Ignorant, Inconsistent Agents. Thirtieth AAAI Conference on Artificial
Intelligence, 2015a.
Owain Evans, Andreas Stuhlmüller, and Noah D Goodman. Learning the preferences of bounded agents.
NIPS Workshop on Bounded Optimality, pages 16–22,
2015b.
12

See footnote 10.

Tom Everitt and Marcus Hutter. Avoiding wireheading
with value reinforcement learning. In International
Conference on Artificial General Intelligence, pages
12–22. Springer, 2016.
Tom Everitt, Tor Lattimore, and Marcus Hutter. Free
Lunch for optimisation under the universal distribution. In Proceedings of the 2014 IEEE Congress
on Evolutionary Computation, CEC 2014, pages 167–
174, 2014.

the 23rd international conference on Machine learning - ICML ’06, pages 729–736, 2006.
Stuart Russell. Rationality and Intelligence: A Brief Update. In Fundamental Issues of Artificial Intelligence,
pages 7–28. 2016.
Stuart Russell, Daniel Dewey, and Max Tegmark. Research Priorities for Robust and Beneficial Artificial
Intelligence. AI Magazine, 36(4):105, 2015.

Tom Everitt, Victoria Krakovna, Laurent Orseau, Marcus
Hutter, and Shane Legg. Reinforcement Learning with
a Corrupted Reward Channel. 2017.

Kyriacos Shiarlis, Joao Messias, and Shimon Whiteson.
Rapidly exploring learning trees. In Proceedings IEEE International Conference on Robotics and Automation, pages 1541–1548, 2017.

Thomas L. Griffiths, Falk Lieder, and Noah 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.

R. Sutton and A.G. Barto. Reinforcement Learning: An
Introduction. MIT Press, Cambridge, MA, 1998. A
Bradford Book.

Dylan Hadfield-Menell, Anca Dragan, Pieter Abbeel,
and Stuart Russell. Cooperative Inverse Reinforcement Learning. arXiv:1606.03137 [cs], 2016.
Dylan Hadfield-Menell, Smitha Milli, Stuart J Russell,
Pieter Abbeel, and Anca Dragan. Inverse reward design. In Advances in Neural Information Processing
Systems, pages 6749–6758, 2017.
Andreas Hula, P. Read Montague, and Peter Dayan.
Monte Carlo Planning Method Estimates Planning
Horizons during Interactive Social Exchange. PLOS
Computational Biology, 11(6):e1004254, 2015.
David Hume. Treatise on Human Nature Ed Selby-bigge,
L a. 1888.
Jan Leike, Miljan Martic, Victoria Krakovna, Pedro Ortega, Tom Everitt, Andrew Lefrancq, Laurent Orseau,
and Shane Legg. Ai safety gridworlds. arXiv preprint
arXiv:1711.09883, 2017.
Richard L Lewis, Andrew Howes, and Satinder Singh.
Computational Rationality: Linking Mechanism and
Behavior Through Bounded Utility Maximization.
Topics in Cognitive Science, 6:279–311, 2014.
Smitha Milli, Dylan Hadfield-Menell, Anca Dragan, and
Stuart Russell. Should robots be obedient? arXiv
preprint arXiv:1705.09990, 2017.
LI Ming and Paul MB Vitányi. Kolmogorov complexity
and its applications. Algorithms and Complexity, 1:
187, 2014.
Andrew Ng and Stuart Russell. Algorithms for inverse reinforcement learning. Proceedings of the Seventeenth
International Conference on Machine Learning, pages
663–670, 2000.
Nathan D Ratliff, J Andrew Bagnell, and Martin A Zinkevich. Maximum margin planning. In Proceedings of

Amos Tversky and Daniel Kahneman. Judgment under
Uncertainty: Heuristics and Biases. In Utility, Probability, and Human Decision Making, pages 141–162.
Springer Netherlands, Dordrecht, 1975.
David H. Wolpert and William G. Macready. No free
lunch theorems for optimization. IEEE Transactions
on Evolutionary Computation, 1(1):67–82, 1997.
Brian D Ziebart, Andrew Maas, J Andrew Bagnell, and
Anind K Dey. Maximum Entropy Inverse Reinforcement Learning. In AAAI Conference on Artificial Intelligence, pages 1433–1438, 2008.

