On reducing the order of arm-passes bandit streaming algorithms under memory bottleneck
In this work we explore multi-arm bandit streaming model, especially in cases where the model faces resource bottleneck. We build over existing algorithms conditioned by limited arm memory at any instance of time. Specifically, we improve the amount of streaming passes it takes for a bandit algorithm to incur a $O(\sqrt{T\log(T)})$ regret by a logarithmic factor, and also provide 2-pass algorithms with some initial conditions to incur a similar order of regret.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
We give a near-optimal sample-pass trade-off for pure exploration in multi-armed bandits (MABs) via multi-pass streaming algorithms: any streaming algorithm with sublinear memory that uses the optimal sample complexity o…
Multi-Armed BanditsA Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits
The stochastic $K$-armed bandit problem has been studied extensively due to its applications in various domains ranging from online advertising to clinical trials. In practice however, the number of arms can be very larg…
Tight Memory-Regret Lower Bounds for Streaming Bandits
In this paper, we investigate the streaming bandits problem, wherein the learner aims to minimize regret by dealing with online arriving arms and sublinear arm memory. We establish the tight worst-case regret lower bound…
Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems
We propose Streaming Bandits, a Restless Multi Armed Bandit (RMAB) framework in which heterogeneous arms may arrive and leave the system after staying on for a finite lifetime. Streaming Bandits naturally capture the hea…
Multi-Armed BanditsOn-the-fly learning of adaptive strategies with bandit algorithms
Automation of machine learning model development is increasingly becoming an established research area. While automated model selection and automated data pre-processing have been studied in depth, there is, however, a g…
Model Selection