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

arXiv:2305.16056v5 Announce Type: replace-cross Abstract: 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.

Abstract: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.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI)

arXiv:2305.16056 [cs.LG]

(or arXiv:2305.16056v5 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2305.16056 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

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

Related coverage