The goal of this post is to present a theorem structure that seems useful for the agent structure problem. I'll give some examples of these types of theorems that illustrate what we may mean by structure.
The theorem form looks like the following:
- The space of all agents is constrained by a pool constraint.
- The agent pool is run in some environment class.
- The agent pool is filtered by an environment constraint.
- The remaining agents must all have a certain structure.
We will now break down these terms.
An agent is a traditional RL agent that operates in some environment by receiving observations and outputting actions. Agents are thought of as Turing machines: observations are written to their input tapes, they use their work tapes to compute their next actions, and they write those actions to their output tapes.
An agent pool is created by filtering the space of all agents by the pool constraint. This can be a simple constraint, like ensuring the agents have the correct input and output types. Or it can be a constraint on the description length of the Turing machine that keeps only agents that could be represented on a modern computer.
An environment is a Turing machine that takes actions as inputs and returns observations.
The agent pool is run in an environment class. This is either a single environment or a set of environments parameterized by some variables. The agent pool is run in all environments in the set.
Then we can pick an environment constraint to judge how well the agent did and whether it should pass. A simple constraint is optimization of the environment. In simple terms, an agent optimizes an environment if it ends in a special state more often than random chance would predict. In a sense, it is pushing the environment toward that state.
There could be multiple ways of picking a criterion over an environment class. The agent could optimize in a single environment, in all environments, or in a majority of them.
We can then prove a common structure among all the remaining agents in the agent pool. This structure could be a lot of different things like storing a variable or running a looping mechanism.
We will now present examples of theorems of this form.
Theorem examples
Paying attention
We first define an environment class, Button World, with the following conditions:
- The state is a single integer
- There are two actions $A$ and $B$
- $A$ adds one to the state and outputs a 1
- $B$ subtracts one from the state and outputs a 0
- The other environment in this class has the actions flipped.
To perform optimization in Button World, an agent needs to pay attention to its observations.
The space of all agents is first filtered to include agents whose inputs and outputs type-check with the environment (i.e., agents that don't output $C$ as an action). Otherwise, all possible agents are run in the environment. Call this set of agents the Button World Agent Pool.
We then filter the Button World Agents by running them in the environment class and keeping those that make the value of every environment's state greater than 0 after $n$ steps. That is, an agent must systematically move each environment to a greater state. Call this new agent pool the Button World Winning Agents.
To do this, an agent must change the actions it takes in different environments. It must also try an action and remember whether it produced a good outcome. It has to learn the positive action and keep taking it. This filters out agents that take random actions.
We now try to define the structure all the agents in Button World Winning Agents must share.
If we think of the agents' actions as probabilistic, we can write the following:
$$
p(a_i) \ne p(a_i|o_{i-1})
$$
$p(a_i)$ is the probability that an agent takes a certain action. This probability must be different if the agent is given the last observation. If the agent saw that the last observation was a 1, then it should be certain about which action to take. This is a necessary but not sufficient condition for optimization in the environment.
Optimization in this environment also implies that the agent must have remembered the last action it took at some point.
$$ p(a_j) \ne p(a_j | a_i)$$
This says that the probability of taking an action at time step $j$, where $j > i$, must be different if the agent has seen its last action.
This implies some structure in the work tape and in how the agent copies data from its input tape to its output tape.
Searching
We can define an environment (Tree World) where the agent has to perform tree search. Imagine the states in a tree-like formation where, at each state, you can go up the tree or down to the left or right. There is exactly one leaf node that outputs a 1 when the agent reaches it; all other nodes output a 0. The environment also outputs the possible next states. The environment class is parameterized by which leaf state is the winning state.
The criterion is that an agent always reaches the final state.
There would be some strange agents that optimize in this environment. Some could have memorized every possible tree like this and have the correct list of states to visit preprogrammed so that they visit all states. These entities don't feel like they are searching. They don't even need to pay attention to the observations; they just output all the actions and finish.
How can we eliminate these non-searchers? We can bound the entity's description length. We can also add an extra parameter to the set of environments: the height of the tree. If an entity isn't given this value, it must pay attention to its inputs to know which actions to output.
We can now pick our favorite search algorithm and start bounding the set of entities even more. They have to have the same space and time complexity as DFS. We then get a space of agents where some are doing DFS, but are they all searching? A proof could look like this:
- Add the following constraints to the space of all agents
- optimize in Tree World
- $O(n)$ time and space complexity
- $n$ is the length of the tree
- All of the remaining agents must be in some sense "searching"
- The agent must have some internal state that is tracking where in the tree it is located
We could keep coming up with different constraints to narrow down the remaining space and try to pull out more formal structure.
The main goal
Now we set up the main goal of this project, which is to show that if an agent is doing well enough in some environment, then it must be a goal-optimizing agent.
The pool constraint should be very liberal. We want to say that we will get anything that we could plausibly get from training a large model via gradient descent.
I think the creative part of the proof would be coming up with an environment class and a constraint such that only scary goal-optimizing agents come out. To do this, we need to build up more intuition about the structure of goal optimization. This could involve developing more robust definitions of planning and search that don't overly constrain the space.
Closing thoughts
It is interesting to note that the entities aren't really "trying" to be the right entities here. They just happen to be the correct ones for the environment class that we are constructing. This is nowhere near the agency of a human who can change what they are trying to do.
These types of proofs seem complicated. It is easy to provide an example of an agent that is optimizing in an environment, but it is much harder to put constraints on the space of all agents such that you only get agents with a certain structure. This is similar to proving a lower bound on some problem.
I think this is important for AI safety because, by default, our models come from the space of all entities. If we can prove certain things about their internal structure just by observing that they are optimizing in certain scenarios, this could give us better evals for detecting this behavior more quickly.
A negative proof here would also be interesting. If an agent can solve most problems with reasonable time and space without a mechanism that we would recognize as search, that would say fundamental things about intelligence.
In further posts, I hope to break down this idea and explore more formally the different structures one can get.