### Abstract

We study the problem of selecting K arms with the highest expected rewards in a stochastic n-armed bandit game. This problem has a wide range of applications, e.g., A/B testing, crowd-sourcing, simulation optimization. Our goal is to develop a PAC algorithm, which, with probability at least 1 - δ, identifies a set of K arms with the aggregate regret at most e. The notion of aggregate regret for multiple-arm identification was first introduced in Zhou et al. (2014), which is defined as the difference of the averaged expected rewards between the selected set of arms and the best K arms. In contrast to Zhou et al. (2014) that only provides instance-independent sample complexity, we introduce a new hardness parameter for characterizing the difficulty of any given instance. We further develop two algorithms and establish the corresponding sample complexity in terms of this hardness parameter. The derived sample complexity can be significantly smaller than state-of-the-art results for a large class of instances and matches the instance-independent lower bound upto a log(e^{-1}) factor in the worst case. We also prove a lower bound result showing that the extra log(ϵ^{-1}) is necessary for instance-dependent algorithms using the introduced hardness parameter.

Original language | English (US) |
---|---|

Title of host publication | 34th International Conference on Machine Learning, ICML 2017 |

Publisher | International Machine Learning Society (IMLS) |

Pages | 1202-1210 |

Number of pages | 9 |

ISBN (Electronic) | 9781510855144 |

State | Published - Jan 1 2017 |

Externally published | Yes |

Event | 34th International Conference on Machine Learning, ICML 2017 - Sydney, Australia Duration: Aug 6 2017 → Aug 11 2017 |

### Publication series

Name | 34th International Conference on Machine Learning, ICML 2017 |
---|---|

Volume | 2 |

### Other

Other | 34th International Conference on Machine Learning, ICML 2017 |
---|---|

Country | Australia |

City | Sydney |

Period | 8/6/17 → 8/11/17 |

### Fingerprint

### ASJC Scopus subject areas

- Computational Theory and Mathematics
- Human-Computer Interaction
- Software

### Cite this

*34th International Conference on Machine Learning, ICML 2017*(pp. 1202-1210). (34th International Conference on Machine Learning, ICML 2017; Vol. 2). International Machine Learning Society (IMLS).

**Adaptive multiple-arm identification.** / Chen, Jiecao; Chen, Xi; Zhang, Qin; Zhou, Yuan.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*34th International Conference on Machine Learning, ICML 2017.*34th International Conference on Machine Learning, ICML 2017, vol. 2, International Machine Learning Society (IMLS), pp. 1202-1210, 34th International Conference on Machine Learning, ICML 2017, Sydney, Australia, 8/6/17.

}

TY - GEN

T1 - Adaptive multiple-arm identification

AU - Chen, Jiecao

AU - Chen, Xi

AU - Zhang, Qin

AU - Zhou, Yuan

PY - 2017/1/1

Y1 - 2017/1/1

N2 - We study the problem of selecting K arms with the highest expected rewards in a stochastic n-armed bandit game. This problem has a wide range of applications, e.g., A/B testing, crowd-sourcing, simulation optimization. Our goal is to develop a PAC algorithm, which, with probability at least 1 - δ, identifies a set of K arms with the aggregate regret at most e. The notion of aggregate regret for multiple-arm identification was first introduced in Zhou et al. (2014), which is defined as the difference of the averaged expected rewards between the selected set of arms and the best K arms. In contrast to Zhou et al. (2014) that only provides instance-independent sample complexity, we introduce a new hardness parameter for characterizing the difficulty of any given instance. We further develop two algorithms and establish the corresponding sample complexity in terms of this hardness parameter. The derived sample complexity can be significantly smaller than state-of-the-art results for a large class of instances and matches the instance-independent lower bound upto a log(e-1) factor in the worst case. We also prove a lower bound result showing that the extra log(ϵ-1) is necessary for instance-dependent algorithms using the introduced hardness parameter.

AB - We study the problem of selecting K arms with the highest expected rewards in a stochastic n-armed bandit game. This problem has a wide range of applications, e.g., A/B testing, crowd-sourcing, simulation optimization. Our goal is to develop a PAC algorithm, which, with probability at least 1 - δ, identifies a set of K arms with the aggregate regret at most e. The notion of aggregate regret for multiple-arm identification was first introduced in Zhou et al. (2014), which is defined as the difference of the averaged expected rewards between the selected set of arms and the best K arms. In contrast to Zhou et al. (2014) that only provides instance-independent sample complexity, we introduce a new hardness parameter for characterizing the difficulty of any given instance. We further develop two algorithms and establish the corresponding sample complexity in terms of this hardness parameter. The derived sample complexity can be significantly smaller than state-of-the-art results for a large class of instances and matches the instance-independent lower bound upto a log(e-1) factor in the worst case. We also prove a lower bound result showing that the extra log(ϵ-1) is necessary for instance-dependent algorithms using the introduced hardness parameter.

UR - http://www.scopus.com/inward/record.url?scp=85045580675&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045580675&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85045580675

T3 - 34th International Conference on Machine Learning, ICML 2017

SP - 1202

EP - 1210

BT - 34th International Conference on Machine Learning, ICML 2017

PB - International Machine Learning Society (IMLS)

ER -