On Bits and Bandits: Quantifying the Regret-Information Trade-off

## Abstract

Abstract In many sequential decision problems, an agent performs a repeated task. He then suffers regret and obtains information that he may use in the following rounds. However, sometimes the agent may also obtain information and avoid suffering regret by querying external sources. We study the trade-off between the information an agent accumulates and the regret it suffers. We invoke information-theoretic methods for obtaining regret lower bounds, that also allow us to easily re-derive several known lower bounds. We introduce the first Bayesian regret lower bounds that depend on the information an agent accumulates. We also prove regret upper bounds using the amount of information the agent accumulates. These bounds show that information measured in bits , can be traded off for regret, measured in reward. Finally, we demonstrate the utility of these bounds in improving the performance of a question-answering task with large language models, allowing us to obtain valuable insights.

## 1 Introduction

In interactive decision-making problems, an agent repeatedly interacts with a task by sequentially choosing decisions from a decision space. Subsequently, the agent receives feedback that usually includes a reward and, optionally, other types of information. For example, the feedback includes only the reward in multi-armed bandit (MAB) problems [Lattimore and Szepesvári, ]. In partial monitoring, however, it only includes a signal, which the agent then utilizes to indirectly infer the reward [Cesa-Bianchi et al., ]. The goal of the agent in such tasks is to minimize the gap between the accumulated reward and the reward of the best decision in hindsight, also known as regret.

In these tasks, agents can accumulate information from multiple sources, that can be categorized into two main types. One is information acquired through direct interactions and receiving feedback from the task. For example, in reinforcement learning (RL) such information includes visited states, accumulated rewards, and performed actions. The other type is information provided by external sources, such as human advice [Najar and Chetouani, ], text description generated by large language models [Du et al., , Hu and Sadigh, ], and more.

Resource allocation is an example of a task that combines both types of information. In this task, our goal is to route a process from a mobile device to a server while minimizing energy consumption and execution time [Zuo and Joe-Wong, ]. In this task, we can accumulate information directly by routing processes and receiving feedback. However, we also have relevant information that can be obtained from other sources, such as server specifications, load information, and more.

Consider two agents playing on the same online task. Both agents have access to the same observations, but the first agent has already played multiple rounds in the task. Thus, he already suffered regret and gained an advantage over the second agent. Before he starts interacting with the task, the second agent can use external knowledge that will allow him to reach the same performance level as the first agent. In this paper, we focus on how much information the second agent needs to query so he will "catch up" with the first agent without suffering regret. In other words, we focus on the following question:

What is the exact relationship between information bits and regret?

Figure: Figure 1: Schematic of a general interactive decision-making task with contextual information. Every round, a source of knowledge provides our agent with information. The agent then makes a decision, that causes the task to generate an observation and a reward. The observation is revealed to the agent, who updates his next decision according to the past observations and the information he received.
Refer to caption: x1.png

### 1.1 Contributions

##### New method for obtaining regret lower bounds.

We introduce a novel information-theoretic method to obtain regret lower bounds for a wide variety of interactive decision-making problems. This method uses Fano’s inequality [Cover, ] and the construction method introduced by Yang and Barron [] to lower bound the worst-case Bayesian regret. We then use this method to derive lower bounds for MAB, contextual bandit, and RL tasks.

##### Information-theoretic prior-dependent bounds.

We consider an interactive decision-making framework that describes general online tasks with contextual information in a Bayesian setting. We examine the regret of policies with a mutual information constraint and obtain Bayesian regret lower bounds that depend on the amount of information an agent accumulates. Additionally, we show upper bounds for Thompson sampling [Thompson, ] in an MAB environment, which depends on the information the agent collects. We also present lower bounds for scenarios where the entropy of the prior is constrained, for a specific family of algorithms.

##### Regret-information trade-off.

We show that the presented lower bounds quantify the relationship between external information and regret. Furthermore, these bounds quantify the relationship between the rate of information accumulation and regret in online tasks. These relationships allow us to measure how much regret can be avoided by looking at the information that can be accumulated. We then demonstrate how to easily utilize this insight in an online question-answering task with large language models.

The rest of the paper is organized as follows: In Section 2 we present our setting and relevant preliminaries. In Section 3 we present a novel information-theoretic method for obtaining regret lower bounds. In Section 4 we present regret bounds that depend on the information accumulated by the agent, followed by experiments in Section 5. In Section 6 we review related work, and draw conclusions in Section 7.

## 2 Setting and Preliminaries

We introduce a new setting called interactive decision-making in Bayesian environments with contextual information, which is illustrated in Figure 1. This setting is a Bayesian adaptation of the frequentist interactive decision-making setting introduced by Foster et al. []. We denote the set of Borel probability measures over a locally compact space by $\Delta(\cdot)$. Let $\Pi$ be a compact decision space, $\mathcal{M}$ be a compact model space and $\mathcal{C}$ be a compact context space. Every model $M\in\mathcal{M}$ is a mapping from the decision and context space to an observation space $\mathcal{O}$, i.e., $M:\Pi\times\mathcal{C}\to\mathcal{O}$. Every model $M$ has a reward function, $R_{M}:\Pi\times\mathcal{C}\to\Delta([0,1])$ that maps every decision-context pair to a reward distribution over $[0,1]$. A task in this setting is defined by the decision space $\Pi$, the model class $\mathcal{M}$, the context space $\mathcal{C}$, the reward functions $R_{M}$, and the prior $P\in\Delta(\mathcal{M}\times\mathcal{C})$. We denote by $\mu_{M}(\pi,C)=\mathbb{E}_{x\sim R_{M}(\pi,C)}[x]$ the mean reward of decision $\pi$ under model $M$ and context $C$. With a slight abuse of notation, we also denote by $\mu_{M}(\phi,C)=\mathbb{E}_{\pi\sim\phi}[\mu_{M}(\pi,C)]$, the mean reward of a policy $\phi\in\Delta(\Pi)$ under model $M$ and context $C$.

In a $T$-round game, a random model $M$ is sampled before the game starts according to the prior $P$. Then a context $C_{t}$ is sampled every round, independently from previous rounds, according to the marginal prior probability $P(\cdot\mid M)$. Before each round starts, the context $C_{t}$ is revealed to the agent, who determines his policy $p_{t}:\mathcal{C}\to\Delta(\Pi)$ according to the context and the observed history. Then, a decision $\pi_{t}\sim p_{t}$ is sampled and an observation $O_{t}\sim M(\pi_{t},C_{t})$ is revealed to the agent. A reward, $r_{t}\sim R_{M}(\pi_{t},C_{t})$ is also generated. We denote the history up to time $t$ as $\mathcal{H}_{t}=\{C_{i},\pi_{i},O_{i}\}_{i=1}^{t}$. We measure the performance with respect to the best context-dependent decision in hindsight. This performance metric is called the Bayesian regret and is defined by

$$ $\mathcal{BR}_{P}(T;\{p_{t}\}_{t=1}^{T})=\sup_{\pi^{*}:\mathcal{C}\to\Pi} \mathbb{E}\left[\sum_{t=1}^{T}\left(\mu_{M}(\pi^{*}({C_{t}}),C_{t})-r_{t} \right)\right]$ (1) $$

where the expectation is taken with respect to the randomness in decisions, contexts, observations, and rewards ($(M,C_{t})\sim P$, $\pi_{t}\sim p_{t}$ and $r_{t}\sim R_{M}(\pi_{t},C_{t})$). We also note that by fixing a single context, $\left|\mathcal{C}\right|=1$, the setting reduces to regular Bayesian interactive decision-making. When obvious from the context, $P$ and $\{p_{t}\}_{t=1}^{T}$ are omitted. We next show how our general framework covers common decision-making tasks with contextual information.

###### Example 2.1 (Contextual MAB with Bernoulli rewards) .

The contextual MAB problem is defined by the rewards of each arm, which are, say, Bernoulli random variables. For simplicity, we assume a finite set of decisions, which are called arms in this setting, $\Pi=\{1,2,\dots,K\}$. Furthermore, we assume that the context space is finite as well, $\mathcal{C}=\{1,2,\dots,C\}$. The model class is then given by $\mathcal{M}=\{f|f:\Pi\times\mathcal{C}\to[0,1]\}$, so every model maps $\left(\pi,C\right)$ to $\mathrm{Bern}(f(\pi,C))$. At each round $t$, a context is sampled and revealed. A decision $\pi_{t}$ is selected and the observation is the incurred reward, $r_{t}=O_{t}\sim\mathrm{Bern}(f_{t}(\pi_{t},C_{t}))$.

###### Example 2.2 (Tabular reinforcement learning with a finite horizon) .

The finite-horizon tabular MDP is defined by the tuple $(\mathcal{S},\mathcal{A},\mathbb{P},\mathbb{R},H)$ (which are the state space, action space, transition kernel, reward function and horizon, accordingly). We assume the episodic and stationary setting, where we update the policy only at the beginning of every episode. Additionally, we assume that the reward of every episode is bounded in $[0,1]$. In this setting, the decision space is all of the deterministic policies, so $\Pi=\{\pi:\mathcal{S}\times\mathcal{H}\to\mathcal{A}\}$. The model class $\mathcal{M}$ is defined by the set of all MDPs with the same state space, action set, and horizon. At every time step, the agent determines a policy and plays it over the entire horizon. The observations are the trajectories, which include the visited states, rewards, and actions performed.

###### Example 2.1 (Contextual MAB with Bernoulli rewards) .

###### Example 2.2 (Tabular reinforcement learning with a finite horizon) .

##### Covering and packing.

Consider a normed space $A$ with metric $d$ induced by the norm, and let $\epsilon>0$. We denote by $\mathcal{N}(d,A,\epsilon)$ and $\mathcal{M}(d,A,\epsilon)$ the $\epsilon$-covering and $\epsilon$-packing numbers of $A$ under the norm $d$, respectively. We define an $\epsilon$-local set of $A$ as $B(b,\epsilon)=\{a\in A:d(b,a)\leq\epsilon\}$, for every $b\in A$ and $\epsilon>0$. The local packing number, denoted by $\mathcal{M}^{\mathrm{loc}}\left(d,A,\epsilon\right)$, is the largest $(\epsilon/2)$-packing set of any set $B(b,\epsilon)$, i.e.,

$$ $\displaystyle\mathcal{M}^{\mathrm{loc}}\left(d,A,\epsilon\right)=\max\left\{M: \text{there is }b\text{ such that the }(\epsilon/2)\text{-packing number of }B (b,\epsilon)\text{ is }M\right\}.$ $$

When $d(x,y)=\left\|x-y\right\|_{p}$ we denote by $\mathcal{M}_{p}(A,\epsilon),\mathcal{N}_{p}(A,\epsilon)$ and $\mathcal{M}^{\mathrm{loc}}_{p}\left(A,\epsilon\right)$ the $\epsilon$-packing, $\epsilon$-covering and $\epsilon$-local packing number, respectively. Detailed definitions and properties of the covering, packing and local packing numbers are provided in Appendix B.

##### Additional notations.

We denote by $H(X)=\mathbb{E}\left[-\log Q(X)\right]$ the Shannon entropy of a random variable $X\sim Q$, and with a slight abuse of notation, we also denote $H(Q)=H(X)$. Given two jointly distributed random variables, $(X,Y)\sim Q$, we denote their marginal distributions by $Q(x)$ and $Q(y)$. We also define the mutual information of two jointly distributed random variables $(X,Y)\sim Q$ as $I(X;Y)=\mathbb{E}\left[\log\left(\frac{Q(X,Y)}{Q(X)Q(Y)}\right)\right]$. The KL-divergence is defined as $D\left(P,Q\right)=\mathbb{E}_{X\sim P}\left[\log\frac{P(X)}{Q(X)}\right]$ [Cover, ]. Unless stated otherwise, logarithms are assumed to be in base-2, denoted by $\log$. We also denote $x\gtrsim y$ if there is some global constant $c>0$ such that $x\geq cy$. We define by $\mathbb{B}_{p}^{d}=\{x\in\mathbb{R}^{d}:\left\|x\right\|_{p}\leq 1\}$ the unit sphere in $\mathbb{R}^{d}$ under the $L_{p}$ norm.

**Table 1: Lower bounds for online problems, recovered using methods presented in the paper.**
| Problem | Retrieved lower bound | Optimal? |
| --- | --- | --- |
| MAB | $\Omega(\sqrt{KT})$ | Yes [Audibert and Bubeck, ] |
| Tabular RL | $\Omega(\sqrt{HSKT})$ | Yes [Zhang et al., ] |
| Linear bandits | $\Omega(\sqrt{dT})$ | No |
| Lipschitz bandit | $\Omega\left(T^{\frac{d+1}{d+2}}\right)$ | Yes [Kleinberg et al., ] |
| Bayesian MAB ($R$ bits) | ${\Omega\left(\sqrt{KT\frac{\log K}{R}}\right)}$ | First bound |
| Bayesian linear MAB ($R$ bits) | $\Omega\left(\sqrt{dT\frac{\log K}{R}}\right)$ | First bound |
| Bayesian MAB | $\Omega\left(\sqrt{KT\frac{H(\pi^{*})}{\log K}}\right)$ | First bound |

## 3 Regret Lower Bounds Using Fano’s Inequality

We now introduce a novel approach for obtaining worst-case Bayesian regret lower bounds, which can be applied to a wide variety of interactive decision-making tasks. This method can be viewed as an extension of Fano’s inequality for non-exact recovery [Scarlett and Cevher, ] to online problems. We define worst-case Bayesian regret in the following manner,

$$ $\sup_{\nu\in\Delta(\mathcal{M}\times\mathcal{C})}\inf_{\{p_{t}\}_{t=1}^{T}} \mathcal{BR}_{\nu}(T;\{p_{t}\}_{t=1}^{T})\equiv\mathcal{BR}^{*}(T).$ (2) $$

To lower bound the worst-case Bayesian regret we use Fano’s inequality.

###### Theorem 3.1 (Fano’s inequality, Theorem 2.10 of Cover [ 1999 ] ) .

Let $X,Y\sim Q$ be two jointly distributed random variables, where $X$ can take values over a finite set, whose cardinality is $\mathcal{X}$. Let $\hat{X}=f(Y)$ for some $f$ be an estimator of $X$. If $\hat{X}$ is uniformly distributed over all possible values in $\mathcal{X}$, then the following holds for all $f$,

$$ $\mathbb{P}(X\neq\hat{X})\geq 1-\frac{I(X;Y)+1}{\log\mathcal{X}}.$ (3) $$

While Theorem 3.1 is used to lower-bound the error in hypothesis testing problems, we now show how it can also be applied to regret minimization. We assume access to some set $\Phi=\{\phi_{1},\dots,\phi_{K}\}$ of (possibly stochastic) policies. We also assume that a metric $\rho$ exists such that $\mathbb{E}[\left|\mu_{M}(\psi,C)-\mu_{M}(\phi,C)\right|]\geq\rho(\phi,\psi)$ for all $\psi,\phi\in\Delta(\Pi)$. The following proposition applies Theorem 3.1 to regret minimization, by reducing it to a hypothesis testing over the finite set $\Phi$.

###### Proposition 3.2 .

For any algorithm, prior $P$, a decision set $\Phi=\{\phi_{1},\dots,\phi_{K}\}\subseteq\Delta(\Pi)$ and for all $\epsilon>0$ such that $\rho(\phi_{i},\phi_{j})\geq\epsilon$ for all $i\neq j$,

$$ $\displaystyle\frac{\mathcal{BR}_{P}(T)}{T\epsilon}\geq\frac{1}{2}\left[1-\frac {I(V;\mathcal{H}_{T})+1}{\log K}\right]$ (4) $$

where $V$ is the index of the best decision in hindsight from the set $\Phi$.

The proof of Proposition 3.2 is provided in Appendix C.1. Proposition 3.2 allows us to lower-bound the Bayesian regret using a specific set of decisions. We suggest a method for selecting the decision set $\Phi$, which provides a general approach for obtaining regret lower bounds. We separate our analysis into finite, parametric with infinite decisions, and non-parametric decision spaces. This separation is done to make the lower bound in Equation 4 tighter. We observe that the lower bound is tighter for larger values of $K$. Thus, we should select the largest value of $K$ that satisfies the requirement $\rho(\phi_{i},\phi_{j})\geq\epsilon$ for a given $\epsilon>0$. For finite decision spaces, we choose $\Phi$ to be an $\epsilon$-local packing set of the decision simplex, $\Delta(\Pi)$, according to $\rho$, under $P$. So, we have $K={\mathcal{M}}^{\mathrm{loc}}(\rho,\Delta(\Pi),\epsilon)$. Similarly, for parametric decision spaces with infinite decisions, we choose $\Phi$ to be an $\epsilon$-local packing set of the decision set, $\Pi$, i.e., $K={\mathcal{M}}^{\mathrm{loc}}(\rho,\Pi,\epsilon)$. For non-parametric decision spaces, we use an $\epsilon$-global packing set of our decision space $\Pi$, which means that $K=\mathcal{M}(\rho,\Pi,\epsilon)$.
After selecting $\Phi$, we need to handle $I(V;\mathcal{H}_{T})$. To do this, we make the following assumption about the policies.

###### Assumption 3.1 .

There exist constants $\bar{A},\epsilon_{0}>0$ such that for all policies $p_{1},p_{2}$ such that $\rho(p_{1},p_{2})\leq\epsilon_{0}$, $D\left(p_{1},p_{2}\right)\leq 2\bar{A}\rho(p_{1},p_{2})^{2}$.

This assumption is also made by Yang and Barron []. The following theorem upper bounds $I(V;\mathcal{H}_{T})$.

###### Theorem 3.3 ( Yang and Barron [ 1999 ] ) .

Let Assumption 3.1 hold. Under the assumptions and notations of Proposition 3.2,
if $\Pi$ is a parametric decision space then

$$ $I(V;\mathcal{H}_{T})\leq 2\bar{A}\epsilon^{2}T$ (5) $$

for $\epsilon\leq\epsilon_{0}$. If $\Pi$ is a non-parametric decision space then

$$ $I(V;\mathcal{H}_{T})\leq\inf_{\delta>0}\left(\log\mathcal{N}\left(\rho,\Pi, \sqrt{\delta}\right)+T\delta\right).$ (6) $$

Now, substituting Theorem 3.3 in Proposition 3.2, and selecting $\Phi$ as we described above, results in the following Theorem.

###### Theorem 3.4 .

Let there be a Bayesian interactive decision-making problem as defined in Section 2, and let $\epsilon>0$. If $\Pi$ is a finite decision space,

$$ $\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\geq\frac{1}{2}\left[1-\frac{2\epsilon^{2 }\bar{A}T+1}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Delta(\Pi),\epsilon)}\right].$ (7) $$

If $\Pi$ is an infinite parametric decision space,

$$ $\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\geq\frac{1}{2}\left[1-\frac{2\epsilon^{2 }\bar{A}T+1}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Pi,\epsilon)}\right].$ (8) $$

If $\Pi$ is a non-parametric decision space,

$$ $\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\geq\frac{1}{2}\left[1-\frac{\inf_{\delta >0}\left(\log\mathcal{N}\left(\rho,\Pi,\sqrt{\delta}\right)+T\delta\right)+1}{ \log\mathcal{M}(\rho,\Pi,\epsilon)}\right].$ (9) $$

The proof of Theorem 3.4 is provided in Appendix C.2. To obtain regret lower bounds, all we need are the values of the packing or local packing, and covering numbers of the decision space. Then, we simply need to select a value of $\epsilon$ such that the right-hand side of Equations 7, 8 or 9 is a positive constant. In Appendix C.3 we demonstrate this, by deriving regret lower bounds for several known online problems, which are summarized in Table 1. Moreover, this method can be used to obtain lower bounds for the frequentist regret, due to the mini-max theorem, which states that the worst-case Bayesian regret is equal to the mini-max frequentist regret [Lattimore and Szepesvári, ].

###### Theorem 3.1 (Fano’s inequality, Theorem 2.10 of Cover [ 1999 ] ) .

###### Proposition 3.2 .

###### Assumption 3.1 .

###### Theorem 3.3 ( Yang and Barron [ 1999 ] ) .

###### Theorem 3.4 .

## 4 Information Theoretic Bayesian Regret Lower Bounds

### 4.1 Mutual Information Constraint

We now derive Bayesian regret bounds under a constraint on the total amount of information that the agent accumulates. Intuitively, in information-theoretic terms, mutual information quantifies the amount of information one random variable contains about another one [Cover, ]. This means that mutual information can be utilized to measure the information that is aggregated from various sources using a common measure of bits. We are interested in lower bounding the regret, under a constraint on the amount of information the agent accumulates. Then, we ask the following question: What is the lower bound of the worst-case Bayesian regret, when the agent accumulates less than $R$ bits of information? We will use the method described in Section 3 to derive regret lower bounds under this constraint. We note that in general $I(\pi^{*};\mathcal{H}_{T})=D\left(P^{\pi^{*}\mid\mathcal{H}_{T}},P^{\pi^{*}}\right)$. Thus, for general agents, $D\left(p_{t},P^{\pi^{*}}\right)$ is the information accumulated up to round $t$, in bits. The following proposition answers this question, for problems with a finite decision space.

###### Proposition 4.1 .

Let $0<R\leq\log K$ be given. Assume that the Bayesian decision problem has a finite decision space of size $K$, and that the agent accumulates no more than $R$ bits. Then the worst-case Bayesian regret can be lower bounded by $\Omega\left(\sqrt{TK\frac{\log K}{R}}\right)$. Additionally, if $\ \Pi\subset\mathbb{B}_{2}^{d}$ and the rewards are a linear function of the decisions, then the worst-case Bayesian regret can be lower bounded by $\Omega\left(\sqrt{Td\frac{\log K}{R}}\right)$. Furthermore, if $R=0$ the worst-case regret is linear.

The proof of Proposition 4.1 utilizes Lemma D.1, which, similarly to the proof of Theorem 3.3, introduces an upper bound for the mutual information, but this time taking the information constraint into account.
The rest of the proof follows a similar structure to the proof of Theorem 3.4, substituting the tighter bound into Equation 7. This yields the following proposition.

###### Proposition 4.2 .

Let $R\leq\log K$ be given. Assume that the Bayesian decision problem has a finite decision space of size $K$, such that $D\left(p_{t},P^{\pi^{*}}\right)\leq R$ for all $t$. Then,

$$ $\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\geq\frac{1}{2}\left[1-\frac{2\epsilon^{2 }\bar{A}T\frac{R}{\log K}+1}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Delta(\Pi), \epsilon)}\right]$ (10) $$

Furthermore, if the decision-making problem is a part of a parametric set, then

$$ $\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\geq\frac{1}{2}\left[1-\frac{2\epsilon^{2 }\bar{A}T\frac{R}{\log K}+1}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Pi,\epsilon) }\right]$ (11) $$

The proof follows from Proposition 4.2, by selecting an appropriate value of $\epsilon$. We now state an upper bound for MAB problems where the agent accumulates $R$ bits.

###### Proposition 4.3 .

Assume an $K$-MAB problem with no constraints. Let $\tilde{O}_{t},\tilde{\mathcal{H}}_{T}$ be constrained observations and history such that $I(\pi^{*};\tilde{\mathcal{H}_{T}})=R$. The regret of a policy that utilizes Thompson sampling with these observations is upper bounded by $O\left(\log K\sqrt{\frac{KT}{R}}\right)$. Additionally, if the MAB is linear the regret can be upper bounded by $O\left(\log K\sqrt{\frac{dT}{R}}\right)$.

Detailed proofs of Propositions 4.1, 4.2, and 4.3 can be found in Appendix D.

Now, we can quantify the relationship between information and regret. Consider two agents, $A$ and $B$, that play on the same online decision-making task. $A$ has an advantage over $B$, since he already played multiple rounds before. $B$ can query external information to reach the same level of performance as $A$ on the task. Using the regret upper bound in Proposition 4.3 we can get a lower bound on the information $B$ needs. Similarly, Proposition 4.1 gives an upper bound on the number of bits. Thus, Propositions 4.1 and 4.3 quantify information in terms of regret. We note that this quantification is not tight, as the upper bounds differ from the lower bounds by a factor of $\sqrt{\log K}$.

These Propositions also allow us to quantify the relationship between the rate of information accumulation and regret. If both parties play for the same number of rounds, the one that accumulates information faster will also suffer less regret.

###### Proposition 4.1 .

###### Proposition 4.2 .

###### Proposition 4.3 .

### 4.2 Entropy Constraint

While Proposition 4.1 shows how we can lower bound regret under a constraint on accumulated information, we now shift our focus to a constraint on the prior only, i.e $H(\pi^{*})\leq R$.
Russo and Van Roy [, ] showed that in this scenario, the regret of Thompson sampling and information-directed sampling (IDS) can be upper bounded using $H(\pi^{*})$.

###### Theorem 4.4 (Propositions 2 and 4 of Russo and Van Roy [ 2014 ] ) .

In the $K$-MAB setting, the regret of Thompson sampling and IDS is upper bounded as $O(\sqrt{KTH(\pi^{*})})$. Furthermore, if the rewards are a linear function of the decisions, and the decisions are vectors in $\mathbb{R}^{d}$, then the regret is upper bounded by $O\left(\sqrt{dTH(\pi^{*})}\right)$.

We next develop an entropy-dependent Bayesian regret lower-bound for algorithms that obey the following assumption.

###### Assumption 4.1 .

$D\left(p_{t},P^{\pi^{*}}\right)\geq c\bar{A}R$ for all $t$, for some constant $c>0$.

Intuitively, this assumption means that we consider only agents that gather a minimal amount of information regarding the problem. We now state the following theorem.

###### Proposition 4.5 .

For any agent for the $K$-MAB problem that satisfy Assumption 4.1, the regret is lower-bounded as $\Omega\left(\sqrt{\frac{KH(\pi^{*})T}{\log K}}\right)$. Additionally, if the MAB is linear, then the regret is lower bounded by $\Omega\left(\sqrt{\frac{dH(\pi^{*})T}{\log K}}\right)$.

The proof of Proposition 4.5 can be found in Appendix D.3. We note that this lower bound behaves like the upper bound Presented in Theorem 4.4, up to a factor of $\sqrt{\log K}$. We also show in the appendix that Assumption 4.1 holds for any algorithm that learns the optimal decision.

###### Theorem 4.4 (Propositions 2 and 4 of Russo and Van Roy [ 2014 ] ) .

###### Assumption 4.1 .

###### Proposition 4.5 .

## 5 Experiments

### 5.1 Stochastic Bayesian Bandit

We begin by demonstrating the trade-off in a simple Bayesian MAB problem. In this problem, our model space contains $K$ possible models. The decision space of the problem also contains $K$ decisions, which are called arms. The mean of all arms in every model is $0.5(1-\varepsilon)$, except for one arm for which the mean is $0.5(1+\varepsilon)$. The optimal arm is different for every model, and the reward of each arm is Bernoulli distributed. We also fix $K=8,\varepsilon=0.1$ and a uniform prior over the problems and compare three different bandit algorithms - EXP3 [Lattimore and Szepesvári, ], APS [Xu and Zeevi, ], and Thompson sampling [Thompson, ]. We also estimate the accumulated information for each algorithm. Results are presented in Figure 2. We see how algorithms that accumulate information quickly also suffer less regret. We also compare Thompson sampling under different priors $H(\pi^{*})$. The results of this experiment can be found in Figure 3. Additional experimental details are provided in Appendix E.

Figure: (a) Bayesian regret
Refer to caption: extracted/5907235/Figures/algo_bandit_regret.png

### 5.2 Question Answering with Large Language Models

In the following experiment, we show how the regret-information trade-off can be utilized in a practical setting. We consider a sequential multiple choice question-answering (MCQA) task, where every round we need to answer a question, given four possible answers. We also have access to two large language models (LLM), where one has significantly more parameters than the other. At every turn, we choose which LLM should be used to answer the question. Every round we are provided with the question, possible answers, and the output of the small LLM for the given prompt. We receive a positive reward of 1 for answering the question correctly. If we choose to deploy the large LLM we also incur a negative reward of 0.1. Our goal is to minimize the accumulated regret.

On the one hand, the larger LLM is more accurate and will output the correct answer with a higher probability. On the other hand, we do not wish to query the large LLM due to the penalty we suffer, if the small LLM already outputs the correct answer with high probability. We present the following method for selecting the LLM using bits: Use the small LLM to quantify the amount of information that can be obtained. If it is above some threshold, we opt to use the large LLM since it provides more information, which results in less regret as we have seen in Section 3. Otherwise, use the small LLM. We call this approach the bits-based policy.

Since the LLM outputs a probability distribution over tokens, we can measure the information the small LLM will gain after answering the question, in bits. We prompt the small LLM with the question and possible answers, which returns scores for each token. We take the scores corresponding only for the tokens [A, B, C, D], each corresponding to a different answer, and use them to get a distribution over these tokens. We measure the information in bits by calculating the KL divergence between this distribution and the uniform one. We compare the mean regret over a horizon of 200 steps between this policy, and one that randomly selects which LLM to use. The threshold value for the bits-based policy is selected to ensure that we query the large LLM the same number of times as the random policy.

We run the experiment described above with the following specifications. To generate the multiple-choice questions, we used the MMLU dataset, which contains multiple-choice questions in a variety of topics, such as algebra, business, etc. [Hendrycks et al., , ].

**Table 2: Mean regret for both policies for a horizon of 200 episodes, under different deployment percentages of the large LLM. The left column denotes the percentage of queries to the large LLM. For all tables, we used Mixtral-8x7B as the large LLM. For the small LLM, we used Mistral-7B (top table) and Gemma-2B (bottom table). Comparison with other LLMs is provided in Appendix F.**
|  | % Deployment | Bits-based | Random |
| --- | --- | --- | --- |
| Mistral 7B | $50\%$ | $\mathbf{36\pm 1}$ | $38.7\pm 0.3$ |
| $70\%$ | $\mathbf{26.6\pm 0.8}$ | $30.5\pm 0.4$ |  |
| $90\%$ | $\mathbf{21.8\pm 0.4}$ | $22.4\pm 0.5$ |  |
| Gemma 2B | $50\%$ | $\mathbf{38\pm 2}$ | $44.5\pm 0.7$ |
| $70\%$ | $\mathbf{32\pm 1}$ | $35.6\pm 0.8$ |  |
| $90\%$ | $\mathbf{26\pm 1}$ | $27\pm 1$ |  |

We used 10 different seeds to generate 10 sets of 200 questions from MMLU randomly. For the small LLM we either used Mistral 7B Jiang et al. [], Falcon 7B [Almazrouei et al., ], or Gemma 2B [Team et al., ]. We used Mixtral 7Bx8 [Jiang et al., ], Llama3-70B [AI@Meta, ], or Gemma 7B for the large LLM. We applied 4-bit quantization [Dettmers and Zettlemoyer, ] for all models and flash attention [Dao et al., ] for all models excluding Falcon 7B.
Table 2 describes the mean regret of every policy under a different number of large LLM deployments. Tables 4 and 5 provide additional results for different combinations of small and large LLMs.

From the results, we see that deciding whether to query the large LLM or not using bits is better than random selection. Furthermore, this improvement becomes more significant as we increase the number of deployments allowed. This demonstrates how we can easily utilize the quantification of information to improve performance in online tasks. Additional details and results for other models are provided in Appendix F. Code is available here(^1^11[https://github.com/itaishufaro/bitsandbandits](https://github.com/itaishufaro/bitsandbandits)).

## 6 Related Work

##### Bayesian setting.

In the Bayesian setting, prior information is assumed to be expressed as a probability distribution, called the prior. New information is then incorporated using Bayesian inference to update the prior probability, resulting in a posterior distribution. Bayesian algorithms have been extensively studied in multiple online decision-making problems such as multi-armed bandits [Russo and Van Roy, , Kaufmann et al., ] and reinforcement learning [Guez et al., , Ghavamzadeh et al., ]. Upper bounds for Bayesian algorithms have been proved for both the frequentist [Kaufmann et al., ] and Bayesian settings [Russo and Van Roy, , ]. Prior dependent regret bounds for Bayesian algorithms have also been studied [Bubeck and Liu, , Russo and Van Roy, ]. Previous studies have explored prior-dependent lower bounds for Bayesian regret, but these are limited to specific forms of priors, such as Gaussian priors [Atsidakou et al., ].

##### Contextual information.

In the contextual setting, information is revealed to the agent before every round, which can be leveraged to minimize regret. This framework has gathered attention within both the bandit [Bietti et al., ] and reinforcement learning frameworks [Klink et al., , Modi and Tewari, ]. The contexts can be selected arbitrarily by an adversary [Beygelzimer et al., , Chu et al., ] or generated from some prior probability distribution, similarly to the Bayesian setting [Hao et al., , May et al., ]. Bayesian algorithms have also been adapted to the arbitrary context setting [Agrawal and Goyal, ]. Furthermore, the type of information provided to the learner can expand beyond the contextual information provided directly [Schneider and Zimmert, ]. Our work introduces a contextual Bayesian setting framework that covers a wide variety of interactive decision-making tasks.

##### Information-theoretic methods

have been employed to derive upper bounds for various online tasks. Russo and Van Roy [] introduced an information-theoretic method for establishing Bayesian regret upper bound for Thompson sampling in the multi-armed bandit setting, which depends on the entropy of the prior. This approach was also used to design new Bayesian algorithms that utilize mutual information called information-directed sampling (IDS) [Russo and Van Roy, ]. IDS and the information-theoretic method it utilizes were also extended to other tasks such as contextual bandits [Neu et al., ], sparse linear bandits [Hao et al., ], non-stationary bandits [Min and Russo, , Liu et al., ], reinforcement learning [Lu and Van Roy, ], non-linear control [Kakade et al., ], partial monitoring [Lattimore and Szepesvári, ], and other online optimization problems [Liu et al., , Dong et al., , Lattimore and Gyorgy, , Russo and Van Roy, ]. The bounds presented in works such as [Russo and Van Roy, , , Neu et al., ] are based on the upper bounding of the information ratio. Our work uses a different approach, which obtains nearly matching prior-dependent lower bounds for Thompson sampling and information-directed sampling (IDS). Furthermore, these bounds can be applied beyond the bandit setting. Seldin et al. [] utilized PAC-Bayes bounds to obtain information-theoretic upper bounds on the per-round regret, that depend on mutual information. Arumugam and Van Roy [, ] have explored a different information-theoretic method, utilizing rate-distortion theory to minimize regret.

## 7 Conclusions and Future Work

We introduce a general setting that embeds contextual information in a Bayesian setting. This setting covers a wide variety of online decision-making tasks. Using information-theoretic tools, we demonstrated a general method for obtaining regret lower bounds for problems in this setting. We used this method to present regret lower bound which depends on the information accumulated by the agent. We also presented regret upper bounds for Thompson sampling which depends on the accumulated information. These results quantify the relationship between a-priori external information and regret in online settings and the relationship between online information accumulation and regret. We then utilized this trade-off in a multiple-choice question-answering task with LLMs, demonstrating that the aforementioned quantification can be easily used in an online setting.

##### Limitations.

A central assumption in our analysis is that exogenous information can be gathered regardless of the process history. However, this assumption may be violated in a general sequential decision process where the action itself may have ramifications on the quality, quantity, and cost of the exogenous information. Our work only covers the Bayesian setting, and our definition of the measure of information relies on it. In other settings, such as adversarial learning [Neu and Olkhovskaya, ] or frequentist settings, a different measure of information is required. Another limitation is the difference in $\sqrt{\log K}$ between the lower and upper bounds presented in this work. Making these bounds tighter can be the topic of future work.

Finally, and importantly, with the increasing prevalence of LLMs, and foundation models in general, building solid foundations as well as practical algorithms for using prior knowledge in sequential decision-making is an important research endeavor that may be built upon the foundations that are laid in this paper.

## Acknowledgements

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034255.

## Appendix A Table of Notations

**Table 3: Commonly used notations throughout the paper and the appendix.**
| Notations | Description |
| --- | --- |
| $\Pi$ | The decision space. |
| $\mathcal{M}$ | The model class. |
| $\mathcal{O}$ | The observation space. |
| $\mathcal{C}$ | The context space. |
| $\pi$ | A decision. |
| $R_{M}(\pi,C)$ | reward distribution according to decision $\pi$ on model $M$. |
| $\mu_{M}(\pi,C)$ | mean reward according to decision $\pi$ on model $M$. |
| $P$ | Prior probability of the task. |
| $\pi^{*}_{M}$ | The optimal decision for a model $M$. |
| $\mathcal{H}_{t}$ | The total accumulated history up to round $t$ |
|  | (including observations and contexts). |
| $p_{t}$ | Policy selected at round $t$. |
| $r_{t}$ | Reward sampled at time $t$. |
| $\rho$ | A norm that lower bounds the difference in reward means. |
| $\mathcal{BR}_{P}(T)$ | The Bayesian regret given prior $P$. |
| $\mathcal{BR}^{*}(T)$ | The worst-case Bayesian regret. |
| $\mathcal{N}(d,\epsilon,H)$ | $\epsilon$-covering number of $H$ concerning metric $d$. |
| $\mathcal{M}(d,\epsilon,H)$ | $\epsilon$-packing number of $H$ concerning metric $d$. |
| $\mathcal{M}^{\mathrm{loc}}(d,\epsilon,H)$ | $\epsilon$-local packing number of $H$ concerning metric $d$. |
| $\mathrm{Vol}(\cdot)$ | Volume of a set. |

## Appendix B Useful Properties of Covering Numbers

###### Definition B.1 (Covering and packing numbers [Wainwright, 2019 ] ) .

Let $H$ be a normed space, and let $d(\cdot,\cdot)$ be the metric induced by the norm. Let $\epsilon>0$.

- •
A set $C\subset H$ is said to be an $\epsilon$-covering set of $H$ if for all $h\in H$ there is $c\in C$ such that $d(h,c)\leq\epsilon$.
- •
The covering number is defined as
$\mathcal{M}(d,\epsilon,H)=\min\left\{m:\exists C,\left|C\right|=m\text{ and $C
$ is an $\epsilon$-covering set of $H$}\right\}.$
If $d(x,y)=\left\|x-y\right\|_{p}$, we denote it by $\mathcal{M}_{p}(\epsilon,H)$.
- •
A set $C\subset H$ is said to be a packing set of $H$ if for all $c_{1},c_{2}\in C$ we have that $d(c_{1},c_{2})\geq\epsilon$.
- •
The packing number is defined as
$\mathcal{N}(d,\epsilon,H)=\max\left\{m:\exists C,\left|C\right|=m\text{ and $C
$ is an $\epsilon$-packing set of $H$}\right\}.$
If $d(x,y)=\left\|x-y\right\|_{p}$, we denote it by $\mathcal{N}_{p}(\epsilon,H)$.
- •
We now define $B(\theta,\epsilon)=\{\theta^{\prime}\in H:d(\theta^{\prime},\theta)\leq\varepsilon\}$. $C\subseteq B$ is an $\epsilon$-local packing set of $B(\theta,\epsilon)$ if for all $c_{1},c_{2}\in C$, $d(c_{1},c_{2})\geq\frac{\epsilon}{2}$.
- •
The local packing number is defined as
$\mathcal{M}^{\mathrm{loc}}(d,\epsilon,H)=\max\left\{m:\exists B(\theta,
\varepsilon),\text{such that $C$ is an }\epsilon-\text{local packing of $B$
and }\left|C\right|=m\right\}.$

###### Lemma B.1 .

The following properties hold:

- •
(Theorem 14.2 of Wu []) For any subset of dimension $d$ that is contained in $\mathbb{B}_{p}^{d}$ the covering number $\mathcal{N}_{p}(\epsilon)$ obeys $d\log\left(\frac{2}{\epsilon}\right)\leq\log\mathcal{N}_{p}(\epsilon)\leq d
\log\left(\frac{3}{\epsilon}\right)$. This includes the probability simplex with $d$ variables and $\mathbb{B}_{d}^{2}$.
- •
(Theorem 14.1 of Wu []) Under the same norms, for the same set,
$\mathcal{M}(2\epsilon)\leq\mathcal{N}(\epsilon)\leq\mathcal{M}(\epsilon)$

Throughout the appendix, $\mathrm{Vol}(A)$ denotes the volume of set $A$.

###### Definition B.1 (Covering and packing numbers [Wainwright, 2019 ] ) .

###### Lemma B.1 .

## Appendix C Proofs for Section 3

### C.1 Proof of Proposition 3.2

###### Proof.

We write

$$ $\displaystyle\mathcal{BR}^{*}(T)$ $\displaystyle=\sup_{\nu}\inf_{p_{1},\dots,p_{T}}\mathbb{E}_{M\sim\nu}\left[ \sum_{t=1}^{T}(\mu_{M}(\pi^{*},C_{t})-\mu_{M}(p_{t},C_{t}))\right]$ $\displaystyle\geq\sup_{\nu}\inf_{p_{1},\dots,p_{T}}\frac{\epsilon T}{2}\mathbb {P}_{\nu}\left(\sum_{t=1}^{T}(\mu_{M}(\pi^{*},C_{t})-\mu_{M}(p_{t},C_{t}))\geq \frac{\epsilon T}{2}\right)$ $\displaystyle\geq\frac{\epsilon T}{2}\sup_{\nu}\inf_{p_{1},\dots,p_{T}}\mathbb {P}_{\nu}\left(\forall t:\mu_{M}(\pi^{*},C_{t})-\mu_{M}(p_{t},C_{t})\geq\frac{ \epsilon}{2}\right)$ $\displaystyle\geq\frac{\epsilon T}{2}\max_{k\in\{1,\dots,K\}}\inf_{p_{1},\dots ,p_{T}}\mathbb{P}\left(\forall t:\left|\mu_{M}(\phi_{k},C_{t})-\mu_{M}(p_{t},C _{t})\right|\geq\frac{\epsilon}{2}\right)$ $\displaystyle\geq\frac{\epsilon T}{2}\max_{k\in\{1,\dots,K\}}\inf_{p_{1},\dots ,p_{T}}\mathbb{P}\left(\forall t:\rho(\phi_{k},\pi_{t})\geq\frac{\epsilon}{2}\right)$ $\displaystyle\geq\frac{\epsilon T}{2}\max_{k}\inf_{t}\mathbb{P}(p_{t}\neq\phi_ {k})$ $\displaystyle\geq\frac{\epsilon T}{2}\left(1-\frac{I(V;\mathcal{H}_{T})+1}{ \log K}\right).$ $$

The first inequality follows from Markov’s inequality, the second inequality from a union bound, and the last inequality from Fano’s inequality (Theorem 3.1).
∎

###### Proof.

### C.2 Proof of Theorem 3.4

###### Proof.

We provide proof for three different scenarios.

- •
First scenario, finite $\Pi$. For this scenario, we choose $\Phi$ to be a local packing set of the decisions simplex $\Delta(\Pi)$, so $K=\mathcal{M}^{\mathrm{loc}}(\rho,\Delta(\Pi),\epsilon)$. Applying this selection of set, and using Equation 4 we have that
$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq\frac{1}{2}\left[1-
\frac{1+I(V;\mathcal{H}_{T})}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Delta(\Pi),
\epsilon)}\right].$
(12)
Applying Theorem 3.3 we have that $I(V;\mathcal{H}_{T})\leq 2\bar{A}\epsilon^{2}T$. Substituting this back into Equation 12,
$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq\frac{1}{2}\left[1-
\frac{1+2\bar{A}\epsilon^{2}T}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Delta(\Pi)
,\epsilon)}\right].$
- •
Second scenario, infinite-parametric $\Pi$. For this scenario, we choose $\Phi$ to be a local packing set of the decision space $\Pi$, so $K=\mathcal{M}^{\mathrm{loc}}(\rho,\Pi,\epsilon)$. Applying this selection of set, and using Equation 4 we have that
$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq\frac{1}{2}\left[1-
\frac{1+I(V;\mathcal{H}_{T})}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Pi,\epsilon
)}\right].$
(13)
Applying Theorem 3.3 we have that $I(V;\mathcal{H}_{T})\leq 2\bar{A}\epsilon^{2}T$. Substituting this back into Equation 13,
$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq\frac{1}{2}\left[1-
\frac{1+2\bar{A}\epsilon^{2}T}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Pi,
\epsilon)}\right].$
- •
Third scenario, non-parametric $\Pi$. For this scenario, we choose $\Phi$ to be a global packing set of the decision space $\Pi$, so $K=\mathcal{M}(\rho,\Pi,\epsilon)$. Applying this selection of set, and using Equation 4 we have that
$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq\frac{1}{2}\left[1-
\frac{1+I(V;\mathcal{H}_{T})}{\log\mathcal{M}(\rho,\Pi,\epsilon)}\right].$
(14)
Applying Theorem 3.3 we have that $I(V;\mathcal{H}_{T})\leq\inf_{\delta>0}\left(\log\mathcal{N}\left(\rho,\Pi,
\sqrt{\delta}\right)+T\delta\right)$. Substituting this back into Equation 14,
$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq\frac{1}{2}\left[1-
\frac{1+\inf_{\delta>0}\left(\log\mathcal{N}\left(\rho,\Pi,\sqrt{\delta}\right
)+T\delta\right)}{\log\mathcal{M}(\rho,\Pi,\epsilon)}\right].$

∎

###### Proof.

### C.3 Proofs for Additional Lower Bounds

###### Proposition C.1 .

For any algorithm, there exists a Bayesian decision-making task with a finite decision set and a single context ($\left|\mathcal{C}=1\right|$) such that the regret can be lower bounded by $\Omega(\sqrt{\left|\Pi\right|T})$.

###### Proof.

We focus on the set $\Delta(\Pi)$ and note that it is a parametric set.
We also see that for all policies $\phi,\psi\in\Delta(\Pi)$ we have that

$$ $\mathbb{E}[\left|\mu_{M}(\phi,C)-\mu_{M}(\psi,C)\right|]=c\left\|\phi-\psi \right\|_{1}.$ $$

for some positive constant $c$.
Hence, in this scenario, we can take $\rho(x,y)=c\left\|x-y\right\|_{1}$. It is convenient to denote $K=\left|\Pi\right|$. Thus, using a scaling argument,

$$ $\displaystyle\log\mathcal{M}^{\mathrm{loc}}(\rho,\Delta(\Pi),\epsilon)$ $\displaystyle=\log\mathcal{M}^{\mathrm{loc}}_{1}(\Delta(\Pi),\epsilon/c).$ $$

From the definition of a local packing number, we have that

$$ $\displaystyle\log\mathcal{M}^{\mathrm{loc}}_{1}(\Delta(\Pi),\epsilon/c)$ $\displaystyle\geq\log\left(\frac{\mathrm{Vol}(\mathbb{B}_{1}^{K-1}(\epsilon))} {\mathrm{Vol}(\mathbb{B}_{1}^{K-1}(\epsilon/2))}\right)$ $\displaystyle\geq(K-1)\log\frac{2\epsilon}{\epsilon}$ $\displaystyle=K-1.$ $$

Substituting this into Equation 7 we obtain that

$$ $\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq\frac{1}{2}\left[1-\frac{1+2\bar{A} \epsilon^{2}T}{K-1}\right].$ $$

Now, we select $\epsilon$ to maximize such that our lower bound will be the tightest. In particular, we choose $\epsilon=\sqrt{\frac{K-1}{6T\bar{A}}}$ which yields the following lower bound,

$$ $\displaystyle\mathcal{BR}^{*}(T)$ $\displaystyle\geq\frac{1}{2}\sqrt{\frac{T(K-1)}{6\bar{A}}}\left[\frac{2}{3}- \frac{1}{K-1}\right].$ $$

This concludes our proof.
∎

The results for multi-armed bandits and tabular MDPs are shown by substituting $\left|\Pi\right|=K$ and $HSK$ respectively.

###### Proposition C.2 .

For any algorithm, there exists a Bayesian decision-making task with $\Pi\subseteq\mathbb{B}_{2}^{d}$, where the reward means are a linear function of the decisions, such that the regret can be lower bounded by $\Omega(\sqrt{dT})$.

###### Proof.

Similarly to Proposition C.1, we have $\rho(x,y)=c\left\|x-y\right\|_{1}$ for some positive constant $c>0$. We focus on the set $\mathbb{B}_{2}^{d}$ and note that it is a parametric set. Furthermore, using Lemma B.1 we have that

$$ $\log\mathcal{M}^{\mathrm{loc}}(\rho,\mathbb{B}_{2}^{d},\epsilon)\geq d.$ $$

Substituting this into Equation 8 we obtain that

$$ $\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq\frac{1}{2}\left[1-\frac{1+2\bar{A} \epsilon^{2}T}{d}\right].$ $$

Now, we select $\epsilon$ to maximize such that our lower bound will be the tightest. In particular, we choose $\epsilon=\sqrt{\frac{d}{6T\bar{A}}}$ which yields the following lower bound,

$$ $\displaystyle\mathcal{BR}^{*}(T)$ $\displaystyle\geq\frac{1}{2}\sqrt{\frac{Td}{6\bar{A}}}\left[\frac{2}{3}-\frac{ 1}{d}\right].$ $$

This concludes our proof.
∎

In the Lipshitz bandit setting, $\Pi$ is some metric space with metric $\rho$ and $\mathcal{M}=\mathcal{M}_{\mathcal{F}}$, where

$$ $\mathcal{F}=\{f:\Pi\to[0,1]|f\text{ is $1$-Lipschitz w.r.t }\rho\}.$ $$

Unlike the previous settings, we note that the decision set is not parametric this time. We now prove a lower bound for this setting.

###### Proposition C.3 .

The regret lower bound for the Lipschitz bandit is $\Omega\left(T^{\frac{d+1}{d+2}}\right)$, where $d$ is chosen such that

$$ $\displaystyle c_{1}\leq\log\mathcal{N}(\rho,\epsilon,\Pi)\cdot\epsilon^{d}\leq c _{2}$ $$

###### Proof.

From the assumption, the covering and packing number can now be bounded by

$$ $\displaystyle\log\mathcal{N}\left(\rho,\sqrt{\frac{2}{\delta}},\Pi\right)$ $\displaystyle\leq c_{2}\left(\frac{2}{\delta}\right)^{d/2}$ $\displaystyle\log\mathcal{M}(\rho,\epsilon,\Pi)$ $\displaystyle\geq c_{1}{\epsilon}^{-d}.$ $$

Substituting this into Equation 9,

$$ $\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}$ $\displaystyle\geq\frac{1}{2}\left[1-\left({1+c_{2}\left(\frac{2}{\delta}\right )^{d/2}+T\delta}\right)\frac{\epsilon^{d}}{c_{1}}\right].$ $$

We choose $\delta=T^{\frac{2}{d+2}}c_{2}^{-\frac{2}{d+2}}2^{-\frac{d}{d+2}}$. This yields that

$$ $\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq\frac{1}{2}\left[1-\left(1+2(2c_{2}) ^{-\frac{d}{d+2}}T^{\frac{d}{d+2}}\right)\frac{\epsilon^{d}}{c_{1}}\right].$ $$

Selecting $\epsilon^{d}=\frac{1}{2}\left[\frac{c_{1}}{\left(1+(2c_{2})^{-\frac{d}{d+2}}T^
{\frac{d}{d+2}}\right)}\right]$ yields

$$ $\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}$ $\displaystyle\geq\frac{1}{4}$ $$

Now, $\epsilon T\gtrsim T^{\frac{d+1}{d+2}}$ so we have that

$$ $\displaystyle\mathcal{BR}^{*}(T)\gtrsim T^{\frac{d+1}{d+2}}.$ $$

∎

We now present the following theorem, which shows that the worst-case Bayesian regret is equal to the mini-max frequentist regret.

###### Theorem C.4 (Theorem 1 of Lattimore and Szepesvári [ 2019 ] ) .

$$ $\inf_{\{\pi_{i}\}_{i=1}^{T}}\sup_{r_{1},\dots,r_{t}}\max_{\pi^{*}\in\Pi} \mathbb{E}\left[\sum_{t=1}^{T}\left(r_{t}(\pi^{*})-r_{t}(\pi_{t})\right)\right ]=\sup_{\nu}\inf_{\{\pi_{i}\}_{i=1}^{T}}\max_{\pi^{*}\in\Pi}\mathbb{E}\left[ \sum_{t=1}^{T}\left(r_{t}(\pi^{*})-r_{t}(\pi_{t})\right)\right]$ $$

This theorem then states that, without any constraints on the prior, the worst-case Bayesian regret is equal to the mini-max regret. This means that any lower bound derived for the Bayesian regret can also be applied to the frequentist one.

###### Proposition C.1 .

###### Proof.

###### Proposition C.2 .

###### Proof.

###### Proposition C.3 .

###### Proof.

###### Theorem C.4 (Theorem 1 of Lattimore and Szepesvári [ 2019 ] ) .

### C.4 Additional Explanation

We now provide an additional explanation regarding Proposition 3.4. In particular, we explain why we had to select a local packing set for parametric decision spaces $\Pi$ and why we focused on the simplex of the decision set for finite decision spaces.

##### Selecting Δ ⁢ ( Π ) Δ Π \Delta(\Pi) roman_Δ ( roman_Π ) over Π Π \Pi roman_Π .

This explanation is rather straightforward. We see that by selecting $\Pi$ we have that $\mathcal{M}^{\mathrm{loc}}(\rho,\Pi,\epsilon)=1$ for any value of $\epsilon$ which makes the lower bound null.

##### Selecting a local-packing set for parametric Π Π \Pi roman_Π .

This decision stems from the improved upper bound of $I(V;\mathcal{H}_{T})$ for parametric decision space, which is found in Theorem 3.3. Using the other upper bound for $I(V;\mathcal{H}_{T})$ simply results in a sub-optimal lower bound. Additional details can be found in Yang and Barron [].

## Appendix D Proofs for Section 4

We begin by stating and proving the following Lemma.

###### Lemma D.1 .

Under the assumptions and notations of Proposition 3.2, the constraint of $I(\pi^{*};\mathcal{H}_{T})\leq R\leq\log K$, and the regularity Assumption 3.1,
the following holds.

$$ $I(V;\mathcal{H}_{T})\leq 2\bar{A}T\frac{R}{\log K}\epsilon^{2}.$ $$

###### Proof.

The proof follows a similar analysis to the proof of Theorem 3.3, which is provided in Yang and Barron []. Since we focus on a parametric set, we consider a local packing set with a cardinality of $\mathcal{M}^{\mathrm{loc}}(\rho,\epsilon,\Delta(\Pi))$, which we denote by $E$. $\tilde{E}$ is the set contained by $E$ under the mutual information constraint,

$$ $\tilde{E}=\{p\in E:I(\pi^{*};\mathcal{H}_{T})\leq R\}.$ $$

We now have

$$ $\displaystyle I(V;\mathcal{H}_{T})$ $\displaystyle=\sum_{t=1}^{T}I(V;C_{t+1},O_{t+1},\dots,C_{T},O_{T}\mid\mathcal{ H}_{t})$ $\displaystyle=\sum_{t=1}^{T}D\left(P^{V\mid\mathcal{H}_{T}},P^{V\mid\mathcal{H }_{t}}\right)$ $\displaystyle\leq T\max_{P_{1},P_{2}\in\tilde{E}}D\left(P_{1},P_{2}\right)$ $\displaystyle\leq T\frac{R}{\log K}\max_{P_{1},P_{2}\in E}D\left(P_{1},P_{2}\right)$ $\displaystyle\leq T\frac{R}{\log K}\bar{A}\max_{P_{1},P_{2}\in E}\rho(P_{1},P_ {2})^{2}$ $\displaystyle\leq T\frac{R}{\log K}\bar{A}\epsilon^{2}.$ $$

where the second inequality follows from a scaling argument, and the last follows from the fact that $E$ is a local packing set.
∎

As a corollary from Lemma D.1, we obtain the following.

###### Corollary D.2 (Proposition 4.2 ) .

Let there be a Bayesian interactive decision-making problem as defined in Section 2, with a finite decision space $\Pi$, where $\left|\Pi\right|=K$. Then,

$$ $\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\geq\frac{1}{2}\left[1-\frac{2\bar{A} \epsilon^{2}T\frac{R}{\log K}+1}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Delta( \Pi),\epsilon)}\right]$ $$

Furthermore, if the decision-making problem is a part of a parametric set, then

$$ $\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\geq\frac{1}{2}\left[1-\frac{2\bar{A} \epsilon^{2}T\frac{R}{\log K}+1}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Pi, \epsilon)}\right]$ $$

###### Proof.

The proof follows immediately by utilizing Lemma D.1 and using the fact that in this scenario, $\rho(x,y)=\left\|x-y\right\|_{1}$, similarly to the proof of Proposition C.1.
∎

###### Lemma D.1 .

###### Proof.

###### Corollary D.2 (Proposition 4.2 ) .

###### Proof.

### D.1 Proof of Proposition 4.1

###### Proof.

We start by considering $R=0$. From Lemma 4.2,

$$ $\mathcal{BR}^{*}(T)\geq\frac{\epsilon T}{2}\left(1-\frac{1}{K}\right)$ $$

for any $\epsilon>0$ such that lower bounds the difference between two different decisions. Since the maximal difference between two decisions is $1$, we set $\epsilon=1$ and obtain the linear lower bound,

$$ $\mathcal{BR}^{*}(T)\geq\frac{T}{2}\left(1-\frac{1}{K}\right).$ $$

We now consider $R>0$. We denote the polytope space with the mutual information constraint by $\Delta_{R}$. Similarly to the proof of Proposition C.1,

$$ $\log\mathcal{M}^{\mathrm{loc}}(\rho,\Delta(\Pi),\epsilon)\geq(K-1).$ $$

Substituting this into Equation 10,

$$ $\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\geq\frac{1}{2}\left[1-\frac{2T\bar{A} \frac{R}{\log K}\epsilon^{2}+1}{(K-1)}\right].$ $$

Selecting $\epsilon=\sqrt{\frac{(K-1)\log K}{6RT\bar{A}}}$ we now have that

$$ $\displaystyle\mathcal{BR}^{*}(T)$ $\displaystyle\geq\frac{1}{2}\sqrt{\frac{TK\log K}{6R\bar{A}}}\left(\frac{2}{3} -\frac{1}{K-1}\right)$ $$

We present the proof for the linear case. Now,

$$ $\log\mathcal{M}^{\mathrm{loc}}(\rho,\Pi,\epsilon)\geq d.$ $$

So now we have

$$ $\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\geq\frac{1}{2}\left[1-\frac{2T\frac{R}{ \log K}\bar{A}\epsilon^{2}+1}{d}\right].$ $$

Selecting $\epsilon=\sqrt{\frac{d\log K}{6R\bar{A}T}}$ we now have that

$$ $\displaystyle\mathcal{BR}^{*}(T)$ $\displaystyle\geq\frac{1}{2}\sqrt{\frac{Td\log K}{6R\bar{A}}}\left(\frac{2}{3} -\frac{1}{d}\right)$ $$

∎

Proposition 4.1 can then be applied directly on the MAB setting.

###### Corollary D.3 .

Consider a Bayesian MAB with $K$ arms. If $I(\pi^{*};\mathcal{H}_{T})=0$ then the worst-case regret is linear. Otherwise, for $I(\pi^{*};\mathcal{H}_{T})\geq 0$, the worst-case regret can be lower-bounded by $\Omega\left(\sqrt{\frac{TK\log K}{I(\pi^{*};\mathcal{H}_{T})}}\right)$. Additionally, if $\Pi=\mathbb{B}_{2}^{d}$ and the reward means are linear functions of the decisions, we have a lower bound of $\Omega\left(\sqrt{\frac{Td\log K}{I(\pi^{*};\mathcal{H}_{T})}}\right)$.

###### Proof.

###### Corollary D.3 .

### D.2 Proof of Proposition 4.3

###### Proof.

We consider the following two algorithms. The first is Thompson sampling, whose policy at round $t$ is the posterior probability, $p_{t}=P^{\pi^{*}\mid\mathcal{H_{t}}}$. The second algorithm is Thompson sampling with the constrained observations $\tilde{O}_{t}$ such that $I(\pi^{*};\tilde{\mathcal{H}}_{T})=D\left(P^{\pi^{*}\mid\tilde{\mathcal{H}}_{T
}},P^{\pi^{*}}\right)=R$, where $\tilde{\mathcal{H}}_{t}$ is the history with constrained observations. Now, we define the information ratio for both the normal and constrained variants of Thompson sampling:

$$ $\rho_{t}=\frac{\mathbb{E}[r_{M}(\pi^{*}(C_{t}),C_{t})-r_{M}(p_{t},C_{t})]^{2}} {I(\pi^{*};O_{t+1}\mid\mathcal{H}_{t})}\quad;\quad\tilde{\rho}_{t}=\frac{ \mathbb{E}[r_{M}(\pi^{*}(C_{t}),C_{t})-r_{M}(p_{t},C_{t})]^{2}}{I(\pi^{*}; \tilde{O}_{t+1}\mid\tilde{\mathcal{H}_{t}})}.$ $$

We see that

$$ $\displaystyle\frac{\rho_{t}}{\tilde{\rho}_{t}}$ $\displaystyle=\frac{I(\pi^{*};\tilde{O}_{t+1}\mid\tilde{\mathcal{H}_{t}})}{I( \pi^{*};O_{t+1}\mid\mathcal{H}_{t})}$ $\displaystyle\geq\frac{I(\pi^{*};\tilde{O}_{t+1}\mid\tilde{\mathcal{H}_{t}})}{ \log K}$ $$

where the inequality follows from $I(\pi^{*};O_{t+1}\mid\mathcal{H}_{t})\leq\log K$.
Thus,

$$ $\displaystyle\max_{P}\max_{t}\tilde{\rho}_{t}$ $\displaystyle\leq\max_{P}\max_{t}\frac{\log K}{D\left(P^{\pi^{*}\mid(\tilde{O_ {t}},\tilde{\mathcal{H}}_{t})},P^{\pi^{*}\mid\tilde{\mathcal{H}}_{t}}\right)} \rho_{t}$ $\displaystyle\leq\frac{\log K}{R}\max_{t}\rho_{t}$ $\displaystyle\leq\frac{K\log K}{2R}$ $$

Where the third inequality follows by the information ratio upper bound presented by Russo and Van Roy [].
If the MAB is linear then the information ratio $\rho_{t}$ can be upper-bounded by $\frac{d}{2}$. Then, we have the following upper bound,

$$ $\max_{P}\max_{t}\tilde{\rho}_{t}\leq\frac{d\log K}{2R}$ $$

Now, by the analysis done by Russo and Van Roy [], we know that if $\max_{t}\tilde{\rho}_{t}\leq\tilde{\rho}$ for all $t$, then the Bayesian regret can be upper bounded by

$$ $\displaystyle\mathcal{BR}^{*}(T)$ $\displaystyle\leq\sqrt{\tilde{\rho}T\log K}$ $$

Thus, we have for $K$-MAB:

$$ $\mathcal{BR}^{*}(T)\leq\log K\sqrt{\frac{KT}{2R}}.$ $$

And for linear bandits:

$$ $\mathcal{BR}^{*}(T)\leq\log K\sqrt{\frac{dT}{2R}}.$ $$

∎

###### Proof.

### D.3 Proof of Proposition 4.5

We begin by stating and proving the following Lemma.

###### Lemma D.4 .

Let $P_{1},P_{2}$ be two priors such that $H(P_{1}^{\pi^{*}})=R\leq\log K$. Also let $\psi,\phi$ be two decisions such that $D\left(\psi,P_{1}^{\pi^{*}}\right)\geq c\bar{A}R$ and $D\left(\phi,P_{2}^{\pi^{*}}\right)\leq\log K$. Then,

$$ $\displaystyle\frac{\mathbb{E}_{P_{1}}[\mu_{M}(\pi^{*},C)-\mu_{M}(\psi,C)]}{ \mathbb{E}_{P_{2}}[\mu_{M}(\pi^{*},C)-\mu_{M}(\phi,C)]}\geq 2\sqrt{c\frac{R}{ \log K}}$ $$

###### Proof.

By the regularity assumption, we know that

$$ $\displaystyle(\mathbb{E}_{P_{1}}[\mu_{M}(\pi^{*},C)-\mu_{M}(\psi,C)])^{2}\geq \frac{cR}{2}.$ $$

From Pinsker’s inequality,

$$ $\displaystyle(\mathbb{E}_{P_{2}}[\mu_{M}(\pi^{*},C)-\mu_{M}(\phi,C)])^{2}\leq 2 D\left(\phi,P_{2}^{\pi^{*}}\right)\leq\log K.$ $$

Dividing these two inequalities yields

$$ $\displaystyle\frac{(\mathbb{E}_{P_{1}}[\mu_{M}(\pi^{*},C)-\mu_{M}(\psi,C)])^{2 }}{(\mathbb{E}_{P_{2}}[\mu_{M}(\pi^{*},C)-\mu_{M}(\phi,C)])^{2}}\geq 4c\frac{R }{\log K}$ $$

which concludes our proof.
∎

Now, we prove the following Proposition.

###### Proposition D.5 .

Let $P$ be a prior $P$ with $H(\pi^{*})=R\leq\log K$. If Assumption 4.1 holds, then

$$ $\mathcal{BR}_{P}(T;\{p_{t}\})\geq 2\sqrt{\frac{cR}{\log K}}\mathcal{BR}^{*}(T).$ (15) $$

###### Proof.

We see that

$$ $\displaystyle\mathcal{BR}_{P}(T;{p_{t}})$ $\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{P}[\mu_{M}(\pi^{*},C_{t})-\mu_{M}(p_{t },C_{t})]$ $\displaystyle\geq 2\sqrt{c\frac{R}{\log K}}\sum_{t=1}^{T}\mathbb{E}_{\nu}[\mu_ {M}(\pi^{*},C_{t})-\mu_{M}(p_{t}^{\prime},C_{t})]$ $$

for any prior $\nu$ and policies $p^{\prime}_{t}$ such that $D\left(p^{\prime}_{t},\nu^{\pi^{*}}\right)\leq\log K$. So we can take the worst-case regret,

$$ $\displaystyle\mathcal{BR}_{P}(T;{p_{t}})$ $\displaystyle\geq 2\sqrt{c\frac{R}{\log K}}\max_{\nu}\inf_{\{p^{\prime}_{t}\}: D\left(p^{\prime}_{t},\nu^{\pi^{*}}\right)\leq\log K}\sum_{t=1}^{T}\mathbb{E}_ {\nu}[\mu_{M}(\pi^{*},C_{t})-\mu_{M}(p_{t}^{\prime},C_{t})]$ $\displaystyle\geq 2\sqrt{c\frac{R}{\log K}}\max_{\nu}\inf_{\{p^{\prime}_{t}\}} \sum_{t=1}^{T}\mathbb{E}_{\nu}[\mu_{M}(\pi^{*},C_{t})-\mu_{M}(p_{t}^{\prime},C _{t})]$ $\displaystyle=2\sqrt{c\frac{R}{\log K}}\mathcal{BR}^{*}(T)$ $$

where the second inequality follows by removing a constraint on the available policies.
∎

This results in the following Corollary.

###### Corollary D.6 (Proposition 4.5 ) .

Let there be a $K$-MAB. Then for any algorithm such that $D\left(p_{t},P^{\pi^{*}}\right)\geq c\bar{A}H(\pi^{*})$, the regret can be lower-bounded by $\Omega\left(\sqrt{\frac{KH(\pi^{*})T}{\log K}}\right)$. Additionally, if the MAB is linear, then the regret can be lower bounded by $\Omega\left(\sqrt{\frac{dH(\pi^{*})T}{\log K}}\right)$.

We now explain why in scenarios where the optimal decision is unique, an algorithm that selects the optimal arm with high probability obeys Assumption 4.1.

###### Proposition D.7 .

Let there be an algorithm such that $p_{t}$ selects the optimal decision $\pi^{*}$ with probability $1-\delta$. Then,

$$ $D\left(p_{t},P^{\pi^{*}}\right)\geq(1-\delta)H(\pi^{*})-c_{\delta}$ $$

where $c_{\delta}\to 0$ as $\delta\to 0$.

###### Proof.

We can write that

$$ $\displaystyle D\left(p_{t},P^{\pi^{*}}\right)$ $\displaystyle=\mathbb{E}\left[\sum_{\pi}p_{t}(\pi)\log\left(\frac{p_{t}(\pi)}{ P^{\pi^{*}}(\pi)}\right)\right]$ $\displaystyle\geq\mathbb{E}_{P}\left[(1-\delta)\log\left(\frac{1-\delta}{P^{ \pi^{*}}(\pi^{*})}\right)\right]$ $\displaystyle=(1-\delta)H(\pi^{*})-(1-\delta)\log\left(\frac{1}{1-\delta}\right)$ $$

where the second inequality follows from the fact that $p_{t}(\pi^{*})\geq 1-\delta$.
∎

From this, we can conclude that any algorithm whose policy converges to the optimal decision obeys the assumption.

Figure: (a) Bayesian regret
Refer to caption: extracted/5907235/Figures/bayes_bandit_regret.png

###### Lemma D.4 .

###### Proof.

###### Proposition D.5 .

###### Proof.

###### Corollary D.6 (Proposition 4.5 ) .

###### Proposition D.7 .

###### Proof.

## Appendix E Bandit Experiments

### E.1 Additional Details

The mutual information for the experiments in this setting is estimated using the KL divergence between the output probability distribution of every algorithm with the prior probability, $D\left(p_{t},P^{\pi^{*}}\right)$. This is an estimator of the mutual information, similar to the one used by Seldin et al. []. The mutual information was then calculated according to $D\left(p_{t},P^{\pi^{*}}\right)$, where $p_{t}$ is the real posterior. In our problem, the posterior update is done in the following manner.

$$ $\displaystyle P(\pi^{*}=i\mid\mathcal{H}_{t})$ $\displaystyle=\frac{P(\mathcal{H}_{t}\mid i)P(i)}{P(\mathcal{H}_{t})}$ $\displaystyle=\frac{P(\mathcal{H}_{t}\mid i)P(i)}{\sum_{j}P(\mathcal{H}_{t} \mid i)P(i)}$ $$

where

$$ $\displaystyle P(\mathcal{H}_{t}\mid i)$ $\displaystyle=\left(\frac{1+\epsilon}{2}\right)^{N_{s,i}}\left(\frac{1- \epsilon}{2}\right)^{N_{f,i}}\prod_{j\neq i}\left[\left(\frac{1-\epsilon}{2} \right)^{N_{s,j}}\left(\frac{1+\epsilon}{2}\right)^{N_{f,j}}\right],$ $$

and $N_{s_{i}}$ is the number of successful pulls (pulls that received reward 1) of arm $i$. $N_{f,i}$ is the number of failed pulls of arm $i$.

In both bandit experiments, we used 200 random seeds. Each random seed considers both the randomness in the problem generated (since the bandit problem is generated via a prior) and the randomness during the algorithm’s execution. We then reported in each graph the standard error for both the regret and mutual information, which is given by $\mathrm{err}=\frac{2\sigma}{\sqrt{n}}$ where $\sigma$ is the standard deviation and $n$ is the number of seeds.

### E.2 Additional Experiments

We use the same bandit setting as in Section 5. In this experiment, we compare the regret of Thompson sampling under three $H(\pi^{*})$ values. We use the same model space and number of arms. Results are presented in Figure 3. As we can see, when less information can be accumulated, less regret is suffered.

Figure: Figure 4: The prompting done for the LLMs in our experiments. The question is preceded by a question prompt followed by "Answer the following question:". Following this, the options are presented. <Question prompt> and <End prompt> are both replaced by a different prompt for every model.
Refer to caption: x2.png

## Appendix F MCQA with LLM Experiment

### F.1 Additional details

In this experiment, we used a small LLM and a large LLM in every experiment. The small LLM was one of the following: Mistral 7B [Jiang et al., ], Gemma 2B [Team et al., ] and Falcon 7B [Almazrouei et al., ]. For the large LLM we used Mixtral 8x7B [Jiang et al., ], Llama3-70B [AI@Meta, ] and Gemma 7B [Team et al., ]. 4-bit quantization [Dettmers and Zettlemoyer, ] and flash attention [Dao et al., ] were applied for all models (excluding Falcon 7B, for which flash attention was not applied).
In every round, we queried the LLM with a prompt, which is described later on.
An example of the prompt used is provided in Figure 4.
Using the LLM’s output we obtain a probability distribution over the tokens of the possible answers [A,B,C,D]. We then selected the answer according to this distribution and received feedback on whether the answer was correct, which was our reward. We also see that performance improvement is not clear when we use Mistral for the small model and Gemma 7B for the large one. This is because they are similar in size, while for the rest of the experiments, the larger LLM has significantly more parameters.

**Table 4: Regret for 10 different seeds for random and bits-based policies in LLM selection for MCQA tasks. Both policies were allowed to query the large LLM for only 50% of the episodes. The top row corresponds with the large LLM and the left column with the small one.**
|  | Random | Bits-Based |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | Mixtral | Llama3 | Gemma 7B | Mixtral | Llama3 | Gemma 7B |
| Mistral | $38.7\pm 0.3$ | ${47.0\pm 0.5}$ | $40.4\pm 0.3$ | $\mathbf{36\pm 1}$ | $\mathbf{46\pm 1}$ | $\mathbf{40\pm 1}$ |
| Gemma 2B | $44.5\pm 0.7$ | $54.1\pm 0.6$ | $39.3\pm 0.3$ | $\mathbf{38\pm 2}$ | $\mathbf{46\pm 2}$ | $\mathbf{35.3\pm 0.9}$ |
| Falcon 7B | $44.0\pm 0.3$ | $52.2\pm 0.4$ | $45.5\pm 0.3$ | $\mathbf{35.0\pm 0.8}$ | $\mathbf{44\pm 1}$ | $\mathbf{39\pm 1}$ |

**Table 5: Regret for 10 different seeds for random and bits-based policies in LLM selection for MCQA tasks. Both policies were allowed to query the large LLM for only 70% of the episodes. The top row corresponds with the large LLM and the left column with the small one.**
|  | Random | Bits-Based |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | Mixtral | Llama3 | Gemma 7B | Mixtral | Llama3 | Gemma 7B |
| Mistral | $30.5\pm 0.4$ | ${33.8\pm 0.4}$ | $34.8\pm 0.3$ | $\mathbf{26.6\pm 0.8}$ | $\mathbf{31\pm 1}$ | $\mathbf{33.0\pm 0.8}$ |
| Gemma 2B | $35.6\pm 0.8$ | $40.1\pm 0.6$ | $32.9\pm 0.3$ | $\mathbf{32\pm 1}$ | $\mathbf{36\pm 2}$ | $\mathbf{30\pm 1}$ |
| Falcon 7B | $34.0\pm 0.3$ | $37.0\pm 0.3$ | ${37.9\pm 0.2}$ | $\mathbf{27.0\pm 0.7}$ | $\mathbf{31\pm 1}$ | $\mathbf{33\pm 1}$ |

We repeated this process for 10 different question seeds. Table 2 reports the regret after 200 steps for all combinations of LLMs across all 10 seeds. Additional results are presented in Tables 4 and 5. Both tables compare the random selection method and the bits-based one for different LLMs. Table 4 compares the regret for 50% deployment rate of the large LLM and Table 5 compares the regret for 70% deployment rate of the large LLM. We conclude from both tables that the effect of the bits-based policy increases with the deployment rate of the large LLM. Furthermore, we also see that bits-based selection becomes more significant, as the performance gap between the small and large LLM increases as well.

### F.2 Compute Specifications

The bandit experiments are performed on a CPU and do not require special compute workers.
The experiments using Mistral 7B, Gemma 2B, Gemma 7B and Falcon 7B were evaluated using a machine with RTX4090. The experiments using Mixtral 8x7B and Llama3-70B were performed using a machine with 3xA40.

### F.3 Dataset and Models License

The MMLU dataset [Hendrycks et al., , ] is available under the MIT license. Mistral 7B [Jiang et al., ], Mixtral 8x7B [Jiang et al., ] and Falcon 7B [Almazrouei et al., ] are available under the Apache license 2.0. Gemma 2B and 7B [Team et al., ] are available under the Gemma license. Llama3-70B [AI@Meta, ] is available under the Llama license.

### F.4 LLM Prompts

We now describe the different prompts for every LLM.

#### F.4.1 Mistral and Mixtral

#### F.4.2 Llama3

#### F.4.3 Falcon

#### F.4.4 Gemma 2B / 7B

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: .
soundness: 3
strengths: The problem formulated in this paper seems interesting, and it is interesting to see how information affects learning in general. 
The paper also companies its theoretical results with experiments.
summary: This paper studies regret minimization when extra information about the prior is revealed. 
In particular, the authors consider contextual bandit problems, where at each round, the natural reveals some context and the algorithm needs to select actions based on the context. The authors consider a Bayesian set up, where there are some Bayesian prior on the context/reward. The external information reveals extra information about the prior. Under this formulation, the paper studies how external information affects learning and performance.

The paper proves both upper and lower bounds that depend on the amount of information an agent accumulates. The theoretical results demonstrate that information, measured in bits, can be directly traded off against regret, measured in reward. The paper also validates their findings through experiments with both traditional multi-armed bandits and a practical application involving large language models for question-answering tasks.
weaknesses: The technique is not the strong part of this paper.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: - Can the authors comment on how the proposed regret bounds might extend to adversarial or non-Bayesian settings? Are there particular adjustments or challenges anticipated in these contexts?
- Could the authors comment on extensions to settings where the information depends on prior actions?
soundness: 3
strengths: - The paper presents an interesting information-theoretic approach to quantifying the regret-information trade-off
- The theoretical approach is rigorous, with clear definitions and proofs
- The paper is well-organized
- The paper holds high significance for fields involving sequential decision-making (online learning in particular)
summary: The paper investigates the trade-off between information acquisition and regret minimization in sequential decision-making. It introduces a framework to quantify this trade-off, drawing on information-theoretic methods. The authors present novel Bayesian regret lower bounds that depend on the information accumulated by the agent, and they show how these quantify the relationship between external information and regret. 
For brownie points, they show an application of their theory to question answering with LLMs.
weaknesses: - The assumption regarding information gathering being independent of task history could limit applicability in some environments

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 1
questions: I don’t have further questions beyond what I’ve written above in “Weaknesses”.
soundness: 3
strengths: I think this work has many of the ingredients of a strong conceptual paper. The authors identify a conceptual phenomenon which spans many mathematical models, formalize that phenomenon, and develop a method which can analyze this phenomenon simultaneously in all of those models.

Although the LLM experiment initially felt out of place to me, I actually think it provides a nice complement to the theoretical results (although the theoretical results certainly remain the primary contribution).

Overall, I think the ceiling for this paper is quite high.
summary: The paper studies a general sequential decision-making framework from a Bayesian perspective. Within this framework, it is intuitive that the more information the agent accumulates, the lower the resulting regret. The goal of the paper is to formalize that intuition. The paper does the following:
1. Develops new information-theoretic methods for analyzing sequential decision-making algorithms
2. Uses those methods to recover existing lower bounds for a range of sequential decision-making problems, such as standard multi-armed bandits, tabular RL, Lipschitz bandits, etc (Table 1).
3. Obtains lower and upper regret bounds which depend explicitly on the number of bits of information accumulated.
4. Runs a question-answering LLM experiment inspired by the above results.
weaknesses: I have serious concerns about the presentation. Although the conceptual idea behind the paper is intuitive, it took me a while to make sense of the technical content of the paper. I think there are two issues:
1. Confusing writing and non-standard terminology. 
2. Lack of explanation of the technical statements.
I have provided a non-exhaustive list of examples below.

Although I am not an expert in information-theoretic methods, I am quite familiar with bandits, RL, and Bayesian regret, so more casual readers may struggle even more than me. If the paper purports to elucidate the intuitive tradeoff between information and regret, but the technical results are not accessible to readers, then I believe the impact of the paper will be limited.

I also think the LLM experiments could be improved by including baselines of always querying/never querying the large LLM. Table 2 suggests that with the query cost of 0.1, always querying the large LLM might actually be the optimal policy. To me, this suggests that a larger query cost is needed and calls into question the significance of the evaluation.

Overall, although I think the paper has many merits, I lean towards rejection so that these issues can be addressed, hopefully resulting in a strong final paper.

_Writing issues_
1. I found it a bit hard to make sense of Section 1.1 (“Contributions”) without at least informally defining the model. It would also be useful to link to the theorems/sections corresponding to each of the results.
2. Some of the terminology and notation is a bit confusing. Normally $\pi \in \Pi$ denotes a policy, but here it denotes a “decision” (basically an action). Instead, $\phi \in \Delta(\Pi)$ is called a policy, which seems like it should just be called a randomized decision/action. Furthermore, $p_t: \mathcal{C} \to \Delta(\Pi)$ is _also_ called a policy, which is more in line with the normal usage of “policy”. And $\pi^*$ is also a function from $\mathcal{C} \to \Delta(\Pi)$, which gives it a different type than $\pi$. I have also never before seen the term “epsilon-local set” used to describe epsilon-balls. I would suggest better aligning terminology and notation with the literature.
3. In Example 2.1, is there a reason that you use Bernoulli rewards instead of general rewards? Does your model not cover contextual MAB with general rewards.
4. Lines 197 - 215: I assume the rho separation assumption is for policies in $\Phi$, not for policies in $\Delta(\Pi)$? If it is supposed to be $\Delta(\Pi)$, that seems like a very strong assumption about the structure of the decision space.

_Lack of interpretation/explanation_
1. I understand that Yang and Barron also make Assumption 3.1, but it seems pretty unintuitive to me, and I would have appreciated some explanation.
2. Theorem 3.4, especially (9), is a bit hard to make sense of. Could you provide an interpretation for this expression?

_Minor issues_
1. Line 41: resource allocation is much broader than the specific routing problem you describe. Consider something like “One example of a resource allocation problem is route a process…” The flow in this section also feels a bit weird since you never bring up resource allocation again in the paper. Consider omitting either the resource allocation or online game example and using a single running example?
2. Since Section 4 also includes upper bounds, should the title be “Information-theoretical regret upper and lower bounds?”
3. Table 2 caption: the “Appendix ??” reference is broken

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: - (3) The first column in Table 2 resembles a budgeted setting. Can there be an autonomous scenario? For instance, let the learning agent decide the proportion of queries.
soundness: 3
strengths: - The submission points out that using Fano, one can introduce the mutual information into the regret bound. The connection between the mutual information and the accumulated knowledge bits (R) provides a means to analyze the effect of the knowledge bits (R) on the regret bound.
- Moreover, Prop. 4.5 provides an entropy-dependent Bayesian regret lower bound, which is listed in the last entry of Table 1.
- The advantage of accumulating information in bits is experimentally justified (Figure 2).
- A bits-based query policy illustrates the advantage of quantifying knowledge in bits and searching for a query that will bring an abundant increase in the knowledge accumulation.
summary: The submission studies the information lower bounds of bandits. By relating the mutual information to KL divergence and entropy, the submission rephrases regret bounds in terms of information bits. The new form of the bounds allows a learning agent to acquire and accumulate additional knowledge through active queries (as opposed to passive observations in the previous setting). The main results are summarized in Table 1, consisting of Theorem 3.4, Proposition 4.1 and Proposition 4.5. In the experiments, the advantage of information accumulation is verified in a simulation (Figure 1). Then, a query strategy is proposed and tested in MCQA.
weaknesses: - (1) Combining Prop. 4.1 and 4.3, the submission provides a range of bits required to achieve a given level of regret. Note that the range has a $\sqrt{logK}$ gap.
- (2) The proof sketches of the main results (e.g., Proposition 3.2, Theorem 3.4, Proposition 4.1, and the others) are plain. It seems that packing and covering are standard techniques in analysis. Could you please elaborate on the technical challenges and the corresponding contributions in the sketches?

Meta-review: This paper develops new information-theoretic methods for analyzing sequential decision-making algorithms. The methods are then used to recover existing lower bounds for a range of sequential decision-making problems. The reviewers gave overall very positive feedback and unanimously recommend acceptance of the paper. There are, however, some significant concerns about the presentation of the paper and I suggest that the authors implement the wide range of changes suggested by the reviewers.

Decision: Accept (Poster)