<aside> 💡 Google에서는 Regret bound를 강화학습에 적용시키는 연구가 활발해보인다. 기초지식을 위해 아래 강의를 한번 따라가 보자

https://arxiv.org/pdf/1204.5721.pdf (요건 약간 책이라서 이거보고 공부해도 될듯) https://people.eecs.berkeley.edu/~jiantao/2902021spring/material.html https://www.cs.umd.edu/~slivkins/CMSC858G-fall16/

</aside>

마르코프 부등식 (Markov’s inequality)

$X$가 음수가 아닌 랜덤 변수일 때,

$$ P(X\geq t) \leq\frac{E(X)}{t}, \text{ where }t > 0 $$

• Proof

Pros

• 확률변수의 정의가 없어도 기댓값만을 이용해 대략적인 확률을 추정할 수 있다.

체비셰프 부등식 (Chebyshev’s inequality)

$X$가 랜덤 변수일 때,

$$ P(|X-\mu|\geq t)\leq \frac{\sigma^2}{t^2} $$

• Proof

실제 사용시에는 모평균, 모분산은 구하기 어렵다. 그러므로, 표본평균과 표본분산을 대체해서 사용한다.

Pros

• 마르코프 부등식과는 다르게 분산을 알고있을 때 사용.
• 당연히 더 tight한 bound 계산이 가능하다.

Cons

• 가정자체가 대칭성을 가지고 있는 분포이기에 실제로 사용기에 제약조건이 있다.

• 그래서 양측이 아닌 단측 체비셰프 부등식을 사용할 수 있다.

  $$ P(X\geq\mu+t)\leq\frac{\sigma^2}{\sigma^2+t^2} \\ P(X\leq\mu-t)\leq\frac{\sigma^2}{\sigma^2+t^2} $$

변형식