Blessing from Experts: Super Reinforcement Learning in Confounded Environments
Authors: Jiayi Wang
Zhengling Qi
Chengchun Shi
Venue: Submitted to ICLR 2023 (2023)

Abstract: We introduce super reinforcement learning in the batch setting, which takes the observed action as input for enhanced policy learning. In the presence of unmeasured confounders, the recommendations from human experts recorded in the observed data allow us to recover certain unobserved information. Including this information in the policy search, the proposed super reinforcement learning will yield a super policy that is guaranteed to outperform both the standard optimal policy and the behavior one (e.g., the expert’s recommendation). Furthermore, to address the issue of unmeasured confounding in finding super-policies, a number of non-parametric identification results are established. Finally, we develop two super-policy learning algorithms and derive their corresponding finite-sample regret guarantees.

Under review as a conference paper at ICLR 2023
BLESSING FROM EXPERTS: SUPER REINFORCEMENT LEARNING IN CONFOUNDED ENVIRONMENTS
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce super reinforcement learning in the batch setting, which takes the ob- served action as input for enhanced policy learning. In the presence of unmeasured confounders, the recommendations from human experts recorded in the observed data allow us recover certain unobserved information. Including this information in the policy search, the proposed super reinforcement learning will yield a super- policy that is guaranteed to outperform both the standard optimal policy and the behavior one (e.g., the expert's 's recommendation). Furthermore, to address the issue of unmeasured confounding in finding super-policies, a number of non- con-paraettric identification results are established. Finally, we develop two super-policy learning algorithms and derive their corresponding sample regret guarantees.
INTRODUCTION
Offline reinforcement learning (RL) aims to find a sequence of optimal policies by leveraging the batch data (Sutton & Barto 2018 Levine et al., 2020). In many high-stake domains such as medical studies (Kosorok & Laber 2019). it is very costly or dangerous to interact with the environment for online data collection, and learning must rely entirely on pre-collected observational or experimental data. Recently, there a surging interest in studying offline RL theories and methods. Most existing solutions rely the unconfoundedness assumption that excludes the existence of latent variables that confound the action-reward/-nexx unmeasured confounding, under which most existing RL algorithms will lead to sub-optimal polices.
associations. However, in practice we often encounter
In this paper, we study offline policy learning in confounded contextual bandits and sequential decision making, Existing works on policy learning focused on searching an optimal policy that purely depends on the past history, ignoring the recommended action given by the human expert in the observed data. In many applications, there a common belief that human pecision-maken have access to important information that is not recorded in the observed data when taking an action (Kleinberg et al., 2018). For example, in the urgent care, clinicians leverage visual observations or communications with patients to recommend treatments, where such unstructured information is hard to quantify and often not recorded (McDonald) 1996). Another motivating example is given by the deep brain stimulation (DBS Lozano al. 2019). Due to recent advances in DBS technology, it becomes feasible to instantly collect electroencephalogran data, based on which we are able to provide adaptive stimulation to specific regions in the brain as to treat patients with neurological disorders including Parkinson's 's disease, essential tremor, etc. In these applications, the patient is allowed to determine the behavior policy (e.g., when turn on/off the stimulation, for how long, etc) based on information only known to herself (e.g., how she feels), therefore generating batch data with unmeasured confounders. We notice that despite challenges in policy learning with latent confounders, human recommendations may capture certain unobserved information as discussed in aforementioned applications. Including this information as input of the policy can enhance policy learning, which is indeed "a blessing from experts". Therefore, in this paper, we ask
Is it possible to consistently learn an optimal policy that takes both the data history and human recommendation at the current time input for better decision making?
We will answer the above question affirmatively. Specifically, we first introduce novel framework called super RL, which compared with the standard RL additionally takes the human's 's recommenda- tion input for policy learning. In confounded environments, super RL can embrace the blessing

---

Under review as a conference paper at ICLR 2023
from experts. In other words, it leverages the human expertise in discovering unobserved information for enhanced policy learning. The resulting policy, which we call super-policy, is guaranteed to outperform the standard optimal one learned from without using the human expertise and the behavior policy that may depend on the hidden state. To implement the proposed super-policy for decision making in the future, we require the human expert recommend action at each time, which is commonly seen in practice. The super-policy then takes this action and other observations as input and override the recommendation produced by the expert. Second, to address the challenge of partial observability or unmeasured confounding, we establish several aanpaaametric identification results in finding these super-polictes in various confounded environments, leveraging the recent development in causal inference (Tchetgen Tchetgen et al.) 2020). Notably, our identification results prove that the super-policy is learnable from the observed data despite the presence of unmeasured confounding. Finally, we develop two super RI algorithms and derive the corresponding finite-sample regret guarantees that are polynomial in terms of all relevant parameters in finding a desirable super-policy.
2 RELATED WORK
There is an increasing interest in studying off- off-policy evaluation (OPE) and learning in sequential decision making problem with unmeasured confounding. Specifically, Zhaing & Bareinboim (2016) introduced the causal RL framework and the confounded Markov decision process (MDP) with memoryless unmeasured confounding, under which the Markov property holds in the observed data. Along this direction, many OPE and learning methods are proposed using instrumental or mediator
variables (Chen & Zhang 2021 Liao et al. 2021 Li et al. 2021 Wang et al. 2021 Shi et al. 2022
Fu et al. 2022 Yu et al. 2022). In addition, partial identification bounds for the off-policy ' va lue have been established based sensitivity analysis (Namkoong et al., 2020 Kallus & Zhou 2020
Bruns-Smith 2021). Another streamline of research focuses on general confounded POMDP models to allow for both unmeasured confounding and partial observability. Several point identification
Nair results were established (Tennenholtz et al. 2020 Bennett & Kallus [021]] Nair & Jiang [222] Shhi al. 202T; Ying al., 2021] Miao et al. 2022). However, none of the aforementioned works study policy learning with the help of human expertise, i.e., taking recommended action in the observed data for decision making. Different from these works, we tackle the policy learning problem from unique perspective and propose novel super RL framework by leveraging human expertise in discovering certain unobserved information to further improve decision making. We also rigorously establish the super-optimality of the proposed super-policy over the standard optimal policy and the behavior policy. Our paper is also related to a line of works on policy learning and evaluation with partial observability using spectral decomposition and predictive state representation related methods (see e.g., Littman & Sutton, 2001
Song et al., 2010 Boots et al. 2011 Hsu et al. 2012
Singh et al. 201 2 Anandkumar et al. 2014 Jin al., 2020 Cai al. 2022 Lu al.) 2022 Uehara
et al.
2022a b). Nonetheless, these methods require the no- cawnecasured-cooouuuee
assumption.
Finally, our proposal is motivated by the work of Stensrud & Sarvet (2022) that introduced the
concept of superoptimal treatment regime in contextual bandits. They used an instrumental variable approach for discovering such regime. However, their method can only be applied in a restrictive single-stage decision making setting with binary actions. In contrast, our super-RL framework is generally applicable to both confounded contextual bandits and sequential decision making allowing arbitrarily many actions. It is also worth mentioning that the proposed super RL differs from the recently proposed safe RL via human intervention (Saunders et al., (017), where human intervention is performed to override bad actions recommended by the intelligent agent. We aim to leverage the human expertise in the previously collected data for intelligent agents to make better decisions.
3 SUPER RL: A CONTEXTUAL BANDIT EXAMPLE
In this section, we introduce the super-policy in confounded contextual bandits (e.g., single-stage decision making with unmeasured confounders). Consider random tuple (S, U, A, where S and U denote the observed and unobserved features respectively. A denotes the action whose space is given by finite set A, and {R(a) Jas denotes set of the catettial/cuunterfacuuuul rewards under A = a, representing the reward that the agent would receive had action a been taken. The observed reward, denoted by R, can then be written as R = E.EA R(a)T(A = a).
2

---

Under review as a conference paper at ICLR 2023
Table 1: Policy values under different choices of in the toy example. In general, V(T))
1.6--1. 1.2e,
V(T") = 0.4, V(v*)= = |0.7- - cl + |c 0.3|. Bold values are the largest under different settings.
Policy Value
((TT))
V(T*)
V(v*)
é 0.5
0.0
0.4
0.4
é 0
0.6
0.4
1.0
6 =
-0.6
0.4
1.0
Denote the spaces of and by and respectively. Let :S P((A) denote a policy depending only on the observed information S, where P(A) refers to the class of all probability distributions over A. In particular, л [a 8) refers to the probability of choosing an action a given that S = s. In the batch setting, behavior policy n² S x U + P(A) that depends on both observed and unobserved features. Since U is unobserved, nearly all existing solutions focused on finding optimal policy x² given by
given i..d. copies of (S, A, Rt), where the action A is generated by some
x² ra s)
if a" argmax, E.A E (R(a) SS s] Vs E S.
(1)
assuming the uniqueness of the maximization in equation D for every s E S. In addition, notice that U may confound the causal relationship of the action-rewars in the observational data. Ignoring this latent confounder will produce a biased estimator of n²
As discussed earlier, in this paper, we aim to find an optimal policy that leverages the input of human expertise, since actions generated by the behavior policy depend on the latent information. In particular, we search super-policy v" in a larger policy class Ω = {u S A P(A)) such that
v"(a" |s,a') =1 a" = argmax E [R(a) = =, A= a'] v(s,a') E A. (2)
The two optimal optimal policies are equivalent when unconfoundedness assumption holds. When this condition is violated, E [R(a) S 5, A a'] * E. (R(a) | S s] in general. More importantly, it follows from Proposition 1 of Stensrud & Sarvet (2022) that the value under y² is no worse and often larger than that under π*. This yields the super-optimality of V² over ' It also worth mentioning that in the presence of latent confounders, there is no guarantee that the standard optimal policy r² outperforms the behavior policy n² because n² depends on the unobserved information. To the contrary, since n² E S2, the proposed super-policy is always better than N.. Specifically, let V(v) be the value under the intervention of a generic policy v, i.e., V(v) = E.EA E R(a))(( S, A)]. We have the following lemma that demonstrates the super-optimality of v³ over both Rt" and T.
Lemma 3.1 Suppe-Optimallty: V(v*)= 2 (ax("( V(T*)).
Intuitively speaking, the super-optimality of μ^ comes from the use of unobserved information U contained in x². We consider the following toy example to elaborate.
Toy Example: Assume S and U independently follow a Bernoulli distribution with success probabil- ity 0.5. Suppose the action is binary and the behavior policy satisfies P(A 1|5, U 1) P(A S,S,U = 0) =1- - - for some 0 < < 1. Let R = 8(4- - 0.5) OU - 0.3). In this example, the parameter & measures the degree unmeasured confounding. When 0.5, the behavior policy assumption is automatically satisfied.
does not depend on U and the no-ummeasured-comfouus Otherwise, this condition is violated. In particular, when e = 0 or 1, we can fully recover the latent confounder based on the recommended action. Table summarizes the policy values of n², x² and v² under different E, in which the super-optimality holds.
Despite its appealing property, it is generally impossible to learn the super-policy D² without any further assumptions, since the counterfactual effect E [R(a) S = s, A = a') is not identifiable from the observed data due to unmeasured confounding. Toward that end, we adopt the proximal causal inference framework developed by Tehetgen Tchetgen et al. (2020). Specifically, we assume the existence of certain action and reward proxies Z E 2 and W W in additional to (S, A, R). These proxies are required to satisfy the following assumptions (Miao et al. 20188):
Assumption 1. (a) R.I. | (S, A); (b) W WIL(Z,,) A)
(S, U), W YUU S; (c) R(a) (S,U)
for a E A: (d) There exists bridge function W x A x S - IR such that
E [g a, S) U, A a) E R U. A a).
(3)
3

---

Under review as a conference paper at ICLR 2023
Assumptions [a)-(b) are standard in proximal causal inference, requiring these proxies to meet certain conditional independence conditions. Assumptions [ called latent unconfoumdedness, is mild allow U to be unobserved. The last assumption can be satisfied when some completeness and regularity conditions hold. See Miao et al. (2018a) and also Lemma 3.3 below for more details. Then the following lemma allows consistently learn the super-policy v from the observed data.
Lemma 3.2. Under Assumption I we have E [R(a) S s, A = a'] Elg(W, a, S) | S s,A= a'), which further leads to that V(v) = E EnEA ( a, S)v(a) S, A) for any Ω.
In practice, one may want to include as many confounders in the policy as possible to achieve the largest super-optimality. Hence under this proximal causal inference framework, with some abuse of notation, we further extend the policy class to f {v S x 2 A P(A)} and consider the corresponding super-policy y² as
1/ v'(a" 1 s, 2,,,')==1 =1 if a' =araamaa E [(aa) | S = =,, 2 = ž, A = d'
(4)
where Z is a subset Z that continues to exist when we implement the super-policy. In applications where the action proxy is no longer available in future decision making, equation i reduced to cquation[] We also remark that different from Z, W is obtained after intervention. As such, it does not make
to include W in the super-policy. The following corollary allows to identify v*.
Corollary 3.1. Under Assumption
the policy value under given E Ω is given by V(v)
E EEEA q(W, a, S)v(a S,A, )
In addition, the optimal policy '* is given by
v'(a" 2,), if a' argmax (o(W,,, S) S A-
(5)
It can be seen from Corollary 3.1 that to identify the super-policy, it remains to estimate the bridge
function q defined in Assumption d). One can impose the following completeness condition.
Assumption 2. For any squared-integrabbe function g and for any (s,a) S x A. Bl)(U) 2,5
8, A = a) = 0 almost surely and only if g(U) = O almost surely.
Lemma 3.3. Under Assumptions 2 and some regularity conditions (see Assumption 7 Appendix
solving the following linear integral equation
E [a o, S) Z, S, A a| E |R| 2,5, a-
(6)
for every a E A with respect to gives a valid bridge function that satisfies Assumption [d).
Built upon Corollary 3.1 and Lemma 3.3 Algorithm | summarizes the procedure to find v/ from
population perspective. Practical procedure that learns 1" given samples can be found in Appendix B
Algorithm 1: Identification of n² in confounded contextual bandits.
Input: i..dd copies (S, 2, A, R, W).
Compute g by solving E [a( a, 5) Z, S, al= = B| Z, A for every E A. of 2(s, E 8 2 x A.
Compute a" arrgmax,.a E [(, a, S) S s,
Output: n" with D² (a") s,,,,d' for any (s, a').
SUPER RL IN SEQUENTIAL DECISION MAKING
4.1 MODEL SETUP AND
IN SEQUENTIAL DECISION MAKING
In this section, we formally introduce the super-policy in confounded sequential decision making, demonstrate its super-optimality, and present several non-parametric identification results. Consider an episodic and confounded POMDP denoted by M (S, A, P,r) where S and 24 denote the spaces of observed and unobserved features respectively, AA denotes the action space, T denotes the total length of horizon, P (Pr (PrYT_ where each P, denotes transition kernel from S x U A to x 24 at time t, and r = {rr)T=1 denotes the set reward functions over x U x A. The data following M can be summarized (S., Ut, A,, Rdy T where S, and U, correspond the observed
4

---

Under review as a conference paper at ICLR 2023
and latent features at time t, A, and R2 denote the action and the reward at time t. For simplicity, assume the action space is discrete and all rewards are uniformly bounded, i.c., | S Rmax-
Given an offline dataset, objective is to learn an (in-class) optimal policy to maximize the expected cumulative rewards. All existing works consider policies defined as a sequence of functions mapping from the past history (excluding the current action) to probability mass function over the action space A. Specifically, given a generic policy π = {Te M one can define its value function as
V (s, u) E
T Σ
Re S. 8, U, u for every (s, u) 8 U,
where E= denotes the expectation with respect to the distribution whose action at each time follows Tr. Existing works aim to leverage the batch data to estimate an optimal policy that maximizes
V(T) E Ui)],
where we use to denote the expectation with respect to the initial data distribution. Under unmeasured confounding, the observed action A, in the batch data is generated by some behavior policy x S u + (PA) for 1 t T. Let T = {=/]]=1-
To handle unmeasured confounding, (Wa)?=1 and action proxies {2,){== that can help identify policy values. In sequential decision making, shown in [Tennenholtz et al. (2020), past and future observations can be served as the two proxies in confounded partially observable Markov decision processes (POMDPs). As such, our method can be applied most confounded decision-making problems where human agents will recommend actions in the future. Concrete examples of these proxies are given in later sections and Appendix A Previous works such as Lu et al. (2022) focus on finding ' E II = {x {5e]7- Te S x 2, + }P(A) such that x² argmax_ enn (TT). In particular, when Z,s are certain current features that can serve as the action proxies (see Section 4.2). II corresponds to the class of stationary policies. When Z,s are given by the entire data history (see Section (..). IT corresponds to the class of general distory-dependent policies. When Z,s are given by the most recent k-step observations (see Section 4.4), 11 corresponds to the class of k-memory policies.
similarly assumee the existence of certain reward proxies
Motivated by the discussions in Section we propose to learn super policy v² E S = {v {vr 2/4 S x Z, x A + }(A)) which leverages human expertise for enhanced policy making that maximizes (2v). Here AA in 12 reflects the action space at the current time point Actions recommended by the expert before time can be included in Zq. See Section 4.3 for more details. When considering Ω the policy value V(v) indeed depends on z² as well because to implement the proposed super-policy
require the human agent produce action according to x² and then intervene using p. However, to ease notation, we omit T when referring to (V()). Similar as before, since the super-policy additionally uses the expert's recommendation that depends on the unobserved information, we expect the super-policy v" to be superior to both ' and x²,, which is shown below.
Theorem 4.1 (Super-Optimaliyy V(v*)= 2 max(V(**)) (TT)))
4.2 IDENTIFICATION OF STATIONARY
VIA Q-BRIDGE FUNCTIONS
Under unmeasured confounding, apply the proximal causal inference framework to sequential decision making and make following assumptions to identify the policy value (iv) for each v e Q. Assumption 3. (a) (Markovianity) The process (Se, Ur, Ac, R. T satisfies the Markov prop- erty, i.e., for any I, (R,, S441, U(+1) depends on the past history only through (S,, U, At).
(b) (Reward proxy) WL U.-1 St-1) (U,, Si), W. W.K S., for 1 StST.
(c) (Action proxy) Z, IL RR, W., S141, U1+1, W++1) (U,, St, A.) for S
Assumption 3 is satisfied by a wide range of confounded sequential decision making models. See Appendix [A for detailed discussions. Specifically, Assumption (a) is mild. It essentially requires the data to be Markovian if we were to observe (U.) Assumptions (b) and (c) extends Assumption I to sequential decision making. In this section, we require the existence of current features that can serve as action proxy and focus on learning an optimal stationary policy. Alternatively, one can set the action proxy to past observations, as in Sections Without loss of generality, we also assume these action proxies continue to be available when making decisions in the future. Otherwise, can restrict the super-policy to be function of (St, As) only.
policies. 4.5 and study distory-dependee
5

---

Under review as a conference paper at ICLR 2023
To identify V(z) and ultimately v" under unmeasured confounding, we rely the existence of a class of Q-bridge functions {g: fr=1 defined over W x S x A such that for every (s, u, a) E S 4 A.
E" ET= Re U2, St, A1]
E (Wi, a)vcla St Z, Ar) U.. St. A,]
(9)
Theorem 4.2 (Identification). If there exist {a Jt=1 that satisfy equation 9 then the value of policy 1/ can be identified by V(v)= = af oi S1, a)vu (a S1, 21, A.
The following theorem proves the identifiability of these Q-bridge functions under certain complete- ness and regularity conditions. Together with Theorem 4.2 it forms the basis to learn the super-policy from the observed data. Let (WW, S,, Zz, At) = of (We, St, a)v SS,, Az).
Theorem 4.3. Under Assumption 3 and certain completeness and regularity (Assumptions 8 and 10 in Appendix F) there always exist Q-bridge functions {qī ) satisfying equation 9 In particular, set 07 0, qr can be obtained by solving the following linear integral equations for T, T,...,
1E St. Ad) Re- 1 S4+1, Z441, A(11) Ze, St. A.} O.
(10)
4.3 IDENTIHICATION GENERAL HISTORY
SUPER-POLICIES
In this section, we set Ze = [O A1: S, - 9 and W, to certain future features that can serve as a reward proxy that satisfies Assumption bb (e.g.. conditionally independent of the current action). The corresponding space of Z, is given by 2, = IT' O x I A. Alternatively, one may set Z, {0 1:t--))) 11) and W; to the current observation as in Tennenholtz et al. (2020); Shi et al. (202T) to meet Assumption 3 The resulting model is reduced to a typical POMDP with unmeasured confounding and we present the identification results in Section 4.5 We focus on the case where A1:(t-1) in Zr are generated by the behavior policy instead of the super-policy. The policy
II: - (O A) P(A)), which includes all actions recommended by the expert for decision making but those generated by v E Ω. We leave the inclusion of these actions in the policy class future work. To ease notation, omit "history" hhiistory when there is no confusion. Let Og denote some pre-collected observation before the decision process initiates. We impose the following additional assumption:
class we focus is given by Qhhistory = {v {vt)
Assumption 4. (a) 1 1st5 (c) O E O is generated from U2 by some unknown map H4,
U,, Zt, A,, for 1 < t < T - 1; (b) 1LO, U,, Z1, for
O.
Assumption 4 (b) can be easily satisfied by initializing the decision process at / = 2. Assumption 4 c) is often imposed in POMDPs. Then we have the following identification results.
Theorem 4.4. Assume assumptions 3 4 and certain completeness and regularity conditions in (g))T=
Appendix F hold. Define t 0, and {al ) over W [ A) the solutions the following linear integral equations:
E d (W,, Zz, Ar) Rs-
Σ (4 Ze+1, a)vi(a) 4441,441) Zr, Oo. A 0, (11)
aeA
for = T,T 1....,,,
...,. 1. Then we could identify the policy value for v E Quisttryy as V(v) E [a (W1, Z1, A1)].
(12)
Theorem 4.4 allows us to identify general bistory-dependent policies.
4.4 IDENTIFICATION OF K-STEP HISTORY-DEPENDEN
POLICIPS
In Section 4.3
discuss how to identify the value of history-dependent policy by taking Z, as past observations up to time t. As a result, the dimension of Ze increases linearly with f, resulting in the curse of dimensionality and history (Pineau et al. 2006). In this section, we consider more practical class of policies that only use the most recent k- ktstep observations. Policies this type are widely used in practice (see e.g., Mnnh et al. 2015 Berner et al. (019)).
To begin with, let W, be the future proxy reward that satisfies Assumption B). For any t 2 + 1, let Z, E 2, denote the observed history from time ( k up to time 1, i.e., (O ((-k):(t-1))-

---

Under review as a conference paper at ICLR 2023
We further define 2, 7 Ze-1 E 2 as subset of Ze. Next, we define the Q-bridge functions (g)) It= over W x Ze x A such that for every (u,a) E U A and t k 1,
B T Ry U, = E/EAEA of (W,, 2, a)us(a Z, AD) 1 [t,
(13)
Under certain regularity conditions (Assumptions 13 and 14 specified in Appendix F). we are able to identify the Q-bridge functions (4e )[=x++ through the following linear integral equations.
Theorem 4.5. Under Assumptions B] Mc), Assumptions 13 and 14 in Appendix [F] there exist Q-
bridge functions {g¹ )(=k|] satisfying equation 13 In particular, set 4f = 0, of can be obtained
by solving the following linear integral equations for ...... , ++11
(W,,, Z,, A.) R4 Σ aEA
d+ta a) A44) Z, A.)= = 0. (14)
As for 1 S k take Zz (OLa, A if additionally Assumptions 11 12 in Appendix F and
Assumption 4 ab-(b) on Ou hold for S S ks then there exist {q:' 1t= over W = x A) as the solution to the following linear integral equation for / = 1,....kk
EE (g (W, Ar) - Rs- Σ aEA
a (W Zi+1, a)v Z441, Ze, Oo, A:} = 0, (15)
where Ou denotes some pre-collected observation defined in Section 4.3 Finally, the policy value can be identified as V(v) = Elg' (W1, Z1, AI)].
We remark that the requirement for Og in Theorem 4.5 is much weaker than that in Theorem 4.4 In
particular, here we only need Assumptions 4 (b)- I and 12 to hold for the first l steps. W When
t 2 k 1, we require the variability of Z, to cover the variability of (U,, Ze), which to some extent requires the observation at k-th lag has sufficient variability relative to the variability unobserved state at the current time (U,). As the lag &s increases, this assumption becomes more restrictive.
4.5 ALTERNATIVE IDENTIFICATION OF SUPER-POLICIES
In Section 4.2 we discuss how to identify the policy value via Q-bridge functions assuming the existence of certain future observations (W₂) that can serve as reward proxy and are conditionally independent of the current action. As commented earlier. this condition can be relaxed by setting W, = Or, Z, = {(Or:t-1); A1:(t-1) and S, = 0. The resulting data generating process is reduced to the POMDP model studied in Tennenholtz et al. (2020). However, based on identification results in Sections 4 4.4 this rules out the dependence of the super-policy the most recent observation, which could be restrictive. In the following, we provide a remedy for addressing this limitation.
For simplicity, we focus on identifying given history-dependent super-policy v == {mr) 's value, where V/ : IT== (O A) + ((A) depends all the past observations and recommended actions. We consider a tabular setting where all random variables can only take finitely many values and use boldface letters Rdd, Rd... Rdd to represent the vectors consisting of all possible rewards, latent states and observations. Meanwhile, our results can be extended to general settings as well using value-bridge functions (Shi et al.) 2021). Let On denote some pre-collected observation. The following assumption summanizes the conditions for the model:
Assumption 5. (a) The process (U,, Ar) satisfies the Markov property; (b) For all 1 S ( S T, the observation O is generated from U, by some unknown map H, Ul - O: (c) For all 1 5 t $ T.
O 11 (R,, O,, U++1) At).
We define the following matrices:
[P(te) jigj
Pr((R, ri, O, = 4, a, O.1 = oj);
pl1 Rd.xdd; p(() e Rdoxdo;
[P!0) Pr(O, = 0; A a, 0,- = 0,),
[p(t.e) al = Pr((O+1 = o₁ Or = o, Art1 =d d' A, = a 0, 1 = 0j),
p(t) plt) E Rdoxdo
[P(t)] Pr(U, u; A = a, O 0j),
p(i) E Rduxdo
7

---

Under review as a conference paper at ICLR 2023
Theorem 4.6. Under Assumption 5 as long Pad) and Pa are invertible for any 1..., and a E A, the value function V(v) for any v E Qt is identifiable. In particular,
v(u)
Σ Σ
01, vx(ax ok, -..--.,, 01, "(,a(())'
o1 aa k=1
1 )
II
plk,o) or. ap
= =
A=t-1
SUPER-POLICY LEARNING WITH REGRET GUARANTEE
Based on the established identification results, introduce our super-policy learning algorithms and establish the corresponding finite-sample regret bounds. We only focus on settings described in Sections and 4.2 Other settings can be similarly studied, which will leave as the future work.
5.1 CONFOUNDED CONTEXTUAL BANDITS: REGRET GUARANTEES
We develop practical algorithm in Appendix based on the minimax estimation (Dikkala et al. 2020b. Let 0 denote the output Algorithm 3 in Appendix which relies on the estimation bridge function & given by equation Define the Le norm of a generic function f as || V Let gSS Z, A f) = ([ S) S, I, A] for any f defined over W x S. For given projection estimator E, let Ú(S, Z, A. B[((W, S) S, Z, A] denote the corresponding estimator. Define
EGEA Tb
U
s) = a' 2,
Pmax
sup a.s.2,al PEE
Tbl A' d' U u. =
Lemma 5.1. Suppose belongs to certain function class Q C > A. Define the projection error as En == suppeQ,ae . g(., a)] -.. g( a)]ll and the bridge function estimation error as Co = 114 áll2 Then we obtain the following regret decomposition
V(v*) v(0*) 2(E.. + PmaxCa).
Suppose and the projection estimator are computed by the procedure described in Appendix B When Q (the function space for q) and G (the function space for the projected function) are VC- subgraph classes, we have the following theorem for the regret guarantee. Results when & and are reproducing kernel Hilbert spaces (RKHSs) are provided in Appendix L.3
Theorem 5.1. If the star- sar-sh spaces G and are VC-subgraph classes with VC dimensions V(g), and VG)) respectively. Under assumptions in Theorems 1.2 and 1.4 with probability at least 1 - 6,
V(6*) V(v") S n 1
Pinax / /og((1 1/6) + max (V()), V(O)),
where for any two positive sequences {an lns (ba Ins an S b, means that there exists some constant C > 0 such that a, Cb, for any
5.2
CONFOUNDED SEQUENTIAL DECISION MAKING: REGRET GUARANTEES
Now we present our super-policy learning algorithm for the sequential setting introduced in Section 4.2 Given the identification results in Theorems 4.2 and 4.6 obtain the super- policy V one solution is to directly search over the space of super-policies that maximizes the estimated value, i.e., & argmax (zv). However, when T is large and models im- posed for estimating bridge functions are complex (e.g., deep neural networks), direct opti- mizing ((v)) requires extensive computational power. Motivated by Theorem 4.3] we pro- pose fitte-QQiiteattion type algorithm (Algorithm 2 for practical implementation and estab-
8

---

Under review as a conference paper at ICLR 2023
lish the regret bound in finding the super policy v' under memoryless unmeasured confounding.
Algorithm 2: Super RL for the confounded POMDP
Input: Data D (Dt) with D. {(St,,, Z, As,t, Ra,, Wa,, S1.41 21,+1, We
Let 0r+1 = and b/ be an arbitrary policy.
Repeat for = T , 1:
Obtain an estimator de for gt via a min-max estimation method in Appendix [1 using Dr 2, A. d') for E A using the method in Appendix 1.2 and obtain the estimated super policy ij as for every (a', 2, 8),
Compute Egg. St,a) a) - Z.
(a("a 8, 2.)
argmax (W, St, a) S = s, Ze = 2, = a'l
Output: 8² = {0,)7=1-
Assumption (Memoryless Unmeasured Confounding). For S S T, U4 is independent of past data history (including latent factors in the past) up time - 1 given Sy.
We introduce some notations. Define p and p as the marginal distributions of all random variables at time under the policy v and behavior policy %b respectively. Define constants Pt,max == sup,, Pi (8, 2, a)/p," (s, 2, a), and prx = ... wi (s, a,, where w (s, 2, a) denotes certain density ratio whose explicit form is given in equation 29 of Appendix H
Let Q(t) denote the class for modelling Qt- Define 9r (e,S, Ze, A:; 9(: : a)] = Elg(W,, St. a)
S. Ze, A,] for q E Qit) and E A. Consider two projection errors Êt, := 0(t), .. ((:..a) - g......:: gl
St, Zi, A,] and [r, Zi, A ((v.,a)) == (W,,
l
and G... which denotes the projected error related to the computation in line of Algorithm 2 The The finite-sample regret bound of 1
exact definition of C.n is given in equation of of Appendix [ by Algorithm 2 relies on the following regret decomposition.
Lemma 5.2. Suppose q: E Q(0) for 1 S T and Ø computed via Algorithm Then under
Assumptions 3
6 8
and 10 we obtain the following regret decomposition,
- (ww)~v(0')
&
Σ 2pt, maxt
+
T
(Se,.))
t=1
In Appendix [ we provide detailed analysis of &,,. and Gr.n regarding to the critical radii of local Rademacher complexities of different spaces, when qt is estimated by the conditional moment method and the projection [[g(W,, St, a) St Z,, (i2,AA As] is estimated by the empirical risk minimization. Here we provide regret bound which is characterized by the VC dimensions. Let g(1) be the space of testing functions in the min-max estimating procedure described in Appendix I.1 and H(O) be the space of inner products between any policy v E Ω and E @(t) with H(++1) = (0). See the exact definitions of ((t) and (t)) in Appendix I.1
Theorem 5.2. If the star-shaped spaces g(t), H((+1) and ((t) are VC-subgraph classes with VC
dimensions V(g("), ((H(++1)) and V(g(t)) respectively for 1 S l S T. Under assumptions
specified in Theorems I.1 and 1.3 with probability at least
(og(T/6) + max (V)()) V(L V(H())
V(6") V(u*) S
Σ (pr.max + Pr, + 1)2.5 1)25
When ((t), Q(t) and H( are RKHSs, we establish the corresponding results in Appendix L.3
CONCLUSION
In this paper, we introduce super reinforcement learning. which takes the observed action as input for enhanced policy learning. We establish the identification results for the super-policy in various confounded environments. Practical algorithms are proposed to perform the super policy learning and corresponding finite-sample regret guarantees provided.
super-policy

---

Under review as a conference paper at ICLR 2023
REFERENCES
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15: 2773-2832, 2014.
Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. The Annals of Statistics,
2005.
Andrew Bennett and Nathan Kallus. Proximal reinforcement learning: Efficient off-policy evaluation in partially observed markov decision processes. arXiv preprint arXiv:2110.153322 2021.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large seale deep reinforcement learning. arXiv preprint arXiv:
2019.
Byron Boots, Sajid M Siddiqi, and Geoffrey J Gordon. Closing the predictive state representations. The International Journal of Robotics Research, 30(7):954 966, 2011.
loop with
David A Bruns-Smith. Model-free and model-based policy evaluation when causality is uncertain. In International Conference on Machine Learning, pp. 11 16-111... PMLR, 2021.
Qi Cai, Zhuoran Yang. and Zhaoran Wang- Sample-efficient reinforcement learning for pomdps with linear function approximations. arXiv preprint arXiv:2204.09787, 2022.
Marine Carrasco, Jean-Piere Cann-ieerre Florens, and Eric Renault. Linear inverse problems in structural econo- metries estimation based on spectral decomposition and regularization. Handbook of Econometrics, 6:5633-5751, 2007.
Shuxiao Chen and Bo Zhang. Estimating and improving dynamic treatment regimes with time- varying instrumental variable. arXiv preprint 2xXiv22144078222, 2021.
Alfred F Connors, Theodore Speroff, Neal V Dawson, Charles Thomas, Frank E Harrell, Douglas Wagner, Norman Deshiens, Lee Goldman, Albert W Wu, Robert M Califf, et al. The effectiveness of right heart catheterization in the initial care of critically iii patients. Jama, 276( I 1):889-897, 1996.
Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis. Minimax estimation of conditional moment models. arXiv preprint S00i:::0006072001. 2020.
Zuyue Fu, Zhengling Qi, Zhaoran Wang, Zhuoran Yang, Yanxum Xu, and Michael R. Kosorok. Offline reinforcement learning with instrumental variables in confounded markov decision processes. 2022. doi: 2..4555//ARXII.2299.... 086666. UtL/ttps:: /ttp://aaaivviviii org/ abs 2209. 08666
Daniel Hsu, Sham M Kakade, and Tong Zhang. spectral algorithm for learning hidden Markov models. Journal of Computer and System Sciences, 1660)1446 2012.
Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-effcieet reinforcement learning of undercomplete pomdps. Advances in Neural Information Processing Systems, 33: 18530-18539, 2020.
Nathan Kallus and Angela Zhou. Confounding-rooust policy evaluation in infinite-horizon reinforce- ment learning. Advances in Neural Information Processing Systems, 33:22293-22304 2020.
Jon Kleinberg, Himabindu Lakkaraju. Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. Human decisions and machine predictions. The quarterly journal of economics, 133(1):237-293 2018.
Michael Kosorok and Eric Laber. Precision medicine. Annual review of statistics and its application, 6:263-286, 2019,
Rainer Kress. Linear Integral Equations, volume 82. Springer, 1989.
10

---

Under review as a conference paper at ICLR 2023
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643, 2020.
Jin Li, Ye Luo, and Xiaowei Zhang. Causal reinforcement learning: An instrumental variable approach. arXiv preprint arXiv:2 1X3:2200300422. 2021.
Luofeng Liao, Zuyue Fu, Zhuoran Yang. Yixin Wang, Mladen Kolar, and Zhaoran Wang. Instrumental variable value iteration for causal offiine reinforcement learning. arXiv preprint arXiv:2102.09907, 2021.
Michael Littman and Richard S Sutton. Predictive representations of state. Advances in Neural Information Processing Systems, 14, 2001.
Andres M Lozano, Nir Lipsman, Hagai Bergman, Peter Brown, Stephan Chabardes, Jin Woo Chang, Keith Matthews, Cameron C McIntyre, Thomas E Schlaepfer, Michael Schulder, al. Deep brain stimulation: current challenges and future directions. Nature Reviews Neurology. 15(3):148-160 2019.
Miao Lu, Yifei Min, Zhaoran Wang. and Zhuoran Yang. Pessimism in the face of confounders: Provably efficient offline reinforcement learning partially observable markov decision processes. arXiv preprint
2022.
Clement McDonald. Medical heuristics: the silent adjudicators of clinical practice, 1996.
Rui Miao, Zhengling Qi, and Xiaoke Zhang. Off-policy evaluation for episodic partially observable markov decision processes under non parammeetttic models, 2022. URL httttts//aaxxi..ooett abs abs/2205 10064
Wang Miao, Zhi Geng, and Eric Tchetgen Tchetgen. Identifying causal effects with proxy variables of unmeasured confounder. Biometrika, 105(4):987-99)) 2018a.
Wang Miao, Xu Shi, and Eric Tchetgen Tchetgen. A confounding bridge approach for double negative control inference causal effects. arXiv preprint arXiv: 04945, 2018b.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-333, 2015.
Yash Nair and Nan Jiang. spectral approach to off-policy evaluation for POMDPs. arXiv preprint 1xXi:2119.11000 2021.
Hongseok Namkoong, Ramtin Keramati, Steve Yadlowsky, and Emma Brunskill, Off-policy policy evaluation for sequential decisions under unobserved confounding. Advances in Neural Information Processing Systems, 33:18814 19-188831, 2020.
Thesath Nanayakkara, Gilles Clermont, Christopher James Langmead, and David Swigon. Unifying cardiovascular modelling with deep reinforcement learning for uncertainty aware control of sepsis treatment. PLOS Digital Health, 1(2):0000002, 2022.
Joelle Pineau, Geoffrey Gordon, and Sebastian Thrun. Anytime baset-based approximations for large pomdps. Journal of Artificial Intelligence Research, 27:335-380, 2006.
Zhengling Qi, Rui Miao, and Xiaoke Zhang. Proximal learning for individualized treatment regimes under unmeasured confounding. arXiv preprini arXiv:2105.01188 202.
Aniruddh Raghu, Matthieu Komorowski, Imran Ahmed, Leo Celi, Peter Szolovits, and Marzyeh Ghassemi. Deep reinforcement learning for sepsis treatment. arXiv preprint ArXiv:1711.096000 2017.
William Saunders, Girish Sastry, Andreas Stuhlmueller, and Owain Evans. Trial without error:
Towards safe reinforcement learning via human intervention. arXiv preprint 17XXv:1777.0555 2017.
11

---

Under review as a conference paper at ICLR 2023
Chengchun Shi, Masatoshi Uehara, and Nan Jiang. A minimax learning approach to off- evaluation in partially observable Markov decision processes. arXiv preprint arXiv:2111.0677 2021.
Chengchun Shi, Jin Zhu, Ye Shen, Shikai Luo, Hongtu Zhu, and Rui Song. Off- confidence interval estimation with confounded Markov decision process. arXiv preprint arXiv:2202. 10589, 2022.
Satinder Singh, Michael James, and Matthew Rudary. Predictive state representations: A new theory for modeling dynamical systems. arXiv preprint arXiv: 2012.
Le Song, Byron Boots, Sajid Siddiqi, Geoffrey J Gordon, and Alex Smola. Hilbert space embeddings of hidden markov models. 2010.
Mats J Stensrud and Aaron L Sarvet. Optimal regimes for algorithm- assisted human decision-maken making. arXiv preprint arXiv:2203 2022.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Eric J Tchetgen Tchetgen, Andrew Ying, Yifan Cui, Xu Shi, and Wang Miao. An introduction to proximal causal learning. arXiv preprint arXiv:2009. 10982, 2020.
Guy Tennenholtz, Uri Shalit, and Shie Mannor. Off-policy evaluation in partially observable en- viromments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10276-10283, 2020.
Masatoshi Uchara, Haruka Kiyohara, Andrew Bennett, Victor Chernozhukov, Nan Jiang, Nathan Kallus, Chengchun Shi, and Wen Sun. Future-dependent value-based off-policg evaluation in pomdps. arXiv preprint 2rXiv:2207.13081, 2022a.
Masatoshi Uehara, Ayush Sekhari, Jason D Lee, Nathan Kallus, and Wen Sun. Provably efficient re- inforcement learning in partially observable dynamical systems. arXiv preprint 220.22206..2020. 2022b.
Lingxiao Wang, Zhuoran Yang, and Zhaoran Wang. Provably efficient causal reinforcement learning with confounded observational data. Advances in Neural Information Processing Systems, 34: 21164 21175, 2021.
Andrew Ying. Wang Miao, Xu Shi, and Eric Tchetgen Tchetgen. Proximal causal inference for complex longitudinal studies. arXiv preprint arXiv:2109.07030, 2021.
Mengxin Yu, Zhuoran Yang, and Jianqing Fan. Strategic decision- makinn in the presence of information asymmetry: Provably efficient rl with algorithmic instruments. arXiv preprint arXiv:2208. 11440, 2022.
Junzhe Zhang and Elias Bareinboim. Markov decision processes with unobserved confounders: A causal approach. Technical report, Technical Report R-23, Purdue Al Lab, 2016.
A POMDP STRUCTURES AND PROXY VARIABLES
A.1 POMDP STRUCTURES
In Figure we illustrate the general POMDP structure regarding to the variables (U,, St, Ar, ReYT Figure providds example of the POMDP structure under the memoryless assumption (Assumption 6). As [ all the information from the past time steps is transited to the next step only through the current observed state S. Figure 3 provides
illustration for the causal relationship of all the variables involved in the confounded POMDP. At any time step t, the reward proxy W, is only related to the action A, through S, and Ug; the action proxy Z, is only related the reward R, through S, and U,. In Section A.2, we provide more illustrations about the relationship proxy variables with other variables.
12

---

Under review as a conference paper at ICLR 2023
R
R
R1+1
Up-1
Up
Uc+1
A
Ac
A++1
S
Sc
Sp11
Figure 1: The data generation process under typical POMDP.
U,-1
Re-1
Up
R
Ut+1
Re+1
S
Ac-1
S
Ac
S
Ar+1
Figure 2: The data generation process under the memoryless POMDP.
W
Rt-1
W
R
W
R
Up-1
U:
U
A
A
A
St-1
Se
Se11
Z
Ze
Zu+1
Figure 3: An illustration of the causal relationship of variables involved in the confounded POMDP.
A.2 PROXY VARIABLES
In this section, we discuss several options for proxy variables W, and Z, satisfying the basic assumption (Assumption 3
13

---

Under review as a conference paper at ICLR 2023
In Figure 4 we list some plausible causal relationship among W,, Uz. A.. We require the effect between U2 and W exists, but the effect between W2 and Rg is optional. For concrete examples of We, readers refer to the discussion of type variables in Tchetgen Tchetgen et al. (2020).
W
R
W
Re
We+1
R141
Up-1
U,
Uc+1
Ac-1
A
Ac+1
St-1
S
Sc11
Figure 4: Causal relationship between We and other variables. Dashed arrows indicate the causal effect is optional.
Once we determine Wt, we can select Ze accordingly. Figure 5 shows several different relationships of the action proxy Z, with other variables. the left plot Figure 5| Ze is one of the cause of A, and Z, JL (U,, S,) Ar. In this case, Z, can be considered an instrumental variable for Ar. In the middle plot of Figure 5 (U,, S.) is direct cause for Zr, the effect between Ze and A, can in both directions and can be optional. As for the right plot in Figure 5 Ze direct effect of U, and S,. And the effect between Z, and A₁ can be both directions and can be optional. For concrete examples of choices of 7, in the observational study, readers refer to the discussion of type we also discuss the cases when
variables in TTchetee Tchetgen et al. (020). In Section 4.3 and 4.4 7, includes previous history.
R
R
U2
U
A
A
A
S
S
Zz
Z:
Ze
Figure 5: Different causal relationship between Z, and other variables. Dashed arrows indicate the causal effect is optional.
B LEARNING ALGORITHM FOR CONTEXTUAL BANDITS
In this section, present the practical algorithm (Algorithm 3 for finding the super-policy in our contextual bandit example. The key step is to estimate the bridge function by the linear integral equation stated in Lemma When S Z x A W are all finite and discrete. it can be straightforwardly estimated. the following, we discuss the estimation when the general space is considered.
14

---

Under review as a conference paper at ICLR 2023
Algorithm 3: Learning Algorithm for the contextual bandits under unmeasured confounding
Input: Data D = (Si, Z, A,, R4, Wa)
Obtain the estimation of the bridge function by solving the estimation equation equation 6 using data D
Implement any supervised learning method for estimating E [6(W, 5, S,
Compute a" = arggax İ ([, S, a) S = 8, 7 = 2, A = a'] V(8,2,a') ( ex x Output: 8r with D(aa) 5, 5, a') 1 and ( s, 2, a') for + a².
We consider the conditional moment estimation procedure Dikkala et al. (2020) and propose to estimate Q-bridge function by
U q = arg sup (g. g) X |191 + A 1119112. + Apllelle. TEQ lEG
(16)
where (g. g) E (a S., A.) R g( St, A.), Q is the function space that we as- sume q"' lies in, G is the function space where the test functions g come from, X, μ. A, U are some tuning parameters.
As for the projection Big(W, S =, Z A = a'], the conditional moment framework can be also adopted to perform the estimation, here we propose to estimate it via the empirical risk minimization.
0 ((.:)a)) == arg min 9Eg
Σ
- a(.,;,a]] L9(S,, - + :leel
(17)
n i=1
where q is defined in equation 16 >> 0 is a tuning parameter.
C SIMULATIONS
C.I SIMULATION STUDY FOR CONTEXTUAL BANDITS
In this section, we conduct two simulation studies to evaluate the performance of the proposed super-policy. The first one is contextual bandit example with tabular state values. We aim to demonstrate the super-policy performs better when the behavior policy reveals more information about the unmeasured confounders. The second one is contextual bandit example with continuous state space. It is used to demonstrate the performance our algorithm using the bridge function.
A contextual bandit with tabular state values
Similar to the toy example described Section 3 we take S' and U as independent binary variables such that Pr(S 1) 0.5 and Pr(U 1) 0.5. The binary action A is generated by the following conditional probabilitics
Pr(A 1 U =
0) 0) =,
Pr(A = 1)
with different choices of E [0. 1]. The larger the Je 0.5| is, the more information of U is revealed in the observed action A. Both the reward proxy W and the action proxy Z are binary and are generated according the following conditional probabilities
Pr(W 1 U = 0) = 0.4,
U
Pr(W = -) 0.6;
0) Pr(Z = 1) - 0.4,
Pr(Z = 1 U 1)=
Moreover, W and Z are conditionally independent given U. The observed reward is computed by R = (U - (A (A- - 0.5) + e where e ~~ (0 0.5).
Three types of policy classes considered.
1. SONLY: S + P(A). The policy only depends on the observed state S.
2. SZONLY: S x Z + P(4). The policy depends on on the observed state S and the action
proxy Z.
3. SUPER: S x Z x A + P(A). The super-policy class where the policy depends on the observed state S, the action proxy Zr, and observed action A.
15

---

Under review as a conference paper at ICLR 2023
Table 2: Simulation results for the tabular setting described in C.1 under different choices of e. We replicate the simulation for 50 times. Mean regret values for estimated optimal policies under different policy classes are provided (and smaller regret value indicates a better performance). Values in the parentheses are the standard deviations of the regret values.
SONLY
SZONLY
SUPER
6 0.5
0.25 (3. le-04)
0.21 (1.7e-02)
0.21 (1.4e-02)
0.7
0.25 (3.1e-04)
0.22 (1.8c-02)
0.18 (3.5e-02)
E = 0.9 0.25 (2.5c-04)
0.24 (1.2e-02)
0.17 (8.6c-02)
Table Simulation results for the continuous setting described in C.1 under different choices of c. The simulation is performed over 50 simulated datasets. Mean regret values for estimated optimal policies using different policy classes are provided. Smaller regret values indicate better performance. Values in the parentheses are the standard deviations of the regret values.
SONLY
SZONLY
SUPER
c = 0.5
0.40 (9.6c-04)
0.14 (6.1c-03)
0.12 (2.5c-03)
0.7
0.40 (9.2c-04)
0.12 (5.9c-03)
0.11 (3.5e-03)
c = 0.9
0.40 (1e-03)
0.11 (1.3e-02)
0.065 (1e-02)
We implement Algorithm to estimate the corresponding optimal policies for different policy classes. Note that for SONLY and SZONLY, we perform the projection step (line 4) by conditioning S and (S, Z) respectively. Since this is a tabular setting, we use the empirical averages to approximate all the conditional expectations. In this simulation study, consider the sample size 5000. As Table[]shows the super-policy produces smaller regret as e deviates from 0.5 more, while the estimated optimal policies such as SONLY and SZONLY do not change and have larger regrets.
contextual bandit with a continuous state
In this setting, we take S and U as independent Gaussian random variables such that S ~~ NN, 1) and U [(0, 1). The binary action is generated by the following conditional probabilities
Pr(A = 1 I > 0) -, Pr(A = U < 0) = 11 -,
with different choices of e E []. The larger the Ic 0.5| is, the more information of U is revealed the observed action A. We generate W and Z according to the following conditional probabilities
W (S,U) ~ N(S + 3U, 1);
2 (S, A) ~ N(35 + U + 1..
Moreover, W and Z conditionally independent given (S, U). The observed reward is computed by R R==00 (U (A - 0.5) + where ~ (0, 0.5). For this continuous setting, we compute the Q-bridge function via the min-max conditional moment estimation described in Appendix by taking G, Q as reproducing kernel Hilbert Spaces (RKHSs) equipped with Gaussian kernels. The bandwidths of Gaussian kernels are selected by the median heuristic. Tuning parameters of the penalties are selected by cross cross-valdattion Computation details can be found in Section E of Dikkala al. (020). As for the projection step, we adopt kernel ridge regression (KRR) to perform the estimation, and the tuning parameter of the penalty is selected by cross-validation. In this simulation study, we take the sample size n 1000.
Table 3 shows the simulation results over 50 replications. The observation is consistent with that in the tabular setting. And the super-policy outperforms the other two commonly used optimal policies when deviates from 0.5.
C.2 A SIMCLATION STUDY FOR SEQUENTIAL DECISION MAKING
In this section, we perform a simulation study to evaluate the performance of the super-police in the sequential decision making. Specifically, mainly follow the data generation process
16

---

Under review as a conference paper at ICLR 2023
Table 4: Simulation results for the sequential decision making problem described in simulation is performed over 50 simulated datasets. Mean regret values for estimated optimal policies under different policy classes are provided. The smaller regret values indicate better performances. Values in the parentheses are the standard deviations of the regret values.
The
SONLY
SZONLY
SUPER
5.4 (1.9--1)) 5.3 (4.7e-01) 2.2 (4.9e-01)
described in Section F.1 of Miao et al. (0222) ). and only change the reward function to R₂ (x, 0.5)) + ct. where 62 Uniform(-0.1,00 We take the sample size as n = 1000 and the length of episode 7 = 20. Note that this setting satisfies the memoryless assumption (i.e., Assumption ( We implement Algorithm 2 to estimate the optimal policies from three policy classes considered in Section C. by adjusting the projection step accordingly. We again use the RKHS modeling to perform the min-max max conditional moment estimation for obtaining sequence of Q-bridge functions and implement KRR to estimate the projections at every iteration. See implementation details in the discussion of the continuous setting in Section C. To obtain the regret value, we estimate the optimal policy which depends on both S, and U2, and use to approximate the oracle optimal value. Table 4 summarises the simulation results over 50 simulated datasets. As we can see, the super policy performs significantly better than the other two commonly used optimal policies.
and cxpit(x) = 11((1 + cxp(-x)
D REAL DATA APPLICATIONS
D.1 APPLICATION TO RHC DATA
In this section, we evaluate the performance of our method on the dataset from the Study to Understand Prognoses and Preferences for Outcomes and Risks of Treatments (SUPPORT Connors et al. 1996).
SUPPORT examined the effectiveness and safety of direct measurement of cardiac function by Right
Heart Catheterization (RHC) for certain critically ill patients in intensive care units (ICU). This
dataset has been studied by many existing works (e.g. Qi et al. 2021 Tehetgen Tchetgen et al. 2020).
Our goal is to find optimal policy on the usage of RHC that maximizes 30-day survival rates 30-day survival rates of critically ill patients from the day admitted or transferred to ICU.
This dataset corresponds to the setting of contextual bandits. There are 5735 patients, of whom 2184 were measured by RHC in the first 24 hours (A = I) and the remaining were considered in the control group (A = 0). If patient survived or censored at day 30, we let the response Y = 1, otherwise, we take the response as Y = 1. Following the data pre-processing steps in Qi et al. (202I), consider 71 covariates including demographics, diagnosis, estimated survival probability, comorbidity, vital signs, and physiological status among others in this study. See the full list of covariates in petts://hh3t ostat............ orgg hrg//da data repo/ / rhc. html In particular, we take the action proxy Z = (pafil, paco21) and the reward proxy W = (ph1, hemal). ).. For more details and justifications of the choices of proxy variables, we refer readers Section 6.1 TehTeeegen Tchetgen et al. (2200).
We compare the super-policy with the following two policies considered in Qi et al. (202] di (L, Z) and di (L), where d1 (L, Z) corresponds to the policy in the policy class SZONLY and di (L) cor- responds to the policy in the policy class SONLY. To make it more comparable, we use the same estimating procedure for the bridge functions considered in these three methods. In addition, the RKHS modeling for the min-max conditional moment estimation is taken to obtaín the Q-bridge function. See details of the RKHS modeling in the continuous setting in Section C.I Since Qi et al. (2021) adopt the linear modeling for the decision functions d (L, 2) and di (L), we also use the linear regression to obtain the projection (line 4) in Algorithm
To evaluate the value by different policies, we randomly separate 40% of the data and use it as the evaluation set E. More specifically, after obtaining the estimated optimal policies using 60% of the data, we perform the policy evaluation of these three estimated optimal policies using the remaining 40% of the data. Take q as the estimated bridge function using &. The evaluation is
17

---

Under review as a conference paper at ICLR 2023
Table 5: Evaluation results of the optimal policies learned from three different policy classes using the RHC data. The averages of evaluation values over 20 random splits are presented. Larger values indicate better performances. Values the parentheses are standard deviations.
SONLY
SZONLY
SUPER
0.55 (5.80e-02)
0.55 (5.78e-02) 0.69 (1.10e-02)
Table 6: Evaluation results of the optimal policies learned from three different policy classes using the MIMIC-III data. The averages of evaluation values over 20 random splits are presented. Larger values indicate better performances. Values in the parentheses are standard deviations.
SONLY
SZONLY
SUPER
-2833 (5.30c-02) -2811 (5.03c-02) -1.75 (1.14c-02)
conducted as follows. V(z) E{E @(W, a,a)v(a A.), for v SUPER; V(x) E{E ((W,,, S, a)x(a| S, Z)), for π E SZONLY; V(T) E{E.EA ((W, S,W,Sa S)}. for SONLY. The expectation E. refers to the average with respect the evaluation set
Table shows the evaluation results over 20 random splits. As we can see, the super-policy produces higher policy values compared with the other two methods.
D.2 APPLICATION TO MIMIC3 DATA
In this section, we use the Multi Multi-paramettrr Intelligent Monitoring in Intensive Care (MIMIC-II) dataset (https: : h/phys senyssiness ionet. orq/ httpe//g/goooooooooonoeo poontent/mimiiiii1.
to demonstrate the perfor- mance of estimated optimal policies from three policy classes (SONLY, SZONLYY and SUPER). This dataset records the longitudinal information (including information of demographics, vitals, labs and scores, see details in Section 4.3 of Nanayakkaaa et al. (2022) of patients who satisfied the sepsis criteria, and the goal is to learn an optimal personalized treatment strategy for sepsis. Despite the richness of data collected at the ICU, the mapping between true patient states and clinical observations usually ambiguous (Nanayakkara et al. 2022). and therefore makes this dataset fit into the setting of confounded POMDP.
We obtain a clean dataset following the same data pre-processing steps described in Raghu et al. (2017). Based on it, take (vasopressor administration, fluid administration) the action variable, (-1)*SOFA as the reward function. We take (Weight, Temperature) as the reward proxy W since they are not directly related the action. All the remaining variables except for aforementioned ones are treated as observed state variables. The action proxy is taken as (Weight, Temperature) observed from the last time step. And it natural to assume that (Weight, Temperature) observed from the last time step is not directly related to the response at the current time step. To simplify the complexity of the action space, we discretize vasopressor and fluid administrations into 2 bins, instead of 5 as in the previous work (Raghu et al. 2017). This results in 4-dimensional action space. The numbers of episode length for every patient differ in the dataset. We decide fix the horizon 2, and exclude those patients with records less than 2 time steps.
Following the estimation steps described Section C.2 we estimate the optimal policies under policy classes SONLY, SZONLY and SUPER respectively. We also adopt the idea of "random splitting" described in Section D.I to evaluate different policies. Basically, we randomly divide the data into two parts with equal sample sizes. We use one part the training data to learn optimal policies. The other part is used for evaluating the corresponding policies. We implement the off off-policy evaluation method proposed by Miao al. (2022) in the confounded POMDP to calculate the policy values.
18

---

Under review as a conference paper at ICLR 2023
Table 5 summarizes the evaluation results over 20 random splits. As see, the super-policy produces higher policy values compared to the other two methods.
E TECHNICAL PROOFS IN SECTION 3
Proof of Lemma 3.1
|
V(T')= = E
(a E E
R(a)t* (al S, Z, A
aEA
AEEA
}
$
E
E
R(a)v'(a S, 5 A
V(v)).
The first inequality is due to the optimality of v^. Similarly, for the behavior policy x², we can show that
R(a)1(a= A) S, }
}
V(T))
E
E
aEA
8, R(a)v*(a S,2, ( } v(v)).
E
E
Proof of Lemma 3.2
E [R(a)] S = 8, A = a'I = E |B (R(a) U,8
E [ U,S =
(18)
E [B --
E [[ A=
(19)
E EE
a') s A a!)
(20)
E (1) ==
where equation 18 because of Assumption c). equation
19 from equation 3 in Assumption
and equation 20 is due to Assumption ().
To close this section, we prove Lemma 3K3
The following regularity condition is imposed. For
probability measure function let L (x(()) denote the space of all squared integrable functions of with respect measure μ(z). which Hilbert space endowed with the inner product (91.92)
In (x)))))))))( For all s, a, 1, define the following operator
Ks.a 2 [wWls.A(w 8, a)) - I {Az]s,A(= |s,a)} h 1+ == =
and its adjoint operator
K L2 (PzISAA (,,) La [uw]s,A(w s,a)]
g E+ W = w. = =a.
Assumption 7 (Regularity conditions for contextual bandits). For any Z z, 8, W w, A
(a) Jlwxz fwiz.s,1(w 2, a) fz,,z w. w.s,a) co, where fw.1z,,8.A4 and SS.AW are conditional density functions.
(b)
E (R,
= S A a}} fz1s.a(e s,a)dz < co.
19

---

Under review as a conference paper at ICLR 2023
(c) There exists singular decomposition (As,a;u: Ps,a; aaa, of Ke such that,
(E (Re Z = 2.5 8, = a} )s.a cc.
Proof of Lemma 3.3
From equation 6
we have
E R (W,A, 2,S,A] A,5) U, A 2,8,A)
E R ((W,
(21)
E R A,,5, U,S,A] 2,5,A),
where equation 21 is due to Assumption Tb). Then by Assumption we have
ER qW, U,S,A]=0,
which exactly equation 3 addition, by Proposition Miao et al. (2018a), the solution to
equation exxist under Assumption
7 Then Lemma 3.3
proved.
F TECHNICAL PROOFS IN SECTION 4
Proof of Theorem 4.7 First of all, note that there is one-to-one corresponding policy of m. and x²
in Ω respectively. Specifically, for { we can let vf (a St, d') 1(a = a') almost surely to recover тe. For x², we can always choose y" such that nr (a S, At) = x (a S.). This completes proof that v² achieves the super-optimality.
Next, to show Theorem 4.3 we need to make some additional conditions.
Assumption 8. ( A (Uz, Sr, A,) for S -
Assumption (Completeness). For any as) 8 A, ,,...,T,
(a) For any square-integrable function g. [(((U,) Z,, = -8 8, = a} = a.s. if and only
g 0 a.s;
(b) For any square-integrable function g. (fg(Z)) W. s, a a.s. and only
if g = 0 a.s.
For a probability measure function 14, L22 (1(()) denote the space of all squared integrable functions of x with respect to measure ((x)), which is Hilbert space endowed with the inner product (g1.92) 91 (z)g2 (z du)()))
Assumption 10 (Regularity conditions). For all 8, a, t, define the following operator
Ka 2 (Pwiss..s (w s, a)} + L2 {uzzss.. (z s, a)}
(h(W,) Z, 2, S, 8, At = a}.
Take K aat as the adjoint operator of Kg
For any Z. S. = W. w, A. a and 1 < T, following conditions hold:
(a) [fwxz Sw. (w 8, 12,,a) S. w, a)dwdz < oc, where fwalz.. and fz. W.S.A.A. are conditional density functions.
(b) For any E G(++1)
/ [E (Re + g(We+1, S441, Ae41, A++1) 2; = S. =s a}1² fz.1s.. s,a)dz < co.
z
(c) There exists a singular decomposition (As,astur, as the ass of Ks such that for all E ((++1)
2 Martw
KE (Re + 9(W41, Se+1, Acs1) 1 2, = 2, St = Ar veraaww) < oo.
20

---

Under review as a conference paper at ICLR 2023
(d) For all S T, of G where G satisfies the regularity conditions (b) and (c) above.
Now we are ready to prove Theorem 4.3
Proof of Theorem 4.3 Part I. We suppose there exists of satisfying equation 10 1 t - T.
Define (WW, St, Ze, A,) EoEn Sr St, Zz, As) and VT+
Then
RR Vit1 (W 411 1 Z441, [c)
=F R. + Vi-1 (W Se+ Ze+1, A(+1)
U,, Z,, St; Ar] Ze, St, St, A.]
=E E { R + Vi-1 (W4+1, S441, Ze+1, A(+1)
U2, At] Z₁, Zt, A.] by Assumption and
and
A,) Ze, Ar} =E E (al (We, St, Ad) U,, Ze St, A,) Z,, St,Se, A.]
E
=E E (o (We, St, At)
St A.) Z,, St, A.] by Assumption
Therefore, by Assumption 9 (a), we have
E ( Re + Vi S441, Z+11, 1441144411 A4t1) (41 and for any A.
St, A.] = (W,, A,) St A.}
a.s.
E [Ra + (W,,,, Z (.+1) A, =
=E (W,, Ai) U4, a) = (4 S, U2 St, A a}
=E (W a) S.
(22)
Next, we prove that
E" [Re + Set Zeti, Ac41) Sc Z, A.} E Σ
St, Ze, A.) U. St, Ze, Zr.Ane a.s.
(23)
Take Wit1(a), (()))))) Z++1 (a), (1+1(a) as the counterfactual variables had the action a is taken the current time as For any
E" {Re (W Z 4411) U. Ze, Al=i =a}
Σ E (
(d), [U, U,, Z,, 4,
d'EA
vi(al) Se Zr A a)
+ |4
|U, A, a]
a'EA
mlla' |S, Z, A, by Assumption
E
| vila' S A, =
AEA
Σ d'A
E +
Un, Sr, At d') ve(a' Sr, Z,, A. a)
UU, S Sr, Z,, A. a) by equation 22
Elg
A'A
Σ (Wd a'EAA
Z,, a] (a St. Ze. Ar a),
where the fourth, fifth and last equations are based on the unconfoundedness assumption once U, is given and W, is independent of (A,, 7x) given U,, St. Therefore, equation 23 is verified.
21

---

Under review as a conference paper at ICLR 2023
Part II. We will use this Bellman-like equation equation 23 to verify equation 9 and thus establish the identification results. First, at time T, by equation 23 and
T+1 = 0,
E" (Rr Sr, Zr, Ar) E
Σ LEE
a)rr(a Sr. Zr, Ar) Ur. Sr, Zr, Ar
By induction, suppose that at time + 1, E" EE Ry S Up+1 Zo41 Act1
{ VEt (We+1, S1+1. A041,)411) S441, U11 Z441; A441) Then at time t,
E
Σ P'=t
Ry
U2, As
T
-F"
Rs + E.
Σ
Re
S441, Z411, A Un, Se Ze, A1)
Un. Sr. Ze: Zr: Sr.
W=t+1
T
=E"
Rs + E"
Σ
Z Act1) |u, Zr Re
by Assumption! 3
#=t+1
=B"
R4 + E (Vi+ (WW1 S1+1, Zet1, Act1)
ULt1, Stt1, Ze+1, Act1)
Ut, Ze, As S141, Ze41, A4t1, U2, St, Zr, A1)
=E"
Rs + E (V (W2-1, Ze+1, Act1)
Sr 21,
by Assumption
=R RR + E" (Wi,, S4+1, Z Att1) U441, Si+1; Z411, A U4, Se Z, A1)
Ur, Ze Ar}
=B EE {Re + WW S141, (441 Uc, St, Ze, At} by the law of total expectation
E Σ (W,, S,, (a S, A4) Uv, S₁ Zn, A by equation 23
Part III. Now we prove the existence of the solution to equation 10
For to T.... 1. by Assumption 10 (a), Ka.a is a compact operator for each (s, E S x A
(Carrasco et al., 2007, Example 2.3), so there exists a singular value system stated in Assumption (c). Then by Assumption 9 (b), we have Ker( K a,aa)) = 0, since for any g E Ker(K (at))
we have, by the definition of Ker, K 2ang E [g( Z.) W St = s,
al = 0, which implies
that 9 =
Therefore Ker(K" k,a))) 0 and Ker K? (
1,2 A. (z (,,a).. By
Assumption 10 (b), E (R, g( 4+1, S141, Ze41, A++1) Zt =, A₁ a} Ker(K" (3) (.
for given (s, a) E S, x A and any g E ((+1), Now condition (a) in Theorem 15.16 of Kress (989)
has been verified. The condition (b) is satisfied given Assumption TO Recursively applying the above argument from = to t = yields the existence of the solution to equation 10
Next, we show our generalized identification results stated in Section 4.3 Before that, we make the following assumptions.
Assumption 11 (Completeness conditions for history-dependent policies). For any a E A, L =
(a) For any square-integrable function g. B, 7:) 7,, A, a} = 0.s.. if and only if 0 a.s;
(b) For any iquere-integrable function g. E(g(Z,, W, Z,, A, = a} = a.s. if and only a.s.
if
Assumption 12 (Regularity Conditions for history-dependdnt policies). For all z, 2, define the following operator
Ke.tt L2 (Awilzenad (w |2,a) LL2 {uool|2.A, (z)o,)))
h h E (M(W.) Z, 2, Ou o, A: a).
22

---

Under review as a conference paper at ICLR 2023
Take K aa;t the adjoint operator of Kz,,t
For any Z, = 2, Ou = o, W = w, = a and $ <t S T, following conditions hold:
(a) wo fw, (o.0AA (w 2, w, (,.,,,, [ w, 2, a dddddo co, where (w. and 2.., are conditional density functions.
(b) For any G(++1)
E [Rt + 9(W Zet1, Act1) Ze = 2, =, foslzuni 2, a) co.
Z
(c) There exists a singular decomposition (Az,attir, 22,actur V2,actu) of K2,az such that for all G(++1),
(R, g(W Z,41, A.t1) Z, = Oo =. = at v 22 co.
2mm
(d) For all StST. of ( where (( satisfies the regularity conditions (b) and (c)
above.
Now ready to prove Theorem 4.4
Proof of Theorem
4.4
The structure of the proof and related arguments are similar to the proof of
Theorem 4.3
Mainly, we will show the solution of equation 11 satisfies the following equation
T
E
Σ
RR U. A,
E Σ
(W,, Zz, a)a((a Z,, A.) U2, A
Lt==t
LaEA
where E" refers expectation taken with respect to {4: Therefore we only list several key steps in the corresponding three parts of the proof. Take Vi" A,) = EaEA (W, Ze. (a Zz, At).
I. By Assumption
and we have
E Rr V (We+,, Ze+1, Ac+1) Up, Zz Oo, As}
E (Re + V Z441, A441) U,, Ze, A!}
and
E (2 (W,, 2,, A.) U, Z. Oo A.) (g Z,, A,) | Ur, Zz, Ar).
Then by Assumption II (a), we have
E Ei + Vi+1 (WW Z A(t1) Ur Z, A1} E (W,, Zz U2 Ar) a.s.
and therefore
E" { Re + V (WH1,,741 441) U, Z, 4, = Σ
Z,, a)u((a Ze Ad) Ue, Ze, A A a.s., (24)
LGEA
where E" refers to expectation taken with respect to {ve)T
Part
II.
Following the same induction idea,
we can show that (V#+_WW+1, Ze+1, A441) U141 Zeer, 1
E"
Σ Eimet Rr U1+1, Ze+i, Ac+1
then by utilizing equation 25 at time t, we can obtain
E"
Σ
Re Ur, Ze. Ac A
Σ
of (W,, Zi a)u Ze, At) Uc, Ze, At
AEA
where E" refers to expectation taken with respect to {n, 1T Part III. The existence of the solution equation can can be verified by utilizing Assumption (T) and Assumption 12
n
23

---

Under review as a conference paper at ICLR 2023
Lastly, in order to show generalized identification results stated in Section 4.4 adapt the completeness and regularity assumptions as follows.
Assumption 13 (Completeness conditions for k-step history policies). For any A,
t t= t=k+1....,1
Ze. A. = a} = a.s. if and only (a) For any square-integrate function 9, B(g(Ui, Z,)
g 0;
(b) For any square-integrable function g. B(g(Zz) Wi, 2z, A. a} a.s. if and only
g 0 a.s.
Assumption 14 (Regularity Conditions for k-step history-dependern policies). Define the following conditional expectation operator:
Ks,azt : L (M ((w, 2) s, + L2 (UZ,)s,,,, s.
h h(W, 2,) 11 = =2,5; 58 A, = a) and take K saa as its adjoint operator. For any 2 3, Ze = 2, s, W = w, A: = a and
k ++1 < T.
(a) ( 2,, and f(... S.. are conditional density functions.
((w, 8) 2, 2,8, a),a2 W. S,,, (= | w, w, 8, a dddddddz < co, where
(b) For any E G(++1),
/ E (Re + 1,,,,,,,44, Z411, Act1) 2: = 2, = -8, Ae aa]² (2.15... 8, s,a)dz < co.
z
(c) There exists a singular decomposition (As,att;es as v (s,aat;)) of K such that for all g G(++1)
satt (E (Re + Sen,
12 = 2, s, A: =a} a ) < co.
(d) For all k + 511SIST, E G(O where ( satisfies the regularity conditions (b) and (c) above.
Now we are ready to prove Theorem 4.5
The results for < t < can be obtained by directly applying the proof of Theorem 4.4 Here only show the proof for the case when t > k. The proof structure and argument are quite similar to the proof of Theorem 4.3 Therefore, we list several important steps in three parts of the proof. Take vy (W, Ze, Ae) = ELEA 4: (W,, Ze, a)v(a At)
Proof of Theorem 4.3
Part I.
By Assumption
Z411, { RR W A441,4411 Uz Ze, A1} E R₁ (M U. Zz, Ar
and
E df (We, Zt, A.) Uc, Zz, A1] =E ( 2, Ab) UU, A1)
Then by Assumption 13 (a). we have
A4+1) U2, Zí, Ar] = { (We, Z,, 1 U2, 2z, A13 a.s.
and therefore
E" {Re + (WH1, A411) Ur, Zz Ar)
Σ
d (W., a)v((a Ze, Ar) Uc, Ze. A A
a.s.
..A
(25)
24

---

Under review as a conference paper at ICLR 2023
where E" refers to expectation taken with respect to {pe)T=r-
Part
II.
Following the same
induction idea, we can show that
E"
E Ev=++1 Ry U1+1, Ze+i, A4+1
E (Viza Ze+1, A441) U241 Zett, A }.
then by utilizing equation
25 at time
E"
Σ P'=t
Re
Un Ae
E
Σ AEAAA
(W,, Z), Zi, Up. Zt.
where EE" refers to expectation taken with respect to {ur 17 equation 14 be verified by utilizing Assumption 13
f=t- Part III. The existence of the solution
b) and Assumption 14
G TECHNICAL PROOFS IN SECTION 4.5
Proof of Theorem 4.6 We notice that Ot-1 (R O₂, (UU,)(U, Ad). Consequently, the condi- tional distributions of (Re, Oz) and (U1+1, Ot) given (A,, U1) shall satisfy
Pr(R, = r, O2 = olA, = a, U, = u) Pr(U, = ul = 0, 0,-1
Pr(R: O2 a|4 a, 01-1
(ffr))
Pr(U++1 = u, = o|A = 0, U, = u) Pr(Up = u A 0, 0, -
Pr(U1+1 u, O2 A a, 02-1 -
pft.
Pr((U++1 = u, Ar+1 = d',O, = of = a, U, = u) Pr(U, = u A = 0, 0, 0)
= =Pr(Ut+1 = u, A141 = d,,0, = 0 A = a, 0,-1 =
p(.a)
Pr((O, o u) Pr(U: = u/ = 0 = Prr(O -
A O2-1 1
p(()
u), Accordingly, Pr(R,, = r, 0, = = a, u). Pr(U141 = u, O, = olA₁ = a, a = u). Pr((U, u, A.+1 a' O2 olA,, a, u) and Pr( olU u) correspond to the
matrices consisting of all conditional probabilities. When (()) and Pr(U, = u/A, = 0 = 0) are invertible, it allows us to represent Pr(R, r. O2 o a, a,U, = u) and Pr(U
u, O = A: = a, U, = u) and Pr((U++1 u. A = d' O, = A a, U, = u) by
Pr(Rt r, A,A,- = a, U, u) p( p PP o U² = 4)
Pr(U++1 = u, O, A, a, U. u) = (tt.u)
p(0)
p Pr((O, =OU; = 4.)
0a
Pr((U++1 = u, A41 = =a,00, = A| = o, U. = u) ((..)
p(() | - =U = u.
o,'' a
respectively. We first represent E" R1 using the observed data. Notice that
=d, = d'uu== = } Pr(Ai = ='
E" R1
.1
Σ nnaa a,a)r P =r, o = =
Pr(Ai = =d'Uu =u)
Eula o''')" Tp (P()) = o = u)
Pr(Ai = -'UU- =))
06
0,,0
Σ
(a 0, p(..) (( Pr = o, A1 = =d)
0,a.a
25

---

Under review as a conference paper at ICLR 2023
Next, consider E" Rg. According to the Markov property, R2 and O2 are conditionally independent of (A1, Up. O1) given (A1, U1). As such, we have that
E" Rg
Σ (1(a1lo1,14)
01,0%
Σ
= Σ (az 02, P =2 02, = =u)
=
$2,05,02
Pr(U2 = u, A2 = 02
an, -,
= u)} Pr(Ui = u. = dj).
Σ (a1loo d() Σ
Σ
022 0f,
p(2.r) - = o|0 = u)
pll.y or.aaa
02,03 #2
01
02
02
P = o = u) Pr(U1 u, A1 = =
Σ (1(a9lo1,55) d())
Σ
12(02/02, d1, d2)r
(!!2) (1.0)
02,00 oo 01.02.00
42,00,00
[P - 0, -1=)
where ((t.)) 11
-0, a, 0.-1 = 0). Follow the similar argument, one can derive the identification formula for , T.
= Pr((O++1 o, =
0, -
H PROOF IN SECTION 5
Proof of Lemma 5.7
V(v") ) - V(i*)
E
E
(WW,
-E
Σ 8, S,2,
aEA
LaEA
}
<R
E
S(W,S, 8, (1 8 - R
((W,S,a)u' | |,
LREA
LREA
E Σ (W,S,a)) S, |S,2, A 1
+ E
Σ
((W S,2,A) 8,2, A
LaEA
(26)
225n +
(W S,Z,A) Σ
@(W, ((W,S,))v'a (,),,,)))"(/ss,,A)
(27)
nEAA
REA
+ E
Σ ((W,S,))*' S,2,4) Σ (W |5,2,))
LaEA
aEA
=25, + E (q(W.S, - @(W, S,A)) ΣGEA Tbla
U, U,S) Z,S,a)
(28)
(A'Al U,S)
ΣAEA Ta(a U, U)S) (A'' S,
+ E (,(W,,,4) @W, S, A'))
2 PmaxCa)s
(AlA' | U,
where equation 26 is due to the optimality of q and equation 27 is due to the definition Sn.
Proof of Theorem 5.7
The bound Theorem 5.] can derived by combining the results of Theorem
1.2 Theorem 1.4 and Lemma 1.2
26

---

Under review as a conference paper at ICLR 2023
In the following, derive the regret bound stated in Section 5.2 following regret decomposition lemma. Define function class Q over W x S such that Q == (a(::;a) : Q a E AA).
Before that, present the
Lemma H.1. Suppose St. E Q C x S x A and take the policy "y = { as the one that is greedy with respect to (W, S, a) St, Zz, Ar]. Take 9e(S, Z,, A.; == Elū St)
St, Z,, As] and (e,,, Ze, A Blj(W,, St) St,, Z,, As] for q E Q Define the projection emoor
E,, = sup
TE
and
R.
J&, Ab)
Rs >
S41 Zet1, Act1)
| 2r As
12
Define
Pr.max sup Pi (S₁ = Zi 2, a)
$,5,0 Pł (S: = S, Zi =, a)
and
P Pmax,I = sup w/ (St = Zz = z, A. = =a,
8,2,a
where
Exea(hueu Tola U, = u, St)p?" (u (.)dd) ((a St Zz, (S Zt) Su To
(S,, Z,, At)
U, u, S.)PE (u St, Zdd
(St, 7,) (29)
Then under Assumption 3 8 and 10 together with Assumption 6 obtain the following regret bound
T
- "(v")~((ug) <
Σ 2pt Sax
+
T
[Prmmax) + (T
Proof of Lemma H.1
We start from the decomposition
V(v") - -V(ug)
<V(u") - E
Σ
(W Si, Si, 21,
LAEA
| f(Wi,S St, 21) - E 18 Σ S(W,, S,, 21, |S,, 2n 15.
+ E
S( Ai) Z1, }
+ E
-E Σ
SAWW SI, Ai.
A
LaeA
+E
fiW Sya)yy S1. 2,.2, A1) - -V(8")
LaEA
<281,n V(v") EE
Σ S(W., |S, Z1, A1)
+E Σ
S(Wr S1, S,, A1)
-(vy))
LacA
(30)
27

---

Under review as a conference paper at ICLR 2023
First, we can show that for any policy Q.
E
Si Si, A1)
V(v)
aeA
Σ
Si St, (1))) {- E" Σ Rt
10
aEAA
T
Re + (W S4-1. Z-11 Abml)}
E"
S,, St, Zr, A1)
- -K"
1=1
A
aEA
(31)
At time I, because of the optimality of Uftt, we have
É
Σ
St | 2, A.) St, Zz, A SE
Σ
St, (.), St. Ze, A1 A1J.
AEA
nEA
Then
E
J(,W,, S, A:) SS, Z2, As
E
J&WW,, L,, S,,))aaa S,, Z, Ar) Se Zz, Av
<B
Σ S.,W,,..a) S, Zz At) 1S, Lz, As
-E
S.. Sr, Ar) | St, Ze, At
aEA
LEE
+ É
Σ
f((W,, Sr, Su,a)ssa(a St, 2, Ai) S Ze, A
- E
fiW,, a), S₁ Zg, | Se Zz, A A...
aEEAA
(32)
and
E
Sa),, St, At) Σ
Si,,,, a)ug,(a St, Ze, Anl
aEA
aed
St, St, 2z, Ar) | St, Zz, Ar 12)
<BI/2
S,, St, Ze, Ar) - Σ
< 2h
aEA
aEA
(33)
The last inequality is due to the decomposition equation 32 and the definition of &t,..
Note that
E
S,, S,, Z,, SS, Z,, A - E" Σ
fe(W,, S.. St, Zi,
Se, Ze, A A0}
AEA
LaEA
E=
E"a
St, S, A.) Vy St, Z,, A.)) U,, Zt, 4
|S,, S5, A
LaEA
=B"
E
f(W,, Se, a) (v St, 7, A,) vz,((a| St, 7,, A.)) U2, St. Z,, A,
|s,, 7r Ar
E
pkd (U, Ss, Z, An)
E
Σ S.W,,, a) (1 Z. A.) - v1, S,, Z, A.)
Ug, Sz. Z Zr Ar
| Ze. Av
PU,
Se A,, Ar)
LaEd
Due to Assumption
6 we have pi (Uz S = -,, (U, S.) and
18-(2, (Z,, A, Se)E (U, S))
pt (U, S1, At)
SNEE P% (Z:: A, U, u, S.)pk' (U, S,)du
pr (Z,, At U., S:)pi T6 (U, S.)
"hee Pi T (Zz, A U¹ u, St)pp T) (U,- St)du = p. (U, S., Ze. A.).
28

---

Under review as a conference paper at ICLR 2023
Therefore,
E
E
ft, S, At) | |S,, Zz, As
Se Zc, St. Ze. A
aEA
aEA
St Sz S,, Ab) Su Ze, A }
=E"
E
fe, S.. S, (,),, I,, - EE
Σ
nEA
DEA
pi (St, Ze, A1)
E
Σ aaA
fol,, Sr (a/ St Zz, At) Vg,s(a) St Ze, At)) St. Zz. A
Pi (St, Zz, As)
Sttm.
(34)
The last inequality is due to equation 33 and the definition Pmax, Now let's go back to equation 30, we have
E Σ (1, S1, Z1, Ai)) - V(Uget)
LaEA
Se+1, 7+1, Arni
-
Σ
(W, Se, Zr, Ai)
-R
Re+ + E
aaE
aEA
because of equation and
E
((W,,SS, St, A1)
V(r*)
LaEA
=
S(, St, S, Ao)
- EE
R₁ + Σ Su a)// S Ze+1 Acti))
t=1
LaEA
aEAA
T
E"
Σ S,, S₁, Zc,
- -E
R₁ + Σ
(W41 a) S4+1 Ze+1, Alti)
AEA
aEA
because of equation
Then
V(o*) - V(VF)
<251.n + +E! Σ
Σ
f(W,,
St, S,,,,, a)u St, Ze, Ai)
Lad
Si+1, 1,41,,444 St, Zr Au }
Eyr
Rs + Σ
aEA
Σ (1, Se, Ze,
aEEA
}
T
+
R₁ + Σ
(W S41 Z441, A441)
St, Ze, A }
Σ
Et
aEA
1=2
We know that for E (0",us),
E"
R₂ +
Σ
S411, Z41, A41) | Uz, St, Ze, A
aEA
Uz St, 2., A, = a a
=
Σ E
Re +
Σ
De) S411 2 A4t1)
vi(al St, Ze, Ac)
LEEA
a'EA
29

---

Under review as a conference paper at ICLR 2023
Take
(St, Ze: Ar) = EacaWhwer Tala U, - ( St, Z.)du)u(A,
St, Zz,a) pf Z.) Pi (St, Zr)
Su (Ar Ue u, St)pi (u St, Zr)
Then at any t.
Σ
S., St, Zz, Ad)
LaEA
S Z441, A441) St, Ze, An) )n)
}
-E"
Rs
Σ
EEA
=
Vy,ela Se, At)
aEA
Re + Σ Soi(We S441, St:1,d")ffstaldd St-1, S1-1, 2et1, dwr)) (c11) 2,, =
E
fi(W,, Ai)
a'EA
=R"
Σ
MFala St,
aEd
-(e+ B&+ (een Se-1, Zen1, Ausi) | 2z A:
E
Sc, Ar)
E
wh' (St, Ze, Ar)
Si: R Σ
(') S441, Ze41, Act1)
a'EA
The second equality is due to that PU, St, Ze, A, = =p: (Ue Sr. Ze. A. a).
Σ
feW,, Sz, a), S₁, Zz, At)
Rr. + Σ Sup. Si+1. Ze+1, Act1))
-
LEEA
aEA
T
(E (
(S L, A:) (FWWW,
1/2
)
})
Rí Σ
Se+1, Ze1,, Acti)
St Zz, A Ar
a'EA
PP" "y
)?
Similarly, we have
Σ
Rr + (We( S441, Zeti, Aeti)
R
JeWW,, Sr, Sr, Zz, At)
LaEA
aEd
T
(piaxx ) (2
Therefore, overall have
V(v*) -V(1))
Σ
2p 2pt.
T
(p 2
30

---

Under review as a conference paper at ICLR 2023
Proof of Lemma 5.2
Proof of Lemma 5.2 is direct adaption of Lemma H.1
Proof of Theorem 5.2
The result is concluded by directly combining Theorems
1.3 and Lemma
I MIN-MAX CONDITIONAL MOMENT ESTIMATION AND PROJECTION ESTIMATION
LI1 MIN-MAX CONDITIONAL MOMENT ESTIMATION
We take the min-max estimation procedure to solve the estimation equation equation 10 More specif-
ically, we follow the construction in Dikkala et al. (2020) and propose the following estimators for Q-bridge functions. For the following discussion, without loss of generality, we assume max [Re] S 1 for .,...,7 T, and function spaces Q(", g() H²() below are classes of bounded functions whose image is subset of [-1,1] 1J. Take ûT+11 = 0. For 1. = .,
U Φ (T - + 1) arg min sup (g V1+1,9) - A (1011300 + A2 (1912... + Apllallion (35)
geQu geg(t)
where || 11a, is the empirical norm, U, and μ are positive tuning parameters, and
S(en R1, + V (W,++., S4,411 Z,, Awtt1) g Slenes Are)
1n(g, V(+1.9) n2
T-t+1
Ve41 (W Zi,t1 A1.41)
Σ (W Saat1 1) St,41 Zes41, A1,41). aeA
(36)
In the following, utilize uniform error bound to study Et,.- Define the operator T, = T
where [Thh] (S,, Zz A,) B[h( R4, W,+1, S,+1, Z441, A+t1) St Z, Ag] for h E 2 W x S x 2 x A} and [Tg (s., Ze A,) Blg A.) St, 7t, A,] for h E C2 x S x A}. And take [v. (W, S, Z, A₂) EmEA ((W, S, a) S,,, Ze A,). For a function space F, we
define aF = {af : f E F} and FB f |11 < B}.
Assumption 15. The following conditions hold for t I.
(a) For any and q Q19, (v.g) E H(t) For any h E H(++1, Ti(h Re) Q(9.
(b) For any q E (T- ()+++ and any V, we have | (utivgg)
||
$
q
Qw
T- ga+"""
(c) For any E (! and v E V, we have (1 9) 11 S Coll411310 for some constant C. > 0.
(d) There exists > such that l|g -Tegele S Dt,ns where g" E arg min
l1g -
geg(t)
2 e(t)
Tigilla for all de ((t)
Take 2 2 and G00 as balls in ((1), H()) and g(t) respectively for some fixed constants
B, D,U such that functions in offi H and Git are uniformly bounded by Consider the following two spaces:
( =(wi, St, 2t, az, 8141, 2 01+1) + rlgh (wr, ar) (w 8441, #t-1, o4 (141))9((2,......00) 8t, az)
h h .9 E (!t) ( E 10.
(++1)
E()) (we, 2t, 0r) + r(g qा st,
St, az) )g (2,,))
(2,,
9 E Qit), .9 th E 0 h Hot11) rE j0. 11.
31

---

Under review as a conference paper at ICLR 2023
where 9% Q is the solution to St, A.) - h(W St41, Z+11, Ast1) Sc. A.] 0
and g arg min
llg (g 97,))l for given 0.
seg 6a
We use the Rademacher complexity to characterize the complexity of function class. For generic real-valued function space F C R', the local Rademacher complexity with radius >> 0 is defined
as
Σ (x. i=1
(x,
sup fEF,1IfilaS"
where {X:)_=1 are i.i.d. copies of X and {4)]= are i.i.d. Rademacher random variables.
Suppose F is star-shape and || for f E.F. The critical radius of the local Rademacher complexity R., (F,, r), denoted by r", the smallest value satisfying r > R, (F,r).
Theorem L.I Suppose g(t), = 1,....? T are symmetric and start-convex set of test functions and (Rr))ll S Mq. Under Assumption 15 take A År, + co / log(c:T/8)/nn for some
universal constants co, Ci 0, where A is the maximum of critical radius of ( 2 and
E(") Assume that Otn in Assumption 15 d) S A. Then (Rg + (T+ - ((+11) with
D CT M)M
If we further assume tuning parameters satisfy UA x (A)² and μ 2 0 + U/B), then the following equality holds uniformly for all I..... T with probability 1 1-
|T + 1) $ (T + 2).
where d the solution of equation 35 and
Se, S Mo(T -t 1)?(, + ( Vlog(c11/0)/m),
where
(eH1(We 241,, Ast1) St. Zo A Ar } (37)
G.m
E (WW
St,
R₁ + Σ
aEA
with Ve+1 defined in equation
Proof of Theorem I.1 Proof of Theorem I1 is direct adaption of Theorem 6.2 and Lemma D.2 in
Miao et al. (2022).
Remark 1. Under the setting of contextual bandits, the Q function estimation can be considered as special case of equation 35 by setting / T.. Then the result of bounding Sn can be adopted from Theorem accordingly. And we have the following theorem.
Theorem I.2. Suppose there exists 9" E G that satisfy the E[g" - R S, Z, 0. The functions in G and Q are uniformly bounded by 1. |R] < 1. Take A = Ån + co / log(c1/8)/n with some positive universal constants Co and C1, and A, the maximum of critical radius of Gao and
E (w, 2, a) rlq 9- (w t²
42 (2, (2, - q" E Qn. 10.11.
where g.²²B arg migmineg,2p 1|g - E(q q" 1S, 2, A))22. In addition, suppose that for any
q E Q 1g 12 Tilā-Eqq-i E(q-q" 5, Z, A))l2 S Tm < A. By taking the tuning parameters À = A A/U and p 2 L (BA) with probability at least 1 8, we have
Ga S Gnán Vlog(c1/0)/n.
I.2 PROJECTION ESTIMATION
In this section, discuss how to perform the projection step (W,, St, aS. =s 2, A a!) in Algorithm 2 Take (()) space defined over W such that Q(t) (a(s)a)) :
32

---

Under review as a conference paper at ICLR 2023
Q A}. estimate g" by
Take g7 (,,2, (l
St = A, a] for q Q We
1
G.(.. == arg min
Σ
( Ze, A,,) "(W,,, Sr.)1 + 9 gi::
g [=1
and and Elq S,,a) a) St = s, Z 2, At d') (T ++
1)). (38)
Take B and G as balls in Q and ((+) respectively for some fixed constants B and M such that functions in th and 9/ are uniformly bounded by 1.
Consider the following space:
(4) = { (we, St, Zz, ax) + [g(s), 21, at) - ((w,, s:)]² - [g" (s), 24, a); ((w,, 8,)]3
9.9º E g q E BB
Theorem I.3. Suppose for any 9 Q(1) and A. llall a I C. 1gl: for any Ø g'(s', ()) E g()) and l1g" 9 I Cgllāll Bin Take Kie, Re,n + co (ov/oo(cTT/8)) for
some universal positive constants co and c,, where x.! is the critical radius function space (1),
we further assume the tuning parameter j in equation 38 satisfying p Z (N then with probability at least 1 - 6, we have
Kt, 1+ 11 ( -1 1)13 for any 1 1,, ... T, Er, (T-
Vulle /(T / 1+ 1))l2
S -T- 1) v /Maki...
Remark 2. Under the setting of contextual bandits, the estimation for the projection (equation 17 can be considered as a special case of equation by setting = T. Then the corresponding result for bounding En can be obtained by taking t = T. - = (g(. ",lss,,a) a) : E 9, E A} in Theorem 1.3 And we obtain
Theorem I.4. Suppose for any q E Q and E A. |la(; a))l S Collal1:: for any ğ E Ô &. Take N. = R. + / (log(c//)/// for some universal positive constants co and ct, where R. is the critical radius of function space
ge(s ())))))) E G and (. 1 I Cyllāl?
r = { (wr, 8, 2, a) + [g(s, 2, - 7(w, })}² L6" (s, z, 2, ②) - 7(w, s)}² g.9" E GM,4 E 2n}
If we further assume the tuning parameter y in equation 17 satisfying p 2 (Nm)) )², then with probability least 1 - 5, we have
En S
Kin 1 10 + / $ Knn
Proof of Theorem 1.3 First, we note that for any g g(),
E [S Z,, A,)
Z, A;;) Z4, ((W,, S.)]
=E Kg(S,, Z, A) - g"(S,, A,; (o(S,, A,) Z,, Ar: q) - W.),
=E Kg(S Z, Ar)
Z,, (g(S,
(S, Z, An:)) 29" (Sc, Ac; 27( S:)
= [oo(S, Z,, (S,, Z,, Ac;)? 7)
(39)
The last equality is due to the fact that (S,,,, Z., As)[g (S., Zi, Ari ((), = 0 for any
g E g(), From the basic inequality, we have
n
1 n
( Z,,, Ar.) Sw.))
Σ
Ig Zo,t, Ar.i L.,,,, St.))² 1al19" 11 =
n
(40)
33

---

Under review as a conference paper at ICLR 2023
Next, we will establish the different between
[ Ze; Ad (.W..)))
-B (S Z, A&g) ((W,,,
and
L Zi,,, A(.)) ((W,,,,S.))
(S L,,,
A), (..
to study the bound for R [o(St, A,, (Se, Ze. Ar: 11:
To begin with, for any 9.9" E g( and g E ②
Var [9(S Z, A.) ((,, S.)? [g" (St. Ze, Ac: g(W,, S
<E (L0(S) Zz A1) @(W, 8,)1 - -gg 2r Ari G(W,, (WW, }
<1GE (g(S,, Zz, As) 90 (S,, 2, Ar: q)²
=16E {L Z.) g(W, S,]] - (S, Zz, A): - @(W. 5.)1)
where the second inequality is due the uniform boundness of g and q, and the last equality is from equation 39
Then we apply Corollary of Theorem 3.3 Bartlett et al. (2055) to the function class rO) For any function f f (+), || 1, and Var S 16Ef. Take the functional T in Theorem 3.3 of Bartlett et al. (2005) as T(f) = Ef2 and define r" as the fixed point of sub-root function to such
that for any r".
(r) N 16ER, (T(), T()) r)).
Then with probability at least 1- 5, the following inequality holds for any f E (())
BS S 2 Σ S(W., St,,, Zia, Asd) + log(1/0)
If we take Re, rv for some universal constant and the sub-root function v as the identity function. Then Kin is the critical radius of R., (T))).
Therefore, for any g g00 q (tt) B
we have
E
(g(S,, Z,, As) - (St. Z,, Ar: 91}
(41)
(S (,,, Ar,) "(W,,, 3 n
1
1 (Strr Zi,,, Ar,ei)) (.Wa,sS.e)) + k2,n +
log( (o/(
"
n
(42)
Therefore, for any g E g(t), q E Q if 11l1|3.0 - M and Ilgl I B, then equation 41 is still valid. Otherwise, take 2 = /m min / B, V + lllllg0o / //M, we can verify that
|1g/>11gu> < M
ll//=1/00 S B
llg 11/=)l))///)) < C₂ ll//=|13.0 I M.
34

---

Under review as a conference paper at ICLR 2023
Then
B
[g(S), Z2, At)/z - (S,, Ze. Ar: Q)/z}²
@(We.. S,,)/2/² +R log(1/6)
(S(, (1,)/2 @( St,)/2/²
Σ (5 Ar,19/22
n
E
(g(S Ze As) (S Zr, Ac: 91}
(S Zi,e, Ai,)) 7( Wi,,, Sr.))²
9 (Si, Zi,r, Arti S..))
i=1
+ max {1. |19| M
T Q10
log(1/0)
min B, M/CCl//l
hold with probability at least 1 - 8.
Then combine with the basic inequality equation 40 with probability least we have
r" log(1/6) n
(l, 7,, A.) - 9 (St, Zr A:: Ar: S max
1,
+ ~lllg 11:00 =1lbllg
M
min miinBBul MBCM/C2)
}
I
#1l9"" 11:0. log(1 log(1/5)
max
1,
min BB M/C/)
n
The last inequality is from the condition of tuning parameter jr.
1.3 BOUND THE CRITICAL RADIUS
In this section, we characterize the bound of critical radius mentioned above. Lemma L.I. Suppose ((), H((+1 and Q(9) are VC-subgraph classed with VC dimensions V(g()).
(H(()) and V(g(t)) respectively, then we have
Å 2 (T - 11+112 max (V(G()), V(H(+1)), ((((++))))(((1)
(43)
n
max (V(g()), v(Q"))
(44)
Proof. Note that for any / E H(t+1), we have | MeLD S C. t+ 1) MQ by Theorem I.1 And
equation 43 13 is derived directly from Section D.3.1 in Miao al. (0022) As for equation 44 note that
(t) {wir St, Zz. ar) + [g(st, Zes (e) - g" (Be, zt, az ()][g(s Ze, ax) + g" (St, Zt, 0z; ②) 277 st)]
g.g" g00 ((0)
By the similar argument in bounding log N. (t, (21)) in Section D.4.2 in Miao et al. (022)), we have log N, (1, r()) S log N, (1, ( log N, (1, ((0) log Nr ( log (t. o!!)
where (e, G) denotes the smallest empirical e-covering of G. And the bound in equation 44 is obtained by bounding the local Rademacher complexity by entropy integral (See Section D.3.I in Miao et al. (2022)
Similar results apply to Å, and Hh and get
35

---

Under review as a conference paper at ICLR 2023
Lemma I.2. Suppose 9 and Q are VC-subgraph classed with VC dimensions V(G) and V(G) respectively, then we have
An Rn max (V(G),
(45)
7
Lemma I.3. Suppose g( Q(() and H((+1) are RKHSs endowed with reproducing kernel Kg. Ko and Kg with decreasing sorted eigenvalues {>y(Ke))s=, (Ay(Ke))ī and (>((K=)) respectively.
Then A,, is upper bounded by satisfies
min (K()))))(((o)))33 8
1,=1
TT (+-++1)
min ([v()Kg)) ((42))) <
π
1-j=1
Then Re is upper bounded by 8 satisfies
TT
1++1
min ( (KK 88.
The proof follows the similar argument in the proof of Lemma D.7 in Miao et al. (2022). (See Section D.4.3 in Miao et al. (2022).)
Proof.
With different decay rates of eigenvalues, by directly applying Lemma L.3 we obtain the following corollary.
Corollary L.. With the same conditions in Lemma L.3 if (Ke) x 20-n0 (y(Kg) xc j 2ag Ay(Kz) x j j--2nn where ogg, 0zH, 0Q > 1/2, then we have
den I VIT - t 1)n //al/////////..//// log n,
Ren S n 2tmax (1aa: log
Similar results apply to Å, and Ke.
Corollary I.2. Suppose 9, Q are RKHSs endowed with reproducing kernel Kg, Ko and Kg with decreasing sorted eigenvalues ()y(Kg) (Xy (Ke) respectively.
Then if (K)) xj 200, (Kg) x 2ng, we have
Ån Ri S 11m3s(1) log n.
36


Reviews:
[{"review_id": "hC6tQXOZu0", "reviewer": "Reviewer_SFSz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "This paper analyzes offline policy learning in a confounded setting for contextual bandits and sequential decision-making. The paper introduces the notion of super policy learning in the setup where expert-recommended actions are available at each step in addition to the past historical data. Under this setup, the author(s) propose two algorithms for the contextual bandit and sequential decision-making (RL) settings and derive corresponding regret bounds.\n", "summary_of_the_review": "The paper tackles the important problem of finding an optimal policy in confounded offline reinforcement learning. The proposed practical algorithms have the potential to be implemented for real-world tasks. However, the justification of the assumptions on the real-world task is missing. Adding such empirical evaluation would eventually improve the justification of the paper's claims.\n", "strength_and_weaknesses": "Strength:\n\nImportant problem finding an optimal policy in confounded offline reinforcement learning.\nOverall well-written, and the assumptions are stated in the context of the theorem.\nThe practical derivation of the proposed algorithms helps leverage them in a real-world task.\n\nWeakness:\n\nReal-world evaluation of the proposed practical algorithms is missing.\nWhile assumptions are stated, it is unclear if all those are held in a real-world setup.\nMissing empirical evaluation and discussion.\n\n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EL4o2-CnYn", "reviewer": "Reviewer_ye4h", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper considers the problem of reinforcement learning in the presence of unmeasured confounders. In particular, the authors consider a setting where the data is collected according to a behavioral policy $\\pi^b: S \\times U \\rightarrow \\Delta(A)$ but the variables in $U$ are unobserved. The goal is to learn a \"super\" policy which might be history dependent and has return higher than the optimal policy that uses only the observed states in S.\n\nIn order to solve the super policy learning problem, the authors use techniques from proximal causal learning. In particular, they assume that there are proxies for both actions and rewards at each time step. If the proxies satisfy certain conditional independence assumption the expected return from a super policy can be expressed through a set of $Q$-bridge functions. These $Q$-bridge functions only depend on observable variables (states in S, and proxies W, Z) and they are estimated as the solution of a set of linear integral equations.\n\nThe authors finally provide sample complexity guarantees for learning optimal policies under confounded contextual bandits and confounded RL setting, but with memoryless unmeasured confounding. The bounds are derived assuming bounded complexity for the class of $Q$-bridge functions and their projections.", "summary_of_the_review": "I am leaning towards rejecting the paper mainly because the presentation of the paper is not clear, and the author makes many assumptions without giving proper example. The methods are also not validated on any real-world datasets, and not clear how they compare with prior methods.", "strength_and_weaknesses": "Strengths:\n- I think the application of proximal causal learning in confounded RL setting is quite interesting. \n- As far as I can tell, the identification results look complete if one assumes the existence of proxy variables with desired properties.\n\nWeaknesses:\n- The paper is quite hard to follow at times. For example, the authors do not motivate the existence of proxy variables with desired properties. There is also no real-world example regarding the setting considered in section 4 (confounded RL with proxy variables for rewards and actions).\n- Perhaps the major drawback of the paper is that the proposed method is not validated on any real-world dataset. So it is hard to tell where such methods can be applied.\n- The final section on finite sample guarantees requires many assumptions. For example, it requires a bound on $p_\\max$ which is completely a property of the behavioral policy. Second, for RL setting it requires memoryless confounding. I am not sure if confounding is memoryless one still requires such complicated method for estimation. Wouldn't it be possible to just perform posterior inference on hidden variables from the observation? \n- The authors also do not discuss how to solve the sequence of linear integral equation. This problem should be hard in general and it should have been discussed. Moreover, for finite sample guarantees, one needs to solve this set of equations from finite samples and needs to argue about estimation error. However, as far as I can tell, no such error bound (in terms of samples n) was provided.\n\n\n\nQuestions for the authors:\n1. Why do you need two different types of proxy variables? Can you obtain similar results if there is a single proxy variable depending on the unobserved hidden state? \n2. I am not sure if the assumptions of multiple proxy variables and bridge functions with appropriate conditions are realistic. Can the authors provide some real-world examples where such multiple proxies are available and bridge functions satisfy the desired properties. I understand that it might not be feasible to verify some of the properties in practice, but does there exist any real-world datasets which suggest existence of such $Q$-bridge functions at every time-step?\n3. Why does the finite sample guarantee depend on the constant $p_\\max$? In general, one should expect a constant related to the overlap between the behavioral policy $\\pi^b$ and optimal policy to show up in the bound but the constant $p_\\max$ as well as $p^\\omega_{t,\\max}$ just depend on behavioral policy and can be arbitrarily large.\n4. The role of the class $\\mathcal{G}$ is not clear in theorem 5.1. Since this is just obtained from projecting the class of $q$-functions, why isn't bounding the complexity of bridge functions sufficient? ", "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": "1k_Nax5Oi5s", "reviewer": "Reviewer_FcTZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper considers offline reinforcement learning in the presence of unobserved confounding. There are two observations. First, including the \"expert recommended\" action (from the behavioral policy) as part of the state is helpful, because this action was informed by the unobserved confounder. Second, if there are proxies for the unobserved confounder available, these can be leveraged to learn the optimal policy under the (better) expert-recommendations available setting. This later result is a direct application of recent proxy identification methods in causal inference.\n\n------------\n\nI read the rebuttal comments and the revised paper. I think the point about past/future state serving as proxies is a good one (though I haven't given much thought to its correctness). The authors have also added some experimental demonstration. Unfortunately, these are substantial revisions and I don't have the capacity to do more than a cursory evaluation of them.  \n\nOverall, I remain weakly positive on this paper. It's not earth shattering, but it seems to be a solid execution of a reasonably interesting idea.  I've updated my score to an 8, but with the intention that this should be parsed literally (\"I think it's a good paper worth accepting\") and not as a very strong endorsement. \n\n(FWIW though, I find the brain stimulation example pretty unconvincing---if patient actions are available at runtime, then we'd presumably just ignore whatever the learned policy is and defer to the patient)\n\n-----------\nA second update:\n\nFollowing the reviewer discussion, I'm downgrading my score to a weak reject. The crux of this is:\n1. we all agree that proxy identification results from causal inference translate to results for policy learning for unobserved confounding. This paper seems to do the translation correctly, and I'm willing to accept that it's likely technically correct.*\n2. however, a main claim of the paper is that expert recommended actions can serve / are especially good choices for the required proxies. None of us were able to articulate clearly how this part of the argument goes. (AFAICT, the real world healthcare examples don't use expert recommendations in this role)\n3. thus, it seems that there's at least a clarity problem, and potentially a technical correctness problem. Based on the discussion, this is severe enough that the paper needs a major revision. If no reviewer is able to explain the gist of the main idea, then the paper is not communicating its development clearly enough.\n\n*Although, here, I wonder if the presentation could be improved substantially simply by taking the building block as the identification result rather than the tool used for identification. That is, explain directly how to translate from such-and-such is causally identified, so the policy learning can now be achieved as such-and-such. The technical details of how proxy identification results work don't seem obviously different than how it works for identification, but they're involved enough to be distracting\n\n", "summary_of_the_review": "This paper is clear and (apparently) correct. While I am not fully convinced of its importance, I think it's a nice demo of the use of proxy methods in reinforcement learning, and may have some real-world applicability. ", "strength_and_weaknesses": "Strengths: this paper has a clear problem statement and exposition. I have no checked the proofs in detail, but they seem to be correct. There may be situations where the proposed scheme is useful. \n\nWeaknesses: the motivation is not totally clear to me. Particularly, the proxies for the unobserved confounder are introduced as an assumption to get around the non-identifiability of the target, expert-recommendation enhanced, policy. How realistic is this assumption? Are there particular motivating problems in mind? It would also be nice to have some experiments showing the scope of the benefits.", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject