Strategic Linear Contextual Bandits
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929515740004352 |
|---|---|
| author | Buening, Thomas Kleine Saha, Aadirupa Dimitrakakis, Christos Xu, Haifeng |
| author_facet | Buening, Thomas Kleine Saha, Aadirupa Dimitrakakis, Christos Xu, Haifeng |
| contents | Motivated by the phenomenon of strategic agents gaming a recommender system to maximize the number of times they are recommended to users, we study a strategic variant of the linear contextual bandit problem, where the arms can strategically misreport privately observed contexts to the learner. We treat the algorithm design problem as one of mechanism design under uncertainty and propose the Optimistic Grim Trigger Mechanism (OptGTM) that incentivizes the agents (i.e., arms) to report their contexts truthfully while simultaneously minimizing regret. We also show that failing to account for the strategic nature of the agents results in linear regret. However, a trade-off between mechanism design and regret minimization appears to be unavoidable. More broadly, this work aims to provide insight into the intersection of online learning and mechanism design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00551 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Strategic Linear Contextual Bandits Buening, Thomas Kleine Saha, Aadirupa Dimitrakakis, Christos Xu, Haifeng Machine Learning Computer Science and Game Theory Motivated by the phenomenon of strategic agents gaming a recommender system to maximize the number of times they are recommended to users, we study a strategic variant of the linear contextual bandit problem, where the arms can strategically misreport privately observed contexts to the learner. We treat the algorithm design problem as one of mechanism design under uncertainty and propose the Optimistic Grim Trigger Mechanism (OptGTM) that incentivizes the agents (i.e., arms) to report their contexts truthfully while simultaneously minimizing regret. We also show that failing to account for the strategic nature of the agents results in linear regret. However, a trade-off between mechanism design and regret minimization appears to be unavoidable. More broadly, this work aims to provide insight into the intersection of online learning and mechanism design. |
| title | Strategic Linear Contextual Bandits |
| topic | Machine Learning Computer Science and Game Theory |
| url | https://arxiv.org/abs/2406.00551 |