A Direct Approach for Handling Contextual Bandits with Latent State Dynamics

We consider a linear contextual bandit model where contexts and rewards are governed by a finite hidden Markov chain. We first revisit the simplified model by Nelson et al. (2022), in which rewards are linear functions of the posterior probabilities over the hidden states given the observed contexts (called beliefs), rather than functions of the hidden states themselves. This simplified model may be handled through a direct reduction to standard linear contextual bandits. We extend the theoretical analysis of this reduction to take into account the estimation of the parameters of the hidden Markov model [HMM] in the regret bound and to provide high-probability bounds not depending anymore on the reward functions and only depending on the model through the estimation of the HMM parameters. Second, and most importantly, we instead study the more natural and more complex model incorporating direct dependencies in the hidden states (on top of dependencies on the observed contexts, as is natural for contextual bandits). Under a classic HMM forgetting condition, the main algorithmic tool introduced to cope with the various statistical dependencies that the reward structure introduces is to only periodically update reward-model parameters.

Many real-world decision-making systems, for recommendation or pricing of financial products, operate in environments where important factors influencing outcomes are hidden and change over time (such as economic cycles). Contextual bandits provide a framework for learning effective decisions from limited feedback, but most existing methods assume that all relevant information is directly observable. This work studies contextual bandits with latent state dynamics modeled by a hidden Markov model [HMM]. We first revisit a simplified setting where rewards depend on inferred probabilities over hidden states and strengthen its theoretical guarantees by accounting for uncertainty in learning the HMM itself. We then study a more realistic setting where rewards depend directly on hidden states, creating complex temporal dependencies. To address these challenges, we introduce an algorithm that updates reward estimates only periodically. Our results advance the theory of online learning and decision-making in realistic environments with evolving latent state structure.