Title: Hierarchical Reinforcement Learning: Approximating Optimal Discounted TSP Using Local Policies,
Abstract: In this work, we provide theoretical guarantees for reward decomposition in
deterministic MDPs. Reward decomposition is a special case of Hierarchical
Reinforcement Learning, that allows one to learn many policies in parallel and
combine them into a composite solution. Our approach builds on mapping this
problem into a Reward Discounted Traveling Salesman Problem, and then deriving
approximate solutions for it. In particular, we focus on approximate solutions
that are local, i.e., solutions that only observe information about the current
state. Local policies are easy to implement and do not require substantial
computational resources as they do not perform planning. While local
deterministic policies, like Nearest Neighbor, are being used in practice for
hierarchical reinforcement learning, we propose three stochastic policies that
guarantee better performance than any deterministic policy.