Chernoff Bounds
- multiplicative Chernoff bound 라는 것이 bandit algorithm 에 대한 offline evaluation 에서 나왔다.
- Chernoff bound 는 tail probabilities 에서 지수적으로 (exponentially) 줄어드는 bound 를 계산하기 위한 방법이라고 한다.
- Multiplicative Chernoff Bound
- 특정 assumption: the statement of the bound for the simple case of a sum of independent Bernoulli trials, i.e. the case in which each random variable only takes the values 0 or 1.