Research On State Abstraction For Reinforcement Learning

Abstraction method is an important technique for solving the problem of curse of dimensionality because it enables us eliminate irrelevant features to our current decision which is based only on relevant or important features. In reinforcement learning field, there are two main methods: procedural abstraction and state abstraction. Procedural abstraction occurs when the details of a complex action are ignored and the entire complex action is treated as a unit. State abstraction is the process of eliminating features to reduce the effective state space. Although state abstraction has been developed largely, there are a lot of problems in this field.In order to solve the problem of discretization for continuous state space, we construct a SOM-based state abstraction method that organically consists of SOM, ET(Eligibility Trace) and the Actor/Critic frame. The method's characteristics are as follows: good discretization quality for continuous state space acquired by combining SOM with on-line experiences acquired by agent; on-line automatic discretization acquired by unsupervised SOM method; improving learning performance acquired by combining SOM with ET.In order to solve the problem of weak task-oriented representation for HRL (hierarchical reinforcement learning), we classify SMDPs task, define the HAM- decomposable concept, clearly explain the relations among HAM, HAM-decomposable and policy-coupled SMDPs task. In addition, we prove that HAM method is suitable for solving policy-coupled SMDPs. In fact, there is another view of HAM, i.e. policy-coupled based HAM. Based on the new view, we propose a hierarchical decomposition method for policy-coupled SMDPs task with DAG. The method makes use of both CALL and CHOICE machine state in HAM. Compared to other methods, it need less information and the resulting hierarchy has simple sub-tasks and limiting the set of actions. In addition, the independence between layers in hierarchy enables state abstraction which can speed up learning.Based on policy-coupled based HAM, we propose a homomorphism method that can solve the problem in subtask-based state abstraction and of joint state space in HAM , by theoretically analysis and empirically test. For empirical use, we conclude some important views for homomorphism and discuss some problems such as approximating homomorphism and partial homomorphism.Based on the main concepts and theories above, we propose a unifying frame for HAM-based HRL from the view of task-oriented solution as a basic requirement. Basiclly, it supports the modeling and computation for tasks, enable the simultaneous use of some state abstraction methods, and simultaneously learn both hierarchical optimal policy and recursive optimal policy. We also propose a designing method for NPCs'behavior and test the movement behavior for NPCs on Quake2—a real game platform. This shows that our methods above can be used for real problems.