On Bits and Bandits: Quantifying the Regret-Information Trade-off
Authors: Itai Shufaro
Nadav Merlis
Nir Weinberger
Shie Mannor
Venue: ICLR 2025 Poster (2025)
Keywords: Online learning
Information theory
Bayesian regret
Bandits
Primary area: reinforcement learning

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.

Published as a conference paper at ICLR 2025
ON BITS AND BANDITS: QUANTIFYING THE REGRET- INFORMATION TRADE-OFF
Itai Shufaro
Nadav Merlis
Technion
ENSAE nadav. www.mmerllie www.mmmeeesssee....e fr
itai. heaa.sshufarrocccmss.teeeec www.:/ppppp..ttttttio......aa i1
Nir Weinberger
Shie Mannor
Technion
Technion, NVIDIA Research shieβee technion.
pirsein@techiion.ac
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 re- gret by querying external sources. We study the trade-off between the information an agent accumulates and the regret it suffers. We invoke information
methods for obtaining regret lower bounds, that also allow -ioomation-tthoortiic theoretic easily re-derive several known lower bounds. We introduce the first Bayesian regret lower bounds that depend 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 per- formance of guestion-answerrngg task with large language models, allowing us to obtain valuable insights.
INTRODUCTION
In interactive decision-making problems, an agent repeatedly interacts with a task by sequentially choosing decisions from 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 & Szepesvári, 2020). In partial monitoring, however, it only includes a signal, which the agent then utilizes to indirectly infer the reward (Cesa-Bianchi al.) 2006). The goal of the agent in such tasks is 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 feed- back 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 ex- ternal sources, such as human advice (Najar & Chetouani (021). text description generated by large language models (Du et al. 2023 Hu & Sadigh] 2023), and more.
In some tasks both information from direct interactions and external information are present. One example is RL with LLM (Du et al. (203), where an agent interacts with an online environment and is provided with advice from LLM. The agent can interact with the environment well as ask the LLM for advice.
Consider two agents playing on the same online task. Both agents have access to the same obser- vations, 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 the first agent. In this paper, focus how much information the second agent needs to query

---

Published as a conference paper at ICLR 2025
Observation
Information
Knowledge
Task Trajectory
Reward
Decision
Figure Schematic of a general interactive decision-making task with contextual information. Every round, source of knowledge provides agent with information. The agent then makes a decision, that causes the task to generate an observation and a reward. The observation is revealed the agent, who updates his next decision according the past observations and the information he received.
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?
1.1 CONTRIBUTIONS
New method for obtaining regret lower bounds. We consider an interactive decision-making framework that describes general online tasks with contextual information in Bayesian setting. We then introduce novel information-theoretioo method to obtain regret lower bounds for decision- making problems in this setting. This method uses Fano's 's inequality (Cover) 1999) and the construc- tion method introduced by Yang & Barron 1999) to lower bound the worst-case Bayesian regret. In Theorem 3.4 we introduce the general lower bound, and Table shows its application on MAB, contextual bandit, and RL tasks.
Information-theoreti prior-dependent bounds. The total amount information an agent gath- can be quantified to bits by the mutual information functional. Proposition 4. presents Bayesian regret lower bounds that depend on the amount of information an agent accumulates. Additionally, Proposition 4.3 upper bounds the regret for Thompson sampling (Thompson 1933) in MAB en- vironment, which depends on the information the agent collects. We also present lower bounds for scenarios where the entropy of the prior is constrained in Proposition 4.5
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 be- tween the rate of information accumulation and regret in online tasks. These relationships allow us to measure how much regret can 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 we present our setting and relevant preliminaries. Section we present novel information- theorrtti method for obtaining regret lower bounds. In Section we present regret bounds that depend the information accumulated by the agent, followed by experiments in Section Section 6 we review related work, and draw conclusions in Section 7
2 SETTING AND PRELIMINARIES
We introduce setting called interactive Docision-makingg in Bayesian environments with textual information, which illustrated in Figure [ This setting Bayesian adaptation of the frequentist interactive decision-making setting introduced by Foster al. (202)). We denote the set
2

---

Published as a conference paper at ICLR 2025
of Borel probability measures over locally compact space by A(:). Let II be compact decision space, M be a compact model space and C be a compact context space. Every model M E M is mapping from the decision and context space to an observation space O, ie., M II x C + O. Every model M has a reward function, RM IT x C + ( 1]) that maps every decision-context pair reward distribution over [0, 1]. A task in this setting is defined by the decision space II, the model class M, the context space C, the reward functions RM, and the prior P E A(M x C). We denote by pM (T, C) = (M. [x] the mean reward of decision π under model M and context C. With slight abuse of notation, we also denote by (M( C) En=olurs( C)], the mean reward of a stochastic decision & E A (III under model M and context C.
In a T-round game, random model M is sampled before the game starts according to the prior P. Then a context C2 is sampled every round, independently from previous rounds, according to the marginal prior probability P(- M). Before each round starts, the context C, is revealed to the agent, who determines his stochastic decision P: C + A according to the context and the observed history. Then, a decision He ~ ps is sampled and an observation O₂ ~ M Ct) is revealed to the agent. A reward, re ~ RA Ct) is also generated. We denote the history up to time as H, = {Ci, ,. O:) We denote MM. = arg max [MM(TT C). We measure the performance with respect to the best context- context-dependent decision in hindsight. This performance metric is called the Bayesian regret and is defined by
(Rp (pe)) = E Σ (pN((TM,,,,,)) Ci) m)) -.))
(I)
where the expectation is taken with respect to the randomness in decisions. contexts, observations, and rewards ((M, Ci) P. T. Pt and re Rys (TT, Ct)). We also note that by fixing a single context, |C] = 1, the setting reduces to regular Bayesian interactive decision-making. When obvious from the context, P and (p:) 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, II = 2I. K}. Furthermore, we assume that the context space is finite
well, C f1,2,.... ... The model class is then given by M = {fif= II x C - [0, 1]}. so every model maps C) to Bern(f(T,, C)). At each round context is sampled and revealed. A decision n, is selected and the observation is the incurred reward, r; = O ~ Bern (TT, Ct)). We note that the Bernoulli rewards were selected to maintain simple example, and that our setting also covers general reward distributions.
Example 2.2 (Tabular reinforcement learning with a finite horizon). The finite-horizon tabular MDP defined by the tuple (8, PP 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, 1j. In this setting, the decision space is all of the deterministic policies, so IT = (π S H - A). The model class M defined by the set of all MDPs with the same state space, action set, and horizon. At every time step, the agent determines policy and plays over the entire horizon. The observations are the trajectories, which include the visited states, rewards, and actions performed.
Covering and packing. Consider a normed space A with metric d induced by the norm, and let > 0. We denote by (d,, A) and M(d, e) the e-covering and e-packing numbers of A under the norm d, respectively. We define an e-ball b E A as B(,, c) = {a E A d(b, a) S c), for every b E A and c 0. The local packing number, denoted by Mloc (d, A, c), is the largest -paakai set of any set B(b, e), i.c.,
Mase Ad c) max (M there is b such that the (c/2)- number of B(b, c) is M).
When d(r,y) = || vllp we denote by (,,, and Mile () the e-packing, 6- covering and clcaa packing number, respectively. Detailed definitions and properties of the cover- ing, packing and local packing numbers are provided in Appendix B
Additional notations. We denote by HX) = E[- log Q(X) the Shannon entropy of a random variable X ~ Q, and with a slight abuse of notation, we also denote H(Q) H()). Given
3

---

Published as a conference paper at ICLR 2025
Table I: Lower bounds for online problems, recovered using methods presented the paper.
Problem
Retrieved lower bound
Optimal?
MAB
R(vK7
KT)
Yes
Audibert & Bubeck
2009)
Tabular RL
S HSKT)
Yes
Zhang al.
2021
Linear bandits
S(vdT dT)
No
441
Lipschitz bandit
Ω
T 842
Yes KKleinberg et al.
2019
Bayesian MAB (R bits)
Ω
KT log
First bound
Bayesian linear MAB (R bits)
Ω
/dT IdT
log
First bound
Bayesian MAB
KT ((x)) Tog K
First bound
two jointly distributed random variables, (X,Y) Q, we denote their marginal distributions by (xr) and (3)) We also define the mutual information of two jointly distributed random variables
(X,Y) ~ Q as I( = E log Q(190)) ) The KL-divergence is defined as DKL (P Q) =
P(X) Ex-P log Q(x)
Cover 1999). Unless stated otherwise, logarithms are assumed to be in base-2,
denoted by log. We also denote x Z y if there is some global constant e such that æ 2 cy. We
define by Bd {x Rd
||=||, 1} the unit sphere in Edd under the Lp norm.
REGRET LOWER BOUNDS USING FANO'S INEQUALITY
We now introduce novel approach for obtaining worst-case Bayesian regret lower bounds, which can be applied wide variety of interactive decision-making tasks. This method can be viewed extension of Fano's 's incquality for non-exact recovery (Scarlett & Cevher 2019) to online problems. We define worst-case Bayesian regret the following manner,
sup inf BR; (pr)te) (R"(T)
(EA(MxC) {P+)T.
To lower bound the worst-case Bayesian regret we use Fano's 's inequality.
Theorem 3.1 (Fano's inequality, Theorem 2.10 of Cover (1999).. Let X,Y Q be two jointly distributed random variables, where X can take values over finite set, whose cardinality is X. Let
X = f(Y) for some f be an estimator of X. If X is uniformly distributed over all possible values X, then the following holds for all f.
P(X + x 1(X;Y)+1
(3)
log X
While Theorem 3.1 used lower-bound the error in hypothesis testing problems, now show how it can also be applied to regret minimization. We assume access to some set Φ = {di...., .x) of (possibly stochastic) decisions. We also assume that metric p exists such that Ellpar( C C (s C)ll 2 p(ó. 1b) for all u à E A(II. The following proposition applies Theorem 3.1 to regret minimization, by reducing it to a hypothesis testing over the finite set
Proposition 3.2. For any algorithm, prior P, a decision set & (Φ1.... Ox} C A(II) and for all 0 such that pl 05) 2 e for all + j.
(T)
I(V; H H(V;
1
Te
log
where V is the index of the best decision in hindsight from the set Tb
The proof of Proposition 3.2 is provided in Appendix C.I
Proposition 3.2 allows us to lower-
bound the Bayesian regret using a specific set of decisions. We suggest method for selecting the
4

---

Published as a conference paper at ICLR 2025
decision set 4, which provides general approach for obtaining regret lower bounds. We separate our analysis into finite, parametric with infinite decisions, and non--oramaan con-paaaettric decision spaces. This separation is done to make the lower bound in Equation Migutte tighter. We observe that the lower bound tighter for larger values of K. Thus, we should select the largest value of K that satisfies the requirement p(ti, $5) Z for given
O. For finite decision spaces, we choose & to be e-local packing set of the decision simplex, AlI), according to under P. So, we have K (M (lI)), e). Similarly, for parametric decision spaces with infinite decisions, we choose & to be an c-local packing set of the decision set, II, i.e., K = M (p. II, c). For con-parametric decision spaces, we use an e-global packing set of our decision space II, which means that K M(p e). After selecting 4, we need to handle I(V; HT). To do this, we make the following assumption about the decisions.
Assumption 3.1. There exist constants A, co > 0 such that for all stochastic decisions P1: P2 such that p(p1, P2) S cu. DKL (pi P2) S 2Ap(pi. P2)2.
This assumption means that for all stochastic decisions in co-ball around Pt. the KL divergence can be upper bounded using and is commonly made, for example, by Yang & Barron (1999) The following theorem upper bounds T(V; H.r).
Theorem 3.3 (Yngg& & Barron 1999)). Let Assumption 3.1 hold. Under the assumptions and nota- tions of Proposition 3.2 is parametric decision space then
:(T S 2ÂeT
(5)
for S c0- II is non-parametric decision space then
I(V:Hr) < inf (log.V (p. vo) TT) 850
(6)
Now, substituting Theorem 3.3 in Proposition the following Theorem.
3.2 and selecting + described above, results in
Theorem 3.4. Let there be a Bayesian interactive decision-making problem as defined in Section and let e >> O. If 11 is a finite decision space,
(T)
1
AT + log.M Mloc (p. A(II,
Te 2
If II is an infinite parametric decision space,
BR BR*(T) (T))
2c AT + 1 log Mloo (p, IT,
(8)
Te
If II a non-parametric decision space,
infoso (log/V (,, 11, vo) + T88
BR (T)
+1
1
(9)
Te
log Log,(p,11,e El,
The proof Theorem 3.4 is provided in Appendix C.2 To obtain regret lower bounds, all we need are the values of the packing local packing, and covering numbers of the decision space. Then, we simply need to select a value of such that the right-hand side of Equations] 7 g or 9 a positive constant. In Appendix C demonstrate this, by deriving regret lower bounds for several known online problems, which are summarized in Table [ Moreover, this method can be used to obtain lower bounds for the frequentist regret, due the mini-max theorem, which states that the worst- case Bayesian regret is equal to the mini-max frequentist regret (Lattimore & Szepesvári 2019).
4 INFORMATION THEORETIC BAYESIAN REGRET UPPER AND 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--heorrtiiic terms, mutual information quantifies
5

---

Published as a conference paper at ICLR 2025
the amount of information random variable contains about another one (Cover 1999). This means that mutual information can be utilized to measure the information that is aggregated from various sources using 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 [ H6) = DRL. (Px" [Pr || P**).
Thus, for general agents, DKL (pr pT)) 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 < 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 bits. Then the
Additionally, if II Bğ and the rewards are a linear function of the decisions, then the worst-case Bayesian regret can be lower bounded by (Ta
worst-case Bayesian regret can be lower bounded by St
( log R
log
Furthermore, if R 0 the worst-case regret linear.
The proof of Proposition 4.1 utilizes Lemma D.I which, similarly to the proof of Theorem 3.3
introduces an upper bound for the mutual information, but this time taking the information con- straint 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 S log K be given. Assume that the Bayesian decision problem has finite decision space of size K, such that DKL (Px p" < for all t. Then,
BR (T))
AT
log +
(10)
TE
log Mice (p. ATT)),
Furthermore, if the decision-making problem is a part of a parametric set, then
BR (T)
1
2< log +1
(11)
Te
2
log Mloe (p. El,
The proof follows from Proposition 4.2 by selecting an appropriate value of e. We now state an upper bound for MAB problems where the agent accumulates R bits.
Proposition 4.3. Assume an K-MAB problem with constraints. Let Öi, for be constrained observations and history such that [mr;; ;Hr) R. The regret of Thompson sampling with these observations is upper bounded by O [log K
KT
Additionally, if the MAB is linear the regret
can be upper bounded by O [log
4T R
Detailed proofs of Propositions
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- decision-making task. A has an advantage over B, since he already played multiple rounds before. B can query external information reach the same level of performance as A on the task. Using the regret upper bound in Proposition 4.3 we can get lower bound on the information needs. Similarly, Proposition 4.1 gives an upper bound on the number of bits. Thus, Propositions 4. 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 Vlog K.
These Propositions also allow to quantify the relationship between the rate of information accu- mulation and regret. If both parties play for the same number rounds, the one that accumulates information faster will also suffer less regret.
4.2 ENTROPY CONSTRAINT
While Proposition 4.1 shows how we can lower bound regret under a constraint on accumulated information, shift focus constraint the prior only, i.e H(*)) < R. Russo

---

Published as a conference paper at ICLR 2025
TS
2.5
T5
APS
APS
60
EXP3
EXP3
Mut.al Information
2.0
Regret
1.3
0
0.0
0
200
400
600
800
1000
0
200
400
600
800
1000
(a) Bayesian regret
(b) Accumulated information
Figure 2: (a) The Bayesian regret and (b) the accumulated information in bits for three different bandit algorithms, under the same bandit structure and a uniform prior. The bandit algorithms used described in the legend. The shadowed areas correspond to 2-sigma error bars.
& Van Roy 2014 2016) showed that in this scenario, the regret of Thompson sampling and information-directed sampling (IDS) can be upper bounded using 11 (T*).
Theorem 4,4 (Propositions 2 and 4 of Russo & Van Roy (2014). In the K-MAB setting, the regret of Thompson sampling and IDS is upper bounded O(y (T)()*)) Furthermore, if the rewards linear function of the decisions, and the decisions vectors in R then the regret is upper bounded by (VTTH(TT)
We next develop an following assumption.
Bayesian regret bownd-bound for algorithms that obey the
Assumption 4.1. DKL (px p=') cAR for all t, for some constant > 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 S2 (V log [KHET]T)
Additionally, if the MAB is linear, then the regret is lower
(V
( log K
bounded by 2
We that this lower bound behaves like the upper bound Presented in Theorem 4.4, up to a factor of Vlog K. We also show in the appendix that Assumption 4.1 holds for any algorithm that learss the optimal decision.
The proof of Proposition 4.5 can be found in Appendix D.3
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 E), except for one arm for which the mean is 0.5(1 + e). The optimal arm is different for every model, and the reward of each arm is Bernoulli distributed. We also fix K 8, 0.1 and uniform prior over the problems and compare three different bandit algorithms EXP3 (Lattimore Szepesvári] 2020), APS (Xu & Zeevi 2023), and Thompson sampling (Thompson, 1933). 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

---

Published as a conference paper at ICLR 2025
Table 2: Mean regret for both policies for 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
% Deployment
Bits-based
Random
Small only
Large only
50%
36 1
38.7 + 0.3
Mistral 7B
70%
26.6 + 0.8
30.5 + 0.4
5.7
08.2
90%
21.8 = 0.4
22.4 + 0.5
50%
38
44.5 0.7
Gemma 2B
70%
32 1
35.6 + 0.8
67 +
22 + 1
90%
26 1
27 +
sampling under different priors (TT)). The results of this experiment can be found in Figure Additional experimental details are provided in Appendix E
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 sequential multiple choice question-answeriigg (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 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 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 less regret as we have seen in Section Otherwise, use the small LLM. We call this approach the bits-bascd 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 ques- tion and possible answers, which returns scores for each token. We take the scores corresponding only for the tokens [A, B. C, DJ. each corresponding 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 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.
different answer, and use them to get
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. (Hendryeks et 2021b]a). We used 10 different seeds to generate 10 sets of 200 questions from MML.U randomly. yy For the small L.LM we either used Mistral 7B Jiang et al. (203)) Falcon 7B (Almazrouei et al. 2023), or Gemma 2B (Team et al.) 2024). We used Mixtral 7Bx8 (Jiang et al. (2024). Llama3-70B (AI@ Metal 2024), Gemma 7B for the large LLM. We applied 4-bit quantization (Dettmers & Zettlemoyer 2023) for all models and flash attention (Dao et al. (022) 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 5loovide 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 increase the
8

---

Published as a conference paper at ICLR 2025
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 provided in Appendix F Code is available herd"
RELATED WORK
Bayesian setting. In the Bayesian setting, prior information assumed to be expressed as a prob- ability distribution, called the prior. New information is then incorporated using Bayesian infer- ence 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 & Van Roy| 2014 Kaufmann et al., 2012) and reinforcement learning (Guez et al.) 2012] Ghavamzadeh et al. 2016). Upper bounds for Bayesian algorithms have been proved for both the frequentist (Kaufmann et al., 2011] and Bayesian settings (Russo & Van |2y|[2014]]] 2016). Prior de-
pendent regret bounds for Bayesian algorithms have also been studied (Bubeck & Liu 2013, Russo & Van Roy 2014). Previous studies have explored prior-dependent lower bounds for Bayesian re- gret, but these are limited to specific forms of priors, such as Gaussian priors (Atsidakou et al.) 2024).
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.) 202I) and reinforcement learning frameworks (Klink et al.) 2020 Modi Tewari 2020). The contexts can be selected arbitrarily by an adversary (Beygelzimer et al. 2011] Chu et al. 2011) generated from some prior probability distribution, similarly the Bayesian setting (Hao et al. 2020 May et al.] 2012). Bayesian algorithms have also been adapted to the arbitrary context setting (Agrawal & Goyal| 2013). Furthermore, the type of information provided to the learner can expand beyond the contextual information provided directly (Schneider & Zimmert 20044). Our work introduces contextual Bayesian setting framework that covers a wide variety of interactive decision-making tasks.
Information-theorrtic methods have been employed to derive upper bounds for various on- line tasks. RRssoo & Van Roy (2016) introduced an information-thhorete method for establishing Bayesian regret upper bound for Thompson sampling in the multi-armed bandit setting, which de- pends on the entropy of the prior. This approach was also used to design new Bayesian algorithms that utilize mutual information called information-directe method it utilizes were also extended to other tasks such as
sampling (IDS) (Russo & Van Roy]
2014). IDS and the iiformation-theoreee contextual bandits (Neu et 2022), sparse linear bandits (Hao et al. 2021), non-stationary bandits (Min & Russo 2023; Liu et al. 2023). reinforcement learning (Luu & Van Roy 2019). non-linear control (Kkkade al. 2020), partial monitoring (Lattimore & Szepesvári, 2019) and other online
optimization problems (Liu et al., 2018 Dong et al.] 2019; Lattimore Gyorgy 2021 Russo &
Van Roy 2018). The bounds presented in works such as Russo & Van Roy 2016 2014 Neu
et al. 2022) are based on the upper bounding of the information ratio. Our work uses a different ap- proach, 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. (201T) utilized PAC-Bayes bounds obtain information-theoree theoretic upper bounds on the per-round regret, that depend on mutual information. |Arumugam & Van Roy (2021) 2022) have explored a different information-thed -thooretic method, utilizing rate-distortion theory to minimize regret.
CONCLUSIONS AND FUTURE WORK
We introduce general setting that embeds contextual information in a Bayesian setting. This set- ting covers wide variety of online decision decision-making tasks. Using information-theoreti tools, we demonstrated general method for obtaining regret lower bounds for problems 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
https://githubs cwt.uub..oommmee
t.s

---

Published as a conference paper at ICLR 2025
accumulated information. These results quantify the relationship between a-priori external infor- mation and regret in online settings and the relationship between online information accumulation and regret. We then utilized this trade-off in multiple-choice question-ani answering task with LLMs, demonstrating that the aforementioned quantification can be easily used in an online setting.
Limitations. central assumption in our analysis that exogenous information can be gathered regardless of the process history. However, this assumption may be violated in 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 & Olkhovskaya 2020 frequentist settings, different measure of information is required. Another limitation is the difference in vlog 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 Sklodowska-Cun Curie grant agreement No 101034255.
REFERENCES
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff's. In International conference muchine learning, pp. 127-135. PMLR, 2013.
AI@Meta Llama 3 model card. 2024.
URL https://gittub..cmm http://tttt...ccmmcmaaaaaaaaaaaa
CARD. md
Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxandra Co- jocaru, Merouane Debbah, Etienne Goffinet, Daniel Heslow, Julien Launay, Quentin Malartic, Badreddine Noune, Baptiste Pannier, and Guilherme Penedo. Falcon-40B: an open large lan- guage model with state-of-the-art performance. 2023.
Dilip Arumugam and Benjamin Van Roy. Deciding what to learn: A rate-distortion approach. In International Conference Machine Learning, pp. 373-382. PMLR, 2021.
Dilip Arumugam and Benjamin Van Roy. Deciding what model: Value-equivalent sampling for reinforcement learning. Advances in neural information processing systems, 35:9024-9044 2022.
Alexia Atsidakou, Branislav Kveton, Sumeet Katariya, Constantine Caramanis, and Sujay Sanghavi. Logarithmic bayes regret bounds. Advances in Neural Information Processing Systems, 36, 2024.
Jean-Y Jean-Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In COLT, pp. 217-226, 2009.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 19-26. JMLR Workshop and Conference Proceedings, 2011.
Alberto Bietti, Alekh Agarwal, and John Langford. A contextual bandit bake-off. Journal of Ma- chine Learning Research, 22(133):1-44 2021.
Sébastien Bubeck and Che- Yu Liu. Prior-free and dreer-dependent regret bounds for thompson sampling. Advances in neural information processing systems, 26, 2013.
10

---

Published as a conference paper at ICLR 2025
Nicolo Cesa-Bianchi Gábor Lugosi, and Gilles Stoltz. Regret minimization under partial monitor- ing. Mathematics of Operations Research, 31(3):562-580, 2006.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214. JMLR Workshop and Conference Proceedings, 2011.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Tri Dao. Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances Neural Information Processing Systems, 35:16344-1635, 2022.
Tim Dettmers and Luke Zettlemoyer. The case for 4-bit precision: k-bit inference scaling laws. In International Conference on Machine Learning, pp. 7750-7774, PMIR, 2023.
Shi Dong, Tengyu Ma, and Benjamin Van Roy. On the performance of thompson sampling on logistic bandits. In Conference on Learning Theory, pp. 1158-1160. PMLR, 2019.
Yuging Du, Olivia Watkins, Zihan Wang, Cédric Colas, Trevor Darrell, Pieter Abbeel, Abhishek Gupta, and Jacob Andreas. Guiding pretraining in reinforcement learning with large language models. In International Conference on Machine Learning, pp. 8657-8677. PMLR, 2023.
Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487 2021.
Mohammad Ghavamzadeh, Yaakov Engel, and Michal Valko. Bayesian policy gradient and actor- critic algorithms. Journal of Machine Learning Research, 17(66):1-53, 2016.
Arthur Guez, David Silver, and Peter Dayan. Efficient bayes-adaptive reinforcement learning using sample-based search. Advances neural information processing systems, 25, 2012.
Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in linear contextual bandit. In International Conference Artificial Intelligence and Statistics, pp. 3536-3545. PMLR, 2020.
Botao Hao, Tor Lattimore, and Wei Deng. Information directed sampling for sparse linear bandits. Advances in Neural Information Processing Systems, 34:16738-16750, 2021.
Dan Hendrycks, Collin Burns, Steven Basart, Andrew Critch, Jerry Li, Dawn Song, and Jacob Steinhardt. Aligning ai with shared human values. Proceedings of the International Conference on Learning Representations (ICLR), 2021a.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Mcasuring massive multitask language understanding. Proceedings of the Interna- tional Conference on Learning Representations (ICLR), 2021b.
Hengyuan Hu and Dorsa Sadigh. Language instructed reinforcement learning for human-ai coordi- nation. In International Conference on Machine Learning, pp. 13584-13598, PMLR, 2023.
Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chap- lot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b, 2023.
Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gi- anna Lengyel, Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie- Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang. Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang. Timothée Lacroix, and William Sayed. Mixtral of experts, 2024.
Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Infor- mation theoretic regret bounds for online nonlinear control. Advances in Neural Information Processing Systems, 33:15312-153255, 2020.

---

Published as a conference paper at ICLR 2025
Emilie Kaufmmann, Olivier Cappé, and Aurélien Garivier. On the efficiency of bayesian bandit algo- rithms from a frequentist point of view. In Neural Information Processing Systems (NIPS). Curran Associates Red Hook, NY. 2011.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On bayesian upper confidence bounds for bandit problems. In Artificial intelligence and statistics, pp. 590-600. PMLR, 2012.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts metric spaces. Journal of the ACM (JACM), 66(4):1-77, 2019.
Pascal Klink, Hany Abdulsamad, Boris Belousov, and Jan Peters. Self-paced contextual reinforce- ment learning. In Conference on Robot Learning, pp. 513-529. PMLR, 2020.
Tor Lattimore and Andras Gyorgy. Mirror descent and the information ratio. In Conference on Learning Theory, pp. 2965-2992, PMLR, 2021.
Tor Lattimore and Csaba Szepesvári. An information- -heorretc approach to minimax regret in partial monitoring. In Conference on Learning Theory, pp. 2111-2139. PMLR, 2019.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Fang Liu, Swapna Buccapatnam, and Ness Shroff. Information directed sampling for stochastic bandits with graph feedback. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Yueyang Liu, Benjamin Van Roy, and Kuang Xu. Nonstationary bandit learning via predictive sampling. International Conference on Artificial Intelligence and Statistics, pp. 6215-6244. PMLR, 2023.
Xiuyuan Lu and Benjamin Van Roy. Information-theorrtic confidence bounds for reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Benedict C May, Nathan Korda, Anthony Lee, David S Leslie, and Nicolo Cesa-Bianchi. Optimistic bayesian sampling in contextual-bandee problems. Journal of Machine Learning Research, 13(6), 2012.
Seungki Min and Daniel Russo. An information-thcoreti analysis of nonstationary bandit learning. In International Conference on Machine Learning, pp. 24831-24849, PMLR, 2023.
Aditya Modi and Ambuj Tewari. No-regret exploration in contextual reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pp. 829-838. PMLR, 2020.
Anis Najar and Mohamed Chetouani. Reinforcement learning with human advice: a survey. Fron- fiers in Robotics and AI, 8:584075, 2021.
Gergely Neu and Julia Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual
bandits. In Conference Learning Theory, pp. 3049-3068. PMLR, 2020.
Gergely Neu, Juliia Olkhovskaia, Matteo Papini, and Ludovic Schwartz. Lifting the information ratio: An information-theoretic analysis of thompson sampling for contextual bandits. Advances in Neural Information Processing Systems, 35:9486-9498, 2022.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-direecee sampling. Advances in Neural Information Processing Systems, 27, 2014.
Daniel Russo and Benjamin Van Roy. An informatioon-thoortiic analysis of thompson sampling. Journal of Machine Learning Research, 17(68):1-30) 2016.
Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. arXiv preprint arXiv:1803.02855. 2018
Jonathan Scarlett and Volkan Cevher. An introductory guide to fano's inequality with applications in statistical estimation. arXiv preprint arXiv: 1901.005,.. 2019. 2019..
12

---

Published as a conference paper at ICLR 2025
Jon Schneider and Julian Zimmert. Optimal cross-learning for contextual bandits with unknown context distributions. Advances in Neural Information Processing Systems, 36, 2024.
Yevgeny Seldin, Peter Auer, John Shawe-taylor, Ronald Ortner, and François Laviolette. Pac- bayesian analysis of contextual bandits. Advances in neural information processing systems, 24, 2011.
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, Pouya Tafti, Léonard Hussenot, Pier Giuseppe Sessa, Aakanksha Chowdhery, Adam Roberts, Aditya Barua, Alex Botev, Alex Castro-Ros, Ambrose Slone, Amélie Héliou, Andrea Tacchetti, Anna Bulanova, An- tonia Paterson, Beth Tsai, Bobak Shahriari, Charline Le Lan, Christopher A. Choquette-Choo, Clément Crepy. Daniel Cer, Daphne Ippolito. David Reid, Elena Buchatskaya, Eric Ni, Eric Noland, Geng Yan, George Tucker, George- Chhorge-hhristian Muraru, Grigory Rozhdestvenskiy, Hen- ryk Michalewski, lan Tenney, Ivan Grishchenko, Jacob Austin, James Keeling, Jane Labanowski, Jean-Baptiste Lespiau, Jeff Stanway, Jenny Brennan, Jeremy Chen, Johan Ferret, Justin Chiu, Justin Mao-Jones, Katherine Lee, Kathy Yu, Katie Millican, Lars Lowe Sjoesund, Lisa Lee, Lucas Dixon, Machel Reid, Maciej Mikula, Mateo Wirth, Michael Sharman, Nikolai Chinaev, Nithum Thain, Olivier Bachem, Oscar Chang, Oscar Wahltinez, Paige Bailey, Paul Michel, Petko Yotov, Rahma Chaabouni, Ramona Comanescu, Reena Jana, Rohan Anil, Ross Mcllroy, Ruibo Liu, Ryan Mullins, Samuel I. Smith, Sebastian Borgeaud, Sertan Girgin, Sholto Douglas, Shree Pandya, Siamak Shakeri, Soham De, Ted Klimenko, Tom Hennigan, Vlad Feinberg, Wojeiech Stokowiec, Yu hui Chen, Zafarali Ahmed, Zhitao Gong, Tris Warkentin, Ludovic Peran, Minh Giang, Clément Farabet, Oriol Vinyals, Jeff Dean, Koray Kavukcuoglu, Demis Hassabis, Zoubin Ghahramani, Douglas Eck, Joelle Barral, Fernando Pereira, Eli Collins, Armand Joulin, Noah Fiedel, Evan Senter, Alek Andreev, and Kathleen Kenealy. Gemma: Open models based on gemini research and technology, 2024. URL URthttps::: /ttp//axivvvv.v. wwt./ogg//b////ee abwp:/3bs/444...oo 08295
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-244, 1933.
Martin J. Wainwright. High--Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Yihong Wu. information-theoree methods for high-dimensional statistics. Lecture notes, Yale University, New Haven, CT, 2020.
Yunbei Xu and Assaf Zeevi. Bayesian design principles for frequentist sequential learning. In International Conference on Machine Learning, pp. 31768-3880000 PMLR, 2023.
Yuhong Yang and Andrew Barron. Information-theereeiee determination of minimax rates of conver- gence. Annals of Statistics, pp. 1564-1599, 1999.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference Learning Theory, pp- 4528 4531. PMLR, 2021.
13

---

Published as a conference paper at ICLR 2025
A
TABLE OF NOTATIONS
Table 3: Commonly used notations throughout the paper and the appendix.
Notations
Description
IT
The decision space.
M
The model class.
O
The observation space.
C
The context space.
π
A decision.
RM C)
reward distribution according to decision π on model M.
(M,(TT,)
mean reward according to decision on model M.
P
Prior probability of the task.
TM
The optimal decision for a model M.
H4
The total accumulated history up to round
(including observations and contexts).
P
stochastic decision selected at round t.
Reward sampled at time
P
A norm that lower bounds the difference in reward means.
(T)(T)
The Bayesian regret given prior P.
(T)
The worst-case Bayesian regret.
c(d,c,H)
c-covering number of H concerning metric d.
M(d,e,H)
e-packing number of H concerning metric d.
e-local packing number of H concerning metric d.
Vol(.)
Volume of a set.
B USEFUL PROPERTIES OF COVERING NUMBERS
Let H be normed space, and Definition B.1 (Covering and packing numbers (Wainwright 2019 let d(.,,) be the metric induced by the norm. Let c
A set C H is said be an e-covering set of И if for all h e there is C such that d(h, c) < c.
The covering number is defined as
M(d, H) = min {m 3C, |C| m and C an e-covering set of H}.
If d(x ||æ vllp we denote it by Mc, H).
A set C is said to be a packing set of // if for all Cı, 02 E C' we have that d(c1, 62) 2
The packing number is defined as
(dd, c, H) max (m 3C, |C| = m and is an c-packing set of H)
If d(x, v) ||+ v|lp- we denote it by Np(e, H).
We now define B(8,e) c) = {Ø' E H d 0) S E}. C B is an c-local packing set of B(0,c) if for all C1,02 C, d((), 02) > 4
14

---

Published as a conference paper at ICLR 2025
The local packing number is defined as
M (d, HI) max {m : 3B(0,e), such that C' is local packing of B and |C| m)
Lemma B.1. The following properties hold:
(Theorem 14.2 of Wu (0200) For any subset of dimension d that is contained in By the covering number Np(e) obeys dloog (2) I <logNN(()) S dllog (2). This includes the prob- ability simplex with d variables and Bz.
(Theorem 14.1 of Wu 2020 Under the same norms, for the same set,
M(2e) s N(O) - M(()
Throughout the appendix, Vol(A) denotes the volume of set A.
C PROOFS FOR SECTION
C. PROOF PROPOSITION 3.2
Proof. We write
BR (T) sup inf EMaw v Pr
Σ (UM( -
cT Pv
E(umeat HM ((),,,,o)2 eT 2 2 2
2 sup inf
Pr
2
7
sup inf P. (vt: pms( Cc) - pMs Mas C PL
max inf TP (vt: IuM (0x,, Ce) - MM (Pr. C,) 2 E /
2 k PT
el'
max inf PP IP(V pldre Tz) 2 2
ke kE.I.... K) Pr
max inf P(pp + sb))
1(V; +
2
log K
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
C.2
PROOF OF THEOREM 3.4
Proof. We provide proof for three different scenarios.
First scenario, finite II. For this scenario, we choose & to be local packing set of the decisions simplex (ITT, so K MM (p. A(T)) Applying this selection of set, and using Equation 4 we have that
BR (T)
1 [(V HT) log Moor (p. A AIII,
(12)
CT
2
Applying Theorem Equation| 12
3.3 have that 1(V; Hr) < 2A.TT.
Substituting this back into
BR (T)
1 T logM Mloc A(TI),)
C
2
15

---

Published as a conference paper at ICLR 2025
Second scenario, infinite-paramenie parametric II. For this scenario, choose & to be a local packing set of the decision space II, so K = -Moor(p. II, c). Applying this selection of set, and using Equation 4 we have that
BR (T)
+ I(V; Ht)
(13)
CT
log M (0o (p. cI,
Applying Theorem
3.3 we have that ((VHHr) 1 2Ac Substituting this back into
Equation 13
(T) eT
1
1 2Ac2T log Mioa (p. II,
Third scenario, non-parametric I1. For this scenario, choose & be global packing set of the decision space II, so K = MM(p. II, c). Applying this selection of set, and using Equation 4 we have that
BR (T)
1
1 :()
(14)
cT
2
log M(p [T,
Applying Theorem 3.3 we have that T(V; Hr) S infs>o (1og.N (p, vō) + Tō) Sub- stituting this back into Equation 14
BR (T) TT
1 + inf i
(log N (1. + Tō
1
2
C.3 PROOPS FOR ADDITIONAL LOWER BOUNDS
Proposition C.1. For any algorithm,, there exists a Bayesian decision-makee maaiing task with a finite decision set and single context (|C = 11) such that the regret can be lower bounded by Sy [T)..
Proof. We focus the set AIII) and note that it is parametric set. We also see that for all stochastic decisions Φ, vb E (II) we have that
(llum( C) - par (th, C) = ol +111.
for some positive constant c. Hence, this scenario, we can take p(x, = c||x v1h It convenient to denote K = [II]. Thus, using scaling argument,
log. 1 (p. A(T), e) = log From the definition local packing number, we have that
Vol(BB - Vol(BR (( (c/2))
log M M c/c) 2 log
2c 2 (K 1olog
K - 1.
Substituting this into Equation 7 we obtain that
BR' (T)
1 + 2A.2T
C
K
Now, select maximize such that our lower bound will be the tightest. In particular, choose K-1 which yields the following lower bound,
GTA
1
T(K
2
1
BR (T)
2
K
This concludes proof.
16

---

Published as a conference paper at ICLR 2025
The results for multi-armed bandits and tabular MDPs are shown by substituting [[] K and HSK respectively.
Proposition C.2. For any algorithm, there exists Bayesian decision-making task with II C By where the reward means are a linear function of the decisions, such that the regret can be lower bounded by S2( (dT).
Proof. Similarly to Proposition C.I have p(z, y) c||ar vll for some positive constant c O. We focus on the set BB and note that is parametric set. Furthermore, using Lemma B.1 we have that
log M (p. TB c) 2
Substituting this into Equation g
we obtain that
BR (T)
+ 2
TT
d
Now, we select to maximize such that our lower bound will be the tightest. In particular, we choose GTA which yields the following lower bound,
1
Td
2
1
BR BR
2
6A
d
This concludes our proof.
In the Lipshitz bandit setting, II is some metric space with metric and M = My, where
F= [ II + [0, 1]l/ is 1-Lipschitz w.r.t p}-
Unlike the previous settings, we note that the decision set is not parametric this time. We now prove lower bound for this setting.
Proposition C.3. The regret lower bound for the Lipschitz bandit is Ω (T such that
d+l
where d is chosen
6 S (p, d S
Proof. From the assumption, the covering and packing number be bounded by
2 (ove
4/2
2
log.V
p %
11 s
02
logM(p, IT) 2 or
Substituting this into Equation 9
BR" (T)
d/2
1 1 c2
+ T8
el
2
2
We choose 8 TT'- C2
This yields that
BR (T)
1
1 - (1 2(202) -
ed
ET
2
Selecting ed = (14/202) sts rots
yields
BR (T)
2
cT
Now, cT 2 2 have that
BR (T) 2 $
17

---

Published as a conference paper at ICLR 2025
We now present the following theorem, which shows that the worst-case Bayesian regret is equal to the mixi-max frequentist regret.
Theorem C.4 (Theorem of Lattimore & Szepesváni (009)).
inf sup max E m Plomrr ell
(rx(*") - (2 = sup inf max E (m)) Ell
Σ (r
This theorem then states that, without any constraints on the prior, the worst-case Bayesian regret equal the mini-max regret. This means that any lower bound derived for the Bayesian regret can also be applied to the frequentist one.
C.4 ADDITIONAL EXPLANATION
We now provide an additional explanation regarding Proposition 3.4 In particular, explain why we had to select local packing set for parametric decision spaces II and why we focused on the simplex of the decision set for finite decision spaces.
Selecting AIII over II. This explanation is rather straightforward. We see that by selecting we have that M (p. II, c) 1 for any value of which makes the lower bound null.
Selecting a local-packing set for parametric II. This decision stems from the improved upper bound of [VV Hr) for parametric decision space, which is found in Theorem 3.3 Using the other upper bound for I(V:H, simply results sub-optimal lower bound. Additional details can be found in Yang & Barron 1999).
D PROOFS FOR SECTION
We begin by stating and proving the following Lemma. Lemma D.1. Under the assumptions and notations of Proposition
the constraint of [(T HT) S R S log K, and the regularity Assumption 3.1 the following holds.
3.2
R
I(V: < 2AT
2
log K
Proof. The proof follows a similar analysis to the proof Theorem 3.3 which is provided in Yang
& Barron (1999. Since focus parametric we consider a local packing set with cardinality of lo ((I)), which we denote by E. E is the set contained by E under the mutual information constraint,
( I HT) R).
We now have
I(: Σ ILV:Ci+t. Hi)
Σ DKL (VIHT || pvvi)))
T max DKL (Pi || P2)
PrPE
R
T
max DKL. (Pi P2) log K P.PEE
< TT A
max p(P,, 2
log K P.PEEE
R
Ac2
log K
where the second inequality follows from a scaling argument, and the last follows from the fact that E is local packing set.
18

---

Published as a conference paper at ICLR 2025
As corollary from Lemma D.1 obtain the following.
Corollary D.2 (Proposition defined in Section 2
Let there be a Bayesian interactive decision-making problem as with jinite decision space 11, where [11| K. Then,
BR BR*(T) Te
2
log +1
1
log, Mio (p, e(II),
Furthermore, if the decision-making problem is a part of a parametric set, then
BR*(T)
BR (T)
1
log 2 +
R
Te
2
log M (p, e),
Proof. The proof follows immediately by utilizing Lemma D.1 and using the fact that in this sce- nario, p(z, v) = || vll,. similarly to the proof of Proposition C.1
D.1
PROOF OF PROPOSITION[4. 4.1
Proof. We start by considering 0. From Lemma 4.2
TT
BR (T)
2
for any e > such that lower bounds the difference between two different decisions. Since the maximal difference between two decisions is L, we set e = and obtain the linear lower bound,
T BR (T)
1
2
K
We now consider R O. We denote the polytope space with the mutual information constraint by Ag. Similarly to the proof of Proposition C.1
log M loe
(p. () (K 1).
Substituting this into Equation
10
BR (T)
21 A R e² +
Tog K
Te
2
(K - 1)
Selecting c
(K (K-1) log
we now have that
GRTA
1
TK FKlogh K
2
BR'
2V
6RA
K K-1
We present the proof for the linear case. Now,
log Mloc
(p. II, c) d.
So have
BR (T)
1
2T Ac log
Te.
d
Selecting e
dlog K GRAT
have that
1
Tdlog K
(
1
BR* BR*(T)
2 6RA
d
Proposition 4.1 can then be applied directly on the MAB setting.
Corollary D.3. Consider Bayesian MAB with K arms. If T(x"; HT) 0 then the worst-case
regret is linear. Otherwise, for T(x" ;Hr) 2 0, the worst-case regret can be lower-bounded by
Q
TK log Additionally, if TBd and the reward means are linear functions of the deci- H [or
sions, we have a lower bound of (V Td [(r
19

---

Published as a conference paper at ICLR 2025
D.2 PROOF OF PROPOSITION 4.3
Proof. We consider the following two algorithms. The first is Thompson sampling, which means that, Pt = pr I" The second algorithm is Thompson sampling with the constrained observations O such that [x=;; Hr) = DKL | |Hr pr = R, where H, is the history with constrained observations. Now, we define the information ratio for both the normal and constrained variants of Thompson sampling:
Pt (T (C.). (Pe, Ci)I
Bir (x" (Ct), (pe. C.)1 H6)
Pr.
1( Oc+1 H4)
We see that
1 O.+1 (l,)
Pt
I( Os+1 (H4)
I(x"; 0.+1 Hl,)
log K
where the inequality follows from 1(T=; Os41 Hi) S log K. Thus,
log K
max max Pe max max
Pt.
DEL ( || px (Pto
log K
R max
K log K
2R
Where the third inequality follows by the information ratio upper bound presented by Russo & Van Roy (016). If the MAB is linear then the information ratio Pt can be upper-bounded by 2- Then, we have the following upper bound,
g.
max PL S dllog K
2R
Now, by the analysis done by Russo & Van Roy 2016), we know that max, Pe. I ý for all t, then the Bayesian regret can be upper bounded by
BR (T)(T) S PTlog K
Thus, we have for K-MAB:
KT
BR' (T) < log
2R
And for linear bandits:
dT
BR*(T) < log K
2R.
D.3 PROOF OF PROPOSITION 4.5
We begin by stating and proving the following Lemma.
Lemma D.4. Let Pt, Pz be two priors such that H (PT') = R. S. log K. Also let vh, ó be two
decisions such that DEL (1b) || PT 2 cAR and DKL (6 || P < log K. Then,
Jum (,, - Mas (vb C)]
R TTg K
> 2,
Ep, (MM(( (TT",
(T², ,C) (M( (b, C)]
20

---

Published as a conference paper at ICLR 2025
Proof. By the regularity assumption, we know that
(Ep,luss(T C) - MM((, (M((,))))* 2 cR
2
From Pinsker's inequality,
(Erglus(T' C) Mas (2. C))) 2DkL (6 Ps
log K.
Dividing these two inequalities yields
(Ep, ( C) - JM (1b, C)))
2 4c R log K
EEp (M* C) Mas (0, C)]}
which concludes our proof.
Now, we prove the following Proposition.
Proposition D.5. Let be a prior with H(x") )- = R S log K. If Assumption 4. holds, then
cR
BRp(T; (prt) 2 2/ log K
BR (T).
(15)
Proof. We see that
(Rr(T:p()
Erlus (T"", ,,) pa (pe, Ct)
T
2 2 log K
R
Σ
Euluxe( Ci) - Mwr(,, Ci)
t=1
for any prior and stochastic decisions pt such that DEL (p/ v**)) I logg K. So we can take the worst-case regret,
T
BRP(Tip:) 2 2/
c max
inf (rillla )log K
EuluM (TT, Cc) pM Ct)
log K
1=1
R
2 2/
inf Σ Ey [u Ct) (c)--M((''s Ct) (x))
"oo K
R
2/ log K
c
BR (T)
BR
where the second inequality follows by removing constraint on the available decisions.
This results in the following Corollary.
Corollary D.6 (Proposition 4.5) Let there be K-MAB. Then for any algorithm such that
DKL (pe p=*) 2 cT"( the regret can be lower-bounded by Ω
KH(a')T log K
Addition-
(V
ally, if the MAB is linear, then the regret can be lower bounded by Ω
aH(aa)TT log K
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 pt selects the optimal decision R²" with prob- ability - 5. Then,
DKL (p: p=*') 2 (1 -0)((()) C5
where C$ aas 8
21

---

The mutual information for the experiments in this setting is estimated using the KL diver- gence between the output probability distribution of every algorithm with the prior probability, DKL Pr Pr)) This is an estimator of the mutual information, similar to the one used by Seldin et al. 2011). The mutual information was then calculated according to DKL (pt p*"), where Pt Published as a conference paper at ICLR 2025
Proof. We can write that
PT(
DKL. (e || pa))
= E Σ (t( log
p (ST)
1 δ P (TT*)
2 Ep
(1 5) log
- (TT))) - (1 (1-6)log log
1- 8
where the second inequality follows from the fact that (T -
From this, we can conclude that any algorithm whose stochastic decision round converges to the optimal decision obeys the assumption.
E BANDIT EXPERIMENTS
E.
ADDITIONAL DETAILS
is the real posterior. In our problem, the posterior update is done the following manner.
P(H, ())
P( = =
P(H4)
P(H. ()P(()
Σ, P(He ()P(()
where
P(H: (i)
1 +
No.
N
II
1--
Ne.
+
N15
2
2
2
2
jæl
and No, the number of successful pulls (pulls that received reward 1) of arm Nys is the number of failed pulls of arm i.
2.07
2.07
1.01
1.01
14utual Information
2.0
30
Regret
1.5
20
1.0
10
0.0
200
400
600
800
1000
0
200
400
600
800
1000
Episodes
Episodes
(a) Bayesian regret
(b) Accumulated information
Figure 3: (a) The Bayesian regret and (b) the accumulated information in bits for Thompson sam- pling under three different priors over the same bandit structure. The entropy each prior is de- scribed in the legend. The shadowed areas correspond to 2-sigma error bars.
22

---

Published as a conference paper at ICLR 2025
Question
<Question prompt>
You are given the following question:
Why the sky blue?
These are the possible answers:
A. Because the molecules that compase the Earth's atmosphere have a blue-ish color.
B. Because the sky reflects the color of the Earth's oceans.
C. Because the stmosphere preferentially scatters short wavelengths.
Because Earth's atmosphere preferentially absorbs all other colors.
<End prompt>
Figure 4: The prompting done for the LLMS in our experiments. The question is preceded by 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.
In both bandit experiments, used 200 random seeds. Each random seed considers both the randomness in the problem generated (since the bandit problem is generated via 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 err = 2a where a is the standard deviation and is the number of seeds.
vn
E.2 ADDITIONAL EXPERIMENTS
We use the same bandit setting as in Section In this experiment, we compare the regret of Thomp- son sampling under three H H(x") values. We use the same model space and number of arms. Results are presented Figure suffered.
As we can see, when less information can be accumulated, less regret is
F MCQA WITH LLM EXPERIMENT
F.1 ADDITIONAL DETAILS
In this experiment, we used a small LLM and large LLM in every experiment. The small LLM was one of the following: Mistral 7B (Jang et al. 2023). Gemma 2B (Team al. (0244) and Falcon 7B Allazrrouei et al. 2023). For the large LLM we used Mixtral 8x7B (Jiang et al. (024)) Llama3- 70B AI@ Meta 2024) and Gemma 7B (Team al. (024). 4-bit quantization (Dettmers & Zettlemoyer 2023) and flash attention (Dao et al. 2022) were applied for all models (excluding Falcon 7B, for applied). In every round, queried the LIM 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 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.
which flash attention
Table 4: Regret for different seeds for random and bits-based policies 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 + 0.3
47.0 1.5 0.5
40.4 0.3
36 + 1
46 = 1
40 10:1
Gemma 2B
0.7
54.1
39.3 0.3
38 + 2
46 = 2
35.3 0.9
Falcon 7B
0.3
52.2
45.5 + 0.3
05.0
44 = 1
39 +
23

---

Published as a conference paper at ICLR 2025
Table 5: Regret for 10 different seeds for random and bats-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 + 0.4
33.8 = 0.4
34.8 = 0.3
26.6 = 0.8
31 =1
33.0 + 0.8
Gemma 2B
35.6 0.8
40.1 0.6
32.9 0.3
32 + 1
36 2
30
Falcon 7B
34.0 + 0.3
37.0 + 0.3
37.9 + 0.2
27.0 + 0.7
31 = 1 33 +
We repeated this process for 10 different question seeds. Table reports the regret after 200 steps for all combinations of LLMs across all 10 seeds. Additional results presented in Tables 4 and Both tables compare the random selection method and the bits-based one 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 also that bits-based selection becomes more significant, as the performance gap between the small and large LLM increases well.
the bits-based policy increases with the deployment rate of the large L.M.. Furthermore,
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 ma- chine with RTX4090. The experiments using Mixtral 8x and Llama3-700 were performed using machine with 3xA40.
F.3 DATASET AND MODELS LICENSE
The MMLU dataset (Hendrycks et al. 2021b is available under the MI7 license. Mistral 7B (Jang al. 2023), Mixtral 8x (Jiang et al. (2244) and Falcon 7B (Almazrouei al. (023) are available
under the Apache license 2.0. Gemma 2B and 7B (Team et al. (224) are available under the Gemma
license. Llama3-70B @ Meta 2024) available under the Llama license.
F.4 LLM PROMPTS
We now describe the different prompts for every LLM.
F.4.1 MISTRAL AND MIXTRAL.
Prompt for generating answers for Mistral 7B and Mixtral 8x7B
You will answer the following question using one of the following letters, A, B, C, D. Do not explain or describe the answer. You are given the following question:
< =uesttin>>
The possible answers are:
A. <Option A
B. <Option B>
C. <Option C>
D. OOtion D>
Please output only the letter corresponding with the correct answer A, B, C D. Don't explain or describe the answer.
Your answer:
24

---

Published as a conference paper at ICLR 2025
F.4.2 LLAMA3
Prompt for generating answers for Llama3 8B 70BB
You are a bot that only outputs one the following letters A, B, C or D. You are designed multiple choice questions. Do not explain describe the answer.
Question: You are given the following question: Question
The possible answers are:
A. <Option A>
B. <Option B>
C. <Option C>
D. <Option D>
You must output only the letter corresponding with the correct answer A, B, or Don't explain or describe the answer.
Output:
F.4.3
FALCON
Prompt for generating answers for Falcon 7B
You are an AI assistant designed to answer multiple choice questions. You will answer the following question using one of the following letters, A, B, C, or D. Do not explain or describe the answer. You are given the following question:
<Question>>
The possible answers are:
A. <Option A>
B. <Option B>
C. <Option C>
D. <Option D
Please output only the letter corresponding with the correct answer A, B, C or D. Don't explain or describe the answer.
Your answer:
F.4.4
GEMMA 2B/ 7BB
Prompt for generating answers for Gemma 2B 7BB
<start_of. Sftart_of..um>>uu user
You will answer the following question using one of the following letters, A, B, C. or D. Do not explain or describe the answer. You are given the following question: <Question>>
The possible answers are:
A. Optiion A>
B. <Option B>
C. <Option C>
D. <Opttin D>
Please output only the letter corresponding with the correct answer A, B, C D. Don't
explain or describe the answer.<end.og tumn
25


Reviews:
[{"review_id": "b90eqB53zF", "reviewer": "Reviewer_oZWy", "summary": "This paper studies regret minimization when extra information about the prior is revealed. \nIn 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.\n\nThe 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.", "questions": ".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem formulated in this paper seems interesting, and it is interesting to see how information affects learning in general. \nThe paper also companies its theoretical results with experiments.", "weaknesses": "The technique is not the strong part of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wMJnVrPhJt", "reviewer": "Reviewer_6gEU", "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. \nFor brownie points, they show an application of their theory to question answering with LLMs.", "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?\n- Could the authors comment on extensions to settings where the information depends on prior actions?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper presents an interesting information-theoretic approach to quantifying the regret-information trade-off\n- The theoretical approach is rigorous, with clear definitions and proofs\n- The paper is well-organized\n- The paper holds high significance for fields involving sequential decision-making (online learning in particular)", "weaknesses": "- The assumption regarding information gathering being independent of task history could limit applicability in some environments", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PldUMupBC2", "reviewer": "Reviewer_smVV", "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:\n1. Develops new information-theoretic methods for analyzing sequential decision-making algorithms\n2. 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).\n3. Obtains lower and upper regret bounds which depend explicitly on the number of bits of information accumulated.\n4. Runs a question-answering LLM experiment inspired by the above results.", "questions": "I don’t have further questions beyond what I’ve written above in “Weaknesses”.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 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.\n\nAlthough 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).\n\nOverall, I think the ceiling for this paper is quite high.", "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:\n1. Confusing writing and non-standard terminology. \n2. Lack of explanation of the technical statements.\nI have provided a non-exhaustive list of examples below.\n\nAlthough 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.\n\nI 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.\n\nOverall, 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.\n\n_Writing issues_\n1. 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.\n2. 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.\n3. 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.\n4. 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.\n\n_Lack of interpretation/explanation_\n1. 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.\n2. Theorem 3.4, especially (9), is a bit hard to make sense of. Could you provide an interpretation for this expression?\n\n_Minor issues_\n1. 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?\n2. Since Section 4 also includes upper bounds, should the title be “Information-theoretical regret upper and lower bounds?”\n3. Table 2 caption: the “Appendix ??” reference is broken", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qkvC9rwAp5", "reviewer": "Reviewer_z6VF", "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.", "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.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n- Moreover, Prop. 4.5 provides an entropy-dependent Bayesian regret lower bound, which is listed in the last entry of Table 1.\n- The advantage of accumulating information in bits is experimentally justified (Figure 2).\n- 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.", "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.\n- (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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)