Exploration remains a key bottleneck for reinforcement learning (RL) post-training of large language models (LLMs), where sparse feedback and large action spaces can lead to premature collapse into repetitive behaviors. We propose Verbalized Action Masking (VAM), which verbalizes an action mask in the prompt and enforces that the model outputs an action from the masked set. Building on this interface, we introduce iterative action-space pruning: if the target action is not sampled, we remove valid sampled actions from the mask and resample under the reduced candidate set, repeating until the target is sampled or a fixed budget is exhausted. We study VAM in chess and evaluate it under two training regimes: an engine-play regime that generates states via play against an engine opponent and a fixed-dataset regime that trains from a fixed dataset of positions with verifier scores. Across held-out chess puzzles and full-game play measured by average centipawn loss (ACPL), VAM improves learning efficiency and final performance over strong baselines, highlighting verbalized masking as a practical mechanism for controllable exploration in LLM RL post-training.
Figures & tables
Figure 1: Overview of Verbalized Action Masking (VAM) with iterative action-space pruning. Given a state and a provided set of allowed actions, we prompt the LLM and sample rollout groups for Group Relative Policy Optimization (GRPO). Each sampled output is parsed into an action and then evaluated by a verifier to produce reward feedback. If the target condition is not met in the current round (for example, the target action is not sampled), we mask the distinct valid sampled actions out of the allowed action set and resample under the updated prompt. This iterative pruning procedure increases within-state action coverage and yields more informative grouped on-policy updates.
Figure 4: Performance on held-out chess puzzles. Pass@1 accuracy for selecting the dataset-provided solution move on the 10,000-position test set. The left panel compares fixed-dataset GRPO baselines under three engine-derived reward signals (expected-score proxy μexp , win-rate μwin , and rank-based μrank ; Eqs. 8 and 9 ). The right panel compares VAM with iterative action-space pruning against GRPO under the same fixed dataset and matched rollout budget for Qwen2.5-3B-Instruct and Qwen2.5-7B-Instruct. The horizontal axis counts GRPO gradient updates, and each point evaluates the current policy with fixed decoding settings over the full test set. Dashed horizontal lines indicate rejection-sampled SFT baselines.
Figure 5: Move quality in full games against Stockfish. Average centipawn loss (ACPL; lower is better) during evaluation against fixed Stockfish opponents at depth 1 and depth 5, shown for Qwen2.5-3B-Instruct and Qwen2.5-7B-Instruct. We report overall ACPL as well as per-opponent ACPL trajectories over training. VAM is trained with engine-play position generation and iterative action-space pruning, while the GRPO baseline uses the same verifier and prompt interface but omits pruning. Dashed horizontal lines indicate rejection-sampled SFT baselines. VAM consistently reaches lower ACPL across opponents and model sizes, indicating stronger move quality under full-game play.
Figure 6: Fixed-dataset versus engine-play training regimes for VAM. Radar plots summarize performance and training statistics for VAM trained either on a fixed dataset or with engine-play position generation via games against a fixed engine opponent, shown for Qwen2.5-7B-Instruct (left) and Qwen2.5-3B-Instruct (right). Axes report pass@1 puzzle accuracy, KL loss to the reference policy, average response length, mean verifier reward, and full-game move quality measured by ACPL (overall and per-move). Within each model, each metric is linearly normalized across the two regimes for visualization, and numeric annotations indicate the raw values. The profiles highlight a trade-off between one-step puzzle performance and full-game play quality across regimes.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Parameter
GRPO
VAM
Parameter
SFT
Batch size
128
128
Global batch size
32
Mini batch size
128
128
Total source prompts
100,000
GRPO group size
8
8
Samples per prompt
8
Sampling temperature
1.0
1.0
Sampling temperature
0.6
Sampling top- p
1.0
1.0
Sampling top- p
0.9
Max response tokens
2000
2000
Max response tokens
2000
Appendix
Table 1: Hyperparameters for GRPO, VAM, and SFT.
Figure 7: Prompt used for Verbalized Action Masking (VAM).
Reinforcement learning (RL) has demonstrated notable success in post-training large language models (LLMs) as agents for tasks such as computer use, tool calling, and coding. However, exploration remains a central challenge in RL for LLM agents, especially as they operate in language-action spaces with complex observations and sparse outcome rewards. In this work, we address exploration for LLM agents by leveraging the ability of LLMs to plan and reason in language about the environment to shift exploration from low-level actions to higher-level language strategies. We thus propose Strategy-Guided Exploration (SGE), which first generates a concise natural-language strategy that describes what to do to make progress toward the goal, and then generates environment actions conditioned on that strategy. By exploring in the space of strategies rather than the space of actions, SGE induces structured and diverse exploration that targets different environment outcomes. To increase strategy diversity during RL, SGE introduces mixed-temperature sampling, which explores diverse strategies in parallel, along with a strategy reflection process that grounds strategy generation on the outcomes of previous strategies in the environment. Across UI interaction, tool-calling, coding, and embodied agent environments, SGE consistently outperforms exploration-focused RL baselines, improving both learning efficiency and final performance. We show that SGE enables the agent to learn to solve tasks too difficult for the base model.
Reinforcement learning (RL) has become a standard paradigm for post-training and aligning Large Language Models (LLMs), yet recent evidence suggests it faces a persistent "capability ceiling": unlike classical RL systems that discover novel strategies, RL for LLMs often acts as a mere refiner of patterns already latent in pre-trained weights. In this work, we identify a fundamental structural bottleneck: while classical RL relies on compact, informative Markov states, current LLM post-training formulations are tethered to an ever-expanding history of actions. We revisit a classical principle long central to RL yet absent from LLM post-training: explicit Markov states. Theoretically, we provide rigorous guarantees demonstrating that leveraging estimated Markov states can significantly reduce sample complexity. Empirically, we show that introducing Markov states consistently breaks the performance boundaries of standard RL post-training across a suite of complex logic puzzles. Our findings suggest that moving beyond "history-as-state" modeling in favor of structured Markovian representations is essential for unlocking open-ended discovery and genuinely new reasoning capabilities in Generative AI.
Recent years have witnessed the rapid adoption of reinforcement learning (RL) in large language model (LLM) post-training, with substantial gains in mathematical reasoning and code generation. In practical systems, however, policy updates and differences between rollout and training engines can make sampled responses off-policy. Sequence-level masking addresses this mismatch by deciding whether an entire response should contribute to optimization. A common masking rule uses the length-normalized geometric mean of sampled token probability ratios. Its signed log-ratios can cancel across positions, concealing substantial bidirectional policy drift. We propose Cancellation-Aware Response Masking (CARM), a sequence-level mask that takes the absolute value of each token log-ratio before averaging, preventing opposing probability changes from canceling. We prove that accepted responses satisfy a joint bound on the fraction of sampled-token ratios outside a prescribed band and their mean log-distance beyond its boundaries. Experiments on mathematical reasoning and code generation show that CARM improves mean@16 averaged over AIME 2024/2025/2026 and BeyondAIME by up to 3.13 percentage points over geometric-mean masking, and increases average pass@1 across four code benchmarks by 2.88 points over the strongest evaluated baseline. These findings support CARM as a theoretically grounded and effective method for response-level off-policy control in LLM reinforcement learning.