We present regret minimization algorithms for the contextual multi-armed bandit (CMAB) problem over $K$ actions in the presence of delayed feedback, a scenario where loss observations arrive with delays chosen by an adversary. As a preliminary result, assuming direct access to a finite policy class $\Pi$ we establish an optimal expected regret bound of $ O (\sqrt{ KT \log |\Pi|} + \sqrt{ D \log |\Pi|)} $ where $D$ is the sum of delays. For our main contribution, we study the general function approximation setting over a (possibly infinite) contextual loss function class $ \mathcal{ F} $ with access to an online least-square regression oracle $\mathcal{ O}$ over $\mathcal{ F}$. In this setting, we achieve an expected regret bound of $O(\sqrt{ KT\mathcal{ R}_T(\mathcal{ O})} + \sqrt{ d_{ \max} D \beta})$ assuming FIFO order, where $d_{ \max}$ is the maximal delay, $\mathcal{ R}_T(\mathcal{ O})$ is an upper bound on the oracle's regret and $\beta$ is a stability parameter associated with the oracle. We complement this general result by presenting a novel stability analysis of a Hedge-based version of Vovk's aggregating forecaster as an oracle implementation for least-square regression over a finite function class $\mathcal{ F}$ and show that its stability parameter $\beta$ is bounded by $\log |\mathcal{ F}|$, resulting in an expected regret bound of $O(\sqrt{ KT \log |\mathcal{ F}|} + \sqrt{ d_{ \max} D \log |\mathcal{ F}|})$ which is a $\sqrt{ d_{ \max}}$ factor away from the lower bound of $\Omega(\sqrt{ KT \log |\mathcal{ F}|} + \sqrt{ D \log |\mathcal{ F}|})$ that we also present.
Categories: cs.LG