2022/05/19 by Avishek Ghosh, Ghosh, Avishek, Abishek Sankararaman +1 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2205.09899
openalex publication_date 2022/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove an instance independent (poly) logarithmic regret for stochastic contextual bandits with linear payoff. Previously, in \citechu2011contextual, a lower bound of O(√(T)) is shown for the contextual linear bandit problem with arbitrary (adversarily chosen) contexts. In this paper, we show that stochastic contexts indeed help to reduce the regret from √(T) to \polylog(T). We propose Low Regret Stochastic Contextual Bandits (LR-SCB), which takes advantage of the stochastic contexts and performs parameter estimation (in ℓ2 norm) and regret minimization simultaneously. LR-SCB works in epochs, where the parameter estimation of the previous epoch is used to reduce the regret of the current epoch. The (poly) logarithmic regret of LR-SCB stems from two crucial facts: (a) the application of a norm adaptive algorithm to exploit the parameter estimation and (b) an analysis of the shifted linear contextual bandit algorithm, showing that shifting results in increasing regret. We have also shown experimentally that stochastic contexts indeed incurs a regret that scales with \polylog(T).