text:
\section{Introduction}

In the \emph{maximum expected value all-or-nothing subset} problem, a decision maker seeks to maximize the expected value of a subset of activities $[n]=\{1,\ldots,n\}$, where  each activity $i\in [n]$ is associated with a positive profit $c_i$ and probability of success $ p_i$. The profits are earned in an all-or-nothing fashion -- the overall success of a subset of activities depends on the individual success of all of its independent member activities. Accordingly, the problem is
\[
\max_{S\in 2^{[n]}}\sum_{i\in S}c_i\prod_{j\in S}p_j.
\]
The problem arises in the design of serial reliability (or 1-out-of-$n$) systems in which each component may have a different value and reliability but deriving value from the system depends on all of the selected components being operational. For example, this objective function arises in failure-aware barter exchanges such as kidney-exchange cycles in which the failure of a single pair to barter may cause the entire chain or cycle of transactions to fail~\cite{Dickerson13}. In that setting arcs of a directed graph represent possible transplants and donations; $c_i$ would be the value of transplant $i$ (that connects some donor-patient pair), and $p_i$ is the probability of the transplant $i$ taking place. The current all-subset setting corresponds to a special case of a complete directed graph of possible transplants, where a particular node (patient-donor pair) is connected to all other graph nodes through certain (probability-one) arcs. Another setting is a utility-maximizing evader who may select a subset of elicit activities that are under inspection, and the evader does not receive any value if one or more of the selected covert activities are exposed. This problem is proposed as an extension of the basic model studied in~\cite{Goldberg17}. The problem may arise in network settings and a special case is that of disjoint edges that is the subject of the current paper, which is next shown to be NP-hard.

We find it convenient to formulate
the problem as the (unconstrained) nonlinear mathematical program with binary decision variables $x_1,\ldots,x_n$,
\begin{align}
\label{FORM3}
& \max_{x\in\{0,1\}^n} \sum_{i=1}^n c_{i}x_{i}\prod_{j=1}^np_j^{x_j}.
\end{align}

The complexity of several related, yet different, problems has been investigated in the literature. The minimization of a (continuous) positive bilinear objective function of two variables subject to linear inequality constraints has been shown to be (strongly) NP-hard in~\cite{Matsui96}. The maximization of a product of linear functions of binary decision variables has been shown to be NP-hard in~\cite{Hammer02}. Half-product pseudo-Boolean function minimization, a special case of unconstrained quadratic binary minimization, has been shown to be NP-hard in~\cite{Badics98}. For an extensive survey of pseudo-Boolean optimization including these special cases the reader may refer to~\cite{Boros02}.

Related cost-reliability problems, with a different objective function than~\eqref{FORM3}, include variants that have been shown to be solvable in polynomial time. Let $\mathcal S\subseteq 2^{[n]}$ denote a collection of feasible item subsets.
Then a general
cost-reliability ratio minimization problems takes the form
\begin{equation}
\label{RATIOPROB}
\min_{S\in \mathcal S}\frac{\sum_{i\in S}c_i}{\prod_{i\in S} p_i}.
\end{equation}
 Such problems include the minimization of the spanning-tree cost to reliability ratio~\cite{Chandrasekaran84} when $\mathcal S$ is the set of all  spanning trees of a given graph. Katoh \cite{Katoh92} considers a general cost-reliability ratio minimization problem under the  assumption that given $E\subseteq [n]$, the problem of determining $S\subseteq E$ with $S\in \mathcal S$ and minimum $\sum_{i\in S}c_i$ can be solved in polynomial time in $\card E$. In \cite{Katoh92} a fully polynomial time approximation scheme (FPTAS) is developed for this problem, but the computational complexity was unresolved and appears to remain open. Also~\cite{Katoh87} develops an FPTAS for a general quasiconcave minimization problem.
 Note that in contrast, the maximization variant of the ratio problem~\eqref{RATIOPROB} with $\mathcal S=2^{[n]}$ can be solved in polynomial time via the Dinkelbach algorithm; see~\cite{Hansen14} and references therein.

We first establish the NP-hardness of the maximum expected value all-or-nothing subset.

Then we develop an FPTAS for this problem.

\section{Maximum Expected Value All-Or-Nothing Subset - Complexity}

 First, observe that the objective function of problem~\eqref{FORM3} can be equivalently replaced (maintaining all optimal solutions) by the concave objective
\begin{equation}
\label{LOGTRANS}
z(x)=\ln\left(\sum_{i=1}^nc_{i}x_{i}\right)+\sum_{i=1}^n\ln p_{i}x_{i}.
\end{equation}

Note that if for some $i\in [n]$, $p_i=1$, then evidently $x^*_i=1$ in every $x^*$ is optimal for~\eqref{FORM3}, while similarly $p_i=0$ implies that $x^*_i=0$. Therefore, the following assumption is without loss of generality:
\begin{assumption}
	For $i\in [n]$, the probabilities satisfy the inequalities  $0<p_i<1$.
\end{assumption}

\medskip

For fixed $M>1$ and $y>0$ let
\[
f(y)=\ln y-\frac{y}{M}.
\] The following lemma establishes the optimal value of $f$ and also that to determine a maximizer of $f$ over the integers it suffices to be able to approximately evaluate $f$ with precision that is bounded by a function of $M$.

\begin{lemma}\label{CNVXLEM} Let $M > 1$ be an integer. Then, the function $f$ is concave, with a unique maximum at $f(M)=\ln(M)-1$. Furthermore, for any positive integer $N\neq M$ we have $f(M)-f(N)\geq\frac{1}{5M^2}$.
\end{lemma}
\begin{proof}
	Since $f'(y)=\frac{1}{y}-\frac{1}{M}$ has a unique zero at $y=M$, and $f''(y)=\frac{-1}{y^2}<0$ holds for all $y>0$, the first part of our claim immediately follows. Keeping in mind that $f(y)$ is concave with a unique maximum at $y=M$, for any positive integer $N<M$ we have
	$$f(M)-f(N)\geq f(M-\frac{1}{2})-f(M-1)\geq\frac{1}{2} f'(M-\frac{1}{2}) =\frac{1}{2}\left(\frac{1}{M-\frac{1}{2}}-\frac{1}{M}\right)=\frac{1}{4M^2-2M}.$$
	Similarly, for any integer $N>M$ we have
	$$f(M)-f(N)\geq f(M+\frac{1}{2})-f(M+1)\geq\frac{-1}{2} f'(M+\frac{1}{2}) =\frac{-1}{2}\left(\frac{1}{M+\frac{1}{2}}-\frac{1}{M}\right)=\frac{1}{4M^2+2M}.$$
	As $\frac{1}{4M^2-2M}\geq\frac{1}{4M^2+2M}\geq\frac{1}{5M^2}$ holds for any integer $M>1$, the proposition follows.
\end{proof}

In order to prove NP-hardness, we first show that a given instance of the subset sum problem can be decided by solving a maximum expected value all-or-nothing subset problem with the logarithmically
 transformed  objective~\eqref{LOGTRANS} and the $\ln p_i$ values as the input parameters.

\begin{lemma}\label{MAXPROP} Let $c_1,\dots,c_n$ and $M$ be positive integers. Then, there exists an $x\in\{0,1\}^n$ such that $\sum_{i=1}^nc_ix_i=M$ if and only if the optimal objective value of the following maximization problem equals $\ln M-1$.
\begin{equation}\label{maximization}\max\limits_{{x}\in\{0,1\}^n}\ln\left(\sum\limits_ {i=1}^nx_ic_i\right)-
\frac{1}{M}\sum\limits_ {i=1}^nx_ic_i
\end{equation}
\end{lemma}
\begin{proof} First,
by Lemma~\ref{CNVXLEM} $f$ has a unique maximum at $y=M$, $f(M)=\ln(M)-1$. Also note that the objective function in \eqref{maximization} can be written as $f\left(\sum\limits_ {i=1}^nx_ic_i\right)$.

Now assume that $\sum_{i=1}^nc_ix_i=M$ holds for some ${x}\in\mathbb{R}^n$.  Since ${x}$ is a solution of \eqref{maximization} with objective value $\ln(M)-1$, it is also an optimal solution according to our observation.

Similarly, if ${x}\in\{0,1\}$ is an optimal solution of \eqref{maximization} with objective value $\ln(M)-1$ then by our observation we have $\sum\limits_{i=1}^nx_ic_i=M$.
\end{proof}

The equivalence of the optimization problems following the log transformation of the objective~\eqref{LOGTRANS} and the fact that the $c_i$ values are integer together imply the following corollary of Lemma~\ref{MAXPROP}.

\begin{corollary}
\label{COR1}
Let $c_1,\dots,c_n$ and $M$ be positive integers. There exists a subset $I\subseteq [n]$ such that $\sum_{i\in I}c_i=M$ if and only if the optimal objective value of the problem
\begin{equation}\label{maximization2}\max\limits_{{x}\in\{0,1\}^n}\left(\sum_ {i=1}^n c_ix_i\right)\prod_ {i=1}^ne^{-\frac{ c_i}{M} x_i}
\end{equation}
is greater than $\max\{(M-1)e^{-1+1/M},(M+1)e^{-1-1/M}\}$. Equivalently,~\eqref{maximization2} has an optimal objective value of $M e^{-1}$ if and only if~\eqref{maximization} has an optimal objective \[
\max_{x\in\{0,1\}^n}z(x)>\max\left\{\ln(M-1)-\frac{M-1}{M},\ln(M+1)-\frac{M+1}{M}\right\}.
\]
\end{corollary}

To prove that~\eqref{FORM3} is NP-hard it has to be shown that the reduction is polynomial time. However, as the input parameters $e^{-c_i/M}$ for each $i\in [n]$ cannot be exactly represented using a polynomial number of bits we employ a simple rounding argument.

For a given $K>0$ let
\begin{align*}
\hat p_i = \frac{\lfloor K e^{-\frac{c_i}{M}} \rfloor}{K} , && \text{and} &&
\hat z(x)=\ln(\sum_{i=1}^n c_ix_i)+\sum_{i=1}^n\ln \hat p_i x_i.
\end{align*} Observe that $p_i-\frac{1}{K} \leq \hat p_i \leq p_i$.
The following Lemma establishes the existence of a $K$ that is polynomial in the input size for which the maximizers of $\hat z$ and $z$ coincide.

\begin{lemma}
\label{LEM1}
For $c_{\text{max}}< M$, there exists a positive $K \in O ( n  M^2)$ that satisfies for all
$x^*$ that are optimal for~\eqref{FORM3},
\[
z(x^*)-\max_{x\in\{0,1\}^n}\hat z(x) < \ln M - \max\left\{\ln(M-1)+\frac{1}{M}, \ln(M+1)-\frac{1}{M}\right\}.
\]  In particular, this inequality holds for any $K > \frac{5nM^2}{1-1/(10nM^2)}$.
\end{lemma}
\begin{proof} Consider an $x\in\{0,1\}^n$. Then,
\begin{align*}
 z(x)-\hat z(x)&=\ln\left(\sum_{i=1}^nc_ix_i\right)+\sum_{i=1}^{n}\ln p_i x_i -\ln\left(\sum_{i=1}^nc_ix_i\right)-\sum_{i=1}^{n}\ln\hat p_ix_i\\
 & \leq \sum_{i=1}^n \ln p_i - \ln (p_i - 1/K)=\sum_{i=1}^n \ln \left(\frac{p_i}{p_i-1/K}\right)\\
 & = \sum_{i=1}^n\ln\left(\frac{1}{1-1/(Kp_i)}\right) \leq -n\ln\left(1-\frac{1}{Ke^{-c_{max}/M}}\right).
\end{align*}
Since this upper bound holds for every $x\in\{0,1\}^n$ it also applies to the maxima of~\eqref{FORM3}, and by Lemma~\ref{CNVXLEM} it suffices to choose $K$ so that
\begin{align*}
& -n\ln\left(1-\frac{1}{Ke^{-c_{max}/M}}\right) &&<&&  \frac{1}{5M^2} && \leq \min_{L\neq M}\{f(M)-f(L)\} \\
&\Leftrightarrow
 1-\frac{e^{c_{max}/M}}{K} &&>&& e^{-\frac{1}{5nM^2}}
&&\Leftrightarrow K > \frac{e^{c_{max}/M}}{1-e^{-\frac{1}{5nM^2}}}>\frac{e}{1-e^{-\frac{1}{5nM^2}}}.
\end{align*} By a Taylor series expansion of the denominator it follows that any
$K>\frac{5nM^2}{1-1/(10nM^2)}$
is sufficiently large.
\end{proof}

\begin{proposition}
The all-or nothing subset problem~\eqref{FORM3} is NP-hard.
\end{proposition}
\begin{proof} We prove our claim by providing a reduction of the subset sum problem with positive integer inputs, which is known to be NP-hard. Consider an instance where the goal is to decide whether there exists a subset of $\{c_1,\dots,c_n\}\subset\mathbb{N}$ that sums to $M\in\mathbb{N}$. Without losing of generality it is assumed that $c_{\text{max}}\leq M$. For each $i\in[n]$, let $p_i = e^{-\frac{c_i}{M}}$. Let $K\in O(nM^2)$ be an integer satisfying the condition of Lemma~\ref{LEM1} (which also states that it suffices to choose $K=6nM^2$). Set $\hat p_i = \lfloor p_i K\rfloor / K\geq  e^{-\frac{c_i}{M}}-\frac{1}{K}$ for each $i\in[n]$.
Following Corollary~\ref{COR1} the subset sum problem has a feasible solution if and only if
\[
\max_{x\in\{0,1\}^n} z(x) = \ln M - 1 > \max\left\{\ln(M-1)-\frac{M-1}{M},\ln(M+1)-\frac{M+1}{M}\right\}.
\]
By the choice of $K$ and Lemma~\ref{LEM1} it follows that
\[
\max_{x\in\{0,1\}^n} z(x) - \max_{\{0,1\}^n}\hat z(x)
< \ln M - \max\left\{\ln(M-1)-\frac{1}{M}, \ln(M+1)+\frac{1}{M}\right\}\]
Then it follows there exists an $x\in\{0,1\}^n$ such that $\sum_{i=1}^nc_ix_i=M$ if an only if \[
\max_{x\in\{0,1\}^n}\hat z(x)>\max\left\{\ln(M-1)-\frac{M-1}{M},\ln(M+1)-\frac{M+1}{M}\right\}.
\] Since $K\in O(nM^2)$ it follows that the reduction of subset sum is polynomial in $n$, $\ln M$ and $\ln c_{max}$.
\end{proof}

\section{Approximation of Maximum Expected Value All-or-Nothing Subset}

We now develop an FPTAS for our nonlinear unconstrained problem~\eqref{FORM3}. To this end we first consider a pseudo-polynomial time algorithm. This analysis is similar to that of a related constrained linear problem, namely the knapsack problem;  see~\cite{Ibarra75,Gens80,vazirani01}. A fundamental difference is that~\eqref{FORM3}  unconstrained.

\subsection{A Pseudo-polynomial Dynamic Program}
For $i\in [n]$ let $P(i,C)$ denote the maximum probability of a subset of $[i]$ with a profit of exactly $C$.
Consider the dynamic program (DP) given by the equations
\begin{align}
\label{DPEQNS}
P(i,C)=\begin{cases}
\max\{P(i-1,C),  p_i \cdot P(i-1,C-c_i)\} & i\geq 2, c_i < C\\
P(i-1,C) & i\geq 2, c_i\geq C\\
p_1 & i=1 \text { and } c_{1}=C\\
1 & C=0\\
0 & \text{ otherwise.}
\end{cases}
\end{align}

Let $\bar C$ denote an upper bound on the sum of profits of an item set that is optimal for~\eqref{FORM3}. A straightforward upper bound is $\bar C = \sum_{i=1}^n c_i$.

Then, the problem of determining $x\in\{0,1\}^n$ that maximizes
~\eqref{FORM3} is solved by determining
\begin{equation}
\label{DPSOL}
\max_C\set{C\cdot P(n,C)}{C = \min_{i\in[n]}\{c_i\},\min_{i\in[n]}\{c_i\}+1,\ldots, \bar C}.
\end{equation}
The total running time of this algorithm that determines an optimum of~\eqref{FORM3} through~\eqref{DPSOL} is $O(n\bar C)$. In the following let $x^*\in\{0,1\}^n$ be an optimal solution for~\eqref{FORM3} with support $S^*=\set{i\in[n]}{x^*_i=1}$, and let $C^*=\sum_{i\in S^*}c_i$ denote the corresponding maximizer of~\eqref{DPSOL}.

\noindent The next lemma establishes a lower bound on the probabilities of items that are included in an optimal solution.

\begin{lemma}
	\label{LEMHALF} Suppose $S^*$ is (the support of a solution that is) optimal for~\eqref{FORM3} with $\card{S^*}\geq 2$, and $l\in\argmin_{i\in S^*}\{p_i\}$.
If $p_l<\frac{1}{2}$ then $\prod_{i\in S^*\setminus\{l\}}p_i\geq\frac{1}{2}$.
\end{lemma}
\begin{proof}
	Assume for the sake of deriving a contradiction that there exists an $l\in S^*$ with $p_l  <  \frac{1}{2}$ and $\prod_{i\in S^*\setminus \{l\}}p_i < \frac{1}{2}$. Let $X=\prod_{i\in  S^*\setminus\{l\}}p_i\sum_{i\in \hat S^*\setminus\{l\}}c_i$. Then, \[
	\prod_{i\in S^*}p_i\sum_{i\in S^*}c_i=p_l X + p_lc_l\prod_{i\in S^*\setminus \{l\}}p_i < \max\{X,p_lc_l\},
	\] thereby establishing a contradiction with the optimality of $S^*$.
\end{proof}

\noindent In particular Lemma~\ref{LEMHALF} implies the following corollary.

\begin{corollary}\label{ONEHALFCOR}
Suppose $S^*$ is (the support of a solution that is) optimal for~\eqref{FORM3}. Then \[\card{\set{i\in S^*}{p_i < \frac{1}{2}}}\leq 1.
\]
\end{corollary}
\noindent The result of this corollary is instrumental for developing an FPTAS that is the subject of the next section.

\subsection{A Fully Polynomial Time Approximation Scheme}

In order to approximately solve DP~\eqref{DPSOL} and with a polynomial run-time complexity bound we consider scaling down (and rounding) the profit coefficients whose magnitude determines the running time of~\eqref{DPSOL}. In particular consider scaling the profit coefficients using some factor $\kappa > 0$.  Accordingly, for each $i\in[n]$, $\hat c_i = \lfloor\frac{c_i}{\kappa}\rfloor$ is the scaled profit coefficient. In the following let $N_{1/2}=\set{i\in[n]}{p_i\geq \frac{1}{2}}$.  Further, for convenience assume that $[n]\setminus N_{1/2}=[h]$ for some $h\in [n]\cup \{0\}$ ($h=0$ when $[n]\setminus N_{1/2}=\emptyset$). Accordingly, $N_{1/2}=\{h+1,\ldots,n\}$. For $i\in [n]$ let $\hat P(i,C)$ denote the DP equations~\eqref{DPEQNS} with the $\hat c_i$ values in place of the $c_i$'s. Also let $\hat c_{n+1}=0$ and $p_{n+1}=1$.
Then, for $i\in [n]$ and $j>i$ the scaled DP problem is defined as
\begin{equation}
\label{SCALEDDPSOL}
\hat z(i,j)=\max_C\set{(C+\hat c_j)\cdot \hat P(i,C)\cdot p_j}{C = \min_{k\in[i]}\{\hat c_k\},\min_{k\in[i]}\{\hat c_k\}+1, \ldots, \bar C(i)},
\end{equation}
where $\bar C(i) = \sum_{k=1}^i \hat c_k$.

Note that $\hat z(i,j)$ is an optimal objective value of~\eqref{FORM3} with $c$ replaced by $\hat c$ and the additional constraints (fixing the decision variable values) for $k\in \{i+1,\ldots,n\}$
\[
x_k =
\begin{cases}
 0 & k\in \{i+1,\ldots,n\}\setminus \{j\}\\
 1 & k = j.
\end{cases}.
\]
Let $\hat C\equiv \hat z(n,n+1)=max_C\set{C\cdot\hat P(n,c)}{C=1,\ldots,\bar C(n)}$ and let $\hat S$ be the corresponding support of $x$ that maximizes~\eqref{FORM3} with $c$ replaced by $\hat c$ (for which $\sum_{i\in\hat S}\hat c_i=\hat C$).
Following Corollary~\ref{ONEHALFCOR}, it can observed that it suffices to evaluate $\hat z(i,j)$ with $h=i < j = h+1,\ldots,n+1$ to determine $\hat z(n,n+1)$ and $\hat C \in\argmax_C\set{C\cdot\hat P(n,c)}{C=1,\ldots,\bar C(n)}$.

The following lemma establishes an upper bound on $\kappa$ that is sufficient to bound the relative error to within a given $\epsilon>0$.
\begin{lemma}\label{FPTASLEM}
For a given $\epsilon > 0$, and all $\kappa \leq \frac{\epsilon \max_{i\in S^*}p_ic_i}{n}$,
\begin{equation}
\label{APPROXINEQ}
  \kappa\cdot \hat z(n,n+1)
  \geq (1-\epsilon) \cdot C^*\cdot P(n,C^*),
\end{equation} where $C^*$ is a maximizer of~\eqref{DPSOL}.
\end{lemma}
\begin{proof}
First note that
\begin{equation*}
 \sum_{i\in S^*}c_i-\kappa\sum_{i\in S^*}\hat c_i\leq n\kappa.
\end{equation*}
Then, it follows that
\begin{align*}

  \kappa\cdot \hat C \cdot \hat P(n,\hat C) =\kappa\sum_{i\in \hat S}\hat c_i\prod_{j\in \hat S}p_j
& \geq \left(1-\frac{n\kappa}{\sum_{i\in  S^*}c_i}\right)\sum_{i\in S^*}c_i\prod_{j\in  S^*}p_j
\end{align*} where the last inequality also followed from the optimality of $\hat S$ with the scaled profit $\hat c_i$ values. Then, given an $\epsilon>0$,~\eqref{APPROXINEQ} implies that $\kappa$ must satisfy
\begin{equation*}
\frac{n\kappa}{\sum_{i\in S^*}c_i}\leq \epsilon\Leftrightarrow \kappa\leq \frac{\epsilon\sum_{i\in S^*}c_i}{n},
\end{equation*}
and so it suffices to choose
\[
\kappa\leq \frac{\epsilon \max_{i\in[n]}\{p_ic_i\}}{n}\leq \frac{\epsilon\sum_{i\in S^*}c_i\prod_{j\in  S^*}p_j}{n} \leq \frac{\epsilon\sum_{i\in  S^*}c_i}{n}.
\]
\end{proof}

 Algorithm~\ref{FPTAS} is now considered as an approximation scheme for~\eqref{DPSOL} and (the equivalent)~\eqref{FORM3}.

\begin{algorithm}
\caption{\label{FPTAS}}
\begin{algorithmic}[1]
	\REQUIRE{$\epsilon,c,p$}

	\STATE $\kappa\leftarrow \frac{\epsilon \max_{i\in N_{1/2}}\{p_ic_i\}}{n}$

	\FOR{$j=h+1,\ldots,n+1$}\label{BEGINLOOP}
\STATE $z\leftarrow \max\{\kappa\cdot \hat z(h,j), c_jp_j \} $\label{SINGLEITEMSTEP}
\IF{$z_{\text{max}} < z$}
\STATE $z_{\text{max}} \leftarrow z$
\ENDIF
\ENDFOR\label{ENDLOOP}
\ENSURE{$z_{\text{max}}$}
\end{algorithmic}
\end{algorithm}

\noindent The following proposition establishes that Algorithm~\ref{FPTAS} is an FPTAS for~\eqref{FORM3}.
\begin{proposition}
Algorithm~\ref{FPTAS} is an FPTAS for~\eqref{FORM3}.
\end{proposition}
\begin{proof}
The following cases need to be considered.
\paragraph{Case $\card{S^*}=1$:} It is straightforward that Algorithm~\ref{FPTAS} outputs an optimal solution determined in step~\ref{SINGLEITEMSTEP}.
\paragraph{Case $\card{ S^*}\geq 2$:} It follows from Corollary~\ref{ONEHALFCOR} that if $\card{ S^*}\geq 2$ then $\card{S^*\setminus N_{1/2}}\leq 1$. Then, consider the following collectively exhaustive subcases:
\subparagraph{Case $S^*\setminus N_{1/2}=\emptyset$:}
For each given $\epsilon>0$, $\kappa$ satisfies the supposition of Lemma~\ref{FPTASLEM}. So, following Lemma~\ref{FPTASLEM} with $\bar C=\bar C(h)=\sum_{i\in N_{1/2}}c_i\geq \sum_{i\in S^*} c_i$,
 \[
 \kappa\cdot \hat z(h,n+1)=\kappa\cdot \hat C\cdot \hat P(h,\bar C)\geq (1-\epsilon) \cdot C^*\cdot P(h,C^*)=P(n,C^*).
 \]

\subparagraph{Case $\card{S^*\setminus N_{1/2}}=1$: } Then
for each $\epsilon > 0$, the choice of $\kappa$ by Lemma~\ref{FPTASLEM} satisfies for some $j\in [n]\setminus N_{1/2}=\{h+1,\ldots,n\}$
\[
\kappa \cdot \hat z(h,j)=\hat z(n,n+1)\geq (1-\epsilon) \cdot C^*\cdot P(n,C^*),
\] and the algorithm must determine $j$ since it enumerates all elements of $[n]\setminus N_{1/2}$ in the main loop (in lines~\ref{BEGINLOOP}-\ref{ENDLOOP}).

The complexity of the algorithm is determined by at most $\card{[n]\setminus N_{1/2}}\leq n$ invocations of~\eqref{SCALEDDPSOL}. Hence, it is \[
O(n^2\bar C)\subseteq O\left(n^2\sum_{i\in N_{\frac{1}{2}}} c_i/\kappa \right)\subseteq O\left(\frac{n^4}{\epsilon}\right).\qedhere
\]
\end{proof}

\section{Conclusion}

We have established the NP-hardness of all-or-nothing maximum expected value subset. It also implies the hardness of constrained all-or-nothing subset problems in different graph settings. In particular one may consider an all-or-nothing maximum expected value matching, a similar problem, with activities and feasible subsets corresponding to edges and matchings in a graph, respectively. In ongoing work we develop an approximation scheme for this problem.

\section*{Acknowledgement}

Noam Goldberg thanks Naoki Katoh for discussing~\cite{Katoh92} and referring him to~\cite{Matsui96} and~\cite{Hammer02}, John Dickerson for a discussion of kidney exchange and referring to~\cite{Dickerson13}, and also  Martin Milani\v c for comments.

redpajama_set_name: RedPajamaArXiv


text:
\section{Environment Descriptions}
\textbf{PointTrajectory}:
\begin{itemize}
    \item Dynamics: This environment requires controlling a pointmass on a 2D plane, where the state $s_t = (x_t,y_t)$ represents the location of the pointmass. It always starts at the origin, with $s_0 = (0,0)$, and the agent is restricted to the box $[-1, 1]^2$ via clipping. The agent can take actions $(dx, dy) \in [-0.1, 0.1]^2$, which affect the state via $s_{t+1} = (x_t + dx, y_t + dy)$.
    \item Rewards: The agent is rewarded for following a sinusoidal trajectory parameterized by a three-dimensional vector $z = (\theta, d, a)$. $\theta$ controls the orientation of the sinusoidal trajectory, $d$ controls its wavelength, and $a$ controls its amplitude. Specifically, the reward function is:
    \begin{align*}
        r(s, a | z) = \begin{cases}
        \frac{\tilde x}{d} \phi(\frac {\tilde y - a \times sin(\pi \tilde x / d)}{0.05}) & \text{if } \tilde{x } \geq 0 \\
        0 & \text{if } \tilde{x } < 0
        \end{cases}
    \end{align*}
    where $\tilde x$ is the projection of the current state $(x,y)$ onto the line $y = \tan (\theta) x$, $\tilde y$ is the orthogonal component, and $\phi$ is the probability density function of the unit Gaussian. The $x/d$ term encourages movement towards the goal, and the $\phi(\cdot)$ term sharply penalizes an agent for deviating from the target trajectory.

    The task distribution $\mathcal T$ is as follows: each element of $z$ is drawn independently from a separate distribution, where $\theta \sim \text{Unif}[-\pi, \pi]$, $d \sim \text{Unif}[0.75, 1]$, and $a \sim \text{Unif}[-0.25, 0.25]$.
\end{itemize}

\textbf{PointReacher}
\begin{itemize}
    \item Dynamics: PointReacher shares the same dynamics as PointTrajectory.
    \item Rewards: This environment requires managing three quantities of interest: distance to a goal, distance from an obstacle, and energy used. We control these via a 6-dimensional task vector $z= (x_g,y_g,x_{obst},y_{obst},u,v)$, where the goal is located at $(x_g, y_g)$, the obstacle is located at $(x_{obst}, y_{obst})$, and $u$ and $v$ control the relative weighting of the three terms. Specifically, $u$ and $v$ represent a location on a unit sphere, and we calculate the weights $w_1$, $w_2$, and $w_3$ as the Euclidean coordinates of that point. The distance reward $r_{goal, t}$, safety reward $r_{obst, t}$, and energy penalty $E_t$ are calculated as following:

    \begin{align*}
        r_{goal, t} &= 2 \exp \left\{\frac{-((x_t - x_g)^2 + (y_t - y_g)^2)}{0.08^2} \right\} \\
        r_{obst, t} &= \log_{10}\left(0.01 + (x_t - x_{obst})^2 + (y_t - y_{obst})^2\right) \\
        E_t &= - ||a_t||_2
    \end{align*}
    We found that using these formulations encouraged specificity for the goal (i.e. optimal behavior is to move to the goal, not just a relatively close location), and a heavy penalty for coming too close to the obstacle.

    Overall, the reward is then:
\begin{align*}
    r(s_t, a_t| z) = w_1 r_{goal,t} + w_2 E_t + w_3 r_{obst,t}
\end{align*}
    Note that the obstacle is not physically present in the environment, so the dynamics of the environment are the same across all possible tasks. The obstacle is solely a part of the reward function, and the agent is discouraged from coming nearby via the penalty in the reward function. In general, this represents the idea that we can ``practice'' for certain safety-critical applications without needing to actually interact with the dangerous obstacle at hand.

    The task distribution $\mathcal T$ is as follows: $u,v$ are sampled uniformly from the portion of the sphere in the first octant, and $(x_g, y_g)$ and $(x_{obst}, y_{obst})$ are sampled uniformly from the disk of radius 0.3 centered at the start state $s_0 = (0,0)$.
\end{itemize}

\textbf{Fetch}
\begin{itemize}
    \item Dynamics: We use the Fetch Robot from OpenAI Gym \cite{brockman2016openai, plappert2018multi}. Fetch has 3-dimensional observations, corresponding to the coordinates of its end-effector. It is operated through noisy position control, so the action space is also 3-dimensional. We increase the number of solver iterations from 20 to 100, to make the controller more accurate and reduce control noise.

    \item Rewards: We use the same parameterized reward function as we do in PointReacher, adapted so that the goal and obstacle lie in 3D space.
\end{itemize}

\textbf{HalfCheetahMultiObjective}
\begin{itemize}
    \item Dynamics: We use the HalfCheetah-v1 environment from OpenAI Gym \cite{brockman2016openai}, corresponding to a two-legged robot constrained to run in the $xz$ plane. It has a 17-dimensional observation space, and a 6-dimensional action space of torque inputs for each joint.
    \item Rewards: Our task variable $z \in \mathcal Z \subseteq \mathbb{R}^4$ controls a weighted combination of velocity in the x-direction ($v_t$), energy use ($E_t$), height of the center of mass ($h_t$), and rotation speed ($\omega_t)$.
    \begin{align*}
        r(s_t, a_t| z) = z_1 v_t + z_2 E_t + z_3 h_t + z_4 \omega_t
    \end{align*}
    where $v_t = x_{t+1} - x_{t}$, $\omega_t = \theta_{t+1} - \theta_{t}$, and $E_t = -0.1 \times ||a_t||_2^2$. Since only the ratio between individual elements of $z$ are relevant for eliciting different behavior, we constrain the set of allowed task variables $\mathcal Z = \{z \in \mathbb R ^4 : ||z||_2  = 1, z_1 \geq 0, z_2 \geq 0\}$. We enforce non-negativity of $z_1$ and $z_2$ because it is rather unimpressive behavior to maximize energy use without purpose or minimize the height of the robot's center of mass. To sample from the task distribution $\mathcal T$, we sample uniformly from $\mathcal Z$.
\end{itemize}

\textbf{AntDirection}
\begin{itemize}
    \item Dynamics: We use the Ant-v2 environment from OpenAI Gym \cite{brockman2016openai}, corresponding to a four-legged robot that can move in the $x$, $y$, and $z$ directions. The state space is 111-dimensional, and the joints are controlled via torque control, for an 8-dimensional action space.
    \item Rewards: We use a 1-dimensional task variable to control which direction the Ant robot should move in. Our reward function is:
    \begin{align*}
        r(s, a |z) = ||\text{velocity}||_2 \times \mathbbm{1}\{\text{velocity angle within 15 degrees of z}\}
    \end{align*}
    This reward function encourages moving quickly in the direction chosen by the task variable $z$. An alternative reward function that returns the length of the velocity component in the direction of $z$ allows a policy to gain high rewards while going even at a $45^\circ$ angle from the target direction, so we add the indicator function to restrict the space of high-reward behavior. The task distribution $\mathcal T$ is uniform over $\mathcal Z = [- \pi, \pi]$.
\end{itemize}

\section{Training Details}
\subsection{Training Tricks}

Since our task space $\mathcal Z$ is continuous, we cannot use multi-headed networks, which are commonly used when dealing with a discrete set of tasks \cite{yu2019meta}. We thus follow the ubiquitous approach of concatenating $(s || z)$ and feeding that into the policy network $\pi$, and concatenating $(s || a || z)$ and feeding that into the q-network. However, when the observation space is large, such as in Ant (111-dimensional) or HalfCheetah (17-dimensional), it becomes difficult for the network to identify the few dimensions of its input that correspond to $z$ and should thus strongly determine the desired behavior (for $\pi$) or the correct q-value.

We deal with this by (a) repeating the task variable $z$ a few times, and (b) appending the repeated latent at every hidden layer. (a) increases the salience of $z$, which should improve the ability of the network to do credit assignment and identify $z$ as the causal variable responsible for the difference between tasks. (b) allows the policy and q networks to more easily have differentiated behavior, depending on the current task $z$. Empirically, we find that these two tricks are crucial for getting the baselines (No relabeling, Intentional-Unintentional Agent) to work at all; our Generalized Hindsight methods benefit to a smaller degree. For HalfCheetahMultiObjective and AntDirection, we repeat the task variable 5 times.

\subsection{Hyperparameters}
We list shared hyperparameters in \autoref{tab:hyperparams}, and environment-specific hyperparameters in \autoref{tab:envhyperparams}.
\begin{table*}[!htbp]
  \begin{center}
    \begin{tabular}{l|l}\toprule
      Parameter & Value\\
      \hline
      Algorithm & Soft Actor Critic \cite{haarnoja2018soft} \\
      Optimizer & Adam \cite{kingma2014adam} \\
      Batch size & 256 \\
      Target smoothing coefficient ($\tau$) & 0.005\\
      Reward scale & Auto-tuned \cite{haarnoja2018softapplications} \\

    \end{tabular}
  \end{center}
\caption{Hyperparameters used for the experiments shown in \autoref{fig:learningcurves}.}
\label{tab:hyperparams}
\end{table*}

\begin{table*}[!htbp]
  \begin{center}
    \begin{tabular}{l|ccccc}\toprule
      Environment & Hidden Layers & Learning Rate & Gradient Steps per Epoch & Horizon  & Discount ($\gamma$)\\
      \hline
      PointTrajectory &     [400, 300] & $3 \times 10^{-3}$ & 100 & 15 & 0.9\\
      PointReacher &        [400, 300] & $3 \times 10^{-3}$ & 200 & 20 & 0.97\\
      Fetch &               [400, 300] & $3 \times 10^{-3}$ & 200 & 50 & 0.98\\
      HalfCheetahMultiObj & [256, 256] & $3 \times 10^{-4}$ & 1000 & 1000 & 0.99\\
      AntDirection &        [256, 256] & $3 \times 10^{-4}$ & 1000 & 1000 & 0.99

    \end{tabular}
  \end{center}
\caption{Environment-specific hyperparameters used for the experiments shown in \autoref{fig:learningcurves}.}
\label{tab:envhyperparams}
\end{table*}

\section{Videos}
A video of our environments and results can be found here: \href{https://sites.google.com/view/generalized-hindsight}{sites.google.com/view/generalized-hindsight}.

\end{appendices}

\section{Background}
Before discussing our method, we briefly introduce some background and formalism for the RL algorithms used. A more comprehensive introduction to RL can be found in \citet{kaelbling1996reinforcement} and \citet{sutton1998reinforcement}.

\subsection{Reinforcement Learning}
In this paper we deal with continuous space Markov Decision Processes $\mathcal{M}$ that can be represented as the tuple $\mathcal{M}\equiv(\mathcal{S},\mathcal{A},\mathcal{P},r,\gamma, \mathbb{S})$, where $\mathcal{S}$ is a set of continuous states and $\mathcal{A}$ is a set of continuous actions, $\mathcal{P}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$ is the transition probability function, $r: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ is the reward function, $\gamma$ is the discount factor, and $\mathbb{S}$ is the initial state distribution.

An episode for the agent begins with sampling $s_0$ from the initial state distribution $\mathbb{S}$.
At every timestep $t$, the agent takes an action $a_t=\pi(s_t)$ according to a policy $\pi:\mathcal{S} \rightarrow \mathcal{A}$.
At every timestep $t$, the agent gets a reward $r_t=r(s_t,a_t)$, and the state transitions to $s_{t+1}$, which is sampled according to probabilities $\mathcal{P}(s_{t+1} | s_t,a_t)$.
The goal of the agent is to maximize the expected return $\expect_{\mathbb{S}}[R_0|\mathbb{S}]$, where the return is the discounted sum of the future rewards $R_t=\sum^{\infty}_{i=t}\gamma^{i-t}r_i$. The $Q$-function is defined as $Q^{\pi}(s_t,a_t)=E[R_t|s_t,a_t]$. In the partial observability case, the agent takes actions based on the partial observation, $a_t=\pi(o_t)$, where $o_t$ is the observation corresponding to the full state $s_t$.

\subsection{Off Policy RL using Soft Actor Critic}

Generalized Hindsight requires an off-policy RL algorithm to perform relabeling. One popular off-policy algorithm for learning deterministic continuous action policies is Deep Deterministic Policy Gradients (DDPG)~\cite{lillicrap2015continuous}. The algorithm maintains two neural networks: the policy (also called the actor) $\pi_\theta:\mathcal{S} \rightarrow \mathcal{A}$ (with neural network parameters $\theta$) and a $Q$-function approximator (also called the critic) $Q_\phi^{\pi}:\mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ (with neural network parameters $\phi$).

During training, episodes are generated using a noisy version of the policy (called behaviour policy),
e.g. $\pi_b(s) = \pi(s) + \mathcal{N}(0,1)$, where $\mathcal{N}$ is the Normal distribution noise.
The transition tuples $(s_t,a_t,r_t,s_{t+1})$ encountered during training are stored in a replay buffer~\cite{mnih2015human}. Training examples sampled from the replay buffer are used to optimize the critic. By minimizing the Bellman error loss $\mathcal{L}_c=(Q(s_t,a_t)-y_t)^2$, where $y_t=r_t + \gamma Q(s_{t+1},\pi(s_{t+1}))$, the critic is optimized to approximate the $Q$-function. The actor is optimized by minimizing the loss $\mathcal{L}_a=-\expect_s[Q(s,\pi(s))]$. The gradient of $\mathcal{L}_a$ with respect to the actor parameters is called the deterministic policy gradient ~\cite{silver2014deterministic} and can be computed by backpropagating through the combined critic and actor networks.
To stabilize the training, the targets for the actor and the critic $y_t$ are computed on separate versions of the actor and critic networks,
which change at a slower rate than the main networks. A common practice is to use a Polyak averaged~\cite{polyak1992acceleration} version of the main network. Soft Actor Critic (SAC) \cite{haarnoja2018soft} builds on DDPG by adding an entropy maximization term in the reward. Since this encourages exploration and empirically performs better than most actor-critic algorithms, we use SAC for our experiments, although Generalized Hindsight is compatible with any off-policy RL algorithm.

\subsection{Multi-Task RL}
The goal in multi-task RL is to not just solve a single MDP $\mathcal{M}$, but to solve to solve a distribution of MDPs $\mathcal{M}(z)$, where $z$ is the task-specification drawn from the task distribution $z\sim\mathcal{T}$. Although $z$ can  parameterize different aspects of the MDP, we are specially interested in the different reward functions. Hence, our distribution of MDPs is now $\mathcal{M}(z)\equiv(\mathcal{S},\mathcal{A},\mathcal{P},r(\cdot|z),\gamma, \mathbb{S})$. Thus, a different $z$ implies a different reward function under the same dynamics $\mathcal{P}$ and start state $z$. One may view this representation as a generalization of the goal-conditioned RL setting~\cite{schaul2015universal}, where the reward family is restricted to $r(s,a|z=g)=-d(s,z=g)$. Here $d$ represents the distance between the current state $s$ and the desired goal $g$. In sparse goal-conditioned RL, where hindsight has previously been applied~\cite{andrychowicz2017hindsight}, the reward family is further restricted to $r(s,a|z=g)=[d(s,z=g)<\epsilon]$. Here the agent gets a positive reward only when $s$ is within $\epsilon$ of the desired goal $g$.

\subsection{Hindsight Experience Replay (HER)}

HER~\cite{andrychowicz2017hindsight} is a simple method of manipulating the replay buffer used in off-policy RL algorithms that allows it to learn state-reaching policies more efficiently with sparse rewards. After experiencing some episode $s_0,s_1,...,s_T$, every transition $s_t\rightarrow s_{t+1}$ along with the goal for this episode is usually stored in the replay buffer. However with HER, the experienced transitions are also stored in the replay buffer with different goals. These additional goals are states that were achieved later in the episode. Since the goal being pursued does not influence the environment dynamics, one can replay each trajectory using arbitrary goals, assuming we use an off-policy RL algorithm to optimize~\cite{precup2001off}.

\subsection{Inverse Reinforcement Learning (IRL)}
In IRL~\cite{ng2000algorithms}, given an expert policy $\pi_E$ or more practically, access to demonstrations $\tau_E$ from $\pi_E$, we want to recover the underlying reward function $r^*$ that best explains the expert behaviour. Although there are several methods that tackle this problem~\cite{ratliff2006maximum,abbeel2004apprenticeship,ziebart2008maximum}, the basic principle is to find $r^*$ such that:
\begin{equation}
    \mathbb{E}[\sum_{t=0}^{T-1} \gamma r^*(s_t)|\pi_E] \geq \mathbb{E}[\sum_{t=0}^{T-1} \gamma r^*(s_t)|\pi] \;\; \forall \pi
\end{equation}
We use the framework of IRL to guide our \textit{Approximate IRL} relabeling strategy for Generalized Hindsight.

\section{Generalized Hindsight}
\subsection{Overview}
Given a multi-task RL setup, i.e. a distribution of reward functions $r(.|z)$, our goal is to maximize the expected reward across the task distribution $z\sim\mathcal{T}$ through optimizing our policy $\pi$:
\begin{equation}
    \expect_{z\sim\mathcal{T}}[R(\pi|z)]
\end{equation}
Here, $R(\pi|z)=\sum^{T-1}_{t=0}\gamma^{t}r(s_t,a_t\sim\pi(s_t|z)|z)$ represents the cumulative discounted reward under the reward parameterization $z$ and the conditional policy $\pi(.|z)$. One approach to solving this problem would be the straightforward application of RL to train the $z-$ conditional policy using the rewards from $r(.|z)$. However, this fails to re-use the data collected under one task parameter $z$ $(s_t,a_t)\sim\pi(.|z)$ to a different parameter $z'$. In order to better use and share this data, we propose to use hindsight relabeling, which is detailed in Algorithm \ref{alg:hindsight}.

The core idea of hindsight relabeling is to convert the data generated from the policy under one task $z$ to a different task. Given the relabeled task $z'=\texttt{relabel}(\tau(\pi(.|z)))$, where $\tau$ represents the trajectory induced by the policy $\pi(.|z)$, the state transition tuple $(s_t,a_t,r_t(.|z),s_{t+1})$ is converted to the relabeled tuple $(s_t,a_t,r_t(.|z'),s_{t+1})$. This relabeled tuple is then added to the replay buffer of an off-policy RL algorithm and trained as if the data generated from $z$ was generated from $z'$. If relabeling is done efficiently, it will allow for data that is sub-optimal under one reward specification $z$, to be used for the better relabeled specification $z'$. In the context of sparse goal-conditioned RL, where $z$ corresponds to a goal $g$ that needs to be achieved, HER~\cite{andrychowicz2017hindsight} relabels the goal to states seen in the trajectory, i.e. $g'\sim\tau(\pi(.|z=g))$. This labeling strategy, however, only works in sparse goal conditioned tasks. In the following section, we describe two relabeling strategies that allow for a generalized application of hindsight.

\begin{algorithm}
   \caption{$\texttt{Generalized Hindsight}$}
   \label{alg:hindsight}
\begin{algorithmic}[1]
    \STATE {\bfseries Input:} Off-policy RL algorithm $\mathbb{A}$, strategy $\mathbb{S}$ for choosing suitable task variables to relabel with, reward function $r: \mathcal{S} \times \mathcal{A} \times \mathcal{Z} \rightarrow \mathbb{R}$
    \FOR{episode $=1$ to $M$}
        \STATE Sample a task variable $z$ and an initial state $s_0$
        \STATE Roll out policy on $z$ for $T$ steps, yielding trajectory $\tau$
        \STATE Find set of new tasks to relabel with: $Z := \mathbb{S}(\tau)$
        \STATE Store original transitions in replay buffer:
        \Statex $\quad$ $(s_t, a_t, r(s_t, a_t, z), s_{t+1}, z)$
        \FOR{$z' \in Z$}
                \STATE Store relabeled transitions in replay buffer:
                \Statex $\quad \quad$ $(s_t, a_t, r(s_t, a_t, z'), s_{t+1}, z')$
        \ENDFOR
        \STATE Perform $n$ steps of policy optimization with $\mathbb{A}$
    \ENDFOR
\end{algorithmic}
\end{algorithm}

\subsection{Approximate IRL Relabeling (AIR)}

\begin{algorithm}
   \caption{$\texttt{$\mathbb{S}_{IRL}$: Approximate IRL}$}
   \label{alg:approxirl}
\begin{algorithmic}[1]
    \STATE {\bfseries Input:} Trajectory $\tau = (s_0, a_0, ..., s_T)$, cached trajectories $\mathcal{D} = \{(s_0, a_0, ..., s_T)\}_{i=1}^N$, reward function $r: \mathcal{S} \times \mathcal{A} \times \mathcal{Z} \rightarrow \mathbb{R}$, number of candidate task variables to try: $K$, number of task variables to return: $m$
    \STATE Sample set of candidate tasks $Z = \{v_j\}_{j=1}^K$, where $v_j \sim \mathcal{T}$
    \Statex \textbf{Approximate IRL Strategy:}
    \FOR{$v_j \in Z$}
        \STATE \textbf{Calculate trajectory reward} for $\tau$ and the trajectories in $\mathcal{D}$: $R(\tau|v_j) := \sum_{t=0}^T \gamma^t r(s_t, a_t, v_j)$
        \STATE \textbf{Calculate percentile estimate:}
        \Statex $\quad \quad  \hat{P}(\tau, v_j) = \frac{1}{n} \sum_{i=1}^N \mathbbm{1}\{R(\tau|v_j) \geq R(\tau_i|v_j)\}$
    \ENDFOR
    \STATE \textbf{return} $m$ tasks $v_j$ with highest percentiles $\hat{P}(\tau, v_j)$
\end{algorithmic}
\end{algorithm}

The goal of computing the optimal reward parameter, given a trajectory is closely tied to the Inverse Reinforcement Learning (IRL) setting. In IRL, given demonstrations from an expert, we can retrieve the reward function the expert was optimized for. At the heart of these IRL algorithms, a reward specification parameter $z'$ is optimized such that
\begin{equation}
\label{eq:irl_orig}
    R(\tau_E|z')\geq R(\tau'|z') \; \forall \, \tau'
\end{equation}
where $\tau_E$ is an expert trajectory. Inspired by the IRL framework, we propose the \textit{Approximate IRL} relabeling seen in \Algref{alg:approxirl}. We can use a buffer of past trajectories to find the task $z'$ on which our current trajectory does better than the older ones. Intuitively this can be seen as an approximation of the right hand side of ~\Eqref{eq:irl_orig}. Concretely, we want to relabel a new trajectory $\tau$, and have $N$ previously sampled trajectories along with $K$ randomly sampled candidate tasks $v_k$. Then, the relabeled task for trajectory $\tau$ is computed as:
\begin{equation}
    z' = \argmax_{k} \frac{1}{N} \sum_{j=1}^N \mathbbm{1}\{R(\tau|v_k) \geq R(\tau_j|v_k)\}
\end{equation}
The relabeled $z'$ for $\tau$ maximizes its percentile among the $N$ most recent trajectories collected with our policy. One can also see this as an approximation of max-margin IRL~\cite{ratliff2006maximum}.
One potential challenge with large $K$ is that many $v_k$ will have the same percentile. To choose between these potential task relabelings, we add tiebreaking based on the advantage estimate
\begin{equation}
    \hat{A}(\tau, z) = R(\tau|z) - V^\pi(s_0, z)
\end{equation}
Among candidate tasks $v_k$ with the same percentile, we take the tasks that have higher advantage estimate. From here on, we will refer to Generalized Hindsight with Approximate IRL Relabeling as AIR.

\subsection{Advantage Relabeling}

\begin{figure*}[t!]
\centering
\subfigure[PointTrajectory]{\label{fig:pointmass_env}\includegraphics[width=0.19\linewidth]{figures/pointmass_env.pdf}}
\subfigure[PointReacher]{\label{fig:pointgoal_env}\includegraphics[width=0.19\linewidth]{figures/pointgoalobst_env.pdf}}
\subfigure[Fetch]{\includegraphics[width=0.19\linewidth]{figures/fetchreach.png}}
\subfigure[HalfCheetahMultiObj]{\includegraphics[width=0.19\linewidth]{figures/hc.png}}
\subfigure[AntDirection]{\includegraphics[width=0.19\linewidth]{figures/ant.png}}
\caption{Environments we report comparisons on. PointTrajectory requires a 2D pointmass to follow a target trajectory; PointReacher requires moving the pointmass to a goal location, while avoiding an obstacle and modulating its energy usage. In (b), the red circle indicates the goal location, while the blue triangle indicates an imagined obstacle to avoid. Fetch has the same reward formulation as PointReacher, but requires controlling the noisy Fetch robot in 3 dimensions. HalfCheetah requires learning running in both directions, flipping, jumping, and moving efficiently. AntDirection requires moving in a target direction as fast as possible.}
\label{fig:learningcurves}
\end{figure*}

One potential problem with AIR is that it requires $O(NT)$ time to compute the relabeled task variable for each new trajectory, where $N$ is the number of past trajectories compared to, and $T$ is the horizon. A relaxed version of AIR could significantly reduce computation time, while maintaining relatively high-accuracy relabeling. One way to do this is to use the \textit{Maximum-Reward} relabeling objective. Instead of choosing from our $K$ candidate tasks $v_k\sim\mathcal{T}$ by selecting for high percentile (\autoref{eq:irl_orig}), we could relabel based on the cumulative trajectory reward:
\begin{equation}
    z'=\argmax_{v_k} \{R(\tau|v_k)\}
\end{equation}
However, one challenge with simply taking the \textit{Maximum-Reward} relabel is that different reward parameterizations may have different scales which will bias the relabels to a specific $z$. Say for instance there exists a task in the reward family $v_j$ such that $r(.|v_j) = 1 + \max_{i\neq j} r(.|v_i)$. Then, $v_j$ will always be the relabeled reward parameter irrespective of the trajectory $\tau$. Hence, we should not only care about the $v_k$ that maximizes reward, but select $v_k$ such that $\tau$'s likelihood under the trajectory distribution drawn from the optimal $\pi^*(.|v_k)$ is high. To do this, we can simply select $z'$ based on the advantage term that we used to tiebreak for AIR.
\begin{equation}

    z'_i = \argmax_{k} R(\tau|v_k) - V^\pi(s_0, v_k)
\end{equation}
We call this \textit{Advantage} relabeling (Algorithm \ref{alg:advantage}), a more efficient, albeit less accurate, version of AIR. Empirically, \textit{Advantage} relabeling often performs as well as AIR, but requires the value function $V^\pi$ to be more accurate than it has to be in AIR. We reuse the twin $Q$-networks from SAC as our value function.
\begin{equation}
    V^\pi(s, z) = \min(Q_1(s, \pi(s|z), z), Q_2(s, \pi(s|z), z))
\end{equation}

\begin{algorithm}
   \caption{$\texttt{$\mathbb{S}_A$: Trajectory Advantage}$}
   \label{alg:advantage}
\begin{algorithmic}[1]
    \STATE Repeat steps 1 \& 2 from Algorithm \ref{alg:approxirl}
    \Statex \textbf{Advantage Relabeling Strategy:}
    \FOR{$v_j \in Z$}
        \STATE \textbf{Calculate trajectory reward:}
        \Statex $\quad \quad R(\tau|v_j) := \sum_{t=0}^T \gamma^t r(s_t, a_t, v_j)$
        \STATE \textbf{Calculate advantage estimate of the trajectory}:
        \Statex $\quad \quad \hat{A}(\tau, v_j) = R(\tau|v_j) - V^\pi(s_0, v_j)$
    \ENDFOR
    \STATE \textbf{return} $m$ tasks $z_j$ with highest advantages $\hat{A}(\tau, z_j)$
\end{algorithmic}
\end{algorithm}

\section{Conclusion}

In this work, we have presented Generalized Hindsight, an approximate IRL based task relabelling algorithm for multi-task RL. We demonstrate how efficient relabeling strategies can significantly improve performance on simulated navigation and manipulation tasks. Through these first steps, we believe that this technique can be extended to other domains like real world robotics, where a balance between different specifications, such as energy use or safety, is important.

\textbf{Acknowledgements} We thank AWS for computing resources. We also gratefully
acknowledge the support from Berkeley DeepDrive, NSF, and the ONR Pecase award.

\section{Experimental Evaluation}

\label{section:experiments}

In this section, we describe our environment settings along with a discussion of our central hypothesis: Does relabeling improve performance?

\begin{figure*}[t!]
\centering
\includegraphics[width=\linewidth]{figures/learning_curves.pdf}
\caption{Learning curves comparing Generalized Hindsight algorithms to baseline methods.  For environments with a goal-reaching component, we also compare to HER. In (a), AIR learning curve obscures the Advantage learning curve. In (d) and (e), where we use $N$ = 500 for AIR, AIR takes much longer to run than the other methods. 10 seeds were used for all runs.}
\label{fig:learningcurves}
\end{figure*}

\subsection{Environment setting}
Multi-task RL with a generalized family of reward parameterizations does not have existing benchmark environments. However, since sparse goal-conditioned RL has benchmark environments~\cite{plappert2018multi}, we build on their robotic manipulation framework to make our environments. The key difference in the environment setting between ours and \citet{plappert2018multi} is that in addition to goal reaching, we have a dense reward parameterization for practical aspects of manipulation like energy consumption~\cite{meike2011energy} and safety~\cite{calinon2010learning}. These environments will be released for open-source access. The five environments we use are as follows:

\begin{enumerate}
  \item \textbf{PointTrajectory}: 2D pointmass with $(x,y)$ observations and $(dx, dy)$ position control for actions. The goal is to follow a target trajectory parameterized by $z \in \mathcal{Z} \subseteq \mathbb{R}^3$. Figure \autoref{fig:pointmass_env} depicts an example trajectory in green, overlaid on the reward heatmap defined by some specific task $z$.
  \item \textbf{PointReacher}: 2D pointmass with $(x,y)$ observations and $(dx, dy)$ position control for actions. This environment has high reward around the goal position $(x_g, y_g)$ and low reward around an obstacle location $(x_{obst}, y_{obst})$. The 6-dimensional task vector is $z = (x_g, y_g, x_{obst}, y_{obst}, u, v)$, where $u$ and $v$ control the weighting between the goal rewards, obstacle rewards, and action magnitude penalty.
  \item \textbf{Fetch}: Here we adapt the Fetch environment from OpenAI Gym~\cite{brockman2016openai}, with $(x,y,z)$ end-effector position as observations and noisy position control for actions. We use the same parameterized reward function as in PointReacher that includes energy and safety specifications.
  \item \textbf{HalfCheetahMultiObjective}: HalfCheetah-V2 from OpenAI Gym, with 17-dimensional observations and 6-dimensional actions for torque control. The task variable $z = (w_{vel}, w_{rot}, w_{height}, w_{energy}) \in \mathcal{Z} = S^3$ controls the weights on the forward velocity, rotation speed, height, and energy rewards.
  \item \textbf{AntDirection}: Ant-V2 from OpenAI gym, with 111-dimensional observations and 8-dimensional actions for torque control. The task variable $z \in [-180^\circ, +180^\circ]$ parameterizes the target direction. The reward function is $r(\cdot|z) = ||\text{velocity}||_2 \times \mathbbm{1}\{\text{velocity angle within 15 degrees of z}\}$.
\end{enumerate}

\subsection{Does Relabeling Help?}
To understand the effects of relabeling, we compare our technique with the following standard baseline methods:
\begin{itemize}
    \item No relabeling (None): as done in \cite{yu2019meta}, we train with standard SAC without any relabeling step.
    \item Intentional-Unintentional Agent (IU) \cite{cabi2017intentional}: when there is only a finite number of tasks, IU relabels a trajectory with every task variable. Since our space of tasks is continuous, we relabel with random $z' \sim \mathcal{T}$. This allows for information to be shared across tasks, albeit in a more diluted form.
    \item HER: for goal-conditioned tasks, we use HER to relabel the goal portion of the latent with the future relabeling strategy.
\end{itemize}
We compare the learning performance for AIR and Advantage Relabeling with these baselines on our suite of environments in \autoref{fig:learningcurves}. On all tasks, AIR and Advantage Relabeling outperform the baselines in both sample-efficiency and asymptotic performance. Both of our relabeling strategies outperform the Intentional-Unintentional Agent, implying that selectively relabeling trajectories with a few carefully chosen $z'$ is more effective than relabeling with many random tasks. Collectively, these results show that AIR can greatly improve learning performance, even on highly dense environments such as HalfCheetahMultiObjective, where learning signal is readily available.

\begin{figure}[!t]
\centering
\subfigure[Stationary]{\includegraphics[width=0.23\linewidth]{figures/stationary.png}}
\subfigure[Forward]{\includegraphics[width=0.23\linewidth]{figures/forward.png}}
\subfigure[Back]{\includegraphics[width=0.23\linewidth]{figures/back.png}}
\subfigure[Frontflip]{\includegraphics[width=0.23\linewidth]{figures/backflip.png}}
\subfigure[Left]{\includegraphics[width=0.23\linewidth]{figures/left.png}}
\subfigure[Right]{\includegraphics[width=0.23\linewidth]{figures/down.png}}
\subfigure[Top Right]{\includegraphics[width=0.23\linewidth]{figures/right.png}}
\subfigure[Top Left]{\includegraphics[width=0.23\linewidth]{figures/up.png}}
\caption{The agents efficiently learn a wide range of behaviors. On HalfCheetahMultiObjective, the robot can stay still to conserve energy, run quickly forwards and backwards, and do a frontflip. On AntDirection, the robot can run quickly in any given direction.}
\label{fig:behavior}
\end{figure}

\subsection{How does generalized relabeling compare to HER?}
HER is, by design, limited to goal-reaching environments. For environments such as HalfCheetahMultiObjective, HER cannot be applied to relabel the weights on velocity, rotation, height, and energy. However, we can compare AIR with HER on the partially goal-reaching environments PointReacher and Fetch. \autoref{fig:learningcurves} shows that AIR achieves higher asymptotic performance than HER on both these environments. \autoref{fig:relabelingexample} demonstrates on PointReacher how AIR can better choose the non-goal-conditioned parts of the task. Both HER and AIR understand to place the relabeled goal around the terminus of the trajectory. However, only AIR understands that the imagined obstacle should be placed above the goal, since this trajectory becomes an optimal example of how to reach the new goal while avoiding the obstacle. HER (as well as the Intentional-Unintentional Agent) offer no such specificity, either leaving the obstacle in place or randomly placing it.

\begin{figure}[!t]
\centering
\includegraphics[width=\linewidth]{figures/test_figure.pdf}
\caption{Red denotes areas of high reward, for following a target trajectory (top) or reaching a goal (bottom). Blue indicates areas of negative reward, where an obstacle may be placed. On both environments, relabeling finds tasks on which our trajectory has high reward signal.
On PointReacher, AIR does not place the obstacle arbitrarily far. It places the relabeled obstacle within the curve of the trajectory, since this is the only way that the curved path would be better than a straight-line path (that would come close to the relabeled obstacle). }
\label{fig:relabelingexample}
\end{figure}

\begin{figure*}[!t]
\centering
\subfigure[Approximate IRL]{\includegraphics[width=0.33\linewidth]{figures/irl.pdf}}
\subfigure[Advantage Relabeling]{\includegraphics[width=0.33\linewidth]{figures/advantage.pdf}}
\subfigure[Reward Relabeling]{\label{fig:relabeling}\includegraphics[width=0.33\linewidth]{figures/reward.pdf}}
\caption{Comparison of relabeling fidelity on optimal trajectories for approximate IRL, advantage relabeling, and reward relabeling. We train a multi-task policy to convergence on the PointReacher environment. We roll out our policy on 1000 randomly sampled tasks $z$, and apply each relabeling method to select from $K=100$ randomly sampled tasks $v$. For approximate IRL, we compare against $N=10$ prior trajectories. The x-axis shows the weight on energy for the task $z$ used for the rollout, while the y-axis shows the weight on energy for the relabeled task $z'$. Note that goal location, obstacle location, and weights on their rewards/penalties are varying as well, but are not shown. Closer to to the line $y=x$ indicates higher fidelity, since it implies $z' \approx z^*$.}
\label{fig:relabelingcomparison}
\end{figure*}

\subsection{Analysis of Relabeling Fidelity}
Approximate IRL, advantage relabeling, and reward relabeling are all approximate methods for finding the optimal task $z^*$ that a trajectory is (close to) optimal for. As a result, an important characteristic is their \textit{fidelity}, i.e. how close the $z'$ they choose is to the true $z^*$. In \autoref{fig:relabelingcomparison}, we compare the fidelities of these three algorithms. Approximate IRL comes fairly close to reproducing the true $z^*$, albeit a bit noisily because it relies on the comparison to $N$ past trajectories. Advantage relabeling is slightly more precise, but fails for large energy weights, likely because the value function is not precise enough to differentiate between these tasks. Finally, reward relabeling does poorly, since it naively assigns $z'$ solely based on the trajectory reward, not how close the trajectory reward is to being optimal.

\section{Introduction}

Model-free reinforcement learning (RL) combined with powerful function approximators has achieved remarkable success in games like Atari~\cite{mnih2015human} and Go~\cite{silver2017mastering}, and control tasks like walking~\cite{haarnoja2018soft} and flying~\cite{kaufmann2018deep}. However, a key limitation to these methods is their sample complexity. They often require millions of samples to learn simple locomotion skills, and sometimes even billions of samples to learn more complex game strategies. Creating general purpose agents will necessitate learning multiple such skills or strategies, which further exacerbates the inefficiency of these algorithms. On the other hand, humans (or biological agents) are not only able to learn a multitude of different skills, but from orders of magnitude fewer samples~\cite{karni1998acquisition}. So, how do we endow RL agents with this ability to learn efficiently across multiple tasks?

\begin{figure}[t!]
\centering
\includegraphics[width=\linewidth]{figures/illustration.pdf}
\caption{A rollout can often provide very little information about how to perform a task A. In the trajectory-following task on the left, the trajectory (green) sees almost no reward signal (areas in red). However, in the multi-task setting where each target trajectory represents a different task, we can find another task B for which our trajectory is a ``pseudo-demonstration." This hindsight relabeling provides high reward signal and enables sample-efficient learning.}
\label{fig:illustration}
\end{figure}

One key hallmark of biological learning is the ability to learn from mistakes. In RL, mistakes made while solving a task are only used to guide the learning of that particular task. But data seen while making these mistakes often contain a lot more information. In fact, extracting and re-using this information lies at the heart of most efficient RL algorithms. Model-based RL re-uses this information to learn a dynamics model of the environment. However for several domains, learning a robust model is often more difficult than directly learning the policy~\cite{duan2016benchmarking}, and addressing this challenge continues to remain an active area of research~\cite{nagabandi2018neural}. Another way to re-use low-reward data is off-policy RL, where in contrast to on-policy RL, data collected from an older policy is re-used while optimizing the new policy. But in the context of multi-task learning, this is still inefficient (\Secref{section:experiments}) since data generated from one task cannot effectively inform a different task. Towards solving this problem, recent work~\cite{andrychowicz2017hindsight} focus on extracting even more information through \textit{hindsight}.

In goal-conditioned settings, where tasks are defined by a sparse goal, HER~\cite{andrychowicz2017hindsight} relabels the desired goal, for which a trajectory was generated, to a state seen in that trajectory. Therefore, if the goal-conditioned policy erroneously reaches an incorrect goal instead of the desired goal, we can re-use this data to teach it how to reach this incorrect goal. Hence, a low-reward trajectory under one desired goal is converted to a high-reward trajectory for the unintended goal. This new relabelling provides a strong supervision and produces significantly faster learning. However, a key assumption made in this framework is that goals are a sparse set of states that need to be reached. This allows for efficient relabeling by simply setting the relabeled goals to the states visited by the policy. But for several real world problems like energy-efficient transport, or robotic trajectory tracking, rewards are often complex combinations of desirables rather than sparse objectives. So how do we use hindsight for general families of reward functions?

\begin{figure*}[t!]
\centering
\includegraphics[width=0.9\textwidth]{figures/GH_intro_1.pdf}
\caption{Trajectories $\tau(z_i)$, collected trying to maximize $r(\cdot|z_i)$, may contain very little reward signal about how to solve their original tasks. Generalized Hindsight checks against randomly sampled ``candidate tasks" $\{v_i\}_{i=1}^K$ to find different tasks $z'_i$ for which these trajectories are ``pseudo-demonstrations." Using off-policy RL, we can obtain more reward signal from these relabeled trajectories.}
\label{fig:intro}
\end{figure*}

In this paper, we build on the ideas of goal-conditioned hindsight and propose \textbf{Generalized Hindsight}. Here, instead of performing hindsight on a task-family of sparse goals, we perform hindsight on a task-family of reward functions. Since dense reward functions can capture a richer task specification, GH allows for better re-utilization of data. Note that this is done along with solving the task distribution induced by the family of reward functions. However for relabeling, instead of simply setting visited states as goals, we now need to compute the reward functions that best explain the generated data. To do this, we draw connections from Inverse Reinforcement Learning (IRL), and propose an approximate IRL relabeling algorithm we call AIR. Concretely, AIR takes a new trajectory and compares it to $K$ randomly sampled tasks from our distribution. It selects the task for which the trajectory is a ``pseudo-demonstration," i.e. the trajectory achieves higher performance on that task than any of our previous trajectories. This ``pseudo-demonstration" can then be used to quickly learn how to perform that new task. We go into detail on good selection algorithms in \Secref{section:experiments}, and show an illustrative example of the relabeling process in \autoref{fig:illustration}. We test our algorithm on several multi-task control tasks, and find that AIR consistently achieves higher asymptotic performance using as few as 20\% of the environment interactions as our baselines. We also introduce a computationally more efficient version that also achieves higher asymptotic performance than our baselines.

In summary, we present three key contributions in this paper: (a) we extend the ideas of hindsight to the generalized reward family setting; (b) we propose AIR, a relabeling algorithm using insights from IRL; and (c) we demonstrate significant improvements in multi-task RL on a suite of multi-task navigation and manipulation tasks.

\section{Do \emph{not} have an appendix here}

\end{document}

\section{Related Work}

\subsection{Multi-task and transfer learning}
Learning models that can share information across tasks has been concretely studied in the context multi-task learning~\cite{caruana1997multitask}, where models for multiple tasks are simultaneously learned. More recently, \citet{kokkinos2017ubernet, doersch2017multi} looks at shared learning across visual tasks, while \citet{devin2017learning,pinto2017learning} looks at shared learning across robotic tasks.

Transfer learning~\cite{pan2009survey,torrey2010transfer} focuses on transferring knowledge from one domain to another. One of the simplest forms of transfer is finetuning~\cite{girshick2014rich}, where instead of learning a task from scratch it is initialized on a different task. Several other works look at more complex forms of transfer~\cite{yang2007adapting,hoffman2014continuous,aytar2011tabula,saenko2010adapting,kulis2011you,fernando2013unsupervised,gopalan2011domain,jhuo2012robust}.

In the context of RL, transfer learning~\cite{taylor2009transfer} research has focused on learning transferable features across tasks~\cite{parisotto2015actor,barreto2017successor,omidshafiei2017deep}.  Another line of work by \cite{rusu2016progressive,kansky2017schema,devin2017learning} has focused on network architectures that improves transfer of RL policies. Another way of getting generalizable policies is through domain randomization~\cite{sadeghi2016cad,tobin2017domain}, i.e. train an unconditional policy across all of the domains in the multi-task learning setting. Although this works for task distributions over the dynamics and observation space~\cite{pinto2017asymmetric}, it cannot handle distributions of reward functions as seen in our experiments. The techniques of domain randomization are however complementary to our method, where it can provide generalizability to dynamics and observation space while Generalized Hindsight can provide generalizability to different reward functions.

Hierarchical reinforcement learning~\cite{morimoto2001acquisition, barto2004intrinsically} is another framework amenable for multitask learning. Here the key idea is to have a hierarchy of controllers. One such setup is the Options framework~\cite{sutton1999between} where the higher level controllers breaks down a task into sub-tasks and chooses a low-level controller to complete that sub-task.
Variants of the Options framework \cite{frans2017meta, li2019sub} have examined how to train hierarchies in a multi-task setting, but information re-use across tasks remains restricted to learning transferable primitives. Generalized Hindsight could be used to train these hierarchical policies more efficiently.

\subsection{Hindsight in RL}
Hindsight methods have been used for improving learning across as variety of applications. \citet{andrychowicz2017hindsight} uses hindsight to efficiently learn on sparse, goal-conditioned tasks. \citet{nair2018visual} approaches goal-reaching with visual input by learning a latent space encoding for images, and using hindsight relabeling within that latent space. \citet{ding2019goal} uses hindsight relabeling as a form of data augmentation for a limited set of expert trajectories, which it then uses with adversarial imitation learning to learn goal-conditioned policies. Several hierarchical methods \cite{levy2017hierarchical, nachum2018data} train a low-level policy to achieve subgoals and a higher-level controller to propose those subgoals. These methods use hindsight relabeling to help the higher-level learn, even when the low-level policy fails to achieve the desired subgoals. Generalized Hindsight could be used to allow for richer low-level reward functions, potentially allowing for more expressive hierarchical policies.

\subsection{Inverse Reinforcement Learning}
Inverse reinforcement learning (IRL) has had a rich history of solving challenging robotics problems~\cite{abbeel2004apprenticeship,ng2000algorithms}. More recently, powerful function approximators have enabled more general purpose IRL. For instance, \citet{ho2016generative} use an adversarial framework to approximate the reward function. \citet{li2017infogail} build on top of this idea by learning reward functions on demonstrations from a mixture of experts. Although, our relabeling strategies currently build on top of max-margin based IRL~\cite{ratliff2006maximum}, our central idea is orthogonal to the choice of IRL techniques and can be combined with more complex function approximators.


text:
\section{Introduction}
Convolutional neural networks~\cite[CNN,][]{Fukushima80,LeCun89} have become the
method of choice for object recognition~\citep[see, e.g.,][]{Krizhevsky-2012}.
They have proved to be successful at a variety of benchmark problems including,
but not limited to, handwritten digit recognition~\citep[see,
e.g.,][]{Ciresan-2012}, natural image classification~\citep[see,
e.g.,][]{Lin2014,Simonyan2015,szegedy2014going}, house number
recognition~\citep[see, e.g.,][]{Goodfellow+et+al-ICLR2014a}, traffic sign
recognition~\citep[see, e.g.,][]{Ciresan-et-al-2012}, as well as for speech
recognition~\citep[see, e.g.,][]{Hamid2012, sainath2013, toth2014combining}.
Furthermore, image representations from CNNs trained to recognize objects on a
large set of more than one million images~\citep{Simonyan2015,szegedy2014going}
have been found to be extremely helpful in performing other computer vision
tasks such as image caption generation~\citep[see,
e.g.,][]{Vinyals-et-al-arxiv2014,Xu-et-al-arxiv2015}, video description
generation~\citep[see, e.g.,][]{Li2015} and object
localization/detection~\citep[see, e.g.,][]{Sermanet14}.

While the CNN has been especially successful in computer vision, recurrent
neural networks (RNN) have become the method of choice for modeling sequential
data, such as text and sound. Natural language processing (NLP) applications
include language modeling~\citep[see, e.g.,][]{Mikolov-thesis-2012}, and machine
translation~\citep{Sutskever-et-al-NIPS2014,Cho2014,bahdanau2014neural}.  Other
popular areas of application include offline handwriting
recognition/generation~\citep{Graves+Schmidhuber-2009,Graves-et-al-NIPS2007,Graves-arxiv2013}
and speech recognition~\citep{Chorowski-et-al-arxiv2014,Graves+Jaitly-ICML2014}.
RNNs have also been used together with CNNs in speech
recognition~\citep{sainath2015}.  The recent revival of RNNs has largely been
due to advances in learning
algorithms~\citep{Pascanu+al-ICML2013-small,Martens+Sutskever-ICML2011} and
model
architectures~\citep{Pascanu-et-al-ICLR2014,Hochreiter+Schmidhuber-1997,Cho2014}.

The architecture proposed here is
related and inspired by this earlier work, but our model relies on purely
uni-dimensional RNNs coupled in a novel way, rather than on a multi-dimensional
RNN. The basic idea behind the proposed ReNet architecture is to replace each
convolutional layer (with convolution+pooling making up a layer) in the CNN with
four RNNs that sweep over lower-layer features in different directions: (1)
bottom to top, (2) top to bottom, (3) left to right and (4) right to left.
The recurrent layer ensures that each feature activation in its output is an
activation at the specific location \emph{with respect to the whole image}, in
contrast to the usual convolution+pooling layer which only has a local context
window.  The lowest layer of the model sweeps over the input image, with
subsequent layers operating on extracted representations from the layer below,
forming a hierarchical representation of the input.

\citet{Graves+Schmidhuber-2009} have demonstrated an RNN-based object
recognition system for offline Arabic handwriting recognition.  The main
difference between ReNet and the model of \citet{Graves+Schmidhuber-2009} is
that we use the usual sequence RNN, instead of the multidimensional RNN. We make
the latter two parts of a single layer, usually (horizontal) RNNs or one
(horizontal) bidirectional RNN, work on the hidden states computed by the first
two (vertical) RNNs, or one (vertical) bidirectional RNN. This allows us to use
a plain RNN, instead of the more complex multidimensional RNN, while making each
output activation of the layer be computed with respect to the whole input
image.

One important consequence of the proposed approach compared to the
multidimensional RNN is that the number of RNNs at each layer scales now linearly
with respect to the number of dimensions $d$ of the input image ($2d$). A
multidimensional RNN, on the other hand, requires the exponential number of RNNs
at each layer ($2^d$). Furthermore, the proposed variant is more easily
parallelizable, as each RNN is dependent only along a horizontal or vertical
sequence of patches. This architectural distinction results in our model being
much more amenable to distributed computing than that of
\citet{Graves+Schmidhuber-2009}.

In this work, we test the proposed ReNet on several widely used object
recognition benchmarks, namely  MNIST~\citep{Lecun99objectrecognition},
CIFAR-10~\citep{KrizhevskyHinton2009} and SVHN~\citep{Netzer-wkshp-2011}. Our
experiments reveal that the model performs comparably to convolutional neural
networks on all these datasets,
suggesting the potential of RNNs as a competitive alternative to CNNs for image
related tasks.

\section{Model Description}

\begin{wrapfigure}{R}{0.3\textwidth}
    \centering
    \includegraphics[width=0.3\columnwidth]{first_layer.pdf}
    \caption{A one-layer ReNet}
    \label{fig:networklayer}
    \vspace{-3mm}
\end{wrapfigure}

Let us denote by $X=\left\{x_{i,j}\right\}$ the input image or the feature map
from the layer below, where $X \in \RR^{w \times h \times c}$ with $w$, $h$ and
$c$ the width, height and number of channels, or the feature dimensionality,
respectively. Given a receptive field (or patch) size of $w_p \times h_p$, we
split the input image $X$ into a set of $I \times J$ (non-overlapping) patches
$P = \left\{ p_{i,j} \right\}$, where $I = \frac{w}{w_p}$, $J = \frac{h}{h_p}$
and $p_{i,j} \in \RR^{w_p \times h_p \times c}$ is the $(i,j)$-th patch of the
input image. The first index $i$ is the horizontal index and the other index
$j$ is the vertical index.

First, we sweep the image vertically with two RNNs, with one RNN working in
a bottom-up direction and the other working in a top-down direction.
Each RNN takes as an input one (flattened) patch at a time and updates its
hidden state, working \emph{along each column} $j$ of the split input image $X$.
\begin{align}
    v^F_{i,j} = f_{\text{VFWD}}(z^F_{i,j-1},p_{i,j}), &\text{ for
    }j=1,\cdots, J\\
    v^R_{i,j} = f_{\text{VREV}}(z^R_{i,j+1},p_{i,j}), &\text{ for
    }j=J,\cdots,1
\end{align}

Note that $f_{\text{VFWD}}$ and $f_{\text{VREV}}$ return the activation of the
recurrent hidden state, and may be implemented either as a simple $\tanh$ layer,
as a gated recurrent layer~\citep{Cho2014} or as a long short-term memory
layer~\citep{Hochreiter+Schmidhuber-1997}.

After this vertical, bidirectional sweep, we concatenate the intermediate hidden
states $v^F_{i,j}$ and $v^R_{i,j}$ at each location $(i,j)$ to get a composite
feature map $V= \left\{ v_{i,j} \right\}_{i=1,\ldots,I}^{j=1,\ldots,J}$, where
$v_{i,j} \in \RR^{2d}$ and $d$ is the number of recurrent units.
Each $v_{i,j}$ is now the activation of a feature detector at the location
$(i,j)$ with respect to all the patches in the $j$-th column of the original
input ($p_{i, j}$ for all $i$).

Next we sweep over the obtained feature map $V$ horizontally with two RNNs
($f_{\text{HFWD}}$ and $f_{\text{HREV}}$).
In a similar manner as the vertical sweep, these RNNs work along each row
of $V$ resulting in the output feature map $H = \left\{ h_{i,j} \right\}$, where
$h_{i,j} \in \RR^{2d}$. Now, each vector $h_{i,j}$ represents the features of
the original image patch $p_{i,j}$ \emph{in the context of the whole image}.

Let us denote by $\phi$ the function from the input image map of $X$ to
the output feature map $H$ (see Fig.~\ref{fig:networklayer} for a graphical
illustration.) Clearly, we can stack multiple $\phi$'s to make the
proposed ReNet deeper and capture increasingly complex features of the input
image. After any number of recurrent layers are applied to an input image,
the activation at the last recurrent layer may be flattened and fed into a
differentiable classifier. In our experiments we used several
fully-connected layers followed by a softmax classifier (as shown in Fig.~\ref{fig:network}).

The deep ReNet is a smooth, continuous function, and the parameters (those from
the RNNs as well as from the fully-connected layers) can be estimated by the
stochastic gradient descent algorithm with the gradient computed by
backpropagation algorithm~\citep[see, e.g.,][]{BP86} to maximize the
log-likelihood.

\section{Differences between LeNet and ReNet}
\label{sec:lenetrenet}

There are many similarities and differences between the proposed ReNet and a
convolutional neural network. In this section we use LeNet to refer to the
canonical convolutional neural network as shown by \citet{LeCun89}. Here we
highlight a few key points of comparison between ReNet and LeNet.

At each layer, both networks apply the same set of filters to patches of the
input image or of the feature map from the layer below. ReNet, however,
propagates information through lateral connections that span across the whole
image, while LeNet exploits local information only. The lateral connections
should help extract a more compact feature representation of the input image at
each layer, which can be accomplished by the lateral connections
removing/resolving redundant features at different locations of the image. This
should allow ReNet resolve small displacements of features across multiple
consecutive patches.

LeNet max-pools the activations of each filter over a small region to achieve
local translation invariance. In contrast, the proposed ReNet does not use any
pooling due to the existence of learned lateral connections. The lateral
connection in ReNet can emulate the local competition among features induced by
the max-pooling in LeNet.  This does not mean that it is not possible to use
max-pooling in ReNet. The use of max-pooling in the ReNet could be helpful in
reducing the dimensionality of the feature map, resulting in lower computational
cost.

Max-pooling as used in LeNet may prove problematic when building a
convolutional autoencoder whose decoder is an inverse\footnote{
    All the forward arrows from the input to the output in the original LeNet
    are reversed.
}
of LeNet, as the max operator is not invertible. The proposed
ReNet is end-to-end smooth and differentiable, making it more suited to be used
as a decoder in the autoencoder or any of its probabilistic variants~\citep[see,
e.g.,][]{Kingma+Welling-ICLR2014}.

In some sense, each layer of the ReNet can be considered as a variant of a usual
convolution+pooling layer, where pooling is replaced with lateral connections,
and convolution is done without any overlap. Similarly, \citet{Springenberg2014}
recently proposed a variant of a usual LeNet which does not use any pooling.
They used convolution with a larger stride to compensate for the lack of
dimensionality reduction by pooling at each layer. However, this approach still
differs from the proposed ReNet in the sense that each feature activation at a
layer is only with respect to a subset of the input image rather than the whole
input image.

The main disadvantage of ReNet is that it is not easily parallelizable, due to
the sequential nature of the recurrent neural network (RNN). LeNet, on the other
hand, is highly parallelizable due to the independence of computing activations
at each layer. The introduction of sequential, lateral connections, however, may
result in more efficient parametrization, requiring a smaller number of
parameters with overall fewer computations, although this needs to be further
explored. We note that this limitation on parallelization applies only to
model parallelism, and any technique for data parallelism may be used for both
the proposed ReNet and the LeNet.

\section{Experiments}

\subsection{Datasets}

We evaluated the proposed ReNet on three widely-used benchmark datasets; MNIST,
CIFAR-10 and the Street View Housing Numbers (SVHN). In this section we describe
each dataset in detail.

\paragraph{MNIST}
The MNIST dataset~\citep{Lecun99objectrecognition} consists of 70,000
handwritten digits from 0 to 9, centered on a $28\times 28$ square canvas. Each
pixel represents the grayscale in the range of $\left[0, 255\right]$.\footnote{
    We scaled each pixel by dividing it with $255$.
}
We split the dataset into 50,000 training samples, 10,000 validation
samples and 10,000 test samples, following the standard split.

\paragraph{CIFAR-10}
The CIFAR-10 dataset~\citep{KrizhevskyHinton2009} is a curated subset of the 80
million tiny images dataset, originally released by
\citet{Torralba+Fergus+Freeman-2008}. CIFAR-10 contains 60,000 images each of which
belongs to one of ten categories; airplane, automobile, bird, cat, deer, dog,
frog, horse, ship and truck. Each image is 32 pixels wide and 32 pixels high
with 3 color channels (red, green and blue.) Following the standard procedure,
we split the dataset into 40,000 training, 10,000 validation and 10,000 test
samples. We applied zero-phase component analysis (ZCA) and normalized each pixel
to have zero-mean and unit-variance across the training
samples, as suggested by \citet{KrizhevskyHinton2009}.

\paragraph{Street View House Numbers}
The Street View House Numbers (SVHN) dataset~\citep{Netzer-wkshp-2011} consists
of cropped images representing house numbers captured by Google StreetView
vehicles as a part of the Google Maps mapping process. These images consist of
digits 0 through 9 with values in the range of [0, 255] in each of 3
red-green-blue color channels. Each image is 32 pixels wide and 32 pixels
high giving a sample dimensionality (32, 32, 3). The number of samples we used for
training, valid, and test sets is 543,949, 60,439, and 26,032 respectively. We
normalized each pixel to have zero-mean and unit-variance across the training
samples.

\subsubsection{Data Augmentation}

It has been known that augmenting training data often leads to better
generalization~\citep[see, e.g.,][]{Krizhevsky-2012}. We decided to employ
two primary data augmentations in the following experiments: {\it flipping} and
{\it shifting}.

For flipping, we either flipped each sample horizontally with 25\% chance,
flipped it vertically with 25\% chance, or left it unchanged. This allows lets
the model observe ``mirror images'' of the original image during training.
In the case of shifting, we either shifted the image by 2 pixels to the left
(25\% chance), 2 pixels to the right (25\% chance) or left it as it was. After
this first processing, we further either shifted it by 2 pixels to the top
(25\% chance), 2 pixels to the bottom (25\% chance) or left it as it was. This
two-step procedure makes the model more robust to slight shifting of an object
in the image. The shifting was done without padding the borders of the image,
preserving the original size but dropping the pixels which are shifted out of
the input while shifting in zeros.

The choice of whether to apply these augmentation procedures on each dataset was
chosen on a per-case basis in order to maximize validation performance.

\begin{figure}[t]
    \advance\leftskip-0.2\columnwidth
    \centering
    \makebox[\columnwidth][c]{\includegraphics[height=.135\textheight,width=1.1\columnwidth]{recrec_svhn.pdf}}
    \caption{The ReNet network used for SVHN classification}
    \label{fig:network}
\end{figure}

\subsection{Model Architectures}

\paragraph{Gated Recurrent Units}

Gated recurrent units~\citep[GRU,][]{Cho2014} and long short-term memory
units~\citep[LSTM,][]{Hochreiter+Schmidhuber-1997} have been successful in many
applications using recurrent neural networks~\citep[see,
e.g.,][]{Cho2014,Sutskever-et-al-NIPS2014,Xu-et-al-arxiv2015}. To show that the
ReNet model performs well independently of the
specific implementation of the recurrent units, we decided to use the GRU on
MNIST and CIFAR-10, with LSTM units on SVHN.

The hidden state of the GRU at time $t$ is computed by
\begin{align*}
    h_t = (1-u_t) \odot h_{t-1} + u_t \odot \tilde{h}_t,
\end{align*}
where
\begin{align*}
    \tilde{h}_t = \tanh\left( W x_t + U (r_t \odot h_{t-1}) + b \right)
\end{align*}
and
\begin{align*}
    \left[ u_t; r_t\right] = \sigma\left( W_g x_t + U_g h_{t-1} + b_g\right).
\end{align*}

For more details on the LSTM unit, as well as for an in-depth comparison among
different recurrent units, we refer the reader to \citep{Chung2015}.

\paragraph{General Architecture}

The principal parameters that define the architecture of the proposed ReNet are
the number of ReNet layers ($N_{\text{RE}}$), their corresponding receptive field
sizes ($w_p \times h_p$) and feature dimensionality ($d_{\text{RE}}$),
the number of fully-connected layers ($N_{\text{FC}}$) and their corresponding
numbers ($d_{\text{FC}}$) and types ($f_{\text{FC}}$) of hidden units.

In this introductory work, we did not focus on extensive hyperparameter
search to find the optimal validation set
performance. We chose instead to focus the experiments on a small set of
hyperparameters, with the only aim to show the potential of the proposed model.
Refer to Table~\ref{tbl:architectures} for a summary of the settings that performed
best on the validation set of the studied datasets and to Fig.~\ref{fig:network}
for a graphical illustration of the model we selected for SVHN.

\begin{table}[t]
    \centering
    \begin{tabular}{l || c | c | c }
        & MNIST & CIFAR-10 & SVHN \\
        \hline
        \hline
    $N_{\text{RE}}$ & 2 & 3 & 3 \\
        \hline
        $w_p \times h_p$ & $[2\times 2]$--$[2 \times 2]$ & $[2\times 2]$--$[2 \times 2]$--$[2
        \times 2]$ & $[2\times 2]$--$[2 \times 2]$--$[2 \times 2]$ \\
        \hline
    $d_{\text{RE}}$ & 256--256 & 320--320--320 & 256--256--256 \\
        \hline
    $N_{\text{FC}}$ & 2 & 1 & 2 \\
        \hline
    $d_{\text{FC}}$ & 4096--4096 & 4096 & 4096--4096 \\
        \hline
    $f_{\text{FC}}$ & $\max(0, x)$ & $\max(0,x)$ & $\max(0,x)$ \\
        \hline
    Flipping & no & yes & no \\
        \hline
    Shifting & yes & yes & yes \\
    \end{tabular}
    \caption{Model architectures used in the experiments. Each row shows
             respectively the number of ReNet layers, the size of the patches,
             the number of neurons of each ReNet layer, the number of fully
             connected layers, the number of neurons of the fully connected
             layers, their activation function and the data augmentation
             procedure employed.}
    \label{tbl:architectures}
\end{table}

\subsection{Training}

To train the networks we used a recently proposed adaptive learning rate
algorithm, called Adam~\citep{Kingma2014}. In order to reduce overfitting we
applied dropout~\citep{Srivastava14} after each layer, including both the
proposed ReNet layer (after the horizontal and vertical sweeps) and the
fully-connected layers. The input was also corrupted by masking out each variable
with probability $0.2$. Finally, each optimization run was early stopped based
on validation error.

Note that unlike many previous works, we did not retrain the model (selected
based on the validation performance) using both the training and validation
samples. This experiment design choice is consistent with our declared goal to
show a proof of concept rather than stressing absolute performance. There are
many potential areas of exploration for future work.

\begin{table}[ht]
    \centering

    \begin{minipage}{0.45\textwidth}
        \centering

        \begin{tabular}{l |  l}
            Test Error & Model  \\
            \hline
0.28\% & \citep{DBLP:conf/icml/WanZZLF13}$\star$ \\
0.31\% & \citep{DBLP:journals/corr/Graham14}$\star$ \\
0.35\% & \citep{DBLP:journals/corr/abs-1003-0358} \\
0.39\% & \citep{DBLP:conf/nips/MairalKHS14}$\star$ \\
0.39\% & \citep{DBLP:journals/corr/LeeXGZT14}$\star$ \\
0.4\% & \citep{DBLP:conf/icdar/SimardSP03}$\star$ \\
0.44\% & \citep{DBLP:journals/corr/Graham14a}$\star$ \\
0.45\% & \citep{Goodfellow2013}$\star$ \\
\bf{0.45\%} & \bf{ReNet} \\
0.47\% & \citep{Lin2014}$\star$ \\
0.52\% & \citep{DBLP:journals/pami/AzzopardiA13} \\
        \end{tabular}

        \vspace{2mm}
        (a) MNIST
    \end{minipage}
    \hfill
    \begin{minipage}{0.45\textwidth}
        \centering

        \begin{tabular}{l |  l}
            Test Error & Model  \\
            \hline
4.5\% & \citep{DBLP:journals/corr/Graham14a}$\star$ \\
6.28\% & \citep{DBLP:journals/corr/Graham14}$\star$ \\
8.8\% & \citep{Lin2014}$\star$ \\
9.35\% & \citep{Goodfellow2013}$\star$ \\
9.39\% & \citep{DBLP:journals/corr/SpringenbergR13}$\star$ \\
9.5\% & \citep{DBLP:conf/nips/SnoekLA12}$\star$ \\
11\% & \citep{Krizhevsky-2012}$\star$ \\
11.10\% & \citep{DBLP:conf/icml/WanZZLF13}$\star$ \\
\bf{12.35\%} & \bf{ReNet} \\
15.13\% & \citep{DBLP:journals/corr/abs-1301-3557}$\star$ \\
15.6\% & \citep{DBLP:journals/corr/abs-1207-0580}$\star$ \\
        \end{tabular}

        \vspace{2mm}
        (b) CIFAR-10
    \end{minipage}

    \vspace{4mm}
    \begin{minipage}{0.45\textwidth}
        \centering
        \begin{tabular}{l |  l}
            Test Error & Model  \\
            \hline
1.92\% & \citep{DBLP:journals/corr/LeeXGZT14}$\star$ \\
2.23\% & \citep{DBLP:conf/icml/WanZZLF13}$\star$ \\
2.35\% & \citep{Lin2014}$\star$ \\
\bf{2.38\%} & \bf{ReNet} \\
2.47\% & \citep{Goodfellow2013}$\star$ \\
2.8\% & \citep{DBLP:journals/corr/abs-1301-3557}$\star$ \\
        \end{tabular}

        \vspace{2mm}
        (c) SVHN
    \end{minipage}
    \hfill
    \begin{minipage}{0.45\textwidth}
        \caption{Generalization errors obtained by the
            proposed ReNet along with those reported by previous works
            on each of the three datasets. $\star$ denotes a
            convolutional neural network. We only list the results reported by a single
            model, i.e., no ensembling of multiple models.
            In the case of SVHN, we report results from models trained on
            the Format 2 (cropped digit) dataset only.}
        \label{tbl:result}
    \end{minipage}
\end{table}

\section{Results and Analysis}

In Table~\ref{tbl:result}, we present the results on three datasets,
along with previously reported results.

It is clear that the proposed ReNet performs comparably to deep convolutional
neural networks which are the {\it de facto} standard for object recognition.
This suggests that the proposed ReNet is a viable alternative to convolutional
neural networks (CNN), even on tasks where CNNs have historically dominated.
However, it is important to notice that the proposed ReNet does not outperform
state-of-the-art convolutional neural networks on any of the three benchmark
datasets, which calls for more research in the future.

\section{Discussion}

\paragraph{Choice of Recurrent Units}
Note that the proposed architecture is independent of the chosen recurrent
units. We observed in preliminary experiments that gated
recurrent units, either the GRU or the LSTM, outperform a usual sigmoidal unit
(affine transformation followed by an element-wise sigmoid function.) This
indirectly confirms that the model utilizes long-term dependencies across an
input image, and the gated recurrent units help capture these dependencies.

\paragraph{Analysis of the Trained ReNet}
In this paper, we evaluated the proposed ReNet only quantitatively. However, the
accuracies on the test sets do not reveal what kind of image structures the
ReNet has captured in order to perform object recognition. Due to the large
differences between ReNet and LeNet discussed in
Sec.~\ref{sec:lenetrenet}, we expect that the internal behavior of ReNet
will differ from that of LeNet significantly. Further investigation along
the line of \citep{ZeilerFergus14} will be needed, as well exploring ensembles
which combine RNNs and CNNs for bagged prediction.

\paragraph{Computationally Efficient Implementation}
As discussed in Sec.~\ref{sec:lenetrenet}, the proposed ReNet is less
parallelizable due to the sequential nature of the recurrent neural network
(RNN). Although this sequential nature cannot be addressed directly, our
construction of ReNet allows the forward and backward RNNs to be run
independently from each other, which allows for parallel computation.
Furthermore, we can use many parallelization tricks widely used for training
convolutional neural networks such as parallelizing fully-connected layers
~\citep{krizhevsky2014one}, having separate sets of kernels/features in
different processors~\citep{Krizhevsky-2012} and exploiting data parallelism.

\section*{Acknowledgments}

The authors would like to thank the developers of
Theano~\citep{Bergstra2010,Bastien2012}. We acknowledge the support of the
following organizations for research funding and computing support: NSERC,
Samsung, Calcul Qu\'{e}bec, Compute Canada, the Canada Research Chairs and
CIFAR.  F.V. was funded by the AI*IA Young Researchers Mobility Grant
and the Politecnico di Milano PHD School International Mobility Grant.

\small