New method improves decision making in changing bandit problems
Future Information-Directed Sampling for Bayesian Nonstationary Bandits
Machine Learning
Summary
When making choices over time, like picking the best option among many, traditional methods look only at what is best right now. This paper presents a new method that tries to learn about what might be the best choice in the future, especially when things change over time. The authors show their method works almost as well as popular ones that assume stable conditions but can better handle changing situations. They also offer a way to teach this method from pre-collected data, making it practical to use.
What this means in practice
- •For online advertisement teams: Improve ad selection by better anticipating future user preferences in environments where interests change over time.
- •For robot control engineers: Enable robots to adapt exploration strategies in tasks where optimal actions shift unpredictably during operation.
Authors
Yichen Song, Alessio Russo, Aldo Pacchiano
Abstract
Exploration--exploitation is a central trade-off in bandit learning. While classical algorithms such as upper confidence bound methods and Thompson Sampling effectively balance this trade-off in stationary environments, their exploration strategies mainly reduce uncertainty about the current optimal arm, which can be insufficient in nonstationary settings where future optimal arms may differ substantially from current ones. In this paper, we propose Future Information-Directed Sampling (FIDS), a new algorithm for Bayesian nonstationary bandits that explicitly explores to gather information about future optimal arms. We show that FIDS achieves regret comparable to Thompson Sampling up to a small constant factor, while being able to exploit predictive information structures that conventional exploration objectives fail to capture. To address the practical difficulty of posterior inference, we further propose a supervised-learning-based approximation framework that learns the FIDS policy from offline data, and demonstrate its effectiveness on synthetic benchmarks.