Paper tackles robust offline RL with heavy-tailed rewards.
problem Real-world applications often encounter heavy-tailed rewards, challenging offline RL.
method Proposes ROAM and ROOM algorithms using median-of-means method for robust off-policy evaluation and OPO.
result Demonstrates superior performance on heavy-tailed reward datasets compared to existing methods.
New algorithm reduces worst-case regret for heavy-tailed bandits.
problem Stochastic Multi-Armed Bandit problem with heavy-tailed rewards.
method Modified minimax policy MOSS with saturated empirical mean.
result Worst-case regret matching lower bound for heavy-tailed distributions.
New algorithms handle heavy-tailed rewards in reinforcement learning.
problem Learning from heavy-tailed rewards in reinforcement learning.
method Robust mean estimation techniques for constructing algorithms.
result Near-optimal regret bounds achieved in heavy-tailed reward settings.
Paper tackles robust batched bandits for heavy-tailed rewards.
problem Clinical trials and other applications with heavy-tailed rewards.
method Proposes robust batched bandit algorithms for heavy-tailed rewards in finite-arm and Lipschitz-continuous settings.
result Heavier-tailed rewards require fewer batches for near-optimal regret in the instance-independent regime and Lipschitz setting.
New algorithm tackles multi-agent bandits with heavy-tailed data.
problem Maximizing system performance in multi-agent settings with heavy-tailed data.
method Algorithm exploits hub-like structures and synchronization among clients.
result Regret bound of O ( M 1 − 1 α log T ) O(M^{1 -\frac{1}α} \log{T}) O ( M 1 − α 1 log T ) for homogeneous settings, O ( M log T ) O(M \log{T}) O ( M log T ) for heterogeneous. The paper develops a robust algorithm for contextual bandits with heavy-tailed rewards.
problem Contextual bandits with heavy-tailed rewards.
method Develops an algorithm based on Catoni's estimator for robust statistics, applying it to contextual bandits with general function approximation.
result Establishes regret bounds that depend on cumulative reward variance and logarithmically on the reward range and number of rounds.
INF-clip optimizes heavy-tailed MAB problems with improved performance.
problem Optimizing multi-armed bandit problems with heavy-tailed rewards.
method INF-clip algorithm for adversarial and stochastic heavy-tailed MAB settings.
result INF-clip is optimal for linear and non-linear heavy-tailed stochastic MAB problems.
New method makes reinforcement learning robust to heavy-tailed rewards.
problem Heavy-tailed rewards cause statistical outliers in reinforcement learning.
method Dynamic gradient clipping in TD learning and NAC.
result Provably robust TD and NAC achieve optimal sample complexities.
Two algorithms tackle heavy-tailed rewards in reinforcement learning with linear function approximation.
problem Online sequential decision-making with heavy-tailed rewards.
method AdaOFUL and VARA algorithms for linear stochastic bandits and MDPs, using modified adaptive Huber regression.
result Achieved state-of-the-art and variance-aware regret bounds for heavy-tailed rewards.
Study on private and robust multi-armed bandits with contaminated heavy-tailed rewards.
problem Private and robust multi-armed bandits with contaminated heavy-tailed rewards.
method Proposed a meta-algorithm with a private and robust mean estimation sub-routine exttt{PRM}.
result Achieved nearly-optimal regret for two heavy-tailed settings.
New algorithm tackles heavy-tailed rewards in RL with instance-dependent regret bounds.
problem Efficient algorithms for RL with heavy-tailed rewards in large state-action spaces.
method Design of \textsc{Heavy-OFUL} for heavy-tailed linear bandits and \textsc{Heavy-LSVI-UCB} for RL with linear function approximation.
result First instance-dependent regret bounds for heavy-tailed rewards in RL with linear function approximation.
Paper develops robust estimators and strategies for stochastic MABs with heavy-tailed rewards.
problem Stochastic multi-armed bandits with heavy-tailed rewards.
method Proposes a novel robust estimator and perturbation-based exploration strategy.
result Develops upper and lower regret bounds for various perturbations.
Paper develops robust policy evaluation for reinforcement learning with outlier and heavy-tailed rewards.
problem Outlier contamination and heavy-tailed rewards in reinforcement learning.
method Develops a fully online robust policy evaluation procedure and efficient statistical inference.
result Establishes the Bahadur-type representation of the estimator and develops an online inference procedure.
Improved regret bounds for linear bandits with heavy-tailed rewards.
problem Stochastic linear bandits with heavy-tailed rewards.
method Elimination-based algorithm guided by experimental design.
result Regret bound of \(\tilde{\mathcal{O}}(d^\frac{1+3ε}{2(1+ε)} T^\frac{1}{1+ε})\) for \(ε\in (0,1)\).
PPO's gradients are heavy-tailed, affecting learning; a robust estimator improves performance.
problem Heavy-tailedness of PPO gradients causing learning issues.
method Characterized heavy-tailed gradients, identified likelihood ratios and advantages as sources, proposed GMOM as a robust estimator.
result GMOM improves PPO performance without clipping tricks.
New framework controls generalization for heavy-tailed data in RLHF and SGLD.
problem Heavy-tailed data in modern learning pipelines.
method Tail-dependent information-theoretic framework for sub-Weibull data.
result Sharp generalization bounds for heavy-tailed data.
Motivated by problems in search and detection we present a solution to a Combinatorial Multi-Armed Bandit (CMAB) problem with both heavy-tailed reward distributions and a new class of feedback, filtered semibandit feedback. In a CMAB problem an agent pulls a combination of arms from a set { 1 , . . . , k } \{1,...,k\} { 1 , ... , k } in each round, g…
Algorithm for low-rank matrix bandits with heavy-tailed rewards, achieving nearly optimal regret bound.
problem Stochastic low-rank matrix bandit with heavy-tailed rewards.
method LOTUS algorithm using truncation and dynamic exploration.
result Regret bound of order $ ilde O(d^ rac{3}{2}r^ rac{1}{2}T^ rac{1}{1+δ}/ ilde{D}_{rr})$ without knowing T T T . New UCB-type algorithms reduce regret bounds for stochastic bandits with heavy and super heavy noise.
problem Improving regret bounds for stochastic bandits with heavy-tailed noise.
method General convex optimization methods with an inexact oracle, Clipped-SGD-UCB algorithm.
result Achieved an O ( log T K T log T ) O(\log T\sqrt{KT\log T}) O ( log T K T log T ) regret bound for symmetric noise, better than general lower bounds. Optimal algorithm for minimizing regret in heavy-tailed bandits.
problem Minimizing regret in stochastic multi-armed bandits with heavy-tailed distributions.
method Proposes an optimal algorithm under the assumption of uniformly bounded moments of order (1+ε).
result Matches the lower bound exactly in the first-order term and provides a finite-time bound on its regret.
A new UCB algorithm for heavy-tailed bandits with near-optimal regret.
problem Sequential decision making in uncertain environments with heavy-tailed rewards.
method Data-driven, distribution-free UCB algorithm combining resampled median-of-means and UCB.
result Near-optimal regret bound for heavy-tailed distributions.
New method identifies uncertainty shocks in financial markets using revised VIX.
problem Traditional VIX fails to capture non-Gaussian, heavy-tailed asset returns.
method Fit a double-subordinated Normal Inverse Gaussian Levy process to S&P 500 option prices to construct a revised VIX.
result Revised VIX provides a more comprehensive measure of volatility reflecting extreme movements and heavy tails.
New algorithm reduces heavy-tailed linear bandits' computational cost.
problem Stochastic linear bandits with heavy-tailed noise.
method One-pass online mirror descent with adaptive Huber regression.
result Near-optimal regret bound with reduced computational cost.
Optimizing rewards under budget constraints with correlated costs and rewards.
problem Maximizing total expected reward under a budget constraint on total cost with correlated and potentially heavy-tailed cost-reward pairs.
method Proposes algorithms exploiting correlation between cost and reward via linear minimum mean-square error estimation to achieve tight regret bounds.
result Achieves O ( log B ) O(\log B) O ( log B ) regret for a budget B > 0 B>0 B > 0 under certain moment conditions. Classical multi-armed bandit problems use the expected value of an arm as a metric to evaluate its goodness. However, the expected value is a risk-neutral metric. In many applications like finance, one is interested in balancing the expected return of an arm (or portfolio) with the risk associated with that return. In …
This work creates a CS for non-negative heavy-tailed data with bounded mean.
problem Constructing a confidence sequence for non-negative heavy-tailed data with bounded mean.
method Non-parametric, non-asymptotic lower confidence sequence construction.
result The constructed CS is efficient and can be converted into a closed-interval CS.
This paper proposes a method to evaluate policies using quantile metrics, improving upon existing mean-based approaches.
problem Evaluating policies using mean-based metrics ignores the variability of outcomes, especially in skewed reward distributions.
method The paper introduces a doubly-robust inference procedure for quantile off-policy evaluation using deep conditional generative learning.
result The proposed estimator outperforms classical OPE estimators for mean outcomes in heavy-tailed reward distributions.
We consider black box optimization of an unknown function in the nonparametric Gaussian process setting when the noise in the observed function values can be heavy tailed. This is in contrast to existing literature that typically assumes sub-Gaussian noise distributions for queries. Under the assumption that the unknow…
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+ε, for some ε ∈ ( 0 , 1 ] ε\in (0,1] ε ∈ ( 0 , 1 ] . Surprisingly, moments of order 2 (i.e., finite variance) are suffi…
Thompson Sampling provides an efficient technique to introduce prior knowledge in the multi-armed bandit problem, along with providing remarkable empirical performance. In this paper, we revisit the Thompson Sampling algorithm under rewards drawn from symmetric α α α -stable distributions, which are a class of heavy-taile…
Novel LSE estimator improves off-policy learning and evaluation.
problem High variance and poor performance with low-quality propensity scores and heavy-tailed reward distributions.
method Introduces a novel estimator based on the log-sum-exponential (LSE) operator.
result Achieves convergence rate of O ( n − ε / ( 1 + ε ) ) O(n^{-ε/(1+ ε)}) O ( n − ε / ( 1 + ε ) ) for regret bounds. Optimized bandit algorithms have heavy-tailed regret distributions that can grow faster than expected.
problem Heavy-tailed regret distributions in optimized bandit algorithms.
method Change-of-measure ideas and UCB algorithm modifications.
result Regret distributions of optimized UCB algorithms have a heavy Cauchy tail, and can grow faster than poly-logarithmically.
Study improves ERM for heavy-tailed data with dependent inputs.
problem Empirical Risk Minimization with dependent and heavy-tailed data.
method Extending risk bounds for ERM with heavy-tailed, dependent data.
result Established risk bounds for ERM with dependent and heavy-tailed data.
New algorithms for efficient return distribution approximation in reinforcement learning.
problem Efficiently approximating unknown return distributions in reinforcement learning.
method Introduced novel distributional dynamic programming algorithms for arbitrary probabilistic reward mechanisms.
result Proved error bounds for the algorithms in Wasserstein and Kolmogorov--Smirnov distances.
Efficiently estimates sparse linear regression with heavy-tailed and outlier-contaminated data.
problem Estimating sparse linear regression coefficients with heavy-tailed and outlier-contaminated data.
method Efficient computation of estimators with sharp error bounds.
result Sharp error bounds for efficient estimators.
Is AdamW effective under heavy-tailed noise?
problem Stochastic gradient noise in LLM pretraining is typically heavy-tailed.
method Formulate as an open problem, prove a positive weighted-metric benchmark, and give a corridor lower-bound mechanism.
result No rigorous convergence theory for AdamW established in heavy-tailed regime.
Self-regulating annealing improves sampling from heavy-tailed datasets.
problem Sampling from heavy-tailed distributions using diffusion models.
method Proposed an SDE-based sampler with a state-dependent diffusion coefficient.
result State dependence induces a self-regulating annealing mechanism.
New diffusion models capture heavy-tailed distributions better.
problem Diffusion models struggle with rare or extreme events in heavy-tailed distributions.
method Repurposed diffusion framework using multivariate Student-t distributions, tailored perturbation kernel, and γ γ γ -divergence. result Our models generate rare and extreme events more effectively than standard diffusion models.
New concentration inequalities for tensors with heavy-tailed coefficients.
problem Developing bounds for Euclidean functions of tensors with sub-Weibull distributions.
method Extending concentration inequalities to sub-Weibull random tensors, using new inequalities for heavy-tailed random variables and martingale analysis.
result Established a phase transition between sub-gaussian and heavy-tailed regimes for Euclidean functions of tensors.
New models explain heavy-tailed behavior in neural networks.
problem Heavy-tailed spectral densities in neural networks.
method High-temperature Marchenko-Pastur (HTMP) ensemble models.
result Heavy-tailed behavior arises from three factors: data structure, training temperature, and eigenvector entropy.
New PAC-Bayes bounds for heavy-tailed losses using supermartingales.
problem Extending PAC-Bayes bounds to heavy-tailed losses.
method Using supermartingales and bounded variance assumption.
result PAC-Bayes generalization bounds for heavy-tailed losses.
New bounds for heavy-tailed SDEs without info-theory terms.
problem Understanding generalization of heavy-tailed stochastic optimization.
method Fractional Fokker-Planck equation to estimate entropy flows.
result High-probability bounds with better dimension dependence.
Study on error probability for classification of heavy-tailed renewal processes.
problem Error probability in classification of heavy-tailed renewal processes.
method Asymptotic expressions for Bhattacharyya bound on misclassification error probabilities.
result Obtained asymptotic expressions for misclassification error probabilities.
TTF improves performance of normalizing flows for heavy-tailed distributions.
problem Improving performance of normalizing flows for heavy-tailed distributions.
method Uses a Gaussian base distribution and a final transformation layer to produce heavy tails.
result Experimental results show TTF outperforms current methods, especially in high-dimensional or heavy-tailed scenarios.
Study tail behavior of sum of heavy-tailed risks with copulas.
problem Analyzing the tail behavior of sums of heavy-tailed risks with dependence modeled by copulas.
method Modeling dependence with copulas and analyzing tail asymptotics of sums of heavy-tailed risks.
result Obtained asymptotic expansions for Value-at-Risk of aggregate risk.
New sampling method for heavy-tailed distributions using Langevin Algorithm.
problem Sampling from heavy-tailed distributions efficiently.
method Transformed Unadjusted Langevin Algorithm on specific transformations.
result Polynomial-order oracle complexities for certain heavy-tailed densities.
Heavy-tailed distributions emerge in SGD's parameter evolution.
problem Understanding heavy-tailed distributions in SGD parameter evolution.
method Continuous diffusion approximation of SGD (homogenized SGD) analysis.
result Explicit upper and lower bounds on tail-index of homogenized SGD.
Privacy-preserving SGD with heavy-tailed noise achieves differential privacy guarantees.
problem Privacy preservation in noisy SGD with heavy-tailed noise.
method Differential privacy guarantees for SGD with heavy-tailed noise.
result SGD with heavy-tailed perturbations achieves ( 0 , O ( 1 / n ) ) (0, O(1/n)) ( 0 , O ( 1/ n )) -DP.