2024/05/26 by Itai Shufaro, Shufaro, Itai, Nadav Merlis +5
Decision Sciences · Mathematics · #Auction Theory and Applications #Benford’s Law and Fraud Detection #FOS: Computer and information sciences #Machine Learning (cs.LG) #Stock Market Forecasting Methods
paper · pdf · doi:10.48550/arxiv.2405.16581
openalex publication_date 2024/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
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.