{"id":"arxiv/2606.00183","url":"https://arxiv.org/abs/2606.00183","tags":["cs.LG","cs.AI","math.OC","stat.ML"],"score":0,"title":"Agentic Transformers Provably Learn to Search via Reinforcement Learning","domain":"cs.LG","source":"arxiv","authors":["Tong Yang","Yu Huang","Yingbin Liang","Yuejie Chi"],"reviews":0,"subject":"cs.LG","summary":"Tree search is a central abstraction behind many language-agent reasoning and decision-making tasks: agents must explore actions, remember failures, and backtrack toward promising alternatives. Yet, we lack a theoretical understanding of how transformer-based policies acquire such search capabilities from the training dynamics of reinforcement learning (RL). We study this question in a stochastic $k$-ary tree environment, where an agentic transformer observes only its trajectory history through interaction and receives a terminal reward for reaching a hidden leaf goal node. We first…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-29","reactions":{}}