Highway Graph to Accelerate Reinforcement Learning
Authors: Zidu Yin
Zhen Zhang
Dong Gong
Stefano V Albrecht
Javen Qinfeng Shi
Venue: Accepted by TMLR ()

Abstract: Reinforcement Learning (RL) algorithms often struggle with low training efficiency. A common approach to address this challenge is integrating model-based planning algorithms, such as Monte Carlo Tree Search (MCTS) or Value Iteration (VI), into the environmental model. However, VI faces a significant limitation: it requires iterating over a large tensor with dimensions $|\mathcal{S}|\times |\mathcal{A}| \times |\mathcal{S}|$, where $\mathcal{S}$ and $\mathcal{A}$ represent the state and action spaces, respectively. This process updates the value of the preceding state $s_{t-1}$ based on the succeeding state $s_t$ through value propagation, resulting in computationally intensive operations. To enhance the training efficiency of RL algorithms, we propose improving the efficiency of the value learning process. In deterministic environments with discrete state and action spaces, we observe that on the sampled empirical state-transition graph, a non-branching sequence of transitions—termed a \textit{highway}—can take the agent directly from $s_0$ to $s_T$ without deviation through intermediate states. On these non-branching highways, the value-updating process can be streamlined into a single-step operation, eliminating the need for iterative, step-by-step updates. Building on this observation, we introduce a novel graph structure called the \textit{highway graph} to model state transitions. The highway graph compresses the transition model into a compact representation, where edges can encapsulate multiple state transitions, enabling value propagation across multiple time steps in a single iteration. By integrating the highway graph into RL (as a model-based off-policy RL method), the training process is significantly accelerated, particularly in the early stages of training. Experiments across four categories of environments demonstrate that our method learns significantly faster than established and state-of-the-art model-free and model-based RL algorithms (often by a factor of 10 to 150) while maintaining equal or superior expected returns. Furthermore, a deep neural network-based agent trained using the highway graph exhibits improved generalization capabilities and reduced storage costs.

Published in Transactions on Machine Learning Research (12/2024)
Highway Graph to Accelerate Reinforcement Learning
Zidu Yin
zidu beak.giin@yeemu.du.coo
School of Information Science and Technology Yunnan Normal University
Zhen Zhang
zhen@zshang.ov org
School of Computer and Mathematicol Sciences Adelaide University
Dong Gong
edgong01 @gmail com
School of Computer Science and Engineering The Universily of New South Wales
Stefano V. Albrecht
s.albrecht@ed..cm ac. uk
School of Informatics University of Edinburgh
Javen Q. Shi
juven.shi@udelliie edu
School of Computer and Mathematical Sciences Adelaide University
Reviewed on OpenReview: https: // openreviee.. net/ forum? id- 3mJ22
Abstract
Reinforcement Learning (RL) algorithms often struggle with low training efficiency. A com- mon approach to address this challenge is integrating model-based planning algorithms, such as Monte Carlo Tree Search (MCTS) or Value Iteration (VI), into the envirommental model. However, VT faces a significant limitation: il requires iterating over a large tensor with di- mensions |S] x |A] x [S], where S and represent the state and action spaces, respectively. This process updates the value of the precoding state $t-1 basod on the succeoding state st through value propagation, resulting in computationally intensive operations. To enhance the training efficiency of RL algorithms,
propose improving the efficiency of the value learning process. In deterministic environments with discrete state and action spaces, observe that on the sampled empirical state- tratttrraantiinn graph, non- non-branching sequence of transitions-tente a highway can take the agent directly from 8p to 8T without deviation through intermediate states. On these non- non-branching highways, the value-updating process can be streamlined into single-step operation, eliminating the need for ilerative, step-by- step updates. Building on this observation, we introduce a novel graph structure called the highway graph to model state transitions. The highway graph compresses the transition model into compact representation, where edges encapsulate multiple state transitions, enabling value propagation across multiple time steps in single iteration. By integrating the highway graph into RL (as a model- based off-policy RL method), the training process significantly accolcrated, particularly in the early stages of training. Experiments across four calegories of enviromments demonstrate that our method learns significantly faster than established and state-of-the-ee model-free and model-based RL algorithms (often by fac- tor of 10 to 150) while maintaining equal superior expected returns. Furthermore, deep neural beework-based agent trained using the highway graph exhibits improved generaliza- tion capabilities and reduced storage costs. The implementation of our highway graph RT. hod is publicly available at http:://gituub.om/// coodest highwayRL.

---

Published in Transactions on Machine Learning Research (12/2024)
o State - Action Highway
Value updating per iteration
(I)
Figure 1: Comparison of the state-transition graph and its corresponding highway graph. An RL agent on the state-transition graph carns/propagater values state-by-state per learning step, and the highway graph propagates values for a stack of states in the highway per learning step. The highway graph is much smaller than the state-transie teateerranstiion graph which leads to more efficient value learning. Take the Atari game Star Gunner as an example, the 234,521 states in the sampled empirical state-transition graph are represented by highway graph with only 1,084 (0.5% of its original size) states connected by highways.
1 Introduction
Reinforcement learning (RL) agent training is often time-intensive, primarily due to the low efficiency of the value-updating process. From the perspective of RL agents, the environment they interact with can be represented as a state-transition graph, which models transitions between possible states within a Markov Decision Process (MDP). In this context, the value-updating process (illustrated in Figure (1)) involves iteratively propagating value information across known states a sampled state-transition graph (empir- ical state-transition graph) until training concludes. However, for environments with large state-transition graphs, this process becomes computationally expensive. The value of each state must be propagated back state by state from all potential future states, leading to significant delays in convergence.
A common approach to address this issue is incorporate model-based planning algorithms, such as Monte Carlo Tree Search (MCTS) (Schrittwieser al., 2020) and Value Iteration (VI) (Tamar et al., 2016), estimate and propagate future state values. However, MCTS can be slow for action selection as it requires extensive sampling at decision time (Swiechowski et al., 2023). This limitation has led us to focus the potential of the classical VI algorithm for improving training efficiency.
The primary drawback VI lies in its requirement to itcrate over a large tensor with dimensions |S| [||||xx (S), where S and A denote the state and action spaces, respectively. During each iteration, the value of state 8; is only propagated back incrementally to update the preceding state 8t-1, limiting efficiency.
In this paper, present enhancement to the VI algorithm by introducing novel graph structure to accelerate the value-updating process in RL. Our approach draws inspiration from real-world highway systems, where drivers traverse significant, frequently visited destinations without the need for constant mecision-making at intersections, enabling high-speed travel along unbranched paths. Similarly, we identify paths without branching within the empirical stato-transition graph, which we term highways. Along these highways, value updates for states can be aggregated and performed as single operation, as opposed to incrementally updating values state by state. By enabling efficient propagation of values over long ranges from potential future states simultaneously, our method significantly enhances overall training elficiency. This notion of multi-step efficiency has also shown promise in the context of representation learning in RL (McInroe et al., 2024).
We introduce the concept of a highway graph for modeling the environment, shown in Figure 1. In this work, we focus on deterministic environments with discrete state and action spaces. The highway graph is constructed from the empirical stato-transitions graph (Figure (1)). In the highway graph, nodes are intersection states, and edges are highways. A highway is formed using the sequence of transitions in a non- branching path that only bridges two states without adjacent (Figure (2)). Decisions are only necessary
2

---

Published in Transactions on Machine Learning Research (12/2024)
202
Simple maze (5 5) Google research football
Toy text
Atari games
Baselines
Converged
14.86 + 2.90 (A3C)
79.81 0.42 (IMPALA)
41.67 + 0.18 (DQN)
251.26 17.64 (MFEC)
time (min)..
Eval. return
0.76 0.03
1.01 + 0.09
88.18 = 0.73
764.46 + 239.06
Converged
0.15 + 0.02 (99.0 speedup)
7.33 + 0.10 (10.9 speedup)
3,82 + 0.23 (10.9 speedup)
1,51 + 0.10 speedup)
Highway graph.
time (min)
Eval. return
0.83 0.00
1.03 0.02
5.99 + 0.74
2201.62 + 918.52
Figure 2: A comparison of converged time of training (within one million frames) and corresponding speedups by the highway graph compared to baselines. The first row of images are example states from each environ- ment. The results demonstrate 10 to more than 150 times faster RL agent training compared to baselines when adopting the highway graph. All the experiments were performed on the same machine with a 12-core CPU and 128 GB Memory.
intersection states, such when driver must choose direction at an intersection, and continue along the highway otherwisc. It worth noting that the concept of the highway graph is not equivalent to the concept of state abstraction (Chen et al., 2024). When the environment deviates from what is recorded in the highway graph, the agent can fall off the highway, gaining new experiences and incrementally expanding the highway. Thus, our approach does not reduce the problem's 's size or complexity.
Due to the highways, the original empirical state-transition graph shrinks into a very small highway graph, with two advantages for value learning. First, the values of any state connected by the highways updated with a single operation, achieving a very high training efficiency. Second, experience sampling for the value updating is required, and the VI algorithm can be conducted on the entire graph to avoid sub-optimal value learning caused by the sampling. We theoretically demonstrate the convergence to the optimal state value function of the VI algorithm on a highway graph.
As mosel-based RL method, the highway graph still needs to be stored in memory. There is a possibility that the highway graph will be too large to fit in memory. To address this issue, we further replace the highway graph with neural network-based agent obtained by re-paramcterizing the value information of the highway graph.
We evaluate our proposed methods against a range of established and Seate-of-the-ar RL approaches (Schrit- twieser et al., 2020; Antonoglou et al., 2022; Danihelka et al., 2022; Lin et al., 2018; Hu et al., 2021; Blundell Pritzel et al., 2017a; Mnih al., 2015; Kaplurowski et al., 2019; Schulman et al., 2017; Espeholt et al., 2018; Mnih et al., 2016) across four distinct categories of tasks. Figure 2 illustrates the speedups achieved by highway graph approach compared to popular baselines across four different environments. Our highway graph consistently delivers on-par or superior expected returns, with speedups ranging from approximately 10-fold to over 150-fold compared to baselines, providing compelling evidence of the feasibility and effectiveness of converting to a highway graph structure. Notably, many tasks in the evaluated environ- ments can be solved within just one million frames, a milestone that most baseline methods fail to achieve. Furthermore, the re-parameterized neural network, employed as the agent. trained by the highway graph, delivers an additional 5% to 20% improvement in expected returns, attributed to its enhanced gencralization capabilities.
et al., 2016;
In summary, our paper makes the following key contributions:
We propose a novel graph structure, the highway graph, which facilitates more efficient value learning by enabling long-range value propagation within each learning iteration.
3

---

Published in Transactions on Machine Learning Research (12/2024)
State
Action
Value updating
planning
sampled transition
T2
T2
T2
71
Q-Icarning
(2) Policy gradient
MCTS
(4) Highway graph
Figure 3: Types of value updating.
We improve the training efficiency of the classic VI algorithm by leveraging the highway graph. Additionally, we provide a theoretical proof of convergence to the optimal state value function for the improved VI algorithm.
We re-parameterize the highway graph into a neural network, resulting in a policy with superior generalization capabilities and reduced storage costs.
We evaluate our framework on four categories of learning tasks, benchmarking it against state-of-the- art RL baselines. Our approach significantly reduces training time and increases sample efficiency, achieving speedups ranging from approximately 10-fold to over 150-fold compared to baselines. Furthermore, it solves tasks within one million frames while maintaining equal or superior expected returns.
2 Related work
In this section, we discuss how model-based and model-free RL methods learn state values, highlighting the differences between these approaches and our proposed highway graph method.
Model-based RL agents generally leverage the environment model-reee repeeeeneed as a state-transition throuhh two primary approaches: value search and graph-based value iteration. Both approaches rely on the model to facilitate value learning, which aims to propagate values from terminal states back to the starting states within the state-transition graph.
Value search methods use tree search algorithms (Schrittwicser et al., 2020; Kaiser et al., 2020; Danihelka et al., 2022), such as MCTS, for both agent training and action selection through simulation. This process is often time-consuming. In value search, state values for action selection-ree referred to as planning are typically determined within a specific range of the state-transition graph. The values of the leaf states in the search tree usually provided by the state value function. The planning replies sampling strategics to imate the value of the current state, which can decrease the efficiency of the training, illustrated in Figure 3 (3).
Value iteration methods obtain the state values by retrieving from a previously maintained memory of the state-transition model (Tamar al., 2016). Also, episodic control algorithms (Blundell al., 2016; Zhu et al., 2020; Pritzel et al., 2017a; Hu et al., 2021; Zhu et al., 2020) are in this category. The episodic control algorithms maintain memory make decisions that explicitly store the transition information as memory. During value updating, the maximum value of either all the future states (Blundell et al., 2016) states of related trajectorics (Zhu et al., 2020) will be used to update the current state's value (Zhu et al., 2020). Such memory can also be parameterized to improve the generalization and performance (Lin et al., 2018; Pritzel et al., 2017b) which gives insight into the parameterized agent trained by memorized data.
Model-free RL algorithms do not explicitly Iearn the environment model but instcad use sampled transitions from the replay recognize the dynamics of the environment when learning the state value. The value-based and based approaches are typical mrdel-free RL algorithms.
4

---

Published in Transactions on Machine Learning Research (12/2024)
Q-learning methods are typical value-based methods, like DQN (Mnih et al, 2015), which propagate the value of the next. few states in the randomly sampled transitions to the current one in each update using n-step temporal difference error, see Figure 3 (1). However, not all valuable transitions are sampled for value updates. To solve this, a prioritized replay buffer was proposed to sample more useful transitions when training the agent (Schaul et al., 2016). Highway value ileration networks (Wang et al., 2024) optimize the n-step value updating process via a modified multi-step Bellman operator to avoid the value underestima- tion issue and make the value updating converge to the optimal value function. R2D2 improved DQN by using recurrent encoder to obtain better state representations considering all past states in the episode (Kapturowski et al., 2019). The recurrent model considers the causal effect of the historical transition which gives us an insight into designing the encoder for the state.
Policy gradient methods update the value of states directly from the gradient of future value estimation from the sampled trajectories (Schulman et al., 2017; Che et al., 2023; Fatkhullin et al., 2023; Mnih et al., 2016), see Figure 3 (2). The training efficiency can be improved by using distributed systems (Mnih et al., 2016; Espeholt et al., 2018).
During the value update of the model-free agents, inconsistent value updates may occur. The value updating of these methods heavily depends on the sampled transitions or trajectories, and if transitions from s, with the highest, value are not sampled, the updated value of 82 will bias to the real value. Often more sampling is required to overcome this bias, which leads to low training efficiency. In addition, it also makes model-free RL training inefficient since the value of terminal states is propagated to the starting states state-by-state.
Consequently, there are major differences between the highway graph and the above methods, see Figure 3 (4). First, the highway graph itself acts a memory to store the transiting information, and during value updating, the value will be propagated throughout the entire graph, leading to complete value propagation on each learning iteration. Second, the value updating operation on the highway graph is only for the states of intersection (much fewer than the original states) and highways, instead of all states and transitions, to reduce unnecessary computation and therefore increase training efficiency.
Many approaches also attempt to reduce the costs of value learning by task division. Hierarchical rein- forcement learning methods learn the sub-goals of the environment hicrarchically to reduce the problem- solving complexity (Nachum et al., 2018). Similarly, state abstraction methods, such as macro-action meth- ods (van den Berg et al., 2012), use fixed action sequences to interact with environments for a smaller problem size. These methods are different from our method, since our highway RL agent directly interacts with the environment at every step without state abstraction or policy hicrarchies, and is capable of exiting the highway at any time, thereby gaining new experiences and incrementally expanding the highway graph.
Improving the sample efficiency of value learning is important to speed up agent training. Offline data can be used to improve the sample efficiency of agent training by pre-training policy before online RL training (Andres et al., 2025). Auxiliary learning targets can also help the agent to learn more effective representations (He et al., 2022; Liu et al., 2021) and enhance generalization to unseen environments (Dunion et al., 2023b;a; Yu et al., 2024). These methods share the same goal of our method but with different approaches.
3 Methodology
In this section, we will introduce novel graph structure to model the MDP of the environment, named highway graph. The highway graph is built upon the empirical state-transition graph to accelerate value updating, as well as action selection for the environment, see Figure 4 for the overall data flow of our highway graph RL method.
3.1 Markov decision process and empirical
graph
Generally, RL agents try to maximize the expected return when interacting with the environment (Kaelbling et al., 1996). The environment can be described as Markov docision process (MDP) (Sutton Barto, 2018) by a 5-tuple (S,A, T, 7), where S and A denote the spaces for state and action, T(s', aa,ss p(s'(a,s) is the probability of transition into state s' given current state and action a, R(s, a) is the immediate reward
5

---

Published in Transactions on Machine Learning Research (12/2024)
XCHL
Action
Rehavior
Policy
Value updlating
Neural netwark-
Environment
Agent (Actor)
agcut
O
r-1
(3) Target Policy
(2) Highway Graph
(1) Empirical State-transition
Riifa Trajectory
Gruph
Observation (ok:
Agent (Learner)
Reward
State
-
Action
- -lighway
..... Value updating
Figure 4: Overall data flow of our highway graph RL method. The actor (on the left) sends the sampled transitions by the behavior policy to the learner (on the right) which (1) constructs the empirical state- transition graph with rewards (in Section 3.1); (2) converts the empirical state-transition graph to the corresponding highway graph (Section 3.2); (3) updates the value of state-actions in the highway graph by an improved value itcration algorithm and ro-parameterize the highway graph to neural network- basod agent the behavior policy (Section 3.3).
of action in current state and 0 & < 1 is the discount factor. With known transition and reward function, the state value function of the policy at learning step a can be obtained by value update as follows,
viu) max a
a( + T(s T ())))))))
(1)
where (s) can be initialized as O. For deterministic environments, T(s', is constant and Ex T(8', a, ())()))()))) will be a, s) ((u-
Empirical transition and reward functions For general RL methods, obtaining the transition and reward functions of the entire MDP is merely impossible. Only empirical state transitions and rewards, sampled from the environments, efficiently updates state values for the empirical transition and reward functions. The empirical transition and reward functions are defined as Definition 1 (Empirical Transition and Reward Functions). Given an MDP
used by the RL algorithms. Therefore, provide method that
7), assume that we sampled samples (8/, ai 8i, rs) with some policy n, then the empirical transition function T
Σ -i=1 1(s' = 8 8;
T(8',,,)
(2)
Et 1(a =8)
and many consecutive transitions in the l samples form the trojectory I L which
1= U (is a, s,,),,
(3)
where m and n is the beginning and terminal time step of l. The empirical reward function R. is
R(s,a) = {rr ris if Bi s.t. s= a;. otherwise.
(4)
Empirical State-transition graph The empirical stato-transition graph from the empirical transition and reward functions which can be defined Definition 2 (Empirical transs-tanntnion Graph). Given an empirical transition function 7 and an empir-
ical reword function R, the corresponding empirical stale-transition graph is given by 99 = { where S is the mode set (i.e. each node corresponds to state), and the edge (8' 8, R( a)) E E if and only if T(', (a,,)))= 0.

---

Published in Transactions on Machine Learning Research (12/2024)
10 States/ Transitions Value updates
10 Transstranssssons/ Value updates
Intersection Stite
Empirical State-transition Graph
Highway Graph
State Action
Hiihway
Value updating
Figure 5: Intuitive idea of the highway graphs. The path without branching in the empirical state-transition graph can be merged highway. Value updating on the highway graph will be much less computationally extensive due to the dramatic reduction of the nodes and edges.
In deterministic environment, action a given current state s, uniquely determines the consequent state 8y. Therefore, ((', a) (0,1} in deterministic environments.
3.2 Highway graph
In our work, we convert the empirical state-transition graph into the highway graph with reduced states and transitions, shown in Figure 4 (2). What is highway graph and how obtain it are discussed in Scction 3.2.1 and Section 3.2.2 respectively.
3.2.1 Highway and highway graph
Naively, the value iteration algorithm requires iterating over a space of the whole empirical stale-transition graph (S x A x S) to reach the converged state value function, leading to a very high computational cost (van den Berg et al., 2012). To tackle this problem, we propose new graph structure, named highway graph, which is obtained from the original empirical stale-transition graph.
Instead of naively iterating over the whole empirical state- transition graph, seek to merge various value updates to reduce the computations. The intuitive idea of the highway graph is to merge the non-intersection states in the empirical state-transition graph, which converts a path in between intersection states, into a highway (an edge of the highway graph) to reduce the overall graph size, see Figure 5. The intersection states (nodes in the highway graph), which fork, merge, or loop state transitions, remain the same in the highway graph. Within this smaller, yet equivalent, highway graph, we can define new value update that effectively merges a few value updates under the original empirical state transition graph. This leads better efficiency since the highway graph smaller, which means fewer value updates required.
The edge from the merging, i.e. highway, denoted h E H, is defined in Definition 3.
Definition (Highway). Given an empirical Mate-transition graph 9 = {S.E7) that are constructed from series of samples (5/, at si, if for some s, S, there is only one trajectory I from to s' in the empirical state-transition graph, then I between and s' will be considered highway, denoted h s.s E H:
h L,,0"
(5)
Based on highways, the highway graph with shrunk graph size is defined in Definition 4. The merging to make the highways occurs for all possible nodes between non-branching paths, and only intersection nodes will be excluded. Thus, the highway graph is the minimal graph structure to fulfill identical value updating on the original empirical stato-transition graph. The value propagation of state transitions will be replacod by single operation on highways as much possible, and the value updating process will consequently speed up. Practical examples of the highway graph be found in Section 4.2 and Section 4.3.
7

---

Published in Transactions on Machine Learning Research (12/2024)
81 Ni
51
81
Constructing highways
(b) 82 SinterNO
hmm
h2.
+
82
hm,2
#2
E hmmp
Intersection detection State
Trajectory assembling Highway
Action
Figure The highway graph construction.
Definition (The highway graph). Given an empirical stale-transition gruph 9. {S, that are
constructed from series of samples (6/, ai Ti), its corresponding highwaay gruph Gx inter H} can be constructed as follows:
(1) Sinter {s|38/, 5f E SS # s, such that there are transitions from to s a. 0) and from to 5/g (5 s) > 0) in E,, or there are transitions from 8 to s (T a s,) > 0) and from s'y to 8 (T(s, 8/) 0) in };
(2) ys, s' E Sintery ha E H. if and only if there erist only one trajectory of 9. starts from s to s'.
3.2.2 Highway graph construction
Based on this idea, next give the incremental algorithm to continually construct the highway graph from the sampled trajectory 1. The entire algorithm can be divided into two phases: intersection detection and trajectory assembling, shown in Figure 6.
Intersection detection It aims to find all the intersection states and store them into Sinters which is initially an empty set, for the nodes of the highway graph. There are mainly two sources of intersection states. (1) it happens among new states of the newly sampled trajectory by revisiting previous states in the same sampled trajectory, denoted as NnterNNii (2) or during the merge between the new trajectories and the existing old highway graph, denoted as S AnterNO
The first type of the intersection state is given by Equation 6.
S Sinter N. = f&r: 8t, 81t1 E E1,8, E Spisited; 8141 & Spisited] U {r1t S111 E L, & Spisiteds 8 Svisited) U ( 841 E 1,, 8441 Spisiteds ($441) a.. 8,) & Teisited)
(6)
where S Spissted = and T Tvisited U/ ag. 8t) are the visited states and transitions of the current step in the trajectory Sets in different lines of Equation are for the forking, merging, and crossing of the current trajectory respectively.
Another type of the intersection state is given by Equation 7.
So
81 1 1,, 8141 E El,8, E Gu s411 & gn
8241 18, E EL, E IN 8141 E 2r }m }u
(7)
8141 8 8441 E E188, 8411 E &Hn, T 1,a, 1) = = =0].

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm 1 Highway graph incremental construction
Input : New trajectories C and existing 9x
Output: The updated highway graph Fz
foreach / E C do
2 Let source state 8; be so E c = (66: a0, 80 ro)
Find all intersection states SinterN U U of I using Equation 6 and Equation 7 foreach current intersection state 8j E sort ({0y: : E SiterrN U U. (nterroo) do Search sub-trajectory Ly that bridge 8; and $j
4
Convert lee into highway hag according to Definition 3 if 8, E Snter then
8
if has $ H then Let be H Hhhs
9
10
else if o E Emmm where mmn E H then
Let Sinte be Sinter Usj Split mmn into hns and hy,n
11
12
13
Let be H fim.j h mmm
14
else
15
Let Sinter be Sinter Usg
16
Let H be H. Wii
17
Let source state 8; be 8j
18
Let H be H U 3, where |2| T
19
return 9H = (Smter H}
where 8, E Sn means either 8, S Sinte or 8, E h(h E H), and F(t + 1, 1,a, f) is the transition function for any action a from state 8 to 8141 of 9x- The first two sets of Equation indicate whether 8, or 8141 of current trajectory / is in the existing highway graph GN (either is the existing intersection h E H) that should be considered as possible new intersection nodes. The last set of Equation is for the new intersections in an existing highway or is the existing intersections in the Gz- Thus, the intersection states will be in Equation 8.
within highway
Sinter = Snter U (8, : 8, E S U Notterno)
Trajectory assembling This phase will split the new trajectory L, by the newly found intersection states, and convert them into highways. If the interscction state is on the existing highway, this highway will be split into two highways by this state. After that, the intersection states and highways will be used to assemble the highway graph. Algorithm 1 shows the process of highway graph construction. The function sort () sorts the input set of states in ascending order according to the time step of the trajectory.
After the construction of the highway graph, the original MDP can be converted to a new MDP, which we call the highway MDP, defined in Definition The transition and reward function of the highway MDP is different from the ones in the original MDP. The transition function of highway MDP is only for intersection states in the highway graph, and the reward function is for the aggregated reward of highways instead of individual states. The action in the highway graph for 8, which transits the agent to h will bring the agent from s, to Sj.
Definition (Highway MDP). The highoway graph Iy convert the classic MDP (S,,,TRR,7) into highway MDP, denoted as MDPx (Sinters A, TH Ry,7) RH R (S. and
= {1, has E H and a is the first action of b4gs
Th (8 0, 8,) = 0,
(9)
otherwise.
9

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm 2 Value updating on highway graph
Input : Highway graph 9, = (Sinter H),, max learning iteration U, threshold of changes 8
Output: Highway graph with estimated state values Oz
Let be
while u < do
Update state value function Vi (1)) (s,) using Equation 11
Update state-action value function @ (5 az) using Equation 12 Set u be u + if E0,eS,merr Eayea EA AQ (8;, az) < then break
3.3 Value updating and target policy
During value updating, we introduce the graph Bellman operator as the planning module to iterate values on the highway graph. After that, we discuss how highway graphs help to speed up value updating and act as the policy afterward to tackle the task in the environment, as shown in Figure 4 (3).
3.3.1 Value updating on the highway graph
Once the highway graph and its highway MDP obtained, more efficient yet accurate value update of all states can be performed based on value iteration.
Highway MDP shares the same properties as the classic MDP, and the state values during updating are still in a complete metric space shown by Lemma 1, and RL algorithms suitable for MDP can be applied to Highway MDP as well. Lemma 1, associated with Lemma 2, will be used to show the convergence value updating on the highway, shown in Proposition 1.
E v, where V R enterl, V is estimate of state value function V, and 8; E Synter is from Highwwyy MDP, and define a metric d(w, v) = | - =l (w,v EV, V), then (V.d) is complete metric space.
Lemma 1. Denote the state value vector = ((2)) ,(,)), J
Bellman equation is widely used by temporal-differencc learning (Sutton & Barto, 2018). Given the currently sampled empirical transitions from the environment, states' values can be propagated within several time steps. However, this updale process only considers the future value along with one trajectory per ileration and leads to non-optimal value updates the best transitions are not sampled for the training. To avoid this issue, we give the graph Bellman operator to update the value of states in value itcration scheme on the highway graph, considering all the known future states for accurate value updating, defined in Definition 6.
Definition (Graph Bellman operator). Denote T is the 1-order neighbors of 8f on the highway graph 9x i.e. h4g E H. for 8, E r!, and max pooling function & to retrieve the effective value propagated from the neighbor. Given the complete metric space (V.d), d), the graph-based Bellman operator is ((V(tS.te)))) - V, and G; is
G.(V(s,)) +b s, (R(s,, +)V(()))
(10)
where 8, Synter.
Graph Bellman operator is still contracting mapping given in Lemma 2. Lemma 2. Graph Bellmon operator G is a maz-norm c-contraction mapping.
According the graph Bellman operator, the w-th value updating on the highway graph to obtain the state value and state-action value functions will correspondingly be
(a) (st) = 2 eerer (V-f (V/l=")(ss) (s,) Phnl + rhii
(11)
10

---

Published in Transactions on Machine Learning Research (12/2024)
iter.
itcr.
itcr. 3
iter. 4
0.90
0.99
0.98
0.98
Fag 4.9%
4.98.
4.98.
Val
1.98
Veg
4.78
Veg
4.78
Veg
4.78
4.78
4.78
4.83
4.78
1.00
1.00
0.98
1.96
1.96
5.73
5.02
6.51
5.62
0.98
0.98
4.73
4.68
6.51
4.68
Migg 0.98
4.83
5.62
Pag
5.62
State
Highway
Action selection of the state
Figure 7: Value updating and action selection of corresponding highway graph of the empirical state- transition graph in Figure (1). The discount, factor 0.99. The updated values of states and highways are in yellow in each learning iteration. The selected actions of intersection states are changing according to the latest learned value.
(s)
V/
((( (sn ?illisa + Theg."
(12)
where 81,8; E Sinters and a2 is the action to 8j from 8,. VA (s,) and Q (s; az) are initialized with zcros. The reward the highway Thes is
7
(13)
where T is the reward of the f-th state 8 in the highway. The value updating iterations of the empirical state- transition graph in Figure 4 (1) are shown in Figure 7, and the value of states are obtained by Algorithm 2. The process calculates the value of both intersection states and highways for U (less than oo) rounds until the state value function reaches optimal.
Next, we analyze the convergence of highway graph value updating in Proposition 1, and further give the speed advantages of value updating using the highway graph.
Proposition 1 (Convergence of value updating on highway graphs.). Let (V,d) be complete metric space of the MDPH = intter::A: TH. 7)) sufficient application of the graph Bellman operator G for value updating on highoway graph, according to Equation 11, converges to a unique oplimal state value function VA- The advantage of the highway graph is that uses a much smaller highway graph to replace the original empirical trate--ransiiion graph. This replacement leads to high computational speedup. The time complexity of value iteration on the original empirical state- tute-transition graph is O (15) |A] (S)) where (S] and [A] are the numbers of states and actions of the empirical state- transitionniiion graph, respectively, Highwways merge trajectories without branching, and the ratio of reduced states to original states is 2 = the time complexity of value updating on the highway graph is ([Sinter |A] (Stnter 1), which 1 times smaller than that of vanilla value iteration algorithm.
Remark 1.
18 p3ppl Consequently,
3.3.2 Highway graph as the policy
Once the values of states are obtained, the highway graph will be used as the policy. An example of action selection by the highway graph is also shown in Figure 7. The selected action for the state may change during the value updating until the highway graph with optimal state values is obtained. The action will be accordingly generated by the policy in Equation 14 to interact with the environment.
arg maxQ(s;;
8, Siuttr
03;-
8, his
(14)
random (s;)
8, & IN
where any is the action recorded in the highway bajj and random(s.) generate the action a for 8, by uniformed random sampling from the valid actions A.
11

---

Published in Transactions on Machine Learning Research (12/2024)
3.3.3 Highway graph re-parameterization
Despite the compact nature of value updating, an important property of the highway graph is the increasing graph size during constructioo from newly sampled empirical transitions. Thus, it is required to use neural network-based agent, derived from the highway graph, to interact with the environment. Ideally, a neural network-based agent can inherit useful state-action value information from the highway graph, and maintain the generalization ability of neural networks. To this end, we re- re-parameterize the stale-action value of the highway graph to obtain neural network-based agent to (1) reduce the storage cost for the growing highway graph; and (2) generalize the highway graph to more unknown states. By doing this the highway graph can be considered as a jump-starter for both model-free and model-based RL agent training at the early training stage, by providing the state transitions and its values.
Take the model-free Q-learning algorithm an example, the highway graph can be re-parameterized as the initial state-action value function Qs(s,, a) before continuing improvement using the Q-learning. The initial neural state-action value function Qo a) can be trained using the state-action pairs with learned values from the highway graph through supervised learning, and a simple MSE loss between Qu(s, a) and Qo(s, a) can be used during re- ce-parameterization Denole Qa as the trained neural network- -aaed agent utilizing the highway graph. The action as generated by Qe for the s; will be
0g arg max Qo(s;
(15)
4 Experiments
In this section, we first evaluate the expected return (accumulated rewards with discount) versus frames and computed time respectively on different categories of environments to answer the following questions: (1) is our proposed highway graph RL method suitable for both simple and complex environments? (2) can our method converge with less sampled experience/ experienceccompute /compute time to a policy yiclding higher returns compared to other baselines? Next, we analyze the functionality and behavior of our method by investigating: (3) evidence of the structural advantage of the highway graph; (4) effectiveness and efficiency details of value updating on the highway graph; (5) the performance of the re-parameterized neural network-based agent.
Environments To better show the training efficiency advantages of our highway graph RL method, we only use one million frames of interaction from different types of Environments. Whether the information from one million frames is enough to solve the task in the environments will also be shown. Different random seeds are used to guarantee the deterministic assumption of the environments. Types of environments are listed below.
Simple Maze 1; a simple maze environment with customizable sizes.
Toy Text (Towers et al., 2023): a tiny and simple game set, with small discrete state and action spaces, including FrozenLake, Taxi, ClifWWalkigg, and Blackjack.
Google Research Football (GRF) (Kurach et al., 2020): physical-based football simulator.
Atari learning environment (Bellemare et al., 2013): a simulator for Atari 2600 console games. These games are different, interesting, and designed to be a challenge for reinforcement learning.
Baselines We compare our highway graph RL method (HG) with different baselines for different environ- ments based on difficulty and complexity. For Simple Maze and Toy Text, our method is compared with model-frec Q-lcarning methods DQN (Mnih et al., 2015) and policy gradient method A3C (Mnih et al., 2016) and PPO (Schulman et al., 2017), as well as mosel-based method MuZero (Schrittwieser et al., 2020) and its variants including Stochastic MuZero with a more powerful transition model (Antonoglou et al., 2022) and Gumbel MuZero with optimized root action selection for MCTS (Danihelka et al., 2022), to show how
hhttss//gthhbb.cm//MaatCCCaaaa mmye-
12

---

Published in Transactions on Machine Learning Research (12/2024)
The HG behavior on The Simple Maze. We evaluate the convergence to the optimal state value function of value updating the highway graph on three maze environments of varying sizes. We show the total reward and average discount return after convergence, frames and time taken until convergence, as well as the minimum number of learning iterations required for the convergence.
Table 1:
Total Reward
Discounted avg. return
Frames
Wall clock
Converged learning
used (M)
time (min)
iteration(s)
3x3
0.97
0.93+0.01
0.07
0.03=10001
1
5x5
0.95
0.82=0.02
0.09
0.12=0000
1
15x15
0.96++0.01
0.37+0005
0.43++0.02
+0.04
different categories of RL methods learn the state before update its value (as shown in Figure 3) and the advantages of the highway graph. For more difficult and computationally demanding GRF environments, our method is compared with the Q-learning method R2D2 (Kapturowski et al., 2019) and policy gradient method IMPALA (Espeholt et al., 2018) to reveal the efficiency advantage during value updating among important model-free RT. methods and our model-based highway graph RT. method. The Atari games are important image-based environments for RL algorithm evaluation duc to their versatility, so take both classic methods including DQN, PPO, A3C, and slate-of-the-art episodiic-conlrolbbsseel methods including EMDQN (Lin et al., 2018), GEM (Hu et al., 2021), MFEC (Blundell et al., 2016), NEC (Pritzel et al., 2017a) as the baselines for a more comprehensive comparison. The reason we include the opisodic--contro--ase methods is that these methods also use a memory module of transition to speed up the value updates which is similar to the highway graph RI, method. In addition, we use RLlib (Tiang et al., 2018) implementations for DQN, PPO, A3C, R2D2, and IMPALA. Other baselines including NEC, MFEC, EMDQN, GEM, and Gumbel MuZero are obtained from its official repository. The network architectures and hyperparameters of different baselines are given in the Appendix.
Experiment sctup Our method also adopts an actor-learner training scheme similar to SEED RL (Espe- holt et al., 2020). During the experiments, our highway graph RL agent is trained from scratch to compare to other baselines. The general training process is as follows. (1) The actors are guided by the highway graph to get the experiences in episodes with expected returns. Thus, initially, when the highway graph is empty, the actors randomly explore the environment before the first highway graph is constructed. The values of employed across the actors for e-reedy strategy are equally spaced, starting from 0.1 and ending at 1.0. During training, if the actors see an observation not in the highway graph, a random action is taken. (2) New experiences from the actors will be used to incrementally update the highway graph by the learner, and a value learning of the highway graph will be fulfilled for better action selection. During the value learning, our method propagates the values among nodes in the highway graph based on topological adjacency. The nunber of episodes used for incrementally highway graph updating vary across enviromments: 10 for Simple Maze and Atari games, 20 for Toy Text, and 50 for GRF. (1) and (2) are processed alternatively for iterations until the end of training. All the experiments were running in the Docker container with identical system resources including 8 CPU corcs with 128 GB RAM, and an NVIDIA RTX 3090Ti GPU with 24 GB VRAM. The reported result of each experiment is from the averaged results among 10 different runs.
4.1 Comparison with baselines
4.1.1
Simple Maze
The Simple Maze environment generates a grid-like maze whose width and length can be specified. A sequence of adjacent grids not separaled by a line constitutes a path, and the lines between grids are the walls that the agent cannot get through. The state of this environment at each step will be the current agent location, i.c. 2D coordinates, in the maze. The agent can move within the maze with up, down, loft, and right actions. The RL agent needs to find path from the blue/start point in the upper left to the red/terminate point in the lower right. Once the path is found, a reward of + 1.0 can be obtained. A very
13

---

Published in Transactions on Machine Learning Research (12/2024)
HG
A3C
PPO
DQN
MuZero
Stochastic MuZero
Gumbel MuZero
Expected Return
Expected Return
Minu
(a) Simple Maze 3x3
Expected Return
Expected Return
84
Frames
Minutes
Frames
(b) Simple Maze 5x5
Experted Return
Expected Return
Minutes
Frames
Minutes
Frames
(c) Simple Maze 15x15
Figure 8: Expected return and efficiency comparison on 3x3, 5x5, and 15x15 Simple Maze environments. The lines and shaded areas are for the average values and the corresponding range (+) of standard deviations, and dashed horizontal lines show the asymplotic performance. Each run of every method was recorded from three perspectives simultaneously: frames and minutes versus expected return demonstrate the performance over frames and time (in the first two columns), and frames versus minutes to illustrate the relative training efficiency (in the last colunn).
small penalty /nnumberofgrrds will be applied for cach move. The maze environments are configured different sizes: 3x3, 5x5, 15x15.
Table 1 records the behavioral statistics after the highway graph RL agent solved the puzzle in each maze. The policy, derived from the highway graph, is considered to have converged only if newly collected experiences do not enhance the highway graph for better action generation. Although the lime used varies, the optimal path to the desired location was found in all environments by the agent after a single iteration of value lcarning, and the training converged environment relatively tiny (i.c. less than hundreds of states), so the highway can be constructed with no more than half million frames and fulfill value learning entirely the GPU in parallel. The value learning
the optimal policy within a minute. The state space of this kind of
14

---

Published in Transactions on Machine Learning Research (12/2024)
Table 2: The HG behavior on Toy Text. We evaluate the convergence of value updating on the highway graph three Toy Text environments to show the total reward and average discount return after convergence, frames and time taken until convergence, as well as the minimum number of learning iterations required for the convergence.
Total Reward
Discounted avg. return
Frames used (M)
Wall clock
Converged learning
time (min)
iteration(s)
Taxi
6.34
5.12:55.99
0.11#0.01 0.10
0.24+0.01
1
CliffWalking
-13000=0.01
-1.088
0.30=#0.02
1
on the whole graph, instead of sampling part of the graph, makes sure the optimal value will be propagated accurately to all states after each value learning iteration.
Next, to extend Table 1 with more training details, we compare the expected return over frames and clock wall time of our method and other baselines, shown in Figure 8. The highway graph RI. method is 20 to more than 1000 times faster than other baselines to solve the Simple Maze 3x3, achieves the best expected return on Simple Maze 5x5, and is the only method to solve the Simple Maze 15x15 within one million frames. Both the model-free DQN, model-based MuZero, Stochastic MuZero, and Gumbel MuZero demonstrate instability and relatively slow value learning. Gumbel MuZero has been shown to outperform other MCTS methods in terms of planning efficiency, as it requires fewer simulations to achieve superior outcomes. They are unable to find a path to the desired location in Simple Maze 5x5 and 15x15 with such a few frames. This is because the sampled transitions may not always be in the optimal path when updating state values, preventing the optimal values from being propagated. This can be correct with much more sampling, but if the amount of sampled transitions is small, it is hard to update by the optimal value for states. Model-free policy gradient methods PPO and A3C outperformed MuZero and its variants in Simple Maze 3x3 and 5x5 with much fewer frames and time. However, PPO and A3C did not find the optimal path of Simple Maze 5x5 and 15x15 within one million frames. The reason is that the trajectories, used to update the state values, to the desired location sampled by PPO and A3C are not enough, and there is still improving space to obtain more precise state values. See Section 4.3 for more detailed analyzes.
Consequently, HG can update state values with values from the optimal future states to avoid inaccurate and redundant value updates for every learning iteration.
4.1.2 Toy Text
Toy Text is more complex than Simple Maze since there will be many more paths to the desired location (Towers al., 2023). We choose the deterministic CliffWalking and Taxi environments from Toy Text to evaluate the RL methods.
HG acts similarly when it is Simple Maze, shown in Table 2. HG agent converged to the optimal policy and the optimal solution was found after one learning iteration within minute.
The execution time and expected return of all methods are shown in Figure 9. HG achieved the best expected returns for all environments, and the growth rate of time over frames is the smallest among all methods, according to the third column Figure 9. For Cliffaaliig results in Figure 9 (a), the optimized root action selection for MCTS helps Gumbel MuZero firstly converted to a locally optimal policy which is worse than the optimal policy due to the lack of sampling and training. DQN and PPO gradually increased the ability to get higher scores until the global optimal was reached. A3C and Stochastic MuZero did not effectively find a solution within one million frames of training. CliffWalking is different from Simple Maze since most grids have paths to the desired location. Thus, most sampled transitions of DQN can propagate optimal values to the starting state. However, randomly sampled trajectories will fade and slow down the optimal value propagation of A3C for each state. For Taxi, all basclines were unable find the solution within one million frames, see Figure 9 (b). MuZero, Gumbel MuZero, A3C, and DQN converged to local optimal policy. PPO and Stochastic MuZero require more training develop better behavior.
15

---

Published in Transactions on Machine Learning Research (12/2024)
HG
A3C
PPO
DQN
MuZero
Stochastic MuZero
Gumbel MuZero
Expected Retuurn
Exprected Return
www
2000
08
Minutes
(a) ClifWalking
Expected Return
Expected
Frames
Minutes
Frames
(b) Taxi
Figure 9: Episodic reward and efficiency comparison on Toy Text enviromments. The lines and shaded areas are for the average values and the corresponding range (=) of standard deviations, and dashed horizontal lines show the asymptotic performance. Each run of every method simultaneously: frames and minules versus expected return to demonstrate the performance over frames and time (in the first two columns), and frames versus minutes to illustrate the relative training efficiency (in the last column).
recorded from three perspectives
Thus, these environments are again examples to show our HG can update state values without inaccuracy and redundancy.
4.1.3 Google Research Football
Next, we test our algorithm on the more difficult and computationally demanding Google Research Football (GRF) (Kurach et al., 2020) environment to show the efficiency of value updating. Agents evaluated three customized environments of 3 vs 2, 5 vs 5, and 11 vs 11 with increasing difficulty. The 3v2 is the attacking scenario with three defenders and two offenders including one goalkeeper for both teams. The tasks of 5v5/11v11 are confrontation scenarios with 5/11 players on each side, We use the single RL agent to control all the players the team on the hand side according to the player's specific state at each time step, and the state the SMM (Super Mini Map) feature (72 96 x 4) direct output from the GRF environment. Random sceds are used for cuvironments to moct the deterministic assumption. There are two different rewards: goal reward and distance reward. If a team scores goal, the simulator returns +1.0 reward. The distance reward is determined by the minimum distance to the opponent's goal any team player ever made in this episode (the closer, the higher, with max +1.0).
The expected return and execution time of different RL agents are shown in Figure 10. The HG achieved the best expected return and scored for all scenarios within one million frames. Both IMPALA and R2D2 cannot score goals all scenarios because the input of these environments is more complex and requires more computation update the value of states. IMPALA made more progress on all scenarios compared with R2D2. This is partially because, in large state space, the states the path to the goal have
16

---

Published in Transactions on Machine Learning Research (12/2024)
HG
R2D2
IMPALA
Expected Return
Expecled Return
Minules
Frames
Minutes
Frames
(a) Custom 3 vs
Expeztes Retum
Expected Retum
3.4
Minules
Frames
Minules
Frames
(b) Custom 5
Expested Return
Expected Return
wywmmn
Minutes
Minutes
(c) Custom vs 11
Figure 10: Expected return and efficiency comparison 3v2, 5v5, 11v1l scenarios. The lines and shaded areas are for the average values and the corresponding range (+) of standard deviations, and dashed horizon- tal lines show the asymptotic performance. Each run of every method was recorded from three perspectives simultaneously: frames and minutes versus expected return to demonstrate the performance over frames and time (in the first two columns), and frames versus minutes to illustrate the relative training efficiency (in the last column).
higher chance of being chosen to update value by a policy gradient method than the Q-learning method. With the number of possible states becoming larger from 3 vs to 11 vs 11, the learning efficiency of R2D2 correspondingly decreased.
From the result on GRF environments, we can see the efficiency advantage of our highway graph RL agent.
See Section 4.3 for more speed advantage of value updating.
17

---

Published in Transactions on Machine Learning Research (12/2024)
HG
A3C
PPO
DQN
NEC
MFEC
GEM
EMDQN
1999
Expected Retum
Expected Retur
L200
2900
Frames
Min
Framess
(a) BattleZone
Expeceed Return
Expected Return
Minutes
Frames
Min ubes (b) Defender
Frames
2912
Expected Return
Expecled Retur
Frames
Min utes
Frames
(c) StarGunner
Figure 11: Expected return and efficiency comparison on Atari games. The lines and shaded arcas are for the average values and the corresponding range (+) of standard deviations, and dashed horizontal lines show the asymptotic performance. Each of every method was recorded from three perspectives simultaneously: frames and minutes versus expected return to demonstrate the performance over frames and time (in the first two columns), and frames versus minutes to illustrate the relative training efficiency (in the last column).
4.1.4 Atari learning environment
The Atari games using the Atari Learning Environment (Bellemare et al., 2013) are also used to evaluate proposed method. We randomly select games with mainstream genera of Atari to train the different RL agents for one million frames. An environment seed is also used during initialization for all games to guarantee the deterministic property.
The state of Atari games may not be directly accessible, instead we got an observation from the environment. To solve this, we use a recurrent random lincar projector on all the past obsorvations of the episode, to obtain more compact state representation for the highway graph. This projection does not affect the deterministic property of the environments. More details of the random linear projector in the Appendix.
18

---

Published in Transactions on Machine Learning Research (12/2024)
States (nodes in the state transitaion graph) Intersection States (node in the highway graph)
Transirions the state-ransstion graph) Highways (edge highway graph)
$2.5%
10.0%
100.0%
100,0%
92.5%
27.9%
9.5%
4.4%
Simple 15x15
(e)
vs
-0.9%
10b00%
100.0%
0.5%
0.4%
1.2%
(c) CliFWalking
(f) BattleZono
Defender
(b) SurGunner
Figure 12: Percentage of nodes and edges in the highway graph compared with its corresponding state- transition graph. The conversion into highway graphs dramatically reduces the size of both nodes and edges.
Next, compare the total scores of different agents different games, shown in Figure 11. We can the expected return curve of HG is above all the baselines for every environment. It shows the value of states of trained HG agent will be more accurate than other methods. Another advantage of HG is drawn on the efficiency. The growth rate of time over frames of HG the smallest. Additionally, HG only used about 1/10 to less than 1/ 1/150 period of time compared to other baselines to get converged and finish the training.
Many ppisodic-controd boased methods including EMDQN and MFEC show high sample efficiency by achiev- ing relatively high scores, but the training efficiency of these methods is low.
Consequently, the highway of HG improves the value updating efficiency and accuracy simultaneously on Atari games.
4.2 Structural advantage of highway graph
To investigate the advantage of our highway graph compared with the original empirical stato-transition graph; we compare the size of nodes and edges for different environments, see Figure 12. The size of the nodes and edges of the highway graph is smaller than the original empirical state-transition graph. For example, the empirical state-transition graph of StarGunner has 234,521 nodes and 236,266 edges, whereas its highway graph only has 1,084 nodes (0.5%) and 2,829 edges (1.2%). According to Remark 1, 2 0.005 << 1 means the computation required by the value updating will be theoretically reduced to 205x Many environments, including all evaluated Atari games, have very few intersection states (nodes), which makes the highway graph small enough to be loaded entirely into GPU to update all known state-action values in parallel, and hence achieve a promising acceleration during training.
Simple tasks, such Simple Maze and Toy Text environments, have densely connected state-transition graph with small state space of the empirical state-transition graph, whereas tough tasks observe nearly tree-like state-transition graph structure, where states different branches not connected, with large state space. This trend becomes more obvious as the complexity of the environment increascs, since from a state, in a complex enviromment, it is not easy to move to a previously visited state. After converting lo highways, many paths can be shrunk as highways to reduce the number of states and edges. Thus, the use of the highway graph to model and update the value can be less computationally extensive. of highway graph and its original empirical state- transition graph of a trained agent for the Custom 5 5 is shown in Figure 13. More comparison for the Atari game can be found in the Appendix.
comparison
19

---

Published in Transactions on Machine Learning Research (12/2024)
Non-branching path
Highway
(a) Empirical state-transition graph
(b) Highway graph
Figure 13: The empirical state-transition graph (a) and its corresponding highway graph (b) of Custom 5 5. The states in both (a) and (b) are blue cycles, highways in (b) are green arrows, and transitions are in grey. One of the highways and its corresponding path are highlighted in red in (b) and (a) respectively. The nodes and edges in the highway graph are considerably reduced.
1.0
0.7
Node Value
0.6
0.5
Figure 14: The 15x15 maze environment (left) and its state values on the corresponding highway graph
(right, self-loops are not shown).
4.3 Value updating advantage of highway graph
Value updating completeness This experiment invostigates the distance between the values output by trained RL agents and the ground truth values of each state on Simple Maze 15x15 (225 states total). Completeness indicates the percentage of state values that are identical to the ground truth. The distances and completeness of value updating of different methods performs optimal value updating of this task, and all states' values are updated ideally. The visualization of the learned HG model for the Simple Maze with size of 15x15 is shown in Figure 14. The comparison methods cannot completely update the values of all states and many states have incorrect values.
method shown in Table From the rosults,
In the case Simple Maze 15x15, the DQN cannot successfully find a path to the target location. We find this caused by the design of Q-learning. The effective training of Q-learning- considerable amount of high-rewarded samples in the replay buffer (the ratio of the high-rewarded samples is mask-dependent)) The training of the state-action value function of this kind of method is influenced by the sampled transition and its built-in target state-action value function. Using the high-rewarded samples, the statc-action value function will be more close to the real situation. Later, the target state-action value function can be updated more reliably, and the agent training enters a virtuous cycle. However, the high- rewarded sample is not enough, the target state-action value function will take more effect. The sampling in the Simple Maze environment is not necessary to always find high-rewarded samples, and more exploration may find samples with lower rewards due moving penalties. That leads an unusable target state-action value function at early stage that the entire Q-learning will fail.
algorithms relies on a
20

---

Published in Transactions on Machine Learning Research (12/2024)
Table 3: Value updating completeness. It shows the distance to the ground truth of the learned value after million frames of training. Completeness indicates the percentage of state value that is identical to the ground truth.
Method
Min Distance
Max Distance
Avg. Distance
Completeness (%)
PPO
0.24
0.99
0.53
1.88%
DQN
0.13
0.92
0.41
6.57%
HG (Ours)
0.00
0.00
0.00
100.00%
Valuee update speed (M Op./s)
HG Stargunner
HG Simple Maze 15x15
10a
DQN Simple Maze 15x15
10-4
10
Learning iteration
The million step/operation (Op.) per second of different value update iterations. The value update speed is the value propagation steps among the original empirical state-transition graph per training iteration. In each iteration, the highway graph is converted to empirical transition graph to calculate the value update speed.
Figure 15:
Value updating speed advantage We further show the value updating speed (the value propagation steps among the original empirical State-transition graph per training iteration). We use the Simple Maze with the size of 15 x 15 (225 states in total) and StarGumner to show the value updating speed. The results are in Figure 15. The speed of value updating on the highway graph is converted to value updating steps in the empirical state-transition graph, by counting the value updating operation for each transition. The results show the value updating speed of DQN the slowest which is due to the N-step TD learning algorithm, where only parts of the states always updates the entire graph, and HG reaches the 1159 + 31 million Op./s value updating speed during the 10th value update in the StarGunner. HG's s value update speed gives evidence for faster convergence on previously evaluated environments.
sampled for the value learning. On the contrary,
HG
4.4 Performance of re- parammetrrized neural network-based agent
Graph re-parameterization Atari games require very large state-transition graphs to store the environ- mental information, and graph re-parameterization can help reduce storage costs. To re-parameterize the information the highway graph, we use a very simple 2-layered MLP with 512 units in each layer store the state-action value of the highway graph. The re-parameterized neural nelwork-based agent is HG-Q. The relative performance of the expected return of the neural network- based agent HG-Q compared with the HG is shown in Figure 16.
From the result, we can see the neural network-based agent achieved an on-par performance compared with the agent built from the highway graph. Additionally, on Atari games, the neural network-based agent outperformed the highway graph by about 5% to 20%, which shows the generalization ability of the neural networks. These experiments indicate that the highway graph can be a jump-starter for other RL agents during the early stages of training.
21

---

Published in Transactions on Machine Learning Research (12/2024)
Relateive Expected Return (9)
133..0
HG
HG-Q
120.0
110.0
90.0
80.0
Simple Maze 3x3
custom 3 vs
StarGunner Environments
Defender
BattleZone
Figure 16: The relative expected return of HG-Q compared with HG.
HG
A3C
PPO
MuZero
Stochastic MuZero
Gumbel MuZero
Expected Recurn
Expected Return
Minutes
Frames
Minutes
Frames
Figure 17: Highway graph on stochastic environments Blackjack.
5 Limitations
One of the important assumptions when designing the highway graph that the state can be restored by observation. Thus, the highway graph does not suit partially observable and stochastic environments. (1) In stochastic environment, from specific state, the same action does not always lead the same future state. In this case, the value updating of the highway graph will not be correct since the value will not always propagate in the same way. (2) In partially observable environment, the state in the state-transition graph will not always be reliable, one state in the graph might link to two different real states, i.c. state conflict. When state conflict exists, value updating of the highway graph will be incorrectly caused by the same issue in the stochastic environment.
Experimental results on Blackjack support this idea. The goal for players of Blackjack in Figure 17 obtain cards that sum to closer to 21 (without going over 21) than the dealer's cards. The card the player gels every time is randomly selected, which makes the environment stochastic. We evaluate the expected return of the highway graph of stochastic environment Blackjack from Toy text and the expected return will be unpredictable, resulting in failed highway graph, see Figure 17. The found result is mainly caused by the state conflict, which means two different states will have the same representation and use the same node in the highway graph. The different nodes the highway graph should lead to different actions, but the state conflict prevents the agent from doing so.
6 Conclusions
The high cost of training RL agents has constrained their research and practical applications. To address this challenge, we explored a novel approach to significantly reduce this cost by applying the concept of highways, inspired by real-world transportation systems, the valuo-updating process of RI. algorithms. We introduced the highway graph structure, derived from the empirical state-transition graph, which sub- stantially reduces the state space. This structure be learned from sampled transitions and seamlessly
22

---

Published in Transactions on Machine Learning Research (12/2024)
integrated into the value iteration procedure, enabling efficient value-updating process. Furthermore, we provided theoretical proof of convergence to the optimal state value function when using the highway graph for value learning.
In our experiments, we evaluated the highway graph RL method across four categories of learning tasks, benchmarking against range of other RL. methods. The results demonstrate that our method drastically reduces training time, achieving speedups ranging from 10-fold to over 150-fold compared to baselines, while maintaining equal superior expected returns. Additionally, re-parameterized the highway graph into simple neural network-based agent, which achieves comparable or improved performance with minimal storage requirements.
To enhance the versatility of the highway graph RL method, future work could extend the approach to partially observable environments with stochastic characteristics, Moreover, the highway graph's aggregated and efficient value updating process could potentially be integrated into various RL algorithms during value learning, including value-based algorithms for multi-agent RL (Albrecht et al., 2024). By doing so, the highway graph has the potential to accelerate the value learning process of broader range of RL algorithms.
Acknowledgments
This work was supported by the Basic Research Foundation for Youths of Yunnan Province (20300AA0070147).
References
Stefano V. Albrecht, Filippos Christianos, and Lukas Schäfer. Multi-Agent Reinforcement Learning: Foun- dalions and Modern Approaches. MIT Press, 2024. URL https://www.arrl--ook.. www.mmalk.l...ommm com.
Alain Andres, Lukas Schäfer, Stefano V. Albrecht, and Javier Del Ser. Using offline data to speed up reinforcement learning in procedurally generated environments. Neurocomputing, 618:129079, 2025.
Joannis Antonoglou, Julian Schrittwicser, Sherjil Ozair, Thomas K. Hubert, and David Silver. Planning stochastic environments with learned model. In International Conference on Learning Represenlations, 2022.
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253 279, 2013.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z. Leibo, Jack W. Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control. arXiv preprint arXiv:1606.04. 2016.
Fengdi Che, Gautham Vasan, and A. Rupam Mahmood. Correcting discount-factor mismatch on-policy policy gradient methods. In International Conference on Machine Learning, volume 202, pp. 4218 4240. PMLR, 2023.
Yu-Ming Chen, Kuan-Yu Chang, Chien Liu, Tsu-Ching Hsiao, Zhang Wei Hong, and Chun Yi Lec. Compos- ing synergistic macro actions for reinforcement learning agents. IEEE Transactions on Neural Networks and Learning Systems, 35(5):7251-7258, 2024.
Ivo Danihelka, Arthur Guez, Julian Schrittwieser, and David Silver. Policy improvement by planning with gumbel. In International Conference on Learning Representations, 2022.
Mhairi Dunion, Trevor McInroe, Kevin Sebastian Luck, Josiah Hanna, and Stefano V. Albrecht. Conditional mutual information for disentangled representations in reinforcement learning. In Conference on Neural Information Processing Systems, 2023a.
Mhairi Dunion, Trevor McInroe, Kevin Sebastian Luck, Josiah Hanna, and Stefano V. Albrecht. Temporal disentanglement of representations for improved generalisation in reinforcement learning. In International Conference Learning Represendations, 2023b.
23

---

Published in Transactions on Machine Learning Research (12/2024)
Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Tain Dumning, Shane Legg, and Koray Kavukouoglu. IMPATA: scalable dis- tributed deep-rl with importance weighted actor-learner architectures. In International Conference on Machine Learning, volume 80, pp. 1406-1415. PMLR, 2018.
Lasse Espeholt, Raphaël Marinier, Piotr Stanczyk, Ke Wang, and Marcin Michalski. SEED RL: scalable and efficient deep-rl with accelerated central inference. In International Conference on Learning Repre- sentations, 2020.
Ilas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao Hc. Stochastic policy gradient methods: Im- proved sample complexity for fisher-non-degenerate policies. In International Conference on Machine Learning, pp. 9827-9869. PMLR, 2023.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Slulistics, volume 9, pp. 249 256, 2010.
Tairan He, Yuge Zhang, Kan Ren, Minghuan Liu, Che Wang, Weinan Zhang, Yuqing Yang, and Dongsheng Li. Reinforcement learning with automated auxiliary loss search. In Conference on Neural Information Processing Systems, 2022.
Hao Hu, Jianing Ye, Guangxiang Zhu, Zhizhou Ren, and Chongjie Zhang. Generalizable episodic memory for deep reinforcement learning. In International Conference on Machine Learning, volume 139, pp. 4380- 4390. PMLR, 2021.
Leslic Pack Kaclbling, Michael L Littman, and Andrew W Moorc. Reinforcement learning: survey. Journal of artificial intelligence research, 4:237-285, 285, 1996.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Afroz Mohiuddin, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model based reinforcement learning for atari. In International Confer- ence on Learning Representations, 2020.
Steven Kapturowski, Georg Ostrovski, John Quan, Rémi Munos, and Will Dabney. Recurrent experience replay in distributed reinforcement learning. In International Conference on Learning Representations, 2019.
Mohamed A Khamsi and William A Kirk. An introduction to metric spaces and fized point theory. John Wiley Sons, 2011.
Karol Kurach, Anton Raichuk, Piotr Stanezyk, Michal Zajac, Olivier Bachem, Lasse Espcholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, and Sylvain Gelly. Google research football: A novel reinforcement learning environment. In AAAT Conference on Artificial Intelligence, volume 34, pp. 4501 4510, 2020.
Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael I. Jordan, and lon Stoica. Rllib: Abstractions for distributed reinforcement learning, In Interna- tional Conference on Machine Learning, volume 80, pp. 3059 3068. PMLR, 2018.
Zichuan Lin, Tianqi Zhao, Guangwen Yang, and Lintao Zhang. Episodic memory deep q-networks. In International Joint Conference on Artificial Intelligence, pp. 1433-2439, 2018
Guoqing Liu, Chuheng Zhang, Li Zhao, Tao Qin, Jinhua Zhu, Jian Li, Nenghai Yu, and Tie Yan Liu. Return-based contrastive representation learning for reinforcement learning. In International Conference on Learning Representations, 2021.
Trevor McInroe, Lukas Schäfer, and Stefano V. Albrecht. Multi-horizon representations with hierarchical forward models for reinforcement learning. Transactions Machine Learning Research (TMLR), 2024.
24

---

Published in Transactions on Machine Learning Research (12/2024)
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7 2015.
Volodymyr Muih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Inter- national Conference on Machine Learning, volume 48, pp. 1928 1937. PMLR, 2016.
Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learn- ing. In Conference on Neural Information Processing Systems, pp. 3307-3317, 2018.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adrià Puigdomênech Badia, Oriol Vinyals, Demis Has- sabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In International Conference Machine Learning, volume 70, pp. 2827-2836. PMLR, 2017a.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adria Puigdomenech Badia, Oriol Vinyals, Demis Has- sabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In International conference machine learning, pp. 2827 2836. PMLR, 2017b.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In Interna- tional Conference Learning Representations, 2016.
Julian Schrittwieser, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy P. Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):604 609, 2020.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimiza- tion algorithms. Xiv preprint arXiv:1707.06:: 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Maciej Swiechowski, Konrad Godlewski, Bartosz Sawicki, and Jacck Mandziuk. Monte carlo tree scarch: review of recent modifications and applications. Artificial Intelligence Review, (6(3):2497-2566)) 2023.
Aviv Tamar, Sergey Levine, Pieter Abbeel, Yi Wu, and Garrett Thomas. Value iteration networks. In Conference Neural Information Processing Systems, pp. 2146-2154, 2016.
Mark Towers, Jordan Terry, Ariel Kwiatkowski, John U. Balis, Gianluca Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Arjun KG, Markus Krimmel, Rodrigo Perez-Vicente, Andrea Pierró, Sander Schulhoff, Jun Jet Tai, Andrew Tan Jin Shen, and Omar G. Younis. Gymnasium, 2023. URL https: //zenodo. org/record/812700
Jur van den Berg, Sachin Patil, and Ron Alterovitz. Efficient approximate value iteration for continuous gaussian pomdps. In AAAI Conference on Artificial Intelligence, volume 26, pp. 1832 1838, 2012.
Yuhui Wang, Weida Li, Francesco Faccio, Qingyuan Wu, and Jürgen Schmidluber. Highway value iteration networks. In International Conference on Machine Learning. Open 2024.
Xuchui Yu, Mhairi Dunion, Xin Li, and Stefano V. Albrecht. Skill-aware mutual information optimisation for generalisation in reinforcement. learning. In Conference on Neural Information Processing Systems, 2024.
Guangxiang Zhu, Zichuan Lin, Guangwen Yang, and Chongjic Zhang, Episodic reinforcement learning with associative memory. In International Conference on Learning Representations, 2020.
25

---

Published in Transactions on Machine Learning Research (12/2024)
A Details of baselines
For Simple Maze, Toy text, and Google Research Football, we adopt discount factor of 0.99, and for Atari games, we adopt a discount factor of 1 - 1e6 since very long trajectories in Atari games are not suitable for recurrent random projectors.
The official or widely recognized implementations, based on the original papers, for MuZero, Gumbel MuZero, and Stochastie MuZero are adopted, and the grid search was conducted on the most critical hyperparameters for them to ensure we obtained the best results. We use the default hyperparameters for those from the official code including NEC, MFEC, EMDQN, and GEM, which were tested to be the optimal oncs according to its original paper. Other methods are implemented by the RLlib, and adopt the best hyperparameters by fine-tuning and referencing the previous evaluation reported in the RLlib.
The network structure of different basclines depends on the environment observation spaces. If the obser- vation is images (Atari games), CNN encoder is attached to the front of the network, otherwise, a fully connected encoder is attached instead. For R2D2 and A3C, an LSTM encoder used. More detailed network architectures and hyperparameters of different baselines are:
DQN: double DQN is used with dueling enabled. N-step of Q-learning is 1. A Huber loss is computed for TD error.
A3C: the coefficient for the value function term and the entr regularizer term in the loss function are 0.5 and 0.01 respectively. The grad clip is set 40.
PPO: initial coefficient and target value for KL divergence are 0.5 and 0.01 respectively. The coefficient of the value function loss is 1.0.
R2D2: the LSTM cell size is 64 and the max sequence length is 20.
IMPALA: the coefficient for the value function term and the entropy regularizer term in the loss function are 0.5 and 0.01 respectively.
the implementation uses four 16-layer MLPs to learn the transition, reward function, state value function, and policy to select the action.
MuZero:
Gumbel MuZero: the implementation uses MLPs to learn the representation, dynamic, and predic- lion functions to serve the planning and action selection processes.
Stochastic MuZero: the implementation utilizes a 4-layer MLP as an encoder with a hidden size of 128 for the observation, and the rest of the parts remain as default.
NEC: the network structure consists of 3-layer CNN followed by linear layer. The size of the DND dictionary is 500000, a for updating stored values is 0.1, and 8 for thresholding the closeness of neighbors is 0.001.
EMDQN: there are 3 convolution layers and 2 linear layers in the net
GFM: the network is constructed using convolution layers and 1 linear layer.
B Random projection
Following the episodic control methods (Blundell et al., 2016), we use mapping function Fs, such RNN, or CNN+RNN with randomly initialized fixed parameters, to obtain the state representation of MDPs, i.e. random projection. Random projection transforms the input to another lower dimensional space with the linear properties preserved. Although Icarnable functions show promising results (Mnih et al., 2015; 2016), the state representation is always changing during the entire training process, which increases the difficulties of convergence. Instead, random projection without learning process will produce fixed state
26

---

Published in Transactions on Machine Learning Research (12/2024)
representations during the entire training, but its ability to represent complicated relationships between states is less powerful.
For Atari gamnes, we adopt a simple static linear RNN to reduce the state uncertainty by using all the historical observations, and each state 8, in the trajectory I can be calculated by Equation 16.
1s h random (or: 11) + random (0, E E!)
(16)
where - is the hidden vector of RNN. First hidden vector h_ is randomly initialized. w rondom and b random is initialized with xavier initializer (Glorot & Bengio, 2010), and will not update afterwards.
C Proof of Lemma 1
Proof. According to Equation 1, the value distance of any two different state value function estimates V and 122 for a state 8, E S Sinter can be described by
max (7())- = max a( +7 E ( 4
a(s +7 ET(h,
a
For any two different points u (V E R Bnseol))) we have two state value vectors
P* ('())). ))²
w
(2) (3(,))
where 8, E Sinter- The difference between w and can be described by the metric d as d (w,v) = (S - (S
max V' m (s,) (s,))
max R(s,, a) + E T((aass)V\()))
max R(s,, + ETs,,,,s)
max
Thus, we denote (V,d) the metric space from highway MDP.
Next, we prove all Cauchy sequences of V have a limit. Let (m(m) and (vfr)) be any two different Cauchy sequences of V, i.c.
(b(m) = (v) 1/2 Smnee
(m) (m)
(m)
(wl))) (vf (r)
According to the definition of the Cauchy sequence (Khamsi & Kirk, 2011), for arbitrary c 0, there exist N when m, r > N that
(m) d (((m)) mar (m))) v/-7 < e.
For any i, 1 (()) - o(t)) < e, so (1. (m)) and (u are Cauchy sequences of R.
(r) Since R complete metric space (Khamsi & Kirk, 2011), for arbitrary i, v has limit. Thus, we denote lim (r) = of, and we have (v*) = (Vi. ... uis which means every element of (x!") converged to a fixed point.
27

---

Published in Transactions on Machine Learning Research (12/2024)
According to the definition of the Cauchy sequence, have
d (ulm) w0) max i
(m) u/ <E.
The above relation shows that any Cauchy sequence of V converges to fixed point.
Hence, d) is complete metric space.
D Proof of Lemma 2
Proof. For any two different state value function estimates V1 and 1/2 we have two state value vectors
w (( .M (s)),, ...)) )],
= [v9(s))) .. (8)))).
where 8, E S Siter and we study the metric d for any 8, E Sinter
d (CA()))) G((2(s))))
o 2, हr:
(R( +
[ +
- 2,,er, +
()( +77')))))) - (R(s,,0)+>D2(0)
p. er!
[((0)) - (2(s)) ((05))10
= ,
S 7/w ulloo.
The metric for all intersection states Sinter will be
d (G(w), Sy [/0 ollao
Thus, the contraction property of the graph Bellman operator G holds that d (G(w)),(()) 7 (w v),
and G is a max-norm 7-contraction mapping.
E Proof of Proposition 1
Proof. The following proof will firstly give the convergence property for value updating on the highway graph; and prove the uniqueness of the convergence.
Property of convergence Given the complete metric space (V, for arbitrary w, u, x E V, the following properties (symmetry and triangle inequality) (Khamsi & Kirk, 2011) hold
d d(w v) = dv,, w), d (w,x) S (w + (v,x).
Lemma 2 has proved the graph Bellman operator G g-contraction mapping for V, ie. (G(ww, G(v)) s nd (w, v), then for arbitrary w, V, we have
d v)
d (w, G(w)) + d (G(w), v) d (w, G(w)) (G(w), G(v)) (G(()),)))
d d(G(w) w) + nd (w, v) + (G())))
28

---

Published in Transactions on Machine Learning Research (12/2024)
Moving the term yd (w,y) to the left and dividing for both sides, we have d(G(w), w) + d (G(v). v)
d vw x
1 1-7
Next, for any E V we define a sequence (Gtn)
(w) G(G(()), (()) G(G
(w) ( (w))))))..,))))))))))))))))))))) (c)
Then, we study any two elements of the defined sequence (1)(w, (U)(w) (G that d (G G (w) + d (GU+) (()
a (c (w), (w)(w))
1-7
)d(((w) w) + [d((((w)
1-7
7' +2 1-7 (G(w))..
Since y E [0,1), i,j co leads to 2' d (G(w), w) O.
So (G is Cauchy sequence of V. Given (V,d) d) is a complete metric space proved by Lemma where all Cauchy sequences will converge within V, the property of convergence of (G(n)) hold consequently.
1-7
Uniqueness of convergence Assume the value updating of the state value function converged to some point w' E V, which satisfies w' = G According to the graph Bellman operator G, we need to find that
G Gww") G (lim ((1) (w)
limn- G (G(m)) (w)
litm- G (x+11) (w)
w".
We can proof by contradiction. Assume there are two different points w", w", v² E V(w" F2" which satisfy G (w*) = wn and G (v") = v", then we have
0 (w", (v))
dGG(w") G,("")
s 7d (w" ,v))
d (w",v")
We find it contradictory that d(w", v*) < d(w", v*), and therefore conclude that G(w*) G(v*) = w². Furthermore, we study that
d (c() d (clh) G(w"))
yd (c(n-l(w),, w²)
? nd nd w²),
(17)
which indicates the sequence (G(") has a linear rate of convergence determined by 7.
From above, there only one fixed point
w = (22),, ... "..
29

---

Published in Transactions on Machine Learning Research (12/2024)
that the value updating will converge to, where Vi is the corresponding optimal state value function for the fixed point w" of convergence. This shows that the state value function Va during value updating the highway graph will converge to the optimal state value function Vi
F More discussions of Remark 1
The VI process aims to pass the value information among all states, which shares the value information of all states for every state. This process takes two steps: (1) interchanges value information pairwisely between any pair of states, which takes [S] x |A] number of computations, where [S], |A| is the number of states and actions; (2) passes the value information for a state from its farthest state by pairwise exchange in (1). The VI process in our work exhibits two extreme scenarios, with other cases lying in between these two.
Case 1. The entire empirical state- transition graph consists of single long path made of branchang transitions with |S] states, and the highway graph is reduced to two intersection states connected by single edge. Note that in the non-branching sequence of transitions, |A| will be 1. In addition, the possible farthest information passing starts from the last state to the initial state in this path, and the number of computations will be (S]. Therefore, the time complexity of VI on the empirical state-transition graph will be ((S) x 1) x [S]. Although the reduced states form the highway graph, the VI process does not change, and the difference is the size of the states reduced. So, the time complexity be mtterl x 1 mntell where (nterl = [S| That means the VI process on the highway graph will be f faster compared with the empirical state-transition graph.
for the highway graph will
Case 2. Despite the rarity of this occurrence in RL environments, all states in the empirical state-transition graph can densely connect all the other states via an action. In this case, step (1) of VT will pass all the value information among all states, and step (2) will not be required. Since states connect to all the other states, |A| = SS. The states are all intersections, which means |S] [Sinterl- So, the time complexity of VI on both the empirical stato-transition graph and highway graph will be |S| |A| SS] |S|
S S [
where | [s| 1. The condition is still satisfied that the highway graph is g2 times faster during VI.
Other cases lie in between Case and Case 2. Consequently, the reduction of time complexity of adopting the highway graph is in consensus with Remark 1.
G More experimental results
G.1 Highway graph for Pong
A comparison of a highway graph and its original empirical state-transition graph using 0.1 million frames for the Atari game Pong is shown in Figure 18. The size of the highway graph is significantly smaller than that of the original empirical state-transition graph, and this will expedite the value learning process during agent training.
G.2 Exploration capability
To assess the exploration capability of our HG method, Atari games, reduce the number of episodes for periodically updating the highway graph to one-fifth of its original value and increase the frame budgets by five times to 5 million frames. Through this setting, it will be more evident whether HG is more prone to getting stuck in suboptimal trajectories. The results are presented in Figure 19 (c)-
According the results, it can be observed that the expected return of HG all three games consistently increases without getting stuck at certain point and outperforms the performance compared to that with million frames.
30

---

Published in Transactions on Machine Learning Research (12/2024)
Non-branching path
Highway
(a) Empirical sate-transition graph
(b) Highway graph
The empirical state-transition graph (a) and corresponding highway graph (b) of Pong. The states in both (a) and (b) are blue cycles, highways in (b) are green arrows, and transitions are in grey. One of the highways and its corresponding path are highlighted in red in (b) and (a) respectively. The nodes and edges in the highway graph considerably reduced.
Figure 18:
Next, we additionally assess HG on Pong. In this context, we reduce the number of episodes for periodically updating the highway graph to one-tenth and increase the frame budgets to 10 million frames. The results are presented in Figure 19 (d).
From the results, HG solved Pong within 15 minutes by using approximately 6 to 9 million frames.
Based on all the aforementioned results, can observed that HG has the ability to explore better trajectories even when the initial highway graph is extremely small.
31

---

Published in Transactions on Machine Learning Research (12/2024)
Expecled Return
2000
Expeecedd Return
20000
Minutes
Frames
Minutes
Frames
(a) BattleZone
Expected Relum
Expected Retur
1300
MA Mnw
10000
2000
240
204
Frames
Min utes
Frames
(b) Defender
Expected Return
Expecled Return
k00
3000
Frames
Frames
(c) StarGunner
Expected Return
Expected Retur
Minules
Frames
1
Minutes
Frames
(d) Pong
Figure 19: Expected return and efficiency of HG Atari games. The lincs and shaded areas are for the average values and the corresponding range (+) of standard deviations, and dashed horizontal lines show the asymptotic performance. Each run of every method was recorded from three perspectives simultaneously: frames and minutes versus expected return to demonstrate the performance over frames and time (in the first two columns), and frames versus minutes illustrate the relative training efficiency (in the last column).
32


Reviews:
[{"review_id": "VmWY49ubiy", "reviewer": "Reviewer_EKdR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper demonstrated an effective method to improve training efficiency of reinforcement learning by simplifying the graph structure for state transition.\n\n- The paper presents the methodology in a detailed and clear manner.\n\n- Extensive experiments using various environments were conducted to demonstrate the efficiency of the proposed algorithm based on the Highway graph.\n\nWeakness:\n\n- In 'Related Work' section, a broader discussion around other researches aiming at improving the efficiency of basic reinforcement learning algorithms could be helpful. For example, there are researches on Graph Highway Networks, Highway Value Iteration Networks, Hierarchical Reinforcement Learning, and general graph contraction/state abstraction techniques. While these approaches differ from the proposed approach, they could provide more background than basic reinforcement learning algorithms.\n\n- In the 'Experiments' section, it is unclear whether the construction of the highway graph is incorporated into the evaluation and comparison with benchmark algorithms or if the highway graph is pre-constructed and not counted in the learning iterations. \n\n- Since the highway consists of a non-branching sequence of transitions, the original state-transition graph is not fully connected, resulting in original complexity lower than 𝑆×𝐴×𝑆. Clarifying how this relates to the reduction of time complexity would be beneficial.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies an effective graph-based algorithm designed to enhance the training efficiency of reinforcement learning in environments with discrete state and action spaces. The proposed approach simplifies the empirical state-transition graph by merging non-branching sequences of transitions into a single transition, referred to as a \"highway.\" This simplification significantly reduces the number of iteration steps required during learning. The authors conducted extensive experiments across a broad range of test environments to demonstrate the effectiveness of the proposed algorithm compared to various benchmarks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "To strengthen the work:\n- It would be helpful to include discussions on other algorithms that aims to improve efficiency of reinforcement learning.\n\nCritical for my recommendation for acceptance:\n- It would be helpful to clarify in the paper if the construction of highway graph is included in performance evaluation. \n- In 3.1.1, Remark 1. Could you confirm if \"The number of states is reduced to z\" or if the ratio compared with before is z? Could you also confirm if the reduction in time complexity will always be $\\frac{1}{z^2}$? For instance, consider a scenario where the original state transition consists of a single long path made of non-branching transitions, and the Highway graph is reduced to just two states connected by a single edge.", "broader_impact_concerns": "I have no concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wZ5WaDIf9A", "reviewer": "Reviewer_aY2z", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.The credit assignment is a core problem of RL algorithms. The paper propose a novel method that transforms the empirical state transition  graph to the highway graph. \n2. The paper proves the optimality of the method.\n3. Experiments validates its effectiveness.\n\nWeakness:\n1.The state abstraction method also reduce the problem size and compress the state graph. However, the paper does not discuss the relationship.\n2. It is hard to understand the definition the highway graph, the paper will be strengthen if the paper show some cases.\n3. It is unclear how the paper parameterizes the highway graph by neural networks. There is no difference between the highway graph and the critic network.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a highway graph method to improve the sample efficiency of RL methods in deterministic environments with discrete state and action spaces. The paper defines the highway as a non-branching sequence of transitions can directly bring the agent from the source state to the target state. Then the paper propose to directly update the value function of the source state with the value of the target state. The paper theoretically proves the convergence to the optimality of the value learning in the highway MDP. Experiments validates the effectiveness of the propose method compared with value-based, policy-based and search-based methods on some toy and some atari games.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the paper should revise according to the following points:\n1.The state abstraction method also reduce the problem size and compress the state graph. However, the paper does not discuss the relationship.\n2. It is hard to understand the definition the highway graph, the paper will be strengthen if the paper show some cases.\n3. It is unclear how the paper parameterizes the highway graph by neural networks. There is no difference between the highway graph and the critic network.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9HWlr9G22T", "reviewer": "Reviewer_C93Q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n1. Clean justification and interesting idea to compress the state transition model for faster learning\n2. Strong empirical results against baselines.\n\n### Weaknesses:\n1. The primary weakness I can detect is that it was not very clear to me from the text how exactly the experimental results from Tables 1 onwards are obtained. In particular, as I understand (and from looking at Section 4 Experiment Setup) first an agent is run in the environment (which agent?) in order to get samples of state transitions, then from the state transitions the empirical highway graph is constructed (according to definition 4), then the value function is learned against the simplified highway graph transitions, then that agent is evaluated. This however seems to disagree with the results in Figure 8 onwards, which have a frame budget on the x-axis, which would suggest that the highway graph is being constructed incrementally during exploration (like Algorithm 1?). I also could not find pointers in the Appendix for how exactly this is done. I had enough difficulty here that it makes it quite hard to read the rest of the text and reason about its significance, and I would very much appreciate some clarity around the matter. If it is true that there is an exploration phase before the highway graph is populated, then how were the frame budgets for Table 1 decided? If it is true that there is an exploration phase required, how important is the choice of agent for that phase?\n2. I'm not the most up-to-date with model-based RL, but it would seem to me like there would be missing recent model-based baselines in the experiments. Comparing this method to model-free methods, or MuZero at the latest feels a little strange, though I would be willing to hear an argument as to why nothing more recent is suited.\n\nMinor issues:\n1. Is there are reason why Figure 15 is 3d? I don't see why simple curves wouldn't suffice.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a method to accelerate reinforcement learning in deterministic settings by compressing the state transition model into a \"highway graph\" so that signal can propagate many steps into the past, making credit assignment much easier. Experiments support the strength of the proposed method.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see Weaknesses. In particular the results seem strong, but I am having quite a hard time judging them without understanding the exact method in each section, for each figure, and besides the Simple Maze setting that does not seem to be currently in the text (and even then I have questions about the Simple Maze setting. Addressing both weaknesses would be critical for my acceptance. I would be happy also to engage in dialogue around both points as I need more information before making recommendations.", "broader_impact_concerns": "None that I can see.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Significant discussion around the experimental settings and baseline results solidified my confidence in the overall paper. The algorithm in very clearly presented and easy to grok, so once the empirical results were thoroughly discussed it made sense to accept without further revision.
Decision: Accept (poster)