  Reinforcement Learning (RL) algorithms often suffer from low training
efficiency. A strategy to mitigate this issue is to incorporate a model-based
planning algorithm, such as Monte Carlo Tree Search (MCTS) or Value Iteration
(VI), into the environmental model. The major limitation of VI is the need to
iterate over a large tensor. These still lead to intensive computations. We
focus on improving the training efficiency of RL algorithms by improving the
efficiency of the value learning process. For the deterministic environments
with discrete state and action spaces, a non-branching sequence of transitions
moves the agent without deviating from intermediate states, which we call a
highway. On such non-branching highways, the value-updating process can be
merged as a one-step process instead of iterating the value step-by-step. Based
on this observation, we propose a novel graph structure, named highway graph,
to model the state transition. Our highway graph compresses the transition
model into a concise graph, where edges can represent multiple state
transitions to support value propagation across multiple time steps in each
iteration. We thus can obtain a more efficient value learning approach by
facilitating the VI algorithm on highway graphs. By integrating the highway
graph into RL (as a model-based off-policy RL method), the RL training can be
remarkably accelerated in the early stages (within 1 million frames).
Comparison against various baselines on four categories of environments reveals
that our method outperforms both representative and novel model-free and
model-based RL algorithms, demonstrating 10 to more than 150 times more
efficiency while maintaining an equal or superior expected return, as confirmed
by carefully conducted analyses. Moreover, a deep neural network-based agent is
trained using the highway graph, resulting in better generalization and lower
storage costs.
