Constrained Best Arm Identification in Grouped Bandits
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909424497459200 |
|---|---|
| author | Dharod, Sahil Sravani, Malyala Preethi Heda, Sakshi Moharir, Sharayu |
| author_facet | Dharod, Sahil Sravani, Malyala Preethi Heda, Sakshi Moharir, Sharayu |
| contents | We study a grouped bandit setting where each arm comprises multiple independent sub-arms referred to as attributes. Each attribute of each arm has an independent stochastic reward. We impose the constraint that for an arm to be deemed feasible, the mean reward of all its attributes should exceed a specified threshold. The goal is to find the arm with the highest mean reward averaged across attributes among the set of feasible arms in the fixed confidence setting. We first characterize a fundamental limit on the performance of any policy. Following this, we propose a near-optimal confidence interval-based policy to solve this problem and provide analytical guarantees for the policy. We compare the performance of the proposed policy with that of two suitably modified versions of action elimination via simulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_08031 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Constrained Best Arm Identification in Grouped Bandits Dharod, Sahil Sravani, Malyala Preethi Heda, Sakshi Moharir, Sharayu Machine Learning We study a grouped bandit setting where each arm comprises multiple independent sub-arms referred to as attributes. Each attribute of each arm has an independent stochastic reward. We impose the constraint that for an arm to be deemed feasible, the mean reward of all its attributes should exceed a specified threshold. The goal is to find the arm with the highest mean reward averaged across attributes among the set of feasible arms in the fixed confidence setting. We first characterize a fundamental limit on the performance of any policy. Following this, we propose a near-optimal confidence interval-based policy to solve this problem and provide analytical guarantees for the policy. We compare the performance of the proposed policy with that of two suitably modified versions of action elimination via simulations. |
| title | Constrained Best Arm Identification in Grouped Bandits |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2412.08031 |