# Weak Human Preference Supervision
For Deep Reinforcement Learning

Zehong Cao, KaiChiu Wong, Chin-Teng Lin, Z. Cao is with the School of
Information and Communications Technology (ICT), University of Tasmania,
Australia. (E-mail: zehong.cao@utas.edu.au.)K. Wong was with the University of
Tasmania and is now with the MyState Bank, Australia.C.T. Lin is with the
Australian Artificial Intelligence Institute (AAII) and the School of Computer
Science, University of Technology Sydney, Australia.Manuscript received on 27
July, 2020; revised on 06 December, 2020.

###### Abstract

The current reward learning from human preferences could be used to resolve
complex reinforcement learning (RL) tasks without access to a reward function
by defining a single fixed preference between pairs of trajectory segments.
However, the judgement of preferences between trajectories is not dynamic and
still requires human input over thousands of iterations. In this study, we
proposed a weak human preference supervision framework, for which we developed
a human preference scaling model that naturally reflects the human perception
of the degree of weak choices between trajectories and established a human-
demonstration estimator via supervised learning to generate the predicted
preferences for reducing the number of human inputs. The proposed weak human
preference supervision framework can effectively solve complex RL tasks and
achieve higher cumulative rewards in simulated robot locomotion – MuJoCo games
– relative to the single fixed human preferences. Furthermore, our established
human-demonstration estimator requires human feedback only for less than 0.01%
of the agent’s interactions with the environment and significantly reduces the
cost of human inputs by up to 30% compared with the existing approaches. To
present the flexibility of our approach, we released a video
(https://youtu.be/jQPe1OILT0M) showing comparisons of the behaviours of agents
trained on different types of human input. We believe that our naturally
inspired human preferences with weakly supervised learning are beneficial for
precise reward learning and can be applied to state-of-the-art RL systems,
such as human-autonomy teaming systems.

###### Keywords:

Deep Reinforcement Learning, Weak Human Preferences, Scaling, Supervised
Learning.

##  I Introduction

Reinforcement learning (RL) [1] typically uses a reward function to train an
agent’s behaviours for a specified task. Nevertheless, constructing an
effective reward function in complicated scenarios can often be challenging.
If the design of a reward function is too simple, then the behaviours of the
trained agent may not match our expectations, i.e., the results may exhibit
misalignment between our expectations and the actual testing [2]. To achieve
more effective RL, having a communication pathway between the RL agent and our
expectations during the training process is valuable [3].

In autonomous vehicle research, robotic controls with RL have already
demonstrated tremendous potential in improving transportation systems for
related problems such as localisation, path planning, and collision avoidance
[4] [5]. Investigating human-autonomy teaming using RL can enable the
development of a reliable reward function in the human-robot interaction
process. Some recent work showed challenges in training an intelligent robot
to complete task objectives [6] [7] [8] and in multi-agent interactions [9]
[10], addressing the difficulties of alignment between human expectations and
the final training outcome. Although approaches such as inverse RL [11] and
imitation learning [12] were suggested to extract the reward function and
mimic the actions of human experts to ensure an expected outcome, these
approaches are not direct enough to train the desired behaviour. Moreover, the
degree of movement of a robot could be larger than that of a human, as a human
demonstration for imitation learning may not be available in some cases [13].

A novel study proposed by the DeepMind group [14] first addressed deep RL from
human preferences, in which a comparison measurement between pairs of
trajectory segments was designed to replace the reward function and preference
inputs from an expert were allowed, as shown in Figure 1. This approach
requests advice from an expert to ensure that the RL training is on the
correct track, implying that agents could be assisted when tackling problems
in some highly complicated scenarios. However, the judgement of preferences
between trajectories is not dynamic. For example, the candidate preferences
include only fixed left, right, or equal options, represented by the
preference values 1, 0, and 0.5, respectively; thus, we assume that this
approach cannot reflect natural human intentions. In addition, the current
approach still requires human input over thousands of iterations, which
requires a substantially large amount of time from humans.

Figure 1: Illustration of Deep RL from Human Preferences

Inspired by the above DeepMind study and the uncertainties in decision making
[14] [15], in this study, we propose a new framework: weak human preference
supervision for deep RL. In particular, we develop a scaling model to support
dynamic and weak human preferences, instead of single fixed preferences, for
RL. Moreover, we use a database of human preference scaling values to
establish a human-demonstration estimator via supervised learning to predict
the preference scaling values based on initial human inputs to reduce the
amount of human effort.

The contributions of our weak human preference supervision framework for RL
are as follows:

  1. 1.

Our proposed weak human preference supervision for deep RL allows humans to
input dynamic and weak preference levels via our developed human preference
scaling model to reflect human behaviour and decrease the number of human
inputs for our established human-demonstration estimator.

  2. 2.

Based on 5 experiments with the robotic physical simulator MuJoCo [16], our
developed human preference scaling model for RL can achieve higher cumulative
reward values than those of the current fixed human preference model, and our
established human-demonstration estimator support for RL can reduce the amount
of human input for dynamic and weak preferences by up to 30% without
significantly sacrificing the reward values.

The rest of this paper is organised as follows. The related work is briefly
introduced in Section II. Then, the preliminaries and our proposed framework
are illustrated in Section III. Afterwards, experiments involving MuJoCo games
and the relevant settings are addressed in Section IV. Finally, we present our
findings and comparison results in Section V and conclude this work in Section
VI.

##  II Related Work

###  II-A Preference Learning

An agent may often not be able to learn expected actions from rewards when
using the traditional RL strategy, but preference learning can potentially
minimise the gap between the missing agent information and the behaviour
desired by humans. A recent study [17] stated that preference learning could
facilitate the adaptation of robotic movement and noted that the human
demonstration is particularly easy for task-dependent goals. An earlier study
[18] also showed that human preferences are more effective in acquiring better
actions than are agent rewards in RL. They implied that the feedback from a
human could leverage RL in qualitative policy models and that manipulation
from preference learning could be a new strategy to assist agents in achieving
the desired human behaviour in robotic control.

Additionally, [19] provided a human behaviour decision model to increase the
accuracy in preference learning, but it focused only on adjusting the attitude
and the importance of relative criteria without improving the human preference
coverage. Another recent work [20] developed a DemPref model to provide
efficient preference-based learning in robotic movements, but this approach
requires collecting a large number of purely human-demonstrated actions prior
to training.

###  II-B Learning by Pairwise Comparisons

Learning by pairwise comparisons allows the application of human preferences
to RL. Fürnkranz’s work [18] revealed that the preferences could help an agent
carry out label ranking in RL so that humans could provide feedback to the
agent. To distinguish between preference learning and RL, a survey study [21]
clarified that an agent can receive feedback from two options in preference
learning, while in RL, only one human feedback option is accepted. This
restriction facilitates RL agent label ranking when performing a task.

$z_{i}\succ z_{j}$ indicates that $z_{i}$ is the preferred choice over
$z_{j}$, where $\mathit{Z}$ represents a set of options. Kreps [22] offered
some notations that could be defined from preference learning while comparing
a pair of options:

  * •

$z_{i}\succ z_{j}$: option $z_{i}$ is absolutely preferred.

  * •

$z_{i}\prec z_{j}$: option $z_{j}$ is absolutely preferred.

  * •

$z_{i}\sim z_{j}$: options $z_{i}$ and $z_{j}$ are the same, as no preferred
option can be distinguished.

  * •

$z_{i}\succeq z_{j}$: option $z_{i}$ is weakly preferred.

  * •

$z_{i}\preceq z_{j}$: option $z_{j}$ is weakly preferred.

###  II-C RL from Human Preferences

To link preference learning to RL, according to the communication pathway
proposed by Christiano [14], the basic flow of RL from human preferences
comprises three main modules: agent, preference interface, and reward
predictor. The agent continually trains and explores the environment as RL
progresses. The novelty of the communication pathway is the addition of a
preference interface, which randomly generates some episodes in which human
judgement is requested. An expert therefore inputs which options he/she
prefers by inputting the preference database into the preference interface.
These preferences are sent to a reward predictor to perform further training
to assess the relative rewards from these preferences. These data are then
used return the trained preferences as the agent’s observations to perform the
policy training.

###  II-D Motivations

The settings of Christiano’s study [14] cover only three conditions among the
definitions of preference learning from Kreps [22], i.e., $z_{i}\succ z_{j}$,
$z_{i}\prec z_{j}$ and $z_{i}\sim z_{j}$. Christiano’s study did not consider
$z_{i}\succeq z_{j}$ and $z_{i}\preceq z_{j}$, which are two weak but
important conditions we encounter in real-life decision making based on
preferences. This lack motivates us to develop a new RL-based human preference
setup to cover the weak preference conditions $z_{i}\succeq z_{j}$ and
$z_{i}\preceq z_{j}$.

Furthermore, Christiano’s study [14] required a large number of human
preference labels, which may require a long period of time dedicated to human
inputs. In particular, at least 5,500 human inputs are required in the
training setup. We assume that some human preference labels may not be
accurate, as a human may experience a high level of fatigue, potentially
resulting in an increase in the error rate after a long period of performing
the preference judgement task. This problem motivates us to develop a human-
demonstration estimator via supervised learning to reduce the number of human
inputs and improve learning performance.

##  III Preliminaries and Methods

###  III-A Settings and Goal

An RL agent interacts with the environment for a number of steps, during which
the agent inspects the environment according to the observation $o_{t}\in O$,
receives an instant reward $r$ at each timestep $t$ and then performs action
$a_{t}\in A$ based on the observation. The agent aims to maximise the
cumulative rewards during the training and receives the predicted instant
reward values during each timestep $r_{t}\in R$ via the reward predictor and
preference interface modules. When the agent takes an action in the
environment, a video clip from a trajectory segment is pushed into the list in
the preference interface. The preference interface module randomly draws two
video clips from the list and asks a human which clip he/she would prefer.
Once the human inputs his/her preference, this information is passed to the
reward predictor to generate predicted rewards for the agent for training.

In this study, we follow the preference interface design from Christiano’s
work [14], which accepts the generated segments from the RL agent and places
them into a queue, as shown in Figure 1. Two segments are randomly selected
from the queue, and the preference interface asks a human for his/her
preference between the two candidate options. After the preference interface
collects the preferred option from the human, this option is saved in the
preference queue of the reward predictor for the later training of RL
policies. Because the currently used approach accepts only a fixed preference,
i.e., left, right or equal, as its input, it lacks dynamic inputs of the
preferred range. In this study, we modify the preference interface design to
consider weak human preference conditions and propose a synthetic preference
scaling model, as shown in the following section.

###  III-B Weak Human Preferences: Synthetic Preference Scaling

In this study, we assume that the human always chooses the trajectory segment
that has the most potential to return a high reward value; thus, we use the
synthetic oracle, a Bayesian approach for policy learning from trajectory
preference queries, to mimic the preference of the human, whose preference
over several trajectories precisely reflects the reward [23]. For the
synthetic human preference, when the agent queries for comparisons, the
synthetic human can immediately reply by indicating a preference for whichever
trajectory segment yields a higher reward in the underlying task.

Based on the synthetic human preference [23], we develop a weak human
preference model called synthetic preference scaling, as presented in
Algorithm 1.

Algorithm 1 Weak Human Preferences: Synthetic Preference Scaling

0: synthetic preference scaling represented as $\widehat{z}$.

0: $\widehat{z}$ from a given reward set ($R_{left}$, $R_{Right}$) in the
range [0.0, 1.0], where equal preference corresponds to a value of 0.5.

0: $R_{left}$, the reward of the left trajectory segment.

0: $R_{right}$, the reward of the right trajectory segment.

0: $R$, the reward list composed of all $n$ reward sets.

0: $\widehat{z}$

1:
$R\leftarrow\left[R_{left_{1}},R_{right_{1}},R_{left_{1}},R_{right_{1}},...,R_{left_{n}},R_{right_{n}}\right]$

2: sort($R$), sort the list, in ascending order by default.

3: $N\leftarrow$ number of elements in $R$.

4: $R_{min}\leftarrow\left(\left\lceil\frac{10}{100}\times
N\right\rceil\right)^{th}$ element from $R$.

5: $R_{max}\leftarrow\left(\left\lceil\frac{90}{100}\times
N\right\rceil\right)^{th}$ element from $R$.

6: if ($R_{left}>R_{right}$) then

7: normalise $\widehat{R}_{left}\leftarrow
max\left(0,min\left(\frac{R_{left}-R_{min}}{R_{max}-R_{min}},1\right)\right)$

8: $\widehat{z}\leftarrow 0.5+0.5\times\widehat{R}_{left}$

9: else if ($R_{left}<R_{right}$) then

10: normalise $\widehat{R}_{right}\leftarrow
max\left(0,min\left(\frac{R_{right}-R_{min}}{R_{max}-R_{min}},1\right)\right)$

11: $\widehat{z}\leftarrow 0.5-0.5\times\widehat{R}_{right}$

12: else

13: $\widehat{z}\leftarrow 0.5$

14: end if

15: return $\widehat{z}$

We elaborate on the proposed Algorithm 1 in the following. Because the range
of ${z}$ is set as [0.0, 1.0], a ${z}$ value of 1.0 means that the human
absolutely prefers the left trajectory segment, while a ${z}$ value of 0.0
means that the human absolutely prefers the right trajectory segment. A ${z}$
value of 0.5 indicates that the human cannot judge between the two trajectory
segments. For preference scaling, the reward list $R$ is collected in the
memory in each iteration, and the synthetic preferences are calculated based
on the reward values with a normalisation measurement. In particular, based on
the 90% confidence interval level, from the sets in the reward list $R$, we
first remove the lowest 10% and highest 10% of reward values to ensure that
outliers or anomalous reward values will not affect the preference scaling
calculation. Then, all collected reward values are normalised to values
between 0.0 and 1.0, and all sets in the reward list $R$ are ranked in
ascending order.

###  III-C Human Preference Scaling for Deep RL

Following the basic preference settings for RL as addressed in Section III-A,
at each time $t$, we maintain the policy $\pi$ :
$\mathit{O}\rightarrow\mathit{A}$, where the agent interacts with the
environment according to observation $o_{t}\in\mathit{O}$ and then performs
particular action $a_{t}\in\mathit{A}$ based on instant observation $o_{t}$.
During the training, the agent tries to estimate the reward function
$\widehat{r}$ : $\mathit{O}\times\mathit{A}\rightarrow\mathit{R}$ from a deep
neural network, which is updated as follows:

  1. (1)

A set of trajectories $\left\\{\gamma^{1},\gamma^{2},...,\gamma^{i}\right\\}$
is generated by policy $\pi$. The parameters of policy $\pi$ are updated by
the traditional RL to ensure that the maximum sum of predicted rewards
$r_{t}=\widehat{r}\left(o_{t},a_{t}\right)$ that could be achieved from
observation $o$ and action $a$ is obtained.

  2. (2)

A pair of segments $\left(\sigma^{1},\sigma^{2}\right)$ is randomly selected
from a set of trajectories
$\left\\{\gamma^{1},\gamma^{2},...,\gamma^{i}\right\\}$. This pair of segments
is sent to the preference interface and allows the human to perform the
comparison.

  3. (3)

Based on Algorithm 1, the preference scaling $z$ is collected from the human
and linked to the pair of segments $\left(\sigma^{1},\sigma^{2}\right)$.

Please note that the above updating processes occur in the asynchronous mode:
process (1) passes the trajectories
$\left\\{\gamma^{1},\gamma^{2},...,\gamma^{i}\right\\}$ to process (2),
process (2) passes the human preferences to process (3), and process (3)
passes the parameters of $\widehat{r}$ back to process (1).

Figure 2: Proposed (A) Human Preference Scaling Model and (B) Human-
Demonstration Model for Deep RL

#### Preference Elicitation

In Figure 2-A, we show a human preference scaling structure for the RL agent
to make these processes easily understandable. To reflect natural human
intent, we modify the format of human preferences from fixed preferences to
scale-based preferences in process (3). In terms of the current fixed
preferences for a pair of segments [14] (as shown in Figure 1), this approach
allows inputting only the left, right or equal option, and the judgement is
saved in the preference database $D$ with the data format
$(\sigma^{1},\sigma^{2},{z})$, where $\sigma^{1}$ and $\sigma^{2}$ are the
extracted paired segments and ${z}=[{0,0.5,1}]$ is the fixed preference input
from the human. Thus, the approach does not provide information regarding how
much a human prefers a particular segment. For example, the left segment could
be better than the right segment, but the left one may not be perfect.

Our proposed scale-based preferences provide a scaling model (as shown in
Algorithm 1) with which the human can input a dynamic score for the preferred
segment by assigning any value between 0.0 and 1.0. The value of $\widehat{z}$
could be in the range of $\left\\{0.0,1.0\right\\}$ to specify the dynamic
judgement of the human. If $\widehat{z}$ is input as 0.0, then the condition
of $\sigma^{1}$ is absolutely preferred, while if $\widehat{z}$ is input as
1.0, then the condition of $\sigma^{2}$ is absolutely preferred. A
$\widehat{z}$ value of 0.5 indicates that $\sigma^{1}$ and $\sigma^{2}$ are
not different; hence, the above conditions do not hold. Then, we can further
address the additional conditions, which are in the weakly preferred
categories. To be more specific, any values between 0.0 and 0.5 (excluding the
margin values 0.0 and 0.5) indicate that $\sigma^{1}$ is weakly preferred,
while any values between 0.5 and 1.0 (excluding the margin values 0.5 and 1.0)
indicate that $\sigma^{2}$ is weakly preferred. For example, a human could
input a preference value of 0.87 or any value he/she likes in the range
between 0.0 and 1.0 to specify that they weakly prefer the left or right
segment. Our contribution aims to supply more accurate information regarding
the human preferences to the RL agent, not simply indicating whether the
chosen option is better than the other but rather indicating how much better
it is.

#### Fitting the Reward Function

If the reward function estimate $\widehat{r}$ is the predicted reward from the
reward predictor, as shown in Figure 2-A, then we consider $\widehat{r}$ as a
latent factor explaining the human judgements and assume that the human
probability of preferring a segment $\sigma$ depends exponentially on the
value of the latent reward summed over the length of the clip, which follows
Christiano’s design process [14], as follows.

$\hat{P}\left[\sigma^{1}\succ\sigma^{2}\right]=\frac{\exp\sum\hat{r}\left(o_{t}^{1},a_{t}^{1}\right)}{\exp\sum\hat{r}\left(o_{t}^{1},a_{t}^{1}\right)+\exp\sum\hat{r}\left(o_{t}^{2},a_{t}^{2}\right)}$

$\widehat{r}$ minimises the cross-entropy loss between these predictions and
the actual labels of human inputs:

$\operatorname{loss}(\hat{r})=$
$-\sum_{\left(\sigma^{1},\sigma^{2},\widehat{z}\right)\in\mathcal{D}}\widehat{z}(1)\log\hat{P}\left[\sigma^{1}\succ\sigma^{2}\right]+\widehat{z}(2)\log\hat{P}\left[\sigma^{2}\succ\sigma^{1}\right]$

#### Optimising the Policy

After the reward function $\widehat{r}$ computes the rewards, we can meet the
need for traditional RL. As the reward function, $\widehat{r}$ may be non-
stationary, which leads us to prefer RL algorithms that are robust to changes
in the reward function, such as policy gradient methods [24]. In this study,
we use proximal policy optimisation (PPO) [25] to perform simulated robotics
tasks and apply the same parameter settings as in Christiano’s work [14].

###  III-D Human Preference Supervision: Human-Demonstration Estimator for
Deep RL

Because a large number of human preference scaling values (generally over
1,000 preference inputs) must be stored in the preference database to train
the fitting of predicted rewards, we assume that reducing the number of human
preference inputs by training a preference estimator is worthwhile. As shown
in Figure 2-B, we develop a preference estimator based on the previous human
inputs and use a regression model with supervised learning that we call the
human-demonstration estimator to predict some of the human preferences. We
expect this human-demonstration estimator to not only reduce the number of
human inputs $n$ but also maintain good performance without sacrificing the
cumulative rewards.

The human-demonstration estimator is an extended version of the previous human
preference scaling for deep RL presented in Section III-C. In particular, the
collected database includes $n$-fold preference scalings of a preference
estimator based on previous human inputs, and a regression model with
supervised learning that we call the human-demonstration estimator is used to
predict some of the human preferences with the data format
$(\sigma^{1},\sigma^{2},\widehat{z})$, as discussed earlier. Specifically, the
initial preferences are collected at the initial stage and stored in the
preference queue. These preferences are used as the base of the preference
estimation. In our study, two reliable supervised learning models, i.e.,
linear regression and support vector regression (SVR) with a radial basis
function (RBF) kernel, are considered as the estimator to predict the human
preference based on the collected initial preferences. To construct a
prediction model and fit the parameters of the human preference scaling
estimator, the database is separated into two parts, i.e., a training dataset
and a testing dataset, and we implement two types of data splitting: i) 50%
training data and 50% testing data and ii) 70% training data and 30% testing
data. As a result, 30-50% of the human inputs will be replaced by the agent’s
estimation.

With linear regression, the objective function for ordinary least squares with
one preferred segment $\sigma$ in the set $(\sigma^{1},\sigma^{2})$ is as
follows:

$\operatorname{Min}\sum_{i=1}^{n}\left(\widehat{z}^{\prime}_{i}-w_{i}\sigma_{i}\right)^{2}$

where $\widehat{z}^{\prime}_{i}$ is the estimated preference scaling value and
$w_{i}$ is the coefficient.

SVR gives us the flexibility to define errors and finds an appropriate
hyperplane in higher dimensions to fit the data. The objective function of SVR
is to minimise the coefficients: the l2-norm of the coefficient vector. The
error term is instead handled in the constraints, where we set the absolute
error less than or equal to a specified margin, called the maximum error
$\varepsilon$. We can tune $\varepsilon$ to gain the desired accuracy of our
model. The updated objective function of SVR and the constraints are as
follows:

Minimise:

$\operatorname{Min}\frac{1}{2}\|\boldsymbol{w}\|^{2}$

Constraints:

$\left|\widehat{z}^{\prime}_{i}-w_{i}\sigma_{i}\right|\leq\varepsilon$

where $\widehat{z}^{\prime}_{i}$ is the estimated preference scaling value and
$w_{i}$ and $\sigma_{i}$ are the coefficients and the preferred segment,
respectively.

To evaluate the performance of the estimators, the mean squared error (MSE) is
applied to measure the average of the squares of the errors, i.e., the average
squared difference between the estimated preference scaling values
$\widehat{z}^{\prime}$ and the ground truth of preference scaling
$\widehat{z}$.

##  IV Experiment

We implemented the existing models and our proposed models for deep RL and
performed experiments in 5 scenarios from MuJoCo [26] with TensorFlow [27]
under the OpenAI Gym platform [28]. The collected results were consolidated
under the TensorBoard package from TensorFlow.

###  IV-A Robotic Control Scenarios

OpenAI Gym provides baseline environments to train the agent on the RL
algorithms [28]. MuJoCo is one of the popular continuous control tasks in
OpenAI Gym, with a physics engine that can be used to simulate model-based
control [16]. MuJoCo [26] contains diverse scenarios with robot control, where
the agent moves different joints with continuous control instead of
intermittent control to achieve a particular goal [29]. The agent performs
different types of actions to achieve the maximum cumulative reward value to
reach the target goal. This process could be challenging, as the MuJoCo
environment involves high exploration dimensions for the agent.

TABLE I: List of 5 MuJoCo Scenarios MuJoCo Scenario | Observation |  Task Summary
---|---|---
Walker | (18, 6, 24) |  A planar walker tries to roll forward and walk as quickly as possible. The reward depends on the velocity $v$ and the torso height $h$.
Hopper | (14, 4, 15) |  A one-legged robot is required to move forward and attain as high a torso height as possible. The reward depends on the velocity $v$ and the torso height $h$.
Swimmer | (10, 2, 13) |  A robot tries to reach a random target by swimming. The reward is given when the nose of the robot touches the random target.
Ant | (29, 8, 67) |  A 4-legged robot attempts to learn to walk as quickly as possible. The reward is based on the velocity $v$ and the body height $h$.
Cheetah | (18, 6, 17) |  A robot has to learn to move forward as quickly as possible. The reward $R$ is based on the velocity $v$, the formula for which is $R(v)=max\left(0,min\left(\frac{v}{10},1\right)\right)$.

As shown in Table I, in this study, our testing environments include 5
scenarios: Walker, Hopper, Swimmer, Cheetah, and Ant. The existing approaches,
such as traditional RL (PPO) and RL from human preferences (RLHP), and our
proposed weak human preference supervision framework composed of two models,
i.e., 1) weak human preferences: RL from human preference scaling (RLHPS) and
2) human preference supervision: RL from human preference scaling with
demonstrations (RLHPS with Demo), are applied to compare their performances in
these 5 scenarios.

###  IV-B Parameter Settings

Generally, in the policy gradient strategy, e.g., PPO, the agent starts with
the initial policy, interacts with the environment, obtains a predicted reward
from human feedback or from using the pre-defined reward function, and then
uses the reward to improve the policy. Here, we need to know how many
transitions (sequences of states, rewards, and actions) the agent should
gather before updating the policy and how to use the transitions for updating
under the new policy.

First, we need to address the collection of experience (horizon, mini-batches,
and epochs) prior to updating the policy. For example, PPO collects
trajectories up to the time horizon ($T$) limit and then performs a minimum
batch size stochastic gradient descent (SGD) update on all collected
trajectories within a specified epoch. Second, to update the new policy from
the old policy, PPO uses a surrogate loss function to keep the step from the
old policy to the new policy within a safe range; here, consideration of the
discount factor $\gamma$ and the GAE parameter $\lambda$ is necessary. In
addition, the remaining parameters are general hyperparameters that can be
used in many deep learning experiments to determine, e.g., the learning rate,
number of steps, and number of hidden units. In this study, the experiments in
the MuJoCo scenarios are trained for $3\times 10\textsuperscript{7}$ timesteps
over 10 iterations. All MuJoCo scenarios are trained under the PPO strategy
with or without human feedback with the hyperparameters given in Table II.

TABLE II: Hyperparameters of PPO used in MuJoCo Scenarios Hyperparameter |  Value
---|---
Horizon ($T$) |  2048
Mini-batch size |  64
Number of epochs |  10
$\gamma$ |  0.99
GAE parameter ($\lambda$) |  0.95
Adam step size |  $3\times 10\textsuperscript{-4}$
Learning rate |  $1\times 10\textsuperscript{-4}$
Number of steps |  $3\times 10\textsuperscript{7}$
Number of hidden units |  64

###  IV-C Baselines

#### Traditional RL

The baseline of each scenario is training with the traditional RL (PPO)
without any human involvement. The agent has to learn, based on the scenario
goal, only from the rewards they receive. The learning performance is the same
as that of the traditional RL process and relies on the design of the reward
function of each scenario. The details of the reward design of each scenario
are specified in Table I. Our goal for this setup is to set the baseline
algorithm and evaluate the performance in each scenario to check what reward
values could be achieved without human input.

#### RL from Human Preferences (RLHP)

We consider RLHP as another baseline that contains the basic human preferences
to replicate the results under advice from a human [14]. The experimental
setup emphasises a preference interface to ask for human preferences, and the
user interface shows the rewards and the video clip information to let each
human input a large number of preferences. The interface allows the user to
input either a left, right or equal option into the preference interface.

##  V Results

In this study, 5 scenarios (Walker, Hopper, Swimmer, Cheetah and Ant) are used
as our experimental environments to evaluate the training performance among 4
types of RL model by comparing the traditional RL baselines (without human
preferences), i.e., PPO and RLHP, with our two proposed models, i.e., RLHPS
and RLHPS with Demo. The RL algorithms involved in this study are summarised
in Table III, where human preferences require an input of 700 to 1,400 labels,
which correspond to less than 0.01% of the training timesteps.

TABLE III: Summary of the RL Algorithms RL Type | Algorithm |  | No. of Inputs
---
(1)
| No. of Inputs
---
(2)
Note
RL without Human Inputs | Traditional RL (PPO) | N/A | N/A |
| RLHP | 1,400 | 700 | RL from human preferences.
RL with Human Inputs (Preferences) | RLHPS (ours) | 1,400 | 700 | RL from human preference scaling.
| RLHPS with Demo (ours) | 980 | 700 |  | RL from human preference scaling
---
with demonstrations;
30-50% of the 1,400 inputs (420-700 inputs)
are generated from the estimated preferences.

###  V-A RL from Human Preference Scaling (RLHPS)

Based on the experiments in the 5 MuJoCo scenarios, the performance in terms
of the cumulative reward values of the two baselines, i.e., the traditional RL
(PPO) and RLHP, and our proposed approach (RLHPS) are compared, as shown in
Figure 3, which presents the training of our agent by learning from two types
of human preference input (700 and 1,400 labels, amounting to less than 0.01%
of the training timesteps) for RLHP and our proposed RLHPS. The cumulative
reward values from our proposed RLHPS are always higher than those from RLHP
or PPO, except in the Hopper scenario, where all the RL algorithms achieve
similar reward values after $2\times 10\textsuperscript{7}$ timesteps. From
another perspective, the use of 1,400 human input labels generally yields
higher rewards than obtained from 700 human input labels, suggesting that more
human effort may benefit the training of a robust RL agent.

#### Cumulative Reward Values

Particularly in the Walker scenario, our proposed RLHPS can achieve an
approximately 1,500 higher reward value than the traditional RL PPO setup and
an approximately 1,000 higher reward value than RLHP for the case of 1,400
human preference inputs. For the Swimmer scenario, the reward learning from
RLHPS with the 1,400-label setup can achieve an approximately 350 reward value
at the end of the experiment, while RLHP with the 1,400-label setup can
achieve a reward value of only approximately 300 at the end of the experiment.
Both human preference setups (RLHP and RLHPS) are much better than the
traditional RL setup (PPO), as PPO achieves a reward value of only 150. In
terms of the Cheetah scenario, our proposed RLHPS can also acquire higher
rewards, a reward value of approximately 4,000, compared to the range of
3,000-3,500 when trained by RLHP and PPO.

Regarding the special case of the Ant scenario, complete three-dimensional
movement and observation are required for the robot to achieve learning.
Continuous movement of the agent is very difficult to achieve, as the ant
robot has to find a way to balance its body and walk. From our observation,
during the initial period of training, the robot does not know how to walk and
balance and always flips over, which causes the reward values in this period
to always be negative. The experimental results show that the scale-based
preferences, highlighted in red, could yield a good performance compared to
the fixed preferences. This outcome is good evidence that our proposed RLHPS
can attain higher rewards (either with 700 or 1,400 labels) and quickly
achieve positive reward values compared with RLHP or PPO.

---
Figure 3: Experimental Results of PPO, RLHP, and RLHPS in the 5 MuJoCo
Scenarios

#### Instant Reward Distributions

For our proposed RLHPS, we also investigated the instant reward distributions
between the initial and final training periods in the 5 MuJoCo scenarios. The
initial training period is that in which the human has not input a preference
label, generally within the first 300 timesteps. The final training period
includes the final 2,500-3,000 timesteps, during which the human inputs 1,400
preference labels and the RL agent is approaching completion of the training
process. This scenario was considered because the experimental setup requires
use of the initial stage (the initial training period) to generate segments
for the segment queue for the preference interface so that the agent can
perform the initial RL training before the preference interface can select
some segments from which the human can choose. We also intend to replicate the
performance from Christiano’s work [14] as our baseline; thus, our proposed
method uses exactly the same settings to contrast with the existing results.

As shown in Figure 4, the instant reward distributions are sampled for these
two training periods (initial vs. final) in the 5 MuJoCo scenarios. The blue
data distribution represents the beginning of training before acquiring any
preferences; hence, most of the instant rewards are still negative. The grey
data distribution shows the situation at the end of training, where the RL
agent can achieve more positive rewards from human preferences. Our findings
from the instant reward distributions confirm that our proposed RLHPS has a
positive effect on RL and that the agent can use self-management to learn the
values of the human preference scaling.

---
Figure 4: RLHPS: Instant Reward Distributions Between the Initial and Final
Training Periods in the 5 MuJoCo Scenarios

In summary, our findings show that the setting with human preference scaling
is always much better than the baseline with fixed human preferences, which
confirms that our scaling model enables the agent to learn in higher-
dimensional environments, as our setting did reflect natural human intent.
Additionally, from the comparison results of the instant reward distributions,
RLHPS is confirmed to have excellent training performance, as instant reward
values are made more favourable than those in the initial stages prior to the
agent receiving any preferences.

###  V-B RL from Human Preference Scaling with Demonstrations (RLHPS with
Demo)

---
Figure 5: Experimental Results of PPO, RLHPS, and RLHPS with Demo in the 5
MuJoCo Scenarios

After the experiments on RLHPS, we implemented the estimator interface to link
the preference interface and the human based on our proposed approach – RLHPS
with Demo. As addressed in Section III-D, we performed two types of data
splitting, with 30% and 50% of the data from the preference database used for
testing. Because 1,400 human preference inputs could achieve better
performance across the different scenarios according to the previous
experiment, we kept the same number of labels – 1,400 – to test the
performance of RLHPS with Demo. As shown in Figure 5, the experiment employing
RLHPS with Demo (30%) indicates that we can reduce the human preference inputs
by 30%; thus, humans need to input only 70% of the 1,400 (980) preference
labels, with the remaining 30% predicted by the regression model. The
experiment employing RLHPS with Demo (50%) aims to provide further
observations of the influence of reducing the number of human preferences on
the cumulative reward values, indicating that 50% of the 1,400 (700)
preference labels need to be input by the human, while 50% of the 1,400
preferences can be predicted by linear regression or the SVR model with the
smallest MSE, as shown in Table IV, which presents the prediction accuracies
achieved using the averaged MSE trained by linear regression or SVR (with the
RBF kernel) in the 5 scenarios.

#### Cumulative Reward Values

Figure 5 generally indicates that RLHPS with Demo (30% estimated human
preferences) can achieve similar or superior cumulative reward values compared
to the other approaches, i.e., RLHPS with Demo (50% estimated human
preferences) and RLHPS (without Demo), which excludes the human-demonstration
stage. For RLHPS with Demo (50% estimated human preferences), where we reduce
the number of human preference inputs by half, only a performance similar to
that of PPO can be achieved, far from the achievement when using RLHPS. The
main reason is that removing 50% of the human inputs will cause higher MSEs,
which may lead to a negative impact on training performance.

In terms of the Walker and Hopper scenarios, RLHPS with Demo (30% estimated
human preferences) yields the highest cumulative reward values. For the
Swimmer and Ant scenarios, RLHPS with and RLHPS without Demo have similar
performances, suggesting that we can employ 30% less human inputs to achieve
similar outcomes. Only in the Cheetah scenario was RLHPS with Demo unable to
achieve a comparable performance to that of RLHPS, suggesting that the
estimated preferences may not be of benefit to walking guidance for the
Cheetah scenario.

TABLE IV: MSEs of Preference Estimations | Linear Regression | SVR (RBF kernel)
---|---|---
Scenario | Mean | Standard | Mean | Standard
|  | Deviation |  | Deviation
Walker | 0.0514 | 0.0752 | 0.0099 | 0.0184
Hopper | 0.0688 | 0.0383 | 0.0122 | 0.0716
Swimmer | 0.0239 | 0.0397 | 0.0737 | 0.0665
Ant | 0.0356 | 0.0846 | 0.0637 | 0.1210
Cheetah | 0.0607 | 0.0769 | 0.0725 | 0.0870

Although the 30% reduction may not show a significant improvement in terms of
the percentage, it could reduce human input by a notable amount (from 1,400 to
980 inputs) without impacting the training performance. In short, it removes
the need for approximately 420 human inputs per experiment. Assuming that a
human needs 1 second per input on average, this reduction will amount to 7
minutes saved per experiment under the MuJoCo scenarios. A total of 25 minutes
per experiment could also be saved under the Atari scenarios. If we repeat the
experiments 25 times, we could save 175 minutes and 625 minutes for the MuJoCo
and Atari scenarios, respectively, which are significant time reductions when
considering complex scenarios.

###  V-C Observation of Testing Behaviours

We released a video (https://youtu.be/jQPe1OILT0M) to demonstrate the
behaviours of the trained agent in all MuJoCo scenarios. Generally, our
proposed method, RLHPS or RLHPS with Demo can perform more appropriate
behaviours to achieve the expected goal than can RLHP or PPO. In only a few
exceptional cases, the goal of the Walker scenario is for the agent to roll
forward and walk. Nevertheless, by observing the behaviour of the trained
agent, we find that the agent operated very slowly to achieve this goal. In
the Ant scenario, our RLHPS with Demo seemed to take more time to learn to
walk around than required by RLHP or PPO.

###  V-D Limitations

This study has some limitations. Our findings provide insights into some human
preference labels that could be generated by the prediction model, which could
reduce the number of human inputs without sacrificing the training performance
while maintaining an excellent reward return. However, this reduction process
is still limited. From the experimental results, when half of the human
preference labels are predicted, the training performance is dramatically
impacted. Therefore, under the current settings, using up to 30% of the
estimated preference inputs in place of human inputs can prevent this negative
impact and maintain the training performance.

Furthermore, the frame selections are made on a random basis, which may
influence the human preferences for some cases close to the equal option. We
suggest that this could be refined by having an intelligent selection model
select segments that have diverse rewards or at time points when the
prediction model is unable to judge between the two segments. In addition, the
normalisation step of our human preference scaling model could be further
investigated since the distribution of rewards could affect preference levels
for the estimator.

##  VI Conclusions

Our study proposed a weak human preference supervision framework involving a
human preference scaling model with demonstrations that aims to effectively
solve complex RL tasks and achieve higher cumulative rewards in simulated
robot locomotion – MuJoCo games. We attempted to optimise RLHP in two ways:
enhancement of the weak human preference details by scaling the preference
levels and reduction of the number of human preference inputs by replacing
some inputs with preference labels generated by an estimator. Remarkably, our
two developed models, RLHPS and RLHPS with Demo, achieve higher cumulative
reward values and significantly reduce the cost of human inputs up to 30%
compared to PPO and RLHP. To present the flexibility of our approach, the
released video shows comparisons of the behaviours of agents trained on
different types of human input.

Given the high scalability of deep RL, we believe that our proposed weak human
preference supervision framework, which includes RLHPS and RLHPS with Demo,
can help an agent learn natural human preferences with fewer inputs to enhance
the training performance. In this work, our contribution to the improvement of
RL-based robotic movement potentially approaches human thinking in more
complex situations and focuses on the new human-robot interaction scheme by
proposing a weak human preference supervision framework in deep RL for robotic
controls. Our breakthrough results are part of a broader core set of robotics
challenges concerning the deployment of automated driving systems.

## Acknowledgements

We thank Prof. Jun Wang (Department of Computer Science, University College
London, UK) and Prof. Haifeng Zhang (Institute of Automation, Chinese Academy
of Sciences, China) for providing suggestions to improve the presentation of
the manuscript. This work was supported in part by the CoSE incentive grant
scheme at the University of Tasmania and the US Office of Naval Research
Global, under Cooperative Agreement Number: ONRG-NICOP-N62909-19-1-2058.

## Appendix

The code of this paper can be found at GitHub
https://github.com/kaichiuwong/rlhps

## References

  * [1] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [2] S. Nikolaidis, S. Nath, A. D. Procaccia, and S. Srinivasa, “Game-theoretic modeling of human adaptation in human-robot collaboration,” in _Proceedings of the 2017 ACM/IEEE international conference on human-robot interaction_ , 2017, pp. 323–331.
  * [3] K. Bogert, J. F.-S. Lin, P. Doshi, and D. Kulic, “Expectation-maximization for inverse reinforcement learning with hidden data,” in _Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems_, 2016, pp. 1034–1042.
  * [4] Y. Lu, C. Wen, T. Shen, and W. Zhang, “Bearing-based adaptive neural formation scaling control for autonomous surface vehicles with uncertainties and input saturation,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2020.
  * [5] S. Xu and H. Peng, “Design, analysis, and experiments of preview path tracking control for autonomous vehicles,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 1, pp. 48–58, 2019.
  * [6] S. Russell, “Should we fear supersmart robots?” _Scientific American_ , vol. 314, no. 6, pp. 58–59, 2016.
  * [7] D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané, “Concrete problems in ai safety,” _arXiv preprint arXiv:1606.06565_ , 2016\.
  * [8] Z. Ke, Z. Li, Z. Cao, and P. Liu, “Enhancing transferability of deep reinforcement learning-based variable speed limit$\backslash$endgraf control using transfer learning,” _IEEE Transactions on Intelligent Transportation Systems_ , 2020.
  * [9] Z. Cao and C.-T. Lin, “Reinforcement learning from hierarchical critics,” _arXiv preprint arXiv:1902.03079_ , 2019.
  * [10] Z. Cao, K. Wong, Q. Bai, and C.-T. Lin, “Hierarchical and non-hierarchical multi-agent interactions based on unity reinforcement learning,” in _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ , 2020, pp. 2095–2097.
  * [11] A. Y. Ng and S. J. Russell, “Algorithms for inverse reinforcement learning,” in _Icml_ , vol. 1, Conference Proceedings, pp. 663–670.
  * [12] A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne, “Imitation learning: A survey of learning methods,” _ACM Computing Surveys (CSUR)_ , vol. 50, no. 2, pp. 1–35, 2017.
  * [13] Y. Schroecker and C. L. Isbell, “State aware imitation learning,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 2911–2920.
  * [14] P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei, “Deep reinforcement learning from human preferences,” in _Advances in Neural Information Processing Systems_ , 2017, Conference Proceedings, pp. 4299–4307.
  * [15] F. Xiao, Z. Cao, and A. Jolfaei, “A novel conflict measurement in decision making and its application in fault diagnosis,” _IEEE Transactions on Fuzzy Systems_ , 2020.
  * [16] E. Todorov, T. Erez, and Y. Tassa, “Mujoco: A physics engine for model-based control,” in _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, Conference Proceedings, pp. 5026–5033.
  * [17] B. Woodworth, F. Ferrari, T. E. Zosa, and L. D. Riek, “Preference learning in assistive robotics: Observational repeated inverse reinforcement learning,” in _Machine Learning for Healthcare Conference_ , 2018, pp. 420–439.
  * [18] J. Fürnkranz, E. Hüllermeier, W. Cheng, and S.-H. Park, “Preference-based reinforcement learning: a formal framework and a policy iteration algorithm,” _Machine learning_ , vol. 89, no. 1-2, pp. 123–156, 2012.
  * [19] M. Aggarwal and A. Fallah Tehrani, “Modelling human decision behaviour with preference learning,” _INFORMS Journal on Computing_ , vol. 31, no. 2, pp. 318–334, 2019.
  * [20] M. Palan, N. C. Landolfi, G. Shevchuk, and D. Sadigh, “Learning reward functions by integrating human demonstrations and preferences,” _arXiv preprint arXiv:1906.08928_ , 2019.
  * [21] C. Wirth, R. Akrour, G. Neumann, and J. Fürnkranz, “A survey of preference-based reinforcement learning methods,” _The Journal of Machine Learning Research_ , vol. 18, no. 1, pp. 4945–4990, 2017.
  * [22] D. Kreps, _Notes on the Theory of Choice_. Westview press, 1988.
  * [23] A. Wilson, A. Fern, and P. Tadepalli, “A bayesian approach for policy learning from trajectory preference queries,” in _Advances in neural information processing systems_ , 2012, pp. 1133–1141.
  * [24] J. Ho, J. Gupta, and S. Ermon, “Model-free imitation learning with policy optimization,” in _International Conference on Machine Learning_ , 2016, pp. 2760–2769.
  * [25] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [26] E. Todorov, T. Erez, and Y. Tassa, “Mujoco: A physics engine for model-based control,” in _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2012, pp. 5026–5033.
  * [27] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard _et al._ , “Tensorflow: A system for large-scale machine learning,” in _12th $\\{$USENIX$\\}$ symposium on operating systems design and implementation ($\\{$OSDI$\\}$ 16)_, 2016, pp. 265–283.
  * [28] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, “Openai gym,” _arXiv preprint arXiv:1606.01540_ , 2016.
  * [29] Y. Tassa, Y. Doron, A. Muldal, T. Erez, Y. Li, D. d. L. Casas, D. Budden, A. Abdolmaleki, J. Merel, and A. Lefrancq, “Deepmind control suite,” _arXiv preprint arXiv:1801.00690_ , 2018.


# Computing isogenies at singular points of the modular polynomial

William E. Mahaney and Travis Morrison

###### Abstract.

In this paper we present a method which, given a singular point
$(j_{1},j_{2})$ on $Y_{0}(\ell)$ with $j_{1},j_{2}\neq 0,1728$ and an elliptic
curve $E$ with $j$-invariant ${j_{1}}$, returns an elliptic curve
$\widetilde{E}$ with $j$-invariant ${j_{2}}$ that admits a normalized
$\ell$-isogeny $\phi\colon E\to\widetilde{E}$. The isogeny $\phi$ can then be
efficiently computed from $E$ and $\widetilde{E}$ using an algorithm of
Bostan, Morain, Salvy, and Schost.

##  1\. Introduction

For an elliptic curve $E$ defined over a field $k$, a separable isogeny
$\phi\colon E\to E^{\prime}$ is determined (up to post-composition with an
isomorphism) by its kernel. This result is effective: for example, Vélu [V7́1]
gives formulas for computing $\phi$ (as a rational map) given the points in
$\ker\phi$, and Kohel [Koh96, Section 2.4] gives formulas for computing these
rational maps from the kernel polynomial of $\phi$, the monic polynomial which
vanishes precisely at the $x$-coordinates of the nontrivial points in
$\ker\phi$. The methods of Vélu and Kohel also give an equation for
$E^{\prime}$, the codomain of $\phi$. The resulting isogeny is always
normalized, meaning the invariant differential $\omega^{\prime}$ of
$E^{\prime}$ pulls back, under $\phi$, to the invariant differential $\omega$
of $E$. The isogeny $\phi$ will be defined over $k$ if $\ker\phi$ is
$\operatorname{Gal}(\overline{k})$-stable, or equivalently, if the kernel
polynomial of $\phi$ has coefficients in $k$.

As mentioned above, a (description of) a cyclic subgroup $K$ of $E$ determines
a unique normalized isogeny $E\to E/K$. Alternatively, given $E^{\prime}$ and
$d$ such that there exists a cyclic, normalized $d$-isogeny $\phi\colon E\to
E^{\prime}$, this isogeny can be computed with Stark’s algorithm [Sta73] and
even more efficiently with an algorithm due to Bostan, Morain, Salvy, and
Schost [BMSS08]. Suppose now one only knows there exists a not necessarily
normalized isogeny between $E$ and $E^{\prime}$ of prime degree $\ell$,
perhaps because one has found that $\Phi_{\ell}(j(E),j(E^{\prime}))=0$ where
$\Phi_{\ell}(X,Y)$ is the modular equation. Provided that
$\operatorname{\operatorname{char}}(k)=0$ or is sufficiently large relative to
$\ell$, an algorithm of Elkies [Elk98, Section 3] can compute first a curve
$\widetilde{E}\cong E^{\prime}$ such that a normalized $\ell$-isogeny
$\phi\colon E\to\widetilde{E}$ exists, and then the kernel polynomial for
$\phi$, provided that $(j(E),j(E^{\prime}))$ is a non-singular point on
$\Phi_{\ell}(X,Y)=0$ (see also [Sch95, Section 7] for further details and
[Gal12, Section 25.2.1] for pseudocode). This algorithm is an important
subroutine in the SEA algorithm for point-counting on elliptic curves over
finite fields: for an ordinary curve $E$ defined over $\mathbb{F}_{q}$, one
computes a kernel polynomial for primes $\ell$ which split in
$\operatorname{End}(E)\otimes\mathbb{Q}$ in order to compute the trace of the
Frobenius endomorphism of $E$ modulo $\ell$.

Elkies’ method for computing an equation for the isogenous curve as described
in [Sch95] works as follows. Suppose $E\mathrel{\mathop{\mathchar
58\relax}}y^{2}=x^{3}+Ax+B$ is an elliptic curve over $\mathbb{C}$ which is
$\ell$-isogenous to the curve $E^{\prime}\mathrel{\mathop{\mathchar
58\relax}}y^{2}=x^{3}+A^{\prime}x+B^{\prime}$. Then there exists
$q_{0}=\exp(2\pi i\tau_{0})\in\mathbb{C}$ such that $A=-G_{4}(q_{0})/48$ and
$B=G_{6}(q_{0})/864$ and $j(E)=j(q_{0})$ where $G_{4}$ and $G_{6}$ are the
Eisenstein series of weights $4$ and $6$ respectively and $j(q)$ is the
$j$-function (in their $q$-expansions). Moreover, if we set
$\widetilde{j}(q)\coloneqq j(q^{\ell})$, then
$\widetilde{j}(q_{0})=j(E^{\prime})$ and setting

$\widetilde{A}=\frac{-\ell^{4}}{48}\cdot\frac{\widetilde{j}(q_{0})^{\prime
2}}{\widetilde{j}(q_{0})(\widetilde{j}(q_{0})-1728)},\quad\widetilde{B}=\frac{-\ell^{6}}{864}\cdot\frac{\widetilde{j}(q_{0})^{\prime
3}}{\widetilde{j}(q_{0})^{2}(\widetilde{j}(q_{0})-1728)}$

yields coefficients for a short Weierstrass equation for $E^{\prime}$ such
that the $\ell$-isogeny $\phi\colon E\to\widetilde{E}$ is normalized.
Therefore one can compute $\widetilde{E}$ as soon as one obtains
$\widetilde{j}^{\prime}(q_{0})$. Letting $\Phi(X,Y)\coloneqq\Phi_{\ell}(X,Y)$
denote the $\ell$-th modular polynomial parametrizing $\ell$-isogenous
$j$-invariant pairs, we have that $\Phi_{\ell}(j(q),\widetilde{j}(q))$ is
identically zero as a power series in $q$. Differentiating with respect to $q$
yields the identity

$j^{\prime}(q_{0})\Phi_{X}(j(q_{0}),\widetilde{j}(q_{0}))+\ell\widetilde{j}^{\prime}(q_{0})\Phi_{Y}(j(q_{0}),\widetilde{j}(q_{0}))=0$

so, assuming $(j(E),j(E^{\prime}))$ is a nonsingular point on $\Phi(X,Y)=0$,
one can solve for $\widetilde{j}^{\prime}$ and hence $\widetilde{E}$ in terms
of the equation for $E$ and the $j$-invariant of $E^{\prime}$.

If $(j(E),j(E^{\prime}))$ is a singular $k$-point on
$Y_{0}(\ell)\mathrel{\mathop{\mathchar 58\relax}}\Phi_{\ell}(X,Y)=0$, there
are (at least) two $\ell$-isogenies $\phi,\psi\colon E\to E^{\prime}$ with
distinct kernels.

Schoof writes that the approach to computing the isogenous curve
$\widetilde{E}$ “does not work if
$\Phi_{X}(j,\widetilde{j})=\Phi_{Y}(j,\widetilde{j})=0$.” However, the broader
idea – compute $\widetilde{j}^{\prime}$ in order to find the model
$\widetilde{E}$ – does. In this paper, we take up the problem of computing an
$\ell$-isogeny $E\to E^{\prime}$ when $(j(E),j(E^{\prime}))$ is a singular
point on $Y_{0}(\ell)$. One simply needs more derivatives of the identity
$\Phi_{\ell}(j,\widetilde{j})=0$.

In Section 4, we find that if $(j_{1},j_{2})$ is a singular point of
multiplicity $m$ on $\Phi_{\ell}(x,y)=0$, we can compute a degree $m$
polynomial whose roots yield the $m$ choices for $\widetilde{j}^{\prime}$ and
hence the $m$ models with $j$-invariant $j_{2}$ admitting normalized
$\ell$-isogenies, under the assumption that $j(E),j(E^{\prime})\not=0,1728$
(which is also assumed in [Sch95]) and the characteristic of the field is zero
or is sufficiently large relative to $\ell$. With the equation for
$\widetilde{E}$, the algorithm of [BMSS08] computes $\phi$ efficiently. This
allows one to compute all $\ell$-isogenies of $E$ efficiently.

In Section 2, we recall relevant definitions and notation. In Section 3, we
review Elkie’s method for computing an equation for the isogenous curve. In
Section 4, we extend Elkies’ method for computing the equation for the
isogenous curve at a singular point of the modular equation. Finally, in
Section 6, we give pseudocode for our algorithm and an example. Our
implementation in Sagemath [The23] is available at
https://github.com/wmahaney/ModularMultipoints.

##  2\. Background

In this section, we include some background elliptic curves, modular curves,
and singularities. We refer the reader to [Sil09, DS05, Ful89] for further
background.

###  2.1. Elliptic Curves

Let $k$ be a field. An elliptic curve over $k$ is a smooth projective genus
$1$ curve with a $k$-rational point. We will assume throughout that the
characteristic of $k$ is not $2$ or $3$ and that our elliptic curves are given
by a short Weierstrass equation over $k$, that is, an equation of the form
$y^{2}=x^{3}+Ax+B$ where $x,y$ are indeterminates and $A,B\in k$ satisfy
$4A^{3}+27B^{2}\neq 0$. Given an elliptic curve $E\mathrel{\mathop{\mathchar
58\relax}}y^{2}=x^{3}+Ax+B$ the invariant differential of $E$ is defined as
[Sil09, III.5]

$\omega_{E}\mathrel{\mathop{\mathchar 58\relax}}=\frac{dx}{2y}\in\Omega_{E}$

where $\omega_{E}$ is regarded as a differential on $E$. The $j$-invariant of
$E$ is given by

$j(E)\mathrel{\mathop{\mathchar
58\relax}}=\frac{-1728(4A)^{3}}{-16(4A^{3}+27B^{2})}=\frac{4\cdot
1728A^{3}}{4A^{3}+27B^{2}}$

Two elliptic curves $E,E^{\prime}$ defined over $k$ are
$\overline{k}$-isomorphic if and only if $j(E)=j(E^{\prime})$. Defining

$E_{j}\mathrel{\mathop{\mathchar
58\relax}}y^{2}=x^{3}+3j(1728-j)x+2j(1728-j)^{2},\quad j\not=0,1728$
$E_{0}\mathrel{\mathop{\mathchar 58\relax}}y^{2}=x^{3}+1,\quad
E_{1728}\mathrel{\mathop{\mathchar 58\relax}}y^{2}=x^{3}+x$

produces curves $E_{j}$ such that $j(E_{j})=j$ for any $j\in k$.

Given a pair of elliptic curves $E,E^{\prime}$ an isogeny [Sil09, III.4] from
$E\to E^{\prime}$ is a non-constant morphism $\phi\colon E\to E^{\prime}$ of
projective varieties such that $\phi(\infty_{E})=\phi(\infty_{E^{\prime}})$.
Any isogeny from $E\to E^{\prime}$ induces a group homomorphism $\phi\colon
E\left(\overline{k}\right)\to E^{\prime}\left(\overline{k}\right)$ [Sil09,
III.4.8]. The degree of an isogeny is its degree as a rational map. Every
isogeny $\phi\colon E\to E^{\prime}$ has a dual isogeny $\widehat{\phi}\colon
E^{\prime}\to E$ which satisfies $\widehat{\phi}\circ\phi=[\deg\phi]$, the
multiplication-by-$\deg\phi$ map. Two elliptic curves $E,E^{\prime}$ are
$n$-isogenous, for $n\geq 1$, provided there is an isogeny $\phi\colon E\to
E^{\prime}$ of degree $n$. We say that two $j$-invariants $j_{1},j_{2}\in K$
are $n$-isogenous provided $E_{j_{1}},E_{j_{2}}$ are $n$-isogenous.

An isogeny $\phi\colon E\to E^{\prime}$ between elliptic curves is separable
if it is separable as a rational map. If $\phi$ is separable, then
$\deg\phi=\\#\ker\phi$. We say that a separable isogeny $\phi\colon E\to
E^{\prime}$ is cyclic provided its kernel is a cyclic subgroup of
$E(\overline{k})$. Every isogeny $\phi$ factors as
$\phi=\phi^{\prime}\circ[n]\circ\pi^{n}$ where $\pi$ is the $p$-power
Frobenius isogeny, $[n]$ is the multiplication-by-$n$ map, and $\phi^{\prime}$
is separable and cyclic. And every $n$-isogeny $\phi\colon E\to E^{\prime}$
can be factored as a composition of prime degree isogenies, so we will focus
primarily on separable isogenies of prime degree.

###  2.2. Modular polynomials, curves, and functions

Let $\ell$ be a prime. The modular curve $X_{0}(\ell)$ is an algebraic curve
defined over $\mathbb{Q}$ whose non-cuspidal points parametrize elliptic
curves with choice of $\ell$-isogeny. The curve $X_{0}(\ell)$ is given by the
modular equation $\Phi_{\ell}(X,Y)=0$ which defines a plane curve
$Y_{0}(\ell)$; we have that $(j_{1},j_{2})$ is a point on $Y_{0}(\ell)$ if and
only if there are elliptic curves $E_{j_{1}},E_{j_{2}}$ and a cyclic
$\ell$-isogeny $\phi\colon E_{j_{1}}\to E_{j_{2}}$. The curve $X_{0}(\ell)$ is
the nonsingular projective model of $Y_{0}(\ell)$. Thus if $E$ is an elliptic
curve and $K$ is a cyclic subgroup of $E$ of order $\ell$, then the point
$[E,K]$ on $X_{0}(\ell)$ maps to the point $(j(E),j(E/K))$ on
$\Phi_{\ell}(x,y)=0$. The modular polynomial $\Phi_{\ell}(X,Y)$ is
irreducible, symmetric, and of the form
$X^{\ell}Y^{\ell}+X^{\ell+1}+Y^{\ell+1}+\ldots$ where $\ldots$ denotes terms
of lower degree [Sch95, Section 6].

There are some particular modular forms we are interested in for this paper,
which we will regard in their $q$-expansions. The first are the weights 4 and
6 normalized (constant coefficient one) Eisenstein series $G_{4}(q)$ and
$G_{6}(q)$ which are modular forms of weights $4$ and $6$ respectively. There
is also the $j$-function given by

$j(q)\mathrel{\mathop{\mathchar
58\relax}}=1728\frac{G_{4}(q)^{3}}{G_{4}(q)^{3}-G_{6}(q)^{2}}$

The $j$-function parametrizes $j$-invariants of elliptic curves over
$\mathbb{C}$; in particular for a given $z\in\mathbb{C}$ there exists a
$q_{0}$ with $j(q_{0})=z$ and the elliptic curve over $\mathbb{C}$ with short
Weierstrass equation

$E\mathrel{\mathop{\mathchar
58\relax}}y^{2}=x^{3}-\frac{G_{4}(q_{0})}{48}+\frac{G_{6}(q_{0})}{864}$

has $j$-invariant $j(q_{0})$.

###  2.3. Singularities of Plane Curves

Two $j$-invariants $(j_{1},j_{2})\in k^{2}$ are $\ell$-isogenous over $k$ if
and only if $\Phi_{\ell}(j_{1},j_{2})=0$, so the $k$-rational points of
$Y_{0}(\ell)/k$ parameterize pairs of $k$-rational $\ell$-isogenous
$j$-invariants. While $X_{0}(\ell)/k$ is smooth, $Y_{0}(\ell)/k$ is not
generally smooth. Before discussing what singularities $Y_{0}(\ell)/k$ has let
us define singularities and their associated data:

######  Definition 2.1.

(Singularities of Plane Curves) [Ful89, Section 3.1]
Let $F(x,y)\in k[x,y]$ be a non-constant polynomial. A point $(a,b)\in k^{2}$
is a multiple point or singular point of $F$ provided

$F(a,b)=\frac{\partial F}{\partial x}(a,b)=\frac{\partial F}{\partial
y}(a,b)=0$

where the derivatives are formal. Suppose $(a,b)$ is a singular point of $F$.
Via change of variables define the polynomial

$H(x,y)=F(x+a,y+b).$

As $H(0,0)=F(a,b)=0$ we can write

$H(x,y)=H_{m}(x,y)+\ldots+H_{\operatorname{Deg}(H)}(x,y),$

where each $H_{d}$ is homogeneous of degree $d$ and $H_{m}\neq 0$. The
multiplicity of the singularity $(a,b)$ of $F$ is $m$. For a curve
$C=\mathcal{V}(F)$, a point $(a,b)$ on $C$ is a singular point provided
$(a,b)$ is a singular point of $F$ and vice versa.

##  3\. Elkies’ method to compute the isogenous curve

In this section, we review ideas of Elkies [Elk98, Section 3] and formulas of
Schoof [Sch95, Section 7] for computing, given an elliptic curve $E$ and prime
$\ell$, an equation for an elliptic curve $\widetilde{E}$ such that there
exists a normalized $\ell$-isogeny $\phi\colon E\to\widetilde{E}$.

Per [Sch95, Proposition 7.1 (i)] we have an equality of power series

$\displaystyle\frac{j^{\prime}(q)}{j(q)}=-\frac{G_{6}(q)}{G_{4}(q)}$

where the above functions are considered as modular forms in their
$q$-expansions; this equality gives another

$j^{\prime}(q)=-\frac{G_{6}(q)}{G_{4}(q)}j(q)$

away from $q_{0}$ for which $j(q_{0})\in\\{0,\infty\\}$. Per [Sch95,
Proposition 7.2] there exist formal power series
$X(\zeta;q),Y(\zeta;q)\in\mathbb{Z}\Big{[}\Big{[}q,\zeta,\frac{1}{\zeta-\zeta^{2}}\Big{]}\Big{]}$
for which

$\displaystyle
Y(\zeta;q)^{2}=X(\zeta;q)^{3}-\frac{G_{4}(q)}{48}X(\zeta;q)+\frac{G_{6}(q)}{864}$

If one took the substitution

$\displaystyle A(q)$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\frac{-G_{4}(q)}{48}$ $\displaystyle B(q)$
$\displaystyle\mathrel{\mathop{\mathchar 58\relax}}=\frac{G_{6}(q)}{864}$

Then the prior equality of power series becomes

$Y(\zeta;q)^{2}=X(\zeta;q)^{3}+A(q)X(\zeta;q)+B(q)$

and each fixed $q_{0}$ we have a short Weierstrass equation for an elliptic
curve over $\mathbb{C}$ whose affine points are the pairs
$\left(X(\zeta(z);q_{0}),\pm Y(\zeta(z);q_{0})\right)$ where
$\zeta(z)=e^{2i\pi z}$ and $z$ ranges over $\mathbb{C}$. Fix a particular
$q_{0}$. Then the curve $E\mathrel{\mathop{\mathchar
58\relax}}Y^{2}=X^{3}+A(q_{0})X+B(q_{0})$ is $\ell$-isogenous to the curve
$\widetilde{E}\colon Y^{2}=X^{3}+A(q_{0}^{\ell})X+B(q_{0}^{\ell})$, and if one
replaces $A(q_{0}^{\ell}),B(q_{0}^{\ell})$ with $\ell^{4}A(q_{0}^{\ell})$ and
$\ell^{6}B(q_{0}^{\ell})$ then the isogeny connecting the two curves is
normalized [Elk98]. Using the identities presented in [Sch95, Proposition 7.1]
one can compute formulas for $G_{4}(q_{0}),G_{6}(q_{0})$ in terms of
$j(q_{0})$ and $j^{\prime}(q_{0})$, similarly one can compute formulas for
$G_{4}(q_{0}^{\ell})$ and $G_{6}(q_{0}^{\ell})$ in terms of
$\widetilde{j}(q_{0})$ and $\widetilde{j}^{\prime}(q_{0})$. Therefore if one
can compute $\widetilde{j}^{\prime}(q_{0})$ one can obtain a model for
$\widetilde{E}$ which admits an isogeny from $E$, and by scaling this model
appropriately compute a normalized model for this isogeny.

Fix a prime $\ell$ and the function $\widetilde{j}(q)=j(q^{\ell})$. For every
$q_{0}$ we have that $j(q_{0}),\widetilde{j}(q_{0})$ are $\ell$-isogenous
$j$-invariants so as a function of $q$ we have
$\Phi_{\ell}(j,\widetilde{j})=0$. Moreover if we take the derivative of the
function $0=\Phi_{\ell}(j,\widetilde{j})$ by applying the multivariate chain
rule we get

$0=\left(\Phi_{\ell}(j,\widetilde{j})\right)^{\prime}=j^{\prime}\Phi_{X}(j,\widetilde{j})+\ell\widetilde{j}^{\prime}\Phi_{Y}(j,\widetilde{j}).$

Solving for $\widetilde{j}^{\prime}$, assuming $\Phi_{y}(j,\widetilde{j})\neq
0$, and then setting

(1)
$\displaystyle\widetilde{A}=\frac{-\ell^{4}}{48}\cdot\frac{\widetilde{j}^{\prime
2}}{\widetilde{j}(\widetilde{j}-1728)}$ (2)
$\displaystyle\widetilde{B}=\frac{-\ell^{6}}{864}\cdot\frac{\widetilde{j}^{\prime
3}}{\widetilde{j}^{2}(\widetilde{j}-1728)}$

yields an equation $Y^{2}=X^{3}+\widetilde{A}X+\widetilde{B}$ for the
isogenous curve admitting a normalized isogeny from $E$ whose points are the
pairs $\left(X(\zeta(z);q_{0}^{\ell}),\pm Y(\zeta(z);q_{0}^{\ell})\right)$ as
$z$ ranges over $\mathbb{C}$.

Even though all the above is derived from properties of modular functions over
$\mathbb{C}$, the Deuring lifting theorem justifies that these computations
can be performed over a finite field as well, provided the characteristic is
not $2,3$, or $\ell$.

##  4\. Singular points on $Y_{0}(\ell)$

In this section, we observe that the multiplicity of a point $(j_{1},j_{2})$
on $Y_{0}(\ell)$ is equal to the number of cyclic $\ell$-isogenies from an
elliptic curve with $j$-invariant $j_{1}$ to an elliptic curve with
$j$-invariant $j_{2}$. We use this in the following section in order to
compute normalized models for $\ell$-isogenies at singular points of
$Y_{0}(\ell)$.

######  Proposition 4.1.

Suppose $j_{1},j_{2}$ are two elements of $k$, neither of which are $0$ or
$1728$. Let $(j_{1},j_{2})$ be a point on $Y_{0}(\ell)$ and let $m$ be the
number of $\ell$-isogenies with distinct kernels between two fixed elliptic
curves $E_{1}$ and $E_{2}$ with $j$-invariants $j_{1}$ and $j_{2}$. If
$\operatorname{\operatorname{char}}(k)=0$ or
$\operatorname{\operatorname{char}}(k)>m$, then $(j_{1},j_{2})$ is a point of
multiplicity $m$ on $Y_{0}(\ell)$. In particular, all partial derivatives of
$\Phi_{\ell}(X,Y)$ of weight less than $m$ vanish at $(j_{1},j_{2})$.
Moreover, both $\Phi_{X^{m}}(j_{1},j_{2}))$ and $\Phi_{Y^{m}}(j_{1},j_{2})$
are nonzero.

###### Proof.

We can identify $X_{0}(\ell)$ as the blowup of $Y_{0}(\ell)$ at its singular
points. The non-cuspidal points on $X_{0}(\ell)$ then correspond to tangent
directions at points $(j_{1},j_{2})$ of $Y_{0}(\ell)$. Suppose there are $m$
distinct points on $X_{0}(\ell)$ above $(j_{1},j_{2})$. Then the multiplicity
of $(j_{1},j_{2})$ on $Y_{0}(\ell)$ is at least the number of tangent
directions at $P$ and therefore at least $m$. On the other hand, the number of
$\ell$-isogenies between $j_{1}$ and $j_{2}$ is equal to the multiplicity of
$j_{2}$ as a root of the degree $\ell+1$ polynomial
$\phi(Y)\coloneqq\Phi(j_{1},Y)$. If $m<\ell+1$, the assumption on the
characteristic of $\operatorname{\operatorname{char}}(k)$ implies
$\phi^{(m)}(j_{2})\not=0$ and therefore the multiplicity is at most $m$. If
$m=\ell+1$ then $(j_{1},j_{2})$ is a point of multiplicity $m$ since its
multiplicity is at most $\ell+1$. ∎

In the following section, we will need to compute $\widetilde{j}^{\prime}$ at
singular points by finding it as a root of a polynomial obtained by
differentiating the modular equation $m+1$ times, where $m$ is the
multiplicity of the singularity. A straightforward argument via induction
gives the following expression for the $n$th derivative of the modular
equation:

######  Proposition 4.2.

Fix the functions $j(q)$ and $\widetilde{j}(q)\coloneqq j(q^{\ell})$ in their
$q$-expansions as well as the $\ell$th modular polynomial
$\Phi=\Phi_{\ell}(X,Y)$. Then for all integers $n\geq 2$ the $n$-fold
derivative of $\Phi(j,\widetilde{j})$ is given by

$\left(\Phi(j,\widetilde{j})\right)^{(n)}=\varepsilon_{n}(q)+F_{n}(q)$

where $\varepsilon_{n}(q)$ is of the form

$\varepsilon_{n}(q)=\sum_{0\leq
u+v<n}\varepsilon_{u,v}(q)\Phi_{X^{u}Y^{v}}(j,\widetilde{j})$

and $F_{n}(q)$ is of the form

$F_{n}(q)=\sum_{u=0}^{n}\binom{n}{u}\ell^{n-u}(j^{\prime})^{u}(\widetilde{j}^{\prime})^{n-u}\Phi_{X^{u}Y^{n-u}}(j,\widetilde{j}).$

##  5\. Computing Reductions of $\widetilde{j}^{\prime}$

Throughout this section, fix a field $k$, fix $j_{1},j_{2}\in k$ with
$j_{1},j_{2}\not=0,1728$, let $E_{A,B}$ be a curve of $j$-invariant $j_{1}$,
and define $j_{1}^{\prime}=\frac{18B}{A}j_{1}$.

######  Definition 5.1.

Suppose $P=(j_{1},j_{2})$ is a singular point of multiplicity $m$ on
$Y_{0}(\ell)$ with $j_{1},j_{2}\not=0,1728$. Define

$F_{P}(t)=\sum_{u=0}^{m}\binom{m}{u}\ell^{m-u}(j_{1}^{\prime})^{u}\Phi_{X^{u}Y^{m-u}}(P)t^{m-u}.$

######  Remark 5.2.

By Proposition 4.1 $F_{P}(t)$ is a degree $m$ polynomial whenever
$m<\operatorname{\operatorname{char}}(k)$.

######  Proposition 5.3.

Fix a singular point $P=(j_{1},j_{2})$ of multiplicity $m$ on $Y_{0}(\ell)/k$
and the associated polynomial $F_{P}(t)$. Then for every $k$-model
$(\widetilde{A},\widetilde{B})$ for $E_{j_{2}}$ admitting a normalized cyclic
$\ell$-isogeny from $E_{A,B}$ there exists a root $\widetilde{r}$ of
$F_{P}(t)$ given by
$\widetilde{r}=\frac{18\widetilde{B}}{\ell^{2}\widetilde{A}}j_{2}$.

###### Proof.

Let $\phi\colon E_{A,B}\to E_{\widetilde{A},\widetilde{B}}$ be a normalized
cyclic $\ell$-isogeny defined over $k$ and define

$\widetilde{r}=\frac{18\widetilde{B}}{\ell^{2}\widetilde{A}}j_{2}.$

Let
$\varphi\colon\widehat{E_{A,B}}\to\widehat{E_{\widetilde{A},\widetilde{B}}}$
be a lift of $\phi$ to an $\ell$-isogeny of elliptic curves defined over a
number field $L$ such that there exists a prime $\mathfrak{P}$ of $L$ where
$\widehat{E_{A,B}}$ and $\widehat{E_{\widetilde{A},\widetilde{B}}}$ both have
good reduction at $\mathfrak{P}$ and $\varphi$ reduces to $\phi$ modulo
$\mathfrak{P}$; in the case that $k$ is a number field we take $L=k$ and
$\mathfrak{P}$ is the zero ideal. There exists $q_{0}$ such that

$\displaystyle\frac{-G_{4}(q_{0})}{48}$ $\displaystyle\equiv
A\pmod{\mathfrak{P}}$ $\displaystyle\frac{G_{6}(q_{0})}{864}$
$\displaystyle\equiv B\pmod{\mathfrak{P}}$
$\displaystyle\frac{-\ell^{4}G_{4}(q_{0}^{\ell})}{48}$
$\displaystyle\equiv\widetilde{A}\pmod{\mathfrak{P}}$
$\displaystyle\frac{\ell^{6}G_{6}(q_{0}^{\ell})}{864}$
$\displaystyle\equiv\widetilde{B}\pmod{\mathfrak{P}}$

and we can realize $\varphi$ as the isogeny mapping

$\widehat{E_{A,B}}\mathrel{\mathop{\mathchar
58\relax}}y^{2}=x^{3}-\frac{G_{4}(q_{0})}{48}x+\frac{G_{6}(q_{0})}{864}$

to

$\widehat{E_{\widetilde{A},\widetilde{B}}}\mathrel{\mathop{\mathchar
58\relax}}y^{2}=x^{3}-\frac{\ell^{4}G_{4}(q_{0})}{48}x+\frac{\ell^{6}G_{6}(q_{0})}{864}$

which is normalized over $L$ [Elk98, Section 3]. We then have an equality of
power series giving an equivalence

$\frac{\widetilde{j}^{\prime}(q_{0})}{\widetilde{j}(q_{0})}=-\frac{\ell^{6}G_{6}(q_{0}^{\ell})}{\ell^{4}G_{4}(q_{0}^{\ell})}\equiv\frac{-864\ell^{4}\widetilde{B}}{-48\ell^{6}\widetilde{A}}\equiv\frac{18\widetilde{B}}{\ell^{2}\widetilde{A}}\pmod{\mathfrak{P}}.$

Because $0\neq j_{2}\equiv\widetilde{j}(q_{0})\bmod{\mathfrak{P}}$ we have
$\widetilde{j}(q_{0})\neq 0$ and so

$\widetilde{j}^{\prime}(q_{0})\equiv\frac{18\widetilde{B}\widetilde{j}(q_{0})}{\ell^{2}\widetilde{A}}\equiv\frac{18\widetilde{B}}{\ell^{2}\widetilde{A}}j_{2}\equiv\widetilde{r}\pmod{\mathfrak{P}}$

So $\widetilde{r}$ is a reduction of $\widetilde{j}^{\prime}$ modulo
$\mathfrak{P}$. As $j(q),\widetilde{j}(q)$ are $j$-invariants for a pair of
$\ell$-isogenous elliptic curves over $\mathbb{C}$ for all $q$ we have that

$\Phi_{\ell}(j,\widetilde{j})=0$

Hence the $m$th derivative $\left(\Phi_{\ell}(j,\widetilde{j})\right)^{(m)}=0$
as well. Using Proposition 4.2 and the prior observation we can write

$0=\left(\Phi(j,\widetilde{j})\right)^{(m)}=\varepsilon_{m}(q)+\sum_{u=0}^{m}\binom{m}{u}\ell^{m-u}(j^{\prime})^{u}(\widetilde{j}^{\prime})^{n-u}\Phi_{X^{u}Y^{m-u}}(j,\widetilde{j})$

where

$\varepsilon_{m}(q)=\sum_{0\leq
u+v<m}\varepsilon_{u,v}(q)\Phi_{X^{u}Y^{v}}(j,\widetilde{j})$

As $(j_{1},j_{2})$ is a singular point of $Y_{0}(\ell)/k$ of multiplicity $m$
by 4.1 we have $\Phi_{X^{u}Y^{v}}(j_{1},j_{2})=0$ whenever $u+v<m$. As
$j_{1}\equiv j(q_{0})\pmod{\mathfrak{P}}$ and
$j_{2}\equiv\widetilde{j}(q_{0})\pmod{\mathfrak{P}}$ we have

$\displaystyle\varepsilon_{m}(q_{0})$ $\displaystyle=\sum_{0\leq
u+v<m}\varepsilon_{u,v}(q_{0})\Phi_{x^{u}y^{v}}(j(q_{0}),\widetilde{j}(q_{0}))$
$\displaystyle\equiv\sum_{0\leq
u+v<m}\varepsilon_{u,v}(q_{0})\Phi_{x^{u}y^{v}}(j_{1},j_{2})\pmod{\mathfrak{P}}$
$\displaystyle\equiv 0\pmod{\mathfrak{P}}$

So both $\left(\Phi(j,\widetilde{j})\right)^{(m)}(q_{0})$ and
$\varepsilon_{m}(q_{0})$ are zero modulo $\mathfrak{P}$, hence their
difference is also zero modulo $\mathfrak{P}$ hence

$\displaystyle 0$ $\displaystyle\equiv
H^{(m)}(q_{0})-\varepsilon_{m}(q_{0})\pmod{\mathfrak{P}}$
$\displaystyle\equiv\sum_{u=0}^{m}\binom{m}{u}\ell^{m-u}(j^{\prime}(q_{0}))^{u}(\widetilde{j}^{\prime}(q_{0}))^{n-u}\Phi_{X^{u}Y^{m-u}}(j(q),\widetilde{j}(q))\pmod{\mathfrak{P}}$
$\displaystyle\equiv\sum_{u=0}^{m}\binom{m}{u}\ell^{m-u}(j_{1}^{\prime})^{u}(\widetilde{r})^{n-u}\Phi_{X^{u}Y^{m-u}}(j_{1},j_{2})\pmod{\mathfrak{P}}$
$\displaystyle\equiv F_{P}(\widetilde{r})\pmod{\mathfrak{P}}$

∎

Thus we have a map from the set of normalized isogenies $\phi\colon E_{A,B}\to
E_{\widetilde{A},\widetilde{B}}$ to the set of roots of $F_{P}(t)$. As $P$ is
a singular point of multiplicity $m$ there exist $m$ distinct cyclic
$\ell$-isogenies from $j_{1}$ to $j_{2}$. However it can happen that there are
two (or more) normalized $\ell$-isogenies between two fixed elliptic curves.

######  Example 5.4.

Consider the curves $E\mathrel{\mathop{\mathchar 58\relax}}y^{2}=x^{3}+x+4$
and $\widetilde{E}\mathrel{\mathop{\mathchar 58\relax}}y^{2}=x^{3}+12x+7$ over
$\mathbb{F}_{169}$. These curves are isomorphic, supersingular, and are
connected by two normalized $\mathbb{F}_{169}$-rational $5$-isogenies with
distinct kernels. The kernel polynomials are the two degree $2$ factors of
$x^{4}+10x^{3}+9x^{2}+12x+6$ over $\mathbb{F}_{169}$.

######  Proposition 5.5.

Assume now that either $\operatorname{\operatorname{char}}(k)=0$ or if
$\operatorname{\operatorname{char}}(k)=p>0$ that $p>4\ell$. Then there is a
bijection between the roots of $F_{P}(t)$ and the cyclic, normalized
$\ell$-isogenies of $E_{A,B}$. Provided the bijection exists it is given by
the following:

  1. (1)

Given a model $(\widetilde{A},\widetilde{B})$ for $E_{j_{2}}$ admitting a
normalized cyclic separable $\ell$-isogeny from $E_{A,B}$ the quantity
$r=\frac{18\widetilde{B}}{\ell^{2}\widetilde{A}}j_{2}$ is a root of
$F_{P}(t)$.

  2. (2)

Given a root $r$ of $F_{P}(t)$ if one sets

$\widetilde{A}=\frac{-\ell^{4}}{48}\frac{r^{2}}{j_{2}(j_{2}-1728)},\quad\widetilde{B}=\frac{-\ell^{6}}{864}\frac{r^{3}}{j_{2}^{2}(j_{2}-1728)},$

then $E_{\widetilde{A},\widetilde{B}}$ admits a normalized cyclic separable
$\ell$-isogeny from $E_{A,B}$.

For this, we need the following lemma:

######  Lemma 5.6.

Let $E,E^{\prime}$ be elliptic curves over a field $k$ and whose
$j$-invariants are not $0$ or $1728$. Suppose there exist two normalized,
separable $\ell$-isogenies $\phi,\psi\colon E\to E^{\prime}$ with distinct
kernels. Then $0<\operatorname{\operatorname{char}}(k)<4\ell$.

###### Proof.

The existence of two distinct subgroups of order $\ell$ in $E$ implies that
$E[\ell]\cong(\mathbb{Z}/\ell\mathbb{Z})^{2}$ and in particular
$\operatorname{\operatorname{char}}(k)\not=\ell$. Consider the (necessarily
separable) endomorphism
$\alpha=\widehat{\psi}\circ\phi\in\operatorname{End}(E)$. Since
$\ker\phi\not=\ker\psi$, the endomorphism $\alpha$ is cyclic of degree
$\ell^{2}$ and therefore $\alpha\not=\pm\ell$. Since both $\phi$ and $\psi$
are normalized, we have that $\alpha^{*}\omega=\ell\omega$ for any invariant
differential of $E$. Therefore the endomorphism $\alpha-\ell$ is inseparable,
so $p=\operatorname{\operatorname{char}}(k)>0$ and the degree of $\alpha-\ell$
is divisible by $p$. Let $t(\alpha)=\alpha+\widehat{\alpha}\in\mathbb{Z}$
denote the trace of $\alpha$. The degree of $\alpha-\ell$ is

$\deg(\alpha-\ell)=2\ell^{2}-\ell t(\alpha)\equiv 0\pmod{p},$

Since $\alpha$ is separable, the prime $p$ does not divide $\ell$, so
$t(\alpha)-2\ell\equiv 0\pmod{p}$. On the other hand, we have that the
discriminant $t(\alpha)^{2}-4\ell^{2}$ is negative, so
$-2\ell<t(\alpha)<2\ell$. This implies

$-4\ell<t(\alpha)-2\ell<0$

so $p<4\ell$, as claimed. ∎

We are now ready to prove Proposition 5.5.

###### Proof of Proposition 5.5.

Since $P$ is a point of multiplicity $m$ on $Y_{0}(\ell)$, there exist $m$
different $\ell$-isogenies of $E=E_{A,B}$ with distinct kernels to curves with
$j$-invariant $j_{2}$. Let
$(\widetilde{A_{1}},\widetilde{B_{1}}),\ldots,(\widetilde{A_{m}},\widetilde{B_{m}})$
denote the coefficients of the short Weierstrass equations for these $m$
codomains. By Lemma 5.6, these curves are all distinct. On the other hand,
since they are all isomorphic, for each $i,j$ there exists
$u_{ij}\in\overline{k}$ such that
$\widetilde{A_{i}}=u_{ij}^{4}\widetilde{A_{j}}$ and
$\widetilde{B_{i}}=u_{ij}^{6}\widetilde{B_{j}}$. Define
$r_{i}=\frac{18}{\ell^{2}}{j_{2}}\frac{\widetilde{B_{i}}}{\widetilde{A_{i}}}$
for each $1\leq i\leq m$. We claim that the $r_{i}$ are distinct.

Observe that if

$r_{i}={j_{2}}\frac{18\widetilde{B_{i}}}{\ell^{2}\widetilde{A_{i}}}={j_{2}}\frac{18\widetilde{B_{j}}}{\ell^{2}\widetilde{A_{j}}}=r_{j}$

then

$\frac{\widetilde{B_{j}}}{\widetilde{A_{j}}}=\frac{\widetilde{B_{i}}}{\widetilde{A_{i}}}=u_{ij}^{2}\frac{\widetilde{B_{j}}}{\widetilde{A_{j}}}$

so $u_{ij}=\pm 1$, which would imply
$(\widetilde{A_{i}},\widetilde{B_{i}})=(\widetilde{A_{j}},\widetilde{B_{j}})$.
Thus $r_{i}\not=r_{j}$ for $i\not=j$. By Proposition 5.3 each of the $r_{i}$
is a root of $F_{P}$, thus we have constructed $m$ distinct roots of the
degree $m$ polynomial $F_{P}$ hence as claimed each root of $F_{P}$
corresponds to a model $(\widetilde{A}_{n},\widetilde{B}_{n})$ and vice versa.
The first formula to obtain $r_{i}$ from $\widetilde{A}_{i},\widetilde{B}_{i}$
is proven in 5.3. The formula to obtain $\widetilde{A}_{i},\widetilde{B}_{i}$
from $r_{i}$ is proven by taking Deuring lifts of
$\widetilde{A}_{i},\widetilde{B}_{i},j_{2}$ and $\widetilde{j}^{\prime}$ and
expressing these lifts in terms of Eisenstein series, then one uses the power
series identities in [Sch95, Proposition 7.1] applied to
$j(q_{0}^{\ell}),\widetilde{j}(q_{0})^{\ell},G_{4}(q_{0}^{\ell}),G_{6}(q_{0}^{\ell})$
to manipulate the expressions for $r_{i}^{2},r_{i}^{3}$ and obtain the claimed
formulas.

∎

##  6\. Pseudocode and examples

5.5 gives a polynomial time algorithm which upon input $(j_{1},j_{2})$ a
multiplicity $m$ point on $Y_{0}(\ell)$ returns every model for $E_{j_{2}}$
which permits a normalized isogeny from $j_{1}$. We simply compute the
polynomial given in definition 5.1, find its roots, and compute the
$\widetilde{A},\widetilde{B}$ corresponding to each root we computed.

Algorithm 1 Basic Algorithm To Compute Normalized Models for the Isogenous
Curve over Finite Fields

A prime $\ell\neq\operatorname{\operatorname{char}}(k)$ such that
$4\ell\leq\operatorname{\operatorname{char}}(k)$ or
$\operatorname{\operatorname{char}}(k)=0$, a singular point
$(j_{1},j_{2})\in\mathcal{V}_{k}(\Phi_{\ell}(X,Y))$ of multiplicity $m$ with
$j_{1},j_{2}\neq 0,1728$, and a $k$-model $(A,B)$ for $E_{j_{1}}$.

$\\{(A_{1},B_{1}),\ldots,(A_{m},B_{m})\\}$ such that for all $1\leq i\leq m$
the cyclic $\ell$-isogeny from $E_{j_{1}}$ with model $(A,B)$ to $E_{j_{2}}$
with model $(A_{i},B_{i})$ is normalized.

$\Phi\leftarrow\Phi_{\ell}(X,Y)\in k[X,Y]$ $\triangleright$ Compute the
$\ell$th modular polynomial.

$j_{1}^{\prime}\leftarrow\frac{18B}{A}j_{1}$ $\triangleright$ Compute the
reduction of $j_{1}^{\prime}\mathrel{\mathop{\mathchar
58\relax}}=j^{\prime}(q_{0})$ to $k$.

for $0\leq u\leq m$ do

$c_{u}\leftarrow\binom{m}{u}\ell^{m-u}(j_{1}^{\prime})^{u}\Phi_{X^{u}Y^{m-u}}(j_{1},j_{2})$
$\triangleright$ Compute Coefficients of $F_{P}$.

end for

$F(t)\leftarrow\sum_{u=0}^{m}c_{u}t^{u}$ $\triangleright$ Instantiate $F_{P}$.

$\\{r_{1},\ldots,r_{m}\\}\leftarrow\text{Roots{$(F)$}}$ $\triangleright$
Compute the roots of $F_{P}$.

for $1\leq i\leq m$ do $\triangleright$ Each $r_{i}$ is a valid
$j_{2}^{\prime}$.

$A_{i}=-\frac{\ell^{4}}{48}\frac{r_{i}^{2}}{j_{2}(j_{2}-1728)}$

$B_{i}=-\frac{\ell^{6}}{864}\frac{r_{i}^{3}}{j_{2}^{2}(j_{2}-1728)}$

end for

Return $\\{(A_{1},B_{1}),\ldots,(A_{m},B_{m})\\}$.

######  Example 6.1.

Take $k=\mathbb{F}_{137^{2}}\cong\mathbb{F}_{137}(w)$ where $w$ has minimal
polynomial $x^{2}+131x+3$ over $\mathbb{F}_{137}$. Fix $j_{1}=136$ and
$j_{2}=22$ regarded in $k$, as well as $P=(j_{1},j_{2})\in k^{2}$ and
$\ell=5$. Note that $1728\equiv 84\pmod{137}$ so neither $j_{1}$ nor $j_{2}$
are in $\\{0,1728\\}$. The instantiated modular polynomial $\Phi_{5}(136,y)$
has a double factor of $y-22$ so there are two distinct 5-isogenies from
$j_{1}=136$ to $j_{2}=22$. Fix a model $E_{A,B}\mathrel{\mathop{\mathchar
58\relax}}y^{2}=x^{3}+19x+65$ for $E_{136}$ and compute
$j_{1}^{\prime}=\frac{18\cdot 65}{19}\cdot 136\equiv 61$. We compute the
partial derivative evaluations $\Phi_{XX}(P),\Phi_{XY}(P)$, and $\Phi_{YY}(P)$
as

$\displaystyle\Phi_{XX}(P)=79,\quad\Phi_{XY}(P)=6,\quad\Phi_{YY}(P)=5$

We can now compute $F_{P}(t)$ as

$\displaystyle F_{P}(t)$
$\displaystyle=\binom{2}{0}\ell^{2}(j_{1}^{\prime})^{0}\Phi_{YY}(P)t^{2}+\binom{2}{1}\ell^{2-1}(j_{1}^{\prime})^{1}\Phi_{XY}(P)t+\binom{2}{2}\ell^{2-2}(j_{1}^{\prime})^{2}\Phi_{XX}(P)t^{0}$
$\displaystyle=5^{2}\cdot 5\cdot t^{2}+2\cdot 5\cdot 61\cdot 6t+61^{2}\cdot
79$ $\displaystyle\equiv 125t^{2}+98t+94\pmod{137}$

The roots of $F_{P}(t)$ are

$r_{1}=134w+93,\quad r_{2}=3w+75$

and the associated models are given by

$\widetilde{A}_{1}=32w+118,\quad\widetilde{B_{1}}=15w+136,\quad\widetilde{A}_{2}=105w+136,\quad\widetilde{B}_{2}=122w+89$

The 5-isogeny from $E_{A,B}\to E_{\widetilde{A}_{1},\widetilde{B}_{1}}$ has
kernel polynomial

$f_{1}=x^{2}+(32w+84)x+(107w+66)$

and the 5-isogeny from $E_{A,B}\to E_{\widetilde{A}_{2},\widetilde{B}_{2}}$
has kernel polynomial

$f_{2}=x^{2}+(105w+2)x+(30w+23)$

######  Remark 6.2.

In Algorithm 1, we compute the $\ell$th modular polynomial in order to compute
the polynomial $F_{(j_{1},j_{2})}(t)$ to compute $\widetilde{j}^{\prime}$.
Alternatively, one could modify Sutherland’s algorithm [Sut13] for computing
the instantiated modular polynomial $\phi(Y)\coloneqq\Phi(j_{1},Y)$ and
derivative $\phi_{X}(Y)\coloneqq\Phi_{X}(j_{1},Y)$ to additionally compute
$\phi_{X^{i}}(Y)=\Phi_{X^{i}}(j_{1},Y)$ for $i=1,2,\ldots,m$ at a multiplicity
$m$ singular point $(j_{1},j_{2})$ of $Y_{0}(\ell)$ and then compute the
polynomial $F_{(j_{1},j_{2})}$ using these instantiated polynomials.

######  Remark 6.3.

Elkies’ method computes not only the model $\widetilde{E}$ such that a
normalized $\ell$-isogeny $E\to\widetilde{E}$ exists; by computing the second
derivative $\widetilde{j}^{\prime\prime}$, one can compute $\sigma$, the
$(\ell-3)/2$ coefficient of the kernel polynomial, i.e. the sum of the
$x$-coordinates of the affine points in the kernel. From this coefficient, the
rest can be determined (see for example [Gal12, Algorithm 28] and [Sch95,
Propositions 7.1, 7.2, 7.3]). Schoof computes $\widetilde{j}^{\prime\prime}$
by differentiating the modular equation twice; one should be able to solve for
$\widetilde{j}^{\prime\prime}$ at a singular point of multiplicity $m$ by
differentiating the modular equation $m+1$ times. Now one would have to match
possible values for $\widetilde{j}^{\prime\prime}$ with the possible values
for $\widetilde{j}^{\prime}$. This could be advantageous, since the algorithm
of [BMSS08] is faster (in terms of field operations) by a factor of $\log\ell$
when $\sigma$ is known.

##  7\. Acknowledgements

We would like to thank Leonardo Mihalcea for helpful discussions. The first
author was supported by the Julian Chin Ph.D. Fellowship in Cybersecurity.
This research was funded in part by the Commonwealth of Virginia’s
Commonwealth Cyber Initiative (CCI). CCI is an investment in the advancement
of cyber R&D, innovation, and workforce development. For more information
about CCI, visit www.cyberinitiative.org.

## References

  * [BMSS08] Alin Bostan, Franccois Morain, Bruno Salvy, and Éric Schost.  Fast algorithms for computing isogenies between elliptic curves.  Mathematics of Computation, 77(263):1755–1778, 2008.
  * [DS05] Fred Diamond and Jerry Michael Shurman.  A First Course in Modular Forms, volume 228.  Springer, 2005.
  * [Elk98] Noam D. Elkies.  Elliptic and modular curves over finite fields and related computational issues.  In Computational perspectives on number theory (Chicago, IL, 1995), volume 7 of AMS/IP Stud. Adv. Math., pages 21–76. Amer. Math. Soc., Providence, RI, 1998.
  * [Ful89] William Fulton.  Algebraic curves.  Advanced Book Classics. Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1989.  An introduction to algebraic geometry, Notes written with the collaboration of Richard Weiss, Reprint of 1969 original.
  * [Gal12] Steven D. Galbraith.  Mathematics of public key cryptography.  Cambridge University Press, Cambridge, 2012.
  * [Koh96] David Kohel.  Endomorphism rings of elliptic curves over finite fields.  PhD thesis, University of California, Berkeley, 1996.
  * [Sch95] René Schoof.  Counting points on elliptic curves over finite fields.  Journal de théorie des nombres de Bordeaux, 7(1):219–254, 1995\.
  * [Sil09] Joseph H Silverman.  The Arithmetic of Elliptic Curves, volume 106.  Springer, 2009.
  * [Sta73] H. M. Stark.  Class-numbers of complex quadratic fields.  In Modular functions of one variable, I (Proc. Internat. Summer School, Univ. Antwerp, Antwerp, 1972), volume Vol. 320 of Lecture Notes in Math., pages 153–174. Springer, Berlin-New York, 1973\.
  * [Sut13] Andrew V. Sutherland.  On the evaluation of modular polynomials.  In ANTS X—Proceedings of the Tenth Algorithmic Number Theory Symposium, volume 1 of Open Book Ser., pages 531–555. Math. Sci. Publ., Berkeley, CA, 2013.
  * [The23] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 10.2), 2023.  https://www.sagemath.org.
  * [V7́1] Jacques Vélu.  Isogénies entre courbes elliptiques.  C. R. Acad. Sci. Paris Sér. A-B, 273:A238–A241, 1971.