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

We want to thank the reviewer for the detailed analysis and feedback. Below is a response addressing your concerns:

(W1) We acknowledge this gap and agree it would be interesting to close it. Still, in settings where $K$ is small, as in many MAB problems, this factor is not too significant. In particular, many works that study problem-independent regret ignore log-factors. Moreover, the bound still gives non-trivial insights, especially concerning the relationship between information and regret.

(W2) The techniques in this paper include the adaptation of the method presented by [Yang and Barron, 1999] to an online setting. This includes utilizing covering and packing numbers to introduce a regret lower bound. One contribution we introduce is the selection of $\Phi$ for different policy classes, allowing us to obtain tighter lower bounds for a wide variety of decision spaces. Another technical contribution is modifying this method to handle problems with information constraints.

(Q3) Allowing the agent to adaptively determine when to query external sources for information is a very interesting setup. While it is outside the scope of this work, we will hopefully examine it in future work.

We appreciate the reviewer’s feedback and have addressed the issues raised. We uploaded a revised version of the paper, where the modifications made are highlighted. Below is a response addressing your concerns:

Regarding your concerns over the LLM experiments, querying the large LLM only is not the optimal policy. This is due to the 0.1 penalty, making the small LLM better than the large one for some questions. However, choosing the large LLM only will be better than both policies – since our focus is when queries are constrained. We have also added the baselines of using only one model to Table 2.

Writing issues

1. We have modified the introduction to briefly introduce the setting before the contributions. We also added references to the appropriate Theorems / Propositions in this section.
2. In our denoting of $\pi$ as a decision and $\Pi$ as a decision set, we will further emphasize that we follow the notations of papers on decision-making settings, e.g. that of (Xu and Zeevi 2023, Foster et. al. 2023). $\pi^*$ is a different type than $\pi$ as it is the optimal decision for every context. However, we changed $\pi^* : \mathcal{C} \to \Pi$ to $\pi^*_{M,C} \in \Pi$ to be less confusing. We also changed our notion of $p_t \in \Delta(\Pi)$ from policy to stochastic decision. We also changed the term $\epsilon$-local set to $\epsilon$-ball to better align with existing terminology.
3. Bernoulli rewards were chosen mainly for simplicity of exposition. Our setting also covers general rewards as well. We added this comment to the paper as well.
4. While Proposition 3.2 requires this assumption to hold only for the decisions in $\Phi$, for Theorem 3.4 to hold $\Phi$ needs to be a packing set. Hence we assume separation for all stochastic decisions. This is not a strong assumption since it essentially entails that any change in our decision entails a change in the mean reward on average. This is why for MAB problems, this assumption holds for $\rho(\phi,\psi)=c\|\phi-\psi\|_1$ where $c>0$ is some constant that depends on the structure and prior (but independent of $\phi,\psi$).

Lack of interpretation / explanation

1. This assumption means that there exists a small enough $\epsilon_0$-ball around every decision $p_1$ such that for any $p_2$ in this ball, the KL divergence is bounded by the norm $\rho$. This is essentially a regularity assumption over the decision space that prevents from the KL divergence to blow-up, which, in turn, can be obtained by requiring that $p_1$ and $p_2$ do not become arbitrarily small on their support. We have added further explanation on this assumption in the paper as well.
2. Theorem 3.4 is obtained by substituting the bounds of Theorem 3.3 and the previously described selection process into Prop. 3.2. The last expression uses a general upper bound for $I(V;H_T)$ (which is the expression with $\mathrm{inf}_{\delta}$ ) and selects $\Phi$ to be a packing set of $\Pi$. The other two expressions use a different upper bound for $I(V;H_T)$, which utilizes the fact that we focus on a local packing set instead.

Minor Issues

1. Thanks for the suggestion, we agree and changed the example to exclusively stick with an example of an online agent with access to a language model.
2. We have fixed the title.
3. We have fixed the reference to the Appendix.

We hope that we have addressed your main concerns and if there are any other issues, we will gladly correct them.

We want to thank the reviewer for the detailed analysis and feedback. The following is a response addressing your concerns:

(Q1) Since in non-Bayesian settings, there is no prior distribution, the mutual information $I(\pi^*;H_T)$ is not well defined, since it requires knowing the prior and posterior distributions. One possible way to extend this definition is to consider a constraint on the worst-case information gain at every step, $\min_{P}D_{KL}\left({P_{\pi^* \mid\pi,C}} ,{P_{\pi^*}}\right)$.

(W1 + Q2) We agree that scenarios, where the collected information depends on previous actions, is an exciting future direction (as we mention in the conclusions section). One potential way to formulate this is by assuming that the contexts are sampled from a posterior distribution. That is, before an agent starts his/her interactions, the model $M \sim P$ is sampled and then the context $C_t$ is drawn from $C_t \sim P(\cdot \mid M,{\mathcal{H}}_t)$. The results presented in our paper can be relatively easily extended to this setting. However, this setting introduces different interesting questions. For example, should an agent in an online task explore a "bad" path to gain valuable external knowledge about a different one?

We want to thank the reviewer for the detailed analysis and feedback. The following is a response addressing your concerns:

(W1) The techniques in this paper include an adaptation of the method presented by [Yang and Barron, 1999] to an online setting. This includes utilizing covering and packing numbers to introduce a regret lower bound. We then introduce a modification of this method to handle problems with information constraint.