# Towards Quantifying the Carbon Emissions of
Differentially Private Machine Learning

Rakshit Naidu  Harshita Diddee  Ajinkya Mulay  Aleti Vardhan  Krithika Ramesh
Ahmed Zamzam

###### Abstract

In recent years, machine learning techniques utilizing large scale datasets
have achieved remarkable performance. Differential privacy, by means of adding
noise, provides strong privacy guarantees for such learning algorithms. The
cost of differential privacy is often a reduced model accuracy and a lowered
convergence speed. This paper investigates the impact of differential privacy
on learning algorithms in terms of their carbon footprint due to either longer
run-times or failed experiments. Through extensive experiments, further
guidance is provided on choosing the noise levels which can strike a balance
between desired privacy levels and reduced carbon emissions.

Machine Learning, ICML

##  1 Introduction

With the rising availability of large-scale, diverse datasets, performance of
Machine Learning (ML) models have experienced a significant boost across a
multitude of domains. This boost is also associated with the availability of
extreme-scale datasets, which is heavily linked to individual user
contributions achieved via crowd-sourcing. ML algorithms often perform
operations directly on raw user data leading to a host of privacy violations.
Differential Privacy (DP) (Dwork & Roth, 2014; Abadi et al., 2016) makes
progress in this domain by providing strong privacy guarantees for such
contributing individuals. This guarantee is achieved by means of noise
addition, which can be done at various stages of the ML pipeline including :
(1) Local DP: Addition to the raw data (Cormode et al., 2018) (2) Gradient DP:
Addition to gradients after clipping (Abadi et al., 2016) (3)  Addition to
Output & Objective DP: Addition to the final ML model or the loss function
(Chaudhuri et al., 2011).

###  1.1 Impact on Climate Change

It is well-known that the computational resource investment requisite for
training ML models generates a carbon footprint. This footprint is amplified
in privacy-preserving setups where it is harder to reach consistent accuracy
due to the addition of noise. Extended and failed runs (especially on larger
datasets) actively contribute to an increase in the carbon footprint of ML
experiments (Strubell et al., 2019). Therefore, an analysis of the climatic
impact of this privacy modulation is critical. While the existing DP
literature studies several performance aspects affected by varying privacy
requirements, it lacks a comprehensive quantification of the carbon footprint
of DP and how it is affected by variable privacy levels. Since DP also
provides a mathematical paradigm to quantify the privacy budget of training ML
models while tracking the privacy usage across multiple runs, this paper aims
at quantifying the Carbon Emissions (CE) associated with varying privacy
budgets of differentially private networks. In order to study impact of DP on
these emissions, we implement Gradient DP (DP-SGD (Abadi et al., 2016)) for
natural language processing, image classification, and reinforcement learning
domains to identify the privacy implications, model performance and most
crucially the carbon footprint of each algorithm. As per our knowledge this is
the first attempt to quantitatively benchmark the carbon footprint of
differentially private ML models.

###  1.2 Differential Privacy

Definition 1: Given a randomized mechanism
$\mathcal{A}:\mathcal{D}\rightarrow\mathcal{R}$ (with domain $\mathcal{D}$ and
range $\mathcal{R}$) and any two neighboring datasets
$d_{1},d_{2}\in\mathcal{D}$ (_i.e._ they differ by a single individual data
element), $\mathcal{A}$ is said to be $(\varepsilon,\delta)$-differentially
private for any subset $S\subseteq\mathcal{R}$ 111In this work, we exclusively
use Gaussian noise.

$\Pr\left[\mathcal{A}\left(d_{1}\right)\in S\right]\leq
e^{\varepsilon}\cdot\Pr\left[\mathcal{A}\left(d_{2}\right)\in S\right]+\delta$
(1)

Here, $\epsilon\geq 0,\delta\geq 0$. A $\delta=0$ case corresponds to pure
differential privacy, while both $\epsilon=0,\delta=0$ leads to an infinitely
high privacy domain. Finally, $\epsilon=\infty$ provides no privacy
guarantees. For practical purposes we want $\epsilon\leq
5,\delta\ll\frac{1}{N}$ where $N$ is the number of samples in the dataset.
(Dwork & Roth, 2014)

The privacy of differentially private models can be quantified with parameters
such as epsilon ($\varepsilon$) and delta ($\delta$). Utilizing DP-SGD (Abadi
et al., 2016), that is, adding noise to the gradients at each step during
training using a clipping factor ($S$) and noise multiplier ($z$), the amount
of noise added to the model can be linked to to the degree of privacy that the
model can achieve. Theoretically, a lower value of $\varepsilon$ indicates a
higher degree of privacy and this increased privacy degree is understandably,
achieved at the expense of model performance due to the addition of the noise.
The practical implication of this, however, includes a direct impact on the
computational resources required to achieve model performance. Reduced privacy
requirements allow the addition of noise with limited power, and hence, models
can achieve appropriate performance without any significant resource expense.
On the other hand, high privacy requirements necessitate adding a
significantly large magnitude of noise which may directly lead to an increase
in the number of training passes that the model has to iterate over to achieve
the same accuracy. Further, noise addition may even lead to the non-
convergence of some systems in the worst case.

###  1.3 Related Work

Works such as (Strubell et al., 2019; Toews, 2020) discuss how conventional
Machine Learning models impact carbon footprint. In particular, (Strubell et
al., 2019) discusses how training a single Deep Learning model generates the
total lifetime carbon footprint of nearly five cars (as mentioned in (Toews,
2020)) which is more than 17 times the amount of CO2 emissions generated by an
average American per year. Regarding DP, there has been very little
considerations on how Privacy-Preserving Machine Learning (PPML) impacts
climate change. In (Qiu et al., 2021), a comprehensive study is presented on
how local client-side models in Federated learning (FL) could potentially hold
quality data required to understand climate change given data privacy concerns
due to recent policies like GDPR (Skendžić et al., 2018). However, running
local models on multiple client devices and aggregating them globally at the
server level requires additional infrastructure in place, thereby causing a
detrimental effect on carbon emissions.

###  1.4 Contributions and Impacts

In this paper, we provide the first benchmark to quantitatively assess how DP-
noise affect carbon emissions in three different tasks : (1) a Natural
Language Processing (NLP) task using news classification (2) a Computer Vision
(CV) task using the MNIST dataset and (3) a Reinforcement Learning (RL) task
using the Cartpole control problem. Intuitively, when DP noise is added to ML
pipelines, the carbon emissions should increase as the energy required for
computations increase due to rising number of epochs required for convergence.
In order to quantify how the addition of noise plays into climate change, we
track carbon emissions in the models using the codecarbon tool (Schmidt et
al., 2021), a joint effort from authors of (Lacoste et al., 2019) and (Lottick
et al., 2019). We record the average accuracy of several runs of the
considered ML task to assess the behavior of DP-noise.

Noise for masking data has been widely used in adversarial machine learning
(Kurakin et al., 2016). Given the rise in Privacy-enhancing Technologies and
privacy policies, noise addition has now become prevalent in the context of
DP. We envisage this work to provide an insight on how much noise could result
in varying amounts of CO2 emissions. Hence, our work takes a peek at how the
addition of noise could impact a number of industries from healthcare to
finance and justice, where sensitive data is commonly in use.

##  2 Experimental Results

###  2.1 BERT

In these set of experiments, we evaluate the performance of two experiments on
Bidirectional Encoder Representations from Transformers or BERT (Devlin et
al., 2019). The model is fine-tuned for topic-classification of news articles.
The primary objective of these experiments is to observe the carbon emissions
and energy usage of vanilla BERT and DP-BERT (over different privacy levels).

A randomly down-sampled subset (15,000 samples) of the AG News Classification
(Anand, 2020) is used for this task with a 80/20 train-test split. We use BERT
with the AdamW optimizer with the bert-base-cased tokenizer (batch size ($B$)
of $32$, Learning Rate being 0.0005) to conduct the following experiments for
this task.

####  2.1.1 Carbon emissions and energy consumed

The aim of this experiment is to analyse any possible association between
different levels of privacy and carbon emissions. We run these experiments for
10 epochs each and present our results in Table 1 (averaged over 3 runs).
Curiously, the carbon emissions for the $\epsilon=0.5$ case is comparable to
the EU’s 2021 passenger vehicle standard (Bandivadekar, 2013). The difference
between a private model ($\epsilon=0.5$) and a non-private model
($\epsilon=\infty$) is approximately 1g of CO2, which is equivalent to the
emissions from five Google searches (Sterling, 2009).

Epsilon ($\varepsilon$) |  CE (g) |  EC (Wh) | Accuracy (%)
---|---|---|---
0.5 |  26.7 $\pm$ 0.63 |  49.9 $\pm$ 1.2 |  48.5 $\pm$ 1.39
2 |  26.3 $\pm$ 0.49 |  49.3 $\pm$ 0.9 |  52.0 $\pm$ 0.73
5 |  26.1 $\pm$ 0.1 |  48.9 $\pm$ 0.9 |  52.3 $\pm$ 0.36
15 |  25.9 $\pm$ 0.09 |  48.5 $\pm$ 0.1 |  54.2 $\pm$ 1.40
$\infty$ (Non-Private) |  25.2 $\pm$ 0.00 |  47.1 $\pm$ 0.27 |  58.5 $\pm$ 5.29

Table 1: DP-BERT: Emission-Accuracy trends over change in $\epsilon$ for
reaching 52% accuracy.

In congruence with existing literature, the accuracy of the differentially
private BERT increases consistently with the increase in epsilon.
Interestingly, with the increase in the epsilon value – both, CE and EC
decrease, though not by a very significant margin. Given that the range of the
chosen $\varepsilon$ varies considerably, the consequent difference in the
carbon emission is not proportionally varied. The practical implication of
this invariance can be seen as incurring nearly the same carbon footprint for
two versions of a model with different degrees of privacy.

Epsilon ($\varepsilon$) | Epochs | CE (g) | EC (Wh)
---|---|---|---
0.5 | 19 | 153.6 | 287.3
2 | 12 | 96.6 | 180.6
5 | 9 | 80.9 | 151.3
15 | 7 | 56.9 | 106.5
$\infty$ (Non-Private) | 6 | 8.5 | 16

Table 2: Observing the number of epochs needed to achieve the threshold test
accuracy ($T$) with different privacy levels

####  2.1.2 Resource Expense Analysis

The main aim of this experiment is to evaluate how many resources, in terms of
consequent carbon and energy emissions are expended in order to achieve a
target or threshold accuracy with different degrees of privacy. As defined in
the previous set of experiments, we compute the accuracies over
$\varepsilon=0.5,2,5,15$.We set the target/threshold accuracy ($T$) to $52\%$
as shown in Table 2.

It can be inferred from Table 2 that the Carbon Emission and Energy Usage
required to attain the maximum experimental value of privacy is nearly 18
times the carbon emission required to attain the same threshold accuracy with
a non-privacy preserving variant of the model. The practical consequence of
this experiment dictates that enhancing the degree of privacy of the model,
can incur a huge compute cost, which can invariably increase the carbon
footprint of the model’s training pipeline.

(a) BERT: Training Accuracy

(b) BERT: Testing Accuracy

Figure 1: BERT with Gaussian DP: Training and Testing accuracy trends over
change in $\epsilon$ where the threshold accuracy ($T$) is set to 52%.

Additionally, From Figure 1, which present the accuracy curves for the
experiment, it is quite evident that the vanilla variant (i.e a model without
DP-noise) achieves the threshold accuracy with a significantly smaller carbon
footprint than all the footprint of its privacy-preserving variants.

###  2.2 MNIST & CIFAR

Epsilon ($\varepsilon$) | CE (g) | EC (Wh)
---|---|---
0.5 * |  10.53 $\pm$ 2.21 |  40.41 $\pm$ 0.93
2 * |  10.6 $\pm$ 2.43 |  40.5 $\pm$ 0.53
5 |  7.85 $\pm$ 1.84 |  29.93 $\pm$ 0.46
15 |  1.61 $\pm$ 0.37 |  6.17 $\pm$ 0.27
$\infty$ (Non-Private) |  0.08 $\pm$ 7e-04 |  0.38 $\pm$ 3.3e-03

Table 3: MNIST: Emission trends over change in $\epsilon$ for reaching 70%
accuracy (* 70% accuracy not reached even after 200 epochs.)

Epsilon ($\varepsilon$) | CE (g) | EC (Wh)
---|---|---
0.5* | 15.34 | 70.216
2 | 12.48 | 57.108
5 | 3.12 | 14.307
15 | 2.03 | 9.297
$\infty$ (Non-Private) | 0.36 | 1.678

Table 4: CIFAR: Emission trends over change in $\epsilon$ for reaching 55%
accuracy in a single run (* 55% accuracy not reached even after 30 epochs.)

We evaluate our approach on the MNIST dataset (LeCun & Cortes, 2010) with a
batch size of 128 using DP-SGD (Abadi et al., 2016). We use a simple multi-
layer perceptron (MNIST 2NN) with a two hidden layers of 200 units each
(parameters = 199,210) as the network from (McMahan et al., 2017). Our goal is
to observe the trend in the CO2 emissions by allowing the model to train and
reach $X$ accuracy with different values of $\varepsilon$ (different levels of
privacy). We compute the accuracies over $\varepsilon=0.5,2,5,15$ as shown in
Fig. 2. We set the target/threshold accuracy ($T$) to $70\%$ so that most of
the privacy-variant models can achieve under $200$ iterations. In Fig. 2 we
see that only models with $\varepsilon=5,15$ reach 70% accuracy within 200
epochs. Fig. 2 shows a clear trend on how increasing levels of privacy in ML
models increases the amount of computation required to reach $T$, thereby
releasing higher carbon emissions.

For the CIFAR-10 experiments, we use the ResNet18 model pre-trained on the
ImageNet dataset. This deep variant of CNN is chosen instead of the simple
MNIST 2NN in order to capture more complex and realistic features. We compute
the accuracies over $\varepsilon=0.5,2,5,15$ as shown in Fig. 3. We set the
target/threshold accuracy ($T$) to $55\%$ as most of the private models can
achieve under $30$ iterations. We run the CIFAR experiments only for 30
iterations as we observe that there is little to no significant improvement
beyond this. In Fig. 3, We observe similar trends as Fig. 2 on how increasing
privacy levels involve higher computations to reach $T$ which in turn, release
higher carbon emissions.

(a) MNIST: Accuracy on Training Set

(b) MNIST: Accuracy on Test Set

Figure 2: MNIST with Gaussian DP: Training and test accuracy trends during
training for multiple $\epsilon$ values.

(a) CIFAR-10: Accuracy on Training Set

(b) CIFAR-10: Accuracy on Test Set

Figure 3: CIFAR-10 with Gaussian DP: Training and test accuracy trends during
training for multiple $\epsilon$ values.

###  2.3 Cartpole

For the reinforcement learning experiments, we trained a DQN over OpenAI Gym’s
Cartpole-v0 environment. Due to page restrictions we defer the discussion of
the RL experiments to the Appendix B.

##  3 Conclusion

We demonstrate and highlight the prominent impact of Privacy-Preserving
Machine Learning (PPML) on carbon emissions over three ML domains, namely, CV,
NLP and RL. We observe that the stronger privacy regime, _i.e,_ a lower
$\epsilon$ value, ML algorithms always result in higher levels of carbon
emissions in the CV and NLP domains. Curiously, results for RL are less
obviously explained and we defer these discussions for future work. We
conclude that alongside the challenge of obtaining state-of-the-art
performance, PPML needs to reduce the number of epochs required to reach the
desired performance. This leads us to the following critical questions which
we leave as open questions for the future: (1) Can we reduce the number of
iterations (including hyperparameter tuning) required to reach a privacy-
utility ratio? (2) How much does the size of ML models affect the carbon
emissions and the overall performance under PPML?

##  4 Acknowledgements

We thank Fatemehsadat Mireshghallah for her valuable inputs and discussions.

## References

  * Abadi et al. (2016) Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L.  Deep learning with differential privacy.  _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , Oct 2016.  doi: 10.1145/2976749.2978318.  URL http://dx.doi.org/10.1145/2976749.2978318.
  * Anand (2020) Anand, A.  Ag news classification, 2020.  URL https://www.kaggle.com/amananandrai/ag-news-classification-dataset.
  * Bandivadekar (2013) Bandivadekar, A.  One (vehicle efficiency) table to rule them all.  https://theicct.org/blogs/staff/one-vehicle-efficiency-table-rule-them-all, 2013\.  Accessed: 2021-5-31.
  * Barto et al. (1983) Barto, A. G., Sutton, R. S., and Anderson, C. W.  Neuronlike adaptive elements that can solve difficult learning control problems.  _IEEE Transactions on Systems, Man, and Cybernetics_ , SMC-13(5):834–846, 1983.  doi: 10.1109/TSMC.1983.6313077.
  * Chaudhuri et al. (2011) Chaudhuri, K., Monteleoni, C., and Sarwate, A. D.  Differentially private empirical risk minimization.  _Journal of Machine Learning Research_ , 12(3), 2011.
  * Cormode et al. (2018) Cormode, G., Jha, S., Kulkarni, T., Li, N., Srivastava, D., and Wang, T.  Privacy at scale: Local differential privacy in practice.  In _Proceedings of the 2018 International Conference on Management of Data_ , pp. 1655–1658, 2018.
  * Dabney et al. (2017) Dabney, W., Rowland, M., Bellemare, M. G., and Munos, R.  Distributional reinforcement learning with quantile regression, 2017.
  * Devlin et al. (2019) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1423.  URL https://www.aclweb.org/anthology/N19-1423.
  * Dwork & Roth (2014) Dwork, C. and Roth, A.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3–4):211–407, August 2014.  ISSN 1551-305X.  doi: 10.1561/0400000042.  URL https://doi.org/10.1561/0400000042.
  * Kurakin et al. (2016) Kurakin, A., Goodfellow, I., and Bengio, S.  Adversarial machine learning at scale.  _arXiv preprint arXiv:1611.01236_ , 2016.
  * Lacoste et al. (2019) Lacoste, A., Luccioni, A., Schmidt, V., and Dandres, T.  Quantifying the carbon emissions of machine learning.  _Workshop on Tackling Climate Change with Machine Learning at NeurIPS 2019_ , 2019.
  * LeCun & Cortes (2010) LeCun, Y. and Cortes, C.  MNIST handwritten digit database.  2010\.  URL http://yann.lecun.com/exdb/mnist/.
  * Lottick et al. (2019) Lottick, K., Susai, S., Friedler, S. A., and Wilson, J. P.  Energy usage reports: Environmental awareness as part of algorithmic accountability.  _Workshop on Tackling Climate Change with Machine Learning at NeurIPS 2019_ , 2019.
  * McMahan et al. (2017) McMahan, H. B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A.  Communication-efficient learning of deep networks from decentralized data, 2017.
  * Qiu et al. (2021) Qiu, X., Parcollet, T., Fernández-Marqués, J., de Gusmão, P. P. B., Beutel, D. J., Topal, T., Mathur, A., and Lane, N. D.  A first look into the carbon footprint of federated learning.  _CoRR_ , abs/2102.07627, 2021.  URL https://arxiv.org/abs/2102.07627.
  * Schmidt et al. (2021) Schmidt, V., Goyal, K., Joshi, A., Feld, B., Conell, L., Laskaris, N., Blank, D., Wilson, J., Friedler, S., and Luccioni, S.  CodeCarbon: Estimate and Track Carbon Emissions from Machine Learning Computing.  2021\.  doi: 10.5281/zenodo.4658424.
  * Skendžić et al. (2018) Skendžić, A., Kovačić, B., and Tijan, E.  General data protection regulation — protection of personal data in an organisation.  In _2018 41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO)_ , pp. 1370–1375, 2018.  doi: 10.23919/MIPRO.2018.8400247.
  * Sterling (2009) Sterling, G.  Calculating the carbon footprint of a google search.  2009\.  URL https://searchengineland.com/calculating-the-carbon-footprint-of-a-google-search-16105.
  * Strubell et al. (2019) Strubell, E., Ganesh, A., and McCallum, A.  Energy and policy considerations for deep learning in NLP.  _CoRR_ , abs/1906.02243, 2019.  URL http://arxiv.org/abs/1906.02243.
  * Toews (2020) Toews, R.  Deep learning’s carbon emissions problem.  _Forbes_ , 06 2020.  URL https://www.forbes.com/sites/robtoews/2020/06/17/deep-learnings-climate-change-problem/?sh=6bcb1b9f6b43.
  * Wang & Hegde (2019) Wang, B. and Hegde, N.  Privacy-preserving q-learning with functional noise in continuous state spaces, 2019.

##  Appendix A Hyperparameter Tuning

###  A.1 BERT

We set out to understand the impact of noise introduced by DP on the model
convergence up until a threshold test accuracy. We primarily tune the epsilon
values (for the privacy guarantee) and the number of epochs. For a fair
comparison we use constant hyperparameters for each epsilon so as to to
minimize the scope of confounding variables (optimally tuned hyperparameters
per epsilon value) for BERT (Table 1).

Succeeding that though, since a lot of differentially private models are
deployed in edge-focused setups where numerous clients can take hyperparameter
optimization decisions locally - the experiments (Table 2) with the
thresholding accuracy were conducted. On grounds of ablation, a subset of
these locally available hyperparamters were chosen with the objective to
evaluate the change in carbon and energy emissions when these hyperparameters
are altered: the privacy guarantee (meant to be a globally decided parameter
in a distributed setup) and the number of epochs (meant to be a locally
decided parameter) are changed.

###  A.2 MNIST & CIFAR

Similar to the BERT approach, we use consistent hyperparameters across
different $\varepsilon$-privacy levels for the MNIST dataset.

However, due to serious model performance degradation on the CIFAR-10 dataset
we use an alternate approach. We tweak a set of hyperparameters to achieve
optimal performance at the respective $\varepsilon$-privacy levels when the
model performs poorly. For instance, we observe a major drop in performance
for only the non-private model when a constant learning rate of $10^{-3}$ is
used for both the private and non-private settings. So, we instead choose a
learning rate of $10^{-6}$ for the non-private model which leads to optimal
performance.

In our experiments, we also use the RMS-PROP optimizer which leads to more
stable results & faster convergence during training.

##  Appendix B Reinforcement Learning: Experiments & Discussion

###  B.1 Cartpole

The Cartpole-v0 environment (Barto et al., 1983) consists of an un-actuated
joint to a cart. There are two possible actions which involve a force of +1 or
-1 being applied to the cart along a friction-less track. The pole starts
upright, with the goal of preventing it from falling over. For every time-step
that the pole is upright, a reward of +1 is added to the total reward.
However, if the pole exceeds 15 degrees from the vertical, or if the cart
moves more than 2.4 units from the center, the episode ends.

Figure 4: CartPole with Gaussian DP: Episodes vs Rewards for the mean reward
every 100 episodes

Figure 5: Acrobot with Gaussian DP: CO2 vs Epsilon values post training after
a 1000 episodes

Figure 6: Acrobot with Gaussian DP: Episodes vs Rewards for the mean reward
every episode for a 1000 episodes

The DQN’s configuration (including the hyperparameters) is the same as the one
used in (Wang & Hegde, 2019), and we observed results similar to this paper,
with one variant of DP model slightly outperforming the baseline as shown in
4. It consists of a single hidden layer with 16 neurons. For our non-private
experiment we obtained a mean reward of 19.94 and carbon emissions of 0.22 g
on average (over a 1000 episodes). We provide results of the private variants
in Fig. 4. Our setup included multiple experiments.

  * •

Noise addition to DQN’s output layer only. (1)

  * •

Noise addition to both, the DQN’s output layer and its parameters. The noise
added to the parameters is the averaged noise sampled from the noisebuffer
function during the forward pass. (2)

We varied the value of the variance $\sigma$ of the distribution to observe
its impact on the function approximated by the DQN. As expected, with
increasing noise addition to the model (_i.e._ , increasing value of
$\sigma$), we notice a drop in the average reward. Subsequently, the increased
computations lead to higher carbon emissions. We observe that there is a
significant increase in CE from Table 6 to Table 7 when the number of episodes
increase.

###  B.2 Acrobot

We alternatively run experiments on the Acrobot-v1 environment. Acrobot-v1 has
2 joints and links and the joint between the links is actuated. The
environment’s initial position has the links in a resting state, hanging
downward, with the objective being to swing the end of the lowermost link up
to a specified height. There are 3 potential actions, to apply positive
torque, to apply negative torque, or to do nothing. The agent attempts to
maximize its reward within 500 time-steps, with each time-step potentially
incurring a punishment of -1, thus making -500 the worst possible reward. If
the agent reaches the given height, a reward of 0 is returned. The state
returned consists of the joint angular velocities and the sin and cos values
of the two rotational joint angles.

For the purpose of training the Acrobot environment, we used distributed
reinforcement learning with quantile regression (Dabney et al., 2017).
Quantile regression models the distribution of the returned rewards instead of
only considering the mean of the distribution. We use the Opacus library in
PyTorch to add the necessary DP guarantees. From Fig.5, we observe a
consistent upward trend of the CO2 emissions with the epsilon value. This
directly implies that better privacy guarantees lead to higher carbon
emissions. As a sanity check, we can observe (from Table 8) that the mean
reward increases with higher epsilons (lower privacy requirement) due to
reduced noise levels.

$\text{{Epsilon}}^{*}$ ($\epsilon^{*}\propto 15\epsilon$) |  Sigma ($\sigma\propto\frac{1}{\epsilon}$) | Mean Reward | CE (g)
---|---|---|---
1 |  15 | 4.5 ± 0.6 | 1.03 ± 0.06
3 |  5 | 2.2 ± 0.2 | 0.96 ± 0.03
7.5 |  2 | 19.9 ± 0.5 | 1.14 ± 0.06
30 |  0.5 | 19.4 ± 0.1 | 1.15 ± 0.06

Table 5: CartPole: Emission trends over change in $\epsilon^{*}$ post 1000
episodes in (1) following (Wang & Hegde, 2019)

$\text{{Epsilon}}^{*}$ ($\epsilon^{*}\propto 15\epsilon$) |  Sigma ($\sigma\propto\frac{1}{\epsilon}$) | Mean Reward | CE (g)
---|---|---|---
1 |  15 | 2.3 ± 0.9 | 0.41 ± 0.01
3 |  5 | 10.2 ± 0.8 | 0.5 ± 0.02
7.5 |  2 | 7.6 ± 0.7 | 0.45 ± 0.02
30 |  0.5 | 13.8 ± 0.1 | 0.48 ± 0.03

Table 6: CartPole: Emission trends post 1000 episodes in (2)

$\text{{Epsilon}}^{*}$ ($\epsilon^{*}\propto 15\epsilon$) |  Sigma ($\sigma\propto\frac{1}{\epsilon}$) | Mean Reward | CE (g)
---|---|---|---
1 |  15 | 13.2 ± 0.3 | 3.51 ± 0.26
3 |  5 | 13.7 ± 0.9 | 2.31 ± 0.28
7.5 |  2 | 18.1 ± 0.1 | 2.72 ± 0.23
30 |  0.5 | 19.8 ± 0.6 | 4.0 ± 0.31

Table 7: CartPole: Emission trends post 5000 episodes in (2)

Epsilon | Mean Reward | CO2
---|---|---
0.5 | -150.7 ± 18.69 | 3.25 ± 0.372
2 | -138.0 ± 11.15 | 3.0 ± 0.245
5 | -120.6 ± 4.64 | 0.98 ± 0.035
15 | -117.5 ± 2.45 | 0.92 ± 0.023
0 | -110.5 ± 1.22 | 0.33 ± 0.023

Table 8: Acrobot-v1: Emission trends post a 1000 Episodes


Could dark matter or neutrinos discriminate between the enantiomers of a
chiral molecule?
Pedro Bargueño
Instituto de Matemáticas y Física Fundamental, CSIC, Madrid, Spain

Departamento de Química Física, Universidad de Salamanca, Spain

Antonio Dobado and Isabel Gonzalo
Departamento de Física Teórica I and Departamento de Óptica

Universidad Complutense de Madrid, 28040 Madrid, Spain

ABSTRACT

We examine the effect of cold dark matter on the discrimination between the
two enantiomers of a chiral molecule. We estimate the energy difference
between the two enantiomers due to the interaction between fermionic WIMPs
(weak interacting massive particles) and molecular electrons on the basis that
electrons have opposite helicities in opposite enantiomers. It is found that
this energy difference is completely negligible. Dark matter could then be
discarded as an inductor of chiroselection between enantiomers and then of
biological homochirality. However, the effect of cosmological neutrinos,
revisited with the currently accepted neutrino density, would reach, in the
most favorable case, an upper bound of the same order of magnitude as the
energy difference obtained from the well known electroweak electron-nucleus
interaction in some molecules.

PACS: 33.15.Bh, 13.15.+g, 95.35.+d

##  1 Introduction

The origin of biological homochirality, that is, the almost exclusive one-
handedness of chiral molecules in biological organisms, is a fundamental
problem for which there is not yet a convincing solution. Several mechanisms
have been proposed to explain chiroselection among the two possible
enantiomers of a chiral molecule (see for example [1, 2, 3] and references
therein). These mechanisms involve chance, $\beta$-radiolysis [4], circularly
polarized light [5, 6, 7], magnetic fields [8, 9], and violation of parity in
the weak interaction (see below).

The discovery of an excess of L-amino acids in meteorites [10, 11] has
reinforced the idea of an extraterrestrial origin of biological homochirality
[1, 12]. In this context, universal mechanisms of chiroselection such as
parity violation in weak interactions would acquire special interest in spite
their tiny effects, without of course underestimating other mechanisms.

The effect of electroweak interactions between electrons and nuclei mediated
by the Z0, have been extensively studied and observed in atoms (see the review
[13]), and only predicted in molecules, where an energy difference between the
two enantiomers of chiral molecules has been estimated to be between
$10^{-16}$ and $10^{-21}$ eV [14, 15, 16, 17, 18]. In the laboratory, no
conclusive energy difference have been reported in experimental spectroscopic
studies reaching an energy resolution of about $10^{-15}$ eV [19].

The above tiny energy difference would require a powerful mechanism of
amplification in order to induce a real enantioselective effect. Otherwise the
small energy difference would be masked by the natural broadening of the
energy levels of the molecule, thermal fluctuations and environment
interactions, which do not discriminate, in average, between L and D
enantiomers. There is active research on amplification mechanisms in which a
permanent although very small interaction acting always in the same
enantioselective direction, and under appropriate conditions, could lead to an
effective enantioselection. Some mechanisms are based on nonlinear
autocatalytic processes of polymerization or crystallization along a large
period of time [20, 21]. Another one involves a second-order phase transition
below a certain critical temperature [22] that could work at low temperatures
such as those of the interstellar space. However, theoretical or experimental
conclusive results from the diverse mechanisms to amplify enantioselection
based on electroweak energy difference, are not yet at hand (e.g.,[23, 24]).

Another universal mechanism that could discriminate between the two
enantiomers of a chiral molecule and that involves weak interaction is
neutrino-electron axial-vector interaction mediated by charged electroweak
bosons W±. This process discriminates on the basis of an asymmetry between the
number of neutrinos and antineutrinos, and that electrons of opposite (L,R)
enantiomers have opposite helicity. Considering the cosmological relic sea of
neutrinos, the estimated energy difference between the two enantiomers was
found to be even lower than the value $10^{-21}$ eV mentioned above [25].
However, it could increase significantly under bigger neutrino fluxes, as in
supernova remnants [26] assumed that big molecules could survive in the
surroundings. Revisited assumptions about the number density of cosmological
neutrinos in the relic sea lead to an increase of the mentioned energy
difference, as we shall see in the next section.

Looking for other universal mechanisms acting also outside of the Earth, we
analyze here the possible enantioselective effect of chiral dark matter on
chiral molecules.

The existence of dark matter is inferred from astrophysical observations in
light of studies of the dynamics of stars in the local disk environment,
rotation curves for a large number of spiral galaxies, gravitational lensing
by clusters of galaxies and some large scale studies of the Universe (for a
recent review of experimental searches for dark matter see for example [27]).
A vast variety of candidates have been proposed for dark matter content, from
baryonic to non-baryonic matter. The non-baryonic candidates are basically
postulated elementary particles beyond the Standard Model which have not been
discovered yet, like axions, WIMPs (Weak Interacting Massive Particles) and
other exotic candidates. The baryonic candidates are the Massive Compact Halo
Objects (Macho) [28]. Another important difference is the hot versus cold dark
matter. A dark matter candidate is called hot if it was moving at relativistic
speeds at the time when galaxies could just start to form, and cold if it was
moving non-relativistically at that time. The problem is that hot dark matter
cannot reproduce correctly the observed structure of the Universe. Therefore
we focus our attention on cold dark matter. The fact that dark matter
interacts weakly with matter makes its detection very difficult [27]. However
many experiments are currently in progress in order to reach this goal.

Here we estimate the energy difference between the two enantiomers of a chiral
molecule, due to the weak type interaction between non-baryonic cold dark
matter (specifically WIMPs) and molecular electrons with non zero helicity.
Experimental results on dark matter are used. Given the resemblance in the
procedure with the energy difference induced by cosmological neutrinos,
estimated in a previous work [25], we first recall this procedure at the time
we improve the result we obtained in that work.

##  2 Energy difference between opposite enantiomers induced by cosmological
neutrinos

Following a previous work [25], we consider neutrino-electron interactions
mediated by the axial-vector Hamiltonian density

$H=\frac{G_{F}}{\sqrt{2}}\bar{e}\gamma^{\mu}(g_{V}-g_{A}\gamma_{5})e\bar{\nu}\gamma_{\mu}(1-\gamma_{5})\nu,$
(1)

where $G_{F}$ is Fermi’s constant, $e(\nu)$ denotes the electron (neutrino)
spinor field, $\bar{e}(\bar{\nu})$ is its adjoint spinor, $\gamma^{\mu}$ are
the Dirac matrices (regarded as a four-vector),
$\gamma^{5}=i\gamma^{0}\gamma^{1}\gamma^{2}\gamma^{3}$, and $g_{V,A}$ are
suitable coupling constants that parameterize the strength of the
interactions. As it was discussed for example in [29], in the non-relativistic
limit it is possible to make the following approximations for the dominant
temporal components of the four-vectors appearing in the above Hamiltonian,

$\displaystyle\bar{e}\gamma^{\mu}\gamma_{5}e$ $\displaystyle\sim$
$\displaystyle\vec{\sigma}_{e}\cdot\vec{v}_{e},\qquad\ $
$\displaystyle\bar{\nu}\gamma_{\mu}\nu$ $\displaystyle\sim$ $\displaystyle
n_{\nu}-n_{\bar{\nu}}\qquad(\textrm{Dirac neutrinos}),$
$\displaystyle\bar{\nu}\gamma_{\mu}\gamma_{5}\nu$ $\displaystyle\sim$
$\displaystyle n_{\nu_{l}}-n_{\nu_{r}}\qquad(\textrm{Majorana neutrinos}),$
(2)

where the number density differences, $n_{\nu}-n_{\bar{\nu}}$ and
$n_{\nu_{l}}-n_{\nu_{r}}$ refer to neutrino-antineutrino and left-right
helicity eigenstates respectively. Obviously they are not zero only in the
case where there is a net lepton number or helicity in the cosmic neutrinos
background. We recall from [25] and [30] that for Dirac neutrinos the energy
splitting obtained for the electron is

$\Delta E\sim
G_{F}|(n_{\nu}-n_{\bar{\nu}})\langle\vec{\sigma}_{e}\cdot\vec{v}_{e}\rangle|,$
(3)

where the expected value of the electron helicity
$\langle\vec{\sigma}_{e}\cdot\vec{v}_{e}\rangle$ takes opposite signs for the
two opposite enantiomers, as we can see from a simplified chiral molecule
model [31]. In this model, a dominant axial symmetry around axis Z, with a
left(right)-handed perturbative potential of period a, is assumed, so that the
electronic molecular states can be described by superposition of eigenstates
of both angular momentum $L_{z}$ and linear momentum $P_{z}$ (eigenvalues
$\hbar n(2\pi/a)$), i.e. $|M_{L},n\rangle$, in the form

$\displaystyle\Phi_{L}$ $\displaystyle=$ $\displaystyle
c_{0}|0,0\rangle+c_{1}|+1,-1\rangle+c_{2}|-1,+1\rangle\,,$ (4)
$\displaystyle\Phi_{R}$ $\displaystyle=$ $\displaystyle
c_{0}|0,0\rangle+c_{1}|+1,+1\rangle+c_{2}|-1,-1\rangle\,,$ (5)

with $|c_{1}|^{2}=|c_{2}|^{2}\equiv C$. These L and R states have then
opposite helicities:

$\langle\Phi_{L}|L_{z}P_{z}|\Phi_{L}\rangle=-4C\pi/a=-\langle\Phi_{R}|L_{z}P_{z}|\Phi_{R}\rangle\,.$
(6)

Notice that we are using all the time natural units where $\hbar=c=1$. The
spin of the electron can be taken into consideration by replacing $L_{z}$ with
$J_{z}=L_{z}+S_{z}$. In a realistic chiral molecule the electronic states
would not be eigenstates of the helicity, but its mean value would have
opposite sign for L and R enantiomers. The parameter $C<1/2$ accounts for the
degree of chirality.

We note that the velocity of the molecule carrier (interstellar grains,
meteorites, the Earth…) does not contribute to the helicity of the electrons:
If $\vec{P}_{T}$ is the translational momentum of the carrier, the electronic
wave function $\Phi_{L(R)}$ must include the factor
$e^{i\vec{P}_{T}\cdot\vec{R}}$ (here $\vec{R}$ is the position of the
molecule), and the contribution of $\vec{P}_{T}$ to the electron helicity is
then

$\displaystyle\langle\Phi_{L(R)}e^{i\vec{P}_{T}\cdot\vec{R}}|\vec{L}\cdot\vec{P}_{T}|\Phi_{L(R)}e^{i\vec{P}_{T}\cdot\vec{R}}\rangle$
$\displaystyle=\langle\Phi_{L(R)}|\vec{L}|\Phi_{L(R)}\rangle\cdot\vec{P}_{T}=0\,,$
(7)

since
$\langle\Phi_{L}|\vec{L}|\Phi_{L}\rangle=\langle\Phi_{R}|\vec{L}|\Phi_{R}\rangle=0$
as can be seen from Eqs. (4,5). We also remark that the particle flux is
assumed to be isotropic, thus, its interaction with the electrons of a chiral
molecule is the same irrespective of the orientation of the molecule.

The energy difference that we obtained, assuming complete neutrino-
antineutrino asymmetry, with number density of about
$10^{-2}\mathrm{cm}^{-3}$, $C=1/2$, $a\sim 1$ Angstrom and the electron
helicity given by Eq. (6), was of the order of $10^{-26}$ eV [25].

However, it has been recently suggested [29, 32] that, in scenarios beyond the
standard model, the neutrino-antineutrino density asymmetry
$n_{\nu}-n_{\bar{\nu}}$ could be up to the order of $\sim 10-1050\
\mathrm{cm}^{-3}$. Although the extreme upper bound density asymmetry seems to
be excluded by considerations of primordial nucleosynthesis [33], we consider
it to estimate an upper bound of the energy difference.

If we take the value $n_{\nu}-n_{\bar{\nu}}\sim 1000\ \mathrm{cm}^{-3}$, we
then obtain an upper bound for the energy difference between enantiomers of
the order of $10^{-21}$ eV, per molecular electron with non zero helicity.
Evidently this tiny energy needs massive amplification mechanisms as those
mentioned at the beginning in order to induce an effective enantioselection.

##  3 Energy difference between opposite enantiomers induced by fermionic cold
dark matter

In a similar way to the neutrino-electron interaction above considered, we are
now to estimate the electron energy splitting induced by the axial-vector
interaction between a fermionic dark matter candidate (typically a WIMP) and
an electron. The relevant Hamiltonian density can be written as

$H=\sum_{i}d_{i}\bar{\chi}\gamma_{\mu}(1-\gamma_{5})\chi\bar{\psi}_{i}\gamma^{\mu}\gamma_{5}\psi_{i},$
(8)

where $\chi$ is the dark matter spinor which can be Dirac or Majorana. The
index $i$ runs through $i=e,u,d,s$, i.e., we are considering also the
interaction between the dark matter particle and the $u,d$ and $s$ quarks.
This will be important later in order to use the present experiments trying to
measure the WIMP flux on Earth to set some bounds on the possible effect of
dark matter on opposite enantiomers. Therefore $d_{e},d_{u},d_{d}$ and $d_{s}$
are the coupling of the $\chi$ field to the different matter fields
$e=\psi_{e},u=\psi_{u},d=\psi_{d}$ and $s=\psi_{s}$.

As WIMPs are typical examples of cold dark matter and heavy by definition, we
can invoke again the non-relativistic limit. Thus, as it was the case of
neutrinos, for Dirac WIMPs the term $\bar{\chi}\gamma_{\mu}\chi$ dominates
with the temporal component of this vector being proportional to
$n_{\chi}-n_{\bar{\chi}}$. For the Majorana case only the axial vector
$\bar{\chi}\gamma_{\mu}\gamma_{5}\chi$ remains and its temporal component
becomes proportional to $n_{\chi_{l}}-n_{\chi_{r}}$, as in Eq. (2).

The expression for the corresponding electron energy splitting is similar to
that of Eq. (3),

$\Delta E\sim d_{e}|\Delta n\langle\vec{\sigma}_{e}\cdot\vec{v}_{e}\rangle|,$
(9)

where $\Delta n$ is the appropriate number density difference corresponding to
the Dirac or the Majorana case. In principle these differences depend on the
unknown nature of the dark matter and its evolution along the universe
history. In the following we will write these differences as $|\Delta
n|=\alpha n$ where $n$ is the total WIMP number density. Clearly the parameter
$\alpha$ is a measure of the degree of particle-antiparticle or left-right
asymmetry present in the the dark matter respectively. For example, in the
case of Dirac dark matter, $\alpha=1$ indicates that all WIMPs are particles
with no antiparticles present and $\alpha=0$ means a complete particle-
antiparticle symmetry. As in the neutrino case, interactions between molecular
electrons with non zero helicity and cold dark matter could lead to an energy
difference between the two enantiomers of a chiral molecule whenever the
parameter $\alpha$ is different from zero. To have an estimation of the energy
difference, we consider the interaction between WIMPs and an electron of a
chiral molecule. Let $\rho=nM_{\chi}$ be the energy density of those WIMPs,
with $M_{\chi}$ being their mass and $n$ their number density. The density of
WIMPs trapped in the gravitational potential wall of the galaxy is expected to
be of the order of $\rho\sim$ 0.3 GeV $\mathrm{cm}^{-3}$. Then the energy
splitting can be written as

$\Delta E\sim d_{e}\alpha\
\frac{\rho}{M_{\chi}}|\langle\vec{\sigma}_{e}\cdot\vec{v}_{e}\rangle|\,.$ (10)

In order to see how important this splitting could be, we need to know which
values of the coupling constant $d_{e}$ are acceptable. In principle there is
no any available experimental information about $d_{e}$. However one
reasonable assumption that could be done is that all the $d_{i}$ couplings are
at least of the same order of magnitude. In the absence of a theory of WIMPs
this seems to be not so bad assumption since WIMPs does not interact strongly
with matter. If this is the case, one can then use the present bounds on the
elastic cross-section proton$-\chi$ to get some information about the size of
the $d_{i}$ couplings. In order to compute this cross section, one needs to
relate the quark$-\chi$ couplings with the proton$-\chi$ coupling. This can be
done by using the effective Hamiltonian (see [34] and references therein)

$H=-a_{p}2\sqrt{2}\bar{\chi}\gamma_{\mu}\gamma_{5}\chi\bar{p}s^{\mu}p\,,$ (11)

where $p$ is the proton spinor and $s^{\mu}$ is its spin vector (here we are
considering the Majorana case but the Dirac case can be treated in a similar
way). The coupling $a_{p}$ is defined as

$a_{p}=\frac{1}{\sqrt{2}}\sum_{i=u,d,s}d_{i}\Delta q_{i}^{(p)}\,.$ (12)

The constants $\Delta q_{i}^{(p)}$ (with $q_{1}=u,q_{2}=d$ and $q_{3}=s$) are
introduced trough the proton matrix element

$\langle
p|\bar{\psi}_{i}\gamma^{\mu}\gamma_{5}\psi_{i}|p\rangle=2s^{\mu}\Delta
q^{(p)}.$ (13)

Experimentally we have $\Delta u^{(p)}\simeq 0.78$, $\Delta d^{(p)}\simeq-0.5$
and $\Delta s^{(p)}\simeq-0.16$. Then, by using standard methods, it is
straightforward to compute the elastic proton$-\chi$ cross-section, which is
given in the proton rest frame by

$\frac{d\sigma}{dq^{2}}=\frac{\sigma_{n}}{4v_{\chi}\mu^{2}}\,,$ (14)

where $\vec{q}$ is the momentum transfer, $v_{\chi}$ is the $\chi$ velocity,
$\mu$ is the proton $-\chi$ reduced mass and

$\sigma_{n}=\frac{12a_{p}^{2}m_{p}^{2}M_{\chi}^{2}}{\pi(m_{p}+M_{\chi})^{2}}$
(15)

($m_{p}$ being the proton mass) is just the non-relativistic cross section for
vanishing momentum transfer. Now days there are many experiments around the
world trying to detect WIMPs directly (visit the webpage [35] for complete and
upgraded report of their main results). Usually they set exclusion regions on
the plane $\sigma_{n}-M_{\chi}$. From the recent XENON10 2007 [35] we learn
for example that, for $M_{\chi}\simeq 100$ GeV, $\sigma_{n}$ must be lesser
than $10^{-43}$ cm2 and, for $M_{\chi}\simeq 1000$ GeV, lesser than $10^{-42}$
cm2. Assuming for simplicity all the quark couplings to be the same, i.e.
$d_{q}\simeq d_{u}\simeq d_{d}\simeq d_{s}$, we have $a_{p}\simeq
0.0072d_{q}^{2}$. Then we get that for $M_{\chi}\simeq 100$ GeV,
$d_{q}^{2}<10^{-14}$ GeV-4 and for $M_{\chi}\simeq 1000$ GeV,
$d_{q}^{2}<10^{-13}$ GeV-4. As discussed above we now assume $d_{e}\sim
d_{q}$. Then it is possible to set a bound on the energy splitting which turn
to be very tiny even in best case corresponding to $M_{\chi}\simeq 100$ GeV.
We obtain in this case, with an electron velocity about $10^{-2}$, $\Delta
E\leq\alpha 10^{-44}$ eV.

##  4 Conclusion

We have analyzed the effect of cold dark matter on the discrimination between
the two enantiomers of a chiral molecule whose external electrons have
opposite helicities in the respective opposite enantiomers. The estimated
energy difference between the two enantiomers, due to WIMP-electron
interaction, is found to be extremely small, several orders of magnitude lower
than that induced by electron-nuclei weak interaction. Hence, dark matter
would be discarded as inductor of chiroselection between enantiomers and then
of biological homochirality. By contrast, the enantioselective effect of the
cosmological relic sea of neutrinos acquires relevance with the current
assumptions about the number density of cosmological neutrinos. In this case
we obtain an energy difference between $10^{-23}$ and $10^{-21}$ eV for the
two opposite enantiomers per molecular electron with non zero helicity. The
upper bound of the energy difference, although could be excluded by reasons
previously mentioned, reaches the same order of magnitude as the energy
difference induced by the well known electron-nucleus electroweak interaction
in some molecules.

acknowledgments

This work is supported by DGICYT (Spain) project BPA2005-02327, by the
Universidad Complutense/CAM projects 910309 and CCG06-UCM/ESP-137, and by the
MEC (Spain) projects CTQ2005-09185-C02-02 and FIS2004-03267. The work of P.
Bargueño was supported by the FPI grant BES-2006-11976 from the Spanish MEC.
The authors would like to thank A. L. Maroto and R. Pérez de Tudela for useful
discussions.

## References

  * [1] Bonner, W.A., Orig. Life Evol. Biosph. 21, 59 (1991) .
  * [2] A. Jorissen and C. Cerf, Orig. Life Evol. Biosph., 32, 129 (2002).
  * [3] D. B. CLine (Ed.), Physical Origin of Homochirality in Life, AIP press, (1996)
  * [4] R.A. Hegstrom, A. Rich and J. Van House, Nature, 313, 391 (1985).
  * [5] J. Bailey, A. Chrysostomou, J.H. Hough et al., Science, 281, 672 (1998)
  * [6] J. Bailey, Orig. Life Evol. Biosph., 31, 167 (2001).
  * [7] M. Buscherm hle, D.C.B. Whittet, A. Chrysostomou et al., Astroph. Journal, 624, 821 (2005).
  * [8] G.L.J.A. Rikken and E. Raupach, Nature, 405, 932 (2000).
  * [9] T. Ruchon, M. Vallet, D. Chauvat et al., J. Chem. Phys., 125, 084104 (2006).
  * [10] M.H. Engel and S.A. Macko, Nature, 389, 265 (1997).
  * [11] S. Pizzarello and J.R. Cronin, Geochim. Cosmochim. Acta, 64, 329 (2000).
  * [12] W.A. Bonner, Orig. Life Evol. Biosph., 22, 407 (1992).
  * [13] A.M. Bouchiat and C.C. Bouchiat, Rep. Prog. Phys., 60, 1351 (1997).
  * [14] V. S. Letokhov, Phys. Lett., 53A, 275 (1975).
  * [15] D. W. Rein, R.A. Hegstrom and P.G.H. Sandars, J. Chem. Phys., 73, 2329 (1980).
  * [16] R. Zanasi, A. Lazzeretti and A. Soncini, Phys. Rev. E, 59, 3382 (1999)
  * [17] J.K. Laerdahl and P. Schwerdtfeger, Phys. Rev. Lett, 84, 3811 (2000).
  * [18] P. Soulard et al., Phys. Chem. Chem. Phys., 8, 79 (2006).
  * [19] J. Crassous et al., Org. Biomol. Chem., 3, 2218 (2005).
  * [20] D.K. Kondepudi and G.M. Nelson, Nature, 314, 438 (1985).
  * [21] R. Plasson, D. K. Kondepudi, H. Bersini, A. Commeyras and K. Asakura, Chirality, 19, 589 (2007).
  * [22] A. Salam, J. Mol. Evol., 33,105 (1991).
  * [23] M. Avalos, R. Babiano, P. Cintas, J. L. Jiménez and J. C. Palacios, Tetr. Asymm., 11, 2845 (2000).
  * [24] S. Chandrasekhar,Chirality, 20, 84 (2008).
  * [25] P. Bargueño and I. Gonzalo, Orig. Life Evol. Biosph., 36, 171 (2006).
  * [26] P. Bargueño and R. Pérez de Tudela, Orig. Life Evol. Biosph., 37, 253 (2007).
  * [27] C. Muñoz, Int. J. Mod. Phys., A19, 3093 (2004).
  * [28] B. Sadoulet, Rev. Mod. Phys., 71, 197 (1999).
  * [29] G. B. Gelmini, Phys. Script., T121, 131, 2005.
  * [30] L. Stodolsky, Phys. Rev. Lett., 34, 110, 1975.
  * [31] J. L. Pérez-Díaz, V. M. Pérez-García and I. Gonzalo, Phys. Lett. A, 160, 453 (1991).
  * [32] G. Duda, G. Gelmini and S. Nussinov, Phys. Rev. D, 64, 122001 (2001).
  * [33] A. D. Dolgov et al., Nucl.Phys. B, 632, 363 (2002).
  * [34] P. Binetruy, Supersymmetry: Theory, Experiment and Cosmology, Oxford University Press, (2006).
  * [35] http://dmtools.berkeley.edu


An adaptive controller with bounded $l_2$-gain from disturbances to errors
is derived for linear time-invariant systems with uncertain parameters restricted to a finite set. The gain bound refers to the closed loop system, including the non-linear learning procedure. As a result, robustness to unmodelled dynamics (possibly nonlinear and infinite-dimensional) follows from the small gain theorem. The approach is based on a new zero-sum dynamic game formulation, which optimizes the trade-off between exploration and exploitation. An explicit upper bound on the optimal value function is stated in terms of semi-definite programming and a corresponding simple formula for an adaptive controller achieving the upper bound is given. Once the uncertain parameters have been sufficiently estimated, the controller behaves like standard $H_\infty$ optimal control.

adaptive control, real-time learning

§ INTRODUCTION

The history of adaptive control dates back at least to aircraft autopilot development in the 1950s. Following the landmark paper [Åström and Wittenmark, 1973], a surge of research activity during the 1970s derived conditions for convergence, stability, robustness and performance under various assumptions. For example, [Ljung, 1977] analysed adaptive algorithms using averaging, [Goodwin et al., 1981] derived an algorithm that gives mean square stability with probability one, while [Guo, 1995] gave conditions for the optimal asymptotic rate of convergence. On the other hand, conditions that may cause instability were studied in [Egardt, 1979], [Ioannou and Kokotovic, 1984] and [Rohrs et al., 1985]. Altogether, the subject has a rich history documented in numerous textbooks, such as [Åström and Wittenmark, 2013], [Goodwin and Sin, 2014], [Narendra and Annaswamy, 2012], [Sastry and Bodson, 2011] and [Astolfi et al., 2007]. In this paper, the focus is on worst-case models for disturbances and uncertain parameters, as discussed in [Cusumano and Poolla, 1988, Sun and Ioannou, 1987, Vinnicombe, 2004] and [Megretski, 2004]. The “minimax adaptive” paradigm illustrated in Figure <ref> was introduced for linear systems in [Didinsky and Basar, 1994] and nonlinear systems in [Pan and Basar, 1998].

More recently, there has been an explosion of research interest in the boundary between machine learning, system identification and adaptive control. For a review, see for example [Matni et al., 2019]. Most of the studies are carried out in a stochastic setting, but recently works connecting to $H_\infty$ control have started to appear [Dean et al., 2018]. There is also recent work connecting adversarial learning and minimax regret analysis to robust control [Zhang et al., 2020].
However, it is worth noting that unlike most recent contributions the minimax approach of this paper will not assume that a stabilizing controller is known in advance.

This paper is an extension and generalization of the approach presented in [Rantzer, 2020]. The outline is as follows: After some notation in sections 2, we give the problem formulation in section 3, followed by preliminary results on minimax dynamic programming in section 4.
The main result is first presented in section 5 for the special case of input sign uncertainty with a double integrator as an illustrating example, then proved for the general case in section 6. Some calculations are deferred to an appendix.

Adaptive Controller

Linear dynamics with
uncertain parameters

(4000,-4561)(-1, 0)1150
(2851,-4561)( 0, 1)2550
(2851,-2011)( 1, 0)1650
(4000,-5161)(-1, 0)1150
(2851,-5161)( 0,-1)2550
(2851,-7711)( 1, 0)1150
(4000,-4861)(-1, 0)2900
(10651,-4861)(-1, 0)2450
(7501,-2011)( 1, 0)1650
(9151,-2011)( 0,-1)2550
(9151,-4561)(-1, 0)950
(8201,-7711)( 1, 0)950
(9151,-7711)( 0, 1)2550
(9151,-5161)(-1, 0)950

Given a finite set of stabilizable linear models, the objective of this paper is to construct an adaptive controller that minimizes the $l_2$-gain from disturbances to errors under worst case values of the uncertain parameters. The gain bound gives a guaranteed robustness to unmodelled (possibly nonlinear and infinite-dimensional) dynamics. Optimal trade-off between exploration and exploitation is needed for minimization of the gain.

§ NOTATION

The set of $n\times m$ matrices with real coefficients is denoted $\realR^{n\times m}$. The transpose of a matrix $A$ is denoted $A^\top$. For a symmetric matrix $A\in\realR^{n\times n}$, we write $A\succ0$ to say that $A$ is positive definite, while $A\succeq0$ means positive semi-definite. For $A, B\in\realR^{n\times m}$, the expression $\langle A,B\rangle$ denotes the trace of $A^\top B$. Given $x\in\realR^n$ and $A\in\realR^{n\times n}$, the notation $|x|^2_A$ means
$x^\top Ax$. Similarly, given $B\in\realR^{m\times n}$ and $A\in\realR^{n\times n}$, the trace of $B^\top AB$ is denoted $\|B\|^2_A$.

§ MINIMAX ADAPTIVE CONTROL

Let $Q\in\realR^{n\times n}$ and $R\in\realR^{m\times m}$ be positive definite. Given a compact set $\mathcal{M}\subset\realR^{n\times n}\times\realR^{n\times m}$ and a number $\gamma>0$, we are interested to compute

\begin{align}
\label{eqn:infsup}
\end{align}

where $(A,B)\in\mathcal{M}$, $w_t\in\realR^n$, $N\ge0$ and the sequences $x$ and $u$ are generated according to

\begin{align}
x_{t+1}&=Ax_t+Bu_t+w_t& t&\ge0 %&=0,1,2,\ldots,T
\label{eqn:plant}\\
\label{eqn:mu_LQ}
\end{align}

The problem above can be viewed as a dynamic game, where the $\mu$-player tries to minimize the cost, while the $(w,A,B)$-player tries to maximize it. If it wasn't for the uncertainty in $(A,B)$, this would be the standard game formulation of $H_\infty$ optimal control [Basar and Bernhard, 1995]. In our formulation, the maximizing player can choose not only $w$, but also the matrices $A,B$. The matrices are unknown but constant, so an optimal feedback law tends to “learn” $A$ and $B$ early on, in order to exploit this knowledge later.
Such nonlinear adaptive controllers can stabilize and optimize the behavior also when no linear controller can simultaneously stabilize (<ref>) for all $(A,B)\in\mathcal{M}$.

To accommodate the uncertainty in $(A,B)$ when deciding $u_t$, it is natural for the controller to consider historical data collected in the matrix

\begin{align}
\begin{bmatrix}-x_{\tau+1}\\x_\tau\\u_\tau\end{bmatrix}^\top}
\label{eqn:Z_t}
\end{align}

since this gives
\left\|\begin{bmatrix}I\;\;\,A\;\;\,B\end{bmatrix}^\top\right\|^2_{Z_t}
$. In fact, we will prove in Theorem <ref> that knowledge of $x_t$ and $Z_t$ is sufficient for optimal control. The result will be based on the following reformulated problem:
Given $Q\succ0, R\succ0$, $\gamma>0$, a set $\mathcal{M}$ and the system

\begin{align}
\left\{\begin{array}{ll}
\begin{bmatrix}-v_t\\x_t\\u_t\end{bmatrix}^\top},\qquad &Z_0=0,
\end{array}\right.
\label{eqn:xZ}
\end{align}

find a control law

\begin{align}
\label{eqn:eta}
\end{align}

to minimize

\begin{align}
\inf_\eta\sup_{v,N}\Bigg[\sum_{t=0}^N\left(|x_t|_Q^2+|u_t|_R^2\right)
\label{eqn:infsup2}
\end{align}

when $x,u,Z$ are generated from $v$
according to

In this formulation, the unknown $(A,B)$ does not appear in the dynamics, only in the penalty of the final state. As a consequence, no past states are needed in the control law (<ref>), only the current state $(x_t,Z_t)$. In fact, the problem is a standard zero-sum dynamic game [Basar and Olsder, 1999], which will next be addressed by dynamic programming.

§ MINIMAX DYNAMIC PROGRAMMING

Define the operators $\mathcal{F}$ and $\mathcal{F}_u$ by

\begin{align*}
\begin{bmatrix}-v\\x\\u\end{bmatrix}^\top}\right)\right\}}_{\mathcal{F}_uV(x,Z)}.
\end{align*}

Then the following result holds:

Given $Q,R,\mathcal{M}$, define the operator ${\mathcal{F}}$ as above and $V_0,V_1,V_2\ldots$ according to the iteration

\begin{align}
\label{eqn:Bellman_t}
\end{align}

The expressions (<ref>) and (<ref>) have the same value. The value is finite if and only if the sequence $\{V_k(x,0)\}_{k=0}^\infty$ is upper bounded. If so, the limit $V_*:=\lim_{k\to\infty}V_k$ exists and $J_*(x_0)=V_*(x_0,0)$.
Defining $\eta(x,Z)$ as the minimizing value of $u$ in the expression for ${\mathcal{F}}V_*(x,Z)$ gives an optimal $\eta^*$ for (<ref>), while the control law $\mu^*$ defined by

\begin{align}
\mu^*_t(x_0,\ldots,x_t,u_0,\dots,u_{t-1})
\begin{bmatrix}-x_{\tau+1}\\x_\tau\\u_\tau\end{bmatrix}^\top}\right)
\label{eqn:muopt}
\end{align}

is optimal for (<ref>). Moreover, if there exists a function $\bar{V}$ satisfying $\bar{V}\ge V_0$ and ${\mathcal{F}}_{\bar\eta}\bar{V}\le\bar{V}$, then
the control law $\bar\mu$ defined by $u_t=\bar\eta(x_t,Z_t)$ satisfies $J_{\bar\mu}(x_0)\le\bar{V}(x_0,0)$.

\begin{align*}
\begin{bmatrix}-v\\x\\u\end{bmatrix}^\top}\right)\\
\end{align*}

so $V_1\ge V_0$ and the sequence $V_0,V_1,V_2,\ldots$ is monotonically non-decreasing.

For any fixed $N\ge0$, the value of (<ref>) is bounded below by the expression

\begin{align}
\inf_\mu\sup_{w,A,B}\sum_{t=0}^N\left(|x_t|_Q^2+|u_t|_R^2-\gamma^2|w_t|^2\right),
\label{eqn:infsup_N} %\\\notag
\end{align}

where $(A,B)\in\mathcal{M}$, $w_t\in\realR^n$ and the sequences $x$ and $u$ are generated according to (<ref>)-(<ref>).
The value of (<ref>) grows monotonically with $N$ and (<ref>) is obtained in the limit. A change of variables with $v_t:=x_{t+1}$ and $Z_t$ given by (<ref>) shows that (<ref>) is equal to

\begin{align}
\inf_\mu\sup_{v}\left[\sum_{t=0}^N\left(|x_t|_Q^2+|u_t|_R^2\right)-\gamma^2\min_{A,B}\big\|\begin{bmatrix}I\;\;A\;\;\,B\end{bmatrix}^\top\big\|^2_{Z_{N+1}}\right]
\label{eqn:sup_vT}
\end{align}

where $x,Z,u$ are generated by (<ref>) combined with (<ref>).
Standard dynamic programming shows that the value of (<ref>) is $V_{N+1}(x_0,0)$, where $V_k$ is defined by (<ref>)-(<ref>).
This proves that (<ref>) has a finite value if and only if the sequence $\{V_k(x,0)\}_{k=0}^\infty$ is upper bounded. The limit $V_*(x_0,0)$ is equal to the value of (<ref>). The relationship $V_k(x,Z)\le V_k(x,0)$ for $Z\succeq0$ shows that the limit then exists for all $Z\succeq0$.

If (<ref>) is finite, then $V_k$ is bounded above by (<ref>), so also $V_*:=\lim_{k\to\infty}V_k$ is finite. Conversely, if $V_0\le\bar{V}\le\infty$ and ${\mathcal{F}}_{\bar{\eta}}\bar{V}\le\bar{V}$, we may define the sequence $W_0,W_1,W_2,\ldots$ recursively by $W_0:=V_0$ and

\begin{align*}
\end{align*}

By dynamic programming,

\begin{align*}
\end{align*}

where $x,Z,u$ are generated by (<ref>) and (<ref>). Hence (<ref>) is bounded above by $\lim_{k\to\infty}W_k(x_0,0)$. The definitions of $V_k$ and $W_k$ give by induction $\bar{V}\ge W_k\ge V_k$ for all $k$, so $V_*\le\lim_{k\to\infty}W_k\le\bar{V}$. This proves that $V_*(x_0,0)\le J_{\bar{\mu}}(x_0)\le \bar{V}(x_0,0)$ when the control law $\bar\mu$ is defined by $u_t=\bar\eta(x_t,Z_t)$. In particular, the control law is optimal if $\bar{V}=V_*$.

We conclude the section by pointing out that even though all our results assume full state measurements, they are immediately applicable also to input-output models. For example, the input-output model

\begin{align}
%    \sum_{k=1}^m\left(b_ku_{t-k}-a_ky_{t-k}\right)
\label{eqn:IO}
\end{align}

has the (non-minimal) state realization $x_{t+1}=Ax_t+Bu_t$ where

\begin{align}
\end{bmatrix}&
\end{bmatrix}&
\end{bmatrix}
\label{eqn:IOstate}
\end{align}

where all states are known from the inputs and outputs. This also shows that it is not really restrictive to consider $B$ as known. Example 1 will use this state realization for a double integrator where only the output of the second integrator is available for measurement.

§ SYSTEMS WITH UNKNOWN INPUT DIRECTION

The following result gives an explicit expression for an adaptive controller satisfying a pre-specified bound on the $L_2$-gain for any stabilizable model set of the form

\begin{align*}
\mathcal{M}&:=\{(A,B),(A,-B))\}\subset\realR^{n\times n}\times\realR^{n\times m}.
\end{align*}

Consider $A\in\realR^{n\times n}$, $B\in\realR^{n\times m}$ and positive definite $Q\in\realR^{n\times n}$ and $R\in\realR^{m\times m}$. Suppose
there exists $K\in\realR^{m\times n}$ and symmetric  $P,T\in\realR^{n\times n}$ satisfying
$0\prec P\prec T\prec \gamma^2I$ and

\begin{align}
P&\succeq Q+K^\top RK+(A-BK)^\top (P^{-1}-\gamma^{-2}I)^{-1}(A-BK)\label{eqn:P}\\
T&\succeq Q+K^\top RK+(A+BK)^\top (P^{-1}-\gamma^{-2}I)^{-1}(A+BK)\label{eqn:T}\\
T&\succeq Q+K^\top(R-\gamma^2B^\top B)K
\end{align}

Then the Bellman inequality $\bar{V}\le\mathcal{F}\bar{V}$ is satisfied by

\begin{align}
\bar{V}(x,Z):=
-\gamma^2\left\|\begin{bmatrix}I&A&\pm B\end{bmatrix}^\top\right\|_Z^2,
[I\;\;A]^\top[I\;\;A]&0\\0&B^\top B
\end{bmatrix}Z\right)\right\}
\label{eqn:Vbar}
\end{align}

and the bound $J_\mu(x_0)\le|x_0|^2_{T}$ is valid for the control law (<ref>) defined by

\begin{align}
-Kx&\hbox{if }\sum_{\tau=0}^{t-1}(x_{\tau+1}-Ax_\tau)^\top Bu_\tau\ge0\\
\end{cases}
\label{eqn:Lcontrol}
\end{align}

Theorem <ref> is a special case of Theorem <ref>, to be proved later. Defining

\begin{align*}
\end{align*}

turns (<ref>)-(<ref>) into (<ref>)-(<ref>).

See Figure <ref> for an illustration. Following (<ref>)-(<ref>), we model a double integrator with unknown sign of the input gain as

\begin{align*}
\end{bmatrix}}_{A}x_t
\pm\underbrace{\begin{bmatrix}
\end{bmatrix}}_Bu_t+w_t
\end{align*}

where the state is $x_t=\begin{bmatrix}
\end{bmatrix}^\top$. Theorem <ref> can be applied with $\mathcal{M}=\{(A,\pm B)\}$. By first solving the Riccati equation for $P$ and $K$, then solving the matrix inequalities for $T$ by convex optimization, we get

\begin{align*}
20.61 & -11.09 &  11.09\\
-11.09 &   7.83 &  -6.83\\
11.09 &  -6.83 &   7.83
\end{array}\right]&
155.0 & -84.4 & 84.4\\
-84.4 & 89.0 & -87.5\\
84.4 & -87.5 & 89.0
\end{array}\right]\\
\gamma&=19&K&=\left[\begin{array}{rrr}
\;\;1.786 &  -1.288 &   1.288
\end{array}\right]
\end{align*}

Simulations with the control law (<ref>) are shown in Figure <ref>, first for $w=0$, then for $w$ being a white noise sequence. The case with worst case disturbance $w$ is not plotted, since it actually makes the state grow exponentially according to the formula $x_{t+1}=(I-\gamma^{-2}T)^{-1}Ax_t$. This does not mean that the system is unstable. Instead, what happens is that the worst disturbance $w$ grows exponentially, to keep the current state large compared to past data and prevent the adaptive controller from becoming confident about the input matrix sign. The construction can be used to verify that the

the $l_2$-gain from $w$ to $(Q^{1/2}x,R^{1/2}u)$
when using the adaptive control law (<ref>) is somewhere between $\sqrt{\|T\|}=16.8$ and $\gamma=19$.

(4501,-4861)(3700,1200)Unmodelled dynamics
(11301,-3061)(1200,1200)$\pm 1$
(3301,-2461)(-1, 0)2200
(7301,-2461)(-1, 0)2200
(11301,-2461)(-1, 0)2200
(14001,-2461)(-1, 0)1500
(2501,-2461)( 0,-1)1800
(10101,-4261)( 0,1)1720
(2501,-4261)( 1, 0)2000
(8201,-4261)( 1, 0)1900
(10501,-2161)$\pm u_t$

No linear feedback can stabilize a double integrator with unknown input sign. However,
Example 1 illustrates how a minimax adaptive controller can do this and even get robustness to a certain amount of unmodelled dynamics. Only the output of the second integrator is measured, but using (<ref>)-(<ref>) it is still possible to write a double integrator on state space form with a fully accessible state.

Output (left) and input (right) are plotted for the double integrator with input matrix sign uncertainty, controlled using a minimax adaptive controller (blue plots with circles). For comparison, trajectories of the optimal controller with known input matrix sign are also given (red plots). The top plots have been generated with $w=0$. The minimax controller automatically increases control activity for the purpose of exploration in the beginning. In the lower plots, $w$ is a white noise sequence and the sign of the input matrix is changed at $t=10$. The adaptation takes longer the second time, since data collected before $t=10$ makes the adaptive controller reluctant to change its internal model.

§ EXPLICIT SOLUTION OF THE BELLMAN INEQUALITY IN THE GENERAL CASE

The following result gives an explicit expression for an adaptive controller satisfying a pre-specified bound on the $L_2$-gain for model sets of the form

\begin{align}
\mathcal{M}&:=\{(A_1,B_1),\ldots,(A_N,B_N))\}\subset\realR^{n\times n}\times\realR^{n\times m}.
\label{eqn:Mfinite)}
\end{align}

Given $A_1,\ldots,A_N\in\realR^{n\times n}$, $B_1,\ldots,B_N\in\realR^{n\times m}$ and positive definite $Q\in\realR^{n\times n}$, $R\in\realR^{m\times m}$, suppose there exist $K_1,\ldots,K_N\in\realR^{m\times n}$ and $P_{ij}\in\realR^{n\times n}$ with
$0\prec P_{ij}\prec \gamma^2I$ and

\begin{align}
%    |x|^2_{P_k}&\ge|x|^2_Q+|K_kx|^2_R+|(A_k-B_kK_k)x|^2_{(P_k^{-1}-\gamma^{-2}I)^{-1}} \label{eqn:Pii}\\
\label{eqn:Pik}
\end{align}

for $x\in\realR^n$ and $i,j,k\in\{1,\ldots,N\}$. Then the Bellman inequality $\bar{V}\le\mathcal{F}\bar{V}$ is satisfied by

\begin{align}
\bar{V}(x,Z):=
-\frac{\gamma^2}{2}\left\|\begin{bmatrix}I&A_i& B_i\end{bmatrix}^\top\right\|_Z^2
-\frac{\gamma^2}{2}\left\|\begin{bmatrix}I&A_j& B_j\end{bmatrix}^\top\right\|_Z^2
\right\}
\label{eqn:Vbar_is}
\end{align}

and the bound $J_\mu(x_0)\le\max_{i,j}|x_0|^2_{P_{ij}}$ is valid for the control law $\mu$ defined by

\begin{align}
u_t&=-K_{k_t}x_t,\hbox{ where }
\end{align}

One way to approach the solution of (<ref>) is to first solve the Riccati equations

\begin{align*}
\end{align*}

for ${P_{ii}}$ and the minimizing control laws $u=-K_ix$, then use semi-definite programming to determine $P_{ij}$ for $i\ne j$. If no solution exists, then increase $\gamma$. However, it should be noted that this approach is not guaranteed to find a solution with the smallest possible $\gamma$.

The inequalities (<ref>) have interesting interpretations. First, for $i=j=k$ it is the standard $H_\infty$ Riccati inequality, which specifies that $|x|^2_{P_{ii}}$ is an upper bound on the minimax cost function for the system $(A_i,B_i)$ when the model is known. Second, for $i=j\ne k$ it
shows that the difference in step cost due to use of a controller that does not match the model is upper bounded by $|x|^2_{P_{ik}}-|x|^2_{P_{ii}}$. Third, (<ref>) also shows that if improved model knowledge is taken into account, then cost-to-go is decreasing even when the “wrong” controller is used. This is due to the last term of the inequality, which represents improved knowledge about the system due to learning.

Define for $i,j\in\{1,\ldots,N\}$

\begin{align*}
%    V^0(x,Z)&:=\max_{i\ne j}V^{ij}(x,Z)&
\end{align*}

Then $\bar{V}=\max_{i,j}V^{ij}$. Define $k:=\arg\min_iz_i$. Lemma <ref> in the Appendix together with (<ref>) give

\begin{align*}
\mathcal{F}_{-K_kx}V^{ij}(x,Z)
\begin{bmatrix}-v\\x\\-K_kx\end{bmatrix}^\top\right)\right\}\\
&\le V^{ik}(x,Z).
\end{align*}

\begin{align*}
\mathcal{F}\bar{V}(x,Z)
\le\max_{i}V^{ik}(x,Z)\le\bar{V}(x,Z).
\end{align*}

so the Bellman inequality $\bar{V}\le\mathcal{F}\bar{V}$ is proved.
Moreover, the control law $u=-K_kx$ can equivalently be written as (<ref>), since (<ref>) gives

\begin{align*}
\left\|\begin{bmatrix}I&A_i&B_i\end{bmatrix}^\top\right\|_{Z_t}^2
\end{align*}

Finally, the inequality $J_\mu(x_0)\le\max_{i,j}|x_0|^2_{P_{ij}}$ follows by application of  Theorem <ref>.

§ CONCLUSIONS

Two main contributions have been given in the is paper. First, Theorem <ref> shows that the minimax adaptive control problem can be stated as a standard zero sum dynamic game with a finite-dimensional state space. Second, Theorem <ref> gives and explicit upper bound for the value of the game and a corresponding adaptive control scheme achieving the upper bound. We believe that the approach has tremendous potential for applications and generalizations in various directions. However, we also believe that upper bound of Theorem <ref> may not be the last word, but rather a first step towards an exact formula for the minimal achievable gain and a seed for a rich new theory of the interplay between learning and control.

The author is grateful to Olle Kjellqvist for help with constructing the example. Both are members of the excellence center ELLIIT. Financial support was obtained from the Swedish Research Council, the European Research Council and the Swedish Foundation for Strategic Research. The work was also partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

§ APPENDIX: QUADRATIC OPTIMIZATION.

For $P\in\realR^{n\times n}$, $y,v\in\realR^n$ and $\gamma\in\realR$, it holds that

\begin{align*}
\max_{v}\left\{|v|^2_P-\gamma^2|y-v|^2\right\}
\end{align*}

\begin{align*}
\max_{v}\left\{|v|^2_P-\gamma^2|y-v|^2\right\}
&=\max_{v}\left\{|v|^2_{(P-\gamma^2I)}-\gamma^2|y|^2+2\gamma^2y^\top v\right\}\\
\end{align*}

For $T\in\realR^{n\times n}$, $y_1,y_2,v\in\realR^n$ and $\gamma\in\realR$, it holds that

\begin{align*}
%        &=|(y_1+y_2)/2|^2_{\gamma^4(\gamma^{2}I-T)^{-1}}-\gamma^2(|y_1|^2+|y_2|^2)/2
\end{align*}

Application of Lemma <ref> gives

\begin{align*}
\end{align*}

[Astolfi et al., 2007]
Alessandro Astolfi, Dimitrios Karagiannis, and Romeo Ortega.
Nonlinear and adaptive control with applications.
Springer Science & Business Media, 2007.

[Åström and Wittenmark, 1973]
Karl Johan Åström and Björn Wittenmark.
On self-tuning regulators.
Automatica, 9:0 185–199, January 1973.

[Åström and Wittenmark, 2013]
Karl Johan Åström and Björn Wittenmark.
Adaptive control.
Courier Corporation, 2013.

[Azar et al., 2017]
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.
Minimax regret bounds for reinforcement learning.
arXiv preprint arXiv:1703.05449, 2017.

[Basar and Bernhard, 1995]
T. Basar and P. Bernhard.
${H}_{\infty}$-Optimal Control and Related Minimax Design
Problems —A Dynamic Game Approach.
Birkhauser, 1995.

[Basar and Olsder, 1999]
Tamer Basar and Geert Jan Olsder.
Dynamic noncooperative game theory, volume 23.
SIAM, 1999.

[Cusumano and Poolla, 1988]
Salvatore J Cusumano and Kameshwar Poolla.
Nonlinear feedback vs. linear feedback for robust stabilization.
In Decision and Control, 1988., Proceedings of the 27th IEEE
Conference on, pages 1776–1780. IEEE, 1988.

[Dean et al., 2018]
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu.
Regret bounds for robust adaptive control of the linear quadratic
In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi,
and R. Garnett, editors, Advances in Neural Information Processing
Systems, volume 31, pages 4188–4197. Curran Associates, Inc., 2018.

[Didinsky and Basar, 1994]
Garry Didinsky and Tamer Basar.
Minimax adaptive control of uncertain plants.
In Proceedings of 1994 33rd IEEE Conference on Decision and
Control, volume 3, pages 2839–2844. IEEE, 1994.

[Egardt, 1979]
Bo Egardt.
Stability of Adaptive Controllers.
Springer-Verlag, Berlin, FRG, January 1979.

[Goodwin and Sin, 2014]
Graham C Goodwin and Kwai Sang Sin.
Adaptive filtering prediction and control.
Courier Corporation, 2014.

[Goodwin et al., 1981]
Graham C Goodwin, Peter J Ramadge, and Peter E Caines.
Discrete time stochastic adaptive control.
SIAM Journal on Control and Optim., 190 (6):0
829–853, 1981.

[Guo, 1995]
Lei Guo.
Convergence and logarithm laws of self-tuning regulators.
Automatica, 310 (3):0 435–450, 1995.

[Ioannou and Kokotovic, 1984]
Petros A Ioannou and Petar V Kokotovic.
Instability analysis and improvement of robustness of adaptive
Automatica, 200 (5):0 583–594, 1984.

[Ljung, 1977]
Lennart Ljung.
Analysis of recursive stochastic algorithms.
IEEE Transactions on Automatic Control, AC-22:0
551–575, January 1977.

[Matni et al., 2019]
Nikolai Matni, Alexandre Proutiere, Anders Rantzer, and Stephen Tu.
From self-tuning regulators to reinforcement learning and back again.
In 2019 IEEE 58th Conference on Decision and Control (CDC),
pages 3724–3740. IEEE, 2019.

[Megretski, 2004]
A Megretski.
A nonlinear dynamical game interpretation of adaptive l2 control:
Performance limitations and suboptimal controllers.
In Proceedings of 16th International Symposium on Mathematical
Theory of Networks and Systems (MTNS2004), Leuven, 2004.

[Narendra and Annaswamy, 2012]
Kumpati S Narendra and Anuradha M Annaswamy.
Stable adaptive systems.
Courier Corporation, 2012.

[Pan and Basar, 1998]
Zigang Pan and Tamer Basar.
Adaptive controller design for tracking and disturbance attenuation
in parametric strict-feedback nonlinear systems.
IEEE Transactions on Automatic Control, 430
(8):0 1066–1083, 1998.

[Rantzer, 2020]
Anders Rantzer.
Minimax adaptive control for state matrix with unknown sign.
In Proceedings of IFAC congress, 2020.
Corrected version avaliable from arXiv:1912.03550.

[Rohrs et al., 1985]
C Rohrs, Lena Valavani, Michael Athans, and Gunter Stein.
Robustness of continuous-time adaptive control algorithms in the
presence of unmodeled dynamics.
IEEE Transactions on Automatic Control, 300
(9):0 881–889, 1985.

[Sastry and Bodson, 2011]
Shankar Sastry and Marc Bodson.
Adaptive control: stability, convergence and robustness.
Courier Corporation, 2011.

[Sun and Ioannou, 1987]
J Sun and PA Ioannou.
The theory and design of robust adaptive controllers.
Automatica, pages 19–24, 1987.

[Vinnicombe, 2004]
Glenn Vinnicombe.
Examples and counterexamples in finite l2-gain adaptive control.
In Proceedings of 16th International Symposium on Mathematical
Theory of Networks and Systems (MTNS2004), Leuven, 2004.

[Zhang et al., 2020]
Kaiqing Zhang, Bin Hu, and Tamer Basar.
On the stability and convergence of robust adversarial reinforcement
learning: A case study on linear quadratic systems.
Advances in Neural Information Processing Systems, 33, 2020.