This idea was inspired by a correspondence with Adam Shimi.

It seem very interesting and important to understand to what extent a purely "behaviorist" view on goal-directed intelligence is viable. That is, given a certain behavior (policy), is it possible to tell whether the behavior is goal-directed and what are its goals, without any additional information?

Consider a general reinforcement learning settings: we have a set of actions $A$, a set of observations $O$, a policy is a mapping $\pi :(A\times O{)}^{\ast }\to \Delta A$, a reward function is a mapping $r:(A\times O{)}^{\ast }\to [0,1]$, the utility function is a time discounted sum of rewards. (Alternatively, we could use instrumental reward functions.)

The simplest attempt at defining "goal-directed intelligence" is requiring that the policy $\pi$ in question is optimal for some prior and utility function. However, this condition is vacuous: the reward function can artificially reward only behavior that follows $\pi$, or the prior can believe that behavior not according to $\pi$ leads to some terrible outcome.

The next natural attempt is bounding the description complexity of the prior and reward function, in order to avoid priors and reward functions that are "contrived". However, description complexity is only naturally well-defined up to an additive constant. So, if we want to have a crisp concept, we need to consider an asymptotic in which the complexity of something goes to infinity. Indeed, it seems natural to ask that the complexity of the policy should be much higher than the complexity of the prior and the reward function: in this case we can say that the "intentional stance" is an efficient description. However, this doesn't make sense with description complexity: the description "optimal policy for $U$ and $\zeta$" is of size $K\left(U\right)+K\left(\zeta \right)+O\left(1\right)$ ($K\left(x\right)$ stands for "description complexity of $x$").

To salvage this idea, we need to take not only description complexity but also computational complexity into account. [EDIT: I was wrong, and we can get a well-defined concept in the unbounded setting too, see child comment. The bounded concept is still interesting.] For the intentional stance to be non-vacuous we need to demand that the policy does some "hard work" in order to be optimal. Let's make it formal. Consider any function of the type $f:{\Sigma }^{\ast }\to \Delta \Xi$ where $\Sigma$ and $\Xi$ are some finite alphabets. Then, we can try to represent it by a probabilistic automaton $T:S\times \Sigma \to \Delta (S\times \Xi )$, where $S$ is the finite set space, $T$ is the transition kernel, and we're feeding symbols into the automaton one by one. Moreover, $T$ can be represented as a boolean circuit $R$ and this circuit can be the output of some program $P$ executed by some fixed universal Turing machine. We can associate with this object 5 complexity parameters:

• The description complexity, which is the length of $P$.
• The computation time complexity, which is the size of $R$.
• The computation space complexity, which is the maximum between the depth of $R$ and $\log |S|$.
• The precomputation time complexity, which is the time it takes $P$ to run.
• The precomputation space complexity, which is the space $P$ needs to run.

It is then natural to form a single complexity measure by applying a logarithm to the times and taking a linear combination of all 5 (we apply a logarithm so that a brute force search over $n$ bits is roughly equivalent to hard-coding $n$ bits). The coefficients in this combination represent the "prices" of the various resources (but we should probably fix the price of description complexity to be 1). Of course not all coefficients must be non-vanishing, it's just that I prefer to keep maximal generality for now. We will denote this complexity measure $C$.

We can use such automatons to represent policies, finite POMDP environments and reward functions (ofc not any policy or reward function, but any that can be computed on a machine with finite space). In the case of policies, the computation time/space complexity can be regarded as the time/space cost of applying the "trained" algorithm, whereas the precomputation time/space complexity can be regarded as the time/space cost of training. If we wish, we can also think of the boolean circuit as a recurrent neural network.

We can also use $C$ to define a prior ${\zeta }_0$, by ranging over programs $P$ that output a valid POMDP and assigning probability proportional to $2^{-C}$ to each instance. (Assuming that the environment has a finite state space might seem restrictive, but becomes quite reasonable if we use a quasi-Bayesian setting with quasi-POMDPs that are not meant to be complete descriptions of the environment; for now we won't go into details about this.)

Now, return to our policy $\pi$. Given $g>0$, we define that "$\pi$ has goal-directed intelligence (at least) $g$" when there is a suitable prior $\zeta$ and utility function $U$ s.t. for any policy ${\pi }^{\prime }$, if $E_{\zeta {\pi }^{\prime }}\left[U\right]\ge E_{\zeta \pi }\left[U\right]$ then $C\left({\pi }^{\prime }\right)\ge D_{KL}\left({\zeta }_0||\zeta \right)+C\left(U\right)+g$. When $g=+\infty$ (i.e. no finite automaton can match the expected utility of $\pi$; in particular, this implies $\pi$ is optimal since any policy can be approximated by a finite automaton), we say that $\pi$ is "perfectly goal-directed". Here, $D_{KL}\left({\zeta }_0||\zeta \right)$ serves as a way to measure the complexity of $\zeta$, which also ensures $\zeta$ is non-dogmatic in some rather strong sense.

[EDIT: if we fix $U$ and $\zeta$ then $g$ is essentially the same as Yudkowsky's definition of optimization power if we regard the policy as the "outcome" and use $2^{-C}$ as our measure on the space of outcomes.]

With this definition we cannot "cheat" by encoding the policy into the prior or into the utility function, since that would allow no complexity difference. Therefore this notion seems like a non-trivial requirement on the policy. On the other hand, this requirement does hold sometimes, because solving the optimization problem can be much more computationally costly than just evaluating the utility function or sampling the prior.