Data Driven Block Replacement Scheduling

We develop data-driven algorithms for maintaining N independent identical machines under a block replacement policy, in which each machine is replaced upon failure and all machines are jointly replaced at regular intervals of length k. The goal is to learn the cost-minimizing interval k^* from operational data when the lifetime distribution is unknown. At each decision epoch, the operator selects k \in {1, 2, \ldots, K}, observes the resulting failure history (a mixture of complete and right-censored lifetimes) and incurs a per-unit-time cost governed by the renewal function. We formulate this as a stochastic multi-armed bandit and propose Hoeffding- and Bernstein-based lower-confidence-bound algorithms achieving O(K \log T) regret, matching the Lai--Robbins lower bound. Exploiting a nested observation property unique to block replacement, correlated variants attain O((K-k^)\log T) regret and require only O(1) direct pulls of suboptimal arms k < k^. A complementary Kaplan--Meier renewal algorithm estimates the lifetime distribution nonparametrically from censored data, achieving almost-sure policy consistency and empirically near-zero incremental regret at long horizons. We additionally analyze two average-cost MDPs: a time-elapsed formulation establishing that block replacement is optimal within its policy class for any lifetime distribution, and an age-vector formulation proving a monotone threshold structure under increasing failure rate distributions and providing a gold-standard cost benchmark. Numerical experiments confirm the theoretical ordering and reveal structural cost gaps between optimal block and age-dependent replacement.