Follow-ups Also Matter: Improving Contextual Bandits via Post-serving
  Contexts
Chaoqi Wang Ziyu Ye Zhe Feng Ashwinkumar Badanidiyuru Haifeng Xu
Standard contextual bandit problem assumes that all the relevant contexts are
observed before the algorithm chooses an arm. This modeling paradigm, while
useful, often falls short when dealing with problems in which valuable
additional context can be observed after arm selection. For example, content
recommendation platforms like Youtube, Instagram, Tiktok also observe valuable
follow-up information pertinent to the user's reward after recommendation
(e.g., how long the user stayed, what is the user's watch speed, etc.). To
improve online learning efficiency in these applications, we study a novel
contextual bandit problem with post-serving contexts and design a new
algorithm, poLinUCB, that achieves tight regret under standard assumptions.
Core to our technical proof is a robustified and generalized version of the
well-known Elliptical Potential Lemma (EPL), which can accommodate noise in
data. Such robustification is necessary for tackling our problem, and we
believe it could also be of general interest. Extensive empirical tests on both
synthetic and real-world datasets demonstrate the significant benefit of
utilizing post-serving contexts as well as the superior performance of our
algorithm over the state-of-the-art approaches.