IEDA Seminar - Causal Reinforcement Learning: An Instrumental Variable Approach

In the standard data analysis framework, data is first collected--once for all, and then data analysis is carried out. Moreover, the data generation process is typically assumed to be exogenous. This approach is natural when the data analyst has no impact on how the data is generated. The advancement of digital technology, however, has facilitated firms to learn from data and make decisions at the same time. Since these decisions generate new data, the data analyst--a business manager or an algorithm--also becomes the data generator. In this article, we formulate the problem as a Markov decision process (MDP) and show that the interaction generates a new type of bias--reinforcement bias--that exacerbates the endogeneity problem in static data analysis. When the data structure is i.i.d, we embed the instrumental variable (IV) approach in the stochastic gradient descent (SGD) algorithm to correct for the bias. For general MDP problems, we propose a class of IV-Reinforcement Learning algorithms to correct for the bias. We establish asymptotic properties of our algorithms by incorporating them into two-timescale stochastic approximation (SA). Since our formulation allows unbounded state space and more importantly, Markovian noise, standard techniques in RL and SA literature, which rely on boundedness of the state space and martingale difference structure of the noise, do not apply. We develop new techniques to establish risk bounds, finite time bounds for pathwise stability, and asymptotic distribution of a class of IV-RL algorithms.

Authors: Jin Li, Ye Luo, Xiaowei Zhang