Research map / Bandits and online learning / Multi-armed bandits
Protocols for Verifying Smooth Strategies in Bandits and Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives interactive-proof protocols that verify approximately optimal smooth strategies in multi-armed bandits and strong smooth Nash equilibria in normal-form games with sublinear oracle queries, plus matching lower bounds.
Problem
Verifying approximate optimality of smooth strategies in multi-armed bandits and approximate smooth Nash equilibria in normal-form games when the number of actions n is large, using few utility/payoff oracle queries with help from an untrusted prover.
Approach
A lying prover must misreport many arms to hide a better sigma-smooth strategy, so a verifier that samples a few random arms and checks the prover's reported utilities catches a lie with constant probability; with binning over lie magnitudes this gives O(sigma n / eps^2) queries, and games reduce to one bandit verification per player.
Key results
- Verifier for eps-optimal sigma-smooth bandit strategies uses O~(sigma n / eps^2) arm queries with a single O~(n)-bit prover message.
- Lower bound Omega(sigma n / eps^2) queries for any MAB verification protocol, and Omega(n) queries for learning smooth strategies, showing a quadratic gap at sigma = O(1/sqrt n).
- Smooth Nash equilibrium verifier uses O~(k sigma n / eta^2) game oracle queries, with an Omega(k n sigma) lower bound for verification.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use interactive proof-based verification instead of learning a smooth bandit strategy | Smooth bandit strategies · n-arm bandits | oracle queries: verifier: \BigO{\frac{n\sigma}{\varepsilon^2} \cdot \logf{\frac{n\sigma}{\varepsilon}}\logf{\frac{1}{\varepsilon}}}; lea | Helped |
| Use interactive proof-based verification instead of computing an ε-NE without a prover | Smooth Nash equilibrium · k-player, n-action normal-form games | oracle queries: verifier: \BigO{\frac{n \sigma}{\eta^2}\log\left(\frac{n \sigma}{\eta} \right)\log\left(\frac{1}{\eta} \right)k \log k}; | Helped |
| Use SNARKs and vector commitments instead of sending the utility vector in full | Smooth bandit verification · n-arm bandits | communication bits: \BigO{\secpar \cdot (\sigma n \log n \log^2(1/\varepsilon) / \varepsilon} | Helped |
Surprising findings
- Verification of smooth strategies can be strictly cheaper than learning them, with a quadratic gap when sigma = O(1/sqrt n).
Limitations
- Requires sigma n = o(n) smoothness assumption for sublinear queries.
- Game verification requires a slackness parameter eta, and query complexity depends on eta rather than eps.
- Low-communication variant relies on a trusted setup and cryptographic assumptions.
Experimental setup
Metrics: query complexity communication bits
Baselines: learning smooth bandit strategies (lower bound) computing smooth equilibria without prover
Builds on: interactive proofs for machine learning smooth Nash equilibrium (Goldberg et al.) SNARKs vector commitments
Closest papers by meaning
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.87)
- Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting (NeurIPS 2024 · similarity 0.87)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.87)
- Replication-proof Bandit Mechanism Design with Bayesian Agents (AAAI 2025 · similarity 0.86)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.86)
- Heterogeneous Multi-Agent Bandits with Parsimonious Hints (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.