Bandits With Heavy Tail
From MaRDI portal
Abstract: The stochastic multi-armed bandit problem is well understood when the reward distributions are sub-Gaussian. In this paper we examine the bandit problem under the weaker assumption that the distributions have moments of order 1+epsilon, for some . Surprisingly, moments of order 2 (i.e., finite variance) are sufficient to obtain regret bounds of the same order as under sub-Gaussian reward distributions. In order to achieve such regret, we define sampling strategies based on refined estimators of the mean such as the truncated empirical mean, Catoni's M-estimator, and the median-of-means estimator. We also derive matching lower bounds that also show that the best achievable regret deteriorates when epsilon <1.
Recommendations
Cited in
(40)- Geometric median and robust estimation in Banach spaces
- Solvable integration problems and optimal sample size selection
- Multi-armed bandit with sub-exponential rewards
- A generalized Catoni's M-estimator under finite \(\alpha\)-th moment assumption with \(\alpha \in (1,2)\)
- Scale calibration for high-dimensional robust regression
- Robust parameter estimation of regression models under weakened moment assumptions
- Robust sub-Gaussian estimation of a mean vector in nearly linear time
- The robust nearest shrunken centroids classifier for high-dimensional heavy-tailed data
- Filtered Poisson process bandit on a continuum
- Distributed statistical estimation and rates of convergence in normal approximation
- Adaptive policies for perimeter surveillance problems
- Algorithms of robust stochastic optimization based on mirror descent method
- Convergence rates of least squares regression estimators with heavy-tailed errors
- Mean estimation and regression under heavy-tailed distributions: A survey
- Robust estimation of U-statistics
- Finite-time analysis for the knowledge-gradient policy
- scientific article; zbMATH DE number 7370566 (Why is no real title available?)
- Median-of-means approach for repeated measures data
- Best arm identification for contaminated bandits
- Rate-optimal robust estimation of high-dimensional vector autoregressive models
- Catoni-style confidence sequences for heavy-tailed mean estimation
- Robust supervised learning with coordinate gradient descent
- The asymptotic distribution of a truncated sample mean for the extremely heavy-tailed distributions
- Gaussian differentially private robust mean estimation and inference
- Robust subgaussian estimation with VC-dimension
- ARFIS: an adaptive robust model for regression with heavy-tailed distribution
- Logarithmic regret bounds for continuous-time average-reward Markov decision processes
- Robust covariance estimation for high-dimensional compositional data with application to microbial communities analysis
- Corruption-tolerant bandit learning
- Robust sparse covariance matrix estimation for high-dimensional compositional data under lower moment assumption
- Matrix Freedman inequality for sub-Weibull martingales
- Trimmed sample means for robust uniform mean estimation and regression
- Minimax off-policy evaluation and learning with subgaussian and differentiable importance weighting
- Factored-reward bandits with intermediate observations: regret minimization and best arm identification
- On deviation probabilities in non-parametric regression with heavy-tailed noise
- Residual permutation test for regression coefficient testing
- Feedback graph regret bounds for Thompson sampling and UCB
- Gradient descent for convex and smooth noisy optimization
- Nonasymptotic heavy-tailed mean estimation in smooth Banach spaces
- Empirical risk minimization for heavy-tailed losses
This page was built for publication: Bandits With Heavy Tail
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346276)
