# Combining Multiple Strategies for Multiarmed Bandit Problems and Asymptotic Optimality

Authors: Hyeong Soo Chang; Sanghee Choe
Journal: Journal of Control Science and Engineering
 (2015)

---

## Abstract

This brief paper provides a simple algorithm that selects a strategy at each time in a given set of multiple strategies for stochastic multiarmed bandit problems, thereby playing the arm by the chosen strategy at each time. The algorithm follows the idea of the probabilisticϵ
t-switching in the ϵ
t-greedy strategy and is asymptotically optimal in the sense that the selected strategy converges to the best in the set under some conditions on the strategies in the set and the sequence of {
ϵ
t
}.


---

## Body

## 1. Introduction

This paper considers the problem of stochastic non-Bayesian multiarmed bandit (MAB) in which a player with a bandit has to decide which arm to play at each time among available arms to maximize the sum of rewards earned through a sequence of playing arms. When played, each arm provides a random reward from an unknown distribution specific to that arm. The problem models the well-known trade-off between “exploration” and “exploitation” in sequential learning. The player needs to obtain new knowledge (exploration) and at the same time optimize her decisions based on existing knowledge (exploitation). The player attempts to balance these competing tasks in order to achieve the goal. Many practical problems, for example, in networking [1, 2], in games [3], and in prediction [4], and problems such as clinical trials and ad placement on the Internet (see, e.g., [1, 5, 6] and the references therein) have been studied with a (properly extended) model of the MAB problems.Specifically, we consider a stochasticK-armed bandit problem where there is a finite set of arms A
=
{
1,2
,
…
,
K
}, K
>
1 and one arm in A needs to be sequentially played. When an arm a
∈
A is played at time t
≥
1, the player obtains a sample bounded reward X
a
,
t
∈
R drawn from an unknown distribution associated with a, whose unknown expectation and variance are μ
a and σ
a
2, respectively. We define astrategy
π
=
{
π
t
,
t
=
1,2
,
…
} as a sequence of mappings such that π
t maps from the set of past plays and rewards, H
t
-
1
:
=
(
A
×
R
)
t
-
1, to the set of all possible distributions over A where H
0 is an arbitrarily given nonempty subset of R. We denote the set of all possible strategies as Π. Given a particular sequence h
t
-
1
π
∈
H
t
-
1 of the past plays and rewards obtained by following π
∈
Π over t
-
1 time steps, π selects a
∈
A to be played by probability π
t
(
h
t
-
1
π
)
(
a
) at time t. We assume that π
1
(
h
0
π
) is arbitrarily given.Let random variableI
t
π denote the arm selected by π at time t and let P
π
(
t
) be the distribution over A given by π at time t so that P
a
π
(
t
)
=
Pr
⁡
{
I
t
π
=
a
}, which is equal to ∑
h
t
-
1
π
∈
H
t
-
1
‍
π
t
(
h
t
-
1
π
)
(
a
)
Pr
⁡
{
h
t
-
1
π
}. We assume that X
a
,
t and X
a
′
,
t
′ are independent of any a
,
a
′ and t
≠
t
′ and X
a
,
t’s for t
≥
1 are identically distributed for any fixed a in A.Letμ
*
=
max
⁡
a
∈
A
μ
a and A
*
=
{
a
∈
A
∣
μ
a
=
μ
*
}. For a given π
∈
Π, if ∑
a
∈
A
∖
A
*
‍
P
a
π
(
t
)
→
0 as t
→
∞, then we say that π is anasymptotically optimal strategy. The notion of the asymptotic optimality was introduced by Robbins [5]. He presented a strategy which achieves the optimality for the K
=
2 case where in a single play, each a
∈
A produces a reward of 1 or 0 with unknown probabilities p
a and 1
-
p
a, respectively. Bather [7] considered the same Bernoulli problem with K
≥
2 and established an asymptotically optimal index-based strategy π such that, at time t, π selects an arm in arg
⁡
max
⁡
a
∈
A
{
X
-
a
,
T
a
π
(
t
-
1
)
π
+
λ
(
T
a
π
(
t
-
1
)
)
Z
a
(
t
)
}, where T
a
π
(
t
-
1
) denotes the number of times arm a has been played by π during the first t
-
1 plays, and X
-
a
,
m
π
,
m
≥
1, denotes the average of the m reward samples obtained by playing a when π is followed, and {
λ
(
n
)
,
n
≥
1
} is a sequence of strictly positive constants such that λ
(
t
)
→
0 as t
→
∞, and Z
a
(
t
)
,
a
∈
A
,
t
≥
K, are i.i.d. positive and unbounded random variables whose common distribution function F satisfies that F
(
0
)
=
0 and F
(
z
)
<
1
,
for
all
z
>
0. The idea is to ensure that each arm is played infinitely often by adding small perturbations to X
-
a
,
T
a
π
(
t
-
1
)
π and to make the effect vanish as T
a
π
(
t
-
1
) increases. The well-known asymptotically optimal ϵ
t-greedy strategy [8] with ∑
t
=
1
∞
‍
ϵ
t
=
∞ and lim
t
→
∞
ϵ
t
=
0 follows exactly the same idea: at time t, with probability ϵ
t
∈
(
0,1
], it selects a
∈
A with probability 1
/
K and, with probability 1
-
ϵ
t, it selects an arm in arg
⁡
max
⁡
a
∈
A
{
X
-
a
,
T
a
π
(
t
-
1
)
π
} where π refers to the ϵ
t-greedy strategy.This brief paper provides a randomized algorithmϵ
t
-comb
(
Φ
) which follows the spirit of the ϵ
t-greedy strategy for combining multiple strategies in a given finite nonempty Φ
⊂
Π. At each time t, we use the probabilistic ϵ
t-switching to select uniformly a strategy in Φ or to select a strategy with the highest sample average of the rewards obtained so far by playing the bandit. Once a strategy ϕ is selected, the arm chosen by ϕ is played for the bandit. Analogous to the case of the ϵ
t-greedy strategy, it is asymptotically optimal in the sense that the selected strategy converges to the “best” in the set under some conditions on the strategies in Φ and {
ϵ
t
}.


## 2. Related Work

In the following, we briefly summarize the most relevant works in the literature with the results of the present paper. A seminal work by Gittins and Jones [9] provides an optimal policy (or allocation index rule) to maximize the discounted reward over an infinite horizon when the rewards are given by Markov chains whose statistics are perfectly known in advance. Note that our model does not consider discounting in the rewards and assumes that the relevant statistics are unknown.Auer et al. [10] presented an algorithm, called Exp4, which combines multiple strategies in anonstochastic bandit setting. In the nonstochastic MAB, it is assumed that each arm isinitially assigned an arbitrary and unknown sequence of rewards, one for each time step. In other words, the rewards obtained by playing a specific arm are predetermined. In Exp4, the “uniform expert,” which always selects an action uniformly over A, needs to be always included in Φ. At time t, Exp4 computes(1)
Exp
4
t
h
t
-
1
Exp
4
a
=
1
-
γ
∑
ϕ
∈
Φ
‍
w
ϕ
t
ϕ
t
h
t
-
1
Exp
4
a
+
γ
Φ
,
a
∈
A
,where h
t
-
1
Exp
4 is obtained from the predetermined sample reward sequence {
X
a
,
t
,
t
=
1
,
…
,
T
} of length T
<
∞, γ
∈
(
0,1
], and w
ϕ
(
t
) is a weight for ϕ such that ∑
ϕ
∈
Φ
‍
w
ϕ
(
t
)
=
1. w
ϕ
(
t
) is updated from the observed sample reward X
I
t
-
1
Exp
4
,
t
-
1 as follows: w
ϕ
(
t
)
=
w
ϕ
(
t
-
1
)
e
γ
y
ϕ
/
K with y
ϕ
=
∑
a
∈
A
‍
ϕ
t
-
1
(
h
t
-
2
Exp
4
)
(
a
)
f
(
a
), where f
(
a
)
=
X
a
,
t
-
1
/
Exp
4
t
-
1
(
h
t
-
2
Exp
4
)
(
a
)
[
a
=
I
t
-
1
Exp
4
] with [
·
] being Iverson bracket. An arm is then played according to the distribution Exp
4
t
(
h
t
-
1
Exp
4
). A finite-time upper bound (but no lower bound) of O
(
K
T
ln
⁡
|
Φ
|
) on the expected “regret” was analyzed against a best strategy that achieves the optimal total reward of max
⁡
ϕ
∈
Φ
{
∑
t
=
1
T
‍
∑
a
∈
A
‍
ϕ
t
(
h
t
-
1
ϕ
)
(
a
)
X
a
,
t
} with respect to the fixed sample reward sequences for the arms (see [11] for a probability version within a contextual bandit setting and [12] for a simplified derivation).McMahan and Streeter [13] proposed a variant of Exp4, called NEXP, in the same nonstochastic setting. NEXP needs to solve a linear program (LP) at each time to obtain a distribution over A that offers a “locally optimal” trade-off between exploration and exploitation. Even if some improvement over Exp4 was shown, this comes at the expense of solving an LP at every time step.de Farias and Megiddo [14] presented another variant of Exp4, called EEE, within a “reactive” setting. In this setting, at each time a player chooses an arm and an environment chooses its state, which is unknown to the player. The reward obtained by the player depends on both the chosen arm and the current state but not necessarily determined by a distribution specific to the chosen arm and the current state. An example of this setting is playing a repeated game against another player. When an expert is selected by EEE for a phase, it is followed for multiple times during the phase, rather than picking a different expert at each time, and the average reward accumulated for that phase is kept track of. The current best strategy with respect to the estimate of the average reward or a random strategy is selected at each phase with a certain control rule of exploration and exploitation, which is similar to the ϵ
t-schedule we consider here. (See also a survey section in [15] for expert-combining algorithms in different scenarios).Because these representative approaches combine multiple experts, we compare them with our algorithm after adapting into our setting (cf. Section4). However, more importantly, the notion of the best strategy in nonstochastic or reactive settings does not directly apply to the stochastic setting. Establishing some kind of asymptotic optimality for Exp4 or its variants with respect to a properly defined best strategy (even after adapting Exp4 as a strategy in Π) is an open problem. In fact, to the authors’ best knowledge, there seems to be no notable work yet which studies asymptotic optimality in combining multiple strategies forstochastic multiarmed bandit problems.Finally, we stress that this paper focuses on asymptotic optimality as performance measure, also termed as “instantaneous regret” [8], but not on “expected regret” which is typically considered in the (recent) existing bandit-theory literature (see, e.g., [12] for a survey). It is worthwhile to note that the instantaneous regret is a stronger measure of convergence than expected regret [8].


## 3. Algorithm and Convergence

Assume that a finite nonempty subsetΦ of Π is given. Once ϕ
∈
Φ is selected by the algorithm τ
=
ϵ
t
-comb
(
Φ
) at time t, the bandit is played with an arm selected by ϕ and a sample reward of X
I
t
ϕ
,
t is obtained. Let S
t
τ denote the random variable denoting the strategy selected by τ at time t, and (with abusing notations) let T
ϕ
τ
(
n
)
=
∑
t
=
1
n
‍
[
S
t
τ
=
ϕ
] denote the number of times ϕ has been selected by τ during the first n time steps, where [
S
t
τ
=
ϕ
]
=
1 if S
t
τ
=
ϕ and 0 otherwise. Let t
ϕ
,
1
τ
=
min
⁡
{
t
∣
S
t
τ
=
ϕ
,
t
≥
1
}, t
ϕ
,
2
τ
=
min
⁡
{
t
∣
S
t
τ
=
ϕ
,
t
>
t
ϕ
,
1
τ
}
,
…, and t
ϕ
,
s
τ
=
min
⁡
{
t
∣
S
t
τ
=
ϕ
,
t
>
t
ϕ
,
s
-
1
τ
} where t
ϕ
,
s
τ is the time for the sth selection of the strategy ϕ
∈
Φ by τ. For finite m
≥
1, we then let (2)
X
-
ϕ
,
m
τ
=
1
m
∑
s
=
1
m
‍
X
I
t
ϕ
,
s
τ
ϕ
,
t
ϕ
,
s
τ
,
ϕ
∈
Φ
.We formally describe the algorithm τ
=
ϵ
t
-comb
(
Φ
) below.The
τ
=
ϵ
t
-
c
o
m
b
(
Φ
)
Algorithm
(1)
Initialization: select ϵ
t
∈
(
0,1
], for t
=
1,2
,
…. Set t
=
1 and T
ϕ
τ
0
=
0
,
X
-
ϕ
,
0
τ
=
0
,
for
all
ϕ
∈
Φ.
(2)
Loop:
(2.1)
obtainS
t
∈
arg
⁡
max
⁡
ϕ
∈
Φ
X
-
ϕ
,
T
ϕ
τ
(
t
-
1
)
τ (ties broken arbitrarily);
(2.2)
with probability1
-
ϵ
t, select S
t and, with probability ϵ
t, select uniformly a strategy in Φ. Set the selected strategy ϕ to be S
t
τ. Select an arm according to ϕ
T
ϕ
τ
(
t
-
1
)
+
1
(
h
T
ϕ
τ
(
t
-
1
)
ϕ
) and obtain X
I
t
S
t
τ
,
t by playing it;
(2.3)
T
S
t
τ
τ
(
t
)
←
T
S
t
τ
τ
(
t
-
1
)
+
1 and t
←
t
+
1.Note thatϵ
t
-comb
(
Φ
) as above is involved with general schedule of {
ϵ
t
}. By setting the {
ϵ
t
}-schedule in ϵ
t
-comb
(
Φ
) properly, {
ϵ
t
} subsumes the schedules used in ϵ-greedy, ϵ-first, and ϵ-decreasing strategies [16, 17]. In particular, as a special case, if Φ
=
{
ϕ
a
,
a
=
1
,
…
,
K
} and ϕ
a is given such that P
a
ϕ
a
(
t
)
=
1 for all t, then τ degenerates to the ϵ
t-greedy strategy. As shown in the experimental results in [16, 17], the performance oftuned
ϵ-greedy is no worse than (or very close to) those of ϵ-first, ϵ-decreasing strategies, and so forth, even with tuning the schedule (and the relevant parameters) each strategy used. However, because these schedules are usually heuristically tuned and ϵ-greedy uses a constant value of ϵ, it is not necessarily guaranteed that employing such schedules in ϵ
t
-comb
(
Φ
) achieves asymptotic optimality. Furthermore, it is very difficult to tune the value of ϵ in advance. The theorem below establishes general conditions for asymptotic optimality of τ with respect to a properly defined best strategy in Φ. It states that if each ϕ
∈
Φ is selected infinitely often by τ and for each ϕ, each a
∈
A is selected infinitely often by ϕ, and each ϕ’s action-selection distribution converges to a stationary distribution, and the selection of τ goes greedy in the limit; then the selected strategy by τ converges to the best strategy in Φ.Theorem 1.
Given a finite nonemptyΦ
⊂
Π, consider τ
=
ϵ
t
-
c
o
m
b
(
Φ
). Suppose that lim
t
→
∞
ϵ
t
=
0, that ∑
t
=
0
∞
‍
ϵ
t
=
∞, that there exists α
>
0 such that P
a
ϕ
(
t
)
≥
α for all ϕ
∈
Φ
,
a
∈
A, and t
≥
1, and that lim
t
→
∞
P
ϕ
(
t
)
=
d
ϕ for all ϕ
∈
Φ. Then (3)
lim
t
→
∞
Pr
⁡
S
t
τ
∈
arg
⁡
max
⁡
ϕ
∈
Φ
⁡
∑
a
∈
A
‍
d
a
ϕ
μ
a
=
1
.Proof.
Becauselim
t
→
∞
P
ϕ
(
t
)
=
d
ϕ
,
for
all
ϕ
∈
Φ from the assumption, there exists t
ϵ
<
∞ such that, for all t
≥
t
ϵ, max
⁡
a
∈
A
|
P
a
ϕ
(
t
)
-
d
a
ϕ
|
≤
ϵ
,
for
all
ϕ
∈
Φ. Fix any ϕ
∈
Φ. Then decomposing the sample average such that(4)
1
T
ϕ
τ
(
t
-
1
)
∑
s
=
1
T
ϕ
τ
(
t
-
1
)
‍
X
I
t
ϕ
,
s
τ
ϕ
,
t
ϕ
,
s
τ
=
1
T
ϕ
τ
(
t
-
1
)
∑
s
=
1
T
ϕ
τ
(
t
ϵ
)
‍
X
I
t
ϕ
,
s
τ
ϕ
,
t
ϕ
,
s
τ
+
1
T
ϕ
τ
(
t
-
1
)
∑
s
=
T
ϕ
τ
(
t
ϵ
)
+
1
T
ϕ
τ
(
t
-
1
)
‍
X
I
t
ϕ
,
s
τ
ϕ
,
t
ϕ
,
s
τ
,we see that as t
→
∞, the first term in the right-hand side of (4) goes to zero because T
ϕ
τ
(
t
-
1
)
→
∞ from ∑
t
=
0
∞
‍
ϵ
t
=
∞ and T
ϕ
τ
(
t
ϵ
)
<
∞. For the second term in the right-hand side of (4), we rewrite it as (5)
T
ϕ
τ
(
t
-
1
)
-
T
ϕ
τ
(
t
ϵ
)
T
ϕ
τ
(
t
-
1
)
·
∑
s
=
T
ϕ
τ
(
t
ϵ
)
+
1
T
ϕ
τ
(
t
-
1
)
X
I
t
ϕ
,
s
τ
ϕ
,
t
ϕ
,
s
τ
T
ϕ
τ
(
t
-
1
)
-
T
ϕ
τ
(
t
ϵ
)and we will establish the convergence of the right product term in (5): (6)
1
T
ϕ
τ
(
t
-
1
)
-
T
ϕ
τ
(
t
ϵ
)
∑
s
=
T
ϕ
τ
(
t
ϵ
)
+
1
T
ϕ
τ
(
t
-
1
)
‍
X
I
t
ϕ
,
s
τ
ϕ
,
t
ϕ
,
s
τbecause (
T
ϕ
τ
t
-
1
-
T
ϕ
τ
t
ϵ
)
/
T
ϕ
τ
(
t
-
1
) goes to one.
LetN
a
(
T
ϕ
τ
(
n
)
)
=
∑
s
=
1
T
ϕ
τ
(
n
)
‍
[
I
t
ϕ
,
s
τ
ϕ
=
a
]
,
a
∈
A. Then (6) can be rewritten such that(7)
∑
s
=
T
ϕ
τ
(
t
ϵ
)
+
1
T
ϕ
τ
(
t
-
1
)
X
I
t
ϕ
,
s
τ
ϕ
,
t
ϕ
,
s
τ
T
ϕ
τ
(
t
-
1
)
-
T
ϕ
τ
(
t
ϵ
)
=
∑
a
∈
A
‍
N
a
T
ϕ
τ
t
-
1
-
N
a
T
ϕ
τ
t
ϵ
T
ϕ
τ
t
-
1
-
T
ϕ
τ
t
ϵ
×
∑
n
=
t
ϵ
+
1
t
-
1
X
a
,
n
S
n
τ
=
ϕ
∧
I
n
ϕ
=
a
N
a
T
ϕ
τ
t
-
1
-
N
a
T
ϕ
τ
t
ϵ
.
BecauseP
a
ϕ
(
t
)
≥
α for all t, we have that, as t
→
∞, N
a
(
T
ϕ
τ
(
t
-
1
)
)
-
N
a
(
T
ϕ
τ
(
t
ϵ
)
)
→
∞. Therefore the second product term inside of the summation in the right-hand side of (7),(8)
∑
n
=
t
ϵ
+
1
t
-
1
X
a
,
n
S
n
τ
=
ϕ
∧
I
n
ϕ
=
a
N
a
T
ϕ
τ
t
-
1
-
N
a
T
ϕ
τ
t
ϵ
,goes to μ
a by the law of large numbers. We now show that the first product term inside of the summation in the right-hand side of (7), (
N
a
(
T
ϕ
τ
(
t
-
1
)
)
-
N
a
(
T
ϕ
τ
(
t
ϵ
)
)
)
/
(
T
ϕ
τ
(
t
-
1
)
-
T
ϕ
τ
(
t
ϵ
)
), goes to d
a
ϕ as t
→
∞. Let (9)
P
-
a
ϵ
=
P
a
ϕ
t
ϕ
,
T
ϕ
τ
t
ϵ
+
1
τ
+
P
a
ϕ
t
ϕ
,
T
ϕ
τ
t
ϵ
+
2
τ
+
⋯
+
P
a
ϕ
t
ϕ
,
T
ϕ
τ
t
-
1
τ
T
ϕ
τ
(
t
-
1
)
-
T
ϕ
τ
(
t
ϵ
)
.Then by Poisson’s limit theorem [18, Chapter 11] in the law of large numbers, for any β
>
0, (10)
Pr
⁡
N
a
(
T
ϕ
τ
(
t
-
1
)
)
-
N
a
T
ϕ
τ
t
ϵ
T
ϕ
τ
(
t
-
1
)
-
T
ϕ
τ
(
t
ϵ
)
-
P
-
a
ϵ
≤
β
≥
1
-
1
4
T
ϕ
τ
t
-
1
-
T
ϕ
τ
t
ϵ
β
2
.Because |
P
a
ϕ
(
t
)
-
d
a
ϕ
|
≤
ϵ for all t
≥
t
ϵ,  |
P
-
a
ϵ
-
d
a
ϕ
|
≤
ϵ. By setting β
=
ϵ and using triangular inequality, we have that, for any ϵ
>
0, (11)
Pr
⁡
N
a
(
T
ϕ
τ
(
t
-
1
)
)
-
N
a
(
T
ϕ
τ
(
t
ϵ
)
)
T
ϕ
τ
(
t
-
1
)
-
T
ϕ
τ
(
t
ϵ
)
-
d
a
ϕ
≤
2
ϵ
≥
1
-
1
4
(
T
ϕ
τ
(
t
-
1
)
-
T
ϕ
τ
(
t
ϵ
)
)
ϵ
2
.It follows that with probability 1, as t
→
∞, X
-
ϕ
,
T
ϕ
τ
(
t
-
1
)
τ
→
∑
a
∈
A
‍
d
a
ϕ
μ
a. Finally, because ϵ
t
→
0 as t
→
∞, the result of the theorem follows.We remark that this algorithm can be used for solving a bandit problem in a decomposed manner. Suppose that we partitionA into m nonempty subsets A
i
,
i
=
1
,
…
,
m, such that A
i
∩
A
j
=
∅
,
i
≠
j and ⋃
i
=
1
m
‍
A
i
=
A. Choose any asymptotically optimal strategy ϕ and associate ϕ with a strategy ϕ
i such that ∑
a
∈
A
i
∖
A
i
*
‍
P
a
ϕ
i
(
t
)
→
0 as t
→
∞, where A
i
*
=
{
a
∈
A
i
∣
μ
a
=
max
⁡
a
′
∈
A
i
μ
a
′
} and P
a
ϕ
i
(
t
)
=
0 for all a
∈
A
∖
A
i. Then by employing τ
=
ϵ
t
-comb
(
Φ
) where Φ
=
{
ϕ
1
,
…
,
ϕ
m
}, we have that ∑
a
∈
A
∖
A
*
‍
P
a
S
t
τ
(
t
)
→
0 as t
→
∞.


## 4. A Numerical Example

For a proof-of-concept implementation of the approach, we consider three simple numerical examples.We have Bernoulli reward distributions withK
=
10 where the reward expectations of the arms 1 through 10 are given by 0.9,0.8,0.8,0.8,0.7,0.7,0.7,0.6,0.6, and 0.6, respectively. For any strategy π involved with {
ϵ
t
} in this section, including ϵ
t
-comb
(
Φ
), we used {
ϵ
t
}-schedule in ϵ
t-greedy strategy given by min
⁡
{
1
,
c
π
/
K
d
2
t
} based on [8, Theorem 3], where d
=
min
⁡
a
∈
A
∖
A
*
(
μ
*
-
μ
a
) and c
(
π
) is a constant chosen for π to control the degree of exploration and exploitation.For the first case,A is partitioned into A
i
,
i
=
1,2
,
3, such that A
1
=
{
1,2
,
3,4
}, A
2
=
{
5,6
,
7
}, and A
3
=
{
8,9
,
10
} and the ϵ
t-greedy strategy associated with A
i, playing only the arms in A
i, corresponds to ϕ
i (cf. the remark given at the end of Section 3). Thus we have Φ
=
{
ϕ
i
,
i
=
1,2
,
3
} and trivially the best strategy is ϕ
1. The second case considers combining two pursuit learning automata (PLA) algorithms [19] with different learning rates designed for solving stochastic optimization problems. Even though PLA was not designed specifically for solving multiarmed bandit problems, PLA guarantees “ϵ-optimality” and can be casted into a strategy for playing the bandit. (Roughly, the error probability of choosing nonoptimal solutions is bounded by ϵ.) The first PLA strategy uses the learning rate of 0.000002 which corresponds to the parameter setting in [19, Theorem 3.1] with ϵ
=
0.1 for a theoretical performance guarantee and the second one uses the tuned learning rate of 0.002 which achieves the best performance among the various rates we tested for the above distribution. These two PLAs are contained in Φ and the PLA with 0.002 is taken as the best strategy.From Figures1–3, we show the percentage of selections of the best strategy and of plays of the optimal arm of (tuned) ϵ
t
-comb
(
Φ
) for each case along with those of (tuned) Exp4, NEXP, and EEE, respectively. (The percentage for the optimal arm for the second case is not shown due to the space constraint.) The tuned strategy corresponds to the best empirical parameter setting we obtained. The performances of all tested strategies were obtained through the average over 1000 different runs where each strategy is followed over 100,000 time steps in a single run. For the first case, that is, Φ
=
{
3
ϵ
t
-greedy’s
}, we set c
(
ϕ
)
=
0.15 for all ϕ
∈
Φ, and c
(
τ
)
=
0.15 for τ
=
ϵ
t
-comb
(
Φ
), and c
(
EEE
)
=
0.15 for EEE. (The value of 0.15 was chosen for a reasonable allocation of exploration and exploitation.) The tuned τ uses 0.075 for c
(
τ
) and the tuned EEE uses 0.07 for c
(
EEE
). Exp4 uses 0.0116 for γ which was obtained by the parameter setting in [10, Corollary 3.2] and the tuned Exp4 uses 0.03. For the second case, that is, Φ
=
{
2
PLAs
}, we set again c
(
τ
)
=
c
(
EEE
)
=
0.15. The tuned τ uses 0.3333 for c
(
τ
), and the tuned EEE uses 0.04 for c
(
EEE
) and (tuned) Exp4 uses the same γ value in the first case. As we can see from Figures 1–3 (tuned) τ successfully combines the strategies in Φ achieving the asymptotic optimality with respect to the best strategy for each case. In particular, τ’s convergence rate is much faster than that of (even tuned) Exp4, NEXP, and EEE for each case. Note that by tuning c
(
τ
), τ achieves a better performance, which shows a similar sensitivity to {
ϵ
t
}-schedule as in the ϵ
t-greedy strategy case [8].Figure 1
Percentage of selections of the best strategy of (tuned)ϵ
t-comb(3 ϵ
t-greedy strategies) and of (tuned) Exp4/NEXP/EEEs for the distribution (0.9,0.8,0.8,0.8,0.7,0.7,0.7,0.6,0.6,0.6).Figure 2
Percentage of plays of the optimal arm of (tuned)ϵ
t-comb(3 ϵ
t-greedy strategies) and of (tuned) Exp4/NEXP/EEEs for the distribution (0.9,0.8,0.8,0.8,0.7,0.7,0.7,0.6,0.6,0.6).Figure 3
Percentage of selections of the best strategy of (tuned)ϵ
t-comb(2 PLAs) and of (tuned) Exp4/NEXP/EEEs for the distribution (0.9,0.8,0.8,0.8,0.7,0.7,0.7,0.6,0.6,0.6).The third case considers the case of combining two different strategies, theϵ
t-greedy strategy and UCB1-tuned [8], and was chosento show some robustness of ϵ
t
-comb
(
Φ
). Here the ϵ
t-greedy strategy uses the value of 0.3 for {
ϵ
t
}-schedule. (Tuning the ϵ
t-greedy strategy will make it more competitive with UCB1-tuned. This particular value was chosen for an illustration purpose only.) Figure 4 shows the average regret of each strategy π tested over n time steps for two different distributions, respectively, calculated by 1
0
-
3
∑
r
=
1
1
0
3
‍
∑
a
∈
A
‍
(
μ
*
-
μ
a
)
T
a
,
r
π
(
n
) where T
a
,
r
π
(
n
) denotes the number of times arm a has been played by π during the first n plays in the rth run. The first distribution is the same as the above one used for the first and the second cases. The second distribution is again Bernoulli reward distributions with K
=
10 but the reward expectations are given by 0.9 for the optimal arm 1 and 0.7 for all the remaining arms. For the first distribution, UCB1-tuned’s regret is much smaller than that of the ϵ
t-greedy strategy but for the second distribution, the ϵ
t-greedy strategy is slightly better than UCB1-tuned. In sum, we have the case where the better performance of the two strategies is distribution-dependent in terms of the average regret even if both achieve asymptotic optimality empirically (not shown here). By combining two strategies by τ
=
ϵ
t
-comb
(
{
UCB
1
-tuned
,
ϵ
t
-greedy
}
), we have a reasonabledistribution-independent algorithm for playing the bandit. As we can see from Figure 4, the tuned τ with c
(
τ
)
=
0.0375 and 0.01, respectively, shows a robust performance across the two distributions. For both cases, the performances of the tuned Exp4, NEXP, and EEE are not good.Figure 4
Average regret of tunedϵ
t-comb({
ϵ
t-greedy, UCB1-tuned}) and of tuned Exp4 for the distributions of (0.9,0.8,0.8,0.8,0.7,0.7,0.7,0.6,0.6,0.6) and (0.9,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7).


## 5. Concluding Remarks

In this paper, we provided a randomized algorithmϵ
t
-comb
(
Φ
) for playing a given stochastic MAB when a finite nonempty strategy set Φ is available. Following the spirit of the ϵ
t-greedy strategy, the algorithm combines the strategies in Φ and finds the best strategy in the limit. Specifically, at each time t, we use the probabilistic ϵ
t-switching to select uniformly a strategy in Φ or to select a strategy with the highest sample average of the rewards obtained so far by playing the bandit. Once a strategy ϕ is selected, the arm chosen by ϕ is played for the bandit. We showed that it is asymptotically optimal in the sense that the selected strategy converges to the best in the set under some conditions on the strategies in Φ and {
ϵ
t
} and illustrated the result by simulation studies on some example problems.If eachϕ
∈
Φ is stationary (as opposed to the general case studied in the present paper) in that, for a distribution d
ϕ over A, P
ϕ
(
t
)
=
d
ϕ for all t, then each ϕ
∈
Φ can be viewed as an arm and playing according to ϕ provides a sample reward of X
I
t
ϕ
,
t with unknown expectation of ∑
a
∈
A
‍
d
a
ϕ
μ
a. Therefore, in this case any asymptotically optimal strategy in Π can be adapted for selecting a strategy at each time instead of ϵ
t
-comb
(
Φ
) to achieve asymptotic optimality with respect to a strategy that achieves max
⁡
ϕ
∈
Φ
∑
a
∈
A
‍
d
a
ϕ
μ
a.Even if we showed the convergence to the best strategy in the set, the convergence rate has not been discussed. In the statement of Theorem1, we assumed only that lim
t
→
∞
P
ϕ
(
t
)
=
d
ϕ
,
for
all
ϕ
∈
Φ. In other words, the convergence rate of each strategy in Φ to its stationary behavior is assumed to be unknown. Because the convergence rate of ϵ
t
-comb
(
Φ
) needs to be given with respect to arg
⁡
max
⁡
ϕ
∈
Φ
∑
a
∈
A
‍
d
a
ϕ
μ
a, it is crucial to know the convergence rate of each strategy in Φ. It would be a good future work to analyze the convergence rate of ϵ
t
-comb
(
Φ
), for example, by extending the result of Theorem 3 in [8] for ϵ
t-greedy strategy into the case of ϵ
t
-comb
(
Φ
), under the conditions on the rates of {
P
ϕ
(
t
)
} to d
ϕ
,
for
all
ϕ
∈
Φ.



---

*Source: 264953-2015-03-25.xml*