Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits

DOI10.1137/19M1247115OpenAlexW3027847404MaRDI QIDQ5890034

Manish Raghavan, Jennifer Wortman Vaughan, Aleksandrs Slivkins, Zhiwei Steven Wu

Publication date: 28 April 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.10624

zbMATH Keywords

greedy algorithmsmoothed analysisdata diversitymultiarmed banditslinear banditsBayesian regret

Mathematics Subject Classification ID

Artificial intelligence (68T99)

Uses Software

• GitHub

Cites Work

• Unnamed Item
• Batched bandit problems
• User-friendly tail bounds for sums of random matrices
• Tail bounds for sums of geometric and exponential variables
• Adaptive estimation of a quadratic functional by model selection.
• The convex geometry of linear inverse problems
• Smoothed analysis of algorithms
• An elementary proof of a theorem of Johnson and Lindenstrauss
• 10.1162/153244303321897663
• Bandit Algorithms
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• Finite-time analysis of the multiarmed bandit problem

This page was built for publication: Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits