2021/03/08 by Aditya Mate, Mate, Aditya, Arpita Biswas +7 · 1 citation
Decision Sciences · #Advanced Bandit Algorithms Research
paper · pdf · doi:10.48550/arxiv.2103.04730
We propose Streaming Bandits, a Restless Multi Armed Bandit (RMAB) framework\nin which heterogeneous arms may arrive and leave the system after staying on\nfor a finite lifetime. Streaming Bandits naturally capture the health\nintervention planning problem, where health workers must manage the health\noutcomes of a patient cohort while new patients join and existing patients\nleave the cohort each day. Our contributions are as follows: (1) We derive\nconditions under which our problem satisfies indexability, a precondition that\nguarantees the existence and asymptotic optimality of the Whittle Index\nsolution for RMABs. We establish the conditions using a polytime reduction of\nthe Streaming Bandit setup to regular RMABs. (2) We further prove a phenomenon\nthat we call index decay, whereby the Whittle index values are low for short\nresidual lifetimes driving the intuition underpinning our algorithm. (3) We\npropose a novel and efficient algorithm to compute the index-based solution for\nStreaming Bandits. Unlike previous methods, our algorithm does not rely on\nsolving the costly finite horizon problem on each arm of the RMAB, thereby\nlowering the computational complexity compared to existing methods. (4)\nFinally, we evaluate our approach via simulations run on realworld data sets\nfrom a tuberculosis patient monitoring task and an intervention planning task\nfor improving maternal healthcare, in addition to other synthetic domains.\nAcross the board, our algorithm achieves a 2-orders-of-magnitude speed-up over\nexisting methods while maintaining the same solution quality.\n