Continuous Time Associative Bandit Problems

1 Introduction

Multi-armed bandit problems find applications in various fields, such as statistics, control, learning theory or economics. They became popular with the seminal paper by Robbins [1952] and since then they enjoy perpetual popularity.

The version of the bandit problem we consider here is motivated by the following example: Imagine that a sequence of tasks arrive for processing in a computer center that has a single supercomputer. For each of the tasks a number of alternative algorithms can be applied to. Some information about the tasks is available that can be used to predict which of the algorithms to try. The processing time depends on the task at hand and also on the algorithm selected and may take continuous values, hence the time instants when the decisions can take place take continuous values, too. The supercomputer has a fixed cost of running, whilst the centre's income is based on the quality of solutions delivered. At any given time only a single task can be executed on the supercomputer. Admittedly, this assumption looks absurd at the first sight in the context of our example, however, we think that our results can be extended to the more general case when the number of algorithms that can run simultaneously is bounded by a constant without much trouble. Hence we decided to stick to this simplifying assumption.

∗This research was supported in part by the Ministry of Economy and Transport, Hungary (Grant No. GVOP-3.1.1.-2004-050145/3.0), the Hungarian National Science Foundation (Grant No. T047193), and by the J´anos Bolyai Research Scholarship of the Hungarian Academy of Sciences.

An allocation rule decides, based on the side information available about the task just received, which algorithm to use for processing it, the goal being to maximize the return rate. Note that this criterion is different frommaximizing the total reward. In fact, since processing a task takes some time during which no other tasks can be processed, the rate maximization problem cannot be solved by selecting the algorithm with the highest expected payoff: Some tasks may look so difficult to solve that the best thing could be to drop them, which results in no payoff, but in exchange the learner does not suffer any loss due to not processing other, possibly more rewarding tasks. (Note that this would not be possible without the presence of side information; in the latter case the problemwould simplify to the usual multi-armed bandit problem where one needs to find the best option with highest reward rate.) This example illustrates that a learner whose aim is to quickly learn a good allocation strategy for rate maximization must solve two problems simultaneously: Predicting the long-term values of the available algorithms given the information about the task to be processed and balancing exploration and exploitation so that the loss due to selecting inferior options (i.e., the regret) is kept at minimum. The problem we consider can be thought of as a minimalistic example where the learner faces these two problems simultaneously.

Bandit problems in continuous time have been studied earlier by a number of authors (see e.g. [Kaspi and Mandelbaum, 1998; Karoui and Karatzas, 1997] and the references therein). These earlier results concern the construction of optimal allocation policies (typically in the form of Gittins indexes) given some parametric form of the distributions of the random variables involved. In contrast, here we consider the agnostic case when no particular parametric form is assumed, but the environment is supposed to be stationary and stochastic. The agnostic (or non-parametric) case has been studied extensively in the discrete time case. In fact, this problem was first considered by Robbins [1952], who introduced a certainty-equivalence rule with forcing. In the same article Robbins showed that this rule is asymptotically consistent in the sense that the frequency of the time instants when the best arm is selected converges to one almost surely. More recently, Agrawal [1995] suggested a number of simple sample-mean based policies and showed that the resulting policies' regret after n decisions is O(logn). Since it is known that no allocation rule can achieve regret lower than Cp logn for an appropriate (problem dependent) constant Cp [Lai and Robbins, 1985], Agrawals' policies are unimprovable apart from constant factors. Lately, Auer et al. [2002] strengthened these results by suggesting policies that achieve logarithmic regret uniformly over time, rather than just asymptotically. An added benefit of their policies is that they are simple to implement.

We base our algorithm on algorithm UCB1 from [Auer et al., 2002] (see also [Agrawal, 1995]). We assume a stationary memoryless stochastic environment, where the side information is an i.i.d. process taking values in a finite set, the payoffdelay sequences are jointly distributed for any of the options and their distribution depends on the side information (the precise assumptions will be listed in the next section). Like UCB1, our algorithm decides which option to choose based on sample-means corrected by upper confidence bounds. In our case, however, separate statistics are kept for all option - side-information pairs. Our main result shows that the resulting policy achieves logarithmic regret uniformly in time and hence it is also unimprovable, apart from constant factors.

The paper is organized as follows: We define the problem and the proposed algorithm in Section 2. Our main result, a logarithmic regret bound on the algorithm's performance is presented in Section 3. Conclusions are drawn in Section 4.

2 The algorithm

The problem of the previous section is formalized as follows: Let K denote the number of options available, and let X denote the set of possible values of the side information, which is assumed to be finite. Let x1, x2, . . . , xt be a random sequence of covariates representing the side information available at the time of the t-th decision, generated independently from a distribution p supported on X. At each decision point the decision maker may select an option It from A = {1, . . . ,K} and receives reward rt = rIt,t(xt), where rit(xt) is the reward the decision maker would have received had it chosen option i. Unlike in classical bandit problems the collection of the reward takes some random time. When option i is selected and the side information equals x, this time is δit(x). We assume that for any fixed x and i, (rit(x), δit(x)) is an i.i.d. sequence, independent of {xt}. We further assume that rit(x) ∈ [rmin, rmax], δit(x) ∈ [δmin, δmax] with δmin > 0. (We expect that the boundedness assumptions can be relaxed to δit(x) ≥ 0 and appropriate moment conditions on δit(x) and rit(x).) Let

and

denote the expected reward and delay, respectively, when option i is chosen at the presence of the side-information x.

The exact protocol of decision making is as follows: Decision making happens in discrete trials. Let τ0 = 0 and let τt denote the time of the beginning of the t-th trial. At the beginning of the tth trial the decision maker receives the side information xt. Based on the value of xt and all information received by the decision maker at prior trials, the decision maker must select an option It. Upon executing It, the decision maker receives a reward rt = rIt,t(xt) and suffers a delay δt = δIt,t(xt). That is, the next time point available when the decision maker can select an option is τt+1 = τt + δIt,t(xt).

The goal of the decision maker is to find a good allocation policy. Formally, an allocation policy maps possible histories to some index in the set A. The gain (average reward rate) delivered by an allocation policy u is given by

where {ru t } is the reward sequence and {δu t } is the delay sequence experienced when policy u is used. An optimal allocation policy is one that maximizes this gain. Note that the problem as stated is a special case of semi-Markov decision problems [Puterman, 1994]. The theory of semi-Markov decision problems furnishes us with the necessary tools to characterize optimal allocation policies: Let us define the optimal gain by

A policy u is said to be optimal if it satisfies λ∗ = λu . It follows from the generic theory that there exist deterministic stationary policies that are optimal. An optimal action for some x ∈ X can be determined by ordering the options by their relative values. The relative value of option i upon observing x is the expected reward that can be collected minus the expected reward that is not gained during the time it takes to collect the reward:

Intuitively it should be clear that a policy that always selects options with best relative values should optimize the overall gain. In fact, it follows from the theory of semi-Markov decision problems that this is indeed the case. A stationary deterministic policy u : X → A is optimal if and only if it obeys the constraints

simultaneously for all x ∈ X .

The (total) regret of an allocation policy is defined as the loss suffered due to not selecting an optimal option in each time step. Since we are interested in the expected regret only, our regret definition uses the optimal gain λ∗ :

The value of the first term is the maximum reward that could be collected during the time of the first n decisions. The expected regret thus compares the expected value of the latter with the expected value of the actual total payoffs received. It follows that an allocation policy that minimizes the regret will optimize the rate of return.

When δit(x) = 1, and X has a single element, the problem reduces to the classical stochastic bandit problem. Since for the stochastic bandit problems the regret is lower bounded by O(log n), we are seeking policies whose regret grows at most at a logarithmic rate.

The idea underlying our algorithm is to develop upper estimates of the values q∗ i (x) with appropriate confidence bounds. Just like in [Auer et al., 2002], the upper confidence estimates are selected to ensure that for any given x with p(x) > 0 all options are ultimately selected infinitely often, but at the same time suboptimal options are selected increasingly rarely.

The algorithm is as follows: Let us consider the t-th decision. If we had a good estimate λt of λ∗ , then for any given x we could base our decision on the estimates of the relative values q∗ i (x) of the options given by rit(x) - δit(x)λt. Here rit(x) denotes the average of rewards during the first n decisions for those time points when the side information is x and option i was selected, and δit(x) is defined analogously:

where Ti(x, t) denotes the number of times option i was selected when side information x was present in trials 1, 2, . . . , t:

The plan is to combine appropriate upper bounds on ri(x) and lower bounds on δi(x) based on the respective sample averages rit(x), δit(x) and Ti(x, t), to obtain an upper estimate of q∗ i (x). However, in order to have a sample based estimate, we also need an appropriate lower estimate of λ∗ . This estimate is defined as follows:

Let U denote the set of stationary policies: U = {u|u : X → A}. Pick any u ∈ U. Let λut denote the empirical estimate of the gain of policy u:

and let Tu(t) denote the number of times when an option 'compatible' with policy u was selected:

Then λt, the estimate of λ∗ is defined by

Here ct,s is an appropriate deterministic sequence that is selected such that simultaneously for all policies u ∈ U, λut is in the ct,Tu(t)-vicinity of λu with high probability. This sequence will be explicitly constructed during the proof where we will also make sure that it depends on known quantities only. In words, λn is the optimal gain that the decision maker can guarantee itself with high probability given the data seen so far.

Our proposed allocation policy, {uUCB t }, selects the options It = uUCB t (xt) by the rule

where, similarly to ct,s, ˆ ct,s is an appropriate deterministic sequence that will be chosen later.

3 Main result

Our main result is the following bound on the expected regret: Theorem 1 Let the assumptions of the previous section hold on rit, δit, xt. Let Rn be the n-step regret of policy uUCB. Then, for all n ≥ 1,

E [Rn] ≤ L∗((2+ 2π2 3(|U | + 1)2 ) K|X | + 2K|X | log(n) + ∑ i:Δi>0 ∑ x∈X a log(n(√|U | + 1)) Δi(x)2 ), where L∗ = δmaxλ∗ - rmin, Δi(x) = max j∈A q∗ j (x) - q∗ i (x) ≥ 0, i = 1, . . . ,K,

and the positive constant a is given by (7) in the proof of the theorem.

The proof follows similar lines to that of Theorem 1 of [Auer et al., 2002], with the main difference being that now we have to handle the estimation error of λ∗ . We prove the theorem using a series of propositions.

The first proposition bounds the expected regret in terms of the number of times when some suboptimal option is chosen:

Proposition 2 The following bound holds for the expected regret of an arbitrary policy, u = (u1, u2, . . .):

where

denotes the set of optimal options at x, and

is the loss for the worst choice at x. Further, by L∗ (x) ≤ L∗,

Proof. Let us consider the t-th term, E [δtλ∗ - rt ], of the expected regret. We have E [δtλ∗ - rt] = ∑i∈A E [(δtλ∗ - rt)I (It = i)] . Using It = ut(xt) and that ut depends only on the past, i.e., if Ft is the sigma algebra of x1, r1, δ1, . . . , xt, rt, δt then It = i is Ft-1 measurable, we get that

Now, using again that ut does not depend on xt, we get

Then

Let wt(i|x) = E [I (ut(x) = i)] if i ∈ U ∗ (x) and wt(i|x) = 0 otherwise, and let μt(i|x) = wt(i|x)/ ∑j∈A wt(j|x). Then μt(i|x) ≥ wt(i|x) (since ∑j∈A wt(j|x) ≤ 1), the first term of the last expression can be upper bounded by

Since μt(i|x) = 0 if i is not optimal, μt defines an optimal (stochastic) policy and hence, Bellman's equation gives vt = 0. Therefore,

Summing up this last expression over t gives the advertised bound. ⊓⊔

The next statements are used to prove that with high probability λt is a good estimate of λ∗ . Here and in what follows u∗ denotes an arbitrary (fixed) optimal policy and λ∗t = λu∗ t .

Proposition 3 Assume that the following conditions are satisfied:

where the first condition is meant to hold for all stationary policies u ∈ U. Then

Proof. Let u′ be the policy that maximizes λut - ct,Tu(t). Since (3) holds for u′ , we get that λt = λut - ct,Tu′(t) ≤ λu′ ≤ λ∗ , proving the upper bound for λt. On the other hand, because of the choice of u′ , λt ≥ λ∗t - ct,Tu∗(t) which can be further lower bounded by λ∗ - 2ct,Tu∗(t) using (4), proving the lower bound for λt. ⊓⊔

The following proposition shows that λt is indeed a lower bound for λ∗ with high probability.

Proposition 4 Let

where

Then

Proof. According to Proposition 3, if (3) holds for all stationary policies u and if (4) holds then λ∗ ≥ λt ≥ λ∗ -2ct,Tu∗ (t). Hence, in order λt < λ∗ - 2ct,Tu∗(t) or λt > λ∗ to hold, we must have that one of the conditions in Proposition 3 is violated. Using a union bound we get

Fix u. By the law of total probability,

Define

Using elementary algebra, we get that

Exploiting that ˆ ru t and ˆ δu t are martingale sequences and resorting to a slight variant of the Hoeffding-Azuma bound (see, e.g. [Devroye et al., 1996]), we get the bound 2/(|U| + 1)t-2 . Summing over s and u and by an analogous argument for P (λ∗ < λ∗t + ct,Tu(t)), we get the desired bound. ⊓⊔

Now we are ready to prove the main theorem. In the proof we put a superscript '∗' to any quantity that refers to the optimal policy u∗. For example, r∗t (x) = ru∗ (x),t(x), δ∗ t (x) = δu∗ (x),t(x), T ∗(x, t) = Tu∗ (x)(x, t), etc.

Proof of Theorem 1. Proposition 2 applied to uUCB shows that it suffices if for any fixed x ∈ X and suboptimal choice i ̸∈ U ∗ (x) we derive an O(logn) upper bound on the expected number of times choice i would be selected by uUCB when the side information is x. That is, we need to show

Let qit(x) = rit(x) - δit(x)λt. Using the definition of uUCB t , if uUCB t (x) = i holds then qit(x) + ˆ ct,Ti(x,t) > q∗ t (x) + ˆ ct,T ∗ (x,t). Hence, for any integer A(n, x),

We write the t-th term in the last sum as follows:

Fix any s, s′ ∈ H(t). Using the definition of qit(x),

The expectations of the second two terms will be bounded by Proposition 4. The first term, multiplied by Zt(s, s′ ) is bounded by

When this expression equals one then at least one of the following events hold:

Here c′t-1,s = ˆ ct-1,s -2δ∗t ct-1,s. Now let us give the choices for the confidence intervals. Define

We have already defined cts in Proposition 4: cts = √2c1uts, where c1 was defined there, too. We define ˆ cts implicitly, through a definition of c′ts which is defined so as to keep the probability of At,s,s′ small: Let

and ˆ cts = (a0 +a1)uts. Using these definitions we bound the probabilities of the above three events. We start with At,s,s′ :

Here we used that ∑ts=1 I (It = i, xt = x) rt, ∑ts=1 I (It = i, xt = x) δt are martingales for any x, i, and the above-mentioned variant of the Hoeffding-Azuma inequality. Plugging in the definition of c′ts we get that the probability of event At,s,s′ is bounded by 2t-4(|U| + 1)-2 . The probability of Bt,s,s′ can be bounded in the same way and by the same expression since ˆ cts > c′ts . Therefore

Moreover, define A(t, x) = a log(t(√|U| + 1))/Δi(x)2 . Now, if Ct,s,s′ holds then one must have Δi(x) > 2ˆ ct,s′ , where s′ ≥ A(t, x). The above choice makes s′ large enough so that Δi(x) > 2ˆ ct,s′ cannot hold. Hence P(Ct,s,s′ ) = 0. Gathering all the terms, we have

This finishes the proof of (6) and hence, by Proposition 2 we get the desired bound, (2). ⊓⊔

4 Conclusions and further work

We considered a generalization of the multi-armed bandit problem, where performing an action (or collecting the reward) takes a random amount of time. The goal of the decision maker is to maximize the reward per unit time where in each time step some side information is received before the decision is made. In this setting one needs to consider seriously the time needed to perform an action, since spending long times with less rewarding actions seriously limits the performance of any algorithm in a given time period. Therefore, efficient methods must predict simultaneously the expected rewards and durations of all actions, as well as to estimate the long term optimal performance. The latter is essential as each action has a hidden cost associated with it: since actions take time, for their correct evaluation their immediate payoffs must be decremented by the optimal reward lost during the time it takes to execute the action.

In this paper we proposed an algorithm to solve this problem, whose cumulative reward after performing n actions is only O(logn) less than that of the best policy in hindsight. The algorithm is based on the upper confidence bound idea of Auer et al. [2002]. Our algorithm, however, extends their UCB1 algorithm proposed for the multi-armed bandit problem in two ways. First of all, it estimates the long termmaximum reward per unit time. For this we proposed to adopt a maximin approach: The estimate was chosen to be the optimal gain that can be guaranteed in the worst-case, with high probability, given all the data seen so far. Moreover, utilizing the structure of the problem the algorithm chooses its actions based on the sufficient statistics of the problem instead of considering each policy separately. Note that doing so would lead to a constant factor in the regret bound that grows linearly with the number of possible policies, i.e., exponentially in the size of the problem. On the other hand, because of the specialized form of our algorithm, the constants in our bound depend only polynomially on these parameters. However, we expect that the explicit dependence of the bound on the number of possible side information values can be relaxed. Note however, that we have not attempted any optimization of the actual constants that appear in our bounds. Therefore, we expect that our constants can be improved easily.

One problem with the algorithm as presented is that it needs to enumerate all the policies in order to compute the estimate of the optimal gain. However, we would like to note that the problem of computing this quantity is very similar to computing the value of minimax Markov games. In fact, the actual definition of δt is not that important: Any estimate that satisfies the conclusion of Proposition 4 would do. We speculate that since efficient methods are available for certain minimax Markov games (cf. [Szepesv´ari and Littman, 1999]), game theoretic techniques might yield an algorithm that not only utilizes the available information effectively, but is also computationally efficient.

In the present work we restricted ourselves to the case when the side information is allowed to take values only in a finite set. Assuming appropriate smoothness conditions on the reward and delay functions, it seems possible to extend the algorithm to the case of continuous valued side information. The extension of the algorithm presented seems possible to certain semi-Markov models when there is a state that is recurrent under all stationary policies. Another interesting avenue for further research is to consider continuous time bandit problems in non-stochastic environments.