Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.10567 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915389805428736 |
|---|---|
| author | Christ, Miranda Reichman, Daniel Shafer, Jonathan |
| author_facet | Christ, Miranda Reichman, Daniel Shafer, Jonathan |
| contents | We study protocols for verifying approximate optimality of strategies in multi-armed bandits and normal-form games. As the number of actions available to each player is often large, we seek protocols where the number of queries to the utility oracle is sublinear in the number of actions. We prove that such verification is possible for sufficiently smooth strategies that do not put too much probability mass on any specific action. We provide protocols for verifying that a smooth policy for a multi-armed bandit is $\varepsilon$-optimal. Our verification protocols require provably fewer arm queries than learning. Furthermore, we establish a nearly-tight lower bound on the query complexity of verification in our settings. As an application, we show how to use verification for bandits to achieve verification in normal-form games. This gives a protocol for verifying whether a given strategy profile is an approximate strong smooth Nash equilibrium, with a query complexity that is sublinear in the number of actions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10567 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Protocols for Verifying Smooth Strategies in Bandits and Games Christ, Miranda Reichman, Daniel Shafer, Jonathan Computer Science and Game Theory Machine Learning We study protocols for verifying approximate optimality of strategies in multi-armed bandits and normal-form games. As the number of actions available to each player is often large, we seek protocols where the number of queries to the utility oracle is sublinear in the number of actions. We prove that such verification is possible for sufficiently smooth strategies that do not put too much probability mass on any specific action. We provide protocols for verifying that a smooth policy for a multi-armed bandit is $\varepsilon$-optimal. Our verification protocols require provably fewer arm queries than learning. Furthermore, we establish a nearly-tight lower bound on the query complexity of verification in our settings. As an application, we show how to use verification for bandits to achieve verification in normal-form games. This gives a protocol for verifying whether a given strategy profile is an approximate strong smooth Nash equilibrium, with a query complexity that is sublinear in the number of actions. |
| title | Protocols for Verifying Smooth Strategies in Bandits and Games |
| topic | Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2507.10567 |