Zero-Inflated Bandits
Haoyu Wei Runzhe Wan Lei Shi Rui Song
Many real applications of bandits have sparse non-zero rewards, leading to
slow learning rates. A careful distribution modeling that utilizes
problem-specific structures is known as critical to estimation efficiency in
the statistics literature, yet is under-explored in bandits. To fill the gap,
we initiate the study of zero-inflated bandits, where the reward is modeled as
a classic semi-parametric distribution called zero-inflated distribution. We
carefully design Upper Confidence Bound (UCB) and Thompson Sampling (TS)
algorithms for this specific structure. Our algorithms are suitable for a very
general class of reward distributions, operating under tail assumptions that
are considerably less stringent than the typical sub-Gaussian requirements.
Theoretically, we derive the regret bounds for both the UCB and TS algorithms
for multi-armed bandit, showing that they can achieve rate-optimal regret when
the reward distribution is sub-Gaussian. The superior empirical performance of
the proposed methods is shown via extensive numerical studies.