\section{Introduction}

The formation of social relationships is a complex process that has long fascinated researchers.
It is well-understood that, besides pairwise interactions, friendships and rivalries are affected by social context.
The study of such phenomena dates back to Heider's theory of \emph{social balance}~\cite{Heider1944,Heider1946,Heider1958}, which can be seen as a rigorous realization of the proverb ``the enemy of my enemy is my friend''.
The theory classifies a social state as \emph{balanced} whenever every group of three entities (a \emph{triad}) is balanced:~it consists of either three mutual friendships, or one friendship whose both parties have a mutual enemy.
The other types of triads create social unrest that eventually gets resolved by changing the relationship between two parties.
For example, a triad with three mutual enmities will eventually lead to two entities forming an alliance against the common enemy.
A triad with exactly one enmity will either see a reconciliation to a friendship under the uniting influence of the common friend, or
lead to the break of one friendship following the social axiom ``the friend of my enemy is my enemy''~\cite{Schwartz2010}.

Cartwright and Harary developed a graph-theoretic model of Heider's theory~\cite{Cartwright1956},
and showed that any balanced state is either a utopia without any enmities,
or it consist of two mutually antagonistic groups~\cite{Harary1953,Davis1967}.
\new{This structural theory of social balance has seen applications across various fields ranging from
philosophy, sociology, or political science~\cite{bramson2017understanding,Taylor1970,fontan2021signed,Sherwin1971,Moore1979}
all the way to fields such as neuroscience or computer science~\cite{Chiang2020,MinhPham2020,li2013influence,altafini2012consensus},
It has also been supported by empirical evidence~\cite{Rawlings2017,Kirkley2019,askarisichani20201995}, see also~\cite{zheng2015social} for a review.
The setting is attractive to physicists due to its intimate connection to the Ising model and spin glasses~\cite{Facchetti2011},
and indeed tools and techniques from statistical physics have proved to be instrumental in improving our understanding of such systems~\cite{belaza2017statistical,saeedian2017epidemic,manshour2021dynamics}, see also~\cite{castellano2009statistical} for a review.}

It is natural to associate each network state with a \emph{potential energy}
that counts the difference of imbalanced minus balanced triads;
hence the perfectly balanced states are those that minimize the energy of the network~\cite{Marvel2009}.
\new{Understanding how energy is minimized in a system is a fundamental problem studied across different physics fields,
and signed graphs present a clean theoretical framework to study this problem in a setting with a population structure.
It is well known that the energy landscape over signed graphs} has local minima (also known as \emph{jammed states})~\cite{Antal2005}, that is,
states from which all paths to social balance must temporarily increase the number of imbalanced triads.

When the network state is imbalanced, we expect that a social process will perturb it until balance is reached.
The seminal work~\cite{Antal2006} introduced a stochastic process known as \emph{Local Triad Dynamics (LTD)},
according to which imbalanced triads are sampled at random, and the sampled triad is balanced by flipping the relationship of two of its entities. This step is called an \emph{edge flip}.
The same work also introduced \emph{Constrained Triad Dynamics (CTD)}, a socially-aware variant of LTD under which an edge flip is only possible if it reduces the number of imbalanced triads.
Unfortunately, the existence of local minima in the energy landscape implies that CTD can get stuck in jammed states and thus remain permanently imbalanced.

Although the existence of jammed states is well understood in terms of the energy landscape,
little is known about them from the perspective of the stochastic process, that is, about their reachability properties.
For example, from which initial states is it possible to reach a jammed state?
Moreover, if a jammed state is reached, can the process escape if we slightly perturb the network?
Finally, is there a plausible, socially-aware stochastic dynamics (like CTD) that always reaches balance (unlike CTD)?
We tackle these questions in this work.

First, we study the robustness and attractor properties of the local minima of the energy landscape.
We show that the number of jammed states is super-exponential, compared to the previously known exponential lower-bound,
and that jammed states are reachable from any initial state that is not too friendship-dense.
Moreover, we show that some of those jammed states are strongly attracting:
even when perturbing
 a constant portion of

 edges adjacent to each vertex, the same jammed state is subsequently reached with probability $1$.
\new{As a byproduct, our results resolve an open problem from~\cite{Marvel2009}.}

Second, we propose a new plausible dynamics called \emph{Best Edge Dynamics (BED)}.
Like CTD, BED is a stochastic process in which edge flips are socially-aware, in the sense that they maximize the number of newly balanced triads (see below for details).
We prove that, unlike CTD, BED always reaches a balanced state from any initial state.
Moreover, we show that BED converges faster to a balanced state than CTD in various interesting settings, such as when started from a state that is already close to being balanced.

\new{Finally, we complement our analytical results with computer simulations in the cases when the initial friendship edges form a random Erd\H{o}s-R\'{e}nyi  network or a random scale-free networks. }

\section{Triad Dynamics in Social Networks}

Balance on social networks is studied in terms of signed graphs.
A {\em signed graph} $G=(V,E,s)$ consists of a finite complete graph $(V,E)$ on $|V|=n$ vertices together with an edge labeling
\[s\colon E\rightarrow \{-1,+1\}.\]
The labeling $s$ assigns to each edge one of the two signs; the edges labeled by $+1$ are {\em friendships} and those labeled $-1$ are {\em enmities}.
\new{Thus each pair of individuals (modeled by vertices) has a defined relationship: either they are friends, or they are enemies.}

Given a signed graph $G=(V,E,s)$, a {\em triad} is a subgraph of $G$ defined by any three of its vertices.
A triad is of {\em type $\Delta_k$} for $k=0,1,2,3$ if it contains exactly $k$ edges labeled $-1$.
A triad is {\em balanced} if its type is $\Delta_0$ or $\Delta_2$.
Intuitively, a triad is balanced if it satisfies the known proverb ``the enemy of my enemy is my friend''.
For an edge $e$ in $G$, its {\em rank} $r_e$ is the number of imbalanced triads containing $e$.
Finally, a signed graph $G$ is {\em balanced} if each triad in $G$ is balanced, see~\cref{fig:process}.

\begin{figure}[h]
\includegraphics[width=\linewidth]{fig1-process.pdf}
\caption{A triad of type $\Delta_k$ contains $k$ enmity edges.
The imbalanced triads $\Delta_1$ and $\Delta_3$ can be made balanced by flipping any one edge.
A sequence of flips typically reaches a state where all triads are balanced.
The rank $r_e$ of edge $e$ is the number of imbalanced triads containing $e$.}
\label{fig:process}
\end{figure}

It is known that a signed graph is balanced if and only if its enmity edges form a complete bipartite graph over the vertex set~\cite{Cartwright1956}.
This means that we may partition the vertices of a balanced signed graph into two vertex classes, such that all pairs of vertices from the same class form friendship edges, and all pairs of vertices from different classes form enmity edges.
Moreover, every signed graph which admits such a partitioning is clearly balanced.
In the special case where one of the vertex classes in this partitioning is empty, each pair of vertices forms a friendship edge and we refer to this balanced signed graph as {\em utopia}.

The main interest in the study of social networks modeled by signed graphs is the evolution of the network
according to some pre-specified dynamics, and the time until the balance is reached.
The goal is to understand which simple dynamics ensure fast convergence to balance.
Following the work of~\cite{Antal2006}, we focus on those dynamics that, at each time step, select one edge $e$ according to some rule and then flip its sign.
We then say that ``$e$ is flipped''.
In~\cite{Antal2006}, two such dynamics on signed graphs were introduced:
{\em Local Triad Dynamics (LTD)}, and {\em Constrained Triad Dynamics (CTD)}.
In the rest of this section, we define these two dynamics and discuss their advantages and limitations.

\subsection{Local Triad Dynamics}

Let $G$ be a signed graph modeling a social network with friendships and enmities.

The {\em Local Triad Dynamics (LTD)} with parameter $p\in [0,1]$ is a discrete-time random process that starts in $G$ and repeats the following procedure until there are no imbalanced triads in $G$:
\begin{enumerate}
\item Select an imbalanced triad $\Delta$ uniformly at random.
\item If $\Delta$ is of type $\Delta_3$, then an edge of $T$ is chosen to be flipped uniformly at random.
If $\Delta$ is of type $\Delta_1$,
then the unique edge with sign $-1$ is chosen to be flipped with probability $p$ and each of the two other edges
is chosen with probability $\frac{1-p}{2}$.
\end{enumerate}
We refer to distinct signed graphs as {\em states}.

LTD is socially oblivious in the sense that once an imbalanced triad is selected, the edge to be flipped is chosen according to a (stochastic) rule that disregards the rest of the network.
Moreover, the guarantees of LTD on the expected time to reach a balanced state are not very plausible:
it was shown in~\cite{Antal2006} that if $p < \frac{1}{2}$, then the expected time grows exponentially with the size of the signed graph.
On the other hand, if $p> \frac{1}{2}$, then the dynamics is more likely to create rather than remove friendships and it reaches utopia with high probability.
This means that the eventual balanced state is essentially pre-determined.

\subsection{Constrained Triad Dynamics}

The {\em Constrained Triad Dynamics (CTD)} is another dynamics on signed graphs.
Given a signed graph $G$ on $n$ vertices, CTD is a random process
that starts in $G$ and repeats the following procedure until there are no imbalanced triads in $G$:
\begin{enumerate}
\item Select an imbalanced triad $\Delta$ uniformly at random.
\item Select an edge $e$ of $\Delta$ uniformly at random.
\item Flip $e$ if $r_e \ge \frac{1}{2}n-1$, that is,~if the number of imbalanced triads in $G$ does not increase upon the flip (in the case of equality, the flip happens with probability $1/2$), otherwise do nothing.
\end{enumerate}
Note that CTD introduces a non-local, socially-aware rule: When deciding whether a selected edge should be flipped, we take into account all triads that contain it.
In~\cite{Antal2006} it was claimed that, starting from any initial signed graph $G$,
CTD converges to a balanced state and that balance is reached fast
-- in a time that scales logarithmically with the size $n$ of the signed graph.
If true, this would imply that CTD overcomes the limitation of LTD in which the expected convergence time could be exponential in $n$.
However the claim, which was supported by an informal argument,
is not quite true, since the energy landscape is rugged: There are states, called {\em jammed states}, that are not balanced but where CTD can not make a move, since any flip would (temporarily) increase the number of imbalanced triads~\cite{Antal2005}.
Moreover, it is known that there are at least roughly $3^n$ jammed states (compared to roughly $2^n$ balanced states)
and that some of the jammed states have zero energy~\cite{Marvel2009}.

\section{Reaching and Escaping the Jammed States}\label{sec:ctd}

Even though there are exponentially many jammed states,
computer simulations on small populations were used to suggest that they can effectively be ignored~\cite{Antal2005}.
In contrast, in this section we present three results which indicate that for large population sizes the jammed states are important.

First (``counting''), we study the number of jammed states.
It is known~\cite{Antal2005}, that there are at least $3^n$ jammed states, that is, at least exponentially many.
Here we construct a family of simple, previously unreported jammed states and we show that
the total number of jammed states on $n$ labeled vertices is super-exponential, namely at least $2^{\Omega(n\log n)}$.
This shows that even on the logarithmic scale,
the jammed states are substantially more numerous than the balanced states (of which there are ``only''~$2^{n-1}$).

Our second result (``reaching'') shows that, starting from any initial signed graph that is not too friendship-dense,
a specific jammed state $J$, which we construct below, is reached with positive probability.
In particular this implies that the expected time to balance in this stochastic process is formally infinite,
even for signed graphs that have a constant positive \new{density of friendship edges}.

Our third result (``escaping'') shows that this specific jammed state $J$ forms a deep well in the energy landscape:
Once it is reached, it can not be escaped even if we perturb a constant portion of edges incident to each vertex.

In the rest of this section, we sketch the intuition behind these results.
For the formal statements and proofs, see~\cref{thm:counting,thm:reaching,thm:escaping} in~\cref{app:ctd}, respectively.

Regarding the first result (``counting''), the new jammed states are defined in terms of an integer parameter $d$.
We partition the population into $4d+2$ clusters ($4d+1$ or $4d+3$ would work too), arrange the clusters along a circle,
and assign a sign $+1$ to those (and only those) edges that connect individuals who live in clusters that are at most $d$ steps apart, see~\cref{fig:counting}.
We then show that, for each friendship or enmity edge $(u,v)$, a strict majority $2(d+1)>\frac12(4d+3)$ of clusters have the property
that any vertex $w$ in that cluster forms a balanced triad $(u,v,w)$ with $(u,v)$.
Thus, flipping $(u,v)$ would increase the number of imbalanced triads.
When all the clusters are roughly equal in size, which is the typical behavior for large population sizes, the state is thus jammed.
Our construction also resolves in affirmative an open question~\cite{Marvel2009} which asks whether there exist jammed states with an even number of friendship cliques (here this number is $4d+2$).

\begin{figure}[h]
\includegraphics[width=\linewidth]{fig2-counting.pdf}
\caption{A jammed state consisting of $4d+2$ roughly equal clusters, each connected by friendships to the clusters at most $d$ steps apart.}
\label{fig:counting}
\end{figure}

Regarding the second result (``reaching''),
we consider any initial state $I_n$ on $n$ vertices in which each vertex is incident to at most $n/12-1$ edges labeled $+1$.
We define a jammed state $J_n$ as follows: We partition the vertices into three clusters $V_1$, $V_2$, $V_3$ of roughly equal size,
label all edges within each set $+1$ and all other edges $-1$.
Then we exhibit a sequence of flips that transforms $I_n$ into $J_n$. This is done in two phases:
First, one can verify that any time we select an imbalanced triangle that contains an edge labeled $-1$ within one cluster $V_i$, this edge can be flipped.
Hence, we may flip all enmity edges within the three clusters to reach a state in which all edges within each $V_i$ are labeled $+1$.
After that, one can similarly verify that all edges labeled $+1$ that connect vertices in two different parts $V_i$, $V_j$ can be flipped one by one, thereby reaching the jammed state~$J_n$, see~\cref{fig:reaching}.

\begin{figure}[h]
\includegraphics[width=\linewidth]{fig3-reaching.pdf}
\caption{A jammed state $J_n$ (right) on $n$ vertices can be reached from any not too friendship-dense initial state $I_n$ (left). Moreover, once it is reached, it can not be escaped, even if a substantial portion of edges around each vertex are perturbed.}
\label{fig:reaching}
\end{figure}

Regarding the third result (``escaping''),
we consider any state $S_n$ that can be obtained from $J_n$ by flipping a set $E_0$ of edges such that each vertex is incident to at most $n/12-1$ edges of $E_0$.
We then show that edges that do \textit{not} belong to $E_0$ can never be flipped.
On the other hand, each edge that does belong to $E_0$ can be flipped.
Thus all edges in $E_0$ are eventually flipped back and the jammed state $J_n$ is reached again.

\section{Best Edge Dynamics}

Our results in the previous section show that the jammed states are a profound feature of the energy landscape:
They are reachable from many conceivable initial states,
and some of them trap stochastic dynamics such as CTD forever even if we allow substantial perturbations.

This brings up a question of whether there exists a simple socially-aware dynamics with all the desirable properties of CTD, but one that can not get stuck in a jammed state.
To address this question, we propose the {\em Best Edge Dynamics (BED)}, a modification of CTD that, unlike CTD, reaches a balanced state with probability $1$ from every initial state.
Moreover, we prove that BED converges fast to a balanced state in several important cases (see~\cref{prop:red-fast,prop:jammed-fast}),
and our empirical evaluation of both BED and CTD in Section~\ref{simulation_results} shows that in general the convergence times are comparable (after we exclude the runs where CTD does not terminate).

Let $G$ be a signed graph. Then the {\em Best Edge Dynamics (BED)} is a discrete-time random process
that starts in $G$ and repeats the following procedure until there are no imbalanced triads in $G$:
\begin{enumerate}
\item Select an imbalanced triad $\Delta$ uniformly at random.
\item Select an edge $e$ from $\Delta$ with the highest rank $r_e$ (in case of ties, pick one such edge uniformly at random).
\item Flip $e$.
\end{enumerate}

Note that, in contrast to CTD, we flip $e$ even when its rank $r_e$ satisfies $r_e<\frac12|V|-1$, that is, when flipping the best edge creates more imbalanced triads than it removes.
In particular, whenever we reach a jammed state, we still make a flip.
In principle, it could still happen that BED remains trapped in a subset of imbalanced states,
toggling edges back and forth unable to escape it,
but in fact we prove that this event occurs with probability 0.

\begin{theorem}\label{thm:bedprob1}
For any initial signed graph on $n$ vertices, BED reaches a balanced state with probability $1$ and in finite expected time.
\end{theorem}

To prove~\cref{thm:bedprob1}, we will show that any signed graph on $n$ vertices can become balanced upon $\mathcal{O}(n^3)$ flips.
This suffices since BED induces a finite Markov chain over the set of all states, and the absorbing states of the Markov chain are precisely the balanced signed graphs.

Fix an edge $(v_1,v_2)$ in $G$ of the lowest rank, and set $B=\{v_1,v_2\}$.
Note that it is possible to flip one edge in each imbalanced triad containing $(v_1,v_2)$ without flipping $(v_1,v_2)$ itself, to make all triads containing $(v_1,v_2)$ balanced:
Indeed, if we consider an imbalanced triad containing $v_1$, $v_2$ and some third vertex $w$, as BED flips an edge of the highest rank, it can flip either $(v_1,w)$ or $(v_2,w)$. This makes the triad balanced and decreases $r_{(v_1,v_2)}$ by $1$, while decreasing the rank of any edge that hasn't been flipped by at most $1$. Hence, $(v_1,v_2)$ will still be of the lowest rank in all imbalanced triads containing it, so we can flip one edge in each such triad until all triads containing $(v_1,v_2)$ become balanced.

The rest of the construction proceeds inductively by adding a new vertex to $B$ in each step and making all triads which contain an edge with endpoints in $B$ balanced.
The process ends when all vertices of $G$ have been added to $B$. For the inductive step, suppose that every triad containing at least two vertices in $B$ is balanced.
Let $(v,w)$ be an edge in $G$ which is of lowest rank among all edges with $v\in B$ and $w\not\in B$.
Each triad containing $w$ and two vertices in $B$ is balanced.
On the other hand, since $(v,w)$ is an edge of lowest rank among all edges with $v\in B$ and $w\not\in B$,
it follows that for each imbalanced triad $\Delta$ containing $v$, $w$ and a third vertex $u$,
BED can flip either $(w,u)$ or each edge $(v',u)$ with $v'\in B$ to make $\Delta$ and all other triads containing $u$ and two vertices in $B$ balanced.
By doing this for each imbalanced triad containing $(v,w)$, we modify the signs in the graph in such a way that all triads containing at least two vertices in $B\cup \{w\}$ become balanced. Thus we can add $w$ to $B$. By induction on the size of $B$, this way we eventually reach a balanced state.

Notice that in each iteration of the above construction, at most $n\cdot |B|$ edges are flipped. Hence the total number of edge flips is at most $n\sum_{i=1}^ni=\mathcal{O}(n^3)$ as claimed.

\subsection{Fast convergence and red-black graphs}

So far we have shown that, unlike CTD, BED ensures convergence to balance with probability $1$ and in finite expected time.
In the rest of this section we show that BED also provides theoretical guarantees on fast convergence when started in certain states that are either ``close'' to being balanced (\cref{prop:red-fast}) or jammed (\cref{prop:jammed-fast}), showing that this new dynamics is robust.

We start by introducing the {\em red-black graphs},
a new concept that allows neat reasoning about signed graphs that are close to being balanced.
Given a signed graph $G$, let $C$ be a balanced signed graph on the same number of vertices which differs from $G$ in the smallest number of edge signs.
We refer to $C$ as a {\em closest} balanced state to~$G$.
Then the red-black graph $R$ associated to $G$ and $C$ is obtained from $G$ by
coloring each edge of $G$ in black if the signs of the edge in $G$ and $C$ agree,
and in red otherwise.
Thus, red edges are precisely those edges whose signs in $G$ and $C$ are misaligned.
Figure~\ref{figure:redBlack} shows an example of a signed graph and the corresponding red-black graph.

\begin{figure}[h]
\includegraphics[width=\linewidth]{fig4-red-black.pdf}
\caption{An example of a signed graph (left) and the corresponding red-black graph (right).
}
\label{figure:redBlack}
\end{figure}

The key property of red-black graphs is that red and black edges can be viewed as enmities and friendships when reasoning about balanced triads in the following sense: A triad in $G$ is imbalanced if and only if exactly $1$ or $3$ of its edges are red in $R$.
The proof of this claim is by casework and is deferred to Appendix~\ref{app:redblack}, see~\cref{lemma:redblack}.
This also implies that the rank of an edge in $G$ is equal to its rank in $R$ if we treat red edges in $R$ as enmities and black edges as friendships.

\subsection{Fast convergence around balanced states}\label{sec:fast-balanced}

We are now ready to study the convergence of BED when started in a signed graph which is close to being balanced.

\begin{proposition}\label{prop:red-fast}
Consider a signed graph $G$ whose red-black graph $R$ satisfies one of the following two conditions:
\begin{enumerate}
\item Each vertex is incident to at most $\frac14n-1$ red edges.
\item There are at most $\frac12n$ vertices incident to a red edge.
\end{enumerate}
Then BED reaches a balanced state in $\mathcal{O}(n^2)$ steps in the worst case.
\end{proposition}

To prove the proposition, it suffices to show that BED flips only red edges:
Since in total there are $\mathcal{O}(n^2)$ red edges, BED reaches a balanced state in $\mathcal{O}(n^2)$  steps.

Consider the imbalanced triad $(u,v,w)$ selected by BED.
If the triad contains $3$ red edges, clearly BED flips a red edge.
Otherwise, from the key property of red-black graphs (\cref{lemma:redblack}) we know that the triad contains exactly $1$ red edge.
Without loss of generality suppose $e=(u,v)$ is the red edge.
For each of the two conditions in~\cref{prop:red-fast} we argue separately:
\begin{enumerate}
\item Since $(v,w)$ is a black edge, any triad containing $(v,w)$ is imbalanced if it contains precisely $1$ red edge.
There are at most $\frac{1}{2}n-2$ such triads, since there are at most $\frac{1}{4}n-1$ red edges incident to $v$ and similarly at most $\frac{1}{4}n-1$ to $w$. Thus, $r_{(v,w)}\leq \frac{1}{2}n-2$.
Analogously $r_{(u,w)}\leq \frac{1}{2}n-2$. On the other hand, as $(u,v)$ is red, a triad containing $(u,v)$ which is balanced has to contain exactly two red edges.
So $(u,v)$ is contained in at most $\frac{1}{2}n-2$ balanced triads by the same argument as above, and
$r_{(u,v)} \geq n-2 - (\frac{1}{2}n-2)=\frac{1}{2}n$.
Thus
\[r_{(u,v)} > \max\{r_{(u,w)},r_{(v,w)}\},\]
so BED will flip the red edge.

\item By assumption, we can partition the vertices of $G$ into two sets $V_1$ and $V_2$ such that
$|V_1| \ge |V_2|$ and all red edges have both endpoints in $V_2$.
Then any triad $(u,v,w')$ with $w'\in V_1$ contains exactly~$1$ red edge and is imbalanced, so $r_e\geq |V_1|$.
On the other hand, as $(u,w)$ is black, for any third vertex contained in $V_1$ the triad is balanced,
so $r_{(u,w)}\leq |V|-2-(|V_1|-1)=|V_2|-1<|V_1|$.
Analogously $r_{(v,w)}<|V_1|$, so $e$ has the highest rank in $(u,v,w)$ and BED flips $e$.
\end{enumerate}

\subsection{Fast convergence from jammed states}

Recall that a state is jammed if it is not balanced but CTD cannot flip an edge in any imbalanced triad.
Here we show that from certain jammed states, BED converges to a balanced state after $\mathcal{O}(n^2)$ edge flips, in expectation.
Thus, BED ensures fast convergence even when the convergence time of CTD is infinite.
(For details, see Appendix~\ref{app:fastbedstuck},~\cref{prop:jammed-fast}.)

As before, consider the jammed state $J_n$ consisting of three large roughly equal clusters of friends on $n$ vertices in total.
\cref{fig:Jn-fast} illustrates that, started from $J_n$, BED converges to balance in $\mathcal{O}(n^2)$ time.
Initially, BED keeps adding friendship edges connecting different clusters.
Due to random fluctuations, the symmetry among the three clusters breaks and
one pair of clusters becomes more densely connected than the other pairs.
This difference is exaggerated over time and eventually that pair of clusters merges.

\begin{figure}[h]
\includegraphics[width=0.5\linewidth]{fig5a-Jn-fast-left.pdf}%
\includegraphics[width=0.5\linewidth]{fig5a-Jn-fast-right.pdf}
\caption{
Left: Started from $J_n$, BED reaches balance in $\mathcal{O}(n^2)$ expected steps.
Right: Friendship densities in different portions of the signed graph $J_{100}$, in a single run of BED.
Apart from possibly the very end, the friendships within clusters ($aa$, $bb$, $cc$) are never flipped.
Eventually, one pair of clusters (here $a$ and $b$) merges.
}
\label{fig:Jn-fast}
\end{figure}

Next, we consider a state $J'_n$ whose $n$ vertices are split into 6 clusters
 arranged along a circle with relative sizes roughly $2:1:1:2:1:1$.
Two vertices are connected by a friendship edge if they belong to the same cluster or to adjacent clusters (see~\cref{fig:bed-jammed}, left).
The different cluster sizes ensure that the symmetry is broken from the very beginning and allow for a simpler formal argument.

\begin{figure}[h]
\includegraphics[width=\linewidth]{fig5-bed-jammed.pdf}
\caption{A jammed state $J'_n$ from which BED reaches a balanced state in $\mathcal{O}(n^2)$ expected steps.
}
\label{fig:bed-jammed}
\end{figure}

It is straightforward to check that the state $J'_n$ is jammed and that the closest balanced state $C$ is
the one depicted in the left figure. The corresponding red-black graph is shown on the right.
Let $E_0$ be the set of edges that are initially red in the red-black graph.
We show that the process always flips an edge $e\in E_0$
and that, at each point in time, we are a constant-factor more likely to turn a red edge into a black one rather than the other way around.
Thus the stochastic process can be projected onto a random walk with a constant forward bias.
Since such a random walk terminates in the number of steps that is linear in its length,
this proves that the process finishes in $\mathcal{O}(|E_0|)=\mathcal{O}(n^2)$ steps in expectation.

\new{\section{Computer Simulations}\label{simulation_results}}
\new{In this section, we compare the two dynamics CTD and BED by means of computer simulations.
In each simulation, we generate a network (possibly randomly) and assign ``$+$'' to each its edge.
All other edges are assigned ``$-$'', so the underlying network is always a complete graph.
Then we simulate each dynamics to determine the quantities such as the typical outcome and the number of steps until it reaches balance.}

\smallskip
\subsection{Erd\H{o}s-R\'{e}nyi graphs}
\def\operatorname{ER}{\operatorname{ER}}
First we consider random Erd\H{o}s-R\'{e}nyi graphs $\operatorname{ER}(n,p)$, where each two of the $n$ vertices are connected by a friendship edge with probability~$p$, independently of each other.

Since CTD can get jammed, the average number of steps until it reaches balance is infinite for many initial states.
To have a meaningful comparison, we first exclude runs in which CTD gets jammed (later we report their proportion).
Upon this exclusion, the two dynamics are comparable.
First, the number of steps until balance for both dynamics scales as $\Theta(n^2)$ with the population size $n$, see~\cref{figure:stepsPlot}.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.8\linewidth]{stepsPlot_ER-ipe.pdf}
    \caption{Average number of steps until balance for CTD (excluding the runs that get jammed) and BED, over $10^5$ runs.
    The friendships in the initial signed graphs form the Erd\H{o}s-R\'{e}nyi graph with edge probability $p = \frac12$ and size $n\le 400$.
    Both quantities scale as $\Theta(n^2)$.
    }
    \label{figure:stepsPlot}
  \end{center}
\end{figure}

\new{Second, the final configuration does not depend on the choice of the dynamics
but it is strongly dependent on the parameter $p$.
Namely, for $p\le 0.5$ the two cliques are almost always roughly equal in size,
whereas for $p\ge 0.6$ the larger clique contains almost all the vertices, see~\cref{figure:like_6}.
(See also~\cref{app:table} for tables showing several network descriptors before and after the network becomes balanced.)}

\begin{figure}
  \begin{center}
    \includegraphics[width=0.5\linewidth]{like_6_bed.pdf}%
    \includegraphics[width=0.5\linewidth]{like_6_ctd.pdf}
    \caption{\new{Distribution of the relative difference of the clique sizes once balance is reached,
    for BED (left) and CTD (right) over $10^5$ runs. Here $n=128$.}
    }
    \label{figure:like_6}
  \end{center}
\end{figure}

Next we focus on the probability that CTD gets jammed.
For fixed $n$, this probability exhibits a threshold behavior as a function of the friendship density $p$, see~\cref{figure:vary_p}.
The intuition is as follows:
When the initial friendship density is large (here $p\ge 0.6$), then the initial state is close to utopia (the balanced state that consists of only friendships).
Utopia is then reached quickly and with high probability (cf.~\cref{sec:fast-balanced}).
When the initial friendship density is small (here $p\le 0.5$), the jamming probability is nonzero (cf.~\cref{sec:ctd}).
Most imbalanced triads are of type $\Delta_3$ (all enmities).
The dynamics thus keeps adding friendship edges and the jamming probability is mostly independent of $p$.
The same phenomenon occurs for other sizes $n$, see~\cref{figure:probabilityPlot}.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.8\linewidth]{probabilityDiffp_ER.pdf}
    \caption{The jamming probability for CTD,
    when friendships form an Erd\H{o}s-R\'{e}nyi graph with size $n=250$ and edge density $p\in[0,1]$
    exhibits a threshold behavior.
}\label{figure:vary_p}
  \end{center}
\end{figure}

\begin{figure}
  \begin{center}
    \includegraphics[width=0.8\linewidth]{probabilityPlot_ER.pdf}
    \caption{The jamming probability for CTD, when friendships form an Erd\H{o}s-R\'{e}nyi graph with size $n\le 400$ and edge density $p\in\{0,0.5,0.6,0.75\}$.
    When $p\ge 0.75$ (or $p\ge 0.6$ and $n$ large), the dynamics typically reaches utopia, otherwise there is a non-negligible probability of reaching a jammed state.
    }\label{figure:probabilityPlot}
  \end{center}
\end{figure}

\subsection{Scale-free networks}
\def\operatorname{BA}{\operatorname{BA}}
Apart from Erd\H{o}s-R\'{e}nyi graphs we also consider the Barab\'asi-Albert model $\operatorname{BA}(n,d)$ for scale-free networks~\cite{Barabasi1999}.
This model creates a scale-free graph with edge density $d\in[0,1]$.
In particular, we start with a path on $11$ vertices and then process the remaining $n-11$ vertices one by one.
When processing a vertex $v$, we randomly connect it to a subset of vertices already present in the network in such a way that
the probability that a pair $uv$ forms a (friendship) edge is proportional to the degree of $u$ (``preferential attachment'') and the resulting (expected) edge density equals $d$.

Compared to Erd\H{o}s-R\'{e}nyi graphs, the degrees of the vertices are unequally distributed.
Despite this difference, the number of steps until balance for both CTD and BED still scales as $\Theta(n^2)$ with the size $n$, see~\cref{figure:BA_steps}.
Moreover, the jamming probability for CTD still exhibits a similar threshold behavior, see~\cref{figure:BA_probability_density,figure:BA_probability}.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.8\linewidth]{stepsScaleFreePlot-ipe.pdf}
    \caption{Average number of steps until balance for CTD (excluding the runs that get jammed) and BED, over $10^5$ runs.
    The initial signed graphs are Barab\'asi-Albert with degree parameter $d = 0.5$ and size $n\le 400$.
    Both quantities scale as $\Theta(n^2)$.
    }\label{figure:BA_steps}
  \end{center}
\end{figure}

\begin{figure}
  \begin{center}
    \includegraphics[width=0.8\linewidth]{probabilityScaleFreeDensities.pdf}
    \caption{The jamming probability in CTD,
    for Barab\'asi-Albert networks with size $n=250$ and parameter $d\in[0,0.7]$
    exhibits a threshold behavior comparable to Erd\H{o}s-R\'{e}nyi graphs, but with significantly lower edge density.
    }\label{figure:BA_probability_density}
  \end{center}
\end{figure}

\begin{figure}
  \begin{center}
    \includegraphics[width=0.8\linewidth]{probabilityScaleFreePlot.pdf}
    \caption{The jamming probability in CTD, for Barab\'asi-Albert networks with size $n\le 400$ and parameters $d\in\{0.0, 0.3, 0.5,0.7\}$.
    }\label{figure:BA_probability}
  \end{center}
\end{figure}

\section{Summary and Discussion}

The theory of structural balance provides a rigorous framework for the study of friendships and enmities in a population.
A central concept in this theory has been the energy landscape of networks, and particularly the energy properties of its local minima.
In this paper we have taken a closer look at the properties of these local minima with respect to the stochastic process, addressing questions regarding their reachability and attractor properties.
We have shown that there are super-exponentially many jammed states, as opposed to the exponentially many balanced states,
and that any initial state that is not too friendship-dense can reach a jammed state.
Moreover, such jammed states are attractors, and hence cannot be escaped by random perturbations of the network.
These findings have strong implications for the socially-aware CTD process, which in fact gets stuck in such jammed states.

Motivated by these rich reachability and attractor properties of jammed states, we have introduced
the plausible socially-aware dynamics BED.
We have shown that BED does not get stuck in jammed states and that it always reaches balance.
Moreover, we have seen that BED converges fast from many interesting states, such as those that are not too far from balance.

The new BED dynamics spawns some natural questions regarding its asymptotic behavior.
Although we have shown that BED converges fast (in $\mathcal{O}(n^2)$ time) to balance from any state that is suitably close to balance, the general convergence rate remains open.

\new{An assumption made throughout our work is that the underlying network is complete.
That is, at each point in time, every two individuals have a defined relationship (they are either friends or enemies).
It is natural to consider non-complete underlying networks $U$, where only those pairs of individuals who are connected by an edge $e\in U$ have a defined relationship.
We note that this generalized setting is considerably more complicated.
First, one needs to adapt the notion of balance accordingly.
One way to do this is to say that a state is balanced if all cycles are balanced, where
a cycle in $U$ is balanced if it contains an even number of edges labeled ``$-$''.
While checking whether a current state is balanced can be done efficiently~\cite{harary1980simple},
several fundamental problems remain.
For instance, computing the distance to the closest balanced state is known to be intractable~\cite{Facchetti2011}.
As another example, to our knowledge the balanced states do not have any simple structure and even the complexity of computing their number (for a given non-complete underlying network $U$) is open.
As a final illustration, we note that there exist ``blinkers''~\cite{Antal2005}, that is,
states where CTD and BED get stuck repeating moves back and forth (rather than getting stuck being unable to make a move), see~\cref{figure:blinker}.
(Note that when the underlying network is complete, there are no blinkers for BED due to~\cref{thm:bedprob1}.)}
Investigating the properties of BED adapted to such generalized settings is thus left as an interesting direction for future research.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.8\linewidth]{fig-blinker.pdf}
    \caption{\new{A blinker. Under both CTD and BED, the thick edge in the middle keeps toggling between friendship (blue) and enmity (red) indefinitely. There is always only one imbalanced triangle (shaded) and flipping any other its edge would create more imbalanced triangles.}
    }\label{figure:blinker}
  \end{center}
\end{figure}

\section*{Acknowledgments}
K.C. acknowledges support from ERC Start grant no. (279307: Graph Games), ERC
Consolidator grant no. (863818: ForM-SMart), and Austrian Science Fund (FWF) grant no.
P23499-N23 and S11407-N23 (RiSE).
This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385.

All authors conceptualized the work.
A.P, J.S., and J.T. wrote the manuscript.
J.S. and J.T. produced the figures.
J.S. implemented the computer simulations.

\clearpage


\section{Introduction}

A common approach to control from images is to collect demonstrations of task success and train a behavioral cloning (BC) agent \cite{Pomerleau1988ALVINNAA, ahn2022can, jang2022bc}. This can lead to policies that are able to succeed on many tasks, particularly when mistakes do not cause the policy to move too far from the distribution of state-action transitions seen in the dataset of successful demonstrations.
But, for many tasks (like T-shirt grasping) a mistake will take the policy out of this distribution and then the learned BC policy will fail to recover \cite{ross2011reduction}.

Such failures occur in part because a dataset of only successes does not contain enough information to recognize failures or learn recovery behaviors. To remedy this issue, we propose a novel data collection method called Visual Backtracking Teleoperation (VBT). Specifically, VBT leverages the teleoperator to collect visually similar failures, recoveries, and successes as seen in Fig. \ref{fig:vbt-vertical}.

VBT data collection is designed to combine well with offline reinforcement learning (OffRL) rather than BC. VBT data contains the necessary coverage of the state action space to learn accurate value functions as well as recovery behaviors. Then OffRL can leverage sparse rewards to automatically emulate the advantageous actions (including recovery behaviors) while avoiding the sub-optimal actions that led to the initial task failure.

It is crucial to the VBT method that the failures, recoveries, and successes are visually similar. Without this visual similarity, the OffRL learner can overfit to non-task-relevant elements of the image such as background clutter, leading to useless value functions. To easily maintain visual similarity, VBT collects each of failure, recovery, and success \emph{within} the same trajectory (Fig. \ref{fig:vbt-vertical}). Thus, VBT avoids overfitting, even on small, image-based datasets, by ensuring that differences between observations of failure and success are task-relevant.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{images/VBT-approach-vertical.pdf}
    \caption{An illustration of our VBT method on a T-shirt grasping task. The method asks the teleoperator to demonstrate failure (red), recovery (blue), and success (green) within each trajectory. This provides the necessary coverage of failure and recovery to learn accurate value functions and robust policies while also preventing overfitting by ensuring that failures and successes are visually similar except for the task-relevant details.}
    \label{fig:vbt-vertical}
\end{figure}

Concretely, our contributions are:
\begin{enumerate}
    \item We propose the novel VBT protocol for data collection to leverage human teleoperation to collect image-based datasets for use with OffRL. VBT resolves the two main issues with naive methods: (a) lack of coverage of failures and recoveries and (b) overfitting caused by visually dissimilar failures and successes.
    \item We discuss how and why VBT can enable better policy learning via learning more accurate $Q$ functions and present empirical evidence of the improvement in $Q$ functions learned from VBT data compared to several baselines for data collection.
    \item We present real robot results on a deformable grasping task to demonstrate the effectiveness of VBT data. When training from scratch on just one hour of robot time for data collection and image-based observations, a policy trained with OffRL on VBT data succeeds 79\% of the time while BC trained on successful demonstrations has a success rate of 66\%.
\end{enumerate}

\section{Related Work}

Our work falls into the broader category of learning from demonstrations \cite{schaal1996learning}. But, rather than taking a more traditional approach of BC from demonstrations of success \cite{Pomerleau1988ALVINNAA, ahn2022can, jang2022bc, argall2009survey}, we propose a novel method for collecting demonstrations of failure and recovery as well as success. The inclusion of failures in our dataset leads us to use OffRL \cite{levine2020offline, fujimoto2019off} to ensure that we do not imitate the failures. Specifically, we use the IQL \cite{kostrikov2021offline} and AWAC \cite{nair2020awac} algorithms for OffRL. Some theoretical motivation for the use of OffRL rather than BC when learning from suboptimal data can be found in \cite{kumar2021should}.

The insight that observations of failures is useful for policy learning has been made before in work on using success detectors to compute rewards in RL \cite{kalashnikov2021mt}. In contrast, VBT does not attempt to learn an explicit success detector, but provides a mechanism for collecting data that is especially useful for learning policies by capturing the salient differences between failure and success in visually similar observations.

While we consider a setting where training happens entirely offline (i.e., the data collection step is separated from the policy learning), there is a related line of work that collects examples of failures and recoveries by moving to an interactive setting where actions from partially trained policies are executed on the robot and judged by the human teleoperator. In particular the DAgger line of work exemplifies this pattern \cite{ross2011reduction, kelly2019hg, Mandlekar2020HumanintheLoopIL, hoque2021lazydagger, hoque2022fleet}. In contrast, VBT operates completely offline and does not require the teleoperator to interact with the learning process or to deploy learned policies on the robot during training.

VBT also is particularly suited to efficiently learn image-based value functions for sparse reward tasks. This capability could be especially useful in architectures like SayCan \cite{ahn2022can} that require image-based affordances for a variety of manipulation tasks, and it is an interesting direction for future work to use VBT as a component in training such larger systems.

\section{Motivation}\label{sec:motivation}

VBT is designed to solve two issues that arise from simpler data collection methods: (1) lack of coverage of failure and recovery behaviors, and (2) overfitting issues that arise in the low-data and high-dimensional observation setting. Here we describe both of these issues in more detail before explaining how VBT resolves them.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{images/VBT-gridworld-2.png}
    \caption{An illustration of each of the four types of datasets that we consider in a gridworld environment with a sparse reward for reaching the green goal. The Success Only dataset contains two successful trajectories. The Coverage+Success and LfP+Success datasets each contain one success and one failure. Our VBT dataset contains one trajectory that fails, then recovers, and then succeeds.  Full descriptions of the datasets are in Section \ref{sec:setup}.}
    \label{fig:gridworld}
\end{figure}

\subsection{Lack of coverage of failure and recovery}

Any offline learning algorithm will be fundamentally limited by the quality of the dataset.
We can only expect the algorithm to reproduce the best behaviors in the dataset, not to reliably extrapolate beyond them. So, when collecting datasets for offline learning of value functions and policies, we want to ensure sufficient coverage of the relevant states and actions. We argue that for sparse reward robotics tasks this requires including failures and recoveries in the dataset.

\textbf{Value functions require coverage.} Most OffRL algorithms involve estimating the $ Q $ and $V $ value functions of a learned policy $ \pi$ that is different from the policy (in our case the teleoperator) that collected the dataset.
Explicitly, letting $ \gamma \in [0,1)$ be a discount factor and $ r $ be the reward function they estimate $ Q^\pi(s,a) = \mathbb{E}_{\pi}[\sum_{t=0}^\infty \gamma^t r(s_t, a_t) | s_0=s, a_0=a]$ and $ V^\pi(s) = \mathbb{E}_{a\sim \pi|s}[Q^\pi(s,a)]$, where expectations are taken over actions sampled from $\pi$.
For the rest of the paper we will omit the superscript $ \pi$ when clear from context.

The key issue with learning value functions for a policy $ \pi $ that did not collect the data is that we can only reliably estimate value functions at states and actions that are similar to those seen in the training set \cite{levine2020offline}. This is born out by theoretical work which often requires strong coverage assumptions to learn accurate value functions, such as assuming that the data distribution covers all reachable states and actions \cite{chen2019information}.

While this sort of assumption is too strong to satisfy in practice, we argue that for the sparse reward robotic tasks that we consider, the relevant notion of coverage is to include failures and recoveries, as well as successes, in the dataset. These failures and recoveries can provide coverage of the task-relevant states and behaviors necessary to learn useful value functions.
Without failures the learned value functions will not be able to identify the ``decision boundary'' between failure and success that is necessary for reliably accomplishing the specified task. Much as in supervised learning it is difficult to train a binary classifier without any examples of the negative class, we conjecture that it is difficult to learn accurate $Q$ functions for sparse reward tasks without any failures.

Consider the example datasets shown in Fig. \ref{fig:gridworld}. If we use the Success Only dataset to train a $Q$ function and then query the $Q$ function at the location of the red agent during evaluation we will get inaccurate $Q$ values. The learned $Q$ function does not have any indication that the presence of the wall between the agent and the goal exists since there is no training data from the left side of the wall. In contrast, any of the other datasets that contain failure examples where the agent enters the room to the left of the wall will allow the learned $Q$ function to assign lower values to states left of the wall compared to those right of the wall.

\textbf{Policies require coverage.} Much as with value functions, learned policies should not be expected to produce behaviors that are not present in the training set. This can be seen by looking at the policy loss function used in OffRL algorithms like IQL \cite{kostrikov2021offline} and AWAC \cite{nair2020awac} which take the following form (where $ \mathcal{D}$ is the distribution that generates the dataset and $ Q, V$ are the learned $Q$ and $V$ value functions):
\begin{align}
    L(\pi) = \mathbb{E}_{s, a\sim \mathcal{D}}[\exp(Q(s,a) - V(s)) \cdot  (-\log \pi(a|s))]
\end{align}
Notice that this is simply the standard negative log likelihood loss that is used for BC, except that each term is weighted by the exponentiated advantage function. This loss leads to policies that imitate actions with high advantages and ignore actions with low advantages. The key takeaway is that OffRL can only produce policies that choose actions that are already covered by the data distribution. So, if we want a robust policy that can recover from failures, we need to see recovery actions in the training set.

Note the DAgger line of work \cite{ross2011reduction} raises a similar issue and resolves it by introducing online learning where the policy $ \pi$ is executed on the system to expand coverage. Instead, we are considering an entirely offline setting where we want to produce the necessary coverage of failure states and recovery behavior a priori from teleoperation.

To see an example of why coverage of failures and recoveries is necessary for robust policy learning, again consider the datasets shown in Fig. \ref{fig:gridworld}. Imagine that at evaluation time, the agent reaches the red triangle. If the agent was trained on the Success Only dataset, it must rely on extrapolation to select an action, but there are never any examples of ``down'' in the dataset. As a result, the agent is stuck in the room to the left of the wall and cannot recover. In contrast, the other datasets may allow for the agent to learn a useful recovery behavior since they have better coverage.

\subsection{Overfitting in the low-data and image observation setting}

When collecting data via teleoperation we are usually in the low-data regime since we are bottlenecked by teleoperator time on the real robot. Moreover, in the tasks that we consider here, the observation space is image-based and thus very high-dimensional. This combination of low-data and high-dimensional observations makes overfitting likely.

As explained above, in sparse reward tasks it is important for the $Q$ functions and policies to accurately represent the ``decision boundary'' between failure and success in the task. In simple observation spaces like the gridworld in Fig. \ref{fig:gridworld}, this may be fairly easy, e.g., as in identifying a failure by recognizing that the $(x,y) $ coordinated of the position are in the room to the left of the wall. However, in high-dimensional image-based observation spaces that are encountered in real robotic tasks, this can become much more challenging.

\begin{figure}[h]
    \centering
    \includegraphics[width=\linewidth]{images/overfitting.png}
    \caption{Datasets that include visually dissimilar successes and failures like Dataset A can cause overfitting. For example, a learned $Q$ function could learn to attend background distractions (like the pen) instead of the task-relevant details. In contrast, in Dataset B the only differences between success and failure are task-relevant.}
    \label{fig:overfitting}
\end{figure}

Fig. \ref{fig:overfitting} illustrates the challenges of image observations in our grasping task. If successes and failures are collected naively in separate episodes (Dataset A), there will be many visual differences between success and failure beyond the salient details about the gripper and shirt. For example, background clutter like the presence of a pen or the exact configuration of the folds of the shirt can spuriously correlate with failure. In contrast, Dataset B reduces the chances of overfitting by eliminating the spurious correlations. Separating the examples in Dataset B requires learning a model that is attuned to the subtle task-relevant visual differences between failure and success that can generalize well. Our method aims to collect data like Dataset B.

\section{Our Method: Visual Backtracking Teleoperation (VBT)}\label{sec:method}

Our main contribution is a novel method for data collection called Visual Backtracking Teleoperation (VBT). This method is particularly suited to collecting small image based datasets. The main idea is that in order to learn useful $Q$ functions and robust policies, we need a dataset that contains failures and recoveries as well as successes. Moreover, when learning from visual inputs we need the failures and recoveries to be as visually similar to the successes as possible to prevent overfitting and to encourage $Q$ functions and policies to use only the task-relevant information in the images.

Explicitly, VBT data collection consists of three steps for the teleoperator \emph{within} each trajectory:
\begin{enumerate}
    \item \textit{Failure:} the teleoperator first fails at the desired task.
    \item \textit{Recovery:} the teleoperator recovers from the failure and begins to attempt the task again.
    \item \textit{Success:} the teleoperator successfully finishes the task.
\end{enumerate}
Then the data is labeled with a sparse reward signal: 1 for the final transition and a small penalty for all other transitions.

VBT is a general recipe that can be applied to any sparse-reward task that has well-defined failure modes and is amenable to teleoperation. The failure modes need not be unique and the data could consist of several different types of failures.

For our example task of deformable grasping these steps can be implemented as depicted in Fig. \ref{fig:vbt-vertical}:
\begin{enumerate}
    \item \textit{Failure:} the teleoperator fails to grasp the shirt and begins to lift the arm.
    \item \textit{Recovery:} the teleoperator opens the gripper and moves the arm back towards the shirt.
    \item \textit{Success:} the teleoperator grasps and lifts the shirt.
\end{enumerate}

Compared to a dataset that contains only demonstrations of success, VBT contains better coverage of failure and recovery behaviors. As explained in Section~\ref{sec:motivation}, this coverage is necessary to learn robust policies capable of recovery and $Q$ functions that can recognize failure.

Compared to a dataset that naively mixes failures and successes that are collected separately, VBT has the benefit of visually similar failures and successes. As explained in Section~\ref{sec:motivation}, this prevents the learned $Q$ functions and policies from overfitting based on visual details that are not task-relevant and instead forces the models to learn the task-relevant features that can generalize better.

\section{Experimental Setup}\label{sec:setup}

\subsection{Robot and Environment}
Our setup consists of a reach-enabled \cite{reach2022pyreach} UR5 arm with a pneumatic powered 3-fingered gripper. We control the robot with a 5 dimensional action space: displacements in $(x,y,z)$ no larger than 5cm, a gripper toggle to either an open or closed position, and a termination indicator that immediately terminates an episode. The orientation of the end-effector is fixed. If the agent does not select the terminate action within 100 steps, we automatically terminate the episode.

The workspace consists of the same blue T-shirt, with various distractor objects and variations in lighting. The robot observation space consists of 2 camera images (360x640x3) from a wrist camera and overhead camera, as well as the Cartesian position of the end-effector $(x,y,z)$ and an indicator of whether the gripper is currently open or closed. We stack a sequence of 4 consecutive timesteps of observations as the input for our learning algorithms.

The task is to lift the T-shirt more than 80\% off a table. During training, as explained in Section \ref{sec:method}, we automatically label each successful trajectory collected by the teleoperator with a terminal reward of 1. We give all other transitions a reward of -0.01 to encourage faster completion of the task. This environment is illustrated in Fig. \ref{fig:mdp}.

\begin{figure}[h]
    \centering
    \includegraphics[width=\linewidth]{images/MDP.png}
    \caption{A description of the observation and actions spaces we use for our real robot experiments. The agent receives an observation of 4 timesteps of images, cartesian coordinates of the end effector, gripper status, and reward from the robot and sends back a 5 dimensional action of cartesian displacements and gripper and terminate commands.}
    \label{fig:mdp}
\end{figure}

\subsection{Datasets}
To understand the performance of VBT, we collect several different baseline datasets of robotic T-shirt grasping by human teleoperators. Each dataset contains 60 minutes of data from the real robot which equates to approximately $ 10,000$ steps in the environment.

\textbf{Success demonstrations (Success)}: The success dataset consists of demonstrations of task success. These episodes demonstrate efficient successful executions of the task with minimal recovery behaviors collected by a human teleoperator instructed to complete the task successfully. The episodes always terminate in success.

\textbf{Visual Backtracking Teleoperation (VBT-Ours)}: Each episode in this dataset demonstrates failure, then recovery, and then task success as described in Section \ref{sec:method}. The visuals of the background, lighting, and positions of scene objects are shared with both optimal behavior, bad behavior, and recoveries. The episodes always terminate in success.

\textbf{Success mixed with failures and recoveries (Coverage+Success)}: This dataset is a mixture of two datasets containing 30 minutes of robot data from each one. The first is the Success dataset described above. The second is a dataset containing repeated failures and recoveries and intended to provide coverage of task-relevant behaviors. This dataset consists of many attempted grasps and retries in quick succession as well as many examples where the shirt is grasped, released, and then attempted to be re-grasped. The goal of this dataset is to provide coverage of failures and recoveries.

\textbf{Success mixed with learning from play (LfP+Success)}: This dataset is also a mixture of two datasets containing 30 minutes of robot data from each one. The first is again the Success dataset. The second is a learning from play \cite{lynch2020learning} dataset which contains data of the robot demonstrating rich interactions such as rolling lifting, dragging, and pushing, between the robot arm and a variety of different objects beyond the T-shirt.

\subsection{Learning algorithms}
We run several different policy learning algorithms to understand utility of our datasets.
\textbf{Behaviour Cloning (BC)} where policy is trained directly to imitate the actions in the dataset.
\textbf{AWAC} \cite{nair2020awac} where an advantaged weighted actor-critic method is used to train both a policy $ \pi $ and critic able to evaluate $V^\pi$ and $Q^\pi$.
\textbf{IQL} \cite{kostrikov2021offline} where implicit Q-Learning is used to train both a policy $ \pi$ and critics $V^\pi$ and $Q^\pi$.

All policies and value functions are parameterized by the same neural architecture and trained using \texttt{JAX} \cite{jax2018github} and \texttt{Flax} \cite{flax2020github}. The image inputs are passed through a ResNet \cite{he2016deep} encoder and then the features are concatenated along with the Cartesian coordinates of the gripper and the gripper indicator (as well as the action for $Q$ functions). These features are then passed through a simple multi-layer perceptron to output either an action or value.

All policies and value functions are trained from 700K gradient steps using the Adam \cite{kingma2014adam} optimizer. During training images are aggressively augmented using changes in brightness, sharpness, color, contrast, artificial shadows, rotation, and cropping. This allows us to train the encoders from scratch on relatively small datasets. We use an inverse temperature of 0.1 for both IQL and AWAC, and we use expectile 0.9 for IQL, following \cite{kostrikov2021offline}.

\section{Experimental Results}

We now present experimental results on our deformable grasping task that attempt to answer the following questions:
\begin{enumerate}
    \item Are $Q$ functions trained on VBT data more accurate than those trained on other datasets? And if so, why?
    \item Are policies trained on VBT data more successful than those trained on other datasets? And if so, why?
\end{enumerate}

\subsection{VBT data leads to improved value functions}

To see the improvement in $Q$ functions when training on VBT data we present examples of the learned $Q$ functions on representative trajectories. From these examples we show that training $Q$ functions on VBT data resolves each of the issues raised in Section \ref{sec:motivation}. Namely, the $Q$ functions trained on VBT data (1) correctly identify failures while those trained on Success data do not and (2) resolve the overfitting issues that can arise when using Coverage+Success data.

\begin{figure}[h]
    \centering
    \includegraphics[width=\linewidth]{images/q-functions-on-double-pick-trajectory.png}
    \caption{Evaluation of various $Q$ functions on a single held out evaluation trajectory that is not seen during training. The trajectory consists of a failure followed by recovery and a successful grasp. The $Q$ functions are trained by running IQL on different datasets (Success, Coverage+Success, LfP+Success or VBT). Notice that the VBT-trained $Q$ function is the only one to drop precisely at the point of the missed grasp instead of the open gripper action that is necessary for recovery.}
    \label{fig:q_functions}
\end{figure}

First, we will show how $Q$ functions trained on VBT data correctly identify failures and recoveries. To do this we illustrate the $Q$ functions trained on Success, Coverage+Success, LfP+Success and VBT data on a single trajectory that contains failure, recovery, and success in Fig. \ref{fig:q_functions}.
As explained in Section \ref{sec:motivation}, the Success dataset does not provide sufficient information to understand failures. As a result, the $Q$ function trained on Success does not use the image observation to recognize failure. Instead it uses the proprioceptive state to correlates ``gripper closed and moving up'' with higher values \emph{regardless of whether the shirt is in hand}. Training on VBT data resolves this issue by forcing the $Q$ function to attend to the information in the image to recognize when a failure has occurred. As a result, the $Q$ function trained on VBT drops dramatically precisely when the missed grasp happens.

To ensure that these results generalize beyond this single trajectory, we compute averages of the relevant value functions across a held-out test of VBT-style trajectories. The results are shown in Fig. \ref{fig:values}. Each trajectory contains three gripper toggles: is a missed grasp, an open gripper recovery behavior, and a successful grasp. The key observations are that as in Fig. \ref{fig:q_functions}, the value functions trained on VBT correctly identify that the $Q$ value of the missed grasp is substantially lower than the $V$ value of the state from which the grasp occurs. This means that the OffRL algorithms using these value functions will correctly learn to avoid missed grasps.
In contrast, training on any of the baseline datasets leads to $Q$ values that are above the $V$ value for the missed grasp (meaning they will learn to miss). And similarly, training IQL on the baseline datasets yields $Q$ values for the recovery behavior that are substantially below the $V$ values while training on VBT does not.

\begin{figure}[h]
    \centering
    \includegraphics[width=\linewidth]{images/vals_on_double_test.png}
    \caption{Visualization of the average $Q$ and $V$ values at each of the three key steps highlighted in Fig. \ref{fig:q_functions} across a held-out test set of 35 trajectories. Error bars show standard error. Note that VBT has much lower $Q$ than $V$ for the missed grasp, while the baseline datasets have much lower $Q$ than $V$ for the open gripper, meaning the VBT value functions are more accurate.}
    \label{fig:values}
\end{figure}

The above results indicate that the Coverage+Success does not resolve the coverage issues that are preventing us from learning accurate $Q$ functions. This may be somewhat surprising since this dataset was designed to have good coverage.
We claim that this issue is due to overfitting in our low-data and high-dimensional observation setting.
Essentially, the $Q$ function trained on Coverage+Success data uses the image observation to classify the trajectory as either ``success'' or ``failure''. If the trajectory is classified as ``success'' then the $Q$ function behaves just like a $Q$ function trained only on Success and associates ``gripper closed and moving up'' with higher $Q$ values. However, if the trajectory is classified as ``failure'' then the $Q$ function trained on Coverage+Success data behaves differently and assigns uniformly lower $Q$ values to the trajectory.
Some hint of this can be seen in Fig. \ref{fig:values} where the values learned on Coverage+Success have substantially higher variance caused by some of the trajectories being classified as failures (note that LfP+Success behaves much more like Success alone since the classification problem between the two datasets is easy enough that the LfP data is completely ignored).

\begin{figure}[h]
    \centering
    \includegraphics[width=\linewidth]{images/overfitting-histogram.png}
    \caption{Histograms of the $Q$ values of IQL trained on Coverage+Success (Top) and VBT (Bottom) on both the data that the respective $Q$ functions were trained on (Left) and held out test sets from the same distribution (Right). The $Q$ function trained on Coverage+Success demonstrates substantial overfitting in the mismatch between the distribution of $Q$ values between train and test while the one trained on VBT does not.}
    \label{fig:histogram}
\end{figure}

To isolate this issue, we plot histograms of the learned $Q$ values on the train datasets and held out test datasets for both the Coverage+Success and VBT data in Fig. \ref{fig:histogram}. The histograms confirm that the $Q$ function trained on Coverage+Success assigns low values to Coverage transitions from the training set and high values to Success transitions from the training set. But, these $Q$ functions do not generalize. The test set yields a very different distribution of values.
In contrast, VBT data resolves the overfitting issue by ensuring that the only visual differences between failure and success are task-relevant, which facilitates better generalization.

\subsection{VBT data leads to improved policies}

To measure the impact of switching to VBT data on policy performance we perform an AB test. Specifically, we train policies using each of the three learning algorithms (BC, AWAC, IQL) on each of the four types of datasets (Success, Coverage+Success, LfP+Success, VBT-Ours), but excluding BC on the datasets that contain episodes that do not terminate in success (Coverage+Success, LfP+Success). For the AB test, each episode a policy is chosen at random and executed until either the policy sends the ``terminate'' action or the maximum number of steps per episode is reached. Success is determined by the majority vote out of three human labelers based on the final image in the episode. The randomness of the AB test ensures a valid comparison between all of the trained policies. Results are reported in Table \ref{tab:ab}.

\begin{table}
\vspace{0.3cm}
\centering
\begin{tabular}{lcc}
\toprule
Dataset & Policy & Task Success \\ \midrule
Success   & BC     & $66 \pm 4$\%  \\
Success   & AWAC   & $67 \pm 3$\%  \\
Success   & IQL    & $69 \pm 3$\%  \\ \midrule
Coverage+Success    & AWAC   & $52 \pm 4$\%    \\
Coverage+Success    & IQL   & $64 \pm 3$\%     \\ \midrule
LfP+Success       & AWAC   & $62 \pm 4$\%    \\
LfP+Success       & IQL    & $58 \pm 4$\%    \\ \midrule
VBT-Ours  & BC     & $73 \pm 3$\%  \\
VBT-Ours  & AWAC   & $73 \pm 3$\%  \\
\textbf{VBT-Ours}  & \textbf{IQL}    & \textbf{79 $\pm$ 3\%}  \\ \bottomrule
\end{tabular}
\caption{Evaluation of grasping on an AB test of 1437 total episodes. Error bars report standard error.}
\label{tab:ab}
\end{table}

There are several takeaways from these results:
\begin{enumerate}
    \item Training IQL on VBT outperforms standard BC on Success data by 13\% and outperforms IQL on Success data by 10\%. These are significant gains, especially given that we are training each policy from scratch on very small datasets with image-based observations.
    \item Due to overfitting, OffRL algorithms trained on Coverage+Success and LfP+Success underperform those same algorithms trained on Success data alone.
    \item Even BC on VBT data outperforms BC on Successes for this task since training BC on VBT leads to retrying behaviors. OffRL provides further benefits beyond BC by effectively filtering out the suboptimal actions that are present in VBT data.
\end{enumerate}

Overall, the experimental results paint a picture that VBT is able to improve coverage and prevent overfitting. This allows for more effective OffRL in terms of qualitatively better value functions and quantitatively better policies than we get from simple Success data or naively mixing in failures as in the Coverage+Success or LfP+Success data.

\section{Discussion}

In this paper, we introduced VBT, a protocol for robot data-collection for offline policy learning.
We showed how value functions learned using VBT data tend to be more accurate, leading to robust policy learning with OffRL.
We compared VBT to a number of other data collection protocols, and found that policies learned using VBT result in superior performance.
We demonstrated these results on a real world, vision-based deformable manipulation task.

While our method significantly outperforms other data-collection protocols, it has certain limitations. VBT requires a teleoperator to understand the relevant failure modes for the task (in our grasping task, this corresponds to narrowly missing the T-shirt), and the ability to recover and re-attempt.

In future work, it would be interesting to apply VBT to tasks with more variety, such as collecting a dataset consisting of interactions with many different objects, instead of just one object.
Finally, while we studied a relatively short-horizon task, future work can look into applying VBT to long-horizon tasks.

\newpage

\bibliographystyle{ieeetr}