uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs
Authors: Yu Chen, Jiatai Huang, Yan Dai, Longbo Huang
ICLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we present a novel algorithm, uni INF, for the Heavy-Tailed Multi Armed Bandits (HTMAB) problem, demonstrating robustness and adaptability in both stochastic and adversarial environments... To be precise, uni INF ensures nearly-optimal regret in both stochastic and adversarial environments, matching the corresponding lower bounds when (σ, α) is known (up to logarithmic factors)... We develop a novel Bo BW algorithm uni INF (see Algorithm 1) for the Parameter-Free HTMAB problem... To derive the desired Bo BW property, we develop novel analytical techniques as well. These include a refined approach to control the Bregman divergence term via calculating partial derivatives and invoking the intermediate value theorem (see Section 5.2) and a stopping-time analysis for achieving O(log T) regret in stochastic environments (see Section 5.4). |
| Researcher Affiliation | Collaboration | Yu Chen IIIS, Tsinghua University EMAIL Jiatai Huang Beijing Zhuo Shi Capital Co., Ltd., China EMAIL Yan Dai ORC, Massachusetts Institute of Technology EMAIL Longbo Huang IIIS, Tsinghua University EMAIL |
| Pseudocode | Yes | Algorithm 1 uni INF: the universal INF-type algorithm for Parameter-Free HTMAB |
| Open Source Code | No | REPRODUCIBILITY STATEMENT This paper is primarily theoretical in nature, with the main contributions being the development of uni INF, the Best-of-Both-Worlds algorithm for Parameter-Free Heavy-Tailed Multi-Armed Bandits, and the introduction of several innovative algorithmic components and analytical tools. To ensure reproducibility, we have provided clear and detailed explanations of our methods, assumptions, and the development process of the algorithm throughout the paper. Complete proofs of our claims and results are included in the appendices. We have made every effort to present our research in a transparent and comprehensive manner to enable other researchers to understand and replicate our results. |
| Open Datasets | No | In this paper, we present a novel algorithm, uni INF, for the Heavy-Tailed Multi Armed Bandits (HTMAB) problem... In Heavy-Tailed MABs (HTMAB), for every t [T] and i [K], the loss is independently sampled from some heavy-tailed distribution νt,i in the sense that Eℓ νt,i[|ℓ|α] σα... (The paper defines theoretical loss distributions and environments, but does not use or provide access to any specific datasets for experimental evaluation.) |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on datasets, therefore, no dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setups or computational resources, therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and analysis rather than implementation details. No specific software dependencies or versions are mentioned. |
| Experiment Setup | No | The paper is theoretical, presenting an algorithm and its regret guarantees. It does not contain details about experimental setup, such as hyperparameters or training configurations, as no empirical experiments are described. |