Abstract
We consider a settings of hierarchical reinforcement learning, in which thereward is a sum of components. For each component we are given a policy thatmaximizes it and our goal is to assemble a policy from the individual policiesthat maximizes the sum of the components. We provide theoretical guarantees forassembling such policies in deterministic MDPs with collectible rewards. Ourapproach builds on formulating this problem as a traveling salesman problemwith discounted reward. We focus on local solutions, i.e., policies that onlyuse information from the current state; thus, they are easy to implement and donot require substantial computational resources. We propose three localstochastic policies and prove that they guarantee better performance than anydeterministic local policy in the worst case; experimental results suggest thatthey also perform better on average.