There has been a surge of interest in off-policy learning in the last decade. Most of these contributions have focused upon improving the estimate of the reward function including the development of estimators for the reward representing sophisticated modifications of the estimators \(\hat{r}_{IPS}\)  and \(\hat{r}_{DR}\)  introduced in the first section. Correctly estimating the reward is an extremely difficult problem and naive estimators suffer from very high variance
especially when the new policies we want to evaluate are far from the policy that collected the data [1]}, [2]}. Many new methods improved the bias-variance trade-off of the reward estimators [3]}, [4]}, [5]}, [6]}, [7]} and tackled the learning problem by using these newly designed estimators within the framework of Empirical Risk Minimization [3]}, [4]}, [5]}, or within a more appropriate statistical learning theory, giving birth to Sample Variance Penalization [11]}, Distributionally Robust Counterfactual Risk Minimization [12]}, [13]}, PAC-Bayesian Counterfactual Risk Minimization [14]} and Imitation Offline Learning [15]}. Alternatively, instead of using an estimator, an explicit reward model can be used [16]}, [17]}. Our contribution here is orthogonal to these developments as we consider the problem of how to efficiently find a good policy given a reward function. Most past work assumes the action space is small and hence the optimization problem is tractable. Our algorithm reduces the optimization cost associated with large action spaces but the estimation challenges of the reward function remain.
