Test-time Reinforcement Learning in Imperfect Information Games
2026-08-31 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to improve strategies in two-player zero-sum games with hidden information by updating policies during test time. They use policy-gradient algorithms combined with a concept called gadget games, but instead of explicitly building these games, they represent them through modified sampling and neural networks, allowing for bigger and more complex subgames. They also prove that their method prevents major drops in strategy quality that older methods couldn't avoid. Their experiments show that retraining policies at test time often leads to better results than sticking with the original strategy.
test-time reasoningpolicy-gradient algorithmstwo-player zero-sum gamesimperfect-information gamesgadget gamereinforcement learningneural policysamplingstrategy degradation
Authors
Ondrej Kubicek, Viliam Lisy, Tuomas Sandholm
Abstract
Test-time reasoning has significantly improved performance in domains ranging from games to language models. However, test-time policy changes with formal guarantees on the performance of the resulting strategy remain a challenge in two-player zero-sum imperfect-information games. Existing solutions are limited to tabular methods or single gradient step updates. In this work, we investigate policy-gradient algorithms as a method for scalable test-time reasoning. We extend the concept of gadget game, tabular technique for test-time search, to the reinforcement learning setting. Unlike prior approaches, we represent the gadget game implicitly by modified sampling and neural policy rather then explicitly by constructing it, thereby removing constraints on subgame size. Furthermore, we formally prove that, unlike prior tabular algorithms, regularized policy-gradient algorithms limit possible strategy degradation caused by test-time reasoning, even without the gadget games. Our evaluation across small- and large-scale games confirms that additional test-time training often substantially improves performance relative to the blueprint strategy.