# Protocols for Verifying Smooth Strategies in Bandits and Games

arXiv: https://arxiv.org/abs/2507.10567 · HTML: https://mlsanity.com/paper/2507.10567/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 44 references that are in the map.
- First posted on arXiv 8 Jul 2025.

## Builds on (most cited first, 14 of 14)

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Corruption-Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06630/) (2021)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [On the Optimal Sample Complexity for Best Arm Identification](https://mlsanity.com/paper/1511.03774/) (2015)
- [Learning Equilibria of Games via Payoff Queries](https://mlsanity.com/paper/1302.3116/) (2013)
- [PAC Verification of Statistical Algorithms](https://mlsanity.com/paper/2211.17096/) (2022)
- [Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria](https://mlsanity.com/paper/1805.06387/) (2018)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [Smooth Nash Equilibria: Algorithms and Complexity](https://mlsanity.com/paper/2309.12226/) (2023)
- [On the Power of Interactive Proofs for Learning](https://mlsanity.com/paper/2404.08158/) (2024)
- [Interactive proofs for verifying (quantum) learning and testing](https://mlsanity.com/paper/2410.23969/) (2024)

## Abstract (arXiv)

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.