# Information maximization for a broad variety of multi-armed bandit games

Alex Barbier-Chebbah, Christian L. Vestergaard, Jean-Baptiste Masson

► To cite this version:

Alex Barbier-Chebbah, Christian L. Vestergaard, Jean-Baptiste Masson. Information maximization for a broad variety of multi-armed bandit games. 2025. pasteur-04997815

HAL Id: pasteur-04997815

https://pasteur.hal.science/pasteur-04997815v1

Preprint submitted on 19 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Information maximization for a broad variety of multi-armed bandit games

Alex Barbier-Chebbah,¹,²,* Christian L. Vestergaard,¹,² and Jean-Baptiste Masson¹,²,†

¹Institut Pasteur, Université Paris Cité, CNRS UMR 3571, Decision and Bayesian Computation, 75015 Paris, France.

²Épimethée, Inria, Paris, France.

(Dated: March 19, 2025)

Information and free-energy maximization are physics principles that provide general rules for an agent to optimize actions in line with specific goals and policies. These principles are the building blocks for designing decision-making policies capable of efficient performance with only partial information. Notably, the information maximization principle has shown remarkable success in the classical bandit problem and has recently been shown to yield optimal algorithms for Gaussian and sub-Gaussian reward distributions. This article explores a broad extension of physics-based approaches to more complex and structured bandit problems. To this end, we cover three distinct types of bandit problems, where information maximization is adapted and leads to strong performance. Since the main challenge of information maximization lies in avoiding over-exploration, we highlight how information is tailored at various levels to mitigate this issue, paving the way for more efficient and robust decision-making strategies.

## I. INTRODUCTION

Decision-making under partial information is a critical challenge faced by biological organisms (in particular relating to taxis or cognition [1–4]), but also extends to broader fields such as Bayesian optimization, robotics and machine learning [5–12]. To perform effectively, the decision-making agent must account for the physical structure of both the environment and decision problem to formulate its strategy, which often involves incorporating complex priors or tailored design elements [13–15]. To this end, general physics principles can serve as key tools, offering observables that inherently adapt to the underlying structure of the environment [16–19]. These principles are also designed to adapt to new information, even conflicting, or when the agent is limited to partial or noisy feedback from a fluctuating environment [5]. They have been applied across various domains, including modeling decision-making in the brain using the free-energy principle [20], optimizing the accuracy-complexity tradeoff through the information bottleneck principle [21], and facilitating navigation in fluctuating environments via information maximization strategies [5].

In the information-maximization framework, the agent seeks to maximize information about one or more relevant observables. The agent's choice is thus driven by the option that maximizes the expected information gain. Due to its versatility in accommodating various environmental structures, this principle has proven its broad applicability across both applied and theoretical areas [22, 23]. Notable applications include robotics, where information sharing enhances collective decision-making [13], and taxis with the search for olfactory sources in turbulent flows [24, 25]. Maximum entropy principles also underpin approaches in Bayesian optimization and reinforcement learning [10, 11, 14].

Multi-armed bandit (MAB) problems constitute a generalized framework for addressing decision-making in fluctuating and partially known environments [1, 26], and has garnered significant attention in a wide range of applications, spanning from neuroscience and healthcare to recommender systems and finance [3, 26–34] In the multi-armed bandit problem, an agent is presented with a set of possible actions, or "arms", each associated with a probabilistic reward (akin to a multi-armed slot machine game). The agent must optimize its actions to achieve a specified goal, which generally involves maximizing cumulative rewards over a fixed or infinite horizon. However, it may occasionally involve identifying a subset of optimal arms or exploring its available options [Fig. 1 a]). Hence, classic bandit settings address the exploration-exploitation dilemma and provide strategies that may achieve asymptotic optimality [35–37]. MAB problems have rapidly expanded to cover many more complex decision scenarios. A first main class of problems focuses on pure exploration, where the agent's goal is solely to identify a single optimal action or a subset of promising actions, without incurring penalties for sampling suboptimal ones [38–42] [Fig. 1 b)]. In essence, pure exploration aims to optimize a test phase to identify reliable candidates using a minimal amount of resources while suffering no penalty for exploration. Following such a test phase, the exploitation phase may ensue, but it is not optimized in this context. Such challenges arise in lower-risk scenarios like cosmetic drug trials or numerical resource allocation. A complementary area is termed contextual bandits, which have found application for example in personalized recommendations and pandemic control [43, 44]. A notable example is linear bandit problems where actions' outcomes, because of an underlying structure between arms, are correlated [26, 45–48], allowing one to gain information about other actions than the one performed [Fig. 1 c)]. Lastly, many-armed problems address scenarios where the number of available actions is large compared to the time horizon, requiring the agent to concentrate on sufficiently promising solutions [Fig. 1

<footnote>* alex.barbier-chebbah@pasteur.fr</footnote>

<footnote>† jbmasson@pasteur.fr</footnote>
<figure><img src="image_2.png" /><figcaption>FIG. 1. Illustrations of multi-armed bandit settings addressed in this work. **a)** Illustration of the multi-armed bandit principle. At each time step *t*, the agent chooses an action *i* = *A*<sub>*t*</sub> that returns a reward *x*<sub>*t*</sub> drawn from a distribution of unknown mean μ<sub>*i*</sub>. The arm is denoted as *A*<sub>*t*</sub> when it is a vector and as *a*<sub>*t*</sub> when it is an index. By accumulating rewards, the agent also gathers information about the average rewards of the arms and optimizes its decision-making policy. The specific goals of the agent will vary depending on the bandit problem. **b)** General principle of the Explore-*m* problem. Here, the goal is to identify the *m* arms with the highest mean rewards (red arms). To this end, our approach introduces a well-designed separator θ<sub>b</sub> between the current *m* highest arms (forming the set M<sub>*t*</sub>) and the remaining arms at each time. Our algorithm chooses the arm to maximize the information gain of the separator's effectiveness in distinguishing both subsets (cumulative distribution pictured in yellow and red below). **c)** Illustration of the linear bandit setting. Here, arms are *d*-dimensional vectors resampled at each time step. The scalar between the arm vector and a constant but unknown vector gives the mean reward value θ<sub>*</sub>. Because of this geometric dependency on the reward, pulling an arm also provides information on the expected results of the others. **d)** Illustration of the many-arms settings. Here, the agent has a finite duration, known in advance to maximize its gains. Because there is no time to explore all the arms thoroughly, the agent needs to focus on a small subset of arms to isolate a sufficiently promising solution before time runs out. Our approach balances two possible actions: exploring a new arm (represented in blue) or greedily exploiting the current empirical best solution (represented in green) based on the empirical mean μ<sub>M<sub>*t*</sub></sub>. We model the upcoming losses as a function to guide the decision-making process.</figcaption></figure>

**d)**. This challenge of finite resources resonates with applications in pharmaceutical and medical trials [49, 50]. Such settings offer various extensions and readily apply to cases where the number of arms is infinite [51–54]. Additional extensions of MAB problems explore dynamic rewards, adversarial settings, and multi-agent interactions, focusing on competition, congestion, and overexploitation respectively, but are not investigated further here [26, 42, 45, 55–57].

We address here three classes of active bandit prob-
lems to show how the general principles of informa-
tion maximization can be adapted to address structured
decision-making problems. Although a wide variety of
bandit games and associated strategies have been stud-
ied in recent years, strategies developed to address them
primarily rely on a few core principles, most notably
confidence bounds on the individual arms’ mean re-
wards, which frequently drive the decision-making pro-
cess [37, 58–60]. Although there are exceptions to this
rule and several alternative approaches have been inves-
tigated [36, 48, 55, 61–64], there is still a crucial need to
develop original approaches, especially when addressing
more complex bandit challenges.

Recently, the information maximization principle has
been shown to achieve strong results in classical ban-
dit settings, displaying state-of-the-art empirical perfor-
mance both at short and long time horizons and when
handling multiple arms. [62, 65]. Information maximiza-
tion algorithms (and information-based algorithms, more
generally) aim to minimize the expected entropy (a func-
tional) of a key variable within the system.

The first difficulty in applying information-based algo-
rithms is that they rely on integrating such a function

that often has no known analytical solution. Their ap-
plication thus relies on numerical integration, which both
hinders theoretical analysis of their statistical perfor-
mance and increases their computational costs [65]. Re-
cently, we introduced a new class of approximate informa-
tion maximization (AIM) algorithms [65, 66] that rely on
tractable approximations of the entropy. The analytical
tractability of the AIM algorithms significantly increases
their computational efficiency, opening up for their appli-
cation to a wider range of bandit problems [65, 66]. Fur-
thermore, it enabled us to rigorously prove their asymp-
totic optimality in the classic setting with Gaussian and
sub-Gaussian rewards [66], confirming the heuristic ob-
servation that information maximization can drive opti-
mal learning and optimization.

A second challenge with information-based approaches
remains choosing the observable and functional to ap-
propriately capture the underlying structure of the ban-
dit problem and ensure an efficient policy. The main
challenge of information maximization is to avoid over-
exploration [62], requiring careful design of the observ-
ables or features on which entropy minimization is per-
formed as well as of the approximations performed to
make the algorithms tractable [65]. In this work, we show
how the approximate information maximization princi-
ple can be applied to the three distinct bandit topics
discussed above, namely the pure exploration problem
of explore-*m* selection, contextual bandits exemplified by
linear bandits, and many-armed bandits. Since the three
problems each involve distinct levels of exploration, we
discuss how relevant information is accessed within each
context. This allows us to extend our building principle
to a broader range of structures not specifically meant
for pure exploration. We provide numerical evaluations of the performance of the approximate information-based approaches and compare it to well-established algorithms in each case. A key challenge left for future work is to establish theoretical bounds for the algorithms investigated below.

## II. STRUCTURE OF THIS PAPER

We detail our approach to the three distinct bandit settings mentioned above. For each case, we follow the same three steps: 1) we introduce the bandit game, defining the key elements that are required of an efficient strategy, and provide an overview of existing strategies to tackle the problem; 2) we detail our design principles for an information-based approach, followed by the development of our approximation scheme that yields a tractable expression and enables an efficient implementation; 3) finally, we investigate the performance of the resulting algorithm, its specific features, and we discuss potential extensions.

## III. EXPLORE-M BANDITS

### A. Setting and core insights

We first consider a well-known multiple-arm identification problem, commonly referred to as the Explore-$m$ problem under the probably approximately correct (PAC)-identification formulation [41, 67–70]. In these problems, we aim to identify a subset of $m$ promising arms (i.e individual actions or choices) among $n$ possible options [Fig. 1(b)]. Each arm is associated with a reward distribution of unknown mean parameter $\mu_i$ (supported on $[0, 1]$ without loss of generality). At each time step $t$, the agent selects an arm $i_t$ and obtains an associated stochastic reward $x_t$ sampled from the $i$th arm's reward distribution. By sampling the environment, the agent sequentially accumulates information on the parameters of the sampled arms' means $\mu_i$. For simplicity, we sort the arms according to their (unknown) means $\mu_n \le \mu_{n-1} < \dots < \mu_m < \dots < \mu_1$.

Explore-$m$ aims to identify the subset of $m$ arms among the highest means up to $\epsilon$ termed $\epsilon$-optimal. More precisely, an arm $i$ is defined to be $\epsilon$-optimal, iff $\mu_i \ge \mu_m - \epsilon$ for some $\epsilon \in (0, 1)$ where $\mu_m$ is the $m$th-highest mean. This criterion prevents the algorithm from spending excessive time distinguishing between arms when $\mu_m$ and $\mu_{m+1}$ are infinitesimally close, ensuring it focuses on more meaningful scenarios.

Since no additional cost is incurred by sampling suboptimal arms, the algorithm's efficiency is evaluated based solely on its ability to identify such a subset both quickly and with high confidence. Two standard evaluation criteria are commonly considered [40]. In the fixed-budget

setting, the algorithm has a finite amount of time to identify the subset, and its performance is measured through the probability of returning an $\epsilon$-optimal subset. In contrast, the PAC formulation requires the algorithm to stop when the probability of returning an $\epsilon$-optimal subset exceeds $1 - \delta$, with $\delta \in (0, 1)$, with the goal of minimizing the stopping time [41]. We focus here on the PAC formulation in the following.

Algorithms for pure exploration problems can broadly be divided into two categories. In the **sample and reject strategies**, a subset of remaining arms is all sampled at each round. Next, a rejection criteria discards from the remaining subset sufficiently drawn arms. This process is repeated sequentially until a stopping criteria is met [54, 71]. For **adaptive sampling strategies**, at each time step, one or two arms with the most critical confidence regarding the subset identification are selected and pulled, with the arms' indices changing over time [40, 41, 72]. Most methods rely on upper and lower bounds on confidence intervals on the arms' means, rooted in the general class of upper confidence bound (UCB) algorithms [39, 71–73]. By comparing the upper confidence bounds of likely suboptimal arms with the lower confidence bounds of the promising subset, these methods can derive an efficient decision-making procedure. However, the stopping criteria are highly dependent on the confidence interval design, which may become less effective when facing various reward distributions or more complex scenarios. For a deeper exploration of the sampling complexity of such strategies under different reward distributions, we refer to [67, 69].

Since no explicit cost is incurred by selecting arms, we would expect a strategy focused solely on acquiring information about the best subset to be efficient. To this end, we developed a fully information-based strategy, ensuring feasibility and tractability through successive derivations, approximations, and simplifications. We focus on the PAC setting but discuss its extension to other pure exploration settings.

### B. Design principle

We first introduce additional notation specific to the Explore-$m$ problem. In each round $t$, each arm $i$ is characterized by its empirical mean $\hat{\mu}_i = \frac{\sum_{t:t_i=t} x_t}{t}$ and the number of times it has been drawn $t_i$ (where we have omitted the subscript $t$ to avoid clutter). $\mathcal{H}_t = \{(i_1, x_1), (i_2, x_2), \dots, (i_t, x_t)\}$ represents the complete history of chosen arms and observed rewards. The subset of arms with the current $m$ highest empirical means is denoted $\mathcal{M}_t$ with associated sets of true (hidden) mean values, $\{\mu_{\mathcal{M}_t}\}$, and empirical means, $\{\hat{\mu}_{\mathcal{M}_t}\}$. The equivalent notations for the remaining arms are $\mathcal{D}_t = \{n\} \setminus \mathcal{M}_t$, $\{\mu_{\mathcal{D}_t}\}$, and $\{\hat{\mu}_{\mathcal{D}_t}\}$, respectively. We also denote the worst selected mean by $\hat{\mu}_{\text{top}} = \min(\{\hat{\mu}_{\mathcal{M}_t}\})$ and the best unselected by $\hat{\mu}_{\text{bot}} = \max(\{\hat{\mu}_{\mathcal{D}_t}\})$.

A promising candidate distribution for information
maximization is the probability of $\mathcal{M}_t$ being $\epsilon$-optimal, i.e., $\mathbb{P}(\min(\{\mu_{\mathcal{M}_t}\}) > \max(\{\mu_{\mathcal{D}_t}\}) - \epsilon|\mathcal{H}_t)$. Unfortunately, this posterior distribution is analytically intractable in practice. Additionally, since the arms are not identically distributed, applying asymptotic extreme value statistics is also challenging without approximations.

Therefore, we adjust the decision process as follows. We introduce $\theta_b$ as a separator value between the observed sets $\{\hat{\mu}_{\mathcal{M}_t}\}$ and $\{\hat{\mu}_{\mathcal{D}_t}\}$ and compare all the arms' mean likelihoods relative to $\theta_b$. In other words, we now focus on comparing the arms' posterior probabilities of their means being above or below $\theta_b$, given by

$$ P_{\text{top}} = \mathbb{P} \left( \min(\{\mu_{\mathcal{M}_t}\}) > \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t \right) \\ = \prod_{i \in \mathcal{M}_t} \mathbb{P} \left( \mu_i \ge \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t \right), \quad (1) $$

and

$$ P_{\text{bot}} = \mathbb{P} \left( \max(\{\mu_{\mathcal{D}_t}\}) < \theta_b + \frac{\epsilon}{2} | \mathcal{H}_t \right) \\ = \prod_{i \in \mathcal{D}_t} \mathbb{P} \left( \mu_i \le \theta_b + \frac{\epsilon}{2} | \mathcal{H}_t \right), \quad (2) $$

respectively.

Notably, if both events occur, $\mathcal{M}_t$ is $\epsilon$-optimal, making Eqs. (1) and (2) an effective proxy to derive an information maximization strategy. This leads us to a policy that selects the arm maximizing $P_{\text{bot}}P_{\text{top}}$ growth. Leveraging the arms' independence, we can derive a straightforward expression for their expected increases should each arm be selected (see Supplementary Material Section S7 for details):

$$ \frac{\Delta_{i \in \mathcal{M}_t} P_{\text{top}} P_{\text{bot}}}{P_{\text{top}} P_{\text{bot}}} = \frac{\Delta \mathbb{P} \left( \mu_i \ge \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t \right)}{\mathbb{P} \left( \mu_i \ge \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t \right)}, \quad (3) $$

and

$$ \frac{\Delta_{i \in \mathcal{D}_t} P_{\text{bot}} P_{\text{top}}}{P_{\text{top}} P_{\text{bot}}} = \frac{\Delta \mathbb{P} \left( \mu_i \le \theta_b + \frac{\epsilon}{2} | \mathcal{H}_t \right)}{\mathbb{P} \left( \mu_i \le \theta_b + \frac{\epsilon}{2} | \mathcal{H}_t \right)}. \quad (4) $$

where the increment $\Delta$ symbols may either account for the expected discrete increment or continuous gradient along arm $i$. Exact expressions can be derived for both choices, and for simplicity, we opt for the latter one (see Supplementary Material Section S7B). The selected arm is then given by

$$ a_t = \underset{i \in \mathcal{M}_t \cup \mathcal{D}_t}{\operatorname{argmax}} (\Delta_{i \in \mathcal{D}_t} P_{\text{bot}} P_{\text{bot}}, \Delta_{i \in \mathcal{M}_t} P_{\text{top}} P_{\text{bot}}). \quad (5) $$

This approach offers two main advantages. First, the information gain is significantly simplified as it relies on a single-point evaluation. Second, it directly provides a well-defined stopping criterion for the PAC setting. As noted above, the joint probabilities Eqs. (1) and (2) lower

bounds the probability of returning an $\epsilon$-optimal subset. As both $P_{\text{top}}$ and $P_{\text{bot}}$ are easy to evaluate, they can be directly translated into a stopping criterion. In other words, the algorithm stops when

$$ P_{\text{bot}} P_{\text{top}} > 1 - \delta, \quad (6) $$

is satisfied for the first time. Hence, the decision-making process is designed to optimize the stopping time. The final step consists in choosing the $\theta_b$ value. We seek an optimal separator, i.e., the $\theta_b$ value that enables fulfilling Eq. (6) in minimal time. Introducing the total time needed to be spent on sampling each subset $T_{\text{top}}$ and $T_{\text{bot}}$ to verify Eq. (6) (regarding the current arms' mean state), $\theta_b$ can be expressed as

$$ \theta_b = \underset{\theta \in [\hat{\mu}_{\text{bot}}, \hat{\mu}_{\text{top}}]}{\operatorname{argmin}} (T_{\text{bot}}(\theta_b) + T_{\text{top}}(\theta_b) | \text{Eq. (6) is verified}). \quad (7) $$

Unfortunately, there is no exact and tractable solution for 7. Hence, we seek a tractable approximation of $(\theta_b, T_{\text{bot}}(\theta_b), T_{\text{top}}(\theta_b))$. To this end, we isolated from the posterior distributions of the maximum and the minimum, respectively, of $\{\mu_{\mathcal{M}_t}\}$ and $\{\mu_{\mathcal{D}_t}\}$, the following closed-form approximations (Supplementary Material Section S7):

$$ \theta_b = \frac{\epsilon}{2} + \hat{\mu}_{\text{top}} - \sqrt{\frac{m}{T_{\text{top}}(\theta_b)}} \left[ \frac{2 \ln(m) - \ln(-\ln(1 - \frac{\delta}{2}))}{\sqrt{2 \ln(m)}} \right], \quad (8) $$

and

$$ \theta_b = -\frac{\epsilon}{2} + \hat{\mu}_{\text{bot}} + \sqrt{\frac{n-m}{T_{\text{bot}}(\theta_b)}} \left[ \frac{2 \ln(n-m) - \ln(-\ln(1 - \frac{\delta}{2}))}{\sqrt{2 \ln(n-m)}} \right]. \quad (9) $$

By inserting Eq. (9) and Eq. (8) into Eq. (7), we obtain a closed system from which we derive a tractable expression of $\theta_b$ given in Eq. (S20). We refer to the Supplementary Material Section S7 for a complete and detailed review of all the approximations and derivations. Briefly, using an extreme value analysis, we approximated $P_{\text{bot}}$ and $P_{\text{top}}$ by Gumbel laws parametrized by $\hat{\mu}_{\text{top}}$, $\hat{\mu}_{\text{bot}}$, $T_{\text{bot}}(\theta_b)$ and $T_{\text{top}}(\theta_b)$. Next, they are evaluated when Eq. (6) is verified, leading to Eq. (8) and Eq. (9).

Pseudocode for the resulting algorithm referred to as PacAIM is presented in Alg. 1.

### C. Results

To evaluate the performance of PacAIM, we compare in Fig. 2 its stopping performance with the LUCB1 algorithm [41], a well-established algorithm in the PAC setting. The reward distributions are Gaussian with unknown mean values in [0, 1] and unit variance.
<caption>**Algorithm 1:** Algorithm for Explore-*m* Gaussian bandits</caption>

**Algorithm 1:** Algorithm for Explore-*m*
Gaussian bandits
**Data:** *n*, *m*, *ϵ*, *δ*, *T* > *n* (optional)
Draw all arms once, observe rewards and update
statistics for all arms, *t* ← *n*
**continue** ← **True**
**while** continue **do**
| // Stopping criteria
| **M**<sub>*t*</sub> = argmax<sub>*I*subseteq{*1,...,n*}, |*I*|=*m*</sub> (hat<sub>*i*</sub>) and hat<sub>top</sub> = min{hat<sub>*M*<sub>*t*</sub></sub>}
| **D**<sub>*t*</sub> = {*n*} \ **M**<sub>*t*</sub> and hat<sub>bot</sub> = max{hat<sub>*D*<sub>*t*</sub></sub>}
| Evaluate θ<sub>*b*</sub> using Eq. (7)
| Evaluate *P*<sub>top</sub> and *P*<sub>bot</sub> using Eqs. (1) and (2)
| **if** Eq. (6) or *t* = *T* **then** continue ← **False**
| **else** Pull *a*<sub>*t*+1</sub> and observe *X*<sub>*t*+1</sub>(*a*<sub>*t*+1</sub>)
| Select *a*<sub>*t*</sub> with Eq. (5) // Arm selection
|   hat<sub>*a*<sub>*t*</sub> ← <sup>hat<sub>*a*<sub>*t*</sub>*t*<sub>*t*</sub>*+*X*<sub>*t*+1</sub>(*a*<sub>*t*+1</sub>)</sup>⁄<sub>*t*<sub>*t*</sub>+1</sub></sup>
|   *t*<sub>*t*+1</sub> ← *t*<sub>*a*</sub> + 1 // Update statistics
| return **M**<sub>*t*</sub> // ϵ-optimal set

In the first experiment, the ϵ-optimal subset is formed
by mean rewards drawn uniformly from [0.9, 1], while the
remaining mean rewards are drawn from [0.0, 0.8]. To as-
sess the algorithm’s performance on more complex tasks,
we also evaluate a scenario where all ϵ-optimal rewards
are set to 0.8 and the remaining mean rewards are set to
0.7. The stopping time is measured for different numbers
of arms while maintaining the ratio *m* = *n*/5.

In both cases, PacAIM outperforms LUCB1, demonstrat-
ing the ability of our approximation to accurately
capture the significant contributions of all arms near the
θb value. Notably, we emphasize that using a decision
procedure directly tied to the stopping criteria enables
the algorithm to sample all relevant arms efficiently, mini-
mizing the stopping time. See the Supplemental Material
Sections S10 and S10B for numerical details and addi-
tional experiments.

To conclude on the Explore-*m* setting, we take a mo-
ment to highlight some additional observations. First,
θ_b depends on the current state of the game and evolves
over time to adapt to the reward distributions. Next,
the algorithm adjusts by sampling the arms that provide
the most information relative to this updated separator
value.

It is worth noting that our expression is designed for a
subset consisting of multiple arms. For single-arm iden-
tification, one may replace Eq. (8) by directly expressing
θ_b in terms of T_top using P(μ_top ≥ θ_b - ε/2 | H_t) = 1 - δ/2.
Furthermore, the expressions in Eqs. (8) and (9) are de-
rived for Gaussian rewards, but equivalent formulations
can be obtained for various distribution families [74].

As a result, our algorithm is readily adaptable to more
complex reward structures, including those with power-
law tails, which lead to extreme value statistics scal-
ing functions, such as Fréchet or Weibull distributions
[74]. Altogether, these first results highlight the poten-

<figure><img src="image_3.png" /><figcaption>FIG. 2. Stopping time of Explore-*m* algorithms for Gaussian rewards. The stopping time, i.e., the time when the stopping criteria for each algorithm is met, is measured for different numbers of arms *n*. In blue our algorithm, and in red LUCB1 given in [41]. The *ϵ*-optimal subset size verifies *m* = *n*/5. In a) the mean rewards value are sampled from two disjoint ensemble [0, 0.8] and [0.9, 1] for the *ϵ*-optimal subset, with confidence parameters *ϵ* = 0.05, *δ* = 0.1. b) Suboptimal mean rewards value are all set to 0.7 while *ϵ*-optimal to 0.8, with confidence parameters *ϵ* = 0.05, *δ* = 0.02. The time is averaged over 100 runs with standard deviation indicated. See Sections S10 and S10B for numerical details and success probability rate.</figcaption></figure>

tial for extending information-based strategies to tackle
more general pure exploration problems [38, 75, 76]. The
design of approximations and the choice of observables
should be addressed in a problem-specific manner. How-
ever, our work can be easily adapted to threshold iden-
tification or gap identification problems [77, 78], where
the focus is on determining the gap between subsets.
Additionally, our approach may be extended to identify
all arms above a certain threshold or to target a spe-
cific fraction of arms, such as identifying all ϵ-good arms
or detecting outliers [79–81]. In all these examples, we
expect information-based strategies to prove efficient in
capturing the structure and correlations within the game
[38, 75].
# IV. LINEAR BANDITS

## A. Setting and core insights

Contextual bandits with linear payoffs is a fundamental paradigm in multi-armed bandit systems, underpinning key applications such as internet advertisement selection and personalized recommendations [46, 82, 83]. This problem extends the classic bandit framework by introducing correlations between arms and allowing the set of arms to change over time [26, 46, 48, 84] (see Fig. 1 c)). For the stochastic linear problem, at each round t, the agent faces the decision set $A_t \in \mathbb{R}^d$ which may vary over time. From this set, it selects an action $A_t$ and observes a corresponding reward,

$$X_t = \langle \theta_*, A_t \rangle + \xi_t, \quad (10)$$

where $\theta_*$ defines the optimal direction and $\xi_t$ is modeled as Gaussian white noise in this study. Since the decision set may evolve over time, the losses are evaluated based on the best option available at any given time, leading to the random pseudo-regret:

$$\hat{R}_n = \sum_{t=0}^{n} \max_{a \in A_t} \langle \theta_*, a - A_t \rangle \quad (11)$$

Hence, $A_t$ composition plays a crucial role in the setting. If $A_t$ forms a constant orthogonal basis, it simplifies to the classical bandit settings. The decision set may be finite or infinite, generated by a stochastic process, or part of an adversarial game adapting to previous choices, with $A_t$ potentially evolving rather than being drawn from a predefined set of decision sets [26]. This inherent diversity makes it difficult for linear bandit algorithms to be optimal across all settings [47, 85]. As in most bandit problems, the UCB algorithm emerges as a useful approach. It relies on a tuned confidence index associated with each arm to decide which arm to play. In the linear bandit case, the core algorithm is referred to as LinUCB, which achieves a logarithmic scaling of the regret when actions sufficiently close to $\theta_*$ are available [26, 43, 83, 86-89]. Otherwise, in the general case, the optimal regret is bounded by $O(d\sqrt{T})$. Beyond the UCB class, Thompson sampling, which relies on sampling mean rewards from a posterior distribution and choosing the arm with probability proportional to this posterior, has also been shown to achieve near-optimal regret bounds for stochastic contextual bandits with linear payoff functions [90] [36, 48, 91]. Optimal allocation matching strategies, on the other hand, rely on an estimate of $\theta_*$ and solve an optimization problem based on this estimate or perform exploration to determine the next action [47, 64, 85, 88]. This class of strategies has been shown to achieve optimality when faced with a fixed action set [85, 88]. Lastly, the information-directed sampling (IDS) principle leverages a measure of information

gain from the optimal action, explicitly balanced by expected losses from exploration. By consistently using an information measure that captures the specific problem structure, IDS has been shown to achieve optimal regret scaling for linear bandits and other structured settings [9, 92-94]. As first found in [47], a key insight is that a consistent strategy must allocate exploration time so that the gaps between all suboptimal actions and $\theta_*$ are identified with high confidence. Otherwise, a purely greedy strategy solely based on $\theta_*$ confidence estimation will fall short. This highlights the complexity arising from the variation of $A_t$.

We developed a new principle that relies almost exclusively on information acquisition to drive its decision policy. Our approach is rooted in the approximate information maximization (AIM) strategy, shown to be optimal in classic bandit settings [65, 66]. The AIM principle involves selecting the arm that maximizes the information gained from a judiciously chosen observable of the game. This gain is measured through the associated entropy, with its increments approximated to identify the arm that will result in the largest entropy reduction. In [65, 66], the entropy of the posterior distribution of the maximum mean reward value results in an optimal exploration-exploitation trade-off. However, it cannot be directly mapped to the linear case. By symmetry $A_{M_t}$ and $-A_{M_t}$ carry the same information. Thus, suboptimal actions can provide extensive information on $\theta_*$ value but incur higher losses. Hence, solely focusing on acquiring more information on $\theta_*$ results in over-exploration. We now present an adapted version of AIM to address this challenge.

## B. Algorithm design

Similar to Explore-m bandits, we first define relevant notation. Let $B_t = \lambda I_d + \sum_n^t A_n A'_n$ be the covariance matrix of the posterior distribution of $\theta_*$ according to a symmetric Gaussian prior parametrized by $\lambda$. We denote by $\hat{\theta}_t = B_t^{-1} \sum_n^{t-1} X_n A_n$ its associated posterior mean (see Supplementary Material Section S8 for detail). Here, $'$ and $^{-1}$ represent the transpose and inverse operators, respectively. The best available empirical arm in $A_t$ is $A_{M_t} = \max_{a \in A_t} \langle \hat{\theta}_t, a \rangle$. We finally define a norm through $\|x\|_G = x'Gx$ for $x \in \mathbb{R}^d$ and with $G \in \mathbb{R}^{d \times d}$ positive definite.

To adapt AIM, we opt to adjust the information gain depending on the selected arm. Arms will be selected to maximize the information regarding the value of $\theta_*$, weighted by the likelihood of the arm being suboptimal. In other words, the arms are evaluated not only by the information they provide but also regarding their relative gap with $A_{M_t}$, quantified by the likelihood that the best empirical choice $A_{M_t}$ is better than $A_t$, i.e., the probability that $\langle \theta_*, A_{M_t} - A_t \rangle > 0$. Finally, $A_{M_t}$ is assigned to maximize the information regarding the $\theta_*$ value. This
procedure offers two main benefits: 1) it prevents over-exploration by adjusting the information gains from sub-optimal arms. 2) It also involves a measure of the gaps between mean rewards, addressing the criteria set out by [47], which are also implicitly included in the information regarding $\theta_*$.

We now provide the analytical expression regarding the entropy increments relative to each choice (see Supplementary Material Section S8 for details).

We first consider the information gain tied to $A_{Mt}$. The posterior distribution of $\theta_*$ is given by

$$p(\theta_* = \theta | \mathcal{H}_t) = \frac{\exp\left(-\frac{1}{2}(\theta - \hat{\theta}_t)' B_t (\theta - \hat{\theta}_t)\right)}{\sqrt{(2\pi)^d \det B_t^{-1}}}, \quad (12)$$

where $\mathcal{H}_t$ represents the history of chosen arms and observed rewards. The associated entropy reads

$$S = \frac{1}{2} \ln (\det B_t^{-1}) + \frac{d}{2} [1 + \ln(2\pi)]. \quad (13)$$

The corresponding entropy increment, which quantifies the gain of information about $\theta_*$, is then

$$\Delta S_{A_{Mt}} = -\frac{1}{2} \ln \left( 1 + A'_{Mt} B_t^{-1} A_{Mt} \right). \quad (14)$$

We now consider the remaining arms, focusing on a given suboptimal arm $A_t$. The probability of observing $\langle \theta_*, A_{Mt} - A_t \rangle > 0$, termed $C_{A_{Mt}, A_t}$, is given by

$$C_{A_{Mt}, A_t} = \frac{1}{2} \left[ 1 + \operatorname{erf} \left( \frac{\theta'_* [A_{Mt} - A_t]}{\sqrt{2[A_{Mt} - A_t]' B_t^{-1} [A_{Mt} - A_t]}} \right) \right], \quad (15)$$

with associated entropy

$$S_{C,A_t} = -C_{A_{Mt},A_t} \ln C_{A_{Mt},A_t} - (1-C_{A_{Mt},A_t}) \ln(1-C_{A_{Mt},A_t}). \quad (16)$$

To achieve a simpler expression, we focus on the asymptotic form of Eq. (16) when $A_{Mt}$ is assumed to be the most probable optimal option. We denote this asymptotic form $w_{A_t}$ such that $S_{C,A_t} \sim w_{A_t}$ as $\frac{\delta}{\sqrt{\Sigma}} \to \infty$, which takes the form

$$w_{A_t} = \frac{\delta e^{-\frac{\delta^2}{2\Sigma^2}}}{\Sigma^{\frac{3}{2}} 2\sqrt{\pi}}, \quad (17)$$

with $\delta = \theta'_*[A_{Mt} - A_t]$, $\Sigma = [A_{Mt} - A_t]' B_t^{-1} [A_{Mt} - A_t]$ (see Supplementary Material Section S8). The weighted information gain relative to $A_t$ thus reads

$$\begin{aligned} \Delta \tilde{S}_{A_t} &= -w_{A_t} \Delta S_{A_t} \\ &= -\frac{1}{2} \frac{\delta}{\Sigma^{\frac{3}{2}}} \frac{e^{-\frac{\delta^2}{2\Sigma^2}}}{2\sqrt{\pi}} \ln \left( 1 + A'_t B_t^{-1} A_t \right). \end{aligned} \quad (18)$$

The pseudo-code for the resulting algorithm is presented in Alg. 2 below.

<caption>**Algorithm 2:** Algorithm for d-dimensional linear Gaussian bandits</caption>

Draw a first arm $A_0$, observe reward $X_0$, and update statistics: $B_1 = \lambda I_d + A_0 A'_0$ and $\hat{\theta}_1 = B_1^{-1} X_0 A_0$
**for** $t = 1$ **to** $T$ **do**
  // Arm selection
  $A_{Mt} \leftarrow \max_{a \in A_t} \langle \hat{\theta}_t, a \rangle$
  Evaluate $\Delta S_{A_{Mt}}$ following Eq. (14)
  **for** $A_n \in A_t \setminus \{A_{Mt}\}$ **do**
    Evaluate $\Delta \tilde{S}_{A_n}$ following Eq. (18)
    Select $A_t$ as
      $\operatorname{argmin} (A_n \in A_t \setminus \{A_{Mt}\}, A_{Mt} : \Delta \tilde{S}_{A_n}, \Delta S_{A_{Mt}})$
    Pull $A_t$ and observe $X_t(A_t)$
    $B_{t+1} \leftarrow B_t + A_t A'_t$ and
    $\hat{\theta}_{t+1} \leftarrow B_{t+1}^{-1} \sum_n^t X_n A_n$ // Update statistics

### C. Results

Suboptimal arms are also evaluated regarding their gap with the best empirical arm available. As a result, the information gain expressed by Eq. (17) decreases exponentially with respect to this gap, making Eq. (14) dominate in most cases, thereby preventing our algorithm from over-exploring. In particular, it makes (17) asymmetric with respect to $A_t$, thereby enabling arms of opposite signs to be told apart. This fulfills the key challenge of preventing suboptimal arms from being sampled regarding the information gain they provide to close off optimal solutions. It also introduces the information relative to the gaps between current arms' means. Nonetheless, suboptimal arms are still evaluated based on the information they provide on the full system and underprobed directions, which stays the core of AIM. A preliminary theoretical guarantee can be assessed by considering the classic bandit setting, where $A_t$ is constant and forms an orthogonal basis. In this setting, Eqs. (14) and (17) demonstrates asymptotic behavior similar to previous information maximization algorithms [65] that have recently been proven optimal. A second illustrative example involves an adversarial scenario where $A_t$ will suddenly start to display solely actions that have not been explored previously—untested directions, i.e. with high values of $A'_{Mt} B_t^{-1} A_{Mt}$. In such cases, the entropy increment Eq. (14) should dominate, still accounting for exploration despite facing solely highly uncertain options.

To evaluate the performance of LinAIM, the average regret is analyzed in Fig. 3 for two complementary settings meant to cover a wide range of scenarios. In the first experiment, $A_t$ is formed by 10 arms resampled at each time from a normal distribution in $\mathbb{R}^{10}$. This decision set exhibits temporal variability, with a sparse number of solutions available at each discrete time step. Here, LinAIM performances match those of commonly used algorithms such as linUCB [26, 87], slightly outperforming them. It showcases the algorithm's efficiency when confronted with a broad range of arms. To eval-
uate LinAIM's ability to leverage available information in suboptimal solutions, we consider a toy setting defined in [64] originally from [47]. The agent faces two fixed sets $A_t$ formed by three arms in $\mathbb{R}^3$, each set having an equal probability of being presented to the agent. The first set is $\{[1, 0, 0], [0, 1, 0], [1 - \xi, 2\xi, 0]\}$, the second set $\{[0, 0.6, 0.8], [0, 0, 1], [0, \xi/10, 1 - \xi]\}$, and finally $\theta_* = [1, 0, 1]$ with $\xi$ small. The key insight is that optimistic strategies are rarely selected $[0, 1, 0]$ $[0, 0.6, 0.8]$ in the first and second sets due to the substantial gap. They thereby incur significant regret in learning which of the remaining arms is optimal. Conversely, an asymptotically optimal strategy strategically allocates more selections to the suboptimal arms, facilitating information acquisition to accurately identify $\theta_*$, hence circumventing regret that scales with accurately $\xi$. Here also, our algo shows strong performance similar to state-of-the-art algorithms. Such performances are quite convincing, and our algorithm demonstrates performance comparable to recent algorithms such as information-directed sampling [92, 94], SOLID [64], OSSB [85] or OAM [88]. Although our algorithm shares similarities with information-directed sampling by adjusting the information gain, our design and analytic expressions are notably simpler than the methods cited above. It notably reduces the implementation costs and doesn't require working with finite arm sets. Nevertheless, linear bandit setting is highly complex, in particular in the adversarial regime where the decision set can be specifically designed to expose the algorithm's flaws. Hence, we must confirm the empirical performance of LinAIM by providing theoretical guarantees, and we may identify settings where its effectiveness is limited. Nonetheless, its design is sufficiently simple to allow substantial extensions to meet these theoretical criteria. In particular, suboptimal actions could also be evaluated based on their ability to provide information about all available gaps, or specifically the gaps between $\hat{\theta}_t$ and all suboptimal arms. This initial design lays the foundation for a deeper exploration of information-based approaches in linear bandits.

# V. MANY-ARMED BANDITS

## A. Setting and core insight

We now consider the many-armed setting as introduced in [95]. The major difference with the classic bandit problem is that the game's duration is finite and known in advance. It aims to cover problems in which the number of actions is too large for exhaustive search [Fig. 1 d)]. It underpins key applications that require multiple testing, such as encountered in medical trials [49, 50, 96]. The agent must carefully define patient testing groups, balancing ethical standards and treatment costs while ensuring maximum information gain on trial efficacy. In this framework, in each round $t$ (where $t = 1, .., T$), the agent selects an arm $a_t \in [K] = \{1, .., K\}$, where K represents

the total number of arms. The chosen arm yields a stochastic reward $X_t(a_t)$, drawn from a distribution of unknown mean $\mu_{a_t}$. We assume a Bayesian framework where the mean reward for each arm is drawn from a common prior distribution $\Gamma$ with a finite support $[\mu_{inf}, \mu_{sup}]$. Furthermore, we assume that the reward distributions for all arms belong to the same family, parameterized solely by their means. For instance, the rewards might follow Gaussian distributions of known fixed variance $\sigma^2$ where the mean of each arm is drawn uniformly from the interval $[0, 1]$. Given a time horizon $T$, the agent's goal is to minimize its expected pseudo-regret over $T$ rounds in a single experiment. The pseudo-regret is here given by

$$R_T = T \max_{i \in [K]} \mu_i - \sum_{t=1}^{T} \mathbb{E}[\mu_{a_t}]. \quad (19)$$

<figure><img src="image_4.png" /><figcaption>FIG. 3. Mean regret for two linear bandit settings with Gaussian rewards. In blue our algorithm and in orange and red UCB algorithms adjusted to the linear settings. (a) Bandit setting with 10 arms resampled at each time from a normal distribution in $\mathbb{R}^{10}$. (b) Toy problem borrowed from [64] with two contexts. Each context (detailed in the main text) is drawn with equal probability and $\xi = 0.5$. Error bars show standard error around the mean. Details of the algorithms, simulations and a focus on standard deviations are provided in the Supplementary Material Sections S10 and S10B.</figcaption></figure>
This measures the gap between the cumulative reward from always choosing the best arm and the agent's expected reward over T rounds. The expectation reflects that the agent's policy, informed by past rewards, is affected by their randomness. Ultimately, the agent aims to minimize the Bayesian expected regret,

$$BR_{T,K} = \mathbb{E}[R_T]. \qquad (20)$$

Here, the expectation is taken over the prior distribution of the mean rewards, representing the agent's performance averaged over all possible mean reward configurations. The key distinction from previous settings is that the agent operates with a finite budget and has prior knowledge of the total number of rounds T. We focus on scenarios where $K > \sqrt{T}$, yielding too little time for the agent to extensively sample all the arms or fully exploit the best ones. To achieve an efficient strategy, the agent must sample only a subset of size $m \sim O(\sqrt{T})$ arms, enabling the algorithm to find a promising solution without inducing excessive exploration [95]. Beyond this scale, further exploration becomes too costly compared to leveraging the best empirical arms. Conversely, before this scale, the sampled arms have a higher probability of inducing significant regret, making early exploitation less effective [95].

Multiple strategies attain the optimal scaling of $BR_{T,K} \approx O(\sqrt{T})$ [97]. Notably, Subsampled Greedy (SS-Greedy) relies on an ad hoc selection of a subset of fixed size ($O(\sqrt{T})$) to limit exploration and has been shown to be optimal for Bernoulli rewards. While such strategies achieve optimal asymptotic scaling, they do not allow the algorithm to adapt to the rewards observed during its execution. Hence, we aim to use a physics-based approach that naturally recovers the $O(\sqrt{T})$ scaling through a functional expression, while maintaining flexibility and both short- and long-time efficiency.

## B. Algorithm design

We propose an algorithm that leverages the minimization of a global functional based on underlying physics principles, using as a proxy variable the expected upcoming regret, i.e., the regret accumulated from time t to T. Our policy works as follows: at each time step, it evaluates the expected upcoming regret for two distinct decision sequences and selects the one with the lower expected upcoming regret. The two sequences are: 1) pull the current best empirical arm, denoted $M_t$, until the end, or 2) try a new untested arm until it eventually underperforms compared to $M_t$, at which point $M_t$ is chosen. Although these strategies recommend actions for the entire remaining time, it does not mean the algorithm will follow them in subsequent steps, as the choice between them is reassessed at each time step. Before evaluating both upcoming regrets, we need to introduce several definitions. When clear from context, we omit the dependence on t for simplicity. The number of times arm i has

been pulled is denoted by $t_i$, and its associated empirical mean by $\hat{\mu}_i$. The number of different arms tested by time t is labeled $k_t$, forming the set $[k_t] = \{k_1, k_2, \dots, k_t\}$. The best empirical arm at time t is labeled $M_t$, with its corresponding empirical mean $\hat{\mu}_{M_t} = \max_{i \in [k_t]} \hat{\mu}_i(t)$. We also define the remaining time as $\tau = T - t$. Last, the expected maximum mean value is denoted $\mu_* = \mathbb{E}_{\Gamma} \left[ \max_{i \in [K]} \mu_i \right]$.

We now derive approximations for the regret in both cases, see the Supplementary Material Section S9 for further details and discussion of all approximations. For 1) (fully exploit $M_t$ for the next $\tau$ turns) the approximated upcoming expected regret is equal to

$$\tilde{R}_g = \tau(\mu_* - \hat{\mu}_{M_t}) \qquad (21)$$

Here, we approximated the expected value of the current best empirical arm by $\hat{\mu}_{M_t}$. For 2) (testing a new arm) the upcoming expected regret is approximated as

$$\tilde{R}_{\text{exp}} = \int_{\hat{\mu}_{M_t}}^{\mu_{\text{sup}}} \Gamma(\mu)(\mu_* - \mu)\tau d\mu + \int_{\mu_{\text{inf}}}^{\hat{\mu}_{M_t}} \Gamma(\mu) [(\mu_* - \mu)\tau_{\text{fpt}} + (\mu_* - \hat{\mu}_{M_t})(\tau - \tau_{\text{fpt}})] d\mu. \qquad (22)$$

The first integral captures cases where the true mean reward of the new arm is higher than $\hat{\mu}_{M_t}$. Roughly, to obtain this expression we neglect cases where the empirical mean of a promising arm never drops below $\hat{\mu}_{M_t}$. The second integral corresponds to cases where the true mean reward value of the new arm is lower than $\hat{\mu}_{M_t}$. In this case, the new arm will be pulled for an average time $\tau_{\text{fpt}}$ until it becomes suboptimal, which happens when its empirical mean falls below $\hat{\mu}_{M_t}$. This first phase yields the first term, following which the algorithm reverts to exploiting the best empirical arm, as captured by the second term.

Finally, the decision procedure evaluates

$$\begin{aligned} \Delta &= \tilde{R}_{\text{exp}} - \tilde{R}_{g} \\ &= \tau \int_{\hat{\mu}_{M_t}}^{\mu_{\text{sup}}} \Gamma(\mu)(\hat{\mu}_{M_t} - \mu) d\mu \\ &\quad + \int_{\mu_{\text{inf}}}^{\hat{\mu}_{M_t}} \Gamma(\mu)(\hat{\mu}_{M_t} - \mu) \tau_{\text{fpt}} d\mu, \end{aligned} \qquad (23)$$

and follows the strategy associated with the lowest upcoming regret. To get a universal and simpler expression, we employ the scaling ansatz that the typical number of steps to assess suboptimality is inversely proportional to the mean differences, $\tau_{\text{fpt}} \propto (\hat{\mu}_{M_t} - \mu)^{-1}$ (refer to Supplementary Material Section S9 for additional details).

For a uniform prior under $[0, 1]$, we obtain the following expression for $\Delta$

$$\Delta = c\hat{\mu}_{M_t} - \tau \frac{(1 - \hat{\mu}_{M_t})^2}{2}, \qquad (24)$$
where c is a free parameter, which we set to 1.

The pseudo-code for the resulting algorithm referred to as approximate expected regret minimization (ARM) is presented in Alg. 3 below.

**Algorithm 3:** Algorithm for k Gaussian arms with finite horizon *T*

Draw a first arm $A_0$, observe reward $X_0$, and update statistics: $\hat{\mu}_0 = X_0$, $k_0 = 1$

**for** *t* = 1 to *T* **do**
  // Arm selection
  $M_t \leftarrow \underset{i \in [k_t]}{\operatorname{argmax}} \hat{\mu}_i(t)$
  **if** $k_t = k$ **then** $a_t \leftarrow M_t$
  **else**
    Evaluate $\Delta$ following Eq. (24)
    **if** $\Delta \le 0$ **then** $a_t \leftarrow M_t$
    **else** $a_t \leftarrow k_t + 1, k_{t+1} \leftarrow k_t + 1$
    Pull $a_t$ and observe $X_t(a_t)$
    $\hat{\mu}_{a_{t+1}} \leftarrow \frac{\hat{\mu}_{a_t} t_{a_t} + X_t(a_t)}{t_{a_t} + 1}$, // Update statistics
    $t_{a_{t+1}} \leftarrow t_{a_t} + 1$

Lets us briefly comment on our algorithm design. When $\Delta$ is positive, the current best empirical arm is chosen, as it involves a lower expected cost. Conversely, if $\Delta$ is negative, a new untested arm is pulled. Note that the algorithm behaves greedily when no more arms remain to be tested, although such cases should rarely be encountered in many-armed settings. These simplifications aim to derive a straightforward and tractable expression, while still leveraging a well-defined global quantity to minimize. Here, since the time horizon is too short for leveraging a full exploration and identification of the best arm, the need to acquire more information must be significantly limited in the decision process. Therefore, here the relevant information lies in the time required to assess that a new arm is sub-optimal and is quantified by $\tau_{fpt}$.

### C. Results

To assess the efficiency of ARM (Alg. 3), its average regret is compared with the state-of-the-art SS-epsilon greedy algorithm (see [95] and Section S10 B in the Supplementary Material for implementation details). Notably, SS-epsilon greedy has been shown to achieve an optimal regret scaling of $O(\sqrt{T})$ for $K \gg \sqrt{T}$. Figure 4 (a) shows the regret in the many-armed bandit setting with a finite horizon and Bernoulli rewards, where our algorithm outperforms the SS-greedy algorithm. This is also confirmed for several horizon durations [Fig. 4(b)]. This numerical result outlines that the optimal balance between exploration and exploitation is already embedded in the underlying physical structure of our algorithm. In contrast, SS-greedy manually imposes a first exploration phase of constant duration (namely $\sqrt{T}$) to ensure optimal scaling, followed by a greedy strategy, leading to disjoint exploration-exploitation phases. This is

exemplified by ARM displaying a smoother initial regret curve compared to SS-greedy. ARM alternates between exploration and exploitation until a sufficiently promising arm is found, adapting its exploration amount around the fixed $\sqrt{T}$ ratio if a sufficiently promising arm is found earlier or later [98]. Notably, in Fig. 4 (a), the selected arm is found later by ARM than by the SS-greedy policy

<figure><img src="image_5.png" /><figcaption>FIG. 4. Mean regret for the many-armed bandit problem with Bernoulli rewards and a uniform prior on [0, 1]. (a) The regret growth of our algorithm (ARM), in blue, is observed until horizon $T$, i.e the stopping time, is reached $T = 10000$ ($K = 5000 \gg \sqrt{T}$ and $c = 1$). The regret is averaged over 2000 runs and standard error are indicated (see Supplementary Material Sections S10 and S10 B for details on the numerical settings). Its performance is compared to the ss-greedy algorithm, in red. The final slopes of both algorithms differs indicating that the selected arm for most of the exploitation is less efficient than the one found for our algorithm. Additionally, our algorithm presents a slower initial slope because exploration and exploitation are already mixed. (b) Mean regret performance when at the stopping time (when the horizon is reached), for distinct games with varying horizon length ($K = T \gg \sqrt{T}$ and $c = 1$). The regret is averaged over 2000 runs with error bars indicating standard error on the mean. Details of the algorithms and simulations, as well as a focus on standard deviations, are provided in the Supplementary Material Sections S10 and S10 B.</figcaption></figure>
but outperforms the one found by SS-greedy on average, as indicated by the distinct final slopes of the regret closer to the horizon.

The empirically observed optimality of ARM is supported by a heuristic scaling argument for when the transition between exploration and exploitation likely occurs (see Supplementary Material Section S9 for additional elements). Briefly, the expected value of $\Delta$ [Eq. (24)] crosses over from positive to negative values for $\tau(1 - \hat{\mu}_{Mt}) \sim O(1)$. Additionally, the typical value of $\hat{\mu}_{Mt}$ scales with $t$ as $(1 - \hat{\mu}_{Mt}) \sim 1/t$ since it is inversely proportional to the number of tested arms, which is in turn proportional to $t$ in the exploration phase (before the crossover from positive to negative $\Delta$). Combining these scales implies that $t \sim O(\sqrt{T})$, thereby explaining the optimal scaling of ARM's regret. Note, however, that this argument does not constitute a rigorous proof, which would need to account for the influence of rare events, such as failing to identify an arm for exploration within $O(\sqrt{T})$ time.

We conclude this section by several remarks. First, ARM relies on its ability to combine its knowledge of the remaining time and the available information on $\Gamma$ to optimize its decision process. Notably, Eq. (22) applies to more general prior distributions. If the prior is not provided to the agent, ARM could be adapted to add an empirical evaluation of $\Gamma$, in particular close to its upper bound. Similar to SS-greedy, ARM exploits by selecting the arm with the best empirical mean, which still allows identifying a sufficiently efficient arm within the subset of tested arms. To enhance the exploitation component and leverage prior knowledge, one may consider selecting the arm with the highest probability of being optimal, rather than the highest posterior mean. This slight difference is crucial, as the algorithm might otherwise fall into exploiting arms with better averages but a higher probability of being suboptimal compared to other explored arms. To implement such a strategy, one could replace $\hat{\mu}_{Mt}$ in Eq. (24) by the expected mean reached by playing this alternative strategy given the cur-

rent tested arms. But such an alternative remains more complex than using the empirical mean as we showed already provides efficient results. This approach could be considered for future developments. This flexibility should favor the extension and adaptability of ARM to more complex priors and bandit problems.

## VI. CONCLUSION

This study presents a generalisation of the information maximization principle and physics-based representations to a varied selection of structured bandit games. Our study addresses three distinct problems within the multi-armed bandit domain: many-armed bandits, linear bandits, and pure exploration. Each of these settings represents a unique facet of the broad field of bandit games, and each requires a tailored approach to account for their underlying structures and achieve the right balance between exploration and exploitation. To this end, for each setting, we focused on a specific observable from which we extracted a simplified and analytical functional at the core of the decision scheme. Numerical experiments in the paradigmatic versions of these games showed the robustness and efficiency of our method. Further research should focus on deriving rigorous theoretical bounds tailored to each bandit setting. Our method goes beyond classical confidence intervals for individual arms by leveraging a functional representation to guide decision-making. This core architecture is designed to make our method more adaptable to the diverse variants that may be encountered in real-world scenarios. Each algorithm examined above could be adapted to address more intricate variations of the corresponding problems, especially when dealing with reward or prior distributions exhibiting power-law tails, which induce extreme values. Future work will focus on searching for demonstrations of optimality (such as the ones derived for AIM) and systematic approaches to devise information-based approaches to decision-making processes.

[1] R. S. Sutton and A. G. Barto, *Reinforcement Learning: An Introduction*, Adaptive Computation and Machine Learning Series (A Bradford Book, Cambridge, MA, USA, 1998), ISBN 978-0-262-19398-6.

[2] J. I. Gold and M. N. Shadlen, Annu. Rev. Neurosci. 30, 535 (2007).

[3] M. Jepma and S. Nieuwenhuis, Journal of Cognitive Neuroscience 23, 1587 (2011).

[4] H. Kim, J. H. Sul, N. Huh, D. Lee, and M. W. Jung, J Neurosci 29, 14701 (2009).

[5] M. Vergassola, E. Villermaux, and B. I. Shraiman, Nature 445, 406 (2007).

[6] J. Murlis, J. S. Elkinton, and R. T. Cardé, Annual Review of Entomology 37, 505 (1992).

[7] J.-B. Masson, M. B. Bechet, and M. Vergassola, J. Phys. A: Math. Theor. 42, 434009 (2009).

[8] Z. Wang and S. Jegelka, in *Proceedings of the 34th International Conference on Machine Learning* (PMLR, 2017), pp. 3627–3635, ISSN 2640-3498.

[9] D. Russo and B. Van Roy, in *Advances in Neural Information Processing Systems*, edited by Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (Curran Associates, Inc., 2014), vol. 27.

[10] D. Lindner, M. Turchetta, S. Tschiatschek, K. Ciosek, and A. Krause, *Information Directed Reward Learning for Reinforcement Learning* (2022), 2102.12466.

[11] R. Houthooft, X. Chen, Y. Duan, J. Schulman, F. D. Turck, and P. Abbeel, *VIME: Variational Information Maximizing Exploration* (2017), 1605.09674.

[12] K. Ding, J. Li, and H. Liu, in *Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining* (Association for Computing Machin-
ery, New York, NY, USA, 2019), WSDM '19, pp. 357–365, ISBN 978-1-4503-5940-5.

[13] S. Zhang, D. Martinez, and J.-B. Masson, Frontiers in Robotics and AI **2** (2015).

[14] D. Hernandez-Lobato, J. Hernandez-Lobato, A. Shah, and R. Adams, in *Proceedings of The 33rd International Conference on Machine Learning*, edited by M. F. Balcan and K. Q. Weinberger (PMLR, New York, New York, USA, 2016), vol. 48 of *Proceedings of Machine Learning Research*, pp. 1492–1501.

[15] D. Martinez, L. Arhidi, E. Demondion, J.-B. Masson, and P. Lucas, JoVE (Journal of Visualized Experiments) p. e51704 (2014).

[16] R. T. Cardé, Annual Review of Entomology **66**, 317 (2021).

[17] J. D. Cohen, S. M. McClure, and A. J. Yu, Philosophical Transactions of the Royal Society B: Biological Sciences **362**, 933 (2007).

[18] K. Doya, *Bayesian Brain: Probabilistic Approaches to Neural Coding* (MIT Press, 2007), ISBN 978-0-262-04238-3.

[19] T. T. Hills, P. M. Todd, D. Lazer, A. D. Redish, and I. D. Couzin, Trends in Cognitive Sciences **19**, 46 (2015).

[20] K. Friston, T. FitzGerald, F. Rigoli, P. Schwartenbeck, J. O Doherty, and G. Pezzulo, Neurosci Biobehav Rev **68**, 862 (2016).

[21] N. Tishby and N. Zaslavsky, in *IEEE Information Theory Workshop (ITW)* (2015).

[22] M. Helias and D. Dahmen, *Statistical Field Theory for Neural Networks*, vol. 970 of Lecture Notes in Physics (Springer International Publishing, Cham, 2020), ISBN 978-3-030-46443-1 978-3-030-46444-8.

[23] T. Parr, G. Pezzulo, and K. J. Friston, *Active Inference: The Free Energy Principle in Mind, Brain, and Behavior* (The MIT Press, 2022), ISBN 978-0-262-36997-8.

[24] J.-B. Masson, Proceedings of the National Academy of Sciences **110**, 11261 (2013).

[25] G. Reddy, V. N. Murthy, and M. Vergassola, Annual Review of Condensed Matter Physics **13**, 191 (2022).

[26] T. Lattimore and C. Szepesvári, *Bandit Algorithms* (Cambridge University Press, Cambridge, 2020), ISBN 978-1-108-48682-8.

[27] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al., Nature **529**, 484 (2016).

[28] D. Bouneffouf, I. Rish, and C. Aggarwal, in *2020 IEEE Congress on Evolutionary Computation (CEC)* (2020), pp. 1–8.

[29] G. Burtini, J. Loeppky, and R. Lawrence, *A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit* (2015), 1510.00757.

[30] A. Durand, C. Achilleos, D. Iacovides, K. Strati, G. D. Mitsis, and J. Pineau, in *Proceedings of the 3rd Machine Learning for Healthcare Conference* (PMLR, 2018), pp. 67–82, ISSN 2640-3498.

[31] C. Gentile, S. Li, and G. Zappella, in *Proceedings of the 31st International Conference on Machine Learning* (PMLR, 2014), pp. 757–765, ISSN 1938-7228.

[32] V. Kuleshov and D. Precup, *Algorithms for multi-armed bandit problems* (2014), 1402.6028.

[33] J. Mary, R. Gaudel, and P. Preux, in *Machine Learning, Optimization, and Big Data*, edited by P. Pardalos, M. Pavone, G. M. Farinella, and V. Cutello (Springer In-

ternational Publishing, Cham, 2015), Lecture Notes in Computer Science, pp. 325–336, ISBN 978-3-319-27926-8.

[34] T. C. Stewart, T. Bekolay, and C. Eliasmith, Front. Neurosci. **6** (2012).

[35] T. L. Lai and H. Robbins, Advances in Applied Mathematics **6**, 4 (1985).

[36] E. Kaufmann, N. Korda, and R. Munos, in *Algorithmic Learning Theory*, edited by N. H. Bshouty, G. Stoltz, N. Vayatis, and T. Zeugmann (Springer, Berlin, Heidelberg, 2012), Lecture Notes in Computer Science, pp. 199–213, ISBN 978-3-642-34106-9.

[37] P. Auer, in *Proceedings 41st Annual Symposium on Foundations of Computer Science* (IEEE Comput. Soc, Redondo Beach, CA, USA, 2000), pp. 270–279, ISBN 978-0-7695-0850-4.

[38] S. Bubeck, R. Munos, and G. Stoltz, Theoretical Computer Science **412**, 1832 (2011).

[39] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck, in *Proceedings of The 27th Conference on Learning Theory* (PMLR, 2014), pp. 423–439, ISSN 1938-7228.

[40] E. Kaufmann and S. Kalyanakrishnan, in *Proceedings of the 26th Annual Conference on Learning Theory* (PMLR, 2013), pp. 228–251, ISSN 1938-7228.

[41] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone, Proceedings of the 29th International Conference on Machine Learning, ICML 2012 (2012).

[42] R. Degenne and W. M. Koolen, in *Advances in Neural Information Processing Systems*, edited by H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett (Curran Associates, Inc., 2019), vol. 32.

[43] L. Li, W. Chu, J. Langford, and R. E. Schapire, in *Proceedings of the 19th International Conference on World Wide Web* (Association for Computing Machinery, New York, NY, USA, 2010), WWW '10, pp. 661–670, ISBN 978-1-60558-799-8.

[44] B. Lin and D. Bouneffouf, in *2022 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE)* (2022), pp. 1–8, ISSN 1558-4739.

[45] L. Zhou, *A Survey on Contextual Multi-armed Bandits* (2016), 1508.03326.

[46] P. Auer, Journal of Machine Learning Research **3**, 397 (2002).

[47] T. Lattimore and C. Szepesvari, in *Proceedings of the 20th International Conference on Artificial Intelligence and Statistics* (PMLR, 2017), pp. 728–737, ISSN 2640-3498.

[48] S. Agrawal and N. Goyal, in *Proceedings of the 30th International Conference on Machine Learning* (PMLR, 2013), pp. 127–135, ISSN 1938-7228.

[49] S. S. Villar, J. Bowden, and J. Wason, Statistical Science **30**, 199 (2015).

[50] S. S. Villar, Probability in the Engineering and Informational Sciences **32**, 229 (2018).

[51] R. de Heide, J. Cheshire, P. Ménard, and A. Carpentier, in *Proceedings of the 35th International Conference on Neural Information Processing Systems* (Curran Associates Inc., Red Hook, NY, USA, 2024), NIPS '21, pp. 22457–22469, ISBN 978-1-7138-4539-3.

[52] T. Bonald and A. Proutiere, in *Advances in Neural Information Processing Systems*, edited by C. J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (Curran Associates, Inc., 2013), vol. 26.
[53] D. A. Berry, R. W. Chen, A. Zame, D. C. Heath, and L. A. Shepp, The Annals of Statistics **25**, 2103 (1997).

[54] Y. Wang, J.-y. Audibert, and R. Munos, in *Advances in Neural Information Processing Systems* (Curran Associates, Inc., 2008), vol. 21.

[55] D. Baudry, E. Kaufmann, and O.-A. Maillard, in *Proceedings of the 34th International Conference on Neural Information Processing Systems* (Curran Associates Inc., Red Hook, NY, USA, 2020), NIPS'20, pp. 5468–5478, ISBN 978-1-7138-2954-6.

[56] S. Guha, K. Munagala, and P. Shi, J. ACM **58**, 3:1 (2010).

[57] N. Levine, K. Crammer, and S. Mannor, in *Advances in Neural Information Processing Systems*, edited by I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Curran Associates, Inc., 2017), vol. 30, pp. 3074–3083.

[58] P. Auer, N. Cesa-Bianchi, and P. Fischer, Machine Learning **47**, 235 (2002).

[59] H. Bastani, M. Bayati, and K. Khosravi, Management Science **67**, 1329 (2021).

[60] P. Ménard and A. Garivier, in *Proceedings of the 28th International Conference on Algorithmic Learning Theory* (PMLR, 2017), pp. 223–237, ISSN 2640-3498.

[61] D. Russo and B. V. Roy, Journal of Machine Learning Research **17**, 1 (2016).

[62] G. Reddy, A. Celani, and M. Vergassola, Journal of Statistical Physics **163**, 1454 (2016).

[63] Y.-H. Hung, P.-C. Hsieh, X. Liu, and P. R. Kumar, *Reward-Biased Maximum Likelihood Estimation for Linear Stochastic Bandits* (2020), 2010.04091.

[64] A. Tirinzoni, M. Pirotta, M. Restelli, and A. Lazaric, in *Proceedings of the 34th International Conference on Neural Information Processing Systems* (Curran Associates Inc., Red Hook, NY, USA, 2020), NIPS '20, pp. 1417–1427, ISBN 978-1-7138-2954-6.

[65] A. Barbier-Chebbah, C. L. Vestergaard, and J.-B. Mason, *Approximate information for efficient exploration-exploitation strategies* (2023), 2307.01563.

[66] A. Barbier-Chebbah, C. L. Vestergaard, J.-B. Masson, and E. Boursier, *Approximate information maximization for bandit games* (2023), 2310.12563.

[67] E. Kaufmann, O. Cappé, and A. Garivier, J. Mach. Learn. Res. **17**, 1 (2016).

[68] S. Kalyanakrishnan and P. Stone, in *Proceedings of the 27th International Conference on International Conference on Machine Learning* (Omnipress, Madison, WI, USA, 2010), ICML'10, pp. 511–518, ISBN 978-1-60558-907-7.

[69] S. Mannor and J. N. Tsitsiklis, Journal of Machine Learning Research **5**, 623 (2004).

[70] Y. Zhou, X. Chen, and J. Li, in *Proceedings of the 31st International Conference on Machine Learning* (PMLR, 2014), pp. 217–225, ISSN 1938-7228.

[71] S. Bubeck, T. Wang, and N. Viswanathan, in *Proceedings of the 30th International Conference on Machine Learning* (PMLR, 2013), pp. 258–265, ISSN 1938-7228.

[72] V. Gabillon, M. Ghavamzadeh, and A. Lazaric, in *Advances in Neural Information Processing Systems*, edited by F. Pereira, C. J. Burges, L. Bottou, and K. Q. Weinberger (Curran Associates, Inc., 2012), vol. 25.

[73] J.-Y. Audibert and S. Bubeck, in *COLT - 23rd Conference on Learning Theory - 2010* (2010), p. 13 p.

[74] S. N. Majumdar, A. Pal, and G. Schehr, Physics Reports **840**, 1 (2020).

[75] A. Carpentier and M. Valko, in *Proceedings of the 32nd International Conference on Machine Learning* (PMLR, 2015), pp. 1133–1141, ISSN 1938-7228.

[76] I. Rejwan and Y. Mansour, in *Proceedings of the 31st International Conference on Algorithmic Learning Theory* (PMLR, 2020), pp. 752–776, ISSN 2640-3498.

[77] S. Katariya, A. Tripathy, and R. Nowak, in *Proceedings of the 33rd International Conference on Neural Information Processing Systems* (Curran Associates Inc., Red Hook, NY, USA, 2019), 991, pp. 11047–11057.

[78] A. Locatelli, M. Gutzeit, and A. Carpentier, in *Proceedings of The 33rd International Conference on Machine Learning* (PMLR, 2016), pp. 1690–1698, ISSN 1938-7228.

[79] B. Mason, L. Jain, A. Tripathy, and R. Nowak, in *Advances in Neural Information Processing Systems*, edited by H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Curran Associates, Inc., 2020), vol. 33, pp. 20707–20718.

[80] W. Ren, J. Liu, and N. B. Shroff, in *Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics* (PMLR, 2019), pp. 2820–2828, ISSN 2640-3498.

[81] H. Zhuang, C. Wang, and Y. Wang, in *Advances in Neural Information Processing Systems*, edited by I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Curran Associates, Inc., 2017), vol. 30.

[82] N. Abe, A. W. Biermann, and P. M. Long, Algorithmica **37**, 263 (2003).

[83] W. Chu, L. Li, L. Reyzin, and R. Schapire, in *Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics* (JMLR Workshop and Conference Proceedings, 2011), pp. 208–214, ISSN 1938-7228.

[84] A. Slivkins, in *Proceedings of the 24th Annual Conference on Learning Theory* (JMLR Workshop and Conference Proceedings, 2011), pp. 679–702, ISSN 1938-7228.

[85] R. Combes, S. Magureanu, and A. Proutiere, in *Proceedings of the 31st International Conference on Neural Information Processing Systems* (Curran Associates Inc., Red Hook, NY, USA, 2017), NIPS'17, pp. 1761–1769, ISBN 978-1-5108-6096-4.

[86] V. Dani, T. P. Hayes, and S. M. Kakade, in *21st Annual Conference on Learning Theory - COLT 2008, Helsinki, Finland, July 9-12, 2008*, edited by R. A. Servedio and T. Zhang (Omnipress, 2008), pp. 355–366.

[87] Y. Abbasi-yadkori, D. Pál, and C. Szepesvári, in *Advances in Neural Information Processing Systems* (Curran Associates, Inc., 2011), vol. 24.

[88] B. Hao, T. Lattimore, and C. Szepesvari, *Adaptive Exploration in Linear Contextual Bandit* (2020), 1910.06996.

[89] P. Rusmevichientong and J. N. Tsitsiklis, Mathematics of OR **35**, 395 (2010).

[90] Note1, these results rely on an adjustment of the variance of the posterior distribution.

[91] M. Abeille and A. Lazaric, Electronic Journal of Statistics **11**, 5165 (2017).

[92] J. Kirschner, T. Lattimore, C. Vernade, and C. Szepesvari, in *Proceedings of Thirty Fourth Conference on Learning Theory* (PMLR, 2021), pp. 2777–2821, ISSN
2640-3498.

[93] J. Kirschner and A. Krause, in *Proceedings of the 31st Conference On Learning Theory* (PMLR, 2018), pp. 358–384, ISSN 2640-3498.

[94] J. Kirschner, T. Lattimore, and A. Krause, in *Proceedings of Thirty Third Conference on Learning Theory* (PMLR, 2020), pp. 2328–2369, ISSN 2640-3498.

[95] M. Bayati, N. Hamidi, R. Johari, and K. Khosravi, in *Advances in Neural Information Processing Systems*, edited by H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Curran Associates, Inc., 2020), vol. 33, pp. 1713–1723.

[96] K. Jamieson and L. Jain, in *Proceedings of the 32nd International Conference on Neural Information Processing Systems*

Curran Associates Inc., Red Hook, NY,
USA, 2018), NIPS'18, pp. 3664–3674.

[97] Note2, the lower bounds holds for sufficiently high $T$, $K$ values and 1-regular $\Gamma$ ($\mu_{sup} = 1$), meaning that $\mathcal{P}_{\Gamma}[\mu > 1 - \epsilon] = O(\epsilon)$ as $\epsilon$ goes to 0; see [95] for theorem details.

[98] Note3, note that a sequential strategy has been proposed in [95], but this strategy still depends on a fixed bound on the subset size.

[99] E. S. Andersen, Mathematica Scandinavica **2**, 195 (1954), 24489033.

[100] M. Bauer, C. Godrèche, and J. M. Luck, Journal of Statistical Physics **96**, 963 (1999).

[101] P. Le Doussal and K. J. Wiese, Phys. Rev. E **79**, 051105 (2009).
Supplemental material
## S7. DETAILS OF EXPLORED-M DESIGN

We provide all derivation details leading to *PacAIM* expression given in the main text.

### A. Link between information maximization and probability maximization

Here, we briefly comment on the decision to switch from entropy increments to probability increments in the arm selection process of our *PacAIM* algorithm. The associated entropy for all arms, effectively well-separated by $\theta_b$, is given by:

$$S_{\text{top}} = -P_{\text{top}} \ln P_{\text{top}} - (1 - P_{\text{top}}) \ln(1 - P_{\text{top}}), \quad (S1)$$

with $P_{\text{top}} = \prod_{i \in \mathcal{M}_t} \mathbb{P}(\mu_i \ge \theta_b - \frac{\epsilon}{2})$. The information gain relative to arm $i \in \mathcal{M}_t$ thus reads.

$$\Delta S_{\text{top}} = -\Delta P_{\text{top}} [\ln(P_{\text{top}}) - \ln(1 - P_{\text{top}})]. \quad (S2)$$

For $P_{\text{top}} > 1/2$, the sign of $\Delta S_{\text{top}}$ is given by $\Delta P_{\text{top}}$, meaning that minimizing the entropy resumes to selecting the arm maximizing $\Delta P_{\text{top}}$. At short times, one may face events with $\Delta P_{\text{top}} < 1/2$. For such cases, direct entropy minimization will be inaccurate since Eq. (S2) ignores that arms may switch from $\mathcal{M}_t$ to $\mathcal{D}_t$, resulting in additional variations in $P_{\text{top}}$ not caught in (S2). We thus assume to minimize to select arms maximizing $\Delta P_{\text{top}} | \ln(P_{\text{top}}) - \ln(1 - P_{\text{top}})|$ increment. The same argument can be drawn for $P_{\text{bot}}$.

### B. Details on increment derivation

We start by reminding $P_{\text{top}}$ expression

$$P_{\text{top}} = \prod_{i \in \mathcal{M}_t} \mathbb{P} \left( \mu_i \ge \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t \right), \quad (S3)$$

By leveraging the arms' independence, the product enables a straightforward computation of the increments along each arm

$$\Delta_{i \in \mathcal{M}_t} P_{\text{top}} = \frac{\Delta \mathbb{P} \left( \mu_i \ge \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t \right)}{\mathbb{P} \left( \mu_i \ge \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t \right)} P_{\text{top}}. \quad (S4)$$

Since all gradients can be factorized by $P_{\text{bot}}P_{\text{top}}$, the decision criteria reduce to a comparison of the relative gradients of the cumulative distribution associated with each arm. Of note, a similar approach can be derived using the discrete increments. We finally conclude by computing the gradient of the cumulative probability associated with the arm $i$. It decomposes into partial derivatives along the empirical mean $\hat{\mu}_i$ and the number of draws $t_i$. We first notice that the partial derivative along $\hat{\mu}_i$ cancels by symmetry. Then we consider the derivative along the number of draws.

For a Gaussian reward with unit variance, we have

$$\begin{aligned} \mathbb{P} \left( \mu_i \ge \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t \right) &= 1 - \frac{1}{2} \left[ 1 + \operatorname{erf} \left( \sqrt{\frac{t_i}{2}} \left[ \theta_b - \frac{\epsilon}{2} - \hat{\mu}_i \right] \right) \right] \\ &= \frac{1}{2} \left[ 1 + \operatorname{erf} \left( \sqrt{\frac{t_i}{2}} \left[ \hat{\mu}_i - \theta_b + \frac{\epsilon}{2} \right] \right) \right] \end{aligned} \quad (S5)$$

and

$$\begin{aligned} \Delta \mathbb{P} \left( \mu_i \ge \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t \right) &= \frac{\partial}{\partial t_i} \mathbb{P} \left( \mu_i \ge \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t \right) \\ &= \frac{\hat{\mu}_i - \theta_b + \frac{\epsilon}{2}}{2\sqrt{2\pi t_i}} \exp \left( -t_i \frac{(\theta_b - \frac{\epsilon}{2} - \hat{\mu}_i)^2}{2} \right) \end{aligned} \quad (S6)$$
Replicating this reasoning for $P_{\text{bot}}$ leads to

$$ 
\begin{aligned}
\Delta \mathbb{P} (\mu_i \le \theta_b + \frac{\epsilon}{2} | \mathcal{H}_t) &= \frac{\partial}{\partial t_i} \mathbb{P} (\mu_i \ge \theta_b - \frac{\epsilon}{2} | \mathcal{H}_t) \\
&= \frac{\partial}{\partial t_i} \left( \frac{1}{2} \left[ 1 + \text{erf} \left( \sqrt{\frac{t_i}{2}} \left[ \theta_b + \frac{\epsilon}{2} - \hat{\mu}_i \right] \right) \right] \right) \\
&= \frac{\theta_b + \frac{\epsilon}{2} - \hat{\mu}_i}{2\sqrt{2\pi t_i}} \exp \left( -t_i \frac{(\theta_b + \frac{\epsilon}{2} - \hat{\mu}_i)^2}{2} \right)
\end{aligned} 
\quad (S7) $$

### C. Details on $\theta_b$ derivation

Here, we provide additional details on the derivation steps leading to $\theta_b$ expression in the main text. Our goal is to derive a tractable expression of an appropriate cutoff between the subset of arms with the current $m$-highest empirical means, $M_t$, with a minimal empirical $\min \hat{\mu}_{\text{top}} = \max(\{\hat{\mu}_{D_t}\})$ and the remaining arms of maximal mean $M_t$, $\hat{\mu}_{\text{bot}} = \min(\{\hat{\mu}_{D_t}\})$.

An optimal $\theta_b$ value should permit the algorithms to successfully stop in a minimal amount of samples denoted $\tau$ in the following. For a given set of observed empirical rewards $\{\mu_{M_t}\}$, $\{\mu_{D_t}\}$ and neglecting their future variations, an oracle strategy will verify

$$ \theta_{b,o} = \underset{\theta \in [\hat{\mu}_{\text{bot}}, \hat{\mu}_{\text{top}}]}{\operatorname{argmin}} \left( \tau = \sum_{i} \tau_i \text{ s.t. } \prod_{i \in D_t} \mathbb{P} \left( \mu_i \le \theta + \frac{\epsilon}{2} | \hat{\mu}_i, \tau_i \right) \prod_{i \in M_t} \mathbb{P} \left( \mu_i \ge \theta - \frac{\epsilon}{2} | \hat{\mu}_i, \tau_i \right) > 1 - \delta \right). \quad (S8) $$

Here, $\theta_{b,o}$ is the optimal value that minimizes $\tau$ while satisfying the stopping criteria, and $\{\tau_1..t_n\}$ are the local times of each arm at the stopping time. Probabilities in Eq. (S8) depend on the hypothetical number of samples for each arm, $\tau_i$ which differs by the current individual arm time $t_i$ for $P_{\text{top}}$ and $P_{\text{bot}}$. At short times, $\tau_i \gg t_i$ because it takes a certain number of samples before meeting the conditions in Eq. (S8). However, by selecting a $\theta_b$ close to $\theta_{b,o}$, the algorithm should adjust its strategy to match $t_i$ with $\tau_i$ as closely as possible.

Unfortunately, the expression for $\theta_{b,o}$ becomes intractable with more than two arms. To derive a simplified expression, we approximate $M_t$ as a fictive set of $m$ arms, all with the same empirical mean, $\hat{\mu}_{\text{top}}$, and the same number of pulls, $t_{\text{top}}$. Because all these fictive arms share the same empirical mean and pull count, the posterior distribution of their minimal mean value can be approximated by a Gumbel law [74] parametrized by $(\hat{\mu}_{\text{top}}, t_{\text{top}}, m)$.

$$ \mathbb{P} \left( \min_{i \in [1..m]} (\mu_i | \hat{\mu}_i = \hat{\mu}_{\text{top}}, t_i = t_{\text{top}}) \ge \theta \right) = \exp \left[ -\exp \left( \sqrt{2 \ln(m)} \left[ \sqrt{t_{\text{top}}} (\theta - \hat{\mu}_{\text{top}}) + \sqrt{2 \ln(m)} \right] \right) \right]. \quad (S9) $$

This approximation holds for large set values $m$, which are the most complicated cases for which relying on an efficient $\theta_b$ value matters the most. By replicating the previous scheme for $D_t$, we obtain a Gumbel law parameterized by $(\hat{\mu}_{\text{bot}}, t_{\text{bot}}, d = n - m)$ with a cumulative distribution reading:

$$ \mathbb{P} \left( \max_{i \in [1..d]} (\mu_i | \hat{\mu}_i = \hat{\mu}_{\text{bot}}, t_i = t_{\text{bot}}) \le \theta \right) = \exp \left[ -\exp \left( -\sqrt{2 \ln(d)} \left[ \sqrt{t_{\text{bot}}} (\theta - \hat{\mu}_{\text{bot}}) - \sqrt{2 \ln(d)} \right] \right) \right]. \quad (S10) $$

Let us note that the centering parameters $\sqrt{2 \ln(m)}$ and $\sqrt{2 \ln(d)}$ result from the Gaussian property of the reward distribution. Hence, we define $\theta_b$ as simultaneously verifying

$$ \mathbb{P} \left( \min_{i \in [1..m]} (\mu_i | \hat{\mu}_i = \hat{\mu}_{\text{top}}, t_i = t_{\text{top}}) \ge \theta_b - \frac{\epsilon}{2} \right) = 1 - \frac{\delta}{2}, \quad (S11) $$

and

$$ \mathbb{P} \left( \max_{i \in [1..d]} (\mu_i | \hat{\mu}_i = \hat{\mu}_{\text{bot}}, t_i = t_{\text{bot}}) \le \theta_b + \frac{\epsilon}{2} \right) = 1 - \frac{\delta}{2}. \quad (S12) $$

These events include all cases where the fictive subset is not $\epsilon$-optimal, upper-bounding the identification error probability by $\delta$. By injecting Eqs. (S9) and (S10) expressions within Eqs. (S10) and (S11) one obtains:

$$ \theta_b = \frac{\epsilon}{2} + \hat{\mu}_{\text{top}} - \frac{1}{\sqrt{t_{\text{top}}}} \left[ \sqrt{2 \ln(m)} - \frac{\ln(-\ln(1 - \frac{\delta}{2}))}{\sqrt{2 \ln(m)}} \right], \quad (S13) $$
and

$$ \theta_b = -\frac{\epsilon}{2} + \hat{\mu}_{\text{bot}} + \frac{1}{\sqrt{t_{\text{bot}}}} \left[ \sqrt{2 \ln(d)} - \frac{\ln(-\ln(1 - \frac{\delta}{2}))}{\sqrt{2 \ln(d)}} \right]. \quad (S14) $$

By combining Eqs. (S12) and (S13) one obtains

$$ \epsilon + \hat{\mu}_{\text{top}} - \hat{\mu}_{\text{bot}} = \frac{1}{\sqrt{t_{\text{top}}}} \left[ \sqrt{2 \ln(m)} - \frac{\ln(-\ln(1 - \frac{\delta}{2}))}{\sqrt{2 \ln(m)}} \right] + \frac{1}{\sqrt{t_{\text{bot}}}} \left[ \sqrt{2 \ln(d)} - \frac{\ln(-\ln(1 - \frac{\delta}{2}))}{\sqrt{2 \ln(d)}} \right]. \quad (S15) $$

We finally look for $t_{top}$ and $t_{bot}$ verifying Eq. (S15) but leading to a minimal amount of time $mt_{top} + dt_{bot}$. By labeling

$$ c_{\text{top}} = \left[ \sqrt{2 \ln(m)} - \frac{\ln(-\ln(1 - \frac{\delta}{2}))}{\sqrt{2 \ln(m)}} \right], \quad c_{\text{bot}} = \left[ \sqrt{2 \ln(d)} - \frac{\ln(-\ln(1 - \frac{\delta}{2}))}{\sqrt{2 \ln(d)}} \right], \quad M = \epsilon + \hat{\mu}_{\text{top}} - \hat{\mu}_{\text{bot}} \quad (S16) $$

we obtain

$$ t_{\text{top}} = \left[ \frac{c_{\text{top}}}{M - \frac{c_{\text{bot}}}{\sqrt{t_{\text{bot}}}}} \right]^2, \quad (S17) $$

and

$$ t_{\text{bot}} = \frac{c_{\text{bot}}}{M^2} + \left( \frac{c_{\text{bot}}^2 c_{\text{top}}^4 m^2}{M^6 d^2} \right)^{\frac{1}{3}} + \frac{2 M^2 d}{c_{\text{top}}^2 m} \left( \frac{c_{\text{bot}}^2 c_{\text{top}}^4 m^2}{M^6 d^2} \right)^{\frac{2}{3}}, \quad (S18) $$

which simplifies into

$$ t_{\text{bot}} = \frac{c_{\text{bot}}}{M^2} + \left( \frac{c_{\text{bot}}^2 c_{\text{top}}^4 m^2}{M^6 d^2} \right)^{\frac{1}{3}} \left( 1 + \frac{2 d^{\frac{2}{3}} c_{\text{bot}}^{\frac{2}{3}}}{m^{\frac{1}{3}} c_{\text{top}}^{\frac{2}{3}}} \right). \quad (S19) $$

Inserting Eq. (S19) in Eq. (S16) gives the desired analytical expression of $\theta_b$

$$ \theta_b = -\frac{\epsilon}{2} + \hat{\mu}_{\text{bot}} + c_{\text{bot}} \left[ \frac{c_{\text{bot}}}{M^2} + \left( \frac{c_{\text{bot}}^2 c_{\text{top}}^4 m^2}{M^6 d^2} \right)^{\frac{1}{3}} + \frac{2 M^2 d}{c_{\text{top}}^2 m} \left( \frac{c_{\text{bot}}^2 c_{\text{top}}^4 m^2}{M^6 d^2} \right)^{\frac{2}{3}} \right]^{-\frac{1}{2}}. \quad (S20) $$

Note that our approximation scheme is mainly independent of the reward distribution, as it only involves in $c_{bot}$ and $c_{top}$ expressions. To extend our results to various reward distributions, one simply needs to adjust the Gumbel law by providing the corresponding centering parameters (here $\sqrt{2 \ln(m)}$ for Gaussian rewards). Leveraging on scaling proposed in [74] for any distribution exhibiting a large $x$ tail $p(x) \sim \exp(-x^\gamma)$, the adjusted Gumbel law distributions read

$$ \mathbb{P} \left( \min_{i \in [1..m]} (\mu_i | \hat{\mu}_i = \hat{\mu}_{\text{top}}, t_i = t_{\text{top}}) \ge \theta \right) = \exp \left[ - \exp \left( \gamma \ln(m)^{1-\frac{1}{\gamma}} \left[ \sqrt{t_{\text{top}}} (\theta - \hat{\mu}_{\text{top}}) + \ln(m)^{\frac{1}{\gamma}} \right] \right) \right] \quad (S21) $$

and

$$ \mathbb{P} \left( \max_{i \in [1..d]} (\mu_i | \hat{\mu}_i = \hat{\mu}_{\text{bot}}, t_i = t_{\text{bot}}) \le \theta \right) = \exp \left[ - \exp \left( \gamma \ln(d)^{1-\frac{1}{\gamma}} \left[ \sqrt{t_{\text{bot}}} (\theta - \hat{\mu}_{\text{bot}}) + \ln(d)^{\frac{1}{\gamma}} \right] \right) \right], \quad (S22) $$

only affecting $c_{bot}$ and $c_{top}$ expressions. Still, keeping the Gaussian approximation within $\theta_b$ should remain reasonable for non-heavy-tailed reward distributions.

## S8. DETAILS OF LinAIM FOR LINEAR BANDITS

Here we provide derivations and simplifications details regarding our algorithm for the linear bandit setting.
A. Note on posterior distribution associated to $\theta_*$ value

We first seek to derive the posterior probability distribution of $\theta_*$ value given the history $\mathcal{H}_t$, which consists of past pairs of chosen arms and their corresponding rewards ($A_n, X_n$ for $n \in [0, t]$). We also rely on a Gaussian prior for $\theta_*$ value with a $L^2$ norm:

$$p(\theta_* = \theta) = \mathcal{N}^{-1} \exp \left( -\frac{\lambda}{2} \sum_{i}^{d} \theta_i^2 \right), \qquad (S23)$$

where $d$ is the arm space dimension. Choosing $\lambda > 0$ serves two purposes: first, it ensures that the covariance matrix of the associated posterior distribution is invertible even when no arms have been drawn. Second, it focuses the inference on more realistic optimal values by expecting a mean reward close to the unit norm. According to Bayes' theorem, the posterior distribution reads

$$\begin{align*}
p(\theta_* = \theta | \mathcal{H}_t) &= p(\mathcal{H}_t | \theta_* = \theta) p(\theta_* = \theta) p(\mathcal{H}_t)^{-1} \\
&= p(\mathcal{H}_t)^{-1} \frac{\mathcal{N}^{-1} e^{-\frac{\lambda}{2} \sum_{i}^{d} \theta_i^2}}{(2\pi)^{t/2}} \exp \left( -\frac{1}{2} \sum_{n=0}^{t} \left[ \theta' A_n - X_n \right]^2 \right) \\
&= p(\mathcal{H}_t)^{-1} \frac{\mathcal{N}^{-1} e^{-\frac{1}{2} \sum_{n=0}^{t} X_n^2}}{(2\pi)^{t/2}} \exp \left( \theta' \sum_{n=0}^{t} X_n A_n - \frac{1}{2} \theta' \left[ \sum_{n=0}^{t} A_n A'_n + \lambda I_d \right] \theta \right) \tag{S24} \\
&= \frac{\exp \left( -\frac{1}{2} (\theta - \hat{\theta}_t)' B_t (\theta - \hat{\theta}_t) \right)}{\sqrt{(2\pi)^d \det B_t^{-1}}}
\end{align*}$$

where we defined $B_t = \lambda I_d + \sum_n^t A_n A'_n$ and $\hat{\theta}_t = B_t^{-1} \sum_n^t X_n A_n$. The final step relies on the distribution being normalized. Eq. (S24) holds for Gaussian rewards and one recognizes a multivariate Gaussian distribution. Eq. (S24) forms the basis for the entropy calculations that underpin our algorithm.

B. Details of entropy increments for linear bandits LinAIM

Here we outline the key steps for computing the entropy increments discussed in the main text.

1. Entropy assigned to the best available empirical arm

We first consider the best available empirical arm at time $t$ defined as $A_{M_t} = \max_{a \in A_t} \langle \theta_*, a \rangle$. We assign to this arm the information gain of $\theta_*$ value which posterior is given by Eq. (S24). Because Eq. (S24) distribution is a Gaussian multivariate, the associated entropy reads

$$\begin{align}
S &= - \int_{\mathbb{R}^d} p(\theta_* = \theta | \mathcal{H}_t) \ln p(\theta_* = \theta | \mathcal{H}_t) d\theta \tag{S25} \\
&= \frac{1}{2} \ln(\det B_t^{-1}) + \frac{d}{2} [1 + \ln(2\pi)] \nonumber
\end{align}$$

The resulting increment, hence reads:

$$\begin{align}
\Delta S &= -\frac{1}{2} \ln \left[ \frac{\det (B_t + A_{M_t} A'_{M_t})}{\det (B_t)} \right] \nonumber \\
&= -\frac{1}{2} \ln \left[ \frac{(1 + A'_{M_t} B_t^{-1} A_{M_t}) \det (B_t)}{\det (B_t)} \right] \tag{S26} \\
&= -\frac{1}{2} \ln (1 + A'_{M_t} B_t^{-1} A_{M_t}) \nonumber
\end{align}$$

where we used the matrix determinant lemma with $B_t^{-1}$ and $A_{M_t} A'_{M_t}$.
## 2. Entropy assigned to the empirical suboptimal arms

Next, we consider the entropy assigned to the remaining suboptimal actions of $\mathcal{A}_t$. For each arm, denoted $A_t$, we assign the information gain regarding the event $\theta'_*(A_{M_t} - A_t) > 0$ of probability $C_{A_{M_t}, A_t}$:

$$C_{A_{M_t}>A_t} = \frac{1}{2} \left[ 1 + \operatorname{erf} \left( \frac{\hat{\theta}'[A_{M_t} - A_t]}{\sqrt{2[A_{M_t} - A_t]' B_t^{-1} [A_{M_t} - A_t]'}} \right) \right], \quad (S27)$$

with its associated entropy

$$S_{C,A_t} = -C_{A_{M_t}>A_t} \ln C_{A_{M_t}>A_t} - (1 - C_{A_{M_t}>A_t}) \ln (1 - C_{A_{M_t}>A_t}). \quad (S28)$$

To get a simplified expression we made a first-order expansion of $C_{A_{M_t}>A_t}$, and of its entropy. As for AIM approaches, we only focus on the asymptotic regime where the probability of a seemingly suboptimal arm being optimal is a rare event, in other words when $C_{A_{M_t}>A_t} \approx 1$. Surprisingly, this approximation is still accurate enough outside this asymptotic regime to provide a high-performance decision scheme. We first make a first-order expansion in the regime $C_{A_{M_t}>A_t} \approx 1$. Denoting the inner term of the error function in Eq. (S27) as $\frac{\delta}{\sqrt{2\Sigma}}$ with $\delta = \hat{\theta}'[A_{M_t} - A_t]$ and $\Sigma = [A_{M_t} - A_t]' B_t^{-1} [A_{M_t} - A_t]'$ leads to

$$C_{A_{M_t}>A_t} = \frac{e^{-\frac{\delta^2}{2\Sigma}}}{2\frac{\delta}{2\sqrt{\Sigma}}\sqrt{\pi}} (1 + o(1)) \quad (S29)$$

and

$$\tilde{S}_{C,A_t} \approx \frac{\delta e^{-\frac{\delta^2}{2\Sigma}}}{\sqrt{\Sigma} 2\sqrt{\pi}} \quad (S30)$$

Applying Eq. (S26) to $S$ for $A_t$ and multiplying it with Eq. (S30) viewed as a weight leads to the final expression given in the main text.

# S9. DETAILS OF ARM FOR THE MANY-ARMED SETTINGS

Here, we recapitulate all the steps leading to the analytical expression constitutive of our algorithm in the many-arms setting. We stress that it involves considerably simplifying our functional expression to get the final form of ARM. We will also evoke extensions to more general prior distributions.

We start by commenting on the partition scheme and their related approximations leading to both upcoming regret expressions given in the main text. The regret induced by solely selecting the currently better empirical arm is given by:

$$\tilde{R}_g = \tau \left( \mu_* - \int_{\mu_{\text{inf}}}^{\mu_{\text{sup}}} \mu p(\mu_{M_t} = \mu | \hat{\mu}_{M_t}, t_{M_t}, \Gamma) d\mu \right) \quad (S31) \\ \approx \tau(\mu_* - \hat{\mu}_{M_t}),$$

where $\tau$ denotes the remaining time and the integral spans over the mean reward of the current best empirical mean based on its history. To be more accurate, the resulting regret of a policy reevaluating the current best empirical arm at each time step should also account for the possibility that the best empirical arm may change over time. Yet, approximating this policy by the simpler strategy given by Eq. (S31) significantly simplifies the derivation without introducing undesirable behavior. We also approximate the mean posterior value by the empirical mean in Eq. (S31) which provides a greedy strategy to explore the most promising arm. Next, we derive the second upcoming regret expression given in the main text. We make a partition based on how the mean reward of the newly explored arm behaves compared to $\hat{\mu}_{M_t}$:

$$\tilde{R}_{\text{exp}} = \tau \int_{\hat{\mu}_{M_t}}^{\mu_{\text{sup}}} \Gamma(\mu)(\mu_* - \mu) d\mu + \int_{\mu_{\text{inf}}}^{\hat{\mu}_{M_t}} \Gamma(\mu) [(\mu_* - \mu)\tau_{\text{fpt}} + (\mu_* - \hat{\mu}_{M_t})(\tau - \tau_{\text{fpt}})] d\mu. \quad (S32)$$
The first term approximates cases where the new arm is better than $\hat{\mu}_{M_t}$. Here, we neglect cases where the new arm's mean falls below $\hat{\mu}_{M_t}$. The second term accounts for cases where the new arm mean is lower than $\hat{\mu}_{M_t}$. Our policy will continue pulling such unfavorable arms until their mean reward falls below $\hat{\mu}_{M_t}$, an event occurring on average after $\tau_{fpt}$ time steps. Finally, for consistency with Eq. (S31), we approximate the regret induced by solely selecting the current best empirical arm using $\hat{\mu}_{M_t}$. An efficient policy should avoid allocating exploration time to previously explored arms that already appear to be suboptimal, even if there is a finite probability that they may be the better choice. Given the large number of arms, our policy will either select arms with empirical means greater than or equal to $\hat{\mu}_{M_t}$ or explore an untested arm. Indeed, if the current best empirical mean starts to decline, there will always be a nearby arm with a similar empirical mean. Iterating this process, it becomes clear that the algorithm will end up finding an arm with a mean close to, if not better than, $\hat{\mu}_{M_t}$. This observation justifies that our greedy policy can be effectively approximated by $\hat{\mu}_{M_t}$. Therefore, we assume that cases where a better arm falls below $\hat{\mu}_{M_t}$ can be neglected, as such an arm will no longer impact the regret. Such probability may also be derived but doesn't seem to improve the algorithm's efficiency.

We now present the last steps to get a tractable expression, i.e., obtaining $\tau_{fpt}$ scaling. We label by $i$ the new tested arm:

$$ \tau_{fpt} = \min(\mathbb{E}[\min(s > t | \hat{\mu}_{M_t} > \hat{\mu}_i(s)) | \mu_i = \mu], \tau), \quad (S33) $$

where arm $i$ is drawn at each time until either $\hat{\mu}_i(s)$ falls below $\hat{\mu}_{M_t}$ or the time horizon is reached. Since the successive rewards are independent from each other, $\tau_{fpt}$ can be modeled by the first time where $\sum_{i}^{n} X_i < n\hat{\mu}_{M_t}$ with $X_i$ being independent identically distributed according to the reward distribution parameterized by $\mu$. It thus resumes as the mean first-passage time of a biased random walk dropping below $\hat{\mu}_{M_t}$. For an asymmetric jump distribution $\tau_{fpt}$ may be deduced from a generalized version of the Sparre-Andersen theorem [99–101]. By defining $q_+(n = \text{Prob}[x_n \ge 0, x_{n-1} \ge 0, \dots, x_0 = 0])$, and its associated generative series $\tilde{q}_+(s) = \sum_s q_+(n)s^n$. It states that

$$ \tilde{q}_+(s) = \exp \left[ \sum_{1}^{\infty} \frac{s^n}{n} \text{Prob} \left( \sum_{i}^{n} X_i \ge \hat{\mu}_{M_t} n \right) \right]. \quad (S34) $$

By noticing

$$ \begin{aligned} \tau_{fpt} &= \sum_{n=1}^{\infty} n[q_+(n-1) - q_+(n)] \\ &= \sum_{n=1}^{\infty} q_+(n-1) + \sum_{n=1}^{\infty} (n-1)q_+(n-1) - \sum_{n=1}^{\infty} nq_+(n) \\ &= \tilde{q}_+(1) \end{aligned} \quad (S35) $$

we obtain using Eq. (S34)

$$ \tau_{fpt} = \exp \left[ \sum_{1}^{\infty} \frac{1}{n} \text{Prob} \left( \sum_{i}^{n} X_i \ge \hat{\mu}_{M_t} n \right) \right]. \quad (S36) $$

This general expression holds for an asymmetric jump distribution, or equivalently, for a general reward distribution. To get a typical behavior, we approximate the jump distribution by a Gaussian of mean $\mu$ and unit variance. Applying it to Eq. (S36) gives:

$$ \tau_{fpt} = \exp \left[ \sum_{1}^{\infty} \frac{1}{2n} \text{erfc} \left( \frac{\sqrt{n}}{\sqrt{2}} (\hat{\mu}_{M_t} - \mu) \right) \right]. \quad (S37) $$

There is no exact expression for Eq. (S37), we hence focus on extracting the scaling of $\tau_{fpt}$. We first focus on the limit case where $\mu \sim \hat{\mu}_{M_t}$. In this regime, the erfc function will behave as $1/2$ until a cutoff $\sqrt{n_c}(\hat{\mu}_{M_t} - \mu)^{-1} \sim O(1)$. Hence, the leading order behaves as

$$ \begin{aligned} \tau_{fpt} &= \exp \left[ \frac{1}{2} \ln \left( \frac{1}{(\hat{\mu}_{M_t} - \mu)^2} \right) + O(1) \right] \\ &= O \left( [\hat{\mu}_{M_t} - \mu]^{-1} \right). \end{aligned} \quad (S38) $$
This regime includes all cases where the probability of observing diverging $\tau_{fpt}$ is the highest. In cases where $\hat{\mu}_{Mt} - \mu = O(1)$, the algorithm will mostly come back to $\hat{\mu}_{Mt}$ after a few steps, which is also given by Eq. (S38). Hence, we assume to extend this approximation in all regimes, leading to the $\tau_{fpt}$ scaling given in the main text.

$$ \tau_{fpt}(\mu) = \frac{c}{\hat{\mu}_{Mt} - \mu} \qquad (S39) $$

Combining Eqs. (S31) and (S39) altogether gives the following decision criteria

$$ \begin{aligned} \Delta &= \tilde{R}_{\text{exp}} - \tilde{R}_{\text{g}} = \tau \int_{\hat{\mu}_{Mt}}^{\mu_{\text{sup}}} \Gamma(\mu)(\mu_{*} - \mu) d\mu + \int_{\mu_{\text{inf}}}^{\hat{\mu}_{Mt}} \Gamma(\mu) [(\mu_{*} - \mu)\tau_{\text{fpt}} + (\mu_{*} - \hat{\mu}_{Mt})(\tau - \tau_{\text{fpt}})] d\mu - \tau(\mu_{*} - \hat{\mu}_{Mt}) \\ &= \tau \int_{\hat{\mu}_{Mt}}^{\mu_{\text{sup}}} \Gamma(\mu)(\hat{\mu}_{Mt} - \mu) d\mu + \int_{\mu_{\text{inf}}}^{\hat{\mu}_{Mt}} \Gamma(\mu)(\hat{\mu}_{Mt} - \mu) \tau_{\text{fpt}} d\mu \\ &= \tau \int_{\hat{\mu}_{Mt}}^{\mu_{\text{sup}}} \Gamma(\mu)(\hat{\mu}_{Mt} - \mu) d\mu + c \int_{\mu_{\text{inf}}}^{\hat{\mu}_{Mt}} \Gamma(\mu) d\mu. \end{aligned} \qquad (S40) $$

For a uniform prior, it resumes as the expression given in the main text :

$$ \Delta = c \frac{\hat{\mu}_{Mt} - \mu_{\text{inf}}}{\mu_{\text{sup}} - \mu_{\text{inf}}} - \frac{\tau}{2} \frac{(\mu_{\text{sup}} - \hat{\mu}_{Mt})^2}{\mu_{\text{sup}} - \mu_{\text{inf}}}. \qquad (S41) $$

Finally for a uniform prior on $[0, 1]$, it simplifies into :

$$ \Delta = c\hat{\mu}_{Mt} - \tau \frac{(1 - \hat{\mu}_{Mt})^2}{2} \qquad (S42) $$

1. Heuristic arguments supporting asymptotic optimality

To further support the empirical evidence of ARM optimality, we consider the asymptotic regime where the algorithms have just converged on a promising arm, given by $\Delta \approx 0$ in Eq. (S42) which is fulfilled when :

$$ \tau(1 - \hat{\mu}_{Mt})^2 \sim O(1). \qquad (S43) $$

We denote $t_f = T - \tau$ the time spent, and by $n_f$ the current number of tested arms. We assume that $n_f$ scales as $O(t_f)$ as long as the promising arm is not found. For a uniform prior, and assuming that the promising arm belongs to the best arms of the subset, the expected regret $(1 - \hat{\mu}_{Mt})$ will thus scale as $1 - \mu_i \sim 1/n_f \sim 1/t_f$. Injecting such scaling into Eq. (S43) leads to $\tau t_f^2 \sim 1$ reached for the first time when $t_f \sim \sqrt{T}$. Hence, the past regret will scale as $t_f \sim \sqrt{T}$ and the resulting upcoming regret of exploiting $\hat{\mu}_{Mt}$ will scale as $\sqrt{\tau} \sim \sqrt{T}$ ensuring the expected optimal scaling. To derive a complete proof, it will be necessary to ensure that the algorithm doesn't fail to identify $\hat{\mu}_{Mt}$ when tested and not longer spend most of its time trying to identify $\hat{\mu}_{Mt}$ within the arm subset.

S10. NUMERICAL EXPERIMENTS

A. Numerical settings

1. Explore-m bandit setting

We here consider Gaussian rewards with $\sigma = 1$. The $\epsilon$-optimal subset size verifies $m = n/5$ with an increasing number of arms tested. In Fig. 2 (a) the mean rewards values are sampled from two disjoint ensembles $[0, 0.8]$ and $[0.9, 1]$ for the $\epsilon$-optimal subset, with confidence parameters $\epsilon = 0.05$, $\delta = 0.1$. In Fig. 2 (b) suboptimal mean rewards values are all set to 0.7 while $\epsilon$-optimal to 0.8, with confidence parameters $\epsilon = 0.05$, $\delta = 0.02$. For both experiments, the time is averaged over 100 runs with standard deviation indicated. Here, seeds are not shared through the algorithms within the same experiment.
## 2. Linear bandit setting

We here again consider rewards subject to Gaussian noise with $\sigma = 1$. In the first experiment, the arms composing $A_t$ are sampled from a normal distribution in $\mathbb{R}^{10}$. $\theta_*$ is assigned a unit norm. The seeds are taken independently for each algorithm. The regret, averaged over 100 runs, already shows a clear and consistent standard deviation. In the second experiment, $\xi = 0.1$ and the $A_t$ are constituted by two fixed sets $\{[1, 0, 0], [0, 1, 0], [1 - \xi, 2\xi, 0]\}$, the second set $\{[0, 0, 6, 0, 8], [0, 0, 1], [0, \xi/10, 1 - \xi]\}$, presented to the agent with equal probability and $\xi = 0.1$, finally $\theta_* = [1, 0, 1]$. The regret, averaged over 1000 runs, already shows a clear and consistent standard deviation. Here, seeds are shared through the algorithms within the same experiment.

## 3. Many armed bandit setting

Here, we consider Bernoulli rewards with a uniform prior. In (a), the parameters used are $T = 10000$, $K = 5000 \gg \sqrt{T}$ and $c = 1$. The regret is averaged over 2000 runs. In (b) the mean regret performance when the horizon is reached is given for distinct games with varying horizon length ($K = T \gg \sqrt{T}$ and $c = 1$). The regret is averaged over 2000 runs for each experiment. Here, seeds are shared through the algorithms within the same experiment.

# B. Overview of baselines algorithms

We will here review the algorithm used for numerical comparison.

## 1. Top-k identification: LUCB1

We rely on the algorithm version first introduced in [41]. It falls under the category of upper confidence bound (UCB) algorithms, which select the arm maximizing a proxy function typically defined as $F_i = \hat{\mu}_i + C_i(t_i, t)$. In the specific case of subset selection, it reformulates as follow. We define $B_i$ as

$$C_i(t_i, t) = \sqrt{\frac{1}{2t_i} \ln \left[ \frac{5nt^4}{4\delta} \right]}. \qquad (S44)$$

After having sorted the arms according to their current empirical means and having formed $M_t$ and $D_t$, the algorithm selects two arms, denoted $l_{top,t}$ and $h_{bot,t}$, respectively in $M_t$ and $D_t$ such that

$$l_{top,t} = \underset{i \in M_t}{\operatorname{argmin}} (\hat{\mu}_i - C_i(t_i, t)), \qquad (S45)$$

and

$$h_{bot,t} = \underset{i \in D_t}{\operatorname{argmax}} (\hat{\mu}_i + C_i(t_i, t)). \qquad (S46)$$

Then, the algorithm stops if

$$\hat{\mu}_{h_{bot,t}} + C_{h_{bot,t}}(t_{h_{bot,t}}, t) - \hat{\mu}_{l_{top,t}} + C_{l_{top,t}}(t_{l_{top,t}}, t) < \epsilon, \qquad (S47)$$

meaning that both sets are sufficiently differentiated. If the algorithm does not stop, both arms $l_{top,t}$ and $h_{bot,t}$ are pulled, and the process is repeated.

## 2. Linear bandit: LinUCB

As for the subset selection, we provide algorithms falling into the upper confidence bound (UCB) category. These algorithms select the arm maximizing a proxy function typically defined as $F_{i,t} = \hat{\mu}_{i,t} + C_{i,t}$. In the linear case $\hat{\mu}_i$ stands for the empirical mean of drawing arm $i$ at $t$ and $C_i$ an associated confidence ellipsoid. The first LinUCB-type algorithm considered in the numerical experiments, referred to as OFUL [87], is given by
$$F_{i,t} = \hat{\theta}'_t A_t + \left[ \sqrt{d \ln(n(1+t))} + 1 \right] \sqrt{A'_t B_t^{-1} A_t}, \qquad (S48)$$

where $d$ stands for the dimension of the arms space, $n$ the arm number at each time step, and $B_t$ as $\hat{\theta}_t$ are defined as in the main text. The second version borrowed from [26], denoted LinUCB here, reads

$$F_{i,t} = \hat{\theta}'_t A_t + \left[ \sqrt{2 \ln(n) + \ln(|B_t|)} + 1 \right] \sqrt{A'_t B_t^{-1} A_t}, \qquad (S49)$$

where $||$ denotes the determinant operator. We now briefly discuss several potential candidate algorithms that were not implemented in this work. One such algorithm is Lin-Thompson, a refined version of the popular Thompson sampling approach. However, the linear variant of Lin-Thompson, which comes with theoretical guarantees, has a critical drawback: its posterior distribution's variance is adjusted by a factor of $\ln(t)$ [48]. This adjustment leads to over-exploration and consequently, significant regret losses, rendering the algorithm inadequate for meaningful performance comparisons. In addition to Lin-Thompson, we could consider comparing our algorithm with other state-of-the-art methods such as SOLID [64], OSSB [85], OAM [88], and IDS [92]. Nevertheless, these algorithms suffer implementation complexities that are not tackled in our current work.

### 3. Many-arms: SS-epsilon greedy

The subsampled greedy algorithm for many-armed settings randomly selects a subset of $m$ arms and performs a greedy strategy after pulling all the arms once. Its pseudo code reads:

* Select $m$ arms uniformly at random without replacement from $[K]$ and pull each arm once.

* Until the end pulls $a_t = \underset{i \in [K]}{\operatorname{argmax}} \hat{\mu}_i$.

The size of the subset is the only parameter that is adjusted depending on the horizon sizes and the reward distribution. [95] proposes $m \sim T^{\beta/(1+\beta)}$ for $\beta$-regular prior, i.e., $\mathbb{P}_{\Gamma}[\mu > 1 - \epsilon] = O(\epsilon^{\beta})$.

### C. Additional figures

<figure><img src="image_6.png" /><figcaption>SUPPLEMENTARY FIG. S1. Success probability of the Explore-$m$ experiments presented in the main text. The probability of identifying the $\epsilon$-optimal subset is averaged over 100 runs for different numbers of arms $n$. Results are shown for our algorithm (blue) and LUCB1 [41] (red). The $\epsilon$-optimal subset size satisfies $m = n/5$. (a) Mean reward values are sampled from two disjoint ensembles [0, 0.7] and [0.8, 1], with confidence parameters $\epsilon = 0.05$ and $\delta = 0.1$. (b) Suboptimal mean reward values are fixed at 0.7, while $\epsilon$-optimal rewards are set to 0.8, with confidence parameters $\epsilon = 0.05$ and $\delta = 0.02$. Both experiments demonstrate an empirical success probability exceeding the tolerance threshold $1 - \delta$, validating the stopping time measured in the main text.</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>SUPPLEMENTARY FIG. S2. Mean regret for two linear bandit settings with Gaussian rewards. This figure is identical to the one given in the main text but with standard deviation shown with error bars. In blue our algorithm and in orange and red UCB algorithms adjusted to the linear settings. (a) Bandit setting with 10 arms resampled at each time from a normal distribution in $R^{10}$. (b) Toy problem borrowed from [64] with two contexts. Each context (detailed in the main text) is drawn with equal probability and $\xi = 0.5$. Details of the algorithms, simulations and a focus on standard deviations are provided in Section S10.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>SUPPLEMENTARY FIG. S3. Mean regret for the many-armed bandit problem with Bernoulli rewards and a uniform prior on [0, 1]. This figure is identical to the one given in the main text but with standard deviation shown with error bars. (a) The regret growth of our algorithm (ARM), in blue, is observed until horizon $T$, i.e the stopping time, is reached $T = 10000$ ($K = 5000 \gg \sqrt{T}$ and $c = 1$). The regret is averaged over 2000 runs and standard error are indicated (see Supplementary Material Sections S10 and S10B for details on the numerical settings). Its performance is compared to the ss-greedy algorithm, in red. The final slopes of both algorithms differs indicating that the selected arm for most of the exploitation is less efficient than the one found for our algorithm. Additionally, our algorithm presents a slower initial slope because exploration and exploitation are already mixed. (b) Mean regret performance when at the stopping time (when the horizon is reached), for distinct games with varying horizon length ($K = T \gg \sqrt{T}$ and $c = 1$). The regret is averaged over 2000 runs.</figcaption></figure>