I'm interested in analyzing a variant of the multi-armed bandit problem with pure exploration. In this variant, in each round we receive samples from two distributions and we need to estimate which distribution has smaller mean. The distribution whose mean was judged to be smaller will return in the next round and then the algorithm needs decide which mean is smaller: that of a new 'fresh' distribution or the previously best?

More precisely the game is as follows. In round $t = 1$, Nature samples $p_1$ from a uniform distribution over $[0,1]$. The variables $p$ will play the role of success probability of the Bernoulli data. We initialize a variable $b = 1$ which is used by the algorithm to keep track of the distribution with smallest mean so far.

Now for every round $t = 2,\ldots,N$:

  • Nature samples $p_t$ from a uniform distribution over $[0,1]$.
  • The algorithm observes $x \sim \text{Bernoulli}(p_t)$ and $y \sim \text{Bernoulli}(p_b)$
  • If $x < y$ the algorithm sets $b \leftarrow t$ (the algorithm thinks that $p_t < p_b$)
  • Store the value $p_t$ in $R_t$, this is the regret

Now I'm interested in whether it's possible to prove that $$\mathbb{E}~ R_{t+1} < \mathbb{E}~ R_{t}~~?$$ where $\mathbb{E}$ is the expectation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.