Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces
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_ | 1866908550740049920 |
|---|---|
| author | Terenin, Alexander Negrea, Jeffrey |
| author_facet | Terenin, Alexander Negrea, Jeffrey |
| contents | We develop a form Thompson sampling for online learning under full feedback - also known as prediction with expert advice - where the learner's prior is defined over the space of an adversary's future actions, rather than the space of experts. We show regret decomposes into regret the learner expected a priori, plus a prior-robustness-type term we call excess regret. In the classical finite-expert setting, this recovers optimal rates. As an initial step towards practical online learning in settings with a potentially-uncountably-infinite number of experts, we show that Thompson sampling over the $d$-dimensional unit cube, using a certain Gaussian process prior widely-used in the Bayesian optimization literature, has a $\mathcal{O}\Big(β\sqrt{Td\log(1+\sqrt{d}\fracλβ)}\Big)$ rate against a $β$-bounded $λ$-Lipschitz adversary. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14790 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces Terenin, Alexander Negrea, Jeffrey Machine Learning Computer Science and Game Theory Statistics Theory We develop a form Thompson sampling for online learning under full feedback - also known as prediction with expert advice - where the learner's prior is defined over the space of an adversary's future actions, rather than the space of experts. We show regret decomposes into regret the learner expected a priori, plus a prior-robustness-type term we call excess regret. In the classical finite-expert setting, this recovers optimal rates. As an initial step towards practical online learning in settings with a potentially-uncountably-infinite number of experts, we show that Thompson sampling over the $d$-dimensional unit cube, using a certain Gaussian process prior widely-used in the Bayesian optimization literature, has a $\mathcal{O}\Big(β\sqrt{Td\log(1+\sqrt{d}\fracλβ)}\Big)$ rate against a $β$-bounded $λ$-Lipschitz adversary. |
| title | Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces |
| topic | Machine Learning Computer Science and Game Theory Statistics Theory |
| url | https://arxiv.org/abs/2502.14790 |