CIF: Small: MAB with Querying and Cost Information

Many real-world problems involve choosing among several options over time, with the results of earlier choices helping guide later ones. For example, a manufacturer may choose among different inspection or testing procedures for detecting product defects, and learn from past inspections which procedures provide reliable quality control. A cybersecurity service may choose among different levels of screening for network activity, and learn from past cases which checks are most useful for detecting potential threats. Classical approaches often focus on identifying and choosing the action with the highest expected reward. However, many important applications require richer forms of decision making. In some settings, a decision maker can obtain partial information about an action’s outcome before committing to it, for example through a test, simulation, or preliminary evaluation, but obtaining such information may incur an additional cost. In other settings, choosing the action with the highest reward may be unnecessary or too expensive; instead, the goal might be to identify the least costly option that attains a desired level of reward. This project will develop new mathematical foundations and algorithms for these settings. The expected results will improve the efficiency and reliability of data-driven decision making in areas such as health care communications, machine learning model selection, recommendation systems, and wireless communications. The project will also contribute to education and workforce development through graduate student training and integration of research results into courses. This project will study new formulations of multi-armed bandit problems motivated by applications where information acquisition and decision costs play a central role. The project will develop new algorithms for bandits with querying, where it is possible to obtain information about an action’s outcome by paying a cost before deciding which action to play, and for bandits with cost information, where the objective is to minimize decision cost subject to attaining a prescribed reward threshold. The project will also investigate extensions involving combinatorial decision spaces, structured reward models, noisy probes, and formulations that combine querying with cost-aware objectives. The performance of the resulting algorithms will be analyzed rigorously through regret guarantees and compared with fundamental limits established through lower bound analysis. The algorithms will also be tested and validated using real or high-fidelity datasets to assess their empirical performance. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.