用剪枝的子模图优化强化学习，让奖励最大化更高效。
Scalable Submodular Policy Optimization via Pruned Submodularity Graph
- 构建剪枝后的子模图，快速找到近似最优动作策略。
- 在基准测试中，新方法获得的奖励高于基线方法。
- 适合处理具有边际收益递减特性的复杂决策问题。
在强化学习中，智能体通过一系列可能的动作与环境交互，奖励来自未知分布。目标是找到一组最优动作，使特定时间步后的奖励最大化。传统强化学习假设奖励函数为可加性，但现实中许多问题（如路径规划、覆盖控制）的奖励函数呈现边际收益递减特性，可用子模函数建模。本文研究奖励函数为子模的强化学习问题，目标是找到使该函数最大化的最优策略。提出一种基于剪枝子模图的方法，可在合理计算时间内提供有保证的近似解。分析了该方法的时间、空间复杂度及性能保障。在基准智能体-环境设置上进行了实验，结果表明，所提方法获得的奖励显著优于基线方法。
原文摘要 · Abstract (English)
In Reinforcement Learning (abbreviated as RL), an agent interacts with the environment via a set of possible actions, and a reward is generated from some unknown distribution. The task here is to find an optimal set of actions such that the reward after a certain time step gets maximized. In a traditional setup, the reward function in an RL Problem is considered additive. However, in reality, there exist many problems, including path planning, coverage control, etc., the reward function follows the diminishing return, which can be modeled as a submodular function. In this paper, we study a variant of the RL Problem where the reward function is submodular, and our objective is to find an optimal policy such that this reward function gets maximized. We have proposed a pruned submodularity graph-based approach that provides a provably approximate solution in a feasible computation time. The proposed approach has been analyzed to understand its time and space requirements as well as a performance guarantee. We have experimented with a benchmark agent-environment setup, which has been used for similar previous studies, and the results are reported. From the results, we observe that the policy obtained by our proposed approach leads to more reward than the baseline methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。