PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Updates, Global Learning (LUGL): Playing Games with non-incremental Learners

David Milec, Spyridon Samothrakis, Michael Fairbank, Dennis J. N. J. Soemers

arXiv:2609.03660v1cs.LGcs.AI

TL;DR

Game-playing reinforcement learning favors neural networks because they learn incrementally, while gradient-boosted trees are strong tabular learners but face evolving self-play distributions. LUGL separates local tabular updates from global model fitting, and experiments across nine games report competitive or superior performance against DQN and DeepCFR, including stronger results for LightGBM-based agents.

  • Problem

    Neural networks dominate game-playing reinforcement learning partly because non-incremental learners struggle with the continuously evolving, non-stationary data generated by self-play.

  • Method

    LUGL alternates local self-play updates in a finite table with global supervised learning that trains a function approximator before resetting the table.

  • Results

    Across tested perfect- and imperfect-information games, LUGL variants were competitive with or superior to DQN and DeepCFR, while LightGBM consistently outperformed neural networks in controlled DeepCFR comparisons.

  • Takeaways & Limitations

    The results challenge the assumption that incremental learning is required for competitive game play and identify gradient-boosted trees as powerful non-neural alternatives.

Abstract

from arXiv · show

The dominance of Neural Networks (NNs) in RL is partially due to their incremental learning capability, which naturally suits the online, non-stationary nature of self-play training. However, gradient-boosted trees like LightGBM are widely recognised as the state of the art for tabular data in supervised learning, often outperforming NNs in accuracy and efficiency. Game states are inherently tabular---discrete actions, categorical card identities, structured board positions---which makes them an ideal candidate for tree-based methods. We introduce LUGL (Local Updates, Global Learning), a framework that decouples data collection from model fitting, enabling non-incremental learners such as GBTs to operate in RL settings where they would otherwise fail due to distributional shift. LUGL alternates between a local updates phase, where the agent plays self-play games and accumulates tabular updates (Q-values, V-values, policies, or regret values) in a finite table, and a global learning phase, where the table is used to train a function approximator that generalises to unseen states before the table is reset. We test our approach in four standard perfect-information games (Tic-tac-toe, Connect-4, Othello, and Hex) and five imperfect-information games (Kuhn's poker, Leduc Hold'em, Liar's Dice, Goofspiel, and Flop5 Hold'em), and show that our results are competitive with or superior to DQN and DeepCFR. Our experiments demonstrate that the community's strong bias towards NNs in game-playing may be unwarranted, since LightGBM-based agents achieve competitive or superior performance across all tested benchmarks.

I. INTRODUCTION

The paper motivates replacing neural networks in game-playing reinforcement learning with batch learners, particularly gradient-boosted trees, and introduces LUGL to address their difficulty with evolving self-play data. LUGL separates local data collection from global model fitting and is evaluated against DQN and DeepCFR across perfect- and imperfect-information games.

  • Motivation: Neural networks are widely used because they can incrementally update between rounds of game play and data collection.DQN uses experience replay and alternating networks to manage distributional shifts, while DeepCFR retrains after data collection.
  • Motivation: Gradient-boosted trees are strong candidates for game states because tabular representations contain discrete actions, categorical identities, and structured board positions.The passage also identifies their inductive bias, variance control, and relatively low tuning burden.
  • Approach: LUGL decouples self-play data collection from model fitting by combining local updates with periodic global learning for non-incremental models.The framework combines ideas from fitted Q-iteration, approximate policy iteration, DQN, and DeepCFR.
  • Evaluation: The study evaluates LUGL on four perfect-information and five imperfect-information games, comparing it with DQN and DeepCFR and testing multiple LUGL variants.The authors report that the variants are reasonably robust and may transfer to more advanced setups.
  • Contributions: The paper claims that neural networks may not be necessary for competitive game play and that batch learners can replace them in game-playing reinforcement learning.Its stated contributions include enabling gradient-boosted trees, splines, or decision trees to replace neural networks.

2) Two-Player Alternating Markov Games:

A two-player alternating Markov game represents an extensive-form game through states, actions, transitions, rewards, and an initial-state distribution. It restricts play to sequential actions without hidden information, enabling standard reinforcement learning algorithms.

  • Definition: An alternating Markov game uses a state space S linked to histories by a surjective Markov-reduction map φ.The state representation is the reduced form of the underlying extensive-form game.
  • Definition: Players act from state-dependent action sets, with A_i(s) specifying the actions available to player i in state s.The available actions correspond to histories mapped to the same state.
  • Dynamics: The transition function T maps a current state and active-player action to a probability distribution over the next state and next player.This permits stochastic transitions while preserving alternating control.
  • Rewards: Reward functions R_1 and R_2 assign immediate rewards to the acting player for state-action pairs.The rewards are defined over S × A_i.
  • Scope: The initial distribution ρ_0 specifies starting states, and the game has sequential actions with no hidden information.These properties distinguish alternating Markov games from the paper’s nontrivial imperfect-information setting.

B. Games

The experiments span games with varied board, state-space, and information structures, covering both solved or tractable benchmarks and larger strategic domains. The selected games provide settings for evaluating agents under perfect and imperfect information.

  • Perfect information: Perfect-information game complexity is described using reachable legal positions and the number of leaves in the smallest full-width game tree.These measures are reported in Table I.
  • Perfect information: The perfect-information suite includes Tic-tac-toe, Connect-4, Othello, and Hex, ranging from solved games to strategically difficult positions.Hex is known to be a first-player win under optimal play, but optimal play is not known for every state or even the initial state.
  • Imperfect information: Kuhn Poker and Leduc Poker use private cards and limited betting, with Leduc adding a public card and a second betting round.Both are tractable benchmarks for poker strategy and game-theoretic solution concepts.
  • Imperfect information: Liar’s Dice and Goofspiel introduce hidden information through private die results or unrevealed simultaneous bids.Their rules create bluffing or auction uncertainty while keeping the games small.
  • Imperfect information: Flop5 Hold’em uses a complete 52-card deck, two hole cards per player, two betting rounds, and a simultaneous reveal of five cards.The variant follows full Limit Texas Hold’em betting rules apart from its altered reveal and round structure.

C. Comparing agents

Agent evaluation uses different measures for perfect- and imperfect-information games: Glicko-2 ratings for the former and exploitability for the latter. Exploitability measures how much a fully rational opponent can gain by unilaterally deviating from the policy profile.

  • Evaluation metrics: Perfect-information agents are evaluated with Glicko-2, whereas imperfect-information agents are evaluated with exploitability.The paper uses these two systems because agent evaluation differs across the two game categories.
  • Evaluation metrics: Glicko-2 estimates player skill from observed match performance using a rating and a rating deviation.The deviation represents uncertainty and affects the size of rating updates.
  • Exploitability: Exploitability quantifies the improvement available to a fully rational opponent that unilaterally deviates from a policy profile.It therefore measures distance from Nash equilibrium in a two-player zero-sum game.
  • Exploitability: OpenSpiel computes exploitability by solving for a best response through backward induction and returning the resulting expected payoff gap.Exact best-response computation is feasible at every checkpoint for the smaller games listed in the passage.
  • Exploitability: Lower exploitability means less opportunity for profitable deviation, while zero exploitability corresponds to a Nash equilibrium.The measure is pointwise, so each value describes closeness to equilibrium at that training iteration.

D. Gradient Boosting Machines

Gradient boosting combines weak predictive models, typically decision trees, into stronger models by iteratively minimising a loss function. The paper uses LightGBM as a tabular-data alternative to neural networks in reinforcement learning.

  • Gradient boosting combines multiple weak predictive models, typically decision trees, to create a stronger predictive model.Decision trees capture complex nonlinear relationships and handle continuous and categorical features.
  • Models are trained by minimising predefined losses such as mean squared error for regression or logarithmic loss for classification.
  • Gradient boosting trains each new weak model to approximate the negative loss gradient, then adds it with a positive learning rate.The update is F_m(x) = F_m−1(x) + αh_i(x), where α > 0 is shrinkage.
  • LightGBM is used as the paper’s gradient-boosting implementation and is presented as an underexplored option for reinforcement learning.
  • DQN approximates optimal action values with deep neural networks, while DeepCFR uses neural networks to approximate cumulative regret and player policies in imperfect-information games.DQN uses replay buffers and target networks; DeepCFR combines counterfactual regret minimization with deep learning.

1) Core Architecture:

LUGL decouples self-play data collection from model fitting so non-incremental learners can train on coherent local-table snapshots. It alternates local tabular updates with global function-approximator learning and then resets the table.

  • Core Architecture: LUGL addresses the mismatch between fixed-dataset batch learning and continuously evolving, non-stationary game-playing reinforcement learning.In standard settings, this mismatch causes severe distributional shift and instability.
  • Local Updates: During local updates, self-play accumulates Q-values, V-values, policy actions, or regret values in a finite local table while leaving the function approximator unchanged.
  • Global Learning: During global learning, local-table entries become supervised training samples for a function approximator such as LightGBM, which generalises values to unseen states.In the experiments, distillation occurs after a fixed number of games, such as 10^4.
  • Stability Mechanism: The cycle stabilises batch learners by buffering data locally, training on a coherent policy snapshot, and resetting the table after distillation.
  • Architecture and Representation: LUGL uses local-table values when available and otherwise falls back to function-approximator estimates, with tables capped at 10^5 rows.The cap limits memory and LightGBM training time because frequently visited states are already covered.
  • Framework Scope: The framework modifies standard reinforcement-learning methods and combines them with LightGBM, including a LightGBM-based DeepCFR variant.

A. Perfect information variations

The perfect-information LUGL variants store learned quantities locally and periodically distil them into LightGBM models. Q-learning variants use hybrid local-table and function-approximator estimates during self-play.

  • LUGL-Q-LightGBM learns Q-values in both a local table and a LightGBM function approximator.
  • During self-play, only local-table Q-values are updated, while LightGBM supplies estimates for state-action pairs absent from the table.
  • The hybrid estimate uses Q_LT(s, a) when a state-action pair exists locally and Q_FA(s, a) otherwise.
  • The agent explores with an ϵ-greedy policy based on the hybrid eQ function and initialises unseen table entries from Q_FA.
  • LUGL-QD-LightGBM is a deterministic variant that sets the Q-learning learning rate α to 1 and uses LightGBM to approximate Q_FA.

3) LUGL-PI-LightGBM:

LUGL-PI-LightGBM stores state values and policy actions locally and globally, applying approximate policy iteration. Its local tables are periodically distilled into LightGBM models and reset.

  • LUGL-PI-LightGBM stores both V-values and policy actions for each state in its local table and LightGBM model.
  • The LightGBM agent performs approximate policy iteration by repeatedly evaluating the current policy and updating the policy.
  • Policy evaluation uses the LightGBM model to approximate the value function before the policy is updated.
  • Every n games, the local value and policy tables are distilled into LightGBM models and then reset.
  • The value-only variant updates V-values from successor-state rewards and typically follows an ϵ-greedy one-step-lookahead policy.

1) LUGL-DeepCFR-LightGBM:

LUGL-DeepCFR-LightGBM replaces DeepCFR’s neural networks with LightGBM models while retaining local regret collection and global fitting. Across imperfect-information games, LightGBM and specialized multi-model variants show strong performance against DeepCFR.

  • LUGL-DeepCFR-LightGBM: LUGL-DeepCFR-LightGBM replaces DeepCFR’s neural networks with LightGBM models that store and approximate regret values.The substitution is compatible with DeepCFR because its networks are retrained from scratch each iteration.
  • LUGL-DeepCFR-LightGBM: During local updates, external-sampling trajectories generate regret values stored by information set, excluding opponents’ private cards from imperfect-information inputs.The input uses observable history such as private cards, public cards, and action history.
  • LUGL-DeepCFR-LightGBM: After fixed traversals, LightGBM trains on accumulated regret samples; regret matching then derives the policy, before the local table resets.This repeats the local-update and global-learning cycle.
  • Evaluation: The experiments compare LUGL variants with random players and DQN using fixed-interval snapshots in all-play-all tournaments scored by Glicko-2.The reported settings include n_distillation = 104, n_measure games = 64, and n_trees = 2000.
  • Results: Across Kuhn Poker, Leduc Poker, Liar’s Dice, and IIGoofspiel(4), LUGL-DeepCFR-LightGBM consistently outperformed original DeepCFR.The comparison evaluates the LightGBM replacement across four imperfect-information games.
  • Results: On Leduc Poker, specialized Multi-S and Multi-D variants significantly outperformed the LightGBM version, with polynomial splines and decision trees showing similar strong performance.These variants split the approximation task by betting sequence.

2) Generalization Experiments in Leduc Poker:

The Leduc Poker experiments withheld specific card combinations to test generalisation to unseen states. Multi variants outperformed DeepCFR despite performance drops across withheld-state scenarios, although two-Queen states remained especially difficult.

  • Generalisation setup: The experiments withheld Jack–King, Jack–Queen, Queen–Jack, and two-Queen card combinations from training.The withheld states forced the algorithms to generalise their policies to novel situations.
  • Generalisation results: Both DeepCFR and the Multi variants performed worse across all withheld-state scenarios than in the standard setting.This confirms the difficulty of generalisation in imperfect-information games.
  • Generalisation results: The MultiS and MultiD variants significantly outperformed DeepCFR across the withheld-state scenarios.Specialised approximators for each betting sequence generalised more effectively than a single global approximator.
  • Generalisation results: With two Queens withheld, DeepCFR failed to learn a coherent strategy, while the Multi variants showed very high variance between runs.The authors identify these states as a particularly difficult generalisation challenge, possibly because of their strategic importance.
  • Implications: The results indicate that decomposing approximation across specialised models is a promising direction for large, complex imperfect-information games.The experiments were designed specifically to test whether multiple specialised approximators improve generalisation.

V. CONCLUSION

LUGL enables non-incremental learners, particularly gradient-boosted trees, to achieve competitive reinforcement-learning performance. Across perfect- and imperfect-information games, it improves learning stability and often outperforms neural-network baselines, while remaining within the statistical realm.

  • V. CONCLUSION: LUGL enables non-incremental learners, specifically gradient-boosted trees, to achieve competitive performance in reinforcement learning environments.Its local table separates data collection from model training, while periodic distillation trains on coherent policy snapshots and resets the table.
  • V. CONCLUSION: LUGL produces smooth, monotonic Glicko-2 improvement in perfect-information games and consistent exploitability reduction in imperfect-information games.The same experiments also indicate greater robustness and generalization capabilities.
  • V. CONCLUSION: LUGL frequently outperforms standard neural-network methods, including rapid convergence against DQN and lower exploitability than DeepCFR across the tested games.In Flop5 Hold’em, LUGL-CFR outperformed the Single Deep CFR baseline by 100 mbb/h in head-to-head winnings.
  • V. CONCLUSION: The approach remains within the statistical realm, and stronger generalization may require extracting global proofs, rules, or features from trajectories.The paper points to methods such as inductive logic programming as a possible direction.

APPENDIX A LIGHTGBM HYPERPARAMETERS

The appendix reports LightGBM configurations used across experimental domains and compares settings by standardization, runtime matching, or training-data matching. Capacity effects for SD-CFR are examined separately, with lower values indicating better performance.

  • APPENDIX A LIGHTGBM HYPERPARAMETERS: The Small LightGBM setting is the standard configuration for every game except Flop5 Holdem.The Time setting is tuned to match SD-CFR computation time, while the Data setting matches SD-CFR training data.
  • APPENDIX A LIGHTGBM HYPERPARAMETERS: The Data setting uses the same amount of training data as SD-CFR but runs 15 times slower.The Time setting instead targets similar computation time to SD-CFR.
  • APPENDIX A LIGHTGBM HYPERPARAMETERS: Figure 6 studies how network capacity affects SD-CFR performance, with lower values indicating better performance.
  • APPENDIX A LIGHTGBM HYPERPARAMETERS: SD-CFR capacity experiments compare smaller, baseline, and larger neural networks using 96, 192, and 384 card block units, respectively.The corresponding other-layer widths are 32, 64, and 128 units.
Loading 2609.03660v1…