An Observation Dimension Weight-Based U-Tree Algorithm
Instance-based methods are a class of effective algorithms for solving reinforcement learning problems. U-Tree algorithm presents the state space from instance chains effectively, which is very beneficial to solve the reasonable Q-value of actions. However, the complexity of the construction of suffix tree in U-Tree algorithm is exponential. A new observation dimension weight-based algorithm ODWU-Tree for optimizing the expansion of fringe of suffix tree is presented in the paper. ODWUTree algorithm obtains the heuristic information of environments by simple heuristic exploration, evaluates the weight coefficient of observation dimensions, and expands the fringes by the most important observation dimensions for reasonable leaf state. Experiment results of New York Driving show that both the efficiency and the effect have been improved by ODWU-Tree algorithm compared to U-Tree algorithm.