Off-policy learning, the task of evaluating and improving policies using historic data collected from a logging policy, is important because on-policy evaluation is usually expensive and has adverse impacts. One of the major challenge of off-policy learning is to derive counterfactual estimators that also has low variance and thus low generalization error. 
 In this work, inspired by learning bounds for importance sampling problems, we present a new counterfactual learning principle for off-policy learning with bandit feedbacks.Our method regularizes the generalization error by minimizing the distribution divergence between the logging policy and the new policy, and removes the need for iterating through all training samples to compute sample variance regularization in prior work. With neural network policies, our end-to-end training algorithms using variational divergence minimization showed significant improvement over conventional baseline algorithms and is also consistent with our theoretical results. Off-policy learning refers to evaluating and improving a deterministic policy using historic data collected from a stationary policy, which is important because in real-world scenarios on-policy evaluation is oftentimes expensive and has adverse impacts. For instance, evaluating a new treatment option, a clinical policy, by administering it to patients requires rigorous human clinical trials, in which patients are exposed to risks of serious side effects. As another example, an online advertising A/B testing can incur high cost for advertisers and bring them few gains. Therefore, we need to utilize historic data to perform off-policy evaluation and learning that can enable safe exploration of the hypothesis space of policies before deploying them.There has been extensive studies on off-policy learning in the context of reinforcement learning and contextual bandits, including various methods such as Q learning BID33 ), doubly robust estimator BID8 ), self-normalized (Swaminathan & Joachims (2015b) ), etc. A recently emerging direction of off-policy learning involves the use of logged interaction data with bandit feedback. However, in this setting, we can only observe limited feedback, often in the form of a scalar reward or loss, for every action; a larger amount of information about other possibilities is never revealed, such as what reward we could have obtained had we taken another action, the best action we should have take, and the relationship between the change in policy and the change in reward. For example, after an item is suggested to a user by an online recommendation system, although we can observe the user's subsequent interactions with this particular item, we cannot anticipate the user's reaction to other items that could have been the better options.Using historic data to perform off-policy learning in bandit feedback case faces a common challenge in counterfactual inference: How do we handle the distribution mismatch between the logging policy and a new policy and the induced generalization error? To answer this question, BID34 derived the new counterfactual risk minimization framework, that added the sample variance as a regularization term into conventional empirical risk minimization objective. However, the parametrization of policies in their work as linear stochastic models has limited representation power, and the computation of sample variance regularization requires iterating through all training samples. Although a first-order approximation technique was proposed in the paper, deriving accurate and efficient end-to-end training algorithms under this framework still remains a challenging task.Our contribution in this paper is three-fold:1. By drawing a connection to the generalization error bound of importance sampling BID6 ), we propose a new learning principle for off-policy learning with bandit feedback. We explicitly regularize the generalization error of the new policy by minimizing the distribution divergence between it and the logging policy. The proposed learning objective automatically trade off between emipircal risk and sample variance. 2. To enable end-to-end training, we propose to parametrize the policy as a neural network, and solves the divergence minimization problem using recent work on variational divergence minimization BID26 ) and Gumbel soft-max BID18 ) sampling. 3. Our experiment evaluation on benchmark datasets shows significant improvement in performance over conventional baselines, and case studies also corroborates the soundness of our theoretical proofs. In this paper, we started from an intuition that explicitly regularizing variance can help improve the generalization performance of off-policy learning for logged bandit datasets, and proposed a new training principle inspired by learning bounds for importance sampling problems. The theoretical discussion guided us to a training objective as the combination of importance reweighted loss and a regularization term of distribution divergence measuring the distribution match between the logging policy and the policy we are learning. By applying variational divergence minimization and Gumbel soft-max sampling techniques, we are able to train neural network policies end-to-end to minimize the variance regularized objective. Evaluations on benchmark datasets proved the effectiveness of our learning principle and training algorithm, and further case studies also verified our theoretical discussion.Limitations of the work mainly lies in the need for the propensity scores (the probability an action is taken by the logging policy), which may not always be available. Learning to estimate propensity scores and plug the estimation into our training framework will increase the applicability of our algorithms. For example, as suggested by BID6 , directly learning importance weights (the ratio between new policy probability to the logging policy probability) has comparable theoretical guarantees, which might be a good extension for the proposed algorithm.Although the work focuses on off-policy from logged data, the techniques and theorems may be extended to general supervised learning and reinforcement learning. It will be interesting to study how A. PROOFS DISPLAYFORM0 We apply Lemma 1 to z, importance sampling weight function w(z) = p(z)/p 0 (z) = h(y|x)/h 0 (y|x), and loss l(z)/L, we have DISPLAYFORM1 Thus, we have DISPLAYFORM2 Proof. For a single hypothesis denoted as δ with values DISPLAYFORM3 By Lemma 1, the variance can be bounded using Reni divergence as DISPLAYFORM4 Applying Bernstein's concentration bounds we have DISPLAYFORM5 σ 2 (Z)+ LM/3 ), we can obtain that with probability at least 1 − η, the following bounds for importance sampling of bandit learning holds DISPLAYFORM6 , where the second inequality comes from the fact that DISPLAYFORM7 sampled from logging policy h 0 ; regularization hyper-parameter λ Result: An optimized generator h * θ (y|x) that is an approximate minimizer of R(w) initialization; while Not Converged do / * Update discriminator * / Sample a mini-batch of 'fake' samples (x i ,ŷ i ) with x i from D andŷ i ∼ h θ t (y|x i ); Sample a mini-batch of 'real' samples (x i , y i ) from D ; Update w t+1 = w t + η w ∂F (T w , h θ )(10) ; / * Update generator * / Sample a mini-batch of m samples from D ; Sample a mini-batch of m 1 'fake' samples ; Estimate the generator gradient as g 2 = F (T w , h θ )(10) ; Update θ t+1 = θ t − η θ (g 1 + λg 2 ) ; end Algorithm 3: Minimizing Variance Regularized Risk -Co-Training Version
For off-policy learning with bandit feedbacks, we propose a new variance regularized counterfactual learning algorithm, which has both theoretical foundations and superior empirical performance.
{"src": "scitldr-AIC_train", "paper_id": "SyPMT6gAb"}