# Environment-Aware Adaptive Reinforcement Learning-Based Routing for Vehicular Ad Hoc Networks
## 3 Preliminaries
### Q-Learning Framework
For simplicity, the authors assume that each grid is a vehicle, \(\mathcal{V}=\{v_{n_{1}},v_{n_{2}},\cdots,v_{n_{15}}\}\), and that two neighboring vehicles are able to communicate directly with each other and form a link \(l\), for example, \(l=(v_{n_{1}},v_{n_{2}})\). That is, there are four neighbor nodes, and the arrows indicate the selection of a neighbor agent to forward the packet. The value above each arrow indicates the Q value of the corresponding action. For simplicity, the authors assume that the vehicle has four actions, i.e., up, down, left, and right. In the current state \(s_{t}\), the optimal action is defined as follows:  
\[a_{t}^{*}=\arg\max_{a_{t}}\mathcal{Q}(s_{t},a_{t}). \tag{3}\]  
In this example, if a node receives a beacon from the target node, it receives a reward of one. For beacons received from other neighboring nodes, the reward is 0. Throughout the grid model, randomly make a portion of the grid empty. That is, there are no vehicle nodes to send beacons, so the nodes around an empty node are unable to update the Q value in that direction.The Q-value update formula is as in Equation (2), with the discount factor \(\gamma=0.8\) and the learning rate \(\alpha=0.9\). In Figure 4, the lower right corner is the target grid D. Neighboring grids \(v_{n_{12}}\) and \(v_{n_{15}}\) can send packets to the target via one hop. That is, for the beacon sent by D, grids \(v_{n_{12}}\) and \(v_{n_{15}}\) are able to receive it. Grid \(v_{n_{12}}\) is labeled as null here, so it is not involved in updating the Q value. From Equation (2), \(\mathcal{Q}^{(1)}(v_{n_{15}},v_{n_{15}}{\rightarrow}D)=0+0.9\times(1-0)\), as shown in Figure 4b. After the second global Q-value update, i.e., \(v_{n_{11}}\), \(v_{n_{13}}\), and \(v_{n_{14}}\) Q-value update, \(\mathcal{Q}^{(2)}(v_{n_{11}},v_{n_{11}}{\rightarrow}v_{n_{15}})=0+0.9\times( 0+0.8\max\{0.99,0.513\}-0)\), \(\mathcal{Q}^{(2)}(v_{n_{13}},v_{n_{13}}{\rightarrow}v_{n_{14}})=0+0.9\times( 0+0.8\times\max\{0.713,0\}-0)\), \(\mathcal{Q}^{(2)}(v_{n_{14}},v_{n_{14}}{\rightarrow}v_{n_{15}})=0+0.9\times( 0+0.8\times\max\{0.99,0.513\}-0)\), as shown in Figure 4c. When the third update is done, the Q values of most of the directions have been updated as shown in Figure 4d. And on the fourth time, the Q values of all the directions have been updated, and it is possible to reach the destination grid from any grid in the grid map based on the Q value, as shown in Figure 4e. The Q values will stabilize in Figure 4f. Assuming that the source is grid \(v_{n_{1}}\) and taking the action with the largest Q value in its own neighbor set \(\mathcal{N}_{v_{n_{1}}}\), the route to reach  
Figure 3: Q-learning structure for VANETs. the destination grid is \(\mathcal{RP}(v_{n_{1}},D)=\{v_{n_{1}}\to v_{n_{5}}\to v_{n_{9}}\to v_{n_{13}}\to v_{n_{14}} \to v_{n_{15}}\to D\}\), \(\#hops(\mathcal{RP})=6\). Figure 4 gives a 4 \(\times\) 4 model from having no a priori information on how to converge to a stable path; only four updates are needed. Figure 5 presents a 6 \(\times\) 6 model, and, similarly, convergence for the 6 \(\times\) 6 model typically requires six updates, thereby stabilizing around the seventh update. It is essential to note that as the model size increases, the number of updates required for convergence using this method becomes less stable. Based on the n x n model, it can be easily demonstrated that, in the most ideal scenario, completing updates in a sequential manner from the destination to the top-left corner requires only one or two updates. Conversely, in the worst-case scenario, updating sequentially from the top-left corner to the destination necessitates 2(n\(-\)1) updates. In practice, the update order is random, thereby making it unlikely for either extreme case to occur. Such convergence is undoubtedly very rapid and relies entirely on the broadcast. It is worth noting that in the learning process of the 6 \(\times\) 6 model, the minimum path can be found independently.