{'fraction_non_alphanumeric': 0.047683814705176415, 'fraction_numerical': 0.014001120089607168, 'mean_word_length': 3.9725500596737833, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exploiting Correlation in Finite-Armed Structured Bandits

We consider a structured Multi-Armed bandit problem in which mean rewards of different arms are related through a hidden parameter. We propose an approach that allows generalization of classical bandit algorithms such as UCB and Thompson sampling to the structured bandit setting. Our approach is based on exploiting the structure in the problem to identify some arms as sub-optimal and pulling them only O(1) times. This results in significant reduction in cumulative regret and in fact our algorithm achieves bounded (i.e., O(1)) regret whenever possible. We empirically demonstrate the superiority of our algorithms via simulations and experiments on the Movielens dataset. Moreover, the problem setting we study in this paper subsumes several previously studied framework such as Global, Regional and Structured bandits with linear rewards.


Introduction
The Multi-armed bandit problem [1] (MAB) falls under the umbrella of sequential decision-making problems and is widely studied because of its numerous applications in medical diagnosis [2], system testing [3], scheduling in computing systems [4], and web optimization [5] etc. In the classical K-armed bandit formulation, a player is presented with K arms. At each time step t, she decides to pull an arm k ∈ K and receives a random reward R t with unknown mean µ k . The goal of the player is to maximize their cumulative reward. The seminal work of Lai and Robins [1] proposed the UCB (upper confidence bound algorithm) that balances the exploration-exploitation tradeoff in the MAB problem. Subsequently, several other algorithms such as Thompson Sampling [6] and KL-UCB [7] were proposed and analyzed for the classical MAB setting.
In this work, we study a setting in which rewards corresponding to different arms are related to each other through a hidden parameter θ; see Section 2.1 and Figure 1. Our main goal is to leverage these relations to reduce the amount exploration and thus achieve a cumulative reward that is significantly higher than possible in the classical MAB setting.
There are many practical applications where the model studied here can be useful. For instance, let us consider the example of ad selection, where a company needs to decide which version of the ad it needs to display to the user. It has different versions for the same ad and depending on which ad is displayed the user engagement (in terms of click probability and time spent looking at the ad) is affected. In order to maximize user engagement, the company needs to identify the most appealing ad for the user in an online manner and this is where multiarmed bandit algorithms like UCB, Thompson Sampling and KL-UCB can be helpful. However, classical MAB algorithms are typically based on the assumption that rewards corresponding to all arms are independent of each other. This assumption is unlikely to hold in reality since the user choices corresponding to different versions of an ad are likely to be related to each other; e.g., the choices corresponding to different versions may depend on the age/occupation/income of the user.
Alternatively, contextual bandits [8] can be considered, where the player also observes the context feature of the user to whom ad is displayed (i.e., their age/occupation/income information). By trying to learn a mapping from feature information to the most appealing arm, contextual bandit algorithms prove useful for the application of targeted advertising. However, observing contextual features leads to privacy concerns. Also, the contextual features may not be visible for the users that are signed in anonymously. This raises the question of arXiv:1810.08164v3 [stat.ML] 26 Mar 2019 whether it is possible to do targeted advertising for a user without observing their features.
Apart from ad selection, there are many other applications where the structured bandit problem described above can be useful. For instance, in the dynamic pricing problem [9], a player needs to select the price of a product from a finite set of prices P, and the average revenue in time slot t is a function of the selected price p t and the market size θ. These functions are typically known from literature [10], but the pricing decisions p t need to be made without knowing the market size such that the total revenue is maximized; hence, this problem fits perfectly in our setting.
Other applications of this model include cellular coverage optimization [11], drug dosage optimization [12] and System diagnosis (See [11,12] for a description on how µ k (θ) are known through literature in these cases). Our general treatment of the structured bandit setting allows our work to be helpful in all these problems.
Motivated by these, we consider a structured multi-armed bandit problem in which the mean reward of different arms are related through a common hidden parameter θ. Specifically, the expected reward of arm k is given as E [R k |θ] = µ k (θ). In the setting considered, the mean reward functions, µ k (θ), are known to the player but the true value of shared parameter θ * is unknown. The dependence on the common parameter introduces a structure in this MAB problem -the rewards observed from an arm can provide information about mean rewards from other arms. In the aforementioned example of ad selection, the mean reward mappings from user contexts to different versions of ad can be learned from paid surveys in which users participate with their consent. Such structured bandit models have been studied in the past [9,12,13,14,15,16], but with certain restriction on the mean reward mappings µ k (θ). In this work, we allow a general treatment of the problem that poses no restriction on the mean reward mappings and in fact subsumes the models studied before; see 2.2 for details.

Main Contributions.
1) We consider a general setting for the structured multiarmed problem which subsumes recently studied models such as the Global Bandits [9], Regional Bandits [12] and Structured bandits with linear functions [13].
2) We develop a novel approach that exploits the structure of the bandit problem to identify sub-optimal arms. In particular, we generate an estimate of θ at each round to identify competitive and non-competitive arms. The non-competitive arms are identified as sub-optimal without having to pull them. We refer to this identification as implicit exploration. This implicit exploration is combined with traditional bandit algorithms such as UCB and Thompson sampling to design UCB-C and TS-C algorithms.
3) We perform finite-time regret analysis of our algorithm and show that it performs better than UCB. In fact, the proposed UCB-C algorithm ends up pulling non-competitive arms only O(1) times. Due to this only C − 1 out of the K − 1 sub-optimal arms are pulled O(log T ) times, where C denotes the number of competitive arms. The value of C can be much less than K and can even be 1, in which case our algorithm achieves bounded regret! We also prove that our algorithm achieves bounded regret whenever possible.
4) The design of UCB-C makes it easy to extend other classical bandit algorithms (such as Thompson sampling [6], KL-UCB [7], etc.) in the structured bandit setting. The ability to incorporate any classical MAB algorithm is an important advantage of our approach as algorithms such as Thompson sampling have attracted great attention recently due to their superior empirical performance [17]. In particular, the extension to Thompson sampling was deemed to be not immediately possible for the UCB-S algorithm [18] developed for a structured MAB problem similar to ours.

5)
We perform experiments on the MOVIELENS dataset to demonstrate the applicability of the UCB-C and TS-C algorithms. Our experimental results show significant improvement over the performance of classical bandit strategies.

Problem Formulation
Consider a multi-armed bandit setting with K arms K = {1, 2 . . . , K}. At each round t, the player pulls arm k t ∈ {1, 2 . . . K} and observes the reward R t . The reward R t is a random variable with mean µ kt (θ) = E [R t |θ, k t ], where θ is a fixed, but unknown parameter which lies in a known set Θ, as illustrated in Figure 1. Our formulation allows the set Θ to be a countable or uncountable set. The hidden parameter θ can also be a vector, however we focus on scalar θ for brevity purposes. We denote the unknown true value of parameter θ by θ * .
The mean reward functions {µ 1 (θ), µ 2 (θ), . . . , µ K (θ)} : Θ → R can be arbitrary functions, and they are known to the player. However, the conditional distribution of rewards i.e., p(R t |θ, k) is not known. Throughout the paper, we assume that the rewards R t are sub-Gaussian with variance proxy σ 2 , i.e., E [exp (s (R t − E [R t ]))] ≤ exp σ 2 s 2 2 ∀s ∈ R, and σ is known to the player. Both of these assumptions are common in the multi-armed bandit literature [18,19]. In particular, the sub-Gaussianity of rewards enables us to apply Hoeffding's inequality, which ... θ Figure 1: Structured bandit setup: mean rewards of different arms share a common hidden parameter θ.
is essential for the analysis of regret (defined below).
The objective of the player is to select arm k t in round t so as to maximize her cumulative reward T t=1 R t after T slots. If the player had known the true value θ * , then she would always pull the arm k * = arg max k∈K µ k (θ * ) which yields the highest mean reward for the parameter θ * as that arm would result in the maximum expected cumulative reward. We refer to this arm k * = arg max k∈K µ k (θ * ) as the optimal arm. Thus, maximizing the cumulative reward is equivalent to minimizing the cumulative regret, which is defined as where n k (T ) is the number of times arm k is pulled in T slots and ∆ k µ k * (θ * ) − µ k (θ * ) is the sub-optimality gap of arm k or the difference between mean reward of the optimal arm k * and that of arm k. The cumulative regret quantifies the performance of a player in comparison to an oracle that pulls the optimal arm at each round.
Minimizing the cumulative regret is in turn equivalent to minimizing n k (T ), the number of times each sub-optimal arm k = k * is pulled. In this work, we exploit the knowledge of functions µ k (θ) to reduce n k (T ) of certain arms to O(1) instead of the typical O(log T ) scaling.

Connection with Previously Studied
Multi-armed Bandit Frameworks Since we do not make any assumptions on the functions {µ 1 , µ 2 , . . . , µ K }, our model subsumes several previously studied frameworks [9,12,13] and is applicable more generally. The similarities and differences between our model and existing works are discussed next.
Classical MAB. Under the classical Multi-armed bandit setting, the rewards obtained from each arm are independent. By considering θ = (θ 1 , θ 2 , . . . , θ K ) and µ k = θ k , our setting reduces to the classical MAB setting. Our proposed algorithm will in fact perform UCB/Thompson sampling ( [1,20]) in this special case.
Structured bandits with linear rewards [13]. In [13], the authors consider a similar model with a common hidden parameter θ ∈ R, but the mean reward functions, µ k (θ) are linear in θ. Under this assumption, they design a greedy policy that achieves bounded regret. Our formulation places no such restriction on the reward functions.
In the special case when µ k (θ) are linear, our proposed algorithm also achieves bounded regret.
Global Bandits [9]. In [9], a model where mean reward functions are dependent on a common scalar parameter is studied. A key assumption in [9] is that the mean reward functions are invertible and Hölder-continuous. Under these assumptions, they demonstrate that it is possible to achieve bounded regret through a greedy policy. In contrast, our work makes no assumptions on the nature of the functions µ k (θ). In fact, when reward functions are invertible, our algorithms also achieve bounded regret.
Regional Bandits [12]. The paper [12] generalizes global bandits by considering that there are M common unknown parameters, that is, θ = (θ 1 , θ 2 , . . . , θ M ). The mean reward of each arm depends on exactly one of these M parameters, θ m , and it is also assumed that the mean reward functions are invertible and Hölder-continuous in θ m . The setting described in [12] is captured in our formulation with vector θ = (θ 1 , θ 2 , . . . , θ M ). Our problem set-up allows arbitrary µ k (θ) that can depend on any subset of the M parameters and need not be invertible or Hölder-continuous.
Finite-armed Generalized Linear bandits [15]. Under the finite-armed linear bandit setting [15], the reward function of arm x k is θ x k . Here, θ is the shared unknown parameter. Our proposed algorithms (designed for a general framework) work even in the linear bandit setting and through simulations we demonstrate its performance relative to the GLM-UCB [14] (an algorithm designed for linear bandit setting). For the case when µ k (θ) = g( θ x k ), our setting becomes the generalized linear bandit setting [14], for some known function g.
Minimal Exploration in Structured Bandits [21]. The problem formulation in [21] is closely related to this paper. The focus of [21] is to obtain asymptotically optimal regret for the regimes when regret scales as log(T ). When all arms are non-competitive (the bounded regret case), the solution to the optimization problem described in [21, Theorem 1] becomes 0, causing the algorithm to get stuck in the exploitation phase. Also, [21] assume the knowledge of the shape of reward distribution (for example, Gaussian with unknown mean), we only assume that the rewards are sub-Gaussian. Moreover, they assume θ → µ k (θ) is continuous, while we make no such assumption. This also restricts [21] to settings where θ lies in an uncountable set, whereas our setting allows θ to lie in a countable set as well.
Finite-armed structured bandits [18]. The work clos- Figure 2: An example showing a 3-armed bandit problem. The figures show the mean rewards of the three arms as a function of θ. Since the true parameter θ * = 3, Arm 2 is the optimal arm while Arms 1 and 3 are sub-optimal. Figure 3: The samples of Arm 2, can be used to obtain empirical mean of arm 2. The empirical mean can be used to construct a region (shaded pink) within which µ 2 (θ * ) lies with high probability. This region can be used to identify a the high confidence set Θ t that contains the true parameter θ * with high probability.
est to ours is [18]. The authors in [18] consider the same model that we consider and propose the UCB-S algorithm, which is a UCB-style algorithm for this setting. Our approach allows us to extend our UCB style algorithm to other classical bandit algorithms such as Thompson sampling. A Thompson sampling-style algorithm was not proposed in [18]. Through simulations, we make comparisons of our proposed algorithms against the UCB-S algorithm proposed in [18].

Intuitions for Developing an Algorithm
In our framework, since mean rewards of all arms are dependent on a common parameter, obtaining an estimate of θ * from the samples observed till round t can give us some (incomplete) information about the mean rewards of all arms. This information can then be used to reduce the need for explicit exploration. Identifying sub-optimal arms through this estimate of θ * can be thought of as implicit exploration.
We illustrate this key idea via the the example shown in Figure 2. In this case, the true parameter θ * = 3 and the mean rewards of Arms 1, 2 and 3 at θ * are 2, 3, and 1 respectively (marked by the blue dots). Thus, the optimal arm in this setup is Arm 2. Suppose that the player uses the samples observed from Arm 2 until time t to obtain an empirical estimate of the mean reward Using this empirical estimate, the player can construct a region in which µ 2 (θ * ) lies with high probability. Figure 3 illustrates such a region in shaded pink color. This region can then be used to identify the set of valuesΘ t within which the true parameter θ * lies with high probability. For example, in Figure 3 that region is the set [1.5, 4.5]. If θ * indeed lies in this set, then we can infer that Arm 3 cannot be optimal as its mean reward is less than that of Arm 2 for all θ ∈ [1.5, 4.5]. However, Arm 1 may still be better than Arm 2 as it has higher mean reward than Arm 2 for some values of θ ∈ [1.5, 4.5]. This provides an example where we implicitly explore Arm 3 without pulling it. As Arm 3 cannot be optimal in the set [1.5, 4.5], we refer to it as non-competitive with respect to the set [1.5, 4.5]. On the other hand, we call Arm 1 and 2 competitive with respect to [1.5, 4.5] as they are optimal for at least one θ in this set.
We formalize this idea of identifying competitive and non-competitive arms and propose the UCB-C and TS-C algorithms in Section 3 below. In Section 4 we prove that UCB-C can reduce a K-armed bandit problem to a C-armed bandit problem, where C ≤ K is the number of competitive arms. In certain regimes (when C = 1), we get bounded (i.e., not scaling with T ) regret as we will show in Section 4.

Proposed Algorithms: UCB-C and TS-C
Classical bandit algorithms such as Thompson sampling and Upper Confidence Bound (UCB) are often termed as index-based policies. At every time instant, these policies maintain an index for each arm, and select the arm with the highest index in the next time slot. More specifically, at each round t + 1, UCB selects the arm whereμ k (t) is the empirical mean of arm k obtained from the n k (t) samples obtained till t.
Under Thompson sampling, we select the arm k t+1 = arg max k∈K S k,t at time step t. Here, S k,t is the sample obtained from the posterior distribution of µ k . That is, Since mean rewards are correlated through the hidden parameter θ * in the structured bandit model, obtaining an estimate of θ * can help identify the optimal arm. In our approach, we will identify subset of arms, called the competitive arms, through the estimate of θ * and then perform UCB or TS over that set of arms. We now define the notions ofΘ t -Competitive andΘ t -Non-competitive arms, which are a key component in the design of UCB-C and TS-C Algorithms.

Competitive and Non-Competitive Arms
From the samples observed till time step t, one can construct a confidence setΘ t . The setΘ t represents the set of values in which the true parameter θ * lies with high confidence, based on rewards observed until time t. Next, we define the notions ofΘ t -Competitive and Θ t -Non-competitive arms.
Intuitively, an arm isΘ-Competitive if it is optimal for at least one θ in the confidence setΘ. Similarly, we define â Θ-Non-competitive arm as follows. Definition 2 (Θ-Non-competitive arm). An arm k is said to beΘ-Non-competitive if µ k < max ∈K µ (θ), for all θ ∈Θ.
Intuitively, if an arm isΘ-Non-competitive, it means that it cannot be optimal if the true parameter lies inside the confidence setΘ. This allows us to identify theΘ-Noncompetitive arm as sub-optimal under the assumption that the true parameter θ * is in the setΘ.

Components of Our Algorithm
Motivated with the above discussion, we propose the following algorithm. At each step t + 1, we: 1. Construct a confidence setΘ t from the samples observed till time step t.
3. Play a bandit algorithm (UCB or Thompson sampling) among arms which areΘ t -Competitive and choose the next arm k t+1 accordingly.
The formal description of this algorithm with UCB and Thompson sampling as final steps is given in Algorithm 1 and Algorithm 2, respectively. Below, we explain the three key components of these algorithms.
Step 1: Constructing a confidence set,Θ t . From the samples observed till time step t, We define the confidence set as follows: Confidence set construction:

8: end for
Hereμ k is the empirical mean of rewards obtained in n k samples of arm k. Using the confidence bound on mean of each arm, we constructΘ t that contains values of θ, which lead to mean reward within confidence interval of mean of each arm.
Step 2: IdentifyingΘ t -Non-competitive arms. At each time step t + 1, we define the set C t as the set ofΘ t -Competitive arms, that includes all arms k that satisfy µ k = max ∈K µ (θ) for some θ ∈Θ t . The rest of the arms, termed asΘ t -Non-competitive, are eliminated for round t + 1 and are not considered in the next part of the algorithm. Note that these arms can beΘ t -Competitive in subsequent rounds.
Step 3: Play bandit algorithm amongΘ t -Competitive arms. After identifying theΘ t -Competitive arms, we use classical bandit algorithms such as UCB and Thompson sampling to decide which arm to play at time step t + 1 as specified in (2) and (3) respectively.
It is important to note that the last step of our algorithm can utilize any one of the classical bandit algorithms. This allows us to easily define a Thompson sampling algorithm which has attracted great attention [6,17,22] for the structured bandits problem considered in this paper. The ability to employ any bandit algorithm in its last step is an important advantage of our algorithm. For instance, the extension to Thompson sampling was deemed to be not possible for the UCB-S algorithm proposed in [18]. Sample S k,t ∼ N μ k (t), σ 2 n k (t) . 5: end for 6: k t+1 = arg max k∈Ct S k,t 7: Update empirical mean,μ k and n k for all arm k.

Regret Analysis and Bounds
In this section, we evaluate the performance of the UCB-C algorithm through a finite-time analysis of the expected cumulative regret defined as where ∆ k = µ k * (θ * ) − µ k (θ * ) and n k (T ) is the number of times arm k is pulled in a total of T time steps. To analyze the expected regret, we need to determine E [n k (T )] for each sub-optimal arm k = k * .
In this section we derive E [n k (T )] separately for competitive and non-competitive arms and show that it is O(1) for non-competitive arms. For the purpose of regret analysis, we first define confidence set Θ * and formally define the notion of competitive and non-competitive arms. Define the set Θ * = {θ : µ k * (θ) = µ k * (θ * )}. We can view Θ * as the confidence set Θ t after the optimal arm is sampled infinitely many times. A Θ * ( ) -non-competitive arm is then defined as follows.
Definition 3 (Θ * ( ) -non-competitive arm). We call an arm k as Θ * ( ) -non-competitive if where Θ * ( ) is an expanded version of Θ * that allows a deviation of at most from the optimal mean reward. For each arm k, we define k as the largest for which it is Θ * ( ) -non-competitive, where the set Θ * ( ) is the expanded version of Θ * . An arm is competitive (according to Definition 1) if k = 0, otherwise it is said to be Θ * ( k ) -Non-Competitive.
Our first result shows that expected pulls for any arm (competitive or non-competitive) is O(log T ).
Theorem 1 (Expected pulls for any arm). The expected number of times any arm is pulled by UCB-C Algorithm is upper bounded as Our next result shows that the expected number of pulls for an Θ * ( k ) -non-competitive arm are bounded.

Theorem 2 (Expected pulls of Non-competitive Arms).
If an arm k is Θ * ( k ) -non-competitive for some k > 0, then the number of times it is pulled by UCB-C is upper bounded as where, Plugging the results of Theorem 1 and Theorem 2 in (5) yields the following bound on the expected regret of the UCB-C Algorithm. Note that in this work we consider a finite-armed setting and hence are focused on studying the scaling of regret with respect to T and not with K.
Theorem 3 (Regret upper bound). For α > 3, the expected regret of the UCB-C Algorithm is upper bounded as, Here, U given in Theorem 2. The set C denotes the set of competitive arms and C is the cardinality of that set.
Reduction in the effective number of arms. The classic UCB algorithm that is agnostic to the structure of the problem pulls each of the (K − 1) sub-optimal arms O(log T ) times. In contrast, our algorithm pulls only (C − 1) sub-optimal arms O(log T ) times, where C ≤ K.
In fact, when C = 1, all sub-optimal arms are pulled only O(1) times, leading to a bounded regret. The value of C depends on the specific correlation structure, i.e., the functions µ k (θ), and the hidden parameter θ * . Cases with C = 1 can arise quite often in practical settings. For example, when the optimal arm k * is invertible around θ * , the set Θ * becomes a singleton; i.e., there is just a single θ ∈ Θ that leads to µ k * (θ * ). In that case, all sub-optimal arms become non-competitive and our UCB-C algorithm returns bounded (i.e., O(1)) regret.
We now show that the UCB-C algorithm achieves bounded regret whenever possible. We do so by analyzing a lower bound obtained in [21].
Proposition 1 (Lower bound). For any uniformly good algorithm [1], and for any θ ∈ Θ, we have: An algorithm π is uniformly good if Reg π (T, θ) = o(T a ) for all a > 0 and all θ ∈ Θ.
The proof of this proposition, given in Appendix, follows from a lower bound derived in [21]. This lower bound leads us to the following observation.
Remark 1 (Bounded regret whenever possible). The result on lower bound in Proposition 1 shows that sublogarithmic regret is possible only when C = 1. In the case when C = 1, our proposed algorithm achieves a bounded regret (see Theorem 3). This implies that the UCB-C algorithm is able to achieve bounded regret whenever possible and reduce the number of effective arms for the cases when regret is logarithmic.

Simulation Results
We now study the empirical performance of the proposed algorithms. For all simulations we choose α = 3. Rewards are drawn from the distribution N (µ k (θ * ), 4), i.e., σ = 2. For each case considered, we run 100 independent experiments and present the average regret. We demonstrate i) how UCB-C reduces the number of arms selected O(log T ) times; ii) the comparison with UCB-S [18]; iii) how our algorithms perform for multi-dimensional θ; and iv) the performance of our algorithms in the linear bandit setting.
Reduction in the effective number of arms. In Figure 4 we compare the regret of the UCB-C algorithm with classic UCB for the example considered in Figure 4. For θ * = 0.5, Arm 2 is optimal and Arms 1 and 3 are noncompetitive. As expected from our regret analysis, in Figure 5(a) the UCB-C algorithm achieves bounded regret, while the regret of UCB grows logarithmically in Arm 1 Arm 2 Arm 3 Figure 4: An example where Arm 2 is optimal for θ * ∈ [0, 1], Arm 3 is optimal for θ * ∈ [1, 2.5] and Arm 1 is optimal for θ * ∈ [2.5, 6].  Figure 5(c) shows the case where θ * = 2.8, leading to Arm 1 being optimal and all the arms being competitive. As the UCB-C algorithm uses samples from all arms to generate the confidence setΘ t , it achieves empirically smaller regret for this setting than the UCB algorithm even when all arms are competitive.
Comparison with UCB-S [18]. We now compare the performance of our UCB-C and TS-C algorithms against the UCB and UCB-S Algorithm proposed in [18]. We consider the example shown in Figure 6. We plot the cumulative regret of the UCB, UCB-S, UCB-C and TS-C algorithms over 50000 time steps for the values of θ * between 0 and 5 in Figure 7. When θ * is below 3, UCB-S, UCB-C and TS-C all obtain smaller regret than UCB as they are able to identify the sub-optimal arm as noncompetitive. For θ * ∈ (3, 5), UCB-C has a performance similar to that of UCB as sub-optimal arm is competitive.
We see that when θ * = 3.25, UCB-S achieves a regret which is quite large compared to even UCB. This is because with θ * = 3.25, Arm 1 is optimal but the samples from Arm 1 does not allow accurate estimation of θ as its mean reward is constant over a large region of θ values 0 2 4 6 -1 0 1 θ µ(θ) Arm 1 Arm 2 Figure 6: Arm 2 is optimal for θ * ∈ [0, 3] and Arm 1 is optimal for θ * ∈ [3,5].  Figure 6 over 50000 runs compared over different values of θ * (at some of which Arm 2 is optimal). Since the UCB-S algorithm selects k t+1 = arg max k∈K sup θ∈Θt µ k (θ), the sup leads it to select the sub-optimal Arm 2 a large number of times. We also see that TS-C does not suffer from the same issue and performs significantly better than all other algorithms. We attribute this to the fact that Thompson sampling can offer significant empirical improvements over UCB. This highlights the benefits of being able to incorporate Thompson sampling in a correlated MAB algorithm which was deemed to be not possible in [18].
Multi-Dimensional θ. Our formulation allows for θ to be a vector as well. To demonstrate this, we consider a case where θ = (θ 1 , θ 2 ) and θ 1 , θ 2 ∈ [−1, 1]. The three arms have mean reward functions µ 1 ( θ) = θ 1 + θ 2 , µ 2 ( θ) = θ 1 − θ 2 and µ 3 ( θ) = max(|θ 1 |, |θ 2 |). Note that this setting cannot be captured by linear bandit or generalized linear bandit models. Figure 8 shows the performance of UCB-C and TS-C algorithms against the UCB algorithm in this setting. For θ * = (0.9, 0.2), Arm 1 is optimal and Arm 3 is Non-Competitive, due to which we see empirical superiority of UCB-C and TS-C algorithms over UCB. For the case where θ * = (−0.2, 0.1), Arm 3 is optimal and all arms are competitive. As as result, UCB-C and UCB give the same performance, while TS-C performs better due to the empirical superiority of the Thompson sampling in this setting. der the finite-armed linear bandit setting, the reward function of arm k is θ x k , where x k is a known vector associated with arm k. When µ k (θ) = θ x k , our setting covers the linear bandit setup. We now compare the performance of our UCB-C and TS-C algorithms against the GLM-UCB algorithm, which is specifically designed for linear bandits. In the example considered, Θ = [0, 1] × [0, 1] and we consider three arms x 1 = (2, 1), x 2 = (1, 1.5) and x 3 = (3, −1). Figure 9 shows the results of the simulation performed. We see that when hidden parameter θ = (0.9, 0.9), our algorithm outperforms the GLM-UCB algorithm [14]. In the case when θ = (0.5, 0.5), GLM-UCB has better performance than UCB-C however TS-C performs the best. This occurs due to the fact that Thompson sampling is empirically better than UCB in this setting. It is important to note that while UCB-C and TS-C are designed for a much broader class of problems, they still show competitive performance relative to specialized algorithms (i.e., GLM-UCB) in the linear bandit setting.

Experiment with MOVIELENS dataset
We now show the performance of UCB-C and TS-C on a real-world dataset. As mentioned earlier, structured bandits might be useful in targeted advertising without observing the user context. We use the MOVIELENS dataset [23], which contains a total of 1M ratings made by 6040 users for 3883 movies to demonstrate how UCB-C and TS-C can be deployed in practice. In particular, we will demonstrate the superiority of our algorithms over the classical UCB in movie recommendations.
We consider the MOVIELENS dataset, in which the there are 106 different types of users (based on their age and occupation features) and there are 18 different genres of movies. We refer to each type of user as a meta-user (so, there are 106 meta-users), which corresponds to the parameter θ in our setup. For example, one meta-user in the data-set contains 18-25 year old college students. The users have given ratings to the movies on a scale of 1 to 5. Each movie is associated with one (and in some cases, multiple) genres. For the experiments, of the possibly multiple genres for each movie one is randomly allotted.
For a particular user whose features is unknown (i.e., the true value of the θ is hidden), our goal is to recommend a movie sequentially from the genre (i.e., arm) that the user has the highest mean rating for. We use a part of the dataset (50%) as the training dataset, on which the mean reward mappings from meta-users to different genres are learned. The learned mappings from meta users (θ) to genres (arms) are shown in the appendix. The learned mappings indicate that the mean-reward mappings of meta-users for different genres are related to one another. For example, on average 56+ year old retired users tend to like documentaries and tend to dislike children's movies. Such dependencies are learned in the mapping from θ to µ k (θ) in training. In order to implement it for recommendations or advertising, these mappings could be learned from surveys in which users participate with their consent.
The goal is to recommend the most preferred genre to an unknown meta-user. To test the algorithm, we select a meta-user θ * from the remaining 50% of the data, i.e., the test data. At every round t, the MAB algorithm selects a genre to recommend to the meta-user. The rating corresponding to that genre is obtained by sampling randomly from the available reward samples of the (metauser, genre) pairing. This process is repeated for a total of 15000 rounds. We measure the regret of algorithm in the test data by evaluating T t=1 µ k * (θ * ) − µ kt (θ * ) on the test data. We report the results in Figure 10 for two different types of meta-users (i.e., θ * ), i) 18-25 year old college students and ii) 25-34 year old executives. Figure 10 shows that UCB-C and TS-C algorithms are able to achieve significantly lower regret than UCB as only a few arms are pulled O(log T ) times. We plot results for two different values of θ * , similar improvements are seen for other values of θ * as well. This experiment demonstrates that it is indeed possible to provide better recommendations than UCB without viewing the contextual (and private) information of the users. Our approach can be useful in broader settings for advertising or recommendations without using personal information.

Concluding Remarks
In this work, we studied a structured bandit problem in which the mean rewards of different arms are related through a common hidden parameter. This is done under a general framework without any assumptions on the mean reward functions, due to which our model subsumes several previously studied frameworks [9,12,13]. We developed an approach that allows identifying some arms as sub-optimal without exploring them explicitly. Through finite time regret analysis, we showed that the resulting UCB-C algorithm reduces the K-armed bandit problem to a C-armed bandit problem in the sense that only C − 1 ≤ K − 1 of the sub-optimal arms are chosen O(log T ) times. We also showed that UCB-C achieves bounded regret whenever possible. Our approach allows extension of any classical bandit strategy in the structured bandit setting. Through experiments on the MOVIE-LENS dataset, we demonstrated the empirical superiority of UCB-C and TS-C algorithms over other approaches.
Ongoing work includes the finite-time regret analysis of TS-C algorithm. An interesting direction would be to study the case where θ is random with an unknown distribution. We also plan to study the best-arm identification problem in the same setting.

SUPPLEMENTARY MATERIAL A Lower bound
We use the following result of [21] to state Proposition 1.
We see that the solution to the optimization problem (10) is L(θ) = 0 only when the set Λ(θ) is empty. The set Λ(θ) being empty corresponds to a case where all suboptimal arms are non-competitive. This implies that sublogarithmic regret is possible only when C = 1, i.e there is only one competitive arm, which is the optimal arm, and all other arms are non-competitive. It is assumed that reward distribution of an arm k is parameterized by the mean µ k of arm k; this ensures that if µ k (θ) = µ k (λ) then we have D(θ, λ, k) = 0.

B Proof for the UCB-C Algorithm
Fact 1 (Hoeffding's inequality). Let Z 1 , Z 2 , . . . Z T be i.i.d. random variables, where Z i is σ 2 sub-gaussian with mean µ, then Hereμ is the empirical mean of the Z 1 , Z 2 . . . Z T .
Lemma 1 (Standard result used in bandit literature). If µ k,n k (t) denotes the empirical mean of arm k by pulling arm k n k (t) times through any algorithm and µ k denotes the mean reward of arm k, then we have Proof. Let Z 1 , Z 2 , ...Z t be the reward samples of arm k drawn separately. If the algorithm chooses to play arm k for m th time, then it observes reward Z m . Then the probability of observing the event (μ k,n k (t) − µ k ≥ , τ 2 ≥ n k (t) ≥ τ 1 ) can be upper bounded as follows, Lemma 2. The Probability that the difference between the true mean of arm k and its empirical mean after t time slots is more than 2ασ 2 log t n k (t) is upper bounded by 2t 1−α , i.e., Pr |µ k (θ * ) −μ k | ≥ 2ασ 2 log t n k (t) ≤ 2t 1−α .
We have (19) from union bound and is a standard trick to deal with the random variable n k (t) as it can take values from 1 to t (Lemma 1). The true mean of arm k is µ k (θ * ). Therefore, ifμ k,m denotes the empirical mean of arm k taken over m pulls of arm k then, (20) follows from Fact 1 with in Fact 1 being equal to 2ασ 2 log t n k (t) .
Proof. Observe that, = Pr k∈K |µ k (θ * ) −μ k,n k (t) | ≥ 2ασ 2 log t n k (t) Pr |µ k (θ * ) −μ k,n k (t) | ≥ 2ασ 2 log t n k (t) Pr |µ k (θ * ) −μ k,m | ≥ 2ασ 2 log t m We are usingμ k,m to denote the empirical mean of rewards from arm k obtained from it's m pulls. Here (23) follows from definition of confidence set and (24) follows from union bound. We have (25) from union bound and is a standard trick to deal with the random variable n k (t) as it can take values from 1 to t (Lemma 1). Inequality (26) follows from Hoeffding's lemma. for some constant t 0 > 0, then, ∀t > t 0 , where k = k * is a suboptimal arm.