Linear Bandits with Non-i.i.d. Noise
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_ | 1866908381185310720 |
|---|---|
| author | Abélès, Baptiste Clerico, Eugenio Flynn, Hamish Neu, Gergely |
| author_facet | Abélès, Baptiste Clerico, Eugenio Flynn, Hamish Neu, Gergely |
| contents | We study the linear stochastic bandit problem, relaxing the standard i.i.d. assumption on the observation noise. As an alternative to this restrictive assumption, we allow the noise terms across rounds to be sub-Gaussian but interdependent, with dependencies that decay over time. To address this setting, we develop new confidence sequences using a recently introduced reduction scheme to sequential probability assignment, and use these to derive a bandit algorithm based on the principle of optimism in the face of uncertainty. We provide regret bounds for the resulting algorithm, expressed in terms of the decay rate of the strength of dependence between observations. Among other results, we show that our bounds recover the standard rates up to a factor of the mixing time for geometrically mixing observation noise. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_20017 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear Bandits with Non-i.i.d. Noise Abélès, Baptiste Clerico, Eugenio Flynn, Hamish Neu, Gergely Machine Learning We study the linear stochastic bandit problem, relaxing the standard i.i.d. assumption on the observation noise. As an alternative to this restrictive assumption, we allow the noise terms across rounds to be sub-Gaussian but interdependent, with dependencies that decay over time. To address this setting, we develop new confidence sequences using a recently introduced reduction scheme to sequential probability assignment, and use these to derive a bandit algorithm based on the principle of optimism in the face of uncertainty. We provide regret bounds for the resulting algorithm, expressed in terms of the decay rate of the strength of dependence between observations. Among other results, we show that our bounds recover the standard rates up to a factor of the mixing time for geometrically mixing observation noise. |
| title | Linear Bandits with Non-i.i.d. Noise |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.20017 |