Optimal Exploration-Exploitation in a Multi-armed Bandit Problem with Non-stationary Rewards
In a multi-armed bandit (MAB) problem a gambler needs to choose at each round of play one of K arms, each characterized by an unknown reward distribution. Reward realizations are only observed when an arm is selected, and the gambler's objective is to maximize cumulative expected earnings over some planning horizon of length T. To do this, the gambler needs to acquire information about arms (exploration) while simultaneously optimizing immediate rewards (exploitation). The gambler's policy is measured relative to a (static) oracle that knows the identity of the best arm a priori.