I'm reading the following paper on the epoch greedy algorithm for the contextual bandits problem. I have two questions


  1. I'm unsure how they've used the Bernstein inequality on page 6 to conclude $\mu_{n}(\mathcal{H},1) \leq c^{-1} \sqrt{k \mathrm{ln}(m)/n}$. Could someone please elaborate on this as it seems Bernsteins inequality seems to measure whp the deviation of a sum of random variables from it's mean. Where as the regret bound $\mu_{n}(\mathcal{H},1)$ is defined as the expected regret from the empirically best policy from the absolute best policy. Could someone fill in the detail?

  2. Can we get any reasonable estimate for the constant $c$ if i was to try and implement this in practice?

I'd really appreciate any help, Thanks.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.