harfe comments on The Learning-Theoretic Agenda: Status 2023

[harfe]

Regarding direction 17: There might be some potential drawbacks to ADAM. I think its possible that some very agentic programs have relatively low $g$ score. This is due to explicit optimization algorithms being low complexity.

(Disclaimer: the following argument is not a proof, and appeals to some heuristics/​etc. We fix $M=M_0$ for these considerations too.) Consider an utility function $\hat{U}$. Further, consider a computable approximation of the optimal policy (AIXI that explicitly optimizes for $\hat{U}$) and has an approximation parameter n (this could be AIXI-tl, plus some approximation of $\hat{U}$; higher $n$ is better approximation). We will call this approximation of the optimal policy ${\pi }_n^{\hat{U}}$. This approximation algorithm has complexity $K\left({\pi }_n^{\hat{U}}\right)=C+K\left(\hat{U}\right)+K\left(n\right)$, where $C>0$ is a constant needed to describe the general algorithm (this should not be too large).

We can get better approximation by using a quickly growing function, such as the Ackermann function with $n=A(k,k)$. Then we have $K\left({\pi }_{A(k,k)}^{\hat{U}}\right)=C+K\left(\hat{U}\right)+K\left(A\right(k,k\left)\right)\le C+K\left(\hat{U}\right)+\log \left(k\right)$.

What is the $g$ score of this policy? We have $g\left({\pi }_{A(k,k)}^{\hat{U}}\right)={max}_U\left({min}_{{\pi }^{\prime }:\dots }K\right({\pi }^{\prime })-K(U\left)\right)$. Let $\overline{U}$ be maximal in this expression. If $K\left(\overline{U}\right)\ge K\left(\hat{U}\right)-C$, then $$g\left({\pi }_{A(k,k)}^{\hat{U}}\right)=\underset{{\pi }^{\prime }:E_{{\zeta }_{M_0}{\pi }^{\prime }}\left(\overline{U}\right)\ge E_{{\zeta }_{M_0}{\pi }_{A(k,k)}^{\hat{U}}}\left(\overline{U}\right)}{min}K\left({\pi }^{\prime }\right)-K\left(\overline{U}\right)\le K\left({\pi }_{A(k,k)}^{\hat{U}}\right)-K\left(\hat{U}\right)+C\le 2C\log \left(k\right)$$.

For the other case, let us assume that if $K\left(\overline{U}\right)<K\left(\hat{U}\right)-C$, the policy ${\pi }_{A(k,k)}^{\overline{U}}$ is at least as good at maximizing $\overline{U}$ than ${\pi }_{A(k,k)}^{\hat{U})}$. Then, we have $$g\left({\pi }_{A(k,k)}^{\hat{U}}\right)=\underset{{\pi }^{\prime }:E_{{\zeta }_{M_0}{\pi }^{\prime }}\left(\overline{U}\right)\ge E_{{\zeta }_{M_0}{\pi }_{A(k,k)}^{\hat{U}}}\left(\overline{U}\right)}{min}K\left({\pi }^{\prime }\right)-K\left(\overline{U}\right)\le K\left({\pi }_{A(k,k)}^{\overline{U}}\right)-K\left(\overline{U}\right))\le C+\log (k)$$.

I don’t think that the assumption ($({\pi }_{A(k,k)}^{\overline{U}}$ maximizes $barU$ better than $({\pi }_{A(k,k)}^{\hat{U}}$) is true for all $\hat{U}$ and $k$, but plausibly we can select $\hat{U}$ such that this is the case (exceptions, if they exist, would be a bit weird, and if ADAM working well due to these weird exceptions feels a bit disappointing to me). A thing that is not captured by approximations such as AIXI-tl are programs that halt but have insane runtime (longer than $A(k,k)$). Again, it would feel weird to me if ADAM sort of works because of low-complexity extremely-long-running halting programs.

To summarize, maybe there exist policies ${\pi }_{A(k,k)}^{\hat{U}}$ which strongly optimize a non-trivial utility function $\hat{U}$ with approximation parameter $n=A(k,k)$, but where $g\left({\pi }_{A(k,k)}^{\hat{U}}\right)\le 2C+\log \left(k\right)$ is relatively small.

[Vanessa Kosoy]

Yes, this is an important point, of which I am well aware. This is why I expect unbounded-ADAM to only be a toy model. A more realistic ADAM would use a complexity measure that takes computational complexity into account instead of $K$. For example, you can look at the measure $C$ I defined here. More realistically, this measure should be based on the frugal universal prior.