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.
Code (0)
등록된 구현이 없습니다.
Tasks
Active LearningBinary ClassificationGeneral ClassificationSimilar Papers 제목 키워드 기반
Peer-inspired Student Performance Prediction in Interactive Online Question Pools with Graph Neural Network
Student performance prediction is critical to online education. It can benefit many downstream tasks on online learning platforms, such as estimating dropout rates, facilitating strategic intervention, and enabling adapt…
Graph Neural NetworkPredictionClaw-R1: A Step-Level Data Middleware System for Agentic Reinforcement Learning
Agentic reinforcement learning (RL) has become an important post-training paradigm for turning LLMs from static chatbots into interactive agents, giving rise to representative applications such as OpenClaw. Existing work…
Reinforcement LearningStructure-aware Interactive Graph Neural Networks for the Prediction of Protein-Ligand Binding Affinity
Drug discovery often relies on the successful prediction of protein-ligand binding affinity. Recent advances have shown great promise in applying graph neural networks (GNNs) for better affinity prediction by learning th…
Drug DiscoveryGraph AttentionGraph Neural NetworkProtein-Ligand Affinity PredictionNeural Active Learning Beyond Bandits
We study both stream-based and pool-based active learning with neural network approximations. A recent line of works proposed bandit-based approaches that transformed active learning into a bandit problem, achieving both…
Active LearningFleet-DAgger: Interactive Robot Fleet Learning with Scalable Human Supervision
Commercial and industrial deployments of robot fleets at Amazon, Nimble, Plus One, Waymo, and Zoox query remote human teleoperators when robots are at risk or unable to make task progress. With continual learning, interv…
Continual LearningGPU