Metraipolis › archive › dc_a875110f2945
EPIG-Tree: Compute-Optimal Branching for Gradient-Efficient Reinforcement Learning — arXiv:2609.20004
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.20004
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T03:23:58.736Z
- SHA-256 of the archived text
669063e28112dfafde9a4aec42f0f6baadea5b63cbec3fe6123f98d3e84ca046- Stable URL of this page
https://metraipolis.com/documento/dc_a875110f2945
How to cite
EPIG-Tree: Compute-Optimal Branching for Gradient-Efficient Reinforcement Learning — arXiv:2609.20004 — arXiv (en), https://arxiv.org/abs/2609.20004 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a875110f2945 (Metraipolis archive dc_a875110f2945, sha256 669063e28112dfafde9a4aec42f0f6baadea5b63cbec3fe6123f98d3e84ca046)
BibTeX
@misc{dca875110f2945,
title = {EPIG-Tree: Compute-Optimal Branching for Gradient-Efficient Reinforcement Learning — arXiv:2609.20004},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.20004},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a875110f2945; sha256 669063e28112dfafde9a4aec42f0f6baadea5b63cbec3fe6123f98d3e84ca046},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20004. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Reward-based reinforcement learning for language models, exemplified by Group Relative Policy Optimization (GRPO), collapses an entire stochastic trajectory into a single scalar reward. This is clean and scalable, but it explores and allocates reward inefficiently: a trajectory may contain many causal decisions, recovery attempts, and environment-randomness events, yet every token or action inherits one trajectory-level advantage. We study tree-based rollout construction as a compute-allocation problem for policy-gradient estimation. Our central claim is that branches should be placed not where the policy is merely uncertain, but where an additional branch most reduces uncertainty about the policy gradient per unit of compute. From a law-of-total-variance decomposition of the local policy-gradient random variable, we derive two allocation laws: new branches reduce decision uncertainty, while repeated suffix rollouts reduce continuation uncertainty. The resulting EPIG-Tree score allocates branches using the already computed rollouts. It estimates occupancy- and score-weighted value uncertainty, along with a suffix law $n_e \propto w_e \|\nabla_\theta \log \pi(a_e|h_e)\| \sigma_e / \sqrt{c_e}$. Empirically, EPIG reduces gradient MSE in cloned-state control, winning in all nine dense continuous-control environments of a 13-environment sweep and recovering the reference gradient direction near-perfectly, and it improves frozen-LLM gradient calibration relative to entropy branching. In online single-turn math, tree-local credit beats flat GRPO, while branch placement is secondary to token-level credit assignment. In online multi-turn Wordle, EPIG attains the highest final win rate (0.850), overtaking flat GRPO, which saturates early at 0.790, and entropy branching as training proceeds, confirming that the gradient-estimation advantage transfers to a stateful, large-action setting.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-18 in cs.AI).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2609.20004 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T03:04:13.882Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).