Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917364232093696 |
|---|---|
| author | Cheng, Zhuoyu Hatano, Kohei Takimoto, Eiji |
| author_facet | Cheng, Zhuoyu Hatano, Kohei Takimoto, Eiji |
| contents | We study a class of adversarial bandit optimization problems in which the loss functions may be non-convex and non-smooth. In each round, the learner observes a loss that consists of an underlying linear component together with an additional perturbation applied after the learner selects an action. The perturbations are measured relative to the linear losses and are constrained by a global budget that bounds their cumulative magnitude over time. Under this model, we establish both expected and high-probability regret guarantees. As a special case of our analysis, we recover an improved high-probability regret bound for classical bandit linear optimization, which corresponds to the setting without perturbations. We further complement our upper bounds by proving a lower bound on the expected regret. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_26066 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses Cheng, Zhuoyu Hatano, Kohei Takimoto, Eiji Machine Learning We study a class of adversarial bandit optimization problems in which the loss functions may be non-convex and non-smooth. In each round, the learner observes a loss that consists of an underlying linear component together with an additional perturbation applied after the learner selects an action. The perturbations are measured relative to the linear losses and are constrained by a global budget that bounds their cumulative magnitude over time. Under this model, we establish both expected and high-probability regret guarantees. As a special case of our analysis, we recover an improved high-probability regret bound for classical bandit linear optimization, which corresponds to the setting without perturbations. We further complement our upper bounds by proving a lower bound on the expected regret. |
| title | Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2603.26066 |