Zero-Inflated Bandits

• URL: http://arxiv.org/abs/2312.15595v2
• Date: Thu, 10 Oct 2024 19:17:38 GMT
• Title: Zero-Inflated Bandits
• Authors: Haoyu Wei, Runzhe Wan, Lei Shi, Rui Song,
• Abstract summary: We study zero-inflated bandits, where the reward is modeled as a classic semi-parametric distribution called zero-inflated distribution. We derive the regret bounds under both multi-armed bandits with general reward assumptions and contextual generalized linear bandit with sub-Gaussian rewards. In many settings, the regret rates of our algorithms are either minimax optimal or state-of-the-art.
• Score: 11.60342504007264
• License:
• Abstract: Many real applications of bandits have sparse non-zero rewards, leading to slow learning speed. Using problem-specific structures for careful distribution modeling is known as critical to estimation efficiency in statistics, yet is under-explored in bandits. We initiate the study of zero-inflated bandits, where the reward is modeled as a classic semi-parametric distribution called zero-inflated distribution. We design Upper Confidence Bound- and Thompson Sampling-type algorithms for this specific structure. We derive the regret bounds under both multi-armed bandits with general reward assumptions and contextual generalized linear bandit with sub-Gaussian rewards. In many settings, the regret rates of our algorithms are either minimax optimal or state-of-the-art. The superior empirical performance of our methods is demonstrated via numerical studies.

Related papers

• Batch Ensemble for Variance Dependent Regret in Stochastic Bandits [41.95653110232677]
  Efficiently trading off exploration and exploitation is one of the key challenges in online Reinforcement Learning (RL) Inspired by practical ensemble methods, in this work we propose a simple and novel batch ensemble scheme that achieves near-optimal regret for Multi-Armed Bandits (MAB) Our algorithm has just a single parameter namely the number of batches, and its value does not depend on distributional properties such as the scale and variance of the losses.
  arXiv  Detail & Related papers  (2024-09-13T06:40:56Z)
• Diffusion Models Meet Contextual Bandits with Large Action Spaces [1.0878040851638]
  In contextual bandits, the rewards of actions are often correlated and this can be leveraged to explore them efficiently. In this work, we capture such correlations using pre-trained diffusion models; upon which we design diffusion Thompson sampling (dTS)
  arXiv  Detail & Related papers  (2024-02-15T15:48:55Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Distributionally Robust Skeleton Learning of Discrete Bayesian Networks [9.46389554092506]
  We consider the problem of learning the exact skeleton of general discrete Bayesian networks from potentially corrupted data. We propose to optimize the most adverse risk over a family of distributions within bounded Wasserstein distance or KL divergence to the empirical distribution. We present efficient algorithms and show the proposed methods are closely related to the standard regularized regression approach.
  arXiv  Detail & Related papers  (2023-11-10T15:33:19Z)
• Exact Non-Oblivious Performance of Rademacher Random Embeddings [79.28094304325116]
  This paper revisits the performance of Rademacher random projections. It establishes novel statistical guarantees that are numerically sharp and non-oblivious with respect to the input data.
  arXiv  Detail & Related papers  (2023-03-21T11:45:27Z)
• From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits [0.0]
  We study a generic Dirichlet Sampling (DS) algorithm, based on pairwise comparisons of empirical indices computed with re-sampling of the arms' observations. We show that different variants of this strategy achieve provably optimal regret guarantees when the distributions are bounded and logarithmic regret for semi-bounded distributions with a mild quantile condition.
  arXiv  Detail & Related papers  (2021-11-18T14:34:21Z)
• An Effective Baseline for Robustness to Distributional Shift [5.627346969563955]
  Refraining from confidently predicting when faced with categories of inputs different from those seen during training is an important requirement for the safe deployment of deep learning systems. We present a simple, but highly effective approach to deal with out-of-distribution detection that uses the principle of abstention.
  arXiv  Detail & Related papers  (2021-05-15T00:46:11Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  We show how iteration under a more standard notion of low inherent Bellman error, typically employed in least-square value-style algorithms, can provide strong PAC guarantees on learning a near optimal value function. We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function.
  arXiv  Detail & Related papers  (2020-08-18T04:34:21Z)
• Latent Bandits Revisited [55.88616813182679]
  A latent bandit problem is one in which the learning agent knows the arm reward distributions conditioned on an unknown discrete latent state. We propose general algorithms for this setting, based on both upper confidence bounds (UCBs) and Thompson sampling. We provide a unified theoretical analysis of our algorithms, which have lower regret than classic bandit policies when the number of latent states is smaller than actions.
  arXiv  Detail & Related papers  (2020-06-15T19:24:02Z)
• A General Method for Robust Learning from Batches [56.59844655107251]
  We consider a general framework of robust learning from batches, and determine the limits of both classification and distribution estimation over arbitrary, including continuous, domains. We derive the first robust computationally-efficient learning algorithms for piecewise-interval classification, and for piecewise-polynomial, monotone, log-concave, and gaussian-mixture distribution estimation.
  arXiv  Detail & Related papers  (2020-02-25T18:53:25Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  We develop Thompson Sampling-style algorithms for mean-variance MAB. We also provide comprehensive regret analyses for Gaussian and Bernoulli bandits. Our algorithms significantly outperform existing LCB-based algorithms for all risk tolerances.
  arXiv  Detail & Related papers  (2020-02-01T15:33:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.