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.

为了提高 RL 算法的训练效率，本研究基于高速公路图的观察，提出了一种新颖的图结构，用于模拟状态转换，将 RL 训练在早期阶段显著加速，并在性能上优于其他无模型和带模型的 RL 算法。同时，基于高速公路图训练的深度神经网络代理具有更好的泛化性能和更低的存储成本。