equationEquationEquationsfigureFigureFigurestableTableTablespagePagePagespartPartPartschapterChapterChapterssectionSectionSectionsappendixAppendixAppendicesenumiItemItemsfootnoteFootnoteFootnotestheoremTheoremTheoremslemmaLemmaLemmascorollaryCorollaryCorollariespropositionPropositionPropositionsdefinitionDefinitionDefinitionsresultResultResultsexampleExampleExamplesremarkRemarkRemarksnoteNoteNotesalgorithmAlgorithmAlgorithmslistingListingListingslineLineLinesequationEquationEquationsfigureFigureFigurespagePagePagestableTableTablespartPartPartschapterChapterChapterssectionSectionSectionsappendixAppendixAppendicesenumiItemItemsfootnoteFootnoteFootnotestheoremTheoremTheoremslemmaLemmaLemmascorollaryCorollaryCorollariespropositionPropositionPropositionsdefinitionDefinitionDefinitionsresultResultResultsexampleExampleExamplesremarkRemarkRemarksnoteNoteNotesalgorithmAlgorithmAlgorithmslistingListingListingslineLineLinesequationequationequationsfigurefigurefigurespagepagepagestabletabletablespartpartpartschapterchapterchapterssectionsectionsectionsappendixappendixappendicesenumiitemitemsfootnotefootnotefootnotestheoremtheoremtheoremslemmalemmalemmascorollarycorollarycorollariespropositionpropositionpropositionsdefinitiondefinitiondefinitionsresultresultresultsexampleexampleexamplesremarkremarkremarksnotenotenotesalgorithmalgorithmalgorithmslistinglistinglistingslinelinelinessectionsubsectionsubsectionsubsubsectionappendixsubappendixsubappendixsubsubappendixfiguresubfiguretablesubtableequationsubequationenumienumiienumiienumiiienumiiienumivenumivenumv

# KAN or MLP: A Fairer Comparison

Runpeng Yu, Weihao Yu, and Xinchao Wang
National University of Singapore

###### Abstract

This paper does not introduce a novel method. Instead, it offers a fairer and
more comprehensive comparison of KAN and MLP models across various tasks,
including machine learning, computer vision, audio processing, natural
language processing, and symbolic formula representation. Specifically, we
control the number of parameters and FLOPs to compare the performance of KAN
and MLP. Our main observation is that, except for symbolic formula
representation tasks, MLP generally outperforms KAN. We also conduct ablation
studies on KAN and find that its advantage in symbolic formula representation
mainly stems from its B-spline activation function. When B-spline is applied
to MLP, performance in symbolic formula representation significantly improves,
surpassing or matching that of KAN. However, in other tasks where MLP already
excels over KAN, B-spline does not substantially enhance MLP’s performance.
Furthermore, we find that KAN’s forgetting issue is more severe than that of
MLP in a standard class-incremental continual learning setting, which differs
from the findings reported in the KAN paper. We hope these results provide
insights for future research on KAN and other MLP alternatives.

https://github.com/yu-rp/KANbeFair

TL;DR-Under the same number of parameters or FLOPs, we find KAN outperforms
MLP only in symbolic formula representing, but remains inferior to MLP on
other tasks of machine learning, computer vision, NLP, and audio processing.

Figure 1:  Performance comparison between KAN and MLP under fair setup. MLP
yields higher average accuracy in machine learning, computer vision, natural
language processing, and audio processing, while KAN leads to lower average
root mean square error. page

##  1 Introduction

Multi-Layer Perceptrons (MLP) [15, 16, 17], also known as fully-connected
feedforward neural networks, are fundamental building blocks in modern deep
learning models. MLP consist of multiple layers of nodes, where each node (or
neuron) applies a fixed activation function to a weighted sum of its inputs.
This structure allows MLP to approximate a wide range of nonlinear functions,
a property guaranteed by the universal approximation theorem. As a result, MLP
are extensively used in various deep learning tasks, including classification,
regression, and feature extraction. Despite their versatility and widespread
application, MLP have certain limitations, such as difficulty in interpreting
the learned representations and flexibility in expanding the network scale.

Kolmogorov–Arnold Networks (KANs) [14] presents an innovative alternative to
traditional MLP by leveraging the Kolmogorov-Arnold representation theorem.
Unlike MLP, which employ fixed activation functions on nodes, KANs feature
learnable activation functions on edges, replacing linear weight parameters
with univariate functions parameterized as splines. KANs are expected to be
promising alternatives for MLP [14], which motivated us to carefully examine
it. However, current comparison experiments between KAN and MLP are not fair,
under different parameters or FLOPs. To probe the potential of KAN, it is
necessary to comprehensively compare KAN and MLP under fair settings.

To this end, we control the parameters or FLOPs of KAN and MLP, and then train
and evaluate them on tasks in various domains, including symbolic formula
representing, machine learning, computer vision, NLP, and audio processing.
Under these fair settings, we observe that KAN outperforms MLP only in
symbolic formula representation tasks, while MLP typically excels over KAN in
other tasks.

We further find that KAN’s advantages in symbolic formula representation stem
from its use of the B-spline activation function. Originally, MLP’s overall
performance lags behind KAN, but after replacing MLP’s activation function
with B-spline, its performance matches or even surpasses that of KAN. However,
BSpine cannot further improve the performance of MLP on other tasks, such as
computer vision.

We also found that KAN does not actually perform better than MLP in continual
learning task. The original KAN paper compared the performance of KAN and MLP
in continual learning tasks using a series of one-dimensional functions, where
each subsequent function was a translation of the previous function along the
number axis. We compared the performance of KAN and MLP in a more standard
class-incremental continual learning setting. Under fixed training iterations,
we found that KAN’s forgetting issue is more severe than that of MLP. We hope
that these results can provide insights for future research on KAN and other
MLP alternatives.

##  2 Formulation of KAN and MLP

There are two branches in KAN, the first branch is the B-spline branch, and
the other branch is the shortcut branch, which is a non-linear activation
concatenated with a linear transformation. In the official implementation, the
shortcut branch is a SiLU function followed by a linear transformation. Let
$x$ denote the feature vector for one sample. Then, the forward equation of
KAN‘s spline branch can be written as

$x=[\bm{A}*\text{Spline}(\bm{1}x^{T})]\bm{1}.$

Here the Spline function is an element-wise non-linear function. Its input is
a matrix and its output is the matrix with the same shape as the input. For
each element in the matrix, the spline function has a different non-linear
operation. All the non-linear operations share a same template, but with
different parameters. In the original KAN architecture, the spline function is
chosen to be the B-spline function. The parameters of each B-spline function
are learned together with other network parameters.

Correspondingly, the forward equation of a one-layer MLP with non-linear
operation first can be written as

$x=[\bm{A}*\sigma(\bm{1}x^{T})]\bm{1}.$

This formula shares the same form as the B-spline branch formula in KAN,
differing only in the nonlinear function. Therefore, aside from the
interpretation of the KAN structure in the original KAN paper, KAN can also be
viewed as a type of fully-connected layer. This fully-connected layer
undergoes an elementwise nonlinear function, followed by a linear
transformation. The differences between KAN and common MLP are in two aspects.
(1) Different activation functions. Commonly, the activation functions in MLP,
such as ReLU and GELU, have no learnable parameters and are uniform for all
input elements. However, in KAN, the activation function is a spline function,
which has learnable parameters and is different for each input element. (2)
The order of linear and non-linear operation. Generally, we conceptualize MLP
as performing a linear transformation followed by a non-linear transformation.
However, KAN actually performs a non-linear transformation first, followed by
a linear transformation. To some extent, it is also feasible to describe the
fully-connected layers in an MLP as “first non-linear, then linear”. For
example, for an MLP, the following two descriptions are equivalent: some
fully-connected layers with non-linear last and a linear head, or a linear
tail and some fully-connected layers with non-linear first.

Among the differences between KAN and MLP, we believe that the variation in
activation functions is the primary factor that differentiates KAN from MLP.
We hypothesize that the variation in activation functions makes KAN and MLP
suitable for different tasks, resulting in functional differences between the
two models. To validate this hypothesis, we compared the performance of KAN
and MLP across various tasks and delineated the tasks each model suits. To
ensure a fair comparison, we first derived the formulas for calculating the
number of parameters and FLOPs for KAN and MLP. In our experiments, we
controlled for either the same number of parameters or FLOPs to compare the
performance of KAN and MLP.

##  3 Number of Parameters of KAN and MLP

We use $d_{in}$ and $d_{out}$ to denote the input and output dimensions of the
neural network layer. We use $K$ to denote the order of the spline, which
corresponds to the parameter k of the official nn.Module KANLayer. It is the
order of the Polynomial basis in the spline function. We use $G$ to denote the
number of spline intervals, which corresponds the num parameter of the
official nn.Module KANLayer. It is the number of intervals of the B-spline,
before padding. It equals the number of control points - 1, before padding.
After padding, there should be $(K+G)$ functioning control points.

The learnable parameters in KAN include the B-spline control points, the
shortcut weights, the B-spline weights, and the bias. The total learnable
parameters are

${(d_{in}\times d_{out})\times(G+K+3)+d_{out}}.$

Correspondingly, the learnable parameters of one MLP layer is

${(d_{in}\times d_{out})+d_{out}}.$

##  4 FLOPs of KAN and MLP

In our evaluation, the FLOPs for any arithmetic operations are considered to
be 1, and the FLOPs for Boolean operations are considered to be 0. The
operations in De Boor-Cox algorithm at order 0 can be transformed into a
series of Boolean operations where it does not require floating-point
operations. Thus, theoretically, its FLOPs is 0. This is different from the
official KAN implementation, in which it transforms the Boolean data back to
Float data to conduct the operation. In our evaluation, the FLOPs is
calculated for one sample. The B-spline FLOPs with De Boor-Cox Iterative
Formulation implementation in the official KAN code is

$\displaystyle(d_{in}\times d_{out})\times$ $\displaystyle[9\times
K\times(G+1.5\times K)+2\times G-2.5\times k-1].$

Together with the FLOPs of the shortcut path and the FLOPs of merging the two
branches, the total FLOPs of one KAN layer is

$\displaystyle\text{FLOPs of non-linear function}\times d_{in}$
$\displaystyle\quad+(d_{in}\times d_{out})\times[9\times K\times(G+1.5\times
K)+2\times G-2.5\times K+3].$

Correspondingly, the FLOPs of one MLP layer is

$2\times{d_{in}\times d_{out}+\text{FLOPs of non-linear function}\times
d_{out}}.$

The difference between the FLOPs of a KAN layer and that of a MLP layer with
the same input dimension and output dimension can be written as

$\displaystyle\text{FLOPs of non-linear function}\times(d_{in}-d_{out})$
$\displaystyle\quad+(d_{in}\times d_{out})\times[9\times K\times(G+1.5\times
K)+2\times G-2.5\times K+1].$

If the MLP also does the non-linear operation first, the first term is zero.

##  5 Experiments

Our objective is to compare the performance differences between KAN and MLP
under the same number of parameters or FLOPs. Our experiments cover various
tasks including machine learning, computer vision, natural language
processing, audio processing, and symbolic formula representing. All
experiments used the Adam optimizer with a batch size of 128, and learning
rates of 1e-3 or 1e-4. All experiments are conducted on one RTX3090 GPU.

###  5.1 Performance Comparison

Figure 2: Performance comparison between KAN and MLP on Machine Learning
datasets controlling the number of parameters.page Figure 3: Performance
comparison between KAN and MLP on Machine Learning datasets controlling
FLOPs.page

Machine Learning. We conduct experiments on 8 machine learning datasets. We
use KAN and MLP with one or two hidden layers. The input and output dimensions
of the neural networks were adjusted according to the datasets. The hidden
layer widths for MLP were 32, 64, 128, 256, 512, or 1024, with GELU or ReLU as
the activation functions, and normalization layers were used in the MLP. For
KAN, the hidden layer widths were 2, 4, 8, or 16, the number of B-spline grids
was 3, 5, 10, or 20, and the B-spline degrees were 2, 3, or 5. Since the
original KAN architecture does not include normalization layers, to balance
the potential advantage from the normalization layers in MLP, we increased the
range of KAN’s spline function. In addition to the range of [-1,1] used in the
original paper, we also experimented with ranges of [-2,2] and [-4,4]. All
experiments are trained for 20 epochs. The best accuracy on the testing set
during the training is recorded. The upper envelope of all the recorded points
is plotted in the fig:ml_para and fig:ml_flops. On machine learning datasets,
MLP generally maintains an advantage. In our experiments on eight datasets,
MLP outperformed KAN on six of them. However, we also observed that on one
dataset, the performance of MLP and KAN was nearly equivalent, and on another
dataset, KAN outperformed MLP. For these two datasets, we will conduct an
architecture ablation in the next subsection to analyze the reasons behind
KAN’s advantages. Overall, MLP still holds a general advantage over KAN on
machine learning datasets.

Figure 4: Performance comparison between KAN and MLP on Computer Vision
datasets controlling the number of parameters.page Figure 5: Performance
comparison between KAN and MLP on Computer Vision datasets controlling
FLOPs.page

Computer Vision. We conduct experiments on 8 computer vision datasets. We use
KAN and MLP with one or two hidden layers. The input and output dimensions of
the neural networks were adjusted according to the datasets. The hidden layer
widths for MLP were 32, 64, 128, 256, 512, or 1024, with GELU or ReLU as the
activation functions, and no normalization layers were used. For KAN, the
hidden layer widths were 2, 4, 8, or 16, the number of B-spline grids was 3,
5, 10, or 20, and the B-spline degrees were 2, 3, or 5. All experiments are
trained for 20 epochs. The best accuracy on the testing set during the
training is recorded. The upper envelope of all the recorded points is plotted
in the fig:vision_para and fig:vision_flops. For the computer vision datasets,
the conductive bias introduced by KAN’s spline functions was not effective, as
its performance consistently fell short of MLP with the same number of
parameters or FLOPs.

Figure 6: Performance comparison between KAN and MLP on audio and text
datasets controlling the number of parameters.page Figure 7: Performance
comparison between KAN and MLP on audio and text datasets controlling
FLOPs.page

Audio and Natural Language. We conduct experiments on 2 audio classification
and 2 text classification datasets. We use KAN and MLP with one or two hidden
layers. The input and output dimensions of the neural networks were adjusted
according to the datasets. The hidden layer widths for MLP were 32, 64, 128,
256, 512, or 1024, with GELU or ReLU as the activation functions, and
normalization layers were used in the MLP. For KAN, the hidden layer widths
were 2, 4, 8, or 16, the number of B-spline grids was 3, 5, 10, or 20, the
B-spline degrees were 2, 3, or 5, and the B-spline range is [-1,1], [-2,2] or
[-4,4]. All experiments are trained for 20 epochs, except on the UrbanSound8K
dataset, on which the models are trained for 40 epochs. The best accuracy on
the testing set during the training is recorded. The upper envelope of all the
recorded points is plotted in the fig:audio_text_para and
fig:audio_text_flops. On both two audio datasets, MLP outperformed KAN. In
text classification tasks, MLP maintained an advantage on the AG News dataset.
However, on the CoLA dataset, there was no significant difference in
performance between MLP and KAN. When controlling for the same number of
parameters, KAN appeared to have an advantage on the CoLA dataset.
Nevertheless, due to the high FLOPs required by KAN’s spline functions, this
advantage did not persist in experiments controlling for FLOPs. When FLOPs
were controlled, MLP seemed to be superior. Thus, there is no consistent
answer as to which is better on the CoLA dataset. Overall, MLP remains a
better choice for audio and text tasks.

Figure 8: Performance comparison between KAN and MLP for symbolic formula
representing controlling the number of parameters.page Figure 9: Performance
comparison between KAN and MLP for symbolic formula representing controlling
FLOPs.page

Symbolic Formula Representing. We compared the differences between KAN and MLP
on 8 symbolic formula representing tasks. The functions to be fitted were
sourced from Section 3.2 of the original KAN paper. We use KAN and MLP with
one to four hidden layers. The input and output dimensions of the neural
networks were adjusted according to the datasets. The hidden layer widths for
MLP were 5, 50, or 100, with GELU or ReLU as the activation functions, and no
normalization layers were used in the MLP. For KAN, the hidden layer width was
5, the number of B-spline grids was 3, 5, 10, or 20, and the B-spline degrees
were 2, 3, or 5. All experiments are trained for 500 epochs. The best RMSE on
the testing set during the training is recorded. The lower envelope of all the
recorded points is plotted in the fig:special_para and fig:special_flops. When
controlling for the number of parameters, KAN outperformed MLP on 7 out of 8
datasets. When controlling for FLOPs, due to the additional computational
complexity introduced by the spline functions, KAN’s performance was roughly
equivalent to MLP, outperforming MLP on two datasets and underperforming on
one. Overall, for symbolic formula representation tasks, KAN performed better
than MLP.

###  5.2 Architecture Ablation

From the above experiments, we can conclude that KAN and MLP indeed have
functional differences. KAN is more suitable for task symbolic formula
representing, while MLP demonstrates advantages in machine learning, computer
vision, NLP, and audio processing. Next, we perform ablation studies on the
architecture of KAN and MLP to determine which specific components contribute
to their differences.

We conducted ablation experiments on two computer vision datasets and two
machine learning datasets. The architectures included in the ablation and
their relationship are plotted in fig:archs. KAN is a mix of KAN Layers and
fully-connected Layers, thus the first architecture we ablate is built by
purely stacking KAN Layers without fully-connected Layers. Because the KAN
Layer is actually a fully-connected Layer with the special B-spline activation
before the linear transformation. Thus, we also compare with MLP with B-spline
activation before or after the linear transformation.

Figure 10: Architectures Included in the Ablation.page Figure 11: Architecture
Ablation from MLP to KAN.page Figure 12: Performance comparison between KAN
and MLP with spline activation for symbolic formula representing controlling
the number of parameters.page

The observations are twofold. (1) On the computer vision datasets, for MLP
models, using spline activation functions brought little improvement. However,
the higher computational cost of spline functions makes it a worse choice than
conventional ReLU or GELU activation functions. (2) However, on the other
hand, for machine learning tasks, replacing the activation functions in MLP
with spline functions resulted in a significant performance boost. Initially,
on these two datasets, MLP’s performance was inferior to KAN, but after
substituting the activation function with a spline function, MLP’s performance
became comparable to KAN. This indicates that KAN’s performance improvement on
machine learning datasets primarily stems from the use of spline activation
functions. Whether the linear transformation is applied before the spline
function, or vice versa, does not significantly affect the final performance.
Whether the spline activation is used on all input-output pairs or only on the
inputs or outputs does not significantly affect the performance.

We also evaluated the performance of MLP using B-spline activation functions
on symbolic formula representing. In this experiment, the hidden layer width
of MLP was set to 10 or 20 to balance the additional parameters and FLOPs
introduced by the B-spline function. All other settings were the same as in
the previous symbolic formula representing experiments. The results are shown
in fig:arch_special_para and fig:arch_special_flops. In the previous symbolic
formula representation experiments, KAN’s performance is overall superior to
that of MLP. However, with B-spline activation functions, MLP’s performance in
all symbolic formula representing tasks can either surpass or match that of
KAN. This fully validates our hypothesis that the functional differences
between KAN and MLP stem from the different activation functions they use.
These different activation functions make the two architectures suited for
different tasks.

Figure 13: Performance comparison between KAN and MLP with Spline activation for symbolic formula representing controlling FLOPs.page #Parameters | KAN | MLP
---|---|---
$\overline{\text{ACC}}$ | Backward | T1 Acc | T2 Acc | T3 Acc |  $\overline{\text{ACC}}$ | Backward | T1 Acc | T2 Acc | T3 Acc
0.4M | 31.70 | -63.18 | 0.00 | 0.00 | 95.10 | 75.58 | -9.20 | 74.45 | 64.63 | 87.67
0.3M | 29.82 | -59.15 | 0.00 | 0.00 | 89.46 | 72.84 | -13.00 | 65.40 | 65.92 | 87.20
0.2M | 26.58 | -63.61 | 0.00 | 0.00 | 79.73 | 64.70 | -12.87 | 60.53 | 52.12 | 81.45
0.1M | 20.39 | -50.39 | 0.00 | 0.00 | 61.18 | 62.93 | -5.67 | 58.21 | 57.73 | 72.84
FLOPs | KAN | MLP
$\overline{\text{ACC}}$ | Backward | T1 Acc | T2 Acc | T3 Acc |  $\overline{\text{ACC}}$ | Backward | T1 Acc | T2 Acc | T3 Acc
3.7M | 31.96 | -63.76 | 0.00 | 0.00 | 95.88 | 66.98 | -29.02 | 50.49 | 55.03 | 95.41
1.6M | 31.52 | -63.28 | 0.00 | 0.00 | 94.56 | 74.93 | -16.25 | 66.19 | 66.47 | 92.13
1.3M | 29.90 | -60.09 | 0.00 | 0.00 | 89.70 | 78.06 | -13.79 | 70.58 | 72.50 | 91.11
0.8M | 28.09 | -55.14 | 0.00 | 0.00 | 84.26 | 75.58 | -9.20 | 74.45 | 64.63 | 87.67
Table 1: Performance comparison between KAN and MLP under the continual
learning setup.page

###  5.3 Continual Learning

The original paper of KAN validated that KAN performs better in the continual
learning of one-dimensional functions. We further verified this in computer
vision, by constructing a more standard class-incremental setup. We divided
the MNIST dataset into three tasks according to digit: the first task involved
classifying digits 0, 1, and 2; the second task involved classifying digits 3,
4, and 5; and the third task involved classifying digits 6, 7, 8, and 9. We
trained KAN and MLP models on these three tasks sequentially. The training
hyperparameters were the same as those used in the vision experiments, but the
training epoch for each task was set to 1. The results are summarized in the
tab:continual_learning. It is evident that KAN did not exhibit an advantage in
continual learning tasks for computer vision. Its speed of forgetting is
faster than that of MLP. After the training of all three tasks, KAN’s accuracy
on the first and second tasks dropped to 0, achieving relatively high accuracy
only on the third task. In contrast, MLP was able to retain acceptable
accuracy on the first two tasks. The methods for calculating the average
accuracy and backward scores are consistent with those in [19].

##  6 Related Works

Significant improvements have been made to KAN networks. In KAN, the nonlinear
activation originally present in MLP is implemented using B-spline functions.
Due to the locality and adjustable number of grids in B-splines, KAN networks
can achieve a certain degree of dynamic network architecture and continual
learning. Numerous studies have replaced B-splines with Chebyshev polynomials
[18], wavelet functions [11], Jacobi polynomials [9], orthogonal polynomials
[10], etc., imparting different properties to KAN networks. More efforts have
been made to combine KAN networks with existing popular network structures for
various applications. For instance, integrating KAN with convolutional
networks and vision transformer networks to enhance KAN’s performance in
classification and other vision tasks [12, 2, 3, 4, 5, 6, 7, 8], combining KAN
with U-Net for medical image segmentation and generation [13], merging KAN
with GNN for graph-related tasks [13], or integrating KAN with NeRF networks
for 3D reconstruction [1]. Different from these works, this paper does not
introduce any improvements over KAN. Instead, we provide a fairer and
comprehensive comparison between KAN and MLP to offer insights for future
research.

##  7 Conclusion

In this work, we first mathematically compared the forward process of KAN and
MLP. We found that KAN can be seen as a special type of MLP, with its
uniqueness stemming from the use of learnable B-spline functions as activation
functions. We hypothesize that this difference in activation functions is the
primary reason for the functional differences between KAN and MLP. To test
this hypothesis, we compared the performance of KAN and MLP on symbolic
formula representing, machine learning, computer vision, natural language
processing, and audio processing tasks, controlling for the same number of
parameters or FLOPs. Our experiments revealed that KAN only had an advantage
in symbolic formula representing, while MLP outperformed KAN in other tasks.
Furthermore, we found that after replacing MLP’s activation function with the
learnable B-spline, MLP outperformed or was comparable to KAN across all
tasks. Lastly, we discovered that under standard class-incremental learning
settings, KAN exhibited more severe forgetting issues compared to MLP.

## References

  * XKA [2024] X-kanerf.  https://github.com/lif314/X-KANeRF.git, 2024.
  * con [2024a] Convolutional-kans.  https://github.com/AntonioTepsich/Convolutional-KANs.git, 2024a.
  * con [2024b] torch-conv-kan.  https://github.com/IvanDrokin/torch-conv-kan.git, 2024b.
  * con [2024c] convkan.  https://github.com/StarostinV/convkan.git, 2024c.
  * con [2024d] Ka-conv.  https://github.com/XiangboGaoBarry/KA-Conv.git, 2024d.
  * con [2024e] Kan-conv2d.  https://github.com/omarrayyann/KAN-Conv2D.git, 2024e.
  * con [2024f] Cnn-kan.  https://github.com/jakariaemon/CNN-KAN.git, 2024f.
  * con [2024g] Convkan3d.  https://github.com/FirasBDarwish/ConvKAN3D.git, 2024g.
  * jac [2024] Kolmogorov-arnold networks (kan) using jacobi polynomials instead of b-splines.  https://github.com/SpaceLearner/JacobiKAN.git, 2024.
  * ort [2024] Kolmogorov-arnold networks (kan) using orthogonal polynomials instead of b-splines.  https://github.com/Boris-73-TA/OrthogPolyKANs.git, 2024.
  * Bozorgasl and Chen [2024] Zavareh Bozorgasl and Hao Chen.  Wav-kan: Wavelet kolmogorov-arnold networks, 2024.
  * Chen et al. [2024] Ziwen Chen, Gundavarapu, and WU DI.  Vision-kan: Exploring the possibility of kan replacing mlp in vision transformer.  https://github.com/chenziwenhaoshuai/Vision-KAN.git, 2024.
  * Li et al. [2024] Chenxin Li, Xinyu Liu, Wuyang Li, Cheng Wang, Hengyu Liu, and Yixuan Yuan.  U-kan makes strong backbone for medical image segmentation and generation, 2024.
  * Liu et al. [2024] Ziming Liu, Yixuan Wang, Sachin Vaidya, Fabian Ruehle, James Halverson, Marin Soljačić, Thomas Y. Hou, and Max Tegmark.  Kan: Kolmogorov-arnold networks, 2024.
  * McCulloch and Pitts [1943] Warren S McCulloch and Walter Pitts.  A logical calculus of the ideas immanent in nervous activity.  _The bulletin of mathematical biophysics_ , 5:115–133, 1943.
  * Rosenblatt [1958] Frank Rosenblatt.  The perceptron: a probabilistic model for information storage and organization in the brain.  _Psychological review_ , 65(6):386, 1958.
  * Rumelhart et al. [1986] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams.  Learning representations by back-propagating errors.  _nature_ , 323(6088):533–536, 1986.
  * SS and R [2024] Sidharth SS and Gokul R.  Chebyshev polynomial-based kolmogorov-arnold networks: An efficient architecture for nonlinear function approximation, 2024.
  * Wang et al. [2024] Liyuan Wang, Xingxing Zhang, Hang Su, and Jun Zhu.  A comprehensive survey of continual learning: Theory, method and application, 2024.


# LOQA: Learning with Opponent Q-Learning Awareness

Antiquus S. Hippocampus, Natalia Cerebro & Amelie P. Amygdale
Department of Computer Science
Cranberry-Lemon University
Pittsburgh, PA 15213, USA
<EMAIL_ADDRESS>
&Ji Q. Ren & Yevgeny LeNet
Department of Computational Neuroscience
University of the Witwatersrand
Joburg, South Africa
<EMAIL_ADDRESS>
Coauthor
Affiliation
Address
email Use footnote for providing further information about author (webpage,
alternative address)— _not_ for acknowledging funding agencies. Funding
acknowledgements go at the end of the paper.

###### Abstract

In various real-world scenarios, interactions among agents often resemble the
dynamics of general-sum games, where each agent strives to optimize its own
utility. Despite the ubiquitous relevance of such settings, decentralized
machine learning algorithms have struggled to find equilibria that maximize
individual utility while preserving social welfare. In this paper we introduce
Learning with Opponent Q-Learning Awareness (LOQA) , a novel, decentralized,
reinforcement learning algorithm tailored to optimizing an agent’s individual
utility while fostering cooperation among adversaries in partially competitive
environments. LOQA assumes the opponent samples actions proportionally to
their action-value function Q. Experimental results demonstrate the
effectiveness of LOQA at achieving state-of-the-art performance in benchmark
scenarios such as the Iterated Prisoner’s Dilemma and the Coin Game. LOQA
achieves these outcomes with a significantly reduced computational footprint,
making it a promising approach for practical multi-agent applications.

##  1 Introduction

What happens if each of us delegate all of our decision makings to RL agents
that act on our behalf and are optimized to maximize our return? This is an
important question as autonomous agents are already being integrated into our
society. They are making decisions for us rl-in-finance; rl-in-healthcare; rl-
in-medical-imaging, simulating policy proposals for climate change
negotiations zhang2022ai and driving on behalf of their owner. To answer this,
extrapolating current research indicates a potentially concerning scenario:
countries could fail to reach climate deals, research labs might not share
their tools with other research laboratories, and farmers may exploit shared
water resources for their own plant growth. The reason behind these gloomy
predictions is that we have substantial evidence that current naive MARL
agents fail to solve social dilemmas which severely limits their practicality.

Naive MARL agents cannot reach reciprocation-based cooperation even in simple
matrix environments. Two naive RL agents optimizing their return in an
environment as simple as Iterated Prisoner’s Dilemma (IPD) converge to always
defect(AD) policies. They miss the tit-for-tat(TFT) solution which has a
higher return than the AD and enables conditional cooperation. Although
optimizing agents for the shared reward looks like a simple fix it leads to
exploitable agents that always cooperate(AC). Reciprocation is key. Therefore,
algorithms that enable emergence of reciprocation hold tremendous theoretical
and practical value.

Naive RL algorithms assume the opponents’ policies are static in each policy
update. By not accounting for the opponents’ optimizing their return the naive
RL agent misses the potential to shape the learning of the opponents. This
shaping is possible because The outcome of each opponent is determined not
only by their own actions but also of the agent vonNeumann1928. LOLA
Foerster2018a, POLA, M-FOS, Good Shepherd, and Meta-Value enable emergent
reciprocation by shaping the opponents’ learning 11todo: 1cite these papers.

However, the existing algorithms don’t scale. LOLA and POLA differentiate
through an assumed naive gradient step of the opponent by explicit
computations graphs of the opponent’s optimization. For neural network
policies that need many steps to optimize their return it means they need
thousands of explicit optimization step roll-outs. Next, the agent
differentiates through this complex computational graph, which leads to huge
computational and memory costs and also higher order-gradients. M-FOS, Good-
Shepherd, Meta-Value, and others(22todo: 2which others) shape the opponent by
constructing a meta-game in the space of agent policies. They define the
problem as a meta-state over the product space of policies of the agent and
opponent, and learns a meta-policy that maps from the meta-state to the
agent’s updated policy. Therefore they need to learn the dynamics of multiple
agents simultaneously being optimized to guide the optimization of the
opponent afterwards. This is very challenging in Deep RL as learning the
optimization dynamics of multiple neural network policies is complex, hard,
and sample inefficient. While, in fully competitive and fully cooperative
large scale environments RL algorithms have super-human performance, the
state-of-the-art in solving social dilemmas is solving the 3x3 coin game. This
shows the need for faster algorithms with less computational and memory
requirements. In other words, more scalable algorithms.

In this paper we introduce Q-value Shaping (QS). QS is an scalable algorithm
that side-steps both building explicit iterative computational graphs of
optimization steps or learning the meta-state dynamics altogether by making a
key observation. The optimization step of each opponent is shaped by that
opponent’s return. As the return of every opponent is dependent on the agent
actions in a multi agent environment, the agent can shape the optimization of
opponents, by shaping their return. Explicitly, each opponent is assumed to
optimize its policy to choose the action with the highest action-value. This
action-value is differentiable w.r.t the agent parameters. QS build a
steerable approximated policy of the opponent by a softmax over its action-
values which is close to (TODO: should mention sac). QS shapes the opponent’s
return, and the optimization step of the opponent will be shaped indirectly as
a result. Therefore, QS does not involve neither building complex optimization
computational graphs nor second order gradients which leads to significant
computational efficiency.

We experiment with QS on IPD to show its capability to solve simple
environments and on the coin game to show its superior scalability as solving
the 3x3 coin game is the state of the art in this subfield. We showcase the
scalability of QS in two directions: 1) QS reached reciprocation-based
cooperation 30 times faster than POLA (SOTA) on 3x3 coin game. 2) QS reaches
strong reciprocation-based cooperation in 7x7 coin game where POLA fails and
just learns always defect strategies. We summarize our contributions as
follows:

  1. 1.

We propose Q-value Shaping(QS) which shapes opponent’s learning via shaping
its action-values.

  2. 2.

QS does not involve computing opponent optimization steps, let alone
differentiating through the constructed computational graph, high-order
gradients, and learning optimization dynamics of multiple agents all of which
hindered the scalability of previous methods significantly.

  3. 3.

We show QS reaches the same performance the previous SOAT algorithm, POLA, on
the SOTA benchmark, 3x3 coin game 30 times faster using the same hardware
setup. Also, QS solves the 7x7 coin game where POLA fails.

##  2 Background

We consider general-sum, $n$-player, Markov games, also referred as stochastic
games Shapley1953. Markov games are defined by a tuple
$\mathcal{M}=(N,\mathcal{S},\mathcal{A},P,\mathcal{R},\gamma)$ where
$\mathcal{S}$ denotes the state space,
$\mathcal{A}:=\mathcal{A}^{1}\times\ldots\times\mathcal{A}^{n}$, is the joint
action space of all players,
$P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$, defines a mapping from
every state and joint action to a probability distribution over states,
$\mathcal{R}=\\{r^{1},\ldots,r^{n}\\}$ is the set of reward functions where
each $r^{i}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ maps every state and
joint action to a scalar return and $\gamma\in[0,1]$ is the discount factor.

We use the notation and definitions for standard RL algorithms of Agarwal2021.
Consider two agents, 1 (agent) and 2 (opponent) that interact in an
environment with neural network policies
$\pi^{1}:=\pi(\cdot|\cdot;\theta^{1})$, $\pi^{2}:=\pi(\cdot|\cdot;\theta^{2})$
parameterized by $\theta^{1}$ and $\theta^{2}$ respectively. We denote $\tau$
to be a trajectory with initial state distribution $\mu$ and probability
measure $\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}$ given by

$\displaystyle\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}(\tau)=\mu(s_{0})\pi^{1}(a_{0}|s_{0})\pi^{2}(b_{0}|s_{0})P(s_{1}|s_{0},a_{0},b_{0})\ldots$

here $b\in\mathcal{A}^{2}$ denotes the action of the second agent. In multi-
agent reinforcement learning, each agent seeks to optimize their expected
discounted return $R$, for agent 1 this is given by:

$\displaystyle
V^{1}(\mu):=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[R^{1}(\tau)\right]=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty}\gamma^{t}r^{1}(s_{t},a_{t},b_{t})\right]$

The key observation is that under the definitions above, $V^{1}$ is dependent
on the policy of agent 2 through the reward function
$r^{1}(s_{t},a_{t},b_{t})$. $V^{1}$ is thus differentiable with respect to the
parameters of agent 2 via the REINFORCE estimator (Williams1992)

$\begin{split}\nabla_{\theta^{2}}V^{1}(\mu)&=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[R^{1}(\tau)\sum_{t=0}^{\infty}\nabla_{\theta^{2}}\text{log
}\pi^{2}(b_{t}|s_{t})\right]\\\
&=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty}\gamma^{t}r^{1}(s_{t},a_{t},b_{t})\sum_{k<t}\nabla_{\theta^{2}}\text{log
}\pi^{2}(b_{k}|s_{k})\right]\end{split}$ (1)

we will rely on this observation to influence the opponent’s $Q$ value and
incentivize reciprocity-based cooperation in partially competitive
environments.

##  3 Related Work

###  3.1 Opponent Shaping

Learning with opponent learning awareness (LOLA), (Foerster2018a) introduces
the concept of opponent shaping, i.e. the idea of steering the other agent
throughout its learning process. LOLA assumes that the opponent is a naive
learner and attempts to shape it by considering one step in its optimization
process. Rather than optimizing the value under the current policies at the
current iteration $i$, $V^{1}(\theta_{i}^{1},\>\theta_{i}^{2})$, LOLA
optimizes $V^{1}(\theta_{i}^{1},\>\theta_{i}^{2}+\Delta\theta_{i}^{2})$ where
$\Delta\theta_{i}^{2}$ is a learning step of the opponent.
$\Delta\theta_{i}^{2}$ is as a function that depends on the agent’s parameters
and that is thus differentiable with respect to $\theta^{1}$. Since the
derivative of function
$V^{1}(\theta_{i}^{1},\>\theta_{i}^{2}+\Delta\theta_{i}^{2})$ is difficult to
compute, the authors consider the surrogate value given by its first order
Taylor expansion. POLA, (Zhao2022) builds an idealized version LOLA that,
unlike its predecessor, is invariant to the parameterization of the policy. In
a similar fashion to proximal policy optimization (PPO) (Schulman2017), each
agent increases the probability of actions that increase their expected
return, while trying to minimize the $l_{2}$ distance between the updated
policy and the old policy. This combined objective of maximizing the return
and minimizing the $l_{2}$ distance in policy space is equivalent to the
Proximal Point method, hence the name Proximal-LOLA or POLA. Other
modifications to the original LOLA algorithm attempt to resolve its
shortcomings. Consistent learning with opponent learning awareness (COLA),
(Willi2022) attempts to resolve the inherent inconsistency of LOLA assuming
that the other agent is a naive learner instead of another LOLA agent. Stable
opponent shaping (SOS), (Letcher2021) introduces an interpolation between LOLA
and a more stable variant called _look ahead_ , which has strong theoretical
convergence guarantees.

###  3.2 Meta Learning

Other methods have been used to generate agents that have near optimal
behavior in social dilemmas. First used by Alshedivat2018 for this setting,
meta learning redefines the MARL problem as a meta-game in the space of policy
parameters in an attempt to deal with the non-stationary nature of the
environment. In this meta-game, the meta-state is the joint policy, the meta-
reward is the return on the underlying game, and a meta-action is a change to
the inner policy (i.e. the policy in the original game). Model free opponent
shaping (M-FOS) (Lu2022) applies policy gradient methods to this meta-game to
find a strong meta-policy. Meta-Value Learning (Cooijmans2023) applies value
learning to model the long-term effects of policy changes, and uses the
gradient of the value as an improvement direction.

##  4 Social Dilemmas

Social dilemmas are a type of decision problem where each party’s miopic
efforts to maximize their own benefit lead to a less favorable outcome
compared to when all parties cooperate. Designed primarily as thought
experiments, these dilemmas demonstrate the trade-offs that are often inherent
in multi-agent decision-making scenarios. As such, they have been used to
model real-life situations in diverse fields such as economics, ecology and
policy making. One example of such a decision problem is the famous Iterated
Prisoner’s Dilemma (IPD).

#### The Prisoner’s Dilemma (PD)

PD is a game in which each of the two agents or prisoners must decide to
either cooperate with one another or defect. The dilemma the prisoners face
originates from the reward structure, given in Table 1. With with reward
structure, a rational agent will choose to defect no matter what the other
agent chooses. As a result, both agents become locked in the defect-defect
Nash equilibrium, even though they would achieve greater utility by both
choosing to cooperate.

Agent 1 Agent 2 | Cooperate | Defect
---|---|---
Cooperate | $(-1,-1)$ | $(-3,\phantom{+}0)$
Defect | $(\phantom{+}0,-3)$ | $(-2,-2)$
Table 1: Payoff (or reward) matrix for the Prisoner’s Dilemma game, where the
numbered pairs corresponds to the payoffs of Agent 1 and Agent 2 respectively.

#### Iterated Prisoner’s Dilemma (IPD)

As the name implies IPD is simply an (infinitely) repeated version of the
Prisoner’s Dilemma. Unlike standard PD, IPD offers some hope for rational
cooperative behaviour. Originally popularized by Axelrod1980, the IPD has been
used to model many hypothetical and real-world scenarios. It has also become a
popular test-bed for MARL algorithms attempting to achieve reciprocity based
cooperation policies. A simple but effective strategy in the IPD is _tit-for-
tat_ (TFT), which consists in cooperating at the first turn and copying the
opponent’s action thereafter.

#### The Coin Game

Initially described in (Lerer2018), the Coin Game is a grid world environment
in which two agents take turns taking coins. At the beginning of each episode
a coin of a particular color (red or blue), corresponding to that of one of
the two agents, spawns at a random location in the grid. Agents are rewarded
for any coin taken, but are punished if the other agent takes the coin
corresponding to their color. The reward structure of the Coin Game is
designed to incentivize cooperation between agents, as each one would be
better off if both take only the coin corresponding to their color. In such
way the Coin Game mirrors the IPD, therefore policies that _cooperate
reciprocally_ are highly desirable as they achieve better individual and
social outcomes. However unlike IPD, the Coin Game is embedded in a non-
trivial environment and requires non-trivial policy models. It can be seen as
an extension of IPD towards more complex and realistic scenarios.

##  5 Method Description

Intuitively, a change in either the agent’s or the opponent’s policy results
in a change in the probability measure over the trajectories that are observed
when both of them interact in an environment. Since the value function of the
_opponent_ is an expectation over said probability measure, it is controllable
by the _agent’s_ policy (and vice versa). LOQA leverages this observation to
exert influence over the policy that the opponent will learn.

As an illustration, consider an instance of the IPD game where a LOQA agent
and the opponent are initialized to be random agents, i.e. they samples
actions from a uniform distribution. If the LOQA agent increases its
probability of defection after the opponent defects, it implicitly decreases
the action-value function of the opponent for defecting. The opponent will
then learn this and reduce its probability of defecting. Similarly, if the
LOQA agent cooperates after the opponent cooperates, it increases the action-
value of cooperation for the opponent. In response, the opponent will learn to
cooperate more. This reciprocity-based cooperative behavior is the structure
behind tit-for-tat.

###  5.1 Modeling the Opponent’s Policy

LOQA relies on a key assumption about the opponent’s policy. Similar to Soft
Actor Critic (SAC) (Haarnoja2018), the assumption is that the opponents’
actions are sampled from a distribution that is proportional to its action-
value function $Q^{2}(\cdot)$. More formally, at time $t$, we can write this
assumption as

$\displaystyle\pi^{2}(b_{t}|s_{t})$
$\displaystyle\approx\frac{\text{exp}(Q^{2}(s_{t},b_{t}))}{\sum_{b^{\prime}}\text{exp}(Q^{2}(s_{t},b^{\prime}))}$

where $\pi^{1}(b|s):=\pi(b|s;\theta^{1})$ 33todo: 3Aaron: this isn’t in the
equation above so it’s confusing to say where … refers to the policy of the
agent and $\pi^{2}(b|s):=\pi(b|s;\theta^{2})$ refers to the policy of the
opponent, which are neural networks with parameters $\theta^{1}$ and
$\theta^{2}$. Similarly, $Q^{2}(s,b):=Q(s,b;\phi^{2})$ 44todo: 4Aaron: this
also isn’t in the equation above so it’s again confusing denotes the action-
value function of the opponent, which is a neural network with parameters
$\phi^{2}$.

More specifically we approximate $Q^{2}$ with Monte Carlo rollouts
$\mathcal{T}$ of length $T$, where every trajectory $\tau\in\mathcal{T}$,
$\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}$, starts at state $s_{t}$ with the
opponent taking action $b_{t}$

$\displaystyle\hat{Q}^{2}(s_{t},b_{t})$
$\displaystyle=\mathbb{E}_{\tau\sim\mathcal{T}}\left[R^{2}(\tau)|s=s_{t},b=b_{t}\right]$
$\displaystyle=\frac{1}{|\mathcal{T}|}\sum_{\tau\in\mathcal{T}}\sum_{k=t}^{T}\gamma^{k-t}r^{2}(s_{k},a_{k},b_{k})$

where $r^{2}(s,a,b)$ denotes the opponent’s reward at state $s$ after taking
action $b$ and the opponent taking action $a$. This empirical expectation of
the $Q$ function is controllable by the agent using the reinforce estimator

$\displaystyle\nabla_{\theta^{1}}\hat{Q}^{2}(s_{t},b_{t})=\mathbb{E}_{\tau\sim\mathcal{T}}\left[\sum_{k=t+1}^{T}\gamma^{k-t}r^{2}(s_{k},a_{k},b_{k})\sum_{j<k}\nabla_{\theta^{1}}\text{log
}\pi^{1}(a_{j}|s_{j})\right]$

The opponent’s policy evaluated at state $s_{t}$ can now be approximated using
the Monte Carlo rollout estimate $\hat{Q}^{2}$ and the action-value function
$Q^{2}$ as follows

$\hat{\pi}^{2}(b_{t}|s_{t}):=\frac{\text{exp}(\hat{Q}^{2}(s_{t},b_{t}))}{\text{exp}(\hat{Q}^{2}(s_{t},b_{t}))+\sum_{b^{\prime}\neq
b_{t}}\text{exp}(Q^{2}(s_{t},b^{\prime}))}$ (2)

Notice that we assume access to the opponent’s real action-value function
$Q^{2}$. To have a fully decentralized algorithm we can simply replace $Q^{2}$
with the agent’s own estimate of the opponent’s action-value function. We now
integrate these ideas into the Actor-Critic formulation.

###  5.2 Opponent Shaping

In order to shape the opponent behavior, we factor in the opponent’s policy
approximation $\hat{\pi}^{2}$ as well as the agent’s policy $\pi^{1}$ in the
probability measure over trajectories. Adapting the original Actor-Critic
formulation (Konda2000) to the joint agent-opponent policy space we have:

$\displaystyle\nabla_{\theta^{1}}V^{1}(\mu)$
$\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{T}A^{1}(s_{t},a_{t},b_{t})\nabla_{\theta^{1}}\left(\text{log
}\pi^{1}(a_{t}|s_{t})+\underbrace{\text{log
}\pi^{2}(b_{t}|s_{t})}_{=0}\right)\right]$

where $A^{1}(s_{t},a_{t},b_{t})$ is the advantage of the agent, and $\pi^{2}$
is constant w.r.t. $\theta_{1}$. LOQA approximates the opponent’s policy using
Equation 2. This approximated policy is differentiable with respect to agent
parameters since it is computed based on the opponent’s action-value, which is
also differentiable (see Equation 1). Consequently, a second term emerges in
LOQA’s update

$\nabla_{\theta^{1}}V^{1}(\mu)=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{T}A^{1}(s_{t},a_{t},b_{t})\nabla_{\theta^{1}}\left(\text{log
}\pi^{1}(a_{t}|s_{t})+\text{log }\hat{\pi}^{2}(b_{t}|s_{t})\right)\right]$ (3)

The first log term comes from the Actor-Critic update and the second log term
is a shaping component that pushes the opponent’s return in a beneficial
direction for the agent (in policy space). This second term comes from the
assumption that the opponent’s policy can be influenced by the agent’s
parameters. For a derivation refer to section F in the appendix.

In practice we use DiCE (Foerster2018b) and loaded-DiCE (Farquhar2019) on the
action-value estimate $\hat{Q}^{2}$ to compute the gradient
$\nabla_{\theta^{1}}\text{log }\hat{\pi}^{2}$ and reduce its variance. For
implementation details, please refer to section B in the appendix.

Algorithm 1 LOQA

Initialize: Discount factor $\gamma$, agent 1 action-value parameters
$\phi^{1}$, target action-value parameters $\phi_{\text{target}}^{1}$, actor
parameters $\theta^{1}$, agent 2 action-value parameters $\phi^{2}$, target
action-value parameters $\phi_{\text{target}}^{2}$, actor parameters
$\theta^{2}$

for iteration$=1,2,\ldots$ do

Run policies $\pi^{1}$ and $\pi^{2}$ for $T$ timesteps in environment and
collect trajectory $\tau$

$L_{Q}^{1}\leftarrow 0$, $L_{Q}^{2}\leftarrow 0$

for $t=1,2,\ldots,T-1$ do

$L_{Q}^{1}\leftarrow L_{Q}^{1}+$ HUBER_LOSS$(r_{t}+\gamma
Q_{\text{target}}^{1}(s_{t+1},a_{t+1})-Q^{1}(s_{t},a_{t}))$

$L_{Q}^{2}\leftarrow L_{Q}^{2}+$ HUBER_LOSS$(r_{t}+\gamma
Q_{\text{target}}^{2}(s_{t+1},b_{t+1})-Q^{2}(s_{t},b_{t}))$

end for

Optimize $L_{Q}^{1}$ w.r.t. $\phi^{1}$ and $L_{Q}^{2}$ w.r.t. $\phi^{2}$ with
optimizer of choice

Compute advantage estimates $\\{A_{1}^{1},\ldots,A_{T}^{1}\\}$,
$\\{A_{1}^{2},\ldots,A_{T}^{2}\\}$

$L_{a}^{1}\leftarrow$
LOQA_ACTOR_LOSS$(\tau,\pi^{1},\gamma,\\{A_{1}^{1},\ldots,A_{T}^{1}\\})$

$L_{a}^{2}\leftarrow$
LOQA_ACTOR_LOSS$(\tau,\pi^{2},\gamma,\\{A_{1}^{2},\ldots,A_{T}^{2}\\})$

Optimize $L_{a}^{1}$ w.r.t. $\theta^{1}$ and $L_{a}^{2}$ w.r.t. $\theta^{2}$
with optimizer of choice

end for

Algorithm 2 LOQA_ACTOR_LOSS

Input: Trajectory $\tau$ of length $T$, actor policy $\pi^{i}$, opponent
action-value function $Q^{-i}$, discount factor $\gamma$, advantages
$\\{A_{1}^{i},\ldots,A_{T}^{i}\\}$

$L_{a}\leftarrow 0$

for $t=1,2,\ldots,T-1$ do

$\hat{Q}^{-i}(s_{t},b_{t})\leftarrow\sum_{k=t}^{T}\gamma^{k-t}r^{-i}(s_{k},a_{k},b_{k})$
$\triangleright$ $r^{-i}$ made differentiable using DiCE

Compute $\hat{\pi}^{-i}$ using $\hat{Q}^{-i}(s_{t},b_{t})$ and
$Q^{-i}(s_{t},b_{t})$ according to equation (2)

$L_{a}\leftarrow L_{a}+A_{t}^{i}\>\left[\text{log
}\pi^{i}(a_{t}|s_{t})+\text{log }\hat{\pi}^{-i}(b_{t}|s_{t})\right]$

end for

return: $L_{a}$

###  5.3 Self Play and Replay Buffer of Previous Agents

Because the environments are symmetric we can use _self-play_ to train a
single LOQA agent against itself. We also maintain a replay buffer and, for
each optimization step (which requires generating environment rollouts), we
sample uniformly from previously encountered agents. This increases the
diversity of the opponents the agent faces in the training. The replay buffer
has a certain capacity and receives a new agent every $n$th iteration where
$n$ is a hyperparameter.

##  6 Experiments

We consider two general-sum environments to evaluate LOQA against the current
state-of-the-art, namely, the Iterated Prisoner’s Dilemma (IPD) and the Coin
Game. We only compare with the POLA algorthm, as it is, to the best of our
knowledge, the only method that generates strong reciprocity-based cooperative
policies on the Coin Game.

###  6.1 Iterated Prisoner’s Dilemma

We train an agent consisting of a sigmoid over logits for each possible state
in the one-step history IPD. There are 5 possible states in this
configuration, namely START (the starting state), CC, CD, DC and DD where C
stands for cooperation and D stands for defection. The training is done for
4500 iterations (approximately 15 minutes on an Nvidia A100 gpu) using a batch
size of 2048. We empirically observe that a LOQA agent is able to reach a tit-
for-tat like policy as shown by looking at the probability of cooperation at
each state. We believe that the probabilities are not fully saturated for two
reasons. First, the normalization over the action-values in the opponent’s
policy approximation makes it numerically impossible to reach a probability of
one for either action. Second, we observed that after some time the
trajectories become homogeneous ”always cooperate” trajectories that
ultimately degenerate the quality of the resulting policy by making it less
likely to retaliate after a defection by the opponent.

Figure 1: Probability of cooperation of a sigmoid LOQA agent at each possible
state in the one-step history IPD after 7000 training iterations. LOQA agents’
resulting policy is similar to tit-for-tat, a policy that cooperates at the
first step and copies the previous action of the opponent at subsequent time-
steps.

###  6.2 Coin Game

Like (Zhao2022), we use a GRU policy that has access to the current
observation of the game plus both agents’ actions in the previous turn to
train a LOQA agent in the Coin Game. We run trajectories of length 50 with a
discount factor $\gamma=0.7$ in parallel with a batch size of 8192. For
evaluation we run 10 seeds of fully trained LOQA and POLA agents for 50
episodes in a league that involves other agents and plot the time-averaged
reward. The results are shown in Figure 2. We also experimented with ablations
of LOQA that either removed self-play during training or removed the replay
buffer of past policy weights to train against. These two ablations showed
that these two elements, although not essential, improve the performance of
LOQA agents in the Coin Game by making them more cooperative with themselves
and less exploitable by always-defect agents. For details refer to the
Appendix section C.

In Figure 2, we observe that LOQA agents are able to cooperate with themselves
as indicated by the high average reward of 0.3 which is close to the 0.35 of
an always cooperate agent against itself. LOQA agents are able to achieve high
social welfare without being exploited by an always defect agent as they
achieve an average reward of -0.05, which is comparable to POLA’s own -0.03.
More importantly our agents are fully trained after only 2 hours of compute
time in an Nvidia A100 gpu, compared to the 8 hours of training it takes POLA
to achieve the results shown in Figure 2. It should be noted that as compared
to IPD, in the Coin Game, cooperation and defection consist of sequences of
actions, therefore an agent must learn to take coins before learning whether
they should cooperate with their opponent or not. We also consider full
histories as opposed to one-step, making the state space significantly larger.

Figure 2: Average rewards after evaluating 10 fully trained LOQA and POLA
seeds against different agents in a 3x3 sized Coin Game lasting 50 episodes.
AC for always Cooperate, AD for always defect. Notice that a fully cooperative
agent achieves an average reward of 0.35 against itself. LOQA is able to
generate a policy that demonstrates reciprocity-based cooperation.

###  6.3 Scalability Experiments

In this section, we test POLA and LOQA on larger grid sizes in the Coin Game
to evaluate their scalability. As grid size increases, the average distance
between the agents and the coin also grows This added complexity challenges
the learning of reciprocal cooperative behavior. For example, when the
opponent takes the agent’s coin, the agent must learn to take multiple steps
to retaliate. This behavior is less likely to be discovered by random actions
on larger grids. Our experiments with different grid sizes illustrate LOQA’s
scalability properties compared to POLA.

In assessing the performance of the agents, we consider two metrics: the
achievement of a predetermined performance threshold and the time taken to
reach this threshold. For the latter, it is critical to acknowledge that the
conceptualization of a ’step’ differs between POLA and LOQA. The steps in POLA
encompass numerous inner optimization steps, rendering a direct comparison of
performance per step inconclusive. To facilitate an equitable comparison, we
employ the wall clock time of both algorithms, executed under identical
computational configurations (GPU, memory, etc.).

The thresholds are defined based on two principal criteria pertaining to a
reciprocity-based cooperative policy. Firstly, we evaluate the agent’s return
against an “Always Defect” opponent; this serves to test the cessation of
cooperation following a lack of reciprocation from the opponent. Secondly, we
consider the agents’ return against each other, which serves as a measure of
cooperative behavior. This dual-threshold approach is pragmatic as it discerns
the distinctive behaviors; an ‘Always Defect’ agent meets the first threshold
but fails the second, whereas an ‘Always Cooperate’ agent satisfies the second
but not the first. However, a policy resembling ‘Tit-for-Tat’ satisfies both
thresholds. Furthermore, as the grid size grows the average returns of agents
per step decrease since it takes longer to reach the coin. Therefore, it is
crucial to ensure our thresholds are consistent when evaluating for different
grid sizes.

We normalize the returns to make our thresholds standard over all grid sizes.
Specifically, we multiply the return by the maximum distance possible between
the agent and the coin for a given grid size. Since the grid is wrapped, the
normalization value $N$ is given by the Manhattan distance between the center
of the grid and one of the corners. We call this the normalized return and we
calculate our thresholds based on it. We have three thresholds for our
evaluation. The weak and medium thresholds are designed so that all the
algorithms are able to reach them. However, as LOQA reaches much higher return
on large grid sizes as compared to POLA, we set the strong threshold to a high
performance. The specification of the thresholds values is shown in Table 2.

Threshold | Normalized Return against Each Other | Normalized Return against Always Defect
---|---|---
Weak |  $\geq$0.05 |  $\geq$-1.2
Medium |  $\geq$0.1 |  $\geq$-0.5
Strong |  $\geq$0.2 |  $\geq$-0.2
Table 2: Thresholds based on two main criteria of a reciprocity-based
cooperative policy. The weak and medium thresholds are designed such that all
agents pass them, while the strong threshold represents good performance.
Figure 3: Wall clock time vs grid size for three seeds of LOQA and POLA on
reaching different thresholds. Each data point indicates the first time its
corresponding seed passed a certain threshold. The wall clock time is measured
in seconds. Red triangles indicate LOQA’s performance while blue circles
visualize LOQA’s performance. Dashed lines pass through the average time for
runs that passed for their respective algorithm.

The results of our experiments on larger grid sizes are illustrated in Figure
3. All LOQA runs meet the strong threshold for grid sizes up to 6, but at a
grid size of 7, one run falls short of the strong threshold. In contrast,
every POLA run fails to reach the strong threshold for grid sizes above 3. For
further details on the training curves from these experiments, please see the
appendix section D. Figure 6 also provides the evaluation metrics for each
algorithm, detailing their behaviors. Additionally, LOQA consistently achieves
each threshold substantially faster, by at least one order of magnitude
because of its lower time and memory complexity.

The complexity of LOQA is equivalent to the calculation of a REINFORCE
estimator, as is standard in RL. Unlike POLA, LOQA does not involve
calculations for opponent optimization steps nor does it differentiate through
a computational graph of said optimizations during each training step, giving
LOQA greater computationoal efficiency compared to POLA. Additionally, the
absence of a second-order gradient in LOQA reduces the variance of its
gradient estimators.

The model of opponent learning in POLA is restricted to a limited number of
optimization steps. In scenarios with increased complexity and varying
opponent policies, additional steps may be necessary to accurately represent
the opponent’s learning. This increase necessitates extended runtimes and
increased memory allocation for storing the computational graphs required for
differentiation, positioning LOQA as more efficient and economical in memory
usage.

Figure 4: Training curves for 3 seeds of POLA and LOQA on the two evaluation
metrics for a 7x7 grid size: Normalized return vs. themselves (Self) and vs.
always defect (AD). The wall clock time is measured in seconds. Note that the
range of the x-axis is different for POLA and LOQA as POLA takes longer to
pass the considered thresholds.

##  7 Limitations

LOQA is primarily limited by the assumption that the other player acts
accordingly to an inner action-value function. As such, it is unable to shape
other opponents that do not necessarily follow this assumption. In a similar
way, LOQA agents are designed for environments with discrete action spaces.
Future work could explore relaxations that allow LOQA agents to shape other
types of agents and learn in continuous action spaces.

##  8 Conclusion

In this paper we have introduced LOQA, a decentralized reinforcement learning
algorithm that is able to learn reciprocity-based cooperation in general sum
environments at a lower computational cost than its predecessors. To do so,
LOQA agents rely on the observation that their opponent’s action-value
function is controllable, and the assumption that their opponent’s policy
closely mirrors it. As a result, LOQA agents are able to shape other LOQA
agents by performing REINFORCE updates that can be efficiently computed in
hindsight after collecting environment trajectories. This is especially
advantageous as demonstrated in the experimental setup, where LOQA agents
confidently outperform POLA agents in terms of optimality and efficiency in
the Coin Game. Therefore, LOQA stands out as a promising algorithm for
tackling more complex and empirically-grounded social dilemmas.

## Appendix

##  Appendix A Experimental Details

###  A.1 IPD

Game specification We use a finite prisoner dilemma of game length 50. The
hyperparameters of our training are indicated in the Table 3

Hyperparameter | Value
---|---
Actor Model | logits
Advantage Estimation Method | TD0
Gradient Clipping Mode | disabled
Entropy Regularization Beta | 0
Actor Learning Rate | 0.001
Q-value Learning Rate | 0.01
Target EMA Gamma | 0.99
Optimizer | adam
Batch Size | 2048
Game Length | 50
Epsilon Greedy | 0.2
Reward Discount | 0.96
Agent Replay Buffer Mode | disabled
Differentiable Opponent Method | n step
Differentiable Opponent N Step | 2
Table 3: List of hyperparameters used in the training run.

Agent’s architecture The agent’s policy is modeled via 5 logits. We take a
sigmoid over these logits to indicate the probability of cooperation on each
of Start, CC, CD, DC, DD states. As the critic, we use a GRU unit described in
A.2.

Advantage Estimation In our experiments we used TD-0 for advantage estimation.
We estimate the value for a state as
$V(s_{t})=\sum_{a_{t}}Q(s_{t},a_{t})\pi(a_{t}|s_{t})$. Consequently, we use
$r_{t}+\gamma V(s_{t+1})-V(s_{t})$ as the advantage.

###  A.2 Coin Game

GPU and Running Time: We run our Coin Game experiments for 15 minutes on a
single A100 GPU with 80 Gigabytes of GPU memory and 20 Gigabytes of CPU
memory. We choose the last state of the training as our checkpoint which is
the state at the 6000 iteration.

Agent’s architecture We use the same GRU module taken from POLA’s codebase. It
is a GRU with two dense layers before the GRU unit and a single linear layer
after GRU’s output. We use one for actor and one for our critic.

Replay Buffer We maintain a replay buffer of agents visited during the
trianing. It has a capacity of storing 10000 agents. We also push a new agent
every 10 step. During trainig we sample an agent from the replay buffer
uniformly.

Hyperparameters In table 4 we show the hyperparameters we used for training
the agent.

Hyperparameter | Value
---|---
Grid Size | 3
Game Length | 50
Advantage Estimation Method | TD0
Gradient Clipping Method | Norm
Gradient Clipping Max Norm | 1
Actor Optimizer | Adam
Actor Loss Entropy Beta | 0.1
Actor Learning Rate | 0.001
Actor Hidden Size | 128
Actor Dense Layers Before GRU | 2
Critic Estimation | Mean
Critic Optimizer | Adam
Critic Learning Rate | 0.01
Critic Target Exponential Moving Average’s Gamma | 0.99
Critic Hidden Size | 64
Critic Dense Layers Before GRU | 2
Batch Size | 512
Reward Discount | 0.96
Agent Replay Buffer Mode | Enabled
Agent Replay Buffer Capacity | 10000
Agent Replay Buffer Update Freq | 10
Differentiable Opponent Method | Loaded-Dice
Differentiable Opponent Discount | 0.9
Table 4: List of hyperparameters used in the training run.

###  A.3 Scalability Experiments

GPU and Running Time: In our scalability experiments we train the LOQA agents
for a maximum of two hours on a single node that has one A100 GPU with 80
Gigabytes of GPU memory on a system with 20 Gigabytes of CPU memory. For POLA
we use a longer runtime of 10 hours on the same node configuration as it takes
longer to achieve reasonable performance.

Hyperparameters: For POLA we take the hyperparameters as suggested on POLA’s
github repository. We those same hyperparameters for all the grid sizes. For
LOQA, we use the same hyperparameters as we found to work suitably on the 3x3
board. Although, we increased the batch size of LOQA to be 2048 to ensure
reduced variance. In our 3x3 experiments for running the league we reduced the
batch size to 512 so we can run ten seeds faster.

##  Appendix B Implementation Details

Using naive REINFORCE estimators to compute the gradient with respect to the
differentiable action-value estimate of the opponent leads to a suboptimal
performance of LOQA due to high variance. We instead use a loaded-DiCE
(Farquhar2019) implemenation of the actor loss.

Algorithm 3 LOQA_ACTOR_LOSS with loaded-DiCE

Input: Trajectory $\tau$ of length $T$, actor policy $\pi^{i}$, opponent
action-value function $Q^{-i}$, discount factor $\gamma$, action discount
factor $\lambda$, advantages $\\{A_{1}^{i},\ldots,A_{T}^{i}\\}$

$L_{a}\leftarrow 0$

for $t=1,2,\ldots,T-1$ do

$w\leftarrow 0$

$\hat{Q}^{-i}(s_{t},b_{t})\leftarrow\sum_{k=t}^{T}\gamma^{k-t}r^{-i}(s_{k},a_{k},b_{k})$

for $k=2,\ldots,T$ do

$w\leftarrow\lambda\cdot w+\text{log }(\pi^{i}(a_{t}|s_{t}))$

$v\leftarrow\lambda\cdot w-\text{log }(\pi^{i}(a_{t}|s_{t}))$

$\hat{Q}^{-i}(s_{t},b_{t})\leftarrow\hat{Q}^{-i}(s_{t},b_{t})+A_{k}^{i}(f(w)-f(v))$

end for

Compute $\hat{\pi}^{-i}$ using $\hat{Q}^{-i}(s_{t},b_{t})$ and
$Q^{-i}(s_{t},b_{t})$ according to equation (2)

$L_{a}\leftarrow L_{a}+A_{t}^{i}\>\left[\text{log
}\pi^{i}(a_{t}|s_{t})+\text{log }\hat{\pi}^{-i}(b_{t}|s_{t})\right]$

end for

return: $L_{Q}$

function $f(x)$

return: exp$(x-$ STOP_GRADIENT$(x))$

end function

##  Appendix C Ablations

Figure 5: Average rewards after evaluating 10 fully trained LOQA and POLA
seeds against different agents in a 3x3 sized Coin Game. We abbreviate L:LOQA,
L-R:LOQA without replay buffer, L-S:for LOQA without self-play, P:POLA,
AC:Always Cooperate, AD:Always defect and R:Random.

###  C.1 Self-play Ablations

We achieve the results presented in the main paper by training one agent
against itself 111Note when we use the replay buffer of agents, we train the
agent against a sampled agent from the replay buffer. The replay buffer is
filled with the past versions of the same agent encountered in training..
Figure 5 shows the performance of L-S (LOQA without Self Play) agents. The
performance of L-S is close to the L (LOQA with Self Play) although, L is
stronger in cooperating with itself.

###  C.2 Agent Replay Buffer Ablations

Inspired by (Mnih2013), we use a replay buffer with capacity to store 10000
agents. Every 10 training steps, we push a copy of the agent’s parameters to
the replay buffer. Figure 5 shows the performance of L-R (LOQA without Replay
Buffer). The replay buffer gets updated slowly with new agents, thus, it
decreases the variance of the training process.

##  Appendix D Scalability Experiments

Figure 6: Training curves for 3 seeds of POLA and LOQA for 3x3, 4x4, 5x5 and
6x6 grid sizes on the two metrics in the Coin Game: Normalized return vs. each
other and vs. always defect (AD). The wall clock time is measured in seconds.
Note that the range of the x-axis is different for POLA and LOQA as POLA takes
longer to pass the considered thresholds.

##  Appendix E LOQA’s Actor Critic Update Derivation

In LOQA we assume that the trajectories are generated by policies $\pi^{1}$
and $\hat{\pi}^{2}$, which induces a different probability measure over
trajectories

$\displaystyle\text{Pr}_{\mu}^{\pi^{1},\hat{\pi}^{2}}(\tau)=\mu(s_{0})\pi^{1}(a_{0}|s_{0})\hat{\pi}^{2}(b_{0}|s_{0})P(s_{1}|s_{0},a_{0},b_{0})\ldots$

Our expected return must now be computed using this probability measure

$\displaystyle\hat{V}^{1}(\mu):=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\hat{\pi}^{2}}}\left[R^{1}(\tau)\right]=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\hat{\pi}^{2}}}\left[\sum_{t=0}^{\infty}\gamma^{t}r^{1}(s_{t},a_{t},b_{t})\right]$

Therefore we can write

$\displaystyle\nabla_{\theta^{1}}\hat{V}^{1}(\mu)$
$\displaystyle=\nabla_{\theta^{1}}\sum_{\tau}R^{1}(\tau)\text{Pr}_{\mu}^{\pi^{1},\hat{\pi}^{2}}(\tau)$
$\displaystyle=\sum_{\tau}R^{1}(\tau)\text{Pr}_{\mu}^{\pi^{1},\hat{\pi}^{2}}(\tau)\nabla_{\theta^{1}}\text{log}\left(\text{Pr}_{\mu}^{\pi^{1},\hat{\pi}^{2}}(\tau)\right)$
$\displaystyle=\sum_{\tau}R^{1}(\tau)\text{Pr}_{\mu}^{\pi^{1},\hat{\pi}^{2}}(\tau)\nabla_{\theta^{1}}\text{log}\left(\prod_{t=0}^{\infty}\pi^{1}(a_{t}|s_{t})\hat{\pi}^{2}(b_{t}|s_{t})\right)$
$\displaystyle=\sum_{\tau}R^{1}(\tau)\text{Pr}_{\mu}^{\pi^{1},\hat{\pi}^{2}}(\tau)\sum_{t=0}^{\infty}\nabla_{\theta^{1}}\left(\text{log
}\pi^{1}(a_{t}|s_{t})+\text{log }\hat{\pi}^{2}(b_{t}|s_{t})\right)$
$\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\hat{\pi}^{2}}}\left[R^{1}(\tau)\sum_{t=0}^{\infty}\nabla_{\theta^{1}}\left(\text{log
}\pi^{1}(a_{t}|s_{t})+\text{log }\hat{\pi}^{2}(b_{t}|s_{t})\right)\right]$
$\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\hat{\pi}^{2}}}\left[\sum_{t=0}^{T}A^{1}(s_{t},a_{t},b_{t})\nabla_{\theta^{1}}\left(\text{log
}\pi^{1}(a_{t}|s_{t})+\text{log }\hat{\pi}^{2}(b_{t}|s_{t})\right)\right]$

In reality, we use trajectories sampled from $\pi^{1}$ and $\pi^{2}$, to
compute our own estimate of the actor-critic update so we have

$\displaystyle\nabla_{\theta^{1}}\hat{V}^{1}(\mu)$
$\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{T}A^{1}(s_{t},a_{t},b_{t})\nabla_{\theta^{1}}\left(\text{log
}\pi^{1}(a_{t}|s_{t})+\text{log }\hat{\pi}^{2}(b_{t}|s_{t})\right)\right]$

##  Appendix F Reproducibility

For reproducing our results on the IPD and the Coin Game please visit this
link. This is an anonymized repository and the instructions for reproducing
the results and the seeds are provided. The seeds we used are $42$ to $51$.