Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers
Abstract
Reinforcement learning (RL) has become a standard tool for post-training language models on reasoning tasks, where the policy is updated by reward feedback while exploring the space of responses. Despite its empirical success, theoretical understanding of RL post-training remains limited, in particular of why on-policy exploration combined with a neural reward model is effective. In this paper, we address this question by modeling the reward as a hierarchical function on the response space: the reward consists of infinitely many local components, each of which becomes relevant only after the preceding ones have been resolved. We show that a natural Transformer-based actor--critic algorithm, which alternates between sampling from the current KL-regularized policy, fitting a Transformer critic to the observed rewards, and updating the policy, achieves the minimax optimal rates in the query budget and in the regularization strength up to logarithmic factors, and is minimax optimal for a fixed number of prompts. In contrast, we prove that sampling from the fixed reference distribution, as in offline reward modeling, can limit regret decay to a logarithmic rate. These results show that on-policy exploration progressively zooms in on the region where the reward is concentrated, and quantify its benefit for RL post-training.
Related
- When Does Momentum Help in Reinforcement Learning with Verifiable Rewards?
- Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
- HALO: Hierarchical Evidence Selection and Reinforcement Learning for Allocating Budgeted Label Optimization from Longitudinal Clinical Records
- Safety-Certified Hierarchical Control of DC Microgrids via Continuous Deep Reinforcement Learning and Covariance-Weighted Sliding Mode Synthesis
- Learning to Solve Stochastic Controls with Unknown Drifts and Running Rewards: Theory, Algorithms and Convergence
BibTeX
@misc{nishikawa2026reinforcement,
title = {{Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers}},
author = {Naoki Nishikawa and Taiji Suzuki},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08561},
eprint = {2610.08561},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08561},
}
RIS
TY - UNPB
TI - Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers
AU - Naoki Nishikawa
AU - Taiji Suzuki
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08561
UR - https://arxiv.org/abs/2610.08561
AB - Reinforcement learning (RL) has become a standard tool for post-training language models on reasoning tasks, where the policy is updated by reward feedback while exploring the space of responses. Despite its empirical success, theoretical understanding of RL post-training remains limited, in particular of why on-policy exploration combined with a neural reward model is effective. In this paper, we address this question by modeling the reward as a hierarchical function on the response space: the reward consists of infinitely many local components, each of which becomes relevant only after the preceding ones have been resolved. We show that a natural Transformer-based actor--critic algorithm, which alternates between sampling from the current KL-regularized policy, fitting a Transformer critic to the observed rewards, and updating the policy, achieves the minimax optimal rates in the query budget and in the regularization strength up to logarithmic factors, and is minimax optimal for a fixed number of prompts. In contrast, we prove that sampling from the fixed reference distribution, as in offline reward modeling, can limit regret decay to a logarithmic rate. These results show that on-policy exploration progressively zooms in on the region where the reward is concentrated, and quantify its benefit for RL post-training.
ER -