Constrained Restless Bandits for Dynamic Scheduling in Cyber-Physical Systems
This paper studies a class of constrained restless multi-armed bandits (CRMAB). The constraints are in the form of time varying set of actions (set of available arms). This variation can be either stochastic or semi-deterministic. Given a set of arms, a fixed number of them can be chosen to be played in each decision interval. The play of each arm yields a state dependent reward. The current states of arms are partially observable through binary feedback signals from arms that are played. The current availability of arms is fully observable. The objective is to maximize long term cumulative reward. The uncertainty about future availability of arms along with partial state information makes this objective challenging. Applications for CRMAB can be found in resource allocation in cyber-physical systems involving components with time varying availability. First, this optimization problem is analyzed using Whittle's index policy. To this end, a constrained restless single-armed bandit is studied. It is shown to admit a threshold-type optimal policy and is also indexable. An algorithm to compute Whittle's index is presented. An alternate solution method with lower complexity is also presented in the form of an online rollout policy. A detailed discussion on the complexity of both these schemes is also presented, which suggests that online rollout policy with short look ahead is simpler to implement than Whittle's index computation. Further, upper bounds on the value function are derived in order to estimate the degree of sub-optimality of various solutions. The simulation study compares the performance of Whittle's index, online rollout, myopic and modified Whittle's index policies.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingDecision Making Under UncertaintyMulti-Armed BanditsSchedulingSimilar Papers 제목 키워드 기반
Scheduling in Wireless Networks with Spatial Reuse of Spectrum as Restless Bandits
We study the problem of scheduling packet transmissions with the aim of minimizing the energy consumption and data transmission delay of users in a wireless network in which spatial reuse of spectrum is employed. We appr…
SchedulingPlanning and Learning in Risk-Aware Restless Multi-Arm Bandit Problem
In restless multi-arm bandits, a central agent is tasked with optimally distributing limited resources across several bandits (arms), with each arm being a Markov decision process. In this work, we generalize the traditi…
SchedulingThompson SamplingIndexability of Finite State Restless Multi-Armed Bandit and Rollout Policy
We consider finite state restless multi-armed bandit problem. The decision maker can act on M bandits out of N bandits in each time step. The play of arm (active arm) yields state dependent rewards based on action and wh…
Networked Restless Bandits with Positive Externalities
Restless multi-armed bandits are often used to model budget-constrained resource allocation tasks where receipt of the resource is associated with an increased probability of a favorable state transition. Prior work assu…
Multi-Armed BanditsFairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks
Motivated by applications such as machine repair, project monitoring, and anti-poaching patrol scheduling, we study intervention planning of stochastic processes under resource constraints. This planning problem has prev…
FairnessMulti-Armed BanditsScheduling