Hugging Face Trending Papers

Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff

We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and returns a single bit in response to a query $Q: \mathbb{R}\to\{0,1\}$ chosen by a central learner.

arXiv Machine Learning
Oct 16

Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds

The paper investigates transfer learning in stochastic multi‑armed bandits when historical data come from an unknown adaptive policy. It establishes asymptotic problem‑dependent lower bounds and introduces the KL‑UCB‑Transfer algorithm, which combines online and historical data to achieve logarithmic regret with an improved constant under certain mean‑gap conditions. The study also relaxes the source‑target discrepancy assumption to a one‑sided condition, demonstrating that logarithmic regret can still be achieved under misspecification and identifying regimes of improvement, degradation, or loss of guarantee.

By Adrien Prevost, Timothee Mathieu, Waris Radji, Odalric-Ambrym Maillard
arXiv Machine Learning
Sep 25

Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon

The paper revisits realizable multiclass PAC learning with bandit feedback, correcting a previously claimed lower bound on sample complexity. It introduces a new anchored dimension, “aBDS,” and establishes a constant‑free three‑part lower bound, while also providing tighter upper bounds that eliminate dependence on the total label count. The authors demonstrate that the optimal sample complexity can vary dramatically even among classes with identical dimensional profiles, revealing a confidence direct‑sum phenomenon and a rank‑saturation phase transition.

By Guangjian Zhang