Online Scoring with Delayed Information: A Convex Optimization Viewpoint
  We consider a system where agents enter in an online fashion and are
evaluated based on their attributes or context vectors. There can be practical
situations where this context is partially observed, and the unobserved part
comes after some delay. We assume that an agent, once left, cannot re-enter the
system. Therefore, the job of the system is to provide an estimated score for
the agent based on her instantaneous score and possibly some inference of the
instantaneous score over the delayed score. In this paper, we estimate the
delayed context via an online convex game between the agent and the system. We
argue that the error in the score estimate accumulated over $T$ iterations is
small if the regret of the online convex game is small. Further, we leverage
side information about the delayed context in the form of a correlation
function with the known context. We consider the settings where the delay is
fixed or arbitrarily chosen by an adversary. Furthermore, we extend the
formulation to the setting where the contexts are drawn from some Banach space.
Overall, we show that the average penalty for not knowing the delayed context
while making a decision scales with $\mathcal{O}(\frac{1}{\sqrt{T}})$, where
this can be improved to $\mathcal{O}(\frac{\log T}{T})$ under special setting.
