Skip to main content
edited tags; deleted 20 characters in body
Source Link

Motivation

I'm interested in whether Levin and Solomonoff's results on "universal semimeasures" can be extended to other settings. One case that especially interests me is finding "universal" strategies in the one-player game "guess the next bit, win 1 dollar if you're right, lose 1 dollar if you're wrong" played over infinite (and possibly uncomputable) bit sequences. Obviously any deterministic strategy (whether computable or incomputable) can be humiliated by an input sequence that makes it always guess wrong, so I shifted my attention to computable randomized strategies. Here's a formalization:

The question

Let's define a "supermartingale with bounded increments" (SWBI) as a function M on finite bit sequences S that satisfies the following conditions:

  1. M(empty sequence) = 0

  2. for any S, (M(S#0) + M(S#1))/2 ≤ M(S)

  3. for any S, M(S#0) - M(S) ≤ 1 and M(S#1) - M(S) ≤ 1

Question 1: does the set of all lower-semicomputable SWBIs contain an element X that dominates any other element Y up to an additive constant (which may depend on Y but doesn't depend on S)?

Question 2: if the answer to question 1 is "no", is there a lower-semicomputable SWBI that doesn't lose to any other by more than epsilon per step?

Partial result that may be helpful

Multiplicative weights over all lower-semicomputable SWBIs yields an SWBI that fits the conditions of question 2, but I don't know if it's lower-semicomputable, though it is certainly limit-computable.

Motivation

I'm interested in whether Levin and Solomonoff's results on "universal semimeasures" can be extended to other settings. One case that especially interests me is finding "universal" strategies in the one-player game "guess the next bit, win 1 dollar if you're right, lose 1 dollar if you're wrong" played over infinite (and possibly uncomputable) bit sequences. Obviously any deterministic strategy (whether computable or incomputable) can be humiliated by an input sequence that makes it always guess wrong, so I shifted my attention to computable randomized strategies. Here's a formalization:

The question

Let's define a "supermartingale with bounded increments" (SWBI) as a function M on finite bit sequences S that satisfies the following conditions:

  1. M(empty sequence) = 0

  2. for any S, (M(S#0) + M(S#1))/2 ≤ M(S)

  3. for any S, M(S#0) - M(S) ≤ 1 and M(S#1) - M(S) ≤ 1

Question 1: does the set of all lower-semicomputable SWBIs contain an element X that dominates any other element Y up to an additive constant (which may depend on Y but doesn't depend on S)?

Question 2: if the answer to question 1 is "no", is there a lower-semicomputable SWBI that doesn't lose to any other by more than epsilon per step?

Partial result that may be helpful

Multiplicative weights over all lower-semicomputable SWBIs yields an SWBI that fits the conditions of question 2, but I don't know if it's lower-semicomputable, though it is certainly limit-computable.

I'm interested in whether Levin and Solomonoff's results on "universal semimeasures" can be extended to other settings. One case that especially interests me is finding "universal" strategies in the one-player game "guess the next bit, win 1 dollar if you're right, lose 1 dollar if you're wrong" played over infinite (and possibly uncomputable) bit sequences. Obviously any deterministic strategy (whether computable or incomputable) can be humiliated by an input sequence that makes it always guess wrong, so I shifted my attention to computable randomized strategies. Here's a formalization:

The question

Let's define a "supermartingale with bounded increments" (SWBI) as a function M on finite bit sequences S that satisfies the following conditions:

  1. M(empty sequence) = 0

  2. for any S, (M(S#0) + M(S#1))/2 ≤ M(S)

  3. for any S, M(S#0) - M(S) ≤ 1 and M(S#1) - M(S) ≤ 1

Question 1: does the set of all lower-semicomputable SWBIs contain an element X that dominates any other element Y up to an additive constant (which may depend on Y but doesn't depend on S)?

Question 2: if the answer to question 1 is "no", is there a lower-semicomputable SWBI that doesn't lose to any other by more than epsilon per step?

Partial result that may be helpful

Multiplicative weights over all lower-semicomputable SWBIs yields an SWBI that fits the conditions of question 2, but I don't know if it's lower-semicomputable, though it is certainly limit-computable.

Source Link

Lower-semicomputable supermartingales with bounded increments

Motivation

I'm interested in whether Levin and Solomonoff's results on "universal semimeasures" can be extended to other settings. One case that especially interests me is finding "universal" strategies in the one-player game "guess the next bit, win 1 dollar if you're right, lose 1 dollar if you're wrong" played over infinite (and possibly uncomputable) bit sequences. Obviously any deterministic strategy (whether computable or incomputable) can be humiliated by an input sequence that makes it always guess wrong, so I shifted my attention to computable randomized strategies. Here's a formalization:

The question

Let's define a "supermartingale with bounded increments" (SWBI) as a function M on finite bit sequences S that satisfies the following conditions:

  1. M(empty sequence) = 0

  2. for any S, (M(S#0) + M(S#1))/2 ≤ M(S)

  3. for any S, M(S#0) - M(S) ≤ 1 and M(S#1) - M(S) ≤ 1

Question 1: does the set of all lower-semicomputable SWBIs contain an element X that dominates any other element Y up to an additive constant (which may depend on Y but doesn't depend on S)?

Question 2: if the answer to question 1 is "no", is there a lower-semicomputable SWBI that doesn't lose to any other by more than epsilon per step?

Partial result that may be helpful

Multiplicative weights over all lower-semicomputable SWBIs yields an SWBI that fits the conditions of question 2, but I don't know if it's lower-semicomputable, though it is certainly limit-computable.