Empirical Bound Information-Directed Sampling for Norm-Agnostic Bandits
Piotr M. Suder, Eric Laber · 2025
Read Empirical Bound Information-Directed Sampling for Norm-Agnostic Bandits by Piotr M. Suder, Eric Laber (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-05098.txt.
Introduction
Piotr Suder and Eric Laber improve a bandit algorithm that usually needs a lucky guess to work well, in a paper from 2025. Bandit methods pick among options while learning which pays best. Information-directed sampling picks the option that teaches the most per unit of loss.
Its frequentist form needs a tight cap on the true parameter size, rarely known in advance. A bad cap piles up regret fast. Their fix rebuilds the cap from data as trials roll in, with high confidence. Mixed goals steer effort between shrinking the cap and hunting the best option. Proofs bound the regret without the starting guess. Benchmarks beat rival methods.
Catalog record
| CREATOR | Piotr M. Suder, Eric Laber |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-05098
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Empirical Bound Information-Directed Sampling for Norm-Agnostic Bandits Piotr M. Suder, Eric Laber Abstract Information-directed sampling (IDS) is a powerful framework for solving bandit problems which has shown strong results in both Bayesian and frequentist settings. However, frequentist IDS, like many other bandit algorithms, requires that one have prior knowledge of a (relatively) tight upper bound on the norm of the true parameter vector governing the reward model in order to achieve good performance. Unfortunately, this requirement is rarely satisfied in practice. As we demonstrate, using a poorly calibrated bound can lead to significant regret accumulation. To address this issue, we introduce a novel frequentist IDS algorithm that iteratively refines a high-probability upper bound on the true parameter norm using accumulating data. We focus on the linear bandit setting with heteroskedastic subgaussian noise. Our method leverages a mixture of relevant information gain criteria to balance exploration aimed at tightening the estimated parameter norm bound and directly searching for the optimal action. We establish regret bounds for our algorithm that do not depend on an initially assumed parameter norm bound and demonstrate that our method outperforms state-of-the-art IDS and UCB algorithms. Keywords and phrases: Bandit algorithms, information-directed sampling, parameter bounds, heteroskedastic noise. 1 Introduction We consider linear stochastic bandits ( Lattimore & Szepesvári, 2020 ) with heteroskedastic noise (see Weltz et al., 2023 , for applications of such models in marketing and other areas) . In this setting, information directed sampling (IDS) and upper confidence bound (UCB) algorithms have been shown to be extremely effective ( Auer, 2002 ; Abbasi-Yadkori et al., 2011 ; Kirschner & Krause, 2018 ; Kirschner et al., 2021 ) . However, many of these methods require strong prior information that can be used to inform a high-quality upper bound on the Euclidean norm of the parameter vector indexing the reward model. The choice of this bound is critical to algorithm performance. If the bound is too large, the algorithm risks incurring excess risk due to needless exploration, and if the bound is too small, the algorithm may fail to identify the optimal arm and thus suffer linear regret. To reduce sensitivity on a user-specified bound, we propose a novel version of frequentist IDS that uses accumulating data to generate a sequence of high-probability upper bounds on the norm of the reward model parameters. A key component of our method is a new information gain criterion that balances improving the requisite upper bound and regret minimization. Because improving the bound is critical to avoid over-exploration in early rounds of the bandit process, we develop a two-phase procedure that uses our new information criterion in the first phase and then defaults to a more standard IDS information criterion in the second phase. Unlike other bandit strategies, such as UCB ( Auer, 2002 ; Garivier & Cappé, 2011 ; Cappé et al., 2013 ; Zhou et al., 2020 ) or Thompson sampling (TS) ( Thompson, 1933 ; Agrawal & Goyal, 2013 ; Phan et al., 2019 ) , which encourage exploration indirectly by leveraging uncertainty about the optimal arm, IDS explicitly balances exploration and exploitation. It selects actions that minimize estimated instantaneous regret while maximizing expected information gain about model parameters. As shown by Russo & Van Roy (2014) and Kirschner & Krause (2018) , this approach allows IDS to avoid pitfalls inherent in UCB and TS-based algorithms, particularly in scenarios where certain suboptimal actions provide valuable information about the environment’s dynamics. In such cases, UCB and TS tend to overlook these actions, whereas IDS plays them early on, enabling faster learning of the optimal policy and ultimately achieving superior long-term performance. IDS was first introduced for Bayesian bandits by Russo & Van Roy (2014) and later adapted to the frequentist setting by Kirschner & Krause (2018) . Beyond the standard bandit setting, IDS has been applied to problems such as linear partial monitoring ( Kirschner et al., 2020 ) — a generalization of bandits where the observed signal on the environment model parameters is not necessarily the same as the reward to be optimized — as well as reinforcement learning ( Nikolov et al., 2019 ; Lindner et al., 2021 ; Hao & Lattimore, 2022 ) , where the actions taken by the agent influence the state of the environment and the reward dynamics. To the best of our knowledge, no previous work has considered either the strategy of iteratively refining and utilizing a high-probability upper bound on the parameter norm in the heteroskedastic subgaussian linear bandit setting we work with here, or the use of the information gain criterion for tightening the bound on the parameter norm we introduce. We are also not aware of any work utilizing a mixture of information gain criteria to encourage simultaneously obtaining different types of information about the dynamics of the environment. We note that while we introduce this idea in the form of an IDS algorithm, the approach of iteratively refining and utilizing a high-probability upper bound of the true parameter norm can be regarded as a more general design principle beyond its IDS implementation in this setting. The remainder of this manuscript is structured as follows. The next section provides a brief review of related work. Section 3 introduces the problem setup and notation used throughout the paper. In Section 4 , we present the necessary background on IDS. Section 5 introduces the novel empirical bound information-directed sampling (EBIDS) algorithm, which removes the need for a tight parameter norm bound to be known a priori . Section 6 establishes regret bound guarantees for EBIDS, and finally, Section 7 evaluates its empirical performance against competitor algorithms in a simulation study. 2 Related works The assumption that the norm of the parameter indexing the reward model is known or that one has a (relatively) tight upper bound on this quantity is abundant in the IDS and UCB literature ( Auer, 2002 ; Abbasi-Yadkori et al., 2011 ; Kirschner & Krause, 2018 ; Hung et al., 2021 ) ; it has also been used in Thompson sampling ( Xu et al., 2023 ) . This assumption commonly arises through the use of self-normalized martingale bounds and related concentration results ( Abbasi-Yadkori et al., 2011 ) . Consequently, algorithms constructed through these concentration results require a user-specified upper bound on the norm or the true parameter vector. Critically, as noted previously, the performance of these algorithms can be highly sensitive to the choice of these bounds. Despite this, only a handful of papers have attempted to alleviate this sensitivity. Gales et al. (2022) propose norm-agnostic linear bandits which construct a series of confidence ellipsoids for the true parameter vector along with a projection interval to construct a UCB-type algorithm. However, their algorithms rely on an initial burn-in during which regret accumulation is not controlled, e.g., it need not be sublinear. In our simulation experiments, we find that the impact of this initial exploration on accumulated regret is not negligible. Furthermore, as UCB algorithms, their methods do not explicitly make use of heteroskedasticity in the reward distributions across arms. The algorithm proposed by Ghosh et al. (2021) shares some underlying ideas with our method in the sense that they use multi-phase exploration to iteratively update