---
title: "数据驱动块替换调度：基于多臂老虎机的非参数成本优化"
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估计","块替换","多臂老虎机","生存分析","维护调度","遗憾界"]
---

# 数据驱动块替换调度：基于多臂老虎机的非参数成本优化

## AI 点评

> 这篇论文将维护调度问题与多臂老虎机巧妙结合，嵌套观测的利用非常聪明。对于从事工业AI或运筹学优化的读者，它提供了一套优雅而实用的非参数框架；对理论研究者，它的遗憾界匹配与MDP分析同样值得细读。

## 速览

该论文针对未知寿命分布下的N台独立同型机器维护调度问题，提出了数据驱动的块替换策略。通过将替换间隔选择建模为随机多臂老虎机，设计了基于Hoeffding和Bernstein的置信下界算法，实现O(K log T)的遗憾上界，匹配理论下界。利用块替换特有的嵌套观测特性，进一步提出相关变体算法，对次优臂k<k*仅需常数次直接拉动。同时，引入Kaplan-Meier更新算法非参数估计寿命分布，达到几乎必然策略一致性。实验验证了理论排序，并揭示了最优块替换与年龄依赖替换之间的结构化成本差距。

## 关键点

- 将块替换调度问题转化为随机多臂老虎机，并设计两种置信下界算法，遗憾界达到理论最优。
- 利用嵌套观测特性提出相关变体，显著降低次优臂的探索成本。
- 引入Kaplan-Meier更新算法处理截尾数据，实现非参数分布估计与策略一致性。
- 通过两种平均成本MDP分析，证明块替换在策略类中的最优性及其与年龄依赖替换的成本差距。

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_d5ecdf2dcdb482a3aa8387ae