在状态查询有成本时,用预测减少查询次数,提升效率。
Monitoring State Transitions in Markovian Systems with Sampling Cost
- 用预测代替频繁查询,仅在不确定时才触发查询
- 贪婪策略在多数情况下接近最优,但可能表现极差
- 提出新算法,适合未知转移概率的实时系统
我们研究一个节点-监控器配对系统,其中节点状态随时间变化。监控器需持续追踪状态,但每次状态查询有固定成本。因此,监控器可采用时间序列预测方法(包括时间序列基础模型)进行预测,并仅在预测不确定性高时才查询。由于查询决策影响预测精度,何时查询成为关键问题。一种自然做法是贪婪策略:当预期预测损失低于查询成本时预测,否则查询。我们在马尔可夫设定下分析该策略,此时最优策略(OPT)为状态相关阈值策略,最小化平均查询成本与预测损失之和。我们证明,一般情况下贪婪策略次优,且竞争比可能无界;但在转移概率同分布等常见条件下,其性能接近最优。针对转移概率未知的情况,我们进一步提出基于投影随机梯度下降(PSGD)的贪婪策略学习变体,实现更优的预测-查询权衡,且计算效率优于OPT。
原文摘要 · Abstract (English)
We consider a node-monitor pair, where the node's state varies with time. The monitor needs to track the node's state at all times; however, there is a fixed cost for each state query. So the monitor may instead predict the state using time-series forecasting methods, including time-series foundation models (TSFMs), and query only when prediction uncertainty is high. Since query decisions influence prediction accuracy, determining when to query is nontrivial. A natural approach is a greedy policy that predicts when the expected prediction loss is below the query cost and queries otherwise. We analyze this policy in a Markovian setting, where the optimal (OPT) strategy is a state-dependent threshold policy minimizing the time-averaged sum of query cost and prediction losses. We show that, in general, the greedy policy is suboptimal and can have an unbounded competitive ratio, but under common conditions such as identically distributed transition probabilities, it performs close to OPT. For the case of unknown transition probabilities, we further propose a projected stochastic gradient descent (PSGD)-based learning variant of the greedy policy, which achieves a favorable predict-query tradeoff with improved computational efficiency compared to OPT.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。