Hierarchical Reinforcement Learning: Approximating Optimal Discounted TSP Using Local Policies
This work addresses hierarchical reinforcement learning for improving efficiency in deterministic environments, but it appears incremental as it builds on existing local policy methods.
The paper tackles the problem of reward decomposition in deterministic MDPs by mapping it to a Reward Discounted Traveling Salesman Problem and deriving approximate local solutions. It proposes three stochastic policies that guarantee better performance than any deterministic policy, though no concrete numbers are provided.
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.