  For infinite action contextual bandits, smoothed regret and reduction to
regression results in state-of-the-art online performance with computational
cost independent of the action set: unfortunately, the resulting data exhaust
does not have well-defined importance-weights. This frustrates the execution of
downstream data science processes such as offline model selection. In this
paper we describe an online algorithm with an equivalent smoothed regret
guarantee, but which generates well-defined importance weights: in exchange,
the online computational cost increases, but only to order smoothness (i.e.,
still independent of the action set). This removes a key obstacle to adoption
of smoothed regret in production scenarios.

Machine Learning