I am trying to compare Epoch Greedy in Langford & Zhang's paper and the epsilon-greedy approach for contextual bandits as in Chen et al, 2020. My question is that are these the same algorithms?-- one considers minimizes the regret over a hypothesis class while in the other we minimize the expected cumulative regret for the contextual bandit problem with a finite set of arms and linear regression framework.


1 Answer 1


Are these the same algorithms?

They are different in how we chunk exploration and exploitation. The primary idea of epoch-greedy is as follows: exploration and exploitation are performed sequentially in chunks, either with apriori fixed $T-$steps or with $\ell-$steps (epochs). It means we do $\ell-$steps exploration before doing $\ell-$steps of exploitation or some variations of this dynamically, where Langford & Zhang analyse the idea in detail. However, in $\epsilon$-greedy, we alternate between exploring and exploiting with the probability of $\epsilon$ and $1-\epsilon$.

  • $\begingroup$ Thanks. But is there a reason one should expect the same rates of convergence for the cumulative regret the two algorithms? I ask because it looks like in essence they try to do the same thing- in one controlling the epoch sizes and in the other controlling the probability of exploration. $\endgroup$
    – user111092
    Oct 3, 2022 at 3:06
  • 1
    $\begingroup$ Good point.There might be a regime where two algorithms produce similar regret bounds. It looks like an open research. However, there is a hint in Langford & Zhang's analysis that structure of hypothesis space would determine this equivalence. $\endgroup$ Oct 3, 2022 at 9:06
  • $\begingroup$ Ok thanks. I just wanted to make sure I am not missing on something trivial. $\endgroup$
    – user111092
    Oct 3, 2022 at 18:06

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.