Concise Open Problem in Logical Uncertainty

[-]János Kramár10yΩ450

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 $mean (E [p r e v : t h i s]) \leq \frac{2}{5}$ will decrease bad2() by roughly at least $(t h i s - p r e v) (log (1 - p 1) - log (1 - p 2) + \frac{2}{5} (log (p 1) - log (p 2) - log (1 - p 1) + log (1 - p 2))) = (t h i s - p r e v) \frac{1}{5} log (2) ≫ p r e v$ , 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 $mean (E [p r e v : t h i s]) \geq \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}{p 1})$ ), 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.

[-]TsviBT10yΩ000

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 Garrabrant10yΩ110

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.

[-]TsviBT10yΩ110

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 Garrabrant10yΩ000

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 2/3, or bad in the second sense and outputting probabilities converging to 1/3. 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ár10yΩ000

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

Now define $b_{i}^{'} (j) = | A_{i} (j) + E (j) - 1 | - | p (j) + E (j) - 1 |$ and $b_{i} (n) = \sum_{j < n} b_{i}^{'} (j)$ . Note that if we also define ${bad}_{i} (n) = \sum_{j < n} (log | A_{i} (j) + E (j) - 1 | - log | p (j) + E (j) - 1 |)$ then $\sum_{j < n} | 2 b_{i} (j) - {bad}_{i} (j) | \leq \sum_{j < n} (2 A_{1} (j) - 1 - log (2 A_{1} (j)))) = \sum_{j < n} O ({(\frac{1}{2} - A_{1} (j))}_{1}^{2})$ is bounded; therefore if we can force $b_{1} (n) \to \infty$ or $b_{2} (n) \to \infty$ then we win.

Let's reparametrize by writing $δ (n) = A_{2} (n) - A_{1} (n) = \frac{2}{n + 3}$ and $q (n) = \frac{p (n) - A_{1} (n)}{δ (n)}$ , so that $b_{i}^{'} (j) = δ (j) (| i - 2 + E (j) | - | q (j) - 1 + E (j) |)$ .

Now, similarly to how $M$ worked for constant advisors, let's look at the problem in rounds: let $s_{0} = 0$ , and $s_{n} = ⌊ exp (s_{n - 1} - 1) ⌋ + 1$ for $n > 0$ . When determining $E (s_{n - 1}), \dots, E (s_{n} - 1)$ , we can look at $p (s_{n - 1}), \dots, p (s_{n} - 1)$ . Let $t_{n} = ⌊ b_{2} (s_{n}) - \frac{1}{n} ⌋$ . Let's set $E (s_{n - 1}), \dots, E (s_{n} - 1)$ to 1 if $\sum_{j = s_{n - 1}}^{s_{n} - 1} δ (j) (1 - q (j)) \geq 1$ ; otherwise we'll do something more complicated, but maintain the constraint that $b_{2} (s_{n}) \geq b_{2} (s_{n - 1}) - \frac{1}{n (n - 1)} \geq t_{n - 1} + \frac{1}{n}$ : this guarantees that $t_{n}$ is nondecreasing and that ${l i m i n f}_{j \to \infty} b_{2} (j) \geq {lim}_{n \to \infty} t_{n}$ .

If $t_{n} \to \infty$ then $b_{2} (n) \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} δ (j) (1 - q (j)) < 1$ . Let $J \subseteq {s_{n - 1}, \dots, s_{n} - 1}$ be a set of indices with $q (j) \geq q (j^{'})$ for all $j \in J, j^{'} \notin J$ , that is maximal under the constraint that $\sum_{j \in J} δ (j) (1 - q (j)) \leq \frac{1}{n (n - 1)}$ ; thus we will still have $\sum_{j \in J} δ (j) (1 - q (j)) \geq \frac{1}{n (n - 1)} - δ (s_{n - 1})$ . We shall set $E (j) = 0$ for all $j \in J$ .

By the definition of $J$ : $\begin{matrix} \sum j \in J b_{1}^{'} (j) & = \sum j \in J δ (j) q (j) \geq \sum j \in J δ (j) (1 - q (j)) \frac{\sum_{j = s_{n - 1}}^{s_{n} - 1} δ (j) q (j)}{\sum_{j = s_{n - 1}}^{s_{n} - 1} δ (j) (1 - q (j))} \geq (\frac{1}{n (n - 1)} - δ (s_{n - 1})) \frac{\sum_{j = s_{n - 1}}^{s_{n} - 1} δ (j) - 1}{1} \geq (\frac{1}{n (n - 1)} - δ (s_{n - 1})) (2 log (\frac{s_{n} + 3}{s_{n - 1} + 3}) - 1) \geq 2 if n ≫ 0 \end{matrix}$

For $j^{'} \notin J$ , we'll proceed iteratively, greedily minimizing $∣ ∣ \sum_{j^{'} = s_{n - 1}}^{j} 1_{j^{'} \notin J} (b_{1}^{'} (j^{'}), b_{2}^{'} (j^{'})) ∣ ∣$ . Then: $\begin{matrix} min s_{n - 1} \leq j < s_{n} j \sum j^{'} = s_{n - 1} 1_{j^{'} \notin J} b_{1}^{'} (j^{'}) & \geq - \sqrt{s_{n} - 1 \sum j = s_{n - 1} δ (j)^{2}} = - 2 \sqrt{s_{n} - 2 \sum j = s_{n - 1} + 3 \frac{1}{j^{2}}} \geq - 2 \sqrt{s_{n} - 2 \sum j = s_{n - 1} + 3 (\frac{1}{j - 1} - \frac{1}{j})} \geq - \frac{2}{\sqrt{s_{n - 1} + 2}} \geq - 1 if n ≫ 0 \end{matrix}$

Keeping this constraint, we can flip (or not flip) all the $E (j^{'})$ s for $j^{'} \notin J$ so that $\sum_{j^{'} = s_{n - 1}}^{s_{n} - 1} 1_{j^{'} \notin J} b_{2}^{'} (j^{'}) > 0$ . Then, we have $b_{2} (s_{n}) \geq b_{2} (s_{n - 1}) - \frac{1}{n (n - 1)}$ , $b_{1} (s_{n}) - b_{1} (s_{n - 1}) = \sum_{j = s_{n - 1}}^{s_{n}} (1_{j \in J} + 1_{j \notin J}) b_{1}^{'} (j) \geq 2 - 1 = 1$ if $n ≫ 0$ , and for $s_{n - 1} \leq j \leq s_{n}$ , $b_{1} (j) \geq b_{1} (s_{n - 1}) + \sum_{j^{'} = s_{n - 1}}^{j - 1} 1_{j^{'} \notin J} b_{1}^{'} (j^{'}) \geq b_{1} (s_{n - 1}) - 1$ if $n ≫ 0$ .

Therefore, $b_{1} (j) \to \infty$ , so we win.

[-]János Kramár10yΩ000

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 - p 1) - log (1 - p 2)}{log (1 - p 1) - log (1 - p 2) + log (p 2) - log (p 1)}$ . This $q$ is the probability between p1 and p2 such that if E[k] is chosen with probability $| q - f l i p |$ then that will have an equal impact on bad(i) and bad(j). Now consider some $q^{'}$ between p1 and $q$ . Every iteration where $mean (| E [p r e v : t h i s] - f l i p |) \leq q^{'}$ 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 $p r e v \cdot - log ({max}_{k : P_{k} has been reached} max (P_{k}, 1 - P_{k})) > b a d (j)$ , 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 $mean (| E [p r e v : t h i s] - f l i p |) > q^{'}$ . 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 $b a d (i) < 0$ . So if M is bad for E then for each value of i we will eventually make $b a d (i) < 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 (i) i i d \sim Bern (q)$ . When computing $p (n)$ , $M$ can't do appreciably better than Laplace's law of succession, which will give it standard error $\sqrt{\frac{q (1 - q)}{log (n)}}$ , and relative badness $\sim \frac{q (1 - q)}{log (n)} (\frac{1}{q} + \frac{1}{1 - q}) = \frac{1}{log (n)}$ (relative to the $q$ -advisor) on average. For $i \leq n$ , and $n ≫ 0$ , the greatest deviation of the badness from the $\sum_{j = 2}^{i} \frac{1}{log (j)} \geq \frac{i - 1}{log (i)}$ trend is $\approx \sqrt{2 n log log (n) 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_it10yΩ000

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

LESSWRONG
LW

LESSWRONG
LW

5

Concise Open Problem in Logical Uncertainty

5

Ω 3

5

Ω 3