Balancing exploration and exploitation with information and randomization