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
. This maximum is attained exactly if we spread the number of pulls evenly amongst all the
arms (convince yourself of this, should hopefully not be too hard to see). Hence, all the arms (including the arm
as defined in the notes) will be pulled
times.
Using above upper bound, the total number of pulls of all arms except for arm
is lower bounded by
.
Best,
Thomas
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 n](https://moodlearchive.epfl.ch/2022-2023/filter/tex/pix.php/7b8b965ad4bca0e41ab51de7b31363a1.gif)
![K K](https://moodlearchive.epfl.ch/2022-2023/filter/tex/pix.php/a5f3c6a11b03839d46af9fb43c97c188.gif)
![i i](https://moodlearchive.epfl.ch/2022-2023/filter/tex/pix.php/865c0c0b4ab0e063e5caa3387c1a8741.gif)
![n/K n/K](https://moodlearchive.epfl.ch/2022-2023/filter/tex/pix.php/8437936d4a9554ef2f1eb2deb6a99f46.gif)
Using above upper bound, the total number of pulls of all arms except for arm
![i i](https://moodlearchive.epfl.ch/2022-2023/filter/tex/pix.php/865c0c0b4ab0e063e5caa3387c1a8741.gif)
![(K-1) *n/K = (1-1/K)n (K-1) *n/K = (1-1/K)n](https://moodlearchive.epfl.ch/2022-2023/filter/tex/pix.php/6d54cd7ae41bebbe0616a530844e19c1.gif)
Best,
Thomas