Adversarial Bandits Robust to Switching Targets
We study the adversarial bandit problem under $S$ number of switching best
arms for unknown $S$. For handling this problem, we adopt the master-base
framework using the online mirror descent method (OMD). We first provide a
master-base algorithm with basic OMD, achieving
$\tilde{O}(S^{1/2}K^{1/3}T^{2/3})$. For improving the regret bound with respect
to $T$, we propose to use adaptive learning rates for OMD to control variance
of loss estimators, and achieve
$\tilde{O}(\min\{\mathbb{E}[\sqrt{SKT\rho_T(h^\dagger)}],S\sqrt{KT}\})$, where
$\rho_T(h^\dagger)$ is a variance term for loss estimators.