# Deep Q-Network Approach for Train Timetable Rescheduling Based on Alternative Graph
## 2 Materials and Methods
### Deep Q-Learning  
In reinforcement learning, instead of directly considering policies, a policy can be derived from the so-called _action value function_ or the _Q-value function_. For each policy \(\pi\), the action value function \(Q_{\pi}(s_{t},a_{t})\) is the expected total return given an action \(a_{t}\) at state \(s_{t}\) assuming the agent follows the policy \(\pi\). The optimal action value function is then defined as \(Q_{s}(s_{t},a_{t})=\max_{\pi}(s_{t},a_{t})\).  
Q-learning [25] maintains a lookup table of \(Q(s,a)\) for every state-action pair \((s,a)\). To estimate the optimal action-value function \(Q^{*}(s,a)\), the Q-learning approach uses the following updates:  
\[Q(s,a)\gets Q(s,a)+\alpha\bigg{(}r_{t}+\gamma\max_{a_{t+1}}Q(s_{t+1},a_{ t+1})-Q(s_{t},a_{t})\bigg{)} \tag{8}\]  
where \(\alpha\in[0,1]\) is the learning rate.  
However, \(Q\)-learning suffers the curse of dimensionality in maintaining the look-up table when the number of states and/or actions is large. One way to address this challenge is to approximate the \(Q\)-value function as a neural network. In particular, [PERSON] et al. [26] proposed the DQN method, which uses a deep neural network as a function approximation of the \(Q\)-value function. The neural network, called the deep \(Q\)-network, is modeled as a parameterized function \(Q(s_{t},a_{t}|\theta)\) and is determined by adjusting the parameter \(\theta\) in the direction of minimizing the following loss function:  
\[L(\theta):=\bigg{(}\bigg{[}r_{t}+\gamma\max_{a_{t+1}}Q(s_{t+1},a_{t+1}|\theta )\bigg{]}-Q(s_{t},a_{t}|\theta)\bigg{)}^{2}. \tag{9}\]  
To learn the optimal parameters and scenarios, the alternate sequences of states, actions, and rewards are randomly generated. To generate each scenario, an action is chosen from the current state \(s_{t}\) via the \(\epsilon\)-greedy policy in which the agent chooses the action maximizing the \(Q(a,s_{t})\), but there exists a small chance that \(\epsilon\) will choose a random action. In this way, we obtain a set of \((s_{t},a_{t},r_{t},s_{t+1})\), which constitutes the loss function \(L(\theta)\). The trained \(Q\)-network is used to make a decision by selecting the action that maximizes the \(Q\)-value. The pseudocode of the training phase of the proposed method is shown in Algorithm 1.  
Figure 3: (**a**) Example of state transition at \(t=0\); (**b**) Example of state transition at \(t=1\).  
In Algorithm 1, to mitigate the issue of instabilities during learning, the following techniques are typically incorporated [26]:  
* _Experience replay_. In its basic setting, \(Q\)-learning is on-policy, which means we generate scenarios and learn parameters simultaneously. When we consider the loss function with \((s_{t},a_{t},r_{t},s_{t+1})\) obtained from a set of scenarios, there exists autocorrelation among different \((s_{t},a_{t},r_{t},s_{t+1})\). However, most algorithms used for training deep neural networks assume that training samples are independently and identically distributed. Therefore, instead of on-policy learning, off-policy learning is incorporated, in which \((s_{t},a_{t},r_{t},s_{t+1})\) is stored in the so-called replay memory and a minibatch of a set of random samples from this memory forms the loss function.
* _Target network_: In both \(Q\)-learning and deep \(Q\)-learning, scenarios are generated with the policy derived by the current \(Q\)-value function being updated. This has been identified as one of the reasons for unstable learning. To overcome this problem, [PERSON] et al. [26] used two separate neural networks, \(Q(s_{t},a_{t}|\theta)\) and \(Q^{\prime}(s_{t},a_{t}|\theta^{\prime})\). The former network is used to generate random scenarios, and the latter, called the target network, is used to set the target in the loss function \(L(\theta)\). The parameter \(\theta\) is updated in the same way introduced previously, and the parameter \(\theta^{\prime}\) of the target network is kept unchanged during a predefined number of steps and updated to the parameter \(\theta\).