Learning a coin's bias (localized)
Write $p=p_0=1-q$. We may assume that $\epsilon&lt;\eta \le p\le 1/2$. Then the sample complexity is of order $\log(1/\delta)$ times the reciprocal of the relative entropy  $D((p,q)||(p+\epsilon,q-\epsilon))$. 
This yields sample complexity  $\Theta(p\epsilon^{-2}\log(1/\delta))$.