Multi-thresholding Good Arm Identification with Bandit Feedback
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909661211394048 |
|---|---|
| author | Jiang, Xuanke Hashima, Sherief Hatano, Kohei Takimoto, Eiji |
| author_facet | Jiang, Xuanke Hashima, Sherief Hatano, Kohei Takimoto, Eiji |
| contents | We consider a good arm identification problem in a stochastic bandit setting with multi-objectives, where each arm $i \in [K]$ is associated with a distribution $D_i$ defined over $R^M$. For each round $t$, the player pulls an arm $i_t$ and receives an $M$-dimensional reward vector sampled according to $D_{i_t}$. The goal is to find, with high probability, an $ε$-good arm whose expected reward vector is larger than $\bmξ - ε\mathbf{1}$, where $\bmξ$ is a predefined threshold vector, and the vector comparison is component-wise. We propose the Multi-Thresholding UCB~(MultiTUCB) algorithm with a sample complexity bound. Our bound matches the existing one in the special case where $M=1$ and $ε=0$. The proposed algorithm demonstrates superior performance compared to baseline approaches across synthetic and real datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10386 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-thresholding Good Arm Identification with Bandit Feedback Jiang, Xuanke Hashima, Sherief Hatano, Kohei Takimoto, Eiji Machine Learning We consider a good arm identification problem in a stochastic bandit setting with multi-objectives, where each arm $i \in [K]$ is associated with a distribution $D_i$ defined over $R^M$. For each round $t$, the player pulls an arm $i_t$ and receives an $M$-dimensional reward vector sampled according to $D_{i_t}$. The goal is to find, with high probability, an $ε$-good arm whose expected reward vector is larger than $\bmξ - ε\mathbf{1}$, where $\bmξ$ is a predefined threshold vector, and the vector comparison is component-wise. We propose the Multi-Thresholding UCB~(MultiTUCB) algorithm with a sample complexity bound. Our bound matches the existing one in the special case where $M=1$ and $ε=0$. The proposed algorithm demonstrates superior performance compared to baseline approaches across synthetic and real datasets. |
| title | Multi-thresholding Good Arm Identification with Bandit Feedback |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2503.10386 |