2023/07/21 by Khashayar Khosravi, Renato Paes Leme, Khosravi, Khashayar +5
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Smart Grid Energy Management
paper · pdf · doi:10.48550/arxiv.2307.11655
openalex publication_date 2023/07/21 · openalex created_date 2023/07/25 · openalex updated_date 2026/07/28
We propose a model for learning with bandit feedback while accounting for deterministically evolving and unobservable states that we call Bandits with Deterministically Evolving States (B-DES). The workhorse applications of our model are learning for recommendation systems and learning for online ads. In both cases, the reward that the algorithm obtains at each round is a function of the short-term reward of the action chosen and how "healthy" the system is (i.e., as measured by its state). For example, in recommendation systems, the reward that the platform obtains from a user's engagement with a particular type of content depends not only on the inherent features of the specific content, but also on how the user's preferences have evolved as a result of interacting with other types of content on the platform. Our general model accounts for the different rate λ∈ [0,1] at which the state evolves (e.g., how fast a user's preferences shift as a result of previous content consumption) and encompasses standard multi-armed bandits as a special case. The goal of the algorithm is to minimize a notion of regret against the best-fixed sequence of arms pulled, which is significantly harder to attain compared to standard benchmark of the best-fixed action in hindsight. We present online learning algorithms for any possible value of the evolution rate λ and we show the robustness of our results to various model misspecifications.