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

Authors: Itai Shufaro, Nadav Merlis, Nir Weinberger, Shie Mannor
Primary area: reinforcement learning
Keywords: Online learning, Information theory, Bayesian regret, Bandits

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.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 6

Reviews and discussion:
<thread>
creation date:
1730634903430

thread_type:
official_review

<thread_object>
creator: reviewer_z6vf

<content>
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.

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.

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?

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730687569176

thread_type:
official_review

<thread_object>
creator: reviewer_smvv

<content>
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.

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.

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

questions:
I don’t have further questions beyond what I’ve written above in “Weaknesses”.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730830690394

thread_type:
official_review

<thread_object>
creator: reviewer_6geu

<content>
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.

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)

weaknesses:
- The assumption regarding information gathering being independent of task history could limit applicability in some environments

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731300878509

thread_type:
official_review

<thread_object>
creator: reviewer_ozwy

<content>
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.

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.

weaknesses:
The technique is not the strong part of this paper.

questions:
.
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.