Bi-CL: A Reinforcement Learning Framework for Robots Coordination Through Bi-level Optimization

Reinforcement Learning (RL) has gained significant popularity for controlling robotic systems for complex tasks [11]. Using RL for multi-robot systems faces the challenge of increased system dimension and the need for robots to make decisions based on local observations. Addressing these challenges has led to the development of the CTDE [3] learning scheme, which enables robots to cooperatively learn coordination strategies through centralized training, while the learned policies are local and, thus, can be deployed for decentralized execution. Examples include MADDPG [3], which extends the centralized Deep Deterministic Policy Gradient (DDPG) framework to multi-robot systems. A similar case applies to Proximal Policy Optimization (PPO) algorithm and its generalization MAPPO [12]. While these approaches might be concerned with state dimensionality during centralized training, recent advances, such as Value-Decomposition Networks (VDN), can be leveraged to decompose the joint value function into individual value functions for each robot [13]. Building on this, QMIX further extends the framework, allowing for a more complex, state-dependent mixing of individual robot’s value functions to learn coordinated behaviors [14].

These CTDE approaches often rely on end-to-end learning, which cannot leverage the hierarchical structures of robot actions considered in this paper. In addition, their performance and training efficiency may significantly degrade [15] if each robot’s local observation covers only parts of the state space. Such local observation leads to a Decentralized Markov Decision Process (Dec-MDP), whose complexity is NEXP-complete [16]. In this case, even a slight reduction in the state/action space can have a huge impact on the overall computational complexity.

Regarding state/action space reduction, bi-level optimization is a hierarchical mathematical formulation where the solution of one optimization task is restricted by the solution set mapping of another task [8]. In recent years, this technique has been incorporated with various machine learning methods for nested decision-making, including multi-task meta-learning [17], neural architecture search [18], adversarial learning [19], and deep reinforcement learning [20]. The applications of these bi-level learning approaches span economics, management, optimal control, systems engineering, and resource allocation problems [21, 22, 23, 24, 25], with a comprehensive review by Liu et al. [8]. Corresponding to the scope of this paper, when solving multi-robot coordination problems, bi-level decomposition has been introduced  [10, 26] for actor-critic MARL to reduce the training burden of each level, thus improving the training efficiency and convergence. Le et al. [27] uses latent variables to introduce a mechanism similar to bi-level optimization that can significantly improve the performance of multi-agent imitation learning.

Nevertheless, a commonality among the mentioned works is the assumption that robots (agents) can access complete state information of the system. In cases where each robot has only partial information, the incomplete information can lead to a mismatch between the optimal solutions on the two levels. This challenge has motivated our work to incorporate an alignment penalty in order to generalize the bi-level optimization concept under CTDE, taking into account robots’ local observations.

A regular centralized Markov Decision Process (MDP) can be defined by a tuple $(\mathcal{S},\mathcal{A},\mathcal{T},\gamma,{R})$, including state, action, state transition, discount factor, and reward. The goal is to learn a policy $\pi:\mathcal{S}\to\mathcal{A}$ to maximize the expected cumulative reward over the task horizon $T$, i.e.,

where $\bm{a}_{t}\in\mathcal{A}$ and $\bm{s}_{t}\in\mathcal{S}$ are the action and state of the system at each step.

Let’s assume the actions of the system can be decomposed as $\bm{a}_{t}=\{{\bm{x}}_{t},{\bm{y}}_{t}\}\in{\mathcal{X}}\times{\mathcal{Y}}$, and the system’s state transition depends only on action ${\bm{x}}_{t}$ such that $\mathcal{T}:\mathcal{S}\times{\mathcal{X}}\to\mathcal{S}$:

However, the reward function depends on both actions:

If the structure of problem (1) satisfies (2) and (3), it can be formulated into a bi-level problem:

In this paper, we make the following assumption:

The assumption can be justified by the fact that (4a) is a planning problem involving state transitions and rewards for future $T$ steps, while (4b) only involves a one-step reward.

Under Assumption 1, for the lower level problem (4b), the optimal ${\bm{y}}^{*}_{t}$ is solvable from $f:\mathcal{S}\times{\mathcal{X}}\to{\mathcal{Y}}$, based on the current $\bm{s}_{t}$ and the choice of ${\bm{x}}_{t}$. Bringing this solution back to the upper level (4a), we only need to solve a reduced-dimension MDP defined by $(\mathcal{S},{\mathcal{X}},\mathcal{T},\gamma,{R})$, to obtain a policy $\widehat{\pi}:\mathcal{S}\to{\mathcal{X}}$ that generates action ${\bm{x}}_{t}$. During implementation, the policy $\pi$ in problem (1) can be a composition of $\pi=\widehat{\pi}\circ f$. We learn the policy $\widehat{\pi}$ to generate ${\bm{x}}_{t}$ from ${\bm{s}}_{t}$, then use $f$ to generate ${\bm{y}}_{t}$ from $\{{\bm{s}}_{t},{\bm{x}}_{t}\}$. Fig. 2 provides a visualization of this bi-level mechanism builds on actor-critic reinforcement leaning.

In this paper, we generalize the bi-level formulation into a multi-robot system with local observation. Consider a multi-robot system with a set of $\mathbf{n}=\{1,\cdots,n\}$ robots. Suppose the centralized actions and states in (1) are decomposed into each robot’s state and action as $\bm{s}_{t}=\{s^{1}_{t},\dots,s^{n}_{t}\}\in\mathcal{S}$ and $\bm{a}_{t}=\{a^{1}_{t},\dots,a^{n}_{t}\}\in\mathcal{A}$. Assume each robot’s action can be further written as $a^{i}_{t}=\{{x}^{i}_{t},{y}^{i}_{t}\}$, where the action ${x}^{i}_{t}$ determines the robot’s local state update ${s}^{i}_{t+1}=\mathcal{T}^{i}({s}^{i}_{t},{x}^{i}_{t})$. The multi-robot system shares a global reward determined by all robots’ states, and their two actions: ${R}_{t}=U({\bm{s}}_{t},{\bm{x}}_{t},{\bm{y}}_{t})$.

For many real-world applications, the deployment of a multi-robot system faces communication and sensing constraints, where each agent may only have access to the states of its neighbors through a network, denoted by set $\mathcal{N}_{i}$. The neighbors’ states are a subset of the full system state, denoted by ${s}^{\mathcal{N}_{i}}_{t}\subsetneq{\bm{s}}_{t}$. Such local observation turns the problem into a Dec-MDP. Under this constraint, the problem of interest in this paper is to learn a local policy $\pi^{i}$ for each agent such that:

While solving Dec-MDP problems is known to be difficult [16], in this paper, we will generalize the idea of bi-level optimization under the scheme of CTDE and use action space reduction to alleviate the challenges in high-dimensional parameter tuning for MARL. Note that such a generalization is non-trivial and the main challenge lies in the local observation and local decision-making of each robot using incomplete information. As a consequence, compared with the centralized case, the robots cannot solve an optimization problem like (4b) to directly determine their secondary action $y^{i}_{t}$.

The alignment of the problem with (2) and (3) allows it to be reformulated into (6) and then solved by our Bi-CL.

Fig. 5 illustrates the RL-Reward curves and T-Reward for different $c_{t}$ by setting $c=0,c=1,c=5,c=10,c=50$, all with $\beta=2e-3$ and $h=3000$. This, together with (7), makes $c_{k}$ gradually increase in an ‘S’ shape from $0$ to $c$. Upon examining the results, it is evident that the R-Gap is large when $c$ is small, and the gap diminishes as $c$ increases. This verifies the effectiveness of the proposed alignment penalty term in (6c), as it motivates the policy $\widehat{\pi}_{t}^{i}$ to be tuned using a ${y_{t}^{i}}^{\star}$ that is closer to the output of $\eta_{t}^{i}$. It is also important to note that although the MARL training reward appears high when $c$ is small, this is misleading and unattainable in decentralized execution due to the mismatch between $\widehat{\pi}_{t}^{i}$ and $\eta_{t}^{i}$. The attainable reward (T-Reward) is much lower with smaller $c$.

Finally, we observe in the last plot of Fig. 5 that a very large $c=50$ may negatively impact the training performance. This is due to two reasons. First, as we discussed in the algorithm development, larger $c_{k}$ reduces the training efficiency of the imitation learning part of the algorithm. This is reflected by the lower values on both RL-Reward and T-Reward. Second, since $c_{k}$ impacts the computation of ${y_{t}^{i}}^{\star}$ during the training process, changing it too aggressively will lead to instability in training. This is evidenced by the middle part of the curve, where increased osculation is observed.

The same test is performed under various environment setups and the results are shown in Table I. Here, Na_Mb means the environment has $a$ robots and $b$ adversaries. Especially, in N5_M4*, each robot further reduces the number of other robots’s states it can observe. The results in the table align with our above analysis. In all cases where $c_{k}=c=0$, i.e., without alignment penalty, the performance is the worst. The R-Gap generally reduces when $c$ grows large. Since T-Reward is the core metric for performance, the best result mostly occurs at $c=10$ with only one exception and the difference is small. Furthermore, to read the table column-wise, environments with the same number of adversaries, i.e., M4 are comparable. From N4_M4 to N5_M4, the T-Rewards generally increase because more coordination behaviors can be generated. When comparing N5_M4* and N5_M4, the T-Rewards generally decrease due to the reduced sensing distances of the robots. This also leads to a larger R-Gap when $c=0$, necessitating the introduced alignment penalty.

The alignment of the problem with (2) and (3) allows it to be reformulated into (6) and then solved by our Bi-CL.

The comparison results are presented in Table II, which verifies the effectiveness of the Bi-CL algorithm for learning coordinated actions among robots within graph-based coordination tasks. Despite variations in the number of robots, graph nodes, or densities of the graph edges, the proposed Bi-CL algorithm delivers comparable results to the baseline algorithms while requiring fewer training episodes to converge. By observing the column of MAPPO, the results tend to fall below those of other methods under conditions of increased environmental complexity. This suggests that policy gradient approaches may only learn a sub-optimal policy solution in these cases. The QMIX method is more robust in terms of optimality, however, it generally requires more training episodes to converge. In comparison, the proposed Bi-CL method enjoys much more efficient convergence properties. This improvement is mainly due to (i) the reduction of the action space for reinforcement learning, and (ii) the use of optimization (6c) to jump-start the training.