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 (√KT log |Pi| + √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 F with access to an online least-square regression oracle O over F. In this setting, we achieve an expected regret bound of O(√KTRT(O) + √ dmax D β) assuming FIFO order, where dmax is the maximal delay, RT(O) is an upper bound on the oracle's regret and β 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 F and show that its stability parameter β is bounded by log |F|, resulting in an expected regret bound of O(√KT log |F| + √dmax D log |F|) which is a √dmax factor away from the lower bound of Omega(√KT log |F| + √D log |F|) that we also present.