Protocols for Verifying Smooth Strategies in Bandits and Games

2025-07-08 · Miranda Christ, Daniel Reichman, Jonathan Shafer 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.

📄 PDF Abstract BibTeX arXiv:2507.10567

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-Armed Bandits

Online Monotone Games

2017-10-19 · Ian Gemp, Sridhar Mahadevan

Algorithmic game theory (AGT) focuses on the design and analysis of algorithms for interacting agents, with interactions rigorously formalized within the framework of games. Results from AGT find applications in domains …

Reinforcement Learning Reinforcement Learning (RL)

Combinatorial Multi-armed Bandits for Real-Time Strategy Games

2017-10-13 · Santiago Ontañón

Games with large branching factors pose a significant challenge for game tree search algorithms. In this paper, we address this problem with a sampling strategy for Monte Carlo Tree Search (MCTS) algorithms called {\em n…

Multi-Armed Bandits Real-Time Strategy Games

Quantum Agents for Algorithmic Discovery

2025-10-09 · Iordanis Kerenidis, El-Amine Cherrat arxiv

We introduce quantum agents trained by episodic, reward-based reinforcement learning to autonomously rediscover several seminal quantum algorithms and protocols. In particular, our agents learn: efficient logarithmic-dep…

Reinforcement Learning

Convergence analysis and acceleration of the smoothing methods for solving extensive-form games

2023-03-20 · Keigo Habara, Ellen Hidemi Fukuda, Nobuo Yamashita

The extensive-form game has been studied considerably in recent years. It can represent games with multiple decision points and incomplete information, and hence it is helpful in formulating games with uncertain inputs, …

Form

Regression Oracles and Exploration Strategies for Short-Horizon Multi-Armed Bandits

2021-02-10 · Robert C. Gray, Jichen Zhu, Santiago Ontañón

This paper explores multi-armed bandit (MAB) strategies in very short horizon scenarios, i.e., when the bandit strategy is only allowed very few interactions with the environment. This is an understudied setting in the M…

Multi-Armed Bandits regression