9 papers
Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
Yuepeng Yang, Yuxin Chen, Yuejie Chi
Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and…
On the Emergence of Implicit Curriculum in RLVR Learning Dynamics
Yu Huang, Zixin Wen, Yuejie Chi +4
Reinforcement learning with verifiable rewards (RLVR) has been a main driver of recent breakthroughs in large reasoning models. Yet it remains a mystery how rewards based solely on…
Agentic Transformers Provably Learn to Search via Reinforcement Learning
Tong Yang, Yu Huang, Yingbin Liang +1
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…
Preconditioning Benefits of Spectral Orthogonalization in Muon
Jianhao Ma, Yu Huang, Yuejie Chi +1
The Muon optimizer, a matrix-structured algorithm that leverages spectral orthogonalization of gradients, is a milestone in the pretraining of large language models. However, the u…
Multi-head Transformers Provably Learn Symbolic Multi-step Reasoning via Gradient Descent
Tong Yang, Yu Huang, Yingbin Liang +1
Transformers have demonstrated remarkable capabilities in multi-step reasoning tasks. However, understandings of the underlying mechanisms by which they acquire these abilities thr…
Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization
Yu Huang, Zixin Wen, Aarti Singh +2
The ability to reason lies at the core of artificial intelligence (AI), and challenging problems usually call for deeper and longer reasoning to tackle. A crucial question about AI…