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