\documentclass[letterpaper]{article} % DO NOT CHANGE THIS
\def\year{2021}\relax
%File: formatting-instructions-latex-2021.tex
%release 2021.1

%Added by Zidong
\usepackage{color}
\newcommand{\rmk}[1]{\textcolor{red}{--[#1]--}}
\newcommand{\note}[1]{\textcolor{red}{#1}}
\usepackage{enumitem}

\usepackage{aaai21}  % DO NOT CHANGE THIS
\usepackage{times}  % DO NOT CHANGE THIS
\usepackage{helvet} % DO NOT CHANGE THIS
\usepackage{courier}  % DO NOT CHANGE THIS
\usepackage[hyphens]{url}  % DO NOT CHANGE THIS
\usepackage{graphicx} % DO NOT CHANGE THIS
\urlstyle{rm} % DO NOT CHANGE THIS
\def\UrlFont{\rm}  % DO NOT CHANGE THIS
\usepackage{natbib}  % DO NOT CHANGE THIS AND DO NOT ADD ANY OPTIONS TO IT
\usepackage{caption} % DO NOT CHANGE THIS AND DO NOT ADD ANY OPTIONS TO IT
\frenchspacing  % DO NOT CHANGE THIS
\setlength{\pdfpagewidth}{8.5in}  % DO NOT CHANGE THIS
\setlength{\pdfpageheight}{11in}  % DO NOT CHANGE THIS
\usepackage{algorithm}  
\usepackage{algorithmic} 
%\nocopyright
%PDF Info Is REQUIRED.
% For /Author, add all authors within the parentheses, separated by commas. No accents or commands.
% For /Title, add Title in Mixed Case. No accents or commands. Retain the parentheses.
\pdfinfo{
/Title (Characterization Capacity of Agents and Compositionality from Naturally Emergent Communication)
/Author (AAAI Press Staff, Pater Patel Schneider, Sunil Issar, J. Scott Penberthy, George Ferguson, Hans Guesgen, Francisco Cruz, Marc Pujol-Gonzalez)
/TemplateVersion (2021.1)
} %Leave this
% /Title ()
% Put your actual complete title (no codes, scripts, shortcuts, or LaTeX commands) within the parentheses in mixed case
% Leave the space between \Title and the beginning parenthesis alone
% /Author ()
% Put your actual complete list of authors (no codes, scripts, shortcuts, or LaTeX commands) within the parentheses in mixed case.
% Each author should be only by a comma. If the name contains accents, remove them. If there are any LaTeX commands,
% remove them.

% DISALLOWED PACKAGES
% \usepackage{authblk} -- This package is specifically forbidden
% \usepackage{balance} -- This package is specifically forbidden
% \usepackage{color (if used in text)
% \usepackage{CJK} -- This package is specifically forbidden
% \usepackage{float} -- This package is specifically forbidden
% \usepackage{flushend} -- This package is specifically forbidden
% \usepackage{fontenc} -- This package is specifically forbidden
% \usepackage{fullpage} -- This package is specifically forbidden
% \usepackage{geometry} -- This package is specifically forbidden
% \usepackage{grffile} -- This package is specifically forbidden
% \usepackage{hyperref} -- This package is specifically forbidden
% \usepackage{navigator} -- This package is specifically forbidden
% (or any other package that embeds links such as navigator or hyperref)
% \indentfirst} -- This package is specifically forbidden
% \layout} -- This package is specifically forbidden
% \multicol} -- This package is specifically forbidden
% \nameref} -- This package is specifically forbidden
% \usepackage{savetrees} -- This package is specifically forbidden
% \usepackage{setspace} -- This package is specifically forbidden
% \usepackage{stfloats} -- This package is specifically forbidden
% \usepackage{tabu} -- This package is specifically forbidden
% \usepackage{titlesec} -- This package is specifically forbidden
% \usepackage{tocbibind} -- This package is specifically forbidden
% \usepackage{ulem} -- This package is specifically forbidden
% \usepackage{wrapfig} -- This package is specifically forbidden
% DISALLOWED COMMANDS
% \nocopyright -- Your paper will not be published if you use this command
% \addtolength -- This command may not be used
% \balance -- This command may not be used
% \baselinestretch -- Your paper will not be published if you use this command
% \clearpage -- No page breaks of any kind may be used for the final version of your paper
% \columnsep -- This command may not be used
% \newpage -- No page breaks of any kind may be used for the final version of your paper
% \pagebreak -- No page breaks of any kind may be used for the final version of your paperr
% \pagestyle -- This command may not be used
% \tiny -- This is not an acceptable font size.
% \vspace{- -- No negative value may be used in proximity of a caption, figure, table, section, subsection, subsubsection, or reference
% \vskip{- -- No negative value may be used to alter spacing above or below a caption, figure, table, section, subsection, subsubsection, or reference

\setcounter{secnumdepth}{0} %May be changed to 1 or 2 if section numbers are desired.

% The file aaai21.sty is the style file for AAAI Press
% proceedings, working notes, and technical reports.
%

% Title

% Your title must be in mixed case, not sentence case.
% That means all verbs (including short verbs like be, is, using,and go),
% nouns, adverbs, adjectives should be capitalized, including both words in hyphenated terms, while
% articles, conjunctions, and prepositions are lower case unless they
% directly follow a colon or long dash

\title{Enabling the Emergence of Symbolic Language without Handcrafted Inductions}
\author{
    %Authors
    % All authors must be in the same font size and format.
    %Written by AAAI Press Staff\textsuperscript{\rm 1}\thanks{With help from the AAAI Publications Committee.}\\
    %AAAI Style Contributions by Pater Patel Schneider,
    %Sunil Issar,  \\
    %J. Scott Penberthy,
    %George Ferguson,
    %Hans Guesgen,
    %Francisco Cruz,
    %Marc Pujol-Gonzalez
    %\\
}
\affiliations{
    %Afiliations

    %\textsuperscript{\rm 1}Association for the Advancement of Artificial Intelligence\\
    %If you have multiple authors and multiple affiliations
    % use superscripts in text and roman font to identify them.
    %For example,

    % Sunil Issar, \textsuperscript{\rm 2}
    % J. Scott Penberthy, \textsuperscript{\rm 3}
    % George Ferguson,\textsuperscript{\rm 4}
    % Hans Guesgen, \textsuperscript{\rm 5}.
    % Note that the comma should be placed BEFORE the superscript for optimum readability

    %2275 East Bayshore Road, Suite 160\\
    %Palo Alto, California 94303\\
    %% email address must be in roman text type, not monospace or sans serif
    %publications21@aaai.org

    % See more examples next
}
\iffalse
%Example, Single Author, ->> remove \iffalse,\fi and place them surrounding AAAI title to use it
\title{My Publication Title --- Single Author}
\author {
    % Author
    Author Name \\
}

\affiliations{
    Affiliation \\
    Affiliation Line 2 \\
    name@example.com
}
\fi

\iffalse
%Example, Multiple Authors, ->> remove \iffalse,\fi and place them surrounding AAAI title to use it
\title{My Publication Title --- Multiple Authors}
\author {
    % Authors

        First Author Name,\textsuperscript{\rm 1}
        Second Author Name, \textsuperscript{\rm 2}
        Third Author Name \textsuperscript{\rm 1} \\
}
\affiliations {
    % Affiliations
    \textsuperscript{\rm 1} Affiliation 1 \\
    \textsuperscript{\rm 2} Affiliation 2 \\
    firstAuthor@affiliation1.com, secondAuthor@affilation2.com, thirdAuthor@affiliation1.com
}
\fi
\begin{document}

\maketitle

\begin{abstract}
 The emergence of symbolic languages with high compositionality has
  attracted extensive attention from a broad range of communities. Existing
  studies achieve high compositionality through \emph{deliberately handcrafted}
  inductions (e.g., small vocabulary sizes, carefully constructed distractors, 
  and ease-of-teaching) in multi-agent learning, which are unnatural. 
  Yet, few studies investigate the emergence of symbolic language with high
  compositionality \emph{naturally}, i.e., without deliberately handcrafted
  inductions. 
  
  In this paper, we are the first to successfully achieve high compositional symbolic
  language in a \emph{natural} manner without handcrafted inductions.
  Initially, by thoroughly investigating the compositionality of emerged symbolic
  language after removing the \emph{deliberately handcrafted}
  inductions, we observe that the agent capacity plays a key role in
  compositionality. We further reveal and characterize the quantitative relationship
  between the agent capacity and the compositionality of symbolic language both
  theoretically and experimentally.
  %The theoretical analysis is built on the MSC
  %(Markov Series Channel) model for the language transmission process and a
  %novel mutual information-based metric for the compositionality.
  %The
  %experiments are conducted on a listener-speaker referential game framework
  %with eliminated external environment factors.
  Both theoretical analysis and
  experimental results lead to a counter-intuitive conclusion that lower agent
  capacity facilitates the emergence of symbolic language with higher
  compositionality. \note{Based on our conclusion, we can generate higher
  compositional symbolic language with a higher probability.}


%  The natural emergence of symbolic languages with high compositionality has
%  attracted extensive attentions from a broad range of communities. Existing
%  studies only investigated the impacts of \emph{deliberately designed} external
%  environmental factors (e.g., small vocabulary sizes, carefully constructed
%  distractors, and ease-of-teaching), which may be too ideal to exist in the
%  real world, without considering the importance of internal capacity of agents.
%  
%  In this paper, we first reveal and characterize the quantitative relationship
%  between the agent capacity and the compositionality of symbolic language both
%  theoretically and experimentally. The theoretical analysis is built on the MSC
%  (Markov Series Channel) model for the language transmission process and a
%  novel mutual information-based metric for the compositionality. The
%  experiments are conducted on a listener-speaker referential game framework
%  with eliminated external environment factors. Both theoretical analysis and
%  experimental results lead to a counter-intuitive conclusion that lower agent
%  capacity facilitates the emergence of symbolic language with higher
%  compositionality.
  
\end{abstract}


\input{tex/introduction.tex}
\input{tex/relatedwork.tex}
\input{tex/theory.tex}
\input{tex/experiments.tex}
\input{tex/last.tex}

\begin{algorithm}[!h]
	\caption{OurAlgorithm$(t,\hat{t})$}
	\begin{algorithmic}[1]
		\IF{Training the speaker agent S}
		\FOR{Batch T randomly selected from $M_0\times M_1$}
        \FOR{$t=(c_0,c_1)$ in T}
        \STATE $P(s_0|t),P(s_1|t)=\pi_{old}^S(s=(s_0,s_1)|t)$
        \STATE Sample $s_0$ with $P(s_0|t)$, $s_1$ with $P(s_1|t)$
        \STATE $P(\hat{t}|s) = \pi^L(\hat{t}|s)$ 
        \STATE Sample $\hat{t}$ with $P(\hat{t}|s)$
        \STATE Get reward $R(\hat{t},t)$
        \STATE $J(\theta^S,\theta^L)=E_{\pi_{old}^S,\pi^L}[R(\hat{t},t)\cdot\frac{\pi^S(s|t)}{\pi^S_{old}(s|t)}]$
        \STATE Update $\theta^S$ by $\bigtriangledown_{\theta^S}J$
        \ENDFOR
        \STATE $\pi_{old}^S\leftarrow \pi^S$
		\ENDFOR
		\ENDIF
	
		\IF{Training the listener agent L}
		\FOR{Batch T randomly selected from $M_0\times M_1$}
		\FOR{$t=(c_0,c_1)$ in T}
		\STATE $P(s_0|t),P(s_1|t)=\pi^S(s=(s_0,s_1)|t)$
		\STATE Sample $s_0$ with $P(s_0|t)$, $s_1$ with $P(s_1|t)$
		\STATE $P(\hat{t}|s) = \pi^L_{old}(\hat{t}|s)$ 
		\STATE Sample $\hat{t}$ with $P(\hat{t}|s)$
		\STATE Get reward $R(\hat{t},t)$
		\STATE $J(\theta^S,\theta^L)=E_{\pi_{old}^S,\pi^L}[R(\hat{t},t)\cdot\frac{\pi^L(s|t)}{\pi^L_{old}(s|t)}]$
		\STATE Update $\theta^L$ by $\bigtriangledown_{\theta^L}J$
		\ENDFOR
		\STATE $\pi_{old}^L\leftarrow \pi^L$
		\ENDFOR
		\ENDIF
	\end{algorithmic}
\end{algorithm}


\bibliography{ref.bib}

\end{document}
