Cost-Efficient Online Decision Making: A Combinatorial Multi-Armed Bandit Approach
Authors: Arman Rahbar
Niklas Åkerblom
Morteza Haghir Chehreghani
Venue: Accepted by TMLR ()

Abstract: Online decision making plays a crucial role in numerous real-world applications. In many scenarios, the decision is made based on performing a sequence of tests on the incoming data points. However, performing all tests can be expensive and is not always possible. In this paper, we provide a novel formulation of the online decision making problem based on combinatorial multi-armed bandits and take the (possibly stochastic) cost of performing tests into account. Based on this formulation, we provide a new framework for cost-efficient online decision making which can utilize posterior sampling or BayesUCB for exploration. We provide a theoretical analysis of Thompson Sampling for cost-efficient online decision making, and present various experimental results that demonstrate the applicability of our framework to real-world problems.

Published in Transactions on Machine Learning Research (01/2025)
Cost-Efficient Online Decision Making: A Combinatorial Multi-Armed Bandit Approach
Arman Rahbar'
armonn@chalmers.see
Chalmers University of Technology and University of Gothenburg
Niklas Åkerblom"
Voluo Car Corporation
Chalmers University of Technology and University of Golhenburg
Morteza Haghir Chehreghani
mortem..ceeerggnnn@ddddaeeee..e
Chalmers University of Technology and University of Gothenburg
Reviewed on OpenReview: https: // oppnrevvee.. net/ forum? id- eZGZI1geGA
Abstract
Online decision making plays a crucial role in numerous real-world applications. In many scenarios, the decision is made based on performing sequence of tests on the incoming data points. However, performing all tests can be expensive and is not always possible. In this paper, we provide a novel formulation of the online decision making problem based on combinatorial multi-armod bandits and take the (possibly stochastic) cost of performing lests into account. Based on this formulation, we provide a new framework for cost-efficient online decision making which can utilize posterior sampling or BayesUCB for exploration. We provide a theoretical analysis of Thompson Sampling for cost-efficient online decision making, and present various experimental results that demonstrate the applicability of our framework to real-world problems.
1 Introduction
Online decision making (ODM) is concerned with interactions of an agent with an environment through a series of sequential tests in order to acquire sufficient information about the environment and successively learn how to make better decisions. Each such test and decision can be associated with either a reward or a cost. Here, we focus on problem scttings where tests may incur stochastic costs.
One such example medical diagnosis. A patient arrives at hospital with unknown alliction. In order to determine appropriate treatment for the patient, number of medical tests need to be performed. Since cach of these tests might take time (which can differ depending on the test result and the underlying aflliction), be expensive or cause discomfort to the patient, it is desirable to limit the set of tests to the most informative ones. On the other hand, it is apparent that misdiagnosing the patient can have severe consequences, so performing too few tests also undesirable.
Another example is adaptive identification of driver preferences for in-car navigation systems. Consider the selection of charging stations during long-distance trips with battery-electric vehicles (BEVs). Since the duration of a single charging stop can be as long 40 minutes, it may be desirable to select charging station with additional amenities in close proximity, such as restaurants, shops, or public restrooms. While it is possible to ask questions through the vehicle user interface of drivers to learn their charging location
TThee authors contributed equally to this work.

---

Published in Transactions on Machine Learning Research (01/2025)
preferences, such questions should be kept few, short, and simple. We note that in both of these examples, the problem instances (e.g., diagnosis of patients and identification of driver preferences) arrive incrementally in an online manner and should be processed accordingly.
We take a novel view of the online decision making problem described above, where we cast it as a combi- natorial multi-armed bandil problem (CMAB) (Cesa-Bianchi & Lugosi 2012], an extension of the classical multi-armed bandit problem (MAB). The standard MAB problem is a common way of representing the trade-off inherent to decision making problems between exploring an environment by performing successive actions (playing arms, in bandit nomenclature) to gain more knowledge and exploiting that knowledge to reach a long-term objective. In CMAB problem, an agent interacts with the environment in each time step by performing a set of actions (a super arm), where the set may be subject to combinatorial constraints. Each individual action (bose arm) in that set may result in some observed feedback (so-called semi-bandit foedback), and the agent also receives a reward associated with the complete super arm.
In this work, we view the combined choice of lests to perform and the selected decision as super arm in a CMAB problem where the underlying cost distribution parameters are initially unknown, which allows to leverage effective MAB exploration strategies like Thompson Sampling (TS) (Thompson 1933) and Upper Confidence Bound (UCB) (Auer et al. 2002) together with cost-efficient (active) information acquisition methods, such as Equivalent. Class Edge Culling (RC²) (Golovin et. al. 2010 and Information Gain (TG)
Dasgupta 2005). We summarize our contributions as follows.
1. We study the novel problem of outcome-dependent cost-efficient online decision making, where costs may be stochastic and depend on both test and decision outcomes.
2. We propose a novel combinatorial semi-bandit framework for our online decision making problem. This formulation involves an elegant definition of base arms and super arms, providing new per- spective on cost-efficient information acquisition while simultaneously exploring the concept of interactive CMAB oracles.
3. We adapt a number of bandit methods to this framework, namely Thompson Sampling and Upper Confidence Bound, combined with novel extensions of EC² and IG which can handle tests with different and stochastic costs, which we call W-FC2 and W-TG, respectively. Thereby, in addition to Thompson Sampling, we develop W-EC² and W-1G oracles utilizing a Bayesian variant of UCB (called UCy by Kaufmann et al. 2012) that fits well to our framework and enables the UCB method to effectively employ prior knowledge in the form of a prior distribution.
4. We demonstrate the effectiveness of our framework via several experimental studies performed on data sets from a variety of important domains. We find that Thompson Sampling yields the best performance in most of the experiments we perform.
5. We theoretically analyze the performance of Thompson Sampling within our framework for cost- efficient online decision making and establish an upper bound on its Bayesian regret.
2 Related Work
Cost-efficient information acquisition. The primary goal of cost-efficient information acquisition (also called Bayesian active learning in the literature) algorithms to sequentially select from a number of avail- able costly tests to make decision (such as making a prediction about a label) with a minimal cost. To minimize cost, these tests are performed until sufficient level of confidence in the decision is reached. Prominent algorithms for cost-efficient information acquisition are Information Gain (IG) (originally devel- oped by Lindley 1956), 2 (Golovin et al. 2010), and Uncertainty Sampling (US). Bayesian Active Learning by Disagreement (BALD) (Houlsby et al. 2011) proposes an equivalent formulation of the underlying util- ity function in IG which provides practical and computational advantages. EC² has been proved to enjoy adaptive submodularity (Golovin et al.) 2010), and thus yields ncar-optimal cost. Acquisitinn functions Bayesian optimization have also been used in active learning. Probability of Improvement (PI) (Kushner) 1964) and Expected Improvement (FT) (Jones et al. 1998) are two important acquisition functions used in
2

---

Published in Transactions on Machine Learning Research (01/2025)
active learning. Both PI and EI use surrogate models (e.g., Gaussian Processes) to select the next sample
to query (see Di Fiore et al. 2022 for more details). The works of Rahbar et. al. (2023) Chen et al. (2017) consider active information acquistioon in an online setting. The regret bounds in these works are based on formulating the problem as a Partially Observable Markov Decision Process (POMDP) and are exponential in the lotal number of possible lests. In this work, we consider a CMAB formulation of the problem and derive a regret bound that is linear the number of tests (and sublinear w.r.t. the horizon T). In addition,
unlike Rahbar et al. (2023); Chen et al. (2017), our framework supports variability in the cost of the tests depending on the outcomes of the tests and the decisions.
Combinatorial semi- algorithms. CMAB methods have been utilized to address online learning problems in various settings but often without considering cost-efficient information acquisition. Durand & Gagné (2014) adapt a combinatorial variant of Thompson Sampling for online feature selection where the agent has a fixed budget for tests and the reward is a linear function of the test outcomes. Both assumptions are used in later works studying the problem from a CMAB perspective (Bouneffouf al., 2017 2021), but differ from the setting considered in this work (e.g., the budget for information acquisition is fixed with no concopt of achieving decision, and the costs are independent of the outcomes of the tests and the docisions). Wang & Chen (2018) analyze the regret of combinatorial Thompson sampling, but their proof technique is not directly applicable to our problem since they do not allow changes in the set of available super arms. Therefore, in this work, we adopt the approach originally developed by Russo & Van Roy (2014) for standard and linear MAB. Finally, it is notable that the analysis of Wang & Chen (2018) yiclds an instance dependent regret bound, whereas our analysis is focused on deriving Bayesian and instance-independent bounds.
Online decision making. Our work relates to the theoretical online decision making framework presented by Cesa-Biannhii et al. (2021). Their framework aims to maximize total Return on Investment (ROI) in a sequence of decision making tasks, where each task involves accepting or rejecting innovation. The au- thors provide an algorithm to learn ROI-maximizing decision making policies, with thcoretical guarantees of convergence to an optimal policy. In the framework, accept/rejedt decisions are made by drawing i.i.d. sam- ples from a probability distribution modeling the value an innovation. In contrast, our approach involves making low-cost decisions by performing a sequence of different tests (with different costs). Furthermore, our work not limited to binary accept/refe reejet/ decisions.
Algorithm Online decision making protocol
1: f21, }: available tests
[m]: possible decisions
A= = {ayli e [n].j e [m]]: set of base arms
Pij and Mi costs of base arm aij (given test outcomes 0 and 1, respectively)
(0)
(1).
0,3 Pr(x, 1ly j)
2: for t= 1, ..... T do
3: Receive problem instance (()
for all selected tests x:!" (by an oracle) do
5: Observe outcome of test (1( ~ (ernoulli(O.)).
6: end for
7: Make a decision y( = E [m] based on test outcomes.
j 8: Super arm g(t) = {aij Altost xa (t) is performed) E I where I(t) C 2- is set of feasible super arms.
Receive reward R()()) where [[R)) = Evjssw Pig and Ptj = (1) x Oig + (.) x (1 0.y)
10:
end for
3 Problem Formulation
In this section, we propose our new formulation of the online decision making problem which incorporates the cost acquiring test outcomes. In each time step t, we receive the problem instance (e.g., data point) (t) (t)
x()) with tests (z(()) .22 ,..., (......()). Here, we assume that all test outcomes (unknown until after each test
3

---

Published in Transactions on Machine Learning Research (01/2025)
(t) is performed) are binary (i.e.; x; E {0, for all i); but our methods can easily be exlended to other test
values (see Section 6.3). The goal is to make accurate decision yd)) E [m]] for that problem instance with minimal cost of performing tests (m represents the total number of options for the decision, or outcomes if the correct decision is viewed as a random variable), where we denote the correct decision by y². As an example, let's consider the medical problem of diagnosing lung cancer. At each time step L, a patient x()) arrives, and our goal is to make a decision (prediction) yd (1(benign), ( (m 3). In this problem, there are several tests that can be performed to reach a decision. For instance, available tests can include CTH scan, PET scan, genetic lesting and biopsy (n = 4).. These tests can have positive negative outcomes (test results), which will be used in the decision making process.
Consistent with the common Naive Bayes assumption, we let all tests a be mutually independent and Bernoulli-distributal conditional on the decision y The Naive Bayes assumption common for soquential decision making, even in the oflline setting, and is consistent with previous works including Chen el al.] (2017p: Rahbar et al. (023). This assumption is needed for computing the gains in approximate oracles defined in Section 4.1 (W-IG and W-EC*). We also let y" be known given a full realization of x(1). This implies that upon performing all available tests, we know the correct decision for the problem instance. This is realistic and consistent with the settings of Golooin et al. (2010); Chen et al. (2017): Rahbar et al. (2023) though they do not follow a CMAB formulation. As an example, consider a medical diagnosis problem. This property mcans that if we perform all available medical tests, we can determine the correct diagnosis.
Regarding the costs, we assume that they directly depend on the outcomes of the tests and the decisions. As motivation, again consider the medical diagnosis problem. Here, the costs (e.g., time and patient's discomfort) of medical lests can vary based on the underlying allliction the outcome of the test itself. For example, in the case of diagnosing cancer through biopsy procedures, the cost of the biopsy can change based on the specific underlying condition and the outcome of the test. If the suspected cancerous tissue can be accessed easily and shows a positive result for cancer cells, the biopsy procedure may cause lower costs in terms of time and discomfort. Conversely, if the tissue is in a challenging area or requires multiple biopsies, the procedure's complexity may cause higher costs, both in terms of time and increased patient's s discomfort.
We model the problem described above by elegant design of stochastic combinatorial multi-armed bandit (CMAB) problem (Cesa- -isnchi & Lugosi 2012) with semi-bandit feedback. Briefly, CMAB corresponds to a reward maximization problem with a set of base arms. In each time step, the agent seleets a subset of base arms. After playing this subset of base arms, called super arm, the agent receives a reward from the environment. The objective is to maximize the expected sum of rewards within time horizon T,, which is typically formulated as a regret minimization task.
Perform tests
Tasts {a1, 222 223 2
22
431
022
Decisions (1,2}
+
431
0:8
2
d4t
043
Make decision
y 2
Base
A
Super arm S = {azz; 442, 412)
Figure Illustration of base arms and super arms in our problem formulation. In this example, we have four tests (n = 4) and two possible decisions (m 2). Based on these tests and decisions, we have x 2 possible base arms A = {ayli E [4], E [2]]. If we perform tests with indices 2, 4, 1, and make decision y 2 (based on the test results), then the super arm will be S = {a22, 442, .12).
'Computed Tomography
Positron Emission Tomography
4

---

Published in Transactions on Machine Learning Research (01/2025)
In our problem, since the costs of tests depend on both test and decision outcomes, need to consider set of base arms that reflect both. Therefore, we define the set A of m base arms dij (i E [n] and E [m]). In each time step f, the agent selects a super arm S(t) E 2 and receives the reward R(S(t)) ) R( A base arm aij in 5td) indicates that the test with index is performed for making decision y = j (see Figure
We define I ç 24 as the set of feasible super arms at Lime which yield a decision, i.e.; each feasible super arm consists of tests and a single decision (concretely, if dij; aik E S E I((,, then j = k). The feedback at time & of a base arm Oij A (observable by the agent if aij E g(t) is the corresponding outcome of test oi which given a decision y(t) = j is -irtouli-distributed (test outcomes are binary) with an unknown (to the agent) parameter Ozj - Pr(x; - 1/y - j), for all é,j- While tests may, in practice, be selected sequentially, the super arm (and base arms) are only known in hindsight after the decision has been made. This is intentional and allows us to analyze the problem as a CMAB.
(0) We let the cost (assumed to be fixed and known) of each base arm 0ij be 14g E [0, and My E [0, 1] (given test outcomes 0 and 1, respectively). Then, we define the expected reward of the selected feasible super arm 5(t) as the negative sum of expected base arm costs, such that E[[[S(())] = Eieestn May, where
(0) May - Pig 0.5 + +Mg (1 0ty),
(1)
with the vector of all Miy's denoted by l and the vector of all 0.y 's denoted by A. We let μr' be the truc underlying mean cost vector, with corresponding parameter vector 0" This is novel problem; the previous studies are special cases of this problem with pij
(0) p.j c₁ where G is the cost of performing test i and
is independent of test outcome or the decision. We show an outline of our online decision making protocol in Algorithm
We define the suboptimality gap at time t of a feasible super arm S as
1 (S) - fn- fM (S),
(S)
(2)
where (MM _ (- EijEE V() denotes the expected reward super arm M given an arbitrary mean cost vector 7, and S².(1) A argmaxsezie Sy (S) is the optimal super arm found by the oracle applied the feasible set I(t), Then, the regret (which the agent should minimize) for time horizon T is defined as
Regret, 4 (7) A Σ A (S
IE
4 CMAB Methods for ODM
In our framework, utilize oracles (i.e., optimization algorithms) which, given parameter vector 0, output super arms with maximum expected reward (or approximately, in the case of approximate oracles), such that
Oracle () a argmmax ().
(4)
SEZO)
The 0f, values of the true parameter vector 0* are initially unknown, but to be able to employ prior knowledge, we consider a prior distribution over 0t Formally, we assume that each 0G, follows a Beta distribution, (eta(a g.)) The reason is that a Beta distribution defined on range (0, 1), and parameter of Bernoulli distribution should be in this range (cach 8 parameter of a Bernoulli distribution). We also assume a fixed and known distribution over decision outcomes, denoted by P(y) (i.e., the learning agent knows the marginal distribution príorí). However, even if the oracle is assumed to always be able to find the correct decision (i.c., it only needs to minimize the number of tests), the optimization problem is NP-hard, and thus in practice, we use approximate oracles (introduced in Section
A greedy method to address the problem defined in Section 3 is that in each time step t, we use an oracle with the current (MAP) estimate of 0" However, this greody method may converge to a sub-optimal super arm due to lack of exploration. To balance exploration and exploitation, we adapt Thompson Sampling and BayesUCD to our problem.
5

---

Published in Transactions on Machine Learning Research (01/2025)
Thompson Sampling. Algorithm A summarizes framework, with Thompson Sampling used as explo- ration method. In each time step i, we sample the parameters from the current posterior distribution (line 2 We then (in lines 3 use the oracle to get super arm based on the sampled parameters, and perform the tests sequentially. Finally, we use Algorithm g to update the posterior distribution of the paramoters. A Algorithu
3 uses the fact that Beta distribution is conjugale prior to the Bernoulli distributtion
BayesUCB. To utilize BayesUCB for exploration instead of Thompson Sampling, we have to modify lines 3 of Algorithm 2 such that instead of sampling parameters from the posterior distribution, we retrieve optimistic parameter estimates. Like Kaufmann et al. (2012) (done for classical bandits), we achieve this Eq. of the approximate oracles introduced in this section is monotonically increasing w.r.t. the provided parameter vector 0, high value of base arm paramcter Bij does not necessarily mean that test i is more likely to be selected. Hence, with (π(r) denoting the quantile function (such that under the distribution X, Pr (X & Qx(n)) = 77), we compute both an upper confidence bound T ij = Betatalf) (
by utilizing quantiles of the posterior distribution. However, since neither gain function (Eq.
1/t) and a lower confidence bound 0 = Rotatas .a)) (1/t) for each base arm Ggj, which we pass to the oracles. Then, while computing Eq. 7 and Eq. 11 whenever a high value for a term involving fig makes the algorithm more likely to select test i, we use 017 as an optimistic estimate, and correspondingly, 8 for terms making less likely to be selected.
Algorithm 2 Cost-efficient online decision making (0)
Require: P(y); μe: prior parameters (aly - 1: for i. == 1, 2, ..... T do
Sample 0/4) from Beta(a (t-1), "
[ " for all i,j.
g(t) +- Oracle((()) (e.g,, Algorithm 4
4: Make decision based on s(1), and observe af4 for all i such that ay E sto.
Observe correct decision y
6: Call Algorithm and obtain Beta(a. (1) ) for all i,j.
7: end for
Algorithm Posterior update
Require: 8(); a.
(t) for all such that any E 80); y()) k; aij (1-1);s and 00-11)
1: for each z;
(1) do
2: if œ (t) = then
(6) (t-1)
ai a +1
else
Bl0) +- 1)t-l)
5:
ik +1
6: end if
7:
end for
4.1
Approximate Oracles
Solving the optimization problem in Eq. is intractable in general (see, e.g., Golovin et al. 2010 Chakar avarthy et al. 2007]. Therefore, to implement line 3 of Algorithm 2 we propose two different approzimate oracles using algorithms that greedily select tests to optimize a surrogate objective function, Information Gain (IG) ZZeng el al.) 2012) and EC (Golovin et al. 2010). We introduce exlensions of IG and EC2 to handle tests with stochastic costs, which we call Weighted IG (W-IG) and Weighted EC (W-EC²) re- spectively. In both of those, all probabilitics involved are computed using the fixed and known decision
SSince test outcomes are binary, then, given decision y j. each x; follows Bernoulli distribution with parameter 0.y.

---

Published in Transactions on Machine Learning Research (01/2025)
distribution P(y) and the conditional distribution over test outcomes P(xly) (determined by given pa- rameter vector 0, see line 3 in Algorithm 2 In particular, the dependence on 0 is omitted in the following section to simplify notation.
Before introducing W-IG and W-EC?, we need to define the notions of hypothesis and decision region. We call full realization of test outcomes (i.e., of all possible tests) hypothesis. Therefore, with n binary tests, we have 2n different possible hypotheses. Let H 2 {0, 1 be the set of all possible hypotheses for tests. We can partition H. into disjoint sets. We call each of these disjoint sets a decision region. Each decision region corresponds to decision y E [m]. So our objective will be finding the correct decision region, for which the cost of performing tests is low. We want to emphasize that one important difference between these oracles and standard CMAB oracles is that they are interactive. In other words, during a single time step, they sequentially perform tests and observe outcomes to select subsequent tests and make a decision. To our knowledge, our work the first work which utilizes this approach for CMABs.
Weighted IG algorithm (W-IG). In the standard TG algorithm, based on a set of previously observed test outcomes, we select the test that maximizes the reduction of entropy in the decision regions. Formally, the gain of a test in the IG algorithm is defined as:
AiG (i xp) - [[(ylpp)) Exixx (p(()))))))
where is the set of previously performed tests, and Xp the vector of results of tests in P. The random variable for decision regions is denoted y, and H=)) is the Shannon entropy of random variable In the sequentially perform tests that maximize AIG (i xx) divided with the expected cost
W-IG algorithm,
of test i given the previously performed tests. In other words, after performing and observing the outcomes of the tests in P, the next test to perform will be
argmnax AW-iG (i xp), (E([R)(P)
(6)
where
AW-IG (i Xx) A AIG [i|xpp xp) Cost(i)
(7)
and
Cost(i) A Σ
Σ
Mij x Pr (I; = 9. =j - xx),
(4)
(8)
5E(m] (0.1.
given test outcome costs Ui and p consistent with the outcome of test i. We continue performing lests until all hypotheses N Hi belong to sCP
(1) for all i,j. We call the set of hypotheses H4 = (<: > 0}
the same decision region, ie., there only one decision region remaining.
Weighted EC² algorithm (W-EC²). The standard EC² algorithm starts with a graph with H as the set of nodes. We have edge hh, between two hypothescs h and h' if and only if they do not belong to the same decision region. The weight of an edge (h, is set to waw P(h xp) P(h' xp) where P(- | xx) is the posterior distribution of a hypotheses after performing tests. Naturally, the weight of a set of odges & is defined as the sum of weights of edges in E, ie.., w(E) & EnnAnee WAy- We say that performing test i cuts an edge (h, R') if h & Hi or h H.. We denote the set of edges cut by test i with K(i).
We now define the objective function for the EC2 algorithm as
(UKI)) ViE
fECa (P) a w
(9)
Based on the objective function above, we define the EC2 gain of test i as
Agca (i Xp) A E [SECe (PU (i))
SECa (P)),
(10)
7

---

Published in Transactions on Machine Learning Research (01/2025)
and, similar to W-IG, the W-EC² gain as
Aw. (1 xp) & AEca (i xp) Cost(i)
(11)
with Cist(i) defined as in Eq. 8
Also like with W-IG, in the W-EC² algorithm, we sequentially perform tests that maximize the gain A Aw- (i xp). We stop performing tests when all edges are cut, which means that we have only one decision region left.
To be able to implement W-IG and W-EC² (calculate AW-IG and Aw-Bc2), similar to standard IG and EC?, assume that the outcomes of the tests are conditionally independent given the decision. We show the test selection process in W-IG and W-EC² algorithms in Algorithm 4
Algorithm 4 Cost-cfficient approximate oracle
Require: Alg E (W-IG, W-EC)); P(y); μ; 0 Enumerate hypotheses in H
P=U
while more than one docision region left do
Select next test (with A.) computed w.r.t. 0) i" argmax Aale (i xx)).
(E([))(P)
Perform test i" and observe Ze.
Update P(h xp) based results of tests in P.
7: end while
8: Sclect the decision associated to the remaining decision region.
5 Theoretical Analysis
In this section, we theoretically analyze the framework proposed in Section 4 Specifically, we provide an upper bound on the Bayesian regret (defined below) of the online decision making procedure in Algorithm The analysis technique that we use extends the approach by Russo Van Roy (2014) to our setting and yields an analysis which significantly simpler than those by Chen et al. (2013) and Wang & Chen (2018). Furthermore, in our problem, due to the interactive nature of the oracle, the set of available arms changes in each time step. In general, bandit problem with changing sets of available arms is called bandit with sleeping arms, setting which is not considered in the analyses of combinatorial UCB (CUCB) by Chen et al. (013)) and combinatorial Thompson sampling (CTS) by Wang & Chen (2018). Our analysis holds for interactive oracles (hrough the sleeping arms assumption. Moreover, the analyses of CUCB and CTS yield instance-dependen. regret bounds, whereas we focus on an instance-independent (and Bayesian) bound, which also requires a different type of analysis (c.g., a different rogret dccomposition). Furthermore, the analysis of CTS is tailored for one specific choice of uninformative prior, while ours, in principle, allows for arbitrary selection of the prior distribution (whether uninformative informative).
In our problem setting, the set of fcasible super arms I(t) is restricted such that y y" (i.c., correct decisions are guaranteed, and the objective is to minimize the cost of lests). This means that a super arm is feasible if and only if the test outcomes determine the correct decision region. f We also consider access to a perfect oracle which can solve the optimization problem Eq. 4 As mentioned earlier, the problem under consideration Na-hard. On the other hand, assuming access to an exact oracle is common for analyses of regret. bounds for CMABs, even in settings where the exact oracle needs to deal with NP-hard problem. For instance, the work of Hüyük & Tekin (2020) assumes access to exact oracles for NP-hard network problems. Akerblom et al. (2023) consider the intractable problem of stochastic bottleneck identification in an online setting. In fact, via the elegant CMAB formulation of our problem (in contrast to, e.g., the POMDP formulation of Rahbar et al. 2023 and Chen et al. 2017), we are able to obtain a regret bound that is linear in the nunber of tests (rather than exponential).
We relax this assumption in the experiments Section

---

Published in Transactions on Machine Learning Research (01/2025)
The Bayesian regret is defined the expected value of (egret(T) (sce Eq. B. with the expectation taken over the prior distribution of f= and other random variables (e.g., randomness in the rewards and the policy of the agent). Formally,
Bayesian Regret (7) - R
Σ [E[T]
A th (sttt)
(12)
We then prove the lollowing theorem which establishes an upper bound on the Bayesian regret of Thompson Sampling applied our framework. Theorem 5.1. The Bayesion Regret of Algorithm is O(mnyTllog)
Proof. We begin our regret analysis by decomposition of E| ( (5(9)) in the following lemma.
Lemma 5.2. For any upper confidence bound U(!; I + R and lower confidence bound L I(() + R,
=
(((()) ( (S E( f4r (S(
(13)
Proof. This lemma based on Proposition of Russo & Van Roy 2014). Given the history of played super arms (and base arms) and their rewards, we know that in Thompson Sampling the optimal super arm S*.(1) and the played super arm S(t) follow the same distribution. Since (-) deterministic function, we conclude that given the history, the expected values of (S(1) and (S*M()) are equal, and we have:
(2) (S -E((()()))) [s-(((())] + (S (S+,())
and by adding and subiracting (S(1)) prove Lemma 5.2
Additionally, we define lower and upper confidence bounds as
log T (ii)
(S) & Sau nS5)
Σ
(14)
fES
2og T
(() e (n +
Σ
(15)
Ni)
iES
where 2/ the average cost of base arm ai till time t, and (ij) is the number of times base arm aij has been played till time We continue the proof by bounding each term in Lemma 5.2 For the second and third terms, we have the following lemma (where the proof is in Appendix B.I.
Lemma 5.3. (S()) - fu- (S((S))) < 2mn Bf (S* (S-(()))))) < 2mm
In order to bound the first term of the regret decomposition, we utilize the following lemma (where the proof uses a similar technique as Lemma 8 by Akerblom et al. (0023 for the combinatorial batched feedback setting (with batch size 1). See Appendix B.3
Lemma 5.4. Eiery (SU) - (S()) < 87
Now, based on Lemma 5.2 2mn log O(mn Tlog
Lemma
5.3 and Lemin 5.4 we have Bayesian Regret(T)
<
4mn
We utilize the structure of the problem in our analysis and thereby, the bound derived in Theorem 5.1 is significantly tighter than the ones by RRahbar et al. (2023); Chen et al. (2017) which take a different perspective than our CMAB formulation. Our bound is also consistent with Bayesian upper bounds for combinatorial semi-bandit. methods developed in other (standard) settings.
9

---

Published in Transactions on Machine Learning Research (01/2025)
6 Experiments
In this section, we empirically validate our cost-efficient online decision making framework via various exper- iments [ Unless otherwise specified, we consider 22) as the prior distribution of all f7.''s We employ both of the cost-efficient approximate oracles introduced in Section 4.1 (W-IG and W-EC*) as the oracle in Algorithm 2 We also employ the hypothesis enumeration procedure proposed by Chen et al. (2017) to
generate the most likely hypotheses for each dccision region. In Section 6.3 we provide an extension of our
framework to real-valued non-binary test outcomes. Moreover, In Section 6.4 we demonstrate the applica- bility of our framework in the setting where the decision regions for the set of hypotheses are not known, We run each experiment with 5 different random seeds singlo-node CPU machine with 8 cores, 16GB memory and macOS. We implement the algorithms in Python mainly using NumPy (Harris et al. 2020 NetworkX (Hagberg et al. 2008) and SciPy (Virtanen et al. 2020
Data sets. We apply our framework to the LED display domain data set from the UCI repository Breiiman et al. 1988). Additionally, we use the ProPublica recidivism (Compas) data set (Larson et al., 2016) and the Fair Isaac (Fico) credit risk data set (FICO et al. 2018), which both are preprocessed in the same way by Hu et al. (2019). The aforementioned data sets contain relatively large numbers of tests and few decision oulcomes, which correspond well to, e.g., the medical diagnosis example in Section 1 In applications like the charging station selection example, it might instead be reasonable to expect a large number of decision outcomes (individual charging stations or groups sharing certain characteristics) and relatively few tests (questions). Hence, in order thoroughly evaluate the latter type of setting, we create a synthetic data set (called Navigation) with the desired characteristies. With = tests and m 20 decision outcomes, we sample parameters 07 from the prior distribution Beta(2,2) for each i E [r]] and j [m=] which subsequently use to generale the data set. Moreover, in Section 6.2 we present the application of our framework to a real-world troubleshooting case study. Finally, to demonstrate the applicability of our methods to valued
test outcomes, we investigate the Breast Cancer Wisconsin data set (Strect et al. 1993) (Section 6.3
Algorithms. In our experiments, investigate the cost of decision making using both W-IG and W-EC² algorithms embedded in our framework (Algorithm 2). For each algorithm, we investigate both Thompson Sampling and BayesUCB for exploration. In addition to Thompson Sampling (TS) and BCye (BUCB), we consider the following baselines for selecting lests in each lime step:
Random Information Acquisition. Within our framework, we can use a random subset of tests decision making. This bascline continues performing random tests until only one docision region is left (similar to W-IG and W-EC*).
All. This baseline always performs all available tests, and does not consider the cost.
DPP. Determinantal Point Process (DPP) provides a way to select diverse sets. With this method, we use exact sampling (Derezinski et al.) 2019) (finite DPP with likelihood kernel) to subsample columns (tests). We use the implementation of Gautier et al. 2019). To perform the sampling, in each time step 4, we provide all data points (all test results for all data points) until time - 1 to the sampler. The number of selected tests related to the number of eigenvoctors of the kernel matrix.
Table I: Average cost (+: standard deviation) of decision making in time step (over the entire learning period).
Data sot \Algorithm
W-EC2-TS
B-EC
W-IG-TS
W-IG-BUCB
Random
A11
DPP
Navigation
1,746 = 0.030
1,760 = 0.130
1889 + 0.020
[.67 + 0.023
1976 = 0.008
2,300 = 0.000
2,300 + 0.002
LED
2,032 = 0.053
2,061 = 0.059
2,118 0.015
2-138 - 0.019
261 0.025
3.147 = 0.000
3.137 : 0.002
Fimo
1.159 0.003
1.101 + 0.002
1.905
0.075
2.067 + 0.064
3.078
0.005
8.353 0.000
8.240 0.056
Compes
3.006 = 0.009
3,090 + 0.017
4.197
+ 0.039
4.034
+ 0.028
4.719 0.006
6.101 = 0.000
6.923 + 0.049
Broast cancer
1.437 + 0.019
1.554 + 0.032
2.001 0.048
2.213
+ 0.136
6.376
0.087
14.181 4 0.000
9.296 + 0.077
Troubleshotingg
6,207
0.013
7.615 0.034
12.010 0.078
12.563
0.117
38.113 0.000
24.338
The source code for our experiments can he accessed here on GitHub.
10

---

Published in Transactions on Machine Learning Research (01/2025)
Navigation
LED
3
2
Cost
Cost
2
1
W-EC'-TS
Random
W-EC+-BUCB
All
W-IG-TS
DPP
1
W-IG-BUCB
2000
4000
2000
4000
Time step
Time step Compas
Fico
6
7.5
Cost
5.0
100
2.5
2
0
2500
5000
7500
0
2000
4000
Time step
Time step
Figure 2: Decision making costs of our framework applied to four different data sets.
6.1 Experimental Results
We first investigate the four data sets Navigation, LED, Fico, and Compas. As mentioned, to guarantee accurate decision regions for all hypotheses, we implement the algorithm outlined by Chen et al. (2017) for enumeration of hypotheses. In short, this algorithm produces the most probable hypotheses based on a decision and the conditional probabilities of test outcomes associated with that decision. To assign the correct decisions to hypotheses, we extract the parameter vector from the entire data set and subscquently utilize the enumeration procedure to generate the most. likely hypotheses for each decision. However, the
parameters are not known to the agent after the enumeration of hypotheses. We assign fixed costs (0) [0, 1] (1) and Mij E [0, 1] (randomly sampled from a uniform distribution) for each data set before performing our experiments.
2 we illustrate the cos of performing tests (i.e., ([R((()) during online learning for different algorithms. The cost of each test is calculated based Eq. [ where the parameter 0ig is derived from the data. The (maximum) numbers of enumerated hypotheses per decision region are 2, 5. 70 and 70 for Navigation, LED, Fico and Compas datasets, respectively. Our results in Figure show that our framework yields the lowest information acquisition cost for all data sets. DPP has a low cost initially since only uses a few data points to perform sampling, but after a few time steps its cost becomes as high as 'All. During these initial time steps DPP can make incorrect decisions. Additionally, we observe that the W-FC² algorithm always has the lowest cost. This result consistent with the theoretical results of Golovin et al. (2010) for the cost of the original EC² algorithm in the offline setting. We also observe that the exploration methods (TS and BayesUCB exhibit very similar performances in terms of cost. During online learning, it is observed that the cost of the random algorithm remains relatively constant, whercas the costs associated with the W-IG and W-EC² algorithms decrease until they converge to a low value. This behavior is attributed to the utilization of parameter estimates by the W-IG and W-EC² algorithms when selecting tests. As the knowledge of the agent about these parameters improves over the course of learning, the associated costs
In Figure
oTeh reported here directly correspond the (instant) regret up only a term. Therefore, the order of the methods and their relative performances remain the same.
11

---

Published in Transactions on Machine Learning Research (01/2025)
Troubleshooting
40
W-EC²-TS
W-EC2-BUCB
Cost
W-IG-TS
20
W-IG-BUCB
Random
All
DPP
0
0
500
1000
1500
Time step
Figure Decision making costs of our framework when applied online troubleshooting.
decline. Furthermore, in Table ! we report the average cost of decision making in single time step for different data sets. It is obvious that our framework incurs significantly lower costs for performing tests.
6.2 Application to Online Troubleshooting
In this section, we study the application of our decision making framework for online troubleshooting. The data set for this real-world application is collected from contact center agents. The agents solve problems from mobile devices. We use subset of this data with 15 possible decisions and 74 tests. Each test corresponds to symptom that a customer may or may not
the device.
We experiment approximately 1500 different scenarios (i.e., roughly 100 scenarios for each decision). A scenario starts with a customer entering the system. Then the online learning agent aims at finding the correct decision by asking a sequence of multiple questions the customer (performing tests). The goal for the agent is to ask the most informative questions in a cost-efficient manner. We enumerate 15 hypotheses for each decision. Figure 3 shows the cost of making decisions for different time steps (i.e., scenarios) the same setting Section 6.1 The results show that our framework enables the agent find the correct decisions for troubleshooting in mobile devices with significantly lower cost compared to other methods. Similar to previous observations, the W-EC² algorithı remains the most cost-effective method within our framework.
Breast cancer
15
W-EC
W-CC
10
Cost
W-IG-TS
W-IG-BUCB
Random
All
DPP
0
200
400
Time step
Figure 4: Decision making costs of our framework extended to real-valued test outcomes in the Breast Cancer Wisconsin data set.
12

---

Published in Transactions on Machine Learning Research (01/2025)
Navigation
LED
Fico
Compas
3
7.5
2
Cost
55.0
Cost
1
W-EcT-Ta
WH-CC-OUCD
Random
All
2.5
WHG-TS
DPP
WVG BUCB
0.0
2000
Time step
Navigation
4000
1.0
2000
Time step
LED
4000
2500
Time step
Fico
5000
7500
0.6
2000
Time step
Compas
4000
0.0
0.5
0.4
Utiliyy
-0.2
Usiliy
Unilty
Utiliy
0.0
0.2
-0.4
0.0
2000
4000
0
2000
4000
2500
5000
7500
2000
4000
Time step
Time step
Time step
Time step
Figure 5: Decision making cost (first row) and utility (second row) of our framework applied to the setting that the decision regions are not known beforchand.
6.3 Extension to
Test Outcomes
In this section, we extend our experimental results to real-valued (non-binary) test outcomes. For this purpose, we adapt the discretization method proposed by Rahbar et al. (2023). Specifically, for each test, we consider different thresholds for "binarization". Then, in each time step, can calculate the gain (Aw-IG or Aw-Ec= for the tests using different. binarization thresholds and choose the one with maximal gain. We employ this method on the Breast Cancer Wisconsin data set. In this data set, we predict the diagnosis from 30 real-valued medical tests computed from an image of a fine needle aspirate. Figure ! illustrates the decision making cost incurred by our framework when applied to this data set. We enumerate 70 hypotheses per decision region. Similar to the results depicted lowest cost, demonstrating its effectiveness in this setting. In particular, we observe that W-EC²-TS yields the best results, and W-IG-TS, W-EC²-BUCB, and W-IG-BUCB other suitable methods for this task.
Figure 2 our framework consistently achieves the
6.4 Extension to Unknown Decision Regions
In this section, to demonstrate the generality of our framework, we examine the setting where the decision regions for the enumerated hypotheses are not known. To assign hypothescs to decision regions, we employ the hypothesis enumeration algorithm discussed in Section 6.1 to generate the most probable hypotheses for each decision region based on the current parameter sample. Therefore, each hypothesis is assumed to correspond to the decision it is assigned to. This situation may lead to incorrect decisions by the agent. Specifically, in the context of online learning, our objectives are: i) to achieve highly accurate decisions, and ii) minimize the cost of performing tests. To quantify the accuracy of the decisions, we employ utility function. Specifically, we assign a utility of 2 for a correct docision and -1 for an incorrect one. Additionally, we consider an "unknown" decision when the correct hypothesis is assigned multiple decision regions. We define the utility of such decisions as 0.
The first row in Figure shows the cost of making decisions for different data sets (when the correct decisions of the hypotheses are not known). We use the same numbers of enumerated hypotheses as Figure 2 Similar to the findings in Figure 2 we observe that our framework (with both W-IG and W-EC?) yields final docision with significantly lower cost than other algorithms. Again, we observe that EC² (with both Thompson Sampling and BayesUCB) has the lowest cost of performing tests. The IG algorithm results in the second lowest cost, and the random algorithm for picking tests is the third option.
13

---

Published in Transactions on Machine Learning Research (01/2025)
As previously mentioned, when faced with unknown decision regions, our goal is to enhance the accuracy of our decisions during online learning. The second row in Figure 5 illustrates the utility achieved by various information acquisition algorithms. Notably, our framework demonstrates comparable performance to both All and DPP in the early stages of learning. Therefore, our approach proves capable of making precise decisions with a significantly reduced cost. We note that DPP yields very low costs in the early time steps, but the corresponding utility is also very low.
7 Conclusion
We propose novel framework for online decision making based an elegant design of combinatorial multi-armed bandit problem, which incorporates the cost of performing tests, and where the costs may be stochastic and depend on both test and decision outcomes. Within this framework, we develop various cost- efficient online decision making methods such as W-EC² and W-IG. We also adapt Thompson Sampling and BCy, methods that are commonly used for exploration. In particular, we provide a theoretical upper bound for the Bayesian regret of Thompson Sampling. We demonstrate the performance of the framework on a number of data sets from different domains.
Acknowledgments
The work of Arman Rahbar and Morteza Haghir Chehreghani was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foun- dation. The work of Niklas Åkerblom was partially funded by the Strategic Vehicle Research and Innovation Programme (FFI) of Sweden, through the project EENE (reference number: 2018-01937).
References
Niklas Akerblom, Fazeleh Sadat Hoseini, and Morteza Haghir Chehreghani. Online learning of network bottlenecks via minimax paths. Machine Learning, 112(1):131 150, 2023.
Peter Auer, Nicolo
and Paul Fischer. Finite-time analysis of the multiarmed bandit problem.
Machine learning, 47:235 256, 2002.
Djallel Bouneffoff, Irina Rish, Guillermo A. Cecchi, and Raphaël Féraud, Context attentive bandits: Contex- tual bandit with restricted context. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI11, pp. 1468 1475. AAAI Press, 2017. ISBN 9780999241103.
Djallel Bouneffouf, Raphael Feraud, Sohini Upadhyay, Irina Rish, and Yasaman Khazaeni. Toward optimal solution for the context-attentive bandit problem. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 3493-3500. International Joint Conferences on Artificial Intelligence Organization, 8 2021. doi: 10.24963 /0//:////caai2221//// URL https: 7/doi 249633//2.993 2021/481 Main Track.
L. Breiman, J.H. Friedman, R.A. Olshen, and C.J. Stone. LED Display Domain. UCI Machine Learning Repository, 1988.
Nicolo BiancBianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404 1422 2012.
Nicolò Cesa-Bianchi, Tom Cesari, Yishay Mansour, and Vianncy Perchot. Roi maximization in stochastic online decision-making. Advances in Neural Information Processing Systems, 34:9152 9166, 2021.
Venkatesan T Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Pranjal Awasthi, and Mukesh Mohania. Docision trees for entity identification: Approximation algorithms and hardness results. In Proceedings of the twenty-sirth ACM SIGMOD-SIGACT-SICE, symposium on Principles of database systems, pp. 53 62, 2007.
14

---

Published in Transactions on Machine Learning Research (01/2025)
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning, pp. 151-159. PMI.R, 2013.
Yuxin Chen, Jean-Michel Renders, Morteza Haghir Chehreghani, and Andreas Krause. Efficient. online learning for optimizing value of information: Theory and application to interactive troubleshooting. In Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI 2017). 2017.
Sanjoy Dasgupta. Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17:337-344, 2005.
Michal Derezinski, Danicle Calandriello, and Michal Valko. Exact sampling of determinantal point processes with sublinear time preprocessing. Advances in neural informalion processing systems, 32, 2019.
Francesco Di Fiore, Michela Nardelli, and Laura Mainini. Active learning and bayesian optimization: a unified perspective learn with goal. Archives of Computational Methods in Engineering, pp. 1 1-29, 2024.
Audrey Durand and Christian Gagné. Thompson sampling for combinatorial bandits and its application to online feature selection. In Workshops at the Sovetty-igghts AAAI Conference on Artificial Intelligence, 2014.
FICO, Google, Imperial College London, MIT, University of Oxford, UC Irvine, and UC Berke- ley. Explainable machine learning challenge, 2018. URL https:://commnig:/ ftw...cmms.//////ccccccc...
Guillaume Gautier, Guillermo Polito, Rémi Bardenet, and Michal Valko. DPPy: DPP Sampling with Python. Journal of Machine Learning Research Machine Learning Open Source Software (JMLR-MLORE 2019.
URL http::tttt/mml / httpp//..rr//ppppp/////////11111 html Code at wtt.gg/b..../gillgggeeee. /DPPy/ Doc-
umentation at http://appp.rraatticooo....
Daniel Golovin, Andreas Krause, and Debajyoti Ray. Near-optimal bayesian active learning with noisy observations. Advances in Neural Information Processing Systems, 23, 2010.
Aric Hagberg, Pieter Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008.
Charles R. Harris, K. Jarrod Millman, Stéfan J. der Walt, Ralf Gommers, Pauli Virtanen, David Cournapcau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathanicl J. Smith, Robert Kern, Matti Pi- cus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825) 362, September 2020. doi: 10.1038/s41586-020 2-29-264-... URL https: //doi.org/// 10000.0001/4418800222000 2649-2.
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classifi- cation and preference learning. arXiv preprint orXiw:111..57453 2011.
Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. Advances in Neural Informa- tion Processing Systems, 32, 2019.
Alihan Hüyük and Cem Tekin. Thompson sampling for combinatorial network optimization in unknown environments. IEEE/ACM Transactions on Networkingg 2836)2288,,,849, 2020.
Donald R Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black- box functions. Journal of Global optimization, 13:455-492, 1998.
Emilie Kanfmann, Olivier Cappé, and Aurelien Garivier. On bayesian upper confidence bounds for bandit problems. In Artificial intelligence and statisties, pp. 592 600. PMT.R, 2012.
15

---

Published in Transactions on Machine Learning Research (01/2025)
Harold J. Kushner. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of Basic Engineering, 86:97-106, 1964. URL http:////ppp..mmmmiiccccchooll
org/CorpusID:6220 62599010
J. Lanson, S. Mattu, L. Kirchner, and J. Angwin. How we analyzed the compas recidivism algorithm. SIAM journal on computing, 2016.
Dennis Lindley. On a measure of the information provided by an experiment. The Annals of Mathematical Statisties, 27(4):986-100 1005, 1956.
Arman Rahbar, Ziyu Ye, Yuxin Chen, and Morteza Haghir Chehreghani. Efficient online decision tree learning with active feature acquisition. International Joinl Conference on Artificial Intelligence (IJCAI), 32, 2023.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathemalics of Operalions Research, 39(4):1221 -22411121121, 2014.
Aleksandrs Slivkins al. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2):1-286, 2019.
W Nick Street, William H Wolberg, and Olvi Mangasarian. Nuclear feature extraction for breast tumor diagnosis. Biomedical image processing and biomedical visualization, volume 1905, pp. 861 870. SPIE, 1993.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 294, 1933.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Ev- geni Burovski, Pearu Peterson, Warren Weekesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Tan Henriksen, A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbrogt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261 272, 2020. doi: 10. 10100////4592 0066-2..
Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. In International Conference on Machine Learning, pp. 5114-5122. PMLR, 2018
Alice X Zheng, Irina Rish, and Alina Beygelzimer. Efficient test selection in active diagnosis via entropy approximation. XrXiv preprint arXiv:1207.1418. 2012.
A Nomenclature
Table 2: Table of notation used this paper.
Notation
Description
Time stop
x
A problem instance
x (1)
A problem instance received at time t
Test index
Test with index
Test with index performed at time E
A decision
(0
A decision made at time t
n
Number of available tests
16

---

Published in Transactions on Machine Learning Research (01/2025)
Table 2: Table of notation used in this paper.
Notation
Description
Number of possible decisions
Correct decision
T
Time horizon
dij
Base arm related to test with index and decision with index j
A
Set of base arms
super arm A super arm selected at time Reward received at time t Reward of super arm Set of feasible super arms at time Parameter of Bernoulli distribution for test and decision j
S(0
R
R(S)
Z()
By
(6)
P
Cost of basc arm aij when test outcome is 0
Cost of base arm ag when test outcome
Pij
Expected cost of base arm azj
Vector of all pay Vector of all 0zy' True mean cost vector True parameter vector
0'
(1) (S)
Suboptimality gap at time t of super arm S with mean cost vector is μ Expected reward of super arm given a mean cost vector μ Optimal super arm at time t
(a(S)
S*.(t)
Regret (T)
Regret for time horizon when true mean cost vector is μ
First shape parameter of Beta distribution related to Oij at time f Second shape parameter of Beta distribution related to 8ig at time Quantile function (if X has distribution X, then Pr Pr < (x(r)) = n)
Qx
d0
Upper confidence bound for 0ig used in BayesUCB Lower confidence bound for 0y used in Bayes
Set of all possible hypotheses A hypothesis Set of performed tests Vector of results of tests in P Shannon entropy of a random variable 2
P
H(2)
Alg (i) xp)
Gain of test i with algorithm Alg when P the set of performed tests Index of next lest to perform
Hi
Set of hypotheses consistent with the outcome of test
(h,h')
An edge between two hypotheses h and h Weight of an edge (h,
Wha
E
A set of edges Weight of set of edges
(E)
(()
Sot edges cut by test
fE (P)
Objective function of EC² for a set of performed tests
Bayesian Regret(T) (S)
Bayesian regret over a time horizon T
Upper confidence bound for a super arm Lower confidence bound for a super arm S
(S)
Average cost of base arm ai till time t
(()
Number of times base a,j has been played till time t
Average of first т observations of test i under decision
17

---

Published in Transactions on Machine Learning Research (01/2025)
B Additional Proofs
B.1 Proof of Lemma 5.3
Proof.
ELL
fp- (8(0))
2 T
Σ
+ Σ uig
N((-1
(ij)
ijESt)
(jES())
ijES(O
Σ
E
P p(6-1) 1)
2 T (ij)) + pij
((ES(t)
$ Σ
E
Mig
Pig
(1-1)
2 log T (ij)
i()
([z]+ = max (0,
- Σ
E
Pij - Mij
(1-1)
log T N (ij
DEA
Σ TEE
E
[nts
111-111
2 log T Nut 1) (ij)
"bad event"
Pr event")
(16)
where "bad event" is |04g
(1-1)
21og No (10-11(5))
The last cquality comes from the fact that [lułs We continue with the following lemma.
111-111 11
oog N(i-
=0 107s - - -1(011) S V
2 Ni
Lemma B.1. Pr 3r [T] Bij E A. A, Pij
(t-1))
log T
4.
Proof. To prove Lemma B.1
we use Eq. which implies that Ing - 1
1n mb 10 0/-11 D
together with the fact that |m!) Appendix B.2
Miy (0)] S 1, as well as Hoeffding's inequality. The full proof is given in
Continuing from Eq. 16 using Lemma B.1 and noting that |M - A,j (t-1)) < 1 we have
([(0) fx. (8(1)) <
Σ
2mn
(17)
T T
DEU
We can similarly show that
Blf.. - - (5+(0)))))) 2mn
(18)
T
7
18

---

Published in Transactions on Machine Learning Research (01/2025)
B.2 Proof of Lemma B11
Proof. Let ] be the average of first 7 observations of x; under the decision region y = j. We have:
Pr E [ E A P/g 1
2 2log T N (i))
Bq.
Pr Et E [T] Bij E A. 11 0ig
11
2 log T N(C-1)
(since |n4
(0) Mij - 1)
< Pr E1E [T] 3ij E A.1% 00-111
2 log T N(1
(Union bound)
[t-1]
2 log T
$
TE[T] ijE r=1
(assuming 722 [4))
2 T
ST 27 2T
The last inequality is due to Hoeffding's inequality (e.g., Theorem A.1 of Slivkins et al. 2019 with 2).
B.3 Proof of Lemma 5.4
Proof.
Σ LE[T]
- - (8(0))
2log T
Σ
E Σ
V 1(1)
1E(T]
ijES(
//g T
E
VN(I-D)(1)
SE[T]
Lijestn
-Vllog
E
Σ
VN((-1)(T)
iEEA
(tijes())
= =8log T
Σ
KjEA
(IE
19

---

Published in Transactions on Machine Learning Research (01/2025)
(Lemma of Russo & Van Roy 2014
s 22/8log T
E
ijEA
(Cauchy Schwarz inequality)
- 2 8 log E
mn
(ij
ijEA
S $2/8 1//8lgg1 T IE
V(mn))
= =2mn/87 8////Tlog T.
20


Reviews:
[{"review_id": "URYhES6P7j", "reviewer": "Reviewer_rkex", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- New formulation for cost efficiency as a CMAB is interesting and results look promising\n- Theoretical analysis and bound on Bayesian Regret show good mathematical grounding for the idea\n- Approximate oracles are elegant approaches to solve the untractable optimization problem\n- Extensive empirical study of the methods in practice, both on benchmark datasets and the case study on online troubleshooting\n\nWeaknesses:\n- Lack of clarity sometimes in the reasoning and notations - e.g. modeling choices are not always justified (for instance, why specifically a a Beta distribution as a prior for the parameters in section 4?)\n- No theoretical analysis of the approximate oracles, which for me is fairly significant - this is necessary to give insights on the practicality of the method (not just the framework which is not directly applicable)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the problem of cost efficient online Multi-Armed Bandits exploration, i.e. when there is a cost attached to running the experiments. After a brief overview of related work, the paper formally introduces the CMAB formulation of the problem. Given the difficulty of the optimization used, it also provides two approximate oracles to solve it. It then provides some theoretical insights on the Bayesian Regret of the framework, before validating the approach on benchmark datasets and a case study on online troubleshooting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses section. In short:\n- Review clarity of notation, and comprehensively define everything\n- Extend theoretical analysis to the approximate oracles", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gRp1E2uab2", "reviewer": "Reviewer_ZvvS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1. It is reasonable to consider the cost of decision making problem and formulate as a combinatorial MAB problem. \n2. The results are complete with both theoretical and empirical verifications. \n\nWeakness: \n1. It is not easy to follow the story of the work. In Section 3, what does the $m$ mean? The authors say that $m$ represents the total number of options for the decision. Can $m$ be regarded as a combination over $n$ tests thus each decision making corresponds to a selection over $n$ tests? If so, the base arm set size in the CMAB should be $n$ instead of $n\\times m$. \n2. In the end of page 3, \"We let the cost (assumed to be fixed and known)\", should \"know\" be changed as \"unknown\"? And what does test outcome mean? It seems that the paper assumes the cost to be known but the test outcome to be unknown. Can authors give a motivating example for this assumption?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper formulates the online decision making problem as a combinatorial multi-armed bandits problem. The reward in the literature corresponds to the cost of each decision making. The paper proposes oracles to solve the combinatorial offline optimazation problem and propose a Thompson sampling as well as a Bayes UCB algorithm to solve the online setting. The paper provide both theoretical guarantees and empirical verifications for the proposed methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weakness part. Section 3 should be modified for better readability.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LekPVMybnm", "reviewer": "Reviewer_ZRLU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. Novel Formulation: The combination of cost-efficient decision-making with combinatorial bandit algorithms is a significant extension of existing online learning models.\n\n2. Theoretical Rigor: The paper provides formal theoretical guarantees, in the form of a regret upper bound.\n\n**Weaknesses**\n\n1. Heavy Notation: The paper introduces complex notation that can be overwhelming, especially in the problem formulation and algorithmic sections, where the reader is just getting acquainted with it.\n\n2. Readability: The presentation is not easy to follow due to the notation and the way the material is presented. It would help to get some visual aids, such as representing the base arms as a matrix with a highlighted subset representing a superarm, and arrows pointing to the other quantities (e.g., the corresponding tests) to clarify the interactions between tests and decisions.\n\n3. Presentation of the protocol: It would be helpful to have a fully detail pseudocode representing the protocol (similar to Algorithm 1, but where all notation is clarified). It was not immediate to me to get everything from the drawn-out description in Section 3. Place this float at the beginning of the problem formulation.\n\n4. Missing matching lower bound", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel framework for cost-efficient online decision-making by leveraging a combinatorial multi-armed bandit (CMAB) approach. The core contributions can be summarized as follows:\n\n- Problem Formulation: The authors introduce a new problem formulation for outcome-dependent, cost-efficient online decision-making, where tests and decisions incur stochastic costs. This framework generalizes traditional multi-armed bandit problems to include combinatorial and cost-efficient aspects.\n\n- CMAB Framework: The proposed combinatorial semi-bandit framework involves selecting a subset of actions (referred to as \"super arms\") under combinatorial constraints, thus optimizing the trade-off between information gain and decision cost.\n\n- Algorithmic Development: The authors adapt classical bandit methods, particularly Thompson Sampling and Bayesian Upper Confidence Bound (BayesUCB), and extend existing active information acquisition methods (like EC2 and Information Gain) to handle variable costs. The new algorithms, named W-EC2 and W-IG, optimize test selections to minimize overall decision costs.\n\n- Theoretical Analysis: The paper establishes a theoretical upper bound on the Bayesian regret for Thompson Sampling, demonstrating the efficiency of their approach in the CMAB setting.\n\nExperiments complement the theoretical analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Implement the visual aids requested in Weakness 2.\n\n- Add the protocol as described in Weakness 3.\n\n- (Optional but strongly recommended) Add a (near-)matching lower bound to complement Theorem 5 (Weakness 4.)\n\n- ROI Maximization in Stochastic Online Decision-Making (Cesa-Bianchi et al., 2021) seems related. Please, add it to the related work section, and compare/contrast.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UfVWISwuut", "reviewer": "Reviewer_JNrp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. Combining CMAB with (cost-aware) information acquisition-based methods for solving cost-aware decision-making problems is an interesting approach.\n2. Theoretical guarantees on the regret, albeit straightforward and not novel, are nice to have.\n3. Simulations show that the authors' approach does better than some baseline algorithms on semi-synthetic datasets.\n\n### Weaknesses\n1. Adaptations of the TS and BayesUCB algorithms for parameter estimation lack novelty.\n2. The framework relies on the Naïve Bayes assumption of conditional independence among tests given the decision.\n3. The framework assumes that a super arm is feasible if and only if the test outcomes determine the correct decision region. This implies that the model focuses solely on minimizing test costs. Such an assumption may limit the applicability of the framework in settings where certain decisions naturally incur higher test costs. For instance, in a medical diagnosis scenario involving both flu and cancer, the current approach would consistently select lower-cost tests for flu, potentially neglecting the necessary, higher-cost tests required to accurately diagnose cancer.\n4. There are theoretical results, but only for the Bayesian regret (i.e., CMAB part), and no guarantees for the oracles (W-IG and W-EC$^2$).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a framework for an online decision-making problem where decisions are made based on the results of cost-incurring tests. They utilize the Combinatorial Multi-Armed Bandit (CMAB) framework, specifically Thompson Sampling (TS) and BayesUCB-based algorithms, to estimate the test-decision parameters. Additionally, they information acquisition-based methods to select which tests to perform based on the estimated parameters. The authors also provide a sublinear upper bound for the Bayesian regret and present simulation results demonstrating the performance of their approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. As stated in the weaknesses section, the assumption that \"a super arm is feasible if and only if the test outcomes determine the correct decision region\" is very limiting. Could the authors please justify this?\n2. Could the authors compare their chosen oracles to some other active-learning algorithms? For instance Expected Improvement (EI), Probability of Improvement (PI), or Bayesian Active Learning by Disagreement (BALD).\n3. Could the authors provide a real-world example of their proposed framework, where they define tests, decisions, costs, etc.?\n4. Could the authors provide guarantees/error bounds for the proposed oracles (W-IG and W-EC$^2$)?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the problem is relevant and that the formulation of online decision making as a combinatorial multi armed bandit problem is meaningful and novel. 
The techniques employed in the design and analysis of the proposed algorithm are rather standard, but the results are comprehensive and sound.
The authors have already implemented the main suggestions of the reviewers so I deem the latest revision ready for publication.
Decision: Accept (poster)