Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912064056852480 |
|---|---|
| author | Li, Kuan-Ta Hsieh, Ping-Chun Huang, Yu-Chih |
| author_facet | Li, Kuan-Ta Hsieh, Ping-Chun Huang, Yu-Chih |
| contents | The piecewise-stationary bandit problem is an important variant of the multi-armed bandit problem that further considers abrupt changes in the reward distributions. The main theme of the problem is the trade-off between exploration for detecting environment changes and exploitation of traditional bandit algorithms. While this problem has been extensively investigated, existing works either assume knowledge about the number of change points $M$ or require extremely high computational complexity. In this work, we revisit the piecewise-stationary bandit problem from a minimalist perspective. We propose a novel and generic exploration mechanism, called diminishing exploration, which eliminates the need for knowledge about $M$ and can be used in conjunction with an existing change detection-based algorithm to achieve near-optimal regret scaling. Simulation results show that despite oblivious of $M$, equipping existing algorithms with the proposed diminishing exploration generally achieves better empirical regret than the traditional uniform exploration. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_05734 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits Li, Kuan-Ta Hsieh, Ping-Chun Huang, Yu-Chih Machine Learning Information Theory The piecewise-stationary bandit problem is an important variant of the multi-armed bandit problem that further considers abrupt changes in the reward distributions. The main theme of the problem is the trade-off between exploration for detecting environment changes and exploitation of traditional bandit algorithms. While this problem has been extensively investigated, existing works either assume knowledge about the number of change points $M$ or require extremely high computational complexity. In this work, we revisit the piecewise-stationary bandit problem from a minimalist perspective. We propose a novel and generic exploration mechanism, called diminishing exploration, which eliminates the need for knowledge about $M$ and can be used in conjunction with an existing change detection-based algorithm to achieve near-optimal regret scaling. Simulation results show that despite oblivious of $M$, equipping existing algorithms with the proposed diminishing exploration generally achieves better empirical regret than the traditional uniform exploration. |
| title | Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits |
| topic | Machine Learning Information Theory |
| url | https://arxiv.org/abs/2410.05734 |