FlipIt and the Cramér-Rao BoundPeter Schmidt-Nielsen
MIT, Center for Bits and Atoms

August 16, 2011

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundFlipIt

FlipIt is a two player game (with players 0 and 1), with threebasic rules:

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundFlipIt

FlipIt is a two player game (with players 0 and 1), with threebasic rules:
There is a common resource that player i may capture at any
time by paying a cost of ki .

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundFlipItFlipIt is a two player game (with players 0 and 1), with threebasic rules:
There is a common resource that player i may capture at any
time by paying a cost of ki .
For each second that the resource is held by a player he or she
gains one point.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundFlipIt

FlipIt is a two player game (with players 0 and 1), with threebasic rules:
There is a common resource that player i may capture at any
time by paying a cost of ki .
For each second that the resource is held by a player he or she
gains one point.
The players don’t know who owns the resource at any given
time, except that when a player captures the resource he or
she learns something about the past history of who owned it.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundFlipIt

FlipIt is a two player game (with players 0 and 1), with threebasic rules:
There is a common resource that player i may capture at any
time by paying a cost of ki .
For each second that the resource is held by a player he or she
gains one point.
The players don’t know who owns the resource at any given
time, except that when a player captures the resource he or
she learns something about the past history of who owned it.
Here we only consider the case where a player capturing theresource learns only the last move (and thus who made it).

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

Open Problems

What is the asymptotically optimal non-adaptive strategy against
an adaptive opponent?

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

Open Problems

What is the asymptotically optimal non-adaptive strategy against
an adaptive opponent?
What is the non-asymptotic optimal adaptive strategy against thecurrently best known non-adaptive strategy (playing as a Poissonprocess)?

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

The Setup

Let player 0 be a non-adaptive Poisson process playing at a rate of
α = λ, playing at least once in time period τ with probability
1 − e −λτ .

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

The Setup

Let player 0 be a non-adaptive Poisson process playing at a rate of
α = λ, playing at least once in time period τ with probability
1 − e −λτ .
Player 1 is adaptive, and would like to learn λ to figure out theoptimal capture rate.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

The Setup

Let player 0 be a non-adaptive Poisson process playing at a rate of
α = λ, playing at least once in time period τ with probability
1 − e −λτ .
Player 1 is adaptive, and would like to learn λ to figure out the
optimal capture rate.
Player 1 can’t learn λ without capturing, but each capture has acost of k1 .

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

The Setup

Let player 0 be a non-adaptive Poisson process playing at a rate of
α = λ, playing at least once in time period τ with probability
1 − e −λτ .
Player 1 is adaptive, and would like to learn λ to figure out theoptimal capture rate.
Player 1 can’t learn λ without capturing, but each capture has acost of k1 .
If player 1 plays too fast, his or her moves might be consecutive,
which will waste points and give less information about λ.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

The Setup

Let player 0 be a non-adaptive Poisson process playing at a rate of
α = λ, playing at least once in time period τ with probability
1 − e −λτ .
Player 1 is adaptive, and would like to learn λ to figure out theoptimal capture rate.
Player 1 can’t learn λ without capturing, but each capture has acost of k1 .
If player 1 plays too fast, his or her moves might be consecutive,
which will waste points and give less information about λ.
In a finite game player 1 has to trade off certainty of λ withspending points (needless captures) and wasting time (needlesscaution).

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundA Tentative Information Theoretic Bound

The Cramér-Rao bound limits the variance of an unbiased1
estimator of an unknown parameter θ of a distribution X fromobservations of X .

1This is a big assumption!
Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundA Tentative Information Theoretic Bound

The Cramér-Rao bound limits the variance of an unbiased1
estimator of an unknown parameter θ of a distribution X fromobservations of X .
The variance of our estimate of θ is at least 1/I, where I is theFisher information of our observations of X .

1This is a big assumption!
Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundA Tentative Information Theoretic Bound

Generous assumption:Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundA Tentative Information Theoretic Bound

Generous assumption:
Every time player 1 captures, he or she learns a valid samplingof the mean time to a player 0’s plays – player 1 never plays“too fast”.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundA Tentative Information Theoretic Bound

Generous assumption:
Every time player 1 captures, he or she learns a valid samplingof the mean time to a player 0’s plays – player 1 never plays“too fast”.
If we make n plays, we get n observations of player 0’s playing
rate, and the minimum variance in our estimate of λ possible is...

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound*I(X , λ) =nY∂lnλe −λxi
∂λ!!2 +(1)

i=1

*=
*=

∂∂λn ln(λ) − λnX!!2 +xi(2)i=1n−λnX!2 +xii=1n(3)nn

XXn22n X= 2−
hxi i +
hxi xj iλλi=1=n2λ2−(4)i=1 j=1nnn
E X
DXX
2 −λ(xi +xj )+λ e+hxi2 i (5)22n2λi=1 j=1,j6=i

i=1λ2

1=I(X , λ)n(6)Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundTactic OneAs player 0’s strategy is memoryless, and by Ron’s first theorem,
player 1 can’t play better after n plies than a non-adaptive player
who guesses λ from a distribution of variance λ2 /n. Thus, we canbound the quality of player 1’s play at any point in time.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundTactic One

As player 0’s strategy is memoryless, and by Ron’s first theorem,
player 1 can’t play better after n plies than a non-adaptive player
who guesses λ from a distribution of variance λ2 /n. Thus, we canbound the quality of player 1’s play at any point in time.
This proof strategy works against any non-adaptive player 0
strategy parameterized by a set of unknowns to learn, assuming we
can make a reasonable approximation of the Fisher information.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundTactic One

As player 0’s strategy is memoryless, and by Ron’s first theorem,
player 1 can’t play better after n plies than a non-adaptive player
who guesses λ from a distribution of variance λ2 /n. Thus, we canbound the quality of player 1’s play at any point in time.
This proof strategy works against any non-adaptive player 0strategy parameterized by a set of unknowns to learn, assuming we
can make a reasonable approximation of the Fisher information.
... assuming that the optimal adaptive player estimates λ with nobias, the Cramér-Rao bound holds, and we have bounded thequality of the best player 1 strategy.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundTactic One

As player 0’s strategy is memoryless, and by Ron’s first theorem,player 1 can’t play better after n plies than a non-adaptive player
who guesses λ from a distribution of variance λ2 /n. Thus, we canbound the quality of player 1’s play at any point in time.
This proof strategy works against any non-adaptive player 0
strategy parameterized by a set of unknowns to learn, assuming wecan make a reasonable approximation of the Fisher information.
... assuming that the optimal adaptive player estimates λ with nobias, the Cramér-Rao bound holds, and we have bounded thequality of the best player 1 strategy.
But we don’t want to assume the best strategy consists of anunbiased estimator, so we try a different tactic...

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundTactic Two

Define a given bound we would like to prove on player 1’s qualityof play, and let any player 1 strategy that is greater than thisbound a “FlipIt shark”.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundTactic Two

Define a given bound we would like to prove on player 1’s qualityof play, and let any player 1 strategy that is greater than thisbound a “FlipIt shark”.
Construct a unbiased estimator that can estimate λ from thehistory of any game between a FlipIt shark and player 0.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundTactic Two

Define a given bound we would like to prove on player 1’s qualityof play, and let any player 1 strategy that is greater than thisbound a “FlipIt shark”.
Construct a unbiased estimator that can estimate λ from thehistory of any game between a FlipIt shark and player 0.
If this unbiased estimator beats the Cramér-Rao bound, bycontradiction, FlipIt sharks don’t exist, and the bound is proven– regardless of how the given shark actually works.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundOur new Cramér-Rao bound, expanded for two player 1 plies:
*
2 +1
∂
ln(P[X0 = x0 , X1 = x1 ])= 1/I(X0 , X1 , λ)
∂λ..
.

(8)
*

= 1/(7)2− x0 − x1 + wλ

2 +(9)Where xi are the times of the first two observations, and where w
is the period of time waited between the first two plies.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundOur new Cramér-Rao bound, expanded for two player 1 plies:
*
2 +1
∂
ln(P[X0 = x0 , X1 = x1 ])= 1/I(X0 , X1 , λ)
∂λ..
.

(8)
*

= 1/(7)2− x0 − x1 + w
λ2 +(9)Where xi are the times of the first two observations, and where w
is the period of time waited between the first two plies.
A FlipIt shark that manages to estimate λ well enough from thefirst ply to gain the maximal amount of information from thesecond ply without wasting too much time waiting might end up
violating this bound.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

The End of the Proof – (sketch)

Let our FlipIt shark be any strategy that holds the resource morethan . . . of the time on average.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

The End of the Proof – (sketch)

Let our FlipIt shark be any strategy that holds the resource morethan . . . of the time on average.
This implies that it only attempts to capture the resource while italready controls the resource . . . proportion of the time, and w isno larger than . . . .

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

The End of the Proof – (sketch)

Let our FlipIt shark be any strategy that holds the resource morethan . . . of the time on average.
This implies that it only attempts to capture the resource while italready controls the resource . . . proportion of the time, and w isno larger than . . . .
Thus, we construct an estimator of λ that gets . . . samples ofplayer 0’s Poisson process after . . . plies, and thus violates theCramér-Rao bound.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound

The End of the Proof – (sketch)

Let our FlipIt shark be any strategy that holds the resource morethan . . . of the time on average.
This implies that it only attempts to capture the resource while italready controls the resource . . . proportion of the time, and w isno larger than . . . .
Thus, we construct an estimator of λ that gets . . . samples ofplayer 0’s Poisson process after . . . plies, and thus violates theCramér-Rao bound.
Sharks don’t exist, QED.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundRelevant Conclusions

On Ron’s open problem: What’s the optimal non-adaptive strategy
against an adaptive opponent?

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundRelevant Conclusions

On Ron’s open problem: What’s the optimal non-adaptive strategy
against an adaptive opponent?
A Poisson process minimizes the Fisher information of anon-adaptively chosen observations, and I think it minimizes theFisher information given by a series of adaptively timed
observations.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao BoundRelevant Conclusions

On Ron’s open problem: What’s the optimal non-adaptive strategy
against an adaptive opponent?
A Poisson process minimizes the Fisher information of a
non-adaptively chosen observations, and I think it minimizes theFisher information given by a series of adaptively timed
observations.
If true, this implies that a Poisson process kills as many sharks as
possible with the Cramér-Rao bound in the non-asymptotic versionof FlipIt.

Peter Schmidt-Nielsen

FlipIt and the Cramér-Rao Bound