贪心算法已足够：智能体LLM中的稀疏动作发现

现代智能体系统运行于具有极大动作空间的环境中，例如配备数千个API或检索操作的语言模型。尽管如此，实证研究表明，在特定部署中仅有少量动作对性能有显著影响。受此启发，本文研究了一个基于结构稀疏性假设的上下文线性奖励模型，即仅少数动作在潜在状态中具有非零效应。将动作发现建模为块稀疏恢复问题，并分析了一种受正交匹配追踪启发的贪心算法。在标准假设下，证明该方法能以高概率准确恢复相关动作集，样本数量随稀疏度和潜在维度多项式增长，而仅随总动作数对数增长。此外，提供了参数估计误差保证，并表明所得决策规则对新潜在状态近似最优。同时，建立了信息论下界，证明稀疏性和充分覆盖是可处理性的必要条件。这些结果将稀疏动作发现识别为大规模动作决策的基本原理，并为智能体系统的动作剪枝提供了理论基础。