The ε-Greedy Algorithm

Another variation of the Greedy algorithm is the ε-Greedy algorithm. For Explore-then-commit, the amount of forced exploration depends on the settable parameter, T, which again gives rise to the question of how to best set it. For ε-Greedy, we do not explicitly require the algorithm to explore more than one round for each arm. Instead, we leave it to chance to determine when the algorithm should carry on exploitation, and when it should explore a seemingly suboptimal arm.

Formally, an ε-Greedy algorithm is parameterized by a number, ε, between zero and one, denoting the exploration probability of the algorithm. After the first exploration rounds, the algorithm will choose to pull the arm with the greatest running reward average with probability 1 - ε. Otherwise, it will uniformly choose one out of all the available arms (with probability ε). Unlike Explore-then-commit, where we know for sure the algorithm will be forced...