The Hidden Game Problem
This addresses challenges in AI alignment and language games, offering a novel algorithmic solution for efficient equilibrium discovery in complex strategy spaces.
The paper tackles the hidden game problem, where players have unknown subsets of strategies with higher rewards, by developing regret minimization algorithms that achieve optimal bounds and ensure rapid convergence to correlated equilibria in hidden subgames.
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.