Sequential Decision Making with Limited Observation Capability: Application to Wireless Networks
For researchers in sequential decision-making under limited observation, this work extends restless bandit theory to a more realistic setting with cumulative feedback, but the results are incremental as they build on existing Whittle-index methods.
This paper introduces lazy restless bandits (LRB), a generalization of restless multi-armed bandits with hidden states and cumulative feedback, and shows that the optimal policy has a threshold structure in belief space. The Whittle-index policy is analyzed, indexability is proven, and closed-form index expressions are provided for special cases, with simulations showing near-optimal performance.
This work studies a generalized class of restless multi-armed bandits with hidden states and allow cumulative feedback, as opposed to the conventional instantaneous feedback. We call them lazy restless bandits (LRB) as the events of decision-making are sparser than events of state transition. Hence, feedback after each decision event is the cumulative effect of the following state transition events. The states of arms are hidden from the decision-maker and rewards for actions are state dependent. The decision-maker needs to choose one arm in each decision interval, such that long term cumulative reward is maximized. As the states are hidden, the decision-maker maintains and updates its belief about them. It is shown that LRBs admit an optimal policy which has threshold structure in belief space. The Whittle-index policy for solving LRB problem is analyzed; indexability of LRBs is shown. Further, closed-form index expressions are provided for two sets of special cases; for more general cases, an algorithm for index computation is provided. An extensive simulation study is presented; Whittle-index, modified Whittle-index and myopic policies are compared. Lagrangian relaxation of the problem provides an upper bound on the optimal value function; it is used to assess the degree of sub-optimality various policies.