Multi-armed bandit algorithms - ETC Explore then Commit

Key Takeaways

in a multi-armed bandit problem we have a row of slot machines where each machine provides a random rewards from a probability distribution in real life we can consider each machine as different adds a b testing variants or others now we need to figure out which strategy can give us the best reward the simplest algorithm is the etc explore then commit algorithm let's assume that we have two arms depending on your use case the reward distribution may follow any kinds of distributions here we assume that the reward distribution follow a one sub gaussian arm 1 has a mean of 0.5 and arm 2 has a mean of 0.8 the first step of the algorithm is explore where each arm gets played one after another for a number of times the first round arm 1 returns a 0.6 reward second round arm 2 returns 0.7 and then arm 1 returns 0.5 and then arm 2 returns 0.9 if we just look at these four rounds we can calculate the empirical mean of the rewards for each arm we can see that the improper mean for arm 1 is 0.55 and the empirical mean for arm 2 is 0.8 arm 2 wins here is the mathematical equation of the simple coming calculation where the entire mean mu of the of the arm i around t equals to one of the sum of this indicator function times the sum of the indicator function times the reward at each step again after four rounds the improvement of arm two is greater than arm one if we only consider this four rounds we can say that arm two is better and thus in the commit phase we only use arm 2. the overall algorithm can be summarized as follows in round t we can choose the action a t where it equals t mod k plus 1 if t is less than or equal to mk meaning that we explore k arms m times in the exploration phase if t is greater than mk we choose the action a t that is the arc max of the empirical mean of the rewards of arm i during exploration if we only have two arms k equals two then it is the best to choose m as the max of one or this other term which is a function of delta the mean difference between two arms and n the total number of rounds so that is the etc algorithm for a problem