Abstraction of Markov Decision Processes is a useful tool for solving complex problems, as it can ignore unimportant aspects of an environment, simplifying the process of learning an optimal policy. In this paper, we propose a new algorithm for finding abstract MDPs in environments with continuous state spaces. It is based on MDP homomorphisms, a structure-preserving mapping between MDPs. We demonstrate our algorithm's ability to learns abstractions from collected experience and show how to reuse the abstractions to guide exploration in new tasks the agent encounters. Our novel task transfer method beats a baseline based on a deep Q-network. Abstraction is a useful tool for effective control in complex environments. Instead of learning an entangled and uninterpretable policy with a deep neural network, as is the current practice in the deep reinforcement learning literature, we can abstract away unimportant details, which allows us to learn a much simpler policy. Such a policy can be examined by hand in its full form.There are two approaches to abstraction: temporal abstraction and abstraction of the state space. The former is best suited for tasks that take hundreds or thousands of time steps to solve, as it creates temporally-extended actions that mitigate the difficulties of making decisions over long time periods. The latter groups together states that exhibit similar behaviors, which decreases the size of the state spaces and allows for simpler policies. The abstracted state space is the smallest when the actions are temporally extended, hence, temporal abstraction complements state abstraction. We focus on state abstraction in this paper.To find useful abstraction, we adopt a theoretical framework called Markov Decision Process (MDP) homomorphism BID5 ): a mapping between two MDPs that preserves their structure. Our goal is to find the smallest MDP homomorphic to the underlying problem. This can also be viewed as model minimization with MDP homomorphism serving the role of an equivalence relation between models-MDPs. We call the minimized MDP an abstract MDP because it abstracts away many unnecessary distinctions between states from the underlying MDP. Instead of proposing an ad-hoc algorithm, our approach leverages the theoretical foundations of BID5 .We focus on solving end-to-end manipulation tasks from robotics characterized by continuous high-dimensional state spaces (i.e. the input from an RGB or a depth camera) and discrete highdimensional action spaces: all possible positions where the robot can execute an action. Such environments are best handled with convolutional neural networks, which can learn from highdimensional inputs without overfitting due to extensive weight sharing and various other desirable properties. However , our algorithm does not depend on a particular model-we replace the convolutional network with a decision tree in one experiment.In this paper, we propose a new approach to learning abstract MDPs from experience. These are our key contributions:• We propose an algorithm for creating abstract MDPs from experience in both discrete and continuous state spaces (Subsection 5.1). The algorithm first explores the environment with either a random uniform policy or a deep Q-network BID3 ). Subsequently, it generates an abstract MDP homomorphic to the underlying MDP and plans the optimal actions in the abstract MDP. It is limited to deterministic MDPs in its current version.• We develop a classifier based on a convolutional network that learns to sort state-action pairs based on their behavior. We include several augmentations, such as sharing the weights of previously learned models and oversampling minority classes, for speeding-up learning and dealing with extreme class imbalance (Subsection 5.2).• We propose a method for guiding exploration in a new task with a previously learned abstract MDP (Subsection 5.5). Our method is based on the framework of options BID10 ); it can augment any existing reinforcement learning agent with a new set of temporally-extended actions. The method beats a baseline based on a deep Q-network in one class of tasks and performs equally well in another.2 RELATED WORK BID5 proposed Markov Decision Process (MDP) homomorphism together with a sketch of an algorithm for finding homomorphisms (i.e. finding the minimal MDP homomorphic to the underlying MDP) given the full specification of the MDP. The first and only algorithm (to the best of our knowledge) for finding homomorphisms from experience BID13 ) operates over Controlled Markov Processes (CMP), an MDP extended with an output function that provides more supervision than the reward function alone. Homomorphism over CMPs was also used in BID12 to find objects that react the same to a defined set of actions.An approximate MDP homomorphism BID6 ) allows aggregating together state-action pairs with similar, but not the same dynamics. It is essential when learning homomorphisms from experience in non-deterministic environments because the estimated transition probabilities for individual state-action pairs will rarely be the same, which is required by the MDP homomorphism. BID11 built upon this framework by introducing a similarity metric for state-action pairs as well as an algorithm for finding approximate homomorphisms.Sorg & Singh (2009) developed a method based on homomorphism for transferring a predefined optimal policy to a similar task. However, their method maps only states and not actions, requiring actions to behave the same across all MDPs. BID7 and BID4 also studied skill transfer in the framework of MDP homomorphisms.3 BACKGROUND An agent's interaction with an environment can be modeled as a Markov Decision Process (MDP, Bellman (1957) ). An MDP is a tuple S, A, Φ, P, R , where S is the set of states, A is the set of actions, Φ ⊂ S×A is the state-action space (the set of available actions for each state), P (s, a, s ) is the transition function and R(s, a) is the reward function.We aim to find minimal MDPs that retain the structure of the underlying MDP. An MDP homomorphism captures this intuition: Definition 1 BID5 ). An MDP homomorphism from M = S, A, Φ, P, R to M = S , A , Φ , P , R is a tuple of surjections f, {g s : s ∈ S} with h(s, a) = (f (s), g s (a)), where f : S → S and g s : DISPLAYFORM0 Computing the optimal state-action value function in the minimized MDP requires fewer computations, but does it help us act in the underlying MDP? The following theorem states that the optimal state-action value function lifted from the minimized MDP is still optimal in the underlying MDP: Theorem 1 (Optimal value equivalence, BID5 ). Let M = S , A , Φ , P , R be the homomorphic image of the MDP M = S, A, Φ, P, R under the MDP homomorphism h(s, a) DISPLAYFORM1 During MDP minimization, Φ is partitioned and the partition subsequently induces the abstract MDP. Let B = {b 1 , b 2 , ..., b N } be the partition over Φ. We call B the state-action partition, with b i being a block of state-action pairs. The state-action partition induces the quotient MDP:Definition 2. Given a reward respecting SSP partition B of an MDP M = S, A, Φ, P, R , the quotient MDP M/B is the MDP S , A , Φ , P , R , where DISPLAYFORM2 We omit the definition of the reward respecting SSP partition for brevity, please find it in BID5 . We call the induced quotient MDP an abstract MDP-it ignores many unimportant distinctions from the underlying MDP.Finally, we adopt the framework of options BID10 ) for the purpose of transferring learned homomorphisms between similar tasks. An option I, π, β is a temporally extended action; it can be executed from the set of states I, the individual primitive actions are selected with a policy π and each state it encounters has a probability of terminating the option, which is given by β : DISPLAYFORM3 We developed an algorithm for finding abstract MDPs in environments with continuous state spaces and demonstrated the algorithm works with medium-sized abstract MDPs. Furthermore, we devised a method for guiding exploration with an abstract MDP learned in a previous task based on the options framework. Our transfer method beats a deep Q-network baseline when the goal of the previous task is not on the path to the goal of the next task and it performs equally well otherwise.In robotic manipulation tasks, most MDPs are deterministic with the exception of a small number of failure modes (e.g. the robot grasps an object by its edge and it subsequently falls out of its hand); in our future work, we aim to bound the loss in the performance of our algorithm when dealing with a certain degree of non-determinism in the MDP. Moreover, our algorithm creates a brand new partition every time it is run to avoid over-segmentation-if there are too many state-action blocks there is no way of merging them. We will address this limitation by introducing an operation that can merge two state-action blocks upon receiving more experience.
We create abstract models of environments from experience and use them to learn new tasks faster. A methodology that uses the idea of MDP homomorphisms to transform a complex MDP with a continuous state space to a simpler one.