Information Acquisition Under Resource Limitations in a Noisy Environment

Matvey Soloviev, Joseph Y. HalpernAAAI 2018 · DOI

Introduction

In real-world scenarios, information acquisition is rarely free or perfect. Whether an animal is foraging for food or an automated sensor is monitoring a complex environment, agents must often make critical decisions based on noisy data while operating under a strict resource budget. This research, originally presented at AAAI-18, explores the mathematical foundations of "smart" information gathering. It provides a formal framework to explain why rational agents frequently choose to ignore relevant information—a phenomenon known as Rational Inattention (RI)—to focus their limited resources on a subset of variables.

The Information-Acquisition Game

The authors model the challenge of optimal resource allocation as a game against nature. An agent aims to determine the truth value of a Boolean formula $\phi$ given a budget of $k$ noisy tests. Each test on a variable $v_i$ returns the correct value with a certain probability, and the agent's strategy is represented as a decision tree.

Finding the absolute optimal strategy is computationally intensive, categorized as $\Sigma_2^p$-complete. To analyze the problem at scale, the researchers utilized Linear Programming (LP) to identify optimal test sequences across thousands of logical formulas. They also proposed a "random-test heuristic," proving that if a positive payoff is possible, this simple approach will eventually find it, providing a robust fallback for agents in complex environments.

The Prevalence of Rational Inattention

A core finding of the study is that Rational Inattention is not just a cognitive bias but often the mathematically optimal strategy. For instance, in a disjunction like $v_1 \lor v_2$, an agent with a limited budget and noisy sensors might achieve higher certainty by testing $v_1$ repeatedly rather than splitting attention between $v_1$ and $v_2$.

To quantify how common this behavior is, the authors analyzed exhaustive sets of logical equivalence classes for formulas with up to 4 variables and sampled 4,000 formulas for each $n$ from 5 to 9.

Prevalence of Rational Inattention for formulas with 1 to 4 variables.
Statistical estimates of Rational Inattention for formulas with 5 to 9 variables.

The data indicates that at least 15% of all Boolean formulas exhibit RI. When applying the "Noise Transfer Conjecture" (NTC), which suggests that noise in one variable can be effectively transferred to others in certain logical structures, the prevalence of RI jumps to approximately 30%.

Concept Hardness and the XOR Peak

The research also introduces a new measure of "test complexity" to rank logical concepts. A significant insight is the identification of XOR (parity) functions as the hardest concepts to verify. In an XOR operation, every variable is essential; missing information on a single variable leaves the agent with zero knowledge about the final truth value.

Interestingly, this mathematical complexity aligns well with cognitive psychology studies on human concept learning, with one notable exception: humans tend to find small XOR problems easier than the model predicts. This suggests a distinction between the effort required to "work with" a known concept versus "learning" it from scratch through noisy observation.

Conclusion and Future Work

While the current model provides a rigorous foundation for understanding resource-constrained information gathering, it faces challenges in computational complexity for very large formulas. The authors also note that their definition of Rational Inattention is quite strict; a more relaxed definition would likely reveal RI to be even more widespread. Future research directions include extending this framework to multi-agent systems, where collaborative agents must decide how to divide labor and share information to efficiently learn complex logical formulas.

Summary updated

BibTeX
@inproceedings{soloviev2018information,
  author = {Matvey Soloviev and Joseph Y. Halpern},
  title = {{Information Acquisition Under Resource Limitations in a Noisy Environment}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12122},
}
Figure