arXiv:2601.20694cs.LG2026-01中稿 · ICLR

在外部随机决策问题中,仅靠贪婪策略就能达到最优,无需主动探索。

Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?

  • 提出纯利用学习(PEL)方法,不依赖探索直接优化策略。
  • 首次证明无探索算法在有限样本下有可保证的误差,线性近似下误差多项式增长。
  • 适合资源管理、库存控制等外部随机场景,尤其适用于高维连续状态空间。

外部马尔可夫决策过程(Exo-MDPs)描述了不确定性仅来自独立于智能体行为的外部输入的序列决策问题,常见于库存控制、能源存储和资源分配等运筹学场景。尽管几十年来经验表明贪心策略在这些场景中表现优异,但现有理论仍依赖显式探索或表格假设。本文证明探索并非必需:提出纯利用学习(PEL),并首次为无探索算法建立了通用的有限样本后悔界。在表格情形下,PEL 的后悔界为 $\widetilde{O}(H^2|Ξ|\sqrt{K})$;对于大且连续的内生状态空间,引入基于线性近似的 LSVI-PE,其后悔界关于特征维度、外部状态空间和时域呈多项式增长,与内生状态和动作空间无关。分析中提出反事实轨迹与贝尔曼闭合特征传输两个新工具,使贪婪策略无需乐观性即可获得准确价值估计。合成数据与资源管理任务实验显示,PEL 始终优于基线。总体而言,结果推翻了‘探索必要’的普遍认知,证明在 Exo-MDP 中,纯利用已足够。

原文摘要 · Abstract (English)

Exogenous MDPs (Exo-MDPs) capture sequential decision-making where uncertainty comes solely from exogenous inputs that evolve independently of the learner's actions. This structure is especially common in operations research applications such as inventory control, energy storage, and resource allocation, where exogenous randomness (e.g., demand, arrivals, or prices) drives system behavior. Despite decades of empirical evidence that greedy, exploitation-only methods work remarkably well in these settings, theory has lagged behind: all existing regret guarantees for Exo-MDPs rely on explicit exploration or tabular assumptions. We show that exploration is unnecessary. We propose Pure Exploitation Learning (PEL) and prove the first general finite-sample regret bounds for exploitation-only algorithms in Exo-MDPs. In the tabular case, PEL achieves $\widetilde{O}(H^2|Ξ|\sqrt{K})$. For large, continuous endogenous state spaces, we introduce LSVI-PE, a simple linear-approximation method whose regret is polynomial in the feature dimension, exogenous state space, and horizon, independent of the endogenous state and action spaces. Our analysis introduces two new tools: counterfactual trajectories and Bellman-closed feature transport, which together allow greedy policies to have accurate value estimates without optimism. Experiments on synthetic and resource-management tasks show that PEL consistently outperforming baselines. Overall, our results overturn the conventional wisdom that exploration is required, demonstrating that in Exo-MDPs, pure exploitation is enough.

强化学习决策优化线性近似无探索

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。