---
title: "Budgeted Multi-Armed Bandits with Multiple Plays"
authors:
  - "Yingce Xia"
  - "Tao Qin"
  - "Weidong Ma"
  - "Nenghai Yu"
  - "Tie-Yan Liu"
doi: ""
url: "https://ijcai.org/proceedings/2016/315"
pdf: "https://ijcai.org/proceedings/2016/0315.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "2210-2215"
track: ""
keywords:
---

# Budgeted Multi-Armed Bandits with Multiple Plays

Yingce Xia, Tao Qin, Weidong Ma, Nenghai Yu, Tie-Yan Liu

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 2210-2215.

## Abstract

We study the multi-play budgeted multi-armed bandit (MP-BMAB) problem, in which pulling an arm receives both a random reward and a random cost, and a player pulls L( ≥ 1) arms at each round. The player targets at maximizing her total expected reward under a budget constraint B for the pulling costs. We present a multiple ratio confidence bound policy: At each round, we first calculate a truncated upper (lower) confidence bound for the expected reward (cost) of each arm, and then pull the L arms with the maximum ratio of the sum of the upper confidence bounds of rewards to the sum of the lower confidence bounds of costs. We design 0-1 integer linear fractional programming oracle that can pick such the L arms within polynomial time. We prove that the regret of our policy is sublinear in general and is log-linear for certain parameter settings. We further consider two special cases of MP-BMABs: (1) We derive a lower bound for any consistent policy for MP-BMABs with Bernoulli reward and cost distributions. (2) We show that the proposed policy can also solve conventional budgeted MAB problem (a special case of MP-BMABs with L = 1) and provides better theoretical results than existing UCB-based pulling policies.