# RoboCLIP:
One Demonstration is Enough to Learn Robot Policies

Sumedh A Sontakke1 corresponding author<EMAIL_ADDRESS>Jesse Zhang  Thomas
Lord Department of Computer Science, University of Southern California
Sébastien M. R. Arnold  Google Research
Karl Pertsch  University of California, Berkeley  Stanford University  Erdem
Bıyık  Thomas Lord Department of Computer Science, University of Southern
California  University of California, Berkeley  Dorsa Sadigh  Stanford
University  Chelsea Finn  Stanford University  Laurent Itti  Thomas Lord
Department of Computer Science, University of Southern California

###### Abstract

Reward specification is a notoriously difficult problem in reinforcement
learning, requiring extensive expert supervision to design robust reward
functions. Imitation learning (IL) methods attempt to circumvent these
problems by utilizing expert demonstrations but typically require a large
number of in-domain expert demonstrations. Inspired by advances in the field
of Video-and-Language Models (VLMs), we present RoboCLIP, an online imitation
learning method that uses a single demonstration (overcoming the large data
requirement) in the form of a video demonstration or a textual description of
the task to generate rewards without manual reward function design.
Additionally, RoboCLIP can also utilize out-of-domain demonstrations, like
videos of humans solving the task for reward generation, circumventing the
need to have the same demonstration and deployment domains. RoboCLIP utilizes
pretrained VLMs without any finetuning for reward generation. Reinforcement
learning agents trained with RoboCLIP rewards demonstrate 2-3 times higher
zero-shot performance than competing imitation learning methods on downstream
robot manipulation tasks, doing so using only one video/text demonstration.
Visit our website for experiment videos.

##  1 Introduction

Sequential decision-making problems typically require significant human
supervision and data. In the context of online reinforcement learning (Sutton
and Barto, 2018), this manifests in the design of good reward functions that
map transitions to scalar rewards (Amodei et al., 2016; Hadfield-Menell et
al., 2017). Extant approaches to manual reward function definition are not
very principled and defining rewards for complex long-horizon problems is
often an art requiring significant human expertise. Additionally, evaluating
reward functions often requires knowledge of the true state of the
environment. For example, imagine a simple scenario where the agent must learn
to lift an object off the ground. Here, a reward useful for task success would
be proportional to the height of the object from the ground — a quantity non-
trivial to obtain without full state information. Thus, significant effort has
been expounded in developing methods that can learn reward functions either
explicitly or implicitly from demonstrations, i.e., imitation learning
(Pomerleau, 1988; Ng and Russell, 2000; Abbeel and Ng, 2004; Ziebart et al.,
2008). With these methods, agent policies can either be directly extracted
from the demonstrations or trained to optimize rewards functions learned from
them.

Imitation learning (IL), however, only somewhat alleviates the need for expert
human intervention. First, instead of designing complex reward functions,
expert supervision is needed to collect massive datasets such as RT-1 (Brohan
et al., 2022), Bridge Dataset (Ebert et al., 2021), D4RL (Fu et al., 2020), or
Robonet (Dasari et al., 2019). The performance of imitation learning
algorithms and their ability to generalize hinges on the coverage and size of
data (Kumar et al., 2019, 2022), making the collection of large datasets
imperative.

Figure 1: RoboCLIP Overview.  A Pretrained Video-and-Language Model is used to
generate rewards via the similarity score between the encoding of an episode
of interaction of an agent in its environment, $\mathbf{z}^{v}$ with the
encoding of a task specifier $\mathbf{z}^{d}$ such as a textual description of
the task or a video demonstrating a successful trajectory. The similarity
score between the latent vectors is provided as reward to the agent.

Second and most importantly, the interface for collecting demonstrations for
IL is tedious, requiring expert robot operators to collect thousands of
demonstrations. On the contrary, a more intuitive way to define rewards would
be in the form of a textual description (e.g., “robot grasping object”), or in
the form of a naturalistic video demonstration of the task performed by a
human actor in an environment separate from the robotic environment. For
example, demonstrating to a robot how to open a cabinet door in one’s own
kitchen is more naturalistic than collecting many thousands of trajectories
via teleoperation in the target robotic environment.

Thus, there exists an unmet need for IL algorithms that 1) require very few
demonstrations and 2) allow for a natural interface for providing these
demonstrations. For instance, algorithms that can effectively learn from
language instructions or human demonstrations without the need for full
environment state information. Our key insight is that by leveraging Video-
and-Language Models (VLMs)—which are already pretrained on large amount of
video demonstration and language pairs—we do not need to rely on large-scale
and in-domain datasets. Instead, by harnessing the power of VLM embeddings, we
treat the mismatch between a single _instruction’s_ embedding (provided as a
language command or a video demonstration) and the embedding of the video of
the current policy’s rollout as a proxy reward that will guide the policy
towards the desired _instruction_.

To this end, we present RoboCLIP, an imitation learning algorithm that learns
and optimizes a reward function based on a single language or video
demonstration. The backbone model used in RoboCLIP is S3D (Xie et al., 2018)
trained on the Howto100M dataset (Miech et al., 2019), which consists of short
clips of humans performing activities with textual descriptions of the
activities. These videos typically consist of a variety of camera angles,
actors, lighting conditions, and backgrounds. We hypothesize that VLMs trained
on such diverse videos are invariant to these extraneous factors and generate
an actor-agnostic semantically-meaningful representation for a video, allowing
them to generalize to unseen robotic environments.

We present an overview of RoboCLIP in Figure 1. RoboCLIP computes a similarity
score between videos of online agent experience with a task descriptor, i.e.,
a text description of the task or a single human demonstration video, to
generate trajectory-level rewards to train the agent. We evaluate RoboCLIP on
the Metaworld Environment suite (Yu et al., 2020) and on the Franka Kitchen
Environment (Gupta et al., 2019), and find that policies obtained by
pretraining on the RoboCLIP reward result in $2-3\times$ higher zero-shot task
success in comparison to state-of-the-art imitation learning baselines.
Additionally, these rewards require no experts for specification and can be
generated using naturalistic definitions like natural language task
descriptions and human demonstrations.

##  2 Related Work

#### Learning from Human Feedback.

Learning from demonstrations is a long-studied problem that attempts to learn
a policy from a dataset of expert demonstrations. Imitation learning (IL)
methods, such as those based on behavioral cloning (Pomerleau, 1988),
formulate the problem as a supervised learning over state-action pairs and
typically rely on large datasets of expert-collected trajectories directly
demonstrating how to perform the target task (Brohan et al., 2022; Lynch et
al., 2022). However, these large demonstration datasets are often expensive to
collect. Another IL strategy is _inverse_ RL, i.e., directly learning a reward
function from the demonstrations (Ng and Russell, 2000; Abbeel and Ng, 2004;
Ziebart et al., 2008; Finn et al., 2016). Inverse RL algorithms are typically
difficult to apply when state and action spaces are high-dimensional. Methods
such as GAIL (Ho and Ermon, 2016), AIRL (Fu et al., 2017), or VICE (Fu et al.,
2018) partially address these issues by assigning rewards which are
proportional to the probability of a given state being from the demonstration
set or a valid goal state as estimated by a learned discriminator network.
However these discriminator networks still require many demonstrations or goal
states to train to effectively distinguish between states from agent-collected
experience and demonstration or goal states. On the other hand, RoboCLIP’s use
of pretrained video-and-language models allows us to train agents that learn
to perform target tasks with just _one demonstration_ in the form of a video
or a language description. Other works instead use human feedback in the form
of pairwise comparisons or rankings to learn preference reward functions
(Christiano et al., 2023; Sadigh et al., 2017; Biyik et al., 2019; Myers et
al., 2021; Bıyık et al., 2022; Brown et al., 2019; Biyik et al., 2020; Lee et
al., 2021; Hejna and Sadigh, 2022). These preferences may require less human
effort to obtain than reward functions, e.g., through querying humans to
simply rank recent trajectories. Yet individual trajectory preferences convey
little information on their own (less than dense reward functions) and
therefore humans need to respond to many preference queries for the agent to
learn useful reward functions. In contrast, RoboCLIP is able to extract useful
rewards from a single demonstration or single language instruction.

#### Large Vision and Language Models as Reward Functions.

Kwon et al. (2023) and Hu and Sadigh (2023) propose using large language
models (LLMs) for designing and regularizing reward functions that capture
human preferences. These works study the reward design problem in text-based
games such as negotiations or card games, and thus are not grounded in the
physical world. RoboCLIP instead leverages video-and-language models to assess
if video demonstrations of robot policies align with an expert demonstration.
Prior work has demonstrated that video models can be used as reward functions.
For example, Chen et al. (2021) learn a visual reward function using human
data and then utilize this reward function for visual model-based control of a
robot. However, they require training the reward model on paired human and
robot data from the deployment environment. We demonstrate that this paired
data assumption can be relaxed by utilizing large-scale vision-language models
pretrained on large corpora of human-generated data. The most well-known of
these is CLIP (Radford et al., 2021), which is trained on pairs of images and
language descriptions scraped from the internet. While CLIP is trained only on
images, video-language-models (VLMs) trained on videos of humans performing
daily tasks such as S3D (Xie et al., 2018) or XCLIP (Ni et al., 2022) are also
widely available. These models utilize language descriptions while training to
supervise their visual understanding so that _semantically_ similar vision
inputs are embedded close together in a shared vector space. A series of
recent works demonstrate that these VLMs can produce useful rewards for agent
learning. Fan et al. (2022) finetune CLIP on YouTube videos of people playing
Minecraft and demonstrate that the finetuned CLIP model can be used as a
language-conditioned reward function to train an agent. DECKARD (Nottingham et
al., 2023) then uses the fine-tuned reward function of Fan et al. (2022) to
reward an agent for completing tasks proposed by a large-language model and
abstract world model. PAFF (Ge et al., 2023) uses a fine-tuned CLIP model to
align videos of policy rollouts with a fixed set of language skills and
relabel experience with the best-aligned language label. We demonstrate that
_videos_ and multi-modal task specifications can be utilized to learn reward
functions allowing for training agents. Additionally, we present a method to
test the alignment of pretrained VLMs with deployment environments.

##  3 Method

#### Overview.

RoboCLIP utilizes pretrained video-and-language models to generate rewards for
online RL agents. This is done by providing a sparse reward to the agent at
the end of the trajectory which describes the similarity of the agent’s
behavior to that of the demonstration. We utilize video-and-language models as
they provide the flexibility of defining the task in terms of natural language
descriptions or video demonstrations sourced either from the target robotic
domain or other more naturalistic domains like human actors demonstrating the
target task in their own environment. Thus, a demonstration (textual or video)
and the video of an episode of robotic interaction are embedded into the
semantically meaningful latent space of S3D (Xie et al., 2018), a video-and-
language model pretrained on diverse videos of human actors performing
everyday tasks taken from the HowTo100M dataset (Miech et al., 2019). The two
vectors are subsequently multiplied using a scalar product generating a
similarity score between the 2 vectors. This similarity score (without
scaling) is returned to the agent as a reward for the episode.

#### Notation.

We formulate the problem in the manner of a POMDP (Partially Observable Markov
Decision Process) with ($\mathcal{O}$, $\mathcal{S}$, $\mathcal{A}$, $\phi$,
$\theta$, $r$, $T$, $\gamma$) representing an observation space $\mathcal{O}$,
state space $\mathcal{S}$, action space $\mathcal{A}$, transition function
$\phi$, emission function $\theta$, reward function $r$, time horizon $T$, and
discount factor $\gamma$. An agent in state $\mathbf{s}_{t}$ takes an action
$\mathbf{a}_{t}$ and consequently causes a transition in the environment
through $\phi(\mathbf{s}_{t+1}\mid\mathbf{s}_{t},\mathbf{a}_{t})$. The agent
receives the next state $\mathbf{s}_{t+1}$ and reward
$r_{t}=r(\mathbf{o}_{t},\mathbf{a}_{t})$ calculated using the observation
$\mathbf{o}_{t}$. The goal of the agent is to learn a policy $\mathbf{\pi}$
which maximizes the expected discounted sum of rewards, i.e.,
$\sum_{t=0}^{T}\gamma^{t}r_{t}$. Note that all of our baselines utilize the
true state for reward generation and for policy learning. To examine the
effect of using a video-based reward, we also operate our policy on the state
space while using the pixel observations for reward generation. Thus, $r_{t}$
uses $\mathbf{o}_{t}$ while $\mathbf{\pi}$ uses $\mathbf{s}_{t}$ for RoboCLIP
while for all other baselines, both $r_{t}$ and $\mathbf{\pi}$ utilize
$\mathbf{s}_{t}$. This of course is unfair to our method, but we find that in
spite of the advantage provided to the baselines, RoboCLIP rewards still
generate higher zero-shot success.

#### Reward Generation.

During the pretraining phase, we supply the RoboCLIP reward to the agent in a
sparse manner at the end of each episode. This is done by storing the video of
an episode of the interaction of the agent with the environment into a buffer
as seen in Figure 1. A sequence of observations of length $128$ are saved in a
buffer corresponding to the length of the episode. S3D is trained on videos
length $32$ frames and therefore the episode video is subsequently downsampled
to result in a video of length $T=32$. The video is subsequently center-
cropped to result in frames of size $(250,250)$. This is done to ensure that
the episode video is preprocessed to match the specifications of the HowTo100M
preprocessing used to train the S3D model. Thus the tensor of a sequence of
$T$ observations $\mathbf{o}_{0:T}$ is encoded as the latent video vector
$\mathbf{z}^{v}$ using

$\mathbf{z}^{v}=S3D^{\text{video-encoder}}(\mathbf{o}_{0:T})$ (1)

The task specification is also encoded into the same space. If it is defined
using natural language, the language encoder in S3D encodes a sequence of $K$
textual tokens $\mathbf{d}_{0:K}$ into the latent space using:

$\mathbf{z}^{d}=S3D^{\text{text-encoder}}(\mathbf{d}_{0:K})$ (2)

If the task description is in the form of a video of length $K$, then we
preprocess and encode it using the video-encoder in S3D just as in Equation 1.
For intermediate timesteps, i.e., timesteps other than the final one in an
episode, the reward supplied to the agent is zero. Subsequently, at the end of
the episode, the similarity score between the encoded task descriptor
$\mathbf{z}^{d}$ and the encoded video of the episode $\mathbf{z}^{v}$ is used
as reward $r^{\text{RoboCLIP}}(T)$. Thus the reward is:

$r^{\text{RoboCLIP}}(t)=\begin{cases}0,&t\neq T\\\
\mathbf{z}^{d}\cdot\mathbf{z}^{v}&t=T\end{cases}$

where $\mathbf{z}^{d}\cdot\mathbf{z}^{v}$ corresponds to the scalar product
between vectors $\mathbf{z}^{d}$ and $\mathbf{z}^{v}$.

#### Agent Training.

Using $r^{\text{RoboCLIP}}$ defined above, we then train an agent online in
the deployment environment with any standard reinforcement learning (RL)
algorithm by labeling each agent experience trajectory with
$r^{\text{RoboCLIP}}$ after the agent collects it. In our paper, we train with
PPO (Schulman et al., 2017), an on-policy RL algorithm, however, RoboCLIP can
also be applied to off-policy algorithms. After training with this reward, the
agent can be zero-shot evaluated or fine-tuned on true environment reward on
the target task in the deployment environment.

##  4 Experiments

We test out each of the hypotheses defined in Section 1 on simulated robotic
environments. Specifically, we ask the following questions:

  1. 1.

Do existing pretrained VLMs semantically align with robotic manipulation
environments?

  2. 2.

Can we utilize natural language to generate reward functions?

  3. 3.

Can we use videos of expert demonstrations to generate reward functions?

  4. 4.

Can we use out-of-domain videos to generate reward functions?

  5. 5.

Can we generate rewards using a combination of demonstration and natural
language?

  6. 6.

What aspects of our method are crucial for success?

We arrange this section to answer each of these questions. Both RoboCLIP and
baselines utilize PPO (Schulman et al., 2017) for policy learning.

#### Baselines.

We use 2 state-of-the-art methods in inverse reinforcement learning: GAIL, or
Generative Adversarial Imitation Learning (Ho and Ermon, 2016) and AIRL or
Adversarial Inverse Reinforcement Learning (Fu et al., 2017). Both of these
methods attempt to learn reward functions from demonstrations provided to the
agent. Subsequently, they train an agent using this learned reward function to
imitate the expert behavior. Both methods receive a single demonstration,
consistent with our approach of using a single video imitation. However, since
they both operate on the ground-truth environment state, we provide them with
a trajectory of states, instead of images, thereby providing them privileged
state information that our method does not receive.

###  4.1 Domain Alignment

Pretrained vision models are often trained on a variety of human-centric
activity data, such as Ego4D (Grauman et al., 2022). Since we are interested
in solving robotic tasks with view from third person perspectives, we utilize
the S3D (Xie et al., 2018) VLM pretrained on HowTo100M (Miech et al., 2019), a
dataset of short third-person clips of humans performing everyday activities.
This dataset, however, contains no robotic manipulation data.

Figure 2: Domain Alignment Confusion Matrix.  We perform a confusion matrix
analysis on a subset of the data on collected on Metaworld (Yu et al., 2020)
environments by comparing the pair-wise similarities between the latent
vectors of the strings describing the videos and those of the videos. We find
that Metaworld is well-aligned with higher scores along the diagonal than
along the off-diagonal elements.

To analyze the alignment of the VLM to different domains, we perform a
confusion matrix analysis using videos from Metaworld (Yu et al., 2020). We
collect 10 videos per task with varying values of true reward. For each video,
we also collect the true reward. We then compute the RoboCLIP reward for each
video using VLM alignment between the textual description of the task and the
video. We visualize the correlations between the RoboCLIP and true rewards in
the form of an $n\times n$ matrix where entry $(i,j)$ corresponds to the
correlation between the true reward and the RoboCLIP reward generated for the
$i^{\text{th}}$ task using the $j^{\text{th}}$ text description. As one can
see, for a given task, the highest correlation in the matrix is for the
correct textual description. We visualize one such similarity matrix in Figure
2 for Metaworld. We find that Metaworld seems to align well in the latent
space of the model with a more diagonal-heavy confusion matrix. The objects
are all correctly identified.

###  4.2 Language for Reward Generation

The most naturalistic way to define a task is through natural language. We do
this by generating a sparse reward signal for the agent as described in
Section 3: the reward for an episode is the similarity score between its
encoded video and the encoded textual description of the expected behavior in
the VLM’s latent space. The reward is provided to the agent at the end of the
episode. For RoboCLIP, GAIL, and AIRL, we first pretrain the agents online
with their respective reward functions and then perform finetuning with the
true task reward in the deployment environment.

Figure 3: Language-Conditioned Reward Generation.  The pretrained VLM is used
to generate rewards via the similarity score of the encoding of an episode of
interaction of an agent in its environment, $\mathbf{z}^{v}$ with the encoding
of a task specifier $\mathbf{z}^{d}$ specified in natural language. We use the
strings, “robot closing black box”, “robot closing green drawer” and “robot
pushing red button” for conditioning for the 3 environments respectively. We
find that agents pretrained on these language-conditioned rewards outperform
imitation learning baselines like GAIL (Ho and Ermon, 2016) and AIRL (Fu et
al., 2017).

We perform this analysis on 3 Metaworld Environments: Drawer-Close, Door-Close
and Button-Press. We use the textual descriptions, “robot closing green
drawer”, “robot closing black box”, and “robot pushing red button” for each
environment, respectively. Figure 3 plots returns on the target tasks while
finetuning on the depoloyment environment after pretraining (with the
exception of the Dense Task Reward baseline). Our method outperforms the
imitation learning baselines with online exploration in terms of true task
rewards in all environments. Additionally our baselines utilize the full state
information in the environment for reward generation where RoboCLIP uses only
the pixels to infer state. RoboCLIP also achieves more than double zero-shot
rewards in all environments — importantly, the RoboCLIP-trained agent is able
to complete the tasks even before finetuning on true task rewards.

Figure 4: Using In-Domain Videos for Reward Generation.  The pretrained VLM is
used to generate rewards via the similarity score of the encoding of an
episode of interaction of an agent in its environment, $\mathbf{z}^{v}$ with
the encoding of a video demonstration of expert behavior in the same
environment. The similarity score between the latent vectors is provided as
reward to the agent and is used to train online RL methods. We study this
setup in the Kettle, Hinge and Slide Tasks in the Franka Kitchen Environment
(Gupta et al., 2019). We find that policies trained on the RoboCLIP reward are
able to learn to complete the task in all three setups without any need for
external rewards using just a single in-domain demonstration.

###  4.3 In-Domain Videos for Reward Generation

Being able to use textual task descriptors for reward generation can only work
in environments where there is domain alignment between the pretrained model
and the visual appearance of the environment. Additionally, VLMs are large
models often with billions of parameters making it computationally expensive
to fine tune for domain alignment. The most naturalistic way to define a task
in such a setting is in the form a single demonstration in the robotic
environment which can be collected using teleoperation. We study how well this
works in the Franka Kitchen (Gupta et al., 2019) environment. We consider
access to a single demonstration per task whose video is used to generate
rewards for online RL.

#### Quantitative Results.

We measure the zero-shot task reward, which increases as the task object
(i.e., Kettle, Slide and Hinge Cabinets) gets closer to its goal position.
This reward does not depend on the position of the end-effector, making the
tasks difficult. Figure 4 shows the baselines perform poorly as they generally
do not interact with the target objects, while RoboCLIP is able to solve the
task using the reward generated using the video of a single demonstration.

#### Qualitative Results.

We find that RoboCLIP allows for mimicking the “style” of the source
demonstration, with idiosyncrasies of motion from the source demonstration
generally transferring to the policy generated. We find this to occur in the
kitchen environment’s Slide and Hinge task as seen in Figure 5. The first row
of the subfigures in Figure 5 are visualizations of the demonstration video
used to condition the VLM for reward generation. The bottom rows correspond to
the policies that are trained with the generated rewards of RoboCLIP. As can
be seen, the Slide demonstration consists of a wide circular arc of motion.
This is mimicked in the learned policy, although the agent misses the cabinet
in the first swipe and readjusts to make contact with the handle.

Figure 5: Qualitative Inspection of Imitation. The first row in each subfigure
shows the visualizations of the demonstration video used for reward generation
via the VLM. The second rows are videos taken from policy recovered from
training on the RoboCLIP reward generated using the videos in the first rows.
The quick swiping motion demonstrated in the Slide demonstration is mimicked
well in the resultant policy while the wrist-rotational “trick-shot” behavior
in the demonstration for Hinge appears in the resultant learned policy. Figure
6: Finetuning for Harder Environments: In harder environments, like Coffee-
Push and Faucet-Open, we find that RoboCLIP rewards do not solve the task
completely. We test whether providing a single demonstration in the
environment (using observations and actions) is enough to finetune this
pretrained policy, a setup identical to our baselines. Thus, we pre-train on
the RoboCLIP reward from language and then finetune using a single robotic
demonstration. This improves performance by $\sim 200$%. See videos on our
website.

This effect is even more pronounced in the Hinge example where the source
demonstration consists of twirling wrist-rotational behavior, which is
subsequently imitated by the learned policy. The downstream policy misses the
point of contact with the handle but instead uses the twirling motion to open
the hinged cabinet in an unorthodox manner by pushing near the hinge. We posit
that the VLMs used in RoboCLIP contain a rich latent space encoding these
various motions, and so even if they cannot contain semantically meaningful
latent vectors in the Franka Kitchen environments due to domain mismatch, they
are still able to encode motion information allowing them to be used for
RoboCLIP with a single demonstration video.

Figure 7: Using Out-of-Domain Videos for Reward Generation.  A Pretrained
Video-and-Language Model is used to generate rewards via the similarity score
of the encoding of an episode of interaction of an agent in its environment,
$\mathbf{z}^{v}$ with the encoding of a task specifier $\mathbf{z}^{d}$ in the
form of a video of a human or an animated character demonstrating a task in
their own environment. The similarity score between the latent vectors is
provided as reward to the agent and is used to train online RL methods. The
frames below the graphs illustrate the video used for reward generation.

###  4.4 Out-of-Domain Videos for Reward Generation

Another natural way to define a task is to demonstrate it yourself. To this
end, we try to use demonstrations of humans or animated characters acting in
separate environments as task specification.

Figure 8: Multimodal Task Specification. We study whether video demonstrations
of expert demonstrations can be used to define tasks. We use the latent
embedding of a video demonstration of a robot pushing a button and subtract
from it the embedding of the text “red button” and add to it the embedding of
the text “green drawer”. This modified latent is used to generate rewards in
the Drawer-Close environment. We find that the policy trained using this
modified vector outperforms string-only manipulation in the zero-shot setting.

For this, we utilize animated videos of a hand pushing a red button and
opening a green drawer and a real human video of opening a fridge door (see
Figure 7). The animated videos are collected from stock image repositories and
the human video is collected using a phone camera in our lab kitchen. Using
the encodings of these video, we test out RoboCLIP in the 3 corresponding
Metaworld tasks - Button-Press, Drawer-Open and Door-Open. We follow the same
setup as in Section 4.2 by first pretraining methods with their respective
reward functions and then finetuning in the deployment environment with target
task reward.

We compare the performance of the policy trained with these rewards to GAIL
(Ho and Ermon, 2016) and AIRL (Fu et al., 2017) trained using the same single
expert demonstration as RoboCLIP on these rewards with state information.
These methods are known to be data-hungry, requiring multiple demonstrations
to train their reward functions. Consequently, they perform much worse than
RoboCLIP, even with 2-3x worse zero-shot task performance, as can be seen from
Figure 7.

###  4.5 Multimodal Task Specification

Using videos to specify a task description is possible when either there is
access to a robot for teleoperation as in Section 4.3 or a human can
demonstrate a behavior in their own environment as in Section 4.4. When these
are not the case, a viable alternative is to utilize multimodal
demonstrations. For example, consider a scenario where the required task is to
push a drawer to close it, but only a demonstration for pushing a button is
available. In this situation, being able to edit the video of the off-task
demonstration is useful. This way, one can direct the agent to move its end-
effectors to push the drawer instead of the button.

We do this by algebraically modifying the encoding of the video demonstration:

$\mathbf{z}^{\text{edited}}(\text{push drawer})=\mathbf{z}^{video}(\text{push
button})-\\\
\mathbf{z}^{text}(\text{button})+\mathbf{z}^{text}(\text{drawer})$ (3)

where $\mathbf{z}^{\text{edited}}(\text{push drawer})$ is the vector used to
generate rewards in the Drawer-Close environment,
$\mathbf{z}^{video}(\text{push button})$ is the vector of the encoding of the
video of the robot pushing a button, $\mathbf{z}^{text}(\text{button})$ is the
encoding of the string button and $\mathbf{z}^{text}(\text{drawer})$ is the
encoding of the string drawer. As can be seen in Figure 8, defining rewards in
such a multimodal manner results in a higher zero-shot score than the dense
task reward and also pretraining on the string-only task reward.

###  4.6 Finetuning

In harder environments, and with rewards from OOD videos and language, the
robot policy sometimes approaches the target object, but fails to complete the
task. Thus, we tested whether providing a single demonstration (using
observations and actions) was enough to finetune this pretrained policy.

Thus, for this experiment we first (1) pretrain on the RoboCLIP reward from
human videos or language descriptions and then (2) finetune using a single
demonstration. As seen in Figure 6, we find that this converts each of the
partially successful policies into complete success and improves the rewards
attained by the policies by $\leavevmode\nobreak\ 200\%$. This fine-tuning
setup is especially useful in harder tasks like like Coffee-Push and Faucet-
Open and is competitive with state-of-the-art approaches like FISH (Haldar et
al., 2023).

###  4.7 Ablations

Finally, we investigate the effects of various design decisions in RoboCLIP.
First, we study the effect of additional video demonstrations on agent
performance. We also examine the necessity of using a pre-trained VLM. Recent
works like RE3 (Seo et al., 2021; Ulyanov et al., 2018) have shown that
randomly initialized networks often contain useful image priors and can be
used to supply rewards to agents to encourage exploration. Therefore, we test
whether a _randomly initialized_ S3D VLM can supply useful pretraining rewards
in the in-domain video demonstration setup as in Section 4.3. Finally, we
study our choice of pre-trained VLM. We examine whether a pretrained CLIP
(Radford et al., 2021), which encodes single images instead of videos and was
trained on a different dataset from S3D, can be used to generate rewards for
task completion. In this setup, we record the last image in an episode of
interaction of the agent in its environment and feed it to CLIP trained on
ImageNet (Russakovsky et al., 2015) (i.e., not trained on videos). We then
specify the task in natural language and use the similarity between the
embeddings of the textual description of the task and the final image in the
episode to generate a reward that is fed to the agent for online RL.

As seen in Figure 9, using a single video demonstration provides the best
signal for pretraining. We posit that our method performs worse when
conditioned on multiple demonstrations as the linear blending of multiple
video embeddings, which is used due to the scalar product, does not
necessarily correspond to the embedding of a successful trajectory.

Figure 9: Ablations. We study the effects of varying the number of
demonstrations provided to the agent can have on downstream rewards. We also
study the effects of the training provided to the VLM on the downstream
rewards. Finally, we study whether using CLIP trained on static images
provides good rewards for pretraining.

Crucially, we also find that using the static image version of CLIP does not
provide any useful signal for pretraining. The zero-shot performance is very
poor, which we posit is because it does not contain any information about the
dynamics of motion and task completion although it contains semantic meaning
about objects in the frame. On the other hand, video contrastive learning
approaches do contain this information. This is further evidenced by the fact
that inspite of poor domain alignment between Franka Kitchen and the VLM, we
find that encodings of in-domain video demonstrations are still good for
providing a pretraining reward signal to the agent.

##  5 Conclusion

Summary. We studied how to distill knowledge contained in large pretrained
Video-and-Language-Models into online RL agents by using them to generate
rewards. We showed that our method, RoboCLIP, can train robot policies using a
single video demonstration or textual description of the task, depending on
how well the domain aligns with the VLM. We further investigated alternative
ways to use RoboCLIP, such as using out-of-domain videos or multimodal
demonstrations. Our results showed RoboCLIP outperforms the baselines in
various robotic environments.

Limitations and Broader Impact. Since we are using VLMs, the implicit biases
within these large models could percolate into RL agents. Addressing such
challenges is necessary, especially since it is unclear what the form of
biases in RL agents might look like. Currently, our method also faces the
challenge of stable finetuning. We find that in some situations, finetuning on
downstream task reward results in instabilities as seen in the language
conditioned reward curve in Figure 8. This instability is potentially due to
the scale of rewards provided to the agent. Rewards from the VLM are fairly
low in absolute value and subsequently, the normalized Q-values in PPO
policies are out-of-shape when finetuned on task rewards. In our experiments,
this is not a big problem since the RoboCLIP reward is already sufficient to
produce policies that complete tasks without any deployment environment
finetuning, but this will be essential to solve when deploying this for longer
horizon tasks.

Another limitation of our work is that there is no fixed length of
pretraining. Our current method involves pretraining for a fixed number of
steps and then picking the best model according to the true task reward. This
is of course difficult when deploying RoboCLIP in a real-world setup as a true
reward function is unavailable and a human must monitor the progress of the
agent. We leave this for future work.

## Acknowledgments and Disclosure of Funding

This work was supported by DARPA (HR00112190134), C-BRIC (one of six centers
in JUMP, a Semiconductor Research Corporation (SRC) program sponsored by
DARPA), the Army Research Office (W911NF2020053) and the Office of Naval
Research (ONR) (#N00014-21-1-2298 and #N00014-21-1-2685). The authors affirm
that the views expressed herein are solely their own, and do not represent the
views of the United States government or any agency thereof. Thanks to Karol
Hausman, Sergey Levine, Ofir Nachum, Kuang-Huei Lee and many others at Google
DeepMind for helpful discussions.

## References

  * Abbeel and Ng [2004] Pieter Abbeel and Andrew Y. Ng.  Apprenticeship learning via inverse reinforcement learning.  In _Proceedings of the Twenty-First International Conference on Machine Learning_ , ICML ’04, page 1, New York, NY, USA, 2004. Association for Computing Machinery.  ISBN 1581138385.  doi: 10.1145/1015330.1015430.
  * Amodei et al. [2016] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané.  Concrete problems in ai safety.  _arXiv preprint arXiv:1606.06565_ , 2016.
  * Biyik et al. [2019] Erdem Biyik, Malayandi Palan, Nicholas C. Landolfi, Dylan P. Losey, and Dorsa Sadigh.  Asking easy questions: A user-friendly approach to active reward learning.  In _Proceedings of the 3rd Conference on Robot Learning (CoRL)_ , 2019\.
  * Biyik et al. [2020] Erdem Biyik, Nicolas Huynh, Mykel J. Kochenderfer, and Dorsa Sadigh.  Active preference-based gaussian process regression for reward learning.  In _Proceedings of Robotics: Science and Systems (RSS)_ , July 2020\.  doi: 10.15607/rss.2020.xvi.041.
  * Bıyık et al. [2022] Erdem Bıyık, Dylan P Losey, Malayandi Palan, Nicholas C Landolfi, Gleb Shevchuk, and Dorsa Sadigh.  Learning reward functions from diverse sources of human feedback: Optimally integrating demonstrations and preferences.  _The International Journal of Robotics Research_ , 41(1):45–67, 2022.
  * Brohan et al. [2022] Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Joseph Dabis, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Jasmine Hsu, Julian Ibarz, Brian Ichter, Alex Irpan, Tomas Jackson, Sally Jesmonth, Nikhil Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Isabel Leal, Kuang-Huei Lee, Sergey Levine, Yao Lu, Utsav Malla, Deeksha Manjunath, Igor Mordatch, Ofir Nachum, Carolina Parada, Jodilyn Peralta, Emily Perez, Karl Pertsch, Jornell Quiambao, Kanishka Rao, Michael Ryoo, Grecia Salazar, Pannag Sanketi, Kevin Sayed, Jaspiar Singh, Sumedh Sontakke, Austin Stone, Clayton Tan, Huong Tran, Vincent Vanhoucke, Steve Vega, Quan Vuong, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Tianhe Yu, and Brianna Zitkovich.  Rt-1: Robotics transformer for real-world control at scale.  In _arXiv preprint arXiv:2212.06817_ , 2022.
  * Brown et al. [2019] Daniel S. Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum.  Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 783–792, Long Beach, California, USA, 09–15 Jun 2019. PMLR.
  * Chen et al. [2021] Annie S. Chen, Suraj Nair, and Chelsea Finn.  Learning generalizable robotic reward functions from "in-the-wild" human videos, 2021.
  * Christiano et al. [2023] Paul Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei.  Deep reinforcement learning from human preferences, 2023.
  * Dasari et al. [2019] Sudeep Dasari, Frederik Ebert, Stephen Tian, Suraj Nair, Bernadette Bucher, Karl Schmeckpeper, Siddharth Singh, Sergey Levine, and Chelsea Finn.  Robonet: Large-scale multi-robot learning.  _arXiv preprint arXiv:1910.11215_ , 2019.
  * Ebert et al. [2021] Frederik Ebert, Yanlai Yang, Karl Schmeckpeper, Bernadette Bucher, Georgios Georgakis, Kostas Daniilidis, Chelsea Finn, and Sergey Levine.  Bridge data: Boosting generalization of robotic skills with cross-domain datasets.  _arXiv preprint arXiv:2109.13396_ , 2021.
  * Fan et al. [2022] Linxi Fan, Guanzhi Wang, Yunfan Jiang, Ajay Mandlekar, Yuncong Yang, Haoyi Zhu, Andrew Tang, De-An Huang, Yuke Zhu, and Anima Anandkumar.  Minedojo: Building open-ended embodied agents with internet-scale knowledge.  In _Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track_ , 2022.
  * Finn et al. [2016] Chelsea Finn, Sergey Levine, and Pieter Abbeel.  Guided cost learning: Deep inverse optimal control via policy optimization.  In _Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48_ , ICML’16, page 49–58. JMLR.org, 2016.
  * Fu et al. [2017] Justin Fu, Katie Luo, and Sergey Levine.  Learning robust rewards with adversarial inverse reinforcement learning.  _arXiv preprint arXiv:1710.11248_ , 2017.
  * Fu et al. [2018] Justin Fu, Avi Singh, Dibya Ghosh, Larry Yang, and Sergey Levine.  Variational inverse control with events: A general framework for data-driven reward definition.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Fu et al. [2020] Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine.  D4rl: Datasets for deep data-driven reinforcement learning.  _arXiv preprint arXiv:2004.07219_ , 2020.
  * Ge et al. [2023] Yuying Ge, Annabella Macaluso, Li Erran Li, Ping Luo, and Xiaolong Wang.  Policy adaptation from foundation model feedback, 2023.
  * Grauman et al. [2022] Kristen Grauman, Andrew Westbury, Eugene Byrne, Zachary Chavis, Antonino Furnari, Rohit Girdhar, Jackson Hamburger, Hao Jiang, Miao Liu, Xingyu Liu, et al.  Ego4d: Around the world in 3,000 hours of egocentric video.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 18995–19012, 2022.
  * Gupta et al. [2019] Abhishek Gupta, Vikash Kumar, Corey Lynch, Sergey Levine, and Karol Hausman.  Relay policy learning: Solving long-horizon tasks via imitation and reinforcement learning.  _arXiv preprint arXiv:1910.11956_ , 2019.
  * Hadfield-Menell et al. [2017] Dylan Hadfield-Menell, Smitha Milli, Pieter Abbeel, Stuart J Russell, and Anca Dragan.  Inverse reward design.  _Advances in neural information processing systems_ , 30, 2017.
  * Haldar et al. [2023] Siddhant Haldar, Jyothish Pari, Anant Rai, and Lerrel Pinto.  Teach a robot to fish: Versatile imitation from one minute of demonstrations.  _arXiv preprint arXiv:2303.01497_ , 2023.
  * Hejna and Sadigh [2022] Joey Hejna and Dorsa Sadigh.  Few-shot preference learning for human-in-the-loop rl.  In _Proceedings of the 6th Conference on Robot Learning (CoRL)_ , 2022\.
  * Ho and Ermon [2016] Jonathan Ho and Stefano Ermon.  Generative adversarial imitation learning.  _Advances in neural information processing systems_ , 29, 2016.
  * Hu and Sadigh [2023] Hengyuan Hu and Dorsa Sadigh.  Language instructed reinforcement learning for human-ai coordination.  In _40th International Conference on Machine Learning (ICML)_ , 2023\.
  * Kumar et al. [2019] Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine.  Stabilizing off-policy q-learning via bootstrapping error reduction.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Kumar et al. [2022] Aviral Kumar, Joey Hong, Anikait Singh, and Sergey Levine.  When should we prefer offline reinforcement learning over behavioral cloning?  _arXiv preprint arXiv:2204.05618_ , 2022.
  * Kwon et al. [2023] Minae Kwon, Sang Michael Xie, Kalesha Bullard, and Dorsa Sadigh.  Reward design with language models.  In _International Conference on Learning Representations (ICLR)_ , 2023.
  * Lee et al. [2021] Kimin Lee, Laura Smith, and Pieter Abbeel.  Pebble: Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training, 2021.
  * Lynch et al. [2022] Corey Lynch, Ayzaan Wahid, Jonathan Tompson, Tianli Ding, James Betker, Robert Baruch, Travis Armstrong, and Pete Florence.  Interactive language: Talking to robots in real time, 2022.
  * Miech et al. [2019] Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivic.  Howto100m: Learning a text-video embedding by watching hundred million narrated video clips.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 2630–2640, 2019.
  * Myers et al. [2021] Vivek Myers, Erdem Biyik, Nima Anari, and Dorsa Sadigh.  Learning multimodal rewards from rankings.  In _5th Annual Conference on Robot Learning_ , 2021.
  * Ng and Russell [2000] Andrew Y. Ng and Stuart J. Russell.  Algorithms for inverse reinforcement learning.  In _Proceedings of the Seventeenth International Conference on Machine Learning_ , ICML ’00, page 663–670, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc.  ISBN 1558607072.
  * Ni et al. [2022] Bolin Ni, Houwen Peng, Minghao Chen, Songyang Zhang, Gaofeng Meng, Jianlong Fu, Shiming Xiang, and Haibin Ling.  Expanding language-image pretrained models for general video recognition.  In _European Conference on Computer Vision (ECCV)_ , 2022.
  * Nottingham et al. [2023] Kolby Nottingham, Prithviraj Ammanabrolu, Alane Suhr, Yejin Choi, Hannaneh Hajishirzi, Sameer Singh, and Roy Fox.  Do embodied agents dream of pixelated sheep?: Embodied decision making using language guided world modelling.  _arXiv preprint arXiv:2301.12050_ , 2023.
  * Pomerleau [1988] Dean A Pomerleau.  Alvinn: An autonomous land vehicle in a neural network.  _Advances in neural information processing systems_ , 1, 1988.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , pages 8748–8763. PMLR, 2021.
  * Russakovsky et al. [2015] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  _International journal of computer vision_ , 115:211–252, 2015.
  * Sadigh et al. [2017] Dorsa Sadigh, Anca D. Dragan, S. Shankar Sastry, and Sanjit A. Seshia.  Active preference-based learning of reward functions.  In _Proceedings of Robotics: Science and Systems (RSS)_ , July 2017\.  doi: 10.15607/RSS.2017.XIII.053.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Seo et al. [2021] Younggyo Seo, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee.  State entropy maximization with random encoders for efficient exploration.  In _International Conference on Machine Learning_ , pages 9443–9454. PMLR, 2021.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Ulyanov et al. [2018] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky.  Deep image prior.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 9446–9454, 2018.
  * Xie et al. [2018] Saining Xie, Chen Sun, Jonathan Huang, Zhuowen Tu, and Kevin Murphy.  Rethinking spatiotemporal feature learning: Speed-accuracy trade-offs in video classification.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 305–321, 2018.
  * Yu et al. [2020] Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine.  Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning.  In _Conference on robot learning_ , pages 1094–1100. PMLR, 2020.
  * Ziebart et al. [2008] Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey.  Maximum entropy inverse reinforcement learning.  In _Proceedings of the 23rd National Conference on Artificial Intelligence - Volume 3_ , AAAI’08, page 1433–1438. AAAI Press, 2008.  ISBN 9781577353683.


# Combinatorial isoperimetric inequality for the free factor complex

Radhika Gupta  School of Mathematics, Tata Institute of Fundamental Research,
Mumbai<EMAIL_ADDRESS>
###### Abstract.

We show that the free factor complex of the free group of rank $n\geq 3$ does
not satisfy a $\operatorname{\text{combinatorial isoperimetric inequality}}$:
that is, for every $N\geq 3$, there is a loop of length 4 in the free factor
complex that only bounds discs containing at least $\mathrm{O(N)}$ triangles.
To prove the result, we construct a coarsely Lipschitz function from the
‘upward link’ of a free factor to $\mathbb{Z}$.

##  1\. Introduction

Webb [Web20] showed that arc complexes associated to almost all hyperbolic
surfaces do not admit a _$\mathrm{CAT}(0)$ metric with finitely many shapes_.
That is, they do not admit CAT(0) metrics which have finitely many isometry
types of simplices, in the induced metric. Moreover, he showed that the same
is true for the free splitting complex and the cyclic splitting complex
associated to the outer automorphism group $\mathrm{Out}(\mathbb{F})$ of a
free group $\mathbb{F}$ of rank $n\geq 6$. He proved this by showing that none
of the above complexes satisfy a _$\operatorname{\text{combinatorial
isoperimetric inequality}}$_. In contrast, he showed that the curve complex of
a hyperbolic surface satisfies a _linear_ $\operatorname{\text{combinatorial
isoperimetric inequality}}$. In this article, we show that the _free factor
complex_ follows suit with the other two hyperbolic
$\mathrm{Out}(\mathbb{F})$-complexes. Thus still leaving open the question: is
there a cocompact complex for $\mathrm{Out}(\mathbb{F})$, analogous to the
curve complex, that satisfies a linear combinatorial isoperimetric inequality?

The free factor complex $\mathcal{F}_{n}$ associated to $\mathbb{F}$ is the
simplicial complex whose vertices are conjugacy classes of proper free factors
of $\mathbb{F}$ and a collection $\\{A_{1},\ldots,A_{k}\\}$ of vertices spans
a simplex if $A_{1}\subset A_{2}\subset\cdots\subset A_{k}$, where the
inclusions are up to conjugation. We show:

######  Theorem A.

Let $\mathcal{F}_{n}$ be the free factor complex of free group of rank $n\geq
3$. There exists a family of loops $c_{N}$, for $N\in\mathbb{N}$, of
combinatorial length 4 in $\mathcal{F}_{n}^{(1)}$ such that the following
holds: whenever $P$ is a triangulation of a disc and $f\colon
P\to\mathcal{F}_{n}^{(2)}$ is a simplicial map with $f|_{\partial P}$ mapping
bijectively onto $c_{N}$, then $P$ must have at least $\mathrm{O(N)}$
triangles.

As a direct consequence of Webb’s main result [Web20, Theorem 1.1], we get

######  Corollary 1.1.

For $n\geq 3$, $\mathcal{F}_{n}$ does not admit a $\mathrm{CAT}(0)$ metric
with finitely many shapes.

We refer the reader to [Web20] for motivation to study CAT(0) metrics on these
spaces. The proof strategy for the theorem is as follows. For any $N>0$, we
construct an explicit loop $c_{N}$ of length 4 with vertices
$A_{0},A,A_{N},B$, where $A$ is a rank one free factor. See Figure 1. We show
that any path between $A_{0}$ and $A_{N}$ in the link of $A$ has length
bounded from below by $\mathrm{O(N)}$. We do this by defining (see Proposition
3.6) a coarsely Lipschitz function from the link of $A$ to $\mathbb{Z}$. Using
this, we conclude that at least $\mathrm{O(N)}$ triangles are needed to cap
off any disc with boundary $c_{N}$.

In fact, in Section 3 we define a family of coarsely Lipschitz functions from
the upward link, denoted $\mathcal{F}^{\uparrow}(A)$, of a free factor $A$ of
corank at least 3 to $\mathbb{Z}$. Choose a complementary free factor $B$, a
cyclically reduced filling element $w$ in $B$ that is not a power, and a
primitive element $b$ in $B$. Then we define
$\Psi_{w,b,B}\colon\mathcal{F}^{\uparrow}(A)\to\mathbb{Z}$ to roughly measure
how much $b$ gets conjugated by $w$, in other words how much $b$ twists about
$w$, in a basis of $\mathbb{F}$ that contains a basis of
$X\in\mathcal{F}^{\uparrow}(A)$ as a subbasis. Proposition 3.5 is the main
technical lemma proving the coarse Lipshitzness of the above function. It uses
the ‘active interval lemma’ [BF14b] and understanding of unfolding paths
[BF14a] in relative outer space.

$[\langle a\rangle]$
---
$[\langle a,w^{N}bw^{-N}\rangle]$
---
$[\langle a,b\rangle]$
---
$[\langle b\rangle]$
---
Figure 1. The loop $c_{N}$.

#### Acknowledgments

The author would like to thank Richard Webb for asking her this question and
useful discussions. She is grateful to Mladen Bestvina for sharing his ideas
and she would also like to thank Jean Pierrre Mutanguha for reading a draft.
The author was supported by the Department of Atomic Energy, Government of
India, under project no.12-R&D-TIFR-5.01-0500 and also by an endowment of the
Infosys Foundation.

##  2\. Background

###  2.1. Combinatorial isoperimetric inequalities

We recall some definitions from [Web20].

Let $P$ and $K$ be simplicial complexes. A _simplicial map_ is a map $c\colon
P\to K$ that sends each simplex of $P$ to a simplex of $K$ by a linear map
taking vertices to vertices. Let $K^{(i)}$ denote the $i$-skeleton of $K$. A
_combinatorial loop_ $c$ in $K$ is a sequence of vertices
$(v_{1},\ldots,v_{k})$ in $K$ where $v_{k}$ is adjacent (or equal) to $v_{1}$
and $v_{i}$ is adjacent (or equal) to $v_{i+1}$ for $1\leq i\leq j-1$. The
_combinatorial length_ $l_{C}(c)$ of $c$ is equal to $k$. A combinatorial loop
$c$ of combinatorial length $k$ can also be described as a simplicial map
$c\colon P\to K$, where $P$ is a triangulation of $S^{1}$ with $k$
1-simplices.

Let $D^{2}$ be the closed unit disc with boundary $S^{1}$. We say that a
combinatorial loop $c$ can be _capped off with at most $m$ triangles_ if there
is a triangulation $P$ of $D^{2}$ into at most $m$ 2-simplices and a
simplicial map $c^{\prime}\colon P\to K$ such that $c^{\prime}|_{S^{1}}=c$.

A function $f\colon\mathbb{N}\to\mathbb{N}$ is called a _combinatorial
isoperimetric bound_ for $K$ if every combinatorial loop $c$ in $K$ can be
capped off with at most $f(l_{C}(c))$ many triangles. We say $K$ satisfies a
_linear $\operatorname{\text{combinatorial isoperimetric inequality}}$_ if
there exists a combinatorial isoperimetric bound $f$ for $K$ such that
$f(n)=\mathrm{O(n)}$. We say _$K$ satisfies no combinatorial isoperimetric
inequality_ if no combinatorial isoperimetric bound for $K$ exists.

###  2.2. Outer space

We say an $\mathbb{R}$-tree is an $\mathbb{F}$-tree if it admits a non-trivial
action of $\mathbb{F}$. We denote by $\mathcal{O}$ the (unprojectivized) Outer
space of $\mathbb{F}$, defined in [CV86], consisting of minimal, metric,
simplicial $\mathbb{F}$-trees up to equivariant isometry. Let $A$ be a free
factor of $\mathbb{F}$. Let $\mathcal{O}(\mathbb{F},A)$ be the unprojectivised
_Outer space relative to $A$_ ([GL07]), that is, the space of minimal, metric,
simplicial $\mathbb{F}$-trees with trivial edge stabilizers and vertex
stabilizers conjugates of $A$, up to equivariant isomorphism. Let
$\mathbb{P}\mathcal{O}(\mathbb{F},A)$ denote the projectivized outer space
relative to $A$. For $T\in\mathcal{O}(\mathbb{F},A)$, the _covolume of $T$_ is
the sum of the lengths of edges of $T/\mathbb{F}$, which is a finite graph.
Then we think of points in $\mathbb{P}\mathcal{O}(\mathbb{F},A)$ as covolume 1
trees.

Let $\mathcal{FS}(\mathbb{F},A)$ be the free splitting graph relative to $A$
([HM14]). A vertex is given by minimal, simplicial $\mathbb{F}$-tree $T$,
without the metric, with trivial edge stabilizers and such that $A$ is
elliptic in $T$, up to equivariant isomorphism. Two such trees $T_{1},T_{2}$
are joined by an edge if there is an equivariant collection of edges in
$T_{1}$ that can be collapsed to obtain $T_{2}$. There is a natural function
from $\mathbb{P}\mathcal{O}(\mathbb{F},A)$ to $\mathcal{FS}(\mathbb{F},A)$,
given by forgetting the metric on the tree, such that the image is contained
in the vertex set of $\mathcal{FS}(\mathbb{F},A)$. The _vertex group system_
of a free splitting of $\mathbb{F}$ is the collection of conjugacy classes of
its vertex stabilizers.

###  2.3. Train track structure and morphism

Let $\Gamma$ be a simplicial $\mathbb{F}$-tree. A direction $d$ based at
$p\in\Gamma$ is a component of $\Gamma-\\{p\\}$. A turn is an unordered pair
of directions based at the same point. An _illegal turn structure_ on $\Gamma$
is an equivalence relation on the set of directions at each point
$p\in\Gamma$. The classes of this relation are called _gates_. A turn
$(d,d^{\prime})$ is _legal_ if $d$ and $d^{\prime}$ do not belong to the same
gate. If in addition there are at least two gates at every vertex of $\Gamma$,
then the illegal turn structure is called a _train track structure_. A path is
legal if it only crosses legal turns.

Given two $\mathbb{F}$-trees $\Gamma$ and $\Gamma^{\prime}$, an
$\mathbb{F}$-equivariant map $f\colon\Gamma\to\Gamma^{\prime}$ is called a
_morphism_ if every segment of $\Gamma$ can be subdivided into finitely many
subintervals such that $f$ is an isometry when restricted to each subinterval.
A morphism between $\mathbb{F}$-trees induces a _train track structure_ on the
domain $\Gamma$. A morphism is called _optimal_ if there are at least two
gates at each point of $\Gamma$. See [BF14a, BF14b] for more details.

###  2.4. Folding

Let $T,T^{\prime}\in\mathcal{O}(\mathbb{F},A)$ . A _folding path with its
natural parametrization_ $(T_{t})_{t\in\mathbb{R}^{+}}$, guided by an optimal
morphism $f\colon T\to T^{\prime}$ can be defined as follows (see [BF14a,
Section 2] and [GL07, Section 3]): Given $a,b\in T$ with $f(a)=f(b)$, the
_identification time_ of $a$ and $b$ is defined as
$\tau(a,b)=\sup_{x\in[a,b]}d_{T^{\prime}}(f(x),f(a))$. Define
$L:=\frac{1}{2}\operatorname{BBT}(f)$, where $\operatorname{BBT}$ is the
bounded backtracking constant for $f$. For each $t\in[0,L]$, one defines an
equivalence relation $\sim_{t}$ by $a\sim_{t}b$ if $f(a)=f(b)$ and
$\tau(a,b)<t$. The tree $T_{t}$ is then a quotient of $T$ by the equivalence
relation $\sim_{t}$. The authors of [GL07] prove that for each $t\in[0,L]$,
$T_{t}$ is an $\mathbb{R}$-tree. The collection of trees $(T_{t})_{t\in[0,L]}$
comes equipped with $\mathbb{F}$-equivariant morphisms $f_{s,t}\colon T_{t}\to
T_{s}$ for all $t<s$ and these maps satisfy the semi-flow property: for all
$r<s<t$, we have $f_{t,s}\circ f_{s,r}=f_{t,r}$. Moreover $T_{L}=T^{\prime}$
and $f_{L,0}=f$.

Let $\overline{T},\overline{T^{\prime}}$ be the covolume 1 representatives of
$T$ and $T^{\prime}$ in $\mathbb{P}\mathcal{O}(\mathbb{F},A)$. Then a folding
path $({S_{t}})_{t}$ between them is the projection of the folding path
between $T$ and $T^{\prime}$. In other words, $S_{t}$ is obtained by rescaling
$T_{t}$ to covolume 1.

######  Lemma 2.1 ( [BF14b, Lemma 4.1, Corollary A.3]).

Let $f\colon T\to T^{\prime}$ be an optimal morphism between two points
$T,T^{\prime}$ in $\mathbb{P}\mathcal{O}(\mathbb{F},A)$. Then
$d_{\mathrm{FS}(\mathbb{F},A)}(T,T^{\prime})$ is bounded above by a linear
function of cardinality of $f^{-1}(y)$ for any point $y\in T^{\prime}$.

###  2.5. Unfolding

In [BF14a], Bestvina and Feighn analyzed in detail folding and unfolding paths
in Outer space $\mathcal{O}$ of a free group. The latter are folding paths
traversed in reverse. The following is a relative version of their result and
is used in the proof of the active interval lemma in the next section.

######  Theorem 2.2 (cf. [BF14a, Theorem 4.2]).

Let $T_{t}$, $t\in[0,\delta]$ be a folding path in $\mathcal{O}(\mathbb{F},A)$
with its natural parametrization. There is a partition
$0=t_{0}<t_{1}<\cdots<t_{N}=\delta$ of $[0,\delta]$ such that the restriction
of $T_{t}$ to each $[t_{i},t_{i+1}]$ is given by folding an _orbit of a
gadget_ in $T_{t}$.

We briefly describe why the proof of the above result in Outer space works in
relative outer space as well. Let $N$ be a small neighborhood of a vertex $v$
in $T_{t}$. Then $N$ is a wedge of (infinitely many) arcs with wedge point
$v$. The above theorem says that for small $\epsilon$, the pre-image
$N_{\epsilon}$ of $N$ in $T_{t-\epsilon}$ is a tree that comes with a height
function and a collection of _widgets_ (see Figure 2 and [BF14a, Definition
4.1]). A widget is topologically a cone on finitely many points and a _gadget_
is a finite union of widgets. In $N_{\epsilon}$, the folding happens at
vertices with two gates where one gate is a single direction. The picture
resembles the scenario when we are in the middle of folding a collection of
edges based at a vertex in Stallings folding process.

Note that in the case of a folding path in Outer space of free group we get a
collection of finitely many widgets in $N_{\epsilon}$, which is used
essentially in the proof of [BF14a, Theorem 4.2]. That will no longer be true
for folding paths in relative outer space as the trees have infinite valence
vertices. However, it is still true that $N_{\epsilon}$ will be a collection
of finitely many _orbits_ of widgets, which are topologically still cones on
finitely many points. This is because edge stabilizers are trivial in $T_{t}$
and hence the pre-image of an edge under folding is a finite collection of
edges. Thus the unfolding process in relative outer space looks basically the
same as that in Outer space.

$0$
---
$\epsilon$
---
Figure 2. Widget

###  2.6. Active intervals lemma

Let $T\in\mathbb{P}\mathcal{O}(\mathbb{F},A)$ with a train track structure.
Let $w\in\mathbb{F}$ be a cyclically reduced element that is not a power of
another element and it is not contained in $A$, up to conjugation. The minimal
subtree of $w$ in $T$ is the axis of $w$ and the core of $T/\langle w\rangle$
is a circle, denoted $C_{w}(T)$. Since the quotient map $q\colon T\to
T/\langle w\rangle$ does not collapse any edges, the train track structure on
$T$ induces a train track structure on $T/\langle w\rangle$. The restriction
of the train track structure (resp. metric) on $T$ to the axis of $w$ defines
a train track structure (resp. metric) on $C_{w}(T)$ as well.

######  Lemma 2.3 (cf. [BF14b, Lemma 3.2]).

Given a folding path $T_{t}$ in $\mathbb{P}\mathcal{O}(\mathbb{F},A)$,
$t\in[\alpha,\delta]$ and a cyclically reduced word $w\in\mathbb{F}$ not
contained in any conjugate of $A$, the interval $[\alpha,\delta]$ can be
subdivided into three segments $[\alpha,\beta),[\beta,\gamma),[\gamma,\delta]$
so that:

  1. (1)

for every $t$ in the first segment $[\alpha,\beta)$, $C_{w}(T_{t})$ has an
illegal turn,

  2. (2)

for every $t$ in the middle segment $[\beta,\gamma)$, $C_{w}(T_{t})$ has
volume at most 2, and there are no illegal turns,

  3. (3)

for every $t$ in in the last segment $[\gamma,\delta]$, $C_{w}(T_{t})$ has a
legal segment of length at least 2.

For completeness, we include a proof which is essentially the same as the
original proof in the setting of Outer space.

###### Proof.

Let $J$ be the set of times $t_{0}$ in $[\alpha,\delta]$ such that
$C_{w}(T_{t_{0}})$ contains an illegal turn. We first show that $J$ is an open
set. Let $t_{0}$ be in $J$. If $t_{0}\neq\delta$, then it is clear from the
definition of folding that $[t_{0},t_{0}+\epsilon)\subset J$ for small
$\epsilon>0$. We need to show that $(t_{0}-\epsilon,t_{0}]$ is also in $J$. We
will show that $C_{w}(T_{t_{0}-\epsilon})$ also has an illegal turn. Let $v$
be a vertex of $C_{w}(T_{t_{0}})$ of valence two and one gate. Let
$\overline{T}_{t}$ be the quotient of $T_{t}$ by the action of $w$. Let $N$ be
a small neighborhood of $v$ in $\overline{T}_{t}$. Also let
$\overline{N}_{\epsilon}$ be the pre-image of $N$ under the induced map
$\overline{T}_{t_{0}-\epsilon}\to\overline{T}_{t_{0}}$. All the edges in a
widget in $\overline{N}_{\epsilon}$ map to a small segment with one end point
$v$. If this segment is in $C_{w}(T_{t_{0}})$, then the widget is called
_essential_ , and _inessential_ otherwise. Similarly, an edge below height 0
in $\overline{N}_{\epsilon}$ is essential if it’s image is in
$C_{w}(T_{t_{0}})$ and inessential otherwise. In our case, there are two
essential edges and widgets in $\overline{N}_{\epsilon}$.

Let $\overline{N}_{\epsilon}^{\prime}$ be the hull of all essential edges and
widgets, together with edges above essential widgets. Using the observations
made in the detailed proof of [BF14b, Lemma 3.2], we get three possibilities
for $\overline{N}_{\epsilon}^{\prime}$ as shown in Figure 3. Since
$\overline{N}_{\epsilon}^{\prime}$ is contained in
$C_{w}(T_{t_{0}-\epsilon})$, we find an illegal turn in
$C_{w}(T_{t_{0}-\epsilon})$. Thus $J$ is an open set. Moreover, $J$ must be an
initial segment. Otherwise, there would be a $t_{0}\notin J$ but
$(t_{0},t_{0}+\epsilon)\subset J$. However, a local fold cannot produce an
illegal turn at a valence two vertex.

To finish the proof, we have to consider the last segment. Suppose that
$C_{w}(T_{t_{0}})$ has a legal segment of length at least 2. For this argument
use the natural parametrization of folding paths and work in unprojectivized
relative outer space. After time $\epsilon$, the covolume of
$T_{t_{0}+\epsilon}$ is at most $1-\epsilon$. The legal segment in
$C_{w}(T_{t_{0}})$ of length $L\geq 2$ may lose a piece of length $\epsilon$
at each end. Therefore, after rescaling by at least $1/(1-\epsilon)$ to bring
back the covolume of $T_{t_{0}+\epsilon}$ to 1, the length of the legal
segment is at least $(L-2\epsilon)/(1-\epsilon)$, which is at least 2 for
$L\geq 2$. ∎

$\alpha$
---
$\beta$
---
$\alpha$
---
$\beta$
---
$v$
---
$\alpha$
---
$\beta$
---
$\alpha$
---
$\beta$
---
$v$
---
$\alpha$
---
$\beta$
---
$\alpha$
---
$\beta$
---
$v$
---
Figure 3. Three possibilities for $\overline{N}_{\epsilon}^{\prime}$.

##  3\. Coarsely Lipschitz function to $\mathbb{Z}$

Let $A$ be a free factor of $\mathbb{F}$ and let $B$ be a complementary free
factor, that is, $\mathbb{F}=A\ast B$. Choose a filling element $w\in B$, that
is, $w$ is not contained in any proper free factor of $B$. Also choose $w$
such that it is cyclically reduced and not a power of another element. Choose
$b\in B$ primitive, that is, a basis element. Let $\mathcal{F}^{\uparrow}(A)$
be the subcomplex of $\mathcal{F}_{n}$ whose vertices are given by conjugacy
classes of free factors that properly contain $A$ up to conjugation. In other
words, $\mathcal{F}^{\uparrow}(A)$ is the ‘upward link’ of the vertex $A$ in
$\mathcal{F}_{n}$. The _corank_ of $A$ is the rank of any complementary free
factor of $A$.

In this section, we will define a coarsely Lipschitz function
$\Psi_{w,b,B}\colon\mathcal{F}^{\uparrow}(A)\to\mathbb{Z}$ and use it to prove
our main theorem in the next section.

######  Lemma 3.1.

If corank of $A$ is at least 3, then $\mathcal{F}^{\uparrow}(A)$ is connected.

###### Proof.

Let $G$ be a marked metric graph in $\mathbb{P}\mathcal{O}$ such that $G$ has
a subgraph $H$ with fundamental group $A$. Let $v$ be a vertex of this
subgraph. Let $P$ and $Q$ be two subgraphs of $G$ that properly contain $H$
and have rank at least $1+\text{rank}(A)$. Then they determine two free
factors $\dot{P}$ and $\dot{Q}$ in $\mathcal{F}^{\uparrow}(A)$. We claim that
$d_{\mathcal{F}^{\uparrow}(A)}(\dot{P},\dot{Q})\leq 4$ (see [BF14a, Section
3]). Indeed, let $P^{\prime}$, respectively $Q^{\prime}$, be a subgraph of $G$
containing $P$, respectively $Q$, and all edges of $G$ except one. Since
$G\setminus H$ has rank at least 3, $P^{\prime}\cap Q^{\prime}$ contains $H$
and another circle based at $v$. Let $R$ be the union of $H$ and this circle.
Then $\dot{P},\dot{P^{\prime}},\dot{R},\dot{Q^{\prime}},\dot{Q}$ is a path of
length 4 in $\mathcal{F}^{\uparrow}(A)$. Let $\Pi(G)$ denote the collection of
free factors in $\mathcal{F}^{\uparrow}(A)$ arising from subgraphs of $G$
containing $H$. Then we just showed that $\Pi(G)$ is a connected set of
diameter at most 4.

Now for $X,Y\in\mathcal{F}^{\uparrow}(A)$, let $G_{X}$ and $G_{Y}$ be two
marked metric graphs in $\mathbb{P}\mathcal{O}$ such that they both have
subgraphs with fundamental group $A$ and $X\in\Pi(G_{X})$, $Y\in\Pi(G_{Y})$.
By [BF14a, Proposition 2.5], there is a folding path between $G_{X}$ and
$G_{Y}$ with an invariant subgraph of fundamental group $A$. We claim that the
folding path maps to a path connecting $X$ and $Y$ in
$\mathcal{F}^{\uparrow}(A)$. We may assume that the folding path is obtained
by a continuous parametrization of Stallings foldings (see [BF14a, Section
2.2A]). If one performs an elementary Stallings fold on $G_{X}$, that is fold
two edges to obtain a new marked graph $G^{\prime}$, then $\Pi(G_{X})$ and
$\Pi(G^{\prime})$ intersect non-trivially. Thus we can produce a path joining
$X$ and $Y$ in $\mathcal{F}^{\uparrow}(A)$. ∎

Let $X$ be the conjugacy class of a free factor in
$\mathcal{F}^{\uparrow}(A)$. For any
$T\in\mathbb{P}\mathcal{O}(\mathbb{F},X)$, let $e$ denote the base point, that
is, the vertex fixed by $A$. For $g\in\mathbb{F}$, let $\mathrm{a}_{T}(g)$
denote the axis or fixed point set of $g$ acting on $T$ and $\tau_{T}(g)$
denote the translation length.

######  Lemma 3.2.

The element $w$ is a hyperbolic isometry of any
$T\in\mathbb{P}\mathcal{O}(\mathbb{F},X)$, where
$X\in\mathcal{F}^{\uparrow}(A)$.

###### Proof.

By Kurosh subgroup theorem, the intersection of two free factors of
$\mathbb{F}$ is a free factor. Therefore, $X\cap B$, if non-empty is a free
factor of $\mathbb{F}$ and in particular of $B$ and $X$. Suppose some
conjugate of $w$ is contained in $X$, then up to conjugation $w$ would be
contained in a proper free factor of $B$, which is a contradiction to $w$
being filling in $B$. Therefore, $w$ is not contained in $X$ up to
conjugation. Hence, $w$ is hyperbolic in $T$. ∎

Recall $b\in B$ is a fixed primitive element. Let $L_{T}(b)$ be the shortest
path from $e$ to $\mathrm{a}_{T}(b)$ in $T$. We will call it the _leg of $b$_
in $T$. Let

$\Phi_{w,b,B}(T):=\left\lceil\frac{\mathrm{diam}_{T}(L_{T}(b)\cap\mathrm{a}_{T}(w))}{\tau_{T}(w)}\right\rceil.$

Informally, $\Phi_{w,b,B}(T)$ is the number of fundamental domains of $w$
crossed by the leg of $b$ in $T$. See Figure 4 for an illustration of the
definition. For comparison, Clay–Pettet [CP12] define the _relative twist of
$T$ and $b$ relative to $w$_ as the supremum of the number of fundamental
domains of $w$ in the intersection of the axis of $w$ and axes of all
conjugates of $b$ in $T$. In our setting, this number is one since $b\in B$ is
primitive and $w$ is filling in $B$.

$e$
---
$we$
---
$w^{2}e$
---
$w^{3}e$
---
$x$
---
$wx$
---
$w^{2}x$
---
$w^{6}x$
---
$\mathrm{a}_{T}(w)$
---
$\mathrm{a}_{T}(b)$
---
$L_{T}(b)$
---
Figure 4. In this figure $\Phi_{w,b,B}(T)=6$.

######  Example 3.3.

This example is to illustrate the setup in the above definition. Let
$\mathbb{F}=\langle a,b,c,d\rangle$ and $w=c^{2}b^{2}d^{2}c^{2}$. It is easy
to check using Whitehead’s algorithm that $w$ is filling in $\langle
b,c,d\rangle$. Now consider a new basis $\\{a,x,c,d\\}$ where
$b=d^{-1}c^{-1}xcd$. Then in the new basis $w=c^{2}d^{-1}c^{-1}xcd^{3}c^{2}$.
Let $T$ be the Bass-Serre tree of a graph of groups with one vertex group
stabilized by $\langle a\rangle$ and three loops labeled $x,c,d$. Then in $T$,
the axis of $w$ and $b$ are disjoint.

######  Example 3.4.

Let $\mathbb{F}=\langle a,b,c,d\rangle$ and $w=b^{2}c^{2}d^{2}\in\langle
b,c,d\rangle$. It is easy to check using Whitehead’s algorithm that $w$ is
filling in $\langle b,c,d\rangle$. Let $A=\langle a\rangle,B=\langle
b,c,d\rangle$ and let $X=[\langle a,b\rangle]$ and $Y=[\langle
a,w^{N}bw^{-N}\rangle]$ be two points in $\mathcal{F}^{\uparrow}(A)$ for some
$N>0$. Let $T_{X}$ be the Bass-Serre tree of the graph of groups with one
vertex stabilized by $X$ and two loops labeled by $c$ and $d$. Similarly, let
$T_{Y}$ be the Bass-Serre tree of the graph of groups with one vertex
stabilized by $Y$ and two loops labeled $w^{N}cw^{-N}$ and $w^{N}dw^{-N}$.
Then $\Phi_{w,b,B}(T_{X})=0$ and $\Phi_{w,b,B}(T_{Y})=N$.

######  Proposition 3.5.

There exists a constant $C>0$, depending only on the rank $n$ of $\mathbb{F}$,
such that the following holds: For $X\in\mathcal{F}^{\uparrow}(A)$, let $T$
and $T^{\prime}$ be two free splittings in $\mathcal{FS}(\mathbb{F},X)$ with
vertex group systems equal to $X$. Then
$|\Phi_{w,b,B}(T)-\Phi_{w,b,B}(T^{\prime})|\leq C$.

###### Proof.

First suppose that $T$ and $T^{\prime}$ are distance one apart in
$\mathcal{FS}(\mathbb{F},X)$, that is, there is a collapse map from $T$ to
$T^{\prime}$. Since $w$ is hyperbolic in both $T$ and $T^{\prime}$, the
collapse map changes the number of fundamental domains of $w$ crossed by the
leg of $b$ by at most one. Therefore,
$|\Phi_{w,b,B}(T)-\Phi_{w,b,B}(T^{\prime})|\leq 1$.

Now consider $T^{\prime}$ as a point in $\mathbb{P}\mathcal{O}(\mathbb{F},X)$,
with some metric and, up to changing $T$ to another tree in a simplex in
$\mathbb{P}\mathcal{O}(\mathbb{F},X)$ containing $T$, consider an optimal
morphism $f\colon T\to T^{\prime}$, where $T$ has the pull back metric. Let
$(T_{t})_{t\in[0,\delta]}$ be a folding path with natural parametrization
guided by $f$ where $T_{0}=T$ and $T_{\delta}=T^{\prime}$. Note that
$C_{w}(T_{t})$ is a loop. Let $\mathrm{a}_{t}(b)$ and $\mathrm{a}_{t}(w)$
denote the axis of $b$ and $w$ in $T_{t}$ and let $\tau_{t}(w)$ be the
translation length of $w$ in $T_{t}$. By Lemma 2.3, the folding path
$(T_{t})_{t}$ can be broken into three intervals.

  * •

For every $t$ in the first interval, $C_{w}(T_{t})$ has an illegal turn.
Therefore, the only folding between edges of $\mathrm{a}_{t}(w)$ happens at
these illegal turns. Let $E$ be any edge of $T_{t}$ not in
$\mathrm{a}_{t}(w)$. Under the folding map, $E$ cannot fold over
$\mathrm{a}_{t}(w)$ for a length more than $\tau_{t}(w)$ because
$C_{w}(T_{t})$ has an illegal turn.

  * •

For every $t$ in the last interval, $C_{w}(T_{t})$ has a legal segment of
length at least 2. Then any edge of $T_{t}$ again cannot fold over
$\mathrm{a}_{t}(w)$ for a length more than $\tau_{t}(w)$.

We claim that $|\Phi_{w,b,B}(T_{t})-\Phi_{w,b,B}(T_{s})|$ is uniformly bounded
for $s,t$ both in the first interval or both in the last interval. Let
$f_{s,t}\colon T_{t}\to T_{s}$ be the morphism induced by the folding path.
For $T_{t}$, let $G_{t}$ denote the quotient graph under the action of
$\mathbb{F}$. The fundamental group of $G_{t}$, as a graph of groups, is a
free product $X*F_{m}$, where $m$ is the corank of $X$. Choose a maximal tree
in $G_{t}$. Then the edges not in this maximal tree correspond to a basis for
$F_{m}$. Fix one such partial basis coming from $G_{t}$ and one from $G_{s}$.

Since an edge of $T_{t}$ folds over at most one fundamental domain of $w$, we
get that the image under $f_{s,t}^{*}$ of a basis element of $\pi_{1}(G_{t})$,
as chosen above, acquires a suffix or prefix $w^{N+1}$ for $N$ at most the
number of edges in a maximal tree in $G_{t}$ which is at most $2n-3$.
Therefore, $f_{s,t}^{*}$ conjugates $b$ by $w^{N+1}$, if at all, for uniformly
bounded $N$. This implies that the difference in the number of fundamental
domains of $w$ crossed by the leg of $b$, in $T_{t}$ and $T_{s}$, is uniformly
bounded. Lastly,

  * •

for any $t$ in the middle segment, $C_{w}(T_{t})$ is a legal loop of length at
most two.

In addition, we claim that it crosses the orbit of every edge of $T_{t}$ at
least twice. Indeed, if $C_{w}(T_{t})$ does not cross the orbit of an edge
$E$, then $w$ is contained in a proper free factor $Y$ given by the
fundamental group of $G_{t}\setminus\\{E\\}$. Then $w$ is contained in $Y\cap
B$, which is a proper free factor of $B$, a contradiction. If $C_{w}(T_{t})$
crosses the orbit of some edge only once, then $w$ will be a primitive
element, again a contradiction. Thus, $C_{w}(T_{t})$ crosses the orbit of
every edge exactly twice. Now for $t<s$ in the middle segment, $C_{w}(T_{t})$
is a legal loop that maps to another legal loop $C_{w}(T_{s})$ and they cross
the orbit of every edge of $T_{t}$, resp. $T_{s}$, exactly twice. Therefore,
the pre-image of an edge of $T_{s}$ is a single edge and by Lemma 2.1 they are
uniformly bounded distance apart in $\mathcal{FS}(\mathbb{F},X)$. Now by the
first para of this proof, we get that
$|\Phi_{w,b,B}(T_{t})-\Phi_{w,b,B}(T_{s})|$ is uniformly bounded for $t,s$ in
the middle segment.

Combining the behaviour in the three segments of the folding path from $T$ to
$T^{\prime}$, we conclude that $|\Phi_{w,b,B}(T)-\Phi_{w,b,B}(T^{\prime})|$ is
uniformly bounded. ∎

We are now ready to define a coarsely Lipschitz function from
$\mathcal{F}^{\uparrow}(A)\to\mathbb{Z}$. Choose a complementary free factor
$B$ (of $A$) of rank at least 3, and, choose $b,w\in B$ such that $b$ is
primitive in $B$ and $w$ is a cyclically reduced filling element in $B$ that
is not a power of another element. Define
$\Psi_{w,b,B}\colon\mathcal{F}^{\uparrow}(A)\to\mathbb{Z}$ by setting
$\Psi_{w,b,B}(X)$ equal to $\Phi_{w,b,B}(T)$ for any
$T\in\mathcal{FS}(\mathbb{F},X)$ with vertex group system equal to
$X\in\mathcal{F}^{\uparrow}(A)$.

######  Proposition 3.6.

For a free factor $A$ of $\mathbb{F}$ of corank at least 3, the function
$\Psi_{w,b,B}\colon\mathcal{F}^{\uparrow}(A)\to\mathbb{Z}$ is coarsely
Lipschitz.

###### Proof.

The function is coarsely well-defined by Proposition 3.5. Consider two
vertices $X$ and $Y$ in $\mathcal{F}^{\uparrow}(A)$ joined by an edge, with
$Y\subset X$, up to conjugation. Pick $T_{X}\in\mathcal{FS}(\mathbb{F},X)$
with vertex group system $X$ and $T_{Y}\in\mathcal{FS}(\mathbb{F},Y)$ with
vertex group system $Y$, such that there is a proper subtree of $T_{Y}$ which
is collapsed to obtain $T_{X}$. Since $w$ is hyperbolic in both $T_{X}$ and
$T_{Y}$, under the collapse map a fundamental domain of the axis of $w$ in
$T_{Y}$ maps to a unique non-degenerate fundamental domain of the axis of $w$
in $T_{Y}$. Thus $|\Phi_{w,b,B}(T_{X})-\Phi_{w,b,B}(T_{Y})|\leq 1$ and hence
$\Psi_{w,b,B}$ is a coarsely Lipschitz function. ∎

##  4\. Proof of main theorem

We are now ready to prove the main theorem.

######  Theorem 4.1.

Let $\mathcal{F}_{n}$ be the free factor complex of free group of rank $n\geq
4$. There exists a family of loops $c_{N}$ of combinatorial length 4 in
$\mathcal{F}_{n}^{(1)}$ such that the following holds: whenever $P$ is a
triangulation of a disc and $f\colon P\to\mathcal{F}_{n}^{(2)}$ is a
simplicial map with $f|_{\partial P}$ mapping bijectively onto $c_{N}$, then
$P$ must have at least $\mathrm{O(N)}$ triangles.

###### Proof.

Let $\mathbb{F}=\langle a,b,a_{3},\ldots,a_{n}\rangle$. Let $w\in B=\langle
b,a_{3},\ldots,a_{n}\rangle$ be cyclically reduced, filling in $B$ and not a
power of another element. For any $N>0$, let $c_{N}$ be the length 4 loop in
$\mathcal{F}_{n}$ with vertices $A_{0}=[\langle a,b\rangle],A_{1}=[\langle
a\rangle],A_{N}=[\langle a,w^{N}bw^{-N}\rangle],A_{2}=[\langle b\rangle]$ (see
Figure 1). Let $P$ be a triangulation of a disc $D^{2}$ and $c\colon
P\to\mathcal{F}_{n}$ a simplicial map such that $c|_{\partial D^{2}}=c_{N}$.

Since $A_{1}$ is a rank one free factor, $\mathcal{F}^{\uparrow}(A_{1})$ is
the full link of $A_{1}$ in $\mathcal{F}$. By Proposition 3.6, the function
$\Psi_{w,b,B}\colon\mathcal{F}^{\uparrow}(A_{1})\to\mathbb{Z}$ is coarsely
Lipschitz and by Example 3.4, $\Psi_{w,b,B}(A_{0})$ is coarsely $0$ and
$\Psi_{w,b,B}(A_{N})$ is coarsely $N$. Thus, the distance between $A_{0}$ and
$A_{N}$ in the link of $A_{1}$ is at least $c_{1}N+c_{2}$ for some uniform
constants $c_{1},c_{2}>0$.

Let $x_{i}$ be the pre-image of $A_{i}$ on the boundary of the disc $D$. Then
in $P$, there is an edge path from $x_{0}$ to $x_{N}$ of length at least
$c_{1}N+c_{2}$. If we count every triangle thrice, then we count every edge at
least once. Therefore, there are at least $(c_{1}N+c_{2})/3$ many triangles in
$P$. Thus, for arbitrary $N>0$, the length 4 loop $c_{N}$ requires at least
$\mathrm{O(N)}$ triangles to be capped off. ∎

### The case $n=3$

Let $\mathbb{F}_{3}=\langle a,b,c\rangle$, $A=[\langle a\rangle]$ and $w$
filling, cyclically reduced element in $\langle b,c\rangle$ that is not a
power of another element. The complex $\mathcal{F}^{\uparrow}(A)$ is not
connected as a subset of $\mathcal{F}_{3}$ since all the free factors
containing $A$ are rank 2. We can define a different structure on
$\mathcal{F}^{\uparrow}(A)$ as follows: two free factors $[\langle
a,x\rangle]$ and $[\langle a,y\rangle]$ in $\mathcal{F}^{\uparrow}(A)$ are
joined by an edge if $\\{a,x,y\\}$ is a basis for $\mathbb{F}_{3}$. An
argument similar to Lemma 3.1 using folding paths, shows that
$\mathcal{F}^{\uparrow}(A)$ is connected.

For $X\in\mathcal{F}^{\uparrow}(A)$, there is only one free splitting $T_{X}$
with vertex group system equal to $X$, up to equivariant isomorphism.
Therefore, we set $\Psi_{w,b,B}(X)$ equal to $\Phi_{w,b,B}(T_{X})$. Now we
show that $\Psi_{w,b,B}\colon\mathcal{F}^{\uparrow}(A)\to\mathbb{Z}$ is a
Lipschitz function. Let $X$ and $Y$ be distance one in
$\mathcal{F}^{\uparrow}(A)$, that is we may assume $X=[\langle
a,x\rangle],Y=[\langle a,y\rangle]$ and $\\{a,x,y\\}$ is a basis of
$\mathbb{F}_{3}$. Let $T_{X}$ be the Bass-Serre tree of the graph of groups
with vertex group $X$ and edge labeled $y$, and vice versa for $T_{Y}$. Let
$T$ be a common refinement of $T_{X}$ and $T_{Y}$ described at the Bass-Serre
tree of the graph of groups with one vertex stabilized by $[\langle a\rangle]$
and two loops labeled $x$ and $y$. Then there are collapse maps $p_{X}\colon
T\to T_{X}$ and $p_{Y}\colon T\to T_{Y}$. Defining $\Phi_{w,b,B}(T)$ as
before, we see that $|\Phi_{w,b,B}(T)-\Phi_{w,b,B}(T_{X})|\leq 1$ and same for
$Y$ since $w$ is hyperbolic in all three trees. Therefore,
$|\Phi_{w,b,B}(T_{Y})-\Phi_{w,b,B}(T_{X})|\leq 2$ which implies that
$\Psi_{w,b,B}$ is Lipschitz.

Now to complete the proof of the main theorem, we observe that if $X$ and $Y$
are distance one in $\mathcal{F}^{\uparrow}(A)$, then they are distance at
most 4 in $\mathcal{F}_{3}$. Therefore, the same argument as before shows that
at least $\mathrm{O(N)}$-triangles are needed to cap off $c_{N}$.

The proof of Proposition 3.6 when $A$ has corank 2 is similar to the $n=3$
case outlined here.

##  5\. Concluding remarks

The free factor complex $\mathcal{F}_{n}$ is quasi-isometric to another
complex called the _complex of free factor systems_ , denoted
$\mathcal{F}\mathcal{F}_{n}$. The complex $\mathcal{F}\mathcal{F}_{n}$ is
closely related to the simplicial closure of unreduced Outer space (see
[BG20]). A free factor system of $\mathbb{F}$ is a finite collection of the
form $\mathcal{A}=\\{[A_{1}],...,[A_{k}]\\},$ where $k>0$, each $A_{i}$ is a
proper, non-trivial free factor of $\mathbb{F}$, such that there exists a free
factorization $\mathbb{F}=A_{1}\ast\cdots A_{k}\ast F_{M}$. There is a partial
ordering on the set of free factor systems given as follows:
$\mathcal{A}\sqsubseteq\mathcal{A}^{\prime}$ if for every
$[A_{i}]\in\mathcal{A}$ there exists $[A^{\prime}_{j}]\in\mathcal{A^{\prime}}$
such that $A_{i}\subseteq A_{j}^{\prime}$ up to conjugation. The vertices of
$\mathcal{F}\mathcal{F}_{n}$ are free factor systems and two vertices
$\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ are joined by an edge if
$\mathcal{A}_{1}\sqsubseteq\mathcal{A}_{2}$ or vice versa.

Now recall the length 4 loop $c_{N}$ in $\mathcal{F}_{n}$. It can also be
viewed as a loop in $\mathcal{F}\mathcal{F}_{n}$. However, in this complex,
the vertex $\\{[\langle a\rangle],[\langle b\rangle]\\}$ is connected to both
$A_{0}$ and $A_{N}$ and hence the loops $c_{N}$ can be capped off with 4
triangles. It is curious to know if $\mathcal{F}\mathcal{F}_{n}$ satisfies
some kind of combinatorial isoperimetric bound.

## References

  * [BF14a] Mladen Bestvina and Mark Feighn.  Hyperbolicity of the complex of free factors.  Adv. Math., 256:104–155, 2014.
  * [BF14b] Mladen Bestvina and Mark Feighn.  Subfactor projections.  J. Topol., 7(3):771–804, 2014.
  * [BG20] Benjamin Brück and Radhika Gupta.  Homotopy type of the complex of free factors of a free group.  Proc. Lond. Math. Soc. (3), 121(6):1737–1765, 2020.
  * [CP12] Matt Clay and Alexandra Pettet.  Relative twisting in outer space.  J. Topol. Anal., 4(2):173–201, 2012.
  * [CV86] Marc Culler and Karen Vogtmann.  Moduli of graphs and automorphisms of free groups.  Invent. Math., 84(1):91–119, 1986.
  * [GL07] Vincent Guirardel and Gilbert Levitt.  The outer space of a free product.  Proc. Lond. Math. Soc. (3), 94(3):695–714, 2007.
  * [HM14] Michael Handel and Lee Mosher.  Relative free splitting and free factor complexes I: Hyperbolicity.  arXiv e-prints, page arXiv:1407.3508, July 2014.
  * [Web20] Richard C. H. Webb.  Contractible, hyperbolic but non-${\rm CAT}(0)$ complexes.  Geom. Funct. Anal., 30(5):1439–1463, 2020.