Cost-Aware Learning

Clara Mohri; Amir Globerson; Haim Kaplan; Tomer Koren; Yishay Mansour

cs.LGApr 30, 2026

Cost-Aware Learning

Authors: Clara Mohri, Amir Globerson, Haim Kaplan, Tomer Koren, Yishay Mansour

Organizations: Kempner Institute · Harvard University · Google Research · Tel Aviv University

Abstract

We consider the problem of Cost-Aware Learning, where sampling different components of a finite-sum objective incurs different costs. The objective is to reach a target error while minimizing the total cost. We propose Cost-Aware SGD, which uses a distribution based on gradient norms and costs to sample components. We provide a thorough analysis of this algorithm, including cost-improvement bounds over baselines, a characterization of distribution proxy sub-optimality, and a lower bound. We apply our theoretical insights to reinforcement learning with language models, where the computational cost of sequence-level policy gradients varies with length. We find that the advantage magnitude serves as a high-fidelity proxy for gradient norms, and use this to introduce Cost-Aware GRPO. Empirical results on 1.5B, 4B, and 8B LLMs demonstrate that this algorithm significantly reduces the tokens used in policy optimization while matching or exceeding baseline accuracy.

Explore similar work

A First-Principles Derivation of LLM Policy Optimization: From Expected Reward to GRPO and Its Structural Extensions
Jun 15, 2026Jianghan Shen, Siqi Luo, Yue Li +9Group Relative Policy Optimization Extended Version
In-Context Learning as Implicit Policy Gradient
Jul 25, 2026Masahiro Kaneko, Timothy BaldwinIn-Context Learning Large Language Model Post-Training
Selective-Advantage Entropy-Adaptive Horizon GRPO: Asymmetric Token-Level Discounting for Efficient Reinforcement Learning of Language Models
Jun 3, 2026Chirag Chawla, Rohan Charudatt Salvi, Madhav S. BaidyaGroup Relative Policy Optimization Policy Gradient

Jun 15, 2026 · cs.AIJ/K move · Enter open · S save

A First-Principles Derivation of LLM Policy Optimization: From Expected Reward to GRPO and Its Structural Extensions

Jianghan Shen, Siqi Luo, Yue Li, Jiyao Liu+8

1Nanjing University · 2Shanghai Artificial Intelligence Laboratory · 3Shanghai Jiao Tong University · 4Peking University · 5Fudan University

Policy gradient algorithms for language models optimize the same objective

J(θ) = \mathbb{E}*{τ\sim p*θ(τ)}[R(τ)]

, which has exactly two factors: the trajectory probability

p_θ(τ)

and the reward

R(τ)

. Every method from REINFORCE to PPO to GRPO and their descendants modifies one or both factors to address a specific failure in the preceding formulation. Existing surveys organize these methods by domain or chronology, which obscures the rationale behind each design choice and the precise location of its intervention within the gradient estimator. This survey revisits the landscape of LLM policy optimization from

J(θ)

on first principles and uses the trajectory side, induced by

p_θ(τ)

, and the reward side, induced by

R(τ)

, as the two axes along which methods are located. It covers the path from REINFORCE and PPO to GRPO, as well as post-GRPO variants, Agentic RL, and GRPO-OPD. The resulting framework is unified, diagnostic, and extensible: it analyzes methods from a shared objective, identifies which side each method modifies and why, and applies the same trajectory and reward axes across these settings. Across these settings, the framework also exposes compound failures that no single-side fix resolves and that therefore require joint design of the trajectory side and the reward side. The boundary cases and coupled failures identified by this map mark where existing solutions run out and provide a principled starting point for designing the next generation of LLM policy optimization algorithms.

Group Relative Policy Optimization Extended Version First-Principles Calculation

Open paper Ask about it PDF

Abstract

Explore similar work

A First-Principles Derivation of LLM Policy Optimization: From Expected Reward to GRPO and Its Structural Extensions

In-Context Learning as Implicit Policy Gradient

Selective-Advantage Entropy-Adaptive Horizon GRPO: Asymmetric Token-Level Discounting for Efficient Reinforcement Learning of Language Models