Published as a conference paper at ICLR 2018 DEEP LEARNING WITH LOGGED BANDIT FEEDBACK
We propose a new output layer for deep neural networks that permits the use of logged contextual bandit feedback for training. Such contextual bandit feedback can be available in huge quantities (e.g., logs of search engines, recommender systems) at little cost, opening up a path for training deep networks on orders of magnitude more data. To this effect, we propose a counterfactual risk minimization approach for training deep networks using an equivariant empirical risk estimator with variance regularization, BanditNet, and show how the resulting objective can be decomposed in a way that allows stochastic gradient descent training. We empirically demonstrate the effectiveness of the method by showing how deep networks -ResNets in particular -can be trained for object recognition without conventionally labeled images.
This paper proposes a new output layer in neural networks, which allows them to use logged contextual bandit feedback for training. The paper is well written and well structured. 
General feedback:
I would say the problem addressed concerns stochastic learning in general, not just SGD for training neural nets. And it's not a "new output layer", but just a softmax output layer (Eq. 1) with an IPS+baseline training objective (Eq. 16).
Others:
- The baseline in REINFORCE (Williams'92), which is equivalent to introduced Lagrange multiplier, is well known and well defined as control variate in Monte Carlo simulation, certainly not an "ad-hoc heuristic" as claimed in the paper [see Greensmith et al. (2004). Variance Reduction for Gradient Estimates in Reinforcement Learning, JMLR 5.]
- Bandit to supervised conversion: please add a supervised baseline system trained just on instances with top feedbacks -- this should be a much more interesting and relevant strong baseline. There are multiple indications that this bandit-to-supervised baseline is hard to outperform in a number of important applications.
- The final objective IPS^lambda is identical to IPS with a translated loss and thus re-introduces problems of IPS in exactly the same form that the article claims to address, namely:
    * the estimate is not bounded by the range of delta
    * the importance sampling ratios can be large; samples with high such ratios lead to larger gradients thus dominating the updates. The control variate of the SNIPS objective can be seen as defining a probability distribution over the log, thus ensuring that for each sample that sample’s delta is multiplied by a value in [0,1] and not by a large importance sampling ratio.
    * IPS^lambda introduces a grid search which takes more time and the best value for lambda might not even be tested. How do you deal with it?
- As author note, IPS^lambda is very similar to an RL-baseline, so results of using IPS with it should be reported as well:
    In more detail, Note:
    1. IPS for losses<0 and risk minimization: raise the probability of every sample in the log irrespective of the loss itself
    2. IPS for losses>0 and risk minimization: lower the same probability
    3. IPS^lambda: by the translation of the loss, it divides the log into 2 groups: a group whose probabilities will be lowered and a group whose probabilities will be raised (and a third group for delta=lambda but the objective will be agnostic to these)
    4. IPS with a baseline would do something similar but changes over time, which means the above groups are not fixed and might work better. Furthermore, there is no hyperparameter/grid search required for the simple RL-baseline
    -> results of using IPS with the RL-baseline should be reported for the BanditNet rows in Table 1 and in CIFAR-10 experiments.
- What is the feedback in the CIFAR-10 experiments? Assuming it's from [0..1], and given the tested range of lambdas, you should run into the same problems with IPS and its degenerate solutions for lambdas >=1.0. In general, how are your methods behaving for lambda* (corresponding to S*) such that makes all difference (delta_i - lambda*) positive or negative?
- The claim of Theorem 2 in appendix B does not follow from its proof: what is proven is that the value of S(w) lies in an interval [1-e..1+e] with a certain probability for all w. It says nothing about a solution of an optimization problem of the form f(w)/S(w) or its constrained version. Actually, the proof never makes any connection to optimization.
- What the appendix C basically claims is that it's not possible to get an unbiased estimate of a gradient for a certain class of non-convex ratios with a finite-sum structure. This would contradict some previously established convergence results for this type of problems: Reddi et al. (2016) Stochastic Variance Reduction for Nonconvex Optimization, ICML and Wang et al. 2013. Variance Reduction for Stochastic Gradient Optimization, NIPS. On the other hand, there seem to be no need to prove such a claim in the first claim, since the difficulty of performing self-normalized IPS on GPU should be evident, if one remembers that the normalization should run over the whole logged dataset (while only the current mini-batch is accessible to the GPU).