Reinforcement Learning under External Influence: Guarantees, Algorithms, and Sample Complexity

In this paper, we study the problem of reinforcement learning under the influence of external events. For this, we consider Markov decision processes with continuous state and action spaces whose transition dynamics are perturbed by an external process in a non-Markovian manner. First, we establish the conditions under which the problem becomes tractable, allowing it to be addressed by considering only a finite history of events, based on the properties of the perturbations introduced by the exogenous process. We propose and theoretically analyze a policy iteration algorithm to tackle this problem that learns policies contingent on the current state of the environment and a finite history of prior exogenous events. Since this algorithm is not guaranteed to converge, we provide a guarantee for policy improvement in regions of the state space determined by the approximation error induced by considering tractable policies and value functions. We also establish the sample complexity of least-squares policy evaluation and policy improvement algorithms that account for approximations arising from considering only a finite history of temporal events. While our results are applicable to general discrete-time processes satisfying certain conditions on the rate of decay of the influence of their events, we further analyze the case of discrete-time Hawkes processes with Gaussian marks. We performed experiments to demonstrate our findings for policy evaluation and deployment in traditional control environments.