The coverage principle: How pre-training enables post-training New preprint where we look at the mechanisms through which next-token prediction produces models that succeed at downstream tasks. The answer involves a metric we call the "coverage profile", not cross-entropy.

The new call for Motwani postdocs application is now open! academicjobsonline.org/ajo/jobs/30865 BTW- Not quite ready for a postdoc? We updated the TCS Masters programs spreadsheet: www.cs.princeton.edu/~smattw/mast... Any career stage and in the (SF) Bay Area? Save the date for TOCA-SV on 11/7!

Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking. A totally new framework based on ~backtracking~ for using process verifiers to guide inference, w/ connections to approximate counting/sampling in theoretical CS. Paper: www.arxiv.org/abs/2510.03149

MSR NYC is hiring spring and summer interns in AI/ML/RL! Apply here: jobs.careers.microsoft.com/global/en/jo...

🚨Microsoft Research NYC is hiring🚨 We're hiring postdocs and senior researchers in AI/ML broadly, and in specific areas like test-time scaling and science of DL. Postdoc applications due Oct 22, 2025. Senior researcher applications considered on a rolling basis. Links to apply: aka.ms/msrnyc-jobs

Microsoft Research New York City (www.microsoft.com/en-us/resear...) is seeking applicants for multiple Postdoctoral Researcher positions in ML/AI! These are positions for up to 2 years, starting in July 2026. Application deadline: October 22, 2025

Quick reminder: The deadline for our workshop on Foundations of Reasoning in Language Models (FoRLM) at NeurIPS 2025 is next Wednesday, Sept 3!

Announcing the first workshop on Foundations of Language Model Reasoning (FoRLM) at NeurIPS 2025! 📝Soliciting abstracts that advance foundational understanding of reasoning in language models, from theoretical analyses to rigorous empirical studies. 📆 Deadline: Sept 3, 2025

For those at ICML, Audrey will be presenting this paper at the 4:30pm poster session this afternoon! West Exhibition Hall B2-B3 W-1009

ICML's election for their board of directors has begun. I've thrown my hat in the ring. Please consider voting for Gautam Kamath. I have experience with the governance of TMLR, COLT, and ALT, and I think I've demonstrated myself as a consciencious and engaged community member.

This week's #PaperILike is "The Power of Resets in Online Reinforcement Learning" (Mhammedi et al., 2024). If you're doing RL in sim, why not use the sim to its full potential? Reset to any state! (gym.Env.reset() is not all we need.) PDF: arxiv.org/abs/2404.15417

📣Join us at COLT 2025 in Lyon for a community event! 📅When: Mon, June 30 | 16:00 CET What: Fireside chat w/ Peter Bartlett & Vitaly Feldman on communicating a research agenda, followed by mentorship roundtable to practice elevator pitches & mingle w/ COLT community! let-all.com/colt25.html

Hiring a postdoc to scale up and deploy RL-based planning onto some self-driving cars! We'll be building on arxiv.org/abs/2502.03349 and learn what the limits and challenges of RL planning are. Shoot me a message if interested and help spread the word please! Full posting to come in a bit.

At the IDEAL annual meeting and saw this paper presented. Basically: reducing length of chain of thought LLM computations by deleting intermediate computations, more like classical functional programming where only function call and return values are important. arxiv.org/abs/2503.14337

RADEMACHER CHAOS 🤘

Dhruv Rohatgi will be giving a lecture on our recent work on comp-stat tradeoffs in next-token prediction at the RL Theory virtual seminar series (rl-theory.bsky.social) tomorrow at 2pm EST! Should be a fun talk---come check it out!!

Later today, Sikata and Marcel will talk about their recent work on oracle-efficient RL with ensembles. Join us!

The abstract submission deadline for FoPt has been extended to the 21st of May (11:59pm UTC). Submission website: openreview.net/group?id=lea...

Announcing the first workshop on Foundations of Post-Training (FoPT) at COLT 2025! 📝 Soliciting abstracts/posters exploring theoretical & practical aspects of post-training and RL with language models! 🗓️ Deadline: May 19, 2025

Announcing the first workshop on Foundations of Post-Training (FoPT) at COLT 2025! 📝 Soliciting abstracts/posters exploring theoretical & practical aspects of post-training and RL with language models! 🗓️ Deadline: May 19, 2025

Is Best-of-N really the best we can do for language model inference? New paper (appearing at ICML) led by the amazing Audrey Huang (ahahaudrey.bsky.social) with Adam Block, Qinghua Liu, Nan Jiang, and Akshay Krishnamurthy (akshaykr.bsky.social). 1/11

Last seminars before the summer break: 04/29: Max Simchowitz (CMU) 05/06: Jeongyeol Kwon (Univ. of Widsconsin-Madison) 05/20: Sikata Sengupta & Marcel Hussing (Univ. of Pennsylvania) 05/27: Dhruv Rohatgi (MIT) 06/03: David Janz (Univ. of Oxford) 06/10: Nneka Okolo (MIT)

What is the place of exploration in today's AI landscape and in which settings can exploration algorithms address current open challenges? Join us to discuss this at our exciting workshop at @icmlconf.bsky.social 2025: EXAIT! exait-workshop.github.io #ICML2025

Reinforcement learning has led to amazing breakthroughs in reasoning (e.g., R1), but can it discover truly new behaviors not already present in the base model? A new paper with Zak Mhammedi and Dhruv Rohatgi: The Computational Role of the Base Model in Exploration arxiv.org/abs/2503.07453

Join us tomorrow to attend Vlad's presentation! Related to the seminar from last week, but this time in the offline setting. Tuesday March 25, 6 PM UTC.

Excited to share new paper: Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity Link: arxiv.org/abs/2503.04712 Work with Karthik Sridharan and two great undergrads at Cornell, Daniel Yiming Cao and Benjamin Tang 1/8

Dylan J. Foster, Zakaria Mhammedi, Dhruv Rohatgi: Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration https://arxiv.org/abs/2503.07453 https://arxiv.org/pdf/2503.07453 https://arxiv.org/html/2503.07453

We have a new blog post on reinforcement learning theory for language model post training! By Akshay Krishnamurthy (@akshaykr.bsky.social) and Audrey Huang (@ahahaudrey.bsky.social)! www.let-all.com/blog/2025/03...

Congratulations to @lestermackey.bsky.social for receiving the 2025 COPSS Award! 🎉👏 Lester is currently the Chair of the Section on Bayesian Statistical Sciences (SBSS) of the American Statistical Association.

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier arxiv.org/abs/2502.12465 New paper (another fun internship project!) with Dhruv Rohatgi, Adam Block, Audrey Huang (ahahaudrey.bsky.social), and Akshay Krishnamurthy (akshaykr.bsky.social). 1/11

What are the minimal supervised learning primitives required to perform RL efficiently? New paper led by my amazing intern Dhruv Rohatgi: Necessary and Sufficient Oracles: Toward a Computational Taxonomy for Reinforcement Learning arxiv.org/abs/2502.08632 1/

Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, Dylan J. Foster: Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning und... https://arxiv.org/abs/2502.12465 https://arxiv.org/pdf/2502.12465 https://arxiv.org/html/2502.12465

What kind of policy optimization is this?

One of the reasons LLMs make RL fun again is: 1) They make efficient exploration and low sample complexity genuinely matter 2) They give us good base policies so less time flailing around

It’s finally out — and I got to blurb it!

Finally finally finally some scaling curves for imitation learning in the large-scale-data regime: arxiv.org/abs/2411.04434

📣My team at Microsoft Research New York is hiring a senior researcher in AI, both broadly in AI/ML, and in some specific areas including science of deep learning and modular transfer learning. Apply by February 7, 2025 on the link below. jobs.careers.microsoft.com/global/en/jo...

Happy new year! Upcoming: 01/07: Jean Tarbouriech 01/14: Adrienne Tuynman 01/21: Victor Boone 02/18: Itai Sufaro 02/25: Jongmin Lee 03/04: Dhruv Rohatgi 03/11: David Cheikhi 03/18: Zakaria Mhammedi 03/25: Vlad Tkachuk

If you are into ML theory (RL or not) with a proven track record, and you are interested in an industry research position, PM me. Feel free to spread the word.

Given a high-quality verifier, language model accuracy can be improved by scaling inference-time compute (e.g., w/ repeated sampling). When can we expect similar gains without an external verifier? New paper: Self-Improvement in Language Models: The Sharpening Mechanism arxiv.org/abs/2412.01951

Preaching THE POWER OF RESETS with Zak! Poster 6402 in the West ballroom

In their 2024 NeurIPS paper on RL under latent dynamics, researchers examine whether existing algorithms designed for simple RL problems can be used to solve more complex RL problems. Dylan Foster discusses the modular approach his team explored. www.microsoft.com/en-us/resear...

Happening now!

www.microsoft.com/en-us/resear... Did this short MSR podcast about our paper arxiv.org/abs/2410.17904 on modular approaches to RL with latent dynamics!

Heading to neurips! Stop by and say hi if you're around.

📣I'm hiring PhD interns for combined theory+empirical projects in: exploration in post-training, multi-task learning in autoregressive models, distillation, reasoning beyond CoT. Apply on the link below. If you're at #NeurIPS2024, message me to chat. jobs.careers.microsoft.com/global/en/jo...

I wrote a survey article on computationally efficient methods for "robust" mean estimation, including robustness to contamination, heavy-tailed data, or in the sense of differential privacy. The same ideas are useful for all 3 (seemingly-different) forms of robustness! 1/2 arxiv.org/abs/2412.02670

the most important social media outlet ever has just made its transition to @bsky.app --- follow @rl-theory.bsky.social if you don't want to miss out on the latest research on RL theory!

The FATE group at @msftresearch.bsky.social NYC is accepting applications for 2025 interns. 🥳🎉 For full consideration, apply by 12/18. jobs.careers.microsoft.com/global/en/jo... Interested in AI evaluation? Apply for the STAC internship too! jobs.careers.microsoft.com/global/en/jo...

For those who don’t feel like they fit into my Grumpy Machine Learners list (which I still need to update based on 100+ requests) I’ve created another starter pack: go.bsky.app/Js7ka12 (Self) nominations welcome.