Approximate information maximization for bandit games

Multi-armed bandit problems have raised a vast interest Entropy maximization and free energy minimization in the past decades. They embody the challenge are general physical principles for of balancing exploration and exploitation and have modeling the dynamics of various physical been applied to various different settings such as online systems. Notable examples include modeling recommendation (Bresler et al., 2014), medical trials decision-making within the brain using (Thompson, 1933), dynamic pricing (Den Boer, 2015), the free-energy principle, optimizing the and reinforcement learning-based decision making (Silver accuracy-complexity trade-off when accessing et al., 2016; Ryzhov et al., 2012). Besides the classic hidden variables with the information stochastic version of the multi-armed bandit problem, bottleneck principle (Tishby et al., 2000), and many subsequent extensions have been developed, navigation in random environments using information providing finer models for specific applications. These maximization (Vergassola et al., extensions include linear bandits (Li et al., 2010), 2007). Built on this principle, we propose a many-armed bandits (Bayati et al., 2020), and pure exploration new class of bandit algorithms that maximize problems such as thresholding bandits (Locatelli an approximation to the information of a key et al., 2016) or top-K bandits (Kalyanakrishnan variable within the system.