# The Hidden Game Problem

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

## Key facts

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

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [AI safety via debate](https://mlsanity.com/paper/1805.00899/) (2018)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [XDO: A Double Oracle Algorithm for Extensive-Form Games](https://mlsanity.com/paper/2103.06426/) (2021)
- [Strategizing against Learners in Bayesian Games](https://mlsanity.com/paper/2205.08562/) (2022)
- [Multicalibration as Boosting for Regression](https://mlsanity.com/paper/2301.13767/) (2023)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Learning in Non-convex Games with an Optimization Oracle](https://mlsanity.com/paper/1810.07362/) (2018)
- [Learning Equilibria in Mean-Field Games: Introducing Mean-Field PSRO](https://mlsanity.com/paper/2111.08350/) (2021)
- [The Relationship between No-Regret Learning and Online Conformal Prediction](https://mlsanity.com/paper/2502.10947/) (2025)
- [Online Learning and Solving Infinite Games with an ERM Oracle](https://mlsanity.com/paper/2307.01689/) (2023)
- [Simultaneous Swap Regret Minimization via KL-Calibration](https://mlsanity.com/paper/2502.16387/) (2025)
- [Efficient tracking of a growing number of experts](https://mlsanity.com/paper/1708.09811/) (2017)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [Playing Large Games with Oracles and AI Debate](https://mlsanity.com/paper/2312.04792/) (2023)
- [Online Learning with Low Rank Experts](https://mlsanity.com/paper/1603.06352/) (2016)
- [Sparsity-Based Interpolation of External, Internal and Swap Regret](https://mlsanity.com/paper/2502.04543/) (2025)
- [Developing, Evaluating and Scaling Learning Agents in Multi-Agent Environments](https://mlsanity.com/paper/2209.10958/) (2022)

## Abstract (arXiv)

This paper investigates a class of games with large strategy spaces, motivated by challenges in AI alignment and language games. We introduce the hidden game problem, where for each player, an unknown subset of strategies consistently yields higher rewards compared to the rest. The central question is whether efficient regret minimization algorithms can be designed to discover and exploit such hidden structures, leading to equilibrium in these subgames while maintaining rationality in general. We answer this question affirmatively by developing a composition of regret minimization techniques that achieve optimal external and swap regret bounds. Our approach ensures rapid convergence to correlated equilibria in hidden subgames, leveraging the hidden game structure for improved computational efficiency.