No-regret optimization of time-varying bilevel problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910239994937344 |
|---|---|
| author | Mauduit, Eliabelle Berthier, Eloïse Simonetto, Andrea |
| author_facet | Mauduit, Eliabelle Berthier, Eloïse Simonetto, Andrea |
| contents | Bilevel optimization problems arise in many applications where decisions must account for the optimal response of another system, such as in game-theoretic settings. However, these problems are notoriously challenging, as even linear bilevel programs are strongly NP-hard. In this work, we consider bilevel optimization with a known upper-level objective and an unknown, potentially time-varying lower-level response, accessible only through noisy zeroth-order observations. We propose W-SparQ-BL, a Bayesian optimization framework that models the lower-level mapping using multi-output Gaussian processes and enables efficient optimization under uncertainty. Our approach leverages a sparse, observation-based approximation to control the effect of noise and temporal variability, while requiring only limited access to additional information over time. We establish regularity results linking the lower-level response to standard RKHS assumptions for common kernels, including Matérn and squared exponential. We prove that W-SparQ-BL achieves sublinear dynamic regret in both stationary and time-varying settings. Experiments on representative time-varying game-theoretic problems demonstrate the effectiveness of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_20962 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | No-regret optimization of time-varying bilevel problems Mauduit, Eliabelle Berthier, Eloïse Simonetto, Andrea Optimization and Control Bilevel optimization problems arise in many applications where decisions must account for the optimal response of another system, such as in game-theoretic settings. However, these problems are notoriously challenging, as even linear bilevel programs are strongly NP-hard. In this work, we consider bilevel optimization with a known upper-level objective and an unknown, potentially time-varying lower-level response, accessible only through noisy zeroth-order observations. We propose W-SparQ-BL, a Bayesian optimization framework that models the lower-level mapping using multi-output Gaussian processes and enables efficient optimization under uncertainty. Our approach leverages a sparse, observation-based approximation to control the effect of noise and temporal variability, while requiring only limited access to additional information over time. We establish regularity results linking the lower-level response to standard RKHS assumptions for common kernels, including Matérn and squared exponential. We prove that W-SparQ-BL achieves sublinear dynamic regret in both stationary and time-varying settings. Experiments on representative time-varying game-theoretic problems demonstrate the effectiveness of our approach. |
| title | No-regret optimization of time-varying bilevel problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.20962 |