论文标题
记忆力有限的探索：用于抛售硬币，嘈杂比较和多臂匪徒的流算法
Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
论文作者
论文摘要
考虑以下抽象硬币抛弃问题：给定一组$ n $偏见的$ N $硬币，请使用最少数量的硬币折腾找到最有偏见的硬币。这是理论计算机科学和机器学习中各种探索问题的普遍抽象，并且多年来已经进行了广泛的研究。特别是，具有最佳样本复杂性（硬币量数）的算法已有很长时间了。 通过应用程序进行大量数据集的应用，我们研究了解决此问题的空间复杂性，并使用流媒体模型中的最佳硬币投掷数量。在此模型中，硬币是一个一个逐一到达的，并且算法只能在任何点存储有限数量的硬币 - 存储器中不存在的任何硬币都会丢失，并且不能再抛弃或将其与到达硬币进行比较。对于最佳样本复杂性，将硬币抛弃问题的先前算法基于迭代消除硬币，该硬币固有地需要存储所有硬币，从而导致内存的信息流式流媒体算法。 We remedy this state-of-affairs by presenting a series of improved streaming algorithms for this problem: we start with a simple algorithm which require storing only $O(\log{n})$ coins and then iteratively refine it further and further, leading to algorithms with $O(\log\log{(n)})$ memory, $O(\log^*{(n)})$ memory, and最后，一个只在内存中存储一个额外硬币的一个 - 仅在整个流中存储最佳硬币所需的确切空间。 此外，我们将算法扩展到找到$ k $最有偏见的硬币以及其他探索问题的问题，例如使用嘈杂的比较查找顶级$ k $元素，或在随机多臂bastits中找到$ε$ best手臂，并获得这些问题的有效流算法。
Consider the following abstract coin tossing problem: Given a set of $n$ coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a common abstraction of various exploration problems in theoretical computer science and machine learning and has been studied extensively over the years. In particular, algorithms with optimal sample complexity (number of coin tosses) have been known for this problem for quite some time. Motivated by applications to processing massive datasets, we study the space complexity of solving this problem with optimal number of coin tosses in the streaming model. In this model, the coins are arriving one by one and the algorithm is only allowed to store a limited number of coins at any point -- any coin not present in the memory is lost and can no longer be tossed or compared to arriving coins. Prior algorithms for the coin tossing problem with optimal sample complexity are based on iterative elimination of coins which inherently require storing all the coins, leading to memory-inefficient streaming algorithms. We remedy this state-of-affairs by presenting a series of improved streaming algorithms for this problem: we start with a simple algorithm which require storing only $O(\log{n})$ coins and then iteratively refine it further and further, leading to algorithms with $O(\log\log{(n)})$ memory, $O(\log^*{(n)})$ memory, and finally a one that only stores a single extra coin in memory -- the same exact space needed to just store the best coin throughout the stream. Furthermore, we extend our algorithms to the problem of finding the $k$ most biased coins as well as other exploration problems such as finding top-$k$ elements using noisy comparisons or finding an $ε$-best arm in stochastic multi-armed bandits, and obtain efficient streaming algorithms for these problems.
