TY - GEN
T1 - Time-Varying Gaussian Process Bandit Optimization with Experts
T2 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2025
AU - Mauduit, Eliabelle
AU - Berthier, Eloïse
AU - Simonetto, Andrea
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.
PY - 2026/1/1
Y1 - 2026/1/1
N2 - 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.
AB - 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.
KW - Bandit feedback
KW - Gaussian Processes
KW - Sparse inference
KW - Time-varying optimization
KW - Upper confidence bounds
UR - https://www.scopus.com/pages/publications/105018670174
U2 - 10.1007/978-3-032-06096-9_10
DO - 10.1007/978-3-032-06096-9_10
M3 - Conference contribution
AN - SCOPUS:105018670174
SN - 9783032060952
T3 - Lecture Notes in Computer Science
SP - 164
EP - 182
BT - Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2025, Proceedings
A2 - Ribeiro, Rita P.
A2 - Soares, Carlos
A2 - Gama, João
A2 - Pfahringer, Bernhard
A2 - Japkowicz, Nathalie
A2 - Larrañaga, Pedro
A2 - Jorge, Alípio M.
A2 - Abreu, Pedro H.
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 15 September 2025 through 19 September 2025
ER -