This will be unparseable to anyone except maybe ten people here. What the hell, I’m posting it anyway.
Consider game 3 from my earlier post: a possibly uncomputable sequence of bits comes in, you’re trying to guess the next bit, the payoff for each correct guess is $1. Obviously any deterministic strategy can be humiliated by a sequence of bits that’s chosen to make it always guess wrong. User paulfchristiano suggested that multiplicative weights could yield a randomized strategy that does at most a constant worse than any human in expectation. I noted that, unlike the Solomonoff mixture, multiplicative weights over lower-semicomputable randomized strategies is not itself lower-semicomputable (several pages of algebra omitted), so we don’t have a strategy that’s optimal within its own class. Then I found some slides by Hutter that include a handy table showing how unusual it is for a class do be dominated by a measure within that same class.
So here’s the question: is there an analog of “dominant lower-semicomputable semimeasure” for some class of games other than the log-score game? Desiderata: I guess it must correspond to randomized strategies (because deterministic ones are not enough), it must play at most an additive constant worse than any human in expectation (or maybe a multiplicative constant that can be made arbitrarily close to 1 by parameter choice, as with multiplicative weights), and it must be good within its own class of computability (not just superior to all members of some lower class). As far as I can tell, the literature has no answer to this question, and I already spent about a week on it with no success. Anyone here have more understanding than me?
A math problem I’m trying to figure out now
This will be unparseable to anyone except maybe ten people here. What the hell, I’m posting it anyway.
Consider game 3 from my earlier post: a possibly uncomputable sequence of bits comes in, you’re trying to guess the next bit, the payoff for each correct guess is $1. Obviously any deterministic strategy can be humiliated by a sequence of bits that’s chosen to make it always guess wrong. User paulfchristiano suggested that multiplicative weights could yield a randomized strategy that does at most a constant worse than any human in expectation. I noted that, unlike the Solomonoff mixture, multiplicative weights over lower-semicomputable randomized strategies is not itself lower-semicomputable (several pages of algebra omitted), so we don’t have a strategy that’s optimal within its own class. Then I found some slides by Hutter that include a handy table showing how unusual it is for a class do be dominated by a measure within that same class.
So here’s the question: is there an analog of “dominant lower-semicomputable semimeasure” for some class of games other than the log-score game? Desiderata: I guess it must correspond to randomized strategies (because deterministic ones are not enough), it must play at most an additive constant worse than any human in expectation (or maybe a multiplicative constant that can be made arbitrarily close to 1 by parameter choice, as with multiplicative weights), and it must be good within its own class of computability (not just superior to all members of some lower class). As far as I can tell, the literature has no answer to this question, and I already spent about a week on it with no success. Anyone here have more understanding than me?