# OCHADAI at SemEval-2022 Task 2: Adversarial Training for Multilingual
Idiomaticity Detection

Lis Kanashiro Pereira1, Ichiro Kobayashi2
Ochanomizu University
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

We propose a multilingual adversarial training model for determining whether a
sentence contains an idiomatic expression. Given that a key challenge with
this task is the limited size of annotated data, our model relies on pre-
trained contextual representations from different multilingual state-of-the-
art transformer-based language models (i.e., multilingual BERT and XLM-
RoBERTa), and on adversarial training, a training method for further enhancing
model generalization and robustness. Without relying on any human-crafted
features, knowledge bases, or additional datasets other than the target
datasets, our model achieved competitive results and ranked 6th place in
SubTask A (zero-shot) setting and 15th place in SubTask A (one-shot) setting.

##  1 Introduction

Large-scale pre-trained language models such as BERT Devlin et al. (2019) have
achieved great success in a wide range of natural language processing (NLP)
tasks. However, more recent studies show that even such contextual models have
a limited ability to capture idiomaticity Garcia et al. (2021). Idiomatic
expressions denote a group of words that behave as single words to some
extent. Their linguistic behavior cannot be inferred from the characteristics
of their components, and still pose a challenge to natural language processing
(NLP) systems.

This paper describes the system developed by the OCHADAI team for SemEval-2022
Task 2 - Multilingual Idiomaticity Detection and Sentence Embedding Tayyar
Madabushi et al. (2022). Given that a key challenge in this task is the
limited size of annotated data, we follow best practices from recent work on
enhancing model generalization and robustness and propose a model ensemble
that leverages multilingual pre-trained representations and adversarial
training. Our model ranked 6th on SubTask A (zero-shot), and 15th on SubTask A
(one-shot).

##  2 Task Description

SemEval-2021 Task 2 SubTask A consists of a binary classification task that
requires classifying sentences with a target multiword expression (MWE) into
either "Idiomatic" or "Literal" across English, Portuguese and Galician Tayyar
Madabushi et al. (2021). Further, it is subdivided into two settings to better
test models’ ability to generalize: zero-shot and one-shot. In the zero-shot"
setting, multiword expressions (potentially idiomatic phrases), in the
training set are completely disjoint from those in the test and development
sets. In the "one-shot" setting, one positive and one negative training
examples are included for each MWE in the test and development sets. Note that
the actual examples in the training data are different from those in the test
and development sets in both settings. Only the datasets provided by the
organizers are allowed to train the models. Participants can use only the data
provided for the zero-shot setting to train the zero-shot model. However,
participants were allowed to use data provided for both settings to train
models in the one-shot setting. The statistics of the corpus are presented in
Table 1. Our team submitted results for both settings, and the next section
outlines the overview of our model.

Setting | Language | Train | Dev | Eval | Test
---|---|---|---|---|---
zero-shot | English | 3,327 | - | - | -
Portuguese | 1,164 | - | - | -
Galician | 0 | - | - | -
one-shot | English | 87 | 466 | 483 | 916
Portuguese | 53 | 273 | 279 | 713
Galician | 0 | 0 | 0 | 713
Table 1:  Summary of the SemEval 2022 Task 2 Subtask A dataset. Note that the dev, eval and test sets are used in both settings. Setting | Language |  Sentence | Target MWE | Label
---|---|---|---|---
zero-shot | English |  This song is about unconditionally supporting someone you love. This is a love song. Let’s be there for each other. | love song | 1
one-shot | Portuguese |  Estamos honrando o teto e construindo as paredes”, afirmou. Em outro momento, voltando ao tema do impasse do Orçamento, ele reforçou que a busca é por uma solução, que a briga tem “mérito” e que “sempre, em grande rebanho, tem uma ovelha negra”."Mas não é o Congresso nem o grosso do ministério”, completou. | ovelha negra | 0
one-shot | Galician |  Non podemos abandonalos á súa sorte, porque sen mozos e mozas no campo e sen a súa actividade agraria suporía, entre outras cousas, a deslocalización da produción e a dependencia alimentaria Máis alá das políticas comunitarias, ¿cres que poden desenvolverse alternativas para a xente nova a partir de medidas municipais, autonómicas ou estatais? Estase a facer? | xente nova | 0
Table 2:  Example sentences and labels for Subtask A. Note that "Idiomatic" is
assigned the label 0 in the dataset and "non-idiomatic" (including proper
nouns) are assigned the label 1.

##  3 System Overview

We focus on exploring different training techniques using BERT and RoBERTa,
given their superior performance on a wide range of NLP tasks. Each text
encoder and training method used in our model are detailed below.

###  3.1 Text Encoders

M-BERT Devlin et al. (2019): We use the M-BERTBASE model released by the
authors. It is pre-trained on the top 104 languages with the largest Wikipedia
using a masked language modeling (MLM) objective. This model is case
sensitive: it makes a difference between english and English.

XLM-R Conneau et al. (2019): XLM-RoBERTa (XLM-R) is a multilingual version of
RoBERTa. It is pre-trained on 2.5TB of filtered CommonCrawl data containing
100 languages. XLM-R has been shown to perform particularly well on low-
resource languages, such as Swahili and Urdu. We use the XLM-RLARGE model
released by the authors.

###  3.2 Training Procedures

Standard fine-tuning: This is the standard fine-tuning procedure where we
fine-tune BERT and RoBERTa on each training setting-specific data.

Adversarial training (ADV): Adversarial training has proven effective in
improving model generalization and robustness in computer vision Madry et al.
(2017); Goodfellow et al. (2014) and more recently in NLP Zhu et al. (2019);
Jiang et al. (2019); Cheng et al. (2019); Liu et al. (2020a); Pereira et al.
(2020). It works by augmenting the input with a small perturbation that
maximizes the adversarial loss:

$\min_{\theta}\mathbb{E}_{(x,y)\sim D}[\max_{\delta}l(f(x+\delta;\theta),y)]$
(1)

where the inner maximization can be solved by projected gradient descent Madry
et al. (2017). Recently, adversarial training has been successfully applied to
NLP as well Zhu et al. (2019); Jiang et al. (2019); Pereira et al. (2020). In
our experiments, we use SMART Jiang et al. (2019), which instead regularizes
the standard training objective using virtual adversarial training Miyato et
al. (2018):

$\displaystyle\min_{\theta}\mathbb{E}_{(x,y)\sim D}[l(f(x;\theta),y)+$ (2)
$\displaystyle\alpha\max_{\delta}l(f(x+\delta;\theta),f(x;\theta))]$

Effectively, the adversarial term encourages smoothness in the input
neighborhood, and $\alpha$ is a hyperparameter that controls the trade-off
between standard errors and adversarial errors.

##  4 Experiments

###  4.1 Implementation Details

Our model implementation is based on the MT-DNN framework Liu et al. (2019a,
2020b). We use BERT Devlin et al. (2019) and XLM-R Conneau et al. (2019) as
the text encoders. We used ADAM Kingma and Ba (2015) as our optimizer with a
learning rate in the range $\in\\{8\times 10^{-6},9\times 10^{-6},1\times
10^{-5}\\}$ and a batch size $\in\\{8,16,32\\}$. The maximum number of epochs
was set to 10. A linear learning rate decay schedule with warm-up over 0.1 was
used, unless stated otherwise. To avoid gradient exploding, we clipped the
gradient norm within 1. All the texts were tokenized using wordpieces and were
chopped to spans no longer than 512 tokens. During adversarial training, we
follow Jiang et al. (2019) and set the perturbation size to $1\times 10^{-5}$,
the step size to $1\times 10^{-3}$, and to $1\times 10^{-5}$ the variance for
initializing the perturbation. The number of projected gradient steps and the
$\alpha$ parameter (Equation 2) were both set to $1$.

We follow Devlin et al. (2019) and Liu et al. (2019b), and set the first token
as the [CLS] token and the <s> token, respectively, when encoding the input on
BERT and RoBERTa, respectively. We separate the input sentence and the target
expression with the special token [SEP] and </s> for BERT and RoBERTa,
respectively. e.g. [CLS] Ben Salmon is a committed night owl with an undying
devotion to discovering new music.,"He lives in the great state of Oregon,
where he hosts a killerradio show and obsesses about Kentucky basketball from
afar. [SEP] night owl [SEP].

For both settings (zero-shot and one-shot), we used the dev dataset released
by organizers to fine-tune the model’s hyperparameters.

###  4.2 Main Results

Submitted systems were evaluated in terms of F1-score. The systems were ranked
from highest F1-score score to lowest. We built several models that use
different text encoders and different training methods, as described in
Section 3. See Table 3 for the results.

First, we observe that models that use adversarial training obtained better
performance overall, without using any additional knowledge source, and
without using any additional dataset other than the target task datasets.
These results suggest that adversarial training leads to a more robust model
and helps generalize better on unseen data. For the zero-shot setting, the
model that uses XLM-R as the text encoder and adversarial training performed
better than M-BERT on the development set. Thus, we decided to submit this
model’s results on the test set. It obtained a test set F1-score of 0.7457,
and ranked 6th among all participating systems. On the other hand, on the one-
shot setting, M-BERT performed better than XLM-R on the development set.
Again, M-BERT with adversarial training performed better than vanilla fine-
tuning. This model obtained an F1-score of 0.6573 on the test set, and ranked
15th among all participating systems.

Method | zero-shot | one-shot
---|---|---
F1 | F1
Dev |
StandardXLM-RLARGE | 0.7076 | 0.7769
SMARTXLM-RLARGE | 0.7378 | 0.7958
StandardM-BERTBASE | 0.5540 | 0.8462
SMARTM-BERTBASE | 0.6200 | 0.8568
Test |
SMARTXLM-RLARGE | 0.7457 | -
SMARTM-BERTBASE | - | 0.6573
Table 3: Comparison of standard and adversarial training in zero-shot
evaluation on various natural language inference datasets, where the standard
BERTBASE model is fine-tuned on the MNLI training data.

##  5 Conclusion

We proposed a simple and efficient model for multilingual idiomaticity
detection. Our experiments demonstrated that it achieves competitive results
on both zero-shot and one-shot settings, without relying on any additional
resource other than the target task dataset. Although in this paper we focused
on the multilingual idiomaticity detection task, our model can be generalized
to solve other downstream tasks as well, and we will explore this direction as
future work.

## Acknowledgements

We thank the reviewers for their helpful feedback. This work has been
supported by the project KAKENHI ID: 21K17802.

## References

  * Cheng et al. (2019) Yong Cheng, Lu Jiang, and Wolfgang Macherey. 2019.  Robust neural machine translation with doubly adversarial inputs.
  * Conneau et al. (2019) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Unsupervised cross-lingual representation learning at scale.  _arXiv preprint arXiv:1911.02116_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.
  * Garcia et al. (2021) Marcos Garcia, Tiago Kramer Vieira, Carolina Scarton, Marco Idiart, and Aline Villavicencio. 2021.  Probing for idiomaticity in vector space models.  In _Proceedings of the 16th conference of the European Chapter of the Association for Computational Linguistics_. Association for Computational Linguistics (ACL).
  * Goodfellow et al. (2014) Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. 2014.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_.
  * Jiang et al. (2019) Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Tuo Zhao. 2019.  Smart: Robust and efficient fine-tuning for pre-trained natural language models through principled regularized optimization.  _arXiv preprint arXiv:1911.03437_.
  * Kingma and Ba (2015) Diederik P Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  _ICLR (Poster) 2015_.
  * Liu et al. (2020a) Xiaodong Liu, Hao Cheng, Pengcheng He, Weizhu Chen, Yu Wang, Hoifung Poon, and Jianfeng Gao. 2020a.  Adversarial training for large neural language models.  _arXiv preprint arXiv:2004.08994_.
  * Liu et al. (2019a) Xiaodong Liu, Pengcheng He, Weizhu Chen, and Jianfeng Gao. 2019a.  Multi-task deep neural networks for natural language understanding.  _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4487–4496.
  * Liu et al. (2020b) Xiaodong Liu, Yu Wang, Jianshu Ji, Hao Cheng, Xueyun Zhu, Emmanuel Awa, Pengcheng He, Weizhu Chen, Hoifung Poon, Guihong Cao, and Jianfeng Gao. 2020b.  The microsoft toolkit of multi-task deep neural networks for natural language understanding.  _arXiv preprint arXiv:2002.07972_.
  * Liu et al. (2019b) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019b.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Madry et al. (2017) Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. 2017.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_.
  * Miyato et al. (2018) Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. 2018.  Virtual adversarial training: a regularization method for supervised and semi-supervised learning.  _IEEE transactions on pattern analysis and machine intelligence_ , 41(8):1979–1993.
  * Pereira et al. (2020) Lis Pereira, Xiaodong Liu, Fei Cheng, Masayuki Asahara, and Ichiro Kobayashi. 2020\.  Adversarial training for commonsense inference.  _arXiv preprint arXiv:2005.08156_.
  * Tayyar Madabushi et al. (2022) Harish Tayyar Madabushi, Edward Gow-Smith, Marcos Garcia, Carolina Scarton, Marco Idiart, and Aline Villavicencio. 2022.  SemEval-2022 Task 2: Multilingual Idiomaticity Detection and Sentence Embedding.  In _Proceedings of the 16th International Workshop on Semantic Evaluation (SemEval-2022)_. Association for Computational Linguistics.
  * Tayyar Madabushi et al. (2021) Harish Tayyar Madabushi, Edward Gow-Smith, Carolina Scarton, and Aline Villavicencio. 2021.  AStitchInLanguageModels: Dataset and methods for the exploration of idiomaticity in pre-trained language models.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Zhu et al. (2019) Chen Zhu, Yu Cheng, Zhe Gan, Siqi Sun, Thomas Goldstein, and Jingjing Liu. 2019\.  Freelb: Enhanced adversarial training for language understanding.  _arXiv preprint arXiv:1909.11764_.


# Counting Guidance for High Fidelity Text-to-Image Synthesis

Wonjun Kang1,2, Kevin Galim1, Hyung Il Koo1,3

###### Abstract

Recently, the quality and performance of text-to-image generation
significantly advanced due to the impressive results of diffusion models.
However, text-to-image diffusion models still fail to generate high fidelity
content with respect to the input prompt. One problem where text-to-diffusion
models struggle is generating the exact number of objects specified in the
text prompt. E.g. given a prompt ”five apples and ten lemons on a table”,
diffusion-generated images usually contain the wrong number of objects. In
this paper, we propose a method to improve diffusion models to focus on
producing the correct object count given the input prompt. We adopt a counting
network that performs reference-less class-agnostic counting for any given
image. We calculate the gradients of the counting network and refine the
predicted noise for each step. To handle multiple types of objects in the
prompt, we use novel attention map guidance to obtain high-fidelity masks for
each object. Finally, we guide the denoising process by the calculated
gradients for each object. Through extensive experiments and evaluation, we
demonstrate that our proposed guidance method greatly improves the fidelity of
diffusion models to object count.

Stable Diffusion (Rombach et al. 2022)

(a)

(b)

(c)

(d)

Ours

(e) “six bananas”

(f) “five apples”

(g) “four donuts”

(h) “three apples and two donuts”

Figure 1: Our text-to-generation method generates the exact number of each
object for a given prompt. The first row shows the result of Stable Diffusion
(Rombach et al. 2022) while the second row shows our method’s result.

“ten apples on the table”

“fifty apples on the table”

(a) w/o guidance ($N=3$)

(b) w/ guidance ($N=10$) (d) w/ guidance ($N=46$) Figure 2: Effectiveness of
counting network guidance. Our method is also effective for large number.

(c) w/o guidance ($N=18$)

## Introduction

Text-to-image generation aims to generate high-fidelity images given a user-
specified text prompt. It has various applications like digital art, design,
and graphics and was traditionally performed using GANs since the early start
of deep learning (Goodfellow et al. 2014; Karras, Laine, and Aila 2019; Karras
et al. 2020, 2021; Zhang et al. 2017, 2018; Xu et al. 2018; Xia et al. 2021;
Patashnik et al. 2021). However, GANs suffer from unstable training and a lack
of diversity (mode collapse), making GANs only viable when generating images
in narrow domains such as faces, animals, or vehicles. Recently, diffusion
models (Ho, Jain, and Abbeel 2020; Song and Ermon 2019; Song et al. 2020), a
new family of generative models, show impressive, high fidelity and high
diversity results with stable training procedures, outperforming GANs and
shifting the research focus from GANs to diffusion (Nichol et al. 2021; Ramesh
et al. 2022; Saharia et al. 2022; Rombach et al. 2022). While many diffusion
models were proposed recently, the open source model Stable Diffusion (Rombach
et al. 2022), a latent diffusion model trained on large datasets, has become
the global standard of text-to-image generation models.

However, there are still unresolved issues with diffusion models and Stable
Diffusion. For example, Stable Diffusion usually shows bad performance for
compositional text-to-image synthesis (e.g., “an apple and a lemon on the
table”), and various efforts have been made to resolve this problem. Attend-
and-Excite (Chefer et al. 2023) proposes novel attention map guidance to
generate two different objects successfully. Several other studies suggest
layout-based methods for compositional text-to-image synthesis (Li et al.
2023; Lian et al. 2023; Phung, Ge, and Huang 2023). While there is a high
interest in compositional text-to-image synthesis, recent studies are only
focusing on synthesizing one object of each kind, leaving the problem of
synthesizing multiple instances of each object unsolved (e.g., “three apples
and five lemons on the table”).

In this work, we focus on improving diffusion models to generate the exact
number of instances per object, as specified in the input prompt. To alleviate
this problem, we propose counting guidance by using gradients of a counting
network. Specifically, we use RCC (Hobley and Prisacariu 2022) which performs
reference-less class-agnostic counting for any given image. While most
counting networks adopt a heatmap-based approach, RCC retrieves the object
count directly via regression and, thus, allows us to obtain its gradient for
classifier guidance (Dhariwal and Nichol 2021; Bansal et al. 2023).

Furthermore, to handle multiple object types, we investigate the semantic
information mixing problem of Stable Diffusion. For instance, the text prompt
“three apples and four donuts on the table.” usually causes diffusion models
to mix semantic information between apples and donuts leading to poor results
and making it hard to enforce the correct object count per object type. We
propose novel attention map guidance to separate semantic information between
nouns in the prompt by obtaining masks for each object from the corresponding
attention map. Fig. 1 compares Stable Diffusion with our method for single and
multiple object types. Our approach successfully generates the right amount of
each object, while Stable Diffusion fails in these scenarios. To the best of
our knowledge, our work is the first attempt to generate the exact number of
each object using a counting network for text-to-image synthesis. Our
contributions can be summarized as follows:

  * •

We present counting network guidance to improve pre-trained diffusion models
to generate the exact number of objects specified in the prompt. Our approach
can be applied to any diffusion model requiring no retraining or finetuning.

  * •

We propose novel attention map guidance to solve the semantic information
mixing problem and obtain high-fidelity masks for each object.

  * •

We demonstrate the effectiveness of our method by qualitative and quantitative
comparisons with previous methods.

## Related Work

### Diffusion Models

Diffusion models (Ho, Jain, and Abbeel 2020; Song and Ermon 2019; Song et al.
2020; Dhariwal and Nichol 2021; Rombach et al. 2022) are a new family of
generative models that show a significant advance in performance of image
synthesis and text-to-image generation. DDPM (Ho, Jain, and Abbeel 2020)
designed the Markov chain process by gradually adding noise and demonstrated
the potential of diffusion models for unconditional image generation.
Concurrently, VP-SDE (Song and Ermon 2019; Song et al. 2020) interpreted
diffusion models as Stochastic Differential Equations and provided broad
insight into diffusion models. One of the problems with DDPM is that it
depends on probabilistic sampling and requires about 1000 steps to obtain
high-fidelity results making the sampling process very slow and
computationally intensive. To solve this problem, DDIM (Song, Meng, and Ermon
2020) removed the probabilistic factor in DDPM and achieved comparable image
quality to DDPM with only 50 denoising steps.

Beyond unconditional image generation, recent papers on diffusion models also
started to focus on conditional image generation. ADM (Dhariwal and Nichol
2021) suggested classifier guidance by calculating the gradient of a
classifier to perform conditional image generation. This method though
requires a noise-aware classifier and per step gradient calculation. To avoid
this problem, (Ho and Salimans 2022) proposed classifier-free guidance, which
removes the need of an external classifier by computing each denoising step as
an extrapolation between one conditional and one unconditional step.
Furthermore, ControlNet (Zhang and Agrawala 2023) proposed a separate control
network attached to a pre-trained diffusion model to perform guidance with
additional input in feasible training time. Universal Guidance (Bansal et al.
2023) alleviates the problem of requiring a noise-aware classifier by instead
calculating the gradient of the predicted clean data point.

One issue of diffusion models when first proposed was the high inference cost
because of repeated inference in pixel-space. To address this problem, Stable
Diffusion (Rombach et al. 2022) proposed performing the diffusion process in a
low dimensional latent space instead of image space, greatly reducing the
computational cost. Despite Stable Diffusion’s powerful performance, there are
still some remaining problems. For example, Stable Diffusion usually fails to
generate multiple objects successfully (e.g., an apple and a lemon on the
table). Thus, the paper Attend-and-Excite (Chefer et al. 2023) suggested
attention map-based guidance to activate the attention of all objects in the
prompt but nevertheless only focuses on a single instance per object, leaving
the issue of reliable generation of multiple instances per objects. In this
paper, we explicitly address this issue by introducing counting network
guidance and attention map guidance to pre-trained diffusion models.

Concurrent with our work, (Paiss et al. 2023; Zhong et al. 2023) tries to
generate the exact number of objects using enhanced language models. (Paiss et
al. 2023) trains a counting-aware CLIP model (Radford et al. 2021) and uses it
to train the text-to-image diffusion model Imagen (Saharia et al. 2022). (Lee
et al. 2023; Fan et al. 2023) uses human feedback to fine-tune text-to-image
generation models by supervised learning and reinforcement learning. (Phung,
Ge, and Huang 2023; Lian et al. 2023) proposes layout-based text-to-image
generation, which requires additional layout input and leverages a large
language model (LLM) to generate proper layouts from given prompts. Unlike the
above works, our method does not require additional layout input, a LLM or
retraining.

### Object Counting

The goal of object counting is to count arbitrary objects in images. Object
counting can be divided into few-shot object counting, reference-less counting
and zero-shot object counting. For few-shot object counting (You et al. 2023;
Shi et al. 2022), a few example images of the object to count are provided as
input while for reference-less counting (Ranjan and Nguyen 2022; Hobley and
Prisacariu 2022), example images are not provided and the aim is to count the
number of all salient objects in the image. Zero-shot object counting, on the
other hand, (Xu et al. 2023; Jiang, Liu, and Chen 2023) aims to count
arbitrary objects of a user-provided class.

Object counting networks are usually either heatmap-based or regression-based
(You et al. 2023; Shi et al. 2022; Hobley and Prisacariu 2022). For our
approach, regression-based methods are more suitable for calculating the
gradient of the counting network compared to heatmap-based methods. In
particular, we adopt RCC (Hobley and Prisacariu 2022), a reference-less
regression-based counting model which builds on top of extracted features of a
pre-trained ViT (Dosovitskiy et al. 2020)

## Preliminaries

“three oranges and four eggs on the table”

w/o attention map guidance

(a)

(b)

(c)

(d)

(e)

w/ attention map guidance

(f) generated image

(g) attention map of “oranges”

(h) attention map of “eggs”

(i) mask of “oranges”

(j) mask of “eggs”

Figure 3: Effectiveness of attention map guidance. The first row shows the
results of Stable Diffusion without attention map guidance, and the second row
shows the results with attention map guidance.

Denoising Diffusion Probabilistic Models (DDPM) (Ho, Jain, and Abbeel 2020)
define a forward noising process and a reverse denoising process, each with
$T$ steps ($T=1000$ in the paper). The forward process $q(x_{t}|x_{t-1})$ is
defined as

$q(x_{t}|x_{t-1})=\mathcal{N}(x_{t};\sqrt{\alpha_{t}}x_{t-1},(1-\alpha_{t})I),$
(1)

where $\alpha_{t}$ and $x_{t}$ are schedule and data point at time step $t$.
This process can be seen as iteratively adding scaled Gaussian noise. Thanks
to the property of the Gaussian distribution, we can obtain $q(x_{t}|x_{0})$
directly as

$q(x_{t}|x_{0})=\mathcal{N}(x_{t};\sqrt{\bar{\alpha}_{t}}x_{0},(1-\bar{\alpha}_{t})I),$
(2)

and rewrite as

$x_{t}=\sqrt{\bar{\alpha}_{t}}x_{0}+\sqrt{1-\bar{\alpha}_{t}}\epsilon,$ (3)

where $\bar{\alpha}=\prod_{i=1}^{t}\alpha_{i}$ and
$\epsilon\sim\mathcal{N}(0,I)$. DDPM $\epsilon_{\theta}(x_{t},t)$ is trained
to estimate the noise which was added in the forward process $\epsilon$ at
each time step $t$. By iteratively estimating and removing the estimated
noise, the original image can be recovered. During inference, images are
generated by using random noise as starting point.

In practice however, deterministic DDIM (Song, Meng, and Ermon 2020) sampling
is commonly used since it requires significantly less sampling steps compared
to DDPM. DDIM sampling is performed as

$x_{t-1}=\sqrt{\bar{\alpha}_{t-1}}(\frac{x_{t}-\sqrt{1-\bar{\alpha}_{t}}\epsilon_{\theta}}{\sqrt{\bar{\alpha}_{t}}})+\sqrt{1-\bar{\alpha}_{t-1}}\epsilon_{\theta}.$
(4)

With DDIM sampling, the clean data point $\hat{x}_{0}$ can be obtained by

$\hat{x}_{0}=\frac{(x_{t}-\sqrt{1-\bar{\alpha}_{t}}\epsilon_{\theta}(x_{t},t))}{\sqrt{\bar{\alpha}_{t}}}.$
(5)

To add classifier guidance to DDIM (Dhariwal and Nichol 2021), the gradient of
a classifier is computed and used to retrieve the refined predicted noise
$\hat{\epsilon}$ by

$\hat{\epsilon}=\epsilon-s\sqrt{1-\bar{\alpha}_{t}}\nabla_{x_{t}}\log
p_{\phi}(y|x_{t})$ (6)

where $s$ is scale parameter and $p_{\phi}$ is a classifier. One issue of
classifier guidance is that the underlying classifier needs to be noise-aware
as it receives outputs from intermediate denoising steps, requiring expensive
noise-aware retraining. Universal Guidance (Bansal et al. 2023) addresses this
by feeding the predicted clean data point $\hat{x}_{0}$ instead of the noisy
$x_{t}$ to the classifier which can be expressed as

$\hat{\epsilon}=\epsilon-s\sqrt{1-\bar{\alpha}_{t}}\nabla_{x_{t}}\log
p_{\phi}(y|\hat{x}_{0}).$ (7)

## Method

Algorithm 1 Counting guidance for single object type

Input: time step $t$, denoising network $\epsilon_{\theta}(\cdot,\cdot)$,
decoder $Decoder(\cdot)$, counting network $Count(\cdot)$, number of object
$N$
Parameter: scale parameter $s_{count}$
Output: clean latent $z_{0}$

1: for $t=T,T-1,...,1$ do

2: $\epsilon\leftarrow\epsilon_{\theta}(z_{t},t)$

3:
$\hat{z}_{0}\leftarrow(z_{t}-\sqrt{1-\bar{\alpha}_{t}}\epsilon)/\sqrt{\bar{\alpha}_{t}}$

4: $\hat{x}_{0}\leftarrow Decoder(\hat{z}_{0})$

5: $L_{count}\leftarrow|(Count(\hat{x}_{0})-N)/N|^{2}$

6:
$\epsilon\leftarrow\epsilon+s_{count}\sqrt{1-\bar{\alpha}_{t}}\nabla_{z_{t}}L_{count}$

7: $z_{t-1}\leftarrow Sample(z_{t},\epsilon)$

8: end for

9: return $z_{0}$

Algorithm 2 Counting guidance for multiple object types

Input: time step $t$, denoising network $\epsilon_{\theta}$, decoder
$Decoder$, counting network $Count$, number of $i$th object $N_{i}$
Parameter: scale parameter $s_{max}$, $s_{attention}$, $s_{count,i}$
Output: clean latent $z_{0}$

1: for $t=T,T-1,...,1$ do

2: $\epsilon,M\leftarrow\epsilon_{\theta}(z_{t},t)$

3: $L_{min}\leftarrow\sum_{j,k}\min_{i}({M_{i,j,k}})$

4: $L_{max}\leftarrow\sum_{j,k}\max_{i}({M_{i,j,k}})$

5: $L_{attention}\leftarrow L_{min}-s_{max}L_{max}$

6:
$\epsilon\leftarrow\epsilon+s_{attention}\sqrt{1-\bar{\alpha}_{t}}\nabla_{z_{t}}L_{attention}$

7:
$\hat{z}_{0}\leftarrow(z_{t}-\sqrt{1-\bar{\alpha}_{t}}\epsilon)/\sqrt{\bar{\alpha}_{t}}$

8: $\hat{x}_{0}\leftarrow Decoder(\hat{z}_{0})$

9: for i do

10: $\hat{x}_{0,i}\leftarrow Mask(\hat{x}_{0},M_{i})$

11: $L_{count,i}\leftarrow|(Count(\hat{x}_{0,i})-N_{i})/N_{i}|^{2}$

12:
$\epsilon\leftarrow\epsilon+s_{count,i}\sqrt{1-\bar{\alpha}_{t}}\nabla_{z_{t}}L_{count,i}$

13: end for

14: $z_{t-1}\leftarrow Sample(z_{t},\epsilon)$

15: end for

16: return $z_{0}$

In this section, we first present how to control the number of a single object
type using counting network guidance and then expand it to multiple object
types. For multiple object types, we solve the semantic information mixing
problem of Stable Diffusion with attention map guidance and present masked
counting network guidance for successful multiple object type generation.

### Counting Guidance for a Single Object Type

To avoid retraining the counting network on noisy images, we perform counting
network guidance following Universal Guidance (Bansal et al. 2023). For a
given number of $N$ objects, we define the counting loss $L_{count}$ as

$L_{count}=|\frac{Count(\hat{x}_{0})-N}{N}|^{2},$ (8)

where $Count(\cdot)$ is the pre-trained counting network RCC (Hobley and
Prisacariu 2022) and $\hat{x}_{0}$ is the predicted clean image at each time
step. We update the predicted noise $\epsilon$ using the gradient of the
counting network as

$\epsilon\leftarrow\epsilon+s_{count}\sqrt{1-\bar{\alpha}_{t}}\nabla_{z_{t}}L_{count},$
(9)

where $s_{count}$ is an additional scale parameter to control the strength of
counting guidance.

Fig. 2a and Fig. 2b show the effectiveness of our proposed counting network
guidance method. For the prompt “ten apples on the table,” Stable Diffusion
with counting network guidance generates ten apples, while vanilla Stable
Diffusion generates only three apples. We find that Fig. 2a and Fig. 2b have
similar textures and backgrounds, indicating that counting guidance maintains
the original properties of Stable Diffusion while only influencing the object
count.

Counting guidance also proves itself effective when generating a large number
of objects. Due to a lack of images containing a large number of objects in
Stable Diffusion’s training dataset, it often fails to create plausible
results for such cases. Fig. 2c and Fig. 2d show the effectiveness of counting
guidance on large numbers. For the given text prompt “fifty apples on the
table,” Stable Diffusion with counting network guidance generates 46 apples,
while vanilla Stable Diffusion generates only 18 apples.

Although counting guidance helps to generate the given number of objects, it
sometimes fails to produce the exact number of objects. We think that this is
an issue of the accuracy of the counting network itself, so we adjust the
output number $N$ of the counting network by adding a fixed offset $N_{off}$:

$N\leftarrow N+N_{off},$ (10)

where the value of offset $N_{off}$ is usually 0, -1, or 1.

### Counting Guidance for Multiple Object Types

Stable Diffusion (Rombach et al. 2022)

(a)

(b)

(c)

(d)

(e)

(f)

Attend-and-Excite (Chefer et al. 2023)

(g)

(h)

(i)

(j)

(k)

(l)

Ours

(m) “five rabbits”

(n) “ten oranges”

(o) “four tomatoes”

(p) “twelve macarons”

(q) “three chicks”

(r) “seven eggs”

Figure 4: Qualitative comparison for single object type. The first row shows
the results of Stable Diffusion (Rombach et al. 2022), the second row shows
the results of Attend-and-Excite (Chefer et al. 2023) and the last row shows
the results of our method.

#### Semantic Information Mixing Problem

Handling multiple object types requires counting each type separately. We
could use a class-aware counting network, however, the predicted clean image
of early denoising steps is still too low quality for the counting network to
correctly identify each object instance. Therefore, we decide to use a class-
agnostic counting network instead. For each object type to count, we obtain a
mask using the underlying self attention maps of the UNet model and feed the
masked image of each object type to the counting network separately. It has
been shown in previous works (Hertz et al. 2022; Chefer et al. 2023) that the
attention map corresponding to each object has high activation at the object
region. Thus, we use the attention map of each object as its mask.

However, we require accurate object masks for counting guidance, but Stable
Diffusion often tends to produce attention maps that do not accurately
correspond to the correct location of each object. The first row of Fig. 3
demonstrates this semantic information mixing problem. For the prompt “three
oranges and four eggs on the table.”, we find that the attention map of
“oranges” and the attention map of “eggs” share a large part of pixels
resulting in the generation of orange-colored eggs instead of oranges and
eggs.

#### Attention Map Guidance

To solve the semantic information mixing problem, we first obtain each
object’s attention map following (Chefer et al. 2023). Similarly, we exclude
the $\langle sot\rangle$ token, re-weigh using Softmax, and then Gaussian-
smooth to receive the attention map $M_{i}$ for each object $i$. Finally, we
normalize each object’s attention map as

${\hat{M}_{i,j,k}}=\frac{{M_{i,j,k}}-\min_{j,k}({M_{i,j,k}})}{\max_{j,k}({M_{i,j,k}})-\min_{j,k}({M_{i,j,k}})},$
(11)

where $M_{i,j,k}$ is the attention value of coordinate $(j,k)$ of object $i$’s
attention map.

We then ensure that each pixel coordinate is only referred to by the attention
of a single object by calculating each coordinate’s minimum attention value
and summate them to $L_{min}$ where a low $L_{min}$ indicates that each
coordinate is only activated by a single object:

$L_{min}=\sum_{j,k}\min_{i}({\hat{M}_{i,j,k}}).$ (12)

Similar to $L_{min}$, we define $L_{max}$ to ensure that at least one object
activates each pixel as

$L_{max}=\sum_{j,k}\max_{i}({\hat{M}_{i,j,k}}).$ (13)

Finally, we calculate the total attention loss $L_{attention}$ as

$L_{attention}=L_{min}-s_{max}L_{max},$ (14)

where $s_{max}$ is a scale parameter. The predicted noise $\epsilon$ is then
updated as

$\epsilon\leftarrow\epsilon+s_{attention}\sqrt{1-\bar{\alpha}_{t}}\nabla_{z_{t}}L_{attention}.$
(15)

The second row of Fig. 3 shows the effectiveness of our attention map
guidance. We find that the attention map of “oranges” only focuses on oranges,
and the attention map of “eggs” only focuses on eggs, resulting in a correctly
synthesized output. Furthermore, we observe that high-fidelity object masks
are generated from the corresponding attention maps.

#### Masked Counting Guidance

For each object $i$, we binarize its attention map to receive the binary mask
$M^{b}_{i}$ as

$M^{b}_{i,j,k}=\begin{cases}1,&\text{if}\
i=\operatorname*{argmax}_{i}(M_{i,j,k})\\\ 0,&\text{otherwise}\end{cases}$
(16)

and then generate a masked clean image $\hat{x}_{0,i}$ using element-wise
multiplication:

$\hat{x}_{0,i}=\hat{x}_{0}\odot M^{b}_{i}.$ (17)

For the $i$-th object count of object $N_{i}$, each masked counting guidance
$L_{count,i}$ is defined as

$L_{count,i}=|\frac{Count(\hat{x}_{0,i})-N_{i}}{N_{i}}|^{2}.$ (18)

Finally, we update the noise $\epsilon$ as

$\epsilon\leftarrow\epsilon+\sum_{i}s_{count,i}\sqrt{1-\bar{\alpha}_{t}}\nabla_{z_{t}}L_{count,i}$
(19)

where $s_{count,i}$ is an additional scaling parameter per object.

## Experiments

We borrow the state-of-the-art text-to-image generation model Stable Diffusion
v1.4 for our experiments. We use DDIM sampling with 50 steps and set the scale
parameter for $L_{max}$ to $s_{max}=0.1$ by default. We create a modified
dataset based on the object classes in Attend-and-Excite (Chefer et al. 2023)
to evaluate and compare our approach with previous methods. Specifically, we
remove the color category and add more animals and objects to focus on
counting performance. We compare our method with Stable Diffusion (Rombach et
al. 2022) and Attend-and-Excite.

### Results for Single Object Type

“two apples and three donuts on the table”

(a)

(b)

(c)

“three lemons and one bread on the table”

(d)

(e)

(f)

“two onions and two tomatoes on the table”

(g) Stable Diffusion

(h) Attend-and-Excite

(i) Ours

Figure 5: Qualitative comparison for multiple object types. The first column
shows the results of Stable Diffusion, the second column shows the results of
Attend-and Excite, and the last column shows the results of our method.

Fig. 4 shows a qualitative comparison for the single object type scenario.
While Stable Diffusion and Attend-and-Excite fail to generate the same number
of objects as specified in the prompt, our method generates the correct
number. For the text prompt “four tomatoes on the table,” Stable Diffusion
generates only three tomatoes without counting guidance. With counting
guidance, the tomato at the bottom is successfully divided into two tomatoes,
while the rest of the image is consistent with the original result. The text
prompt “ten oranges on the table,” causes Stable Diffusion to only generate
four oranges compared to our solution that creates the correct amount of ten.
The big difference in count results in large gradients, making our result
severely differ from the original.

Our method also works well for more complex categories, such as animals.
Considering text prompt “three chicks on the road”, Stable Diffusion and
Attend-and-Excite synthesize only two chicks, unlike our method which
generates one additional chick while maintaining the other two chicks’
appearance. For the text prompt “five rabbits in the yard” Stable Diffusion
and Attend-and-Excite generate only four rabbits, while our method generates
one more rabbit but fails to maintain the other rabbits’ appearance. That is
because of the difference between the background and the rabbit colors. It is
hard to generate a white rabbit from a brown yard, so Stable Diffusion with
counting guidance changes the overall structure and recreates five rabbits.

### Results for Multiple Object Types

Fig. 5 shows a qualitative comparison for multiple object types. For the given
text prompt “three lemons and one bread on the table,” Stable Diffusion
successfully creates one bread but fails to generate three lemons, while
Attend-and-Excite fails in both cases. With masked counting guidance, our
method correctly synthesizes three lemons and one bread. The result shows that
the lemon at the bottom is divided into two lemons thanks to masked counting
guidance while maintaining the bread’s shape.

For the text prompt “two onions and two tomatoes on the table,” we find that
Stable Diffusion suffers from the semantic information mixing problem and
generates red onions instead of tomatoes. Due to our attention map guidance,
our method creates real tomatoes. As Attend-and-Excite is also based on
attention map optimization, it successfully generates real tomatoes but fails
to generate the exact number of onions.

## Limitations

As our results show, our method aids in generating the exact number of each
object, but we also found several limitations. First, it is often necessary to
tune the scale parameters of the counting network guidance for a specific text
prompt. Although fixed scale parameters can help to control the number of
objects to a certain degree, generating the exact number of each object may
require tuning the underlying scale parameters.

Second, we found that generating the exact number of more complex objects is
much more complicated than generating simple object shapes. The structure of
the result image is mostly determined at the early denoising steps, limiting
the dividing or merging of objects by counting guidance.

## Conclusions

In this paper, we propose counting guidance which is, to our knowledge, the
first attempt to guide Stable Diffusion with a counting network to generate
the correct number of objects during text-to-image generation. For a single
object type, we calculate the gradients of a counting network and refine the
estimated noise at every step. For multiple object types, we discuss the
semantic information mixing problem and propose attention map guidance to
alleviate it. Finally, we obtain masks of each object from the corresponding
attention map and calculate the counting network’s gradient of each masked
image separately. We demonstrate that our method effectively controls the
number of objects with a few limitations. For future work, we will aim to
remove the necessarity of scale parameter tuning and create one global
framework working for every prompt without additional tuning.

## References

  * Bansal et al. (2023) Bansal, A.; Chu, H.-M.; Schwarzschild, A.; Sengupta, S.; Goldblum, M.; Geiping, J.; and Goldstein, T. 2023.  Universal Guidance for Diffusion Models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 843–852.
  * Chefer et al. (2023) Chefer, H.; Alaluf, Y.; Vinker, Y.; Wolf, L.; and Cohen-Or, D. 2023.  Attend-and-excite: Attention-based semantic guidance for text-to-image diffusion models.  _arXiv preprint arXiv:2301.13826_.
  * Dhariwal and Nichol (2021) Dhariwal, P.; and Nichol, A. 2021.  Diffusion models beat gans on image synthesis.  _Advances in Neural Information Processing Systems_ , 34: 8780–8794.
  * Dosovitskiy et al. (2020) Dosovitskiy, A.; Beyer, L.; Kolesnikov, A.; Weissenborn, D.; Zhai, X.; Unterthiner, T.; Dehghani, M.; Minderer, M.; Heigold, G.; Gelly, S.; et al. 2020\.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_.
  * Fan et al. (2023) Fan, Y.; Watkins, O.; Du, Y.; Liu, H.; Ryu, M.; Boutilier, C.; Abbeel, P.; Ghavamzadeh, M.; Lee, K.; and Lee, K. 2023.  DPOK: Reinforcement Learning for Fine-tuning Text-to-Image Diffusion Models.  _arXiv preprint arXiv:2305.16381_.
  * Goodfellow et al. (2014) Goodfellow, I.; Pouget-Abadie, J.; Mirza, M.; Xu, B.; Warde-Farley, D.; Ozair, S.; Courville, A.; and Bengio, Y. 2014.  Generative adversarial nets.  _Advances in neural information processing systems_ , 27.
  * Hertz et al. (2022) Hertz, A.; Mokady, R.; Tenenbaum, J.; Aberman, K.; Pritch, Y.; and Cohen-Or, D. 2022\.  Prompt-to-prompt image editing with cross attention control.  _arXiv preprint arXiv:2208.01626_.
  * Ho, Jain, and Abbeel (2020) Ho, J.; Jain, A.; and Abbeel, P. 2020.  Denoising diffusion probabilistic models.  _Advances in Neural Information Processing Systems_ , 33: 6840–6851.
  * Ho and Salimans (2022) Ho, J.; and Salimans, T. 2022.  Classifier-free diffusion guidance.  _arXiv preprint arXiv:2207.12598_.
  * Hobley and Prisacariu (2022) Hobley, M.; and Prisacariu, V. 2022.  Learning to count anything: Reference-less class-agnostic counting with weak supervision.  _arXiv preprint arXiv:2205.10203_.
  * Jiang, Liu, and Chen (2023) Jiang, R.; Liu, L.; and Chen, C. 2023.  CLIP-Count: Towards Text-Guided Zero-Shot Object Counting.  _arXiv preprint arXiv:2305.07304_.
  * Karras et al. (2021) Karras, T.; Aittala, M.; Laine, S.; Härkönen, E.; Hellsten, J.; Lehtinen, J.; and Aila, T. 2021.  Alias-free generative adversarial networks.  _Advances in Neural Information Processing Systems_ , 34.
  * Karras, Laine, and Aila (2019) Karras, T.; Laine, S.; and Aila, T. 2019.  A style-based generator architecture for generative adversarial networks.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 4401–4410.
  * Karras et al. (2020) Karras, T.; Laine, S.; Aittala, M.; Hellsten, J.; Lehtinen, J.; and Aila, T. 2020\.  Analyzing and improving the image quality of stylegan.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 8110–8119.
  * Lee et al. (2023) Lee, K.; Liu, H.; Ryu, M.; Watkins, O.; Du, Y.; Boutilier, C.; Abbeel, P.; Ghavamzadeh, M.; and Gu, S. S. 2023.  Aligning text-to-image models using human feedback.  _arXiv preprint arXiv:2302.12192_.
  * Li et al. (2023) Li, Y.; Liu, H.; Wu, Q.; Mu, F.; Yang, J.; Gao, J.; Li, C.; and Lee, Y. J. 2023\.  GLIGEN: Open-Set Grounded Text-to-Image Generation.  _arXiv preprint arXiv:2301.07093_.
  * Lian et al. (2023) Lian, L.; Li, B.; Yala, A.; and Darrell, T. 2023.  LLM-grounded Diffusion: Enhancing Prompt Understanding of Text-to-Image Diffusion Models with Large Language Models.  _arXiv preprint arXiv:2305.13655_.
  * Nichol et al. (2021) Nichol, A.; Dhariwal, P.; Ramesh, A.; Shyam, P.; Mishkin, P.; McGrew, B.; Sutskever, I.; and Chen, M. 2021.  Glide: Towards photorealistic image generation and editing with text-guided diffusion models.  _arXiv preprint arXiv:2112.10741_.
  * Paiss et al. (2023) Paiss, R.; Ephrat, A.; Tov, O.; Zada, S.; Mosseri, I.; Irani, M.; and Dekel, T. 2023\.  Teaching clip to count to ten.  _arXiv preprint arXiv:2302.12066_.
  * Patashnik et al. (2021) Patashnik, O.; Wu, Z.; Shechtman, E.; Cohen-Or, D.; and Lischinski, D. 2021.  Styleclip: Text-driven manipulation of stylegan imagery.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2085–2094.
  * Phung, Ge, and Huang (2023) Phung, Q.; Ge, S.; and Huang, J.-B. 2023.  Grounded Text-to-Image Synthesis with Attention Refocusing.  _arXiv preprint arXiv:2306.05427_.
  * Radford et al. (2021) Radford, A.; Kim, J. W.; Hallacy, C.; Ramesh, A.; Goh, G.; Agarwal, S.; Sastry, G.; Askell, A.; Mishkin, P.; Clark, J.; et al. 2021.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , 8748–8763. PMLR.
  * Ramesh et al. (2022) Ramesh, A.; Dhariwal, P.; Nichol, A.; Chu, C.; and Chen, M. 2022.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_.
  * Ranjan and Nguyen (2022) Ranjan, V.; and Nguyen, M. H. 2022.  Exemplar free class agnostic counting.  In _Proceedings of the Asian Conference on Computer Vision_ , 3121–3137.
  * Rombach et al. (2022) Rombach, R.; Blattmann, A.; Lorenz, D.; Esser, P.; and Ommer, B. 2022.  High-resolution image synthesis with latent diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 10684–10695.
  * Saharia et al. (2022) Saharia, C.; Chan, W.; Saxena, S.; Li, L.; Whang, J.; Denton, E. L.; Ghasemipour, K.; Gontijo Lopes, R.; Karagol Ayan, B.; Salimans, T.; et al. 2022\.  Photorealistic text-to-image diffusion models with deep language understanding.  _Advances in Neural Information Processing Systems_ , 35: 36479–36494.
  * Shi et al. (2022) Shi, M.; Lu, H.; Feng, C.; Liu, C.; and Cao, Z. 2022.  Represent, compare, and learn: A similarity-aware framework for class-agnostic counting.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 9529–9538.
  * Song, Meng, and Ermon (2020) Song, J.; Meng, C.; and Ermon, S. 2020.  Denoising diffusion implicit models.  _arXiv preprint arXiv:2010.02502_.
  * Song and Ermon (2019) Song, Y.; and Ermon, S. 2019.  Generative modeling by estimating gradients of the data distribution.  _Advances in neural information processing systems_ , 32.
  * Song et al. (2020) Song, Y.; Sohl-Dickstein, J.; Kingma, D. P.; Kumar, A.; Ermon, S.; and Poole, B. 2020.  Score-based generative modeling through stochastic differential equations.  _arXiv preprint arXiv:2011.13456_.
  * Xia et al. (2021) Xia, W.; Yang, Y.; Xue, J.-H.; and Wu, B. 2021.  Tedigan: Text-guided diverse face image generation and manipulation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2256–2265.
  * Xu et al. (2023) Xu, J.; Le, H.; Nguyen, V.; Ranjan, V.; and Samaras, D. 2023.  Zero-Shot Object Counting.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 15548–15557.
  * Xu et al. (2018) Xu, T.; Zhang, P.; Huang, Q.; Zhang, H.; Gan, Z.; Huang, X.; and He, X. 2018.  Attngan: Fine-grained text to image generation with attentional generative adversarial networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 1316–1324.
  * You et al. (2023) You, Z.; Yang, K.; Luo, W.; Lu, X.; Cui, L.; and Le, X. 2023.  Few-shot object counting with similarity-aware feature enhancement.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 6315–6324.
  * Zhang et al. (2017) Zhang, H.; Xu, T.; Li, H.; Zhang, S.; Wang, X.; Huang, X.; and Metaxas, D. N. 2017\.  Stackgan: Text to photo-realistic image synthesis with stacked generative adversarial networks.  In _Proceedings of the IEEE international conference on computer vision_ , 5907–5915.
  * Zhang et al. (2018) Zhang, H.; Xu, T.; Li, H.; Zhang, S.; Wang, X.; Huang, X.; and Metaxas, D. N. 2018\.  Stackgan++: Realistic image synthesis with stacked generative adversarial networks.  _IEEE transactions on pattern analysis and machine intelligence_ , 41(8): 1947–1962.
  * Zhang and Agrawala (2023) Zhang, L.; and Agrawala, M. 2023.  Adding conditional control to text-to-image diffusion models.  _arXiv preprint arXiv:2302.05543_.
  * Zhong et al. (2023) Zhong, S.; Huang, Z.; Wen, W.; Qin, J.; and Lin, L. 2023.  Sur-adapter: Enhancing text-to-image pre-trained diffusion models with large language models.  _arXiv preprint arXiv:2305.05189_.


# Lifelong Learning in Multi-Armed Bandits

Matthieu Jedor
Centre Borelli, ENS Paris-Saclay & Cdiscount
<EMAIL_ADDRESS>
&Jonathan Louëdec
Cdiscount
<EMAIL_ADDRESS>
&Vianney Perchet
CREST, ENSAE Paris & Criteo AI Lab
<EMAIL_ADDRESS>

###### Abstract

Continuously learning and leveraging the knowledge accumulated from prior
tasks in order to improve future performance is a long standing machine
learning problem. In this paper, we study the problem in the multi-armed
bandit framework with the objective to minimize the total regret incurred over
a series of tasks. While most bandit algorithms are designed to have a low
worst-case regret, we examine here the average regret over bandit instances
drawn from some prior distribution which may change over time. We specifically
focus on confidence interval tuning of UCB algorithms. We propose a bandit
over bandit approach with greedy algorithms and we perform extensive
experimental evaluations in both stationary and non-stationary environments.
We further apply our solution to the mortal bandit problem, showing empirical
improvement over previous work.

##  1 Introduction

The multi-armed bandit (MAB) is a simple instance of online learning problem
with partial feedback (see [13]; [34]; [44], and references therein). In the
stochastic bandit framework, a learning agent sequentially pulls arms and
obtains noisy rewards. The goal of the agent is to maximize her expected
cumulative reward, or equivalently, to minimize her regret, which is the
difference between the cumulative reward of an oracle (that knows the mean
rewards of arms) and the one of the agent. There is thus a clear trade-off,
called “exploration vs exploitation”, that arises between gathering
information on uncertain arms by pulling them (exploration) and leveraging the
information obtained so far by greedily pulling the arm with the highest
estimated reward (exploitation). MAB has received a large attention recently
due to its wide applications range and the theoretical guarantees associated
with learning algorithms (see also [9], and references therein for a survey on
practical applications of MAB).

Most of the work in the stochastic bandit literature focuses on developing
algorithms with optimal regret, either asymptotically in the instance-
dependent sense or in the worst-case, on some problem class (typically on
bounded or subgaussian rewards). While the theory guarantees that these
algorithms will have a sublinear regret in all instances within the problem
class, they will be overly conservative for the majority of these instances,
leading to a large regret. Additionally, on these “easier” instances,
sophisticated algorithms are outperformed by simpler ones [48, 31], which is
an obstacle to their implementation in practice. In this paper, we consider
that the learner successively interacts with a task sampled from a problem
class with some prior distribution, which may or may not be stationary over
time. Within each task, there is a learning problem which is a MAB problem
with a fixed time horizon. The learning agent does not know the model
parameters of each bandit problem, nor does she know the prior distribution
within the problem class. Yet, it is critical for the learner be to able to
“track” this probability distribution to build lifelong learning agent and
thus achieve the best possible performance. In a stationary environment, the
learner experiences the same bandit problem over and over again, and an
efficient algorithm, in order to improve the performance when it faces the
same problem again, should leverage the information acquired from previous
tasks. Conversely in a non-stationary environment, the distribution within the
problem class may change over time and the previously learned solution may
fail to keep its good performance under the new distribution. An efficient
algorithm must thus continuously learn to improve itself. The goal of the
learning agent is then to minimize the lifelong regret, that is the cumulative
regret across all tasks. This approach can be regarded as a special case of
meta-learning [42, 46] or lifelong learning [45, 16, 43].

#### Our results

We focus on a tractable instance of this problem that is the tuning of the
confidence interval width of UCB-like policies. We first evaluate the impact
of the choice of algorithm on empirical performance over several problem
classes with different prior and different number of arms. On a side note, we
prove a bound on the Bayesian regret of a tuned UCB algorithm showing that we
do not lose all theoretical guarantees. We then concentrate on learning in a
stationary environment. We first investigate the influence of various
initializations on performance. Next, we discuss about the main part of this
paper that is learning the optimal algorithm. For this purpose, we consider a
bandit over bandit approach, that is using a bandit algorithm to choose the
optimal parameter. We show empirically that the Greedy algorithm as the meta-
algorithm performs extremely well. We next concentrate on learning in a non-
stationary environment, precisely we look at both an abruptly changing and a
slowly changing environment. To this effect, we adapt the Greedy algorithm
using methods from non-stationary bandits. Finally, we apply our method to a
more realistic setting, the mortal bandit problem. By decomposing the time
horizon into episodes according to the expected lifetime of arms, we show
great empirical improvement compared to previous work.

#### Related Work

Bayesian bandits [23, 24, 7] have been studied extensively with the goal of
developing optimal algorithms in the Bayesian sense. Lower bounds on the
Bayesian regret have also been derived [32, 28]. Unfortunately, computing the
Bayesian optimal algorithm is generally intractable [34].

The closest to our work is that of [35] who considered a framework which
closely resembles to ours except they studied the stochastic setting and
further assumed a finite set of models; whereas we consider the Bayesian
setting and do not make any assumption on the number of changes in the prior
distribution. [20] extended the previous work in the contextual framework.

Also related to our work, [37] tuned existing algorithms and also learned
index algorithms of historical features. [26] proposed a best-arm
identification algorithm for tuning the confidence interval of the UCB
algorithm and the posterior distribution of the Thompson Sampling algorithm.
[12] focused on “differentiable” algorithms and optimized them by gradient
ascent. In comparison, the setting of these works are offline while we are
more interested in the lifelong regret incurred in potentially non-stationary
environments.

Several works also use bandit algorithms as meta-algorithm. [36] introduced a
bandit-based approach to hyperparameter optimization using Sequential Halving,
a pure-exploration bandit algorithm, as a subroutine. The celebrated UCT
algorithm [30] makes use of the UCB algorithm applies on trees. In the non-
stationary framework, a few methods involve MAB in a hierarchical way: [25]
considered a meta-bandit to decide whether to accept the change detection or
not; [17] used the EXP3 algorithm to decide the window size of the SW-UCB
algorithm; and [49, 50] adopted a hierarchical bandit algorithm where a master
bandit manages some slave bandits.

The model can also be viewed as a special case of mortal bandits [14, 8, 47]
in which arms show up by batch where the time of death is the same for each
arm in a given batch.

##  2 Setting

In the stochastic MAB model, an agent interacts sequentially with a set of $K$
unknown distributions $\mathcal{V}_{1},\dots,\mathcal{V}_{K}$, called arms. At
time $t$, the agent chooses an arm $A_{t}$ which yields a reward $X_{t}$ drawn
from the associated probability distribution $\mathcal{V}_{A_{t}}$. The
objective is to design a sequential algorithm maximizing the expected
cumulative reward up to some time horizon $T$. Let $\mu_{1},\dots,\mu_{K}$
denote the mean rewards of arms, and
$\mu^{\star}\coloneqq\max_{k\in[K]}\mu_{k}$. The goal is equivalent to
minimizing the regret, defined as the difference between the expected reward
accumulated by an oracle strategy always playing the best arm at each round,
and the one accumulated by an algorithm $\mathcal{A}$,

$R(T,\mathcal{A})=\mathbb{E}\left[\sum_{t=1}^{T}\left(\mu^{\star}-\mu_{A_{t}}\right)\right]$

where the expectation is taken with respect to the randomness in the sequence
of successive rewards from each arm and the possible randomization of the
algorithm. Furthermore, we assume the following Bayesian, parametric bandit
setting: a random vector
$\boldsymbol{\theta}=\left(\theta_{1},\dots,\theta_{K}\right)$ is drawn from a
prior distribution $\Pi$, and the distribution of arm $k$ depends on the
parameter $\theta_{k}$. This leads to the notion of Bayesian regret which
depends on the prior distribution $\Pi$,

$\mathrm{BR}_{\Pi}(T,\mathcal{A})=\int
R(T,\mathcal{A})d\Pi(\boldsymbol{\theta})\,.$

We consider a lifelong learning setting where at each episode $j$ the learner
interacts with a task
$\mathcal{V}_{\theta_{1}^{j}},\dots,\mathcal{V}_{\theta_{K}^{j}}$, where each
$\theta_{k}^{j}$ is drawn i.i.d. from a prior distribution $\Pi_{j}$. The
objective is to find a series of algorithms minimizing the lifelong (Bayesian)
regret over $J$ episodes,

$\mathrm{LR}_{\boldsymbol{\Pi}}(T,\mathfrak{A})=\sum_{j=1}^{J}\mathrm{BR}_{\Pi_{j}}(T,\mathcal{A}_{j})$

where $\mathfrak{A}=\left(\mathcal{A}_{1},\dots,\mathcal{A}_{J}\right)$ and
$\boldsymbol{\Pi}=\left(\Pi_{1},\dots,\Pi_{J}\right)$ denote respectively the
algorithms and the prior distributions for each episode. We further assume
that the horizon for each task $T$ and the number of episodes $J$ are known.
An unknown number of episodes can be handled as usual [18]; while the
knowledge of the time horizon is mostly for convenience in the choice of the
sub-algorithm and similar results can be achieved with an anytime algorithm.

In order to minimize the lifelong regret, our method consists in designing a
meta-algorithm which, at each episode $j$, selects an algorithm
$\mathcal{A}_{j}$ from a class of algorithms, which can be finite or infinite,
that aims at minimizing the Bayesian regret with respect to the prior
distribution $\Pi_{j}$.

We especially focus on a tractable class of algorithms, the UCB algorithm [3]
with a parameter $\gamma$ controlling the width of the confidence interval. We
emphasis that similar results can be obtained with any UCB-like algorithms.
Formally, the UCB($\gamma$) index of arm $k\in[K]$ in round $t$ is

$U_{t}(k)=\widehat{\mu}_{k}(t-1)+\gamma\sqrt{\frac{2\log\left(1/\delta\right)}{N_{k}(t-1)}}$

where $\widehat{\mu}_{k}(t)$ is the average reward of arm $k$ in the first $t$
rounds, $N_{k}(t)$ is the number of times that arm $k$ has been pulled in the
first $t$ rounds and $\delta=1/T$ is the probability that the confidence
interval fails (in subsequent sections, we will choose $\delta=1/T$). Note
that the case $\gamma=1$ corresponds to the theoretical value that attains the
optimal instance-dependent regret for Gaussian rewards, while $\gamma=0$
corresponds to the Greedy algorithm. Hence for this class of algorithms, the
meta-algorithm faces a new trade-off between being conservative and being
aggressive on a class of bandit instances. Thereby, the objective that is to
minimize the lifelong regret is equivalent to finding the optimal values of
$\gamma\in[0,1]$ that minimizes the Bayesian regret in each episode.

Theoretically, any worst-case optimal algorithm will also be optimal, up to
constant factors, in the Bayesian setting [34]; and thus optimal in the
lifelong setting. Yet, we will see that we can empirically improve these
algorithms. We end this section with an analysis of this tuned UCB. More
generally, [41] noticed that the Bayesian regret of any UCB-like algorithm
satisfies

$\mathrm{BR}_{\Pi}(T,\textsc{UCB})\leq\mathbb{E}\left[\sum_{t=1}^{T}\left(\mu^{\star}-U_{t}(A^{\star})\right)+\sum_{t=1}^{T}\left(U_{t}(A_{t})-\mu_{A_{t}}\right)\right]$
(1)

where $A^{\star}$ denotes the optimal arm, which is a random variable.
Specifically for the UCB($\gamma$) algorithm we state the following theorem.

######  Theorem 1.

For 1-subgaussian distributions with mean in $[0,1]$, UCB($\gamma$) with
$\gamma>0$ satisfies

$\mathrm{BR}_{\Pi}(T,\textsc{UCB}(\gamma))\leq
4KT^{2}\delta^{4\gamma^{2}}+2\gamma\sqrt{2KT\log(1/\delta)}\,.$

As an example, for $\gamma=1$ and $\delta=1/T$, we get the known bound
$\mathcal{O}\left(\sqrt{KT\log{}T}\right)$.

###### Proof.

Let $E$ be the event that for all $t=1,\ldots,T$ and $k=1,\ldots,K$,

$\left|\widehat{\mu}_{k}(t-1)-\mu_{k}\right|<\gamma\sqrt{\frac{2\log(1/\delta)}{N_{k}(t-1)}}\,.$

Using the subgaussian assumption and a union bound, we get that
$\mathbb{P}\left(E^{c}\right)\leq 2KT\delta^{4\gamma^{2}}$. On the event
$E^{c}$, the terms inside the expectation of Equation (1) are bounded by $2T$,
while on the event $E$, the first sum is bounded by 0 and for the second term,
standard computations yield

$\sum_{t=1}^{T}\left(U_{t}(A_{t})-\mu_{A_{t}}\right)\mathbf{1}\\{E\\}\leq
2\gamma\sqrt{2KT\log(1/\delta)}\,.$

Putting together the pieces completes the proof. ∎

##  3 Choice of the class of algorithms

We begin by showing that the choice of the class of algorithms in which we
seek to find the one that maximize the average cumulative reward over bandit
instances, is of the utmost importance in order to have the best possible
empirical performance, and the most favorable algorithm depends on a number of
factors. In Figure 1, we evaluate the Bayesian regret of several UCB-like
algorithms as a function of their parameter $\gamma$ in different setups. In
all experiments, the distribution of each arm is a Bernoulli distribution
where the mean reward is drawn i.i.d. from a uniform distribution over
$[0,1]$. The horizon is fixed at $T=1000$ and we vary the number of arms $K$.
Results are averaged over $5000$ iterations. See also Appendix A.1 for
additional experiments with different distributions and priors.

(a) $K=5$

(b) $K=63$

(c) $K=250$

Figure 1: Bayesian regret of various algorithms as a function of $\gamma$ for
diverse numbers of arms $K$.

In Figure 1(a), we compare, for a small number of arms $K$, different UCB-like
algorithms: the original UCB algorithm [3], MOSS [2], which is known to be
worst-case optimal contrary to UCB, and AdaUCB [33] which is simultaneously
worst-case optimal, asymptotically optimal, and never worse than UCB in the
worst case. Interestingly, the later statement is also verified on the
Bayesian regret for all values of $\gamma$. The same can also be said almost
everywhere for MOSS over UCB. For large values of $\gamma$, AdaUCB outperforms
MOSS while for small values, MOSS only improves slightly over AdaUCB. As a
result, if one is purely interested in great empirical performance, a default
choice would be AdaUCB for any value of $\gamma$. However in the lifelong
setting, we want to optimize the parameter $\gamma$ and it is not clear which
choice of algorithm will perform better through all the episodes; AdaUCB may
be better but this also makes it harder for the meta-algorithm to find the
optimal value of $\gamma$, meaning a potentially larger lifelong regret
compared to UCB for example. Additionally, the best Bayesian regret of the
optimally tuned version of each algorithm is roughly the same for all three.
Hence our choice of the UCB algorithm, which is simple enough for
illustration, yet may also be suitable for practical applications. We finally
note that for all algorithms, the gain of their tuned version over the default
choice ($\gamma=1$) is substantial even though MOSS and AdaUCB are worst-case
optimal up to constant factors, supporting our choice to optimize algorithms
for practical purpose.

In Figure 1(b) and 1(c), we compare the UCB algorithm with sub-sampled
versions of itself, denoted SubUCB, in the case of an intermediate and a large
number of arms $K$. Formally, SubUCB($m$) selects randomly $m$ arms and
performs UCB on these arms. For $K=63$, we see that the Greedy algorithm,
symbolized by UCB with $\gamma=0$, performs better than any tuned UCB and also
better than SubUCB. For $K=250$, SubUCB performs always better than UCB. It is
interesting to notice that as $m$ grows larger, up to a certain point, SubUCB
has a better optimal Bayesian regret, becomes more sensitive to the parameter
$\gamma$ and a sub-sampled version of the Greedy algorithm turns into the best
performing algorithm. We mention that these behaviors, i.e. the good empirical
performance of the Greedy algorithm and the superiority of a sub-sampled
version of UCB in the case of a great number of arms, have been pointed out by
[6]. We showed that they also hold true empirically after tuning of the
confidence interval width.

##  4 Learning in a stationary environment

In this section, we consider the learning of the optimal algorithm in a fixed
environment, i.e. when the prior distribution is the same in all episodes. In
this case, the objective is equivalent to finding the algorithm that minimizes
the Bayesian regret for that specific prior distribution.

###  4.1 Influence of the initialization

We start with a study of the effect of the initialization choice on empirical
performance. By default, most bandit algorithms initialize arms by pulling
them at least one time. Knowing that we solve again and again similar bandit
problems, we may want to find a more clever initialization. For example,
consider a challenging bandit problem with a large number of arms with respect
to the time horizon and assume we have found a reasonably good arm; exploiting
this arm may then be more rewarding that exploring new arms in the hope of
finding a better one. This becomes especially critical the more greedy we get.
In this section, we fix the value of the hyperparameter $\gamma$ and we
evaluate three different initializations. In all cases, we set the empirical
means of arms to a specific value and their upper confidence bounds are built
as if they have been played once. In the first case we set this value at 0
(Init 1), in the second (Init 2) and third (Init 3) cases, it is fixed at the
mean and median, respectively, of previous empirical means. We denote by “Init
0” the default initialization.

We analyze here a particular problem class and we refer the reader to Appendix
A.2 for a more complete overview on the impact of the different
initializations for different prior distributions and number of arms. In this
experiment, each episode consists of a Gaussian bandit problem with $K=5$
arms, a time horizon $T=,000$ and the mean rewards of arms are drawn i.i.d.
from a uniform distribution over $[0,1]$. We fix $\gamma=0.2$ and we repeat
this tuned UCB for $J=100$ episodes with the different initializations
previously mentioned. On Figure 2(a), we report the lifelong regret averaged
over 100 iterations.

In this experiment, all three initializations improve over the default choice;
it turns out that initializing arms with the median of previous empirical
means performs better than the mean of previous arms which in turn performs
better than an initialization at 0. However, this is not always the case and
it heavily depends on the number of arms $K$ and on the prior distribution.
Fortunately, this choice is insignificant on instances with a small number of
arms, which we study in this paper, therefore in what follows we assume that
UCB uses the default initialization in each episode.

(a) Comparison of various initializations

(b) Comparison of various meta-algorithms

Figure 2: Lifelong regret of various meta-algorithms in stationary
environments. Shaded areas show standard errors.

###  4.2 Bandit algorithms as meta-algorithm

Now that the initialization rule is set, we can focus on the meta-algorithm,
i.e. the algorithm that is responsible for picking the parameter $\gamma$ of
UCB for each episode, and ultimately, is the keystone in the minimization of
the lifelong regret. We consider bandit algorithms for the choice of the meta-
algorithm, since they are efficient online optimization algorithms. This may
seem like a vicious circle as we are talking about optimization of bandits
algorithms and we want to avoid having to optimize the optimizer. Fortunately,
the two algorithms, the meta-algorithm and the sub-algorithm, face a different
problem. Indeed, the sub-algorithm aims at maximizing the average reward over
bandit instances while the meta-algorithm aims at maximizing a function, which
is the expected cumulative reward of the sub-algorithm with respect to its
parameter $\gamma$. The dilemma encountered by the meta-algorithm is actually
a continuous-armed bandit problem [29, 4] where the set of arms lies in some
bounded interval, in our case the different $\gamma\in[0,1]$. [29] proposed a
simple, yet nearly optimal, algorithm which consists in discretizing the
$[0,1]$ interval into a finite set of $n$ equally spaced points and running a
standard bandit algorithm over those points. Unfortunately, their theoretical
result holds only when the function to be optimize satisfies some Hölder
conditions which may not verified for the Bayesian regret of UCB($\gamma$).
Still, that does not refrain us from using this strategy. The chosen number of
arms $n$ is critical in practice; set too low we may be far from the optimal
solution and set too high we may end up exploring all the time. [4], with a
similar algorithm, claimed a value $n=(J/\log J)^{1/3}$ is optimal without
knowing the exact Hölder condition. We thus choose this specific
discretization in our simulations. It has also been noted by [6] that the
Greedy algorithm, known to have a linear regret, ran with a sufficiently large
number of arms may benefit from “free” exploration. This change point in its
behavior happens around $\sqrt{J}$; we also evaluate Greedy with a
discretization which contains that many points.

We again study a particular bandit instance; see Appendix A.3 for the same
experiment made with different choices of prior distribution. In this
experiment, each episode consists of a Bernoulli bandit problem with $K=5$
arms, a time horizon $T=1000$ and the mean rewards are drawn i.i.d. from a
uniform distribution over $[0,1]$. We set the number of episodes $J=10000$ and
we compare different meta-algorithms, namely Thompson Sampling (TS) with a
uniform prior [1], AdaUCB [33] and the Greedy algorithm with the two discussed
discretizations, denoted Greedy(100) for the discretization with 100 points.
We also report an oracle meta-algorithm, which knows the optimal $\gamma$.
Results are averaged over 100 iterations and are displayed on Figure 2(b).

We see that TS has a “linear” regret indicating that it fails to learn a good
parameter $\gamma$ within that time frame. Whereas the regret of AdaUCB is
sublinear and the algorithm is thus learning; however it is outperformed for a
relatively long period of time by a naive Greedy, which is stuck to a
suboptimal, yet good arm. The most interesting part is that Greedy(100)
performs extremely well; its regret is remarkably close to the one of Oracle
and is even sublinear. This supports the notion of free exploration for a
large enough number of arms of the Greedy algorithm.

##  5 Leaning in a non-stationary environment

We now focus our attention to learning in a non-stationary environment, i.e.
in which the prior distribution is not the same for all episodes. We will
consider two scenarios: one where the environment changes abruptly and another
where it slowly changes over time. Regrettably, adaptively tracking the prior
distribution is intractable without making strong distributional assumptions
(and potentially at the cost of forced exploration). Nonetheless, that does
not mean that trying to improve over a naive meta-algorithm is hopeless.
Taking inspiration from the stochastic non-stationary bandit literature [22],
we adapt the index of Greedy to take into account a changing environment.

The following two adjustments are based on the idea of “forgetting” rewards
obtained long ago. The first one is based on discounting. Formally, let
$\omega\in(0,1)$ be the discount factor and define the discounted DGreedy
index

$\widehat{\mu}_{k}^{\omega}(t)=\frac{\sum_{s=1}^{t}\omega^{t-s}X_{k}\mathbf{1}\\{A_{s}=k\\}}{\sum_{s=1}^{t}\omega^{t-s}\mathbf{1}\\{A_{s}=k\\}}\,.$

The idea is to reduce the weight of rewards collected a long time ago, making
the index more sensitive to recent rewards. A similar approach, somewhat more
sharp, called sliding-window, simply discards rewards older than a parameter
$\tau\in\mathbb{N}^{\star}$. Formally, the SWGreedy index is defined as

$\widehat{\mu}_{k}^{\tau}(t)=\frac{\sum_{s=t-\tau+1}^{t}X_{k}\mathbf{1}\\{A_{s}=k\\}}{\sum_{s=t-\tau+1}^{t}\mathbf{1}\\{A_{s}=k\\}}\,.$

Both these indexes are similar to those of the Discounted UCB and Sliding-
Window UCB [22], the difference being that the bonus terms are removed.
Unfortunately, there is no choice of $\omega$ and $\tau$ which guarantees
strong performance, and they must be tuned empirically for the specific
environment. Additionally, because both of this algorithms do not reflect on
the whole horizon, the optimal discretization for the Greedy meta-algorithm is
also more challenging to determinate. Consequently, in the following, we set
the number of points in the discretization at a lesser value.

In the following experiments, we run the Greedy meta-algorithm with the
different indexes111We choose $\omega=0.9975$ and $\tau=1,000$ on both
scenarios; these parameters have been roughly tuned. on a discretization
consisting of 21 equally-spaced points. In both scenarios, each episode is a
Bernoulli bandit problem with $K=10$ arms, the time horizon $T=1000$ and the
number of episodes is set at $J=10000$. In the first scenario, we consider an
abruptly changing environment, the prior distribution over the mean rewards of
arms is a Beta(1, 3) distribution for $j\leq J/3$ and $j\geq 2J/3$ and a
Beta(3, 1) distribution in between. While in the second scenario, we consider
a slowly changing environment, the prior distribution at episode $j$ is a
Beta($2+\cos(2\pi j/J+\pi),2+\cos(2\pi j/J)$). In the first scenario, we also
report an algorithm which restart at times where the prior changes; this can
be seen as an oracle we aim to emulate. Results are reported on Figure 3 and
are averaged over 100 runs.

(a) Abruptly changing environment

(b) Slowly changing environment

Figure 3: Lifelong regret of various meta-algorithms in non-stationary
environments. Shaded areas show standard errors.

In both scenarios, DGreedy and SWGreedy are able to track the change in the
prior distribution while the naive Greedy fails to do so. In the abruptly
changing scenario, SWGreedy outperforms DGreedy, thus underlining the need to
discard data from the previous prior. Regrettably, when the first prior comes
back, both algorithms take a long time before finding again the previous
learned solution; making the naive Greedy competitive in this experiment even
if it completely missed the first change. Conversely in the slowly changing
scenario, Greedy fails to track the slow change in the prior distribution and
thus accumulates a larger regret with in addition a broad variance. DGreedy
and SWGreedy are roughly similar in this case, though SWGreedy performs
slightly better in the end. We would also like to mention that there is a
hidden parameter in DGreedy. Indeed, in the Greedy algorithm, each arm must
have enough information for its index to calculated. In Greedy, and also
SWGreedy, this is done by ensuring that each arm has been played at least
once. In DGreedy, this initialization is more challenging to determine and we
believe it is partly responsible for the poor performance of DGreedy. In both
experiments, we arbitrarily set this value to 1.

##  6 Application to mortal bandits

Finally in this last section, we apply our method to a more realistic setting,
the mortal bandit problem [14], where arms appear and disappear regularly (in
particular, an arm is not always available contrary to the standard model).
While the notion of episode may be more elusive in this setting, we show that
synchronizing an episode according to the expected lifetime of arms can help
to overcome this difficulty. We look upon the case where this value is known
and the one where it is not and thus have to be estimated. We also have to
modify the index of the UCB sub-algorithm to take into account that arms
arrive at different times and for the unknown expected lifetime. Thereby, we
replace the $\log(T)$ term by $\log(t-s_{k}+1)$, where $t$ and $s_{k}$ denotes
respectively the current and the arrival time steps for arm $k$. We then again
pick the Greedy algorithm as meta-algorithm.

We consider the same setting as [14]. Although they mostly consider a large
number of arms, we previously illustrated in Section 3 that this problem can
be reduced via sub-sampling to a more tractable one, and with better
performance as well. Therefore we focus our attention on problems with a small
number of arms. In this setting, the number of arms remains fixed throughout
the time horizon $T$, that is when an arm dies, it is immediately replaced by
another one. The lifetime of arm $k$, denoted $L_{k}$, is drawn i.i.d. from a
Geometric distribution with mean lifetime $L$; this arm died after being
available for $L_{k}$ rounds. We also assume that arms are Bernoulli random
variables. We consider two scenarios: in the first one, mean rewards of arms
are drawn i.i.d. from a uniform distribution over [0, 1], while in the second
scenario they are drawn from a Beta(1, 3) distribution. In both cases, we fix
the number of arms $K=5$ and the expected lifetime $L=1000$. The horizon is
set at $T=1000L$, meaning that there are on average 1000 episodes throughout
the time horizon. We compare several algorithms: the untuned UCB algorithm and
its optimally tuned variant OracleUCB, along with a tuned AdaptiveGreedy (AG)
[14];222Both algorithms have been tuned with respect to the mean lifetime. On
scenario 1, $\gamma=0.25$ and $c=1.5$, while on scenario 2, $\gamma=0.25$ and
$c=2.5$. and our proposed methods, PeriodicUpdate-UCB (PU-UCB) and
EstimatedPeriodicUpdate-UCB (EPU-UCB), where in the first one we assume the
knowledge of the expected lifetime, while in the second it is estimated by the
empirical mean of dead arms. On top of both our proposed algorithms lie a
Greedy algorithm on a discretization of $n=\sqrt{1000}$ points. Results are
averaged over 100 runs and are reported on Figure 4.

(a) Uniform prior

(b) Beta(1, 3) prior

Figure 4: Regret of various algorithms in the mortal bandit setting. Shaded
areas show standard errors. PU-UCB and PEU-UCB are almost identical in (a).

These experiments further underline the benefit of tuning the UCB algorithm
for practical purposes. AG, a state of the art algorithm in the mortal bandit
setting, is clearly outperformed by OracleUCB. Additionally, PU-UCB and EPU-
UCB, with somewhat similar performances on both setups, become rapidly better
than AG, despite that the latter being optimally tuned. We also remark once
more that the regret of both algorithms is sublinear, highlighting the
performance of the Greedy meta-algorithm. Interestingly, EPU-UCB performs
slightly better than PU-UCB on scenario 2, hinting at a potentially better
decomposition of episodes.

##  7 Conclusion

In this paper, we studied a lifelong learning problem in the multi-armed
bandit framework where tasks arrive sequentially, sampled from a problem class
with some prior distribution. We first introduced our method which consists in
optimize a bandit algorithm, focusing on confidence interval width tuning of
UCB-like algorithms. We then considered a bandit over bandit approach
employing greedy algorithms as meta-algorithm and evaluated them in both
stationary and non-stationary environments. Finally, we applied our method to
a more realistic setting, the mortal bandit problem, by decomposing the time
horizon into episodes according to the mean lifetime of arms and showed great
empirical improvement compared to previous work.

#### Interesting directions

The most prominent future work, especially in terms of practical applications,
concerns the tracking of seasonal environments. It is crucial for building
lifelong learning agents. Just recently this problem has been studied in the
non-stationary bandit setting [21, 15].

Another direction may be the analysis of the Greedy algorithm in the
continuous-armed bandit problem. It has been shown in a recent line a work
that it enjoys great performances in several bandit frameworks [5, 27, 6, 40],
and this setting is most likely one of them as shown indirectly in our
experiments. Although it may be suboptimal, with high probability it
concentrates quickly on arms with high expected rewards and thus works
extremely well in practice. The next question is the “optimal” discretization
for the greatest performance.

Finally in this first work, we focused solely on classical context-free
bandits, but extending it to other settings that receive increasing interest,
such as contextual [38], combinatorial [19, 39] or multi-player bandits [10,
11], seems also quite crucial and an interesting direction of research.

## Acknowledgments and Disclosure of Funding

The research presented was supported by the French National Research Agency,
under the project BOLD (ANR19-CE23-0026-04) and it was also supported in part
by a public grant as part of the Investissement d’avenir project, reference
ANR-11-LABX-0056-LMH, LabEx LMH, in a joint call with Gaspard Monge Program
for optimization, operations research and their interactions with data
sciences.

## References

  * [1] Shipra Agrawal and Navin Goyal  “Further optimal regret bounds for thompson sampling”  In _Artificial intelligence and statistics_ , 2013, pp. 99–107
  * [2] Jean-Yves Audibert and Sébastien Bubeck  “Minimax policies for adversarial and stochastic bandits”, 2009
  * [3] Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer  “Finite-time analysis of the multiarmed bandit problem”  In _Machine learning_ 47.2-3 Springer, 2002, pp. 235–256
  * [4] Peter Auer, Ronald Ortner and Csaba Szepesvári  “Improved rates for the stochastic continuum-armed bandit problem”  In _International Conference on Computational Learning Theory_ , 2007, pp. 454–468  Springer
  * [5] Hamsa Bastani, Mohsen Bayati and Khashayar Khosravi  “Mostly exploration-free algorithms for contextual bandits”  In _arXiv preprint arXiv:1704.09011_ , 2017
  * [6] Mohsen Bayati, Nima Hamidi, Ramesh Johari and Khashayar Khosravi  “Optimal and Greedy Algorithms for Multi-Armed Bandits with Many Arms”  In _arXiv preprint arXiv:2002.10121_ , 2020
  * [7] Donald A Berry and Bert Fristedt  “Bandit problems: sequential allocation of experiments (Monographs on statistics and applied probability)”  In _London: Chapman and Hall_ 5 Springer, 1985, pp. 71–87
  * [8] Zahy Bnaya, Rami Puzis, Roni Stern and Ariel Felner  “Volatile multi-armed bandits for guaranteed targeted social crawling”  In _Workshops at the Twenty-Seventh AAAI Conference on Artificial Intelligence_ , 2013
  * [9] Djallel Bouneffouf and Irina Rish  “A survey on practical applications of multi-armed and contextual bandits”  In _arXiv preprint arXiv:1904.10040_ , 2019
  * [10] Etienne Boursier and Vianney Perchet  “SIC-MMAB: synchronisation involves communication in multiplayer multi-armed bandits”  In _Advances in Neural Information Processing Systems_ , 2019, pp. 12071–12080
  * [11] Etienne Boursier, Emilie Kaufmann, Abbas Mehrabian and Vianney Perchet  “A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players”  In _AISTATS 2020_ , 2020
  * [12] Craig Boutilier et al.  “Differentiable Bandit Exploration”  In _arXiv preprint arXiv:2002.06772_ , 2020
  * [13] Sébastien Bubeck and Nicolo Cesa-Bianchi  “Regret analysis of stochastic and nonstochastic multi-armed bandit problems”  In _arXiv preprint arXiv:1204.5721_ , 2012
  * [14] Deepayan Chakrabarti, Ravi Kumar, Filip Radlinski and Eli Upfal  “Mortal multi-armed bandits”  In _Advances in neural information processing systems_ , 2009, pp. 273–280
  * [15] Ningyuan Chen, Chun Wang and Longlin Wang  “Learning and Optimization with Seasonal Patterns”  In _arXiv preprint arXiv:2005.08088_ , 2020
  * [16] Zhiyuan Chen and Bing Liu  “Lifelong machine learning”  In _Synthesis Lectures on Artificial Intelligence and Machine Learning_ 10.3 Morgan & Claypool Publishers, 2016, pp. 1–145
  * [17] Wang Chi Cheung, David Simchi-Levi and Ruihao Zhu  “Hedging the drift: Learning to optimize under non-stationarity”  In _arXiv preprint arXiv:1903.01461_ , 2019
  * [18] Rémy Degenne and Vianney Perchet  “Anytime optimal algorithms in stochastic multi-armed bandits”  In _Proceedings of The 33rd International Conference on Machine Learning_ 48, Proceedings of Machine Learning Research  New York, New York, USA: PMLR, 2016, pp. 1587–1595  URL: http://proceedings.mlr.press/v48/degenne16.html
  * [19] Rémy Degenne and Vianney Perchet  “Combinatorial semi-bandit with known covariance”  In _Advances in Neural Information Processing Systems_ , 2016, pp. 2972–2980
  * [20] Aniket Anand Deshmukh, Urun Dogan and Clay Scott  “Multi-task learning for contextual bandits”  In _Advances in neural information processing systems_ , 2017, pp. 4848–4856
  * [21] Giuseppe Di Benedetto, Vito Bellini and Giovanni Zappella  “A Linear Bandit for Seasonal Environments”  In _arXiv preprint arXiv:2004.13576_ , 2020
  * [22] Aurélien Garivier and Eric Moulines  “On upper-confidence bound policies for switching bandit problems”  In _International Conference on Algorithmic Learning Theory_ , 2011, pp. 174–188  Springer
  * [23] John C Gittins  “Bandit processes and dynamic allocation indices”  In _Journal of the Royal Statistical Society: Series B (Methodological)_ 41.2 Wiley Online Library, 1979, pp. 148–164
  * [24] John Gittins, Kevin Glazebrook and Richard Weber  “Multi-armed bandit allocation indices”  John Wiley & Sons, 2011
  * [25] Cédric Hartland et al.  “Multi-armed bandit, dynamic environments and meta-bandits”, 2006
  * [26] Chih-Wei Hsu et al.  “Empirical bayes regret minimization”  In _arXiv preprint arXiv:1904.02664_ , 2019
  * [27] Sampath Kannan et al.  “A smoothed analysis of the greedy algorithm for the linear contextual bandit problem”  In _Advances in Neural Information Processing Systems_ , 2018, pp. 2227–2236
  * [28] Emilie Kaufmann  “On Bayesian index policies for sequential resource allocation”  In _arXiv preprint arXiv:1601.01190_ , 2016
  * [29] Robert D Kleinberg  “Nearly tight bounds for the continuum-armed bandit problem”  In _Advances in Neural Information Processing Systems_ , 2005, pp. 697–704
  * [30] Levente Kocsis and Csaba Szepesvári  “Bandit based monte-carlo planning”  In _European conference on machine learning_ , 2006, pp. 282–293  Springer
  * [31] Volodymyr Kuleshov and Doina Precup  “Algorithms for multi-armed bandit problems”  In _arXiv preprint arXiv:1402.6028_ , 2014
  * [32] Tze Leung Lai  “Adaptive treatment allocation and the multi-armed bandit problem”  In _The Annals of Statistics_ JSTOR, 1987, pp. 1091–1114
  * [33] Tor Lattimore  “Refining the confidence level for optimistic bandit strategies”  In _The Journal of Machine Learning Research_ 19.1 JMLR. org, 2018, pp. 765–796
  * [34] Tor Lattimore and Csaba Szepesvári  “Bandit algorithms”  In _preprint_ , 2018, pp. 28
  * [35] Alessandro Lazaric and Emma Brunskill  “Sequential transfer in multi-armed bandit with finite set of models”  In _Advances in Neural Information Processing Systems_ , 2013, pp. 2220–2228
  * [36] Lisha Li et al.  “Hyperband: A novel bandit-based approach to hyperparameter optimization”  In _The Journal of Machine Learning Research_ 18.1 JMLR. org, 2017, pp. 6765–6816
  * [37] Francis Maes, Louis Wehenkel and Damien Ernst  “Meta-learning of exploration/exploitation strategies: The multi-armed bandit case”  In _International Conference on Agents and Artificial Intelligence_ , 2012, pp. 100–115  Springer
  * [38] Vianney Perchet and Philippe Rigollet  “The multi-armed bandit problem with covariates”  In _The Annals of Statistics_ 41.2 Institute of Mathematical Statistics, 2013, pp. 693–721
  * [39] Pierre Perrault, Etienne Boursier, Michal Valko and Vianney Perchet  “Statistical efficiency of thompson sampling for combinatorial semi-bandits”  In _Advances in Neural Information Processing Systems_ 33, 2020
  * [40] Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan and Zhiwei Steven Wu  “Greedy Algorithm almost Dominates in Smoothed Contextual Bandits”  In _arXiv preprint arXiv:2005.10624_ , 2020
  * [41] Daniel Russo and Benjamin Van Roy  “Learning to optimize via posterior sampling”  In _Mathematics of Operations Research_ 39.4 INFORMS, 2014, pp. 1221–1243
  * [42] Jurgen Schmidhuber  “Evolutionary principles in self-referential learning”  In _On learning how to learn: The meta-meta-… hook.) Diploma thesis, Institut f. Informatik, Tech. Univ. Munich_ 1, 1987, pp. 2
  * [43] Daniel L Silver, Qiang Yang and Lianghao Li  “Lifelong machine learning systems: Beyond learning algorithms”  In _2013 AAAI spring symposium series_ , 2013
  * [44] Aleksandrs Slivkins  “Introduction to multi-armed bandits”  In _arXiv preprint arXiv:1904.07272_ , 2019
  * [45] Sebastian Thrun  “Lifelong learning algorithms”  In _Learning to learn_ Springer, 1998, pp. 181–209
  * [46] Sebastian Thrun and Lorien Pratt  “Learning to learn”  Springer Science & Business Media, 2012
  * [47] Stefano Traca, Cynthia Rudin and Weiyu Yan  “Reducing Exploration of Dying Arms in Mortal Bandits”  In _arXiv preprint arXiv:1907.02571_ , 2019
  * [48] Joannes Vermorel and Mehryar Mohri  “Multi-armed bandit algorithms and empirical evaluation”  In _European conference on machine learning_ , 2005, pp. 437–448  Springer
  * [49] Qingyun Wu, Naveen Iyer and Hongning Wang  “Learning contextual bandits in a non-stationary environment”  In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_, 2018, pp. 495–504
  * [50] Qingyun Wu, Huazheng Wang, Yanen Li and Hongning Wang  “Dynamic Ensemble of Contextual Bandits to Satisfy Users’ Changing Interests”  In _The World Wide Web Conference_ , 2019, pp. 2080–2090

##  Appendix A Additional simulations

In this section, we repeat the simulations of Sections 3, 4.1 and 4.2 for
different environments.

###  A.1 Choice of the class of algorithms

In this subsection, we repeat the simulations of Section 3. We recall that we
evaluate the Bayesian regret of several UCB-like algorithms as a function of
their parameters $\gamma$. We consider two scenarios: the first scenario is a
Gaussian bandit problem where mean rewards are drawn i.i.d. from a uniform
distribution over $[0,1]$; while the second scenario is a Bernoulli bandit
problem where mean rewards are drawn i.i.d. from a Beta(1, 3) distribution. In
all experiments, the horizon is fixed at $T=1000$ and we vary the number of
arms $K$. Results are averaged over $5000$ iterations and displayed on Figure
5.

(a) Scenario 1 / $K=5$

(b) Scenario 1 / $K=63$

(c) Scenario 1 / $K=250$

(d) Scenario 2 / $K=5$

(e) Scenario 2 / $K=63$

(f) Scenario 2 / $K=250$

Figure 5: Bayesian regret of various algorithms as a function of $\gamma$ for
diverse environments and numbers of arms $K$. Rows correspond respectively to
Gaussian bandits with a uniform prior and Bernoulli bandits with a Beta(1, 3)
prior.

In the first scenario, we observe a similar behavior compared to the Bernoulli
case: for small numbers of arms $K$, AdaUCB performs better than UCB for all
$\gamma$; for moderate values of $K$, the Greedy algorithm is roughly the
best; and for large values $K$, SubUCB performs the best. Similarly,
SubUCB($m$) performs better as $m$ grows larger and becomes more sensitive to
$\gamma$ at the same time. In the second scenario, the same behavior can be
noticed, however what we called moderate and large values of $K$ are, in this
case, much higher than previously.

###  A.2 Influence of the initialization

In this subsection, we repeat the simulations of Section 4.1. We recall that
we study the impact of several initializations on the lifelong regret. To do
so, we set $\gamma=0.22$ in the UCB algorithm. We consider three scenarios:
the first scenario is a Bernoulli bandit problem where mean rewards are drawn
i.i.d. from a uniform distribution over $[0,1]$, the second scenario is a
Gaussian bandit problem where mean rewards are drawn i.i.d. from a uniform
distribution over $[0,1]$ and the third scenario is a Bernoulli bandit problem
where mean rewards are drawn i.i.d. from a Beta(1, 3) distribution. In all
experiments, the horizon is fixed at $T=1000$ and we vary the number of arms
$K$. For $K=5$ and $K=63$, the numbers of episodes is $J=100$, whereas for
$K=250$ it is $J=10$. Results are averaged over $500$ iterations for $K=5$,
$100$ for the rest, and displayed on Figure 6.

(a) Scenario 1 / $K=5$

(b) Scenario 1 / $K=63$

(c) Scenario 1 / $K=250$

(d) Scenario 2 / $K=5$

(e) Scenario 2 / $K=63$

(f) Scenario 2 / K = 250

(g) Scenario 3 / $K=5$

(h) Scenario 3 / $K=63$

(i) Scenario 3 / $K=250$

Figure 6: Lifelong regret of a deterministic meta-algorithm with various
initializations in stationary environments. Rows correspond respectively to
Bernoulli bandits with a uniform prior, Gaussian bandits with a uniform prior
and Bernoulli bandits with a Beta(1, 3) prior. Shaded areas show standard
errors.

It is complex to observe a clear trend across the different simulations. For
small values of $K$, the choice of initialization is insignificant; except for
the initialization at 0 in the first scenario, they all have roughly the same
performance. For intermediate values of $K$, the impact of the choice of
initialization becomes apparent. Although there is no optimal choice,
initializing arms with the median of previous arms seems more robust. For
large value of $K$, a clear trend is emerging: pulling each arm once is always
the worst thing to do. It was expected since we spend most of the time
initializing arms. There is still no optimal choice in this case, yet the
initialization at 0 seems more robust.

###  A.3 Learning in a stationary environment

In this subsection, we repeat the simulations of Section 4.2. We recall that
we study the impact of several meta-algorithms on the lifelong regret. We
consider two scenarios: the first scenario is a Gaussian bandit problem where
mean rewards are drawn i.i.d. from a uniform distribution over $[0,1]$; while
the second scenario is a Bernoulli bandit problem where mean rewards are drawn
i.i.d. from a Beta(1, 3) distribution. In all experiments and for each
episode, the horizon is fixed at $T=1000$ and the number of arms at $K=5$; and
for the meta-algorithm, the number of episodes is set at $J=10000$. Results
are averaged over $100$ iterations and illustrated on Figure 7.

(a) Gaussian bandits with uniform prior

(b) Bernoulli bandits with Beta(1, 3) prior

Figure 7: Lifelong regret of various meta-algorithms in stationary
environments. Shaded areas show standard errors.

The results are similar to Section 4.2: TS fails to learn in that time frame,
while AdaUCB manages to do so but is outperformed for a long period of time by
a naive Greedy. As for Greedy(100), it still performs extremely well; its
regret is close to the optimal one and is again sublinear.