Review

Concise Open Problem in Logical Uncertainty

5János Kramár

0Tsvi Benson-Tilsen

1Scott Garrabrant

1Tsvi Benson-Tilsen

0Scott Garrabrant

0János Kramár

0János Kramár

0Vladimir Slepnev

New Comment

8 comments, sorted by Click to highlight new comments since: Today at 7:01 AM

```
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 . `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 will decrease `bad2()`

by roughly at least , 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 will cause `bound - bad1()`

to grow exponentially (by a factor of ), 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.

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() ).

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.

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.

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 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).

Ah, I think I can stymy with 2 nonconstant advisors. Namely, let and . We (setting up an adversarial ) precommit to setting if and if ; now we can assume that always chooses , since this is better for .

Now define and . Note that if we also define then is bounded; therefore if we can force or then we win.

Let's reparametrize by writing and , so that .

Now, similarly to how worked for constant advisors, let's look at the problem in rounds: let , and for . When determining , we can look at . Let . Let's set to 1 if ; otherwise we'll do something more complicated, but maintain the constraint that : this guarantees that is nondecreasing and that .

If then and we win. Otherwise, let , and consider such that .

We have . Let be a set of indices with for all , that is maximal under the constraint that ; thus we will still have . We shall set for all .

By the definition of :

For , we'll proceed iteratively, greedily minimizing . Then:

Keeping this constraint, we can flip (or not flip) all the s for so that . Then, we have , if , and for , if .

Therefore, , so we win.

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 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 . This is the probability between `p1`

and `p2`

such that if `E[k]`

is chosen with probability then that will have an equal impact on `bad(i)`

and `bad(j)`

. Now consider some between `p1`

and .
Every iteration where 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 , 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 . 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 . So if `M`

is bad for `E`

then for each value of `i`

we will eventually make 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 that isn't outperformed by any constant advisor. However, this cannot be done, according to the following handwavy argument:

Let be some incompressible number, and let . When computing , can't do appreciably better than Laplace's law of succession, which will give it standard error , and relative badness (relative to the -advisor) on average. For , and , the greatest deviation of the badness from the trend is (according to the law of the iterated logarithm), which isn't enough to counteract the expected badness; therefore the badness will converge to infinity.

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(i) for all i<logn, and which outputs a probability p(n).

Definition:If limn→∞n∏i=1|p(i)+E(i)−1||E(i)−13|=0, then M is bad. Similarly, if limn→∞n∏i=1|p(i)+E(i)−1||E(i)−23|=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 2/3. If M is bad in the second sense, that means that M it has made much worse predictions than if it just output 1/3. It seems easy enough to avoid the first failure mode; we just have to switch to output 2/3 if we cross some threshhold where 2/3 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 2/3, and then switch to giving probability 1/3 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.