=Paper=
{{Paper
|id=Vol-2808/Paper_26
|storemode=property
|title=Performance of Bounded-Rational Agents With the Ability to Self-Modify
|pdfUrl=https://ceur-ws.org/Vol-2808/Paper_26.pdf
|volume=Vol-2808
|authors=Jakub Tětek,Marek Sklenka,Tomáš Gavenčiak
|dblpUrl=https://dblp.org/rec/conf/aaai/TetekSG21
}}
==Performance of Bounded-Rational Agents With the Ability to Self-Modify==
<pdf width="1500px">https://ceur-ws.org/Vol-2808/Paper_26.pdf</pdf>
<pre>
      Performance of Bounded-Rational Agents With the Ability to Self-Modify*
                                  Jakub Tětek1† , Marek Sklenka2 , Tomáš Gavenčiak3
                                       1
                                           BARC, University of Copenhagen j.tetek@gmail.com
                                            2
                                              University of Oxford sklenka.marek@gmail.com
                                                3
                                                  Independent researcher gavento@ucw.cz




                            Abstract                                  ing systems and one of the major proposed models for future
                                                                      AI systems1 .
  Self-modification of agents embedded in complex environ-
                                                                         If strong AI systems with the ability to act in the real
  ments is hard to avoid, whether it happens via direct means
  (e.g. own code modification) or indirectly (e.g. influencing        world are ever deployed2 , it is very likely that they will have
  the operator, exploiting bugs or the environment). It has been      some means of deliberately manipulating their own imple-
  argued that intelligent agents have an incentive to avoid mod-      mentation, either directly or indirectly (e.g. via manipulat-
  ifying their utility function so that their future instances work   ing the human controller, influencing the development of a
  towards the same goals.                                             future AI, exploiting their own bugs or physical limitations
  Everitt et al. (2016) formally show that providing an option        of the hardware, etc). While the extent of those means is un-
  to self-modify is harmless for perfectly rational agents. We        known, even weak indirect means could be extensively ex-
  show that this result is no longer true for agents with bounded     ploited with sufficient knowledge, compute, modelling ca-
  rationality. In such agents, self-modification may cause ex-        pabilities and time.
  ponential deterioration in performance and gradual misalign-
  ment of a previously aligned agent. We investigate how the             Omohundro (2008) argues that every intelligent system
  size of this effect depends on the type and magnitude of im-        has a fundamental drive for goal preservation, because when
  perfections in the agent’s rationality (1-4 below). We also dis-    the future instance of the same agent strives towards the
  cuss model assumptions and the wider problem and framing            same goal, it is more likely that the goal will be achieved.
  space.                                                              Therefore, Ohomundro argues, a rational agent should never
  We examine four ways in which an agent can be bounded-              modify into an agent optimizing different goals.
  rational: it either (1) doesn’t always choose the optimal ac-          Everitt et al. (2016) examine this question formally and
  tion, (2) is not perfectly aligned with human values, (3) has       arrive at the same conclusion: that the agent preserves its
  an inaccurate model of the environment, or (4) uses the wrong       goals in time (as long as the agent’s planning algorithm an-
  temporal discounting factor. We show that while in the cases        ticipates the consequences of self-modifications and uses the
  (2)-(4) the misalignment caused by the agent’s imperfection         current utility function to evaluate different futures).3 How-
  does not increase over time, with (1) the misalignment may
  grow exponentially.
                                                                      ever, Everitt’s analysis assumes that the agent is a perfect
                                                                      utility maximizer (i.e. it always takes the action with the
                                                                      greatest expected utility), and has perfect knowledge of the
                      1    Introduction                               environment. These assumptions are probably unattainable
We face the prospect of creating superhuman (or otherwise             in any complex environment.
very powerful) AI systems in the future where those sys-                 To address this, we present a theoretical analysis of a self-
tems hold significant power in the real world (Bostrom 2014;          modifying agent with imperfect optimization ability and in-
Russell 2019). Building up theoretical foundations for the            complete knowledge. We model the agent in the standard
study and design of such systems gives us a better chance to
                                                                         1
align them with our long-term interests. In this line of work,              Other major models include e.g. comprehensive systems of
we study agent-like systems, i.e. systems optimizing their            services (Drexler 2019) and ”Oracle AI” or ”Tool AI” (Arm-
actions to maximize a certain utility function – the frame-           strong, Sandberg, and Bostrom 2012). However, there are con-
                                                                      cerns and ongoing research into the emergence of agency in these
work behind the current state-of-the-art reinforcement learn-
                                                                      systems (Omohundro 2008; Miller, Yampolskiy, and Häggström
   * Supported by Grant Number 16582, Basic Algorithms Re-            2020).
                                                                          2
search Copenhagen (BARC), from the VILLUM Foundation.                       Proposals to prevent this include e.g. boxing (Bostrom 2014)
   †                                                                  but as e.g. Yampolskiy (2012) argues, this may be difficult or im-
     This author was supported by the Bakala Foundation Scholar-
ship                                                                  practical.
                                                                          3
Copyright © 2021, for this paper by its authors. Use permitted un-          Everitt et al. (2016)’s results hold independent of the length of
der Creative Commons License Attribution 4.0 International (CC        the time horizon or temporal discounting (by simple utility scal-
BY 4.0).                                                              ing).
cybernetic model where the agent can be bounded-rational          not self-modify. We show upper and tight lower bounds (by
in two different ways. Either the agent makes suboptimal          a constant) on the worst-case value loss in Theorem 7. As
decisions (is a bounded-optimization agent) or has inaccu-        we decrease γ (increase discounting), the rate at which the
rate knowledge. We conclude that imperfect optimization           agent’s performance deteriorates increases and the possibil-
can lead to exponential deterioration of alignment through        ity of self-modification becomes a more serious problem.
self-modification, as opposed to bounded knowledge, which            Our analysis of bounded-optimization agents is a general-
does not result in future misalignment. An informal sum-          ization of Theorem 16 from Everitt et al. (2016) in the sense
mary of the results is presented below.                           that their result can be easily recovered by a basic measure-
   Finally, we explicitly list and discuss the underlying as-     theoretic argument.
sumptions that motivate the theoretical problem and anal-         Self-modifying u -misaligned, ρ -ignorant, or γ -impatient
ysis. In addition to clearly specifying the scope of conclu-      perfect optimizers can only lose the same value as non-self-
sions, the explicit problem assumptions can be used as a          modifying agents with the same irrationality bounds. This
rough axis to map the space of viable research questions in       also holds for any combination of the three types of bounded
the area; see Sections 2 and 6.                                   knowledge. We give tight upper and lower bounds (up to a
                                                                  constant factor) for the worst-case performance. See Sec-
1.1   Summary of our results                                      tion 5.2 for details.
The result of Everitt et al. (2016) could be loosely inter-          This implies that unlike bounded-optimization agents, the
preted to imply that agents with close to perfect rationality     performance of perfect-optimization bounded-knowledge
would either prefer not to self-modify, or would self-modify      agents does not deteriorate in time. This is because bounded-
and only lose a negligible target value.                          knowledge agents continue to take optimal actions with re-
   We show that when we relax the assumption of perfect ra-       spect to their almost correct knowledge and do not self-
tionality, their result no longer applies. The bounded-rational   modify in a way that would worsen their performance in
agent may prefer to self-modify given the option and in do-       their view. Therefore, the possibility of self-modification
ing so, become less aligned and lose a significant part of the    seems less dangerous in the case of bounded-knowledge
attainable value according to its original goals.                 agents than in the case of bounded-optimization agents.
   We use the difference between the attainable and attained      A self-modifying agent with any combination of the four ir-
expected future value at an (arbitrarily chosen) future time      rationality types may lose value exponential in the time step
point as a proxy for the degree of the agent’s misalignment       t when the agent optimization error parameter o > 0. We
at that time. Specifically, for a future time t, we consider      again give tight (up to a constant factor) lower bounds on the
the value attainable from time t (after the agent already ran     worst-case performance of such agents. See Section 5.3 for
and self-modified for t time units), and we estimate the loss     details.
of value f t relative to the non-modified agent in the same
                                                                     Our results do not imply that every such agent will ac-
environment state. Note that f t is not pre-discounted by the
                                                                  tually perform this poorly but the prospect of exponential
previous t steps. See Section 3 for formal definitions and
                                                                  deterioration is worrying in the long-term, even if it happens
Section 2 for motivation and discussion.
                                                                  at a much slower speed than suggested by our results. We fo-
   We consider four types of deviation from perfect rational-     cus on worst-case analysis because it tells us whether we can
ity, see Section 4 for formal definitions.                        have formal guarantees of the agent’s behaviour – a highly
• -optimizers make suboptimal decisions.                         desirable property for powerful real-world autonomous sys-
                                                                  tems, including a prospective AGI (artificial general intelli-
• -misaligned agents have inaccurate knowledge of the hu-        gence) or otherwise strong AIs.
  man utility function.
                                                                  Overview of formal results. Here we summarize how much
• -ignorant agents have inaccurate knowledge of the envi-
                                                                  value the different types of bounded-rational agents may
  ronment.
                                                                  lose via misalignment. Note that the maximal attainable dis-
• -impatient agents have inaccurate knowledge of the cor-                                     1
                                                                  counted value is at most 1−γ     and the losses should be con-
  rect temporal discount function.                                sidered relative to that, or to the maximum attainable value
   Note that for the sake of simplicity, we use a very simple     in concrete scenarios. Otherwise, the values for different
model of bounded rationality where the errors are simply          value of γ are incomparable. In all cases, the worst-case
bounded by the error parameters • ; this has to be taken into    lower and upper bounds are tight up to a constant.
account when interpreting the results. However, we suspect        -optimizer agents – bounded optimization, after t steps of
that the asymptotic dependence of value loss on the size of       possible self-modification (Theorem 7)
errors and time would be similar for a range of natural, real-
istic models of bounded rationality.                                             t                       1
                                                                                fopt (, γ) = min( t−1 ,     )
                                                                                                  γ      1−γ
Informal result statements
Self-modifying -optimizers may deteriorate in future align-      -misaligned agents – inaccurate utility (Theorem 9)
ment and performance exponentially over time, losing ex-                                                 2
ponential amount of utility compared to -optimizers that do                           futil (, γ) =
                                                                                                        1−γ
  -ignorant agents – inaccurate belief (Theorem 11)                       goals, knowledge or behaviour. The problem of robust
                                                                           strong AI corrigibility is far from solved today and this
                                  2         2
                 fbel (, γ) =       −                                     paper can be read as a further argument for substantially
                                 1−γ   1 − γ(1 − )                        more research in this direction.
  -impatient agents – inaccurate discounting (Theorem 13)             (v) Worst-case analysis and bound tightness. We focus on
  Here γ ∗ is the correct discount factor and γ is the agent’s             worst-case performance guarantees in abstracted models
  incorrect discount factor.                                               rather than e.g. full distributional analysis, and we show
                                              1                            that our worst-case bounds are attainable (up to constant
                                         2γ ∗ lg γ − 1                     factors) under certain agent behaviour. Note this approach
                     fdisc (γ, γ ∗ ) ≈
                                           1 − γ∗                          may turn out as too pessimistic or even impossible in
                                                                           some settings (e.g. quantum physics).
             2      Assumptions and rationale
                                                                      (vi) Bounded value attainable per time unit. We assume the
  Both the statement of the problem and its relevance to AI
                                                                           agent obtains instantaneous utility between 0 and 1 at
  alignment rest on a set of assumptions listed below. While
                                                                           each time step. This is not an arbitrary choice: A constant
  this list is non-exhaustive, we try to cover the main implicit
                                                                           bound on instantaneous value can be normalized to this
  and explicit choices in our framing, and the space of alter-
                                                                           interval. Instantaneous values bounded by a function of
  natives. This is largely in hope of eventually finding a better,
                                                                           time U (t) < µt can be pre-discounted when γµ < 1, and
  more robust theoretical framework for solving agent self-
                                                                           generally lead to infinite future values otherwise, which
  modification within the context of AI alignment, but even
                                                                           we disallow here to avoid foundational problems.
  further negative results in the space would inform our intu-
  itions on what aspects of self-modification make the prob-         (vii) Temporal value discounting. We assume the agent em-
  lem harder.                                                              ploys some form of temporal value discounting. This
     We propose consideration of various assumptions as a                  could be motivated by technical or algorithmic limita-
  framework for thinking about prospective realistic agent                 tions, increasing uncertainty about the future, or to avoid
  models that admit formal guarantees. We invite further re-               issues with incomparable infinite values of considered
  search and generalizations in this area, one high-level goal             futures (see Bostrom (2011) for a discussion of infinite
  being to map a part of the space of agent models and as-                 ethics). Discounting, however, contrasts with the long-
  sumptions that do or do not permit guarantees, eventually                termist view; see the discussion below.
  finding agent models that do come with meaningful guaran-          (viii) Exponential discounting. Our model assumes the agent
  tees. Further negative results would inform our intuitions on             discounts future utility exponentially, a standard assump-
  what aspects of the problems make it harder.                              tion in artificial intelligence and the only time-invariant
  (i) Bounded rationality model. In the models of -bounded-                discounting schema (Strotz 1955) leading to consistent
      rational agents defined in Section 4.1,  is generally an             preferences over time.
      upper bound on the size of the optimization or knowledge        (ix) Unbounded temporal horizons. Our analysis focuses on
      error. One interpretation of our results is that value drift         the long-term behaviour of the agent, in particular stabil-
      can happen even if the error is bounded at every step. One           ity and performance from the perspective of future stake-
      could argue that a more realistic scenario would assume              holders (sharing the original utility function). Note that
      some distribution of the size of the errors, assuming larger         our results also to some extent apply to finite-horizon but
      errors less likely or less frequent; see discussion below            long-running systems.
      and in Section 6.                                                    Temporal discounting contrasts with the long-termist
 (ii) Unlimited self-modification ability. We assume the agent             view: Why not model non-discounted future utility di-
      is able to perform any self-modification at any time. This           rectly? Noting the motivations we mention in (vii), we
      models the worst-case scenario when compared to a lim-               agree that models of future value aggregation other than
      ited but still perfectly controlled self-modification. How-          discounting would be generally better suited for long-term
      ever, embedded (non-dualistic) agents in complex envi-               objectives. However, this seems to be a difficult task, as
      ronments may chieve almost-unlimited self-modification               such models are neither well developed nor currently used
      from a limited ability, e.g. over a longer time span; see            in open-ended AI algorithms (with the obvious exception
      e.g. (Demski and Garrabrant 2019). We model the agent’s              of a finite time horizon, which we propose to explore in
      self-modifications as orthogonal to actions in the environ-          Section 6).
      ment.                                                                We therefore propose a direct interpretation of our results:
(iii) Modification-independence. We assume that the agent’s                Assuming we implement agents that are -optimizers with
      utility function does not explicitly reward or punish self-          discounting, they may become exponentially less aligned
      modifications. We also assume that self-modifications do             over time. This is not the case with perfect optimizers with
      not have any direct effect on the environment. This is cap-          imperfect knowledge and discounting.
      tured by Definition 2.                                           (x) Dualistic setting. We assume a dualistic agent and allow
(iv) No corrigibility mechanisms. We do not consider systems               self-modification through special actions. This allows us
      that would allow human operators to correct the system’s             to formally model one aspect of embedded agency – at
  least until there are sufficient theoretical foundations of      a perception. A history is a sequence of action-perception
  embedded agency.                                                 pairs æ1 æ2 ...æt . We will often abbreviate such sequences to
  Note that in the embedded (non-dualistic) agent setting, it      æ<t = æ1 ...æt−1 or æn:m = æn ...æm . A complete history
  is not formally clear – or possibly even definable – what        æ1:∞ is a history containing information about all the time
  constitutes a self-modification, since there is no clear con-    steps.
  ceptual boundary between the agent and the environment,             An agent can be described by its policy π. The policy4
  as discussed by Demski and Garrabrant (2019).                    π : (A × E)∗ → A is used to determine the agent’s next
                                                                   action from the history at time t. We consider (bounded-
                                                                   rational) utility maximizers, where the policy is (partially)
Assumption categories and the problem space. Each as-              determined by the instantaneous utility function u, belief
sumption identifies a subspace of research questions we            ρ and discount factor γ. We sometimes use the notation
would obtain by varying the relevant choices. These sub-           κ = (u, ρ, γ), where κ is called the agent’s knowledge. The
spaces vary from very technical (e.g. concrete rationality         utility function ũ : (A × E)∞ → R describes how much the
model) to foundational (e.g. finite values and dualistic agent     agent prefers the complete history æ1:∞ compared to other
models). Along this axis, the assumptions and choices point        complete histories. We will assume that the total utility is a
to different kinds of prospective problems; we briefly de-         discounted sum of instantaneous utilities given by the instan-
scribe three such categories and their prospects. See Sec-         taneous utility              u : (A × E)∗ → [0, 1]. Formally,
tion 6 for concrete proposals of future work.                                     Pfunction
                                                                                     ∞      t−1
                                                                   ũ(æ1:∞ ) =       t=1  γ     u(æ ≤t ). The discount factor γ de-
Technical choices: A concrete model of bounded rational-           scribes how much the agent prefers immediate reward com-
ity, unlimited self-modification model, and modification-          pared to the same reward at a later time. Smaller γ means
independence. These are likely important for short and             heavier discounting of the future and stronger preference for
medium time-frames, where even eventually-diverging guar-          immediate reward. Note that the maximum achievable utility
                                                                        1
antees are useful.                                                 is 1−γ  , which happens when u(æt ) = 1 at each step. Also
   We believe that many models within some realistic and           note that instantaneous utility depends not only on the latest
sufficiently strong model classes would lead to qualitatively      perception but can also depend on all previous perceptions
equivalent results in long time horizons; e.g. the agent diver-    and actions.
gence would be asymptotically exponential without external            In addition to all this, an agent has a belief ρ : (A × E)∗ ×
corrigibility, embedded agents in sufficiently complex en-         A → ∆Ē where ∆Ē is the set of full-support probabil-
vironments would be able to self-modify arbitrarily over a         ity distributions over E. This is a function which maps any
long time (see discussion above) etc. However, these intu-         history ending with an action onto a probability distribu-
itions call for further verification.                              tion over the next perceptions. Intuitively speaking, the be-
                                                                   lief describes what the agent expects to see after it per-
Problem components: No corrigibility mechanisms, un-               forms an action given a certain history. A belief together
bounded time horizon, time-invariant temporal discounting,         with a policy induce a measure on the set (A × E)∗ using
focus on the worst-case guarantees. For those, there are in-       P (et | æ<t at ) = ρ(et | æ<t at ) and P (at | æ<t ) = 1
teresting alternatives that may yield more optimistic results.     if π(æ<t ) = at and 0 otherwise. Intuitively speaking, this
In particular, it would be valuable to explore formal models       probability measure captures probabilities assigned by the
of corrigibility, perform a full probabilistic analysis of agent   agent to possible futures.
development, and develop long-term non-discounted finite-             Following the reinforcement learning literature, we define
time settings.                                                     the value function V : (A × E)∗ → R as the expected future
Foundational assumptions: Dualistic agent model and fi-            discounted utility:
nite value of the future. Those are a standard in the area,                                        ∞
                                                                                                   X         0
but alternative settings may open up important and fruitful                        π
                                                                                 V (æ<t ) = E[             γ t −t u(æ<t0 ) ]
model classes and technical choices that capture currently                                         t0 =t
pre-paradigmatic aspects (e.g. theory of embedded agency
and non-dualistic agents).                                         The expectation value on the right is calculated with respect
                                                                   to belief ρ and assuming the agent will follow the policy π.
                                                                   Intuitively, the value function describes how promising the
                    3    Preliminaries                             future seems. When the value V π (æ<t ) of a history is high,
In this section, we explain our model of a self-modifying          it means we can expect an agent with policy π to collect a
agent, which is borrowed from Everitt et al. (2016). We will       lot of utility in the future starting from this history. Note that
extend this model to include bounded rationality in Sec-           when calculating V-values, instantaneous utilities are mul-
                                                                                   0                   0
tion 4.                                                            tiplied by γ t −t rather than γ t . This means that V-values
   We use a modified version of the standard cybernetic            can remain high throughout the whole history and are not
model. In this model, an agent interacts with the environ-         affected by discounting. We define the Q-value of an action
ment in discrete time steps. At each time step t, the agent        as the expected future discounted utility after taking that ac-
performs an action at from a finite set A and the environ-
ment responds with a perception et from a finite set E. An            4
                                                                        For a set S, S ∗ denotes the set of finite sequences of elements
action-perception pair æt is an action concatenated with           from S
tion:                                                                    Modification-independence assumption: In the rest of
                 π
              Q (æ<t at ) = E[u(æ1:t ) + V (æ1:t )]π                     the paper, we will assume that the agent’s belief and util-
                                                                         ity function as well as the correct belief are modification-
where the expectation is over the next perception drawn                  independent.
from the belief (note that belief is a probability distribution)
   The Q-value measures how good an action is given that                    4    Definitions of bounded-rational agents
the agent will later follow policy π. A policy π ∗ is an optimal
                  ∗
policy when V π (æ<t ) = supπ V π (æ<t ) for all histories               We now extend the model from Everitt et al. (2016) by defin-
æ<t (such a policy always exists, as shown in (Lattimore                 ing two types of bounded-rational agents which we will be
and Hutter 2014)).                                                       using throughout the paper: bounded-optimization agents
                                                                         (described in Section 4.1) and bounded-knowledge agents
                                                                         (described in Section 5.3). Bounded-knowledge agents can
3.1     Self-modification model
                                                                         be subdivided further into misaligned, ignorant and impa-
In this section, we extend the formalism above to include the            tient agents.
possibility of self-modification. Since we are interested in
the worst-case scenario, we assume the agent has unlimited               4.1    Bounded-optimization agents
self-modification ability. Worst-case results derived for such
an agent will also hold for agents with limited ability to self-         We introduce the notion of -optimizers. Intuitively speak-
modify.                                                                  ing, the expected future discounted utility gained by an -
                                                                         optimizer is no more than  lower than the optimal one in
Definition 1. A policy self-modification model is defined as             any situation they could get into (that is, for any history).
a quadruple (Ă, E, P, ι) where Ă is the set of world actions,          Definition 3. We say that agent A is an -optimizer for his-
E is the set of perceptions, P is a non-empty set of names               tory æ<t if it holds that
and ι is a map from P to the set of all policies Π.
   At every time step, the agent chooses an action at =                          Q(æ<t π(æ<t )) ≥ sup Q(æ<t π 0 (æ<t )) − 
                                                                                                      π0
(ăt , pt+1 ) from the set A = (Ă × P). The first part ăt de-
scribes what the agent “actually does in the world” while the               When the utility function, belief and discount factor is ob-
second part chooses the policy πt+1 = ι(pt+1 ) for the next              vious from the context (or unimportant), we also speak of
time step. We will also use the notation at = (ăt , πt+1 ),             policy being -optimizing (with respect to the utility func-
keeping in mind that only policies with names may be cho-                tion and belief), meaning that the corresponding agent is an
sen. This new policy is used in the next step to pick the ac-            -optimizer.
tion at+1 = πt+1 (æ1:t ). Note that only policies with names
can be chosen and that P = Π is not a possibility because it             4.2    Bounded-knowledge agents
                                                          ∗
entails a contradiction: |Π| = |(Ă × E × Π)||(Ă×E×Π) | >               We consider agents with inaccurate knowledge of the correct
2|Π| > |Π|. A history can now be written as:                             utility function (Definition 4), inaccurate knowledge of the
                                                                         world (Definitions 5 and 6), and inaccurate knowledge of
      æ1:t = a1 e1 a2 e2 ...at et = ă1 π2 e1 ă2 π3 e2 ...ăt πt+1 et   the correct discount factor (how much future reward is worth
The subscripts for policies are one time step ahead because              compared to reward in the present).
the policy chosen at time t is used to pick an action at time
t + 1. The subscript denotes at which time step the policy is            Misaligned agents We define -misaligned agents as
used. Policy πt is used to choose the action at = (a˘t , πt+1 ).         agents whose utility function u has absolute error  with re-
No policy modification happens when at = (a˘t , πt ).                    spect to the correct utility function u∗ .
   In the previous section, we used these rules to calculate
the probability of any finite history: P (et | æ<t at ) = ρ(et |         Definition 4. We say that the instantaneous utility function
æ<t at ) and P (at | æ<t ) = 1 if π(æ<t ) = at and 0 oth-                u has absolute error  with respect to the correct utility func-
erwise. However, the second rule doesn’t take into consid-               tion u∗ if
eration that the agent’s policy is changing. Therefore, to ac-
                                                                                         sup |u(æ<t ) − u∗ (æ<t )| = 
count for self modification, we need to modify the second                              t∈N,æ<t
rule into “P (at | æ<t ) = 1 if πt (æ<t ) = at and zero other-
wise”. To evaluate the V and Q-functions for self-modifying
agents, we need to use probabilities of complete histories               Ignorant agents We define -ignorant agents as agents
calculated in this way.                                                  whose belief ρ has error (absolute or relative depending on
                                                                         the context)  with respect to the correct belief ρ∗ .
Definition 2. Let æ̆1:t denote the history æ1:t with infor-                 For belief, we define both relative and absolute error. This
mation about self-modification removed so that æ̆1:t =                   is in contrast with utility, for which this does not make sense
ă1 e1 ă2 e2 ...ăt et . A function f : (A × E)∗ → (anything)           in our setting. This is because when one speaks of relative
                                                  0
is modification-independent if æ̆1:t = æ̆1:t implies that                utility, one usually compares it to some default action of “do-
                      0
f (æ1:t ) = f (æ1:t ).                                                   ing nothing” which we do not have.
                                               Bounded-rational agents




                 Bounded-optimization agents                        Bounded-knowledge agents
                  (make suboptimal decisions)


                                                  Misaligned agents            Ignorant agents         Impatient agents
                                               (inaccurate utility function)   (inaccurate belief)   (inaccurate discount rate)



Definition 5. We say that a belief ρ has absolute error  with           Theorem 7. Let ρ and u be modification-independent. Con-
respect to the correct belief ρ∗ if for any t ∈ N, history æ<t           sider a self-modifying agent which is an -optimizer for the
and action a,                                                            empty history. Then, for every t ≥ 1,
               kρ(æ<t a) − ρ∗ (æ<t a)kT V ≤                (?)
                                                                               Eæ<t [Q (æ<t πt (æ<t ))] ≥Eæ<t [Q (æ<t π1 (æ<t ))]
where k • kT V is the total variational distance.
                                                                                                                         1
   Recall that (on discrete measure spaces where all subsets                                             − min( t−1 ,        ) (1)
are measurable) for two distributions (formally two proba-                                                       γ     1−γ
bility measures) µ, ν on E, the total variational distance is            where the expectation is with respect to æ<t such that the
defined as                                                               perceptions are distributed according to the belief and the
             kµ − νkT V = sup |µ(E) − ν(E)|                              actions are given by ai = πi (æ<i ).
                             E⊆E                                            Moreover, for all histories æ<t given by ai = πi (æ<i )
Definition 6. We say a belief ρ has relative error  with re-            for which the agent is an -optimizer it holds that
spect to the correct belief ρ∗ if for any t ∈ N, any history
æ<t , action a, and percept e,                                                     Q (æ<t π1 (æ<t )) +  ≥ Q (æ<t πt (æ<t ))        (2)
                  1       ρ(e|æ<t a)
                      ≤ ∗              ≤1+
                1+      ρ (e|æ<t a)                                     Equality in Inequality (1) can be achieved up to a factor of
                                                                         at most γ.
Impatient agents We define impatient agents as agents
whose discount factor γ is smaller than the correct discount                The expectation in inequality (1) is necessary as can be
factor γ ∗ . This means they have a stronger preference for              demonstrated by the following example. Consider an envi-
immediate reward compared to the same reward in the fu-                  ronment in which the first perception is α with probability
ture.                                                                    (1 − γ) and β otherwise. Regardless of the first perception,
                                                                         the utility in the future is always 1 if the action following
             5   Exposition of the results                               this perception is a and 0 if b. An -optimizing agent which
                                                                         performs action a may choose to self-modify to an agent
We now formally describe our results, including statements
                                                                         which performs action a after perception α and b after per-
of the theorems. Proofs and description of the techniques                                          γ
                                                                         ception β, thus losing 1−γ    utility in the case of perception
used to prove these results are included in the full version of
this paper.                                                              β, regardless of how small  is.
                                                                         Setting  = 0 allows us to easily recover Theorem 16 from
5.1   Performance of -optimizers can deteriorate                        (Everitt et al. 2016), showing that self-modifications do not
In their paper, Everitt et al. (2016) show that, for                     impact expected discounted utility gained by perfectly ratio-
modification-independent belief and utility function, if we              nal agents. This proof is also considerably simpler than the
start with a perfect expected utility maximizer and at any               one in the original paper.
time replace the current policy by the initial policy, the ex-              If we only care about future discounted utility, this de-
pected discounted utility stays the same. Therefore, later               terioration in performance doesn’t need to concern us be-
policies cannot be worse than the initial policy and no dete-            cause it only happens at future times when utility is heavily
rioration happens. We show that in the case of -optimizers,             discounted. From the definition of an -optimizer, the max-
such a replacement can never decrease the expected dis-                  imum utility lost is indeed only . On the other hand, if we
counted utility by more than  (Inequality (2)) but can in-              care about long-term performance of the agent and have only
crease it more, meaning that agent’s behaviour can deterio-              introduced the discount factor for instrumental reasons (as
rate with time (Inequality (1)). Specifically, it can deterio-           would likely be the case), the possibility of self-modification
rate at an exponential rate, until its actions become arbitrar-          becomes a serious problem. The discount factor might be in-
ily bad – that is, until the expected future utility lost is the         troduced because optimizing the long-term future might be
                                            1
maximum achievable utility (which is 1−γ      ).                         computationally intractable.
5.2   Bounded-knowledge agents are -optimizers                     Theorem 11. Let A be a perfect expected utility maximizer
In this section, we discuss perfect utility maximizers with         whose belief ρ has absolute error  with respect to the cor-
bounded knowledge and show performance guarantees for               rect belief ρ∗ . Then it is a ( 1−γ2          2
                                                                                                          − 1−γ(1−)   )-optimizer with
                                                                                   ∗
such agents. In Section 5.3, we combine these results, show         respect to ρ and this bound is tight up to a factor of 2.
how to relax the assumption of perfect optimization and,            Moreover, if  is the relative error, this bound is tight up to a
most importantly, show how the performance of a bounded-            factor of 4.
rational agent differs between the cases with and without              So far, we have considered the worst-case scenario. In
self-modification.                                                  the next theorem, we show that in the case of both absolute
   In Lemma 8, we show that if the agent’s estimate of the          and relative error, the upper bound is tight up to a constant
expected discounted utility is at most  away from the true         factor even in the case when the error at each timestep is
value, the agent will be a 2-optimizer. In sections 5.2 to 5.2,    randomly chosen from the set {−, } (that is, ρ(et |æ<t at )
we show bounds on how inaccurate the agent’s estimate of            is chosen uniformly from the set {max(0, ρ∗ (et |æ<t at ) −
expected discounted utility can be, thus proving bounds on          ), min(1, ρ∗ (et |æ<t at ) + )} in the case of absolute error
                                                                            ∗
optimization. In Section 5.2, we proceed differently: we for-                    |æ<t at )
                                                                    and { ρ (et1+         , min(1, (1 + )ρ∗ (et |æ<t at ))} in the case
mulate the worst case as a solution of an optimization prob-        of relative error), independently of other timesteps.
lem which we then solve analytically.
                                                                    Theorem 12. Let A be a perfect expected utility max-
Lemma 8. Let A be a (possibly self-modifying) perfect ex-           imizer whose belief ρ is such that for any et , æ<t at ,
pected utility maximizer with knowledge κ = (u, ρ, γ). Let          the value ρ(et |æ<t at ) is independently for any argument
κ∗ = (u∗ , ρ∗ , γ ∗ ) be the correct knowledge. Assume that         chosen uniformly from the set {max(0, ρ∗ (et |æ<t at ) −
                 |Vκπ (æ<t ) − Vκπ∗ (æ<t )| ≤                      ), min(1, ρ∗ (et |æ<t at ) + )} in the case of absolute error
                                                                             ∗
                                                                                 |æ<t at )
                                                                    and { ρ (et1+         , min(1, (1 + )ρ∗ (et |æ<t at ))} in the case
for all policies π and histories æ<t . Then, A is a 2-optimizer    of relative error.
with respect to κ∗ .                                                   Then, in expectation, the amount of expected discounted
-misaligned agents are 0 -optimizers We now consider              utility lost is respectively
agents with an inaccurate utility function and derive bounds                                  1             1
                                                                                                 −
on 0 such that the misaligned agent is an 0 -optimizer.                                  1−γ       1 − γ(1 − /8)
Theorem 9. Let A be a perfect utility maximizer with util-                                   1              1
                                                                                                 −
ity function u and error  with respect to the correct utility                            1−γ       1 − γ(1 − /16)
function u∗ . Then it is a 1−γ
                            2
                               -optimizer with respect to u∗ .         and this is equal to the upper bound for non-random error
Moreover, this bound is tight.                                      up to a factor of 16 and 32, respectively.
   In the random-error case when for any æ<t , we ran-              Impatient agents are -optimizers In this section, we dis-
domly choose u(æ<t ) from the set {max(0, u∗ (æ<t ) −               cuss the case when an agent has an incorrect discount factor
), min(1, u∗ (æ<t )+)}, we give a simple lower bound that         and give a bound on the performance of this agent with re-
is only a factor 4 away from the upper bound. Consider an           spect to the correct discount factor. We only consider the
environment with only one perception 1 and actions {0, 1}           case when the agent discounts faster than the correct dis-
and u∗ (1|æ<t 0) = 1 − 2 and u∗ (1|æ<t 1) = 1. With prob-          count rate – we deem this to be the interesting case as, gen-
ability 1/4, it holds that u(1|æ<t 1) = u(1|æ<t 0), in which        erally speaking, while optimizing in the long-term might be
case the agent may take the suboptimal action 0, thus losing        desirable, it is difficult to achieve, so the agent is likely to
2 in instantaneous utility. At every step, it therefore loses      optimize in shorter term than desired. Bounds for the other
/2 instantaneous expected utility. In total, it then loses in      case can be derived by the same method. To simplify the
                 
expectation 2(1−γ)  . We have thus proved the following:            bounds, we define k = d− lg1γ e.
Theorem 10. Let A be a perfect utility maximizer whose              Theorem 13. Let πγ and πγ ∗ be perfect expected utility
utility function u is such that for any et , æ<t at , the value     maximizers with respect to discount factors γ and γ ∗ respec-
u(et |æ<t at ) is chosen independently and uniformly from the       tively for some γ ≤ γ ∗ , either with or without the ability to
set {max(0, u∗ (et |æ<t at ) − ), min(1, u∗ (et |æ<t at ) + )}.   self-modify. Let u,ρ be their utility function and belief. Then
Then, the amount of utility lost is in expectation                                                      γ ∗ k + γ ∗ k−1 − 1
                                                                      |V πγ ∗ (æ<t ) − V πγ (æ<t )| ≤
                                                                                                              1 − γ∗
                            2(1 − γ)                                                                                γ k + γ k−1 − 1
                                                                                                        − γ ∗ k−1 k−1
-ignorant agents are 0 -optimizers In this section, we                                                             γ     (1 − γ)
discuss agents with inaccurate belief. Theorem 11 gives             For γ → 1, it holds that d− lg1γ e ∼ − lg1γ . This enables us to
bounds on the utility lost as a result of the agent having an
inaccurate belief. We give an upper bound in terms of the           simplify the previous result to get a good approximation for
(weaker) absolute error and lower bounds in terms of both           when γ is close to 1:
                                                                                                                                1
absolute and relative error, showing that the upper bound is        γ ∗ k + γ ∗ k−1 − 1            k
                                                                                            ∗ k−1 γ + γ
                                                                                                          k−1
                                                                                                              −1   2γ ∗ lg γ − 1
tight up to factors of 2 and 4 for absolute and relative error.                         − γ                      ≈
                                                                          1 − γ∗                   γ k−1 (1 − γ)     1 − γ∗
 5.3     Combining the results                                            Therefore it may be interesting to explore bounded ratio-
 In this section we combine the results from sections 5.1                 nality models where the information about own bounded
 and 5.2 and present a bound on the utility lost by an agent              rationality could be explicitly reasoned about (with more
 which is misaligned, ignorant, impatient and has bounded                 precision than e.g. modelling the trajectory of the full en-
 optimization, all at the same time. It is an interesting feature         vironment). Would the agent then be more reluctant to self-
 of this bound that the worst-case performance guarantee can              modify?
 in some cases be improved by adjusting its discount rate.                Time horizons and discounting. Avoiding temporal dis-
    Recall that the functions f• in the following theorem have            counting would likely yield results with stronger impli-
 been defined in Section 1.1.                                             cations (Section 2). We propose analysing the finite-time
                                                                          undiscounted case, as well as exploring other means of fu-
 Theorem 14. Let A be an o -optimizer for the empty history
                                                                          ture value aggregation (finite or infinite, as explored by
 with either (1) the ability to self-modify and modification-
                                                                          Bostrom (2011)).
 independent utility function and belief, or (2) without the
 ability to self-modify and with a possibly modification-                 Model of self-modification. As noted above, embedded
 dependent utility function and belief. Let γ be the agent’s              agents with a strong influence on the environment may
 discount rate, u the error in its utility function wrt. the cor-        self-modify by exploiting the environment. However, the
 rect utility function u∗ and ρ its absolute error in belief with        extent of this self-modification, and the strength and sta-
 respect to the correct belief ρ∗ . Then at timestep t:                   bility of mechanisms against self-modification (e.g. via
                                                                          modification-dependent utility function) require further re-
(1) If we let 0 be the smallest possible number such that A              search.
    at time t is an 0 -optimizer, then Eæ<t [0 ] ≤ fopt (o , γ) +
    futil (u , γ) + fbel (ρ , γ) + fdisc (γ, γ ∗ ) where the expecta-   Probabilistic analysis. Build stochastic models of agent
    tion is over histories where perceptions are distributed ac-          rationality and self-modification, and perform full proba-
    cording to ρ∗ and actions are given by the agent’s policy.            bilistic analysis. This may e.g. inform us about required
    Moreover, if o = 0, then 0 ≤ fopt (o , γ) + futil (u , γ) +       safety margins. In particular, approaches based on statisti-
    fbel (ρ , γ) + fdisc (γ, γ ∗ ) almost certainly.                     cal physics and information theory seems to be promising
                                                                          here and have already proven fruitful in analyzing existing
(2) A will be an 0 -optimizer, with respect to the correct dis-
                                                                          optimization problems and algorithms.
    count rate γ ∗ , where 0 ≤ o + futil (u , γ) + fbel (ρ , γ) +
    fdisc (γ, γ ∗ )
                                                                                         7    Acknowledgements
    Moreover, when γ ≥ 1/2, there exists an agent which
 achieves equality up to a factor of at most 8 and up to a                This work was carried out as part of the AI Safety Research
 factor of 16 if ρ is the relative error.                                Program 2019. We are grateful to Vojtěch Kovařı́k, Jan Kul-
                                                                          veit, and Gavin Leech (in alphabetical order) for their valu-
                                                                          able inputs.
                        6    Future work                                     Copyright © 2020 for this paper by its authors. Use per-
 We propose several directions for future research. In general,           mitted under Creative Commons License Attribution 4.0 In-
 it would be interesting to explore the central problem of self-          ternational (CC BY 4.0).
 modification safety under different agent and environment
 models and with different assumptions.                                                          References
 Bounded rationality models. We analyzed a model of                       Armstrong, S.; Sandberg, A.; and Bostrom, N. 2012. Think-
 bounded-rationality with a strict upper bound on the size of             ing Inside the Box: Controlling and Using an Oracle AI.
 errors (of several kinds). While this shows that even agents             Minds and Machines 22. doi:10.1007/s11023-012-9282-2.
 guaranteed to have small errors may self-modify in detri-
 mental ways, the analysis would be significantly different               Bostrom, N. 2011. Infinite Ethics. Analysis and Metaphysics
 for fully stochastic bounded rationality models (e.g. negligi-           10: 9–59. URL www.nickbostrom.com/ethics/infinite.pdf.
 ble expected errors with non-negligible variance). One such              Bostrom, N. 2014. Superintelligence: Paths, Dangers,
 model of interest is Information-Theoretic Bounded Ratio-                Strategies. USA: Oxford University Press, Inc., 1st edition.
 nality of Ortega et al. (2015).                                          ISBN 0199678111.
 Awareness of own bounded-rationality. Whatever under-                    Demski, A.; and Garrabrant, S. 2019. Embedded Agency.
 lying decision procedure the agent uses somehow implic-                  CoRR abs/1902.09469.     URL http://arxiv.org/abs/1902.
 itly takes its -optimality into account – in particular since           09469.
 the assumed -optimality depends on the behavior of future
 agent versions. In our formulation, we do not assume the                 Drexler, K. E. 2019. Reframing superintelligence: Compre-
 agent to have explicit knowledge of its bounded rationality              hensive AI services as general intelligence. Future of Hu-
 model and , which would at least intuitively seem useful to             manity Institute, University of Oxford .
 know.                                                                    Everitt, T.; Filan, D.; Daswani, M.; and Hutter, M. 2016.
    Note, however, that in our framing such explicit knowl-               Self-Modification of Policy and Utility Function in Ratio-
 edge would not be necessarily useful, as any deliberation                nal Agents. CoRR abs/1605.03142. URL http://arxiv.org/
 about it is subject to the same error within -optimality.               abs/1605.03142.
Lattimore, T.; and Hutter, M. 2014. General time consistent
discounting. Theoretical Computer Science 519: 140 – 154.
ISSN 0304-3975. doi:https://doi.org/10.1016/j.tcs.2013.09.
022. URL http://www.sciencedirect.com/science/article/pii/
S0304397513007135. Algorithmic Learning Theory.
Miller, J. D.; Yampolskiy, R.; and Häggström, O. 2020. An
AGI Modifying Its Utility Function in Violation of the Or-
thogonality Thesis. arXiv preprint arXiv:2003.00812 .
Omohundro, S. M. 2008. The basic AI drives. In AGI, vol-
ume 171, 483–492.
Ortega, P. A.; Braun, D. A.; Dyer, J.; Kim, K.-E.; and Tishby,
N. 2015. Information-Theoretic Bounded Rationality.
Russell, S. 2019. Human compatible: artificial intelligence
and the problem of control. New York, New York: Viking.
ISBN 9780525558613.
Strotz, R. H. 1955. Myopia and inconsistency in dynamic
utility maximization. The review of economic studies 23(3):
165–180.
Yampolskiy, R. 2012. Leakproofing the Singularity Arti-
ficial Intelligence Confinement Problem. Journal of Con-
sciousness Studies 19: 194–214.

</pre>