提出验证平滑策略近似最优性的高效协议，查询次数低于学习所需。
Protocols for Verifying Smooth Strategies in Bandits and Games
- 设计基于效用预言机的子线性查询验证方法
- 证明平滑策略ε-最优性可被高效验证
- 适用于大规模博弈与多臂老虎机场景
我们研究了在多臂老虎机和标准形式博弈中验证策略近似最优性的协议。由于每名玩家可用动作数量通常较大，我们寻求查询次数在动作数上为次线性的验证协议。我们证明，对于在任意特定动作上不分配过多概率质量的充分平滑策略，此类验证是可行的。我们提供了验证多臂老虎机中平滑策略ε-最优性的协议，其所需臂查询次数严格少于学习过程。此外，我们在该设定下建立了近乎紧致的查询复杂度下界。作为应用，我们展示了如何利用老虎机的验证机制实现对标准形式博弈的验证，给出一种验证给定策略组合是否为近似强平滑纳什均衡的协议，其查询复杂度在动作数上为次线性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。