Discussion Forum

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