Threshold-Based Optimal Arm Selection in Monotonic Bandits: Regret Lower Bounds and Algorithms
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_ | 1866914017263484928 |
|---|---|
| author | Varude, Chanakya Chaudhary, Jay Kaushik, Siddharth Chaporkar, Prasanna |
| author_facet | Varude, Chanakya Chaudhary, Jay Kaushik, Siddharth Chaporkar, Prasanna |
| contents | In multi-armed bandit problems, the typical goal is to identify the arm with the highest reward. This paper explores a threshold-based bandit problem, aiming to select an arm based on its relation to a prescribed threshold \(τ\). We study variants where the optimal arm is the first above \(τ\), the \(k^{th}\) arm above or below it, or the closest to it, under a monotonic structure of arm means. We derive asymptotic regret lower bounds, showing dependence only on arms adjacent to \(τ\). Motivated by applications in communication networks (CQI allocation), clinical dosing, energy management, recommendation systems, and more. We propose algorithms with optimality validated through Monte Carlo simulations. Our work extends classical bandit theory with threshold constraints for efficient decision-making. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02119 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Threshold-Based Optimal Arm Selection in Monotonic Bandits: Regret Lower Bounds and Algorithms Varude, Chanakya Chaudhary, Jay Kaushik, Siddharth Chaporkar, Prasanna Machine Learning In multi-armed bandit problems, the typical goal is to identify the arm with the highest reward. This paper explores a threshold-based bandit problem, aiming to select an arm based on its relation to a prescribed threshold \(τ\). We study variants where the optimal arm is the first above \(τ\), the \(k^{th}\) arm above or below it, or the closest to it, under a monotonic structure of arm means. We derive asymptotic regret lower bounds, showing dependence only on arms adjacent to \(τ\). Motivated by applications in communication networks (CQI allocation), clinical dosing, energy management, recommendation systems, and more. We propose algorithms with optimality validated through Monte Carlo simulations. Our work extends classical bandit theory with threshold constraints for efficient decision-making. |
| title | Threshold-Based Optimal Arm Selection in Monotonic Bandits: Regret Lower Bounds and Algorithms |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2509.02119 |