We thank the reviewer for responding to our rebuttal and hope that we have adequately addressed their concerns regarding the design of our algorithms and our results. We kindly ask the reviewer to take this into consideration in their final assessment.
We would like to emphasize again that our contributions are focused on the theoretical aspects of combinatorial bandits. Our paper is already dense with significant theoretical contributions, including new gap-free regret bounds, improved computational complexity, and a novel stochastic algorithm with analysis that combines the computational efficiency of Thompson Sampling with the analytical strengths of optimistic algorithms, all of which contribute to a deeper understanding of combinatorial bandits.
The empirical study we provided in the rebuttal primarily serves to demonstrate that our algorithms can be implemented, achieve the expected logarithmic regret expected by the theory, and perform well in practice compared to their competitors. We acknowledge that this study alone is not sufficient, and we will strive to conduct more thorough experiments in the final version (although we do not expect it to be considered as a contribution of our current work).
Regarding the additional questions, due to time constraints during the rebuttal phase and the high computational cost of existing combinatorial bandit algorithms, our experiments were conducted on a single synthetic dataset and should be interpreted with caution.
> I have reviewed the experiments [...].
Note that due to the log-log scale, the early shape of the regret curves should be interpreted with caution, as they correspond to only a few rounds $(\approx 30)$ compared to the total number of rounds $(\approx 10\,000)$. Furthermore, the curves are only valid after the measurement at $t=10$; prior to that, they mistakenly appear flat. The early behavior is primarily influenced by how the algorithms perform initial exploration and may be affected by hyper-parameter calibrations, which were not thoroughly optimized in this case.
What is more important to observe in these experiments is the behavior at the end of the regret curves:
- Both OLS-UCB-C and ESCB-C-approx appear to have converged and entered the logarithmic regret regime. The difference between them seems to be due to constant terms related to their exploration strategies, but it does not seem to increase over time.
- Towards the end, the per-round regret of C-UCBV is higher than that of OLS-UCBV, indicating that its cumulative regret will eventually be higher. This synthetic instance was "easy" enough for both algorithms to reach the logarithmic regime. However, it's important to note that in more challenging instances, ESCB-C only guarantees a worst-case regret of $O(T^{2/3})$, while our algorithm provides a stronger guarantee of $O(\sqrt{T})$.
> Covariance-Adaptation and error bars.
Indeed, having error bars is important, and we will include them in the final version. Unfortunately, we did not have time to include them in this preliminary experiment presented in the rebuttal. The adaptivity of our algorithms (and ESCB-C) to the covariance structure of the base items can be inferred from the per-round regret (i.e., the derivative) at the end of the plot. We observe that ESCB-C and OLS-UCB-C maintain a relatively similar distance asymptotically. In contrast, C-UCBV (C-UCB with plugged-in variance estimators) has also converged, but its final per-round regret is slightly worse than both. This is likely because C-UCBV does not account for covariance but instead assumes worst-case correlations between items. However, we must emphasize that this could be an artifact, and these experiments are not thorough enough to draw definitive conclusions.