aiqbench analysis
This paper introduces Future Information-Directed Sampling (FIDS), a novel algorithm designed to address the exploration-exploitation trade-off in nonstationary bandit environments where future optimal actions differ significantly from current ones. By explicitly gathering predictive information about future arms and utilizing a supervised-learning-based approximation for posterior inference, FIDS outperforms classical methods like Thompson Sampling in dynamic settings while maintaining comparable regret bounds. The work advances the theoretical understanding of adaptive learning systems capable of anticipating environmental shifts rather than merely reacting to immediate uncertainty.
Future Information-Directed Sampling for Bayesian Nonstationary Bandits
arXiv:2609.33981v1 Announce Type: new 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.
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.
18 pages. An earlier version appeared at the ICML 2026 DEMO Workshop
Machine Learning (cs.LG)
arXiv:2609.33981 [cs.LG]
(or arXiv:2609.33981v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.33981 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 248 words
Related coverage
Generalization and infinite width
LessWrong · Aug 1, 2026
Information-Directed Sampling for Causal Bandits
arXiv · Jul 20, 2026
Information-Directed Sampling for Causal Bandits
arXiv · Sep 22, 2026
Why do models task game?
AI Alignment Forum · Aug 6, 2026