Divide-and-conquer offline policy evaluation for contextual bandits

Weiwei Wang, Yuliya Shapovalova, Yuqiang Li and Xianyi Wu

Physica A: Statistical Mechanics and its Applications, 2025, vol. 676, issue C

Abstract: This paper investigates the application of divide-and-conquer (DC) algorithm to address the challenge of processing large datasets in offline policy evaluation within contextual bandit settings. We address the critical issue of determining the optimal number of machines as the dataset size scales, and establish a theoretical upper bound on the number of machines to control information loss from the DC algorithm. Our work aims at developing an estimator whose estimation accuracy matches that of an ideal direct estimator obtained by using the complete dataset. It turns out that the DC estimator can improve computational efficiency while maintaining statistical efficiency. When the number of machines is appropriately chosen, the estimator can be optimal in minimax rate. Furthermore, we extend the application of the DC algorithm to offline policy evaluation in reinforcement learning (RL) and explore the relationships between the number of machines and combinations of distribution shifts and horizons, showcasing enhanced computational efficiency through an extensive set of simulation experiments.

Keywords: Contextual bandit; Offline policy evaluation; Divide-and-conquer algorithm; Minimax-optimal; Reinforcement learning (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437125004741
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:676:y:2025:i:c:s0378437125004741

DOI: 10.1016/j.physa.2025.130822

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().