Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning

Summary

The paper considers the offline contextual bandit problem. The authors consider a class of reward estimators for this setting that is a regularization of Inverse Propensity Scoring (IPS - aka importance sampling). A general concentration result is provided for this class of estimators. This is used to provide a tight result for an existing clipping IPS estimator and to construct a new Logarithmic Smoothing (LS) estimator. The resulting estimator is pessimistic by design, making it immediately applicable to the offline contextual bandit problem. The authors use it to derive bounds for policy evaluation and selection and also for policy learning in the Bayesian setting. Experimental results also support the usefulness of the estimator.

Strengths

I am only broadly familiar with this line of research making it hard for me to properly contextualize its contributions. 1. The proposed estimator is novel and has nice properties. 2. As the name suggests, the estimator is smooth making it potentially easy to optimize. 3. The application to contextual bandits is interesting. 4. The experimental results are positive. 5. The overall writing is good and clear.

Weaknesses

1. A more explicit comparison with existing concentration\contextual bandit bounds is missing. The authors explain that their bound is better but this is somewhat vague, especially if the reader is not already an expert in this field. 2. In line 155 the authors explain that their result can be derived from [1, Lemma 1.3]. Does this mean that the LS estimator has previously been suggested or only that an alternative proof technique exists for its concentration bound? 3. Performance seems very close to that of IX 4. The main body of the paper does not include any explanation of the techniques used. This can be a proof sketch for the concentration bound or a discussion comparing your approach to existing techniques. Can you provide such an explanation in your response? 5. The notation U(pi) appears without definition in line 281. I assume it's defined in one of the references but should also be defined in this paper for completeness. (Please include an explanation in your response) Typo: line 98: one of the brackets is reversed in the definition of h

Questions

See above.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

N/a

Summary

The authors propose empirical concentration inequalities for off-policy evaluation that apply to several forms of (smoothed) IPS, which are claimed to be tighter than the results in existing works. These bounds are then used to derive policy learning guarantees that inherit the properties of the concentration inequalities.

Strengths

I appreciate that the authors have applied their method to OPE, OPS, OPL, and also provided some experiments. I did not read the appendix nor check the correctness of the analysis in detail, but from a quick glance it appears that the authors were careful to provide rigorous and well-organized proofs.

Weaknesses

My biggest criticism is that the authors have not justified *in the main body* their claim that "LS is provably tighter than its competitors" (L12) for any of the results, including the concentration inequalities (Prop 1, Cor 3, Cor 4) and the policy learning guarantee (e.g., Prop 6). Since these claims are the whole premise for the paper, their justification should be a central pursuit and only stating "x is in Appendix y" (L147, 178, 195) is hugely insufficient. For example, I would have liked to see a discussion on (possibly even in graphs): - For the choices of $h$ described in (4), when do the bounds in Prop 1, Cor 3, and Cor 4 improve over the bounds from their respective papers? - Is $h*$ (the tightest choice) better than all of the above? - Does this hold for all hyperparameter choices, e.g. $\lambda$ and $L$? - How does the computational complexity of calculating the bounds in Prop 1, Cor 3, Cor 4 hold up relative to their competitors? - Exactly how does this lead to downstream policy learning improvements? Lastly, I found the overall technical presentation to be relatively poor, and I'll give a few examples: - The condition (C1) from Section 2 ("Regularized IPS") that all results depend on is never explicitly defined, and it should be an assumption that is called in every proceeding proposition/theorem statement. - Shouldn't (11) be framed in, e.g., a lemma environment? - The term "pessimism" is overloaded, e.g., for "high-probability upper bounds" in L111 but also for an in-expectation variant in Eq. (5), which is slightly unusual (and I'm pretty sure not the way it's used in [26]) but not recalled again in the main body so I'm not sure what it's for (perhaps the proof of Prop 1).

Questions

In addition to the ones in "Weaknesses," I have a specific question about Proposition 6. The gold standard in offline policy selection is a bound in the form of $R(\pi) - R(\widehat\pi) \le \lambda S(\pi) + \varepsilon$ for any comparator policy $\pi$ rather than the optimal one $\pi^*$ (see [26] and [Wang 2024] and [Xie 2021]). The former is strictly more general -- can you write your bound in such a form? **References** Wang, L., Krishnamurthy, A., & Slivkins, A. (2024, April). Oracle-efficient pessimism: Offline policy optimization in contextual bandits. In International Conference on Artificial Intelligence and Statistics (pp. 766-774). PMLR. Xie, T., Cheng, C. A., Jiang, N., Mineiro, P., & Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34, 6683-6694.

Rating

3

Confidence

5

Soundness

2

Presentation

1

Contribution

2

Limitations

I do not believe the authors have fully discussed the limitations of their method (see "Weaknesses").

Summary

This paper studies log-algorithmic smoothing of importance weight for off-policy learning. The proposed smoothing technique can be seen as a differentiable variant of clipping, which is useful for variance reduction for OPL. The paper also analyzes the PAC-Bayes learning bound of the proposed OPL method, characterized by the KL divergence with the logging policy, showing that the proposed method achieves a tighter bound than baselines, including simple clipping. The experiment also shows that the proposed method has tighter bounds than baselines and enables more accurate off-policy selection.

Strengths

- **Reasonable formulation based on theoretical analysis**: The proposed method is derived from a tight upper bound of the policy's risk. Also, the proposed method has an interpretation as soft, differentiable clipping. The technique is well-motivated and is reasonable to interpret. - **PAC-Bayes learning bound**: A sub-optimality form is derived, and it is also easy to interpret as a pessimistic approach, which should be acknowledged. - **Experiments on various tasks**: The paper evaluates the proposed approach in upper bound derivation, off-policy selection, and off-policy learning. The experiment results show the wide applicability of the proposed method in many OPE/OPL-related tasks.

Weaknesses

- **Connection to Metelli et al. 2021 is not clear**: Metelli et al. 2021 also considers the importance of weight differential and shows that the proposed method achieves a Subgaussian rate. Similar to the reviewed paper, Metelli et al. 2021 also have a KL divergence term in the theoretical analysis. While the proposed method adequately differs from Metelli et al. 2021, and the paper does cite it, the paper does not mention Metelli et al. 2021 in the related work in detail. Since the motivation and contributions are similar, a detailed discussion on the advantages and the differences would be appreciated. - **Baselines in the experiments**: As mentioned above, Metelli et al. 2021 propose a similar idea that can be used as a baseline in experiments. Comparing with advanced regularization techniques such as shrinkage (Su et al. 2020) would also be informative. (Metelli et al. 2021) Subgaussian and Differentiable Importance Sampling for Off-Policy Evaluation and Learning. Alberto Maria Metelli, Alessio Russo, Marcello Restelli. NeurIPS, 2021. (Su et al. 2020) Doubly robust off-policy evaluation with shrinkage. Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, Miroslav Dudík. ICML, 2020.

Questions

- What are the connections with Metelli et al. 2021? (See weaknesses for the detailed comments.) - How does OPL work with the varying performance of the behavior policy? In my understanding, the policy will be pessimistic in out-of-distribution, but seeing how it works in experiments would be informative for readers.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Missing connection with a similar idea. See the weaknesses for the details.

Summary

Policy evaluation, selection and optimization are considered in the context of offline contextual bandits, where i.i.d. data with a known behavior policy is given. The authors set out to study a generalization of importance weighted policy evaluation; for this they start from a general formulation that computes a value for all data observations, which are then averaged. The free "parameter" here is $h$, the function that assigns a value given an observation (of a context, associated action, and cost). A tight, general, high probability upper bound on the expected cost of a fixed target policy is derived first. Specific choices for the map $h$ are then derived based on minimizing this upper bound. Two practical solutions to this optimization problem are studied in more details: Global clipping and "logarithmic smoothing". Results are then derived for both policy selection and optimization.

Strengths

Novel ideas, novel results, good empirical results.

Weaknesses

Despite saying that the methodology of paper [31] is adopted, this is only partially done. Why deviate from the evaluation in [31]? I expected an explanation of this.

Questions

Can you explain why you did not follow the protocol and reported values of [31]?

Rating

10

Confidence

5

Soundness

4

Presentation

4

Contribution

4

Limitations

na

Response

Thank you for responding to my concerns, I will keep my score. A small side note: the abbreviation LS is usually associated with Least Squares. If there is another sensible naming option it will probably help avoid confusing the two :)