Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911639064805376 |
|---|---|
| author | Balcan, Maria-Florina Bernasconi, Martino Castiglioni, Matteo Celli, Andrea Harris, Keegan Wu, Zhiwei Steven |
| author_facet | Balcan, Maria-Florina Bernasconi, Martino Castiglioni, Matteo Celli, Andrea Harris, Keegan Wu, Zhiwei Steven |
| contents | We study the problem of online learning in Stackelberg games with side information between a leader and a sequence of followers. In every round the leader observes contextual information and commits to a mixed strategy, after which the follower best-responds. We provide learning algorithms for the leader which achieve $O(T^{1/2})$ regret under bandit feedback, an improvement from the previously best-known rates of $O(T^{2/3})$. Our algorithms rely on a reduction to linear contextual bandits in the utility space: In each round, a linear contextual bandit algorithm recommends a utility vector, which our algorithm inverts to determine the leader's mixed strategy. We extend our algorithms to the setting in which the leader's utility function is unknown, and also apply it to the problems of bidding in second-price auctions with side information and online Bayesian persuasion with public and private states. Finally, we observe that our algorithms empirically outperform previous results on numerical simulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_00204 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information Balcan, Maria-Florina Bernasconi, Martino Castiglioni, Matteo Celli, Andrea Harris, Keegan Wu, Zhiwei Steven Machine Learning Computer Science and Game Theory We study the problem of online learning in Stackelberg games with side information between a leader and a sequence of followers. In every round the leader observes contextual information and commits to a mixed strategy, after which the follower best-responds. We provide learning algorithms for the leader which achieve $O(T^{1/2})$ regret under bandit feedback, an improvement from the previously best-known rates of $O(T^{2/3})$. Our algorithms rely on a reduction to linear contextual bandits in the utility space: In each round, a linear contextual bandit algorithm recommends a utility vector, which our algorithm inverts to determine the leader's mixed strategy. We extend our algorithms to the setting in which the leader's utility function is unknown, and also apply it to the problems of bidding in second-price auctions with side information and online Bayesian persuasion with public and private states. Finally, we observe that our algorithms empirically outperform previous results on numerical simulations. |
| title | Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information |
| topic | Machine Learning Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.00204 |