11institutetext: Dublin City University, Ireland 22institutetext: University
College Dublin, Ireland 33institutetext: Insight SFI Research Centre for Data
Analytics, Ireland
33email<EMAIL_ADDRESS>
# Hierarchical reinforcement learning for in-hand robotic manipulation using
Davenport chained rotations

Francisco Roldan Sanchez* 1133 Qiang Wang 22 David Cordova Bulens 22 Kevin
McGuinness 11 3 3 Stephen J. Redmond 22 3 3 Noel E. O’Connor 11 3 3

###### Abstract

End-to-end reinforcement learning techniques are among the most successful
methods for robotic manipulation tasks. However, the training time required to
find a good policy capable of solving complex tasks is prohibitively large.
Therefore, depending on the computing resources available, it might not be
feasible to use such techniques. The use of domain knowledge to decompose
manipulation tasks into primitive skills, to be performed in sequence, could
reduce the overall complexity of the learning problem, and hence reduce the
amount of training required to achieve dexterity. In this paper, we propose
the use of Davenport chained rotations to decompose complex 3D rotation goals
into a concatenation of a smaller set of more simple rotation skills. State-
of-the-art reinforcement-learning-based methods can then be trained using less
overall simulated experience. We compare its performance with the popular
Hindsight Experience Replay method, trained in an end-to-end fashion using the
same amount of experience in a simulated robotic hand environment. Despite a
general decrease in performance of the primitive skills when being
sequentially executed, we find that decomposing arbitrary 3D rotations into
elementary rotations is beneficial when computing resources are limited,
obtaining increases of success rates of approximately 10% on the most complex
3D rotations with respect to the success rates obtained by HER trained in an
end-to-end fashion, and increases of success rates between 20% and 40% on the
most simple rotations.

###### Keywords:

Robotic manipulation Deep reinforcement learning Hierarchical reinforcement
learning

##  1 Introduction

A primary reason why it takes so long to train state-of-the-art reinforcement
learning techniques in manipulation tasks is that they are very complex to
solve without domain knowledge [1, 2, 3]. However, most manipulation tasks can
be decomposed into a number of easier tasks that a robot can learn more easily
with much less training experience required [4, 5]. For example, robots can
easily learn how to reach a point in space, or how to push an object, when
these tasks are trained independently [6]. However, if the robot needs to
learn from scratch how to reach an object and push it at the same time, the
training time required increases in a nonlinear manner, meaning it often
requires more simulated experience overall to learn these skills [7].

Training time becomes an important matter for tasks that have high degrees of
complexity, like the block manipulation tasks in OpenAI’s Gym environment [8].
The most popular method for learning in this kind of goal-based environment is
Hindsight Experience Replay (HER) [9] trained in conjunction with Deep
Deterministic Policy Gradients (DDPG) [1]. HER is capable of successfully
solving most tasks implemented in this environment, but the amount of
simulated experience it requires for training is immense, exceeding $38\times
10^{7}$ time-steps in the most complex tasks, and even then it is not able to
discover an optimal policy that is able to solve all object rotation goals.
Furthermore, 19 CPU cores are required to generate simulated experience in
parallel [10].

Traditional robotic manipulation systems usually define a set of non-primitive
and primitive tasks that have a hierarchy [11, 12, 13]. Non-primitive actions
are a composition of primitive actions performed in a particular order, where
a primitive action is one which cannot or should not be further divided into a
sequence of simpler actions. Therefore, in order to reproduce a non-primitive
action, a robot must sequentially perform a set of primitive actions. We refer
to Hierarchical Reinforcement Learning (HRL) as those reinforcement learning
methods that decompose a problem into a hierarchy of sub-problems such that
solving the original problem requires the sequential execution of the
solutions of these sub-problems as if they were primitive actions.

The most notable difference between traditional robotic manipulation and
reinforcement learning based manipulation is how decision making is done:
while traditional methods use a sequential set of motions that have a
hierarchy, reinforcement-learning-based methods typically do not.
Reinforcement learning methods are useful because they can learn policies that
are closer to optimality than those an engineer might heuristically design.
However, when tasks are very complex, reinforcement learning methods take a
very long time to train.

In this paper we propose the use of Davenport angles [14] to decompose 3D
rotations into a sequential chain of 1D rotations. By independently learning
to perform 1D rotations around different orthogonal axes, which can then be
executed sequentially to achieve a 3D rotational goal, we investigate if this
methodology will accelerate the overall reinforcement learning goal when
compared to training using the standard method that uses HER.

##  2 Related work

In the context of robotic manipulation, deep reinforcement learning methods
allow the robot to learn more refined skills that would be very difficult to
replicate through bespoke engineering. Because off-policy methods have an
improved sample complexity when compared to on-policy methods, off-policy
methods are often preferred when dealing with manipulation tasks [15, 16].
This also relates to a general data-efficiency problem that reinforcement
learning methods suffer, as data collection is very intensive [17].

In off-policy reinforcement learning, two different policies are observed
during the learning phase: a behavioral policy and a target policy. While the
behavioral policy is used for action selection and exploration, the target
policy is the one being updated by using previously-collected experience from
a replay buffer. This replay buffer not only improves sample efficiency, but
also allows the target policy to learn from mistakes and successes of the
behavioral policy, whereas on-policy methods would learn sub-optimal policies.

HER is an exploration strategy that allows agents to learn faster,
particularly when dealing with sparse rewards (i.e., temporally intermittent
rewards). More specifically, HER has proven to be a very efficient method in
reward settings where the reward is sparse and does not carry much
information, such as binary rewards.

In a standard reinforcement learning framework, the agent learns from positive
experiences [18]. In other words, under a standard framework, every time that
agent actions lead to an unsuccessful example where the task is not correctly
solved, the only outcome the agent can have is that the sequence of actions
that was taken did not lead to the target goal. However, if the objective
would have been to reach the achieved goal, this same sequence of actions
would then be a valid sequence from which the agent could learn.

HER facilitates learning from failed attempts by replaying each episode but
altering the goal that the agent was originally trying to solve. For example,
if a robotic hand is trying to manipulate a cube so that it reaches a target
pose $p$, but the actions taken lead to a different pose $p^{\prime}$, when
HER replays, the agent would get two outcomes: that this sequence of actions
is not optimal to reach pose $p$, but instead it is optimal to reach the pose
$p^{\prime}$. In other words, the agent will be learning from mistakes.

This algorithm can also be understood as a curriculum learning technique, with
HER goals naturally evolving from simple goals that even random actions can
perform successfully, to more sophisticated goals that require a more skillful
policy. However, in contrast to typical curriculum learning approaches, this
is done automatically without needing to initialize the environment in any
particular state.

Even though HER is a method that is capable of solving complex manipulation
tasks, it takes a very long time to train because of the lack of domain
knowledge employed during the learning phase. In this paper we explore this
problem in the context of in-hand cube manipulation tasks by decomposing the
target goals and training HER to learn simpler primitive skills.

##  3 Method

Complex tasks are often defined by complex goals. In the case of the OpenAI
Gym hand block manipulation environment, this complexity appears when the goal
the robot needs to achieve consists of implementing arbitrary 3D rotations.

However, any 3D rotation can be decomposed into three sequential rotations
around the orthogonal axes of a known reference frame [19]. These rotations
can be performed around the axes of a fixed system of reference (extrinsic
rotations) or around the axes of the rotating system of reference (intrinsic
rotations), and only if the second axis of rotation is orthogonal to the plane
containing the first and third axes [20]. In the case of the OpenAI’s robotic
hand environment, this reference frame is fixed, and therefore, the decomposed
sequence of rotations applied to the cube must be extrinsic (see Figure 1).

Figure 1: Example of a 3D rotation goal decomposition into three Davenport
angles. A target 3D rotation (a) is decomposed into three consecutive target
rotations around the (b) $z$, (c) $x$ and (d) $z$ axes, respectively. Goal
decomposition can be understood by looking at the target poses, which are the
cubes that are not touching the robotic hand, compared to the starting poses
for the rotations, which are shown as the cubes in the robotic hand.

The OpenAI Gym robotic hand block environment contains three different
manipulation tasks of increasing complexity:

  * •

RotateZ: goal consists of a random target rotation around the $z$ axis of the
reference frame and position is ignored.

  * •

RotateParallel: goal consists of a random target rotation around the $z$ axis
and rotations by multiples of $\frac{\pi}{2}$ around the $x$ and $y$ axes,
with position being ignored.

  * •

RotateXYZ: goal consists of a random target 3D rotation with the target
position ignored.

Observations in all of these tasks include positions and velocities of the
robot joints and the pose of the object manipulated (its Cartesian position
and its rotation expressed in quaternions).

The reward system applied in this environment is as follows: at each time-
step, the agent gets 0 reward if the task is completed, and -1 otherwise. In
order to determine whether a rotation has been completed successfully, a
quaternion difference between the desired and the achieved poses is used
$\theta=\arccos(2\langle q_{1},q_{2}\rangle^{2}-1)$, where $\langle
q_{1},q_{2}\rangle$ represents the inner product of quaternions $q_{1}$ and
$q_{2}$, and considered successful when this difference is less than 0.1
radians.

In order to learn rotations around the $x$ and $y$ axes, two different new
tasks based on the RotateZ task were implemented for the hand
environment111The newly defined tasks can be found at
https://github.com/franroldans/custom_gym:

  * •

RotateY: goal consists of a random target rotation around the $y$ axis of
reference frame, with the block’s position ignored;

  * •

RotateX: goal consists of a random target rotation around the $x$ axis of
reference frame and again position is ignored.

###  3.1 Policy learning

We trained HER in combination with DDPG for each of the basic rotation tasks:
RotateX, RotateY, and RotateZ. For these tasks, episodes have a length of 100
time-steps. This means that, during inference, the agent will have 300 time-
steps in order to solve the task, 100 time-steps for each of the three chained
rotations.

To have a fair comparison, we train HER for the most complex tasks
(RotateParallel and RotateXYZ) using episodes lasting 100 time-steps to
encourage the learning of actions that solve the task quickly, but test it
using episodes of 300 time-steps in order to match the number of time-steps
our method uses to solve the tasks. However, we only train HER for these tasks
using the same number of time-steps used for training the three policies that
perform rotations around extrinsic axes, which are the policies trained on the
RotateX, RotateY and RotateZ tasks: 4,000,000 + 4,000,000 + 2,000,000 =
10,000,000 time-steps. This way, we can determine whether using Davenport
chained rotations is comparable to end-to-end learning of 3D rotations in
terms of the accuracy with which the target rotation is achieved for the same
amount of training.

We hypothesize that training HER to learn rotations around extrinsic axes and
using the policies learned in a hierarchical manner can achieve better success
rates than training HER in an end-to-end fashion on the most complex
RotateParallel and RotateXYZ tasks, if both methods are trained using the same
amount of simulated experience.

###  3.2 Evaluation

There is no unique way of decomposing a 3D rotation into three consecutive
rotations around extrinsic axes. The same rotation can be achieved by
decomposing that rotation into elementary rotations around
$z{\text{-}}x{\text{-}}z$, $x{\text{-}}y{\text{-}}x$,
$y{\text{-}}z{\text{-}}y$, $z{\text{-}}y{\text{-}}z$,
$x{\text{-}}z{\text{-}}x$ or $y{\text{-}}x{\text{-}}y$.

Because applying rotations around the $z$-axis in the context of the hand
block environment is easier than rotating the cube around the $x$ or $y$ axes,
we only evaluate the performance of our model for the rotation decomposition
configurations that require two rotations around the $z$-axis and one rotation
around either the $y$ or the $x$ axis; that is, we only evaluate the
$z{\text{-}}x{\text{-}}z$ and $z{\text{-}}y{\text{-}}z$ chained rotation
configurations.

To evaluate our method and compare its performance against that obtained with
end-to-end learning, we create a test set of 6,600 different initial and
target cube poses. This test set is divided depending on how many extrinsic
rotations the robot must perform to achieve the target goals.

We also differentiate whether the rotation targets are comparable only to the
RotateXYZ task, or if they are also comparable to the RotateParallel task. Not
all rotations that are comparable to the RotateXYZ task can be performed by
the policy trained on the RotateParallel task because the goals generated on
the RotateParallel task only had angles of rotation around the $x$ and $y$
axes contained in the set $\\{-\pi,-\frac{\pi}{2},0,\frac{\pi}{2},\pi\\}$. The
distribution of target goals of this test set is shown in Table 1.

Table 1: Test set created to evaluate the method. We compare the success rate of our method and HER trained in an end-to-end fashion and classify the target rotations depending on how many extrinsic rotations are needed to solve the task. The table shows how many rotations of each task category are present in the test set. All target rotations comparable to the RotateParallel are also contained in the RotateXYZ. Comparable | # rotations
---|---
to | 1 | 2 | 3
RotateParallel | 200 | 1000 | 2000
RotateXYZ | 600 | 2000 | 4000

##  4 Results

As predicted, HER trained in conjunction with DDPG was able to successfully
learn rotations around extrinsic axes. However, in order to achieve near
perfect success rates, the RotateX and RotateY tasks needed a total of 40
epochs of training instead of the 20 epochs that it takes for the RotateZ task
(see Figure 2). This happens because rotations around the $z$-axis always have
one of the cube faces parallel to the palm of the hand, which makes the task
easier, as the cube position is very stable. In contrast, rotations around the
$x$ and $y$ axes often have cube poses where there is no face parallel to the
palm of the hand, making it more challenging to maintain a stable grasp on the
cube.

These initial experiments suggest that it is indeed the case that chained
rotations can achieve better performance than end-to-end training. Using the
same overall amount of time-steps for training rotations around intrinsic axes
can achieve approximately 100% success rate, while for the RotateParallel and
the RotateXYZ tasks, end-to-end HER can only achieve approximately 50% and 40%
of success rate, respectively (see Figure 3).

(a) RotateZ

(b) RotateX

(c) RotateY

Figure 2: Success rate evolution during training of the policies trained for
the original (a) RotateZ, and the implemented (b) RotateX and (c) RotateY
tasks. Shown is success rate versus policy update count, which happens every
50 episodes (5000 time-steps). In total, the RotateZ tasks needs $2\times
10^{6}$ timesteps of simulated experience, while the RotateX and RotateY need
$4\times 10^{6}$ timesteps in order to have near perfect success rates.

(a) RotateParallel

(b) RotateXYZ

Figure 3: Success rate evolution per policy update of HER trained in an end-to-end manner for the (a) RotateParallel, and the (b) RotateXYZ tasks using $10^{7}$ time-steps of simulated experience.  Table 2: Success rates on the test set for our method and the policies learned on the RotateParallel and RotateXYZ experiments depending on how many extrinsic rotations the robot is required to perform. Our method only shows the best performance out of the $z{\text{-}}x{\text{-}}z$ and $z{\text{-}}y{\text{-}}z$ chained rotations configurations. Success rates of our method on the left side only apply to those rotations on the test set that are comparable to the RotateParallel experiments, while success rates on the right side show the results of those rotations comparable to the RotateXYZ experiments. # rotations | Multi-step (Ours) | RotateParallel | Multi-step (Ours) | RotateXYZ
---|---|---|---|---
1 | 97.5% | 69% | 96.16% | 57.5%
2 | 88.4% | 63.4% | 82.21% | 47.25%
3 | 66.05% | 47.15% | 51.68% | 43.85%

Results after evaluating the method on the test set show that the hypothesis
stated in this paper is supported: decomposing complex 3D rotations into
elementary rotations around extrinsic axes can be beneficial when computing
resources for training are limited (see Table 2). However, the success rates
obtained when applying this approach vary depending on how many elementary
extrinsic rotations must be applied to achieve the target 3D rotation.

##  5 Discussion

While the success rate obtained when requiring only one extrinsic rotation is
near perfect, this result does not hold when two or more extrinsic rotations
are needed. The reason behind this decrease in performance is because each
rotation step expects the previous rotation to have been performed perfectly.
If the second extrinsic rotation is not achieved, the third rotation will
automatically fail because the policy employed has been trained to perform
rotations around one axis, but the goal it needs to reach would also require
it to correct the previous mistake.

There are two main possible alternatives to overcome this problem. First, data
augmentation could be used in order to add noise to the initial cube positions
so that the primitive policies learned could also take into account errors on
the previous steps [21, 22], helping the robot achieve a better performance at
the expense of more training time. Second, the method of decomposing the
rotation could be applied in an iterative manner, with each sequence of three
rotations converging on the target goal through repeated attempts. However,
doing this would obviously slow down the execution of the manipulation task.

From a qualitative analysis of some of our earlier preliminary results, most
of the errors our method produced in the second rotation appeared when dealing
with large rotations. While the policies learned for the RotateX and RotateY
tasks were very proficient in applying rotations on the range of
$[-\frac{\pi}{2},\frac{\pi}{2}]$, when having to apply rotations in the range
of $[-\pi,-\frac{\pi}{2})$ and $(\frac{\pi}{2},\pi]$, they were not always
correctly reproduced. This was overcome by introducing further intermediate
steps: whenever these policies need to perform a large rotation with a
magnitude greater than $\frac{\pi}{2}$, firstly rotate the cube either
$\frac{\pi}{2}$ or $-\frac{\pi}{2}$ and then apply the remaining smaller
rotation to complete the goal.

After including this extra intermediate step, the success rate on the test set
increased from 67.05% to 82.21% for those 3D rotations that can be decomposed
into two extrinsic rotations. Some errors appeared in the third rotation that
used the policy trained on the RotateZ task, where the agent could not always
maintain tilted cube poses. This happens because the policy trained on the
RotateZ task had the cube initialized in a way that it always had one face
touching the robotic hand in a stable position. Because the policy never saw
this kind of tilted configuration during training, on inference it tends to
fail. A solution to this would be introducing these tilted initial
configurations and goals into the RotateZ environment so that the robot sees
these configurations during the learning phase. Another solution could be
forcing the agent to learn how to apply rotation vectors instead of reaching a
pose in particular, making the learning invariant to the initial
configuration. A last possible solution could be applying rotations with a
magnitude of $\frac{\pi}{2}$, where the cube would be kept face down until the
last rotation, and then apply the remaining rotation in the last step.

As mentioned in Sections 1 and 2, HER is able to successfully solve this task
when being trained for $38\times 10^{7}$ time-steps and using 19 CPU cores
generating simulated experience in parallel, one worker for each core [10].
Translated to days, this equates to approximately 30 days of training.
Considering the sensitivity of reinforcement learning models to hyperparameter
selection, this becomes an issue when computing resources are scarce [23].
Instead, our method is trained using a single CPU with no parallelization, and
the training takes less than one day (three days if adding the training time
of all the primitive skills, or two days if only considering the training time
of the primitive skills used to perform one arbitrary 3D rotation, such as
$z-y-z$).

##  6 Conclusion

Training time is a key consideration of all artificial intelligence research,
as often small companies and academia have scarce computing resources. In
order to train reinforcement learning algorithms to solve complex manipulation
tasks in an end-to-end fashion with minimal domain knowledge, engineers either
need to spend a lot of time training their models or use a substantial number
of CPU cores to generate data in parallel. This presents difficulties for
hyperparameter exploration and tuning, as in many cases running several
simultaneous experiments is not feasible.

In this paper we explored the idea of decomposing complex manipulation goals
into a set of simpler goals in the context of a simulated robotic hand
environment. Through the addition of domain knowledge, a robot learns how to
rotate a cube, with the simulated experience used during training limited to
$10^{7}$ time-steps.

Furthermore, several ideas for future work have been stated throughout the
discussion above. These are summarized as follows for the reader’s
convenience:

  * •

Use data augmentation techniques to find policies capable of correcting
mistakes made in previous intermediate steps;

  * •

Iteratively decompose the target rotation into three other elementary
extrinsic rotations when a step fails;

  * •

Improve goal and state exploration by introducing tilted cube configurations
and goals during training in order to make the agent learn more unconventional
rotations;

  * •

Encourage the agent to learn how to apply any given rotation vector instead of
reaching a particular pose.

## References

  * [1] Lillicrap, Timothy P., Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. “Continuous control with deep reinforcement learning.” arXiv preprint arXiv:1509.02971 (2015).
  * [2] Gu, Shixiang, Timothy Lillicrap, Ilya Sutskever, and Sergey Levine. “Continuous deep q-learning with model-based acceleration.” In International conference on machine learning, pp. 2829-2838. PMLR, 2016.
  * [3] Pastor, Peter, Heiko Hoffmann, Tamim Asfour, and Stefan Schaal. “Learning and generalization of motor skills by learning from demonstration.” In 2009 IEEE International Conference on Robotics and Automation, pp. 763-768. IEEE, 2009.
  * [4] Cohen, Benjamin J., Sachin Chitta, and Maxim Likhachev. “Search-based planning for manipulation with motion primitives.” 2010 IEEE International Conference on Robotics and Automation. IEEE, 2010.
  * [5] Stulp, Freek, et al. “Learning motion primitive goals for robust manipulation.” 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2011.
  * [6] Stulp, Freek, Evangelos A. Theodorou, and Stefan Schaal. “Reinforcement learning with sequences of motion primitives for robust manipulation.” IEEE Transactions on robotics 28, no. 6 (2012): 1360-1370.
  * [7] Strudel, Robin, Alexander Pashevich, Igor Kalevatykh, Ivan Laptev, Josef Sivic, and Cordelia Schmid. “Learning to combine primitive skills: A step towards versatile robotic manipulation §.” In 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 4637-4643. IEEE, 2020.
  * [8] Brockman, Greg, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. “Openai Gym.” arXiv preprint arXiv:1606.01540 (2016).
  * [9] Andrychowicz, Marcin, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojciech Zaremba. “Hindsight experience replay.” Advances in neural information processing systems 30 (2017).
  * [10] Plappert, Matthias, Marcin Andrychowicz, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider et al. “Multi-goal reinforcement learning: Challenging robotics environments and request for research.” arXiv preprint arXiv:1802.09464 (2018).
  * [11] Clement, Bradley J., and Edmund H. Durfee. “Top-down search for coordinating the hierarchical plans of multiple agents.” In Proceedings of the third annual conference on Autonomous Agents, pp. 252-259. 1999.
  * [12] Garland, Andrew, and Neal Lesh. “Learning hierarchical task models by demonstration.” Mitsubishi Electric Research Laboratory (MERL), USA–(January 2002) (2003): 51-79.
  * [13] Liu, Mingxing, Yang Tan, and Vincent Padois. “Generalized hierarchical control.” Autonomous Robots 40, no. 1 (2016): 17-31.
  * [14] Malcolm D. Shuster, F. Landis Markley, “General formula for extraction the Euler angles.” Journal of guidance, control, and dynamics, vol. 29.1, pp. 215-221. 2006
  * [15] Munos, Rémi, Tom Stepleton, Anna Harutyunyan, and Marc Bellemare. “Safe and efficient off-policy reinforcement learning.” Advances in neural information processing systems 29 (2016).
  * [16] Haarnoja, Tuomas, Aurick Zhou, Pieter Abbeel, and Sergey Levine. “Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.” In International conference on machine learning, pp. 1861-1870. PMLR, 2018.
  * [17] Thomas, Philip, and Emma Brunskill. “Data-efficient off-policy policy evaluation for reinforcement learning.” In International Conference on Machine Learning, pp. 2139-2148. PMLR, 2016.
  * [18] Mitsunaga, Noriaki, Christian Smith, Takayuki Kanda, Hiroshi Ishiguro, and Norihiro Hagita. “Robot behavior adaptation for human-robot interaction based on policy gradient reinforcement learning.” Journal of the Robotics Society of Japan 24, no. 7 (2006): 820-829.
  * [19] Henderson, David M. “Euler angles, quaternions, and transformation matrices for space shuttle analysis.” No. DN-1.4-8-020. 1977.
  * [20] Goldstein, H. “Euler Angles in Alternate Conventions.” Appendix B in Classical Mechanics, 2nd ed. Reading, MA: Addison-Wesley, 606-610, 1980.
  * [21] Mitrano, Peter, and Dmitry Berenson. “Data Augmentation for Manipulation.” arXiv preprint arXiv:2205.02886 (2022).
  * [22] Hansen, Nicklas, and Xiaolong Wang. “Generalization in reinforcement learning by soft data augmentation.” In 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 13611-13617. IEEE, 2021.
  * [23] Paine, Tom Le, Cosmin Paduraru, Andrea Michi, Caglar Gulcehre, Konrad Zolna, Alexander Novikov, Ziyu Wang, and Nando de Freitas. “Hyperparameter selection for offline reinforcement learning.” arXiv preprint arXiv:2007.09055 (2020).

## Acknowledgments

This publication has emanated from research supported by Science Foundation
Ireland (SFI) under Grant Number SFI/12/RC/2289_P2, co-funded by the European
Regional Development Fund, by Science Foundation Ireland Future Research
Leaders Award (17/FRL/4832), and by China Scholarship Council (CSC
No.202006540003). For the purpose of Open Access, the author has applied a CC
BY public copyright licence to any Author Accepted Manuscript version arising
from this submission.


$\left\lVert\boldsymbol{x}-\boldsymbol{z}\right\rVert_{2},\left\lVert\boldsymbol{x}^{\prime}-\boldsymbol{z}^{\prime}\right\rVert_{2}\leq
O(1/m)$, we have

$\sup_{t\in T}\left\lvert
r_{t}^{(p),m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-r_{0}^{(p),m}(\boldsymbol{z},\boldsymbol{z}^{\prime})\right\rvert=O\left(m^{-\frac{1}{12}}\sqrt{\log
m}\right),~{}\text{when}~{}m\geq C_{1}\left(\log(C_{2}/\delta)\right)^{6/5}.$

###### Proof of Proposition 7.24.

By Lemma 7.23 (choose parameter $\tau=\Theta(m^{1/4})$), Lemma 7.9 and

$\displaystyle\left\lVert\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x})\right\rVert_{F}$
$\displaystyle\leq\left\lVert\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z})\right\rVert_{F}+\left\lVert\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x})-\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z})\right\rVert_{F};$
$\displaystyle\left\lVert\nabla_{\boldsymbol{V}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x}^{\prime})\right\rVert_{F}$
$\displaystyle\leq\left\lVert\nabla_{\boldsymbol{V}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z}^{\prime})\right\rVert_{F}+\left\lVert\nabla_{\boldsymbol{V}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x}^{\prime})-\nabla_{\boldsymbol{V}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z}^{\prime})\right\rVert_{F},$

with probability at least $1-\exp(-\Omega(m^{5/6}))$, we have

$\displaystyle\left\lvert\left\langle\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x}),\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x}^{\prime})\right\rangle-\left\langle\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z}),\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z}^{\prime})\right\rangle\right\rvert$
$\displaystyle\qquad\qquad\qquad~{}~{}\leq\left\lVert\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z})\right\rVert_{F}\left\lVert\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x}^{\prime})-\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z}^{\prime})\right\rVert_{F}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad~{}~{}+\left\lVert\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x}^{\prime})\right\rVert_{F}\left\lVert\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x})-\nabla_{\boldsymbol{W}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z})\right\rVert_{F}$
$\displaystyle\qquad\qquad\qquad~{}~{}\leq O(1)\cdot
O\left(m^{-\frac{1}{12}}\sqrt{\log m}\right)+O(1)\cdot
O\left(m^{-\frac{1}{12}}\sqrt{\log m}\right)\leq
O\left(m^{-\frac{1}{12}}\sqrt{\log m}\right)$

and similarly have

$\displaystyle\left\lvert\left\langle\nabla_{\boldsymbol{V}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x}),\nabla_{\boldsymbol{V}^{(l)}}f^{(p),m}_{t}(\boldsymbol{x}^{\prime})\right\rangle-\left\langle\nabla_{\boldsymbol{V}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z}),\nabla_{\boldsymbol{V}^{(l)}}f^{(p),m}_{0}(\boldsymbol{z}^{\prime})\right\rangle\right\rvert$
$\displaystyle\leq O\left(m^{-\frac{1}{12}}\sqrt{\log m}\right)$

for all $l\in[L]$, $t\in T$ and
$\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathbb{S}^{d-1}$ such that
$\left\lVert\boldsymbol{x}-\boldsymbol{z}\right\rVert_{2},\left\lVert\boldsymbol{x}^{\prime}-\boldsymbol{z}^{\prime}\right\rVert_{2}\leq
O(1/m)$ when $m$ is greater than some positive absolute constant $C$. Combine
with Eq.(17), with probability at least $1-\exp(-\Omega(m^{5/6}))$, we can get

$\displaystyle\sup_{t\in T}\left\lvert
r_{t}^{(p),m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-r_{0}^{(p),m}(\boldsymbol{z},\boldsymbol{z}^{\prime})\right\rvert=O\left(m^{-\frac{1}{12}}\sqrt{\log
m}\right).$

Also, it is easy to check that there exist some positive absolute constants
$C_{1}>0$ and $C_{2}\geq 1$ such that
$C_{1}\left(\log\left(C_{2}/\delta\right)\right)^{6/5}\geq C$ holds for
$\delta\in(0,1)$ and when $m\geq
C_{1}\left(\log\left(C_{2}/\delta\right)\right)^{6/5}$, we have
$1-\exp\left(-\Omega\left(m^{5/6}\right)\right)\geq 1-\delta$.

∎

###  7.5 Hölder Continuity of $r$

For our convenience let us first introduce the following definition of Hölder
spaces. For a compact set $\Omega$ and $\alpha\in[0,1]$, let us define a semi-
norm for $f:\Omega\to\mathbb{R}$ by

$\displaystyle\left\lvert f\right\rvert_{0,\alpha}=\sup_{x,y\in\Omega,~{}x\neq
y}\frac{\left\lvert f(x)-f(y)\right\rvert}{\left\lVert
x-y\right\rVert^{\alpha}}$

and define the Hölder space by

$\displaystyle C^{0,\alpha}(\Omega)=\left\\{f\in C(\Omega):\left\lvert
f\right\rvert_{0,\alpha}<\infty\right\\},$ (20)

which is equipped with norm $\left\lVert
f\right\rVert_{C^{0,\alpha}(\Omega)}=\sup_{x\in\Omega}\left\lvert
f(x)\right\rvert+\left\lvert f\right\rvert_{\alpha}$. Then it is easy to show
that

  * •

$i)$ $C^{0,\alpha}(\Omega)\subseteq C^{0,\beta}(\Omega)$ if $\beta\leq\alpha$;

  * •

$ii)$ if $f,g\in C^{0,\alpha}(\Omega)$, then $f+g,~{}fg\in
C^{\alpha}(\Omega)$;

  * •

$iii)$ if $f\in C^{0,\alpha}(\Omega_{1})$ and $g\in C^{0,\beta}(\Omega_{2})$
with $\text{Ran }g\subseteq\Omega_{1}$, then $f\circ g\in
C^{0,\alpha\beta}(\Omega_{2})$.

######  Proposition 7.25.

We have $r\in C^{0,s}(\Omega)$ with $s=2^{-L}$ and
$\Omega=\mathbb{S}^{d-1}\times\mathbb{S}^{d-1}$, that is, there is some
constant $C>0$ that

$\displaystyle|r(\boldsymbol{x},\boldsymbol{x}^{\prime})-r(\boldsymbol{z},\boldsymbol{z}^{\prime})|\leq
C\|(\boldsymbol{x},\boldsymbol{x}^{\prime})-(\boldsymbol{z},\boldsymbol{z}^{\prime})\|_{2}^{s}.$

###### Proof of Proposition 7.25.

Recall that $r$ is given by

$\displaystyle
r(\boldsymbol{x},\boldsymbol{x}^{\prime})=C\sum_{l=1}^{L}B_{l+1}(\boldsymbol{x},\boldsymbol{x}^{\prime})\left[(1+a^{2})^{l-1}\kappa_{1}\left(\frac{K_{l-1}(\boldsymbol{x},\boldsymbol{x}^{\prime})}{(1+a^{2})^{l-1}}\right)+K_{l-1}(\boldsymbol{x},\boldsymbol{x}^{\prime})\kappa_{0}\left(\frac{K_{l-1}(\boldsymbol{x},\boldsymbol{x}^{\prime})}{(1+a^{2})^{l-1}}\right)\right],$

where $C={1}/{2L(1+a^{2})^{L-1}}$,
$K_{0}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\boldsymbol{x}^{\top}\boldsymbol{x}^{\prime}$,
$B_{L+1}(\boldsymbol{x},\boldsymbol{x}^{\prime})=1$ and

$\displaystyle\kappa_{0}(u)=\frac{1}{\pi}(\pi-\arccos(u),\quad\kappa_{1}(u)=\frac{1}{\pi}\left(u(\pi-\arccos(u))+\sqrt{1-u^{2}}\right)$
$\displaystyle
K_{l}(\boldsymbol{x},\boldsymbol{x}^{\prime})=K_{l-1}(\boldsymbol{x},\boldsymbol{x}^{\prime})+a^{2}(1+a^{2})^{l-1}\kappa_{1}\left(\frac{K_{l-1}(\boldsymbol{x},\boldsymbol{x}^{\prime})}{(1+a^{2})^{l-1}}\right)$
$\displaystyle
B_{l}(\boldsymbol{x},\boldsymbol{x}^{\prime})=B_{l+1}(\boldsymbol{x},\boldsymbol{x}^{\prime})\left[1+a^{2}\kappa_{0}\left(\frac{K_{l-1}(\boldsymbol{x},\boldsymbol{x}^{\prime})}{(1+a^{2})^{l-1}}\right)\right].$

Since $r$ is symmetric, by triangle inequality it suffices to prove that
$r(\boldsymbol{x}_{0},\cdot)\in C^{0,s}(\mathbb{S}^{d-1})$ with $\left\lvert
r(\boldsymbol{x}_{0},\cdot)\right\rvert_{0,s}$ bounded by a constant
independent of $\boldsymbol{x}_{0}$. It is easy to check that
$\boldsymbol{x}\to\boldsymbol{x}^{T}\boldsymbol{x}_{0}\in
C^{0,1}(\mathbb{S}^{d-1})$ and

$|\arccos\mu-\arccos\nu|=O(\sqrt{|\mu-\nu|})~{}\text{and}~{}|\sqrt{1-\mu^{2}}-\sqrt{1-\nu^{2}}|=O(\sqrt{|\mu-\nu|}),$

meaning that $\kappa_{0},\kappa_{1}\in C^{0,\frac{1}{2}}([-1,1])$. Thus, $r\in
C^{0,s}(\Omega)$ with $s=(1/2)^{L}$.

∎

###  7.6 Proof of the kernel uniform convergence

###### Proof of Proposition 3.2.

By Lemma 7.19, there exists a polynomial $\mathrm{poly}_{1}(\cdot)$, such that
for any $\delta\in(0,1)$, when
$m\geq\mathrm{poly}_{1}\left(n,\left\lVert\boldsymbol{y}\right\rVert_{2},\lambda_{0}^{-1},\log(1/\delta)\right)$,
then with probability at least $1-\delta/2$, for all $p\in[2]$ and $l\in[L]$,
we have

$\sup_{t\geq
0}\left\lVert\boldsymbol{W}^{(p,l)}_{t}-\boldsymbol{W}^{(p,l)}_{0}\right\rVert_{F}=O(m^{1/4}),\quad\sup_{t\geq
0}\left\lVert\boldsymbol{V}^{(p,l)}_{t}-\boldsymbol{V}^{(p,l)}_{0}\right\rVert_{F}=O(m^{1/4}).$

Since $\|\boldsymbol{x}\|_{2}=1$, we have an $\varepsilon$-net
$\mathcal{N}_{\varepsilon}$ of $\mathcal{X}$ such that the cardinality
$|\mathcal{N}_{\varepsilon}|=O(\varepsilon^{-(d-1)})$. We choose
$\varepsilon={1}/{m^{2^{L}}}$ and thus $\log|\mathcal{N}_{\varepsilon}|=O(\log
m)$. Denote
$B_{\boldsymbol{z}}(\varepsilon)=\\{\boldsymbol{x}\in\mathbb{S}^{d-1}:\|\boldsymbol{x}-\boldsymbol{z}\|_{2}\leq\varepsilon\\}$.
Then, fixing
$\boldsymbol{z},\boldsymbol{z}^{\prime}\in\mathcal{N}_{\varepsilon}$, for any
$\boldsymbol{x}\in B_{\boldsymbol{z}}(\varepsilon)$ and
$\boldsymbol{x}^{\prime}\in B_{\boldsymbol{z}^{\prime}}(\varepsilon)$, we have

$\displaystyle\lvert
r_{t}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-r(\boldsymbol{x},\boldsymbol{x}^{\prime})\rvert\leq\lvert
r_{0}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})-r(\boldsymbol{z},\boldsymbol{z}^{\prime})\rvert+\lvert
r(\boldsymbol{z},\boldsymbol{z}^{\prime})-r(\boldsymbol{x},\boldsymbol{x}^{\prime})\rvert$
$\displaystyle+\lvert
r_{t}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-r_{0}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})\rvert$

Then, noticing that $r^{m}_{t}=\left(r^{(1),m}_{t}+r^{(2),m}_{t}\right)/2$, we
control the four terms on the right hand side by Corollary 7.2, Proposition
7.25 and 7.24 respectively. We have shown that

$\displaystyle\lvert
r_{0}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})-r(\boldsymbol{z},\boldsymbol{z}^{\prime})\rvert\leq
O(m^{-0.2}),\qquad~{}\lvert
r(\boldsymbol{x},\boldsymbol{x}^{\prime})-r(\boldsymbol{z},\boldsymbol{z}^{\prime})\rvert\leq
O({1}/{m}),$ $\displaystyle\sup_{t\geq 0}\sup_{\boldsymbol{x}\in
B_{\boldsymbol{z}}(\varepsilon)}\sup_{\boldsymbol{x}^{\prime}\in
B_{\boldsymbol{z}^{\prime}}(\varepsilon)}|r_{t}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-r_{0}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})|\leq
O\left(m^{-{1}/{12}}\sqrt{\log m}\right),$

with probability at least
$1-\delta/\left(2|\mathcal{N}_{\varepsilon}|^{2}\right)$ if $m\geq
C_{1}\log\left(C_{2}|\mathcal{N}_{\varepsilon}|^{2}/\delta\right)^{5}$ for
some positive absolute constants $C_{1}>0$ and $C_{2}\geq 1$. There exists a
polynomial $\mathrm{poly}_{2}(\cdot)$, such that when
$m\geq\mathrm{poly}_{2}\left(\log(1/\delta)\right)$, we have $m\geq
C_{1}\log\left(C_{2}|\mathcal{N}_{\varepsilon}|^{2}/\delta\right)^{5}$, since
$\log|\mathcal{N}_{\varepsilon}|=O(\log m)$. By applying the union bound for
any pair $\boldsymbol{z},\boldsymbol{z}^{\prime}\in\mathcal{N}_{\varepsilon}$,
we have with probability at least $1-\delta$, we have

$\displaystyle\sup_{t\geq
0}\sup_{\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}}\lvert
r_{t}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-r(\boldsymbol{x},\boldsymbol{x}^{\prime})\rvert\leq
O\left(m^{-{1}/{12}}\sqrt{\log m}\right)$

if
$m\geq\mathrm{poly}_{1}\left(n,\left\lVert\boldsymbol{y}\right\rVert_{2},\lambda_{0}^{-1},\log(1/\delta)\right)+\mathrm{poly}_{2}(\log(1/\delta))$.

∎

##  8 Proofs in Section 2 and Section 4

###### Proof of Lemma 2.1.

For any $\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathbb{S}^{d-1}$, we have
the following decomposition of the NTK,

$\displaystyle
r(\boldsymbol{x},\boldsymbol{x}^{\prime})=\sum_{k=0}^{\infty}\mu_{k}\sum_{h=1}^{N(d,k)}Y_{k,h}(\boldsymbol{x})Y_{k,h}(\boldsymbol{x}^{\prime}),$

where $Y_{k,h}$, $h=1,..,N(d,k)$ are spherical harmonic polynomials of degree
$k$ and

$\displaystyle N(d,k)=\frac{\Gamma(k+d-2)}{\Gamma(d-1)\Gamma(k)}.$

By Stirling approximation, $\Gamma(x)=Cx^{x-1/2}\exp(-x)(1+O(\frac{1}{x}))$.
Therefore, $N(d,k)$ is the order of $k^{d-2}$ and

$\displaystyle\lambda_{j}=\mu_{l},\quad\sum_{i=1}^{l-1}N(d,2i)\leq
j\leq\sum_{i=1}^{l}N(d,2i),$

i.e., $\lambda_{j}\asymp\mu_{l}$ for $j\in[(2l-2)^{d-1},(2l)^{d-1}]$. By
Theorem 4.3 of [3], the non-negative eigenvalues $\mu_{k}$ satisfy
$\mu_{k}\asymp k^{-d}$, which implies $\lambda_{j}\asymp j^{-\frac{d}{d-1}}$.

∎

###### Proof of Theorem 4.1.

######  Proposition 8.1 (Corollary 4.4 in [24]).

Suppose Assumption 1 holds. For any given $\delta\in(0,1)$, if the training
process is stopped at $t_{*}\propto n^{\frac{d}{2d-1}}$ for the NTK
regression, then for sufficiently large $n$, there exists a constant $C$
independent of $\delta$ and $n$, such that

$\mathcal{E}(f_{t_{*}}^{NTK})\leq
Cn^{-\frac{d}{2d-1}}\log^{2}\frac{6}{\delta}$

holds with probability at least $1-\delta$.

Setting $\epsilon=Cn^{-\frac{d}{2d-1}}\log^{2}\frac{6}{\delta}$ in Theorem 3.1
yields

$\displaystyle\mathcal{E}(f_{t_{*}}^{m})$
$\displaystyle\leq|\mathcal{E}(f_{t_{*}}^{m})-\mathcal{E}(f_{t_{*}}^{NTK})|+\mathcal{E}(f_{t_{*}}^{NTK})$
$\displaystyle\leq 2Cn^{-\frac{d}{2d-1}}\log^{2}\frac{6}{\delta}.$

∎