Advanced MiniMax Optimality Strategy in Bandit Problems

Nowadays, with the development of the Internet, recommending personalized information for every user becomes economically valuable. How to properly recommend to users the content they prefer is important. Mostly, bandit strategies are useful for this problem. As one of the most time-saving algorithms, Minimax Optimal Strategy (MOSS) performs well in most data sets. However, the traditional MOSS algorithm applies a conservative strategy in order to minimize the cumulative regrets in the worst situations. This strategy will over-explore the bandit models and spend too much time exploring every arm at the initial stage. This means the MOSS strategy cannot fully take advantage of the known information and then the accuracy and efficiency will be lower. In real life, people have a lot of Internet information to look through and they will not stay on one website or one advertisement for a long time. So, designing an efficient algorithm that performs well in all situations and can make good use of the known knowledge to do quick exploitation becomes so important. Therefore, this research aims to develop an advanced MOSS algorithm that can properly explore each of the bandit arms and improve the performance of the exploitation phase. By achieving this goal, this research adds an enhancement factor on the confidence bound part to speed up the exploration process. The research bases on the MovieLens data set and the data set is divided into 18 categories (arms) according to its genre attribute. Then apply this new advanced MOSS strategy to the designed data set and compare its performance with normal MOSS and UCB algorithms. Results display that the advanced MOSS strategys selection provides higher total rewards and lower average cumulative regrets than others with the advantage of time-saving. This shows the improvement of the advanced MOSS strategy in balancing the exploitation and exploration phases.