text:
\section{INTRODUCTION}
Deep reinforcement learning (RL) has yielded many recent successes in solving a variety of complex problems ranging from video games, self-driving vehicles, robotic manipulators as well as various other simulated and real scenarios \cite{Mnih2015a, andrychowicz2018learning, lillicrap2015continuous}.
RL, however, is a trial-and-error based method that is inherently sample inefficient and often requires large computational and data resources to learn reliable policies. The trial-and-error nature of RL results in random behaviors at the beginning of training, which makes RL poorly suited for certain tasks that require more guarantees on performance, such as physically embodied tasks.  Additionally, traditional RL approaches are typically very sample inefficient and have slow convergence rates. This is even more problematic in tasks with either large state and action spaces or environments with relatively long time horizons, which can require tens of millions of training samples \cite{Bellemare2013, mnih2013playing}.

One approach for overcoming these limitations is learning from example behavior or demonstrations of the desired task from expert policies. These expert policies can come from either some other autonomous agent or directly from a human.
Traditionally, learning from human demonstrations via direct behavior cloning can lead to high-performance policies with significantly less computation time given that the algorithm has access to high-quality demonstration data covering the most likely scenarios to be encountered when the agent is operating.
However, in real-world scenarios, this is often not the case as expert data is limited and thus most imitation learning techniques that learn from demonstrations, often fail when the agent encounters new scenarios that were never seen before in the training data due to the distributional drift problem \cite{Levine2019}. Since we desire that our artificial intelligence (AI) agents learn policies robust enough to handle situations that were not demonstrated by the human expert, relying solely on demonstrations that cover the span of possible scenarios is simply not feasible.

One possible solution to improve learning efficiency for RL agents is to break-down complex tasks into a series of easier ones to solve problems that form a curriculum.
Curriculum learning is a relatively new technique designed to speed up reinforcement learning by adjusting the difficulty of the task according to the agent's current capabilities.
Curriculum learning in AI draws inspiration from the curriculum learning techniques that humans use on a daily basis to teach complex tasks and concepts. In the field of reinforcement learning, curriculum learning has shown great promise in improving the speed and effectiveness of RL agents \cite{salimans2018learningmontezuma,rudin2021learningtowalk,miki2022wyldanimal}. The main challenge in curriculum learning is how to design a proper curriculum for a complex problem.
Our solution is to leverage a technique called \emph{Automatic Curriculum Learning} (ACL) from human demonstrations in which we attempt to extract a reasonable curriculum automatically from expert human demonstrations of the task \cite{salimans2018learningmontezuma}. Using human demonstrations as an implicit curriculum, we can incrementally allow the agent to learn from different portions of the demonstration, starting from a simpler task (i.e. near the end of the demonstration) and eventually building the agent's ability to perform more and more complex tasks.

In this paper, we improve upon ACL, previously only  demonstrated in simple Atari tasks \cite{salimans2018learningmontezuma}, in which we use a single human demonstration to define an automatic curriculum to guide the exploration of an actor-critic RL agent to solve complex tasks within the challenging and high-dimensional state-space of \emph{StarCraft II}, as illustrated in Fig.~\ref{fig:overall_concept}.
We train deep reinforcement learning agents that can command multiple heterogeneous actors using an automatic curriculum learning technique where starting positions and overall difficulty of the task are controlled using a single human demonstration.
Our results show that an agent trained via ACL outperform state-of-the-art deep reinforcement learning baselines and match the performance of the human expert in a simulated command and control task in \textit{StarCraft II} modeled over a real military scenario.

\begin{figure}
    \centering
    \includegraphics[width=0.75\textwidth]{overall_concept.eps}
    \caption{High-level overview of the proposed method. A single human demonstration is used to automatically generate a curriculum for the reinforcement learning agent to solve complex tasks within the challenging and high-dimensional state-space of \emph{StarCraft II}.}
    \label{fig:overall_concept}
\end{figure}

\section{METHODS}

\subsection{StarCraft II Environment}

\textit{StarCraft II} has a number of difficult challenges for AI algorithms that make it a suitable simulation environment for experimentation and development of deep reinforcement learning agents. For example, the game has notoriously complex state and action spaces, can last tens of thousands of time-steps, can have thousands of actions selected in real time, and can capture uncertainty due to the partial observability or ``fog-of-war''. Further, the game has multiple heterogeneous assets, that make learning infeasible for most traditional off-the-shelf RL techniques.

In this paper, we utilize a custom made \textit{StarCraft II} map that we developed in a previous paper \cite{dsifirstyear,goecks2022ongames} called ``TigerClaw". TigerClaw is a tactical command and control scenario where Blue Force units must engage and eliminate the Red Force units that currently occupy a neutral city.
To facilitate training our RL agents, we developed a custom gym wrapper built around Deepmind's  \textit{StarCraft II Learning Environment} (SC2LE) \cite{vinyals2017starcraft}. To implement off-the-shelf deep reinforcement learning algorithms we utilize \textit{RLlib} \cite{liang2018rllib}, a library that provides scalable software primitives and high-quality reinforcement learning algorithms on a high performance computing system.
\textit{DeepMind}'s SC2LE framework \cite{vinyals2017starcraft} exposes \textit{Blizzard Entertainment}'s \textit{StarCraft II} Machine Learning API as a reinforcement learning environment. This tool provides access to \textit{StarCraft II}, its associated map editor, and an interface for RL agents to interact with \textit{StarCraft II}, getting observations and sending actions.

\begin{figure}
    \centering
    \subfloat[\label{fig:TigerClaw_a}]{\includegraphics[width=0.255\textwidth]{tigerclaw.png}}\hfill
    \subfloat[\label{fig:TigerClaw_b}]{\includegraphics[width=0.405\textwidth]{tigerclaw_sc2_units.png}}\hfill
    \subfloat[\label{fig:TigerClaw_c}]{\includegraphics[width=0.301\textwidth]{tigerclaw_aurora2.png}}
    \caption{Illustration of the \textit{TigerClaw} scenario map (Fig.~\ref{fig:TigerClaw_a}), how it was represented in \textit{StarCraft II} using MILSTD2525 symbols for the units (Fig.~\ref{fig:TigerClaw_b}), and the human-computer interface used to visualize the trajectories generated by both humans and learning agents in the Accelerated User Reasoning for Operations, Research, and Analysis (AURORA) \cite{dennison2020accelerated} virtual reality platform (Fig.~\ref{fig:TigerClaw_c}).}
    \label{fig:TigerClaw}
\end{figure}

\subsubsection{Task: The TigerClaw Scenario} \label{sec:tigerclaw}
In \textit{TigerClaw}, the Blue Force's goal is to cross a dry riverbed (wadi) terrain, neutralize the Red Force, and control certain geographic locations. Fig.~\ref{fig:TigerClaw} shows the overall objective of the TigerClaw Scenario. These objectives are encoded in the game score for use by reinforcement learning agents as a baseline for comparison across different neural network architectures and reward driving attributes.

\subsubsection{State and Action spaces} \label{sec:state_action_space}

The original \textit{StarCraft II} state-space consisted of approximately 20 images of size 64x64 (13 screen feature layers and 7 mini-map feature layers) which included categorical features ranging from unit type to geographical path traversal information \cite{Vinyals2017}.
In this tactical version of the \textit{StarCraft II} mini-game, we utilize a custom state-space consisting of two representations: (i) \emph{image representation} and (ii) \emph{vector representation}. The image representation consists of a single 256 x 256 image of the entire battlefield that includes all of the relevant information of the original feature maps as well as terrain information, as seen in Fig.~\ref{fig:TigerClaw_c}. The vector representation is a set of $287$ non-spatial features that include all of the information about the game and units, including unit type, position, health, player resources, and build queues.

The actions in \textit{StarCraft II} are compound actions in the form of functions that require arguments and specifications about what unit should take an action and where that action is intended to take place on the screen. For example, once a unit is selected, an action such as ``attack'' is represented as a function that would require the $x-y$ attack locations on the screen. The action space consists of the action identifier (i.e., which action to run), and two spatial actions ($x$ and $y$) that
represent the pair of coordinates in the screen where the action should be executed. This results in a very large action space that is impractical to be represented in a flattened space. To reduce this complexity, we defined \emph{cardinal actions} that divide the map into a $C$x$C$ grid, where we set $C=3$. Thus, the possible actions for the $x$ and $y$ coordinates are represented as two vectors of length $C=3$ with real-valued entries between $0$ and $1$ constituting left, center, and right, and top, middle, and bottom, respectively.

\subsubsection{Game Score and Reward Implementation}

The reward function is an important component of reinforcement learning as it ultimately controls how the agent reacts to environmental changes by giving them positive or negative reward for each situation. We developed a custom reward function for the \textit{TigerClaw} scenario consisting of awarding $+10$ points for the Blue Force crossing the wadi (river) and $-10$ points for retreating back. In addition, we awarded $+10$ points for destroying a Red Force unit and $-10$ points if a Blue Force unit was destroyed. The overall goal of this reward function was to incentivize the elimination of the opposing force while preserving Blue Force units from being destroyed.

\subsection{Reinforcement Learning Agent}

Next, we developed and implemented a modern deep reinforcement learning agent into the \textit{StarCraft II} environment to achieve the goal of the TigerClaw scenario discussed in Section~\ref{sec:tigerclaw}. We designed the action-space of our agent by adapting the traditional control approach of \textit{StarCraft II}, where the player performs the following steps to control each unit: (1) Select a unit using their mouse pointer, (2) Select an action based on the unit's possible actions and observed state, and (3) Select the $(x,y)$ coordinate in which the unit will execute the selected action.

\subsubsection{Learning Algorithm}
To train our deep reinforcement learning agent, we used the Asynchronous Advantage Actor Critic (A3C) algorithm, which is a state-of-the-art on-policy RL algorithm shown to have success on numerous challenging environments \cite{mnih2016asynchronous}. The A3C is a distributed RL algorithm that allows for parallelized exploration and training across multiple actors simultaneously. The A3C algorithm is an extension of the Advantage Actor Critic (A2C) in which multiple agents explore parallel environments simultaneously to speed up exploration and learning. Just like the A2C, the A3C maintains a a policy $\pi(a_t|s_t;\theta)$ and an estimate of the value function $V(s_t;\theta_v)$. In A3C, multiple copies of the actor policy are distributed across multiple instances of the environment to speed up exploration.

Our A3C model was trained with $35$ parallel actor-learners on separate threads for over $70$ million timesteps (around $112$ thousand simulated battles) against a built-in \textit{StarCraft II} bot operating on hand crafted rules.
Each trained model was tested on 100 rollouts of the agent on the \textit{TigerClaw} scenario. The curriculum learning models are compared against a traditional baseline A3C approach with details in the Experiments and Results section.

\subsubsection{Network Architecture}

\begin{figure}
    \centering
    \subfloat[Overall Network Architecture \label{fig:architecture}]{\includegraphics[width=0.65\textwidth]{full_model.eps}}\hfill
    \subfloat[``Feature Extraction Networks" Block \label{fig:features}] {\includegraphics[width=0.45\textwidth]{feature_extraction.eps}}\hfill
    \subfloat[``Baseline Network" Block\label{fig:baseline}]{\includegraphics[width=0.45\textwidth]{baseline_model.eps}}
        \caption{Diagrams illustrating the overall network architecture of the reinforcement learning agent (Fig.~\ref{fig:architecture}), the architecture of the networks responsible to learn the main features of the environment (Fig.~\ref{fig:features}), and the network used to select all components of the actions (Fig.~\ref{fig:baseline}).}
        \label{fig:approach}
\end{figure}

As shown in Fig.~\ref{fig:architecture}, our deep reinforcement learning agent is represented by a multi-input and multi-output neural network adapted from Waytowich et al 2019 \cite{waytowich2019ICML} capable of handling the complex state-space and the multi-faceted action-space of \textit{StarCraft II}.

The state observations, as described in Section~\ref{sec:state_action_space}, are fed through a feature extraction network, shown in Fig.~\ref{fig:features}, to identify all of the relevant information available. Next, the state-space is fed into the Baseline network, shown in Fig.~\ref{fig:baseline}, which outputs the action and $(x,y)$ coordinates of the control group. The agent then executes the policy into the TigerClaw environment and receives a reward and a new state-space. The details of the state-space, feature extraction network, and the baseline network are described in the following subsections.
As shown in Fig.~\ref{fig:features}.i, the screen features were processed through three Convolutional Neural Network (CNN) layers with ReLu activation functions in order to extract visual feature representations of the global and local states of the map, respectively.
The non-spatial features were processed through a fully-connected layer with a non-linear activation as shown in Fig.~\ref{fig:features}.ii. These two outputs were then concatenated to form the full state-space representation for the agent.

\subsection{Curriculum Learning}

Curriculum learning is a method for training machine learning models by gradually increasing the complexity of the task to be solved as well as the data samples used during training in order to improve training efficiency \cite{Soviany2021}.
In the reinforcement learning, curriculum learning is a vital component that ensures the agents receives positive rewards even during early stages of training when the policy is not fully developed.
This technique has enabled reinforcement learning agents to learn how to control a quadrupedal robot to walk on challenging terrain \cite{lee2020learning,rudin2021learningtowalk} and complete hiking trails \cite{miki2022wyldanimal} (policies were trained first on flat terrain, then progressively moved to more challenging ones with slopes and obstacles), control realistic bipedal robots in simulation to walk over stepping stones \cite{xie2020allsteps} (curriculum is used to generate courses of different complexities), and a 2D simulated obstacle course with different levels \cite{wang2019paired}.
Self-play or League-based training, is another form of curriculum learning whereby the agent learns from playing against previously trained versions of itself.  Agents trained under this strategy have had notable success in competitive environments
This strategy was previously used to train an agent to play the full-game of \textit{StarCraft II} and achieve grandmaster level, which translates to ranking above 99.8\% of the officially ranked human players.  \cite{vinyals2019grandmaster}.

\subsubsection{Automatic Curriculum Generation}

\begin{figure}
    \centering
    \subfloat[\label{fig:autocurriculum_steps_a}]{\includegraphics[width=0.24\textwidth]{autocurriculum_1.png}}\hfill
    \subfloat[\label{fig:autocurriculum_steps_b}]{\includegraphics[width=0.24\textwidth]{autocurriculum_2.png}}\hfill
    \subfloat[\label{fig:autocurriculum_steps_c}]{\includegraphics[width=0.24\textwidth]{autocurriculum_3.png}}\hfill
    \subfloat[\label{fig:autocurriculum_steps_d}]{\includegraphics[width=0.24\textwidth]{autocurriculum_4.png}}
    \caption{Diagram illustrating how a single human demonstration is used to generate a curriculum to the reinforcement learning agent. The goal of the agent (Blue Force) is to avoid the Red Forces near the bridge and engage them at the corner of the map. the The agent starts learning from the end of the demonstrated trajectory \ref{fig:autocurriculum_steps_a}, represented by a yellow line. Once this final segment is mastered, as judge by the reward value, the agent starts to learn further from the end of the trajectory, as seen in \ref{fig:autocurriculum_steps_b} and \ref{fig:autocurriculum_steps_c}. This process repeats until the agent masters all segments and starts at the beginning of the demonstrated trajectory, as shown in \ref{fig:autocurriculum_steps_d}.}
    \label{fig:autocurriculum_steps}
\end{figure}

In automatic curriculum generation (ACL), the difficulty of the task is automatically controlled based on the current skill level of the agent during the training procedure. Self-play can be thought as a form of ACL since the agent learns continuously playing against itself. This results in a self-sustaining loop where the agent gets better as its opponent (i.e the agent itself) also gets better. However, for our task, we are unable to utilize traditional self-play since the Blue Force and Red Forces are heterogeneous and are composed of different StarCraft units.
Instead, our main approach revolves around training an RL model using curriculum learning defined by a single human demonstration. We do this by starting the agent at the near end of the human demonstration, and then progressively making the task more difficult by rolling back through the human demonstration as the agent gets better and better, illustrated in Fig.~\ref{fig:autocurriculum_steps}.

In detail, this procedure is accomplished by the following scheme:
1) We record the sequence of states, actions and rewards (i.e., the trajectory) observed during the demonstration of the human user performing the given task.
2) Given this trajectory, the automatic curriculum generation starts by letting the agent complete only the last few steps of the task, as demonstrated by the human.
This is done by first sampling a state from the end of the human demonstration from which the learning agent will execute its current policy. We record the trajectory resulting from this rollout, and train the policy by comparing the rewards received by the agent in this trajectory to the ones observed during demonstration.
We repeat this step until the agent is proficient at this part of the curriculum.
We consider this an easier task to be solved because the agent only needs to perform a few good actions to complete the task.
3) Once the agent has achieved comparable performance to the human, at the current stage of the curriculum, we then increase the difficulty of the task by setting the initial states of the agent further away from the end of the task along the trajectory generated generated by the human.
4) The agent continues following this scheme until it becomes proficient in solving the task from all states demonstrated by the human, completing the curriculum.

For our ACL agent, the exact point in the human demonstrated trajectory where we start the curriculum is represented by a Gaussian distribution with mean that ranges from 0 to 1 (0 to 100\% of the trajectory) and standard deviation of $1/6$.
During each rollout of the task, the starting point of the agent is sampled from this distribution and clipped between 0 and 100\%.
This helps the agents to experience diverse starting locations instead of overfitting to a single point, plus, ACL acts as a way to guide the exploration for an RL agent for efficient learning.

\section{EXPERIMENTS and RESULTS}

\subsection{Experimental Conditions} \label{sec:exp_cond}

In order to understand the benefits of ACL, we conducted the following four experiments: (i) \emph{Automatic Curriculum Learning with Image Representation}, (ii) \emph{Automatic Curriculum Learning with Vector Representation}, (iii) \emph{No Automatic Curriculum Learning (Traditional RL) with Image Representation}, and (iv) \emph{No Automatic Curriculum Learning (Traditional RL) with Vector Representation}.
The first and third experiments follow the network architecture shown in Fig.~\ref{fig:baseline}, while the second and forth experiments remove the Image Features from the input. Thus, we aim to understand if (a) ACL achieves more reward than traditional reinforcement learning and if (b) increasing the observation state space to include terrain information in image format improves learning.

For each experimental condition, we trained our agent on the DoD High Performance Computing system with 35 parallel actor-learners for over $70$ million timesteps (around $112$ thousand simulated battles) against a built-in \emph{StarCraft II} bot operating on hand-crafted rules.
The traditional RL algorithms resets each episode so the agent starts at the beginning of the game, while the ACL experiments sample the start of the episode from a Gaussian distribution initially centered at 95\% of the human-demonstrated trajectory, that is, the start of each episode the battle is played out according to the first sampled percentage of the actions of the human demonstration, then the ACL agent takes over.
Once the ACL agent finishes at least 50 battles with a score similar to the human demonstration, the mean of the Gaussian distribution is rolled back through the curriculum in 20\% increments to provide progressively more and more difficult tasks of the ACL agent.

\subsection{Results}

\begin{figure}
    \centering
    \subfloat[\label{fig:reward_img_rep}]{\includegraphics[width=0.48\textwidth]{reward_image_rep.png}}\hfill
    \subfloat[\label{fig:reward_vec_rep}]{\includegraphics[width=0.48\textwidth]{reward_vec_rep.png}}
    \caption{Average episode reward received by the agent during training when using the curriculum automatically generated from human demonstrations (Autocurriculum RL) and when using traditional RL methods with no curriculum (Traditional RL) with the state information of the environment being represented as images (Fig.~\ref{fig:reward_img_rep}) or vectors (Fig.~\ref{fig:reward_vec_rep}).}
    \label{fig:reward_plot}
\end{figure}

Our first result compares agents that were trained using images (terrain information) within their observed states.
Fig.~\ref{fig:reward_img_rep} presents the average reward achieved by the agent for experiments (i) and (iii), \emph{Automatic Curriculum Learning with Image Representation} and \emph{No Automatic Curriculum Learning (Traditional RL) with Image Representation}, respectively.
As seen, initially, the reward achieved using ACL is much less than without ACL due to the agent starting at the end of the curriculum, as defined by the human-demonstrated trajectory.
In this case, the agent only needs to eliminate the last couple units of the opposing force, which does not result in a large reward. However, after $3$ million episodes, the ACL agent has moved further along the curriculum and has learned to eliminate the opposing force, resulting in a larger reward than without ACL.
Furthermore, the reward for the agent without ACL (Traditional RL) slowly increases, indicating that learning a complex task from the beginning, that is, searching over the full state space of the task, results in a agent that learns slower than an agent that is guided through a curriculum.

\begin{table
\caption{Average casualties for each force.}
\centering
\begin{tabular}{c|c|cc|cc}
                & \multicolumn{1}{c|}{Human}      & \multicolumn{2}{c|}{Autocurriculum RL}          & \multicolumn{2}{c}{Traditional RL}        \\
                & \multicolumn{1}{c|}{Demonstration}      & \multicolumn{1}{c|}{Image Rep.} & Vector Rep. & \multicolumn{1}{c|}{Image Rep.} & Vector Rep. \\ \hline
Blue Force Casualties & \multicolumn{1}{c|}{$2.80$} & \multicolumn{1}{c|}{\textbf{$2.94$}}     & $10.66$          & \multicolumn{1}{c|}{$13.57$}         & $11.22$          \\
Red Force Casualties & \multicolumn{1}{c|}{$17.00$} & \multicolumn{1}{c|}{$13.17$}    & $13.08$          & \multicolumn{1}{c|}{$15.02$}         & $12.33$
\end{tabular} \label{tab:casualties}
\end{table}

We also evaluated the average amount of casualties for the Blue force and the Red force at the end of training.
As seen in Table~\ref{tab:casualties}, learning with ACL achieves \textit{significantly} fewer Blue force casualties and higher Red force casualties when compared to traditional RL.
This also explains why the ACL agent achieves a larger reward since the Blue force casualties contribute to a large negative reward. Additionally, the ACL with image representation almost achieves the casualty rates of the human demonstration, showing that the curriculum helped guide the agent to learn a similar policy.

Next, we compared experiments (ii) and (iv), \emph{Automatic Curriculum Learning with Vector Representation} and \emph{No Automatic Curriculum Learning (Traditional RL) with Vector Representation}, respectively, where the agent uses only vector representations for the observed state. As seen in Fig.~\ref{fig:reward_vec_rep}, similar to the behavior observed in Fig.~\ref{fig:reward_img_rep}, the reward for the ACL surpasses the reward without ACL after a few million training steps.
However, the gap between the two experiments is not as significant as the agents trained with image representations.
In the case of experiments where the agents are trained with only the vector representation of the environment, both agents result in similar Blue force and Red force casualties, with ACL slightly outperforming traditional RL.

When we compare experiments (i) and (iii) against (ii) and (iv), we note that agents with image representations achieve a larger reward than agents with vector representations due to the resulting fewer Blue Force casualties and similar number for Red Force casualties.
This indicates that including additional information, i.e., terrain information, allows for the agent to learn a better policy. However, this result is at the cost of additional training time due to the complexity in the observational state space.

To further understand how the ACL policies were outperforming traditional RL and the differences from the human demonstration, we collected data on how the agents were commanding each coalition, as represented by their distance travelled (Table \ref{tab:distance}) and health percentage remaining at the end of the battle (Table \ref{tab:health}).
Looking at the policies that utilize terrain information (image representation as input), ACL policies maneuvered their units more often than traditional RL and the human demonstration.
For example, \emph{aviation} units (which are faster and able to attack both ground and air units, but with lower total health capacity) travelled more than five times more in ACL than traditional RL and three times more than the human demonstration.
All other coalitions travelled at least twice more in ACL.
This could have led to higher fuel usage but units were able to eliminate more Red Forces and remain alive.
To illustrate this point, Table \ref{tab:health} shows that mortar units commanded by ACL received no damage.
All coalitions commanded by ACL, on average, finished the battles with more health percentage remaining when compared to all other conditions.

\begin{table
\caption{Average distance travelled for each coalition of the Blue force.}
\centering
\begin{tabular}{c|c|cc|cc}
                   & \multicolumn{1}{c|}{Human}   & \multicolumn{2}{c|}{Autocurriculum RL}          & \multicolumn{2}{c}{Traditional RL}        \\
                   & \multicolumn{1}{c|}{Demonstration}   & \multicolumn{1}{c|}{Image Rep.} & Vector Rep. & \multicolumn{1}{c|}{Image Rep.} & Vector Rep. \\ \hline
Aviation & \multicolumn{1}{c|}{$295.91$} & \multicolumn{1}{c|}{\textbf{$1041.99$}}     & $243.88$          & \multicolumn{1}{c|}{$178.30$}         & $351.90$          \\
Mechanized Infantry & \multicolumn{1}{c|}{$350.00$} & \multicolumn{1}{c|}{$818.90$}    & $495.45$          & \multicolumn{1}{c|}{$443.14$}         & $287.49$         \\
Mortars & \multicolumn{1}{c|}{$88.19$}  & \multicolumn{1}{c|}{$218.02$}    & $209.05$          & \multicolumn{1}{c|}{$123.85$}         & $92.09$            \\
Scouts & \multicolumn{1}{c|}{$83.73$}  & \multicolumn{1}{c|}{$235.60$}    & $83.72$          & \multicolumn{1}{c|}{$36.02$}         & $46.90$               \\
Tanks & \multicolumn{1}{c|}{$597.10$}  & \multicolumn{1}{c|}{$2281.20$}    & $1330.18$          & \multicolumn{1}{c|}{$1381.22$}         & $1763.06$
\end{tabular}
 \label{tab:distance}
\end{table}

\begin{table
\caption{Average health percentage remaining for each coalition of the Blue force.}
\centering
\begin{tabular}{c|c|cc|cc}
                    & \multicolumn{1}{c|}{Human}  & \multicolumn{2}{c|}{Autocurriculum RL}          & \multicolumn{2}{c}{Traditional RL}        \\
                    & \multicolumn{1}{c|}{Demonstration}  & \multicolumn{1}{c|}{Image Rep.} & Vector Rep. & \multicolumn{1}{c|}{Image Rep.} & Vector Rep. \\ \hline
Aviation & \multicolumn{1}{c|}{$59.78$} & \multicolumn{1}{c|}{\textbf{$29.48$}}     & $1.15$          & \multicolumn{1}{c|}{$0.63$}         & $17.65$          \\
Mechanized Infantry & \multicolumn{1}{c|}{$48.16$} & \multicolumn{1}{c|}{$59.58$}    & $12.42$          & \multicolumn{1}{c|}{$6.32$}         & $8.87$         \\
Mortars & \multicolumn{1}{c|}{$96.62$} & \multicolumn{1}{c|}{$100.00$}    & $11.60$          & \multicolumn{1}{c|}{$1.90$}         & $15.01$            \\
Scouts & \multicolumn{1}{c|}{$22.30$} & \multicolumn{1}{c|}{$29.00$}    & $0.12$          & \multicolumn{1}{c|}{$0.00$}         & $2.96$               \\
Tanks & \multicolumn{1}{c|}{$28.77$} & \multicolumn{1}{c|}{$35.57$}    & $14.03$          & \multicolumn{1}{c|}{$4.96$}         & $15.97$
\end{tabular} \label{tab:health}
\end{table}

\section{DISCUSSION}

Curriculum Learning is a technique designed to make learning complex problems easier by designing a curriculum of simple tasks and concepts to improve the speed and efficiency of learning
Curriculum learning has been utilized in the reinforcement learning field in order to improve the sample efficiency of RL training, however, manually designing a curriculum is often challenging. In this paper, we utilize human demonstrations to generate a curriculum automatically (i.e. automatic curriculum learning (ACL)) and then use that curriculum to speed up reinforcement learning on the complex environment of \textit{StarCraft II}. We show that with our curriculum learning agent, we are able to significantly improve training speed and performance compared to traditional RL agents in \textit{StarCraft II}.

In reinforcement learning, the state-space that is made available to the agent is often a critical factor in determining the complexity of the learning problem. In this paper, we analyzed two different state-space representations for our learning agents, a high dimension, image-based representation and a low-dimension, vector-based representation. The image representation consists of game-screen images of the \textit{StarCraft II} environment that contain unit information and terrain information. The vector representation is a much more compact representation that contains the entire state of the game in a vectorized format (i.e. unit position, health, etc.), however, it does not contain any terrain information. Generally, there is a trade-off between the higher-complexity image representation and lower-dimensional vector representation in terms of both training time and overall policy performance. Based on our results, as seen in Figs.~\ref{fig:reward_img_rep} and \ref{fig:reward_vec_rep}, we show that despite the larger state-space, both traditional RL and ACL agents achieve a higher overall reward using image representation when compared to the vector representation-based agents. Interestingly, as shown in Table~\ref{tab:casualties}, we see that for the Autocurriculum RL agent trained with images, the agent was able to dramatically reduce the number of Blue Force casualties to only 3, compared to the 10-13 casualties that the vectorized representation produced. The results in Table~\ref{tab:distance} show that the image based ACL agent utilizes the aviation units more often, as indicated by the amount of distance traveled. These are powerful units since they are fast and can attack enemy air and ground forces. Although more analysis needs to be performed, we speculate that having access to terrain information allows for the ACL agent to better follow the human guided curriculum, which relies on heavy use of the aviation units, which ultimately leads to fewer Blue Force casualties.

\subsection{Limitations and Future Work}

Although we have shown that there is a benefit to performance in terms of overall reward and performance achieved by the ACL agent compared to traditional RL, there are several limitations of the current work that we highlight here as the topic of future studies. Firstly, as with almost all deep reinforcement learning work, training RL agents on these tasks is incredibly difficult and requires extensive hyper-parameter turning to achieve proper convergence. We found that our approach of using curriculum learning to train RL agents is not immune to this problem.

With curriculum learning, one of the difficulties is deciding when and how the RL agent should progress through the curriculum. One limitation in the current work is that we utilized a rather naive and straightforward curriculum step policy of just setting a fixed performance threshold before allowing the agent to progress to the next step in the curriculum. This leads to problems of the agent potentially getting stuck at a certain part of the curriculum and never progressing because the threshold is too high. This ultimately slows down learning to an extent where curriculum learning is no longer useful or practical. Future work could involve developing more intelligent strategies for traversing the curriculum.

\acknowledgments

This work was supported in part by high-performance computer time and resources from the DoD High Performance Computing Modernization Program.
This work was also sponsored by the Army Research Laboratory and was accomplished partly under Cooperative Agreement Number W911NF-20-2-0114. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.


text:
\section{Why Direct Gradient Estimation is Inefficient}

\section{Proof of Theorem \ref{tho:dimred}}
\label{sec:tho-proof}
We first prove a lemma of the gradient estimation quality which samples from the entire subspace:
\begin{lemma}
\label{lemma:cos}
For a boundary point $x$, suppose that $S(x)$ has $L$-Lipschitz gradients in a neighborhood of $x$, and that ${\bf u}_1, \ldots, {\bf u}_B$ are sampled from the unit ball in $\mathbb{R}^m$ and orthogonal to each other. Then the expected cosine similarity between $\widetilde{\nabla S}$ and $\nabla S$ can be bounded by:
\begin{align}
    & \bigg( 2\bigg(1-(\frac{L\delta}{2||\nabla S||_2})^2\bigg)^{\frac{m-1}{2}} - 1 \bigg)c_m\sqrt{\frac B m}\\
    \leq & \mathbb{E}\big[\cos (\widetilde{\nabla S}, \nabla S) \big]\\
    \leq & c_m\sqrt{\frac B m}
\end{align}
where $c_m$ is a constant related with $m$ and can be bounded by $c_m \in (2/\pi, 1)$. In particular, we have:
\begin{align}
    \label{eqn:grad-est-qual}
    \lim_{\delta\rightarrow 0}\mathbb{E}\big[\cos (\widetilde{\nabla S}, \nabla S) \big] = c_m\sqrt{\frac B m}.
\end{align}
\end{lemma}

\label{sec:proof}
\begin{proof}
Let ${\bf u}_1, \ldots, {\bf u}_B$ be the random orthonormal vectors sampled from $\mathbb{R}^m$. We expand the vectors to an orthonormal basis in $\mathbb{R}^m$: ${\bf q}_1={\bf u}_1, \ldots, {\bf q}_B={\bf u}_B, {\bf q}_{B+1}, \ldots, {\bf q}_m$. Hence, the gradient direction can be written as:
\begin{equation}
    \label{eqn:proof-gt}
    \frac{\nabla S}{||\nabla S||_2} = \sum_{i=1}^m a_i{\bf q}_i
\end{equation}
where $a_i=\langle \frac{\nabla S}{||\nabla S||_2}, {\bf q}_i \rangle$ and its distribution is equivalent to the distribution of one coordinate of an $(m-1)$-sphere. Then each $a_i$ follows the probability distribution function:
\begin{equation}
    p_a(x) = \frac{(1-x^2)^{\frac{m-3}2}}{\mathcal{B}(\frac{m-1}2, \frac12)},~x\in(-1,1)
\end{equation}
where $\mathcal{B}$ is the beta function. According to the conclusion in the proof of Theorem 1 in \cite{chen2019hopskipjumpattack}, if we let $w=\frac{L\delta}{2||\nabla S||_2}$, then it always holds true that $\phi({\bf x}+\delta{\bf u_i})=1$ when $a_i>w$, -1 when $a_i<-w$ regardless of $u_i$ and the decision boundary shape. Hence, we can rewrite $\phi_i$ in term of $a_i$:
\begin{equation}
    \phi_i = \phi({\bf x}+\delta{\bf u_i}) =
    \begin{cases}
    1, & \text{if } a_i \in [w, 1)\\
    -1, & \text{if } a_i \in (-1, -w]\\
    \text{undetermined}, & \text{otherwise}
    \end{cases}
\end{equation}
Therefore, the estimated gradient can be rewritten as:
\begin{equation}
    \label{eqn:proof-est}
    \widetilde{\nabla S}=\frac1B\sum_{i=1}^B \phi_i{\bf u}_i
\end{equation}
Combining Eqn. \ref{eqn:proof-gt} and \ref{eqn:proof-est}, we can calculate the cosine similarity:
\begin{align}
    \mathop{\mathbb{E}}\big[ \cos (\widetilde{\nabla S}, \nabla S)\big] &= \mathop{\mathbb{E}}_{a_1, \ldots,a_B}\frac{\sum_{i=1}^Ba_i\phi_i}{\sqrt{B}}\\
    &= \sqrt{B}\cdot \mathop{\mathbb{E}}_{a_1} \big[ a_1\phi_1 \big]
\end{align}
In the best case, $\phi_1$ has the same sign with $a_1$ everywhere on $(-1,1)$; in the worst case, $\phi_1$ has different sign with $a_1$ on $(-w,w)$. In addition, $p_a(x)$ is symmetric on $(-1, 1)$. Therefore, the expectation is bounded by:
\begin{align}
    &2\int_{w}^{1} p_a(x)\cdot xdx - 2\int_0^w p_a(x)\cdot xdx\\
    \leq& \mathop{\mathbb{E}}_{a_1} \big[ a_1\phi_1 \big]\\
    \leq& 2\int_0^1 p_a(x)\cdot xdx
\end{align}
By calculating the integration, we have:
\begin{align}
&\bigg( 2\bigg(1-w^2\bigg)^{\frac{m-1}{2}} - 1 \bigg) \cdot \frac{2\sqrt{B}}{\mathcal{B}(\frac{m-1}2, \frac12)\cdot(m-1)}\\
\leq& \mathop{\mathbb{E}}\big[ \cos (\widetilde{\nabla S}, \nabla S)\big]\\
\leq& \frac{2\sqrt{B}}{\mathcal{B}(\frac{m-1}2, \frac12)\cdot(m-1)}
\end{align}
The only problem is to calculate $\mathcal{B}(\frac{m-1}2, \frac12)\cdot(m-1)$. It is easy to prove by scaling that $\mathcal{B}(\frac{m-1}2, \frac12)\cdot(m-1) \in (2\sqrt{m}, \pi \sqrt{m})$. Hence we can get the conclusion in the theorem.
\end{proof}

Having Lemma \ref{lemma:cos}, Theorem \ref{tho:dimred} follows by noticing that $\mathbb{E}\big[\cos (\widetilde{\nabla S}, \nabla S) \big]=\rho\mathbb{E}\big[\cos (\widetilde{\nabla S}, \text{proj}_{\text{span}(W)}(\nabla S)) \big]$.

\section{Introduction}

Please follow the steps outlined below when submitting your manuscript to
the IEEE Computer Society Press.  This style guide now has several
important modifications (for example, you are no longer warned against the
use of sticky tape to attach your artwork to the paper), so all authors
should read this new version.

\subsection{Language}

All manuscripts must be in English.

\subsection{Dual submission}

Please refer to the author guidelines on the CVPR 2019 web page for a
discussion of the policy on dual submissions.

\subsection{Paper length}
Papers, excluding the references section,
must be no longer than eight pages in length. The references section
will not be included in the page count, and there is no limit on the
length of the references section. For example, a paper of eight pages
with two pages of references would have a total length of 10 pages.
{\bf There will be no extra page charges for CVPR 2019.}

Overlength papers will simply not be reviewed.  This includes papers
where the margins and formatting are deemed to have been significantly
altered from those laid down by this style guide.  Note that this
\LaTeX\ guide already sets figure captions and references in a smaller font.
The reason such papers will not be reviewed is that there is no provision for
supervised revisions of manuscripts.  The reviewing process cannot determine
the suitability of the paper for presentation in eight pages if it is
reviewed in eleven.

\subsection{The ruler}
The \LaTeX\ style defines a printed ruler which should be present in the
version submitted for review.  The ruler is provided in order that
reviewers may comment on particular lines in the paper without
circumlocution.  If you are preparing a document using a non-\LaTeX\
document preparation system, please arrange for an equivalent ruler to
appear on the final output pages.  The presence or absence of the ruler
should not change the appearance of any other content on the page.  The
camera ready copy should not contain a ruler. (\LaTeX\ users may uncomment
the \verb'\cvprfinalcopy' command in the document preamble.)  Reviewers:
note that the ruler measurements do not align well with lines in the paper
--- this turns out to be very difficult to do well when the paper contains
many figures and equations, and, when done, looks ugly.  Just use fractional
references (e.g.\ this line is $095.5$), although in most cases one would
expect that the approximate location will be adequate.

\subsection{Mathematics}

Please number all of your sections and displayed equations.  It is
important for readers to be able to refer to any particular equation.  Just
because you didn't refer to it in the text doesn't mean some future reader
might not need to refer to it.  It is cumbersome to have to use
circumlocutions like ``the equation second from the top of page 3 column
1''.  (Note that the ruler will not be present in the final copy, so is not
an alternative to equation numbers).  All authors will benefit from reading
Mermin's description of how to write mathematics:
\url{http://www.pamitc.org/documents/mermin.pdf}.

\subsection{Blind review}

Many authors misunderstand the concept of anonymizing for blind
review.  Blind review does not mean that one must remove
citations to one's own work---in fact it is often impossible to
review a paper unless the previous citations are known and
available.

Blind review means that you do not use the words ``my'' or ``our''
when citing previous work.  That is all.  (But see below for
techreports.)

Saying ``this builds on the work of Lucy Smith [1]'' does not say
that you are Lucy Smith; it says that you are building on her
work.  If you are Smith and Jones, do not say ``as we show in
[7]'', say ``as Smith and Jones show in [7]'' and at the end of the
paper, include reference 7 as you would any other cited work.

An example of a bad paper just asking to be rejected:
\begin{quote}
\begin{center}
    An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of our
   previous paper [1], and show it to be inferior to all
   previously known methods.  Why the previous paper was
   accepted without this analysis is beyond me.

   [1] Removed for blind review
\end{quote}

An example of an acceptable paper:

\begin{quote}
\begin{center}
     An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of the
   paper of Smith \etal [1], and show it to be inferior to
   all previously known methods.  Why the previous paper
   was accepted without this analysis is beyond me.

   [1] Smith, L and Jones, C. ``The frobnicatable foo
   filter, a fundamental contribution to human knowledge''.
   Nature 381(12), 1-213.
\end{quote}

If you are making a submission to another conference at the same time,
which covers similar or overlapping material, you may need to refer to that
submission in order to explain the differences, just as you would if you
had previously published related work.  In such cases, include the
anonymized parallel submission~\cite{Authors14} as additional material and
cite it as
\begin{quote}
[1] Authors. ``The frobnicatable foo filter'', F\&G 2014 Submission ID 324,
Supplied as additional material {\tt fg324.pdf}.
\end{quote}

Finally, you may feel you need to tell the reader that more details can be
found elsewhere, and refer them to a technical report.  For conference
submissions, the paper must stand on its own, and not {\em require} the
reviewer to go to a techreport for further details.  Thus, you may say in
the body of the paper ``further details may be found
in~\cite{Authors14b}''.  Then submit the techreport as additional material.
Again, you may not assume the reviewers will read this material.

Sometimes your paper is about a problem which you tested using a tool which
is widely known to be restricted to a single institution.  For example,
let's say it's 1969, you have solved a key problem on the Apollo lander,
and you believe that the CVPR70 audience would like to hear about your
solution.  The work is a development of your celebrated 1968 paper entitled
``Zero-g frobnication: How being the only people in the world with access to
the Apollo lander source code makes us a wow at parties'', by Zeus \etal.

You can handle this paper like any other.  Don't write ``We show how to
improve our previous work [Anonymous, 1968].  This time we tested the
algorithm on a lunar lander [name of lander removed for blind review]''.
That would be silly, and would immediately identify the authors. Instead
write the following:
\begin{quotation}
\noindent
   We describe a system for zero-g frobnication.  This
   system is new because it handles the following cases:
   A, B.  Previous systems [Zeus et al. 1968] didn't
   handle case B properly.  Ours handles it by including
   a foo term in the bar integral.

   ...

   The proposed system was integrated with the Apollo
   lunar lander, and went all the way to the moon, don't
   you know.  It displayed the following behaviours
   which show how well we solved cases A and B: ...
\end{quotation}
As you can see, the above text follows standard scientific convention,
reads better than the first version, and does not explicitly name you as
the authors.  A reviewer might think it likely that the new paper was
written by Zeus \etal, but cannot make any decision based on that guess.
He or she would have to be sure that no other authors could have been
contracted to solve problem B.
\medskip

\noindent
FAQ\medskip\\
{\bf Q:} Are acknowledgements OK?\\
{\bf A:} No.  Leave them for the final copy.\medskip\\
{\bf Q:} How do I cite my results reported in open challenges?
{\bf A:} To conform with the double blind review policy, you can report results of other challenge participants together with your results in your paper. For your results, however, you should not identify yourself and should not mention your participation in the challenge. Instead present your results referring to the method proposed in your paper and draw conclusions based on the experimental comparison to other results.\medskip\\

\begin{figure}[t]
\begin{center}
\fbox{\rule{0pt}{2in} \rule{0.9\linewidth}{0pt}}

\end{center}
   \caption{Example of caption.  It is set in Roman so that mathematics
   (always set in Roman: $B \sin A = A \sin B$) may be included without an
   ugly clash.}
\label{fig:long}
\label{fig:onecol}
\end{figure}

\subsection{Miscellaneous}

\noindent
Compare the following:\\
\begin{tabular}{ll}
 \verb'$conf_a$' &  $conf_a$ \\
 \verb'$\mathit{conf}_a$' & $\mathit{conf}_a$
\end{tabular}\\
See The \TeX book, p165.

The space after \eg, meaning ``for example'', should not be a
sentence-ending space. So \eg is correct, {\em e.g.} is not.  The provided
\verb'\eg' macro takes care of this.

When citing a multi-author paper, you may save space by using ``et alia'',
shortened to ``\etal'' (not ``{\em et.\ al.}'' as ``{\em et}'' is a complete word.)
However, use it only when there are three or more authors.  Thus, the
following is correct: ``
   Frobnication has been trendy lately.
   It was introduced by Alpher~\cite{Alpher02}, and subsequently developed by
   Alpher and Fotheringham-Smythe~\cite{Alpher03}, and Alpher \etal~\cite{Alpher04}.''

This is incorrect: ``... subsequently developed by Alpher \etal~\cite{Alpher03} ...''
because reference~\cite{Alpher03} has just two authors.  If you use the
\verb'\etal' macro provided, then you need not worry about double periods
when used at the end of a sentence as in Alpher \etal.

For this citation style, keep multiple citations in numerical (not
chronological) order, so prefer \cite{Alpher03,Alpher02,Authors14} to
\cite{Alpher02,Alpher03,Authors14}.

\begin{figure*}
\begin{center}
\fbox{\rule{0pt}{2in} \rule{.9\linewidth}{0pt}}
\end{center}
   \caption{Example of a short caption, which should be centered.}
\label{fig:short}
\end{figure*}

\section{Formatting your paper}

All text must be in a two-column format. The total allowable width of the
text area is $6\frac78$ inches (17.5 cm) wide by $8\frac78$ inches (22.54
cm) high. Columns are to be $3\frac14$ inches (8.25 cm) wide, with a
$\frac{5}{16}$ inch (0.8 cm) space between them. The main title (on the
first page) should begin 1.0 inch (2.54 cm) from the top edge of the
page. The second and following pages should begin 1.0 inch (2.54 cm) from
the top edge. On all pages, the bottom margin should be 1-1/8 inches (2.86
cm) from the bottom edge of the page for $8.5 \times 11$-inch paper; for A4
paper, approximately 1-5/8 inches (4.13 cm) from the bottom edge of the
page.

\subsection{Margins and page numbering}

All printed material, including text, illustrations, and charts, must be kept
within a print area 6-7/8 inches (17.5 cm) wide by 8-7/8 inches (22.54 cm)
high.
Page numbers should be in footer with page numbers, centered and .75
inches from the bottom of the page and make it start at the correct page
number rather than the 4321 in the example.  To do this fine the line (around
line 23)
\begin{verbatim}
\setcounter{page}{4321}
\end{verbatim}
where the number 4321 is your assigned starting page.

Make sure the first page is numbered by commenting out the first page being
empty on line 46
\begin{verbatim}
\end{verbatim}

\subsection{Type-style and fonts}

Wherever Times is specified, Times Roman may also be used. If neither is
available on your word processor, please use the font closest in
appearance to Times to which you have access.

MAIN TITLE. Center the title 1-3/8 inches (3.49 cm) from the top edge of
the first page. The title should be in Times 14-point, boldface type.
Capitalize the first letter of nouns, pronouns, verbs, adjectives, and
adverbs; do not capitalize articles, coordinate conjunctions, or
prepositions (unless the title begins with such a word). Leave two blank
lines after the title.

AUTHOR NAME(s) and AFFILIATION(s) are to be centered beneath the title
and printed in Times 12-point, non-boldface type. This information is to
be followed by two blank lines.

The ABSTRACT and MAIN TEXT are to be in a two-column format.

MAIN TEXT. Type main text in 10-point Times, single-spaced. Do NOT use
double-spacing. All paragraphs should be indented 1 pica (approx. 1/6
inch or 0.422 cm). Make sure your text is fully justified---that is,
flush left and flush right. Please do not place any additional blank
lines between paragraphs.

Figure and table captions should be 9-point Roman type as in
Figures~\ref{fig:onecol} and~\ref{fig:short}.  Short captions should be centred.

\noindent Callouts should be 9-point Helvetica, non-boldface type.
Initially capitalize only the first word of section titles and first-,
second-, and third-order headings.

FIRST-ORDER HEADINGS. (For example, {\large \bf 1. Introduction})
should be Times 12-point boldface, initially capitalized, flush left,
with one blank line before, and one blank line after.

SECOND-ORDER HEADINGS. (For example, { \bf 1.1. Database elements})
should be Times 11-point boldface, initially capitalized, flush left,
with one blank line before, and one after. If you require a third-order
heading (we discourage it), use 10-point Times, boldface, initially
capitalized, flush left, preceded by one blank line, followed by a period
and your text on the same line.

\subsection{Footnotes}

Please use footnotes\footnote {This is what a footnote looks like.  It
often distracts the reader from the main flow of the argument.} sparingly.
Indeed, try to avoid footnotes altogether and include necessary peripheral
observations in
the text (within parentheses, if you prefer, as in this sentence).  If you
wish to use a footnote, place it at the bottom of the column on the page on
which it is referenced. Use Times 8-point type, single-spaced.

\subsection{References}

List and number all bibliographical references in 9-point Times,
single-spaced, at the end of your paper. When referenced in the text,
enclose the citation number in square brackets, for
example~\cite{Authors14}.  Where appropriate, include the name(s) of
editors of referenced books.

\begin{table}
\begin{center}
\begin{tabular}{|l|c|}
\hline
Method & Frobnability \\
\hline\hline
Theirs & Frumpy \\
Yours & Frobbly \\
Ours & Makes one's heart Frob\\
\hline
\end{tabular}
\end{center}
\caption{Results.   Ours is better.}
\end{table}

\subsection{Illustrations, graphs, and photographs}

All graphics should be centered.  Please ensure that any point you wish to
make is resolvable in a printed copy of the paper.  Resize fonts in figures
to match the font in the body text, and choose line widths which render
effectively in print.  Many readers (and reviewers), even of an electronic
copy, will choose to print your paper in order to read it.  You cannot
insist that they do otherwise, and therefore must not assume that they can
zoom in to see tiny details on a graphic.

When placing figures in \LaTeX, it's almost always best to use
\verb+\includegraphics+, and to specify the  figure width as a multiple of
the line width as in the example below
{\small\begin{verbatim}
   \usepackage[dvips]{graphicx} ...
   \includegraphics[width=0.8\linewidth]
                   {myfile.eps}
\end{verbatim}
}

\subsection{Color}

Please refer to the author guidelines on the CVPR 2019 web page for a discussion
of the use of color in your document.

\section{Final copy}

You must include your signed IEEE copyright release form when you submit
your finished paper. We MUST have this form before your paper can be
published in the proceedings.

Please direct any questions to the production editor in charge of these
proceedings at the IEEE Computer Society Press: Phone (714) 821-8380, or
Fax (714) 761-1784.

{\small
\bibliographystyle{ieee_fullname}

\subsection{Why Direct Gradient Estimation is Inefficient}
The gradient vector estimated by Eqn. \ref{eqn:grad-est} is a linear combination of $B$ vectors $u_1,\ldots,u_B \in \mathbb{R}^m$.  The best estimated gradient we can possibly get is the projection of the actual gradient onto the subspace spanned by the $B$ vectors. In practice, $m$ is large (for example, $3\times224\times224$ on ImageNet) while $B$ is chosen to be small (e.g., 100). The following theorem shows the expectation of the gradient approximation in a randomly sampled subspace.
\begin{theorem}
\label{tho:cos}
For a boundary point $x$, suppose that $S(x)$ has $L$-Lipschitz gradients in a neighborhood of $x$, and that the sampled ${\bf u}_1, \ldots, {\bf u}_B$ are orthogonal to each other. Then the expected cosine simliarity between $\widetilde{\nabla S}$ and $\nabla S$ can be bounded by:
\begin{align}
    & \bigg( 2\bigg(1-(\frac{L\delta}{2||\nabla S||_2})^2\bigg)^{\frac{m-1}{2}} - 1 \bigg)c_m\sqrt{\frac B m}\\
    \leq & \mathbb{E}\big[\cos (\widetilde{\nabla S}, \nabla S) \big]\\
    \leq & c_m\sqrt{\frac B m}
\end{align}
where $c_m$ is a constant related with $m$ and can be bounded by $c_m \in (2/\pi, 1)$. In particular, we have:
\begin{align}
    \label{eqn:grad-est-qual}
    \lim_{\delta\rightarrow 0}\mathbb{E}\big[\cos (\widetilde{\nabla S}, \nabla S) \big] = c_m\sqrt{\frac B m}.
\end{align}
\end{theorem}
The proof of Theorem \ref{tho:cos} is in Appendix \ref{sec:proof}. We see that in the case of $m=3\times224\times224$ and $B=100$, the expected cosine similarity between the estimation and the ground truth gradient is only around 0.02.
Hence, we claim that direct gradient estimation, i.e. estimating by sampling directly from the entire space, cannot achieve a good gradient estimation.
This also suggests that a better approximation can be expected if we can estimate the gradient in a lower-dimensional space. \Huichen{I think the logic in the writing here is a little bit weird, but I don't know how to improve it..}
\section{Discussion and conclusions}

\section{Conclusion}
Overall we propose {QEBA}\xspace, a general query-efficient boundary-based blackbox attack framework. We in addition explore three novel subspace optimization approaches to reduce the number of queries from spatial, frequency, and intrinsic components perspectives.
Based on our theoretic analysis, we show the optimality of the proposed subspace based gradient estimation compared with the estimation over the original space.
Extensive results show that the proposed {QEBA}\xspace significantly reduces the required number of queries and yields high quality adversarial examples against both offline and onlie real-world APIs.

\subsection*{Acknowledgement}
We would like to thank Prof. Yuan Qi and Prof. Le Song for their comments and advice in this project. This work is partially supported by NSF grant No.1910100.

\newpage
\section{Background}

\section{Problem Definition}
Consider a $k$-way image classification model $f({\bf x})$ where ${\bf x}\in\mathbb{R}^m$ denotes the input image with dimension $m$, and $f({\bf x})\in\mathbb{R}^k$ represents the vector of confidence scores of the image belonging to each classes.
In boundary-based black-box attacks, the attacker can only inquire the model with queries $\{ {\bf x}_i \}$ (a series of updated images) and get the predicted labels
$\tilde{y}_i=F({\bf x_i}) = \argmax_j [f({\bf x_i})]_j,$
where $[f]_j$ represents the score of the $j$-th class. The parameters in the model $f$ and the score vector $\bf s$ are not accessible.

There is a {target-image}\xspace ${\bf x}_{tgt}$ with a \emph{benign label} $y_{ben}$. Based on the \emph{malicious label} $y_{mal}$ of their choice, the adversary will start from a {source-image}\xspace ${\bf x}_{src}$ selected from the category with label $y_{mal}$, and move ${\bf x}_{src}$ towards ${\bf x}_{tgt}$ on the pixel space while keeping $y_{mal}$ to guarantee the attack.
An image that is on the decision boundary between the two classes (e.g. $y_{ben}$ and $y_{mal}$) and is classified as $y_{mal}$ is called {\it boundary-image}\xspace.

The adversary's goal is to find an \emph{adversarial image}({adv-image}\xspace) ${\bf x}_{adv}$ such that $F({\bf x}_{adv}) = y_{mal}$ and $D({\bf x}_{tgt}, {\bf x}_{adv})$ is as small as possible, where $D$ is the distance metric (usually $L_2$-norm or $L_\infty$-norm distance). By definition, {adv-image}\xspace is a {\it boundary-image}\xspace with an optimized (minimal) distance from the {target-image}\xspace.
In the paper we focus on targeted attack and the approaches can extend to untargeted scenario naturally.

\section{Dimension Reduction-assisted Boundary Attack} \Huichen{change title to something related to `theory' blablabla?}
\section{Theoretic Analysis on {QEBA}\xspace}
\label{sec:dimred-theory}

We theoretically analyze how dimension reduction helps with the gradient estimation in {QEBA}\xspace. We show that the gradient estimation bound is tighter by sampling from a representative subspace rather than the original space.

We consider the gradient estimation as in Eqn. \ref{eq:MC_gradient_estimation} and let $\rho = \frac{||\text{proj}_{\text{span}(W)}(\nabla S)||_2}{||\nabla S||_2}$ denote the proportion of $\nabla S$ that lies on the chosen subspace $\text{span}(W)$. Then we have the following theorem on the expectation of the cosine similarity between $\nabla S$ and estimated $\widetilde{\nabla S}$:

\begin{theorem}
\label{tho:dimred}
Suppose 1) $S({\bf x})$ has $L$-Lipschitz gradients in a neighborhood of $\bf x$, 2) the sampled ${\bf v}_1, \ldots, {\bf v}_B$ are orthogonal to each other, and 3) $W^\intercal W = I$, then the expected cosine simliarity between $\widetilde{\nabla S}$ and $\nabla S$ can be bounded by:
\begin{align}
    &\bigg( 2\bigg(1-(\frac{L\delta}{2||\nabla S||_2})^2\bigg)^{\frac{n-1}{2}} - 1 \bigg)c_n\rho\sqrt{\frac B n} \\
    \leq & \mathbb{E}\big[\cos (\widetilde{\nabla S}, \nabla S) \big]\\
    \leq & c_n\rho\sqrt{\frac B n}
\end{align}
where $c_n$ is a coefficient related with the subspace dimension $n$ and can be bounded by $c_n \in (2/\pi, 1)$. In particular:
\begin{equation}
    \label{eqn:grad-est-qual-dr}
    \lim_{\delta\rightarrow 0}\mathbb{E}\big[\cos (\widetilde{\nabla_W S}, \nabla S) \big] = c_n\rho
    \sqrt{\frac B n}.
\end{equation}
\end{theorem}
The theorem proof is in Appendix \ref{sec:tho-proof}.
If we sample from the entire space (i.e. $\text{span}(W) = \mathbb{R}^m$), the expected cosine similarity is $c_m\sqrt{\frac{B}{m}}$.
If we let $m=3\times224\times224$ and $B=100$, the similarity is only around 0.02.

On the other hand, if the subspace basis $w$'s are randomly chosen, then $\rho \approx \sqrt{\frac{n}{m}}$ and the estimation quality is low. With larger $\rho$, the estimation quality will be better than sampling from the entire space.
Therefore, we further explore three approaches to optimize the representative subspace that contains a larger portion of the gradient as discussed in Section~\ref{sec:subspaces}.
For example, in the experiments we see that when $n=m/16$, we can reach $\rho=0.5$ and the expected cosine similarity increase to around 0.06.
This improves the gradient estimation quality which leads to more efficient attacks.

\section{Experiments}
In this section, we introduce our experimental setup and quantitative results of the proposed methods {QEBA}\xspace-S, {QEBA}\xspace-F, and {QEBA}\xspace-I, compared with the HSJA attack\cite{chen2019hopskipjumpattack}, which is the-state-of-the-art boundary-based blackbox attack.
Here we focus on the strongest baseline HSJA, which outperforms all of other Boundary Attack~\cite{brendel2017decision}, Limited Attack~\cite{ilyas2018black} and Opt Attack~\cite{cheng2018query} by a substantial margin.
We also show two sets of qualitative results for attacking two real-world APIs with the proposed methods.
\subsection{Datasets and Experimental Setup}
\paragraph{Datasets}
We evaluate the attacks on two offline models on ImageNet\cite{deng2009imagenet} and CelebA\cite{liu2018large} and two online face recognition APIs Face++\cite{facepp-compare-api} and Azure\cite{azure-detect-api}. We use a pretrained ResNet-18 model as the target model for ImageNet and fine-tune a pretrained ResNet-18 model to classify among 100 people in CelebA. We randomly select 50 pairs from the ImageNet/CelebA validation set that are correctly classified by the model as the source and target images.
\paragraph{Attack Setup}
Following the standard setting in \cite{chen2019hopskipjumpattack}, we use $\xi_t=||\xadv{t-1}-{\bf x}_{tgt}||_2/\sqrt{t}$ as the size in each step towards the gradient. We use $\delta_t=\frac1m ||\xadv{t-1}-{\bf x}_{tgt}||_2$ as the perturbation size and $B=100$ queries in the Monte Carlo algorithm to estimate the gradient, where $m=3\times224\times224$ is the input dimension in each Monte Carlo step.

We provide two \textbf{evaluation metrics} to evaluate the attack performance. The first is the average Mean Square Error (MSE) curve between the target image and the adversarial example in each step, indicating the magnitude of perturbation. The smaller the perturbation is, the more similar the adversarial example is with the {target-image}\xspace, thus providing better attack quality.
The second is the attack success rate based on a limited number of queries, where the `success' is defined as reaching certain specific MSE threshold. The less queries we need in order to reach a certain perturbation threshold, the more efficient the attack method is.

As for the dimension-reduced subspace, we use the dimension reduction factor $r=4$
in \emph{spatial transformed} and \emph{low frequency} subspace, which gives a 9408 dimensional subspace.
In order to generate the \emph{Intrinsic Component Subspace}, we first generate a set of image gradient vectors on the space. We average over the gradient of input w.r.t. five different pretrained substitute models - ResNet-50\cite{he2016deep}, DenseNet-121\cite{huang2017densely}, VGG16\cite{simonyan2014very}, WideResNet\cite{zagoruyko2016wide} and GoogleNet\cite{szegedy2015going}. We use part of the ImageNet validation set (280000 images) to generate the gradient vectors. Finally we adopt the scalable approximate PCA algorithm\cite{halko2011finding} to extract the top 9408 major components as the intrinsic component subspace.

\subsection{Commercial Online APIs}
Various companies provide commercial APIs (Application Programming Interfaces) of trained models for different tasks such as face recognition. Developers of downstream tasks can pay for the services and integrate the APIs into their applications. Note that although typical platform APIs provide the developers the confidence score of classes associated with their final predictions, the end-user using the final application would not have access to the scores in most cases. For example, some of Face++'s partners use the face recognition techniques for log-in authentication in mobile phones~\cite{facepp-partner}, where the user only knows the final decision (whether they pass the verification or not).

We choose two representative platforms for our real-world experiments based on only the final prediction. The first is Face++ from MEGVII\cite{facepp-compare-api}, and the second is Microsoft Azure\cite{azure-detect-api}. Face++ offers a `compare' API~\cite{facepp-compare-api} with which we can send an HTTPS request with two images in the form of byte strings, and get a prediction confidence of whether the two images contain the same person. In all the experiments we consider a confidence greater than 50\% meaning the two images are tagged as the same person. Azure has a slightly more complicated interface. To compare two images, each image first needs to pass a `detect' API call~\cite{azure-detect-api} to get a list of detected faces with their landmarks, features, and attributes. Then the features of both images are fed into a `verify' function~\cite{azure-verify-api} to get a final decision of whether they belong to the same person or not. The confidence is also given, but we do not need it for our experiments since we only leverage the binary prediction for practical purpose.

In the experiments, we use the examples in Figure~\ref{fig:src_tgt_imgs} as {source-image}\xspace and {target-image}\xspace. More specifically, we use a man-woman face as the source-target pair for the `compare' API Face++, and we use a cat-woman face as the pair for the `detect' API Azure face detection.

\begin{figure}
\centering
\begin{subfigure}[t]{.28\linewidth}
  \centering
  \includegraphics[width=\linewidth]{figs/resized_f6.png}
  \caption{Person 1}
  \label{fig:tgt_img}
\end{subfigure}
\begin{subfigure}[t]{.28\linewidth}
  \centering
  \includegraphics[width=\linewidth]{figs/resized_m3.png}
  \caption{Person 2}
  \label{fig:src_img_facepp}
\end{subfigure}
\begin{subfigure}[t]{.28\linewidth}
  \centering
  \includegraphics[width=\linewidth]{figs/resized_n3.png}
  \caption{No-face}
  \label{fig:src_img_azure}
\end{subfigure}
\caption{
The source and target images for online API experiments. All images are resized to $3\times 224\times 224$.
Image~\ref{fig:tgt_img} is the {target-image}\xspace for both APIs. Image~\ref{fig:src_img_facepp} is the {source-image}\xspace for attacking Face++ `compare' API, and \ref{fig:src_img_azure} the {source-image}\xspace for Azure `detect' API. }
\label{fig:src_tgt_imgs}
\end{figure}

\begin{figure*}[htpb]
\begin{subfigure}[t]{0.2465\linewidth}
    \centering
    \includegraphics[width=\textwidth]{results/multi_imagenet_mean.pdf}
    \caption{The MSE vs. query number on ImageNet.}
    \label{fig:result-imagenet}
\end{subfigure}
\hspace{1mm}
\begin{subfigure}[t]{0.231\linewidth}
    \centering
    \includegraphics[width=\textwidth]{results/multi_imagenet_success.pdf}
    \caption{The attack success rate with threshold $10^{-3}$ on ImageNet.}
    \label{fig:result-imagenet-sr}
\end{subfigure}
\hspace{1mm}
\begin{subfigure}[t]{0.2465\linewidth}
    \centering
    \includegraphics[width=\textwidth]{results/multi_celeba_mean.pdf}
    \caption{The MSE vs. query number on CelebA.}
    \label{fig:result-celeba}
\end{subfigure}
\hspace{1mm}
\begin{subfigure}[t]{0.235\linewidth}
    \centering
    \includegraphics[width=\textwidth]{results/multi_celeba_success.pdf}
    \caption{The attack success rate with threshold $10^{-5}$ on CelebA.}
    \label{fig:result-celeba-sr}
\end{subfigure}
\caption{The attack results on ImageNet and CelebA datasets.}
\label{fig:results}
\end{figure*}

\paragraph{Discretization Optimization for Attacking APIs}
The attack against online APIs suffers from the problem of `discretization'. That is, in the attack process we assume the pixel values to be continuous in $[0,1]$, but we need to round it into 8-bit floating point in the uploaded RGB images when querying the online APIs.
This would cause error in the Monte Carlo gradient estimation format in Equation~\ref{eq:MC_gradient_estimation} since the real perturbation between the last {\it boundary-image}\xspace and the new {\it query image}\xspace after rounding is different from the weighted perturbation vector $\delta {\bf u}_b$.

In order to mitigate this problem, we perform discretization locally. Let $P_{rd}$ be a projection from a continuous image $\bf x_c$ to a discrete image $\bf x_d = P_{rd}(\bf x_c)$. Let $\delta {\bf u'}_b = P_{rd}(\bf x+\delta {\bf u}_b) - x$, the new gradient estimation format becomes:
\begin{align}
    \widetilde{\nabla f} &= \frac1B \sum_{i=1}^B \phi(P_{rd}({\bf x}+\delta {\bf u}_b)) {\bf u'}_b.
\end{align}

\subsection{Experimental Results on Offline Models}

\begin{table*}[ht]
  \centering
  \caption{Attack success rate using different number of queries and different MSE thresholds.}
    \renewcommand\tabcolsep{5pt}
    \begin{threeparttable}
    \begin{tabular}{l|l|cccc|cccc|cccc}
    \toprule
    &  & \multicolumn{4}{c|}{\# Queries = 5000} & \multicolumn{4}{c|}{\# Queries = 10000} & \multicolumn{4}{c}{\# Queries = 20000} \\
    \cmidrule{2-6} \cmidrule{7-10} \cmidrule{11-14}
    & \makecell{MSE\\ threshold} & \makecell{HJSA} & \makecell{\\-S} & \makecell{{QEBA}\xspace\\-F} & \makecell{\\-I} & \makecell{HJSA} & \makecell{\\-S} & \makecell{{QEBA}\xspace\\-F} & \makecell{\\-I} & \makecell{HJSA} & \makecell{\\-S} & \makecell{{QEBA}\xspace\\-F} & \makecell{\\-I} \\

    \cmidrule{1-2}\cmidrule{3-6} \cmidrule{7-10} \cmidrule{11-14}
    \multirow{3}[0]{*}{ImageNet}
    & 0.01 & 0.76 & \bf 0.86 & \bf 0.86 & \bf 0.86 & 0.98 & \bf 1.00 & 0.96 & 0.98 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 \\
	& 0.001 & 0.16 & 0.40 & \bf 0.42 & 0.36 & 0.50 & 0.74 & \bf 0.76 & 0.74 & 0.84 & \bf 0.98 & 0.96 & \bf 0.98 \\
	& 0.0001 & 0.02 & \bf 0.08 & 0.06 & 0.04 & 0.06 & \bf 0.32 & 0.30 & 0.20 & 0.28 & \bf 0.70 & 0.66 & 0.68\\
	\midrule
    \multirow{3}[0]{*}{CelebA}
    & 0.01 & 0.96 & \bf 1.00 & \bf 1.00 & 0.96 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 \\
	& 0.001 & 0.90 & \bf 1.00 & \bf 1.00 & 0.94 & 0.98 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 \\
	& 0.0001 & 0.76 & \bf 0.96 & \bf 0.96 & 0.90 & 0.90 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 & \bf 1.00 \\
    \bottomrule
    \end{tabular}%
    \end{threeparttable}
  \label{tab:results}%
\end{table*}

\begin{figure}
    \centering
    \includegraphics[width=0.95\linewidth]{results/process.pdf}
    \caption{An example of attacking ImageNet trained model based on different subspaces.}
    \label{fig:result-process}
    \vspace{-0.5cm}
\end{figure}

To evaluate the effectiveness of the proposed methods, we first show the average MSE during the attack process of ImageNet and CelebA using different number of queries in Figure~\ref{fig:result-imagenet} and Figure \ref{fig:result-celeba} respectively.
We can see that all the three proposed query efficient methods outperform HSJA significantly.
We also show the attack success rate given different number of queries in Table \ref{tab:results} using different MSE requirement as the threshold. In addition, we provide the attack success rate curve in Figure \ref{fig:result-imagenet-sr} and \ref{fig:result-celeba-sr} using $10^{-3}$ as the threshold for ImageNet and $10^{-5}$ for CelebA to illustrate convergence trend for the proposed {QEBA}\xspace-S, {QEBA}\xspace-F, and {QEBA}\xspace-I, comparing with the baseline HJSA.

We observe that sampling in the optimized subspaces results in a better performance than sampling from the original space. The spatial transforamed subspace and low-frequency subspace show a similar behaviour since both of them rely on the local continuity. The intrinsic component subspace does not perform better than the other two approaches, and the potential reason is that we are only using 280000 cases to find intrinsic components on the 150528-dimensional space. Therefore, the extracted components may not be optimal. We also observe that the face recognition model is much easier to attack than the ImageNet model, since the face recognition model has fewer classes (100) rather than 1000 as of ImageNet.

A qualitative example process of attacking the ImageNet model using different subspaces is shown in Figure \ref{fig:result-process}. In this example, the MSE (shown as $d$ in the figures) reaches below $1\times10^{-3}$ using around 2K queries when samlping from the subspaces, and it is already hard to tell the adversarial perturbations in the examples. When we further tune the {adv-image}\xspace using 10K queries, it reaches lower MSE.

\subsection{Results of Attacking Online APIs}
The results of attacking online APIs Face++ and Azure are shown in Figure~\ref{fig:facepp_atk} and Figure~\ref{fig:azure_atk} respectively.
The labels on the y-axis indicate the methods. Each column represents successful attack instances with increasing number of API calls. \Huichen{I unify the two (.) and move front}
As is the nature of boundary-based attack, all images are able to produce successful attack. The difference lies in the quality of attack instances.

For attacks on Face++ `compare' API, the {source-image}\xspace is a man and the {target-image}\xspace is a woman as shown in Figure~\ref{fig:src_tgt_imgs}. Notice the man's eyes appear in a higher position in the {source-image}\xspace than the woman in the {target-image}\xspace because of the pose.
All the instances on the first row in Figure~\ref{fig:facepp_atk} based on HJSA attacks contain two pairs of eyes. The MSE scores ($d$ in the figures) also confirm that the distance between the attack instance and the {target-image}\xspace does not go down much even with more than 6000 queries. On the other hand, our proposed methods {QEBA}\xspace- can optimize attack instances with smaller magnitude of perturbation more efficiently. The perturbations are also smoother.

The attack results on Azure `detect' API show similar observations. The {source-image}\xspace is a cat and the {target-image}\xspace is the same woman. Sampling from the original high-dimensional space (HJSA) gives us attack instances that presents two cat ear shapes at the back of the human face as shown in the first row in Figure~\ref{fig:azure_atk}. With the proposed query efficient attacks, the perturbations are smoother. The distance metric ($d$) also demonstrates the superiority of the proposed methods.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.91\linewidth]{results/facepp_atk.pdf}

    \caption{Comparison of attacks on Face++ `compare' API. Goal: obtain an image that is tagged as `same person' with the {source-image}\xspace person 2 (Figure~\ref{fig:src_img_facepp}) by the API when humans can clearly see person 1 here.}
    \label{fig:facepp_atk}
    \vspace{-0.3cm}
\end{figure}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.91\linewidth]{results/azure_atk.pdf}

    \caption{Comparison of attacks on Azure `detect' API. Goal: get an image that is tagged as `no face' by the API when humans can clearly see a face there. The {source-image}\xspace is a cat as shown in Figure~\ref{fig:src_img_azure}.}
    \label{fig:azure_atk}
    \vspace{-0.3cm}
\end{figure}

\section{Introduction}

Recent developments of machine learning (ML), especially deep neural networks (DNNs), have advanced a number of real-world applications, including object detection~\cite{ren2015faster}, drug discovery~\cite{chen2018rise}, and robotics~\cite{lenz2015deep}. In the meantime, several safety-critical applications have also adopted ML, such as autonomous driving vehicles~\cite{chen2015deepdriving} and surgical robots~\cite{richter2019open,mlsurgicalrobotics}.
However, recent research have shown that machine learning systems are vulnerable to \emph{adversarial examples}, which are inputs with small magnitude of adversarial perturbations added and therefore cause arbitrarily incorrect predictions during test time~\cite{eykholt2017robust,xiao2018generating,carlini2017towards,goodfellow2014explaining,chaowei2018characterizing,chaowei2018spatially}.
Such adversarial attacks have led to great concerns when applying ML to real-world applications. Thus in-depth analysis of the intrinsic properties of these adversarial attacks as well as potential defense strategies are required.

First, such attacks can be categorized into whitebox and blackbox attacks based on the attacker's knowledge about the victim ML model. In general, the whitebox attacks are possible by leveraging the gradient of the model --- methods like fast gradient sign method (FGSM) ~\cite{goodfellow2014explaining}, optimization based attack~\cite{carlini2017towards}, projected gradient descent based method (PGD)~\cite{madry2017towards} have been proposed. However, whitebox attack is less practical, given the fact that most real-world applications will not release the actual model they are using. In addition, these whitebox attacks are shown to be defendable~\cite{madry2017towards}.
As a result, blackbox adversarial attack have caught a lot of attention in these days.
In blackbox attack, based on whether an attacker needs to query the victim ML model, there are query-free (e.g. transferability based attack) and query-based attacks. Though \emph{transferability} based attack does not require query access to the model, it assumes the attacker has access to the large training data to train a substitute model, and there is no guarantee for the attack success rate. The query based attack includes score-based and boundary-based attacks. Score-based attack assumes the attacker has access to the class probabilities of the model, which is less practical compared with boundary-based attack which only requires the final model prediction, while both require large number of queries.

In this paper,  we propose Query-Efficient Boundary-based blackbox Attack ({QEBA}\xspace) based only on model's final prediction labels as a general framework to minimize the query number.
Since the gradient estimation consumes the majority of all the queries, the main challenge of reducing the number of queries for boundary-based blackbox attack is that a high-dimensional data (e.g. an image) would require large number of queries to probe the decision boundary. As a result, we propose to search for a small representative subspace for query generation.
In particular, queries are generated by adding perturbations to an image. We explore the subspace optimization methods from three novel perspectives for perturbation sampling: 1) spatial, 2) frequency, and 3) intrinsic component.
The first one leverages spatial transformation (e.g. linear interpolation) so that the sampling procedure can take place in a low-dimensional space and then project back to the original space.
The second one uses intuition from image compression literature and samples from low frequency subspace and use discrete consine transformation (DCT)~\cite{guo2018low} to project back.
The final one performs scalable gradient matrix decomposition to select the major principle components via principle component analysis (PCA)~\cite{wold1987principal} as subspace to sample from.
In addition
, we theoretically prove the optimality of them on estimating the gradient compared with estimating the gradient directly over the original space.

To demonstrate the effectiveness of the proposed blackbox attack {QEBA}\xspace methods,
we conduct extensive experiments on high dimensional image data including ImageNet~\cite{deng2009imagenet} and CelebA~\cite{liu2018large}. We perform attacks on the ResNet model~\cite{he2016deep}, and show that compared with the-state-of-the-art blackbox attack methods, the different variations of {QEBA}\xspace can achieve lower magnitude of perturbation with smaller number of queries (attack success rate 100\%).
\Huichen{I deleted one sentence here because its expression is not accurate.}
In order to show the real-world impact of the proposed attacks, we also perform {QEBA}\xspace against online commercial APIs including MEGVII Face++\cite{facepp-compare-api} and Microsoft Azure\cite{azure-detect-api}. Our methods can successfully attack the APIs with perturbations of reasonable magnitude.
Towards these different subspaces, our conjecture is that the over-all performance on different subspaces depends on multiple factors including dataset size, model smoothness, adversarial attack goals etc. Therefore, our goal here is to make the first attempt towards providing sufficient empirical observations for these three subspaces, while further extensive studies are required to compare different factors of these subspaces, as well as identifying new types of subspaces.

The \textbf{contributions} of this work are summarized as follows:
1) We propose a general Query-Efficient Boundary-based blackbox Attack {QEBA}\xspace to reduce the number of queries based on boundary-based attack. The {QEBA}\xspace contains three variations based on three different representative subspaces including spatial transformed subspace, low frequency subspace, and intrinsic component subspace;
2) We theoretically demonstrate that gradient estimation in the whole gradient space is inefficient in terms of query numbers, and we prove the optimality analysis for our proposed query-efficient gradient estimation methods;
3) We conduct comprehensive experiments on two high resolution image datasets: ImageNet and CelebA. All the different variations of {QEBA}\xspace outperform the state-of-the-art baseline method by a large margin;
4) We successfully attack two real-world APIs including Face++\cite{facepp-compare-api} and Azure\cite{azure-detect-api} and showcase the effectiveness of {QEBA}\xspace.

\section{Query-Efficient Boundary-based blackbox Attack ({QEBA}\xspace)}
\label{sec:subspaces}
In this section we first introduce the pipeline of {QEBA}\xspace which is based on HopSkipJumpAttack (HSJA)~\cite{chen2019hopskipjumpattack}. We then illustrate the three proposed query reduction approaches in detail. We provide the theoretic justification of {QEBA}\xspace in Section~\ref{sec:dimred-theory}.
The pipeline of the proposed Query-Efficient Boundary-based blackbox Attack (QEBA) is shown in Figure \ref{fig:pipeline} as an illustrative example. The goal is to produce an {adv-image}\xspace that looks like ${\bf x}_{tgt}$ (cat) but is mislabeled as the malicious label (fish) by the victim model.
First, the attack initializes the {adv-image}\xspace with ${\bf x}_{src}$.
Then it performs an iterative algorithm consisting of three steps: \textbf{estimate gradient at decision boundary} which is based on the proposed representative subspace, \textbf{move along estimated gradient}, and \textbf{project to decision boundary} which aims to move towards ${\bf x}_{tgt}$.

First, define the adversarial prediction score $S$ and the indicator function $\phi$ as:
\begin{align}
    S_{{\bf x}_{tgt}}({\bf x}) &= [f({\bf x})]_{y_{mal}} - \max_{y \neq y_{mal}} [f({\bf x})]_y,\\
    \phi_{{\bf x}_{tgt}}({\bf x}) &= \text{sign}(S_{{\bf x}_{tgt}}({\bf x})) =
    \begin{cases}
    1 & \text{if } S_{{\bf x}_{tgt}}({\bf x})\geq 0;\\
    -1 & \text{otherwise}.
    \end{cases}
\end{align}
We abbreviate the two functions as $S({\bf x})$ and $\phi({\bf x})$ if it does not cause confusion. In boundary-based attack, the attacker is only able to get the value of $\phi$ but not $S$.

In the following, we first introduce the three interative steps in the attack in Section~\ref{sec:iterative_attack}, then introduce three different methods for generating the optimized representative subspace in Section~\ref{sec:name-S}-\ref{sec:name-I}.

\subsection{General framework of {QEBA}\xspace}
\label{sec:iterative_attack}

\begin{figure}
    \centering

    \includegraphics[width=\linewidth]{figs/arxiv_ver/estimation.jpeg}
    \caption{Query model and estimate gradient near the decision boundary.}
    \label{fig:gradient_estimation}

\end{figure}

\paragraph{Estimate gradient at decision boundary}
Denote $\xadv{t}$ as the {adv-image}\xspace generated in the $t$-th step. The intuition in this step is that we can estimate the gradient of $S(\xadv{t})$ using only the access to $\phi$ if $\xadv{t}$ is at the decision boundary. This gradient can be sampled via Monte Carlo method:
\begin{align}
    \widetilde{\nabla S} = \frac1B \sum_{i=1}^B \phi(\xadv{t}+\delta {\bf u}_b) {\bf u}_b
    \label{eq:MC_gradient_estimation}
\end{align}
where $\{{\bf u}_b\}$ are $B$ randomly sampled perturbations with unit length and $\delta$ is a small weighting constant. An example of this process is shown in Figure \ref{fig:gradient_estimation}. The key point here is how to sample the perturbation ${\bf u}_b$'s and we propose to draw from a representative subspace in $\mathbb{R}^n$.

Formally speaking, let $W=[w_1, \ldots, w_n] \in \mathbb{R}^{m\times n}$ be $n$ orthonormal basis vectors in $\mathbb{R}^m$, meaning $W^\intercal W = I$. Let $\text{span}(W) \subseteq \mathbb{R}^m$ denote the $n$-dimensional subspace spanned by $w_1, \ldots, w_n$. We would like to sample random perturbations from $\text{span}(W)$ instead of from the original space $\mathbb{R}^m$. In order to do that, we sample ${\bf v}_b \in \mathbb{R}^n$ from unit sphere in $\mathbb{R}^n$ and let ${\bf u}_b = W {\bf v}_b$. The detailed gradient estimation algorithm is shown in Alg.\ref{alg:grad-approx}.
Note that if we let $\text{span}(W)=\mathbb{R}^m$, this step will be the same as in \cite{chen2019hopskipjumpattack}. However, we will sample from some representative subspace so that the gradient estimation is more efficient, and the corresponding theoretic justification is discussed in Section \ref{sec:dimred-theory}.

\begin{algorithm}
\caption{Gradient Approximation Based {QEBA}\xspace}
\label{alg:grad-approx}
\begin{algorithmic}[1]
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
 \renewcommand{\algorithmicensure}{\textbf{Output:}}
 \REQUIRE a data point on the decision boundary ${\bf x} \in \mathbb{R}^m$, basis of the subspace $W \in \mathbb{R}^{m\times n}$, number of random sampling $B$, access to query the decision of victim model $\phi$.
 \ENSURE the approximated gradient $G$
 \STATE sample $B$ random Gaussian vectors of the lower dimension: $V_{rnd} \in \mathbb{R}^{B \times n}$.
 \STATE project the random vectors onto the gradient basis to get the perturbation vectors: $U_{rnd} = V_{rnd} \cdot W^\intercal$.
 \STATE get query points by adding perturbation vectors with the original point on the decision boundary: ${\bf x}_q[i] = {\bf x} + U_{rnd}[i]$.
 \STATE Monte Carlo approximation for the gradient: $G = \frac{1}{B}\sum_{i=1}^{B} \phi({\bf x}_q[i]) \cdot U_{rnd}[i]$
 \RETURN $G$
\end{algorithmic}
\end{algorithm}
\vspace{-0.5cm}

\paragraph{Move along estimated gradient}
After we have estimated the gradient of adversarial prediction score $\nabla S$, we will move the $\xadv{t}$ towards the gradient direction:
\begin{align}
    \label{eqn:move-grad}
    \hat{\bf x}_{t+1} = \xadv{t} + \xi_t \cdot \frac{\widetilde{\nabla S}}{||\widetilde{\nabla S}||_2}
\end{align}
where $\xi_t$ is the step size at the $t$-th step. Hence, the prediction score of the adversarial class will be increased.

\vspace{-2mm}
\paragraph{Project to decision boundary}
Current $\hat{\bf x}_{t+1}$ is beyond the boundary, we can move the {adv-image}\xspace towards the target image so that it is projected back to the decision boundary:
\begin{align}
    \label{eqn:binary}
    \xadv{t+1} = \alpha_t \cdot {\bf x}_{tgt} + (1-\alpha_t) \cdot \hat{\bf x}_{t+1}
\end{align}
where the projection is achieved by a binary search over $\alpha_t$.

Note that we assume $\xadv{t}$ lies on the boundary while ${\bf x}_{src}$ does not lie on the boundary. Therefore, in the initialization step we need to first apply a project operation as in Eqn. \ref{eqn:binary} to get $\xadv{0}$.

In the following sections, we will introduce three exploration for the representative subspace optimization from spatial, frequency, and intrinsic component perspectives.

\subsection{Spatial Transformed Subspace ({QEBA}\xspace-S)}
\label{sec:name-S}
First we start with the spatial transformed query reduction approach.
The intuition comes from the observation that the gradient of input image has a property of local similarity\cite{ilyas2018prior}. Therefore, a large proportion of the gradients lies on the low-dimensional subspace spanned by the bilinear interpolation operation\cite{spath1993two}.
In order to sample random perturbations for an image, we first sample a lower-dimensional random perturbation $Q$ of shape $\lfloor \frac Nr \rfloor \times \lfloor \frac Nr \rfloor$, where $r$ is the hyperparameter of dimension reduction factor. Then we use bilinear-interpolation to map it back the original image space, $X = \text{Bil\_Interp}(Q)$.

The basis of this spatial transformed subspace is the images transformed from unit perturbations in the lower space:
\begin{align*}
    w^{(i,j)} = \text{Bil\_Interp}(e^{(i,j)}),\quad 0\leq i,j \leq \lfloor N/r \rfloor
\end{align*}
where $e^{(i,j)}$ represents the unit vector that has 1 on the $(i,j)$-th entry and 0 elsewhere.

\subsection{Low Frequency Subspace ({QEBA}\xspace-F)}
\label{sec:name-F}
In general the low frequency subspace of an image contains the most of the critical information, including the gradient information\cite{guo2018low}; while the high frequency signals contain more noise than useful content.
Hence, we would like to sample our perturbations from the low frequency subspace via Discrete Cosine Transformation(DCT)\cite{ahmed1974discrete}. Formally speaking, define the basis function of DCT as:
\begin{align}
    \phi(i,j) = \cos \bigg(\frac{(i+\frac12)j}{N} \pi \bigg)
\end{align}
The inverse DCT transformation is a mapping from the frequency domain to the image domain $X=\text{IDCT}(Q)$:
\begin{align}
    X_{i_1,i_2}=\sum_{j_1=0}^{N-1}\sum_{j2=0}^{N-1} N_{j_1} N_{j_2} Q_{j_1,j_2} \phi(i_1,j_1) \phi(i_2,j_2)
\end{align}
where $N_j=\sqrt{1/N}$ if $j=0$ and otherwise $N_j=\sqrt{2/N}$.

We will use the lower $\lfloor N/r \rfloor$ part of the frequency domain as the subspace, i.e.
\begin{align}
    w^{(i,j)} = \text{IDCT}(e^{(i,j)}),\quad 0\leq i,j \leq \lfloor N/r \rfloor
\end{align}
where hyperparameter $r$ is the dimension reduction factor.

\subsection{Intrinsic Component Subspace ({QEBA}\xspace-I)}
\label{sec:name-I}
\begin{figure}
    \centering

    \includegraphics[width=\linewidth]{figs/arxiv_ver/subspace.jpeg}
    \caption{Generate representative subspace from the original high-dimensional gradient space.}
    \label{fig:bases_generation}
    \vspace{-0.5cm}
\end{figure}

Principal Component Analysis (PCA)\cite{wold1987principal} is a standard way to perform dimension reduction in order to search for the intrinsic components of the given instances. Given a set of data points in high dimensional space, PCA aims to find a lower dimensional subspace so that the projection of the data points onto the subspace is maximized.

Therefore, it is possible to leverage PCA to optimize the subspace for model gradient matrix. However, in order to perform PCA we will need a set of data points. In our case that should be a set of gradients of $S({\bf x})$ w.r.t. different $\bf x$. This is not accessible under black-box setting. Hence, we turn to a set of `reference models' to whose gradient we have access. As shown in Figure \ref{fig:bases_generation}, we will use a reference model to calculate a set of image gradients ${\bf g}_1, {\bf g}_2, \ldots, {\bf g}_K \in \mathbb{R}^m$ Then we perform a PCA to extract its top-$n$ principal components - ${\bf w}_1, \ldots, {\bf w}_n \in \mathbb{R}^m$. These $w$'s are the basis of the Intrinsic Component Subspace.
Note that different from transferability, we do not restrict the reference models to be trained by the same training data with the original model, since we only need to search for the intrinsic components of the give dataset which is relatively stable regarding diverse models.

In practice, the calculation of PCA may be challenging in terms of time and memory efficiency based on large high-dimensional dataset (the data dimension on ImageNet is over 150k and we need a larger number of data points, all of which are dense). Therefore, we leverage the randomized PCA algorithms\cite{halko2011finding} which accelerates the speed of PCA while achieving comparable performance.

An additional challenge is that the matrix $X$ may be too large to be stored in memory. Therefore, we store them by different rows since each row (i.e. gradient of one image) is calculated independently with the others. The multiplication of $X$ and other matrices in memory are then implemented accordingly.

\section{Related Work}

\paragraph{Boundary-based Attack}
Boundary Attack~\cite{brendel2017decision} is one of the first work that uses final decisions of a classifier to perform blackbox attacks. The attack process starts from the {source-image}\xspace, which is classified as the adversarial {\it malicious-class}\xspace. Then it employs a reject sampling mechanism to find a {\it boundary-image}\xspace that still belongs to the {\it malicious-class}\xspace by performing random walk along the boundary. The goal is to minimize the distance between the {\it boundary-image}\xspace and the {target-image}\xspace. However, as the steps taken are randomly sampled, the convergence of this method is slow and the query number is large.

Several techniques have been proposed to improve the performance of Boundary Attack. \cite{brunner2019guessing,srinivasan2019black,guo2018low} propose to choose the random perturbation in each step more wisely instead of Gaussian perturbation, using Perlin noise, alpha distribution and DCT respectively. \cite{ilyas2018black,khalid2019red,liu2019geometry,chen2019hopskipjumpattack} propose a similar idea - approximating the gradient around the boundary using Monte Carlo algorithm.

There are two other blackbox attacks which are not based on the boundary. \cite{cheng2018query} proposes to transform the boundary-based output into a continuous metric, so that the score-based attack techniques can be adopted. \cite{dong2019efficient} adopts evolution algorithm to achieve the decision-based attack against face recognition system.
\vspace{-5mm}
\paragraph{Dimension Reduction in Score-based Attack}
Another line of work involves the dimension reduction techniques only for the score-based attacks, which requires access to the prediction of confidence for each class.
In~\cite{guo2018low}, the authors draw intuition from JPEG codec~\cite{wallace1992jpeg} image compression techniques and propose to use discrete cosine transform (DCT) for generating low frequency adversarial perturbations to assist score-based adversarial attack.
AutoZoom~\cite{tu2019autozoom} trains an auto-encoder offline with natural images and uses the decoder network as a dimension reduction tool. Constrained perturbations in the latent space of the auto-encoder are generated and passed through the decoder. The resulting perturbation in the image space is added to the benign one to obtain a query sample.

redpajama_set_name: RedPajamaArXiv