Time-varying Gaussian Process Bandit Optimization with Experts: no-regret in logarithmically-many side queries
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911229650403328 |
|---|---|
| author | Mauduit, Eliabelle Berthier, Eloïse Simonetto, Andrea |
| author_facet | Mauduit, Eliabelle Berthier, Eloïse Simonetto, Andrea |
| contents | We study a time-varying Bayesian optimization problem with bandit feedback, where the reward function belongs to a Reproducing Kernel Hilbert Space (RKHS). We approach the problem via an upper-confidence bound Gaussian Process algorithm, which has been proven to yield no-regret in the stationary case.
The time-varying case is more challenging and no-regret results are out of reach in general in the standard setting. As such, we instead tackle the question of how many additional observations asked to an expert are required to regain a no-regret property. To do so, we formulate the presence of past observation via an uncertainty injection procedure, and we reframe the problem as a heteroscedastic Gaussian Process regression. In addition, to achieve a no-regret result, we discard long outdated observations and replace them with updated (possibly very noisy) ones obtained by asking queries to an external expert. By leveraging and extending sparse inference to the heteroscedastic case, we are able to secure a no-regret result in a challenging time-varying setting with only logarithmically-many side queries per time step. Our method demonstrates that minimal additional information suffices to counteract temporal drift, ensuring efficient optimization despite time variation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21274 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Time-varying Gaussian Process Bandit Optimization with Experts: no-regret in logarithmically-many side queries Mauduit, Eliabelle Berthier, Eloïse Simonetto, Andrea Optimization and Control We study a time-varying Bayesian optimization problem with bandit feedback, where the reward function belongs to a Reproducing Kernel Hilbert Space (RKHS). We approach the problem via an upper-confidence bound Gaussian Process algorithm, which has been proven to yield no-regret in the stationary case. The time-varying case is more challenging and no-regret results are out of reach in general in the standard setting. As such, we instead tackle the question of how many additional observations asked to an expert are required to regain a no-regret property. To do so, we formulate the presence of past observation via an uncertainty injection procedure, and we reframe the problem as a heteroscedastic Gaussian Process regression. In addition, to achieve a no-regret result, we discard long outdated observations and replace them with updated (possibly very noisy) ones obtained by asking queries to an external expert. By leveraging and extending sparse inference to the heteroscedastic case, we are able to secure a no-regret result in a challenging time-varying setting with only logarithmically-many side queries per time step. Our method demonstrates that minimal additional information suffices to counteract temporal drift, ensuring efficient optimization despite time variation. |
| title | Time-varying Gaussian Process Bandit Optimization with Experts: no-regret in logarithmically-many side queries |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2510.21274 |