Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits

Yuriy Dorn (), Nikita Kornilov (), Nikolay Kutuzov (), Alexander Nazin (), Eduard Gorbunov () and Alexander Gasnikov ()
Additional contact information
Yuriy Dorn: MSU Institute for Artificial Intelligence
Nikita Kornilov: Moscow Institute of Physics and Technology
Nikolay Kutuzov: Moscow Institute of Physics and Technology
Alexander Nazin: V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences
Eduard Gorbunov: Mohamed bin Zayed University of Artificial Intelligence
Alexander Gasnikov: Moscow Institute of Physics and Technology

Computational Management Science, 2024, vol. 21, issue 1, No 19, 29 pages

Abstract: Abstract The Implicitly Normalized Forecaster (INF) algorithm is considered to be an optimal solution for adversarial multi-armed bandit (MAB) problems. However, most of the existing complexity results for INF rely on restrictive assumptions, such as bounded rewards. Recently, a related algorithm was proposed that works for both adversarial and stochastic heavy-tailed MAB settings. However, this algorithm fails to fully exploit the available data. In this paper, we propose a new version of INF called the Implicitly Normalized Forecaster with clipping (INF-clip) for MAB problems with heavy-tailed reward distributions. We establish convergence results under mild assumptions on the rewards distribution and demonstrate that INF-clip is optimal for linear heavy-tailed stochastic MAB problems and works well for non-linear ones. Furthermore, we show that INF-clip outperforms the best-of-both-worlds algorithm in cases where it is difficult to distinguish between different arms.

Keywords: Multi-armed bandits; Clipping; Online mirror descent (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10287-023-00500-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:comgts:v:21:y:2024:i:1:d:10.1007_s10287-023-00500-z

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-023-00500-z

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().