Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback

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{R}_T(\mathcal{O})}+\sqrt{d_{\max }D\beta })$ assuming FIFO order, where $d_{\max }$ is the maximal delay, $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.