# An Improved Q-Learning-Based Sensor-Scheduling Algorithm for Multi-Target Tracking
## 4 Detailed Description of the Proposed Algorithm
### Task Allocation
#### 4.3.1 Reinforcement Learning and Q-Learning Model  
Reinforcement learning (RL) mainly discusses how agents can maximize their rewards in the environment. RL consists of three parts: environment, action, and reward. After obtaining the status from the environment, the agent uses this status to output an action. After the action is executed, the environment outputs the next status and the delayed reward. Delayed reward is a scalar feedback signal sent by the environment to an agent, which can indicate how the agent performs when adopting a strategy at a certain step. Wefocus on RL for two reasons. First, the RL model can adapt well to the complexity and uncertainty of multi-target-tracking scenarios. Second, RL is free from the artificial label of supervised learning and explores the optimal strategies by agents themselves, which may be able to achieve performance beyond human capabilities. Q-learning is a value-based model-free RL algorithm, in which agents do not need to estimate state transitions or formulate explicit policies, but maintain a value table. The agent selects the most valuable action through this table. That is, the Q-learning model can provide what the optimal action is in the current state, but it will not provide which next state the agent will move to. Therefore, Q-learning is suitable for multi-target-tracking scenarios where the environmental state is difficult to estimate and the action set is discrete and limited. In contrast, Q-learning is more generalizable than the model-based method, which requires modeling a virtual environment. Since our training process is describable, and the state of the agent is discrete and observable, we do not need the state transition function, and we can obtain good model performance by training samples. In our model based on Q-learning, sensor nodes in the network can be mapped as agents. Each agent observes the current state of the environment and performs an action according to the exploration-exploitation policy. After that, the environment moves to the next state and produces a reward to strengthen or weaken the trend of the agent to choose this action. The system chooses actions for the sensors based on the value table and based on the principle of maximizing the agent's value function. Our proposed Q-learning-based task-scheduling mechanism is shown in Figure 2.  
Our goal is to maximize the cumulative reward and obtain the optimal scheduling decision. The proposed model can be described as follows:  
Each sensor node acts as an intelligent agent that can make its own decision and the tracking status of targets in the network represents the environment in our model. Interaction between agents and the environment is achieved by executing actions and receiving a reward function. According to the reward of each action taken by the agent in various states during training, we summarize a Q table. As shown in Figure 3, the ordinate of the Q table is the state, the abscissa is the action, and the Q value is obtained from the Q value of the previous state and the estimated future reward, which is given by Equation (13). Every time the agent is in a certain state, the next action is to retrieve from the table the future reward with the highest value. If there are multiple identical values, one of them is randomly selected. Repeat until finished. This operation is repeated until the final state is reached. Figure 2: Proposed task-scheduling mechanism based on Q-learning. (1) Action Space  
The set of actions \(\mathcal{A}=\{a_{0},a_{1},\ldots,a_{n}\}\) is a set that collects all the targets that the sensors in the cluster can sense, and \(n\) denotes the target number. When the sensor executes action \(a_{i}\), it means it selects to track the \(i\)-th target. In particular, executing action \(a_{0}\) indicates that the sensor does not sense any target and goes to sleep. (2) State Space  
The environment state that the agent is in at each time step constitutes the state space \(S\), \(S=\left\{s^{1},s^{2},\ldots,s^{k}\right\}\).