## 5 Proposed mMTC Device Grouping Algorithms
### Reinforcement Learning-Based Device Grouping Algorithm
#### 5.2.2 Lagrange Relaxation  
Considering the environment's constraints, it is essential to prompt the agent to achieve feasible solutions during the MTC device grouping decision. We apply the Lagrange  
Figure 4: The RL structure for massive MTC devices performing an RACH to access the B5G network. Following the reward, the agent optimizes its policy to group the devices further in the current environment. relaxation mechanism to reduce the complexity further. The proposed RL algorithm aims to implement a reward signal for constraint satisfaction and, inversely, a penalty signal for constraint dissatisfaction [52, 53]. As per the goal of our initial problem formulation, the objective of the proposed RL model is to maximize the reward for each constraint-satisfied device grouping decision, and it is given by  
Maximize \[\sum_{t=0}^{T}R(s_{t},a_{t})\] Subject to \[s_{t+1}=f(s_{t},a_{t})\quad\forall t,\]  
where \(R(s_{t},a_{t})\) denotes the reward function, \(s_{t}\) represents the state at time \(t\), \(a_{t}\) is the action taken at time \(t\), and \(f\) is the state transition function. The constraints, as mentioned earlier, on the states, such as application time constraints and actions, are denoted by \(C(s_{t},a_{t})\leq 0\). The Lagrange relaxation introduces a Lagrange multiplier \(\lambda\) and modifies the objective function to include the product of these multipliers and the constraints. The relaxed problem is formulated as follows:  
Maximize \[L=\sum_{t=0}^{T}[R(s_{t},a_{t})+\lambda_{t}C(s_{t},a_{t})]\] Subject to \[s_{t+1}=f(s_{t},a_{t})\quad\forall t,\]  
where \(\lambda_{t}\) represents the Lagrange multiplier associated with the constraint at time \(t\). Here, the term \(\lambda_{t}C(s_{t},a_{t})\) acts as a penalty for violating the constraints but is integrated into the objective function to facilitate solving the dual problem, optimizing over both primal variables (states and actions) and dual variables (Lagrange multipliers). The augmented objective function in the context of policy gradients with Lagrange relaxation is given by  
\[J(\theta,\lambda)=\mathbb{E}_{\tau\sim\pi_{\theta}}\left[\sum_{t=0}^{T}R(s_{t},a_{t})+\lambda C(s_{t},a_{t})\right] \tag{27}\]  
where  
* \(J(\theta,\lambda)\) is the augmented objective function, depending on policy parameters \(\theta\) and Lagrange multipliers \(\lambda\). * \(\mathbb{E}_{\tau\sim\pi_{\theta}}\) denotes the expectation over trajectories \(\tau\) generated by following policy \(\pi\) parameterized by \(\theta\). * \(R(s_{t},a_{t})\) is the reward received after executing action \(a_{t}\) in state \(s_{t}\). * \(C(s_{t},a_{t})\) represents the constraint function, which should ideally be non-positive for all states and actions. Positive values indicate constraint violations. * \(\lambda\) is the Lagrange multiplier associated with the constraint. Policy Gradient Update  
The policy parameters \(\theta\) are updated using gradients of the augmented objective function:  
\[\theta_{new}=\theta_{old}+\alpha\
abla_{\theta}J(\theta,\lambda) \tag{28}\]  
where \(\alpha\) is the learning rate. In summary, our model contains two phases, which are described as follows:  
* **The grouping phase:** As detailed in the Algorithm 1, in this phase, the agent generated a grouping vector to point out in which bin the device should be placed. This is performed according to some policies regulating the group size and the obligation of assigning the device to the group that has the least remaining space after the assignment. * **The evaluation phase:** In the evaluation phase, the grouping action is evaluated, and the rewards are generated based on whether or not the assignment is correct given the policies mentioned above and the environmental state during the grouping phase.