Cost-Aware Learning

• URL: http://arxiv.org/abs/2604.28020v1
• Date: Thu, 30 Apr 2026 15:39:09 GMT
• Title: Cost-Aware Learning
• Abstract summary: We consider the problem of Cost-Aware Learning, where sampling different component functions incur different costs.<n>We propose the Cost-Aware Descent algorithm for convex functions, and derive its cost complexity to attain an error of $$.<n>We introduce Cost-Aware GRPO, an algorithm designed to reduce the cost of policy optimization while preserving performance.
• Score: 72.31444819326795
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of Cost-Aware Learning, where sampling different component functions of a finite-sum objective incurs different costs. The objective is to reach a target error while minimizing the total cost. First, we propose the Cost-Aware Stochastic Gradient Descent algorithm for convex functions, and derive its cost complexity to attain an error of $ε$. Furthermore, we establish a lower bound for this setting and provide a subset selection algorithm to further reduce the cost of training. We apply our theoretical insights to reinforcement learning with language models, where the computational cost of policy gradients varies with sequence length. To this end, we introduce Cost-Aware GRPO, an algorithm designed to reduce the cost of policy optimization while preserving performance. Empirical results on 1.5B and 8B LLMs demonstrate that our approach reduces the tokens used in policy optimization by up to about 30% while matching or exceeding baseline accuracy.

Related papers

• Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization [18.737087162461563]
  Test-time compute scaling has become a powerful lever for improving large language model performance.<n>Yet deploying these techniques under finite inference budgets requires a decision that current systems largely ignore.<n>We formalize this as a constrained optimization problem (maximize expected accuracy subject to an average compute budget) and solve it with a two-stage Solve-then-Learn pipeline.
  arXiv  Detail & Related papers  (2026-04-16T10:39:22Z)
• Cost-aware Stopping for Bayesian Optimization [46.95172329282389]
  We propose a cost-aware stopping rule for Bayesian optimization that adapts to varying evaluation costs and is free of tuning.<n>We prove a theoretical guarantee bounding the expected cumulative evaluation cost incurred by our stopping rule when paired with state-of-the-art acquisition functions.
  arXiv  Detail & Related papers  (2025-07-16T17:54:14Z)
• Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs [3.1269598124014264]
  We propose a novel algorithm for the extension of the BOCVS problem with random and unknown costs.<n>Our algorithm achieves a sub-linear rate in both quality regret and cost regret, addressing the objective of the BOCVS problem more effectively than previous analyses.
  arXiv  Detail & Related papers  (2024-12-20T13:00:39Z)
• Cost-Aware Query Policies in Active Learning for Efficient Autonomous Robotic Exploration [0.0]
  This paper analyzes an AL algorithm for Gaussian Process regression while incorporating action cost. Traditional uncertainty metric with a distance constraint best minimizes root-mean-square error over trajectory distance.
  arXiv  Detail & Related papers  (2024-10-31T18:35:03Z)
• Time-Varying Convex Optimization with $O(n)$ Computational Complexity [0.0]
  We consider the problem of unconstrained convex optimization, where the cost function changes with time. Our proposed algorithms only require the first-order derivatives of the cost function with respect to the decision variable. Specifically, the proposed algorithms reduce computational cost from $(n3)$ to $O(n)$ per timestep.
  arXiv  Detail & Related papers  (2024-10-19T06:45:05Z)
• $\mathbf{(N,K)}$-Puzzle: A Cost-Efficient Testbed for Benchmarking Reinforcement Learning Algorithms in Generative Language Model [50.636423457653066]
  We present a generalized version of the 24-Puzzle: the $(N,K)$-Puzzle, which challenges language models to reach a target value $K$ with $N$ integers. We evaluate the effectiveness of established RL algorithms such as Proximal Policy Optimization (PPO), alongside novel approaches like Identity Policy Optimization (IPO) and Direct Policy Optimization (DPO)
  arXiv  Detail & Related papers  (2024-03-11T22:24:14Z)
• Scalable Online Exploration via Coverability [45.66375686120087]
  Exploration is a major challenge in reinforcement learning, especially for high-dimensional domains that require function approximation. We introduce a new objective, $L_Coverage, which generalizes previous exploration schemes and supports three fundamental desideratas. $L_Coverage enables the first computationally efficient model-based and model-free algorithms for online (reward-free or reward-driven) reinforcement learning in MDPs with low coverability.
  arXiv  Detail & Related papers  (2024-03-11T10:14:06Z)
• Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning [57.154674117714265]
  We show that the number of samples needed to learn a near-optimal policy with FQI-log scales with the accumulated cost of the optimal policy. We empirically verify that FQI-log uses fewer samples than FQI trained with squared loss on problems where the optimal policy reliably achieves the goal.
  arXiv  Detail & Related papers  (2024-03-08T15:30:58Z)
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation [67.66904892192794]
  We propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for reinforcement learning.<n>MQL-UCB achieves minimax optimal regret of $tildeO(dsqrtHK)$ when $K$ is sufficiently large and near-optimal policy switching cost.<n>Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation.
  arXiv  Detail & Related papers  (2023-11-26T08:31:57Z)
• Target-based Surrogates for Stochastic Optimization [26.35752393302125]
  We consider minimizing functions for which it is expensive to compute the (possibly) gradient. Such functions are prevalent in computation reinforcement learning, imitation learning and adversarial training. Our framework allows the use of standard optimization algorithms to construct surrogates which can be minimized efficiently.
  arXiv  Detail & Related papers  (2023-02-06T08:08:34Z)
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm [50.50545326342971]
  We formulate the problem of maximizing a non-linear concave function of multiple long-term objectives.<n>A policy-gradient based model-free algorithm is proposed for the problem.<n>The proposed algorithm is shown to achieve convergence to within an $epsilon$ of the global optima.
  arXiv  Detail & Related papers  (2021-05-28T22:20:54Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• Online Apprenticeship Learning [58.45089581278177]
  In Apprenticeship Learning (AL), we are given a Markov Decision Process (MDP) without access to the cost function. The goal is to find a policy that matches the expert's performance on some predefined set of cost functions. We show that the OAL problem can be effectively solved by combining two mirror descent based no-regret algorithms.
  arXiv  Detail & Related papers  (2021-02-13T12:57:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.