Source-linked AI summary
The on-line shortest path problem under partial monitoring
Andras Gyorgy, Tamas Linder, Gabor Lugosi, Gyorgy Ottucsak
TL;DR
The paper asks how to learn shortest paths in adversarial networks when only selected-path information is observed. It develops structured bandit algorithms and extensions, obtaining polynomial dependence on graph size and an O(1/√n) rate for separately observed edge losses, while also treating more restricted feedback models.
Problem
General bandit bounds depend on the number of paths, which can be exponentially large in the graph, making shortest-path learning computationally and statistically challenging.
Method
The paper estimates gains per edge rather than per path, uses graph structure and dynamic programming, and introduces covering paths to sample every edge sufficiently often.
Results
The main algorithm has polynomial dependence on the number of edges and converges at the O(1/√n) rate when losses of selected-path edges are separately observed.
Takeaways & Limitations
The approach makes online shortest-path learning viable for graphs with exponentially many paths and extends to label-efficient, time-varying-comparator, and restricted-feedback settings.
Takeaways & Limitations
The O(1/√n) result assumes equal path lengths after a graph transformation, while the restricted setting is reported with an O(n−1/3) per-round regret bound and leaves the O(n−1/2) polynomial-edge bound open.
Abstract
from arXiv · showhide
The on-line shortest path problem is considered under various models of partial monitoring. Given a weighted directed acyclic graph whose edge weights can change in an arbitrary (adversarial) way, a decision maker has to choose in each round of a game a path between two distinguished vertices such that the loss of the chosen path (defined as the sum of the weights of its composing edges) be as small as possible. In a setting generalizing the multi-armed bandit problem, after choosing a path, the decision maker learns only the weights of those edges that belong to the chosen path. For this problem, 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/\sqrt{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. An extension to the so-called label efficient setting is also given, in which the decision maker is informed about the weights of the edges corresponding to the chosen path at a total of m << n time instances. Another extension is shown where the decision maker competes against a time-varying path, a generalization of the problem of tracking the best expert. A version of the multi-armed bandit setting for shortest path is also discussed where the decision maker learns only the total weight of the chosen path but not the weights of the individual edges on the path. Applications to routing in packet switched networks along with simulation results are also presented.
1 Introduction
The paper studies online shortest-path learning when edge losses are adversarial and only partial feedback is available. Its main algorithm achieves polynomial dependence on graph size while recovering the O(1/√n) rate, with extensions to restricted feedback, label efficiency, and changing comparators.
- Online shortest path selects a path through a weighted directed acyclic graph each round while edge weights may change arbitrarily.
- Full-information methods can run in time proportional to the number of edges rather than the typically exponential number of paths.
- Earlier partial-monitoring methods removed exponential graph-size dependence but achieved worse-than-O(1/√n) dependence on the number of rounds.
- The paper extends adversarial bandit learning to obtain polynomial edge dependence and the O(1/√n) convergence rate when chosen-path edge losses are observed separately.
- The paper also treats total-path feedback, label-efficient queries, competition with time-varying paths, and routing applications with simulations.
2 The shortest path problem
The shortest-path problem is formulated as online decision-making over paths in a directed acyclic graph. Each path loss is additive across its edges, and performance is measured against the best fixed path in hindsight.
- A packet-routing interpretation chooses a source-to-destination route each time while edge delays change arbitrarily.
- The graph is finite and directed acyclic, with distinguished vertices u and v and a path set containing all u-to-v paths.
- At each round, the decision maker selects one path, after which losses in [0, 1] are assigned to all edges.
- A path’s loss and cumulative loss are additive sums of the losses of its composing edges.
- The randomized decision rule is evaluated by normalized regret against the best expert path over n rounds.
3 The multi-armed bandit setting
The shortest-path bandit setting reveals only feedback associated with the selected route, creating a challenge because the number of possible paths may be exponentially large. The paper distinguishes edge-level feedback from observing only the selected path’s total loss.
- In the bandit setting, the decision maker observes losses only for the path it selected, as in route-delay feedback.
- The unrestricted variant reveals each selected-path edge loss, whereas the restricted variant reveals only the selected path’s total loss.
- Edge and path losses may depend on the decision maker’s earlier path choices, allowing non-oblivious adversaries.
- Applying a general bandit algorithm is impractical because its dependence on the number of paths N can be exponential in graph size.
- Prior algorithms achieved polynomial edge dependence in the restricted setting but paid with worse dependence on the game length n.
4 A bandit algorithm for shortest paths
The algorithm estimates gains at the edge level and exploits shared edges between paths, while using covering paths to ensure sufficient edge sampling. It achieves a shortest-path bandit regret bound scaling with the graph’s edges and path length, and can be implemented efficiently.
- Algorithm design: Equal path lengths are enforced by adding zero-weight vertices and edges without changing path weights.The construction uses K, the longest-path length in the original acyclic graph.
- Algorithm design: The algorithm estimates gains for edges rather than paths, replacing dependence on the number of paths with dependence on the number of edges.It exploits information about paths that share edges with the selected path.
- Algorithm design: A covering set C ensures every edge is sampled sufficiently often, with |C| ≤ |E|.The algorithm uses covering paths alongside graph-based path sampling.
- Performance: The performance bound gives per-round regret of roughly K√(|E| ln N/n), where |E| is the edge count, K the path length, and N the number of paths.The theorem provides the bound with probability at least 1 − δ under stated parameter conditions.
- Implementation: The algorithm has time complexity O(n|E|) and space complexity O(|E|).Dynamic programming computes the main path and edge probabilities efficiently on the acyclic graph.
5 A combination of the label efficient and bandit settings
This section combines label-efficient querying with bandit feedback for shortest paths, motivated by costly observations. The resulting algorithm controls both query usage and regret under partial monitoring.
- Problem setting: The decision maker observes the chosen path’s loss only upon request, with at most m total requests.This combines the multi-armed bandit and label-efficient settings when feedback is costly.
- Algorithm: The combined algorithm queries the chosen path with probability ǫ and computes biased estimates of path gains.The model assumes every graph path has the same length K.
- Algorithm: The algorithm modifies the earlier bandit procedure by replacing its estimation step with a label-efficient version.The modified step draws a Bernoulli variable and updates estimates only when the query event occurs.
- Analysis: The analysis generalizes the preceding bandit theorem and the label-efficient prediction theorem, using concentration and martingale arguments.The proof handles the random shifting term introduced by queried feedback.
- Guarantees: With ǫ chosen using m and δ, the number of queries is at most m with probability at least 1 −δ.The resulting performance bound has order K√(|E| ln(N/δ)/m).
6 A bandit algorithm for tracking the shortest path
This section extends shortest-path bandit learning to compete with paths that may change over time. It targets tracking performance despite an exponentially large set of base paths.
- Tracking objective: The algorithm competes with a time-varying path represented by an m-partition into contiguous segments.Each segment assigns one of the N graph paths.
- Tracking objective: The tracking comparator may switch paths m times, and the goal is small normalized regret against the best such partition.The guarantee is required for all outcome sequences with high probability.
- Motivation: Directly applying classical tracking methods is impractical because the graph’s base experts are all source-to-destination paths, typically exponentially many in the edges.The paper extends efficient structured-expert tracking methods to bandit feedback on chosen-path edges.
- Algorithm: The algorithm samples paths from a tracking distribution, estimates gains, and updates weights while incorporating switching behavior.Its steps include path selection, edge-probability computation, gain estimation, and weight updating.
- Implementation: An alternative efficiently computable formulation has time complexity O(n^2|E|).This follows from the O(n|E|) complexity of the baseline shortest-path bandit algorithm and the tracking construction.
7 An algorithm for the restricted multi-armed bandit problem
This section addresses restricted feedback in which only the total loss of the chosen path is observed, not its individual edge losses. It reconstructs path-loss estimates through a path basis.
- Feedback model: The restricted setting reveals only the chosen path’s total loss, leaving individual edge losses unobserved.This is the shortest-path analogue of a bandit problem with aggregate feedback.
- Guarantee: The proposed restricted-feedback algorithm achieves regret of order n^-1/3 with high probability.This improves on the earlier n^-1/4 result and matches the order achieved by a more complex prior algorithm.
- Representation: Paths are represented as binary edge-incidence vectors, allowing path losses to be expressed through edge-loss inner products.This representation reduces computations over many paths to operations involving graph edges and basis paths.
- Basis construction: A barycentric-spanner basis expresses every path through bounded linear combinations of basis paths.For directed acyclic graphs, a 1-barycentric spanner exists; the paper also uses a 2-barycentric spanner for simplicity.
- Algorithm: The algorithm queries a randomly selected basis path intermittently and uses its unbiased loss estimate to estimate all path losses.The estimated path losses then support exponential weighting implemented by dynamic programming.
8 Simulation results
Simulations test the algorithms on a graph with exponentially many paths and compare them with established baselines. The experiments examine performance under randomized edge losses.
- Experimental setup: The experiments use a small graph with 2^(|E|/2) paths, making exponential path growth central to the comparison.The graph was selected to test the paper’s motivation of avoiding dependence on the total number of paths.
- Experimental setup: Independent uniform edge losses make the all-upper-edge path optimal in the long run.Upper-edge losses are drawn from [0, 1], while lower-edge losses are drawn from [0.32, 1].
- Experimental setup: The simulations run for n = 10000 steps with confidence value δ = 0.001 and include EXP3 as a baseline.The comparison also evaluates edge-bandit, path-bandit, and Awerbuch–Kleinberg variants.
- Results: The edge-bandit algorithm shows the expected superior performance, while path-bandit outperforms AwKl but remains inferior to AwKl tuned.Parameter optimization does not improve path-bandit, which behaves robustly under tuning.
9 Conclusions
The paper addresses adversarial shortest-path problems with limited feedback, providing efficient algorithms with favorable regret dependence in several settings. It also identifies an unresolved guarantee in the restricted setting where only whole-path losses are observed.
- The algorithms handle adversarial edge losses, including losses that may depend on previous routing decisions.
- O(1/√n) normalized regret converges to zero while depending only polynomially on the graph’s edges and vertices.
- Earlier methods either lack the O(1/√n) convergence rate or have regret that grows exponentially with graph size.
- The algorithm extends to competing with time-varying paths when the number of path changes is sublinear in n.
- With only whole-path losses revealed, the simpler algorithm achieves O(n^-1/3) normalized regret and has performance comparable to the best earlier method.
- Whether restricted feedback permits O(1/√n) regret without exponential graph-size dependence remains open.
10 Appendix
The appendix states a Bernstein inequality for martingale differences, beginning with boundedness and then giving its conclusion.
- Lemma 9 concerns a martingale difference sequence whose variables are almost surely bounded between a and b.
- The appendix presents this result as Bernstein’s inequality for martingale differences.
- The lemma then states a bound for every ε > 0, although the supplied passage does not include the bound’s formula.