State-Aware Value Function Approximation with Attention Mechanism for Restless Multi-armed Bandits

Wu, Shuang; Zhao, Jingyu; Tian, Guangjian; Wang, Jun

doi:10.24963/ijcai.2021/64

State-Aware Value Function Approximation with Attention Mechanism for Restless Multi-armed Bandits

Shuang Wu, Jingyu Zhao, Guangjian Tian, Jun Wang

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 458-464.

https://doi.org/10.24963/ijcai.2021/64

Keywords

Agent-based and Multi-agent Systems: Resource Allocation
Agent-based and Multi-agent Systems: Multi-agent Planning
Planning and Scheduling: Markov Decisions Processes
Planning and Scheduling: Planning and Scheduling

Abstract

The restless multi-armed bandit (RMAB) problem is a generalization of the multi-armed bandit with non-stationary rewards. Its optimal solution is intractable due to exponentially large state and action spaces with respect to the number of arms. Existing approximation approaches, e.g., Whittle's index policy, have difficulty in capturing either temporal or spatial factors such as impacts from other arms. We propose considering both factors using the attention mechanism, which has achieved great success in deep learning. Our state-aware value function approximation solution comprises an attention-based value function approximator and a Bellman equation solver. The attention-based coordination module capture both spatial and temporal factors for arm coordination. The Bellman equation solver utilizes the decoupling structure of RMABs to acquire solutions with significantly reduced computation overheads. In particular, the time complexity of our approximation is linear in the number of arms. Finally, we illustrate the effectiveness and investigate the properties of our proposed method with numerical experiments.

Shuang Wu, Jingyu Zhao, Guangjian Tian, and Jun Wang. 2021. State-Aware Value Function Approximation with Attention Mechanism for Restless Multi-armed Bandits. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 458–464. https://doi.org/10.24963/ijcai.2021/64

@inproceedings{ijcai2021p64,
  title     = {State-Aware Value Function Approximation with Attention Mechanism for Restless Multi-armed Bandits},
  author    = {Wu, Shuang and Zhao, Jingyu and Tian, Guangjian and Wang, Jun},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {458--464},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/64},
  url       = {https://doi.org/10.24963/ijcai.2021/64},
}

TY  - CPAPER
TI  - State-Aware Value Function Approximation with Attention Mechanism for Restless Multi-armed Bandits
AU  - Wu, Shuang
AU  - Zhao, Jingyu
AU  - Tian, Guangjian
AU  - Wang, Jun
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 458
EP  - 464
DO  - 10.24963/ijcai.2021/64
UR  - https://doi.org/10.24963/ijcai.2021/64
ER  -