Combinatorial Semi-Bandit in the Non-Stationary Environment - Chen, Wei; Wang, Liwei; Zhao, Haoyu; Zheng, Kai (Conference on Uncertainty in Artificial Intelligence (UAI) 2021, 2021)
In this paper, we investigate the non-stationary combinatorial semi-bandit problem, both in the switching case and in the dynamic case. In the general case where (a) the reward function is non-linear, (b) arms may be probabilistically triggered, and (c) only approximate offline oracle exists [wang2017improving], our algorithm achieves Õ(√ST) distribution-dependent regret in the switching case, and Õ(V1/3T2/3) in the dynamic case, where S is the number of switchings and V is the sum of the total ''distribution changes''. The regret bounds in both scenarios are nearly optimal, but our algorithm needs to know the parameter S or V in advance. We further show that by employing another technique, our algorithm no longer needs to know the parameters S or V but the regret bounds could become suboptimal. In a special case where the reward function is linear and we have an exact oracle, we design a parameter-free algorithm that achieves nearly optimal regret both in the switching case and in the dynamic case without knowing the parameters in advance.