  In most real-world settings such as recommender systems, finance, and
healthcare, collecting useful information is costly and requires an active
choice on the part of the decision maker. The decision-maker needs to learn
simultaneously what observations to make and what actions to take. This paper
incorporates the information acquisition decision into an online learning
framework. We propose two different algorithms for this dual learning problem:
Sim-OOS and Seq-OOS where observations are made simultaneously and
sequentially, respectively. We prove that both algorithms achieve a regret that
is sublinear in time. The developed framework and algorithms can be used in
many applications including medical informatics, recommender systems and
actionable intelligence in transportation, finance, cyber-security etc., in
which collecting information prior to making decisions is costly. We validate
our algorithms in a breast cancer example setting in which we show substantial
performance gains for our proposed algorithms.
