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 (Pi)i=0,… 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=log(1−p1)−log(1−p2)log(1−p1)−log(1−p2)+log(p2)−log(p1). 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′ between p1 and q.
Every iteration where mean(|E[prev:this]−flip|)≤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 prev⋅−log(maxk:Pk has been reachedmax(Pk,1−Pk))>bad(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[prev:this]−flip|)>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 bad(i)<0. So if M is bad for E then for each value of i we will eventually make bad(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)iid∼Bern(q). When computing p(n), M can’t do appreciably better than Laplace’s law of succession, which will give it standard error √q(1−q)log(n), and relative badness ∼q(1−q)log(n)(1q+11−q)=1log(n) (relative to the q-advisor) on average. For i≤n, and n≫0, the greatest deviation of the badness from the ∑ij=21log(j)≥i−1log(i) trend is ≈√2nloglog(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.
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 (Pi)i=0,… be an enumeration of their predictions that contains each one an infinite number of times. Then:
bad(i)is now up to date throughE[:this], not justE[:prev]This is just for early iterations of the inner loop; in the limit,
epsshould be just enough forbad(i)to go halfway toboundif we letp = abs(p1 + eps - flip):Consider q=log(1−p1)−log(1−p2)log(1−p1)−log(1−p2)+log(p2)−log(p1). This q is the probability between
p1andp2such that ifE[k]is chosen with probability |q−flip| then that will have an equal impact onbad(i)andbad(j). Now consider some q′ betweenp1and q. Every iteration where mean(|E[prev:this]−flip|)≤q′ will decreasebad(j)by a positive quantity that’s at least linear inthis-prev, so (at least after the first few such iterations) this will exceed prev⋅−log(maxk:Pk has been reachedmax(Pk,1−Pk))>bad(j), so it will turnbad(j)negative. If this happens for alljthenMcannot be bad forE. If it doesn’t, then let’s look at the firstjwhere it doesn’t. After a finite number of iterations, every iteration must have mean(|E[prev:this]−flip|)>q′. However, this will causebad(i)to decrease by a positive quantity that’s at least proportional tobound - bad(i); therefore, after a finite number of such iterations, we must reach bad(i)<0. So ifMis bad forEthen for each value ofiwe will eventually make bad(i)<0 and then move on to the next value ofi. This impliesMis not bad forE.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)iid∼Bern(q). When computing p(n), M can’t do appreciably better than Laplace’s law of succession, which will give it standard error √q(1−q)log(n), and relative badness ∼q(1−q)log(n)(1q+11−q)=1log(n) (relative to the q-advisor) on average. For i≤n, and n≫0, the greatest deviation of the badness from the ∑ij=21log(j)≥i−1log(i) trend is ≈√2nloglog(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.