Scheduling "Last Minute" Updates for Timely Decision-Making
Scheduling "Last Minute" Updates for Timely Decision-Making
复制标题
DOI：
10.1145/3616388.3617518
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
Jean Abou Rahal;G. de Veciana
中科院分区：
文献类型：
--
作者：
Jean Abou Rahal;G. de Veciana
我们考虑这样一种设置，其中在做出一系列决策之前需要请求关于时变过程的更新。每个请求都有一个有限长度的时间窗口，在此期间应该接收更新。窗口的结束反映了作出决定的时间，而窗口的开始则模拟了可以发送有用的更新的尽可能早的时间。尽可能接近窗口末尾安排的更新被认为是最好的，即反映了有关进程状态的最及时信息。这是通过根据决策点和上次计划的更新之间的时间差进行奖励来建模的。请求任意到达并共享有限的通信资源，例如，每个时隙可以调度单个请求，因此并不是所有的决定都可以基于最新的可能更新。我们考虑最大化总体奖励率的更新调度策略。特别是，我们考虑了一个对抗性请求模型，并通过它们的竞争比(CR)对所提出的算法进行了评估。具体地说，我们首先推导出任何因果政策的CR的下界。然后，我们提出了两种调度策略，表示为对抗性和贪婪，并提供了进一步的分析和见解，其中一个可能优于另一个。我们通过对随机到达情况下的模拟来验证这些观测结果。
We consider a setting where requests for updates regarding time-varying processes are required prior to making a sequence of decisions. Each request has a finite length time window during which the update should be received. The end of the window reflects the time at which a decision is to be made, while the start of the window models the earliest possible time at which a useful update could be sent. An update scheduled as near to the end of the window as possible is deemed the best, i.e., reflects the most timely information about the process' state. This is modelled by a reward depending on the time difference between the decision point and the last scheduled update. Requests arrive arbitrarily and share a limited communication resource, e.g., a single request can be scheduled per time slot, hence not all decisions can be based on the latest possible update. We consider update scheduling policies which maximize the overall reward rate. In particular we consider an adversarial request model and evaluate proposed algorithms via their Competitive Ratio (CR). Specifically, we first derive a lower bound on the CR of any causal policy. We then propose two scheduling policies, denoted adversarial and greedy, and provide further analysis and insights on regimes where one might be superior to the other. We validate these observations via simulation for a setting with stochastic arrivals.