Optimal Data Acquisition for Reinforcement Learning: A Large Deviations Perspective
For researchers and practitioners in reinforcement learning, this work provides a principled theoretical framework for data acquisition efficiency, though the practical impact is limited by the tractable convex relaxation and constant-factor optimality guarantee.
This paper proposes a large deviations framework for data acquisition in infinite-horizon reinforcement learning, introducing the exponential decay rate of policy-selection error probability as an efficiency metric. The resulting adaptive data acquisition policy is proven to be near-robustly optimal up to a constant factor, with numerical experiments supporting its effectiveness.
Data acquisition efficiency is a central challenge in deploying reinforcement learning in business and healthcare operations, where interactions are costly, slow, and often involve humans in the loop. This paper develops a unified large deviations framework for data acquisition in infinite-horizon reinforcement learning. We introduce the exponential decay rate of the policy-selection error probability as a principled efficiency metric and derive a variational characterization of this rate via large deviations theory for Markov chains, yielding a nested optimization problem. Based on this characterization, we formalize two complementary notions of optimality in terms of the optimal solution of the nested problem. Because the resulting program is implicit and generally intractable, we propose a tractable convex relaxation with explicit constraints. We then develop a lazy one-step projected subgradient method to solve the relaxed problem and use its iterates to construct an adaptive data acquisition policy. We prove that the resulting reinforcement learning algorithm is near-robustly optimal under our optimality criterion, up to a constant factor. Finally, we extend the framework to linear function approximation to improve scalability, and numerical experiments support the effectiveness of the proposed approach.