Publications -> Conference Papers

Playing Repeated Network Interdiction Games with Semi-Bandit Feedback


Authors: Q. Guo, B. An, and L. Tran-Thanh
Title: Playing Repeated Network Interdiction Games with Semi-Bandit Feedback
Abstract: We study repeated network interdiction games with no prior knowledge of the adversary and the environment, which can model many real world network security domains. Existing works often require plenty of available information for the defender and neglect the frequent interactions between both players, which are unrealistic and impractical, and thus, are not suitable for our settings. As such, we provide the first defender strategy, that enjoys nice theoretical and practical performance guarantees, by applying the adversarial online learning approach. In particular, we model the repeated network interdiction game with no prior knowledge as an online linear optimization problem, for which a novel and efficient online learning algorithm, SBGA, is proposed, which exploits the unique semi-bandit feedback in network security domains. We prove that SBGA achieves sublinear regret against adaptive adversary, compared with both the best fixed strategy in hindsight and a near optimal adaptive strategy. Extensive experiments also show that SBGA significantly outperforms existing approaches with fast convergence rate.
Keywords: 
Conference Name: 26th International Joint Conference on Artificial Intelligence (IJCAI'17)
Location: Melbourne, Australia
Publisher: AAAI Press
Year: 2017
Accepted PDF File: Playing_Repeated_Network_Interdiction_Games_with_Semi-Bandit_Feedback_accepted.pdf
Permanent Link: https://dx.doi.org/10.24963/ijcai.2017/515
Reference: Q. Guo, B. An, and L. Tran-Thanh, “Playing repeated network interdiction games with semi-bandit feedback,” in Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI’17). AAAI Press, August 2017, pp. 3682–3690.
bibtex: 
@inproceedings{LILY-c129, 
    author = {Guo, Qingyu and An, Bo and Tran-Thanh, Long},
    title  = {Playing Repeated Network Interdiction Games with Semi-Bandit Feedback},  
    booktitle = {Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI'17)}, 
    year  = {2017}, 
    month = {August}, 
    pages = {3682-3690}, 
    location = {Melbourne, Australia},
    publisher = {AAAI Press},
 }