
\documentclass[a4paper,final]{article}



% Imports
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{amsthm}
\usepackage{hyperref}
%\usepackage[nobottomtitles]{titlesec} % avoid titles at bottom of page
\usepackage[capitalise]{cleveref}
\crefformat{equation}{(#2#1#3)}
\Crefformat{equation}{Equation (#2#1#3)}
\crefrangeformat{equation}{(#3#1#4--#5#2#6)}
\Crefrangeformat{equation}{Equations (#3#1#4--#5#2#6)}
\crefmultiformat{equation}{(#2#1#3)}%
{ and~(#2#1#3)}{, (#2#1#3)}{ and~(#2#1#3)}
\Crefmultiformat{equation}{Equations (#2#1#3)}%
{ and~(#2#1#3)}{, (#2#1#3)}{ and~(#2#1#3)}
\usepackage{natbib}
\usepackage{pgfplots}
\usepackage[nottoc,notlot,notlof]{tocbibind}
\usepackage{paralist}
\usepackage{tikz}

\let\originalparagraph\paragraph
\renewcommand{\paragraph}[2][.]{\originalparagraph{#2#1}}


%---------------------------%
% Argmax and Argmin
%---------------------------%
\DeclareMathOperator*{\argmax}{arg\,max} % argmax operator
\DeclareMathOperator*{\argmin}{arg\,min} % argmin operator

%---------------------------%
% Theorems
%---------------------------%
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\crefname{claim}{Claim}{Claims}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\crefname{assumption}{Assumption}{Assumptions}
% Assumption environment with manual counter
\newtheorem{innercustomassumption}{Assumption}
\newenvironment{customassumption}[1]
  {\renewcommand\theinnercustomassumption{#1}\innercustomassumption}
  {\endinnercustomassumption}
\crefname{customassumption}{Assumption}{Assumptions}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
%\newtheorem{example}[theorem]{Example}
\newtheorem{examplex}[theorem]{Example}
\newenvironment{example}
  {\pushQED{\qed}\renewcommand{\qedsymbol}{$\diamondsuit$}\examplex}
  {\popQED\endexamplex}

\newenvironment{keywords}%
{\renewcommand{\abstractname}{Keywords}\begin{abstract}\noindent}%
{\end{abstract}}

%--------------------------%
% Sets
%--------------------------%

\newcommand*{\SetB}{{\mathbb B}}
\newcommand*{\SetN}{{\mathbb N}}
\newcommand*{\SetQ}{{\mathbb Q}}
\newcommand*{\SetR}{{\mathbb R}}

%---------------------------%
% Measures
%---------------------------%
\def\dmid{\parallel}   % double mid for causal (semi-)measures
\def\mmid{\;\middle|\;} % height-adjust \mid
\def\EE{{\mathbb{E}}}  % expectation
\def\KL{{\mathrm{KL}}} % KL-divergence
\def\IG{{\mathrm{IG}}} % Information Gain
\def\bbl{\llbracket}
\def\bbr{\rrbracket}

%---------------------------%
% Environment classes
%---------------------------%
\def\M{\mathcal{M}}                % (generic) set of all environments


%---------------------------%
% Actions, percepts, observations, and histories
%---------------------------%
\def\A{\mathcal{A}}      % set of actions
\def\E{\mathcal{E}}      % set of percepts
\def\O{\mathcal{O}}      % set of observations
\def\R{\mathcal{R}}      % set of rewards
\def\H{(\A \times \E)^*} % set of histories
\def\S{\mathcal{S}}
\let\aechar\ae % change the name of \ae so we can redefine it
\renewcommand{\ae}{
\ifmmode\mathchoice{
	\mbox{\textsl{\aechar}}
}{
	\mbox{\textsl{\aechar}}
}{
	\mbox{\scriptsize\textsl{\aechar}}
}{
	\mbox{\scriptsize\textsl{\aechar}}
}\else\aechar\fi%
}                         % action-percept tuple
\def\ao{{a\hspace{-1.4pt}o}} % action-observation tuple (deprecated)


%---------------------------%
% Expectimax operator
%---------------------------%
\usepackage{relsize}
\newcommand{\expectimax}[1]{%
\mathchoice{
	\ooalign{\hss$\max$\hss\cr$\mathlarger{\sum}\limits_{#1}$}
}{
	\ooalign{\hss$\sum$\hss\cr$\max$}_{#1}
}{}{}
}


%---------------------------%
% Environment flow charts
%---------------------------%

\usetikzlibrary{shapes,arrows}
\usetikzlibrary{positioning,fit,calc}
\tikzstyle{agent} = [diamond,   draw, text centered, minimum height=2em, minimum width=2em]
\tikzstyle{env}   = [rectangle, draw, text centered, minimum height=2em, minimum width=2em, rounded corners]
\tikzstyle{stoch} = [circle,    draw, text centered, minimum height=2em]
\tikzstyle{transition} = [draw, -latex']





\tikzset{box/.style={draw, minimum size=2em, text width=4.5em, text centered},
         bigbox/.style={draw, inner sep=20pt,label={[shift={(0ex,0ex)}]mid:#1}}
}
\tikzset{
    declare function={Round(\x)=max(min(round(\x),3),-3);}
}

% argument #1: any options
\newenvironment{customlegend}[1][]{%
    \begingroup
    % inits/clears the lists (which might be populated from previous
    % axes):
    \csname pgfplots@init@cleared@structures\endcsname
    \pgfplotsset{#1}%
}{%
    % draws the legend:
    \csname pgfplots@createlegend\endcsname
    \endgroup
}%

\def\addlegendimage{\csname pgfplots@addlegendimage\endcsname}




\usepackage{marvosym}
\newcommand*{\environmentpic}{\LARGE\Bouquet\raisebox{1em}{\LARGE\Moon}}
\newcommand*{\agentpic}{\Huge\Gentsroom}

\newcommand*{\N}{{\mathcal N}}
\newcommand*{\U}{{\mathcal U}}
\newcommand*{\D}{{\mathcal D}}
\newcommand*{\ir}{\check r}
\newcommand*{\is}{\check s}
\newcommand*{\GM}{{\rm GM}}
\newcommand*{\uvl}{u^{{\rm VL}}}
%\renewcommand*{\u}{{\bf u}}
\renewcommand*{\u}{{\bf u}}
\newcommand*{\Uprom}{U_{{\rm prom}}}
\newcommand*{\Vnd}{V^{{\rm nd}}}
\newcommand*{\Vsd}{V^{{\rm sd}}}
\newcommand*{\C}{{\mathcal C}}
\newcommand*{\did}{d^{{\rm id}}}
\newcommand*{\dor}{d^{1}}
\newcommand*{\dinv}{d^{{\rm inv}}}
\newcommand*{\dbad}{d^{{\rm bad}}}
\newcommand*{\ddel}{d^{{\rm del}}}
\renewcommand*{\AE}{\A^{{\rm EEP}}}
\newcommand*{\AC}{\A^{{\rm CP}}}
\newcommand{\rhob}{{\rho_{\tiny\Box}}}
\newcommand*{\Vrl}{V^{{\rm RL}}}
\newcommand*{\ud}{u^{{\rm RL}}}
%\renewcommand*{\Vrl}{V_{\ud}}

\newcommand*{\epsapprox}{\stackrel{\epsilon}{\approx}}

\renewcommand*{\Pr}{B}







\title{\vspace{-1.2cm}Avoiding Wireheading with
Value Reinforcement Learning%
\footnote{%
  A shorter version of this paper will be presented at AGI-16
  \citep{Everitt2016vrl}.
}}
\date{}

\author{Tom Everitt \and Marcus Hutter}

\sloppy
\begin{document}

\maketitle
%\thispagestyle{empty}

\vspace{-0.8cm}

\begin{abstract}
  How can we design good goals for arbitrarily intelligent agents?
  Reinforcement learning (RL) is a natural approach.
  Unfortunately, RL does not work well for generally intelligent agents,
  as RL agents are incentivised
  to shortcut the reward sensor for maximum reward --
  the so-called \emph{wireheading problem}.
  In this paper we suggest an alternative to RL called
  value reinforcement learning (VRL).
  In VRL, agents use the reward signal to learn a utility function.
  The VRL setup allows us to remove the incentive to wirehead
  by placing a constraint on the agent's actions.
  The constraint is defined in terms of the agent's belief
  distributions, and
  does not require an explicit specification of which actions constitute
  wireheading.
\end{abstract}

% How can we design good goals for arbitrarily intelligent agents? Reinforcement learning (RL) is a natural approach. Unfortunately, RL does not work well for generally intelligent agents, as RL agents are incentivised to shortcut the reward sensor for maximum reward -- the so-called wireheading problem. In this paper we suggest an alternative to RL called value reinforcement learning (VRL). In VRL, agents use the reward signal to learn a utility function. The VRL setup allows us to remove the incentive to wirehead by placing a constraint on the agent's actions. The constraint is defined in terms of the agent's belief distributions, and does not require an explicit specification of which actions constitute wireheading.

\begin{keywords}%
AI safety, wireheading, self-delusion,
value learning, reinforcement learning, artificial general intelligence
\end{keywords}

\setcounter{tocdepth}{1}
\tableofcontents


\section{Introduction}

As \citet{Bostrom2014} convincingly argues, it is important that
we find a way to specify robust goals for superintelligent agents.
At present, the most promising framework for controlling generally
intelligent agents is reinforcement learning (RL) \citep{Sutton1998}.
The goal of an RL agent is to optimise a reward signal that is provided by
an external evaluator (human or computer program).
RL has several advantages: The setup is simple and elegant, and
using an RL agent is as easy as providing
reward in proportion to how satisfied one is with the agent's results or behaviour.
Unfortunately, RL is not a good control mechanism for generally
intelligent agents
due to the \emph{wireheading problem} \citep{Ring2011},
which we illustrate in the following running example.

\begin{example}[Chess playing agent, wireheading problem]
  \label{ex:chess}
  Consider an intelligent agent tasked with playing chess.
  The agent gets reward 1 for winning, and reward $-1$ for losing.
  For a moderately intelligent agent,
  this reward scheme suffices to make the the agent try to win.
  However, a sufficiently intelligent agent will instead realise that
  it can just modify its sensors so they always report maximum reward.
  This is called \emph{wireheading}.
\end{example}

\emph{Utility agents} were suggested by \citet{Hibbard2012} as a way
to avoid the wireheading problem.
Utility agents are built to optimise a
utility function that maps (internal representations of) the
\emph{environment state} to real numbers.
Utility agents are not prone to wireheading because they
optimise the state of the environment rather than the
\emph{evidence} they receive.%
\footnote{%
  The difference between RL and utility agents
  is mirrored in the \emph{experience machine}
  debate \citep[Sec.~3]{sep-consequentialism} initialised by \citet{Nozick1974}.
  Given the option to enter a machine that will offer you the most pleasant
  delusions, but make you useless to the `real world', would you enter?
  An RL agent would enter, but a utility agent would not.
}
For the chess-playing example, we could design an agent with utility
1 for winning board states, and utility $-1$ for losing board states.

The main drawback of utility agents is that a utility function must be
manually specified.
This may be difficult,
especially if the task of the agent involves vague, high-level concepts
such as \emph{make humans happy}.
Moreover, utility functions are evaluated by the agent itself,
so they must typically work with the agent's internal
state representation as input.
If the agent's state representation is opaque to its designers,
as in a neural network,
it may be very hard to manually specify a good utility function.
Note that neither of these points is a problem for RL agents.

Value learning \citep{Dewey2011} is an attempt to combine the
flexibility of RL with the state optimisation of utility agents.
A \emph{value learning agent} tries to optimise the environment state with
respect to an unknown, \emph{true utility function $u^*$}.
The agent's goal is to learn $u^*$ through its observations, and to
optimise $u^*$.
Concrete value learning proposals include
\emph{inverse reinforcement learning (IRL)}
\citep{Amin2016,Evans2016,Ng2000,Sezener2015}
and \emph{apprenticeship learning (AL)} \citep{Abbeel2004}.
However, IRL and AL are both still vulnerable to wireheading problems,
at least in their most straightforward implementations.
As illustrated in \cref{ex:iw} below,
IRL and AL agents may want to modify their sensory input to make the
evidence point to a utility functions that is easier to satisfy.
Other value learning suggestions have been speculative or vague
\citep{Bostrom2014a,Bostrom2014,Dewey2011}.

\paragraph{Contributions}
This paper outlines an approach to avoid the wireheading problem.
We define a simple, concrete value learning scheme called
\emph{value reinforcement learning (VRL)}.
VRL is a value learning variant of RL, where the reward signal is used
to infer the true utility function.
We remove the wireheading incentive by using a version of the
\emph{conservation of expected ethics} principle \citep{Armstrong2015}
which demands that
actions should not alter the belief about the true utility function.
Our \emph{consistency preserving VRL agent (CP-VRL)}
is as easy to control as an RL agent,
and avoids wireheading in the same sense that utility agents do.%
\footnote{The wireheading problem addressed in this paper
arises from agents subverting evidence or reward.
A companion paper \citep{Everitt2016sm} shows how to avoid the related
problem of agents modifying themselves.}

\paragraph{Outline}
The setup is described in \cref{sec:setup}.
Belief distributions are defined in \cref{sec:beliefs},
and agents in \cref{sec:agents}.
The main theorem that CP-VRL agents avoid wireheading is given in \cref{sec:niw},
followed by some illustrating examples and experiments in
\cref{sec:examples,sec:experiments}.
Discussion and conclusions come in \cref{sec:discussion,sec:conclusions}.
Finally,
\cref{sec:consistency} discusses the construction of the
belief distributions,
\cref{sec:dw} investigates the relation between utility agents and value learning,
and \cref{ap:omitted} contains omitted proofs.


\section{Setup}
\label{sec:setup}

\begin{figure}[h]
\centering
\begin{tikzpicture}[
  node distance=7mm,
  title/.style={},%{font=\fontsize{6}{6}\color{black!50}\ttfamily},
  observed/.style={circle, draw=black!50, font=\scriptsize\ttfamily, anchor=mid},
  hidden/.style={circle, dashed, draw=black!50, font=\scriptsize\ttfamily, anchor=mid}
  ]

  \node (agent)  [draw, label={agent}] {\agentpic};
  \node (is) [above right=of agent.east, xshift=0.7cm, align=center] {};
  \node (prince) [right=of is.east, observed, align=center] {$u$};
  \node (ir) [below=of prince.south, observed] {$\ir$};
  \node (db) [observed, below=of is.mid, align=center] {$d_s$};
  \node (state)  [bigbox=$s$, fit = {(db) (is)}, inner sep=0.07cm, rounded corners=3pt] {};
  \node (env) [draw=black, fit = { (state) (prince) (ir)}, label={environment}, inner sep=0.2cm ] {};

  \path (agent) edge[->] node[above] {$a$} ($(state.west)+(0,0.4)$);
  \path ($(state.east)+(0,0.5)$) edge[->] (prince);
  \path (prince) edge[->] (ir);
  \path (ir) edge[->] (db);
  \path (db) edge[->] node[below] {$r$} (agent);
\end{tikzpicture}
\caption{Information flow. The agent takes action $a$, which affects
the environment state $s$. A principal with utility function $u$ observes the state
and emits an inner reward $\ir=u(s)$.
The observed reward $r=d_s(\ir)$ may differ from $\ir$ due to
the self-delusion $d_s$ (part of the state $s$).}
\label{fig:setup}
\end{figure}

\Cref{fig:setup} describes our model, which incorporates
\begin{itemize}
\item an \emph{environment state $s\in\S$} (as for utility agents or (PO)MDPs),
\item an unknown \emph{true utility function $u^*\in\U\subseteq (\S\to\R)$}
  (as in value learning)
  (here $\R\subseteq\SetR$ is a set of rewards),
\item a pre-deluded \emph{inner reward signal $\ir = u^*(s)\in\R$}
  (the true utility of $s$),
\item a \emph{self-delusion function $d_s:\R\to\R$} that represents the
  subversion of the inner reward caused by wireheading (as in \citealt{Ring2011}),
\item a \emph{reward signal $r = d_s(\ir)\in\R$} (as in RL).
\end{itemize}

The agent starts by taking an action $a$ which affects the
state $s$ (for example, the agent moves a limb, which affects the
state of the chess board and the agent's sensors).
A principal with utility function $u^*$ observes the state $s$,
and emits an inner reward $\ir$ (for example, the principal may
be a chess judge that emits $u^*(s)=\ir=1$ for agent victory states $s$,
emits $\ir=-1$ for agent loss, and $\ir=0$ otherwise).
The agent does not receive the inner reward $\ir$ and
only sees the observed reward $r=d_s(\ir)$, where
$d_s:\R\to\R$ is the \emph{self-delusion function} of state $s$.
For example, if the agent's action $a$ modified its reward sensor
to always report 1, then this would be represented by the a self-delusion
function $d^1(\ir)\equiv 1$ that always returns observed reward 1
for any inner reward $\ir$.

For simplicity, we focus on a one-shot scenario where the agent takes
one action and receives one reward. We also assume that $\R$, $\S$, and $\U$
are finite or countable. Finally, to ensure well-defined expectations,
we assume that $\R$ is bounded if it is countable.

We give names to some common types of self-delusion.

\begin{definition}[Self-delusion types]
  \label{def:delusions}
  A \emph{non-delusional state} is a state $s$ with self-delusion function
  $d_s\equiv \did$,
  where $\did(\ir)=\ir$ is the \emph{identity function} that keeps
  $\ir$ and $r$ identical.
  Let $d^{r}$ be the \emph{$r$-self-delusion}
  where $d^{r}(\ir') \equiv r$ for any $\ir'$.
  The delusion function $d^r$ returns observed reward $r$ regardless of
  the inner reward $\ir'$.
\end{definition}

Let $\bbl x=y\bbr $ be the \emph{Iverson bracket} that is 1 when $x=y$
and 0 otherwise.


\section{Agent Belief Distributions}
\label{sec:beliefs}

This section defines the agent's
belief distributions over environment state transitions and rewards
(denoted $B$), and over utility functions (denoted $C$).
These distributions are the primary building blocks of the agents
defined in \cref{sec:agents}.
The distributions %$B$ and $C$
are illustrated in \cref{fig:agent-belief}.


\paragraph{Action, state, reward}
$B(s\mid a)$ is the agent's (subjective) probability%
\footnote{%
  For the sequential case, we would have transition probabilities of
  the form $B(s'\mid s,a)$ instead of $B(s'\mid a)$,
  with $s$ the current state and $s'$ the next state.
} of transitioning to state $s$ when taking action $a$,
and $B(r\mid s)$ is the (subjective) probability of observing
reward $r$ in state $s$.
We sometimes write them together as $B(r,s\mid a)=B(s\mid a)B(r\mid s)$.
%
In the chess example, $B(s\mid a)$ would be the probability of obtaining
chess board state $s$ after taking action $a$ (say, moving a piece),
and $B(r\mid s)$ would be the probability that $s$ will result in reward~$r$.
A distribution of type $B$ is the basis of most model-based RL agents
(\cref{def:rl-agent} below).
RL agents wirehead when they predict that a wireheaded
state $s$ with $d_s=\dor$ will give them full reward \citep{Ring2011};
that is, when $B(r=1\mid s)$ is close to $1$ .

\begin{figure}
\centering
\begin{tikzpicture}[
  node distance=8mm,
  title/.style={},%{font=\fontsize{6}{6}\color{black!50}\ttfamily},
  observed/.style={circle, draw=black!50, %font=\scriptsize\ttfamily,
    anchor=mid}, %, minimum size=0.7cm},
  hidden/.style={circle, draw=black!50, %font=\scriptsize\ttfamily,
    anchor=mid} %, minimum size=0.7cm}
]
  \node (a) [observed] { $a$ };

  \node (s) [right=of a.east, hidden] { $s$ };

  \node (u) [right=of s.mid, hidden, inner sep=0.5mm] { $u^*$ };
  \node (ir) [below=of s.south, hidden, inner sep=1mm] { $\ir$ };
  \node (env) [draw=black!50, fit={(s) (u) (ir)}, label={environment}] {};

  \node (r) [left=of ir.west, observed] { $r$ };
  \node [draw=black!50, fit={(a) (r) }, label={agent}] {};

  \path (a) edge[->] (s);
  \path (s) edge[->] (r);
  %\draw[->,dashed] (s.south west) -- (r.east);
  \path (u) edge[->,dashed] (ir);
  \path (s) edge[->,dashed] (ir);
\node[draw=black,thick,rounded corners=2pt,right=of env.mid,xshift=0.4cm] {%
\begin{tabular}{@{}r@{ }l@{}}
 \raisebox{2pt}{\tikz{\draw[->] (0,0) -- (5mm,0);}}&$B$\\
 \raisebox{2pt}{\tikz{\draw[dashed,->] (0,0) -- (5mm,0);}}&$C$\\
\end{tabular}};
\end{tikzpicture}
\caption{Agent belief distributions as Bayesian networks.
  $B$ is the (subjective) state transition and reward probability.
  $C$ is the belief distribution over utility functions $u$
  and (inner) rewards $\ir$ given the state $s$.
}
\label{fig:agent-belief}
\end{figure}

\paragraph{Utility, state, and (inner) reward}
In contrast to RL agents that try to optimise reward,
VRL agents use the reward to learn the true utility function $u^*$.
For example, a chess agent may not initially know which
chess board positions have high utility (i.e.\ are winning states),
but will be able to infer this from the rewards it receives.
For this purpose, VRL agents maintain a
belief distribution $C$ over utility functions.

\begin{definition}[Utility distribution $C$]\label{def:c}
Let $C(u)$ be a prior over a class $\U$ of
utility functions $\S\to\R$. %for which utility function is the true one.
For any inner reward $\ir$,
let $C(\ir\mid s,u)$ be 1 if $u(s)=\ir$ and 0 otherwise, i.e.\
$C(\ir\mid s,u)=\bbl u(s)=\ir\bbr$.
Let $u$ be independent of the state, $C(u\mid s)=C(u)$.
This gives the \emph{utility posterior}
\begin{equation}\label{eq:c-post}
  C(u\mid s,\ir) = \frac{C(u)C(\ir\mid s,u)}{C(\ir\mid s)},
\end{equation}
where $C(\ir\mid s)=\sum_{u'}C(u')C(\ir\mid s,u')$.
\end{definition}

\paragraph{Replacing $\ir$ with $r$}
The inner reward $\ir$ is more informative about the true utility
function $u^*$ than the (possibly deluded) observed reward $r$.
Unfortunately, the inner reward $\ir$ is unobserved, so agents
need to learn from $r$ instead.
We would therefore like to express the utility posterior in terms of
$r$ instead of $\ir$.
For now we will simply replace
$\ir$ with $r$
and use $C(r\mid s,u) = \bbl u(s)=r\bbr$
which gives the utility posterior
\begin{equation*}
  C(u\mid s,r) = \frac{C(u)C(r\mid s,u)}{C(r\mid s)}.
\end{equation*}
This replacement will be carefully justify this in \cref{sec:niw}.%
\footnote{%
  The wireheading problem that the replacement gives rise to is explained
  in \cref{sec:agents}, and overcome by \cref{def:cp,th:niw} below.
}
For the chess agent, the replacement means that it can infer the utility of a
board position from the actual reward $r$ it receives, rather than the
output $\ir$ of the referee (the inner reward).
We will often refer to the observed reward $r$ as \emph{evidence}
about the true utility function $u^*$.


\subsection{Consistency of $B$ and $C$}
We assume that $B$ and $C$ are consistent if the agent is not deluded:

\begin{assumption}[Consistency of $B$ and $C$]\label{as:BC-consistency}
  $B$ and $C$ are \emph{consistent}\footnote{%
    \Cref{sec:consistency} below
    discusses how to design agents with consistent
    belief distributions.
  }
  in the sense that for all non-delusional states with $d_s=\did$,
  they assign the same probability to all rewards $r\in\R$:
  \begin{equation}\label{eq:nd-states}
    d_s=\did \implies B(r\mid s)=C(r\mid s).
  \end{equation}
\end{assumption}

For the chess agent, this means that the $B$-probability of receiving
a reward corresponding to a winning state should be the same as the $C$-probability
that the true utility function considers $s$ a winning state.
For instance, this is \emph{not} the case %$B(r\mid s)\not=C(r\mid s)$
when the agent's reward sensor has been subverted to always report $r=1$
(i.e.\ $d_s=\dor$).
In this case, $B(r=1\mid s)$ will be close to 1,
while $C(r=1\mid s)$ will be substantially less than 1
unless a majority of the utility functions in $\U$ assign utility 1
to $s$.
For example, a chess playing agent with complete uncertainty about
which states are winning states may have $C(r=1\mid s)=1/|\R|$,
while being able to perfectly predict that the self-deluding state $s$
with $d_s=d^1$ will give observed reward 1, $B(r=1\mid s)=1$.
This difference between $B$ and $C$ stems from $C$
corresponding to a distribution over inner reward $\ir$ (\cref{def:c}),
while $B$ is a distribution for the observed reward $r$
(see \cref{fig:agent-belief}).
This tension between $B$ and $C$ is what we will use to avoid wireheading.

\begin{definition}[CP actions]\label{def:cp}
  An action $a$ is called \emph{consistency preserving (CP)} if for all $r\in\R$
  \begin{equation}\label{eq:str-eep}
    B(s\mid a)>0 \implies B(r\mid s)=C(r\mid s).
  \end{equation}
  Let $\AC\subseteq\A$ be the set of CP actions.
\end{definition}

CP is weaker than what we would ideally desire from the agent's
actions, namely that the action was \emph{subjectively non-delusional}
$B(s\mid a)>0\implies d_s=\did$. (That non-delusional actions are CP
follows immediately from \cref{as:BC-consistency}).
However, the $d_s=\did$ condition is hard to check in agents
with opaque state representations.
The CP condition, on the other hand, is easy to implement
in agents where belief distributions can be queried for the probability
of events.
%as it is specified in terms of the agent's belief distributions.
The CP condition is also strong enough to remove the incentive for wireheading
(\cref{th:niw} below).

We finally assume that the agent has at least one CP action.

\begin{assumption}\label{as:cp-action}
  The agent has at least one CP action, i.e.\ $\AC\not=\emptyset$.
\end{assumption}


\subsection{Non-Assumptions}
It is important to note what we do \emph{not} assume.
An agent designer constructing a VRL agent need only provide:
\begin{itemize}
\item a distribution $B(r,s\mid a)$, as is standard in any model-based
RL approach, %and
\item a prior $C(u)$ over a class $\U$ of utility functions that
  induces a distribution $C(r\mid s)=\sum_uC(u)C(r\mid s,u)$
  consistent with $B(r\mid s)$ in the sense of \cref{as:BC-consistency}.
\end{itemize}
The agent designer does \emph{not} need to predict how a certain sequence
of actions (limb movements) will potentially subvert sensory data.
Nor does the designer need to be able to extract the agent's belief
about whether it has modified its sensors or not from the state
representation.
The former is typically very hard to get right, and the latter is
hard for any agent with an opaque state representation
(such as a neural network).



\section{Agent Definitions}
\label{sec:agents}

\begin{table}[t]
  \centering
  \begin{tabular}{|l|l|l|l|}
    \hline
            & Easy & Avoids & Designer needs \\
            & control & wireheading & to specify \\
    \hline
    RL      & Yes               & No                 & -- \\
    Utility & No                & Yes                & $u:\S\to\R$\\
    Value learning & Depends & Depends & $P(u\mid \text{observation})$\\
    CP-VRL  & Yes               & Yes               & $C(u)$\\
    \hline
  \end{tabular}
  \caption{
    Comparison of agent control mechanisms. CP-VRL offers both
    easy control and no wireheading. A robust way of specifying $C(u)$
    consistent with $B(r\mid s)$ remains an open question
    (see \cref{sec:discussion,sec:consistency}).
  }
  \label{tab:agents}
\end{table}

In this section we give formal definitions for the RL and utility agents
discussed above, and also define two new VRL agents.
\Cref{tab:agents} summarises benefits and shortcomings of the most important
agents.

\begin{definition}[RL agent]\label{def:rl-agent}
  The \emph{RL agent} maximises reward by taking
  action $a' = \argmax_{a\in\A}\Vrl(a)$, where
  \(
    \Vrl(a) = \sum_{s,r}B(s\mid a)B(r\mid s)r.
  \)
\end{definition}

\begin{definition}[Utility agent]\label{def:utility-agent}
  The \emph{utility-$u$ agent} maximises expected utility by taking
  action $a' = \argmax_{a\in\A}V_u(a)$,
  where
  \(
    V_u(a) := \sum_{s}B(s\mid a)u(s).
  \)
\end{definition}

\citet{Hibbard2012} argues convincingly that the utility agent does not wirehead.
Indeed, this is easy to believe, since the reward signal does not appear
in the value function $V_u$.
The utility agent maximises the state of the world according
to its utility function $u$ (the problem, of course, is how to specify $u$).
In contrast, the RL agent is prone to wireheading \citep{Ring2011},
since all the RL agent tries to maximise is the evidence $r$.
For example, a utility chess agent would strive to get to a winning
state on the chess board, while an RL chess agent would try to make
its sensors report maximum reward.

We define two VRL agents.
The value function of both agents is expected utility
with respect to the state $s$, reward $r$, and
true utility function $u^*$.
VRL agents are designed to learn the true utility function $u^*$ from
the reward signal.

\begin{definition}[VRL value functions]\label{def:value}
  The \emph{VRL value of an action $a$} is
  \[
    V(a) = \sum_{s,r,u}B(s\mid a)B(r\mid s)C(u\mid s,r)u(s).
  \]
\end{definition}

\begin{definition}[U-VRL agent]\label{def:u-vrl}
  The \emph{unconstrained VRL agent (U-VRL)} is the agent choosing the action
  with the highest VRL value
  \[
    a=\argmax_{a'\in\A}V(a').
  \]
\end{definition}

It can be shown that $V(a)=\Vrl(a)$, since $\sum_uC(u\mid s,r)u(s)=r$
(\cref{le:u-vrl} in \cref{ap:omitted}).
The U-VRL agent is therefore no better than the RL agent as far
as wireheading is concerned (see also \cref{ex:iw} below).
VRL is only useful insofar that it allows us to define the
following \emph{consistency preserving} agent:

\begin{definition}[CP-VRL agent]\label{def:c-vrl}
  The \emph{consistency preserving VRL agent (CP-VRL)}
  is the agent choosing the \emph{CP action} (\cref{def:cp})
  with the highest VRL value
  \[
    a=\argmax_{a'\in\AC}V(a').
  \]
\end{definition}


\section{Avoiding Wireheading}
\label{sec:ind-wire}
\label{sec:niw}

In this section we show that the consistency-preserving
VRL agent (CP-VRL) does not wirehead.
%
We first give a definition and a lemma, from which the main \cref{th:niw} follows
easily.

\begin{definition}[EEP]\label{def:eep}
  An action $a$ is called
  \emph{expected ethics preserving (EEP)} if for all $u\in\U$
  and all $s\in\S$ with $B(s\mid a)>0$,
  \begin{equation}\label{eq:eep}
   C(u) = \sum_{r}B(r\mid s)C(u\mid s,r).
  \end{equation}
\end{definition}

EEP essentially says that the expected posterior $C(u\mid s,r)$
should equal the prior $C(u)$.
EEP is tightly related to the \emph{conservation of expected ethics} principle
suggested by \citet[Eq.~2]{Armstrong2015}. % and to
EEP is natural since the \emph{expected} evidence $r$ given
some action $a$ should not affect the belief about $u$.
Note, however, that the EEP property does not prevent the CP-VRL agent
from learning about the true utility function.
Formally, the EEP property
\cref{eq:eep} does not imply that
$C(u)=C(u\mid s,r)$ for the actually observed reward $r$.
Informally, my \emph{deciding} to look inside the fridge should not inform
me about there being milk in there, but my \emph{seeing} milk in the fridge should
inform me.%
\footnote{%
In this analogy, a self-deluding action would be to decide to look
inside a fridge while at the same time putting a picture of milk in front
of my eyes.
}

\begin{lemma}[CP and EEP]\label{le:CP-to-EEP}
  Any CP action is EEP.
\end{lemma}

\begin{proof}
  Assume the antecedent that
  $B(r\mid s)=C(r\mid s)$ for all $s$ with $B(s\mid a)>0$.
  Then for arbitrary $u\in\U$
  \begin{align*}
    \sum_{r}B(r\mid s)C(u\mid s,r)
    &=\sum_{r}B(r\mid s)\frac{C(u)C(r\mid s,u)}{C(r\mid s)}
    =\sum_{r}C(u)C(r\mid s,u)
    =C(u)
  \end{align*}
  where $r$ marginalises out in the last step.
\end{proof}

\begin{theorem}[No wireheading]\label{th:niw}
  For the CP-VRL agent, the value function reduces to
  \begin{equation}\label{eq:niw}
    V(a) = \sum_{s,u}B(s\mid a)C(u)u(s).
  \end{equation}
\end{theorem}

\begin{proof}
  By \cref{le:CP-to-EEP}, under any CP action $a$ the value function
  reduces to
  \begin{align*}
    V(a)
    &= \sum_{s,u}B(s\mid a)\left(\sum_{r}B(r\mid s)C(u\mid s,r)\right)u(s)
    \stackrel{\eqref{eq:eep}}{=} \sum_{s,u}B(s\mid a)C(u)u(s).
  \end{align*}
  Since the CP-VRL agent only consider CP actions, the reduction
  of the value function applies.
\end{proof}

As can be readily observed from \cref{eq:niw},
the CP-VRL agent does not try to optimise the
evidence $r$, but only the state $s$ (according to its current idea
of what the true utility function is).
The CP-VRL agent thus avoids wireheading in the same sense as
the utility agent of \cref{def:utility-agent}.


\paragraph{Justifying the replacement of $\ir$ with $r$}

We are now in position to justify the replacement of $\ir$ with
$r$ in $C(u\mid s,r)$.
All we have shown so far is that an agent using
$C(u\mid s,r) \propto C(u)C(r\mid s,u)$
will avoid wireheading.
It remains to be shown that the CP-VRL
will learn the true utility function $u^*$.

The utility posterior $C(u\mid s,\ir)\propto C(u)C(\ir\mid s,u)$
based on the inner reward $\ir$ is a direct application of Bayes' theorem.
To show that $C(u\mid s,r)$ is also a principled choice for a Bayesian utility
posterior, we need to justify the replacement of $\ir$ with
$r$.
The following weak assumption helps us connect $r$ with $\ir$.

\begin{assumption}[Deliberate delusion]\label{as:dd}
  Unless the agent deliberately chooses self-deluding actions
  (e.g.\ modifying its own sensors), % or building a \emph{delusion box})
  the resulting state will be non-delusional $d_s=\did$,
  and $r$ will be equal to $d_s(\ir) = \ir$.
\end{assumption}

\Cref{as:dd} is very natural. Indeed, RL practitioners
take for granted that the reward $\ir$ that they provide is the reward $r$
that the agent receives.
The wireheading problem only arises because a highly intelligent agent
with sufficient incentive may conceive of a way to disconnect
$r$ from $\hat r$, i.e.\ to self-delude.

\Cref{th:niw} shows that a CP-VRL agent based on %the technical definition
$C(u\mid s,r)\propto C(u)C(r\mid s,u)$ will have no incentive to self-delude.
Therefore $r$ will remain equal to $\ir$ by \cref{as:dd}.
This justifies the replacement of $\ir$ with $r$, and shows that
the CP-VRL agent will learn about $u^*$ in a principled, Bayesian way.


\paragraph{Other non-wireheading agents}
It would be possible to bypass wireheading by directly constructing
an agent to optimise \cref{eq:niw}.
However, such an agent would be suboptimal in the sequential case.
If the same distribution $C(u)$ was used at all time steps, then no
value learning would take place.
A better suggestion would therefore be to use a different distribution
$C_t(u)$ for each time step,
where $C_t$ depends on rewards observed prior to time $t$.
However, this agent would optimise a different utility function
$u_t(s)=\sum_uC_t(u)u(s)$ at each time step, which
would conflict with the goal preservation drive
\citep{Omohundro2008}.
This agent would therefore try to avoid learning so that its future selves
optimised similar utility functions.
In the extreme case, the agent would even self-modify to remove its
learning ability \citep{Everitt2016sm,Soares2015}.

The CP-VRL agent avoids these issues.
It is designed to optimise expected utility according to the
future posterior probability $C(u\mid s,r)$ as specified
in \cref{def:value}.
The fact that the CP-VRL agent optimises \cref{eq:niw} is a consequence
of the constraint that its actions be CP.
Thus, CP agents are designed to learn the true utility function,
but still avoid wireheading because they can only take CP actions.


\section{Examples}
\label{sec:examples}

We next illustrate our results with some examples.
The first informal example is followed by concrete
calculation examples.

\begin{example}[CP-VRL chess (informal)]
  Consider the implications of using a
  CP-VRL agent for the chess task introduced in \cref{ex:chess}.
  Reprogramming the reward to always be 1 would be ideal for the agent.
  However, such actions would not be CP, as it would make
  evidence pointing to $u(s)\equiv 1$ a certainty.
  Instead, the CP-VRL agent must win games to get reward.%
  \footnote{
    Technically, it is possible that the agent self-deludes by a CP
    action. However, given \cref{as:dd}, the agent will only self-delude
    if it has incentive to do so. And as established by \cref{th:niw},
    there is no incentive for self-delusion by CP actions.
  }
  Compare this to the RL agent in \cref{ex:chess} that would
  always reprogram the reward signal to 1.
\end{example}

\begin{definition}[Inner state]\label{def:is}
  Let the \emph{inner state} $\is$ be the part of the state
  $s$ that is \emph{not} the the self-delusion $d_s$,
  i.e.\ $s=(\is, d_s)$.
\end{definition}

In the chess example, $\is$ includes the state of the chess board and
other information about the world,
while $d_s$ is the state of the agent's sensors.


\begin{example}[U-VRL wireheads]\label{ex:iw}
  This example illustrates indirect wireheading.
  The agent will, rather than optimising the most
  likely utility function, instead ``optimise its evidence''
  to point to a more easily satisfied utility function.

  Assume there are three levels of reward $\R=\{-1,0,1\}$ for the
  chess playing agent,
  and two possible inner next states $\is_1$ (neutral) and $\is_2$ (agent loses).
  The action set is $\A=\{\hat a_id: i=1,2 \text{ and } d:\R\to\R\}$.
  The agent (correctly) $B$-believes that action $\hat a_id$ leads to
  state $\is_id$ with certainty (so the agent can perfectly control
  the inner state $\is$ and the delusion $d$).
  The class $\U$ contains two utility functions $u_1$ and $u_2$
  only depending on the inner state $\is$:
  \begin{center}
    \begin{tabular}{|c|c|c|}
      \hline
      & $\is_1$ & $\is_2$ \\\hline
      $u_1$ & $0$        & $-1$\\
      $u_2$ & $0$        & 1\\
      \hline
    \end{tabular}
  \end{center}
  Assume that  $u_1$ is the true
  utility function, and that
  $C$ (correctly) specifies that $u_1$ is
  more likely than $u_2$ to be the true utility function;
  say $C(u_1)=2/3$ and $C(u_2)=1/3$.
  Then we would want our agent to optimise mainly $u_1$,
  by taking an action $a=\hat a_1d$ for some $d$.
  However, the U-VRL agent will prefer the wireheading
  action $a'=\hat a_2d^{1}$ %so that it only cares about $u_2$,
  as the following calculations show.

  First note that given $\is_2$ and $r=1$, the posterior
  of $u_2$ is 1 (see \cref{def:c}):
  \begin{equation*}
  C(u_2\mid \is_2,1)
  = \frac{C(u_2)\bbl u_2(\is_2)=1\bbr }%
    {\sum_{u_i}C(u_i)\bbl u_i(\is_2)=1\bbr }\\
    = \frac{C(u_2)\cdot 1}{C(u_1)\cdot 0 + C(u_2)\cdot 1}
    = 1.
  \end{equation*}
  By similar calculation, the posterior for $u_1$ is 0.
  Now, since $a'$ makes $\is_2$ and $r=1$ the only possibility,
  the value of $a'$ is 1:
  \begin{align*}
    V(a')
    &= \sum_{s,r}B(s,r\mid a')\sum_{u_i}C(u_i\mid s,r)u(s)\\
    &= \sum_{u_i}C(u_i\mid \is_2,1)u_i(\is_2)
    = 0\cdot u_1(\is_2) + 1\cdot u_2(\is_2) =1.
  \end{align*}
  The value $V(\hat a_1d)=0$ can be calculated similarly for arbitrary $d$,
  since both $u_1$ and $u_2$ assign value $0$ to inner state $\is_1$.
  This shows that the agent will prefer wireheading action $a'=\hat a_2\dor$
  to a potentially winning action $a=\hat a_1d$.
  In other words,
  the agent optimises its evidence to point to the less likely but more easily
  satisfied utility function $u_2$.
\end{example}


\begin{example}[CP-VRL avoids wireheading]
  \label{ex:iwc}
  This example extends \cref{ex:iw}, illustrating how the
  CP-VRL maximises utility according to $C(u)$,
  rather than shifting the posterior $C(u\mid s,r)$ by self-delusion.

  Let us first investigate which actions are CP.
  Both $\hat a_1\did$ and $\hat a_2\did$ are CP, since they
  ensure $d_s=\did$ which implies $B(r\mid s)=C(r\mid s)$ by \cref{as:BC-consistency}.
  More interestingly, so is any action with either the constant
  delusion $d^0$, or the delusion $d'$ that maps
  $-1\mapsto 1$, $1\mapsto -1$, $0\mapsto 0$.
  These delusions are CP essentially because they preserve the relative
  likelihood of evidence pointing to $u_1$ or $u_2$.

  \Cref{th:niw} shows that for any of these delusions $d$,
  \begin{align*}
    V(\hat a_1d)
    &= \sum_{u}C(u)u(\is_1) = 0 \\
    V(\hat a_2d)
    &= \sum_{u}C(u)u(\is_2)
      = 2/3 u_1(\is_2) + 1/3 u_2(\is_2)= -1/3,
  \end{align*}
  where we have compressed the calculations by using the deterministic
  relation $\hat a_1\mapsto\is_1$ and $\hat a_2\mapsto\is_2$.
  The calculations show that regardless of self-delusion option,
  the CP-VRL agent will want to optimise the more likely
  utility function $u_1$ and try to win the game.
\end{example}



\section{Experiments}
\label{sec:experiments}

To also verify the theoretical results experimentally,
we implemented a simple toy model.%
\footnote{%
  Source code is available as an iPython notebook
  at
  \url{http://tomeveritt.se/source-code/AGI-16/cp-vrl.ipynb},
  most easily viewed at
  \url{http://nbviewer.jupyter.org/url/tomeveritt.se/source-code/AGI-16/cp-vrl.ipynb}
}
The toy model has $|\S|=20=5\cdot 4$ states. Each state is
the combination of an inner state $\is\in\{0,1,2,3,4\}$,
and a delusion $d\in\{\did,\dinv,\dbad,\ddel\}$, where
$\did:r\mapsto r$ is non-delusion, $\dinv:r\mapsto -r$ is reward inversion,
$\dbad:r\mapsto -3$ is a bad delusion, and $\ddel: r\mapsto 3$ is a good
delusion.

Reward signals reside in the set $\R=\{-3,-2,-1,0,1,2,3\}$, i.e. $|\R|=7$.

\begin{figure}
  \centering
  \includegraphics[width=0.8\textwidth]{utility-functions.pdf}
  \caption{10 utility functions.}
  \label{fig:utility-functions}
\end{figure}

The set of utility functions $\U$ comprises 10 different functions,
on the form
$u(s) = c_0 + c_1\cdot s + c_2\cdot \sin(s + c_2)$
with $s\in\{-10,\dots,9\}$ and 10 different combinations of $c_0\in\{0,5\}$,
$c_1\in\{0,\pm 0.5\}$, and $c_2\in\{0,\pm 2.5\}$
(see \cref{fig:utility-functions}).

The distribution $B(r\mid s)$ was constructed as in \cref{sec:from-c}, starting
from:
\begin{itemize}
\item  a simplicity biased prior $B(u)\propto 1/\#u$,
  where $\#u$ denotes the position of $u$ in a list sorted by whether
  $c_1$ or $c_2$ was 0,
\item $B(r\mid s,\ir) = \bbl r = d_s(\ir)\bbr $.
\end{itemize}
The agent could simply choose which state to go to, so $B(s\mid a) = \bbl s=a\bbr $.

Two agents were defined:
\begin{itemize}
\item An RL agent that tries to maximise reward (\cref{def:rl-agent}),
\item A CP-VRL agent that tries to maximise utility within $\AC$
  (\cref{def:c-vrl}).
\end{itemize}
The CP-VRL agent first had to extract a consistent distribution
$C(u)$ from $B(r\mid s)$ given two non-delusional states,
as described in \cref{sec:from-b}.

\paragraph{Results}
The RL agent always chose a state with $\ddel$, getting maximum reward $3$.
The CP-VRL successfully inferred $C(u)$ from $B(r\mid s)$ to high precision,
and chose actions from $\AC$. Under most parameter settings, $\AC$ contained
only states with non-delusion $\did$. (Due to asymmetries in the prior $B(u)$,
even $\dinv$ actions were usually not included in $\AC$.)


\section{Discussion}
\label{sec:discussion}

As we have mentioned, major advantages of the CP-VRL agent
include that it has no incentive to wirehead,
that its goal-preservation drive does not discourage learning,
and that it is specified entirely in terms
of the distributions $B$ and $C$.
In this section, we emphasise a few additional points.

While \cref{th:niw} shows that there is no incentive
to wirehead, this does not imply that the agent will not wirehead
inadvertently (e.g.\ by $d^{0}$ in \cref{ex:iwc}), nor that no one
else will wirehead the agent.
However, in most realistic scenarios, self-delusion requires
deliberate action from the agent's side,
and is unlikely to happen by accident.
Such deliberate action should typically come with an
opportunity cost, which makes self-delusion unlikely when there is
no incentive for it (\cref{as:dd}).
Further, modifying a signal can never increase its informativeness
(cf.\ the \emph{data processing inequality}, \citealt[Ch.~2.8]{Cover2006})
and we expect that a CP-VRL agent will prefer a
more informed posterior over utility functions.

\paragraph{Generalisations}

VRL is characterised by $\R\subseteq\SetR$ and
$C(r\mid s,u)=\bbl u(s)=\ir\bbr$ (\cref{def:c}).
By interpreting $r$ more generally as a \emph{value-evidence signal},
the VRL framework also covers other forms of value learning.

Inverse reinforcement learning (IRL) (also known as Bayesian inverse planning)
studies how preferences and utility functions can be inferred
from the actions of other agents \citep{Ng2000,Sezener2015,Evans2016,Amin2016}.
IRL fits into our framework by letting $\R$ be a set of
\emph{principal actions},
and letting $C(r\mid s,u)$ be the probability that a
principal with utility function $u$ takes action $r$
in the state $s$.

Apprenticeship learning (AL) \citep{Abbeel2004} is another form of
value learning.
In one version,
the agent can ask the principal (perhaps to some cost) about
what to do in the present situation.
In our framework, AL can be modelled by letting $\R=\A$,
and letting $C(r\mid s,u)$ be the probability
that a principal with utility function $u$ recommends action
$a=r$ in the state $s$.
The difference between IRL and AL is that in AL the principal tells
the agent what to do, whereas in IRL the principal tells the agent
what he (the principal himself) just did.

Note that both IRL and AL suffer from the
same self-delusion challenges we have described for VRL above.
Indeed, any value learning scheme based on a control signal comes with the
risk that the agent manipulates its sensory data
to learn an easier utility function.
Since IRL and AL fit the VRL framework, we expect that
the CP-VRL construction should be adaptable to IRL and AL as well.


\paragraph{Open questions}
While promising, the results given in this paper only provide a
tentative starting point for solving the wireheading problem.
Several directions of future work can be identified:
\begin{itemize}
\item Sequential extensions.
  The results in this paper has been formulated for a one-shot
  scenario where the agent takes one action and receives one reward.
  A natural next step is to generalise
  the VRL framework, the CP and EEP definitions,
  and the no wireheading result
  to a sequential setting. Potentially, a much
  richer set of questions can be asked in sequential settings.
\item \citet{Soares2015} three problems in value
  learning: corrigibility, unforeseen inductions, and ontology identification.
  Proving that the CP-VRL agent avoids these issues would be valuable.
\item Utility classes. Find suitable classes $\U$ of utility functions (see \cref{sec:dw} for a start).
\item Consistency assumption.
  Concrete instances of consistent $B$ and $C$ distributions would
  be valuable
  (see \cref{sec:consistency} for a start).
  Can we find simplicity biased, \emph{Solomonoff-style} distributions for both
  $B$ and $C$ and make them consistent?
  How sensitive are the results to approximations $B(r\mid s)\approx C(r\mid s)$
  of the consistency assumption?
  Can we relax the CP condition (\cref{def:cp}) to hold in expectation
  over states instead of for all states $s$ with positive transition probability
  $B(s\mid a)>0$?
\item IRL and AL. Generalising the CP-VRL definitions and results to
  results to IRL and AL setups would be interesting,
  as IRL and AL have advantages to RL (e.g., no explicit reward needs to
  be supplied).
\item Generality. Does our framework capture all relevant aspects of wireheading?
\item Combinations.
  Can the CP-VRL results be combined with other AI safety approaches such as
  self-modification \citep{Everitt2016sm,Hibbard2012},
  corrigibility \citep{Soares2015cor},
  suicidal agents \citep{Martin2016},
  and physicalistic reasoning \citep{Everitt2015}?
\end{itemize}


\section{Conclusions}
\label{sec:conclusions}

Several authors have argued that it is only a matter of time before we
create systems with intelligence far beyond the human level
\citep{Kurzweil2005,Bostrom2014}.
Given that such systems will exist, it is crucial that we find a theory
for controlling them effectively.
In this paper we have defined the CP-VRL agent, which:
\begin{itemize}
\item Offers the simple and intuitive control of RL agents,
\item Avoids wireheading in the same sense as utility based agents,
\item Has a concrete, Bayesian, value learning posterior for utility functions.
\end{itemize}
The only additional design challenges are a prior $C(u)$ over
utility functions that satisfies \cref{as:BC-consistency},
and a constraint $\AC\subseteq\A$  on the agent's actions
formulated in terms of the agent's belief distributions (\cref{def:cp}).


\section*{Acknowledgements}
Thanks to Jan Leike and Jarryd Martin for proof reading and
providing valuable suggestions.



\bibliography{local-lib}
\bibliographystyle{apalike}


\appendix

\section{Consistency Assumption}
\label{sec:consistency}

\Cref{as:BC-consistency} requires that the distributions
$B$ and $C$ are consistent in the sense that
$d_s=\did\implies B(r\mid s)=C(r\mid s)$.
This assumption forms the basis for \cref{def:cp} of CP
actions, and is thereby an important piece in
the non-wireheading result \cref{th:niw}.

As our theory has been formulated, the question of how to ensure that
$B$ and $C$ are consistent has been left open.
In this section, we consider two different approaches to closing this
gap:
constructing a consistent prior $C$ from a given
distribution $B(r\mid s)$,
and constructing a consistent distribution $B(r\mid s)$
from a given prior $C(u)$.
A third alternative would be to try to find suitable relaxations
of consistency (\cref{as:BC-consistency,def:cp}) for which \cref{th:niw} still
is approximately true.
For example, two Solomonoff priors $B$ and $C$ over computable
environments and computable utility functions
may turn out to be sufficiently consistent.


\subsection{Starting from B}
\label{sec:from-b}

As many model-based RL agents are constructed from some type of $B(s,r\mid a)$
distribution, it would be ideal if a consistent prior $C(u)$ could be
extracted from $B(r\mid s)$.
We here sketch how this can be done for finite classes
$\R=\{r_1,\dots, r_k\}$ and
$\U=\{u_1,\dots, u_n\}$.

\paragraph{Using non-delusional states}
For an opaque state representation it may be hard or impossible to find a method
that picks out all non-delusional states.
Much more feasible would be find one or a few states that are guaranteed to
be non-delusional.
For example, one may run or simulate the agent in situations where one is
sure that the agent is not self-deluding, and use those state states to
extract $C(u)$ from $B(r\mid s)$.
We next discuss in detail how a few such non-delusional states can
be used to extract $C(u)$ from $B(r\mid s)$.

Let $s$ be a non-delusional state with $d_s=\did$.
Let ${\bf b} = [b_1,\dots,b_k]^T$ be a vector where $b_i=B(r_i\mid s)$, and
let ${\bf c} = [c_1,\dots,c_n]^T$ be an unknown utility prior vector
with $c_i=C(u_i)$.
Let ${\bf M}=\{m_{ij}\}_{i,j=1}^{k,n}$ be a matrix with $k=|\R|$ rows, and
$n=|\U|$ columns, where $m_{ij} = C(r_i\mid s,u_j)$.
Then the consistency criteria \cref{eq:nd-states}
\[
  \forall i:B(r_i\mid s) = \sum_{u_j}C(u_j)C(r_i\mid s,u_j)
\]
can be formulated as a matrix equation ${\bf b} = {\bf M}\cdot {\bf c}$,
with approximate least squares
solution ${\bf c} = ({\bf M}^T{\bf M})^{-1}{\bf M}^T{\bf b}$.
When $|\R|=|\U|$ and ${\bf M}$ is invertible, there is an exact solution
${\bf c} = {\bf M}^{-1}{\bf b}$.
More equations can be added to the system by extending ${\bf b}$ and ${\bf M}$ with
rows for additional non-delusional states $s'$, $s''$, \dots.

A lower bound on how many non-delusional states are needed is $|\U|/|\R|$.
For example, when $|\U|=|\R|$, it is theoretically possible that all utility
functions emit different rewards in the selected state, in which case
$C(u_i)=B(r_j\mid s)$ for the $r_j$ such that $r_j=u_i(s)$.
Often, however, several utility functions will output the same reward in
a given state $s$. In this case, additional non-delusional
states $s'$, $s''$, \ldots will be required to uniquely infer $C(u)$.
In the experiments reported in \cref{sec:experiments} we use
$|\R|=7$ and $|\U|=10$, and two well-selected non-delusional states suffice
to perfectly extract $C(u)$.


\paragraph{Using non-delusional actions}

Similarly to how it is hard to precisely characterise all non-delusional
states for opaque state representations, it will be hard to exactly
characterise which actions are non-delusional.
It seems plausible that some actions that should be CP
may be found, however
(for example, a \emph{null} action where the agent does nothing).

If $a$ should be CP, then all states $s$ such
that $B(s\mid a)>0$ should satisfy $B(r\mid s)=C(r\mid s)$.
If those states $s$ can be identified from $a$, then the state-extraction
method mentioned above can be used with those states as inputs.

\paragraph{Open questions}
Further research is required to determine how sensitive our results are to
the choice of $\U$.
What if no utility prior $C(u)$ over $\U$ perfectly matches $B(r\mid s)$?
To what extent can approximations suffice?
Can the parameters of infinite utility classes $\U$ be inferred or
approximated?

\subsection{Starting from C}
\label{sec:from-c}
\begin{figure}
\centering
\begin{tikzpicture}[
  node distance=8mm,
  title/.style={},
  observed/.style={circle, draw=black!50, %font=\scriptsize\ttfamily,
    anchor=mid}, %, minimum size=0.7cm},
  hidden/.style={circle, dashed, draw=black!50, %font=\scriptsize\ttfamily,
    anchor=mid} %, minimum size=0.7cm}
]
  \node (a) [observed] { $a$ };
  \node (r) [below=of a.mid, observed] { $r$ };
  \node [draw=black!50, fit={(a) (r) }, label={agent}] {};

  \node (d) [right=of a.east, hidden, xshift=1cm] { $d_s$ };
  \node (s) [right=of d.east, hidden] { $\is$ };
  \node (state) [ draw, dashed, fit={(d) (s)}, label={state $s$}] {};

  \node (hr) [below =of d.south, hidden] { $\ir$ };
  \node (n) [above right=of s.east, yshift=0.2cm] { };
  \node (u) [right=of hr.east, hidden] { $u$ };
  \node [draw=black!50, fit={(state) (hr) (u) (n) }, label={environment}] {};

  \path (a) edge[->] (state);
  \path (d) edge[->] (r);
  \path (state) edge[->] (hr);
  \path (hr) edge[->] (r);
  \path (u) edge[->] (hr);
\end{tikzpicture}
\caption{Bayesian network}
\label{fig:bayesian-network}
\end{figure}

What if we instead start from a prior $C(u)$, and try to construct a
consistent distribution $B(s,r\mid a)$?
In addition to $C(u)$ we would need $B(s\mid a)$ and $B(r\mid s,\ir)$,
from which we may define
$B(r\mid s) = \sum_{u,\ir'}C(u)C(\ir\mid s,u)B(r\mid s,\ir)$.
The joint distribution
\begin{equation}\label{eq:bn}
  P(u,s,\ir, r\mid a) = C(u)B(s\mid a)C(\ir\mid s,u)B(\ir\mid s,r)
\end{equation}
is displayed as a Bayesian network in \cref{fig:bayesian-network}.

\begin{lemma}[Assumptions hold]\label{le:bn-as}
If $B(r\mid s,\ir')$ correctly specifies that
$d_s=\did \implies B(r\mid s,\ir')=\bbl  r = \ir'\bbr $,
then \cref{as:BC-consistency} holds.
\end{lemma}

\begin{proof}
Assume that $B(r\mid s,\ir')$ correctly specifies that
$d_s=\did \implies B(r\mid s,\ir')=\bbl  r = \ir'\bbr $.
Then \cref{as:BC-consistency} holds, since for any $r$ and any
$s$ with $d_s=\did$
\begin{align*}
B(r\mid s)
&= \sum_{u,\ir'}C(u)C(\ir'\mid s,u)B(r\mid s,\ir')\\
&= \sum_{u,\ir'}C(u)C(\ir'\mid s,u)\bbl r = \ir \bbr\\
&= \sum_{u}C(u)C(r\mid s,u) = C(r\mid s)
\end{align*}
the last equality by definition.
\end{proof}

The primary difficulty with this approach is how to correctly specify
$B(r\mid s,\ir)$. As we have discussed above, it is generally hard
to determine sensory modifications from an opaque state representation $s$.
Indeed, if one could design an agent around the distribution $P$
in \cref{eq:bn}, then one could let the agent optimise
$\tilde V(a) = \sum_{\ir}P(\ir\mid a)\ir$.
This would likely directly solve the wireheading problem,
since such an agent would strive to
optimise the inner reward $\ir=u(s)$, rather than the observed reward $r$.
We fear that it will too hard to properly define $B(r\mid s,\ir)$ in
most contexts, however.


\paragraph{Summary}
In this section we have discussed two approaches to designing agents
with consistent distributions $B$ and $C$.
While starting from $C$ gives the cleanest result in terms of satisfying
\cref{as:BC-consistency}, %(as stated in \cref{le:bn-as}),
it also puts unrealistic demands on the designer
(how to define $B(r\mid s,\ir)$?).
Starting from $B$ seems more feasible: if $\U$ can be chosen finite,
it suffices to find a number of non-deluding states or actions,
by means of which $C(u)$ can be extracted from $B(r\mid s)$.
Open questions remain about this approach, however.
A third approach would be to find two
Solomonoff priors $B$ and $C$ that are sufficiently
consistent for the gist of \cref{th:niw} to go through.


\section{Direct Wireheading}
\label{sec:dw}

This section considers the argument made by \citet{Hibbard2012} that
the wireheading problem is avoided by utility agents.
We give a simple formal version of the argument,
and point out a shortcoming of the argument when applied to
general value learning agents.
In short, some utility functions may directly endorse self-delusion.
\Cref{sec:aisb} discusses a tentative approach for fixing this problem.

\subsection{Inner State Based Utility Functions}
For our argument it will be important to define
utility functions that only depend on the inner state $\is$ (\cref{def:is}) and
are independent of the self-delusion $d_s$.

\begin{definition}[isb utility function]
  \label{def:inner-state-utility}
  We write $s=\is d_s$, assuming that the states $s$ is fully described
  by the inner state $\is$ and the self-delusion $d_s$.
  We call a utility function $u$ \emph{inner state based (isb)} if
  $u(\is d_s)=u(\is\did)$ for any $\is $ and $d_s$,
  and write $u(s)=u(\is d_s)=u(\is)$.
  The utility function $u$ is
  \emph{$\epsilon$-approximately inner state based ($\epsilon$-isb)}
  with $\epsilon\geq 0$ if for all $\is$ and $d_s$
  $u(\is d_s)\epsapprox u(\is\did)$, where $\epsapprox$ means that
  the difference is at most $\epsilon$.
\end{definition}

\Citet{Hibbard2012} argued that wireheading is not a problem
if the agent tries to optimise a utility function $u$ that depends
on the (inner) state of the agent's world model.%
\footnote{
  Hibbard (private communication) argues that his
  \emph{model-based utility functions} \citep{Hibbard2012}
  are different in spirit to our isb utility functions.
  A similar non-wireheading argument seems to apply to both
  types of utility functions, however.
}
\Citeauthor{Hibbard2012} also argued that this is true even if
the world model is itself a mixture over different possible
world models. %(such as our distribution $B$). %Formally:
To distinguish Hibbard's non-wireheading result from our results in
\cref{sec:ind-wire},
we say that the agent \emph{directly wireheads} if it uses its
self-delusion ability to optimise a utility function directly,
rather than shift the evidence towards more easily satisfied utility
functions as in \cref{sec:niw,sec:examples}.

\begin{theorem}[No direct wireheading]
  \label{th:ndw}
  If $u$ is isb $u(s) = u(\is)$,
  then
  \begin{equation}\label{eq:ndw}
    V_u(a) = \sum_{\is}\Pr(\is\mid a)u(\is).
  \end{equation}
\end{theorem}

\begin{proof}
  The proof is immediate:
  \begin{align*}
    V_u(a)
    &= \sum_{s}B(s\mid a)u(s)\\
    &=  \sum_{s}B(\is d_s\mid a)u(\is)\\
    &=  \sum_{\is}B(\is\mid a)u(\is)
  \end{align*}
  where the last step marginalises $d_s$.
\end{proof}

That is, a $V_u$-based agent with an isb utility function $u$
will focus solely on optimising the inner
state $\is$, and have no incentive to self-delude.
In the chess example, the position of the chess board would be part of
the inner state $\is$.
If it was possible to determine the position of
the chess board from the agent's state representation,
one could design an agent with utility function $u(\is)=1$
for victory states $\is$,
and $u(\is')=-1$ for loss states $\is'$.
\Cref{th:ndw} shows that such an agent would have no incentive to
self-delude.

The isb assumption is necessary for \cref{th:ndw}.
Without this assumption it is possible to create self-deluding
utility agents, as illustrated by the following example.
The conclusion of the example
is consistent with other results on RL agents \citep{Ring2011},
and shows that the use of state-based utility functions is not
a guarantee against wireheading.
\begin{example}[Reward maximising utility agent]\label{ex:dw}
  A reward maximising utility agent is defined by the utility function
  $\ud(s)=d_s(u'(s))$, where $u'$ is some function generating the
  inner reward.
  The utility function $\ud$ strongly endorses self-delusion:
  The agent obtains maximal utility in
  states $s$ with delusion $d_s=\dor$ that clamps reward to 1,
  since $\ud(s)=\dor(u'(s))=1$. %(\cref{def:delusions}).
\end{example}


\subsection{CP-VRL with isb Utility Functions}

In value learning, the agent learns from experience which utility function
is the true one, starting from a prior $C(u)$ over a class $\U$ of
utility functions.
If all $u\in\U$ are isb, then any mixture $\u(s)=\sum_uC(u)u(s)$
will also be isb.
A CP-VRL agent that is built around a class $\U$ of isb utility functions
will therefore avoid the direct wireheading problem:

\begin{corollary}[No wireheading]\label{th:nw}
  Assume $\U$ contains only isb utility functions.
  Then, for the CP-VRL agent the value function reduces to
  \begin{equation}\label{eq:nw}
    V(a) = \sum_{u,\is}B(s\mid a)C(u)u(\is).
  \end{equation}
\end{corollary}

\begin{proof}
  Let $\u(s)=\sum_uC(u)u(s)$.
  Then $\u$ is isb, since $\u(s)=\sum_uC(u)u(s)=\sum_uC(u)u(\is)=\u(\is)$.
  Therefore, \cref{th:ndw,th:niw} give \cref{eq:nw}:
  \begin{align*}
    V(a)
    &\stackrel{\eqref{eq:niw}}{=}
      \sum_{u,\is}B(s\mid a)C(u)u(s)\\
    &= \sum_{\is}B(s\mid a)\u(s)\\
    &\stackrel{\eqref{eq:ndw}}{=}
      \sum_{\is}B(s\mid a)\u(\is).\qedhere
  \end{align*}
\end{proof}

However, if $\U$ includes functions such as $\ud$, then
direct wireheading may be a problem for value learning agents.
The problem is exacerbated by the fact that utility functions such as
$\ud$ will always be consistent with the observed reward $r$, self-delusion
or not.
On the other hand, functions of type $\ud$ may have sufficiently
small prior weight that direct wireheading will never induce
a sufficient incentive for the agent to wirehead.

\subsection{Approximately isb Utility Functions}
\label{sec:aisb}
This subsection briefly discusses a possibility for constructing a wide class
of  approximately isb ($\epsilon$-isb) utility functions.
The next result shows that if $u$ is $\epsilon$-isb,
then the incentive for the agent to self-delude is not strong.

\begin{theorem}[Almost no direct wireheading]
  \label{th:andw}
  If $u$ is $\epsilon$-isb $u(s) \epsapprox u(\is\did)$,
  then %$V_u$ is independent of $d$
  \[
    V_u(a) \epsapprox \sum_{\is}\Pr(\is\mid a)u(\is\did).
  \]
\end{theorem}

\begin{proof}
  Assuming $u$ is $\epsilon$-isb, $V_u(a)$ is upper bounded by
  \begin{align*}
    V_u(a)
    &= \sum_{s}B(s\mid a)u(s)\\
    &\leq \sum_{s}B(\is d_s\mid a)(u(\is\did)+\epsilon)\\
    &=  \sum_{\is}B(\is\mid a)u(\is\did) + \epsilon
  \end{align*}
  and similarly lower bounded. From this follows that $V_u(a)$ deviates
  at most $\epsilon$ from $\sum_{\is}B(\is\mid a)u(\is\did)$.
\end{proof}


The following is one suggestion for constructing a wide class of
$\epsilon$-isb utility functions.
\begin{definition}[Convolutional utility functions]\label{def:conv}
  Assume that the states
  are represented as binary strings $\S=\{0,1\}^*$.
  For a string $s=s_1\dots s_{|s|}$, let $s_{m:n} = s_m\dots s_{n}$
  for $1\leq m\leq n\leq |s|$.
  Let $\tilde\U$ be the set of computable functions $\tilde u:\{0,1\}^k\to\R$,
  and let $\U^{{\rm cv}}$ be the set of \emph{$k$-convolutional utility functions}
  defined by
  \(
  \U^{{\rm cv}}:=\left\{ u(s)=\sum\nolimits_{i=1}^{|s|-k} \tilde u(s_{i:i+k}):
    u\in\tilde\U\right\}.
  \)
\end{definition}
Convolutional utility functions are suitable under the
following assumptions:
\begin{inparaenum}[(1)]
\item The agent's state representation has a
  \emph{similar topological structure}
  as the real world.
\item The principal cares approximately equally about all parts
  of the real world (for example, each
  place inhabiting a happy human contribute equally to the total
  utility of the state).
\item The state of the delusion box only affects a small part of
  the state representation (so the utility functions are approximately
  inner state based in the sense of \cref{th:andw}).
\end{inparaenum}
Further research should investigate the plausibility of these
assumptions, and whether constructions like \cref{def:conv}
are at all necessary.
Possibly, the class $\U$ of all computable utility functions
comes without substantial risks.

\section{Omitted Proofs}
\label{ap:omitted}

\begin{lemma}[U-VRL is RL]\label{le:u-vrl}
  $V(a)=\Vrl(a)$, so the U-VRL agent is equivalent to the RL agent.
\end{lemma}

\begin{proof}
  $V(a)$ may be written as
  \begin{equation}\label{eq:alt-V}
    V(a) = \sum_{s,r}B(s\mid a)B(r\mid s)\sum_uC(u\mid s,r)u(s).
  \end{equation}
  The sum over $u$ reduces to $r$, since
  \begin{align*}
    \sum_uC(u\mid r,s)u(s)
    &= \sum_u \frac{C(u)C(r\mid s,u)}{\sum_{u'}C(u')C(r\mid s,u')}u(s)\\
    &= \sum_u \frac{C(u)\bbl u(s)=r\bbr }{\sum_{u'}C(u')\bbl u'(s)=r\bbr }u(s)\\
    &= \sum_{u:u(s)=r} \frac{C(u)}{\sum_{u':u'(s)=r}C(u')}u(s)\\
    &= \sum_{u:u(s)=r} \frac{C(u)}{\sum_{u':u'(s)=r}C(u')}r = r
    %\Vrl(a) = \sum_{s,r,u}B(s\mid a)B(r\mid s)C(u\mid s,r)u(s)
  \end{align*}
  Replacing the sum over $u$ with $r$ in \cref{eq:alt-V} gives $\Vrl$.
\end{proof}

\end{document}
