Avoiding Overfitting to the Importance Weights in Offline Policy Optimization
Authors: Yao Liu
Emma Brunskill
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement Learning
Batch Reinforcement Learning
Policy Optimization
Overfitting

Abstract: Offline policy optimization has a critical impact on many real-world decision-making problems, as online learning is costly and concerning in many applications. Importance sampling and its variants are a widely used type of estimator in offline policy evaluation, which can be helpful to remove assumptions on the chosen function approximations used to represent value functions and process models. In this paper, we identify an important overfitting phenomenon in optimizing the importance weighted return,  and propose an algorithm to avoid this overfitting. We provide a theoretical justification of the proposed algorithm through a better per-state-neighborhood normalization condition and show the limitation of previous attempts to this approach through an illustrative example. We further test our proposed method in a healthcare-inspired simulator and a logged dataset collected from real hospitals. These experiments show the proposed method with less overfitting and better test performance compared with state-of-the-art batch reinforcement learning algorithms.

Under review as a conference paper at ICLR 2022
AVOIDING OVERFITTING TO THE IMPORTANCE WEIGHTS IN OFFLINE POLICY OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Offline policy optimization has critical impact on many real-world decision- making problems, as online learning is costly and concerning many applications. Importance sampling and its variants are widely used type of estimator in offline policy evaluation, which can be helpful remove assumptions on the chosen function approximations used to represent value functions and process models. In this paper, we identify an important overfitting phenomenon in optimizing the importance weighted return, and propose algorithm to avoid this overfitting. We provide a theoretical justification of the proposed algorithm through a bet- ter stttt--niighorrhoo normalization condition and show the limitation of previous attempts to this approach through an illustrative example. We further test our proposed method in a healthcare-inspired simulator and logged dataset collected from real hospitals. These experiments show the proposed method with less overfitting and better test performance compared with state-of-the-art batch reinforcement learning algorithms.
INTRODUCTION
Learning decision policies from offline data has a critical impact on real-world decision-making applications such healthcare (Lei al. [2012 Komorowski al. 20188), recommendation systems eLi al. 2010 Chen et al.) 2019), and intelligent tutoring systems (Mandel et al.) 20144).m In real-world crasionnmmking applications. we often need use limited amounts of data about past decisions to yield better future performance in complex, hard-to-model domains. Such offline policy optimization encounters two key generalization challenges: distribution shift and modeling bias. Distribution shift arises because, under new decision policy, the distribution of observations and actions will be different than the distribution of observations and actions in the offline data. Modeling bias can occur when popular assumptions over the domain structure model class (such as the Markov assumption, realizability, or the value function class being closed under the Bellman), fail to hold in the problem setting. Learning from limited data, algorithms ignoring these challenges estimates of policy performance that are far more optimistic than they achieve in practice similar to the overfitting in supervised learning.
produce policies and
To address this, prior work in batch reinforcement learning (RL. and contextual bandits mostly falls into two categories: (1) changing the estimator or loss function used in computing offline value estimates, or (2) constraining the policy search space. In category (1), self-normalized IS (or weighted
IS) (Hesterberg 1995 Swaminathan & Joachims 20136), variance regularization (Swaminathan &
Metelli et al. 2018). doubly robust SerthodssDudiin et al.) 2011 Jiang & Li 2016 Thomas & Brunskill 2016), and uncertainty regularized model-based batch RL (Yu et 2020
Joachims
201 2015a
Kidambi et al.) 2020) are all approaches that aim to provide more stable and
penalized
estimates of a policy'ss s performance to address the uncertainty due to limited data and distribution shift. The second category of direct constraints on the policy class includes bandit learning under action/policy constraints with behavior probability (Sachdeva et al. (020)), value-base batch RL algorithms by constraining the policy disagreement (Kumar al.) 2019 Buckman et al. 2020), thresholding the action probability (Fujimoto et al. [019]] Futoma et al. 2000). or thresholding the marginalized state-action probability (Liu et al. 2020), under the behavior policy.
Many of the works above rely on learning MDP models or value functions based on MDP assumptions.
However, the Markov assumption and function approximation assumptions are often unrealistic in

---

Under review as a conference paper at ICLR 2022
real-world problems and hard verify, which limits their eligibiliity in certain application problems. In this paper, we consider learning an policy to optimize an importance weighted return, as it is free from Markov and other types of model assumptions. We identify unique overfitting that is not solved in prior work about policy optimization and propose a new constraint on policy named eligible actions (EA) to address the overfitting issue.
The overfitting issue comes from fitting the importance weights in the weighted return objective. The importance weighted return can effectively remove certain subgroup of samples in the dataset by decreasing all weights to zero. This context avoidance is unrealistic when the subgroup consists of a subset of initial states, as the policy does not get to control the initial state distribution. Consider the following motivating example: an AI decision policy may learn from historical treatment logs to avoid all the logged treatment in the history for patients with severe conditions as they lead to low rewards. This avoidance can be achieved with finite data if the action space is large, and such avoidance will result in high off- off-po estimates. However, in the real environment, a policy still should make good decisions for patients who arrive with severe conditions. This propensity overfitting problem was studied in contextual bandit problems (Swaminathan Joachims 2015b). While their solution effectively constrained the upper bound on importance weights on high-reward samples, the challenge of overfitting to avoid the low-reward samples remains.
Our contribution To address the issue that optimizing with propensity weights may avoid certain initial states, we propose the Policy Optimization with Eligible Actions (POELA) algorithm. We constrain the potential action set the set of observed actions with similar states to prevent improper avoidance to lower-reward initial states. Thus within a radius of particular state, the sum of observed importance weights are always lower bounded. We then study the empirical performance of POELA in medical simulator and a real-world medical dataset. Our approach finds much better decision policies than prior state-of of-the-art algorithms in both domains.
OFFLINE POLICY OPTIMIZATION
We study the problem of offline policy optimization in sequential decision -aniingaingggg under uncertainty, Let the environment be a finite- hortzeh Contextual Decision Process (CDP) (Jiang et al.) 2017). A CDP can capture more general, Mar-Morko settings (also sometimes refered to as Mon-Markov DP (Kallus & Ueharal 201
CDP defined as a tuple (X, A, H, P. R),, where X' is the context space, AA is the action space, and H is the horizon. P = { k= is the unknown transition model, where PA= (A' X A)^-1 + ((X) is the distribution over next context given the history P. A(X) is the initial context distribution. Similarly, R = {Ro h= [ is the reward model and RA (X' x A)a -> A[[ [[]-Rmax: Rmax)).
In this paper we focus on learning policies that map from the most recent context to an action distribution, æ X + A(A). This is optimal when the domain is Markov and can often be more interpretable and more feasible to optimize given finite data in the offline setting. In offline policy optimization settings, we have a dataset with n trajectories collected by a fixed behavior policy ; X A(A), and aim to find policy æ in a policy class II with the highest value.
Policy gradient and optimization approaches do not rely on a Markov assumption on the under- lying domain, and have had some encouraging success in offline RL (Chen et al., 2019). Often these methods leverage an importance sampling (IS) estimator in policy evaluation: (is(TT) =
E. E (0) I
x(a (1 plaf ( (
The IS estimator is an unbiased and consistent estimate
of the value under the following two assumptions:
Assumption 1 (Overlap). For any E II, and any E X, E A,
s(als)
00.
[[ass)
Assumption 2 (No Confounding/ / Sequential ignorability). For any policy E II and μ., conditioning on the current context Th, the sampled action on is independent of the outcome Th:H and 11+1::H-
IS often suffers from high variance, which has prompted work into extensions such as doubly robust methods (Jiag & Li 2016: Thomas & Brunskill 2016) and/or methods that balance variance and bias. Truncating the weights and using self-normalizatio has been shown to be empirically beneficial
both in bandit and RL settings (Swaminathan & Joachims 2015b Futoma et al. 2020): refer to
2

---

Under review as a conference paper at ICLR 2022
this Self-Normalize Truncated IS (SNTIS):
(SNTIS(T) E:=1 min W M
Ei=
(En=
(1)
min [ who
(1)
where (( = sla
For the ease of notation, in the rest of this paper we define (
plan ) Il W W
1:hh =
w
1 W E W(O,, and p(t) Ck=1 (
3 THE OVERFITTING PROBLEM IN IMPORTANCE WEIGHTED POLICY OPTIMIZATION
We now highlight an important problem with using important sampling estimators such as the above during offline policy optimization. For concreteness we will describe this in the contextual bandit setting using the self-normalized importance sampling estimator, but a similar results hold for un- normalized estimator. We will also shortly describe in the main text how this issue persists in existing importance weighted off-policy learning methods and about the multi-step case in the appendix.
The key issue is that given finite dataset, during optimization the IS estimator objective can benefit policies that improperly avoid low reward states, inducing a lack of overlap on the empirical behavior data. To this, let ed (z) E[r [r x|, p(x) be the empirical probability mass/density over the
contexts a in the dataset, and (x) = Einr off- off-policy estimator into three parts.
w
We now decompose the importance weighted W.
W W()) 2 v=(())
: = Exl0"(z)1+ + Σ (p(z)- (()))) Σ (()) TEX
Σ -F
(2)
REX
empirical
difference context weights
weighted 15 error each context
The first term a supervised empirical value estimate whose only error due to the error in the empirical context distribution sampled in the dataset, the true context distribution. The second term captures the error caused by the difference between context distribution introduced by weights and empirical context distribution in the dataset. The third term computes the difference between the weighted IS estimate of the value of the policy in a specific context I versus its true value e (x), and then sums this over all contexts.
The second term is of particular interest, because it highlights how the IS estimator of policy may effectively shift the relative weight on the context space. Note the bandit setting (and in the initial starting state distribution for the RL setting) such shifting should not be allowed: the policy may control what actions are taken, but cannot change the initial context distribution.
Before illustrating the problematic behavior that can result from this type of objective function for offline policy learning, we first further analyze if it possible for W(x) to differ significantly from halp(z), given the normalization constraint of æ. Expanding the difference between the empirical distribution over a context and (zx):
W
N p(x)
Σ p(aaz) TTaax)
p(x) W(x) = -(x))
Σ (
= p(x)
(3)
W
W
p(alz)
=(1
N
p(z)
N
p(x)
Σ
1
p(a[z)
T(alz)
(4)
W
u(alx)
While the first term is asymptotically zero because W + N, the second term will be non-zero whenever the policy π puts non-zero weight actions in contexts where the empirical behavior distribution differs significantly from the true behavior distribution. Such a difference between the empirical and true behavior distributions can easily happen. This is especially the case in settings where the state aate-nction space large and the number of observed actions per state is small, which is common in recommendation settings, healthcare and many other applications.
A policy learning algorithm maximizing the objective in Equation 2 can exploit this difference in context weights and return policy with over inflated value estimate, as illustrate:
3

---

Under review as a conference paper at ICLR 2022
Example 1. Consider contextual bandit problem with [X] contexts and |A| actions in each context. For half the contexts Sp, the reward is 1 for one action and zero for others. For the other half of the contexts, Sn, the reward is -1 for half the actions, and -5 for the rest. The true distribution over contexts is uniform. Note in this setting the optimal policy would have a reward of 0. The behavior dataset is draw from a uniform distribution over contexts and actions. When the sample size (D) < [A], we can assume there is only one observed positive reward in the dataset. Then computing the policy to maximize the important sampling weighted objective will yield weights that are on all contexts except for the context with the positive reward, through policy π that selects actions that are not present in the dataset for all contexts whose observed actions lead to only zero or negative rewards: lei As, = {a; : r((s,, (1));;))) S 0} then T(s)) = =a where 0g & Ass.
The resulting IS/SNIS estimator of the value of ι is 1, which is much higher than the optimal policy value. In addition, note that the returned policy x is likely to be worse than the optimal policy for any context where r r(8;, az) = -1, since that the optimal reward possible for such states 8i, and by ı selecting unobserved action 0j in that state (T((:) o,hh the policy may select action with worse true reward, T(8;, Qz) -5
Note that in this example, there is no error in the importance weighted return for the contexts with positive (()) (which is the third term in the decomposition shown in Equation 2). The issue arises because to optimize the objective, is possible to select a policy whose W (x) distribution over the contexts has zero weight on least the half of the contexts with negative rewards Sn, by assigning them actions not selected in the dataset. This causes the second term in the decomposition (Equation to be significantly overestimated.
This is unique overfitting phenomena in the counterfactual (or called off-policy learning settings since in supervised learning is not possible for a hypothesis π to manipulate the weights over the input contexts. While this issue can arise in contextual bandits with large state and action space in small datasets, we show that is even easier for this to occur in sequential reinforcement learning settings, even when only 2 actions are available in Hxample and i in the Appendix.
Intuitively, the issue arises because in estimating the value of new decision policy, is acceptable to choose policy that re-distributes the weights of actions within initial context but not re-distribute the weights across initial contexts, since it is not a function of the actions selected. It is well known that in importance sampling, the expected ratio of the weights should be 1: Ey- (T(y)/ /M(()) = 1. In contextual policies, we expect that the expected weights should also be 1 for all initial contexts zng (()))()) (=(a|<a)/ /a aro) Jaro] 1. However, optimizing for standard importance sampling objective (such as Equation 2 does not involve constraints that the empirical expectation
of weights given an initial context È w |,rh (=(])
[6)]
(or the weights of n-step given initial context
É [= (a]) ) is still close to one. In order to optimize the future return, the optimization algorithm can optimize the weights of initial contexts in the dataset, instead of optimizing the weights on different actions/ action sequences in a given initial context.
This result may seem surprizing, given that under mild assumptions which are satisfied here (As- sumptions and 2) importance sampling is well known to provide an unbiased estimate of the value of policy. Our observations do not contradict this fact: while importance sampling will still provide an unbiased estimate given a policy, the policy optimization can exploit the finite sample error and its heterogeneousness across the policy class.
4 PRIOR WORK ON OFFLINE POLICY OPTIMIZATION
Before we describe method to alleviate this problem, we first review prior work. There increasing interest in multi-armed bandits and offline RL to avoiding overly optimistic estimates of policies computed from finite datasets that can cause suboptimal policy learning, and prior work has discussed extrapolation error(Fujimote et al., 2019). propensity overfitting (Swaminathan & Joachims 20156), and bandit error (Brandfonbrener et al. 2020). The problem we identified arises specifically from deficient support in the observed dataset.
To address potential overfitting, one line of work focuses on changing the objective used for policy optimization. For example. (Saamintthan & Joachims (2015b) has shown that policy optimization
4

---

Under review as a conference paper at ICLR 2022
using vanilla importance sampling in contextual bandits will over-maximize the weights if the reward is positive and over-minimize the weights for negative reward. Shifting the rewards will help with the latter (and avoid part of the context avoidance we describe) but can worsen the former. The self-normalized estimator proposed to address the issue of over-maximizing reward (Swaminathan & Joachims 2015b) is equivariant any constant shift in rewards, and will still suffer from the context avoidance issues we describe above. Counterfactual risk minimization (Swaminathan & Joachims 2015a) uses variance regularization based on the empirical Bernstein's 's inequality. However, this penalization is at the policy level and does not directly address the problem with avoiding contexts with low reward. In Appendix Figure 22 we show the counterfactual risk minimization regularization with or without self-normalization requires large dataset to perform well. Later work (Joachims) eet al., 2018) extended morm-POEN to stochastic gradient descent settings for large-scale training. Recent work (Brandfonbrener et al. 2020) discussed a similar overfitting issue as we describe and compared the performance of offline policy optimization and model/value- based method on this overfitting issue. Those authors focus primarily the negative result of the policy optimization approach and the advantage of the model/value- based method. Doubly robust estimators (Dudik) eet al. 2011] Diang & Li 2016 Thomas & Brunskill| [016] Kallus & Uehara 2019a ()) have multiple benefits but as long as the learned Q function is imperfect, policy learning can still overfit to the high/positive residual r Q. Pessimism under uncertainty approaches are promising (Kidambi et al.)
2020: Yu et al. 2020) but have so far only been developed for Markov settings and are not robust to model class misspecification.
Another line of offline batch policy optimization constrains the policy search space, for example to constrain target policies to be close in some distance the behavior policy (Kumar al., 2019)
Buckman et al. 2020). A common approach is to constrain target policies to have a minimum
conditional action probability under the behavior policy p{aass (e.g. Sachdeva et al. [2020 Fujimoto eet al. (2019); Futoma et al. (2020); Liu et al. (2020). This work has focused on algorithms and analysis for the Markov setting with additional model realizability assumptions, except [Sachdeva) jet al. (2020) in the bandit case and [Futoma et al. (2020) in the RL setting. For example, the MDP value based approaches often require the value function class is closed respect to the Bellman operator and the value function is realizable. Such assumptions are hard verify in real-world domains.
This prior work does not address the issues we outlined, that occur due to deficient support in the observed finite data rather than in the expected behaviors. Our work can be broadly viewed as following in the recent line of work on pessimism under uncertainty, but adapted to provide policy search based offline learning method that does not require the Markov assumption or model realizability assumptions, and can achieve strong performance given a finite dataset.
5 LOWER BOUND OF É [ AND ELIGIBLE ACTIONS
We have observed that the issue rises in policy learning because weight can be placed on unobserved actions for certain contexts, causing the empirical conditional expectation of weights given context to be zero for such contexts. To address this, one possibility is to constrain the conditional expectation of weights given a context be 1 or lower bounded. However doing so in infinite/continuous context spaces is subtle: each context likely only appears once in the dataset, and requiring ÉE[W |a] = 1 would be equivalent to only allowing policy that exactly matches the observed logged actions.
We now propose a slight relaxation of the above proposal. Intuitively the issue arises because without further constraints, policy learning can place large weight on unobserved actions in the dataset, for which our reward uncertainty is high. The recent line of pessimism under uncertainty for model and value based MDP offline RL explicitly accounts for such statistical uncertainty through constraining or penalizing actions and/or states and actions for which there are limited observed data. Similar to this, introduce pessimistic constraint on the policy class to be considered, and then demonstrate this allows us to constrain the empirical conditional expectation of weights given a context.
For policy learning, we create local constraints on the eligible policy class by defining for each context x, dataset 'D and a given threshold 6, the eligible action set A(x; D)
An (z: D) {an 3 an) D s.t. dist 2n) S 8}
(5)
Intuitively this allows any action that was taken for a given context, or actions taken in contexts within a given distance of the observed contexts.
5

---

Under review as a conference paper at ICLR 2022
We now show that any policy that only selects actions in eligible action sets will ensure that the empirical sum of weights in any hypersphere of any context can be lower bounded, as desired. To do we first introduce an assumption about the policy's smoothness in the context space.
Assumption 3 (L-Lipschitz policy). VI E II, [[((a)) ग (aaa=))l < Ldist( x").
Under this and the former assumptions, we can now show the following. All proofs, when omitted, are provided in the appendix:
Theorem 1. /x B(2%) 6) == {a dist(z, 2//)) S 63. E.GeBOl Wx 2 21-8L|A
Given the likelihood ratio is lower bounded, we can further show that the self-normalize truncated weights are also lower bounded in the one-step settings.
Corollary 1. For = Ez E,E,, CB(a
(ax)WW() .M) .6) Er=, max W WO 2
1-8L[A1 nM
for M 1.
In n-step sequential settings, it is necessary to have the 1-step weights be greater than zero in order to have n-step weights greater than zero.
Proposition 1. For any I, 5, E W (0)
E B(x, 6)] = B(W
1h- 1x e B(x, B(x,
1:h 2h
(zx 5)]. E(W 1:h (a E B(x, 5) = B[ 1-h-1 12 E B(x, 6) (
(0) B(I,
If the policy overfits the weights on an h-step context such that ((WX" |= n-step weights will also be zero even the roll-in probability under non-zero.
9 E B(I, [)z = 0, the
The above results highlight that introducing a constraint on the policy class to have local overlap with actions taken in the dataset, is sufficient to ensure that the weights on the contexts are lower bounded. This will help address the overfitting issue highlighted in the prior sections. Policy learning can now be done by finding the policy which satisfy the eligible actions constraints given the input dataset:
arg max J(;; D) s.t. Vi,h " (D.)) <aaa=/ (0) =1
(6)
J(;; D) can be any objective function such ugs, OSNTIS with the counterfactual risk minimization regularization (Swaminathan & Joachims 2015a in prior work:
arg ma (SN - X Var (fsNns(TT).
A natural question is whether these action eligibility local constraints limits the expressivity of the policy class 11. We show that asymptotically the expressivity is the same, and the maximizer in Equation 6 will converge to the optimal policy in the policy class if J(T, D) is consistent.
Theorem 2. i) Fixed 6, for any x. (x; + {a : p(a[z) > 0} as n + oo with probability
1. Thus the solution to Equation 6 is the same ĀD arg max, (Tt, D). ii) If J D) is the objective in Equation] 7 the truncation threshold M as a function satisfies - oo and M/n +
as oc, and cC, then AD. + max t in probability.
ALGORITHM: POLICY OPTIMIZATION WITH ELIGIBLE ACTIONS
Algorithm Policy Optimization with ELigible Actions (POELA)
1: Input: D, 1lg, sphere radius 6, IS truncation M, CRM coefficient X, learning rate a
2: Output: Ro
3: Initialize fu
4: for t = 0, 1 until convergence do
5: no. (a(xx (:) = 1 (a An DT (alx)/ (E. 1a E An(x; (x; 8) (alx))
6: 0.11 + O2 + aVo ÓSNTIS(Ro.) >v Var (essns((Fo)))
7: end for
Now in Algorithm I we introduce our POELA (Policy Optimization with Eligible Actions) algorithm that implements the learning objective in Equation 6 (see Algorithm We use the counterfactual

---

Under review as a conference paper at ICLR 2022
risk minimization objective function Equation 7 as the [r: D). where the estimator Var (an(s)))))
constructed using the Normal approximation in [ (Owen 2013 Equation 9.9) Var(i)) =
Ee (v49 (Bxmm) (min(W(6)
After each gradient step, we enforce the policy to satisfy the
(E min(W M))"
eligible action constraints by re- re-normalizing the output probability on A (z; D, 8) for z E D. The eligible action set for each training sample is static and can be stored to reduce computational cost.
In the experiments, we use Euclidean distance in over nearby states at any time index.
7 EXPERIMENT
We now compare POELA with several prior methods for offline RL. Perhaps the most relevant work in avoiding overfitting when using importance sampling is norm-POEM (Swaminathan & Joachims 2013b). Here we extend it here to be suitable for sequential decision settings, use neural network policy class and refer to the resulting algorithm as PO-CRM. A second baseline PO-μ constrains the policy class to only include policies which take actions with sufficient probability under the behavior policy j(a(s) (see e.g Futoma et al. (2020). ). We also compared with recent deep value-based MDP methods in batch RL: BCQ (Fujimoto et al. 2019) and PQL (Liu al.] 2020). For all algorithms use a feedforward neural network for the relevant policy and/or value, function approximators.
We use the same procedures for each algorithm to select its hyper-paramett parameters. An algorithm is trained on the training set multiple times, using different typer-parameters and several restarts. Intermittent policies generated during the training process saved checkpoints. Across this set of potential policies, we identify the policy with the highest nolmanorml truncated IS (SNTIS) estimates on held-out validation set. Finally, we report the test performance of selected policy either through online Monte-Carlo estimation if simulator is available, or using SNTIS estimates on held out test set. Full experimental details are provided are the Appendix.
7.1 EXPERIMENT IN LGG TUMOR GROWTH INHIBITION SIMULATOR
The Tumor Growth Inhibition (TGI) simulator (Ribba al. 2012) describes low-grade gliomas (LGG) growth kinetics in response to chemotherapy in a horizon of 30 steps (months), with an non-Markov context and binary action of drug dosage (Yauney& & Shah 2018). The reward consist of an immediate penalty proportional to the drug concentration, and delayed reward of the decrease in mean tumor diameter. The behavior policy selects from a fixed dosing schedule of months (the median duration from Peyre al. (2010)) with 70% probability and else selects actions at random.
In this experiment, the behavior policy can only take values in {0.15, 0.85). This means constraining the policy class to have minimal probability under p[aas), in baseline PO-J4, is only non-trivial constraint for thresholds greater than 0.15: this produces a single potential target policy, which is the deterministic fixed-dosage part of behavior policy. We include this 9-mon (short for month dosing) in Table [ The training and validation set both have 1000 episodes, and we repeat the experiment 5 times with 5 different train and validation sets. Policy values are normalized between 0 (uniform random) and 100 (best policy from online RL).
As shown in Table (Non-MDP rows), our POELA achieves the highest test value as well as smaller variability compared with the baselines.
Does POELA reduce overfitting? We calculate the difference between uSNTsS on the validation set and the online test value. Although for given algorithm, we select the final policy using off off-policy evaluation on the validation set, most algorithms still result in a policy whose value is significant overestimate of its true performance (see Table rows for USNTIS =²)) In contrast, our approach yields policy whose value is much more accurately estimated and performs better.
Performance comparison in MDP environment We also repeat the experiment with an MDP modification of the simulator, including an immediate Markovian reward and additional features for a Markovian state space. Note that we expect BCQ and PQL to do very well: both are designed to avoid overfitting in offline MDP learning and in particular PQL uses a pessimism under uncertainty approach to penalize policies that put weight on state-action pairs with little support. Though our POELA algorithm makes no Markov assumptions, it performs only slightly worse than the conservative MDP methods. POELA also substantially outperforms other policy-based approaches.
7

---

Under review as a conference paper at ICLR 2022
Algorithms
POELA
PO-CRM
BCQ
PQL
9-mon
Non-MDP
Test v"
92.20 + 1.63
75.06 13.22
30.24 1 15.22
74.76 1 9.75
68.12
USNIIS
-1.26 = 1.92
15.57 13.07
63.72 15.54
17.74 + 9.49
MDP
Test o"
89.52 1 1.55
78.79 1 6.42
95.64 + 4.64
96.88 1 3.76
68.12
USNTIS
5.16 + 1.78
14.93 5.71
0.69 + 0.81
0.55 + 5.12
Table 1: Test v and amount of overfitting of the learned policy. Test en is computed from 1000 rollouts the simulator. ŪSNTIS on the validation set test v* represents the amount of overfitting. All numbers are averaged across 5 runs with the standard error reported.
Method
POELA
PO-H
PO-CRM
BCQ
PQL
Clinician
Test SNTIS
91.46 (90.82)
87.95
87.71
82.67
84.40
81.10
95% BCa UB
93.24 (92.61)
90.58
90.04
86.83
88.29
82.19
95% BCa LB
89.59 (88.68)
84.77
84,90
78.25
80.13
79.80
Test ESS
624.92 (586.37)
372.00
399.59
228.82
231.93
2995
Table 2: MIMIC III sepsis dataset. Test evaluation, (0.05, 0.95) BCa bootstrap interval, and effective sample size. The value of POELA without a CRM variance penalty is shown in parentheses.
7.2 EXPERIMENT IN ICU DATA MIMIC III
We next apply our method in a real-world example of learning policies for sepsis treatment in medical intensive care units (ICU). We use an extracted cohort (Komorowski et al., 2018) of patients fulfilling the sepsis-3 criteria from the MIMIC III data set (Johnson et al.] (016) and obtain a dataset of 14971 patients, 44 context features, 25 actions and 20 step maximum horizon. Full details are in the Appendix. We hold out 20% of data for validation and 20% of data for the final test. The treatment logs do not include the probabilities of clinicians' actions. Instead, suggested by prior work(Raghu et al. 2018), we estimate the probabilities of the behavior clinicians' policy by k-NN with k 100. To ensure overlap, for all policy optimization algorithms we allow (a]ss) > 0 only if (((ass 0.
Using nelf-normalized truncated importance sampling to evaluate the performance on a test set is appealing because it makes little assumptions the underlying domain. However, it may be that very few test behavior policy trajectories match a candidate test policy, which can make the resulting value estimate unreliable. The amount of overlap between the test set and a desired policy to evaluate can be measured quantitatively by the effective sample size (ESS) (Owen 2013). To help increase the chance that the test effective sample size is sufficient to yield reliable estimates, during the policy selection process for a given algorithm, only policies with an effective sample size of at least 200 on the validation set are considered] Similar prior work (Thomas al. 2015), in addition the SNTIS estimator on the test set, we also report 95% upper and lower bound from bias-corrected and accelerated (BCa) bootstrap. The clinician's 's column is the test dataset rewards and sample size.
Table 2 shows our POELA is the best on all metrics, achieving the highest evaluation on the test set, the highest upper and lower bounds, and the highest effective sample size.
Is the variance regularization helpful? To demonstrate the effect of variance penalty the POELA algorithm, we demonstrate the test performance POELA without the variance penalty. The performance is worse than using the variance penalty but still higher than the baseline algorithms.
Is there a trade-off between effective sample size (ESS) and performance estimates? A tension in conservative offline optimization is that the most reliable and conservative policy estimates come from effectively imitating the behavior policy (which will maximize effective sample size). Policies that differ substantially from the behavior policy may yield higher performance, but have less overlap with the existing logged data (and lower ESS). In Figure Ta we plot each hyper-parameter and each re-start from different algorithms. The plots show that POELA achieve a better Pareto frontier between performance estimates and effective sample size than other algorithms.
'Noe that the variance penalty may not ensure that the ESS is large. In particular, if only 2 trajectories in a dataset match desired target policy (an ESS of 2). When they have the same reward and weights, the variance penalty of self-normalized estimator will he 0.
8

---

Under review as a conference paper at ICLR 2022
Ciriciin Palicy
POLLA
PO-mU
000
100
800
wis validation
95
400
90
200
FD-CHM
PQL
800
80
600
250
500
750
1000
Effective Somple Size validation set
POELA
PO-CRM
200
PQI
Vesopressoors
(a) Trade-off between ESS and OPE
(b) Action counts Righ-SOFA contexts
Figure I: (a): Trade-off between effective sample size and value estimates. (b): Action counts
heatmap in high-SOFA initial contexts of the policy learned.
Do learned policies take medically reasonable actions on sicker patients? As we discuss, prior IS methods can overfit to achieve high estimated IS/SNIS score by avoiding initial contexts with low expected rewards. We now explore the learned policies for patients with high logged SOFA score (measuring organ failure) initially in the test dataset. Figure Tb depicts the number of actions that would taken by different policies, as well as by the clinicians on the high-SOFA contexts. POELA mainly takes high-vase righ-vasopressors high-IV-fluic treatments but also some IV-fluid-only treatments, which similar to the clinician's 's policy but more concentrated on high-vasopressors treatments. In contrast, PO-CRM and value-based methods, take treatments that different from the logged clinician decisions. This suggests these policies may be overfitting to avoid the contexts with high SOFA in the distribution. However, some patients arrive with high SOFA scores, policy must have a suitable policy to support such individuals, which our method helps to ensure.
While these results are promising, before deploying any offinn reinforcement learning algorithm in high stakes clinical setting, further investigation and collaborations with clinicians would be essential.
8 CONCLUSION & FUTURE WORK
To conclude, we identify a novel overfitting challenge that arises when using importance sampling as part of an offline policy learning objective. In particular, the objective can result in a policy that under-weigh certain (lower performing) initial contexts, to achieve higher average value. To address this, we constrain the policy class to only consider logged actions taken by nearby samples. This can be viewed as a similar pessimism constraint that has been used in MDP offline policy learning, now developed for a non-Markov, direct policy search setting. Our approach yielded strong performance relative to state-of- tfate-of-the-ar the-art prior approaches in tumor growth simulator and real world dataset on ICU sepsis treatment. Our method may be particularly useful for many applied settings such healthcare, education and customer interactions, which have short medium length decision horizon, but are unlikely to be Markov in the observed per-step variables.
A reader might wonder if similar benefit might be possible if the algorithm first learned empirical behavior policy from the logged dataset, and then constraining the policy class to be close to the empirical behavior policy. Our current results suggest that such an approach is likely require additional innovation: indeed the PO-pubaseline for the sepsis dataset uses an empirical behavior policy, and does not perform as well as our approach. This is interesting because prior work has shown that using such an empirical behavior policy can yield better off-policy estimates than using true behavior policy (Xie et al.] 2018 Hanna et al. 202T) settings, and lead to benefits in off policy learning for contextual bandits Xie et al. (2018). However, this prior work did not consider constraining the policy class nor performing offline RL, and there are some significant subtleties in learning empirical behavior policy for large continuous spaces. For example, Hanna et al.) (2021) demonstrated that learning a behavior policy that maximized the likelihood of the logged data in a IS bS-based estimator did not yield the most accurate estimate. An interesting direction for future work whether different ways of learning an empirical behavior policy might yield similar or additional benefits locally constrained approach proposed.

---

Under review as a conference paper at ICLR 2022
REFERENCES
David Brandfonbrener, William F Whitney, Rajesh Ranganath, and Joan Bruna. Offline contextual bandits with overparameterizzed models. arXiv preprint arXiv:2006. 15368, 2020.
Jacob Buckman, Carles Gelada, and Mare G Bellemare. The importance of pessimism in fixed-dataset policy optimization. arXiv preprint wwxXi:2000.066999 2020.
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed Chi. Top-k off off-pollcy correction for reinforce recommender system. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 456-464, 2019.
Thomas Cover and Peter Hart. Nearest neighbor pattern classification. JEEE transactions on information theory, 13(1):21-2) 1967.
Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning.
In Proceedings of the 28th International Conference on International Conference on Machine Learning, pp. 1097-1104. Omnipress, 2011.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In ICML, pp. 2052-2062, 2019.
Joseph Futoma, Michael C Hughes, and Finale Doshi Delei.Velez. Popcorn: Partially observed prediction constrained reinforcement learning, arXiv preprint arXiv:2001.04032, 2020.
Josiah P Hanna, Scott Niekum, and Peter Stone. Importance sampling in reinforcement learning with an estimated behavior policy. Machine Learning, pp. 2021.
Tim Hesterberg. Weighted average importance sampling and defensive mixture distributions. Techno- metrics, 37(2):185-194 1995.
Edward L lonides. Truncated importance sampling. Journal of Computational and Graphical Statistics, 17(2):295-311, 2008.
Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on International Conference Machine Learning- Volume 48. pp. 652 661, 2016.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pp. 1704-1713. PMLR, 2017.
Thorsten Joachims, Adith Swaminathan, and Maarten de Rijke. Deep learning with logged bandit feedback. In International Conference on Learning Representations, 2018
Alistair EW Johnson, Tom J Pollard, Lu Shen, H Lehman Li-Wei, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark. Mimic-iii, freely accessible critical care database. Scientific data, 3(1):119,, 2016.
Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evalua- tion in markov decision processes. arXiv preprint arXiv: /908. 085266 2019a.
Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon: Double reinforcement learning in infinite-horionn processes. arXiv preprint arXiv: 190:::99000000 0509005550, 2019b.
Rahul Kidambi, Aravind Rajeswaran, Pranceth Netrapalli, and Thorsten Joachims. Morel: Model- based offline reinforcement learning. arXiv preprint arXiv:2005.05951, 2020.
Matthieu Komorowski, Leo Celi, Omar Badawi, Anthony Gordon, and Aldo Faisal. The artificial intelligence clinician learns optimal treatment strategies for sepsis in intensive care. Nature medicine, 24(11):1116-172), 2018.
Aviral Kumar, Justin Fu. Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. In NeurlPS, pp. 11761-11771, 2019.
10

---

Under review as a conference paper at ICLR 2022
Huitan Lei. Inbal Nahum-Shani, Kevin Lynch, David Oslin, and Susan A Murphy. A" smart" design for building individualized treatment sequences. Annual review of clinical psychology, 8:21-48. 48, 2012.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. In Advances in Neural Information Processing Systems, 2020.
Travis Mandel, Yun-En Liu, Sergey Levine, Emma Brunskill, and Zoran Popovic. Offline policy evaluation across representations with applications to educational games. In Proceedings of the 2014 international conference Autonomous agents and multi-agent systems, pp. 1077-1084. International Foundation for Autonomous Agents and Multiagent Systems, 2014.
Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy optimization via importance sampling. In Advances in Neural Information Processing Systems, pp. 5442-5454, 2018.
Art B Owen. Monte Carlo theory, methods and examples.
stanffrr
edu/~owen/mc// 2013.
Matthieu Peyre, Stephanie Cartalat-Carel David Meyronet, Damien Ricard, Anne Jouvet, Johan Pallud, Karima Mokhtari, Jacques Guyotat, Emmanuel Jouanneau, Marie- Sunyach, et al. Prolonged response without prolonged chemotherapy: lesson from pev chemotherapy in low- grade gliomas. Neuro-oncology, 12(10):
2010.
Aniruddh Raghu, Omer Gottesman, Yao Liu, Matthieu Komorowski, Aldo Faisal, Finale Doshi- Velez, and Emma Brunskill. Behaviour policy estimation in off-policy policy evaluation: Calibration matters. arXiv preprint arXiv: 1807 2018
Benjamin Ribba, Gentian Kaloshi, Mathieu Peyre, Damien Ricard, Vincent Calvez, Michel Tod, Branka Cajavec- Bernnadd, Ahmed Idbaih, Dimitri Psimaras, Linda Dainese, et al. A tumor growth inhibition model for low-grade glioma treated with chemotherapy radiotherapy. Clinical Cancer Research, 18(18)55071- 1-5000, 2012.
Noveen Sachdeva, Yi Su, and Thorsten Joachims. Off-policy bandits with deficient support. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 965 975, 2020.
Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. International Conference on Machine Leurning, pp. 814-823. PMLR, 2015 5a.
Adith Swaminathan and Thorsten Joachims. The self-normalized estimator for counterfactual learning. In advances in neural information processing systems, pp. 3231-3239, Citeseer, 2015b.
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 211922114444 2016.
Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High confidence policy
improvement. In Proceedings of the 32nd International Conference on International Conference on Machine Learning, pp. 2380-2388. 2015.
Yuan Xie, Boyi Liu, Qiang Liu, Zhaoran Wang. Yuan Zhou, and Jian Peng. Off Off-policy evaluation and learning from logged bandit feedback: Error reduction via surrogate policy. In International Conference on Learning Representations, 2018.
Gregory Yauney and Pratik Shah. Reinforcement learning with action-derived rewards for chemother- apy and clinical trial dosing regimen selection. In Machine Learning for Healthcare Conference, pp. 161-226. PMLR, 2018
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-base offline policy optimization. arXiv preprint arXiv:2005. 2020.
11

---

Under review as a conference paper at ICLR 2022
We first briefty describe the structure of appendices here. In Appendix A add two more example in the multi-step settings as supplementary to the example in Section 3 In Appendix B we provide the proof of theorems in Section 5 In Appendix C we include experiment details and more results of ablation study as well.
A COUNTER EXAMPLES IN RL SETTINGS
In the main text, we gave an example about the overfitting issue in contextual bandits with large state and action space in small datasets. Here show that it is even easier for this to occur in sequential reinforcement learning settings, even when only 2 actions are available in the next two examples with or without state aliasing.
Example 2. Consider a sequential treatment problem as shown in Figure 2a There are two actions available in each state. From the first state, action an has 50% chance of leading to immediate terminal positive reward r = 1 and a 50% chance of leading to an immediate terminal negative reward -1 From the first state, action 02 also has 50% chance of leading an immediate terminal positive reward r 1. For the other 50% of states, action a2 results in transitions to additional states, which are followed by additional actions, for another H steps; however, all transitions eventually end in large negative outcome (e.g. consider a risky surgical procedure that results in many subsequent additional operations and but ultimately typically unsuccessful. Assume the behavior policy is uniform over each action, yielding plaa = 0 = p(a- = 1[21) = 0.5 and a probability of each action sequence following 02 of Tam---- With even minimal data the value of (zo) 01 will be accurately estimated as O. However, when H is large relative to a function of the dataset size, there always exists action sequence after an initial selection of (22 that is not observed in the dataset. This means that a policy ma that starts with x (2o) = 02 and then selects an unobserved action sequence will essentially put weight on the resulting contexts that incur
-5). 3). For example, one could
-5 outcomes, even though such outcomes will occur 50% of the time after taking action a2- In this case, the value of n2 will be overestimated sigmificantly by IS or self selfnnormalized IS. Thus the offline policy optimization will prefer taking action 2 at the first step result of overfitting even though the true value of first taking a2 is - -15 and the optimal policy value obtained by taking action a1
Now we add a slight change in the transitions shown in Figure 2a approach will also fail.
We can see that model/value-bart
Example In this example, we add another action in the first step. The action 3 and action 1 will lead to the same next state. However in the next state, matter which action taken, the reward will depends on the action taken in the last step: If = 1, then we have the same reward for a = in have reward -5. Thus model and value based method will mix the reward for a1 and 01 = 3 so fail in this example. Other method is not affected by the additional structure as it only add action with minimum reward.
the example in Figure 2a af = 3 then
Number plmplles
4000
5
5
1
-5
3000
SNIS
CRM
2000
1f,=
1000
2
a ==1 1
==2
(a) Example 2
(b) Example 3
(c) Number of samples to solve Ex- ample 2/3 for A = 2.
B PROOFS FOR SECTION 5
Proof of Theorem 1
12

---

Under review as a conference paper at ICLR 2022
Proof.
x(ap (0)
12
Σ
T(a (
(8)
2 EB( 53
2 EB 1 8)
Σ
max (0, T(a (aa (z/ 8L}
(9)
Σ
[0, T(a|=,) 8L} = óLLA
(10)
ac Ar (a (.6)
Proof of Corollary !
Proof.
max [W(), M}
max (OX) M1
Σ
Σ
(1I)
i= max (()) M)
nM
( (0) #1 EB(a
5)
a a ( .8)
max {E (0) EB
W M}
1 - 8LIA
(12)
nM
nM
Proof of Proposition
Proof. This due to x and u(alzx))) (2) are independent from history given a So w(( and ((O conditionally independent given (1)))
Proof of Theorem 2
Proof. We first prove the first part.
Let Pa(2; μ1) be the distribution of context at k-th step with roll-in policy p. For any fixed For a such that ((aax)) O. Pa. (x) a; p)) is also greater than zero. All (1) with a a i.i.d. samples draw from the distribution PA (I; 1)). By the property of nearest neighbor (Cover & Hart 1967). with probability
we can define the distribution (a(r|a; (.) = p(alz)) (2; p)/ Σ, P
dist(z, xx(²) 0<6
min 3.1.0
That means with probability a E (x; for all a such that ((alc)) > 0. Given the overlap assumption, have Ag (a; D) for for all such that क (a]=:) > 0 with probability 1. Thus the solution to Equation is the same as arg max, J(z, D) JJ.D-
Now we prove the second part. By the condition that M + oo and M 0 as - co, we have that the truncated IS estimator mean square consistent (Tonides) 2008):
H
II
( h
(
min
M
0"
(13)
as n. + oc. Similarly, we have that the mean of weights converge to in quadratic mean:
min
W
(1)
M
q.m. 1
(14)
13

---

Under review as a conference paper at ICLR 2022
Training Set
Validation Set
Test Simulator: rollout Real normalized truncated IS on test set
N Re-starts, hyper- parameters
Select the highest self- normalized truncated
Checkpoints
NxK policies
policy
Figure 3: The process of parammtas search and test in the experiment.
By continuous mapping theorem, we have that the self-normalized truncated IS converge vt in probability sSNTIS & n. The empirical variance penalty, also converge almostly surely, since M/v converge to O:
Ei=1 (r(0) USNTIs) (min(W(), MM)²
M
g.m.
0
(15)
(E =i min min(W() M))²
n min (W()), M7)
==
Thus the objective function J(T; D) converge to en in probability:
Pr(I)(T;)) 0²1 c) 8n +
(16)
Since we assume [II] < oc, we have
Pr (VT E [[J((T))) - - > t) |1
(17)
So with probability [ for any c:
AID 2 J( D)
(18)
2 {(T"; D)
(19)
0" 2e,
(20)
where n² is arg max v² As | O, we proved the value of empirical maximizer f converge to the maximum of value max 8 in probability.
C EXPERIMENT DETAILS
For all experiment, we follows the 3-phases pipelines to decide the test score we finally report in the paper. The pipeline is described the main text and summarized in Figure ??]here well.
C.1 EXPERIMENT DETAILS IN TGI SIMULATOR
The TGI simulator describes low-grat low-grade gliomas (LGG) growth kinetics in response chemotherapy in a horizon 30 months using an ordinary differential equation model. The parameter in ODEs estimated using data from adult diffuse LGG during and after chemotherapy horizon of 30 months. The goal in this environment is to achieve a reduction in mean tumor diameters (MTD) while reducing the drug dosage (Yauney & Shahl 2018). We includes the MTD, the drug concentration, and the number of month (time-step) in the context space. Notice that this context space non- non-Markov as it does not include all parameters in the ODEs. Actions are binary representing taking the full dose or no dose which is same as prior work (Yauney & Shah 2018). The reward each step consist of an immediate penalty proportional to the drug concentration, and delayed reward at the end measures the decrease of MTD compared with the beginning. Each episodes, the parameters including the initial MTD are sampled from a log-Normal distribution as (Ribba et al. 2012) representing the difference in individuals. The behavior policy is fixed dosing schedule of months (the median duration from Peyre et al. (0100) plus 30% of a uniformly random choice of actions. We run all algorithms (listed below). and 5 restarts, saving checkpoints along the training. Then we select the best policy for each algorithm by iSNns the validation set with 1000 episodes well.
used, in
training with 1000 episodes with different hyperparameters
14

---

Under review as a conference paper at ICLR 2022
Hyperparameeers In the first part of Table algorithm, except that the parameter b in PQL is set adaptively as the 2-percentile of the score on the training set in the original Laper|Liu al. (2020). As know the behavior policy, use the true behavior policy in BCQ and PQL. algorithm. So BCQ threshold takes only two values as the hehavior policy is e-deterministic so there are only distinct values. In the second part of Table 3 we specify for all algorithm. All policy/Q functions are approximated by
show the searched hyperparameters of each
some fixed hyperparameters/setinn fully-connected neural networks with two hidden layers with 32 units.
Hyperparameters
used in algorithms
values
POELA POELA, PO-CRM
0.05, 0.1, 0.5
CRM Var coefficient BCQ threshold
0, 0,0.1,
BCQ. PQL
0.0, 0.2
M in iSNTIS Max training steps
All POELA, PO-CRM, PO-H
1000
500
PQL All
5000
Number checkpoints
50
Batch size
BCQ, PQL
100
Table Hyperparameters in the TGI simulator experiment
The difference in the max update steps and checkpoints frequency caused by the fact that BCQ and PQL is updated by stochastic gradient descent and all policy optimization based on SNTIS is using gradient descent.
C.2 EXPERIMENT DETAILS IN MIMIC III DATASET
The MIMIC III sepsis dataset is available upon application and training: https://mimic.mit.co mit.eduffillgetinntttreeedd//
The code to extract the cohort available on: https://gitlab.dos ic.ac.uke www..cuuk/ACCIC wtt/A/Ciiiciin/AACliiiie patients. The contexts for each patient consist 44 features, summarized 4-hour intervals, for at most 20 steps. The actions consider the prescription of IV fluids and vasopressors. Each of the two treatments is binned into 5 discrete actions according to the dosage amounts, resulting in 25 possible actions. The rewards are defined from the 90-day mortality in the logs, 100 if the patient survives and 0 otherwise.
This cohort consists of data for 14971
We now provide details of the experiment on MIMIC III sepsis dataset here. We all algorithms on a training set with 8982 trajectories with different hyperparameters (listed below). and 3 restarts, saving checkpoints along the training. Then select the best policy for each algorithm by ósNTI on the validation set with 2994 trajectories. Finally we get the ÜSNTIS evaluation on the test set with 2995 trajectories.
In the first part of Table 4 we list the hyperparameters that we searched on the validation set for each algorithm, except that the parameter b in PQL is set adaptively as the 2-percentile of the score on the training set as in the original paper Liu et al. (220). In the second part of Table we specify some fixed hyperparameterr//sttinngs for all algorithm. All policy/Q functions are approximated by fully-connected neural networks with two hidden layers with 256 units.
As we explained, the difference in the max update steps and checkpoints frequency is caused by the fact that BCQ and PQL. is updated by stochastic gradient descent and all policy optimization based on SNTIS is using gradient descent.
C.2.1 ACTION VISUALIZATION FOR MID/LOW-SON PATIENTS
In the main text show the action visualization for high-SOFA (> 15) diagnose of how algorithm behave for the high-risk patients. For the completeness of results here we show the visualization of mid-SOFA (5 15) and low-SOFA (< 5) patient contexts.
15

---

Under review as a conference paper at ICLR 2022
Hyperparameters
used algorithms
values
POELA
0.4, 0.6, 0.8, 1.0 0.01, 0.02, 0.05, 0.1 1, 0.0, 0.01, 0.05, 0.1, 0.3, 0.5
ji threshold
PO-μ
CRM Var coefficient
POELA, PO-CRM
BCQ threshold
BCQ, PQL
M in dSNTI
All POELA, PO-CRM, PO-u
1000
Max training steps
1000
BCQ, PQL All
10000
Number of checkpoints Batch size
100
BCQ, PQL
100
Table 4: Hyperparameters in the MIMIC III sepsis experiment
C.2.2 ADDITIONAL ABLATION STUDY: WITHOUT EFFECTIVE SAMPLE SIZE CONSTRAINTS FOR HYPER-PARAMETE. SELECTION ON VALIDATION SET
In the main text, selected on validation set. This is to make sure we have large enough effective sample size on the test to provide reliable off-policy test estimates. Here show the result if do threshold the effective sample size on validation set. Generally, all algorithms will prefer a high off-policy estimates without enough effective sample size. On the test set, all algorithms yields a small effective sample size, thus unreliable off-policy estimates and large bootstrap confidence interval. The proposed methods is better than baselines but also has much smaller 95% bootstrap lower bound than with the effective sample size constraint.
effective sample size threshold of 200 for seaiicyhhppe-ppraanee
be
Method
POELA
PO-μ
PO-CRM
BCQ
PQL
Test SNTIS 95% BCa LB
87.63(86.29)
82.36
82.36
83.28
96.32
85.06(83.51)
64.92
63.48
56.65
57.25
95% BCa UB Test ESS
90.00(88.59)
94.22
93.62
100
100
528.18 (8(411()))))))
21.23
21.23
9.04
1.27
Table 5: Test evaluation without effective sample size constraint on the validation set, (0.05, 0.95)
BCa bootstrap interval, and effective sample size in the sepsis cohort of MIMIC III dataset. Value inside parenthesis of POELA is without CRM variance penalty.
16

---

Under review as a conference paper at ICLR 2022
Physician Policy
POELA
PO-mu
6000
IV fluid
2
4000
1
2000
norm-IS
BCQ
PQL
4
6000
IV fluid
-4000
2
1
2000
2 Vasopressors
2 Vasopressors
Vasopressors
(a) Action counts in mid-SOFA contexts
Physician Policy
POELA
PO-mu
4000
3000
IV fluid
2000
1000
0
PO-CRM
BCQ
PQL
3000
IV fluid
2000
11000
2
3
4
4
Vasopressors
Vasopressors
Vasopressors
(b) Action counts in low-SOFA contexts
Figure 4: (a): Action counts heatmap in mid-SOFA contexts of the policy learned from different algorithms. (b): Action counts heatmap in low-SOFA contexts of the policy learned from different algorithms.
C.3 IMPORTANCE WEIGHTS LOW-REWARD TRAJECTORIES
To examine if the proposed overfitting phenomenon exists in real experimental datasets, compute the importance weights of the learned policy on the low-reward trajectories the training data for MIMIC III dataset and tumor simulator. Our hypothesis is that overfitting of the importance weights in policy gradient methods may result in the algorithm avoiding initial states with low rewards, which motivated proposed algorithm.
In MIMIC dataset the reward for a trajectory is either 0 or 100. We define the low-reward
trajectories those with 0 reward. Low-reward trajectories 60% of all trajectories in the
17

---

Under review as a conference paper at ICLR 2022
dataset. In the Tumor simulation experiment we define low-reward trajectory when reward is less than -2. Over 95% of trajectories the Tumor simulation dataset are low-reward trajectories.
The table below shows, for each algorithm and setting, the sum of the SNTIS weights of the learned policy on the training set, for low-reward trajectory states. Our primary interest is to illustrate that alternate policy gradient methods that also suitable for non-Markov domains, can exhibit the importance sampling overfitting of avoiding low reward trajectories. We indeed see that our POELA method has much larger weight on low-reward trajectories than these alternate offline policy search methods:
Method
POELA
PO-H
PO-CRM
MIMIC III Tumor non-MDP
0.028
0.001
0.003
0.054
(fixed policy)
0.005
Table 6: Importance weights overfitting: sum of SNTIS weights of learned policy on the training set.
The Q-learning baselines we consider (BCQ and PQL) do not directly use the importance weights, but they do try to avoid actions and/or states and actions with little support. Our POELA method can be viewed as being similarly inspired, but for non-Markovian settings where policy gradient beneficial. We also compute the SNTIS weights of the BCQ/PQL policy on the training set in that our POELA, BCQ and PQL all still give significantly more weight to low reward trajectories than the alternate policy gradient methods:
the Markov domain that satisfies the Markov assumptions of BCQ/PQL. Here we
Method
POELA
PO-p
PO-CRM
BCQ
PQL
Tumor MDP
0.097
(fixed policy)
0.0004
0.083
0.124
Table 7: Importance weights overfitting: sum of SNTIS weights of learned policy on the training set.
These results help illustrate that the over avoidance of low-reward trajectories can be observed by past policy gradient methods in our datasets. Of course, one challenge is that in real settings, an excellent policy may have low importance weights in avoidable low-reward states and trajectories, but should have higher importance weights in non-avoidable low reward starting states and trajectories. To get fuller picture of performance, it is helpful to look both at the weights on trajectories with low rewards and the test evaluation results. Compared with strong policy gradient baselines, our proposed regularization method have larger importance weights on low-reward trajectories, and the gap between maining/validation evaluation and online test performance is also smaller, suggesting that we are less likely to learn policies that erroneously believe they can avoid unavoidable low reward settings.
C.4 THE EFFECT OF ELIGIBLE ACTION CONSTRAINTS 6
In this section we explore how the choice of 8, which constrains the policy class through impacting the eligible actions, impacts empirical performance. Larger 5 corresponds to less constrained policy class. Other hyper-parameters are selected by the same procedure as described previous sections.
As 8 increases, the policy search operates with less constraints. The results show that in this case, our policy gradient method produces a policy with higher value in the training set, but that policy may not perform as well in the test evaluation, and may have smaller effective sample size than when smaller is used. The best hyper-paramene value 8 lies in the middle of the explored range. can be selected based on performance and effective sample size.
18

---

Under review as a conference paper at ICLR 2022
0.4
0.6
0.8
1.0
training ÜSNTIS
91.62
98.41
98.9
99.12
training ESS
3601.12
2242.07
1993.08
1769.46
test êSNTIS
86.62
90.07
91.46
90.23
test ESS
1278.08
819.64
624.92
542.53
Table 8: The effect of eligible action constraints 5 on the results in MIMIC III sepsis dataset.
19


Reviews:
[{"review_id": "s2LffFnbaFJ", "reviewer": "Reviewer_oG3M", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I find the proposed method of this paper is quite intuitive and the baselines compared seem to be appropriate. The Example 1 is good to understand with more motivating examples in the appendix. I also love the clinically-inspired evaluations.\n\nMy concerns are as followed:\n1. Regarding the methods\n  - A) This phenomenon seems to only apply when highly negative reward are present. One way is to shift and scale the rewards to be positive, and capped the importance weights to avoid over-maximize the reward. I am curious if authors can compare with this method, or at least illustrate why this way of shifting reward will not work.\n  - B) The distance considered in the paper uses the euclidean distance in the raw input space, which may not work when lots of missingness present in the data, or in settings when some features of the inputs are not relevant to the reward. I think learning a meaningful latent space that depends on the reward like [1] could further improve this method.\n  - C) The novelty of this work is not high as similar ideas have been proposed but not particularly in the non-MDP setting as acknowledged by the authors.\n\n\n2. Regarding the experimental results\n  - A) Although it's intuitive that this overfitting phenomenon could happen theoretically, only qualitative figures in Fig. 1(b) support this claim. I believe it's crucial to support this statement in the experiments. I think authors can quantify it in both simulations and the MIMIC3 by showing that the importance weights are close to 0 for the baselines in lower-reward states.\n  - B) Since you use WIS as the validation metric, it might favor methods also optimized under IS-based methods but might give an disadvantage to non-IS based methods like PQL. Though I understand you have to choose a metric.\n  - C) In Fig. 1(a) why there is no blue point around x=200~400? Just want to see if blue actually is better in those regions.\n\n3. Regarding the presentations (this has little effect on my evaluation)\n  - A) Bolding table 1 and 2 can help readers quickly understand which method is better\n  - B) In Sec. 3 please list the source of equation (2). \n\n[1] Zhang, Amy, et al. \"Learning Invariant Representations for Reinforcement Learning without Reconstruction.\" International Conference on Learning Representations. 2020.", "summary_of_the_paper": "When optimizing an policy under batch data under importance weighting adjustment of batch data, this paper observes that methods can learn to ignore states with highly negative rewards by having lower support to the behavior policy. And this paper proposes to solve this problem by only constraining actions that have observed in the nearby states in the batch data. Although various similarly ideas have been proposed like regularizing toward behavior policy, this paper improves on importance sampling methods that does not assume MDP that separates itself from recent baselines like PQL. They also show some analysis on this problem. They show that compared to recent baselines they improve in a tumor growth simulation environment when MDP assumption is violated, and a real-world sepsis dataset.", "summary_of_the_review": "Pros:\n+ The method is easy and simple and shows improvement in both experiments that include non-MDP simulations and a real-world dataset\n+ The writing is mostly clear\n+ The improvement shown in a real-world clinical environment is encouraging.\n\nCons:\n- No quantitative analysis if the overfitting actually happens.\n- Simple heuristics like shifting rewards to be positive and avoiding over-maximizing reward is not compared\n- The novelty of this work seems limited since similar ideas have been proposed. \n- The distance considered in this paper may not handle missingness or when some input features are irrelevant to the reward.\n\nAlthough I feel the proposed overfitting phenomenon can be an interesting contribution, the authors should quantify if it happens in the experiments and justify their method by comparing with heuristics like shifting the reward. I think addressing these can further push the paper over the acceptance bar.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RPHGbLY5sA", "reviewer": "Reviewer_qYyg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Major comments:\n\n* In Section 3, the author(s) decomposed the importance sampling estimator into three parts and argued that the second term can be problematic. I suggest the author(s) to design a toy simulation example to evaluate the order of magnitude of these three error terms (the first error term being $E_{\\hat{p}} v^{\\pi}(x) - E_{p} v^{\\pi}(x)$ where $p$ corresponds to the oracle context distribution).  \n\n* In Equations (3) and (4), suppose we plug-in the empirical behavior distribution for $\\mu$, then $\\hat{p}(x)$ equals $W(x)$. This would solve the over-fitting problem. In practice, according to the semiparametric theory, even if the true importance sampling ratios are known to us, the resulting estimator with an estimated ratio would be more efficient (see e.g., Tsiatis, 2006, Semiparametric Theory and Missing Data). Would you please clarify why you did not use such a simple method with an estimated importance sampling ratio?\n\n* Would you please elaborate the constraint in Equation (6)? Why would such a constraint help solve the offline learning problem? \n\n* The condition $|\\Pi|<+\\infty$ is not sufficient to guarantee the validity of Theorem 2. As shown in the proof, $|\\Pi| \\delta_n$ shall decay to zero. The author(s) needs to provide an upper bound for $\\delta_n$ in the proof (as a function of M and $n$) and presents the corresponding condition for $|\\Pi|$. In addition, naively apply the Bonferroni's inequality would give a loose bound. Concentration inequalities would be preferred to relax the resulting condition for $|\\Pi|$. \n\n* The proposed algorithm relies on several tuning parameters, such as $\\delta$, $M$, $\\lambda$ and $\\alpha$. Is your algorithm sensitive to the choice of these tuning parameters? How would you recommend practioners to select these hyper-parameters? Could cross-validation be possibly employed? In addition, what policy class do you consider in the numerical experiments?\n\n* Just curious how the proposed compares with existing baselines in standard openAI Gym environment. Have you conducted some related experiments? \n\n* Since the numerical experiments use policy evaluation algorithms to compare different policies, I wonder if the estimated values are sensitive to the choice of the policy evaluation algorithm or the tuning parameters used in the algorithm. Would you please discuss? \n\nMinor comments:\n\n* Page 3, Line -12. Shall $hatp(x)$ be $\\hat{p}(x)$? \n* Page 4, Lines -17 and -18. Missing parentheses in $E [ ... ]$.\n* Page 6, Theorem 2. $M$ as a function of $n$?\n* Page 13, Line -14. \"to be\" -> \"be\". ", "summary_of_the_paper": "The paper considers offline policy optimization. The author(s) discussed the issue of overfitting of the importance weights in existing offline algorithms and developed an algorithm to alleviate the issue. Results are supported via theories and real datasets from healthcare applications. ", "summary_of_the_review": "My detailed comments are given under the \"Main Review\" section. I have some concerns about the motivation of the method (#2), the theoretical results (#4), the choice of the tuning parameters (#5) and the sensitivity of the estimated values in the empirical studies to the choice of the policy evaluation algorithms (#6). So I give a score of 5. However, I would like to increase my score shall my comments be addressed. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Iamc8uErlv", "reviewer": "Reviewer_EAaa", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\n- One major issue with the proposed approach is the expressivity of the policy class. Although authors in Theorem 2 have shown that asymptotically, the expressivity stays the same, one question here is that what really happens in the non-asymptotic setting and how much we loose expressivity with the introduced constraint.\n\n- In other words, the reviewer believes one missing part of this paper is to show how much local constraints on actions (eq. 5) is hurting the performance in the non-asymptotic setting. How does this loss change as sample size grows? Showing empirical results even on synthetic datasets will be helpful.\n\n- One issue with Table 1 is that authors say their approach does not make any Markovian assumption and hence, its performance is worse than other competitors in the MDP setting while it outperforms other methods in the non-MDP setting. One question here is that is this comparison fair? In other words, do other methods make Markovian assumption and at the same time we expect them to perform well in a non-MDP setting?\n\n- The writing of the paper needs a major review. Examples are but not limited to:\n\nPage 1, Introduction Section: “different than”\nPage 2, line 2: : “learning an policy”\t\nPage 2, Section 2, Line 6: “over next context”\nPage 2, Section 2: “also sometimes refered”\nPage 3, Section 3: “but a similar results”\nPage 3, Section 3: “for unnormalized estimator.”\nPage 5, Section 4: “function class is closed respect”\nPage 7, Section 6: “Euclidean distance in over”\nPage 7, Section 7: “details are provided are in the Appendix”\nPage 7, Section 7: “The reward consist of”\nPage 9, Section 8: “in a policy that under-weigh certain (lower performing) initial contexts”\n", "summary_of_the_paper": "In this paper, authors have introduced an overfitting phenomenon that has not been addressed in previous works related to policy optimization and importance sampling. They then propose a new constraint on policy and a new algorithm which avoids the overfitting. They have provided theoretical justification on why their proposed method works and show experimental results to show the effectiveness of their approach.", "summary_of_the_review": "This paper introduces a legit overfitting issue and proposed a solution for it. However, the reviewer is not convinced enough about the effectiveness of the proposed approach due to the concerns raised in the main review plus the fact that the paper needs a major writing revision.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "9uRE2uV_Bou", "reviewer": "Reviewer_2pVL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n- the paper tackles the important and relevant issue of overfitting in counterfactual risk minimization. the motivation is also nicely supported with some toy examples.\n- the paper identifies the source of overfitting that is not addressed in previous works.\n- the paper proposed a novel algorithm to address the overfitting issue with some gurantees  \nrelated work is covered rigorously \n- the code is provided as supplementary material. I encourage the authors to publicize it upon publication to ensure the reproducibility\n\n**Weaknesses**\n- I skimmed through the proofs of Theorem 1 and Corollary 1. They look correct, but the bounds seem very loose and might be meaningless. It would be more interesting to see how the empirical sum of weights are different among different methods using synthetic data. \n- All experiments are based on real-world data, meaning that the policy performances are now measured with OPE on a test set, which might not be accurate. Having synthetic experiments as a complement would strengthen the empirical contribution.\n- Do we still observe the overfitting issue when we use k-fold cross validation?\n", "summary_of_the_paper": "The paper studies the overfitting issue in counterfactual policy learning. The paper first  identifies an important overfitting phenomenon in optimizing the importance weighted return, and proposes an algorithm to avoid the issue. The notable limitation of some previous approaches is that they use penalization at the policy level and do not directly address the problem with avoiding contexts with low reward. The proposed POELA method addresses deficient support in the observed finite data rather than in the expected behaviors.  Some experiments show the benefit of the proposed approach.", "summary_of_the_review": "The paper identifies the unexplored aspect of the overfitting issue in off-policy learning. The motivation was easy to follow with some easy examples. I would recommend a weak accept at this moment. Some additional efforts in the experiments (as I described above) would strengthen the contribution more.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors proposed an offline policy optimization algorithm, motivated by an analysis of the upper bound error of importance sampling policy value estimator. Specifically, by the decomposition of the error in a particularly way, the authors identified some error which does not converge. Then, the authors introduce the contraints over feasible actions to avoid the overfitting induced by such errors. Finally, the authors tested the proposed algorithm empirically.

The paper is well-motivated and the authors addressed some of the questions in their rebuttals. However, there are still several issues need to be addressed, 

- The alternative practical estimator with plug-in behavior distribution would perfectly avoid the over-fitting, which is, however, ignored. This is an important and easy-to-implemented competitor.

- The pessimistic principle in the face of uncertainty (PFU) has been exploited extensively in offline policy optimization problem. How the proposed algorithm is connected to the PFU has not been discussed carefully, especially in terms of non-asymptotic sample complexity, which makes the paper is not well-positioned. 

- While the motivation is derived from the unbiased importance sampling estimator, the counterfactual risk minimization in Equation 7 is introduced suddently, without clear justification. 

- In my opinion, for a better clarification of the paper, the expressiveness of the policy family should not be discussed in this way. I understand the authors would like to avoid any possible degeneration, and explain the asymptotic lossless in terms of policy flexibility. However, the whole point of the paper is trying to introduce some mechanism to avoid the possible overfitting by regularizing the policy family. In other words, the restriction is on purpose and beneficial. I think the argument of policy family expressiveness should be re-considered and re-discussed. 


Minor: 

- Markovian vs. non-Markovian baseline comparison is not fair, and more comparison on well-known benchmarks, e.g., OpenAI gym, should be conducted. 
- The \sigma upper bound should be explicitly provided and verified in practice.

In sum, the paper is well-motivated, however, need further improvement to be pulished.
Decision: Reject