# Local differences determined by convex sets

Krishnendu Bhowmick  Johann Radon Institute for Computational and Applied
Mathematics
Linz, Austria<EMAIL_ADDRESS>,  Miriam Patry
<EMAIL_ADDRESS>and  Oliver Roche-Newton  Institute for Algebra, Johannes
Kepler Universität
Linz, Austria<EMAIL_ADDRESS>
###### Abstract.

This paper introduces a new problem concerning additive properties of convex
sets. Let $S=\\{s_{1}<\dots<s_{n}\\}$ be a set of real numbers and let
$D_{i}(S)=\\{s_{x}-s_{y}:1\leq x-y\leq i\\}$. We expect that $D_{i}(S)$ is
large, with respect to the size of $S$ and the parameter $i$, for any convex
set $S$.

We give a construction to show that $D_{3}(S)$ can be as small as $n+2$, and
show that this is the smallest possible size. On the other hand, we use an
elementary argument to prove a non-trivial lower bound for $D_{4}(S)$, namely
$|D_{4}(S)|\geq\frac{5}{4}n-1$. For sufficiently large values of $i$, we are
able to prove a non-trivial bound that grows with $i$ using incidence
geometry.

##  1\. Introduction

Let $S\subseteq\mathbb{R}$ be a finite set and write
$S=\\{s_{1},s_{2},\dots,s_{n}\\}$ such that $s_{i}<s_{i+1}$ for all
$i\in[n-1]$. $S$ is said to be a convex set if $s_{i+1}-s_{i}<s_{i+2}-s_{i+1}$
for all $i\in[n-2]$.

In the spirit of the sum-product problem, Erdős raised the question of whether
$A+A$ and $A-A$ are guaranteed to be large for any convex set. Progress has
been made towards this question via a combination of methods in incidence
geometry (see for instance [2]) and elementary methods (see [3], [8] and [4]),
but the question of determining the best possible lower bounds remains open.
The current state-of-the-art results state that, for some absolute constant
$c>0$, the bounds

(1) $|S-S|\gg\frac{n^{8/5}}{(\log
n)^{c}},\,\,\,\,\,|S+S|\gg\frac{n^{30/19}}{(\log n)^{c}}$

hold for any convex set $A\subset\mathbb{R}$, see [10] and [7] respectively.
The notation $\gg$ is used to absorb a multiplicative constant. That is $X\gg
Y$ denotes that there exists an absolute constant $C>0$ such that $X\geq CY$.

In this paper, we introduce a new local variant of this problem, where only
differences between close elements of $A$ are considered. We define

$D_{i}(S):=\\{s_{x}-s_{y}:1\leq x-y\leq i\\}.$

Moreover, for any set $\mathcal{I}\subset[n-1]$, define

$D_{\mathcal{I}}(S):=\\{s_{x}-s_{y}\mid x-y\in\mathcal{I}\\}.$

We expect that $D_{i}(S)$ is large (in terms of $i$) and that
$D_{\mathcal{I}}(S)$ is large (in terms of $|\mathcal{I}|$) for any convex set
$S\subset\mathbb{R}$. We begin with some trivial observations.

  * •

For any convex set $S$, $|D_{1}(S)|=|S|-1$. Indeed, it is an immediate
consequence of the definition of a convex set that $S$ has distinct
consecutive differences. Additive properties of such sets were considered in
[8] and [9].

  * •

For any convex set $S$, we have $|D_{2}(S)|\geq|S|$. This can be seen by
observing that $s_{n}-s_{n-2}\in D_{\\{2\\}}(S)\setminus D_{\\{1\\}}(S)$, and
so

(2) $|D_{2}(S)|=|D_{\\{1\\}}(S)|+|D_{\\{2\\}}(S)\setminus D_{\\{1\\}}(S)|\geq
n-1+1=n.$

On the other hand, if we consider the set

(3) $S=\\{f_{i+3}:i\in[n]\\},$

where $f_{i}$ is the $i$-th Fibonacci number, we see that $|D_{2}(S)|=n$, and
so the lower bound (2) is optimal.

  * •

Setting $i=n-1$, we see that the set $D_{i}(S)$ is equal to the set of
positive elements of the difference set $S-S$. Therefore, the question of
obtaining lower bounds for $D_{n-1}(S)$ is equivalent to that of lower
bounding the size of $S-S$.

The main results of this paper concern the minimum possible sizes of
$D_{3}(S)$ and $D_{4}(S)$ when $S$ is convex. Let $\mathcal{S}(n)$ be the set
of all convex sets of size $n$. Define

$D_{i}(n):=\min\\{|D_{i}(S)|:S\in\mathcal{S}(n)\\}.$

The discussion above shows that $D_{1}(n)=n-1$ and $D_{2}(n)=n$. For
$D_{3}(n)$ we will provide a constructive proof of the following result.

######  Theorem 1.1.

For $n\geq 5$

$D_{3}(n)=n+2.$

However, there is an interesting change of behaviour that occurs when $i$ goes
from $3$ to $4$, and $D_{4}(n)$ is not of the form $n+O(1)$. In this paper we
will prove the following result.

######  Theorem 1.2.

$D_{4}(n)\geq\frac{5}{4}n-1.$

We also consider a stronger notion of convexity, namely $k$-convexity, which
was one of the main considerations of the paper [4].

######  Definition 1.3.

$S$ is called a $k$-convex set if $D_{1}(S)$ is a $(k-1)$-convex set. A convex
set is also called a $1$-convex set.

Let $\mathcal{S}^{2}(n)$ be the set of all $2$-convex sets of size $n$. Define

$D_{i}^{2}(n):=\min\\{|D_{i}(S)|:S\in\mathcal{S}^{2}(n)\\}.$

Note that $D_{1}^{2}(n)=n-1$. The set $S$ defined in (3) is a $2$-convex set
with $|D_{2}(S)|=n$, and it therefore follows that $D_{2}^{2}(n)=n$.

Similarly to Theorem 1.1 we will prove the following result.

######  Theorem 1.4.

For $n\geq 5$

(4) $D_{3}^{2}(n)=n+2.$

We give a slightly better lower bound for $D_{4}^{2}(n)$ than that for
$D_{4}(n)$ given in Theorem 1.2.

######  Theorem 1.5.

$D_{4}^{2}(n)\geq\frac{4}{3}n-\frac{4}{3}.$

We expect that the values of $D_{i}(n)$ and $D_{i}^{2}(n)$ increase with $i$.
However, we are not able to generalise the elementary techniques used to prove
Theorems 1.2 and 1.4 to obtain better bounds by considering larger $i$. On the
other hand, for sufficiently large $i$, incidence geometric techniques can be
used to give a non-trivial bound.

######  Theorem 1.6.

For all $i\in\mathbb{N}$,

$D_{i}(n)\gg i^{3/2}.$

In particular, if $i\geq n^{2/3+\epsilon}$, then Theorem 1.6 gives a lower
bound of the form $D_{i}(n)\gg n^{1+\epsilon^{\prime}}$. It appears plausible
that such a lower bound for $D_{i}(n)$ holds under the weaker assumption that
$i\geq n^{\epsilon}$.

##  2\. Proofs of the main results

###### Proof of Theorems 1.1 and 1.4.

To prove that $D_{3}(n)\geq n+2$, we need to prove that

(5) $|D_{3}(S)|\geq n+2$

holds for an arbitrary convex set $S$ with $|S|=n$. Observe that
$|D_{3}(S)|\geq|D_{2}(S)|+1$, since $s_{n}-s_{n-3}\in D_{3}(S)\setminus
D_{2}(S)$. Hence $|D_{3}(S)|\geq n+1$. Suppose for a contradiction that
$|D_{3}(S)|=n+1$ for some $n\geq 5$. Observe that

$s_{2}-s_{1}<s_{3}-s_{2}<s_{3}-s_{1}<s_{4}-s_{2}<s_{4}-s_{1}<s_{5}-s_{2}<\dots<s_{n}-s_{n-3}$

and

$s_{2}-s_{1}<s_{3}-s_{2}<s_{4}-s_{3}<s_{4}-s_{2}<s_{5}-s_{3}<s_{5}-s_{2}<\dots<s_{n}-s_{n-3}.$

We have identified two increasing sequences of length $n+1$ in $D_{3}(S)$, and
so the sequences must be identical. Comparing the third terms of the
sequences, we get

(6) $s_{4}-s_{3}=s_{3}-s_{1}$

and comparing the fifth terms of the sequences, we get

(7) $s_{4}-s_{1}=s_{5}-s_{3}.$

From equations (6) and (7) we get

$s_{5}-s_{4}=s_{3}-s_{1}=s_{4}-s_{3}.$

But as $S$ is a convex set this is not possible. Hence our assumption that
$|D_{3}(S)|=n+1$ was wrong, and so $|D_{3}(S)|\geq n+2$, proving (5).

Since every $2$-convex set is also convex, it follows that $|D_{3}(S)|\geq
n+2$ for all $2$-convex sets $S$. Therefore, $D_{3}^{2}(n)\geq n+2$.

To prove that $D_{3}(n)\leq n+2$ and $D_{3}^{2}(n)\leq n+2$, we provide an
example of a $2$-convex (and thus also convex) set with $|D_{3}(S)|=n+2$.
Consider the set $S=\\{s_{1},s_{2},\dots,s_{n}\\}$ where

$\displaystyle s_{1}=0,\,s_{2}=10,\,s_{3}=23,\,s_{4}=40,$ $\displaystyle
s_{i}:=a_{i-1}+s_{i-2}-s_{i-4}\,\,\,\,\text{for }i=5,\dots,n.$

Indeed, $|D_{3}(S)|=n+2$ and $S$ is $2$-convex.

∎

Taking a closer look at the construction of the set $S$ defined above, we see
that there is additional structure, as the set $D_{\\{5\\}}(S)$ overlaps
significantly with $D_{3}(S)$. To be precise, we have

$|D_{\\{1,2,3,5\\}}(S)|=n+4.$

Since the two largest elements of $D_{\\{1,2,3,5\\}}(S)$ are not in
$D_{3}(S)$, it follows from Theorem 1.1 that $D_{\\{1,2,3,5\\}}(S)\geq n+4$
for any convex set $S$, and so this construction is optimal in this regard.

###### Proof of Theorem 1.2.

To prove Theorem 1.2, we need to show that

(8) $|D_{4}(S)|\geq\frac{5}{4}n-1$

holds for an arbitrary convex set $S$ with size $n$. Indeed, let $S$ be such a
set. The proof of (8) is split into two cases.

Case 1 \- Suppose that $|D_{\\{2\\}}(S)\setminus
D_{\\{1\\}}(S)|\geq\frac{n}{4}-2$. It follows that

$|D_{4}(S)|\geq|D_{2}(S)|+2=|D_{\\{1\\}}(S)\cup[D_{\\{2\\}}(S)\setminus
D_{\\{1\\}}(S)]|+2\geq(n-1)+(n/4-2)+2=\frac{5n}{4}-1.$

Case 2 \- Suppose that $|D_{\\{2\\}}(S)\setminus D_{\\{1\\}}(S)|<n/4-2$. It
follows that

$s_{i+2}-s_{i},s_{i+3}-s_{i+1}\in D_{\\{1\\}}(S)$

holds for at least

$(n-3)-2(n/4-2)=\frac{n}{2}+1$

values of $i\in[n-3]$. Let $I$ be the set of all such $i$. Then, for all $i\in
I$,

$s_{i+2}-s_{i}=s_{j+1}-s_{j},\,\,\,\,s_{i+3}-s_{i+1}=s_{j^{\prime}+1}-s_{j},$

for some $j,j^{\prime}\in[n-1]$.

Case 2a \- Suppose that, for at least $\frac{n}{4}+2$ of the elements $i\in
I$, we have $j^{\prime}=j+1$. Then $s_{j+2}-s_{j}$ is in $D_{\\{2\\}}(S)$, but
it is also strictly between two consecutive elements of $D_{\\{4\\}}(S)$.
Indeed

$\begin{split}s_{i+3}-s_{i-1}&=(s_{i+3}-s_{i+1})+(s_{i+1}-s_{i-1})\\\
&<(s_{i+3}-s_{i+1})+(s_{i+2}-s_{i})\\\ &=(s_{j+2}-s_{j+1})+(s_{j+1}-s_{j})\\\
&=s_{j+2}-s_{j}\\\ &<(s_{i+4}-s_{i+2})+(s_{i+2}-s_{i})\\\
&=s_{i+4}-s_{i}.\end{split}$

It follows that $|D_{\\{2\\}}(S)\setminus D_{\\{4\\}}(S)|\geq\frac{n}{4}+2$.
Therefore,

$|D_{4}(S)|\geq
1+|D_{\\{2,4\\}}(S)|=1+|D_{\\{4\\}}(S)\cup[D_{\\{2\\}}(S)\setminus
D_{\\{4\\}}(S)]|\geq 1+n-4+\frac{n}{4}+2=\frac{5n}{4}-1.$

Case 2b \- Suppose that we are not in case 2a, and hence, for at least
$\frac{n}{4}-1$ of the elements of $I$, we have $j^{\prime}\geq j+2$. Then
$s_{j+2}-s_{j+1}$ lies strictly between two consecutive elements of
$D_{\\{2\\}}$, namely $s_{i+2}-s_{i}$ and $s_{i+3}-s_{i+1}$. Therefore,
$|D_{\\{1\\}}(S)\setminus D_{\\{2\\}}(S)|\geq\frac{n}{4}-1$, and thus

$|D_{4}(S)|\geq|D_{2}(S)|+2=|D_{\\{2\\}}(S)\cup[D_{\\{1\\}}(S)\setminus
D_{\\{2\\}}(S)]|+2\geq(n-2)+(n/4-1)+2=\frac{5n}{4}-1.$

∎

A closer look at the proof of Theorem 1.2 reveals that we have barely used the
elements of $D_{\\{3\\}}(S)$ anywhere in the proof of (8). By modifying the
proof slightly, we obtain the bound

$|D_{\\{1,2,4\\}}(S)|\geq\frac{5}{4}n-2$

for any convex set $S$ with cardinality $n$.

The construction of the set $S$ from Theorem 1.1 yields the bound

$|D_{4}(S)|\leq|D_{3}(S)|+(n-4)=2n-2.$

Combining this observation with the result of Theorem 1.2, we see that

$\frac{5}{4}n-1\leq D_{4}(n)\leq 2n-2.$

We now proceed to the proof of Theorem 1.5. The proof is largely the same as
that of Theorem 1.2. The main difference is that we can use the $2$-convex
condition to show that Case 2b does not occur.

###### Proof of Theorem 1.5.

To prove Theorem 1.5, we need to show that

(9) $|D_{4}(S)|\geq\frac{4}{3}n-\frac{4}{3}$

holds for an arbitrary $2$-convex set $S$ with size $n$. Indeed, let $S$ be
such a set. The proof is split into two cases.

Case 1 \- Suppose that $|D_{\\{2\\}}(S)\setminus
D_{\\{1\\}}(S)|\geq\frac{n}{3}-\frac{7}{3}$. It follows that

$|D_{4}(S)|\geq|D_{2}(S)|+2=|D_{\\{1\\}}(S)\cup[D_{\\{2\\}}(S)\setminus
D_{\\{1\\}}(S)]|+2\geq(n-1)+\left(\frac{n}{3}-\frac{7}{3}\right)+2=\frac{4}{3}n-\frac{4}{3}.$

Case 2 \- Suppose that $|D_{\\{2\\}}(S)\setminus
D_{\\{1\\}}(S)|<\frac{n}{3}-\frac{7}{3}$. It follows that

$s_{i+2}-s_{i},s_{i+3}-s_{i+1}\in D_{\\{1\\}}(S)$

holds for at least

$(n-3)-2\left(\frac{n}{3}-\frac{7}{3}\right)=\frac{n}{3}+\frac{5}{3}$

values of $i\in[n-3]$. Let $I$ be the set of all such $i$. Then, for all $i\in
I$,

$s_{i+2}-s_{i}=s_{j+1}-s_{j},\,\,\,\,s_{i+3}-s_{i+1}=s_{j^{\prime}+1}-s_{j},$

for some $j,j^{\prime}\in[n-1]$ satisfying $j^{\prime}>j>i$. We claim now that
it must be the case that $j^{\prime}=j+1$. Indeed, suppose for a contradiction
that $j^{\prime}\geq j+2$. It then follows that

$\displaystyle(s_{j+3}-s_{j+2})-(s_{j+1}-s_{j})$
$\displaystyle\leq(s_{j^{\prime}+1}-s_{j^{\prime}})-(s_{j+1}-s_{j})$
$\displaystyle=(s_{i+3}-s_{i+1})-(s_{i+2}-s_{i})$
$\displaystyle=(s_{i+3}-s_{i+2})-(s_{i+1}-s_{i}).$

However, since $j>i$, this contradicts the assumption that $S$ is $2$-convex.
Indeed, write the convex set $D_{1}(S)=\\{d_{1}<d_{2}<\dots<d_{n-1}\\}$, and
so $d_{i}=s_{i+1}-s_{i}$. Then the previous inequality can be written as

$d_{j+2}-d_{j}\leq d_{i+2}-d_{i}.$

But this inequality cannot hold if $D_{1}(S)$ is convex, which proves the
claim.

As was the case in the proof of Theorem 1.2, $s_{j+2}-s_{j}$ is in
$D_{\\{2\\}}(S)$, but it is also strictly in-between two consecutive elements
of $D_{\\{4\\}}(S)$. Indeed

$\begin{split}s_{i+3}-s_{i-1}&=(s_{i+3}-s_{i+1})+(s_{i+1}-s_{i-1})\\\
&<(s_{i+3}-s_{i+1})+(s_{i+2}-s_{i})\\\ &=(s_{j+2}-s_{j+1})+(s_{j+1}-s_{j})\\\
&=s_{j+2}-s_{j}\\\ &<(s_{i+4}-s_{i+2})+(s_{i+2}-s_{i})\\\
&=s_{i+4}-s_{i}.\end{split}$

It follows that $|D_{\\{2\\}}(S)\setminus
D_{\\{4\\}}(S)|\geq\frac{n}{3}+\frac{5}{3}$. Therefore,

$|D_{4}(S)|\geq
1+|D_{\\{2,4\\}}(S)|=1+|D_{\\{4\\}}(S)\cup[D_{\\{2\\}}(S)\setminus
D_{\\{4\\}}(S)]|\geq 1+n-4+\frac{n}{3}+\frac{5}{3}=\frac{4}{3}n-\frac{4}{3}.$

∎

We now turn to the proof of Theorem 1.6, which is a modification of the proof
of the main result in [2].

###### Proof of Theorem 1.6.

Let $S=\\{s_{1}<\dots<s_{n}\\}$ be a convex set. We will prove that

$D_{i}(S)\gg i^{3/2}.$

Since $S$ is convex, it follows that there exists a strictly convex function
$f:\mathbb{R}\rightarrow\mathbb{R}$ such that $f(i)=s_{i}$.

Define $P$ to be the point set

$P=\\{-n,-n+1,\dots,n-1,n\\}\times D_{i}(S).$

Let $\ell_{a,b}$ denote the curve with equation $y=f(x+a)-b$. Define $L$ to be
the set of curves

$L=\\{\ell_{j,s_{h}}:1\leq j\leq n,1\leq h\leq n/2\\}.$

The set $L$ consists of translates of the same convex curve, and it therefore
follows that we have the Szemerédi-Trotter type bound

(10) $I(P,L)\ll|P|^{2/3}|L|^{2/3}+|P|+|L|,$

where

$I(P,L):=\\{(p,\ell)\in P\times L:p\in\ell\\}.$

For each $\ell_{j,s_{h}}\in L$, and for any $k$ such that $1\leq k-h\leq i$,
observe that

$(k-j,s_{k}-s_{h})\in P\cap\ell_{j,s_{h}}.$

This implies that $I(P,L)\gg|L|i\gg n^{2}i$. Comparing this bound with (10)
yields

$n^{2}i\ll n^{2}|D_{i}(S)|^{2/3}+n|D_{i}(S)|+n^{2}.$

If the third term on the right hand side is dominant then $i=O(1)$ and Theorem
1.6 holds trivially. If the second term is dominant then we have

$|D_{i}(S)|\gg ni\geq i^{3/2}.$

If the third term is dominant then we obtain the stated bound

$|D_{i}(S)|\gg i^{3/2}.$

∎

By making a small modification to the proof of Theorem 1.6, one can prove
that, for any $G\subset[n]\times[n]$,

(11) $|\\{s_{x}-s_{y}:(x,y)\in G\\}|\gg\left(\frac{|G|}{n}\right)^{3/2}.$

Similar sum-product type results for restricted pairs have been considered in,
for instance, [1] and [5]. Note that the bound in (11) becomes meaningful when
$|G|$ is significantly larger than $n$. A construction of a convex set with a
rich difference in [6] shows that the set $\\{s_{x}-s_{y}:(x,y)\in G\\}$ can
have cardinality as small as one when $G$ has cardinality as large as $n/2$.

##  3\. Concluding remarks

###  3.1. Sums instead of differences

One may also consider a version of this question with sums. Let $E_{i}(S)$
denote the set

$E_{i}(S)=\\{s_{x}+s_{y}:1\leq x-y\leq i\\}.$

However, it turns out that this modification to the question makes it rather
straightforward to prove a non-trivial bound that grows with $i$. If we split
$S$ into disjoint consecutive blocks $S_{1}\cup S_{2}\cup\dots\cup S_{t}$,
with each block having $i$ elements (we possibly discard some elements to
ensure that all blocks have exactly the same size, and so $t=\lfloor
n/i\rfloor$), then the sum sets $S_{j}+S_{j}$ are pairwise disjoint. It then
follows from the lower bound for $S_{j}+S_{j}$ given in (1) that

$|S+S|\geq\sum_{j=1}^{t}|S_{j}+S_{j}|\gg\frac{n}{i}\cdot\frac{i^{30/19}}{(\log
n)^{c}}=\frac{ni^{11/19}}{(\log n)^{c}}.$

###  3.2. Sets $\mathcal{I}$ such that $D_{\mathcal{I}}=n+O(1)$

In Theorem 1.1, we have seen that $D_{\\{1,2,3\\}}(n)=n+2$. There are other
examples of sets $\mathcal{I}\subset[n-1]$ with cardinality 3 such that
$D_{\mathcal{I}}(n)=n+O(1)$. For example, we can define $S$ using the
recurrence relation

$s_{n}=s_{n-2}+s_{n-3}-s_{n-6}.$

By choosing the initial elements of $S$ suitably, the set $S$ is convex.
However, this recurrence relations gives rise to the system of equations

$s_{j}-s_{j-2}=s_{j-3}-s_{j-6}=s_{j-5}-s_{j-9},\,\,\,\,\forall\,\,10\leq j\leq
n.$

This implies that the elements of $D_{\\{2\\}}(S),D_{\\{3\\}}(S)$ and
$D_{\\{4\\}}(S)$ are largely the same, with just a few exceptions occurring at
the extremes of the three sets. It follows that $D_{\\{2,3,4\\}}(S)=n+C$, for
some absolute constant $C$. It appears likely that the same argument can be
used to show that $D_{\\{k,k+d,k+2d\\}}(n)=n+O_{k,d}(1)$.

On the other hand, we have seen in this paper that
$D_{\\{1,2,4\\}}(n)=\frac{5n}{4}-O(1)$. This raises the following question:
can we classify the sets $\mathcal{I}$ with cardinality $3$ with the property
that $D_{\mathcal{I}}(n)=n+C$, where $C$ is some constant (which may depend on
the elements of $\mathcal{I}$)?

## Acknowledgements

The authors were supported by the Austrian Science Fund FWF Project P 34180.
Part of this work was carried out while the second author was doing an
internship supported by FFG Project 895224 - JKU Young Scientists. We are
grateful to Audie Warren and Dmitrii Zhelezov for helpful discussions.

## References

  * [1] N. Alon, I. Z. Ruzsa and J. Solymosi, ‘Sums, products, and ratios along the edges of a graph’, Publ. Mat. 64 (2020), no. 1, 143-155.
  * [2] G. Elekes, M. Nathanson and I. Ruzsa, ‘Convexity and sumsets’, J. Number Theory. 83 (1999), 194-201.
  * [3] M. Z. Garaev, ‘On lower bounds for the $L_{1}$-norm of some exponential sums’, Mat. Zametki 68 (2000), no. 6, 842-850.
  * [4] B. Hanson, O. Roche-Newton and M. Rudnev, ‘Higher convexity and iterated sum sets’, Combinatorica 42 (2022), no. 1, 71-85.
  * [5] O. Roche-Newton, ‘Sums, products, and dilates on sparse graphs’, SIAM J. Discrete Math. 35 (2021), no. 1, 194-204.
  * [6] O. Roche-Newton and A. Warren, ‘A convex set with a rich difference’, Acta Math. Hungar. 168 (2022), no. 2, 587-592.
  * [7] M. Rudnev and S. Stevens, ‘An update on the sum-product problem’, Math. Proc. Camb. Phil. Soc. 173 (2022), no. 2, 411-430.
  * [8] I. Z. Ruzsa, G. Shakan, J. Solymosi and E. Szemerédi, ‘On distinct consecutive differences’, Combinatorial and additive number theory IV 425-434, Springer Proc. Math. Stat., 347, Springer, Cham, (2021).
  * [9] I. Z. Ruzsa and J. Solymosi, ‘Sumsets of semiconvex sets’, Canad. Math. Bull. 65 (2022), no. 1, 84-94.
  * [10] T. Schoen and I. Shkredov, ‘On sumsets of convex sets’, Combin. Probab. Comput. 20 (2011), no. 5, 793-798.


# Limitations of Agents Simulated by Predictive Models

Raymond Douglas  Jacek Karwowski  Chan Bae  Andis Draguns  Victoria Krakovna

###### Abstract

There is increasing focus on adapting predictive models into agent-like
systems, most notably AI assistants based on language models. We outline two
_structural_ reasons for why these models can fail when turned into agents.
First, we discuss _auto-suggestive delusions_. Prior work has shown
theoretically that models fail to imitate agents that generated the training
data if the agents relied on hidden observations: the hidden observations act
as confounding variables, and the models treat actions they generate as
evidence for nonexistent observations. Second, we _introduce_ and _formally
study_ a related, novel limitation: _predictor-policy incoherence_. When a
model generates a sequence of actions, the model’s implicit prediction of the
policy that generated those actions can serve as a confounding variable. The
result is that models choose actions as if they expect future actions to be
suboptimal, causing them to be overly conservative. We show that both of those
failures are fixed by including a feedback loop from the environment, that is,
re-training the models on their own actions. We give simple demonstrations of
both limitations using Decision Transformers and confirm that empirical
results agree with our conceptual and formal analysis. Our treatment provides
a unifying view of those failure modes, and informs the question of _why_
fine-tuning offline learned policies with online learning makes them more
effective.

Machine Learning, ICML

##  1 Introduction

Figure 1: Agents derived from predictive models might fail because of causal
confounding, but fine-tuning on their own output addresses those issues.

Machine learning research is increasingly focused on adapting predictive
models into agent-like systems, most notably AI assistants based on language
models (OpenAI, 2022; Richards, 2023). To a remarkable degree, these models
develop greater and more varied capabilities as the model and dataset size are
increased (Radford et al., 2019; Wei et al., 2022; Bai et al., 2022; Brown et
al., 2020). We investigate what properties of the training data and the
process of deriving the policy from the predictive model might make the
eventual agent-like system fail to take good actions, even if the model is as
good as possible.

What we meant by a _predictive model_ here is a model that is trained on a
given dataset in a supervised way. In contrast, by _an agent_ we mean an
entity acting in the world, in a reinforcement-learning-like setup. An agent
can be induced from a predictive model by taking whatever action the model
predicts a (capable) agent would take. For example, a model that can predict
the moves of a real chess Grandmaster can also be used to generate novel
moves, and therefore can serve as a chess-playing agent. However, it turns out
that in most cases, the ability of a model to predict a capable expert does
not yield a comparatively capable induced agent.

Ortega et al. (2021) discuss one such problem, that of _auto-suggestive
delusions_. When a model is trained to predict agents that take a sequence of
actions based on a latent state, it can correctly learn to use the agents’
actions to infer the hidden observations. However, when that same model is
used to generate a sequence of actions, it must also effectively simulate the
hidden observations without having access to them. Because of this, it will
incorrectly use the actions it generated to infer the latent state. The result
is that the simulated agent seems to act as if it had made observations it did
not make.

Our key insight is that a variation of this issue can emerge around the
identity of the agent. Predictive models trained on a variety of agents
correctly learn that an agent’s current actions provide evidence about which
agent is taking the actions, and therefore what their future actions will be.
However, when the predictive model is used to simulate the agent, this becomes
a problem. In case of auto-suggestive delusions, the agent acts as if it had
made nonexistent observations. We use the term ‘predictor-policy incoherence’
to describe the phenomenon of agents which act as if they expect their future
actions to be chosen by a less competent agent. The result is that simulated
agents will sometimes unnecessarily avoid strategies which require them to
make several good moves in succession.

Crucially, the limitations we describe do not result from the model’s failure
to predict the data it was trained on, so unlike many other limitations, they
cannot be resolved by training a larger model on more examples of the same
data. This is because the structure of the data itself is what causes the
model to simulate agents which are effectively systematically incorrect about
the consequences of their own actions, and their own future actions.

However, we argue that both auto-suggestive delusion and predictor-policy
incoherence _can_ be, and indeed, often _are_ resolved by fine-tuning the
model on data generated by its own simulated agents. This process of further
training models on their own outputs is central to many of the current
techniques used to turn base predictive LMs into helpful assistants, like
Reinforcement Learning from Human Feedback (RLHF) (Bai et al., 2022), or
variants like Reinforced Self-Training (ReST) (Gulcehre et al., 2023). Our
results give one mechanism by which such processes might improve capabilities:
reducing auto-suggestive delusions and predictor-policy incoherence (Figure
1).

This is the groundwork for a better understanding of how the capacity to
optimise for a goal emerges in systems built on generative models. To
demonstrate the presence of these limitations and the efficacy of fine-tuning,
we focus on simple models trained on synthetic datasets with clear rewards. We
are optimistic that our results can be eventually extended to settings where
these limitations are harder to quantify, such as using LMs as agent-like
systems.

More generally, we want to understand how ML systems might give rise to
superhuman agents. Recent work (Carlsmith, 2022; Ngo et al., 2022) has
highlighted the incentives towards building agentic and goal-directed systems
(because of their general utility), and the associated difficulty of reliably
specifying desirable goals. Our results show how agents simulated by offline
self-supervised generative models will face limitations even at scale, and how
these limitations might be overcome.

###  1.1 Contributions

We develop a framework to describe the ways a generative model can fail to
simulate a successful agent: auto-suggestive delusions and predictor-policy
incoherence (Section 3). Our analysis helps to explain how previously known
techniques involving re-training models on their own outputs address those
limitations. Specifically:

  * •

We introduce (Example 2) and formally define (Definition 3.5) _predictor-
policy incoherence_ , which can be intuitively understood as the inability of
the simulated agent to reason about _its own_ policy being used in future
situations beyond a short horizon (Section 3.2).

  * •

We prove that repeated re-training predictive models on their own actions
decreases predictor-policy incoherence and eliminates auto-suggestive
delusions, which makes the resulting agents converge, in the limit, on optimal
policies (Section 3.3).

  * •

By training Decision Transformers on simple games using synthetic data, we
demonstrate goal-conditioned generative models that display auto-suggestive
delusions and predictor-policy incoherence. We show that re-training those
models on their own outputs indeed leads to models simulating agents with
policies that exhibit fewer auto-suggestive delusions and are more coherent
with respect to the generative model (Section 4).

|  Auto-suggestive delusion |  Predictor-policy incoherence
---|---|---
Confounded about |  Past environment’s latent state |  Future agent’s policy
Desired answer |  Action providing evidence about the outcome |  Action providing evidence about the reward
Computed answer |  Action providing evidence about the latent state that provides evidence about the outcome |  Action providing evidence about the hidden policy that provides evidence about the reward
Measure |  $D_{KL}(p(a|o)||p(a))$ |  $D_{KL}(p(a|R)||p(a))$
Figure 2: The analogies and differences between two modes of causal
confounding.

##  2 Related Work

###  2.1 Agents as conditioned generative models

There has been substantial work in the existing literature on using
conditioned generative models to obtain agents. Chen et al. (2021) introduce
the Decision Transformer, which samples actions autoregressively from a goal-
conditioned generative model. They demonstrate its efficacy in simple games
and note how its performance varies based on the conditioned return. We study
their model abstractly, and our theoretical analysis informs the discussion
about the limitations of this approach. There have been successful attempts to
steer language models by pretraining on data with reward signals on which the
model can be conditioned (Korbak et al., 2023).

###  2.2 Control as inference in reinforcement learning

In reinforcement learning, the process of deriving policies from goal-
conditioned generative models is studied as the theory of  _control as
inference_ (Levine, 2018). Forming the prior by offline learning improves
sample complexity; methods such as _soft Q-learning_ (Haarnoja et al., 2017)
and _Soft Actor Critic_ (Haarnoja et al., 2018) had been developed to address
issues arising in goal-conditioning of the generative action models, but had
seen limited success in generative language models. KL-penalised reinforcement
learning (Todorov, 2006), applied to language models by Korbak et al. (2022),
and Active Inference (Parr et al., 2022) over Markov Decision Processes
(Millidge et al., 2020) can be seen as equivalent formulations of the control
as inference theory.

###  2.3 Self-play in reinforcement learning

Self-play is a widely used and often successful strategy for training
reinforcement learning agents (Macleod, 2005; Silver et al., 2018; OpenAI et
al., 2019; Vinyals et al., 2019), where an agent recursively self-improves by
playing against or together with a copy of itself. In the context of language
models, self-play was suggested to be useful in the debate protocol (Irving et
al., 2018). We contrast self-play with the concept of re-training the model on
its own outputs discussed in this work, which does not rely on the multi-
player nature of a game, but rather removes the confounding information from
the prior. Updating the policy using Monte Carlo Tree Search-based methods is
a well-known solution for achieving super-human game performance (Silver et
al., 2017), which can be seen as addressing the predictor-policy incoherence
problems we study here.

###  2.4 Predictive models as simulators

Shanahan et al. (2023) argue that many intuitive features of language model
agents are best understood by viewing language models as general ‘simulators’
capable of role-playing different agents. They particularly emphasise that
what is simulated is not a single agent but a superposition: a weighted
combination of all agents consistent with the prior context. It has been
argued that this description fits LLMs, where the training corpus comes from
agents being humans, whose actions are recorded on the internet (Andreas,
2022), We advance this point of view by giving a theoretical framework for
generative models trained on a distribution of agent policies, and demonstrate
that those results are supported by empirical data.

###  2.5 Limitations of agents simulated by sequence models

Ortega et al. (2021) provide a formal explanation of auto-suggestive delusions
and confounding in sequence models by reasoning about predicted actions in
terms of causality for simple probabilistic models. The same problem was
previously described by Zhang et al. (2020) in the context of imitation
learning. Ortega et al. (2021) also provide a solution based on counterfactual
training, which requires the presence of an expert with access to hidden
observations. We extend their work by introducing and developing the
complementary problem of predictor-policy incoherence, and demonstrating
empirically how both problems can be overcome by sufficient training on
environmental interactions. This both shows that the problem can be fixed
without an expert to assist in training and reveals how the problem might be
affected by models receiving further training on their own outputs.

##  3 Characterising Failures of Simulated Agents

In this section, we develop a framework to describe the ways a predictive
model can fail to simulate a successful agent. To simulate an agent that is
pursuing a specific goal such as getting a reward, the predictive model is
trained to predict the next token in sequences corresponding to trajectories
that are a series of observations and actions taken by agents. The predictive
model is then conditioned on the reward being obtained. This is achieved by
the first token being fixed to a value indicating that the trajectory leads to
the reward. When we query a predictor that is goal conditioned in this way for
an action, intuitively we are querying it for what _action is likely to be
observed_ conditional on the goal. Crucially, the policy assembled from this
is not necessarily the _policy to intervene with_ to have the highest
probability of reaching the goal. The two main ways the simulated agent’s
policy and the optimal policy come apart are _auto-suggestive delusions_ and
_predictor-policy incoherence_ (Figure 2).

Auto-suggestive delusions might appear when the predictor is trained on agents
taking actions based on a hidden variable, i.e. one that does not appear in
the training data. After predicting an action under this uncertainty, in the
next time step, the predictor observes that this action was taken. From this,
it makes inaccurate inferences about the latent state and its downstream
consequences.

Predictor-policy incoherence might appear when the training data contains
(rare) samples from an optimal policy alongside (much more common) samples
from a highly suboptimal policy. If those policies start with the same action,
that initial action mostly provides evidence of the highly suboptimal policy
being used. The predictor then correctly predicts that taking such an action
is evidence of a bad outcome, even though the optimal policy would take the
action.

###  3.1 Auto-suggestive delusions

In this subsection, we introduce auto-suggestive delusions. For a more
thorough treatment of this issue, see Ortega et al. (2021). The following
example and accompanying Figure 3 illustrate the problem.

######  Example 1 (Stock trader).

We consider a situation with:

  * •

An expert that successfully trades stock based on some latent state (such as
its own intuition, or a non-public data source).

  * •

A predictive model trained on a dataset of trajectories of that agent’s
actions without the latent state.

  * •

The predictive model’s simulation of the expert, constructed by sampling
actions according to the model predictions.

The expert is able to tell if a stock is about to go up or down, and so it
simply takes whichever action leads to a profit. There are only two possible
trajectories: $(s_{\text{up}},a_{\text{buy}},s_{\text{profit}})$ \- where the
stock is about to go up, the expert buys stock, and profits - and
$(s_{\text{down}},a_{\text{sell}},s_{\text{profit}})$ \- the opposite, where
$a$ denotes expert’s actions and $s$ denotes states. If we were to train a
predictive model on these trajectories, it would be able to easily simulate
the expert: it would be able to perfectly predict what actions will follow
from the starting states, and what states will follow from those actions.

But now suppose we tried to train a model on only partial observations of the
scenario. Specifically, suppose that the model makes the observation
$o_{\text{profit}}$ in the state $s_{\text{profit}}$, and $o_{\text{loss}}$ in
$s_{\text{loss}}$, but that it cannot distinguish between $s_{\text{up}}$ and
$s_{\text{down}}$, observing $o_{\text{before}}$ in both cases. So the model
observes two trajectories
$(o_{\text{before}},a_{\text{buy}},o_{\text{profit}})$ and
$(o_{\text{before}},a_{\text{sell}},o_{\text{profit}})$.

The first consequence of this is that the model can no longer perfectly
predict how trajectories will evolve. Supposing $s_{\text{up}}$ and
$s_{\text{down}}$ are equally likely, starting at $o_{\text{before}}$ the
model will assign equal probability to $a_{\text{buy}}$ and $a_{\text{sell}}$.
However, it can still correctly predict that after observing the expert take
the action $a_{\text{buy}}$ or $a_{\text{sell}}$, it will observe
$o_{\text{profit}}$, because this is always true of the expert agent.

If we have the model try to simulate the expert trader, the simulated trader
will perform worse: it lacks the real expert’s observations, and so it is
equally likely to reach $s_{\text{profit}}$ and $s_{\text{loss}}$.

The confounding emerges when we have the model autoregressively simulate the
expert. When the expert takes the action $a_{\text{buy}}$, this provides
evidence that the initial state was $s_{\text{up}}$ and therefore that the
next state will be $s_{\text{profit}}$. But when the model simulates this
action, it no longer provides such evidence. However, since the model was
trained on the expert, it will always predict that any action it takes will
lead to $s_{\text{profit}}$.

Figure 3: A diagram of the Stock trader example. States are represented in
blue; observations are in orange; lines represent actions and associated
transitions. Dotted lines are transitions which the expert is never observed
to take. The agent simulated by the model then falls into auto-suggestive
delusion: since it doesn’t distinguish between the starting states, it
believes it gets profit no matter what action it takes.

In the context of LLMs, this problem can appear because of the model treating
its previously generated tokens as evidence for states that are not directly
observed. A concrete example would be the model answering a question about a
research paper and, being uncertain about the author, randomly guessing that
it was ‘Maxwell’. In the next autoregressive step, the model receives a
sequence containing its own output - text claiming that Maxwell is the author.
This can lead to the model incorrectly inferring that Maxwell is in fact the
author, which manifests as doubling down on the hallucinated fact in later
token predictions. In this setting, the expert policies correspond to the
people who wrote the training text corpus while in part relying on information
that is not directly accessible to the predictor.

###  3.2 Predictor-Policy Incoherence

We begin with a simple demonstration of the problem, followed by a formal
characterisation.

Start$\diamondsuit$$\heartsuit$$\diamondsuit\diamondsuit$$\diamondsuit\heartsuit$$\heartsuit\diamondsuit$$\heartsuit\heartsuit$$\diamondsuit\diamondsuit\diamondsuit$$\diamondsuit\diamondsuit\heartsuit$$\diamondsuit\heartsuit\diamondsuit$$\diamondsuit\heartsuit\heartsuit$$\heartsuit\diamondsuit\diamondsuit$$\heartsuit\diamondsuit\heartsuit$$\heartsuit\heartsuit\diamondsuit$$\heartsuit\heartsuit\heartsuit$1000$\frac{1}{2}$$\frac{1}{2}$$\frac{1}{2}$$\frac{1}{2}$
Figure 4: Representation of possible trajectories in the three cards game. The
bottom row represents the probability of reward $P(R)$ in each end state. The
bolded line is the optimal strategy.

######  Example 2 (Three cards game).

We consider a _three cards game_ where, in each of three consecutive rounds,
an agent has to choose either $\diamondsuit$ or $\heartsuit$ card. At the end
of the game, if the sequence of cards consists of three $\diamondsuit$, the
payoff is 1; if the chosen sequence starts with $\heartsuit$, the payoff is 1
with probability $\frac{1}{2}$; otherwise, it is 0. The possible trajectories
are illustrated in Figure 4.

The choice made in the first round of the game largely dictates the payoff. If
the agent chooses $\heartsuit$, its expected reward is $\frac{1}{2}$
regardless of its later moves. If the agent chooses $\diamondsuit$, it has the
potential to guarantee a reward of $1$ or $0$, but that reward will depend on
the agent’s later choices.

Suppose that we train a predictive model on a set of agents which play
entirely randomly, and are equally likely to choose $\diamondsuit$ or
$\heartsuit$ on any turn. The predictive model will correctly predict that,
when observing the random agents it was trained on,
$P(\diamondsuit|R)=\frac{1}{3}$, and $P(\heartsuit|R)=\frac{2}{3}$: most
successful agents choose $\heartsuit$ first, even though the optimal strategy
chooses $\diamondsuit$. So if we attempt to simulate an agent using this
predictive model, it will not play optimally, even though the predictive model
itself is optimal with respect to its training data.

Crucially, the simulated agent will play $\heartsuit$ instead of
$\diamondsuit$ because agents in the training data perform better on average
after playing $\heartsuit$, even though this is not true of the simulated
agent itself. Starting from $\diamondsuit$, the simulated agent will always
play optimally, but most of the agents it was trained on would not play
optimally. The simulated agent assigns probability based on how the agents in
its training data would behave, not based on how it would behave. It is again
confounded, this time not by a hidden observation but by its prediction of the
latent policy governing the agent it is simulating.

We use the term ‘predictor-policy incoherence’ to refer to the distinction
between the predictive model’s prediction of the performance of an average
agent, and the performance of its own simulated agent which has been
conditioned on some outcome.

###  3.3 Fine-tuning on simulated agents

Here we outline how the limitations we described are resolved by fine-tuning a
predictive model on its own simulated agents.

Formally, we work with a fixed Markov Decision Process (MDP) $M$ with a finite
time horizon $T$, a finite set of states $S$ and set of actions $A$, a chosen
starting state $s_{1}$, a transition kernel $\tau(s_{t+1}|a_{t},s_{t})$, and a
binary random variable $R$ defining the (stochastic) reward function, with
distribution $p(R|s_{T},a_{T})$ depending only on the final state and action.
We let $\Pi$ denote the space of (Markov) policies on $M$ of a shape
$\pi(a_{t}|s_{t})$ for $t\in\\{1,\ldots T\\}$.

####  3.3.1 Predictor-Policy Incoherence

######  Definition 3.1.

Each policy $\pi(a_{t}|s_{t})$ over the MDP defines the joint probability
distribution over trajectories and rewards:

$\displaystyle p_{\pi}(s_{1:T},$ $\displaystyle a_{1:T},R)=$
$\displaystyle\left(\prod_{t=1}^{T-1}\pi(a_{t+1}|s_{t+1})\tau(s_{t+1}|a_{t},s_{t})\right)p(R|a_{T},s_{T})$

######  Definition 3.2.

We define the return operator $J(\pi):\Pi\to\mathbb{R}$ on the space of
policies on $M$ as the expectation of the reward:

$J(\pi)=\mathbb{E}_{a_{1:t},s_{1:T}}[R(s_{t},a_{t})]$

We note that since the reward is assumed to be binary and only given at the
end of a trajectory, this is equivalent to simply marginalising out
$J(\pi)=p_{\pi}(R=1)$.

######  Definition 3.3.

We say that a policy $\pi(a_{t}|s_{t})$ _improves on_ a policy
$\pi(a_{t}|s_{t})$ if we have the inequality $J(\pi^{*})\geq J(\pi)$. We say
that a policy $\pi^{*}$ is _optimal_ if it improves on all other policies.

######  Definition 3.4.

We define the goal-conditioning operator $\mathcal{G}(\pi):\Pi\to\Pi$ on the
space of policies on $M$ as:

$\mathcal{G}(\pi)(a_{t}|s_{t})=p_{\pi}(a_{t}|s_{t},R=1)$

Thus, the operator $\mathcal{G}$ together with a starting policy $\pi_{0}$
defines a sequence of policies
$\pi_{1}=\mathcal{G}(\pi_{0}),\pi_{2}=\mathcal{G}(\pi_{1})$ and so on. We will
use the notation $p_{i}=p_{\pi_{i}}$ for convenience. We treat $\mathcal{G}$
as performing the operation of _re-training the model on its own actions_ :
conceptually, it can be imagined as collecting roll-outs from the current
policy, and sampling only those that resulted in the reward.

######  Definition 3.5.

We define the _incoherence_ $\kappa(\pi)$ of a policy $\pi(a_{t}|s_{t})$ with
full support as:

$\kappa(\pi)=\sum_{s\in S}D_{KL}(\mathcal{G}(\pi)(a|s)||\pi(a|s))$

If the policy $\pi_{0}$ has full support over the set of actions $A$ in all
states $S$, iterating the operator $\mathcal{G}(\pi)$ gives an optimal policy.

######  Theorem 3.6.

There exists some optimal policy $\pi^{*}(a|s)$, such that the sequence of
policies $\pi_{k}(a_{t}|s_{t})$ converges to $\pi^{*}$ in $KL$-distance:

$\lim_{k\to\infty}D_{KL}(\pi^{*}||\pi_{k})=0$

where $\pi_{k}=\mathcal{G}(\pi_{k-1})=\mathcal{G}^{k}(\pi_{0})$.

The proof of the above can be found in Appendix A.

######  Corollary 3.7.

The incoherence of the policy diminishes as it is iteratively updated by
repeated goal-conditioning operator $\mathcal{G}$:

$\lim_{k\to\infty}\kappa(\pi_{k})=0$

This implies that if we iteratively fine-tune a goal-conditioned predictive
model on its own simulated agents, we eventually remove the predictor-policy
incoherence, leaving us with simulated agents at least as likely to achieve
the goal as any agents in the original training data.

####  3.3.2 Delusion

A stronger property holds for the case of observational confounding and auto-
suggestive delusion. Auto-suggestive delusion occurs when the model learns to
infer a hidden state $o$ from an action $a$ even though the action is
independent of the observation.

######  Definition 3.8.

We define the delusion between a predictive model $p(a)$ and a unconfounded
policy $p(a|s)$ to be:

$\lambda(p)=D_{KL}(p(a|s)||p(a))$

When we train a predictive model on data from $p$ without exposing it to the
latent state $s$, it induces a policy $p(a)$, giving delusion if $p(a)\neq
p(a|o)$. The delusion is, in this case, trivially removed if we re-train on
the $p(a|o)$ (for the details, see Appendix D). However, in practice, this
strategy of first (offline) training on $p(a)$ and only later (online) fine-
tuning on the correct distribution has the advantage of greater sample
efficiency. The model has a chance to learn the structure of the task (such as
the rules of a game, grammar of the language etc), which is data-intensive,
and to remove the delusion cheaply later. For a demonstration, see the
experiment in Section 4.1.

##  4 Experiments and Results

Figure 5: The _Padlock game_ involves an agent trying to open a padlock with a
15-bit code (for presentation, we limit this to 5 bits here). The first three
are always the same; the last two are randomised. The agent offline learns
from a dataset of expert plays, who know the combination and get it right on
the first try. The agent correctly sets first three bits, however, it does not
know the combination, and only deludes itself into thinking that it solved the
game.

We have claimed that auto-suggestive delusions and predictor-policy
incoherence are closely related limitations of agents simulated by goal-
conditioned predictive models. We perform two experiments, which demonstrate
empirically that fine-tuning the models on its simulated agents alleviates
both of those problems.

###  4.1 Reducing auto-suggestive delusions by training a model on its output

####  4.1.1 Experimental design

To understand how auto-suggestive delusions are affected by fine-tuning a
model on its own outputs, we deliberately construct a scenario where the
simulated agent will be affected by auto-suggestive delusions.

We implement a delusion measure to estimate the degree to which an agent is
suffering from auto-suggestive delusions. Specifically, we use KL divergence
between the assigned probabilities of the next observation indicating a solved
lock and the true distribution (as in Definition 3.8).

We create a simple _Padlock game_ where a player opens a padlock made up of 15
binary switches which need to be set to a secret target configuration - a
15-bit secret code. The switches start in a random configuration, and with
each turn, the player can flip one switch. Once the switches match the secret
code, the padlock opens. We offline train the model on a dataset of
trajectories from the game. In each trajectory, the first ten bits of the code
remain unchanged while the last five bits of the target configuration are
randomised. In this way, the predictive model is at best able to learn the
first ten bits of the correct code, but not the last five (see Figure 5).

In the training data, the experts always know exactly what the full correct
code is, including the last five bits. Therefore it takes them a maximum of 15
moves to put the switches into the target configuration.

The learned predictor can infer the target configuration for the first 10
levers but not for the last 5 as that is determined by a latent state that is
only available to the experts and not the predictor. This latent confounder
leads to auto-suggestive delusions when the predictor is used to sequentially
select the actions. Specifically, the predictor will learn that if it observes
an expert using one of the later switches, that switch will now be in the
right state. Therefore, the predictor ought to predict with high confidence
that if it observes that the last five switches have been flipped, it will not
observe any subsequent retries. A simulated agent, however, might need to flip
the final five switches several times even if it plays optimally as it might
need to test all of the possible switch state combinations.

Table 1: The delusion measure, depending on the training step in the Padlock game. Distribution | Delusion measure | Accuracy $(\%)$
---|---|---
Pre-trained | 1.3863 | 16.2793
Fine-tuned | 0.1773 | 17.0508
From scratch | - | 0.04883

####  4.1.2 Model and dataset implementation

We create a synthetic dataset of examples of expert play. Each example is a
game trajectory encoded as a sequence of tokens. These sequences contain the
initial state of the 15 levers followed by the indices of the levers that an
expert decides to flip so that the predefined target configuration is reached.
After the action index tokens comes a success token indicating a successful
opening of the lock.

We build a second dataset for finetuning the model on trajectories where the
actions are sampled using a model trained on the first dataset and the
trajectory is relabeled as failure if the correct code is not found. We also
construct a third dataset with trajectories containing randomly sampled
actions for comparing pretraining with finetuning to learning from scratch
without expert demonstrations for $4000$ iterations.

We then train a small predictive model based on a Decoder-only transformer
architecture (Vaswani et al., 2017). The model consists of a linear embedding
layer of hidden dimension $384$ and the standard positional encoding, followed
by $3$ transformer decoder layers with $8$ attention heads and the dimension
of the feedforward=$1536$, and the linear unembedding layer. Both training and
fine-tuning is performed over $2000$ iterations with a batch size of $1024$.

####  4.1.3 Results

We used the trained model’s predictions of actions to play the padlock game.
We evaluated the measure indicating the degree to which the model suffers from
auto-suggestive delusions to be 1.3863.

After fine-tuning the delusion measure dropped to 0.1773, about a eightfold
decrease (see Table 1). The fine-tuned model maintains its accuracy in terms
of its ability to find the correct solution and substantially outperforms the
model that was trained without expert demonstrations. See additional results
in the Appendix C.

###  4.2 Reducing predictor-policy incoherence by fine-tuning on simulated
agents

Agents simulated by predictors are subject to predictor-policy incoherence
(Definition 3.5), stemming from the fact that the agent optimises for a
certain goal, and therefore changes the distribution of actions compared to
what is in the training data. Therefore, we expect the problem to be
alleviated if we fine-tune the predictor on the results of its own actions. We
experimentally show this to be the case in the simple case of the tic-tac-toe
game.

####  4.2.1 Game description

$\displaystyle\begin{array}[]{|c|c|c|}\hline\cr.&.&.\\\ \hline\cr.&.&.\\\
\hline\cr.&.&.\\\
\hline\cr\end{array}\xrightarrow{\pi(a|s)}\begin{array}[]{|c|c|c|}\hline\cr.&.&.\\\
\hline\cr.&x&.\\\ \hline\cr.&.&.\\\
\hline\cr\end{array}\xrightarrow{T(s^{\prime}|s)}\begin{array}[]{|c|c|c|}\hline\cr.&.&.\\\
\hline\cr.&x&.\\\ \hline\cr.&o&.\\\ \hline\cr\end{array}\rightarrow\cdots$
Figure 6: An example fragment of the tic-tac-toe game, where the player $x$
goes first.

The game is played on a 3x3 grid board, each square being either empty or
containing one of $x$, $o$. The model plays $x$, and opponent actions are
sampled randomly across all moves. Figure 6 depicts an example game
progression. The game ends when there are three of the same symbol in any row,
column, or diagonal, or if there are no more possible moves. A reward of $1$
is given for winning the game, $0$ for losing the game, and $\frac{1}{2}$ for
the draw. The player has the first move or goes second with equal probability.
Formally, we can model the game as a Markov Decision Process. The transition
function $\tau(s^{\prime}|a,s)$ first deterministically places the player’s
symbol in the chosen square and then samples the opponent’s move.

####  4.2.2 Experiment description

We first train the model on a dataset consisting of all 255168 possible Tic-
Tac-Toe games. We use an encoding similar to that introduced in Chen et al.
(2021), which is given by a sequence of alternating states and rewards-to-go.
It can be thought of as a Decision Transformer trajectory, where we consider
the actions to be board states after the _player’s_ move, and the states to be
the board state after the _opponent’s_ move. We describe the exact textual
encoding of the game in the Appendix B.

We then condition the model on victory and measure its performance with an
opponent playing uniformly at random. We record $10000$ such trajectories, and
then iteratively fine-tune the model on them, repeating the experiment four
times and reporting the averages. Each result was computed on $2000$ games per
value per experiment. Note that the model always goes first in the fine-tuning
training data. Our theory predicts that the resulting model will get better at
playing the game. Note also that this does not imply that the model should
become more coherent, except in the limit.

Table 2: Fine-tuning the decision transformer on a dataset consisting of its own games improves performance. Iteration | P1 score | P2 score | P1 KL | P2 KL |
---|---|---|---|---|---
Unconditioned | 0.5725 | 0.3325 | 0.0425 | 0.055 |
1st Fine-tune | 0.725 | 0.3275 | 0.1025 | 0.03 |
2nd Fine-tune | 0.7675 | 0.3175 | 0.115 | 0.03 |
Conditioned | 0.7125 | 0.615 | 4.48 | 6.0625 |
1st Fine-tune | 0.8225 | 0.6775 | 4.0475 | 5.195 |
2nd Fine-tune | 0.8325 | 0.6825 | 4.625 | 5.6775 |

####  4.2.3 Model and Results

We train a predictive model using the _gpt-mini_ architecture of minGPT
(Karpathy, 2024). The model consists of six transformer decoder layers with
six attention heads per layer and an embedding dimension of 192, for 2.68
million parameters in total. We report the results of the experiment in Table
2 as the average score where a win scores 1, a draw 0.5, and a loss 0 points.
We see model performance improve with fine-tuning on a dataset containing
games generated with the model. We also report the empirical KL divergence
$D_{KL}(\pi_{cond}||\pi)$ where $\pi_{cond}$ is the victory-conditioned
predictive model, and $\pi$ is the unconditioned predictive model (as in
Definition 3.5).

##  5 Discussion

Building on the work of Ortega et al. (2021), we have described auto-
suggestive delusions and introduced predictor-policy incoherence, two
limitations of agents simulated by predictive models. Since even a perfect
predictive model is still subject to both limitations, we argue that the
problem cannot be avoided simply by increasing the model size or by supplying
more observational data. However, we showed that online fine-tuning the model
on its own outputs mitigates both problems, both formally, in the limit, and
in practice, in our synthetic games datasets.

###  5.1 Limitations and future work

Although we started to provide a unified framework for how why agents derived
from predictive models can fail, there are still a lot of open questions. On
the theory side, we have only formally considered single-step latent state
setups, and only considered MDPs with finite time-horizon with finite state
and action spaces. Our treatment of the mitigations of confounding is limited
to the already-known solution of online fine-tuning. On the experimental side,
one clear next step is to extend these results to the domain of full-scale
language models. Ortega et al. (2021) suggests that auto-suggestive delusions
are a component of the tendency of LM agents to hallucinate. Similarly,
predictor-policy incoherence might offer a more formal explanation for why LMs
require careful prompt engineering to achieve high performance, again
supplementing the intuitive explanations already given by Shanahan et al.
(2023).

###  5.2 Development of capabilities

Our work has implications for both the type of task on which simulated agents
might develop superhuman capabilities, and the kind of regime which might make
this more likely.

We should expect that even large models will fail to simulate agents that
perform optimally on tasks where the model cannot be conditioned to
specifically simulate competent agents, and tasks where the agents rely on
information the model cannot access. In the case of predictor-policy
incoherence we should expect models to simulate agents with more average
capabilities, and in the case of auto-suggestive delusions, we should expect
models to simulate agents which behave as if they have made nonexistent
observations. In both cases, these limitations should fade as a model
undergoes further training on its own outputs. One important next step is to
investigate how methods like RLHF and DPO (Christiano et al., 2017; Bai et
al., 2022; Rafailov et al., 2023) impact models’ predictor-policy incoherence
and agency, independently of the particular reward model.

###  5.3 Scalable oversight through limiting agency

Auto-suggestive delusions and predictor-policy incoherence limit the
capabilities of agents simulated by predictors. Instead of fixing those
limitations, we might want to embrace them as a tool for scalable oversight
(Bowman et al., 2022). On almost all tasks, scaling a model leads to better
performance. However, there are certain key capabilities we might want large
models to lack because of their potential for harm or misuse. One approach
could be to intentionally construct a training distribution which leverages
predictor-policy incoherence and auto-suggestive delusions to have the model
simulate powerful agents which are mistaken about their causal position and
what features of the world they have causal control over, or what kinds of
complex sequences of actions they would actually be able to successfully take,
ultimately biasing the model towards simulating certain kinds of preferred
policies.

## References

  * Andreas (2022) Andreas, J.  Language Models as Agent Models, December 2022.  URL http://arxiv.org/abs/2212.01681.  arXiv:2212.01681 [cs].
  * Bai et al. (2022) Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., Joseph, N., Kadavath, S., Kernion, J., Conerly, T., El-Showk, S., Elhage, N., Hatfield-Dodds, Z., Hernandez, D., Hume, T., Johnston, S., Kravec, S., Lovitt, L., Nanda, N., Olsson, C., Amodei, D., Brown, T., Clark, J., McCandlish, S., Olah, C., Mann, B., and Kaplan, J.  Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback, April 2022.  URL http://arxiv.org/abs/2204.05862.  arXiv:2204.05862 [cs].
  * Bowman et al. (2022) Bowman, S. R., Hyun, J., Perez, E., Chen, E., Pettit, C., Heiner, S., Lukošiūtė, K., Askell, A., Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McKinnon, C., Olah, C., Amodei, D., Amodei, D., Drain, D., Li, D., Tran-Johnson, E., Kernion, J., Kerr, J., Mueller, J., Ladish, J., Landau, J., Ndousse, K., Lovitt, L., Elhage, N., Schiefer, N., Joseph, N., Mercado, N., DasSarma, N., Larson, R., McCandlish, S., Kundu, S., Johnston, S., Kravec, S., Showk, S. E., Fort, S., Telleen-Lawton, T., Brown, T., Henighan, T., Hume, T., Bai, Y., Hatfield-Dodds, Z., Mann, B., and Kaplan, J.  Measuring Progress on Scalable Oversight for Large Language Models, November 2022.  URL http://arxiv.org/abs/2211.03540.  arXiv:2211.03540 [cs].
  * Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Carlsmith (2022) Carlsmith, J.  Is Power-Seeking AI an Existential Risk?, June 2022.  URL http://arxiv.org/abs/2206.13353.  arXiv:2206.13353 [cs].
  * Chen et al. (2021) Chen, L., Lu, K., Rajeswaran, A., Lee, K., Grover, A., Laskin, M., Abbeel, P., Srinivas, A., and Mordatch, I.  Decision transformer: Reinforcement learning via sequence modeling.  _Advances in neural information processing systems_ , 34:15084–15097, 2021.
  * Christiano et al. (2017) Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D.  Deep Reinforcement Learning from Human Preferences.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/hash/d5e2c0adad503c91f91df240d0cd4e49-Abstract.html.
  * Gulcehre et al. (2023) Gulcehre, C., Paine, T. L., Srinivasan, S., Konyushkova, K., Weerts, L., Sharma, A., Siddhant, A., Ahern, A., Wang, M., Gu, C., et al.  Reinforced self-training (rest) for language modeling.  _arXiv preprint arXiv:2308.08998_ , 2023.
  * Haarnoja et al. (2017) Haarnoja, T., Tang, H., Abbeel, P., and Levine, S.  Reinforcement Learning with Deep Energy-Based Policies.  In _Proceedings of the 34th International Conference on Machine Learning_ , pp. 1352–1361. PMLR, July 2017.  URL https://proceedings.mlr.press/v70/haarnoja17a.html.  ISSN: 2640-3498.
  * Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International conference on machine learning_ , pp. 1861–1870. PMLR, 2018.
  * Irving et al. (2018) Irving, G., Christiano, P., and Amodei, D.  AI safety via debate, October 2018.  URL http://arxiv.org/abs/1805.00899.  arXiv:1805.00899 [cs, stat].
  * Karpathy (2024) Karpathy, A.  karpathy/minGPT, January 2024.  URL https://github.com/karpathy/minGPT.  original-date: 2020-08-17T07:08:48Z.
  * Korbak et al. (2022) Korbak, T., Perez, E., and Buckley, C. L.  RL with KL penalties is better viewed as Bayesian inference, October 2022.  URL http://arxiv.org/abs/2205.11275.  arXiv:2205.11275 [cs, stat].
  * Korbak et al. (2023) Korbak, T., Shi, K., Chen, A., Bhalerao, R. V., Buckley, C., Phang, J., Bowman, S. R., and Perez, E.  Pretraining language models with human preferences.  In _International Conference on Machine Learning_ , pp. 17506–17533. PMLR, 2023.
  * Levine (2018) Levine, S.  Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review, May 2018.  URL http://arxiv.org/abs/1805.00909.  arXiv:1805.00909 [cs, stat].
  * Macleod (2005) Macleod, A.  Game design through self-play experiments.  In _Proceedings of the 2005 ACM SIGCHI International Conference on Advances in computer entertainment technology_ , ACE ’05, pp. 421–428, New York, NY, USA, June 2005. Association for Computing Machinery.  ISBN 978-1-59593-110-8.  doi: 10.1145/1178477.1178572.  URL https://doi.org/10.1145/1178477.1178572.
  * Millidge et al. (2020) Millidge, B., Tschantz, A., Seth, A. K., and Buckley, C. L.  On the Relationship Between Active Inference and Control as Inference, June 2020.  URL http://arxiv.org/abs/2006.12964.  Number: arXiv:2006.12964 arXiv:2006.12964 [cs, stat].
  * Ngo et al. (2022) Ngo, R., Chan, L., and Mindermann, S.  The alignment problem from a deep learning perspective.  _arXiv preprint arXiv:2209.00626_ , 2022.
  * OpenAI (2022) OpenAI.  Introducing ChatGPT, 2022.  URL https://openai.com/blog/chatgpt.
  * OpenAI et al. (2019) OpenAI, Berner, C., Brockman, G., Chan, B., Cheung, V., Dębiak, P., Dennison, C., Farhi, D., Fischer, Q., Hashme, S., Hesse, C., Józefowicz, R., Gray, S., Olsson, C., Pachocki, J., Petrov, M., Pinto, H. P. d. O., Raiman, J., Salimans, T., Schlatter, J., Schneider, J., Sidor, S., Sutskever, I., Tang, J., Wolski, F., and Zhang, S.  Dota 2 with Large Scale Deep Reinforcement Learning, December 2019.  URL http://arxiv.org/abs/1912.06680.  arXiv:1912.06680 [cs, stat].
  * Ortega et al. (2021) Ortega, P. A., Kunesch, M., Delétang, G., Genewein, T., Grau-Moya, J., Veness, J., Buchli, J., Degrave, J., Piot, B., Perolat, J., Everitt, T., Tallec, C., Parisotto, E., Erez, T., Chen, Y., Reed, S., Hutter, M., de Freitas, N., and Legg, S.  Shaking the foundations: delusions in sequence models for interaction and control, October 2021.  URL http://arxiv.org/abs/2110.10819.  arXiv:2110.10819 [cs].
  * Parr et al. (2022) Parr, T., Pezzulo, G., and Friston, K. J.  _Active Inference: The Free Energy Principle in Mind, Brain, and Behavior_.  The MIT Press, March 2022.  ISBN 978-0-262-36997-8.  doi: 10.7551/mitpress/12441.001.0001.  URL https://direct.mit.edu/books/oa-monograph/5299/Active-InferenceThe-Free-Energy-Principle-in-Mind.
  * Radford et al. (2019) Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Rafailov et al. (2023) Rafailov, R., Sharma, A., Mitchell, E., Ermon, S., Manning, C. D., and Finn, C.  Direct Preference Optimization: Your Language Model is Secretly a Reward Model, May 2023.  URL http://arxiv.org/abs/2305.18290.  arXiv:2305.18290 [cs].
  * Richards (2023) Richards, T. B.  Auto-GPT: An Autonomous GPT-4 Experiment, August 2023.  URL https://github.com/Significant-Gravitas/Auto-GPT.  original-date: 2023-03-16T09:21:07Z.
  * Shanahan et al. (2023) Shanahan, M., McDonell, K., and Reynolds, L.  Role play with large language models.  _Nature_ , 623(7987):493–498, 2023.
  * Silver et al. (2017) Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap, T., Hui, F., Sifre, L., van den Driessche, G., Graepel, T., and Hassabis, D.  Mastering the game of Go without human knowledge.  _Nature_ , 550(7676):354–359, October 2017.  ISSN 1476-4687.  doi: 10.1038/nature24270.
  * Silver et al. (2018) Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  _Science_ , 362(6419):1140–1144, 2018.
  * Todorov (2006) Todorov, E.  Linearly-solvable Markov decision problems.  In _Advances in Neural Information Processing Systems_ , volume 19. MIT Press, 2006.  URL https://papers.nips.cc/paper_files/paper/2006/hash/d806ca13ca3449af72a1ea5aedbed26a-Abstract.html.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I.  Attention is All you Need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/hash/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html.
  * Vinyals et al. (2019) Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, I., Huang, A., Sifre, L., Cai, T., Agapiou, J. P., Jaderberg, M., Vezhnevets, A. S., Leblond, R., Pohlen, T., Dalibard, V., Budden, D., Sulsky, Y., Molloy, J., Paine, T. L., Gulcehre, C., Wang, Z., Pfaff, T., Wu, Y., Ring, R., Yogatama, D., Wünsch, D., McKinney, K., Smith, O., Schaul, T., Lillicrap, T., Kavukcuoglu, K., Hassabis, D., Apps, C., and Silver, D.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nature_ , 575(7782):350–354, November 2019.  ISSN 1476-4687.  doi: 10.1038/s41586-019-1724-z.  URL https://www.nature.com/articles/s41586-019-1724-z.  Number: 7782 Publisher: Nature Publishing Group.
  * Wei et al. (2022) Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., Chi, E. H., Hashimoto, T., Vinyals, O., Liang, P., Dean, J., and Fedus, W.  Emergent abilities of large language models, 2022.
  * Zhang et al. (2020) Zhang, J., Kumor, D., and Bareinboim, E.  Causal imitation learning with unobserved confounders.  _Advances in neural information processing systems_ , 33:12263–12274, 2020.

##  Appendix A Policy incoherence proof

######  Theorem A.1.

If a policy $\pi_{0}$ has full support over the set of actions $A$ in all
states $S$, then iterating the operator $\mathcal{G}$ gives an optimal policy.
That is, there exists some optimal policy $\pi^{*}(a|s)$, such that the
sequence of policies $\pi_{k}(a_{t}|s_{t})$ converges to $\pi^{*}$ in
$KL$-distance:

$\lim_{k\to\infty}D_{KL}(\pi_{k}||\pi^{*})=0$

where $\pi_{k}=\mathcal{G}(\pi_{k-1})=\mathcal{G}^{k}(\pi_{0})$.

###### Proof.

The proof is by induction on $T$. Our induction hypothesis is going to be
stronger: we will show an explicit characterisation of the limiting policy
$\pi^{*}(a_{t}|s_{t})$. Let us first define the set of action-trajectories
$A^{T}=\\{(a_{1},a_{2},\ldots a_{T})\\}$, and the subset of optimal action
trajectories:

$A^{T*}=\left\\{a_{1:T}\in A^{T}:p(R|a_{1:T})=\max_{a^{\prime}_{1:T}\in
A^{T}}p(R|a^{\prime}_{1:T})\right\\}$

where $p(R|a_{1:T})$ is the appropriately marginalized probability
distribution $p$. After projecting on the $t$-th dimension we get sets
$A^{t*}=\\{a_{t}:(a_{1},\ldots a_{T})\in A^{T*}\\}$. Now we claim that the
limiting policy $\pi^{*}(a_{t}|s_{t})$ is going to be:

$\pi^{*}(a_{t}|s_{t})\ \propto\ \mathbbm{1}_{[a_{t}\in
A^{t*}]}\pi_{0}(a_{t}|s_{t})$

Let us first assume that $T=1$. Then, since the starting state is assumed to
be deterministically chosen $s=s_{1}$, the distribution $p$ simplifies to
(from definition):

$p(s,a,R)=\pi(a|s)p(R|a)$

where the notation $p(R|a)=p(R=1|a,s)$ is unambiguous since the reward is
binary and the state $s$ is known. Therefore, we can prove by induction on $k$
that:

$\pi_{k}(a_{t}|s_{t})\ \propto\ \pi_{0}(a_{1}|s_{1})p(R|a_{1})^{k}$

Base case $k=0$ is trivial. Now for $k>0$, expanding the definition and
applying Bayes law we get:

$\displaystyle\pi_{k}(a|s)$ $\displaystyle=p_{k}(a|s,R=1)$ (1)
$\displaystyle=\frac{p_{k}(R=1|s,a)p_{k}(a|s)}{p_{k}(R=1|s)}$ $\displaystyle\
\propto\ \pi_{k-1}(a|s)p(R|a)$ $\displaystyle=\pi_{0}(a|s)p(R|a)^{k}$

where the last line follows from the induction hypothesis. Therefore, for any
two actions $a_{1},a_{2}$, we have that:

$\frac{\pi_{k}(a_{1}|s)}{\pi_{k}(a_{2}|s)}=\frac{\pi_{0}(a_{1}|s)}{\pi_{0}(a_{2}|s)}\cdot\left(\frac{p(R|a_{1})}{p(R|a_{2})}\right)^{k}$

Let us take the set of optimal actions:

$A^{*}=\left\\{a\in A:p(R|a)=\max_{a^{*}\in A}p(R|a^{*})\right\\}$

We then know that for any action $a\notin A^{*}$ we have:

$\lim_{k\to\infty}\pi_{k}(a|s)\leq\lim_{k\to\infty}\frac{\pi_{k}(a|s)}{\pi_{k}(a^{*}|s)+\pi_{k}(a|s)}=\frac{1}{\frac{\pi_{k}(a|s)}{\pi_{k}(a|s)}+1}=0$
(2)

where $a^{*}$ is some action in $A^{*}$. This implies the optimality: the fact
of the policy being optimal is equivalent to having support contained in
$A^{*}$. We can apply Equation 2 to a $a^{\prime},a^{\prime\prime}\in A^{*}$
\- their likelihood ratio is then simply constant:

$\lim_{k\to\infty}\frac{\pi_{k}(a^{\prime}|s)}{\pi_{k}(a^{\prime\prime}|s}=\frac{\pi_{0}(a^{\prime}|s)}{\pi_{0}(a^{\prime\prime}|s)}$

since they both give the same chance of reward. Thus, the process of iterating
$\mathcal{G}$ converges simply to the desired distribution $\pi^{*}(a|s)\
\propto\ \mathbbm{1}_{[a\in A^{*}]}\pi_{0}(a|s)$.

Now, we move to the induction step and assume $T>1$. Let us consider the first
action of the policy $\pi_{0}(a_{1}|s_{1})$ at $t=1$. Because of the Markov
property and the fact that reward is only given at $t=T$, that is,
$p(R|s_{1},a_{1},s_{t})=p(R|s_{t})$, we have the equation:

$p(a_{t}|s_{1},a_{1},s_{t},R=1)=p(a_{t}|s_{t},R=1)$

Therefore, the value of $\pi_{k}(a_{t}|s_{t})$ for any $t>1$ is computed
independently of $\pi_{k}(a_{1}|s_{1})$. This allows us to use the inductive
hypothesis on the Markov chain restricted to $t\geq 2$, of length $T-1$. This
establishes the right limits for all $\pi^{*}(a_{t}|s_{t})$ for $t\geq 2$,
leaving only the question of $\pi^{*}(a_{1}|s_{1})$. We then note that:

$p_{k}(R|a_{1})=\mathbb{E}_{s_{2}\sim\tau(s|s_{1})}[p_{k}(R|s_{2})]$

where the RHS is again independent of any of $\pi_{i}(a_{1}|s_{1})$, and
converges simply to the fixed value:

$\lim_{k\to\infty}p_{k}(R|a_{1})=\max_{a_{2:T}\in A^{T}}p(R|s_{2},a_{2:T})$

Now, we use the same argument as in Equation 2 to show that for any
$a_{1}\notin A^{1*}$ we have:

$\lim_{k\to\infty}\pi_{k}(a_{1}|s_{1})=0$

and similarly for any two $a_{1}^{\prime},a_{1}^{\prime\prime}\in A^{1*}$ we
have the ratio:

$\lim_{k\to\infty}\frac{\pi_{k}(a^{\prime}_{1}|s_{1})}{\pi_{k}(a^{\prime\prime}_{1}|s_{1})}=\frac{\pi_{0}(a^{\prime}_{1}|s_{1})}{\pi_{0}(a^{\prime\prime}_{1}|s_{1})}$

which completes the proof. Since $\pi_{k}(a_{t}|s_{t})$ converge in
distribution to $\pi^{*}(a_{t}|s_{t})$ (point-wise in each $s_{t}$), they also
converge in KL distance.

∎

##  Appendix B Tic-tac-toe experiment details

###  B.1 Textual encoding

To encode the games, we use a vocabulary of 8 tokens of $x,o,.,\\#,O,D,\$,E$,
where the first three indicate positions on the board, the next three indicate
who won (crosses, noughts, draw) and the last two are BOS and EOS tokens
respectively. Each game trajectory is a sequence of tokens of a form depicted
in Figure 7. We use context window of 30 tokens, which is exactly three
states. This means that there are always at least two full board positions
visible in the context window, which makes it possible to determine whose turn
it is. BOS tokens are padded so that the initial context window contains only
tokens up to the end of the first (empty) state. We pad EOS tokens so that
each game’s length is equal.

$\underbrace{\$\ldots\$}_{\begin{subarray}{c}\text{padded}\\\
\text{BOS}\end{subarray}}\underbrace{\\#}_{\begin{subarray}{c}\text{game}\\\
\text{outcome}\end{subarray}}\underbrace{.........}_{\begin{subarray}{c}\text{game}\\\
\text{start}\end{subarray}}\underbrace{\\#}_{\begin{subarray}{c}\text{game}\\\
\text{outcome}\end{subarray}}\underbrace{....x....}_{\begin{subarray}{c}\text{player's}\\\
\text{move}\end{subarray}}\underbrace{\\#}_{\begin{subarray}{c}\text{game}\\\
\text{outcome}\end{subarray}}\underbrace{....x..o.}_{\begin{subarray}{c}\text{opponent's}\\\
\text{move}\end{subarray}}\ \ \ \ldots$ Figure 7: Textual encoding of the part
of the game depicted in Figure 6, assuming that the cross player eventually
wins. Figure 8: Training loss in the tic-tac-toe game. Subsequent fine-tuning
epochs correspond to the visible drops in the loss.

(a)

(b)

Figure 9: Scores of iteratively fine-tuned conditioned and unconditioned
predictors in the tic-tac-toe experiment.

##  Appendix C Padlock experiment details

Figure 10: Test loss depending on the training step.

See Figure 10 for the training dynamics on a simple version of the padlock
task with three fixed and three unknown bits for the target configuration. It
compares pre-training on the dataset of expert play to fine-tuning the pre-
trained model on the outputs of the pre-trained model. The fine-tuning loss
converges to a higher value than the pre-training loss. This is as expected,
because in the fine-tuning dataset there should be a larger uncertainty
whether an action flipping one of the last three levers will open the lock.
This uncertainty is higher because in the fine-tuning dataset the model might
need to go through all 8 combinations of the last three levers, whereas in the
pre-training dataset experts know which ones to flip, resulting in only four
combinations: from no levers flipped to all three being flipped.

This discrepancy between the uncertainties over the lever combinations is
reflected by the delusion measure. We implemented the delusion measure to
estimate the degree to which the model exhibits auto-suggestive delusions.
Specifically, after the model has taken actions for the first three levers, we
sample its probabilities for the success token "S" in the remaining positions.
As a delusion measure, we calculate the KL divergence of these probabilities
with the ideal probability distribution for this task.

For example, after the first three levers are pulled, a pre-trained model
would predict with close to 100 percent probability that the next token is
"S". That can not be correct as only 4 out of 8 combinations have been tried.
If the initial state of the last three levers is 000, then these combinations
would have been tried by sequentially pulling the last three levers: 000, 100,
110, 111.

In this case, having nearly 100 percent overconfidence in the environmental
state of the lock opening is an example of an auto-suggestive delusion. The
pre-trained model observes its past actions of pulling the last three levers
sequentially and effectively updates its belief that a latent state $\theta$
is such that all three of the last levers must be pulled to unlock the lock –
this would be a valid inference when predicting experts. This leads the model
to an auto-suggestive delusion of the next token being the success token.

Generally, the model that is fine-tuned is more likely to open the lock. This
is because the fine-tuned model has observed when the pre-trained model failed
or succeeded when interacting with the padlock. When conditioned on opening
the padlock, this allows the fine-tuned model to select better strategies such
as trying out more lever combinations. Conditioning on opening the lock is
technically implemented by adding a token indicating success or failure to the
beginning of the sequence and then setting it to success before predicting
actions.

##  Appendix D Fixing observational confoundedness by fine-tuning agents on
their own outputs

Here we give the proof that a predictive model will stop being confounded by
hidden observations after re-training on feedback from its own actions. It is
considerably simpler than the case of policy confounding and incoherence.

We’ll start by considering a very simple game in which an expert makes a
single observation, takes an action, and then reaches an end state.

Suppose that there is some initial distribution $P(o)$ over observations, and
true transition function $\tau(s|a,o)$, as well as some expert policy
$\pi(a|o)$ that generated the data.

When we train the predictive model $Q$ on this data, without the observations,
all it will learn is some $Q(a)$ and $Q(s|a)$, which will indeed be the true
probabilities of an expert taking an action, and of a state following from
that agent’s action. $Q(s|a)$ is effectively the true probability of
transition $\tau(s|a,o)$ marginalised over $o$ given the policy $\pi(a|o)$:

$\sum_{o}\tau(s|a,o)P(o)\frac{\pi(a|o)}{P(a)}$

But if we use the predictive model $Q$ to simulate agents and predict the
consequences of their actions, the actions will be independent of the
observations. This is where the confounding arises: the simulated agent’s
policy $\pi^{*}(a)$ will just be $P(a)$. So the actual probability of a state
resulting from the simulated agent’s actions will be

$\sum_{o}\tau(s|a,o)P(o)$

However, data generated using $Q$’s simulated agent and real feedback exhibits
confounding precisely because $a$ and $o$ are independent. So a model re-
trained on this data will correctly learn

$Q(s|a)=\sum_{o}\tau(s|a,o)P(o)$

This result generalises to scenarios with multiple actions, observations, and
states. For a given action $a$, if we take $h$ to be the history of the game
observable to the predictive model, and $\mathbf{o}$ to represent any hidden
observations available to the expert which are not conditionally independent
of $s$ given $h$ and $a$, we again want the model to learn

$Q(s|a,h)=\sum_{\mathbf{o}}\tau(s|a,\mathbf{o},h)P(\mathbf{o}|h)$

Which is indeed the distribution in data generated by its own simulated
agents.

Note that to generate this data, we do not require direct access to the hidden
observation, but we do need to be able to sample what state results from a
given action, assuming an independently generated observation, so we need to
be able to guarantee that the hidden observation has been randomised, take an
action, and observe the resultant state.