The Shortest Path Problem Under Partial Monitoring
The Shortest Path Problem Under Partial Monitoring
复制标题
部分监控下的最短路径问题
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
György Ottucsák
中科院分区：
文献类型：
--
作者：
A. György;T. Linder;György Ottucsák
部分监控场景下考虑在线最短路径问题。在每一轮中，决策者必须在带权有向无环图的两个不同顶点之间选择一条路径，其边权重可以以任意（对抗性）方式改变，使得所选路径的损失（定义为其组成边的权重之和）很小。在多臂老虎机设置中，选择路径后，决策者仅了解属于所选路径的那些边的权重。对于这种情况，给出了一种算法，其在 n 轮中的平均累积损失超过了最佳路径的损失，离线匹配到边权重的整个序列，其数量与 1/√n 成正比，并且仅与图的边数相关。该算法可以以轮数 n 和边数的线性复杂度来实现。这一结果改进了早期的老虎机算法，这些算法的性能界限要么以指数方式依赖于边的数量，要么以比 O(1/√n) 更慢的速度收敛到零。还给出了所谓的标签有效设置的扩展，其中仅当概率 e < 1 时，决策者才被告知所选路径的权重。还介绍了分组交换网络中路由的应用以及仿真结果。
The on-line shortest path problem is considered under partial monitoring scenarios. At each round, a decision maker has to choose a path between two distinguished vertices of a weighted directed acyclic graph whose edge weights can change in an arbitrary (adversarial) way such that the loss of the chosen path (defined as the sum of the weights of its composing edges) be small. In the multi-armed bandit setting, after choosing a path, the decision maker learns only the weights of those edges that belong to the chosen path. For this scenario, an algorithm is given whose average cumulative loss in n rounds exceeds that of the best path, matched off-line to the entire sequence of the edge weights, by a quantity that is proportional to 1/√n and depends only polynomially on the number of edges of the graph. The algorithm can be implemented with linear complexity in the number of rounds n and in the number of edges. This result improves earlier bandit-algorithms which have performance bounds that either depend exponentially on the number of edges or converge to zero at a slower rate than O(1/√n). An extension to the so-called label efficient setting is also given, where the decision maker is informed about the weight of the chosen path only with probability e < 1. Applications to routing in packet switched networks along with simulation results are also presented.