Hyperparameter Optimization Can Even be Harmful in Off-Policy Learning and How to Deal with It
Yuta Saito Masahiro Nomura


Resolving Red Giant Winds with the
  Hubble Space Telescope1
    Brian E. Wood2, Graham M. Harper3,
  Hans-Reinhard Müller4
    April 29, 2024
==============================================================




There has been a growing interest in off-policy evaluation in the literature such as recommender systems and personalized medicine. We have so far seen significant progress in developing estimators aimed at accurately estimating the effectiveness of counterfactual policies based on biased logged data. However, there are many cases where those estimators are used not only to evaluate the value of decision making policies but also to search for the best hyperparameters from a large candidate space. This work explores the latter hyperparameter optimization (HPO) task for off-policy learning. We empirically show that naively applying an unbiased estimator of the generalization performance as a surrogate objective in HPO can cause an unexpected failure, merely pursuing hyperparameters whose generalization performance is greatly overestimated. We then propose simple and computationally efficient corrections to the typical HPO procedure to deal with the aforementioned issues simultaneously. Empirical investigations demonstrate the effectiveness of our proposed HPO algorithm in situations where the typical procedure fails severely.




§ INTRODUCTION

Interactive decision making systems, such as recommender systems, produce logged data valuable for optimizing future decision making.
For example, the logs of an e-commerce recommender system record which product was recommended and whether the users purchased it, giving the system designer a rich logged dataset useful for evaluating and improving the decision making quality. 
This type of historical data is often called logged bandit data and is one of the most ubiquitous forms of data available in many real-life applications <cit.>.
 
Off-Policy Learning (OPL) aims to train a new decision making policy using only the logged bandit data. 
OPL is useful in that it can improve the decision making system continuously in a batch manner without requiring a risky exploration.
Owing to the ubiquity of logged bandit data in the real-world, significant attention has been paid to OPL of contextual bandits <cit.>.

The fundamental problem in OPL is that the outcome is only observed for the action chosen by the system in the past. 
Thus, estimating the generalization performance of a policy is non-trivial because we cannot naively apply the empirical risk as done in typical supervised machine learning (ML).
Therefore, a variety of estimators have been developed in the field of off-policy evaluation (OPE), such as Inverse Propensity Score (IPS) <cit.> and Doubly Robust (DR) <cit.>.
Then, a feasible approach to OPL is to maximize one such estimator as a surrogate objective using only the logged data. Hyperparameter optimization (HPO) can also be performed based on one of the estimators on a validation set of the logged data <cit.>.

In this study, we investigate how well automatic HPO algorithms work for OPL using only the available logged data. In particular, we empirically find two critical issues in HPO that have yet to be investigated in the literature, but can have a significant adverse impact on the effectiveness of the OPL pipeline. The first issue is optimistic bias, which implies that the hyperparameter values selected by an HPO procedure are often the ones whose performance is greatly overestimated. In HPO, we often use an unbiased estimator as a strategy to optimize the generalization performance (primary objective) using only validation data. The problem is that, when optimizing the validation performance as a surrogate objective, HPO can identify a set of hyperparameters whose validation performance looks good but its generalization performance is detrimental. As a result, the typical HPO procedure often produces a highly sub-optimal solution, even with an unbiased estimator of the generalization performance. The second issue is unsafe behavior, which suggests that the typical HPO procedure can output a solution, which underperforms the logging (data collection) policy, even when we set the logging policy as an initial solution. This is problematic because a logging policy is often a baseline policy to improve upon in OPL. If an HPO procedure aggravates the performance of the logging policy, there is no need to implement it in practice.

After formulating the problem in Section <ref>, Section <ref> provides clear empirical evidence of optimistic bias and unsafe behavior. We observe these phenomena even when we use an unbiased surrogate objective and a popular adaptive HPO algorithm. We also explain these observations theoretically, demonstrating that ignoring the fact that HPO optimizes the validation performance as a surrogate of the generalization performance can lead to a worse regret of HPO algorithms. More specifically, we identify that a heavy-tailed distribution of overestimation bias during HPO can cause an unexpected gap between the generalization and validation regret. These empirical and theoretical observations result in our proposed corrections to the typical HPO procedure, which we describe in Section <ref>. Finally, Section <ref> conducts comprehensive experiments and demonstrates that our simple corrections can deal with the aforementioned issues and improve the typical procedure, particularly for cases where the typical procedure becomes unsafe and underperforms the logging policy.[Appendix B provides a comprehensive survey of related work.]




§ PRELIMINARIES


We use x ∈ to denote a context vector and a ∈ to denote a (discrete) action such as a playlist recommendation in a music streaming service. Let r ∈ [0, r_max] denote a reward variable, which is sampled identically and independently from an unknown conditional distribution p (r | x, a). A decision making policy is modeled as a distribution over the action space, i.e., π: →Δ() where Δ(·) is a probability simplex. We can then represent the probability of action a being taken by policy π given context x as π (a | x).



 §.§ Off-Policy Evaluation and Learning

In OPE, we are given logged bandit data := {(x_i,a_i,r_i)}_i=1^n consisting of n independent draws from the logging policy π_0. Using this logged dataset, OPE aims to estimate the generalization performance of a given evaluation policy π_e, which is often different from π_0: 

    := _(x,a,r) ∼ p(x) π_e (a | x) p(r | x, a) [r].


This is the ground-truth performance of the evaluation policy when deployed in an environment of interest. OPE uses an estimator V̂ to estimate  based only on  as ≈V̂ (π_e; ). A typical choice of V̂ is IPS:

    := 1/n∑_i=1^n π_e(a_i  |  x_i)/π_0 (a_i  |  x_i) r_i,

where π_e(a_i | x_i)/π_0(a_i | x_i) is called the importance weight. Under some assumptions for identification such as full support (π_e(a|x) > 0 →π_0(a|x) > 0,  ∀ (x,a)), IPS provides an unbiased estimate of the generalization policy performance, i.e., _ [] =. Beyond IPS, significant efforts have been made to enable a more accurate OPE from the logged data <cit.>.

In OPL, we aim to learn an optimal decision making policy π^* := _π V(π) from the logged data. As in supervised ML, we cannot directly use the generalization policy performance. Instead, we use its estimator as a surrogate:

    π̂ = _π∈Π V̂(π; ) - λ·ℛ (π),

where Π is a policy class, which might be a linear class <cit.> or deep neural nets <cit.>. ℛ(·) regularizes the complexity of the policy π, and λ (≥ 0) is a hyperparamter that controls the effect of regularization.






 §.§ Hyperparameter Optimization

OPE involves many hyperparameters to be properly tuned from those defining the policy class Π to the regularization parameter λ. In a typical HPO procedure for OPL, we first split the original logged bandit data  into training () and validation () sets. Then, we wish to solve the following bi-level optimization:

    θ^* := _θ∈Θ  V (π̂(·; θ, ) ),

where Θ is a pre-defined hyperparamter search space. π̂(·; θ, ) is a policy parameterized by a set of hyperparameters θ. The model parameter of π̂(·; θ, ) is trained on the training set  (lower-level optimization). The problem here is that the generalization performance of π̂(·; θ, ) is unknown and needs to be estimated. A feasible HPO procedure based on an estimated policy performance is:

    θ̂() := _θ∈Θ V̂(π̂(·; θ, ); ),

where the generalization performance of π̂(·; θ, ) is estimated by an estimator V̂ on the validation set .[For brevity of notation, we sometimes use V(θ) and V̂(θ;) to denote the generalization and validation performances of the policy induced by θ.] A common choice of V̂ is an unbiased estimator that satisfies [ V̂(π; ) ] = V(π), ∀π∈Π such as IPS. Then, one can apply grid search, random search <cit.>, or adaptive methods such as tree-structured Parzen estimator (TPE) <cit.> to solve the higher-level optimization in Eq. (<ref>) efficiently. Algorithm <ref> describes this typical HPO procedure for OPL, which starts from the logging policy π_0 as its initial solution and adaptively samples promising hyperparameters via an arbitrary HPO algorithm (denoted here as A) <cit.>.







§ UNEXPECTED FAILURE IN HPO FOR OPL

This section studies the effectiveness of HPO when applied to OPL from both empirical and theoretical perspectives. 




 §.§ Empirical Analysis

First, we conduct a synthetic experiment and provide empirical evidence of surprising failure of HPO in OPL.



  §.§.§ Synthetic Data.

Our empirical analysis is based on OpenBanditPipeline (OBP)[https://github.com/st-tech/zr-obp], an open-source toolkit for OPE and OPL, which includes synthetic data generation modules and a range of estimators <cit.>. We synthesize context vectors x by sampling them from a 10-dimensional standard normal distribution. We then set ||=10, where each action a ∈ is characterized by a 10-dimensional representation vector e_a. The reward function μ(x,a):=[r  |  x,a] is defined as:

    μ(x,a) = σ( x^⊤ M e_a + η_x^⊤ x +  η_a^⊤ e_a ),

where σ(z):= 1/(1+exp(-z)) is the sigmoid function. M, η_x, and η_a are parameter matrices or vectors for defining the synthetic reward function. These parameters are sampled from a uniform distribution with range [-1,1]. After generating the synthetic reward function, we sample binary rewards from a Bernoulli distribution with parameter μ(x,a).

We then define the logging policy π_0 by applying the softmax function to the reward function μ(x,a) as follows.

    π_0(a  |  x) =  exp( β_0 ·μ(x,a))/∑_a' ∈exp( β_0 ·μ(x,a'))  ,

where β_0 is an inverse temperature parameter to control the optimality and entropy of the logging policy.
A large positive value of β_0 leads to a near-deterministic and near-optimal logging policy. When β_0=0, π_0 is uniform.



  §.§.§ Policy Class and HPO Algorithms.

To train a new policy π from only the logged data, we first estimate μ(x,a) by a supervised ML method, where the resulting estimator is denoted as μ̂(x,a;). We then form a stochastic policy by applying the softmax rule as:

    π(a  |  x; θ, ) =  exp( β·μ̂(x,a;))/∑_a' ∈exp( β·μ̂(x,a';))  ,

where β is an inverse temperature parameter to define a new policy. θ is a set of hyperparameters, which consists of β, supervised ML model to construct μ̂, and the hyperparameters of μ̂. The hyperparameter search space Θ is summarized in Table 1 in Appendix E.

As an HPO algorithm, we use TPE <cit.>, which is a popular adaptive method in the HPO community <cit.>. TPE has been shown to work well for HPO of supervised ML, however, whether it also works for OPL has never been thoroughly investigated.




  §.§.§ Observations.

In this synthetic experiment, we set β_0 ∈{0,3,20} and ||=||=1,000. The number of trials (T in Algorithm <ref>) for HPO is set to 1,000.

Figure <ref> shows the validation performance ((π; ); what HPO algorithm maximizes from the logged data) and the generalization performance (V(π); the primary objective of OPL) during the HPO procedure. We obtain the following key observations in this experiment.


    
  * Optimistic Bias: For all β_0, TPE succeeds in maximizing the validation performance, monotonically improving the blue lines. However, there is a substantial gap between validation and generalization, and the validation performance becomes an extremely optimistic proxy of the generalization performance. For example, when β_0=3, TPE does not bring any impact on the generalization performance, although the validation performance is greatly improved. This result suggests that implementing HPO is indeed a waste of time and resources for this setting. 

    
  * Unsafe Behavior: When β_0 = 20 (where π_0 is already much better than uniform random), TPE outputs a solution that is significantly worse than the logging policy with respect to the generalization performance. This is problematic, as the solution at the final trial seems to provide a substantial improvement over the logging policy with respect to the unbiased validation performance (blue lines). In reality, we have no access to the generalization performance (red lines), making it impossible to detect this performance degradation, possibly deploying an unsafe policy in the field without even noticing it. 


These observations suggest that optimizing an unbiased surrogate objective is not an ideal strategy and is even harmful in some cases regarding the optimization of the generalization performance. Note that we obtain similar results when random search (RS) is used as an HPO algorithm and DR is used as an OPE estimator as reported in Appendix E. In particular, comparing RS with TPE in terms of the generalization performance, we find that there are no particular differences between the two algorithms for β_0=0,3. Even more surprisingly, when β_0=20, TPE is outperformed by RS, even if TPE is better at optimizing the validation performance. These results further suggest that merely optimizing an unbiased surrogate objective is not a suitable approach for optimizing the generalization performance in HPO of OPL.




 §.§ Theoretical Analysis

Next, we investigate the mechanism causing the somewhat surprising issues observed in the previous section.[Appendix C provides proofs omitted in the main text.]
First, we explain the phenomena from a statistical perspective.
 
Given that V̂ is unbiased, we have the following inequalities. 

    _[V̂(θ̂(); ) ] 
         ≥ V ( θ^* ) ≥_[ V ( θ̂() ) ],

where _[·] takes expectation over every randomness in the logged data , and _ [V̂ (θ̂(); ) ] -  _ [ V ( θ̂() ) ] is the amount of optimistic bias.

Note that, in Eq. (<ref>), V ( θ^* ) is defined as the best generalization performance we could achieve with HPO. Thus, the first inequality in Eq. (<ref>) suggests that the validation performance of the HPO solution θ̂() is better than the best achievable generalization performance in expectation, suggesting that the performance estimation of the HPO solution is optimistic in general. In addition, the second inequality in Eq. (<ref>) implies that the generalization performance of θ̂() is worse than the best achievable generalization performance in expectation, even though the validation performance of θ̂() is likely to be better. As a result, we will often be disappointed with the performance of the HPO solution θ̂ even with an unbiased surrogate (validation) objective. Overall, Proposition <ref> explains the substantial gap between the blue ([V̂ (θ̂() ) ]) and red ([ V ( θ̂() )]) lines observed in Figure <ref>.



Next, we analyze “regret" to understand what causes the optimistic bias in Proposition <ref> and how we can deal with it. For this, we define two variants of regret, which measure the difference between the validation or generalization performances of the optimal hyperparameter and HPO solution.

    r_gen(T; A, )     := V (θ^*) - V ( θ̂_T,A () ) ,
    
        r_val(T; A, )     :=  (θ̂^*; ) -  ( θ̂_T,A (); ) ,

where θ^* := _θ∈Θ V (θ) is the optimal hyperparameter with respect to the generalization performance. θ̂^* = _θ∈Θ(θ; ) denotes the optimal hyperparameter with respect to the validation performance, and θ̂_T,A () is the solution of Algorithm <ref> given budget T and algorithm A. We also define the overestimation bias for a specific hyperparameter θ as τ (θ; ) = (θ; ) -  V(θ). Then, the following implies that a heavy-tailed distribution of overestimation bias during HPO can produce an unexpected gap between the generalization and validation regret.
 
    Given HPO algorithm A, budget T, and logged data , the generalization regret can be written as
    
    r_gen(T; A, )  
               = r_val(T; A, ) + Δτ(θ̂_T,A (), θ^*; ) + C,

    where Δτ(θ_1, θ_2; ) := τ(θ_1; ) - τ(θ_2; ), and C := (θ^*; ) - (θ̂^*; ).


Only the first two terms of the RHS in Eq. (<ref>) depend on the HPO solution θ̂_T,A (), and are thus critical for analyzing the HPO performance. The first term r_val is the validation regret. Under some mild conditions, we can achieve no-regret (r_val(T; A,) = o(1)) with optimization methods such as GP-UCB <cit.>, as we can target the validation performance directly using available data. The second term Δτ(θ̂_T,A (), θ^*; ) is the difference in the extent of overestimation between θ̂_T,A () and θ^*. When the extent of overestimation of θ̂_T,A () is larger than that of θ^*, Δτ(θ̂_T,A (), θ^*; ) becomes large. Therefore, Proposition <ref> suggests that the overestimation bias of θ̂_T,A () can exacerbate the generalization regret of HPO algorithms. More specifically, if an HPO algorithm is likely to sample many hyperparameters whose performance is overestimated ((θ) - V(θ) > 0) and the overestimation bias has a heavy-tailed distribution, the second term of Eq. (<ref>) tends to become large, so does the generalization regret r_gen.
Given this regret analysis, we investigate the distributions of overestimation bias observed in the empirical analysis in Figure <ref>.
This figure implies that TPE more frequently samples hyperparameters incurring a large overestimation bias than RS. According to Proposition <ref>, this is why we do not find the advantage of TPE with respect to the generalization performance.
RS has a worse validation regret than TPE, while overestimation bias of RS is not very problematic compared to TPE. As a result, RS performs similarly to or slightly better than TPE in terms of the generalization performance.
In this way, the heavy-tailed distribution of overestimation bias makes the generalization regret of HPO algorithms (in particular TPE) worse than its validation regret, resulting in optimistic bias and possibly unsafe behavior.




§ HOW SHOULD WE DEAL WITH THE ISSUES?

In this section, we propose two simple corrections, namely (i) conservative surrogate objective and (ii) adaptive imitation regularization, to deal with the critical issues in HPO. We also describe the resulting HPO procedure, which we call Conservative and Imitation-Regularized HPO (CIR-HPO).



 §.§ Conservative Surrogate Objective (CSO)

First, we address the heavy-tailed distribution of overestimation bias ((π) - V(π)) during HPO, as suggested in Figure <ref>. Proposition <ref> implies that the overestimation of the value of hyperparameters sampled during HPO can exacerbate the generalization regret of an HPO algorithm. To deal with this issue, we introduce conservative surrogate objective, which penalizes the validation performance of hyperparameters whose performance has a large uncertainty to avoid the issue of overestimation bias during HPO. Specifically, we propose to use a high probability lower bound of the generalization performance (denoted as V̂_-(·)) as an alternative surrogate objective, which is given as: ( V (π) ≥V̂_- (π; , δ)  ) ≥ 1 - δ where δ∈ (0,1) specifies a confidence level.

A prevalent strategy to construct V̂_-(·) in OPE is to apply a concentration inequality such as Hoeffding and Bernstein <cit.>. A problem is that these inequalities are often overly conservative as they make no assumptions about underlying distribution. Thus, we use an alternative strategy to construct V̂_-(·) based on the Student's t-distribution as follows.

    V̂^t_- (π; , δ) := (π; ) - t_1-δ, ν√(_n ( (π; )) /n-1),

where t_1-δ, ν is the T-value given confidence level δ and degrees of freedom ν.

The upside of Eq. (<ref>) is that it produces a tighter lower bound than aforementioned concentration inequalities. This is because Eq. (<ref>) introduces the additional assumption that the mean of importance weighted rewards (π/π_0)r is normally distributed. This assumption is reasonable with growing data sizes. However, (π/π_0)r often follows a distribution with heavy upper tails, which may make the assumption invalid in a small sample setting. Nonetheless, Appendix E empirically verifies that Eq. (<ref>) is reasonably tight compared with other popular concentration inequalities.











 §.§ Adaptive Imitation Regularization (AIR)

The second technique we propose is adaptive imitation regularization, which tackles the unsafe behavior of the typical procedure. The issue of unsafe behavior suggests that, if logging policy π_0 is better than uniform random or is near-optimal, Algorithm <ref> can produce a solution whose performance is much worse than that of the logging policy. 
Avoiding this problem is non-trivial, because we do not have access to the generalization performance and do not know the optimality of the logging policy in practice. For example, simply setting π_0 as an initial solution does not solve the issue at all, as suggested in Section <ref>. An instant idea might be to imitate the logging policy to some extent:

    π_t (a | x; α, θ_t, ) = (1-α) π̂(a | x; θ_t, ) + απ_0 (a | x),

where θ_t is a set of hyperparameters sampled at the t-th trial. α  (∈ [0,1]) is a regularization parameter, which mixes the policy induced by θ_t and π_0 to construct a policy to evaluate. A large value of α makes π_t closer to the logging policy, possibly avoiding the unsafe behavior. However, if the logging policy is detrimental, we should use a small α so that we can avoid an unnecessary performance degradation. So, a natural question to ask here is: how should we set the regularization parameter α? Again, this problem is non-trivial, as the optimality of the logging policy is unknown when performing HPO.

To overcome this difficulty in correctly setting α, we propose adaptively tuning this parameter over the course of HPO.
Based on the previous discussion, we should apply a strong regularization if π_0 performs well, otherwise we should not imitate π_0.
A key idea here is that we can reason about the optimality of the logging policy by comparing it with solutions sampled during HPO, i.e., {π̂(a | x; θ_t, ) }_t=1^T. If most of the sampled solutions underperform π_0, we can infer that the logging policy is well-performing. To make a valid comparison between the sampled solutions and the logging policy, we apply a Student’s t-test based on the following T-value.

    T(π_1, π_2) := ||/√(_n ()/(n-1)).

where := (π_1) - (π_2) is the performance difference between the two policies estimated by IPS.
Given a null hypothesis (=0) and a normality assumption, T(π_1, π_2) follows a t-distribution with ν degrees of freedom. 
We then calculate the optimality score of π_0 at the t-th trial as follows.

    s_t = 
            
            1     (T(π_0, π_t) ≥ t_1-δ/2, ν and Δ (π_0, π_t) ≥ 0)
    
            - 1     (T(π_0, π_t) ≥ t_1-δ/2, ν and Δ (π_0, π_t) < 0)
    
            0     (otherwise, i.e.,  T(π_0, π_t) < t_1-δ/2, ν)

s_t indicates whether π_0 is better or worse than π_t in a significant level.
If π_0 is better than π_t, then s_t = 1. Instead, s_t=-1 if π_0 is tested to be worse.
If there is no significant difference between π_0 and π_t, the score is zero.

Using the sequence of scores up to the t-th trial, i.e., { s_t'}_t'=1^t, we define adaptive regularization parameter as:

    α_t 
           := α_init + (1-α_init) ·( t/T)^γ·∑_t'=1^t s_t'/t

where α_init∈ [0,1] is an initial regularization parameter and γ  (> 0) is a scheduling parameter for adaptive regularization. 
For example, suppose that s_t=1, ∀ t =1,2,…,T, meaning that π_0 is always better than π_t in a significant level.
Then, following Eq. (<ref>), α_T = 1 and the HPO procedure outputs π_0, because it should be near-optimal.
On the other hand, if s_t=-1, ∀ t =1,2,…,T, meaning that π_0 is always worse than π_t in a significant level, then α_T = 0 and the HPO procedure does not imitate the logging policy at all, because it should be a bad policy.




 §.§ The CIR-HPO Algorithm

Algorithm <ref> describes the CIR-HPO algorithm, which leverages conservative surrogate objective (lines 6 and 9) and adaptive imitation regularization (line 5). δ and γ are meta hyperparameters. δ controls how conservative we would like to be during HPO, and γ controls the scheduling of the adaptive regularization. In Section <ref>, we show that these configurations have some impact on the behavior of CIR-HPO, but we also demonstrate that the default values (δ=0.1 and γ=0.01) work reasonably well in a range of experiment settings. The other inputs are the same as those of Algorithm <ref>. Note that our algorithm is easy to implement with a few additional lines of code and there is no additional computational overhead compared to the typical procedure in Algorithm <ref>.




§ EMPIRICAL EVALUATION

This section empirically compares Baseline (Algorithm <ref>) and CIR-HPO (Algorithm <ref>), employing the same synthetic data and policy class as in Section <ref>.
Note that we compare CIR-HPO against only Baseline because there is no other method proposed for HPO using logged bandit data (comprehensive summary of related work can be found in Appendix B).



 §.§ Baseline vs CIR-HPO

Figure <ref> compares the performance of Baseline and CIR-HPO with varying logging policies (β_0 ∈{0,3,20}). First, when β_0=0 where the logging policy is uniform random, both Baseline and CIR-HPO work reasonably well and succeed in finding a set of hyperparameters that leads to a policy much better than the logging policy. What is notable for this setting is that CIR-HPO is inefficient and slow to converge compared to Baseline due to adaptive imitation regularization, even though it reaches far above the black horizontal line (V(π_0)). At the initial stage of HPO, we do not know how close the logging policy is to the optimal policy. Therefore, the proposed procedure gradually learns the optimality of the logging policy, potentially leading to a slower convergence if the logging policy is far from optimal (such as uniform random). Next, when β_0=3 where the logging policy is better than uniform random, but is not close to the optimal, both Baseline and CIR-HPO slightly improve the logging policy. However, the confidence intervals indicate that CIR-HPO is much more stable than Baseline. In particular, Baseline is much more likely to underperform the logging policy, even though it outperforms the logging policy on average. Finally, when β_0=20 where the logging policy is near-optimal, Baseline outputs a solution that is substantially worse than the logging policy, even though it starts from the logging policy as its initial solution. In contrast, CIR-HPO learns that the logging policy is near-optimal during HPO and strengthens the imitation regularization adaptively. As a result, it prevents the solution from being significantly worse than the (already near-optimal) logging policy, which is compelling, because we do not know the optimality of the logging policy in advance. Figure <ref> illustrates the behavior of adaptive imitation regularization, which suggests that it succeeds in controlling the strength of regularization depending on the optimality of the logging policy.













 §.§ Choice of Meta Hyperparameters

Next, we evaluate the sensitivity of CIR-HPO to the choice of its meta hyperparameters. Figure <ref> shows that the effectiveness of CIR-HPO with different values of δ. The result demonstrates that there is no significant difference among the three values, suggesting that we do not have to care too much about which value to use for δ. In addition, Figure <ref> evaluates different values of γ, which controls the scheduling of adaptive imitation regularization. This result implies that, for a sub-optimal logging policy (β_0=0), the choice of γ has no significant effect on the behavior of CIR-HPO. For a near-optimal logging policy (β_0=20), however, a smaller γ leads to a faster convergence, although all values achieve the same level of performance in the final stage.




 §.§ Ablation Study

We also conduct an ablation study to evaluate the contribution of conservative surrogate objective (CSO) and adaptive imitation regularization (AIR) to the effectiveness of CIR-HPO. To this end, we compare CIR-HPO to CIR-HPO (w/o CSO) and CIR-HPO (w/o AIR) in Figure <ref>. The result demonstrates that both CSO and AIR clearly contribute to the performance of CIR-HPO, while AIR has a more appealing effect (CSO and AIR provide 1.6% and 23.6% improvements, respectively, in terms of the final generalization performance).




 §.§ A Real-World Experiment

In addition to the synthetic experiments, we apply CIR-HPO to the Open Bandit Dataset <cit.>, a publicly available logged bandit dataset collected on a large-scale fashion e-commerce platform. The results suggest that CIR-HPO leads to a better policy compared to the Baseline procedure in terms of the generalization performance, providing a further argument regarding its real-world applicability. The experiment detail and results can be found in Appendix A.




§ CONCLUSION

This work studies the effectiveness of the typical HPO procedure in the OPL setup from both empirical and theoretical perspectives and found that it can fail and even be harmful. In particular, we investigated two surprising issues, namely optimistic bias and unsafe behavior, and showed that a heavy-tailed distribution of overestimation can cause an unexpected gap between validation and generalization. In response, we made two extremely simple corrections to the typical HPO procedure, resulting in the CIR-HPO algorithm, to deal with the issues. Extensive experiments demonstrated that CIR-HPO can be advantageous, particularly when the conventional procedure collapses and causes a significant and undetectable deterioration in the generalization performance. 


named








§ A REAL-WORLD EXPERIMENT




 §.§ Dataset.


To assess the real-world applicability of our CIR-HPO, here we evaluate it on the Open Bandit Dataset (OBD)[https://research.zozo.com/data.html] <cit.>, a publicly available logged bandit dataset collected on a large-scale fashion e-commerce platform. We use 100,000 observations that are randomly sub-sampled from the “Men's" campaign data of OBD. The dataset contains user contexts x, fashion items to recommend as action a ∈ where ||=240, and resulting clicks as reward r ∈{0,1}.

The dataset consists of two sets of logged bandit data collected by two different policies (uniform random and Thompson sampling) during an A/B test of these policies. We regard Thompson sampling as a logging policy and perform HPO of a policy class defined in Section <ref>. We then approximate the ground-truth performance of the tuned policies on the test dataset collected by uniform random. Note that we use the same policy class defined in Section <ref> and the default meta-parameters of CIR-HPO described in Section <ref>. All the experiments were conducted on MacBook Pro (2.4 GHz Intel Core i9, 64 GB).



 §.§ Result.


Table <ref> reports the results (averaged over 5 runs with different random seeds) of the real-world experiment. We compare Baseline and CIR-HPO (ours) combined with IPS and DR as OPE estimators to provide a surrogate objective (i.e., V̂(θ; )). The results suggest that, for both estimators, CIR-HPO outperforms Baseline in terms of the test policy value. This observation provides further arguments for the applicability of our CIR-HPO.




§ RELATED WORK
 



  
Off-Policy Evaluation and Learning.
The basis of our study lies in OPE, which is interested in accurately estimating the generalization policy performance from logged bandit data.
This has been one of the most fundamental problems in contextual bandits and RL, with applications ranging from recommender systems <cit.> to personalized medicine <cit.>.
The most common solution in OPE is to use IPS weighting. IPS provides an unbiased estimate of the policy performance. However, there is a canonical criticism that IPS often suffers from a high variance due to a low overlap <cit.>.
Thus, alternative estimators have been explored to reduce the variance without introducing large bias. 
For example, Self-Normalized IPS (SNIPS) <cit.> aims to reduce the variance of IPS as follows.

    := 1/∑_i=1^n π_e(a_i | x_i)/π_0 (a_i | x_i)∑_i=1^n  π_e(a_i | x_i)/π_0 (a_i | x_i)  r_i.

This estimator normalizes the IPS estimate by the sum of the importance weights (∑_i=1^n π_e(a_i | x_i)/π_0 (a_i | x_i)) to gain stability.
Moving forward, DR leverages a control variate to provide an efficient OPE. The DR estimator is defined as follows.

    := 1/n∑_i=1^n μ̂(x_i, π_e) + π_e(a_i | x_i)/π_0 (a_i | x_i)  (r_i-μ̂(x_i, a_i) ),

where μ̂(x,π_e) estimates _π_e[μ(x,a)]. This estimator is still unbiased and consistent if either the importance weight or the reward estimator is true or consistent. In addition, DR is efficient in that it reaches the lowest achievable asymptotic variance if the reward estimator is correctly specified. There have also been much efforts to further improve DR in a finite sample setting such as Switch <cit.>, More Robust Doubly Robust <cit.>, and Shrinkage <cit.>.

Instead, OPL is the task of improving the decision making policies using only logged bandit data collected from a logging policy <cit.>. The optimal policy maximizes the generalization performance, i.e., π^* := _π V(π). However, this problem is intractable because we cannot know the generalization performance. This raises the need for applying an estimator for its careful approximation, as done in the empirical risk minimization of supervised ML. A typical estimator choice for OPL is IPS <cit.> or its variants <cit.>. A problem is that the variance issue arises here again. Thus, research has been centered around adding regularization to deal with the variance issue during policy training. The fundamental method is variance regularization, which penalizes the policy whose variance in the performance estimation is high <cit.>. Other regularization methods include imitation regularization <cit.> and behavior regularization <cit.>. <cit.> explore the optimistic bias in OPL, and propose a pessimistic reward modeling for OPL based on a Bayesian uncertainty estimation. Instead, we focus on investigating and alleviating the optimistic bias in HPO and empirically illustrate the unsafe behavior, which is specific to our HPO setup.



  
Off-Policy Selection.
Off-Policy Selection (OPS) is a sub-field of OPE and OPL and is closely related to our HPO setting. This is the task of identifying the best policy out of a given finite set of candidate policies using only logged bandit data. We can view this selection problem as a special case of OPL, where the policy class Π is finite. <cit.> study OPS in the contextual bandit setting. They develop a confident OPS procedure, which is based on an Efron-Stein high probability lower bound of the policy performance derived from SNIPS. <cit.> study OPS in RL and propose BayesDICE for estimating the brief over the performance of the candidate policies, which is useful for the selection task. <cit.> theoretically characterize a failure of IPS in OPS. Specifically, <cit.> show that naively applying IPS to OPS can result in an unfair selection in the sense that the procedure can select the worst of the two candidate policies more often than not.
<cit.> and <cit.> conduct empirical studies on OPS of RL polices for several benchmark control tasks. They identify Fitted Q Evaluation as a useful strategy for OPS in RL.
<cit.> also provide an empirical study on OPS of RL policies and propose to combine multiple OPE estimators for an accurate and scalable OPS.

Although these studies on OPS are closely related, our contributions are unique in several ways. First, we focus on HPO, not OPS, which adaptively finds better hyperparameter solutions given a certain budget. By paying attention to HPO, our empirical analysis succeeded in finding that the TPE algorithm, a popular adaptive method in HPO, cannot improve the generalization performance of OPL. This is our unique finding, not captured by previous studies targeting only OPS. Second, we provide a theoretical analysis about the optimistic bias and the gap in generalization and validation regret, explaining the empirical observations. Although <cit.> point out the overestimation bias in the context of OPS, they provide no theoretical explanation. Finally, we propose CIR-HPO based on our empirical observations and analysis. This procedure is specific to the adaptive optimization process and is non-trivial given any existing studies on OPS.




  
Hyperparameter Optimization (HPO).
HPO is a critical element for the success of a range of machine learning algorithms and tasks <cit.>.
For instance, hyperparameter configurations can entirely change the performance of deep neural networks <cit.>.
A typical formulation regards HPO as a black-box optimization problem, where the input is a set of hyperparameters, and the output is a validation performance (an accessible proxy of the generalization performance). 
Among many black-box optimization methods, Bayesian optimization (BO) <cit.>, such as Gaussian process bandit algorithms <cit.> and tree-structured Parzen estimator (TPE) <cit.> have gained particular attention.
These methods sequentially optimize the hyperparameters of a prediction model by leveraging the previous evaluation results to sample the next set of hyperparameters to evaluate.
More specifically, previous evaluation results are used to train a surrogate to model the relationship between hyperparameters and the resulting prediction accuracy. Then, the algorithms balance the exploration and exploitation based on an acquisition function, such as expected improvement and upper confidence bound. Because of the sample efficiency, BO demonstrates a state-of-the-art performance with a limited budget  <cit.>.
It should be noted that, while this study focuses on BO, our discussion can be applied to other optimization methods such as CMA-ES <cit.>, whose efficiency is verified in multiple HPO tasks <cit.>.

A critical convention in HPO research is to evaluate the performance and efficiency of algorithms based solely on the validation performance.
This implies that there is an implicit and often neglected assumption that optimizing the validation performance is a reasonable strategy for optimizing the generalization performance (primary objective). However, it is unclear whether optimizing the validation performance really improves the generalization performance. In fact, Section <ref> sheds light on the fact that ignoring this assumption in OPL can lead to an unexpected failure and a substantial validation-generalization gap. Our theoretical and empirical illustrations might also contribute to a broader HPO community, as there are few studies verifying whether naively setting the validation performance as a surrogate objective is reasonable, given the goal of optimizing the generalization performance.




§ OMITTED PROOFS
 
This section provides proofs omitted in the main text.



 §.§ Proof of Proposition <ref>



Given that θ^* and θ̂ are defined in Eq. (<ref>) and Eq. (<ref>), we have that 

    [V̂ (π̂(·|·, θ̂, _tr); _val ) ] 
       ≥[ V̂(π̂(·|·, θ^*, _tr); _val) ] 
        = V (π̂(·|·, θ^*, _tr) ),

where the last equation follows, as θ^* does not depend on _val.
Similarly, the right inequality of Eq. (<ref>) comes from the fact that θ^* is optimal in terms of the true generalization policy performance.






 §.§ Proof of Proposition <ref>


Our derivation is inspired by the regret analysis provided in <cit.>.
Given the notations introduced in Section <ref>, it follows that

    r_gen(T; A, ) 
        = V (θ^*) - V ( θ̂_T,A () ) 
       = V (θ^*) - (θ^*; )_= - τ(θ^*; ) + (θ^*; ) - V ( θ̂_T,A () ) 
       = - τ(θ^*; ) + (- V(θ̂_T,A ()) + (θ̂_T,A (); ) )_= τ(θ̂_T,A(); )
            - (θ̂_T,A(); ) + (θ^*; ) 
       = Δτ(θ̂_T,A(), θ^*) + ((θ̂^*; ) - (θ̂_T,A(); ))_= r_val(T; A, )
                
        + ((θ^*; ) - (θ̂^*; ))_= C
       = r_val(T; A, ) + Δτ(θ̂_T,A(), θ^*; ) + C.






§ ADDITIONAL THEORETICAL RESULT

We suppose V̂(θ) has the following form:

    V̂(θ) = 1/n∑_i=1^n v(a_i, x_i; θ).

Note that this form is general and encompasses common estimators.
For example, we can obtain IPS estimator by setting v(a_i, x_i; θ) = 1/n∑_i=1^n π_e(a_i | x_i; θ)/π_0 (a_i | x_i) r_i.
The following inequality suggests that the optimistic bias V̂(θ̂(); )
     - V ( θ^* ) decreases at the order 𝒪( 1 / √(n)) as the data increases.


    Suppose |Θ| < ∞ and 0 ≤ v(a,x,θ) ≤ 1 for all a ∈, x ∈, θ∈Θ. For δ∈ (0, 1), the following inequality holds with probability as least 1 - δ:
    
    V̂(θ̂(); ) 
         - V ( θ^* ) ≤√(1/2nlog|Θ|/δ)∈𝒪( 1/√(n)).



We first decompose the optimistic bias as

    V̂(θ̂(); ) 
         - V ( θ^* ) 
       = V̂(θ̂()
         ; ) - V(θ̂()) + V(θ̂())
         - V ( θ^* )_≤ 0
       ≤V̂(θ̂(); ) - V(θ̂()).


Hence, for ϵ > 0,

    ( V̂(θ̂(); ) 
         - V ( θ^* ) ≥ϵ) 
       ≤( V̂(θ̂(); ) - V(θ̂()) ≥ϵ) 
       ≤( ⋃_θ∈Θ{V̂(θ(); ) - V(θ()) ≥ϵ}) 
       ≤∑_θ∈Θ( V̂(θ(); ) - V(θ()) ≥ϵ) 
       ≤ |Θ| e^-2nϵ^2.

We used the union bound and Hoeffding's inequality[By replacing Hoeffding's inequality with Chebyshev's inequality, we can obtain a weaker result even if the boundedness of v(a,x,θ) is not assumed.].
Putting the RHS as δ and solving it for ϵ completes the proof.




 


 











§ SUPPLEMENTAL SIMULATIONS
 
This section empirically evaluates the confidence lower bound of OPE based on concentration inequalities (Hoeffding and Bernstein) and a Student’s t-test. We follow Section <ref> to generate synthetic bandit data. We vary the value of β_0 within the range of {0,3,20}, and the number of validation data |_val| within the range of {400,800,1600,3200,6400,12800}. We also follow Section <ref> to train the evaluation policy π_e. Specifically, we first train μ̂ using logistic regression and form a stochastic policy based on Eq. (<ref>) with β=10.

We use IPS and estimate a high probability lower bound of V(π_e) based on Hoeffding, Bernstein, and t-Test. Given a confidence level δ∈ (0,1), the estimated lower bounds are given as (π_e; _val) - f(δ, _val) where 

    Hoeffding:    f(δ, _val) = w_max√(2 log(2/δ)/n), 
    Bernstein:    f(δ, _val) = √(2 log(2/δ)( (π_e; _val))/n-1)
                    + 7w_maxlog(2/δ)/3(n-1),
    t-Test:    f(δ, _val) = t_1-δ,ν√(( (π_e; _val))/n-1).

Note that n=|_val| and w_max:= sup_(x,a) ∈×π_e(a|x)/π_b(a|x). t_1-δ,ν is the 100(1-δ) percentile of the Student’s t distribution with ν degrees of freedom. The lower bound given by the t-test is based on the assumption that (π_e(a|x)/π_0(a|x))r is normally distributed.

Figure <ref> shows the estimated lower bounds with varying β and sample size, and with a fixed δ=0.05.
The black horizontal line represents the ground-truth policy value V(π_e). We observe that the lower bound given by t-Test is the tightest, while those by Hoeffding and Bernstein are invisible when β_0=20, as they are too loose. Bernstein is always tighter than Hoeffding, but t-Test is even better, particularly when β=3,20 where the logging policy is near-deterministic (w_max is large).

Next, Figure <ref> shows how frequently the estimated lower bounds fail to lower bound V(π_e). Here, we say that a lower bound fails, if (π_e; _val) - f(δ, _val) ≥ V(π_e). The black horizontal line represents the allowed error rate δ. We observe that, in all scenarios, the bounds given by Hoeffding and Bernstein have an error rate of 0, even if they are allowed to produce an error rate of δ, meaning that these lower bounds are overly conservative. In contrast, the lower bound given by t-Test makes some errors, but the error rate is around δ. Although the normality assumption might fail in OPE with small sample sizes, we empirically verify that t-Test produces a lower bound tighter than those of Hoeffding and Bernstein, and its error rate is around the allowed value.








