Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates
Sanghoon Yu, Min-hwan Oh · 2026
Read Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates by Sanghoon Yu, Min-hwan Oh (2026) 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-2606-00984.txt.
Description
Yu and Oh study bandit learning when updates must stay rare in this 2026 paper. In a linear contextual bandit, a learner sees a context, picks an action, and earns a reward. Real systems may fold feedback into their model only a few times. Past batched methods often freeze the action rule inside each interval as well. That extra freeze is a separate, stronger curb.
The pair give two practical algorithms that update parameters only on the order of log log T times. The first, BLCE-G, hits minimax optimal regret in both small and large action regimes at once. The second, BLCE, drops a costly design step that slowed prior methods. It keeps optimal regret and posts the lowest known run time among such methods. The ideas extend to generalized linear bandits with near optimal results.
Catalog record
| CREATOR | Sanghoon Yu, Min-hwan Oh |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 150 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.00984