Dynamic Continuous Hyperparameter Tuning for Generalized Linear Contextual Bandits

Q2

In our work we put the running time of our method with all baselines in Appendix A.4.5 for the 10 cases corresponding to Figure 1 plots 1-10. For ease of your review, we copied the results from Appendix A.4.5 in the following tables. Furthermore, we reproduced the last 4 cases in Figure 1 (plots 11-14) these days and displayed the results for completeness:

LinUCB

UCB-GLM

GLM-TSL

Laplace-TS

GLOC

SGD-TS

From the above tables, we can see that all existing methods and our CDT can run very fast in practice, and our CDT is only slightly more expensive in computation (CDT only takes few more seconds). In addition, we can observe that the main computation time comes from the contextual bandit algorithm we tune on. Specifically, GLM-TSL requires much more running time than all other methods under different tuning methods. Therefore, our CDT significantly outperforms all existing baselines without increasing much computation.

Q3.

Thank you very much for your careful review. We will correct this typo in the revision.

We sincerely value the time you've dedicated to reviewing our work. Please let us know if our response has sufficiently resolved your concern and improved your opinion of our work, and we are more than happy to engage in any further discussion with you.

Thank you for your insightful comments on our work, and we are pleased to know that you find our work solves an important practical problem and achieves significant performance improvements in comprehensive experiments. Please see our responses to your concerns as follows:

Weakness:

We appreciate your careful review. To use our algorithm 1 as the meta-algorithm in our CDT framework (algorithm 2), the values of $T_1$ (warming time) and $T_2$ (epoch length) only depend on the number of hyperparameters we want to tune ($p$), which is known in the beginning. This is because we can safely use an upper bound $p$ of the unknown zooming dimension $p_{z,\*}$ in practice, and the final regret deduced in our Theorem 4.2 will depend on $p$ instead of $p_{z,*}$. For the issue of unknown $T$, we can utilize the widely-used doubling trick [1] when $T$ is unknown with the same regret bound held. We will mention this trick in the revision of our work.

In section 4.1, we mention that the choice of $H$ could be handled by introducing an extra layer for the completeness of theory, and we provide a detailed analysis in Appendix F with solid theoretical support. However, we don’t use this procedure in our CDT framework due to concerns about the efficiency of the three-layer structure in practice as well. As in Section 4.1, we illustrate that the choice of $H$ could be handled by introducing this extra layer mostly for the completeness of theoretical analysis.

For the restriction on the value of $T$, our algorithm doesn’t have to assume the value of $T$ is larger than certain values in theory, and the warming-up time $T_1$ is always strictly less than $T$. For practice, it is noteworthy that bandit algorithms cannot achieve good performance if $T$ is small since they estimate the model parameters on the fly, not to mention the more difficult model selection task for bandits. From Figure 1, we can clearly observe that the cumulative regrets of our CDT framework are smaller after some warm-up iterations in most cases, which validates that our CDT could perform better than all existing baselines regardless of the magnitude of $T$.

[1]. The adversarial multi-armed bandit problem. P. Auer et al., IEEE Annual Symposium on Foundations of Computer Science, 1995.

Q1:

Thank you for your insightful questions. It is widely known that there is a huge discrepancy between the theoretical analysis and practical performance for bandit algorithms. From Figure 1, we can see that the theoretically derived hyperparameters usually yield terrible or even linear cumulative regret for most algorithms while they achieve the optimal regret bound in theory, and this is because most theoretical optimal settings are way too conservative in practice. To obtain better practical performance, intuitively we should choose less conservative exploration hyperparameters, which will lead to worse regret bounds. This fact is the motivation why we study this intriguing practical problem: how to choose hyperparameters for bandit algorithms in practice to adapt to different environments with superior performance while some decent regret bounds can still hold. As we mention in our work, we mostly concentrate on the practical performances of our CDT framework in our paper. And according to our section 4.2 and our proof in Appendix G, it is very difficult and challenging to present the novel theoretical analysis of Theorem 4.2. Furthermore, the existing work on bandit hyperparameter tuning (e.g. "Syndicated bandits: A framework for auto-tuning hyper-parameters in contextual bandit algorithms") intrinsically can't achieve the best regret bound of the base algorithms without stringent assumptions. Specifically, Syndicated can only achieve the $\tilde O(T^{2/3})$ bound of regret with finite number of candidate values for each hyperparameter, and their regret bound will becomes infinitely large under our problem setting with continuous candidate sets. These facts also demonstrate the significance of our theoretical analysis, even though the focus of our work is mainly on practical performances.

Weakness 4:

In practice, most studies would have the stochastic rewards bounded, e.g., in the interval (0,C) for some positive constant $C$, where we could naturally take this hyperparameter as $C/2$ when applying Algorithm 1 and Algorithm 2. Note we use this implementation in our experiments and it works very well as shown in our extensive simulations and real datasets.

We really appreciate your valuable insights. Please let us know if our response has sufficiently resolved your concern and improved your opinion of our work, and we are more than happy to engage in any further discussion with you.

Thank you for your insightful comments. We are happy that you are positive on our contributions since you find our work is well-motivated in practice and our method performs well in extensive conducted. Please see our response to your concerns.

Weakness 1:

Thank you for your insightful questions. In Section 4.1, we illustrate that the choice of $H$ could be handled by introducing an extra layer mostly for the completeness of theory, and we provide a detailed analysis in Appendix F with solid theoretical support. We agree with the reviewer that in practice this extra outer layer may not bring many benefits since between each two outer EXP3 pulls we don’t have many iterations to explore the Lipschitz structure with restarts. However, in our CDT we don’t have to use this procedure, as we mention in the last paragraph of Section 4.1.

Weakness 2: Thank you very much for your valuable comments. As we emphasize in our response to Weakness 1, we use the master EXP3 algorithm to choose the base Algorithm 1 with different epoch parameters mostly for the completeness of our theoretical analysis. And this is not the main concentration of our work. However, we believe the methodology of our main algorithm CDT aligns with your speculation here: instead of using the same hyperparameter combination for a certain period of time, our CDT algorithm can choose the hyperparameter values and then update its state at each iteration sequentially. This can help prevent the circumstance you mention in weakness 2 since even though an eventually good hyperparameter combination may yield bad performance in the beginning, we still have lots of iterations to update our estimate promptly, and hence this hyperparameter combination will become favorable again after rounds of updates. Moreover, the restarting method in our CDT can further help to alleviate this issue: it can discard the historical memories generated from different environments periodically so that the eventually good hyperparameter combination will not be ruled out.

Weakness 3: “have an adaptive restart schedule where one restarts more often during earlier rounds and less toward later rounds?”

Thank you for your helpful comments. We use the fixed length epochs to keep consistent with our theoretical analysis, and we can observe that it works very well in practice. To show whether it is more efficient to restart the algorithm less often in the long run, we reproduced the experiments in Figure 1 while increasing the restarting period by a multiplier of 2. The results are displayed in the following table:

From the Table, we can observe that the CDT in our paper and CDT with increasing restarting epochs yield comparable performance: the CDT in our paper is better in 6 cases while the CDT with increasing restarting epochs wins 8 cases. Both algorithms can beat all the existing baselines consistently and achieve state-of-the-art results. And it is a interesting future work to study how to adaptively increase the restarting epoch with solid theoretical guarantee.

Weakness 3: “There could be discontinuities in the rewards as a function of hyper-parameters.”

As in "Syndicated bandits: A framework for auto-tuning hyper-parameters in contextual bandit algorithms", our work assumes that the arms in the arm set $X_t$ are drawn IID from some unknown distribution. Therefore, considering the randomness of the action set in each iteration, we can anticipate that the expected performance of the bandit algorithm should be similar with close hyperparameters given historical information (F_t) fixed. We will emphasize this point in our problem setting in the revision. We further use Figure 2 in Appendix A.2 to demonstrate the Lipschitzness of reward w.r.t hyperparameter selection empirically, and it is evident that this figure authenticates our assumption very well.

Weakness 1:

Thank you very much for your insightful comments. For the work “Regret Bound Balancing and Elimination for Model Selection in Bandits and RL”, we will cite it in the revision of our paper, since it discusses how to choose the confidence radius of OFUL on the fly. However, we’d like to point out that this work mainly concentrates on the general model selection in bandits and reinforcement learning, and the theoretical regret bound deduced in this work also depends on the number of candidates $M$, which is infinitely large and hence becomes meaningless in our problem setting. For experiments, the algorithm proposed in this work is also inefficient since it has to update each active base candidate at every iteration, and the implementation of this algorithm also relies on some unspecified parameters such as $\kappa$. This implies that this algorithm could not be easily adapted to the hyperparameter tuning of any contextual linear bandit. Note in Remark B.1 in Appendix B, we illustrate why the general bandit model selection method can’t be used for hyperparameter tuning of bandit algorithms, and “Syndicated bandits: A framework for auto-tuning hyper-parameters in contextual bandit algorithms” is the only existing work with theoretical guarantees that considers exactly hyperparameter tuning of bandit algorithms.

For “Syndicated bandits: A framework for auto-tuning hyper-parameters in contextual bandit algorithms”. In theory, the general regret bound is of order $\tilde{O}(T^{2/3} + \sqrt{MT})$, where $M$ is the number of hyperparameters considered in the candidate set. Note that this regret bound also becomes futile in our problem setting since $M$ is infinitely large, and hence this regret bound becomes infinite. Note it is intrinsically much more difficult in theory for the infinite-arm case compared with the finite-arm case: for example, the minimax regret bound for multi-armed bandit is of order $\tilde{O}(\sqrt{T})$ while the minimax regret bound for the continuum-armed bandit in $[0,1]^d$ is of order $\tilde{O}(T^{(d+1)/(d+2)})$. This fact means that for continuum-armed bandit it is impossible to recover most of the results in multi-armed bandits in the same order. In experiments, we include the TL or Syndicated in all of our simulations and real datasets as an important baseline, and we can evidently observe the practical advantage of our proposed CDT over all existing baselines.

Weakness 2:

Thank you very much for your valuable questions. As in "Syndicated bandits: A framework for auto-tuning hyper-parameters in contextual bandit algorithms", in our work we also assume that the arms in the arm set $X_t$ are drawn IID from some unknown distribution. Therefore, without an oblivious adversary choosing our arm set, we can anticipate that the expected performance of the bandit algorithm should be similar with close hyperparameters given other conditions (F_t) fixed. We will emphasize this point in our problem setting in the revision.

Weakness 3:

As we mention in our response to Weakness 1, in "Syndicated bandits: A framework for auto-tuning hyper-parameters in contextual bandit algorithms", the general regret bound is of order $\tilde{O}(T^{2/3} + \sqrt{MT})$. Their algorithm can only achieve the $\tilde{O}(\sqrt{T} + \sqrt{MT})$ and $\tilde{O}(T^{4/7}+ \sqrt{MT})$ bound of regret when there is only one hyperparameter to be tuned with some assumptions held. Specifically, to obtain the order $\tilde{O}(\sqrt{T} + \sqrt{MT})$, their work has to assume that the theoretical optimal exploration rate is smaller than any element in the candidate set. This assumption is stringent and unrealistic since it is widely known that the theoretical exploration rate is very large and conservative, and hence the elements in the candidate set should be smaller than the theoretical value in practice. On the other hand, we can observe that their regret bound also depends on the number of candidates $M$ in the order $\sqrt{MT}$, and $M$ becomes infinitely large under our problem setting. This fact implies that all their regret bounds are actually infinitely large and hence meaningless under our problem setting.

We sincerely value the time you've dedicated to reviewing our work. And we respectfully hope you could re-evaluate our work if your concerns have been decently addressed.

Weakness 1:

Thank you very much for your valuable comments. Note $M$ in our rebuttal refers to the number of possible candidates for each hyperparameter. For example, $M$ could be the number of possible choices for the hyperparameter "exploration rate". To make it more clear, the general regret bound of “Syndicated bandits: A framework for auto-tuning hyper-parameters in contextual bandit algorithms” can be formulated as:

$\tilde O(T^{2/3} + \sum_{i=1}^L\sqrt{n_lT})$

where $L$ is the number of hyperparameters (usually small for contextual bandits) and $n_l (\text{we call it }M)$ is the size of candidate value set for the $l$th hyperparameter. Here we consider tune each hyperparameter in an interval, which means the candidate set for each hyperparameter is a continuous interval and hence contains infinitely many candidates ($M = +\infty$). Note all the existing work, e.g. Syndicated, will incur linear regret under our problem setting since $M = +\infty$. In Appendix A.4.3, we firmly validate the necessity of tuning hyperparameters in a continuous set instead of a user-defined set with extensive experiments: finding the optimal hyperparameter combination for different bandit algorithms is a black-box problem and hence it is impossible for us to construct decent value candidate sets for all hyperparameters. If we discretize the interval finely, then the large size of the candidate set would evidently hurt the performance, as shown in the experiments. On the other hand, our proposed CDT could adaptively “zoom in” on the regions containing this optimal hyperparameter value automatically, without pre-specifying the candidate set.

Weakness 2:

Thank you for your further comments. Yes, we acknowledge that the optimal regret bound is of order $\tilde O(\sqrt{T})$. However, as in “Syndicated bandits: A framework for auto-tuning hyperparameters in contextual bandit algorithms”, it is inevitable to suffer from the suboptimal regret bound due to the enormous difficulty of bandit hyperparameter tuning in theory. Note “Syndicated bandits: A framework for auto-tuning hyperparameters in contextual bandit algorithms” also considers the generalized linear contextual bandits with theoretical guarantee. Furthermore, we consider a more challenging problem in our work with infinitely many candidate values for each hyperparameter, and under this problem setting all the existing theory in Syndicated and other general bandit model selection problems will be futile. Moreover, as we mention in Section 4.1, our work is more practical oriented and the extensive experiments in our work significantly validate the high efficiency of our algorithm over all baselines. And we include a non-trivial theoretical analysis for the completeness of our work in theory.

Weakness 3:

Thank you very much for your clarification. On the one hand, as we mentioned in our response to Weakness 1, the regret bound of Syndicated is $\tilde O(T^{2/3} + \sum_{i=1}^L\sqrt{n_lT})$, which becomes infinitely large under our much more difficult problem setting ($M = + \infty$). And we believe it is not very fair to compare our regret bound with the one in Syndicated since they considered an easier setting with finite $M$. On the other hand, even under the stochastic bandits, for continuum-armed bandits it is impossible to recover most of the results in multi-armed bandits in the same order. As the example in our first response to Weakness 1, the minimax regret bound for multi-armed bandit is of order $\sqrt{T}$ while the minimax regret bound for the continuum-armed bandit in $[0,1]^d$ is of order $T^{(d+1)/(d+2)}$. This fact also implies that it is intrinsically inevitable to get a worse regret bound when we consider the continuous set for hyperparameter tuning.

We sincerely appreciate your valuable feedbacks on our work. Please let us know if our response has sufficiently resolved your concern and improved your opinion of our work, and we are more than happy to engage in any further discussion with you.

Thank you very much for taking your time to review our work and raise insightful comments. In our last feedbacks, we have carefully examined your questions and comments, and then presented a solid response to your concerns.

Specifically, we first clear up some potential misunderstandings from you regarding our work: in our problem setting, each hyperparameter can take any value in a continuous interval (infinitely many candidate values), and our algorithm can tune multiple hyperparameters simultaneously. In other words, $M$ in our response stands for the number of candidate values for each hyperparameter, instead of the number of hyperparameters we want to tune. Note all the regret bounds in existing literature (e.g. "Syndicated") will becomes infinitely large since their values depend on the number of candidate values $M$ for each hyperparameter. Not to mention that how to choose the candidate values is a black-box problem and hence unclear. Then, we also emphasize the significance of our theoretical analysis under a much more difficult setting, where all the existing theoretical results will fail.

We sincerely appreciate your valuable feedbacks on our work. Since the discussion deadline is approaching, we respectfully hope you could let us know whether our response has sufficiently resolved your concerns and improved your opinion of our work. And we are more than happy to engage in any further discussions with you.