knapsack-rl-budget-allocation

name	knapsack-rl-budget-allocation
title	Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget Allocation
version	0.0.2
engine	skillxiv-v0.0.2-claude-opus-4.6
license	MIT
url	https://arxiv.org/abs/2509.25849
keywords	["resource-allocation","RL-training","exploration-efficiency","curriculum-learning","GRPO"]
description	Improve RL training for LLMs by dynamically allocating exploration budget (rollout count) to tasks based on their difficulty and current learning status. Solves the knapsack problem of maximizing gradient signal within fixed compute budget, increasing non-zero policy gradients by 20-40% and achieving 2-4 point performance gains.

Knapsack RL: Adaptive Budget Allocation for Efficient Exploration

Standard RL training allocates uniform exploration budget: every task gets the same number of rollouts. But this is wasteful. Easy tasks consistently succeed (all rollouts produce zero gradients) while hard tasks consistently fail (all rollouts produce unhelpful noise). Neither generates useful learning signals.

Knapsack RL reframes this as an optimization problem: given a fixed compute budget, allocate rollout counts to tasks to maximize useful gradients. Easy tasks need fewer rollouts; hard tasks need more. This simple insight increases training efficiency significantly.

Core Concept

For each task, define a cost (number of rollouts) and value (expected policy gradient magnitude). Tasks fall into regimes:

• Easy regime: Consistently succeed regardless of policy. Zero gradient. Should reduce budget.
• Learning regime: Sometimes fail, sometimes succeed. High gradient. Should increase budget.
• Hard regime: Consistently fail. Near-zero gradient. Should reduce budget.

Knapsack RL identifies which regime each task is in, then solves:

Maximize: Σ (gradient_quality_i × rollout_count_i) Subject to: Σ (rollout_count_i) ≤ total_budget

This is a variant of the knapsack problem (hence the name), solvable with dynamic programming or greedy algorithms.

Architecture Overview

• Regime detector: Classifies tasks (easy/learning/hard) based on success rate
• Gradient estimator: Estimates expected gradient magnitude per task
• Value function: Combines regime + gradient to define task value
• Budget allocator: Solves knapsack problem to assign rollout counts
• Training loop: Standard GRPO with adaptive per-task budgets

Implementation Steps

First, implement task regime detection:

import numpy as np
from collections import defaultdict

class RegimeDetector:
    """
    Detect which learning regime each task is in.
    """
    def __init__(self, window_size=20):
        .window_size = window_size
        .task_history = defaultdict()  

     ():
        
        .task_history[task_id].append(success)

        
         (.task_history[task_id]) > .window_size:
            .task_history[task_id].pop()

     ():
        
         task_id   .task_history   .task_history[task_id]:
             ,   

        outcomes = .task_history[task_id]
        success_rate = (outcomes) / (outcomes)

         success_rate > :
            regime = 
         success_rate < :
            regime = 
        :
            regime = 

         regime, success_rate