The on-line shortest path problem under partial monitoring

Abstract

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.

35 pages

Cited by in corpus (23)

• Combinatorial Bandits Revisited
• Minimal Exploration in Structured Stochastic Bandits
• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
• Minimax Policies for Combinatorial Prediction Games
• Online Multi-task Learning with Hard Constraints
• Towards Optimal Adaptive Wireless Communications in Unknown Environments
• Online combinatorial optimization with stochastic decision sets and adversarial losses
• Deterministic MDPs with Adversarial Rewards and Bandit Feedback
• First-order regret bounds for combinatorial semi-bandits
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Adversarial Online Learning with Variable Plays in the Pursuit-Evasion Game: Theoretical Foundations and Application in Connected and Automated Vehicle Cybersecurity
• Regret in Online Combinatorial Optimization
• (Locally) Differentially Private Combinatorial Semi-Bandits
• Data Driven SMART Intercontinental Overlay Networks
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
• Practical Adversarial Combinatorial Bandit Algorithm via Compression of Decision Sets
• Near Optimal Adaptive Shortest Path Routing with Stochastic Links States under Adversarial Attack
• An efficient algorithm for learning with semi-bandit feedback
• Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays
• SpecWatch: A Framework for Adversarial Spectrum Monitoring with Unknown Statistics