Aditya Gupta

Overview

The aim of this project is ultimately to “solve” (i.e. find a Nash Equilibrium) for the two-person card game Bluff Poker. The game is similar to Liar’s Poker, a game associated with Wall Street traders, but is more complex, allowing for claims of straights, flushes, etc., as in the Texas Hold’em variant. A full set of rules can be found in the GitHub repository linked below.

I began by reviewing the formalism of POMDPs (Partially Observed Markov Decision Processes) and relevant literature, particularly 'Deep Reinforcement Learning from Self-Play in Imperfect-Information Games'. I also looked at 'Reevaluating Policy Gradient Methods for Imperfect-Information Games', to compare the performance of different reinforcement learning algorithms in this setting.

Since then the project has moved away from plain RL towards game-theoretic solvers: Counterfactual Regret Minimisation (CFR, and its variant CFR+) and their neural-network versions. This is the same family of methods behind the poker AIs Libratus, Pluribus and DeepStack. Steps 3–5 below describe that work.

The overall approach is to simplify, solve, and then add back complexity.

Approach & Iterations

Step 1: One Card Each

The first sub-goal was to solve a one-card-each version of the game. The state space here is very small: indeed, brute-force value iteration of the entire state space (taking care to allow stochastic strategies) is enough. This provided a good baseline truth against which I tried out various Reinforcement Learning techniques:

– Q-Value Tables
– Hyperparameter tuning (learning rate, exploration–exploitation, etc.)
– Best-Response / Mixing Loop (as described in “Fictitious Self-Play in Extensive-Form Games” )
– Monte Carlo vs SARSA methods

These methods were strong enough to give near-optimal performance for the 1-card version of the game. My full (somewhat meandering) thoughts can be found here.

Encouraged, I moved on to the 2-card version of the game.

Step 2: Two Cards Each

The state space is now large enough that exhaustive Q-Tables do not work: function approximation is needed. I first tried linear function approximation, representing states with feature vectors and strategies with a weight matrix. This restricted the class of possible strategies I could learn, but allowed me to implement gradient descent easily. Unfortunately, while this approach had modest success for small decks (n=2 => deck size 12), it failed to learn even basic strategies for larger n, suggesting scalability requires more effort.

Step 3: Exact Solvers on Small Games

I started from scratch, trying to extend tabular methods as far as they can go. I began by rebuilding the project around a configurable game engine: number of ranks, suits, cards per hand, and which claim types are allowed (high card, pair, two pair, trips, full house, quads). Each setting is a smaller version of the full game, which has 368 possible claims. The number of claims possible in a game gives a rough idea of how complicated the game is, since the number of possible games goes like 2^claims.

For small versions, it's feasible to compute an exact best response, ie the best possible counter-strategy to a fixed policy. That gives the key metric exploitability: how much a perfect opponent could win against a policy (0 means a Nash equilibrium). With it, I compared three exact solvers:

– Fictitious self-play (FSP): broadly this worked, but was very slow.
– CFR: every iteration, each node tracks how much it 'regrets' not having played each action, and plays in proportion to positive regret.
– CFR+: CFR with regrets floored at zero and a weighted average. Clearly the best, solving games with up to ~20 claims to exploitability around 0.001.

Step 4: Neural CFR+ and Scaling

At some point with the exponential scaling in terms of claims, the tables stop fitting in memory. Natural next step is neural networks: one network learns cumulative regrets from sampled games, and another learns the average strategy (which is what we actually evaluate). This is the idea behind Deep CFR. With the help of coding agents, I wrote a GPU-batched version that simulates thousands of games in parallel, and trained on rented GPUs.

The main obstacle was that I couldn't get long games to be very stable: more compute stopped helping. Training improved policies for a while, then plateaued or got worse. I calibrated by focusing on an 18-claim game where exploitability can still be computed exactly, but by gradually replacing each tabular / exact step with a neural step. The main fixes ended up being:

Clipping: CFR+ clips regrets at zero, but clipping noisy estimates biases them upwards since RELU is not linear. Averaging samples of the same decision before clipping fixed much of this, but isn't super scalable.

The regret network's learning rate: in hindsight obvious, but I wasn't lowering this learning rate over time, which I should be doing.

Under-trained averaging: the average-strategy network needed some tuning with respect to learning rate, etc, to get close to exact averaging.

Variance reduction: scoring each call by its exact expectation over the opponent's possible hands (given their bids), and sampling more games per iteration as training goes on.

Step 5: Measuring Strength Without Exact Answers

Beyond about 20 claims the exact best response is out of reach (at least in its current form - could probably trade memory for time here ie do a streaming version which doesn't store the whole table in memory), so I built approximate ones and calibrated them on games where the exact answer is known. Depth-limited searches do kinda ok? Where we just assume call at the end nodes. But they probably become less accurate as we scale up and games will probably last more than a few moves.

I think the next steps will be exploring things like ReBeL (https://arxiv.org/abs/2007.13544) which was used on traditional heads-up no-limit Texas hold'em poker, plus possibly looking into value networks both for better evaluation and for some sort of test time compute.

State of Play

Exploitability = (best response's win rate when moving first) + (best response's win rate when moving second) − 1. Thus 0 = perfect play and 1 = lose every game. The table shows −log₁₀(exploitability): higher is better, and each +1 means ten times less exploitable (3.0 = 0.001, so win rate of 49.95% against an opponent tailored to play against it).

Values marked ≤ come from depth=2 best response, which only finds a lower bound on exploitability, so the true score is at most that. Having said that, it is likely not too much lower.

Next Steps

– 30 claims: we've got something decent, and the neural recipe is fairly good at continuing to improve even at late iterations. But we may be encountering a fundamental wall.
– Larger games: we will need to sample both our and opponents actions, introducing yet more variance.

Resources

GitHub Repository (CFR and neural CFR+) · GitHub Repository (original RL work)