AdaLinUCB: Opportunistic Learning for Contextual Bandits

1 Introduction

In sequential decision making problems such as contextual bandits [Auer, 2002; Chu et al., 2011; Abbasi-Yadkori et al., 2011; Langford and Zhang, 2008], there exists an intrinsic trade-off between exploration (of unknown environment) and exploitation (of current knowledge). Existing algorithm design focuses on how to balance such a trade-off appropriately under the implicit assumption that the exploration cost remains the same over time. However, in a variety of application scenarios, the exploration cost is time varying and situation-dependent. Such scenarios present an opportunity to explore more when the exploration cost is relatively low and exploit more when that cost is high, thus adaptively balancing the exploration-exploitation trade-off to reduce the overall regret. Consider the following motivating examples.

1 The supplementary material of this paper is available at: https: //github.com/xiaoxiao01/IJCAI19/blob/master/Supplementary.pdf

Motivating scenario 1: return variation in recommendations. Contextual bandits have been widely used in recommendation systems [Li et al., 2010]. In such scenarios, the candidate articles/products to be recommended are considered as the arms, the features of users as the context, and the click-through rate as the reward (i.e., the probability that a user accepts the recommendation). However, note that the monetary return of a recommendation (if accepted) can differ depending on 1) timing (e.g., holiday vs. non-holiday season) and 2) users with different levels of purchasing power or loyalty (e.g., diamond vs. silver status). Because the ultimate goal is to maximize the overall monetary reward, intuitively, when the monetary return of a recommendation (if accepted) is low, the monetary regret of pulling a suboptimal arm is low, leading to a low exploration cost, and correspondingly, high returns lead to high regret and high exploration cost.

Motivating scenario 2: load variation for network configuration. In computer networks, there are a number of parameters that can be configured and have a large impact on overall network performance. For example, in cellular networks, a cell tower can configure transmission power, radio spectrum, antenna, etc., that can affect network performance such as coverage, throughput, and quality of service. Contextual bandit can be applied in network configuration [Chuai et al., 2019]. In such problems, the goal of network configuration can be improving network performance for peak load scenario. In such a scenario, a possible configuration of a cellular base station can be considered as an arm, the characteristics of the cell station such as coverage area as the context, and network performance such as throughput as reward. However, network traffic load fluctuates over time, and thus the actual regret of using a suboptimal configuration varies accordingly. Specifically, when the network load is low, dummy traffic can be injected into the network so that the total load (real plus dummy load) is the same as the peak load. In this manner, we can seek the optimal configuration under the peak load even in off-peak hours. Meanwhile, the regret of using a suboptimal configuration is low since the real load affected is low. In practice, the priority of the dummy traffic can be set to be lower than that of the real traffic. Because the network handles high priority traffic first, low priority traffic has little or no impact on the high priority traffic[Walraevens et al., 2003]. Thus, the regret on the actual load can be further reduced, leading to a low or even negligible exploration cost.

Opportunistic Contextual Bandits. Motivated by these application scenarios, we study opportunistic contextual bandits in this paper, focusing on the contextual bandit setting with linear payoffs. Specifically, we define opportunistic contextual bandit as a contextual bandit problem with the following characteristic: 1) The exploration cost (regret) of selecting a suboptimal arm varies depending on a time-varying external factor that we called the variation factor. 2) The variation factor is revealed first so that the learning agent can decide which arm to pull depending on this variation factor. As suggested by its name, in opportunistic contextual bandits, the variation of this external variation factor can be leveraged to reduce the actual regret. Further, besides the previous two examples, opportunistic contextual bandit algorithms can be applied to other scenarios that share these characteristics. We also note that this can be considered as a special case of contextual bandits, by regarding the variation factor as part of context. However, the general contextual bandit algorithms do not take advantage of the opportunistic nature of the problem, and can lead to a less competitive performance.

Contributions. In this paper, we propose an Adaptive Upper-Confidence-Bound algorithm for opportunistic contextual bandits with Linear payoffs (AdaLinUCB). The algorithm is designed to dynamically balance the explorationexploitation trade-off in opportunistic contextual bandits. To be best of our knowledge, this is the first work to study opportunistic learning for contextual bandits. We focus on the problem-dependent bound analysis here, which is a setting that allows a better bound to be achieved under stronger assumptions. To the best of our knowledge, such a bound does not exist for LinUCB in the existing literature. In this paper, we prove problem-dependent bounds for both the proposed AdaLinUCB and the traditional LinUCB algorithms. Both algorithms have a regret upper bound of O ((logT)2 ), and the coefficient of the AdaLinUCB bound is smaller than that of LinUCB. Furthermore, using both synthetic and real-world large-scale dataset, we show that AdaLinUCB significantly outperforms other contextual bandit algorithms, under large exploration cost fluctuations.

2 RelatedWork

Contextual bandit algorithms have been applied to many real applications, such as display advertising [Li et al., 2011] and content recommendation [Li et al., 2010; Bouneffouf et al., 2012]. In contrast to the classic K-arm bandit problem [Auer et al., 2002; Chapelle and Li, 2011; Agrawal, 1995], side information called context is provided in contextual bandit problem before arm selection [Auer, 2002; Chu et al., 2011; Abbasi-Yadkori et al., 2011; Langford and Zhang, 2008]. The contextual bandits with linear payoffs was first introduced in [Auer, 2002]. In [Li et al., 2010], LinUCB algorithm is introduced based on the "optimism in the face of Uncertainty" principal for linear bandits. The LinUCB algorithm and its variances are reported to be effective in real application scenarios [Li et al., 2010; Wu et al., 2016; Wang et al., 2016; Wang et al., 2017]. Compared to the classic K-armed bandits, the contextual bandits achieves superior performance in various application scenarios [Filippi et al., 2010].

Although LinUCB is effective and widely applied, its analysis is challenging. In the initial analysis effort [Chu et al., 2011], instead of analyzing LinUCB, it presents an O(√T ln3 (T)) regret bound for a modified version of LinUCB. The modification is needed to satisfy the independent requirement by applying Azuma/Hoeffding inequality. In another line of analysis effort, the authors in [Abbasi-Yadkori et al., 2011] design another algorithm for contextual bandits with linear payoffs and provide its regret analysis without independent requirement. Although the algorithm proposed in [Abbasi-Yadkori et al., 2011] is different from LinUCB and suffers from a higher computational complexity, the analysis techniques are helpful.

The opportunistic learning has been introduced in [Wu et al., 2018] for classic K-armed bandits. However, we note that opportunistic learning exists for any sequential decision making problem. In [Bouneffouf et al., 2012], the authors study into contextual bandits with HLCS (High-Level Critical Situations) set, and proposes a contextual-ϵ-greedy policy, a policy that has an opportunistic nature since the ϵ (exploration level) is adaptively adjusted based on the similarity to HLCSs (importance level). However, it only introduces a heuristic algorithm, and does not present a clearly formulation of opportunistic learning. Furthermore, the policy design in [Bouneffouf et al., 2012] implicitly makes the assumption that the contexts in HLCS have already been explored sufficiently beforehand, which is not a cold-start problem. To the best of our knowledge, no prior work has made formal mathematical formulation and rigorous performance analysis for opportunistic contextual bandits.

The opportunistic linear contextual bandits can be regarded as a special case of non-linear contextual bandits. However, general contextual bandit algorithms such as KernelUCB [Valko et al., 2013] do not take advantage of the opportunistic nature of the problem, and thus can lead to a less competitive performance, as shown in Appendix E.3 of the supplementary material for more details. Moreover, KernelUCB suffers from the sensitivity to hyper-parameter tuning, and the extremely high computational complexity for even moderately large dataset, which limits its application in real problems.

3 SystemModel

We use the following notation conventions. We use ‖x‖2 to denote the 2-norm of a vector x ∈ Rd . For a positive-definite matrix A ∈ Rd×d , the weighted 2-norm of vector x ∈ Rd is defined by ‖x‖A = √x⊤Ax. The inner product of vectors is denoted by 〈·, ·〉, that is, 〈x, y〉 = x⊤y. Denote by λmin(A) the minimum eigenvalue of a positive-definite matrix A. Denote by det(A) the determinant of matrix A. Denote by trace(A) the trace of matrix A.

Now, we present system model. We first introduce the setting of a standard linear contextual bandit problem. The time is slotted. In each time slot t, there exists a set of possible arms, denoted by set Dt. For each arm a ∈ Dt, there is an associated context vector xt,a ∈ Rd , and a nominal reward rt,a. In each slot t, the learner can observe context vectors of all possible arms, and then choose an arm at and receive the corresponding nominal reward rt,at . Note that only the nominal reward of the chosen arm is revealed for the learner in each time slot t. Further, the nominal rewards of arms are assumed to be a noisy version of an unknown linear function of the context vectors. Specifically, rt,a = 〈xt,a, θ⋆〉 + ηt, where θ⋆ ∈ Rd is an unknown parameter, and ηt is a random noise with zero mean, i.e., E[ηt|xt,at ,Ht-1] = 0, with Ht-1 = (x1,a1 , η1, · · · , xt-1,at-1 , ηt-1) representing historical observations.

The goal of a standard contextual bandit problem is to minimize the total regret in T slots, in terms of the nominal rewards. Particularly, the accumulated T-slot regret regarding nominal reward is defined as,

where Rt is the one-slot regret regarding nominal reward for time slot t, a⋆t is the optimal arm at time slot t. Here, the optimal arm is the one with the largest expected reward, i.e., a⋆t = argmaxa∈Dt E[rt,a]. To simplify the notation, we denote rt,⋆ = rt,a⋆t in the following. That is, rt,⋆ is the optimal nominal reward at slot t.

In the opportunistic learning environment, let Lt be an external variation factor for time slot t. The actual reward ˜ rt,a that the agent receives has the following relationship with the nominal reward:

At each time slot, the learner first observes the context vectors associated with all possible arms, i.e., xt,a, ∀a ∈ Dt, as well as the current value of Lt. Based on which the learner selects current arm at, observes a nominal reward rt,at , and receives the actual reward ˜ rt,a = Ltrt,a.

This model captures the essence of the opportunistic contextual bandits. For example, in the recommendation scenario, and Lt can be a seasonality factor, which captures the general purchase rate in current season. Or Lt can be purchasing power (based on historical information) or loyalty level of users (e.g., diamond vs. silver status). In the network configuration example, when the nominal reward rt,a captures the impact of a configuration at the peak load, the total load (the dummy load plus the real load) resembles the peak load. Then, Lt can be the amount of real load, and thus the actual reward is modulated by Lt as Ltrt,a.

The goal of the learner is to minimize the total regret in T slots, in terms of the actual rewards. Particularly, the accumulated T-slot regret regarding actual reward is defined as,

In a special case, equation (2) has an equivalent form: when Lt is i.i.d. over time with mean value ¯L and rt,at is independent of Lt conditioned on at, the total regret regarding actual reward is ˜Rtotal(T ) = ¯L ∑Tt=1 E[rt,⋆]-∑Tt=1 E[Ltrt,at ]. Note that in general, it is likely that E[Ltrt,at ] ̸= ¯LE[rt,at ], because the action at can depend on Lt.

Algorithm 1 AdaLinUCB

• 1: Inputs: α ∈ R+, d ∈ N, l(+) , l(-) .
• 2: A ← Id {The d-by-d identity matrix}
• 3: b ← 0d
• 4: for t = 1, 2, 3, · · · , T do
• 5: θt-1 = A-1 b
• 6: Observe possible arm set Dt, and observe associated context vectors xt,a, ∀a ∈ Dt.
• 7: Observe Lt and calculate ˜Lt by (3).
• 8: for a ∈ Dt do
• 9: pt,a ← θ⊤ t-1xt,a + α√(1 - ˜Lt)x⊤t,aA-1xt,a
• 10: end for
• 11: Choose action at = argmaxa∈Dt pt,a with ties broken arbitrarily.
• 12: Observe nominal reward rt,at .
• 13: A←A+xt,at x⊤t,at
• 14: b ← b +xt,at rt,at
• 15: end for

4 Adaptive LinUCB

We note that the conventional LinUCB algorithm assumes that the exploration cost factor does not change over time, i.e., Lt = 1. Therefore, to minimize the the nominal reward is equivalent to that of the actual reward. When Lt is timevarying and situation dependent as discussed earlier, we need to maximize the total actual reward, which is affected by the variation factor Lt. Motivated by this distinction, we design the adaptive LinUCB algorithm (AdaLinUCB) as in Algo. 1.

In Algo. 1, α is a hyper-parameter, which is an input of the algorithm, and ˜Lt is the normalized variation factor, defined as,

where l(-) and l(+) are the lower and upper thresholds for truncating the variation factor, and [Lt]l(+) l(-) = max{l(-) ,min{Lt, l(+) }}. That is, ˜Lt normalizes Lt into [0, 1] to capture different ranges of Lt. To achieve good performance, the truncation thresholds should be appropriately chosen to achieve sufficient exploration. Empirical results show that a wide range of threshold values can lead to good performance of AdaLinUCB. Furthermore, these thresholds can be learned online in practice without prior knowledge on the distribution of Lt, as discussed in Sec. 6 and Appendix E of the supplementary material. Note that ˜Lt is only used in AdaLinUCB algorithm. The actual rewards and regrets are based on Lt, not ˜Lt.

In Algo. 1, for each time slot, the algorithm updates a matrix A and a vector b. The A is updated in step 13, which is denoted as At = Id+∑tτ=1 xτ,aτ x⊤τ,aτ in the following analysis. Note that At is a positive-definite matrix for any t, and that A0 = Id. The b is updated in step 14, which is denoted as bt = ∑tτ=1 xτ,aτ rτ,aτ in the following analysis. Then, we have θt = A-1 t bt (see step 5), which is the estimation of the unknown parameter θ⋆ based on historical observations.

Specifically, θt is the result of a ridge regression for estimating θ⋆, which minimizes a penalized residual sum of squares, i.e., θt = argminθ {∑tτ=1 (rτ,aτ - 〈θ, xτ,aτ 〉)2 + ‖θ‖22}.

In general, the AdaLinUCB algorithm explores more when the variation factor is relatively low, and exploits more when the variation factor is relatively high. To see this, note that the first term of the index pt,a in step 9, i.e., θ⊤ t-1xt,a, is the estimation of the corresponding reward; while the second part is an adaptive upper confidence bound modulated by ˜Lt, which determines the level of exploration. At one example, when Lt is at its lowest level with Lt ≤ l(-) , ˜Lt = 0, and the index pt,a is the same as that of the LinUCB algorithm, and then the algorithm selects arm in the same way as the conventional LinUCB. At the other extreme, when ˜Lt = 1, i.e., Lt ≥ l(+) , the index pt,a = θ⊤ t-1xt,a, which is the estimation of the corresponding reward. That is, when the variation factor is at its highest level, the AdaLinUCB algorithm purely exploits the existing knowledge and selects the current best arm.

5 Performance Analysis

We first summarize the technical assumptions needed for performance analysis: i. Noise satisfies Cnoise-sub-Gaussian condition, as explained later in (4); ii. The unknown parameter θ⋆ satisfies ||θ⋆||2 ≤ Ctheta; iii. For ∀t, ∀a ∈ Dt, ‖xt,a‖2 ≤ Ccontext holds; iv. λmin(Id) ≥ max{1,C 2 context}; v. the nominal reward rt,at is independent of the variation factor Lt, conditioned on at.

We note that assumptions i.-iv. are widely used in contextual bandit analysis [Auer, 2002; Chu et al., 2011; AbbasiYadkori et al., 2011; Wu et al., 2016; Wang et al., 2016].

Specifically, the sub-Gaussian condition in assumption i. is a constraint on the tail property of the noise distribution, as that in [Abbasi-Yadkori et al., 2011]. That is, for the noise ηt, we assume that,

with Ht-1 = (x1,a1 , η1, · · · , xt-1,at-1 , ηt-1) and Cnoise > 0. Note that the sub-Gaussian condition requires both (4) and E[ηt|xt,at ,Ht-1] = 0. Further, this condition indicates that Var[ηt|Ft-1] ≤ C 2 noise , where {Ft}∞t=0 is the filtration of σ-algebras for selected context vectors and noises, i.e., Ft = σ(x1,a1 , x2,a2 , · · · , xt+1,at+1 , η1, η2, · · · , ηt). Thus, C 2 noise can be viewed as the (conditional) variance of the noise. Examples for the distributions that satisfies the subGaussian condition are: 1) A zero-mean Gaussian noise with variance at most C 2 noise ; 2) A bounded noise with zero-mean and lying in an interval of length at most 2Cnoise.

Assumption iv. can be relaxed by changing the value of A0 in Algo. 1 from the current identity matrix Id to a positivedefinite matrix with a higher minimum eigenvalue (see Appendix A of the supplementary material for more details).

Assumption v. is valid in many application scenarios. For example, in the network configuration scenario, since the total load resembles the peak load, the network performance, i.e., the nominal reward rt,at , is independent of the real load Lt, conditioned on configuration at. Also, in the recommendation scenario, the click-through rate (i.e., reward rt,a) can be independent of the user influence (i.e., variation factor Lt).

5.1 Problem-Dependent Bounds

We focus on problem-dependent performance analysis here because it can lead to a tighter bound albeit under stronger assumptions. To derive the problem-dependent bound, we assume that there are a finite number of possible context values, and denote this number as N. Then, let ∆min denote the minimum nominal reward difference between the best and the "second best" arms. That is, ∆min = mint {rt,⋆ -maxa∈Dt,rt,a̸=rt,⋆ rt,a}. Similarly, let ∆max denote the maximum nominal reward difference between arms. That is, ∆max = maxt {rt,⋆ -mina∈Dt rt,a}.

As in existing literature for problem-dependent analysis of linear bandits[Abbasi-Yadkori et al., 2011], we assume that single optimal context condition holds here. Specifically, for different time slot t = 1, 2, · · · , there is a single optimal context value. That is, there exists x⋆ ∈ Rd , such that, x⋆ = xt,a⋆t , ∀t.

5.2 AdaLinUCB under Binary-Valued Variation

We first introduce the result under a random binary-valued variation factor. We assume that the variation factor Lt is i.i.d. over time, with Lt ∈ {ϵ0, 1 - ϵ1}, where ϵ0, ϵ1 ≥ 0 and ϵ0 < 1 - ϵ1. Let ρ denote the probability that the variation factor is low, i.e., P{Lt = ϵ0} = ρ.

Firstly, we note that, for a ˜ δ ∈ (0, 1), there exists a positive integer Cslots such that,

To see such an integer Cslots exists, note that for large enough t, in the left-hand side of the inequality (5), the dominant positive term is O(t) while the dominant negative term is O(√t).

To interpret Cslots, it is an integer that is large enough so that during Cslots-slot period, enough exploration is done in the time slots when variation factor is relatively low, such that to have a relatively tight bound for the estimation of the optimal reward.

Then, we have the following results.

Theorem 1. Consider the opportunistic contextual bandits with linear payoffs and binary-valued variation factor. With probability at least 1 - ˜ δ, the accumulated regret (regarding actual reward) of AdaLinUCB algorithm satisfies,

where Cslots is a constant satisfying (5).

Proof Sketch: Although the proof for Theorem 1 is complicated, the key is to treat the slots with low variation factor and the slots with high variation factor separately. For slots with low variation factor, the one-step regret is upper bounded by the weighted 2-norm of the selected context vectors, i.e., Rt1{Lt = ϵ0} ≤ 2α‖xt,at ‖A-1 t-1 , and then the accumulated regret can be analyzed accordingly. For the slots with high variation factor, by matrix analysis, we can show that when a particular context value has been selected enough times, its estimated reward is accurate enough in an appropriate sense. Further, it can benefit from regret bound for low variation factor slots that the optimal context has been selected enough time with high probability. Then, we combine these to prove the result. More details are shown in Appendix B of the supplementary material.

Remark 1. For the regret bound in Theorem 1, the first three lines cover the accumulated regret that is incurred during time slots when the variation factor is relatively low, i.e., during slots t with Lt = ϵ0, while the last two lines cover the accumulated regret that is incurred during time slots when the variation factor is relatively high, i.e., during slots t with Lt = 1 - ϵ1. Further, when T is large enough, the dominant term for the first three lines is O ((logT)2 ), while the dominant term for the last two lines is O(logT). That is, the bound for the accumulated regret during slots when the variation factor is relatively high actually increases slower than the bound for the accumulated regret during slots when the variation factor is relatively low. This is in consistent with the motivation of AdaLinUCB design: explore more when the variation factor is relatively low, and exploit more when the variation factor is relatively high.

Furthermore, beside parameter T, which is the time horizon, the regret bound in Theorem 1 is also affected by problem-dependent parameters: it is affected by N, which is the number of possible context values, ∆min, which is the minimum nominal reward difference between the best and the "second best" arms, and ∆max, which is the maximum nominal reward difference between arms. In general, a larger number of possible context values, i.e., a larger N, may lead to a larger ∆max and a smaller ∆min, and in this way, results in a larger regret bound.

5.3 AdaLinUCB under Continuous Variation

We now study AdaLinUCB in opportunistic contextual bandits under continuous variation factor. Under continuous variation factor, it is difficult to obtain regret bound for general values of l(-) and l(+) because exploration and exploitation mix in a complex fashion when l(-) < Lt < l(+) . Instead, inspired by the insights obtained from the binary-valued variation factor case, we illustrate the advantages of AdaLinUCB for special case with l(-) = l(+) .

In the special case of l(-) = l(+) , the normalized variation factor ˜Lt in (3) is redefined as ˜Lt = 0 when Lt ≤ l(-) and as ˜Lt = 1 when Lt > l(+) = l(-) .

Theorem 2. In the opportunistic contextual bandits with linear payoffs and continuous variation factor that is i.i.d. over time, under AdaLinUCB with P{Lt ≤ l(-) } = ρ > 0 and l(-) = l(+) , with probability at least 1 - ˜ δ, the accumulated regret (regarding actual reward) satisfies,

where Cslots is a constant satisfying (5).

Proof. Recall that for the special case with l(+) = l(-) , we have ˜Lt = 0 when Lt ≤ l(-) and as ˜Lt = 1 when Lt > l(+) . Thus, this theorem can be proved analogically to the proof of Theorem 1, by noting the following: When Lt ≤ l(-) , we have ˜Lt = 0 which corresponds to the case of Lt = ϵ0 (˜Lt = 0) in the binary-valued variation factor case; while when Lt > l(+) ( ˜Lt = 1) corresponds to the case of Lt = 1ϵ1 under binary-valued variation factor case. The conclusion of the theorem then follows by using the fact that all variation factor below l(-) are treated same by AdaLinUCB, i.e., ˜Lt = 0 for Lt ≤ l(-) ; while all variation factor above l(-) are treated same by AdaLinUCB, i.e., ˜Lt = 1 for Lt ≤ l(+) .

Remark 2. Similar to Remark 1 for Theorem 1, the regret bound in Theorem 2 can be divided into two parts: the first three lines cover the accumulated regret that is incurred during time slots when Lt ≤ l(-) and is O ((logT)2 ), while the last two lines cover the accumulated regret for time slots when Lt > l(-) and is O((logT)). Furthermore, a larger N, i.e., a larger number of possible context values, can lead to a larger regret bound.

5.4 Regret Bound of LinUCB

To the best of our knowledge, there exists no problemdependent bound on LinUCB. (The initial analysis of LinUCB presents a more general and looser performance bound for a modified version of LinUCB. The modification is needed to satisfy the independent requirement by applying Azuma/Hoeffding inequality [Chu et al., 2011].) Furthermore, we note that one can directly apply LinUCB to opportunistic contextual bandits using the linear relationship E[rt,a|xt,a] = 〈xt,a, θ⋆〉, which is called LinUCBExtracted in numerical results. Therefore, we derive the regret upper bound for LinUCB here, both as an individual contribution as well as for comparison purpose.

Theorem 3. In the opportunistic contextual bandits with linear payoffs and continuous variation factor that is i.i.d. over time with mean ¯L, with probability at least 1 - δ, the accumulated T-slot regret (regarding actual reward) of LinUCB satisfies,

The regret bound for LinUCB under non-opportunistic case can be shown by simply having ¯L = 1 in the above result. Here, note that problem-dependent bound analysis is a setting that allows a better bound to be achieved with stronger assumptions. Recall that the assumptions are discussed in Sec. 5.1. As a result, the problem-dependent bound of LinUCB is much better than its general bound, such as the bound for a modified version of LinUCB in [Chu et al., 2011]. More results for LinUCB and the proof of Theorem 3 can be found in Appendix C of the supplementary material.

Remark 3. Theorem 3 and Theorem 1 show that the problem-dependent regret bounds (regarding actual reward) for LinUCB and AdaLinUCB are both O ((logT)2 ). Further, for binary-valued variation factor, the asymptotically dominant term for the bound of LinUCB is 1-ϵ1+ϵ0 2 · 16C2 noiseC2 theta

theta ∆min (logT)2 . Because ϵ0 < 1 - ϵ1, in the scenario of binary-valued variation factor, the AdaLinUCB algorithm has a better asymptotic problem-dependent upper bound than that of the LinUCB algorithm. Similarly, in scenario with continuous variation factor, the AdaLinUCB algorithm with l(+) = l(-) has a better problem-dependent bound than LinUCB algorithm as long as E[Lt|Lt ≤ l(-) ] < ¯L, which holds in most cases.

∆min (logT)2 . In comparison, for AdaLinUCB, it is ϵ0 · 16C2 noiseC2

5.5 Discussions on the Disjoint Model

The seminal paper on LinUCB [Li et al., 2010] introduces different models for contextual bandits. The opportunistic learning applies to these different models. One of them is the joint model discussed above. Another model is the disjoint model, which assumes that, E[rt,a|xt,a] = 〈xt,a, θ(a) ⋆ 〉, where xt,a is a context vector and θ(a) ⋆ is the unknown coefficient vector for arm a. This model is called disjoint since the parameters are not shared among different arms. There is also a hybrid model that combines the joint model and the disjoint model.

In this paper, we focus on the design and analysis of opportunistic contextual bandits using the joint model. However, it should be noted that, the AdaLinUCB algorithm in Algo. 1 can be modified slightly and applied to the disjoint model, see Appendix D of the supplementary material for more details. Also, the analysis of the joint model can be extended to the disjoint one. Note that the disjoint model can be converted to a joint model when the number of possible arms is finite. Specifically, for an arbitrary disjoint-model opportunistic contextual bandit problem with θ(a) ⋆ ∀a, an equivalent joint-model problem exists with the joint unknown parameter as θ⋆ = ([θ(1) ⋆ ]⊤, [θ(2) ⋆ ]⊤, · · · )⊤ and the context vectors modified accordingly. Thus, the previous analytical results are valued for the disjoint model with appropriate modifications.

6 Numerical Results

We present numerical results to demonstrate the performance of the AdaLinUCB algorithm using both synthetic scenario and real-world datasets. We have implemented the following algorithms: 1) AdaLinUCB in Algo. 1; 2) LinUCB(Extracted) in Sec. 5.4; 3) LinUCBMultiply, another way to directly apply LinUCB in opportunistic case, where we use Lt · xt,a as context vector; 4) E-AdaLinUCB, an algorithm that adjusts the threshold l(+) and l(-) based on the empirical distribution of Lt. In all the algorithms, we set α = 1.5 to make a fair comparison.

We have also experimented LinUCBCombine algorithm, where we use ˜xt,a = [Lt, x⊤t,a ]⊤ as context vector to directlty apply LinUCB, and find that LinUCBCombine has a much worse performance compared to other algorithms.

Meanwhile, we also notice that the opportunistic linear contextual bandits can be regarded as a special case of nonlinear contextual bandits by viewing the variation factor Lt as a part of context vector. Along this line of thinking, we have also experimented KernelUCB algorithm [Valko et al., 2013], which is a general algorithm for non-linear contextual bandits. However, we find that KernelUCB is less competitive in performance and suffers from extremely high computational complexity (see Appendix E.3 of the supplementary material for more details). One reason is that a general contextual bandit algorithm such as KernelUCB does not take advantage of the opportunistic nature of the problem, and can, therefore, have a worse performance than AdaLinUCB.

6.1 Experiments on Synthetic Scenarios

The synthetic scenario has a total of 20 possible arms, each associated with a disjoint unknown coefficient θ(a) ⋆ . The simulator generates 5 possible groups of context vectors, and each group has context vectors associated with all the possible arms. At each time slot, a context group is presented before the decision. Further, each unknown coefficient θ(a) ⋆ and each context xt,a is a 6-dimension vector, with elements in

• (a) Binary-valued variation factor

(b) Beta distributed variation factor

Figure 1: Regret under Synthetic Scenarios. In (a), ϵ0 = ϵ1 = 0, ρ = 0.5. In (b), AdaLinUCB: l(-)=l(-) 0 , l(+)= l(+) 0 ; AdaLinUCB: (l(-)= l(+) ), l(-)= l(+)= l(-) 0.5

each dimension generated randomly, and is normalized such that the L2-norm of θ(a) ⋆ or xt,a is 1.

Fig. 1(a) shows the regret for different algorithms under random binary-value variation factor with ϵ0 = ϵ1 = 0 and ρ = 0.5. AdaLinUCB significantly reduces the regret in this scenario. Specifically, at time slots t = 5×104 , AdaLinUCB achieves a regret that is only 10.3% of that of LinUCBMultiply, and 17.6% of that of LinUCBExtracted.

For continuous variation factor, Fig. 1(b) compares the regrets for the algorithms under a beta distributed variation factor. Here, we define l(-) ρ as the lower threshold such that P{Lt ≤ l(-) ρ =ρ}, and l(+) ρ as the higher threshold such that P{Lt ≥ l(+) ρ =ρ}. It is shown that AdaLinUCB still outperforms other algorithms, and AdaLinUCB has a regret 41.8% lower than that of LinUCBExtracted. Furthermore, its empirical version, E-AdaLinUCB has a similar performance to that of AdaLinUCB. Even in the special case with a single threshold l(-) = l(+) = l(-) 0.5 , AdaLinUCB still outperforms LinUCBExtracted, reducing the regret by 28.6%.

We have conducted more simulations to evaluate the impact of environment and algorithm parameters such as variation factor fluctuation and the thresholds for variation factor truncation, and find that AdaLinUCB works well in different scenarios (see Appendix E.1 and E.2 of the supplementary material ).

6.2 Experiments on Yahoo! TodayModule

We also test the performance of the algorithms using the data from Yahoo! Today Module. This dataset contains over 4 million user visits to the Today module in a ten-day period in May 2009 [Li et al., 2010]. To evaluate contextual bandits using offline data, the experiment uses the unbiased offline evaluation protocol proposed in [Li et al., 2011]. For the variation factor, we use a real trace - the sales of a popular store. It includes everyday turnover in two years [Rossman, 2015].

In this real recommendation scenario, because we do not know the ground truth; i.e., which article is best for a specific user, we cannot calculate the regret. Therefore, all the results are measured using the reward, as shown in Fig. 2. We note that AdaLinUCB increases the reward by 17.0%, compared to LinUCBExtracted, and by 40.8% compared to the random policy. We note that an increase in accumulated reward is typically much more substantial than the same decrease in regret. We also note that E-AdaLinUCB, where one does not assume prior knowledge on the variation factor distribution, achieves a similar performance. This experiment demonstrates the effectiveness of AdaLinUCB and E-AdaLinUCB in practical situations, where the variation factor are continuous and are possibly non-stationary, and the candidate arms are time-varying. More details on the datasets and evaluation under different parameters can be found in Appendix E.4 of the supplementary material.

7 Conclusions

In this paper, we study opportunistic contextual bandits where the exploration cost is time-varying depending on external conditions such as network load or return variation in recommendations. We propose AdaLinUCB that opportunistically chooses between exploration and exploitation based on that external variation factor, i.e., taking the slots with low variation factor as opportunities for more explorations. We prove that AdaLinUCB achieves O ((log T )2 ) problem-dependent regret upper bound, which has a smaller coefficient thatn that of the traditional LinUCB algorithm. Extensive experiment results based on both synthetic and real-world database demonstrate the significant benefits of opportunistic exploration under large exploration cost fluctuations.

Acknowledgments

The work is partially supported supported by NSF through grants CNS-1547461, CNS-1718901, and IIS-1838207.