# PI-ARS: Accelerating Evolution-Learned Visual-Locomotion with
Predictive Information Representations

Kuang-Huei Lee∗1 Ofir Nachum∗1 Tingnan Zhang1 Sergio Guadarrama1 Jie Tan1
Wenhao Yu1 *Equal contribution1All authors are with Google Research,
1600 Amphitheatre Parkway Mountain View, CA 94043, United States {leekh,
ofirnachum, tingnan, sguada, jietan<EMAIL_ADDRESS>
###### Abstract

Evolution Strategy (ES) algorithms have shown promising results in training
complex robotic control policies due to their massive parallelism capability,
simple implementation, effective parameter-space exploration, and fast
training time. However, a key limitation of ES is its scalability to large
capacity models, including modern neural network architectures. In this work,
we develop Predictive Information Augmented Random Search (PI-ARS) to mitigate
this limitation by leveraging recent advancements in representation learning
to reduce the parameter search space for ES. Namely, PI-ARS combines a
gradient-based representation learning technique, Predictive Information (PI),
with a gradient-free ES algorithm, Augmented Random Search (ARS), to train
policies that can process complex robot sensory inputs and handle highly
nonlinear robot dynamics. We evaluate PI-ARS on a set of challenging visual-
locomotion tasks where a quadruped robot needs to walk on uneven stepping
stones, quincuncial piles, and moving platforms, as well as to complete an
indoor navigation task. Across all tasks, PI-ARS demonstrates significantly
better learning efficiency and performance compared to the ARS baseline. We
further validate our algorithm by demonstrating that the learned policies can
successfully transfer to a real quadruped robot, for example, achieving a 100%
success rate on the real-world stepping stone environment, dramatically
improving prior results achieving 40% success.††The supplementary video is
available at kuanghuei.github.io/piars

Figure 1: In PI-ARS, an observation encoder $\phi$ is used to provide a
compressed observation representation. This way, ARS learning is focused on a
much smaller neural network than if the whole policy (mapping robot
observations to actions) were learned end-to-end. As ARS uses sampled
trajectories from the policy to update its parameters, PI-ARS uses the same
trajectories to maintain a replay buffer for training $\phi$ via predictive
information (PI), which includes auxiliary-learned networks as described in
Section III-B.

##  I Introduction

Evolution Strategy (ES) optimization techniques have received increasing
interest in recent years within the robotics and deep reinforcement learning
(DRL) communities [1, 2, 3, 4, 5, 6, 7]. ES algorithms have been shown to be
competitive alternatives to commonly used gradient-based DRL algorithms such
as PPO [8] and SAC [9], while also enjoying the benefits of massive
parallelism, simple implementation, effective parameter-space exploration, and
faster training time [1].

Despite the promising progress of ES algorithms, they nevertheless exhibit key
limitations when compared to gradient-based DRL algorithms. Namely, unlike
gradient-based methods, ES methods scale poorly to high-dimensional search
spaces, commonly encountered when using high-capacity modern neural network
architectures [10, 1]. An important and exemplary task is visual-locomotion
[3], in which a legged robot relies on its vision input to decide where to
precisely place its feet to navigate uneven terrains. Due to the rich and
diverse sensor observations as well as complex robot dynamics, learning such a
task requires the use of deep convolutional neural networks (CNNs) with a
large number of learnable parameters, thus exacerbating the sample-complexity
of ES methods.

In this paper, we develop Predictive Information Augmented Random Search (PI-
ARS) to relieve this key bottleneck of ES algorithms. Our key insight is to
leverage the power of gradient-based and gradient-free learning together by
modularizing the learning agent into two components: (1) an encoder network
mapping high-dimensional and diverse observation inputs to a concise fixed-
length vector _representation_ , and (2) a smaller policy network that maps
the compressed representations to actions. For (1), we leverage the power of
gradient-based learning, and use a self-supervised objective based on
maximizing the _predictive information_ (PI) of the output representation,
inspired by previous work in representation learning [11, 12, 13, 14, 15, 16].
Meanwhile for (2), we leverage the simplicity and parallelizability of the ES
optimization method Augmented Random Search (ARS) [2]. By decoupling
representation learning from policy optimization in this way, we avoid
scalability issues while fully leveraging the advantages of ES methods.

We evaluate our proposed PI-ARS algorithm on a variety of visual-locomotion
tasks, both in simulation and on a quadruped robot. Among these tasks, the
robot is evaluated on its ability to walk on uneven stepping stones,
quincuncial piles, and moving platforms, as well as to complete an indoor
navigation task (Figure 2). Through extensive experimentation in simulation,
we find that PI-ARS significantly outperforms the baselines (ARS [3], SAC [9],
PI-SAC [13]), both in training speed and final performance. We further
validate the results by deploying the learned policies on a real quadruped
robot. Using the same physical setup as prior work [3], PI-ARS learns more
robust policies that can consistently finish the entire course of stepping
stones, achieving 100% success over 10 real-robot trials, compared to 40%
success rate of prior work. We observe similarly successful robustness to
real-world transfer for the indoor navigation policy.

In summary, the contributions of this paper are the following:

  1. 1.

We propose a new PI-ARS algorithm that combines the advantages of gradient-
based self-supervised representation learning and gradient-free policy
learning, thus solving a key bottleneck of ES algorithms.

  2. 2.

We apply PI-ARS in visual-locomotion tasks, which significantly improve the
state-of-the-art [3] both in simulation and in the real world.

##  II Related Work

###  II-A Evolution Strategy for RL

There have been numerous works that demonstrate the effectiveness of applying
Evolution Strategy (ES) algorithms to continuous control problems [17, 1, 2].
For example, Tan et al. applied Neural Evolution of Augmenting Topologies
(NEAT) to optimize a character to perform bicycle stunts [17]. Within the
field of deep reinforcement learning, Salimans et al. first demonstrated that
ES algorithm can be applied to train successful neural-network policies for
the OpenAI Gym control tasks [1]. Mania et al. introduced Augmented Random
Search (ARS), a simple yet effective ES algorithm that further improves the
learning efficiency for robotic control tasks [2].

Compared to gradient-based RL algorithms, ES algorithms can handle non-
differentiable dynamics and objective functions, explore effectively with
sparse or delayed rewards, and are naturally parallelizable. As such,
researchers have applied ES algorithms in a variety of applications such as
legged locomotion [3, 18], power grid control [7], and mixed autonomy traffic
[19]. However, as ES algorithms do not leverage backpropagation, they suffer
from low sample efficiency and may not scale well to complex high-dimensional
problems [1]. As a result, applying ES to learn vision-based robotic control
policies is rarely explored [3].

###  II-B Predictive Representations for RL

Our work relies on learning representations that are predictive of future
events. Prior work has shown benefit from having good models of the past and
future states [20, 21, 22]. More recently, using these principles to guide
state representation learning methods has been demonstrated to yield favorable
performance both in practice [13, 15] and in theory [23, 24]. A natural
approach to learning such representations is using generative models to
explicitly predict observations [12, 25], which could be challenging and
expensive for high-dimensional tasks. Alternatively, using variational forms
[26] of the predictive information [27], commonly leading to contrastive
objectives, makes learning such representations more tractable [13, 15, 11].
In this work, we take the contrastive approach to learn predictive
representations of the observed states, upon which we learn an optimal policy
with augmented random search (ARS) [2], an ES method. To the best of our
knowledge, the proposed learning system is the first to take such a combined
approach, and the first to apply predictive information representations on
visual locomotion tasks with legged robots.

###  II-C Visual-Locomotion for Legged Robots

Visual-locomotion is an important research direction that has received much
attention in the robotics research community [28, 29, 30, 31, 32, 33, 34, 35,
36]. Directly training a visual-locomotion controller is challenging due to
the high dimensional visual input and the highly nonlinear dynamics of legged
robots [3, 37]. Many existing methods manually and explicitly decouple the
problem into more manageable components including perception [31, 36], motion
planning [32, 38], and whole body control [39, 40, 41]. In this work, we
consider direct learning of visual-locomotion controllers for quadruped robots
as the test-bed for our proposed learning algorithm and demonstrate that by
combining gradient-free ES and gradient-based representation learning
techniques, we can enable more effective and efficient learning of visual-
locomotion controllers.

##  III Method

In this section we describe our method, PI-ARS, which combines representation
learning based on predictive information (PI), and Augmented Random Search
(ARS) [2]. See Figure 1 for a diagram of the algorithm and Algorithm 1 for a
pseudocode.

###  III-A Problem Formulation and Notations

PI-ARS solves a sequential decision-making environment in which at each
timestep $t$ the agent is presented with an _observation_ $\mathbf{s}_{t}$. In
visual-locomotion, this observation typically includes a visual input
$\mathbf{s}^{v}_{t}$ (e.g., depth camera images) as well as proprioceptive
states $\mathbf{s}^{p}_{t}$. The agent’s _policy_ determines its behavior, by
providing a mapping from observations $\mathbf{s}_{t}$ to _actions_
$\mathbf{a}_{t}$. After application of action $\mathbf{a}_{t}$, the agent
receives a reward $r_{t}$ and a new observation $\mathbf{s}_{t+1}$. This
process is repeated until the agent is terminated, either due to a timeout or
encountering a terminal condition (e.g., the robot falls). The agent’s
_return_ is computed as the sum of rewards over an entire episode, and the
agent’s goal is to maximize the expected value of the return.

###  III-B Predictive Information

A good observation encoder for policy learning must provide representations
that are both _compressive_ – so that ARS learning is focused on much fewer
parameters than learning from raw observations would entail – and _task-
relevant_ – so that ARS has access to all features necessary for learning
optimal behavior. To this end, we propose to learn an encoder $\phi$ to
maximize predictive information (PI). In general, PI refers to the mutual
information between past and future $I(\mathrm{past};\mathrm{future})$ [27].
In our setting involving environment-produced sub-trajectories
$\tau=(\mathbf{s}_{t},\mathbf{a}_{t},r_{t},\mathbf{a}_{t+1},r_{t+1},\dots,\mathbf{a}_{t+k-1},r_{t+k-1},\mathbf{s}_{t+k})$,
$\mathrm{past}$ corresponds to
$(\mathbf{s}_{t},\mathbf{a}_{t},\dots,\mathbf{a}_{t+k-1})$ and
$\mathrm{future}$ refers to the both the per-step rewards
$(r_{t},\dots,r_{t+k-1})$ and the ultimate visual observation
$\mathbf{s}_{t+k}^{v}$111This empirical choice of $\mathrm{future}$ works well
in our setting.; i.e.,
$\mathbf{s}_{t+j}=(\mathbf{s}^{v}_{t+j},\mathbf{s}^{p}_{t+j})$.

We use $\phi$ to map both $\mathbf{s}_{t}$ and $\mathbf{s}_{t+k}^{v}$ to a
lower dimensional representation. Namely, as shown in Figure 1, the
observation encoder $\phi$ contains a vision encoder $\phi_{v}$ that maps
visual observations $\mathbf{s}^{v}_{t}$ to a 128-d representation. This
representation is subsequently concatenated with proprioceptive states, and
the concatenation is projected to be the output of $\phi$, which is also
128-d. We thus use the entire encoder $\phi$ to encode $\mathbf{s}_{t}$, while
use only the vision encoder $\phi_{v}$ to encode the future
$\mathbf{s}_{t+k}^{v}$. By learning $\phi$ to maximize the mutual information
between these $\mathrm{past}$ and $\mathrm{future}$, we ensure that $\phi$
encodes the necessary information in $\mathbf{s}_{t}$ to predict the future.
Notably, previous work has shown that representations that are predictive of
the future are also provably beneficial for solving the task [23].

To learn $\phi$, we use a combination of two objectives, the first
corresponding to reward prediction and the second to $\mathbf{s}_{t+k}^{v}$
prediction.222We note that in our early experiments, we found learning $\phi$
using reward prediction alone leads to insufficient representations for
solving the tasks. For the former, we simply predict rewards
$\hat{r}_{t},\dots,\hat{r}_{t+k-1}$ using an RNN over inputs
$(\phi(\mathbf{s}_{t}),\mathbf{a}_{t},\dots,\mathbf{a}_{t+k-1})$. At time
$t+j$, the RNN cell takes a latent state and an action and outputs a reward
prediction $\hat{r}_{t+j}$ and the next latent state. The reward loss is
defined as

$\displaystyle\small
L_{r}=\mathbb{E}_{\tau}\bigg{[}{\sum_{j=0}^{k-1}(\hat{r}_{t+j}-r_{t+j})^{2}}\bigg{]}.$
(1)

This corresponds to maximizing $I(\mathrm{past};\mathrm{future\ rewards})$
with a generative model [42].

For the prediction of $\mathbf{s}_{t+k}^{v}$, rather than a generative model,
as used for $\hat{r}_{t+j}$, which would present challenges for high-
dimensional image observations, we leverage InfoNCE, a contrastive variational
bound on mutual information [11, 26, 13]. We use an auxiliary learned, scalar-
valued function $f$ to estimate the mutual information using access to samples
of sub-trajectories
$\tau=(\mathbf{s}_{t},\mathbf{a}_{t},\dots,\mathbf{a}_{t+k-1},\mathbf{s}_{t+k})$.
Specifically, we conveniently exclude the course of actions and choose the
following form:

$I(\mathrm{past};\mathrm{future\
obs})\geq\tilde{I}(\mathrm{past};\mathrm{future\ obs})=\\\
~{}\mathbb{E}_{\tau}\bigg{[}f(\phi(\mathbf{s}_{t}),\phi_{v}(\mathbf{s}^{v}_{t+k}))\\\
-\log\mathbb{E}_{\tilde{\mathbf{s}}_{t+k}}[\exp\\{f(\phi(\mathbf{s}_{t}),\phi_{v}(\tilde{\mathbf{s}}^{v}_{t+k}))\\}]\bigg{]},$
(2)

where $\tilde{\mathbf{s}}^{v}_{t+k}$ is from an observation randomly sampled
independent of $\tau$. Our objective is then to maximize this variational form
with respect to both $\phi$ and $f$.

To parameterize $f$, we use an MLP to map $\phi(\mathbf{s}_{t})$ to
$\mathbf{z}^{\mathrm{past}}_{t}$, a 128-d vector. Meanwhile, we map
$\phi_{v}(\mathbf{s}^{v}_{t+k})$ to $\mathbf{z}^{\mathrm{future}}_{t+k}$, a
128-d vector representation of the future, using another MLP. The function $f$
is then computed as a scalar dot-product of the two vectors.

We train both the reward objective and the variational objective using batch
samples from a replay buffer of sub-trajectories collected by ARS. To
approximate $\mathbb{E}_{\tilde{\mathbf{s}}_{t+k}}$ in Equation (2), we use
samples of $\tilde{\mathbf{s}}^{v}_{t+k}$ within the same batch of sub-
trajectories. The full objective is optimized using the Adam stochastic
gradient descent optimizer [43] and the gradient is calculated using back-
propagation. Full implementation details are included in the Appendix.

Algorithm 1 Pseudocode for PI-ARS.

Initialize encoder $\phi$, auxiliary networks (RNN, $f$), and optimizer
$\mathrm{Opt}_{\phi,\mathrm{aux}}$.

Initialize ARS parameters $\theta$ and optimizer $\mathrm{Opt}_{\theta}$.

Initialize replay buffer $\mathcal{B}$.

for $T=1,\dots$ do

#### ARS ####

Sample $\\{\sigma_{i}\\}_{i=1}^{N}$ from normal with scale $\delta$.

Collect environment trajectories for policies $(\phi,\theta\pm\sigma_{i})$.

Compute returns $R_{i,\pm}$ for each policy.

Compute gradient of $M$ best-performing directions:

$~{}~{}~{}~{}\hat{g}=\frac{\delta}{M}\sum_{i=1}^{M}(R_{i,+}-R_{i,-})\sigma_{i}$.

Update $\theta$ w.r.t. gradient $\hat{g}$ and $\mathrm{Opt}_{\theta}$.

Add trajectories to $\mathcal{B}$.

#### PI ####

Sample batch of sub-trajectories $\\{\tau_{i}\\}_{i=1}^{B}$ from
$\mathcal{B}$.

for $i=1,\dots,B$ do

$\hat{L}_{i}=-\tilde{I}(\tau_{i})+L_{r}(\tau_{i})$ Equations (1), (2)

end for

Compute total loss $\hat{L}=\sum_{i=1}^{B}\hat{L}_{i}$.

Update $\phi$ and aux. networks w.r.t. loss $\hat{L}$ and
$\mathrm{Opt}_{\phi,\mathrm{aux}}$.

end for

Figure 2: The environments that we used to benchmark the PI-ARS learning
system: (a) uneven stepping stones, (b) quincuncial piles, (c) moving
platforms (the afterimage is for indicating that these platforms are moving),
and (d) indoor navigation. Figure 3: Simulation results. We compare the
performance of PI-ARS to ARS during training on four challenging simulation
environments. PI-ARS consistently and significantly outperforms ARS.

###  III-C PI-ARS

The encoder $\phi$ learned by PI maps a high-dimensional observation to a
concise 128-d representation, upon which we use ARS to train a more compact
policy network as follows. At each iteration of ARS, the algorithm samples $N$
perturbations $[\sigma_{1},\dots,\sigma_{N}]$ of the policy weights $\theta$
using a standard normal distribution with scale $\sigma$. The algorithm
evaluates the policy returns at $\theta+\sigma_{i}$ and $\theta-\sigma_{i}$.
ARS then computes an estimation of the policy gradient by aggregating the
returns from the best-performing perturbation directions:

$\hat{g}=\frac{\delta}{M}\sum_{i=1}^{M}(R_{i,+}-R_{i,-})\sigma_{i},$ (3)

where $\delta$ is the update coefficient, $M$ is the number of top-performing
perturbations to be considered, and $R_{i,+},R_{i,-}$ denote the total return
of the policy at perturbations $\theta\pm\sigma_{i}$. We refer the readers to
[2] for additional details.

We iterate between updating the representation network $\phi$ with the PI
objective and updating the policy with ARS. To maximize data re-use, we store
the sampled trajectories from perturbed policies evaluated by ARS in a replay
buffer used for the PI learning pipeline.

##  IV Experiments

We aim to answer the following questions in our experiments:

  * •

Is our proposed algorithm, PI-ARS, able to learn vision-based policies that
solve challenging visual-locomotion tasks?

  * •

Does PI-ARS achieve better performance than alternative methods that do not
apply representation learning?

  * •

Are our learned policies applicable to real robots?

###  IV-A Visual-Locomotion Tasks

To answer the above questions, we design a variety of challenging visual
locomotion tasks. Figure 2 shows the suite of environments that we evaluate
on. More details of each environment can be found in Section -B.

##### Uneven stepping stones

In this task, the robot is tasked to walk over a series of randomly placed
stepping stones separated by gaps, and elevation of the stepping stones
changes dramatically (Figure 2 (a)).

##### Quincuncial piles

This is an extension to uneven stepping stones, where we reduce the contact
surface area and arrange stones in both forward and lateral directions (Figure
2(b)).

##### Moving platforms

We construct a set of stepping stones and allow each piece to periodically
move either horizontally and vertically at a random speed (Figure 2(c)).

##### Indoor navigation with obstacles

In this task, we evaluate the performance of PI-ARS controlling the robot to
navigate in a cluttered indoor environment (Figure 2 (d). Specifically, we
randomly place boxes on the floor of a scanned indoor environment and command
the robot to walk to a target position.

###  IV-B Experiment Setup

We use the Unitree Laikago quadruped robot [44], which weighs $24$kg and has
$12$ actuated joints, with two depth cameras installed: one Intel D435 in the
front for a wider field of view and one Intel L515 on the belly for better
close-range depth quality. We create a corresponding simulated Laikago robot
in the PyBullet physics simulator [45] with physical properties from hardware
spec and simulated cameras that matches the camera intrinsics and extrinsics
from the real cameras. The observation, action, and reward designs are
detailed as follows.

####  IV-B1 Observation Space

We design the observation space in our visual-locomotion tasks following prior
work by Yu et al. [3]. In particular, our observation space consists of two
parts: $\mathbf{s}=(\mathbf{s}^{v},\mathbf{s}^{p}$), where $\mathbf{s}^{v}$
are the two $32\times 24$ images from depth sensors, and $\mathbf{s}^{p}$
include all the proprioceptive states (and controller states). In our
experiments,
$\mathbf{s}^{p}=(\mathbf{q}_{s},\dot{\mathbf{p}},\dot{\Phi},\dot{\Theta},\mathbf{r}_{1\ldots
4},c_{1\ldots 4},\phi_{1\ldots 4},\mathbf{a}_{prev})$ includes the CoM height,
roll, and pitch $\mathbf{q}_{s}=(p_{z},\Phi,\Theta)$, the estimated CoM
velocity $\dot{\mathbf{p}}$, the gyroscope readings $\dot{\Phi},\dot{\Theta}$,
the robot’s feet positions $\mathbf{r}_{1\ldots 4}$ in the base frame, the
feet contact states $c_{1\ldots 4}$, the phase of each leg in its respective
gait cycle $\phi$, and the previous action.

For the indoor navigation task, we additionally include the relative goal
vector $\mathbf{n}=\mathbf{\bar{o}}-\mathbf{p}$ as part of the observation,
where $\mathbf{\bar{o}}$ is the target location and $\mathbf{p}$ is the
robot’s position.

####  IV-B2 Action Space

We follow the prior work [3] to use a hierarchical design for the visual-
locomotion controller with a trainable high-level vision policy $\pi_{\theta}$
that maps visual and proprioceptive input to a high-level motion command, and
an MPC-based low-level motion controller that executes the high-level motion
command with trajectory optimization. The high-level motion command, i.e. the
action space for the RL problem, is defined as:
$(\mathbf{q}_{s}^{d},\mathbf{\dot{q}}^{d},\mathbf{r}^{d}_{1\ldots
4},\mathbf{h}_{1\ldots 4})$, where $\mathbf{q}_{s}^{d}$ and
$\mathbf{\dot{q}}^{d}$ are the desired CoM pose, velocity,
$\mathbf{r}^{d}_{i}$ is $i$th foot’s target landing position
$(r_{xi},r_{yi},r_{zi})$, and $\mathbf{h}_{i}$ is the peak height of $i$th
foot’s swing trajectory.

####  IV-B3 Reward Function

For training a policy to walk on different terrains, we use the following
reward function:

$R(\mathbf{s},\mathbf{a})=clip(\dot{p}_{x},-\dot{p}_{x}^{max},\dot{p}_{x}^{max})-w|\Psi|,$
(4)

where $\dot{p}_{x}$ is the CoM velocity in the forward direction, and $\Psi$
the base yaw angle. The first term rewards the robot to move forward with a
maximum speed controlled by $\dot{p}_{x}^{max}$, the second term encourages
the robot to walk straightly.

For the indoor navigation task, we use the delta geodesic (path) distance to
the goal as our reward:

$R(\mathbf{s},\mathbf{a},\mathbf{\bar{o}})=d_{g}^{t}-d_{g}^{t-1},$ (5)

where $d_{g}^{t}$ is the geodesic distance between the robot and the target
location at time $t$.

####  IV-B4 Early termination.

A training episode is terminated if: 1) the robot loses balance (CoM height
$p_{z}$ below 0.15 m, pitch $|\Theta|>1$ rad, or roll $|\Phi|>0.3$ rad in our
experiments), or 2) the robot reaches an invalid joint configuration, e.g.
knee bending backwards.

###  IV-C Learning in Simulation

In this subsection, we discuss the results of PI-ARS learned on simulated
visual-locomotion tasks and compare to a state-of-the-art ARS approach to
robotic visual-locomotion [2, 3] (Figure 3). Among other baseline approaches
that we have tried include SAC [9] and PI-SAC [13] but both algorithms failed
to make any non-negligible learning progress for the tasks we consider despite
extensive hyperparameter tuning, and so we omit these algorithms from the
results. For fair comparison, all algorithms utilize the same MPC-based
locomotion controller and learn policies in the high-level command space
described in Section IV-B2. All policies utilize the same network
architecture; i.e., the policy learned by the baseline ARS method is composed
of the same set of convolution and feed-forward layers used for $\phi$ in PI-
ARS.

We train PI-ARS and ARS policies using a distributed implementation. For all
PI-ARS and ARS experiments, we perform $N=1024$ perturbations per ARS
iteration and use the top 50% performers ($M=512$) to update the policy
network head. This choice, determined through a grid search, empirically works
the best for both PI-ARS and ARS in our implementation. Further increase of
$N$ (and thus computation cost) does not significantly improve the
performance. The algorithm is run until convergence with a maximum of $4000$
training iterations, resulting in a maximum of $2,048,000$ simulation episodes
per trial. We perform $30$ trials of training PI-ARS/ARS with uniformly
sampled $\sigma$ and $\delta$ values ($\sigma\sim[0.005,0.05]$,
$\delta\sim[0.005,0.05]$) and report the mean and standard error of returns
against number of training episodes for each task.

As we demonstrate in the supplementary video, PI-ARS is able to learn vision-
based policies that successfully solve these challenging visual-locomotion
tasks. Figure 3 shows that on all tasks, PI-ARS gives significantly better
returns and sample-efficiency than the ARS baseline. For example, on uneven
stepping stones, the mean return after 2,000,000 episodes of training improves
by 48.01%, from 2.93 to 4.34. This empirically demonstrates the effectiveness
of learning ARS policies upon compressed, gradient-learned representations
instead of end-to-end. On the other hand, observing that SAC fails to learn,
we hypothesize that the advantages of ARS such as parameter-space exploration
and stability are critical to these complex visual-locomotion tasks.
Furthermore, adding predictive information to SAC, i.e. PI-SAC, does not
improve learning, suggesting that even with an effective representation
learner, without a powerful policy solver, a learning algorithm is not able to
sufficiently tackle these visual-locomotion tasks.

Figure 4: PI-ARS policy solving a challenging real-world visual-locomotion
task involving a series of four step stones separated by gaps. PI-ARS
successfully completes this terrain, avoiding all gaps, 100% of the time
measured over 10 trials. Figure 5: PI-ARS policy learns to navigate in a
cluttered real-world indoor environment.

###  IV-D Validation on Real Robot

We deploy the visual-locomotion policy trained in simulation on a Laikago
robot to perform two visual-locomotion tasks: 1) walking over real-world
stepping stones (Figure 4), and 2) navigating in an indoor environment with
obstacles (Figure 5).

To overcome the sim-to-real gap, we adopt the same procedure as done by Yu et
al. [3]. For the visual gap, during training, we first apply random noise to
the simulated depth images to mimic the real-world depth noises. Then we apply
a Navier-Stokes-based in-painting operation [46] with radius of 1 to fill the
missing pixels, followed by down-sampling to $32x24$ (with OpenCV’s
$\mathrm{INTER\\_AREA}$ interpolation method for resizing [47]). On the real
hardware, we obtain $640x480$ raw depth images from both L-515 and D435
cameras and perform the same in-painting and down-sampling. To mitigate the
dynamics gap, we apply dynamics randomization during training.

Videos of our real-world experiments can be found in the supplementary
material.

##### Stepping Stones

For the stepping stones task, we created a physical setup consisting of four
stones separated by three gaps between $[0.12,0.18]$m (Figure 4). The PI-ARS
policy is learned in simulation with an easier version of uneven stepping
stones where stone heights change less significantly. Our PI-ARS policy was
able to achieve $100\%$ success rate on the stepping stone environment with
$10$ trials. In contrast, the ARS baseline [3] with the same training and
evaluation setting achieved $40\%$ success rate for reaching the last stone
with all four legs and often failed at the last gap.

##### Indoor Navigation

For evaluating the navigation task in the real world, we design a route in an
indoor environment with obstacles (Figure 5). The robot needs to navigate to
the target location while avoiding the obstacles. To enable the robot to
better avoid the obstacles, we rotate the front camera of the robot such that
it can see $\sim$3 meters ahead of the robot. We also track the robot base
position using a motion capture system, which is needed to compute the
relative goal vector $\mathbf{n}$. As shown in the supplementary video, our
PI-ARS policy is able to successfully navigate to the designated target
location. For the setting shown in Figure 5, our policy successfully
discovered a ‘shortcut’ in between two obstacles and was able to go through.
We do note there is collision with the obstacle’s arm. This is because the
robot was trained with simulated obstacles with box shapes only; further
training with more diverse obstacles would likely mitigate this problem.

Overall, these experiments validate that PI-ARS is capable of learning
policies that can transfer to real robots.

##  V Conclusion

We present a new learning method, PI-ARS, and apply it to the visual-
locomotion problem. PI-ARS combines gradient-based representation learning
with gradient-free policy optimization to leverage the advantages of both. PI-
ARS enjoys the simplicity and scalability of gradient-free methods, and it
relieves a key bottleneck of ES algorithms on high-dimensional problems by
simultaneously learning a low-dimensional representation that reduces the
search space. We evaluate our method on a set of challenging visual-locomotion
tasks, including navigating through uneven stepping stones, quincuncial piles,
moving platforms, and cluttered indoor environments, among which PI-ARS
significantly outperforms the state-of-the-art. Furthermore, we validate the
policy learned by PI-ARS on a real quadruped robot. It enables the robot to
walk over randomly-placed stepping stones and navigating in an indoor space
with obstacles. In the future, we plan to test PI-ARS in outdoor visual-
locomotion tasks, which presents more diverse and interesting terrains for the
robot to overcome.

## Acknowledgments

We thank Noah Brown, Gus Kouretas, and Thinh Nguyen for helping set up the
real-world stepping stones and address robot hardware issues.

## References

  * [1] T. Salimans, J. Ho, X. Chen, S. Sidor, and I. Sutskever, “Evolution strategies as a scalable alternative to reinforcement learning,” _arXiv preprint arXiv:1703.03864_ , 2017.
  * [2] H. Mania, A. Guy, and B. Recht, “Simple random search provides a competitive approach to reinforcement learning,” _arXiv preprint arXiv:1803.07055_ , 2018\.
  * [3] W. Yu, D. Jain, A. Escontrela, A. Iscen, P. Xu, E. Coumans, S. Ha, J. Tan, and T. Zhang, “Visual-locomotion: Learning to walk on complex terrains with vision,” in _5th Annual Conference on Robot Learning_ , 2021.
  * [4] X. Song, Y. Yang, K. Choromanski, K. Caluwaerts, W. Gao, C. Finn, and J. Tan, “Rapidly adaptable legged robots via evolutionary meta-learning,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 3769–3776.
  * [5] W. Yu, J. Tan, Y. Bai, E. Coumans, and S. Ha, “Learning fast adaptation with meta strategy optimization,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 2950–2957, 2020.
  * [6] A. Cully, J. Clune, D. Tarapore, and J.-B. Mouret, “Robots that can adapt like animals,” _Nature_ , vol. 521, no. 7553, pp. 503–507, 2015.
  * [7] R. Huang, Y. Chen, T. Yin, X. Li, A. Li, J. Tan, W. Yu, Y. Liu, and Q. Huang, “Accelerated deep reinforcement learning based load shedding for emergency voltage control,” _arXiv preprint arXiv:2006.12667_ , 2020.
  * [8] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [9] T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha, J. Tan, V. Kumar, H. Zhu, A. Gupta, P. Abbeel, _et al._ , “Soft actor-critic algorithms and applications,” _arXiv preprint arXiv:1812.05905_ , 2018.
  * [10] Y. Nesterov and V. Spokoiny, “Random gradient-free minimization of convex functions,” _Foundations of Computational Mathematics_ , vol. 17, no. 2, pp. 527–566, 2017.
  * [11] A. v. d. Oord, Y. Li, and O. Vinyals, “Representation learning with contrastive predictive coding,” _arXiv preprint arXiv:1807.03748_ , 2018\.
  * [12] D. Ha and J. Schmidhuber, “World models,” _arXiv preprint arXiv:1803.10122_ , 2018.
  * [13] K.-H. Lee, I. Fischer, A. Liu, Y. Guo, H. Lee, J. Canny, and S. Guadarrama, “Predictive information accelerates learning in rl,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 11 890–11 901, 2020.
  * [14] A. Srinivas, M. Laskin, and P. Abbeel, “CURL: Contrastive unsupervised representations for reinforcement learning,” _arXiv preprint arXiv:2004.04136_ , 2020.
  * [15] M. Yang and O. Nachum, “Representation matters: Offline pretraining for sequential decision making,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 11 784–11 794.
  * [16] X. Chen, S. Toyer, C. Wild, S. Emmons, I. Fischer, K.-H. Lee, N. Alex, S. H. Wang, P. Luo, S. Russell, _et al._ , “An empirical investigation of representation learning for imitation,” in _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2)_ , 2021.
  * [17] J. Tan, Y. Gu, C. K. Liu, and G. Turk, “Learning bicycle stunts,” _ACM Trans. Graph._ , vol. 33, no. 4, pp. 50:1–50:12, 2014. [Online]. Available: http://doi.acm.org/10.1145/2601097.2601121
  * [18] D. Jain, A. Iscen, and K. Caluwaerts, “Hierarchical reinforcement learning for quadruped locomotion,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2019, pp. 7551–7557.
  * [19] E. Vinitsky, A. Kreidieh, L. Le Flem, N. Kheterpal, K. Jang, C. Wu, F. Wu, R. Liaw, E. Liang, and A. M. Bayen, “Benchmarks for reinforcement learning in mixed-autonomy traffic,” in _Conference on robot learning_. PMLR, 2018, pp. 399–409.
  * [20] J. Schmidhuber, “Making the world differentiable: On using self-supervised fully recurrent neural networks for dynamic reinforcement learning and planning in non-stationary environments,” Institut für Informatik, Technische Universität München, Tech. Rep., 1990.
  * [21] ——, “Reinforcement learning in markovian and non-markovian environments,” in _Advances in Neural Information Processing Systems_ , 1991, pp. 500–506.
  * [22] ——, “On learning to think: Algorithmic information theory for novel combinations of reinforcement learning controllers and recurrent neural world models,” _arXiv preprint arXiv:1511.09249_ , 2015.
  * [23] O. Nachum and M. Yang, “Provable representation learning for imitation with contrastive fourier features,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [24] M. Yang, S. Levine, and O. Nachum, “Trail: Near-optimal imitation learning with suboptimal data,” _arXiv preprint arXiv:2110.14770_ , 2021.
  * [25] D. Hafner, T. Lillicrap, J. Ba, and M. Norouzi, “Dream to control: Learning behaviors by latent imagination,” _arXiv preprint arXiv:1912.01603_ , 2019\.
  * [26] B. Poole, S. Ozair, A. Van Den Oord, A. Alemi, and G. Tucker, “On variational bounds of mutual information,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 5171–5180.
  * [27] W. Bialek and N. Tishby, “Predictive information,” _arXiv preprint cond-mat/9902341_ , 1999.
  * [28] C. Mastalli, M. Focchi, I. Havoutis, A. Radulescu, S. Calinon, J. Buchli, D. G. Caldwell, and C. Semini, “Trajectory and foothold optimization using low-dimensional models for rough terrain locomotion,” in _2017 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2017, pp. 1096–1103.
  * [29] O. A. V. Magana, V. Barasuol, M. Camurri, L. Franceschi, M. Focchi, M. Pontil, D. G. Caldwell, and C. Semini, “Fast and continuous foothold adaptation for dynamic locomotion through CNNs,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 2140–2147, 2019.
  * [30] O. Villarreal, V. Barasuol, P. M. Wensing, D. G. Caldwell, and C. Semini, “MPC-based controller with terrain insight for dynamic legged locomotion,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 2436–2442.
  * [31] P. Fankhauser, M. Bjelonic, C. D. Bellicoso, T. Miki, and M. Hutter, “Robust rough-terrain locomotion with a quadrupedal robot,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 5761–5768.
  * [32] F. Jenelten, T. Miki, A. E. Vijayan, M. Bjelonic, and M. Hutter, “Perceptive locomotion in rough terrain–online foothold optimization,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 4, pp. 5370–5376, 2020.
  * [33] R. Grandia, A. J. Taylor, A. D. Ames, and M. Hutter, “Multi-layered safety for legged robots via control barrier functions and model predictive control,” _arXiv preprint arXiv:2011.00032_ , 2020.
  * [34] S. Gangapurwala, M. Geisert, R. Orsolino, M. Fallon, and I. Havoutis, “RLOC: Terrain-aware legged locomotion using reinforcement learning and optimal control,” _arXiv preprint arXiv:2012.03094_ , 2020.
  * [35] T. Miki, J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter, “Learning robust perceptive locomotion for quadrupedal robots in the wild,” _Science Robotics_ , vol. 7, no. 62, p. eabk2822, 2022.
  * [36] D. Kim, D. Carballo, J. Di Carlo, B. Katz, G. Bledt, B. Lim, and S. Kim, “Vision aided dynamic exploration of unstructured terrain with a small-scale quadruped robot,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 2464–2470.
  * [37] G. B. Margolis, T. Chen, K. Paigwar, X. Fu, D. Kim, S. Kim, and P. Agrawal, “Learning to jump from pixels,” _arXiv preprint arXiv:2110.15344_ , 2021\.
  * [38] H. W. Park, P. M. Wensing, and S. Kim, “Online planning for autonomous running jumps over obstacles in high-speed quadrupeds,” in _2015 Robotics: Science and Systems Conference, RSS 2015_. MIT Press Journals, 2015.
  * [39] J. Di Carlo, P. M. Wensing, B. Katz, G. Bledt, and S. Kim, “Dynamic locomotion in the mit cheetah 3 through convex model-predictive control,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 1–9.
  * [40] D. Kim, J. Di Carlo, B. Katz, G. Bledt, and S. Kim, “Highly dynamic quadruped locomotion via whole-body impulse control and model predictive control,” _arXiv preprint arXiv:1909.06586_ , 2019.
  * [41] G. Bledt, P. M. Wensing, and S. Kim, “Policy-regularized model predictive control to stabilize diverse quadrupedal gaits for the mit cheetah,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2017, pp. 4102–4109.
  * [42] I. Fischer, “The conditional entropy bottleneck,” _Entropy_ , vol. 22, no. 9, p. 999, 2020.
  * [43] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [44] “Unitree Robotics.” [Online]. Available: http://www.unitree.cc/
  * [45] E. Coumans and Y. Bai, “Pybullet, a python module for physics simulation in robotics, games and machine learning,” 2017.
  * [46] M. Bertalmio, A. L. Bertozzi, and G. Sapiro, “Navier-stokes, fluid dynamics, and image and video inpainting,” in _Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001_ , vol. 1. IEEE, 2001, pp. I–I.
  * [47] G. Bradski, “The OpenCV Library,” _Dr. Dobb’s Journal of Software Tools_ , 2000.

###  -A PI-ARS Implementation

We describe implementation details of PI-ARS as follows.

####  -A1 Network Architecture for $\phi$

In the visual-locomotion tasks we consider, an observation $\mathbf{s}_{t}$
contains a visual observation $\mathbf{s}^{v}_{t}$ and proprioceptive states
$\mathbf{s}^{p}_{t}$. The visual observation $\mathbf{s}^{v}_{t}$ contains one
depth image from the front camera and one from the rear (described in Section
IV-B). Accordingly, our vision encoder $\phi_{v}$ contains two identical CNNs
that independently map the front and rear images to two 64-d vectors and
concatenates them into a 128-d representation output $\mathbf{z}^{v}_{t}$.
Each CNN consists of 2 convolution layers with $3\times 3$ kernels, 8
channels, stride size 1, followed by a 64-d linear projection, where each
convolution and projection is followed by a relu activation.
$\mathbf{z}^{v}_{t}$ is then concatenated with proprioceptive states
$\mathbf{s}^{p}_{t}$ and linearly projected with tanh activation to yield a
128-d representation output $\mathbf{z}_{t}$. These together give us the
observation encoder $\phi$, in which
$\mathbf{z}_{t}=\phi(\mathbf{s}^{v}_{t},\mathbf{s}^{p}_{t})=\phi(\mathbf{s}_{t})$.

####  -A2 Network Architecture for Auxiliary Functions

The auxiliary-learned function $f$ maps $\mathbf{z}_{t}$ to a unit-length
128-d vector $\mathbf{z}^{\mathrm{past}}_{t}$, which corresponds to the
$\mathrm{past}$, via a 2-layer MLP (64 units, 128 units) followed by $l$-2
normalization.

For the future observation, $f$ only considers the visual observation
$\mathbf{s}^{v}_{t+k}$ and ignores $\mathbf{s}^{p}_{t+k}$:

$\displaystyle\mathbf{z}^{\mathrm{future}}_{t+k}=h(\mathrm{stopgrad}(\phi_{v}(\mathbf{s}^{v}_{t+k})))$
(6)

where $h$ is another 2-layer MLP (64 units, 128 units), and
$\mathrm{stopgrad}$ refers to the stop gradient operation. The output of $f$
is a dot-product of $\mathbf{z}^{past}_{t}$ and $\mathbf{z}^{future}_{t+k}$.

For predicting the future rewards, we recurrently apply an auxiliary RNN cell
$g$ to encode a latent state and an action (i.e. the $\mathrm{past}$) and
output a reward prediction and the next latent state at each time step:

$\displaystyle\hat{r}_{t},\mathbf{z}^{\prime}_{t+1}=g(\mathbf{z}_{t},\mathbf{a}_{t}),\hat{r}_{t+1},\mathbf{z}^{\prime}_{t+2}=g(\mathbf{z}^{\prime}_{t+1},\mathbf{a}_{t+1}),\dots,$
$\displaystyle\hat{r}_{t+k-1},\mathbf{z}^{\prime}_{t+k}=g(\mathbf{z}^{\prime}_{t+k-1},\mathbf{a}_{t+k-1}).$

$g$ is a 3-layer MLP (128 units each with tanh activations), and a 128-to-1
linear layer branch is attached to the second layer of $g$ to output reward
predictions $\hat{r}_{t},\dots,\hat{r}_{t+k-1}$, one at each step. The initial
latent state is $\mathbf{z}_{t}$.

####  -A3 Policy Network Head

The ARS-learned policy network head is a simple 3-layer MLP (64, 32, and
$\mathrm{dim}(\mathcal{A})$ units, where $\mathcal{A}$ is the action space)
with tanh activation that takes $\mathbf{z}_{t}$ and proprioceptive states
$\mathbf{s}^{p}_{t}$ as input, and outputs an action. The output of the policy
network is tanh-squashed to $[-1,1]$ and subsequently re-scaled to the
environment action bounds (Table I).

####  -A4 PI-ARS Training

In PI-ARS, we alternate between 1 step for ARS and 2 steps for PI. Each PI
step uses a batch of 512 $k$-step trajectories from the replay buffer and
performs gradient steps with a learning rate of $10^{-4}$. We set $k=5$ for
all tasks but indoor navigation. For indoor navigation, we use $k=30$ as the
task nature requires a longer planning horizon. We also apply observation
normalization, using running means and standard deviations.

####  -A5 ARS, SAC, PI-SAC Implementations

To ensure fair comparison for non-representation learning methods (ARS, SAC),
we use the an identical policy network as used for PI-ARS, which combines a
base encoder $\phi$ and a policy network head. Thus, all algorithms have
access to the same capacity policy network. The critic in SAC and PI-SAC share
the same base encoder $\phi$ with the policy (actor) network and we stop
gradients from the policy head to the base encoder following [13]. We also
apply the same observation normalization used for PI-ARS to these baseline
methods.

###  -B Visual-Locomotion Task details

Here we describe additional details regarding the visual-locomotion tasks we
used in our work. For the uneven stepping stone, quincuncial piles, and moving
platform tasks we follow the design in prior work [3].

##### Uneven stepping stones

In this task we evaluate the ability for the policy to traverse stepping
stones with varied heights. The widths, and lengths of stepping stones are
sampled from $[0.55,0.7]$, and $[0.5,0.8]$ meters. The height offsets of
neighboring stones are uniformly sampled in $[0.13,0.2]m$, and a gap of
$[0.05,0.1]m$ is added between the stones. To successfully traverse this
environment the agent needs to identify and avoid the gaps between stones and
land the swing leg to the appropriate height for the next stone.

##### Quincuncial piles

In this task, we create a two-dimensional stepping stones to evaluate the
robot’s behavior in avoiding gaps in both forward and lateral direction.
Specifically, each stone has an area of $0.15\times 0.15m^{2}$ with a standard
deviation of $0.015m$ in height, and is separated by $[0.13,0.17]$ m from each
other in both x and y directions. At the beginning of each episode, we also
randomly rotate entire stone grid in $[0.1,0.1]$ rad.

##### Moving platforms

Our proposed framework can also be applied to handle dynamic objects. In this
example, we construct an environment with random stepping stones and allow
each piece to move dynamically. Each platform follows a periodic movement
whose magnitude and frequency are randomly sampled in $[0.10,0.15]m$ and
$[0.4,1.0]Hz$, respectively. Also, we randomly pick half of the platforms to
move horizontally and the rest vertically. This task requires the control
policy to infer both the position and velocity of the platforms and thus
presents a more challenging representation learning problem. To enable the
model to infer velocity information, we stack a history of three recent images
as input to the policy for this task, which slightly changes the observation
spec.

##### Indoor navigation

For the indoor navigation task, we use a scan of the building interior with
size about $25\times 15$m. We randomly place $50$ boxes of different sizes in
the scanned scene to model obstacles during navigation. Among the $50$
obstacles, $20\%$ are sampled with length in $[1.6,2]$m, width in $[0.7,1]$m,
and height in $[0.4,1.2]$m, which are to mimic bigger obstacles like sofa.
$40\%$ are sampled with length and width in $[0.5,0.8]$m and height in
$[0.4,1.4]$m, which represent smaller obstacles like chairs. The rest $40\%$
are sampled with length and width in $[0.1,0.4]$m and height in $[0.8,2.0]$m,
which correspond to taller objects like pillars.

TABLE I: Action space ranges action | lower bound | upper bound
---|---|---
Target local foothold | (-0.05, -0.05, -0.03)m | (0.1, 0.05, 0.03)m
Target peak swing height | 0.05m | 0.1m
Desired CoM height | 0.42m | 0.47m
Desired base roll | -0.1 | 0.1
Desired base pitch | -0.2 | 0.2
Desired base twist speed | -0.2 | 0.2


# Expectation Entropy as a Password Strength Metric

Khan Reaz, Gerhard Wunder This work is carried out within “PHY2APP:
Erweiterung von Physical Layer Security für Ende-zu-Ende Absicherung des IoT"
project, which is funded by the German Federal Ministry of Education and
Research (BMBF) under grant number 16KIS1473 [1] Cybersecurity and AI Research
Group
Freie Universität Berlin, Germany
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The classical combinatorics-based password strength formula provides a result
in tens of bits, whereas the NIST Entropy Estimation Suite give a result
between 0 and 1 for Min-entropy. In this work, we present a newly developed
metric – Expectation entropy that can be applied to estimate the strength of
any random or random-like password. Expectation entropy provides the strength
of a password on the same scale as an entropy estimation tool. Having an
Expectation entropy of a certain value, for example, 0.4 means that an
attacker has to exhaustively search at least 40% of the total number of
guesses to find the password.

###### Index Terms:

Password, Entropy, Randomness, NIST Entropy Estimation Tool

##  I Motivation

The recipe for constructing a strong password has two ingredients: randomness,
and length, i.e., the characters of the password must have high randomness
(ideally truly random) and the number of characters should be large. A good
combination of these properties can make brute-force attacks infeasible for
that password.

State-of-the-art password strength estimation methods can be grouped into
three main categories [2]: (1) Attack-based methods estimate the time it takes
to break it with brute force. (2) Heuristic-based methods are based on
Shannon’s notion of entropy bits. (3) Probabilistic-based methods consider
human intrinsic nature, context, and imposed password composition rules.
NIST’s Entropy Estimation Suite [3] is the industry standard solution to
estimate min-entropy using 10 tests as described in [4], [5].

In our previous work [6], the device provisioning problem of Wi-Fi personal
mode has been addressed and provided with ComPass protocol to supplement
WPA2/WPA3. ComPass foregoes the pre-printed or user-generated password with an
automatically generated strong symmetric password for the participating
devices. The generated password is between 16 and 32 characters long and is
generated by extracting signal parameters from typical Wi-Fi OFDM signals
using Physical Layer Security methods. As we wanted to analyse the randomness
of the quantise bit-string, and the strength of the generated password, we
noticed that the classical combinatorics-based password strength formula:
$\log_{2}(\text{character space}^{\text{length of the password}})$ provides
the result in tens of bits, whereas entropy estimation formulae (and NIST
entropy estimation tool) give a result between 0 and 1.

In this work, we present a newly developed metric – Expectation entropy that
can be applied to estimate the strength of any random or random-like password.
It captures the composition of the characters and estimate the strength from a
single password. Expectation entropy provides the strength of the password on
the same scale as entropy estimation formulae and NIST Entropy Estimation
Suite.

##  II Various Definitions of Entropy

Entropy is a measure of the disorder, randomness or variability in a closed
system. The larger the amount of entropy, the greater the uncertainty in
predicting the value of an observation. It is usually denoted by $H$. If
$p_{i}$ is the probability of an element of a random discreet variable, then
the min-entropy, $H_{\infty}$ is the largest value $m$ having the property
that each observation of the variable guarantees at least $m$ bits of
information: $H_{\infty}=-\log_{2}(max(p_{i}))$.

Shannon entropy, $H_{1}$ (or just $H$) was introduced by Claude Shannon in [7]
as : $H_{1}=-\sum_{i=1}^{N}p_{i}\log_{2}pi$, where $N=2$ for binary digits,
and $N=26$ for English letters. Shannon entropy gives an average estimate and
ignores the length of the password. Ralph Hartley proposed a quantitative
measure of “information” two decades prior to Shannon [8]. Hartley entropy
measures only the size of the distribution and ignores the probabilities:
$H_{0}=\log_{2}N$.

However, in a password cracking case, an attacker must guess each value one at
a time which makes all previously mentioned metrics unrelated to guessing
difficulty [9]. Massey [10], Cachin [11], and Pliam [12] individually
developed the Guessing entropy concept which states the expected number of
guesses required if the attacker optimally tries: $G=\sum_{i=1}^{N}p_{i}\cdot
i$.

##  III Expectation entropy

Let us define four disjoint element sets such that $\mathcal{L}$ be the set of
lower-case letters, $\mathcal{U}$ be the set of upper-case letters,
$\mathcal{D}$ be the set of digits, and $\mathcal{S}$ be the set of symbols.
Which means, $|\mathcal{L}|=26$, $|\mathcal{U}|=26$, $|\mathcal{D}|=10$,
$|\mathcal{S}|=32$, and their disjoint union resulting in the total character
space $\mathcal{K}$ of cardinality
$|\mathcal{K}|=|\mathcal{L}|+|\mathcal{U}|+|\mathcal{D}|+|\mathcal{S}|=94$ for
English language. Naturally, one can choose the character space for a
different language.

A password $P$, where each of its character $c$ is chosen uniformly at random,
is called valid if it contains characters from at least two disjoint element
sets, and the password length $|P|$ satisfies
$min(|\mathcal{L}|,|\mathcal{U}|,|\mathcal{D}|,|\mathcal{S}|)\leq|P|$. Then
the probability of a character from each element sets would be:
$p_{\mathcal{L}}=\mathbb{P}(c\in\mathcal{L})=\frac{26}{94}$,
$p_{\mathcal{U}}=\mathbb{P}(c\in\mathcal{U})=\frac{26}{94}$,
$p_{\mathcal{D}}=\mathbb{P}(c\in\mathcal{D})=\frac{10}{94}$, and
$p_{\mathcal{S}}=\mathbb{P}(c\in\mathcal{S})=\frac{32}{94}$.

If $l,u,d,s$ are the number of characters chosen at random from $\mathcal{L}$,
$\mathcal{U}$, $\mathcal{D}$, $\mathcal{S}$ sets respectively such that
$l,u,d,s\leq|\mathcal{K}|$. We find the expectation of a character $c$
appearing in a password as:

$E(c(P))=p_{\mathcal{L}}\cdot l+p_{\mathcal{U}}\cdot u+p_{\mathcal{D}}\cdot
d+p_{\mathcal{S}}\cdot s$ (1)

The maximum entropy (which is traditionally defined as Hartley entropy) of the
total character space, $\mathcal{K}$ is
$H_{0}(\mathcal{K})=\log_{2}|\mathcal{K}|$. Then we express the Expectation
entropy $H_{E}$ of the password $P$ as:

$H_{E}(P)=\frac{\log_{2}E(c(P))}{H_{0}(\mathcal{K})}$ (2)

It is not difficult to show that the upper bound is achieved for the random
variable $E(c(P))$ if and only if $l,u,d,s$ are equal to
$4\cdot|\mathcal{K}|$. When the password length is larger than the
restriction, $H_{E}$ gives a value more than 1, and for the smaller length it
gives a negative value.

##  IV Results

Empirical evaluation has been done using two different types of datasets. In
the first case, 100,000 random passwords are generated using a computer with a
dedicated hardware random number generator. These passwords are labelled with
RandomMin, Random10ch, Random32ch, Random128ch, and RandomMax based on the
length of the password. In the second case, three publicly leaked password
databases (LinkedIn, 10Million, and WPA2) were used for evaluation.

Figure 1: Comparison of Expectation entropy for randomly generated passwords
with different length. Figure 2: Comparison of Expectation entropy for leaked
passwords.

Fig. 1, and Fig. 2 summarise the result in terms of Cumulative Distributive
Function (CDF) and Expectation entropy. It can be observed from Fig. 1 that
the value of $H_{E}$ increases or decreases according to the length of the
password and satisfies the bounds. Fig. 2 shows that the publicly leaked
databases mostly contain passwords with a short length and the characters of
the password are not chosen from all element sets, hence low Expectation
entropy. Having an Expectation entropy of a certain value, for example, 0.4
means that an attacker has to exhaustively search at least 40% of the total
number of guesses to find the password using brute-force.

## References

  * [1] Bundesministerium für Forschung und Bildung, “ Erweiterung von Physical Layer Security für Ende-zu-Ende Absicherung des IoT (PHY2APP),” _URL: https://is.gd/foSnNd_, 2021-2023.
  * [2] J. Galbally, I. Coisel _et al._ , “A new multimodal approach for password strength estimation—Part I: Theory and algorithms,” _IEEE Tran. on Information Forensics and Security_ , vol. 12, no. 12, 2016.
  * [3] J. Hill, K. McKay _et al._ , “ NIST SP800-90B Entropy Assessment C++ package,” _NIST_ , 2022, available at: https://github.com/usnistgov/SP800-90B_EntropyAssessment.
  * [4] M. S. Turan, E. Barker _et al._ , “Recommendation for the Entropy Sources Used for Random Bit Generation,” _NIST Special Publication_ , vol. 800, no. 90B, 2018.
  * [5] W. Burr, D. F. Dodson _et al._ , “ Electronic Authentication Guideline,” _NIST Special Publication 800-63-2_ , 2013.
  * [6] K. Reaz and G. Wunder, “ComPass: Proximity Aware Common Passphrase Agreement Protocol for Wi-Fi Devices Using Physical Layer Security,” in _Innovative Mobile and Internet Services in Ubiquitous Computing_. Springer, 2022, pp. 263–275.
  * [7] C. E. Shannon, “Prediction and entropy of printed English,” _Bell system technical journal_ , vol. 30, no. 1, pp. 50–64, 1951.
  * [8] R. V. Hartley, “Transmission of information 1,” _Bell System technical journal_ , vol. 7, no. 3, pp. 535–563, 1928.
  * [9] J. Bonneau, “Guessing human-chosen secrets,” Ph.D. dissertation, University of Cambridge, 2012.
  * [10] J. L. Massey, “Guessing and Entropy,” in _IEEE International Symposium on Information Theory_ , 1994, p. 204.
  * [11] C. Cachin, “Entropy measures and unconditional security in cryptography,” Ph.D. dissertation, ETH Zurich, 1997.
  * [12] J. O. Pliam, “On the Incomparability of Entropy and Marginal Guesswork in Brute-force Attacks,” in _International Conf. on Cryptology_. Springer, 2000, pp. 67–79.