Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.24692 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908386261467136 |
|---|---|
| author | Everett, Derek Lu, Fred Raff, Edward Camacho, Fernando Holt, James |
| author_facet | Everett, Derek Lu, Fred Raff, Edward Camacho, Fernando Holt, James |
| contents | Canonical algorithms for multi-armed bandits typically assume a stationary reward environment where the size of the action space (number of arms) is small. More recently developed methods typically relax only one of these assumptions: existing non-stationary bandit policies are designed for a small number of arms, while Lipschitz, linear, and Gaussian process bandit policies are designed to handle a large (or infinite) number of arms in stationary reward environments under constraints on the reward function. In this manuscript, we propose a novel policy to learn reward environments over a continuous space using Gaussian interpolation. We show that our method efficiently learns continuous Lipschitz reward functions with $\mathcal{O}^*(\sqrt{T})$ cumulative regret. Furthermore, our method naturally extends to non-stationary problems with a simple modification. We finally demonstrate that our method is computationally favorable (100-10000x faster) and experimentally outperforms sliding Gaussian process policies on datasets with non-stationarity and an extremely large number of arms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_24692 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms Everett, Derek Lu, Fred Raff, Edward Camacho, Fernando Holt, James Machine Learning Canonical algorithms for multi-armed bandits typically assume a stationary reward environment where the size of the action space (number of arms) is small. More recently developed methods typically relax only one of these assumptions: existing non-stationary bandit policies are designed for a small number of arms, while Lipschitz, linear, and Gaussian process bandit policies are designed to handle a large (or infinite) number of arms in stationary reward environments under constraints on the reward function. In this manuscript, we propose a novel policy to learn reward environments over a continuous space using Gaussian interpolation. We show that our method efficiently learns continuous Lipschitz reward functions with $\mathcal{O}^*(\sqrt{T})$ cumulative regret. Furthermore, our method naturally extends to non-stationary problems with a simple modification. We finally demonstrate that our method is computationally favorable (100-10000x faster) and experimentally outperforms sliding Gaussian process policies on datasets with non-stationarity and an extremely large number of arms. |
| title | Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.24692 |