← All problems
Unverified

Regret Minimization in Heavy-Tailed Bandits with Unknown Moment Parameters

In a KK-armed bandit run for TT rounds, arm ii has reward distribution νi\nu_i satisfying

EX∼νi∣X∣1+ϵ≤u \mathbb E_{X\sim\nu_i}|X|^{1+\epsilon}\leq u

for common but unknown ϵ∈(0,1]\epsilon\in(0,1] and u>0u>0. Write μi=EX\mu_i=\mathbb E X, μ⋆=max⁡iμi\mu^\star=\max_i\mu_i, Δi=μ⋆−μi\Delta_i=\mu^\star-\mu_i, and

RT=∑t=1T(μ⋆−μIt). R_T=\sum_{t=1}^T(\mu^\star-\mu_{I_t}).
  1. What is the best regret rate that can be incurred in the heavy-tailed multi-armed bandit problem without any knowledge of ϵ\epsilon and uu and without any additional assumption? This requires a minimax lower bound and a matching upper bound.

  2. Does there exist an algorithm that can achieve such a bound without knowing ϵ\epsilon and uu and without any additional assumption?

  3. Is there an assumption that is better than the others, or that encompasses all of the distributions for which adaptation comes at no additional cost?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu