Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Chenlu Ye, Yujia Jin, Alekh Agarwal, Tong Zhang · 2025
Read Catoni Contextual Bandits are Robust to Heavy-tailed Rewards by Chenlu Ye, Yujia Jin, Alekh Agarwal, Tong Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02486.txt.
Description
Chenlu Ye and co-authors build, in a 2025 paper, a bandit algorithm that does not break when rewards swing wildly. Bandit methods learn by trial which option pays best in each context. Standard versions assume rewards stay inside a known range, and their cost grows fast when that range is huge. Real rewards, though, often have heavy tails: rare, enormous values that wreck averages.
Their approach borrows a robust estimator from statistics, named for Catoni, which trims the pull of extremes. With known reward variance, the method's regret, its loss versus the best policy, grows only with the true variance and barely with the range. A peeling variant drops the need to know the variance at all. A matching lower bound shows the main term cannot be beaten.
Catalog record
| CREATOR | Chenlu Ye, Yujia Jin, Alekh Agarwal, Tong Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 149 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-02486