# Revisiting Reward Design and Evaluation for
Robust Humanoid Standing and Walking

Bart van Marum, Aayam Shrestha, Helei Duan, Pranay Dugar, Jeremy Dao, Alan
Fern All authors are with the Dynamic Robotics and Artificial Intelligence
Laboratory. Oregon State University. Corvallis, Oregon, USA. Email: {vanmarub,
shrestaa, duanh, dugarp, daoje<EMAIL_ADDRESS>
###### Abstract

A necessary capability for humanoid robots is the ability to stand and walk
while rejecting natural disturbances. Recent progress has been made using sim-
to-real reinforcement learning (RL) to train such locomotion controllers, with
approaches differing mainly in their reward functions. However, prior works
lack a clear method to systematically test new reward functions and compare
controller performance through repeatable experiments. This limits our
understanding of the trade-offs between approaches and hinders progress. To
address this, we propose a low-cost, quantitative benchmarking method to
evaluate and compare the real-world performance of standing and walking (SaW)
controllers on metrics like command following, disturbance recovery, and
energy efficiency. We also revisit reward function design and construct a
minimally constraining reward function to train SaW controllers. We
experimentally verify that our benchmarking framework can identify areas for
improvement, which can be systematically addressed to enhance the policies. We
also compare our new controller to state-of-the-art controllers on the Digit
humanoid robot. The results provide clear quantitative trade-offs among the
controllers and suggest directions for future improvements to the reward
functions and expansion of the benchmarks.

##  I Introduction

Figure 1: We propose a set of metrics with an easy-to-setup testing fixture
and provide quantitative results towards the controller performance in the
real-world. Our proposed RL-based method produces a robust standing-and-
walking controller for the humanoid robot Digit. The learned controller can
handle a set of significant amount of disturbances, such as lateral push at
150N for 500ms shown in A and sagittal push at 200N for 500ms shown in B. The
controller is able to walk, stand, and seamlessly transition between these two
settings.

Humanoid robots hold the promise to deliver enormous amounts of human-like
physical labor across varied real-world spaces. A precondition for realizing
this potential is for humanoids to be able to stand and walk (SaW) in natural
settings while withstanding typical disturbances encountered during
deployments. In particular, walking provides mobility and standing provides
the foundations for humanoid manipulation tasks. For more traditional wheeled
based robots, designing controllers for analogous SaW behaviors is relatively
straightforward due to the inherent stability of wheeled platforms. However,
for humanoids, even these basic SaW behaviors are a challenge due to the
inherent instability of bipedal systems.

There has been recent progress in bipedal locomotion through sim-to-real
reinforcement learning (RL) [1, 2, 3, 4, 5]. The approaches train controllers
in simulation using various reward functions to shape the locomotion behavior
while domain randomization to help transfer to the real world. While these
approaches have yielded impressive real-world video demonstrations, there have
not been repeatable quantitative evaluations that allow for clear comparison
of the real-world trade-offs among different methods. This limits our ability
to systematically explore the space of reward functions to develop effective
SaW controllers. The lack of systematic evaluation is especially pressing as
current reward functions are often based on engineered constraints which may
be counter-productive for producing reliable SaW behaviors under disturbances.
S

In this paper, we address the above issues with the goal paving the way for
experimentally measurable progress in SaW control learning. Our first
contribution is to introduce a SaW benchmarking procedure that specifies
repeatable physical experiments for measuring real-world metrics of SaW
controllers. Importantly, these experiments can be conducted without expensive
equipment, using simple devices that can be constructed from readily available
materials. As our second contribution, we leverage the proposed benchmark to
clearly identify areas of improvement for current reward functions, leading us
to revisit the reward-design problem for SaW controllers. We attempt to
construct a minimally-constraining reward function that avoids undesired
behavior with the hope that such a reward function will allow for more
flexibility in learning to reject disturbances and react to changing commands.
Our third contribution is to use the benchmarking procedure to evaluate and
compare our new controller with the manufacturer-supplied controller and a
current state-of-the-art reward function. The results reveal trade-offs that
would not be apparent without the rigor of repeatable experiments, emphasizing
the importance of systematic evaluation in advancing the field of SaW control
learning.

Importantly, we are not claiming that the current SaW benchmarks are complete
or that the new reward function is truly minimal and cannot be further
improved. Instead, we view the SaW benchmarks and new reward function as
starting points on a trajectory of continual, measurable real-world
improvements. Indeed, our experiments in this paper already point to
directions for improvement.

##  II Problem Statement and Related Work

We consider the problem of producing a controller for a bipedal humanoid robot
that supports the following two commands: 1) Stand. The robot should stop if
moving and stand in place with two feet on the ground. 2) Walk. The robot
should walk at a specified velocity (direction and speed) and a specified
heading with an important special case corresponding to rotating in place.
Note that the key distinction between standing and walking is that for
standing the default behavior should be for both feet to be on the ground,
while for walking, including walking in place, the feet cycle through stance
and swing phases.

To be useful in practice, a _standing and walking (SaW)_ controller must be
able to reliably switch between different commands and reject physical
disturbances, such as bumps or terrain features, that may occur in an
application. The primary objective of disturbance rejection is to prevent the
robot from falling, while the secondary objective is to minimize departure
from the commanded behavior. For example, when commanded to stand the
occurrence of a large enough disturbance may require the robot to take a step
in order to avoid falling, which conflicts with the default command objective
of having two feet on the ground. However, we would typically prefer the robot
to take the step, rather than risk falling by struggling to keep both feet
planted.

Prior Standing and Walking Control. There have been a number of prior
approaches for model-based humanoid SaW control [6, 7, 8, 9, 10]. More
recently, there has been significant progress in using sim-to-real RL for
training bipedal locomotion controllers, e.g. blind locomotion for multiple
gaits [1, 2, 3], locomotion under different loads [4], and visually-guided
locomotion over irregular terrain [5]. In many cases, these controllers do not
have a native standing mode and instead walk in place. In cases where standing
is explicitly supported, a separate standing controller is usually designed or
trained (e.g. [11, 12, 13]).

One challenge in using separate standing and walking controllers is that
switching between the control modes is not always straightforward. This is
because the control state-spaces of each controller have little native
overlap, which requires the use of difficult to tune heuristics to yield
smoother and more reliable transitions. For example, this may involve hand-
engineered cycle-time constraints in transitioning from waking to standing
[11] or blending the outputs of the controllers at transition points [12, 14].
Another approach to improving controller switching is to train controllers for
different behaviors from starting states typical of other behaviors [12],
which raises the challenge of generating appropriate start state
distributions. Alternatively, in this work, we choose to train a single SaW
controller that does not require any form of reference or clock-based inputs,
and natively learns to switch freely between commands throughout the entire
learning process.

Reward Functions for Bipedal Locomotion. One of the challenges in sim-to-real
RL for bipedal locomotion is specifying a reward function that results in the
desired locomotion characteristics. Prior work has used highly prescriptive
reward functions to describe preferred characteristics of the behavior to be
learned. This includes clock-based rewards that asserts preferences for stance
and swing phases in alignment with periodic clocks [1], and reference-motion
rewards that attempt to imitate joint or task space reference trajectories
captured from humans [15, 16] or produced through optimization [17]. Designing
such prescriptive reward functions is expensive and brittle as they must be
retargeted to each robot and behavior variation (e.g. velocity) or extensively
tuned and do not handle transitions between gaits well. For example, prior
work on fast locomotion (i.e. running) requiring substantial manual tuning for
transitions between multiple speed gaits and standing [11]. While such
prescriptive reward designs have yielded impressive controllers it is unclear
whether they are placing unnecessary, or even counter-productive constraints,
on the learned controllers. For example, handling disturbances can require
generating behavior that significantly departs from the constraints imposed by
the periodic clock or reference motions. These challenges provide our
motivation for investigating minimally-constraining reward functions in this
paper.

Evaluating Locomotion Controllers. The vast majority of prior work on model-
based and RL-based control for bipedal locomotion does not report real-world
performance metrics based on repeatable experiments. Instead, the primary
method of demonstrating real-world performance is based on producing videos of
the controllers in action. For example, many studies are limited to apply
external disturbances by human experimenters [2, 18] or demonstrating the
robot traversing arbitrary terrains and obstacles [1], which are non-
reproducible and not quantitative. Some exceptions do consider hardware setups
for repeatable tests of specific tasks [19], such as disturbance rejection and
low-level velocity tracking. For example, prior work [20] used an impact
generator, similar to those used in vehicle testing, which provides repeatable
quantitative results, but is not widely available to researchers. The failure
to establish objective measurements of real-world performance that can be
easily implemented by most researchers has made it difficult to judge progress
and compare competing methodologies. This failure motivates our proposal in
this paper for simple metrics that can be experimentally measured using widely
available materials and devices.

##  III Quantitative SaW Performance Benchmark

We propose a reproducible set of benchmarks for quantitatively assessing key
aspects of a SaW controller in the real-world. These metrics quantify the
disturbance rejection ability, accuracy in command following, and energy
efficiency. The benchmark is intended to allow comparison of any SaW
controller, regardless of what method a controller is based on.

###  III-A Disturbance Rejection

To enable standardized comparison, we propose a formal impulse perturbation
test with precise control over disturbance parameters. Specifically, our
method applies a force $\boldsymbol{F}$ of fixed magnitude and duration
$\Delta t$ to the robot base, generating an impulse $\boldsymbol{J}$. By
systematically varying $\boldsymbol{F}$ and $\Delta t$ over a range of values,
we can quantify performance in terms of the success rate for recovery after
experiencing the impulse $\boldsymbol{J}$.

In order to objectively measure this metric in the real world it is necessary
to apply forces consistently in a repeatable manner, without human input. To
that end we construct a simple impulse application device from off the shelf
materials.

Figure 2 shows our impulse application device in the lab environment. The
impulse applicator works by releasing a weight suspended by magnets, which is
automatically disconnected after a preset duration. After applying a fixed
duration impulse, the robot is freely able to recover. We provide a
video111included in submission to further clarify this procedure and will
open-source the part list and construction details.

Figure 2: An impulse is applied to the robot by means of a weight connected by
a rope. Force $\boldsymbol{F}$ is regulated by adding and removing weight.
Duration $\Delta t$ is regulated by a microcontroller that automatically
disconnects the weight from the rope, after a set amount of time. The rope is
always attached to Digit at the same height of 122 cm.

Metric 1: Standing Fall Percentage. In this paper, to simplify the measurement
setup, we limit the experimental scope to characterizing disturbance rejection
when standing. We focus on disturbances in the positive and negative X and Y
directions, where the positive X direction is the direction faced by the
robot. For each direction and selected combinations of weight and duration, we
compute the metric value over multiple trials. Each trial involves
initializing the robot by issuing a standing command and then using the device
connected in the appropriate direction to provide the specified impulse weight
and duration. The metric value is the percentage of trials leading to success,
where a trial is successful if the robot does not fall. There are many
variations of this metric using the same device that can be considered in
future work. For example, defining more detailed metrics such as how much the
average robot position changed after the disturbance, the time taken for
recovery, or the same procedure can be applied to a robot when walking at a
particular speed.

###  III-B Command Following

Precisely executing commanded motions is essential for a humanoid robot to
reliably perform planned behaviors. However, metrics of command following
accuracy often rely on motion capture systems, limiting reproducibility. To
address this, we propose three simple metrics that measure the accuracy of
velocity control and control of in-place robot rotation.

Metrics 2 and 3: In-Place Rotation Accuracy. For certain applications it is
useful for a humanoid to be able to rotate its body to a particular
orientation while remaining in place. To test this we conduct trials where the
robot starts in a standing position in the middle of a 2ft diameter circle,
which is considered the region of zero positional error. The robot is then
given a command to rotate at angular velocity $\omega_{z}$ for $\Delta t$
seconds, which ideally should correspond to a commanded orientation change of
$\theta_{c}=\omega_{z}\cdot\Delta t$. We compute two metrics at the end of the
trial: 1) _angular error_ , which is the difference between the commanded
angular rotation and the actual rotation, and 2) _lateral drift_ , which is
measured as the distance of the furthest foot from the boundary of the
starting circle.

Metric 4: Velocity Accuracy. We consider a simple velocity tracking test using
only basic measurements. Specifically, we issue a constant velocity command
$v$ for duration $\Delta t$, which should ideally produce a net translation of
$d_{c}=v\cdot\Delta t$. For our current procedure, each trial of the
experiments starts the duration clock when the robot is in a standing position
and then after $\Delta t$ seconds the standing command is issued. The distance
traveled is then manually measured and averaged across trials. By comparing
the actual distance traveled $d_{r}$ to the commanded distance $d_{c}$, we can
quantify velocity control performance without specialized equipment. This
metric assumes that the SaW controller under test is able to walk on flat
terrain without falling. Note that, this procedure does not explicitly account
for startup and stopping times for the robot. Instead, velocity ramp up and
down are assumed symmetrical, canceling out. If this level of inaccuracy is of
concern, then the procedure can be modified accordingly.

###  III-C Energy Efficiency

Metric 5: Energy Efficiency. In addition to quantifying the accuracy of
command execution, energy efficiency of command execution is an important
performance metric for real-world humanoid viability. More efficient gaits
directly extend operational runtime by conserving battery power. Additionally,
a more efficient gait reduces mechanical wear from torque and impacts,
prolonging hardware lifespan. The energy usage of a gait over a duration
$\Delta$ is given by:
$E=\int_{0}^{\Delta}\boldsymbol{\tau}_{t}\cdot\boldsymbol{\omega}_{t}\,dt$,
where $\boldsymbol{\tau}_{t}$ represents the motor torques at time $t$ with
the motor angular velocities $\boldsymbol{\omega}_{t}$. In our experiments we
estimate the energy usage over a time interval by using the robots estimated
torques, rather than the actual torques, due to the lack of a torque sensor
and current draw information. As a metric we report the average energy usage
per meter traveled to normalize for different travel distances.

##  IV SaW Training and Reward Design

Below, we first describe our controller architecture and simulation-based
training framework. Next, we describe the design of our SaW reward function
that aims to minimally constrain the learned behavior.

###  IV-A Architecture and Training Framework

Our SaW controller is a (64, 64) two-layer long short-term memory (LSTM) [21]
recurrent neural network. The input to the network consists of: 1) the current
robot state [motor velocities, motor positions, joint velocities, joint
positions, torso orientation], and 2) the user command
$c_{u}=[c_{x},c_{y},c_{yaw}]$, specifying the desired x, y, and angular
velocities, where standing corresponds to $c_{u}=[0,0,0]$. The output action
of the controller is the joint-space PD setpoints for all 20 actuators. The
SaW controller is operated at 50Hz with the PD controllers operating at 2kHz.
We train the controller using the Proximal Policy Optimization (PPO) [22] RL
algorithm, which is extended with a mirror loss, to encourage symmetry in
policy behavior.

We follow a standard episodic RL training process. Each episode begins with
the robot initialized in a default standing position and lasts for 16 seconds
of simulated time, or is terminated early when the robot falls. During an
episode a new user command is uniformly sampled every $2$ to $6$ seconds from
five categories: [standing, walking in sagittal plane, walking laterally,
rotating in place, omnidirectional walking]. User command ranges are sampled
from $c_{x}$: $[-0.5,2.0]$ m/s, $c_{y}$: $[-0.5,0.5]$ m/s, $c_{yaw}$:
$[-0.5,0.5]$ rad/s.

In addition, during each episode, for each frame there is a 1% chance of
getting a random push to encourage disturbance rejection capability. These
random pushes were uniformly sampled from a range of 200N to 800N, lasting a
single timestep (20ms). Our early ad-hoc testing indicated that using a more
diverse distribution did not improve performance. However, as we will see in
our experiments, our real-world benchmarking process will lead to a different
conclusion (see Section V-B).

###  IV-B Reward Design

During an episode, we seek a reward function that indicates throughout an
episode how well the behavior satisfies the current user command.
Additionally, the reward function should achieve this, while also minimally
constraining other aspects of the learned behavior. Our design process began
with an enumeration of the reward terms found in the many prior studies on RL
for legged-robot locomotion. We then progressively added terms based on
observations of intermediate learned policies. The resulting reward function
is composed of a number of additively weighted reward terms, which are shown
in Table I along with the associated weights. Below we outline the essential
role that each term plays in the overall design.

Basic Command Following. The first three essential components in Table I
measure how well the current robot velocities and orientation match the
commands. We found that training with just these components results in a
hopping locomotion behavior, where the robot moves by jumping with both feet.
While this behavior satisfies the commands, it is not desirable walking
behavior indicating that additional reward terms are required.

Single Foot Contact. To address hopping we have found multiple approaches that
can individually be added to the above three reward terms to learn to walk
instead. These include: 1) adding a base height reward, 2) clock based rewards
and inputs [23], 3) tuning exploration noise, 4) a feet contact transition
reward, and 5) a single feet contact reward. We found that the most reliable
and unconstrained way to produce walking instead of hopping is via the single
foot contact reward, which also does not require tuning.

For non-standing commands, the single foot contact component provides a reward
of 1 at each time step where only one foot is in contact with the ground. To
allow for some overlap in the stance and swing phases, we add a grace period
of $0.2$ seconds. This means that if single contact occurred at least once in
the last $0.2$ seconds, the reward is granted, otherwise the reward is 0.

For the standing command, this reward component is a constant of 1, giving no
preference for foot contact. Intuitively, we might expect standing to involve
rewarding double foot contact. However, this is problematic since it penalizes
the recovery steps needed to reject disturbances, as that requires breaking
ground contact of at least one of the feet. Additionally, when transitioning
from walking to standing, requiring double foot contact will cause a policy to
opt for the closest stance position rather than the most stable one. Thus, to
learn standing while avoiding these problems we opt to implicitly reward
standing utilizing existing reward terms. It turns out that most reward terms
will be greater when a policy stands still with both feet on the ground, than
when it steps in place or only stands on one foot.

Sim-to-Real and Style. While the combination of the above reward terms are
enough to reliably train a SaW controller in simulation, RL often results in
controllers that lack certain stylistic characteristics that can influence
visual properties and more importantly stability of sim-to-real transfer. We
note that, it is not clear whether these stylistic characteristics are missing
due to the inability of RL to perfectly optimize the above reward terms, or if
the above terms are inherently inadequate. In either case, the inclusion of
additional stylistic reward terms is intended to more reliably and quickly
lead RL to acceptable solutions. The following terms are ones that we have
found to be important to include, noting that a more exhaustive analysis may
reveal a more minimal set.

  * •

_base height_ : maintain a consistent base height during different modes and
commands.

  * •

_feet air time_ : this term regularizes the stepping frequency by applying a
penalty of 0.4 at each foot touchdown, which can be counteracted by a positive
reward component equal to the number of seconds since the foot has been in the
air (airtime). Without this component the learned controllers tend to favor
gaits with step frequencies that are stylistically too large, which may be due
to those frequencies corresponding to likely local minima. This component is a
constant when standing.

  * •

_feet orientation_ : make feet point out straight at all times, except when
commanded to rotate.

  * •

_feet position_ : loosely define the foot position during stance, to prevent
undesired stance positions.

  * •

_arm position_ : loosely defines desired joint angles for the arms to prevent
unwanted arm movements, while allowing use of arms for balancing. This
stylistic component can be important to minimize the potential for self-
collisions.

  * •

_base acceleration_ : prevent jerky base motions.

  * •

_action difference_ : minimize changes in actions between timesteps.

  * •

_torque_ : minimize torque usage.

No Clocks. While prior work that uses clock-based reward signals (e.g. [23])
does allow for standing, the nontrivial question of what to do with the
required clock inputs during standing and transitions remains a challenge.
Additionally, the clock framework incentivizes low foot velocities in standing
mode, which directly impedes disturbance rejection capabilities. Rather, the
above reward function does not require reference clocks, trajectories or
signals of any sort to learn walking, and allows a policy to control such
parameters internally. Without such signals we eliminate the problem of having
to engineer the transitions between standing and walking modes. Additionally
for disturbance rejection, without any references to attain to, the policy is
free to move feet in any way it seems fit to stay upright.

TABLE I: Reward Terms

Reward Term | Definition | Weighting
---|---|---
$x,y$ velocity | $\begin{cases}e^{-5\cdot(v_{xy}-c_{xy})}&\text{if }c_{s}\\\ e^{-5\cdot(v_{xy}-c_{xy})^{2}}&\text{else }\end{cases}$ | 0.15, 0.15
Yaw orient. | $e^{-300\cdot qd(\mathbf{q}_{yaw},\mathbf{c}_{yaw})}$ | 0.1
Roll, pitch orient. | $e^{-30\cdot qd(\mathbf{q}_{rp},\mathbf{c}_{rp})}$ | 0.2
Feet contact | $\begin{cases}1&\text{if }c_{s}\\\ 1&\text{if }n_{c,t^{*}}=1\text{ for any }t^{*}\in[t-0.2,t]\\\ 0&\text{else}\end{cases}$ | 0.1
Base height | $e^{-20\cdot|p_{z}-c_{h}|}$ | 0.05
Feet airtime | $\begin{cases}1&\text{if }c_{s}\\\ \sum_{f\in(l,r)}(t_{air,f}-0.4)*\mathds{1}_{td,f}&\text{else}\end{cases}$ | $1.0^{\dagger}$
Feet orientation | $\begin{cases}e^{-\sum|\mathbf{r}_{\text{feet, rp}}-\mathbf{c}_{feet,\text{rp}}|}&\text{if }|c_{yaw}|>0\\\ e^{-\sum|\mathbf{r}_{\text{feet, rpy}}-\mathbf{c}_{feet,\text{rpy}}|}&\text{else}\end{cases}$ | 0.05
Feet position | $\begin{cases}e^{-3\cdot|\mathbf{p}_{feet}-\mathbf{c}_{feet}|}&\text{if }c_{s}\\\ 1&\text{else}\end{cases}$ | 0.05
Arm | $e^{-3\cdot||\boldsymbol{\theta}_{\text{arm}}-\boldsymbol{c}_{\text{arm}}||}$ | 0.03
Base acceleration | $e^{-0.01\cdot\sum|\mathbf{b}_{xyz}|}$ | 0.1
Action difference | $e^{-0.02\cdot\sum|\mathbf{a}_{t}-\mathbf{a}_{t-1}|}$ | 0.02
Torque | $e^{-0.02\cdot\frac{1}{N}\sum|\mathbf{t}_{\text{motor}}|/\mathbf{t}_{\text{max}}}$ | 0.02

  * •

$c$ = a command; $c_{s}$ = standing command; $q$ = a quaternion; $p$ = a
position; $\boldsymbol{b}$ = base acceleration; $qd(\cdot)$ = quaternion
distance function; $n_{c}$ = number of feet in contact with ground;
$\mathds{1}_{td}$ = boolean variable indicating a touchdown in the current
timestep; † = note that the feet airtime reward is the only sparse reward,
therefore the weight is significantly higher than other terms.

##  V Evaluation Results

In this section, we use our proposed benchmarking procedure to evaluate and
compare three SaW controllers for the Digit V3 humanoid robot manufactured by
Agility Robots: 1) _Single Contact RL._ trained using our minimally-
constrained SaW reward function from Table I, 2) _Clock Based RL._ trained
using a state-of-the-art clock-based [23] reward function, and 3) _Agility
Controller._ the manufacturer-provided controller. In addition, we describe
how the results motivated the training of a new SaW controller, called _Single
Contact++ RL_ , which yielded measurable improvement.

###  V-A Disturbance Rejection While Standing

Figure 3: Disturbance rejection success rates for various humanoid SaW
controllers in the $x$-direction (left) and $y$-direction (right). Results
show that our Single Contact++ reward function outperforms competing
alternatives. Our Single Contact controller shows asymmetric and non-monotonic
results in the $y$-direction, emphasizing the importance of systematic
evaluation.

Metric 1: Standing Fall Percentage. We use our impulse application setup to
conduct disturbance rejection experiments on the robot. For each impulse, we
attempt 5 trials to gauge reliability and stop testing at the first failure to
avoid damage to the robot. Figure 3 show results for $x$ and $y$ directions
respectively. We note the number of tests for every impulse in the plots. The
range for force and duration is $[79,214]$ N and $[200,500]$ ms. We chose
these ranges of forces and durations to yield a set of impulses that are both
challenging to all controllers, while minimizing risk of damage to the
hardware. The upper end of the force range corresponds to approximately half
the robot weight.

We find that the Single Contact RL Controller outperforms the Clock based
controller in the x-direction, for both forward and backward pushes, as
expected. Interestingly there are large asymmetries and gaps showing up for
the Single Contact RL controller in the y-direction. Unintuitively, in some
cases a higher impulse push can be more easily dealt with than a lower
impulse. This is unexpected, and underscores that claims of stability must be
substantiated through formal experiments.

###  V-B Benchmark Guided Improvement

The above results revealed several weaknesses in the disturbance rejection
profile of the Single Contact RL controller. In particular, the maximum
backward force and duration led to complete failure and there were many gaps
in the y-direction disturbance profile. These results led us to hypothesize
that the limited disturbances used in our simulation training episodes were
not adequate for the desired sim-to-real robustness. We trained a new version
of Single Contact RL, called _Single Contact++ RL_ , by using the same reward
function but adjusting the simulated disturbances to be closer to the test
distribution. Specifically, the random pushes are uniformly sampled from [20N,
200N] and [200ms, 500ms] in all three dimensions, and no other pushes are
sampled while a push is executing. In addition, in an attempt to encourage
improved drift performance we increased the length of the window from which
random commands are sampled from [40, 100] timesteps to [100, 300] timesteps.

The results of disturbance benchmarking for this new controller are in Figure
3 and show significant improvement, achieving perfect disturbance rejection in
our tests. Additionally we performed single tests of 258 N, which the Single
Contact++ RL controller passed, though we do not investigate this further due
to the risk of damaging the hardware. This result shows the utility of the
proposed benchmarking approach for driving measurable improvement.

###  V-C Command Following

Metrics 2 and 3: In-Place Rotation Accuracy. We measured the drift and heading
accuracy for all controllers rotating at 0.5 rad/s for 1, 5 and 30 seconds.
The results in Figure 4 reveal substantially lower drift for the RL
controllers compared to the model-based Agility Controller. The Agility
Controller especially suffers large drifts up to 2 meters in the 30 second
test. Interestingly, the clock based controller has the largest drift for the
1 second test. We observe from the foot motions that this is caused by the
clocks suddenly changing due to transitioning from standing to walking. We
observe in our testing that the Single Contact controllers sway less during
rotating, causing a lower drift. Finally, the Single Contact++ controller
performs best in all cases. We hypothesize this is due to the longer time
range used for command windows during its training, which allows RL to become
more sensitive to drift that accumulates over longer time periods.

Figure 4 also shows the RL controllers having very low angular error compared
to the Agility controller. This is likely due to an architectural difference,
as our controller tracks a rotating heading, rather than a yaw velocity. The
result is that the RL controllers are highly accurate in rotating a desired
number of degrees.

Figure 4: Command following accuracy for turning in place. Error bars are
standard deviation. Also note that the 30 seconds drift results for Agility
Controller were in some cases helped by the robot tether. It is safe to assume
results without tether would have been closer to the upper end of the error
bar.

Metric 4: Velocity Accuracy. We test velocity command following accuracy by
commanding 1 m/s for 10 seconds. The resulting distances are shown in Figure
5. We find that the Agility Controller undershoots the target, yielding an
average velocity of 0.74 m/s. The Clock Based RL controller is most accurate
at 1.04 m/s, while the Single Contact RL Controller overshoots at 1.13 m/s.
The overshooting performance of the Single Contact RL controller does not
occur in simulation, where the actual velocity is slightly below the commanded
1 m/s. This indicates a sim-to-real inconsistency. Interestingly, the increase
in speed between sim and real is three times less for the Clock-Based policy,
indicating that the constraint imposed by the clock might help this aspect of
sim-to-real transfer. This point deserves further investigation. These metrics
were not recorded for Single Contact++ due to a hardware failure during
experiments close to the submission deadline.

###  V-D Energy Efficiency

Metric 5: Energy Efficiency. During the same 10 second walk we record positive
work done by the motors and plot the power usage in Figure 5. Interestingly
the Agility Controller uses less energy than both RL controllers, when
accounting for the difference in distance traveled. This is also apparent
visually during tests, as the RL controllers stomp more loudly. It is
interestingly to realize that at least 33 J/m are not being spent usefully by
the RL controllers. We hypothesize that higher energy usage might correspond
to the situation where our RL controllers would always anticipate
disturbances, so we noticed hardware execution has more stompy touchdowns and
more impact forces to be prepared for a disturbance at anytime. These results
suggest the next iteration of our SaW reward function, which will emphasize
smaller ground contact forces. The energy profile were not recorded for Single
Contact++ due to a hardware failure during unrelated experiments close to the
submission deadline.

Figure 5: Power consumption for a commanded run of 1 m/s for 10 seconds.
Policies start in standing mode, and end in standing mode. _* Note that
results for Single Contact++ RL Controller are missing due to an experiment
damaging the robot close to submission._

##  VI Summary

The goal of this paper is to lay the foundations for continually measurable
improvement of humanoid standing and walking (SaW) controllers. For this
purpose, we introduce a set of quantitative real-world benchmarks for
evaluating humanoid standing and walking (SaW) controllers, covering
disturbance rejection, command following accuracy, and energy efficiency. We
also revisited prior reward designs from previous RL-based SaW approaches in
an attempt to arrive at a minimal set of reward terms. We demonstrate the
benchmarks’ utility by comparing our newly learned SaW controller against a
manufacturer-provided controller and a state-of-the-art learning-based
controller trained with clock-based rewards. The proposed metrics provided
clear, quantitative comparisons of the strengths and weaknesses of these
controllers. In particular, the benchmarks reveal unexpected failure modes in
the learning-based controller, which guided targeted improvements, ultimately
resulting in an enhanced controller that successfully handles all tested
disturbances. The benchmark results provide valuable insights into the current
limitations of learned controllers for humanoid SaW, including lower energy
efficiency and a significant sim-to-real gap.

These results underscore the crucial role of systematic real-world
benchmarking in advancing humanoid SaW control and other aspects of humanoid
robotic control. The proposed benchmarks and reward functions serve as only a
starting point and we believe that by continuously iterating and building upon
these benchmarks, the research community can achieve measurable and consistent
progress in real-world humanoid locomotion capabilities.

## Acknowledgment

This material is based upon work supported by the National Science Foundation
under Grant No. (2321851).

## References

  * [1] Jonah Siekmann, Yesh Godse, Alan Fern and Jonathan Hurst  “Sim-to-real learning of all common bipedal gaits via periodic reward composition”  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 7309–7315  IEEE
  * [2] Zhongyu Li et al.  “Reinforcement learning for robust parameterized locomotion control of bipedal robots”  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 2811–2817  IEEE
  * [3] Guillermo A Castillo et al.  “Template model inspired task space learning for robust bipedal locomotion”  In _2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2023, pp. 8582–8589  IEEE
  * [4] Jeremy Dao et al.  “Sim-to-real learning for bipedal locomotion under unsensed dynamic loads”  In _2022 International Conference on Robotics and Automation (ICRA)_ , 2022, pp. 10449–10455  IEEE
  * [5] Helei Duan et al.  “Learning vision-based bipedal locomotion for challenging terrain”  In _arXiv preprint arXiv:2309.14594_ , 2023
  * [6] Scott Kuindersma et al.  “Optimization-based locomotion planning, estimation, and control design for the atlas humanoid robot”  In _Autonomous robots_ 40 Springer, 2016, pp. 429–455
  * [7] Siyuan Feng, Eric Whitman, X Xinjilefu and Christopher G Atkeson  “Optimization based full body control for the atlas robot”  In _2014 IEEE-RAS International Conference on Humanoid Robots_ , 2014, pp. 120–127  IEEE
  * [8] Taylor Apgar et al.  “Fast Online Trajectory Optimization for the Bipedal Robot Cassie.”  In _Robotics: Science and Systems_ 101, 2018, pp. 14  Pittsburgh, Pennsylvania, USA
  * [9] Yukai Gong et al.  “Feedback control of a cassie bipedal robot: Walking, standing, and riding a segway”  In _2019 American Control Conference (ACC)_ , 2019, pp. 4559–4566  IEEE
  * [10] Xiaobin Xiong and Aaron Ames  “3-d underactuated bipedal walking via h-lip based gait synthesis and stepping stabilization”  In _IEEE Transactions on Robotics_ 38.4 IEEE, 2022, pp. 2405–2425
  * [11] Devin Crowley et al.  “Optimizing bipedal locomotion for the 100m dash with comparison to human running”  In _2023 IEEE International Conference on Robotics and Automation (ICRA)_ , 2023, pp. 12205–12211  IEEE
  * [12] Jeremy Dao, Helei Duan and Alan Fern  “Sim-to-Real Learning for Humanoid Box Loco-Manipulation”  In _arXiv preprint arXiv:2310.03191_ , 2023
  * [13] Guillermo A Castillo, Bowen Weng, Wei Zhang and Ayonga Hereid  “Robust feedback motion policy design using reinforcement learning on a 3d digit bipedal robot”  In _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2021, pp. 5136–5143  IEEE
  * [14] Brendan Tidd, Nicolas Hudson, Akansel Cosgun and Jürgen Leitner  “Learning Setup Policies: Reliable Transition Between Locomotion Behaviours”  In _IEEE Robotics and Automation Letters_ 7.4 IEEE, 2022, pp. 11958–11965
  * [15] Annan Tang et al.  “HumanMimic: Learning Natural Locomotion and Transitions for Humanoid Robot via Wasserstein Adversarial Imitation”  In _arXiv preprint arXiv:2309.14225_ , 2023
  * [16] Xuxin Cheng et al.  “Expressive Whole-Body Control for Humanoid Robots”  In _arXiv preprint arXiv:2402.16796_ , 2024
  * [17] Kevin Green et al.  “Learning spring mass locomotion: Guiding policies with a reduced-order model”  In _IEEE Robotics and Automation Letters_ 6.2 IEEE, 2021, pp. 3926–3932
  * [18] Ilija Radosavovic et al.  “Learning Humanoid Locomotion with Transformers”  In _arXiv preprint arXiv:2303.03381_ , 2023
  * [19] Bowen Weng, Guillermo A. Castillo, Wei Zhang and Ayonga Hereid  “On Safety Testing, Validation, and Characterization with Scenario-Sampling: A Case Study of Legged Robots”  In _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2022, pp. 5179–5186  DOI: 10.1109/IROS47612.2022.9981359
  * [20] Bowen Weng, Guillermo A. Castillo, Yun-Seok Kang and Ayonga Hereid  “Towards Standardized Disturbance Rejection Testing of Legged Robot Locomotion with Linear Impactor: A Preliminary Study, Observations, and Implications”, 2023  arXiv:2308.14636 [cs.RO]
  * [21] Sepp Hochreiter and Jürgen Schmidhuber  “Long Short-Term Memory”  In _Neural Comput._ 9.8 Cambridge, MA, USA: MIT Press, 1997, pp. 1735–1780  DOI: 10.1162/neco.1997.9.8.1735
  * [22] John Schulman et al.  “Proximal Policy Optimization Algorithms.”  In _CoRR_ abs/1707.06347, 2017  URL: http://dblp.uni-trier.de/db/journals/corr/corr1707.html#SchulmanWDRK17
  * [23] Jonah Siekmann, Yesh Godse, Alan Fern and Jonathan Hurst  “Sim-to-Real Learning of All Common Bipedal Gaits via Periodic Reward Composition”  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ Xi’an, China: IEEE Press, 2021, pp. 7309–7315  DOI: 10.1109/ICRA48506.2021.9561814


# Blockchain-based PKI within a Corporate Organization: Advantages and
Challenges

Julian Springer
Department Computer Science and Security
St. Pölten University of Applied Sciences
St. Pölten, Austria
<EMAIL_ADDRESS>
Philipp Haindl
Department Computer Science and Security
St. Pölten University of Applied Sciences
St. Pölten, Austria
<EMAIL_ADDRESS>

###### Abstract

This research investigates the potential use of a blockchain-based Public Key
Infrastructure (PKI) within an organization and compares it to conventional
PKI systems. The goal is to assess the advantages and disadvantages of both
approaches in order to determine the feasibility of employing blockchain
technology for a decentralized PKI. The study will also evaluate the impact of
current legal frameworks, such as the Cyber Resilience Act (CRA) and NIS-2
Directive. The study will examine various implementations of blockchain PKIs
based on factors such as security, performance, and platform. The results
indicate that blockchain-based PKIs can overcome the limitations of
conventional PKIs by decentralizing the trust anchor, providing greater
security. Blockchain technology allows for the immutable and transparent
management of certificates, making tampering significantly more challenging.
Additionally, blockchain-based PKIs offer enhanced mechanisms for identifying
and addressing certificate misconduct.

##  1 Objective

It is assessed whether a public key infrastructure (PKI) based on blockchain
technology offers an advantage within an association organization.
Additionally, the challenges that arise are explained, and if feasible, how
they can be addressed. This paper also includes the following contributions:

  * •

A fundamental examination of cryptography

  * •

An introduction to the functionalities of both classic and blockchain-based
PKIs

  * •

The development of basic knowledge about how blockchains operate

  * •

A list of current implementations of blockchain-based PKIs, along with their
advantages and disadvantages in meeting the requirements

  * •

A consideration of the impact of legal framework conditions

##  2 Research Questions

The following research questions are answered in this paper:

  1. 1.

What notable implementations are currently available and how effectively do
they address the challenges posed by a traditional PKI?

  2. 2.

Is it practical to employ a decentralized PKI within a group organization?

    1. (a)

Which distributed ledger technology would be appropriate for a decentralized
Public Key Infrastructure (PKI)?

    2. (b)

How can one evaluate the suitability of employing a PKI?

  3. 3.

In what manner does the Cyber Resilience Act impact the execution of a
blockchain-based Public Key Infrastructure (PKI)?

##  3 Cryptography Fundamentals

Cryptography is employed to ensure the confidentiality, integrity,
authenticity, and non-repudiation of information. These four aspects guarantee
that a third party cannot view the content of a message, the recipient can
confirm that the message has not been altered during transmission, and the
sender’s identity can be verified. Non-repudiation, however, is not always
guaranteed since there are protocols that do not offer this feature [1].

###  3.1 Symmetric Cryptography

In current communication systems, only a single key is utilized by both
parties involved in the exchange. However, transmitting this key securely
poses a challenge. As the number of participants increases, the need for
additional keys grows proportionately. The quantity of keys required can be
determined by the formula $\frac{n*(n-1)}{2}$. One of the primary benefits of
symmetric cryptography is its ability to secure substantial amounts of data
with relatively short key lengths. Nevertheless, this approach cannot be
applied to digital signatures because the key must be kept confidential at all
times. In contemporary times, symmetric encryption is widely employed using
the AES algorithm.

###  3.2 Asymmetric Cryptography

The primary distinction between symmetric cryptography and asymmetric
cryptography lies in the utilization of a single shared key, which both
participants must maintain in strict secrecy, and the employment of two keys
per participant. These key pairs, also referred to as such, comprise of a
private key and a public key, with the private key being consistently guarded
in secrecy, while the public key is commonly acknowledged and frequently
conveyed in the form of a certificate. Unlike symmetric cryptography, there is
no straightforward relationship between the encryption key, which is the
public key, and the decryption key, which is the private key. This means that
it is only possible to deduce the private key from the public key with
significant effort. This phenomenon is rooted in mathematical functions that
are easily computable but are practically impractical to compute without the
knowledge of the private key. Examples of such mathematical functions, among
others, include:

  * •

Prime factorization

  * •

Discrete logarithm

  * •

Chinese remainder theorem

  * •

Elliptical curves

Asymmetric cryptography presents several advantages, including the simplicity
of distributing keys since the public key can generally be known and
transmitted via insecure channels. Additionally, only one key pair is required
per participant, reducing the number of such pairs. Asymmetric procedures also
enable digital signatures using the private key instead of the public key,
which is utilized in encryption. However, asymmetric cryptography has some
drawbacks, such as less efficiency in the encryption process and the need for
longer keys. Furthermore, it lacks security against quantum computers, unlike
symmetric procedures. The most commonly used algorithms for asymmetric
cryptography are RSA and elliptic curves.

###  3.3 Hybrid Cryptography

The customary approach incorporates both of the aforementioned techniques.
Symmetrically, the message is encrypted. For the key exchange, the recipient
discloses their public key, and the contents are encrypted asymmetrically. The
recipient must first decrypt the symmetric key, which has been utilized to
encrypt the content of the transmitted message, in order to access the content
[2].

###  3.4 Digital signature

The need for authenticity and integrity necessitates the implementation of
specific measures. Such measures comprise:

  * •

Technical security measures, such as digital signatures, which guarantee the
authenticity of participants and the integrity of data by encrypting the hash
value of the message with the sender’s private key and attaching it to the
message, which is then decrypted by the recipient using the sender’s public
key to ensure the authenticity and integrity of the data.

  * •

Certification authorities, which provide an infrastructure for secure key
management.

  * •

Legal regulations, which ensure legal bindingness within an organization,
although this is limited to the public sector and legally binding channels.

A digital signature functions as a substitute for a traditional signature, and
there are functional, technical, and legal requirements that must be met in
order to effectively implement digital signatures.

####  3.4.1 Functional requirements

Verifiability, forgery protection, and binding nature are essential aspects of
a signature. These three elements are crucial to ensure that a signature is
genuine and legally binding. Verifiability refers to the ability to verify the
authenticity of the signature, while forgery protection ensures that only the
owner of the signature can generate it. The binding nature of a signature
means that the signatory cannot deny authorship once it has been signed.
Therefore, it is critical to ensure that these elements are present in a
signature to ensure its validity and legality.

####  3.4.2 Technical requirements

The following points must be taken into consideration when evaluating the
effectiveness of a digital signature solution:

  * •

Performance: The verification process should not cause undue delay when
loading the document.

  * •

Security: The system must ensure cryptographic security to protect against
unauthorized access or tampering.

  * •

User Experience: The process of creating and verifying a signature should be
designed to minimize inconvenience and facilitate ease of use.

####  3.4.3 Legal Requirements

The legal effect should be equivalent to that of a traditional signature. It
is crucial to ensure that the certification of the signatories is legally
binding. Furthermore, the law must specify the requirements for the technical
implementation and monitor compliance with them.

##  4 Introduction to Public Key Infrastructure

###  4.1 Definition and Significance

Public key infrastructure (PKI) comprises the various roles, policies,
hardware, software, and procedures that are necessary to create, manage,
distribute, and revoke digital certificates and manage public key encryption
[3]. The primary objective of PKI is to enable the secure electronic
transmission of information. PKI allows users and computers to verify the
legitimacy of the parties involved in electronic transactions, thus ensuring
the confidentiality and integrity of the data exchanged. This is accomplished
by issuing a digital certificate that can be used to identify a person or
organization. In addition, directory services are utilized to store these
certificates and to revoke them if necessary [4, 5]. As previously mentioned,
key exchange remains a problem in larger environments. If the participants are
aware of each other’s public key, they can communicate via any public key-
based protocol. Even if the public key does not need to be kept secret,
indiscriminate distribution of it is not helpful, as it cannot be verified
that a public key belongs to the entity it claims to be. For instance, a
website could be hosted where public keys can be uploaded, and anyone can
access it to obtain the necessary key. This would allow Bob to look up Alice’s
public key. However, Bob cannot be sure that it is actually Alice’s key and
not someone else’s who wants to impersonate Alice. PKI enables the secure and
convenient determination of public keys, which is essential for secure
communication. It provides a mechanism for verifying the identities of the
parties involved in electronic communication, facilitating trust within and
between organizations and across the Internet [5, 3].

###  4.2 Digital certificates

Digital certificates are formal documents that consist of a set of elements,
as specified in the table, and are widely used to establish secure
communication over the internet. These certificates provide assurance to the
user that the public key contained within belongs to the specified subject,
such as an individual, organization, or server [3]. The format and contents of
digital certificates are determined by established standards. Table 1 lists
the contents of a X.509 certificate.

Dataelement | X.509 Version | Explanation
---|---|---
Version | 1 | An integer indicating the version of the certificate.
Serial number | 1 |  | An integer representing the unique number for each certificate issued by a certification authority.
---
Signature | 1 |  | The identifier for the cryptographic algorithm used by the certification authority to sign the certificate.
---
The value contains the identifier of the algorithm and all optional parameters
that may be used by this algorithm.
Issuer | 1 | The Distinguished Name (DN) of the certification authority that issued the certificate.
Validity period | 1 | The period (inclusive) during which the certificate is valid.
Subject | 1 | The Distinguished Name (DN) of the certificate applicant.
| Information on the
---
applicant’s public key
1 | The public key held by the certificate applicant.
Unique ID of the issuer | 2 |  | A unique identifier representing the issuing certification body, as defined by the issuing certification body.
---
Unique ID of the certificate applicant | 2 |  | A unique identifier that stands for the certificate applicant as defined by the issuing certification authority.
---
Extentions | 3 | A collection of standard and Internet-specific certificate extensions.

Table 1: Data elements of a digital certificate according to the X.509
standard [6].

##  5 Blockchain and Distributed Ledger

###  5.1 Distributed Ledger

The primary objective of distributed ledger technologies (DLT) is to
facilitate interactions between two parties without the need for a mutually
trusted third party [7]. DLTs such as blockchain offer a secure method for
conducting and recording data transfers without a central administrative body.
Distribution occurs through the shared use of copies of the ledger and their
synchronization via a peer-to-peer network. New entries are added permanently
in a cryptographically secure manner and made accessible to all participants
[8]. It is essential to recognize that a distributed ledger does not
necessarily have to be implemented using a blockchain. A blockchain is simply
one way of implementing a distributed ledger [9]. Despite differences between
various DLTs, such as the data model or technology, they all rely on three
well-known technologies:

  * •

Public key cryptography serves the purpose of providing secure identities for
each participant, thereby enabling the ability to function in an insecure
environment.

  * •

A peer-to-peer distributed network serves the purpose of achieving
scalability, avoiding single points of failure, and enabling decentralized
control of the network by individuals.

  * •

The consensus procedure is a means of achieving agreement among all
participants on a common truth, without the need for a central authority that
is universally trusted [7].

###  5.2 Blockchain

As already pointed out, blockchain is a distributed ledger technology that
involves the chronological chaining of blocks. When a participant wishes to
conduct a transaction, they transmit all relevant information to all other
network participants. A miner, a specialized node, then generates a block and
attempts to calculate a valid hash value. Once a valid hash is found, all
participants are informed and the validated block is added to the chain. This
process is referred to as "mining" and is attractive to the financial sector,
asset records, and identity management due to the immutability of validated
data in the blockchain. A comparison of various distributed ledger
technologies reveals that while all of these DLTs are theoretically possible,
blockchain is the most suitable option due to its widespread use and resulting
higher level of maturity, as well as its strong security features. The
consensus mechanism’s basic functioning is also well-suited to meet the
requirements of a Public Key Infrastructure (PKI) [1].

##  6 Decentralized PKI in a Group Organization

Several organizations are involved in a current PKI and have set themselves
the goal of establishing a common trust anchor. The most important use case is
private TLS certificates for interfaces between the individual organizations
and their partners. With the help of common rules and standards, which are
defined in the CP/CPS documents of the CAs, an improved quality of security
and thus its increase should be achieved for the participating organizations.
At the highest level, there is the root CA, which only issues certificates for
sub-CAs. It is operated by an organization A, as agreed among themselves. Each
of the participating organizations can operate one or more such sub-CAs. These
are subject to the requirements of the policies of the Root CA and can tighten
these as much as possible. Other participants (organizations) can use the
services of the Root CA directly at any time by setting up a sub-CA. Partners
can use the infrastructure indirectly by using certificates from the sub-CAs.
It should also be noted that the participants can operate their own PKIs in
parallel and independently. For reasons of controllability and separation of
the technical areas, a separate root CA is created for each certificate type.

###  6.1 Criteria for evaluation of blockchain-based PKIs

The following factors can be utilized to assess the execution of a blockchain-
based public key infrastructure (PKI):

  1. 1.

Key feature: Each implementation possesses its own specialized focus, i.e. it
targets a weakness of conventional PKI and proposes a solution.

  2. 2.

Blockchain type: The type of blockchain used, such as permissioned or
permissionless.

  3. 3.

Blockchain platform: e.g. Ethereum, Bitcoin, or a custom implementation.

  4. 4.

Certificate: The format of the certificate, such as the X.509 standard or a
custom format.

  5. 5.

Trust Model: The mechanism that selects the node responsible for validating a
certificate, such as hierarchical or Web of Trust (WoT).

  6. 6.

Consensus mechanism: The type of consensus mechanism employed, such as proof-
of-work or proof-stake.

  7. 7.

Storage: The method of storing blockchain data, which can be in the form of
the entire data or the hash function of the block. There are two categories of
blockchain data storage: on-chain storage, where the data is stored directly
on the blockchain network, and off-chain storage, where the data is stored in
a public ledger that can be accessed by all other nodes or in a private
storage that can be accessed by the respective node.

  8. 8.

Time complexity: The algorithmic computational complexity in the form of time
[10].

##  7 Influence of CRA and NIS-2

The applicability of the CRA to the blockchain PKI hinges on the mode of
delivery. If the PKI is provided as a service and customers are not required
to install or host any software on their own, it is exempt from the CRA since
SaaS solutions are covered under the NIS2 directive. Conversely, if the PKI
software is sold as a product to be installed and operated by the purchaser,
the CRA would apply [11].

##  8 Conclusion

The study has revealed that blockchain-based Public Key Infrastructures (PKIs)
possess the ability to tackle the fundamental flaws present in traditional
PKIs. In particular, these include the reliance on central trust anchors,
which can serve as a single point of failure in conventional PKIs. With the
implementation of blockchain technology, the trustworthiness and authenticity
of the certificates can be upheld in a decentralized manner, ensuring their
immutability and enabling easy monitoring. This ultimately results in enhanced
security, providing resistance against manipulation and potential failures.

###  8.1 Summary and Outlook

The research indicates that blockchain-based public key infrastructures (PKIs)
present a promising alternative to traditional PKIs. They offer enhanced
security, transparency, and resilience, which make them appealing for use in
corporate organizations. However, implementing such a solution necessitates
careful planning and evaluation to meet specific requirements and legal
framework conditions. In the future, additional research and practical
applications will be required to further optimize and improve the technology.
Specifically, the feasibility of incorporating blockchain-based PKIs into
existing IT infrastructures and the development of standards and best
practices will be crucial to achieving widespread acceptance. Overall, this
study makes a significant contribution to the discussion on the future of PKI
and the role of blockchain technology in cybersecurity, beyond the financial
and cryptocurrency sectors. It demonstrates that innovative approaches and
technologies can effectively address the challenges of modern IT security. In
conclusion, a blockchain-based PKI offers substantial advantages in terms of
security and reliability, but selecting the appropriate distributed ledger
technology and complying with legal requirements are crucial for the
successful implementation of such a solution. These findings provide a solid
foundation for further research and practical applications to fully leverage
the benefits of blockchain technology in the field of PKI and enhance
cybersecurity in corporate settings.

## References

  * [1] Daniel Hellwig, Goran Karlic and Arnd Huchzermeier  “Entwickeln Sie Ihre eigene Blockchain: Ein praktischer Leitfaden zur Distributed-Ledger-Technologie”  Berlin, Heidelberg: Springer Berlin Heidelberg, 2021  DOI: 10.1007/978-3-662-62966-6
  * [2] Brian Komar  “Windows Server® 2008 PKI and Certificate Security”  Microsoft Press, 2008
  * [3] Vishwas T. Patil and R.K. Shyamasundar  “Evolving Role of PKI in Facilitating Trust”  In _2022 IEEE International Conference on Public Key Infrastructure and its Applications (PKIA)_ , 2022, pp. 1–7  DOI: 10.1109/PKIA56009.2022.9952249
  * [4] Russ Housley  “Public Key Infrastructure (PKI)”  In _The Internet Encyclopedia_ John Wiley & Sons, Ltd, 2004  URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/047148296X.tie149
  * [5] R. Perlman  “An overview of PKI trust models” Conference Name: IEEE Network  In _IEEE Network_ 13.6, 1999, pp. 38–43  DOI: 10.1109/65.806987
  * [6] kgremban  “X.509-Zertifikate”, 2023  URL: https://learn.microsoft.com/de-de/azure/iot-hub/reference-x509-certificates
  * [7] Nabil El Ioini and Claus Pahl  “A Review of Distributed Ledger Technologies”  In _On the Move to Meaningful Internet Systems. OTM 2018 Conferences_ Cham: Springer International Publishing, 2018, pp. 277–288  DOI: 10.1007/978-3-030-02671-4_16
  * [8] Timothy M. Persons  “BLOCKCHAIN & DISTRIBUTED LEDGER TECHNOLOGIES”, 2019  URL: https://www.gao.gov/assets/gao-19-704sp.pdf
  * [9] Emily Rutland  “Blockchain Byte”  R3 Research  URL: https://www.finra.org/sites/default/files/2017_BC_Byte.pdf
  * [10] Amrutanshu Panigrahi, Ajit Kumar Nayak and Rourab Paul  “Smart Contract Assisted Blockchain based PKI System”  arXiv, 2022  arXiv: http://arxiv.org/abs/2207.09127
  * [11] “Cyber Resilience Act - Questions and Answers”, 2023  URL: https://ec.europa.eu/commission/presscorner/api/files/document/print/en/qanda_22_5375/QANDA_22_5375_EN.pdf


# The Principle of Optimality in Dynamic Programming: A Pedagogical Note

Bar Light Microsoft Research, NYC, USA. e-mail<EMAIL_ADDRESS>
Abstract:

> The principle of optimality is a fundamental aspect of dynamic programming,
> which states that the optimal solution to a dynamic optimization problem can
> be found by combining the optimal solutions to its sub-problems. While this
> principle is generally applicable, it is often only taught for problems with
> finite or countable state spaces in order to sidestep measure-theoretic
> complexities. Therefore, it cannot be applied to classic models such as
> inventory management and dynamic pricing models that have continuous state
> spaces, and students may not be aware of the possible challenges involved in
> studying dynamic programming models with general state spaces. To address
> this, we provide conditions and a self-contained simple proof that establish
> when the principle of optimality for discounted dynamic programming is
> valid. These conditions shed light on the difficulties that may arise in the
> general state space case. We provide examples from the literature that
> include the relatively involved case of universally measurable dynamic
> programming and the simple case of finite dynamic programming where our main
> result can be applied to show that the principle of optimality holds.

##  1 Introduction

Dynamic programming is a powerful tool used in many areas, including
operations research, engineering, artificial intelligence, mathematical
finance, and economics. One of the major concepts in dynamic programming is
the principle of optimality (sometimes called Bellman’s principle of
optimality), which is a method for solving a dynamic optimization problem by
breaking it down into smaller sub-problems. While the principle of optimality
holds under general conditions, proving it in the general case is quite
involved and requires a non-trivial background in measure theory (Bertsekas
and Shreve, 1996). In addition, some important functions that are studied in
dynamic programming are not well behaved with respect to measurability. For
example, it is well known, that even under the natural assumption that the
dynamic optimization problem’s primitives are Borel measurable, the optimal
solution of the problem (i.e., the value function) need not to be Borel
measurable (Blackwell, 1965).

To overcome the measurability difficulty, major textbooks that are used to
teach the principle of optimality in dynamic programming, even for advanced
graduate level courses, typically avoid measure-theoretic issues by assuming
that the state space is finite or countable (e.g., Bertsekas (2012) and
Puterman (2014)). This approach has two major drawbacks. First, in some of the
canonical dynamic optimization models in operations research and economics
like inventory management, consumption-savings problems, or dynamic pricing
models, the state space is continuous. Hence, the theory that is developed for
countable state spaces does not apply to these canonical models. Second,
students who are introduced to the important field of dynamic programming may
not fully comprehend or acknowledge the challenges involved in studying
dynamic programming models with continuous or other more general state spaces
such as Borel spaces.

In this note, we provide a self-contained proof for the principle of
optimality and the existence of an optimal stationary policy for discounted
dynamic programming that requires minimal knowledge of measure theory. The key
assumptions that guarantee the correctness of the principle of optimality and
the existence of an approximate optimal stationary policy are that the Bellman
operator preserves some form of measurability and that there is a measurable
selection that attains the supremum of the Bellman equation. These assumptions
are simple to state and provide insight into the potential measurability
challenges in dynamic programming with general state spaces (such as the issue
of measurable selection). Our results are applicable to important cases that
have been studied in the literature. We provide 7 examples from the literature
where our main result can be applied to prove the principle of optimality and
the existence of an optimal policy, including the general universally
measurable case (Bertsekas and Shreve, 1996), the upper semi continuous case
(Maitra, 1968), the continuous case (Stokey and Lucas, 1989), and the standard
countable case (Bertsekas, 2012). We demonstrate a potential failure of our
assumptions using an example from Blackwell (1965) that involves Borel
measurable primitives. The rest of the note is organized as follows. In
Section 2 we present the discounted dynamic programming model. In Section 2.1
we present the main theorem and its proof. In Section 2.2, we present the
applications of the main Theorem. In the Appendix, we review the results from
metric spaces needed to prove the main theorem.

##  2 Discounted Dynamic Programming

For the sake of brevity, we will focus on discounted dynamic programs in this
note.

We define a discounted dynamic programming model111All the measurability
assumptions we make in this section can be initially ignored by assuming that
the relevant functions are well-defined (see alternative assumptions on the
primitives of the dynamic programming model in Section 2.2). in terms of a
tuple of elements $(S,A,\Gamma,p,U,r,\beta)$. $(S,\mathcal{B}(S))$ is a
measurable space where $S$ is a polish space that describes the possible
states of the system and $\mathcal{B}(X)$ denotes the Borel sigma-algebra for
a Borel set $X$. $(A,\mathcal{B}(A))$ is a measurable space where $A$ is a
polish space that describes the action space. $p:S\times
A\times\mathcal{B}(S)\rightarrow[0,1]$ is a transition probability function,
i.e., $p(s,a,\cdot)$ is a probability measure on $S$ for each $(s,a)\in
S\times A$ and $p(\cdot,\cdot,B)$ is a Borel measurable function for each
$B\in\mathcal{B}(S)$. $U:=U(X,Y)$ is a set of functions from a Borel set $X$
to a Borel set $Y$ such that if $f\in U(X,Y)$ then $f:X\rightarrow Y$ is a
function that satisfies some measurability conditions we discuss later.
$r:S\times A\rightarrow\mathbb{R}$ is the single-period bounded from below
Borel measurable payoff function. $0<\beta<1$ is the discount factor. $\Gamma$
is a subset of $S\times A$ such that for any $s\in S$ the non-empty
$s$-section $\Gamma(s)$ of $\Gamma$ is the Borel set of feasible actions in
state $s\in S$.

The process starts at some state $s(1)\in S$. Suppose that at time $t$ the
state is $s(t)$. Based on $s(t)$, the decision maker (DM) chooses an action
$a(t)\in\Gamma(s)$ and receives a payoff $r(s(t),a(t))$. The probability that
the next period’s state $s(t+1)$ will lie in $B\in\mathcal{B}(S)$ is given by
$p(s(t),a(t),B)$.

Let $H^{t}:=S\times(A\times S)^{t-1}$ be the set of finite histories up to
time $t$. A strategy $\sigma$ is a sequence $(\sigma_{1},\sigma_{2},\ldots)$
of functions $\sigma_{t}\in U(H^{t},A)$ such that
$\sigma_{t}(s(1),a(1),\ldots,s(t))\in\Gamma(s(t))$ for all $t$ and all
$(s(1),a(1),\ldots,s(t))\in H^{t}$. We assume that the set $U$ is such that
for each initial state $s(1)\in S$, a strategy $\sigma$ and a transition
probability function $p$ induce a well-defined probability measure over the
measurable space of all infinite histories
$(H^{\infty},\mathcal{B}(H^{\infty}))$.222Thus, $U$ can be the set of Borel
measurable functions, universally measurable functions, etc (see Bertsekas and
Shreve (1996)). We provide specific examples in Section 2.2. We denote the
expectation with respect to that probability measure by $\mathbb{E}_{\sigma}$,
and the associated stochastic process by $\\{s(t),a(t)\\}_{t=1}^{\infty}$. The
decision maker’s goal is to find a strategy that maximizes her expected
discounted payoff. When the decision maker follows a strategy $\sigma$ and the
initial state is $s\in S$, the expected discounted payoff is given by

$V_{\sigma}(s)=\mathbb{E}_{\sigma}\sum\limits_{t=1}^{\infty}\beta^{t-1}r(s(t),a(t)).$
(1)

Define

$V(s)=\sup_{\sigma}V_{\sigma}(s).$

We call $V:S\rightarrow\mathbb{R}$ the value function. A strategy $\sigma$ is
said to be optimal if $V_{\sigma}(s)=V(s)$ for all $s$. A strategy $\sigma$ is
said to be $\epsilon$-optimal if for every $\epsilon>0$, every strategy
$\sigma^{\prime}$, and any $s\in S$ we have $V_{\sigma^{\prime}}(s)\leq
V_{\sigma}(s)+\epsilon$. A strategy is said to be stationary if
$\sigma(h(t))=\lambda(s(t))$ where $h(t)=(s(1),a(1),\ldots,s(t))$ for any
history $h(t)\in H^{t}$ and some function $\lambda\in U(S,A)$ which is called
a stationary policy.

For a function $f\in U(S,\mathbb{R})$ we define the operator (called the
Bellman operator or the Bellman equation) $T$ by

$Tf(s)=\sup_{a\in\Gamma(s)}Q(s,a,f),$

where

$Q(s,a,f)=r(s,a)+\beta\int_{S}f(s^{\prime})p(s,a,ds^{\prime})$ (2)

and the set of optimal solutions for the Bellman equation $\Lambda_{f}$ by

$\Lambda_{f}=\\{\lambda\in U(S,A):\sup_{a\in\Gamma(s)}\
Q(s,a,f)=Q(s,\lambda(s),f),\ \forall s\in S\\}.$

For a stationary policy $\lambda\in U(S,A)$ and $f\in U(S,\mathbb{R})$ we also
define $T_{\lambda}$ by

$T_{\lambda}f(s)=r(s,\lambda(s))+\beta\int_{S}f(s^{\prime})p(s,\lambda(s),ds^{\prime})=Q(s,\lambda(s),f).$
(3)

###  2.1 The Dynamic Programming Principle

Let $B(S)$ be the space of all real-valued bounded functions on $S$ equipped
with the sup-norm $\|f\|=\sup_{s\in S}|f(s)|$ and the induced metric
$d_{\infty}(f,g):=\sup_{s\in S}|f(s)-g(s)|$ for $f,g\in B(S)$. Let
$B_{m}(S)=B(S)\cap U(S,\mathbb{R})$. We assume that $U(S,\mathbb{R})$ is
closed in $B(S)$ so $B_{m}(S)$ is a complete metric space. We now present the
main theorem of this note that shows that the value function satisfies the
Bellman equation under certain conditions. We show that if $T_{\lambda}f\in
U(S,\mathbb{R})$ whenever $f\in U(S,\mathbb{R})$, $\lambda\in U(S,A)$ and
there exists a closed set $D$ of $B_{m}(S)$ such that $T(D)\subseteq D$ and
for each $f\in D$ we have $\Lambda_{f}\neq\emptyset$, then the value function
is in $D$, satisfies the Bellman equation, and there exists an
$\epsilon$-optimal stationary policy.333One could also prove a version of
Theorem 1 for the case of unbounded but positive rewards (discounted or
undiscounted) by using a monotone convergence theorem argument instead of
Banach’s fixed-point theorem (see Bertsekas and Shreve (1996), Feinberg et al.
(2012) and Feinberg et al. (2016).

The assumptions that $f\in D$ implies that $Tf\in D$ and $T_{\lambda}f\in
U(S,\mathbb{R})$ whenever $f\in U(S,\mathbb{R})$ and $\lambda\in U(S,A)$
guarantee that the Bellman equation preserves some form of measurbility as $D$
consists of appropriately chosen measurable functions. The assumption that
$f\in D$ implies that $\Lambda_{f}\neq\emptyset$ guarantees a measurable
solution (or a measurable selection) for the Bellman equation. In the finite
and countable cases these assumptions trivially holds (see Section 2.2). In
the general case, these assumptions can be quite involved to establish.
Finding conditions on the model’s primitives that guarantee that these
assumptions hold are crucial in the study of dynamic programming. We discuss
some important cases from the literature in Section 2.2.

###### Theorem 1

Let $D\subseteq B_{m}(S)$ be a complete metric space with the metric
$d_{\infty}$ that contains the constant $0$ function and any constant function
$M$ such that $M=\sup_{s\in S}f(s)$ for $f\in D$.

Assume that $f\in D$ implies $\Lambda_{f}\neq\emptyset$, and $Tf\in D$ and
that $f\in U(S,\mathbb{R})$ implies $T_{\lambda}f\in U(S,\mathbb{R})$ for each
$\lambda\in U(S,A)$.

Then the following holds:

1\. $V$ is the unique function in $D$ that satisfies the Bellman equation,
i.e., $TV=V$.

2\. $\lambda\in\Lambda_{V}$ is an $\epsilon$-optimal stationary policy.

3\. If $\lambda\in\Lambda_{V}$ achieves the supremum then $\lambda$ is an
optimal stationary policy.

We first prove a few simple properties of the operators $T$ and $T_{\lambda}$.

###### Lemma 1

The operator $T$ satisfies the following two properties.444For two functions
$f,g$ from $S$ to $\mathbb{R}$, $f\geq g$ means $f(s)\geq g(s)$ for each $s\in
S$.

(a) Monotone: $Tf\geq Tg$ whenever $f\geq g$.

(b) Discounting: $T(f+c)=Tf+\beta c$ for any constant function $c$.

In addition, $T_{\lambda}$ satisfies $(a)$ and $(b)$ for any stationary policy
$\lambda\in U(S,A)$.

Proof. (a) We have $Q(s,a,f)\geq Q(s,a,g)$ whenever $f\geq g$. Hence, $Tf\geq
Tg$.

(b) For each $s\in S$ we have

$T(f+c)(s)=\sup_{a\in\Gamma(s)}r(s,a)+\beta\int_{S}f(s^{\prime})p(s,a,ds^{\prime})+\beta
c=Tf(s)+\beta c.$

The proof for the operator $T_{\lambda}$ is similar.

A key property of the operators $T$ and $T_{\lambda}$ is the contraction
property. The operator $T$ on $B_{m}(S)$ is $L$-contraction if $\|Tf-Tg\|\leq
L\|f-g\|$ for all $f,g\in B_{m}(S)$.

###### Lemma 2

The operator $T$ is $\beta$-contraction on $D$, and the operator $T_{\lambda}$
is $\beta$-contraction on $B_{m}(S)$ for any stationary policy $\lambda\in
U(S,A)$.

Proof. Let $f,g\in B_{m}(S)=U(S,\mathbb{R})\cap B(S)$ and $\lambda\in U(S,A)$.
From the theorem’s assumption, $T_{\lambda}f\in U(S,\mathbb{R})$ and from the
argument in the start of the proof of Theorem 1, $T_{\lambda}f\in B(S)$ so
$T_{\lambda}f$ is indeed in $B_{m}(S)$.

For any $s\in S$ we have

$|T_{\lambda}f(s)-T_{\lambda}g(s)|=|\beta\int_{S}(f(s^{\prime})-g(s^{\prime}))p(s,\lambda(s),ds^{\prime})|\leq\beta\int_{S}|f(s^{\prime})-g(s^{\prime})|p(s,\lambda(s),ds^{\prime})\leq\beta\|f-g\|.$

Taking the supremum over $s\in S$ yields
$\|T_{\lambda}f-T_{\lambda}g\|\leq\beta\|f-g\|$ so $T_{\lambda}$ is
$\beta$-contraction on $B_{m}(s)$.

Hence, it follows that for all $s\in S$, $f,g\in D$ and $a\in\Gamma(s)$ we
have

$Q(s,a,f)\leq Q(s,a,g)+\beta\|f-g\|\leq Tg(s)+\beta\|f-g\|.$

Taking the supremum over $a\in\Gamma(s)$ yields

$Tf(s)\leq Tg(s)+\beta\|f-g\|.$

By a symmetrical argument, we can deduce $Tg(s)\leq Tf(s)+\beta\|f-g\|$ for
all $s\in S$ so $T$ is $\beta$-contraction on $D$.

Proof of Theorem 1. From the Banach fixed-point theorem (see Proposition 1 in
the Appendix) the operator $T:D\rightarrow D$ has a unique fixed-point $x$. We
will show that $V=x$. We first show that $V\leq x$.

Let $k(s)=\sup_{a\in\Gamma(s)}r(s,a)$. Then $k(s)$ is finite. This follows
because $Tf\in B_{m}(S)$ whenever $f$ is in $D$, so taking $f$ to be the $0$
constant function that belongs to $D$ by assumption implies that
$M^{\prime}\geq Tf(s)\geq r(s,a)$ for all $(s,a)$ for some finite
$M^{\prime}$. In addition, $Tf(s)=\sup_{a\in\Gamma(s)}r(s,a)=k(s)$ is in $D$.
Thus, $M=\sup_{s\in S}k(s)$ belongs to $D$ also. Using the same argument again
for the constant function $f_{2}(s)=M$ for all $s\in S$ we have
$Tf_{2}(s)=k(s)+\beta M$ is in $D$ so $M+\beta M$ is in $D$. Continuing
inductively, we conclude that the constant function $M_{T}$ given by
$M_{T}=\sum_{t=1}^{T}\beta^{t-1}M$ is in $D$. Because $D$ is closed as a
closed subset of a complete metric space, the constant function
$y(s)=\lim_{T\rightarrow\infty}M_{T}=M/(1-\beta)$ for all $s\in S$ belongs to
$D$. Because $r$ is bounded by $M$ we have $V\leq y$. Hence, there exists a
$y\in D$ such that $V\leq y$.

For a strategy $\sigma$ let $\sigma|(s,a)$ be the strategy that is induced by
$\sigma$ given that the first period’s state-action pair was $(s,a)$, i.e.,
$\sigma|(s,a)_{t}(h_{t})=\sigma_{t+1}(s,a,h_{t})$ for all $t$ and any history
$h_{t}\in H^{t}$. For any strategy $\sigma$, a function $y\in D$ with $V\leq
y$, and $s\in S$ we have

$\displaystyle V_{\sigma}(s)$
$\displaystyle=\mathbb{E}_{\sigma}\left(r(s,a(1))+\sum\limits_{t=2}^{\infty}\beta^{t-1}r(s(t),a(t))\right)$
$\displaystyle=r(s,\sigma_{1}(s))+\beta\int_{S}V_{\sigma|(s,\sigma_{1}(s))}(s^{\prime})p(s,\sigma_{1}(s),ds^{\prime})$
$\displaystyle\leq
r(s,\sigma_{1}(s))+\beta\int_{S}V(s^{\prime})p(s,\sigma_{1}(s),ds^{\prime})$
$\displaystyle\leq
r(s,\sigma_{1}(s))+\beta\int_{S}y(s^{\prime})p(s,\sigma_{1}(s),ds^{\prime})$
$\displaystyle\leq\sup_{a\in\Gamma(s)}\
r(s,a)+\beta\int_{S}y(s^{\prime})p(s,a,ds^{\prime})$ $\displaystyle=Ty(s).$

Thus, taking the supremum over all strategies $\sigma$ implies that $V\leq
Ty$. Repeating the same argument we deduce that $V\leq T^{n}y$ for all $n\geq
1$. From the Banach fixed-point theorem $T^{n}y$ converges to the unique
fixed-point of $T$ on $D$. We conclude that $V\leq x$.

We now show that $V\geq x$. Let $\epsilon>0$. Because $x\in D$, the Theorem’s
assumption implies that $\Lambda_{x}\neq\emptyset$. Hence, because $Tx=x$,
there is a function $\lambda\in U(S,A)$ such that $T_{\lambda}x\geq
x-\epsilon(1-\beta)$.

We will now show that $T_{\lambda}^{n}x\geq x-\epsilon$ for all $n$. For $n=1$
the result holds from the construction of $\lambda$. Assume it holds for
$n>1$. Then

$T_{\lambda}^{n+1}x=T_{\lambda}(T_{\lambda}^{n}x)\geq
T_{\lambda}(x-\epsilon)=T_{\lambda}x-\beta\epsilon\geq x-\epsilon$

where we used Lemma 1 to derive the inequalities. Thus, $T_{\lambda}^{n}x\geq
x-\epsilon$ for all $n$. From Lemma 2 and the Banach fixed-point theorem
$T_{\lambda}^{n}$ converges to the unique fixed-point of $T_{\lambda}$ in
$B_{m}(S)$ which we denote by $W$ so $W\geq x-\epsilon$. Note that

$W(s)=r(s,\lambda(s))+\beta\int_{S}W(s^{\prime})p(s,\lambda(s),ds^{\prime})=\mathbb{E}_{\sigma}\sum\limits_{t=1}^{\infty}\beta^{t-1}r(s(t),a(t))$

with $s=s(1)$ and $\sigma$ is the stationary plan that plays according to
$\lambda$, i.e., $\sigma_{t}(h_{n})=\lambda(s(n))$ for all
$h_{n}(s(1),a(1),\ldots,s(n))$, and hence, $V\geq W\geq x-\epsilon$. Thus,
$V\geq x$. We conclude that $V=x$ so $V$ is the unique fixed point of $T$ and
$\lambda\in\Lambda_{V}$ is an $\epsilon$-optimal strategy.

In addition, if $\lambda\in\Lambda_{V}$ achieves the supremum then
$T_{\lambda}V=V$ so $\lambda$ is the optimal stationary policy.

###  2.2 Applications of Theorem 1

As a starting point it is natural to assume that the dynamic programming
problem’s primitives are Borel measurable and choose $D$ to be the set of
Borel bounded measurable functions. But there is a well-known measurability
issue with this choice. The following example with Borel primitives is given
by Blackwell (1965). Let $S=A=[0,1]$. Then there is a Borel set $B\subseteq
S\times A$ such that its projection $D$ to $S$ is not Borel measurable.
Consider $f$ to be the zero function and $r=1_{B}(a,s)$. Then $f$ and $r$ are
Borel measurable. But $Tf(s)=\sup_{a\in A}1_{B}(a,s)=1_{D}(s)$ is not Borel
measurable. Hence, we cannot apply Theorem 1 for the Borel primitives case.

We now present the assumptions of some of the main cases studied in the
literature on discounted dynamic programming where Theorem 1 can be applied.
We will assume that $\Gamma(s)=A$ for all $s\in S$ for the simplicity of the
exposition.

We say that $p$ is continuous (concave, increasing) if
$\int_{S}f(s^{\prime})p(s,a,ds^{\prime})$ is continuous (concave, increasing)
on $S\times A$ for every bounded and continuous (concave, increasing) function
$f$ on $S$.

Let $f\in U(S,\mathbb{R})$ and $\lambda\in U(S,A)$. The fact that
$T_{\lambda}f\in U(S,\mathbb{R})$ follows immediately for the last two cases
we consider (countable and finite). For the rest of the cases it holds from
the following argument: $\int_{S}f(y)p(s,a,ds^{\prime})$ is continuous,
(universally measurable, Borel measurable) whenever $f$ is continuous,
(universally measurable, Borel measurable). Hence, $Q(s,a,f)$ is continuous,
(universally measurable, Borel measurable) as the sum of continuous,
(universally measurable, Borel measurable) functions. Thus,
$T_{\lambda}f=Q(s,\lambda(s),f)$ is continuous, (universally measurable, Borel
measurable) as the composition of continuous, (universally measurable, Borel
measurable) (Bertsekas and Shreve, 1996).

  * •

The upper semianalytic case.555See Bertsekas and Shreve (1996) for a detailed
study of analytic sets, upper semianalytic functions, and universally
measurable sets and functions. $U(X,Y)$ is the set of universally measurable
functions666For a Borel set $X$ and a measure $q$ on $X$ define
$\mathcal{B}_{q}(X)$ to be the sigma-algebra generated by $\mathcal{B}(X)$ and
all the subsets of $X$ with outer measure zero with respect to $q$. $q$ has a
unique extension to $\mathcal{B}_{q}(X)$ called the completion of $q$. A set
is universally measurable if it belongs to $\cap_{q}\mathcal{B}_{q}(X)$ where
the intersection is over the set of all completions of probability measures on
$X$, i.e., a set is universally measurable if it is measurable with respect to
every complete probability measure on $X$ that measures all the Borel sets of
$X$. A function between two Borel sets $X$ and $Y$, $f:X\rightarrow Y$ is
universally measurable if the set $f^{-1}(B)$ is universally measurable in $X$
for every Borel measurable set $B$ of $Y$.  from $X$ to $Y$. $r$ is a bounded
function. We can choose $D$ to be the set of all bounded upper semianalytic
functions on $S$. $D$ is closed in $B_{m}(S)$ and it can be shown that $f\in
D$ implies $Tf\in D$ and $\Lambda_{f}\neq 0$ (see Bertsekas and Shreve
(1996)). Hence, we can apply Theorem 1.

  * •

The upper semi continuous case.777Recall that a function
$f:S\rightarrow\mathbb{R}$ is upper semi continuous if $\limsup f(s_{n})\leq
f(s)$ whenever $s_{n}\rightarrow s$.  $U(X,Y)$ is the set of Borel measurable
functions from $X$ to $Y$. $A$ is a compact metric space, $r$ is a bounded
upper semi continuous (u.s.c) function on $S\times A$, $p$ is continuous.
Under these conditions, we can choose $D$ to be the set of all bounded u.s.c
functions on $S$. $D$ is closed in $B_{m}(S)$ and it can be shown that $f\in
D$ implies $Tf\in D$ and $\Lambda_{f}\neq 0$ (see Dubins and Savage (1965) and
Maitra (1968)). In particular, $\Lambda_{f}$ contains a Borel measurable
function that achieves the supremum. Hence, we can apply Theorem 1.

  * •

The continuous case. $U(X,Y)$ is the set of Borel measurable functions from
$X$ to $Y$. $S$ and $A$ are compact metric spaces, $r$ is bounded and
continuous, $p$ is continuous. We can choose $D$ to be the set of all bounded
and continuous functions on $S$ which is closed in $B_{m}(S)$. It can be shown
that if $f\in D$ then $Tf\in D$ and $\Lambda_{f}\neq\emptyset$ (see Stokey and
Lucas (1989) for a detailed analysis of the continuous and continuous-concave
cases). In particular, $\Lambda_{f}$ contains a Borel measurable that achieves
the supremum. Hence, we can apply Theorem 1.

  * •

The continuous-concave case. $U(X,Y)$ is the set of continuous functions from
$X$ to $Y$. $A$ and $S$ are convex sets, $r$ is strictly concave, $p$ is
concave, and all the assumptions of the continuous case hold. We can choose
$D$ to be the set of all bounded, continuous and concave functions on $S$
which is closed in $B_{m}(S)$. It can be shown that if $f\in D$ then $Tf\in D$
and $\Lambda_{f}$ contains a continuous function that achieves the supremum.
Hence, we can apply Theorem 1.

  * •

The monotone case. $U(X,Y)$ is the set Borel measurable functions from $X$ to
$Y$. $A\subseteq\mathbb{R}^{n}$ is compact, $S\subseteq\mathbb{R}^{m}$. $r$ is
supermodular,888Recall that a function $f:X\rightarrow\mathbb{R}$ where $X$ is
a subset of $\mathbb{R}^{n}$ is supermodular if $f(x\vee y)+f(x\wedge y)\geq
f(x)+f(y)$ for all $x,y\in X$ where as usual $x\vee y$ denotes the
componentwise maximum and $x\wedge y$ the componentwise minimum.  continuous
in $a$, and increasing in $s$, $p$ is increasing, continuous in $a$, and
supermodular, i.e., for every increasing and supermodular function
$f:S\rightarrow\mathbb{R}$ the function
$\int_{S}f(s^{\prime})p(s,a,ds^{\prime})$ is supermodular, increasing, and
continuous in $a$. We can choose $D$ to be the set of increasing supermodular
functions which is closed in $B_{m}(S)$. It can be shown that if $f\in D$ then
$Tf\in D$ and $\Lambda_{f}$ contains an increasing function that achieves the
supremum (see Topkis (1998) and Light (2021) for examples and analysis of the
increasing case). Hence, we can apply Theorem 1.

  * •

The countable-compact case. $U(X,Y)$ is the set of all functions from $X$ to
$Y$. $S$ is countable, $A$ is compact999A prominent choice is to have $A$ be
the set all probability measures on some finite action set $A^{\prime}$. in
$\mathbb{R}^{n}$, $r$ is continuous and bounded, $p$ is continuous. We can
choose $D=B_{m}(S)=B(S)$ and the conditions of Theorem 1 obviously holds.

  * •

The finite case. $U(X,Y)$ is the set of all functions from $X$ to $Y$. $S$ and
$A$ are finite. We can choose $D=B_{m}(S)=B(S)$ and the conditions of Theorem
1 holds.

## References

  * Bertsekas (2012) Bertsekas, D. (2012): _Dynamic programming and optimal control: Volume I_ , vol. 1, Athena scientific.
  * Bertsekas and Shreve (1996) Bertsekas, D. and S. E. Shreve (1996): _Stochastic optimal control: the discrete-time case_ , vol. 5, Athena Scientific.
  * Blackwell (1965) Blackwell, D. (1965): “Discounted dynamic programming,” _The Annals of Mathematical Statistics_ , 36, 226–235.
  * Dubins and Savage (1965) Dubins, L. and L. Savage (1965): “How To Gamble If You Must,” _Mcgraw-Hill_.
  * Feinberg et al. (2012) Feinberg, E. A., P. O. Kasyanov, and N. V. Zadoianchuk (2012): “Average cost Markov decision processes with weakly continuous transition probabilities,” _Mathematics of Operations Research_ , 37, 591–607.
  * Feinberg et al. (2016) Feinberg, E. A., P. O. Kasyanov, and M. Z. Zgurovsky (2016): “Partially observable total-cost Markov decision processes with weakly continuous transition probabilities,” _Mathematics of Operations Research_ , 41, 656–681.
  * Light (2021) Light, B. (2021): “Stochastic Comparative Statics in Markov Decision Processes,” _Mathematics of Operations Research_ , 46, 797–810.
  * Maitra (1968) Maitra, A. (1968): “Discounted dynamic programming on compact metric spaces,” _Sankhyā: The Indian Journal of Statistics, Series A_ , 211–216.
  * Puterman (2014) Puterman, M. L. (2014): _Markov decision processes: discrete stochastic dynamic programming_ , John Wiley & Sons.
  * Stokey and Lucas (1989) Stokey, N. and R. Lucas (1989): _Recursive Methods in Economic Dynamics_ , Harvard University Press.
  * Topkis (1998) Topkis, D. M. (1998): _Supermodularity and complementarity_ , Princeton university press.

##  Appendix A Metric Spaces

We first recall the definition of a metric space.

###### Definition 1

A metric $d$ on a nonempty set $X$ is a function $d:X\times
X\rightarrow\mathbb{R}$ satisfying three properties:

1\. Positivity: $d(x,y)\geq 0$ for all $x,y\in X$, and $d(x,y)=0$ if and only
if $x=y$.

2\. Symmetry: $d(x,y)=d(y,x)$ for all $x,y\in X$.

3\. Triangle inequality: $d(x,y)\leq d(x,z)+d(z,y)$ for all $x,y,z\in X$.

The pair $(X,d)$ is called a metric space.

A sequence $\\{x_{n}\\}$ of a metric space $(X,d)$ is called a Cauchy sequence
if for all $\epsilon>0$, there exists $N$ such that $d(x_{n},x_{m})<\epsilon$
for all $n,m>N$. A metric space $(X,d)$ is called complete if every Cauchy
sequence converges in $X$ (e.g., $\mathbb{R}^{n}$).

Recall that a fixed-point of a mapping $T:X\rightarrow X$ is a $x\in S$ such
that $T(x)=x$. We will need the following result due to Banach.

###### Proposition 1

(Banach fixed-point theorem) Let $(X,d)$ be a complete metric space. Let
$T:X\rightarrow X$ be a mapping that is $L$-contraction, i.e.,
$d(T(x),T(y))\leq Ld(x,y)$ for some $0<L<1$ and for all $x,y\in X$. Then $T$
has a unique fixed-point.

Proof. First, $T$ has at most one fixed-point. If $T$ has two fixed-points
$x,y$, then $d(x,y)=d(T(x),T(y))\leq Ld(x,y)$ which implies $d(x,y)=0$, i.e.,
$x=y$.

It remains to establish the existence of a fixed-point.

Let $x_{0}\in X$ and consider the sequence $\\{x_{n}\\}$ given by
$x_{n+1}=T(x_{n})$. We claim that $\\{x_{n}\\}$ is a Cauchy sequence.

We have $d(x_{m+1},x_{m})=d(T(x_{m}),T(x_{m-1}))\leq Ld(x_{m},x_{m-1})$ so
continuing recursively we conclude that $d(x_{m+1},x_{m})\leq
L^{m}d(x_{1},x_{0})$. Hence, for $n\geq m$ we have

$d(x_{n},x_{m})\leq\sum_{i=m}^{n-1}d(x_{i+1},x_{i})\leq\sum_{i=m}^{n-1}L^{i}d(x_{1},x_{0})\leq\frac{L^{m}}{1-L}d(x_{1},x_{0}).$

Because $0<L<1$, for all $\epsilon>0$ there exists an $N$ such that for all
$n,m\geq N$ we have $d(x_{n},x_{m})\leq\epsilon$. Thus, $\\{x_{n}\\}$ is a
Cauchy sequence.

Because $(X,d)$ is complete the sequence $\\{x_{n}\\}$ converges to some $x\in
X$. We will show that $x$ is a fixed-point of $T$. We have

$d(x,T(x))\leq d(x,x_{n})+d(x_{n},T(x))=d(x,x_{n})+d(T(x_{n-1}),T(x))\leq
d(x,x_{n})+Ld(x_{n-1},x).$

Taking the limit $n\rightarrow\infty$ in the last inequality implies that
$d(x,T(x))=0$, i.e., $T(x)=x$ so $x$ is a fixed-point of $T$.