Zero-Inflated Bandits
Authors: Haoyu Wei
Runzhe Wan
Lei Shi
Rui Song
Venue: ICML 2025 poster (2025)
Keywords: Bandits
Zero-Inflated
Exploration
Primary area: theory->online_learning_and_bandits

Abstract: Many real-world bandit applications are characterized by sparse rewards, which can significantly hinder learning efficiency. Leveraging problem-specific structures for careful distribution modeling is recognized as essential for improving estimation efficiency in statistics. However, this approach remains under-explored in the context of bandits. To address this gap, we initiate the study of zero-inflated bandits, where the reward is modeled using a classic semi-parametric distribution known as the zero-inflated distribution. We develop algorithms based on the Upper Confidence Bound and Thompson Sampling frameworks for this specific structure. The superior empirical performance of these methods is demonstrated through extensive numerical studies.

Zero-Inflated Bandits
Haoyu Wei"
Runzhe Wan
Lei Shi?
Rui Song? ?
Abstract
USA
Many real-world bandit applications are charac- terized by sparse rewards, which can significantly hinder learning efficiency. Leveraging problem- specific structures for careful distribution model- ing is recognized as essential for improving esti- mation efficiency in statistics. However, this ap- proach remains under-explored in the context of bandits. To address this gap, we initiate the study of zero-infiin pero-inflated bandits, where the reward mod- eled using classic semi-pan panimparamttric distribution known as the zero-inflated distribution. We de- velop algorithms based on the Upper Confidence Bound and Thompson Sampling frameworks for this specific structure. The superior empirical performance of these methods is demonstrated through extensive numerical studies.
bnaee UCG
price huskdt UCS
Froquency
Uppe Contornce
predtd based jount)
Vha procy baaee
Reward (a)
Round
(b)
Figure I. Results from a real personalized pricing dataset detailed in Section 5, (a) Histogram of rewards, with zero represented in orange. (b) Comparison 1 - upper confidence bounds across different methods. We use Monte Carlo to approximate the true quantile (the tightest valid upper confidence bound). All methods are validated as their curves lie above the Monte Carlo baseline. Our proposed method (green) achieves the tightest bound quickly, demonstrating effective utilization of the zero-inflated structure. The other bounds correspond to UCB baselines detailed in Ap- pendix D. Notably, applying existing concentration incqualities dircctly on the reward (ycllow), even when knowing the true size parameter but without utilizing the structure, results in signifi- cantly looser bounds.
1. Introduction
Bandit algorithms have been widely applied in areas such as clinical trials (Durand et al., 2018), finance (Shen et al., 2015), recommendation systems (Zhou et al., 2017), among others. Accurate uncertainty quantification key to ad- dressing the exxllittiee trade-off and typically requires certain reward distribution assumptions. Exist- ing assumptions can be roughly classified into two groups:
Non-parametric: the reward distributions need to satisfy certain characteristics, such as having sub- Gaussian tails (Chowdhury & Gopalan, 2017; Jin et al., 2021; Zhu Tan, 2020) or being bounded (Kveton al., 2019; 2020; Kalvit Zeevi, 2021). In some cases, such an approach can achieve regret rates com- parable to those of parametric methods (Urteaga & Wiggins, 2018; Kalvit & Zeevi, 2021; Jin et al., 2021). However, in general, these weaker assumptions sacri- fice statistical efficiency by ignoring structural informa- tion. Even when the rates are the same, there may still be a significant empirical performance gap between the two approaches when the parametric distribution is correctly specified (see Chapter 9 in Lattimore & Szepesvári, 2020).
the reward distribution is assumed be- long to a parameterized family, such as Gaussian or Bernoulli distributions (Audibert et al., 2010; Krause & Ong, 2011; Agrawal & Goyal, 2012). The strong assumption typically ensures clean algorithmic design and nice theoretical results. However, when misspeci- fied, it may lead to over- or under-cxploration.
Parametric:
'Equal contribution 'Department of Economics, University of California San Diego, La Jolla, USA AAmazon, Seattle, USA. This work does not relate to the positions Amazon. Cor- respondence to: Haoyu Wei <songray@ Eamgray@gmail.com: gmail.com>.
As in many statistics and machine learning areas, using problem-specife structures to focus on more detailed dis- tribution family, if correctly specified, can improve the ef- ficiency of estimation or uncertainty quantification. This leads to lower regrets in bandits. However, as discussed above, compared to the vast statistical literature on univari-
Rui Song
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Zero-Inflated Bandits
Table 1. Summary of the thcoretical guarantees for our algorithms.
BANDIT PROBLEM
ALGORITIMM
REWARD DISTRIBUTION
MINIMAX RATIO
sub-Gaussian (Algorithm 1)
v log T
UCB
sub- (Algorithm 1)
Vlog T
MAB
heavy-tailed (Algorithm B.1)
KK/T + (K/T) शंकक log THe K
TS
sub-Gaussian (Algorithm C.1)
UCB
sub-Gaussian (Algorithm C.2)
log(d q) log(TT(d 9))
GLM
TS
sub-Gaussian (A (Algorithm C.3) (d q) log(d V q) log(T/ A 1))
Our MAB algorithms are designed for tixed horizon 1' but the doubling trick can adapt them into anytime algorithms with comparable guarantees (Section 6.2 in Lattimore & Szepesvári, 2020), preserving all the cooblem-depender regret bounds (Theorems 7 and 9 Besson & Kaufmaan, 2018);
Our prohlem-dependent and prblem--ndependent regrets achieve state-of-the-an performance for both sub-Weihul (Hao
et al., 2019) and heavy-tailed (Bubeck et al., 2013) rewards;
Our groblem-independer regret matches the minimax lower bound up to a logarithmic factor (Theorem 3 in Dani et al., 2008) and aligns with the stateoof-the-an rate (Li et al., 2017).
ate distribution, this direction is underexplored in bandits. This paper initiates the study of this direction by focusing on the sparse reward problem. Specifically, this work is motivated by the observation that rewards tend to be sparse in many real-world applications, meaning they are zero (or a constant) in most instances, called zero-inflated (ZI). For instance, in online advertising, most customers will not click the advertisement and hence the reward is zero with high probability; while for those clicked, the reward will then follow a certain distribution. Similar structures exist in broad upplications, including mobile health (Ling, 2019) and freemium games (Yu et al., 2021). While some standard bandit algorithms can still be applied, they fail to utilize the distribution property and hence can be less efficient. See Figure Ia for a real example.
first finite-sample concentration analysis of the general ZI models in the literature, even outside of bandits. Lastly, we show the value of our approach through both simulated and real experiments.
Related work. Besides the bandit literature with paramet- ric or nonparametric reward distributions discussed above, our work connects to several related research areas. First, there is research on semiparametrie bandits (Krishnamurthy et al., 2018; Kim & Paik, 2019; Ou et al., 2019; Peng et al., 2019; Choi et al., 2023). However, these works focus on addressing the misspecification of the regression function within the context of contextual bandits. This focus is or- thogonal to our objectives. Second, the zero-inflated distri- bution can also be regarded as a special case of hierarchical distributions. In recent years, there is growing interest in leveraging hierarchical models in bandits (Hong et al., 2022: Wan et al., 2021; 2023a). However, all of them study the hierarchical structure among bandit instances (with meta- learning) instead of in the reward distribution as in our setup. Third, to be agnostic to the distribution assump- tion, besides relying on nonparametric distribution fami- lies, one may also consider bootstrap-basek methods (Wan et al., 2023b; Kveton et al., 2019). Nonetheless, on one hand, these methods still rely on certain restrictive distribu- tion assumptions to ensure a regret guarantee; on the other hand, they fail to fully utilize the problem-specift structure, which may lead to compromised efficiency. Fourth, our work is related to research on sparse rewards and heavy- tailer//symmetric bandits. While traditional sparse bandits (K won et al., 2017: Perrault et al., 2020) focus on arms with zero mean rewards, our zero-inflated framework ad- dresses structural sparsity where actions frequently yield zero rewards. This connects to heavy-tailed bandits (Bubeck et al., 2013; Zhang & Cutkosky, 2022) and asymmetric ban-
Contributions. Our contributions are threefold. First, we propose a general bandit algorithm framework for zero- inflated bandit (ZIB). Both Upper Confidence Bound (UCB) and Thompson Sampling (TS)-type algorithms are proposed. Using the cooblem-specifie structure, our algorithm is more efficient than the existing ones via more accurate uncer- tainty quantification. We illustrate this with Figure lb, which shows that our method leads to tighter concentration bounds, and this will translate into lower regrets when used with UCB and TS. Our algorithms are designed for wide range of reward distributions, including the neb-Weibull distribution and even more heavy-tailed distributions (with moments exceeding one). Second, we theoretically de- rive the regret bounds for our UCB and TS algorithms in multi-armed bandits (MAB) under weak reward distribu- tion assumptions, as well as for contextual linear bandits. In many cases, our algorithms achieve regret rates that are either minimax optimal or state-of-the-art A detailed sum- mary is provided in Table 1. To our knowledge, this is the
2

---

Zero-Inflated Bandits
dits (Zhang& & Ong, 2021; Li et al., 2023), as zero-inflated distributions can exhibit heavy-tailed or asymmetric prop- erties. However, our approach is specifically tailored to the zero-inflated structure, allowing the non-zero component to be either heavy-tailed or asymmetric while maintaining computational efficiency.
reward Rg X, Y, X, Yú; thus, we can simply replace X2 with X,. Finally, the conditional distribution of Rd is a mixture of two distributions, one of which is delta distribution on zero and the other is only required to satisfy minimal assumptions; while the assignment Y, is Bernoulli. For simplicity, we will occasionally omit the subscript t when there is no ambiguity.
Finally, while zero-inflated structures have been studied in offline settings (supprvised/uusuperviiddd learning, see Lambert, 1992; Hall, 2000; Cheung, 2002) and there is some literature focusing on model-specific zero-inflated bandits (Liu et al., 2023, which only considers two discrete count rewards: Poisson and negative binomial), to our knowledge, this work is the first formal study on this topic in bandits generally, which poses unique challenges such as finite- sample concentration bounds and regret rate analysis for class of distributions.
To simplify the exposition, we first focus on pulling single arm and may omit the subscript k. We begin with con- sidering scenarios where E, exhibits relatively light tails. Specifically, we consider the bub-Weibull tail property, i.c., there exists > O for which the moment generating func- tion (MGF) of |ee|" is defined within an interval around zero. This sub- Weibull distribution family is very gen- eral (Zhang & Chen, 2021; Zhang & Wei, 2022): for ex- ample, when f = 1 and 0 = 2, it reduces to the sub- exponential or sub-Gaussian family, respectively. Mathemat- ically, we denote E subW (0; C* if the noise E, satisfies E exp(1ea) 0 /C*) S 2, with 0 > O and C >> 0 representing the tail and size parameter (Rinne, 2008; Vladimirova et al., 2020). In the design and analysis of bandit algorithms, it commonly assumed that the parameters 0 and C are known (Wu et al., 2016; Lattimore & Szepesvári, 2020; Wu et al., 2022; Zhou et al., 2025).
2. Zero-Inflated Multi-Armed Bandits
In this section, we use the MAB setting to outline our moti- vation and strategy. We will extend to contextual bandits in Section 3.
Setup. For any positive integer M, we denote the set {L. {I....,M M) } by [M.] We start our discussion with the MAB problem: on each round t E [T', the agent can choose an action A, E AA with the action space A = [K]. and then receive a random reward Rg = TA, Ee, where Th = -[R A, = k| is the mean reward of the k- th arm and Et is the random error. The performance of bandit algorithm is measured by the cumulative regret R(T) = > E| maxaed Ta -... We focus appli- cations where the reward is zero for a significant proportion of time, and propose to characterize the reward distribution by the following Infoltefl (ZI) model:
We first note that the Zl structure retains the sub- Weibull tail behavior of the non-zero component X, 14, as established in Lemma 2.1.
Lemma 2.1. Assuming independent Y, ~ Bernoulli(p) and Xt - 1 subW (0; C), let R, = X, x Y, Then, there exists a constant CR > 0 such that R pp ~ su Cr).
Naive approaches and their limitations. With Lemma 2.1, once the size parameter for RG is known (or estimated), we can construct an upper confidence bound for r up using existing concentration inequalities for sub-Weibull variables {Ra} (Zhang & Chen, 2021: Zhang & Wei, 2022). The corresponding UCB algorithms then follows, which we refer to as naive approaches. While such approaches can theoretically attain minimax regret rates under appropriate parameter specifications, the zero-inflated structure intro- duces unique challenges that lead to two clear limitations.
X₁ MA, + Et, Y, Bernoulli(pA.),
and
R₂ = 0 x (1 Y.) + X, x Yr.
Here, for each arm k we introduce two unknown parame- ters, the non-zero probability p& E [0, 1] and the mean of the non-zero part μ4 such that Fx = fl x Pk. Here E, is a mean-zero random eтror term. For any arm k. we assume P(X,- = 0)- = O. We note this assumption can always be satisfied: given a reward variable RG, one can always define Y, = 1RR,= # 0) and X, = 1(R, * 0) x Ri. Moreover, as such, it is natural to regard Y, as observable as well. In contrast, the value of X, is only observable when Y, + 0 (equivalently, R2 * 0), and in this case it is equal to R. For simplicity of notations and without loss of generality, we assume X, IL Y;: even if X, 1 Y, we can re-define X, Y = y to have the same distribution as X, Y = for y = 0, 1. In this case, X, 11 Yr, and the observable
First, even when the true size parameter is known, with- out leveraging the zero-inflated structure, such an ap- proach leads to a loose concentration bound and hence under-exploration. This can be seen in Figure 1b, our numerical study in terms of regret, and also our regret bound (e.g. Lemma 6.1). We can appreciate the intu- ition from the following fact: var R2)) = Ey (var( (R, (Y)) + vary (E( (R2 (Y:)) = y var(X,) + ,²²p(1 - p). Therefore, if we directly apply concentration bound with RG, the width of the bound will roughly increase linearly with μ.. How- ever, the noise level and the difficulty of estimating either p or j (and hence r) should not change only by shifting the
3

---

Zero-Inflated Bandits
non-zero distribution.
with a variance proxy o²,
Second, in practice, estimating valid size parameter CR for (hence having valid upper confidence bound) is chal- lenging, as the size parameter has complex dependency on 14, p. 6 and C. In real applications, there are a few com- mon methods to choose CR: (1) Use the size parameter of X;-Mi μr; (2) use the variance of R, (estimated on the fly); (3) Use the definition to calculate CR. with μ and p estimated on the fly. The first two approaches are not valid, while the third one is also not reliable due to the sensitiveness induced by the ZI structure. We illustrate the issues with these methods in Lemma E.1 (in Appendix E) using sub- Gaussian distributions, which we summarize here: 1) CR can significantly exceed C, hence approach is not valid; 2) CR can significantly exceed var( hence approach 2 is not valid; 3) Cn is very sensitive to (p, μa, g²), and hence prone to be heavily influenced by their estimation errors specifically, the partial derivatives of Cn with respect to these parameters can be arbitrary large within some regions.
P(u- - X > 2 B log (2/a))
[ X > v (202 B) log (2/a) B)] s a//2.
With Ux (202/BB log (2/a), based on (1), we can derive a valid upper confidence bound for r'k and develop the corresponding UCB algorithm. The algorithm details are outlined in Algorithm 1.
Algorithm 1 UCB for ZI MAB with light tails
Data: Horizon T, tail parameter 0, and size parameter C. Set U 1 and U 1, Ak E [K].
Set the counters C₁ = 0, and set Max = 0 and Pl: = 0.
3 for t = L,.,. KK do
4
Take action A, = 1;
5
Observe RA, set Xt = [(e * 0) x Rs and Y
1(R: + 0).
end
fort K 1, ..... T do
8
Take action A, = arg ke(K UK x U (break tie randomly);
2.1. Proposed product method and upper confidence bound approach
Observe Rr, set Yt = 1 1R: # 0):
To address the shortcomings of the naive approaches, we 10 introduce the product method, which leverages the product structure of the true reward R₂ = X, x Y,- Utilizing the corresponding concentration inequalities, we establish valid 11 upper confidence bounds for ja using {X,) Ji and for p 12 using {Yi formulated as P(( > X + Ux) S a/2 and 13 P(p > Y + ) I ax/2. Here Ux and Uy are known func- tions, and X and Y are the sample averages for {x,] and [- respectively. Consequently.
Update CA = CAi + 1, PA. = PA. + Y Y-- and
cAe
U%. = PA. +
[Tg(2/0))
20A,
if R. 7 0 then
Set X, =
Re;
Update
PA
# #ISEAAi=A, and RA RO, EISLAIZA, RA
and U PA. + 2eD(0)C
log(1/5) + mpA,/2
Fi(0) (og(1/ox2(1/8) where D(0) and E(() are npA,/2
defined in Lemma 2.2.
P(up= > (x) + Uy)) SP(p X > +Pp - - Y>yuu Uy)
(1) 14 end
While the above construction provides valid algorithm, the theoretical analysis presents additional complexities. The concentration bound /(202/B) log (2/a) is random and depends on {Yi)-,,, which significantly complicates regret analysis. Fortunately, Lemma 2.2 demonstrates that we can have a similar concentration bound with rate /'ppk. which is much easier to analyze. also verifies that the observed average of i.i.d. sub- Weibull variables behave with combination of Gaussian and Weibull tail.
which suggests + (X) + Uy) is valid upper confi- dence bound r μ x p.
Now, the key of establishing our method lies in determining sharp concentration bounds for both p and μ. For p. a stan- dard concentration bound for Bernoulli variables can be ap- plied, such as: Uy vI/(2n) x log (2/a). However, es- tablishing sharp bounds for 14 presents significant challenges: (i) X is not directly observable since we only observe X, when Y 1, and (ii) the number of non-zero observations is random, complicating standard concentration analysis. We therefore define the average value of the observed X, as: X
Lemma 2.2. Suppose X,
1 lid subW C) and Y, ltd.
Bernoullipp). Let X # (tE(n).ReE) 200 En_ R₂ be the observed sample mean X
# =1 Exy: X,. Let B Σm= Y, represent the count of X, observations. While B is a random variable, given any fixed B, the sub- Weibull concentration inequality still holds. For example, if X, is nub-Gaussian (i.e., 2)
Ux- = 2eD(()C (v
2 2log(4/0)
2E(() (og(1/0vv) (4/8)
+
pm
pn
then TP(1 X
2 Ux. } S 8 for any 8 0 and n nz
4

---

Zero-Inflated Bandits
4 1og(2/6)/12 The constants ((0) and B(O) are defined in Lemma F.2.
ror. The cumulative regret in this setup is defined as EE| maxxeA, r(x,, a) r(x,, At)]-
More importantly Ux- is not only independent of ja but also enables a tighter product method-based concentration for r = xxxpp compared to standard dab-Weibull concentrations for R, = X; x Y, Our numerical results in Figure lb demonstrate this advantage.
To utilize the ZI structure, we propose to consider the fol- lowing model: R; = 0 x (1 Y2) + Xx x Y with
X2 = g X Ac: + Et: Y ~ Bernoulli (h(x,, Ari 0)),
In addition, some applications exhibit zero-inflated rewards where the non-zero part is heavy-tailed possessing only finite moments of order 1 + c for some E (0, 1]. To handle such cases, we construct an upper bound for the trimmed mean (Bickel, 1965; Bubeck et al., 2013). enabling the corresponding UCB algorithm. Further details are provided in Appendix B.
where EN is mean-zero error term, h is function with codomain [0, 1] and parameterized by 0 E IR,, and g is a function parameterized by / E R We remark the relation- ship that r(x, a) = h(x, a; 0) x g(x, o: (3).
Here, we present general UCB template for our method in Algorithm 2, which extends the MAB version in Section 2.2. Specifically,, based on the functional forms of h(: O) and :(:333) we construct confidence bounds for exploration, denoted as Uan, a) for h and Uan,,(x, a) for g. respec- tively. At each step, we estimate and B. then structure the UCB algorithm by maximizing the UCB score for each action. Similarly, the TS algorithm follows by designing appropriate sampling rules with suitable priors for 0 and B. As a concrete example, Appendix C.2 provides detailed update formulas for both the UCB and TS algorithms when h and g are modeled as generalized linear functions.
2.2. Thompson sampling approach
We also extend our discussion to another widely adopted approach, Thompson Sampling (TS, Thompson, 1933). Sim- ilarly to our approach with the UCB algorithms above, we consider the non-zer part X, and the binary variable Y; separately. For ease of exposition, we consider the sub- Gaussian case for X,, This can be easily extended to sub- Weibull cases by introducing an extra sampling step, known as Phambers-Mallows-SS
(CMS) Generation, to rescale X2 to a sub-Gaussian tail (Weron, 1996; Dubey & Pentland, 2019; Shi et al., 2023).
Algorithm 2 General template of UCB for ZI contextual bandits
Following the standard TS framework, we sample μl and Pk. from their respective posteriors and multiply them. We
Data: Confidence bound exploration terms (an, and .), random selection period т, and other
(: / algorithm-specific parameters.
Unon-zero.
prove this is equal to posterior sampling in Appendix C.I. To achieve minimax optimal TS algorithm for general sub- 15 Set Hall = 0 and Haoo-zero = -0-
Gaussian distributions, we follow Jin et al. (2021); Karbasi 16 Randomly choose action a, A for [r]:
al. (2021) to use a clipped Gaussian distribution, denoted as cl (1,, o2; ()- == (ax((Wrr o²), 0). which curtails overestimation of suboptimal arms and ensures optimality. We adapt this idea to use the clipped Gaussian distribution for sampling the non-zero part X, and a clipped Beta distri- bution for the binary part Yz. Our decision to use a clipped Beta distribution over standard Beta distribution stems from our analysis, which shows it is critical for managing the risk of overestimating suboptimal arms in Rg- = X, x Y, Further details are outlined in Appendix C.
17 for / = r + 1,.... T do
18
Estimate 0, from the binary outcomes, using Hall;
Estimate Be from the non-zero outcomes, using
Hoon-zero:
Take action A, = arg maX [M(x,, a;0,) 0.) + (x a)] x [g((x, a: 3,) + (xx,
20
Observe reward RG, set X, 1RR # 0) Rs and
Y, = =,1,(R #0..
22
Update the dataset as Hall +- Hall U ((x,, Ar, Y.) if Re + O then
23
24
Update the dataset as Hnon f- Hnon zero {(x,, Ar, Re)
3. Zero-Inflated Contextual Bandits
25 end
In this section, we extend our discussion to the Contex- tual Bandits problem. For concreteness, we consider the following setup of contextual bandits, although other se- tups can be similarly formulated and addressed: on each round f, the agent observes context vector and a set of feasible actions Ar, choose an action A, E Ar, and receive a random reward R₁ = r(x;, A²) + Ec, where r is the mean-reward function and e, is the random er-
4. Theory
4.1. Regret bounds for ZI MAB
Although concentration bounds for both components (c.g. van de Geer & Lederer, 2013; Kuchibhotla & Chakrabortty,
5

---

Zero-Inflated Bandits
2022: Zhang & Wei, 2022, for sub-Weibull) and Y (e.g. Ben- tkus, 2004; Mattner & Roos, 2007; Zhang & Chen, 2021, for Bernoulli) have been extensively studied, there present non- trivial challenges to analyze our algorithm with the product of them. These challenges, as discussed above, arise be- cause the reward, and consequently the action selection, is jointly determined by both X and Y. Unlike standard ban- dits where the observability of X depends solely on arm selection, here it also depends on Y's value. Consequently, the number of times X is observed becomes random vari- able. The lack of precise distribution for sub- SehbWeibull X also complicates analytical analysis. Fortunately, our Lem- mas 2.2 and 1.1 help address these challenges to support the regret analysis of our algorithms.
Theorem 4.2. Consider a K K-armed ZIB with sub- Gaussian
rewards. Let the taning parameters satisfy 7 4, p (1/2,1), and ogs, 3 Uk E [0, 11. Then Algorithm C.I has
R(T) S KT
Σ
Pk De + Pi VT/(pK)).
Given that Pk are bounded within (0. 1J. the problem- independent regret is R(T) S VKT + K. Compared to UCB (Theorem 4.1), Algorithm C.I improves by fac- tor of vlogT. The regret is both minimax optimal (Auer et al., 2002) for sub-Gaussian MAB. One can extend Theo- rem 4.2 for sub-Weibull rewards with 0 < 2 with the CMS generation (Dubey & Pentland, 2019). This introduces an additional regret term scaling as (KT) (Dubey & Pent- land, 2019; Shi et al., 2023), which remains state-of-the-art.
Without loss of generality, we assume Th E (0, 1), and T1 [ Pk2 i.e., the first arm is the optimal arm. To demonstrate the prior properties of considering the ZI struc- ture from a theoretical perspective, we present the regret bound for our light-tailed ZI UCB algorithm for MAB.
4.2. Regret bounds for ZI contextual bandits
Theorem 4.1. Consider a K K-armed zero- rero-inflated bandit with sub- Weibull noise so C). We have upper bound for the debeedn-d regret of Algorithm I with 5 = 2/T² R(T)= S
Analyzing ZI contextual bandit algorithms requires con- structing confidence regions for both 33 and 0. Unlike in standard contextual linear bandit literature, the ZI structure means that updates to only occur when non-zero outcomes are observed. Fortunately, the concentration analysis we established for MAB can be similarly applied here. To illustrate the theoretical advantage of our ZI contextual ban- dit algorithms, we analyze an instantiation where both the non-zero part X, and the binary part Y, follow generalized linear models (GLMs):
K
Pk log T/A +)
Σne PE Po'log (180/1 T' +p log Σ Ak.
where 4 ri-- rk for 2,...,K. K.
In Theorem 4.1, the notation "S" indicates inequality up to constants independent of bandit-specific parameters. Since py is bounded in (0, 1] and A S 1. the problem- independent regret simplifies to R(T) S log + K. This matches the minimax lower bound up to factor of O( 7) given in Theorem 15.2 of Lattimore & Szepesvári (2020).
X, = g( x At)) + Ex Y, ~ Bernoulli {h(0' s/y (x,, AJ))
and
Here, e, is sub-Gaussian, g()) and hi(-) are strictly increasing link functions, +-x(-) and by are known transformations. The unknown parameter vectors 3 E H and 0 e R govern the models, and the action space A = [K] S N can be large or even infinite. This GLM setting is widely studied in bandit literature (Filippi et al., 2010; Li et al., 2017; Wu et al., 2022; Li et al., 2010; 2012: Lattimore & Szepesvári, 2020).
Similarly, we establish both pobleem-dependent and problem-indepenndnt regret bounds for our heavy-tailed UCB algorithm (Algorithm B. in Appendix C.I), which matches the sharpness upper bounds rates in the current liter- ature (Bubeck al., 2013; Dubey al., 2020; Chatterjee & Sen, 2021) and hence achieves state-of state-of-the-art performance. The detailed regret analysis is provided in Appendix B.
Denote | = =ZTAr Az for any E IR and positive definite matrix A E Rddd For the GLM setting, we design explicit forms for the confidence bound exploration terms Uan. and Unon zemo,t along with the estimation steps in Algorithm 2. Specifically, at round t, the estimates Gr and Og are obtained via ridge regression
We also provide the regret analysis for our TS algorithm, Algorithm C.1 in Appendix C.I, when the non-zero part sub-Gaussian. In contrast to the proofs of UCB algo- rithms, we require the anti-concentration properties of the distributions to control the probability of underestimating the optimal arm (Agrawal & Goyal, 2013; Jin et al., 2021; 2022). Fortunately, we prove that the clipped Gaussian and clipped Beta distributions, as well as their products, exhibit conieconnenttation with optimal decay rates (Lemma F.3 and Lemma F.4.. This finding allows us to establish the problem-dependent regret bound for our TS algorithm.
RR. 1(xx (x.. A.) ATT |
G. = arg min BET
Σ sE
and 0. = arg min
Σ [Y. hhlyhhwxxxxx An) Ao) ب.ب
BEB
6

---

Zero-Inflated Bandits
The corresponding sample covariance matrices are V. = AvIa Ivenix,=1 thx (xs, Ax) A,) and U, = I + Exejt) (x,, A A.)", where Av, Ày are regularization parameters, and I, θ are compact parameter spaces. To balance exploitation and exploration, we select actions that maximize the sum of the estimated mean and variance, which can be interpreted as an upper confidence bound. The confidence bound exploration terms are designed as U (X,, a) = Pxx,lllxx (Xe, (xx,,))l y. and (X,,) - iY; | (x,, a)llu, 1, where PP: are ellipsoidal scaling factor sequences controlling exploration. This leads to our UCB algorithm for ZI GLM (Algorithm C.2 in Appendix C).
(ex.e: ey.e:e.y.r20o the TS algorithm selects actions as A arg max [xxx (x,, a) B.] x (xeeeyyxx a) 0,]. The corre- sponding regret bounds are provided in the following corol- lary.
Corollary 4.4. Suppose the conditions in Theorem 4.3 hold. If Algorithm C.3 is run with the same random selec- tion period T as Algorithm C.2 and the tuning parameters 2x,1,
2Y, ex, specified in (C.3), then the regret is bounded with probability at least 1 - 58 by Ö(dd V g)²
5. Experiment
Simulation with MAB. For MAB problems, we evaluate our algorithms across three reward distributions: Gaussian, Gaussian mixture, and exponential. We set up several UCB baselines using the lub-Weibull concentration (Bogucki, 2015; Hao et al., 2019), with difference in the size parameter specification: size parameter of the non-zero component, estimated variances, on-the-fly -fl estimated size parameters, and the true size parameters (strong baseline). Additionally, we include the MOTS algorithm from Jin et al. (2021) as a TS baseline. The details of these baselines and our setting are presented in Appendix D.I.
To derive the regret bounds for our UCB algorithm, we impose regularity conditions on the link functions, param- eter spaces, and underlying distributions. Informally, we assume that the link functions have bounded derivatives, the parameter spaces are compact, the variance matrices for both the non-zero and binary components are positive definite with bounded minimal eigenvalues, and the noise is aub-Gaussian. These assumptions are standard and mild in the literature on generalized linear contextual bandits (e.g.. Li et al., 2010; Deshpande et al., 2018; Wu et al., 2022). The formal assumptions are detailed in Assumptions C.I and C.2 in Appendix C.2. Utilizing results on self-normalized martingales (Abbasi- Yadkori et al., 2011), we derive the following regret bounds for Algorithm C.2.
For the reward distributions, we consider: (i) Gaussian re- wards with unit standard deviation and means pai (ii) Mixed
Gaussian rewards drawn from (1 (1-px)** xN ((1-p))) o²) +
Theorem 4.3. Fix any > O. Suppose Algorithm C.2 is run with a suitable random selection period T and tuning parameters {px.t, py,, as specified in Assumption C.3 in Appendix C.2. Under the regularity conditions in Assump- tions C.1 and C.2, the regret is bounded with probability at least 1 - 5b as
Pk X W 2pp o²) ensuring overall mean μ4; and (iii) Ex- ponential rewards with mean μıg. All mean parameters Us are independently drawn from (O, 100). Throughout our experimental evaluation, all plotted línes represent mean cumulative regret over multiple independent replications. Error bars around the curves indicate #1/10 standard devi- ation, chosen to ensure visual clarity while reflecting vari- ability. In some cases, error bars may appear negligible or invisible due to very low variability across replications.
R(T) S + + v dT log(1 + + (lgg dlog(( + d d-1
+ (Tooog(1 + + (og(1/))) + g + TT)
for any NU, dv > 0.
We run simulations with different distributions of p max Pk with 8 = 4/T². Here, we only present the result with p U [0.300, 0.35) in Figure 2. Besides, the 1 8 upper confidence bounds for different UCB algorithms are shown in Figure 1 (b). Findings from other settings (includ- ing high and very low values of p. and bounded rewards) are similar and detailed in Appendix D. Our algorithms demonstrated sub-linear regrets across various distributions. In contrast, except for the strong baseline, all other methods exhibited either linear or significantly higher regrets in some cases, due to the challenge to correctly quantifying uncer- tainty in ZIB. Consistent with our observations in Figure lb, our UCB algorithm even exhibits a much lower regret than the strong baseline in both Gaussian and Gaussian- mixture cases. This proves our motivation that ignoring the Zl structure leads to looser concentration bounds and hence
A notable observation is that the regularity conditions, ran- dom selection period, tuning parameter choices, and regret bound in Theorem 4.3 are independent of the number of arms K. This regret rate Ö((d VT) matches the mini- max lower bound up a logarithmic factor for contextual bandit problems with both finite and countably infinite ac- tion spaces (Theorem 3 in Dani et al., 2008).
While Theorem 4.3 focuses on the UCB approach, the TS variant can achieve the same regret rate. Specifically, the TS algorithm samples parameters as
3. (2.
and
0, NO U,
using the same estimators B. o, V., U, as in the UCB algorithm. With appropriately chosen confidence radii
7

---

Zero-Inflated Bandits
Gaussian
Mixed Gaussian
Exponential
Method
product UCB (ours)
culumalive regret
3000
culumative regrot
3000
culumative regret
6000
product TS (ours)
non-zero pari based UCB
2000
2000
4000
varlance based
estimated proxy besed UCB
1000
1000
2000
true procy based UCB
MOTS
0
20000
40000
60000
5 20000 40000 60000
0
20000
40000 80000
Round
Figure2 2. Zero-inflated MAB with K- 10 and T 75000 with N 50 replications for p (00030, 0.35].
higher regret. Similarly, unlike the baseline TS algorithm (Jin et al., 2021), our TS algorithm outperforms other base- line algorithms. We present results for TS algorithms only in Gaussian and Gaussian-mixture cases. For exponential distributions, the required CMS transformation to rescale the distribution to sub-Gaussian tails discussed in Section 2.2 2.2-complicates fair comparisons.
Real Data. We apply our ZI contextual bandit algorithms to a real dataset of loan records from a U.S. online auto loan company, widely studied public dataset (Columbia Business School, Columbia University, 2024; Phillips et al., 2015; Ban & Keskin, 2021; Bastani et al., 2022). We mainly follow the setup in Chen et al. (2023). At each round t, an applicant arrives with certain covariates (the context) x,. The company then proposes a loan interest rate, which can be transformed into the nominal profit A, for the company (the raw action). This raw action, along with x,, determines the actual profit X, and affects the applicant's decision to accept Y; E {0, 13. The resulting reward for the company is hence R2 = X, x Y, We categorize the raw action A, E R into discrete levels: A, E Adiscrete = ("low", "medium", "high", "very high", "luxury"). each representing a distinct price level. To simulate counter- factual outcomes, we begin by fitting the entire dataset using
Simulation with contextual bandits. We adapt the settings in Bastani et al. (2021); Wu et al. (2022) to ZIB, We design K 100 arms and generate a vector Px E Hd with d = 10 for each arm k [K]. At each round /. the context for arm l is sampled as Xx.t ~ NNa (Vk, 2k La). The non-zero part of the reward, X,, is generated using linear model: 3 XA + εx, with é, representing white noise. For the bi- nary part, we model the probability using a generalized lin- ear function with the link function h(" sin(x Both B and I are d-dimensional, with & having non-zero ele- ments, where E [d]. The sparsity level signifies that the non-zero elements in O influence the occurrence of non-zero rewards. Unlike the MAB problem, the contextual bandits problem introduces an additional layer of complexity for fair comparison due to model specification. We evaluate Algorithm C.2 against two baseline UCB methods: The first one is a naive method, called misspecified UCB, that over- looks the ZI structure, treating it as a linear bandit and thus misspecifying the model. The second, termed integrated UCB, aligns with the UCB baselines in MAB: it correctly specifies the model, but directly quantifies the uncertainty of (BT,, T from the model B3 ( )in(x.)) + ct. by utilizing generalized contextual linear bandit algorithms (Li et al., 2017). Similarly, we assess our TS algorithm, Algo- rithm C.3, against the misspecified TS, which disregards the ZI structure, and integrated TS, which mirrors the integrated UCB. Various sparsity levels and link functions h(.)) are considered. Results for s = 7 using the Probit function are shown in Figure 3, with additional simulation details pro- vided in Appendix D.2. Again, TS algorithms are excluded for exponential noise to ensure fair comparison. As shown in Figure 3, our UCB and TS algorithms consistently achieve lower sub-linear regrets across all tested distributions. In contrast, other methods, except for integrated TS, exhibit linear regrets. While integrated TS also achieve sub-linear regret, our product TS demonstrates superior performance.
X, (Ar, 1) and Y, ~ Bernoulli (h((A,,,,)) 1, (x())
where h(-) is the logistic function and the transformation function b(-) applied the context is detailed in Appendix C.2.
After deriving initial estimators 3 and 0 we then compare our method with two baseline approaches discussed in sim- ulations for contextual bandits at each round I, an action A is selected from Alssrette using our algorithm. The profit A, is then sampled from its truncated distribution based on A.. Subsequently, the real profit X, and the binary decision
Y based on the offered A,, and the corresponding reward
R2 = Xx x Y, are calculated. With the estimated param- eters, we determine the optimal actions for each round to compute the regret. Detailed procedures and tuning parame- ters are in Appendix C.2. The average cumulative regrets over 5000 rounds are shown in Figure 4. Our UCB and TS algorithms demonstrate significantly lower regret compared to the integrated UCB and TS algorithms, highlighting the importance of leveraging the ZI structure in real-world con- textual bandit problems. Furthermore, it is worth noting that while the misspecified UCB and TS algorithms may appear to perform well on this dataset, we should approach their performance with caution: As shown in Figure 3, these algorithms sometimes result in linear regrets. In contrast,
8

---

open Zero-Inflatel Bandits
Gaussian
Exponential
culumesivv regret
2000
culurmitive regret
1900
culumeltive regret
1:000
Method
product UCB (ours)
1500
1000
product TS (ours)
misspeellied UCB integrated UCB misspecifled TS integrated TS
830
500
400
8000
10000
15000
80:000
5000
100000
16000
20000
6000
10000
15000
20200
Round
Figure Zero-inflated contextual bandits with T 20000 and 8 = under = 25 replications.
lower bound holds:
culurnatie regret
400
Method product UCB (oun) tours) rissperftedd LG3
R(T)
K
V (1k - -Phs 'ri)?
-
200
lim inf +-0400 log'T T
202
sspeo//led
km
imtograted iniegrated
1 Phe
100
Pk log
+ (1 -Pp) log
Pk A P4
Pa Ph
1000
2003
5000
Round
Specifically, a necessary condition for an algo- rithm to achieve asymptotic order-optimality for sub- Gaussian ZI MABs is that its regret satisfies lim inf R(T)/logT IK -
Figure 4. Results with the real dataset.
UCB and TS algorithms consistently outperform the competition, achieving the lowest overall regret.
We call an algorithm as asymptotic order-optimal, also known as finite-time instance near-optimality (Lai & Rob- bins, 1985; Lattimore, 2015; Ménard & Garivier, 2017; Lattimore & Szepesvári, 2020), if its regret satisfies lim in RTT) /log)/lo/) T and achieves the lower bound in Lemma 6.1, up to universal constants independent of both the horizon T and problem-specific parameters r (and thus AR, Pk). While we do not explicitly prove that our UCB and TS algorithms for MABs achieve asymptotic order-optimality, they satisfy the necessary condition by accounting for the ZI structure parameter Pks However, de- signing an algorithm that attains this optimality may require additional refinements. For example, in (1), we allocate equal probability a/2 for the two concentration bounds, P(u > X + Ux) S a/2 and P(p > Y + Uv) S a/2. To attain asymptotic order-optimality. these probability al- locations should potentially be adapted based on the zero- inflation parameters {px fk= We leave this problem for future research.
6. Discussion
In this paper, we introduce a new bandit model and the corresponding algorithmic framework tailored to the com- mon ZI distribution structure. The primary advantage lies in lower regrets from more accurate uncertainty quantification by utilizing the ZI structure. We establish theoretical regret bounds for UCB and TS algorithms in MABs under various reward distributions, as well as for contextual linear bandits.
Time and Space Complexity. Computational efficiency is crucial for practical applications. An important advantage of our approach is that our ZI-based methods retain the same big-O time and space complexity standard baselines for both MAB and GLM settings. The only difference is a small constant overhead from maintaining two estimators: one for the zero indicator Y2 and one for the nonzero magnitude X instead of single reward estimator. Thus, our methods pre- serve the same computational order as existing approaches without adding extra computational cost.
Broader Implications. The ZI structure studied in this pa- per can be viewed as a special case of a broader class of problems where the reward distribution follows a hierarchi- cal structure. This framework is particularly useful when the reward distribution is multimodal or when the reward generation mechanism follows hicrarchical process. For instance, in product recommendations, customer's 's initial reaction (e.g.. "highly interested"' "somewhat interested", "not interested") could determine the subsequent reward dis- tribution. Exploring these broader applications remains an interesting direction for future research.
Asymptotic Order-Optimalit. A natural theoretical ques- tion is whether our algorithms achieve asymptotic order- optimality. The following lemma establishes a problem- dependent lower bound for ZIB with a Gaussian non-zero component.
Lemma 6.1. Consider a K -aarmed zero-inflated bandit with the non-zero components belong to Gaussian distributions with variance o?. For any consistent algorithm (see Defini- tion 16.1 Lottimore Szepesvári, 2020), the following

---

Zero-Inflated Bandits
Impact Statement
Besson, L. and Kaufmann, E. What doubling tricks can and can't do for multi-armed bandits. arXiv preprint arXiv: (00iv:8803.00000 1803.06971, 2018.
This paper presents an improved algorithm framework for multi-armed bandits and contextual bandits, both are ma- ture area with many applications. We are not aware any particular negative social impacts of this work.
Bickel, On some robust estimates of location. The Annals of Mathematical Statistics, pp. 847-858, 1965.
Bogucki, R. Suprema of canonical weibull processes. Statis-
References
tics & Probability Letters, 107:253-266 020553--6,222 2015.
Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Boucheron, S., Lugosi, G., and Massart, P. Concentration inequalities: A nonasymptotic theory of independence. univ. press, 2013.
Abramowitz, M., Stegun, I. A., and Romer, R. Handbook of mathematical functions with formulas, graphs, and mathematical tables, 1988.
Bubeck, S., Gesa-Bianchi, N., and Lugosi, G. Bandits with heavy tail. IEEE Transactions Information Theory, 59 (11):7711-7717, 2013.
Adamczak, R., Litvak, A. E., Pajor, A., and Tomezak- Jaegermann, N. Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling. Constructive Approximation,, 34:61- 88, 2011.
Chatterjee, S. and Sen, Regret minimization in isotonic, heavy-tailed contextual bandits via adaptive confidence bands. arXiv preprint arXiv:21 10. 10245, 2021.
Chen, X., Wang, Y., and Zhou, Dynamic assortment optimization with changing contextual information. The Journal of Machine Learning Research, 21(1):8918 8961,, 2020.
Agrawal, S. and Goyal, N. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pp. JMLR Workshop and Confer- ence Proceedings, 2012.
JMLR
Chen, X., Qi, Z., and Wan, R. Steel: Singularity reinforcement learning. arXiv e-prints, pp. arXiv-2301, 2023.
Agrawal, S. and Goyal, N. Thompson sampling for contex- tual bandits with linear payoffs. In International Confer- ence on Machine Learning, pp. 127-135. PMLR, 2013.
Cheung, Y. B. Zero-inflated models for regression analy- sis of count data: study of growth and development. Statistics medicine, 11600):461-1466) 2002.
Ahle, D. Asymptotic tail bound and applications. 2017.
Audibert, J.-Y., Bubeck, S., and Munos, R. Best arm iden- tification in multi-armed bandits. In COLT, pp. 41-53, 2010.
Choi, Y.G.,, Kim, G.-S, Paik, S., and Paik, M. C. Semi- parametric contextual bandits with graph-laplacian regu- larization. Information Sciences, 645: 19367, 2023.
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, E. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48-77) 2002.
Chowdhury, S. R. and Gopalan, A. On kemelized multi- armed bandits. In International Conference Machine Learning, pp.
PMLR, 2017.
Ban, G.-Y. and Keskin, N. B. Personalized dynamic pricing with machine learning: High- fiigh-dimensionll features and hetcrogeneous clasticity. Management Science, 67(9): 5549-5568. 106555568888 2021.
Columbia Business School, Columbia University. Center for pricing and revenue management, 2024. available https://busineess wtw.:/eess...umbaaccccccccmmmm upon request.
Dai, C., Lin, B., Xing, X., and Liu, S. False discovery rate control via data splitting. Journal of the American Statistical Association, 11 188644))2503-2520, 2023.
Bastani, H., Bayati, M., and Khosravi, K. Mostly exploration-free algorithms for contextual bandits. Man- agement Science, 63) 1329-1399, 2021.
Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. COLT, volume 2, pp. 3, 2008
Bastani, H., Simchi-Levi, D., and Zhu. R. Meta dynamic pricing: Transfer learning across experiments. Manage- ment Science, 68(3):1865-188) 2022.
Deshpande, Y., Mackey, L., Syrgkanis, V., and Taddy, M. Accurate inference for adaptive linear models. In Interna- tional Conference on Machine Learning, pp. 1194-1203 PMLR, 2018
Bentkus, V. On hoeffding's inequalities. Annals of proba- bility: An official journal of the Institute of Mathematical Statistics, 3250)166 2004.
10

---

Zero-Inflated Bandits
Dubey, A. and Pentland, A. S. Thompson sampling on symmetric alpha-stable bandits. In Proceedings of the Eigght International Joint Conference on Artifi- cial Intelligence, ICCAI-19, pp. 5715-5721. International Joint Conferences on Artificial Intelligence Organization, 7 2019.
Kim, G.-S. and Paik, M. C. Contextual multi-armed bandit algorithm for semiparametric reward model. In Interna- tional Conference on Machine Learning, pp. 3389-3397. PMLR, 2019.
Krause, A. and Ong, C. Contextual gaussian process bandit optimization. Advances in neural information processing systems, 24, 2011.
Dubey, A. et al. Cooperative multi-agent bandits with heavy tails. In International conference on machine learning, pp. 2730-2739 PMLR, 2020.
Krishnamurthy, A., Wu, Z. S., and Syrgkanis, V. Semipara- metric contextual bandits. In International Conference on Machine Learning, pp. 2776-2785. PMLR, 2018.
Durand, A., Achilleos, C., lacovides, D., Strati, K., Mitsis, G. D., and Pineau, J. Contextual bandits for adapting treatment in a mouse model of de novo carcinogenesis. In Machine learning for healthcare conference, pp. 67-82. PMLR, 2018.
Kuchibhotla, A. K. and Chakrabortty, A. Moving beyond lub-gaussiianty in high- high-dimensional statistics: Applica- tions in covariance estimation and linear regression. In- formation and Inference: A Journal of the IMA, 11(4): 1389-1456, 2022.
Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. Para- metric bandits: The generalized linear case. Advances in neural information processing systems, 23, 2010.
K Kveton, B., Szepesvari, C., Vaswani, S., Wen, Z., Latti- more, T., and Ghavamzadeh, M. Garbage in, reward out: Bootstrapping exploration in multi-armed bandits. In International Conference on Machine Learning, pp. 3601-3610. PMLR, 2019.
Hall, D. B. Zero-inflated poisson and binomial regression with random effects: case study, Biometrics, 56(4): 1039- 2000.
Kveton, B., Szepesvári, C., Ghavamzadeh, M., and Boutilier, C. Perturbed herturbed-history exploration in stochastic linear ban- dits. Uncertainty in Artificial Intelligence, pp. 530-540. PMLR, 2020.
Hao, B., Abbasi Yadkori, Y., Wen, Z., and Cheng, G. Boot- strapping upper confidence bound. Advances in neural information processing systems, 32, 2019.
Henzi, A. and Dümbgen, L. Some new inequalities for beta distributions. Statistics & Probability Letters, 195: 109783, 2023.
Kwon, J., Perchet, V., and Vernade, C. Sparse stochastic bandits. In Conference on Learning Theory, pp. 1269- 1270. PMLR, 2017.
Hong. J., Kveton, B., Zaheer, M., and Ghavamzadeh, M. Hi- erarchical bayesian bandits. In International Conference on Artificial Intelligence and Statistics, pp. 7724-7741. PMLR. 2022.
Lai, T. L. and Robbins, H. Asympiotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):
4-22, 1985.
Lambert, D. Zero-inflated poisson regression, with an appli- cation to defects in manufacturing. Technometrics, 34(1): 1-14, 1992.
Jin, T., Xu, P., Shi, J., Xiao, X., and Gu, Q. Mots: Minimax optimal thompson sampling. In International Conference on Machine Learning, pp. 5074-5083. PMLR, 2021.
Lattimore, T. Optimally confident ucb: Improved regret for finite-armed bandits. arXiv preprint 1501::1507007880 2015.
Jin, T., Xu, P., Xiao, X., and Anandkumar, A. Finite-time regret of thompson sampling algorithms for exponential family multi-armed bandits. Advances in Neural Infor- mation Processing Systems, 35:38475-38487, 2022.
Lattimore, Т. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Kalvit, A. and Zeevi, A. A closer look at the worst-case behavior of multi-armed bandit algorithms. Advances in Neural Information Processing Systems, 34:8807-8819, 2021.
Li, L., Chu, W., Langford, J., and Schapire, R. E. A certextual-bandeee approach to personalized news article recommendation. In Proceedings of the 19th interna- tional conference on World wide web, pp. 661-670, 2010.
Kang, M. and Kim, G.-S. Heavy-tailed linear bandit with huber regression. In Uncertainty in Artificial Intelligence, pp. 1027-1036. PMLR, 2023.
Li, L., Chu, W., Langford, J., Moon, T., and Wang, X. An unbiased offline evaluation of contextual bandit algo- rithms with generalized linear models. In Proceedings of the Workshop on On-line Trading of Exploration and Ex- ploitation 2, pp. 19-36. JMLR Workshop and Conference Proceedings, 2012.
Karbasi, A., Mirrokni, V., and Shadravan, M. Parallelizing thompson sampling. Advances in Neural Information Processing Systems, 34:10535-10544 2021.

---

Zero-Inflated Bandits
Li, L.,, Lu, Y., and Zhou, D. Provably optimal algorithms for generalized linear contextual bandits. In Interna- tional Conference on Machine Learning, pp. 2071-2080. PMLR. 2017.
Shao, H., Yu, X., King, I., and Lyu, M. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoff'. Advances in Neural Information Processing Systems, 31, 2018.
Li, S., Zhang, L., Yu, Y., and Li, X. Optimal arms identifi- cation with knapsacks. In International Conference on Machine Learning, pp. 20529-20555. PMLR, 2023.
Shen, W. Wang, J., Jiang, Y.G.,, and Zha, H. Portfolio choices with orthogonal bandit learning. In twenty-fourth international joint conference on artificial intelligence, 2015.
Ling, W. Quantile regression for zero-inflated outcomes. PhD thesis, Columbia University, 2019.
Shi, Z.,, Kuruoglu, E. E., and Wei, X. Thompson sampling on asymmetric a-stable bandits. In International Confer- ence on Agents and Artificial Intelligence, 2023.
Liu, X., Deliu, N., Chakraborty, T., Bell, L., and Chakraborty, B. Thompson sampling for zero-inflated count outcomes with an application to the drink less mo- bile health study. arXiv preprint ar arXiv:2311.4339, 2023.
Skorski, M. Bernstein-type bounds for beta distribution. Modern Stochastics: Theory and Applications, 10(2):211- 228, 2023.
Mattner, L. and Roos, B. A shorter proof of kanter's 's bessel function concentration bound. Probability Theory and Related Fields, 199:191-205, 2007.
Sun, Q. Zhou, W.-X., and Fan, J. Adaptive huber regression. Journal of the American Statistical Association, 115(529): 254-265, 2020.
Medina, A. M. and Yang. S. No-regret algorithms for heavy- tailed linear bandits. In International Conference on Machine Learning, pp. 1642-1650. PMLR, 2016.
Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-22 2944, 1933.
Ménard, P. and Garivier, A. A minimax and asymptotically optimal algorithm for stochastic bandits. In International Conference on Algorithmic Learning Theory, pp. 223- 237. PMLR, 2017.
Urteaga, I. and Wiggins, C. H. Nonparametric gaussian mixture models for the multi-armed contextual bandit. stat, 1050:8, 2018
Ou, M., Li, N., Yang, C., Zhu, S., and Jin, R. Semi- parametric sampling for stochastic bandits with many arms. In Proceedings of the AAAI Conference on Artifi- cial Intelligence, volume 33, pp. 7933-7940. 2019.
Vaart, v. d. and Wellner, J. A. Empirical processes. Weak Convergence and Empirical Processes: With Applications Slatistics, pp. 127-384. Springer, 2023.
van de Geer, S. and Lederer, The bernstein cersstii-ooliczz norm and deviation inequalities. Probability theory and related fields, 157(1-2):225 250, 2013.
Peng, Y., Xie, M., Liu, J. Meng, X., Li, N., Yang, C., Yao, T., and Jin, R. A practical cemimparaettric contextual bandit. In ISCAI, pp. 3246-3252, 2019.
Vladimirova, M., Girard, S., Nguyen, H., and Arbel, J. Sub-weibull distributions: Generalizing sub-gaussian and sub-exponential properties to heavier tailed distributions. Star, 91))e331, 2020.
Perrault, P., Valko, M., and Perchet, V. Covariance-adapting algorithm for semi-bandits with application to sparse out- comes. In Conference on Learning Theory, pp. 3152- 3184. PMLR, 2020.
Wan, R., Ge, L., and Song. R. Metadata multi-task bandits with bayesian hierarchical models. Advances in Neural Information Processing Systems, 34:29655- 29668, 2021.
Phillips, R., Şimşek, A. S., and Van Ryzin, G. The effective- ness of field price discretion: Empirical evidence from auto lending. Management Science, 18)1:1774) 2015.
Wan, R., Ge, L.,, and Song, R. Towards scalable and ro- bust structured bandits: A meta-learning framework. In International Conference on Artificial Intelligence and Statistics, pp. 1144-1173. PMLR, 2023a.
Ren, Z. and Barber, R. F. Derandomised knockoffs: lever- aging e-values for false discovery rate control. Journal of the Royal Statistical Society Series B: Statistical Method- ology, 86(1): (6(1))122220)) 154, 2024.
Wan, R. Wei, H., Kveton, B., and Song, R. Multiplier bootstrap-baid based exploration. In International Conference on Machine Learning, pp. 35444-35499 PMLR, 2023b.
Rinne, H. The Weibull distribution: handbook. CRC press, 2008.
12

---

Zero-Inflated Bandits
Wei, H., Lei, X., Han, Y., and Zhang, H. High-dimensional inference and fdr control for simulated markov random fields. arXiv preprint arXivv2202.05000 2024.
Zhu, Q. and Tan, V. Thompson sampling algorithms for mean-variance bandits. In International Conference Machine Learning, pp. 11599-11608, PMLR, 2020.
Weron, R. On the sewebberr-mmallosssutceee method for simulating skewed stable random variables. Statisties & probability letlers, 28(2):165-171, 1996.
Wu, S., Wang, C.-H., Li, Y., and Cheng, G. Residual boot- strap exploration for stochastic linear bandit. In Uncer- tainty Artificial Intelligence, pp. 2117-2127. PMLR, 2022.
Wu, Y., Shariff, R., Lattimore, T., and Szepesvári, C. Conser- vative bandits. In International Conference on Machine Learning, pp. 1254-1262 PMLR, 2016.
Yu, M. et al. Online testing and semiparametric estimation of complex treatment effects. 2021.
Zhang, H. and Chen, S. X. Concentration inequalities for statistical inference. Communications in Mathematical Research, 37(1):1-85, 2021.
Zhang, H. and Wei, H. Sharper sub-weibul concentrations. Mathematics, 10(13):2252, 2022.
Zhang, H., Wei, H., and Cheng, G. Tight non-asymptotic inference via sub-gaussian intrinsic moment norm. arXiv preprint arXiv:2303.07287 2023.
Zhang, J. and Cutkosky, A. Parameter-free regret in high probability with heavy tails. Advances in Neural Infor- mation Processing Systems, 35:8000-8012, 2022.
Zhang, M. and Ong, C. S. Quantile bandits for best arms identification. In International conference on machine learning, pp. 22513-12523, PMLR, 2021.
Zhang, T. Mathematical analysis of machine learning algo- rithms. Cambridge University Press, 2023.
Zhao, P., Zhang, L., Jiang, Y., and Zhou, Z.-H. simple ap-
proach for non-stationary linear bandits. In International Conference Artificial Intelligence and Statistics, pp- 746-755. PMLR, 2020.
Zhong, Z.., Chueng, W. C., and Tan, V. Y. Thompson sam- pling algorithms for cascading bandits. The Journal of Machine Learning Research, 22(1):9915-9988, 2021.
Zhou, P., Wei, H., and Zhang, H. Selective reviews of bandit problems in ai via a statistical view. Mathematics, 13(4), 2025.
Zhou, Q., Zhang, X., Xu, J., and Liang, B. scale bandit approaches for recommender systems. In Interna- tional Conference on Neural Information Processing, pp. 811-821. Springer, 2017.
13

---

Zero-Inflated Bandits
A. Appendix Overview and Roadmap
We provide roadmap to help readers navigate the supplementary material.
SECTION
SUBSECTION
CONTENT DESCRIPTION
Heavy-tailed ZI MAB setup, concentration inequalities, UCB algorithm, and regret analysis
Appendix B
C.1
Thompson Sampling algorithm for ZI MAB with sub-Gaussian rewards
Appendix C
C.2.1
GLM UCB algorithm setup, tuning parameters, and regularity conditions
C.2.2
GLM Thompson Sampling algorithm and tuning parameters
C.2.3
Extension to GLM ZI bandits with heavy-tailed noise
MAB simulation details: baselines, parameters, computational resources, and extended results (small/large p. bounded rewards). Includes confidence bounds of different concentration inequalities for Figure lb
D.1
Appendix D
GLM bandit simulation details: algorithms, parameters, computational setup, and ex- tended results (different sparsity levels, other baselines)
D.2
D.3
US loan dataset setup and modeling as ZI GLM contextual bandits
Appendix E
Supporting lemmas for naive approaches discussion (Section 2)
Appendix F
Proofs of all lemmas
Appendix G
Regret bound proofs for UCB MAB algorithms
Appendix H
Regret bound proofs for Thompson Sampling MAB algorithms
Appendix I
Regret bound proofs for ZI GLM contextual bandit algorithms
Table 2. Appendix overview. Click on section names to navigate directly to the content.
B. Heavy-tailed MAB
In many applications with zero-inflated rewards, the non-zero part can be heavy-tailed (with only finite moments of order 1 ++ for some E (0, 1]). To accommodate these scenarios, we adopt the trimmed mean (Bubeck et al., 2013) as solution. The truncation follows a Hoeffding-type -tppe upper bound under the condition |X|]**e < M. Specifically, for fully observable data (X.) we can construct a upper confidence bound for f with the trimmed mean
X
trimmed
Σ t=1
n
X11 (Xel S (log (6) V144).
The resulting upper confidence bound (Bickel, 1965; Bubeck et al., 2013; Dubey et al., 2020) is given by
trimmed
(nog 4M - (n llog (6 1)-1)) 1/(1+e)
X
In ZIB, we similarly define
X" = # : 1}
Σ :3:=1
X11
(xil S (log (2/0))((())) 1((40))
with j(t) 11(Y= ESt
Then we can construct valid upper bound for as Ux.. = X" M2/(L++) 5(n)/n) e/(1c)) ((m)/m)/((+)) where S(n) is the round index when the arm that we focus on has been pulled for times. The corresponding UCB algorithm is then constructed using Ux-. x Uy with Uy as previously defined. This approach is further detailed in Algorithm B.I.
Similar to Lemma 2.2, Lemma B.1 below confirms that this upper bound maintains a deterministic rate, simplifying the analysis.
14

---

Zero-Inflatel Bandits
Algorithm B.1 UCB for zero-inflated bandits with heavy tails
Data: Horizon T, parameters e and M.
Set U and U vk E [K].
Set the counters Cg 0, set the mean estimator Pk: O and fix: vk [K].
for t 1,..., K do
29
Take action A, 1, set X, = 1RR 0) x R. and Y, 1(R + 0).
30 end
31 for f = K + , do
32
Take action A, = arg maX UK x U% (break randomly);
33
Observe RG, and set Yr = 1R + 0).
Update CA. CA, + 1, PA, PA, + Y Pa, and Uh =AA, v
2
cA
ca.
R2 * 0 then
36
Set X₁ Rr;
37
Update
log
BA.
Σ
RA |Ail S o(PA,.))
# st: A = A, and RA + 0}
CA
ICtAF=A:
where the function c) is defined in Lemma B.1, and Ut TiA, + M1/(1++) (32 (/cggt//(((()))))))) (((tt).
end
Lemma B.1. Suppose Y itd Bernoullip)) and X, satisfy E|X, - -u2tte S M for some (0, 1] with positive M > Then
P p( glp, <) M 4. (n log (og() イল. S
for any 5 > 0 and n 2 4log(2/0)/p², where g(p E) := = गमे + c)2 + 4/3 + 2/.
Similarly, using Lemma B.I, we can establish the groblem-dependee regret bound for our heavy-tailed UCB algorithm in Algorithm B.I.
Theorem B.2. For K K-armed ZIB with noise satisfying max [K] ElEx| 1+c THe oo for some (0, 1]. Algorithm B.l has problem-dependen regret bound as
K
(2pag(pu;)) e)) Lis M log
R(T) 2
(3
+ 4p 2A, +9p "
log
When treating the number arms as finite and assuming that are fixed, comparing our results with those in the heavy- tailed bandit literature (Bubeck et al., 2013; Dubey et al., 2020; Chatterjee & Sen, 2021) and we know that our algorithm achieves state-of-the-art regret rate. Moreover, from Theorem B.2, the problen-independent regret for Algorithm given by
R(T) S Pi K
Σ Pk VT + (MT) (K Ti
(B.1)
KVTT (K (K T)
where the last "<" is due to Pi.Pa (0,1). 1). This finalizes the minimax ratio in Table 1 for MAB.
C. Additional Algorithms Details
C.1. TS Algorithms for MAB
As outlined in Section 2, we have developed a light-tailed TS algorithm for MAB. The light-tailed TS-type algorithm achieves the minimax optimal rate when applied under the clipped distributions. The comprehensive procedure of the presented in Algorithm C.I.
15

---

Zero-Inflatee Bandits
Algorithm C.1 TS for zero-inflated MAB with light tails
Data: Prior parameters {crR, SR, oo and P.7.
39
Set the counter C₁: = 0, vk E [K];
40 for f = 1...., K do
41
Take action A, = t, set X, = 1(R #0) x Rs and Y = 1(R + 0).
42
end
for K + 1, , do
Sample Pkk Beta( Bu; (p)) and juk clN (VEs 2x
perin (1()
Take action A, arg max Pk iuk:
Observe reward R4, and set Y1- (R + 0).
47
Update aA, = U.A, + 1, and BA, AA, + 1-Yi
Update PA. PA. + PA- and CA. = CA. + 1;
48
CA.
49
Update
(p)(p) = =ŌA, +
7
log"
T (CCA K
|cA,
50
if R. A 0 then
51
Calculate:
AA. = #l1 A Ae and RA #03
RAi
ist:AF=
52
Update
UA. -A
and
47 1 + log ((1 + 1/ V/VCATT))
(4 log
'11 1/ //A, 02T
()) = Br.- +
log*
CA,
PA, C.A PA, K
end
The equivalence of directly sampling Fa and the procedure of sampling y* and pи from their respective posteriors and then multiplying them in Algorithm C.I, which can be mathematically expressed as follows:
Re PP(k) x P((Re Tk)
P(paPa) x P((Be)cA ux
(el.::e)duaa de)ddadp
(C.1)
pepe=re
duydpe.
MAPE-TL
where the last equality results from two assumptions: 1) independent priors for μ4 and Pk. and 2) non-zero rewards depend solely on μi. while zero rewards depend only on Pk-
important aspect of the TS-algorithm our use of clipped distributions for both the sub- Gaussian non-zero part and the precisely Bernuuli distributed part Y. As explained in Section 2.2, the reason for using clipped Gaussian distribution for X is due to its deviation from exact Gaussian distribution. The rationale behind employing a clipped Beta distribution for the exactly Bernoulli distributed Y is as follows: the objective is to establish concentration for the product random variable R = x Y. The product the original Beta distribution and the clipped Gaussian does not adequately control the overestimation probability of sub-optimal Rş in our proofs. This is primarily due to the proof techniques employed. For more details, refer to the proofs of Theorem 4.2 in Appendix H.
16

---

Zero-Inflatel Bandits
C.2. Algorithms for Generalized Linear Contextual Bandits
C.2.1. UCB ALGORITHMM AND REGULARITY CONDITIONS
As concrete example, we consider the widely-used generalized linear contextual bandits with finite action set A [K]. where both functions h and g are structured generalized linear functions here.
This setup is characterized by the known transformation functions (x)+),, (.) and the known link functions g( and h((), such that gXx,, Ac; 3) = g ( (x,, A,) () and f(x,, Ar; 0) = h (xe, Ar) 0). When the Es is sub- Sab-Gaussian, confidence radii for the ridge estimations 0. (or Be) in a compact parameter space can fully determined by ( At) (or x (X,, At)) and the sub-Gaussian variance proxy of Et. Specifically, PY,e is chosen such that (Lemma 17.8 Zhang, 2023)
P YO SO Vuu
sup dE[K]
Σ (x., a)
2 1 6.
Thus, the ellipsoidal ratio PY.: in Algorithm C.2 is constructed accordingly. A similar approach applies to px.t for the non-zero component, though additional randomness from X, = ( (X., A,) (3) must be carefully handled, as discussed in Section 2.1. The proof of Theorem 4.3 provides further details, which we omit here for brevity.
Algorithm C.2 General template of UCB for zero-inflated generalized linear bandits
Data: Link functions (-), (yy()). 9()) and h()). Ellipsoidal ratio sequences {px,i- pY,)). Rridge parameters Au and λy 54 Set Hall = O and Hnon-zero {}. Set U, IT and V, = I
55 Randomly choose action E [K] for t E [r]:
56 for / - 1,...,T' do
57
for a E [K] do
58
Set
UCB:(a) = (x(xx a) (xxxx,/"= =
[ [oyyxx, a) + (r,
59
end
60
Take action A, = arg max (C).
61
Observe reward R,, and set Y; = 11 (R, + 0).
62
Update the dataset Hall +- Hal U [(x, A., Y.) and U, = U, + (x Ad)
63
Solve the equation
0. f 0 Σ
((br Ab) -
1
/ (xx Ao) (A) =0}
A))
if R3 + 0 then Update the dataset Hoon-erro &- Hnon zeno U f(xe, Ac, Re)):
66
Update V, Vo + (x,, v Solve
3. E BEr:
Σ +E
Rs ((Vx(x,, (x Ao) o)
end
Next, we present the regularity conditions and selections of tuning parameters for Theorem 4.3. Let the true parameters be 3 and 0", and Z x (x,,a) a) E 2d and W. = shy (x2, a) E R8 for a E [K]. These assumptions are quite standard in generalized linear contextual bandits (see, for example, Li et al., 2010; Deshpande al., 2018; Wu al., 2022).
Assumption C.1 (Link Functions and Parameters). (i) The parameter space and for | and satisfies
sup || I and suppee ||0||2 < 1;
iii) The link function g(-) and h(-) is twice differentiable. Its first and second order derivatives are upper-bounder by Lg and Mg. and T., and Mr. respectively;
17

---

Zero-Inflated Bandits
(iii) Ki inf 22l..1111111111 1--11-----111 -- ((2 and Rq - hisw ((wTT) 0:
(iv) p. == inf w h(w ( 0) > 0.
Assumption C.2 (Distributions). (i) |Z,al2 S and [ W S 1 for all E [K]:
(ii) The minimal eigenvalues for Bi Ziaal and W, W ii satisfy Amin (Bi ((al)
0 and
Amin (E[Wa,a Wa 2 ow for all a E [K] with some positive Oz and ow-
(iii) The noise E, is sub-Gaussian distributed, satisfying Eist Fi-il = 0 and Efe Ft-1] S e0'o212 for any E R. where Ft = ({ R.)..... (X,,, H) an increasing sequence of sigma field. Assumption C.3 (Tuning Parameters). For any E (0, 4/T),
ii the random selection period T is chosen as
max I( [C
+ C2 logoo////)
2
2
4 (lg())
Cav
C4v (01/log(1//) log( (1/6
2
+
o
P.o
p2
o
(ii) the ellipsoidal ratio sequences are chosen as
Px,: Kig o 1og(1/0) + l/d) and PY. K%
2 + q log((1 + (1
where Ct5 2,,44 are some universal positive constants detailed in Appendix
quick remark here is that all regularity conditions Assumption C.I, C.2, and tuiing parameter selections inAssumptionn C.3 are independent the number of arms K.
C.2.2. THOMPSON SAMPLING FOR GLM
Just like in the standard TS algorithm for linear contextual bandits (Agrawal & Goyal, 2013), we employ Gaussian priors for the sub-Gaussian noise. At each round / [T], sample parameters (B., 0.) from Gaussian posterior distributions centered at estimates 1 0.} with covariance matrices { V gy, U where these estimates and covariance matrices are obtained from the UCB algorithm. The arm A, then selected by maximizing the Thompson Sampling objective function x (x,, a) 3g x by (x,, a) 0, leveraging the fact that both link functions are strictly increasing.
Let A denote the optimal action at round and define W; == xxx (W..47 A2). To ensure an appropriate choice of confidence radius sequences (ey, 1220 (or (ex,))<20. both of which can be variance-dependennt, it suffices to find @y such that (Lemma 2 in Agrawal & Goyal, 2013)
|F TT-22 w;O, > W; + +Ve V log T T/lll,,
(C.2)
for some E (0, 1), where G. is high-probability good event defined as
G {Va E [K] WT (0. -2)= s @Y We.llut
From the proof of Theorem 4.3, we can set @Y Z PY.: to ensure that G. holds with probability at least - ô for t > T. To validate the anti-concentration property in (C.2), we use the inequality
1 2 n
exp (2x2/2) < P(W((,, -10 u/>0 x0) <
1
exp (-x²/2)
Thus, choosing @Y.: Ve llllog1///)) with e x log T ensures that
W:O. > Wio + V log T Wello, |
1
P
4ev 4
18

---

Zero-Inflated Bandits
Algorithm C.3 General template of TS for ZI GLM bandits
Data: Link functions (-x()), Vy (-) (-).g()) and h(.). Confidence radio sequences {ex,e: eYa). Rridge parameters Au and
Av. Set Hall = O and Hnon [.. Set U, A and V, = Id Randomly choose action dr E [K] for E [7]; I. do
69
for t
72
for E [K] do
73
Set
(a) ( a) TB.] (x; 0z
end
75
Take action A, = arg maX (a)
76
Observe reward RG, and set Y; [Re + 0).
77
Update the dataset as Hall + Hall U {(x,, Ar, } and U, = U, + +by (x),
78
Solve the equation
0 E :
θ: Σ
Y. -
(x., (xs Ao) uy (x.: Ax) =0).
sml
Sample 0, from distribution (i oy U,
80
Rg * then
81
Update the dataset as Hnon t- Hnon zero U {xx,, Ar, Rt)):
82
Update V, = V. vix (x,, Ar) AI)
83
Solve
3. E gEr:
Σ
R. (x): xx A.) = 0
+E(1):Y,=1
Sample B, from distribution NB, ex,, V.
84
end
Moreover, for any t E [T].
Dy. x logg log(T) ž Vlog(1/8) + glog(1 + t//)) x PY.
Similarly, we select εx correspondingly, leading to the following choices:
0x,t log)
and
Øy = log())
(C.3)
C.2.3. EXTENSION FOR HEAVY-TAILED NOISE
Similarly, one can also devise the UCB-type algorithm for sub- Gaussiassin Et, as detailed in Algorithm C.2 in Appendix C. In cases where e follows a general sub-Weibull distribution or only has finite moments of order 1 + e with E (0, 1], specific adjustments are necessary, such as applying the median of means (MoM) estimator for linear bandits (Medina & Yang, 2016; Shao et al., 2018) or Huber regression (Sun al., 2020; Kang Kim, 2023).
D. Supplement to Simulation
D.1. Detailed Simulation Setting for Multi-Armed Bandits
Our simulations were performed on Mac mini (2020) with an MI chip and 8GB of RAM. We first detail the UCB baselines and TS baselines as follows:
UCB baselines:
We consider following UCB-type algorithms for comparison, round f, the agent takes action A, = maxxe(K] (t()) with
19

---

Zero-Inflated Bandits
the k-th arm's upper bounds (t) = (t) +
2rd log(2/6) (x())
for sub-Gaussian rewards (t(t) (t((t) az / (
+
cx
OKk log(2/6) for sub-Exponential rewards. Here, the size parameters 72 and o for the true rewards are determined using the (0
following methods:
Using the original size parameters for the non-zero part Xx. assuming they are known, as the size parameter for constructing Ux(t);
Using the estimated variance of the rewards from k-th arm as the size parameter Te and ag for constructing Ux(t);
Using the estimated size parameter for k-th arm follows:
- For sub-Gaussian X₂ with sub-Gaussian variance proxy oi the sub-Gaut Gaussian variance proxy for Rg solved by
2 maxx sER 82
sppnnn + log(1 - pn. + TRe (
7
where Py is taken as the average of observations Yx: For uub-Exponential X2 with the single uub-Exponential parameter λE. the sub-Exponential parameter og for the rewards from the k-th arm is solved by
X max [- + log(1 pu + pae 4
a
Here ßi and Pk are taken the averages of observations X₃ and Yk. respectively.
(Strong baseline) Using the true size parameter for the reward of each arm R& 1K k==
TS baselines:
Here we exclusively consider the Ty-type algorithm suitable for general sub-Gaussian distributions, namely the MOTS algorithm (Jin et al., 2021). For Gaussian and mixed Sixed-Gaussian rewards, can directly apply both Algorithm C.I and the MOTS algorithm. But, when applying with Exponential rewards, we adopt Algorithm from Shi et al. (2023). In doing so, we integrate their step with our algorithm and the MOTS algorithm. This ensures that both our method and the one proposed in Jin et al. (2021) are correctly adapted for use with sub-Gaussian distributions after the GMS generation.
Simulation settings and extended results:
For UCB-type algorithms, we set the confidence level 8 4/7² consistently across all experiments. Prior parameters and tuning parameters for TS-type algorithms follow the recommendations in (Jin et al., 2021; Shi et al., 2023) for the MOTS algorithm and GMS generation. Beyond Figure 2, we provide additional simulations across different parameter ranges: Figure shows results for alternative settings, while Figures 6 and 7 examine extremely small and relatively large zero-inflation probabilities, respectively. We also extend our analysis to bounded rewards in Figure 8.
Our methods consistently outperform existing approaches across most settings. However, occasional underperformance against certain proxy-based UCB methods can occur, particularly with exponential rewards under specific parameter ranges (e.g., Ps- U|0.1, 0.3).. As demonstrated in Lemma E, such proxy methods can become unreliable under high variance or strong zero- iefoliinlaaionn whereas our approach demonstrates greater robustness by directly modeling the cero-inflated structure.
For bounded rewards, our UCB method shows clear advantages in most cases. The only exception occurs when the zero-inflation level is low (i.e., Pk is large), in which case the true Hoeffding-bel -based UCB (with access to the exact bound) performs slightly better. Nonetheless, this case represents a rare (as the exact bound baseline is not available in practice). In all other cases, especially when skewness or sparsity increases, our method shows clear advantages.
All simulations for each parameter setting and distribution were completed within 24 hours.
D.2. Detailed Simulation Setting for Contextual Bandits
In our contextual bandits scenario, we employ two UCB baseline methods for comparison of our method:
20

---

Zero-Inflated Bandits
G Gaussian
Mixed G Gaussian
E Exponential
2500
3000
4000
culumative negret
cullmaatvve regret
culumativve regret.
3000
1500
2000
1000
1000
1000
500
20000 40000 60000 round
20000 40000 60000
20000 40000 60000 round
round
product UCB (ours)
non-stero part based UCB
estimated praxy based UCB
MOTS
method
product TS (ours)
varance
true proxy based UCB
G Gaussian
Mixed G Gasssian
E Exponential
4000
culumative negret
Culumative regret
culumative regret.
4000
2000
3000
2000
1000
1000
1000
20000 40000 60000 round
20000 40000 60000
20000 40000 60000 round
round
method
product UCB (ours)
non-zero part based UCB
estimated praxy basad UCB
MOTS
product TS (ours)
varance based
true proxy based UCB
G Gaussian
Mixed G Gaussian
E Exponential
culumative negret
cilumative regret
3000
Culumative regret
5000
2000
a000
2000
3000
1000
2000
1000
1000
20000 40000 60000 round
20000 40000 60000
20000
40000 60000 round
round
method
product UCB (ours)
non-zero part based UCB
estimated proxy basad UCB
MOTS
product TS (ours)
varance based UCB
true proxy based UCB
G Gaussian
Mixed G Gaussian
E Exponential
1600
culumativve regret
Eillmmttive regret
culumative regret
6000
1200
2000
4000
800
1000
400
20000 40000 60000 round
20000 40000 60000
20000 40000 60000 round
round
method
product UCB (ours)
non-zero part based UCB
estimated praxy based UCB
MOTS
product T5 (ours)
varance based UCB
tree proxy based UCB
Figure Simulation zero-inflated MAB 10, 0.15). U(0.15,00 0.20), U (00200, 0.25). and U00.25, 0.30j, respectively.
10
75000 with
replications.
rows represent
(Naive Method) We ignore the zero-inflated structure. The upper bound for any action A, is defined as:
UCB = vxx (Xe, a) Dnsive + Vpx,ollaxx (Xe, a) lumee
with Uniive and Briive computed by Unaive Aurla + Ei vx(xx, (x)xx(x.. A.) and Braine
U U-1 Σ R&txx (x,, As).
(Integrated Component Method) We correctly account for the zero-inflated structure. The upper bound for any action
21

---

Zero-Inflated Bandits
Gaussian
Mixed Gaussian
Exponential
40000
culumaaivve negret
aulumativv regret
culumative regret
30000
30000
20000
20000
20000
10000
10000
10000
25000 250005000750000000
753000000050010000
25005000070000000
round
round
round
product UCB (ours)
non-stero part based UCB
estimated proxy basad UCB
MOTS
method
product TS (ours)
varance based
true proxy based UCB
Figure Simulation zero-inflated under p E U10.0005, 0.01] with K 10 and 7 10000 with 50 replications.
Oaaske
Mex Shanssiee
40090
40030
102300
100300
50300
00000
00000
12000
round
Figure 7. Simulation for zero cero-inflated MAB under (0.75, 0.95] with K 10 and 7' 25000 with N = 50 replications.
ujo.t, 0.2)
p. U10.55,
30200
30000
Qutmaatie nageer
20000
22000
Culmeetive
10000
8200
20000
25000
Bel::
U10.20 0.5)
Beax: 180.75, 0.1]
Calamalie Haght
30000
32000
FJAmetive
10000
10000-
5200
10000 18300
20500
25000
5000
method plodud UCD mung
nonioess partbaeed antiroted piacy Saned MOTS
Hineliing
Figure 8. Simulation for zero-inflated MAB under the scaled Beta distribution of the form Xa 2/1 Beta(pe.pe) such that E[Xa] = with K and 10000 with N 50 replications.
a A₂
v x a) By (xe,
UCB = (xx(xe, Bimegrrttd h(yyy (x,, a) 1 meeggaaed) / /xxx V PY.
Wingonsd
with
3 integrated
arg
min x
Σ
R. ux(xx, Bx 1 1 A.) TO)]
Integrated
22

---

Zero-Inflatel Bandits
(x(Xx, As) (x:: As)
]
and W inttegrnted = Ay + E5=1
thr (x((x,, A.) ].
The first baseline Naive Method results in model misspecification. We design this baseline because this issue will arise when researchers fail to correctly specify the zero-inflation structure. contrast, the second baseline Integrated Component Method, uppropriately specifies the model. The second method estimates two unknown vector , and 0 as single vector (g ) from the model 4'x (X,, a) T) B h h(e'y (x,, a) T 0) + Et, which originates from a range of generalized linear contextual bandit literature (Li al., 2017; Chen al., 2020; Zhao et al., 2020). Similarly, for the naive TS and integrated TS algorithm, we sample Buaive from (Bnnative uz maive) and (mimeeratedd Q mmeegrated) from N ((mmocrrane 0 (nttegrace) T, (13 V %%) ) respectively.
Our experimental setup aligns with that described in Section D.2 of (Wu et al., 2022): the dimension d is set to 10, and there are K = 100 arms in this context. The true parameter for the non-zero part, (3, has a norm of 1 and is uniformly distributed, with each entry B ~ (o, 1] for i E [d]. The zero-inflation structure 0 exhibits sparsity 8, meaning only 8 elements in 0 are derived from a uniform distribution, while the rest are zeros. Similarly, for each arm A E [K], we generate uy exactly the same as 0. At each round t, the context of each arm is sampled as Xx,t ~ Na (vk: 전े Ia). Thus, in this setting, we have dx (x4; A,) = N (MA+ 2R La) and (x, = By (N (VA.: Ia) with element- wised mapping jy x + sin(x). Lastly, the noise term e, follows the distribution F(O, o²) with a mean-zero distribution I and a standard deviation of
In detailing the tuning parameters for UCB algorithms, we initially adopt the configurations in Appendix C.2. For TS algorithms, we follow the original setting in Agrawal & Goyal (2013) while adding hyper-tuning parameters ex and ey such that ex X Ey log -o T suggested by Zhong et al. (2021) as o3 21g'd simplicity, in our implementation, we fix x and éy to log T. Additionally, for both UCB and TS algorithms, we set the parameter& 8 to 1/T.
21g k log(1/6) and og Ke log(1/)). For
Further details are provided in Section 5 of Kang & Kim (2023). In addition to Figure 3, we present simulation results with different sparsity levels in Figure 9 and comparisons with another semiparametric contextual bandit algorithm in Figure 10. We choose SPUCB from Peng et al. (2019) as the representative baseline, as other semiparametric algorithms exhibit similar performance. The results for various link functions h(.) are quite similar, and therefore, have been omitted for brevity. Like in MAB, simulations were conducted on a Mac mini (2020) with MI chip and 8GB of RAM, with all runs completed within 48 hours.
D.3. Detailed Simulation Setting for Real Data Application
The loan records data, collected by Columbia Business School, encompasses all auto loan records (totaling 208,085) from a major online auto loan lending company, spanning from July 2002 to November 2004. This dataset can be accessed upon request at "https://business.oll wow.uems..oommmc..c....... coluumia....cc///mrm In our analysis, we treat the monthly payment and loan term as the raw action A& E RR.. We then compute the price as:
price Monthly payment
x
Prime rate )-t amount of loan requested,
which accounts for the net present value of future payments, following the approach used in (Phillips et al., 2015; Bastani et al., 2022: Chen et al., 2023). Similarly, we exclude outlier records, as done in (Chen et al., 2023). In this dataset, the binary decision of the applicant is denoted as Y, E {0, 1}. Following the approach in (Chen al., 2023), we define the synthetic observed reward as R2 = A, Y, The context vector x, E IR represents set of features identified as significant in (Ban& & Keskin, 2021; Chen et al., 2023). This includes the FICO credit score, the approved loan amount, the prime rate, the competitor's 's rate, and the loan term.
The range of the raw action A₁ spans from 0.0004 to 28.5725. To simplify the online decision process, we introduce a discretization of A, into categorized actions, denoted as A,. This discretization follows a specific transformation, {(A,),
23

---

Zero-Inflated Bandits
Gaussian
Mixed Gaussian
Exponental
200
500
2000
600
600
500-
300
100
0
10005 round
15200
20020
10000
20020
5020
10:00 round
15200
20000
product UCC. teurs
UCB
mispecifed TS
method
product (ouss
itegrated UCB
Integpated
aaussian
Gaussian
Exponential
2500
1202
3000
800
500-
5000
10200 round
15000
20000
5000
10000 round
15000
20000
5000
10000 round
15000
20000
preduct UCB (ouns
Tiasped fed UCB
misspeclee TS
method
preduct (ours)
Gusssia
Exponential
2002
1500
3000
1002
500-
500
500
5000
10000 round
15000
20000
5000
10000 round
15000
20000
5000
10000 round
15000
20000
preduct UCB foun)
nisppe Eud UCB maspecifed T5
method
product lours)
rdagrated irtagrated
Figure Simulation for zero-inflated contextual handits and 20000 with N replications with the different sparsity levels. The three rows represent = 1,3,5 5, respectively.
Cluss with
Gaussion with
Gauss on
1200
800
200
12400
10400
1020
Figure 10. Comparison with SPUCB algorithm for zero-infi acro-inflated contextual bandits with T' 10, 000 rounds over N -25 independent replications across different sparsity levels.
defined as follows:
"low".
A, S 1.5400,
"medium",
1.5400 A, S 3.6390,
À. ((A))
3.666390 A, S 5.4164. "very high", "luxury",
"high",
5.4144 < A, S 8.5466,
if A, > 8.5466
24

---

Pero-tnflated Bandits
Density
kuary
0.1-
offered price (rew action)
Figure 11. The density of the raw actions and the corresponding discretization.
This discretization is derived from specific quantiles of the offered price: the 25% and 75% quantiles, the 66% quantile of the remaining offer beyond the 75% quantile, and the 95% quantile of the remaining offer. We have accordingly plotted the density (a) of the raw action set {Ar) shown in Figure 11.
Again, the decision of applicants mainly depends on the nominal profit A, offered, but it will also depend on the environment. Thus, we first model the binary selection Y, E {0, 13, whether accept the offer, of the applicant as a binary regression as
P-Y; = 1) = ((A,,,, 1, (xx))) = M(A00, + 02 + b (x,)0-1.-2)
with some different functions h--) and suitable context transformation b(-). Intuitively, the raw action A,, the nominal profit that company offer, is the most relevant factor. The offline estimation and the performance of via estimated FDR (Dai et al., 2023) using the whole dataset is shown in Table 3.
Table 3. Estimated FDR under data splitting. The function b(-) is chosen as the best degree in the bracket.
h(-)
logit
probit
cauchit
log
cloglog
b(-)
linear
0.1831
0.1912
0.1699
0.0983
0.1835
polynomial
0.1682 (3)
0.1705 (3)
0.1610 (3)
0.3483 (1)
0.1707 (3)
spline
0.1743 (5)
0.1755 (5)
0.1692 (3)
0.3483 (1)
0.1790 (5)
kernel (Epanechnikov)
0.2052
kernel (Triangale)
0.2050
kernel (Gaussian)
0.2049
As shown in Table 3, when we choose b(-) : x x+++ x the estimated FDR for the whole dataset is no more than 0.1, quite small value, which means this model characterize the dataset quite good (Dai et al., 2023; Ren & Barber, 2024; Wei et al., 2024).
Next, for to simulate the counterfactual outcomes in the online setting, recognizing that rewards are deterministic when based on non-zero rewards, we introduce noise to better simulate real-world scenarios, such as deviations in payment plans or additional service purchases. Two important points here are: (1) Conditional on the raw action the noise is mean-zero; (2) that the noise should be related to the context. This indicates the true reward in the online procedure at each round X, -A,, xx; (3) ex the company will obtain satisfies
B[X, A.] Eig(Ar, xx + Ee Ar] A
25

---

Zero-Inflated Bandits
Estimation of B under different X
estimation
B
1.04
HB. -all a11,+1
+1
value
1.00
0.96
5
Figure The estimation under different A, red line is estimated coefficient for the raw action A, and blue line the fi-mrrm plus one for the estimated coefficients of the environment b(x:).
For simplifying the procedure, here we just let
g(A,, x;;
( B1A, 32 + -L,,
with the same context transformation function b(.). Note that we do not have X, for the real data (the observed reward is R₂ = Ar x Y2 instead of RG = X₁ x Y;). so we manually create X; = A + Exp(A) - X, which satisfy E|X; A.] = A; and use the whole dataset to estimate B.. The result of offline estimation 33 with different À is shown in Figure 12. From the Figure 12, we know that any À E (0, 2] is reasonable as we have 31 x and || 211 s O, which means the nominal profit the company proposed, A, by the company plays major role, but the context does have some influence.
Then we implemented our method and the different baselines described in Section in an online setting to compare their performance. Specially, at each round f, the company selects an discrete action A, from the discrete set Adsorete ("low", "medium", "high", "very high", "luxury")). Then company to have potential nominal profit A, with randomly sampled from the truncated original density for the profit
Next, the potential real profit the company would receive with the current context x, is Xx (0,,1,6T(x))))) Besides, the applicant accordingly makes binary decision Y, E {0. with probability PPY, = = =h((A, 1, 1xbT(x,))0) Next, the company receives the real reward calculated as R₂ = X, x Yz-
The regret for each round calculated as E[ X;] B[Y, where Y and Xī represent the decision of the company and the random true profit according to the optimal action A; defined as
/ (a.11. (x))) 1, (xx)))) da.
À arg Acisue
These online process mirrors that in Appendix D.2, with the same tuning parameters. We treat this dataset heavy-tailed contextual bandit, and thus the Huber regression technique described in (Kang & Kim, 2023). Once again, the simulations were conducted on a Mac mini (2020) with MI chip and 8GB of RAM, with results obtained within 6 hours.
E. Supporting Lemma and Figures for Motivations
Lemma E.1. Assume X, - μ ~ subG(a?) and Y, ~ Bernoull(p)). independent Yy Let RG X, x Y, Then R₃ - pp aab--aassion, with aub-Gaussian variance proxy denoted by 72, satisfying:
26

---

Zero-Inflated Bandits
(i) Given any p (0, o² > 0, and arbitrarily large M > O, there exists μ., 0 such that 7² Mo for any μ p4i
(ii) For any arbitrarity large M 0, there exist o Pe. Ms such that 7² M var(Be) for any μ Ma. o² < o and
p [p.,
(iii) (a) For any o² and arbitrarily large M > there exists μ., and p. (0, 1) such that
0r² M
Öp
p=
for any pl E (0, [.a] and pl E (p., 1);
(b) For any μ > 0 and arbitrarily large M >> O, there exists of > and p. E (0, 1) such that
θr
M
0p
02=00 p=p'
for any o² (0, and p' E [p., L);
(c) For any P E R and arbitrarily large M >> there exists of > 0 and ps (0, 1) such that
M
12 ppp
for any o² E (0 and p' E (p..
Analogous results apply for X, μ subE(X), with o² replaced by X² and 72 by a?
We provide visual clarification for Lemma E.1 in Figure 13, which illustrates the lemma in the context where X, NN(,, o²). Figure 13 (a) and (b) show the values of 7 under different, and values when o² 1, and the ratio of r2/ var (R,) under varying p values when μ 100, respectively. Figure 13 (c) presents the numerical derivative Ør" under different μ and p values when 2 1. Figures 13(d) and (c) display the numerical derivatives d,2 and öy across a range of μ and o² values when a = 100 and f 0.5, respectively.
Op
Up
27

---

Bandits
2500
15
2000
1500
1090
590
0.2
0.4
5
0.4
0.8
sigmaa
mu
(a) Illustration Lemma E.1
(b) Illustration for Lemma E.1 (ii
120
(c) Illustration for Lemma E.1 (iii, a)
(d) Illustration for Lemma E.1 (iii. b)
(c) Illustration for Lemma E.1 (iii, c)
Figure 13. The illustration Lemma E.1 when X, exactly Gaussian distributed.
F. Proof of Lemmas
In this section, we will provide the proofs for the concentration results presented in Section 2. We will also include relevant theoretical background and discussions.
Let (g(A) = JA (F)()) denote the probability of the event A, where (x( is the distribution function of the random variable S. Similarly, let (()) = (())dF((()) represent the expectation. We define b = max(a, b) and A min(a, b} for any real numbers and b.
Notations:
We first define the Geneeedieeerr Bernstein-Orlica (RGBO) transformation function (.) based on the inverse function
V (s) = Vlog(1 + +s + L(log(1 + s))
for any & 2 O. It is worthy to note that we replace (log(1 + 1/ with (log(1 1 + (1/811 in the Generalized Bernstein- Orlicz function defined in van de Geer & Lederer (2013); Kuchibhotla & Chakrabortty (2022). It is easy to verify that monotone increasing and (0) = O, and we can define the RGBO norm of a variable random X such that || (1) > 0 O (IXI/n) < 1}. In contrast to the existent literature only care about heavy tail case 0 < 1, Lemma F.2 provides the uniform optimal concentration sense of rate for any 0 > 0 with explicit constants. Before stating this lemma, we first give the equivalence of RGBO norm and concentration inequality stated follows.
Lemma F.1. For any zero-mean variable X and L O, we have
" XXIe 21/0-1/2, S V = p(IX (Va+ [0 < 2* for any 8 2
0.
Proof. The proof exactly the same as the proof of Lemma and Lemma 2 in (van de Geer Lederer, 2013). It worthy
28

---

Zero-Inflated Bandits
note that the probability here can be rewritten
(IX] >
||
11/0 Vo.L(e" - -1//v3] s 2
for any $ 2 0 and hence
P P 21x
= 1 0,31/2 k (v3))
(F.1)
for any L 1 0.
L
Under this lemma, another way to state Lemma 2.2 is using Bernstein-Orliez norm (van de Geer & Lederer, 2013). As delineated in Lemma F.I, Lemma 2.2 can be reformulated as:
4eD(O)C
X
PEIO:
PVπ
with probability 1 - 6/2 for any n 2 4log(2/8)/p²
Lemma F.2 (Sharper Sub- Wei-Weibull Concentrations). Suppose X; - 1td.
subW C)2 then for any 2 0,
||e X 1/2
2n ((0)C,
and
X > 20D(O)C (1/2 E()) (1/0)/1
P
P n- -
20
where (0) and E() are defined as
(2 (6211/8)1/5
if0 < 1,
D(0)
CC-1) V
if $1580 $ if0
and
22/0-1/2
if0 < 1,
E(0)- = 1/VG,
iʃ1 < 0 2, if 2 2.
0.
Proof. We consider the case 1, S 2, and 2 2 separately.
0 2. From Eexp {IX /1///C /CO} < 2, we know that
(IX 119/CO))
E - 10/50
E
S 1.
(F2)
j!Ci0
/=1
This implies for any & E N. by 0 2 2,
X
11 2k < 1 + E 10/k0
by (F:2)
< 1 k0
= 11 V 12/2)2
by 1 (21((
1 12/2 x (2k 1)!! (2k)
5
1,tt
by Bohr- Mollerup theorem
2 k!
1 1+ (1V 12/222 x (2k 1)!! x
k*
< 11+ - 1)!! x (v2v 122 24
$ (2k - 11)!! x (2 1 12 2k
29

---

Zero-Inflated Bandits
Therefore, the sub-Gaussian intrinsic moment norm for X jr satisfies ||X -ull 2 2C
and thus
17s
17s
P - x (2 (2V20%
IP
x > 1 uloo
6n
6n
for any 2 0 by Theorem 2(b) in Zhang et al. (2023).
If S 2, (F.2) still holds for E (1. We claim there exist positive v and x such that
B n1l I - 1²2 k- kk!
2,3,
(F.3)
2
Indeed, (F.2) together with 0 2 implies
E - 11 < 11+E) 51+E|X - 14 < 1 + k!Ck#
Hence, a sufficient condition for (F.3 is k!C < 222 for any l = 2,3, We rewrite this as
2 k
*
2C
k 2,3
x2
Therefore, we can take ς C and v V3x, and then X, - μ id subl' (v, x) by Lemma 2.2.11 in Vaart & Wellner (2023). We then apply concentration for sub-Gamme distributions in Corollary 5.2 of Zhang & Chen (2021); Boucheron et al. (2013) and obtain that
P (I- (I--x x
vO(1VC")
5 / + (1vC9)) =P -P(M- X
V2v
+ Ri-
8
S
2e
If < 1. Denote 3 is the conjugate 0' i.e., B xc. Then from Theorem in Zhang Wei (2022), we know that
PP
Σ a. x1) 2eD(0)]bll2v5+++ 2ec,) =
where 6 = n CC,, E R" with [16122 = On 1/2, [|61|3 Cn and D = (VV (62/=/8) 1/0
and (0) = L., [000000000)] with (0) = 43/"|bblle
Then we have
v2 bil2
2 20L lbblla 20D( (v E()) 81/8
m
where E(()
Combining these results, we obtain the concentration inequality in the lemma. For the result of the RGBO norm, we just use the lemma F.I.
1/0 2 20
V2
Lemma F.2 establishes a uniform result for sample mean i.i.d. sub- aub-Weibull random variables. important to note that our result here is sharper than those in Kuchibhotla Chakrabortty (2022) and Zhang & Wei (2022), especially for the case when 2 1, as they focus on general weighted summations. Another notable difference is in comparison the sub- Weibull concentration results for sample means in Adamezak al. (2011); Bogucki (2015); Hao al. (2019), which require symmetry, while our approach does not. Consequently, we present novel concentration result for the sample mean of i..d. sub-Weibull random variables.
Next, we will show some anti-concentrations for the posterior distributions in Algorithm C.I, which are essential for the proof of TS-type algorithms.
Lemma F.3. For any S x S a+.. we have
+x P Beta(a, a xx²²
T(3+a) +a) (a)
3
)²
a
+ x
a "/3+ (3+2
a+B B+1" 7
3
a
3+1
30

---

Zero-Inflated Bandits
Proof. First, note that Beta(a, 8) (eta(B, (B, Then we can rewrite the probability as
P Beta(a,
8)
a a 8
=P 1 (eta( (,
a 3 +
-P ()
a +
by Theurem in Dümbgen, 2023)
r + a)
a +
8 ++a
B -2)
1
1
(3)
a 8
3+1
a a+1
T(B + a)
B
8
a
B +
a +
+
3+1 1
(a)
a a++ 8
a 3
B +1
Lemma F.4. Suppose & NN od) and & Beta(a, B), then
osp < x +
a + 3
je 9),
if S Ma+
(20+0)e
V2n
[[ 4B] +2 exp -2
2(0+0) n8
Ma++De--u (2a+-330
if >
2a+B
n3
where
T(B 0.)
33
1
2a + 3
1
B B+4
c)a,8)= =
(T())((a))
2((a 8)]
2(a + B)
22B3 + 1)
Proof. First, we note that
TP
x (x
a+B +x
au
P ( < (u+g) 9)
a
2 P
a + +
with y, defined as
2(a + 8)x - 113
3
2
2x + 3
2(a + 3)
From Lemma F.3, we obtain
PPC C
a
+2
1(B +
3
8
a
+
((8+2 a
(a(
a a B
a + B
(B+1
3+12
T(3 + a)) (3)))(())
3
8
1 2(a + 3)
2a +
+4 4
= =c(a, 9)
2( + 3)
2( 1)
with c(a:, B) is constant only depending on and B. If y 0,
Ma+zy then PP 2 p + y) > 1. and thus
n8
P E au
caa B)
+
2
2
31

---

Zero-Inflated Bandits
If y > 0, i.e., x
ng 2(a+
then by Abramowitz al. (1988),
P(E p = P { 62 2( + 3) - uB
(2xx + B)0
(2m+
1
2(a + 3)x 1B 21
22
21 11
2
exp
2
(2a + B)0
+1
(2a++3jo
(2a + 3)0
2(a + 3)x 1B
1
2/2(a + B)xz 11. 2
exp
22T
12(a + 8)x - u33² + (2a + 3)202
2
(2a + 3)0
which leads to the final result.
The remaining part of this section will consist of the proofs of the lemmas presented in the main content.
Proof of Lemma 2.1:
Proof. From the definition of sub- Weibull distribution, we know that Eexp( X -Ml 0 S 0 S 1, (a (b) S a + +b;; if > 1, (a + 6) s 2 20 (a + bO). Hence,
/Cx S 2. Note that for any a, b 2 0:
(a b) S (20-1 v (a + +b)).
Thus, for any C > O, we have
E Ee /CO}
Eexp {((X - -1)Y + u(Y - /Cm}
s Eexp {(X - -MlY + uly -1) -CO)
I Eexp { (20-1 v 1)((X - - + + - /C*}
s Eexp ((20- v 1) u1 - 4 (1 + (1 - -p)
exp (22 1)n² (p" (1 (1-)))))/ /)O [exp { (20 v 1)1x 11 /O".
Since E Eexp(IX- /1 9 / } < 2, we have
0 lim Eexp upl /C/) +0+00
< lim exp +00
{ (2201 1) (p" + (1-
lim
Eexp (2201 v 1)1x-1100 - 119//")
cxsot+00
0.
This implies there exists CR 2 Cx such that Eexp([R - -upl /C/ 2
Proof of Lemma E.1:
Proof. The result that R up is nub-Gaussian or sub-Ex Eabbexxonentaal in the lemma directly comes from Lemma 2.1 by setting 0 = 2 and 0 = 1. For the second result, we first prove the results for sub-Gaussian case. Denote that ?2 as the minimal value which satisfies
Eexp(s(R-- - up)} S 2xp(
for any 8 E R. By the definition, we have
Eexp(s(R - pp)} = Eexp(s(XY - -mp)}
= Eexp(s(0- - up) = 0) + (exp(x((--x))))
- = 1)
= c p D)
32

---

Zero-Inflated Bandits
Since o² is the minimal value such that (x n) exp(s2o2/2) for all R, it also is the minimal value such
that leex S e This indicates 7² satisfies
e spp (1 p pe <
exp(s>>>122
i...
72
2
ssp log(1 - p pe peouts2o213))
max SER 8²
Denote
f(8, f(..1.p, := s²
2
-spu + log(1 p po
with ,2 = [18, x²) = [8,, Mi P, )²).
We will first show that
vp 0,
lim too p40
and
lim lim 0 +
1
10pt1
Indeed, 8, satisfies og (8, pr p. x²) = 0, i.e.,
2pp
4
log(1 p + pe
2
p( +=2.)
8 p+t + (1 p)e 3. 0,
or say,
2
log(1 - + pc 10 = 84 + (1 p)e 8.11 22 + 1
(n + 0280)
(F.4)
p
As we can see whenever s, is finite, we have limp 2 log(1 1 p + pc /////2 +00, then there must be lim, S. +o0 since y >> O. On the other hand, by letting p = the above equation becomes
log(1 + = /2) s. 8202/2.
Since lim log(1 ea)
x t00, lim log(1 + e²) lo we must have ji to limp 1 s, 0+.
Now, consider 72
2
8.11p + log(1 p pe
2202
p
M(1 - p)p
05.m+620711 /2 +
p + (1 p)e S.p 202222
s 12 /2 +
Then consider > 0, by taking fixed p E (0, 1), and denote s = s. = P. 14 0²
we get that
72
P
M(1 - p1ppp)p
02 +1
P+ (1
D)
3p- 2/022
30
12
u(1 p)F
0 /2 +1
302
+ +1-1
Since for any 0 and p E (0,1) 1)
P e0))) loge xx > log(1 - p pe*) log(1 p) log (1+ I- D
11
log(1 - p) +log
[- p e²
2=-logp p.
and note that satisfies (F:44, we have
(1 + 2²3)
-
2
log(1 (1 P 7eout38021
+ 4
p (1 p) 3u- 20
P
by the inequality above
2
3p
+ 3202/2
log P. 3/ 31+3002 3202/2222
p
33

---

Zero-Inflated Bandits
Note that the left hand above less than
n1 + o²8)
(1 + 0²8)
8
(1 ple 10222 + μ S
+ p = (1 11+pp1)30 +p + -
p
while the right hand above larger than
log(1 p pe 1 2(s + 020 log
2p sp + 2p
log p. + -
p
P
Since for any fixed p E (0, 1), we have p 1. Thus, we must have lim +0 3 0, or
log(1 - pe 02
(μ + 0²8))
lim
1 (1 D) 8リ 8p-3-0212
+00+00
lim
[
1) + 2p log Tgg> > 0,
+00+000
which leads contradiction the equation (F.4). Therefore, must have
p(1 11-
e2 + lim
2p(1 - DDp
lim +00
lim
+00,
G² p=
8g2
7e +1
140++00
802
which concludes the results in (i). Then will prove the results in (iii). By envelope theorem,
θr² 0
2
@3.0to/0212_
8011 +
Op Op
1 1+ p (c
sms"
The fact that 1ts is bounded on [0, 0o) and the fact jumo limpt 8. = 0+ ensure that
lim lim Or2 lim
2 40pt1 s?
lim
8.11 1] +00.
Inlv 40pt1 Öp
Inlvo
By the continuity of f(s", .) on p. and 0², we get the first two results in (iii). Similarly, we can show that
dr2 2
pos-u+6302122
p 1 1 1 222
0p
Sr
which ensures lim, p
dr²
+o0 the last result in (iii). Finally, for the result in (ii), note that 8y
var( = E(XY up) = p var(X) + p(1 p)y².
Then by o² 2 var(XX), we have
2
72
72 p + p(1 p)p
var R
p var + p(1 p)p²
Take 4 cu. with arbitrary by letting o² 1 and p t have
72
72
var(R) (R)
2 + p(1 p)pr k=ep.
Mu >0 milly'laa.e cu.
8
(cu. H.)
Oj u=w
2 + p(1 2)
by the (e)
(c - 1)Mpr
T +00
2 p(1 22
34

---

Zero-Inflated Bandits
which gives the result in (ii). For the case that X - μ ~ SubE(A), one only need to note that the sub-Exponential parameter for R pa satisfies
(1 - + po و cxp(ssa2112
for any S 2. which implies
2 a² = X2 max 82 spp - log(1 pe u 22
Since X² V (\, μ4 p) with differential - -) is also differential on its domain except the points that X² = g(A, (.P,,)))..........)...,... the above results regarding large values will still hold. Thus, we finish the proof.
Proof of Lemma 2.2:
Proof. Denote B ~ binomial(n; independent with (X.) we consider the positive p/2 > 0, by concentration for Bernoulli, we have
P(B 2 pn/2) = - P - B p/2)
- exp np² /4]
Given any 8 > 0, the above inequality ensures
2 pm/2
with probability at least 1 - 6/2 for any n 2 f log(2/8). Now, denote X as the k-th observed X,, Consider > 0 which will be determined later,
(V np/2 + E(0)
((1/8)V1
X > 20D(O)Cx
np/2
B
s1100/11
=Eg
Px
11
X
>ee((0)Cx
+ E(O)
B
r2p/2
rp/2
k=1
2xD(O)Cx (V
3(1/0)11
<EB
Px
11
X
np/2 + E(O)
np/2
B z np/2 /
}
+
k=1
B
2eD(0)Cx (1 13 + E(O) B
s(1/0)v1
}
5
<EB
Px
|1
B
X
2
km
220 * +
2
where the last step is by Lemma F.2. Finally, by letting 2 55/2, i.e., = -log(4/8), we conclude the inequality in the lemma.
Proof of Lemma B.1:
Proof. Denote
k.M
Mj
log
with z will be determined later. The proof idea comes from Lemma in Bubeck et al. (2013). Denote X as the k-th
35

---

pero-Inflated Bandits
observed Xt. Consider some positive
P(u-
X
> 5)
XxI M&) ( M ]
1
=Eg
Px
1
Σ
B
k=
B
<EB
Px
EXI
> MR) +
1
Σ
EXI(X & MD) - X & Ma)] 23)
B
B
k=1
1
B
M
1
B
EXI( & Ma) X.I(INW S MaJ] r0]]
EBB
PX
B
M
B
1=1
k=1
+ c) E log T+r
1
Σ EXI S Mo) - Xx MMa) 20)
<EB
Px
T
B
where B= -m= Y ~ binomial (n: p) is independent with (x))=
The last inequality is using
M
+ log 14r
1
B
-
M
< M _ो. log ITc
1
B
r|c ds
B
= = To. log t+e
2
x
B
Next, we consider the positive p/2 > 0, by concentration for Bernoulli, we have
PPB 2 pn/2) 1 PP(p B p/2)
2 exp npp /4].
Given any 8, the above inequality ensures
B 2 pn/2
with probability at least 1 - 5/2 for any n 2 f log(2/6). Then by Bernstein's 's inequality
P(u
X
5)
8
EX1(XX) S Mc) - Xx1(Ixa)= S Mo] > (1+ e) ih. log ite 2
EB B
Px
B
Bite
k=1 B
EXI(XII & Mc) - Xx1(AXA & Mc]]
(1 + e) Tेत log 2 B 2 pm/2)
<BB
PN
>
+
B
Bif
k=1
<EB
Px
1
EXI(X S MM) XAI S Ma]
(1+c) I log 1+e
B 2 pm/2
8
B
(pn/2) -
2
k=1
(1+6)MT+ log T
B 5
12
(pn/2)1tec
8 1(B 2 pn/2)
<EB
exp
(2+0)MI The log Ifz
MM - + +M
13
(pn/2)
s (T+e)MTTe log Ifr
/4
(pn/2) s4fe
5
<xpp
+ 2
MM--++ + Mn. (s_ (1+e)M it log 1ff x
13
(pn/2) 1+c
36

---

Zero-Inflated Bandits
By letting
(1 + M+ log T
1lo((2/8)
4MM, log(2/6)
M +
(pn/2) T2/ 1
3pn
// by
Ma/3
8 3n
A²
9n
2Ar²
m
3n
2Ar² n
Let 2 = log(2/6), we have
(1 (1+c)MTT c)M 1o
-े. (2/8)
4log(2/8)
4MM, log(2/6)
Mn +
(pn/2)
3pm
pn
(1 + c)2 M
log(2/8)
-
4M +
[log(200)
+
2M +H.
(log(2/))
+
1
3p
n
vp
(1 + 2)
4
(1og(2/)
llo
1=c
+
+
M
p
3p
vp
71
which leads to the result.
Proof of Lemma 6.1:
Proof. From Theorem 16.2 in Lattimore & Szepesvári (2020), algorithm is deemed asymptotically optimal for problem- dependent regret if it satisfies:
R(T)
K
A
lim inf T++0
Σ
log T
dint Pk. rı, M+)
k=
where (nr((;r,,)) = inf [KL (P,P)) ER R > r). Here the model class M₁ = N3. x 3% is ZI structure such that
X subG(("))) PP(X = 0) 0}
34. = ( Bernoulli(pa) : PM E (0, 1)}, where X IL Y. and
To prove the first part of the theorem, let us choose a subclass X C X such that XE = {X ~ N((,: th E R..
Denote Ps = NNu,, o²) x Ber(pu)= E Mi == X x Vk. The remaining task is to calculate
dinr (Pk, ri, Mi)
inf pEpEsrAPEes
KL(Pi,Pa)
Here we first note that the independence between XE and 3%8 implies
KL(P1,P)) KL o O d²)} + KL Ber(pi), Ber(ps) (1I-MN) 22)
1 1 Pk
ph log(ps/pp)) + (1 p&) log
20
1 pl
Then consider the restriction MIP P&Pa. there are two cases:
If < <1/pp. Then we can let pk Pı and then rr/p1 = r1/ps suffices to satisfy the constraint. In this case,
KL (T.(Bao Ber(p)), Ber(px)} = 0, and thus
(M1 - (w)2
(Ms - rr/pp)
inf PA
inf nx MC<h/ppEEs KL(P1,Pb)
202
202
If #i > TI/PE, we let pa Mi and then Pk <ri/Ui =r1/up satisfies the constraint. Similarly, in this case
logppp///p + (1 PP)) log 1
inf PepeepaPa>P
KL(P,.PA)
inf pe me<n//m=rr/ne
1- P1
1- Ph
P& log
+ (1
log
r2/
1 1r////
37

---

Zero-Inflated Bandits
By combining the cases, we complete the proof for the first part in Lemma 6.1.
For proving the second argument in the lemma, we note that Pie == NN Ber(ps) E Mg. which implies
(Pak Mc) I
inf pk.PPepappe2r
(L,
Thus, suffices to bound the infimum derived in the first part. For the Gaussian part, it is straightforward to see that
(LL r11/pa) (FL r1/pk)2
A
inf
PESTi/P /pp
20
402
4p
For the Bernoulli part, applying the Pinsker's inequality, we get
inf P
KL { Ber(p1), Ber(pk))
inf
Pk log
Pk:
+ (1- -D3) log (1
1 - Pk
(r//uk
11 M/
(pk- 11/H2N)2
inf PeSm/RCME
(rI/u4) A (1 -1/14x)
(Tk (T))
(rk - v1)²
inf P& men//ee (g(ri/pA) DEST//AE
inf
1 (
Next, we bound the above two terms by
(Tk r2)
inf A
pk ppp
p (r1
peCT/PERLE (r(1//m)
inf A
PESh/PERLEA TI/4
inf AEPE
AEPE
De DeSn/PENE (r
r
and
(rk - r11²
A
inf Pk STL/pee f4 14 r// 11/Pk)
inf The BeSPs/meR in (E ri)
A
inf Pk P palui r1)
inf nese//mene Palmn Tı (r) 22
P1)
Finally, combining these bounds for both the Gaussian and Bernoulli components, observe that the dominant terms depend on ps. A& (0, 1). The asymptotic regret bound is confirmed
D
K
A
dint
A
APP
2=
k=
4pp
2r
2r -P1)
K
Pk
1
+
A
P&
P
K
Pk
A
A
2=
which concludes the proof for the second part of the lemma.
38

---

Zero-Inflated Bandits
G. Proof of the regrets for UCB-type algorithms
The proofs for our UCB-type algorithms also follow the standard approach used in UCB algorithms, which involves controlling two probabilities. The first probability relates to the underestimation of the optimal arm, characterized by (t) (t) rı), and this can be easily managed using the concentration results presented in Section 2. The second probability concerns the overestimation of suboptimal arms, characterized by P(U x rı) ((U)(t) x (t)) > Yk As). Since A > O, the sharp properties of our concentration results in Section 2 also controls this probability, ensuring an exponential decay rate over rounds.
G.1. Proof of Theorem 4.1
Proof. For any > 0, denote the upper confidence bound for pv until round as (1, == p.)( + V be the point estimate at round Based the estimated Py: (t) define the upper confidence bound for jag;
Ing(2/8)
with (1)
2eg (1)
2eD(0)C (1 log(4/0) + E(O) log (4/8) (1)x2(1)
(t,6)) :
(1) =x
OK (1)(2222
with Tix (t) be the point estimate again. For simplicity, we also denote px (t) as pk.m when (x = m, and similarly define
Pk.m- Similarly, we denote (t, 6) as Fm (5) when (x(() m, and similarly define U (8).
Now can define good events follows
:= (r1<
min
U (8) x UP 1,m, (o)}
16(m1,m1 +1....
and
g = (UK k.me (6) x UP hmme (8) < r1).
Furthermore, define Ge (f > Pk } for l E [K] and G g n 9 n 9 n 9 for k + 1, where ep will be determined later.
Step 1: For bounding P(G)). we use the inequality that
P(AU B) P(A) + P(B) P(A B) = P(A n PP))).
Then we can decompose
P(GE) < (P U 9 POST" 9 = P( n GP) + (P(())))) + ((G))) n 9 + P(()))))
with (( and P((G)))) bounding easily. Indeed, denote d(pi. P2) as the KL-divergence between two Bernoulli distributions of probability P1 and p2, then
((( PP P1 e1) I exp (-m-d(p1- -(1)
and similarly (P((()))) S exp (omppd(ppppp Pk- <x)). For another two terms, we first consider to decompose the sample
space as
Ω pi 2 Pi + + (pi.m < pi + +éi
with e/ > O will be determined later. Then
P((g)) n Gir
<P(2 n (g)) n )
<P(m 2 + + (P SM + +,i. 2 Uf,m, (8) x UP 1,m, (8). Pi - -G)
< <exp(-midlp + (1) + PPr Uf,,, (8) U.,. (0),P) - EI <,,m, Sp + E).
Note that for any real numbers a, and any random variable X, Y with 6, Y 2 0,
P(ab 2 XY) S <P((a 2 X) or (b 2 Y)) S P(a 2 X) + P(b 2YbYY. Y).
39

---

Zero-Inflated Bandits
By the above inequality, can next bound the second term in the above bound,
P(r1 2 U. (6) x UP,m. (6). < Pi,mi P1 + +()
log(4/6)
log log (1/(1//21(4/6)) (4/0)
HIPI 2 Pi,mi + 2cD
mIPi. + E(O)
mi mipi.mi
Pl.mi + 12g(22/)
P1 6 < Pl.m, S +p
2m11
(4/64
log (1/0111 (4/6)
<P
pil1 2
Mi + 20D(
+ F((0)
m1 + +c//22
m1 + c1)/2
log(2/8)
x
Pi,mi +
P1 E1 < pi.m I p1 +
2m11
log(4/6)
log (1/0)V1(4//))
11p1 2 <P
Pi.m + 20D(0)C
(v
+ E(0) mi(Pi + ci)/2
mm(pp +c///2
x pl.m1 + log(2/8)
2171
(V
log(4/5)
log (4/0)
<P'
M1 2 Pi.m 2eD(
+ E(O)
mm((P + +
mi + 11/2
lox(2/0)
P1 2 m + + P
2m1
Since we have
log(2/0)
8
P P1
2 mi
S
2m
2
and
log(4/6)
log (1/0)V1
(4/8))
P m 2 Mi + 2eD(O)C
+ E(0)
mi + +2g//2
(pi + </)/2
log (1/0jv1
4
log
67
21
4(8/4) P1
4(5/4)
11 2 Mm + 20D(
+ F((0)
m1P1/2
m1P1/2
log
4
log (1/01v1
P1 Pi 1
p1
1
4(6/4) P1
4(8/4)
IP
#n 2 Pi.m, + 20D(
11P11 /2
MIP1/2
Lemma 2.2 <
Pi p1tel
4(8/4)
40

---

Zero-Inflated Bandits
whenever
m1 pitie
4
2
4
mi
log
log
(G.1)
Pi
P1
P1
4(5/4)
PI
we can obtain
P(r 2 UL (6) U.m,, (6). - 61 < <i, Sm + 61) S 4(6/4) (1i)TT)) an1
+ +//2.
which concludes that
on1
)C 99) S exp (- m1 m2d(pi + (1,p1)) + 4(5/4) (114))
+ 6/2.
It remains to bound P (((g)) n 9R). We first decompose Q [pn.m, 2 Ph + +6)) U (Pk,m, Pu + c and similarly obtain that
(((())) 9%)
<IP(p 2 ph + E + P Pp S ps + 6KTT S Ukmmy (6) x UP
kmm, (6),Pr,m, > Pc -E1) (8), Pk EN < Pk.m= Pk + +c)).
S exp - m= + Pb)) + P(r1 S UK kmma (6) x UP
k,ma
The second term in above be furthermore bounded by
IP PP S Uk (0) Ko (6), pk Ek < Pk.ma S Pk + Eb)
=P M1P1 I ma.m + 20D(O) (V
log(4/6) mAPk.me
log log(1/0)v/ (1/8)V1 ( MpPk.m+ /2
+ E(())
log(2/8)
x
me
+
< Pk.ma S Pk + cx
2m
=P M&Pk + Ak <
Pe.m + 2eD((0)
(v
log(4/6)
+ E(0)
log (1/8)v1 (4/8)
muPk.ma
/2
MkPkk mm /2
log(2/8)
mx + x
AK. pk < Pk.ma S ph: + EN
2m
(v
1og(4/0)
log (1/0/1 (4/5)
SIP
P&Pk + AB S
mumm + 2eD(())
E(O)
mx - +x
mi (Fk - E2 /2
log(2/8)
ma +
Pk Ek < Dk.ma S Pk c
2111x
<P
M&Pk + Ak S
(V (mm((xx ex
(4/5)
log (10))1(44)))
(2/()
Dhmme + +2cD(0)c
E(O)
Pr.me +
mx =x2/2
2
Ab
Pk + ph Ax
MK +
5
2p1c
2rk + Ak
(g/()
log (1/0)11 (100)1(440)
(4/0)
(2g(2/8)
iummu + 2eeD(
(1
+ E(O)
Peymy +
[ma(pr - -2
my (pt =22/22
2TT
SPk + Pk.p.

---

Zero-Inflated Bandits
where the last step is by the fact that for any real numbers a, and any random variable X, Y with Y 2 0.
P(ab & XY) & Pffa & X) or {b ()) & P(a S + P(bb)))
Now, the two parts in the upper bound of (r1 S Uh k.m (8) x UK k.m, (6), Pa ck < Pk PP + (k) can be furthermore bounded. Indeed, PR.p can be bounded as
P&
log(2/5)
PE P
Pk: 25 + A
S Pk.ma +
2m
Pk: AR
log(2/6)
P
Pr.ma
Pk.
2Tk + A
21T4
Pk
log(2/8)
S exp
-2m
2r'k + A
2m
6
2maPR DR
PRAAR
2 (2/5)
exp 2
2r + Ak
2rk A
mi
I 8/2
long as
2(2rk + AA)²
2
my 2
log
(G.2)
Similarly.
PR.p
Dk
(V= log(4/0)
log (100)1(411)
< mu 2eDD(0)C
E(O) mi (pk - ex)/2
2pk
-cx)/2
(v (Vmatoe -cx)/2
log(4/8)
log (/g()/))v1()) (4/8)
2cD(
+ E(0)
$ Tokmm - 14
2pk
mp =x)/2
by Lemma
Ab
2cD(0)c (V.
log(4/6)
log log (1/1/1
P
E((0)
Tux.max 14k
2pr:
mpx
-x2/22
my (px cx)/2
4eD(0)C
| To
11
+ 8/2
PLE()) 2.
PkymE
by (F. 1)
+ +5/2
1 + V
8. 31/2-1/6 1/6 ny F(o) (v3s)
2
where
Dx 20D(
(V -xx)/2
log(4/6)
log (1/0011
= [4k Po.mell
11
+ E(0)
pu. F30)
2pk
ma (pk- ex)/2
2 2
42

---

Zero-Inflated Bandits
By the increasing property of V (+), obtain that
p/ (v3s)
8. 2
Pk PKV33mm (0D(
A
(V
mx( - <x)/2 + -((0) log" log0 /1/00 (4/0)
log(4/0)
V
8.
34/2-1/0 px R(O)
2pk
2eD(0)C
my (pk - 6x)/2
by (G.3)
V. 4eD(O)C
(V
log(4/6)
log (0/0///1 (4/8)
3 31/2-110pp B19)
20D(
mm(Pp -Ex)/2 + E(0)
0.
2
mx(px cx)
3p% log(4/0) 2(pk ck)
/3 F((0)
(og(1/0)V2(4/0)
V
0,
31/2 1/0 Fy B(o)
Vm ck)
3601 3(1/9341
4 5)
3/22- 110 Pk E(0)
4 log (1/00/1
V
31/2-1 1/0 Bimn
log
mm
i
by TiPk 3(1/0)A1
SPE
28A2
3pk Z0m v
3pk
yk
Ork 1n)8s
31/2-11 1/0
Pk. E()
(1/0J1] (4)
12 10 pq B(0)
log
+
log
8.
2v mK
1
4 2(Pk -rp?
whenever
(1+
1 cD(O)C
(1
log(4/8)
log log (1(21//V1(4//))
(4/8)
A
2
I
mp -xx)/2 + E())
<
(G.3)
vpk
mx(pk cx)/2
2pk
and sufficient condition for this is
1
log(4/0)
A
1+
eD(O)c
Ppk
(p =2x)/2
4px
and
1
log (1100/2244/8)
AB
2 1
eD(O)CF(()
<
/Pk
mp cx)/2
4pk
Thus, we can take
128c (2) (p + Pk)
(6C)())CE()))/d()) + vPk)
44)
m 2
log
+
log log (1/0)VI
(G.4)
(pk 10k-6x44 4
(Ps - -0-x444 A
Therefore, we can furthermore upper-bound Pk.p as
2
PR 5
+ 0/2
1 + v
31/2-1/6 Bio) (v3s)
2
+ 5/2
Spt
+
(1)
Tink
3pk
8 3(P k
8
2
2
Thus, we obtain that
P((gT) n Ø% < exp ( -m + ch. pk)) + (8)
T[ps
+ 8.
43

---

Zero-Inflated Bandits
under condition (G.2) and (G.4). To summarize these results, have
P(C)) _ ) n g P((9))(()))))))))))))))))))) + ((())) n 9k) + +P(())))
$ exp ( (- (-mid(p: + +1. + 4(8/4) PI-1
+ +8/2 2 + exp -i -
3p2
exp ( mpd(pp + c pk)) + (6/ 4) XPp-1 + 8 exp mx Pk Ek))
whenever my satisfies (G.1) and my satisfies (G.2) and (G.4).
Step 2: Now, deal with Blex (T) O (G)).. If c* (T) > max(mi, mg), then arm k pulled more than mg times over the first I rounds, and so there must exist round E [m....., TI such that A, k. However, the good event Gk. have
U (t, (t, (1, 8) m. (o)U mm
the event Ff
rl
on the event g
()U S (t, (), [T......
min
This means the agent will choose arm instead of arm k at time point I, which leads to a contradiction. Thus, we must have
(7) & max (m1, mx).
Step 3: Combining the inequality in Step 1 and Step 2, obtain
Ece (T) E(ca (T) n [(E))] ((a)))))))))))))(())() ( 7P(8))
< max(m1,
yan1
T exp (- mld(pi + (.P)) + exp (-mid(pi.PL - G)) + 4(8/4) (1it()
+ (6/4)
3Pk
+ 36/2 2 + exp 1 dp - e1)) + exp
mxd(pp + bk.
max/m1, m+] + T expp-2m116 exp((
PA1
3P Fipe xx + +20
+ exp( expp-2mm=45 2m + 4(5/4)
PI
+ 2
whenever satisfies (G.1) and my satisfies (G.2) and (G.4), Now, taking
4
4
ritt!
log
Pi
and
mi
12TTk Ax pd
128c D2 (D) + vpx)
log 4/5)
+
(pn - -Ex)
A
16e (GeD(00 D(O) /Pw) log (px Ex)
(o (1/0)v1 (4/8)
A
2(2rk + 22
log (2)
AZ +
128 D2 (0((O) + /Pk)
(()()))E(()))P)))) (PE + /Pk)
log (1/0)V1 4
log 5
(pu -Ex)A3
(pr Ex) =x)
44

---

Zero-Inflated Bandits
with cx t/2 -Pa/2 for k [K] satisfies (G.1), (G.2), and (G.4) by rh (0, 1]. Under these choice, we obtain
exp(-2m1c5 -22m11 (2) exp(-22mpp
(1/2)am1
(4)
exp
-2
2 8
(1/2) MAl7 -2
1
-2
= 4 (66/16) (2/2)
2
and
12mm- (2) -xxpp-2mam -2m
p
2((2kk + Ax)2
128e2 D2 + vPA)²)
log(4/0)
exp
+
pk/2
16eD(0)CE(() /P((1 + vPb) log (4101/)/2(411)) (4/0)
pk/2
D
Vps) 1og(4/8)
(2Tx + Ax)² +
exp
A
log (1/0V1 (4/6)
16eD 3/2 +1+ vpk)
log( log(4/8) )
exp
(2r + Ax)²
A7
1 log
1oglo(4/// 4/6)
exp
8/4.
A
Aggregating these results, ET) can be furthermore upper bounded by
8 (6² (16/ (1/2)
(T) S max(mi, m} } + T
+ + + 4(6/4))///) +2(6/4)² 26
I m1 + m + T 8 (62 (1) 1/2 + 5/22 + + 2 1 +28]
=m + m + T 22v0+ + 38 + +88/32)
4 pi
log (1/10)212300) 12)
2( + Aa)²
128c ( + vPb)?)
log(4/8)
Pk
Pk/2
A
(BE + VPk) log (1/0/1
(4/0) /1/0/((A/0)
T (3V6 + 46 + 83 68/32)
ps/2
A
AA1
2 2lg
<
log (4/8) + (2rk + Ax)² + 12 2 (1 + /px)²
P1
2
A
log (10\v1 (4/8)
+ +320D()) + vpx)
+T (3v8+48
46
+ 46
Dr
by t4 1 1 and Ph $1
4
log (4/8) + 2 0 (1)
log( (og(4/0)
p
+4c)(())CE()) log 1/11)((48))
T (358 + 45 +45++8132)
PKAs
45

---

Zero-Inflatel Bandits
Now, choose 4/T2.
Ecc (T) -
8log p
(9 (1)
log T P
2000000
log
(1/0)11 T
+ T
/
6
16
+
Pk
T
T
T
Finally, we obtain the cumulative regret bounded by
R(T)
K
(T)
2=
log T
Σ
Ds (9 4 (0))
log T
Pi
p A
K
log (1/0)11
16 T
2
k
+ (0
+ 6
+
Σ
A
Pk
7
k=
k=
which gives the regret in the theorem.
G.2. Proof of Theorem B.2
Before proving the heavy tailed bandit results. We first state some basic properties of g(p, c) in the concentration of Lemma B.I. Define c) == pg(p, e) = (1 + e)21-rp14. + 2 + I.4 then is monotonically decreasing and monotonically increasing with respect to p. Specially, they satisfy
2 (8+ 22)
h(p,e) S (1+))((2xx122222
3
for any p E (0, 1), and
(1 c)2
4
2 VPI
g(P1,c)
2 (1+c)2
+ + 2/p2 = h((2.
3p1
Pi
for any P1.P P2 E 10.
Proof. The proof is similar the proof of Theorem 4.1. The essential change is the concentration of trimming observable sample mean in Lemma B. instead of sub- Weibull concentrations. We will borrow some techniques in (Bubeck et al., 2013). For fixed e, we will write g(p) = g(p, e) and h(p) = h(p,e).
Step 1:
Similar as the technique Bubeck al. (2013), suppose A, k, we define the following bad events
(t) = | 2 ph + M
log 12 14. (t)
(t) = (r1 2 U ( x U.P.
and
4s
M
Bl) (1) = ca (1))) < [2(ps + Ex)g(pn + +e)]
log
(Ax EkpuR)
1+c
Mt
(e(t) < [2h(pe + Ex)] 1ts
itc log T
(Ax - ex1x))
with E (0, Ax/Px) determined later. Similarly, define
(t(()) (Pe, > Pk Ex}
46

---

Leflatnfl Bandits
On the event D e
n B have
U (,),
U
1,c1(0),
> 71
rk + A
PEPk + A
log 12 cx(())
c/(1+c)
2 P&PP + 2h(pE + +xx)
HEEE
increasing
log 12
c/(1+c)
PAPE + 2 2/(++))
+ PRER
Ck
log </(1+e)
2 uu(Pn, ek) + 2h( ((1r))
+ MRCk
(x.(t)
log t (x(())
e/(1+e)
-MNPKt + 22((P..)
log t?
(log t² e/(1+e)
Pk.t + 2h(P
(x())
Ck (8)
log t²
e/(1+e))
PR.mutt)t + PR.
Pk.t
C* (t)
U (1)a x UP (t),""
This implies A, = 1, which leads to contradiction.
Step 2:
Consider the probability:
P(B U B U BB) = P((B U B (BE)) + (P S P(B" (BR)) F(B n (B)) + P(B))
with P(BB) and (P n (B))) can bounded easily. Indeed, if we consider them, then
P(B((1) PfN.. > Ps + Ex) S exp (-18
Next,
(( (BE())))
logt? T+C
=P
(i.calti 2 pk M +
(px, S ph + +x))
ca (1)
<P <Ppp
Ek pr.e)
(imoacoss 2 us + + M 14
log 12 (t())
T#7
+ TP
{pr - -Ek S PR.t S Ph + Ek)
by decrensing S
log 12 142 ct(
P(pp- - Ek > Pe.)) +P Maaaet 2 pb + g(pt + M
with
P(p: Ex > PR..) S exp (-tef/22
47

---

Zero-Inflated Bandits
and
log t²
P
(k,c(00, 2 pu + t(p + M
c2 (1)
n 0lpp +x)M i
log 62 (x(
it
2 exp
Mig Ll.
(px)
9 11 (pu + EK)
log 12
=2 exp
(pk)
CA (t)
we need pk +5
h
+ (pk) log 12
2cxp
9 Lis (pk) (t(()
1+4 log
-2x
Pk
CN (t)
Proof in Proposition of (Babeck al., 2013)
2
Σ
1
< 13'
(1(1)
e [+)==
Thus, obtain
(( n (BR())) S exp (-te + 22/0.
Similarly, we can show that
P(B" n (Bg)9 Plrr 2 U (1-1),1 x UP (I < Ph + +
exp (-1s)/2) + 22/2.
for any E1 P1..
Step 3: Denote
it M
V& = [p))
log T
Take E1 P1/2 and
Az 2px
satisfy E1 E (0, and EN E (0, Ax/uk) for k 2,..., K. From Step 2, we know that
(( U (t) BE))
I <exp
(ttek/2) + [exp (-te
+ 2//²]
+ Texp (-te?/2) + 2/1²]
(L142 1A
lpi
=2exp
+ exp
+
8/4
8
1
48

---

Bandits
thus
EcN (T) E
1(A =
1=1
T
T
[(1(A,= =k} n ()) (1) +
B((AA, = k3 n (xmmm.((1))
T
$ V%x+ +
Σ
[(1 = =k} n B (()
tm1
Vx Σ
B(1(A,- = 13 n B (i))
VV/+ +
P(B (Brr (t)
1>V
T
V +
Σ (1) U (t) U BB)
12Vi
tA
tpi
4
V
2exp
+ exp
8yu
13
1>14
t
+00
tpi
+00
S +
J
exp
8
dt
+
exp
8
dt +
4
t=1
13
Sp
2
8
16
S V/2 2 X
+
1.5 < V/
6.
P
A
Pi
7
P
A
P1
Finally, by plugging the above into the decomposition R(T) = >k A Beg (T), we obtain the result in the theorem.
Proof of problem-indepennden regret in haave- UCB:
Proof. Still plug the bound for Eci (T),
K
R(T)= = Σ
Ees S Σ A Vo
Ao
16
+
8
6
P
k
p
2=2
k=2
k=2
For the second part, still apply Cauchy's inequality, we obtain
K
A
16
8
+6)
Σ
Σ
A
16
8
+6)
P
A
pi
A
pi
2
A
A 24
K
8
16
TAA+
+ 6
A
P
Ph
A+SA
by Cauchy's 's incquality with A=
16 ΣK
K
4
S
2K
+3
+ 8
T
Pk
p
2=
49

---

Zero-Inflatee Bandits
For the first part, we Hölder's inequality instead follows:
V
A
k=2
K
Ltc M
V
Itr
(2phg(pe,e))
log
k=2
4
14c
by Hilder's 's inequality
-
Σ
Vi
2pk e) 1ife log 1fz T kE[K]
max
2 2((+ + 10/3) (MT) (K log T) r T
Thus, we complete the proof the
bound.
H. Proof of the regrets for TS-type algorithms
H.1. Proof of Theorem 4.2
The primary proof idea behind our TS-type algorithm be divided into parts: first, controlling the overestimation of suboptimal arms is achieved through truncation in the clipped distribution, a technique we have already used in the proof of UCB-type algorithms with some modifications. Second, restricting the underestimation of the optimal arm can be accomplished through the anti-concentrations for the posterior distributions detailed in Appendix F.
Proof. Denote (t) and px((t) (t) is the posterior sample for the non-zero part in k-th arm at round f, and others use the same notations in the proof of Theorem 4.1. Define
47
+ log
- (1 + 1/VoT)
4 1 + log (1 +1+ 1/VOT)
02T
3 A1 min
P1 +
log*
s
Pi
and
( T
}
Ep = P1
min sE[T]
pr.a +
V 4s
log+
4sK
Let = = En x Ep, then we can decompose the regret as
K
R(T)
(T)
2=
E27E +E
Σ
(+CH(T)
(H.I)
E + 2e +E
Σ
(ECU(T)
A: (EA)
For any x 2 0, we have
P P = P F, 2 x)
PE, 2 x x/2) + PE, 2 x/2).
By Lemma 2.2, we know that the Orlicz norm for فı.. μ satisfies
20
مم M1ll
(H.2)
P1 V
50

---

Zero-Inflated Bandits
with probability 1 8/2 whenever 2 4p, log(2/6). Thus, by the same decomposition technique in proof of Theorem 4.1, and let 6- be the Dirac delta function, have
P P 2 x
=P Es (T) : 141-
4y
+ log
(1 + 1/1 ST)
02
1 log log
'(1 + 1/vs7)
02T
min IsesT
11 +
log+
2 2
2 0
22 8
2 pis
2
=P 3$ E [T] A11
M1, + ISSTT
min
log
0
płsK
2
+ 3s [T] Pl.e P1
P1
82.
log(1 + 1/V/T)
By Lemma 9.3 (Lattimore Szepesvári, 2020), we have
2 pis
[402T)
15K
60K
P E E [
p1
min ISeST
Pu +
log*
přsk
2
0 <
T(x/2)²
x2T
and by Hoeffding incquality, we have
P E (T] pI,- - 2
P1
T
2sp
cxp
log(1
1/v
log (1 + 1/ 1/V
T
20p2
exp
s- S-1T-1 ds
$=1
1 π
exp { (22u? 21 du
P1 VT
pt
V
2T
Similarly, one obtain
P 2(E,2x/2)= PP
3s E [T]
P1
min TE[T]
11. +
log
I
2
0
60K
45
4sK
2
T²T
by Pi is Gaub-an with variance proxy at most
4s Thus, for the first term in (H.1), we have
E 2
27
P PE x) dx
Jo
(H.3)
+00
120K
2T π
2
< 27
1
dr
+
8v 30KT
TT
2T
Now, consider the collection of the 'good' sets defined as
K : k E [K]
A 2 (23) V (2e 2p, K K/T)
then by Theorem 36.2 in Lattimore & Szepesvári (2020) with Ax/2 2 in K, we have
AglEcs (T) < DR + A
T Σ
I(A = k. = EQ())
+ A Σ
(G
-1)
(H.4)
k+=++
51

---

Zero-Inflated Bandits
where
(g(() = -1 (T)(t) (1)
4
2
and Gk.o(c)= =1 (R. c) with Fk. is the non-clipped full posterior of the k-th arm'. Note that (tx comes from cl. (Tu: mandb: TT(())
4
(a(() x Sa(t) > nh +
Ak
(t S (x((t) x (a(t) > >m
2
2
Denote
T
Ak
<x(p)) = Σ 1
(h(())
> Ma
+
4pp
s=1
T
4y
1 + log
(1 + 1/111/// 3T
VT)
o²
4 1 + log (1 + 1/V 22T
pk.s +
log"
> pk +
p 8
sk
4ps
Σ
1 (p)):
and
T
Pk A
(p) = Σ 1 (a(s) Pk +
4rk + Dk
Y log+
T
Pk As 4rk Ao
Pkis +
V
48
4ssK
> Pk
#=1
Σ
(p))
then
AgE
Σ U=*++
T
1(A = M44=k,ET11 (EE(()
< ARE
Σ 1(A = =k)1 (Tu(t) x (x(t) > TA +
A+
)
2
1=
A
< A
(T((s) x (a(() rh
2
Σ 1 ( (p) [n..6e1]
< A
T Σ (()) + -=((CL(())
A
'There is trick for converting the clipped distribution the non-truncated full posterior distribution. We omit here, and the details can seen Jin et al. (2022).
52

---

Zero-Inflated Bandits
Similar as we are dealing with the first part in (H.1), have
r
(1))
20 log+
4022
A
Pk
TP
Miss +
pfa
přsK
Pkk
4pk:
P
PR,s
Ph.
log(1 +
1/v
s=1
T
4
(402T
A
Pkia
+
V
log"
p
11 +
4pk
+
Pk
2T
==1
by Lemma (2021)
S
A
24pk
8YPP A
log
TA
2
log*
T
π
2pk
Ax
8p K
8p
Pk
27
and
Σ P
(g.,,(()))
PR.e
+
V
4s
Y
log"
4sK
T
Pke
4r + D
P&
<
Σ
T
P
PR..
Ph +
V
48
Y
log+
4sK
T
>
Ph
by Lemma 2 in Jin al. (2021)
12
47
Tpk
(Tp) 4K
Ph:
log*
+ V
2 log*
Pk
pk
4K
Note that -
-=---og' llogg (ax²) is decreasing for 2 e/ Va, we have
TA 8p
1
log*
A
K
2pk
for any A 2 20/ 2pp K/ T/TTon and
1
TTp
log"
log
c
Pk
4K
Pk
Pk
for any 2 4eK. Thus, we have the bounds on k E KC such that
Σ (H)) <
Ak
24pk
+
8ypk
log
TA SpÊ
2 log
TD
1
2pk
D
8p
pk
2T
Ag
24pk
1
T
27
1
T
8YPk
2pk
2ev 2pp
K/T
e
2peK
20
2p
K/T
e
2pk
Pk
k
Ph T
Pk
K
PEVT
and
T
12
47
Tr
Ty 4K
Σ P(GR,s(P))
(p))
S Pk
+
+
log
2 log*
Pk:
Pkc
4K
12
2
< Pk
+
+
4ry
pk
p
1
pk
+
53

---

Zero-Inflated Bandits
Therefore, have
T
E
Σ
1(A, k. Ex(())
S A
(()) + P(9),s(D))
PkT
A b
A
+
K
PLVT
Pk
remains to deal with the last term in (H.4), For doing this, we will first prove the following result: for any e 0, there exists universal constant such that
E Σ
c
(H.5)
G1,((c)
p
Indeed, let Z be the random variable denoting the number consecutive independent trails until a sample of the distribution Pk. = N (Nkk00 PLoPE, Beta(ax,,s becomes greater than V1 - e, then E (). - | EY1..
Consider an integer 2 and 2 x v with some p' E (p, 1) determined later. Let Ma.q be the maximum of independent samples from Pk.s and FR,s be the filtration consisting the history of plays of Algorithm C. up to the s-th pull arm 1. Then
1(T1, 9)
P (M1. 11 c)
2 Fi,s) ]
a1,8/11,
+ z
a1, +
z
2B E
Min
(H.6)
01,s + B1,s PI,v/ps'
01,s Br,0 P1,ovps
31,0 PLoYPs Fi.s) )
=E 1 01,5 +
2
2 on-c7t
M2
01
+ 2
01,0 $i, pps
01
Then by Lemma F.4,
a1.$P1.
P M1. >
F1.
01,8 + B1,5
pspp.
+B.
=P
M1
11.s P1,vvps IF1.))
01 + 31 +
by the choice of
c(ai + B1,e, 81 + B1,e) 9 V log
2g P
2
+e
V2T 8p log q +
hy fact (H.8)
24 1 Pf
v1 - Pl
x x 822 (2-2-P))la log p'
v Sp log g
9
23+ +9 πe
2 Sp' log +
(H.7)
by fact (H110)
P1
Xe 12 -1) log log
p'
8pp logg
2
21+2a; +29 ze
2T 8p' log +
by (1 11=x)5oo
-T Pi
4 1-p'
2
1 - exp exex
x s 1-22-p)00 log
24+ +251 NC
/128T log
q1-p'
2 1 - exp
128 log
for some 2 e² and p' > 1/2 when we take
2 20(201,5 + 31,a) 2p log
(H.9) 2
a22n, + +B1.) log q + 31
2(01,5 + (2.z)
2(a1, + 31.s)
54

---

Zero-Inflated Bandits
In the above, we the the following three facts
c(a1 + B1 + -1,,) = B (a1 + B1 81 + 8 B1.a)
B1 + B1
11+s-B1.
(31 + (1,a)
2(a1 + 31 +
2a + 31 + B1,
Bi.
81 + 8 BI, +
x
2(a1 + $1 +
2( + = BI 1)
by Stirling's formula
1
(an + B1 + x)
2T + (1 p1) ps)
(a1 + +ps)
+ (11 +
p1 (1) p1)8-11
(H.8)
81 + (1-P1))
81+(1-p))s
201 + 81 + (1 +1+177 P1)s 01
2(ai + 31 s)
2(a1 + 31 +)
2
4
(ar + 31 + 8)
1/2
2a1 + B1 + P1)s
4 41+0++00 en (31 + (1 - p1)8)
(31 + (1 p1 )8)
1/2 X
@1 + P18
2 -I-Pi P1
x 4 x 2 +p1 VI P1
X e
23+221 +231em eT
23+20; +231 en
for any 8 221 1,
02201, + (2,0) V 2p log 2 11..
01.0(3 + 5 B1,a) (2a1 + B1 + + B1,s)
22 2p logg 2
/11 2011
(2om1] 12
V 2pl logg 2
with probability least
(H.9)
(2o 1)219
2r
= 2 exp
2p'pfo²
with probability at least
(2o + 1)
2g
= q 2 exp
with probability at least e
2p'p300
and
((2-p1)log log 9 p'-6"
P1
24+ 221 +281eT
V128T log g
(2-p1) log 25
q q'-p'
P1
24+201 +231
V128T 1128tlog
Iot :m x log
VI-1 P1
-1-p"
(H.10)
<<
24+201 +281
/ 128mdd
1 ppp
+ +29 3/2
1-0
v(I -PI)dd-
with da <0 for any > O. Now, take
(2o + 1)27
27 272
1-p'
160
2 0² v exp
V
V exp
(H.11)
20'pp0²
V(1-pi)di-p
(1 (1-p²) p')
in (H.7), we obtain that
p Mi >
01.691.8 +
z
Fiis)
21 1
01
Br,0
PI.o ps
55

---

Bandits
On the other hand,
01,5
2
P
+
2 11 -
01,5 + B1
/ ps
01.
20 (2 + B1,5) 2 logg
P
M1P1
01, + 11,
2 + B1,5 p1.0 ps
o (201, + (1,s) 2p logg
01 + 31.5 m-11)
M1, f1 +
2 11
01,
ps
01.8
80 [2a1 + 31 + B1.e]
2p' logg
-(1 - pıla1 + +p1 (Bis P11))
=P
M1s M1
(al + B1,s
ps
M1
a1 a1 Bi,.
24,,
=P
(M1ss
B 2 PPs) PBI,, p1s)
8
P
Ui.* -
< Bi, -18 -
P
B1. Pis < ---
1
oml
2p' logg
PP
P1. H1
20 B1,s 2 p18
P(B1,s 2 p1s)
s s B1,
ps
+
100
P
11,80 11, + A1(
2p' logg
2 m1A2(3,
8 -
< B P18 <
8
ps
1 v+
0=1
s < Bi, - -D18 ++1
x IP
-
by (H. and (H.13)
(1 (1-9-p19 IPBII 2 p1s) +
+o0
Σ
1 - 2p1 20150 2--2-" 22p1-p111) P p-3 < Bi, - p18 -is 8
2
11
1=1
2 - q d - 201 a -p1 4/ip
where define
As(s,)) ols o(s- + B1) + - -1
A2(s,u) 3-11-(1 - p1)ai + p131] - -s-1B P1)
8-1 B1, tan + B1,)
l1 + + B1,
We also use the facts that
σ
2p' log
P
11.8 M1
+
0 B1. 2 p18
9- B-1B1
ps
2p' log
=1 P
11 f1,s
B1,s 2 Pis
8 8 B1,
ps
(H.12)
the fact that Bi ( m1) subG( for Bi.,
pl o'log
1 - exp
ps 1B
by BI..51
1 1 9 1
56

---

Zero-Inflatee Bandits
and similarly
2p logg
P
M1. MI + A1(s,t)
2 (2,,0))
- B1, pis <
ps
0
1 1+
by (1 (1-m) mm Sp
IP Mi,0- A1(8, /
2p log
1i (pi -5 5-Baa,))
8
Bi, - Di8 <
ps
8 81 01 + +8-1B1,
1
2 ++
by similar trick (H.12)
B1,
"1(p1 =BBB)
2p' los
A1(8,u))
sup
exp
8- B Elp - p1 (0+1)-1)
2g²
8 a1 + tB-1B1,
ps
by the fact (H. 14)
-
B1, Al(s, v)
2p' log4
1
sup B1., (p1 - .P1 (1+1)-1
exp
[p1 +
(v + 1)-1
20
ps
by the fact (H.
2z2
p' log q
1 1-exp exp
[pi + (v + 1)-1
P1 6+
ps
by the fact (H. 16)
1 2p q 201 Ppip
(H.13)
where the fact we used is
(1 - -8 -B_BBi,)
M1 s B11s)) -B.B)
2p' logg
-2,1 v)
s- -ai + +
5 + +s11B
ps
(P) -s-DB(,o)
20 20/s-1(200
+ (1)) + + Bl,ol
2p' log
M1 (1,s)
(H.14)
[s- 01 + s-1 --,1, 2
5 B1,
ps
111
2 P1
1 u-2
(v + 1)-1
P1 m+1
B1,
2p' log
(2a1 + B1) + -1 B1.a)² p log
A?(8, v)
20
ps
8 BI,s
1s-1a1 201 3-1B BI,s] 1 ps
1
p' log
(H.15)
8 B1,s ps
B Sp1
p' log q
2
ps
and
1
p' log q
2 Pr
p log q
(H.16)
P1
(v 1 1) 11
P1
v+I
ps
P1
ps
uniformly on v, 2 and - -B,, E [pi 1 ,P - -- 11 Therefore, by plugging these inequalities into (H.6), conclude that
P(M,s < 5 9-2 q d d 2pi q -20 d/0
57

---

enflateteee Bandits
for any y satisfied (H.11), and then
ET
Σ
P(T1,s 29)
(20 112
27+20=+2::41/22
160
S e + exp
+
+ exp
2p'p/0²
v(1 p1 )
p12
t00
+ Σ
q-= +
1110 + 2012" q -2pit1/11
q=1
12
(2o 1)2
77+221+28)+111
160
S ee + exp
2p'p2002
v(1 P1)d1-0
exp
p1)
22p
2p p/ip +1+ 1 p//pp
for any & E Let 2p p//p = 1/2, we immediately conclude that
E
EY,,, S
(H.17)
(1,
with c= c p. 02)
is fully determined by Pl, Pi.p, 0² and free of s. Now, let Eg = (Pi. x PL. > rı e/2], then
P(TL. > 1I E1,)
2P 2P > 1i.s x Pi,s e/2 E1,a)
=1 P Mi.s p.. > N (Mi,s: 20 (pL-ST Beta(on,s; B1,s) 6/2 E1,)
(H.18)
P (M. > N (mi,. 20 (pspi..)) e/(2p)) | E1,1)
21
+P -P((p.. > Beta + pic/(Ar) + {))
58

---

Zero-Inflatel Bandits
Note that we have
P (ui. > (T 20 (pspP, + t/(())) (1,0)
2s0²
eB1,a
= B BI - N
Bl,
E1,
P
2pr
the inequality does rely unything Ei
B
P
Eexp Eexp
x
2
4pf
4so2
Spe2
E
(s
(s11B1,)) B1,a)²
1 > p1/2
>p1/>>>1/2221 P1/2 BB. > p1/2)
2
16p102
spe?
(5 B--B1,)) B,, S 22 P(s- P(5 B1,5 s 1112)
+ E
exp
16p1
spe?
Σ 2
exp
64pio2
+ +P((0- < <-- "BI, Sp112)
by Theorem 2 in (Able, 2017)
1
spE?
I
2
exp
64pi0?
+ +exp (- sc((p1/2.11)
ope2
Pl
1 pt
2 - p1
2
exp
64p102
+ +exp
-
2
log
2 - p1
+ log
2 - 2p1
by 14 Elog x
spe2
(-spi - p2/21)
exp
+ exxp
2
64p1o2
and
TP Pi.. > Beta (1,)) + pic/(4r1 +()
=P
Beta(an,s, E Beta BI, <
(01 + B1) a18
PIe
(a1 B1 + 8)8
4r
when s> 2i4+el
Pıe
P
Beta(aa,,, B1.0) Betalar,, B1,0) <
2(4+ + c)
p¹c
< exp
18(4 + <) [(4+e) 4ple|
where we use the result Theorem of Skorski (2023): if 01,s 2 B1.5. we have
IP
Beta(o B1,s) - E Beta BeBaaaaa.a (a1,,) B1,0) < 2(4 c)
(a1.. + 21,0)((a1,) + .1.0 +
PIE
< exp
2(4 +
31,5
PIE
(al + 81 + 8) (1 + a1 + 31 + s)
exp
2(4 + c)
2(a1 (3: +
BI,s)
3
PI6
< exp
2(4 + E)
2( + ( + 8/2)
by b1
< exp
18(4 4 + c)²
59

---

Zero-Inflated Bandits
and if 01, 01 we have
P
B 31,a)
E (e <
PIc
2(4 +
pff2
11,
2(3 -11,5)
P1
S exp
8(4 + <)²
(01,s + (1,5) (a1,s . + 11,55 1)
3(01,s + +1,,s) + 31,s + 2) 2(4 + 6)
(01 + B1,,) (81 + B1,a)
2(8 104-01+ + +
B1,,)
P16
-1
exp
8(4+ + c)²
(ai + $1 + s) () + 01 + B1 + +s
3(a1 + 31 + s) 01 + 81 + 5)
(al + 8/2) +//2)
pie(BI a1)
S exp
8(4+ c)²
s3
3(4 + E)S²
pfc²
99s2
P16
exp
8(4 + e)²
153
3(4 + E)8²
pie²
$ exp
18(4+ + c) [(4 + c) + 4p1c]
By plugging these inequalities into (H.18), we obtain
P > r1 - E1.s)
64pio2 ) + exp ( spi (1))/)))
spe²
p3e²
21
2 exp
2 exp
18(4 + <) [4 + 4p1c 8
On the other hand, the probability of E,, can be directly bounded through the concentrations for Gaussian and Binomial distribution
P(E = P x pi > r1 e/2))
+ +P(pI > Pl.s + +pie/(Ari + +0)]
21 1 PP 14 > M1, + c/(2p1))
sca
2
2 1 - exp
8pf02
- exp
(4 + e)2
by the facts that
3Ea
IP (MI > Pr.o + e/(2p)) = PP (1(11 Di. > e/(21) s exx
8pfo2
and
( 2spic²
IP (pi Pi,s + pie//Arri + +5) = -P -P(pi -i.s > pie/(4ri +6) S exp
(4ri + e)²
Note that p (1/2, 1), we have exp
(-
spe? 64p1o7
exp (-sp1 (1 p1/2)), exp
( (-1(4+00(4400)444p)
spie²
eepp
88p302 ) and
sc²
exp
[dri+e)z
2² are all less than exp
(-(==e)(2vvo55)
spēo²
Then, by combining the inequalities for P(T1,N 1, > 1i EI,,
and P(E,.)) we have
P(T1, > ri - -1.,)E)))
spie² 2
2 2 (A+ 02)
1 1122spp
spfe² 2 (-(++e)(1Voo))
exp
(4+ (1 V 02)
2exp
2exp
spic²
>
1 3exp
(T(+o)>(1 (V
60

---

Zero-Inflated Bandits
Thus, we take L >
(2vo) pff
log(3(1 - 1/v2) "), it will yield
-1)]
]
E
< E
(),(())
P(T1. > -E 1 P(E),s) )(1,5))(EE,
T
spic²
-2
- exp
- (Ta++ep(1 v2
==
by (1-3z)~² 11 x< 1/3-1/(3/2)
condition
spic² 2
12
exp
(4+c)((
spic2
Lpfe² (T(+t)((1vo2)
< 12
exp
ds + 12exp
L
Lpfez
(4+ (1+
= 12 e2exp
1
(4
p²e (4+ (4+c)(1V03)
the condition for L
1(1-1//2) [1+
pfc²
The above inequality together inequality (H.17) implies (H.5) immediately. Therefore, obtain the last term in (H.4) is bounded by
11)
4 A Pi
A
GI.(An/22)
by 22E22
T
PIYPE
K
and therefore,
T
E
Gi.((a//2- -11
AWEEC(T) < D + A&E
Σ
1(A = k. E((U))
A
k==++1
P
Ak
A
1
T
A
K
PVVT
Ps
PIvPPk
K
A
T
Pk
PI
K
By substituting the above inequality and (H.3) back into (H.1), we obtain the result stated in the theorem.
I. Proof of Regret Bounds for Contextual Bandit Algorithms
Let V = Z,Z, and U, Et= W.W. be the sample variance for the non-zero part and binary part at round respectively. The proof for contextual bandits is divided into three main steps after decomposing the regret into two periods.
The first step is to find the minimal round т such that the minimal eigenvalue of V, and U, satisfies min(dmin (V+), Amin (U.)) 2 1 for any / 2 - with high probability, which bounds the regret in the first periods. The second step uses the norm-norda martingale result to bound the regret from to rounds. The final step combines the regret over both periods.
Proof. Step 0: We start with decomposing the regret. Assume A the optimal action at round i, and let Z; == vx (Xe,, AT)
61

---

Bandits
and PA. 1(vy((x, (xe, A)) then
T
R(T) = Σ PA: z2) - -PA.9(B* zi)
T
Σ |PA:0(3-T22 2,) PA. 2;}
+ Σ
[a: z;) -PA.0(3, Zi)
(1.1)
1
$ (2Lg + g(0)
Σ (p::((8 z2) pA. z,)
where the last inequality is by
PA Z3) PA.9(0
[PA:0(8- zi) -DA;9(B zi) (aa:((3 -DA.0(3
by Assumption (i))
Lig Br | Z -3- -z +
1 Z: - 0 + +0(00) (pn: - pai)}
S
Lg || 1 Zz 13 + Lg | 2 +0(0)
(PA: (P:)
PAz)}
1=1
Assumption C.I (i)
S
[2L, + r(0)]r
and E N will be determined later.
For each arm & [K], let (a(m) = En - Z, Z,,, is the sample variance for the non-zero part and (a(m) == {t E [m] Ye,+ = 1} of the arm & with pulling it m times.
Step 1: Let Σ, = = and Q2 B F. We be the variance matrices for the i.idd sample (x,, and "x,, respectively. Note (m(m) has the same distribution with
(mm))
Σ
Zr
due to X, is independent with Y, for any fixed E [m]] Then by applying Proposition in et al. (2017), for any å E (0, 1)
there exist positive, universal constants Cj and C2 such that
Amin (Vu(m)) 2
with probability at least - 8, as long
Cavlog/)))))
2
(e(m)= 2
+ Amiu (Ex)
Aunin Ex))
Note that (m) is the summation of independent Bernoull((p..)) variables with pr,t 2 pa we have Bg(m) mp./2 with probability at least 1 1- ö whenever m 2 4p." by Hoeffding's inequality.
Similarly, we also apply Proposition 1 in Li et al. (2017) for (a(m) = Em Wi. T tuk. and know that there exist some universal C3, C2 constants such that Amin (U&(m)) 2 1 whenever
C3v4 + Ca Covlog(118) (1/))
2
>
+ Amin (S
Amin (Se))
62

---

Pafo-tefleeed Bandits
Now, by noticing Assumption C.2 (ii), let
2 p
(Civd+ C21 C 108(1/0))
2
2
4 (og(1/0) / [CSV + C4 (oo(l//))))
2
2
Th max
+
Amia (xss)
Amin (xb)
p²
)
mmin (Stz)
then have
min (Ve(n)) Amin (Ux(()))))))) 21
with probability at least 36.
Step 2.1 Define
Vn Σ Vu(ms) + La KE[K]
with n is the round such that for arm pulled my times. Then from Step and the fact that r = maxke[K] The by Assumption
C.2 (ii), we know that for any n 2 ++ 1, the minimal eigenvalue of Vn and Un satisfies
Amin (Vn) 2 1 1 Av.
and
Amin (Un) 2 1 + Au
with probability at least - 36. Next, since V++1 V, + Y, Z,Z,
det Ve+1 = det V, x del (I. + Y, V 1/2 Z,2, V
which furthermore implies
log det V log
det V
II
(1+ Zz, 12 :)
t=++1Y==1
T
= log det V +
Σ
log 1 11+12
t=++1y=:
T
2 log det V , +
1Z1 :) 1
Σ
(I
I
log det V,
Σ
7 2
2
1
where the last step is due to |Z:112 I and Amin (V)) > 1 for 2 r + 1. Therefore, we conclude that
by Cauchy
det VT
Ldll,
T
Σ 1=++
1Z S V log det V,
(1.2)
Note that by the inequality of arithmetic and geometric means,
det V < tr (t((V))
- +T
and the fact that
tr(V,) < Av - and det V, 2 (1+ Av)
Our inequality (I.2) can be furthermore bounded by
det VT
+I
Σ
Izllyy S 2T log det V,
< 2Tdlog
(1.3)
d(1+
63

---

Zero-Inflated Bandits
Similarly, have
T
Ay +T q(1 + Au)
Σ IWelo,,+ S V 2
(1.4)
as Y, would always be observed, which is specific case above.
Step 2.2 Let xx,( = Ei-mn [z 3) - I 1(, 3r Ze. By Assumption C.1 (iii,, we have
|| (3) 2 131 321
(I.5)
for any B r (3 1111 --0-11122 1}. Next, note that 3g directly comes solving Ei=1y== []] Zt 0, then
V (3,)
Σ
(g(
9 Ze
RE
Σ
(Z, 31) 9( 3r) Ze
- - g(Z
&E +=
2E|T):;=1
Σ
[ (Z) 3r) Z Σ
E
RE
RE|t)-YE=1
Note that Ee Fe-1 ~ sab directly implies Et o =l:sE [4]] nF ~ subG(o?). Let
(VT
V Wx, (3),(33)ll
Σ
0 e, - = max Mx,((v), veR*
max VER"
202
RE
then Mx,(vv) == (v) du(vv is also an IFadapted non-negative super-martingale with initial value for any probability measure u(v) on Rd. Thus, by Theorem 3.9 in Lattimore & Szepesvári (2020), we have
E.Mx,o
IP( (uuup M xv.(v) 2 1/0) tEN
1/8
for the probability measure y = NO0 IT). Plugging in the explicit formula for M (v., we obtain that
P 3t :
1
I [x,x 2 log(1/8) + log X
det V, 8
))
(L.6)
20
for any Ao > and E (0, 1). Combining inequality (I.5) and (I.6), we conclude that
det Ve
|| - B3 S Kig 20 llog11/)) + log
s Kg (l/() + d + A t/2t/d) = Pxx
holds with probability at least 8 for any & 2 r + 1, where the last inequality is due to
det
V
d
1 {e [4] Yv [Y=1)] Avd
11 d
< 1 Ayd
tr
<
X
Avd
By using the similar argument, we can also show that
00 0- S K V 4log(11/8) + glog(1 + \7 = PY.
holds with probability at least 8 for any t N T +
Step 2.3 The design of Algorithm C.2 for choosing A, [K] ensures
B. z + px. 12 ll, S 3, Z, + -x..
64

---

Zero-Inflated Bandits
ie.,
( Z.) px,
Px ( (IZellv, || v))
and
0. W + PY, w. S W + /
ie..
0. (W7 W.) s pn -
Apply the last two inequalities in Step 2.2, we obtain
(z - Z.) 3r (z Z.) (Z - -z.) - - -3)
$ px,t (IZzlll.' - || 1) +112; - -ell Zellv,=1183 - 1a1
by the choose of px.1 and T
px Zz |l. - || + +112; Zellv.1)
2 v.
with probability at least 1 - 48 for any 2 + 1. Similarly, by applying the same technique for (W; WW)T 0", obtain that
-Z) 3r < 2px ZZ:ll,
and (W; - (.) o s 2py Well,,
(1.7)
both hold with probability at least 56 for any t ++
Step 3: Now, with the inequality (1.7), we could deal with the remaining part in (I.1) in Step 0. By following the same (3, z;) s [2L. + g(0)]r, we have
technique for proving (
T
Σ
|a:9(3 zj) - PA.9(3 Z,)
(=r+1
T
by Assumption
Σ
(B -BaTzz) + | Z. 0/ -kk-0 Ln
w; To o
t=
by (L.7)
24g
Σ
px, px,el| Zoll. + +( + L(
Σ
pY Wello,
t=T+1
(=
T Izlll, + L(0))
<2L.XXTT
1=
(=++1
(1.3) and (1.)
Av +
5
2x -1 Lg v 4log(110) + dlog(1 + xy T/))
2T
g
d(1+Av)
Au + q(1 + Au))
+ 2k (L, Ll 4log(1/0) + gloog11 + Ao t//t 2T
which completes the regret bound for our UCB algorithm. The regret bound for the TS algorithm follows similarly, leveraging the anti-concentration result in (C.2) along with the proof techniques in Theorem 1 of Agrawal & Goyal (2013).
Specifically, it incorporates anti-concentration results for (B. - -3.)(z Z.) and (0, 0.) W.).
65


Reviews:
[{"review_id": "z9edpj2s7z", "reviewer": "Reviewer_TjeF", "summary": "This paper considers a multi-armed bandit setting, where reward distributions are contaminated with a zero point mass with weight $p$. To accommodate this special reward structure, which returns rewards of 0 with probability $1-p$, and rewards distributed according to an arm-specific sub-Weibull distribution otherwise. The authors leverage a product trick, which uses a union bound over the uncertainty in parameter $p$ and the mean of the nonzero distribution to obtain product confidence intervals, which underlie the modified UCB and Thompson Sampling algorithms proposed in their work. The authors provide theoretical results that show their approach achieves known minimax lower bounds, and their empirical results demonstrate the benefits of their approach on both synthetic and real-world data.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n*Claims & Evidence:*\n\nWhile 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.\n\n*Methods & Evaluation:*\n\nWe tested our approach with bounded, skewed Beta rewards ([anonymous figure](https://anonymous.4open.science/r/ZIB_ICML-2535/MAB_for_Beta.pdf)) 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](https://anonymous.4open.science/r/ZIB_ICML-2535/MAB_for_large_p.pdf)), our approach remains strong under Gaussian and Exponential components. We will add these experiments to the appendix.\n\n*Experimental Designs & Analyses:*\n\nWe 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.\n\n*Weakness 1:*\n\nOur 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.\n\n*Weakness 2:*\n\nAs 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.\n\n*Other Comments & Suggestions:*\n\nWe 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.\n\nFor instance, consider a reward model of the form\n$$\n         (Y_1, \\ldots, Y_m) \\sim \\operatorname{Multi} (1; p_1, \\ldots, p_m), \\qquad R = \\sum_{j = 1}^m X_j Y_j,\n$$\nwhere 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\n$$\nP(S_n - n r > t) \\leq P (S_n - nr \\geq t, V_n \\leq v) + P (V_n > v),\n$$\nwhere $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\n$$\n         V =\\sum_{j = 1}^m p_j E [X_j]^2 - \\bigg( \\sum_{j = 1}^m p_j E [X_j] \\bigg)^2.\n$$\nThis 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.\n\n*References:*\n\n[1] Lattimore, T., & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.\n\n[2] Ren, H., & Zhang, C. H. (2024). On Lai’s Upper Confidence Bound in Multi-Armed Bandits. arXiv preprint arXiv:2410.02279.", "claims_and_evidence": "All claims and proofs are well supported, although the regret rates could be discussed more cleanly with respect to existing work. \n\nFor example, as long as the mixed distribution satisfies some subgaussian (or sub-Weibull) property, then minimax regret rates will be attained by specifying the correct subgaussian (or sub-Weibull) factor. The main gain (at least in terms of order optimality of regret) is only in the heavy-tailed case, which could be emphasized more cleanly.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria (for both the synthetic example and real-world experiment) evaluate the proposed method. \n\nOne interesting case to see (at least from an empirical standpoint) would be bounded rewards (rather than just sub-gaussian reward distributions), which often occurs in practice. It may be the case that modeling the nonzero distribution may be most beneficial when the nonzero distribution component is skewed far away from zero. \n\nIt could also be interesting to test larger values of $p$ - this setting could also be adversarial to the benefits of this approach.", "theoretical_claims": "Proofs were briefly skimmed, but not evaluated in detail.", "experimental_designs_or_analyses": "The experiments do correspond closely with the claims of the authors, and capture the multiple nonzero reward generating distributions that may be contaminated with a zero point mass.\n\nIt would be helpful to have higher simulation numbers - 50 and 25 simulations for figures 2 and 3 seems somewhat smaller than expected. Likewise, it would be helpful to get better intuition on why this approach works well for synthetic data, and works relatively worse on the real world data.", "relation_to_broader_scientific_literature": "The key results of this paper lies in its practical relevance - zero-inflated distributions are very common in settings such as digital advertisement. While this paper does not introduce novel tools, it provides a practical, simple solution for a setting that occurs in many practically relevant scenarios where bandits are applied.", "essential_references_not_discussed": "All relevant references seem to be present in this work.", "other_strengths_and_weaknesses": "We summarize the strengths and weaknesses of this paper below:\n\n** Strengths **\n* Most importantly, this work considers a common setup that occurs in practice, across many different fields. Zero-inflated distributions for arm rewards is a practically relevant setting to study.\n* The authors offer a simple, computationally lightweight solution to this setup that requires little modifications to existing bandit algorithms. \n* The method appears to perform empirically well, especially for heavy-tailed distributions.\n\n** Weaknesses ** \n* For heavy-tailed distributions contaminated with a zero point mass, those distributions are no longer so heavy-tailed. It is unclear whether the modeling of zero inflation or a poorly specified scale factor is the cause of increased performance.\n* The authors rely on a union bound, which is sufficient for order optimal regret. One wonders if there could be a better way to split the confidence (even if union bounding) than $\\alpha/2$, or to avoid wasteful union bounds all-together.", "other_comments_or_suggestions": "There seems to be a reference error in Line 176 of the manuscript (end of Section 2.1).", "questions_for_authors": "Beyond zero inflation, are there other reward models that are best captured with this hierarchical approach? The product method for constructing confidence intervals appears to be a general approach for more complicated reward generation (i.e., we don't necessarily need to fix one distribution to be Bernoulli). Are there other settings where this could be done?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "myJiP9VH8W", "reviewer": "Reviewer_ZEJa", "summary": "The submission studies multi-armed bandits whose reward function follows the zero-inflated (ZI) distribution. The motivation is to investigate the advantages of distribution modeling and exploiting the problem specific structure. UCB and TS are modified to solve the MAB and the contextual bandit problems under the zero-inflated regime. The corresponding regret bounds and experimental verifications are provided.\n\n\n## Update after rebuttal\n\nThe authors' reply addressed my concerns. Given that, I have revised my recommendation to weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n*Theoretical Claims:*\n\nOur 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.\n\n*Experimental Designs & Analyses:*\n\n- 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.\n\n- 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.\n\n- 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.\nWe have also added two uploaded anonymous figures ([Figure 1](https://anonymous.4open.science/r/ZIB_ICML-2535/size_ratio_1.pdf) and [Figure 2](https://anonymous.4open.science/r/ZIB_ICML-2535/size_ratio_2.pdf)) to illustrate how large variance-to-mean ratios may briefly favor alternative baselines but ultimately highlight the value of stable ZI modeling.\n\n*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.\n\n*Weaknesses:*\n\n- 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.\n\n- 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. \n\n- 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.\n\n- 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.\n\n- 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.\n\nReferences:\n\n[1] Lattimore, T., & Szepesvári, C. (2020). Bandit Algorithms.\n\n[2] Zhou, P., Wei, H., & Zhang, H. (2024). Selective Reviews of Bandit Problems in AI via a Statistical View.\n\n[3] Kwon, J., Perchet, V., & Vernade, C. (2017). Sparse Stochastic Bandits. \n\n[4] Tsuchiya, T., Ito, S., & Honda, J. (2023). Stability-Penalty-Adaptive FTRL: Sparsity, Game-Dependency, and Best-of-Both-Worlds. \n\n[5] Yun, H., & Park, B. U. (2023). Exponential concentration for geometric-median-of-means.\n\n[6] Bubeck, S., Cesa-Bianchi, N., & Lugosi, G. (2013). Bandits with heavy tail. \n\n[7] Zhang, J., & Cutkosky, A. (2022). Parameter-free regret in high probability with heavy tails. \n\n[8] Cheng, D., Zhou, X., & Ji, B. (2024). Taming Heavy-Tailed Losses", "claims_and_evidence": "Theoretical claims are supported by proofs.\n\nExperimental claims have less support. See Experimental Designs Or Analyses for more comments.", "methods_and_evaluation_criteria": "The notion of regret is an appropriate evaluation criterion for the theoretical results.\n\nThe synthetic datasets and the real-world dataset are suitable for evaluating the ZI methods.", "theoretical_claims": "The submission provides matching regret bounds for the ZI methods. Due to the multiplicative nature of the reward function (equation (1)), the submission developed technical tools to facilitate the proof. These technical contributions are Lemmas E.2 [1391], E.3 [1480], E.4 [1502].\n\nHowever, if the motivation of this submission is to investigate the benefits of exploiting the ZI structure, then proving matching regret bounds is simply a sanity check on the proposed methods. Ideally, the proofs should show when and how the regret bounds are improved by considering the ZI structure. Unfortunately, these results are lacking.", "experimental_designs_or_analyses": "There is only one real-world dataset used to verify the proposed method. However, in Introduction, there are other practical scenarios that can be used to verify the proposed methods [054R–081L]. In addition, the baselines in the real-world experiment are UCB and TS, which are developed for MAB. Instead, appropriate baselines should be the contextual bandit algorithms.\n\nOne motivation for proposing the ZI model is to deal with sparse reward signals. Baselines aimed at tackling sparse rewards should be included in the synthetic experiments. Related papers are https://arxiv.org/abs/1706.01383 and https://proceedings.neurips.cc/paper_files/paper/2023/hash/9408564a4229f4a933ac9bd09a29ee96-Abstract-Conference.html. Moreover, the proposed method does not always perform the best in figures 5 [1032] and 7 [1131]. The pros and cons of the proposed method are not discussed in the main text.", "relation_to_broader_scientific_literature": "The developed algorithms and the technical contributions provide bandit solutions for the ZI regime. It is, however, unclear if the technique of this submission can be generalized to other regimes.", "essential_references_not_discussed": "Literature with sparse rewards should be included as a part of related work. Related papers are https://arxiv.org/abs/1706.01383 and https://proceedings.neurips.cc/paper_files/paper/2023/hash/9408564a4229f4a933ac9bd09a29ee96-Abstract-Conference.html.", "other_strengths_and_weaknesses": "Weaknesses\n\nThe submission did not justify the rationale for the ZI model [118L]. Why is ZI a good model for sparse rewards while the others are not? What is the intuition behind $X$ and $Y$? Why does $X$ have to be defined by $\\mu$ and $\\epsilon$? Can’t $X$ just be a distribution? Why is $\\epsilon$ restricted to sub-Weibull, sub-Gaussian, and heavy-tailed only?\n\nThere is no discussion of the applicability of ZI in realistic scenarios (applications are mentioned in Introduction, but it is difficult for a reader to connect the applications to the modeling part [110L–140L]).\n\nWhat is the feedback signal? There are X, Y, R in the main text [110L–140L], but only R and Y in the algorithm.\n\nThere are unreferenced pointers ([177R] and [1254]).", "other_comments_or_suggestions": "Please see the comments in the above parts.", "questions_for_authors": "Please see the questions in the above parts.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VFw1GLxpLM", "reviewer": "Reviewer_5ywx", "summary": "This paper “Zero-Inflated Bandits” focuses on the issue of sparse rewards in multi-armed bandit (MAB) and contextual bandit applications. The authors propose a zero-inflated bandit (ZIB) algorithm framework to enhance learning efficiency by leveraging the zero-inflated distribution structure.For zero-inflated multi-armed bandits, the paper presents a model that characterizes the reward distribution with parameters such as non - zero probability \\(p_{k}\\) and mean of the non - zero part \\(\\mu_{k}\\). To address the shortcomings of naive approaches, the product method is introduced to construct more effective upper confidence bounds (UCB). The Thompson Sampling (TS) approach is also extended for this model. In the context of zero-inflated contextual bandits, the model is further extended, and UCB and TS algorithm templates are proposed. These algorithms construct confidence bounds for exploration and estimate parameters to optimize decisions.Theoretical analysis of the regret bounds for UCB and TS algorithms in both MAB and contextual bandits is conducted. Extensive experiments, including simulations in MAB and contextual bandits and a real - data application, demonstrate that the proposed UCB and TS algorithms consistently achieve lower sub - linear regrets, outperforming baseline methods that ignore the zero-inflated structure or directly quantify uncertainty.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and constructive feedback. Below, we respond to each of your points. We hope this addresses your concerns.\n\n*Claims & Evidence:* \n\nOur 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.\n\n*Methods & Evaluation Criteria:*\n\nWe 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.\n\n*Theoretical Claims:*\n\nThank 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.\n\n*Experimental Designs & Analyses:*\n\nFollowing your advice, we included Q-SAR [6] for MAB and SPUCB [7] for GLM as baselines in two uploaded anonymous figures ([Figure 1](https://anonymous.4open.science/r/ZIB_ICML-2535/MAB_extra_QSAR.pdf) and [Figure 2](https://anonymous.4open.science/r/ZIB_ICML-2535/GLM_CB_extra.pdf)). 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.\n\nWe 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](https://anonymous.4open.science/r/ZIB_ICML-2535/AB_testing_new.pdf). 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.\n\n*Supplementary Material & Essential References Not Discussed:*\n\nWe 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.\n\n*Questions:*\n\nDetermining 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.\n\nReferences:\n\n[1] Bubeck, S., Cesa-Bianchi, N., & Lugosi, G. (2013). Bandits with heavy tail.\n\n[2] Zhang, J., & Cutkosky, A. (2022). Parameter-free regret in high probability with heavy tails. \n\n[3] Cheng, D., Zhou, X., & Ji, B. (2024). Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting. \n\n[4] Zhang, M., \\& Ong, C. S. (2021). Quantile bandits for best arms identification. \n\n[5] Shi, Z., Kuruoglu, E. E., & Wei, X. (2022). Thompson Sampling on Asymmetric Stable Bandits. \n\n[6] Zhang, M., & Ong, C. S. (2021). Quantile bandits for best arms identification. \n\n[7] Peng, Y., Xie, M., Liu, J., Meng, X., Li, N., Yang, C., … & Jin, R. (2019, August). A practical semi-parametric contextual bandit. \n\n[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. \n\n[9] Trapani, L. (2016). Testing for (in)finite moments.\n\n[10] Zhang, H., Wei, H., & Cheng, G. (2023). Tight non-asymptotic inference via sub-Gaussian intrinsic moment norm.", "claims_and_evidence": "The independence assumptions in the TS algorithm proofs are too strong. In reality, factors affecting rewards are often interrelated. I suggest the authors list all assumptions in a dedicated section, discuss their implications, justifications, and potential consequences of violation to enhance the research's transparency.", "methods_and_evaluation_criteria": "The paper's omission of analyzing the time and space complexity of the proposed algorithms is a weakness. Understanding the computational resources required by these algorithms is crucial for practical applications, especially in large - scale and real - time scenarios. Without such analysis, it's hard to assess the algorithms' scalability and efficiency. I recommend the authors conduct and report this analysis.", "theoretical_claims": "The paper briefly mentions the link to heavy tail and long tail bandit research. Since zero-inflated distributions can be a special case of heavy tail distributions, a more in - depth discussion is needed. This should cover how the proposed algorithms relate to existing ones in these areas and how the distributions' properties interact.", "experimental_designs_or_analyses": "(a) There is an absence of comparison with heavy tail and long tail bandit algorithms in experiments. Given the relevance, such comparisons are crucial to assess the proposed algorithms' performance comprehensively. (b) The absence of comparisons with semi-parametric bandit algorithms in the experiments is a significant oversight. Given the relevance of semi-parametric bandit research to the topic of this paper, such comparisons are essential for a comprehensive evaluation of the proposed algorithms. (c) if the author could conduct a real online AB testing for the method, it would be better because the real environment will break assumptions normally.", "relation_to_broader_scientific_literature": "Focusing on zero-inflated bandits is valuable for real - world applications with sparse rewards, and the proposed algorithms can enhance learning efficiency.", "essential_references_not_discussed": "There are some citation omissions. The work by Peng Y, et al. titled \"A practical semi-parametric contextual bandit\" presented at IJCAI in 2019 should be included in the references. This paper likely contributes to the semi-parametric bandit literature and its omission undermines the comprehensiveness of the paper's literature review. Another is Liu X, et al. Thompson sampling for zero-inflated count outcomes with an application to the Drink Less mobile health study, which is very related to this work.", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "How can one pre-determine whether the current environment is long-tailed or zero-inflated before utilization?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}, {"review_id": "lsvPASMPPe", "reviewer": "Reviewer_AjGD", "summary": "This paper considers stochastic multi-armed and contextual bandits where the reward distributions are zero-inflated distributions. Formally, each reward observation is a draw of a product random variable $R_t = X_tY_t$ where $X_t$ is a distribution with mean $\\mu$ and $Y_t$ is a Bernoulli distribution with parameter $p$. It is assumed that $\\mu$ and $p$ are unknown and both may vary across arms.\n\nThe paper proposes UCB and TS algorithms for various versions of these problems, with accompanying theoretical and empirical analysis. \n\nThe main innovation in the design of UCB and TS algorithms is to not form a single confidence bound for $p\\mu$ the expected value of $R_t$, or draw a single TS sample from it, but to form separate indices for $\\mu$ and $p$ and combine these, since a quantities based on the entire zero-inflated distribution may scale unnecessarily in $\\mu$. The more substantial challenge lies in the analysis, where handling a random number of observations of the non-zero component presents additional complications over the standard analysis used in parametric bandit proofs.\n\n# POST REBUTTAL: Satisfied with proposed modifications and retain a positive score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n*Theoretical Claims:*\n\nWe 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.\n\nWe 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. \n\n*Experimental Designs & Analyses:*\n\nAll 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.\n\nTo improve reproducibility, we will explicitly detail our reward models:\n\n- Gaussian: Nonzero parts from a $N(\\mu_k, 1)$, with $\\mu_k \\sim U(0, 100)$;\n\n- Mixed Gaussian rewards: The non-zero rewards from\n$$\n(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)\n$$\nwhich ensures that the overall mean of the non-zero component is $\\mu_k$.\n\n- Exponential: The non-zero rewards from an exponential distribution with mean $\\mu_k$, where $\\mu_k \\sim U(0, 100)$.\n\nWe will include these details in Section 5 and Appendix C of our revised submission.\n\n*Relation To Broader Scientific Literature:*\n\nThank 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.\n\n*Other Comments & Suggestions:*\n\n- L038: We will include the specific reference to Chapter 9 in [1], consistent with the other citations in the manuscript.\n\n- 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.\n\n-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.\n\n- R238: The ``less than or equal to\" symbol ($\\lesssim$) is used to indicate inequality up to constants independent of bandit specific parameters.\n\n- 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.\n\nWe 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.\n\n*Question:*\n\nWe 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.\n\nFigure 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.\n\n*References:*\n\n[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.\n\n[2] Lattimore, T., & Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I could not read the entirety of the supplementary material in the time available, but I checked the results leading to Lemma 2.2 in detail and did not find issues. I did however feel that the theoretical contribution could be better explained in the main text:\n\n-\tCan you give a more detailed sense of how Lemma 2.2 and A.1 resolve the issues of handling the distribution of X in the main text? It seems this is one of the main contributions, and while we get a good sense of the challenge, and the fact that these lemmas resolve it, there isn’t a good sense of how within the main text.\n-\tSimilarly in Section 4.2, it’s hard to tell whether there is novelty in the proofs that are seconded to appendix, and if so how much. I think it would help readers to understand the theoretical contribution if this could be concisely expressed in the main text.", "experimental_designs_or_analyses": "I felt the experiments were appropriate, and checked the specification in Appendix C, but had some observations about the presentation of results:\n\n-\tThere doesn’t appear to be an explanation of what the figures are showing in the Experiment section. Are the plotted lines means or medians, are the vertical lines plus/minus standard deviations, or quantiles, or max/mins? Why do some curves appear not to have error bars at all?\n-\tThere are elements of the experimental setup that are unclear. E.g. for the MAB problems, what are the parameters of the Gaussian/Mixed Gaussian/Exponential components, I could only find details of p.", "relation_to_broader_scientific_literature": "I felt this was mostly done appropriately, it seems that \n\n-\tLiu et al. (2023, arxiv:2311.14349) Thompson sampling for zero-inflated count outcomes with an application to the Drink Less mobile health study.\n\nis worth mentioning but it was the only other relevant paper on zero-inflation in bandits I could find.", "essential_references_not_discussed": "See above.", "other_strengths_and_weaknesses": "The paper provides a thorough treatment of the zero-inflated bandit problem, covering MAB and contextual problems, TS and UCB-based approaches, and problem-dependent and problem-independent results. The experiments are sensible to evaluate these algorithms and the work is well motivated and connected to the literature and potential avenues for future work. Aspects of the theoretical and methodological contribution may indeed be translations of existing tools to this new setting, but I think there is sufficient innovation here to interest an ICML audience.", "other_comments_or_suggestions": "Minor observations: \n-\tL038: a chapter or page reference to Lattimore and Szepesvari would be helpful here, as done on L068 and L430.\n-\tL154: clarify the context in which it is commonly assumed – I presume this means in design and analysis of bandit algorithms (but the rest of the paragraph was about defining sub-Weibulls so it’s not the clearest).\n-\tL177: Error with the reference to Corollary “??”\n-\tA lot of equations are squashed into in-line text, presumably to save vertical space in the 8 page template. I’d recommend using some of the post-acceptance additional allowance to remedy this so things are easier to read, especially on pages 4 and 5.\n-\tL238: I’m not sure the less than equal to notation used in Theorem 4.1 is defined?\n\n\nA proof read for grammar would improve the readability of the paper, e.g.:\n-\tL048: distributions*\n-\tL076: follow*\n-\tL078: games*\n-\tL115: follow*\n-\tL146: prone to be heavily influenced by their estimation errors*\n-\tL234-5: We note*\n-\tL230: established used as an adjective here suggests they already exist and or not a new contribution, I think you mean that you establish these results in this paper?", "questions_for_authors": "Mostly repeating questions from above for ease of reference:\n\n-\tSections 1 and 2 refer to Figure 1 (a) and (b) but without a full explanation of what the figures show. For instance, it’s not clear how 1 (a) provides an example of bandit algorithms failing to utilize the distribution property, and how the confidence bounds in 1 (b) are constructed. Could this be rectified?\n-\tCan you give a more detailed sense of how Lemma 2.2 and A.1 resolve the issues of handling the distribution of X in the main text? It seems this is one of the main contributions, and while we get a good sense of the challenge, and the fact that these lemmas resolve it, there isn’t a good sense of how within the main text.\n-\tSimilarly in Section 4.2, it’s hard to tell whether there is novelty in the proofs that are seconded to appendix, and if so how much. I think it would help readers to understand the theoretical contribution if this could be concisely expressed in the main text.\n-\tThere doesn’t appear to be an explanation of what the figures are showing in the Experiment section. Are the plotted lines means or medians, are the vertical lines plus/minus standard deviations, or quantiles, or max/mins? Why do some curves appear not to have error bars at all?\n-\tThere are elements of the experimental setup that are unclear. E.g. for the MAB problems, what are the parameters of the Gaussian/Mixed Gaussian/Exponential components, I could only find details of p.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper discusses a variant of bandit problems where zero-reward appears with high probability and the nonzero part follows some sub-Weibull distributions. UCB-based and Thompson-Sampling-based algorithms are proposed with some regret bounds. For this paper the reviewers agreed in the opinion that the formulation of the paper is well-motivated and the algorithms are supported by good theoretical and empirical results. On the other hand, many concerns have been raised by the reviewers. In particular, the concern on the substantial benefit of considering the zero-inflated setting is shared between the reviewers, which I also agree. Though these concerns seem to be largely solved by the rebuttal, I expect that the authors thoroughly address theses concerns in the final version.
Decision: Accept (poster)