PaperlayerView exact revision on arXiv

Source-linked AI summary

Test-time Reinforcement Learning in Imperfect Information Games

Ondrej Kubicek, Viliam Lisy, Tuomas Sandholm

arXiv:2608.30635v1cs.GT

TL;DR

Test-time policy changes with guarantees remain difficult in two-player zero-sum imperfect-information games, where prior methods are mainly tabular or limited to one gradient step. The paper extends gadget-game reasoning to policy gradients through implicit neural representations and state sampling, and shows that constant-policy regularization bounds strategy changes beyond one step. Across small and large games, test-time reasoning improves performance over blueprint strategies, while persistent updates remain an open limitation.

  • Problem

    Test-time policy changes with formal performance guarantees remain challenging in imperfect-information games, where existing approaches are largely tabular or limited to single gradient-step updates.

  • Method

    The paper extends gadget games to reinforcement learning by implicitly representing them with a temporary neural actor and using a Transformer belief model for required state sampling.

  • Results

    Test-time reasoning improves performance over blueprint strategies in both small and large games, often exceeding the gains of the Update-equivalence framework.

  • Takeaways & Limitations

    Regularized policy gradients can bound strategy improvement or degradation beyond one update, while implicit gadget reasoning removes reliance on explicit subgame construction and tabular solvers.

  • Takeaways & Limitations

    Shared network parameters require resetting weights after each playthrough, preventing agents from retaining test-time insights across playthroughs.

Abstract

from arXiv · show

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.

1 Introduction

Test-time reasoning is difficult in imperfect-information games because beliefs over hidden states depend on prior strategies, while existing scalable guarantees remain limited. This work extends gadget-game reasoning with policy-gradient methods, implicit gadget representations, and regularization-based safety guarantees.

  • Motivation: In imperfect-information games, optimal decisions depend on beliefs over hidden states and the prior strategies of all players.Fixed beliefs about an opponent’s past decisions can produce highly exploitable strategies.
  • Prior approaches: Gadget games provide tabular test-time reasoning, but existing gadget-game and test-time methods have largely remained tabular.Policy-gradient algorithms offer a non-tabular alternative demonstrated in large games such as Stratego.
  • Prior approaches: Single-step update-equivalence reasoning bounds exploitability degradation but restricts test-time reasoning to one policy-gradient update.The single-update restriction also limits potential gains.
  • Contributions: The proposed methods represent gadget games implicitly with modified sampling and neural policies rather than constructing them explicitly.The same policy-gradient algorithm is used during training and test-time reasoning, reducing design complexity and improving scalability.
  • Contributions: Regularized policy-gradient algorithms retain safety guarantees beyond a single gradient step when the regularization policy remains constant.The resulting bound limits both potential policy improvement and degradation.
  • Evaluation: In small games, gadget reasoning improves weaker blueprints and negligibly degrades strong blueprints, while Battleship test-time reasoning exceeds an 80% win rate against an opponent without it.The small-game result is attributed to sampling noise for strong blueprints.

2 Background

The background defines imperfect-information games, strategies, reach probabilities, exploitability, and subgame-solving frameworks. It motivates gadget games and KL-regularized policy gradients as foundations for the paper’s approach.

  • Game model: A two-player zero-sum FOSG models players, chance, world states, transitions, actions, rewards, and observations.Player 2’s reward is the negative of player 1’s reward.
  • Game model: A history is a rule-consistent sequence of states and actions, while a behavioral strategy maps information sets to distributions over legal actions.A strategy profile combines both players’ strategies with the game-fixed chance strategy.
  • Strategies and reach: Reach probability gives the probability of reaching a history under a strategy profile and decomposes into individual player contributions.The notation also defines reach from the initial history.
  • Solution concepts: A best response maximizes utility against a fixed opponent strategy, and a Nash equilibrium is a profile in which all players use best responses.Exploitability measures distance from equilibrium and is non-negative, reaching zero when the strategy is part of a Nash equilibrium.
  • Subgame solving: Subgame solving restricts the original game to histories associated with a collection of starting states, with common-knowledge and knowledge-limited variants.The paper uses 1-KLUSS, which lets both players optimize across histories consistent with one player’s information set.
  • Gadget games: Gadget states and actions connect disjoint subgame initial states to make an imperfect-information subgame well defined.Bayesian gadgets sample initial states according to blueprint reach probabilities but can become highly exploitable when the opponent deviates from the assumed blueprint.
  • Policy gradients: Policy-gradient methods use KL regularization toward a magnet strategy, with stronger regularization keeping the strategy closer to that magnet.Changing the magnet or annealing the regularization strength can eventually yield Nash-equilibrium convergence in normal-form or sequence-form settings.

3 Safe imperfect-information subgame solving

This section develops safe test-time subgame solving for imperfect-information games, combining gadget-game guarantees with policy-gradient methods and regularization. The proposed implicit approach avoids explicit subgame construction, while experiments and theorems characterize performance gains and safety boundaries.

  • 3 Safe imperfect-information subgame solving: Bayesian gadgets depend on beliefs about opponents’ past strategies, whereas resolving gadgets let opponents hypothetically choose past strategies and guarantee no greater exploitability than the blueprint.The guarantee applies when termination rewards equal the opponent’s counterfactual best-response values to the blueprint.
  • 3.1 Subgame solving by implicit gadget game: Explicitly constructed subgames can be computationally infeasible, motivating a policy-gradient method that represents resolving gadgets implicitly.The method uses a temporary actor for the gadget decision and applies the same algorithm during training and test-time reasoning.
  • 3.1 Subgame solving by implicit gadget game: The implicit method samples initial states by player-and-chance reach, estimates continue and terminate q-values, and scales the update by the continue probability for unbiased learning.The terminate q-value uses the blueprint critic estimate, while the continue q-value estimates the sampled state’s counterfactual value.
  • 3.2 Subgame solving with a fixed magnet: Regularization bounds strategy movement from a fixed magnet through its strength, providing safety for policy-gradient strategies even without gadget games.Theorem 2 bounds strategy change, while Theorem 3 bounds exploitability for the regularized game’s Nash strategy in the unregularized game.
  • 3.2 Subgame solving with a fixed magnet: Fixed-magnet safety can fail outside the solved Bayesian subgame, although strong blueprints and KL penalties can keep practical changes near the magnet.The update-equivalence framework also may increase exploitability in the worst case, whereas the fixed-magnet guarantee persists at convergence under its stated conditions.
  • 3.2 Subgame solving with a fixed magnet: Theorem 2 bounds strategy change in both common-knowledge and knowledge-limited solving, unlike gadget-game safety, which needs extra constraints for KLSS.Nested resolving additionally requires later resolves to use weights from preceding resolves to preserve safety.

4 Generating states

The paper introduces learned belief models to generate subgame states conditioned on available information rather than explicitly enumerating complete state spaces. These models must track changing strategies during nested test-time solving to avoid optimizing against outdated state distributions.

  • 4 Generating states: Changing strategies shift the state distribution required for subgame solving, so belief models must dynamically adapt along with the strategy.This creates a coordination requirement between strategy updates and state sampling.
  • 4 Generating states: A generative model learns to sample subgame states conditioned on an infoset or public state, replacing explicit enumeration and fixed-strategy belief models.The approach is intended as a general alternative to rule-based enumeration and predefined or trained abstractions.
  • 4 Generating states: The belief model is a decoder-only Transformer that autoregressively generates action and chance-event tokens leading to a state, conditioned on the relevant information context.The initial token is the infoset for KLSS or the public state for common-knowledge solving.
  • 4 Generating states: For Bayesian gadgets, trajectories sampled under the current strategy train the model with cross-entropy to match strategy-conditioned state probabilities.The target distribution is proportional to P πθ(w|s), where s is an information set or public state.
  • 4 Generating states: Resolving-gadget sampling removes the opponent’s strategy from full-reach trajectory samples using an importance-sampling correction.The correction divides by the opponent’s strategy probability to eliminate bias from that specific opponent strategy.
  • 4 Generating states: Jointly training the belief model during nested solving keeps sampled-state distributions aligned with updated strategies and prevents belief-strategy mismatch.Without joint training, the strategy may be optimized against an outdated distribution.

5 Experiments

The experiments evaluate policy-gradient subgame-solving techniques in one-shot, small, and large imperfect-information games. Test-time reasoning generally improves exploitable blueprints, while strong-blueprint degradation and large-game comparisons reveal practical limits.

  • Experimental setup: Experiments use Regularized Nash Dynamics with Neural Replicator Dynamics to assess exploitability and scalability across small and large games.The evaluation includes one-shot games, benchmark games, and large environments where exact exploitability is infeasible.
  • 5.1 One-shot games: A fixed magnet limits divergence from equilibrium, whereas a moving magnet converges toward an exploitable best response; gadget solving remains low-exploitability after initialization.Gadget exploitability initially rises because its actor learns a randomly initialized decision, then slightly exceeds the blueprint because of critic approximation noise.
  • 5.2 Small games: All techniques improve highly exploitable blueprints in small games, with resolving gadget outperforming alternatives under these policy-gradient settings.The advantage is partly attributed to Bayesian gadget’s fixed-magnet constraint and RNaD’s encouragement of non-zero action probabilities.
  • 5.2 Small games: Resolving gadget slightly increases exploitability for the strongest Goofspiel and Leduc blueprints despite extended training.The authors attribute this to incomplete convergence in earlier subgames and noise from critics, belief samples, and trajectory sampling.
  • 5.3 Large games: The large-game experiment tests whether additional test-time reasoning improves blueprints rather than whether it outperforms every applicable prior technique.Blueprints and subgame solvers receive equal additional computation time, and different training seeds are matched.
  • 5.3 Large games: All evaluated methods outperform UEF in large-game head-to-head play, while Bayesian gadget frequently outperforms resolving gadget despite being theoretically unsafe.The authors note that head-to-head reward is not a perfect proxy for exploitability.

6 Conclusion and discussion

The paper presents scalable policy-gradient test-time reasoning for imperfect-information games by implicitly representing gadget games and using KL regularization as a safety anchor. Experiments show performance improvements over blueprint strategies, while shared parameters require resetting weights after each playthrough.

  • Scalable framework: The framework extends gadget games to reinforcement learning through a generative belief model, avoiding explicit subgame construction and tabular solvers.This enables test-time reasoning when subgame states are not enumerable.
  • Implicit gadget games: A temporary actor implicitly represents the resolving gadget game’s decision.
  • Safety: KL regularization acts as an implicit safety anchor that bounds strategy changes even with nominally unsafe Bayesian techniques.
  • Empirical results: Additional test-time reasoning improved performance over the blueprint in both small and large games, often exceeding the gains from the Update-equivalence framework.The comparison framework was used in the superhuman Stratego bot Ataraxos.
  • Limitations: Shared network parameters require resetting weights after each playthrough, limiting retention of test-time insights across playthroughs.Persistent local updates are identified as a direction for future research.
  • Future directions: The approach omits approximate value functions to isolate test-time reasoning from noise introduced by value approximation.Combining the method with depth-limited solving is proposed for faster updates in long games.

A Proofs

The proofs analyze regularized two-player games relative to a fixed magnet strategy using Bregman divergences. They derive bounds on divergence and exploitability for the regularized Nash strategy in the original unregularized game.

  • Entropy regularization: For entropy regularization, the resulting strategy profile’s divergence from the magnet is bounded by the magnet’s exploitability divided by the regularization weight.The displayed result is given as an upper bound involving E(πM) and η.
  • Regularized formulation: The regularized objective combines the reward matrix with Bregman-divergence penalties relative to a fixed magnet strategy.The proof uses Magnetic Mirror Descent and distinguishes normal-form or sequence-form strategies from behavioral strategies.
  • Bregman analysis: The Bregman three-point property decomposes gradient inner products into divergences involving the candidate strategy, regularized strategy, and magnet.
  • Exploitability guarantee: Theorem 3 bounds the exploitability of the regularized game’s Nash strategy when evaluated in the original unregularized game.Its assumptions include a reward matrix, entropy regularizer, magnet strategy profile, exploitability ϵ, and regularization weight η.

B Experimental details

Experiments were run in Python 3.13 using Jax-ecosystem libraries on one AMD EPYC 7543 core with 16 GB of RAM and one Nvidia A100.

  • Compute environment: Each experiment used Python 3.13, Jax-ecosystem libraries, one AMD EPYC 7543 core, 16 GB of RAM, and one Nvidia A100.

B.1 Game rules

The experimental games include sequential imperfect-information versions of biased matching pennies and rock-paper-scissors, alongside larger games and a gadget-game training procedure. The procedure samples world states from a belief model and updates the policy through actor and critic losses.

  • Game rules: Biased Matching Pennies doubles rewards when both players choose Tails and is implemented with Player 2 acting before an unobserving Player 1.
  • Game rules: Rock-Paper-Scissors uses Rock, Paper, and Scissors with standard cyclic outcomes and is implemented with Player 2 acting before an unobserving Player 1.
  • Game rules: The evaluated game set also includes Battleship, imperfect-information Goofspiel, and Leduc Hold ’em.The supplied table caption identifies normal-form representations for games used in Section 5.1.
  • Subgame solving: The subgame-solving procedure initializes gadget parameters, samples world states from a belief model, and trains trajectories from those states using the current policy.
  • Subgame solving: The procedure estimates counterfactual values and updates the gadget actor, policy parameters, and critic using continuation probabilities and scaled losses.

B.3 Belief model

The authors evaluate belief-model samples by comparing them with blueprint reaches using Jensen-Shannon divergence across public states. The gadget-game belief model can sometimes produce more accurate samples than the Bayesian model, especially for stronger Goofspiel blueprints.

  • Belief-model evaluation: Jensen-Shannon divergence measures differences between blueprint reaches and belief-model samples across each public state.The experiment reports both mean and maximum divergence for each public state.
  • Belief-model evaluation: The gadget-game belief model sometimes produces more accurate samples than the Bayesian model despite importance-sampling variance.This effect is reported for the belief model trained for the gadget game.
  • Belief-model evaluation: The accuracy advantage occurs mostly with stronger Goofspiel 5 blueprints, where later public states contain hundreds of underlying states.The authors attribute this to near-zero Bayesian reaches being harder to predict under sampling variance.

B.4 Choice of the gadget

The paper compares resolving and max-margin gadget games and chooses resolving gadgets for neural simulation and scalability. It also reports the experiment configurations and leaves combining max-margin gifts with the proposed simulation for future work.

  • Gadget choice: Max-margin gadgets maximize minimal subgame improvement, while resolving gadgets may contain stronger equilibria.The paper uses resolving gadgets despite this comparison.
  • Gadget choice: The authors omit max-margin gadgets because their decision order requires beliefs across all root information sets, whose number is unknown in large games.Resolving gadgets instead add a two-action decision that neural networks can simulate easily.
  • Gadget choice: The proposed simulation does not combine max-margin gift redistribution with gadget games.The authors leave this combination for future research.
  • Experimental setup: Large-game experiments used five blueprint strategies, three belief-model variants per blueprint, and approximately 100 hours of head-to-head evaluation per configuration.The estimated total computational cost was at most 6720 GPU-hours.

C Additional Experiments

Additional experiments examine belief strength, magnet regularization, and head-to-head performance against random and heuristic Battleship opponents. Test-time methods improve over blueprints, although differences among several methods are inconclusive.

  • C.1 Magnet regularization: Lower magnet regularization moves Rock-paper-scissors solutions closer to the best response.The magnet limits strategy changes when the Bayesian solution is a fully exploitable pure strategy.
  • C.2 Head-to-head performance: The Battleship evaluation compares methods against uniform-random and strong heuristic opponents.The heuristic player uses random ship placement and a checkerboard shooting strategy focused on the smallest remaining ship.
  • C.2 Head-to-head performance: Gadget and Bayesian approaches significantly improve over the blueprint, while differences among them remain inconclusive.UEF also improves over the blueprint, but its gains are smaller than those of the other methods.
Loading 2608.30635v1…