Zero-Inflated Bandits

Zero-Inflated Bandits

\twocolumn[ \icmltitle{Zero-Inflated Bandits } \icmlsetsymbol{equal}{*}

\icmlaffiliation{to1}{Amazon. This work does not relate to the positions at Amazon } \icmlaffiliation{to3}{Department of Economics, University of California San Diego}

\icmlcorrespondingauthor{Haoyu Wei}{[email removed]}

\icmlkeywords{Machine Learning, ICML}

\vskip 0.3in ] \printAffiliationsAndNotice{\icmlEqualContribution}

Introduction

Bandit algorithms have been widely applied in areas such as clinical trials durand2018contextual, finance shen2015portfolio, recommendation systems zhou2017large, among others. Accurate uncertainty quantification is key to addressing the exploration-exploitation trade-off and typically requires on certain reward distribution assumptions. Existing assumptions can be roughly classified into two groups:

As in many statistics and machine learning areas, using problem-specific structures to focus on a more detailed distribution family, if correctly specified, can improve the efficiency of estimation or uncertainty quantification. This leads to lower regrets in bandits. However, as discussed above, compared to the vast statistical literature on univariate 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 following a certain distribution. Similar structures exist in broad applications, including mobile health ling2019quantile and freemium game yu2021online. While some standard bandit algorithms can still be applied, they fail to utilize the distribution property and hence can be less efficient. See Figure (ref) for a real example.

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 problem-specific structure, our algorithm is more efficient than the existing ones via more accurate uncertainty quantification. We illustrate this with Figure (ref), 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 a wide range of reward distributions, including the sub-Weibull distribution and even more heavy-tailed distributions (with moments exceeding one). { Second, we theoretically derive the regret bounds for our UCB and TS algorithms in multi-armed bandits (MAB) under weak reward distribution 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 summary is provided in Table (ref). To our knowledge, this is the first finite-sample concentration analysis of 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 bandits literature with parametric or nonparametric reward distributions discussed above, our paper is also related to a few areas. First, there is research on semiparametric bandits krishnamurthy2018semiparametric,kim2019contextual,ou2019semi,choi2023semi. However, these works focus on addressing the misspecification of the regression function within the context of contextual bandits. This focus is orthogonal to our objectives. Second, the zero-inflated distribution can also be regarded as a special case of hierarchical distributions. In recent years, there is growing interest in leveraging hierarchical models in bandits hong2022hierarchical, wan2021metadata, wan2023towards. 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 assumption, besides relying on nonparametric distribution families, one may also consider bootstrap-based methods wan2023multiplier, kveton2019garbage. Nonetheless, on one hand, these methods still rely on certain restrictive distribution assumptions to ensure a regret guarantee; on the other hand, they fail to fully utilize the problem-specific structure, which may lead to compromised efficiency. Finally, while zero-inflated structures have been studied in offline settings (supervised/unsupervised learning) lambert1992zero, hall2000zero, cheung2002zero, to our knowledge, this work is the first formal study on this topic in bandits, which pose unique challenges from such as the finite-sample concentration bounds and regret rate analysis.

Zero-Inflated Multi-Armed Bandits

In this section, we use the MAB setting to outline our motivation and strategy. We will extend to contextual bandits in Section (ref).

Setup. For any positive integer $M$, we denote the set $\{1, \dots, M\}$ by $[M]$. We start our discussion with the MAB problem: on each round $t \in [T]$, the agent can choose an action $A_t \in \mathcal{A}$ with the action space $\mathcal{A} = [K]$, and then receive a random reward $R_t = r_{A_t} + \varepsilon_t$, where $r_k = \mathbb{E}[ R_t \mid A_t = k]$ is the mean reward of the $k$-th arm and $\varepsilon_t$ is the random error. The performance of a bandit algorithm is measured by the cumulative regret $\mathcal{R}(T) = \sum_{t=1}^T {\mathbb{E}} \big[ \max_{a \in \mathcal{A}} r_a - r_{A_t} \big]. $ We focus on applications where the reward is zero for a significant proportion of time, and propose to characterize the reward distribution by the following Zero-Inflated (ZI) model: $X_t = \mu_{A_t} + \varepsilon_t$, $Y_t \, \sim \, \operatorname{Bernoulli}(p_{A_t})$, and $R_t = 0 \times (1 - Y_t) + X_t \times Y_t.$ Here, for each arm $k$, we introduce two unknown parameters, the non-zero probability $p_k \in [0,1]$ and the mean of the non-zero part $\mu_k$ such that $r_k = \mu_k \times p_k$. Here $\varepsilon_t$ is a mean-zero random error term. {For any arm $k$, we assume $\mathbb{P}(X_t = 0) = 0$.} We note this assumption can always be satisfied: given a reward variable $R_t$, one can always define $Y_t = \mathds{1} (R_t \neq 0)$ and $X_t = \mathds{1} (R_t \neq 0) \times R_t$. Moreover, as such, it is natural to regard $Y_t$ as observable as well. In contrast, the value of $X_t$ is only observable when $Y_t \neq 0$ (equivalently, $R_t \neq 0$), and in this case it is equal to $R_t$. For simplicity of notations and without loss of generality, we assume $X_t \perp \!\!\! \perp Y_t$: even if $X_t \not\perp \!\!\! \perp Y_t$, we can re-define $\check{X}_t \mid Y_t = y$ to have the same distribution as $X_t \mid Y_t = 1$ for $y = 0, 1$. In this case, $\check{X}_t \perp \!\!\! \perp Y_t$, and the observable reward $R_t = X_t \times Y_t = \check{X}_t \times Y_t$; thus, we can simply replace $X_t$ with $\check{X}_t$. Finally, the conditional distribution of $R_t$ is a mixture of two distributions, one of which is a delta distribution on zero and the other is only required to satisfy minimal assumptions; while the assignment $Y_t$ is Bernoulli. For simplicity, we will occasionally omit the subscript $t$ when there is no ambiguity.

To simplify the exposition, we first focus on pulling a single arm and may omit the subscript $k$. We begin with considering scenarios where $\varepsilon_t$ exhibits relatively light tails. Specifically, we consider the sub-Weibull tail property, i.e., there exists $\theta > 0$ for which the moment generating function (MGF) of $|\varepsilon_t|^{\theta}$ is defined within an interval around zero. This sub-Weibull distribution family is very general zhang2020concentration,zhang2022sharper: for example, when $\theta = 1$ and $\theta = 2$, it reduces to the sub-exponential or sub-Gaussian family, respectively. Mathematically, we denote $\varepsilon_t \sim \operatorname{subW}(\theta; C)$ if the noise $\varepsilon_t$ satisfies $\mathbb{E} \exp ( |\varepsilon_t|^{\theta} / C^{\theta} ) \leq 2$, with $\theta > 0$ and $C > 0$ representing the tail and size parameter rinne2008weibull,vladimirova2020sub. It is commonly assumed that $\theta$ and $C$ are known wu2016conservative,lattimore2020bandit,wu2022residual,zhou2024selective.

We first note that the ZI structure retains the sub-Weibull tail behavior of the non-zero component $X_t - \mu$, as established in Lemma (ref).

Naive approaches and their limitations. With Lemma (ref), once the size parameter for $R_t$ is known (or estimated), we can construct an upper confidence bound for $r=\mu p$ using existing concentration inequalities for sub-Weibull variables $\{R_t\}$ zhang2020concentration,zhang2022sharper. The corresponding UCB algorithms then follows, which we refer to as naive approaches.

However, these approaches have two clear limitations. First, even when the true size parameter is known, without leveraging the zero-inflated structure, such an approach leads to a loose concentration bound and hence under-exploration. This can be seen in Figure (ref), our numerical study in terms of regret, and also our regret bound (e.g. Lemma (ref)). We can appreciate the intuition from the following fact: $\operatorname{var}(R_t) = \mathbb{E}_Y(\operatorname{var}(R_t|Y_t)) + \operatorname{var}_Y(\mathbb{E}(R_t|Y_t)) = p \operatorname{var}(X_t) + \mu^2 p(1-p)$. Therefore, if we directly apply a concentration bound with $R_t$, the width of the bound will roughly increase linearly with $\mu$. However, the noise level and the difficulty of estimating either $p$ or $\mu$ (and hence $r$) should not change only by shifting the non-zero distribution.

Second, in practice, estimating a valid size parameter $C_R$ for $r$ (hence having a valid upper confidence bound) is challenging, as the size parameter has complex dependency on $\mu$, $p$, $\theta$ and $C$. In real applications, there are a few common methods to choose $C_R$: (1) Use the size parameter of $X_t - \mu$; (2) use the variance of $R_t$ (estimated on the fly); (3) Use the definition to calculate $C_R$, with $\mu$ 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 (ref) (in Appendix (ref)) using sub-Gaussian distributions, which we summarize here: 1) $C_R$ can significantly exceed $C$, hence approach 1 is not valid; 2) $C_R$ can significantly exceed $\operatorname{var}(R_t)$, hence approach 2 is not valid; 3) $C_R$ is very sensitive to $(p, \mu, \sigma^2)$, and hence is prone to their estimation errors - specifically, the partial derivatives of $C_R$ with respect to these parameters can be arbitrary large within some regions.

Proposed product method and upper confidence bound approach

To address the shortcomings of the naive approaches, we introduce the product method, which leverages the product structure of the true reward $R_t = X_t \times Y_t$. Utilizing the corresponding concentration inequalities, we establish valid upper confidence bounds for $\mu$ using $\{X_t \}_{t = 1}^n$ and for $p$ using $\{Y_t \}_{t = 1}^n$, formulated as $ \mathbb{P} (\mu > \overline{X} + U_X) \leq \alpha / 2$ and $\mathbb{P} (p > \overline{Y} + U_Y) \leq \alpha / 2$. Here $U_X$ and $U_Y$ are known functions, and $\overline{X}$ and $\overline{Y}$ are the sample averages for $\{X_t \}_{t = 1}^n$ and $\{Y_t \}_{t = 1}^n$, respectively. Consequently,

which suggests $ (\overline{X} + U_X) (\overline{Y} + U_Y) $ is a valid upper confidence bound for $r = \mu \times p$.

Now, the key of establishing our method lies in determining sharp concentration bounds for both $p$ and $\mu$. For $p$, a standard concentration bound for Bernoulli variables can be applied, such as: $U_Y = \sqrt{{1}/{(2n)} \times \log \left( {2} / { \alpha}\right)}$. $\mu$, however, poses a challenge as $\overline{X}$ is not directly observable in our context; we only observe $X_t$ when $Y_t = 1$. We therefore define the average value of the observed $X_t$ as: $ \overline{X}^* := \frac{1}{\# \{t: Y_t = 1\}} \sum_{t: Y_t = 1} X_t. $ Let $B = \sum_{t = 1}^n Y_t$ represent the count of $X_t$ observations. While $B$ is a random variable, given any fixed $B$, the sub-Weibull concentration inequality still holds. For example, if $X_t$ is sub-Gaussian (i.e., $\theta = 2$) with a variance proxy $\sigma^2$, then $\mathbb{P} \big( \mu - \overline{X}^* > {\sqrt{{2 \sigma^2 } / {B}} \log \left( {2} / {\alpha}\right)} \big) = \mathbb{E} \big[ \mathbb{P} \big( \mu - \overline{X}^* > \sqrt{({2 \sigma^2 } / {B}) \log \left( {2} / {\alpha}\right)} \mid B \big) \big] \leq \alpha / 2$. With $U_X = \sqrt{({2 \sigma^2 } / {B}) \log \left( {2} / {\alpha}\right)}$, based on (ref), we can derive a valid upper confidence bound for $r_k$ , and develop the corresponding UCB algorithm. The algorithm details are outlined in Algorithm (ref).

However, this approach leads to a random concentration bound $\sqrt{({2 \sigma^2 } / {B}) \log \left( 2 / \alpha \right)}$ that depends on $\{Y_t\}_{t = 1}^n$, which makes the analysis quite complicated. Fortunately, Lemma (ref) demonstrates that we can have a similar concentration bound with rate $\sqrt{np_k}$, which is much easier to analyze. It also verifies that the observed average of i.i.d. sub-Weibull variables behave with a combination of a Gaussian and a Weibull tail.

More importantly, $U_{X^*}$ is not only independent of $\mu$ but also enables a tighter product method-based concentration for $r = \mu \times p$ compared to standard sub-Weibull concentrations for $R_t = X_t \times Y_t$. Our numerical results in Figure (ref) demonstrate this advantage. Furthermore, the theoretical basis of this improvement will be detailed in Corollary (ref) in Section (ref).

{ In addition, some applications exhibit zero-inflated rewards where the non-zero part is heavy-tailed, possessing only finite moments of order $1 + \epsilon$ for some $\epsilon \in (0,1]$. To handle such cases, we construct an upper bound for the trimmed mean bickel1965some,bubeck2013bandits, enabling the corresponding UCB algorithm. Further details are provided in Appendix (ref). }

Thompson sampling approach

We also extend our discussion to another widely adopted approach, Thompson Sampling (TS) thompson1933likelihood. Similarly to our approach with the UCB algorithms above, we consider the non-zero part $X_t$ and the binary variable $Y_t$ separately. For ease of exposition, we consider the sub-Gaussian case for $X_t$. This can be easily extended to sub-Weibull cases by introducing an extra sampling step, known as Chambers-Mallows-Stuck (CMS) Generation, to rescale $X_t$ to a sub-Gaussian tail weron1996chambers,ijcai2019p0792,shi2022thompson.

Following the standard TS framework, we sample $\mu_k$ and $p_k$ from their respective posteriors and multiply them. We prove this is equal to posterior sampling in Appendix (ref). To achieve a minimax optimal TS algorithm for general sub-Gaussian distributions, we follow jin2021mots,karbasi2021parallelizing to use a clipped Gaussian distribution, denoted as $\operatorname{cl}\mathcal{N}(\mu, \sigma^2; \vartheta) := \max\{\mathcal{N}(\mu, \sigma^2), \vartheta\}$, 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_t$ and a clipped Beta distribution for the binary part $Y_t$. Our decision to use a clipped Beta distribution over a standard Beta distribution stems from our analysis, which shows it is critical for managing the risk of overestimating suboptimal arms in $R_t = X_t \times Y_t$. Further details are outlined in Appendix (ref).

Zero-Inflated Contextual Bandits

In this section, we extend our discussion to the Contextual Bandits problem. For concreteness, we consider the following setup of contextual bandits, although other setups can be similarly formulated and addressed: on each round $t$, the agent observes a context vector $\mathbf{x}_t$ and a set of feasible actions $\mathcal{A}_t$, choose an action $A_t \in \mathcal{A}_t$, and receive a random reward $R_t = r(\mathbf{x}_t, A_t) + \varepsilon_t$, where $r$ is the mean-reward function and $\varepsilon_t$ is the random error. The cumulative regret in this setup is defined as $ \mathcal{R}(T) = \sum_{t=1}^T {\mathbb{E}} \big[ \max_{a \in \mathcal{A}_t} r(\mathbf{x}_t, a) - r(\mathbf{x}_t, A_t) \big]. $

To utilize the ZI structure, we propose to consider the following model: $X_t = g \big(\mathbf{x}_t, A_t;\boldsymbol{\beta} \big) + \varepsilon_t$, $Y_t \sim \operatorname{Bernoulli}\big(h(\mathbf{x}_t, A_t;\boldsymbol{\theta}) \big)$, and $R_t = 0 \times (1 - Y_t) + X_t \times Y_t$, where $\varepsilon_t$ is a mean-zero error term, $h$ is a function with codomain $[0,1]$ and parameterized by $\boldsymbol{\theta} \in \mathbb{R}^q$, and $g$ is a function parameterized by $\boldsymbol{\beta} \in \mathbb{R}^d$. We remark the relationship that $r(\mathbf{x}, a) = h(\mathbf{x}, a;\boldsymbol{\theta}) \times g(\mathbf{x}, a;\boldsymbol{\beta})$.

Here, we present a general UCB template for our method in Algorithm (ref), which extends the MAB version in Section (ref). Specifically, based on the functional forms of $h(\cdot, \cdot; \boldsymbol{\theta})$ and $g(\cdot, \cdot; \boldsymbol{\beta})$, we construct confidence bounds for exploration, denoted as $U_{\text{all}, t} (\mathbf{x}, a)$ for $h$ and $U_{\text{all}, t} (\mathbf{x}, a)$ for $g$, respectively. At each step, we estimate $\boldsymbol{\theta}$ and $\boldsymbol{\beta}$, 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 $\boldsymbol{\theta}$ and $\boldsymbol{\beta}$. As a concrete example, Appendix (ref) provides detailed update formulas for both the UCB and TS algorithms when $h$ and $g$ are modeled as generalized linear functions.

Theory

Regret bounds for ZI MAB

Although concentration bounds for both components $X$ (e.g. van2013bernstein,kuchibhotla2022moving,zhang2022sharper for sub-Weibull) and $Y$ (e.g. bentkus2004hoeffding,mattner2007shorter,zhang2020concentration 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 because the reward, and consequently the action selection, is jointly determined by both $X$ and $Y$. Unlike standard bandits 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 a random variable. The lack of a precise distribution for sub-Weibull $X$ also complicates analytical analysis. Fortunately, our established Lemmas (ref) and (ref) help address these challenges to support the regret analysis of our algorithms.

Without loss of generality, we assume $r_k \in (0, 1)$, and $r_1 = \max_{k \in [K]} r_k$, i.e., the first arm is the optimal arm. To demonstrate the prior properties of considering the ZI structure from a theoretical perspective, we present the regret bound for our light-tailed ZI UCB algorithm for MAB.

In Theorem (ref), since $p_k$ is bounded in $(0,1]$ and $\Delta_k \leq 1$, the problem-independent regret simplifies to $\mathcal{R}(T) \lesssim \sqrt{K T \log T} + K$. This matches the minimax lower bound up to a factor of $\mathcal{O}(\sqrt{\log T})$ as given in Theorem 15.2 of lattimore2020bandit.

Since expected regret for MAB decomposes as $\mathcal{R}(T) = \sum_{k = 2}^K \Delta_k \mathbb{E} [c_k(T)]$, where $c_k(T)$ the number of times arm $k$ is pulled by round $T$, Lemma (ref) implies that achieving asymptotic order-optimality requires pulling each suboptimal arm at least $ \mathcal{O} \big( p_k^{-1} \Delta_k^{-2} \log T \big)$. However, canonical sub-Gaussian UCB algorithms fall short of this requirement. For sufficiently large $T$, there exists an environment $\mathcal{E}$ where regret satisfies $ \mathcal{R}(T) \geq\sum_{k = 2}^K (2 + \varepsilon)^{-1} \Delta_k^{-1} \log T $ for any $\varepsilon > 0$ audibert2009minimax, meaning suboptimal arms are pulled only $(2 + \varepsilon)^{-1} \Delta_k^{-2} \log T$ times. Since this ignores $p_k$, such algorithms fail to explore suboptimal arms sufficiently when $p_k$ is small, leading to under-exploration.

\fi

{ Similarly, we establish both problem-dependent and problem-independent regret bounds for our heavy-tailed UCB algorithm (Algorithm (ref) in Appendix (ref)), which matches the sharpness upper bounds rates in the current literature bubeck2013bandits, dubey2020cooperative, chatterjee2021regret and hence achieves state-of-the-art performance. The detailed regret analysis is provided in Appendix (ref). }

Compared to the results in the heavy-tailed bandits literature bubeck2013bandits, dubey2020cooperative, chatterjee2021regret, our regret bound only introduces an additional term, ${p_1^{-2}}{K} + \sum_{k = 2}^K {p_k^{-1}}{\sqrt{T}}$. If both the number of arms and $p_k$ values are fixed, this additional term is dominated by $K^{\frac{\epsilon}{1 + \epsilon}} T^{\frac{1}{1 + \epsilon}} \log^{\frac{\epsilon}{1 + \epsilon}} T$ as $\epsilon \in (0, 1]$. Therefore, Algorithm (ref) for heavy-tailed distributions is also state-of-the-art in the literature. \fi

We also provide the regret analysis for our TS algorithm, Algorithm (ref) in Appendix (ref), when the non-zero part is sub-Gaussian. In contrast to the proofs of UCB algorithms, we require the anti-concentration properties of the distributions to control the probability of underestimating the optimal arm agrawal2013thompson,jin2021mots,jin2022finite. Fortunately, we prove that the clipped Gaussian and clipped Beta distributions, as well as their products, exhibit anti-concentration with optimal decay rates (Lemma (ref) and Lemma (ref)). This finding allows us to establish the problem-dependent regret bound for our TS algorithm.

{

}

{ Given that $p_k$ are bounded within $(0, 1]$, the problem-independent regret is $\mathcal{R}(T) \lesssim \sqrt{KT} + K$. Compared to UCB (Theorem (ref)), Algorithm (ref) improves by a factor of $\sqrt{\log T}$. The regret is both minimax optimal auer2002nonstochastic for sub-Gaussian MAB. One can extend Theorem (ref) for sub-Weibull rewards with $\theta < 2$ with the CMS generation ijcai2019p0792. This introduces an additional regret term scaling as $(KT)^{1 / \theta}$ ijcai2019p0792,shi2022thompson, which remains state-of-the-art. }

{

Regret bounds for ZI contextual bandits

Analyzing ZI contextual bandit algorithms requires constructing confidence regions for both $\boldsymbol{\beta}$ and $\boldsymbol{\theta}$. Unlike in standard contextual linear bandit literature, the ZI structure means that updates to $\boldsymbol{\beta}$ 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 bandit algorithms, we analyze an instantiation where both the non-zero part $X_t$ and the binary part $Y_t$ follow generalized linear models (GLMs): $X_t = g\big(\boldsymbol{\beta}^{\top}\psi_X(\mathbf{x}_t, A_t)\big) + \varepsilon_t$ and $Y_t \sim \operatorname{Bernoulli}\big\{h\big(\boldsymbol{\theta}^{\top}\psi_Y(\mathbf{x}_t, A_t)\big)\}$. Here, $\varepsilon_t$ is sub-Gaussian, $g(\cdot)$ and $h(\cdot)$ are strictly increasing link functions, $\psi_X(\cdot)$ and $\psi_Y$ are known transformations. The unknown parameter vectors $\boldsymbol{\beta} \in \mathbb{R}^d$ and $\boldsymbol{\theta} \in \mathbb{R}^q$ govern the models, and the action space $\mathcal{A} = [K] \subseteq \mathbb{N}$ can be large or even infinite. This GLM setting is widely studied in bandit literature filippi2010parametric, li2017provably, wu2022residual, li2010contextual, li2012unbiased, lattimore2020bandit. }

{ Denote $\| \mathbf{z} \|_{\mathbf{A}}^2 = \mathbf{z}^{\top} \mathbf{A} \mathbf{z}$ for any $\mathbf{z} \in \mathbb{R}^d$ and positive definite matrix $\mathbf{A} \in \mathbb{R}^{d \times d}$. For the GLM setting, we design explicit forms for the confidence bound exploration terms $U_{\text{all}, t}$ and $U_{\text{non-zero}, t}$, along with the estimation steps in Algorithm (ref). Specifically, at round $t$, the estimates $\widehat{\boldsymbol{\beta}}_t$ and $\widehat{\boldsymbol{\theta}}_t$ are obtained via ridge regression $\widehat{\boldsymbol{\beta}}_t := \arg \min_{\boldsymbol{\beta} \in \Gamma} \big\| \sum_{s \in [t]: Y_s = 1} \big[ R_s - g\big( \psi_X(\mathbf{x}_s, A_s)^{\top} \boldsymbol{\beta}\big) \big] \big\|_{\mathbf{V}_t^{-1}}$ and $\widehat{\boldsymbol{\theta}}_t = \arg\min_{\boldsymbol{\theta} \in \Theta}\big\| \sum_{s = 1}^t \big[ Y_{s} - h \big( \psi_Y(\mathbf{x}_s, A_s)^{\top} \penalty 0 {\boldsymbol{\theta}} \big) \big] \big\|_{\mathbf{U}_t^{-1}}$. The corresponding sample covariance matrices are $\mathbf{V}_t = \lambda_V \mathbf{I}_d + \sum_{s \in [t]: Y_s = 1} \psi_X(\mathbf{x}_s, A_s) \psi_X(\mathbf{x}_s, A_s)^{\top}$ and $\mathbf{U}_t = \lambda_U \mathbf{I}_q + \sum_{s \in [t]} \psi_Y(\mathbf{x}_s, A_s) \psi_Y(\mathbf{x}_s, A_s)^{\top}$, where $\lambda_V, \lambda_U$ are regularization parameters, and $\Gamma, \Theta$ 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_{\text{non-zero}, t}(\mathbf{x}_t, a) = \rho_{X, t} \| \psi_{X}(\mathbf{x}_t, a)\|_{\mathbf{V}_t^{-1}}$ and $U_{\text{all}, t}(\mathbf{x}_t, a) = \rho_{Y, t} \| \psi_{Y}(\mathbf{x}_t, a)\|_{\mathbf{U}_t^{-1}}$, where $\{ \rho_{X, t}, \rho_{Y, t} \}_{t \geq 0}$ are ellipsoidal scaling factor sequences controlling exploration. This leads to our UCB algorithm for ZI GLM (Algorithm (ref) in Appendix (ref)). }

{ To derive the regret bounds for our UCB algorithm, we impose regularity conditions on the link functions, parameter 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 sub-Gaussian. These assumptions are standard and mild in the literature on generalized linear contextual bandits li2010contextual,deshpande2018accurate,wu2022residual. The formal assumptions are detailed in Assumptions (ref) and (ref) in Appendix (ref). Utilizing results on self-normalized martingales abbasi2011improved, we derive the following regret bounds for Algorithm (ref). }

{ A notable observation is that the regularity conditions, random selection period, tuning parameter choices, and regret bound in Theorem (ref) are independent of the number of arms $K$. This regret rate $\widetilde{\mathcal{O}}((d \vee q) \sqrt{T})$ matches the minimax lower bound up to a logarithmic factor for contextual bandit problems with both finite and countably infinite action spaces dani2008stochastic. }

{ While Theorem (ref) focuses on the UCB approach, the TS variant can achieve the same regret rate. Specifically, the TS algorithm samples parameters as $\widetilde{\boldsymbol{\beta}}_t \sim \mathcal{N}(\widehat{\boldsymbol{\beta}}_t, \varrho_{X, t}^2 \mathbf{V}_t^{-1})$ and $\widetilde{\boldsymbol{\theta}}_t \sim \mathcal{N}(\widehat{\boldsymbol{\theta}}_t, \varrho_{Y, t}^2 \mathbf{U}_t^{-1})$, using the same estimators $\widehat{\boldsymbol{\beta}}_t, \widehat{\boldsymbol{\theta}}_t, \mathbf{V}_t, \mathbf{U}_t$ as in the UCB algorithm. With appropriately chosen confidence radii $\{ \varrho_{X, t}, \varrho_{Y, t} \}_{t \geq 0}$, the TS algorithm selects actions as $A_t^{\text{TS}} = \arg\max_{a \in [K]} [\psi_X(\mathbf{x}_t, a)^{\top} \widetilde{\boldsymbol{\beta}}_t] \times [\psi_Y(\mathbf{x}_t, a)^{\top} \widetilde{\boldsymbol{\theta}}_t]$. The full algorithm (Algorithm (ref)) and regret bounds (Corollary (ref)) are detailed in Appendix (ref). }

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 sub-Weibull concentration bogucki2015suprema,hao2019bootstrapping, with difference in the size parameter specification: size parameter of the non-zero component, estimated variances, on-the-fly estimated size parameters, and the true size parameters (strong baseline). Additionally, we include the MOTS algorithm from jin2021mots as a TS baseline. The details of these baselines and our setting are presented in Appendix (ref).

We run simulations with different distributions of $p = \max_{k \in [K]} p_k$ with $\delta = 4 / T^2$. Here, we only present the result with $p \sim U[0.30, 0.35]$ in Figure (ref). Besides, the $1 - \delta$ upper confidence bounds for different UCB algorithms are shown in Figure (ref) (b). Findings from other settings (including $p < 0.01$) are similar and detailed in Appendix (ref). 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 uncertainty in ZIB. Consistent with our observations in Figure (ref), 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 ZI structure leads to looser concentration bounds and hence higher regret. Similarly, unlike the baseline TS algorithm jin2021mots, our TS algorithm outperforms other baseline 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 (ref)—complicates fair comparisons.

Simulation with contextual bandits. We adapt the settings in bastani2021mostly, wu2022residual to ZIB. We design $K = 100$ arms and generate a vector $\boldsymbol{\nu}_k \in \mathbb{R}^d$ with $d = 10$ for each arm $k \in [K]$. At each round $t$ the context for arm $k$ is sampled as $\mathbf{x}_{k, t} \sim \mathcal{N}_d\left( \boldsymbol{\nu}_{k}, \frac{1}{2K} I_d\right)$. The non-zero part of the reward, $X_t$, is generated using a linear model: $\boldsymbol{\beta}^{\top} \mathbf{x}_{A_t, t} + \varepsilon_t$, with $\varepsilon_t$ representing white noise. For the binary part, we model the probability using a generalized linear function with the link function $h(\boldsymbol{\theta}^{\top} \sin(\mathbf{x}_{A_t, t}))$. Both $\boldsymbol{\beta}$ and $\boldsymbol{\theta}$ are $d$-dimensional, with $\boldsymbol{\theta}$ having $s$ non-zero elements, where $s \in [d]$. The sparsity level $s$ signifies that the non-zero elements in $\boldsymbol{\theta}$ 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 (ref) against two baseline UCB methods: The first one is a naive method, called misspecified UCB, that overlooks 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 $(\boldsymbol{\beta}^{\top}, \boldsymbol{\theta}^{\top})$ from the model $\boldsymbol{\beta}^{\top} \mathbf{x}_{t} h(\boldsymbol{\theta}^{\top} \sin(\mathbf{x}_{t})) + \varepsilon_t$, by utilizing generalized contextual linear bandit algorithms li2017provably. Similarly, we assess our TS algorithm, Algorithm (ref), against the misspecified TS, which disregards the ZI structure, and integrated TS, which mirrors the integrated UCB. Various sparsity levels and link functions $h(\cdot)$ are considered. Results for $s = 7$ using the Probit function are shown in Figure (ref), with additional simulation details provided in Appendix (ref). Again, TS algorithms are excluded for exponential noise to ensure fair comparison. As shown in Figure (ref), 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.

Real Data. We apply our method to a real dataset of loan records from an U.S. online auto loan company, a widely studied public dataset columbialoandata, phillips2015effectiveness, ban2021personalized, bastani2022meta. We mainly follow the setup in chen2023steel. At each round $t$, an applicant arrives with certain covariates (the context) $\mathbf{x}_t$. The company then proposes a loan interest rate, which can be transformed into the nominal profit $A_t$ for the company (the raw action). This raw action, along with $\mathbf{x}_t$, determines the actual profit $X_t$ and affects the applicant's decision to accept $Y_t \in\{0,1\}$. The resulting reward for the company is hence $R_t=X_t \times Y_t$. We categorize the raw action $A_t \in \mathbb{R}$ into discrete levels: $\widetilde{A}_t \in \mathcal{A}_{\text{discrete}} = \{\text{``low"}, \text{``medium"}, \text{``high"}, \text{``very high"}, \text{``luxury"}\}$, each representing a distinct price level. To simulate counterfactual outcomes, we begin by fitting the entire dataset using $X_t=(A_t, 1, b(\mathbf{x}_t)^{\top})^{\top} \boldsymbol{\beta} + \varepsilon_t$ and $Y_t \sim \operatorname{Bernoulli}\left(h \big( ( A_t, 1, b^{\top}(\mathbf{x}_t))^{\top} \boldsymbol{\theta} \big)\right)$, where $h(\cdot)$ is the logistic function and the transformation function $b(\cdot)$ applied to the context is detailed in Appendix (ref). After deriving initial estimators $\widehat{\boldsymbol{\beta}}$ and $\widehat{\boldsymbol{\theta}}$, we then compare our method with two baseline approaches discussed in simulations for contextual bandits at each round $t$, an action $\widetilde{A}_t$ is selected from $\mathcal{A}_{\text{discrete}}$ using our algorithm. The profit $A_t$ is then sampled from its truncated distribution based on $\widetilde{A}_t$. Subsequently, the real profit $X_t$ and the binary decision $Y_t$ based on the offered $A_t$, and the corresponding reward $R_t = X_t \times Y_t$ are calculated. With the estimated parameters, we determine the optimal actions for each round to compute the regret. Detailed procedures and tuning parameters are in Appendix (ref).

The average cumulative regrets over 5000 rounds are shown in Figure (ref). 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 contextual 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 (ref), these algorithms sometimes result in linear regrets. In contrast, our UCB and TS algorithms consistently outperform the competition, achieving the lowest overall regret.

Discussion

In this paper, we introduce a new bandit model and the corresponding algorithmic framework tailored to the common 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.

Asymptotic Order-Optimality. A natural theoretical question 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.

We call an algorithm as asymptotic order-optimal, also known as finite-time instance near-optimality lai1985asymptotically,lattimore2015optimally,menard2017minimax,lattimore2020bandit, if its regret satisfies $ \liminf_{T \rightarrow + \infty} {\mathcal{R}(T)}/{\log T}$ and achieves the lower bound in Lemma (ref), up to universal constants independent of both the horizon $T$ and problem-specific parameters $r_k$ (and thus $\Delta_k, p_k$). 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 $p_k$. However, designing an algorithm that attains this optimality may require additional refinements. For example, in (ref), we allocate equal probability $\alpha / 2$ for the two concentration bounds, $\mathbb{P} (\mu_k > \overline{X} + U_X) \leq \alpha / 2$ and $\mathbb{P} (p_k > \overline{Y} + U_Y) \leq \alpha / 2$. To achieve asymptotic order-optimality, these probabilities may need to be adjusted based on $p_k$. We leave this as an open problem for future research.

where the last “$\lesssim$" is due to $p_1, p_k \in (0, 1]$. This finalizes the minimax ratio in Table (ref) for MAB.

Additional Algorithms Details

Algorithms for MAB

As outlined in Section (ref), we have developed a detailed heavy-tailed UCB algorithm and 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 two algorithms are presented in Algorithm (ref) and Algorithm (ref).

The equivalence of directly sampling $r_k$ and the procedure of sampling $\mu_k$ and $p_k$ from their respective posteriors and then multiplying them in Algorithm (ref), which can be mathematically expressed as follows:

where the last equality results from two assumptions: 1) independent priors for $\mu_k$ and $p_k$, and 2) non-zero rewards depend solely on $\mu_k$, while zero rewards depend only on $p_k$.

{An important aspect of the TS-algorithm is our use of clipped distributions for both the sub-Gaussian non-zero part $X$ and the precisely Bernoulli distributed part $Y$. As explained in Section (ref), the reason for using a clipped Gaussian distribution for $X$ is due to its deviation from an 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 \times Y$. The product of the original Beta distribution and the clipped Gaussian does not adequately control the overestimation probability of sub-optimal $R_k$ in our proofs. This is primarily due to the proof techniques employed. For more details, refer to the proofs of Theorem (ref) in Appendix (ref).}

Algorithms for Generalized Linear Contextual Bandits

UCB Algorithms and Regularity Conditions

As a concrete example, we consider the widely-used generalized linear contextual bandits with finite action set $\mathcal{A} = [K]$, where both functions $h$ and $g$ are structured as generalized linear functions here.

{ This setup is characterized by the known transformation functions $\psi_X(\cdot)$, $\psi_Y(\cdot)$, and the known link functions $g(\cdot)$ and $h(\cdot)$, such that $g(\mathbf{x}_t, A_t; \boldsymbol{\beta}) = g\big(\psi_X(\mathbf{x}_t, A_t)^{\top}\boldsymbol{\beta} \big)$ and $h(\mathbf{x}_t, A_t; \boldsymbol{\theta}) = h\big( \psi_Y(\mathbf{x}_t, A_t)^{\top}\boldsymbol{\theta} \big)$. When the $\varepsilon_t$ is sub-Gaussian, confidence radii for the ridge estimations $\widehat{\boldsymbol{\theta}}_t$ (or $\widehat{\boldsymbol{\beta}}_t$) in a compact parameter space can be fully determined by $\psi_Y(\mathbf{x}_t, A_t)$ (or $\psi_X(\mathbf{x}_t, A_t)$) and the sub-Gaussian variance proxy of $\varepsilon_t$. Specifically, $\rho_{Y, t}$ is chosen such that zhang2023mathematical \[ \mathbb{P} \left( \forall 0 \leq t \leq T : \rho_{Y, t} \geq \sqrt{\lambda_U} +\sup_{a \in [K], \mathbf{x}_{1:t} \in \mathcal{X}} \left\| \sum_{s=1}^t \varepsilon_{s} \psi_Y(\mathbf{x}_s, a) \right\|_{\mathbf{U}_t^{-1}} \right) \geq 1 - \delta. \] Thus, the ellipsoidal ratio $\rho_{Y, t}$ in Algorithm (ref) is constructed accordingly. A similar approach applies to $\rho_{X, t}$ for the non-zero component, though additional randomness from $X_s = g \big( \psi_X(\mathbf{x}_s, A_s)^{\top} \boldsymbol{\beta}^* \big)$ must be carefully handled, as discussed in Section (ref). The proof of Theorem (ref) provides further details, which we omit here for brevity. }

Next, we present the regularity conditions and selections of tuning parameters for Theorem (ref). Let the true parameters be $\boldsymbol{\beta}^*$ and $\boldsymbol{\theta}^*$, and $\mathbf{Z}_{t, a} = \psi_X(\mathbf{x}_t, a) \in \mathbb{R}^d$ and $\mathbf{W}_{t, a} = \psi_Y(\mathbf{x}_t, a) \in \mathbb{R}^q$ for $a \in [K]$. These assumptions are quite standard in generalized linear contextual bandits li2010contextual,deshpande2018accurate,wu2022residual.

{ A quick remark here is that all regularity conditions in Assumption (ref), (ref), and tuning parameter selections inAssumptionn (ref) are independent of the number of arms $K$. }

Thompson sampling for GLM

Just like in the standard TS algorithm for linear contextual bandits agrawal2013thompson, we employ Gaussian priors for the sub-Gaussian noise. At each round $t \in [T]$, we sample parameters $\{ \widetilde{\boldsymbol{\beta}}_t,\widetilde{\boldsymbol{\theta}}_t \}$ from Gaussian posterior distributions centered at the estimates $\{ \widehat{\boldsymbol{\beta}}_t,\widehat{\boldsymbol{\theta}}_t \}$ with covariance matrices $\big\{ \varrho_{X, t}^2 \mathbf{V}_t^{-1}, \varrho_{Y, t}^2 \mathbf{U}_t^{-1} \big\}$, where these estimates and covariance matrices are obtained from the UCB algorithm. The arm $A_t$ is then selected by maximizing the Thompson Sampling objective function $\psi_X(\mathbf{x}_t, a)^{\top} \widetilde{\boldsymbol{\beta}}_t \times \psi_Y(\mathbf{x}_t, a)^{\top} \widetilde{\boldsymbol{\theta}}_t $ leveraging the fact that both link functions are strictly increasing.

Let $A_t^*$ denote the optimal action at round $t$, and define $\mathbf{W}_t^* := \psi_X(\mathbf{W}_t, A_t^*)$. To ensure an appropriate choice of confidence radius sequences $\{\varrho_{Y, t}\}_{t \geq 0}$ (or $\{\varrho_{X, t}\}_{t \geq 0}$, both of which can be variance-dependent), it suffices to find $\varrho_{Y, t} > 0$ such that agrawal2013thompson

for some $\epsilon \in (0, 1)$, where $\mathcal{G}_t$ is a high-probability good event defined as \[ \mathcal{G}_t := \Big\{ \forall \, a \in [K] : \mathbf{W}_{t, a}^{\top} \big( \widehat{\boldsymbol{\theta}}_t - {\boldsymbol{\theta}}^* \big) \leq \varrho_{Y, t} \| \mathbf{W}_{t, a} \|_{\mathbf{U}_t^{-1}} \Big\}. \]

From the proof of Theorem (ref), we can set $\varrho_{Y, t} \gtrsim \rho_{Y, t}$ to ensure that $\mathcal{G}_t$ holds with probability at least $1 - \delta$ for $t > \tau$. To validate the anti-concentration property in (ref), we use the inequality \[ \frac{1}{2 \sqrt{\pi} x} \exp \left(-x^2 / 2\right) \leq \mathbb{P} (|\mathcal{N}(\mu, \sigma^2) - \mu| >x \sigma) \leq \frac{1}{\sqrt{\pi} x} \exp \left(-x^2 / 2\right). \] Thus, choosing $\varrho_{Y, t} = \sqrt{\epsilon^{-1} q \log (1 / \delta)}$ with $\epsilon \asymp \log T$ ensures that \[ \mathbb{P} \bigg( \mathbf{W}_{t}^* \widetilde{\boldsymbol{\theta}}_t > \mathbf{W}_{t}^* \boldsymbol{\theta}^* + \sqrt{\varrho_{Y, t}^2 \log^3 T} \| \mathbf{W}_t \|_{\mathbf{U}_t^{-1}} \mid \mathcal{F}_{t - 1} \cap \mathcal{G}_t \bigg) \geq \frac{1}{4 \mathrm{e} \sqrt{\pi T^{\epsilon}}}. \] Moreover, for any $t \in [T]$, \[

\] Similarly, we select $\varrho_{X, t} \asymp \sqrt{d \log (1 / \delta) \log (T)}$. This leads to the following corollary.

Extension for heavy-tailed noise

Similarly, one can also devise the UCB-type algorithm for sub-Gaussian $\varepsilon_t$, as detailed in Algorithm (ref) in Appendix (ref). {In cases where $\varepsilon_t$ follows a general sub-Weibull distribution or only has finite moments of order $1 + \epsilon$ with $\epsilon \in (0, 1]$, specific adjustments are necessary, such as applying the median of means (MoM) estimator for linear bandits medina2016no,shao2018almost or Huber regression sun2020adaptive,kang2023heavy. }