Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications

1 Introduction

The stochastic multi-armed bandit model is a predominant model for characterizing the trade-off between exploration and exploitation in a variety of application fields with stochastic environments. In this model, we are given a set of stochastic arms associated with unknown distributions. Upon each play of an arm, the player can get a reward sampled from the corresponding distribution. The most well studied objective is to maximize the cumulative reward, or minimize the cumulative regret, e.g., [Lai and Robbins, 1985; Auer et al., 2002b; Auer et al., 2002a; Bubeck et al., 2012]. Another popular objective is to identify the optimal arm with high probability by adaptively sampling arms based on the feedback collected. This is called the pure exploration version of the multi-armed bandit problem [Bubeck et al., 2011; Audibert and Bubeck, 2010; Gabillon et al., 2012].

†Corresponding authors.

∗Due to space constraints, supplementary materials and proofs are moved into the extended version [Huang et al., 2018].

Instead of identifying the single optimal arm, there are a class of extended problems identifying the optimal combinatorial decision, e.g., top-k arm identification [Kalyanakrishnan and Stone, 2010; Kalyanakrishnan et al., 2012; Bubeck et al., 2013; Kaufmann and Kalyanakrishnan, 2013; Zhou et al., 2014], multi-bandit best arm identification [Gabillon et al., 2011], and their extension, Combinatorial Pure Exploration with Linear reward functions (CPE-L) [Chen et al., 2014; Chen et al., 2016a], etc. In CPE-L [Chen et al., 2014], the rewards are linear functions on the means of underlying arms, and the decision class is subsets of arms satisfying certain combinatorial constraints.

In this paper, we further generalize CPE-L problems to a large class of Combinatorial Pure Exploration with Continuous and Separable reward functions (CPE-CS) (see Section 2 for the technical definition). We propose the Consistently Optimal Confidence Interval (COCI) algorithm to solve the CPE-CS problem. To analyze its sample complexity, we define a new arm-level measure called consistent optimality radius Λi of arm i and a new hardness measure called consistent optimality hardness HΛ = ∑mi=1 1/Λ2i , where m is the number of arms. We prove that with probability at least 1 - δ, COCI finds the optimal solution in O(HΛ log(HΛδ-1 )) rounds. We also show that CPE-CS problems have a lower bound Ω(HΛ +HΛm-1 log δ-1 ) in expectation, indicating that the hardness HΛ is necessary.

We demonstrate the usefulness of CPE-CS by two applications. The first one is water resource planning [Bradley et al., 1977]. The goal is to remove waste at water sources of an area. One can first do some purification tests at different sources to estimate the water quality responses, and then determines the final allocation of purification powers among different sources. One need to balance the trade-off between the purification power and the cost, and usually the objective function is non-linear. This application can be generalized to other urban planning scenarios such as air pollution control, crime control, etc. The second application is partitioned opinion sampling [Bethel, 1986; Ballin and Barcaroli, 2013; Huang et al., 2017]. The opinion polling is done by partitioning people into groups and sampling each group separately with different sample budget to improve the sample quality. One can first do some tests in each group to estimate its opinion variance, and then determines the sample size for each group under the total sample budget for the formal sampling process. In this case, the objective function is also non-linear. Furthermore, we show that the COCI algorithm also solves the CPE-L problem with the same sample complexity as the CLUCB algorithm proposed by Chen et al. [2014].

In summary, our contributions include: (a) studying the combinatorial pure exploration problem with continuous and separable functions and proposing the COCI algorithm as its solution, (b) analyzing the sample complexity of COCI and providing both its lower and upper bounds with a novel hardness measure, and (c) applying the CPE-CS framework to water resources planning and partitioned opinion sampling with non-linear reward functions to demonstrate the usefulness of the CPE-CS framework and the COCI algorithm.

Related Work. Pure exploration bandit studies adaptive learning methods to identify the optimal solution. Best arm identification [Bubeck et al., 2011; Audibert and Bubeck, 2010; Gabillon et al., 2012], top-k arm identification [Kalyanakrishnan and Stone, 2010; Kalyanakrishnan et al., 2012; Bubeck et al., 2013; Kaufmann and Kalyanakrishnan, 2013; Zhou et al., 2014], the multi-bandit best arm identification [Gabillon et al., 2011] have been studied in the literature. Chen et al.; Chen et al. [2014; 2016a] generalize these studies to Combinatorial Pure Exploration with Linear reward functions (CPE-L). Soare et al. [2014] also study the linear reward functions, but the player is required to select a decision to play instead of a single arm to sample in each round. A very recent paper [Chen et al., 2017] studies the CPE problems beyond linear reward functions, but their model assumes arms with Gaussian distributions and only works with the mean estimator, while our CPE-CS only requires bounded distributions and also works for variance estimators. Moreover, for efficient implementations, they need a pseudo-polynomial algorithm for the exact query besides the maximization oracle, but our solution only needs a maximization oracle.

A related online learning problem is multi-armed bandit (MAB), e.g., [Lai and Robbins, 1985; Auer et al., 2002b; Auer et al., 2002a; Bubeck et al., 2012]. The goal of MAB is to maximize cumulative rewards over multiple rounds, and the key is to balance exploration and exploitation during the learning process. In contrast, in pure exploration, the key is the adaptive exploration in the learning process to quickly find the optimal solution, and thus it is fundamentally different from MAB [Bubeck et al., 2011]. Combinatorial MAB is a popular topic in recent years [Cesa-Bianchi and Lugosi, 2012; Gai et al., 2012; Chen et al., 2016c; Chen et al., 2016b; Gopalan et al., 2014; Kveton et al., 2014; Kveton et al., 2015; Combes et al., 2015], but their goals and techniques are very different from ours.

2 ProblemDefinition

An instance of combinatorial pure exploration bandit problems consists of (a) a set of m arms [m] = {1, . . . ,m}, each arm i being associated with an unknown distribution Di with range [0, 1] and a key unknown parameter θ∗ i ∈ [0, 1] of Di, (b) a finite set of decisions Y ⊆ Rm, with each decision y = (y1, . . . , ym) as a vector, and (c) a real-valued (expected) reward function r(θ; y) with vector θ taken from the parameter space [0, 1]m and y ∈ Y. In each round t = 1, 2, . . . , a player selects one arm i ∈ [m] to play, and observes a sample independently drawn from Di as the feedback. The player needs to decide based on the observed feedback so far if she wants to continue to play arms. If so, she needs to decide which arm to play next; if not, she needs to output a decision yo ∈ Y such that with high probability yo is the optimal decision maximizing the reward r(θ∗ ; yo ), where θ∗ = (θ∗ 1 , . . . , θ∗m) is the vector of the true underlying parameters of the unknown distributions D = (D1, . . . , Dm).

Definition 1. Given a combinatorial pure exploration instance ([m], Y, r(·; ·),D, θ∗ ) and a confidence error bound δ, the combinatorial pure exploration (CPE) problem requires the design of an algorithm with the following components: (a) a stopping condition, which decides whether the algorithm should stop in the current round, (b) an arm selection component, which selects the arm to play in the current round when the stopping condition is false, and (c) an output component, which outputs the decision yo when the stopping condition is true. The algorithm could only use ([m], Y, r(·; ·)) and the feedback from previous rounds as inputs, and should guarantee that with probability at least 1 - δ the output yo is an optimal decision, i.e., yo ∈ argmaxy∈Y r(θ∗ ; y).

A standard assumption for CPE problems is that the optimal decision under the true parameter vector θ∗ is unique, i.e., y∗ = argmaxy∈Y r(θ∗ ; y). The performance of a CPE algorithm is measured by its sample complexity, which is the number of rounds taken when the algorithm guarantees its output to be the optimal one with probability at least 1 - δ.

We say that a reward function r(θ; y) is continuous if r(θ; y) is continuous in θ for every y ∈ Y, and (additively) separable if there exist functions r1, . . . , rm such that r(θ; y) = ∑mi=1 ri(θi, yi). We use CPE-CS to denote the class of CPE problems with Continuous and Separable reward functions and each parameter θ∗ i of arm i can either be mean EX∼Di [X] or variance VarX∼Di [X]. 1 We use ESTi(Xi,1,Xi,2, . . . ,Xi,s) to denote the unbiased estimator for parameter θ∗ i from s i.i.d. observations Xi,1,Xi,2, . . . ,Xi,s of the i-th arm. In particular, for the mean estimator, ESTi(Xi,1,Xi,2, . . . ,Xi,s) = 1s ∑sj=1 Xi,j , and for the variance estimator, ESTi(Xi,1,Xi,2, . . . ,Xi,s) = 1 s-1 (∑sj=1 X2 i,j - 1s (∑sj=1 Xi,j)2). Notice that the variance estimator needs at least two samples. We also define φ: [0, 1]m → Y to be a deterministic tie-breaking maximization oracle such that for any θ ∈ [0, 1]m, φ(θ) = (φ1(θ), . . . , φm(θ)) ∈ argmaxy∈Y r(θ; y) and it always outputs the same optimal solution, called the leading optimal solution, under the same parameter θ.

CPE-CS encompasses the important CPE problems with Linear reward functions (CPE-L). In CPE-L, parameter θ∗ i is the mean of arm i for each i ∈ [m]. Each decision is a subset of [m], which can be represented as an m-dimensional binary vector. Thus, the decision space Y is a subset of {0, 1}m, and each vector y = (y1, . . . , ym) ∈ Y represents a subset Algorithm 1: COCI: Consistently Optimal Confidence Interval Algorithm for CPE-CS

1 Other parameter θ∗ i of Di is also acceptable if it has an unbiased estimator from the samples of Di. Only a minor change is needed in the formula of confidence radius in COCI (Algorithm 1).

Input: Confidence error bound δ ∈ (0, 1), maximization oracle φ. Output: yo = (y1, y2, . . . , ym) ∈ Y. 1 t ← τm; // τ = 1 for the mean estimator and τ = 2 for the variance estimator 2 for i = 1, 2, . . . ,m do 3 observe the i-th arm τ times Xi,1, . . . ,Xi,τ ; 4 Ti,t ← τ; 5 estimate ˆ θi,t ← ESTi(Xi,1, . . . ,Xi,Ti,t ); 6 radi,t ← √ 1 2Ti,t ln 4t3 τδ ; // confidence radius 7 ˆΘt ← {θ ∈ [0, 1]m : |θi-ˆ θi,t| ≤ radi,t, ∀i ∈ [m]}; 8 for t = τm+1, τm+2, τm+3, . . . do 9 Ct ← ∅; 10 for i = 1, 2, . . . ,m do 11 if maxθ∈ˆΘt-1 φi(θ) ̸=minθ∈ˆΘt-1 φi(θ) then 12 Ct ← Ct ∪ {i}; 13 if Ct = ∅ then 14 return yo = φ(θ) for an arbitrary θ ∈ ˆΘt-1; 15 j ← argmaxi∈Ct radi,t-1; 16 Tj,t ← Tj,t-1 +1; Ti,t ← Ti,t-1 for all i ̸= j; 17 play the j-th arm and observe the outcome Xj,Tj,t ; 18 update ˆ θj,t ← ESTj(Xj,1, . . . ,Xj,Tj,t ); 19 update ˆ θi,t ← ˆ θi,t-1 for all i ̸= j; 20 update radi,t ← √ 1 2Ti,t ln 4t3 τδ for all i ∈ [m]; 21 ˆΘt ← {θ ∈ [0, 1]m : |θi-ˆ θi,t| ≤ radi,t, ∀i ∈ [m]};

of arms Sy = {i ∈ [m] : yi = 1}. Moreover, the reward function r(θ; y) = ∑mi=1 θi · yi is continuous and separable.

3 Solving CPE-CS

In this section, we propose the Consistently Optimal Confidence Interval (COCI) Algorithm for CPE-CS, and analyze its sample complexity. En route to our sample complexity bound, we introduce a new concept of arm-level consistently optimal radius Λi of each arm i, which leads to a new hardness measure HΛ. We first introduce the components and notations which will be used in the algorithm.

The algorithm we propose for CPE-CS (Algorithm 1) is based on the confidence intervals of the parameter estimates. The algorithmmaintains the confidence interval space ˆΘt for every round t to guarantee that the true parameter θ∗ is always in ˆΘt for all t > 0 with probability at least 1 - δ. After the initialization (lines 1-7), in each round t, the algorithm first computes the candidate set Ct ⊆ [m] (lines 9-12). According to the key condition in line 11, Ct contains the i-th arm if maxθ∈ˆΘt-1 φi(θ) ̸= minθ∈ˆΘt-1 φi(θ) (this is a logical condition, and its actual implementation will be discussed in Section 3.1). The stopping condition is Ct = ∅ (line 13), which means that within the confidence interval space, all leading optimal solutions are the same. In this case, the algorithm returns the leading optimal solution under any θ ∈ ˆΘt-1 as the final output (line 14). Notice that if the true parameter θ∗ is in ˆΘt-1, then the output is the true optimal solution yo = φ(θ∗ ) = y∗ . If Ct ̸= ∅, then the algorithm picks any arm j with the largest confidence radius (line 15), plays this arm, observes its feedback, and updates its estimate ˆ θj,t and confidence radius radj,t accordingly (lines 16-21). Intuitively, arm j is the most uncertain arm causing inconsistency, thus the algorithm picks it to play first. Since the key stopping condition is that the leading optimal solutions for all θ ∈ ˆΘt-1 are consistently optimal, we call our algorithm Consistently Optimal Confidence Interval (COCI) algorithm.

Before analyzing the sample complexity of the COCI algorithm, we first introduce the (arm-level) consistent optimality radius for every arm i, which is formally defined below.

Definition 2. For all i ∈ [m], the consistent optimality radius Λi for arm i is defined as:

Intuitively, Λi measures how far θ can be away from θ∗ (in infinity norm) while the leading optimal solution under θ is still consistent with the true optimal one in the i-th dimension, as precisely stated below.

The following lemma shows that the consistent optimality radii are all positive, provided by that the reward function is continuous and the true optimal decision y∗ is unique.

Lemma 1. If the reward function r(θ; y) is continuous on θ for every y ∈ Y, and the optimal decision y∗ under the true parameter vector θ∗ is unique, then Λi is positive for every i ∈ [m].

Given that the consistent optimality radii are all positive, we can introduce the key hardness measure used in the sample complexity analysis. We define consistent optimality hardness as HΛ = ∑mi=1 1 Λ2i . The following theorem shows our primary sample complexity result for the COCI algorithm.

Theorem 1. With probability at least 1 - δ, the COCI algorithm (Algorithm 1) returns the unique true optimal solution yo = y∗ , and the number of rounds (or samples) T satisfies

Theorem 1 shows that the sample complexity is positively related to the consistent optimality hardness, or inversely proportional to the square of consistent optimality radius Λ2i . Intuitively, when Λi is small, we need more samples to make the optimal solutions in the confidence interval consistent on the i-th dimension, and hence higher sample complexity.

We remark that if we do not compute the candidate set Ct and directly pick the arm with the largest radius among all arms in line 15, every arm will be selected in a round-robin fashion and COCI becomes a uniform sampling algorithm. In the extended version, we show that the sample complexity upper bound of the uniform version is obtained by replacing HΛ inEq. (1) byHUΛ = m mini∈[m] Λ2i , and the factor HUΛ is tight for the uniform sampling. This indicates that the adaptive sampling method of COCI would perform much better than the uniform sampling when arms have heterogeneous consistent optimality radii such that HΛ ≪HUΛ .

Due to the space constraint, we only provide the key lemma below leading to the proof of the theorem. We define a random event ξ = {∀t ≥ τm, ∀i ∈ [m], |ˆ θi,t - θ∗ i | ≤ radi,t}, which indicates that θ∗ is inside the confidence interval space of all the rounds. Then we have the following lemma.

Lemma 2. Suppose event ξ occurs. For every i ∈ [m] and every t > τm, if radi,t-1 < Λi/2, then the i-th arm will not be played in round t.

Proof. Suppose, for a contradiction, that the i-th arm is played in round t, namely, i ∈ Ct, and i = argmaxj∈Ct radj,t-1. Thus for each j ∈ Ct, we have radj,t-1 ≤ radi,t-1 < Λi/2.

We claim that for all θ ∈ ˆΘt-1, φi(θ) = φi(θ∗ ). If so, maxθ∈ˆΘt-1 φi(θ) = minθ∈ˆΘt-1 φi(θ), then by line 11 i ̸∈ Ct, a contradiction.

We now prove the claim. For any vector x ∈ Rm and any index subset C ⊆ [m], we use xC to denote the subvector of x projected onto C. For vector-valued functions such as φ(θ), we use φC(θ) for φ(θ)C. For any θ ∈ ˆΘt-1, we construct an intermediate vector θ′ = (θCt , θ∗-Ct ), i.e., the j-th component θ′j is θj when j ∈ Ct, or θ∗ j when j /∈ Ct. Since event ξ occurs, we have |ˆ θj,t-1-θ∗ j | ≤ radj,t-1 for j ∈ [m]. Thus for all j ∈ Ct, |θ′j -θ∗ j | ≤ |θj - ˆ θj,t-1| + | ˆ θj,t-1 - θ∗ j | ≤ 2 radj,t-1 < Λi, and for all j /∈ Ct, |θ′j -θ∗ j | = 0. This means that ‖θ′ - θ∗ ‖∞ < Λi. According to Proposition 1, φi(θ′ ) = φi(θ∗ ). We next prove that φi(θ) = φi(θ′ ), which directly leads to φi(θ) = φi(θ∗ ).

Since event ξ occurs and θ∗ ∈ [0, 1]m, θ∗ is in ˆΘt-1. By the definition of θ′ and θ ∈ ˆΘt-1, θ′ is also in ˆΘt-1. According to Algorithm 1, for each j /∈ Ct, we have maxθ∈ˆΘt-1 φj(θ) = minθ∈ˆΘt-1 φj(θ), thus φ-Ct (θ) = φ-Ct (θ′ ) = φ-Ct (θ∗ ).

Note that the reward function is separable, we have

Let YCt (θ) = {yCt : y ∈ Y ∧ y-Ct = φ-Ct (θ)}. It is straightforward to verify that φCt (θ) is the leading optimal solution for the following problem:

Similarly, we have

and φCt (θ′ ) is the leading optimal solution for

Since φ-Ct (θ) = φ-Ct (θ∗ ), optimization problems (2) and (3) are identical, thus they have the some leading optimal solution φCt (θ) = φCt (θ′ ). Notice that i ∈ Ct, therefore, φi(θ) = φi(θ′ ) holds.

The above lemma is the key connecting consistent optimality radius Λi with confidence radius radi,t-1 and the stopping condition. Its proof relies on both the definition of consistent optimality radius and the assumption of separable reward functions. With this lemma, the sample complexity can be obtained by considering the first round when every arm satisfies the condition radi,t-1 < Λi/2.

Borrowing a lower bound analysis in [Chen et al., 2017], we can further show that the hardness measure HΛ is necessary for CPE-CS, even CPE-L, as shown below.

Theorem 2. Given m arms and δ ∈ (0, 0.1), there exists an instance such that every algorithm A for CPE-L which outputs the optimal solution with probability at least 1 - δ, takes at least

samples in expectation.

3.1 Implementing the Condition in Line 11

The key condition in line 11 of Algorithm 1 is a logical one revealing the conceptual meaning of the stopping condition, but it does not lead to a direct implementation. In many CPE-CS instances, the condition can be translated to a condition only on the boundary of ˆΘt-1, and further due to the bi-monotonicity of φ introduced below, it has an efficient implementation. Such instances include best-arm identification, top-k arm identification, water resources planning (Section 4.1), partitioned opinion sampling (Section 4.2), etc.

We say that the leading optimal solution φ(θ) satisfies bi-monotonicity, if for each i ∈ [m], φi(θ) is monotonically non-increasing (or non-decreasing) in θi, and monotonically non-decreasing (or non-increasing) in θj for all j ̸= i. For convenience, we use θi,t = maxθ∈ˆΘt θi and θi,t = minθ∈ˆΘt θi to denote the upper and lower confidence bound of arm i in round t. We also use θ-i,t and θ-i,t to denote the upper and lower confidence bounds of all arms excluding arm i.

Theorem 3. If the leading optimal solution φ(θ) satisfies bimonotonicity, the condition in line 11 of Algorithm 1 can be efficiently implemented by

The above theorem indicates that, when bi-monotonicity holds for φ(θ), we only need two calls to the offline oracle φ(θ) to implement the condition in line 11, and thus the COCI algorithm has an efficient implementation in this case.

4 Applications

4.1 Water Resource Planning

Water resource systems benefit people to meet drinking water and sanitation needs, and also support and maintain resilient biodiverse ecosystems. In regional water resource planning, one need to determine the Biological Oxygen Demand (BOD, a measure of pollution) to be removed from the water system at each source. Online learning techniques proposed in recent years make adaptive optimization for water resource planning possible.

Let yi be the pounds of BOD to be removed at source i. One general model (adapted from [Bradley et al., 1977]) to minimize total costs to the region to meet specified pollution standards can be expressed as:

where θ∗ i is the quality response caused by removing one pound of BOD at source i, and fi(yi) is the cost of removing yi pounds of BOD at source i. Each yi is constrained by ci, the maximum pounds of BOD that can be removed at source i. Moreover, the total pounds of BOD to be removed are required to be larger than a certain threshold b.

The above model formulates the trade-off between the benefit and the cost of removing the pollutants. The cost function fi is usually known and non-linear, which may depend on the cost of oxidation, labor cost, facility cost, etc., while the quality response θ∗ i is unknown beforehand, and needs to be learned from tests at source i. In each test, the tester measures the quality response at a source i and gets an observation of θ∗ i , which can be regarded as a random variable θi derived from an unknown distribution with mean θ∗ i . The goal is to do as few tests as possible to estimate the quality responses, and then give a final allocation (yo 1 , . . . , yom) of BOD among sources as the plan to be implemented (e.g., building BOD removal facilities at the sources).

The above problem falls into the CPE-CS framework. The i-th source corresponds to the i-th arm. Each quality response at source i is the unknown parameter θ∗ i associated with the arm i, and τ = 1. Each allocation (y1, . . . , ym) satisfying the constraints corresponds to a decision. We discretize {yi}'s so that the decision class Y is finite. The reward function is r(θ, y) = ∑mi=1 θiyi-∑mi=1 fi(yi), which is continuous and separable. Suppose the offline problem of Eq. (4) when θ∗ is known can be solved by a known oracle φ(θ∗ ). Then, the COCI algorithm can be directly applied to the water resource planning problem. The following lemma gives a sufficient condition for the bi-monotonicity of φ.

Lemma 3. When {dfi/dyi}'s are all monotonically increasing or decreasing, and the constraint ∑mi=1 yi ≥ b is tight at the leading optimal solution φ(θ) for all θ, then φ(θ) satisfies bi-monotonicity.

By Theorem 3, when the offline oracle for the water resources planning problem satisfies bi-monotonicity, we can instantiate the condition in line 11 of Algorithm 1 as φi(θ-i,t-1 , θi,t-1) ̸= φi(θ-i,t-1, θi,t-1 ).

Although this application is set up in the context of water resource planning, we can see that the formulation in Eq. (4) is general enough to model other applications, especially ones in the urban planning context. For example, for planning air quality control for a city, we need to target a number of air pollution emission sources (e.g., factories), and do adaptive testing at the sources to determine the optimal pollution remove target at each sources which maximizes the total utility of the planning. Other applications, such as crime control, may also be modeled similarly as instances of our CPE-CS framework and solved effectively by our COCI algorithm.

4.2 Partitioned Opinion Sampling

Public opinion dynamics has been well studied, and there are a number of opinion dynamic models proposed in the literature, such as the voter model [Clifford and Sudbury, 1973], and its variants [Yildiz et al., 2011; Li et al., 2015; Huang et al., 2017]. In these models, people's opinions f (t) 1 , f (t) 2 , . . . , f (t) n ∈ [0, 1] change over time t, and will converge to a steady state after sufficient social interactions in which the joint distribution of people's opinions no longer changes. Thus, they are regarded as Bernoulli random variables derived from the steady-state joint distribution, and sampling at time t can be considered as observing part of a realization of f (t) 1 , f (t) 2 , . . . , f (t) n . In partitioned opinion sampling, the population is divided into several disjoint groups V1, V2, . . . , Vm with ni = |Vi|. When we draw yi samples (with replacement) from group Vi at time t, we obtain yi i.i.d. random variables f (t) vi,1 , f (t) vi,2 , . . . , f (t) vi,yi , where vi,j is the j-th sample from group Vi. Partitioned sampling uses ˆ f (t) = ∑mi=1 ni n · ( 1 yi ∑yi j=1 f (t) vi,j ) as the unbiased estimator for the mean population opinion at time t, and the task is to find the optimal allocation (yo 1 , . . . , yom) with sample size budget ∑mi=1 yo i ≤ k which minimizes the sample variance Var[ ˆ f (t) ], a common sample quality measure [Bethel, 1986; Ballin and Barcaroli, 2013; Huang et al., 2017].

One way to achieve best estimate quality for a future time t is to do adaptive sampling to quickly estimate the opinion variance of each group, and then decide the optimal sample size allocation for the real sample event at time t. This corresponds to certain opinion polling practices, for instance, polling after each presidential debates, and preparing for a better sample quality at the election day. We remark that in this setting, past samples are useful to estimate opinion variance within groups, but cannot be directly use to estimate the mean opinion at a future time t, since ˆ f (t) is time-based and using historical samples directly may lead to biased estimates.

More specifically, let Xi be the result of one random sample from group Vi in the steady state. Note that the randomness of Xi comes from both the sampling randomness and the opinion randomness in the steady state. One can easily verify that Var[ ˆ f (t) ] = ∑mi=1 n2i n2 yi Var[Xi], where Var[Xi] is the variance of group Vi, and referred to as the within-group variance. The goal is to use as few samples as possible to estimate within-group variances, and then give the final sample size allocation which minimizes Var[ ˆ f (t) ].

This falls into the CPE-CS framework. In particular, each group Vi corresponds to an arm i, and each withingroup variance Var[Xi] corresponds to the unknown parameter θ∗ i of arm i. The decision space Y is {(y1, . . . , ym) ∈ Zm+ : ∑mi=1 yi ≤ k}. The reward function r(θ; y) is set to be

- ∑mi=1 n2i θi

n2 yi , where the negative sign is because the partitioned opinion sampling problem is a minimization problem. It is non-linear but continuous and separable. Therefore, the problem is an instance of CPE-CS. The oracle for the offline problem can be achieved by a greedy algorithm, denoted as φ(θ), and it satisfies the bi-monotonicity (the design and the analysis of the offline oracle is non-trivial, see the extended version). Thus, the COCI algorithm can be directly applied as follows: 1) ESTi is set to be the variance estimator, i.e., ESTi(Xi,1, . . . ,Xi,s) = 1 s-1 (∑sj=1 X2 i,j - 1s (∑sj=1 Xi,j )2 ), and τ = 2; 2) the condition in line 11 of Algorithm 1 is instantiated by φi(θ-i,t-1 , θi,t-1) ̸= φi(θ-i,t-1, θi,t-1 ).

5 Applying COCI to CPE-L

In Section 2, we already show that the linear class CPE-L is a special case of CPE-CS. In this section, we discuss the implication of applying COCI algorithm to solve CPE-L problems, and compare the sample complexity and implementation efficiency against the CLUCB algorithm in [Chen et al., 2014]. Since the parameter θ∗ is the vector of means of arms, we use the mean estimator and set τ = 1 in COCI.

Recall that for a binary vector y ∈ Y, Sy is defined as {i ∈ [m] : yi = 1}. Chen et al. [2014] use the term reward gap in the formulation of sample complexity. For each arm i ∈ [m], its reward gap ∆i is defined as:

Chen et al. [2014] also define a (reward gap) hardness measure H∆ = ∑mi=1 1 ∆2i . Moreover, for each decision class Y, Chen et al. [2014] define a key quantity width, denoted as width(Y), that is needed for sample complexity. Intuitively, width(Y) denotes the minimum number of elements that one may need to exchange in one step of a series of steps when changing the current decision S ∈ Y into another decision S′ ∈ Y, and for every step of exchange in the series, the resulting decision (subset) should still be in Y. The technical definition is not very relevant with the discussion below, and thus is left in the supplementary material. We remark that width(Y) = O(m).

Given the above setup, Chen et al. [2014] show that with probability 1 - δ, their CLUCB algorithm achieves sample complexity bound

When applying the COCI algorithm to solve CPE-L problems, we are able to obtain the following key connection between consistent optimality radius and the reward gap:

Combining with Theorem 1, we have that COCI could achieve the following sample complexity bound for CPE-L:

The above result has the same sample complexity 2 as in Eq. (5) (with even a slightly better constant). However, with our analysis, we only need the complicated combinatorial quantity width(Y) and the linear reward assumption in the last step. This also suggests that our consistent optimality radius Λi and its associated consistent optimality hardness HΛ are more fundamental measures of problem hardness than the reward gap ∆i and its associated reward gap hardness H∆.

Next we discuss the implementation of the condition in line 11 of COCI for CPE-L. First, because linear functions are monotone, it is easy to see that we only need to check parameters θ on the boundaries of ˆΘt-1 (at most 2|Y| calls to the oracle φ). For simple constraints such as any subsets of size k, it is easy to verify that φ(θ) is bi-monotone in this case, and thus we have efficient implementation of the condition as given in Theorem 3. For more complicated combinatorial constraints, it is still an open question on whether efficient implementation of the condition in line 11 exists when oracle φ is given. The CLUCB algorithm, on the other hand, does have an efficient implementation for all CPE-L problems as long as the oracle φ is given.

Therefore, compared with CLUCB in terms of efficient implementation, COCI can be viewed as taking the tradeoff between the complexity of the reward functions and the complexity of combinatorial constraints. In particular, COCI could handle more complicated nonlinear reward functions on real vectors, and allow efficient implementation (due to bimonotonicity) under simple constraints, while CLUCB deals with complicated combinatorial constraints but could only work with linear reward functions on binary vectors.

6 FutureWork

There are a number of open problems and future directions. For example, one can consider the fixed budget setting of CPE-CS: the game stops after a fixed number T of rounds where T is given before the game starts, and the learner needs to minimize the probability of error Pr[yo ̸= y∗ ]. One may also consider the PAC setting: with probability at least 1 - δ the algorithm should output a decision with reward at most ε away from the optimal reward. This setting may further help to eliminate the requirement of finite decision class Y. Another direction is to combine the advantage of COCI and CLUCB to design a unified algorithm that allows efficient implementation for all CPE-CS problems. How to incorporate approximation oracle instead of the exact oracle into the CPE framework is also an interesting direction.

2 CPE-L in [Chen et al., 2014] assumes R-sub-Gaussian distributions. Our analysis can be adapted to R-sub-Gaussian distributions as well, with the same R2 term appearing in the sample complexity.

Acknowledgments

This work was supported in part by the National Basic Research Program of China Grant 2011CBA00300, 2011CBA00301, the National Natural Science Foundation of China Grant 61033001, 61361136003, 61433014.