Discovering High-Quality Chess Puzzles with Offline Reinforcement Learning

Technical Summary: Discovering High-Quality Chess Puzzles with Offline Reinforcement Learning

Problem Statement

The acquisition of new skills relies heavily on deliberate practice, yet the creation of high-quality pedagogical materials is often a bottleneck due to the need for significant domain expertise and time. In the domain of chess, online platforms like Chess.com and Lichess generate millions of puzzles automatically from player games to maintain user engagement. However, unlike puzzles curated by human experts, these algorithmically generated puzzles often lack proven pedagogical value. Current recommendation systems rely on heuristics (e.g., bucketed uniform sampling based on Elo ratings) that do not explicitly optimize for learning outcomes. The core challenge is to leverage massive datasets of user interactions to automatically discover and recommend puzzles that maximize learning growth, particularly for beginners and those whose progress has stagnated.

Methodology

The authors propose an offline Reinforcement Learning (RL) framework to learn a policy for recommending chess puzzles using 1.5 billion puzzle-solving attempts from 3.1 million users over one year.

1. Data and State Representation:

• Dataset: 1.5 billion interactions involving 441,113 unique puzzles.
• State ($s$): Modeled as a continuous $k$-dimensional embedding derived from a user's puzzle history and learning progress (specifically Elo rating and correctness).
• Action ($a$): The selection of one puzzle from a discrete space of $N = 441,113$ puzzles.
• Reward ($r$): A scalar function quantifying learning benefit, defined by the difficulty-weighted correctness: $r(s, a) = \frac{c}{N} \exp(\alpha \cdot (Elo_{puzzle} - Elo_{user}))$, where $c$ is the number of correct moves, $N$ is total moves, and $\alpha$ is a hyperparameter balancing partial correctness against difficulty.

2. Policy Learning Architecture:

• Model: A causal Transformer architecture is used to model the non-Markovian policy $\pi_\theta$. It processes sequences of user and puzzle embeddings.
• Objective: The authors derive an advantage-weighted actor-critic objective for offline policy learning. To mitigate extrapolation errors common in off-policy learning, they penalize the Kullback-Leibler (KL) divergence between the learned policy and the behavior policy ($\pi_b$).
  • The objective maximizes: $E_{s \sim D} [ E_{a \sim \pi_\theta} [ Q^\pi_\phi(s, a) - V^\pi_\psi(s) ] - \beta D_{KL}(\pi_\theta(\cdot|s) \| \pi_b(\cdot|s)) ]$.
• Training: The system employs a value network ($V$) and an action-value network ($Q$) trained via expectile regression and standard Bellman updates, respectively. Due to the large action space, the policy is parameterized using an exponentiated inner product between the transformer output and puzzle embeddings, approximated via in-batch negative sampling.

3. Evaluation Strategy:

• Offline Policy Evaluation: Since randomized controlled trials are impractical at scale, the authors use one-step importance sampling to estimate the performance of the learned policy ($\pi_\theta$) relative to the behavior policy ($\pi_b$) on a holdout dataset.
• Qualitative Analysis: To assess puzzle quality, the team recruited 8 expert chess players (ranging from Expert to Grandmaster titles) to annotate puzzles based on a rubric covering calculation, pattern recognition, fun, and appropriateness. These annotations were used to calibrate Large Language Models (LLMs) to scale the evaluation process.

Key Results

1. Quantitative Improvements (Offline Evaluation):

• The learned policy ($\pi_\theta$) demonstrated statistically significant improvements over the existing Chess.com heuristic policy ($\pi_b$) for beginners (Elo 100–1000).
• For the 100–600 Elo range, the learned policy achieved a return of 52.9 for the stagnant group and 58.8 for the growth group, compared to 14.3 and 17.7 respectively for the behavior policy. The Average return across all groups for the learned policy was 57.4, compared to 16.9 for the behavior policy.
• Improvements were most pronounced for the "Stagnant Group" (users with minimal Elo growth) in the smallest Elo bucket (100–600), where the policy showed a larger relative improvement over the behavior policy compared to the growth group in that specific bucket. For all other Elo buckets, the policy performed relatively better on growth group users.
• For higher Elo players (>1500), the performance difference between the learned policy and the behavior policy was negligible, indicating that optimal puzzle selection is most critical for novice learners.

2. Qualitative Findings:

• Expert and LLM-calibrated evaluations indicated that the puzzles recommended by the learned policy were rated as slightly more enjoyable, harder (relative to user rating), and higher in calculation and pattern-recognition scores compared to the original system.
• The "Fun" metric showed a statistically significant increase (+4.77 points), and "Rating" (appropriateness) increased by +4.78 points.

Significance and Claims

The paper claims to demonstrate that offline reinforcement learning can successfully extract pedagogical value from massive, uncurated user interaction data. By moving beyond simple heuristic matching, the system learns to identify puzzle sequences that correlate with skill acquisition.

The authors emphasize that their pipeline offers a pathway to understanding the pedagogical value of practice items using general user interaction data. They note that while their results are promising, particularly for beginners and stagnant learners, direct human evaluation (e.g., A/B testing in a live environment) is still required to fully validate the system's impact on long-term learning. The work suggests that similar approaches could be applied to other educational domains, such as math, language learning, or coding, where large-scale interaction data exists but high-quality, curated practice materials are scarce.