Adversarial Bandits against Arbitrary Strategies

We study the adversarial bandit problem against arbitrary strategies, where the difficulty is captured by an unknown parameter S, which is the number of switches in the best arm in hindsight. To handle this problem, we adopt the master-base framework using the online mirror descent method (OMD). We first provide a master-base algorithm with simple OMD, achieving tildeO(S1/2K1/3T2/3), in which T2/3 comes from the variance of loss estimators. To mitigate the impact of the variance, we propose using adaptive learning rates for OMD and achieve tildeO(min√SKTρ,S√KT), where ρ is a variance term for loss estimators.