AdaO2B: Adaptive Online to Batch Conversion for Out-of-Distribution Generalization

1. Although the motivation for investigating OOD generalization of the online-to-batch (O2B) conversions is convincing, it is actually not clear why the O2B of bandits algorithms should be focused. The authors should provide more explanations on the motivation. Moreover, it is natural to ask whether the OOD generalization of O2B with full-information algorithms has already been addressed.
2. I am not convinced that the generalization error defined in Eq. (3) can reflect the generalization ability of the estimated reward parameters $\theta$, because the first term $C_{ER}$ is an upper bound that does not depend on $\theta$, and the second term directly computes the reward by using $\theta$. Note that in the bandit setting, one should first utilize the estimated parameters $\theta$ to select an arm, and the reward of the arm is computed on the underlying model of the reward function i.e., \theta^\\ast.
3. It is not clear whose regret is reflected by the weighted regret defined in Eq. (4). So, combining with the above concern on the definition of the generalization error, I am not convinced that the generalization error bound derived in this paper can really reflect the hardness of OOD generalization.
4. Although the authors argue that "theoretical analysis provides justification for why and how the learned adaptive batch learner can achieve OOD generalization error guarantees", the proposed algorithm actually is not strictly designed under their theoretical results. Specifically, it is too heuristic to learn the weights via the Multi-Layer Perceptron.

In the context of OOD settings with online-to-batch conversion techniques, the theoretical contributions of the paper fall short of providing novel insights. The established relationship between the generalization error, online learning stage regret, and distribution divergence seems somewhat intuitive and might be anticipated by some information-theoretic results. Given the paper’s emphasis on OOD settings, it is noticeable that the algorithmic design leans more towards addressing distribution shift issues rather than actively identifying potential outliers. Additionally, the parameter $\beta$ appears to be important in determining the final model’s performance. Due to this, conducting ablation studies to show the impact of different choices of $\beta$ values would have been a valuable addition to this work.

Weakness 1: The proof of Theorem 1 can be decomposed into calculating the difference of $\theta_{ada}$ and $\theta^*$ in training dataset $P$ and the distance for $\theta_{ada}$ in distribution $P$ and $Q$. For the first part, the proof is the same compared to Theorem 3.1 of [1]. For the second part, this work uses the results of [2]. The technical novelty of Theorem 1 is not clear and needs to be discussed in detail.

Weakness 2: In the experimental part, the experimental dataset is variable in different episodes, and the AdaO2B framework prefers to assign larger weight $\beta_n$ to those $\theta_n$, whose training distribution is similar to the testing distribution $Q$. However, in the theoretical analysis part, this work assumes training distributions in different episodes $n$ are the same, which does not capture the dynamic nature of the data stream in the training process and does not match the intuition of adaptive $\beta_n$. Hence, it will be better to discuss the distribution shift in the training process to make up the difference between theoretical analysis and experimental results.

[1] Orabona, F. (2019). A modern introduction to online learning. arXiv preprint arXiv:1912.13213. [2] Shui, C., Chen, Q., Wen, J., Zhou, F., Gagné, C., & Wang, B. (2020). Beyond H-divergence: Domain adaptation theory with jensen-shannon divergence. arXiv preprint arXiv:2007.15567, 6.

The main weaknesses of this paper are in the areas of 1) novelty; 2) soundness of the theoretical analysis; and 3) completeness and significance of the empirical evaluations.

Regarding novelty, there is already a great deal of prior work on learning adaptive or hierarchical mixtures. The adaptive method proposed in this paper was previously proposed by Jacobs et al. 1991 (https://www.cs.toronto.edu/~hinton/absps/jjnh91.pdf), though not cited here. And adaptive mixtures have been employed elsewhere in the recommations space: Kumthekar et al. 2019 (https://research.google/pubs/pub49380/) focus on adaptively mixing shared models for multitask learning, which is admittedly different from handling temporal drift.

Regarding theoretical soundness, my main concern is that the bound in theorem 1, equation (5), does not seem particularly useful, but perhaps I am misunderstanding it. It has two terms: the first is what I would call the "value-add" term of using an adaptive mixture rather than a fixed mixture. And the second describes the worst-case / "out of distribution" penalty which cannot be alleviated by the proposed method. Therefore, only the first term is of potential use. But here, the value-add term is just assumed to have some worst-case fixed upper bound "C_{WREG}" and the denominator is the sum of the mixture weights \Beta_{1:N}, which is often constrained to be equal to 1.0. So I am not sure what useful information this bound conveys.

Further, the corollary in equation 6 puzzles me because it assumes that nature's densities p_i and q_i are paired in some fashion. But in actuality there is no guarantee that nature will swap q_i for p_i; it could instead swap q_j with p_j. And therefore a double sum seems more appropriate:

   \sqrt{ 2 logK  +  K \sum_{ij} \pi_i \tau_j D(p_i || q_j) }.

Finally regarding the empirical results, I have two concerns:

i) In experiments on KuaiRecs (the real-world dataset), AdaO2B shows no benefit over using a fully online (FOL) bandit. Therefore, I am not sure why one would use it, especially since it requires training constituent models online anyway.

ii) The experiments do not show comparisons against the baseline of training a single recommender system offline, directly on the logged bandit feedback. This baseline approach might work just as well as, or better than, the proposed adaptive mixture-of-bandits model. And it is the more obvious thing to try.