2018/01/04 by Kesav Kaza, Rahul Meshram, Kaza, Kesav +5 · 1 citation
Decision Sciences · Engineering · Computer Science · #Advanced Bandit Algorithms Research #Smart Grid Energy Management #Cognitive Radio Networks and Spectrum Sensing
paper · pdf · doi:10.48550/arxiv.1801.01301
This work studies a generalized class of restless multi-armed bandits with\nhidden states and allow cumulative feedback, as opposed to the conventional\ninstantaneous feedback. We call them lazy restless bandits (LRB) as the events\nof decision-making are sparser than events of state transition. Hence, feedback\nafter each decision event is the cumulative effect of the following state\ntransition events. The states of arms are hidden from the decision-maker and\nrewards for actions are state dependent. The decision-maker needs to choose one\narm in each decision interval, such that long term cumulative reward is\nmaximized.\n As the states are hidden, the decision-maker maintains and updates its belief\nabout them. It is shown that LRBs admit an optimal policy which has threshold\nstructure in belief space. The Whittle-index policy for solving LRB problem is\nanalyzed; indexability of LRBs is shown. Further, closed-form index expressions\nare provided for two sets of special cases; for more general cases, an\nalgorithm for index computation is provided. An extensive simulation study is\npresented; Whittle-index, modified Whittle-index and myopic policies are\ncompared. Lagrangian relaxation of the problem provides an upper bound on the\noptimal value function; it is used to assess the degree of sub-optimality\nvarious policies.\n