acceptodds
Under review as a conference paper at ICLR 2027

Test-time Reinforcement Learning in Imperfect Information Games

Abstract

Test-time reasoning has significantly improved performance in domains ranging from games to language models. However, principled test-time policy improvement remains 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 games, a tabular technique for test-time search, to the reinforcement learning setting. Unlike prior approaches, we represent the gadget game implicitly by training a state sampler and virtual actor policy rather than explicitly by constructing the gadget, thereby removing constraints on subgame size. Furthermore, we prove that a fixed regularization policy bounds the strategy change within a subgame, making simpler Bayesian subgame solving viable without safe gadgets. In small games, test-time training substantially improves weak blueprints, while strong blueprints may degrade slightly. In large games, it improves over the blueprint in head-to-head play and generally outperforms the update-equivalence framework.

Primary area:
reinforcement learning
Keywords:
imperfect information games, two-player zero-sum games, test-time reasoning, reinforcement learning, subgame solving, policy-gradient, state generation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_NFdLOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposed a subgame solving approach for deep reinforcement learning in two-player zero-sum extensive-form games with a trained sampler to sample the state.

Critical strengths
  • The writing of the paper is clear and easy to understand, especially the illustrations in Figure 1.
  • The comparison with related work is comprehensive.
Critical weaknesses
  • The code is unavailable.
  • The benchmark games in this paper are too small. I would expect heads-up limit Texas hold'em/dark chess.
Questions for authors

How's the importance sampling factor incorporated into the training objective of the sampler? I would expect it to be large since it is the inverse of the reach probability.

6 comments

We would like to thank the reviewer for their review.

Codebase

We have included the code within the revision

Small benchmark games

We agree that more evaluation is always better, but we do not agree that the games we have used are too small, and we believe the results are representative of the performance in large games. The lower bounds on the game sizes for the Battleship variants we have used are following:

Battleship 7x7: 103810^{38} unique states, 103210^{32} unique decisions, 1013310^{133} nodes in the game tree and 1012810^{128} decisions if we assume perfect recall.

Battleship 10x10: 107310^{73} unique states, 106510^{65} unique decisions, 1032810^{328} nodes in the game tree, and 1032010^{320} decisions if we assume perfect recall.

The reason the game tree and decisions with perfect recall are so much higher is that they differentiate between the order of shots during gameplay (so shooting to Tile 1 and then Tile 2 is different from shooting to Tile 2 and then Tile 1).

We specifically decided to avoid Texas Hold 'em, as the variance in Poker requires at least tens of thousands of gameplays to estimate the quality of the strategy. With 10 seconds per decision, this may take several weeks just for gameplay experiments to yield reasonable estimates. Since the experiments we present already establish scalability of the method to large games, we considered this computation wasteful.

Importance Sampling

We use importance sampling as as Pjpi(w∣s)=Πt=0Tπj(sjt,ajt)P_j^{pi}(w|s)= \Pi_{t=0}^T \pi_j(s_j^t,a_j^t), where πj(sjtajt)\pi_j(s^t_j a^t_j) is a probability player jj played ajta_j^t in information set sjts_j^t at timestep tt within the trajectory. So indeed, 1Pjpi(w∣s)\frac{1}{P_j^{pi}(w|s)} can grow high in long games, because πj(sjtajt)≤1\pi_j(s^t_j a^t_j) \leq 1. However, several things can avoid blowup.

  1. The correction is only for one of the players.
  2. We are using gradient normalization to avoid big spikes in the network updates.
  3. In most games, the number of turns that have passed is public knowledge. Then, at a specific depth, it is possible to multiply the loss by a constant without biasing the distribution. We use this in our experiments for large games.

We agree that the importance sampling can grow. However, in order to keep unbiased estimates it is necessary to use it. It may be tempting to use the uniform strategy of the opponent for the sampling and then skip the importance sampling correction. However, this may introduce bias into the estimate.

Consider a game where Player 2 first selects between two decisions, then, based on the first decision, it either selects between 1000 actions or 2 actions. Now consider that Player 1 observes the ID of the action selected in the second round. If Player 1 observes an action with ID 1, then there are two states consistent with this hidden information, which correspond to these two sequences: 1,1; 2,1. As such, the belief model conditioned on the observation of Player 1 should sample, with 50% probability, the sequence 1,1 and, with 50% probability, the sequence 2,1. If you would only naively sample uniformly at each decision and avoid importance sampling, then the sequence 1, 1 would be sampled with probability 0.001⋅0.50.001 \cdot 0.5 whereas the sequence 2, 1 would be sampled with probability 0.5⋅0.50.5 \cdot 0.5.

Thank you for your response!

Evaluation on Large Games

I think [1] could serve as a useful reference for evaluating the performance of test-time search in large games, such as dark chess. I would still expect to see experimental results on Texas Hold’em and/or dark chess.

Importance Sampling

Could you also report the variance of the importance-sampling factors and the average number of steps per game in each experiment?

[1] Zhang, Brian, and Tuomas Sandholm. "General search techniques without common knowledge for imperfect-information games, and application to superhuman fog of war chess." International Conference on Learning Representations. Vol. 2026. 2026.

Thank you for the ongoing discussion!

Large games

As we said, we agree that more evaluation is always better. However, we are still unsure whether experiments on Dark Chess or Texas Hold’em would bring any new insights into the paper. The goal of the large-scale experiment was to show that the additional training improves upon the blueprint and the update equivalence framework, which we explicitly state in line 427. We think that the results in the paper support this sufficiently.

While we could compare ourselves to Obscuro in Dark Chess, the comparison itself would not yield much useful insight, since the underlying algorithm used by Obscuro requires enumerating the states within an information set, which is not possible in the large Battleship. So even if Obscuro outperforms our method in Dark Chess, our approach is still applicable to a broader class of games. On the other hand, outperforming Obscuro would be a strong contribution of the paper, but not necessary, in our opinion.

Importance Sampling

We have added to Appendix B.3 a further description of the belief model. In it, we include the details about the normalization. The game lengths of the games we use are as follows:

Goofspiel X: X-1 actions per player

Leduc: at most 4 actions per player

Batteship 2x2: at most 4 actions per player

Battleship 7x7: 33 actions per player on average, at most 52 actions per player.

Battleship 10x10: 75 actions per player on average, at most 104 actions per player.

Reviewer_cr4JOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies policy-gradient algorithms in two players zero sum and imperfect information games. The authors propose two approaches: implicit resolving gadget and bayesian subgame solving with fixed regularization policy. The theoretical results bound the stratefy change and exploitability of game solutions to a fixed reference policy. Experiments show that the method improve weak blueprints and outperform the update-equivalence framework for larger games.

Critical strengths
  1. Using policy-gradient methods to for subgame solving is an interesting and under-explored direction, especially for games where subgame construction is infeasible
  2. The empirical results covers small games in which exploitability can be measured, and larger games, where the authors use head-to-head performance
Critical weaknesses
  1. I am not fully convinced that the theoretical guarantees justify the proposed Bayesian subgame solving method. Thms. 2 and 3 concern the equilibrium of a regularized game, but, to my understanding, the method solves subgames and combines the resulting strategies with the blueprint.
  2. To the best of my knowledge, the implicit resolving gadget doesn't retain the safety guarantee of standard resolving. In Sec. 3.1, the authors replace the required counterfactual best-response values with critic estimates of blueprint values.
Questions for authors
  1. Could you provide a bound on the exploitability of the full strategy obtained after Bayesian subgame solving?
  2. In small games, could you compare the implicit resolving gadget using the exact counterfactual best-response termination values against the current critic-based approximation?
2 comments

We would like to thank the reviewer for their review.

Theoretical guarantees of Bayesian subgame solving:

We should rephrase what we aim to show in Theorems 2 and 3. The goal is to formalize the intuitive fact that the KL divergence to the frozen blueprint does not allow the Bayesian subgame solving to converge to an arbitrary strategy of the subgame, but only to a subset of strategies that are reasonably close to the blueprint (given that the rewards in the game are bounded). This prevents the worst-case degradation that may happen when the strategy converges to a pure best response. This sometimes happens when this type of subgame solving is used with tabular algorithms like CFR. Surprisingly, this becomes more of a problem the better the blueprint is [1].

We have improved Theorem 3 in the revision. The bound remains the same, but it properly bounds the exploitability of the sequence-form strategies. Since this bound holds throughout the whole game, and Bayesian subgame solving changes only a subset of the sequence-form strategies, this bound directly relates to the exploitability of the whole game. Moreover, the Bayesian resolving updates the strategy of only one player, therefore, the exploitability does not increase more than Rmax⁡2ϵη\mathcal{R}^{\max}\sqrt{\frac{2 \epsilon}{\eta}}, whereas the Theorem 3 bound uses Rmax⁡4ϵη\mathcal{R}^{\max}\sqrt{\frac{4 \epsilon}{\eta}}.

We have modified the paragraph starting at line 270 to reflect how the bound connects to the new version of Theorem 3.

Exact counterfactual best response values

This is not a difference between standard resolving and the proposed method (implicit resolving). Both methods’ theory requires using the opponent’s counterfactual best response values as the opponent’s alt-values (i.e., the value, for a given opponent’s information set, that the opponent would get by not playing into the subgame). In both techniques, in practice on large games, the best responses cannot be computed, so in practice people always use the self-play blueprint values instead. As the blueprint improves, these values get closer to each other, and at Nash equilibrium they are the same.

Furthermore, even in small games where the best-response values would be computable, using those conservative values can lead to worse play. Consider Rock-Paper-Scissors, with the blueprint for both players being to always play Rock. Then the counterfactual best-response value is -1 (fully exploitable). However, the critic estimate from self-play is 0. Using the counterfactual best-response value is overly pessimistic, and the solution to the gadget game would be any strategy with worst-case exploitability of -1 (such as playing Rock again). In contrast, the critic estimate would guarantee convergence to the strategy of choosing actions uniformly. Still, there is a danger that when the critic is overly optimistic, the resulting solution may be worse than the blueprint.

We have also included an ablation experiment in the revision in Appendix C.3. It measures the effect of using the true counterfactual best-response values instead of the estimated ones in the games from Section 5.2. Based on those results, using the true values performs slightly better for strong blueprints, but slightly worse for weak blueprints, as expected due to the conservative estimates we discussed in the previous paragraph.

Thank you for the additional clarifications. I will keep my positive score.

Reviewer_kEUBOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes test-time reinforcement learning for two-player zero-sum imperfect-information games. It introduces an implicit resolving gadget, implemented through a temporary actor, and Bayesian subgame solving with a fixed regularization policy. A transformer samples hidden histories. Experiments show improvements over weak blueprints and gains against separately trained opponents, but some stronger blueprints become more exploitable.

Critical strengths
  • The implicit gadget provides a simple alternative to explicit subgame construction.
  • Reusing the policy-gradient solver for training and test-time improvement reduces implementation complexity.
  • The normal-form analysis provides useful motivation for fixed-reference regularization.
Critical weaknesses
  • Theorem 3’s claimed sequence-form extension is not supported by Eqs. (20)–(21). Realization plans are generally not normalized probability distributions, so the norm and Pinsker steps require additional geometric constants. The normal-form proof is sound under appropriate assumptions, but the sequence-form statement needs correction.
  • The analyzed and implemented objectives are not adequately connected. Eq. (1)’s trajectory-level regularization produces visitation-weighted penalties, whereas Eq. (3) assumes separable strategy-level Bregman penalties. These are not generally equivalent. The authors should distinguish the idealized objective covered by the proofs from the implemented objective.
Questions for authors
  • Can the authors correct Theorem 3’s sequence-form scope and clarify when, if ever, Eq. (1) induces Eq. (3)?
1 comment

We would like to thank the reviewer for their review and for pointing out the mismatches between the sequence-form and normal-form claims.

Theorem 3

Thank you for pointing this out. We agree that we overstated Theorem 3’s sequence-form extensions. We modified Theorem 3 and added Lemma 1, which extends it to Sequence-form strategies. The same bounds still apply.

Connection of Equation (1) and Equation (3)

We have expanded this connection in Section 2.2. To summarize, the change is that regularization in Equation (1) is what RNaD and MMD use, and it is a regularization in behavior strategies, which weights the regularization by the on-policy reach of both players, whereas Equation (3) only uses the weight of one player and works with sequence-form strategies. Both quantities serve as regularizers, but different ones. Using the regularizer suggested by the theory would require importance sampling corrections or different sampling schemes. Prior works on policy-gradient algorithms and our experiments suggest it is not necessary.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.