RL with Learnable Textual Feedback: A Bilevel Approach

Reinforcement learning with verifiable rewards can improve LLM reasoning, but learning remains sample-inefficient when terminal rewards are sparse. This has motivated a growing line of work on RL with textual feedback, where a critic model generates natural language feedback to guide a reasoning model (the actor), augmenting scalar rewards with richer learning signals. However, existing methods typically treat feedback as fixed or auxiliary, which misses a key property: feedback should not merely be correct, but should improve the policy (actor model) when provided in context. This motivates a paradigm of \textit{learnable textual feedback for RL}. Yet the learnability and usefulness of feedback depend on the policy's ability to learn from it, making RL with learnable feedback an inherently bilevel problem. We formalize this coupling as a Stackelberg bilevel program and derive \emph{Bilevel Natural Language Actor-Critic} (Bi-NAC), which jointly trains a critic to generate reward-improving feedback and an actor to exploit it. Across MATH-500, MBPP, and GPQA, Bi-NAC improves sample and parameter efficiency over RL and fixed-critic baselines: our 2B model outperforms the 3B GRPO baseline, achieving 46.6% versus 41.4% on MATH-500, while our 6B model surpasses the 7B GRPO baseline, achieving 49.3% versus 43.6% on GPQA. Our code is available at GitHub Repository.

Teaching AI models how to solve complex math or coding problems often relies on a pass-or-fail reward at the very end of a task. If a model gets everything wrong during training, it receives no guidance on how to fix its mistakes, stalling its learning progress. While some methods use a second critic model to provide feedback, this feedback is usually static and fails to adapt to how the main model actually learns. To solve this, we develop Bi-NAC (Bilevel Natural Language Actor-Critic), a framework that pairs the main model with a learnable critic. Instead of giving generic feedback, the critic is explicitly trained to generate feedback tailored to improve the main model's next response. This creates an aligned framework where the critic learns to provide better feedback, and the main model learns to effectively leverage it. As a result, Bi-NAC drastically reduces the computing time needed for training. Further, smaller models trained using this targeted feedback approach consistently outperform much larger, traditional models on difficult reasoning benchmarks.