1
$\begingroup$

I'm reading the following paper

https://arxiv.org/pdf/1003.0146.pdf on building a fair online simulator for contextual bandits. In particular i'm interested in the proof on page 665 of Theorem 1

enter image description here

I don't believe this has been proved rigourously so i wanted to try and prove it myself. Is the following correct?

For any given tuple $(x_{1},\ldots,x_{k},a,r_{a})$ the probability that the policy evaluator adds this tuple to the history $h_{t-1}$ is the same as the probability that the for loop terminates with a match on $(x_{1},\ldots,x_{k},a,r_{a})$. Since the stream is infinite this success can come at any time from $r=1,\ldots,\infty$. The probability that we have a success at time $r=p$ is equal to the probability of having $p-1$ failures and a sucess on the $p$th trial and thus is equal to

$((k-1)/k)^{p-1}P((x_{1},\ldots,x_{k},a,r_{a})\times 1/k$ the total probability of obtaining event $(x_{1},\ldots,x_{k},a,r_{a})$ in the simulated environment at time $h_{t}$ is then

$\sum_{p=1}^{\infty} ((k-1)/k)^{p-1}P((x_{1},\ldots,x_{k},a,r_{a})\times 1/k=P((x_{1},\ldots,x_{k},a,r_{a})$ and thus the policy evaluator is unbiased

Is this correct? If not could someone provide a more detailed proof? Thanks!

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.