Multi-armed bandit algorithms - Epsilon greedy algorithm

Key Takeaways

previously we talked about the etc algorithm for the multi-armed bandit problem the epsilon greedy algorithm is a randomized relative of etc the algorithm is described as follows first it chooses each arm once and then subsequently in each round t it chooses empirically best arm with probability one minus epsilon otherwise it chooses an arm uniformly at random let's take a look at an example with two arms let's assume the rewards for these two arms are one subgaussian with a mean of 0.9 and 0.6 we first play each arm once at the third round we know that with the probability 1 minus epsilon we choose the empirically best arm and with probability epsilon we choose a norm at random in this example let's assume epsilon three equals one which means that we have a hundred percent of chance choosing an arm and random here in this example we randomly choose arm 2. now assume at round 4 epsilon 4 is 0.9 which means that with 90 probability we choose an arm at random and ten percent probability we choose the best arm how do we choose let's get a random number from this random number generator here we get point four eight we see that the random number is smaller than epsilon 4 thus we choose an arm at random again this time we choose arm 1. at round 5 assume epsilon 5 is 0.5 which means half of the chance we should choose the best arm half of the chance we should select an arm at random again we use the random number generator to get a random number 0.8 which is greater than 0.5 therefore this time we need to choose the empirically best arm how do we find the best arm let's assume that in the previous four rounds we played arm one gives us a reward of 0.9 arm 2 gives us 0.5 and then arm 2 gives us 0.3 and arm 1 gives us 0.7 the empirical mean estimate for arm 1 is 0.8 and for arm 2 is 0.4 which you play arm one and then we just repeat this whole process over and over again to write this algorithm formally we have action a at time t expressed as follows it is the arg max of the programming estimate with probability y minus epsilon and the uniform selection of an arm with the probability epsilon note that we need to calculate epsilon at each round at epsilon is a function of c k p and delta c is a constant number k is the number of arms p is the number of the current round delta mean is the minimum of mean rewards difference among arms in our example with two arms this delta mean is simply the difference of the main rewards between our two arms so that is the epsilon greedy algorithm for a multi-armed bandit problem