Nima Akbarzadeh

openreview.net

Conditions for indexability of restless bandits and an algorithm to compute whittle index – CORRIGENDUM

Nima Akbarzadeh

2023-06-09

Advances in Applied Probability (publié)

On learning Whittle index policy for restless bandits with scalable regret

Nima Akbarzadeh

Reinforcement learning is an attractive approach to learn good resource allocation and scheduling policies based on data when the system mod… (voir plus)el is unknown. However, the cumulative regret of most RL algorithms scales as ˜ O(S

2023-01-01

IEEE Transactions on Control of Network Systems (publié)

Partially observable restless bandits with restarts: indexability and computation of Whittle index

Nima Akbarzadeh

We consider restless bandits with restarts, where the state of the active arms resets according to a known probability distribution while th… (voir plus)e state of the passive arms evolves in a Markovian manner. We assume that the state of the arm is observed after it is reset but not observed otherwise. We show that the model is indexable and propose an efficient algorithm to compute the Whittle index by exploiting the qualitative properties of the optimal policy. A detailed numerical study of machine repair models shows that Whittle index policy outperforms myopic policy and is close to optimal policy.

2022-12-06

IEEE Conference on Decision and Control (publié)

Conditions for indexability of restless bandits and an
$\mathcal{O}\!\left(K^3\right)$
algorithm to compute Whittle index

Nima Akbarzadeh

Abstract Restless bandits are a class of sequential resource allocation problems concerned with allocating one or more resources among sever… (voir plus)al alternative processes where the evolution of the processes depends on the resources allocated to them. Such models capture the fundamental trade-offs between exploration and exploitation. In 1988, Whittle developed an index heuristic for restless bandit problems which has emerged as a popular solution approach because of its simplicity and strong empirical performance. The Whittle index heuristic is applicable if the model satisfies a technical condition known as indexability. In this paper, we present two general sufficient conditions for indexability and identify simpler-to-verify refinements of these conditions. We then revisit a previously proposed algorithm called the adaptive greedy algorithm which is known to compute the Whittle index for a sub-class of restless bandits. We show that a generalization of the adaptive greedy algorithm computes the Whittle index for all indexable restless bandits. We present an efficient implementation of this algorithm which can compute the Whittle index of a restless bandit with K states in

2022-06-14

Advances in Applied Probability (publié)

On learning Whittle index policy for restless bandits with scalable regret

Nima Akbarzadeh

Reinforcement learning is an attractive approach to learn good resource allocation and scheduling policies based on data when the system mod… (voir plus)el is unknown. However, the cumulative regret of most RL algorithms scales as

2022-02-07

ArXiv (preprint)

Scalable Operator Allocation for Multirobot Assistance: A Restless Bandit Approach

Abhinav Dahiya

Nima Akbarzadeh

Stephen L. Smith

In this article, we consider the problem of allocating human operators in a system with multiple semiautonomous robots. Each robot is requir… (voir plus)ed to perform an independent sequence of tasks, subject to a chance of failing and getting stuck in a fault state at every task. If and when required, a human operator can assist or teleoperate a robot. Conventional dynamic programming-based techniques used to solve such problems face scalability issues due to an exponential growth of state and action spaces with the number of robots and operators. In this article, we derive conditions under which the operator allocation problem satisfies a technical condition called indexability, thereby enabling the use of the Whittle index heuristic. The conditions are easy to check, and we show that they hold for a wide range of problems of interest. Our key insight is to leverage the structure of the value function of individual robots, resulting in conditions that can be verified separately for each state of each robot. We apply these conditions to two types of transitions commonly seen in remote robot supervision systems. Through numerical simulations, we demonstrate the efficacy of Whittle index policy as a near-optimal and scalable approach that outperforms existing scalable methods.

2022-01-01

IEEE Transactions on Control of Network Systems (publié)

Two Families of Indexable Partially Observable Restless Bandits and Whittle Index Computation

Nima Akbarzadeh

2022-01-01

SSRN Electronic Journal (publié)

Maintenance of a collection of machines under partial observability: Indexability and computation of Whittle index

Nima Akbarzadeh

We consider the problem of scheduling maintenance for a collection of machines under partial observations when the state of each machine det… (voir plus)eriorates stochastically in a Markovian manner. We consider two observational models: first, the state of each machine is not observable at all, and second, the state of each machine is observable only if a service-person visits them. The agent takes a maintenance action, e.g., machine replacement, if he is chosen for the task. We model both problems as restless multi-armed bandit problem and propose the Whittle index policy for scheduling the visits. We show that both models are indexable. For the first model, we derive a closed-form expression for the Whittle index. For the second model, we propose an efficient algorithm to compute the Whittle index by exploiting the qualitative properties of the optimal policy. We present detailed numerical experiments which show that for multiple instances of the model, the Whittle index policy outperforms myopic policy and can be close-to-optimal in different setups.

2021-04-12

arXiv.org (prépublication)

dblp.uni-trier.de

Restless bandits: indexability and computation of Whittle index

Nima Akbarzadeh

Restless bandits are a class of sequential resource allocation problems concerned with allocating one or more resources among several altern… (voir plus)ative processes where the evolution of the process depends on the resource allocated to them. Such models capture the fundamental trade-offs between exploration and exploitation. In 1988, Whittle developed an index heuristic for restless bandit problems which has emerged as a popular solution approach due to its simplicity and strong empirical performance. The Whittle index heuristic is applicable if the model satisfies a technical condition known as indexability. In this paper, we present two general sufficient conditions for indexability and identify simpler to verify refinements of these conditions. We then present a general algorithm to compute Whittle index for indexable restless bandits. Finally, we present a detailed numerical study which affirms the strong performance of the Whittle index heuristic.

2020-06-01

arXiv.org (prépublication)

dblp.uni-trier.de

Restless bandits with controlled restarts: Indexability and computation of Whittle index

Nima Akbarzadeh

Motivated by applications in machine repair, queueing, surveillance, and clinic care, we consider a scheduling problem where a decision make… (voir plus)r can reset m out of n Markov processes at each time. Processes that are reset, restart according to a known probability distribution and processes that are not reset, evolve in a Markovian manner. Due to the high complexity of finding an optimal policy, such scheduling problems are often modeled as restless bandits. We show that the model satisfies a technical condition known as indexability. For indexable restless bandits, the Whittle index policy, which computes a function known as Whittle index for each process and resets the m processes with the lowest index, is known to be a good heuristic. The Whittle index is computed by solving an auxiliary Markov decision problem for each arm. When the optimal policy for this auxiliary problem is threshold based, we use ideas from renewal theory to derive closed form expression for the Whittle index. We present detailed numerical experiments which suggest that Whittle index policy performs close to the optimal policy and performs significantly better than myopic policy, which is a commonly used heuristic.

2019-12-01

IEEE Conference on Decision and Control (publié)

Dynamic spectrum access under partial observations: A restless bandit approach

Nima Akbarzadeh

We consider a communication system where multiple unknown channels are available for transmission. Each channel is a channel with state whic… (voir plus)h evolves in a Markov manner. The transmitter has to select L channels to use and also decide the resources (e.g., power, rate, etc.) to use for each of the selected channels. It observes the state of the channels it uses and receives no feedback on the state of the other channels. We model this problem as a partially observable Markov decision process and obtain a simplified belief state. We show that the optimal resource allocation policy can be identified in closed form. Once the optimal resource allocation policy is fixed, choosing the channel scheduling policy may be viewed as a restless bandit. We present an efficient algorithm to check indexability and compute the Whittle index for each channel. When the model is indexable, the Whittle index policy, which transmits over the L channels with the smallest Whittle indices, is an attractive heuristic policy.

2019-06-01

Canadian Workshop on Information Theory (publié)