\section{Introduction}

A central endeavour in information theory is the study of capacity limits and coding strategies for reliable communication over different types of channels. Two different philosophies exist on how channels are modeled. Channels in the Shannon world are characterized by some stochastic process that injects errors independently of the communication scheme, while channels in the Hamming world are characterized by an adversary who injects worst-case errors. Historically, adversarial channels were studied under either full knowledge (\textit{omniscient adversary}) or no knowledge (\textit{oblivious adversary}) of the transmitted codeword. A number of recent works \cite{langberg2009binary,code_online_adv_old,improved_upbounds,dey2013upper,bassily2014causal,chen2015characterization,error_erasure,online_largea} instead consider coding against \textit{online} or \textit{causal} adversaries wherein at any point during the transmission, the adversary knows only part of the codeword transmitted thus far.

As noted in \cite{dey2013upper}, the causal adversary model lies in between the stochastic and the omniscient adversary models. In this work, we further bridge together the Shannon and the Hamming worlds by studying a new model where both adversarial and random sources of error are present. Specifically, Alice attempts to send a message to Bob over a binary erasure channel BEC($q$)  or binary symmetric channel BSC($q$) in the presence of a causal adversary Calvin who can erase or flip a certain number of bits at the input of the channel. This is depicted in Fig \ref{channelmodel}. Any transmission strategy must not only overcome the noise due to the random channel but also from the adversary. We also assume that Calvin has access to Bob's reception, which we refer to  as \textit{feedback snooping}. The ability to spy on both Alice and Bob aids Calvin in designing strong attacks. Our goal is to characterize the capacity of this channel.

When there is no random channel present, i.e., $q=0$ in Fig. \ref{channelmodel}, the only source of noise is adversarial. A complete capacity characterization for this case is given in \cite{dey2013upper,chen2015characterization,bassily2014causal}. Our models differ from the ones considered previously in two ways:
\begin{itemize}
    \item \textbf{Mixture of random and adversarial noise} - The noise in the received word is affected by the random channel BEC (BSC) as well as the actions of Calvin who is erasing (flipping) bits. For example in the erasure case, a bit not erased by Calvin can be erased by the BEC. Similarly, in the bit-flip case, a bit flipped by Calvin may be ``unflipped" by the BSC. Conceptually, we think of the discrete memoryless channel (DMC) as the main channel through which Alice and Bob communicate, and Calvin as a malicious entity who attempts to disrupt the transmission.

    \item \textbf{Feedback to adversary} - In our setting, Calvin is allowed access to Bob's reception through \textit{feedback snooping}. This becomes important due to the presence of the stochastic channel. The adversarial attacks described in \cite{dey2013upper,bassily2014causal} if used directly do not provide the right distance bounds needed to establish our converse results. These are appropriately strengthened and crucially rely on Calvin's ability to snoop. Note that feedback snooping is unnecessary when $q=0$.

\end{itemize}
Our contributions can be summarized as follows:
\begin{itemize}
    \item We provide a complete characterization of capacity for the case of erasures. Our result implies that the presence of the random channel BEC($q$) in addition to adversarial erasures simply scales the capacity by a multiplicative factor.
    \item For the case of erasures, we also characterize the capacity when Alice has causal access to Bob's reception and encoding is \textit{closed-loop}. In this scenario, we show that Calvin gains no benefit from his ability to spy on Alice or Bob.  In fact,  he can do no better than making erasure decisions in an i.i.d. manner.
     \item Finally in the case of bit-flips, we prove non-trivial converse and achievability bounds.
\end{itemize}

There are other adversarial models intermediate between the oblivious and omniscient models that have been considered in literature which we do not pursue here (e.g.,  \cite{sufficientlymyopic,dey2010codingdelayed,dey2016bitofdelay,dey2019interplay,zhang2018covert,amita1}). The problem of coding with feedback to the transmitter has been studied by several authors such as \cite{berlekamp1964block,lebedev2016coding,zigangirov1976number}. Finally, we note that our models can be cast under the more general framework of arbitrarily varying channels (AVCs) \cite{csiszarkornerbook,surveyAVC}.  However, known results for AVCs do not directly imply the results in this paper.

\section{Channel Models}

Consider the channel depicted in Fig.\ref{channelmodel}. Alice (the transmitter) attempts to convey a message to Bob (the receiver) over a BEC($q$), in the presence of a $p$-limited causal adversary (Calvin) where the terms will be clarified shortly. The input and output alphabets are $\mathcal{X} = \lbrace 0,1 \rbrace$ and $\mathcal{Y} = \lbrace 0,1,\Lambda\rbrace, $ respectively, where $\Lambda$ denotes an erasure symbol. Encoding is done over $n$ channel uses, and the size of the message set at the transmitter is $2^{nR}$. We allow stochastic encoding and assume the presence of local randomness available only to Alice for this purpose. Denote $x_k \in \mathcal{X}$ to be the symbol selected by the transmitter at channel use $k$. At time $k$, the adversary makes a decision on whether to erase $x_k$  based on his side-information to be specified later. If Calvin erases $x_k$, the received symbol at time $k$ at the receiver is an erasure, i.e., $y_k = \Lambda$. If Calvin decides not to erase $x_k$, then $y_k = x_k$ with probability $1-q$ and $y_k = \Lambda$ with probability $q$, i.e., $x_k$ is erased with probability $q$.

We assume that Calvin knows the codebook used at the transmitter in the case of deterministic encoding or the distribution of codewords in the case of stochastic encoding. Calvin is assumed to be \textit{causal}, i.e., at each channel use $k$, he knows only part of the codeword transmitted so far $(x_1,x_2,\cdots,x_{k}) \in \mathcal{X}^{k}$. Calvin is neither aware of the message nor future transmissions. However, he has access to Bob's reception $(y_1,y_2,\cdots,y_{k-1}) \in \mathcal{Y}^{k-1}$ through a delay-free and noise-free causal feedback link as shown in Fig. \ref{channelmodel}.

A power constraint is further imposed by enforcing Calvin to be $p$-limited, meaning that he can erase at most a constant fraction $p$ of the bits, i.e., if ${\mathbf{a}}} \def\bb{{\mathbf{b}}} \def\bc{{\mathbf{c}}} \def\bd{{\mathbf{d}} \in \{ 0,\Lambda \}^n$ denotes the positions where Calvin decides to erase symbols from $(x_1,x_2,\cdots,x_{n})$, we must have $weight(\mathbf{a}) \leq pn$. We refer to this model as \textit{the BEC causal adversarial channel with feedback snooping} (or BEC($q$)-ADV($p$)-FS). Note that the BEC block in Fig. \ref{channelmodel} is slightly different from the classical BEC. If Calvin erases $x_k$ to an erasure symbol $\Lambda$, we have $y_k = \Lambda$, where $\Lambda$ does not carry any information.

\begin{figure}
    \centering
    \includegraphics[width=0.47\textwidth]{Channel_models_2.png}
    \caption{Channel models considered in this work. }
    \label{channelmodel}
\end{figure}

Our aim is to characterize the capacity of this channel, i.e., the largest value of $R$ such that Alice can reliably convey one out of $2^{nR}$ possible messages to Bob. Precise definitions are given shortly. In Section \ref{BFchannel}, we also consider a related channel by replacing the BEC($q$) with a BSC($q$) and letting Calvin flip bits instead of erasing them, denoted henceforth as BSC($q$)-ADV($p$)-FS.

\textit{Notation and Definitions:} In this work, we only consider fixed length encoding. The blocklength is denoted by $n$. The transmitted message is denoted by the random variable (r.v.) ${\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}$ chosen uniformly from the message set $\mathcal{U}=\lbrace 1,2,3,\cdots,2^{nR} \rbrace$. A deterministic code consists of a fixed encoder map $\Phi_d:\mathcal{U} \to \mathcal{X}^n$ and a decoder map $\Gamma_d:\mathcal{Y}^n\to \mathcal{U}$, where each message is associated to a unique codeword. In case of stochastic encoding, a codeword $\bx$ is selected for a message $u$ according to a chosen conditional distribution $\Phi(.|u)$ defined on $\mathcal{X}^n$. A stochastic code is fully specified by defining all conditional distributions $\left \lbrace \Phi(.|u) \right \rbrace_{u\in \mathcal{U}}$ and a decoder $\Gamma : \mathcal{Y}^n \to \mathcal{U}$. Without loss of generality, we assume in proving converse results that no two distinct messages map to the same codeword. The (maximum) probability of error is then
\begin{equation}\label{maxerrorprob}
    P_e = \max_{u \in \mathcal{U}}\max_{\text{ADV($p$)}}\sum_{{\mathbf{y}}} \def\bz{{\mathbf{z}}}\sum_{\bx} P({\mathbf{y}}} \def\bz{{\mathbf{z}} | \bx) \Phi(\bx|u) \mathbbm{1}(\Gamma({\mathbf{y}}} \def\bz{{\mathbf{z}})\neq u)
\end{equation}
where $\mathbbm{1}(.)$ denotes the indicator function and ADV($p$) denotes a feasible strategy chosen by Calvin. Note that $P({\mathbf{y}}} \def\bz{{\mathbf{z}}|\bx)$ in \eqref{maxerrorprob} is a function of both the stochastic channel and the chosen adversarial strategy. We say that $R>0$ is achievable if for every $\delta>0$ and every sufficiently large $n$, there is a code of rate $R$ and blocklength $n$ with $P_e < \delta$. The capacity is defined to be the supremum of all achievable rates. Let Ber($q$) denote a Bernoulli r.v. with success probability $q$. For $x,y\in[0,1/2]$, let $x \star y = x(1-y)+y(1-x)$ and note that $x \star y = 1/2$ iff either $x=1/2$ or $y=1/2$ (or both).

\section{Results for Erasures}

\subsection{No Transmitter Feedback}
Denote by $C^E(p,q)$ the capacity of BEC($q$)-ADV($p$)-FS when Alice has no side-information, i.e., encoding is restricted to be \textit{open-loop}. We prove the following result.

\begin{theorem}\label{thm_er}
The capacity $C^E(p,q)$ of BEC($q$)-ADV($p$)-FS is given by
\begin{equation}\label{drloveresult_er}
    C^E(p,q) =     \begin{cases}
    (1-2p)(1-q) & \text{ for $0\leq p\leq \frac{1}{2}, ~ 0 \leq q \leq 1$} \\
    0 & \text{otherwise}
    \end{cases}.
\end{equation}
\end{theorem}
\begin{rem}
When there is no BEC, i.e., when $q=0$, our model reduces to the one studied in \cite{dey2013upper, chen2015characterization}. Our result implies that in the setting where both causal adversarial erasures and random erasures are present, the capacity simply scales by a factor of $1-q$.
\end{rem}

\begin{proof}

\textbf{Converse :}
The proof of converse is based on a \textit{wait and snoop, then push} attack inspired by, but different from, an attack in \cite{langberg2009binary,bassily2014causal}. Let the transmitted and the received codewords be denoted by $\bx$ and ${\mathbf{y}}} \def\bz{{\mathbf{z}}$ respectively. Let $\bx_1=(x_1,x_2,\cdots,x_\ell)$ and $\bx_2=(x_{\ell+1},\cdots,x_n)$, where $\ell$ is specified shortly. Similarly, let ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1=(y_1,y_2,\cdots,y_\ell)$ and ${\mathbf{y}}} \def\bz{{\mathbf{z}}_2=(y_{\ell+1},\cdots,y_n)$.

Suppose Alice attempts to communicate at a rate $R= C^E(p,q)+\epsilon=(1-2p)(1-q) + \epsilon$. We will show that for sufficiently large block-length $n$, the probability of decoding error under the proposed attack is lower bounded by a constant that is only a function of $\epsilon$ (and independent of $n$). The two phases of the attack are:
\begin{itemize}
    \item \textbf{Wait and Snoop}: Calvin waits and does not induce any erasures for the first $\ell = n\frac{R-\frac{\epsilon}{2}}{1-q}$ channel uses. Instead, Calvin simply snoops into Bob's reception to determine the erased/unerased bits and their positions. At the end of this phase, Bob receives ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1=(y_1,y_2,\cdots,y_{\ell})$ containing some erased and some unerased bits. Note that the erasures in this phase occur purely due to the BEC($q$) channel. Let $\lbrace i_j \rbrace_{j=1}^m$ be the indices of symbols in ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1$ that remain unerased. Here, $m$ is a random quantity in accordance to the erasure distribution from the BEC($q$).
    \item \textbf{Push}: Calvin forms the set $\mathcal{B}_{{\mathbf{y}}} \def\bz{{\mathbf{z}}_1}$ of codewords consistent with ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1$ as
\begin{multline}\label{Econfset}
    \mathcal{B}_{{\mathbf{y}}} \def\bz{{\mathbf{z}}_1} = \lbrace \bv \in \mathcal{X}^n : \exists \tilde{u} \in \mathcal{U} \text{ s.t. } \Phi(\bv|\tilde{u})>0 \text{ and } \\  v_{i_k} = x_{i_k} ~ k = 1,2,\cdots, m  \rbrace,
\end{multline}
where $\Phi(.|u)$ is the distribution of codewords when message $u$ is to be transmitted. In other words, $\mathcal{T}_{{\mathbf{y}}} \def\bz{{\mathbf{z}}_1}$ consists of all possible codewords that align with ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1$ at the positions that are unerased.
Calvin then samples a codeword $\bx'$ from $\mathcal{B}_{{\mathbf{y}}} \def\bz{{\mathbf{z}}_1}$ according to the distribution $P_{\bX|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1={\mathbf{y}}} \def\bz{{\mathbf{z}}_1}(.|{\mathbf{y}}} \def\bz{{\mathbf{z}}_1)$. In the push phase, Calvin simply erases bit $x_i$ whenever $x_i \neq x_i'$. To complete the proof, it suffices to show that $\bx$ and $\bx'$ correspond to different messages $u$ and $u'$ and that $d(\bx_2,\bx_2')<pn$ with a probability \textit{independent} of $n$. This way there is no way for Bob to distinguish between messages $u$ and $u'$. This is illustrated in Fig. \ref{push_erasure_fig}.
\end{itemize}

\begin{figure}
    \centering
    \includegraphics[width=0.45\textwidth]{push_er.png}
    \caption{In the push phase, if $\bx_2$ and $\bx_2'$ are sufficiently close (within distance $pn$), Calvin can make Bob completely uncertain whether the transmitted codeword was $\bx$ or $\bx'$.}
    \label{push_erasure_fig}
\end{figure}

Note that while the presence of the BEC($q$) lowers the target rate, Calvin adds no erasures for approximately $n(1-2p)$ channel uses which from \cite{bassily2014causal,chen2015characterization} is optimal when there is no BEC($q$). The main difference in attack when $q\neq 0$ is that even though Calvin knows the entire prefix of the transmitted codeword $\bx_1 = (x_1,x_2,\cdots,x_{\ell})$, he forms his set in \eqref{Econfset} based only on the unerased bits. Thanks to feedback snooping, Calvin exploits the additional equivocation induced by the BEC($q$) in the wait and snoop phase to pick a codeword that is sufficiently close to the transmitted codeword, and which corresponds to a message different from one that Alice chose. Note also that while we give Calvin full causal access to Bob's reception, an alternate model where Calvin is allowed \textit{one-time block feedback} is sufficient - he would add no erasures for $\ell$ channel uses, retrieve through feedback the entire block ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1$ and then `push'.

The proof steps are similar to section A from \cite{bassily2014causal} except that we account for the presence of the BEC($q$) in our claims. Define the set $
    A_0 = \left \lbrace  {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 :  H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}} \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1) > \frac{n\epsilon}{4}  \right \rbrace
$ and the event $E_1=\lbrace {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 \in A_0 \rbrace$. We have the following lemma.

\begin{lemma}
     $P(E_1 )\geq \frac{\epsilon}{4}$.
\end{lemma}
\begin{proof}
Since ${\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}\to \bX_1 \to {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1$ is a Markov chain, by the data processing inequality, we have
\begin{equation*}
    I({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}};{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1) \leq I(\bX_1,{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1) = \ell (1-q) = n(R - \epsilon /2).
\end{equation*}
The above holds since Calvin adds no erasures in the wait and snoop phase and the channel between $\bX_1$ and ${\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1$ is a BEC($q$). Now, since $H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}) = nR$, we have
\begin{equation*}
    H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1) =  \mathbb{E}_{{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1} H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1) =  H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}) - I({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}};{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1) \geq n\epsilon / 2.
\end{equation*}
By Markov's inequality then,
\begin{equation*}
    P\left ( nR - H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1) > nR - n\epsilon/4\right ) \leq 1 - \frac{\epsilon/4}{R - \epsilon/4}
\end{equation*}
which gives as desired,
\begin{equation*}
   P(E_1) = P\left ( H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}} \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1) > \frac{n\epsilon}{4}  \right ) \geq \frac{\epsilon}{4}.
\end{equation*}
\end{proof}

Now let $E_2$ be the event $\lbrace {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}} \neq {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}'\rbrace $ and $E_3$ be the event $\lbrace d(\bX_2,\bX_2')<pn \rbrace$. First, we will show that for ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1 \in A_0$, $P(E_2,E_3 \mid \lbrace {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1={\mathbf{y}}} \def\bz{{\mathbf{z}}_1\rbrace) \geq \epsilon^{\mathcal{O}(1/\epsilon)}$. To that end, consider sampling $t=\frac{9}{\epsilon}$ codewords $\mathcal{C}_t = \left \lbrace \bX^{(1)},\bX^{(2)},\cdots,\bX^{(t)} \right \rbrace$ from the set $\mathcal{B}_{{\mathbf{y}}} \def\bz{{\mathbf{z}}_1}$ where each codeword is sampled according to the conditional distribution $P_{\bX|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1={\mathbf{y}}} \def\bz{{\mathbf{z}}_1}(.|{\mathbf{y}}} \def\bz{{\mathbf{z}}_1)$. Let the messages corresponding to the codewords be ${\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_1,{\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_2,\cdots,{\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_t$ and let $E_4$ be the event that $\left \lbrace {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_1, {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_2, \cdots {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_t \text{ are all distinct}\right \rbrace$ i.e. all of the codewords are distinct. We have from proposition 1, section A.2 from \cite{bassily2014causal} the following.

\begin{lemma} \cite{bassily2014causal}\label{er_distlemma}
For ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1 \in A_0$ and for sufficiently large block length $n$,
$$P(E_4 \mid  {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \geq \left (\frac{\epsilon}{5}\right )^{t-1}.$$
\end{lemma}

The average Hamming distance between the suffixes of codewords in $\mathcal{C}_t$ is defined as
\begin{equation*}
    d_{avg}(\mathcal{C}_t) = \frac{1}{t(t-1)} \sum_{i\neq j} d_H\left ( \bX_2^{(i)} ,\bX_2^{(j)}\right ).
\end{equation*}
Conditioning on $E_5$, Plotkin's bound dictates that
\begin{equation*}
\begin{split}
       d_{avg}(\mathcal{C}_t) \leq \frac{1}{2}\frac{t}{t-1}(n-\ell) &= n \frac{t}{t-1}\left ( p - \frac{\epsilon}{4(1-q)}\right ) \\
       &\leq  n \frac{\frac{9}{\epsilon}}{\frac{9}{\epsilon}-1}\left ( p - \frac{\epsilon}{4}\right ) \leq np - n\frac{\epsilon}{8}.
\end{split}
\end{equation*}
Thus for ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1 \in A_0$, we have
\begin{equation*}
    \mathbb{E}(d_{avg}(\mathcal{C}_t) \mid E_4, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \leq np - n\epsilon/8.
\end{equation*}
Now, since all of the $\bX^{(i)}$'s are picked independently, all pairs $(\bX^{(i)}, \bX^{(j)})$ have identical distribution. Thus,
\begin{multline*}
   \mathbb{E}(d_{avg}(\mathcal{C}_t) \mid E_4, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) =  \\ \mathbb{E}(d_H(\bX_2^{(1)},\bX_2^{(2)}) \mid E_4, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 )
\end{multline*}
and also
\begin{multline*}
 \mathbb{E}(d_H(\bX_2^{(1)},\bX_2^{(2)}) \mid E_4, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) = \\ \mathbb{E}(d_H(\bX_2,\bX_2') \mid E_4, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ).
\end{multline*}
Thus, we have
\begin{equation*}
    \mathbb{E}(d_H(\bX_2^{(1)},\bX_2^{(2)}) \mid E_4, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \leq  np - n\epsilon/8
\end{equation*}
and by Markov's inequality
\begin{equation}\label{er_markov}
    P(d_H(\bX_2^{(1)},\bX_2^{(2)})>np \mid E_4, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \leq 1 - \frac{\epsilon}{8p}.
\end{equation}
We have also,
\begin{multline*}
    P(E_2,E_3 \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) = \\ P(d(\bX_2^{(1)},\bX_2^{(2)}) \leq pn, {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_1 \neq {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_2 \mid  {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \\ \geq     P(d(\bX^{(1)}_2,\bX^{(2)}_2)  \leq pn, E_4 \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ).
\end{multline*}
where the last inequality holds because event $E_4$ is a subset of the event $\lbrace U_1\neq U_2 \rbrace$. We then have,
\begin{multline*}
     P(d(\bX^{(1)}_2,\bX^{(2)}_2)\leq pn, E_4 \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) = \\
     P(d(\bX^{(1)}_2,\bX^{(2)}_2) \leq pn \mid E_4, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) P(E_4\mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1  ).
\end{multline*}
From Lemma \ref{er_distlemma} and \eqref{er_markov}, when $E_1$ occurs i.e. ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1 \in A_0$, we get,
\begin{equation*}
        P(E_2,E_3 \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \geq \frac{\epsilon}{8p}\left (\frac{\epsilon}{5}\right )^{\frac{9}{\epsilon}-1} = \epsilon^{\mathcal{O}(1/\epsilon)}
\end{equation*}
as we set out to prove.

Recall that $E_2$ is the event that the message ${\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}'$ picked by the adversary is different from the one transmitted and $E_3$ is the event that the corresponding codewords $\bX_2$ and $\bX_2'$ are close enough so that Calvin's push phase succeeds and Bob is completely uncertain whether the message transmitted was ${\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}$ or ${\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}'$. Hence when $E_2$ and $E_3$ occur, the probability of decoding error is at least $1/2$. To finish the proof, we need only show a lower bound on $P(E_2,E_3)$. We have,
\begin{equation*}
\begin{split}
P(E_2,E_3) &\geq P(E_2,E_3,E_1) \\
&= \sum_{{\mathbf{y}}} \def\bz{{\mathbf{z}}_1 \in A_0}  P(E_2,E_3 \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) P({\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1={\mathbf{y}}} \def\bz{{\mathbf{z}}_1) \\
&\geq \frac{\epsilon}{8p}\left (\frac{\epsilon}{5}\right )^{\frac{9}{\epsilon}-1}\sum_{{\mathbf{y}}} \def\bz{{\mathbf{z}}_1 \in A_0}P({\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1={\mathbf{y}}} \def\bz{{\mathbf{z}}_1) \\
&= \frac{\epsilon}{8p}\left (\frac{\epsilon}{5}\right )^{\frac{9}{\epsilon}-1} P(E_1)\\
&\geq \frac{\epsilon}{4} \frac{\epsilon}{8p}\left (\frac{\epsilon}{5}\right )^{\frac{9}{\epsilon}-1},
\end{split}
\end{equation*}
a lower bound that is independent of $n$, hence completing the proof.

\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{BEC_v1}
    \caption{Capacity of BEC($q$)-ADV($p$)-FS with ($C_f^E(p,q))$ and without transmitter feedback (resp. $C^E(p,q))$ as a function of $p$ for $q=0,0.3,0.6$. The cut-off value of $p$ beyond which $C^{E}(p,q)=0$ is $p=1/2$ independent of $q$.}
    \label{BECupperbounds}
\end{figure}

\textbf{Achievability}: We resort to a random coding argument to claim existence of a stochastic code that achieves \eqref{drloveresult_er}. Let $R= C^E(p,q)-\epsilon=(1-2p)(1-q) - \epsilon$. Our construction is a modification of the encoder and decoder described in \cite{chen2015characterization}, which was used to prove (tight) achievability when $q=0$. We begin by briefly reviewing the encoder and decoder of \cite{chen2015characterization}. While reviewing, we provide key insights into how this decoder might fail once a BEC is added to the channel model. Following the review, we use our insights to modify the decoder in order to account for the additional random noise when $q>0$. Alice has a set of private secret keys $\mathcal{S}$ she uses for (stochastic) encoding. The encoder and decoder of \cite{chen2015characterization} is constructed as follows (here, $q=0$):
\begin{itemize}
\item \textbf{Encoder:} A message $u$ is mapped to $1/\theta$ sub-codewords or chunks, each of length $n \theta$, where $\theta=\frac{\epsilon}{4}$ is a quantization parameter. Each of the sub-codewords is obtained by a stochastic code and the secrets between chunks are chosen independently. The sub-codewords are then concatenated together to form the transmitted word. Further technical details are in the appendix.

 \item \textbf{Decoder:} Decoding begins after Bob receives the entire $n$-symbol channel output $\mathbf{y}$. For some integer $t^*$, Bob partitions $\mathbf{y}$ into 2 strings: $\mathbf{y}_{1} = (y_1, \ldots, y_{t^*})$ and $\mathbf{y}_{2}= (y_{t^*+1}, \ldots, n)$. Decoding occurs in two sequential phases. In the first phase, Bob performs list decoding on $\mathbf{y}_1$ to create a list of messages $\mathcal{L}$. In the second phase, he refines the list by removing all messages in $\mathcal{L}$ that are not consistent with $\mathbf{y}_2$. Here, a message $u'$ is said to be consistent with $\mathbf{y}_2$ iff some codeword corresponding to $u'$ agrees with $\mathbf{y}_2$ on the unerased bits. If exactly one message, say $\hat{u}$, remains in $\mathcal{L}$ after refinement, the decoder outputs $\hat{u}$. If the refined list does not contain exactly one message, a decoding error is declared. Decoding is successful if $\hat{u} = u$.

\end{itemize}
The integer $t^*$ is a decoding point which indicates which part of the channel output is used for list decoding (phase 1) and which part is used for list refinement (phase 2). The authors in \cite{chen2015characterization} show that Bob can choose $t^*$ such that decoding is successful w.h.p.. Here, $t^*$ is chosen as a function of the number of (purely adversarial) erasures $\lambda^{a}_{t^*}$ observed in $\mathbf{y}$ up until time $t^*$. Specifically, Bob chooses $t^*$ as the smallest integer that satisfies the so-called \textit{list-decoding condition}
\begin{equation} \label{eq:phase1_cond}
\lambda^{a}_{t^*} \leq t^*(1-\theta) - ((1-2p)-\epsilon)n
\end{equation}
and the \textit{energy bounding condition}
\begin{equation} \label{eq:phase2_cond}
np - \lambda^{a}_{t^*} \leq \frac{(n-t^*)(1-\theta)}{2}.
\end{equation}
Condition (\ref{eq:phase1_cond}) ensures the size of $\mathcal{L}$ is small (at most a constant) while condition (\ref{eq:phase2_cond}) ensures the fraction of erasures that occur in $\mathbf{y}_2$ is small enough to perform list refinement.

Problems in this construction arise when $q>0$. If the decoder assumes that all erasures that he sees are adversarial and performs decoding by selecting $t^*$ according to conditions \eqref{eq:phase1_cond} and \eqref{eq:phase2_cond}, the maximum rate that can be achieved is $C^E(p+q-pq,0) = C^E(p,q)-q$ which is strictly less than capacity. Therefore, simply counting erasures without knowing (or estimating) their source is no longer a viable strategy when $q>0$.

To circumvent the issues described above, we modify conditions \eqref{eq:phase1_cond} and \eqref{eq:phase2_cond} appropriately. Let $\lambda_t$ denote the number of erasures observed by Bob up until time $t$, which includes contributions both from Calvin and the BEC($q$). Then, Bob chooses $t^*$ as the smallest integer that satisfies the modified list-decoding condition
\begin{equation} \label{eq:phase1_cond_m}
{\lambda}_{t^*} - qt^*  \leq t^*(1-q)(1-\theta) - Rn
\end{equation}
and the modified list refinement condition
\begin{equation} \label{eq:phase2_cond_m}
np(1-q) - ({\lambda}_{t^*}- qt^*)  \leq \frac{(n-t^*)(1-q)(1-\theta)}{2}.
\end{equation}
Note that if Calvin adds $\lambda^{a}_{t^*}$ erasures up until $t^*$, the total number of erasures  ${\lambda}_{t^*}$ that Bob observes is approximately ${\lambda}_{t^*} \approx \lambda^{a}_{t^*} + q(t^* - \lambda^{a}_{t^*})$. On making this substitution we see that $t^*$ satisfying \eqref{eq:phase1_cond_m} and \eqref{eq:phase2_cond_m} is nearly the same as that satisfying \eqref{eq:phase1_cond} and \eqref{eq:phase2_cond} i.e. it is sufficient to choose $t^*$ only as a function of pure adversarial erasures. However, since Bob has no way to ascertain this, he works with the quantity ${\lambda}_{t^*} - qt^*$ which is an estimate of the number of adversarial erasures that do not conincide with random erasures. Having selected $t^*$, Bob can then finish decoding using the two-phase decoding process of \cite{chen2015characterization} to successfully recover the transmitted message. Further details of the proof are provided in the appendix.

\end{proof}

\subsection{With Transmitter Feedback}
Suppose now that Alice in addition to Calvin has access to Bob's reception perfectly through a separate causal feedback link. This allows Alice to employ \textit{closed-loop} encoding strategies where the input $x_k$ at time $k$ is possibly a function of both the message and Bob's reception thus far $(y_1,y_2,\cdots,y_{k-1})$, i.e.,
\begin{equation}
    \bX_k \sim f_k({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}},{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1,{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_2,\cdots,{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_{k-1}) ~~ k=1,2,\cdots,n
\end{equation}
where for each $k$, $f_k$ is either deterministic or, more generally, a probabilistic map defining a conditional distribution $P_{\bX |{\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}},{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1,{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_2,\cdots,{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_{k-1}}$ over $\mathcal{X}$. Calvin is assumed to be causal. He does not know the message but knows the closed-loop encoding (possibly stochastic) maps $\lbrace f_k \rbrace_{k=1}^{n}$ used by Alice. Let the capacity in this case be denoted as $C_f^{E}(p,q)$. We have the following result.

\begin{theorem}
\label{causalBECtcfbk}
The capacity $C_f^E(p,q)$ of BEC($q$)-ADV($p$)-FS with causal feedback to the transmitter is
\begin{equation}\label{causalBECtxfbk_formula}
    C_f^E(p,q) =(1-p)(1-q) \quad \forall ~ 0\leq p \leq 1, 0 \leq q \leq 1 .
\end{equation}
\end{theorem}
\begin{rem}
If Calvin were to simply erase each symbol with probability $p$, the effective channel is a BEC with erasure probability $s=1-(1-p)(1-q)$. This means that the rate is limited to\footnote{For a vanilla DMC such as the BEC, the capacity is the same under deterministic and stochastic encoding \cite{surveyAVC}.} $(1-p)(1-q)$ which matches with the expression in \eqref{causalBECtxfbk_formula}. This implies that \textit{the optimal attack for the adversary is to simply cause i.i.d. erasures. The knowledge of the (closed-loop) encoding scheme or the ability to snoop into Bob's reception does not buy Calvin any benefit.}
\end{rem}
\begin{proof}
\textbf{Converse:} The converse proof follows the above remark. Fix $\epsilon>0$. Calvin simply erases each symbol with probability $p-\frac{\epsilon}{1-q}$. By the Chernoff bound, the probability that Calvin will run out of his budget of $pn$ erasures decays exponentially with $n$. The combined effect of the adversary and the BEC($q$) then is a BEC with erasure probability $    s=\left(p-\frac{\epsilon}{1-q}\right)(1-q)+q\left (1-\left (p-\frac{\epsilon}{1-q} \right) \right)+\left (p-\frac{\epsilon}{1-q}\right)q=p+q-pq - \epsilon.$ Hence, $ C_f^{E}(p,q) \leq 1-s = (1-p)(1-q) + \epsilon.$

\textbf{Achievability :} The achievability scheme is essentially an ARQ type scheme. Alice simply transmits each of the $k$ bits in the message repeatedly until it is successfully received. If $e_\Lambda$ is the total number of erasures (a random quantity) that occur due to both the actions of Calvin and the BEC($q$), Alice needs $n = k + e_\Lambda$ channel uses for this scheme to succeed. Note that at channel use $t$, since Calvin does not know whether the BEC($q$) will introduce an erasure or not,

we can show by the Chernoff bound that $P\left( e_{\Lambda} \leq ((p+q-pq)+\epsilon)n  \right )$ with probability at least $1-2^{\Omega(n\epsilon^2)}$ and hence, $ C_f^{E}(p,q) \geq (1-p)(1-q)-\epsilon$.

\end{proof}

In Fig. \ref{BECupperbounds}, we plot $C^E(p,q)$ and $C_f^E(p,q)$ as a function of $p$ for $q=0,0.3,0.6$.

\section{Results for Bit-Flips}\label{BFchannel}
In this section, we assume that Calvin can attempt to flip up to $pn$ bits and the random channel is a BSC($q$) instead of a BEC($q$). The input and output alphabets are $\mathcal{X} = \lbrace 0,1 \rbrace$ and $\mathcal{Y} = \lbrace 0,1\rbrace $. At time $k$, Calvin produces $a_k \in \mathcal{A}=\{0,1\}$ based on his side information which is the same as before, i.e., he knows $(x_1,x_2,\cdots, x_k)$, the codebook or the codeword distribution, and $(y_1,y_2,\cdots,y_{k-1})$. The received symbol at time $k$ at the receiver is $y_k = x_k + a_k +1$ with probability $q$ and $y_k = x_k + a_k $ with probability $1-q$ where $+$ denotes mod-$2$ addition and $q \in [0,1/2]$. The constraint on the adversary can be expressed as $weight(a_1,a_2,\cdots,a_n) \leq pn$. In contrast to the erasure case, note that a flip-attempt of Calvin can now be undone by the BSC. No feedback to the transmitter is assumed. For this model denoted BSC($q$)-ADV($p$)-FS, we prove an upper bound and use the result of \cite{chen2015characterization} to provide a simple achievable rate. The gap between the bounds gets larger when $q$ gets larger. Eliminating this gap and proving a tight capacity characterization is left as future work.
\subsection{An Upper Bound $\overline{C}(p,q)$}
\begin{theorem}\label{flipconv_thm}
The capacity $C(p,q)$ of BSC($q$)-ADV($p$)-FS is bounded as $C(p,q)\leq \overline{C}(p,q)$ where
\begin{equation}\label{drloveresult}
    \overline{C}(p,q) = \min_{ \bar{p}: \bar{p} \in \mathcal{P}} \alpha(p,\bar{p},q) \left (  1 - h_2\left ( \frac{\bar{p}}{\alpha(p,\bar{p},q)} \star q\right)    \right),
\end{equation}
\begin{equation*}
    \alpha(p,\bar{p},q) = 1-4(p-\bar{p}) ~~,~~    \mathcal{P} = \left\lbrace \bar{p} : 0\leq \bar{p} \leq p  \right \rbrace
\end{equation*}
when $p<\frac{1}{4}$. When $p \geq \frac{1}{4}$, $C(p,q)=0$.
\end{theorem}
\begin{rem}
When $q=0,$ i.e., there is no BSC, the channel model reduces to that considered in \cite{dey2013upper}, and the capacity expression \eqref{drloveresult} matches with the result proved in \cite{dey2013upper}.
\end{rem}

\begin{proof}
Fix a $\bar{p} \in [0,p]$. Suppose that for some $\epsilon >0 $, the transmitter attempts to communicate at a rate of $R = \alpha(p,\bar{p},q) \left (  1 - h_2\left ( \frac{\bar{p}}{\alpha(p,\bar{p},q)} \star q\right)    \right) +\epsilon$. We show that for sufficiently large $n$, under the proposed attack strategy for Calvin, the probability of decoding error in \eqref{maxerrorprob} is lower bounded by $\epsilon^{O(1/\epsilon)}$, a quantity \textit{independent} of $n$. Since the same argument works for any $\bar{p}$, the result in theorem \ref{flipconv_thm} holds.

Our proof is based on a \textit{babble and snoop, then push} attack inspired, in part from \cite{dey2013upper}. As noted before, the attack in \cite{dey2013upper} does not work if used directly. Let $\bx$ and ${\mathbf{y}}} \def\bz{{\mathbf{z}}$ denote the transmitted and received words. Let $\bx_1=(x_1,x_2,\cdots,x_\ell)$ and $\bx_2=(x_{\ell+1},\cdots,x_n)$, where $\ell$ is specified shortly. Similarly, let ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1=(y_1,y_2,\cdots,y_\ell)$ and ${\mathbf{y}}} \def\bz{{\mathbf{z}}_2=(y_{\ell+1},\cdots,y_n)$. The proposed attack consists of the following two phases:
\begin{itemize}
    \item \textbf{Babble and Snoop}: For the first $\ell=(\alpha(p,\bar{p},q)+\epsilon/2)n$ channel uses, Calvin injects random bit-flips and monitors Bob's reception - at channel use $i$, $1\leq i \leq \ell$, he flips bit $x_i$ with probability $\bar{p}n/\ell$. At the end of this phase, Calvin knows $\bx_1$ and ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1$.
    \item \textbf{Push}: Calvin samples a codeword $\bx'$ (corresponding to message $u'$) according to the conditional distribution $P_{\bX|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}={\mathbf{y}}} \def\bz{{\mathbf{z}}_1}(.|{\mathbf{y}}} \def\bz{{\mathbf{z}}_1)$. His goal is to confuse the receiver between $\bx$ and $\bx'$. At positions where $\bx_2$ and $\bx_2'$ agree, he does nothing. Positions $j$ where $\bx_2$ and $\bx_2'$ disagree, he flips $x_j$ with probability $1/2$. This way, the Bob cannot distinguish between $\bx$ and $\bx'$ or messages $u$ and $u'$ (even with the BSC($q$)) due to the fact that $p({\mathbf{y}}} \def\bz{{\mathbf{z}}_2 | \bx_2) = p({\mathbf{y}}} \def\bz{{\mathbf{z}}_2 | \bx_2')$. The proof relies on showing that with a small probability independent of $n$, $u$, $u'$ are distinct and $\bx_2$, $\bx_2'$ are sufficiently close.

\end{itemize}

Note that Calvin requires knowledge of ${\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1$, i.e., the symbols received by Bob during the first phase of the attack. The presence of the BSC($q$) introduces additional equivocation at the receiver which Calvin is able to exploit to cause a reduction in rate. Here also, \textit{one-time block feedback} (of entire block ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1$) after the first $\ell$ channel uses is sufficient for the attack to succeed.

In the babble and snoop phase, by the Chernoff bound, Calvin uses at most $\bar{p}n+\epsilon n /64$ flips with probability at least $1-e^{-\Omega(\epsilon^2n)}$. Let this be denoted as event $E_1$. Conditioned on $E_1$, Calvin's remaining budget in the push phase is atleast $(p-\bar{p})n-\epsilon n / 64$. Define the set
\begin{equation*}
   A_0 = \left \lbrace  {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 :  H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}} \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1) > \frac{n\epsilon}{4}  \right \rbrace.
\end{equation*}

Defining the event $E_2=\lbrace {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 \in A_0\rbrace$, we have the following lemma.
\begin{lemma}
     $P(E_2) \geq \epsilon /4$.
\end{lemma}
 \begin{proof}
 The proof closely follows claim 4 in \cite{dey2013upper}. Note that ${\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}\to \bX_1 \to {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1$ is a markov chain and hence, by the data processing inequality and Calvin's actions in the babble phase,
\begin{equation*}
    I({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}};{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1) \leq I(\bX_1;{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1) = \ell \left ( 1 - h_2 \left ( \frac{\bar{p}n}{\ell} \star q\right ) \right ).
\end{equation*}
This is because the channel between $\bX_1$ and ${\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1$ is now a cascade of $BSC(\bar{p}n/\ell)$ and $BSC(q)$.
Noting that $\ell = (\alpha + \epsilon/2 )n$,
\begin{equation*}
    I({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}};{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1) \leq   n (\alpha + \epsilon/2 ) \left ( 1 - h_2 \left ( \frac{\bar{p}}{\alpha + \epsilon /2} \star q\right )\right ).
\end{equation*}
Since $I({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}},{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1)=H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}) - H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}| {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1)$ and $H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}) = nR =  n\alpha\left (  1 - h_2\left ( \frac{\bar{p}}{\alpha} \star q\right)    \right) +n \epsilon $, we get,
\begin{multline*}
    H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1) \geq \frac{n\epsilon}{2} + \\ n \left ( (\alpha + \epsilon/2)h_2 \left ( \frac{\bar{p}}{\alpha + \epsilon /2} \star q\right ) - \alpha h_2\left(\frac{\bar{p}}{\alpha} \star q\right) \right ).
\end{multline*}
Now, the function $f(x) = xh_2\left ( \frac{\bar{p}}{x} \star q\right)$ is increasing in $x$, for any fixed $q\in(0,1/2)$. To see this, note that
\begin{equation*}
    \frac{ df}{dx} =h_2\left(\frac{\bar{p}}{x} \star q\right) + (2q-1)\frac{\bar{p}}{x} \log_2 \left (\frac{1-\frac{\bar{p}}{x}\star q}{\frac{\bar{p}}{x}\star q} \right ) >0
\end{equation*}
since $\frac{\bar{p}}{x}\star q < 1/2$ and $\log_2\left ( \frac{1-y}{y} \right) = \frac{d}{dy} h_2(y) >0 $ for $y\in(0,1/2)$. Hence, we have $H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1) = \mathbb{E}_{{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1} H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1={\mathbf{y}}} \def\bz{{\mathbf{z}}_1) \geq n\epsilon /2$. Finally, by Markov's inequality,
\begin{equation*}
    P\left ( nR - H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1) > nR - n\epsilon/4\right ) \leq 1 - \frac{\epsilon/4}{R - \epsilon/4}
\end{equation*}
which gives as desired,
\begin{equation*}
    P\left ( H({\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}} \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1) > \frac{n\epsilon}{4}  \right ) \geq \frac{\epsilon}{4}.
\end{equation*}
\end{proof}
Next, define the events $E_3=\lbrace {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}} \neq {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}' \rbrace$ and $E_4 = \lbrace d_{H}(\bX_2,\bX_2') \leq 2(p-\bar{p})n - \epsilon n /8  \rbrace$. $E_3$ is the event that the message picked by the adversary to confuse Bob in the push phase is different from the one transmitted. Similarly, event $E_4$ ensures that Calvin's remaining flips are enough to carry his push attack. Using techniques from section A.2 of \cite{bassily2014causal} and claim 6 in \cite{dey2013upper}, we can now show the following.
\begin{lemma}
For ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1 \in A_0$,
   \begin{equation}\label{bscproofeventbd}
    P(E_3,E_4 \mid  {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1) \geq \frac{\epsilon}{48}\left (\frac{\epsilon}{5}\right )^{\frac{12}{\epsilon}-1} = \epsilon^{\mathcal{O}(1/\epsilon)}.
\end{equation}
\end{lemma}
\begin{proof}
Consider sampling $t = \frac{12}{\epsilon}$ codewords $\mathcal{C}_t = \left \lbrace \bX^{(1)},\bX^{(2)},\cdots,\bX^{(t)} \right \rbrace$, each codeword sampled according to the conditional distribution $P_{\bX|{\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1={\mathbf{y}}} \def\bz{{\mathbf{z}}_1}(.|{\mathbf{y}}} \def\bz{{\mathbf{z}}_1)$. Let the messages corresponding to the codewords be ${\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_1,{\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_2,\cdots,{\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_t$ and let $E_5$ be the event that $\left \lbrace {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_1, {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_2, \cdots {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_t \text{ are all distinct}\right \rbrace$ i.e. all of the codewords are distinct. We have from proposition 1, section A.2 from \cite{bassily2014causal} that for ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1 \in A_0$, for sufficiently large block length $n$,
\begin{equation*}
 P(E_5 \mid  {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \geq \left (\frac{\epsilon}{5}\right )^{t-1}.
\end{equation*}
The average Hamming distance between the suffixes of codewords in $\mathcal{C}_t$ is defined as
\begin{equation*}
    d_{avg}(\mathcal{C}_t) = \frac{1}{t(t-1)} \sum_{i\neq j} d_H\left ( \bX_2^{(i)} ,\bX_2^{(j)}\right ).
\end{equation*}
Recall that $\ell=(1-4(p-\bar{p})+\epsilon/2)n$. Conditioning on $E_5$, by Plotkin's bound we have
\begin{equation*}
       d_{avg}(\mathcal{C}_t) \leq \frac{1}{2}\frac{t}{t-1}(n-\ell) \leq 2(p-\bar{p})n - \epsilon n /6.
\end{equation*}
Thus for ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1 \in A_0$, we have
\begin{equation*}
    \mathbb{E}(d_{avg}(\mathcal{C}_t) \mid E_5, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \leq 2(p-\bar{p})n - \epsilon n /6.
\end{equation*}
Now, since all of the $\bX^{(i)}$'s are picked independently, all pairs $(\bX^{(i)}, \bX^{(j)})$ have identical distribution. Thus,
\begin{multline*}
   \mathbb{E}(d_{avg}(\mathcal{C}_t) \mid E_5, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) =  \\ \mathbb{E}(d_H(\bX_2^{(1)},\bX_2^{(2)}) \mid E_5, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 )
\end{multline*}
and also
\begin{multline*}
 \mathbb{E}(d_H(\bX_2^{(1)},\bX_2^{(2)}) \mid E_5, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) = \\ \mathbb{E}(d_H(\bX_2,\bX_2') \mid E_5, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ).
\end{multline*}
Thus, we have
\begin{equation*}
    \mathbb{E}(d_H(\bX_2^{(1)},\bX_2^{(2)}) \mid E_5, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \leq  2(p-\bar{p})n - \epsilon n /6.
\end{equation*}
and by Markov's inequality
\begin{multline}\label{flip_markov}
    P(d_H(\bX_2^{(1)},\bX_2^{(2)})>2(p-\bar{p})n - \epsilon n /8 \mid E_5, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \leq \\ \frac{2(p-\bar{p})n - \epsilon n /6 }{2(p-\bar{p})n - \epsilon n /8 } = 1 - \frac{\epsilon}{48(p-\bar{p})-3\epsilon} \leq 1 - \frac{\epsilon}{48}.
\end{multline}
Thus,
\begin{multline*}
    P(E_3,E_4 \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) = \\ P(d(\bX_2^{(1)},\bX_2^{(2)}) \leq 2(p-\bar{p})n - \epsilon n /8, {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_1 \neq {\mathbf{U}}} \def\bV{{\mathbf{V}}} \def\bW{{\mathbf{W}}} \def\bX{{\mathbf{X}}_2 \mid  {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \\ \geq     P(d(\bX^{(1)}_2,\bX^{(2)}_2)  \leq 2(p-\bar{p})n - \epsilon n /8, E_5 \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ).
\end{multline*}
where the last inequality holds because event $E_5$ is a subset of the event $\lbrace U_1\neq U_2 \rbrace$. We then have,
\begin{multline*}
     P(d(\bX^{(1)}_2,\bX^{(2)}_2)\leq 2(p-\bar{p})n - \epsilon n /8, E_5 \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) = \\
     P(d(\bX^{(1)}_2,\bX^{(2)}_2) \leq 2(p-\bar{p})n - \epsilon n /8 \mid E_5, {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \\ \times P(E_5\mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1  ).
\end{multline*}
From \eqref{flip_markov}, when $E_1$ occurs i.e. ${\mathbf{y}}} \def\bz{{\mathbf{z}}_1 \in A_0$, we get,
\begin{equation*}
        P(E_3,E_4 \mid {\mathbf{Y}}} \def\bZ{{\mathbf{Z}}_1 = {\mathbf{y}}} \def\bz{{\mathbf{z}}_1 ) \geq \frac{\epsilon}{48}\left (\frac{\epsilon}{5}\right )^{\frac{12}{\epsilon}-1} = \epsilon^{\mathcal{O}(1/\epsilon)}
\end{equation*}
as we set out to prove.
\end{proof}
 Now, in the push phase, Calvin injects $Ber(1/2)$ noise at $d_H(\bX_2,\bX_2^')$ positions. Conditioned on $E_1$, Calvin has at least a budget of $(p-\bar{p})n-\epsilon n /64$ bit-flips that remain. If ${\mathbf{a}}} \def\bb{{\mathbf{b}}} \def\bc{{\mathbf{c}}} \def\bd{{\mathbf{d}}_2$ is the error vector chosen by Calvin in the push phase, conditioned on $E_3$ and $E_4$ we have $\mathbb{E}  (d_H({\mathbf{a}}} \def\bb{{\mathbf{b}}} \def\bc{{\mathbf{c}}} \def\bd{{\mathbf{d}}_2,\mathbf{0})) = (p-\bar{p})n - \epsilon n /16$. Further by the Chernoff bound, with probability at least $1-2^{-\Omega(\epsilon^2 n )}$, the distance $d_H({\mathbf{a}}} \def\bb{{\mathbf{b}}} \def\bc{{\mathbf{c}}} \def\bd{{\mathbf{d}}_2,\mathbf{0})$ is within $3\epsilon n/ 64$ of its expected value. Let this event be $E_5$. Since $\mathbb{E}  (d_H({\mathbf{a}}} \def\bb{{\mathbf{b}}} \def\bc{{\mathbf{c}}} \def\bd{{\mathbf{d}}_2,\mathbf{0})) + 3\epsilon n/64 = (p-\bar{p})n-\epsilon n /64$, the power constraint is respected w.h.p..

When events $E_1,E_3,E_4,E_5$ occur, the probability of decoding error is clearly at least $1/2$ since the receiver cannot distinguish between $\bx$ and $\bx'$. Since $P(E_1)\geq 1-e^{-\Omega(\epsilon^2 n)}$ and $P(E_5)\geq 1-e^{-\Omega(\epsilon^2 n)}$, the bound in \eqref{bscproofeventbd} together with the bound $P(E_2)\geq \epsilon/4$ implies for sufficiently large $n$, the maximum probability of error in \eqref{maxerrorprob} is at least of the order $\epsilon^{O(1/\epsilon)}$, a quantity independent of $n$ and the proof is complete.
\end{proof}

 The solution $\overline{C}(p,q)$ to the optimization problem in \eqref{drloveresult} has the following form:
\begin{itemize}
    \item $\overline{C}(p,q)>0$ for all $p\in[0,1/4)$ and $q \in [0,1/2)$.

    \item For a fixed $q\in[0,1/2)$, there is a $p_0$ (a function of $q$) such that for $p\leq p_0$, $\overline{C}(p,q)$ is convex and equal to ($1-h_2(p \star q)$), which is the capacity when channels BSC($p$) and BSC($q$) are in cascade. Thus when $p\leq p_0$, the babble, snoop, and push strategy outlined here provides no benefit over a simpler adversarial strategy of injecting i.i.d. Ber($p$) bit-flips.

    \item It can be shown that the value of $p_0$ is the unique solution (different from $1/2$) of the equation
    \begin{equation}\label{Eqp_0}
        4 + (1+2q)\log_2\left(p_0\star q\right) + (3-2q)\log_2\left(1-p_0 \star q\right) = 0.
    \end{equation}

    \item For a fixed $q\in[0,1/2)$, $\overline{C}(p,q)$ for $p_0 \leq p\leq 1/4$ is a decreasing linear function in $p$ that intersects the p-axis at $p = 1/4$. Furthermore, $\overline{C}(p,q)$, $p_0\leq p\leq 1/4$ is in fact the \textit{tangent} to the curve $1-h_2(p \star q)$ at $p=p_0$.
\end{itemize}
The proof of the above can be found in appendix \ref{solutionform}. In summary, for $q\in [0,1/2)$, we have
\begin{equation*}
    \overline{C}(p,q) = \begin{cases}
        1-h_2(p\star q) & 0\leq p \leq p_0 \\
    \frac{1-4p}{1-4p_0} \left ( 1 - h_2 \left(p_0\star q \right) \right ) & p_0\leq p \leq 1/4 \\
    0& p \geq 1/4
    \end{cases}
\end{equation*}
where $p_0$ is implicitly given by \eqref{Eqp_0}. In Fig. \ref{BSCupperboundsfig}, we plot $\overline{C}(p,q)$ as a function of $p$ for various values of $q$, specifically, $q=0.0,0.1,0.2$.

\begin{figure}
    \centering
    \includegraphics[width=0.485\textwidth]{BSC_v1}
    \caption{Upper bounds $\overline{C}(p,q)$ and lower bounds $\underline{C}(p,q)$ on the capacity of BSC($q$)-ADV($p$)-FS as a function of $p$. The cut-off value of $p$ beyond which $\overline{C}(p,q)=0$ is $p=1/4$ independent of $q$.}
    \label{BSCupperboundsfig}
\end{figure}

\subsection{An Achievable Rate $\underline{C}(p,q)$}

\begin{theorem}
\label{achratenfb}
The capacity $C(p,q)$ of BSC($q$)-ADV($p$)-FS is at least $\underline{C}(p,q)=\overline{C}\left ((p \star q),0 \right)$.
\end{theorem}
\begin{proof}
From \cite{dey2013upper,chen2015characterization}, $\overline{C}(s,0)$ is a tight characterization of the capacity when there is no BSC present and Calvin has a total budget of $sn$ bit-flips. Since at channel use $k$, Calvin does not know if the BSC will cause a bit-flip, it can be shown by Chernoff bound that the total number of bit-flips is at most $\left((p \star q)+\epsilon\right)n$ with probability at least $1-e^{-\Omega(n\epsilon^2)}$. If we now assume that all of the $\left((p \star q)+\epsilon\right)n$ flips are chosen in an adversarial manner by Calvin, a rate of $\overline{C}((p \star q) + \epsilon,0)$ is achievable.
\end{proof}
In Fig. \ref{BSCupperboundsfig}, we also plot achievable rates $\underline{C}(p,q)$ for $q=0,0.1,0.2$. As noted before, the gap between upper and lower bounds increases with $q$.

\section{Conclusion}
In this work, we considered communicating over a stochastic channel (BEC/BSC) in the presence of a powerful adversary who can spy on both communicating terminals and inject further erasures/bit-flips at the input of the channel. For erasures, we gave a complete capacity characterization and for bit-flips, we proved interesting converse and achievability bounds. Future work includes characterizing capacity tightly for bit-flips and for the case where the adversary has no feedback snooping.

\bibliographystyle{IEEEtran}


\section{Introduction}

Training reinforcement learning agents to solve environments with large, complex action spaces is a notoriously difficult task~\cite{kanervisto_2020}. Several methods have been proposed to try to either reduce the space of actions by re-using model outputs for different action types \cite{masson_2016, vinyals_2017}, provide side information to facilitate the exploration of large numbers of possible actions \cite{samvelyan_2019, ontan_2013, justesen_2018}, or simplify the manipulation of the action spaces through action embeddings via mechanisms such as attention and graphs networks \cite{openai_2019, ma_2019, ammanabrolu_2020}.
In this paper we propose a {\em Conditional Action Tree} as a paradigm to generalise several of these methods. {\em Conditional Action Trees} can be used to describe action spaces in a way that naturally reduces the required policy model output size whilst also allowing action parameterisation and action reduction using invalid action masking. We show how many of the action spaces frequently found in single, multi-agent and Real Time Strategy (RTS) games can be described using {\em Conditional Action Trees}. We also show that agents that have access to {\em Conditional Action Trees} as part of their state observations can learn high performing policies. We present several experiments where we purposefully modify the action space of a game environment to include several increasingly more complex features, whilst keeping the observation space and game mechanics consistent. In these experiments we show that agent operating with {\em Conditional Action Trees} maintains the performance of those operating with common action space constructions while significantly compressing the number of outputs, or \textit{logits}, required to furnish the policy distribution.

In addition to these experiments we also perform several ablation studies to show various possible modifications to the {\em Conditional Action Tree} formulation and how they can affect training.

The results suggest that the {\em Conditional Action Trees} could offer an alternative to generically handle complex combinatorial action spaces with multiple components. As part of this work, {\em Conditional Action Trees} are made available for all environments in the Griddly Framework~\cite{bamford2020griddly}.

\section{Background}

In a discrete action setting, reinforcement learning (RL) has typically been adapted to environments with simple and small action spaces. Accordingly the implications that the size could have for the agent have been relatively overlooked. Let us start by considering a single actor-critic agent with a small repertoire of actions that consists in motion operations (e.g. up, down, left and right). In this setting, a policy will provide a probability distribution weighting each of the four directions. The agent then can sample this policy to select which action to apply to the environment. However these small manageable action spaces tend to be confined to either simple games or toy environments. The situation changes as we move to tasks requiring combinatorial actions such as in robotics~\cite{korenkevych_2019}, finance~\cite{yang_2020} and games that involve action spaces with several moving parts and interdependent components. For the latter, RTS games provide instances of actions spaces that can be particularly complicated. To consider a few examples, StarCraft II\cite{vinyals_2017}, $\mu$RTS~\cite{huang_2020} and BotBowl~\cite{justesen_2019} allow control of multiple individual units either by selecting their locations and then issuing commands to those units. Some of the units can perform certain types of actions that are not accessible to other units. Furthermore, some of those actions in turn require additional parameters. For instance, selecting a combat unit that can target several potential locations in the game requires to specify them. Moreover, the particular type of combat actions might be tied or dependent on the unit selected. Several techniques have been proposed to handle this kind of action spaces. \cite{kanervisto_2020} proposes several ways of shaping actions spaces and their relative advantages and disadvantages across several games. For the rest of this section we briefly review two strategies for action space shaping that have been recently proposed in the literature.

\subsection{Parameterised Actions}

Parameterised action spaces commonly take the form of an action $a$ made from two components ${c_0, c_1}$ where the first component is a {\em type} of action and the second is a {\em parameter}. In \cite{masson_2016}, this action space shaping strategy was applied in the \textit{RoboCup 2D Half-Field-Offense} environment to beat the state-of-the-art hard-coded bots. The first action component defines whether the agent will \textit{dash, turn, tackle} or \textit{kick}. The second component defines continuous parameters for each of these actions. Four sets of parameters are used, however only one of them is used at each time-step depending on the action type selection. In larger environments such as RTS games, requiring parameters for every action quickly becomes infeasible as the number of action types increases. To contextualise the effect this can have for the size of the policy representation consider the example of \textit{BotBowl}. The game contains 17 action types that require an $x$ and $y$ position parameter. If we proceeded to parameterise the action space, 17 sets of $x$,$y$ positions would need to be predicted at each time step. From the point of view of an RL agent, the problem is exacerbated if we consider that the policy would have to specify each combination of $x$ and $y$ position. In a traditional \textit{BotBowl} map ($25\times5$) this would lead to a policy that requires to output $17 + 17\times25\times15 = 6,382$ logits (i.e. unnormalised scores) to parameterise these actions. The number grows exponentially with the map size, a $30\times30$ map for example, would require $17 + 17\times30\times30 = 15,317$ logits.

\subsection{Autoregressive Policies}

\begin{figure}
    \centering
    \input{images/autoregressive_pol}
    \caption{An autoregressive policy can be graphically represented as a directed acyclic graph where we can illustrate the dependency of a component $c_k$ on the previous components $c_{<k}$.}
    \label{fig:autoregressive-policy}
\end{figure}

The curse of dimensionality and the combinatorial explosion faced in certain action spaces renders the typical action selection approach highly impractical. An alternative comes from reflecting on the structural relations that exist in complex action spaces. For example, when comparing among all the potential actions that an agent could choose to enact, not all of them will belong to the same level of abstraction. Some actions will be more self-contained, whereas others may need a group of actions to be properly contextualised. Actions can also manifest to an agent as affordances, that is, arising from its coupling with the environment at a particular moment. Moreover, some actions also exert some degree of influence on each other, for instance mutual exclusivity or forming other types of associations.

It is possible to capture some of these notions more concretely by representing a policy in a more expressive manner. In \cite{vinyals_2017} the authors suggest an autoregressive model of the form:

\begin{equation}
    \pi(a|s) = \pi(c_0,\dots,c_k|s) =\prod_{k=0}^K{\pi(c_k|c_{<k}, s)}
\end{equation}

to decompose the action space into a sequence of sub-spaces. Instead of obtaining $a$ in the full action space, an agent samples multiple sub-actions or components $c_k$ that depend on the previous $c_{<k}$ choices (illustrated in Fig. \ref{fig:autoregressive-policy}). \cite{vinyals_2017} explores the usage of conditional policies within the context of StarCraft II. However they relax the constraints imposed by the autoregressive model opting for a policy $\pi(a|s) = \prod^K_k \pi(c_k|s)$. In \cite{vinyals_2019}, the approach is extended substantially as the architecture considers a conditional policy that captures the context of previous actions through different embeddings. The action sub-space decomposition is facilitated by an \textit{invalid action masking} scheme to prevent the agent from selecting actions that are invalid or cannot be performed in the current state, where a function identifier $c_0$ determines the number of subsequent function arguments $c_1 \dots c_k$. From the point of view of the implementation and the capacity required by a policy, this form of decomposition implies a significant reduction in the number of actions that are effectively considered. Here we also take an approach that places an invalid action masking scheme as a crucial component to tackle the issue of policy decomposition and describe it in more detail in Section \ref{sec:invalid-action-masking}.

\section{Conditional Action Trees} \label{sec:conditional-action-trees}

Conditional action trees (CAT) offer a generalisation of discrete action spaces to provide an interpretation of action selection as the process of traversing along a chained sequence of action components with different levels of dependency. To complete the characterization of a {\em Conditional Action Tree} we first need to define three main elements: {\em Action Trees}, {\em Valid Action Trees}, and finally {\em Conditional Masking}.

\subsection{Action Trees} \label{sec:action-trees}

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{images/action_tree.pdf}
    \caption{An action tree consisting of nine possible actions and two components $C_0 = 3$ and $C_1 = 4$. The possible action are move or attack in any of the four directions, attack in any of the four directions and finally to use a food item. {\em Move}, {\em Attack} and {\em Use} cannot be performed at the same time.}
    \label{fig:action-tree}
\end{figure}

We start by formulating a single action as a list of a fixed number of components $a = \{c_0, c_1 ... c_n\}$, where each component is a discrete value taken from a set of possible values for that particular component $c_k \in C_k$. Actions in the same component level are mutually exclusive. For example, \textit{move left} and \textit{move right} must be options within a single component $C_k$. The possible values of $C_k$ are determined first, by the specification of environment, and second by the values of previous selections $C_k = f(c_0, c_1, ... , c_{k-1})$.

These restrictions naturally allow the components to form a tree structure, where a path from the root node to any leaf forms the action. An example of an {\em action tree} is shown in Fig.~\ref{fig:action-tree}. Note that under this specification an environment requiring the agent to specify a single atomic action at each time step results in an {\em action tree} with a single component, $a = \{c_0\}$. Parameterised action spaces that contain an action type and a discrete action parameter can also be described by action trees with two components, $a = \{c_0, c_1\}$.

Previous work has touched upon the idea of using trees as a formalization of action spaces with multiple components such as in \cite{fan_2019}, where the tree structure is referred to as a {\em Hierarchical Action Space}. Other works have used action spaces that are similar to those used in this paper as examples of  action trees. The {\em Global Action Space} in \cite{huang_2019} for example can also be described as an {\em action tree}.

\subsection{Valid Action Trees} \label{sec:valid-action-trees}

We define a \textit{valid action tree} as a sub-tree of an action tree at a particular environment state, where the nodes of the sub-tree correspond to {\em possible} actions in that state. For example, consider the tree in Fig.~\ref{fig:action-tree}, an agent in a state where there are no enemies surrounding it and does not have food in its inventory has a {\em valid action tree} only consisting of the left-most {\em move} branch and its children.

In the context of reinforcement learning, a valid action tree is provided by the environment at each time step. Valid action trees are then used to construct the {\em Invalid Action Masks} which are described next in Section~\ref{sec:invalid-action-masking}. These masks index the child nodes that are available in the full action tree.

\subsection{Invalid Action Masking} \label{sec:invalid-action-masking}

Invalid action masking (IAM) \cite{huang_2020} is a technique used to stop agents from sampling actions that are invalid in a particular game state. IAM is useful in environments where the action space is large, and some of the actions are only available in certain states. For example in RTS games \cite{vinyals_2019, vinyals_2017, samvelyan_2019}, the agent's action may consist of selecting a unit or units from a large list, and then issuing commands to those units. The commands sent to those units can also be unique to particular unit types. This results in a large number of options in the action space that are invalid. In policy gradient and actor critic methods in deep RL, IAM is applied to the logits, $\textbf{l} \in \mathbb{R}^n$, produced by a neural network by replacing the logits corresponding to invalid actions with large negative numbers. This forces the probability of selecting those actions to tend towards 0.

For instance, let us assume a compound policy constituted by $K$ independent components, such that $\pi(a|s) = \prod^K_k \pi(c_k|s)$. This type of action policy could be described by:

\begin{equation}
    \pi(a|s) = [\pi(c_{0}|s), \pi(c_{1}|s), \dots, \pi(c_{k}|s)]
    \label{eq:indep_pol}
\end{equation}

For each of the components in equation \ref{eq:indep_pol}, a value is selected following a softmax sub-policy. We can create a mask to modify the logits to assign large negative numbers to actions deemed as non-viable or inaccessible. The modified logits result in $\hat{\textbf{l}} = \textbf{l} + \textbf{m}$ where $-\infty < m_i \ll 0$. It then follows that the {\em masked} logits alter the probability of a value of $c_i$ of being sampled:

\begin{equation*}
    \pi(c_i|s) =
    \begin{cases}
        0 & \text{if } m_i \longrightarrow - \infty \\
        \frac{e^{l_i}}{\sum_j^N{e^{l_j}}}  & \text{if } m_i \quad=\quad0
    \end{cases}
\end{equation*}

 In PySC2 \cite{vinyals_2017}, $\mu$RTS \cite{ontan_2013} and BotBowl\cite{justesen_2019} action masks can be constructed from lists of available actions that are provided by the environment implementations, however, these action masks do not take into account that the masking of some sub-actions can depend on the sampled values of others. As an example, in an environment with units that are selected by coordinates and the set of available actions for each unit is disjoint, the mask for the available actions is dependent on the selection of the unit. Masks that are naively constructed using these lists can still lead to select actions that are not available, as the list does not take into account the selection of the unit. \cite{huang_2021} introduces a two-step method for generating masks where the unit location is selected using masked logits and then a second mask is generated based on that selection. This significantly improves training as the mask for unit actions is dependent on the selected unit.

\subsection{Conditional Masking}
\label{sec:cond_mask}

The two-step method of masking in \cite{huang_2021} can be generalised to an n-step masking method when the environment provides a valid action tree as described in Section~\ref{sec:valid-action-trees}. We refer to this generalization of action selection and masking as a \textit{Conditional Action Tree (CAT)}.

A CAT is constructed by adding a mask at each node of a valid action tree, defining which child nodes of the complete action tree are available.
An action is constructed by starting at the root node of the valid action tree and selecting a child node from the masked distribution. This child node contains the mask to use for the next component. Thus, first the mask is obtained as $\textbf{m}_{k+1} \sim p(\textbf{m}_{k+1}|c_k)$, to produce a masked sub-policy to sample a component $c_{k+1} \sim p(c_{k+1}|\mathbf{m}_{k+1},s)$. This process continues until all action components have been sampled. The full compound policy, as illustrated in Fig. \ref{fig:masked_pol}, is factorised as:

\begin{figure}
    \centering
    \input{images/mask_dep_pol}
    \caption{A graphical model representing the policy as a joint distribution of masks $m$ and components $c$. In a CAT, a component $c_0$ is sampled from the options allowed by the mask $\textbf{m}_0$. The next mask $\mathbf{m}_1$ depends on $c_0$ which in turn constrains the next possible component $c_1$. The process is repeated until all $c_k$ have been sampled.}
    \label{fig:masked_pol}
\end{figure}

\begin{equation}
    \pi(a|s) = p(\mathbf{m}_0) \prod_k^K p(\mathbf{m}_{k+1}|c_k)p(c_k|\mathbf{m}_k,s)
\end{equation}

\section{Actor-Critic with Conditional Action Trees} \label{sec:policy-gradient-methods}

\subsection{IMPALA}

The description of the action spaces provided by CAT is naturally agnostic to the choice of the RL algorithm. We examine this perspective within the context of IMPALA, an actor-critic based framework introduced in \cite{espeholt_2018}. Unlike A3C \cite{mnih2016} or other similar distributed approaches where the agents share their gradients, IMPALA considers the acting and the data collection as independent from the learning step. That is, it separates the learners who are in charge of computing the gradients and sharing the most recent parameters, from the actors whose role is to execute a policy, only sharing back with the learners the observations gathered during an episode.

\subsection{V-trace and masking}

As an actor-critic, IMPALA learns $V_\theta(s)$ parameterised by $\theta$ to be used as part of the baseline, and a policy $\pi_\phi$ parameterised by $\phi$. Each actor executes their own policy $\mu$ by retrieving the latest policy $\pi$ from the learner. Meanwhile the learner updates continuously the parameters $\theta$ and $\phi$. As the process occurs in parallel and in a decoupled manner, there will be a discrepancy between the policy $\mu$ from an actor and $\pi$. Namely, the trajectories $(s_t,a_t,r_t \dots)$ collected by an actor come from a policy $\mu$ that has become obsolete with respect to $\pi$. IMPALA proposes to address these off-policy corrections by introducing a v-trace target,

\begin{equation}
    v_t  = V(s_t) + \sum_{i=t}^{t+n-1} \gamma^{i-t} \big(\prod_{j=t}^{i-1} u_j\big) \delta_i V
\label{eq:v-trace}
\end{equation}

where $\delta_i V$ corresponds to a temporal difference term,

\begin{equation*}
    \delta_iV = \rho_i (r_i + \gamma V(s_{i+1}) - V(s_i))
\end{equation*}

the v-trace adjusts the weight of the contributions provided by the actors through the presence of two truncated importance sampling weights $\rho_i=\min(\overline{\rho},\frac{\pi}{\mu})$ and $u_j=\min(\overline{u},\frac{\pi}{\mu})$. Thus the second part of v-trace target acts as a correction term. For example assuming $\overline{p}$ and $\overline{u} \geq 1$, if $\mu>\pi$ the learner would downweight the observations and actions followed by the actor. Intuitively, if this ratio tends towards a low number it indicates that the policies have diverged significantly. The extent to which more recent $\delta_i V$ affect the update of a previous $V$ is captured by the product of $u_{t:i-1}$ where $\overline{u}$ serves as a hyperparameter controlling the convergence speed towards $V$. In turn, $\rho$ determines to which $V$ we converge. A $\overline{\rho}$ close to 0 leads convergence towards a $V^\mu$ as the correction term becomes negligible in the v-trace target.

It is important to note that for CAT we do not just consider a single set of importance sampling weights $\{\rho, u\}$ but instead we must account for multiple corrections dependent on the various sub-policies such that $\rho_{k,i} = min(\overline{\rho}, \frac{\pi(c_k|m_k,s)}{\mu(c_k|m_k,s)})$ and $u_{k,j} = min(\overline{u}, \frac{\pi(c_k|m_k,s)}{\mu(c_k|m_k,s)})$ for a sub-policy $k$. Moreover, we must synchronize the masks applied to $c_k$ in both $\pi$ and $\mu$. Similarly, for updating the policy parameters $\phi$ we adapt,

\begin{equation*}
    \rho_{k,i}\nabla_\phi \log \pi_\phi(c_k|m_k, s)(r_t + \gamma v_{t+1} - V_\theta (x_t))
\end{equation*}

to consider the inclusion of the masks and to propagate the gradients to all sub-policies.

\section{Experiment Setting} \label{sec:experiment-setting}

\begin{figure*}
    \centering
    \includegraphics{images/conditional_action_tree.pdf}
    \caption{Image of a conditional action tree from a 5x4 {\em Clusters} level configured in with the MSa action space as described in Section~\ref{sec:action_space_variations}. The agent is configured with an action space with 4 components, the agent selects which object to move by it's position and it's colour, it can then choose which direction to move the {\em box}. The CAT shown contains the selected action component $c_k$ and the mask $\textbf{m}_k$ for each possible valid combination of components.}
    \label{fig:conditional-action-tree}
\end{figure*}

\subsection{The "Clusters" Game}

\begin{figure}
    \centering
    \begin{subfigure}{.5\linewidth}
        \centering
        \includegraphics[width=.9\textwidth]{images/global_clusters.png}
        \caption{Global}
    \end{subfigure}%
    \begin{subfigure}{.2\linewidth}
        \centering
        \includegraphics[width=.9\textwidth]{images/po_clusters.png}
        \caption{Agent}
    \end{subfigure}%
    \caption{An example of a level in the Clusters game, showing (a) the entire game and (b) the viewpoint of the agent.}
    \label{fig:clusters}
\end{figure}

We perform our experiments in the {\em Clusters} environment provided by Griddly~\cite{bamford2020griddly}. {\em Clusters}\footnote{\url{https://griddly.readthedocs.io/en/latest/games/Clusters/index.html}} is a game in which coloured {\em boxes} must be clustered together in specific locations defined by the environment level. The environment contains five levels with a set of movable coloured {\em boxes} and a single fixed-position {\em block} of each colour. The agent receives a reward of +1 each time it pushes a coloured {\em box} against a fixed location {\em block} of the same colour. When a coloured {\em box} is pushed against its respective {\em block}, it becomes a {\em block} itself. If all {\em boxes} are converted to {\em blocks} the episode is completed successfully. Some levels also contain {\em spikes} which give the player a negative reward (-1) and terminate the episode if the agent or any {\em boxes} collide with them.

The observation space of the agent consists of a $5\times5$ grid where the agent itself is situated at the center-bottom of the grid as shown in Fig.~\ref{fig:clusters}. Each cell of the $5\times5$ grid contains 10 binary values describing whether an object is present in each cell. The 10 objects are as follows: three (red, green, blue) coloured {\em boxes} and three associated {\em blocks}, {\em walls}, {\em spikes}, the agent and finally a {\em broken box} which only appears in the final state of an episode if a coloured {\em box} is pushed against {\em spikes}.

\subsection{Action Space Variations} \label{sec:action_space_variations}

By default, the agent's movement is restricted to moving forward one position, or rotating $\pm 90$ degrees every step. {\em Boxes} are "pushed" by the agent when the agent attempts to move into the cell occupied by the {\em box}.

In our experiments, we modify these action spaces to make it increasingly more complex whilst keeping the game mechanics, observation space and reward scheme consistent. This allows us to test the Conditional Action Tree formulation on different action spaces with minimal influencing factors. The only significant change we make to the environment across experiments is when we remove the avatar and allow the agent to move {\em boxes} independently by selecting their $x$ and $y$ coordinates. These action space variations are explained below:

\subsubsection{\textbf{Move (M)}}

The first action tree variation is the default action space provided by the {\em Clusters} environment. The action space consists of rotate left, right and move forward. As mentioned in Section~\ref{sec:action-trees}, this is equivalent to an {\em Action Tree} with a single component $a = \{c_0\}$, with $c_0 \in {0,1,2,3}$.

\subsubsection{\textbf{Move + Push (MP)}}

Next we modify the action space to consider that the agent can no longer {\em push} boxes by simply moving into the location occupied by them. We define a separate {\em push} action that must be performed in order to move any of the boxes. The {\em push} action has no effect unless there is a box directly in front of the agent. The {\em move} action is left unmodified, other than the fact that it can no longer be used to push boxes. As the {\em move} and {\em push} actions are mutually exclusive they are confined to the first level in the tree $C_0 = \{0,1\}$, whilst the second component $C_1$ contains either the three move parameters or the single {\em push} parameter.

\subsubsection{\textbf{Move + Push + Separate colours (MPS)}}

This action space configuration contains the same modifications as the MP variant, however it splits the {\em push} component into three to account for the separate colours. The agent must select the correct {\em push} action, depending on which colour {\em box} it is pushing (i.e. push green, push blue, push red). Similarly to {\em MP}, the action space consists of two components, but the first one now contains the three different push actions instead of one, that is $C_0 = \{0,1,2,3\}$. The second component $C_1$ remains the same.

\subsubsection{\textbf{Move - Agent (Ma)}}

To make the action space significantly larger we remove the agent and the associated ego-centric partial observability. Thus the input consists of the entire $13\times10$ grid with the same 10 binary digits per cell. The {\em boxes} are now moved first by selecting their $x$ and $y$ coordinates and then by issuing the direction where to move it. This action space has three components: $C_0 = \{ \text{valid x coordinates}\}$, $C_1 = \{ \text{valid y coordinates} \}$ and $C_2 = \{0,1,2,3\}$ referring to the movement directions {\em up}, {\em down} {\em left} and {\em right}.

\subsubsection{\textbf{Move + Seperate colours - Agent (MSa)}}

The final and largest action space we consider starts with the same formulation as {\em Ma}, but separates the colour components in the same way as done in {\em MPS}. This results in an action space with four components: x, y, action type and action parameters. An example of a conditional action tree for this space is shown in Fig.~\ref{fig:conditional-action-tree}

\subsection{Baselines} \label{sec:baselines}

For each of the variations of the action space described in the previous section, we compare against two baselines which are designed to show the benefits and limitations of the CAT paradigm. The baselines modify only the way that the model interacts with the action space in terms of number of logits required. The number of actions and mechanics of the game are consistent.

\subsubsection{\textbf{No Masking}}

For the first comparison we use the same action components as a CAT but remove the Invalid Action Masking entirely. This means that the component selections are made independently of each other and invalid actions can be selected.

\subsubsection{\textbf{Depth-2}} \label{sec:depth-2}

The second comparison also uses a conditional action tree structure, but flattens the action tree to only a depth of two. The separate $x$ and $y$ components (only available in MSa and Ma) are flattened into a single $xy$ component. Additionally the action type and action parameter components are flattened into a single selection. This flattening process was also considered in \cite{kanervisto_2020} where multi-discrete actions are flattened into single discrete spaces. Table~\ref{tab:policy-logits} shows the number of logits per-component for all experiments and the equivalent number of logits required in the depth-2 representation.

\begin{table}[]
    \centering
    \begin{tabular}{lrlllr}
        \multicolumn{1}{l|}{}    & \multicolumn{1}{c}{$|C_0|$} & \multicolumn{1}{c}{$|C_1|$}  & \multicolumn{1}{c}{$|C_2|$}  & \multicolumn{1}{c|}{$|C_3|$}                 & \multicolumn{1}{r}{Total Logits} \\ \hline
        \multicolumn{1}{l|}{\textbf{M}}   & 3                      & \cellcolor{lightgray}         & \cellcolor{lightgray}      & \multicolumn{1}{l|}{\cellcolor{lightgray}} & 3                                \\
        \multicolumn{1}{l|}{\textbf{MP}}  & 2                      & \multicolumn{1}{r}{3}         & \cellcolor{lightgray}      & \multicolumn{1}{l|}{\cellcolor{lightgray}} & 5                                \\
        \multicolumn{1}{l|}{\textbf{MPS}} & 4                      & \multicolumn{1}{r}{3}         & \cellcolor{lightgray}      & \multicolumn{1}{l|}{\cellcolor{lightgray}} & 7                                \\
        \multicolumn{1}{l|}{\textbf{Ma}}  & 13                     & \multicolumn{1}{r}{10}        & \multicolumn{1}{r}{4}      & \multicolumn{1}{l|}{\cellcolor{lightgray}} & 27                               \\
        \multicolumn{1}{l|}{\textbf{MSa}} & 13                     & \multicolumn{1}{r}{10}        & \multicolumn{1}{r}{4}      & \multicolumn{1}{r|}{3}                     & 30                               \\
        \multicolumn{6}{c}{\textbf{Depth-2}}                                                                                \\
        \multicolumn{1}{l|}{\textbf{M}}   & 3                      & \cellcolor{lightgray}         & \cellcolor{lightgray}      & \multicolumn{1}{l|}{\cellcolor{lightgray}} & 3                                \\
        \multicolumn{1}{l|}{\textbf{MP}}  & 4                      & \cellcolor{lightgray}         & \cellcolor{lightgray}      & \multicolumn{1}{l|}{\cellcolor{lightgray}} & 4                                \\
        \multicolumn{1}{l|}{\textbf{MPS}} & 6                      & \cellcolor{lightgray}         & \cellcolor{lightgray}      & \multicolumn{1}{l|}{\cellcolor{lightgray}} & 6                                \\
        \multicolumn{1}{l|}{\textbf{Ma}}  & 130                    & \multicolumn{1}{r}{4}         & \cellcolor{lightgray}      & \multicolumn{1}{l|}{\cellcolor{lightgray}} & 134                              \\
        \multicolumn{1}{l|}{\textbf{MSa}} & 130                    & \multicolumn{1}{r}{12}        & \cellcolor{lightgray}      & \multicolumn{1}{l|}{\cellcolor{lightgray}} & 142
    \end{tabular}
    \caption{This table shows the number of action components, their sizes in term of number of logits and the total logits needed in the policy output for the action space variations described in Section~\ref{sec:action_space_variations}. We also show the number of logits that are required in the {\em Depth-2} model.}
    \label{tab:policy-logits}
\end{table}

\subsection{Masking Ablation}

To show that structure of the tree and the resulting conditional masking has an effect on the learning of the policy, we perform an experiment where we relax the conditional masking restrictions and compare it against the fully conditional masking.
We relax the conditional masking of the tree by collapsing the masking across the tree breadth-wise, so all masking is effectively a union of all the possible masks at each depth. This method is equivalent to applying a single mask to the entire action space with no consideration for dependencies between action selections. We refer to the relaxed {\em Collapsed} and full {\em Conditional} masking options in further sections as CAT\_CL and CAT\_CD respectively.

\subsection{Model Architecture}

We keep the model architecture consistent throughout all experiments as much as possible. The size of the model input observations differs between partially observable agent-based environments (\textbf{M}, \textbf{MP}, \textbf{MPS}) and unit-selecting environments (\textbf{Ma}, \textbf{MSa}). The partially observable environments have a $5\times5\times10$ observation space, while for the unit-selecting environments it is $13\times10\times10$. Additionally, the final layer in each experiment outputs the number of logits shown in Table~\ref{tab:policy-logits}. The model itself contains two convolutional layers with padding 1 and kernel size 3 that up-scales the number of values in each channel to 32 and then 64 respectively, whilst keeping the width and height the same. After these layers, the output tensor is flattened and then passed through two linear layers with 1024 and 512 neurons. We then use a separate actor and critic head. The actor head contains a further two linear layers, first to compress to 256 nodes and then a final layer to output predicted logits. The critic head contains a single layer which outputs the single predicted value.

\section{Results}

\begin{figure*}
    \centering
    \includegraphics[width=.9\linewidth]{images/plots_training.pdf}
    \caption{The average episode reward during training of the 5 different action space variations as described in Section~\ref{sec:action_space_variations}. For each of the 5 action space variations, we compare three policies with the same action tree structure, but different masking methods: No Masking, CAT\_CD (conditional) and CAT\_CL (collapsed). We also provide a comparison with a model policy that uses an action tree limited to depth 2 as described in Section~\ref{sec:depth-2}}
    \label{fig:results}
\end{figure*}

In total we run 4 experiments on each variation of the action space of the \textit{Clusters} game. The four experiments contain the two baselines as previously described, and two versions of masking (CAT\_CL and CAT\_CD).

The first variation \textbf{M} provides evidence that the formulation of conditional action trees generalise to simple action spaces. In this environment, all variations of the action space are almost identical and therefore have similar performance. Masks in this environment have little effect because only a few actions are ever invalid. \textbf{MP} and \textbf{MPS} variations begin to show that the fully conditional tree CAT\_CD and the depth-2 action tree policies learn faster and plateau at high-scoring policies. Depth-2 action policies in these variations are in fact slightly better performing than the more hierarchical formulation of the Conditional Action Tree, in addition of using one less logit in their policies. The reason for this is that in the \textbf{MP} and \textbf{MPS} the structure of the associated action tree has a degree of 1 in all of the {\em push} nodes, making the tree structure redundant for the push actions. In cases like these, where parent nodes have only single children, it is more efficient to flatten these nodes into a single set of children.

Conditional Action Trees excel in the variations with the highest branching factors. \textbf{Ma} and \textbf{MSa} both require the policy to select an individual unit to perform an action at each time step. As expected, the depth-2 policy and CAT\_CD have similar performance as they are both CATs, but CAT\_CD splits the $x$, $y$ selection into separate components, which results in a greater than 4x reduction in the number of logits required by the policy, with no loss in performance.

The results for experiments on all five test environments with {\em Collapsed} (CAT\_CL) masks are also shown in Fig.~\ref{fig:results}. We can see that with {\em Conditional Action Trees} the full {\em Conditional} (CAT\_CD) masking strategy is important for efficient training, as the {\em Collapsed} masking strategy performs similarly to the {\em No Masking} Baseline.

\section{Discussion}

Trees are a useful data structure across many fields of computer science, and can provide a natural representation for action spaces. Although the formulation and the experimental setting focused on discrete action spaces, we hypothesize that in principle the formulation can be extended to continuous spaces by implementing a similar parameterisation to structure the action components associated to specific densities. To the best of our knowledge this direction has not been explored.

It is important to note that the degree of subtrees in a CAT should be taken into consideration when deciding on parts of the tree that could be flattened, as this can lead to unnecessary increase in policy size.

The current work presented the CAT formulation in five toy scenarios intended to recreate, with different levels of complexity, the conditions frequently exhibited in various single, multi-agent and RTS games. Further work will be required to analyse the behavior of the CAT in more complex domains such as $\mu$RTS or BotBowl. Part of the current limitation resides in adapting these and other environments to provide \textit{Valid Action Trees}. With a {\em Conditional Action Tree} the parameterised part of BotBowl's action space could be reduced from $6392$ logits to $25+15+17 = 57$

Other relevant research on how to handle large action spaces has applied techniques such as evolutionary algorithms \cite{baier_2018, justesen_2018}. These proposals have also been tested in scenarios that require multiple actions per time-step. A naive approach to work with CATs within this context would be to recursively append the tree to its own leaf nodes, resampling until a condition specifying the required number of actions is fulfilled.

In its current form a CAT makes specific assumptions about the conditional dependencies between actions (Section \ref{sec:cond_mask}). Following \cite{vinyals_2019}, a potential future research avenue is to explore the possibility of modelling more complex dependencies. Namely, by contextualizing further the selection of a $c_k$ with with an encoding learned from previous components $c_{<k}$.

\subsection{Entropy reduction}

The process by which an agent acquires a policy in reinforcement learning is essentially an exercise in reducing its behavioral uncertainty. Although it remains important that the agent maintains a level of flexibility that can support an adequate generalization \cite{ziebart2008,haarnoja2017}. It must effectively has to be able to discriminate the actions that are beneficial from those that are not in a particular state. We can interpret this procedure of action discrimination as a process of entropy reduction, as an initial high entropy policy is transformed by redistributing the probability mass or density to weight those actions that have been identified as more favorable. For large action spaces it is evident that this process becomes more complex as the behavioral possibilities explode. The view posited by CAT is that it is possible to exploit the structure of the action space to facilitate the acquisition of behaviorally relevant policies as we can state that for two arbitrary segments of the action space, $C_i$ and $C_j$, the mutual information between them is $I(C_i;C_j) \geq 0$. This implies that there can be information to be gained by using existing relationships between actions. To express it differently, conditioning guarantees us that $H(C_i|C_j) \leq H(C_i)$ with equality iff $p(c_i,c_j) = p(c_i)p(c_j)$. Thus constructing an action tree becomes a tool that contributes to the process of entropy reduction at the level of the policy as it decomposes what is potentially a large flat action space into multiple smaller sub-spaces.

\section{Conclusion}

In this paper we have proposed a formalisation of a tree structure for representing discrete action spaces with any number of components. We have provided the required steps to adapt already existing action spaces to conform to a {\em Conditional Action Tree}. From a technical perspective, a side effect of imposing a structure to the action space is the reduction of the elements considered by a policy. The experiments showed that this modification does not reduce the sample efficiency during training and achieves comparable performance while resulting in significantly smaller models with less parameters.

As part of the this work, Griddly~\cite{bamford2020griddly} implements built-in functionality for generating {\em Valid Action Trees} and we provide all reproducible examples in a github repository~\footnote{\url{https://github.com/Bam4d/conditional-action-trees}}. We also provide all training parameters, statistic and videos using Weights and Biases~\footnote{\url{https://wandb.ai/chrisbam4d/conditional_action_trees}}.

We encourage the developers of reinforcement learning environments, especially those with large discrete action spaces to provide {\em Valid Action Tree} observations in their environments.

\section*{Acknowledgment}

We would like to thank Paulo Rauber, Simon Lucas and Shengyi Huang for their valuable feedback and to the ITS Research team at Queen Mary University of London for providing technical support necessary to run the simulations. This research utilised Queen Mary's Apocrita HPC facility, supported by QMUL Research-IT. \url{http://doi.org/10.5281/zenodo.438045}.

\bibliographystyle{IEEEtran}