# Data Driven Block Replacement Scheduling

arXiv: https://arxiv.org/abs/2607.15229 · HTML: https://mlsanity.com/paper/2607.15229/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 30 references that are in the map.
- First posted on arXiv 16 Jul 2026.

## Builds on (most cited first, 1 of 1)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)

## Abstract (arXiv)

We develop data-driven algorithms for maintaining N independent identical machines under a textitblock 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 ∈ 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.