Note: this is a new version -- with a new title -- of my recent post "A Behavioral Definition of Goal-Directedness". Most of the formulas are the same, except for the triviality one that deals better with what I wanted; the point of this rewrite is to present the ideas in a perspective that makes sense. I'm not proposing a definition of goal-directedness, but just sufficient statistics on the complete behavior that make a behavioral study of goal-directedness more human-legible.

I also use this new version as a first experiment in another approach to feedback: this post includes a lot of questions asked through the elicit prediction feature. A lot. I definitely tried to overshoot the reasonable number to add, to compensate my tendency to never use them. But don't worry: whether or not there were too many questions will be the subject of another question at the end!

Introduction

In a previous post, I argued for the study of goal-directedness in two steps:

• Defining goal-directedness: depends only on the complete behavior of the system, and probably assumes infinite compute and resources.
• Computing goal-directedness: depends on the internal structure, and more specifically what information about the complete behavior can be extracted from this structure.

Intuitively, understanding goal-directedness should mean knowing which questions to ask about the complete behavior of the system to determine its goal-directedness. Here the “complete” part is crucial; it simplifies the problem by removing the need to infer what the system will do based on limited behavior. Similarly, we don’t care about the tractability/computability of the questions asked; the point is to find what to look for, without worrying (yet) about how to get it.

Despite these simplifications, the behavioral approach still suffers from one massive problem: it's not human-legible. We don't know what to do with this mass of loosely structured information, and have slim hopes of finding the right angle or question by sheer luck.

This post addresses this problem: it proposes human-legible sufficient statistics on this complete behavior that should be enough to deconfuse and clarify most questions about goal-directedness. The next posts then use these statistics to explore a formal understanding of goal-directedness.

Eventually we will have to rely on internal structure; but knowing the property to derive/approximate beforehand should help quite a lot.

Thanks to Joe Collman and Michele Campolo for helpful feedback and discussion on this post.

Preliminaries

Let’s start with the formalisation of the environment. The interface is defined by the set $O$ of observations and the set $A$ of actions. We have a finite set $Envs$ of environments, which are just finite deterministic POMDPs with no reward , using $O$ and $A$ for observations and actions, with a uniform distribution over initial states. For an $E\in Envs$, $S_E$ is the set of states of $E$.

My sufficient statistics for goal-directedness actually extend to more reasonable settings (stochastic POMDPs and a general distribution over initial states) straightforwardly, but I start with the simpler deterministic case to get the intuitions right. On the other hand, the assumption that $Envs$ is finite (although maybe intractably big) is kept through the post because it ensures without additional work the well-definedness of some expressions. There might be a way to extend the sufficient statistics to the countable case, but that’s beyond the scope of this post.

The system we study is given by a program $\pi$ that takes as inputs the successive observations and return the action taken. I use a program in place of a function from histories to actions because it hides the internal state (that I don’t use) while retaining the expressiveness of such a computable function. We can query the behavior of $\pi$ on any environment of $Envs$ by giving an initial state and seeing what happens; we can also ask potentially uncomputable questions about this behavior (as long as they are well-defined).

Now, when we call a system goal-directed, we usually have a goal for it in mind. The subtlety about a behavioral definition is that we can’t just look inside the model to find the goal; we somehow have to infer goals from the behavior. This is made easier in the setting of this post because we have access to all the behavior and uncomputable procedures -- but we still have to do it.

In fact, the sufficient statistics for goal-directedness of $\pi$ talk about all possible goals. More specifically, for each goal, I define a vector of numbers called focus, capturing how coherent the goal is with the behavior of $\pi$.

The next section... focuses on defining and motivating this vector.

Focus of a goal

A goal is a a function from an environment $E\in Envs$ to a subset of $S_E$. That is, a goal gives for each environment the states to reach. This form is certainly limited; yet it captures enough intuitive goals to not be trivial. Another important constraint is that every goal $g$considered satisfies $K\left(g\right)<K\left(\pi \right)$, where K is the Kolmogorov complexity. What this means is that $g$ doesn't just capture the states that $\pi$ end up in environment $E$ by simulating $\pi$ in $E$; if that was the case, then the smallest program implementing $g$ should be more complex than the smallest program implementing $\pi$, and we forbid that.

For each goal $g$, its focus for $\pi$ is a 4-tuple $(comp{l}_g,ge{n}_g,{\text{eff}}_g,exp{l}_g)\in [0,1{]}^4$ capturing important properties of $\pi$ and the goal. The last three correspond to the last three intuitions (without the far-sightedness) about goal-directedness from the literature review that we wrote with Joe Collman and Michele Campolo.

Complexity factor

This is just the Kolmogorov complexity of $g$ mapped into $[0,1]$: $comp{l}_g=1-\frac{1}{K\left(g\right)}$. There’s not much more to say about it. It’s just useful to compare goal close or equal on the other factors, to reason about which one is more likely to emerge from training.

Generalization factor

This first element of the focus, the generalization factor $ge{n}_g$, captures how much $\pi$ reaches the goal $g$ over the environments of $Envs$. The formula is the following:

$ge{n}_g=max(0,\frac{1}{|Envs|}(\sum _{E\in Envs}\frac{\sum _{s\in reachabl{e}_s\left(E\right)}ge{n}_g^E(\pi ,s)}{|reachabl{e}_g\left(E\right)|}-trivialit{y}_g(E\left)\right))$,
where $ge{n}_g^E(\pi ,s)=\{\begin{array}{cc}1& \text{if}\pi \text{reaches}g\left(E\right)\text{starting at}s\\ 0& \text{otherwise}\end{array}$, $reachabl{e}_g\left(E\right)$ is the set of states of $S_E$ from which some goal state in $g\left(E\right)$ is reachable, and $trivialit{y}_g\left(E\right)=\frac{1}{mi{x}_g^E(\pi ,x)}$ such that $mi{x}_g^E(\pi ,s)$ measures the time it takes for the random uniform policy to put $mix\_thresh$ % of the probability mass on goal states. A bit more formally, if we start with a probability distribution over $S_E$ with $1$ on $s$ and $0$ everywhere else, and then update that probability distribution according to the random uniform policy and the environment, $mi{x}_g^E(\pi ,x)$ captures the first time (if any) where the probability distribution puts more than $mix\_thresh$ % of the probability mass on goal states. (It’s more involved than just “the probability that the random uniform policy reaches a goal state” because the simple version trivially goes to $1$ in a lot of simple and finite cases).

The intuition of the formula is straightforward: it’s the average generalization of $\pi$ for goal $g$ over $Envs$. The expression averaged is the indicator of whether $\pi$ reaches a goal state, minus the "triviality" of the goal (a measure of how difficult it is to reach a goal state). Thanks to this correction (for a good choice of $mix\_thresh$, which I don't know how to make and motivate yet), trivial goals, like the one outputting $S_E$ for environment $E$, don't generalize well despite being trivially reachable.

A high generalization means that $\pi$ reaches a goal state most of the time; a small one that it rarely does. In the former case it makes more sense to consider $g$ as a goal of the system.

Efficiency factor

This second element of the focus, the efficiency factor ${\text{eff}}_g$, captures how efficiently $\pi$ reaches the goal $g$ in the (environment,initial state) pairs. The formula is the following:
${\text{eff}}_g=\frac{1}{|\{E\in Envs|\exists s\in S_E:ge{n}_g^E(\pi ,s)=1\}|}\sum _{\begin{array}{c}E\in Envs,\\ \exists s\in S_E:ge{n}_g^E(\pi ,s)=1\end{array}}\frac{1}{|\{s\in S_E|ge{n}_g^E(\pi ,s)=1\}|}\sum _{\begin{array}{c}s\in S_E,\\ ge{n}_g^E(\pi ,s)=1\end{array}}{\text{eff}}_g^E(\pi ,s)$where ${\text{eff}}_g^E(\pi ,s)=\frac{nb\_steps\_opt{i}_g}{nb\_step{s}_{\pi }}$, the ratio between the number of steps taken by the optimal policy for $g$ to reach a goal state starting at $s$, and the number of steps taken by $\pi$ to reach a goal state starting at $s$.

It’s pretty straightforward; the only subtlety is that the so called optimal policy is the optimal policy for the reward (-1 for any non goal state, 0 for a goal state -- and then the episode stops), and for all environments in $Envs$. Now, there might be multiple optimal policies (privileging different environments but getting the same expected return over $Envs$). I'm fine with using the one that maximize $ef{f}_g$. Doing so mean comparing $\pi$ with the optimal policy for $g$ that is most similar to it in some sense.

While the generalization factor captures in what proportion of environments does $\pi$ reach a goal state, the efficiency factor captures how fast $\pi$ does that compared to the optimal policy for $g$.

Explainability factor

This last element of the focus, the explainability factor ${\text{expl}}_g$, captures how well explained $\pi$ is by assuming it is directed towards $g$. The formula is the following:

$exp{l}_g=\underset{\mu }{max}\left(\frac{1}{|Envs|}\sum _{E\in Envs}\frac{1}{|S_E|}\sum _{s\in S_E}pre{d}_g^E\right(\pi ,{\pi }_g,s\left)\right)$

where $pre{d}_g^E(\pi ,\mu ,s)=\frac{1}{T}\sum _{t=0}^T\frac{\underset{a}{max}{q}_{\mu }(s_t,a)-q_{\mu }(s_t,actio{n}_{\pi })}{\underset{a}{max}{q}_{\mu }(s_t,a)}$ measures the average deviation of $\pi$ from the actions favored by the action-value function $q_{\mu }$ of $\mu$.

There are many details and subtleties to unravel here.

• (The policy $\mu$) Another policy $\mu$ is used in computing the prediction fitness for the goal $g$. It is obtained by doing RL on the reward defined by $g$ (see the section on efficiency for more details); importantly, it’s not necessarily an optimal policy for this reward. It can be any policy that results from RL training (when you stop after some time), with the caveat that it must do $n$ times better than the random uniform policy (in terms of expected return). Here $n$ is a parameter that seems important (to not allow policies without any direction towards $g$), but I have no idea how to decide on its value.
  The reason for the use of $\mu$ instead of an optimal policy for the reward is that explainability by a “decent” policy moving towards the goal seems just as good to me.
   

• (The time limit $T$) This is used for normalizing the prediction using the goal. If $\pi$ actually reaches the goal (and thus ends the episode), then $T$ is just the length of this episode. If $\pi$ never finishes, then $T$ is some arbitrary time limit after which the episode ends anyway.

Explainability captures Daniel Dennett’s intentional stance through RL: it measures how well-explained $\pi$ is through some learned RL method on the goal. There’s one aspect that is missing though: the comparison with the best prediction of simple high-level models (Dennett’s design stance). This other sufficient statistics depends only on $\pi$, so it’s not defined in this section.

Complete Sufficient Statistics

The sufficient statistics on the behavior of $\pi$ for studying goal-directedness are then the focus for each goal satisfying the complexity constraint, as well as the explainability of $\pi$ in terms of simple gears-level model:

$expl\_gears=\underset{K\left(d\right)<C}{max}\left(\frac{1}{|Envs|}\sum _{E\in Envs}\frac{1}{|S_E|}\sum _{s\in S_E}error\_pre{d}_d^E\right(\pi ,s\left)\right)$, where $d$ is a program capturing a simple model of $\pi$ (the upper bound on its Kolmogorov complexity $C$ is assumed to be $<<K\left(\pi \right)$);  $pre{d}_d^E(\pi ,s)$ is the proportion of time where the action taken by $\pi$ in its trajectory starting at $s$ is the action taken by $d$.

When you compare it to the prediction using the goal, the prediction using a simple model looks very binary: either the action taken is the one $\pi$ takes or it’s completely wrong. We can rephrase this as saying that the actions are all equally far from each other.

This looks like a reasonable default assumption, but it doesn’t always hold. For example, if the actions are the angles by increments of 5 degrees, then getting the angle just next to the one $\pi$ took sure seems closer than taking the opposite one. That is, there is a notion of similarity for the action space. In these cases the definition should probably be altered to use that notion of similarity (and normalize it) instead of the binary default.

Now, given a goal $g$, we can use $expl\_gears$ to compute the difference in explainability $exp{l}_g-expl\_gears$ in $[-1,1]$. Here being close to $-1$ means being better explained by a simple model, being close to $1$ means being better explained by the goal $g$, and being close to zero means that both are equally good (or bad) at predicting $\pi$.

What I hope for these sufficient statistics is that they can provide more than just a simple number telling you how goal directed you $\pi$ is. They also allow us to think more clearly about many questions related to goals, like the importance of explainability, convergent instrumental subgoals, and inner alignment. The next posts in this sequence explore these in more detail, but we can look quickly at one example (to be revisited later in the sequence) now.

The one true goal

In some settings, knowing if a clear goal exists, and what it is, matters. Maybe we’re worried about the focus on too narrow a goal, and what it entails. Can we adapt the core definition of goal-directedness to this application?

My current intuition is that this most representative goal should primarily depend on generalization. It should matter more because a goal with better generalization is a goal that points more often in the right direction. This leaves us two cases:

• If there is a goal with a massive lead on generalization (something like 2x the second largest generalization), then I think we should go with that one.
• If there isn't, then we lack a clear representative goal.

What’s even more exciting is that framing it that way highlights important questions: what if there are two goals, both with far more generalization, and one with even more than the other? In the absence of a representative goal, are all goals the same or is there a relevant hierarchy?

All these questions, and more, will be solv… addressed at the very least in the following posts of the sequence.

Stochastic version

As promised, I'll explain how to get from the deterministic case above to a more realistic stochastic one. The changes considered are making $\pi$ into a stochastic policy returning an element of $\Delta A$ (a distribution over actions); the environments being stochastic POMDP with stochastic transition function and stochastic observation function (returning the observation for a given state); and there is a distribution of initial states for each environment.

Here are the changes necessary for the computation of each factor of the focus (no change necessary for complexity, as it just depends on the program itself):

• (Generalization factor) $ge{n}_g^E\left(\pi \right)$ goes from an element of $\{0,1\}$ to a the probability that $\pi$ eventually reaches a state in $g\left(E\right)$, computed by extracting a distribution over histories from the distribution over initial states, the POMDP and the policy. Then we take the probability of getting a history that reaches a goal state.
• (Efficiency factor) ${\text{eff}}_g^E\left(\pi \right)$ goes through similar changes, where the time taken becomes an expected value over the distributions on histories generated.
• (Explainability factor) The prediction error computed now compares distributions at each step. But that's doable with something like KL divergence (maybe we want something different if we allow distributions with 0 probability, which might make KL divergence... diverge)

Conclusion

I proposed sufficient statistics over the complete behavior of a system encoding relationships with goals (about reaching some states). These properties are the complexity of the goal, the generalization towards the goal, the efficiency of the system when it generalizes, and how well it is explained by a goal-based model. There’s an additional sufficient statistic for the system in general, about how well it is explained by a simple gears-level model.

We can’t compute these directly for concrete systems, as they rely on the knowledge of the complete behavior, and ask many questions that might be uncomputable or at best intractable.

Nonetheless, I believe this is progress. Instead of arguing without common grounding, we can argue using these statistics. And any deeper understanding of goal-directedness we get will provide a guiding light to checking the goal-directedness of some actual AIs.

The next posts in this sequence will explore what can be done with these statistics