贪心就够了：Agentic LLM中的稀疏动作发现

现代agentic系统在极大动作空间的环境中运行，例如拥有数千个可用API或检索操作的工具增强语言模型。尽管规模如此之大，实证证据表明只有一小部分动作会实质性地影响给定部署中的性能。受此观察启发，我们研究一个上下文线性奖励模型，其中动作相关性由结构化稀疏性假设支配：只有少数动作在潜在状态上具有非零效应。我们将动作发现形式化为块稀疏恢复问题，并分析一个受Orthogonal Matching Pursuit启发的贪心算法。在非相干性、信号强度与动作覆盖的标准假设下，我们证明贪心过程能以高概率精确恢复相关动作集，所需样本量关于稀疏度与潜在维度按多项式缩放，而关于动作总数仅按对数缩放。我们进一步为重拟合参数提供估计误差保证，并表明所得决策规则对新潜在状态接近最优。作为补充，我们建立信息论下界，证明稀疏性与充分覆盖是可解性的必要条件。总之，我们的结果把稀疏动作发现确立为大动作决策的基本原则，并为agentic系统中的动作剪枝提供理论基础。