KnapsackRL: Optimizing Exploration Budget Allocation in Large Language Model Reinforcement Learning Using the Knapsack Problem

This article introduces the KnapsackRL project, whose core is applying classic knapsack problem algorithms to exploration budget allocation in reinforcement learning (RL) to solve the exploration-exploitation dilemma in large language model (LLM) training. Due to the enormous search space in LLM training, efficiently exploring high-quality trajectories under limited resources is a key bottleneck. KnapsackRL models the problem using the knapsack approach to optimize resource allocation, improving training efficiency and model performance.

In RL training, agents need to balance exploring unknown strategies and exploiting known optimal strategies—this is the exploration-exploitation dilemma, which directly affects learning efficiency and performance. For LLMs, their search space is extremely large; how to efficiently explore high-quality trajectories within limited computing resources has become a key bottleneck for improving model capabilities.

KnapsackRL models RL exploration budget allocation as a 0/1 knapsack problem: each exploration attempt (trajectory generation) is an item that consumes computing budget (weight) and brings potential benefits (value), with the goal of maximizing total benefits under the given budget. Technical implementations include:

1. Dynamic programming solver (space compression, sparsity utilization, approximation algorithms);
2. Integration with policy gradient methods (e.g., PPO): first evaluate trajectory benefits, then select the optimal exploration set;
3. Adaptive budget adjustment: more exploration in the early training phase, reduced exploration in the later phase to focus on optimization.

Experimental results show:

• Benchmark environments (Atari, MuJoCo): 30% improvement in sample efficiency (fewer steps to achieve the same performance), 25% reduction in convergence time, and higher final rewards;
• LLM RLHF scenarios: 20-35% reduction in training GPU hours while maintaining model quality.

Practical significance of KnapsackRL:

1. Reduce training costs: minimize computational waste, lowering AI training costs for enterprises/research institutions;
2. Improve model reliability: more efficient exploration increases sample diversity, enhancing generalization and robustness;
3. Open-source contribution: provide reusable exploration budget management tools. This project demonstrates the value of combining classic algorithms with modern ML, opening a new path for improving LLM training efficiency.

Current limitations:

• Uncertainty in benefit estimation;
• Dependence on discretization assumptions (budget/benefits may be continuous in actual RL);
• Single-step optimization does not consider multi-step sequential decisions. Future directions:

1. Improve benefit estimation via online learning;
2. Multi-objective knapsack problem optimization;
3. Distributed expansion to support cluster resource coordination;
4. In-depth theoretical analysis (convergence, sample complexity).