Asymptotic Allocation Rules for a Class of Dynamic Multi-armed Bandit Problems
This provides a unified framework for handling time-varying option characteristics in bandit problems, which is incremental but useful for applications like resource allocation.
The paper tackles the problem of dynamic multi-armed bandits with time-varying rewards modeled by linear stochastic systems, showing that combining Upper Confidence Bound algorithms with efficient reward estimators ensures logarithmic bounds on expected cumulative regret.
This paper presents a class of Dynamic Multi-Armed Bandit problems where the reward can be modeled as the noisy output of a time varying linear stochastic dynamic system that satisfies some boundedness constraints. The class allows many seemingly different problems with time varying option characteristics to be considered in a single framework. It also opens up the possibility of considering many new problems of practical importance. For instance it affords the simultaneous consideration of temporal option unavailabilities and the depen- dencies between options with time varying option characteristics in a seamless manner. We show that, for this class of problems, the combination of any Upper Confidence Bound type algorithm with any efficient reward estimator for the expected reward ensures the logarithmic bounding of the expected cumulative regret. We demonstrate the versatility of the approach by the explicit consideration of a new example of practical interest.