---
title: "Data-Driven Block Replacement Scheduling: Multi-Armed Bandit Based Nonparametric Cost Optimization"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2607.15229v1"
permalink: "https://feed.astralor.com/items/itm_d5ecdf2dcdb482a3aa8387ae"
published: "2026-07-16T17:31:15.000Z"
score: 75
channel: "tech"
tags: ["Kaplan-Meier Estimator","Block Replacement","Multi-Armed Bandits","Survival Analysis","Maintenance Scheduling","Regret Bound"]
---

# Data-Driven Block Replacement Scheduling: Multi-Armed Bandit Based Nonparametric Cost Optimization

## AI commentary

> This paper cleverly integrates maintenance scheduling with multi-armed bandits, and the exploitation of nested observations is particularly ingenious. For those working in industrial AI or operations research optimization, it offers an elegant and practical nonparametric framework; for theoreticians, the regret bound matching and MDP analysis are equally worth careful study.

## At a glance

This paper addresses the block replacement scheduling problem for N independent identical machines with unknown lifetime distributions. By formulating the interval selection as a stochastic multi-armed bandit, the authors propose Hoeffding- and Bernstein-based lower-confidence-bound algorithms achieving O(K log T) regret, matching the Lai–Robbins lower bound. Exploiting the 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 nonparametrically estimates the lifetime distribution from censored data, ensuring almost-sure policy consistency. Numerical experiments confirm theoretical ordering and reveal structural cost gaps between optimal block and age-dependent replacement.

## Key points

- Formulates block replacement scheduling as a stochastic multi-armed bandit and designs two LCB algorithms achieving optimal regret bounds.
- Leverages nested observation property to develop correlated variants with reduced exploration cost for suboptimal arms.
- Introduces Kaplan–Meier renewal algorithm for nonparametric distribution estimation from censored data, ensuring policy consistency.
- Analyzes two average-cost MDPs, proving optimality of block replacement within its policy class and revealing cost gaps with age-dependent replacement.

## Full text

We develop data-driven algorithms for maintaining $N$ independent identical machines under a \textit{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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_d5ecdf2dcdb482a3aa8387ae