Concise Open Problem in Logical Uncertainty

[Scott Garrabrant]

The purpose of this post is to provide a short fully mathematically specified conjecture which can be worked on with very little background, but which has an important consequence in logical uncertainty. Not too many man-hours have been put into this question yet, so it is plausible that a MIRIx team could solve this problem.

Let $E$ be a be an envirnoment which is a function from $N$ to $\{0,1\}$.

Let $M$ be an algorithm which on input $n$ is given oracle access to $E\left(i\right)$ for all $i<\log n$, and which outputs a probability $p\left(n\right)$.

Definition: If $$\underset{n\to \infty }{lim}\prod _{i=1}^n\frac{|p\left(i\right)+E\left(i\right)-1|}{|E\left(i\right)-\frac{1}{3}|}=0,$$ then $M$ is bad. Similarly, if $$\underset{n\to \infty }{lim}\prod _{i=1}^n\frac{|p\left(i\right)+E\left(i\right)-1|}{|E\left(i\right)-\frac{2}{3}|}=0,$$ then $M$ is bad. Otherwise, $M$ is good. (Note that if there is no limit, this does not mean $M$ is bad.)

Conjecture: For every algorithm $M$, there exists an environment $E$ such that $M$ is bad.

Intuitively, $M$ is slowly seeing bits from $E$, and much more quickly making predictions about $E$. If $M$ is bad in the first sense, that means that $M$ it has made much worse predictions than if it just output ²⁄₃. If $M$ is bad in the second sense, that means that $M$ it has made much worse predictions than if it just output ¹⁄₃. It seems easy enough to avoid the first failure mode; we just have to switch to output ²⁄₃ if we cross some threshhold where ²⁄₃ has been doing better. Adding the second failure mode makes this strategy stop working, because an evil environment could cause us to lock in to ²⁄₃, and then switch to giving probability ¹⁄₃ forever.

We would like an $M$ which can take a countable set of advisors, and do at least as well as all of them, even when there is a delay in the observations. However, I believe that $M$ can’t even do at least as well as two constant advisors. The above conjecture implies that $M$ cannot even balance the predictions of two constant advisors, and therefore also cannot balance countably many advisors. Note that a disproof would also be very interesting.

[János Kramár]

def M(p, E):
    p1, p2 = 1./3, 2./3
    prev, this, next = 0, 0, 1

bad1 and bad2 compute log-badnesses of M relative to p1 and p2, on E[:prev]; the goal of M is to ensure neither one goes to $\infty$. prev, this, next are set in such a way that M is permitted access to this when computing p[this:next].

    def bad(advisor):
        return lambda:
            sum(log(abs((E[i] + advisor(i) - 1) /
                        (E[i] + p[i] - 1)))
                for i in xrange(prev))
    bad1, bad2 = bad(lambda i: p1), bad(lambda i: p2)
    for i in xrange(this, next): p[i] = 0.5
    prev, this, next = this, next, floor(exp(next - 1)) + 1

    while True:
        for i in xrange(this, next): p[i] = p1
        prev, this, next = this, next, floor(exp(next - 1)) + 1

bad1() is now be up to date through E[:this], not just E[:prev]

        bound = 2 * bad1()
        while bad1() > 0:
            # won't let bad1() surpass bound
            eps = (bound - bad1()) / 2 / (1 - p1) / (next - this)

This is just for early iterations; in the limit, eps should be just enough for bad1 to go halfway to bound:

            while eps >= 1 - p1 or
              bound <= bad1() + (next - this) *
              log((1 - p1) / (1 - p1 - eps)):
                eps /= 2
            for i in xrange(this, next): p[i] = p1 + eps
            prev, this, next = this, next, floor(exp(next - 1)) + 1

            for i in xrange(this, next): p[i] = p1
            # this is where the p1 + eps affects bad1()
            prev, this, next = this, next, floor(exp(next - 1)) + 1

Now every iteration (after the first few) where $\mathrm{mean}\left(E[prev:this]\right)\le \frac{2}{5}$ will decrease bad2() by roughly at least $(this-prev)\left(\log \right(1-p1)-\log (1-p2)+\frac{2}{5}(\log \left(p1\right)-\log \left(p2\right)-\log (1-p1)+\log (1-p2)\left)\right)=(this-prev)\frac{1}{5}\log \left(2\right)\gg prev$, which is large enough to turn bad2() negative. Therefore, if M is bad for E, there can be only finitely many such iterations until the loop exits. However, every iteration where $\mathrm{mean}\left(E[prev:this]\right)\ge \frac{2}{5}$ will cause bound - bad1() to grow exponentially (by a factor of $\frac{11}{10}=1+\frac{1}{2}(-1+\frac{2}{5}\frac{1}{p1})$), so the loop will terminate.

Now we’ll perform the same procedure for bad2():

        for i in xrange(this, next): p[i] = p2
        prev, this, next = this, next, floor(exp(next - 1)) + 1

        bound = 2 * bad2()
        while bad2() > 0:
            # won't let bad2() surpass bound
            eps = (bound - bad2()) / 2 / p2 / (next - this)
            while eps >= p2 or
              bound <= bad2() + (next - this) *
              log( p2 / (p2 - eps)):
                eps /= 2
            for i in xrange(this, next): p[i] = p2 - eps
            prev, this, next = this, next, floor(exp(next - 1)) + 1

            for i in xrange(this, next): p[i] = p2
            # this is where the p2 - eps affects bad2()
            prev, this, next = this, next, floor(exp(next - 1)) + 1

For the same reasons as the previous loop, this loop either stops with bad2() < 0 or runs forever with bad2() bounded and bad1 repeatedly falling back below 0.

Therefore, this algorithm either gets trapped in one of the inner while loops (and succeeds) or turns bad1() and bad2() negative, each an infinite number of times, and therefore succeeds.

[TsviBT]

Could you spell out the step

every iteration where mean(𝙴[𝚙𝚛𝚎𝚟:𝚝𝚑𝚒𝚜])≥2/​5 will cause bound—bad1() to grow exponentially (by a factor of 11/​10=1+(1/​2)(−1+2/​5𝚙𝟷))

a little more? I don’t follow. (I think I follow the overall structure of the proof, and if I believed this step I would believe the proof.)

We have that eps is about (2/​3)(1-exp([bad1() - bound]/​(next-this))), or at least half that, but I don’t see how to get a lower bound on the decrease of bad1() (as a fraction of bound-bad1() ).

[Scott Garrabrant]

You are correct that you use the fact that 1+eps is at approximately e^(eps).

The concrete way this is used in this proof is replacing the ln(1+3eps) you subtract from bad1 when the environment is a 1 with 3eps=(bound—bad1) /​ (next—this), and replacing the ln(1-3eps/​2) you subtract from bad1 when the environment is a 0 with −3eps/​2=-(bound—bad1) /​ (next—this)/​2

Therefore, you subtract from bad1 approximately at least (next-this)((2/​5)(bound—bad1) /​ (next—this)-(3/​5)*(bound—bad1) /​ (next—this)/​2).

This comes out to (bound—bad1)/​10.

I believe the inequality is the wrong direction to just use e^(eps) as a bound for 1+eps, but when next-this gets big, the approximation gets close enough.

[TsviBT]

In case anyone shared my confusion:

The while loop where we ensure that eps is small enough so that

bound > bad1() + (next—this) * log((1 - p1) /​ (1 - p1 - eps))

is technically necessary to ensure that bad1() doesn’t surpass bound, but it is immaterial in the limit. Solving

bound = bad1() + (next—this) * log((1 - p1) /​ (1 - p1 - eps))

gives

eps >= (1/​3) (1 - e^{ -[bound—bad1()] /​ [next—this]] })

which, using the log(1+x) = x approximation, is about

(1/​3) ([bound—bad1()] /​ [next—this] ).

Then Scott’s comment gives the rest. I was worried about the fact that we seem to be taking the exponential of the error in our approximation, or something. But Scott points out that this is not an issue because we can make [next-this] as big as we want, if necessary, without increasing bad1() at all, by guessing p1 for a very long time until [bound—bad1()] /​ [next—this]] is close enough to zero that the error is too small to matter.

[Scott Garrabrant]

Nice! I think I believe your claim, and I would like to chat with you to verify stuff and talk about future directions.

I have thought about algorithms very similar to this, and using such an algorithm got an $M$ which is either good, or bad in the first sense and outputting probabilities converging to ²⁄₃, or bad in the second sense and outputting probabilities converging to ¹⁄₃. I had thought that if epsilon was shrinking quickly enough as to not have bad1 go to infinity, it would be shrinking so quickly that you could get locked in the while loop with bad2 increasing. I don’t think I actually checked this claim carefully, so I guess maybe I was wrong.

If this algorithm works as claimed, I wonder if you can extend it to three advisors (which may not be constant).

[János Kramár]

Ah, I think I can stymy $M$ with 2 nonconstant advisors. Namely, let $A_1\left(n\right)=\frac{1}{2}-\frac{1}{n+3}$ and $A_2\left(n\right)=\frac{1}{2}+\frac{1}{n+3}$. We (setting up an adversarial $E$) precommit to setting $E\left(n\right)=0$ if $p\left(n\right)\ge A_2\left(n\right)$ and $E\left(n\right)=1$ if $p\left(n\right)\le A_1\left(n\right)$; now we can assume that $M$ always chooses $p\left(n\right)\in \left[A_1\right(n),A_2(n\left)\right]$, since this is better for $M$.

Now define $b_i^{\prime }\left(j\right)=\left|A_i\right(j)+E(j)-1|-\left|p\right(j)+E(j)-1|$ and $b_i\left(n\right)={\sum }_{j<n}{b}_i^{\prime }\left(j\right)$. Note that if we also define ${\mathrm{bad}}_i\left(n\right)={\sum }_{j<n}(\log \left|A_i\right(j)+E(j)-1|-\log \left|p\right(j)+E(j)-1|)$ then ${\sum }_{j<n}\left|2b_i\right(j)-{\mathrm{bad}}_i(j\left)\right|\le {\sum }_{j<n}\left(2A_1\right(j)-1-\log (2A_1\left(j\right)\left)\right))={\sum }_{j<n}O\left({(\frac{1}{2}-A_1(j\left)\right)}^2\right)$ is bounded; therefore if we can force $b_1\left(n\right)\to \infty$ or $b_2\left(n\right)\to \infty$ then we win.

Let’s reparametrize by writing $\delta \left(n\right)=A_2\left(n\right)-A_1\left(n\right)=\frac{2}{n+3}$ and $q\left(n\right)=\frac{p\left(n\right)-A_1\left(n\right)}{\delta \left(n\right)}$, so that $b_i^{\prime }\left(j\right)=\delta \left(j\right)(|i-2+E(j\left)\right|-\left|q\right(j)-1+E(j\left)\right|)$.

Now, similarly to how $M$ worked for constant advisors, let’s look at the problem in rounds: let $s_0=0$, and $s_n=\lfloor \exp (s_{n-1}-1)\rfloor +1$ for $n>0$. When determining $E\left(s_{n-1}\right),\dots ,E(s_n-1)$, we can look at $p\left(s_{n-1}\right),\dots ,p(s_n-1)$. Let $t_n=\lfloor b_2\left(s_n\right)-\frac{1}{n}\rfloor$. Let’s set $E\left(s_{n-1}\right),\dots ,E(s_n-1)$ to 1 if ${\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)(1-q(j\left)\right)\ge 1$; otherwise we’ll do something more complicated, but maintain the constraint that $b_2\left(s_n\right)\ge b_2\left(s_{n-1}\right)-\frac{1}{n(n-1)}\ge t_{n-1}+\frac{1}{n}$: this guarantees that $t_n$ is nondecreasing and that ${liminf}_{j\to \infty }{b}_2\left(j\right)\ge {lim}_{n\to \infty }{t}_n$.

If $t_n\to \infty$ then $b_2\left(n\right)\to \infty$ and we win. Otherwise, let $t={lim}_{n\to \infty }{t}_n$, and consider $n$ such that $t_{n-1}=t$.

We have ${\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)(1-q(j\left)\right)<1$. Let $J\subseteq \{s_{n-1},\dots ,s_n-1\}$ be a set of indices with $q\left(j\right)\ge q\left(j^{\prime }\right)$ for all $j\in J,j^{\prime }\notin J$, that is maximal under the constraint that ${\sum }_{j\in J}\delta \left(j\right)(1-q(j\left)\right)\le \frac{1}{n(n-1)}$; thus we will still have ${\sum }_{j\in J}\delta \left(j\right)(1-q(j\left)\right)\ge \frac{1}{n(n-1)}-\delta \left(s_{n-1}\right)$. We shall set $E\left(j\right)=0$ for all $j\in J$.

By the definition of $J$: $$\begin{array}{cc}\sum _{j\in J}{b}_1^{\prime }\left(j\right)& =\sum _{j\in J}\delta \left(j\right)q\left(j\right)\\ & \ge \sum _{j\in J}\delta \left(j\right)(1-q(j\left)\right)\frac{{\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)q\left(j\right)}{{\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)(1-q(j\left)\right)}\\ & \ge (\frac{1}{n(n-1)}-\delta (s_{n-1}\left)\right)\frac{{\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)-1}{1}\\ & \ge (\frac{1}{n(n-1)}-\delta (s_{n-1}\left)\right)(2\log \left(\frac{s_n+3}{s_{n-1}+3}\right)-1)\\ & \ge 2\text{if}n\gg 0\end{array}$$

For $j^{\prime }\notin J$, we’ll proceed iteratively, greedily minimizing $\left|{\sum }_{j^{\prime }=s_{n-1}}^j{1}_{j^{\prime }\notin J}\left(b_1^{\prime }\right(j^{\prime }),b_2^{\prime }(j^{\prime }\left)\right)\right|$. Then: $$\begin{array}{cc}\underset{s_{n-1}\le j<s_n}{min}\sum _{j^{\prime }=s_{n-1}}^j{1}_{j^{\prime }\notin J}{b}_1^{\prime }\left(j^{\prime }\right)& \ge -\sqrt{\sum _{j=s_{n-1}}^{s_n-1}\delta (j{)}^2}\\ & =-2\sqrt{\sum _{j=s_{n-1}+3}^{s_n-2}\frac{1}{j^2}}\\ & \ge -2\sqrt{\sum _{j=s_{n-1}+3}^{s_n-2}(\frac{1}{j-1}-\frac{1}{j})}\\ & \ge -\frac{2}{\sqrt{s_{n-1}+2}}\\ & \ge -1\text{if}n\gg 0\end{array}$$

Keeping this constraint, we can flip (or not flip) all the $E\left(j^{\prime }\right)$s for $j^{\prime }\notin J$ so that ${\sum }_{j^{\prime }=s_{n-1}}^{s_n-1}{1}_{j^{\prime }\notin J}{b}_2^{\prime }\left(j^{\prime }\right)>0$. Then, we have $b_2\left(s_n\right)\ge b_2\left(s_{n-1}\right)-\frac{1}{n(n-1)}$, $b_1\left(s_n\right)-b_1\left(s_{n-1}\right)={\sum }_{j=s_{n-1}}^{s_n}(1_{j\in J}+1_{j\notin J})b_1^{\prime }\left(j\right)\ge 2-1=1$ if $n\gg 0$, and for $s_{n-1}\le j\le s_n$, $b_1\left(j\right)\ge b_1\left(s_{n-1}\right)+{\sum }_{j^{\prime }=s_{n-1}}^{j-1}{1}_{j^{\prime }\notin J}{b}_1^{\prime }\left(j^{\prime }\right)\ge b_1\left(s_{n-1}\right)-1$ if $n\gg 0$.

Therefore, $b_1\left(j\right)\to \infty$, so we win.

[János Kramár]

I don’t yet know whether I can extend it to two nonconstant advisors, but I do know I can extend it to a countably infinite number of constant-prediction advisors. Let $(P_i{)}_{i=0,\dots }$ be an enumeration of their predictions that contains each one an infinite number of times. Then:

def M(p, E, P):
    prev, this, next = 0, 0, 1
    def bad(i):
        return sum(log(abs((E[k] + P[i] - 1) /
                           (E[k] + p[k] - 1)))
                   for k in xrange(prev))
    for k in xrange(this, next): p[k] = 0.5
    prev, this, next = this, next, floor(exp(next - 1)) + 1

    for i in xrange(0, Inf):
        for k in xrange(this, next): p[k] = P[i]
        prev, this, next = this, next, floor(exp(next - 1)) + 1

bad(i) is now up to date through E[:this], not just E[:prev]

        bound = 2 * bad(i)
        for j in xrange(0, Inf):
            if P[j] == P[i]: continue
            flip = P[j] < P[i]
            p1, p2 = abs(P[i] - flip), abs(P[j] - flip)
            for k in xrange(this, next): p[k] = abs(p1 - flip)
            prev, this, next = this, next, floor(exp(next - 1)) + 1
            
            if bad(i) <= 0: break
            while bad(i) > 0 and bad(j) > 0:
                # won't let bad(i) surpass bound
                eps = (bound - bad(i)) / 2 / abs(1 - p1 - flip) / (next - this)

This is just for early iterations of the inner loop; in the limit, eps should be just enough for bad(i) to go halfway to bound if we let p = abs(p1 + eps - flip):

                while eps >= 1 - p1 or
                      bound <= bad(i) + (next - this) *
                        log((1 - p1) / (1 - p1 - eps)):
                    eps /= 2
                for k in xrange(this, next): p[k] = abs(p1 + eps - flip)
                prev, this, next = this, next, floor(exp(next - 1)) + 1

                for k in xrange(this, next): p[k] = abs(p1 - flip)
                # this is where the P[i] + d * eps affects bad(i)

Consider $q=\frac{\log (1-p1)-\log (1-p2)}{\log (1-p1)-\log (1-p2)+\log \left(p2\right)-\log \left(p1\right)}$. This $q$ is the probability between p1 and p2 such that if E[k] is chosen with probability $|q-flip|$ then that will have an equal impact on bad(i) and bad(j). Now consider some $q^{\prime }$ between p1 and $q$. Every iteration where $\mathrm{mean}\left(\left|E[prev:this]-flip\right|\right)\le q^{\prime }$ will decrease bad(j) by a positive quantity that’s at least linear in this-prev, so (at least after the first few such iterations) this will exceed $prev\cdot -\log ({max}_{k:P_k\text{has been reached}}max(P_k,1-P_k\left)\right)>bad\left(j\right)$, so it will turn bad(j) negative. If this happens for all j then M cannot be bad for E. If it doesn’t, then let’s look at the first j where it doesn’t. After a finite number of iterations, every iteration must have $\mathrm{mean}\left(\left|E[prev:this]-flip\right|\right)>q^{\prime }$. However, this will cause bad(i) to decrease by a positive quantity that’s at least proportional to bound - bad(i); therefore, after a finite number of such iterations, we must reach $bad\left(i\right)<0$. So if M is bad for E then for each value of i we will eventually make $bad\left(i\right)<0$ and then move on to the next value of i. This implies M is not bad for E.

---

Emboldened by this, we can also consider the problem of building an $M$ that isn’t outperformed by any constant advisor. However, this cannot be done, according to the following handwavy argument:

Let $q$ be some incompressible number, and let $E\left(i\right)\stackrel{iid}{\sim }\mathrm{Bern}\left(q\right)$. When computing $p\left(n\right)$, $M$ can’t do appreciably better than Laplace’s law of succession, which will give it standard error $\sqrt{\frac{q(1-q)}{\log \left(n\right)}}$, and relative badness $\sim \frac{q(1-q)}{\log \left(n\right)}(\frac{1}{q}+\frac{1}{1-q})=\frac{1}{\log \left(n\right)}$ (relative to the $q$-advisor) on average. For $i\le n$, and $n\gg 0$, the greatest deviation of the badness from the ${\sum }_{j=2}^i\frac{1}{\log \left(j\right)}\ge \frac{i-1}{\log \left(i\right)}$ trend is $\approx \sqrt{2n\log \log \left(n\right)q(1-q)}$ (according to the law of the iterated logarithm), which isn’t enough to counteract the expected badness; therefore the badness will converge to infinity.

[cousin_it]

Let’s say E(i) = 1 iff p(i) < ¹⁄₂. Then both products go to zero at least as fast as (3/​4)^n. Or am I missing something?