Interactive algorithms: from pool to stream
  We consider interactive algorithms in the pool-based setting, and in the
stream-based setting. Interactive algorithms observe suggested elements
(representing actions or queries), and interactively select some of them and
receive responses. Pool-based algorithms can select elements at any order,
while stream-based algorithms observe elements in sequence, and can only select
elements immediately after observing them. We assume that the suggested
elements are generated independently from some source distribution, and ask
what is the stream size required for emulating a pool algorithm with a given
pool size. We provide algorithms and matching lower bounds for general pool
algorithms, and for utility-based pool algorithms. We further show that a
maximal gap between the two settings exists also in the special case of active
learning for binary classification.
