Opponent modeling with trajectory representation clustering

2.1. Opponent modeling

Opponent modeling stems from a naive motivation that infers the opponent's policy and behavior through the information about the opponent to obtain a higher reward for itself. Early opponent modeling work ^{[25, 26]} mainly focused on simple game scenarios where the opponent policy is fixed. With the development of deep reinforcement learning, scholars have begun to apply the idea of opponent modeling in more complex environments and settings. The following introduces the opponent modeling work in recent years in terms of explicit modeling and implicit modeling.

2.2. Contrastive learning

Contrastive learning, as the most popular self-supervised learning algorithm in recent years, is different from generative encoding algorithms. Contrastive learning focuses on learning common features between similar instances and distinguishing differences between non-similar instances. van den Oord et al. first proposed InfoNCE loss, which encodes time-series data. By separating positive and negative samples, it can extract data-specific representations ^[21]. Based on similar ideas, He et al. achieved high performance in the field of image classification, by improving the similarity between the query vector and its corresponding key vector while reducing the similarity with the key vector of other images ^[23]. From the perspective of data augmentation, Chen et al. performed random cropping, inversion, grayscale, and other transformations on the image and extracted the invariant representation behind the image through contrastive learning ^[22]. The subsequent series of works ^[29-31] continued with a series of improvements, and the performance on some tasks is close to that of supervised learning algorithms.

From the above works, we can see that most of the previous opponent modeling work is to additionally input representations into neural networks for policy training. This paper provides another perspective on training a general policy to respond to various opponents by balancing the data in the replay buffer interacting with different opponent policies. Through the powerful representation extraction ability of contrastive learning, we distinguish various opponent policies at the representation level. It is worth noting that we only additionally use opponent observations, which is a looser setting compared to other work in multi-agent settings.

3.1. Problem formulation

We describe the problem as a partially-observable stochastic game (POSG) ^[32] composed of a finite set $$ \mathcal{I}=\{1, 2, \dots, N\} $$, a state space $$ \mathcal{S} $$, the joint action space $$ \mathcal{A}=\mathcal{A}^{1} \times \ldots \times \mathcal{A}^{N} $$, the joint observation space $$ \mathcal{O}=\mathcal{O}^{1} \times \ldots \times \mathcal{O}^{N} $$, a transition function $$ \mathcal{P}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1] $$ denoting the transition probabilities between two states when given a joint action, and a reward function $$ \mathcal{R}_{i}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R} $$ for each agent $$ i\in \mathcal{I} $$. Since we only focus on the performance of the agent under our control, we denote this agent by 1 and other agents are denoted by $$ -1 $$ with joint observation $$ o^{-1} $$ and joint action $$ a^{-1} $$.

We design a set of $$ K $$ fixed policies for agent $$ -1 $$$$ \Pi=\left\{\pi^{-1, k} \mid k=1, \ldots, K\right\} $$, which can be rule-based (artificial) or network (pre-trained). Assume that an opponent policy $$ \pi^w $$ is a probability distribution on $$ \Pi $$, $$ w \in \Delta(\Pi) $$, which means at the beginning of each episode, the agent $$ -1 $$ samples a policy from $$ \Pi $$ with probability distribution $$ w $$ and executes this policy throughout the episode. Different from the setting of only switching between fixed policies in previous work, we allow more complex opponent policy changes, making the setting looser and more general.

Ideally, our goal is to find a general response policy $$ \pi_{\theta} $$ parameterized by $$ \theta $$, which can maximize the reward of agent 1 against each opponent policy $$ \pi^w $$. However, considering the reality, we maximize the minimum reward of $$ \pi_{\theta} $$ against $$ \pi^w $$:

where $$ r_{t}^{1} $$ is the reward of agent 1 at step $$ t $$ after performing the action $$ a_{t}^{1} $$ determined by $$ \pi_\theta $$, $$ H $$ is the horizon of episode, and $$ \gamma \in(0, 1) $$ is a discount factor. It is also important to note that at any time the agent 1 knows neither the policy type $$ k $$ of opponent nor the distribution $$ w $$. This gives us the motivation to infer the type of opponent policy.

3.2. Representation extraction module

Different from previous opponent modeling methods that model opponent policies, we use a contrastive learning approach to self-supervised distinguish trajectories against different opponent policies, so that we only use the opponent's observations. We denote trajectory as $$ \tau=\{o^1_t, o^{-1}_t\}_{t=0}^{t=H-1} $$ where $$ o^1_t $$ and $$ o^{-1}_t $$ are the observations of agent 1 and agent $$ -1 $$ at step t, respectively. Given a set of trajectories $$ \mathcal{T}=\{\tau_1, \tau_2, \dots, \tau_M\} $$, the representation of each trajectory is self-supervised extracted by the CPC ^[21] algorithm.

Figure 1 shows the architecture of the contrastive predictive coding algorithm. First, we encode the observations by a multi-layer perceptron (MLP) to get a sequence of latent representation $$ z_t $$:

Figure 1. Overview of contrastive predictive coding (CPC), a representation extraction algorithm by contrasting positive and negative samples.The context $$ c_t $$ and subsequent state embeddings $$ \{z_{t+1}, z_{t+2}, \dots, z_{H-1}\} $$ are regarded as positive samples when they come from the same trajectory; otherwise, they are regarded as negative samples. By increasing the similarity between positive samples and reducing the similarity between negative samples, we obtain trajectory representations to distinguish different opponent policies.

Then, use a gated recurrent unit (GRU) to extract the context information for the first t steps:

In addition, we also need to define the similarity function $$ f_k $$. To unify the dimensions, we use a bilinear product function:

where $$ k=1, \dots, H-t-1 $$ and $$ W_k $$ is different for each k. For given set of trajectory $$ \mathcal{T}=\{\tau_1, \tau_2, \dots, \tau_M\} $$, $$ c_t^{i} $$ and $$ z_{t+k}^i $$ are calculated from $$ \tau_i $$. Since representations extracted from the same trajectory have similarities, we maximize $$ f_k(z_{t+k}^i, c_t^j) $$ when $$ i=j $$ and minimize $$ f_k(z_{t+k}^i, c_t^j) $$ when $$ i\neq j $$. The InfoNCE loss is:

where $$ t $$ is random sampling within a suitable range, M is the size of the trajectory set (batch size), and H is the horizon. Optimizing this loss will extract a unique representation of each trajectory that is different from others.

As described above, we self-supervise the extraction of policy representations from trajectories through contrastive learning, which can discriminate different opponent policies in representation space. Especially the contrast between positive and negative samples makes the representation highlight the differences between trajectories, which is beneficial for subsequent clustering operations.

3.3. Experience replay module

In Section 3.2, we introduce how to extract the representations of opponent policies from the trajectories that interact with opponents. Different from the previous approaches of directly using representations to assist training, we focus on another aspect, that is, the impact of non-stationary opponents on the experience replay. Experience replay is a commonly used method in reinforcement learning whose purpose is to improve the sample efficiency. When the replay buffer is full, the data are usually processed in a first-in, first-out (FIFO) manner. When the opponent uses a fixed policy, the environment can be treated as a deterministic MDP, and FIFO is feasible. When the opponent is non-stationary, the replay buffer will pass through data that interacts with different types of opponent policies. The decrease in the proportion of certain types of data will affect the effectiveness against such an opponent, and the loss of old data may lead to the forgetting of learned strategies. Therefore, we design new data in and out, a mechanism to keep as many types of trajectory data as possible in the replay buffer.

We cluster the trajectory data in the replay buffer in the representation space, and, for the representation, $$ z_{: H}^i $$ and $$ z_{: H}^j $$ of the trajectories $$ \tau_i $$ and $$ \tau_j $$, we use the average Euclidean distance to measure the distance between them:

For all trajectories in the replay buffer, we can calculate the representation distance matrix $$ D $$ by Equation (6). Additionally, the truncation method can be used for trajectory representations of different lengths, or the dynamic time warping (DTW) can be used instead of the Euclidean distance.

Since the number of opponent policies is unknown, some clustering methods such as K-means are not suitable for use. We use agglomerative clustering to distinguish trajectory representations in the replay buffer, which is implemented in the standard algorithm library scikit-learn, and the clustering threshold is set as the average distance of all trajectory representations. Then, the labels of the trajectories that interact with the opponents are obtained in a self-supervised manner.

To balance the proportion of different types of data in the replay buffer, we no longer pop the oldest data when the replay buffer is full, but pop the oldest data from the largest class based on the clustering results. This ensures the dynamic balance of various types of data to a certain extent. Even if a certain type of opponent policy has a very low probability of appearing in a period, the data interacting with it can maintain a certain proportion in the replay buffer, thereby avoiding policy forgetting. However, this approach will lead to some useless old data existing in the replay buffer for a long time, reducing the training effect of reinforcement learning. We introduce a probability threshold $$ \rho $$, where the replay buffer pops the oldest data from the largest class with the probability of $$ \rho $$ and pops the oldest data from the entire replay buffer with the probability of $$ 1-\rho $$. This allows the data that hinder training to be popped. In this paper, we set $$ \rho=0.9 $$.

3.4. Combine with reinforcement learning

This section describes the overall algorithm flow in combination with the classic reinforcement learning algorithm soft actor–critic (SAC) whose optimization goal is:

where $$ \mathcal{H}\left(\pi\left(\cdot \mid \mathbf{s}_{t}\right)\right) $$ is the additional policy entropy added to encourage exploration and $$ \alpha $$ is the temperature parameter determines the relative importance of the entropy term. However, our method can be combined with any off-policy reinforcement learning algorithm.

Since the training speed of representation learning is much faster than that of reinforcement learning, we set the training frequency $$ F_c $$ for it to balance their learning rate. In addition, this also considers that the flow of data in the replay buffer in the short term will not change the data distribution in it. Considering that the introduction of the clustering requires a large amount of extra computation, and the data that newly entered replay buffer will not be popped in the short term, we update the labels of trajectory representations by clustering every $$ F_l $$ episode.

The complete algorithm is described in Algorithm 1. The training of representation learning and reinforcement learning process alternately. Since the FIFO rule is still followed in the class, our method will not have too much influence on the training of reinforcement learning; at the same time, the diversity of the data in the replay buffer is guaranteed as much as possible, so that the policy forgetting caused by the non-stationary of the opponent policy is avoided.

4.1. Game description

Soccer is a classic competitive environment that has been used by many opponent modeling approaches ^{[11, 13]} to verify their performance. We extend the rules based on the classic soccer environment and design more complex rule-based opponent policies based on this. As shown in Figure 2, the environment is a 15 $$ \times $$ 15 grid world, and there are two goals on each end line. At the beginning of the episode, the two agents are in the center of their respective end lines with 0 energy, and one random agent holds the ball. Each agent has 13 optional actions, moving to any of the 12 grid points within a two-grid range around itself or staying in place, but moving 2 grids requires 2 energy. The agent with the ball recovers 0.5 energy per step, while the agent without the ball recovers 1 energy per step, and the upper limit of energy is 2. When both agents are about to enter the same grid, they stop in place and exchange the ball possession. When the agent dribbles the ball into the opponent's goal, it gets a +5 reward, while the opponent gets a $$ -5 $$ reward, and then ends this episode. If the interaction exceeds 50 steps, the episode will also be terminated and each agent will get 0 rewards. The position, energy, and ball possession are fed back to the agent as observation.

Figure 2. The configuration of soccer. The goal of each agent is to drive the ball into the opponent's goal.

The opponent policies are designed to be random policies based on given rules, which makes it more complex. Specifically, we design two base opponent policies $$ \pi_1^{-1} $$ and $$ \pi_2^{-1} $$ with different styles. $$ \pi_1^{-1} $$: Keep away from the opponent while attacking the upper goal when holding the ball, and get close to the opponent when not holding the ball. $$ \pi_2^{-1} $$: Keep away from the opponent while attacking the lower goal when holding the ball, and defend near its end line when not holding the ball. As described in Section 3.1, we define $$ w\in [0, 1] $$ as a class of opponent policies, and, at the beginning of the episode, the opponent chooses a policy from $$ \{\pi_1^{-1}, \pi_2^{-1}\} $$ with probability distribution $$ \{w, 1-w\} $$.

4.2. Non-stationary opponent

We make the opponent policy switch from $$ w=0.5 $$ to $$ w=0.05 $$ at step 100k to observe the performance of the agent training by different algorithms in a non-stationary environment. Figure 3a shows the comparison of the reward curves of our algorithm and three baselines against opponent policy $$ \pi_1^{-1} $$. In these baselines, vanilla SAC uses no opponent information and performs the worst. DRON uses the opponent's observation as an additional input, while DPIQN further uses the opponent's actions to obtain the representations of opponent policy to aid training. However, they both perform worse than our work due to a lack of consideration of data balance. Figure 3b shows the change in the proportion of interaction trajectories with opponent strategy $$ \pi_1^{-1} $$ in the replay buffer. It can be seen that, when the probability of an opponent policy decreases, only our method can maintain a relatively high proportion of the data obtained by interacting with it in the replay buffer. This improves responsiveness to such an opponent policy and avoids forgetting the learned policy.

Figure 3. (a) The average reward curve of interacting with opponent policy $$ \pi_1^{-1} $$; and (b) the proportion change curve of opponent $$ \pi_1^{-1} $$ trajectory in replay buffer.

To explain the impact of data ratio on policy forgetting in more detail, we make the opponent policy change from $$ w=0.5 $$ to $$ w=0, 0.02, 0.04, 0.06, 0.08, 0.1 $$ at step 100k and use SAC for training with the other conditions remaining the same. As shown in Figure 4, when a certain opponent policy appears very infrequently, a small proportional increase in the replay buffer can bring about higher performance improvement, but, for data that already exist in significant proportions, the impact of adjusting the data ratio is minimal. This also explains our motivation to balance the proportion of various data.

Figure 4. The average reward curve of interacting with opponent policy $$ \pi_1^{-1} $$ when $$ w $$ change from 0.5 to 0, 0.02, 0.04, 0.06, 0.08, and 0.1.

4.3. Analysis of clustering

In Section 4.2, we show the performance of the algorithm and analyze the rationale behind data balancing. In this section, from the perspective of policy representation, we analyze the clustering properties of the policy representations obtained by contrastive learning in the representation space. Figure 5 shows the visualization of trajectory encoding after dimensionality reduction by t-SNE. Self-supervised contrastive learning is not very accurate in distinguishing two types of opponent policies. Because policies may have similar parts, a type of policy can also be decomposed into several more refined sub-policies. Self-supervised learning of policy representations only with trajectory information can only be used for coarse clustering. However, our algorithm does not rely on extremely accurate trajectory clustering and strategy identification but balances the proportion of various trajectory data generally. This also makes the algorithm have certain robustness.

Figure 5. t-SNE projection of the embeddings in the soccer environment: (a) the two colors represent the two base opponent policies $$ \pi_1^{-1} $$ and $$ \pi_2^{-1} $$; and (b) the different colors represent the classes of trajectory representations encoded by the contrastive learning.

Authors' contributions

Designed and run experiments: Lv Y

Made substantial contributions to conception and design of the study: Zheng Y

Provided administrative, technical, and material support: Hao J

Availability of data and materials

Not applicable.

Financial support and sponsorship

None.

Conflicts of interest

All authors declared that they have no conflicts of interest to this work.

Ethical approval and consent to participate

Not applicable.

Consent for publication

Not applicable.

Copyright

© The Author(s) 2022.