Exploration with Limited Memory - Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits

Dive into a 24-minute conference talk exploring streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits with limited memory. Learn about the naive algorithm, median elimination, and sample complexity before delving into the streaming coin tossing problem. Discover how this perspective twist relates to memory limitations and compare it with the naive approach. Explore noisy comparisons and multi-armed bandits, understanding key concepts and notations. Gain insights into budgeting techniques and analyze the GAME-OF-COINS algorithm. Conclude with an overview of the Top-k Coins Algorithm and a comprehensive summary of the presented concepts.