extfieldsofstudy:
Computer Science
Mathematics

text:
Conditional Importance Sampling for Off-Policy Learning

The principal contribution of this paper is a conceptual framework for off-policy reinforcement learning, based on conditional expectations of importance sampling ratios. This framework yields new perspectives and understanding of existing off-policy algorithms, and reveals a broad space of unexplored algorithms. We theoretically analyse this space, and concretely investigate several algorithms that arise from this framework.

Importance sampling often suffers from high variance, especially when multi-step trajectories are considered. This has motivated the study of a wide range of variance reduction techniques in off-policy reinforcement learning. These techniques include importance weight truncation [Munos et al., 2016, Espeholt et al., 2018 Preliminary work. Under review by AISTATS 2020.
In this paper, we propose a new framework for variance reduction in off-policy learning, conditional importance sampling (CIS), based on taking conditional expectations of importance weights. This framework is motivated by the observation that when estimating a return off-policy using standard importance sampling, every action along a trajectory contributes to the importance weight, even if the action had no effect on the return observed. Intuitively, it would be preferable for the importance weight to depend only on the return itself; if two policies generate similar distributions of returns, there should be no need to perform importance weighting at all. As just one application of the CIS framework, we make this insight precise, and introduce return-conditioned importance sampling (RCIS), a new off-policy evaluation algorithm. Concretely, using notation introduced formally in Section 2, given a random return G, RCIS uses conditional importance weights of the form which integrates out noise in the trajectory that is irrelevant in determining the return, leading to a lower variance importance weight.
However, return is just one possible variable to condition on. The central insight of the CIS framework is that there is large space of variables that the importance weights can be conditioned on, with each choice leading to a different off-policy algorithm. In the remainder of the paper, we give a mathematical description of the general CIS framework, which then arXiv:1910.07479v1 [cs.LG] 16 Oct 2019 allows us to make several further contributions: (i) We compare and analyse the statistical properties of CIS algorithms based on properties of the conditioning variables. (ii) We study several specific instantiations of algorithms from this framework, including RCIS and state-conditioned importance sampling (SCIS, given by conditioning on the states visited by a trajectory at each timestep). (iii) We develop practical versions of these algorithms, based on learning the conditioned importance weights in a supervised manner.

Notation
Consider a Markov decision process (MDP) (X , A, γ, P, R) with finite state space X , finite action space A, discount factor γ ∈ [0, 1), transition kernel P : X × A → P(X ), reward distribution probability mass function R : R × X × A → R, and initial state distribution ν ∈ P(X ) 1 .
Given a Markov policy π : X → P(A), the distribution of the process (X t , A t , R t ) t≥0 itself is defined by X 0 ∼ ν, A t |X 0:t , A 0:t−1 , R 0:t−1 ∼ π(·|X t ), R t |X 0:t , A 0:t , R 0:t−1 ∼ R(·|X t , A t ), and X t+1 |X 0:t , A 0:t , R 0:t ∼ P (·|X t , A t ) for each t ≥ 0. We denote the full trajectory (X t , A t , R t ) t≥0 by τ , and use the notation τ s:t to denote the partial trajectory (X s , A s , R s , X s+1 , . . . , X t ). We denote the distribution of τ under the policy π by η π , and denote the distribution of τ s:t by η π s:t for any 0 ≤ s ≤ t. We will also denote the conditional versions of these distributions given (X 0 , A 0 ) = (x, a) in the manner η π | (x,a) .

Policy evaluation
The evaluation problem with target policy π : X → P(A) is defined as estimation of the Q-function for all (x, a) ∈ X × A. The fundamental result of value-based RL is that the Q-function in Expression (1) satisfies the Bellman equation T π Q π = Q π [Bellman, 1 With some care, it is possible to show through the use of measure theory that versions of many results in this paper hold in much greater generality, such as in classes of MDPs with continuous state and/or action spaces. For the sake of accessibility and clarity of exposition, the main paper focuses on the discrete case, but we discuss how these results generalise in Appendix C.2 for the interested reader.
1957], where the one-step Bellman evaluation operator T π : R X ×A → R X ×A is defined by for all Q ∈ R X ×A and (x, a) ∈ X × A. Since T π is a contraction in (R X ×A , · ∞ ), Q π is its unique fixed point, and repeated application of T π to any initial Q-function will converge to Q π . An evaluation algorithm may therefore seek to (approximately) perform a recursion of the form Q k+1 ← T π Q k (k ≥ 1), with the aim of converging to Q π . More general classes of contractive operators with fixed point Q π can also be considered, such as the n-step Bellman operator (for n ≥ 1), given by and the Retrace operator [Munos et al., 2016].

Off-policy policy evaluation
Exact computation of the expectations defining the above operators is often intractable, and so Monte Carlo 2 estimators based on trajectories sampled from the environment are used [Bertsekas and Tsitsiklis, 1996, Szepesvári, 2010, Sutton and Barto, 2018. Further, it is often desirable, or necessary, to use trajectories sampled from a different distribution η µ , based on a behaviour policy µ : X → P(A); in such cases, the problem is said to be off-policy.
A common estimator for the application of the n-step Bellman operator (T π ) n to a Q-function Q at a specific state-action pair (x, a) ∈ X × A is given by sampling τ 0:n from η µ 0:n | (x,a) , and computing a bootstrapped return, defined bȳ and an importance-weighting correction term, defined generally for 1 ≤ s ≤ t by and forming the ordinary importance sampling (OIS) estimatorḠ OIS;π,µ 0:n := ρ π,µ 1:n−1Ḡ π 0:n .
Much research in off-policy learning is concerned with constructing such estimators, with desirable statistical properties, such as low variance and consistency. Throughout, we will assume that supp(π(·|x)) ⊆ supp(µ(·|x)) for all x ∈ X , (SC) a mild assumption that is sufficient for unbiased importance sampling, which is satisfied by exploratory behaviours such as ε-greedy. We refer to this as the support condition; intuitively, this ensures that any trajectory that can arise by following π is also realisable under µ.

Preliminary analysis
As a warm-up and motivation for the general conceptual framework we present in the next section, we analyse some commonly-used off-policy Monte Carlo estimators.

Ordinary importance sampling
We begin with a formal proof of the unbiasedness of the OIS estimator, a well-known result in the literature. In this and many results that follow, we will be interested in distributions over trajectories conditioned on some initial state-action pair (x, a) ∈ X × A; this will be present in the notation, but we avoid continuously mentioning it in the text for brevity. We examine the proof of this result in some detail, since it will be informative for the original results that follow. Proofs of other results in the paper are given in Appendix A.
Proposition 3.1. Assume the support condition (SC) holds. For a trajectory drawn from η µ | (x,a) , the OIS estimator in Expression (4) is unbiased for the output of the n-step return operator (T π ) n . That is, Proof. We first observe that the ratio of policy probabilities that appears within the factor ρ π,µ 1:n−1 can also be interpreted as the importance ratio for the conditional trajectory distributions η µ 0:n | (x,a) and η π 0:n | (x,a) , as the following calculation shows: =ρ π,µ 1:n−1 .
Noting also that the termḠ π 0:n in Equation (5) is simply a function of the random truncated trajectory τ 0:n , we may now appeal to standard importance sampling theory, using the notation Ψ(τ 0:n ) =Ḡ π 0:n , to obtain as required.
We highlight two points. Firstly, note that the argument above did not depend on any special structure of G π 0:n , other than that it was expressible as a function of the truncated trajectory τ 0:n ; this analysis is therefore readily applicable to many other functions of the trajectory beyond n-step returns, as we will see in Section 4. Secondly, note that within the proof we showed that the familiar product of ratios of action probabilities (7) is precisely equal to the ratio of trajectory probabilities (6), a fact we will use in the remainder of the paper.

Per-decision importance sampling
Whilst the OIS target of Expression (4) is straightforwardly understood, it often has very high variance. A popular variant that aims to address this shortcoming is given by the per-decision importance sampling (PDIS) [Precup et al., 2000] target: G PDIS;π,µ 0:n = n−1 t=0 ρ π,µ 1:t γ t R t + ρ π,µ 1:n−1 γ n V (X n ; π) , (8) The intuition behind this estimator is that each individual reward is only weighted by importance ratios for actions that preceded the reward, it being unnecessary to account for the off-policyness of future actions. This estimator is also unbiased, and is described in the literature as often having lower variance than the OIS estimator. We show below that each constituent term of the PDIS estimator is lower variance than the counterpart term in the OIS estimator.
Proposition 3.2. For general policies µ and π, each term in the PDIS estimator has variance at most that of the corresponding term in the OIS estimator. That is, The proof technique provides the main insight giving rise to the conditional importance sampling framework described in the next section, so we provide a sketch below. The fundamental idea is to show that each term in the estimatorḠ PDIS;π,µ 0:n can be viewed as a conditional expectation of a corresponding term in the estimator G OIS;π,µ 0:n ; we can then use the following well known variance decomposition for any two real-valued random variables Z 1 and Z 2 with finite second moments: with the inequality strict whenever Z 1 is not σ(Z 2 )measurable, or not a function of Z 2 , using non-measuretheoretic terminology. This idea is related to the notion of Rao-Blackwellisation, a variance reduction technique which is ubiquitous across statistics and signal processing [Casella and Berger, 2002, Särkkä, 2013, Robert and Casella, 2013.
To apply this result to prove Proposition 3.2, consider the term ρ π,µ 1:n−1 γ t R t from the OIS estimator, and the term ρ π,µ 1:t γ t R t from the PDIS estimator. A direct calculation yields The final equality follows from the general fact that when the support condition (SC) is satisfied, the expectation of an importance weight with respect to the importance sampling distribution is 1. Thus, the PDIS term really is a conditional expectation of the corresponding term in the OIS estimator. The bootstrap terms in the PDIS and OIS estimators are in fact equal, and hence the result of Proposition 3.2 follows.
We are now ready to generalise the reasoning presented in this section, and present the main conceptual framework of the paper.

Conditional importance sampling: Theory
The proof of Proposition 3.2 highlights an important observation; the PDIS estimator in Expression (8) can be interpreted as taking particular conditional expectations of the OIS estimator in Expression (4) as a means of reducing variance. It will turn out that this process of taking conditional expectations is a productive way of both discovering new off-policy importance sampling methods, and also understanding their statistical properties. For this reason, we take some time to spell out this logic more generally.
Consider the problem of estimating E η π 0:n | (x,a) [Ψ(τ 0:n )], for some function Ψ of the truncated trajectory τ 0:n , via importance sampling. A standard importance estimator, taking τ 0:n ∼ η µ 0:n | (x,a) , is given by If Ψ extracts an n-step return from the trajectory, this yields the standard OIS estimator, and if Ψ extracts a single reward R t , this yields an individual term from the OIS estimator. In Section 3, we saw that in this latter case, a way of reducing the variance of the resulting estimator is to take the conditional expectation given the random variables (X 0:t , A 0:t , R t ), essentially because Ψ(τ 0:n ) = R t is expressible as a function of (X 0:t , A 0:t , R t ), and the trajectory importance weight is not expressible as a function of (X 0:t , A 0:t , R t ), allowing some extraneous sources of noise to be integrated out. We now formalise this in greater generality.
Definition 4.1. Given a functional Ψ of a trajectory τ 0:n , we say that Ψ factors through another functional Φ if there exists a third function h (independent of the MDP) with Ψ = h • Φ, or equivalently, if Ψ(τ 0:n ) can be written as a function of Φ(τ 0:n ) for all values of τ 0:n . We say that Φ is a sufficient conditioning functional (SCF) for Ψ.
This notion of sufficient conditioning functionals suggests the following general framework for constructing off-policy estimators, generalising the perspective of PDIS given in the previous section.

Conditional importance sampling.
Given a target functional Ψ(τ 0:n ), select an SCF Φ for Ψ and construct the estimator Through different choices of Ψ and Φ, this yields a wide space of possible off-policy learning algorithms; we refer to this as the conditional importance sampling (CIS) framework. We begin with some basic analysis of the properties of these estimators.
Proposition 4.2. Given a trajectory functional Ψ and an associated SCF Φ, the estimator in Expression (11) is unbiased for E η π [Ψ(τ 0:n )]. Further, its variance is no greater than that of the OIS estimator in Expression (10).
Having established our framework and some basic properties of the associated estimators, we now provide several examples to aid intuition. Examples: • By taking Ψ(τ 0:n ) = Φ(τ 0:n ) =Ḡ π 0:n , we recover the usual OIS estimator.

Orderings and optimality
Given the wide space of possible SCFs Φ for a given target Ψ encompassed by the CIS estimators in Expression (11), we now turn our attention to understanding the statistical properties of these estimators. 3 There is a natural preorder on SCFs for a given target Ψ, given by specifying that for two such conditioners The relation Φ 1 Φ 2 thus makes rigorous the notion "all information encoded about the trajectory τ 0:n by Φ 1 (τ 0:n ) is also encoded by Φ 2 (τ 0:n )".
A second preorder that is particularly relevant to studying the statistical properties of off-policy estimators is that of having lower variance, denoted 1:n−1 Φ 2 (τ 0:n ) ). Note that whilst the preorder is invariant to the MDP and policies π and µ in question, the variance preorder V is not. This potentially complicates our variance analysis; however, the following proposition establishes a useful relationship between these two preorders.
Proposition 4.3. For any given MDP, and pair of policies π and µ, and target functional Ψ, the variance preorder refines the inclusion preorder. That is, for The connection established in Proposition 4.3 will allow us to address the question of optimality: which SCFs for Ψ yield the lowest variance estimator given in Expression (11)? Proposition 4.4. An SCF for Ψ for which the associated estimator in Expression (11) achieves minimal variance is Ψ itself.
This result gives guidance for choosing a conditioner Φ for a given target Ψ; we study several such algorithms in more detail in Section 5.
3 It is possible to get a slightly more streamlined analysis by working with sigma-algebras, rather than functions of the random trajectory. We restrict the exposition in the main paper to the functional perspective for accessibility and simplicity, but provide a measure-theoretic perspective in Appendix C.1.

Variance
Estimation Difficulty Bias Uncorrected Figure 1: Schematic illustration of three traded-off quantities associated with CIS estimators.

Beyond sufficient conditioning functionals
So far, we have enforced the condition that if Ψ is a target functional, a conditioner Φ used to form the conditional importance-weighted term in Expression (11) should be such that Ψ(τ 0:n ) is expressible in terms of Φ(τ 0:n ). This condition ensures that the resulting estimator is unbiased, as shown in Proposition 4.2. However, relaxing this condition gives an even greater collection of off-policy estimators. Such estimators formed with functionals Φ which are not SCFs for Ψ will generally be biased, but in many circumstances may be particularly low-variance, allowing for a biasvariance trade-off to be made. Example: • By taking Ψ(τ 0:n ) = n−1 t=0 γ t R t + γ n V (X n ; π), and Φ(τ 0:n ) = 0 (i.e., a function independent of the trajectory), we recover n-step uncorrected returns, popularly used in deep reinforcement learning.

Trade-offs in bias, variance, and estimation difficulty
We now discuss the various trade-offs inherent within the choice of Φ required by the CIS framework. Proposition 4.2 shows that any Φ that is an SCF for Ψ yields an unbiased off-policy estimator. As described in Section 4.2, choosing Φ which is not an SCF for Ψ generally results in the introduction of bias, but may also offer a further substantial reduction in variance. In addition, there is the question of whether for a given Φ, the importance weight above is available analytically (as in the case of per-decision importance sampling, for example), or whether the weight itself must be estimated, as is the case for several concrete CIS algorithms, RCIS and SCIS, which we describe in Section 5. Figure 1 schematically illustrates the trade-offs between these three quantities made by several algorithms in the CIS framework.

Conditional importance sampling: Algorithms
Having set out the CIS framework, we now investigate several novel algorithms which naturally arise from it.

Return-conditioned importance sampling
Consider taking the n-step truncated return as our target: Ψ(τ 0:n ) = n−1 t=0 γ t R t , and following the optimality result of Proposition 4.4, taking the conditioner Φ = Ψ to be this return too. This yields a conditional importance weight of the form It is possible to express this conditional importance weight more directly, as the following result shows.
Proposition 5.1. Fix a target policy π. For a given policy µ let p µ | (x,a) be the probability mass function of That is, the optimal conditional importance weight for the n-step bootstrapped return is the ratio of the probabilities of the returns themselves under the target and behaviour distributions. This is appealing since it shifts the focus from (potentially irrelevant) policy probabilities directly to probabilities of generating a certain return value. Due to this property, we term the corresponding estimator of the full bootstrapped return the return-conditioned importance sampling (RCIS) estimator, which is given by: where G = n−1 t=0 γ t R t . We note that several further variations of return-conditioned importance sampling are available, such as using an importance weight conditioned on the entire bootstrapped return.
There are strong connections here to distributional reinforcement learning [Morimura et al., 2010, Bellemare et al., 2017, Dabney et al., 2018, in which approximations to return distributions are learnt directly through interaction with the environment. An interesting question for future work is whether progress can be made in distributional RL through estimation of these ratios, rather than the individual distributions directly.

Reward-conditioned and state-conditioned importance sampling
The previous section establishes return-conditioned importance sampling as the optimal (with respect to estimator variance) unbiased means of importance weighting an entire return. However, this leaves open the question as to whether improvements can be made by importance weighting the individual terms of a return separately, as in per-decision importance sampling. If we interpret each reward R t in the returnḠ π 0:n as a target in its own right, Proposition 4.4 shows that the corresponding optimal unbiased importance weight is We refer to the use of these weights as rewardconditioned importance sampling. Another estimator of interest that we mention due to its connections with existing off-policy evaluation algorithms and modelbased reinforcement learning is given by (suboptimally) conditioning on the tuple (X t , A t , R t ) instead of R t itself. In this case, we obtain the importance weight which can be shown to be equal to where p π t | (x,a) represents the distribution over the state at time t starting at state-action pair (x, a) and following π thereafter. Thus, learning this conditional importance weight is closely related to learning the difference between the two transition models p t,µ and p t,π . For this reason, we refer to the use of the importance weight in Expression (13) as state-conditioned importance sampling (SCIS). There are also close ties with marginalised importance sampling [Xie et al., 2018[Xie et al., , 2019, which estimates a similar quantity, but by focusing on learning these transitions distributions separately, rather than their ratio directly, as well as the work of Liu et al. [2018], which learns a ratio of different but related distributions via a Bellman equation.

Importance weight regression
A crucial practical question about the conditional importance weights appearing in Equations (12) and (14) (and indeed in the general CIS estimator in Equation (11)), is how these should be estimated when they are not available analytically. A general approach is given by solving the following regression problem: In words, we attempt to predict the trajectory importance weight via the function f θ parameterised by θ, using solely the information contained in Φ(τ 0:n ). In addition, a single regressor could be used across all initial state-action pairs, taking these quantities as additional input (i.e., f θ (x, a, Φ(τ 0:n ))), and thus allowing for generalisation across actions and states. In cases where global minimisation of this objective isn't possible, it may be desirable to modify the objective to take into account the magnitude of the target term Ψ(τ 0:n ) (e.g. the n-step return) to reduce the variance of the resulting approximate solution. One such modified objective takes the form The following proposition gives theoretical grounding to these objectives. (15) and (16) is given by

Experiments
To complement the CIS framework and the theoretical analysis conducted in earlier sections, we provide several simple illustrative experiments that demonstrate (i) that CIS algorithms can deliver substantial variance reduction, and (ii) that the regression approach of Section 5.3 can be used to obtain practical implementations of CIS algorithms. We exhibit results on a classic chain environment, with both tabular and linear function approximation methods; full experiment specifications are given in Appendix B.

Operator estimation
We begin with the task of off-policy estimation of the application of the n-step Bellman operator (T π ) n to a fixed Q-function through trajectories generated by following the behaviour policy µ. This serves as a precursor for off-policy evaluation, and allows us to disentangle the variance reduction achieved by conditional importance sampling from compounding bootstrapping effects.
Results are shown for a chain environment in Figure 2. We plot MSE for both OIS and PDIS, as well as conditional importance sampling versions of these algorithms, RCIS and SCIS, with the conditional importance weights provided by a pre-computed oracle. The use of an oracle allows us to separate the variance reduction effects of conditional importance sampling from the potential errors introduced by the regression approach described in Section 5.3. In each of the four sub-plots of Figure 2, we vary one property of the estimation problem, to illustrate how performance of the under-study methods changes. In all cases, we plot results for three different settings of the parameter in question, with solid lines corresponding to low values of this parameter, and finely-dashed lines corresponding to high values of the parameter; see Table 1 for precise values. "Noise" refers to the transition noise added to the chain, β controls mismatch between the target π and behaviour µ policies, by replacing the target with a mixture βπ + (1 − β)µ, and "extra actions" describes how many extra (redundant) copies of each action are added to the environment. In all cases, the CIS methods outperform their existing counterparts, with more pronounced improvements in the presence of larger n, more transition noise, greater off-policyness, and high level of action redundancy.

Policy evaluation
We now consider the full task of off-policy policy evaluation using n-step returns along trajectories generated by the behaviour policy, with importance weighting provided by existing and new CIS algorithms. We report results for the same chain environment as for the operator estimation experiments in Figure 3, with varying levels of transition noise and off-policyness as described in Table 1. We give results for CIS algorithms using a conditional importance weight oracle, and online variants estimating conditional importance weights by solving the empirical version of Expression (15) (based on the observed trajectories) exactly for each different value of the functional observed. We show results for tabular evaluation, as well as versions using tile-coding linear function approximation [Sutton and Barto, 2018] (full details in Appendix B.3). At a high level, we observe that whilst oracle versions of CIS algorithms outperform those that learn the conditional importance weights online, the online versions still generally give a noticeable improvement over their non-conditional versions. These results serve as a proof of concept that practical, online versions of the CIS algorithms introduced in Section 5 can improve over non-conditional baselines. We expect that with further research into   regression methods that can accurately approximate conditional expectation of the from Expression (11), the gap between oracle and online versions of CIS algorithms can be narrowed.

Discussion
We have unified several existing importance sampling algorithms via a new conceptual framework based on conditional expectations of importance weights, allowing for straightforward analysis and comparison, in addition to the development of new algorithms.
There remain many interesting investigations to be carried out towards theoretically and empirically understanding how the CIS framework interacts with complementary approaches for variance reduction, such as weighted importance sampling and importance weight truncation. We expect several further directions to prove fruitful for future work, including further exploration of the space of algorithms the CIS framework opens up, scaling up CIS algorithms to work in combination with deep RL architectures, and further investigation into relationships between particular CIS algorithms with other sub-fields of RL (such as RCIS and distributional RL).

APPENDICES: Conditional Importance Sampling for Off-Policy Learning A Proofs
Proposition 4.2. Given a trajectory functional Ψ and an associated SCF Φ, the estimator in Expression (11) is unbiased for E η π [Ψ(τ 0:n )]. Further, its variance is no greater than that of the OIS estimator in Expression (10).
Proof. The proof of unbiasedness follows the logic of Proposition 3.1's proof and the proof for the variance upper bound follows the logic of Proposition 3.2's proof. Beginning with unbiasedness, we make the following calculation: where (a) follows since Φ is an SCF for Ψ (and hence Ψ(τ 0:n ) is fully determined by Φ(τ 0:n )), (b) follows from the tower law of conditional expectations, and (c) follows from standard importance sampling theory.
Proposition 4.4. An SCF for Ψ for which the associated estimator in Expression (11) achieves minimal variance is Ψ itself.
Proof. This follows by first observing that Ψ(τ 0:n ) is a minimal sufficient conditioning functional for Ψ with respect to the ordering induced by ; this is immediate from the definition. Next, since V refines (by Proposition 4.3), we have that Ψ(τ 0:n ) is also a minimal sufficient conditioning functional with respect to V , and the statement follows.
We then decompose , as required.
Proposition 5.2. A global minimum for each of the objectives in Expressions (15) and (16) is given by Proof. We begin by restating Expression (15), and use the tower law of conditional expectation as follows: The inner conditional expectation is of the form E Y [(z − Y ) 2 ]; viewed as a function of z, it is well known that the minimiser of such an expression is z = E[Y ]. Thus, for a fixed value of Φ(τ 0:n ), the optimal value of f θ (Φ(τ 0:n )) is given by Therefore, the global optimiser of Expression (15) is given precisely by the function as required. For Expression (16), in a similar manner we can write the following: with the equality following from the fact that Φ is a sufficient conditioning functional for Ψ. Now we may proceed in an identical manner to that for Expression (15), and the claim follows.

B.1 Environment
Chain. We use a 6-state chain environment, with absorbing states at each end of the chain. Two actions, left and right, are available at each state of the chain. Transitions corrupted with p% noise means that with probability p, a transition to a uniformly-random adjacent state (independent of the action taken) occurs. Each non-terminal step incurs a reward of +1, whilst reaching an absorbing state incurs a one-off reward of +10, and the episode then terminates. The initial state of the environment is taken to be the third state from the left. Figure 4 provides an illustration. Figure 4: Illustration of the chain environment.

B.2 Other experimental details: operator estimation
Throughout, the discount factor is taken to be γ = 0.99, and the Q-function used to form the target (T π ) n Q has its entries sampled independently from the N (0, 0.1) distribution. The policies π and µ are drawn independently, with each π(·|x) and µ(·|x) drawn independently from a Dirichlet(1, . . . , 1) distribution. Default values of parameters are taken as n = 5, the transition noise level is set to 10%, and the learning rate is set to 0.1, and 100 repetitions of each experiments are performed to compute the bootstrapped confidence intervals.

B.3 Other experimental details: policy evaluation
The environment and default parameters are exactly the same as in the operator estimation experiments, with the exception that the Q-function is initialised so that all coordinates are 0, and n = 3. We estimate bootstrap confidence intervals using 500 repetitions of each experiment. In the linear function approximation experiments, we use a version of tile-coding [Sutton and Barto, 2018]; the specification parametrisation we use is as follows. For a chain of length K, we take a weight vector w = (w k,a |k ∈ [K − 1], a ∈ A) ∈ R (K−1)×|A| . Labelling the states of the chain x 1 , . . . , x K , we parametrise Q(x 1 , a) by w 1,a , Q(x K , a) by w K−1,a , and Q(x k , a) by 1 2 w k−1,a + 1 2 w k,a , for each a ∈ A and each 1 < k < K; this is illustrated in Figure 5. The weight vector is initialised with all coordinates equal to 0 in all experiments.

Termination Termination
Figure 5: An illustration of the tile-coding scheme used in the linear function approximation scheme; the figure shows how feature weights (for each action) are allocated states. The value prediction at each state is given by averaging the weights allocated to the state.

C Extending the CIS framework
C.1 A measure-theoretic perspective on conditional importance sampling In this section, we give a measure-theoretic treatment of the conditional importance sampling framework introduced in Section 4 of the main paper. We do not provide any fundamentally new results relative to the main paper, but we believe the measure-theoretic exposition gives a useful perspective, and may be useful for future work.
We begin by returning to the trajectory importance-weighted estimator given in Expression (10) in the main paper: This expression weights the target quantity Ψ(τ 0:n ) by the importance weight associated with the proposal distribution η µ 0:n and the target distribution η π 0:n . A conditional importance sampling estimator is formed by taking a function Φ that in the language of the main paper, is a sufficient conditioning functional for Ψ, and forming the new estimator E η π 0:n | (x,a) (τ 0:n ) η µ 0:n | (x,a) (τ 0:n ) Φ(τ 0:n ) Ψ(τ 0:n ) .
Proposition 4.2 then shows that the variance of the conditioned estimator is no greater than that of the trajectory-weighted estimator, and, roughly speaking, in many cases it is strictly lower.
Whilst this perspective of conditioning on functionals Φ of the trajectory is conceptually straightforward and clearly hints at how such techniques can be implemented in practice, as described in Section 5.3, there are some subtleties introduced by this perspective that make the analysis of the method less straightforward. One such case is illustrated by the following example: consider two sufficient conditioning functionals Φ 1 and Φ 2 for a target Ψ, which happen to be related according to the identity Φ 1 (τ 0:n ) = 2Φ 2 (τ 0:n ) for all τ 0:n . Intuitively, Φ 1 and Φ 2 encode the same information about τ 0:n , and thus the estimators they produce are identical. We might therefore like to be able to treat Φ 1 and Φ 2 as "identical" in our analysis, and yet this is made difficult by the focus of the analysis on functionals of the trajectory. This is related to the need to work with preorders in Section 4.1, rather than the perhaps more familiar notion of partial orders. One route around this difficulty is to define an equivalence relation over functions of the trajectory, rigorously encoding the notion of "captures the same information about τ 0:n ", and then to work instead with equivalence classes of trajectory functionals under this relation. However, this has the potential to be very unwieldy, and further, it turns out this is essentially equivalent to a much more familiar collection of objects from measure theory, known as sigma-algebras. For formal definitions and background on sigma-algebras, see for example Billingsley [1995]. We note that technically speaking, it is necessary to constrain functionals of the trajectory to be measurable; we do not mention this condition further in this section, but return to it in Appendix C.2 when describing the application of the conditional importance sampling framework to more general classes of MDPs. For a general random variable Z, we write F Z for the sigma-algebra generated by Z; in the discussion that follows, all random variables will be defined over the same probability space, which we therefore suppress from the notation in what follows.
The counterpart to a sufficient conditioning functional Φ is a sufficient conditioning sigma-algebra (SCSA) F , which is defined as being a sigma-algebra over the same measurable space as F τ0:n , with the property that F Ψ(τ0:n) ⊆ F . With this definition, a functional Φ is an SCF if and only if F Φ(τ0:n) is an SCSA. The corresponding importance sampling estimator is then given by E η µ | (x,a) η π 0:n | (x,a) (τ 0:n ) η µ 0:n | (x,a) (τ 0:n ) F Ψ(τ 0:n ) .
The analogue of the preorder over conditioning functionals is the inclusion partial order ⊆ over sigma-algebras; we have Φ 1 Φ 2 if and only if F Φ1(τ0:n) ⊆ F Φ2(τ0:n) . Further, if for two conditioning functionals Φ 1 and Φ 2 we have Φ 1 Φ 2 and Φ 2 Φ 1 (that is, roughly speaking, Φ 1 and Φ 2 encode the same information about the trajectory), then we have F Φ1(τ0:n) = F Φ2(τ0:n) . Thus, working with sigma-algebras eliminates the issue of several conditioning objects representing exactly the same information about the trajectory.

C.2 Generalising the conditional importance sampling framework to other classes of MDPs
We have restricted the presentation in the main paper to MDPs with finite state and action spaces and reward distributions with finite support for ease of exposition, and to avoid having to introduce measure-theoretic terminology such as Radon-Nikodym derivatives to deal with more general classes of MDPs. Nevertheless, the framework described in the main paper applies much more generally, such as for certain classes of MDPs with continuous state and/or action spaces. In this section, we briefly describe how the framework generalises to these settings. The aim is not to be exhaustive, but rather to indicate how key concepts change when moving away from the assumptions of the main paper; for a rigorous treatment of the measure-theoretic issues that arise in MDPs with more general state and action spaces, see Bertsekas and Shreve [2007].
Consider now an MDP with a general state space X and action space A, each equipped with a sigma-algebra, and consider R, the domain of rewards in the MDP, to be equipped with its usual Borel sigma-algebra. Given


s2fieldsofstudy:
Computer Science
Mathematics

text:
Sensor-Seeded Cryptographically Secure Random Number Generation

Random numbers are essential to generate secret keys, initialization vector, one-time pads, sequence number for packets in network and many other applications. Though there are many Pseudo Random Number Generators available they are not suitable for highly secure applications that require high quality randomness. This paper proposes a cryptographically secure pseudorandom number generator with its entropy source from sensor housed on mobile devices. The sensor data are processed in 3-step approach to generate random sequence which in turn fed to Advanced Encryption Standard algorithm as random key to generate cryptographically secure random numbers.

INTRODUCTION
Information security algorithms aim to ensure the confidentiality, integrity and availability of data that is transmitted along the path from sender to receiver. All the security mechanisms like encryption, hashing, signature rely on random numbers in generating secret keys, one time pads, initialization vector, and nonce respectively. The random numbers are generated either from True Random Number Generator (TRNG) or Pseudo Random Number Generator (PRNG). TRNG uses entropy source that have natural randomness to produce random bit sequence. PRNG uses deterministic algorithm that takes a seed value to produce random sequence that are easily predictable. Hence PRNG require their seed to be more secure and unknown to attacker. Seed values can be obtained from any randomness rich sources like clock pulse, user activity, interrupts, time, etc.
To overcome the issue of predictability one can use sensor data as seeds for PRNG. Sensors are used to measure various physical parameters like pressure, temperature, motion, etc. These physical parameters exhibit randomness. Hence the values recorded by these sensors are a great source of random seeds for PRNG. The lack of security within the random number generation process would compromise the entire system as long as an attacker could easily infer the key. Hence the sensor source data must be processed before they are fed to PRNG that prevents attacker to gain adversarial control over the source of seed.
Advanced Encryption Standard uses a symmetric key algorithm meaning same key is used for encryption and decryption. It uses 128-bit fixed length message block and 128-bit key with 10 cycles of repetition. AES is the widely used security algorithm that can be implemented easily on both hardware and software.

II. PRNG IMPLEMENTATIONS
PRNG requires the seed value to be fed to a deterministic algorithm. Many deterministic algorithms are proposed, some of widely used algorithms are Blum-Blum-Shub algorithm uses where X 0 is seed value and M =pq, p and q are prime.
Linear congruential Generator uses where is the seed value. Mersenne Prime Twister uses range of , where that outputs sequence of 32-bit random numbers.

III. SENSOR-SEEDED PRNG
Some of PRNGs uses clock pulse of computer system as seeds. However they are obtainable by hacker making them vulnerable. The idea proposed is to use sensor data from mobile devices that has high source of entropy. The sensor data are collected from mobile device sensors and they are used as seeds in any one of the deterministic algorithm mentioned above. In our paper the accelerometer of Smartphone is used to collect data. An accelerometer is a sensor which measures the tilting motion and orientation of a mobile phone. The dataset collected is recorded value of accelerometer of a single day usage. Though they produce good quality randomness they are not enough secure in their implementation. When an attacker gains control of sensor or knows the sensor data the output of PRNG is compromised. Attacker may move the mobile in same orientation to generate the same seed value. Also the accelerometer data are available to the mobile's operating system which can be obtained by any malicious software.

IV. SECURING SENSOR SEEDS
To make the sensor data suitable as seeds for generating random sequences we must first remove the predictable patterns present in them and secondly resolving the collinearity problem that arise from multiple sensors housed on same device.

V. REMOVING PREDICTABLE PATTERNS
The predictable patterns in sensor data provide valuable information to attacker to control the movement patterns of mobile phone. These patterns are removed by 3 step approach namely  Wash  Rinse  Spin The above three steps can be represented in the Fig 1. below.

Fig.1 Schematic Diagram of Wash-Rinse-Spin A. Wash
The sensor data used for this research was collected from Smartphone's accelerometer that measures the coordinates of phone in X-, Y-and Z-axis. These data are dependent upon the position of the mobile phone held by user and are easily predictable. These patterns are easily predictable and pose a risk. The recorded accelerometer data along X-axis is shown in Fig.2. Such collected sensor data are very weak source to produce random numbers. To remove those predictable patterns that are seen as slow drifts, the data are preprocessed. Preprocessing is done in such a way that those slow drifts are washed away. Such processed sensor data are less likely to be useful to hacker in determining the generated random numbers.
The Smartphone may be held idle for sometime or held at same position for sometime or periodically used in same position. These slow drifts causes slight variations in mean and variance of the sequence. Such variations lead to nonstationarity. The first step in processing is to remove those slow drifts by differentiating the data until all the nonstationarity are removed.

Fig.2 Raw Sensor Data
Differentiating the sensor data produces First order derivative that sufficiently removes nonstationarity. If nonstationarity still remains, differentiation can be repeated until threshold stationarity is obtained. The result is shown in Fig.3. As can be seen from the figure Fig.3, the sensor data shows absence of any minor drifts.

B. Rinse
Slow drifts are removed in the previous step by differentiation. Next step aims to dust away the soap traces in the washed data. The washed data are free from drifts however still contain predictable patterns and bare spots. They need to be removed completely by further inducing randomness in the data. The randomness is not introduced into the data directly. They are converted into complex numbers using Fast Fourier Transform with complex exponentials given by = The complex number has two parts namely real and imaginary. The real number denotes the sine wave magnitude. To add further randomness to data, the imaginary number is replaced by new random number. This modified complex numbers are converted back to sensor data i.e. from frequency domain to time domain using Inverse Fast Fourier Transform. This results in rinsed senor data represented in Fig.4. After rinse step, 8-bit integer is taken as seed value to generate the Pseudo random numbers.

Fig.4 Rinsed Sensor Data C. Spin
The data sequence with added randomness is produced in the rinse step. This is now used as seed for a RNG to produce required quantity of random numbers that find its application in password creation, key exchange, encryption, connection establishment, etc. The data sequence is broken down into sizes depending on the PRNG used. For our testing Linear congruential generator was used.

VI. CRYPTOGRAPHICALLY SECURE PRNG (CSPRNG)
The random bit sequence generated from above process may exhibit randomness but does not have good quality randomness to be used for highly secure applications. For example some applications require nonces to be unique. However encryption keys for secure application require it to be of good quality with rich entropy. Next Bit test requires that given first k bits of random sequence it is infeasible for any polynomial time algorithm to determine the k+1th bit of random sequence.
CSPRNG must withstand state compromise extension where the current or previous state of generator is exposed to attacker, it is impossible to recreate sequence prior to revelation or future sequence to be generated.
Many PRNGs that pass statistical tests fail to pass these requirements making them unfit for cryptographic algorithms. One way of designing CSPRNG is to use a block cipher with counter mode.

VII. AES IN CTR MODE
AES can be implemented in any of modes-Cipher Block Chaining (CBC), Cipher Feedback (CFB), Output Feedback (OFB), and Counter (CTR). AES uses 128-bit plaintext block and 128-bit, 192-bit, 256-bit key to generate highly secure cipher text.

Fig.5 Schematic Diagram of Wash-Rinse-Spin with AES
Number of rounds of repetition depends on key size chosen. For this paper 128-bit key size is used with 10 cycle repetitions. To make our PRNG as CSPRNG that satisfy the two requirements, the random sequence generated from sensor data is used as random key in AES implementation with Counter mode. The counter can be initially set to any arbitrary value. After 10 cycles of repetition the cipher text produced can be used as random number that exhibits highquality randomness. The random numbers generated have very high period length. AES without CTR mode can result in generating random numbers that may repeat after 2 n/2 rounds. Running AES with Counter mode prevents this problem of producing identical random numbers since the counter value keeps on increasing or decreasing

VIII. NEED FOR TESTING RANDOMNESS
Various statistical tests are available that attempt to compare and evaluate the given sequence with a truly random sequence. It is necessary to test the random sequence before they are deployed in any application to ensure their randomness property is met. Randomness is a probabilistic property; that is, the properties of a random sequence can be characterized and described in terms of probability. The likely outcome of statistical tests, when applied to a truly random sequence, is known a priori and can be described in probabilistic terms. There are an infinite number of possible statistical tests, each assessing the presence or absence of a "pattern" which, if detected, would indicate that the sequence is nonrandom. Because there are so many tests for judging whether a sequence is random or not, no specific finite set of tests is deemed "complete." In addition, the results of statistical testing must be interpreted with some care and caution to avoid incorrect conclusions about a specific generator.
To measure the randomness guaranteed by wash-rinsespin approach the seeds are tested by NIST (National Institute of Standards and Technology) statistical test suite for randomness. This test suite has fifteen different tests that measure various properties of randomness. For our analysis raw sensor data generated sequence, processed sensor data generated sequence, AES generated sequence are compared. These sequences are separately tested under NIST Test suite and results are compared. Though washrinse-spin approach and AES approach provide good results the former fails to pass the next bit test and state compromise extension withstanding.

X. CONCLUSION AND FUTURE WORK
The NIST test results for the random numbers produced by our processed sensor data shows better probability over the random numbers generated by raw sensor data. This ensures that the wash-rinse-spin processing of sensor data are reliable and less vulnerable to be predicted. Raw sensor data have very less entropy and are inadequate to produce secure random numbers. More cyberattacks are launched against mobile devices with the growth of Internet. This technique leverages the weakness by processing and enriching the entropy of sensor data. Such processed sensor data are more suitable for cryptographically secure random number generation. Using AES in counter mode in this approach produces much stringer random numbers as AES still remains unbreakable.
The approach uses only measurement data from single sensor. But practically there are many sensors housed in the environments. The future works may consider collecting and processing multiple sensor data for better improvement. The rinse step involving Fast Fourier Transform can be replaced by any other better technique in inducing the randomness to the sequence. Replacing AES with any other block cipher that guarantees hardness to break can improve the results further.
In summary this approach generates very high secure good quality random sequence that is suitable for applications requiring robustness. Also AES can be implemented in hardware to enhance efficiency of generating random numbers.


Coherent Point Drift Networks: Unsupervised Learning of Non-Rigid Point Set Registration

Given new pairs of source and target point sets, standard point set registration methods often repeatedly conduct the independent iterative search of desired geometric transformation to align the source point set with the target one. This limits their use in applications to handle the real-time point set registration with large volume dataset. This paper presents a novel method, named coherent point drift networks (CPD-Net), for unsupervised learning of geometric transformation towards real-time non-rigid point set registration. In contrast to previous efforts (e.g. coherent point drift), CPD-Net can learn displacement field function to estimate geometric transformation from a training dataset, consequently, to predict the desired geometric transformation for the alignment of previously unseen pairs without any additional iterative optimization process. Furthermore, CPD-Net leverages the power of deep neural network to fit an arbitrary function, that adaptively accommodates different levels of complexity of the desired geometric transformation. Particularly, CPD-Net is proved with a theoretical guarantee to learn a continuous displacement vector function that could further avoid imposing additional parametric smoothness constraint as in previous works. Our experiments verify CPD-Net's impressive performance for non-rigid point set registration on various 2D/3D datasets, even in presence of significant displacement noise, outliers, and missing points. Our code is availabel at https://github.com/nyummvc/CPD-Net.

Existing approaches often solve the registration problem through an iterative optimization process to search the optimal geometric transformation to minimize a pre-defined alignment loss between transformed source point set and target point set [10,[12][13][14]20]. The geometric transformation can be modelled by a specific type of transformation (e.g. thin plate spline) [5], or described as a model-free deformation field [20] where a displacement vector function is defined. The rotation, translation and scaling are often used to model rigid geometric transformation, while the affine and thin plate spline are widely used to model non-rigid geometric transformation. For model-based method, the registration task turns into a searching process for an optimal set of parameters of the model. For model-free method, the registration task turns into to process to determine the displacement field that moves the source point set towards the target one. Regardless the model-based or model-free point set registration approaches, most existing efforts have to start over a new iterative optimization process to determine the geometric transformation. Consequently, the intensive computation in the iterative routine pose great challenges for existing approaches to handle a large scale dataset in real-time application. To address this challenge, we are motivated to develop a learning based approach to generalize its ability from training process to predict the desired geometric transformation to register previously unseen pair of point sets.
In this paper, we proposed a novel approach, named coherent point drift networks (CPD-Net), for unsupervised learning of displacement vector function to estimate a model-free geometric transformation for point set registration. Figure 1 illustrates the pipeline of the proposed CPD-Net which consists of three major components. The first component is "Learning Shape Descriptor'. In this component, the global shape descriptor is learned with a multilayer perceptron (MLP). The second component is "Coherent PointMorph". In this component, we firstly concatenate the point coordinate of source point, the global shape descriptor of source point set, and global shape descriptor of target point set to form a new descriptor for each source point. Three successive MLP takes the new descriptor to Figure 1. Our pipeline. The proposed structure includes three parts: learning shape descriptor, coherent PointMorph, and the alignment Loss. For a pair of source point set S i and target point set G j , we firstly leverage MLPs to learn two global descriptors L S i and L G j . We then concatenate these two descriptors to each coordinate {x k } k=1,2,...,m of source points as the input ([x k , L S i , L G j ]) for PointMorph structure. We further use MLPs to learn the drifts for each source point. Finally we move the source point set by our predicted drifts and define the alignment loss function between target and transformed source point sets for back-propagation. learn the continuous displacement vector field. The third component is "Point Set Alignment". In this component, a loss function is defined to assess the quality of alignment. The main contributions of our proposed method as follows: • This paper introduces a novel Coherent Point Drift Networks (CPD-Net) that can be trained in unsupervised manner, consequently it can be generalized to predict geometric transformation for non-rigid point set registration.
• CPD-Net leverages the power of deep neural network to fit an arbitrary function, that is able to accommodate different levels of complexity of the target geometric transformation for best aligning the pair of point sets.
• The CPD-Net theoretically guarantees the continuity of predicted displacement field as geometric transformation, which naturally eliminate the necessity to impose a parametric hand-crafted smoothness constraint.
• The CPD-Net is free of specific geometric model selection for modeling the desired transformation, which avoids the potential mismatch between the transformation described by specific adopted models and the actual transformation required for point set registration.

Iterative registration methods.
The development of optimization algorithms to estimate the rigid or non-rigid geometric transformations in an iterative routine attracts attention of numerous researchers in decades. The Iterative Closest Point (ICP) algorithm [5] is one successful solution for rigid registration. It initializes an estimation of a rigid function and then iteratively chooses corresponding points to refine the transformation. However, the ICP algorithm is reported to be vulnerable to the selection of corresponding points for initial transformation estimation, and also incapable of dealing with non-rigid transformation. To accommodate the deformation (e.g. morphing, articulation) between a pair of point sets, many efforts were spent in the development of algorithms for a non-rigid transformation. For non-rigid registration, classical previous methods can usually be divided into parametric and non-parametric by the target transformation. As a robust parametric method, TPS-RSM algorithm was proposed by Chui and Rangarajan [7] to estimate parameters of non-rigid transformation with a penalization on second order derivatives. As a classical non-parametric method, coherence point drift (CPD) was proposed by Myronenko et al. [20], which successfully introduced a process of fitting Gaussian mixture likelihood to align the source point set with the target one. With the penalization term on the velocity field, the algorithm enforces the motion of source point set to be coherent during the registration process. Another non-parametric vector field consensus algorithm was proposed by Ma et al. [14]. This algorithm is emphasized to be robust to outliers. Ma et al. proposed the importance to leverage both local and global structures during the non-rigid point set registration in [15]. The existing algorithms achieved great success for the registration task. Even though all these methods state the registration task as an independent optimization process for each single pair of source and target point sets, they greatly inspire us for designing our learning-based system.

Learning-based registration methods.
In recent years, learning-based methods achieved great success in many fields of computer vision [1,17,18,21,25,29,32,33]. Especially recent works started a trend of directly learning geometric features from cloud points (especially 3D points), which motivates us to approach the point set registration problem using deep neural networks by leveraging the possibility of direct learning features from points [4,17,21,24,29,32]. The closest research to this work is the unsupervised non-parametric non-rigid registration of 3D volumetric medical image proposed by Balakr-ishnan et al. [4]. In this research, authors use a voxelMorph CNN architecture to learn the registration field to align two volumetric medical images. Even though, both of our researches engage in learning a non-parametric transformation. In contrast, we discuss a broader task for 2D/3D point set registrations in this paper. In comparison to volumetric data, point clouds have very different characteristics and we target to predict the coherent drifts. Moreover, Our proposed model dose not require additional penalization term on smoothness of predicted transformation. For registration of 2D images, an outstanding registration model was proposed by Rocco et al. [24]. Wang et al. [28] proposed PR-Net for non-rigid point set registration. These works mainly focus on parametric approach for 2D image registration. The parameters of both rigid and non-rigid function (TPS) can be predicted by a CNN-based structure from learning the correlation relationship between a pair of source and target 2D images. Even though these learning-based methods are not exactly designed for solving the point set registration problem, they are closely related to our paper and greatly encourage us to investigate the efficient learningbased structure for model-free point set registration.

Approach
We introduce our approach in the following sections. Firstly we define the learning-based registration problem in section 3.1. In section 3.2, our first module is introduced for learning shape descriptor from a 2D/3D source/target point sets. Section 3.3 illustrates coherent PointMorph module for learning the smooth drifts to align the source point set with the target one. In section 3.4, The definition of the loss function is provided. The model configurations and the settings for training are described in section 3.5.

Problem statement
For iterative methods, the optimization task is defined on a given pair of source and target point sets (S i , G j ). Here, unlike interactive methods, for a given training dataset we need to redefine the new optimization task. We assume the existence of a function g θ (S i , G j ) = φ using a neural network structure, where φ is the coherent drifts for each (sampled) point in source point set. As shown in Figure 1, we demonstrate the overview of our proposed structure. Taking a pair of source and target point sets (S i , G j ) as input, out model compute the coherent point drifts φ based on a set of parameters θ, which are weights in the neural network structure. We further transform the input source points by simply moving the drifts and then, measure the similarity between the transformed source and target point sets as the alignment loss to update θ.
For a given dataset, we use stochastic gradient descent based algorithm to optimize parameters set θ for minimiz-ing the expected loss function: , where L represents a similarity measure. CPD-Net dose not require any ground truth drifts for each point for supervision. For a unseen pair from testing dataset, our model directly predict the desired coherent drifts without an additional iterative process.

Learning shape descriptor
For a given input point set, we firstly learn a shape descriptor that captures representative and deformationinsensitive geometric features. Let (S i , G j ) denotes the input source and target point sets and Figure 2. To address the problem of irregular format of point set, we introduce the following encoding network, which includes t successive multi-layer perceptrons (MLP) with ReLu activation function We use the Maxpool function to extract the orderinvariant descriptors from the input point sets. The readers can refer to PointNet [21] for detailed discussion. One can also use other symmetric operators such as summation, average pooling function and so on. This structure can be easily adapted for 3D point set inputs. Other point signature learning architecture such as PointNet++ [22] can be easily implemented here as well.

Coherent PointMorph architecture
For the next step, we define a PointMorph MLP (multilayer perceptrons) architecture for learning the coherent point drifts to move the source point set towards alignment with the target one as shown in Figure 3. This architecture includes successive multi-layer perceptrons (MLP) with ReLu activation function: {g i } i=1,2,...,s , such that: where v i is the input layer's dimension and v i+1 is the output layer's dimension. Therefore, ,where S i is the transformed source point set and dx i represents the predicted drift for each point x i ∈ S i . The notation [*,*] represents concatenation of vectors in same domain. We should notice that due to the high non-linearity of neural networks, there is no difficulty to minimize the similarity loss function between S and G. However, the main challenge is to make sure the predicted drifts are coherent [20]. The coherency of drifts is quite important for holding reasonable correspondence and points interpolation for registering large scale point sets as well. Most previous methods deal with this problem by adding a penalization term on smoothness to trade-off target alignment loss for smoothness [4]. Our network naturally predicts smooth drifts because (1) by formula (6), for any neighbor points x k ∈ S, with concatenating two identical global descriptors, the inputs [x k , L S , L G ] should be very close to each other as input for function g. (2) Function g is a simple linear combination with ReLu activation. This function is continuous and its first derivative should be a constant almost everywhere. Based on the special function g and our assumption, we have the following theorem.
Claim: For a single layer perceptron with ReLu activation function g, (6).
Proof in sketch. Since g is a linear function with ReLu activation and we assume its weights w converges to w after training.

Loss functions
In this part, we define the similarity measure between the transformed source point set φ(S i ) and the target point set G j as both our loss function and evaluation metric.
where c is a hyper-parameter to choose. In our experiment 3, we choose c equal to 0.1.

Settings of CPD-Net
We train our network using batch data form training b is the batch size and is set to 16. As we explain in section 3.2, for learning the shape descriptor tensor, the input is N × 4/6 matrix and we use 5 MLP layers with dimensions (16, 64, 128, 256, 512) and a Maxpool layer to convert it to a 512-dimensional descriptor. For learning the coherent PointMorph discussed in 3.3, we use three layers MLP with dimension (256, 128, 2/3). We use ReLU activation function and implement batch normalization [9] for every layer except the output layer. Learning rate is set as 0.0001 with 0.995 exponential decay with Adam optimizer. The model is trained on single Tesla K80 GPU.

Experiments
In this section, we carry out a set of experiments for nonrigid point set registration and assess the performance of our proposed CPD-Net. In section 4.1, we describe the details of datasets that are used for training and testing of CPD-Net. We report the experimental results to evaluate the performance of our trained CPD-Net on 2D and 3D datasets in section 4.2 and 4.3. Section 4.4 discusses the resistance of CPD-Net to various types of noise. In section 5.5, we compare CPD-Net with non-learning based method. • To prepare the deformable shape dataset (as shown in the first column row of Figure 4), we simulate nonrigid geometric transformation on the normalized raw point sets by thin plate spline (TPS) [6] transformation with different deformation levels. The deformation level is defined as the perturbing degree of controlling points in TPS. Specifically, given the deformation level set at l (e.g. 0.5), a Gaussian random shift with zero-mean and 2l standard deviation is generated to perturb the controlling points.

Experimental Dataset
• To prepare the Gaussian Displacement (G.D.) noise dataset (as shown in the first row of Figure 8), we simulate the random displacement superimposed on a deformed point set (deformation level at 0.5) by applying an increasing intensity of zero-mean Gaussian noise.

2D non-rigid point set registration
In this experimental section, we demonstrate the point set registration performance of the CPD-Net on various categories of 2D shapes at different deformation levels.
Experiment Setting: In this experiment, we use four different type of 2D shapes (i.e. fork, face.) to prepare the dataset. For each shape, we first synthesize a set of 20k deformed shapes at each deformation level. The deformation level ranges from 0.3 to 2.0. To prepare the training dataset, for each type of shape at each deformation level, we split synthesized dataset into two groups. We randomly choose a pair of shapes from group one to form 20k pairs of training. Similarly, we randomly choose two shapes from the other synthesized dataset to form 10k testing pairs. Note that there is no intersection between training and testing datasets. To evaluate the registration performance, we use the Chamfer Distance (C.D.) between the transformed source point set and target one as quantitative assessment, and we visualize the pairwise point sets before and after registration for qualitative assessment. We conduct two tests based on the shapes we used in the test. For test one, we use the commonly adopted fish shape, and in test two, we use other 2D shape categories, such mushroom, face, and fork, to assess CPD-Net's performance, particularly on   the non contour-based shapes.
Results of Test 1: After training CPD-Net, we applied the trained model to testing dataset prepared as described above. In Figure 4, shapes from different rows have different deformation levels from 0.1 to 1.5. From the fourth column, we can observe that CPD-Net can predict nearly perfect registration when the deformation level is smaller than 0.9. While we increase the deformation to the level greater than 1.5, the source and target point sets have significant shape structural variation, which dramatically increase the difficulty of point set registration. However, CPD-Net can still reliably transform the source point set to align the main portion of the shape of the target point set.
In addition, it is interesting to observe from the second and third columns that source point set moves coherently as a whole towards the target one. This observation verifies that CPD-Net is able to predict a continuous smooth displacement field without necessity to impose additional coherence constraint term. We further provide the mean and standard deviation of C.D. calculated from the 10K testing pairs at each deformation level for quantitative evaluation. In the Figure 5, we plot the mean and standard deviation for the set of C.D. between the source point set and the target one at all deformation levels. We can see from the comparison that the red curve (post registration) is consistently below the blue one (pre registration), which indicates CPD-Net is able to robustly register the source and target point set with a small C.D. Moreover, the red curve stays nearly flat as the deformation increases from 0.1 to 2.0, which indicates that CPD-Net's robust performance at high deformation level. The detailed qualitative result is presented in Table 1.

Results of Test 2:
In this test, we further use CPD-Net to perform the non-rigid registration on other three types of 2D shapes including Mushroom, Fork, and Face shapes as shown in Figure 6. To visualize the registration result, we compare the pair of testing shapes before and after registration at deformation level 0.5 as shown in Figure 6. All randomly selected samples show nearly perfect registration. Similar to test 1, we present quantitative evaluation using C.D. metric for the non-rigid registration of those three types of shapes in the Table 1. Each row contains the mean and standard deviation of C.D. measurement for all testing pairs of shapes at deformation level from 0.3 to 2.0. Based on the quantitative results shown in the Figure 5, for all the four shapes, CPD-Net demonstrates the remarkable performance of non-rigid registration as evidenced by the fact that the C.D. is dramatically reduced and consistently stays low after alignment at all deformation levels.

3D non-rigid point set registration
In this experiment, we take a further step to investigate how well the CPD-Net performs 3D point set registration at different deformation levels since the 3D data have been gaining great attention in community with recent advancements in 3D acquisition and computation resources.
Experimental Setting: In this experiment, we use two categories of 3D shapes (i.e. 3D Face and 3D Cat) to prepare the dataset. Similar to 2D data preparation, we synthesize 10k training pairs of 3D shapes and 2k testing pairs for both 3D Face and Cat shapes at various deformation levels (0.3, 0.5, 0.8, and 1.2). We use the same measurement methods for both qualitative and quantitative results (as shown in Figure 7.
Result: In Figure 7, we illustrate the quantitative evaluation curves on the left and visualize one registration cases at deformation level 0.3 on the right. For both 3D cat and face shapes, CPD-Net demonstrates impressive performance with a quite small pairwise C.D. after registration, and the C.D. measurement remains consistently low while we increase the deformation level. At the level of 1.2, the mean of C.D. between source and target point sets is nearly 10 times less after alignment, which indicates that the trained CPD-Net is able to align most portion of the shapes between a source and target point sets. To further visualize the registration performance, on the right side of Figure 7, we show the registration results by plotting the figures for 3D source and target point sets, pre and post registration in first and third columns and the second column depicts the predicted coherent point drift vector. Those plots clearly prove that CPD-Net is able to predict an accurate smooth non-rigid transformation. Due to the limited space, more qualitative results will be showed in supplementary section.

Resistance to Noise
While using the sensors such as LIDAR sensor and laser scanner, it is unavoidable that the data might be acquired with a variety types of noises. An effective non-rigid registration method should be robust to those noise in addition to the structural variations as discussed in previous section. Therefore, in this section, we focus on testing how well CPD-Net can predict the non-rigid registration from the noisy dataset.
Experimental Setting: In this section, we use fish shape data at deformation level of 0.5 to prepare the experimental noisy dataset. We simulate three types of noise (i.e. Gaussian Displacement (G.D.) noise, Point Outlier (P.O.) noise and Data Incompleteness (D.I.) noise). For each type, we gradually increase the level of noise added to the deformed target point set of fish dataset as shown in Figure 8). We prepare 10k pairs of source and target point sets for each type of noise for testing. As in previous section, the same quantitative and qualitative performance measurement is used in this experiment.
Result: As shown in the Figure 8, we plot the quantitative evaluation curves on the left and visualize five registration cases at different noise level on the right. For the clean data, the mean of C.D. for the fish shape at deformation level of 0.5 is around 0.08. We need to validate if CPD-Net can significantly reduce the C.D. for pairs of source and target point sets of noisy dataset after registration, and if CPD-Net consistently keep the C.D. comparatively low when the noise level increases.
For the G.D. noise, in the Figure 8 the first row depicts the registration by our CPD-Net for the G.D. noise corrupted data. As we notice the plot, the C.D. after registration remains constantly lower than 0.08, even when the G.D. noise increases to the level of 0.2. CPD-Net can still predict the non-rigid transformation to align the source set (the red points) to the target one (the blue points) with a relatively small C.D. between two point sets, even though the shape was dramatically altered by the Gaussian Displacement noise. For the P.O. noise, as shown in the second row, outlier points is increasingly added to the target point set (blue ones) from left to right in a row. The registration result is impressive that the main body of the source and target shapes can robustly aligned to each other with a small C.D. between them after registration, especially when the P.O. noise level reaches as high as 0.3. For D.I. noise, as shown in the third row, an increasing number of points is removed from the target point set (blue ones) to check if CPD-Net is able to successfully align the source point set to the incomplete portion of the target one. The visualization of pairwise registration result in the third row clearly demonstrates that CPD-Net is able to robustly align the source point set (red) to the incomplete target point set (blue). When D.I. noise level reaches 0.25, the missing part is aligned with a straight line, which is less desired. But the aligned portions from transformed source point set and target one show consistent common geometric structure, which is not affected by the missing portion of the target point set.

Comparison to CPD
Different from previous efforts, the proposed CPD-Net is a learning-based non-rigid point set registration method, which can learn the registration pattern to directly predict the non-parametric geometric transformation for the point sets alignment. As a learning-based approach to predict the non-rigid registration, it is not applicable to have a direct comparison between CPD-Net and other existing non-rigid iterative registration methods. To compare our method to non-learning based iterative method (i.e. Coherent Point Drift (CPD) [20]), we design the experiment as follows to assess both time and accuracy performance.
Experimental Setting: In this experiment, we use the fish shape at deformation level of 0.5 to prepare the dateset. We synthesize 20k pairwise source and target point sets to form the training set, and another 20k pairs to form the testing set. The CPD-Net is firstly trained with the 20k training dataset. The trained CPD-Net is then applied to directly predict registration for the 20k testing dataset. In contrast, CPD is directly applied to both 20k training and testing dataset.
Result: The C.D. based quantitative comparison is presented in the Table 2. The first and third row list the experimental results for CPD on training and testing dataset respectively. The second row lists the results for the CPD-Net on training dataset, and the fourth row lists the results for the trained CPD-Net on the testing dataset. Based on the comparison between first and third rows, we can see that our model can achieve better performance (i.e. smaller C.D.) than that of CPD within a shorter time (25 minutes versus 22 hours) to align 20k pairs. Unlike the CPD needs to start over a new iterative optimization process to register a new pair of shapes independently, CPD-Net actively learns the registration pattern from training and consequently become capable of handling real-time point set registration or a large volume dataset by direct predicting the geometric transformation. As shown on second and fourth row of the Table  1, we notice that the trained CPD-Net is able to achieve nearly the same training performance, which indicates that CPD-Net has great generalization capability. The trained CPD-Net is able to achieve better performance than CPD on the same dataset with orders of magnitude less time (15 seconds versus 22 hours).

Conclusion
In this paper, we report our latest research effort towards non-rigid point set registration. The proposed method, Coherent Point Drift Network (CPD-Net), is presented to the research community as an new alternative solution for nonrigid point registration. In contrast to existing approaches, which often iteratively search for the optimal geometric transformation to register a given pair of point sets, driven by minimizing a pre-defined alignment loss function. The proposed CPD-Net can actively learn the registration pattern from a training dataset as non-parametric geometric transformation in an unsupervised manner. Consequently CPD-Net can predict the desired geometric transformation to align a pair of unseen point sets. To the best of our knowledge, this is the first effort in the community that an algorithm can actually learn to register point sets from training in unsupervised fashion. The CPD-Net can be extended to other modality data such as 2D and 3D image and a highdimensional multimedia data. We will present the extension of the CPD-Net in separate works.

Supplementary Materials: Demonstration of Additional Qualitative Results
Due to the space limitation, in the submitted paper we only show one qualitative example for each case in Figure 4 and 7. For better understanding our performance in Figure  4 and 7 of the submitted paper, we randomly select several registration results of testing samples to demonstrate in the supplementary section as we mentioned in the paper. The following Figure 9 is supplementary to Figure 4 of the submitted paper and Figure 10 is supplementary to Figure 7 of the submitted paper.  Figure 4 of the submitted paper. The testing qualitative registration results for Fish shape at different deformation level. The blue shape is target point set. The red shape is source point set. Please zoom-in for better visualization.
[33] Hang and Maji Su Subhransu and Kalogerakis, Multi-view convolutional neural networks for 3d shape recognition, Proceedings of the IEEE international conference on computer vision, 2015, pp. 945-953. Figure 10. Supplementary to Figure 7 of the submitted paper. The testing qualitative registration results for 3D shapes at different deformation level. The red points represents the source points and the blue ones represent the target points. Please zoom-in for better visualization.