Useful Proof Tricks for Multi-armed Bandits
Published:
Some notes for algorithm/proof tricks for MAB. Keep updating…
Probability
- If A then B, or A implies B, or A⇒B, then $\Pr(B) \ge \Pr(A)$. This is because B occurs every time A occurs, but B might also occur at some other times as well. E.g., A=”dice 1”, B=”dice 1” or “dice 6”, A⇒B.
- Only If A occurs, B occurs, or B⇒A, then $\Pr(A)\ge \Pr(B).$
- $\Pr(A_1>A_2 \cap B_1>B_2)\le \Pr(A_1+B_1>A_2+B_2)\le\Pr(A_1>A_2) + \Pr(B_1>B_2)$. This is because $A_1+B_1>A_2+B_2$ implies $A_1>A_2$ or $B_1>B_2$ (the reverse cannot happen).