# Environment-Aware Adaptive Reinforcement Learning-Based Routing for Vehicular Ad Hoc Networks
## 3 Preliminaries
### Q-Learning Framework  
Reinforcement learning solves optimization problems through the specific framework of the Markov decision process (MDP) [42; 43]. The MDP can be described by the tuple (\(\mathcal{S}\), \(\mathcal{A}\), \(\mathcal{P}\), \(\mathcal{R}\), \(\gamma\)), where \(\mathcal{S}\) denotes a finite set of state spaces; \(\mathcal{A}\) denotes a finite set of action spaces; \(\mathcal{P}\) is the state-transfer probability denoted as \(\mathcal{P}(s_{t+1}\mid s_{t},a_{t})\), i.e., the probability of transferring after completing an action \(a_{t}\) in the current state \(s_{t}\) to the next state \(s_{t+1}\) probability; \(R\) is the immediate reward; and \(\gamma\) is the discount factor. Q-learning is a model-free reinforcement learning method based on the Markov decision process in which an agent selects actions to interact with the environment. Over a series of decision processes, the agent controls its behavior to maximize rewards. Unlike traditional machine learning, where training data are readily available, in Q-learning, training data are collected by the agent as it continuously explores an unknown environment. The algorithm relies on trial and error to find the optimal control strategy [44]. The entire workflow of this algorithm bears a close resemblance to the process of route selection, thereby making it applicable to routing models. When the agent explores an unknown environment through trial and error, it maintains a Q table containing optimal state-action pairs and their respective Q values. The Q-learning algorithm adjusts action selection based on rewards obtained from the environment and evaluates the chosen actions in the current state to maximize the Q value. The iterative process of updating the Q value in the Q-learning algorithm is depicted in Equation (2). Action selection relies on the action corresponding to the maximum Q value in the Q table for the current state. However, during the action selection process, there is a need to balance exploration and exploitation, typically achieved using an \(\varepsilon\)-greedy strategy. Nevertheless, the Q-learning approach is computationally expensive for exploring optimal paths, especially in scenarios with numerous states such as VANETs. \[ \begin{split}\mathcal{Q}(s_{t},a_{t})&\leftarrow \mathcal{Q}(s_{t},a_{t})\\ &+\alpha\{r_{t}+\gamma\times\max_{a^{\prime}}\mathcal{Q}(s_{t+1},a ^{{}^{\prime}})-\mathcal{Q}(s_{t},a_{t})\}.\end{split}  \tag{2}\]  
In the design presented in this paper, the agent corresponds to the vehicle nodes. To train the Q table and converge towards optimal paths, broadcast beacons are used to explore the network. The agent serves as the learner and decision maker in the Q-learning framework, thereby continuously interacting with the environment to learn control strategies. The environment encompasses the entire VANET scenario, or all objects that interact with the agent. It provides appropriate responses to actions and adjusts the state accordingly. Figure 3 shows the collaboration between the agent and environment in Q-learning for vehicle routing. The state space is the set of all valid neighbor nodes of the vehicle, and \(s_{t}\in\mathcal{S}\) can be depicted as \(\mathcal{N}_{v_{n_{t}}}\), thereby representing the neighbor set of vehicle \(v_{n_{t}}\). In particular, the size of the state space varies for each vehicle. The action space, the selectable next-hop neighbor nodes, and \(a_{t}\in\mathcal{A}\) represent the action taken by the agent at moment \(t\). In particular, since beacons are employed as actions, the broadcasted beacons are treated as reverse actions as they are received by the nodes. This is important, as it allows for fast convergence with low network consumption and a direct solution to the exploration or exploitation dilemma. The process of receiving a beacon is equivalent to exploring all possible next states in the current state. As shown in Figure 4, this study gives simple examples to demonstrate how the beacon update process works to converge quickly.