Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting
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_ | 1866909466769752064 |
|---|---|
| author | Yahmed, Ahmed Ben Calauzènes, Clément Perchet, Vianney |
| author_facet | Yahmed, Ahmed Ben Calauzènes, Clément Perchet, Vianney |
| contents | We consider the classical multi-armed bandit problem, but with strategic arms. In this context, each arm is characterized by a bounded support reward distribution and strategically aims to maximize its own utility by potentially retaining a portion of its reward, and disclosing only a fraction of it to the learning agent. This scenario unfolds as a game over $T$ rounds, leading to a competition of objectives between the learning agent, aiming to minimize their regret, and the arms, motivated by the desire to maximize their individual utilities. To address these dynamics, we introduce a new mechanism that establishes an equilibrium wherein each arm behaves truthfully and discloses as much of its rewards as possible. With this mechanism, the agent can attain the second-highest average (true) reward among arms, with a cumulative regret bounded by $O(\log(T)/Δ)$ (problem-dependent) or $O(\sqrt{T\log(T)})$ (worst-case). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16018 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting Yahmed, Ahmed Ben Calauzènes, Clément Perchet, Vianney Machine Learning Computer Science and Game Theory We consider the classical multi-armed bandit problem, but with strategic arms. In this context, each arm is characterized by a bounded support reward distribution and strategically aims to maximize its own utility by potentially retaining a portion of its reward, and disclosing only a fraction of it to the learning agent. This scenario unfolds as a game over $T$ rounds, leading to a competition of objectives between the learning agent, aiming to minimize their regret, and the arms, motivated by the desire to maximize their individual utilities. To address these dynamics, we introduce a new mechanism that establishes an equilibrium wherein each arm behaves truthfully and discloses as much of its rewards as possible. With this mechanism, the agent can attain the second-highest average (true) reward among arms, with a cumulative regret bounded by $O(\log(T)/Δ)$ (problem-dependent) or $O(\sqrt{T\log(T)})$ (worst-case). |
| title | Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting |
| topic | Machine Learning Computer Science and Game Theory |
| url | https://arxiv.org/abs/2501.16018 |