This paper introduces the Log-Sum-Exponential (LSE) estimator, a novel approach for off-policy evaluation (OPE) and off-policy learning (OPL) with only logged bandit feedback. The estimator is designed to address high variance, noisy propensity scores, and heavy-tailed reward distributions, common challenges in OPE/OPL. The paper provides theoretical bounds on regret, bias, and variance, and supports the claims with empirical evaluations comparing the LSE estimator against several baseline methods, including truncated importance sampling (IPS) and other state-of-the-art estimators.

The paper proposes a new off-policy estimator based on the log-sum-exp operator, that is motivated by its robustness to heavy tailed rewards. The bias-variance tradeoff of the estimator was studied, its learning guarantees (in terms of regret) as well as its behaviour in reward drift/contaminated reward scenarios. The regret bound in particular has a rate of $O(n^{-\epsilon/(1 + \epsilon)})$ where $n$ the sample size, assuming bounded $(1 + \epsilon)$-th moment ($\epsilon \le 1$). Experiments were conducted to validate the performance of the estimator in specific settings.

The paper proposes to use a "log sum exp" estimator for off policy evaluation and learning in contextual bandits. The main theoretical claim is that this estimator allows for handling heavy tailed reward distributions and provides some robustness under distribution shift (called noisy reward). The main practical claim is simply that the estimator works better than several baselines in both OPE and OPL settings.

Questions and Comments:

0. In general, I am unconvinced that heavy-tailed reward is a real problem. The main reason is that the reward is something that we (the system builder) gets to design (i.e., if we are building a recommender system, we decide how to aggregate collected telemetry data into a scalar reward). It is always possible to design the reward so that it is bounded at a minimum, which implies that all moments are bounded.

0a. Given this, one possibility is to interpret the heavy-tailed assumption as a sort of "instance dependence." Suppose that rewards are bounded in [0,R_max] but that the 1+\eps moment is much much smaller. Then we'd like statistical guarantees that have a benign dependence on R_{max}, replacing it with 1+\eps moment. This seems worthwhile, but if I understand correctly, I think this is already done in [3] (for the unweighted second moment).

0b. I certainly agree that heavy-tailed importance weight is a real problem, but this is addressed by a number of other previously proposed estimators, including IX, clipped importance weights, smoothing/shrinkage, SWITCH (from [3]), etc.

1. In terms of exposition, it would be helpful to clearly explain how LSE compares to existing estimators. Table 2 is not very helpful because the quantities that appear in the bias/variance for LSE do not appear in the bounds for the others.

1a. As a concrete question: Suppose that rewards were bounded in [0,Rmax], then we should take \nu_2 = R_{max}^2 P_2(\pi_\theta||\pi_0). Is LSE better than IPS under this setup? It seems that the positive term of the LSE variance is worse, due to R_{max}^2 vs R_{max}.

2. Why does the variance bound in Prop 5.7 require bounded second moment (rather than 1+eps for any eps)? It seems like I can always use Lemma 5.1 to bound the variance of LSE under bounded (1+eps) moment. Is the point that Prop 5.7 is tighter due to the -\lambd\nu_2^{3/2} term? If so, it would be great to make this clear in the exposition and somehow highlight where/why this refinement matters. (e.g., maybe it is necessary to address the question in 1a.)

3. The OPE experiment is somewhat unconvincing because the setting is highly synthetic. It seems that the setup is designed to expose a weakness of prior methods that is addressed in the present work (i.e., heavy tails). But it is not clear that this problem is prevalent in practice or whether LSE results in some tradeoffs in "more benign" settings.

3a. In particular, it is by now standard to do these experiments on a wide range of datasets with a broad set of experimental conditions. See e.g., [1,2]. I strongly recommend that the authors add such experiments to the paper.

4. Regarding OPE experiments, there are also a number of important missing baselines, including clipped importance weighting, the SWITCH estimator of [3], etc.

5. For the OPL experiments, why do we only compare against unregularized baselines? I think we should view the LSE estimator as a form of regularization, so it seems natural to also compare with regularized baselines. In particular, why not compare against MRDR [1] and DR-Shrinkage [2]? Both can be implemented with a "reward estimator" that always predicts 0.

6. As alluded to above, the exposition/presentation could be greatly improved.

Overall, I feel the paper has a decent amount of potential, but isn't quite there yet. As it stands, it feels a rather shallow. There could have been a much deeper theoretical and empirical investigation into the estimator and its properties and this could have made the paper much better. As mentioned above, I don't think the heavy tailed reward setting is particularly interesting, but heavy-tailed importance is definitely a real problem. Focusing the paper on this setting would have helped, but then this requires a much deeper discussion of prior work and connections. As a concrete point about this, I believe the estimator can be formally viewed as a form of regularization, via the duality between log-sum-exp and entropy regularization. It would have been nice to consider this view point as a means to connect to other forms of regularization in the off policy evaluation literature, for example those developed in [2]. In particular, I think there is potentially something interesting about the LSE estimator relative to prior works like [2], namely it is a new form of shrinkage that explicitly accounts for the n-dimensional nature of the regularization problem (akin to Stein shrinkage). It would be nice to investigate this in more detail.

Missing references:

[1] Mehrdad Farajtabar, Yinlam Chow, Mohammad Ghavamzadeh. More Robust Doubly Robust Off-policy Evaluation. https://arxiv.org/abs/1802.03493

[2] Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, Miroslav Dudík. Doubly robust off-policy evaluation with shrinkage. https://arxiv.org/abs/1907.09623

[3] Yu-Xiang Wang, Alekh Agarwal, Miroslav Dudik. Optimal and Adaptive Off-policy Evaluation in Contextual Bandits. https://arxiv.org/abs/1612.01205

Post-rebuttal: I thank the authors for their detailed responses. I have a few comments (below) and I will raise my score to 5. As I mentioned above, I think this paper does have potential but is not quite there yet so I am not quite ready to recommend acceptance.

• I understand the examples provided but I am still unconvinced that heavy-tailed reward is a real problem. We can always make the reward bounded, this is without loss of generality and so the question is which moments are controlled. I appreciate the discussion about 1+eps vs 2+eps moment, and I think the paper would greatly benefit by having this included. More generally, the paper would benefit from a much clearer explanation of (a) the settings that are not handled by prior work and (b) the instance dependent improvements that LSE achieves in settings that are handled by prior work.
• I think LSE can be viewed as regularization, we just need to minimize rather than maximize. Take \lambda < 0, let z be given and define the optimization problem \min_{y} y^\top z + \lambda H(y). Since entropy is concave and \lambda < 0, this is a convex optimization problem. The value at the minimum is exactly LSE_\lambda(z) as defined in Eq (1) of the paper. Note that minimizing makes more sense because we want to be pessimistic (which is standard in offline RL/CB).
• I certainly appreciate the additional experiments and the references to missing related work. Thank you!

Summary: The authors consider stochastic, contextual bandits where data is collected using a logging policy $\pi_{\log}$. This policy is available for point evaluation. The main idea is to use the LSEA, "log-sum-exponential average" ($f_s(z_1,\dots,z_n) =-1/s \log \sum_{i=1}^n \exp(- s z_i)$, $s>0$) on the top of importance weighted reward data (i.e., estimate the value of policy $\pi$ using $f_s(Z_1,\dots,Z_n)$ where $Z_i = R_i \pi(A_i|X_i)/\pi_{\log}(A_i|X_i)$, $X_i$ is context for the $i$th data point, $A_i$ is the corresponding action logged, and $R_i$ is the associated reward). The authors show generalization bounds on how well this estimator approximates the true value of policies, as well as bounds on the (simple) regret of the policy which, in a given class, gives the best LSEA. The bounds depend on the smoothing parameter $s$ (the authors use $\lambda = -s$) and $\epsilon>0$, which is a constant such that $\mathbb{E}[ |Z_i]^{1+\epsilon} ]\le \nu$ (since $Z_i$ depends on the policy, this is demanded to hold uniformly for all policies). We shall call this a moment constraint on the importance weighted reward. In particular, it is claimed that the "rate" of the suboptimality of the chosen policy is $O(n^{-\epsilon/(1+\epsilon)})$. In addition to the theoretical result, the authors also show empirical evidence that their approach is a good one. For this, two setting are considered: a synthetic problem (gaussian policies, etc.), and another problem based on transforming EMNIST (and also FMNIST) to a bandit problem.

Significance/novelty: The problem is of high significance, "fixing importance weighting estimators" is also of high importance. Bringing LSEA to this problem is a new and nice idea. The theoretical results are of interest, as well, and the empirical evidence presented is promising. The robustness result is OK, but I could not see its significance (yes, we can do this.. until I see a lower bound, it is unclear how lose this or similar results are).

Soundness: I believe the results are correct, although I did not verify the details of the proofs. However, both the results and the techniques look reasonable (see a few questions below). I wished that Table 3 comes with error bars, and/or some presentation of the distributional properties of the various estimators, especially, given the emphasis on "heavy tailedness".

Novelty/related work: The authors motivate using LSEA by arguing that the data will be "heavy tailed". This is fine, but then I don't see the relevant literature on estimating means with heavy tail data discussed in the paper. The discussion of the rest of the literature is fine. This literature is big, so we should not expect a comprehensive discussion. I found it awkward that while the 2024 paper of Sakhi et al., which introduced the logarithmic smoothing estimator, is cited, it is not compared to and the idea of logarithmic smoothing is not discussed, even though it feels also related to the present paper in that I expect it also perform well in the heavy-tailed setting of the paper (the logarithmic transformation of the data, intuitively, turns large tails into smaller ones).

Presentation: I found the presentation to be fine.

Some minor issues: Is the number of actions finite? If not, what is $\pi(a|x)$? Density of distribution over arms with respect to some base measure?

Rebuttal Summary

We are grateful to all reviewers for their insightful comments and feedback. In this post, we summarize our both the original experiments from our work and those additional experiments we conducted during the rebuttal period to address reviewer questions and suggestions.

Experiments

OPL Experiments:

• SupervisedToBandit (Section 6.2 and Section G.2): These experiments are based on the supervised-to-bandit experimental setup explained. Detailed experiments including normal, noisy propensity scores, and noisy rewards settings on FMNIST and EMNIST datasets for evaluating different estimators are reported. LS-LIN and OS estimators were added during the rebuttal period (reviewers PX8q, FxqM and 3zEX).
• Model-based estimator (Section G.3): The estimator based on Double-Robust estimation are evaluated and compared. DR-SWITCH, DR-SWITCH-LSE, DR-OS and MRDR estimators were added during the rebuttal period (reviewer FxqM) .
• Real-world Experiments (Section G.4) : The real-world experiments evaluate model performance on an original bandit dataset collected in a real-world circumstance. KuaiRec dataset results are reported. LS-LIN and OS estimators were added during the rebuttal period (reviewers PX8q, FxqM and 3zEX).
• Sample size $n$ effect (Section G.5): Analyzes how the sample size impacts the performance of different estimators.
• Effect of hyperparameter $\\lambda$ (Section G.6): explores the effect of the hyperparameter $\\lambda$ on the LSE estimator.
• $\\lambda$ selection for OPL (Section G.7): $\\lambda$ selection based on number of samples is compared to grid-search selection.

OPE Experiments:

• Synthetic Experiments (Section 6.1 and G.1): Synthetic datasets, Gaussian and Lomax, are generated to compare different estimators based on their ability to estimate target policy's average reward. LS, LS-LIN, and OS estimators were added during the rebuttal period (reviewers PX8q, FxqM and 3zEX).
• $\\lambda$ selection for OPE (Section G.7.2-G.7.3, rebuttal, reviewer W6M8): Proposes $\\lambda$ value for OPE and compares LSE with this selection against other estimators.
• Sensitivity to $\\lambda$ (Section G.7.4, rebuttal, reviewer W6M8): Shows estimator sensitivity to hyperparameter selection.
• OPE with noise (Section G.8, rebuttal, reviewer W6M8): Discusses robustness of different estimators to noise.
• Distributional behavior in OPE (Section G.9, rebuttal, reviewer 3zEX): Investigates error distribution of different estimators.
• Comprehensive comparison with LS (Section G.10, rebuttal, reviewers PX8q and 3zEX): Detailed experiments comparing LS and LSE estimator sensitivity to hyperparameter selection.
• OPE on real-world datasets (Section G.11, rebuttal, reviewer FxqM): Experiments on real classification datasets from UCI repository.

We would be happy to conduct additional experiments to address any remaining questions or concerns before the end of discussion period.

I have read and agree with the venue's withdrawal policy on behalf of myself and my co-authors.