  In interactive decision-making tasks, information can be acquired by direct
interactions, through receiving indirect feedback, and from external
knowledgeable sources. We examine the trade-off between the information an
agent accumulates and the regret it suffers. We show that information from
external sources, measured in bits, can be traded off for regret, measured in
reward. We invoke information-theoretic methods for obtaining regret lower
bounds, that also allow us to easily re-derive several known lower bounds. We
then generalize a variety of interactive decision-making tasks with external
information to a new setting. Using this setting, we introduce the first
Bayesian regret lower bounds that depend on the information an agent
accumulates. These lower bounds also prove the near-optimality of Thompson
sampling for Bayesian problems. 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.
