Intelligent Agent Foundations Forumsign up / log in
Another Concise Open Problem
post by Scott Garrabrant 1271 days ago | Nate Soares and Patrick LaVictoire like this | 1 comment

Given the success of the last open problem I posted, (Janos Kramer disproved my conjecture) I decided to post another one. Again, I will cut off the philosophy, and just give the math. The reason I want this result is to solve the problem described here.

Let \(S\) be the set of all paris \((M,k)\) where \(M\) is a Turing machines which and \(k\) is a natural number.

For \(P=(M,k)\in S\), we define the function \(P(n)=p\) if \(M\) halts on input \(n\) in time \(n^k\) and outputs a probability \(p\), and \(P(n)=1/2\) otherwise.

Let \(E=e_1,e_2,\ldots\) be an infinite bit string. We say \(Q\in S\) defeats \(P\in S\) on \(E\) if

\[\lim_{n\rightarrow\infty}\prod_{i=0}^n\frac{|1-e_i-P(i)|}{|1-e_i-Q(i)|}=0.\]

If there is no \(Q\) in \(S\) which defeats \(P\) on \(E\), we say that \(P\) is undefeated on \(E\).

Let \(A\) be an algorithm which takes as input a finite bit string, and whose output encodes an element of \(S\).

Does there exist an algorithm \(A\) such that for all \(E\), if there exists a \(P\) which is undefeated on \(E\), then for all sufficienty large \(n\), \(A(e_1,\ldots,e_n)\) is undefeated on \(E\)?

Note that \(A\) can run as long as it wants. I would also be very interested in a positive result that requires that \(P\in S\) is undefeated by every function computable in exponential time. (\(P\) still runs in polynomial time.)

Also, note that if I replace the \(\lim\) with \(\lim \inf\), and require that \(P\in S\) is undefeated by every function computable in exponential time, then such an \(A\) does in fact exist. (The algorithm that does this has not been posted on the forum yet, sorry. If anyone wants to work on this problem, and is curious, I can explain it to them)



by Scott Garrabrant 1267 days ago | link

I am still curious about this question, but am much less optimistic that an answer to it would be very valuable than I was when I first asked it.

reply



NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

[Note: This comment is three
by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

RSS

Privacy & Terms