1

An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of
Multi-Armed Bandit

Shintaro Nakamura 1,2 and Masashi Sugiyama 2,1
1 University of Tokyo
2 RIKEN AIP

Keywords: Combinatorial bandit, pure exploration, (transductive) linear bandit

Abstract

We study the real-valued combinatorial pure exploration problem in the
stochastic multi-armed bandit (R-CPE-MAB). We study the case where the size of
the action set is polynomial with respect to the number of arms. In such a
case, the R-CPE-MAB can be seen as a special case of the so-called
transductive linear bandits. Existing methods in the R-CPE-MAB and
transductive linear bandits have a gap of problem-dependent constant terms and
logarithmic terms between the upper and lower bounds of the sample complexity,
respectively. We close these gaps by proposing an algorithm named the
combinatorial gap-based exploration (CombGapE) algorithm, whose sample
complexity upper bound matches the lower bound. Finally, we numerically show
that the CombGapE algorithm outperforms existing methods significantly.

##  1 Introduction

The stochastic multi-armed bandit (MAB) model is one of the most popular
models for action-making problems where we investigate trade-offs between
exploration and exploitation in a stochastic environment. In this model, we
are given a set of stochastic arms associated with unknown distributions.
Whenever an arm is pulled, it generates a reward sampled from the
corresponding distribution. The MAB model is mainly used for two objectives.
One is regret minimization, or cumulative reward maximization (Auer et al.,
2002a, ; Bubeck and Cesa-Bianchi,, 2012; Auer et al., 2002b, ), where the
player tries to maximize its average rewards by sequentially pulling arms by
balancing _exploring_ all the distributions and _exploiting_ the most
rewarding ones. The other is pure exploration (Audibert et al.,, 2010;
Gabillon et al.,, 2012), where the player tries to identify the optimal arm
with high probability with as few samples as possible.

On the other hand, it is well known that many real-world problems can be
modeled as linear optimization problems, such as the shortest path problem,
the optimal transport problem, the minimum spanning tree problems, the
traveling salesman problem, and many more (Sniedovich,, 2006; Villani,, 2008;
Pettie and Ramachandran,, 2002; Gutin et al.,, 2001). Abstractly, these linear
optimization problems can be formulated as follows:

$\begin{array}[]{ll@{}ll}\text{maximize}_{\boldsymbol{\pi}}&\boldsymbol{\mu}^{\top}\boldsymbol{\pi}&\\\
\text{subject
to}&\boldsymbol{\pi}\in\mathcal{A}\subset\mathbb{R}^{d},&\end{array}$

where $\boldsymbol{\mu}\in\mathbb{R}^{d}$ is a given vector that specifies the
cost, $d(\geq 2)$ is a positive integer, $\top$ denotes the transpose, and
$\mathcal{A}$ is a set of feasible solutions. For instance, if we see the
shortest path problem in Figure 2, each edge $i\in\\{1,\ldots,7\\}$ has a cost
$\mu_{i}$ and
$\mathcal{A}=\\{(1,0,1,0,0,1,0),(0,1,0,1,0,1,0),(0,1,0,0,1,0,1)\\}$. The
optimal transport problem shown in Figure 2 can also be formulated similarly
to the above. We have five suppliers and four demanders. Each supplier $i$ has
$s_{i}$ goods to supply. Each demander $j$ wants $d_{j}$ goods. Each edge
$\mu_{ij}$ is the cost to transport goods from supplier $i$ to demander $j$.
Our goal is to minimize $\sum_{i=1}^{5}\sum_{j=1}^{4}\pi_{ij}\mu_{ij}$ where
$\pi_{ij}(\geq 0)$ is the number of goods transported to demander $j$ from
supplier $i$.

Figure 1: A simple sketch of the shortest path problem. One candidate of
$\boldsymbol{\pi}$ can be
$\boldsymbol{\pi}=\left(1,0,1,0,0,1,0\right)^{\top}$.

Figure 2: A simple sketch of the optimal transport problem. One candidate of
$\boldsymbol{\pi}$ can be $\boldsymbol{\pi}=\begin{pmatrix}2&0&0&0\\\
1&2&0&0\\\ 0&2&1&0\\\ 0&0&1&0\\\ 0&0&2&2\\\ \end{pmatrix}.$

In real-world applications, the cost can often be random variables. For
instance, in the shortest path problem, each edge (road) can be congested, and
therefore the cost stochastically changes. Here, our main interest is to
identify the best action $\boldsymbol{\pi}^{*}\in\mathcal{A}$ which maximizes
the expectation of the objective $\boldsymbol{\mu}^{\top}\boldsymbol{\pi}$ in
the MAB framework.

There are many MAB frameworks where the goal is to identify the best action
for a linear objective in a stochastic environment (Soare et al.,, 2014; Xu et
al.,, 2018; Kuroki et al.,, 2020; Rejwan and Mansour,, 2020; Jourdan et al.,,
2021; Chen et al.,, 2014; Du et al., 2021a, ) (Table 1). Our work focuses on
the combinatorial pure exploration of the MAB (CPE-MAB) framework (Chen et
al.,, 2014; Wang and Zhu,, 2022; Gabillon et al.,, 2016). In CPE-MAB, the
player pulls a certain arm $i$ in each round and observes its reward. The
player’s goal is to identify the best action
$\boldsymbol{\pi}^{*}\in\mathcal{A}$ with the smallest number of rounds.

Most of the existing works in CPE-MAB (Chen et al.,, 2014; Wang and Zhu,,
2022; Gabillon et al.,, 2016; Chen et al.,, 2017; Du et al., 2021a, ; Chen et
al.,, 2016) assume $\mathcal{A}\subset\\{0,1\\}^{d}$, which means the player’s
objective is to identify the best action which maximizes the sum of the
expected rewards. Although we can apply this model to the shortest path
problem (Sniedovich,, 2006), top-$K$ arms identification (Kalyanakrishnan and
Stone,, 2010), matching (Gibbons,, 1985), and spanning trees (Pettie and
Ramachandran,, 2002), we cannot apply it to problems where
$\mathcal{A}\subset\mathbb{R}^{d}$ such as the optimal transport problem
(Villani,, 2008), the knapsack problem (Dantzig and Mazur,, 2007), and the
production planning problem (Pochet and Wolsey,, 2010). In this paper, we
study the real-valued CPE-MAB (R-CPE-MAB), where the action set is
$\mathcal{A}\subset\mathbb{R}^{d}$. For the R-CPE-MAB, Nakamura and Sugiyama,
(2023) proposed a Thompson sampling-based algorithm, which works even when the
size of the action set is exponentially large in $d$. They assumed that they
have _offline oracles_ that compute $\mathop{\rm
arg~{}max}\limits_{\boldsymbol{\pi}\in\mathcal{A}}\boldsymbol{\nu}^{\top}\boldsymbol{\pi}$
efficiently, once $\boldsymbol{\nu}$ is given. However, an extra problem-
dependent constant factor exists between the sample complexity upper bound and
the lower bound, and may lead to a large gap for some action sets. On the
other hand, if we assume the size of the action set is polynomial in $d$, the
R-CPE-MAB reduces to a special case of the transductive linear bandits (Fiez
et al.,, 2019; Katz-Samuels et al.,, 2020). Unfortunately, existing algorithms
in the transductive linear bandits have an extra logarithmic factor between
the sample complexity upper bound and the lower bound.

In this paper, we propose an optimal algorithm named the CombGapE
(Combinatorial Gap-Based Exploration) algorithm for the R-CPE-MAB for the case
where the size of the action set $\mathcal{A}$ is polynomial in $d$. We show
that the upper bound of the CombGapE matches the lower bound. We also show
that the CombGapE algorithm significantly outperforms existing methods
numerically.

The remainder of this paper is structured as follows. In Section 2, we
formally introduce the R-CPE-MAB. In Sections 3, we explain why naively
modifying existing methods for CPE-MAB may not be suited for R-CPE-MAB, and
give a new arm selection strategy for R-CPE-MAB. In Section 4, we show our
algorithm inspired by Xu et al., (2018) and theoretically analyze the sample
complexity of our algorithm. Finally, we experimentally compare our algorithm
to some existing works in Section 5 and conclude our work in Section 6.

Related Works and the Location of this Work

Table 1: Taxonomy of MAB problems. We compare the pure exploration in linear bandits (PE-LB), combinatorial pure exploration with full-bandit linear feedback, combinatorial pure exploration with semi-bandit linear feedback (CPE-S-LB), combinatorial pure exploration of multi-armed bandit(CPE-MAB), and the real-valued combinatorial pure exploration of multi-armed bandit(R-CPE-MAB). | Player’s behavior | Observation | Characteristic of $\mathcal{A}$
---|---|---|---
PE-LB | Play an action $\boldsymbol{\pi}(t)$ | $\boldsymbol{\mu}^{\top}\boldsymbol{\pi}(t)+\epsilon_{t}$ | $\mathcal{A}\subset\mathbb{R}^{d}$
CPE-F-LB | Play an action $\boldsymbol{\pi}(t)$ | $\sum_{i:\boldsymbol{\pi}_{i}(t)=1}r_{i}$ | $\mathcal{A}\subset\\{0,1\\}^{d}$
CPE-S-LB | Play an action $\boldsymbol{\pi}(t)$ |  | $\\{r_{i}\mid\forall i\in[d],$
---
$\pi_{i}(t)=1\\}$
$\mathcal{A}\subset\\{0,1\\}^{d}$
CPE-MAB | Pull an arm $i$ | $r_{i}$ | $\mathcal{A}\subset\\{0,1\\}^{d}$
| R-CPE-MAB
---
(this work)
Pull an arm $i$ | $r_{i}$ | $\mathcal{A}\subset\mathbb{R}^{d}$

Here, we introduce models that investigate the best action identification in
linear objective optimization with an MAB framework (Table 1). Then, we
briefly explain the location of this work in the literature.

Pure Exploration in Linear Bandits (PE-LB) In PE-LB (Soare et al.,, 2014; Xu
et al.,, 2018), we are given in advance a set of actions whose size is
polynomial in $d$. Then, in each time step $t$, the player chooses an action
$\boldsymbol{\pi}(t)$ from the action set and observes a reward with noise,
i.e., $r(t)=\boldsymbol{\mu}^{\top}\boldsymbol{\pi}(t)+\epsilon(t)$, where
$\epsilon(t)$ is a random noise from a certain distribution. Since
$\boldsymbol{\mu}$ is typically treated as an unknown vector, many algorithms
estimate $\boldsymbol{\mu}$ by leveraging the sequence of action selections.
For instance, Soare et al., (2014) used the least-squares estimator to
estimate $\boldsymbol{\mu}$.

Combinatorial Pure Exploration with Full-Bandit Linear Feedback (CPE-F-BL) In
CPE-F-BL (Kuroki et al.,, 2020; Rejwan and Mansour,, 2020), arms are often
called _base arms_ , and the actions are often called _super arms_. Super arms
are subsets of base arms, therefore $\mathcal{A}\subset\\{0,1\\}^{d}$. In each
time step, the player chooses an action and observes the sum of rewards from
the base arms involved in the chosen action. Therefore, CPE-F-BL can be seen
as an instance of PE-LB. However, since the running time of existing methods
for PE-LB has polynomial dependence on the size of action space, they are not
suitable for CPE-F-BL, where the size of the action space $\mathcal{A}$ can be
exponentially large with respect to $d$. To cope with this problem, algorithms
specifically designed for CPE-F-BL have been explored in the literature
(Kuroki et al.,, 2020; Rejwan and Mansour,, 2020; Du et al., 2021b, ).

Combinatorial Pure Exploration with Semi-Bandit Linear Feedback (CPE-S-BL)
CPE-S-BL (Jourdan et al.,, 2021) is a framework similar to CPE-F-BL: In each
round, the player chooses an action from the set of actions (super arms)
$\mathcal{A}\subset\\{0,1\\}^{d}$, which is a subset of base arms. Yet, the
observation is different. The player observes rewards $r_{i}$ for every base
arm $i$ where $\pi_{i}=1$. For instance, in Figure 2, if the player chooses
$\boldsymbol{\pi}=(1,0,1,0,0,1,0)$, she can observe the rewards of base arms
1, 3, and 6.

Transductive Linear Bandit Problem Fiez et al., (2019) introduced a framework
named the _transductive linear bandit problem_ : given a set of _measurement
vectors_ $\mathcal{X}\subset\mathbb{R}^{d}$, a set of actions
$\mathcal{A}\subset\mathbb{R}^{d}$, a fixed confidence $\delta$, and an
unknown vector $\boldsymbol{\mu}\subset\mathbb{R}^{d}$, a player tries to
identify $\mathop{\rm
arg~{}max}\limits_{\boldsymbol{\pi}\in\mathcal{A}}\boldsymbol{\mu}^{\top}\boldsymbol{\pi}$
with probability more than $1-\delta$ by sequentially choosing a measurement
vector $\boldsymbol{x}(t)\in\mathcal{X}$ in each round $t$ and observing a
stochastic random variable whose expected value is
${\boldsymbol{x}(t)}^{\top}\boldsymbol{\mu}$. When $\mathcal{X}=\mathcal{A}$,
this setting reduces to the linear bandits, and when $\mathcal{X}$ is the
standard basis vectors and $\mathcal{A}\subset\mathbb{R}^{d}$, this setting
reduces to the R-CPE-MAB. Therefore, we can apply existing algorithms from the
transductive linear bandit, such as the RAGE (Randomized Adaptive Gap
Elimination) (Fiez et al.,, 2019) and Peace (Katz-Samuels et al.,, 2020)
algorithms for the R-CPE-MAB.

Contribution of this Work

In this work, we propose the CombGapE (combinatorial gap-based exploration)
algorithm, which is the first algorithm whose sample complexity upper bound
matches the lower bound for the R-CPE-MAB. We also discuss the difference
between the R-CPE-MAB and the ordinary CPE-MAB and show both quantitatively
and qualitatively that naively applying algorithms in the literature of the
ordinary CPE-MAB is not a good choice for the R-CPE-MAB. Finally, we
numerically show that the CombGapE algorithm outperforms existing methods,
taking an example of the knapsack problem.

##  2 Problem Formulation

In this section, we formally define our R-CPE-MAB model similar to Chen et
al., (2014). Suppose we have $d$ arms, numbered $1,\ldots,d$. Assume that each
arm $s\in[d]$ is associated with a reward distribution $\phi_{s}$, where
$[d]=\\{1,\ldots,d\\}$. We assume all reward distributions have $R$-sub-
Gaussian tails for some known constant $R>0$. Formally, if $X$ is a random
variable drawn from $\phi_{s}$ for some $s\in[d]$, then, for all
$t\in\mathbb{R}$, we have
$\mathbb{E}[\exp(tX-t\mathbb{E}[X])]\leq\exp(R^{2}t^{2}/2)$. It is known that
the family of $R$-sub-Gaussian tail distributions includes all distributions
that are supported on $[0,R]$ and also many unbounded distributions such as
Gaussian distributions with variance $R^{2}$ (Rivasplata,, 2012). Let
$\boldsymbol{\mu}=(\mu_{1},\ldots,\mu_{d})^{\top}$ denote the vector of
expected rewards, where each element $\mu_{s}=\mathbb{E}_{X\sim\phi_{s}}[X]$
denotes the expected reward of arm $s$ and $\top$ denotes the transpose. We
denote the number of times arm $s$ pulled before round $t$ by $T_{s}(t)$, and
by
$\boldsymbol{\hat{\mu}}(t)=(\hat{\mu}_{1}(t),\ldots,\hat{\mu}_{d}(t))^{\top}$
the vector of sample means of each arm in round $t$.

We define the action class
$\mathcal{A}=\\{\boldsymbol{\pi}^{1},\ldots,\boldsymbol{\pi}^{K}\
|\boldsymbol{\pi}^{1},\ldots,\boldsymbol{\pi}^{K}\in\mathbb{R}^{d}\\}$ as the
set of all actions whose size is $K$. We assume $K$ is polynomial in $d$. Let
$\boldsymbol{\pi}^{*}=\mathop{\rm
arg~{}max}\limits_{\boldsymbol{\pi}\in\mathcal{A}}\boldsymbol{\mu}^{\top}\boldsymbol{\pi}$
denote the optimal member in the action class $\mathcal{A}$ which maximizes
$\boldsymbol{\mu}^{\top}\boldsymbol{\pi}$. Let $a^{*}$ be the index of
$\boldsymbol{\pi}^{*}$, i.e., $\boldsymbol{\pi}^{*}=\boldsymbol{\pi}^{a^{*}}$.
We denote the true gap and the estimated gap in time step $t$ by
$\Delta_{ij}=\boldsymbol{\mu}^{\top}(\boldsymbol{\pi}^{i}-\boldsymbol{\pi}^{j})$
and
$\hat{\Delta}_{ij}(t)={\hat{\boldsymbol{\mu}}(t)}^{\top}(\boldsymbol{\pi}^{i}-\boldsymbol{\pi}^{j})$,
respectively.

The player’s objective is to identify $\boldsymbol{\pi}^{*}$ from
$\mathcal{A}$ by playing the following game. At the beginning of the game, the
action class $\mathcal{A}$ is revealed while the reward distributions
$\\{\phi_{s}\\}_{s\in[d]}$ are unknown to her. Then, the player pulls an arm
over a sequence of rounds; in each round $t$, she pulls an arm $p(t)\in[d]$
and observes a reward $r_{p(t)}$ sampled from the associated reward
distribution $\phi_{p(t)}$. The game continues until a certain stopping
condition is satisfied. After the game finishes, the player outputs an action
$\boldsymbol{{\pi}}_{\mathrm{out}}\in\mathcal{A}$. Let ${a}_{\mathrm{out}}$ be
the index of $\boldsymbol{{\pi}}_{\mathrm{out}}$, i.e.,
$\boldsymbol{{\pi}}_{\mathrm{out}}=\boldsymbol{\pi}^{{a}_{\mathrm{out}}}$.

The problem is to design an algorithm to find an action
$\boldsymbol{\pi}_{\mathrm{out}}$ which satisfies

$\Pr\left[\boldsymbol{\pi}^{*}\neq\boldsymbol{\pi}_{\mathrm{out}}\right]\geq
1-\delta,$

as fast as possible. We denote by $\tau$ the round an algorithm terminated. We
use the term sample complexity as the round an algorithm terminated.

##  3 The Arm Selection Strategy

In this section, we discuss the arm selection strategy qualitatively and
quantitatively. We first qualitatively show that applying or naively modifying
existing works in CPE-MAB for R-CPE-MAB may not be a good choice. Then, we
discuss the arm selection strategy quantitatively by looking at the confidence
bound of the estimated gap between actions and propose a new arm selection
strategy for R-CPE-MAB.

###  3.1 Limitation of Existing Works in CPE-MAB

Here, we first briefly explain what some of the existing algorithms in CPE-MAB
(Chen et al.,, 2014; Gabillon et al.,, 2016; Wang and Zhu,, 2022) are doing at
a higher level. First, in each round $t$, they output the action
$\hat{\boldsymbol{\pi}}(t)$ which maximizes
${\hat{\boldsymbol{\mu}}(t)}^{\top}\boldsymbol{\pi}$. As we have seen in the
example in Figure 2, we denote by $\hat{S}$ the set that contains all the arms
“used” in $\hat{\boldsymbol{\pi}}(t)$. Next, they output another action
$\tilde{\boldsymbol{\pi}}(t)$, which potentially be the best action by
considering a confidence bound on arms. Similarly, we denote by $\tilde{S}$
the set of arms that contains all the arms “used” in
$\tilde{\boldsymbol{\pi}}(t)$. Finally, they choose the arm $s$ that is in
$\hat{S}\oplus\tilde{S}=(\hat{S}\setminus\tilde{S})\cup(\tilde{S}\setminus\hat{S})$
with the least number of pulls. This means they are choosing an arm $s$ where
$\hat{{\pi}}_{s}(t)\neq\tilde{\pi}_{s}(t)$. They repeat this until some
stopping condition for the algorithm is satisfied.

In R-CPE-MAB, we can no longer think
$\hat{S}\oplus\tilde{S}=(\hat{S}\setminus\tilde{S})\cup(\tilde{S}\setminus\hat{S})$
since we are thinking of $\mathcal{A}\subset\mathbb{R}^{d}$, and therefore
have to think of other arm selection strategies. One naive way to modify their
methods to R-CPE-MAB is to choose the arm $s$ with the least number of times
it was pulled among the set of arms $\\{s\in[d]\ |\
\hat{\pi}_{s}(t)\neq\tilde{\pi}_{s}(t)\\}$. However, this may not be an
efficient strategy to pull arms in R-CPE-MAB. To explain this, suppose we have
two actions $\boldsymbol{\pi}^{1}=(100,0,0.1)$ and
$\boldsymbol{\pi}^{2}=(0,100,0.2)$, and the stopping condition for an
algorithm is not satisfied. Also, let us assume that we are pretty sure that
$\hat{{\mu}}_{1}(t)\in(0.9-0.01,0.9+0.01)$,
$\hat{{\mu}}_{2}(t)\in(0.9-0.01,0.9+0.01)$, and
$\hat{{\mu}}_{3}(t)\in(0.9-0.01,0.9+0.01)$ using some concentration
inequality. Here, although the confidence interval is all the same when we
estimate the gap between actions 1 and 2, i.e.,
$\boldsymbol{\mu}^{\top}(\boldsymbol{\pi}^{1}-\boldsymbol{\pi}^{2})$, the
uncertainty of arms 1 and 2 will be amplified by 100 times where the
uncertainty of arm 3 will be amplified by only 0.1 times. This example
suggests that we must consider how _important_ a certain arm is to estimate
the gaps between actions in R-CPE-MAB, and not simply pull the arm with the
least number of times it was pulled among the set of arms $\\{s\in[d]\ |\
\hat{\pi}_{s}(t)\neq\tilde{\pi}_{s}(t)\\}$. In Appendix B, we discuss the
limitation of other works on CPE-MAB (Du et al., 2021a, ; Chen et al.,, 2016,
2017), which are close to the above discussion.

###  3.2 Confidence Bounds and the Arm Selection Strategy

In Section 3.1, we have seen that the uncertainty of arms will be amplified
when we estimate gaps between actions. We discuss this quantitatively in this
section.

First, we bound the gap of two actions $\boldsymbol{\pi}^{k}$ and
$\boldsymbol{\pi}^{l}$ with a concentration inequality. Define $\beta_{kl}(t)$
as

$\displaystyle\beta_{kl}(t)=R\sqrt{\frac{1}{2}\sum_{s=1}^{d}\frac{(\pi^{k}_{s}-\pi^{l}_{s})^{2}}{T_{s}(t)}\log\frac{2K^{2}t^{2}}{\delta}}.$
(1)

Then, we have the following proposition.

######  Proposition 3.1.

Let $T_{s}(t)$ be the number of times arm $s$ has been pulled before round
$t$. Then, for any $t\in\mathbb{N}$ and
$\boldsymbol{\pi}^{k},\boldsymbol{\pi}^{l}\in\mathcal{A}$, with probability at
least $1-\delta$, we have

$\displaystyle\Pr\left(\left|\Delta_{kl}-\hat{\Delta}_{kl}(t)\right|\leq\beta_{kl}(t)\right)\geq
1-\delta.$ (2)

We show the proof in Appendix C. If we set $\delta$ small, Lemma 3.1 shows
that the estimated gap between two actions is close to the true gap with high
probability. We regard

$\displaystyle\hat{\Delta}_{kl}(t)+\beta_{kl}(t)$ (3)

as an upper confidence bound of the estimated gap between actions
$\boldsymbol{\pi}^{k}$ and $\boldsymbol{\pi}^{l}$.

Assume we want to estimate the gap between two actions $\boldsymbol{\pi}^{k}$
and $\boldsymbol{\pi}^{l}$. Since we want to estimate it as fast as possible,
we want to pull an arm that makes the confidence bound $\beta_{kl}(t)$
smallest.

$\displaystyle p(t)=\mathop{\rm
arg~{}min}\limits_{u\in[d]}\sum_{s=1}^{d}\frac{(\pi^{k}_{s}-\pi^{l}_{s})^{2}}{T_{s}(t)+\boldsymbol{1}[s=u]},$
(4)

where $\boldsymbol{1}[\cdot]$ denotes the indicator function. Then, the
following proposition holds.

######  Proposition 3.2.

$p(t)$ in (4) can be written as follows:

$\displaystyle p(t)=\mathop{\rm
arg~{}max}\limits_{s\in[d]}\frac{(\pi^{k}_{s}-\pi^{l}_{s})^{2}}{T_{s}(t)(T_{s}(t)+1)}.$
(5)

We show the proof in Appendix D. Intuitively speaking, we can say computing
(5) is considering the _importance_ of each arm to estimate the gap between
$\boldsymbol{\pi}^{k}$ and $\boldsymbol{\pi}^{l}$. If
$({\pi}_{s}^{k}-{\pi}_{s}^{l})^{2}$ is large, that means the uncertainty of
arm $s$ can be amplified largely, and arm $s$ needs to be pulled many times to
reduce the gap between actions $\boldsymbol{\pi}^{k}$ and
$\boldsymbol{\pi}^{l}$. Additionally, the arm selection strategy (5) is
equivalent to pulling the arm with the least number of times pulled among
$\\{i\in[d]\ |\ {\pi}^{k}_{s}\neq{\pi}^{l}_{s}\\}$ in CPE-MAB. Therefore, we
can see the arm selection strategy (5) as a generalization of the arm
selection strategies in Chen et al., (2014), Gabillon et al., (2016), and Wang
and Zhu, (2022).

##  4 CombGapE Algorithm and Theoretical Analysis

In this section, we introduce our algorithm (Algorithm 1) inspired by Xu et
al., (2018). We name it CombGapE (Combinatorial Gap-based Exploration
algorithm). We first show that, given a confidence parameter $\delta$, the
CombGapE algorithm identifies the best action identification algorithm with a
probability of at least $1-\delta$. Then, we establish the sample complexity
of the CombGapE algorithm.

###  4.1 CombGapE Algorithm

We show our algorithm CombGapE in Algorithm 1. In each round, it chooses two
actions $\boldsymbol{\pi}^{i(t)}$ and $\boldsymbol{\pi}^{j(t)}$, the action
with the largest estimated reward and the action whose gap from
$\boldsymbol{\pi}^{i(t)}$ is the largest. We can say $\boldsymbol{\pi}^{i(t)}$
is the action that is most likely to be the best, and
$\boldsymbol{\pi}^{j(t)}$ is an action that is potentially the best. Then, as
we discussed in Section 3, CombGapE pulls the arm $p(t)$ that most reduces the
confidence bound $\beta_{i(t)j(t)}(t)$ (line 17).

Algorithm 1 CombGapE Algorithm

1: Input: Confidence level $\delta$ and an action set $\mathcal{A}$

2: Output: action $\boldsymbol{\pi}_{\mathrm{out}}\in\mathcal{A}$

3: $t\leftarrow 1$

4: // Initialization phase

5: for $s=1$ to $d$ do

6: Observe $r_{s}$

7: $t\leftarrow t+1$

8: end for

9: for $t=d+1$, … do

10: // Select which gap to examine

11: $(i(t),j(t),B(t))\leftarrow\textrm{Select-Ambiguous-Action($t$)}$ (see
Algorithm 2)

12: // Check the stopping condition

13: if $B(t)\leq 0$ then

14: return $\boldsymbol{\pi}^{i(t)}$ as the best action
$\boldsymbol{\pi}_{\mathrm{out}}$

15: end if

16: // Pull an arm based on (5)

17: Pull $p(t)=\mathop{\rm
arg~{}max}\limits_{s\in[d]]}\frac{(\pi^{i(t)}_{s}-\pi^{j(t)}_{s})^{2}}{T_{s}(t)(T_{s}(t)+1)}$

18: Observe $r_{p(t)}$, and update the number of
pulls:$T_{p(t)}(t+1)\leftarrow T_{p(t)}(t)+1$ and $T_{e}(t+1)\leftarrow
T_{e}(t)$ for all $e\neq p(t)$

19: end for

Algorithm 2 Select-Ambiguous-Action(t)

1: procedure Select-Ambiguous-Action()

2: Compute $\hat{\mu}_{s}(t)$ for every $s\in[d]$

3: $i(t)\leftarrow\mathop{\rm
arg~{}max}\limits_{i\in[K]}{\boldsymbol{\pi}^{i}}^{\top}\boldsymbol{\hat{\mu}}(t)$

4: $j(t)\leftarrow\mathop{\rm
arg~{}max}\limits_{j\in[K]}\hat{\Delta}_{ji(t)}(t)+\beta_{ji(t)}(t)$

5: $B(t)\leftarrow\max_{j\in[K]}\hat{\Delta}_{ji(t)}(t)+\beta_{ji(t)}(t)$

6: return $(i(t),j(t),B(t))$

7: end procedure

###  4.2 Accuracy and the Sample Complexity

Here, in Theorem 4.1, we first show that given a confidence parameter
$\delta$, our algorithm misidentifies the best action with probability at most
$\delta$.

######  Theorem 4.1.

The output of Algorithm 1 $\boldsymbol{\pi}^{a_{\mathrm{out}}}$ satisfies the
following condition:

$\displaystyle\Pr\left(\boldsymbol{\pi}^{*}\neq\boldsymbol{\pi}_{\mathrm{out}}\right)\geq
1-\delta.$ (6)

We show the proof in Appendix E.

Next, we show an upper bound of the sample complexity of the CombGapE
algorithm.

######  Theorem 4.2.

Assume that $\delta\in(0,1)$, any action class $\mathcal{A}\in\mathbb{R}^{d}$,
and any expected rewards $\boldsymbol{\mu}\in\mathbb{R}^{d}$ are given. The
reward distribution $\phi_{s}$ for each arm $s\in[d]$ is an $R$-sub-Gaussian
tail distribution. With probability at least $1-\delta$, the upper bound of
the sample complexity $\tau$ of Algorithm 1 is

$\displaystyle\mathcal{O}\left(R^{2}\max_{i\in[K]\setminus\left\\{a^{*}\right\\}}\left\\{\frac{\left(\sum_{u=1}^{d}\left|\pi^{*}_{u}-\pi_{u}^{i}\right|\right)^{2}}{\Delta^{2}_{i}}\right\\}\log\left(\frac{2K^{2}M^{2}}{\delta}\right)\right),$
(7)

where
$M=\left(2R\max_{i\in[K]}\left\\{\frac{2\sum_{u=1}^{d}\left|\pi_{u}^{*}-\pi_{u}^{i}\right|}{\Delta_{i}}\right\\}\left(\frac{K}{\delta}\right)^{\frac{1}{4}}\right)^{4}$.

We show the proof in Appendix F. From Fiez et al., (2019), a lower bound of
the sample complexity can be written as follows:

$\displaystyle\mathbb{E}\left[\tau\right]\geq
R^{2}\min_{\boldsymbol{\lambda}\in\Pi_{d}}\max_{i\in[K]\setminus\left\\{a^{*}\right\\}}\left\\{\frac{\sum_{s=1}^{d}\frac{\left|\pi^{*}_{s}-\pi_{s}^{i}\right|^{2}}{\lambda_{s}}}{\Delta_{i}^{2}}\right\\}\log\left(\frac{1}{2.4\delta}\right),$
(8)

where $\Pi_{d}=\left\\{\boldsymbol{v}\in\mathbb{R}^{d}\ |\
\sum_{s=1}^{d}v_{s}=1\right\\}$. From the max-min inequality (Bronstein,,
2014), we can rewrite (8) as follows:

$\displaystyle\mathbb{E}\left[\tau\right]$ $\displaystyle\geq$ $\displaystyle
R^{2}\min_{\boldsymbol{\lambda}\in\Pi_{d}}\max_{i\in[K]\setminus\left\\{a^{*}\right\\}}\left\\{\frac{\sum_{s=1}^{d}\frac{\left|\pi^{*}_{s}-\pi_{s}^{i}\right|^{2}}{\lambda_{s}}}{\Delta_{i}^{2}}\right\\}\log\left(\frac{1}{2.4\delta}\right)$
(9) $\displaystyle\geq$ $\displaystyle
R^{2}\max_{i\in[K]\setminus\left\\{a^{*}\right\\}}\min_{\boldsymbol{\lambda}\in\Pi_{d}}\left\\{\frac{\sum_{s=1}^{d}\frac{\left|\pi^{*}_{s}-\pi_{s}^{i}\right|^{2}}{\lambda_{s}}}{\Delta_{i}^{2}}\right\\}\log\left(\frac{1}{2.4\delta}\right)$
$\displaystyle=$ $\displaystyle
R^{2}\max_{i\in[K]\setminus\left\\{a^{*}\right\\}}\left\\{\frac{\left(\sum_{s=1}^{d}\left|\pi^{*}_{s}-\pi_{s}^{i}\right|\right)^{2}}{\Delta_{i}^{2}}\right\\}\log\left(\frac{1}{2.4\delta}\right),$

where the inequality follows from the min-max inequality theorem (Bronstein,,
2014) and the last equality follows from the method of Lagrange multipliers.
We can see that the upper bound of the CombGapE algorithm in (7) matches the
lower bound in (9).

###  4.3 Comparison with Existing Works

Some algorithms in the literature of transductive bandit can be used in the
R-CPE-MAB. Fiez et al., (2019) proposed the RAGE (Randomized Adaptive Gap
Elimination) algorithm whose upper bound of the sample complexity is

$\displaystyle\mathcal{O}\left(R^{2}\min_{\boldsymbol{\lambda}\in\Pi_{d}}\max_{i\in[K]\setminus\left\\{a^{*}\right\\}}\left\\{\frac{\sum_{s=1}^{d}\frac{\left|\pi^{*}_{s}-\pi_{s}^{i}\right|^{2}}{\lambda_{s}}}{\Delta_{i}^{2}}\right\\}\log\left(\frac{1}{\Delta_{\mathrm{min}}}\right)\log\left(\frac{1}{\delta}\right)\right),$
(10)

where $\Delta_{\mathrm{min}}=\min_{i\in[K]\setminus\\{a^{*}\\}}\Delta_{i}$.
The RAGE algorithm has an extra logarithmic term compared to the lower bound
in (9). Katz-Samuels et al., (2020) proposed an algorithm named the Peace
algorithm whose order of the sample complexity upper bound is the same as
RAGE. The Peace algorithm works only when the rewards of each arm follow a
Gaussian distribution. This is a relatively stronger assumption than our
assumption that each arm’s reward follows an $R$-sub-Gaussian distribution.

Nakamura and Sugiyama, (2023) proposed an algorithm named the GenTS-Explore
(Generalized Thompson Sampling Explore) algorithm for the R-CPE-MAB problem.
Its sample complexity upper bound is tight up to a problem-dependent constant
factor. This problem-dependent factor depends on $\mathcal{A}$. Depending on
$\mathcal{A}$, the gap between the upper and lower bounds becomes large. One
advantage the GenTS-Explore algorithm has over the CombGapE algorithm is that
it works even when the size of the action class is exponentially large in $d$.
It is an interesting future work to investigate whether there is an optimal
algorithm even when the size of the action class is exponentially large in
$d$.

In Section 5, we show that the CombGapE algorithm outperforms the RAGE, Peace,
and GenTS-Explore algorithms numerically.

##  5 Experiment

In this section, we numerically show that the CombGapE algorithm outperforms
existing methods. We compare the CombGapE algorithm with existing methods in
the best action identification problem for the knapsack problem (Dantzig and
Mazur,, 2007).

In the knapsack problem, we have $d$ items. Each item $s\in[d]$ has a weight
$w_{s}$ and value $v_{s}$. Also, there is a knapsack whose capacity is $W$ in
which we put items. Our goal is to maximize the total value of the knapsack,
not letting the total weight of the items exceed the capacity of the knapsack.
Formally, the optimization problem is given as follows:

$\begin{array}[]{ll@{}ll}\text{maximize}_{\boldsymbol{\boldsymbol{\pi}}\in\mathcal{A}}&\sum_{s=1}^{d}v_{s}\pi_{s}&\\\
\text{subject to}&\sum_{s=1}^{d}\pi_{s}w_{s}\leq W,&\end{array}$

where $\pi_{s}$ denotes the number of item $s$ in the knapsack. Here, the
weight of each item is known, but the value is unknown, and therefore has to
be estimated. In each time step, the player chooses an item $s$ and gets an
observation of value $v_{s}$, which can be regarded as a random variable from
an unknown distribution with mean $v_{s}$.

We generated the weight of each item uniformly from
$\left\\{5,6,\ldots,50\right\\}$ for our experiment. For each item $s\in[d]$,
we generated $v_{s}$ as $v_{s}=w_{s}+x$, where $x$ is a uniform sample from
$[-5,5]$. As the capacity of the knapsack, $W=100$. As a prior knowledge of
the problem, we assumed that we know each $v_{s}$ is in $[w_{s}-5,w_{s}+5]$,
and used this prior knowledge to generate the action class $\mathcal{A}$ in
the following procedure. We first generated a vector $\boldsymbol{v}^{\prime}$
whose $s$-th element $v^{\prime}_{s}$ was uniformly sampled from
$[w_{s}-5,w_{s}+5]$, and then solved the knapsack problem with
$v^{\prime}_{s}$ and added the obtained solution $\boldsymbol{\pi}$ to
$\mathcal{A}$. We repeated this until 100 times, and therefore,
$|\mathcal{A}|\leq 100$. Each time we chose an item $s$, we observed a value
$v_{s}+x$ where $x$ is a noise from $\mathcal{N}(0,1)$. We set $R=1$. We ran
experiments 30 times.

We show the result in Table 2. We can see that the CombGapE algorithm using
the arm selection strategy shown in (5) significantly outperforms existing
methods.

Table 2: The mean and standard deviation of sample complexity of each algorithm normalized by the sample complexity of the CompGapE algorithm for different $d$. CombGapE (Naive) pulls the arm $a(t)=\mathop{\rm arg~{}min}\limits_{s\in\left\\{u\in[d]\ |\ \hat{\pi}_{u}(t)\neq\tilde{\pi}_{u}(t)\right\\}}T_{s}(t)$ each round (see the discussion in Section 3.1).  | $d=5$ | $d=7$ | $d=9$
---|---|---|---
CombGapE (Naive) | $2.6\pm 4.1$ | $3.0\pm 3.3$ | $2.2\pm 2.5$
GenTS-Explore | $65\pm 81$ | $58\pm 45$ | $74\pm 75$
RAGE |  | $1.8\times 10^{4}$
---
$\pm 3.5\times 10^{4}$
| $8.4\times 10^{3}$
---
$\pm 1.3\times 10^{4}$
| $2.0\times 10^{4}$
---
$\pm 4.0\times 10^{4}$
PEACE | $82\pm 96$ | $39\pm 29$ | $55\pm 49$

##  6 Conclusion

We studied the R-CPE-MAB in the stochastic multi-armed bandit for the case
where the size of the action set is polynomial with respect to the number of
arms, which can be seen as a special case of the so-called transductive linear
bandits. We proposed an optimal algorithm named the CombGapE algorithm, whose
sample complexity upper bound matches the lower bound. Also, we numerically
showed that the CombGapE algorithm outperforms existing methods significantly.

## Acknowledgement

We thank Dr. Kevin Jamieson for his very helpful advice and comments on
existing studies. SN was supported by JST SPRING, Grant Number JPMJSP2108. MS
was supported by JST CREST Grant Number JPMJCR18A2.

## References

  * Audibert et al., (2010) Audibert, J.-Y., Bubeck, S., and Munos, R. (2010).  Best arm identification in multi-armed bandits.  In The 23rd Conference on Learning Theory, pages 41–53.
  * (2) Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002a).  Finite-time analysis of the multiarmed bandit problem.  Machine Learning, 47:235–256.
  * (3) Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. (2002b).  The nonstochastic multiarmed bandit problem.  SIAM Journal on Computing, 32(1):48–77.
  * Bronstein, (2014) Bronstein, A. (2014).  Lagrangian duality.
  * Bubeck and Cesa-Bianchi, (2012) Bubeck, S. and Cesa-Bianchi, N. (2012).  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.
  * Chen et al., (2016) Chen, L., Gupta, A., and Li, J. (2016).  Pure exploration of multi-armed bandit under matroid constraints.  In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 647–669. JMLR.org.
  * Chen et al., (2017) Chen, L., Gupta, A., Li, J., Qiao, M., and Wang, R. (2017).  Nearly optimal sampling algorithms for combinatorial pure exploration.  In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 482–534. PMLR.
  * Chen et al., (2014) Chen, S., Lin, T., King, I., Lyu, M. R., and Chen, W. (2014).  Combinatorial pure exploration of multi-armed bandits.  In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1, page 379–387, Cambridge, MA, USA. MIT Press.
  * Dantzig and Mazur, (2007) Dantzig, T. and Mazur, J. (2007).  Number: The Language of Science.  A Plume book. Penguin Publishing Group.
  * (10) Du, Y., Kuroki, Y., and Chen, W. (2021a).  Combinatorial pure exploration with bottleneck reward function.  In Advances in Neural Information Processing Systems, volume 34, pages 23956–23967. Curran Associates, Inc.
  * (11) Du, Y., Kuroki, Y., and Chen, W. (2021b).  Combinatorial pure exploration with full-bandit or partial linear feedback.  In AAAI Conference on Artificial Intelligence.
  * Fiez et al., (2019) Fiez, T., Jain, L. P., Jamieson, K. G., and Ratliff, L. J. (2019).  Sequential experimental design for transductive linear bandits.  In Neural Information Processing Systems.
  * Fomin et al., (2015) Fomin, F. V., Philip, G., and Villanger, Y. (2015).  Minimum fill-in of sparse graphs: Kernelization and approximation.  Algorithmica, 71(1):1–20.
  * Gabillon et al., (2012) Gabillon, V., Ghavamzadeh, M., and Lazaric, A. (2012).  Best arm identification: A unified approach to fixed budget and fixed confidence.  In Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 2, NIPS’12, page 3212–3220, Red Hook, NY, USA. Curran Associates Inc.
  * Gabillon et al., (2016) Gabillon, V., Lazaric, A., Ghavamzadeh, M., Ortner, R., and Bartlett, P. (2016).  Improved learning complexity in combinatorial pure exploration bandits.  In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 1004–1012, Cadiz, Spain. PMLR.
  * Gibbons, (1985) Gibbons, A. (1985).  Algorithmic Graph Theory.  Cambridge University Press.
  * Gutin et al., (2001) Gutin, G., Punnen, A., Barvinok, A., Gimadi, E., and Serdyukov, A. (2001).  The traveling salesman problem and its variations.
  * Jourdan et al., (2021) Jourdan, M., Mutný, M., Kirschner, J., and Krause, A. (2021).  Efficient pure exploration for combinatorial bandits with semi-bandit feedback.  In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 805–849. PMLR.
  * Kalyanakrishnan and Stone, (2010) Kalyanakrishnan, S. and Stone, P. (2010).  Efficient selection of multiple bandit arms: Theory and practice.  In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML’10, page 511–518, Madison, WI, USA. Omnipress.
  * Katz-Samuels et al., (2020) Katz-Samuels, J., Jain, L., karnin, z., and Jamieson, K. G. (2020).  An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits.  In Advances in Neural Information Processing Systems, volume 33, pages 10371–10382. Curran Associates, Inc.
  * Kuroki et al., (2020) Kuroki, Y., Xu, L., Miyauchi, A., Honda, J., and Sugiyama, M. (2020).  Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback.  Neural Computation, 32(9):1733–1773.
  * Labille et al., (2021) Labille, K., Huang, W., and Wu, X. (2021).  Transferable contextual bandits with prior observations.  In Advances in Knowledge Discovery and Data Mining, pages 398–410, Cham. Springer International Publishing.
  * Nakamura and Sugiyama, (2023) Nakamura, S. and Sugiyama, M. (2023).  Thompson sampling for real-valued combinatorial pure exploration of multi-armed bandit.  arXiv:2308.10238.
  * Pettie and Ramachandran, (2002) Pettie, S. and Ramachandran, V. (2002).  An optimal minimum spanning tree algorithm.  J. ACM, 49(1):16–34.
  * Philip et al., (2009) Philip, G., Raman, V., and Sikdar, S. (2009).  Solving dominating set in larger classes of graphs: Fpt algorithms and polynomial kernels.  In Algorithms - ESA 2009, pages 694–705, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Pochet and Wolsey, (2010) Pochet, Y. and Wolsey, L. A. (2010).  Production Planning by Mixed Integer Programming.  Springer Publishing Company, Incorporated, 1st edition.
  * Rejwan and Mansour, (2020) Rejwan, I. and Mansour, Y. (2020).  Top-$k$ combinatorial bandits with full-bandit feedback.  In International Conference on Algorithmic Learning Theory.
  * Rivasplata, (2012) Rivasplata, O. (2012).  Subgaussian random variables : An expository note.
  * Sniedovich, (2006) Sniedovich, M. (2006).  Dijkstra’s algorithm revisited: the dynamic programming connexion.  Control and Cybernetics, 35:599–620.
  * Soare et al., (2014) Soare, M., Lazaric, A., and Munos, R. (2014).  Best-arm identification in linear bandits.  Advances in Neural Information Processing Systems, 1.
  * Villani, (2008) Villani, C. (2008).  Optimal Transport: Old and New.  Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg.
  * Wang and Zhu, (2022) Wang, S. and Zhu, J. (2022).  Thompson sampling for (combinatorial) pure exploration.  In Proceedings of the 39 th International Conference on Machine Learning, Baltimore, Maryland, USA.
  * Xu et al., (2018) Xu, L., Honda, J., and Sugiyama, M. (2018).  A fully adaptive algorithm for pure exploration in linear bandits.  In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 843–851. PMLR.
  * Yang and Gao, (2021) Yang, S. and Gao, Y. (2021).  An optimal algorithm for the stochastic bandits while knowing the near-optimal mean reward.  IEEE Transactions on Neural Networks and Learning Systems, 32(5):2285–2291.

##  Appendix A Situations where we can assume the size of $\mathcal{A}$ is
polynomial in $d$

In our study, we assume that the size of the action space $\mathcal{A}$ is
polynomial in $d$ so that we can run a search algorithm in the action space to
choose which arm to pull in each time step. For instance, if we think of the
shortest path problem, this assumption holds when the graph is sparse (Philip
et al.,, 2009; Fomin et al.,, 2015), and only a reasonably small number of
actions (path) have to be compared. Alternatively, even though it is nearly
impossible to identify the best action $\boldsymbol{\pi}^{*}$ which maximizes
$\boldsymbol{\mu}^{\top}\boldsymbol{\pi}$ from $\mathbb{R}^{d}$ due to the
uncertainty of $\boldsymbol{\mu}$, it may be sufficient to identify the best
action from a set of candidate $\mathcal{A}$. In order to construct
$\mathcal{A}$, one may use some prior knowledge of each arm, which is
sometimes obtainable in the real world (Labille et al.,, 2021; Yang and Gao,,
2021). For instance, if we model the real world with the optimal transport
problem, we may know in advance that some edges are clearly more costly than
others. For example, the distance from New York to San Francisco is clearly
farther than from New York to Boston. Also, nowadays, the approximate time
required to travel between two points on the globe can be easily obtained from
databases. Based on this prior knowledge, a realistic transportation method
can be narrowed down from all the solutions to the optimal transport problem.

##  Appendix B Limitation of existing works

Here, we discuss the limitation of other existing works in CPE-MAB (Du et al.,
2021a, ; Chen et al.,, 2016, 2017). Du et al., 2021a  introduced an algorithm
named GenLUCB, which is an algorithm for CPE-MAB. In each round, it computes a
lower and an upper bound for each arm’s reward, and uses the maximization
oracle to find the action $M_{t}$ with the maximum pessimistic reward from
$\mathcal{A}$ and the action $\tilde{M}_{t}$ with the maximum optimistic
reward from $\mathcal{A}\setminus\\{M_{t}\\}$. Then, we play the arm $p(t)$
with the maximum confidence radius from $M_{t}\cup\tilde{M}_{t}$, which is the
arm with the least number of times it was pulled among
$M_{t}\cup\tilde{M}_{t}$. The algorithm repeats this procedure until a certain
stopping condition is satisfied. However, as we discussed in Section 3, it is
not clear what sets $M_{t}$, $\tilde{M}_{t}$, and $M_{t}\cup\tilde{M}_{t}$ are
in R-CPE-MAB, since the action class is no longer binary in R-CPE-MAB. Chen et
al., (2016) introduces an algorithm for CPE-MAB when the action class
$\mathcal{A}$ is a matroid, such as the top-$k$ arm identification. However,
in R-CPE-MAB, $\mathcal{A}$ is not necessarily a matroid, and the
applicability is limited for our model. Chen et al., (2017) introduced the
NaiveGapElim algorithm, which is an algorithm for CPE-MAB. The sampling
procedure is a little different from CPE-MAB explained in Section 1, but
essentially the same. Each time step, it computes a vector
$\boldsymbol{m}=(m_{1},\ldots,m_{d})^{\top}$ by solving a certain optimization
problem, and pulls arm $s$ $m_{s}$ times. The algorithm is evaluated by the
total number of arms the algorithm pulled when it outputs the best action.
Therefore, it is essentially the same setting as our model. However,
$\boldsymbol{m}$ is computed by considering symmetric difference between
actions, which can only be defined when actions are binary.

##  Appendix C Proof of Proposition 3.1

Here, we prove Proposition 3.1. First, we recall the Hoeffding’s inequality,
which is a concentration inequality of sub-Gaussian random variables. The
proof of it can be seen in Lemma 6 in Chen et al., (2014).

######  Lemma C.1 (Hoeffding’s inequality (Chen et al.,, 2014)).

Let $X_{1},\ldots,X_{n}$ be $n$ independent random variables such that, for
each $i\in[n]$, random variable $X_{i}-\mathbb{E}[X_{i}]$ is $R$-sub-Gaussian
distributed, i.e., $\forall
t\in\mathbb{R},\mathbb{E}[\exp(tX_{i}-t\mathbb{E}[X_{i}])]\leq\exp(R^{2}t^{2}/2)$.
Let $\bar{X}=\sum_{i=1}^{n}X_{i}$ denote the average of these random
variables. Then, for any $\lambda>0$, we have

$\Pr\left[|\bar{X}-\mathbb{E}[\bar{X}]|\geq\lambda\right]\leq
2\exp\left(-\frac{n\lambda^{2}}{2R^{2}}\right)$ (11)

Next, we note that if $X_{1}$ and $X_{2}$ are $R_{1}$-sub-Gaussian and
$R_{2}$-sub-Gaussian random variables, respectively,
$\alpha_{1}X_{1}+\alpha_{2}X_{2}$ is $(\alpha R_{1}+\alpha R_{2})$-sub-
Gaussian. Here, $\alpha_{1},\alpha_{2}\in\mathbb{R}$. The proof can be seen in
Rivasplata, (2012).

Now, we prove Proposition 3.1.

###### Proof of Proposition 3.1.

Fix, $t$ and $k,l\in[K]$. From Hoeffding’s inequality (Lemma C.1), we have

$\displaystyle\Pr\left(\left|\Delta_{kl}-\hat{\Delta}_{kl}(t)\right|\leq\beta_{kl}(t)\right)$
(12) $\displaystyle\leq$ $\displaystyle
2\exp\left(-\frac{2{\beta_{kl}(t)}^{2}}{\sum_{s=1}^{d}\frac{(\pi^{k}_{s}-\pi^{l}_{s})^{2}R^{2}}{T_{s}(t)}}\right)$
$\displaystyle\leq$ $\displaystyle\frac{\delta}{K^{2}t^{2}}.$

From union bounds, for any $t\in\mathbb{N}$ and $k,l\in[K]$, we have

$\displaystyle\Pr\left(\left|\Delta_{kl}-\hat{\Delta}_{kl}(t)\right|\leq\beta_{kl}(t)\right)$
(13) $\displaystyle\leq$
$\displaystyle\sum_{k,l\in[K]}\sum_{t=1}^{\infty}\frac{\delta}{K^{2}t^{2}}$
$\displaystyle\leq$ $\displaystyle\delta.$

∎

##  Appendix D Proof of Proposition 3.2

Here, we prove Proposition 3.2.

###### Proof.

For any $q\neq p(t)$, we have

$\displaystyle\sum_{s=1}^{d}\frac{(\pi^{k}_{s}-\pi^{l}_{s})^{2}}{T_{k}(t)+\boldsymbol{1}[s=q]}\geq\sum_{s=1}^{d}\frac{(\pi^{k}_{s}-\pi^{l}_{s})^{2}}{T_{k}(t)+\boldsymbol{1}[s=p(t)]}.$
(14)

Thus,

$\frac{(\pi^{k}_{q}-\pi^{l}_{q})^{2}}{T_{q}(t)+1}+\frac{(\pi^{k}_{p(t)}-\pi^{l}_{p(t)})^{2}}{T_{p(t)}(t)}\geq\frac{(\pi^{k}_{q}-\pi^{l}_{q})^{2}}{T_{q}(t)}+\frac{(\pi^{k}_{p(t)}-\pi^{l}_{p(t)})^{2}}{T_{p(t)}(t)+1},$

which implies

$\frac{(\pi^{k}_{p(t)}-\pi^{l}_{p(t)})^{2}}{T_{p(t)}(t)(T_{p(t)}(t)+1)}\geq\frac{(\pi^{k}_{q}-\pi^{l}_{q})^{2}}{T_{q}(t)(T_{q}(t)+1)},$

for all $q\neq p(t)$ ∎

##  Appendix E Proof of Proposition 4.1

###### Proof.

Let $\mathcal{E}$ be an event defined as follows:

$\mathcal{E}=\\{\forall t>0,\ \forall
i,j\in[K],|\Delta_{ij}-\hat{\Delta}_{ij}(t)|\leq\beta_{ij}(t)\\}.$

From Proposition 3.1, this event holds with probability at least 1 - $\delta$.
Let $\tau$ be the stopping round of CombGapE. If
$\Delta(a^{*},a_{\mathrm{out}})>\epsilon$ holds, then we have

$\Delta_{a^{*}a_{\mathrm{out}}}>0\geq
B(\tau)\geq\hat{\Delta}_{a^{*}a_{\mathrm{out}}}(\tau)+\beta_{a^{*}a_{\mathrm{out}}}(\tau).$

The second inequality holds for stopping condition $B(\tau)\leq 0$ and the
last follows from the definition of $B(\tau)$. From this inequality, we can
see that $\Delta(a^{*},a_{\mathrm{out}})>0$ means that event $\mathcal{E}$
does not occur. Thus, the probability that CombGapE returns such actions is

$\Pr\left[\boldsymbol{\pi}_{\mathrm{out}}\neq\boldsymbol{\pi}^{*}\right]\geq\Pr\left[\mathcal{E}\right]\geq
1-\delta.$ (15)

∎

##  Appendix F Proof of Theorem 4.2

To prove Theorem 4.2, we first introduce two lemmas.

######  Lemma F.1 (Xu et al., (2018), Lemma. 5).

For any $i\in[K]$, let $\Delta_{i}$ defined as follows:

$\displaystyle\Delta_{i}=\begin{cases}\boldsymbol{\mu}^{\top}(\boldsymbol{\pi}^{*}-\boldsymbol{\pi}_{i})&\mathrm{if}\
i\neq a^{*},\\\ \mathop{\rm
arg~{}min}\limits_{j\in[K]}\boldsymbol{\mu}^{\top}(\boldsymbol{\pi}^{*}-\boldsymbol{\pi}_{j})&\mathrm{if}\
i=a^{*}.\end{cases}$ (16)

Under event $\mathcal{E}$, B(t) is bounded as follows. If $i(t)$ or $j(t)$ is
the best action, then

$\displaystyle
B(t)\leq\min(0,-(\Delta_{i(t)}\lor\Delta_{j(t)})+\beta_{i(t)j(t)}(t)))+\beta_{i(t)j(t)}(t).$

Otherwise, we have

$\displaystyle
B(t)\leq\min(0,-(\Delta_{i(t)}\lor\Delta_{j(t)})+2\beta_{i(t)j(t)}(t))+\beta_{i(t)j(t)}(t).$

where $a\lor b=\max(a,b)$.

Then, from Lemma F.1, we have either

$\displaystyle\min(0,-(\Delta_{i(t)}\lor\Delta_{j(t)})+\beta_{i(t)j(t)}(t))+\beta_{i(t)j(t)}(t)\geq
B(t)\geq 0,$ (17)

or

$\displaystyle\min(0,-(\Delta_{i(t)}\lor\Delta_{j(t)})+2\beta_{i(t)j(t)}(t))+\beta_{i(t)j(t)}(t)\geq
B(t)\geq 0.$ (18)

Therefore, we have

$\displaystyle\beta_{i(t)j(t)}(t)\geq\max\left\\{\frac{\Delta_{i(t)}}{3},\frac{\Delta_{j(t)}}{3}\right\\},$
(19)

if the stopping condition is not satisfied.

Now, we prove Theorem 4.2.

###### Proof of Theorem 4.2.

For any $t$, let us define $T_{ij}$ as follows:

$\displaystyle
T_{ij}(t)=\min_{s\in[d],\pi_{s}^{i}\neq\pi_{s}^{j}}\frac{T_{s}(t)(T_{s}(t)+1)}{(\pi_{s}^{i}-\pi_{s}^{j})^{2}}.$
(20)

Let $(d\leq)\tilde{t}\leq\tau$ be the last round arm $u$ was pulled. Then,

$\displaystyle
T_{i(\tilde{t})j(\tilde{t})}(\tilde{t})=\frac{T_{u}(\tilde{t})(T_{u}(\tilde{t})+1)}{(\pi^{i(\tilde{t})}_{u}-\pi^{j(\tilde{t})}_{u})^{2}}.$
(21)

If we solve this for $T_{u}(\tilde{t})$, we have

$\displaystyle
T_{u}(\tilde{t})=\frac{-1+\sqrt{1+4T_{i(\tilde{t})j(\tilde{t})}(\tilde{t})(\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})})^{2}}}{2}.$
(22)

Since arm $u$ is pulled in round $\tilde{t}$,

$\displaystyle T_{u}(\tau+1)$ $\displaystyle=$ $\displaystyle
T_{u}(\tilde{t})+1$ (23) $\displaystyle=$
$\displaystyle\frac{1+\sqrt{1+4T_{i(\tilde{t})j(\tilde{t})}(\tilde{t})(\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})})^{2}}}{2}.$

Moreover, since we have

$\displaystyle
T_{i(\tilde{t})j(\tilde{t})}(\tilde{t})\leq\frac{T_{s}(\tilde{t})(T_{s}(\tilde{t})+1)}{(\pi_{s}^{i(\tilde{t})}-\pi_{s}^{j(\tilde{t})})^{2}}$
(24)

for all $s\in[d]$, we have

$\displaystyle\frac{(\pi_{s}^{i(\tilde{t})}-\pi_{s}^{j(\tilde{t})})^{2}}{T_{s}(\tilde{t})}\leq\frac{T_{s}(\tilde{t})+1}{T_{i(\tilde{t})j(\tilde{t})}(\tilde{t})}.$
(25)

Therefore,

$\displaystyle\sum_{s=1}^{d}\frac{(\pi_{s}^{i(\tilde{t})}-\pi_{s}^{j(\tilde{t})})^{2}}{T_{s}(\tilde{t})}<\frac{\tau+d}{T_{i(\tilde{t})j(\tilde{t})}(\tilde{t})},$
(26)

because $\sum_{s=1}^{d}T_{s}(\tilde{t})=\tilde{t}-1<\tau$.

From (19), we have
$\left(\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}\right)^{2}\leq\beta_{i(\tilde{t})j(\tilde{t})}^{2}(\tilde{t})$,
and thus,

$\displaystyle\left(\max\left\\{\frac{\Delta_{i(t)}}{3},\frac{\Delta_{j(t)}}{3}\right\\}\right)^{2}\leq\frac{R^{2}}{2}\sum_{s=1}^{d}\frac{(\pi_{s}^{i(\tilde{t})}-\pi_{s}^{j(\tilde{t})})^{2}}{T_{s}(\tilde{t})}\cdot\log\left(\frac{2K^{2}\tilde{t}^{2}}{\delta}\right).$
(27)

Combining (26) and (27), we have

$\displaystyle T_{i(\tilde{t})j(\tilde{t})}(\tilde{t})$ $\displaystyle<$
$\displaystyle\frac{R^{2}}{2}\frac{\tau+d}{\left(\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}\right)^{2}}\log\left(\frac{2K^{2}\tilde{t}^{2}}{\delta}\right).$

If we substitute this for (23), we have

$\displaystyle T_{u}(\tau+1)$ $\displaystyle<$
$\displaystyle\frac{1+\sqrt{1+4R^{2}\frac{\tau+d}{2\left(\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}\right)^{2}}\log\left(\frac{2K^{2}\tilde{t}^{2}}{\delta}\right)\left(\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right)^{2}}}{2}$
$\displaystyle\leq$ $\displaystyle
1+\sqrt{R^{2}\frac{\tau+d}{2\left(\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\epsilon+\Delta_{j(\tilde{t})}}{3}\right\\}\right)^{2}}\log\left(\frac{2K^{2}\tau^{2}}{\delta}\right)\left(\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right)^{2}},$
$\displaystyle\leq$ $\displaystyle
1+\frac{R\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\epsilon,\frac{\epsilon+\Delta_{i(\tilde{t})}}{3},\frac{+\Delta_{j(\tilde{t})}}{3}\right\\}}\sqrt{\tau\log\left(\frac{2K^{2}\tau^{2}}{\delta}\right)},$
$\displaystyle\leq$
$\displaystyle\frac{2R\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}}\sqrt{\tau\log\left(\frac{2K^{2}\tau^{2}}{\delta}\right)},$

where the second inequality is because $\sqrt{x+1}\leq\sqrt{x}+1$ for all
$x\geq 0$, and the third inequality is because $d\leq\tau$. Since
$\sum_{u=1}^{d}T_{u}(\tau+1)=\tau$, if we sum up with $u$, we have

$\displaystyle\tau$ $\displaystyle\leq$ $\displaystyle
2R\frac{\sum_{u=1}^{d}\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}}\sqrt{\tau\log\left(\frac{2K^{2}\tau^{2}}{\delta}\right)}.$

Let $\tau^{{}^{\prime}}$ be a parameter satisfying

$\displaystyle\tau=2R\frac{\sum_{u=1}^{d}\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}}\sqrt{\tau^{{}^{\prime}}\log\left(\frac{2K^{2}{\tau^{{}^{\prime}}}^{2}}{\delta}\right)}.$
(28)

Since $f(x)=\alpha\sqrt{t\log(\beta t)}$ is a convex upward function of $x>0$
for any $\alpha,\beta>0$, $\tau^{{}^{\prime}}\leq\tau$ holds. We have

$\displaystyle\tau^{{}^{\prime}}$ $\displaystyle\leq$ $\displaystyle
2R\frac{\sum_{u=1}^{d}\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}}\sqrt{\tau^{{}^{\prime}}\log\left(\frac{2K^{2}{\tau^{{}^{\prime}}}^{2}}{\delta}\right)}$
$\displaystyle<$ $\displaystyle
2R\frac{\sum_{u=1}^{d}\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}}\sqrt{{\tau^{{}^{\prime}}}^{\frac{3}{2}}\sqrt{\frac{K}{\delta}}},$

where the second inequality is because $\log x<\sqrt{x}$ for $x\geq 1$.

If $\tau^{{}^{\prime}}\geq d$,

$\displaystyle\tau^{{}^{\prime}}<2R\frac{\sum_{u=1}^{d}\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}}{\tau^{{}^{\prime}}}^{\frac{3}{4}}\left(\frac{K}{\delta}\right)^{\frac{1}{4}},$

and therefore,

$\displaystyle{\tau^{{}^{\prime}}}\leq\left(2R\frac{\sum_{u=1}^{d}\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}}\left(\frac{K}{\delta}\right)^{\frac{1}{4}}\right)^{4}.$
(29)

Let $M$ be the RHS of (29). Combining this result with (28) and
$\tau^{{}^{\prime}}<\tau$, we have

$\displaystyle\tau<2R\frac{\sum_{u=1}^{d}\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}}\sqrt{\tau\log\left(\frac{2K^{2}M^{2}}{\delta}\right)}.$
(30)

If we solve this for $\tau$, we obtain

$\displaystyle\tau$ $\displaystyle<$ $\displaystyle
4R^{2}\left(\frac{\sum_{u=1}^{d}\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}}\right)^{2}\log\left(\frac{2K^{2}M^{2}}{\delta}\right)$
(31) $\displaystyle\leq$ $\displaystyle
4R^{2}\left(\frac{\sum_{u=1}^{d}\left|\pi_{u}^{i(\tilde{t})}-\pi_{u}^{*}\right|+\left|\pi_{u}^{*}-\pi_{u}^{j(\tilde{t})}\right|}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}}\right)^{2}\log\left(\frac{2K^{2}M^{2}}{\delta}\right)$
$\displaystyle\leq$ $\displaystyle
4R^{2}\frac{4{\max\left\\{\sum_{u=1}^{d}\left|\pi_{u}^{*}-\pi_{u}^{i(\tilde{t})}\right|,\sum_{u=1}^{d}\left|\pi_{u}^{*}-\pi_{u}^{j(\tilde{t})}\right|\right\\}}^{2}}{\max\left\\{\frac{\Delta_{i(\tilde{t})}}{3},\frac{\Delta_{j(\tilde{t})}}{3}\right\\}^{2}}\log\left(\frac{2K^{2}M^{2}}{\delta}\right)$
$\displaystyle\leq$ $\displaystyle
144R^{2}\max_{i\in[K]}\left\\{\frac{\left(\sum_{u=1}^{d}\left|\pi^{*}_{u}-\pi_{u}^{i}\right|\right)^{2}}{\Delta^{2}_{i}}\right\\}\log\left(\frac{2K^{2}M^{2}}{\delta}\right).$

∎