Counterfactually Fair Reinforcement Learning via Sequential Data Preprocessing Jitao Wang, Chengchun Shi, John D. Piette, Joshua R. Loftus, Donglin Zeng, Zhenke Wu Abstract When applied in healthcare, reinforcement learning (RL) seeks to dynamically match the right interventions to subjects to maximize population benefit. However, the learned policy may disproportionately allocate efficacious actions to one subpopulation, creating or exacerbating disparities in other socioeconomically-disadvantaged subgroups. These biases tend to occur in multi-stage decision making and can be self-perpetuating, which if unaccounted for could cause serious unintended consequences that limit access to care or treatment benefit. Counterfactual fairness (CF) offers a promising statistical tool grounded in causal inference to formulate and study fairness. In this paper, we propose a general framework for fair sequential decision making. We theoretically characterize the optimal CF policy and prove its stationarity, which greatly simplifies the search for optimal CF policies by leveraging existing RL algorithms. The theory also motivates a sequential data preprocessing algorithm to achieve CF decision making under an additive noise assumption. We prove and then validate our policy learning approach in controlling unfairness and attaining optimal value through simulations. Analysis of a digital health dataset designed to reduce opioid misuse shows that our proposal greatly enhances fair access to counseling. Keywords: Counterfactual Fairness, Digital Health, Opioid Misuse, Reinforcement Learning, Sequential Data Preprocessing. 1 Introduction With the widespread integration of machine learning (ML)-based decision making systems in various sectors of the economy such as banking, education, financial analysis and healthcare, there is a growing focus on the ethical and societal implications of its deployment ( Howard & Borenstein, 2018 ; Chouldechova et al., 2018 ; Mehrabi et al., 2021 ) . The susceptibility of ML algorithms to bias is raising concerns about the potential for discrimination, particularly as it affects already socioeconomically-disadvantaged subgroups (e.g., racial/ethnic minorities or women). For example, in healthcare, automated decision making systems may unfairly allocate treatment resources to specific subpopulations to maximize population-wise long-term benefits, while neglecting the needs of patients already at risk for limited access or poor outcomes. To redress these problems, researchers have proposed the imposition of fairness constraints on decision-making in order to achieve various fairness-related objectives ( Hardt et al., 2016 ; Chouldechova, 2017 ; Yeom & Tschantz, 2018 ; Mehrabi et al., 2021 ; Black et al., 2022 ; Corbett-Davies et al., 2023 ) . The counterfactual fairness ( Kusner et al., 2017 , CF,) adopted in this paper requires that, all else being equal, the distribution of the decisions for an individual be the same had the individual belong to a different group defined by a sensitive attribute (e.g., gender, race). Unlike other fairness definitions, CF offers a solution based on causal reasoning, which lends itself to statistical techniques to eliminate the influence of sensitive attributes on the outcomes ( Kusner et al., 2017 ; Silva, 2024 ) . DeDeo (2014) further argued that even the most successful algorithms would fail to make fair judgments without causal reasoning. To illustrate the differences in major existing fairness concepts, consider the following simplified single-stage university admissions example ( Wang et al., 2022 ) : a university wants to develop an ML-based decision support system for undergraduate admission. The system makes admission decisions based on an applicant’s information, including entrance exam score, gender, race/ethnicity, access to prior educational opportunities, where the score may be correlated with the rest of the variables and unmeasured factors like aptitude. Below, we discuss three notions of fairness: 1. Demographic parity : If the university were to pursue “demographic parity” with respect to gender, the goal would be to ensure admission of an equal proportion of male and female applicants regardless of entrance exam scores or the student’s aptitude. It only seeks to match the proportion of admission between the groups, regardless of actual qualifications, which can be problematic if one group is genuinely different in terms of the distribution of actual qualifications. It is purely a statistical metric without considering causal mechanisms that lead to differences in the observed data. 2. Equal opportunity : If the university were to pursue “equal opportunity” ( Hardt et al., 2016 ) with respect to gender, the goal would be to ensure that truly qualified applicants would be admitted with equal probabilities (i.e., true positive rates) across groups defined by gender. Equal opportunity relies on observational measures and checks statistical parity conditional on the true qualification but does not consider why or how group differences arise, i.e., it does not directly model or reason about causal relationships. 3. Counterfactual fairness : CF with respect to gender shifts attention to individual-level and a causal interpretation of fairness. It ensures that the chance of being admitted does not change had their gender been hypothetically switched while keeping all else about the individual’s situation the same. Instead of focusing on matching group-level metrics, CF involves building or assuming a causal model that explains how sensitive attributes influence the individual’s observed features. This example highlights two key distinctions of CF compared to other fairness definitions: 1) CF focuses on individual-level fairness rather than group-level, and 2) it seeks to remove direct and indirect effects of sensitive attributes on decisions, ensuring fairness from a causal, rather than purely statistical, perspective, by considering fairness in slightly different hypothetical worlds. Significant progress has been made in achieving CF decision making in single-stage scenarios. However, focusing solely on a single static decision can lead to suboptimal outcomes if it fails to consider the dynamic nature of sequential decision-making processes ( Liu et al., 2018 ; Creager et al., 2020 ; D’Amour et al., 2020 ) . Reinforcement learning (RL) excels at sequential decision-making applications including fintech ( Malibari et al., 2023 ) , traffic light control ( Wei et al., 2018 ) , and healthcare ( Li et al., 2022 ; Buçinca et al., 2024 ) , by learning policies that maximize future rewards. Despite its success, integrating CF principles within RL remains an under-explored area ( Reuel & Ma, 2024 ) . The challenges of applying CF in RL are two-fold. First, unlike static scenarios, sensitive attributes may not only directly affect the current state, but also indirectly influence the current state through its impact on previous states and decisions. Disentangling these direct and indirect effects to ensure CF is a significant challenge. Second, most existing RL algorithms operate under a Markov decision process (MDP) model assumption, under which the optimal policy achieves desirable properties such as Markovian properties and stationarity ( Puterman, 2014 ) . These properties substantially reduce the search space and simplify the algorithm. It is unclear whether these properties still hold when incorporating CF constraints. Our work is motivated by the “PowerED” study ( Piette et al., 2023 ) . The original study was a randomized controlled trial of patients who were at risk for opioid-related harms (e.g., overdose or addiction) in which investigators evaluated an RL-supported, 12-week digital health intervention designed to prevent those negative outcomes through behavioral counseling of opioid users while conserving scarce counselor time. Specifically, the intervention arm used an RL-based automated decision making system to dynamically assign weekly personalized treatment options based on each patient’s self-reported pain score and opioid use behaviors in the prior week, with the goal of reducing self-reported opioid misuse behaviors. Treatment options included i) brief motivational interactive voice response (IVR) call (less than 5 minutes), ii) a longer recorded call (5 to 10 minutes), or iii) a live call with counselor (20 minutes). Comparison-group participants received 12 weeks of standard motivational enhancement via weekly calls with a trained counselor. In this paper, we focus on the RL-supported arm of the trial where an RL agent seeks to intelligently allocate a limited supply of counselors’ time (option iii). There are two ways unfairness could be introduced in an application like the PowerED study if fairness-unaware RL algorithms are used (as they were in this trial). First, by directly including sensitive attributes (e.g., ethnicity and gender) into the set of state variables within the RL model, the learned policy could make biased decisions for those minority groups characterized by the sensitive attributes. For example, patients with similar pain levels but different ethnicities might receive different treatment options if the agent uses ethnicity as a decision factor. Second, even when sensitive attributes are excluded from the state variables to make decisions, the effect of the sensitive attribute upon the state variables may still indirectly influence the agent’s decisions. For instance, research indicates that Hispanic Americans, despite experiencing higher pain sensitivity, often report fewer pain conditions due to cultural factors ( Hollingshead et al., 2016 ) . This under-reporting may mislead the agent to think that Hispanics are experiencing less pain compared to other subgroups and to assign fewer human counseling (option iii above; more efficacious) to Hispanic patients, creating unfairness. In this paper, we demonstrate that CF provides a promising statistical framework to study fair sequential decisions while controlling for both direct and indirect influences of the sensitive attributes. Contributions Our work makes four main contributions: (i) Motivated by a real-world digital-health application, the PowerED study, we propose a novel and generalized CF definition that is suitable for the more challenging but ubiquitous dynamic setting in which RL makes sequential decisions; (ii) We theoretically characterize the class of CF policies and prove the stationarity of the optimal CF policy which greatly simplifies the search and evaluation for optimal CF policies by leveraging existing RL algorithms. (iii) Motivated by the theory, we propose a sequential data preprocessing algorithm designed for optimal CF policy learning under an additive noise assumption. We establish theoretical guarantees that our approach asymptotically controls the level of unfairness and attaining optimal value; (iv) We demonstrate the efficacy of our proposed algorithm in controlling unfairness and attaining optimal value through numerical studies and real data analysis. Related Work on Fair ML A variety of fairness criteria in ML and their characterizations in the literature have been recently reviewed ( Kleinberg et al., 2018 ; Mehrabi et al., 2021 ; Barocas et al., 2023 ; Yang et al., 2024 ; Caton & Haas, 2024 ) . Broadly speaking, ML methods addressing fairness goals can be classified into three categories. Preprocessing approaches remove potential bias from the data before training. For example, Kusner et al. (2017) ; Nabi & Shpitser (2018) ; Chiappa & Isaac (2019) ; Salimi et al. (2019) ; Zuo et al. (2022) ; Chen et al. (2023) used the causal framework of directed acyclic graph (DAG) to remove unfairness from the training data. Others proposed to preprocess the training data using relabelling and perturbation techniques to balance between underprivileged and privileged instances ( Kamiran & Calders, 2012 ; Jiang & Nachum, 2020 ; Wang et al., 2019 ) . In-processing methods incorporate fairness metrics directly into the model’s training process, for example by regularization or constrained optimization ( Berk et al., 2017 ; Aghaei et al., 2019 ; Di Stefano et al., 2020 ; Viviano & Bradic, 2024 ) or with adversarial approaches ( Edwards & Storkey, 2015 ; Beutel et al., 2017 ; Celis & Keswani, 2019 ) . Post-processing approaches adjust the model’s predictions after training to ensure fairer outcomes for different groups ( Pleiss et al., 2017 ; Hébert-Johnson et al., 2018 ; Kim et al., 2019 ; Wang et al., 2022 ) . Several recent works have explored various approaches to achieve CF in single-stage scenarios. Chen et al. (2023) proposed an algorithm that removes sensitive information from the training data. Wang et al. (2022) developed a post-processing procedure to make unfair ML models fair. Kusner et al. (2017) and Zuo et al. (2022) considered building ML models that rely only on non-sensitive attributes. Di Stefano et al. (2020) proposed to use regularization by incorporating fairness penalty into the loss function. Paper organization The remainder of this paper is organized as follows. Section 2 reviews structural causal models, counterfactual inference, and the contextual Markov decision process (CMDP) model. In Section 3 , we extend single-stage CF to multi-stage decision making under the framework of CMDP. In Section 4 , we characterize the form of (optimal) CF policies when the counterfactuals are known. In Section 5 , we propose a sequential data preprocessing algorithm for estimating the counterfactuals. The preprocessed data serve as inputs to any offline RL algorithm for CF policy learning. We then theoretically establish value optimality and asymptotic fairness control of the learned policy in Section 5.1 , which are empirically supported by synthetic and semi-synthetic experiments in Section 6 . We apply the algorithm to a real-world interventional digital health dataset Section 7 . The paper concludes with a brief discussion on limitations and future directions. 2 Preliminaries To bring the discussion of fairness into the framework of causal inference, we first give a brief introduction to the definitions of structural causal model (SCM) and counterfactuals. Then we introduce the the framework of CMDP in which we define the CF using the language of SCM (Section 3 ). 2.1 Structural causal model and counterfactuals Following Pearl et al. (2000) , SCM provides a mathematical framework for modeling causal relationships between variables. An SCM M=(\mathcal{U},\mathcal{V},F) consists of a set of observable endogenous variables V , a set of unobserved exogenous variables U and a set of functions F . These functions assign value to each endogenous variable V given its parents pa(V)\in\mathcal{V} and unobserved direct causes U : V=f_{V}(pa(V),U) . U are required to be jointly independent. The structure of M can be depicted by a causal graph, usually in the form of directed acyclic graph (DAG), where (pa(V),U) forms the parent set of V . In the SCM framework, we define counterfactual inference. Assume Y\in V is the variable of interest. Let Z and U_{Y} be the parents of Y where Z\in V and U_{Y}\in U ; let U_{Z} be the parent of Z and U_{Z}\in U . By the definition of SCM, Y is fully determined by Z and U_{Y} through function f_{Y} , i.e., Y=f_{Y}(Z,U_{Y}) . Given a realization of U_{Y}=u_{Y} , suppose we have observed the values of Z and Y , denoted as z and y . Consider a typical counterfactual inference statement: what would be the value of Y had Z taken value z^{\prime} instead of z given we have observed z and y ? This counterfactual query can be realized through Pearl’s do-operator, do(Z=z^{\prime}) , which generates an interventional distribution by removing the edges leading into Z in the corresponding DAG and set Z to the value z^{\prime} . Following the notation in the seminal CF paper ( Kusner et al., 2017 ) , we denote it by Y^{Z\leftarrow z^{\prime}}(U_{Y}) , where “ Z\leftarrow z^{\prime} ” represents the do(Z=z^{\prime}) operation and Y^{Z\leftarrow z^{\prime}}(U_{Y}) is a deterministic function of Z and U_{Y} . Figure 1 depicts the difference between SCM and counterfactual inference. It is important to note that while U_{Y} is not directly observable, we can infer its value from the observed values z and y . This inference of U_{Y} is essential for computing counterfactuals. Figure 1: A simple example of SCM and counterfactual inference. We adhere to a general three-step procedure for counterfactual inference to compute this quantity (please refer to Pearl et al., 2016 , for more details) : 1. Abduction : update P(U_{Y}) by the observed quantities Y=y,Z=z , obtaining P(U_{Y}|Y=y,Z=z) . 2. Action : remove the structure equations for Z and replace them with the appropriate value, i.e. Z=z^{\prime} . 3. Prediction : use the modified structural model and updated P(U_{Y}|Y=y,Z=z) to compute Y^{Z\leftarrow z^{\prime}}(U_{Y}) . We will detail this inference procedure for our specific settings in Section 3.1 and 3.2 . 2.2 Contextual Markov Decision Process Contextual Markov Decision Process ( Hallak et al., 2015 , CMDP,) is an augmented MDP that incorporates additional contextual information during decision making. Definition 1 (CMDP) . Contextual Markov decision process is a tuple (\mathcal{C},\mathcal{S},\mathcal{A},\mathcal{M}(c)) where \mathcal{C} is called the context space, \mathcal{S} and \mathcal{A} are the state and action space, and \mathcal{M} is function mapping any context c\in\mathcal{C} to an MDP \mathcal{M}(c)=(P^{c},R^{c}) . Figure 2: Causal DAG of CMDP. We assume the observational data follows a CMDP where the sensitive attributes serve as the contextual information, as illustrated in Figure 2 . Consider the collected observed tuples \{(z_{i},s_{it},a_{it},r_{it}):t=1,\dots,T_{i},i=1,\dots,N\} , where N denotes the number of subjects and T_{i} denotes the length of horizons for subject i . For simplicity, we fix T_{i}=T for all i in the rest of the paper. Z_{i} denotes time-invariant sensitive attributes for subject i , which takes value from \mathcal{Z}=\{z^{(1)},\dots,z^{(K)}\} . In this paper, we consider the sensitive attributes to be categorical, which is a reasonable assumption for commonly studied attributes such as race and gender. Additionally, for ease of presentation, we focus on a single sensitive attribute in this paper, but the extension to multiple attributes is straightforward. For simplicity, we omit index i for individual. Let S_{t},A_{t},R_{t} represent the state variables, actions and received reward at time t . U^{S}_{t},U^{R}_{t} are the exogenous variables for S_{t},R_{t} . We use {\pi}=\{\pi_{t}\}_{t\geq 1} to denote a policy, which consists of a sequence of decision rules. At time t , the environment arrives at a state S_{t} and the agent takes an action A_{t} based on a behavior decision rule \pi_{t}^{(b)} which is specific to the mechanism of how the observed data at hand are collected and often differ from an alternative and potentially better decision rule \pi_{t} . The environment then transitions to a new state X_{t+1} and gives a reward R_{t} according to transition kernel P_{t}(S_{t+1},R_{t}|S_{t},A_{t},Z) . Here the transition kernel P_{t} can vary by time in general as indicated by the dependence on the index t ; \pi_{t} can generally depend on entire history H_{t}=\{Z,\bar{S}_{t},\bar{A}_{t-1},\bar{R}_{t-1}\} where the notation “ \bar{W}_{t} ” generically represents the sequence of variable W from time 1 up to and including time t . We introduce two assumptions as implied by the DAG structure in the CMDP framework and remark on their relevance to our theoretical analyses. Assumption 1 (No unmeasured confounders) . For each t1 , U_{t}^{S} and U_{t-1}^{R} are deterministic functions of H_{t} . With a slight abuse of notation, we denote by U^{S}_{t}(\cdot) and U^{R}_{t-1}(\cdot) the corresponding mapping functions, such that: U^{S}_{t}=U^{S}_{t}(H_{t}) , and U^{R}_{t-1}=U^{R}_{t-1}(H_{t}) .Furthermore, let \bar{U}_{t}(\cdot) be a vector-valued function with component functions: (U_{1}^{S}(\cdot),U_{1}^{R}(\cdot),\dots,U_{t-1}^{R}(\cdot),U_{t}^{S}(\cdot)). Following Pearl’s three-step procedure, we use A_{t}^{Z\leftarrow z^{\prime}}(\bar{U}_{t}(h_{t})) to denote the counterfactual action that would have been taken following a decision rule \pi_{t} for an individual with history h_{t} had their sensitive attribute been set to z^{\prime} . With these notation and assumptions established, we can now formally define CF for a decision rule \pi_{t} in the CMDP framework, Definition 3 (Counterfactual Fairness in CMDP) . Given an observed trajectory H_{t}=h_{t} where h_{t}=\{z,\bar{s}_{t},\bar{a}_{t-1},\bar{r}_{t-1}\} , a decision rule \pi_{t} is counterfactually fair at time t if it satisfies the following condition: \mathbb{P}^{\pi_{t}}\left(A_{t}^{Z\leftarrow z^{\prime}}(\bar{U}_{t}(h_{t}))=a\right)=\mathbb{P}^{\pi_{t}}\left(A_{t}^{Z\leftarrow z}(\bar{U}_{t}(h_{t}))=a\right),\vskip-14.22636pt (2) for any z^{\prime}\in\mathcal{Z} and a\in\mathcal{A} . Similar to Definition 2 , CF requires that \pi_{t} must assign the same action a for the same individual with history h_{t} , if in a hypothetical world their sensitive attribute Z were changed to any other valid value z^{\prime}\in\mathcal{Z},z^{\prime}\neq z , while experiencing the same action sequence \bar{a}_{t-1} . A policy {\pi}=\{\pi_{t}\}_{t\geq 1} is said to satisfy CF under CMDPs if each \pi_{t} satisfies the Definition 3 . Remark 2 . Definition 3 aligns with Pearl’s three-step counterfactual inference procedure ( Pearl et al., 2016 ) , which we can break down as follows: • Abduction step : \bar{U}_{t} is the historical values of the background variables that follow the distribution of P(\bar{U}_{t}|H_{t}=h_{t}) that update our knowledge of \bar{U}_{t} given the observed trajectories h_{t} ; • Action step : We perform do-operation: Z is set to a hypothetical value z^{\prime} ; • Prediction step : Based on our updated knowledge of \bar{U}_{t} given h_{t} , z^{\prime} and \bar{a}_{t-1} , we can predict the distribution of A_{t} following \pi_{t} , the decision rule executed by the agent. 4 Characterizing Counterfactually Fair Policies In this section, we theoretically characterize the class of CF policies under CMDPs, and show the optimal CF policy is stationary when CMDPs are stationary assuming known counterfactual states and rewards. In Section 5 , we will present identification assumptions and an algorithm for learning the counterfactual states and rewards from data. Given the observed history H_{t}=h_{t} , let \mathcal{S}_{t} denote the set of counterfactual states at all possible values of Z at time t . Similarly, let \mathcal{R}_{t} denote the set of counterfactual rewards. Formally, \mathcal{S}_{t}=\left\{S_{t}^{Z\leftarrow z^{(k)}}(\bar{U}_{t}(h_{t}))\right\}_{k=1,\dots,K} , and \mathcal{R}_{t}=\left\{R_{t}^{Z\leftarrow z^{(k)}}(\bar{U}_{t}(h_{t+1}))\right\}_{k=1,\dots,K} . In addition, let \bar{\mathcal{S}}_{t}=\{\mathcal{S}_{t^{\prime}}\}_{t^{\prime}\leq t} and \bar{\mathcal{R}}_{t}=\{\mathcal{R}_{t^{\prime}}\}_{t^{\prime}\leq t} . Theorem 1 (Counterfactual augmentation) . Given observed history H_{t}=h_{t} under CMDPs, \pi_{t} satisfies CF if it admits the following functional form that \pi_{t}\left(\bar{\mathcal{S}}_{t},\bar{\mathcal{R}}_{t-1},\bar{a}_{t-1}\right),~\textrm{for any}~t.\vskip-14.22636pt (3) In what follows, we will focus the class of CF policies that take (\bar{\mathcal{S}}_{t},\bar{\mathcal{R}}_{t-1},\bar{a}_{t-1}) as input. In DTR settings, the policy that takes observables (Z,\bar{S}_{t},\bar{R}_{t-1},\bar{A}_{t-1}) as input would achieve value optimality but violates the CF definition due to its direct use of Z . Our interested policy class of form ( 3 ) removes direct or indirect impact of Z in a causal framework, which ensures CF but potentially at the cost of reduced value due to the loss of Z ’s information. In RL, stationarity is often assumed for efficient policy learning ( Sutton & Barto, 2018 ) . Building on this, we consider stationary CMDPs, where the system dynamics remain invariant over time. A history-dependent policy {\pi} is a sequence of decision rules {\pi}=\{\pi_{t}\}_{t\geq 1} where each \pi_{t} maps (\bar{\mathcal{S}}_{t},\bar{\mathcal{R}}_{t-1},\bar{a}_{t-1}) to a probability mass function on \mathcal{A} . When there exists some function \pi^{*} such that \pi_{t}(\bar{\mathcal{S}}_{t},\bar{\mathcal{R}}_{t-1},\bar{a}_{t-1})=\pi^{*}(\mathcal{S}_{t}) for any t\geq 1 almost surely, we refer to \pi as a stationary policy. Let HCF , SCF denote the class of history-dependent and stationary CF policies, respectively. The following theorem characterizes optimal CF policies under stationary CMDPs. Theorem 2 (Optimality in stationary CMDPs) . Under a stationary CMDP, there exists some \pi^{opt}\in\text{SCF} such that J(\pi^{opt})=\sup_{\pi\in\text{HCF}}J(\pi), where J(\pi)=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t}\right] is integrated expected discounted cumulative reward with discount factor \gamma\in(0,1) . Theorem 2 implies that the optimal CF policy in a stationary CMDP can be found within the class of SCF , which is much smaller than HCF . Leveraging existing offline RL algorithms with minimal modifications, we can pool information across time to better learn a single stationary policy. Theorem 1 and 2 suggest that in stationary CMDPs, the optimal CF policy is stationary, where the decisions rely on the most recent counterfactual states at all possible values of Z . However, we can only observe the factual but not the counterfactual states, limiting direct application of these theoretical results. To bridge this gap, we propose a sequential data preprocessing algorithm (Section 5 ) that estimates these unobserved counterfactuals. This preprocessing step enables the application of existing offline RL algorithms to learn optimal CF policies using the preprocessed experience tuples. 5 Counterfactually Fair Policy Learning In this section, we focus on the problem of learning optimal CF policies acknowledging that counterfactuals are unobserved. Our proposed approach has two steps. First, we remove sensitive attribute information from the original dataset via a sequential data preprocessing procedure (Algorithm 1 ). Second, the preprocessed dataset is used as input to any existing offline RL algorithm to learn the optimal CF policy. Similar to the single-stage setting reviewed in Section 3.1 , a key ingredient in the first step is to accurately estimate the counterfactual states and rewards from the observed data at each time point, for which we introduce the following assumption: Assumption 4 (Additivity) . For all time t\geq 1 , the exogenous variables U^{S}_{t} and U^{R}_{t} are additive to S_{t} and R_{t} , respectively. Assumption 4 , which enables the estimation of exogenous variables \{U^{S}_{t}\}_{t\geq 1} and \{U^{R}_{t}\}_{t\geq 1} , allows us to identify and estimate the counterfactual states and rewards using observed data. This assumption is related to level 3 assumption in Kusner et al. (2017) ’s work, which maximizes the information the policy learner can use. Kusner et al. (2017) also introduced level 1 and 2 assumptions, which are more flexible than this additivity assumption. With all the necessary assumptions established, we now present Algorithm 1 of the proposed sequential data preprocessing procedure. We use \hat{s}_{it}(z^{\prime}) and \hat{r}_{it-1}(z^{\prime}) to represent the estimated values of S_{t}^{Z\leftarrow z^{\prime}}(\bar{U}_{t}(H_{t})) and R_{t-1}^{Z\leftarrow z^{\prime}}(\bar{U}_{t}(H_{t})) for individual i , respectively. The algorithm’s core strategy is to leverage observed data to estimate counterfactual states and rewards under the additive assumption. These estimates enable us to construct preprocessed experience tuples from the original data, which can then be used to train optimal policies that satisfy CF requirements. Notably, these preprocessed experience tuples naturally form a MDP, as shown in the proof of Theorem 2 , allowing us to apply existing RL algorithms directly. It is important to note that the rationale for preprocessing s_{it} and r_{it} differs. According to Theorem 1 , pre-processing s_{it} ensures that the learned policy achieves CF and there is no requirement on reward r_{it} . One can use preprocessed \hat{s}_{it} and observed r_{it} to learn a CF policy. However, the purpose of preprocessing r_{it} is to ensure that the learned policy maximizes the cumulative discounted reward under stationary CMDPs based on Theorem 2 . 1: Original data \mathcal{D}=\{(s_{it},z_{i},a_{it},r_{it}):i=1,\dots,N;t=1,\dots,T\} . 2: Fit the mean of transition kernel \hat{\mu}(s,a,z) by minimizing mean squared error (MSE) on \mathcal{D} . 3: Estimate \hat{\mathbb{E}}(S_{1}|Z=z) and \hat{P}(Z=z) \forall z^{\prime}\in\mathcal{Z} by the empirical means. 4: for i=1,\dots,N do 5: Calculate \hat{s}_{i1}^{z^{\prime}}=s_{i1}-\hat{\mathbb{E}}(S_{1}|Z=z)+\hat{\mathbb{E}}(S_{1}|Z=z^{\prime}),\forall z^{\prime}\in\mathcal{Z} . 6: Set \tilde{s}_{i1}=[\hat{s}_{i1}^{z^{(1)}},\dots,\hat{s}_{i1}^{z^{(K)}}]^{\top} . 7: for t=2,\dots,T do 8: [\hat{s}_{it}^{z^{\prime}},\hat{r}_{i,t-1}^{z^{\prime}}]^{\top}=[s_{it},r_{i,t-1}]^{\top}-\hat{\mu}(s_{i,t-1},a_{i,t-1},z_{i})+\hat{\mu}(\hat{s}_{i,t-1}^{z^{\prime}},a_{i,t-1},z^{\prime}),\forall z^{\prime}\in\mathcal{Z} . 9: \tilde{s}_{it}=[\hat{s}_{it}^{z^{(1)}},\dots,\hat{s}_{it}^{z^{(K)}}]^{\top} , 10: \tilde{r}_{i,t-1}=\sum_{k=1}^{K}\hat{P}(Z=z^{(k)})\hat{r}_{i,t-1}^{z^{(k)}}. 11: end for 12: end for 13: Preprocessed experience tuples \{(\tilde{s}_{it},a_{it},\tilde{r}_{it}):i=1,\dots,N;t=1,\dots,T\} . Algorithm 1 Proposed sequential data preprocessing Remark 3 . Algorithm 1 generalizes the data preprocessing algorithm in Chen et al. (2023) , which shares the idea of estimating the counterfactual states through preprocessing. Although their approach can be extended to single-stage contextual bandit settings, it falls short in multi-stage CMDP settings. The challenge is that the information of Z is embedded in the states S_{t} for every time point t\geq 1 . To infer the counterfactual state S_{t}^{Z\leftarrow z^{\prime}}(\bar{U}_{t}(H_{t})) at time t , it is necessary to first compute the value of preceding counterfactual state S_{t-1}^{Z\leftarrow z^{\prime}}(\bar{U}_{t-1}(H_{t-1})) (Line 7, Algorithm 1 ). This sequential dependency motivates the proposed sequential data preprocessing procedure, where counterfactual states are inferred from t=1 to T . 5.1 Theoretical analysis In this section, we establish the theoretical results on the regret, which measures the difference between the expected cumulative reward under the optimal policy and that under the estimated policy, and unfairness control of the optimal policy learned using Algorithm 1 and fitted Q iteration ( Riedmiller, 2005 , FQI, ) in tandem. FQI is widely used policy learning algorithm in RL, where the procedure is detailed in Algorithm 2 . Unlike traditional FQI analyses that work on observed states and rewards, our algorithm requires estimating the counterfactual states and rewards before applying FQI. Therefore, this section presents a novel FQI analysis tailored to the scenario where both states and rewards are estimated. For ease of presentation, we use \hat{s} and \hat{r} to represent estimated quantities in theoretical analysis. 1: Dataset \mathcal{D}=\{(s_{i},a_{i},r_{i},s_{i}^{\prime}):i=1,\dots,n\} , function class \mathcal{F} . 2: Initialize \hat{f}_{0}\in\mathcal{F} randomly. 3: for b=1,\dots,B do 4: Compute target y_{i}=r_{i}+\gamma\max_{a}\hat{f}_{b-1}(s_{i}^{\prime},a) . 5: Build training dataset D_{b}=\{s_{i},a_{i},y_{i}\}_{i=1,\dots,n} . 6: Solve a supervised learning problem: \hat{f}_{b}=\arg\min_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\left(f(s_{i},a_{i})-y_{i}\right)^{2}\vskip-8.5359pt 7: end for 8: Estimated optimal Q function \hat{f}_{B} . Algorithm 2 Fitted Q iteration ( Riedmiller, 2005 ) . Here we briefly introduce the assumptions used in the analysis. First, our results are based on the FQI algorithm on the hypothesis class \mathcal{F} that is linear in d -dimensional features \phi(s,a) , with bounded coefficients w\in\mathbb{R}^{d} (Assumption ). Second, we assume that \mathcal{F} is closed under the Bellman optimality operator (Assumption ), which is known as the Bellman completeness assumption ( Chen & Jiang, 2019 ) . Third, we assume sufficient feature coverage in the dataset (Assumption ). More specifically, we require that the minimum eigenvalue of \mathbb{E}_{s,a\sim\mu_{b}}[\phi(s,a)\phi(s,a)^{T}]) is greater than \lambda_{0} where \mu_{b} is the data distribution. This assumption is commonly required to guarantee the convergence of FQI estimators ( Wang et al., 2020 ; Hu et al., 2024 ) . Fourth, we assume that each feature \phi_{i}(s,a) is a L- Lipschitz continuous function for any i=1,\ldots,d and a (Assumption ). Fifth, we assume that the reward are bounded, i.e., |r|\leq R_{\max} (Assumption ). We denote n as the number of experience tuples in the dataset, i.e., n=NT . Theorem 3 (Regret Bound) . Let \epsilon=\max_{s}\|\hat{s}-s\|_{\infty}+\max_{r}|\hat{r}-r| . Suppose Assumptions - holds. With probability at least 1-n^{-\kappa}-d\exp(-n\lambda_{0}/8) the regret of the optimal policy estimated using Algorithm 1 and FQI is upper bounded by \frac{CdLR_{\max}\epsilon}{\lambda_{0}(\lambda_{0}-4dL\epsilon)(1-\gamma)^{3}}+\frac{CdR_{\max}\kappa\log(n)}{\lambda_{0}\sqrt{n}(1-\gamma)^{3}}+\frac{\gamma^{B}R_{\max}}{(1-\gamma)^{2}},\vskip-14.22636pt (4) for any \kappa>0 , some positive constant C>0 and B is the number of FQI iterations. Theorem 3 implies that the regret bound is composed of three terms: (i) The first term is proportional to \epsilon , which measures the estimation error of counterfactual states and rewards ; (ii) The second term is directly linked to the one-step FQI regression error , which approaches zero as n increases; (iii) The third term characterizes the initialization bias , which approaches zero exponentially fast with respect to the number of FQI iterations B . Meanwhile, these error terms are also dependent upon some other factors, such as the feature dimension d , the Lipschitz constant L , the reward upper bound R_{\max} , the minimum eigenvalue \lambda_{0} and the (1-\gamma)^{-1} -term which has a similar interpretation to the horizon in episodic tasks. Their dependencies align with existing findings in the literature ( Chen & Jiang, 2019 ; Hu et al., 2024 , see e.g.,) . To analyze unfairness control of the learned policy, we introduce an additional margin-type assumption, as detailed in Assumption in the supplementary materials. This assumption is often imposed in RL literature ( Qian & Murphy, 2011 ; Shi, Zhang, Lu & Song, 2022 ; Hu et al., 2024 ) . Let \xi be the FQI error bound (Equation ( ) in the supplementary materials) and \hat{\pi} denote the learned optimal policy using Algorithm 1 and 2 . Theorem 4 (Unfairness Control) . Under Assumptions - and in the supplementary materials, suppose \epsilon=\max_{s}\|\hat{s}-s\|_{\infty}+\max_{r}|\hat{r}-r| , for any \kappa>0 , with probability at least 1-n^{-\kappa}-d\exp(-n\lambda_{0}/8) , the absolute difference in action distributions for \hat{\pi} using under two counterfactual worlds ( z^{\prime} and z^{\prime\prime} ) is no more than 2^{\alpha+1}\xi^{\alpha}+2^{\alpha}(L\epsilon)^{\alpha} . Theorem 4 characterizes the difference in action distributions when the input counterfactual states are estimated under two worlds with distinct values of Z . The analysis implies that the unfairness is influenced by two terms: (i) The first term is related to the FQI estimation error. As this error goes smaller, the unfairness also decreases. (ii) The second term is related to the estimation error of counterfactual states. As this estimation error becomes smaller, the estimated counterfactual states under different z ’s will be similar, resulting in generating similar action distributions. 6 Numerical experiments In this section, we evaluate the performance of our approach using synthetic and semi-synthetic datasets that mirror the distributional characteristics of the PowerED study data. Our assessment focused on two key metrics: (1) the value attained by the learned policy, and (2) the degree of counterfactual unfairness. The latter is operationalized as a measure of how actions differ between the observed world and a hypothetical world where only the sensitive attribute is altered. Baselines Five baselines are considered: 1) Full , a standard policy that uses all variables, including the sensitive attribute and other state variables, to make decisions; 2) Unaware , a policy that uses all variables except the sensitive attribute to make decisions; and 3) Oracle , an idealized policy that used concatenations of counterfactual states where the counterfactual states and rewards are assumed known. For reference, we also include 4) Random policy that selects actions randomly and 5) Behavior policy that is used to collect data. By definition, Random policies naturally satisfy CF but may not achieve high values. Fairness metric To measure deviation from counterfactual fairness, we introduce the following CF metric, adapted from previous work ( Chen et al., 2023 ; Wang et al., 2022 ; Wu et al., 2019 ) , \displaystyle\max_{z^{\prime},z\in\mathcal{Z}}\frac{1}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}\mathbf{I}\left(A_{t}^{Z\leftarrow z^{\prime}}(\bar{U}_{t}(h_{it}))\neq A_{t}^{Z\leftarrow z}(\bar{U}_{t}(h_{it}))\right). (5) This metric calculates the maximum discrepancy between the average discordance rate between actions in the factual and counterfactual worlds across all the time points for any given pair of distinct sensitive attribute values, (z,z^{\prime}) where z,z^{\prime}\in\mathcal{Z},z\neq z^{\prime} . A lower value indicates that the policy is fairer. The metric is bounded between 0 and 1, with 0 representing perfect fairness and 1 indicating complete unfairness. Deployment of our approach: To deploy the learned policy using Algorithm 1 and 2 , counterfactual states need to be sequentially estimated. Specifically, before making a decision at time t using \tilde{x}_{t} , the policy needs to first use the stored \tilde{x}_{t-1} and observed x_{t} to estimate the value of \tilde{x}_{t} . Therefore, the learned policy requires a memory buffer to store the counterfactual states at previous time point during deployment. 6.1 Synthetic data experiments We consider both linear and non-linear transition kernels settings in this experiment. We consider two goals: 1) validate that the level of counterfactual unfairness decreases as the sample size increases for our approach, and 2) investigate how the strength of a sensitive attribute’s impact on state and reward affects unfairness. For each setting, we fix the length of horizon T=10 . Let \delta denote the strength of impact of sensitive attribute Z on states \{S_{t}\}_{t\geq 1} and rewards \{R_{t}\}_{t\geq 1} . For the first goal, we vary the sample size N in \{100,200,500,1000,2000\} and fix \delta to be 1 . For the second goal, we fix the sample size N=1000 and vary \delta in \{0.0,0.5,1.0,1.5,2.0\} . The CF metric is calculated by comparing the action distributions generated by the policy in the observed and corresponding counterfactual world. The cumulative discounted reward is calculated using the observed reward collected from the trajectories. We use N=10000 and T=20 to calculate each metric. Figure 4 (a,b,d,e) present the results for the first goal. As expected, both Random and Oracle policies achieves prefect CF. The Full and Unaware policies exhibits high unfairness levels, while our proposed approach achieves lower CF metric. Additionally, the CF metric of our approach decreases with increasing sample size N , validating the consistency. In terms of cumulative discounted reward, the Full policy achieves the greatest total reward due to its access to all state information. The other three approaches have lower reward due to the loss of state information, indicating a fairness-reward trade-off ( Dutta et al., 2020 ; Wick et al., 2019 ) . To control the degree of unfairness, a weighted combination of the Full policy and our proposed policy could be considered. Greater weight assigned to our proposed method prioritizes fairness, and conversely, greater weight on the Full policy prioritizes reward maximization. Figure 4 (c,f) show the results for the second goal. We observe that the unfairness of the Full and Unaware policies increases with increasing \delta , while our proposed approach effectively controls unfairness, indicating that our approach can effectively remove the information of sensitive attribute from the state variables and learn CF policy at varying vulnerabilities to unfairness. Figure 4: Comparisons under the linear setting (top row) and non-linear setting (bottom role): a,d) CF metric versus sample size, b,e) cumulative discounted reward versus CF metric (multiple sample sizes) with \delta=1 , c,f) CF metric versus \delta . All the results are aggregated over 100 random seeds. The shaded area represents the 95\% CI. 6.2 Semi-synthetic data To bridge the gap between theoretical results and practical applicability, we conduct real-world data-based simulations to evaluate the performance of different approaches under more realistic conditions. These simulations were designed to mimic the motivating PowerED study ( Piette et al., 2023 ) with respect to transition dynamics. We select education, sex and ethnicity as three different potentially sensitive attributes in our simulations. The state variables include weekly pain intensity score and pain interference score - two commonly used metrics to evaluate progress in pain management programs. The reward is the 7 - weekly self-reported opioid medication risk score , defined in detail in Piette et al. (2023) . We simulate 100 different datasets with N=1000 and T=12 using the neural network-based generative models learned from the real dataset. To investigate how the strength of the sensitive attribute’s state variables affects unfairness, we incorporated a strategy similar to the one used in the synthetic data experiments. We varied the effect magnitude of the sensitive attribute on the state variables by adding a constant value \eta to the state variables for one value of sensitive attribute. The results are shown in Figure 5 . We observe that the Full policy has high levels of counterfactual unfairness across all scenarios. The Unaware policy demonstrates increasing unfairness as the effect of the sensitive attribute on the state variables \eta increases. This suggests that even after excluding the sensitive attribute, the state variables might still contain residual information of the sensitive attribute, resulting in unfairness. Our proposed approach achieves lower counterfactual unfairness compared with the other two methods. The observed unfairness in our method is primarily due to the approximation error of the counterfactual state when compared with the perfect fairness for the Oracle policy. The results are in line with our theoretical findings. Figure 5: Semi-synthetic experiments: CF metric of different approaches versus \eta for different sensitive attributes: education, sex, ethnicity. All the results are aggregated over 100 random seeds. The shaded area is the 95\% CI. 7 Application to Reducing Opioid Misuse Behaviors In this section, we apply the proposed algorithm to a real-world digital health dataset named PowerED study, as described in Section 1 . The data comprise 207 patients over 12 weeks. We selected education, age, gender, and ethnicity as the potentially sensitive attributes, and weekly pain and pain interference scores as the state variables. The reward is defined as 7 - weekly self-reported opioid medication risk score , which was measured by items during weekly monitoring calls. We compare our approach to three baselines: Full , Random and Unaware , as detailed in Section 6 . CF metric and cumulative discounted reward are evaluated. To compute the CF metric, we need to assess counterfactual actions under different values of Z , while we only observe a single z in the dataset. Therefore, we train a generative model, similar to the one presented in Section 6.2 , to generate counterfactual actions, enabling the calculation of the CF metric. We use fitted Q evaluation ( Le et al., 2019 ) to estimate the value for each policy. The dataset is split into training and validation sets using an 80:20 ratio, where the training set is used for policy learning and validation set is used for metric calculations. The results are aggregated for 10 different seeds. As summarized in Table 1 , Random policy achieves the perfect fairness but a lower value, as it entirely disregards state information for decision-making. Full policy demonstrates the highest value for most variables, however, it has the highest level of unfairness, as incorporating sensitive attributes into the decision-making process can inherently lead to unfair decisions. Our approach achieves the lowest unfairness for all four sensitive attributes compared to other methods. While our approach did not achieve perfect fairness, we believe that the approximation errors associated with estimating counterfactual states and rewards are likely to be relatively higher. Supplemental Figure illustrates the favorability of actions of different policies towards different sensitive groups. It can be seen that the Full policy tends to favor younger, more educated, non-Hispanic, and male patients by giving them a higher percentage of treatments compared to other sensitive groups. Our approach mitigates this bias and achieves lower unfairness. Our approach greatly enhanced fair access to human counselors without significantly compromising population-level benefit. Metric Method Education Age Sex Ethnicity Unfairness Full 0.44 (0.14) 0.59 (0.15) 0.61 (0.15) 0.39 (0.13) Random 0.00 (0.00) 0.00 (0.00) 0.00 (0.00) 0.00 (0.00) Unaware 0.10 (0.03) 0.10 (0.02) 0.08 (0.03) 0.21 (0.05) Ours 0.06 (0.02) 0.08 (0.02) 0.07 (0.02) 0.16 (0.03) Value Full 57.09 (0.31) 57.29 (0.30) 57.20 (0.39) 56.87 (0.33) Random 56.61 (0.22) 56.66 (0.27) 56.53 (0.27) 56.54 (0.39) Unaware 57.01 (0.18) 57.21 (0.29) 56.96 (0.32) 57.00 (0.31) Ours 57.05 (0.30) 57.11 (0.28) 56.95 (0.51) 56.93 (0.48) Table 1: Unfairness metric (the lower the better) and value (the higher the better) for different approaches in the real data analysis. 8 Discussion In this paper, we have studied counterfactual fairness in the novel context of RL. We provide a general framework for defining CF in multi-stage settings and theoretically characterize the class of CF policies. We also prove that the optimal CF policy is stationary under stationary CMDPs, which greatly simplifies policy learning. Methodologically, we develop a novel sequential data preprocessing algorithm designed to mitigate bias in multi-stage settings and to produce preprocessed experience tuples to enable learning CF policies by leveraging existing RL methods. We also establish theoretical guarantees on value optimality and unfairness control. Empirical results based on numerical experiments corroborate with our theory. We provide some additional discussions. Definition 3 Definition 3 extends path-dependent CF ( Kusner et al., 2017 ) to the CMDP setting by fixing the historical action sequence \bar{A}_{t-1} to the observed sequence \bar{a}_{t-1} rather than allowing the past actions to change after switching the value of Z . A direct extension of single-stage CF ( Kusner et al., 2017 ) to CMDP without fixing \bar{A}_{t-1} to \bar{a}_{t-1} would be problematic, as the resulting CF definition would depend on the behavior policy. A further extension to Definition 3 would require action distribution invariance for arbitrary historical action sequences \bar{a}_{t-1}^{\prime}\in\mathcal{A}^{t-1} that could have but not actually experienced by the individual in the past (Definition , Section in the supplementary materials). The extension requires correcting historical unfair decisions the individual have received before an action at time t , while Definition 3 solely focuses on mitigating decision unfairness at and later than time t assuming past actions \bar{A}_{t-1} cannot be undone. Definition is therefore stricter than Definition 3 and will result in a lower optimal value. Class of CF Policies We focused on the class of CF policies that takes (\bar{\mathcal{S}}_{t},\bar{\mathcal{R}}_{t-1},\bar{a}_{t-1}) as input. Do there exist CF policies outside this class that can achieve higher value? Consider the three policy classes below with increasing restrictiveness. The first class is \Pi_{1}=\{\pi_{t}:\pi_{t}(Z,\bar{S}_{t},\bar{R}_{t-1},\bar{A}_{t-1})\} . DTR ( Murphy, 2003 ) ensures that \Pi_{1} contains value-optimal policies, however, direct use of Z violates the CF definition. The second class, \Pi_{2}=\{\pi_{t}:\pi_{t}(\bar{\mathcal{S}}_{t},\bar{\mathcal{R}}_{t-1},\bar{A}_{t-1})\} , removes the information of Z from the policy inputs, which ensures CF but potentially at the cost of reduced value compared to \Pi_{1} . The third class, \Pi_{3} , extends beyond \Pi_{2} by applying do-calculus not only to Z but also to \bar{A}_{t-1} (to any action sequence). While policies in \Pi_{3} satisfy CF, they achieve lower value than those in \Pi_{2} because the information of the observed \bar{A}_{t-1} is removed from policy input. Additivity Assumption The additive assumption (Assumption 4 ) can be restrictive in real-world settings. However, it is important to acknowledge that causal inference, especially when dealing with counterfactuals, often relies on strong assumptions ( Dawid, 2000 ; Pearl, 2009 ) . Relaxing these assumptions may be possible with more flexible approaches, such as variational autoencoder ( Louizos et al., 2017 ) and adversarial training ( Melnychuk et al., 2022 ) . We leave this topic for future research. Supplementary Materials Supplementary Materials contain a glossary of notation, proofs, supporting figures, tables, longer derivations, and additional results. The following sections are included: A: Generalization of Definition 3 . B-E: Proofs of Theorems 1 2 , 3 , 4 F: Details on numerical experiments in Section 6 G: More details on real data analysis in Section 7 Code to reproduce simulations and data analysis will be made available online at github.com. Suppplementary Materials for “Counterfactually Fair Reinforcement Learning via Sequential Data Preprocessing” The supplementary materials contain a glossary of technical notation, a technical extension, proofs of theorems, and additional details about simulation and data analysis. We first provide a glossary for key notation used in the Main Paper. Symbol Description \bar{S}_{t},\bar{A}_{t},\bar{R}_{t} historical states, actions and rewards up to time t . \bar{U}^{S}_{t},\bar{U}^{A}_{t},\bar{U}^{R}_{t} historical exogenous variables for states, actions and rewards up to time t . H_{t} \{Z,\bar{S}_{t},\bar{A}_{t-1},\bar{R}_{t-1}\} , complete history up to time t \bar{U}_{t} \{\bar{U}^{R}_{t-1},\bar{U}^{S}_{t}\} R_{t-1}^{Z\leftarrow z^{\prime}}(\bar{U}_{t}(h_{t})) , S_{t}^{Z\leftarrow z^{\prime}}(\bar{U}_{t}(h_{t})) , A_{t}^{Z\leftarrow z^{\prime}}(\bar{U}_{t}(h_{t})) the counterfactual reward, state, action that would have been for an individual with history h_{t} had their sensitive attribute been z^{\prime} , while experiencing the observed action sequence \bar{a}_{t-1} and following \pi_{t} \mathcal{S}_{t} [S_{t}^{Z\leftarrow z^{(k)}}(\bar{U}_{t}(h_{t}))]_{k=1,\dots,K} \mathcal{R}_{t-1} [R_{t-1}^{Z\leftarrow z^{(k)}}(\bar{U}_{t}(h_{t}))]_{k=1,\dots,K} A Generalization of Definition Definition A1 (Strict Counterfactual Fairness in CMDP) . Given an observed trajectory H_{t}=h_{t} , a decision rule \pi_{t} is strictly counterfactually fair at time t if it satisfies the following condition: \displaystyle\mathbb{P}^{\pi_{t}}\left(A_{t}^{Z\leftarrow z^{\prime},\bar{A}_{t-1}\leftarrow\bar{a}_{t-1}^{\prime}}(\bar{U}_{t}(h_{t}))=a\right)=\mathbb{P}^{\pi_{t}}\left(A_{t}^{Z\leftarrow z,\bar{A}_{t-1}\leftarrow\bar{a}_{t-1}}(\bar{U}_{t}(h_{t}))=a\right), (A.1) for any z^{\prime}\in\mathcal{Z},\bar{a}_{t-1}^{\prime}\in\mathcal{A}^{t-1} and a\in\mathcal{A} . Here the definition is stricter than Definition because it requires action distribution invariance for arbitrary historical action sequences \bar{a}_{t-1}^{\prime}\in\mathcal{A}^{t-1} that could have but not actually experienced by the individual in the past. B Proof of Theorem Proof. If we can show that \bar{\mathcal{S}}_{t} , \bar{\mathcal{R}}_{t} and \bar{a}_{t-1} are invariant with respect to the counterfactual values of Z , and given \pi_{t} is a function of these quantities, then Equation ( ) is invariant to different counterfactual values of Z . First , since we fix \bar{A}_{t-1} to be the observed action sequence \bar{a}_{t-1} for all possible values of Z , \bar{a}_{t-1} is invariant to the counterfactual values of Z . Second , \mathcal{S}_{t} consists of the counterfactual states for all possible values of Z . Altering the value of Z does not affect the distribution of \mathcal{S}_{t} . Since \bar{\mathcal{S}}_{t} is a collection \mathcal{S}_{t^{\prime}} for t^{\prime}\leq t , its distribution of \bar{\mathcal{S}}_{t} remains invariant to counterfactual values of Z . Similarly, we can show that \bar{\mathcal{R}}_{t} is invariant to any counterfactual values of Z . As \bar{\mathcal{S}}_{t} , \bar{\mathcal{R}}_{t} and \bar{a}_{t-1} are invariant with respect to the counterfactual values of Z , any decision rule \pi_{t} satisfies Equation ( ) is counterfactually fair. ∎ C Proof of Theorem Proof. We begin by introducing the following notations \displaystyle\mathbb{S}_{t}^{k} \displaystyle=S_{t}^{Z\leftarrow z^{(k)}}\left(\bar{U}_{t}\left(H_{t}\right)\right), \displaystyle\mathbb{R}_{t}^{k} \displaystyle=R_{t}^{Z\leftarrow z^{(k)}}\left(\bar{U}_{t}\left(H_{t}\right)\right), \displaystyle\mathbb{S}_{t} \displaystyle=\left\{\mathbb{S}_{t}^{k}\right\}_{k=1,\dots,K}, \displaystyle\mathbb{R}_{t} \displaystyle=\left\{\mathbb{R}_{t}^{k}\right\}_{k=1,\dots,K}. For simplicity, we include \mathbb{R}_{t}^{k} in the set of \mathbb{S}_{t+1}^{k} . The following conclusions automatically holds if we include U^{R}_{t} in the set of U^{S}_{t+1} . Note that unlike \mathcal{S}_{t}^{k} , we do not enforce \bar{A}_{t-1}\leftarrow\bar{a}_{t-1} on \mathbb{S}_{t}^{k} . The action sequence \bar{a}_{t-1} can be arbitrary, however, \mathbb{S}_{t}^{k} share the same \bar{a}_{t-1} for different k due to Pearl’s three-step procedure for counterfactual inference ( Pearl et al., 2016 ) . According to Assumption , Figure C.1 depicts the relationship between \mathbb{S}_{t}^{k} , A_{t} and U_{X_{t}} . Figure C.1: Causal diagram of counterfactual states and actions. We have following conclusions via d-separation: for any k \displaystyle\mathbb{S}_{t+1}^{k}\perp\!\!\!\!\perp\{\mathbb{S}_{j}^{k},A_{j}\}_{1\leq j\leq t-1}\mid\mathbb{S}_{t}^{k},A_{t}, \displaystyle\mathbb{S}_{t+1}\perp\!\!\!\!\perp\{\mathbb{S}_{j},A_{j}\}_{1\leq j\leq t-1}\mid\mathbb{S}_{t},A_{t}. So far, we have shown that the Markov property holds for \mathbb{X}_{t} . In the next step, we show the connection between \mathbb{S}_{t} and \mathcal{S}_{t} . The key assumption we use here is Assumption . We use mathematical induction to show that the Markov property holds for \mathcal{S}_{t} . First , assume that for t\leq l , we have \displaystyle P(S_{t}^{Z\leftarrow z^{(k)},\bar{A}_{t-1}\leftarrow\bar{a}_{t-1}}(\bar{U}_{t}(H_{t}))\mid S_{1}^{Z\leftarrow z^{(k)}}(U_{1}(H_{1})),\dots,S_{t-1}^{Z\leftarrow z^{(k)},\bar{A}_{t-2}\leftarrow\bar{a}_{t-2}}(\bar{U}_{t-1}(H_{t-1}))) \displaystyle= \displaystyle P(S_{t}^{Z\leftarrow z^{(k)}}(\bar{U}_{t}(H_{t}))\mid S_{t-1}^{Z\leftarrow z^{(k)}}(\bar{U}_{t-1}(H_{t-1})),A_{t-1}=a_{t-1}) \displaystyle= \displaystyle P(\mathbb{S}_{t}^{k}\mid\mathbb{S}_{t-1}^{k},A_{t-1}=a_{t-1}). (C.1) It is obvious that C.1 holds when t=2 due to Assumption , \displaystyle P(S_{2}^{Z\leftarrow z^{(k)},A_{1}\leftarrow a_{1}}(\bar{U}_{2}(H_{2}))\mid S_{1}^{Z\leftarrow z^{(k)}}(U_{1}(H_{1}))) \displaystyle= \displaystyle P(S_{2}^{Z\leftarrow z^{(k)}}(\bar{U}_{2}(H_{2}))\mid S_{1}^{Z\leftarrow z^{(k)}}(U_{1}(H_{1})),A_{1}=a_{1}) \displaystyle= \displaystyle P(\mathbb{S}_{2}^{k}\mid\mathbb{S}_{1}^{k},A_{1}=a_{1}). (C.2) Second , for t=l+1 , we have \displaystyle P(S_{t}^{Z\leftarrow z^{(k)},\bar{A}_{t-1}\leftarrow\bar{a}_{t-1}}(\bar{U}_{t}(H_{t})),\cdots,S_{1}^{Z\leftarrow z^{(k)},A_{1}\leftarrow a_{1}}(\bar{U}_{2}(H_{2}))\mid S_{1}^{Z\leftarrow z^{(k)}}(\bar{U}_{1}(H_{1}))) \displaystyle= \displaystyle P(S_{t}^{Z\leftarrow z^{(k)},A_{2}\dots A_{t-1}\leftarrow a_{2}\dots a_{t-1}}(\bar{U}_{t}(H_{t})),\cdots,S_{2}^{Z\leftarrow z^{(k)}}(\bar{U}_{t-1}(H_{t-1}))\mid S_{1}^{Z\leftarrow z^{(k)}}(\bar{U}_{1}(H_{1})),A_{1}=a_{1}). (C.3) Combine C.3 with C.2 , we have \displaystyle P(\{S_{j}^{Z\leftarrow z^{(k)},\bar{A}_{j-1}\leftarrow\bar{a}_{j-1}}(\bar{U}_{j}(H_{j}))\}_{j=3,\dots,t}\mid S_{2}^{Z\leftarrow z^{(k)},A_{1}\leftarrow a_{1}}(\bar{U}_{2}(H_{2})),S_{1}^{Z\leftarrow z^{(k)}}(\bar{U}_{1}(H_{1}))) \displaystyle= \displaystyle P(\{S_{j}^{Z\leftarrow z^{(k)},A_{2}\dots A_{j-1}\leftarrow a_{2},\dots a_{j-1}}(\bar{U}_{j}(H_{j}))\}_{j=3,\dots,t}\mid S_{2}^{Z\leftarrow z^{(k)}}(\bar{U}_{2}(H_{2})),S_{1}^{Z\leftarrow z^{(k)}}(\bar{U}_{1}(H_{1})),A_{1}=a_{1}). (C.4) By repeating this procedure up to time t-1 , we have \displaystyle P(S_{t}^{Z\leftarrow z^{(k)},\bar{A}_{t-1}\leftarrow\bar{a}_{t-1}}(\bar{U}_{t}(H_{t}))\mid\{S_{j}^{Z\leftarrow z^{(k)},\bar{A}_{j-1}\leftarrow\bar{a}_{j-1}}(\bar{U}_{j}(H_{j})\}_{j=2,\dots,t-1},S_{1}^{Z\leftarrow z^{(k)}}(\bar{U}_{1}(H_{1}))) \displaystyle= \displaystyle P(S_{t}^{Z\leftarrow z^{(k)},A_{t-1}\leftarrow a_{t-1}}(\bar{U}_{t}(H_{t}))\mid\{S_{j}^{Z\leftarrow z^{(k)}}(\bar{U}_{j}(H_{j})\}_{j=2,\dots,t-1},S_{1}^{Z\leftarrow z^{(k)}}(\bar{U}_{1}(H_{1})),\bar{A}_{t-2}=\bar{a}_{t-2}) \displaystyle= \displaystyle P(S_{t}^{Z\leftarrow z^{(k)}}(\bar{U}_{t}(H_{t}))\mid\{S_{j}^{Z\leftarrow z^{(k)}}(\bar{U}_{j}(H_{j})\}_{j=2,\dots,t-1},S_{1}^{Z\leftarrow z^{(k)}}(\bar{U}_{1}(H_{1})),\bar{A}_{t-1}=\bar{a}_{t-1}) \displaystyle= \displaystyle P(\mathbb{S}_{t}^{k}\mid\{\mathbb{S}_{j}^{k}\}_{j=1,\dots,t-1},\bar{A}_{t-1}=\bar{a}_{t-1}) \displaystyle= \displaystyle P(\mathbb{S}_{t}^{k}\mid\mathbb{S}_{j}^{t-1},A_{t-1}=a_{t-1}) (C.5) The first and second equation are due to Assumption , the third equation is due to the Markov property of \mathbb{S}_{t}^{k} . Therefore, we show that the Markov property holds for \mathcal{S}_{t}^{k} . Similarly, we can show that the Markov property holds for \mathcal{S}_{t} . Let \tilde{\mathbb{R}}_{t} to be the weighted sum of \mathbb{R}_{t}^{k} , \displaystyle\tilde{\mathbb{R}}_{t}=\sum_{k}p_{k}\mathbb{R}_{t}^{k}, where \{p_{k}\}_{k=1,\dots,K} are fixed weights with \sum_{k}p_{k}=1 . Note that we have \displaystyle\mathbb{S}_{t},\tilde{\mathbb{R}}_{t-1}\;\,\rule[0.0pt]{0.29999pt}{6.69998pt}\hskip-2.70004pt\rule[-0.20004pt]{6.99997pt}{0.29999pt}\hskip-2.70004pt\rule[0.0pt]{0.29999pt}{6.69998pt}\;\,\{\tilde{\mathbb{R}}_{j-1},\mathbb{S}_{j},A_{j}\}_{j=2,\dots,t-2}\mid\mathbb{S}_{t-1},A_{t-1}. By applying Lemma 1 of ( Shi et al., 2020 ) , we show that there exists a stationary deterministic policy \pi(\cdot|\mathbb{S}_{t}) such that it maximize the integrated value function defined as follow, \displaystyle J(\pi)= \displaystyle\int_{s}E\left[\sum_{t=1}^{\infty}\gamma^{t-1}\tilde{\mathbb{R}}_{t}\mid\mathbb{S}_{1}=s\right]P(\mathbb{S}_{1}=x)ds \displaystyle= \displaystyle\int_{s}E\left[\sum_{t=1}^{\infty}\gamma^{t-1}\sum_{k}\tilde{\mathbb{R}}_{t}^{k}p_{k}\mid\mathbb{S}_{1}=s\right]P(\mathbb{S}_{1}=s)ds \displaystyle= \displaystyle\int_{s}\sum_{k}E\left[\sum_{t=1}^{\infty}\gamma^{t-1}\tilde{\mathbb{R}}_{t}^{k}\mid\mathbb{S}_{1}=s,Z=z_{k}\right]p_{k}P(\mathbb{S}_{1}=s)ds \displaystyle= \displaystyle\int_{s}\sum_{k}V_{0}^{\pi}(s,z_{k})p_{k}P(\mathbb{S}_{1}=s)ds, (C.6) where V_{0}^{\pi}(\cdot,\cdot) is the value function for original CMDP. Note that we have \mathbb{S}_{1}\;\,\rule[0.0pt]{0.29999pt}{6.69998pt}\hskip-2.70004pt\rule[-0.20004pt]{6.99997pt}{0.29999pt}\hskip-2.70004pt\rule[0.0pt]{0.29999pt}{6.69998pt}\;\,Z due to the definition of counterfactual state. If p_{k} match the distribution of P(Z=z_{k}) in the target population, maximizing C.6 is the same as maximizing \displaystyle J_{0}(\pi)=\int_{s,z}V_{0}^{\pi}(s,z)P(S_{1}=s,Z=z)dsdz, which is the same as integrated value function of original CMDP with observed reward in the target population. ∎ D Proof of Theorem Assumption D1 (Hypothesis Class) . \mathcal{F}=\{w^{T}\phi(s,a):w\in\mathbb{R}^{d},\|w\|\leq\mathcal{B}\}, where \phi is a feature map \mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d} with \|\phi(s,a)\|_{\infty}\leq 1 . Assumption D2 (Completeness) . Let \mathcal{T} be the Bellman optimality operator: for f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R} , \mathcal{T}f(s,a)=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim P(\cdot\mid s,a)}\max_{a^{\prime}\in\mathcal{A}}f(s^{\prime},a^{\prime}). Assume for any f\in\mathcal{F} , \mathcal{T}f\in\mathcal{F} . Assumption D3 (Feature Coverage) . There exists a constant \lambda_{0}>0 such that \displaystyle\lambda_{min}(\mathbb{E}_{s,a\sim\mu_{b}}[\phi(s,a)\phi(s,a)^{T}])\geq\lambda_{0}. Assumption D4 (Lipschitz Continuous Features) . There exists a constant L>0 such that \displaystyle\|\phi_{i}(s,a)-\phi_{i}(s^{\prime},a)\|\leq L\|s-s^{\prime}\|, for any a\in\mathcal{A} and i=1,\dots,d . Assumption D5 (Bounded Reward) . There exists a constant R_{\max}>0 such that |r|\leq R_{\max} . Proof. Let w_{f} denote the parameter estimate when the value function is f , namely, \displaystyle w_{f}=\left[\sum_{i=1}^{n}\phi(s_{i},a_{i})\phi(s_{i},a_{i})^{\top}\right]^{-1}\left[\sum_{i=1}^{n}\phi(s_{i},a_{i})\left(r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a^{\prime})\right)\right]. (D.1) Let \hat{w}_{f} be the corresponding parameter estimate when the s_{i} , s_{i}^{\prime} and r_{i} are replaced by estimated \hat{s}_{i} , \hat{s}_{i}^{\prime} and \hat{r}_{i} , namely, \displaystyle\hat{w}_{f}=\left[\sum_{i=1}^{n}\phi(\hat{s}_{i},a_{i})\phi(\hat{s}_{i},a_{i})^{\top}\right]^{-1}\left[\sum_{i=1}^{n}\phi(\hat{s}_{i},a_{i})\left(\hat{r}_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(\hat{s}_{i}^{\prime},a^{\prime})\right)\right]. (D.2) According to Theorem 8 in Hu et al. (2024) , we know that \displaystyle\|Q^{*}-\hat{f}_{B}\|_{\infty}\leq\sum_{t=0}^{B-1}\gamma^{t}\|\hat{f}_{B-t}-\mathcal{T}\hat{f}_{B-t-1}\|_{\infty}+\frac{\gamma^{B}R_{max}}{1-\gamma}. (D.3) The second term is a diminishing term as the number of iterations B increase. Therefore, we aim to characterize the first term, which is a weighted sum of one-step estimation errors. For any f\in\mathcal{F} , one step estimation error can be bounded by, \displaystyle\|\hat{w}_{f}^{\top}\phi-\mathcal{T}f\|_{\infty} \displaystyle\leq\|\hat{w}_{f}^{\top}\phi-w_{f}^{\top}\phi+w_{f}^{\top}\phi-\mathcal{T}f\|_{\infty} \displaystyle\leq\|\hat{w}_{f}^{\top}\phi-w_{f}^{\top}\phi\|_{\infty}+\|w_{f}^{\top}\phi-\mathcal{T}f\|_{\infty} \displaystyle\leq\|\hat{w}_{f}^{\top}-w_{f}^{\top}\|_{\infty}\cdot\|\phi\|_{\infty}+\|w_{f}^{\top}\phi-\mathcal{T}f\|_{\infty}. (D.4) The second term can be bounded by Lemma 7 in Hu et al. (2024) . The first term characterizes the estimation error when the state and reward are estimated. To simplify the notation, we denote \displaystyle A \displaystyle=\sum_{i=1}^{n}\phi(s_{i},a_{i})\phi(s_{i},a_{i})^{\top}, \displaystyle\mathbf{b} \displaystyle=\sum_{i=1}^{n}\phi(s_{i},a_{i})\left(r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a^{\prime})\right), \displaystyle C \displaystyle=\sum_{i=1}^{n}\phi(\hat{s}_{i},a_{i})\phi(\hat{s}_{i},a_{i})^{\top}, \displaystyle\mathbf{d} \displaystyle=\sum_{i=1}^{n}\phi(\hat{s}_{i},a_{i})\left(\hat{r}_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(\hat{s}_{i}^{\prime},a^{\prime})\right). And we can bound the estimation error, \displaystyle\left\|\hat{w}_{f}-w_{f}\right\|_{\infty} \displaystyle=\left\|A^{-1}\mathbf{b}-C^{-1}\mathbf{d}\right\|_{\infty} \displaystyle=\left\|A^{-1}\mathbf{b}-A^{-1}\mathbf{d}+A^{-1}\mathbf{d}-C^{-1}\mathbf{d}\right\|_{\infty} \displaystyle\leq\left\|A^{-1}\right\|_{2}\left\|\mathbf{b}-\mathbf{d}\right\|_{\infty}+\left\|A^{-1}-C^{-1}\right\|_{2}\left\|\mathbf{d}\right\|_{\infty} \displaystyle\leq\left\|A^{-1}\right\|_{2}\left\|\mathbf{b}-\mathbf{d}\right\|_{\infty}+\left\|A^{-1}\right\|_{2}\left\|A-C\right\|_{2}\left\|C^{-1}\right\|_{2}\left\|\mathbf{d}\right\|_{\infty}. (D.5) Next step, we bound each term in ( D.5 ). Bound \|A^{-1}\|_{2} : By Lemma 7 in Hu et al. (2024) , we have \displaystyle P(\lambda_{\min}(A)\geq n\lambda_{0}/2)\leq d\exp(-n\lambda_{0}/8). When the event \lambda_{\min}(A)\geq n\lambda_{0}/2 holds, we have \displaystyle\|A^{-1}\|_{2}\leq\frac{2}{n\lambda_{0}}. (D.6) Bound \|A-C\|_{2} : To bound this term, we first consider bounding element-wise difference between A and C , \displaystyle\left|A_{jk}-C_{jk}\right| \displaystyle=\left|\sum_{i=1}^{n}\phi_{j}(s_{i},a_{i})\phi_{k}(s_{i},a_{i})-\phi_{j}(\hat{s}_{i},a_{i})\phi_{k}(\hat{s}_{i},a_{i})\right| \displaystyle=\left|\sum_{i=1}^{n}\phi_{j}(s_{i},a_{i})(\phi_{k}(s_{i},a_{i})-\phi_{k}(\hat{s}_{i},a_{i}))+(\phi_{j}(s_{i},a_{i})-\phi_{j}(\hat{s}_{i},a_{i}))\phi_{k}(\hat{s}_{i},a_{i})\right| \displaystyle\leq\left|\sum_{i=1}^{n}(\phi_{k}(s_{i},a_{i})-\phi_{k}(\hat{s}_{i},a_{i}))+(\phi_{j}(s_{i},a_{i})-\phi_{j}(\hat{s}_{i},a_{i}))\right| \displaystyle\leq 2nL\epsilon. Therefore, we have \displaystyle\|A-C\|_{2} \displaystyle\leq\|A-C\|_{F}=\sqrt{\sum_{j=1}^{d}\sum_{k=1}^{d}\left|A_{j,k}-C_{j,k}\right|^{2}}\leq 2ndL\epsilon (D.7) Bound \|C^{-1}\|_{2} : For any semi positive-definite matrix A and C , we have \displaystyle|\lambda_{\min}(A)-\lambda_{\min}(C)|\leq\|A-C\|_{2}\leq 2ndL\epsilon. When the event \lambda_{\min}(A)\geq n\lambda_{0}/2 holds, we have \displaystyle\lambda_{\min}(C)\geq n\lambda_{0}/2-2ndL\epsilon, and we have \displaystyle\|C^{-1}\|_{2}\leq\frac{2}{n\lambda_{0}-4ndL\epsilon}. (D.8) Bound \|\mathbf{b}-\mathbf{d}\|_{\infty} : We can bound \|\mathbf{b}-\mathbf{d}\|_{\infty} by \displaystyle\|\mathbf{b}-\mathbf{d}\|_{\infty} \displaystyle=\bigg\|\sum_{i=1}^{n}\phi(\hat{s}_{i},a_{i})(r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a_{i}^{\prime})-\hat{r}_{i}-\gamma\max_{a^{\prime}\in\mathcal{A}}f(\hat{s}_{i}^{\prime},a_{i}^{\prime})) \displaystyle+\sum_{i=1}^{n}(\phi(s_{i},a_{i})-\phi(\hat{s}_{i},a_{i}))(r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a_{i}))\bigg\|_{\infty} \displaystyle\leq\bigg\|\sum_{i=1}^{n}\phi(\hat{s}_{i},a_{i})(r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a_{i}^{\prime})-\hat{r}_{i}-\gamma\max_{a^{\prime}\in\mathcal{A}}f(\hat{s}_{i}^{\prime},a_{i}^{\prime}))\bigg\|_{\infty} \displaystyle+\bigg\|\sum_{i=1}^{n}(\phi(s_{i},a_{i})-\phi(\hat{s}_{i},a_{i}))(r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a_{i}))\bigg\|_{\infty} \displaystyle\leq\sum_{i=1}^{n}|r_{i}-\hat{r}_{i}|\bigg\|\phi(\hat{s}_{i},a_{i})\bigg\|_{\infty}+\gamma\sum_{i=1}^{n}\bigg|\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a_{i}^{\prime})-\max_{a^{\prime}\in\mathcal{A}}f(\hat{s}_{i}^{\prime},a_{i}^{\prime})\bigg|\bigg\|\phi(\hat{s}_{i},a_{i})\bigg\|_{\infty} \displaystyle+\sum_{i=1}^{n}\bigg|(r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a_{i}))\bigg|\bigg\|(\phi(s_{i},a_{i})-\phi(\hat{s}_{i},a_{i}))\bigg\|_{\infty} \displaystyle\leq\sum_{i=1}^{n}|r_{i}-\hat{r}_{i}|\bigg\|\phi(\hat{s}_{i},a_{i})\bigg\|_{\infty}+\gamma\sum_{i=1}^{n}L\|s_{i}-\hat{s}_{i}\|_{\infty}\bigg\|\phi(\hat{s}_{i},a_{i})\bigg\|_{\infty} \displaystyle+\sum_{i=1}^{n}\bigg|(r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a_{i}))\bigg|\bigg\|\phi(s_{i},a_{i})-\phi(\hat{s}_{i},a_{i})\bigg\|_{\infty} \displaystyle\leq(1+\gamma L+\frac{R_{\max}L}{1-\gamma})n\epsilon. (D.9) Bound \|d\|_{\infty} : To bound \|d\|_{\infty} , we consider \displaystyle\|\mathbf{d}\|_{\infty} \displaystyle\leq\|\mathbf{b}-\mathbf{d}\|_{\infty}+\|\mathbf{b}\|_{\infty} \displaystyle\leq(1+\gamma L+\frac{R_{\max}L}{1-\gamma})n\epsilon+\|\sum_{i=1}^{n}\phi(s_{i},a_{i})\left(r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a^{\prime})\right)\|_{\infty} \displaystyle\leq(1+\gamma L+\frac{R_{\max}L}{1-\gamma})n\epsilon+\sum_{i=1}^{n}|\left(r_{i}+\gamma\max_{a^{\prime}\in\mathcal{A}}f(s_{i}^{\prime},a^{\prime})\right)|\|\phi(s_{i},a_{i})\|_{\infty} \displaystyle\leq(1+\gamma L+\frac{R_{\max}L}{1-\gamma})n\epsilon+\frac{nR_{\max}}{1-\gamma}. (D.10) Bound \left\|\hat{w}_{f}-w_{f}\right\|_{\infty} : With bound for each term, we have, \displaystyle\left\|\hat{w}_{f}-w_{f}\right\|_{\infty} \displaystyle\leq\left\|A^{-1}\right\|_{2}\left\|\mathbf{b}-\mathbf{d}\right\|_{\infty}+\left\|A^{-1}\right\|_{2}\left\|A-C\right\|_{2}\left\|C^{-1}\right\|_{2}\left\|\mathbf{d}\right\|_{\infty} \displaystyle\leq\frac{2}{n\lambda_{0}}(1+\gamma L+\frac{R_{\max}L}{1-\gamma})n\epsilon \displaystyle+\frac{2}{n\lambda_{0}}*2ndL\epsilon*\frac{2}{n\lambda_{0}-4ndL\epsilon}*((1+\gamma L+\frac{R_{\max}L}{1-\gamma})n\epsilon+\frac{nR_{\max}}{1-\gamma}) \displaystyle=\frac{2\epsilon}{\lambda_{0}-4dL\epsilon}\left(1+\gamma L+\frac{R_{\max}L}{1-\gamma}\right)+\frac{8dL\epsilon R_{\max}}{\lambda_{0}(\lambda_{0}-4dL\epsilon)(1-\gamma)} \displaystyle\leq C_{1}\frac{dLR_{\max}\epsilon}{\lambda_{0}(\lambda_{0}-4dL\epsilon)(1-\gamma)}, (D.11) where we used the fact that \lambda_{0}\leq 1 and C_{1} is a positive constant. Combined D.11 with Lemma 7 in Hu et al. (2024) , we have \displaystyle P\left(\sup_{f}\|w_{f}^{T}\phi-\mathcal{T}f\|_{\infty}\geq\delta\right)\leq 6d\exp\left(-\frac{\lambda_{0}^{2}}{5184d^{2}(R_{\max}+\mathcal{B})^{2}}n\delta^{2}\right), (D.12) \displaystyle P\left(\sup_{f}\|\hat{w}_{f}^{T}\phi-w_{f}^{T}\phi\|_{\infty}\geq\frac{C_{1}dLR_{\max}\epsilon}{\lambda_{0}(\lambda_{0}-4dL\epsilon)(1-\gamma)}\right)\leq d\exp(-n\lambda_{0}/8). (D.13) Here we assume that there exists a positive constant C^{*} such that \mathcal{B}<\frac{C^{*}R_{\max}}{1-\gamma} since the optimal Q function is on the order of \frac{R_{\max}}{1-\gamma} and \|\phi\|_{\infty}\leq 1 . We also use the fact that d2\xi. (E.4) Under the event defined in \mathcal{A}_{0} , we have \displaystyle\max_{a}\hat{f}(s,a)-\max_{a^{\prime}\in A-\arg\max_{a}Q^{opt}(s,a)}\hat{f}(s,a^{\prime})>0, and hence \displaystyle\{a\in\mathcal{A}:\hat{\pi}(a|s)=1\}\subseteq\arg\max_{a\in\mathcal{A}}Q^{opt}(s,a). Thus, we have \displaystyle\|\hat{\pi}(s)-\pi^{*}(s)\|_{2}=0. Let \mathbb{S} denote the set of s that satisfies equation E.4 . It follows that \displaystyle\int_{s}\|\hat{\pi}(s)-\pi^{*}(s)\|_{2}\mathbb{I}(\mathcal{A}_{0})\mathbb{P}(ds) \displaystyle= \displaystyle\int_{x}\|\hat{\pi}(s)-\pi^{*}(s)\|_{2}\mathbb{I}(\mathcal{A}_{0})\mathbb{I}(s\in\mathbb{S}^{c})\mathbb{P}(ds) \displaystyle\leq \displaystyle\int_{s}\mathbb{I}(s\in\mathbb{S}^{c})\mathbb{P}(ds) \displaystyle= \displaystyle(2\xi)^{\alpha} (E.5) Bound \mathbb{E}\|\hat{\pi}(\hat{s}_{z})-\pi^{*}(\hat{s}_{z})\|_{2} : Using similar idea for \mathbb{E}_{s}\|\hat{\pi}(s)-\pi^{*}(s)\|_{2} , we have \displaystyle\mathbb{E}\|\hat{\pi}(\hat{s}_{z})-\pi^{*}(\hat{s}_{z})\|_{2}\leq(2\xi)^{\alpha} (E.6) Bound \mathbb{E}\|\pi^{*}(\hat{s}_{z})-\pi^{*}(s)\|_{2} : By definition of \epsilon , we have \max_{s}\|\hat{s}_{z}-s\|\leq\epsilon . For any s\in S , suppose \displaystyle\max_{a}Q^{opt}(s,a)-\max_{a^{\prime}\in A-\arg\max_{a}Q^{opt}(s,a)}Q^{opt}(s,a^{\prime})>2L\epsilon. (E.7) We have \displaystyle\max_{a}Q^{opt}(\hat{s}_{z},a)-\max_{a^{\prime}\in A-\arg\max_{a}Q^{opt}(s,a)}Q^{opt}(\hat{s}_{z},a^{\prime})>0. (E.8) Thus we have \displaystyle\|\pi^{*}(\hat{s}_{z})-\pi^{*}(s)\|_{2}=0. Let \mathbb{S} denote the set of s that satisfies equation E.7 . It follows that \displaystyle\mathbb{E}_{\hat{s}_{z}}\left[\int_{s}\|\pi^{*}(\hat{s}_{z})-\pi^{*}(s)\|_{2}\mathbb{P}(ds)\right] \displaystyle= \displaystyle\mathbb{E}_{\hat{s}_{z}}\left[\int_{x}\|\pi^{*}(\hat{s}_{z})-\pi^{*}(s)\|_{2}\mathbb{I}(s\in\mathbb{S}^{c})\mathbb{P}(ds)\right] \displaystyle\leq \displaystyle\mathbb{E}_{\hat{s}_{z}}\left[\int_{s}\mathbb{I}(s\in\mathbb{S}^{c})\mathbb{P}(ds)\right] \displaystyle= \displaystyle(2L\epsilon)^{\alpha}. (E.9) Combined all the results together, we have \displaystyle P\left\{\mathbb{E}\|\hat{\pi}(\hat{s}_{z^{\prime}})-\hat{\pi}(\hat{s}_{z^{\prime\prime}})\|_{2}\leq 2^{\alpha+1}\xi^{\alpha}+2^{\alpha}(L\epsilon)^{\alpha}\right\}\geq 1-n^{-\kappa}-d\exp(-n\lambda_{0}/8). (E.10) ∎ F Details on numerical experiments F.1 Implementation details To implement the Algorithm , we use a neural network with [64,64] hidden layer to approximate the transition kernels. The transition kernels are fitted separately for each value of the sensitive attribute to account for potential heterogeneity. Alternative machine learning models can be used to fit the transition kernels depending on the specific characteristics of their data and application domain. The models are fitted using a learning rate of 0.005 , a batch size of 512 , and a maximum of 1000 epochs. We use the mean squared error as the loss function. To prevent overfitting, the dataset was split into training and testing sets with an 80/20 ratio. Early stopping was implemented to terminate training if the test loss did not improve by more than 0.01 for a consecutive period of 10 epochs. We adopt fitted Q iteration (FQI) algorithm for offline policy learning. The Q-functions are modeled by neural network with a single hidden layer [32] . The FQI algorithm is trained for 100 iterations, and within each iteration, the network was optimized for 500 gradient descent steps using a learning rate of 0.1 . The Adam optimizer ( Kingma & Ba, 2015 ) is used throughout the experiments. The experiments are conducted on an internal cluster with 60-core Intel Xeon Gold 6230 CPU clocked at 2.10 GHz and 192 GB memory. A discount factor of \gamma=0.9 is used across all experiments. F.2 Synthetic data F.2.1 Data generating mechanism for linear setting \displaystyle S_{1} \displaystyle=-0.3+1.0\delta Z+U_{S_{1}}, \displaystyle S_{t} \displaystyle=-0.3+1.0\delta(Z-0.5)+0.5S_{t-1}+0.4(A_{t-1}-0.5)+0.3S_{t-1}(A_{t-1}-0.5) \displaystyle+0.3\delta S_{t-1}(Z-0.5)+0.4\delta(Z-0.5)(A_{t-1}-0.5)+U_{S_{t}}, \displaystyle R_{t} \displaystyle=-0.3+0.3S_{t}+0.5\delta Z+0.5A_{t}+0.2\delta S_{t}Z+0.7S_{t}A_{t}-1.0\delta ZA_{t}, where U_{S_{t}}\sim\mathcal{N}(0,1) , Z takes a binary value in \{0,1\} with equal probability. Behavior policy is set as \mathbb{P}(A_{t}=1\mid Z)=\text{expit}(-1.39+2.77Z) . \delta is used to control the impact of sensitive attribute on state variables. When \delta=0 , the state variables \{S_{t}\}_{t\geq 1} are independent of sensitive attribute Z ; the effect of Z on \{S_{t}\}_{t\geq 1} increases as \delta increases. F.2.2 Data generating mechanism for non-linear setting \displaystyle S_{1} \displaystyle=-0.7+0.8Z+U_{S_{1}}, \displaystyle S_{t} \displaystyle=-1.0+0.8\delta Z+0.25(\sin{S_{t-1}}+\cos{S_{t-1}})+0.4(A_{t-1}-0.5) \displaystyle+0.15(\sin{S_{t-1}}+\cos{S_{t-1}})(A_{t-1}-0.5) \displaystyle+0.15\delta(\sin{S_{t-1}}+\cos{S_{t-1}})Z+0.4\delta Z(A_{t-1}-0.5)+U_{S_{t}}, \displaystyle R_{t} \displaystyle=-0.2+0.3S_{t}+0.8\delta Z+0.8A_{t}-0.6\delta S_{t}Z-0.7S_{t}A_{t}-1.6\delta ZA_{t} where U_{S_{t}}\sim\mathcal{N}(0,1) , Z takes a binary value in \{0,1\} with equal probability. Behavior policy is set as P(A_{t}=1\mid Z)=\text{expit}(-1.39+2.77Z) . F.3 Semi-synthetic data To mimic the characteristics of real-world data, we first use the data from PowerED study to learn a generative model. The set of state variables S_{t} consists of weekly pain score and interference at week t . The reward R_{t} is defined as the weekly 7 - weekly self-reported opioid medication risk score . The action A_{t} is a ternary variable, including a brief motivational interactive voice response (IVR) call (less than 5 minutes), a longer IVR call (5 to 10 minutes), or a live call with counselor (20 minutes). The sensitive attribute is univariate: gender, age, ethnicity, or education. We binarize these sensitive attributes for convenience. In this paper, we choose to focus on the sensitive attributes one at a time instead of multivariate, because the latter, although theoretically possible, makes counterfactual state estimation more challenging given limited sample size. In addition, the univariate approach is standard in the current literature as it isolates the role of each sensitive attribute. To account for potential heterogeneity of transition functions among different sensitive attribute groups, for each sensitive attribute group z , we fit a separate model P(S_{t+1},R_{t}|S_{t},A_{t},Z=z) , which follows a multivariate normal distribution with mean \mu_{z}(S_{t},A_{t}) and diagonal covariance matrix \Sigma_{z} . We use a neural network with [32,32] structure to approximate each \mu_{z}(S_{t},A_{t}) for z\in\mathcal{Z} ; the diagonal elements of \Sigma_{z} are estimated using the residual variance of each component. G More on real data analysis In order to calculate the CF metric for each approach, we use the generative model described in Section to generate the states and rewards in the counterfactual world. Please refer to Appendix F.3 for more details on the generative model. Then we apply each method on the factual and counterfactual worlds separately, and calculate the CF metric defined in Section . We use fitted Q evaluation (FQE) to evaluate the value for each policy. A neural network with hidden layer [32] is used to model the Q function. The FQE algorithm is trained for 100 iterations, and within each iteration, the network was optimized for 500 gradient descent steps using a learning rate of 0.1 . The Adam optimizer is used for optimization. Figure G.2: Percentage of favoring actions against another sensitive groups for age, education, ethnicity and gender identity.