Abstract
In many real-world applications of multi-armed bandit problems, both rewards and contexts are often influenced by confounding latent variables which evolve stochastically over time. While the observations might suggest a complex, non-stationary environment, this paper demonstrates that by modeling the underlying latent state dynamics, the problem can be effectively "linearized" to achieve superior performance and provide new theoretical regret bounds.
Introduction
In standard contextual bandits, we assume a relatively stable relationship between an observed context (like a user's profile) and the reward (like a click). However, real-world scenarios are often "non-stationary" and "latent." For example, in a personalized tutoring AI, the reward (a student getting an answer right) depends on the student’s internal state of knowledge, which changes over time as they learn. We cannot observe this internal state directly; we only see contexts like response times.
Most existing bandit algorithms struggle in these settings because the relationship between observations and rewards is nonlinear and changes as the hidden state evolves. This paper addresses this by asking: Can we leverage the underlying causal structure of these hidden dynamics to simplify the problem back into something we know how to solve?
Methods
The authors propose a two-stage pipeline that reduces a complex latent dynamical problem to a standard linear bandit problem:
- Latent State Inference: The environment is treated as a Hidden Markov Model (HMM). Online Expectation-Maximization (EM) is used to recursively update a "belief" (a posterior probability distribution) about the current hidden state based on observed contexts and rewards.
- Linearization: The key insight (Lemma 1) is that while the world is nonlinear, the expected reward is a linear function of the posterior probabilities of the hidden states.
- Bandit Algorithms: Two new algorithms are introduced: $L^2TS$ (Latent Linear Thompson Sampling) and $L^2UCB$ (Latent Linear Upper Confidence Bound). These use the posterior distribution as a "feature vector" for linear bandit subroutines.
Experiments and Results
The researchers evaluated their approach on synthetic discrete tasks and a Rover Mining Application. The rover simulation used real-world geological data where a rover moves across land blocks to mine ore. The "context" is an X-ray fluorescence reading, and the "reward" is the grade of the ore found.
In both synthetic and real-world-inspired tasks, $L^2TS$ and $L^2UCB$ significantly outperformed baselines like Exp4.P (which couldn't model the dynamics) and Discounted Thompson Sampling (which couldn't share information across different contexts).
Key results include:
- Superior Regret: The algorithms achieve lower cumulative regret by effectively modeling state transitions.
- Efficiency: Using online EM rather than intensive particle filtering allows the algorithms to scale well to long time horizons.
- Theoretical Bounds: The authors derived a novel problem-dependent regret bound of $O(\sqrt{T})$ for linear Thompson sampling in non-stationary settings.
Key Insights and Conclusion
The most powerful idea presented is the "Probability-Linearity Bridge": probabilities can linearize expectations. Even if a system is wildly nonlinear, if you can estimate the probability of being in specific states, the expected reward becomes a weighted linear sum. This reduction allows the model to inherit decades of theoretical guarantees from the linear bandit setting.
While the model currently assumes a known number of latent states, it provides a robust foundation for handling non-stationarity. Future work may involve learning the dimensionality of the latent space dynamically and extending the framework to more complex causal graphs with multiple interacting latent variables.
Summary updated