Robust Bandit Learning with Imperfect Context

2021/02/09 by Jianyi Yang, Shaolei Ren, Yang, Jianyi +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics #cs.LG

paper · pdf · doi:10.48550/arxiv.2102.05018

openalex publication_date 2021/02/09 · arxiv created 2021/04/04 · arxiv updated 2021/04/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A standard assumption in contextual multi-arm bandit is that the true context is perfectly known before arm selection. Nonetheless, in many practical applications (e.g., cloud resource management), prior to arm selection, the context information can only be acquired by prediction subject to errors or adversarial modification. In this paper, we study a contextual bandit setting in which only imperfect context is available for arm selection while the true context is revealed at the end of each round. We propose two robust arm selection algorithms: MaxMinUCB (Maximize Minimum UCB) which maximizes the worst-case reward, and MinWD (Minimize Worst-case Degradation) which minimizes the worst-case regret. Importantly, we analyze the robustness of MaxMinUCB and MinWD by deriving both regret and reward bounds compared to an oracle that knows the true context. Our results show that as time goes on, MaxMinUCB and MinWD both perform as asymptotically well as their optimal counterparts that know the reward function. Finally, we apply MaxMinUCB and MinWD to online edge datacenter selection, and run synthetic simulations to validate our theoretical analysis.

Citations

• Finite-Time Analysis of Kernelised Contextual Bandits
• Doubly Robust Policy Evaluation and Learning
• Online Learning with Predictable Sequences
• Analysis of Thompson Sampling for the multi-armed bandit problem
• The Nonstochastic Multiarmed Bandit Problem
• Learning to Forget: Continual Prediction with LSTM
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Adversarial Attacks on Stochastic Bandits
• Adversarially Robust Optimization with Gaussian Processes
• Data Poisoning Attacks on Stochastic Bandits
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits

Related

• Contextual Blocking Bandits
• A Contextual Bandit Bake-off
• Robust Contextual Linear Bandits
• Greedy Bandits with Sampled Context
• Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach