Covariance-adapting algorithm for semi-bandits with application to sparse rewards

• URL: http://arxiv.org/abs/2604.13738v1
• Date: Wed, 15 Apr 2026 11:27:39 GMT
• Title: Covariance-adapting algorithm for semi-bandits with application to sparse rewards
• Abstract summary: We consider a new family of sub-exponential distributions, which contains bounded and Gaussian ones.<n>We prove a new lower bound on the expected regret on this family.<n>We then construct an algorithm that uses covariance estimates, and provide a tight analysis of the regret.
• Score: 43.942639292139425
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate stochastic combinatorial semi-bandits, where the entire joint distribution of outcomes impacts the complexity of the problem instance (unlike in the standard bandits). Typical distributions considered depend on specific parameter values, whose prior knowledge is required in theory but quite difficult to estimate in practice; an example is the commonly assumed sub-Gaussian family. We alleviate this issue by instead considering a new general family of sub-exponential distributions, which contains bounded and Gaussian ones. We prove a new lower bound on the expected regret on this family, that is parameterized by the unknown covariance matrix of outcomes, a tighter quantity than the sub-Gaussian matrix. We then construct an algorithm that uses covariance estimates, and provide a tight asymptotic analysis of the regret. Finally, we apply and extend our results to the family of sparse outcomes, which has applications in many recommender systems.

Related papers

• Inference and Uncertainty Quantification for Streaming $r$-PCA [0.40105987447353786]
  We address two open questions in streaming PCA via Oja's algorithm.<n>We prove a matching lower bound, up to logarithmic factors, across both dense-tail sparse-tail regimes.
  arXiv  Detail & Related papers  (2026-08-18T23:02:28Z)
• Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problem [16.04977600068383]
  We provide a new information-theoretic generalization error bound that is exactly tight (i.e., matching even the constant) Most existing bounds are order-wise loose in this setting. A refined bound is then proposed for decomposable loss functions, leading to a tight bound for the vector setting.
  arXiv  Detail & Related papers  (2023-05-01T15:22:58Z)
• Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms [30.310960863405267]
  We derive sharp non-asymptotic deviation bounds for weighted sums of Dirichlet random variables. These bounds are based on a novel integral representation of the density of a weighted Dirichlet sum.
  arXiv  Detail & Related papers  (2023-04-06T13:15:51Z)
• A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms [14.33758865948252]
  We revisit two famous bandit algorithms, Minimum Empirical Divergence (MED) and Thompson Sampling (TS) We prove that MED is optimal for all these models, but also provide a simple regret analysis of some TS algorithms for which the optimality is already known.
  arXiv  Detail & Related papers  (2023-03-10T16:43:48Z)
• Generalizing Gaussian Smoothing for Random Search [23.381986209234164]
  Gaussian smoothing (GS) is a derivative-free optimization algorithm that estimates the gradient of an objective using perturbations of the current benchmarks. We propose to choose a distribution for perturbations that minimizes the error of such distributions with provably smaller MSE.
  arXiv  Detail & Related papers  (2022-11-27T04:42:05Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  We provide a framework for designing Generative Adversarial Networks (GANs) to solve high dimensional robust statistics problems. Our work extend these to robust mean estimation, second moment estimation, and robust linear regression. In terms of techniques, our proposed GAN losses can be viewed as a smoothed and generalized Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2022-02-02T20:11:33Z)
• 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)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  Conventional approaches for simulating Gaussian process posteriors view samples as draws from marginal distributions of process values at finite sets of input locations. This distribution-centric characterization leads to generative strategies that scale cubically in the size of the desired random vector. We show how this pathwise interpretation of conditioning gives rise to a general family of approximations that lend themselves to efficiently sampling Gaussian process posteriors.
  arXiv  Detail & Related papers  (2020-11-08T17:09:37Z)
• Relative Deviation Margin Bounds [55.22251993239944]
  We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity. We derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment.
  arXiv  Detail & Related papers  (2020-06-26T12:37:17Z)
• 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.