Asymptotic Theory for IV-Based Reinforcement Learning with Potential Endogeneity

Asymptotic Theory for IV-Based Reinforcement Learning with Potential Endogeneity

Introduction

With the advancement of digital technology, data-based management has become increasingly popular. Human resource departments now use data analytics for recruitment, performance evaluation, promotion decisions, and terminations. Marketing teams optimize digital advertising campaigns using objective metrics like viewer counts and click-through rates. Operations managers leverage historical data to forecast demand, manage inventory, design worker incentives, and implement dynamic pricing strategies.

The typical data-based management paradigm assumes, implicitly, that the data is collected, once and for all, and then data analysis is carried out, and the decision is made. Increasingly, however, these decisions are made frequently, and they affect the generation of future data. When data generation and data analysis interact dynamically, how are the results of the data analysis affected in the long run? In particular, if the data collected is imperfect and contains various types of biases---omitted variable, measurement error, model misspecification, selection, and simultaneous equations, how are the magnitude of the biases affected by the dynamic interaction? And what can be done to correct these biases?

These challenges are increasingly relevant as algorithms begin to govern workplace and social interactions. Consider online delivery platforms such as Meituan and Uber Eats, where algorithms assist managers in determining appropriate incentive schemes for riders. The primary objective for these companies is to select an incentive structure that maximizes long-term value. However, measuring this long-term value poses significant difficulties, as many benefits—and costs—are realized in the future. Consequently, companies rely on an imperfect set of metrics, typically encompassing key performance indicators (KPIs) such as delivery time, short-term profit, gross merchandise value, and customer satisfaction ratings. Based on these KPIs, managers decide the extent to which rider compensation is linked to performance metrics.

A frequently discussed issue in this context is the potential for gaming performance metrics HolmstromMilgrom91. Workers may engage in behaviors that artificially enhance their performance indicators. Thus, the performance metrics not only reflect an imperfect measure of true long-term value of the firm due to classic measurement-error problems but also because riders have the capacity to manipulate outcomes. More critically, the extent to which riders can influence these metrics is directly related to the strength of the incentives provided.

For instance, when riders receive a strong incentive to perform well, they may encourage customers to provide favorable ratings. In such cases, while customers may leave positive feedback, their actual satisfaction with the service could be low, potentially leading to decreased platform usage over time. Generally speaking, stronger incentives push riders to take actions that can create negative externalities, thus diminishing the firm's overall value.

In summary, heightened incentive strength exacerbates the measurement problem by widening the gap between measured performance and true performance. This misalignment means that the measured performance consists of the firm's actual long-term reward plus an error term that varies with the chosen incentive level. This scenario introduces a novel form of measurement challenge, further complicated by the fact that incentive strength is frequently adjusted based on historical performance metrics.

Specifically, consider a scenario where the manager implements such an optimal incentive policy that increases with the platform's monthly active users (MAUs). When the manager performs a regression analysis of short-term KPIs against incentive levels using historical data, the estimated effectiveness of incentives shows an upward bias, possibly because of rider's incentive to influence the performance metric.

This upward bias leads the manager to conclude that the current incentive policy is suboptimal, prompting an increase in per-rider incentives. Under this updated policy, new data is generated and analyzed. The analysis of these new data may again suggest that the updated policy is suboptimal, triggering further policy adjustments.

Note that the manager serves dual roles as both data analyst and data generator. As an analyst, she estimates the effectiveness of platform incentives using historical data. As a generator, she uses these estimates to determine future incentive levels. This process continues ad infinitum and stops only when the estimated effectiveness parameter becomes consistent with the parameter guiding the incentive policy---reaching a fixed point.

Being a fixed point, however, is not the same as being the actual parameter. This paper demonstrates that additional biases arise when data generation and analysis interact. The additional bias arises because the biases from the previous analysis affect the new data generated and can amplify the original bias in a fashion similar to the multiplier effect in macroeconomics. We denote such bias as the reinforcement bias (R-bias).

To study this new bias and how to correct it, we consider a Markov decision process (MDP) in which an agent makes a sequence of decisions over time to maximize her discounted rewards. In each period, the true reward is an unknown function of an observable current state variable and the agent's decision. However, the observed reward is biased. Based on the biased data, the agent makes decisions over time. Our findings are summarized as follows.

Main Contributions

First, we demonstrate the existence of the R-bias. We analyze an example where the state variables are Markovian, and the noise (in the observed reward) is correlated with the state variable or action. We calculate how the R-bias arise because of the interaction between learning and decision-making and illustrate how the Markovian structure amplifies the bias.

Second, we show how to correct this bias using an instrumental variable (IV) approach. We introduce IV-based reinforcement learning (RL) algorithms, IV-Q-learning and IV-AC, based respectively on two leading RL algorithms: Q-learning and Actor-Critic. Our use of IVs enables the agent to causally explore in her decisions. The notion of exploration in the conventional sense in RL algorithms helps the agent better learn about the rewards by choosing seemingly inferior actions. But when observed rewards are mis-measured and biased, knowledge from these explorations is also biased, leading to suboptimal policies. By contrast, by perturbing the data-generating process, our IV-based approach helps the agent identify true rewards and learn optimal policies. Notably, Bradtke96 applied instrumental variables to temporal-difference learning---a standard RL algorithm for policy evaluation with fixed policies---for bias correction and proved the algorithm's convergence. In this paper, we establish central limit theorems (CLTs) for more sophisticated algorithms like IV-Q-learning and IV-AC which involve policy improvement, thereby enabling inference on optimal policies.

Our third (and technical) contribution is to analyze IV-RL algorithms through the lens of stochastic approximation (SA) and establish general results concerning asymptotic performances of SA. In contrast to RL literature that usually assumes independent observations to exploit a martingale-difference structure in the SA formulation, we study SA with iterate-dependent Markovian structures (i.e., the underlying Markov chain has a transition distribution depending on the current SA iterate). The Markovian aspect is essential for many practical applications since the transition of state variables (e.g., the MAU in the incentive scheme design example) is typically better described as Markovian. And the iterate-dependent aspect is key to accommodating RL algorithms that feature policy improvement: state transitions depend on the policy used. We establish a CLT for SA under primitive assumptions. Applying the general result, we then develop inference methods for optimal policies of IV-RL algorithms. Our results highlight how intertemporal dependencies in the Markovian environment affect the inference. While KondaTsitsiklis03 provided convergence results for actor-critic algorithms, we focus on CLTs that characterize convergence rates and enable statistical inference. In addition, ChenWhite02 developed theory for SA with high-level conditions for general dependence structures, but our asymptotic theory uses more primitive conditions better suited for RL algorithms.

Related Works

Our paper contributes to methodological advances in RL. For a general introduction to RL, see SuttonBarto18; for applications in economics and finance, see Charpentier23 and Bai24. Despite extensive theoretical analysis of RL algorithms in recent years (see, e.g., BhandariRussoSingal21 and references therein), statistical inference on optimal policies remains significantly underexplored in the RL literature. We address this gap by establishing CLTs for the IV-RL algorithms.

Our problem setting---where adaptive data collection may involve biases from omitted variables, measurement error, and other sources---can be viewed through the lens of partially observable MDPs (POMDPs), in which state variables are only observed through noisy proxies. Although POMDPs can be converted to MDPs by introducing belief states to capture historical information about the original state variables, solving these resulting MDPs remains challenging due to the curse of dimensionality. For an introduction to POMDPs, see Krishnamurthy16, and for recent advances in RL algorithms for POMDPs, see Subramanian22approximate and references therein. Our paper potentially offers an alternative approach to addressing such problems.

Our paper also contributes to the literature on IV methods.\footnote{This is a vast literature, and we refer to Hausman83, Imbens94, and Chen05 for theoretical analyses of IVs in linear models, and refer to Hansen82, Ai03, Newey03, and Chernozhukov07 for the use of IVs in nonlinear models. See Imbens14 for a review on identification problems and the use of IVs in general.} Few existing works use IVs to learn the causal effect of a policy (rather than that of a single decision) in RL settings\footnote{Economists have recently been interested in the use of RL in business decision processes; see, e.g., BlakeNoskoTadelis15,CalvanoCalzolariDenicoloPastorello20,CowgillTucker20,LiRaymondBergman20 and JohnsonRhodesWildenbeest23. } or sequential decision-making problems in general.\footnote{Another approach to causal RL is based on “directed acyclic graph” (DAG) models. However, the DAG approach requires detailed domain knowledge of the causal relationships between states and actions, making it less applicable to economic problems with complex causal channels Imbens20.} One exception is Nambiar19. They study a dynamic pricing problem with contextual information, in which state variables are independent and the demand model is misspecified. They use random experiments to create IVs to identify optimal pricing policies. Unlike the present paper, they do not consider general IVs or Markovian environments. Another is LiLuoZhang21_bandit. They study a contextual bandit problem with biased reward observations and identify self-fulfilling bias, a selection-bias that stems from interactions with the decision-making environment. While the interactive nature makes self-fulfilling bias a particular type of R-bias, the methods they develop to correct it, IV-based standard bandit algorithms, cannot be converted into the form of SA and requires different analysis techniques. Another key difference is that the state variables in contextual bandit problems do not depend on previous actions SuttonBarto18. By contrast, a key focus of our paper is the intertemporal dependencies introduced by Markovian state transitions (through the impact of actions on future states): how they affect R-bias and the inference of IV-based RL algorithms. Notably, there are two papers related to use IV in the online learning environment: Bradtke96 discusses an least square IV approach for temporal difference learning, and provide results on converge rates. Chen23 discusses asymptotic theory for online 2SLS and Stochastic generalized method of moments.

Our paper also relates to the emerging literature on policy evaluation in adaptive experiments, e.g., through contextual bandit algorithms Bottou_etal13,HadadHirshbergZhanWagerAthey21,ZhanHadadHirshbergAthey21. This literature deals with a related bias due to insufficient sampling of certain actions in an adaptive data collection process ShinRamdasRinaldo19. Unlike the present paper, however, this bias is not caused by biased reward observations and is fixed differently, for example, by inverse propensity weighting. Another key difference is that this literature focuses on offline learning in which data is collected in advance and then fixed for subsequent analysis. By contrast, we consider an interactive decision-making environment where new data are continuously generated and optimal policies are learned in an online fashion.

The rest of the paper is organized as follows. Section (ref) presents an illustrative example of R-bias, followed by Section (ref) which introduces the IV-Q-learning algorithm. Section (ref) embeds this algorithm within the SA framework and establishes its theoretical properties. Section (ref) provides numerical evaluations of the IV-RL algorithms, Section (ref) introduces an empirical example of stock repurchase with analysis using IV-Q-learning, and Section (ref) concludes. The IV-AC algorithm and its theoretical analysis appear in the Appendix. The main theorems' proofs are provided in the Online Supplemental Material, while proofs of auxiliary results are available upon request.

Reinforcement Bias

Problem Setup

An agent is engaged in an infinite-horizon MDP with state space $\mathcal{S}$, action space $\mathcal{A}$, and a discount factor $\gamma\in[0,1)$. At each time $t=0,1,\ldots$, the agent observes the current state $S_t =s\in\mathcal{S}$ of the environment and follows a policy $\pi$ to take an action $A_t=a\in\mathcal{A}$. In general, the policy can be random; that is, for each $s\in\mathcal{S}$, $\pi(\cdot|s)$ is a probability distribution on $\mathcal{A}$ from which $a$ is sampled. Following the action $A_t=a$, a reward $r(s,a)\in \mathbb{R}$ is realized, and the state transitions to $S_{t+1} =s'$ with probability $\mathsf{P}(s'|s, a)\coloneqq \operatorname{\mathbb{P}}(S_{t+1} = s'|S_t=s, A_t=a)$. Given an initial state $s$, the goal of the agent is to learn an optimal policy $\pi^*$ that maximizes the expected cumulative discounted reward:

For a policy $\pi$, we define the state-action value function---the “Q-function”---as the expected cumulative discounted reward if the initial state-action pair is $(s,a)$ and the agent follows policy $\pi$ afterward: \[ Q^\pi(s,a) \coloneqq \operatorname{\mathbb{E}}_{A_t\sim\pi(\cdot|S_t):t\geq 1}\biggl[\sum_{t=0}^\infty \gamma^t r(S_t, A_t)\Big|S_0=s,A_0=a\biggr]. \] For simplicity, we write the optimal Q-function (i.e., the Q-function associated with $\pi^*$) as $Q^*(s,a)$. It is well known that $Q^*$ satisfies the Bellman optimality equation

where the expectation is taken with respect to $S' \sim \mathsf{P}(\cdot|s,a)$. Given $Q^*$, an optimal policy can be calculated via $\pi^*(s)=\operatorname*{argmax}_{a\in\mathcal{A}} Q^*(s,a)$ for all $s\in \mathcal{S}$.

The term “model” is typically used to refer to the state transition distribution $\mathsf{P}(\cdot|s,a)$ and the reward function $r(s,a)$. If both are known, one can directly solve the Bellman optimality equation---at least numerically, in principle---for the optimal policy via dynamic programming techniques, including value iteration and policy iteration BertsekasDP. This dynamic programming method is known as the “model-based” approach. However, in complex environments, the state transition distribution or the reward function are typically unknown, making dynamic programming method infeasible. One then resorts to RL methods, which are “model-free.” RL methods allow the agent to adjust her policies towards optimality without knowing the model specification SuttonBarto18.

In RL, the agent adjusts her policies based on observations of the state-action-reward tuple $(S_t, A_t, R_t)$, where $R_t \coloneqq r(S_t,A_t)+\epsilon_t$ is a noisy signal of the true reward. Standard RL methods assume that $R_t$ is unbiased, that is, $\operatorname{\mathbb{E}}[\epsilon_t|S_t,A_t] = 0$. This assumption is important for the agent's policies to converge to the optimal policy in the long run.

In many applications, however, the observed reward is biased, that is, $\operatorname{\mathbb{E}}[\epsilon_t|S_t,A_t]\neq 0$. In the platform incentive policy design example above, if the firm forgets to measure the indirect cost of over-incentivization, such as riders' safety and other externalities that may affect company's long run profit, then the observed reward becomes higher than the true reward. In addition, if the evaluator of the KPI design gains from its success, she may sugarcoat the data, again causing the observed reward to be higher. When $\operatorname{\mathbb{E}}[\epsilon_t|S_t,A_t]\neq 0$, because the agent adjusts her policies based on the biased observed reward, it creates a new bias, which we illustrate below.

An Illustrative Example of R-Bias

Consider an online delivery platform that designs rider incentive schemes each period to maximize its expected cumulative discounted reward. The problem takes the form of equation (ref), where $S_t$ represents the platform's MAUs and $A_t$ denotes the incentive strength such as performance bonus levels, delivery time targets, and associated bonuses or penalties.

Assume that the true reward function $r(S_t,A_t):=\theta^* S_t A_t - \frac{1}{2}A_t^2$, where $ \theta^* S_t A_t$ is the true long run profit, and $ \frac{1}{2}A_t^2$ is the hidden cost of externalities. Here, $\theta^*$ is an unknown parameter that measures the effectiveness of incentive. The product price is normalized to one so that $r(S_t, A_t)$ is the firm's reward in period $t$. The state transition takes the following form: $S_{t+1} = c_1 S_t + c_2 A_t +\eta_t$, where $c_i\geq 0$, $i=1,2$, and $\eta_t$ is random noise independent of $S_t$ and $A_t$ with mean $0$ and variance $\sigma_\eta^2$. The observed reward $R_t=r(S_t,A_t)+\epsilon_t$ and $\operatorname{\mathbb{E}}[\epsilon_t|S_t,A_t] = \beta A_t^2$ for some $\beta>0$. Namely, the observed reward is biased. (If $\epsilon_t$ is unbiased, this problem is a linear-quadratic optimal control problem BertsekasDP).

To show why a new form of bias arises from the platform adjusting its policies based on the observed reward, we first examine the simple case with $c_2=0$. That is, the platform's action $A_t$ does not affect the future states. If the action does affect future states ($c_2>0$), the magnitude of this new bias further increases, which we discuss later in this section.

If $c_2=0$, let us first assume that the platform uses a fixed linear policy $A_t = \theta_{\mathsf{pol}} S_t$, where $\theta_{\mathsf{pol}}$ is exogenously given and not necessarily the same as the true parameter value $\theta^*$. To estimate $\theta^*$, a common strategy is to regress $R_t + \frac{1}{2}A_t^2 = \theta^* S_t A_t + \epsilon_t$ on $S_t A_t$, provided that the cost $\frac{1}{2}A_t^2$ is known. The standard regression formula shows that, in the long run, the estimate of $\theta^*$ is given by

Therefore, the long-run bias of the estimate is $\beta\theta_{\mathsf{pol}}$. This bias reveals the endogeneity in the setting because the noise $\epsilon_t$ is correlated with the action taken. Notice that even if the platform chooses the optimal policy $A_t = \theta^* S_t$, such bias remains, and it equals $\theta^*+\beta\theta^*$.

Next, let the platform adjust its policy based on existing data. In particular, suppose the firm starts with a policy $A_t = \hat{\theta}_0 S_t$, for some $\hat\theta^0$. If this policy is used for an extended period of time, then following (ref) with $\theta_{\mathsf{pol}} = \hat\theta^0$, the estimate of $\theta^*$ from the data generated under this policy is given by $\hat{\theta}_{\mathsf{est},0} = \theta^* + \beta \hat\theta^0$.

Suppose the platform then uses this estimate as a guide and adjusts her policy to $A_t = \hat{\theta}_1 S_t$, where $\hat{\theta}_1 = \hat{\theta}_{\mathsf{est},0}$. After this adjusted policy is used for an extended period of time, the new estimate of $\theta^*$ is then given by $\hat{\theta}_{\mathsf{est},1} = \theta^* + \beta \hat{\theta}_1$. Continuing this process, the estimate of $\theta^*$ after $k$ iterations is given by \[ \hat{\theta}_{\mathsf{est},k} = \theta^* + \beta \hat{\theta}_{k-1} = \cdots = \theta^* + \beta \theta^* + \cdots + \beta^{k-2}\theta^* + \beta^{k-1}\hat{\theta}_0 \to \frac{\theta^*}{1-\beta}, \] as $k\to\infty$, provided that $\beta \in (-1,1)$. We call $\frac{\theta^*}{1-\beta} - \theta^* = \frac{\beta \theta^*}{1 - \beta}$ the R-bias. More generally, we use R-bias to refer to the additional bias that arises because the agent adjusts her policy.

The R-bias can also be calculated via a fixed-point argument. Suppose the long-run policy converges to $A_t = \hat{\theta} S_t$. Then, consistency between the estimate and the decision requires $\operatorname{\mathrm{plim}} \hat\theta_{\mathsf{static}}(\hat{\theta}) = \hat{\theta}$, i.e., $\theta^* + \beta \hat{\theta} = \hat{\theta}$. This implies that $\hat{\theta} = \frac{\theta^*}{1-\beta}$, which, again, gives the same R-bias.

Above, we demonstrate the emergence of R-bias when $c_2=0$. When $c_2>0$ (so that the high incentive scheme increases service quality and therefore, the number of future users), R-bias also arises, although its value is more involved to calculate. Table (ref) shows numerical values of R-bias for different values of $c_2$ and $\beta$. Notice that R-bias is increasing in $c_2$, suggesting that the Markovian dependence structure may amplify the R-bias.

We conclude this section with several remarks. First, the state variable (the MAUs) can depend on the last period's action, i.e., the incentive scheme, since service quality affects future MAUs while the incentive scheme affects the service quality. As the decision-maker adjusts her policy, the transition of the state variable is also affected. In this sense, the stochastic environment of the example, and many economic and business problems in general, is iterate-dependent Markovian, i.e., the transition distribution of state variables iteratively changes in response to policy adjustments.

Second, the noise in the observed reward can depend on the state-action pair in various ways. In the platform incentive design example, the noise $\epsilon_t$ correlates only with the action $A_t$, and the dependence structure takes a specific form. In general, the noise can also correlate with the state variable $S_t$.\footnote{To see how the R-bias may arise when the noise is correlated with the state variable, suppose, for example, that $S_{t+1} = c_1 S_t + \eta_t$ and $ \epsilon_t = \beta S_t^2 + o_t, $ where, again, $\eta_t$'s and $o_t$'s are i.i.d. random variables with mean zero. If the firm uses a policy $A_t = \tilde\theta S_t$, the standard regression formula implies that the long-run estimate of $\theta$ is given by $ \operatorname{\mathrm{plim}} \hat\theta_{\mathsf{static}} (\tilde \theta) = \theta^* +\frac{\operatorname{Cov}(S_t A_t, \epsilon_t)}{\operatorname{Var}(S_t A_t)} = \theta^* + \frac{\operatorname{Cov}(\tilde\theta S_t^2,\beta S_t^2)}{\operatorname{Var}(\tilde\theta S_t^2)} = \theta^* +\frac{\beta}{\tilde\theta}. $ Consequently, to calculate the estimate of $\theta$ in the interactive environment, the fixed-point argument used earlier implies that the long-run estimate should satisfy $\theta^* + \frac{\beta}{\hat\theta} = \hat\theta$. Thus, the R-bias is given by $\hat\theta - \theta^*=\frac{1}{2}(\sqrt{(\theta^*)^2+4\beta}-\theta^*)$.} The method and theory developed in this paper allow the noise to be correlated with $S_t$ and $A_t$ simultaneously with a general dependence structure.

Finally, while we demonstrate R-bias in a simple example, R-bias also arises in complex MDPs with state transitions and reward functions unknown to the agent, and the policy of the agent is updated over time. Therefore, when applying RL methods to these complex MDP problems, the resulting “optimal policies” are also subject to R-bias. The rest of the paper discusses how to incorporate IVs into RL methods to correct the bias.

IV-Q-learning Algorithm

In this section, we first introduce Q-learning, a standard RL algorithm, and then describe how to incorporate IVs into it. We will also discuss how to incorporate IVs into Actor-Critic, another standard RL algorithm, in the Appendix.

Q-learning

Q-learning WatkinsDayan92 is an iterative algorithm that incrementally estimates the long-term discounted reward and, through doing so, identifies the best action for each state. A random behavior policy $\pi$ is fixed\footnote{The behavior policy is fixed to facilitate theoretical analysis of Q-learning, a standard treatment in RL literature. Practical implementations of Q-learning often allow the behavior policy to be “improved” based on the current estimate of the optimal Q-function SuttonBarto18. The improved behavior policy has the advantage of generating data that bears a closer resemblance to the data that the optimal policy would generate, making the subsequent estimation of the optimal Q-function more efficient. However, these modifications lack convergence guarantees from a theoretical viewpoint CalvanoCalzolariDenicoloPastorello20. In this paper, we do not examine policy improvement in Q-learning, but rather in Actor-Critic for which the behavior policy is constantly adjusted.} to generate data from which the algorithm learns optimal policies. Suppose, for now, that the state and action spaces are both finite. The optimal Q-function $Q^*$ then takes the form of a look-up table representation; that is, its information can be stored in a matrix, where the entry indexed by $(s,a)$ is $Q^*(s,a)$.

In each period $t$, the agent observes the state $S_t$, selects action $A_t$ according to policy $\pi$, observes an immediate reward $R_t$ and the subsequent state $S_{t+1}$, and finally, updates the estimate of $Q^*$ according to

for all $s\in\mathcal{S}$ and $a\in\mathcal{A}$, where $\mathbb{I}$ denotes the indicator function. Equation (ref) implies that if $ (s,a) \neq (S_t, A_t)$, the estimate of $Q^*(s,a)$ is unchanged: $\widehat{Q}_{t+1}(s,a) = \widehat{Q}_t(s,a)$. For $(s,a)=(S_t, A_t)$, the updated value $\widehat{Q}_{t+1}(s,a)$ is a weighted average of the previous value $\widehat{Q}_t(s,a)$ and $R_t+\gamma \max_{a' \in \mathcal{A}} \widehat{Q}_t(S_{t+1}, a')$, which is the sum of the observed immediate reward and the best that the agent thinks she can do from the subsequent state $S_{t+1}$. The weight $\alpha_t$ is the learning rate that affects the speed of convergence. With this updating rule, $\widehat{Q}_t$ converges to $Q^*$, provided that the behavior policy permits the agent to visit each state-action pair infinitely often WatkinsDayan92.

This “tabular” Q-learning algorithm, where Q-functions can be represented by a table indexed by state-action pairs, extends naturally to infinite and continuous state-action spaces. Assume the value function $Q^*(s,a)$ lies in the linear span of $\phi(s,a)\coloneqq (\phi_1(s,a),\ldots,\phi_p(s,a))^\intercal$, a vector of $p$ appropriately chosen basis functions, such that $Q^*(s,a) = \phi(s,a)^\intercal \theta^*$ for some unknown parameter $\theta^*\in \mathbb{R}^p$. Then, one learns $Q^*(s,a)$ through $\theta^*$ by iteratively updating its estimate $\theta_t$. To understand this update, consider the original Q-learning update rule (ref), where the estimate $\widehat{Q}_t$ moves toward $Q^*$ in the direction of $\Delta_t I(S_t,A_t)$. Here, \[\Delta_t\coloneqq R_t + \gamma \max_{a' \in \mathcal{A}} \widehat{Q}_t(S_{t+1}, a') - \widehat{Q}_t(S_t, A_t),\] and $I(S_t, A_t)$ denotes a matrix of indicator functions $\mathbb{I}{{(S_t, A_t) = (s,a)}}$ for all $(s, a)$.

Following this principle, we update $\theta_t$ by stepping in the direction of $\Delta_t \nabla_{\theta}\widehat{Q}_t(S_t, A_t) = \Delta_t \phi(S_t, A_t)$, yielding:

When indicator functions serve as basis functions (mapping each state-action pair to a basis function), equation (ref) reduces to (ref).

In this paper, we study inference on $\theta_t$. Under the linear model, the optimal policy, derived from the optimal Q-function, is $\pi^*(s) = \operatorname*{argmax}_{a\in\mathcal{A}} \phi(s,a)^\intercal \theta^*$. This allows us to draw inference on both the estimated optimal policy $\operatorname*{argmax}_{a\in\mathcal{A}} \phi(s,a)^\intercal \theta_t$ and its associated value function $\phi(s,a)^\intercal \theta_t$.

Consider the platform incentive design example, we can select the basis functions as $\phi(s,a) = (1,s,a, sa, s^2, a^2)^\intercal$ for which $Q^*(s,a) = \phi(s,a)^\intercal \theta^*$ with $\theta^* \in \mathbb{R}^5$. Then, $\phi(S_{t+1},a')^\intercal\theta_t$ is a quadratic function in $a$ and thus can be easily maximized. One can then update the estimate of $\theta^*$ according to (ref). Notice that the basis functions $\phi(s,a)$ are non-linear in $(s,a)$, we can estimate the heterogeneous treatment effect $\Delta Q^*(s):=Q^*(s,1)-Q^*(s,0)$ using the estimate of $Q^*$ if the action $a$ is binary.

Incorporating IVs into Q-learning

We now describe and motivate an IV-based approach to address the endogeneity issue in RL algorithms when the observed rewards are biased. Under the updating rule (ref), the policies converge to a limit that satisfies

When the observed reward $R_t = r(S_t, A_t) + \epsilon_t$ is unbiased, i.e., $\operatorname{\mathbb{E}}[\epsilon_t|S_t, A_t]=0$, the limiting policy satisfies the projected Bellman optimality equation (ref). When the observed reward is biased, i.e., $\operatorname{\mathbb{E}}[\epsilon_t|S_t, A_t]\neq 0$, an extra term $\operatorname{\mathbb{E}}_{\nu}[\epsilon_t \phi(S_t, A_t)]$ appears, causing the limiting policy from Q-learning to differ from the optimal policy. Similar problems also occur to the Actor-Critic algorithm as shown in Appendix (ref).

To address the problem, note that equation (ref) is in the form of $\operatorname{\mathbb{E}}[(Y_t - X_t^\intercal \theta) X_t] =0$. This is similar to the moment condition for estimating a linear regression model via OLS, except here, the “dependent variable” $Y_t$ and the “explanatory variables” $X_t$ are generated from an MDP. When there is endogeneity problem in OLS, a standard approach is to introduce instrument variables and correct the bias via 2SLS. This motivates the following bias-correcting idea that is akin to 2SLS.

Specifically, let $Z_t$ be a vector of IVs so that $Z_t$ is correlated with $\phi(S_t, A_t)$ but uncorrelated with $\epsilon_t$. Following the idea of 2SLS, we first use OLS to regress $\phi(S_t, A_t)$ on $Z_t$ to estimate the projection matrix $\theta_{\mathsf{I}}^*$, which satisfies the equation

where $\nu$, with a slight abuse of notation, is the stationary distribution of $(S_t,A_t,Z_t)$. We then use the projected value $\theta_{\mathsf{I}}^* Z_t$ in lieu of $\phi(S_t,A_t)$ in equation (ref) so that the aforementioned extra term $\operatorname{\mathbb{E}}_{\nu}[\epsilon_t \phi(S_t, A_t)] = \operatorname{\mathbb{E}}_{\nu}[\epsilon_t \theta_{\mathsf{I}}^* Z_t] = 0$. This reduces equation (ref) to the projected Bellman optimality equation (ref), thereby solving the endogeneity problem.

In the context of Q-learning, this idea leads to the following procedure. First, we apply SA (see Section (ref) for its definition) to solve equation (ref), which yields the updating rule for $\theta_{\mathsf{I},t}$ as an estimate of $\theta_{\mathsf{I}}^*$:

where $A_t$ is generated by the behavior policy $\pi$ of Q-learning. Having an estimate of $\theta_{\mathsf{I}}^*$ in period $t$, we modify the updating rule (ref) so that the updating is done in the direction of $\theta_{\mathsf{I},t} Z_t$ rather than $\phi(S_t, A_t)$. Specifically,

where the subscript $\mathsf{Q}$ indicates quantities associated with Q-function approximation.

The detailed updating rules for IV-Q-learning are presented in Algorithm (ref). The algorithm incorporates two features that are standard in machine learning but may be unfamiliar to economists.

First, the algorithm permits the use of minibatches, that is, the parameters are updated once every $B$ time periods (where $B$ can be finite or increase with time horizon $T$). Within each minibatch, a total number of $B$ state transitions occur, and the resulting state-action-reward tuples are recorded to provide a more accurate updating direction. The use of minibatches, therefore, helps stabilize the convergence of algorithms and is commonly used in RL in practice SuttonBarto18.

Second, the algorithms contain a projection step, defined as $\Pi_{\Theta}(\theta)\coloneqq \operatorname*{argmin}_{\tilde{\theta}\in \Theta } \|\theta-\tilde{\theta}\|$, between parameter updates. Widely used in practice KushnerYin03, it prevents occasional large random fluctuations in the wrong direction in early iterations, in which case it may take the iterates a long time to return to a convergent trajectory.

Let $\{\theta_{\mathsf{Q}}^*, \theta_{\mathsf{I}}^*\}$ be the limit of the IV-Q-learning algorithm, when it converge. We will show in Section (ref) that for Algorithm (ref), $\{\theta_{\mathsf{Q}}^*, \theta_{\mathsf{I}}^*\}$ satisfies

where $\nu$ is the stationary distribution of $(S_t,A_t,Z_t)$ induced by the behavior policy $\pi$.

IVs in MDP Settings

Returning to the platform's incentive design example: $S_t$ represents the platform's MAUs in period $t$. Endogeneity can arise when the platform fails to account for externalities generated by the incentive scheme (the action). Valid IVs in this context are factors that influence website traffic and MAUs without directly affecting rider incentive schemes. For instance, platforms can leverage Google Ads rankings as a source of exogenous variation in MAUs. Additionally, platforms can introduce controlled variations in website traffic through randomized control trials (RCTs), such as A/B testing of website design elements.

While IVs may appear similar to “exploration” in RL algorithms, their functions are fundamentally distinct. Exploration means that the agent takes suboptimal actions to collect better information. The use of IVs, instead, perturbs the data-generating process. In the platform incentive design example, standard exploration is about choosing a suboptimal spending level, and causal exploration is about perturbing the number of visitors to the website. With biased observed rewards, exploration alone still results in suboptimal policies. When rewards are biased, the key to identify the optimal policies is to perturb the data-generating process, i.e., doing “causal exploration”.

Our approach reveals a novel application for business experiments and RCTs. The existing emphasis of RCTs has been on helping compare alternative choices directly related to the experiment; see AtheyImbens17 for a review. In our framework, however, RCTs also provide an exogenous shock that perturbs the data-generating process. In other words, RCTs can play the role of carrying out casual exploration and help identify parameters not directly related to RCTs.

Theoretical Analysis via Stochastic Approximation

In this section, we analyze SA methods in a general environment and then apply the results to the IV-RL algorithms. Because of the technical nature of the analysis, we first provide an overview of the main results in Section (ref). The formal statement of the assumptions, results, and the discussion of the proof techniques are contained in later subsections.

Overview of Main Results

We analyze a general formulation encompassing both IV-Q-learning and IV-AC (see Appendix (ref)) as special cases. Both algorithms can be expressed as SA iterations that solve equations of the form $\operatorname{\mathbb{E}}[G(W,\theta)] = 0$, where $W$ is a random variable with support $\mathcal{W}$, $\theta\in\mathbb{R}^d$ is an unknown parameter of interest, and $G: \mathcal{W}\times \mathbb{R}^d\mapsto \mathbb{R}^d$ is a deterministic function. We consider the following general form of SA that permits projection and minibatch-updating:

where $\alpha_k \propto k^{-\delta}$ for some $\delta\in (\frac{1}{2}, 1]$,\footnote{This choice of learning rate is standard in RL literature. Other values of $\delta$ typically make the algorithm diverge.} $W_t$ is a random variable approximating $W$ in distribution and $M_k$ is a residual term that arises to account for the estimation error of $\theta_{\mathsf{I}}^*$.

For example, the IV-Q-learning algorithm aims to solve equation (ref). In addition, if $\theta_{\mathsf{I}}^*$ is known,\footnote{When $\theta_{\mathsf{I}}^*$ needs to be estimated, replacing $\theta_{\mathsf{I}}^*$ with $\theta_{\mathsf{I},k}$ introduces additional terms that are absorbed by $M_k$; see Appendix (ref) for details.} the update rule for $\theta_{\mathsf{Q},k}$ is reduced to the form of (ref) with $\theta_k=\theta_{\mathsf{Q},k}$, $\alpha_k = \alpha_{\mathsf{Q},k}$, $W_t = (S_t, A_t, R_t, Z_t, S_{t+1})$, $M_k = 0$, and

Our first main result (Theorem (ref) in Section (ref)) establishes the asymptotic normality of $\theta_k$: with $\rightsquigarrow$ denoting weak convergence,

for some positive definite matrix $\Gamma^*$ that is increasing in a measure (described in Section (ref)) of the intertemporal dependency of the Markov chain $\{G(W_t,\theta^*):t\geq 0\}$, provided that $B/T^\frac{\delta}{1+\delta}\rightarrow 0$ as $T\to\infty$. (This condition means $B$ either is fixed or does not grow too fast relative to $T$, because otherwise $\theta_k$ would not be updated enough times.)

The CLT (ref) differs from previous convergence rate analyses of SA KushnerYin03,KondaTsitsiklis04,mokkadem2006 in two aspects. First, our result accommodates the use of minibatches and characterizes its effect on the convergence rate. Second, our analysis extends the existing studies by allowing the environment to be iterate-dependent Markovian. This extension accommodates applications where the state variables---such as MAUs in our platform incentive design example---are Markovian (instead of i.i.d.) because they are affected by the past (through, for example, customer stickiness). Moreover, by allowing the Markovian structure to be iterate-dependent, our analysis accommodates settings where the behavior policies from RL algorithms improve over time, enabling adaptive data collection. This is a common feature in practice, especially when the state space is large. Without policy improvement and adaptive data collection, the costs associated with identifying the optimal policy can be prohibitive Bottou_etal13.

Our second main result involves applying Theorem (ref) to IV-Q-learning. As we focus on IV-Q-learning in the maintext, a set of result in the Appendix (ref) is available for the IV-Actor Critic (AC) algorithm. Corollary (ref) (Section (ref)) and Corollary (ref) (Appendix (ref)) show that the two algorithms eliminate the R-bias under conditions that correspond to those in Theorems (ref). These results also allow us to make inferences on the optimal policy $\pi^*$ and its value function $Q^*$. This contrasts with prior studies on policy evaluation with adaptively collected data that focus on the inference of the value function $Q^\pi$ of a given policy $\pi$ HadadHirshbergZhanWagerAthey21,ZhanHadadHirshbergAthey21, especially for the case of the IV-AC algorithm.

Key Assumptions

We now describe and discuss the assumptions used in Theorem (ref), starting with those related to the stochastic environment.

Before discussing Assumption (ref) in detail, we note that if $\mathsf{P}_\theta$ is independent of $\theta$ (i.e., $\mathsf{P}_\theta \equiv \mathsf{P}$ for some $\mathsf{P}$)---which responds to the situation where the behavior policy of an RL algorithm is fixed such as Q-learning---then Assumption (ref) is simply reduced to that $W_t$ is a geometrically ergodic (with respect to $U$) Markov chain. (In this case, condition (ref) becomes redundant and is no longer needed.) Loosely speaking, this assumption states that the Markov chain $W_t$ admits a unique stationary distribution $\nu$, and the $t$-step transition distribution induced by $\mathsf{P}$ converges to $\nu$ at an exponential rate of $t$. This is a standard condition for analyzing general state-space Markov chains MeynTweedie09.

To accommodate adaptive behavior policies, Assumption (ref) extends the condition above as follows. Assumption (ref)(ref) defines the iterate-dependent Markovian structure: the Markov chain transition depends on the policy. Assumption (ref)(ref) is a technical condition requiring uniform geometric ergodicity of $\mathsf{P}_\theta$ across $\theta$, which is also used in KondaTsitsiklis03 to prove convergence of standard AC algorithms. A key implication of this condition is that $\mathsf{P}_\theta$ possesses a unique stationary distribution $\nu_\theta$ for each $\theta$. Assumption (ref)(ref) is a Lipschitz condition that guarantees the behavior policies are updated gradually by the step of policy improvement. Assumption (ref)(ref) regularizes the tails of multi-step transition distributions to ensure that, loosely speaking, when the data-generating process is changing, the data $W_t$ may still converge to a stationary distribution.

Next, we state the conditions on $G(W,\theta)$ in (ref) and $\bar{G}(\theta)\coloneqq \operatorname{\mathbb{E}}_{\nu_\theta}[G(W,\theta)] $. These conditions are the standard regularity conditions in SA but are stated at a general level. In Section (ref), we discuss how to translate these conditions to specific conditions on the primitives (reward function and so on) for specific RL algorithms.

Assumption (ref) lists the common linear growth and the Lipschitz conditions. Assumption (ref)(ref) is a standard, albeit strong, condition for theoretical analysis of SA KushnerYin03. Although we only require $\bar{G}(\theta)$ to have a unique root in the subset $\Theta$ rather than in all of $\mathbb{R}^d$, identifying such a region a priori may still pose practical challenges for practitioners. Extending our theory to cases without solution uniqueness in $\Theta$ lies outside this paper's scope and is left for future research. Assumption (ref)(ref) is a classical condition NevelsonHasminskii76 that guarantees $\bar{G}$ is a contraction mapping. Finally, Assumption (ref)(ref) enables Taylor's expansion of $\bar{G}$ around $\theta^*$, a standard condition for establishing CLTs for nonlinear SA mokkadem2006.

Finally, we describe the condition on the residual term $M_k$ in equation (ref).

Assumption (ref) ensures that the residual term $M_k$ from the proposed IV-RL algorithms vanishes sufficiently fast so that its effect on the rate of convergence of $\theta_k$ is asymptotically negligible relative to the learning rate $\alpha_k$. Note that $M_k$ is similar in form to the residual term in the classical Kiefer--Wolfowitz algorithm, which accounts for the error caused by using finite differences to estimate gradients. We stress that it is crucial to allow the residual term $M_k$ in the analysis of iterate-dependent Markovian process such as the Actor-Critic algorithm. For details, see Appendix (ref).

Asymptotic Normality

To prove the asymptotic normality, we follow a common, martingale method: (i) Express $(\theta_{\lfloor T/B \rfloor} - \theta^*)$ as the sum of a martingale and a remainder term, (ii) invoke a martingale CLT, and (iii) show the remainder term is asymptotically negligible. However, steps (ii) and (iii) require calculating moments of various orders of $G(W_t, \theta_k)$, and the iterate-dependent Markovian structure dramatically complicates these calculations.

Our key idea lies in how to construct the martingale. In contrast to the standard approach of creating one martingale difference for each data point $W_t$, we partition the data $W_t$'s into groups and construct a sequence of martingale differences for each group. Note that when the minibatch size $B$ is large enough relative to the order of $\ln T$, one can simply use a minibatch as a group. When the group size $N$ is large, the data of one group are mostly separated from another group's data by a long time interval, implying that the dependence between the groups is weak. This weak dependence allows us to apply the results developed for finite-time performance analysis to verify the conditions for a martingale CLT. However, the remainder term---the difference between the martingale and the quantity of interest $(\theta_{\lfloor T/B \rfloor} - \theta^*)$---grows with $N$. By choosing a proper value of $N$, one can strike a balance between the two competing forces and, therefore, obtain results in Theorem (ref). See Section (ref) of the online supplemental material for the details.

Theorem (ref) highlights the impact of the Markovian dependence structure: $\Sigma^*$ will be large, if $G(W_t,\theta^*)$ exhibits a strong intertemporal dependence structure, meaning $\Sigma^*(l)$'s are large. Therefore, Theorem (ref) sheds light on why “long-term strategies” are very challenging to learn. It also suggests that to learn $\theta^*$ more efficiently, one should perform more exploration to overcome intertemporal dependencies.

Applying SA Theory to IV-RL Algorithms

We now apply our general results for SA to IV-Q-learning. We show that $\theta_{\mathsf{Q},k}$ in IV-Q-learning can achieve the parametric rate of convergence when the learning rates are proportional to $k^{-1}$. A similar result is derived for IV-AC in Appendix (ref). We first describe the conditions required by both algorithms, starting with the assumptions on IVs.

Assumption (ref) describes IV validity conditions in MDP settings.\footnote{In the case of over-identification (i.e., $q > p$), $\theta_{\mathsf{I},k}$ converges to the projection of $\phi(S_t,A_t)$ on $Z_t$. } Assumptions (ref)(ref) and (ref)(ref) are standard. Assumption (ref)(ref) arises from the Markovian environment. This condition requires that the IV does not affect state transitions, which would introduce additional bias. The condition is satisfied when $Z_t$ influences the future only through its effect on $S_t$. For example, consider a state transition written as $S_{t+1} = f(S_t,A_t,\xi_t)$ for some deterministic function $f$ and random variable $\xi_t$. A common form is the linear transition model $S_{t+1}:= \beta_0 +\beta_1 S_t + \beta_2 A_t + \xi_t$, where $\xi_t$ is an i.i.d. random noise. If $\xi_t \perp Z_t$, the IV affects $S_{t+1}$ only through $(S_t, A_t)$, ensuring $S_{t+1} \perp Z_t|(S_t,A_t)$.

One sufficient condition for IVs to exist and satisfy the transition irrelevance condition is that $\xi_t$'s are independent shocks (e.g., productivity shocks). In this case, lagged terms $S_{t-l}$ or $A_{t-l}$, $l=1,2,\ldots,$ would satisfy the transition irrelevance condition while maintaining correlation with $S_t$, $A_t$ through the Markovian property. Nevertheless, a trade-off exists between IV strength and potential bias when using lag terms. As variables become more lagged, their correlation with current variables $S_t$, $A_t$ weakens, reducing IV strength. Adding more lagged terms can improve total IV strength and estimation efficiency for the optimal Q-function and optimal policy. However, this may lead to weak IV or many IV problems, resulting in biased estimates Hansen01102008.

The following assumptions pertain specifically to IV-Q-learning. Corresponding assumptions for IV-AC are presented in Appendix (ref).

Assumption (ref)(ref) is a natural generalization of the standard linear independence condition on the explanatory variables of linear regression. It ensures that the projection from a Q-function to $\mathrm{span}(\phi)$ is unique, so $\theta_{\mathsf{Q}}^*$ is the unique solution to equation (ref) for IV-Q-learning. Assumption (ref)(ref) is used to verify the growth condition in Assumption (ref). Note that KondaTsitsiklis03 use a stronger growth condition on $\phi$ to prove the convergence of standard Actor-Critic algorithms.

We impose Assumption (ref) to verify the conditions of Theorem (ref). In Assumption (ref)(ref), $W_t^{\mathsf{IVQ}}$ can be simplified to $\{S_t, A_t, R_t, Z_t, S_{t+1}\}$ if these random variables are all bounded. Assumptions (ref)(ref), (ref)(ref), and (ref)(ref) correspond to Assumptions (ref), (ref)(ref), and (ref)(ref), respectively. These conditions are self-explanatory except Assumption (ref)(ref), particularly the inequality (ref). It is critical for verifying the contraction condition (Assumption (ref)(ref)) for the SA recursion. This inequality means that the discount factor $\gamma$ cannot be arbitrarily close to one unless the behavior policy $\pi$ is sufficiently close to the optimal policy $\pi^*$ and the IV $Z_t$ is strong enough. MeloMeynRibeiro08 use a similar condition to prove the convergence of Q-learning with linear value functions (see Remark (ref)). This condition potentially narrows the scope of application of IV-Q-learning to practical economic problems, which is essentially due to the algorithm's lack of policy improvement (see more discussion in our numerical experiments in Section (ref)).

Corollary (ref) makes clear that IV-Q-learning can correct for R-bias and learn optimal Q-functions. The asymptotic covariance matrix $\Gamma^*_{\mathsf{Q}}$ is defined in Appendix (ref). Note that when $\delta=1$, the algorithm converges at a rate of $T^{-\frac{1}{2}}$ (i.e., the parametric rate with respect to the sample size), although the number of iterations is not necessarily of order $T$. (For instance, if $B \approx T^{\frac{1}{3}}$, then the number of iterations is approximately $T/B \approx T^{\frac{2}{3}}$.)

Simulation Experiments

In this section, we numerically evaluate the two IV-RL algorithms using the MDP problem in the platform incentive design example in Section (ref). The problem is specified as follows.

This MDP problem can be solved analytically: the optimal Q-function is linear in the basis functions $\phi(s,a)=(1, s, a, sa, s^2 , a^2)^\intercal$ and the optimal policy is a linear policy in the form of $\pi^*(s) = \theta_{\mathsf{A}}^{*,(0)} + \theta_{\mathsf{A}}^{*,(1)} s $. The goal here is to learn $\theta_{\mathsf{A}}^* = (\theta_{\mathsf{A}}^{*,(0)}, \theta_{\mathsf{A}}^{*,(1)})^\intercal $ without using the knowledge of the state transition or the true reward function.

Because the agent knows only that $\epsilon_t$ does not depend on $A_{t,1}$, transformations of $A_{t,1}$ and $S_t$ can serve as IVs, provided that $A_{t,2}$ is independent of $S_t$. Note that $\{A_t, S_tA_t, A_t^2\}$ are potentially endogenous. Thus, we construct three IVs $\{A_{t,1}, S_{t}A_{t,1}, A_{t,1}^2\}$ for them and set $Z_t=(1,S_t, A_{t,1}, S_{t}A_{t,1}, S_t^2, A_{t,1}^2)^\intercal$, where $\{1, S_t, S_t^2\}$ are the IVs for themselves.

In addition to the two IV-RL algorithms, we consider a “non-RL” learning method based on inverse propensity weighting (IPW). They are compared based on the inference on the optimal policy, particularly $\pi^*(s)$ for representative values of the state $s$.

For the two IV-RL algorithms, we set the learning rates to be proportional $k^{-1}$ to achieve the parametric rate of convergence. We consider two cases for the behavior policy $\pi_{\mathsf{A},0}$: in one case, $\pi_{\mathsf{A},0}$ is close to $\pi^*$, making it “easy” for the algorithms to learn the optimal policy, whereas in the other case, $\pi_{\mathsf{A},0}$ is clearly distinct from $\pi^*$ and we call it a “hard” policy. Specifications of the experimental design are detailed in Appendix (ref). The results are reported in Tables (ref) and (ref) for different discount factors, respectively.

The tables show that IV-AC performs well in all the cases. The initial behavior policy $\pi_{\mathsf{A},0}$ has little impact on its performance. This is because of policy improvement, as it allows the distribution of the generated data to be increasingly similar to the distribution corresponding to the optimal policy, making learning more efficient.

IV-Q-learning has a performance comparable to IV-AC in general. The former is even slightly better when the behavior policy $\pi_{\mathsf{A},0}$ is close to $\pi^*$ (the “easy” case), which is because IV-Q-learning has fewer parameters to estimate than IV-AC. When $\pi_{\mathsf{A},0}$ is changed from “easy” to “hard”, or when $\gamma$ increases from 0.85 to 0.95, IV-Q-learning's performance deteriorates, exhibiting larger RMSEs and lower CPs. This suggests that IV-Q-learning tends to work well either when the behavior policy is close to the optimal policy or when the discount factor is relatively small. Note that when $\pi_{\mathsf{A},0}$ is far from $\pi^*$ (the hard case) and the discount factor is large ($\gamma=0.95$), IV-Q-learning's performance is unsatisfactory, confirming the drawback of Q-learning with linear value functions (see Remark (ref)). In contrast, IV-AC continues to perform well because it uses policy improvement.

Last, 2SLS-IPW has a moderate bias but large RMSE in all the cases, especially when $\pi_{\mathsf{A},0}$ is far away from $\pi^*$. In addition, 2SLS-IPW generally yields significant under-coverage. This is because the weighted data $\rho_t \widehat{Q}^{\pi_{\theta_{\mathsf{A},0}}}(S_t,A_t)$ used for estimating $Q^{\pi_{\mathsf{A}}}$ are severely heavy-tailed. This happens because the inverse propensity weight $\rho_t$ tends to explode, if the path $\{(S_{t+l}, A_{t+l}):0\leq l < L\}$ has a low likelihood under $\pi_{\theta_{\mathsf{A},0}}$ (i.e., the policy that generates the path), but has a high likelihood under the policy $\pi_{\theta_{\mathsf{A}}}$ (i.e., the policy to evaluate), which is often the case when the two policies are significantly different. See HadadHirshbergZhanWagerAthey21 and ZhanHadadHirshbergAthey21 for similar findings when data are adaptively collected from multi-armed bandit algorithms.

Application: Corporate Share Repurchases

In this section, we apply IV-Q-learning to corporate share repurchase decisions, demonstrating how our methodology corrects for R-bias in a real-world scenario.

Background

To return cash to shareholders, companies can use two payout policies: dividends and share repurchases. Dividends provide direct payments to shareholders, while share repurchases involve the company buying back its own shares from existing shareholders on the secondary market. Unlike dividends, which distribute cash equally to all shareholders, share repurchases (or buybacks) only provide cash to shareholders who choose to sell. Share repurchases are often viewed favorably by the market, as they signal management's confidence in future earnings and belief that the stock is undervalued. This typically leads to an increase in share price GrullonMichaely04, benefiting all shareholders.

Share repurchases also serve as a valuable tool for earnings management, whereby companies strategically employ accounting techniques to enhance their financial reports. Earnings management often occurs when firms face pressure to adjust their earnings-per-share (EPS) to meet pre-determined targets established in analysts' forecast reports of quarterly financial performance. Share repurchases offer an immediate mechanism to boost short-term EPS by retiring repurchased shares, thereby mechanically reducing the EPS denominator. Consider a scenario where a company anticipates reporting an actual EPS of \$2.99, falling slightly short of the target EPS of \$3.00. In such cases, the firm has a strong incentive to repurchase shares to elevate its post-repurchase EPS to meet the target, thereby avoiding potential stock price declines typically associated with missed market expectations.

To illustrate the “just-miss” discontinuity concept described in AlmeidaFosKronlund16, consider a scenario where analysts forecast an EPS of \$3.00 per share for a company with one billion outstanding shares. If management learns the actual EPS will be \$2.99, just \$0.01 below the forecast, they may increase share repurchases to meet the target.

For example, spending \$600 million to repurchase shares at \$60 each would reduce outstanding shares to \$990 million. This action would affect earnings through forgone interest income on the \$600 million used for repurchases. With a 5% annual interest rate, 30% tax rate, and one quarter's interest, the lost interest income would be $1.25\%(1-30\%)\times\$600$ million = \$5.25 million. Consequently, total earnings would decrease from \$2.99 billion to \$2.98475 billion, resulting in a new EPS of \$3.01 (rounded). Through this mechanism, the company transforms a negative one-cent EPS surprise into a positive one-cent surprise.

This mechanical EPS adjustment through repurchases assumes fixed earnings from the previous quarter. In practice, post-repurchase EPS calculations are complicated by various market factors, such as negative market sentiment. Companies must therefore dynamically adjust their repurchase decisions based on evolving EPS figures to maintain positive surprises and prevent adverse market reactions.

HribarJenkinsJohnson06 first documented a discontinuity in share repurchase likelihood driven by earnings management considerations. Building on this discovery, AlmeidaFosKronlund16 developed an IV to examine how EPS-motivated repurchases affect other corporate policies. Their IV for share repurchase volume is an indicator variable that identifies whether a firm would report a negative EPS surprise in the absence of repurchases, leveraging the observation that firms with marginally negative pre-repurchase EPS surprises demonstrate a higher likelihood to conduct accretive share repurchases.

The repurchases triggered by narrowly missing target EPS connect to findings that firms conduct repurchases when their stock is undervalued IkenberryLakonishokVermaelen95,BrockmanChung01,PeyerVermaelen08. A stock price decline following a marginal EPS miss likely reflects market irrationality or pessimism rather than rational forecasting of the company's future prospects. When market pessimism drives stock prices lower, even companies meeting EPS targets may experience price drops. In such scenarios, companies have increased motivation to execute multiple rounds of repurchases following their initial announcement, adjusting both timing and volume until EPS returns to expected levels. This highlights how repurchases represent endogenous decisions influenced by various corporate state variables and behaviors.

Problem Formulation

We find that the decisions of initiating and iteratively adjusting share repurchases as recurring decisions in response to external conditions, particularly changes in company EPS, meets all the following requirements and conditions, therefore is a good scenario, for applying IV-Q-learning.

Decision Variable ($A$)

Share repurchasing constitutes an endogenous decision variable with a recurring nature. Following initial repurchases, companies make subsequent repurchase decisions based on how other variables evolve over time. This share repurchase decision process bears similarity to the incentive cost concept in the platform incentive scheme design problem discussed in the introduction.

Long-term True Reward ($r$)

Share repurchasing decisions directly impact the decision maker's true reward---the firm value---through two channels: (1) influencing stock price and thus market value, and (2) affecting liabilities if debt financing is used for repurchases. Firm value serves as the decision maker's objective (i.e., true reward) since it's typically the primary metric boards use to evaluate CEO performance. CEOs' compensation packages, including stock options, and their tenure prospects are heavily tied to both market value and liability status.

In corporate finance literature, Tobin's Q, introduced by Kaldor66, is the most common firm value proxy. Its standard calculation formula, which assumes equivalence between market and book values of liabilities, is: \[\frac{Equity\:Market\:Value + Liabilities\:Book\:Value}{Equity\:Book\:Value + Liabilities\:Book\:Value}.\]

Short-term Observable Reward ($R$)

Our objective is to understand how share repurchase decisions affect long-term firm value and to identify the optimal repurchase strategy along three dimensions: the initial decision to repurchase, frequency of repurchases, and repurchase volume. This analysis faces significant challenges. First, long-term firm value is determined by multiple factors, with share repurchases likely playing only a secondary role. Second, current-state firm value is unobservable until the following quarter's financial statements are released. We must instead rely on short-term market capitalization changes around repurchase dates (“$R$”) as a proxy for long-term firm value (“$r$”). This creates potential bias between $R$ and $r$, as we cannot ascertain whether short-term price movements translate into permanent changes in long-term firm value.

State Variable ($S$)

EPS serves as the state variable that, alongside factors such as firm investment and cash holdings, influences repurchase decisions. Conversely, repurchase decisions affect the subsequent period's EPS. In the immediate term, repurchases mechanically increase EPS by reducing the number of outstanding shares. In the short to medium term, repurchases send a positive signal to the market---when a company deploys its own funds for share repurchases, it demonstrates management's confidence in future prospects. This signaling effect can enhance investor confidence and market perception, potentially leading to improved operating performance and lower financing costs, which further boost EPS in subsequent periods. This bidirectional relationship makes EPS a recurring state variable.

Instrumental Variable ($Z$)

We seek an IV for the decision variable, and we adopt the IV proposed AlmeidaFosKronlund16. Their IV for share repurchases is an indicator of whether a firm would report a slightly negative EPS surprise without a repurchase. The EPS surprise is calculated as $S_t - T_t$, where $T_t$ represents the analyst's EPS forecast, considered the company's target EPS.

A valid IV must satisfy two key conditions---exogeneity and relevance. The IV constructed in AlmeidaFosKronlund16, which utilizes the “just-miss” discontinuity of the negative EPS surprise, satisfies both conditions:

Figure (ref) illustrates the dynamics of the above variables.

Data Sources and Sample Construction

Our analysis integrates data from four primary sources. We start with the Thomson Reuters Securities Data Company (SDC) transactions dataset, which provides 58 years of U.S. repurchase records. This dataset covers case-level repurchase information and details the deal date, the board of directors’ initial authorization date, total authorized amount, and the number of shares the company has repurchased for each repurchase program. Next, we merge these observations with firm-quarter fundamental data from the S&P Compustat dataset, stock-level data from the Center for Research in Security Prices (CRSP) dataset, and analysts forecast data of EPS from Institutional Brokers’ Estimate System (IBES) dataset.

The decision variable $A$ is defined as the repurchase amount normalized by the firm’s market value. Following AlmeidaFosKronlund16, we measure the pre-repurchase earnings surprise as the difference between the adjusted pre-repurchase EPS and the median EPS forecast at the end of the quarter. We calculate adjusted pre-repurchase EPS as: \[ EPS_{adj}=\frac{E+I}{SH+\Delta SH} \] where $E$ denotes reported quarterly earnings, $I$ denotes the after-tax interest that would be earned on the fund used to repurchase shares if it were invested in a 3-month T-bill alternatively, $SH$ denotes the number of shares at the end of the quarter, and $\Delta SH$ denotes the estimated number of shares repurchased measured as the repurchase amount divided by average daily stock price during the quarter.

The short-term observable reward ($R$) is constructed as follows. First, we define the treatment group as firms that conduct repurchases and meet or exceed EPS forecasts, but would have reported negative EPS surprises without the buybacks. Then, for each firm in the treatment group, we identify a corresponding firm in the control group using one-to-one nearest neighbor matching based on total assets, ROA, and sales within the same Fama--French 48 industry classification\footnote{\url{https://mba.tuck.dartmouth.edu/pages/faculty/ken.french/Data_Library/det_48_ind_port.html}}. The observable reward is measured as the matched firms' 5-day abnormal returns around earnings announcements (-5 to +5 days relative to announcement).

After excluding the observations with the missing value of the decision variable, our final sample includes 5,302 repurchase cases for 1,206 firms from 1996 to 2020.

Empirical Results

We treat the sample observed as an online learning environment with each repurchase case as a data point. More specifically, for each company's each repurchase announcement, we have multiple data points for its multiple times of repurchase actions that aim to achieve its goal of correcting the market value that is lowered by negative sentiment. Using the constructed sample described in the last subsection, we compute the optimal policy---the optimal repurchase amount normalized by the firm’s market value (or the “repurchase ratio”) for each repurchase action.

Similar to the simulation experiment in Section (ref), we assume that the linear-quadratic specification is used: $$\phi(s,a) = (1,s,a,s^2,sa,a^2)^\intercal.$$ As argued previously, the repurchase action is potentially endogenous, as company CEOs tries to manage EPS to meet the analysts' forecasts. We then adopt the following IV vector, denoted as $\widetilde{Z}$,in our analysis that: $$\widetilde{Z} = (1,s,z,s^2,sz,s^2z)^\intercal.$$ The parameters of $Q_\theta = \phi(s,a)^\intercal \theta_Q$ is initialized as the linear regression coefficient of reward $r$ on $\phi(s,a)$, and the parameter $\Gamma$, i.e., the first stage IV regression, is initialized as the regression coefficient of $\phi(s,a)$ on $\widetilde{Z}$. Our parameters of learning rate is chosen that $\alpha_{0,\mathsf{Q}}= 1$, $\alpha_{0,\mathsf{I}} = 0.1$, with decay rate $\delta = 0.8$. Discount rate $\gamma$ is set to be $0.95$.

The standard linear regression of repurchase action on state demonstrates a weak and insignificant negative slop that:

with t-stats of $EPS_t$ as $-1.011$, which only reveals a weak negative relationship between repurchase behavior and the EPS. After applying IV-Q-learning, the optimal policy learned (the green line in Figure (ref) demonstrates a strong negative relationship between EPS and the suggested optimal repurchase behavior by IV-Q-learning, with tight lower and upper pointwise confidence bands (the blue lines) computed according to our asymptotic results in Theorem (ref). We observe that, in general, the average repurchase behavior calibrated in the OLS of action on state has a slope that is significant lower than that is learned by Q-learning.

In the following, we first show the degree of R-bias, which is how much the actual actions of listed companies deviate from our optimal actions calculated; and then we analyze what factors relate to the degree of the R-bias.

R-bias in Repurchases

The optimal repurchase ratios calculated are close to the actual repurchases for some firms and deviate from the actual ratios for others. Here we calculate the difference between optimal and actual repurchase ratios for each repurchase action, and present the summary statistics below.

As shown in Table (ref), the mean of the actual repurchase ratio is 0.015, significantly below the mean of the optimal repurchase ratio 0.038; the median of the actual repurchase ratio is 0.01, significantly below the median of the optimal repurchase ratio 0.041. The p-values presented under the differences are very close to zero.

We present the distribution of each repurchase action's actual-optimal difference in Figure (ref). While the mean of the difference, or bias, is negative, there is a portion of repurchase cases in which the actual repurchase amount is higher than the optimal level calculated.

Factors Related to R-bias

Here we try to find some factors that may explain the R-bias. We average the difference between optimal and actual repurchase ratios by each firm and generate a firm-level R-bias, and use it as the dependent variable. Since R-bias can be positive or negative, we also create another dependent variable by taking the absolute value of R-bias, indicating merely the degree of deviation of actual repurchase from the optimal ratio. We collect each company's total assets in the repurchase year, years of operation (“firm age”), and the number of repurchase announcements that the company has done before this year (“repurchase experience”) as the explanatory variables.

Table (ref) presents the regression results. Columns (1) and (2) use the raw R-bias value and Columns (3) and (4) use the absolute value of R-bias as the dependent variables. A higher raw R-bias value represents a higher actual repurchase amount compared to the optimal level, while a higher absolute value of R-bias represents a further deviation of the actual repurchase from the optimal level. Columns (2) and (4) control for year fixed effects that absorb all other year-level variants, while the other two columns do not.

As Columns (1) and (2) show, firms that have more years of operation and more experience of repurchases have a higher actual repurchase amount compared to the optimal level, and those firms, according to the estimates in Columns (3) and (4), deviate less from optimal policies. Together, the results indicate that while firms on average repurchase less than the optimal level, the more experienced firms' repurchase is closer to the optimal and the bias is smaller. Firm size, as measured by total assets, and firm value, as measured by Tobin's Q, seem to have little relationship with either the raw or the absolute value of R-bias.

Conclusion

This paper examines causality problems in general MDPs when the observed rewards are biased. Because decisions depend on past data, this interaction generates R-bias. We propose IV-RL algorithms (IV-Q-learning and IV-AC) to correct R-bias and analyze them through the lens of SA with iterate-dependent Markovian structures.

Our paper is a step toward a rich research program of IV-RL algorithms. For example, we have not considered the financial cost of creating IVs. If firms can create different instruments, it will be useful to examine the “optimal” instruments (in terms of financial costs rather than in a statistical sense). Exploring these topics would form a rich avenue for future research.