COM-406: Page 72 polycopie

Hello,

I really don't understand why, in page 72 in the first paragraph, it is said that "If $i=1$ then at least (1- $1/K$ )n times we do not choose arm 1. Can someone explain formally how do we obtain this result ?

Best regards,

Re: Page 72 polycopie

by Thomas Weinberger - Friday, 11 November 2022, 18:29

Hi Gabin,

We look for an upper bound on the amount of times the arm with the least amount of pulls is pulled, for a fixed total number of pulls

$n$ . This maximum is attained exactly if we spread the number of pulls evenly amongst all the

$K$ arms (convince yourself of this, should hopefully not be too hard to see). Hence, all the arms (including the arm

$i$ as defined in the notes) will be pulled

$n/K$ times.

Using above upper bound, the total number of pulls of all arms except for arm

$i$ is lower bounded by

$(K-1) *n/K = (1-1/K)n$ .

Best,
Thomas