summaries: This paper studies the expressivity, complexity and unpredictability of emergent languages in referential games. The authors demonstrate that the expressivity of emergent languages is a trade-off between the complexity and unpredictability of the context that the languages are used in. They also introduce a contrastive loss based training method for referential games that alleviates the collapse of message types often seen when using other standard training methods.

summaries: The authors investigate what aspects of scenario design affect the resultant communication protocol in emergent communication. Specifically, the authors investigate whether scenario complexity (in terms of having many similar distractors) and scenario unpredictability (in terms of future batches not containing items to previous batches) affect the expressivity (measured in terms of learnability) of the resulting protocol.  Further, the authors show that defining a softmax loss over the entire batch of possible references (dubbed the 'contrastive' loss) outperforms the 'referential' loss used in previous works.

summaries: This paper studies the "expressivity" of emergent language in language games. To my understanding, "expressivity" is empirically the transferring ability of the language to unseen data. In this paper, the authors propose two factors of the underlying language game that can affect the expressivity of emergent language: context complexity and unpredicability. In referential games, the context is the distractor candidates for a sample. Complexity denotes how likely a "close" distractor will be included in the candidates. Unpredictability is how likely the context for a single sample will be different among epochs. This paper proposed hypotheses that both context complexity and unpredicability can improve language expressivity, but these two factors are "contradictory" and we need to have a trade-off between them. The hypotheses are supported by empirical experiment results.

summaries: The paper studies the properties of emergent languages in DL-based language games. In particular, they look at referential games where speakers emit messages and listeners need to identify the target object observed by the speaker from some set of candidate objects.    They define the expressivity of an emergent language as the amount of discriminatory information required to encode the inputs so that a listener can correctly decode them. In this setting, complexity refers to the similarity between different objects in a given context. In a context with higher complexity, more similar objects will be present, and more discriminatory information will have to be encoded so that a listener is capable of identifying the correct target. In their definition, the notion of unpredictability can be thought of as how stable the information necessary for encoding is across different trials.    Their primary contribution is to support the hypothesis that the expressivity of emergent language is determined by (and a trade-off between) the complexity and unpredictability of context in language games. The authors introduce a new measure to evaluate expressivity based on partial ordering between languages in terms of their generalization across tasks. They argue that mutual information is not the most appropriate measure to evaluate the expressivity of languages. They propose a contrastive loss which they show helps mitigate the issue of the collapse of message types.

abstractText: Researchers are using deep learning models to explore the emergence of language in various language games, where simulated agents interact and develop an emergent language to solve a task. We focus on the factors which determine the expressivity of emergent languages, which reflects the amount of information about input spaces those languages are capable of encoding. We measure the expressivity of emergent languages based on their generalisation performance across different games, and demonstrate that the expressivity of emergent languages is a trade-off between the complexity and unpredictability of the context those languages are used in. Another novel contribution of this work is the discovery of message type collapse. We also show that using the contrastive loss proposed by Chen et al. (2020a) can alleviate this problem, compared with the standard referential loss used by the existing works.

title: Measuring compositionality in representation learning

venue: arXiv preprint arXiv:1902.07181,

authors:
Henry Brighton
Simon Kirby

title: Understanding linguistic evolution by visualizing the emergence of topographic mappings

venue: Artificial life,

authors:
Rahma Chaabouni
Eugene Kharitonov
Diane Bouchacourt
Emmanuel Dupoux
Marco Baroni

title: Compositionality and generalization in emergent languages

venue: arXiv preprint arXiv:2004.09124,

authors:
Ting Chen
Simon Kornblith
Mohammad Norouzi
Geoffrey Hinton

title: A simple framework for contrastive learning of visual representations

venue: In International conference on machine learning,

authors:
Xinlei Chen
Haoqi Fan
Ross Girshick
Kaiming He

title: Improved baselines with momentum contrastive learning

venue: arXiv preprint arXiv:2003.04297,

authors:
Laura Graesser
Kyunghyun Cho
Douwe Kiela

title: Emergent linguistic phenomena in multi-agent communication games

venue: arXiv preprint arXiv:1901.08706,

authors:
Jean-Bastien Grill
Florian Strub
Florent Altché
Corentin Tallec
Pierre H Richemond
Elena Buchatskaya
Carl Doersch
Bernardo Avila Pires
Zhaohan Daniel Guo
Mohammad Gheshlaghi Azar

title: Bootstrap your own latent: A new approach to self-supervised learning

venue: arXiv preprint arXiv:2006.07733,

authors:
Shangmin Guo
Yi Ren
Serhii Havrylov
Stella Frank
Ivan Titov
Kenny Smith

title: The emergence of compositional languages for numeric concepts through iterated learning in neural agents

venue: EvoLang,

authors:
Raia Hadsell
Sumit Chopra
Yann LeCun

title: Dimensionality reduction by learning an invariant mapping

venue: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06),

authors:
Serhii Havrylov
Ivan Titov

title: Emergence of language with multi-agent games: Learning to communicate with sequences of symbols

venue: In Advances in Neural Information Processing Systems,

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural computation,

authors:
Eric Jang
Shixiang Gu
Ben Poole

title: Categorical reparameterization with gumbel-softmax. 2017

venue: URL https://arxiv.org/abs/1611.01144

authors:
Ivana Kajić
Eser Aygün
Doina Precup

title: Learning to cooperate: Emergent communication in multi-agent navigation

venue: arXiv preprint arXiv:2004.01097,

authors:
Eugene Kharitonov
Rahma Chaabouni
Diane Bouchacourt
Marco Baroni

title: EGG: a toolkit for research on Emergence of lanGuage in Games

venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP): System Demonstrations. Association for Computational Linguistics,

title: Entropy minimization in emergent languages

venue: In International Conference on Machine Learning,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

title: Spontaneous evolution of linguistic structure-an iterated learning model of the emergence of regularity and irregularity

venue: IEEE Transactions on Evolutionary Computation,

authors:
Simon Kirby
James R Hurford

title: The emergence of linguistic structure: An overview of the iterated learning model

venue: In Simulating the evolution of language,

authors:
Simon Kirby
Tom Griffiths
Kenny Smith

title: Iterated learning and the evolution of language

venue: Current opinion in neurobiology,

authors:
Simon Kirby
Monica Tamariz
Hannah Cornish
Kenny Smith

title: Compression and communication in the cultural evolution of linguistic structure

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

venue: Advances in neural information processing systems,

authors:
Angeliki Lazaridou
Alexander Peysakhovich
Marco Baroni

title: Multi-agent cooperation and the emergence of (natural) language

venue: In International Conference on Learning Representations,

authors:
Angeliki Lazaridou
Karl Moritz Hermann
Karl Tuyls
Stephen Clark

title: Emergence of linguistic communication from referential games with symbolic and pixel input

venue: arXiv preprint arXiv:1804.03984,

authors:
Jason Lee
Kyunghyun Cho
Jason Weston
Douwe Kiela

title: Emergent translation in multi-agent communication

title: Convention: A philosophical study

authors:
Fushan Li
Michael Bowling

title: Ease-of-teaching and language structure from emergent communication

venue: arXiv preprint arXiv:1906.02403,

authors:
Ryan Lowe
Yi Wu
Aviv Tamar
Jean Harb
Pieter Abbeel
Igor Mordatch

title: Multi-agent actorcritic for mixed cooperative-competitive environments

venue: arXiv preprint arXiv:1706.02275,

authors:
Sinno Jialin Pan
Qiang Yang

title: A survey on transfer learning

venue: IEEE Transactions on knowledge and data engineering,

authors:
Yi Ren
Shangmin Guo
Matthieu Labeau
Shay B Cohen
Simon Kirby

title: Compositional languages emerge in a neural iterated learning model

authors:
David Silver
Aja Huang
Chris J Maddison
Arthur Guez
Laurent Sifre
George Van Den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot

title: Mastering the game of go with deep neural networks and tree

venue: search. nature,

authors:
James Winters
Simon Kirby
Kenny Smith

title: Contextual predictability shapes signal

venue: autonomy. Cognition,

title: Philosophical investigations

authors:
Luyao Yuan
Zipeng Fu
Jingyue Shen
Lu Xu
Junhong Shen
Song-Chun Zhu

title: Emergence of pragmatics from referential game between theory of mind agents

authors:
Sai Qian Zhang
Qi Zhang
Jieyu Lin

title: Efficient communication in multi-agent reinforcement learning via variance based control

authors:
Chen et al
2020a
Grill

heading: 1 INTRODUCTION

text:
Language games were first introduced by Wittgenstein (1954) to explore the meanings of language utterances. Instantiating this concept with the signalling game design from Lewis (1969) enables linguists to explore the emergence of linguistic structure (Kirby, 2001; Kirby & Hurford, 2002) where artificial languages are represented as symbolic systems. The success of deep learning (DL) models on complicated cognitive tasks (Krizhevsky et al., 2012; LeCun et al., 2015; Silver et al., 2016) then inspired researchers to apply DL-based models to language games for investigating agents’ ability to invent communication protocols without preset rules.
In language games implemented in existing works (e.g. Lazaridou et al., 2018; Graesser et al., 2019; Zhang et al., 2019; Lee et al., 2018; Yuan et al., 2020), there are usually two types of agents, speakers that emit messages based on their observations (i.e. target objects) and listeners that receive messages and take actions accordingly, as illustrated in Figure 1. Based on the goals for listeners, we can categorise most of the games into the following three types: 1) referential games where listeners need to select the target object observed by the speaker among a set of candidate objects (candidates for short) (e.g. Lazaridou et al., 2017; Ren et al., 2020); 2) reconstruction games where listeners need to reconstruct the speaker’s observation (e.g. Chaabouni et al., 2020; Kharitonov et al., 2020); and 3) navigation games where listeners need to go to the location specified by the speaker (e.g. Lowe et al., 2017; Kajić et al., 2020). We focus on referential games, illustrated in Figure 1a, which have been well investigated in both the linguistic community (e.g. Winters et al., 2018; Kirby et al., 2014) and emergent communication community (e.g. Lazaridou et al., 2018; Li & Bowling, 2019).
It is reasonable to assume that listeners in referential games can differentiate the target object from the other distractors in the context as long as the speaker’s message encodes some unique feature of the target. Therefore, the speaker’s messages must convey different amount of information for listeners to complete their task in games with candidates that are similar in different degree. For example, to distinguish two very similar objects in the candidates set, e.g. blue wide-stripped shirt and blue narrow-stripped shirt, it requires more information about the target to be encoded by the speaker’s message than to distinguish a shirt from a cup. Experiments with human participants show that emergent languages are sensitive to the requirements of the communicative tasks for which they are used, with languages developing in which only the necessary discriminatory information is encoded
Speaker Listener
Message
(a) Illustration of the referential game we investigate in this work. Observations are concatenations of two 5-digits-long one-hot vectors. The objective of the listener in to select among a set of candidate inputs (the context).
Speaker's Encoder (MLP) Speaker's Message Generator (LSTM)
Listener's Message Encoder (LSTM)
Speaker Modules
Listener Modules
Listener's Candidate Encoder (MLP)
Input
target
distractor
Listener's Action Module (Softmax)
Message
output distribution
Candidate set (context)
(b) Illustration of the architecture of agents we implement for referential games. Blue modules are components of the speaker, and green modules belong to the listener. Orange and grey indicate the vectors generated by agents and input samples respectively.
Figure 1: Diagram of referential game and the architecture of our agents.
(Winters et al., 2018). Following Kirby et al. (2015), we refer to such ability to encode information about input space (e.g. structure, dimensionality, distribution of samples) as expressivity. In this work, we explore the factors that influence expressivity in the framework of DL-based language games, and we argue that it is important to understand these factors such that agents could develop languages that are useful in general.
Our contribution in this work is threefold. First, we propose and verify a hypothesis about the determining factors of expressivity of emergent languages under the DL-based framework. Following Winters et al. (2018), we show that context size (i.e. the number of candidates the listener must select among when interpreting the speaker’s message) influence both the complexity and unpredictability of that context. Complexity refers to the similarity between the items in the context: in order for the listener to select the target, more information needs to be encoded in the speaker’s signal if the context contains more similar distractors for a given target. Unpredictability refers to the extent to which the information that needs to be encoded by the speaker is stable across contexts in successive episodes of communication: in games where the information required by the listener differs from trial (training epoch for DL agents) to trial, the speaker needs to encode more information on every trial in order to be sure to encode the information the listener needs.1 As we show in Section 3.1, complexity and unpredictability are affected differently by the context size: as context size increases, complexity increases but unpredictability decreases. Therefore, we propose and verify the following hypothesis about the determining factors of expressivity:
The expressivity of emergent languages is a trade-off between the complexity and the unpredictability of context in language games. [1]
Our second contribution is a novel measure of expressivity based on partial ordering of languages in terms of their generalisation performances across tasks. Although expressivity is related to the amount of information encoded in a language, we illustrate that mutual information (MI) is not an appropriate measurement for expressivity in Section 3.2. Considering that one of our objectives is to facilitate a universally useful emergent language, we propose to measure expressivity of a language based on the generalisation performance of agents trained with it across different games. Since it is more challenging to quantitatively measure it, we focus on the partial ordering between languages in this first work towards understanding it.
Our final contribution is the discovery of message type collapse, i.e. the number of unique messages is significantly less than the size of input space in relatively easy games, which further leads to highly ambiguous emergent languages. To overcome the technical limitations imposed by GPU memory size on large-scale referential games, we introduce the contrastive loss proposed by Chen et al. (2020a) in referential games. While comparing the behaviour of the contrastive loss and the loss function by previous work (e.g Havrylov & Titov, 2017; Li & Bowling, 2019; Ren et al., 2020; Guo et al., 2020), we find that this contrastive loss could greatly alleviate the collapse of message types, thus lead to more disambiguous emergent languages.
1Context, complexity, and unpredictability are defined and discussed in depth in Section 3.

heading: 2 GAMES, AGENTS AND LEARNING METHODS

heading: 2.1 GAME ENVIRONMENT AND ARCHITECTURE OF AGENTS

text: Environment Components As shown in Figure 1b, the environment in our referential games have the following components: 1) input space X from which the speaker’s observations are drawn, which consists of 10, 000 possible inputs2 where each x P X is a concatenation of 4 one-hot vectors whose length is 10; 2) message space M consists of 106 6-tokens-long sequences m (called as a message type) where the size of the token inventory is 10; note that the tokens are initially meaningless, and meaning emerges through the negotiation of a communication protocol between speaker and listener; 3) candidate set C which contains a target input xt and |C| ´ 1 distractors txd1 ,xd2 , . . . ,xd|C|´1u sampled uniformly at random from X without replacement. Agents The architecture of the agents we implemented is also illustrated in Figure 1b: 4) speaker S consists of both a multi layer perceptron (MLP) for encoding the 40-digits-long target input xt onto a 256-digits-long embedding hS , and a decoder for generating a message m based on long-short term memory (LSTM) network (Hochreiter & Schmidhuber, 1997). 5) listener L is constituted by an LSTM-based sequence encoder which encodes m into a 256-digits-long embedding hLpmq, and an MLP for encoding the inputs which can be denoted by fLcencp¨q. Definition of an emergent language: following e.g. Ren et al. (2020), we can then define an emergent language L as a mapping function from the input space X to the message space M, i.e. L : X ÞÑ M, thus it can be represented as tpxi,Lpxiqq|@xi P X u. Note that L could be a noninjective mapping function, i.e. it is possible for two different inputs to be mapped to an identical message thus the number of message types might be less than the number of unique inputs.

heading: 2.2 LEARNING METHODS OF AGENTS

text:
In the previous works (e.g. Havrylov & Titov, 2017), the action module of L is usually a softmax function that would produce a categorical distribution over the candidates based on the distance between hLpmq and embeddings of each candidate fLcencpxiq obtained through another MLP-based candidate encoder. By comparing the loss function used in Havrylov & Titov (2017) and the contrastive loss function proposed by Hadsell et al. (2006), we find that the aim of both functions is the same, i.e. to make the distance between positive pairs (xt and m) closer while keeping the embedding for negative pairs (xd and m) as far apart as possible. To effectively validate our hypothesis, we need to make the whole input space X as candidate set C in which case the batch is too large to be stored in GPU memory (since the space complexity is Op|X |2q). Therefore, to overcome this issue, we adapt the contrastive learning method proposed by Chen et al. (2020a) to referential games. Suppose that we have a batch of input samples B “ tx1,x2, . . . ,xi, . . . ,x|B|u and the corresponding messages from the speaker are tm1,m2, . . . ,mi, . . . ,m|B|u which would be further encoded into thLm1 ,h L m2 , . . . ,h L mi , . . . ,h L m|B|
u by the listener L. Then the loss function for a sample xi is defined on a softmax function:
`i “ ´ log exp
´
hLmi J ¨ fLcencpxiq
¯
ř|B| j“1 exp
´
hLmi J ¨ fLcencpxjq
¯ . (1)
In this way, the number of candidates |C| is exactly the batch size |B| during training. More details about the comparison between referential loss and this contrastive loss can be found in Appendix A.
As for updating the parameters, we use the Adam algorithm introduced by Kingma & Ba (2014), and the learning rate is set to 10´4. To allow the gradients being propagated through the discrete channel to overcome the sampling issue of messages, we apply the Gumbel-Softmax trick proposed by Jang et al. (2017), and the temperature hyper-parameter τ is set to 1.0.
Our implementation3 of games bases on the framework EGG developed by Kharitonov et al. (2019). The experiments across 6 random seeds, 18 source games, 11 target games took 4, 216 hours in total, on Nvidia Tesla P100. Definition of “source/target games” are given in the following Section 4.2.
2According to the results from Chaabouni et al. (2020), an input space containing 10, 000 possible inputs is large enough for neural models to achieve ą 99% generalisation accuracy.
3Codes are provided in the supplementary materials.

heading: 3 CONTEXT AND EXPRESSIVITY

heading: 3.1 CONTEXT, AND ITS COMPLEXITY AND UNPREDICTABILITY IN DIFFERENT GAMES

text:
Context: Communication between humans always takes place w.r.t. some context (Winters et al., 2018). For humans, that context includes: 1) features of the environment that can be directly perceived by the dialogue participants and used for comprehending an utterance (e.g. “cup” is interpreted as an object in the immediate physical context); and 2) information that cannot be directly perceived but can affect the interpretation of utterances (e.g. using and interpreting “cup” assumes some shared knowledge of what counts as a “cup”; once a particular cup has been established as salient in particular dialogue, further utterances of “the cup” or “it” will be interpreted as referring to that specific salient cup).
Inspired by this conclusion from pragmatics, in the DL-based language games, we define context as the supervision information involved in the calculation of losses, i.e. the context of a specific input xt, denoted as Cpxtq, is the space of samples involved in the calculation of loss. As for in referential games, the cross entropy loss is calculated based on the distance between the message embedding hLpmq and candidate embedding fLcencpxiq where xi P C, thus Cpxtq “ C Ď X in referential games.
Complexity of context: We assume that the goal of communication is to distinguish a target object from other possibilities in the context (as defined above). It therefore follows that the similarity of distractors in the context to the target influences the communicative precision required, and that greater precision is required to distinguish the target from a more similar distractor. For example, it is relatively easy in natural language to distinguish e.g. a cat from a table (a relatively general label like "cat" or "animal" would suffice), but harder to make fine-grained distinctions between very similar objects e.g. a Scottish Fold Cat and an American Shorthair Cat (a specialist vocabulary or a lengthy description is necessary).
Following the assumption (described verbally above) that a context which contains more similar objects makes the game harder because there are fewer unique features which distinguish the target from the distractors, we first define a neighbour set in k-th degree of a given target xt as Nkpxtq “ txj : dpxt,xjq ď kuwhere d is a distance function that can properly capture the similarity between inputs, e.g Hamming distance in our setting. The complexity of Cpxtq is then defined as the expectation of the probability that Cpxtq contains an object from Nkpxtq, i.e.
Ext rg pCpxtq,Nkpxtqqs ,where g pCpxtq,Nkpxtqq “ " 1, if Dxi P Cpxtq s.t. xi P Nkpxtq 0, otherwise (2)
In our referential games, since the sampling procedure is independent Bernoulli without replacement,
the value of the above expectation is then 1´ ´ |X |´1´|Nkpxtq| |X |´1 ¯|C| which is a monotonically increasing function w.r.t |C| and a fixed k (i.e. larger contexts are more complex since they are more likely to include items which are more similar to the target).
Unpredictability of context: Our notion of unpredictability comes from experimental work with human participants, e.g. Winters et al. (2018). Suppose the aim is to distinguish a striped t-shirt from a number of distractors, and there are two sequences of context: i) three runs of games where distractors are all cups; ii) three runs of games where distractors are a cup, a plain t-shirt, and a pencil. In the first sequence of games, participants would become certain that “t-shirt” is enough for distinguishing the target, whereas in the second sequence participants would learn that a more overspecified utterance (e.g. "striped t-shirt") is required to guarantee comprehension after a failure on the trial involving the plain t-shirt distractor. That is, the context in the first sequence is more predictable than the second. Winters et al. (2018) show that human participants are sensitive to this kind of unpredictability, and adapt their communicative strategies accordingly.
In DL-based games, we refer to the context at the e-th trial, i.e. the e-th training epoch, of a target xt as Cepxtq. Following the above example, the unpredictability of context is then defined as the
proportion of Ce`1pxtq that are not from Cepxtq, i.e.
Ext
»
–
1
|Ce`1pxtq| ÿ xjPCe`1pxtq I pxj R Cepxtqq
fi
fl (3)
In referential game, since the sampling procedure is independent Bernoulli without replacement, the proportion of objects not from Cepxtq in Ce`1pxtq is then simply 1´ |C epxtq| |X | “ 1´ |C| |X | (i.e. smaller contexts are more unpredictable, since contexts on successive trials are more likely to differ in their composition).
More details about the above discussion can be found in Appendix B.

heading: 3.2 MEASURING EXPRESSIVITY IN LANGUAGE GAMES

text:
Following the intuition that the different types of games require messages to convey different amount of information about input space X , Mutual Information may seem to be a good candidate measure for expressivity. However, we found that even for two emergent languages that are both deterministic and bijective mapping functions, i.e. they have the same MI value logp|X |q, their expressivity can still be different. Further discussion about MI can be found in Appendix D.
Since it is more challenging to directly quantify the expressivity of emergent languages, we instead focus on the partial orders between them in this work. Considering that the purpose of the emergent communication is to complete tasks, we therefore propose to measure the partial order between expressivity based on game performance. This leads us to a common practice in the transfer learning community (e.g. Pan & Yang, 2009), i.e. train models on source domain but evaluate them on different target domains. Inspired by this practice, here we propose a definition of partial order between the expressivity of two emergent languages LA and LB , i.e. ELA and ELB :
Definition 3.1 (EGLA ą E G LB ). Let g be an instance of language game, and G be a set of language game instances. Then, given G, if the generalisation performance of LA is better than LB on some language games G1, i.e. @g P G1, PgLA ą P g LB , where ∅ Ă G
1 Ď G and P denotes the generalisation performance, while there is no statistically significant difference between the converged generalisation performance of LA and LB on the remaining games, i.e. Pg 1 LA « P g1 LB@g 1 P GzG1 4, we then say that expressivity of LA is higher than LB on G, i.e. EGLA ą E G LB . The metric of generalisation performance could be varied according to different types of games.
Briefly speaking, if one language performs better than the other on some games while they perform approximately the same on the remaining games, we then say the expressivity of that language is higher than the other. Following this definition, there are several possible relationships between the expressivity of two languages LA and LB: 1) EGLA ą E G LB , defined as above; 2) E G LA “ E G LB , if PgLA « P g LB , @g P G; 3) E G LB ą E G LA , defined as above; 4) E G LA is incomparable to E G LB (ELA £ELA), if propositions Dg 1 P G, s.t. Pg 1 LA ą P g1 LB and Dg 2 P G, s.t. Pg 2 LB ą P g2
LA are both true.

heading: 4 PREDICTIONS AND EXPERIMENT DESIGNS

heading: 4.1 PREDICTIONS FROM OUR HYPOTHESIS

text:
It has been shown by Chen et al. (2020a) that harder task can lead to better representation with contrastive loss. By using complexity as a measure for the difficulty of games and treating the emergent language as a special kind of discrete representation, we then have the following prediction:
1. higher complexity in games having same contextual unpredictability can facilitate emergent languages having higher expressivity;
4Note that « in this work means that there is no statistically significant difference between means of two sequences.
Meanwhile, following the hypothesis from Winters et al. (2018) that higher contextual unpredictability leads to higher signal autonomy, i.e. more comprehensive information about input space is encoded in the emergent languages, we then have the following prediction:
2. higher unpredictability in games having same contextual complexity can facilitate emergent languages having higher expressivity;
Following the above two predictions, both higher complexity and higher unpredictability can lead to better expressivity. However, with an input space whose size is finite, changing context size always affects the two factors in an inverse way, which leads to our Hypothesis 1 and gives the following prediction:
3. if the size of X is fixed, a language which emerges in a game with moderate complexity and unpredictability should have the highest expressivity.

heading: 4.2 LANGUAGE TRANSFER EXPERIMENT

text:
To verify the above three predictions and thus our hypothesis, we evaluate the generalisation performance of languages emerging in various games following the procedure outlined in Procedure 1. Briefly speaking, we first train a pair of speaker and listener to complete a referential game, i.e. a “source game” gs, and obtain an emergent language. We then train a new listener in another referential game, i.e. a “target game” gt, with only 90% of the messages, and use the game performance of this listener on the remaining 10% of messages as the generalisation performance of gs on gt.
Procedure 1: Procedure for the language emergence and transfer experiment Input: A set of source game Gs, a set of target game Gt for every game gis in Gs do
1. initialise a new speaker and listener for gis, and train them to play g i s with the whole X ; 2. after the agents converge on gis, record L “ tpx,mq|x P X u; 3. randomly shuffle and split L into 2 disjoint sets Ltrain and Ltest s.t. |Ltrain| “ 90% ¨ |L|; 4. for every game gjt in Gt do
1. initialise a new listener for gjt ; 2. train the listener with Ltrain to complete gjt ; 3. record the accuracy of listener on Ltest as the generalisation performance of gis on gjt ;
end end
Since our hypothesis concerns the size ofC, we propose to experiment on a series of referential games with varying candidate set size |C| (“referX” where X“ |C|). Meanwhile, as these referential games have both different complexity and unpredictability, we also implement a series of referential games with different |C| but the batches are fixed during training such that there is no unpredictability of the context (“referXf” where X“ |C|). To sum up, in our experiment, Gs “ t“refer2/f”, “refer10/f”, “refer100/f”, “refer1000/f”, “refer2500/f”, “refer5000/f”, “refer7500/f”, “refer10000”u5. Since language games with fixed context are not good simulation of human communication , we keep only the ones having varying batches from Gs in Gt. As a naming convention to allow us to refer easily to the factors that influence a language’s expressivity, we refer to emergent languages by their parameters of their source game, e.g. ‘refer10’6 represents the language which emerges in referential games whose |C| “ 10 (with context varying across epochs). More details about the naming of games and languages can be found in Appendix E.1.

heading: 5 RESULTS & DISCUSSION

text:
To alleviate the effect from randomness as much as possible, all the following results are obtained with 6 different random seeds. All values are averaged across the seeds, and the corresponding standard deviation (SD) are also provided (either in this section or appendices).
5There is no “refer10000f” since no unpredictability is possible when |B| “ |C| “ 10, 000 “ |X | 6“referX” is a game while ‘referX’ is an emergent language from it.

heading: 5.1 UNDER FIXED UNPREDICTABILITY, HIGHER COMPLEXITY LEADS TO HIGHER EXPRESSIVITY

text: To verify the Prediction 1, we compare the generalisation performance of games with fixed context, i.e. the unpredictability of their context are the same, on Gt, and the results are shown in Figure 2. Languages which emerge in source games whose contexts have higher complexity consistently perform better on tasks from Gt than those which emerge in source games with lower-complexity contexts, since all lines keep growing with the increase of values on x-axis (i.e. complexity). That is, the generalisation performance is a monotonically increasing function of |C| if there is no unpredictability in the context, which matches with the prediction of our hypothesis.

heading: 5.2 UNDER FIXED COMPLEXITY, HIGHER UNPREDICTABILITY LEADS TO HIGHER EXPRESSIVITY

text: To verify the Prediction 2, we compare the difference between generalisation performance of all games in Gs (“referX”) and their corresponding fixed-batch version (“referXf”). As indicated by that all points in Figure 3 are positive, languages from context with varying objects always perform better than the corresponding fixed-context version on all target games. Since all “referXf” has lower unpredictability of context than the corresponding “referX” games, this indicates that higher unpredictability can unilaterally lead to better generalisation performance of emergent language across various target games, which matches with the prediction of our hypothesis.

heading: 5.3 EXPRESSIVITY IS A TRADE-OFF BETWEEN CONTEXTUAL COMPLEXITY AND UNPREDICTABILITY

text:
To verify the Prediction 3, we compare performance for all source games with varying context on all target games, and the results are shown in Figure 4 (see also Appendix E.3 for more details).
As shown in Figure 4, on whichever type of game, the peak of the curves is always among ‘refer1000’, ‘refer2500’, or ‘refer5000’, which means that the best expressivity always emerges in these 3 types of games. Considering that the complexity of context in referential game is a monotonically increasing function of the |C||X | while the contextual unpredictability is a monotonically decreasing of it, the results shown in Figure 4 support our hypothesis, i.e. the expressivity is a trade-off between the contextual complexity and unpredictability.
To be specific, although context of ‘refer2’, ‘refer10’, and ‘refer100’ have high unpredictability, their complexity is low thus the languages have lower expressivity. On the other hand, context of ‘refer7500’ and ‘refer10000’ have high complexity, but expressivity of neither language is the highest due to the high predictability of the context in these games. Unpredictability of context incentivises the agents to encode more information into the messages such that the messages could overcome the uncertainty of contexts and be interpreted in various contexts. Therefore, the three languages (‘refer1000’, ‘refer2500’, and ‘refer5000’) from context with both moderate complexity and unpredictability perform better than the others. To make it more straightforward to compare the expressivity between these languages, we also provide another view of the above results in Figure 9 in Appendix E.3, which shows that ‘refer1000’ £‘refer2500’ « ‘refer5000’ ą ‘refer7500’ « ‘refer10000’ ą ‘refer100’ ą ‘refer10’ ą ‘refer2’. To eliminate the possibility that the above phenomena are caused by the hyperparameters we used in our games, we also run the language transfer experiment with varying communication channel capacity and agent capacity (i.e. the size of hidden layers). As shown in the figures in Appendix F, both ‘refer1000’ and ‘refer2500’ perform better than ‘refer10000’ across varying hyperparameters, which shows that the trade-off phenomenon is consistent over game settings.

heading: 5.4 THE COLLAPSE OF MESSAGE TYPES

text:
As we use our contrastive loss instead of the conventional referential loss applied by (e.g. Havrylov & Titov, 2017; Ren et al., 2020), we also compare the behaviours of both loss functions on G1s “ G1t “ t“refer2”, “refer10”, “refer100”u. We discover that the number of message types is some times greatly less than the size of input space. We refer such phenomenon as “message type collapse”, and the mappings that maps several different inputs to a same message type as “degeneracy components”.
While comparing the two loss functions, we observe that contrastive loss is more efficient on removing degenerate components in large-scale games (where |C| ě 100), and can better avoid the collapse of the number of message types. To be specific, as shown in Figure 5a, the numbers of message types collapses to less than 500 on games with conventional referential loss. They, however, would only decrease to roughly 5, 000 on ‘refer10’ and ‘refer1000’ with contrastive loss as shown in Figure 5b. The contrastive loss can also make the training of referential game more stable, as illustrated by the smaller variance in Figure 5b.
Our results indicate that it is necessary to establish a referential game with candidate sets containing enough many distractors to guarantee that the emergent language will be relatively unambiguous. As far as we know, the existing works do not investigate the effects of the size of candidate sets, e.g. Lee et al. (2018) set |C| “ 2, Li & Bowling (2019) set |C| “ 5, and |C| ď 20 is used by Lazaridou et al. (2018). Given our results, our heuristic is that |C| should be higher than either 1, 000 for large input spaces or 110 |X | for smaller ones. We also explore more about the degeneracy degree (as well as structure degree) of the mappings constituting different languages, and the results and discussion are provided in Appendix C.

heading: 6 CONCLUSION & FUTURE WORK

text:
To our knowledge, this is the first work exploring the expressivity of emergent languages from language games involving DL-based agents that have different context size. We first proposed a hypothesis about the factors influencing the expressivity of emergent languages, and defined a partial ordering between expressivity of different emergent languages based on the generalisation performance across a set of games. Through a series of experiments on referential games with varying numbers of candidates, we then validated the three predictions from our hypothesis, which furthers indicates that expressivity is indeed a trade-off between the complexity and unpredictability of context in language games. To overcome the memory inefficiency issue caused by the conventional referential loss function, we introduced a contrastive loss into our implementation. In the comparison between this contrastive loss and the referential loss, we found the message type collapse problem, and also showed that using contrastive loss can alleviate this problem.
Since this is a first step towards defining and understanding the expressivity of emergent languages, there are still some questions unanswered by this work. For example, some properties of our emergent languages are surprising given the simplicity of some of our referential games. In the simplest setting (|C| “ 2), we see emergent languages with more than 2, 000 message types, whereas an optimal strategy requires a language consists of only 40 unique messages (since there are only 40 different values for all properties in X and two items in the context always differ on at least one property). Thus, it needs further investigation of how redundancy helps during the communication between agents. More importantly, we lack understanding of the structure of mappings constituting a language, especially when the languages are generated or encoded by neural networks. We believe that the expressivity of languages still needs further exploration in order to maximise the generalisation performance of emergent languages across various tasks.

heading: A MORE DETAILS ABOUT COMPARISON BETWEEN DIFFERENT LOSS FUNCTIONS

text:
In this section, we give more details about the comparison between the referential loss used by previous works and the contrastive loss we propose in Section 2.2.
Following the same notations used in Section 2.2, the referential loss used by (following e.g. Havrylov & Titov, 2017) written as:
ppci|xi,mq9 expEphLm, fpxiqq “ exp ´ hLm J ¨ fpxiq ¯
(4)
where hLm is the embedding for the message m obtained from the sequence encoder of listener L, and fp¨q is encoding function of L for candidates x P C. From the above equation, we can see that if a candidate has an embedding closer to message m, the probability mass for predicting it would then be higher. Hence, the predicated probability mass is inversely proportional to the distances, e.g. the dot product in the above equation, between the embeddings of m and all candidates.
The contrastive loss function proposed by Chen et al. (2020a) with τ “ 1 is given as follow:
`i,j “ ´ exp psimpxi,xjqq ř
k Irk‰is exp psimpxi,xkqq (5)
where I is an indicator function. By comparing the above loss function with Equation 4, we find that the aim of them is the same, i.e. make the distance between positive pairs (targets and their corresponding messages) closer while keeping the embeddings for negative pairs (distractors and the messages) as far apart as possible. While negative sampling has been deeply investigated in the self-supervised learning (SSL) community, (e.g. Chen et al., 2020a;b; Grill et al., 2020), it has not been discussed in the emergent communication community yet, thus we simply use all randomly sampled distractors as negative examples. As mentioned in Section 2.2, we need to make the whole input space as candidate set, thus the above contrastive loss which has lower space complexity is preferred.
In the following, we give a bit further derivation to show that Equation 1 is computationally equivalent to Equation 5. By substituting k in the denominator of Equation 5 with j, we can see that:
`i,j “ ´ log exp psimpxi,xjqq ř
j Irj‰is exp psimpxi,xkqq
“ log ř j Irj‰is exp psimpxi,xkqq exp psimpxi,xjqq “ log ř
j Irj‰is exp psimpxi,xkqq exp psimpxi,xjqq ` log exp psimpxi,xiqq exp psimpxi,xiqq
loooooooooooomoooooooooooon
“0
“ log ř j exp psimpxi,xjqq exp psimpxi,xjqq
“ ´ log exp psimpxi,xjqqř j exp psimpxi,xjqq
(6)

heading: B MORE DETAILS ABOUT CONTEXTUAL COMPLEXITY/UNPREDICTABILITY

text:
In this section, we give more details about the definition of context and its complexity/unpredictability.
B.1 CONTEXT
As defined in Section 3.1, the context for a target object xt is the space of samples involved in the calculation of its loss. We know that the prediction of the listener is calculated based on the distance between the message received (mpxtq) which is a function of the target input (xt), i.e. softmax pd1 pmpxtq,xdqq where xd is a distractor and d1 is a distance function for embeddings.
Cross entropy loss is then calculated based on softmax function. Thus, we can also write the loss function as Lpmpxtq, txdu; θq. As shown in the equation, the calculation is based on samples from candidate set C. Therefore, in referential game, Cpxtq “ txdu “ C Ď X Ă O.
B.2 COMPLEXITY OF CONTEXT
As defined in Section 3.1, the k-th degree neighbour set is Nkpxtq “ txj : ddpxt,xjq ď ku where k P Z`. As described in Section 2.1, there are 4 features in our synthetic data set and each of them can take 10 different values. Therefore, for a specific target xt, the k in the definition of neighbour set can take only the following 4 values:
• k “ 1: samples in N1pxtq differ only in 1 feature from xt. For the only different feature, there are only 9 possible values a distractor can take. Thus, |N1pxtq| “ 4ˆ 9 “ 36.
• k “ 2: samples from N1pxtq and sample that differ at exactly 2 features from xt. For the later case, there are first `
4 2
˘
“ 12 possible combinations of such two features, and there are 9ˆ9 “ 81 possible samples for each combination. Thus, |N2pxtq| “ 12ˆ81`36 “ 1008.
• k “ 3: samples from N2pxtq and sample that differ at exactly 3 features from xt. For the later case, there are first `
4 3
˘
“ 4 possible combinations of such three features, and there are 9 ˆ 9 ˆ 9 “ 729 possible samples for each combination. Thus, |N3pxtq| “ 4ˆ 729` 1008 “ 3924.
• k “ 4: all samples in X except xt are in this neighbour set, thus |N4pxtq| “ 10000´ 1 “ 9999
Since we use independent Bernoulli sampling, for each draw, the probability to get a sample from Nkpxtq is simply Nkpxtq|X |´1 where |X | ´ 1 is due to excluding xt from X . Meanwhile, since we define Cpxtq as the candidate set in referential games. Therefore, for |Cpxtq| “ |C| draws, the probability of having at one sample from Nkpxtq is:
1´ ˆ 1´ |Nkpxtq||X | ´ 1 ˙|C| “ 1´ ˆ |X | ´ 1´ |Nkpxtq| |X | ´ 1 ˙|C| .
B.3 UNPREDICTABILITY OF CONTEXT
In this section, we first give further explanation about Equation 3 and its simplified form. Since we use Bernoulli sampling for each individual object in candidate set, the overall sampling of candidate set is thus a binomial procedure. As the probability of getting a sample from Cepxtq in X is |C epxtq| |X | , the overall proportion of objects from Cepxtq in Ce`1pxtq is the same, i.e. |C epxtq| |X | . Therefore, the probability of the complementary event, i.e. getting an object not from Cepxtq in Ce`1pxtq, is 1´ |C
epxtq| |X | .

heading: C MORE RESULTS AND DISCUSSION ON EXPRESSIVITY

text:
In this section, we provide two more intermediate properties of emergent languages that are also decided by complexity and unpredictability of context, and may influence the expressivity.
C.1 DEGREE OF DEGENERACY AFFECTS BUT DOES NOT FULLY DETERMINE THE EXPRESSIVITY
Inspired by Kirby et al. (2015), the first intermediate factor we explore is the degree of degeneracy (i.e. the degree of ambiguity) of the languages. As a language is defined as a mapping function L : X ÞÑ M, the degree of its degeneracy could be measured by the number of distinct message types.
As shown in the Table 1, in referential languages, the degeneracy degree decreases rapidly with the increase of the contextual complexity of the source games, and reaches a ceiling around |D| ě 1, 000.
There is a positive correlation between the number of message types and expressivity for the languages with low complexity, which indicates that degree of degeneracy could be an intermediate factor that is correlated with the expressivity of these languages. However, the fact that the average number of message types on refer10000 is higher than refer1000, while the expressivity of ‘refer1000’ is higher than ‘refer10000’, i.e. emergent languages having lower level of degeneracy does not necessarily have higher expressivity, indicates that degeneracy degree of one language cannot fully determine its expressivity.
C.2 STRUCTURE DEGREE OF MAPPINGS OF DIFFERENT LANGUAGES
Since the degenerate degree is not the only factor determining expressivity, another factor to be considered is how the mappings of a language L are structured after the training procedure of agents on source games. According to the cardinality of the mappings of L, we can divide them into two disjoint sets: i) one-to-one mappings, i.e. an input is mapped to a unique message; and ii) many-to-one mappings (a.k.a degenerate components), i.e. several inputs are mapped to the same message instance. Between this two types, the structure of one-to-one mappings has been explored under the view of compositionality in the previous works, e.g. (Brighton & Kirby, 2006; Andreas, 2019). However, as illustrated by Chaabouni et al. (2020), a good generalisability does not require a good compositionality, which means that measurements for compositionality are not good predictors for expressivity either. In this work, we only focus on the many-to-one mappings.
Given the objectives of games, for the degenerate components in an emergent language, a message m being mapped to several closely-related inputs could imply that it captures common features among these inputs. Suppose that several inputs XK “ tx1, . . . ,xKu are mapped to the same message m in a converged language L, we hypothesise that the average distances between every pair of messages, e.g. 1|XK | ř
i,jPt1,...,Ku dpxi,xjq, would become smaller after training, compared with their random initial values. Therefore, we compare the averaged distances between meanings of degenerate components as well as the frequency of degenerate components at the beginning and end of training. To make the plots more readable, we only plot the statistics about the top-10 most frequent ambiguous message types, where the frequency of a message type is defined as the number of inputs that are mapped to it in a languages. Results on ‘refer1000’ (one of the most expressive language in our experiments) are shown in Figure 6.
By comparing the data of beginning and end of training in Figure 6b, we can easily observe that the averaged distance decreased throughout the training, which indicates that the degenerate components
actually became more although not fully structured. Another observation we have limited understanding of is that ‘refer1000’ becomes more ambiguous after training (shown by that the red bars representing the statistics at the end of training are lower than the bars representing the statistics at the beginning of training), although its accuracy does improve to 100%. However, limited by the scope of this work, we will leave further exploration of it to future works.

heading: D MUTUAL INFORMATION IS INSUFFICIENT

text:
In Section 3.2, we mentioned that MI cannot completely reflect the expressivity of an emergent language. Here, we provide more detailed explanations. On one hand, a higher MI value does not necessarily mean more task-relevant information, e.g. encoding colour in messages is unnecessary for tasks involving only the shapes of inputs although it provides more information. On the other hand, not only the determinacy of the mappings matters for generalising them, but also the structures, e.g. it would be easier for humans to extrapolate compositional languages to novel concepts than holistic ones although they are both unambiguous and therefore have the same MI. In the following paragraphs, we will give more reasoning and empirical evidence to support our claim.
Following the mapping function definition of emergent languages illustrated in Section 2.1, suppose that we get a message type collection M ĂM in some training epoch, the calculation of the mutual information between M and X is given as follows:
IpM |Xq “ ÿ
xPX
ÿ mPM ppx,mq log ppx,mq ppxqppmq ppx,mq “ 1|X |“ ÿ xPX ÿ mPM1 1 |X | log ppx,mq ppxqppmq
“ 1|X | ÿ
xPX
ÿ
mPM log
ppx,mq ppxqppmq “ 1 |X | ÿ
xPX
ÿ
mPM plog ppx,mq ´ log ppxq ´ log ppmqq
ppxq “ 1|X |“ 1 N ÿ
xPX
ÿ
mPM
ˆ
log 1 |X | ´ log 1 |X | ´ log ppmq ˙ “ 1|X | ÿ
xPX
ÿ
mPM p´ log ppmqq
“ ´ ÿ
mPM log ppmq “ ´
ÿ
mPM log
|Lpmq| |M | “ ´ ÿ
mPM plog |Lpmq| ´ log |M |q
“ ÿ
mPM plog |M | ´ log |Lpmq|q
(7)
where ppxq “ 1|X | as x follows a uniform distribution over the input space, ppx,mq “ 1 |X | since every x is mapped to a message, and |Lpmq| is the appearance number of m in one language. By observing the above equation, it is straightforward to see that the MI value is decided by the number of message types, i.e. the degeneracy degree of one language. Therefore, if two emergent languages have approximately the same number of messages types (as shown in Table 1 and degeneracy degree, the MI values for these two languages should also be the same. However, as we illustrate in Section C.1 that degree of degeneracy cannot fully determine the expressivity of emergent languages, we can then deduce that MI cannot fully measure the expressivity of emergent languages.
To provide more empirical evidence to support our claim, we tracked the MI values over training epochs, and the results are shown in the following Figure 7. As we can see, there is no statistically significant difference between the MI values of ‘referX’ (where Xě 1, 000) while we can show that their expressivity is different in Section 5.3.

heading: E LANGUAGE TRANSFER EXPERIMENT RESULTS

text:
E.1 NAMING OF GAMES AND LANGUAGES
In this section, we give more details about the naming of games and corresponding languages we used in Section 5 as follows:
• “referX”: this refers to the referential games with candidate sets whose size is X (which itself is an integer), note that we use double quotation marks to indicate that this is a specific type of game. For example, “refer2500” refers to referential games with 2, 500 candidates for listeners.
• ‘referX’: this refers to the emergent languages from “referX”, note that we use apostrophes here in order to differentiate it from the notations of the corresponding games. For example, ‘refer2500’ refers to emergent languages from referential games with 2, 500 candidates for listeners.
• “referXf”: this refers to the referential games with candidate sets whose size is X, but the partition of batches is identical over epochs, thus giving the game a fixed context. For example, “refer2500f” refers to referential games with 2, 500 candidates for listeners, but the batches of data are kept identical through the whole training procedure.
• ‘referXf’: this refers to the emergent languages from “referXf”, note that we use apostrophes here in order to differentiate it from the notations of the corresponding games. For example, ‘refer2500f’ refers to emergent languages from referential games with 2, 500 candidates for listeners with fixed context. Regarding the meaning of “fixed-batch” or “fixed context”, we give an example below where the whole input space is ta, b, c, du and batch size is 2:
– varying batch/context: ta, bu, tc, du is the partition for the 1st epoch; then ta, cu, tb, du is used for the 2nd epoch; and random partitions are used in the following epochs;
– fixed batch/context: whichever epoch it is, ta, bu, tc, du is always used as the partition of context;
• “referX/f”: this equals a “referX” and a “referXf”, both of them have same complexity but different unpredictability. To be more specific, contextual unpredictability of “referX” is higher than “referXf”.
• Gs: the universal set of source games which is defined as t“refer2”, “refer10”, “refer100”, “refer1000”, “refer2500”, “refer5000”, “refer7500”, “refer10000”, “refer2f”, “refer10f”, “refer100f”, “refer1000f”, “refer2500f”, “refer5000f”, “refer7500f”, u.
• Gt: the universal set of target games which is defined as t“refer2”, “refer10”, “refer100”, “refer1000”, “refer2500”, “refer5000”, “refer7500”, “refer10000”u.
E.2 RAW RESULTS OF COMPLEXITY EXPERIMENT
In this section, we provide the raw data of Figure 2 in the following Table 3. Not that although “refer1000f” performs the best on “refer10” than all other languages, we argue this outlier doesn’t influence conclusion of our prediction considering the simplicity of “refer10”.
E.3 MORE RESULTS OF TRADE-OFF EXPERIMENT
In this section, we first provide the complete version of Figure 4, i.e. Figure 8. Since the performance of ‘refer2’, ‘refer10’, and ‘refer100’ are too bad on complex target games, it is very clear that their expressivity are much lower that the rest. Therefore, to emphasise the difference between the other languages, we limit the range of y-axis to r0.7, 1.0s in Figure 8. We also illustrate the partial order between the expressivity of different languages in Figure 9. It is very clear that the ‘refer2’, ‘refer10’, and ‘refer100’ performs worse than the others on referential games with more candidates than their sources. Combining this fact with the fact that ‘refer7500’ and ‘refer10000’ perform worse than ‘refer1000’, ‘refer2500’, and ‘refer5000’ shows that increasing the size of candidate set |C| would not always benefit the expressivity. As for ‘refer1000’, ‘refer2500’, and ‘refer5000’, there is no statistically significant difference between their performance on the simpler referential games, and they intersect on some games, thus their expressivity are approximately the same.
At last, we give the precise values of both Figure 9 and 4 in the following Table 4. All the results are obtained by multiple runs, thus both mean and standard deviation (σ) are given.
To better support our claim, we also provide p-values of testing the statistical significance between the generalisation performance of two different source games across all types of target games in the following Table 5.
F VARYING THE CAPACITY OF CHANNEL AND NETWORK
To verify that our findings are robust to the capacity of the communication channel and agents, we also run some extra experiments on the following different configurations of referential games:
1. larger channel capacity: set the length of messages to 8 and size of token inventory to 20, thus the size of message space becomes 208;
2. larger agent capacity: set the hidden layer size to 128, thus the capacity of both speaker and listener become larger than the original setting (256);
3. larger channel&agent capacity: do the above two changes at the same time.
Since our key findings are about the generalisation performance between refer1000, refer2500, and refer10000, we just run these extra experiments on a game set Gextra “ t‘refer1000’, ‘refer2500’, ‘refer10000’u with multiple runs. The results of configuration 1, 2, and 3 are given in Figure 10, 11, and 12 respectively. It can be observed in all figures that ‘refer1000’ or ‘refer2500’ always perform better than ‘refer10000’ on all kinds of target games, i.e. ‘refer1000’
or ‘refer2500’ both have higher expressivity than ‘refer10000’ . Therefore, we believe the key observation from Figure 9 hold for varying configurations of communication channel and capacity of agents, which means that our conclusions are robust to the configuration of language games.


summaries: This paper studies exploration bonus in practical deep RL based on Sample Average Uncertainty (SAU) and upper confidence bound (UCB). SAU is a recently studied novel uncertainty quantification that works for rather arbitrary estimators. Previous paper has studied how to use SAU to derive UCB-type bonus in multi-armed bandits and proved that it could achieve optimal regret.   This paper successfully extends the SAU-UCB-type exploration bonus from bandits settings to RL and most importantly, deep RL settings, and shows how to incorporate SAU-UCB-type bonus in (deep) RL. This paper conducts various experiments for RL and deep RL, demonstrating the advantage of their algorithms over the standard benchmarks.   The paper is generally well-written.

summaries: This work introduces $\delta^2$-exploration for reinforcement learning (RL), which aims to incorporate sample average uncertainty (SAU) into RL exploration. The authors discussed the background and formulation of SAU. The authors further propose $\delta^2$-exploration, which incorporates SAU into Q-learning and compare such exploration with value-uncertainty exploration (UCB-type exploration) and $\epsilon$-greedy. The author then proposes to incorporate $\delta^2$-exploration into DQN and conduct experiments to compare $\delta^2$-exploration with SOTA exploration algorithms. Empirical results show that $\delta^2$-explorations attain comparable results to bootstrapped DQN.

summaries: This paper extends a recently-proposed exploration method called SAU in bandits to the RL problem. They combine this exploration approach with the standard Q-learning algorithm. Their experiments show that this approach can obtain better performance compared with the Q-learning algorithm with eps-greedy exploration.

summaries: The paper extends the recently introduced SAU measure from bandits to RL. The idea is to enhance the exploration of action based on an approximation of the estimation error. More precisely, the bonus is proportional to the average squared temporal difference error. This uncertainty measure is easy to compute and can be integrated into both tabular and continuous methods (e.g., Q-learning and DQN).

abstractText: Effectively tackling the exploration-exploitation dilemma is still a major challenge in reinforcement learning. Uncertainty-based exploration strategies developed in the bandit setting could theoretically offer a principled way to trade off exploration and exploitation, but applying them to the general reinforcement learning setting is impractical due to their requirement to represent posterior distributions over models, which is computationally intractable in generic sequential decision tasks. Recently, Sample Average Uncertainty (SAU) was develop as an alternative method to tackle exploration in bandit problems in a scalable way. What makes SAU particularly efficient is that it only depends on the value predictions, meaning that it does not need to rely on maintaining model posterior distributions. In this work we propose δ-exploration, an exploration strategy that extends SAU from bandits to the general sequential Reinforcement Learning scenario. We empirically study δ-exploration in the tabular as well as in the Deep Q-learning case, proving its strong practical advantage and wide adaptability to complex reward models such as those deployed in modern Reinforcement Learning.

title: Online learning for linearly parametrized control problems

venue: PhD thesis, University of Alberta,

authors:
Yasin Abbasi-Yadkori
David Pal
Csaba Szepesväri

title: Improved algorithms for linear stochastic bandits

venue: In Advances in Neural Information Processing Systems,

authors:
Shipra Agrawal
Navin Goyal

title: Further optimal regret bounds for Thompson sampling

venue: In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics,

title: Using confidence bounds for exploitation-exploration trade-offs

venue: Journal of Machine Learning Research,

authors:
Peter Auer
Nicolo Cesa-Bianchi
Paul Fischer

title: Finite time analysis of the multiarmed bandit problem

venue: Machine Learning,

authors:
Marc G Bellemare
Yavar Naddaf
Joel Veness
Michael Bowling

title: The arcade learning environment: An evaluation platform for general agents

venue: Journal of Artificial Intelligence Research,

authors:
M.G. Bellemare
S. Srinivasan
G. Ostrovski
T. Schaul
D. Saxton
R. Munos

title: Unifying countbased exploration and intrinsic motivation

authors:
Olivier Chapelle
Lihong Li

title: An empirical evaluation of Thompson sampling

authors:
Meire Fortunato
Mohammad Gheshlaghi Azar
Bilal Piot
Jacob Menick
Ian Osband
Alex Graves
Vlad Mnih
Remi Munos
Demis Hassabis
Olivier Pietquin

title: Noisy networks for exploration

venue: arXiv preprint arXiv:1706.10295,

authors:
T. Jaksch
R. Ortner
P. Auer

title: Near-optimal regret bounds for reinforcement learning

authors:
V. Mnih
K. Kavukcuoglu
D. Silver
A.A. Rusu
J. Veness
M.G. Bellemare
A. Graves
M. Riedmiller
A.K. Fidjeland
G. Ostrovski
S. Petersen
C. Beattie
A. Sadik
I. Antonoglou
H. King
D. Kumaran
D. Wierstra
S. Legg
D. Hassabis

title: Human-level control through deep reinforcement learning

authors:
B. O’Donoghue
I. Osband
R. Munos
V. Mnih

title: The uncertainty Bellman equation and exploration

venue: In Proceedings of the 35rd International Conference on Machine Learning,

authors:
I. Osband
D. Russo
B. Van Roy

title: more) efficient reinforcement learning via posterior sampling

venue: In Advances in neural information processing systems,

authors:
I. Osband
C. Blundell
A. Pritzel
B. Van Roy

title: Deep exploration via bootstrapped dqn

authors:
V. Perchet
P. Rigollet

title: The multi-armed bandit problem with covariates

venue: The Annals of Statistics,

authors:
M. Rigotti
R. Zhu

title: Deep bandits show-off: Simple and efficient exploration with deep networks

venue: arXiv preprint arXiv:2105.04683,

authors:
Carlos Riquelme
George Tucker
Jasper Snoek

title: Deep Bayesian bandits showdown: An empirical comparison of Bayesian deep networks for Thompson sampling

venue: In Proceedings of the 6th International Conference on Learning Representations,

authors:
Patt Rusmevichientong
John Tsitsiklis

title: Linearly parameterized bandits

venue: Mathematics of Operations Research,

authors:
D. Russo
B. Van Roy

title: Learning to optimize via information-directed sampling

title: Contextual bandits with similarity information

authors:
A.L. Strehl
M.L. Littman

title: An analysis of model-based interval estimation for Markov decision processes

venue: Journal of Computer and System Sciences,

title: A bayesian framework for reinforcement learning

venue: In Proceedings of the 17th international conference on Machine learning,

authors:
Richard S. Sutton
Andrew G. Barto

title: Reinforcement Learning: An Introduction

venue: The MIT Press, second edition edition,

authors:
H. Tang
R. Houthooft
D. Foote
A. Stooke
X. Chen
Y. Duan
J. Schulman
F. De Turck
P. Abbeel

title: Exploration: A study of count-based exploration for deep reinforcement learning

title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples

authors:
H. van Hasselt
A. Guez
D. Silver

title: Deep reinforcement learning with double Q-learning

venue: In Proceedings of the 30th AAAI Conference on Artificial Intelligence,

title: Learning from Delayed Rewards

venue: PhD thesis, King’s College,

authors:
Z. Wen
B. Van Roy

title: Efficient exploration and value function generalization in deterministic systems

authors:
R. Zhu
M. Rigotti

title: Self-correcting q-learning

venue: arXiv preprint arXiv:2012.01100,

heading: 1 INTRODUCTION

text:
In Reinforcement Learning (RL) an agent interacts with an external environment taking sequences of actions that cause transitions between states of the environment, with the scope to maximize the sum of rewards that are gathered at each state. In a typical scenario, the RL agent does not initially posses perfect knowledge of the consequences of its actions on the environment, but has to learn that through experience. It therefore has to face the classical exploration-exploitation dilemma, i.e. deciding whether to exploit the actions that are known to maximize immediate reward or whether to explore unfamiliar actions and states in order to potentially find ways to increase future rewards.
Efficient exploration requires the agent to quantify the accuracy of its current estimates of the stateaction values (the conditional expected rewards), so as to trade off expected rewards and uncertainty in a principled way (Strehl & Littman, 2008; O’Donoghue et al., 2018). Measuring the uncertainty associated with the value of each state-action is thus a key component of conventional algorithms for addressing the exploration-exploitation dilemma. These ideas have been developed into successful uncertainty-based exploration strategies such as the Upper Confidence Bound (UCB) algorithm, which quantifies uncertainty through confidence intervals (Auer et al., 2002), and Thompson Sampling (TS), which instead models the posterior distribution over values (Thompson, 1933). However, obtaining either of these measures of uncertainty for general sequential Reinforcement Learning problems has proven arduous because of their reliance on a measure of uncertainty around the current value predictions, which is typically infeasible to obtain for complex environments and value functions. This difficulty limits the applicability of explorations strategies based on UCB and TS for general RL problems, compromising in particular their adaptability to algorithms such as Q-learning (Watkins, 1989; Watkins & Dayan, 1992) and DQN (Mnih et al., 2015), which consequently typically resort to addressing exploration via inefficient heuristics like -greedy action selection.
Recently, Rigotti & Zhu (2021) tackled the mentioned limitations of conventional exploration strategies in the constrained but interesting case of bandit problems. Central to that effort was the development of a novel uncertainty measure, the Sample Average Uncertainty (SAU), which departs from the approach of estimating the uncertainty of expected rewards of selected actions. In contrast to what is done in UCB and TS, SAU is an uncertainty measure that only depends on the value prediction of each action. Specifically, it consists in quantifying the variance of sample averages of rewards under the assumption of known values, which can be used to simply construct an estimated
variance by plugging in the estimated values. Finally, Rigotti & Zhu (2021) were able to use SAU to developed two SAU-based exploration strategies, SAU-UCB and SAU-Sampling, which were shown to display state-of-the-art performance in multi-armed bandits, contextual bandit, and deep bandits.
In this work, we exploit the simplicity of SAU in Rigotti & Zhu (2021) and extend it from the bandits to the more general sequential RL setting. This extension results in δ2-exploration, a class of exploration strategies for RL which share the implementation simplicity of SAU for bandits as well as its effectiveness. Our δ2-exploration algorithms are implementable with a minimal computational overhead that is comparable to -greedy exploration, while being empirically more effective.
As a practical demonstration, we apply δ2-exploration to Q-leaning (Watkins, 1989). We then show that the resulting strategies display empirically efficient exploration, which very quickly reach near optimal policies. As mentioned, in terms of computation and memory requirements, these exploration strategies do not add any additional cost compared to for instance a simple -greedy action selection strategy. Finally, we apply SAU-based exploration to Deep Q Networks (DQN), and observe convincing performance gains over standard DQN in several games we tested from the Atari 2600 domain.
Thanks to its efficiency, flexibility and implementation simplicity, we argue that δ2-exploration could serve as a competitive baseline and as a simple and straight-forward replacement to -greedy action selection in a wide class of RL scenarios.
In the remainder of this paper, Section 2 summarizes common exploration strategies in bandits and Reinforcement Learning in order to set the stage for δ2-exploration. Section 3 establishes the notation and states the problem. Section 4.2 presents the SAU measure, and summarized SAUbased exploration strategies in the setting of multi-armed bandits as developed in Rigotti & Zhu (2021). In Section 5 we then extend these strategies to the sequential RL setting and develop δ2exploration. Section 6 includes empirical evaluations showing substantial performance improvements over conventional exploration strategies in Q-learning and DQN. Section 7 concludes the paper.

heading: 2 RELATED WORK

text:
The most common exploration strategy in Reinforcement Learning (RL) is arguably -greedy action selection, which consists in following the action with the highest estimated value with high probability, but occasionally with a small fixed probability choosing any other available action uniformly at random. Despite the clear inefficiency of not differentiating lower value actions based on their uncertainty or even their value, because of its simplicity -greedy action selection is still the exploration strategy of choice in RL.
One of the most popular and efficient exploration algorithms is the Upper Confidence Bound (UCB) algorithm, which is very successful in the bandit setting (Auer et al., 2002; Auer, 2003; Rusmevichientong & Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011; Abbasi-Yadkori, 2012; Perchet & Rigollet, 2013; Slivkins, 2014). This approach is based on the principle of optimism in the face of uncertainty, which elegantly addresses the exploration-exploitation trade-off by maintaining confidence intervals for action-value estimates and choosing actions optimistically within these intervals. Unfortunately, UCB is difficulty to apply to RL problems on complex domains (Jaksch et al., 2010; Wen & Van Roy, 2013) due to the complexity of computing its uncertainty measure.
A related class of strategies to UCB are count-based methods (Strehl & Littman, 2008; Bellemare et al., 2016) that directly turn the counts of state-action visitations into reward bonuses to encourage the exploration of less visited ones. Despite performing near-optimally for small discrete Markov decision processes, count-based methods suffer the curse of dimensionality in high-dimensional environments (although see Tang et al. (2017) that proposed a possible high-dimensional extension using learned hashing to discretize the state space).
Another popular exploration strategy is Thompson Sampling (TS) which was introduced by Thompson (1933). This is a Bayesian approach that follows the principle of sampling in the face of uncertainty, i.e. it samples action-values from a known posterior distribution, then selects the action with the highest sampled value. TS has been successfully applied in bandit settings (Chapelle & Li, 2011; Agrawal & Goyal, 2013; Russo & Van Roy, 2014). It has also been applied to simple Reinforcement Learning problems (Strens, 2000; Osband et al., 2013). However, because calculating the posterior
distributions over values is intractable in the general case, implementations of TS in even moderately sophisticated domains require the application of posterior approximation methods, like for instance in Osband et al. (2016), which, at least in the contextual bandit setting, are known to be inefficient (see Riquelme et al. (2018)).

heading: 3 PROBLEM FORMULATION

text:
We recall the definition of a Markov Decision Process (MDP) as a set of states S and actionsA so that, given a current state s ∈ S and an action a ∈ A, the probability of ending up in the next state s′ ∈ S is Pss′(a), where P : S×A×S → [0, 1] is a fixed state transition distribution with ∑ s′ Pss′(a) = 1. Moreover, the reward r is drawn from a reward distribution with E[r|s, a, s′] = Rss′(a). The optimal value function Q∗(s, a) solves an MDP by satisfying the following set of Bellman equations for a given discount factor γ ∈ [0, 1):
Q∗(s, a) = ∑ s′ Pss′(a) [ Rss′(a) + γ max a′∈A Q∗(s′, a′) ] ∀s, a.
MDPs can be solved using Q-learning (Watkins, 1989). Let Q(s, a) be the current estimate of the value of action a in state s, and let s′ be the state that follows s upon taking a, and r be the corresponding reward. Then Q-learning consists in updating the action-value function using a learning rate α as follows:
Q(s, a)← Q(s, a) + α [ r + γ max
a′∈A Q(s′, a′)−Q(s, a)
] .
In this update rule, Q-learning uses the max operator as an estimate the value of the next state. The term in the squared brackets
δ = r + γ max a′∈A Q(s′, a′)−Q(s, a) (1) is known as the TD-error, because it is a generalization of the reward prediction error in the case of a Temporal-Difference learning algorithm.
A last element that is crucial for the Q-learning algorithm to converge to the optimal value function is exploration. That is why Q-learning is typically implemented in combination with -greedy action selection, a simple and rather successful exploration strategy proposed in Sutton & Barto (2018) that prescribes to fix a small probability and choose an action at time t as follows:
at = { a ∈ A uniformly at random, with probability ; a∗ = arg maxa∈A {Q(st, a)} , with probability 1− .
(2)
As mentioned in the previous section, -greedy exploration has the obvious inefficiency that, during an exploratory event of probability , actions are selected without differentiating on their uncertainty or even their value. But because of its simplicity -greedy action selection is typically the exploration strategy of choice in many successful RL applications, such as Mnih et al. (2015).

heading: 4 SAMPLE AVERAGE UNCERTAINTY FOR CONTEXTUAL BANDITS

text: The Sample Average Uncertainty (SAU) is a measure of uncertainty that was recently proposed as a simple and scalable mechanism to promote exploration in the bandit setting (Rigotti & Zhu, 2021). For ease of exposition we introduce SAU from the contextual bandit perspective and notation.

heading: 4.1 CONTEXTUAL BANDITS

text: In contextual bandits at each step t the agent observes a context vector st ∈ X , selects an action at from a set A, after which a reward rt corresponding to the chosen action is received. The value of an action a in context st is defined as the expected reward given that a is selected, and is assumed to be a fixed but unknown function of st and a: E[rt|at = a] = µ(st, a). The goal is to design a decisionmaking policy π : X → A that maximizes the expected reward. This goal is readily quantified in terms of minimizing expected regret, where, if action at is chosen at step t after observing context st, we say that we incur expected regret maxa′∈A{µ(st, a′)} − µ(st, at), which is the difference between the optimal value received by playing the optimal action and the value received following the chosen action.

heading: 4.2 SAMPLE AVERAGE UNCERTAINTY EXPLORATION IN BANDITS

text:
Let Ta denote the set of time steps when action a was chosen so far, and let n(a) be the size of this set. Assume there is a sequence of estimators {µ̂(st, at)}t∈Ta of µ(s, a). The Sample Average Uncertainty (SAU (Rigotti & Zhu, 2021)) statistic τ(a)2 is defined as
τ(a)2 = 1
n(a) ∑ t∈Ta e2t with et = rt − µ̂(st, at). (3)
Obviously, computing the SAU measure only requires the prediction residuals et = rt − µ̂(st, at), without any need to model or access the uncertainty of µ̂(st, at).
Reference Rigotti & Zhu (2021) combined this uncertainty measure with UCB and Posterior Sampling exploration and proposed two exploration strategies for contextual bandits named SAU-UCB and SAU-Sampling.
SAU-UCB. SAU-UCB (Rigotti & Zhu, 2021) consists in the use the SAU uncertainty measure τ(a)2 as the exploration bonus in the principle of “optimism in the face of uncertainty”. This works as follow: given value predictions µ̂(st, a) at step t, define Y (st, a) = µ̂(st, a) + √ n(a)−1τ(a)2 log t, where n(a) is the times action a was taken. Then choose the action by maximizing over that: at = arg maxa∈A {Y (st, a)}.
SAU-Sampling. Thompson Sampling (TS) promotes exploration by sampling value estimates from a modelled posterior distribution. The SAU-Sampling algorithm (Rigotti & Zhu, 2021) also adopts this principle of “sampling in the face of uncertainty”, but unlike TS it does so by sampling values from a parametric Gaussian distribution with a mean given by the prediction and a variance proportional to τ(a)2, resulting in values Y (st, a) ∼ N ( µ̂(st, a), τ(a) 2/n(a) )
from which then an action is again selected by maximization: at = arg maxa∈A {Y (st, a)}. In summary, in contrast to uncertainty-based exploration strategies like UCB and TS that first measure the uncertainty of the action-value estimates µ̂(s, a) given the past observations, SAU-based exploration directly quantifies the uncertainty associated with each action through equation 3 by measuring the uncertainty of the sample average rewards. The clear advantage of this procedure is that it is much simpler and more computationally efficient, while at the same time providing the same quality of uncertainty estimates, and often even better exploration than the more complex algorithms that rely on estimating the uncertainty of the action-value function (see empirical results in (Rigotti & Zhu, 2021)).
5 δ2-EXPLORATION: SAU-BASED EXPLORATION FOR SEQUENTIAL RL
The SAU-exploration algorithms summarized in the previous section have been shown to be very effective exploration strategies despite their low computation footprint in the contextual bandit setting, including the deep contextual bandit case where the reward is being parametrized by a deep neural network (Rigotti & Zhu, 2021). We now propose an extension of SAU to adapt it from the bandit to the sequential reinforcement learning scenario. We call the resulting class of exploration algorithms δ2-exploration.
5.1 δ2-EXPLORATION IN Q-LEARNING
Contextual bandits are essentially simplified MDPs with horizon 1, so that each episode only consists of one state observation (which in contextual bandits is called “context”), an action and a reward, after which the environment is reset. Because of this relationship, the first step to extend results in bandits to sequential reinforcement learning is to substitute the bandit feedback rt in equation 3 with the multi-step cumulative return Gt, defined as Gt = ∑T−t−1 k=0 rt+k+1 in the case of episodic
tasks or Gt = ∑∞ k=0 γ
krt+k+1 with discount rate γ in the case of infinite horizon tasks. The value prediction terms, µ(s, a) in equation 3 correspond in a sequential RL setting to the state-action value qπ(s, a) under some policy π, and can therefore be substituted with Q(s, a), its current estimate at a given time.
At this point, we notice that Q-learning uses a target to approximate the cumulative return Gt with the one-step iteration rt+1 + γmaxa′ Q (st+1, a′) (Sutton & Barto, 2018), and we can therefore use the same approximation in our extension of SAU from bandits to sequential RL.
Note that the SAU measure is not a function of the current context st but just depends on action a. A key mechanism explaining why this simple method works is the assumption that the noise in each arm is homogeneous. This is a good approximate description of the data-generating process underlying complicated reward models such as deep neural networks, in particular when there wouldn’t anyway be enough data to provide an accurate fit of uncertainty as a function of context. In sequential RL, the reward models might indeed be complicated, which bodes well for applying the SAU measure in this setting, especially in the deep RL case.
We now have everything to formulate the sequential RL version of the SAU uncertainty measure τa in equation 3 that we call δ2-uncertainty:
∆2(a) = 1
n(a) ∑ t∈Ta δ2(st, at), (4)
where δ(st, at) denotes the TD-error in equation 1 at an observed sequence st, at, rt+1, st+1, i.e.:
δ(st, at) = rt+1 + γ max a′∈A
Q (st+1, a ′)−Q(st, at),
and the sum in equation 4 is over the set Ta of time steps when action a was chosen up until the current time, and n(a) denotes the number of times that the action a was observed.
In practice, ∆2(·) in equation 4 can be efficiently computed by incrementally updating a running estimate that accumulates the TD-error:
∆2(a)← ∆2(a) + [ δ2(s, a)−∆2(a) ] /n(a). (5)
Comparing the derived expression equation 4 for the δ2-uncertainty ∆2 with the definition equation 3 of the SAU measure τa solidifies the intuition that the role played by the prediction residual et in equation 3 for the bandit feedback is naturally taken up by the TD-error δ(st, at) in sequential RL.
As in the case of SAU-based exploration in bandit problems, once the δ2-uncertainty is available it can simply be plugged into the action selection process to implement a class of exploration algorithms that we call δ2-exploration. The δ2-exploration algorithm that is obtained by using the δ2-uncertainty as in UCB will be called δ2-UCB. Analogously, the δ2-exploration algorithm obtained by combining the δ2-uncertainty with sampling-based exploration will be called δ2-Sampling.
More specifically, given action-valuesQ(st, a) at a given state st at time t, δ2-exploration implements exploration by “perturbing” action-values Q̃(st, a) according to one of the following schemes, depending on which specific exploration algorithm we want to use:
1. δ2-UCB: Q̃(st, a) = Q(st, a) +
√ ∆2(a) log t
n(a) ∀a ∈ A;
2. δ2-Sampling: Q̃(st, a) ∼ N ( Q(st, a), ∆2(a)
n(a)
) ∀a ∈ A.
Then an action is selected by maximization: at = arg maxa∈A { Q̃(st, a) } .
The two δ2-exploration algorithms δ2-UCB and δ2-Sampling are detailed in Algorithm 1.
5.2 COMPARISON BETWEEN VALUE UNCERTAINTY EXPLORATION AND δ2-EXPLORATION
Let us take a moment to compare the functioning of δ2-exploration to conventional exploration strategies based on estimating uncertainty of value estimates, such as UCB and posterior sampling (Thompson Sampling) methods. We call these methods “value uncertainty exploration methods” because the mechanism that they use to promote exploration relies on quantifying the uncertainty of the current value function estimates. Maintaining this “internal uncertainty” measure is typically
Algorithm 1 δ2-exploration in Q-learning. Parameters: step size α ∈ (0, 1], discount factor γ ∈ (0, 1], and β ≥ 1. Initialize: Q(s, a) such that Q(terminal, ·) = 0, ∆2(a) = 0, and n(a) = 1 for all a ∈ A. for all episodes do
Initialize state s while s in episode is not terminal do
(1) Use δ2-exploration strategy (a) or (b):
(a) δ2-UCB: Q̃(s, a) = Q(s, a) +
√ ∆2(a) log ∑ a n(a)
n(a) ;
(b) δ2-Sampling: Q̃(s, a) ∼ N ( Q(s, a), ∆2(a)
n(a)
) .
(2) Select a in state s: a = arg maxa′∈A{Q̃(s, a′)} n(a)← n(a) + 1. (3) Take action a, observe r, s′.
(4) Update Q(·) and ∆2(·): δ(s, a) = r + γmax
a′ Q (s′, α)−Q(s, a)
Q(s, a)← Q(s, a) + α · δ(s, a) ∆2(a)← ∆2(a) + ( δ2(s, a)−∆2(a) ) /n(a).
(5) Step to next state: s← s′ end while
end for
computationally costly, to the point of being computationally intractable for large state spaces. Thompson Sampling in particular assumes a prior distribution over value functions that is updated based on observed transitions, a process that is only feasible for simple environments.
In contrast, rather than maintaining the internal uncertainty of value function estimates, δ2-exploration simply updates its propensity for exploration by accumulating the reward prediction error δ as in equation 5. In other words, δ not only has a role in policy evaluation by representing the extent to which the value function should be update, but also has a role in the control policy by representing the extent to which exploration is needed to prevent the policy from being suboptimal.
Figure 1 gives a schematic overview of the difference between value uncertainty exploration methods and our proposed method δ2-exploration, emphasizing the simplicity of δ2-exploration whose exploration mechanism does not need to rely on estimating the distributional uncertainty over the value function, but only needs access to the reward prediction error δ to compute the δ2-uncertainty ∆.
Once the δ2-uncertainty ∆ is available, it is directly passed to the action selection step (see step (2) in Algorithm 1). This means that the δ2-uncertainty, besides being cheap to compute, is also simple to use to instantiate the exploration mechanism: it is simply used to “perturbe” the estimated action-values (either as an exploration bonus in the case of δ2-UCB or as sampling noise in the case of δ2-Sampling) before greedily selecting the next action. This underscores that from a computational standpoint the action selection process of δ2-exploration is as simple as -greedy action selection (equation 2). Indeed, δ2-exploration inherits this trait from SAU-exploration (Rigotti & Zhu, 2021), and similarly to that algorithm can be used as a flexible drop-in replacement for -greedy selection.
5.3 δ2-EXPLORATION IN DEEP Q-LEARNING
Deep Q-learning consists in parameterizing the action-value functionQ(s, a) as a deep neural network, i.e. a Deep Q Network (DQN) policy network (Mnih et al., 2015). Because of the complexity of such an action-value function, it is notoriously difficult to implement efficient exploration strategies in DQN. As a result, dithering heuristics such as -greedy are commonly used in practice. Fortunately,
Environment
Agent
value function
exploration
r as
uncertainty
Environment
Agent
value function
exploration
r as (a) Value uncertainty exploration (b) d2-exploration Figure 1: (a) Value uncertainty exploration algorithms like UCB and Thompson Sampling rely on an estimate of the uncertainty of the current value function, a quantity that is intractable already for moderately complex value functions and environments. (b) δ2-exploration on the other hand only needs access to the reward prediction error δ to compute how to select an action that trades off exploration and exploitation in a principled way.
δ2-exploration just depends on the prediction of the value function, so it is versatile enough to be easily applicable to DQN.
A direct way to combine δ2-exploration with DQN would be to implement Algorithm 1 using a deep neural network (in addition to the policy network) that would fit the δ2-exploration measure ∆. To avoid the computational and memory overhead of an additional network we took inspiration from recent papers that harnessed the target network in DQN (a delayed parameter version of the policy net used in Mnih et al. (2015) to stabilize training) in order to implement unbiased estimators of the value (van Hasselt et al., 2016; Zhu & Rigotti, 2020). We reasoned that the difference between the online policy net Q(s, a) and the delayed parameter target net Q−(s, a) should reflect a minimization of the reward prediction error. This suggests to replace the expression equation 4 with the following expression for the δ2-uncertainty ∆:
∆2dqn(s, a) = (
max a′
Q(s, a′)−Q−(s, a) )2 .
We propose to use this variation of the δ2-uncertainty to implement the DQN version of δ2-exploration algorithms δ2-UCB and δ2-Sampling. Using δ2-exploration in DQN therefore comes down to implementing DQN learning as usual (see e.g. Mnih et al. (2015)), except that the action selection part of the algorithm (which typically would use -greedy action selection) is replaced as in Algorithm 2.
Algorithm 2 δ2-exploration in Deep Q-Networks. 1: Initialize: Regular DQN (Mnih et al., 2015) with policy network Q(s, a), target network Q−(s, a), and global action counts n(a) initialized at 1 for all a ∈ A.
2: Replace action selection ACT(·) in regular DQN with:
3: function ACT-δ2-EXPLORATION(s) 4: for a = 1, . . . , |A| do
5: (1) Compute ∆2dqn(s, a) = (
max a′
Q(s, a′)−Q−(s, a) )2
6: (2) Use δ2-exploration strategy (a) or (b):
7: (a) δ2-UCB: Q̃(s, a) = Q(s, a) +
√ ∆2dqn(s, a) log ∑ an(a)
n(a) ;
8: (b) δ2-Sampling: Q̃(s, a) ∼ N ( Q(s, a), ∆2dqn(s, a)
n(a)
) .
9: end for 10: Select action a∗ = arg maxa∈A{Q̃(s, a)}. 11: Update global count n(a∗)← n(a∗) + 1. 12: Return action a∗ 13: end function

heading: 6 EMPIRICAL RESULTS

text:
We now empirically evaluate the performance of our proposed δ2-exploration strategies in a series of reinforcement learning tasks, including classical tabular Q-learning and Deep Q Learning tasks.
We will benchmark δ2-exploration against -greedy action selection, the de facto go-to exploration strategy in Q-learning, and also the closest exploration strategy in terms of computational and implementation efficiency. In fact, we propose δ2-exploration as a flexible drop-in replacement for -greedy action selection that we now demonstrate is remarkably more efficient, despite being comparably simple in terms of computation and implementation complexity.
6.1 Q-LEARNING ON CLIFF-WALKING TASK
= 1/
√
n(s), where n(s) is the number of times state s has been visited. Learning rate is set to αn(s, a) = 0.1(100+1)/(100+n(s, a)), where n(s, a) is the number of updates of each state-action. Data points are averaged over 1000 runs.
We evaluate the performance of δ2-exploration on the cliff-walking task (Example 6.6 in Sutton & Barto (2018)), a standard undiscounted episodic task with start and goal states, and four movement actions: up, down, right, and left. Reward is −1 on all transitions except those into the “Cliff” region (bottom row except for the start and goal states). If the agent steps into this region, she gets a reward of −100 and is instantly sent back to the start. We vary the environment size by considering 10× 5 and 20× 5 grids. We measure performance as cumulative reward during episodes, and report average values for 1000 runs and standard deviation of values of the final episode in Fig. 2. We compare our two proposed δ2-exploration δ2-UCB and δ2-Sampling against -greedy action selection with = 1/ √ n(s). As Fig. 2 shows the δ2-exploration strategies perform much better than -greedy, quite quickly attaining near optimal values (the reard value indicated by the black dotted lines in the plot). We also compute the standard deviation of rewards of the final rewards of 1000 runs, which show that δ2-exploration strategies display much lower variability (i.e. are more stable) than -greedy action selection.

heading: 6.2 DEEP Q NETWORK ON THE ATARI 2600 DOMAIN

text:
As a final empirical validations for δ2-exploration we study the performance of our DQN adaptation Algorithm 2 on 8 representative games from the Atari 2600 domain (Bellemare et al., 2013). We choose 4 “easy” games for which DQN displays super-human performance, and 4 “hard” games for which DQN performs around or below humans. We compared the performance of the δ2-exploration algorithms with the conventional -greedy action selection that consists of annealing for the first 1M steps from 1.0 linearly to F = 0.1, noisy nets (Fortunato et al., 2017) and Bootstrapped DQN (Osband et al., 2016), a strong baseline, but which requires a form of ensembling resulting in considerable memory overhead. Fig. 3 compares the performance at the end of training for -greedy, Bootstrapped DQN, noisy nets and our δ2-exploration algorithms. The advantage of δ2-exploration is particularly remarkable for harder games, and in particular MsPacman, where our algorithms finds
policies that reach scores that are almost double what the other competitors reach, and Centipede, where δ2-Sampling vastly outperforms even Bootstrapped DQN.

heading: 7 CONCLUSIONS AND DISCUSSION

text:
Here we extended Sample Average Uncertainty, a recently proposed uncertainty measure for exploration, from bandit problems to the general sequential reinforcement learning setting. This resulted in our δ2-exploration algorithms, two exploration strategies that are extremely simple and flexible to implement, as they only depend on the predicted action-values. These can be used as drop-in replacements for -greedy action selection in Q-learning and DQN, resulting in effective and computationally efficient learning and superior empirical performance over the -greedy baseline.
Our work provides a simple, scalable and robust exploration algorithms, that can be effortlessly deployed to mitigate the exploration-exploitation dilemma. While the resulting consequences of the deployment of an RL algorithm, ethical or otherwise, will clearly depend on the specific applications, we believe that providing efficient uncertainty estimates and more reliable exploration than the common -greedy action selection strategy will potentially have a positive contribution in terms of sample-efficiency and optimality of the learned policies, as well as in terms of their trustworthiness.
We limited our experiments to comparisons against -greedy exploration, given its importance and ubiquity, and because our method was developed specifically as a natural drop-in replacement for -greedy exploration. Our δ2-exploration algorithms have in fact a comparably low computation footprint and can be implemented through a minimal API that is the same as for -greedy exploration, only needing to access the action selection process of the RL agent. This enables modular implementations with minimal change on existing RL code bases, as for instances exemplified by the DQN version of δ2-exploration in Algorithm 2, which simply consists in the replacement of the action selection method in a conventional DQN with no modification of the training algorithm. This is in stark contrast with previous exploration strategies based on quantifying value uncertainty, which typically impose limitations on the representation of the value function, need to heavily modify the evaluation process, and introduce costly training loops to update the value uncertainty.
That said, the remarkable performance of our simulation results and the flexibility of δ2-exploration suggest that it could be applied to even more sophisticated RL settings and possibly combined with other learning algorithms besides Q-learning and DQN, an option that we are looking forward to investigating in the future.
REPRODUCIBILITY STATEMENT
We provide detailed pseudo-code of our proposed algorithms and tried our best to indicate important hyperparameters to replicate our experiments and reproduce our benchmarks, which are anyway based on tasks that are already publicly available. In addition, upon acceptance of our paper, we plan to release the code to replicate all our numerical experiments on github.