Data Driven Block Replacement Scheduling

TL;DR - A theoretical paper casting the classic "block replacement" maintenance problem (jointly replacing N machines every k intervals plus on-failure) as a stochastic multi-armed bandit, learning the cost-minimizing interval from censored failure data when the lifetime distribution is unknown. It matters as a rigorous bridge between online-learning theory and reliability/maintenance operations.

• Proposes Hoeffding- and Bernstein-based LCB bandit algorithms achieving $O(K\log T)$ regret, matching the Lai–Robbins lower bound.
• Exploits a "nested observation" property unique to block replacement so correlated variants attain $O((K-k^*)\log T)$ regret with only $O(1)$ pulls of suboptimal short intervals.
• A Kaplan–Meier renewal algorithm nonparametrically estimates the lifetime distribution from censored data, giving almost-sure policy consistency and near-zero incremental regret at long horizons.
• Analyzes two average-cost MDPs (time-elapsed and age-vector), proving block replacement's optimality within its class and a monotone threshold structure under increasing-failure-rate distributions; experiments confirm the theory and reveal block-vs-age cost gaps.