We sincerely appreciate your thoughtful and encouraging review. Below, we provide point-by-point responses to your comments. We look forward to refining our manuscript to address these valuable suggestions.

Theoretical Claims:

We sincerely thank you for your thoughtful and encouraging comment. As you rightly pointed out, obtaining valid concentration bounds for the non-zero component $X$ is a core challenge in both algorithm design and regret analysis. Lemma 2.2 (sub-Weibull noise) and Lemma A.1 (heavy-tailed noise) are indeed key technical contributions that enable us to build confidence intervals. By decoupling the ZI mechanism from the tail structure of X, these lemmas preserve tightness without imposing overly conservative assumptions.

We also appreciate your suggestion regarding Section 4.2. Due to space limitations, we deferred many details of the regret analysis to the appendix, including several nontrivial proof techniques that are tailored to the ZI structure and product-form rewards. In the revision, we will explicitly outline in the main text which parts of the analysis are standard and which are novel, to help readers more clearly appreciate the theoretical contribution.

Experimental Designs & Analyses:

All plots show mean cumulative regret over 25 independent runs, with shading indicating $\pm 1 / 10$ standard deviation. Sometimes the shaded region is nearly invisible when variability is small. We will update figure captions and the main text to clarify this, ensuring the error bars' scale is apparent.

To improve reproducibility, we will explicitly detail our reward models:

• Gaussian: Nonzero parts from a $N(\mu_k, 1)$, with $\mu_k \sim U(0, 100)$;

• Mixed Gaussian rewards: The non-zero rewards from

$$(1 - p_k) \times N \left( \frac{\mu_k}{2(1 - p_k)}, \sigma^2\right) + p_k \times N \left( \frac{\mu_k}{2p_k}, \sigma^2\right)$$

which ensures that the overall mean of the non-zero component is $\mu_k$.

• Exponential: The non-zero rewards from an exponential distribution with mean $\mu_k$, where $\mu_k \sim U(0, 100)$.

We will include these details in Section 5 and Appendix C of our revised submission.

Relation To Broader Scientific Literature:

Thank you for bringing [1] to our attention. We will include this citation in our introduction, noting that it treats zero-inflated count outcomes via Poisson/negative binomial models. Our method accommodates more general real-valued ZI rewards (Gaussian, exponential, heavy-tailed, etc.). Despite this difference in scope, we recognize the close connection and will highlight its relevance.

Other Comments & Suggestions:

• L038: We will include the specific reference to Chapter 9 in [1], consistent with the other citations in the manuscript.

• L154: Yes, the assumption refers to a common modeling assumption for reward distributions in the design and analysis of bandit algorithms. We will clarify this in the revised version.

-L177: This was intended to refer to a corollary comparing constant terms in regret bounds between our method and the canonical UCB algorithm. We appreciate the reviewer catching this and will correct it in the final version.

• R238: The ``less than or equal to" symbol ($\lesssim$) is used to indicate inequality up to constants independent of bandit specific parameters.

• R230: We appreciate the clarification. Our intention was to say that these results are established within this paper. We will revise the sentence to avoid ambiguity.

We also appreciate your suggestions regarding inline equations, grammar, and formatting. We will use the post-acceptance phase to improve readability, split long inline equations, and proofread thoroughly.

Question:

We appreciate your helpful question. The purpose of Figure 1(a) is to present a motivating real-world example (introduced in [L81]) that illustrates the prevalence of zero rewards in practice. This highlights the limitations of traditional bandit algorithms that do not account for such structural sparsity and motivates the need for methods that explicitly model the zero-inflated nature of the reward.

Figure 1(b) compares illustrative confidence bounds under different algorithms. In addition to our proposed method and the Monte Carlo baseline (constructed from empirical samples), the other bounds correspond to those used by the UCB baselines described in Appendix C (Simulation Supplement). We acknowledge that these details were not sufficiently clarified in the main text, and we will revise the captions and discussion accordingly to make the interpretations of both Figure 1(a) and 1(b) more transparent in the updated manuscript.

References:

[1] Liu, X., Deliu, N., Chakraborty, T., Bell, L., & Chakraborty, B. (2023). Thompson sampling for zero-inflated count outcomes with an application to the Drink Less mobile health study. arXiv preprint arXiv:2311.14359.

[2] Lattimore, T., & Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.

Thank you for your thorough and constructive feedback. Below, we respond to each of your points. We hope this addresses your concerns.

Claims & Evidence:

Our main independence assumption is that $X$ (nonzero rewards) and $Y$ (the indicator of a nonzero outcome) are independent in the decomposition $R = X \cdot Y$. We do not assume independence across arms or across time. This independence assumption is introduced mainly for notation simplification and analytical tractability, as discussed in lines L130–L140. We agree we should state this more explicitly in both the MAB and GLM contexts.

Methods & Evaluation Criteria:

We appreciate the suggestion to detail computational cost. We have found that our ZI-based approach retains the same big-O complexity as standard baselines for both MAB and GLM. The only difference is a small constant overhead from maintaining two estimators (one for the zero indicator, one for nonzero magnitude) instead of a single estimate of $R$. We will clarify this in our revision.

Theoretical Claims:

Thank you for your insightful suggestion. We agree that connections to heavy-tailed bandits [1,2,3] and asymmetric bandits [4,5,6] are relevant and worth highlighting. While our approach is specifically tailored to the ZI structure, it remains compatible with heavy-tailed settings (e.g., allowing only $(1+\epsilon)$-th moments as in [1,2,3]) and provides a structural alternative to modeling asymmetry, rather than relying on auxiliary tools like empirical quantiles or calibration, which increase computational complexity (e.g., [5] and [6]). We will incorporate these related works and clarify distinctions in our revision—thank you again for the valuable feedback.

Experimental Designs & Analyses:

Following your advice, we included Q-SAR [6] for MAB and SPUCB [7] for GLM as baselines in two uploaded anonymous figures (Figure 1 and Figure 2). In zero-inflated regimes, Q-SAR's reliance on quantile updates can become unstable when zeros dominate; it tends to over/underestimate crucial quantiles. In contrast, our ZI-based methods explicitly model the sparse reward mechanism, yielding more stable learning and lower regret in both MAB and contextual settings.

We also evaluated a standard A/B testing baseline (uniform allocation) in a zero-inflated Gaussian environment with periodically drifting means, as shown in the anonymous figure. This controlled synthetic setting introduces nonstationarity by perturbing each arm’s mean with Gaussian noise (standard deviation 5) every $T/3$ rounds. We also explored alternative drift magnitudes and observed qualitatively similar trends. Even under moderate nonstationarity, our UCB and TS methods adapt better than fixed allocation. We will include these comparisons in the revised appendix.

Supplementary Material & Essential References Not Discussed:

We agree the current appendix is lengthy. To address this, we will: (1) Add a summary table at the appendix start, mapping each section to its key results; (2) Reduce repetition and highlight core takeaways, ensuring a clearer structure. We will also reference in the related work and clarify the ties to zero-inflated approaches.

Questions:

Determining whether an environment is zero-inflated or heavy-tailed can be guided by domain knowledge (e.g., high-frequency ``no feedback" in ads or loan offers) and data diagnostics (e.g., moment tests [9], sub-G plots [10]). Though a rigorous classification lies beyond this paper’s scope, we consider it an important direction for real-world deployments.

References:

[1] Bubeck, S., Cesa-Bianchi, N., & Lugosi, G. (2013). Bandits with heavy tail.

[2] Zhang, J., & Cutkosky, A. (2022). Parameter-free regret in high probability with heavy tails.

[3] Cheng, D., Zhou, X., & Ji, B. (2024). Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting.

[4] Zhang, M., & Ong, C. S. (2021). Quantile bandits for best arms identification.

[5] Shi, Z., Kuruoglu, E. E., & Wei, X. (2022). Thompson Sampling on Asymmetric Stable Bandits.

[6] Zhang, M., & Ong, C. S. (2021). Quantile bandits for best arms identification.

[7] Peng, Y., Xie, M., Liu, J., Meng, X., Li, N., Yang, C., … & Jin, R. (2019, August). A practical semi-parametric contextual bandit.

[8] Liu, X., Deliu, N., Chakraborty, T., Bell, L., & Chakraborty, B. (2023). Thompson sampling for zero-inflated count outcomes with an application to the Drink Less mobile health study.

[9] Trapani, L. (2016). Testing for (in)finite moments.

[10] Zhang, H., Wei, H., & Cheng, G. (2023). Tight non-asymptotic inference via sub-Gaussian intrinsic moment norm.

We sincerely thank you for your thoughtful and encouraging feedback. Below, we respond to your comments point by point, and we hope our replies provide clear and satisfactory answers to your questions.

Claims & Evidence:

While sub-Gaussian or sub-Weibull assumptions allow existing algorithms to attain minimax rates, ZI introduces unique challenges. In particular, a preponderance of zeros can inflate variance estimates and skew concentration. By explicitly modeling and leveraging the ZI structure, our approach preserves minimax guarantees across a wide array of distributions, including those with heavy-tailed nonzero components. We will revise Lemma 2.1 and related text ([L161–L164]) to emphasize these benefits more clearly.

Methods & Evaluation:

We tested our approach with bounded, skewed Beta rewards (anonymous figure) of the form $X_k = 2\mu_k Beta(p_k, p_k)$ so that $E[X_k] = \mu_k$. Our UCB method outperforms baselines in most settings except when zero-inflation is minimal, where an exact Hoeffding-based UCB can be slightly better (though it relies on unavailable knowledge). Even at high $p_k \sim U(0.75, 0.95)$ Low ZI (anonymous figure), our approach remains strong under Gaussian and Exponential components. We will add these experiments to the appendix.

Experimental Designs & Analyses:

We agree that increasing simulation replications to 100 will yield more reliable comparisons, and we have begun doing so for both MAB and GLM contextual bandits. The performance gap between synthetic and real data likely stems from unobserved confounders in the real-world dataset; still, under the same ZI assumptions, our UCB and TS methods outperform other baselines. We will clarify these observations in the revision.

Weakness 1:

Our discussion of heavy-tailed rewards refers to the conditional distribution of nonzero outcomes, since the zero mass makes the entire distribution no longer heavy-tailed in the strict sense. By modeling the zero mechanism separately, our approach avoids erroneously inflating or deflating uncertainty due to frequent zeros, enhancing robustness across diverse reward distributions.

Weakness 2:

As highlighted in [L421–R423], our current allocation of the failure probability between the concentration bounds for $X$ and $Y$ can be conservative. A more refined analysis, possibly peeling confidence sets for $X$ and $Y$ individually, could yield tighter bounds and smaller constants, aligning with advanced concentration methods (e.g., Section 9.3 of [1], Section 1.2 of [2]). We will mention these refinements in the revision.

Other Comments & Suggestions:

We have fixed the reference error at [176R]. Furthermore, as noted in our Broader Implications [R424–R436], our product-form confidence intervals naturally extend to hierarchical or multi-layer reward structures. By decomposing the variance of each sub-component and applying Freedman or Bernstein-type bounds, one can tackle even more complex reward mechanisms. This direction may be especially relevant for recommendation systems or multi-stage decision-making.

For instance, consider a reward model of the form

$$(Y_1, \ldots, Y_m) \sim \operatorname{Multi} (1; p_1, \ldots, p_m), \qquad R = \sum_{j = 1}^m X_j Y_j,$$

where the reward is determined by sampling one of the $X_j$’s with probability $p_j$. This model captures structured reward uncertainty arising from latent selection or allocation mechanisms. In such settings, the reward inherits a mixture structure that can be decomposed, and concentration bounds can be constructed component-wise. Specifically, Freedman's inequality or Bernstein-type bounds for martingales can be adapted to leverage variance information

$$P(S_n - n r > t) \leq P (S_n - nr \geq t, V_n \leq v) + P (V_n > v),$$

where $S_n$ is the cumulative reward and $V_n$ is its empirical variance. The first term allows for tighter bounds via Bernstein-type inequalities when variance is controlled, while the second term can be analyzed similarly to our ZI setting, noting that

$$V =\sum_{j = 1}^m p_j E [X_j]^2 - \bigg( \sum_{j = 1}^m p_j E [X_j] \bigg)^2.$$

This decomposition lends itself naturally to algorithm design, in which estimates and confidence bounds are tracked separately for each layer of the reward model. We believe such hierarchical formulations represent a promising direction for future research beyond ZI, especially in domains like recommendation systems, multi-stage decision-making, or online pricing, where reward generation often involves latent stochastic mechanisms.

References:

[1] Lattimore, T., & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.

[2] Ren, H., & Zhang, C. H. (2024). On Lai’s Upper Confidence Bound in Multi-Armed Bandits. arXiv preprint arXiv:2410.02279.

Thank you for your detailed review. We greatly value your time and suggestions, and we hope the following clarifications and enhancements address your concerns. We respectfully ask you to consider revising your evaluation score if our replies resolve your reservations.

Theoretical Claims:

Our principal contribution lies not only in matching known regret bounds (a necessary sanity check) but in showing how and why leveraging the ZI structure yields performance gains. As discussed in Section 2 ([R110–R149]) and supported by Lemma D.1 [1278] and Figure 10 [1347], ignoring ZI can inflate variance estimates and produce looser concentration bounds. In contrast, identifying and estimating the nonzero reward part more accurately (rather than lumping all observations into a single variance term) avoids under-exploration. This insight is partly recognized in various works (e.g., [1], [2]) but had not been systematically applied to ZI bandits. We will revise the main text to highlight the link between better variance estimation (using ZI) and improved regret.

Experimental Designs & Analyses:

• In Section 5 ([R345–R356]), we indeed used contextual UCB and TS baselines that incorporate covariates via a GLM-based model (described in Appendix C.2). We will clarify this in the main text.

• Our chosen U.S. online auto loan dataset is both large and exhibits notable ZI properties (high reward sparsity, heterogeneous covariates). Additional datasets are desirable but space-limited, and we plan to expand this line of empirical validation in future work.

• We compare our UCB (or TS) method to other UCB (or TS) algorithms in each experimental setting. Occasional underperformance against certain proxy-base UCB methods occurs mainly with exponential rewards when $p_k \sim U[0.1, 0.3].$ However, as shown in Lemma D.1, such proxies can become unreliable under high variance or ZI. Our approach is generally more robust and practical due to directly modeling ZI. We have also added two uploaded anonymous figures (Figure 1 and Figure 2) to illustrate how large variance-to-mean ratios may briefly favor alternative baselines but ultimately highlight the value of stable ZI modeling.

Essential References Not Discussed: We appreciate you pointing us to [3] and [4]. These works consider sparsity in different senses (e.g., many arms having zero mean or zero losses in partial monitoring). Our ZI setting, by contrast, deals with a stochastic zero draw, even for arms with nonzero mean, leading to different concentration/variance behaviors. We will clarify these distinctions in our introduction and related work sections.

Weaknesses:

• Rationale: Our approach targets scenarios where actions yield zero reward with high probability (not merely zero mean). This modeling accurately depicts domains like loan offers, recommender systems, or online ads, where a user typically rejects or ignores an action, creating a structural zero.

• Decomposing Rewards: We define $R = X \times Y$, with $Y = 1(R \neq 0)$ and $X = 1(R \neq 0) \cdot R$. This decomposition (discussed in [L130–L140]) separates the high-probability zero event from the nonzero reward.

• Intuition Behind $X, Y, \mu$, and $\epsilon$: We let $\mu = E[X]$ and $\epsilon = X - \mu$ to center analyses on deviation from the mean. We classify $\epsilon$ into sub-Gaussian, sub-Weibull, or heavy-tailed categories, each with different tail decay properties (following [1], [2]). Handling these classes separately is standard in bandit theory. More extreme no-moment or adversarial settings (e.g., [5]–[8]) fall outside this paper’s scope, though we will mention them as possible extensions.

• Observed Variables: Only $R$ is directly observed during interaction. We define $X$ and $Y$ to analyze the structure of zero vs. nonzero rewards, but the algorithm indeed only sees $R$. We will clarify this point.

• Unreferenced Pointers: We have fixed [1254] (now pointing to Section 5) and [177R] (referring to a corollary comparing constants with classical UCB). These errors will be corrected in the revised manuscript.

References:

[1] Lattimore, T., & Szepesvári, C. (2020). Bandit Algorithms.

[2] Zhou, P., Wei, H., & Zhang, H. (2024). Selective Reviews of Bandit Problems in AI via a Statistical View.

[3] Kwon, J., Perchet, V., & Vernade, C. (2017). Sparse Stochastic Bandits.

[4] Tsuchiya, T., Ito, S., & Honda, J. (2023). Stability-Penalty-Adaptive FTRL: Sparsity, Game-Dependency, and Best-of-Both-Worlds.

[5] Yun, H., & Park, B. U. (2023). Exponential concentration for geometric-median-of-means.

[6] Bubeck, S., Cesa-Bianchi, N., & Lugosi, G. (2013). Bandits with heavy tail.

[7] Zhang, J., & Cutkosky, A. (2022). Parameter-free regret in high probability with heavy tails.

[8] Cheng, D., Zhou, X., & Ji, B. (2024). Taming Heavy-Tailed Losses