# Combining inherent knowledge of vision-language models with unsupervised
domain adaptation through self-knowledge distillation

Thomas Westfechtel1, Dexuan Zhang1, Tatsuya Harada1,2
1The University of Tokyo 2RIKEN
Tokyo, Japan
<EMAIL_ADDRESS>
###### Abstract

Unsupervised domain adaptation (UDA) tries to overcome the tedious work of
labeling data by leveraging a labeled source dataset and transferring its
knowledge to a similar but different target dataset. On the other hand,
current vision-language models exhibit astonishing zero-shot prediction
capabilities. In this work, we combine knowledge gained through UDA with the
inherent knowledge of vision-language models. In a first step, we generate the
zero-shot predictions of the source and target dataset using the vision-
language model. Since zero-shot predictions usually exhibit a large entropy,
meaning that the class probabilities are rather evenly distributed, we first
adjust the distribution to accentuate the winning probabilities. This is done
using both source and target data to keep the relative confidence between
source and target data. We then employ a conventional DA method, to gain the
knowledge from the source dataset, in combination with self-knowledge
distillation, to maintain the inherent knowledge of the vision-language model.
We further combine our method with a gradual source domain expansion strategy
(GSDE) and show that this strategy can also benefit by including zero-shot
predictions. We conduct experiments and ablation studies on three benchmarks
(OfficeHome, VisDA, and DomainNet) and outperform state-of-the-art methods. We
further show in ablation studies the contributions of different parts of our
algorithm.

##  1 Introduction

Figure 1: Accuracy on the OfficeHome dataset for unsupervised domain
adaptation (blue), CLIP zero-shot predictions (green), and our combined
version (black) integrating zero-shot predictions into UDA. In this work, we
present a way to combine the knowledge from vision-language models with
knowledge transferred via UDA from a source domain. It can be seen that the
performance significantly improves.

Deep neural networks have advanced the field of computer vision largely.
However large amount of labeled data is required to train these networks. One
method to overcome the need for tedious labeling is unsupervised domain
adaptation, where knowledge from a similar but distinct labeled source dataset
is transferred to an unlabeled target dataset.

On the other hand, vision-language models exhibit remarkable zero-shot
prediction accuracy, even without any task-specific training data. It may even
seem that through generating larger foundation models the need for domain
adaptation fades. For example, on the DomainNet dataset, current vision-
language models outperform state-of-the-art domain adaptation methods while
only using zero-shot predictions.

In this work, we argue that rather than seeing these two methods as competing,
combining the strengths of both of them achieves even better results. We
combine the inherent knowledge of the vision-language models with the
knowledge transferred from a source dataset through domain adaptation.

To maintain the inherent knowledge of the vision-language model we employ a
knowledge distillation loss using the zero-shot predictions. However, since
the zero-shot predictions usually exhibit a large entropy, meaning that the
class probabilities are rather evenly distributed, we first adjust the
distribution to accentuate the winning probability. To keep the relative
confidence of the zero-shot prediction between source and target data we do
this step for source and target data in a combined way. We use the knowledge
distillation loss, to maintain the inherent knowledge, in combination with a
conventional unsupervised domain adaptation method to benefit from the
knowledge of the source dataset. As can be seen in Fig. 1 combining the two
knowledge sources significantly increases the performance. We further combine
our method with a gradual source domain expansion strategy (GSDE) [30] and
show that this strategy can also benefit by including zero-shot predictions.

Our main contributions are:

  * •

We introduce self-knowledge distillation to maintain inherent knowledge of
vision-language models using recalibrated zero-shot predictions and combine
them with a conventional UDA method.

  * •

We further employ a gradual source domain expansion GSDE) and enhance the
strategy by introducing zero-shot predictions into it.

  * •

We show the effectiveness of our algorithm on three datasets (Office-Home,
VisDA, and DomainNet) and further evaluate the method in various ablation
studies.

  * •

We show that the method is applicable for both CNN-based and transformer-based
backbones.

Figure 2: Process flow of our algorithm. In a first step, the zero-shot
predictions of source $\mathcal{D}_{s}$ and target $\mathcal{D}_{t}$ dataset
are estimated. The zero-shot distributions are calibrated jointly to
accentuate the winning probability. The network is trained using a
classification loss $L_{CE}$ for the source data, a knowledge distillation
loss employing the shifted zero-shot predictions $\tilde{y}_{o}$, and an
adversarial adaptation loss $L_{DA}$. We further employ strongly augmented
versions of source and target data as input. Since we do not differentiate
between weakly and strongly augmented versions for the losses, their paths are
combined after the visual encoder.

##  2 Related works

###  2.1 Unsupervised domain adaptation

The goal of unsupervised domain adaptation is to overcome the domain shift
between the source and the target dataset. Surveys for this task can be found
in [41], [38]. One approach is to align the feature space distributions
between the two datasets. Domain-adversarial neural network (DANN) [5]
introduces an adversarial approach to achieve this. A domain classifier is
trained to distinguish the feature space of source and target samples. The
work introduced a gradient reversal layer. This layer inverts the gradients
and thereby inverts the training objective, meaning that the backbone is
trained to generate features that are indistinguishable for the domain
classifier, generating so-called domain invariant features. BIWAA introduces a
feature re-weighting approach based on their contribution to the classifier.
CDAN [15] extended DANN by multilinear conditioning the domain classifier with
the classifier predictions. Moving semantic transfer network [32] introduced a
moving semantic loss.

Another approach employs information maximization or entropy minimization to
generate more accurate target predictions. SHOT [14] exploits both information
maximization and self-supervised pseudo-labeling to increase the performance
of the target domain. SENTRY [21] uses prediction consistency among different
augmentations of an image to either minimize its entropy or maximize it in
case of inconsistent predictions.

Following the rise of vision transformers, approaches specially tailored for
these backbones have gained popularity. TVT [34] introduced a Transferability
Adaption Module that employs a patch-level domain discriminator to measure the
transferability of patch tokens, and injects learned transferability into the
multi-head self- attention block of a transformer. CDTrans [33] introduced a
triple-branch transformer framework with cross-attention between source and
target domains. PMTrans [40] introduced PatchMix which builds an intermediate
domain by mixing patches of source and target images. The mixing process uses
a learnable Beta distribution and attention-based scoring function to assign
label weights to each patch.

In our work, we employ CDAN [15] as our domain adaptation loss. While the
performance is neither state-of-the-art for CNN-based nor transformer-based
networks, it achieves reasonable performance for both architectures. [11] has
shown that many algorithms developed for CNN backbones underperform for
transformer-based backbones. On the other hand, most transformer-based
algorithms explicitly make use of the network structure and cannot be employed
for CNN-backbones.

###  2.2 Vision-language models

CLIP [22] introduced a contrastive learning strategy between text and image
pairs. It employs a text encoder and a visual encoder. Feature representations
of positive pairs are pushed together, while unrelated or negative pairs are
pushed apart. The usage of visual and language encoders enables zero-shot
prediction. The class labels are encoded via the language encoder and serve as
classifier. Usually, the class labels are combined with a pretext or ensemble
of pretexts such as ’A photo of a {object}.’ to enhance the performance, where
{object} is replaced with the respective classes. While CLIP collected the
training dataset by constructing an allowlist of high-frequency visual
concepts from Wikipedia, ALIGN [9] does not employ this step, but makes up for
it by using a much larger, though noisier, dataset. BASIC [20] further
increased the zero-shot prediction capabilities by further increasing data
size, model size, and batch size. LiT [36] employs a pre-trained image encoder
as visual backbone and aligns a text encoder to it. The vision encoder is
frozen during the alignment. DFN [4] investigates data filtering networks to
pool high-quality data from noisy curated web data.

In our work, we employ the CLIP pre-trained models due to their popularity. We
employ the seven ImageNet templates subset published on the CLIP Git Hub.

###  2.3 Domain adaptation for vision-language models

Surprisingly there has not been much research on combining domain adaptation
to vision-language models.

Few approaches make use of prompt learning [39]. This approach trains the
prompt’s context words for the text encoder with learnable vectors while the
encoder weights are frozen. DAPL [7] employs a prompt learning approach to
learn domain-agnostic context variables and domain-specific context variables
for unsupervised domain adaptation. This approach freezes the text and vision
encoder during training. AD-CLIP [25] introduces a prompt learning scheme that
entirely leverages the visual encoder of CLIP and introduces a small set of
learnable projector networks. MPA [2] takes a similar approach of prompt
learning for multi-source unsupervised domain adaptation. In a first step,
individual prompts are learned to minimize the domain gap through a
contrastive loss. Then, MPA employs an auto-encoding process and aligns the
learned prompts by maximizing the agreement of all the reconstructed prompts.
DALL-V [35] employs large language-vision models for the task of source-free
video domain adaptation. They distill the world prior and complementary source
model information into a student network tailored for the target. This
approach also freezes the vision encoder and only learns an adapter on top of
the vision encoder.

Unlike all of the above methods, we do not freeze the vision encoder during
the training. Particularly, we employ the zero-shot predictions and use them
in a knowledge distillation step to retain the knowledge of the language-
vision model. Furthermore, we combine our method with a conventional UDA
approach.

Table 1: Accuracy results on Office-Home dataset. The best results are displayed in bold and the runner-up results are underlined. Methods using a ResNet-50 backbone are on top, and methods using a transformer-based backbone are on the bottom. ZS indicates zero-shot results of CLIP. Method | A$\shortrightarrow$C | A$\shortrightarrow$P | A$\shortrightarrow$R | C$\shortrightarrow$A | C$\shortrightarrow$P | C$\shortrightarrow$R | P$\shortrightarrow$A | P$\shortrightarrow$C | P$\shortrightarrow$R | R$\shortrightarrow$A | R$\shortrightarrow$C | R$\shortrightarrow$P | Avg
---|---|---|---|---|---|---|---|---|---|---|---|---|---
CDAN [15] | 50.7 | 70.6 | 76.0 | 57.6 | 70.0 | 70.0 | 57.4 | 50.9 | 77.3 | 70.9 | 56.7 | 81.6 | 65.8
SRDC [27] | 52.3 | 76.3 | 81.0 | 69.5 | 76.2 | 78.0 | 68.7 | 53.8 | 81.7 | 76.3 | 57.1 | 85.0 | 71.3
BIWAA-I [29] | 56.3 | 78.4 | 81.2 | 68.0 | 74.5 | 75.7 | 67.9 | 56.1 | 81.2 | 75.2 | 60.1 | 83.8 | 71.5
Sentry [21] | 61.8 | 77.4 | 80.1 | 66.3 | 71.6 | 74.7 | 66.8 | 63.0 | 80.9 | 74.0 | 66.3 | 84.1 | 72.2
GSDE [30] | 57.8 | 80.2 | 81.9 | 71.3 | 78.9 | 80.5 | 67.4 | 57.2 | 84.0 | 76.1 | 62.5 | 85.7 | 73.6
PCL [12] | 60.8 | 79.8 | 81.6 | 70.1 | 78.9 | 78.9 | 69.9 | 60.7 | 83.3 | 77.1 | 66.4 | 85.9 | 74.5
ZS [22] | 48.5 | 81.2 | 83.5 | 72.6 | 81.2 | 83.5 | 72.6 | 48.5 | 83.5 | 72.6 | 48.5 | 81.2 | 71.5
SKD (Ours) | 61.6 | 86.8 | 86.7 | 78.0 | 87.4 | 86.8 | 77.3 | 61.0 | 87.1 | 79.6 | 64.1 | 88.9 | 78.8
CDAN [15] | 62.6 | 82.9 | 87.2 | 79.2 | 84.9 | 87.1 | 77.9 | 63.3 | 88.7 | 83.1 | 63.5 | 90.8 | 79.3
TVT [34] | 74.9 | 86.8 | 89.5 | 82.8 | 88.0 | 88.3 | 79.8 | 71.9 | 90.1 | 85.5 | 74.6 | 90.6 | 83.6
CDTrans [33] | 68.8 | 85.0 | 86.9 | 81.5 | 87.1 | 87.3 | 79.6 | 63.3 | 88.2 | 82.0 | 66.0 | 90.6 | 80.5
SDAT [23] | 70.8 | 87.0 | 90.5 | 85.2 | 87.3 | 89.7 | 84.1 | 70.7 | 90.6 | 88.3 | 75.5 | 92.1 | 84.3
SSRT [26] | 75.2 | 89.0 | 91.1 | 85.1 | 88.3 | 89.9 | 85.0 | 74.2 | 91.2 | 85.7 | 78.6 | 91.8 | 85.4
PMTrans [40] | 81.3 | 92.9 | 92.8 | 88.4 | 93.4 | 93.2 | 87.9 | 80.4 | 93.0 | 89.0 | 80.9 | 94.8 | 89.0
ZS [22] | 66.8 | 89.1 | 89.7 | 83.3 | 89.1 | 89.7 | 83.3 | 66.8 | 89.7 | 83.3 | 66.8 | 89.1 | 82.2
SKD (Ours) | 79.6 | 93.7 | 92.7 | 89.5 | 93.7 | 92.9 | 89.1 | 81.1 | 92.6 | 90.2 | 81.6 | 94.2 | 89.2

##  3 Methodology

In unsupervised domain adaptation, the goal is to transfer knowledge from a
source dataset $\mathcal{D}_{s}$ consisting of $n_{s}$ labeled images
$\mathcal{D}_{s}={(x_{i,s},y_{i,s})}_{i=1}^{n_{s}}$ to an unlabeled target
dataset $\mathcal{D}_{t}$ containing $n_{t}$ unlabeled data
$\mathcal{D}_{t}={(x_{i,t})}_{i=1}^{n_{t}}$. In this work we focus on
combining the inherent knowledge of vision-language models with the knowledge
gained from the knowledge transfer of the source domain, meaning we further
have access to the zero-shot predictions $y_{o}$ for each sample.

For the knowledge transfer from the source to the target domain, we employ the
widely established adversarial domain adaptation method CDAN as it was shown
to be effective for both convolutional- and transformer-based network
architectures [11].

To preserve the inherent knowledge of the vision-language model we employ a
knowledge distillation loss [8] using the zero-shot predictions. However,
since the zero-shot predictions exhibit a relatively wide spread of
probabilities among the classes (see Fig. 3), we first adjust the distribution
to accentuate the winning probabilities, so that they are more informative for
the knowledge distillation loss. The process flow of our algorithm can be seen
in Fig. 2

We further employ data augmentation and a gradual source domain expansion
strategy to further boost the performance.

For a single run, we use the three losses:

$L=L_{CE}+L_{KD}+L_{AD}$ (1)

where $L_{CE}$ is the classification loss for the source data, $L_{KD}$ is the
knowledge distillation loss, and $L_{AD}$ is the adversarial adaptation loss.
$L_{KD}$ and $L_{AD}$ are calculated for both source and target data. We
further employ a strongly augmented version of source and target data, which
are handled in the same way as the weakly augmented versions.

###  3.1 Knowledge distillation loss

Vision-language models already achieve an incredible zero-shot accuracy for
unseen data. To preserve this knowledge we employ a knowledge distillation
loss. However, since the predictions are rather evenly spread among all
classes, we adjust the distribution (from $y_{o}$ to
$\tilde{y}_{o}=\alpha\cdot y_{o}$) before employing them in the KD-loss (see
Fig. 3). In a normal KD setting, the teacher’s winning prediction score
usually tends to approach a one-hot vector. The goal is to mimic this
distribution while maintaining the relative prediction probabilities. To
accomplish that we estimate a factor $\alpha$ so that the mean winning
probability equals to $\tau$. We employ a value of $\tau=0.9$ in our
experiments. In the estimation, we equally factor the source and target domain
to further maintain the relative prediction confidence between the two
domains.

$\frac{1}{2n_{s}}\sum_{n_{s}}\max(\sigma(y_{o,i,s}\cdot\alpha))+\frac{1}{2n_{t}}\sum_{n_{t}}\max(\sigma(y_{o,i,t}\cdot\alpha))=\tau$
(2)

We then employ the shifted zero-shot predictions for the knowledge
distillation loss:

$L_{KD}=D_{KL}(\tilde{y}_{o}||y)$ (3)

where $D_{KL}$ is the Kullback-Leibler divergence loss, and $y$ is the output
of the classifier of our network.

Figure 3: Distribution of winning probabilities of zero-shot predictions $y_{o}$ and their adjusted distribution $\tilde{y}_{o}$ for the clipart and real domain of OfficeHome. While the zero-shot predictions have low winning probabilities, the adjusted distribution resembles much more one-hot vectors, while maintaining their relative probabilities, as can be seen from the long tail of low winning probabilities. Table 2: Accuracy results on VisDA dataset. The best results are displayed in bold and the runner-up results are underlined. Methods using a ResNet-101 backbone are on top, and methods using a transformer-based backbone are on the bottom. ZS indicates zero-shot results of CLIP. Method | plane | bcycl | bus | car | horse | knife | mcycl | person | plant | sktbrd | train | truck | Avg
---|---|---|---|---|---|---|---|---|---|---|---|---|---
CDAN [15] | 85.2 | 66.9 | 83.0 | 50.8 | 84.2 | 74.9 | 88.1 | 74.5 | 83.4 | 76.0 | 81.9 | 38.0 | 73.9
DWL [31] | 90.7 | 80.2 | 86.1 | 67.6 | 92.4 | 81.5 | 86.8 | 78.1 | 90.6 | 57.1 | 85.6 | 28.7 | 77.1
CGDM [3] | 93.4 | 82.7 | 73.2 | 68.4 | 92.9 | 94.5 | 88.7 | 82.1 | 93.4 | 82.5 | 86.8 | 49.2 | 82.3
STAR [16] | 95.0 | 84.0 | 84.6 | 73.0 | 91.6 | 91.8 | 85.9 | 78.4 | 94.4 | 84.7 | 87.0 | 42.2 | 82.7
CAN [10] | 97.0 | 87.2 | 82.5 | 74.3 | 97.8 | 96.2 | 90.8 | 80.7 | 96.6 | 96.3 | 87.5 | 59.9 | 87.2
CoVi [17] | 96.8 | 85.6 | 88.9 | 88.6 | 97.8 | 93.4 | 91.9 | 87.6 | 96.0 | 93.8 | 93.6 | 48.1 | 88.5
ZS [22] | 98.0 | 83.3 | 90.8 | 65.9 | 97.8 | 83.0 | 93.4 | 67.7 | 85.2 | 90.0 | 94.9 | 66.4 | 84.7
SKD (Ours) | 98.8 | 87.8 | 92.0 | 72.0 | 98.7 | 93.4 | 94.8 | 75.1 | 92.5 | 96.0 | 95.9 | 72.0 | 89.1
TVT [34] | 82.9 | 85.6 | 77.5 | 60.5 | 93.6 | 98.2 | 89.4 | 76.4 | 93.6 | 92.0 | 91.7 | 55.7 | 83.1
SHOT [14] | 99.5 | 91.8 | 88.7 | 65.1 | 98.6 | 98.0 | 96.0 | 66.1 | 95.1 | 98.9 | 96.8 | 52.4 | 87.3
PMTrans [40] | 99.4 | 88.3 | 88.1 | 78.9 | 98.8 | 98.3 | 95.8 | 70.3 | 94.6 | 98.3 | 96.3 | 48.5 | 88.0
SSRT [26] | 98.9 | 87.6 | 89.1 | 84.8 | 98.3 | 98.7 | 96.3 | 81.1 | 94.8 | 97.9 | 94.5 | 43.1 | 88.8
AdaCon [1] | 99.5 | 94.2 | 91.2 | 83.7 | 98.9 | 97.7 | 96.8 | 71.5 | 96.0 | 98.7 | 97.9 | 45.0 | 89.2
DePT-D [6] | 99.4 | 93.8 | 94.4 | 87.5 | 99.4 | 98.0 | 96.7 | 74.3 | 98.4 | 98.5 | 96.6 | 51.0 | 90.7
ZS [22] | 99.3 | 91.5 | 92.9 | 71.0 | 99.4 | 92.7 | 94.4 | 75.6 | 84.7 | 97.4 | 95.5 | 69.0 | 88.6
SKD (Ours) | 99.6 | 95.2 | 94.3 | 74.5 | 99.6 | 98.0 | 95.9 | 79.8 | 89.8 | 99.2 | 96.6 | 71.8 | 91.2

###  3.2 Adversarial loss

We employ conditional adversarial domain adaptation loss CDAN:

$L_{AD}=L_{BCE}(G_{d}((f_{i}\otimes p_{i}),d_{i}))$ (4)

where $G_{d}$ is the domain classification network. $f_{i}$ are the features
of sample $i$, $p_{i}$ the class probabilities and $d_{i}$ the domain label.
CDAN employs a gradient reversal layer to inverse the training objective. This
means that while the domain classifier is trained to distinguish the domain
(source of target) of the respective sample, the objective of the feature
extractor is to extract features that are indistinguishable for the domain
classifier, thereby generating domain invariant features.

###  3.3 Gradual source domain expansion

We further employ the gradual source domain expansion strategy [30]. This
strategy trains the network iteratively $N$ times, each time resetting the
network weights. However, each new run $n$ employs the $\frac{n-1}{N}$ highest
scoring target samples with their respective pseudo-labels estimated from the
previous run as additional source data. To account for the additional
knowledge available from the zero-shot predictions, we slightly modify the
algorithm. While the original algorithm only considers the final predictions
of the previous run to choose the pseudo-source data, we combine the final
predictions with the zero-shot predictions:

$s(\hat{y})=p(y_{n-1})+\frac{1}{2^{n}}p(\tilde{y}_{o})$ (5)

where $s(\hat{y})$ is the scores of the samples for being chosen as pseudo-
source samples, and $p(y_{n-1})$ is the final predictions of the previous run.
As the performance increases over the runs, we decrease the influence of the
zero-shot predictions with every run. We use a value of $N=5$ in our
experiments.

###  3.4 Batch norm layer adjustment

The ResNet backbone employs batch norm layers. However, the distribution of
the pretraining data is vastly different than the data used for the domain
adaptation. The running average and mean change abruptly at the beginning of
the adaptation process, shifting the data out of the learned distribution and
resulting in failure. One solution would be to freeze the batch norm layers,
but this can result in exploding feature norms, making the training unstable.
In our work, we estimate the average and mean for the source and target data
for each batch norm layer and adjust the learnable parameters $\beta$ and
$\gamma$ so that the running mean and var equals that of our training data.

$\tilde{\beta}=\beta-(\mu_{p}-\mu_{c})*\frac{\gamma}{\sqrt{\sigma}_{p}})$ (6)

$\tilde{\gamma}=(\gamma*\frac{\sqrt{\sigma_{c}}}{\sqrt{\sigma_{p}}})$ (7)

where $\mu_{p}$ and $\sigma_{p}$ represent the running mean and variance of
the pre-trained model, and $\mu_{c}$ and $\sigma_{c}$ represent the estimated
mean and variance of the training data.

Table 3: Accuracy results on DomainNet dataset. ZS indicates zero-shot results
of CLIP.

MCD [24] | clp | inf | pnt | qdr | rel | skt | Avg | CGDM [3] | clp | inf | pnt | qdr | rel | skt | Avg | MDD [37] | clp | inf | pnt | qdr | rel | skt | Avg
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
clp | - | 15.4 | 25.5 | 3.3 | 44.6 | 31.2 | 24.0 | clp | - | 16.9 | 35.3 | 10.8 | 53.5 | 36.9 | 30.7 | clp | - | 20.5 | 40.7 | 6.2 | 52.5 | 42.1 | 32.4
inf | 24.1 | - | 24.0 | 1.6 | 35.2 | 19.7 | 20.9 | inf | 27.8 | - | 28.2 | 4.4 | 48.2 | 22.5 | 26.2 | inf | 33.0 | - | 33.8 | 2.6 | 46.2 | 24.5 | 28.0
pnt | 31.1 | 14.8 | - | 1.7 | 48.1 | 22.8 | 23.7 | pnt | 37.7 | 14.5 | - | 4.6 | 59.4 | 33.5 | 30.0 | pnt | 43.7 | 20.4 | - | 2.8 | 51.2 | 41.7 | 32.0
qdr | 8.5 | 2.1 | 4.6 | - | 7.9 | 7.1 | 6.0 | qdr | 14.9 | 1.5 | 6.2 | - | 10.9 | 10.2 | 8.7 | qdr | 18.4 | 3 | 8.1 | - | 12.9 | 11.8 | 10.8
rel | 39.4 | 17.8 | 41.2 | 1.5 | - | 25.2 | 25.0 | rel | 49.4 | 20.8 | 47.2 | 4.8 | - | 38.2 | 32.0 | rel | 52.8 | 21.6 | 47.8 | 4.2 | - | 41.2 | 33.5
skt | 37.3 | 12.6 | 27.2 | 4.1 | 34.5 | - | 23.1 | skt | 50.1 | 16.5 | 43.7 | 11.1 | 55.6 | - | 35.4 | skt | 54.3 | 17.5 | 43.1 | 5.7 | 54.2 | - | 35
Avg | 28.1 | 12.5 | 24.5 | 2.4 | 34.1 | 21.2 | 20.5 | Avg | 36 | 14 | 32.1 | 7.1 | 45.5 | 28.3 | 27.2 | Avg | 40.4 | 16.6 | 34.7 | 4.3 | 43.4 | 32.3 | 28.6
SCDA [13] | clp | inf | pnt | qdr | rel | skt | Avg | CDTrans [33] | clp | inf | pnt | qdr | rel | skt | Avg | SSRT [26] | clp | inf | pnt | qdr | rel | skt | Avg
clp | - | 18.6 | 39.3 | 5.1 | 55 | 44.1 | 32.4 | clp | - | 29.4 | 57.2 | 26 | 72.6 | 58.1 | 48.7 | clp | - | 33.8 | 60.2 | 19.4 | 75.8 | 59.8 | 49.8
inf | 29.6 | - | 34 | 1.4 | 46.3 | 25.4 | 27.3 | inf | 57 | - | 54.4 | 12.8 | 69.5 | 48.4 | 48.4 | inf | 55.5 | - | 54 | 9 | 68.2 | 44.7 | 46.3
pnt | 44.1 | 19 | - | 2.6 | 56.2 | 42 | 32.8 | pnt | 62.9 | 27.4 | - | 15.8 | 72.1 | 53.9 | 46.4 | pnt | 61.7 | 28.5 | - | 8.4 | 71.4 | 55.2 | 45
qdr | 30.0 | 4.9 | 15 | - | 25.4 | 19.8 | 19 | qdr | 44.6 | 8.9 | 29 | - | 42.6 | 28.5 | 30.7 | qdr | 42.5 | 8.8 | 24.2 | - | 37.6 | 33.6 | 29.3
rel | 54 | 22.5 | 51.9 | 2.3 | - | 42.5 | 34.6 | rel | 66.2 | 31 | 61.5 | 16.2 | - | 52.9 | 45.6 | rel | 69.9 | 37.1 | 66 | 10.1 | - | 58.9 | 48.4
skt | 55.6 | 18.5 | 44.7 | 6.4 | 53.2 | - | 35.7 | skt | 69 | 29.6 | 59 | 27.2 | 72.5 | - | 51.5 | skt | 70.6 | 32.8 | 62.2 | 21.7 | 73.2 | - | 52.1
Avg | 42.6 | 16.7 | 37 | 3.6 | 47.2 | 34.8 | 30.3 | Avg | 59.9 | 25.3 | 52.2 | 19.6 | 65.9 | 48.4 | 45.2 | Avg | 60 | 28.2 | 53.3 | 13.7 | 65.3 | 50.4 | 45.2
PMTrans [40] | clp | inf | pnt | qdr | rel | skt | Avg | ZS [22] | clp | inf | pnt | qdr | rel | skt | Avg | SKD (Ours) | clp | inf | pnt | qdr | rel | skt | Avg
clp | - | 34.2 | 62.7 | 32.5 | 79.3 | 63.7 | 54.5 | clp | - | 48.3 | 68.5 | 14.0 | 84.6 | 65.8 | 56.3 | clp | - | 52.7 | 72.0 | 36.3 | 85.1 | 71.5 | 63.5
inf | 67.4 | - | 61.1 | 22.2 | 78 | 57.6 | 57.3 | inf | 73.1 | - | 68.5 | 14.0 | 84.6 | 65.8 | 61.2 | inf | 78.5 | - | 72.2 | 30.4 | 85.0 | 69.5 | 67.1
pnt | 69.7 | 33.5 | - | 23.9 | 79.8 | 61.2 | 53.6 | pnt | 73.1 | 48.3 | - | 14.0 | 84.6 | 65.8 | 57.2 | pnt | 78.7 | 49.8 | - | 29.6 | 84.5 | 69.7 | 62.4
qdr | 54.6 | 17.4 | 38.9 | - | 49.5 | 41 | 40.3 | qdr | 73.1 | 48.3 | 68.5 | - | 84.6 | 65.8 | 68.1 | qdr | 70.7 | 22.9 | 50.9 | - | 82.4 | 62.3 | 57.8
rel | 74.1 | 35.3 | 70 | 25.4 | - | 61.1 | 53.2 | rel | 73.1 | 48.3 | 68.5 | 14.0 | - | 65.8 | 54.0 | rel | 80.3 | 53.5 | 74.2 | 30.2 | - | 71.1 | 61.9
skt | 73.8 | 33.0 | 62.6 | 30.9 | 77.5 | - | 55.6 | skt | 73.1 | 48.3 | 68.5 | 14.0 | 84.6 | - | 57.7 | skt | 81.0 | 52.0 | 73.0 | 36.6 | 84.6 | - | 65.4
Avg | 67.9 | 30.7 | 59.1 | 27 | 72.8 | 56.9 | 52.4 | Avg | 73.1 | 48.3 | 68.5 | 14.0 | 84.6 | 65.8 | 59.1 | Avg | 77.9 | 46.2 | 68.5 | 32.6 | 84.3 | 68.8 | 63.0

##  4 Experiments

We evaluate our proposed method on three different domain adaptation
benchmarks, Office-Home, VisDA, and DomainNet. We show that we can improve the
baselines significantly. In ablation studies, we further investigate the
contribution of the different parts of our proposed algorithm.

###  4.1 Setup

Office-Home [28] contains 15,500 images of 65 categories. The domains are Art
(A), Clipart (C), Product (P), and Real-World (R). We evaluate all twelve
possible adaptation tasks.

VisDA [18] is a challenging dataset for for synthetic-to-real domain
adaptation. The synthetic source domain consists of 152397 images and the
real-world target domain consists of 55388 images over 12 different classes.

DomainNet [19] is a large-scale dataset with about 600,000 images from 6
different domains and 345 different classes. We evaluate all 30 possible
adaptation tasks.

Implementation details: We built up our implementation on the CDAN
implementation of [15]. We do all experiments with the CLIP-trained versions
of the ResNet backbone and transformer backbone. For the ResNet backbone, we
follow most other publications and employ ResNet-50 for OfficeHome and
ResNet-101 for VisDA. For the transformer backbone, we employ ViT-B/16. We
employ the seven ImageNet templates subset published on the CLIP Git Hub for
the language encoder to estimate the zero-shot predictions. For OfficeHome we
train each run for $100$ episodes, for VisDA and DomainNet we train for $50$
episodes. For OfficeHome and DomainNet, we employ AdamW optimizer with a
learning rate of $5e^{-6}$ for the backbone and $5e^{-5}$ for the newly
initialized layers. For VisDA we employ a lower learning rate of $1e^{-6}$,
and $1e^{-5}$ respectively. We employ the GSDE strategy for a total of $N=5$
runs. Each experiment is run for three different seeds, except for the
DomainNet which we only train for one seed.

Figure 4: Accuracy for adaptation of OfficeHome C$\rightarrow$A for different values for $\tau$. None represents directly using the zero-shot predictions without any distribution shift. It can be seen that adjusting the probability distribution is fundamental for the knowledge distillation to work properly. Table 4: Contributions of different parts of our algorithm. Aug means using strongly augmented images alongside the weakly augmented ones, while GSDE uses only the prediction scores of the previous run, GSDE+ adds zero-shot prediction scores according to eq. 5. | ResNet | ViT
---|---|---
$L_{AD}$ | $L_{KD}$ | Aug | GSDE | GSDE+ | VisDA | OH | VisDA | OH
$\checkmark$ |  |  |  |  | 72.73 | 65.99 | 74.25 | 81.74
| $\checkmark$ |  |  |  | 87.65 | 69.06 | 90.28 | 83.27
$\checkmark$ | $\checkmark$ |  |  |  | 88.21 | 73.43 | 90.44 | 87.66
$\checkmark$ | $\checkmark$ | $\checkmark$ |  |  | 88.62 | 75.48 | 90.37 | 87.97
$\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ |  | 88.90 | 78.72 | 91.22 | 89.08
$\checkmark$ | $\checkmark$ | $\checkmark$ |  | $\checkmark$ | 89.09 | 78.78 | 91.20 | 89.24
Table 5: Generalization to unseen data. | train | test | comb
---|---|---|---
ZS | 59.05 | 59.11 | 59.07
Ours | 63.32 | 62.38 | 63.04

###  4.2 Results

Results for Office-Home: The results for the Office-Home dataset are shown in
Tab. 1. The zero-shot predictions already outperform some of the earlier works
but are considerably below current state-of-the-art algorithms. Using our
method, we improve the average accuracy by $7.3$pp for the ResNet-50 backbone
and $7.0$pp for the ViT backbone. An improvement can be seen for all $12$
adaptation tasks. For the ResNet backbone, we improve the state-of-the-art by
around $4.3$pp.

Results for VisDA-2017: The results for the VisDA-2017 dataset are shown in
Tab. 2. Again, the zero-shot predictions already outperform some of the
earlier works but are considerably below current state-of-the-art algorithms.
Using our method, we improve the average accuracy by $4.4$pp for the
ResNet-101 backbone and $2.6$pp for the ViT backbone, letting us outperform
current state-of-the-art methods.

Results for DomainNet: The results for the DomainNet dataset are shown in Tab.
3. The zero-shot predictions already outperform current state-of-the-art
methods considerably. By using our method we further increase the average
accuracy by $3.9$pp. We achieve the biggest increase of performance over the
zero-shot predictions for the target set of quickdraw, increasing the accuracy
by $18.6$pp. However, when using the quickdraw domain as source data, the
accuracy decreases considerably by around $10.3$pp compared to the zero-shot
predictions. The quickdraw domain has a large domain gap to the other domains.
This large gap introduces a negative transfer resulting in a drop in accuracy.

##  5 Ablation studies

Parameter for adjusting zero-shot distribution $\tau$: In this part, we
evaluate the effect of the parameter $\tau$. Figure 4 shows the accuracy for
different values of $\tau$. None means that no distribution shift was applied
to the zero-shot predictions. It can be seen that applying the distribution
shift is essential for the method. Employing a shift of $\tau=0.9$ increases
the accuracy by $10.9$pp for ResNet and $6.2$pp for ViT backbone. For the ViT
backbone, the accuracy increases constantly until a value of $0.9$, for which
the accuracy peaks. For the ResNet backbone, it seems that even higher values
of $\tau$ yield better results. In all our experiments, we employ a value for
$\tau$ of $0.9$.

Contribution of losses: In this part, we evaluate the contribution of the
different losses to our method. The combination of $L_{AD}$ and $L_{KD}$
improves the accuracy in all of the four settings. Especially for the
OfficeHome dataset, where adversarial domain adaptation and knowledge
distillation achieve similar results, the boost is the largest. Data
augmentation further slightly increases the accuracy. And we achieve another
boost by introducing GSDE. Introducing the zero-shot predictions into the GSDE
algorithm increases the accuracy further a slight bit.

Generalization to unseen data: Since we only used the training sets for the
adaptation task in the DomainNet dataset, it allows us to evaluate the
generalization ability to unseen data. The results are shown in Tab. 5. As
expected the zero-shot accuracy is similar between the train and test set. Our
method has a slight drop of around $1$pp for the test set, meaning that there
is a slight overfitting to the seen data. However it still significantly
outperforms the zero-shot prediction accuracy. Since the train dataset is much
larger than the test dataset, the combined results are closer to the train
dataset.

T-SNE visualization: We visualize the feature embedding using T-SNE for the
addition of the different losses as well as for the CLIP pre-trained model in
5. Since the CLIP model is not trained classification but aligning visual and
language features, the distribution is very spread out (see Fig. 5(a)).
Interestingly the source and target domain are quite separated. Using the KD
loss (and classification loss) aligns the different classes into clusters, but
does not do a good job of aligning the features (see Fig. 5(c)). The CDAN loss
aligns both domains well but suffers from misalignment between different
classes (see Fig. 5(e)). By combining the two methods, we get well-aligned
domains with fewer misalignments (see Fig. 5(g)).

(a) CLIP.

(b) CLIP.

(c) KD.

(d) KD.

(e) CDAN.

(f) CDAN.

(g) Combined.

(h) Combined.

Figure 5: TSNE visualization of the A$\shortrightarrow$C adaptation task. On
the left side source samples are in red, and target ones are in blue. On the
right side source samples are marked by circles and target ones by crosses.

##  6 Discussion

In this work, we presented a novel way to combine the knowledge of vision-
language models with knowledge gained from a source dataset through
unsupervised domain adaptation. We maintain the inherent knowledge of the
vision-language model via a knowledge distillation loss. To effectively
distill the knowledge we introduced a distribution adjustment for the
prediction probabilities. For the domain adaptation loss, we employed CDAN as
it is effective for both CNN and transformer-based backbones. We showed the
effectiveness of our method for both backbones on three different datasets,
outperforming current state-of-the-art methods. We showed that combining
unsupervised domain adaptation with the inherent knowledge of vision-language
models improves the performance significantly over using only one of the
knowledge sources. It should be stated, that it can be expected to further
increase the performance by choosing a stronger method for the domain
adaptation task.

## Acknowledgment

This work was partially supported by JST Moonshot R&D Grant Number JPMJPS2011,
CREST Grant Number JPMJCR2015, JSPS KAKENHI Grant Number JP21K17799, and Basic
Research Grant (Super AI) of Institute for AI and Beyond of the University of
Tokyo.

## References

  * Chen et al. [2022a] Dian Chen, Dequan Wang, Trevor Darrell, and Sayna Ebrahimi.  Contrastive test-time adaptation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 295–305, 2022a.
  * Chen et al. [2022b] Haoran Chen, Zuxuan Wu, Xintong Han, and Yu-Gang Jiang.  Multi-prompt alignment for multi-source unsupervised domain adaptation.  _arXiv preprint arXiv:2209.15210_ , 2022b.
  * Du et al. [2021] Zhekai Du, Jingjing Li, Hongzu Su, Lei Zhu, and Ke Lu.  Cross-domain gradient discrepancy minimization for unsupervised domain adaptation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 3937–3946, 2021.
  * Fang et al. [2023] Alex Fang, Albin Madappally Jose, Amit Jain, Ludwig Schmidt, Alexander Toshev, and Vaishaal Shankar.  Data filtering networks.  _arXiv preprint arXiv:2309.17425_ , 2023.
  * Ganin et al. [2016] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky.  Domain-adversarial training of neural networks.  _The journal of machine learning research_ , 17(1):2096–2030, 2016.
  * Gao et al. [2022] Yunhe Gao, Xingjian Shi, Yi Zhu, Hao Wang, Zhiqiang Tang, Xiong Zhou, Mu Li, and Dimitris N Metaxas.  Visual prompt tuning for test-time domain adaptation.  _arXiv preprint arXiv:2210.04831_ , 2022.
  * Ge et al. [2022] Chunjiang Ge, Rui Huang, Mixue Xie, Zihang Lai, Shiji Song, Shuang Li, and Gao Huang.  Domain adaptation via prompt learning.  _arXiv preprint arXiv:2202.06687_ , 2022.
  * Hinton et al. [2015] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ , 2015.
  * Jia et al. [2021] Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc Le, Yun-Hsuan Sung, Zhen Li, and Tom Duerig.  Scaling up visual and vision-language representation learning with noisy text supervision.  In _International conference on machine learning_ , pages 4904–4916. PMLR, 2021.
  * Kang et al. [2019] Guoliang Kang, Lu Jiang, Yi Yang, and Alexander G Hauptmann.  Contrastive adaptation network for unsupervised domain adaptation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 4893–4902, 2019.
  * Kim et al. [2022] Donghyun Kim, Kaihong Wang, Stan Sclaroff, and Kate Saenko.  A broad study of pre-training for domain generalization and adaptation.  In _ECCV_ , pages 621–638. Springer, 2022.
  * Li et al. [2021a] Junjie Li, Yixin Zhang, Zilei Wang, and Keyu Tu.  Probabilistic contrastive learning for domain adaptation.  _arXiv preprint arXiv:2111.06021_ , 2021a.
  * Li et al. [2021b] Shuang Li, Mixue Xie, Fangrui Lv, Chi Harold Liu, Jian Liang, Chen Qin, and Wei Li.  Semantic concentration for domain adaptation.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 9102–9111, 2021b.
  * Liang et al. [2020] Jian Liang, Dapeng Hu, and Jiashi Feng.  Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation.  In _International Conference on Machine Learning_ , pages 6028–6039. PMLR, 2020.
  * Long et al. [2018] Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I. Jordan.  Conditional adversarial domain adaptation.  In _NeurIPS_ , pages 1647–1657, 2018.
  * Lu et al. [2020] Zhihe Lu, Yongxin Yang, Xiatian Zhu, Cong Liu, Yi-Zhe Song, and Tao Xiang.  Stochastic classifiers for unsupervised domain adaptation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 9111–9120, 2020.
  * Na et al. [2022] Jaemin Na, Dongyoon Han, Hyung Jin Chang, and Wonjun Hwang.  Contrastive vicinal space for unsupervised domain adaptation.  In _European Conference on Computer Vision_ , pages 92–110. Springer, 2022.
  * Peng et al. [2017] Xingchao Peng, Ben Usman, Neela Kaushik, Judy Hoffman, Dequan Wang, and Kate Saenko.  Visda: The visual domain adaptation challenge.  _arXiv preprint arXiv:1710.06924_ , 2017.
  * Peng et al. [2019] Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang.  Moment matching for multi-source domain adaptation.  In _ICCV_ , pages 1406–1415, 2019.
  * Pham et al. [2023] Hieu Pham, Zihang Dai, Golnaz Ghiasi, Kenji Kawaguchi, Hanxiao Liu, Adams Wei Yu, Jiahui Yu, Yi-Ting Chen, Minh-Thang Luong, Yonghui Wu, et al.  Combined scaling for zero-shot transfer learning.  _Neurocomputing_ , 555:126658, 2023.
  * Prabhu et al. [2021] Viraj Prabhu, Shivam Khare, Deeksha Kartik, and Judy Hoffman.  Sentry: Selective entropy optimization via committee consistency for unsupervised domain adaptation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 8558–8567, 2021.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , pages 8748–8763. PMLR, 2021.
  * Rangwani et al. [2022] Harsh Rangwani, Sumukh K Aithal, Mayank Mishra, Arihant Jain, and Venkatesh Babu Radhakrishnan.  A closer look at smoothness in domain adversarial training.  In _International Conference on Machine Learning_ , pages 18378–18399. PMLR, 2022.
  * Saito et al. [2018] Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada.  Maximum classifier discrepancy for unsupervised domain adaptation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3723–3732, 2018.
  * Singha et al. [2023] Mainak Singha, Harsh Pal, Ankit Jha, and Biplab Banerjee.  Ad-clip: Adapting domains in prompt space using clip.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 4355–4364, 2023.
  * Sun et al. [2022] Tao Sun, Cheng Lu, Tianshuo Zhang, and Haibin Ling.  Safe self-refinement for transformer-based domain adaptation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 7191–7200, 2022.
  * Tang et al. [2020] Hui Tang, Ke Chen, and Kui Jia.  Unsupervised domain adaptation via structurally regularized deep clustering.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 8725–8735, 2020.
  * Venkateswara et al. [2017] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan.  Deep hashing network for unsupervised domain adaptation.  In _CVPR_ , pages 5018–5027, 2017.
  * Westfechtel et al. [2023a] Thomas Westfechtel, Hao-Wei Yeh, Qier Meng, Yusuke Mukuta, and Tatsuya Harada.  Backprop induced feature weighting for adversarial domain adaptation with iterative label distribution alignment.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 392–401, 2023a.
  * Westfechtel et al. [2023b] Thomas Westfechtel, Hao-Wei Yeh, Dexuan Zhang, and Tatsuya Harada.  Gradual source domain expansion for unsupervised domain adaptation.  _arXiv preprint arXiv:2311.09599_ , 2023b.
  * Xiao and Zhang [2021] Ni Xiao and Lei Zhang.  Dynamic weighted learning for unsupervised domain adaptation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 15242–15251, 2021.
  * Xie et al. [2018] Shaoan Xie, Zibin Zheng, Liang Chen, and Chuan Chen.  Learning semantic representations for unsupervised domain adaptation.  In _International conference on machine learning_ , pages 5423–5432. PMLR, 2018.
  * Xu et al. [2021] Tongkun Xu, Weihua Chen, Pichao Wang, Fan Wang, Hao Li, and Rong Jin.  Cdtrans: Cross-domain transformer for unsupervised domain adaptation.  _arXiv preprint arXiv:2109.06165_ , 2021.
  * Yang et al. [2023] Jinyu Yang, Jingjing Liu, Ning Xu, and Junzhou Huang.  Tvt: Transferable vision transformer for unsupervised domain adaptation.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 520–530, 2023.
  * Zara et al. [2023] Giacomo Zara, Alessandro Conti, Subhankar Roy, Stéphane Lathuilière, Paolo Rota, and Elisa Ricci.  The unreasonable effectiveness of large language-vision models for source-free video domain adaptation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10307–10317, 2023.
  * Zhai et al. [2022] Xiaohua Zhai, Xiao Wang, Basil Mustafa, Andreas Steiner, Daniel Keysers, Alexander Kolesnikov, and Lucas Beyer.  Lit: Zero-shot transfer with locked-image text tuning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 18123–18133, 2022.
  * Zhang et al. [2019] Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan.  Bridging theory and algorithm for domain adaptation.  In _International Conference on Machine Learning_ , pages 7404–7413. PMLR, 2019.
  * Zhao et al. [2020] Sicheng Zhao, Xiangyu Yue, Shanghang Zhang, Bo Li, Han Zhao, Bichen Wu, Ravi Krishna, Joseph E Gonzalez, Alberto L Sangiovanni-Vincentelli, Sanjit A Seshia, et al.  A review of single-source deep unsupervised visual domain adaptation.  _IEEE Transactions on Neural Networks and Learning Systems_ , 33(2):473–493, 2020.
  * Zhou et al. [2022] Kaiyang Zhou, Jingkang Yang, Chen Change Loy, and Ziwei Liu.  Learning to prompt for vision-language models.  _International Journal of Computer Vision_ , 130(9):2337–2348, 2022.
  * Zhu et al. [2023] Jinjing Zhu, Haotian Bai, and Lin Wang.  Patch-mix transformer for unsupervised domain adaptation: A game perspective.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3561–3571, 2023.
  * Zhuang et al. [2020] Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He.  A comprehensive survey on transfer learning.  _Proceedings of the IEEE_ , 109(1):43–76, 2020\.


# CFR-p $\colon$ Counterfactual Regret Minimization with Hierarchical Policy
Abstraction, and its Application to Two-player Mahjong

Shiheng Wang
<EMAIL_ADDRESS>
###### Abstract

> Counterfactual Regret Minimization(CFR) has shown its success in Texas
> Hold’em poker. We apply this algorithm to another popular incomplete
> information game, Mahjong. Compared to the poker game, Mahjong is much more
> complex with many variants. We study two-player Mahjong by conducting game
> theoretical analysis and making a hierarchical abstraction to CFR based on
> winning policies. This framework can be generalized to other imperfect
> information games.

##  1 Introduction to CFR

###  1.1 Normal-form and Extensive-form Games

A finite normal-form game is a tuple $(N,A,u)$, where

  * •

$N=\\{1,...,n\\}$ is a finite set of n players.

  * •

$A=S_{1}\times...\times S_{n}$ is the set of all action profiles, where
$S_{i}$ is a finite set of actions available to player $i$. Each vector $a\in
A$ is called an action profile (or outcome).

  * •

$u=(u_{1},...,u_{n})$, where $u_{i}:A\mapsto\mathbb{R}$ is a real-valued
utility (also called payoff or reward) function for player i.

A normal-form game is zero-sum if the utilities of all players sum up to be
zero for any given outcome, i.e. $\forall a\in A,\sum_{i\in N}u_{i}(a)=0$. In
constant-sum games, the utilities sum up to a constant value. Constant-sum
games can be reformulated into zero-sum games.

A pure strategy picks one action with probability 1, while a mixed strategy
assigns a distribution over actions, denoted with $\sigma$. $\sigma_{i}(s)$
refers to the probability that player $i\in N$ picks action $s\in S_{i}$. $-i$
refers to player $i$’s opponents. The expected utility of player $i$ can be
computed as,

$u_{i}(\sigma_{i},\sigma_{-i})=\sum_{s\in S_{i}}\sum_{s^{\prime}\in
S_{-i}}\sigma_{i}(s)\sigma_{-i}(s^{\prime})u_{i}(s,s^{\prime}).$

Given all other players’ strategies, a best response for player $i$ maximizes
its expected utility. When every player is playing a best response to other
players’ strategies, the combination of strategies is called a Nash
Equilibrium, where no player can get higher utility by deviation.

In a normal-form game, players take actions simultaneously. In a sequential
game, however, a play consists of a sequence of actions. A sequential game is
formed by a extensive-form game, where the game tree is formed of states with
edges transiting from state to state.

A state can be a chance node or decision node. A chance node assigns the
outcome of a chance event, so each edge corresponds to an outcome with its
probability. At a decision node, the edges represent the actions and their
related successor states. Each decision node in the game tree is contained
within an information set, which contains one active player and all
information available to him. One information set may contain more than one
game state.

Let $A$ denote the set of all game actions, $I$ denote an information set, and
$A(I)$ denote the set of legal actions for information set $I$. Let $t$ and
$T$ denote time steps. A strategy $\sigma_{i}^{t}$ maps player i’s information
set $I_{i}$ to $\Delta(A(I_{i}))$, that is, a probability distribution over
legal actions. At time $T$, all players’ strategies form a strategy profile
$\sigma^{t}$, and a strategy profile excluding player i is denoted as
$\sigma_{-i}$. Let $\sigma_{I\to a}$ denote a profile equivalent to $\sigma$,
except that action $a$ is always chosen at information set $I$.

A history $h$ is a sequence of actions (including chance outcomes) starting
from the game root. Let $\pi^{\sigma}(h)$ be the reach probability of the game
history $h$ with strategy profile $\sigma$. Similarly, let $\pi^{\sigma}(I)$
be the probability of reaching information set $I$ through all possible
histories in $I$, i.e. $\pi^{\sigma}(I)=\sum_{h\in I}\pi^{\sigma}(h)$.

All extensive-form games have an equivalent normal-form representation.

###  1.2 Regret Minimization

This introduction follows from (?).

Regret Matching, introduced by Hart and Mas-Colell in 2000, has sparked a
revolution in computer game play of some of the most difficult incomplete-
information games. Players reach equilibrium by tracking regrets for past
plays, making future plays proportional to positive regrets.

Regret of not having chosen an action is defined as the difference between the
utility of that action and the utility of the action that is actually chosen,
with respect to the fixed choices of other players. Formally, for action
profile $a\in A$, let $s_{i}$ be player $i$’s action and $s_{-i}$ be the
actions of all other players. Suppose $s_{i}^{\prime}$ is substituted for
$s_{i}$, then after the play, player $i$’s regret for not have played
$s_{i}^{\prime}$ is $u(s_{i}^{\prime},s_{-i})-u(s_{i},s_{-i})$.

In order to chose the action that has the largest regret and meanwhile not
totally predictable and thus exploitable, one player may take regret matching,
where actions are selected at random with a distribution that is proportional
to positive regrets.

When the game is repeated for a number of rounds, regrets of previous rounds
accumulate. Over time, for two-player zero-sum games, regret matching
converges to a correlated equilibrium.

Our tutorial demo for regret matching is available at,

https://github.com/workplay/CFR

###  1.3 Counterfactual Regret Minimization

Regret matching is only applicable to normal-form games, while CFR works for
extensive-form games. This introduction also follows from (?), and the details
can be found in (?) and (?).

The counterfactual reach probability of information set $I$,
$\pi_{-i}^{\sigma}(I)$, is the probability of reaching $I$ with strategy
profile $\sigma$ except that, we treat current player $i$’s actions to reach
the state as having probability 1. “Counterfactual” here means that player
$i$’s strategy is modified to have intentionally played to information set
$I_{i}$. In other words, the probabilities that factually came into player
$i$’s play is excluded from the computation.

Let $Z$ denote the set of all terminal game histories (from root to leaf).
Then proper prefix $h\sqsubset z$ for $z\in Z$ is a nonterminal game history.
$u_{i}(z)$ is player $i$’s utility of terminal history $z$. Define the
counterfactual value at nonterminal history $h$ as:

$v_{i}(\sigma,h)=\sum_{z\in Z,h\sqsubset
z}\pi_{-i}^{\sigma}(h)\pi^{\sigma}(h,z)u_{i}(z)$ (1)

The counterfactual regret of not taking action $a$ at history $h$ is defined
as:

$r(h,a)=v_{i}(\sigma_{I\to a},h)-v_{i}(\sigma,h)$ (2)

The counterfactual regret of not taking action $a$ at information set $I$ is:

$r(I,a)=\sum_{h\in I}r(h,a)$ (3)

Let $r_{i}^{t}(I,a)$ refer to the regret when players use $\sigma^{t}$ of not
taking action $a$ at information set $I$ belonging to player $i$. The
cumulative counterfactual regret is defined as:

$R_{i}^{T}(I,a)=\sum_{t=1}^{T}r_{i}^{t}(I,a)$ (4)

The regret of action $a$ is the difference between the value of always
choosing action $a$ and the expected value of strategy $\sigma$, weighted by
the probability that other players (including chance player) will play to
reach the node.

Suppose the nonnegative counterfactual regret is defined as
$R_{i}^{T,+}=\max(R_{i}^{T}(I,a),0)$, then the new strategy can be obtained
from cumulative regrets.
If $\sum_{a\in A(I)}R_{i}^{T,+}(I,a)>0$,

$\sigma_{i}^{T+1}(I,a)=\frac{R_{i}^{T,+}(I,a)}{\sum_{a\in
A(I)}R_{i}^{T,+}(I,a)}.$ (5)

Otherwise take a random strategy,

$\sigma_{i}^{T+1}(I,a)={1}\big{/}{|A(I)|}$ (6)

For each information set, equation (5) computes a strategy of which action
probabilities are proportional to the positive cumulative regrets. CFR
computes the utility of each action recursively. Regrets are computed from
returned values, and the values of the current node is finally computed and
returned. The average strategy profile at information set $I$ approaches an
equilibrium as $T\to\infty$.

##  2 Two-Player Mahjong

###  2.1 Rules

Table 1: Mahjong Tile Count Category | Name | Count
---|---|---
Simples | Dots | 36
Bamboo | 36
Characters | 36
Honors | Winds | 16
Dragons | 12
Bonus | Flowers | 4
Seasons | 4
Total | 144
Figure 1: Two-player Mahjong Tiles

Mahjong is a tile-based game developed in China, which is commonly played by
four players. There is a detailed elaboration on
Wikipedia111https://en.wikipedia.org/wiki/Mahjong, which is abbreviated to
this concise instruction. As is shown in Table 1, a typical set of Mahjong
tiles usually has at least 136 tiles. There are 3 suits of simples and in each
suit the tiles are numbered from 1 to 9. The suits are bamboos, dots, and
characters. There are 4 identical copies of each simples tile totaling 108
simples tiles. There are two different sets of Honors tiles: Winds and
Dragons. The Winds are East, South, West, and North. The Dragons are Red,
Green, and White. These tiles have no numerical sequence and there are four
identical copies of each Honors tile, for a total of 28 Honors tiles. There
are two sets of Bonus tiles: Flowers and Seasons. When drawn, the Bonus tile
is not added into a player’s hand but are instead set aside for scoring
purposes, and an extra tile is drawn in replacement of the Bonus tile.

Two-player Mahjong is a simplified variant designed by Tencent
222https://majiang.qq.com/index.html, which is played with a set of 68 tiles.
All Dots and Bamboos are excluded, and there are only Characters, Honors and
Bonus. As Bonus don’t affect the rules of the game, they are not considered in
our analysis. The tiles are displayed in Figure 1.

Although there are fewer tiles and players, the basic rules remain the same.
Each player begins by receiving 13 tiles, and in turn players draw and discard
tiles until they complete a legal hand using the 14th drawn tile to form 4
melds (or sets) and an eye (two identical tiles). Melds are groups of tiles
within the player’s hand, consisting of either a Pong (three identical tiles),
a Kong (four identical tiles), a Chow (three Simple tiles all of the same
suit, in numerical sequence). Whenever a Kong is formed, that player must draw
an extra tile from the end of the wall(face down tiles on the table) and then
discard a tile. Melds may be formed by drawing a tile from the wall, or by
seizing another player’s discard. A player can also win with other special
hands, like seven Eyes.

Points are obtained by matching the winning hand with different values. For
simplicity, we only consider most popular patterns of winning. PongPongHu(4
Pongs and 1 Eye) or QiDui(7 Eyes) gets two points, and all other winning
patterns get one point. We choose two-player Mahjong to study algorithms for
incomplete-information games. This framework can be generalized to other
variants in the future.

###  2.2 Extensive-Form Game Representation

Each player in turn, in counterclockwise direction, draws a tile from the
wall; then this player proceeds to discard a tile. The discarded tile is
thrown into the centre and the other players have an opportunity to seize the
discarded tile; if no one takes it, the turn continues to the next player.
Play continues this way until one player has a legal winning hand and calls
out ”Hu” while revealing their hand.

Figure 2: Extensive-Form Game Representation

As the normal counterclockwise order may be interrupted, a neat extensive-form
game (?) representation is necessary in order to conduct game theoretical
analysis as well as to implement algorithms. There are two players 0 and 1,
and each player’s turn is separated into three phases 0, 1 and 2. Figure 2
shows one turn for player 1. In phase 1, although there is an edge pointing
from node “Draw a tile.” to itself by action Kong, the player actually draws a
tile before he acts Kong, thus the game goes to a new state, which doesn’t
result in a cycle in the game tree.

  * •

In phase 0, the player can seize the discard by forming Chow, Pong, Kong, Win
with tiles in his hand, otherwise he can only Pass. For Chow and Pong, he
directly goes to phase 2, otherwise to phase 1.

  * •

In phase 1, the player draws a tile from the wall. Possible legal actions are
declaring Win, Kong and Pass. By choosing Kong, he reenters phase 1, while
Pass leads to phase 2.

  * •

In phase 2, the only legal action is to discard a tile from his hand.

Table 2: Possible Legal Actions Phase | Possible Legal Actions
---|---
0 | Chow, Pong, Kong, Win, Pass.
1 | Kong, Win, Pass.
2 | Discard a tile.

Possible legal actions are summarized in Table 2. Notice that Chow, Pong,
Kong, Win are legal actions only when certain patterns can be formed with
other tiles in hand.

###  2.3 Complexity

Suppose all hidden information are given, the complexity of two-player Mahjong
is similar to Chess. The number of reachable positions on a chess board is
estimated to be fewer than $10^{46}$ (?) . As most actions in phase 0 and 1
are legal only with certain tiles in hand, we assume that both players take
the action Pass in order to estimate the complexity of the game tree. In phase
3, however, during each round there are 14 tiles in hand, and the player
chooses one of them to discard. Two-player Mahjong consists of 36 Character
tiles and 28 Honor tiles, of which 26 tiles will be allocated to both players
in the beginning. Therefore the game tree has more than $14^{38}$ leaves, and
the complexity can reach $10^{43}$. Note that only one action is considered in
phase 0 and 1, thus the complexity serves as a lower bound.

As long as incomplete information is introduced, the game becomes much more
complicated. Each permutation corresponds to a different game, and only
discarded tiles are public information to both players. There are 4 identical
copies of 16 different tiles, and the number of permutations after shuffling
can be calculated as,

$\frac{A_{64}^{64}}{(A_{4}^{4})^{16}}\approx 1.2*10^{22}.$ (7)

In total, the complexity reaches $10^{64}$. In comparison, two-player Limit
Texas Hold’em poker only has $10^{18}$ leaves (?).

Mahjong is much more complex than Texas Hold’em poker, which is popular among
literatures about incomplete information games. The most significant
difference is that the hidden information keeps changing during the entire
play. In Texas Hold’em poker, play begins with each player being dealt two
cards face down, and this hidden information remains the same during the
entire play. In Mahjong, however, hidden tiles in hand keep changing after
every round. As a result, existing algorithms such as decomposition (?) or
subgame solving (?) cannot be directly applied to Mahjong. Secondly, the
amount of hidden information is much larger. There are only 2 face down cards
in poker, but there are 13 hand tiles in Mahjong. Finally, each poker player
only bets for at most five rounds, while in Mahjong, the number of rounds can
be as large as 38.

Note that two-player Mahjong is the most simplified version. Usually a Mahjong
game is played by four players with 136 tiles.

##  3 Hierarchical Policy Abstraction

Because of the complexity caused by a lot of private hidden information that
keeps changing, we cannot implement CFR on two-player Mahjong directly. We
make many abstractions in order to reduce the complexity.

Figure 3: Hierarchical Policy Abstraction

At high level, we conduct hierarchical policy abstraction. As is introduced in
section 2.1, there are several patterns of winning, such as QiDui, PongPongHu,
etc. Based on the fact that there are several distinct patterns, and that
winning with the same pattern usually receives the same points, we separate
the task of the game into two parts:

  1. 1.

Which winning pattern should we achieve?

  2. 2.

What is the most efficient way to achieve it?

Suppose the complexity of both parts are $\mathcal{O}(T_{1})$ and
$\mathcal{O}(T_{2})$. Compared to an end-to-end algorithm, the hierarchical
policy abstraction significantly reduces the complexity from
$\mathcal{O}(T_{1}*T_{2})$ to $\mathcal{O}(T_{1}+T_{2})$. In addition, at each
node of the game tree, the number of legal actions plunges to the number of
winning patterns. For instance, in two-player Mahjong, phase 3, the agent need
to discard a tile out of 14 tiles in his hand, resulting in 14 possible legal
actions. With policy abstraction, however, the number of legal actions becomes
3, i.e. to win with PongPongHu, to win with QiDui, or to win Normally without
special patterns. Finally the number of leaves in the game tree can be as few
as $3^{3}8\approx 1.35\times 10^{18}$. Moreover, it’s not necessary to change
the policy at every round, especially when the agent is reaching the end of
the game, so that the size of the game tree can be further reduced.

Each separate sub-task can be solved independently by adopting an appropriate
algorithm, such as rule-based search, supervised learning with professional
players’ game history, or reinforcement learning like CFR. For the 1st sub-
task, which winning pattern can win most points should be concluded based on
the statistics from self-play. As for the 2nd sub-task, since there is a clear
indicator to the distance between the tiles in hand and the target winning
pattern, rule-based search can help solve this problem, such as keeping melds
in hand and dropping other single tiles.

Figure 4: GUI for Testing

##  4 Implementation

Our two-player Mahjong framework consists of three parts: the game logic, the
AI and the GUI(graphical user interface) for testing.

###  4.1 The Game Logic and the GUI for Testing

The game logic is designed following the extensive-form representation in
Figure 2. It tracks tiles in hand as well as all hidden and dropped tiles on
the table, determines legal actions in every phase, and writes down all game
states to a log file. Some legal actions can be decided directly according to
special patterns and tiles in hand, for example, whether hand tiles can form a
pattern of Chow, Pong or Kong together with the tile dropped by the other
player. Some other legal actions such as winning are much more complex, which
requires the game logic to check whether the tiles in hand form any of the
winning patterns.

In purpose of supporting CFR and other search based algorithms, the game logic
is designed recursively. At each node, it makes a copy of current game state,
tries some legal actions, and returns the utility recursively from a leaf
node. Since there is only one searching path from root to current game node
each time, only linear memory is required while running search algorithms.

The game logic supports both training and testing. In the training mode, it
repeatedly traverse the game tree recursively, keeping a record of utilities
for each action at each node. The choice of actions and recorded utilities is
determined by the AI algorithm. When testing, however, it runs one possible
path from root to leaf, records all game states and actions and writes them to
a log file, which can be analyzed by GUI for testing.

As is shown in Figure 4, the GUI for testing reads the log file and displays
the entire game process graphically. It keeps track of all tiles in hand, all
dropped tiles and the actions like Chow, Pong, Kong. Although only partial
information can be observed by the agent, all hidden information is released
to the tester. Whoever with some domain knowledge of this game can evaluate
whether the AI has made a rational move or not.

###  4.2 The AI

As is discussed in section 3, policies are abstracted into actions according
to winning patterns. For all three phases at every state there are only three
actions that are abstracted from policies, i.e. PongPongHu, 7Pairs and Normal.
There may be other policies in other variants of Mahjong, such as Defense,
Same Color, etc. Defense, for example, decrease other players’ probability of
winning regardless his own hand tiles. Such policy is not suitable for two-
player Mahjong because the game is zero-sum, thus defense also prevents the
agent itself from winning.

Each policy is realized by heuristic search, whose heuristic function
considers the number of potential winning tiles, the number of melds and
pairs, as well as the possible missing tiles which can form melds or pairs
with hand tiles. In general, the search algorithms aim at maximize the
probability of winning, ignoring winning points. The winning points, however,
is considered by the higher level CFR algorithm that picks the appropriate
winning pattern.

Bit | Meaning | Range
---|---|---
0-5 | The serial number of round | 0 - 38
6-8 | The number of Pairs | 0 - 6
9-11 | The number of Pongs or Kongs | 0-4
12-15 | The number of Character tiles | 0-14
16-19 | The number of Wind tiles | 0-14
Table 3: Encoding Features

The CFR algorithm is to find which abstract policy can win most points in
expectation at every decision node. The algorithm mainly follows from the
description in section 1, which assigns a mixed strategy to every information
set. We only do CFR three times for each player in the beginning, middle and
end of the game since it’s not necessary to change policies in every round.
The accumulated regrets and strategies are saved into a file with a tabular
representation, where each decision node is labeled by a compact encoding.

Figure 3 shows how the labels of nodes are encoded by a single integer.
Because of the huge amount of possible hand tiles and table tiles, we extract
features of hand tiles and cluster information sets according to these
features. Recall that there are basically three abstract actions, i.e. Normal,
PongPongHu and 7Pairs. If there exists an explicit Chow in the hand, Normal is
the only legal action so that the corresponding decision node will not be
saved.

While playing a game, the AI loads the node labeled by the same information
set as current hand tiles, then it picks one legal abstract policy based on
the accumulated regrets. The real action will be generated automatically by
the underlying heuristic search algorithms.

##  5 Evaluation

The notations in this section follow from (?).

To evaluate an extensive game strategy, there are typically two options. The
first one is to organize a tournament consisting of several strategies, like
the Annual Computer Poker Competition. The second one is to compute the worst-
case performance of a strategy. It is infeasible for large scale games because
it requires to traverse the entire game tree. We choose to compute the worst-
case performance of the abstracted game in this paper, and will organize
online tournaments with human players in the future.

A strategy for player i, $\sigma_{i}\in\Sigma_{i}$, is a function that assigns
a probability distribution over actions to each information set $I$. A
strategy profile, $\sigma\in\Sigma$, consists of a strategy for each player.
$\sigma_{-i}$ refers to all strategies in $\sigma$ except for $\sigma_{i}$.
$u_{i}(\sigma)$ is the utility for player $i$ under strategy profile $\sigma$.

The best response is the optimal strategy for player $i$ against the opponent
strategy profile $\sigma_{-i}$, denoted as $b_{i}(\sigma_{-i})$. The value of
the best response is $u_{i}(b_{i}(\sigma_{-i}),\sigma_{-i})$. Two-player zero-
sum games have a game value, $v_{i}$, that is the lower bound on the utility
of an optimal player in position $i$, formally,

$v_{i}=\min_{\sigma_{i}}u_{i}(\sigma_{i},b_{-i}(\sigma_{i})).$

In this case, the term exploitability of a strategy is how much additional
utility is lost to the best response by playing $\sigma_{i}$, formally,

$\varepsilon_{i}(\sigma_{i})=v_{i}-u_{i}(\sigma_{i},b_{-i}(\sigma_{i})).$

In large two player zero-sum games the value of the game is unknown and is
intractable to compute. However, if the players alternate positions, then the
value of a pair of games is zero. If an agent players according to the profile
$\sigma$ then its exploitability is

$\varepsilon(\sigma)=\frac{u_{2}(\sigma_{1},b_{2}(\sigma_{1}))+u_{1}(b_{1}(\sigma_{2}),\sigma_{2})}{2}$
(8)

(a) 5 iterations in each epoch

(b) 500 iterations in each epoch

Figure 5: Exploitability

We run the experiments on a computer with Intel Core i9-9900 3.10GHz CPU and
16GM RAM. The training process is done with single thread and the evaluation
is done with 100 threads. 3000 suits of tiles are randomly shuffled, serving
as the benchmark for evaluation. For each of them, the CFR player plays with
all heuristic search based players, and the opponent’s highest score is
selected as exploitability. Notice that this approximated exploitability is
higher than the actual value, because it allows different actions on the same
information set.

The training process adopts CFR with Monte Carlo sampling. At every iteration,
a suit of tiles is shuffled randomly and the CFR algorithm runs on this
specific suit. The training process is done for a number of iterations in each
epoch, and then it is evaluated on the benchmark generated previously.

Such random training samples can hit the benchmark which shares the same
feature encoding in Table 3. Figure 5(a) shows the training process where
there are 5 iterations in each epoch. This experiment runs for 130 iterations
and it takes around 12 hours. The exploitability gradually decreases but
becomes slower after 100 iterations. Figure 5(b) shows the case where each
epoch has 500 iterations, which turns out to be long tail. The training and
evaluating process takes around 72 hours. The exploitability drops
significantly in the first 500 iterations but gradually becomes stable
afterwards.

After training for 10000 iterations, there are 2618 nodes in the database.
Figure 4 shows an example of nodes. In round 1, there are 3 pairs and 2 Pongs
or Kongs in hand, and 11 of out 14 tiles are wind tiles. Since there is no
explicit Chows, Pongs or Kongs (All 14 tiles are in hand), all possible
actions are legal, among which PongPongHu has the highest regret.

encoding | 734401
---|---
round id | 1
number of Pairs | 3
number of Pongs or Kongs | 2
number of Character tiles | 3
number of wind tiles | 11
number of legal actions | 3
regret sum | [-0.598, 2.128, -1.356]
strategy sum | [1.359, 1.975, 0.667]
Table 4: An Example of Nodes

##  6 Discussion

It’s not entirely accurate to say that the hidden information stays the same
during the entire game of Texas hold’em. As the game proceeds, additional
cards are revealed, which reduces the number of possible states the players
can be in. But this has only a minor impact on the number of states.

Games with private actions are an interesting problem and an area that has
been under-explored. Algorithms like DeepCFR (?) work without a problem in
these games. Subgame solving (?) works in theory, but subgame solving is only
practical with a small amount of hidden information (less than about 1 million
information sets per player per subgame). So subgame solving as it exists
would not work in most games with private actions.

Compared to end-to-end algorithms, hierarchical policy abstraction is feasible
and flexible. It takes comprehensive measures to deal with games with private
actions, which can be trained on a single machine. Such algorithm can be
extended to other Mahjong games with similar winning patterns. However, the
current algorithm relies heavily on abstractions, which will be gradually
released, such as the order of discarded tiles and the features of visible
information.

##  7 Acknowledgement

This work was supported by Tencent Rhino-Bird Joint Research Program No.
GF201911, in collaboration with Peng Sun at the Tencent AI lab.

The game logic is developed based on Sichuan Mahjong which was developed by
Zhichao Shu from Tencent Lightspeed & Quantum Studios Group. We add the logic
of Chow and related winning patterns, formulate the game into extensive-form,
and implement the recursive search framework.

We’ve received valuable advice from Noam Brown 333https://www.cs.cmu.edu/
noamb/ in regard to games with private actions and exploitability, which is
discussed in section 6.

## References

  * [Brown and Sandholm 2017] Brown, N., and Sandholm, T.  2017\.  Safe and nested subgame solving for imperfect-information games.  In Advances in neural information processing systems, 689–699.
  * [Brown et al. 2019] Brown, N.; Lerer, A.; Gross, S.; and Sandholm, T.  2019\.  Deep counterfactual regret minimization.  In International Conference on Machine Learning, 793–802.
  * [Burch, Johanson, and Bowling 2014] Burch, N.; Johanson, M.; and Bowling, M.  2014\.  Solving imperfect information games using decomposition.  In Twenty-Eighth AAAI Conference on Artificial Intelligence.
  * [Chinchalkar 1996] Chinchalkar, S.  1996\.  An upper bound for the number of reachable positions.  ICGA Journal 19(3):181–183.
  * [Johanson et al. 2011] Johanson, M.; Waugh, K.; Bowling, M.; and Zinkevich, M.  2011\.  Accelerating best response calculation in large extensive games.  In Twenty-second international joint conference on artificial intelligence.
  * [Lanctot et al. 2009] Lanctot, M.; Waugh, K.; Zinkevich, M.; and Bowling, M.  2009\.  Monte carlo sampling for regret minimization in extensive games.  In Advances in neural information processing systems, 1078–1086.
  * [Neller and Lanctot 2013] Neller, T. W., and Lanctot, M.  2013\.  An introduction to counterfactual regret minimization.  In Proceedings of Model AI Assignments, The Fourth Symposium on Educational Advances in Artificial Intelligence (EAAI-2013), volume 11.
  * [Sandholm 2010] Sandholm, T.  2010\.  The state of solving large incomplete-information games, and application to poker.  AI Magazine 31(4):13–32.
  * [Shoham and Leyton-Brown 2008] Shoham, Y., and Leyton-Brown, K.  2008\.  Multiagent systems: Algorithmic, game-theoretic, and logical foundations.  Cambridge University Press.
  * [Zinkevich et al. 2008] Zinkevich, M.; Johanson, M.; Bowling, M.; and Piccione, C.  2008\.  Regret minimization in games with incomplete information.  In Advances in neural information processing systems, 1729–1736.