  The multi-armed bandit (MAB) models have attracted significant research
attention due to their applicability and effectiveness in various real-world
scenarios such as resource allocation, online advertising, and dynamic pricing.
As an important branch, the adversarial MAB problems with delayed feedback have
been proposed and studied by many researchers recently where a conceptual
adversary strategically selects the reward distributions associated with each
arm to challenge the learning algorithm and the agent experiences a delay
between taking an action and receiving the corresponding reward feedback.
However, the existing models restrict the feedback to be generated from only
one user, which makes models inapplicable to the prevailing scenarios of
multiple users (e.g. ad recommendation for a group of users). In this paper, we
consider that the delayed feedback results are from multiple users and are
unrestricted on internal distribution. In contrast, the feedback delay is
arbitrary and unknown to the player in advance. Also, for different users in a
round, the delays in feedback have no assumption of latent correlation. Thus,
we formulate an adversarial MAB problem with multi-user delayed feedback and
design a modified EXP3 algorithm MUD-EXP3, which makes a decision at each round
by considering the importance-weighted estimator of the received feedback from
different users. On the premise of known terminal round index $T$, the number
of users $M$, the number of arms $N$, and upper bound of delay $d_{max}$, we
prove a regret of $\mathcal{O}(\sqrt{TM^2\ln{N}(N\mathrm{e}+4d_{max})})$.
Furthermore, for the more common case of unknown $T$, an adaptive algorithm
AMUD-EXP3 is proposed with a sublinear regret with respect to $T$. Finally,
extensive experiments are conducted to indicate the correctness and
effectiveness of our algorithms.
