Standard Multi-Armed Bandit (MAB) problems assume that the arms are independent. However, in many application scenarios, the information obtained by playing an arm provides information about the remainder of the arms. Hence, in such applications, this informativeness can and should be exploited to enable faster convergence to the optimal solution. In this paper, we introduce and formalize the Global MAB (GMAB), in which arms are globally informative through a global parameter, i.e., choosing an arm reveals information about all the arms. We propose a greedy policy for the GMAB which always selects the arm with the highest estimated expected reward, and prove that it achieves bounded parameter-dependent regret. Hence, this policy selects suboptimal arms only finitely many times, and after a finite number of initial time steps, the optimal arm is selected in all of the remaining time steps with probability one. In addition, we also study how the informativeness of the arms about each other's rewards affects the speed of learning. Specifically, we prove that the parameter-free (worst-case) regret is sublinear in time, and decreases with the informativeness of the arms. We also prove a sublinear in time Bayesian risk bound for the GMAB which reduces to the well-known Bayesian risk bound for linearly parameterized bandits when the arms are fully informative. GMABs have applications ranging from drug and treatment discovery to dynamic pricing.
Another seemingly related learning scenario is the experts setting @cite_20 , where after an arm is chosen, the rewards of all arms are observed and their estimated rewards is updated. Hence, there is no tradeoff between exploration and exploitation and finite regret bounds can be achieved in an expert system with finite number of arms and stochastic arm rewards. However, unlike in the expert setting, the GMABs achieve finite regret bounds while observing the reward of the selected arm. Hence, the arm reward estimation procedure in GMABs requires forming reward estimates by collectively considering the observed rewards from all the arms, which is completely different than in the expert systems, in which the expected reward of an arm is estimated only by using the past reward observations from that arm.
@cite_20
2148250692
We consider the restless multi-armed bandit (RMAB) problem with unknown dynamics. At each time, a player chooses K out of N (N > K) arms to play. The state of each arm determines the reward when the arm is played and transits according to Markovian rules no matter the arm is engaged or passive. The Markovian dynamics of the arms are unknown to the player. The objective is to maximize the long-term expected reward by designing an optimal arm selection policy. The performance of a policy is measured by regret, defined as the reward loss with respect to the case where the player knows which K arms are the most rewarding and always plays these K best arms. We construct a policy, referred to as Restless Upper Confidence Bound (RUCB), that achieves a regret with logarithmic order of time when an arbitrary nontrivial bound on certain system parameters is known. When no knowledge about the system is available, we extend the RUCB policy to achieve a regret arbitrarily close to the logarithmic order. In both cases, the system achieves the maximum average reward offered by the K best arms. Potential applications of these results include cognitive radio networks, opportunistic communications in unknown fading environments, and financial investment.