SKILL DISCOVERY WITH WELL-DEFINED OBJECTIVES
SKILL DISCOVERY WITH WELL-DEFINED OBJECTIVES
复制标题
具有明确目标的技能发现
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
G. Konidaris
中科院分区：
文献类型：
--
作者：
Yuu Jinnai;David Abel;Jee Won Park;M. Littman;G. Konidaris
虽然已经提出了许多技能发现方法来加速学习和规划，但大多数都是基于启发式方法，而与技能如何影响代理的目标没有明确的联系。因此，算法有效的条件往往是不清楚的。我们声称，我们应该追求与智能体目标有明确关系的技能发现算法，以理解在什么情况下技能发现方法是有用的。我们分析了两种情况，计划和强化学习，并表明我们能够给出期权发现算法的性能界限。对于规划，我们证明了寻找一组最小化规划时间的选项的问题是np困难的，并给出了在一定条件下近似最优的多项式时间算法。对于强化学习，我们以具有稀疏奖励的基于目标的任务为目标，其中智能体必须在状态空间中导航以达到目标状态，除了目标状态之外没有任何奖励信号。我们表明，在MDP中发现一个遥远的奖励状态的难度是由MDP的过渡动态引起的随机漫步的期望覆盖时间所限制的。因此，我们提出了一种算法，该算法找到一个可证明地减少期望覆盖时间的选项。
While many skill discovery methods have been proposed to accelerate learning and planning, most are based on heuristic methods without clear connections to how the skills impact the agent’s objective. As such, the conditions under which the algorithms are effective is often unclear. We claim that we should pursue skill discovery algorithms with explicit relationships to the objective of the agent to understand in what scenarios skill discovery methods are useful. We analyze two scenarios, planning and reinforcement learning and show that we are able to give bounds to the performance of the option discovery algorithms. For planning, we show that the problem of finding a set of options which minimizes the planning time is NP-hard, and give a polynomial-time algorithm that is approximately optimal under certain conditions. For reinforcement learning, we target goal-based tasks with sparse reward where the agent has to navigate through the state-space to reach the goal state without any reward signals other than the goal state. We show that the difficulty of discovering a distant rewarding state in an MDP is bounded by the expected cover time of a random walk over the graph induced by the MDP’s transition dynamics. We therefore propose an algorithm which finds an option which provably diminishes the expected cover time.
使用技能符号循环构建抽象层次结构。
DOI：
--
发表时间：
2016
期刊：
IJCAI : proceedings of the conference
影响因子：
--
作者：
Konidaris,George
通讯作者：
Konidaris,George